Discrete Partitioning and Coverage Control for Gossiping Robots

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.

Accepted to IEEE TRO. 14 double-column pages, 10 figures. v2 is a thorough revision of v1, including new algorithms and revised mathematical and simulation results

Cited by in corpus (5)

• Equitable Persistent Coverage of Non-Convex Environments with Graph-Based Planning
• A Coverage Control-based Idle Vehicle Rebalancing Approach for Autonomous Mobility-on-Demand Systems
• A Versatile Multi-Robot Monte Carlo Tree Search Planner for On-Line Coverage Path Planning
• Multi-Robot Gaussian Process Estimation and Coverage: A Deterministic Sequencing Algorithm and Regret Analysis
• Asynchronous and Dynamic Coverage Control Scheme for Persistent Surveillance Missions