Stochastic Barrier Certificates in the Presence of Dynamic Obstacles
Rayan Mazouz, Luca Laurenti, Morteza Lahijanian · 2026
Read Stochastic Barrier Certificates in the Presence of Dynamic Obstacles by Rayan Mazouz, Luca Laurenti, Morteza Lahijanian (2026) 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-2604-20208.txt.
Introduction
Mazouz, Laurenti, and Lahijanian study safety checks for random systems in shifting settings with moving obstacles. They give fixed and varying barrier certificates that bound from below the chance of staying safe over a set time span. The varying form uses Bellman optimality ideas to catch time structure, giving tighter bounds than current best methods. Keeping certificates in polynomial form turns the varying build into a convex sum-of-squares program, and tests on nonlinear systems with moving obstacles show tight, scalable guarantees.
Catalog record
| CREATOR | Rayan Mazouz, Luca Laurenti, Morteza Lahijanian |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44403 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.20208
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stochastic Barrier Certificates in the Presence of Dynamic Obstacles Rayan Mazouz, Luca Laurenti, Morteza Lahijanian Abstract Safety of stochastic dynamic systems in environments with dynamic obstacles is studied in this paper through the lens of stochastic barrier functions. We introduce both time-invariant and time-varying barrier certificates for discrete-time, continuous-space systems subject to uncertainty, which provide certified lower bounds on the probability of remaining within a safe set over a finite horizon. These certificates explicitly account for time-varying unsafe regions induced by obstacle dynamics. By leveraging Bellman’s optimality perspective, the time-varying formulation directly captures temporal structure and yields less conservative bounds than state-of-the-art approaches. By restricting certificates to polynomial functions, we show that time-varying barrier synthesis can be formulated as a convex sum-of-squares program, enabling tractable optimization. Empirical evaluations on nonlinear systems with dynamic obstacles show that time-varying certificates consistently achieve tight guarantees, demonstrating improved accuracy and scalability over state-of-the-art methods. I Introduction Complex dynamical systems operating under uncertainty make safety guarantees a central challenge in cyber-physical systems [ 1 ] . In many real-world settings, these systems operate in environments that evolve over time, such as the presence of moving obstacles or time-varying constraints. Providing rigorous guarantees of system behavior in these settings requires reasoning over continuous state spaces, nonlinear stochastic dynamics, and temporally evolving safety specifications. Certificate-based methods, in particular stochastic barrier functions (SBFs) [ 2 , 3 , 4 ] have emerged as a powerful tool for certifying probabilistic safety of stochastic systems. However, existing formulations largely assume static environments and rely on a single certificate enforced uniformly across time, limiting their ability to capture the induced temporal structure. In this work, we address these challenges by developing a time-varying certificate-based framework that provides formal guarantees for stochastic systems evolving in dynamic environments. Existing certificate-based methods for finite-horizon safety guarantees of stochastic systems typically rely on a single barrier certificate enforced uniformly across all time steps [ 5 , 6 , 7 , 8 ] , which is inherently suboptimal as it ignores the sequential nature of the stochastic evolution. Further, the time-dependent structure of the safety constraints, particularly in the presence of dynamic obstacles, are not directly captured. Recent work introduces interpolation-based barrier certificates to incorporate temporal variation [ 9 ] ; however, the resulting guarantees are constructed via Markov’s and Boole’s inequalities, which introduce additional conservatism in the computed probability of safety. Further, due to bilinear terms in the martingale condition, the formulation does not lend itself to a convex functional optimization problem. Consequently, existing formulations that incorporate temporal structure in the certificate construction remain limited in their scalability and ability to provide tight guarantees. In this paper, we focus on time-varying SBF certificates for discrete-time nonlinear stochastic systems with continuous spaces. First, we introduce a time-invariant approach that incorporates dynamic obstacles in an augmented space. Then, we introduce a framework grounded in Bellman’s optimality principle, i.e., dynamic programming (DP), which captures the backward reachability structure of safety and yields temporal guarantees over finite horizons. This perspective naturally motivates varying certificates that evolve over time, thereby providing tighter bounds on safety compared to the time-invariant approach, and other state-of-the-art methods [ 9 ] . Moreover, by restricting the dynamics to the space of polynomial functions in the experiments, the proposed conditions admit a tractable sum-of-squares (SOS) relaxation [ 10 , 11 ] , enabling numerically stable synthesis [ 12 , 13 ] via semi-definite programming [ 14 ] . We evaluate the proposed framework on a range of nonlinear systems with dynamic obstacles, confirming the theoretical guarantees and demonstrating improved probability bounds and scalability compared to existing formulations. In short, the main contributions of this paper are: • A SBF certificate formulation encompassing both time-invariant and time-varying constructions for discrete-time stochastic systems over finite -horizon settings, providing certified lower bounds on safety probabilities while accounting for dynamic obstacles . • A dynamic programming–based characterization of time-varying certificates, establishing reduced conservatism in the resulting probability bound. • Validation of the theoretical guarantees, along with benchmarking comparisons that highlight the advantages of the proposed time-varying formulation over existing certificate approaches. Related Work Reasoning about safety in stochastic systems with dynamic, time-varying environments has been addressed from multiple perspectives, including motion planning, control and formal verification. Approaches for safe motion planning with dynamic obstacles [ 15 , 16 ] typically rely on trajectory optimization or chance-constrained formulations, enabling (real-time) avoidance under uncertainty. Similarly, multi-agent and multi-robot frameworks [ 17 ] focus on coordinating interactions in dynamic settings. However, these methods primarily operate at the planning level, and do not provide certificate-based guarantees that formally bound safety probabilities over continuous state spaces. To obtain such guarantees, one must instead reason at the level of system-wide certificates. Barrier-based methods provide this perspective, with SBFs enabling verification and control synthesis via functional conditions that can often be cast as convex programs. While barrier-based methods provide this certificate perspective, they are typically conservative in practice, as the imposed functional conditions restrict the set of admissible certificates. Although extensions such as piecewise SBFs [ 7 , 18 ] reduce this conservatism, they remain confined to time-invariant formulations. Other approaches rely on learning based or data-driven approximations of the certificate [ 19 , 20 , 21 , 22 , 23 ] ; however, such methods remain difficult to verify against hard safety constraints [ 19 , 22 ] or do not explicitly capture the temporal evolution of the certificate [ 20 , 21 , 23 ] . Overall, existing methods either lack formal certificate guarantees in dynamic environments or fail to fully exploit temporal structure in a tractable manner. In contrast, this work develops a DP–based formulation of time-varying stochastic barrier certificates that directly encodes temporal evolution that yield tight bounds. II Problem Formulation We consider a discrete-time stochastic system described by the stochastic difference equation \mathbf{x}_{k+1}=f(\mathbf{x}_{k},\mathbf{w}_{k}), (1) where k\in\mathbb{N}_{0} is the time step, \mathbf{x}_{k}\in\mathbb{R}^{n} is the state at time step k , f:\mathbb{R}^{n}\times\mathbb{R}^{w}\to\mathbb{R}^{n} is a Lipschitz continuous vector field, and \mathbf{w}_{k}\in\mathbb{R}^{w} is an i.i.d. random variable distributed according to p_{\mathbf{w}} . Intuitively, \mathbf{x}_{k} represents a general stochastic process whose evolution may be governed by nonlinear dynamics and non-additive noise. Given a state x\in\mathbb{R}^{n} and a Borel-measurable set X , we define the transition kernel of System ( 1 ) as T(X\mid x):=\int_{\mathbb{R}^{\mathrm{w}}}\mathbf{1}_{X}(f(x,w))p_{\mathbf{w}}(dw), (2) where \mathbf{1}_{X}(x)=1 if x\in X and 0 otherwise. It follows that, from an initial state x_{0}\in\mathbb{R}^{n} , kernel T defines a unique probability measure \mathrm{Pr}^{x_{0}} over trajectories of System ( 1 ) [ 24 ] . We consider the setting where System ( 1 ) shares the space with N_{o}\in\mathbb{N}_{\geq 1} dynamic obstacles, i.e., unsafe sets (e.g., other agents). Each obstacle j\in\{1,\ldots,N_{o}\} is a compact set, whose geometry at time k is parameterized by configuration o_{k}^{j}\in\mathbb{R}^{p_{j}} , e.g., configuration defined by center and orientation. Configuration o_{k}^{j} evolves according to o^{j}_{k+1}=g^{j}(o_{k}^{j}), (3) where g^{j}:\mathbb{R}^{p_{j}}\to\mathbb{R}^{p_{j}} is a Lipschitz continuous map. Let X^{j}_{o}:\mathbb{R}^{p_{j}}\to\mathbb{R}^{n} be the function that maps the obstacle configuration o^{j}\in\mathbb{R}^{p_{j}} to the set of points X^{j}_{o}(o^{j}_{k})\subset\mathbb{R}^{n} that it occupies in the state space. A collision occurs between System ( 1 ) and obstacle j at time k if \mathbf{x}_{k}\in X_{o}^{j}(o^{j}_{k}) . In this work, we focus on quantifying probabilistic safety , which,