Distributed coverage with mobile robots on a graph: Locational optimization

This paper presents decentralized algorithms for coverage with mobile robots on a graph. Coverage is an important capability of multi-robot systems engaged in a number of different applications, including placement for environmental modeling, deployment for maximal quality surveillance, and even coordinated construction. We use distributed vertex substitution for locational optimization, and the controllers minimize the corresponding cost functions. We prove that the proposed controller with two-hop communication guarantees convergence to the locally optimal configuration. We evaluate the algorithms in simulations and compare them to the coverage algorithms in a continuous domain.

Authors

• Seung-kook Yun
• Daniela Rus

Keywords

• Partitioning algorithms
• Cost function
• Robot sensing systems
• Nickel
• Mobile robots
• Mobile Robot
• Multi-agent Systems
• Simulated Algorithm
• Continuous Domain
• Centroid
• Amount Of Change
• Finite Element Method
• Sensory Function
• Global Optimization
• Robotic System
• Nodes In The Graph
• Discrete Method
• Mesh Network
• Voronoi Diagram
• Graph Partitioning
• Position Of The Robot
• Robot Movement
• Decentralized Control
• Coverage Problem
• Robot Localization
• Environmental Classification
• Swarm Robotics
• Optimal Node