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

来源：计算机工程与应用杂志2023年第12期北京时间：

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

单位：西南科技大学 信息工程学院，四川 绵阳 621010

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

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