融合JPS和改进A*算法的移动机器人路径规划

doi:10.3778/j.issn.1673-9418.2101020

摘要/Abstract

摘要：

针对传统A*算法在场景较大的栅格地图路径规划时，很多冗余节点的遍历导致寻路算法内存消耗大、计算速度慢等问题，提出了一种对A*算法的改进策略。首先，改进启发函数的具体计算方式，利用切比雪夫距离替代欧氏距离使启发式函数精确地等于实际最佳路径，减少A*节点的拓展数量；其次，使用跳点搜索（JPS）策略筛选出跳点添加到OpenList和ClosedList代替A*算法中大量不必要的邻节点，通过跳点实现较长距离的跳跃，从而减少内存占用以及对节点的评估，直到生成最终路径。为了验证A*算法改进后的效果，在五种尺寸的二维栅格地图中进行仿真测试，结果表明，改进后的A*算法减少了大量寻路过程评估的节点，提高了寻路速度，并且随着地图尺寸的增加，改进后的A*算法能将寻路速度提高一个数量级以上。最后，将改进后的算法应用在移动机器人路径规划器上进行实验，在同一规划任务下，JPS策略下改进的A*算法较传统A*算法，路径搜索耗费时间减少了92.2%，拓展的节点减少了97.37%，能够满足大场景下移动机器人快速路径规划的要求。

关键词: 移动机器人, 路径规划, A*算法, 跳点搜索（JPS）, 切比雪夫距离

Abstract:

In order to solve the problems of A* algorithm in raster map path planning, such as large memory consump-tion and slow computing speed due to the traversal of many redundant nodes, an improved strategy for A* algorithm is proposed. Firstly, the specific calculation method of the heuristic function is improved. The Chebyshev distance is used to replace the Euclidean distance so that the heuristic function is exactly equal to the actual optimal path and the number of A* node extension is reduced. Secondly, jump-point-search (JPS) strategy is used to screen out a large number of unnecessary neighboring nodes added to OpenList and ClosedList instead of A* algorithm. Long distance jumps are achieved through the hops, thereby reducing the memory footprint and evaluation of nodes until the final path is generated. In order to verify the improved effect of the A* algorithm, the simulation test is carried out in the two-dimensional raster map with five sizes. The results show that the improved A* algorithm reduces a large number of nodes in pathfinding process evaluation and improves pathfinding speed. Moreover, with the increase of map size, the improved A* algorithm can increase pathfinding speed by more than one order of magnitude. Finally, the improved algorithm can be applied to experiment on mobile robot path planning. Under the same planning tasks, the improved A* algorithm under JPS strategy than traditional A* algorithm, path search consuming time is decreased by 92.2%, and expanded nodes are decreased by 97.37%, which can satisfy the mobile robot fast path planning requirements in large scenarios.

Key words: mobile robot, path planning, A* algorithm, jump-point-search (JPS), Chebyshev distance

张庆，刘旭，彭力，朱凤增. 融合JPS和改进A*算法的移动机器人路径规划[J]. 计算机科学与探索, 2021, 15(11): 2233-2240.

ZHANG Qing, LIU Xu, PENG Li, ZHU Fengzeng. Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(11): 2233-2240.

参考文献

[1] QU D K, DU Z J, XU D G, et al. Research on path planning for a mobile robot[J]. Robot, 2008, 30(2): 97-101.
曲道奎, 杜振军, 徐殿国, 等. 移动机器人路径规划方法研究[J]. 机器人, 2008, 30(2): 97-101.
[2] ZHAO J P, GAO X W, LIU J G, et al. Parameters self-adaptive fuzzy ant colony optimization algorithm with sear-ching window for path planning of mobile robot[J]. Control and Decision, 2011, 26(7): 1096-1100.
赵娟平, 高宪文, 刘金刚, 等. 移动机器人路径规划的参数模糊自适应窗口蚁群优化算法[J]. 控制与决策, 2011, 26(7): 1096-1100.
[3] YUAN Y, YE F, LAI Y Z, et al. Multi-AGV path planning combined with load balancing and A* algorithm[J]. Com-puter Engineering and Applications, 2020, 56(5): 251-256.
袁洋, 叶峰, 赖乙宗, 等. 结合负载均衡与A*算法的多AGV路径规划[J]. 计算机工程与应用, 2020, 56(5): 251-256.
[4] CHEN R N, WEN C C, PENG L, et al. Application of im-proved A* algorithm in indoor path planning for mobile robot[J]. Journal of Computer Applications, 2019, 39(4): 1006-1011.
陈若男, 文聪聪, 彭玲, 等. 改进A*算法在机器人室内路径规划中的应用[J]. 计算机应用, 2019, 39(4): 1006-1011.
[5] CHEN Z W, XIA S, LI J X, et al. Serial strategy for rend-ezvous of multiple UAVS based on directional A* algorithm[J]. Control and Decision, 2019, 34(6): 1169-1177.
陈志旺, 夏顺, 李建雄, 等. 基于定向A*算法的多无人机同时集结分步策略[J]. 控制与决策, 2019, 34(6): 1169-1177.
[6] WU Z P, TANG N, CHEN Y L, et al. AUV path planning based on improved artificial potential field method[J]. Con-trol and Instruments in Chemical Industry, 2014, 41(12): 1421-1423.
吴正平, 唐念, 陈永亮, 等. 基于改进人工势场法的AUV路径规划[J]. 化工自动化及仪表, 2014, 41(12): 1421-1423.
[7] DAVOODI M, PANAHI M, MOHADES A, et al. Multi-objective path planning in discrete space[J]. Applied Soft Computing Journal, 2013, 13(1): 709-720.
[8] HUANG J, CHEN H W. Research on global path planning algorithm of mobile robot[J]. Instrument Technique & Sen-sor, 2014(12): 80-83.
黄静, 陈汉伟. 移动机器人全局路径规划算法的研究[J]. 仪表技术与传感器, 2014(12): 80-83.
[9] ZHANG Y, LI S, GUO H. A type of biased consensus-based distributed neural network for path planning[J]. Nonlinear Dynamics, 2017, 89(3): 1-13.
[10] WANG Y, HE T, SILVA P. Wide-band high-accuracy ADC using segmented DAC with DWA and mismatch shaping[J]. Electronics Letters, 2017, 53(11): 713-714.
[11] ZHANG H Q, DOU L H, FANG H, et al. Autonomous indoor exploration of mobile robots based on door-guidance and improved dynamic window approach[C]//Proceedings of the 2009 IEEE International Conference on Robotics and Bio-mimetics, Guilin, Dec 19-13, 2009. Piscataway: IEEE, 2009: 408-413.
[12] LI X Y, LIU F, LIU J, et al. Obstacle avoidance for mobile robot based on improved dynamic window approach[J]. Tur-kish Journal of Electrical Engineering and Computer Sci-ences, 2017, 25(2): 666-676.
[13] VISTA F P, SINGH A M, LEE D J, et al. Design convergent dynamic window approach for quadrotor navigation[J]. In-ternational Journal of Precision Engineering and Manufac-turing, 2014, 15(10): 2177-2184.
[14] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman pro-blem[J]. IEEE Transactions on Evolutionary Computation, 2002, 1(1): 53-66.
[15] KORF R E. Depth-first iterative-deepening: an optimal ad-missible tree search[J]. Artificial Intelligence, 1985, 27(1): 97-109.
[16] GOLDBERG A V, HARRELSON C. Computing the shortest path: A* search meets graph theory[C]//Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algori-thms, Vancouver, Jan 23-25, 2005. New York: ACM, 2005: 156-165.
[17] XIN Y, LIANG H W, DU M B, et al. An improved A* algo-rithm for searching infinite neighbourhoods[J]. Robot, 2014, 36(5): 627-633.
辛煜, 梁华为, 杜明博, 等. 一种可搜索无限个邻域的改进A*算法[J]. 机器人, 2014, 36(5): 627-633.
[18] HARABOR D, GRASTIEN A. Online graph pruning for path-finding on grid maps[C]//Proceedings of the 25th AAAI Conference on Artificial Intelligence, San Francisco, Aug 7-11, 2011. Menlo Park: AAAI, 2011: 1114-1119.