A Caltech Library Service

Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks

Pavone, Marco and Arsie, Alessandro and Frazzoli, Emilio and Bullo, Francesco (2011) Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks. IEEE Transactions on Automatic Control, 56 (8). pp. 1834-1848. ISSN 0018-9286.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


A widely applied strategy for workload sharing is to equalize the workload assigned to each resource. In mobile multiagent systems, this principle directly leads to equitable partitioning policies whereby: 1) the environment is equitably divided into subregions of equal measure; 2) one agent is assigned to each subregion; and 3) each agent is responsible for service requests originating within its own subregion. The current lack of distributed algorithms for the computation of equitable partitions limits the applicability of equitable partitioning policies to limited-size multiagent systems operating in known, static environments. In this paper, first we design provably correct and spatially distributed algorithms that allow a team of agents to compute a convex and equitable partition of a convex environment. Second, we discuss how these algorithms can be extended so that a team of agents can compute, in a spatially distributed fashion, convex and equitable partitions with additional features, e.g., equitable and median Voronoi diagrams. Finally, we discuss two application domains for our algorithms, namely dynamic vehicle routing for mobile robotic networks and wireless ad hoc networks. Through these examples, we show how one can couple the algorithms presented in this paper with equitable partitioning policies to make these amenable to distributed implementation. More in general, we illustrate a systematic approach to devise spatially distributed control policies for a large variety of multiagent coordination problems. Our approach is related to the classic Lloyd algorithm and exploits the unique features of power diagrams.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2011 IEEE. Manuscript received October 05, 2010; revised December 06, 2010; accepted January 28, 2011. Date of publication February 07, 2011; date of current version August 03, 2011. This work was supported in part by the National Science Foundation under Grants #0705451 and #0705453 and the Office of Naval Research under Grant N00014-07-1-0721. Recommended by Associate Editor M. Egerstedt.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-07-1-0721
Subject Keywords:Autonomous systems; cooperative control; decentralized control; multirobot systems; sensor networks
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number12205230
Issue or Number:8
Record Number:CaltechAUTHORS:20120124-111427134
Persistent URL:
Official Citation:Pavone, M.; Arsie, A.; Frazzoli, E.; Bullo, F.; , "Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks," Automatic Control, IEEE Transactions on , vol.56, no.8, pp.1834-1848, Aug. 2011 doi: 10.1109/TAC.2011.2112410
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:28941
Deposited By: Jason Perez
Deposited On:24 Jan 2012 20:57
Last Modified:03 Oct 2019 03:36

Repository Staff Only: item control page