Carnegie Mellon University
Multi-Robot Coordination with Periodic Connectivity

Geoffrey Hollinger and Sanjiv Singh
IEEE International Conference on Robotics and Automation, May, 2010.

  • Adobe portable document format (pdf) (390KB)
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.

multi-robot coordination, networked robots

Associated Center(s) / Consortia: Field Robotics Center
Associated Project(s): EMBER
Number of pages: 6
Note: Accompanying video is available at:

Text Reference
Geoffrey Hollinger and Sanjiv Singh, "Multi-Robot Coordination with Periodic Connectivity," IEEE International Conference on Robotics and Automation, May, 2010.

BibTeX Reference
   author = "Geoffrey Hollinger and Sanjiv Singh",
   title = "Multi-Robot Coordination with Periodic Connectivity",
   booktitle = "IEEE International Conference on Robotics and Automation",
   month = "May",
   year = "2010",
   Notes = "Accompanying video is available at:"