DARPA Grand Challenge

The Defense Advanced Research Projects Agency (DARPA) is offering two million dollars for the unmanned ground robot that wins a desert race from Barstow, California, to Primm, Nevada. The race was held for the first time in March 2004 and none of the contestants traveled farther than 7.4 miles. The Golem Group entry did well: 5.2 miles, and the best result on a basis of "miles traveled per dollar spent." In 2004, the Golem Group and UCLA have joined forces, and are developing a common entry to the 2005 race.

The Golem Group/UCLA entry has been selected as one of the 20(+3) finalists for the 2005 race! God speed, Golem 2!

Details on the race and the qualification events (including pictures and videos) are available here.

Please check out the Golem Group/UCLA web site for more information.

CAREER: High-Confidence Software for Aerospace Embedded Systems (NSF, Grant 0133869)

This research project is developing new tools and techniques for the design and analysis of high-confidence software for complex, distributed, reconfigurable aerospace embedded systems, and to transfer these methods to undergraduate and graduate students, other researchers, and industry. Examples of problems of direct interest are those arising in the control and coordination of multiple autonomous air and space vehicles, and in the detection and resolution of conflicts in Air Traffic Control. The techniques developed in this project are also applicable to other systems which require similar levels of reliability and performance, such as highway traffic automation systems, health care systems, power networks, and financial services.

Of particular interest for this project is a better understanding of the interactions between real-time software and dynamical systems. This will lead to new and powerful tools and techniques for the design and analysis of embedded systems, as well as an improved approach to the requirement specification for real-time systems. The main core of the research project is aimed at dramatically reducing the complexity of embedded and hybrid systems design and verification by exploiting the geometric structure of the underlying physical system in the modelling effort, and by preserving this structure in the design of control laws and algorithms. This will make feasible for the analysis of the complete system, including its physical and software components, otherwise poorly scalable techniques such as abstract interpretation and model checking, and will provide the means for the effective use of techniques based on compositional reasoning.

For example, group symmetries in vehicle dynamics give rise to families of equivalent controlled trajectories: such sets are called motion primitives for single vehicles, and motion coordination primitives for groups of vehicles. A maneuver automaton is a collection of a finite number of motion primitives. In other words, a maneuver automaton is a discrete model of the vehicle dynamics, which leads to a dramatic reduction of the complexity of describing and controlling the vehicle behavior, by providing a high level of abstraction, and at the same time providing invariants which ensure that the physical state remains within some known bounds.

The educational part of the project is implemented through new course and curriculum development, and student mentoring. The main educational objective is to provide both undergraduate and graduate students with the knowledge and the skills to understand the key issues and to ensure technical leadership in the current and future aerospace information technology arenas. Finally, a special effort is devoted to the development of an interactive web site, where it is possible to access all the relevant information and software developed for the courses, and as a result of the research project.

Geometric and Algorithmic Methods for Design and Verification of Hybrid Control Systems (NSF, Grant 0208891 )

This is a collaborative research project with Steve LaValle at UIUC and Michael Branicky at Case Western Reserve University. Check out Michael's web site.

The proliferation of embedded computing and wireless communication technologies are opening up tremendous possibilities for designing systems with unprecedented capabilities, in fields ranging from air and ground transportation, to law enforcement and homeland security, manufacturing, medical devices, environmental control, and energy management. The shift from human-controlled systems to highly automated systems in safety-critical applications places an enormous burden on the certification of new systems, as new types of failure modes are potentially introduced. Unfortunately, as the complexity of such systems increases at a fast pace, our ability to analyze and precisely predict and understand their behavior is still very limited.

The consequence of this is that the verification of most complex systems depends on extensive testing campaigns, which can increase the certification costs to unacceptable levels, while at the same time failing to cover exhaustively all possible failure modes. We believe that the solution to this problem involves the careful integration of complexity-reducing modelling and design techniques, and of powerful new verification algorithms into the design process.

Therefore, our approach to improving verification capabilities in the design of hybrid control systems involves two thrusts:

1. Dramatically reducing the complexity of embedded and hybrid systems by exploiting the geometric structure of the underlying physical system in the modelling effort and by preserving this structure in the design of control laws and algorithms.
2. Improving the efficiency of the verification process, by developing algorithmic techniques that break the barriers of existing approaches by using provably efficient sampling techniques to enable a fast exploration of the reachable states for high-dimensional hybrid control systems.

The combination of these two thrusts is expected to dramatically improve our ability to develop complex systems, while maintaining a high level of confidence on their safety and reliability. The first thrust is motivated by the fact that most embedded systems of practical interest enjoy a very rich geometric structure. Explicit exploitation of this structure in the modelling effort, and its careful preservation in the design of the control algorithms, allows a substantial reduction in the dimensionality of the state space of the system.

The second thrust is motivated in part by the close relationship between motion planning and verification problems, ensuing from their common reliance on reachability analysis. We propose the design of efficient verification algorithms by building on recently developed techniques that exploit random and quasi-random sampling to rapidly solve many motion planning problems that were too daunting for classical approaches. Focusing on weaker guarantees, captured by notions such as probabilistic verification and resolution-complete verification, we can trade off completeness for complexity.

To ensure both immediate and longer-term impact of this effort, we carefully consider several applications in which our ideas will be evaluated, refined, and demonstrated. The main applications of interest will include the control and coordination of multiple, agile, air and ground vehicles, air traffic control problems, humanoid robotics, and robotic assembly and manufacturing.

Cooperative Networked Control of Dynamical Peer-to-Peer Vehicle Systems (DARPA/AFOSR/UIUC)

The proliferation of computing and wireless communication technology has opened up tremendous possibilities for deploying large cooperative networks of smart vehicles to perform intricate and complex missions. It is evident that collaborative teams of aerial and ground vehicles can perform a plethora of highly beneficial tasks for achieving military objectives and civilian security. Despite the emergence of very successful control design techniques for single vehicle systems, and the almost ubiquitous existence of distributed software systems, systematic methodologies for the reliable construction of cooperative networked multi-vehicle systems are effectively nonexistent.

The major objective of our consortium is the development of a rigorous theoretical foundation, and scalable an- alytical tools and paradigms, so that such systems can be systematically constructed and their performance formally verified. More generally, the activity of this program can be expected to have a dramatic impact on understanding and designing large-scale robust real-time distributed systems. Our goals are to make use of recent algorithmic develop- ments to provide hard performance guarantees and bounds for systems performing sophisticated tasks in uncertain and dynamic physical situations.

The focus of our project is on the control algorithms and internal software required to develop systems which are verifiably robust. Such systems must operate under situations with significant external environmental uncertainty, combined with malicious attacks and rapidly evolving mission objectives, and these issues are a central concern for current and future autonomous systems. A major direction of the proposed program is the frontier between the design methodologies of distributed software systems and those of robust feedback control, an area which holds significant promise for advances with dramatic theoretical and practical impact.

Energy-Efficient Coordination of Controlled-Mobility Wireless Networks (NSF, Grant 0325716 )

Today's embedded computers are increasingly mobile and ubiquitous, are capable of interacting with the environment, and can communicate with one another over possibly vast and pervasive networks. While most of the wireless networks are not expected to be capable of controlling their own motion, new technological possibilities are emerging to provide small embedded devices with the means to propel themselves, with an energy expenditure that is comparable to the energy budget of communication and computation.

A Controlled-Mobility Wireless Network (CMWN) is defined as a network of embedded devices endowed with computation, communication and motion capabilities. The purpose of this project is the development of a new conceptual framework for the design, development and operation of efficient and reliable networks with such characteristics.

The overall objectives of the basic research proposed in this project are:

1. The development of a conceptually sound, consistent and complete framework for the analysis of the interactions between competing computation, communication, and motion control requirements, arising in the design of CMWNs.
2. The design, analysis, and performance characterization of distributed algorithms and communication protocols for provably efficient and adaptive CMWNs. 3. The specification, implementation and verification of software, middleware and networking services for the deployment of representative CMWNs.