Bisimilar Control Systems

George J. Pappas, Departments of EE and CIS, University of Pennsylvania

Theoretical computer science, and, in particular, the areas of concurrency theory, and computer aided verification have established formal notions of abstraction and model refinement which exploit the hierarchical and compositional nature of large scale systems. In particular, the notions of simulation and bisimulation are established complexity reduction methods for the analysis and design of labeled transition systems.

Bisimulations are special quotients of the state space that preserve many important properties, and, in particular, reachability. We apply the framework of bisimilar transition systems to various transition systems that are generated by linear control systems. Given a discrete-time or continuous-time linear system, and a finite or linear observation map, we characterize linear quotient maps that result in quotient transition systems that are bisimilar to the original system. Interestingly, the characterizations for discrete-time systems are more restrictive than for continuous-time systems, due to the existence of an atomic time step. We show that computing the coarsest bisimulation, which results in maximum complexity reduction, corresponds to computing the maximal controlled or reachability invariant subspace inside the kernel of the observation map.

We also derive necessary and sufficient conditions for simulation relations between discrete-time linear systems that are subject to state and input constraints. The simulation conditions are expressed as set-inclusions that can be efficiently checked numerically based on a linear programming formulation. The structure of the linear programs reflects the game theoretic semantics of simulation relations. These results establish strong connections between complexity reduction concepts in control theory and computer science.