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 commu- nication 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 plat- forms. The platforms range from 8 to 80 individual nodes, with a variety of sensing and computation capabilities.