An improved A* path planning algorithm for mobile robots based on bilevel extension strategy

Path planning is one of the key technologies for autonomous navigation of mobile robots. The A* algorithm is a commonly used algorithm for path planning. However, the traditional A* algorithm has problems such as too many path turns, too many traversal nodes, long path finding time and long paths. Therefore, this paper proposes an improved A* algorithm based on a bilevel extension strategy, including obstacle block-based extension and feature corner point-based extension. The algorithm divides the obstacles on the raster map into different blocks, the outer level algorithm is responsible for planning the connection direction between different blocks, and the inner level algorithm plans the connection paths between specific feature corner points. The heuristic function of the traditional A* algorithm is also improved by adding directional angle information. Finally, the simulation and comparison experiments of the path planning algorithm were carried out using C++ and Matlab software, and the results show that compared with the traditional A* algorithm in two different map environments, the number of turning points of the paths planned by the improved A* algorithm in this paper is reduced by 57.1% and 46.7%, the search time is reduced by 62.2% and 48.9%, and the total length of the path is reduced by 8.3% and 12.7%, respectively. The experimental results show that the improved A* algorithm can achieve shorter path length, fewer turns, and shorter search time, which greatly improves the performance of the traditional algorithm.