AAAI Publications, Ninth Symposium of Abstraction, Reformulation, and Approximation

Font Size: 
Path Symmetries in Undirected Uniform-Cost Grids
Daniel Damir Harabor, Adi Botea, Philip Kilby

Last modified: 2011-12-14


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.

Full Text: PDF