论文标题
多个机器人的失败 - 弹性覆盖率最大化
Failure-Resilient Coverage Maximization with Multiple Robots
论文作者
论文摘要
使用多个机器人最大化覆盖范围的任务具有多种应用，例如监视，勘探和环境监测。在实际情况下部署此类多机器人系统的主要挑战是确保抵御机器人故障。最近的一项工作介绍了弹性覆盖率最大化（RCM）问题，在该问题中，当机器人受到对抗性攻击或失败的影响时，目标是最大化的覆盖范围。 RCM问题已知是NP-HARD。在本文中，我们提出了针对RCM问题的两种近似算法，即有序的贪婪（org）和本地搜索（LS）算法。两种算法在准确性和运行时间方面都在经验上优于最先进的解决方案。为了证明我们提出的解决方案的有效性，我们从经验上将我们所提出的算法与现有溶液和蛮力最佳算法进行了比较。我们还对持续监测问题进行了案例研究，以显示我们在实际环境中提出的算法的适用性。
The task of maximizing coverage using multiple robots has several applications such as surveillance, exploration, and environmental monitoring. A major challenge of deploying such multi-robot systems in a practical scenario is to ensure resilience against robot failures. A recent work introduced the Resilient Coverage Maximization (RCM) problem where the goal is to maximize a submodular coverage utility when the robots are subject to adversarial attacks or failures. The RCM problem is known to be NP-hard. In this paper, we propose two approximation algorithms for the RCM problem, namely, the Ordered Greedy (OrG) and the Local Search (LS) algorithm. Both algorithms empirically outperform the state-of-the-art solution in terms of accuracy and running time. To demonstrate the effectiveness of our proposed solution, we empirically compare our proposed algorithms with the existing solution and a brute force optimal algorithm. We also perform a case study on the persistent monitoring problem to show the applicability of our proposed algorithms in a practical setting.
