Abstract: Aiming at the problems of low search efficiency and low path obstacle avoidance performance of traditional A* algorithm in large map scene, an improved A* algorithm is proposed. The concepts of convex corner and neighbor relationship are defined. The convex corner is used as the node and the node is extended to the target point according to the neighbor relationship. The expansion method of using convex corners as nodes can reduce the access to unnecessary nodes and effectively improve the search efficiency of the algorithm. The performance of the improved algorithm is verified in grid maps of different sizes, and compared with the traditional A* algorithm and JPS algorithm. The experimental results show that the search time of the improved algorithm is reduced by about 95% and 90% respectively compared with A* algorithm and JPS algorithm, in maps with convex corners less than the threshold. And the path obstacle avoidance performance of the the improved algorithm is higher than that of the traditional A* algorithm, which is more conducive to the safe walking of the robot.

Key words: path planning, A* algorithm, convex corner, neighbor relationship

摘要： 针对传统A*算法在大地图场景中搜索效率低以及路径避障性能不高的问题，提出了一种改进的A*算法。定义了凸角点和邻居关系的概念，利用凸角点作为节点并根据邻居关系来扩展节点到目标点。将凸角点作为节点的扩展方式可以减少对不必要节点的访问，有效地提高算法搜索效率。在不同大小的栅格地图中验证改进算法的性能，并与传统A*算法和JPS算法进行比较。实验结果表明在凸角点数小于阈值的地图中，改进算法的搜索时间较A*算法和JPS算法分别减少了约95%和90%。并且改进算法的路径避障性能比传统A*算法更高，更有利于机器人安全行走。

关键词: 路径规划, A*算法, 凸角点, 邻居关系