On A* Graph Search Algorithm Heuristics Implementation Towards Efficient Path Planning in the Presence of Obstacles

Abstract

Nowadays it has become more and more important to reach a destination in a short time, in the shortest path between all the options and possibilities. This need is addressed by different search engines like google maps for example and it is common sense that the user is expecting the result in the least amount of time. The scope of this publication, is to help the reader understand the mechanism behind pathfinding algorithms integrated with heuristics and on how to choose between them in a given case study. Moreover, this paper aims at illustrating, after pathfinding algorithm selection, how to tweak and improve it in order to better fit the given setup scenario. With this respect, it will be shown how the A* algorithm computationally performs in a graph theoretic grid setup, initially in a small one and then, in a graph grid with a 10- fold increase of the initial setup dimensions. This experimental study compares two different heuristics in A* implementation, the Euclidean distance heuristic and the Chebyshev heuristic. Computational time results are compared with respect to the time taken to produce a final result in each case. Moreover, the total number of nodes involved in the path as well as the total cost estimated are considered per each case. These results are further compared with the ones derived when obstacles are introduced in the graph grid setup and how the algorithm will handle such scenarios is illustrated. This paper aims at providing information to researchers so that to understand what analysis needs to be done when selecting heuristics associated with pathfinding algorithms heuristics, and at providing relevant performance metrics regarding shortest path planning estimation between two predefined nodes in a graph grid setup. Moreover, aims at providing information on how the heuristics define the decisionmaking process in the A* algorithm and on how to weight the time/cost factors importance based on specific use cases.