Deductive control synthesis for alternating-time logics

摘要

Algorithmic design of control laws for continuous systems for complex temporal specifications is a key step toward automatic synthesis of controllers for cyber-physical systems. Current approaches either abstract the dynamical system to a finite-state approximation or search for certificates that imply invariance or reachability properties (barriers and Lyapunov functions, respectively). The first approach is limited by an exponential blow-up in the abstraction process; the second in the properties that can be controlled for. We present a deductive proof system for the control of alternating-time temporal properties on continuous systems. We show that reasoning about temporal logic constraints in ATL ?, an expressive branching-time logic that allows for quantification over control strategies, can be reduced effectively to reasoning about combinations of barrier certificates and Lyapunov functions. Our approach enables the application of existing constraint-based techniques for finding barriers and Lyapunov functions to the design of controllers for complex temporal properties, while sidestepping the exponential cost of computing finite-state abstractions.