.png){kind=icon}
Return
Exploiting submodularity to quantify near-optimality in multi-agent coverage problems
.png){kind=icon}
OA
AI
DOI：10.1016/j.automatica.2018.11.020.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider optimal coverage problems for a multi-agent network aiming to maximize a joint event detection probability in an environment with obstacles. The objective function of this problem is non concave and no global optimum is guaranteed by gradient-based algorithms developed to date. In order to obtain a solution provably close to the global optimum, the selection of initial conditions is crucial. We first formulate the initial agent location generation as an additional optimization problem where the objective function is monotone submodular, a class of functions for which the performance obtained through a greedy algorithm solution is guaranteed to be within a provable bound relative to the optimal performance. We then derive two tighter 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 of a gradient-based algorithm for the original optimal coverage problem. Simulation results are included to verify that this approach leads to significantly better performance relative to previously used algorithms. (C) 2018 Elsevier Ltd. All rights reserved.
Keywords:
Optimal coverage
Multi-agent systems
Submodular set function
Greedy algorithm
Gradient method
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
5.9
Papers:
1.2W
Citations:
5.2W
Organization
Cited Papers
ShareSaveDistributed coverage control for concave areas by a heterogeneous Robot-Swarm with visibility sensing constraints.png)
AUTOMATICA
AUTOMATICAIF5.9
PREAI
ShareSaveShareSaveShareSaveShareSaveShareSaveShareSave
View more