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 contribution

SN - 9781577355434

T3 - SARA 2011 - Proceedings of the 9th Symposium on Abstraction, Reformulation, and Approximation

SP - 58

EP - 61

BT - SARA 2011 - Proceedings of the 9th Symposium on Abstraction, Reformulation, and Approximation

T2 - 9th Symposium on Abstraction, Reformulation, and Approximation, SARA 2011

Y2 - 17 July 2011 through 18 July 2011

ER -