Title: A Submodularity-Based Approach for Multi-Agent Optimal Coverage Problems,
Abstract: 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.