# A Submodularity-Based Approach for Multi-Agent Optimal Coverage Problems

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2017.

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

- [Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis](https://mlsanity.com/paper/2401.10383/) (2024)
- [Scalable Submodular Policy Optimization via Pruned Submodularity Graph](https://mlsanity.com/paper/2507.13834/) (2025)

## Abstract (arXiv)

We consider the optimal coverage problem where a multi-agent network is deployed in an environment with obstacles to maximize a joint event detection probability. The objective function of this problem is non-convex and no global optimum is guaranteed by gradient-based algorithms developed to date. We first show that the objective function is monotone submodular, a class of functions for which a simple greedy algorithm is known to be within 0.63 of the optimal solution. We then derive two tighter lower bounds by exploiting the curvature information (total curvature and elemental curvature) of the objective function. We further show that the tightness of these lower bounds is complementary with respect to the sensing capabilities of the agents. The greedy algorithm solution can be subsequently used as an initial point for a gradient-based algorithm to obtain solutions even closer to the global optimum. Simulation results show that this approach leads to significantly better performance relative to previously used algorithms.