用子模集覆盖方法分解环境，保证机器人覆盖率的最优分区数。
Approximate Environment Decompositions for Robot Coverage Planning using Submodular Set Cover
- 将环境分解为可能重叠的矩形区域，用子模性质优化分区数量。
- 算法提供分区数量的近似保证，比传统方法更高效。
- 适合复杂真实环境的机器人路径规划，尤其关注覆盖效率。
本文研究二维环境中机器人的覆盖规划问题。覆盖路径规划（CPP）旨在为配备覆盖或传感工具的机器人计算一条成本最低的路径，使其覆盖环境内所有点。由于CPP是NP难问题，现有方法通常通过将环境分解为最少数量的扇区来简化问题。扇区是可使用割草机式路径（即平行直线路径）覆盖的子区域，且有特定朝向。然而，传统方法要么限制扇区朝向为轴对齐（水平/垂直），要么无法保证分解后的扇区数量。本文提出一种方法，将环境分解为可能重叠的矩形扇区，并基于扇区覆盖函数的子模性，将分解问题建模为子模集覆盖（SSC）问题，从而为给定环境提供扇区数量的近似保证。通过在复杂真实环境地图上的评估，验证了该方法优于现有覆盖规划方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。