## 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 | Spain |

City | Parador de Cardona |

Period | 17/07/11 → 18/07/11 |