Path symmetries in undirected uniform-cost grids

Daniel Harabor; Adi Botea; Philip Kilby

Path symmetries in undirected uniform-cost grids

Daniel Harabor, Adi Botea, Philip Kilby

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research

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 language	English
Title of host publication	Proceedings of the Ninth Symposium on Abstraction, Reformulation, and Approximation
Editors	Michael Genesereth, Peter Z. Revesz
Place of Publication	Palo Alto CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	58-61
Number of pages	4
ISBN (Print)	9781577355434
Publication status	Published - 2011
Externally published	Yes
Event	Symposium on Abstraction, Reformulation and Approximation 2011 - Parador de Cardona, Spain Duration: 17 Jul 2011 → 18 Jul 2011 Conference number: 9th

Conference

Conference	Symposium on Abstraction, Reformulation and Approximation 2011
Abbreviated title	SARA 2011
Country/Territory	Spain
City	Parador de Cardona
Period	17/07/11 → 18/07/11

Access to Document

https://www.aaai.org/ocs/index.php/SARA/SARA11/paper/view/4243/4589

Cite this

@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",

note = "Symposium on Abstraction, Reformulation and Approximation 2011, SARA 2011 ; Conference date: 17-07-2011 Through 18-07-2011",

}

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. <https://www.aaai.org/ocs/index.php/SARA/SARA11/paper/view/4243/4589>

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 proceeding › Conference Paper › Research

TY - GEN

T1 - Path symmetries in undirected uniform-cost grids

AU - Harabor, Daniel

AU - Botea, Adi

AU - Kilby, Philip

N1 - Conference code: 9th

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

AN - SCOPUS:84890725643

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

T2 - Symposium on Abstraction, Reformulation and Approximation 2011

Y2 - 17 July 2011 through 18 July 2011

ER -

Path symmetries in undirected uniform-cost grids

Abstract

Conference

Access to Document

Other files and links

Cite this