Approximate Bi-simulation Bridging CS and Control



Lecture Details

Location Information: 
IEEE CDC-ECC 2011 Semi-Plenary Lecture - Orlando, FL, December 2011
George J. Pappas
Author Bio: 

George J. Pappas is the Joseph Moore Professor in the Department of Electrical and Systems Engineering at the University of Pennsylvania. He also holds a secondary appointment in the Departments of Computer and Information Sciences, and Mechanical Engineering and Applied Mechanics. He is member of the GRASP Lab and the PRECISE Center for embedded systems. His research focuses on control theory and in particular, hybrid systems, embedded systems, hierarchical and distributed control systems, with applications to unmanned aerial vehicles, distributed robotics, green buildings, and biomolecular networks. He is a Fellow of IEEE, and has received various awards such as the 2010 Antonio Ruberti Young Researcher Prize, the 2009 George S. Axelby Award, and the 2004 National Science Foundation PECASE Award.


Fifty years ago, control and computing were part of a broader system science.  After a long period of intra-disciplinary development which resulted in control and computing being distant from each other, embedded and hybrid systems have challenged us to unite the, now developed, theories of continuous control and discrete computing on a broader system theoretic basis.

In this talk, we will present a notion of system approximation that applies to both discrete and continuous systems by developing notions of approximate language inclusion, approximate simulation, and  approximate bisimulation relations. We define a hierarchy of approximation pseudo-metrics between two systems that quantify the quality of the approximation, and capture the established notions in computer science as zero sections. Algorithms are developed for computing the proposed pseudo-metrics, both exactly and approximately. The exact algorithms require the generalization of the fixed point algorithms for computing simulation and bisimulation relations, or dually, the solution of a static game whose cost is the so-called branching distance between the systems. Approximations for the pseudo-metrics can be obtained by considering Lyapunov-like functions called simulation and bisimulation functions.   Our approximation framework will be illustrated in in problems such as safety verificaion problems for continuous systems, approximating nonlinear systems by discrete systems, and hierarchical control design.