Geometric Distributed Algorithms for Multi-Robot Coordination and Control

Project Summary:

This project will develop robust and practical distributed algorithms for control and coordination of multi-robot systems, with a rigorous theoretical underpinning. Current models of computation and control cannot adequately capture multi-robot systems at a level of abstraction that is both manageable and accurate. The project is part of a larger research effort to develop a new computation model for multi-robot systems, which integrates distributed processing with the physical properties of the system state. This project will study new models that combine aspects of robotics, distributed algorithms, and computational geometry. It will focus on the following key issues:

  1. Efficiently and robustly exploring an unknown environment, while performing application tasks. Problems here include helping victims in search-and-rescue operations or deactivating mines. The project will study trade-offs between completion time and fault-tolerance, and develop three novel exploration algorithms.
  2. Establishing and maintaining robust network connectivity. The project will develop a robust connectivity service for multi-robot systems. The service will be general-purpose and composable with existing algorithms.
  3. Algorithm correctness and performance in the presence of discrete failures. This will require combining ideas such as self-stabilization from distributed computing theory and ongoing error characterization from control theory, to define new metrics for the rate of discrete errors.
  4. Performance as related to geometric assumptions. The project will compare different assumptions about the information that is available to robots about their geometry and how this affects algorithm performance. Robots might measure their positions in a global coordinate system, or measure positions of nearby robots within a local coordinate system, or just measure distances to nearby robots.
  5. Performance as related to physical parameters such as robot mobility and communication bandwidth. The project will relate the computational performance of multi-robot algorithms to the physical parameters of the robots, such as robot speed and communication bandwidth. This will help us understand the performance potential of a robotic system.
  6. Experimental validation of all of the above on three different multi-robot platforms. The platforms range from 8 to 80 individual nodes, with a variety of sensing and computation capabilities.

Participants:

Nancy Lynch, James McLurkin, Alejandro Cornejo, Andrew Lynch, Elizabeth Fudge, Siegfried Bilstein, Majid Khabbazian, Fabian Kuhn, Ruy Ley-Wild, Calvin C Newport, Seth Gilbert

Publications:

  1. Alejandro Cornejo, Andrew Lynch, Elizabeth Fudge, Siegfried Bilstein, Majid Khabbazian and James McLurkin. Scale-Free Coordinates for Multi-Robot Systems with Bearing-only Sensors, International Journal of Robotics Research(IJRR ), To Appear, pdf.
  2. Alejandro Cornejo, Calvin C Newport Subha Gallakota, Jayanthi Rao, Thomas J Guili Prioritized Gossip in vehicular Networks, Journal of Ad-Hoc Networks, 2013 pdf.
  3. Alejandro Cornejo, Seth Gilbert, Calvin C Newport, Aggregation in Dynamic Networks, Principles of Distributed Computing (PODC 2012), July 2012 pdf.
  4. Alejandro Cornejo, Andrew Lynch, Elizabeth Fudge, Siegfried Bilstein, Majid Khabbazian and James McLurkin. Scale-Free Coordinates for Multi-Robot Systems with Bearing-only Sensors, Workshop on the Algorithmic Foundations of Robotics (WAFR 2012), June 2012, pdf.
  5. Mikhail V Volkov, Alejandro Cornejo, Nancy Lynch, Daniela RusEnvironment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration, Principles and Practice of Multi-Agent Systems (PRIMA 2011)), Sep 2011 pdf.
  6. Alejandro Cornejo and Nancy Lynch. Reliably Detecting Connectivity Using Local Graph Traits , International Conference On Principles Of Distributed Systems (OPODIS 2010), Dec 2010, pdf.
  7. Alejandro Cornejo and Nancy Lynch. Fault-Tolerance Through k-Connectivity, IEEE International Conference on Robotics and Automation (ICRA 2010): Workshop on Network Science and Systems Issues in Multi-Robot Autonomy, May 2010, pdf.
  8. Alejandro Cornejo and Nancy Lynch, Minimum Spanning Trees and Cone-Based Topology Control, Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC 2009), Aug 2009, pdf.
  9. Alejandro Cornejo, Ruy Ley-Wild, Fabian Kuhn and Nancy Lynch, Keeping Mobile Robot Swarms Connected, 23rd International Symposium on Distributed Computing (DISC 2009), Sep 2009, pdf.
  10. Alejandro Cornejo and Nancy Lynch, Connectivity Service for Mobile Ad-Hoc Networks, IEEE Self-Adaptive and Self-Organizing Systems (SASO 08): Spatial Computing Workshop, Oct 2008, pdf.