| NSF Org: |
CNS Division Of Computer and Network Systems |
| Recipient: |
|
| Initial Amendment Date: | September 10, 2010 |
| Latest Amendment Date: | September 10, 2010 |
| Award Number: | 1035199 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Sylvia Spengler
sspengle@nsf.gov (703)292-7347 CNS Division Of Computer and Network Systems CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 15, 2010 |
| End Date: | August 31, 2013 (Estimated) |
| Total Intended Award Amount: | $340,000.00 |
| Total Awarded Amount to Date: | $340,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
77 MASSACHUSETTS AVE CAMBRIDGE MA US 02139-4301 (617)253-1000 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
77 MASSACHUSETTS AVE CAMBRIDGE MA US 02139-4301 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | CPS-Cyber-Physical Systems |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
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.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
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 algorit...
Please report errors in award information by writing to: awardsearch@nsf.gov.
