Abstract
We explore a symmetry-based reformulation technique which can speed up optimal pathfinding on undirected uniform-cost grid maps by over 30 times. Our offline approach decomposes grid maps into a set of empty rectangles, removing from each all interior nodes and possibly some from along the perimeter. We then add macro-edges between selected pairs of remaining perimeter nodes to facilitate provably optimal traversal through each rectangle. To further speed up search, we also develop a novel online pruning technique. Our algorithm is fast, memory efficient and retains both optimality and completeness during search.
Original language | English |
---|---|
Title of host publication | Proceedings of the Ninth Symposium on Abstraction, Reformulation, and Approximation |
Editors | Michael Genesereth, Peter Z. Revesz |
Place of Publication | Palo Alto CA USA |
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Pages | 58-61 |
Number of pages | 4 |
ISBN (Print) | 9781577355434 |
Publication status | Published - 2011 |
Externally published | Yes |
Event | Symposium on Abstraction, Reformulation and Approximation 2011 - Parador de Cardona, Spain Duration: 17 Jul 2011 → 18 Jul 2011 Conference number: 9th |
Conference
Conference | Symposium on Abstraction, Reformulation and Approximation 2011 |
---|---|
Abbreviated title | SARA 2011 |
Country/Territory | Spain |
City | Parador de Cardona |
Period | 17/07/11 → 18/07/11 |