Approximate Bi-simulation Bridging CS and Control

Abstract

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.