Path symmetries in undirected uniform-cost grids

Daniel Harabor, Adi Botea, Philip Kilby

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

7 Citations (Scopus)


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 languageEnglish
Title of host publicationProceedings of the Ninth Symposium on Abstraction, Reformulation, and Approximation
EditorsMichael Genesereth, Peter Z. Revesz
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages4
ISBN (Print)9781577355434
Publication statusPublished - 2011
Externally publishedYes
EventSymposium on Abstraction, Reformulation and Approximation 2011 - Parador de Cardona, Spain
Duration: 17 Jul 201118 Jul 2011
Conference number: 9th


ConferenceSymposium on Abstraction, Reformulation and Approximation 2011
Abbreviated titleSARA 2011
CityParador de Cardona

Cite this