非凸環境における旋回最小カバレッジ計画のための最適分割法
Optimal Partitioning of Non-Convex Environments for Minimum Turn Coverage Planning
屋内環境を軸平行な矩形帯に線形計画で最適分割し、旋回回数を最小化するカバレッジ経路を多項式時間で計画する手法を提案した。
著者: Megnath Ramesh, Frank Imeson, Baris Fidan, Stephen L. Smith
分類: cs.RO, cs.SY, eess.SY
原文アブストラクト
In this paper, we tackle the problem of planning an optimal coverage path for a robot operating indoors. Many existing approaches attempt to discourage turns in the path by covering the environment along the least number of coverage lines, i.e., straight-line paths. This is because turning not only slows down the robot but also negatively affects the quality of coverage, e.g., tools like cameras and cleaning attachments commonly have poor performance around turns. The problem of minimizing coverage lines however is typically solved using heuristics that do not guarantee optimality. In this work, we propose a turn-minimizing coverage planning method that computes the optimal number of axis-parallel (horizontal/vertical) coverage lines for the environment in polynomial time. We do this by formulating a linear program (LP) that optimally partitions the environment into axis-parallel ranks (non-intersecting rectangles of width equal to the tool width). We then generate coverage paths for a set of real-world indoor environments and compare the results with state-of-the-art coverage approaches.
