CS Paper Radar

Comparison Invariants for Verifying Control Invariance

Promit Panja, André Platzer

cs.LO eess.SY ·submitted 2026-08-25 14:20 UTC · v1
top venue

Abstract

Control invariance validates that dynamical systems have a control input that preserves a given property at all times. This paper introduces a set of sound axioms and proof rules in differential dynamic logic (dL) that enable verification of control invariance. First, the scalar and vector comparison principles, relating a system of differential equations to a comparison system such that invariance properties can be established more easily, are axiomatized in dL. This axiomatization primarily utilizes differential ghosts, which are proof-theoretic generalizations of comparison systems. Next, with the comparison principles serving as the basis, comparison invariants are introduced, and sound axioms and proof rules are derived. Comparison invariants reduce the question of control invariance to a functional inequality on its Lie derivative for a suitable class of functions, moreover, the right choice of function can result in decidable arithmetic. Furthermore, the perennially popular control barrier functions (CBFs) used in safety-critical control are shown to be a special instance of comparison invariants. This yields an axiomatization of CBFs that leads to a dedicated set of proof rules. The rules allow for the verification of CBFs, which are traditionally used for synthesizing safe controllers without verification. Lastly, comparison invariants are shown to unify several other safety verification techniques, including Darboux invariants and differential invariants, further cementing their versatility.

Comment
To appear in the 26th Conference on Logic for Programming, Artificial Intelligence, and Reasoning
Journal ref
Proceedings of the 26th Conference on Logic for Programming, Artificial Intelligence, and Reasoning, 2026, vol 112, pages 381-400
DOI
10.29007/5zft

Closest papers

Nearest neighbours by meaning across the whole index.

Linear Axiomatization of Linear Differential Equations

cs.LO math.LO ·2026-10-20 ·Long Qian, André Platzer
similarity 0.62
Abstract

This article presents an axiomatization of linear differential equations that is complete for topologically open properties with compact initial conditions and time horizons by proving them deductively via a sound reduction to formulas of linear real arithmetic. Indeed, linearity is preserved: linear differential invariants are complete for open properties of linear differential equations and reduce with a linear number of Lie derivatives (per atom) to linear real arithmetic. In particular, this article shows that the linear fragment of differential dynamic logic (dL), a modal extension of standard first-order logic over the reals satisfies these completeness properties. By establishing completeness within decidable linear real arithmetic, the need for proving sophisticated nonlinear formulas of real arithmetic is circumvented. Furthermore, this article establishes generalizations to the nonlinear fragment of dL that enable the practical certification of reachability computations, validating the output of external computations in dL with machine-checkable proofs.

0.36

On the Degree of Safety: Beyond Safe or Unsafe with Control Barrier Functions

eess.SY ·2026-09-03 ·Ruoyu Lin, Fabio Pasqualetti, Magnus Egerstedt
similarity 0.61
Abstract

A valid control barrier function (CBF) certifies if its represented safe set can be rendered forward invariant, and the sign of its value indicates whether a state is safe or not, but it does not quantify a degree of safety beyond the binary indication. In this paper, we show that among valid CBFs representing the same safe set, interior values and gradients can be changed arbitrarily, so neither quantity determines a degree of safety that is independent of how the set is represented. We also show that whether a candidate CBF-based inequality constraint is feasible does not by itself quantify a degree of safety. In particular, infeasibility can occur either because the safe set is not controlled invariant or because the candidate CBF representation fails. This motivates our distinction between intrinsic and representational infeasibility. Finally, we introduce the invariance authority demand (IAD), a representation-independent degree of safety that quantifies the control authority required for maintaining safety and can be used to guide actuator redesign or safe set repair.

0.28

Proof Checking Continuous Reachability

cs.LO math.LO ·2026-11-18 ·Long Qian, André Platzer
theory similarity 0.60
Abstract

This paper introduces a proof format and proof checker for certifying reachability computations of ordinary differential equations (ODEs) with polynomial vector fields. Establishing a proof checking framework for certifying ODE reachability is similar to the checking of UNSAT proofs for propositional satisfiability solving, but it is even more important due to the challenges inherent in dealing with ODEs, and even more challenging due to the numerical nature of ODE reachability algorithms. The proofs are expressed in differential dynamic logic (dL), and can be independently verified with symbolic theorem provers for dL (e.g. KeYmaeraX). Such proofs are naturally generated by reachability algorithms based on Taylor models, a popular technique to obtain rigorous bounds on approximations of ODEs. This paper proves the completeness of such proofs - if an approximation was correctly computed by some (possibly untrusted) reachability algorithm via Taylor models, then a corresponding proof in dL can be automatically generated and checked to be correct in dL's proof calculus. A dedicated proof checker is implemented in Lean4 for improved performance, which is capable of formally verifying benchmarks in the ARCH competition.

0.23

Input-to-State Safety and Small-Gain Theorems for Large-Scale Nonlinear Systems

eess.SY ·2026-11-10 ·Jianqiang Wang, Tengfei Liu, Zhong-Ping Jiang
theory similarity 0.58
Abstract · 16 pages, 7 figures

This paper studies the safety verification problem for a general class of large-scale systems characterized by multiple safety indicator functions. Each safety indicator function satisfies a trajectory-based input-to-state safety (ISSf) estimate that provides a lower bound on its value along system trajectories in terms of the initial state, external inputs, and the other safety indicator functions, whose influence is quantified by continuous and nondecreasing gain functions. Within this framework, we establish a safety-oriented small-gain theorem and its corresponding corollaries that enable compositional and scalable safety verification of the interconnected system, provided that the interconnection gain functions satisfy a small-gain condition on the negative real axis. This condition concerns only the neighborhood of the safety boundary, thereby facilitating the application of our results to safety verification of multi-agent systems under distributed control. Our proof combines small-gain techniques with the lower-bound structure of ISSf estimates and develops an inductive comparison argument that establishes the ISSf property for the overall system throughout the maximal interval of existence. As an application, we establish robust safety for the natural distributed "half-spring" controller, theoretically supporting the computationally efficient and inspiring approach to safety-critical control of multi-agent systems in the presence of obstacles and external disturbances.

0.18

Unified Overview of Safety Certificate Functions: Techniques from Hamilton--Jacobi Reachability and Control Barrier Functions

cs.RO eess.SY ·2026-11-05 ·Hao Wang, Max Cohen, Zeyuan Feng, Donggeon David Oh, Oswin So +7 more
surveybenchmark similarity 0.57
Abstract

Safety is a central concern in modern autonomous systems. Safety certificates---functions whose existence guarantees that a system meets its safety specification---have long been used as a principled tool for rigorously reasoning about safety. Methods for synthesizing such certificates are scattered across research areas, with little guidance on when to use a particular approach. This tutorial provides a holistic treatment of safety certificate synthesis centered on two widely used families: Hamilton--Jacobi (HJ) reachability analysis and control barrier functions (CBFs). For each family of methods, we first introduce its general formulation, along with classical and learning-based tools for certificate synthesis. Next, we introduce two benchmark problems consisting of vehicle systems of differing complexity to assess the certificate quality of different synthesis methods and their effectiveness in safety-critical control. We use these benchmarks to compare various methods and provide practical guidance for selecting an approach.

0.24

A Reachability-based Safety Certificate for Dynamical System Motion Policies

cs.RO ·2026-09-29 ·Aditya Vats, Tianyi Xia, Nadia Figueroa
similarity 0.57
Abstract

Dynamical Systems (DS) are reactive motion policies representing vector fields trained with theoretical guarantees of stability and convergence. To ensure safety during deployment in unknown environments they must be locally reshaped, either through modulation or geometric control barrier function strategies. However, depending on the geometry of the obstacles and the complexity of the DS, these local strategies can lead the system to unavoidable collisions or spurious attractors. In this work, we certify safety with a value function drawn from the notion of backward reachability tube, which measures the worst-case safety along a rollout trajectory of the nominal DS. Usually, such a value function is intractable for a controlled system due to curse of dimensionality. We show that in the DS-based learning-from-demonstration setting, the absence of a control input collapses the reachability problem to a deterministic rollout, and the presence of certain stability conditions truncates the infinite horizon to a finite one, resulting in a well-defined value function. We further show that the value function we devised is the maximal forward-invariant subset of the obstaclefree region for the nominal DS flow. The application of this certificate function is validated across five DS constructions - analytical, Neural ODE, diffeomorphic latent space, LPV-DS, SE(3)and validate it on a Franka manipulator. Modulation and geometric CBFs also suffer from saddle point in cases of headon approach towards an unsafe zone. We show that CBF-on-V avoids this pitfall entirely.

0.21

Safe Control of Semi-Explicit Differential-Algebraic Systems: Control Barrier Functions with SOS Verification

eess.SY math.OC ·2026-10-07 ·Mohamad H. Kazma, Hongchao Zhang, Abdallah A. Albustami, Ben Wooding, Meiyi Ma +2 more
similarity 0.56
Abstract

Differential-algebraic equation (DAE) systems arise in power networks, multibody mechanics, and chemical processes, where algebraic constraints couple dynamic and algebraic states. Standard control barrier function (CBF) methods, designed for ordinary differential equations, fail for DAE systems because the algebraic constraints impose compatibility requirements that may render safety filters infeasible. This paper develops a safety-critical control framework for semi-explicit DAE systems using CBFs that consider compatibility with the algebraic constraints, termed DAE-aware CBFs. We construct projected vector fields on the constraint manifold to account for the hidden dynamics, while ensuring compatibility conditions that keep the algebraic constraints satisfied. We then present sum of squares (SOS) verification conditions that certify both correctness and feasibility of the resulting DAE-aware CBF. The framework is validated on power system case studies.

0.45

Verifying Autoware Controller Node by Combining Model Verification and Runtime Monitoring

cs.SE ·2026-10-11 ·Daisuke Ishii
publishedcode/data similarity 0.56
Abstract · 34 pages, 9 figures, 2 tables. Extended version of a paper accepted at SEFM 2026

Formal modeling and verification of autonomous driving systems remain challenging due to the vast operational space and the complexity of the control logic. We propose a hybrid verification approach that combines formal model verification and runtime monitoring for the trajectory-following control node of Autoware, an open-source autonomous driving platform. We formalize the controller as a hybrid system in differential dynamic logic (dL), and introduce an abstract model that captures the essential control dynamics. We then prove safety and liveness properties of the model using the KeYmaera X proof assistant. Complementarily, we monitor the constraints that assure the compatibility between the model and the Autoware implementation across numerical simulation runs using the Autoware toolchain, quantifying to what extent the implementation's behavior is subsumed by the verified model. The experimental results confirmed that (i) monitoring provides a sound evaluation of target following with accuracy bounds, and (ii) the Autoware implementation reaches the target with an accuracy of approximately 0.2-0.4 (m) in position and 0.8 (m/s) in velocity.

0.45