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

Path Planning Method of Improving A*Algorithm Using Convex Corner

作　　者：龚云鑫 刘桂华[1] 张文凯 余东应 崔云轩 沈正斌 GONG Yunxin;LIU Guihua;ZHANG Wenkai;YU Dongying;CUI Yunxuan;SHEN Zhengbin(School of Information Engineering,Southwest University of Science and Technology,Mianyang,Sichuan 621010,China)

机构地区：[1]西南科技大学信息工程学院,四川绵阳621010

出　　处：《计算机工程与应用》2023年第12期309-315,共7页Computer Engineering and Applications

基　　金：四川省科技厅重点研发项目(2021YFG0380)。

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

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

分 类 号：TP242.6[自动化与计算机技术—检测技术与自动化装置]