# Failure-Resilient Coverage Maximization with Multiple Robots

arXiv: https://arxiv.org/abs/2007.02204 · HTML: https://mlsanity.com/paper/2007.02204/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2020.

## Built on by (most cited first, 3 of 3)

- [Beyond Robustness: A Taxonomy of Approaches towards Resilient Multi-Robot Systems](https://mlsanity.com/paper/2109.12343/) (2021)
- [The Holy Grail of Multi-Robot Planning: Learning to Generate Online-Scalable Solutions from Offline-Optimal Experts](https://mlsanity.com/paper/2107.12254/) (2021)
- [Reinforcement Learning for Game-Theoretic Resource Allocation on Graphs](https://mlsanity.com/paper/2505.06319/) (2025)

## Abstract (arXiv)

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.