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. I NTRODUCTION 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. P RELIMINARIES 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 w e > 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 d G ( 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, d G ( h, k ) = 0 if h = k . Note that d G ( h, k ) = d G ( 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 d I ( h, k ) := d G ∩ I ( h, k ) . Note that d I ( h, k ) ≥ d G ( h, k ) . We define a connected subset of Q as a subset A ⊂ Q such that A 6 = ∅ 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 = { P i } N i =1 of N subsets of Q such that (i) ⋃ N i =1 P i = Q ; (ii) P i ∩ P j = ∅ if i 6 = j ; (iii) P i 6 = ∅ for all i ∈ { 1 , . . . , N } ; and (iv) P i is connected for all i ∈ { 1 , . . . , N } . Let Part N ( Q ) to be the set of connected N − partitions of Q . Property (ii) implies that each element of Q belongs to just one P i , i.e., each location in the environment is covered by just one robot. Notice that each P i ∈ P induces a connected subgraph in G ( Q ) . In subsequent references to P i we will often mean G ∩ P i , and in fact we refer to P i ( 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 ∈ Q N , the partition P ∈ Part N ( Q ) is said to be a Voronoi partition of Q generated by c if, for each P i and all k ∈ P i , we have c i ∈ P i and d G ( k, c i ) ≤ d G ( k, c j ) , ∀ j 6 = 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 P i , P j are said to be adjacent if there are two vertices q i , q j belonging, respectively, to P i and P j such that ( q i , q j ) ∈ E . Observe that if P i and P j are adjacent then P i ∪ P j is connected. Similarly, we say that robots i and j are adjacent or are neighbors if their subgraphs P i and P j are adjacent. Accordingly, we introduce the following useful notion. Definition 2.3 (Adjacency Graph): For P ∈ Part N ( Q ) , we define the adjacency graph between regions of partition P as G ( P ) = ( { 1 , . . . , N } , E ( P )) , where ( i, j ) ∈ E ( P ) if P i and P j are adjacent. Note that G ( P ) is always connected since G ( Q ) is. D. Cost Functions We define three coverage cost functions for graphs: H one , H multicenter , and H expected . Let the weight function φ : Q → R > 0 assign a relative weight to each element of Q . The one-center function H one gives the cost for a robot to cover a connected subset A ⊂ Q from a vertex h ∈ A with relative prioritization set by φ : H one ( h ; A ) = ∑ k ∈ A d A ( h, k ) φ ( k ) . A technical assumption is needed to solve the problem of minimizing H one ( · , 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 H one 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 H one , i.e., C ( A ) := argmin h ∈ A H one ( 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 : Part N ( Q ) → Q N as the map which associates to a partition the vector of the centroids of its elements. We define the multicenter function H multicenter to measure the cost for N robots to cover a connected N -partition P from the vertex set c ∈ Q N : H multicenter ( c, P ) = 1 ∑ k ∈ Q φ ( k ) N ∑ i =1 H one ( c i ; P i ) . We aim to minimize the performance function H multicenter 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 H expected : Part N ( Q ) → R ≥ 0 be defined by H expected ( P ) = H multicenter ( 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 H expected , 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 ∈ Part N ( Q ) and c ∈ Q N . If P ′ is a Voronoi partition generated by c and c ′ ∈ Q n is such that c ′ i ∈ C ( P i ) ∀ i , then H multicenter ( c, P ′ ) ≤ H multicenter ( c, P ) , and H multicenter ( c ′ , P ) ≤ H multicenter ( c, P ) . The second inequality is strict if any c i / ∈ C ( P i ) . Proposition 2.5 implies the following necessary condition: if ( c, P ) minimizes H multicenter , then c i ∈ C ( P i ) ∀ i and P must be a Voronoi partition generated by c . Thus, H expected has the following property as an immediate consequence of Proposition 2.5: given P ∈ Part N ( Q ) , if P ∗ is a Voronoi partition generated by Cd ( P ) then H expected ( P ∗ ) ≤ H expected ( P ) . This fact motivates the following definition. Definition 2.6 (Centroidal Voronoi Partition): P ∈ Part N ( Q ) is a centroidal Voronoi partition of Q if there exists a c ∈ Q n such that P is a Voronoi partition generated by c and c i ∈ C ( P i ) ∀ 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 ∈ Part N ( Q ) is a pairwise-optimal partition if for every ( i, j ) ∈ E ( P ) , H one ( Cd ( P i ); P i ) + H one ( Cd ( P j ); P j ) = min a,b ∈ P i ∪ P j { ∑ k ∈ P i ∪ P j min { d P i ∪ P j ( a, k ) , d P i ∪ P j ( 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 ∈ Part N ( 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: H expected 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 . 2 w , (b) has a cost of 1 . 1 w , and (c) has a cost of 1 . 0 w . 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 P i ∪ P j 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. M ODELS , P ROBLEM F ORMULATION , AND P ROPOSED S OLUTION 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 r comm > max e ∈ E w e , when any two agents reside for some positive duration at a distance r < r comm , 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 < r comm . (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 P i ( t ) of environment Q . Our goal is to design a distributed algorithm that iteratively updates the partition P ( t ) = { P i ( t ) } N i =1 while solving the following optimization problem: min P ∈ Part N ( Q ) H expected ( 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 q i from a uniform distribution over its dominance subgraph P i ; 2: agent i moves to vertex q i through the shortest path in P i connecting the vertex it currently occupies and q i ; and 3: agent i waits at q i 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 q i from the boundary of P i or use some heuristic non-uniform distribution over P i . If any two agents i and j reside in two vertices at a graphical distance smaller that r comm 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 P i and P j 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 P i ( t ) and P j ( 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 P i ( t ) to agent j and vice-versa 2: initialize W a ∗ := P i ( t ) , W b ∗ := P j ( t ) , a ∗ := Cd ( P i ( t )) , b ∗ := Cd ( P j ( t )) 3: compute U := P i ( t ) ∪ P j ( t ) and an ordered list S of all pairs of vertices in U 4: for each ( a, b ) ∈ S do 5: compute the sets W a := { x ∈ U : d U ( x, a ) ≤ d U ( x, b ) } W b := { x ∈ U : d U ( x, a ) > d U ( x, b ) } 6: if H one ( a ; W a ) + H one ( b ; W b ) < H one ( a ∗ ; W a ∗ ) + H one ( b ∗ ; W b ∗ ) then 7: W a ∗ := W a , W b ∗ := W b , a ∗ := a, b ∗ := b 8: P i ( t + ) := W a ∗ , P j ( t + ) := W b ∗ 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 W a ∗ and W b ∗ for ( a ∗ , b ∗ ) ∈ S are defined as in the Pairwise Partitioning Rule, then W a ∗ and W b ∗ are an optimal two-partition of U . (2) While the loop in steps 4-7 must run to completion to guarantee that W a ∗ and W b ∗ are an optimal two-partition of U , the loop is designed to return an intermediate sub-optimal result if need be. If P i and P j change, then H expected 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 W a ∗ to i and W b ∗ 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 W a ∗ and W b ∗ 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 W a ∗ and W b ∗ will not change from P i ( t ) and P j ( 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, d U ( x, a ) could be replaced by the expected time for robot i to travel from a to x while d U ( 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 r comm = 2 . 5 m (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 . 34 m down to 1 . 74 m . 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 → Part N ( 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 H expected 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 H one ( h ; P i ) is the sum of the distances between h and all other vertices in P i . 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 | P i | . 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 ( | P i | ) in time and memory; • otherwise, Dijkstra’s algorithm must be used which re- quires O ( | P i | log ( | P i | )) in time and O ( | P i | ) in memory. Let D ( P i ) be the time to compute one-to-all distances in P i , then computing H one ( h ; P i ) requires O ( D ( P i )) in time. Proposition 3.10 (Complexity Properties): The motion protocol requires O ( | P i | ) in memory, and O ( D ( P i )) in computation time. The partitioning rule requires O ( | P i | + | P j | ) in communication bandwidth between robots i and j , O ( | P i | + | P j | ) 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 P i , which is equivalent to computing one-to- all distances from the robot’s current vertex. Hence, it requires O ( D ( P i )) in time and O ( P i ) 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 ( | P i | + | P j | ) in communication bandwidth. For step 3, the robots determine U := P i ∪ P j , which requires O ( | P i | + | P j | ) 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 H one over different subsets of U , however those for W a ∗ and W b ∗ can be stored from previous computation. Since W a and W b 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 W a ∗ and W b ∗ are an optimal two-partition of U , the loop is designed to return an intermediate sub-optimal result if need be. If P i and P j change, then H expected will decrease. Our convergence result will hold provided that all elements of S are eventually checked if P i and P j 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. C ONVERGENCE P ROOFS 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 P i ( t + ) ∪ P j ( t + ) = P i ( t ) ∪ P j ( t ) and P i ( t + ) ∩ P j ( t + ) = ∅ . Moreover, since a ∗ ∈ P i ( t + ) and b ∗ ∈ P j ( t + ) , it follows that P i ( t + ) 6 = ∅ and P j ( t + ) 6 = ∅ . These observations imply the validity of points (i), (ii), and (iii) for P ( t + ) . Finally, we must show that P i ( t + ) and P j ( t + ) are connected, i.e., P ( t + ) also satisfies point (iv). To do so we show that, given x ∈ W a ∗ , any shortest path in P i ( t ) ∪ P j ( t ) connecting x to a ∗ completely belongs to W a ∗ . We proceed by contradiction. Let s x,a ∗ denote a shortest path in P i ( t ) ∪ P j ( t ) connecting x to a ∗ and let us assume that there exists m ∈ s x,a ∗ such that m ∈ W b ∗ . For m to be in W b ∗ means that d P i ( t ) ∪ P j ( t ) ( m, b ∗ ) < d P i ( t ) ∪ P j ( t ) ( m, a ∗ ) . This implies that d P i ∪ P j ( x, b ∗ ) ≤ d P i ∪ P j ( m, b ∗ ) + d P i ∪ P j ( x, m ) < d P i ∪ P j ( m, a ∗ ) + d P i ∪ P j ( x, m ) = d P i ∪ P j ( x, a ∗ ) . This is a contradiction for x ∈ W a ∗ . Similar considerations hold for W b ∗ . 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 6 = j , we define the map T ij : Part N ( Q ) → Part N ( Q ) by T ij ( P ) = ( P 1 , . . . , ̂ P i , . . . , ̂ P j , . . . , P N ) , where ̂ P i = W a ∗ and ̂ P j = W b ∗ . 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 + ) = T ij ( P ( t )) . (2) We define the set-valued map T : Part N ( Q ) ⇒ Part N ( Q ) as T ( P ) = { T ij ( P ) | ( i, j ) ∈ { 1 , . . . , N } 2 , i 6 = 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 { t k } k ∈ Z ≥ 0 such that P ( t + k ) = T ij ( P ( t k )) for some ( i, j ) ∈ E ( P ( t k )) . 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 { t k } 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 ( t k ) and P ( k + 1) := P ( t + k ) , then P ( k + 1) ∈ T ( P ( k )) where T : Part N ( Q ) ⇒ Part N ( Q ) is defined as in (3). Given k ∈ Z ≥ 0 , let I k 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, I k 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 I k , the ( k + 1) -th iteration of the partitioning rule is governed by any of the maps T ij , ( 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) = T ij ( P ( k )) | I k ] ≥ ̄ π. 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 r comm 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 6 = 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 { t k } 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 ∈ Part N ( Q ) and let P + ∈ T ( P ) . If P + 6 = P , then H expected ( P + ) < H expected ( P ) . Proof: Without loss of generality assume that ( i, j ) is the pair executing the Pairwise Partitioning Rule. Then H expected ( P + ) − H expected ( P ) = H one ( Cd ( P + i ); P + i ) + H one ( Cd ( P + j ); P + j ) − H one ( Cd ( P i ); P i ) − H one ( Cd ( P j ); P j ) . According to the definition of the Pairwise Partitioning Rule we have that if P + i 6 = P i , P + j 6 = P j , then H one ( Cd ( P + i ); P + i ) + H one ( Cd ( P + j ); P + j ) ≤ H one ( a ∗ ; P + i ) + H one ( b ∗ ; P + j ) < H one ( Cd ( P i ); P i ) + H one ( Cd ( P j ); P j ) 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 Part N ( 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 H expected 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 T ij , which by definition is the set of the pairwise- optimal partitions. V. E XPERIMENTAL M ETHODS & R ESULTS 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 350 m × 225 m 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 2 m on a side and can move at 3 . 0 m s . Each territory cell is 3 m × 3 m . In this simulation we handle communication and partition- ing as follows. The communication range is set to 30 m (10 edges in the graph) with λ comm = 0 . 3 comm s . The robots wait at their destination vertices for τ = 3 . 5 s . 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 boundary 1 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 . 1 m . 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 . 1 m . Visually, the 1 The open boundary of P i is the set of vertices in P i 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 Time (minutes) Total cost H expected Fig. 5. Graph of the cost H expected 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 H expected 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 . 3 m 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 . 9 m × 15 . 9 m environment. The map of the environment was specified with a 0 . 15 m bitmap which we overlayed with a 0 . 6 m 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 . 6 m . The 0 . 6 m 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 (40 cm × 37 cm ) , 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 10 Hz 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 15 cm resolution and told their starting pose within the map. We set an initial pose standard deviation of 0 . 9 m in position and 12 ◦ in orientation, and request localization updates using 50 of the sensor’s range measurements for each change of 2 cm 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 22 cm , obstacle avoidance distance to 0 . 7 m , 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 20 cm and it will then wait for τ = 3 . 5 s . 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 r comm = 2 . 5 m 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 H expected 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 Time (minutes) Robot costs (m) H expected (m) Fig. 8. Evolution of cost functions during the experiment in Fig. 7. The total cost H expected is shown above in black, while H one 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 P i based on the information received; and (3) i moves to Cd ( P i ) . 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 P i ( t ) to j and vice versa; (2) both robots determine U = P i ( t ) ∪ P j ( t ) ; (3) robot i sets P i ( t + ) to be its Voronoi region of U based on Cd ( P i ( t )) and Cd ( P j ( 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 q i sampled uniformly from the open boundary of P i and τ = 3 . 5 s ; and (2) the range-limited gossip communication model with r comm = 2 . 5 m and λ comm = 0 . 3 comm s . The cost of the initial partition in Fig. 9 is 5 . 48 m , while the best known partition for this environment has a cost of just under 2 . 18 m . 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 . 10 m and start from 2 . 17 m . 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 . 23 m . The Gossip Lloyd Algorithm reaches the lowest bin in only 5 of 116 trials and has a mean final cost of 2 . 51 m . The Decentralized Lloyd Algorithm settles at 2 . 48 m . Our new gossip algorithm requires an average of
12 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. C ONCLUSION 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. A PPENDIX 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 ) 6 = ∅ for all x ∈ X . Given a non-empty set-valued map T , an evolution of the dynamical system associated to T is a sequence { x n } n ∈ Z ≥ 0 ⊂ X where x n +1 ∈ T ( x n ) 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 T 1 , . . . , T m : X → X , define the set-valued map T : X ⇒ X by T ( x ) = { T 1 ( x ) , . . . , T m ( x ) } . Given a stochastic process σ : Z ≥ 0 → { 1 , . . . , m } , consider an evolution { x n } n ∈ Z ≥ 0 of T satisfying x n +1 = T σ ( n ) ( x n ) . 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 F i be the set of fixed points of T i in W , i.e., F i = { w ∈ W | T i ( w ) = w } . If x 0 ∈ W , then the evolution { x n } n ∈ Z ≥ 0 converges almost surely in finite time to an element of the set ( F 1 ∩ · · · ∩ F m ) , i.e., there exists almost surely τ ∈ N such that, for some ̄ x ∈ ( F 1 ∩ · · · ∩ F m ) , x n = ̄ x for n ≥ τ. A PPENDIX 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 ∈ Part N ( 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 ∈ Part N ( Q ) max P i ∈ P max h,k ∈ P i d P i ( 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 ∈ P i , b ∈ P j . 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 t i to reach its destination q i , whereas robot j is in the waiting state at vertex q j 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 q i (resp. q j ) to a (resp. b ). Let E i be the event such that i performs the following actions in ( t, t + ∆) without communicating with any robot k 6 = j : (i) i reaches q i and waits at q i for the duration τ ; and (ii) i chooses vertex a as its next destination and then stays at a for at least ∆ − t ( a ) − t i − τ . Let E j be the event such that j performs the following actions in ( t, t + ∆) without communicating with any k 6 = i : (i) j waits at q j 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 E ij = E i ∩ E j . Next, we lower bound the probability that event E i 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 E i happens is lower bounded by e − λ comm τ N . For (ii), the probability that i chooses a is 1 / | P i | , which is lower bounded by 1 / | Q | . Then, in order to spend at least (∆ − t ( a ) − t i − τ ) at a , i must choose a for ⌈ ∆ − t ( a ) − t i − τ τ ⌉ 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 [ E i ] ≥ ( 1 | Q | ) ⌈ ∆ τ ⌉ e − λ comm (∆+ τ ) N . The same lower bound holds for P [ E j ] , meaning that P [ E ij ] = P [ E i ] P [ E j ] ≥ ( 1 | Q | ) 2 ⌈ ∆ τ ⌉ e − 2 λ comm (∆+ τ ) N . If event E ij 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 ) − t i − τ, ∆ − 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 r comm for at least τ . Conditioned on E ij 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 . A PPENDIX 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 ∈ Part N ( Q ) is a pairwise-optimal partition but not a centroidal Voronoi partition. In other words, there exist components P i and P j in P and an element x of one component, say x ∈ P i , such that d G ( x, Cd ( P i )) > d G ( x, Cd ( P j )) . (5) Choose P j such that for all k 6 = j d G ( x, Cd ( P k )) ≥ d G ( x, Cd ( P j )) . (6) Let s G a,b be a shortest path in G connecting a to b and let m ∈ s G x, Cd ( P j ) be the first element of the path starting from Cd ( P j ) which is not in P j . Let ℓ be such that m ∈ P ℓ . If m = x , then from (5) and the definition of s G x, Cd ( P j ) we have that d P i ( x, Cd ( P i )) ≥ d G ( x, Cd ( P i )) > d G ( x, Cd ( P i )) = d P i ∪ P j ( x, Cd ( P j )) which, since x ∈ P i , creates a contradiction of the fact that P is pairwise-optimal. If m 6 = x , then, given (6), one of these two conditions holds: (i) d G ( m, Cd ( P ℓ )) > d G ( m, Cd ( P j )) , or (ii) d G ( m, Cd ( P ℓ )) = d G ( m, Cd ( P j )) . 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 s G m, Cd ( P ℓ ) such that every vertex in s G m, Cd ( P ℓ ) is also in P ℓ . If there is not such a path, then d P ℓ ( m, Cd ( P ℓ )) > d G ( m, Cd ( P ℓ )) = d P ℓ ∪ P j ( m, Cd ( P j )) 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 s G m, Cd ( P ℓ ) and the vertices in s G x, Cd ( P j ) 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. R EFERENCES [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.