A multiscale analysis of multi-agent coverage control algorithms
(2022) In Automatica 145.- Abstract
This paper presents a theoretical framework for the design and analysis of gradient descent-based algorithms for coverage control tasks involving robot swarms. We adopt a multiscale approach to analysis and design to ensure consistency of the algorithms in the large-scale limit. First, we represent the macroscopic configuration of the swarm as a probability measure and formulate the macroscopic coverage task as the minimization of a convex objective function over probability measures. We then construct a macroscopic dynamics for swarm coverage, which takes the form of a proximal descent scheme in the L2-Wasserstein space. Our analysis exploits the generalized geodesic convexity of the coverage objective function, proving... (More)
This paper presents a theoretical framework for the design and analysis of gradient descent-based algorithms for coverage control tasks involving robot swarms. We adopt a multiscale approach to analysis and design to ensure consistency of the algorithms in the large-scale limit. First, we represent the macroscopic configuration of the swarm as a probability measure and formulate the macroscopic coverage task as the minimization of a convex objective function over probability measures. We then construct a macroscopic dynamics for swarm coverage, which takes the form of a proximal descent scheme in the L2-Wasserstein space. Our analysis exploits the generalized geodesic convexity of the coverage objective function, proving convergence in the L2-Wasserstein sense to the target probability measure. We then obtain a consistent gradient descent algorithm in the Euclidean space that is implementable by a finite collection of agents, via a “variational” discretization of the macroscopic coverage objective function. We establish the convergence properties of the gradient descent and its behavior in the continuous-time and large-scale limits. Furthermore, we establish a connection with well-known Lloyd-based algorithms, seen as a particular class of algorithms within our framework, and demonstrate our results via numerical experiments.
(Less)
- author
- Krishnan, Vishaal LU and Martínez, Sonia
- organization
- publishing date
- 2022-11
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Coverage control, Lloyd's algorithm, Multi-agent systems, Multiscale analysis, Proximal descent
- in
- Automatica
- volume
- 145
- article number
- 110516
- publisher
- Pergamon Press Ltd.
- external identifiers
-
- scopus:85135815851
- ISSN
- 0005-1098
- DOI
- 10.1016/j.automatica.2022.110516
- language
- English
- LU publication?
- yes
- id
- 19d79890-014f-48d9-aa6f-a12e5cad6fa3
- date added to LUP
- 2022-09-09 14:21:37
- date last changed
- 2024-05-16 02:40:31
@article{19d79890-014f-48d9-aa6f-a12e5cad6fa3,
abstract = {{<p>This paper presents a theoretical framework for the design and analysis of gradient descent-based algorithms for coverage control tasks involving robot swarms. We adopt a multiscale approach to analysis and design to ensure consistency of the algorithms in the large-scale limit. First, we represent the macroscopic configuration of the swarm as a probability measure and formulate the macroscopic coverage task as the minimization of a convex objective function over probability measures. We then construct a macroscopic dynamics for swarm coverage, which takes the form of a proximal descent scheme in the L<sup>2</sup>-Wasserstein space. Our analysis exploits the generalized geodesic convexity of the coverage objective function, proving convergence in the L<sup>2</sup>-Wasserstein sense to the target probability measure. We then obtain a consistent gradient descent algorithm in the Euclidean space that is implementable by a finite collection of agents, via a “variational” discretization of the macroscopic coverage objective function. We establish the convergence properties of the gradient descent and its behavior in the continuous-time and large-scale limits. Furthermore, we establish a connection with well-known Lloyd-based algorithms, seen as a particular class of algorithms within our framework, and demonstrate our results via numerical experiments.</p>}},
author = {{Krishnan, Vishaal and Martínez, Sonia}},
issn = {{0005-1098}},
keywords = {{Coverage control; Lloyd's algorithm; Multi-agent systems; Multiscale analysis; Proximal descent}},
language = {{eng}},
publisher = {{Pergamon Press Ltd.}},
series = {{Automatica}},
title = {{A multiscale analysis of multi-agent coverage control algorithms}},
url = {{http://dx.doi.org/10.1016/j.automatica.2022.110516}},
doi = {{10.1016/j.automatica.2022.110516}},
volume = {{145}},
year = {{2022}},
}