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

doi:10.3778/j.issn.1002-8331.2203-0427

摘要/Abstract

摘要： 针对传统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

龚云鑫, 刘桂华, 张文凯, 余东应, 崔云轩, 沈正斌. 利用凸角点改进A*算法的路径规划方法[J]. 计算机工程与应用, 2023, 59(12): 309-315.

GONG Yunxin, LIU Guihua, ZHANG Wenkai, YU Dongying, CUI Yunxuan, SHEN Zhengbin. Path Planning Method of Improving A* Algorithm Using Convex Corner[J]. Computer Engineering and Applications, 2023, 59(12): 309-315.

参考文献

[1] DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerische Mathematik，1959，1（1）：269-271.
[2] 李文刚，汪流江，方德翔，等.联合A*与动态窗口法的路径规划算法[J].系统工程与电子技术，2021，43（12）：3694-3702.
LI W G，WANG L J，FANG D X，et al.Path planning algorithm combining A* with DWA[J].Systems Engineering and Electronics，2021，43（12）：3694-3702.
[3] GURUJI A K，AGARWAL H，PARSEDIYA D K.Time-efficient A* algorithm for robot path planning[J].Procedia Technology，2016，23（3）：144-149.
[4] 李涛，赵宏生.基于进化蚁群算法的移动机器人路径优化[J].控制与决策，2023（3）：612-620.
LI T，ZHAO H S.Path optimization for mobile robot based on evolutionary ant colony algorithm[J].Control and Decision，2023（3）：612-620.
[5] 马小陆，梅宏.基于JPS策略的ACS移动机器人全局路径规划[J].机器人，2020，42（4）：494-502.
MA X L，MEI H.The global path planning of ant colony system mobile robot based on jump point search strategy[J].Robot，2020，42（4）：494-502.
[6] 李大东，孙秀霞，彭建亮，等.基于可视图法的改进Dijkstra算法[J].电光与控制，2010，17（3）：40-43.
LI D D，SUN X X，PENG J L，et al.A modified Dijkstra’s algorithm based on visibility graph[J].Electronics Optics & Control，2010，17（3）：40-43.
[7] 吕太之，赵春霞，夏平平.基于同步可视图构造和A*算法的全局路径规划[J].南京理工大学学报，2017，41（3）：313-321.
LV T Z，ZHAO C X，XIA P P.Global path planning based on simultaneous visibility and A* algorithm[J].Journal of Nanjing University of Science and Technology，2017，41（3）：313-321.
[8] 陈超，唐坚，靳祖光，等.一种基于可视图法导盲机器人路径规划的研究[J].机械科学与技术，2014，33（4）：490-495.
CHEN C，TANG J，JIN Z G，et al.Path planning algorithm for seeing eye robots based on V-Graph[J].Mechanical Science and Technology for Aerospace Engineering，2014，33（4）：490-495.
[9] 孔继利，张鹏坤，刘晓平.双向搜索机制的改进A*算法研究[J].计算机工程与应用，2021，57（8）：231-237.
KONG J L，ZHANG P K，LIU X P.Research on improved A* algorithm of bidirectional search mechanism[J].Computer Engineering and Applications，2021，57（8）：231-237.
[10] 郭晓静，杨卓橙.基于邻域拓展的静态路径规划A*算法研究[J].计算机工程与应用，2022，58（5）：168-174.
GUO X J，YANG Z C.Improved A* algorithm based on neighbor extension in static environment[J].Computer Engineering and Applications，2022，58（5）：168-174.
[11] HARABOR D，GRASTIEN A.The JPS pathfinding system[C]//5th Annual Symposium on Combinatorial Search.Menlo Park，USA：AAAI，2012：207-208.
[12] 张庆，刘旭，彭力，等.融合JPS和改进A*算法的移动机器人路径规划[J].计算机科学与探索，2021，15（11）：2233-2240.
ZHANG Q，LIU X，PENG L，et al.Path planning for mobile robot based on JPS and improved A* algorithm[J].Journal of Frontiers of Computer Science and Technology，2021，15（11）：2233-2240.
[13] 胡蔚旻，靳文舟.改进平滑A*算法的多AGV路径规划[J].计算机工程与应用，2020，56（16）：204-210.
HU W M，JIN W Z.Multi-AGV path planning based on improved smoothing A* algorithm[J].Computer Engineering and Applications，2020，56（16）：204-210.
[14] 殷绍伟，彭力，戴菲菲.融合改进A*蚁群和滚动窗口法的平滑路径规划[J].计算机科学与探索，2021，15（10）：1969-1979.
YIN S W，PENG L，DAI F F.Smooth path planning based on improved A* ant colony and rolling window method[J].Journal of Frontiers of Computer Science and Technology，2021，15（10）：1969-1979.
[15] 刘娅.基于可视图法的避障路径生成及优化[D].昆明：昆明理工大学，2012.
LIU Y.Obstacle avoidance path generation and optimization based on visual graph method[D].Kunming：Kunming University of Science and Technology，2012.