Computer Science – Robotics
Scientific paper
2010-11-08
Computer Science
Robotics
Accepted to IEEE TRO. 14 double-column pages, 10 figures. v2 is a thorough revision of v1, including new algorithms and revise
Scientific paper
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.
Bullo Francesco
Carli Ruggero
Durham Joseph W.
Frasca Paolo
No associations
LandOfFree
Discrete Partitioning and Coverage Control for Gossiping Robots does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Discrete Partitioning and Coverage Control for Gossiping Robots, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discrete Partitioning and Coverage Control for Gossiping Robots will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-492175