An Improved JPS Algorithm in Symmetric Graph

摘要

Path planning is one of the most studied problems in the field of robotics, unmanned aerial vehicles (uavs), vehicle navigation and fields like these. The majority algorithms of path planning produce possible paths of grid graph, and then apply in problems such as classical graph route searching. Astar algorithm, Hierarchical Path-Finding A-star (HPA*) and Jump Point Search (JPS) algorithms are studied in this paper to compare the maze searching capacity and different search maps' efficiency. We also propose an improved JPS algorithm in symmetric grid graph. In this paper, we compare their search time and efficiency. Conducted experiment shows that by adopting the same benchmarks our algorithm not only tackles the congestion problem, but also solves the problem more efficiently. Experiments validated the improved JPS algorithm and results show it outperforms the other algorithms.