Multiagent coverage algorithms with gossip communication: Control systems on the space of partitions

Abstract

Deployment, coverage and partitioning are fundamental tasks for robotic networks. Recently proposed algorithms achieve these tasks under a critical assumption: information is exchanged synchronously among all agents and long-range communication is possibly required. This work proposes novel deployment and partitioning algorithms that require only asynchronous pairwise (so-called gossip) communication. Which robot pair communicates at any given time may be selected deterministically or randomly. A key novel idea is the description of the coverage control problem as a control system on the space of partitions - in other words, we study the evolution of the regions assigned to each agent, rather than the evolution of the agents' positions. The novel gossip algorithms are shown to converge to multicenter Voronoi partitions through various results of independent interest: we establish the compactness of the space of partitions, the continuity of certain geometric maps (e.g., the Voronoi and the centroid maps), and two convergence theorems for switching dynamical systems on metric spaces.