pith. sign in

arxiv: 2604.20208 · v1 · submitted 2026-04-22 · 💻 cs.RO · math.PR

Stochastic Barrier Certificates in the Presence of Dynamic Obstacles

Rayan Mazouz , Luca Laurenti , Morteza Lahijanian This is my paper

Pith reviewed 2026-05-10 00:44 UTC · model grok-4.3

classification 💻 cs.RO math.PR
keywords stochastic barrier functionsdynamic obstaclessum-of-squares optimizationsafety verificationfinite-horizon probability boundsdiscrete-time stochastic systemsconvex optimizationnonlinear dynamics
0
0 comments X

The pith

Time-varying stochastic barrier certificates provide tighter lower bounds on finite-horizon safety probabilities for systems facing dynamic obstacles than time-invariant methods.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies safety certification for stochastic discrete-time systems operating near moving obstacles whose positions change over time. It defines both time-invariant and time-varying barrier certificates that deliver certified lower bounds on the probability that the system stays inside a safe set for a finite number of steps. The time-varying version uses a Bellman optimality view to incorporate the exact timing of unsafe regions created by the obstacles, which produces less conservative probability bounds. Restricting the certificates to polynomial functions turns the search for the best certificate into a convex sum-of-squares program that can be solved efficiently.

Core claim

For discrete-time stochastic systems subject to time-varying unsafe sets induced by dynamic obstacles, a time-varying polynomial barrier certificate synthesized via convex sum-of-squares optimization yields a certified lower bound on the probability of remaining safe over a finite horizon; this bound is strictly tighter than the bound obtained from any time-invariant certificate because the time-varying formulation directly encodes the temporal evolution of the unsafe regions through Bellman's optimality principle.

What carries the argument

Time-varying stochastic barrier certificate: a polynomial function whose one-step expected decrease condition, formulated with respect to the time-dependent safe set, guarantees a finite-horizon safety probability lower bound when solved as a convex sum-of-squares program.

If this is right

  • The time-varying certificate produces a higher (less conservative) lower bound on safety probability than any time-invariant certificate on the same system and horizon.
  • Synthesis of the certificate reduces to a single convex semidefinite program once the barrier is restricted to polynomials.
  • The same convex program scales to nonlinear dynamics provided the one-step expectation can be bounded by sum-of-squares.
  • Empirical tests on nonlinear examples with dynamic obstacles show the bounds are tight and the computation remains tractable.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same Bellman-based construction could be applied to continuous-time systems by replacing the discrete sum-of-squares program with a differential inequality.
  • If obstacle motion is only partially known, the time-varying formulation could be combined with robust or learned uncertainty sets to maintain a guaranteed bound.
  • The resulting certificates could be used inside a receding-horizon planner to select controls that maximize the certified safety probability at each step.

Load-bearing premise

The obstacle trajectories are known in advance so that the exact sequence of time-dependent unsafe regions can be written down and used inside the barrier conditions.

What would settle it

Run Monte Carlo simulations of a nonlinear stochastic system with a known moving obstacle; if the fraction of trajectories that violate the safe set within the horizon exceeds the probability lower bound returned by the time-varying certificate, the claim is false.

Figures

Figures reproduced from arXiv: 2604.20208 by Luca Laurenti, Morteza Lahijanian, Rayan Mazouz.

Figure 1
Figure 1. Figure 1: Propagation of state distributions avoiding a static [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Monte Carlo simulations over a horizon ( [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper introduces time-invariant and time-varying stochastic barrier certificates for discrete-time, continuous-space stochastic systems subject to uncertainty and dynamic obstacles. These certificates provide certified lower bounds on the finite-horizon probability of remaining in a safe set. The time-varying formulation leverages Bellman's optimality perspective to capture temporal structure and reduce conservatism relative to prior methods; restricting certificates to polynomials allows synthesis to be cast as a convex sum-of-squares program. Empirical results on nonlinear systems with dynamic obstacles are reported to show tighter guarantees and better scalability than state-of-the-art approaches.

Significance. If the central claims hold, the work provides a tractable, convex-optimization route to certified safety probabilities for stochastic systems in environments with explicitly modeled moving obstacles. The Bellman-based time-varying construction and the polynomial/SOS restriction are explicit strengths that directly address conservatism and computational tractability; the reported empirical improvements on nonlinear examples further indicate practical utility for robotics and control applications.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'state-of-the-art approaches' is used without naming the specific baselines; explicit citations and a brief quantitative comparison should appear in the introduction or related-work section to ground the 'less conservative' claim.
  2. The problem statement should explicitly list the standing assumptions on obstacle dynamics (known, deterministic or stochastic) and on the form of the time-varying unsafe sets, as these are load-bearing for the time-varying certificate construction.
  3. Notation for the barrier functions and the Bellman operator should be introduced with a short table or consistent equation numbering to aid readability across the time-invariant and time-varying cases.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment of our work on time-varying stochastic barrier certificates. The recommendation for minor revision is appreciated. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's central derivation uses Bellman's optimality principle to formulate time-varying stochastic barrier certificates and then restricts to polynomials to obtain a convex SOS program. These steps are standard reductions from dynamic programming and semidefinite programming literature; they do not reduce the claimed bounds to fitted parameters, self-definitions, or self-citation chains. The time-varying unsafe sets are explicitly modeled from known obstacle dynamics (an external input), and the resulting certificates are optimized rather than tautologically defined. No load-bearing equation or claim collapses to its own inputs by construction. The approach is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The method rests on standard domain assumptions in stochastic control rather than new free parameters or invented entities.

axioms (2)
  • domain assumption System and obstacle dynamics are known and can be represented as discrete-time stochastic processes with explicit time-varying unsafe sets.
    Required to define the safe set evolution and probability bounds.
  • domain assumption Polynomial functions provide a sufficiently expressive class for barrier certificates in the systems considered.
    Enables reduction to convex sum-of-squares optimization.

pith-pipeline@v0.9.0 · 5437 in / 1231 out tokens · 41214 ms · 2026-05-10T00:44:38.118417+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Safety-critical advanced robots: A survey,

    J. Guiochet, M. Machin, and H. Waeselynck, “Safety-critical advanced robots: A survey,”Robotics and Autonomous Systems, vol. 94, 2017

    work page 2017

  2. [2]

    A barrier function approach to finite-time stochastic system verification and control,

    C. Santoyo, M. Dutreix, and S. Coogan, “A barrier function approach to finite-time stochastic system verification and control,”Automatica, vol. 125, p. 109439, 2021

    work page 2021

  3. [3]

    Formal synthesis of stochastic systems via control barrier certificates,

    P. Jagtap, S. Soudjani, and M. Zamani, “Formal synthesis of stochastic systems via control barrier certificates,”IEEE Transactions on Auto- matic Control, vol. 66, no. 7, pp. 3097–3110, 2020

    work page 2020

  4. [4]

    Safety guarantees for neural network dynamic systems via stochastic barrier functions,

    R. Mazouz, K. Muvvala, A. Ratheesh Babu, L. Laurenti, and M. Lahi- janian, “Safety guarantees for neural network dynamic systems via stochastic barrier functions,”Advances in Neural Information Process- ing Systems, vol. 35, pp. 9672–9686, 2022

    work page 2022

  5. [5]

    Risk-bounded control using stochastic barrier functions,

    S. Yaghoubi, K. Majd, G. Fainekos, T. Yamaguchi, D. Prokhorov, and B. Hoxha, “Risk-bounded control using stochastic barrier functions,” IEEE Control Systems Letters, vol. 5, no. 5, pp. 1831–1836, 2020

    work page 2020

  6. [6]

    Control barrier functions for stochastic systems,

    A. Clark, “Control barrier functions for stochastic systems,”Automat- ica, vol. 130, p. 109688, 2021

    work page 2021

  7. [7]

    Piece- wise stochastic barrier functions,

    R. Mazouz, F. B. Mathiesen, L. Laurenti, and M. Lahijanian, “Piece- wise stochastic barrier functions,”arXiv preprint arXiv:2404.16986, 2024

    work page arXiv 2024

  8. [8]

    Finite-time safety and reach-avoid verification of stochastic discrete-time systems,

    B. Xue, “Finite-time safety and reach-avoid verification of stochastic discrete-time systems,”Information and Computation, p. 105368, 2025

    work page 2025

  9. [9]

    k-inductive and interpolation-inspired barrier certificates for stochastic dynamical sys- tems,

    M. A. Oumer, V . Murali, and M. Zamani, “k-inductive and interpolation-inspired barrier certificates for stochastic dynamical sys- tems,”arXiv preprint arXiv:2504.15412, 2025

    work page arXiv 2025

  10. [10]

    Sum- of-squares optimization in Julia,

    B. Legat, C. Coey, R. Deits, J. Huchette, and A. Perry, “Sum- of-squares optimization in Julia,” inThe First Annual JuMP-dev Workshop, 2017

    work page 2017

  11. [11]

    Stochas- ticbarrier. jl: A toolbox for stochastic barrier function synthesis,

    R. Mazouz, F. B. Mathiesen, L. Laurenti, and M. Lahijanian, “Stochas- ticbarrier. jl: A toolbox for stochastic barrier function synthesis,”arXiv preprint arXiv:2602.20359, 2026

    work page arXiv 2026

  12. [12]

    Successive control barrier func- tions for nonlinear systems,

    R. Wajid and S. Sankaranarayanan, “Successive control barrier func- tions for nonlinear systems,” inProceedings of the 28th ACM Inter- national Conference on Hybrid Systems: Comp. and Control, 2025

    work page 2025

  13. [13]

    Correct-by-construction barrier certificate synthesis for safety verification of continuous dynamical systems,

    P. Panja and A. Platzer, “Correct-by-construction barrier certificate synthesis for safety verification of continuous dynamical systems,” in 2025 IEEE 64th Conference on Decision and Control (CDC). IEEE, 2025, pp. 7701–7707

    work page 2025

  14. [14]

    Semidefinite programming,

    L. Vandenberghe and S. Boyd, “Semidefinite programming,”SIAM review, vol. 38, no. 1, pp. 49–95, 1996

    work page 1996

  15. [15]

    Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns,

    G. S. Aoude, B. D. Luders, J. M. Joseph, N. Roy, and J. P. How, “Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns,”Autonomous Robots, vol. 35, no. 1, pp. 51–76, 2013

    work page 2013

  16. [16]

    A real-time approach for chance-constrained motion planning with dynamic obstacles,

    M. Castillo-Lopez, P. Ludivig, S. A. Sajadi-Alamdari, J. L. Sanchez- Lopez, M. A. Olivares-Mendez, and H. V oos, “A real-time approach for chance-constrained motion planning with dynamic obstacles,” IEEE Robotics and Automation Letters, vol. 5, no. 2, 2020

    work page 2020

  17. [17]

    Multi-robot motion planning with cooperative localization,

    A. Theurkauf, N. Ahmed, and M. Lahijanian, “Multi-robot motion planning with cooperative localization,” in2025 IEEE/RSJ Interna- tional Conference on Intelligent Robots and Systems (IROS). IEEE, 2025, pp. 3962–3969

    work page 2025

  18. [18]

    Piecewise control barrier functions for stochastic systems,

    R. Mazouz, L. Laurenti, and M. Lahijanian, “Piecewise control barrier functions for stochastic systems,” in2025 IEEE 64th Conference on Decision and Control (CDC). IEEE, 2025, pp. 3571–3576

    work page 2025

  19. [19]

    Safe and stable neural network dynamical systems for robot motion planning,

    A. E. Binny, M. Anand, H. T. Kussaba, L. Chen, S. Agrawal, F. J. Abu-Dakka, and A. Swikir, “Safe and stable neural network dynamical systems for robot motion planning,”IEEE Robotics and Automation Letters, 2026

    work page 2026

  20. [20]

    Data-driven verification and synthesis of stochastic systems through barrier certifi- cates,

    A. Salamati, A. Lavaei, S. Soudjani, and M. Zamani, “Data-driven verification and synthesis of stochastic systems through barrier certifi- cates,”arXiv preprint arXiv:2111.10330, 2021

    work page arXiv 2021

  21. [21]

    Data-driven permissible safe control with barrier certificates,

    R. Mazouz, J. Skovbekk, F. B. Mathiesen, E. Frew, L. Laurenti, and M. Lahijanian, “Data-driven permissible safe control with barrier certificates,” in2024 IEEE 63rd Conference on Decision and Control (CDC). IEEE, 2024, pp. 6844–6849

    work page 2024

  22. [22]

    Learning a formally verified control barrier function in stochastic environment,

    M. Tayal, H. Zhang, P. Jagtap, A. Clark, and S. Kolathaya, “Learning a formally verified control barrier function in stochastic environment,” in 2024 IEEE 63rd Conference on Decision and Control (CDC). IEEE, 2024, pp. 4098–4104

    work page 2024

  23. [23]

    Training with hard constraints: Learning neural certificates and con- trollers for sdes,

    C.-W. Kong, S. Escobar, I. Gracia, J. McMahon, and M. Lahijanian, “Training with hard constraints: Learning neural certificates and con- trollers for sdes,”arXiv preprint arXiv:2602.23526, 2026

    work page arXiv 2026

  24. [24]

    D. P. Bertsekas and S. E. Shreve,Stochastic Optimal Control: the Discrete-time Case. Athena Scientific, 2004, vol. 5

    work page 2004

  25. [25]

    A unifying perspective for safety of stochastic systems: From barrier functions to finite abstractions,

    L. Laurenti and M. Lahijanian, “A unifying perspective for safety of stochastic systems: From barrier functions to finite abstractions,”IEEE Transactions on Automatic Control, 2025

    work page 2025

  26. [26]

    Ueber die darstellung definiter formen als summen von formenquadraten,

    Hilbert, “Ueber die darstellung definiter formen als summen von formenquadraten,”Mathematische Annalen, vol. 32, 1888

    work page

  27. [27]

    Time-varying reach- avoid control certificates for stochastic systems,

    R. Mazouz, L. Laurenti, and M. Lahijanian, “Time-varying reach- avoid control certificates for stochastic systems,”arXiv preprint arXiv:2603.25816, 2026

    work page arXiv 2026

  28. [28]

    Polynomial and moment optimization in julia and jump,

    T. Weisser, B. Legat, C. Coey, L. Kapelevich, and J. P. Vielma, “Polynomial and moment optimization in julia and jump,” inJuliaCon, 2019

    work page 2019

  29. [29]

    Jump: A modeling language for mathematical optimization,

    I. Dunning, J. Huchette, and M. Lubin, “Jump: A modeling language for mathematical optimization,”SIAM, vol. 59, no. 2, 2017

    work page 2017

  30. [30]

    Arch- comp20 category report: Stochastic models

    A. Abate, H. A. Blom, N. Cauchi, J. Delicaris, A. Hartmanns, M. Khaled, A. Lavaei, C. Pilch, A. Remke, S. Schuppet al., “Arch- comp20 category report: Stochastic models.” inARCH, 2020

    work page 2020