The Analysis of Efficiency Dependence of the Shortest Path Finding Algorithms A* and HPA* on the Grid Size
Abstract
Many pathfinding problems in real-world applications require real-time computation of the shortest path between two points in a grid-based environment. It is not a trivial task. While some shortest path finding algorithms may perform admissibly in one condition, they may prove inadmissible in other conditions. HPA* pathfinding algorithm is faster and more memory efficient than the A*algorithm in relatively large two- dimensional grids, but this advantage may not apply to very small or very large grids. The paper deals with the efficiency of A* and HPA*in two-dimensional grids of different sizes. For the sake of completeness of the analysis, HPA* efficiency is measured taking into consideration the number of hierarchy levels and different cluster sizes. Both algorithms have been implemented and tests conducted. Experimental evidence is proposed to demonstrate the algorithm efficiency in various conditions.
Keywords: |
A*; HPA*; shortest path problems
|
Full Text: |
References
Millington and J. Funge, Artificial Intelligence for Games, Second Edition. San Francisco: Morgan Kaufmann Publishers Inc., 2009.
R. Siegwart and I. R. Nourbakhsh, Introduction to Autonomous Mobile Robots. London: The MIT Press, 2004.
R. C. Holte, M. B. Perez, R. M. Zimmer, A. J. MacDonald, Hierarchical A*: Searching Abstraction Hierarchies Efficiently: AAAI 96 Proceedings of the thirteenth national conference on Artificial intelligence, vol. 1, pp. 530-535, 1996.
N. Sturtevant and M. Buro, Partial Pathfinding Using Map Abstraction and Refinement: AAAI 05 Proceedings of the 20th national conference on Artificial intelligence, vol. 3, pp. 1392-1397, 2005.
M. R. Jansen, M. Buro. HPA* Enhancements: Proceedings of the Third Artificial Intelligence and Interactive Digital Entertainment Conference, June 6-8, 2007, Stanford, California, USA.
Y. Bjornsson and K. Halldorsson. Improved Heuristics for Optimal Path-finding on Game Maps: Proceedings of the Second Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE'06), Marina Del Ray, California, USA, June 20-23, pp. 9–14, 2006.
Botea, M. Müller, J. Schaeffer, “Near Optimal Hierarchical Path-Finding,” in Journal of Game Development, vol. 1, pp. 7-28, 2004.
Cui and H. Shi, “A*-based Pathfinding in Modern Computer Games,” in International Journal of Computer Science and Network Security, vol. 11, pp. 125-130, 2011.
E. W. Dijkstra., “A note on two problems in connexion with graphs,” in Numerische Mathematik, vol. 1, pp. 269-271, 1959.
P. E. Hart, N. J. Nilsson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” in IEEE Transactions of Systems Science and Cybernetics, vol. 4, pp. 100-107, 1968.
R. C. Holte, T. Mkadmi, R. M. Zimmer, A. J. MacDonald, “Speeding up problem solving by abstraction: a graph oriented approach,” in Artificial Intelligence, vol. 85, pp. 321–361, 1996.
Refbacks
- There are currently no refbacks.
Copyright (c) 2012 Imants Zarembo, Oleg Uzhga-Rebrov
This work is licensed under a Creative Commons Attribution 4.0 International License.