Discrete Partitioning and Coverage Control for Gossiping Robots
| Autor: | Paolo Frasca, Ruggero Carli, Francesco Bullo, Joseph W. Durham |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
FOS: Computer and information sciences
0209 industrial biotechnology Theoretical computer science Computer science Computation 02 engineering and technology Systems and Control (eess.SY) Computer Science::Robotics Computer Science - Robotics 020901 industrial engineering & automation Gossip 0202 electrical engineering electronic engineering information engineering FOS: Electrical engineering electronic engineering information engineering FOS: Mathematics Electrical and Electronic Engineering Mathematics - Optimization and Control Mobile robot Partition (database) Computer Science Applications Control and Systems Engineering Distributed algorithm Optimization and Control (math.OC) Coverage control Computer Science - Systems and Control Robot 020201 artificial intelligence & image processing Pairwise comparison Robotics (cs.RO) |
| DOI: | 10.48550/arxiv.1011.1939 |
| Popis: | 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. Comment: 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 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|