A new modification to the A* path-finding algorithm to improve its space and time performance

<p>We propose a new modification to the A* algorithm named AA* that significantly improves space and time complexities. In AA*’s forward pass, the node sets (open and closed) are not used, and only the local node neighborhood is saved to take the next move decision. AA* needs a backward pass to bridge and correct gaps and bad decisions made in the forward pass. The work of the backward pass is far less than that of the forward pass, as most of the task has been done. It is shown via empirical experimental work that our proposed AA* algorithm is superior to the classical A* algorithm in the typical three metrics: running time, number of probed nodes, and length of path. Furthermore, our experimental work showed that AA* is suboptimal in terms of length of path compared to the original Dijkstra’s algorithm with an accuracy of 96.95%.</p>