Discrete Partitioning and Coverage Control for Gossiping Robots

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 pairw...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on robotics 2012-04, Vol.28 (2), p.364-378
Main Authors: Durham, J. W., Carli, R., Frasca, P., Bullo, F.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Applied sciences
Artificial intelligence
Communication
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Control systems
Control theory. Systems
Convergence
Cost function
Distributed control
Exact sciences and technology
Heuristic algorithms
intelligent robots
multirobot systems
optimization
Partitioning algorithms
Protocols
Robotics
Robots
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1552-3098
1941-0468
DOI:10.1109/TRO.2011.2170753