论文标题
在非凸环境中分布式多机器人覆盖的近似算法
Approximation Algorithms for Distributed Multi-Robot Coverage in Non-Convex Environments
论文作者
论文摘要
在本文中，我们在公制图和非凸线连续环境中使用多个机器人重新审视分布式覆盖范围控制问题。传统上，为此问题提供的解决方案融合到本地最佳解决方案，而无法保证解决方案的质量。我们考虑了亚添加感应功能，该功能捕获了感应事件需要机器人访问事件位置的场景。对于这些感应功能，我们为分布式覆盖范围问题提供了第一个常数因子近似算法。近似结果需要在现有覆盖算法中的传统通信范围的两倍。但是，我们通过广泛的模拟结果表明，即使在常规的通信范围内，提出的近似算法的表现都优于凸，非凸连续和离散环境中的几种现有算法。此外，提出的算法与溶液质量中最新的集中算法相匹配。
In this paper, we revisit the distributed coverage control problem with multiple robots on both metric graphs and in non-convex continuous environments. Traditionally, the solutions provided for this problem converge to a locally optimal solution with no guarantees on the quality of the solution. We consider sub-additive sensing functions, which capture the scenarios where sensing an event requires the robot to visit the event location. For these sensing functions, we provide the first constant factor approximation algorithms for the distributed coverage problem. The approximation results require twice the conventional communication range in the existing coverage algorithms. However, we show through extensive simulation results that the proposed approximation algorithms outperform several existing algorithms in convex, non-convex continuous, and discrete environments even with the conventional communication ranges. Moreover, the proposed algorithms match the state-of-the-art centralized algorithms in the solution quality.
