Performance Evaluation of A' Algorithms

Abstract: Context. There have been a lot of progress made in the field of pathfinding. One of the most used algorithms is A', which over the years has had a lot of variations. There have been a number of papers written about the variations of A' and in what way they specifically improve A'. However, few papers have been written comparing A' with several different variations of A'. Objectives. The objectives of this thesis is to find how Dijkstra's algorithm, IDA', Theta' and HPA' compare against A' based on the variables computation time, number of opened nodes, path length as well as number of path nodes. Methods. To find the answers to the question in Objectives, an experiment was set up where all the algorithms were implemented and tested over a number of maps with varying attributes. Results. The experimental data is compiled in a table showing the result of the tested algorithms for computation time, number of opened nodes, path length and number of path nodes over a number of different maps as well as the average performance over all maps. Conclusions. A' is shown to perform well overall, with Dijkstra's algorithm trailing shortly behind in computation time and expanded nodes. Theta' finds the best path, with overall good computation time marred by a few spikes on large, open maps. HPA' performs poorly overall when fully computed, but has by far the best computation time and node expansion when partially pre-computed. IDA' finds the same paths as A' and Dijkstra's algorithm but has a notably worse computation time than the other algorithms and should generally be avoided on octile grid maps.