Award Abstract #0132716
PECASE: Hierarchical Abstractions of Hybrid Systems

NSF Org:	CNS Division of Computer and Network Systems
Initial Amendment Date:	February 28, 2002
Latest Amendment Date:	June 16, 2006
Award Number:	0132716
Award Instrument:	Continuing grant
Program Manager:	D. Helen Gill CNS Division of Computer and Network Systems CSE Directorate for Computer & Information Science & Engineering
Start Date:	May 1, 2002
Expires:	April 30, 2007 (Estimated)
Awarded Amount to Date:	$375000
Investigator(s):	George Pappas pappasg@ee.upenn.edu (Principal Investigator)
Sponsor:	University of Pennsylvania Research Services Philadelphia, PA 19104 215/898-7293
NSF Program(s):	EMBEDDED & HYBRID SYSTEMS(EHS), CONTROL, NETWORKS, & COMP INTE
Field Application(s):
Program Reference Code(s):	HPCC, 9216, 1667, 1518, 1187, 1076, 1045
Program Element Code(s):	2801, 1518

ABSTRACT



Proposal Title: PECASE: Hierarchical Abstractions of Hybrid Systems

Institution: University of Pennsylvania

Recent years have witnessed the availability of extremely powerful and inexpensive computers, the explosion of communication networks, and revolutions in sensor and actuator technology. These accelerating advances have found their way inside many physical systems such as cars, aircraft, chemical processes, power networks, micro-mechanical systems, and manufacturing systems, resulting in the so-called embedded control systems or embedded software systems which merge physical processes with information systems. These application domains are important not only from an engineering perspective but also because of their prevalence in everyday life and the well-being of the economy.

Designing efficient, yet robust, large-scale embedded systems is a significant systems challenge. It is of immediate importance to develop the research foundations and educational programs to enable next-generation engineers to optimally utilize the opportunities offered by information technology. The difficulty with embedded systems arises from the fact that the software design and the control design is highly decoupled. As a result, physical constraints, such as differential equations, are not taken explicitly into account in the software design process. Consequently, fundamentally novel approaches to the design of embedded systems are needed as well as the development of models and tools that address the analysis and design of the integrated system with its many different physical, functional and logical aspects.

The research discipline of hybrid systems provides a theoretical foundation for the modeling, analysis, and design of embedded systems. Hybrid systems naturally combine discrete-event and continuous-time systems in a manner that can capture software logic, physical dynamics, and communication protocols, in a unified modeling framework. Hybrid systems have been used as mathematical models for automated highway systems, air traffic management systems, embedded automotive controllers, manufacturing systems, chemical processes, and, more recently, biomolecular networks. The wide applicability of hybrid systems has inspired a great deal of research from both control theory and theoretical computer science.

Despite the great success of hybrid systems as a model, the applicability of state-of-the-art analysis and design techniques for hybrid systems has been limited to examples of small size due to complexity. One of the fundamental approaches for reducing complexity involves the use of hierarchical decomposition. One of the main challenges in hierarchical systems is the extraction of a hierarchy of models at various levels of abstraction which are compatible with the functionality and objectives of each layer. Hierarchies have been instrumental in separately managing the complexity of both control and software designs. However, for hybrid systems which re-integrate software and control, the right notion of hierarchy is a great challenge, and is the critical obstacle for scaling our models, theories, algorithms, and tools to large scale, embedded systems.

Next-generation, large-scale embedded systems have motivated new control as well as software paradigms. As a result, there are numerous opportunities for fundamental and significant contributions from both a theoretical and an applied perspective. In this exciting intellectual landscape, the research and educational agenda of the proposed research focuses on developing the theoretical foundations for the hierarchical decomposition of hybrid systems at various levels of abstraction. The long term goal of the research agenda will address the fundamental problem of given a class of hybrid models, and a class of properties that must be preserved, extract modeling abstractions that preserve the properties of interest. Achieving this goal will consist of first developing robust notions of bi-simulation for purely continuous systems, and then unifying the continuous and discrete notions in a manner that is consistent with the dynamics of hybrid systems.

Merging discrete and continuous systems creates serious educational issues in order to combine the traditionally separate threads of discrete and continuous mathematics. These issues must be addressed at all educational levels. At the graduate level, creating new courses on hybrid systems are needed, but with focus on complexity reduction methods in both control theory and computer science. However, given the one-sided backgrounds of most undergraduate students, what is needed at the undergraduate level, is a cross-departmental, embedded systems course that will highlight both the discrete and continuous nature of embedded systems in various application domains. This will allow the earlier uniformization of educational backgrounds, expose students to related application domains in other departments, as well as demonstrate the cross-disciplinary power of the models, methods, and tools.

This project was originally funded as a CAREER award, and was converted to a Presidential Early Career Award for Engineers and Scientists (PECASE) award in May 2004.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Antoine Girard and George J. Pappas. "Approximate bisimulation relations for constrained linear systems," Automatica, 2007, p. 1307.

Antoine Girard and George J. Pappas. "Approximation metrics for discrete and continuous systems," IEEE Transactions on Automatic Control, 2007, p. 7.

C. Belta, V. Isler, and G. J. Pappas. "Discrete Abstractions for Robot Motion Planning and Control in Polygonal Environments," IEEE Transactions on Robotics, v.21, 2005, p. 864.

Esfandiar Haghverdi, Paulo Tabuada, and George J. Pappas. "Bisimulation relations for dynamical, control, and hybrid systems," Theoretical Computer Science, v.342, 2005, p. 229.

George J. Pappas. "Bisimilar Linear Systems," Automatica, v.39, 12, p. 2035.

Paulo Tabuada and George J. Pappas. "Bisimilar Control Affine Systems," Systems and Control Letters, v.52, 1, p. 49.

Paulo Tabuada, George J. Pappas, and Pedro Lima. "Compositional abstractions of hybrid control systems," Discrete Event Dynamic Systems, v.14, 2, p. 203.

Please report errors in award information by writing to: awardsearch@nsf.gov.