CPS: Medium: Collaborative Research: Geometric Distributed Algorithms for Multi-Robot Coordination and Control
Lead PI:
Nancy Lynch
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.
Nancy Lynch

Biography

Nancy Lynch is the NEC Professor of Software Science and Engineering in the Department of Electrical Engineering and Computer Science at MIT.  She heads the Theory of Distributed Systems research group in MIT's Computer Science and Artificial Intelligence Laboratory.  She is also currently a Fellow at the Radcliffe Institute for Advanced Study.  

Lynch received her B.S. degree in mathematics from Brooklyn College in 1968, and her PhD in mathematics from MIT in 1972.  She has written numerous research articles about distributed algorithms and impossibility results, and about formal modeling and verification of distributed systems. Her best-known research contribution is the ``FLP'' impossibility result for distributed consensus in the presence of process failures, developed with Fischer
and Paterson in 1982.  Lynch's other well-known research contributions include the I/O automata mathematical system modeling frameworks, with Tuttle, Vaandrager, Segala, and Kaynar.  Her recent work is focused on
algorithms for mobile ad hoc networks.

Lynch has written books  on ``Atomic Transactions'' (with Merritt, Weihl, and Fekete), on ``Distributed Algorithms'', and on ``The Theory of Timed I/O Automata'' (with Kaynar, Segala, and Vaandrager).  She is an ACM Fellow, and a member of both the National Academy of Engineering and the American Academy of Arts and Sciences.  She was co-winner of the first (2006) van Wijngaarden prize, and was awarded the 2007 Knuth Prize, the 2010 IEEE Emanuel Piore award, and
the 2012 Athena award.  Lynch has supervised over 25 PhD students and over 50 Masters
students, as well as numerous postdoctoral research associates.


 

 

 

 

 

 

 
Performance Period: 09/15/2010 - 08/31/2013
Institution: Massachusetts Institute of Technology
Sponsor: National Science Foundation
Award Number: 1035199
Project URL