Failure-Resilient Coverage Maximization with Multiple Robots
This work addresses resilience in multi-robot systems for applications like surveillance and monitoring, but it is incremental as it builds on prior work on the Resilient Coverage Maximization problem.
The paper tackles the problem of maximizing coverage with multiple robots under adversarial failures, proposing two approximation algorithms (Ordered Greedy and Local Search) that empirically outperform the state-of-the-art in accuracy and running time.
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.