Journal of Frontiers of Computer Science and Technology ›› 2021, Vol. 15 ›› Issue (11): 2233-2240.DOI: 10.3778/j.issn.1673-9418.2101020

• Artificial Intelligence • Previous Articles    

Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm

ZHANG Qing, LIU Xu, PENG Li, ZHU Fengzeng   

  1. Engineering Research Center of Internet of Things Technology Applications of the Ministry of Education, School of Internet of Things Engineering, Jiangnan University, Wuxi, Jiangsu 214122, China
  • Online:2021-11-01 Published:2021-11-09

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

张庆刘旭彭力朱凤增   

  1. 物联网技术应用教育部工程研究中心(江南大学 物联网工程学院),江苏 无锡 214122

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

摘要:

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

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