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

Aaron Rasheed Rababaah

Article ID: 2504
Vol 2, Issue 3, 2024
DOI: https://doi.org/10.54517/cte2504
Received: 9 June 2024; Accepted: 13 September 2024; Available online: 26 September 2024; Issue release: 30 September 2024


Download PDF

Abstract

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%.


Keywords

A* path-finding algorithm; new modification to A*; mobile robotics; graph algorithms; grid-based path finding


References

Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Aaron Rasheed Rababaah

License URL: https://creativecommons.org/licenses/by/4.0/