ML Anthology

Comparison of Different Grid Abstractions for Pathfinding on Maps

Yngvi Björnsson, Markus Enzenberger, Robert Holte, Jonathan Schaeffer, Peter Yap
IJCAI 2003 pp. 1511-1512
/ijcai/2003/bjornsson2003ijcai-comparison/

Abstract

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.

PDF Semantic Scholar

Cite

Text

Björnsson et al. "Comparison of Different Grid Abstractions for Pathfinding on Maps." International Joint Conference on Artificial Intelligence, 2003.

Markdown

[Björnsson et al. "Comparison of Different Grid Abstractions for Pathfinding on Maps." International Joint Conference on Artificial Intelligence, 2003.](https://mlanthology.org/ijcai/2003/bjornsson2003ijcai-comparison/)

BibTeX

@inproceedings{bjornsson2003ijcai-comparison,
  title     = {{Comparison of Different Grid Abstractions for Pathfinding on Maps}},
  author    = {Björnsson, Yngvi and Enzenberger, Markus and Holte, Robert and Schaeffer, Jonathan and Yap, Peter},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2003},
  pages     = {1511-1512},
  url       = {https://mlanthology.org/ijcai/2003/bjornsson2003ijcai-comparison/}
}