The desire to use reinforcement learning in safety-critical settings has inspired a recent interest in formal methods for learning algorithms. Existing formal methods for learning and optimization primarily consider the problem of constrained learning or constrained optimization. Given a single correct model and associated safety constraint, these approaches guarantee efficient learning while provably avoiding behaviors outside the safety constraint. Acting well given an accurate environmental model is an important pre-requisite for safe learning, but is ultimately insufficient for systems that operate in complex heterogeneous environments. This paper introduces verification-preserving model updates, the first approach toward obtaining formal safety guarantees for reinforcement learning in settings where multiple possible environmental models must be taken into account. Through a combination of inductive data and deductive proving with design-time model updates and runtime model falsification, we provide a first approach toward obtaining formal safety proofs for autonomous systems acting in heterogeneous environments.
@cite_19: In this paper, we suggest a novel methodology for synthesizing switching controllers for continuous and hybrid systems whose dynamics are defined by linear differential equations. We formulate the synthesis problem as finding the conditions upon which a controller should switch the behavior of the system from one "mode" to another in order to avoid a set of bad states and propose an abstract algorithm that solves the problem by an iterative computation of reachable states. We have implemented a concrete version of the algorithm, which uses a new approximation scheme for reachability analysis of linear systems.
@cite_9: For many performance-critical control systems, an accurate (simple) model is not available in practice. Thus, designing controllers with formal performance guarantees is challenging. In this paper, we develop a framework to use input-output data from an unknown system to synthesize controllers from signal temporal logic (STL) specifications. First, by imposing mild assumptions on system continuity, we find a set-valued piecewise affine (PWA) model that contains all the possible behaviors of the concrete system. Next, we introduce a novel method for STL control of PWA systems with additive disturbances. By taking advantage of STL quantitative semantics, we provide lower-bound certificates on the degree of STL satisfaction of the closed-loop concrete system. Illustrative examples are presented.
Although we are the first to explore hybrid program repair, several researchers have explored the problem of synthesizing hybrid systems from data @cite_19 @cite_9 . This work is closely related to our update. Sadraddini and Belta provide formal guarantees for data-driven model identification and controller synthesis @cite_9 . Relative to this work, our update is continuous-time, synthesizes a computer-checked correctness proof (as opposed to a least violation criterion implied by the synthesis algorithm, both not independently checked by a theorem prover), and does not require dynamics to be compact, bounded, and locally connected. Unlike @cite_19 , our full set of model updates is sometimes capable of synthesizing nonlinear dynamical systems from data (e.g., the static @math circular update) and produces computer-checked correctness proofs for permissive controllers.