arXiv:1011.1939v2  [cs.RO]  26 Sep 2011
Discrete Partitioning and Coverage Control
for Gossiping Robots
Joseph W. Durham
Ruggero Carli
Paolo Frasca
Francesco Bullo
Abstract—We propose distributed algorithms to automatically
deploy a team of mobile robots to partition and provide coverage
of a non-convex environment. To handle arbitrary non-convex
environments, we represent them as graphs. Our partitioning and
coverage algorithm requires only short-range, unreliable pairwise
“gossip” communication. The algorithm has two components: (1)
a motion protocol to ensure that neighboring robots communicate
at least sporadically, and (2) a pairwise partitioning rule to update
territory ownership when two robots communicate. By studying
an appropriate dynamical system on the space of partitions of the
graph vertices, we prove that territory ownership converges to
a pairwise-optimal partition in finite time. This new equilibrium
set represents improved performance over common Lloyd-type
algorithms. Additionally, we detail how our algorithm scales well
for large teams in large environments and how the computation
can run in anytime with limited resources. Finally, we report on
large-scale simulations in complex environments and hardware
experiments using the Player/Stage robot control system.
I. INTRODUCTION
Coordinated networks of mobile robots are already in use
for environmental monitoring and warehouse logistics. In
the near future, autonomous robotic teams will revolutionize
transportation of passengers and goods, search and rescue op-
erations, and other applications. These tasks share a common
feature: the robots are asked to provide service over a space.
One question which arises is: when a group of robots is waiting
for a task request to come in, how can they best position
themselves to be ready to respond?
The distributed environment partitioning problem for robotic
networks consists of designing individual control and com-
munication laws such that the team divides a large space into
regions. Typically, partitioning is done so as to optimize a cost
function which measures the quality of service provided over
all of the regions. Coverage control additionally optimizes the
positioning of robots inside a region as shown in Fig. 1.
This paper describes a distributed partitioning and coverage
control algorithm for a network of robots to minimize the
This work was supported in part by ARO MURI Award W911NF-05-1-
0219, NSF grants IIS-0904501 and CPS-1035917, and MIUR grant PRIN-
20087W5P2. Preliminary and incomplete versions of this work appeared in the
Proceedings of the 2009 ASME Dynamic Systems and Control Conference,
Hollywood, California, USA, and in the Proceedings of the 2010 IEEE
Conference on Decision and Control, Atlanta, Georgia, USA.
Joseph W. Durham and Francesco Bullo are with the Department of
Mechanical Engineering, University of California, Santa Barbara, CA, 93106
(joey, bullo)@engineering.ucsb.edu
Ruggero
Carli
is
with
the
Department
of
Information
Engineer-
ing,
University
of Padova,
Via
Gradenigo
6/a,
35131
Padova,
Italy
carlirug@dei.unipd.it
Paolo
Frasca
is
with
the
Dipartimento
di
Matematica,
Politec-
nico
di
Torino,
corso
Duca
degli
Abruzzi
24,
10129
Torino,
Italy
paolo.frasca@polito.it
Fig. 1.
Example of a team of robots providing efficient coverage of a non-
convex environment, as measured by an appropriate multicenter cost function.
expected distance between the closest robot and spatially
distributed events which will appear at discrete points in a non-
convex environment. Optimality is defined with reference to a
relevant “multicenter” cost function. As with all multirobot co-
ordination applications, the challenge comes from reducing the
communication requirements: the proposed algorithm requires
only short-range “gossip” communication, i.e., asynchronous
and unreliable communication between nearby robots.
Literature Review
Territory partitioning and coverage control have applica-
tions in many fields. In cyber-physical systems, applications
include automated environmental monitoring [1], fetching and
delivery [2], construction [3], and other vehicle routing scenar-
ios [4]. More generally, coverage of discrete sets is also closely
related to the literature on data clustering and k-means [5],
as well as the facility location or k-center problem [6].
Partitioning of graphs is its own field of research, see [7] for a
survey. Territory partitioning through local interactions is also
studied for animal groups, see for example [8].
A broad discussion of algorithms for partitioning and
coverage control in robotic networks is presented in [9]
which builds on the classic work of Lloyd [10] on optimal
quantizer selection through “centering and partitioning.” The
Lloyd approach was first adapted for distributed coverage
control in [11]. Since this beginning, similar algorithms have
been applied to non-convex environments [12], [13], unknown
density functions [14], [15], equitable partitioning [16], and
construction of truss-like objects [3]. There are also multi-
agent partitioning algorithms built on market principles or
1
2
auctions, see [17] for a survey.
While Lloyd iterative optimization algorithms are popular
and work well in simulation, they require synchronous and
reliable communication among neighboring robots. As robots
with adjacent regions may be arbitrarily far apart, these
communication requirements are burdensome and unrealistic
for deployed robotic networks. In response to this issue, in [18]
the authors have shown how a group of robotic agents can
optimize the partition of a convex bounded set using a Lloyd
algorithm with gossip communication. A Lloyd algorithm with
gossip communication has also been applied to optimizing
partitions of non-convex environments in [19], the key idea
being to transform the coverage problem in Euclidean space
into a coverage problem on a graph with geodesic distances.
Distributed Lloyd methods are built around separate parti-
tioning and centering steps, and they are attractive because
there are known ways to characterize their equilibrium sets
(the so-called centroidal Voronoi partitions) and prove con-
vergence. Unfortunately, even for very simple environments
(both continuous and discrete) the set of centroidal Voronoi
partitions may contain several sub-optimal configurations. We
are thus interested in studying (discrete) gossip coverage
algorithms for two reasons: (1) they apply to more realistic
robot network models featuring very limited communication in
large non-convex environments, and (2) they are more flexible
than typical Lloyd algorithms meaning they can avoid poor
suboptimal configurations and improve performance.
Statement of Contributions
There are three main contributions in this paper. First,
we present a discrete partitioning and coverage optimization
algorithm for mobile robots with unreliable, asynchronous, and
short-range communication. Our algorithm has two compo-
nents: a motion protocol which drives the robots to meet their
neighbors, and a pairwise partitioning rule to update territories
when two robots meet. The partitioning rule optimizes cover-
age of a set of points connected by edges to form a graph. The
flexibility of graphs allows the algorithm to operate in non-
convex, non-polygonal environments with holes. Our graph
partition optimization approach can also be applied to non-
planar problems, existing transportation or logistics networks,
or more general data sets.
Second, we provide an analysis of both the convergence
properties and computational requirements of the algorithm.
By studying a dynamical system of partitions of the graph’s
vertices, we prove that almost surely the algorithm converges
to a pairwise-optimal partition in finite time. The set of
pairwise-optimal partitions is shown to be a proper subset
of the well-studied set of centroidal Voronoi partitions. We
further describe how our pairwise partitioning rule can be
implemented to run in anytime and how the computational
requirements of the algorithm can scale up for large domains
and large teams.
Third, we detail experimental results from our implementa-
tion of the algorithm in the Player/Stage robot control system.
We present a simulation of 30 robots providing coverage of a
portion of a college campus to demonstrate that our algorithm
can handle large robot teams, and a hardware-in-the-loop
experiment conducted in our lab which incorporates sensor
noise and uncertainty in robot position. Through numerical
analysis we also show how our new approach to partitioning
represents a significant performance improvement over both
common Lloyd-type methods and the recent results in [18].
The present work differs from the gossip Lloyd method [18]
in three respects. First, while [18] focuses on territory par-
titioning in a convex continuous domain, here we operate
on a graph which allows our approach to consider geodesic
distances, work in non-convex environments, and maintain
connected territories. Second, instead of a pairwise Lloyd-like
update, we use an iterative optimal two-partitioning approach
which yields better final solutions. Third, we also present a
motion protocol to produce the sporadic pairwise commu-
nications required for our gossip algorithm and characterize
the computational complexity of our proposal. Preliminary
versions of this paper appeared in [19] and [20]. Compared to
these, the new content here includes: (1) a motion protocol;
(2) a simplified and improved pairwise partitioning rule; (3)
proofs of the convergence results; and (4) a description of our
implementation and a hardware-in-the-loop experiment.
Paper Structure and Notation
In Section II we review and adapt coverage and geometric
concepts (e.g., centroids, Voronoi partitions) to a discrete envi-
ronment like a graph. We formally describe our robot network
model and the discrete partitioning problem in Section III, and
then state our coverage algorithm and its properties. Section IV
contains proofs of the main convergence results. In Section V
we detail our implementation of the algorithm and present
experiments and comparative analysis. Some conclusions are
given in Section VI.
In our notation, R≥0 denotes the set of non-negative real
numbers and Z≥0 the set of non-negative integers. Given a
set A, |A| denotes the number of elements in A. Given sets
A, B, their difference is A \ B = {a ∈A | a /∈B}. A set-
valued map, denoted by T : A ⇒B, associates to an element
of A a subset of B.
II. PRELIMINARIES
We are given a team of N robots tasked with providing
coverage of a finite set of points in a non-convex and non-
polygonal environment. In this Section we translate concepts
used in coverage of continuous environments to graphs.
A. Non-convex Environment as a Graph
Let Q be a finite set of points in a continuous environment.
These points represent locations of interest, and are assumed
to be connected by weighted edges. Let G(Q) = (Q, E, w)
be an (undirected) weighted graph with edge set E ⊂Q × Q
and weight map w : E →R>0; we let we > 0 be the weight
of edge e. We assume that G(Q) is connected and think of
the edge weights as distances between locations.
Remark 2.1 (Discretization of an Environment): For
the
examples in this paper we will use a coarse occupancy grid
3
map as a representation of a continuous environment. In
an occupancy grid [21], each grid cell is either free space
or an obstacle (occupied). To form a weighted graph, each
free cell becomes a vertex and free cells are connected with
edges if they border each other in the grid. Edge weights
are the distances between the centers of the cells, i.e., the
grid resolution. There are many other methods to discretize a
space, including triangularization and other approaches from
computational geometry [22], which could also be used.
In any weighted graph G(Q) there is a standard notion of
distance between vertices defined as follows. A path in G is
an ordered sequence of vertices such that any consecutive pair
of vertices is an edge of G. The weight of a path is the sum
of the weights of the edges in the path. Given vertices h and
k in G, the distance between h and k, denoted dG(h, k), is
the weight of the lowest weight path between them, or +∞if
there is no path. If G is connected, then the distance between
any two vertices in G is finite. By convention, dG(h, k) = 0
if h = k. Note that dG(h, k) = dG(k, h), for any h, k ∈Q.
B. Partitions of Graphs
We will be partitioning Q into N connected subsets or
regions which will each be covered by an individual robot.
To do so we need to define distances on induced subgraphs of
G(Q). Given I ⊂Q, the subgraph induced by the restriction
of G to I, denoted by G ∩I, is the graph with vertex set
equal to I and edge set containing all weighted edges of
G where both vertices belong to I. In other words, we set
(Q, E, w) ∩I = (Q ∩I, E ∩(I×I), w|I×I). The induced sub-
graph is a weighted graph with a notion of distance between
vertices: given h, k ∈I, we write dI(h, k) := dG ∩I(h, k).
Note that dI(h, k) ≥dG(h, k).
We define a connected subset of Q as a subset A ⊂Q such
that A ̸= ∅and G ∩A is connected. We can then partition Q
into connected subsets as follows.
Definition 2.2 (Connected Partitions): Given
the
graph
G(Q) = (Q, E, w), we define a connected N−partition of Q
as a collection P = {Pi}N
i=1 of N subsets of Q such that
(i) SN
i=1 Pi = Q;
(ii) Pi ∩Pj = ∅if i ̸= j;
(iii) Pi ̸= ∅for all i ∈{1, . . . , N}; and
(iv) Pi is connected for all i ∈{1, . . . , N}.
Let PartN(Q) to be the set of connected N−partitions of Q.
Property (ii) implies that each element of Q belongs to just
one Pi, i.e., each location in the environment is covered by
just one robot. Notice that each Pi ∈P induces a connected
subgraph in G(Q). In subsequent references to Pi we will
often mean G ∩Pi, and in fact we refer to Pi(t) as the
dominance subgraph or region of the i-th robot at time t.
Among the ways of partitioning Q, there are some which
are worth special attention. Given a vector of distinct points
c ∈QN, the partition P ∈PartN(Q) is said to be a Voronoi
partition of Q generated by c if, for each Pi and all k ∈Pi,
we have ci ∈Pi and dG(k, ci) ≤dG(k, cj), ∀j ̸= i. Note that
the Voronoi partition generated by c is not unique since how
to apportion tied vertices is unspecified.
C. Adjacency of Partitions
For our gossip algorithms we need to introduce the notion
of adjacent subgraphs. Two distinct connected subgraphs Pi,
Pj are said to be adjacent if there are two vertices qi, qj
belonging, respectively, to Pi and Pj such that (qi, qj) ∈E.
Observe that if Pi and Pj are adjacent then Pi ∪Pj is
connected. Similarly, we say that robots i and j are adjacent
or are neighbors if their subgraphs Pi and Pj are adjacent.
Accordingly, we introduce the following useful notion.
Definition 2.3 (Adjacency Graph): For P ∈PartN(Q), we
define the adjacency graph between regions of partition P as
G(P) = ({1, . . . , N}, E(P)), where (i, j) ∈E(P) if Pi and
Pj are adjacent.
Note that G(P) is always connected since G(Q) is.
D. Cost Functions
We define three coverage cost functions for graphs: Hone,
Hmulticenter, and Hexpected. Let the weight function φ : Q →R>0
assign a relative weight to each element of Q. The one-center
function Hone gives the cost for a robot to cover a connected
subset A ⊂Q from a vertex h ∈A with relative prioritization
set by φ:
Hone(h; A) =
X
k∈A
dA(h, k)φ(k).
A technical assumption is needed to solve the problem of
minimizing Hone(·, A): we assume from now on that a total
order relation, <, is defined on Q, i.e., that Q = {1, . . . , |Q|}.
With this assumption we can deterministically pick a vertex
in A which minimizes Hone as follows.
Definition 2.4 (Centroid): Let Q be a totally ordered set,
and let A ⊂Q. We define the set of generalized centroids of
A as the set of vertices in A which minimize Hone, i.e.,
C(A) := argmin
h∈A
Hone(h; A).
Further, we define the map Cd as Cd(A) := min{c ∈C(A)}.
We call Cd(A) the generalized centroid of A.
In subsequent use we drop the word “generalized” for
brevity. Note that with this definition the centroid is well-
defined, and also that the centroid of a region always belongs
to the region. With a slight notational abuse, we define
Cd : PartN(Q) →QN as the map which associates to a
partition the vector of the centroids of its elements.
We define the multicenter function Hmulticenter to measure the
cost for N robots to cover a connected N-partition P from
the vertex set c ∈QN:
Hmulticenter(c, P) =
1
P
k∈Q φ(k)
N
X
i=1
Hone(ci; Pi).
We aim to minimize the performance function Hmulticenter with
respect to both the vertices c and the partition P.
We can now state the coverage cost function we will be
concerned with for the rest of this paper. Let Hexpected :
PartN(Q) →R≥0 be defined by
Hexpected(P) = Hmulticenter(Cd(P), P).
4
In the motivational scenario we are considering, each robot
will periodically be asked to perform a task somewhere in its
region with tasks appearing according to distribution φ. When
idle, the robots would position themselves at the centroid of
their region. By partitioning G so as to minimize Hexpected, the
robot team would minimize the expected distance between a
task and the robot which will service it.
E. Optimal Partitions
We introduce two notions of optimal partitions: centroidal
Voronoi and pairwise-optimal. Our discussion starts with the
following simple result about the multicenter cost function.
Proposition 2.5 (Properties of Multicenter Function): Let
P ∈PartN(Q) and c ∈QN. If P ′ is a Voronoi partition
generated by c and c′ ∈Qn is such that c′
i ∈C(Pi) ∀i, then
Hmulticenter(c, P ′) ≤Hmulticenter(c, P), and
Hmulticenter(c′, P) ≤Hmulticenter(c, P).
The second inequality is strict if any ci /∈C(Pi).
Proposition 2.5 implies the following necessary condition:
if (c, P) minimizes Hmulticenter, then ci ∈C(Pi) ∀i and P
must be a Voronoi partition generated by c. Thus, Hexpected
has the following property as an immediate consequence of
Proposition 2.5: given P ∈PartN(Q), if P ∗is a Voronoi
partition generated by Cd(P) then
Hexpected(P ∗) ≤Hexpected(P).
This fact motivates the following definition.
Definition 2.6 (Centroidal Voronoi Partition):
P
∈
PartN(Q) is a centroidal Voronoi partition of Q
if there exists a c ∈Qn such that P is a Voronoi partition
generated by c and ci ∈C(Pi) ∀i.
The set of pairwise-optimal partitions provides an alterna-
tive definition for the optimality of a partition: a partition is
pairwise-optimal if, for every pair of adjacent regions, one can
not find a better two-partition of the union of the two regions.
This condition is formally stated as follows.
Definition 2.7 (Pairwise-optimal Partition):
P
∈
PartN(Q) is a pairwise-optimal partition if for
every (i, j) ∈E(P),
Hone(Cd(Pi); Pi) + Hone(Cd(Pj); Pj) =
min
a,b∈Pi∪Pj

X
k∈Pi∪Pj
min

dPi∪Pj(a, k), dPi∪Pj(b, k)
	
φ(k)

.
The following Proposition states that the set pairwise-
optimal partitions is in fact a subset of the set of centroidal
Voronoi partitions. The proof is involved and is deferred to
Appendix C. See Fig. 2 for an example which demonstrates
that the inclusion is strict.
Proposition 2.8 (Pairwise-optimal Implies Voronoi): Let
P ∈PartN(Q) be a pairwise-optimal partition. Then P is
also a centroidal Voronoi partition.
For a given environment Q, a pair made of a centroidal
Voronoi partition P and the corresponding vector of centroids
c is locally optimal in the following sense: Hexpected cannot be
(a)
(b)
(c)
Fig. 2.
All possible centroidal Voronoi partitions of a uniform 2 × 5 grid.
Assuming all edge weights are w and all vertices have priority 1, then (a)
has a cost of 1.2w, (b) has a cost of 1.1w, and (c) has a cost of 1.0w. Only
(c) is pairwise-optimal by definition.
reduced by changing either P or c independently. A pairwise-
optimal partition achieves this property and adds that for every
pair of neighboring robots (i, j), there does not exist a two-
partition of Pi∪Pj with a lower coverage cost. In other words,
positioning the robots at the centroids of a centroidal Voronoi
partition (locally) minimizes the expected distance between a
task appearing randomly in Q according to relative weights φ
and the robot who owns the vertex where the task appears.
Positioning at the centroids of a pairwise-optimal partition
improves performance by reducing the number of sub-optimal
solutions which the team might converge to.
III. MODELS, PROBLEM FORMULATION, AND PROPOSED
SOLUTION
We aim to partition Q among N robotic agents using
only asynchronous, unreliable, short-range communication. In
Section III-A we describe the computation, motion, and com-
munication capabilities required of the team of robots, and in
Section III-B we formally state the problem we are addressing.
In Section III-C we propose our solution, the Discrete Gossip
Coverage Algorithm, and in III-D we provide an illustration. In
Sections III-E and III-F we state the algorithm’s convergence
and complexity properties.
A. Robot Network Model with Gossip Communication
Our Discrete Gossip Coverage Algorithm requires a team
of N robotic agents where each agent i ∈{1, . . . , N} has the
following basic computation and motion capabilities:
(C1) agent i knows its unique identifier i;
(C2) agent i has a processor with the ability to store G(Q)
and perform operations on subgraphs of G(Q); and
(C3) agent i can determine which vertex in Q it occupies and
can move at speed v along the edges of G(Q) to any
other vertex in Q.
Remark 3.1 (Localization): The localization requirement in
(C3) is actually quite loose. Localization is only used for nav-
igation and not for updating partitions, thus limited duration
localization errors are not a problem.
The robotic agents are assumed to be able to communicate
with each other according to the range-limited gossip commu-
nication model which is described as follows:
(C4) given a communication range rcomm > maxe∈E we, when
any two agents reside for some positive duration at a
distance r < rcomm, they communicate at the sample
times of a Poisson process with intensity λcomm > 0.
Recall that an homogeneous Poisson process is a widely-
used stochastic model for events which occur randomly and
5
independently in time, where the expected number of events
in a period ∆is ∆λcomm.
Remark 3.2 (Communication Model): (1) This commu-
nication capability is the minimum necessary for our algo-
rithm, any additional capability can only reduce the time
required for convergence. For example, it would be acceptable
to have intensity λ(r) depend upon the pairwise robot distance
in such a way that λ(r) ≥λcomm for r < rcomm.
(2)
We use distances in the graph to model limited range
communication. These graph distances are assumed to ap-
proximate geodesic distances in the underlying continuous
environment and thus path distances for a diffracting wave
or moving robot.
B. Problem Statement
Assume that, for all t ∈R≥0, each agent i ∈{1, . . . , N}
maintains in memory a connected subset Pi(t) of environment
Q. Our goal is to design a distributed algorithm that iteratively
updates the partition P(t) = {Pi(t)}N
i=1 while solving the
following optimization problem:
min
P ∈PartN(Q) Hexpected(P),
(1)
subject to the constraints imposed by the robot network model
with range-limited gossip communication from Section III-A.
C. The Discrete Gossip Coverage Algorithm
In the design of an algorithm for the minimization prob-
lem (1) there are two main questions which must be addressed.
First, given the limited communication capabilities in (C4),
how should the robots move inside Q to guarantee frequent
enough meetings between pairs of robots? Second, when
two robots are communicating, what information should they
exchange and how should they update their regions?
In this section we introduce the Discrete Gossip Coverage
Algorithm which, following these two questions, consists of
two components:
(1) the Random Destination & Wait Motion Protocol; and
(2) the Pairwise Partitioning Rule.
The concurrent implementation of the Random Destination
& Wait Motion Protocol and the Pairwise Partitioning Rule
determines the evolution of the positions and dominance
subgraphs of the agents as we now formally describe. We start
with the Random Destination & Wait Motion Protocol.
Random Destination & Wait Motion Protocol
Each
agent
i
∈
{1, . . . , N}
determines
its
motion
by
repeatedly
performing
the
following
actions:
1: agent i samples a destination vertex qi from a uniform
distribution over its dominance subgraph Pi;
2: agent i moves to vertex qi through the shortest path in Pi
connecting the vertex it currently occupies and qi; and
3: agent i waits at qi for a duration τ > 0.
If agent i is moving from one vertex to another we say that
agent i is in the moving state while if agent i is waiting at
some vertex we say that it is in the waiting state.
Remark 3.3 (Motion Protocol): The motion protocol is de-
signed to ensure frequent enough communication between
pairs of robots. In general, any motion protocol can be used
which meets this requirement, so i could select qi from the
boundary of Pi or use some heuristic non-uniform distribution
over Pi.
If any two agents i and j reside in two vertices at a graphical
distance smaller that rcomm for some positive duration, then at
the sample times of the corresponding communication Poisson
process the two agents exchange sufficient information to
update their respective dominance subgraphs Pi and Pj via
the Pairwise Partitioning Rule.
Pairwise Partitioning Rule
Assume that at time t ∈R≥0, agent i and agent j communi-
cate. Without loss of generality assume that i < j. Let Pi(t)
and Pj(t) denote the current dominance subgraphs of i and
j, respectively. Moreover, let t+ denote the time instant just
after t. Then, agents i and j perform the following tasks:
1: agent i transmits Pi(t) to agent j and vice-versa
2: initialize Wa∗:= Pi(t), Wb∗:= Pj(t), a∗:= Cd(Pi(t)),
b∗:= Cd(Pj(t))
3: compute U := Pi(t) ∪Pj(t) and an ordered list S of all
pairs of vertices in U
4: for each (a, b) ∈S do
5:
compute the sets
Wa := {x ∈U : dU(x, a) ≤dU(x, b)}
Wb := {x ∈U : dU(x, a) > dU(x, b)}
6:
if Hone(a; Wa) + Hone(b; Wb) <
Hone(a∗; Wa∗) + Hone(b∗; Wb∗) then
7:
Wa∗:= Wa, Wb∗:= Wb, a∗:= a, b∗:= b
8: Pi(t+) := Wa∗,
Pj(t+) := Wb∗
Some remarks are now in order.
Remark 3.4 (Partitioning Rule): (1) The Pairwise Parti-
tioning Rule is designed to find a minimum cost two-partition
of U. More formally, if list S and sets Wa∗and Wb∗for
(a∗, b∗) ∈S are defined as in the Pairwise Partitioning Rule,
then Wa∗and Wb∗are an optimal two-partition of U.
(2)
While the loop in steps 4-7 must run to completion to
guarantee that Wa∗and Wb∗are an optimal two-partition of
U, the loop is designed to return an intermediate sub-optimal
result if need be. If Pi and Pj change, then Hexpected will
decrease and this is enough to ensure eventual convergence.
(3)
We make a simplifying assumption in the Pairwise
Partitioning Rule that, once two agents communicate, the
application of the partitioning rule is instantaneous. We discuss
the actual computation time required in Section III-F and some
implementation details in Section V.
(4)
Notice that simply assigning Wa∗to i and Wb∗to j can
cause the robots to “switch sides” in U. While convergence is
guaranteed regardless, switching may be undesirable in some
applications. In that case, any smart matching of Wa∗and Wb∗
to i and j may be inserted.
(5)
Agents who are not adjacent may communicate but the
partitioning rule will not change their regions. Indeed, in this
case Wa∗and Wb∗will not change from Pi(t) and Pj(t).
Some possible modifications and extensions to the algorithm
are worth mentioning.
6
Fig. 3.
Simulation of four robots dividing a square environment with obstacles. The boundary of each robots territory is drawn in a different color, the
centroid of a territory is drawn with an X, and pairwise communication is drawn with a solid red line. On the left is the initial partition assigned to the robots.
The middle frames show two pairwise territory exchanges, with updated territories highlighted with solid colors. The final partition is shown at right.
Remark 3.5 (Heterogeneous Robotic Networks): In
case
the robots have heterogeneous dynamics, line 5 can be
modified to consider per-robot travel times between vertices.
For example, dU(x, a) could be replaced by the expected
time for robot i to travel from a to x while dU(x, b) would
consider robot j.
Remark 3.6 (Coverage and Task Servicing): Here we fo-
cus on partitioning territory, but this algorithm can easily be
combined with methods to provide a service in Q as in [4].
The agents could split their time between moving to meet their
neighbors and update territory, and performing requested tasks
in their region.
D. Illustrative Simulation
The simulation in Fig. 3 shows four robots partitioning a
square environment with obstacles where the free space is
represented by a 12 × 12 grid. In the initial partition shown
in the left panel, the robot in the top right controls most of
the environment while the robot in the bottom left controls
very little. The robots then move according to the Random
Destination & Wait Motion Protocol, and communicate ac-
cording to range-limited gossip communication model with
rcomm = 2.5m (four edges in the graph).
The first pairwise territory exchange is shown in the second
panel, where the bottom left robot claims some territory from
the robot on the top left. A later exchange between the two
robots on the top is shown in the next two panels. Notice
that the cyan robot in the top right gives away the vertex it
currently occupies. In such a scenario, we direct the robot to
follow the shortest path in G(Q) to its updated territory before
continuing on to a random destination.
After 9 pairwise territory exchanges, the robots reach the
pairwise-optimal partition shown at right in Fig. 3. The ex-
pected distance between a random vertex and the closest robot
decreases from 2.34m down to 1.74m.
E. Convergence Property
The strength of the Discrete Gossip Coverage Algorithm is
the possibility of enforcing that a partition will converge to a
pairwise-optimal partition through pairwise territory exchange.
In Theorem 3.7 we summarize this convergence property, with
proofs given in Section IV.
Theorem 3.7 (Convergence Property): Consider a network
of N robotic agents endowed with computation and motion ca-
pacities (C1), (C2), (C3), and communication capacities (C4).
Assume the agents implement the Discrete Gossip Coverage
Algorithm consisting of the concurrent implementation of the
Random Destination & Wait Motion Protocol and the Pairwise
Partitioning Rule. Then,
(i) the partition P(t) remains connected and is described by
P : R≥0 →PartN(Q), and
(ii) P(t) converges almost surely in finite time to a pairwise-
optimal partition.
Remark 3.8 (Optimality of Solutions): By
definition,
a
pairwise-optimal partition is optimal in that Hexpected can not
be improved by changing only two regions in the partition.
Remark 3.9 (Generalizations): For simplicity we assume
uniform robot speeds, communication processes, and wait-
ing times. An extension to non-uniform processes would be
straightforward.
F. Complexity Properties and Discussion
In this subsection we explore the computational require-
ments of the Discrete Gossip Coverage Algorithm, and make
some comments on implementation. Cost function Hone(h; Pi)
is the sum of the distances between h and all other vertices
in Pi. This computation of one-to-all distances is the core
computation of the algorithm. For most graphs of interest the
total number of edges |E| is proportional to |Q|, so we will
state bounds on this computation in terms of |Pi|. Computing
one-to-all distances requires one of the following:
• if all edge weights in G(Q) are the same (e.g., for a graph
from an occupancy grid), a breadth-first search approach
can be used which requires O(|Pi|) in time and memory;
• otherwise, Dijkstra’s algorithm must be used which re-
quires O(|Pi| log (|Pi|)) in time and O(|Pi|) in memory.
Let D(Pi) be the time to compute one-to-all distances in Pi,
then computing Hone(h; Pi) requires O(D(Pi)) in time.
Proposition 3.10 (Complexity Properties): The
motion
protocol requires O(|Pi|) in memory, and O(D(Pi)) in
computation time. The partitioning rule requires O(|Pi|+|Pj|)
in
communication bandwidth between
robots i
and
j,
O(|Pi| + |Pj|) in memory, and can run in any time.
Proof: We first prove the claims for the motion protocol.
Step 2 is the only non-trivial step and requires finding a
shortest path in Pi, which is equivalent to computing one-to-
all distances from the robot’s current vertex. Hence, it requires
O(D(Pi)) in time and O(Pi) in memory.
7
We now prove the claims for the partitioning rule. In step
1, robots i and j transmit their subgraphs to each other,
which requires O(|Pi| + |Pj|) in communication bandwidth.
For step 3, the robots determine U := Pi ∪Pj, which requires
O(|Pi|+|Pj|) in memory to store. Step 4 is the start of a loop
which executes O(|U|2) times, affecting the time complexity
of steps 5, 6 and 7. Step 5 requires two computations of
one-to-all distances in U which each take O(D(U)). Step 6
involves four computations of Hone over different subsets of U,
however those for Wa∗and Wb∗can be stored from previous
computation. Since Wa and Wb are strict subsets of U, step
5 takes longer than step 6. Step 7 is trivial, as is step 8. The
total time complexity of the loop is thus O(|U|2 D(U)).
However, the loop in steps 4-7 can be truncated after any
number of iterations. While it must run to completion to
guarantee that Wa∗and Wb∗are an optimal two-partition of
U, the loop is designed to return an intermediate sub-optimal
result if need be. If Pi and Pj change, then Hexpected will
decrease. Our convergence result will hold provided that all
elements of S are eventually checked if Pi and Pj do not
change. Thus, the partitioning rule can run in any time with
each iteration requiring O(D(U)).
All of the computation and communication requirements in
Proposition 3.10 are independent of the number of robots and
scale with the size of a robot’s partition, meaning the Discrete
Gossip Coverage Algorithm can easily scale up for large teams
of robots in large environments.
IV. CONVERGENCE PROOFS
This section is devoted to proving the two statements in
Theorem 3.7. The proof that the Pairwise Partitioning Rule
maps a connected N-partition into a connected N-partition is
straightforward. The proof of convergence is more involved
and is based on the application of Lemma A.1 in Appendix A
to the Discrete Gossip Coverage Algorithm. Lemma A.1
establishes strong convergence properties for a particular class
of set valued maps (set-valued maps are briefly reviewed in
Appendix A).
We start by proving that the Pairwise Partitioning Rule is
well-posed in the sense that it maintains a connected partition.
Proof of Theorem 3.7 statement (i): To prove the state-
ment we need to show that P(t+) satisfies points (i) through
(iv) of Definition 2.2. From the definition of the Pairwise
Partitioning Rule, we have that Pi(t+)∪Pj(t+) = Pi(t)∪Pj(t)
and Pi(t+) ∩Pj(t+) = ∅. Moreover, since a∗∈Pi(t+) and
b∗∈Pj(t+), it follows that Pi(t+) ̸= ∅and Pj(t+) ̸= ∅.
These observations imply the validity of points (i), (ii), and
(iii) for P(t+). Finally, we must show that Pi(t+) and Pj(t+)
are connected, i.e., P(t+) also satisfies point (iv). To do
so we show that, given x ∈Wa∗, any shortest path in
Pi(t) ∪Pj(t) connecting x to a∗completely belongs to Wa∗.
We proceed by contradiction. Let sx,a∗denote a shortest path
in Pi(t) ∪Pj(t) connecting x to a∗and let us assume that
there exists m ∈sx,a∗such that m ∈Wb∗. For m to be
in Wb∗means that dPi(t)∪Pj(t)(m, b∗) < dPi(t)∪Pj(t)(m, a∗).
This implies that
dPi∪Pj(x, b∗) ≤dPi∪Pj(m, b∗) + dPi∪Pj(x, m)
< dPi∪Pj(m, a∗) + dPi∪Pj(x, m)
= dPi∪Pj(x, a∗).
This is a contradiction for x ∈Wa∗. Similar considerations
hold for Wb∗.
The rest of this section is dedicated to proving convergence.
Our first step is to show that the evolution determined by
the Discrete Gossip Coverage Algorithm can be seen as a
set-valued map. To this end, for any pair of robots (i, j) ∈
{1, . . ., N}2, i ̸= j, we define the map Tij : PartN(Q) →
PartN(Q) by
Tij(P) = (P1, . . . , bPi, . . . , bPj, . . . , PN),
where bPi = Wa∗and bPj = Wb∗.
If at time t ∈R≥0 the pair (i, j) and no other pair of robots
perform an iteration of the Pairwise Partitioning Rule, then the
dynamical system on the space of partitions is described by
P(t+) = Tij (P(t)) .
(2)
We define the set-valued map T : PartN(Q) ⇒PartN(Q) as
T (P) = {Tij(P) | (i, j) ∈{1, . . . , N}2, i ̸= j}.
(3)
Observe that (2) can then be rewritten as P(t+) ∈T (P(t)).
The next two Propositions state facts whose validity is
ensured by Lemma B.1 of Appendix B which states a key
property of the Random Destination & Wait Motion Protocol.
Proposition 4.1 (Persistence of Exchanges): Consider
N
robots implementing the Discrete Gossip Coverage Algorithm.
Then, there almost surely exists an increasing sequence of
time instants {tk}k∈Z≥0 such that P(t+
k ) = Tij(P(tk)) for
some (i, j) ∈E(P(tk)).
Proof: The proof follows directly from Lemma B.1
which implies that the time between two consecutive pairwise
communications is almost surely finite.
The existence of time sequence {tk}k∈Z≥0 allows us to to
express the evolution generate by the Discrete Gossip Cover-
age Algorithm as a discrete time process. Let P(k) := P(tk)
and P(k + 1) := P(t+
k ), then
P(k + 1) ∈T (P(k))
where T : PartN(Q) ⇒PartN(Q) is defined as in (3).
Given k ∈Z≥0, let Ik denote the information which
completely characterizes the state of Discrete Gossip Coverage
Algorithm just after the k-th iteration of the partitioning rule,
i.e., at time t+
k−1. Specifically, Ik contains the information
related to the partition P(k), the positions of the robots at
t+
k−1, and whether each robot is in the waiting or moving state
at t+
k−1. The following result characterizes the probability that,
given Ik, the (k + 1)-th iteration of the partitioning rule is
governed by any of the maps Tij, (i, j) ∈E(P(k)).
Proposition 4.2 (Probability of Communication): Consider
a team of N robots with capacities (C1), (C2), (C3), and
(C4) implementing the Discrete Gossip Coverage Algorithm.
8
Then, there exists a real number ¯π ∈(0, 1), such that, for any
k ∈Z≥0 and (i, j) ∈E(P(k))
P [P(k + 1) = Tij(P(k)) | Ik] ≥¯π.
Proof: Assume that at time ¯t one pair of robots commu-
nicates. Given a pair (¯i, ¯j) ∈E(P(¯t)), we must find a lower
bound for the probability that (¯i, ¯j) is the communicating pair.
Since all the Poisson communication processes have the same
intensity, the distribution of the chance of communication
is uniform over the pairs which are “able to communicate,”
i.e., closer than rcomm to each other. Thus, we must only
show that (¯i, ¯j) has a positive probability of being able to
communicate at time ¯t, which is equivalent to showing that
(¯i, ¯j) is able to communicate for a positive fraction of time
with positive probability. The proof of Lemma B.1 implies that
with probability at least α/(1 −e−λcommτ) any pair in E(P(¯t))
is able to communicate for a fraction of time not smaller than
τ
∆, where α and ∆are defined in the proof of Lemma B.1.
Hence the result follows.
The property in Proposition 4.2 can also be formulated as
follows. Let σ : Z≥0 →

(i, j) ∈{1, . . . , N}2, i ̸= j
	
be the
stochastic process such that σ(k) is the communicating pair at
time k. Then, the sequence of pairs of robots performing the
partitioning rule at time instants {tk}k∈Z≥0 can be seen as a
realization of the process σ, which satisfies
P

σ(k + 1) = (i, j) | σ(k)

≥¯π
(4)
for all (i, j) ∈E(P(k)).
Next we show that the cost function decreases whenever the
application of T from (3) changes the territory partition. This
fact is a key ingredient to apply Lemma A.1.
Lemma 4.3 (Decreasing Cost Function): Let
P ∈PartN(Q) and let P + ∈T (P). If P + ̸= P, then
Hexpected(P +) < Hexpected(P).
Proof: Without loss of generality assume that (i, j) is the
pair executing the Pairwise Partitioning Rule. Then
Hexpected(P +) −Hexpected(P)
= Hone(Cd(P +
i ); P +
i ) + Hone(Cd(P +
j ); P +
j )
−Hone(Cd(Pi); Pi) −Hone(Cd(Pj); Pj).
According to the definition of the Pairwise Partitioning Rule
we have that if P +
i
̸= Pi, P +
j ̸= Pj, then
Hone(Cd(P +
i ); P +
i ) + Hone(Cd(P +
j ); P +
j )
≤Hone(a∗; P +
i ) + Hone(b∗; P +
j )
< Hone(Cd(Pi); Pi) + Hone(Cd(Pj); Pj)
from which the statement follows.
We now complete the proof of the main result, Theorem 3.7.
Proof of Theorem 3.7 statement (ii):
Note that the
algorithm evolves in a finite space of partitions, and by Theo-
rem 3.7 statement (i), the set PartN(Q) is strongly positively
invariant. This fact implies that assumption (i) of Lemma A.1
is satisfied. From Lemma 4.3 it follows that assumption (ii)
is also satisfied, with Hexpected playing the role of the function
U. Finally, the property in (4) is equivalent to the property
of persistent random switches stated in Assumption (iii) of
Lemma A.1, for the special case h = 1. Hence, we are in the
position to apply Lemma A.1 and conclude convergence in
finite-time to an element of the intersection of the equilibria
of the maps Tij, which by definition is the set of the pairwise-
optimal partitions.
V. EXPERIMENTAL METHODS & RESULTS
To demonstrate the utility and study practical issues of
the Discrete Gossip Coverage Algorithm, we implemented
it using the open-source Player/Stage robot control system
[23] and the Boost Graph Library (BGL) [24]. All results
presented here were generated using Player 2.1.1, Stage 2.1.1,
and BGL 1.34.1. To compute distances in uniform edge weight
graphs we extended the BGL breadth-first search routine with
a distance recorder event visitor.
A. Large-scale Simulation
To evaluate the performance of our gossip coverage al-
gorithm with larger teams, we tested 30 simulated robots
partitioning a map representing a 350m × 225m portion of
campus at the University of California at Santa Barbara. As
shown in Fig. 4, the robots are tasked with providing coverage
of the open space around some of the buildings on campus,
a space which includes a couple open quads, some narrower
passages between buildings, and a few dead-end spurs. For
this large environment the simulated robots are 2m on a side
and can move at 3.0 m
s . Each territory cell is 3m × 3m.
In this simulation we handle communication and partition-
ing as follows. The communication range is set to 30m (10
edges in the graph) with λcomm = 0.3 comm
s
. The robots wait
at their destination vertices for τ = 3.5s. This value for τ
was chosen so that on average one quarter of the robots are
waiting at any moment. Lower values of τ mean the robots
are moving more of the time and as a result more frequently
miss connections, while for higher τ the robots spend more
time stationary which also reduces the rate of convergence.
With the goal of improving communication, we implemented a
minor modification to the motion protocol: each robot picks its
random destination from the cells forming the open boundary1
of its territory. In our implementation, the full partitioning
loop may take 5 seconds for the largest initial territories in
Fig. 4. We chose to stop the loop after a quarter second for
this simulation to verify the anytime computation claim.
The 30 robots start clustered in the center of the map
between Engineering II and Broida Hall, and an initial Voronoi
partition is generated from these starting positions. This initial
partition is shown on the left in Fig. 4 with the robots
positioned at the centroids of their starting regions. The initial
partition has a cost of 37.1m. The team spends about 27
minutes moving and communicating according to the Dis-
crete Gossip Coverage Algorithm before settling on the final
partition on the right of Fig. 4. The coverage cost of the
final equilibrium improved by 54% to 17.1m. Visually, the
1The open boundary of Pi is the set of vertices in Pi which are adjacent
to at least one vertex owned by another agent.
9
Fig. 4.
Images of starting and final partitions for a simulation with 30 robots providing coverage of a portion of campus at UCSB.
0
5
10
15
20
25
30
15
20
25
30
35
40
g replacements
Time (minutes)
Total cost Hexpected
Fig. 5.
Graph of the cost Hexpected over time for the simulation in Fig. 4.
final partition is also dramatically more uniform than the
initial condition. This result demonstrates that the algorithm
is effective for large teams in large non-convex environments.
Fig. 5 shows the evolution of Hexpected during the simulation.
The largest cost improvements happen early when the robots
that own the large territories on the left and right of the map
communicate with neighbors with much smaller territories.
These big territory changes then propagate through the net-
work as the robots meet and are pushed and pulled towards a
lower cost partition.
B. Implementation Details
We conducted an experiment to test the algorithm using
three physical robots in our lab, augmented by six simulated
robots in a synthetic environment extending beyond the lab.
Our lab space is 11.3m on a side and is represented by the
upper left portion of the territory maps in Fig. 7. The territory
graph loops around a center island of desks. We extended
the lab space through three connections into a simulated
environment around the lab, producing a 15.9m × 15.9m
environment. The map of the environment was specified with
a 0.15m bitmap which we overlayed with a 0.6m resolution
occupancy grid representing the free territory for the robots to
cover. The result is a lattice-like graph with all edge weights
equal to 0.6m. The 0.6m resolution was chosen so that our
physical robots would fit easily inside a cell.
Additional details of our implementation are as follows.
Robot hardware: We use Erratic mobile robots from Videre
Design, as shown in Fig. 6. The vehicle platform has a roughly
PSfrag replacements
Rangefinder
Drive wheel
Computer
Rear caster
Fig. 6.
Erratic mobile robot with URG-04LX laser rangefinder.
square footprint (40cm × 37cm), with two differential drive
wheels and a single rear caster. Each robot carries an onboard
computer with a 1.8Ghz Core 2 Duo processor, 1 GB of
memory, and 802.11g wireless communication. For navigation
and localization, each robot is equipped with a Hokuyo URG-
04LX laser rangefinder. The rangefinder scans 683 points over
240◦at 10Hz with a range of 5.6 meters.
Experiment setup: Our mixed physical and virtual robot
experiments are run from a central computer which is attached
to a wireless router so it can communicate with the physical
robots. The central computer creates a simulated world using
Stage which mirrors and extends the real space in which the
physical robots operate. The central computer also simulates
the virtual members of the robot team. These virtual robots are
modeled off of our hardware: they are differential drive with
the same geometry as the Erratic platform and use simulated
Hokuyo URG-04LX rangefinders.
Localization: We use the amcl driver in Player which
implements Adaptive Monte-Carlo Localization [25]. The
physical robots are provided with a map of our lab with a
15cm resolution and told their starting pose within the map.
We set an initial pose standard deviation of 0.9m in position
and 12◦in orientation, and request localization updates using
50 of the sensor’s range measurements for each change of
2cm in position or 2◦in orientation reported by the robot’s
odometry system. We then use the most likely pose estimate
output by amcl as the location of the robot. For simplicity and
reduced computational demand, we allow the virtual robots
access to perfect localization information.
10
3
2
1
1
3
2
2
3
1
3
1
2
2
1
3
3
2
1
Fig. 7.
Each column contains a territory map and the corresponding overhead camera image for a step of the hardware-in-the-loop simulation. The position
of the camera in the environment is shown with a camera icon in the territory map. The physical robots are numbered 1, 2, and 3 and have the orange, blue,
and lime green partitions. Their positions in each territory map are indicated with numbered circles.
Motion Protocol: Each robot continuously executes the
Random Destination & Wait Motion Protocol, with navigation
handled by the snd driver in Player which implements Smooth
Nearness Diagram navigation [26]. For snd we set the robot
radius parameter to 22cm, obstacle avoidance distance to
0.7m, and maximum speeds to 0.4 m
s and 40
◦
s. The snd driver
is a local obstacle avoidance planner, so we feed it a series
of waypoints every couple meters along paths found in G(Q).
We consider a robot to have achieved its target location when
it is within 20cm and it will then wait for τ = 3.5s. For the
physical robots the motion protocol and navigation processes
run on board, while there are separate threads for each virtual
robot on the central computer.
Communication and Partitioning: As the robots move, a
central process monitors their positions and simulates the
range-limited gossip communication model between both real
and virtual robots. We set rcomm = 2.5m and λcomm =
0.3 comm
s
. These parameters were chosen so that the robots
would be likely to communicate when separated by at most
four edges, but would also sometimes not connect despite
being close. When this process determines two robots should
communicate, it informs the robots who then perform the
Pairwise Partitioning Rule. Our pairwise communication im-
plementation is blocking: if robot i is exchanging territory
with j, then it informs the match making process that it is
unavailable until the exchange is complete.
C. Hardware-in-the-Loop Simulation
The results of our experiment with three physical robots
and six simulated robots are shown in Figs. 7 and 8. The left
column in Fig. 7 shows the starting positions of the team of
robots, with the physical robots, labeled 1, 2, and 3, lined up
in a corner of the lab and the simulated robots arrayed around
them. The starting positions are used to generate the initial
Voronoi partition of the environment. The physical robots own
the orange, blue, and lime green territories in the upper left
quadrant. We chose this initial configuration to have a high
coverage cost, while ensuring that the physical robots will
remain in the lab as the partition evolves.
In the middle column, robots 1 and 2 have met along their
shared border and are exchanging territory. In the territory
map, the solid red line indicates 1 and 2 are communicating
and their updated territories are drawn with solid orange and
blue, respectively. The camera view confirms that the two
robots have met on the near side of the center island of desks.
The final partition at right in Fig. 7 is reached after 9 1
2
minutes. All of the robots are positioned at the centroids of
their final territories. The three physical robots have gone from
a cluster in one corner of the lab to a more even spread around
the space. Fig. 8 shows the evolution of the cost function
Hexpected as the experiment progresses, including the costs for
each robot. As expected, the total cost never increases and the
disparity of costs for the individual robots shrinks over time
until settling at a pairwise-optimal partition.
In this experiment the hardware challenges of sensor noise,
navigation, and uncertainty in position were efficiently han-
dled by the amcl and snd drivers. The coverage algorithm
assumed the role of a higher-level planner, taking in posi-
tion data from amcl and directing snd. By far the most
computationally demanding component was amcl, but the
position hypotheses from amcl are actually unnecessary: our
coverage algorithm only requires knowledge of the vertex
11
0
2
4
6
8
10
2
2.5
3
0
2
4
6
8
10
0
200
400
replacements
Time (minutes)
Robot costs (m)
Hexpected (m)
Fig. 8.
Evolution of cost functions during the experiment in Fig. 7. The total
cost Hexpected is shown above in black, while Hone for each robot is shown
below in the robot’s color.
a robot occupies. If a less intensive localization method is
available, the algorithm could run on robots with significantly
lower compute power.
D. Comparative analysis
In this subsection we present a numerical comparison of the
performance of the Discrete Gossip Coverage Algorithm and
the following two Lloyd-type algorithms.
Decentralized Lloyd Algorithm: This method is from [11]
and [9], we describe it here for convenience. At each discrete
time instant t ∈Z≥0, each robot i performs the following
tasks: (1) i transmits its position and receives the positions of
all adjacent robots; (2) i computes its Voronoi region Pi based
on the information received; and (3) i moves to Cd(Pi).
Gossip Lloyd Algorithm: This method is from [19]. It is
a gossip algorithm, and so we have used the same commu-
nication model and the Random Destination & Wait Motion
Protocol to create meetings between robots. Say robots i and j
meet at time t, then the pairwise Lloyd partitioning rule works
as follows: (1) robot i transmits Pi(t) to j and vice versa; (2)
both robots determine U = Pi(t) ∪Pj(t); (3) robot i sets
Pi(t+) to be its Voronoi region of U based on Cd(Pi(t)) and
Cd(Pj(t)), and j does the equivalent.
For both Lloyd algorithms we use the same tie breaking rule
when creating Voronoi regions as is present in the Pairwise
Partitioning Rule: ties go to the robot with the lowest index.
Our first numerical result uses a Monte Carlo probability
estimation method from [27] to place probabilistic bounds on
the performance of the two gossip algorithms. Recall that the
Chernoff bound describes the minimum number of random
samples K required to reach a certain level of accuracy in a
probability estimate from independent Bernoulli tests. For an
accuracy ǫ ∈(0, 1) and confidence 1 −η ∈(0, 1), the number
of samples is given by K ≥
1
2ǫ2 log 2
η. For η = 0.01 and
ǫ = 0.1, at least 116 samples are required.
Figure 9 shows both the initial territory partition of the
extended laboratory environment used and also a histogram
2
2.2
2.4
2.6
2.8
3
0
50
100
PSfrag replacements
Final cost (m)
Simulation count
Fig. 9.
Initial partition and histogram of final costs for a Monte Carlo
test comparing the Discrete Gossip Coverage Algorithm (black bars), Gossip
Lloyd Algorithm (gray bars), and Decentralized Lloyd Algorithm (red dashed
line). For the gossip algorithms, 116 simulations were performed with different
sequences of pairwise communications. The Decentralized Lloyd Algorithm
is deterministic given an initial condition so only one final cost is shown.
of the final results for the following Monte Carlo test. The
environment and robot motion models used are described in
Section V-B. Starting from the indicated initial condition, we
ran 116 simulations of both gossip algorithms. The random-
ness in the test comes from the sequence of pairwise com-
munications. These sequences were generated using: (1) the
Random Destination & Wait Motion Protocol with qi sampled
uniformly from the open boundary of Pi and τ = 3.5s;
and (2) the range-limited gossip communication model with
rcomm = 2.5m and λcomm = 0.3 comm
s
.
The cost of the initial partition in Fig. 9 is 5.48m, while
the best known partition for this environment has a cost of
just under 2.18m. The histogram in Fig. 9 shows the final
equilibrium costs for 116 simulations of the Discrete Gossip
Coverage Algorithm (black) and the Gossip Lloyd Algorithm
(gray). It also shows the final cost using the Decentralized
Lloyd Algorithm (red dashed line), which is deterministic
from a given initial condition. The histogram bins have a
width of 0.10m and start from 2.17m. For the Discrete
Gossip Coverage Algorithm, 105 out of 116 trials reach
the bin containing the best known partition and the mean
final cost is 2.23m. The Gossip Lloyd Algorithm reaches
the lowest bin in only 5 of 116 trials and has a mean final
cost of 2.51m. The Decentralized Lloyd Algorithm settles
at 2.48m. Our new gossip algorithm requires an average of
12
replacements
Final cost (m)
Simulation count
Fig. 10.
Histograms of final costs from 10 Monte Carlo tests using
random initial conditions in the environment shown in Fig. 9 comparing
Discrete Gossip Coverage Algorithm (black bars), Gossip Lloyd Algorithm
(gray bars), and Decentralized Lloyd Algorithm (red dashed line). For the
gossip algorithms, 116 simulations were performed with different sequences of
pairwise communications. The Decentralized Lloyd Algorithm is deterministic
given an initial condition so only one final cost is shown. The initial cost for
each test is drawn with the green dashed line.
96 pairwise communications to reach an equilibrium, whereas
gossip Lloyd requires 126.
Based on these results, we can conclude with 99% confi-
dence that there is at least an 80% probability that 9 robots
executing the Discrete Gossip Coverage Algorithm starting
from the initial partition shown in Fig. 9 will reach a pairwise-
optimal partition which has a cost within 4% of the best known
cost. We can further conclude with 99% confidence that the
Gossip Lloyd Algorithm will settle more than 4% above the
best known cost at least 86% of the time starting from this
initial condition.
Figure 10 compares final cost histograms for 10 different
initial conditions for the same environment and parameters
as described above. Each initial condition was created by
selecting unique starting locations for the robots uniformly
at random and using these locations to generate an initial
Voronoi partition. The initial cost for each test is shown with
the green dashed line. In 9 out of 10 tests the Discrete Gossip
Coverage Algorithm reaches the histogram bin with the best
known partition in at least 112 of 116 trials. The two Lloyd
methods get stuck in sub-optimal centroidal Voronoi partitions
more than 4% away from the best known partition in more than
half the trials in 7 of 10 tests.
VI. CONCLUSION
We have presented a novel distributed partitioning and cov-
erage control algorithm which requires only unreliable short-
range communication between pairs of robots and works in
non-convex environments. The classic Lloyd approach to cov-
erage optimization involves iteration of separate centering and
Voronoi partitioning steps. For gossip algorithms, however,
this separation is unnecessary computationally and we have
shown that improved performance can be achieved without
it. Our new Discrete Gossip Coverage Algorithm provably
converges to a subset of the set of centroidal Voronoi par-
titions which we labeled pairwise-optimal partitions. Through
numerical comparisons we demonstrated that this new subset
of solutions avoids many of the local minima in which Lloyd-
type algorithms can get stuck.
Our vision is that this partitioning and coverage algorithm
will form the foundation of a distributed task servicing setup
for teams of mobile robots. The robots would split their time
between servicing tasks in their territory and moving to contact
their neighbors and improve the coverage of the space. Our
convergence results only require sporadic improvements to
the cost function, affording flexibility in robot behaviors and
capacities, and offering the ability to handle heterogeneous
robotic networks. In the bigger picture, this paper demonstrates
the potential of gossip communication in distributed coordi-
nation algorithms. There appear to be many other problems
where this realistic and minimal communication model could
be fruitfully applied.
APPENDIX A
For completeness we present a convergence result for set-
valued algorithms on finite state spaces, which can be recov-
ered as a direct consequence of [18, Theorem 4.5].
Given a set X, a set-valued map T : X ⇒X is a map
which associates to an element x ∈X a subset Z ⊂X. A
set-valued map is non-empty if T (x) ̸= ∅for all x ∈X. Given
a non-empty set-valued map T , an evolution of the dynamical
system associated to T is a sequence {xn}n∈Z≥0 ⊂X where
xn+1 ∈T (xn) for all n ∈Z≥0. A set W ⊂X is strongly
positively invariant for T if T (w) ⊂W for all w ∈W.
Lemma A.1 (Persistent random switches imply convergence):
Let (X, d) be a finite metric space. Given a collection of maps
T1, . . . , Tm : X →X, define the set-valued map T : X ⇒X
by T (x) = {T1(x), . . . , Tm(x)}. Given a stochastic process
σ : Z≥0 →{1, . . . , m}, consider an evolution {xn}n∈Z≥0 of
T satisfying xn+1 = Tσ(n)(xn). Assume that:
13
(i) there exists a set W ⊆X that is strongly positively
invariant for T ;
(ii) there exists a function U : W →R such that U(w′) <
U(w), for all w ∈W and w′ ∈T (w) \ {w}; and
(iii) there exist p ∈(0, 1) and k ∈N such that, for all i ∈
{1, . . . , m} and n ∈Z≥0, there exists h ∈{1, . . . , k}
such that P

σ(n + h) = i | σ(n), . . . , σ(1)

≥p.
For i ∈{1, . . . , m}, let Fi be the set of fixed points of Ti in
W, i.e., Fi = {w ∈W | Ti(w) = w}. If x0 ∈W, then the
evolution {xn}n∈Z≥0 converges almost surely in finite time to
an element of the set (F1 ∩· · · ∩Fm), i.e., there exists almost
surely τ ∈N such that, for some ¯x ∈(F1 ∩· · · ∩Fm), xn = ¯x
for n ≥τ.
APPENDIX B
This Appendix proves a property of the Random Destina-
tion & Wait Motion Protocol which is needed to show the
persistence of pairwise exchanges.
Lemma B.1: Consider N robots implementing the Dis-
crete Gossip Coverage Algorithm starting from an arbitrary
P ∈PartN(Q). Consider t ∈R≥0 and let P(t) denote the
partition at time t. Assume that at time t no two robots are
communicating. Then, there exist ∆> 0 and α ∈(0, 1),
independent of P(t) and the positions and states of the
robots at time t, such that, for every (i, j) ∈E(P(t)),
P [(i, j) communicate within (t, t + ∆)] ≥α.
Proof: To begin, we define two useful quantities. Let
S(Q)
:=
max
P ∈PartN (Q) max
Pi∈P max
h,k∈Pi dPi(h, k) be a pseudo-
diameter for Q, and then choose ∆:= 2 S(Q)
v
+ 2τ. We fix a
pair (i, j) ∈E(P), and pick adjacent vertices a ∈Pi, b ∈Pj.
Our goal is to lower bound the probability that i and j
will communicate within the interval (t, t + ∆). To do so
we construct one sequence of events of positive probability
which enables such communication. Consider the following
situation: i is in the moving state and needs time ti to reach
its destination qi, whereas robot j is in the waiting state at
vertex qj and must wait there for time τj ≤τ. We denote
by t(a) (resp. t(b)) the time needed for i (resp. j) to travel
from qi (resp. qj) to a (resp. b). Let Ei be the event such
that i performs the following actions in (t, t + ∆) without
communicating with any robot k ̸= j:
(i) i reaches qi and waits at qi for the duration τ; and
(ii) i chooses vertex a as its next destination and then stays
at a for at least ∆−t(a) −ti −τ.
Let Ej be the event such that j performs the following actions
in (t, t + ∆) without communicating with any k ̸= i:
(i) j waits at qj for the duration τj; and
(ii) j chooses vertex b as its next destination and then stays
at b for at least ∆−t(b) −τj.
Let Eij = Ei ∩Ej.
Next, we lower bound the probability that event Ei occurs.
Recall the definition of λcomm from Sec. III-A. Since a robot
can have at most N −1 neighbors, the probability that (i)
of Ei happens is lower bounded by e−λcommτN. For (ii), the
probability that i chooses a is 1/ |Pi|, which is lower bounded
by 1/ |Q|. Then, in order to spend at least (∆−t(a) −ti −τ)
at a, i must choose a for ⌈∆−t(a)−ti−τ
τ
⌉consecutive times.
Finally, the probability that during this interval i will not
communicate with any robot other than j is lower bounded by
e−λcomm∆(N−2). The probability that (ii) occurs is thus lower
bounded by (1/ |Q|)⌈∆
τ ⌉e−λcomm∆N. Combining the bounds for
(i) and (ii), it follows that
P[Ei] ≥
 1
|Q|

⌈∆
τ ⌉e−λcomm(∆+τ)N.
The same lower bound holds for P[Ej], meaning that
P [Eij] = P [Ei] P [Ej] ≥
 1
|Q|

2⌈∆
τ ⌉e−2λcomm(∆+τ)N.
If event Eij occurs, then robots i and j will be at adjacent
vertices for an amount of time during the interval (t, t + ∆)
equal to min {∆−t(a) −ti −τ, ∆−t(b) −τj} . Since t(a)
and t(b) are no more than
S(Q)
v
, we can conclude that i
and j will be within rcomm for at least τ. Conditioned on
Eij occurring, the probability that i and j communicate in
(t, t+∆) is lower bounded by 1−e−λcommτ. A suitable choice
for α from the statement of the Lemma is thus
α =
 1
|Q|

2⌈∆
τ ⌉e−2λcomm(∆+τ)N 1 −e−λcommτ

.
It can be shown that this also constitutes a lower bound for the
other possible combinations of initial states: robot i is waiting
and robot j is moving; robots i and j are both moving; and
robots i and j are both waiting.
APPENDIX C
In this appendix we provide the proof of Proposition 2.8
which states that any pairwise-optimal partition is also a
centroidal Voronoi partition.
Proof of Proposition 2.8:
To create a contradiction,
assume that P ∈PartN(Q) is a pairwise-optimal partition
but not a centroidal Voronoi partition. In other words, there
exist components Pi and Pj in P and an element x of one
component, say x ∈Pi, such that
dG (x, Cd(Pi)) > dG (x, Cd(Pj)) .
(5)
Choose Pj such that for all k ̸= j
dG (x, Cd(Pk)) ≥dG (x, Cd(Pj)) .
(6)
Let sG
a,b be a shortest path in G connecting a to b and let
m ∈sG
x,Cd(Pj) be the first element of the path starting from
Cd(Pj) which is not in Pj. Let ℓbe such that m ∈Pℓ.
If m = x, then from (5) and the definition of sG
x,Cd(Pj) we
have that
dPi (x, Cd(Pi)) ≥dG (x, Cd(Pi))
> dG (x, Cd(Pi)) = dPi∪Pj (x, Cd(Pj))
which, since x ∈Pi, creates a contradiction of the fact that P
is pairwise-optimal.
If m ̸= x, then, given (6), one of these two conditions holds:
(i) dG (m, Cd(Pℓ)) > dG (m, Cd(Pj)), or
(ii) dG (m, Cd(Pℓ)) = dG (m, Cd(Pj)).
In the first case, we again have a contradiction using the same
logic above with m in place of x. In the second case, we
14
must further consider whether there exists a sG
m,Cd(Pℓ) such
that every vertex in sG
m,Cd(Pℓ) is also in Pℓ. If there is not
such a path, then
dPℓ(m, Cd(Pℓ)) > dG (m, Cd(Pℓ)) = dPℓ∪Pj (m, Cd(Pj))
and we again have a contradiction as above. If there is such a
path, then we can instead repeat this analysis using using ℓin
place of j and considering the path formed by this sG
m,Cd(Pℓ)
and the vertices in sG
x,Cd(Pj) after m. Since the next vertex
playing the role of m must be closer to x, we will eventually
find a vertex which creates a contradiction.
REFERENCES
[1] R. Smith, J. Das, H. Heidarsson, A. Pereira, F. Arrichiello, I. Cetnic,
L. Darjany, M.-E. Garneau, M. Howard, C. Oberg, M. Ragan, E. Seubert,
E. Smith, B. Stauffer, A. Schnetzer, G. Toro-Farmer, D. Caron, B. Jones,
and G. Sukhatme, “USC CINAPS builds bridges,” IEEE Robotics &
Automation Magazine, vol. 17, no. 1, pp. 20–30, 2010.
[2] P. R. Wurman, R. D’Andrea, and M. Mountz, “Coordinating hundreds of
cooperative, autonomous vehicles in warehouses,” AI Magazine, vol. 29,
no. 1, pp. 9–20, 2008.
[3] S. Yun, M. Schwager, and D. Rus, “Coordinating construction of truss
structures using distributed equal-mass partitioning,” in International
Symposium on Robotics Research, (Lucerne, Switzerland), Aug. 2009.
[4] F. Bullo, E. Frazzoli, M. Pavone, K. Savla, and S. L. Smith, “Dynamic
vehicle routing for robotic systems,” Proceedings of the IEEE, vol. 99,
no. 9, pp. 1482–1504, 2011.
[5] A. K. Jain, M. N. Murty, and P. J. Flynn, “Data clustering: A review,”
ACM Computing Surveys, vol. 31, no. 3, pp. 264–323, 1999.
[6] V. V. Vazirani, Approximation Algorithms. Springer, 2001.
[7] P. O. Fj¨allstr¨om, “Algorithms for graph partitioning:
A survey,”
Link¨oping Electronic Articles in Computer and Information Science,
vol. 3, no. 10, 1998.
[8] F. R. Adler and D. M. Gordon, “Optimization, conflict, and nonover-
lapping foraging ranges in ants,” American Naturalist, vol. 162, no. 5,
pp. 529–543, 2003.
[9] F. Bullo, J. Cort´es, and S. Mart´ınez, Distributed Control of Robotic
Networks.
Applied Mathematics Series, Princeton University Press,
2009. Available at http://www.coordinationbook.info.
[10] S. P. Lloyd, “Least squares quantization in PCM,” IEEE Transactions
on Information Theory, vol. 28, no. 2, pp. 129–137, 1982. Presented at
the 1957 Institute for Mathematical Statistics Meeting.
[11] J. Cort´es, S. Mart´ınez, T. Karatas, and F. Bullo, “Coverage control
for mobile sensing networks,” IEEE Transactions on Robotics and
Automation, vol. 20, no. 2, pp. 243–255, 2004.
[12] M. Zhong and C. G. Cassandras, “Distributed coverage control in
sensor network environments with polygonal obstacles,” in IFAC World
Congress, (Seoul, Korea), pp. 4162–4167, July 2008.
[13] L. C. A. Pimenta, V. Kumar, R. C. Mesquita, and G. A. S. Pereira,
“Sensing and coverage for a network of heterogeneous robots,” in IEEE
Conf. on Decision and Control, (Canc´un, M´exico), pp. 3947–3952, Dec.
2008.
[14] M. Schwager, D. Rus, and J. J. Slotine, “Decentralized, adaptive cov-
erage control for networked robots,” International Journal of Robotics
Research, vol. 28, no. 3, pp. 357–375, 2009.
[15] R. Cortez, H. Tanner, and R. Lumia, “Distributed robotic radiation map-
ping,” in Experimental Robotics (O. Khatib, V. Kumar, and G. Pappas,
eds.), vol. 54 of Springer Tracts in Advanced Robotics, pp. 147–156,
Springer, 2009.
[16] O. Baron, O. Berman, D. Krass, and Q. Wang, “The equitable location
problem on the plane,” European Journal of Operational Research,
vol. 183, no. 2, pp. 578–590, 2007.
[17] M. B. Dias, R. Zlot, N. Kalra, and A. Stentz, “Market-based multirobot
coordination: A survey and analysis,” Proceedings of the IEEE, vol. 94,
no. 7, pp. 1257–1270, 2006.
[18] F. Bullo, R. Carli, and P. Frasca, “Gossip coverage control for robotic
networks: Dynamical systems on the the space of partitions,” SIAM
Journal on Control and Optimization, Aug. 2010. Submitted. Available
at http://motion.me.ucsb.edu/pdf/2008u-bcf.pdf.
[19] J. W. Durham, R. Carli, P. Frasca, and F. Bullo, “Discrete partitioning
and coverage control with gossip communication,” in ASME Dynamic
Systems and Control Conference, (Hollywood, CA, USA), pp. 225–232,
Oct. 2009.
[20] J. W. Durham, R. Carli, and F. Bullo, “Pairwise optimal coverage control
for robotic networks in discretized environments,” in IEEE Conf. on
Decision and Control, (Atlanta, GA, USA), pp. 7286–7291, Dec. 2010.
[21] H. Minc, Nonnegative Matrices. Wiley, 1988.
[22] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Computational Geometry: Algorithms and Applications. Springer, 2 ed.,
2000.
[23] B. Gerkey, R. T. Vaughan, and A. Howard, “The Player/Stage Project:
Tools for multi-robot and distributed sensor systems,” in Int. Conference
on Advanced Robotics, (Coimbra, Portugal), pp. 317–323, June 2003.
[24] J. G. Siek, L.-Q. Lee, and A. Lumsdaine, “Boost Graph Library.”
http://www.boost.org, July 2007. Version 1.34.1.
[25] S. Thrun, D. Fox, W. Burgard, and F. Dellaert, “Robust Monte Carlo
localization for mobile robots,” Artificial Intelligence, vol. 128, no. 1-2,
pp. 99–141, 2001.
[26] J. W. Durham and F. Bullo, “Smooth nearness-diagram navigation,” in
IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, (Nice, France),
pp. 690–695, Sept. 2008.
[27] R. Tempo, G. Calafiore, and F. Dabbene, Randomized Algorithms for
Analysis and Control of Uncertain Systems. Springer, 2005.
arXiv:1011.1939v2  [cs.RO]  26 Sep 2011
Discrete Partitioning and Coverage Control
for Gossiping Robots
Joseph W. Durham
Ruggero Carli
Paolo Frasca
Francesco Bullo
Abstract—We propose distributed algorithms to automatically
deploy a team of mobile robots to partition and provide coverage
of a non-convex environment. To handle arbitrary non-convex
environments, we represent them as graphs. Our partitioning and
coverage algorithm requires only short-range, unreliable pairwise
“gossip” communication. The algorithm has two components: (1)
a motion protocol to ensure that neighboring robots communicate
at least sporadically, and (2) a pairwise partitioning rule to update
territory ownership when two robots communicate. By studying
an appropriate dynamical system on the space of partitions of the
graph vertices, we prove that territory ownership converges to
a pairwise-optimal partition in finite time. This new equilibrium
set represents improved performance over common Lloyd-type
algorithms. Additionally, we detail how our algorithm scales well
for large teams in large environments and how the computation
can run in anytime with limited resources. Finally, we report on
large-scale simulations in complex environments and hardware
experiments using the Player/Stage robot control system.
I. INTRODUCTION
Coordinated networks of mobile robots are already in use
for environmental monitoring and warehouse logistics. In
the near future, autonomous robotic teams will revolutionize
transportation of passengers and goods, search and rescue op-
erations, and other applications. These tasks share a common
feature: the robots are asked to provide service over a space.
One question which arises is: when a group of robots is waiting
for a task request to come in, how can they best position
themselves to be ready to respond?
The distributed environment partitioning problem for robotic
networks consists of designing individual control and com-
munication laws such that the team divides a large space into
regions. Typically, partitioning is done so as to optimize a cost
function which measures the quality of service provided over
all of the regions. Coverage control additionally optimizes the
positioning of robots inside a region as shown in Fig. 1.
This paper describes a distributed partitioning and coverage
control algorithm for a network of robots to minimize the
This work was supported in part by ARO MURI Award W911NF-05-1-
0219, NSF grants IIS-0904501 and CPS-1035917, and MIUR grant PRIN-
20087W5P2. Preliminary and incomplete versions of this work appeared in the
Proceedings of the 2009 ASME Dynamic Systems and Control Conference,
Hollywood, California, USA, and in the Proceedings of the 2010 IEEE
Conference on Decision and Control, Atlanta, Georgia, USA.
Joseph W. Durham and Francesco Bullo are with the Department of
Mechanical Engineering, University of California, Santa Barbara, CA, 93106
(joey, bullo)@engineering.ucsb.edu
Ruggero
Carli
is
with
the
Department
of
Information
Engineer-
ing,
University
of Padova,
Via
Gradenigo
6/a,
35131
Padova,
Italy
carlirug@dei.unipd.it
Paolo
Frasca
is
with
the
Dipartimento
di
Matematica,
Politec-
nico
di
Torino,
corso
Duca
degli
Abruzzi
24,
10129
Torino,
Italy
paolo.frasca@polito.it
Fig. 1.
Example of a team of robots providing efficient coverage of a non-
convex environment, as measured by an appropriate multicenter cost function.
expected distance between the closest robot and spatially
distributed events which will appear at discrete points in a non-
convex environment. Optimality is defined with reference to a
relevant “multicenter” cost function. As with all multirobot co-
ordination applications, the challenge comes from reducing the
communication requirements: the proposed algorithm requires
only short-range “gossip” communication, i.e., asynchronous
and unreliable communication between nearby robots.
Literature Review
Territory partitioning and coverage control have applica-
tions in many fields. In cyber-physical systems, applications
include automated environmental monitoring [1], fetching and
delivery [2], construction [3], and other vehicle routing scenar-
ios [4]. More generally, coverage of discrete sets is also closely
related to the literature on data clustering and k-means [5],
as well as the facility location or k-center problem [6].
Partitioning of graphs is its own field of research, see [7] for a
survey. Territory partitioning through local interactions is also
studied for animal groups, see for example [8].
A broad discussion of algorithms for partitioning and
coverage control in robotic networks is presented in [9]
which builds on the classic work of Lloyd [10] on optimal
quantizer selection through “centering and partitioning.” The
Lloyd approach was first adapted for distributed coverage
control in [11]. Since this beginning, similar algorithms have
been applied to non-convex environments [12], [13], unknown
density functions [14], [15], equitable partitioning [16], and
construction of truss-like objects [3]. There are also multi-
agent partitioning algorithms built on market principles or
1
2
auctions, see [17] for a survey.
While Lloyd iterative optimization algorithms are popular
and work well in simulation, they require synchronous and
reliable communication among neighboring robots. As robots
with adjacent regions may be arbitrarily far apart, these
communication requirements are burdensome and unrealistic
for deployed robotic networks. In response to this issue, in [18]
the authors have shown how a group of robotic agents can
optimize the partition of a convex bounded set using a Lloyd
algorithm with gossip communication. A Lloyd algorithm with
gossip communication has also been applied to optimizing
partitions of non-convex environments in [19], the key idea
being to transform the coverage problem in Euclidean space
into a coverage problem on a graph with geodesic distances.
Distributed Lloyd methods are built around separate parti-
tioning and centering steps, and they are attractive because
there are known ways to characterize their equilibrium sets
(the so-called centroidal Voronoi partitions) and prove con-
vergence. Unfortunately, even for very simple environments
(both continuous and discrete) the set of centroidal Voronoi
partitions may contain several sub-optimal configurations. We
are thus interested in studying (discrete) gossip coverage
algorithms for two reasons: (1) they apply to more realistic
robot network models featuring very limited communication in
large non-convex environments, and (2) they are more flexible
than typical Lloyd algorithms meaning they can avoid poor
suboptimal configurations and improve performance.
Statement of Contributions
There are three main contributions in this paper. First,
we present a discrete partitioning and coverage optimization
algorithm for mobile robots with unreliable, asynchronous, and
short-range communication. Our algorithm has two compo-
nents: a motion protocol which drives the robots to meet their
neighbors, and a pairwise partitioning rule to update territories
when two robots meet. The partitioning rule optimizes cover-
age of a set of points connected by edges to form a graph. The
flexibility of graphs allows the algorithm to operate in non-
convex, non-polygonal environments with holes. Our graph
partition optimization approach can also be applied to non-
planar problems, existing transportation or logistics networks,
or more general data sets.
Second, we provide an analysis of both the convergence
properties and computational requirements of the algorithm.
By studying a dynamical system of partitions of the graph’s
vertices, we prove that almost surely the algorithm converges
to a pairwise-optimal partition in finite time. The set of
pairwise-optimal partitions is shown to be a proper subset
of the well-studied set of centroidal Voronoi partitions. We
further describe how our pairwise partitioning rule can be
implemented to run in anytime and how the computational
requirements of the algorithm can scale up for large domains
and large teams.
Third, we detail experimental results from our implementa-
tion of the algorithm in the Player/Stage robot control system.
We present a simulation of 30 robots providing coverage of a
portion of a college campus to demonstrate that our algorithm
can handle large robot teams, and a hardware-in-the-loop
experiment conducted in our lab which incorporates sensor
noise and uncertainty in robot position. Through numerical
analysis we also show how our new approach to partitioning
represents a significant performance improvement over both
common Lloyd-type methods and the recent results in [18].
The present work differs from the gossip Lloyd method [18]
in three respects. First, while [18] focuses on territory par-
titioning in a convex continuous domain, here we operate
on a graph which allows our approach to consider geodesic
distances, work in non-convex environments, and maintain
connected territories. Second, instead of a pairwise Lloyd-like
update, we use an iterative optimal two-partitioning approach
which yields better final solutions. Third, we also present a
motion protocol to produce the sporadic pairwise commu-
nications required for our gossip algorithm and characterize
the computational complexity of our proposal. Preliminary
versions of this paper appeared in [19] and [20]. Compared to
these, the new content here includes: (1) a motion protocol;
(2) a simplified and improved pairwise partitioning rule; (3)
proofs of the convergence results; and (4) a description of our
implementation and a hardware-in-the-loop experiment.
Paper Structure and Notation
In Section II we review and adapt coverage and geometric
concepts (e.g., centroids, Voronoi partitions) to a discrete envi-
ronment like a graph. We formally describe our robot network
model and the discrete partitioning problem in Section III, and
then state our coverage algorithm and its properties. Section IV
contains proofs of the main convergence results. In Section V
we detail our implementation of the algorithm and present
experiments and comparative analysis. Some conclusions are
given in Section VI.
In our notation, R≥0 denotes the set of non-negative real
numbers and Z≥0 the set of non-negative integers. Given a
set A, |A| denotes the number of elements in A. Given sets
A, B, their difference is A \ B = {a ∈A | a /∈B}. A set-
valued map, denoted by T : A ⇒B, associates to an element
of A a subset of B.
II. PRELIMINARIES
We are given a team of N robots tasked with providing
coverage of a finite set of points in a non-convex and non-
polygonal environment. In this Section we translate concepts
used in coverage of continuous environments to graphs.
A. Non-convex Environment as a Graph
Let Q be a finite set of points in a continuous environment.
These points represent locations of interest, and are assumed
to be connected by weighted edges. Let G(Q) = (Q, E, w)
be an (undirected) weighted graph with edge set E ⊂Q × Q
and weight map w : E →R>0; we let we > 0 be the weight
of edge e. We assume that G(Q) is connected and think of
the edge weights as distances between locations.
Remark 2.1 (Discretization of an Environment): For
the
examples in this paper we will use a coarse occupancy grid
3
map as a representation of a continuous environment. In
an occupancy grid [21], each grid cell is either free space
or an obstacle (occupied). To form a weighted graph, each
free cell becomes a vertex and free cells are connected with
edges if they border each other in the grid. Edge weights
are the distances between the centers of the cells, i.e., the
grid resolution. There are many other methods to discretize a
space, including triangularization and other approaches from
computational geometry [22], which could also be used.
In any weighted graph G(Q) there is a standard notion of
distance between vertices defined as follows. A path in G is
an ordered sequence of vertices such that any consecutive pair
of vertices is an edge of G. The weight of a path is the sum
of the weights of the edges in the path. Given vertices h and
k in G, the distance between h and k, denoted dG(h, k), is
the weight of the lowest weight path between them, or +∞if
there is no path. If G is connected, then the distance between
any two vertices in G is finite. By convention, dG(h, k) = 0
if h = k. Note that dG(h, k) = dG(k, h), for any h, k ∈Q.
B. Partitions of Graphs
We will be partitioning Q into N connected subsets or
regions which will each be covered by an individual robot.
To do so we need to define distances on induced subgraphs of
G(Q). Given I ⊂Q, the subgraph induced by the restriction
of G to I, denoted by G ∩I, is the graph with vertex set
equal to I and edge set containing all weighted edges of
G where both vertices belong to I. In other words, we set
(Q, E, w) ∩I = (Q ∩I, E ∩(I×I), w|I×I). The induced sub-
graph is a weighted graph with a notion of distance between
vertices: given h, k ∈I, we write dI(h, k) := dG ∩I(h, k).
Note that dI(h, k) ≥dG(h, k).
We define a connected subset of Q as a subset A ⊂Q such
that A ̸= ∅and G ∩A is connected. We can then partition Q
into connected subsets as follows.
Definition 2.2 (Connected Partitions): Given
the
graph
G(Q) = (Q, E, w), we define a connected N−partition of Q
as a collection P = {Pi}N
i=1 of N subsets of Q such that
(i) SN
i=1 Pi = Q;
(ii) Pi ∩Pj = ∅if i ̸= j;
(iii) Pi ̸= ∅for all i ∈{1, . . . , N}; and
(iv) Pi is connected for all i ∈{1, . . . , N}.
Let PartN(Q) to be the set of connected N−partitions of Q.
Property (ii) implies that each element of Q belongs to just
one Pi, i.e., each location in the environment is covered by
just one robot. Notice that each Pi ∈P induces a connected
subgraph in G(Q). In subsequent references to Pi we will
often mean G ∩Pi, and in fact we refer to Pi(t) as the
dominance subgraph or region of the i-th robot at time t.
Among the ways of partitioning Q, there are some which
are worth special attention. Given a vector of distinct points
c ∈QN, the partition P ∈PartN(Q) is said to be a Voronoi
partition of Q generated by c if, for each Pi and all k ∈Pi,
we have ci ∈Pi and dG(k, ci) ≤dG(k, cj), ∀j ̸= i. Note that
the Voronoi partition generated by c is not unique since how
to apportion tied vertices is unspecified.
C. Adjacency of Partitions
For our gossip algorithms we need to introduce the notion
of adjacent subgraphs. Two distinct connected subgraphs Pi,
Pj are said to be adjacent if there are two vertices qi, qj
belonging, respectively, to Pi and Pj such that (qi, qj) ∈E.
Observe that if Pi and Pj are adjacent then Pi ∪Pj is
connected. Similarly, we say that robots i and j are adjacent
or are neighbors if their subgraphs Pi and Pj are adjacent.
Accordingly, we introduce the following useful notion.
Definition 2.3 (Adjacency Graph): For P ∈PartN(Q), we
define the adjacency graph between regions of partition P as
G(P) = ({1, . . . , N}, E(P)), where (i, j) ∈E(P) if Pi and
Pj are adjacent.
Note that G(P) is always connected since G(Q) is.
D. Cost Functions
We define three coverage cost functions for graphs: Hone,
Hmulticenter, and Hexpected. Let the weight function φ : Q →R>0
assign a relative weight to each element of Q. The one-center
function Hone gives the cost for a robot to cover a connected
subset A ⊂Q from a vertex h ∈A with relative prioritization
set by φ:
Hone(h; A) =
X
k∈A
dA(h, k)φ(k).
A technical assumption is needed to solve the problem of
minimizing Hone(·, A): we assume from now on that a total
order relation, <, is defined on Q, i.e., that Q = {1, . . . , |Q|}.
With this assumption we can deterministically pick a vertex
in A which minimizes Hone as follows.
Definition 2.4 (Centroid): Let Q be a totally ordered set,
and let A ⊂Q. We define the set of generalized centroids of
A as the set of vertices in A which minimize Hone, i.e.,
C(A) := argmin
h∈A
Hone(h; A).
Further, we define the map Cd as Cd(A) := min{c ∈C(A)}.
We call Cd(A) the generalized centroid of A.
In subsequent use we drop the word “generalized” for
brevity. Note that with this definition the centroid is well-
defined, and also that the centroid of a region always belongs
to the region. With a slight notational abuse, we define
Cd : PartN(Q) →QN as the map which associates to a
partition the vector of the centroids of its elements.
We define the multicenter function Hmulticenter to measure the
cost for N robots to cover a connected N-partition P from
the vertex set c ∈QN:
Hmulticenter(c, P) =
1
P
k∈Q φ(k)
N
X
i=1
Hone(ci; Pi).
We aim to minimize the performance function Hmulticenter with
respect to both the vertices c and the partition P.
We can now state the coverage cost function we will be
concerned with for the rest of this paper. Let Hexpected :
PartN(Q) →R≥0 be defined by
Hexpected(P) = Hmulticenter(Cd(P), P).
4
In the motivational scenario we are considering, each robot
will periodically be asked to perform a task somewhere in its
region with tasks appearing according to distribution φ. When
idle, the robots would position themselves at the centroid of
their region. By partitioning G so as to minimize Hexpected, the
robot team would minimize the expected distance between a
task and the robot which will service it.
E. Optimal Partitions
We introduce two notions of optimal partitions: centroidal
Voronoi and pairwise-optimal. Our discussion starts with the
following simple result about the multicenter cost function.
Proposition 2.5 (Properties of Multicenter Function): Let
P ∈PartN(Q) and c ∈QN. If P ′ is a Voronoi partition
generated by c and c′ ∈Qn is such that c′
i ∈C(Pi) ∀i, then
Hmulticenter(c, P ′) ≤Hmulticenter(c, P), and
Hmulticenter(c′, P) ≤Hmulticenter(c, P).
The second inequality is strict if any ci /∈C(Pi).
Proposition 2.5 implies the following necessary condition:
if (c, P) minimizes Hmulticenter, then ci ∈C(Pi) ∀i and P
must be a Voronoi partition generated by c. Thus, Hexpected
has the following property as an immediate consequence of
Proposition 2.5: given P ∈PartN(Q), if P ∗is a Voronoi
partition generated by Cd(P) then
Hexpected(P ∗) ≤Hexpected(P).
This fact motivates the following definition.
Definition 2.6 (Centroidal Voronoi Partition):
P
∈
PartN(Q) is a centroidal Voronoi partition of Q
if there exists a c ∈Qn such that P is a Voronoi partition
generated by c and ci ∈C(Pi) ∀i.
The set of pairwise-optimal partitions provides an alterna-
tive definition for the optimality of a partition: a partition is
pairwise-optimal if, for every pair of adjacent regions, one can
not find a better two-partition of the union of the two regions.
This condition is formally stated as follows.
Definition 2.7 (Pairwise-optimal Partition):
P
∈
PartN(Q) is a pairwise-optimal partition if for
every (i, j) ∈E(P),
Hone(Cd(Pi); Pi) + Hone(Cd(Pj); Pj) =
min
a,b∈Pi∪Pj

X
k∈Pi∪Pj
min

dPi∪Pj(a, k), dPi∪Pj(b, k)
	
φ(k)

.
The following Proposition states that the set pairwise-
optimal partitions is in fact a subset of the set of centroidal
Voronoi partitions. The proof is involved and is deferred to
Appendix C. See Fig. 2 for an example which demonstrates
that the inclusion is strict.
Proposition 2.8 (Pairwise-optimal Implies Voronoi): Let
P ∈PartN(Q) be a pairwise-optimal partition. Then P is
also a centroidal Voronoi partition.
For a given environment Q, a pair made of a centroidal
Voronoi partition P and the corresponding vector of centroids
c is locally optimal in the following sense: Hexpected cannot be
(a)
(b)
(c)
Fig. 2.
All possible centroidal Voronoi partitions of a uniform 2 × 5 grid.
Assuming all edge weights are w and all vertices have priority 1, then (a)
has a cost of 1.2w, (b) has a cost of 1.1w, and (c) has a cost of 1.0w. Only
(c) is pairwise-optimal by definition.
reduced by changing either P or c independently. A pairwise-
optimal partition achieves this property and adds that for every
pair of neighboring robots (i, j), there does not exist a two-
partition of Pi∪Pj with a lower coverage cost. In other words,
positioning the robots at the centroids of a centroidal Voronoi
partition (locally) minimizes the expected distance between a
task appearing randomly in Q according to relative weights φ
and the robot who owns the vertex where the task appears.
Positioning at the centroids of a pairwise-optimal partition
improves performance by reducing the number of sub-optimal
solutions which the team might converge to.
III. MODELS, PROBLEM FORMULATION, AND PROPOSED
SOLUTION
We aim to partition Q among N robotic agents using
only asynchronous, unreliable, short-range communication. In
Section III-A we describe the computation, motion, and com-
munication capabilities required of the team of robots, and in
Section III-B we formally state the problem we are addressing.
In Section III-C we propose our solution, the Discrete Gossip
Coverage Algorithm, and in III-D we provide an illustration. In
Sections III-E and III-F we state the algorithm’s convergence
and complexity properties.
A. Robot Network Model with Gossip Communication
Our Discrete Gossip Coverage Algorithm requires a team
of N robotic agents where each agent i ∈{1, . . . , N} has the
following basic computation and motion capabilities:
(C1) agent i knows its unique identifier i;
(C2) agent i has a processor with the ability to store G(Q)
and perform operations on subgraphs of G(Q); and
(C3) agent i can determine which vertex in Q it occupies and
can move at speed v along the edges of G(Q) to any
other vertex in Q.
Remark 3.1 (Localization): The localization requirement in
(C3) is actually quite loose. Localization is only used for nav-
igation and not for updating partitions, thus limited duration
localization errors are not a problem.
The robotic agents are assumed to be able to communicate
with each other according to the range-limited gossip commu-
nication model which is described as follows:
(C4) given a communication range rcomm > maxe∈E we, when
any two agents reside for some positive duration at a
distance r < rcomm, they communicate at the sample
times of a Poisson process with intensity λcomm > 0.
Recall that an homogeneous Poisson process is a widely-
used stochastic model for events which occur randomly and
5
independently in time, where the expected number of events
in a period ∆is ∆λcomm.
Remark 3.2 (Communication Model): (1) This commu-
nication capability is the minimum necessary for our algo-
rithm, any additional capability can only reduce the time
required for convergence. For example, it would be acceptable
to have intensity λ(r) depend upon the pairwise robot distance
in such a way that λ(r) ≥λcomm for r < rcomm.
(2)
We use distances in the graph to model limited range
communication. These graph distances are assumed to ap-
proximate geodesic distances in the underlying continuous
environment and thus path distances for a diffracting wave
or moving robot.
B. Problem Statement
Assume that, for all t ∈R≥0, each agent i ∈{1, . . . , N}
maintains in memory a connected subset Pi(t) of environment
Q. Our goal is to design a distributed algorithm that iteratively
updates the partition P(t) = {Pi(t)}N
i=1 while solving the
following optimization problem:
min
P ∈PartN(Q) Hexpected(P),
(1)
subject to the constraints imposed by the robot network model
with range-limited gossip communication from Section III-A.
C. The Discrete Gossip Coverage Algorithm
In the design of an algorithm for the minimization prob-
lem (1) there are two main questions which must be addressed.
First, given the limited communication capabilities in (C4),
how should the robots move inside Q to guarantee frequent
enough meetings between pairs of robots? Second, when
two robots are communicating, what information should they
exchange and how should they update their regions?
In this section we introduce the Discrete Gossip Coverage
Algorithm which, following these two questions, consists of
two components:
(1) the Random Destination & Wait Motion Protocol; and
(2) the Pairwise Partitioning Rule.
The concurrent implementation of the Random Destination
& Wait Motion Protocol and the Pairwise Partitioning Rule
determines the evolution of the positions and dominance
subgraphs of the agents as we now formally describe. We start
with the Random Destination & Wait Motion Protocol.
Random Destination & Wait Motion Protocol
Each
agent
i
∈
{1, . . . , N}
determines
its
motion
by
repeatedly
performing
the
following
actions:
1: agent i samples a destination vertex qi from a uniform
distribution over its dominance subgraph Pi;
2: agent i moves to vertex qi through the shortest path in Pi
connecting the vertex it currently occupies and qi; and
3: agent i waits at qi for a duration τ > 0.
If agent i is moving from one vertex to another we say that
agent i is in the moving state while if agent i is waiting at
some vertex we say that it is in the waiting state.
Remark 3.3 (Motion Protocol): The motion protocol is de-
signed to ensure frequent enough communication between
pairs of robots. In general, any motion protocol can be used
which meets this requirement, so i could select qi from the
boundary of Pi or use some heuristic non-uniform distribution
over Pi.
If any two agents i and j reside in two vertices at a graphical
distance smaller that rcomm for some positive duration, then at
the sample times of the corresponding communication Poisson
process the two agents exchange sufficient information to
update their respective dominance subgraphs Pi and Pj via
the Pairwise Partitioning Rule.
Pairwise Partitioning Rule
Assume that at time t ∈R≥0, agent i and agent j communi-
cate. Without loss of generality assume that i < j. Let Pi(t)
and Pj(t) denote the current dominance subgraphs of i and
j, respectively. Moreover, let t+ denote the time instant just
after t. Then, agents i and j perform the following tasks:
1: agent i transmits Pi(t) to agent j and vice-versa
2: initialize Wa∗:= Pi(t), Wb∗:= Pj(t), a∗:= Cd(Pi(t)),
b∗:= Cd(Pj(t))
3: compute U := Pi(t) ∪Pj(t) and an ordered list S of all
pairs of vertices in U
4: for each (a, b) ∈S do
5:
compute the sets
Wa := {x ∈U : dU(x, a) ≤dU(x, b)}
Wb := {x ∈U : dU(x, a) > dU(x, b)}
6:
if Hone(a; Wa) + Hone(b; Wb) <
Hone(a∗; Wa∗) + Hone(b∗; Wb∗) then
7:
Wa∗:= Wa, Wb∗:= Wb, a∗:= a, b∗:= b
8: Pi(t+) := Wa∗,
Pj(t+) := Wb∗
Some remarks are now in order.
Remark 3.4 (Partitioning Rule): (1) The Pairwise Parti-
tioning Rule is designed to find a minimum cost two-partition
of U. More formally, if list S and sets Wa∗and Wb∗for
(a∗, b∗) ∈S are defined as in the Pairwise Partitioning Rule,
then Wa∗and Wb∗are an optimal two-partition of U.
(2)
While the loop in steps 4-7 must run to completion to
guarantee that Wa∗and Wb∗are an optimal two-partition of
U, the loop is designed to return an intermediate sub-optimal
result if need be. If Pi and Pj change, then Hexpected will
decrease and this is enough to ensure eventual convergence.
(3)
We make a simplifying assumption in the Pairwise
Partitioning Rule that, once two agents communicate, the
application of the partitioning rule is instantaneous. We discuss
the actual computation time required in Section III-F and some
implementation details in Section V.
(4)
Notice that simply assigning Wa∗to i and Wb∗to j can
cause the robots to “switch sides” in U. While convergence is
guaranteed regardless, switching may be undesirable in some
applications. In that case, any smart matching of Wa∗and Wb∗
to i and j may be inserted.
(5)
Agents who are not adjacent may communicate but the
partitioning rule will not change their regions. Indeed, in this
case Wa∗and Wb∗will not change from Pi(t) and Pj(t).
Some possible modifications and extensions to the algorithm
are worth mentioning.
6
Fig. 3.
Simulation of four robots dividing a square environment with obstacles. The boundary of each robots territory is drawn in a different color, the
centroid of a territory is drawn with an X, and pairwise communication is drawn with a solid red line. On the left is the initial partition assigned to the robots.
The middle frames show two pairwise territory exchanges, with updated territories highlighted with solid colors. The final partition is shown at right.
Remark 3.5 (Heterogeneous Robotic Networks): In
case
the robots have heterogeneous dynamics, line 5 can be
modified to consider per-robot travel times between vertices.
For example, dU(x, a) could be replaced by the expected
time for robot i to travel from a to x while dU(x, b) would
consider robot j.
Remark 3.6 (Coverage and Task Servicing): Here we fo-
cus on partitioning territory, but this algorithm can easily be
combined with methods to provide a service in Q as in [4].
The agents could split their time between moving to meet their
neighbors and update territory, and performing requested tasks
in their region.
D. Illustrative Simulation
The simulation in Fig. 3 shows four robots partitioning a
square environment with obstacles where the free space is
represented by a 12 × 12 grid. In the initial partition shown
in the left panel, the robot in the top right controls most of
the environment while the robot in the bottom left controls
very little. The robots then move according to the Random
Destination & Wait Motion Protocol, and communicate ac-
cording to range-limited gossip communication model with
rcomm = 2.5m (four edges in the graph).
The first pairwise territory exchange is shown in the second
panel, where the bottom left robot claims some territory from
the robot on the top left. A later exchange between the two
robots on the top is shown in the next two panels. Notice
that the cyan robot in the top right gives away the vertex it
currently occupies. In such a scenario, we direct the robot to
follow the shortest path in G(Q) to its updated territory before
continuing on to a random destination.
After 9 pairwise territory exchanges, the robots reach the
pairwise-optimal partition shown at right in Fig. 3. The ex-
pected distance between a random vertex and the closest robot
decreases from 2.34m down to 1.74m.
E. Convergence Property
The strength of the Discrete Gossip Coverage Algorithm is
the possibility of enforcing that a partition will converge to a
pairwise-optimal partition through pairwise territory exchange.
In Theorem 3.7 we summarize this convergence property, with
proofs given in Section IV.
Theorem 3.7 (Convergence Property): Consider a network
of N robotic agents endowed with computation and motion ca-
pacities (C1), (C2), (C3), and communication capacities (C4).
Assume the agents implement the Discrete Gossip Coverage
Algorithm consisting of the concurrent implementation of the
Random Destination & Wait Motion Protocol and the Pairwise
Partitioning Rule. Then,
(i) the partition P(t) remains connected and is described by
P : R≥0 →PartN(Q), and
(ii) P(t) converges almost surely in finite time to a pairwise-
optimal partition.
Remark 3.8 (Optimality of Solutions): By
definition,
a
pairwise-optimal partition is optimal in that Hexpected can not
be improved by changing only two regions in the partition.
Remark 3.9 (Generalizations): For simplicity we assume
uniform robot speeds, communication processes, and wait-
ing times. An extension to non-uniform processes would be
straightforward.
F. Complexity Properties and Discussion
In this subsection we explore the computational require-
ments of the Discrete Gossip Coverage Algorithm, and make
some comments on implementation. Cost function Hone(h; Pi)
is the sum of the distances between h and all other vertices
in Pi. This computation of one-to-all distances is the core
computation of the algorithm. For most graphs of interest the
total number of edges |E| is proportional to |Q|, so we will
state bounds on this computation in terms of |Pi|. Computing
one-to-all distances requires one of the following:
• if all edge weights in G(Q) are the same (e.g., for a graph
from an occupancy grid), a breadth-first search approach
can be used which requires O(|Pi|) in time and memory;
• otherwise, Dijkstra’s algorithm must be used which re-
quires O(|Pi| log (|Pi|)) in time and O(|Pi|) in memory.
Let D(Pi) be the time to compute one-to-all distances in Pi,
then computing Hone(h; Pi) requires O(D(Pi)) in time.
Proposition 3.10 (Complexity Properties): The
motion
protocol requires O(|Pi|) in memory, and O(D(Pi)) in
computation time. The partitioning rule requires O(|Pi|+|Pj|)
in
communication bandwidth between
robots i
and
j,
O(|Pi| + |Pj|) in memory, and can run in any time.
Proof: We first prove the claims for the motion protocol.
Step 2 is the only non-trivial step and requires finding a
shortest path in Pi, which is equivalent to computing one-to-
all distances from the robot’s current vertex. Hence, it requires
O(D(Pi)) in time and O(Pi) in memory.
7
We now prove the claims for the partitioning rule. In step
1, robots i and j transmit their subgraphs to each other,
which requires O(|Pi| + |Pj|) in communication bandwidth.
For step 3, the robots determine U := Pi ∪Pj, which requires
O(|Pi|+|Pj|) in memory to store. Step 4 is the start of a loop
which executes O(|U|2) times, affecting the time complexity
of steps 5, 6 and 7. Step 5 requires two computations of
one-to-all distances in U which each take O(D(U)). Step 6
involves four computations of Hone over different subsets of U,
however those for Wa∗and Wb∗can be stored from previous
computation. Since Wa and Wb are strict subsets of U, step
5 takes longer than step 6. Step 7 is trivial, as is step 8. The
total time complexity of the loop is thus O(|U|2 D(U)).
However, the loop in steps 4-7 can be truncated after any
number of iterations. While it must run to completion to
guarantee that Wa∗and Wb∗are an optimal two-partition of
U, the loop is designed to return an intermediate sub-optimal
result if need be. If Pi and Pj change, then Hexpected will
decrease. Our convergence result will hold provided that all
elements of S are eventually checked if Pi and Pj do not
change. Thus, the partitioning rule can run in any time with
each iteration requiring O(D(U)).
All of the computation and communication requirements in
Proposition 3.10 are independent of the number of robots and
scale with the size of a robot’s partition, meaning the Discrete
Gossip Coverage Algorithm can easily scale up for large teams
of robots in large environments.
IV. CONVERGENCE PROOFS
This section is devoted to proving the two statements in
Theorem 3.7. The proof that the Pairwise Partitioning Rule
maps a connected N-partition into a connected N-partition is
straightforward. The proof of convergence is more involved
and is based on the application of Lemma A.1 in Appendix A
to the Discrete Gossip Coverage Algorithm. Lemma A.1
establishes strong convergence properties for a particular class
of set valued maps (set-valued maps are briefly reviewed in
Appendix A).
We start by proving that the Pairwise Partitioning Rule is
well-posed in the sense that it maintains a connected partition.
Proof of Theorem 3.7 statement (i): To prove the state-
ment we need to show that P(t+) satisfies points (i) through
(iv) of Definition 2.2. From the definition of the Pairwise
Partitioning Rule, we have that Pi(t+)∪Pj(t+) = Pi(t)∪Pj(t)
and Pi(t+) ∩Pj(t+) = ∅. Moreover, since a∗∈Pi(t+) and
b∗∈Pj(t+), it follows that Pi(t+) ̸= ∅and Pj(t+) ̸= ∅.
These observations imply the validity of points (i), (ii), and
(iii) for P(t+). Finally, we must show that Pi(t+) and Pj(t+)
are connected, i.e., P(t+) also satisfies point (iv). To do
so we show that, given x ∈Wa∗, any shortest path in
Pi(t) ∪Pj(t) connecting x to a∗completely belongs to Wa∗.
We proceed by contradiction. Let sx,a∗denote a shortest path
in Pi(t) ∪Pj(t) connecting x to a∗and let us assume that
there exists m ∈sx,a∗such that m ∈Wb∗. For m to be
in Wb∗means that dPi(t)∪Pj(t)(m, b∗) < dPi(t)∪Pj(t)(m, a∗).
This implies that
dPi∪Pj(x, b∗) ≤dPi∪Pj(m, b∗) + dPi∪Pj(x, m)
< dPi∪Pj(m, a∗) + dPi∪Pj(x, m)
= dPi∪Pj(x, a∗).
This is a contradiction for x ∈Wa∗. Similar considerations
hold for Wb∗.
The rest of this section is dedicated to proving convergence.
Our first step is to show that the evolution determined by
the Discrete Gossip Coverage Algorithm can be seen as a
set-valued map. To this end, for any pair of robots (i, j) ∈
{1, . . ., N}2, i ̸= j, we define the map Tij : PartN(Q) →
PartN(Q) by
Tij(P) = (P1, . . . , bPi, . . . , bPj, . . . , PN),
where bPi = Wa∗and bPj = Wb∗.
If at time t ∈R≥0 the pair (i, j) and no other pair of robots
perform an iteration of the Pairwise Partitioning Rule, then the
dynamical system on the space of partitions is described by
P(t+) = Tij (P(t)) .
(2)
We define the set-valued map T : PartN(Q) ⇒PartN(Q) as
T (P) = {Tij(P) | (i, j) ∈{1, . . . , N}2, i ̸= j}.
(3)
Observe that (2) can then be rewritten as P(t+) ∈T (P(t)).
The next two Propositions state facts whose validity is
ensured by Lemma B.1 of Appendix B which states a key
property of the Random Destination & Wait Motion Protocol.
Proposition 4.1 (Persistence of Exchanges): Consider
N
robots implementing the Discrete Gossip Coverage Algorithm.
Then, there almost surely exists an increasing sequence of
time instants {tk}k∈Z≥0 such that P(t+
k ) = Tij(P(tk)) for
some (i, j) ∈E(P(tk)).
Proof: The proof follows directly from Lemma B.1
which implies that the time between two consecutive pairwise
communications is almost surely finite.
The existence of time sequence {tk}k∈Z≥0 allows us to to
express the evolution generate by the Discrete Gossip Cover-
age Algorithm as a discrete time process. Let P(k) := P(tk)
and P(k + 1) := P(t+
k ), then
P(k + 1) ∈T (P(k))
where T : PartN(Q) ⇒PartN(Q) is defined as in (3).
Given k ∈Z≥0, let Ik denote the information which
completely characterizes the state of Discrete Gossip Coverage
Algorithm just after the k-th iteration of the partitioning rule,
i.e., at time t+
k−1. Specifically, Ik contains the information
related to the partition P(k), the positions of the robots at
t+
k−1, and whether each robot is in the waiting or moving state
at t+
k−1. The following result characterizes the probability that,
given Ik, the (k + 1)-th iteration of the partitioning rule is
governed by any of the maps Tij, (i, j) ∈E(P(k)).
Proposition 4.2 (Probability of Communication): Consider
a team of N robots with capacities (C1), (C2), (C3), and
(C4) implementing the Discrete Gossip Coverage Algorithm.
8
Then, there exists a real number ¯π ∈(0, 1), such that, for any
k ∈Z≥0 and (i, j) ∈E(P(k))
P [P(k + 1) = Tij(P(k)) | Ik] ≥¯π.
Proof: Assume that at time ¯t one pair of robots commu-
nicates. Given a pair (¯i, ¯j) ∈E(P(¯t)), we must find a lower
bound for the probability that (¯i, ¯j) is the communicating pair.
Since all the Poisson communication processes have the same
intensity, the distribution of the chance of communication
is uniform over the pairs which are “able to communicate,”
i.e., closer than rcomm to each other. Thus, we must only
show that (¯i, ¯j) has a positive probability of being able to
communicate at time ¯t, which is equivalent to showing that
(¯i, ¯j) is able to communicate for a positive fraction of time
with positive probability. The proof of Lemma B.1 implies that
with probability at least α/(1 −e−λcommτ) any pair in E(P(¯t))
is able to communicate for a fraction of time not smaller than
τ
∆, where α and ∆are defined in the proof of Lemma B.1.
Hence the result follows.
The property in Proposition 4.2 can also be formulated as
follows. Let σ : Z≥0 →

(i, j) ∈{1, . . . , N}2, i ̸= j
	
be the
stochastic process such that σ(k) is the communicating pair at
time k. Then, the sequence of pairs of robots performing the
partitioning rule at time instants {tk}k∈Z≥0 can be seen as a
realization of the process σ, which satisfies
P

σ(k + 1) = (i, j) | σ(k)

≥¯π
(4)
for all (i, j) ∈E(P(k)).
Next we show that the cost function decreases whenever the
application of T from (3) changes the territory partition. This
fact is a key ingredient to apply Lemma A.1.
Lemma 4.3 (Decreasing Cost Function): Let
P ∈PartN(Q) and let P + ∈T (P). If P + ̸= P, then
Hexpected(P +) < Hexpected(P).
Proof: Without loss of generality assume that (i, j) is the
pair executing the Pairwise Partitioning Rule. Then
Hexpected(P +) −Hexpected(P)
= Hone(Cd(P +
i ); P +
i ) + Hone(Cd(P +
j ); P +
j )
−Hone(Cd(Pi); Pi) −Hone(Cd(Pj); Pj).
According to the definition of the Pairwise Partitioning Rule
we have that if P +
i
̸= Pi, P +
j ̸= Pj, then
Hone(Cd(P +
i ); P +
i ) + Hone(Cd(P +
j ); P +
j )
≤Hone(a∗; P +
i ) + Hone(b∗; P +
j )
< Hone(Cd(Pi); Pi) + Hone(Cd(Pj); Pj)
from which the statement follows.
We now complete the proof of the main result, Theorem 3.7.
Proof of Theorem 3.7 statement (ii):
Note that the
algorithm evolves in a finite space of partitions, and by Theo-
rem 3.7 statement (i), the set PartN(Q) is strongly positively
invariant. This fact implies that assumption (i) of Lemma A.1
is satisfied. From Lemma 4.3 it follows that assumption (ii)
is also satisfied, with Hexpected playing the role of the function
U. Finally, the property in (4) is equivalent to the property
of persistent random switches stated in Assumption (iii) of
Lemma A.1, for the special case h = 1. Hence, we are in the
position to apply Lemma A.1 and conclude convergence in
finite-time to an element of the intersection of the equilibria
of the maps Tij, which by definition is the set of the pairwise-
optimal partitions.
V. EXPERIMENTAL METHODS & RESULTS
To demonstrate the utility and study practical issues of
the Discrete Gossip Coverage Algorithm, we implemented
it using the open-source Player/Stage robot control system
[23] and the Boost Graph Library (BGL) [24]. All results
presented here were generated using Player 2.1.1, Stage 2.1.1,
and BGL 1.34.1. To compute distances in uniform edge weight
graphs we extended the BGL breadth-first search routine with
a distance recorder event visitor.
A. Large-scale Simulation
To evaluate the performance of our gossip coverage al-
gorithm with larger teams, we tested 30 simulated robots
partitioning a map representing a 350m × 225m portion of
campus at the University of California at Santa Barbara. As
shown in Fig. 4, the robots are tasked with providing coverage
of the open space around some of the buildings on campus,
a space which includes a couple open quads, some narrower
passages between buildings, and a few dead-end spurs. For
this large environment the simulated robots are 2m on a side
and can move at 3.0 m
s . Each territory cell is 3m × 3m.
In this simulation we handle communication and partition-
ing as follows. The communication range is set to 30m (10
edges in the graph) with λcomm = 0.3 comm
s
. The robots wait
at their destination vertices for τ = 3.5s. This value for τ
was chosen so that on average one quarter of the robots are
waiting at any moment. Lower values of τ mean the robots
are moving more of the time and as a result more frequently
miss connections, while for higher τ the robots spend more
time stationary which also reduces the rate of convergence.
With the goal of improving communication, we implemented a
minor modification to the motion protocol: each robot picks its
random destination from the cells forming the open boundary1
of its territory. In our implementation, the full partitioning
loop may take 5 seconds for the largest initial territories in
Fig. 4. We chose to stop the loop after a quarter second for
this simulation to verify the anytime computation claim.
The 30 robots start clustered in the center of the map
between Engineering II and Broida Hall, and an initial Voronoi
partition is generated from these starting positions. This initial
partition is shown on the left in Fig. 4 with the robots
positioned at the centroids of their starting regions. The initial
partition has a cost of 37.1m. The team spends about 27
minutes moving and communicating according to the Dis-
crete Gossip Coverage Algorithm before settling on the final
partition on the right of Fig. 4. The coverage cost of the
final equilibrium improved by 54% to 17.1m. Visually, the
1The open boundary of Pi is the set of vertices in Pi which are adjacent
to at least one vertex owned by another agent.
9
Fig. 4.
Images of starting and final partitions for a simulation with 30 robots providing coverage of a portion of campus at UCSB.
0
5
10
15
20
25
30
15
20
25
30
35
40
g replacements
Time (minutes)
Total cost Hexpected
Fig. 5.
Graph of the cost Hexpected over time for the simulation in Fig. 4.
final partition is also dramatically more uniform than the
initial condition. This result demonstrates that the algorithm
is effective for large teams in large non-convex environments.
Fig. 5 shows the evolution of Hexpected during the simulation.
The largest cost improvements happen early when the robots
that own the large territories on the left and right of the map
communicate with neighbors with much smaller territories.
These big territory changes then propagate through the net-
work as the robots meet and are pushed and pulled towards a
lower cost partition.
B. Implementation Details
We conducted an experiment to test the algorithm using
three physical robots in our lab, augmented by six simulated
robots in a synthetic environment extending beyond the lab.
Our lab space is 11.3m on a side and is represented by the
upper left portion of the territory maps in Fig. 7. The territory
graph loops around a center island of desks. We extended
the lab space through three connections into a simulated
environment around the lab, producing a 15.9m × 15.9m
environment. The map of the environment was specified with
a 0.15m bitmap which we overlayed with a 0.6m resolution
occupancy grid representing the free territory for the robots to
cover. The result is a lattice-like graph with all edge weights
equal to 0.6m. The 0.6m resolution was chosen so that our
physical robots would fit easily inside a cell.
Additional details of our implementation are as follows.
Robot hardware: We use Erratic mobile robots from Videre
Design, as shown in Fig. 6. The vehicle platform has a roughly
PSfrag replacements
Rangefinder
Drive wheel
Computer
Rear caster
Fig. 6.
Erratic mobile robot with URG-04LX laser rangefinder.
square footprint (40cm × 37cm), with two differential drive
wheels and a single rear caster. Each robot carries an onboard
computer with a 1.8Ghz Core 2 Duo processor, 1 GB of
memory, and 802.11g wireless communication. For navigation
and localization, each robot is equipped with a Hokuyo URG-
04LX laser rangefinder. The rangefinder scans 683 points over
240◦at 10Hz with a range of 5.6 meters.
Experiment setup: Our mixed physical and virtual robot
experiments are run from a central computer which is attached
to a wireless router so it can communicate with the physical
robots. The central computer creates a simulated world using
Stage which mirrors and extends the real space in which the
physical robots operate. The central computer also simulates
the virtual members of the robot team. These virtual robots are
modeled off of our hardware: they are differential drive with
the same geometry as the Erratic platform and use simulated
Hokuyo URG-04LX rangefinders.
Localization: We use the amcl driver in Player which
implements Adaptive Monte-Carlo Localization [25]. The
physical robots are provided with a map of our lab with a
15cm resolution and told their starting pose within the map.
We set an initial pose standard deviation of 0.9m in position
and 12◦in orientation, and request localization updates using
50 of the sensor’s range measurements for each change of
2cm in position or 2◦in orientation reported by the robot’s
odometry system. We then use the most likely pose estimate
output by amcl as the location of the robot. For simplicity and
reduced computational demand, we allow the virtual robots
access to perfect localization information.
10
3
2
1
1
3
2
2
3
1
3
1
2
2
1
3
3
2
1
Fig. 7.
Each column contains a territory map and the corresponding overhead camera image for a step of the hardware-in-the-loop simulation. The position
of the camera in the environment is shown with a camera icon in the territory map. The physical robots are numbered 1, 2, and 3 and have the orange, blue,
and lime green partitions. Their positions in each territory map are indicated with numbered circles.
Motion Protocol: Each robot continuously executes the
Random Destination & Wait Motion Protocol, with navigation
handled by the snd driver in Player which implements Smooth
Nearness Diagram navigation [26]. For snd we set the robot
radius parameter to 22cm, obstacle avoidance distance to
0.7m, and maximum speeds to 0.4 m
s and 40
◦
s. The snd driver
is a local obstacle avoidance planner, so we feed it a series
of waypoints every couple meters along paths found in G(Q).
We consider a robot to have achieved its target location when
it is within 20cm and it will then wait for τ = 3.5s. For the
physical robots the motion protocol and navigation processes
run on board, while there are separate threads for each virtual
robot on the central computer.
Communication and Partitioning: As the robots move, a
central process monitors their positions and simulates the
range-limited gossip communication model between both real
and virtual robots. We set rcomm = 2.5m and λcomm =
0.3 comm
s
. These parameters were chosen so that the robots
would be likely to communicate when separated by at most
four edges, but would also sometimes not connect despite
being close. When this process determines two robots should
communicate, it informs the robots who then perform the
Pairwise Partitioning Rule. Our pairwise communication im-
plementation is blocking: if robot i is exchanging territory
with j, then it informs the match making process that it is
unavailable until the exchange is complete.
C. Hardware-in-the-Loop Simulation
The results of our experiment with three physical robots
and six simulated robots are shown in Figs. 7 and 8. The left
column in Fig. 7 shows the starting positions of the team of
robots, with the physical robots, labeled 1, 2, and 3, lined up
in a corner of the lab and the simulated robots arrayed around
them. The starting positions are used to generate the initial
Voronoi partition of the environment. The physical robots own
the orange, blue, and lime green territories in the upper left
quadrant. We chose this initial configuration to have a high
coverage cost, while ensuring that the physical robots will
remain in the lab as the partition evolves.
In the middle column, robots 1 and 2 have met along their
shared border and are exchanging territory. In the territory
map, the solid red line indicates 1 and 2 are communicating
and their updated territories are drawn with solid orange and
blue, respectively. The camera view confirms that the two
robots have met on the near side of the center island of desks.
The final partition at right in Fig. 7 is reached after 9 1
2
minutes. All of the robots are positioned at the centroids of
their final territories. The three physical robots have gone from
a cluster in one corner of the lab to a more even spread around
the space. Fig. 8 shows the evolution of the cost function
Hexpected as the experiment progresses, including the costs for
each robot. As expected, the total cost never increases and the
disparity of costs for the individual robots shrinks over time
until settling at a pairwise-optimal partition.
In this experiment the hardware challenges of sensor noise,
navigation, and uncertainty in position were efficiently han-
dled by the amcl and snd drivers. The coverage algorithm
assumed the role of a higher-level planner, taking in posi-
tion data from amcl and directing snd. By far the most
computationally demanding component was amcl, but the
position hypotheses from amcl are actually unnecessary: our
coverage algorithm only requires knowledge of the vertex
11
0
2
4
6
8
10
2
2.5
3
0
2
4
6
8
10
0
200
400
replacements
Time (minutes)
Robot costs (m)
Hexpected (m)
Fig. 8.
Evolution of cost functions during the experiment in Fig. 7. The total
cost Hexpected is shown above in black, while Hone for each robot is shown
below in the robot’s color.
a robot occupies. If a less intensive localization method is
available, the algorithm could run on robots with significantly
lower compute power.
D. Comparative analysis
In this subsection we present a numerical comparison of the
performance of the Discrete Gossip Coverage Algorithm and
the following two Lloyd-type algorithms.
Decentralized Lloyd Algorithm: This method is from [11]
and [9], we describe it here for convenience. At each discrete
time instant t ∈Z≥0, each robot i performs the following
tasks: (1) i transmits its position and receives the positions of
all adjacent robots; (2) i computes its Voronoi region Pi based
on the information received; and (3) i moves to Cd(Pi).
Gossip Lloyd Algorithm: This method is from [19]. It is
a gossip algorithm, and so we have used the same commu-
nication model and the Random Destination & Wait Motion
Protocol to create meetings between robots. Say robots i and j
meet at time t, then the pairwise Lloyd partitioning rule works
as follows: (1) robot i transmits Pi(t) to j and vice versa; (2)
both robots determine U = Pi(t) ∪Pj(t); (3) robot i sets
Pi(t+) to be its Voronoi region of U based on Cd(Pi(t)) and
Cd(Pj(t)), and j does the equivalent.
For both Lloyd algorithms we use the same tie breaking rule
when creating Voronoi regions as is present in the Pairwise
Partitioning Rule: ties go to the robot with the lowest index.
Our first numerical result uses a Monte Carlo probability
estimation method from [27] to place probabilistic bounds on
the performance of the two gossip algorithms. Recall that the
Chernoff bound describes the minimum number of random
samples K required to reach a certain level of accuracy in a
probability estimate from independent Bernoulli tests. For an
accuracy ǫ ∈(0, 1) and confidence 1 −η ∈(0, 1), the number
of samples is given by K ≥
1
2ǫ2 log 2
η. For η = 0.01 and
ǫ = 0.1, at least 116 samples are required.
Figure 9 shows both the initial territory partition of the
extended laboratory environment used and also a histogram
2
2.2
2.4
2.6
2.8
3
0
50
100
PSfrag replacements
Final cost (m)
Simulation count
Fig. 9.
Initial partition and histogram of final costs for a Monte Carlo
test comparing the Discrete Gossip Coverage Algorithm (black bars), Gossip
Lloyd Algorithm (gray bars), and Decentralized Lloyd Algorithm (red dashed
line). For the gossip algorithms, 116 simulations were performed with different
sequences of pairwise communications. The Decentralized Lloyd Algorithm
is deterministic given an initial condition so only one final cost is shown.
of the final results for the following Monte Carlo test. The
environment and robot motion models used are described in
Section V-B. Starting from the indicated initial condition, we
ran 116 simulations of both gossip algorithms. The random-
ness in the test comes from the sequence of pairwise com-
munications. These sequences were generated using: (1) the
Random Destination & Wait Motion Protocol with qi sampled
uniformly from the open boundary of Pi and τ = 3.5s;
and (2) the range-limited gossip communication model with
rcomm = 2.5m and λcomm = 0.3 comm
s
.
The cost of the initial partition in Fig. 9 is 5.48m, while
the best known partition for this environment has a cost of
just under 2.18m. The histogram in Fig. 9 shows the final
equilibrium costs for 116 simulations of the Discrete Gossip
Coverage Algorithm (black) and the Gossip Lloyd Algorithm
(gray). It also shows the final cost using the Decentralized
Lloyd Algorithm (red dashed line), which is deterministic
from a given initial condition. The histogram bins have a
width of 0.10m and start from 2.17m. For the Discrete
Gossip Coverage Algorithm, 105 out of 116 trials reach
the bin containing the best known partition and the mean
final cost is 2.23m. The Gossip Lloyd Algorithm reaches
the lowest bin in only 5 of 116 trials and has a mean final
cost of 2.51m. The Decentralized Lloyd Algorithm settles
at 2.48m. Our new gossip algorithm requires an average of
12
replacements
Final cost (m)
Simulation count
Fig. 10.
Histograms of final costs from 10 Monte Carlo tests using
random initial conditions in the environment shown in Fig. 9 comparing
Discrete Gossip Coverage Algorithm (black bars), Gossip Lloyd Algorithm
(gray bars), and Decentralized Lloyd Algorithm (red dashed line). For the
gossip algorithms, 116 simulations were performed with different sequences of
pairwise communications. The Decentralized Lloyd Algorithm is deterministic
given an initial condition so only one final cost is shown. The initial cost for
each test is drawn with the green dashed line.
96 pairwise communications to reach an equilibrium, whereas
gossip Lloyd requires 126.
Based on these results, we can conclude with 99% confi-
dence that there is at least an 80% probability that 9 robots
executing the Discrete Gossip Coverage Algorithm starting
from the initial partition shown in Fig. 9 will reach a pairwise-
optimal partition which has a cost within 4% of the best known
cost. We can further conclude with 99% confidence that the
Gossip Lloyd Algorithm will settle more than 4% above the
best known cost at least 86% of the time starting from this
initial condition.
Figure 10 compares final cost histograms for 10 different
initial conditions for the same environment and parameters
as described above. Each initial condition was created by
selecting unique starting locations for the robots uniformly
at random and using these locations to generate an initial
Voronoi partition. The initial cost for each test is shown with
the green dashed line. In 9 out of 10 tests the Discrete Gossip
Coverage Algorithm reaches the histogram bin with the best
known partition in at least 112 of 116 trials. The two Lloyd
methods get stuck in sub-optimal centroidal Voronoi partitions
more than 4% away from the best known partition in more than
half the trials in 7 of 10 tests.
VI. CONCLUSION
We have presented a novel distributed partitioning and cov-
erage control algorithm which requires only unreliable short-
range communication between pairs of robots and works in
non-convex environments. The classic Lloyd approach to cov-
erage optimization involves iteration of separate centering and
Voronoi partitioning steps. For gossip algorithms, however,
this separation is unnecessary computationally and we have
shown that improved performance can be achieved without
it. Our new Discrete Gossip Coverage Algorithm provably
converges to a subset of the set of centroidal Voronoi par-
titions which we labeled pairwise-optimal partitions. Through
numerical comparisons we demonstrated that this new subset
of solutions avoids many of the local minima in which Lloyd-
type algorithms can get stuck.
Our vision is that this partitioning and coverage algorithm
will form the foundation of a distributed task servicing setup
for teams of mobile robots. The robots would split their time
between servicing tasks in their territory and moving to contact
their neighbors and improve the coverage of the space. Our
convergence results only require sporadic improvements to
the cost function, affording flexibility in robot behaviors and
capacities, and offering the ability to handle heterogeneous
robotic networks. In the bigger picture, this paper demonstrates
the potential of gossip communication in distributed coordi-
nation algorithms. There appear to be many other problems
where this realistic and minimal communication model could
be fruitfully applied.
APPENDIX A
For completeness we present a convergence result for set-
valued algorithms on finite state spaces, which can be recov-
ered as a direct consequence of [18, Theorem 4.5].
Given a set X, a set-valued map T : X ⇒X is a map
which associates to an element x ∈X a subset Z ⊂X. A
set-valued map is non-empty if T (x) ̸= ∅for all x ∈X. Given
a non-empty set-valued map T , an evolution of the dynamical
system associated to T is a sequence {xn}n∈Z≥0 ⊂X where
xn+1 ∈T (xn) for all n ∈Z≥0. A set W ⊂X is strongly
positively invariant for T if T (w) ⊂W for all w ∈W.
Lemma A.1 (Persistent random switches imply convergence):
Let (X, d) be a finite metric space. Given a collection of maps
T1, . . . , Tm : X →X, define the set-valued map T : X ⇒X
by T (x) = {T1(x), . . . , Tm(x)}. Given a stochastic process
σ : Z≥0 →{1, . . . , m}, consider an evolution {xn}n∈Z≥0 of
T satisfying xn+1 = Tσ(n)(xn). Assume that:
13
(i) there exists a set W ⊆X that is strongly positively
invariant for T ;
(ii) there exists a function U : W →R such that U(w′) <
U(w), for all w ∈W and w′ ∈T (w) \ {w}; and
(iii) there exist p ∈(0, 1) and k ∈N such that, for all i ∈
{1, . . . , m} and n ∈Z≥0, there exists h ∈{1, . . . , k}
such that P

σ(n + h) = i | σ(n), . . . , σ(1)

≥p.
For i ∈{1, . . . , m}, let Fi be the set of fixed points of Ti in
W, i.e., Fi = {w ∈W | Ti(w) = w}. If x0 ∈W, then the
evolution {xn}n∈Z≥0 converges almost surely in finite time to
an element of the set (F1 ∩· · · ∩Fm), i.e., there exists almost
surely τ ∈N such that, for some ¯x ∈(F1 ∩· · · ∩Fm), xn = ¯x
for n ≥τ.
APPENDIX B
This Appendix proves a property of the Random Destina-
tion & Wait Motion Protocol which is needed to show the
persistence of pairwise exchanges.
Lemma B.1: Consider N robots implementing the Dis-
crete Gossip Coverage Algorithm starting from an arbitrary
P ∈PartN(Q). Consider t ∈R≥0 and let P(t) denote the
partition at time t. Assume that at time t no two robots are
communicating. Then, there exist ∆> 0 and α ∈(0, 1),
independent of P(t) and the positions and states of the
robots at time t, such that, for every (i, j) ∈E(P(t)),
P [(i, j) communicate within (t, t + ∆)] ≥α.
Proof: To begin, we define two useful quantities. Let
S(Q)
:=
max
P ∈PartN (Q) max
Pi∈P max
h,k∈Pi dPi(h, k) be a pseudo-
diameter for Q, and then choose ∆:= 2 S(Q)
v
+ 2τ. We fix a
pair (i, j) ∈E(P), and pick adjacent vertices a ∈Pi, b ∈Pj.
Our goal is to lower bound the probability that i and j
will communicate within the interval (t, t + ∆). To do so
we construct one sequence of events of positive probability
which enables such communication. Consider the following
situation: i is in the moving state and needs time ti to reach
its destination qi, whereas robot j is in the waiting state at
vertex qj and must wait there for time τj ≤τ. We denote
by t(a) (resp. t(b)) the time needed for i (resp. j) to travel
from qi (resp. qj) to a (resp. b). Let Ei be the event such
that i performs the following actions in (t, t + ∆) without
communicating with any robot k ̸= j:
(i) i reaches qi and waits at qi for the duration τ; and
(ii) i chooses vertex a as its next destination and then stays
at a for at least ∆−t(a) −ti −τ.
Let Ej be the event such that j performs the following actions
in (t, t + ∆) without communicating with any k ̸= i:
(i) j waits at qj for the duration τj; and
(ii) j chooses vertex b as its next destination and then stays
at b for at least ∆−t(b) −τj.
Let Eij = Ei ∩Ej.
Next, we lower bound the probability that event Ei occurs.
Recall the definition of λcomm from Sec. III-A. Since a robot
can have at most N −1 neighbors, the probability that (i)
of Ei happens is lower bounded by e−λcommτN. For (ii), the
probability that i chooses a is 1/ |Pi|, which is lower bounded
by 1/ |Q|. Then, in order to spend at least (∆−t(a) −ti −τ)
at a, i must choose a for ⌈∆−t(a)−ti−τ
τ
⌉consecutive times.
Finally, the probability that during this interval i will not
communicate with any robot other than j is lower bounded by
e−λcomm∆(N−2). The probability that (ii) occurs is thus lower
bounded by (1/ |Q|)⌈∆
τ ⌉e−λcomm∆N. Combining the bounds for
(i) and (ii), it follows that
P[Ei] ≥
 1
|Q|

⌈∆
τ ⌉e−λcomm(∆+τ)N.
The same lower bound holds for P[Ej], meaning that
P [Eij] = P [Ei] P [Ej] ≥
 1
|Q|

2⌈∆
τ ⌉e−2λcomm(∆+τ)N.
If event Eij occurs, then robots i and j will be at adjacent
vertices for an amount of time during the interval (t, t + ∆)
equal to min {∆−t(a) −ti −τ, ∆−t(b) −τj} . Since t(a)
and t(b) are no more than
S(Q)
v
, we can conclude that i
and j will be within rcomm for at least τ. Conditioned on
Eij occurring, the probability that i and j communicate in
(t, t+∆) is lower bounded by 1−e−λcommτ. A suitable choice
for α from the statement of the Lemma is thus
α =
 1
|Q|

2⌈∆
τ ⌉e−2λcomm(∆+τ)N 1 −e−λcommτ

.
It can be shown that this also constitutes a lower bound for the
other possible combinations of initial states: robot i is waiting
and robot j is moving; robots i and j are both moving; and
robots i and j are both waiting.
APPENDIX C
In this appendix we provide the proof of Proposition 2.8
which states that any pairwise-optimal partition is also a
centroidal Voronoi partition.
Proof of Proposition 2.8:
To create a contradiction,
assume that P ∈PartN(Q) is a pairwise-optimal partition
but not a centroidal Voronoi partition. In other words, there
exist components Pi and Pj in P and an element x of one
component, say x ∈Pi, such that
dG (x, Cd(Pi)) > dG (x, Cd(Pj)) .
(5)
Choose Pj such that for all k ̸= j
dG (x, Cd(Pk)) ≥dG (x, Cd(Pj)) .
(6)
Let sG
a,b be a shortest path in G connecting a to b and let
m ∈sG
x,Cd(Pj) be the first element of the path starting from
Cd(Pj) which is not in Pj. Let ℓbe such that m ∈Pℓ.
If m = x, then from (5) and the definition of sG
x,Cd(Pj) we
have that
dPi (x, Cd(Pi)) ≥dG (x, Cd(Pi))
> dG (x, Cd(Pi)) = dPi∪Pj (x, Cd(Pj))
which, since x ∈Pi, creates a contradiction of the fact that P
is pairwise-optimal.
If m ̸= x, then, given (6), one of these two conditions holds:
(i) dG (m, Cd(Pℓ)) > dG (m, Cd(Pj)), or
(ii) dG (m, Cd(Pℓ)) = dG (m, Cd(Pj)).
In the first case, we again have a contradiction using the same
logic above with m in place of x. In the second case, we
14
must further consider whether there exists a sG
m,Cd(Pℓ) such
that every vertex in sG
m,Cd(Pℓ) is also in Pℓ. If there is not
such a path, then
dPℓ(m, Cd(Pℓ)) > dG (m, Cd(Pℓ)) = dPℓ∪Pj (m, Cd(Pj))
and we again have a contradiction as above. If there is such a
path, then we can instead repeat this analysis using using ℓin
place of j and considering the path formed by this sG
m,Cd(Pℓ)
and the vertices in sG
x,Cd(Pj) after m. Since the next vertex
playing the role of m must be closer to x, we will eventually
find a vertex which creates a contradiction.
REFERENCES
[1] R. Smith, J. Das, H. Heidarsson, A. Pereira, F. Arrichiello, I. Cetnic,
L. Darjany, M.-E. Garneau, M. Howard, C. Oberg, M. Ragan, E. Seubert,
E. Smith, B. Stauffer, A. Schnetzer, G. Toro-Farmer, D. Caron, B. Jones,
and G. Sukhatme, “USC CINAPS builds bridges,” IEEE Robotics &
Automation Magazine, vol. 17, no. 1, pp. 20–30, 2010.
[2] P. R. Wurman, R. D’Andrea, and M. Mountz, “Coordinating hundreds of
cooperative, autonomous vehicles in warehouses,” AI Magazine, vol. 29,
no. 1, pp. 9–20, 2008.
[3] S. Yun, M. Schwager, and D. Rus, “Coordinating construction of truss
structures using distributed equal-mass partitioning,” in International
Symposium on Robotics Research, (Lucerne, Switzerland), Aug. 2009.
[4] F. Bullo, E. Frazzoli, M. Pavone, K. Savla, and S. L. Smith, “Dynamic
vehicle routing for robotic systems,” Proceedings of the IEEE, vol. 99,
no. 9, pp. 1482–1504, 2011.
[5] A. K. Jain, M. N. Murty, and P. J. Flynn, “Data clustering: A review,”
ACM Computing Surveys, vol. 31, no. 3, pp. 264–323, 1999.
[6] V. V. Vazirani, Approximation Algorithms. Springer, 2001.
[7] P. O. Fj¨allstr¨om, “Algorithms for graph partitioning:
A survey,”
Link¨oping Electronic Articles in Computer and Information Science,
vol. 3, no. 10, 1998.
[8] F. R. Adler and D. M. Gordon, “Optimization, conflict, and nonover-
lapping foraging ranges in ants,” American Naturalist, vol. 162, no. 5,
pp. 529–543, 2003.
[9] F. Bullo, J. Cort´es, and S. Mart´ınez, Distributed Control of Robotic
Networks.
Applied Mathematics Series, Princeton University Press,
2009. Available at http://www.coordinationbook.info.
[10] S. P. Lloyd, “Least squares quantization in PCM,” IEEE Transactions
on Information Theory, vol. 28, no. 2, pp. 129–137, 1982. Presented at
the 1957 Institute for Mathematical Statistics Meeting.
[11] J. Cort´es, S. Mart´ınez, T. Karatas, and F. Bullo, “Coverage control
for mobile sensing networks,” IEEE Transactions on Robotics and
Automation, vol. 20, no. 2, pp. 243–255, 2004.
[12] M. Zhong and C. G. Cassandras, “Distributed coverage control in
sensor network environments with polygonal obstacles,” in IFAC World
Congress, (Seoul, Korea), pp. 4162–4167, July 2008.
[13] L. C. A. Pimenta, V. Kumar, R. C. Mesquita, and G. A. S. Pereira,
“Sensing and coverage for a network of heterogeneous robots,” in IEEE
Conf. on Decision and Control, (Canc´un, M´exico), pp. 3947–3952, Dec.
2008.
[14] M. Schwager, D. Rus, and J. J. Slotine, “Decentralized, adaptive cov-
erage control for networked robots,” International Journal of Robotics
Research, vol. 28, no. 3, pp. 357–375, 2009.
[15] R. Cortez, H. Tanner, and R. Lumia, “Distributed robotic radiation map-
ping,” in Experimental Robotics (O. Khatib, V. Kumar, and G. Pappas,
eds.), vol. 54 of Springer Tracts in Advanced Robotics, pp. 147–156,
Springer, 2009.
[16] O. Baron, O. Berman, D. Krass, and Q. Wang, “The equitable location
problem on the plane,” European Journal of Operational Research,
vol. 183, no. 2, pp. 578–590, 2007.
[17] M. B. Dias, R. Zlot, N. Kalra, and A. Stentz, “Market-based multirobot
coordination: A survey and analysis,” Proceedings of the IEEE, vol. 94,
no. 7, pp. 1257–1270, 2006.
[18] F. Bullo, R. Carli, and P. Frasca, “Gossip coverage control for robotic
networks: Dynamical systems on the the space of partitions,” SIAM
Journal on Control and Optimization, Aug. 2010. Submitted. Available
at http://motion.me.ucsb.edu/pdf/2008u-bcf.pdf.
[19] J. W. Durham, R. Carli, P. Frasca, and F. Bullo, “Discrete partitioning
and coverage control with gossip communication,” in ASME Dynamic
Systems and Control Conference, (Hollywood, CA, USA), pp. 225–232,
Oct. 2009.
[20] J. W. Durham, R. Carli, and F. Bullo, “Pairwise optimal coverage control
for robotic networks in discretized environments,” in IEEE Conf. on
Decision and Control, (Atlanta, GA, USA), pp. 7286–7291, Dec. 2010.
[21] H. Minc, Nonnegative Matrices. Wiley, 1988.
[22] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Computational Geometry: Algorithms and Applications. Springer, 2 ed.,
2000.
[23] B. Gerkey, R. T. Vaughan, and A. Howard, “The Player/Stage Project:
Tools for multi-robot and distributed sensor systems,” in Int. Conference
on Advanced Robotics, (Coimbra, Portugal), pp. 317–323, June 2003.
[24] J. G. Siek, L.-Q. Lee, and A. Lumsdaine, “Boost Graph Library.”
http://www.boost.org, July 2007. Version 1.34.1.
[25] S. Thrun, D. Fox, W. Burgard, and F. Dellaert, “Robust Monte Carlo
localization for mobile robots,” Artificial Intelligence, vol. 128, no. 1-2,
pp. 99–141, 2001.
[26] J. W. Durham and F. Bullo, “Smooth nearness-diagram navigation,” in
IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, (Nice, France),
pp. 690–695, Sept. 2008.
[27] R. Tempo, G. Calafiore, and F. Dabbene, Randomized Algorithms for
Analysis and Control of Uncertain Systems. Springer, 2005.