Multi-Robot Coordination with Periodic Connectivity - Robotics Institute Carnegie Mellon University

Multi-Robot Coordination with Periodic Connectivity

Conference Paper, Proceedings of (ICRA) International Conference on Robotics and Automation, pp. 4457 - 4462, May, 2010

Abstract

We consider the problem of multi-robot coordination subject to constraints on the configuration. Specifically, we examine the case in which a mobile network of robots must search, survey, or cover an environment while remaining connected. While many algorithms utilize continual connectivity for such tasks, we relax this requirement and introduce the idea of periodic connectivity, where the network must regain connectivity at a fixed interval. We show that, in some cases, this problem reduces to the well-studied NP-hard multi-robot informative path planning (MIPP) problem, and we propose an online algorithm that scales linearly in the number of robots and allows for arbitrary periodic connectivity constraints. We prove theoretical performance guarantees and validate our approach in the coordinated search domain in simulation and in real-world experiments. Our proposed algorithm significantly outperforms a gradient method that requires continual connectivity and performs competitively with a market-based approach, but at a fraction of the computational cost.

Notes
Accompanying video is available at: http://www.frc.ri.cmu.edu/~gholling/home/pubs.html

BibTeX

@conference{Hollinger-2010-10434,
author = {Geoffrey Hollinger and Sanjiv Singh},
title = {Multi-Robot Coordination with Periodic Connectivity},
booktitle = {Proceedings of (ICRA) International Conference on Robotics and Automation},
year = {2010},
month = {May},
pages = {4457 - 4462},
keywords = {multi-robot coordination, networked robots},
}