対称性を利用したグリッドマップの探索空間削減
Symmetry-Based Search Space Reduction For Grid Maps
無向一様コストグリッドマップ上の最適経路探索を最大38倍高速化するため、空矩形への分解と対称性に基づく探索空間削減手法を提案した論文。
著者: Daniel Harabor, Adi Botea, Philip Kilby
分類: cs.AI, cs.RO
原文アブストラクト
In this paper we explore a symmetry-based search space reduction technique which can speed up optimal pathfinding on undirected uniform-cost grid maps by up to 38 times. Our technique decomposes grid maps into a set of empty rectangles, removing from each rectangle all interior nodes and possibly some from along the perimeter. We then add a series of macro-edges between selected pairs of remaining perimeter nodes to facilitate provably optimal traversal through each rectangle. We also develop a novel online pruning technique to further speed up search. Our algorithm is fast, memory efficient and retains the same optimality and completeness guarantees as searching on an unmodified grid map.
