C.F. Verdier | TU Delft Repository

Formal synthesis of closed-form sampled-data controllers for nonlinear continuous-time systems under STL specifications

Journal article (2022) - Cees Ferdinand Verdier, Niklas Kochdumper, Matthias Althoff, Manuel Mazo

We propose a counterexample-guided inductive synthesis framework for the formal synthesis of closed-form sampled-data controllers for nonlinear systems to meet STL specifications over finite-time trajectories. Rather than stating the STL specification for a single initial condition, we consider an (infinite and bounded) set of initial conditions. Candidate solutions are proposed using genetic programming, which evolves controllers based on a finite number of simulations. Subsequently, the best candidate is verified using reachability analysis; if the candidate solution does not satisfy the specification, an initial condition violating the specification is extracted as a counterexample. Based on this counterexample, candidate solutions are refined until eventually a solution is found (or a user-specified number of iterations is met). The resulting sampled-data controller is expressed as a closed-form expression, enabling both interpretability and the implementation in embedded hardware with limited memory and computation power. The effectiveness of our approach is demonstrated for multiple systems. ...

Formal synthesis of analytic controllers

An evolutionary approach

Doctoral thesis (2020) - C.F. Verdier

Control design for modern safety-critical cyber-physical systems still requires significant expert-knowledge, since for general hybrid systems with temporal logic specifications there are no constructive methods. Nevertheless, in recent years multiple approaches have been proposed to automatically synthesize correct-by-construction controllers. However, typically these methods either result in enormous look-up tables, require online optimization, or are highly dependent on expert-knowledge. The goal of this thesis is to propose a novel approach that overcomes these limitations, i.e. to propose a framework for automatic controller synthesis, capable of synthesizing closed-form controllers for hybrid systems with temporal logic specifications, without a heavy reliance on expert-knowledge. To this end, we draw inspiration from the human design process and utilize two methods that show great similarities to it, namely evolutionary algorithms and counterexample-guided inductive synthesis (CEGIS). Specifically, we use genetic programming (GP), an evolutionary algorithm capable of evolving entire programs. This makes it possible to automatically discover the structure of a solution. Moreover, it enables the synthesis of compact closed-form controllers, circumventing the need for look-up tables or online optimization. In combination with GP, we use the concept of CEGIS to refine candidate solutions based on counterexamples, until the controller is guaranteed to satisfy the desired specification. In this thesis we propose two CEGIS-based synthesis frameworks, which differ in the employed verification paradigms, namely utilizing either (co-synthesized) Lyapunov-like functions or reachability analysis. Both frameworks result in correct-by-construction compact closed-form controllers, where the use of expert-knowledge is optional. Both frameworks are capable of synthesizing sampled-data controllers, enabling implementation in embedded hardware with limited memory and computation power, forming a stepping stone towards faster automation. ...

Control design for modern safety-critical cyber-physical systems still requires significant expert-knowledge, since for general hybrid systems with temporal logic specifications there are no constructive methods. Nevertheless, in recent years multiple approaches have been proposed to automatically synthesize correct-by-construction controllers. However, typically these methods either result in enormous look-up tables, require online optimization, or are highly dependent on expert-knowledge. The goal of this thesis is to propose a novel approach that overcomes these limitations, i.e. to propose a framework for automatic controller synthesis, capable of synthesizing closed-form controllers for hybrid systems with temporal logic specifications, without a heavy reliance on expert-knowledge. To this end, we draw inspiration from the human design process and utilize two methods that show great similarities to it, namely evolutionary algorithms and counterexample-guided inductive synthesis (CEGIS). Specifically, we use genetic programming (GP), an evolutionary algorithm capable of evolving entire programs. This makes it possible to automatically discover the structure of a solution. Moreover, it enables the synthesis of compact closed-form controllers, circumventing the need for look-up tables or online optimization. In combination with GP, we use the concept of CEGIS to refine candidate solutions based on counterexamples, until the controller is guaranteed to satisfy the desired specification. In this thesis we propose two CEGIS-based synthesis frameworks, which differ in the employed verification paradigms, namely utilizing either (co-synthesized) Lyapunov-like functions or reachability analysis. Both frameworks result in correct-by-construction compact closed-form controllers, where the use of expert-knowledge is optional. Both frameworks are capable of synthesizing sampled-data controllers, enabling implementation in embedded hardware with limited memory and computation power, forming a stepping stone towards faster automation.

Near optimal control with reachability and safety guarantees

Journal article (2019) - Cees Verdier, Robert Babuška, Barys Shyrokau, Manuel Mazo

Control systems designed via learning methods, aiming at quasi-optimal solutions, typically lack stability and performance guarantees. We propose a method to construct a near-optimal control law by means of model-based reinforcement learning and subsequently verifying the reachability and safety of the closed-loop control system through an automatically synthesized Lyapunov barrier function. We demonstrate the method on the control of an anti-lock braking system. Here the optimal control synthesis is used to minimize the braking distance, whereas we use verification to show guaranteed convergence to standstill and formally bound the braking distance. ...

Formal synthesis of analytic controllers for sampled-data systems via genetic programming

Conference paper (2018) - Cees F. Verdier, Manuel Mazo

This paper presents an automatic formal controller synthesis method for nonlinear sampled-data systems with safety and reachability specifications. Fundamentally, the presented method is not restricted to polynomial systems and controllers. We consider a periodically switched controllers based on a Control Lyapunov Barrier-like function. The proposed method utilizes genetic programming to synthesize these function in analytic form, as well as the controller modes. Correctness of the controller are subsequently verified by means of a Satisfiability Modulo Theories solver. Effectiveness of the proposed methodology is demonstrated on multiple systems. ...

Optimal symbolic controllers determinization for BDD storage^⁎

Journal article (2018) - Ivan S. Zapreev, Cees Verdier, Manuel Mazo

Controller synthesis techniques based on symbolic abstractions appeal by producing correct-by-design controllers, under intricate behavioural constraints. Yet, being relations between abstract states and inputs, such controllers are immense in size, which makes them futile for embedded platforms. Control-synthesis tools such as PESSOA, SCOTS, and CoSyMA tackle the problem by storing controllers as binary decision diagrams (BDDs). However, due to redundantly keeping multiple inputs per-state, the resulting controllers are still too large. In this work, we first show that choosing an optimal controller determinization is an NP-complete problem. Further, we consider the previously known controller determinization technique and discuss its weaknesses. We suggest several new approaches to the problem, based on greedy algorithms, symbolic regression, and (muli-terminal) BDDs. Finally, we empirically compare the techniques and show that some of the new algorithms can produce up to ≈ 85% smaller controllers than those obtained with the previous technique. ...

Formal controller synthesis via genetic programming

Journal article (2017) - C. F. Verdier, M. Mazo

This paper presents an automatic controller synthesis method for nonlinear systems with reachability and safety specifications. The proposed method consists of genetic programming in combination with an SMT solver, which are used to synthesize both a control Lyapunov function and the modes of a switched state feedback controller. The resulting controller consists of a set of analytic expressions and a switching law based on the control Lyapunov function, which together guarantee the imposed specifications. The effectiveness of the proposed approach is shown on a 2D pendulum. ...