DISCRETE PARTITIONING AND COVERAGE CONTROLWITH GOSSIP COMMUNICATIONJoseph W. DurhamRuggero CarliDepartment of Mechanical EngineeringUniversity of CaliforniaSanta Barbara, California, 93106(joey, carlirug)@engineering.ucsb.eduPaolo FrascaIstituto per le Applicazioni del CalcoloConsiglio Nazionale delle RicercheRome, [email protected] BulloDepartment of Mechanical EngineeringUniversity of CaliforniaSanta Barbara, California, [email protected] this paper we propose distributed algorithms to automat-ically deploy a group of robotic agents and provide coverage ofa discretized environment represented by a graph. We presenta discrete coverage algorithm which converges to a centroidalVoronoi partition while requiring only pairwise “gossip” com-munication between the agents. Our theoretical analysis is basedon a dynamical system on partitions of the graph’s vertices. Wealso establish bounds on the computational requirements of thealgorithm and demonstrate its functionality with simulations.1 INTRODUCTIONThis paper deals with distributed partitioning and coveragecontrol problems for a network of robotic agents in a potentiallynon-convex environment. The distributed partitioning problemfor robotic networks consists of designing control and communi-cation laws to divide an environment into territories. Typically,partitioning is done so as to optimize a cost function that mea-sures the quality of the partitions. Coverage control algorithmsare usually designed in a similar way, with an additional crite-rion of optimizing the placement of the agents. In this paperwe describe a partitioning and coverage control algorithm whichoptimizes the configuration of a group of agents in a discrete en-vironment represented by a graph. Optimality is defined withreference to a cost function which depends on the locations ofthe agents and geodesic distances in the graph. As with all mul-tiagent coordination applications, the challenge comes from re-ducing the communication requirements: the proposed algorithmonly requires pairwise “gossip” communication.A broad discussion of partitioning and coverage control ispresented in [1] which builds on the classic work of Lloyd [2]on algorithms for optimal quantizer design through “centeringand partitioning.” The relationship between discrete and contin-uous coverage control laws based on Euclidean distances is stud-ied in [3]. Coverage control and partitioning of discrete sets arealso related to the literature on the facility location or k-centerproblem [4]. Coverage control algorithms for non-convex envi-ronments are discussed in [5–7] while equitable partitioning isstudied in [8]. In [9] the authors have showed how a group ofrobotic agents can optimize the partition of a given environmentusing pairwise “gossip” communication: only one pair of regionsis updated at each step of the algorithm. In that work the envi-ronment is assumed to be a convex bounded subset of Rd. Thisassumption is not suitable for implementation on physical robotswhich inherently sense and memorize a quantized environment.There are three main contributions of this paper. First, weextend the results for gossip coverage from [9] to perform cover-age of a connected graph using geodesic distances. In the usagewe envision, the connected graph represents a discretization ofan environment, allowing physical robots to cover complex non-convex environments with holes. We discuss important proper-ties of this setup, namely that the centroid of a robot’s regionalways belongs to the region (which is a subset of the vertices),and moreover each robot’s region remains connected during theevolution of the algorithm. Second, we prove that, under suitableassumptions on the sequence of updating pairs, the discrete gos-sip coverage algorithm converges in finite time to a single cen-troidal Voronoi partition. This result, stronger than that in [9],is a consequence of the discrete nature of the problem. Third,we discuss the implementation of the core computations of thealgorithm and provide bounds on their computational complex-ity. We show that the computations of the algorithm scale wellwith the size of the environment and the number of robots used,meaning the algorithm is truly distributed. Combined with theextension to a discrete environment, this efficient computationenables the algorithm to be implemented on a large group of realrobots.This paper is organized as follows. In Section 2 we formallydescribe the discrete coverage control problem and provide def-initions of discrete Voronoi partitions. We present the discretegossip coverage algorithm in Section 3 and discuss some of itsproperties. Section 4 contains the main convergence results. InSection 5 we discuss bounds on the computational complexityof the algorithm. Simulation results are shown in Section 6 andsome conclusions are given in Section 7.In our notation, R≥0denotes the set of non-negative realnumbers and Z≥0the set of non-negative integers. Given a set X,|X|denotes the number of elements in X. Given sets X,Y, theirdifference is X \Y = {x ∈ X | x /∈ Y}. A set-valued map, denotedby T : X ⇉ Y, associates to an element of X a subset of Y.2 PROBLEM FORMULATIONWe are given a group of robotic agents with limited sensingand communication capabilities, and a discretized environment.We want to apportion the environment into smaller regions, eachassigned to one of the agents. Our approach is to iteratively up-date the partition in such a way as to minimize a cost functionalwhich depends on the current partition and the positions of theagents.Let the finite set Q be the discretized environment. Weassume that the elements of Q, which can be thought as loca-tions, are connected by weighted edges. In other words, we letG = (Q,E,w) be an (undirected) weighted graph with edge setE ⊂ Q× Q and weight map w : E → R>0; we let we> 0 be theweight of edge e. We assume that G is connected and think ofthe edge weights as distances between locations.In any weighted graph G there is a standard notion of dis-tance between nodes defined as follows. A path in G is an or-dered sequence of nodes such that any pair of consecutive nodesin the sequence is an edge of G. The weight of a path is the sumof the weights of all the edges in the path. Given two verticesh and k in G, the distance between h an k, denoted by dG(h,k),is the smallest weight of any path from h to k, or +∞ if there isno path from