Research Abstracts - 2007

Introduction

How do you coordinate the actions of 10,000 robots? Centralized control is not feasible for this many agents, so distributed algorithms must be used for coordination and information processing. How should these algorithms be designed? How can you predict the growth properties of an algorithm, or compute the number of robots needed for a particular application? How does one design the hardware and software needed to build these robots? And how can a user interact with such a system? These open questions are the focus of our research; if solutions to these problems can be found, they have many potential applications.

Imagine searching for survivors in a collapsed building after an earthquake. Humans are either too big to search inside the debris, or too weak to lift the rubble to effect a rescue, but a multi-robot system of ant-sized scouts and brontosaurus-sized excavators would be ideal. Imagine searching for fossils on Mars. A group of one thousand microrobots could survey a very large area, then request detailed analyses on promising discoveries from a more capable robot. Imagine looking for hot spots in a forest fire. A multi-robot system could explore the extinguished area, alerting fire fighters if they are at risk of a fire starting behind them. Imagine searching a building for an item of interest. A multi-robot system could start from a single location and disperse into the building, searching in all directions simultaneously to locate the object.

These scenarios are interesting because they all lend themselves to automation, but can be accomplished far better by multi-robot systems than by individual robots. These scenarios are hard because many open research problems lie between their solutions and the current state-of-the-art.

Overview

The key open problems for multi-robot systems can be divided into four areas: distributed algorithms, theoretical models of computation on groups of robots, systems engineering to bring the physical systems into reality, and human interfaces to multi-robot systems. First and foremost, this work requires a rigorous theoretical understanding of the distributed algorithms that produce group behaviors from the interactions among individual robots. This understanding is the critical component of the development path shown in Figure \ref{SwarmbotCallouts}b. Second, these algorithms must be based on a model that incorporates both the algorithmic and \emph{physical computation} performed on the system. Physical computation captures the notion that algorithmic performance in a multi-robot system is not just a function of software, but also depends on the robots' physical locations, mobility, and inter-robot communications. Third, multi-robot systems require specially engineered hardware, sensors, and actuators. Finally, human operators require a user interface for programming, debugging and data collection.

Traditional complexity measures of running time and memory usage do not completely describe algorithms running on multi-robot systems because they do not model physical computation. Multi-robot systems can often be more constrained by physical computation than by limitations in processor speed and memory. I propose four complexity measures for characterizing multi-robot distributed algorithms: accuracy, physical running time, communication complexity, and configuration complexity. Accuracy is similar to correctness in traditional algorithms, and measures how well the robots achieve the desired physical configuration. The physical running time of an algorithm must take into account the robot's velocity, the speed at which messages propagate throughout the network, and the complexity of the environment. Communication resources are used differently in a multi-robot system than in a sensor network or in multiprocessor distributed algorithms, so the communication complexity metric must consider the robots' communication range, available bandwidth between neighboring robots, and messaging rate needed to adapt to changing network topology. Multi-robot systems store algorithm state in the memory of the processors and in the intermediate physical configurations the group produces on the way to the desired configuration. This configuration complexity will help us quantify the minimum number of robots required for an algorithm, the amount of information stored in their configuration, and the algorithmic cost of storing and retrieving this information.

We are working to define these complexity metrics, use them to predict the performance of a library of multi-robot algorithms. In addition, we are augmenting our library of distributed algorithms to evaluate the utility of these metrics. The algorithms tested will range from simple behaviors, such as clustering, to complex applications, such as a depth-first search. The final result will be a library of distributed algorithms with well-characterized real-world performance characteristics.

Acknowledgements

This research is sponsored by Boeing Corporation.

References:

[1] Mac Schwager, James McLurkin, and Daniela Rus. Distributed Coverage Control with Sensory Feedback for Networked Robots: Human-Robot Interface Design for Large Swarms of Autonomous Mobile Robots. In The Proceedings of Robotics: Science and Systems, June, 2006.

[2] James McLurkin and Daniel Yamins. Dynamic Task Assignment in Robot Swarms. In The Proceedings of Robotics: Science and Systems, June 8, 2005.

[3] James McLurkin, Jennifer Smith, James Frankel, David Sotkowitz, David Blau, Brian Schmidt. Speaking Swarmish: Human-Robot Interface Design for Large Swarms of Autonomous Mobile Robots. In The Proceedings of AAAI Spring Symposium, March 28, 2006.