Comparison of Different Grid Abstractions for Pathfinding on Maps
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1511-1511.
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.
Yngvi Björnsson, Markus Enzenberger, Robert C. Holte, Jonathan Schaeffer, and Peter Yap. 2003. Comparison of Different Grid Abstractions for Pathfinding on Maps. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03. IJCAI, 1511–1511. https://ijcai.org/proceedings/2003/254
Björnsson, Y., Enzenberger, M., Holte, R. C., Schaeffer, J., & Yap, P. (2003). Comparison of Different Grid Abstractions for Pathfinding on Maps. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 (pp. 1511–1511). IJCAI. https://ijcai.org/proceedings/2003/254
@inproceedings{ijcai2003p254,
title = {Comparison of Different Grid Abstractions for Pathfinding on Maps},
author = {Björnsson, Yngvi and Enzenberger, Markus and Holte, Robert C. and Schaeffer, Jonathan and Yap, Peter},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {1511--1511},
year = {2003},
url = {https://ijcai.org/proceedings/2003/254},
}
TY - CPAPER TI - Comparison of Different Grid Abstractions for Pathfinding on Maps AU - Björnsson, Yngvi AU - Enzenberger, Markus AU - Holte, Robert C. AU - Schaeffer, Jonathan AU - Yap, Peter T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 1511 EP - 1511 UR - https://ijcai.org/proceedings/2003/254 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
