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 -