Distributed Coverage with Mobile Robots on a Graph: Locational Optimization and Equal-Mass Partitioning

Abstract

This paper presents decentralized algorithms for coverage with mobile robots on a graph. Coverage is an important capability of multi-robot systems engaged in a number of different applications, including placement for environmental modeling, deployment for maximal quality surveillance, and even coordinated construction. We use distributed vertex substitution for locational optimization and equal mass partitioning, and the controllers minimize the corresponding cost functions. We prove that the proposed controller with two-hop communication guarantees convergence to the locally optimal configuration. We evaluate the algorithms in simulations and also using four mobile robots.

Keywords: Multi-robot systems, Modular robots, Distributed algorithms, Path planning on discrete spaces.