Optimal Pathfinding on Weighted Grid Maps
DOI:
https://doi.org/10.1609/aaai.v37i10.26458Keywords:
SO: Heuristic Search, ROB: Motion and Path Planning, PRS: RoutingAbstract
In many computer games up to hundreds of agents navigate in real-time across a dynamically changing weighted grid map. Pathfinding in these situations is challenging because the grids are large, traversal costs are not uniform, and because each shortest path has many symmetric permutations, all of which must be considered by an optimal online search. In this work we introduce Weighted Jump Point Search (JPSW), a new type of pathfinding algorithm which breaks weighted grid symmetries by introducing a tiebreaking policy that allows us to apply effective pruning rules in symmetric regions. We show that these pruning rules preserve at least one optimal path to every grid cell and that their application can yield large performance improvements for optimal pathfinding. We give a complete theoretical description of the new algorithm, including pseudo-code. We also conduct a wide-ranging experimental evaluation, including data from real games. Results indicate JPSW is up to orders of magnitude faster than the nearest baseline, online search using A*.Downloads
Published
2023-06-26
How to Cite
Carlson, M., Moghadam, S. K., Harabor, D. D., Stuckey, P. J., & Ebrahimi, M. (2023). Optimal Pathfinding on Weighted Grid Maps. Proceedings of the AAAI Conference on Artificial Intelligence, 37(10), 12373-12380. https://doi.org/10.1609/aaai.v37i10.26458
Issue
Section
AAAI Technical Track on Search and Optimization