计算机工程与应用 ›› 2023, Vol. 59 ›› Issue (12): 309-315.DOI: 10.3778/j.issn.1002-8331.2203-0427

• 工程与应用 • 上一篇    下一篇

利用凸角点改进A*算法的路径规划方法

龚云鑫,刘桂华,张文凯,余东应,崔云轩,沈正斌   

  1. 西南科技大学 信息工程学院,四川 绵阳 621010
  • 出版日期:2023-06-15 发布日期:2023-06-15

Path Planning Method of Improving A* Algorithm Using Convex Corner

GONG Yunxin, LIU Guihua, ZHANG Wenkai, YU Dongying, CUI Yunxuan, SHEN Zhengbin   

  1. School of Information Engineering, Southwest University of Science and Technology, Mianyang, Sichuan 621010, China
  • Online:2023-06-15 Published:2023-06-15

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

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

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