Synthesis of safety certificates for discrete-time uncertain systems via convex optimization footnoteinfo
Marta Fochesato, Han Wang, Antonis Papachristodoulou, Paul Goulart · 2025
Read Synthesis of safety certificates for discrete-time uncertain systems via convex optimization footnoteinfo by Marta Fochesato, Han Wang, Antonis Papachristodoulou, Paul Goulart (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-2505-08559.txt.
Introduction
Fochesato, Wang, Papachristodoulou, and Goulart worked in twenty twenty-five on proofs of safety for step-time systems that face noise. They pair a safety proof sheet with a plain rule that steers the system by its state. For noise with a capped size, they give a math task whose pass means a safe rule exists.
For noise with no cap, chance math gives a task that yields chance-based safety for a set span. They add ways to fold in caps on inputs and doubt on the chance spread. Safe screens and dodging blocks are also fit in the frame. The tools aim at sound, check-able safety claims.
Catalog record
| CREATOR | Marta Fochesato, Han Wang, Antonis Papachristodoulou, Paul Goulart |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-08559
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Synthesis of safety certificates for discrete-time uncertain systems via convex optimization footnoteinfo Marta Fochesato, Han Wang, Antonis Papachristodoulou, Paul Goulart Abstract We study the problem of co-designing control barrier functions and linear state feedback controllers for discrete-time linear systems affected by additive disturbances. For disturbances of bounded magnitude, we provide a semi-definite program whose feasibility implies the existence of a control law and a certificate ensuring safety in the infinite horizon with respect to the worst-case disturbance realization in the uncertainty set. For disturbances with unbounded support, we rely on martingale theory to derive a second semi-definite program whose feasibility provides probabilistic safety guarantees holding joint-in-time over a finite time horizon. We examine several extensions, including (i) encoding of different types of input constraints, (ii) robustification against distributional ambiguity around the true distribution, (iii) design of safety filters, and (iv) extension to general safety specifications such as obstacle avoidance. keywords Control Barrier Functions; Stochastic systems; Convex optimization. † † thanks: [ † † address: Automatic Control Laboratory (IfA), ETH Zürich, Zürich, Switzerland † † address: Department of Engineering Science, University of Oxford, OX1 3PJ, Oxford, UK footnoteinfo]Marta Fochesato’s research visit at the University of Oxford was supported by the ETH Zürich Doc.Mobility Fellowship Programme. , , , , 1 Introduction Safety requirements are a critical concern in control theory, with many real-world applications calling for certificates ensuring that the system avoids entering unexpected regions, or remains inside a prescribed safe set during the control task length despite the presence of uncertainties. Examples are ubiquitous, ranging from air traffic control [ 21 ] to autonomous vehicles [ 3 ] and robotics [ 22 ] . Consequently, in the wake of the ongoing emergence of ever-more complex safety-critical control problems, there is a growing need for optimal control tools that can provide reliable certificates under uncertainty. Consider a stochastic dynamical system x_{t+1}=f(x_{t},u_{t},w_{t}) with state x\in\mathcal{X}\subseteq\mathbb{R}^{n} , input u\in\mathcal{U}\subseteq\mathbb{R}^{m} , and a stochastic disturbance w_{t}\in\mathcal{W}\subseteq\mathbb{R}^{d} . Concurrently, consider an (application-specific) safe set \mathcal{S}\subseteq\mathcal{X} describing the portion of the state space in which the system state is allowed to lie. For example, \mathcal{S} may describe the road boundaries in autonomous driving applications, or the allowable voltage and current ranges in power converter operations. Two fundamental problems arise in the safety enforcement problem: (i) for a set of initial conditions \mathcal{I}\subseteq\mathcal{S} , verify whether there exists a feedback control law u=\pi(x) such that the trajectories starting from \mathcal{I} are safe, i.e., they remain in \mathcal{S} along a prescribed time interval, and (ii) design such a safe feedback controller in a reliable and computationally efficient manner. The discrete-time Control Barrier Function (CBF) approach answers both of these questions via a continuous function that satisfies certain properties. Roughly speaking, a CBF aims to separate the safe and unsafe regions of the state space by its zero level set and ultimately enables controller synthesis for safety requirements specified by forward invariance of a set using a Lyapunov-like condition. Despite practical success in many applications, such as Segway balancing, bipedal walking robots, and quadrotors (see, for example, [ 1 ] and references therein), the CBF approach suffers from a fundamental challenge as the design of viable and non-conservative CBF candidates is non-trivial even for linear deterministic systems. In fact, even verifying that a candidate function is a CBF is NP-hard [ 4 ] . 1.1 Related works While the continuous-time setting has undoubtedly received more attention, several methods have been proposed in recent years to synthesize control barrier functions for discrete-time systems. For example, reachability-based methods [ 2 ] solve an optimal control problem returning a set of states starting from which the dynamical system is certified to stay within a prescribed safe set during a given time interval. Given this formulation, one can show that the value function of the optimal control problem is a time-varying CBF [ 15 ] . However, solving the optimal control problem is generally challenging as it involves the solution of a Hamilton-Jacobi Partial Differential Equation [ 13 , 16 ] and requires ad-hoc numerical heuristics. Learning-based methods parametrize both the control law and the CBF, and rely on the availability of a finite dataset to determine the optimal parameters minimizing a suitable loss function [ 27 , 23 , 6 ] . For example, [ 35 , 12 ] consider a neural network-based parametrization. This class of methods can address highly nonlinear and high-order systems; however, they lack rigorous guarantees and require large amounts of training data that are not easy to collect in general [ 36 ] . Finally, we recall optimization-based approaches, mostly in the form of Sum-Of-Squares (SOS) optimization. For polynomial dynamics and semi-algebraic safe sets, SOS turns the algebraic conditions for CBF into polynomial positivity conditions, and casts them using SOS hierarchies [ 19 , 32 ] . Compared to the previous methods, SOS allows for rigorous safety guarantees and efficient computation (unlike learning-based methods), and tractable solutions (unlike reachability-based methods). However, when controllers need to be simultaneously designed, a commonly used method alternates between synthesizing the controller and the CBF in sequential SOS programs [ 25 , 33 ] . Unfortunately, alternating methods suffer from two major drawbacks: first, a feasible initial condition must be provided (which may in general be nontrivial to find [ 37 ] , [ 25 ] ); second, no convergence guarantees are provided [ 32 ] . Finally, exploiting SOS programming duality, moment problems based on occupation measures can be formulated to solve the address the synthesis problem [ 10 ] . Whenever the system dynamics are affected by uncertainty, the design procedure faces additional challenges. Recent literature has attempted to address this additional complexity. The seminal work in [ 20 ] only considers the worst-case and stochastic safety verification problems, hence disregarding the control design task. More recently, [ 8 ] addresses the control design task for stochastic discrete-time systems subject to temporal logic specifications. Further, [ 26 ] introduces so-called risk control barrier functions, which are compositions of barrier functions and dynamic coherent risk measures, to enable a risk-aware safety analysis. However, both papers assume a candidate CBF to be known a priori to the control designer. As a result, the convex co-design of CBFs and feedback controllers for discrete-time stochastic systems has not found a comprehensive treatment in the literature and is still an open problem. 1.2 Contributions and Outline The main goal of this manuscript is to address this challenge by providing a convex design procedure for the joint synthesis of a CBF and a feedback controller for the class of discrete-time uncertain linear systems affected by additive stochastic noise. We begin by describing in Section 2 meaningful notions of safety for uncertain systems based on the properties of the disturbance vector. In particular, we distinguish between infinite-horizon safety when the support \mathcal{W} is bounded; and finite-horizon safety that holds joint-in-time over a finite time horizon when \mathcal{W} is unbounded. Next, in Section 3 we formalize our main contribution and show that the above safety requirements can be encoded via convex programs, hence bypassing the need for alternating methods. Further, in Section 4 we consider several extensions: most notably, we consider the inclusion of different types of input