Robot navigation based on improved A* algorithm in dynamic environment

Abstract

Purpose

The purpose of this paper is to put forward a path planning method in complex environments containing dynamic obstacles, which improves the performance of the traditional A* algorithm, this method can plan the optimal path in a short running time.

Design/methodology/approach

To plan an optimal path in a complex environment with dynamic and static obstacles, a novel improved A* algorithm is proposed. First, obstacles are identified by GoogLeNet and classified into static obstacles and dynamic obstacles. Second, the ray tracing algorithm is used for static obstacle avoidance, and a dynamic obstacle avoidance waiting rule based on dilate principle is proposed. Third, the proposed improved A* algorithm includes adaptive step size adjustment, evaluation function improvement and path planning with quadratic B-spline smoothing. Finally, the proposed improved A* algorithm is simulated and validated in real-world environments, and it was compared with traditional A* and improved A* algorithms.

Findings

The experimental results show that the proposed improved A* algorithm is optimal and takes less execution time compared with traditional A* and improved A* algorithms in a complex dynamic environment.

Originality/value

This paper presents a waiting rule for dynamic obstacle avoidance based on dilate principle. In addition, the proposed improved A* algorithm includes adaptive step adjustment, evaluation function improvement and path smoothing operation with quadratic B-spline. The experimental results show that the proposed improved A* algorithm can get a shorter path length and less running time.

Citation

Zhang, L., Zhang, Y., Zeng, M. and Li, Y. (2021), "Robot navigation based on improved A* algorithm in dynamic environment", Assembly Automation, Vol. 41 No. 4, pp. 419-430. https://doi.org/10.1108/AA-07-2020-0095