💻 computer science

Stochastic Barrier Certificates in the Presence of Dynamic Obstacles

This paper introduces time-invariant and time-varying stochastic barrier certificates formulated as convex sum-of-squares programs to provide less conservative, tractable probabilistic safety guarantees for discrete-time systems navigating environments with dynamic obstacles.

Original authors: Rayan Mazouz, Luca Laurenti, Morteza Lahijanian

Published 2026-04-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Rayan Mazouz, Luca Laurenti, Morteza Lahijanian

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are driving a self-driving car through a busy city. The car is a bit "drunk" (it has random noise or uncertainty in its sensors and movements), and the city is full of other cars, pedestrians, and delivery drones moving around unpredictably. Your goal is to get from point A to point B without crashing.

The big question is: How can we mathematically prove that the car will stay safe, even with all this chaos?

This paper introduces a new, smarter way to answer that question using something called "Stochastic Barrier Certificates."

Here is the breakdown in simple terms:

1. The Problem: The "Static" vs. "Dynamic" Trap

Imagine you are trying to draw a safety fence around your car's path.

The Old Way (Time-Invariant): Imagine you try to draw one giant, static fence that covers the entire city for the whole trip. Because the other cars are moving, this fence has to be huge and clumsy to ensure no one ever touches it. It's like trying to catch a fish with a net that is so big it covers the whole ocean. It's safe, but it's very conservative (it assumes the worst-case scenario constantly) and hard to calculate.
The "Interpolation" Way: Some researchers tried to make the fence slightly flexible, like a rubber band that stretches a little. But this method often breaks down when the trip gets long or the traffic gets complex, leading to loose, inaccurate safety guarantees.

2. The Solution: The "Time-Varying" Shield

The authors propose a new approach: The Time-Varying Barrier Certificate.

Instead of one giant, clumsy fence, imagine a smart, shifting shield that changes shape every single second.

At 1:00 PM, the shield is shaped to avoid a pedestrian crossing the street.
At 1:01 PM, the pedestrian has moved, so the shield instantly reshapes itself to avoid a new threat.
At 1:02 PM, it reshapes again for a delivery drone.

This shield is built using Bellman's Optimality Principle (a fancy way of saying "working backward from the finish line"). Instead of guessing the whole path at once, the system calculates the safety of the next step based on the safety of the step after that. This allows the shield to be tight and precise, hugging the danger zones closely without being overly cautious.

3. The Magic Ingredient: Sum-of-Squares (SOS)

You might ask, "How do we actually calculate these shifting shields? Isn't that impossible?"

The authors use a mathematical trick called Sum-of-Squares (SOS). Think of this as a special type of Lego set.

Normally, proving a complex curve is safe is like trying to build a castle out of wet sand.
SOS turns that sand into hard, uniform Lego bricks (polynomials).
Because these "bricks" are so well-behaved, computers can quickly snap them together to build the perfect shield using a method called Semidefinite Programming. It turns a messy, impossible problem into a clean, solvable puzzle.

4. The Results: Tighter, Faster, Smarter

The paper tested this on various scenarios, from a wobbling robot arm to a 4D drone flying near moving obstacles.

The Old Methods: Often gave up or said, "There is a 0% chance of safety" because the math got too messy, or they gave a very low safety guarantee (e.g., "You have a 20% chance of not crashing").
The New Method: Consistently proved much higher safety (e.g., "You have a 98% chance of not crashing").
The Analogy: If the old methods were like a security guard who says, "Don't go outside, it's too dangerous," the new method is like a highly trained bodyguard who says, "It's safe to walk here, but watch out for that specific person moving that way."

Summary

This paper gives self-driving cars and robots a superpower: the ability to calculate a precise, moving safety net that adapts to dynamic obstacles in real-time. By using a "working backward" strategy and turning complex math into a solvable puzzle, they can prove with high confidence that a system will stay safe, even in a chaotic, moving world.

In short: They replaced a giant, clumsy, static safety net with a nimble, shape-shifting, high-tech force field that actually works.

1. Problem Statement

The paper addresses the challenge of providing formal safety guarantees for discrete-time, continuous-space stochastic dynamical systems operating in environments with dynamic obstacles.

System Dynamics: The system evolves according to $x_{k+1} = f(x_k, w_k)$ , where $w_k$ is i.i.d. noise. The dynamics are nonlinear and subject to uncertainty.
Dynamic Obstacles: The environment contains $N_o$ moving obstacles. Each obstacle $j$ has a configuration $o^j_k$ that evolves deterministically (or stochastically) over time, defining a time-varying unsafe region $X^j_o(o^j_k)$ .
Objective: The goal is to verify Probabilistic Safety ( $P_s$ ), defined as the probability that the system remains within a safe set $X_s$ and avoids all dynamic obstacles over a finite horizon $H$ .
Challenge: Existing methods often assume static environments or rely on a single, time-invariant barrier certificate. These approaches fail to capture the temporal structure of moving obstacles, leading to overly conservative safety bounds or computational intractability (the "curse of dimensionality") when attempting to model time explicitly.

2. Methodology

The authors propose a framework based on Stochastic Barrier Functions (SBFs) and Sum-of-Squares (SOS) optimization. They introduce two distinct formulations:

A. Time-Invariant Approach (Centralized)

Concept: The system state and obstacle configurations are stacked into an augmented "meta-state" $z_k = (x_k, o^1_k, \dots, o^{N_o}_k)$ .
Mechanism: By lifting the problem to this higher-dimensional space, the time-varying obstacle sets become static sets in the augmented space. A single, time-invariant barrier certificate $B(z)$ is synthesized.
Limitation: While this converts the problem to a static one, it suffers from the curse of dimensionality. As the number of obstacles or the complexity of their dynamics increases, the dimension of the augmented state grows, making the functional optimization problem computationally intractable.

B. Time-Varying Approach (Dynamic Programming)

Concept: Instead of augmenting the state, the authors introduce a time-varying barrier certificate $B(x, i)$ , where $i$ represents the time step remaining in the horizon.
Mechanism:
- The formulation is grounded in Bellman's optimality principle (Dynamic Programming).
- It utilizes a backward recursion: The safety value at step $i$ depends on the expected safety value at step $i-1$ .
- The certificate explicitly accounts for the time-varying unsafe set $X_u(i) = (R^n \setminus X_s) \cup X_o(i)$ .
Optimization: By restricting the barrier functions to be polynomials, the synthesis conditions are relaxed into a convex Sum-of-Squares (SOS) program. This allows for tractable numerical solution via Semi-Definite Programming (SDP).
Advantage: This approach avoids the state augmentation dimensionality issue. It captures the temporal structure directly, allowing the certificate to adapt to the specific geometry of obstacles at each time step, resulting in less conservative bounds.

3. Key Contributions

Dual Formulation: The paper presents both time-invariant (augmented space) and time-varying (DP-based) SBF formulations for discrete-time stochastic systems with dynamic obstacles.
Dynamic Programming Characterization: The time-varying formulation leverages Bellman's principle to derive a backward recursion. This provides a theoretical guarantee of reduced conservatism compared to time-invariant methods and existing interpolation-based approaches.
Tractable Synthesis: The authors demonstrate that by restricting certificates to polynomials, the time-varying conditions can be formulated as a convex SOS program, enabling efficient and numerically stable synthesis.
Formal Guarantees: The method provides certified lower bounds on the probability of safety, explicitly handling the interaction between stochastic system dynamics and deterministic (or stochastic) obstacle trajectories.

4. Experimental Results

The framework was evaluated on various nonlinear systems (Unstable 1D/2D, Oscillator, Lotka-Volterra, Dubin's Car, Quadrotor) with varying horizons ( $H$ ) and dynamic obstacles.

Comparison: The proposed time-varying method was compared against:
1. Time-invariant SBFs (augmented space).
2. Interpolation-based SBFs (state-of-the-art).
Performance Metrics: Safety probability lower bounds ( $P_s$ ) and computation time ( $\tau$ ).
Key Findings:
- Tighter Bounds: The time-varying approach consistently achieved significantly higher safety probability bounds (often close to 0.90–0.99) compared to the other methods, which often collapsed to 0.00 or very low values (e.g., 0.12) as the horizon increased.
- Scalability: While time-invariant methods required high-degree polynomials and often timed out (1000s limit) in high-dimensional or complex scenarios, the time-varying approach remained computationally tractable.
- Accuracy: Monte Carlo simulations confirmed that the certified bounds from the time-varying method were tight, closely matching empirical safety probabilities.
- Dynamic Obstacles: In scenarios with multiple moving obstacles, the time-invariant and interpolation methods failed to scale or provided trivial guarantees, whereas the time-varying method maintained robust performance.

5. Significance

This work bridges a critical gap in the formal verification of cyber-physical systems (CPS).

Overcoming Conservatism: It demonstrates that explicitly modeling the temporal evolution of safety constraints (via time-varying certificates) is superior to treating dynamic obstacles as static augmented states.
Scalability: By avoiding state augmentation, the method scales better with the number of obstacles and system complexity, making it applicable to real-world multi-agent or navigation problems.
Practical Applicability: The use of SOS programming ensures that the method is not just theoretically sound but computationally implementable for nonlinear systems, offering a reliable tool for safety-critical applications like autonomous driving and robotics in dynamic environments.