The objective of this research is to develop new models of computation for multi-robot systems. Algorithm execution proceeds in a cycle of communication, computation, and motion. Computation is inextricably linked to the physical configuration of the system. Current models cannot describe multi-robot systems at a level of abstraction that is both manageable and accurate. This project will combine ideas from distributed algorithms, computational geometry, and control theory to design new models for multi-robot systems that incorporate physical properties of the systems. The approach is to focus on the high-level problem of exploring an unknown environment while performing designated tasks, and the sub-problem of maintaining network connectivity. Key issues to be studied will include algorithmic techniques for handling ongoing discrete failures, and ways of understanding system capabilities as related to failure rates, geometric assumptions and physical parameters such as robot mobility and communication bandwidth. New metrics will be developed for error rates and robot mobility.
Intellectual merit arises from the combination of techniques from distributed algorithms, computational geometry, and control theory to develop and analyze algorithms for multi-robot systems. The project will develop a new class of algorithms and techniques for their rigorous analysis, not only under ideal conditions, but under a variety of error assumptions. The project will test theoretical ideas empirically, on three different multi-robot systems.
Broader impacts will include new algorithms for robot coordination, and rigorous understanding of the capabilities of different hardware platforms. Robots are an excellent outreach tool, and provide concrete examples of theory in action.
Robot swarms are collections of robots that cooperate to solve problems in the real world. Typical problems might involve, for example, search and rescue, exploring an unknown terrain, or surrounding and cleaning up a hazardous waste spill. The goal of this project was to develop theoretical foundations for developing robot swarm systems. This includes mathematical models for robots, their behavior, and their interactions, as well as algorithms for key problems to be solved by robot swarms. The problems that were considered included maintaining connectivity of the robot swarm for communication and establishing a coordinate system by which robots can locate ("localize") themselves in two-dimensional space. For the study of connectivity, the investigators cast the problem in terms of geometric graphs. They showed that, when all robots maintain connectivity with nearby robots that comprise a "Local Minimum Spanning Tree (LMST)", the entire swarm remains connected. This led to a simple distributed algorithm that maintained LMSTs. The algorithm was shown to subsume several prior algorithms that used different connectivity criteria. The investigators showed how the connectivity algorithm can be used with various kinds of motion-planning algorithms to solve a number of interesting robot swarm problems. An example is "flocking": the robots remain connected for communication while converging to travel in the same direction at the same speed. In order to deal with failures, they extended the work on connectivity to preserve the stronger property of "k-connectivity", which implies that every pair of robots is connected by k different paths. The connectivity work also includes some lower bound results, which express inherent limitations on the capabilities of robot swarms to solve connectivity problems. Using the same theoretical foundation, the investigators studied a second problem called "angular localization", wherein a robot swarm is required to establish a global coordinate system using only simple (optical) angle sensors. The work on connectivity and angular localization was mainly theoretical, but most of the results are supported by experimental work based on simulations and on implementations using actual robot swarm platforms. The investigators also developed an algorithm for robot swarm exploration to isolate and trap intruders in an unfamiliar environment. The algorithm is based on a new way of characterizing the robots' environment, using techniques from the area of machine vision. Related work, partially supported on this project, includes a collection of new distributed algorithms for solving interesting problems in dynamically-changing connected networks, with connected robot swarms as a special case. The problems studied included disseminating messages throughout the network, counting the total number of robots in the system, and computing functions of local inputs. In other related work, the investigators introduced a new ``beeping'' model for communication in robot swarms and other types of wireless networks; in this model, nodes communicate using only simple wireless network carrier sensing. Using the beeping model, the investigators developed several interesting and efficient algorithms, for problems including message dissemination and building various graph-theoretical structures (e.g., colorings and maximal independent sets). In many ways, swarms of robots seem similar to colonies of social insects (such as ants and bees). Insect colonies cooperate to solve problems such as task allocation, exploration, routing, and building structures---all similar to robot swarm problems. However, insect colonies solve these problems in ways that are more flexible, robust, and adaptive than usual robot algorithms. It seems that studying insect algorithms, or at least algorithms with insect-like behavior, could lead to advances in robot swarm algorithms. Therefore, in the final year of this project, the investigators began examining insect colony behavior, trying to develop robot algorithms that have insect-like properties. They have preliminary results about the power of communication in exploration problems. Intellectual Merit: This project combined tools from distributed computing theory, robotics, and computational geometry. It developed theoretical foundations for robot swarms. It produced new algorithms for key robot swarm problems, and analyzed them rigorously. Algorithms were constructed in a modular way, using reusable components. The project tested theoretical ideas empirically, on robot platforms. Broader Impacts: This project produced new robust algorithms for problems involving robot coordination and control. These should make it easier for designers of multi-robot systems to construct high-quality systems. This work has also contributed to a rigorous understanding of the fundamental capabilities of robot platforms for solving important problems. Lower bounds identify limitations, which are interesting in their own right and also should help to steer system designers in feasible directions. PI Lynch is active in mentoring female graduate students and postdocs. A major collaborator, Prof. James McLurkin, is active in efforts to increase the pipeline of minority students in Science, Technology, Engineering, and Math (STEM) careers. Undergraduates have been directly involved in many phases of this project.
