Discrete Partitioning and Coverage Control for Gossiping Robots
- 1 April 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics
- Vol. 28 (2) , 364-378
Abstract
We propose distributed algorithms to automatically deploy a team of mobile robots to partition and provide coverage of a nonconvex environment. To handle arbitrary nonconvex 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, our algorithm is an "anytime algorithm'' that also scales well for large teams and can be run by on-board computers with limited resources. Finally, we report on large-scale simulations in complex environments and hardware experiments using the Player/Stage robot control system.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- USC CINAPS Builds BridgesIEEE Robotics & Automation Magazine, 2010
- Decentralized, Adaptive Coverage Control for Networked RobotsThe International Journal of Robotics Research, 2009
- Discrete Partitioning and Coverage Control With Gossip Communication2009
- Smooth Nearness-Diagram Navigation2008
- The equitable location problem on the planeEuropean Journal of Operational Research, 2007
- Market-Based Multirobot Coordination: A Survey and AnalysisProceedings of the IEEE, 2006
- Coverage Control for Mobile Sensing NetworksIEEE Transactions on Robotics and Automation, 2004
- Optimization, Conflict, and Nonoverlapping Foraging Ranges in AntsThe American Naturalist, 2003
- Computational Geometry2000
- Data clusteringACM Computing Surveys, 1999