Path symmetries in undirected uniform-cost grids

Daniel Harabor, Adi Botea, Philip Kilby

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

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 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)
Pages58-61
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

Conference

ConferenceSymposium on Abstraction, Reformulation and Approximation 2011
Abbreviated titleSARA 2011
CountrySpain
CityParador de Cardona
Period17/07/1118/07/11

Cite this

Harabor, D., Botea, A., & Kilby, P. (2011). Path symmetries in undirected uniform-cost grids. In M. Genesereth, & P. Z. Revesz (Eds.), Proceedings of the Ninth Symposium on Abstraction, Reformulation, and Approximation (pp. 58-61). Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI).
Harabor, Daniel ; Botea, Adi ; Kilby, Philip. / Path symmetries in undirected uniform-cost grids. Proceedings of the Ninth Symposium on Abstraction, Reformulation, and Approximation. editor / Michael Genesereth ; Peter Z. Revesz. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2011. pp. 58-61
@inproceedings{fcdbc120e1f94fcf918509a8be968c44,
title = "Path symmetries in undirected uniform-cost grids",
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.",
author = "Daniel Harabor and Adi Botea and Philip Kilby",
year = "2011",
language = "English",
isbn = "9781577355434",
pages = "58--61",
editor = "Michael Genesereth and Revesz, {Peter Z.}",
booktitle = "Proceedings of the Ninth Symposium on Abstraction, Reformulation, and Approximation",
publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
address = "United States of America",

}

Harabor, D, Botea, A & Kilby, P 2011, Path symmetries in undirected uniform-cost grids. in M Genesereth & PZ Revesz (eds), Proceedings of the Ninth Symposium on Abstraction, Reformulation, and Approximation. Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 58-61, Symposium on Abstraction, Reformulation and Approximation 2011, Parador de Cardona, Spain, 17/07/11.

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 proceedingConference PaperResearch

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 -

Harabor D, Botea A, Kilby P. Path symmetries in undirected uniform-cost grids. In Genesereth M, Revesz PZ, editors, Proceedings of the Ninth Symposium on Abstraction, Reformulation, and Approximation. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2011. p. 58-61