Home/Multi-Robot Coordination with Periodic Connectivity

Multi-Robot Coordination with Periodic Connectivity

Geoffrey Hollinger and Sanjiv Singh
Conference Paper, Carnegie Mellon University, IEEE International Conference on Robotics and Automation, May, 2010

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


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.

BibTeX Reference
title = {Multi-Robot Coordination with Periodic Connectivity},
author = {Geoffrey Hollinger and Sanjiv Singh},
booktitle = {IEEE International Conference on Robotics and Automation},
keyword = {multi-robot coordination, networked robots},
notes = {Accompanying video is available at: http://www.frc.ri.cmu.edu/~gholling/home/pubs.html},
school = {Robotics Institute , Carnegie Mellon University},
month = {May},
year = {2010},
address = {Pittsburgh, PA},