部分モジュラー集合被覆を用いたロボット被覆計画のための環境近似分解
Approximate Environment Decompositions for Robot Coverage Planning using Submodular Set Cover
2次元環境を重複可能な矩形セクターに分解し、部分モジュラー集合被覆問題として定式化することで、被覆計画のセクター数を近似保証付きで削減する手法を提案した。
著者: Megnath Ramesh, Frank Imeson, Baris Fidan, Stephen L. Smith
分類: cs.RO
原文アブストラクト
In this paper, we investigate the problem of decomposing 2D environments for robot coverage planning. Coverage path planning (CPP) involves computing a cost-minimizing path for a robot equipped with a coverage or sensing tool so that the tool visits all points in the environment. CPP is an NP-Hard problem, so existing approaches simplify the problem by decomposing the environment into the minimum number of sectors. Sectors are sub-regions of the environment that can each be covered using a lawnmower path (i.e., along parallel straight-line paths) oriented at an angle. However, traditional methods either limit the coverage orientations to be axis-parallel (horizontal/vertical) or provide no guarantees on the number of sectors in the decomposition. We introduce an approach to decompose the environment into possibly overlapping rectangular sectors. We provide an approximation guarantee on the number of sectors computed using our approach for a given environment. We do this by leveraging the submodular property of the sector coverage function, which enables us to formulate the decomposition problem as a submodular set cover (SSC) problem with well-known approximation guarantees for the greedy algorithm. Our approach improves upon existing coverage planning methods, as demonstrated through an evaluation using maps of complex real-world environments.
