Mobile Robots Path Planning based on A∗ Algorithm Improved with Jump Point Search

摘要

There are many proposed algorithms for path planning but the major challenges of them are high consumption of memory and a long execution time. To cope with such challenges, an algorithm based on A* algorithm improved with Jump Point Search (JPS) is proposed and verified in this paper. Firstly, instead of expanding a node into its adjacent nodes the A* algorithm is improved to expand by using the concept of jump points till an obstacle or end of the map is reached. Secondly, few nodes present on the opposite side of the direction of traversal that are leading away from the target are deleted. Finally, an optimal smoother path is obtained by removing redundancy from the path. In this paper the environment for the optimal navigation of the robot is described by using grid methods and a series of simulations performed are presented. Experimental results reveal that the designed algorithm based on the A* algorithm and JPS algorithm decreases the execution time of the path and it is effective compared with traditional A* algorithm.