An optimization of path planning A* for static uniform grid based on pruning algorithms: Experimental experience

Abstract

Path-finding in uniform-cost grid environments is a popular task in different applications, like and video games, and robotics. In this project, several classical algorithms are presented and their work is explained, such as A*, Dijkstra, and Wave-front algorithm. A novel search strategy called Jump Point Search which uses pruning to decrease the discovered space is also presented. Jump Point Search is a designed optimal and fast algorithm for grids with no memory overhead. Moreover, Jump Point Search improvement will be discussed together with JPS+. We will use a benchmark to evaluate each of mentioned algorithms using different criteria, such as operation time, the number of visited nodes, and path length. Our environment will be a 2D uniform static grid. The aim of this article is to investigate the performance of several grid-based path-finding algorithms. We find that JPS produces the same path length as A* but with dramatically decreasing in time.