Abstract: Aiming at the problems of poor path optimization, low search efficiency and low flexibility caused by the traditional A* algorithms failure to identify the environmental information effectively, an improved A* algorithm based on local obstacle rate pre-acquisition and bidirectional parent node change is proposed. Firstly, the local obstacle rate of each part of the grid map is obtained based on the drift matrix algorithm. Then, the pre-acquired local obstacle information is integrated into the improved A* algorithms evaluation function, and the search space is adaptively adjusted according to the different complexity of each region of the map. Finally, the improved parent node change method is used to further optimize the path and reduce the redundant points and inflection points of the generated path. The simulation results show that the algorithm has a significant improvement in the path length, the number of inflection points, search efficiency, running time and other indicators.

Key words: A* algorithm, path planning, grid map, drift matrix, node change