CS Paper Radar

Sufficient and Necessary Continuous Barrier-like Conditions for Discrete-Time Stochastic Reach-Avoid Verification

Bai Xue

eess.SY ·submitted 2026-09-21 00:58 UTC · v1

Abstract

This paper develops necessary and sufficient barrier-like characterizations using continuous barrier functions for infinite-horizon reach-avoid verification of discrete-time stochastic systems. Existing results establish necessary and sufficient conditions in terms of functional inequalities involving measurable or lower semicontinuous barrier functions. However, the limited regularity of such functions may hinder their numerical approximation and computational synthesis. Building on our previous barrier-like condition for finite-horizon reach-avoid verification, we show that this condition can also be used for infinite-horizon reach-avoid verification and, under a uniform absolute continuity condition on the transition kernels, admits a continuous barrier function whenever the exact reach-avoid probability is strictly larger than the prescribed threshold for every state in the initial set. We further show that the resulting continuous barrier function can be uniformly approximated by a polynomial one while preserving the required barrier-like conditions. For polynomial systems, we formulate these conditions as polynomial positivity constraints over compact basic semialgebraic sets. Putinar's Positivstellensatz then converts the positivity conditions into sum-of-squares (SOS) certificates, yielding semidefinite programming (SDP) formulations for synthesizing polynomial barrier functions. We establish both soundness and completeness of the resulting SOS-based procedure. Finally, two numerical examples illustrate the theoretical results and demonstrate the resulting SDP approach.

Closest papers

Nearest neighbours by meaning across the whole index.

Sufficient and Necessary Smooth Barrier-like Conditions for Continuous-Time Stochastic Reach-Avoid Verification

eess.SY ·2026-09-21 ·Bai Xue
similarity 0.83
Abstract

In this paper, we study infinite-horizon reach-avoid verification for continuous-time stochastic systems modeled by stochastic differential equations (SDEs). We formulate this problem within a barrier-function-based framework, which transforms the verification problem into an existence problem for barrier functions satisfying barrier-like conditions expressed as functional inequalities. We provide sufficient and necessary barrier-like conditions in terms of polynomial barrier functions for infinite-horizon reach-avoid verification under suitable regularity and uniform ellipticity assumptions. We first construct a discounted value function that characterizes lower bounds on the reach-avoid probability. We then show that it is the unique classical solution of an associated elliptic Dirichlet problem. Based on this characterization, we further show that the barrier-like condition proposed in our previous work on finite-horizon reach-avoid verification is not only sufficient for infinite-horizon reach-avoid verification but also necessary whenever the reach-avoid probability is strictly larger than the specified threshold. In particular, whenever the reach-avoid probability is strictly larger than the specified threshold fro every state in the initial set, polynomial barrier functions satisfying this barrier-like condition exist. Furthermore, when the system dynamics are polynomial, we formulate the problem of finding polynomial barrier functions satisfying this barrier-like condition as sum-of-squares (SOS) programs, which are shown to be sound and complete. Finally, we demonstrate the theoretical results on two numerical examples.

0.33

Sufficient and Necessary Smooth Barrier-Like Conditions for Continuous-Time Finite-Horizon Safety Verification

eess.SY ·2026-11-03 ·Bai Xue
similarity 0.82
Abstract

We study finite-horizon safety verification for continuous-time stochastic systems modeled by stochastic differential equations. Given an open and bounded safe set, a compact initial set, a finite time horizon, and a prescribed violation-probability threshold, the objective is to certify that the exit probability from the safe set before the horizon remains below the threshold. Under uniform ellipticity of the diffusion matrix and regularity of the safe-set boundary, we develop a time-dependent barrier-like condition expressed as a set of functional inequalities, obtained by relaxing a parabolic initial-boundary value problem associated with the exit probability. If a function satisfies the condition, then the probability of leaving the safe set before the horizon is guaranteed to remain below the threshold. Conversely, when the exit probability is strictly smaller than the prescribed threshold uniformly over the initial set, the barrier-like condition is also necessary: there exists a smooth function satisfying it. Furthermore, when the dynamics are polynomial and the set descriptions are semialgebraic, the problem of verifying the condition admits a sum-of-squares formulation that is both sound and complete, yielding a complete degree hierarchy for finite-horizon stochastic safety verification.

0.21

Converse Barrier Certificates for Set-Based Stochastic Reach-Avoid Verification

eess.SY ·2026-08-31 ·Bai Xue, C. -H. Luke Ong
similarity 0.80
Abstract

Recent work established sufficient and necessary barrier-like conditions for infinite-horizon reach-avoid verification of stochastic discrete-time systems from a single initial state. Whether such a converse characterization extends to a set of initial states, however, remains open. In this paper, we answer this question affirmatively for compact initial sets. We consider a uniform reach-avoid specification requiring the reach-avoid probability to exceed a prescribed threshold for every initial state in a compact set. Under appropriate assumptions, including continuous system transitions, together with a strict uniform probability margin, we extend the pointwise converse characterization to the uniform setting.

0.42

Quantitative coverability for probabilistic well-structured transition systems

cs.LO cs.FL ·2026-09-22 ·Raphaël Faure, Alain Finkel, Gaspard Fougea, Lina Ye
similarity 0.60
Abstract · 25 pages

Well-structured transition systems (WSTS) provide a classical framework for the verification of infinite-state systems, but their probabilistic extensions lack a unified treatment of quantitative coverability: path-enumeration algorithms assume a finite branching degree, while alternative approximation schemes defer some computations, such as probabilities over a bounded horizon, to the model at hand. We introduce probabilistic well-structured transition systems (pWSTS), Markov chains over countable state sets whose underlying transition systems are WSTS, with no a priori assumption on the branching degree. This class encompasses any WSTS equipped with a Markov kernel, such as probabilistic vector addition systems (pVAS) and probabilistic lossy channel systems (pLCS). For an effective subclass, we solve the approximate quantitative coverability problem over bounded horizons, and over infinite horizons under decisiveness, requiring no probabilistic information beyond individual transition probabilities. We then identify a general source of decisiveness: every stochastically monotone pWSTS is decisive with respect to every upward-closed set. We finally instantiate the framework on multi-type Galton--Watson processes, a classical model of population dynamics whose offspring distributions may have infinite support. Under mild assumptions on the reproduction laws, these processes are effective pWSTS, and they are stochastically monotone, hence decisive. Approximate quantitative coverability is therefore computable for them over both horizons, with a proof that uses none of the traditional tools: neither generating functions nor any case distinction between regimes.

0.41

Reach-Avoid Certificates for Contact-based Stochastic Hybrid Systems

eess.SY cs.ROmath.PR ·2026-10-12 ·Tianyi Xia, Ryan K. Cosner
theory similarity 0.60
Abstract

This work studies certified reach-avoid control of stochastic hybrid systems in which a stochastic differential equation governs continuous flow and a controlled stochastic kernel governs guard-triggered resets. The input appears only in the reset kernel, where it determines the post-jump distribution. Certificates for such systems have so far assumed spontaneous or controller-chosen jump times, a finite horizon, or discrete-time dynamics; we certify, over the infinite horizon, that the target is reached before the unsafe set with at least a prescribed probability. First, we introduce reach-avoid contact certificates, whose flow and jump conditions are imposed only on a sublevel corridor, and prove that any such certificate with a compatible reset policy meets the specification; a pointwise safety filter extends this guarantee from verification to control by constraining arbitrary nominal controllers. Next, we prove that executions are non-Zeno and bound the expected settling time and reset count. We frame certificate search as a linear program over any twice-differentiable dictionary followed by independent verification. We illustrate our approach via comparisons where the certified region is a subset covering 93.6\% of the ground truth and where our certificate-based safety filter reaches the goal while reducing collisions from 68 to zero across 200 episodes of a dribbling ball problem.

0.26

Quantitative Reachability Properties Beyond Decisiveness

cs.LO cs.FL ·2026-10-26 ·Raphaël Faure, Alain Finkel, Lina Ye
similarity 0.58
Abstract · 38 pages

Decisiveness is central to reachability algorithms for infinite Markov chains, but is a qualitative notion: it guarantees that path-enumeration algorithms terminate, without an a priori bound on the horizon. We study decisiveness quantitatively of Markov chains, and apply our results to the approximate quantitative coverability problem for effective probabilistic well-structured transition systems (pWSTS). We introduce truncation sets, which represent the horizons sufficient to approximate the reachability probability within a precision $\varepsilon$. These sets reformulate decisiveness quantitatively, and their elements can be computed when it is decisive. To obtain such horizons, before any exploration, we introduce geometrically reachable sets, for which the probability of not reaching them within n steps decreases exponentially in n, up to a prefactor depending on the initial state. Horizons valid for all initial states exist iff this prefactor can be chosen uniformly for boundedly coarse chains. For such pWSTS, including probabilistic vector addition systems and Galton-Watson processes, we obtain a priori global horizons growing at most logarithmically in $1/\varepsilon$. In the non-uniform case, we give a drift condition ensuring the existence of a finite geometrically reachable set. Under this condition, we derive a priori horizons growing at most logarithmically in $1/\varepsilon$ and in the weight w(x) measuring the size of the initial state x. In both cases, we compute a horizon function whose evaluation on any initial state and precision requires only a constant number of elementary operations $(+, -, \times, / \text{ and } \log)$. For probabilistic lossy channel systems, this yields, to our knowledge, the first explicit a priori horizons from arbitrary initial states, and it extends to $ν$-pLCS, a new infinitely branching variant with probabilistic emissions.

0.23

Algebraic Characterization of Time-Varying Set Invariance

eess.SY ·2026-11-02 ·S. B. Alaoui, E. J. Wafo Wembe, A. Saoud
publishedtheory similarity 0.58
Abstract · The paper was accepted for publication in the CDC 2026

The verification of temporal forward invariance for dynamical systems subject to time-varying constraints is a foundational problem in the analysis of safety-critical systems. Existing methodologies rely on restrictive geometric assumptions, such as the Linear Independence Constraint Qualification (LICQ), or suffer from exponential computational complexity when applied to time-varying polytopes. This paper establishes a rigorous, unified, and computationally tractable framework for temporal safety verification. First, utilizing tools from nonsmooth analysis, we prove that a Nagumo-type geometric inclusion evaluated strictly on the boundary of the augmented graph is both necessary and sufficient for temporal forward invariance. Second, we provide an algebraic characterization of this condition requiring only the weaker Abadie Constraint Qualification (ACQ), generalizing standard Control Barrier Function (CBF) boundary conditions to non-smooth, multi-constraint domains. Finally, for the practical class of Linear Time-Invariant (LTI) systems with time-varying polytopic constraints, we deploy Farkas' Lemma to eliminate exponential vertex enumeration. By introducing a Lipschitz-bounded time-discretization scheme, we reduce the infinite-dimensional continuous-time verification problem to a finite, highly tractable set of decoupled Linear Programs (LPs).

0.39

Concentration-Based Probabilistic Reachability for Linear Systems under Multiplicative Uncertainty and Additive Noise

eess.SY ·2026-11-10 ·Kaouther Moussa, Kaito Ito, Hideaki Ishii
similarity 0.57
Abstract

This paper investigates probabilistic reachability for discrete-time linear stochastic systems subject to bounded multiplicative uncertainty and potentially unbounded additive noise. To address the conservatism of reachable sets constructed solely from covariance information, we develop two complementary approaches based on sub-Gaussian and sub-exponential matrix moment-generating-function characterizations. The sub-Gaussian approach relies on a worst-case envelope over the uncertainty support, whereas the sub-exponential approach exploits expectation-based propagation of the matrix variance proxy. Both approaches are used to construct probabilistic reachable sets with explicit probability guarantees, considering ellipsoidal confidence regions and half-space bounds. For the latter, we derive a necessary and sufficient condition under which the sub-exponential chance-constraint margin is no larger than its sub-Gaussian counterpart. Numerical results show that the proposed bounds can be less conservative than those based on the covariance, and illustrate the complementary nature of the two approaches across probability levels.

0.30