Comparison of Different Abstractions for Pathfinding on Maps
- Yngvi Bjornsson, School of Computer Science, Reykjavik University, Iceland
- Markus Enzenberger, Department of Computing Science, University of Alberta
- Robert Holte, Department of Computing Science, University of Alberta
- Jonathan Schaeffer, Department of Computing Science, University of Alberta
- Peter Yap
Pathfinding on a map is a fundamental problem in many applications, including robotics and computer games. Typically a grid is superimposed over the map where each cell in the grid forms a unique state. A state-space-based search algorithm, such as A* or IDA*, is then used for finding the optimal (shortest) path. In this paper we analyze the search behavior of both A* and IDA* using different grid representations, providing various new insights via analytical and empirical results.
Citation
Y. Bjornsson, M. Enzenberger, R. Holte, J. Schaeffer, P. Yap. "Comparison of Different Abstractions for Pathfinding on Maps". International Joint Conference on Artificial Intelligence (IJCAI), Acapulco, Mexico, pp 1536-1538, January 2003.| Keywords: | |
| Category: | In Conference |
BibTeX
@incollection{Bjornsson+al:IJCAI03,
author = {Yngvi Bjornsson and Markus Enzenberger and Robert Holte and
Jonathan Schaeffer and Peter Yap},
title = {Comparison of Different Abstractions for Pathfinding on Maps},
Pages = {1536-1538},
booktitle = {International Joint Conference on Artificial Intelligence
(IJCAI)},
year = 2003,
}Last Updated: April 24, 2007Submitted by Nelson Loyola
