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 | Spain |
| City | Parador de Cardona |
| Period | 17/07/11 → 18/07/11 |
Cite this
}
Path symmetries in undirected uniform-cost grids. / Harabor, Daniel; Botea, Adi; Kilby, Philip.
Proceedings of the Ninth Symposium on Abstraction, Reformulation, and Approximation. ed. / Michael Genesereth; Peter Z. Revesz. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2011. p. 58-61.Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research
TY - GEN
T1 - Path symmetries in undirected uniform-cost grids
AU - Harabor, Daniel
AU - Botea, Adi
AU - Kilby, Philip
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84890725643&partnerID=8YFLogxK
M3 - Conference Paper
SN - 9781577355434
SP - 58
EP - 61
BT - Proceedings of the Ninth Symposium on Abstraction, Reformulation, and Approximation
A2 - Genesereth, Michael
A2 - Revesz, Peter Z.
PB - Association for the Advancement of Artificial Intelligence (AAAI)
CY - Palo Alto CA USA
ER -