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

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.

Keywords

• mobile robot
• path planning
• a* algorithm
• jump-point-search (jps)
• chebyshev distance