Abstractions: A Bridge Between Continuous Dynamics and Discrete Event Systems

Abstract

In this talk, we will give an overview of finite abstractions, which are graph-based representations for continuous-state control systems. If these finite abstractions are constructed properly, they can be used to design controllers using techniques from discrete event systems or reactive synthesis in a way that the designed controller can be implemented on the underlying continuous control system (namely, the concrete system) and provide guarantees on the closed-loop behavior. In order to lead to a correct-by-construction design, the abstract system should satisfy a certain relation with the concrete system. We will introduce several such relations including, (bi)simulation relations, over-approximations, feedback refinement relations, and discuss what type of properties are preserved under these relations. Finally, we will discuss various ways of constructing these abstractions, e.g., based on gridding or partitioning the state space, for different classes of systems, e.g., discrete-time or continuous-time. Several examples will be used throughout to demonstrate these techniques in action. The talk will conclude with a summary of more recent results and a discussion on several research directions.