Data-Driven Certificate Synthesis

Luke Rickard, Alessandro Abate, Kostas Margellos · 2025

Read Data-Driven Certificate Synthesis by Luke Rickard, Alessandro Abate, Kostas Margellos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-05510.txt.

Introduction

Luke Rickard, Alessandro Abate, and Kostas Margellos learn safety certificates for moving systems straight from their past paths. Their twenty twenty-five paper covers three checks: can the system reach a goal, stay safe, and reach while avoiding harm? A certificate is a function whose shape proves the trait.

Training bends the function until trajectory data satisfy the proof conditions. The team also bounds, in probability terms, how the learned proof will fare on fresh paths. That step uses compression and scenario ideas from learning theory. Self-driving and robot teams need proofs that survive new roads, not just the test track; data-grown certificates with odds attached fit that need.

Catalog record

CREATORLuke Rickard, Alessandro Abate, Kostas Margellos
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-05510

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Data-Driven Certificate Synthesis Luke Rickard, Alessandro Abate, Kostas Margellos Abstract We investigate the problem of verifying different properties of discrete time dynamical systems, namely, reachability, safety and reach-while-avoid. To achieve this, we adopt a data driven perspective and, using past system trajectories as data, we aim at learning a specific function termed certificate for each property we wish to verify. We seek to minimize a loss function, designed to encompass conditions on the certificate to be learned that encode the satisfaction of the associated property. Besides learning a certificate, we quantify probabilistically its generalization properties, namely, how likely it is for a certificate to be valid (and hence for the associated property to be satisfied) when it comes to a new system trajectory not included in the training data set. We view this problem under the realm of probably approximately correct (PAC) learning under the notion of compression, and use recent advancements of the so-called scenario approach to obtain scalable generalization bounds on the learned certificates. To achieve this, we design a novel algorithm that minimizes the loss function and hence constructs a certificate, and at the same time determines a quantity termed compression, which is instrumental in obtaining meaningful probabilistic guarantees. This process is novel per se and provides a constructive mechanism for compression set calculation, thus opening the road for its use to more general non-convex optimization problems. We verify the efficacy of our methodology on several numerical case studies, and compare it (both theoretically and numerically) with closely related results on data-driven property verification. keywords Verification of Dynamical Systems, Safety, Reachability, Statistical Learning, Scenario Approach. † † address: Department of Engineering Science, University of Oxford † † address: Department of Computer Science, University of Oxford 1 Introduction † † This work was supported by the EPSRC Centre for Doctoral Training in Autonomous Intelligent Machines and Systems EP/S024050/1. Dynamical systems offer a rich class of models for describing the behavior of diverse, complex systems [ 25 ] . It is often of importance that these systems meet certain properties, for example, stability, safety or reachability [ 21 , 28 , 34 , 39 ] . Verifying the satisfaction of these properties, also termed as specifications, is a challenging, but important, problem. One research direction involves discretizing the state space [ 3 , 8 , 43 ] , in order to construct a finite model with guarantees generated using probabilistic or statistical model checkers [ 7 , 41 ] . Discretizing the state space however tends to be computationally expensive, even for low-dimensional systems. Table 1 : Classification of Certificate Synthesis Approaches ⋆ Theorem 9 , and Algorithms 1 & 4.2 , follow a non-convex scenario approach methodology, that does not require knowledge of the Lipschitz constant of the dynamics, and offer probabilistic verification bounds that do not necessarily scale exponentially in the state space dimension as with [ 34 , 45 ] . Model-Based Synthesis & Guarantees Data-Driven Synthesis & Model-Based Guarantees Data-Driven Synthesis & Guarantees Sum of Squares Programming [ 36 ] Counter-Example Guided Inductive Synthesis [ 1 , 16 , 19 , 21 ] Neural Network Techniques [ 6 , 47 ] MPC + Reachability analysis [ 2 , 40 ] Neural Hamilton-Jacobi Reachability Analysis [ 46 , 49 ] Convex Scenario Optimization [ 34 , 45 ] SAT-modulo-theory synthesis [ 4 ] Neural Certificates for Safety [ 29 ] Theorem 9 , Algorithms 1 & 4.2 ⋆ An alternative approach to verify properties of dynamical systems that does not require discretizing the state space, is through the use of certificates [ 3 , 5 , 37 ] . The goal is to determine a function over the system’s state space that exhibits certain properties. A well-investigated example of such certificate is that of a Lyapunov function, used to verify that dynamics satisfy some stability property [ 31 ] . Here we consider constructing reachability, safety, and reach-while-avoid (RWA) certificates for discrete-time systems. Overviews of techniques for certificate learning can be found in [ 3 , 20 ] ; Table 1 summarizes the related literature, which we discuss below. One approach to certificate synthesis considers verifying the behavior of systems assuming that a model of the underlying dynamical system is known. Restricting the class of models to polynomial functions, certificates can be obtained by solving a convex sum-of-squares problem [ 36 ] . More generally, synthesis approaches leveraging SAT-modulo-theories can alternatively be leveraged [ 4 , 20 ] . Availability of a model allows for co-design of a controller meeting certain specifications, such as safety and reachability [ 2 , 40 ] , using tools based on Model Predictive Control (MPC), or reachability analysis. The inclusion of the model’s knowledge in the synthesis procedure in practice limits the complexity of the models that may be studied. To alleviate this requirement, data-driven techniques, such as counter-example guided inductive synthesis (CEGIS) [ 1 , 16 , 19 , 21 ] are able to synthesize certificates for general non-linear systems. This is achieved via the use of neural networks as certificate templates, allowing for the approximation of any function within a certain function space [ 27 ] . Neural networks have also been explored as a tool in [ 46 , 49 ] for guaranteeing reachability, and in [ 29 ] for safety analysis. Such approaches involve data-driven synthesis, however, they still require a model of the system when it comes to providing guarantees on the synthesized certificates. Obtaining a model of the system is in general difficult, as it requires domain-specific knowledge. To alleviate these issues, in this work we follow a data-driven route that is model-free as far both the certificate synthesis and guarantee process is concerned. One way to achieve this involves using one set of samples to synthesize a certificate, and a separate set for validation [ 47 ] . An alternative approach which does not require different samples for validation and is hence also the one most closely related to our formulation, involves probabilistic property satisfaction using a convex design and results on scenario optimization [ 34 , 45 ] , and extensions to neural networks [ 6 , 47 ] . However, these developments rely on the system dynamics being Lipschitz continuous and for the Lipschitz constant to be known (or a bound on this to be available). Moreover, the probabilistic guarantees provided exhibit an exponential growth with respect to the system dimension. Both issues are not present within our proposed approach. In this work, we follow a scenario approach paradigm as in [ 34 , 45 ] , however, we exploit some different statistical learning theoretic developments in scenario optimization. This allows us to remove the requirements for convexity and knowledge of the Lipschitz constant of the dynamics, and establish probabilistic verification bounds that do not necessarily scale exponentially on the state dimension, but their complexity rather depends on the complexity of the underlying property verification task. In particular, we use any parameterized function approximator as certificate template, and learn these parameters using a finite number of system trajectories treated as samples. We formulate the certificate synthesis problem as a (possibly) non-convex optimization program, that involves minimizing an appropriately designed loss function,

Read the complete text