PaperlayerView exact revision on arXiv

Source-linked AI summary

Probabilistic Sequential Safety for Stochastic Dynamical Systems

Abhijit Mazumdar, Manuela L. Bujorianu, Rafal Wisniewski

arXiv:2610.37311v1eess.SYcs.SY

TL;DR

Instantaneous safety notions do not capture specifications requiring visits to multiple target regions in a particular pattern or order. The paper develops ordered and unordered sequential-safety characterizations for Itô diffusions using coupled backward equations; in the reported comparison, PDE values lie within Monte Carlo confidence intervals with relative differences below 1%.

  • Problem

    Instantaneous safety notions do not represent specifications requiring several target regions to be visited in a particular pattern or order.

    Source: §I · p. 1

  • Method

    The paper characterizes ordered and unordered sequential-safety probabilities for Itô diffusions using progress augmentation and recursively coupled backward Kolmogorov equations.

    Source: §I · p. 1, §VI · p. 6

  • Results

    Below 1% relative differences were reported between PDE and Monte Carlo values, with every PDE value within the Monte Carlo confidence interval as vmax varied.

    Source: Results · p. 6

  • Takeaways & Limitations

    The framework characterizes the probability of visiting closed target regions by a deadline, either in a prescribed order or in any order.

    Source: §VI · p. 6

Abstract

from arXiv · show

In this letter, we investigate a notion of probabilistic safety for a stochastic dynamical system. Standard safety notions are based on the idea that an unsafe region of the state-space must be avoided at each instant. In contrast, we study a sequential safety notion which is based on avoiding a tuple of target regions of the state-space. The proposed safety notion is inspired by many practical systems, ranging from modeling jailbreak attacks in large language models (LLMs) to predicting hazardous chemical reactions. In solving the sequential safety problem, we solve a sequential reachability problem for a stochastic dynamical system.

I. INTRODUCTION

The introduction argues that instantaneous safety checks cannot capture specifications requiring several regions to be visited in a particular pattern or order. It presents a probabilistic sequential-safety framework for Itô diffusions, with ordered and unordered formulations.

I. INTRODUCTION

  • Multiple-region specifications can depend on visitation order, as in multi-turn jailbreaks and hazardous chemical pathways; instantaneous metrics cannot capture that structure.The same prompts in different orders can have fundamentally different outcomes.Source: §I · p. 1
  • Related work includes diffusion reach-avoid and probabilistic safety, hybrid-system reachability, and finite-state multiphase-until verification; this paper instead targets sequential reachability probabilities for diffusions.Source: §I · p. 1
  • The paper addresses a gap in diffusion safety work, which primarily treats single-target reachability, reach-avoid, or safety specifications.Source: §I · p. 1
  • For prescribed orders, sequential reachability probabilities are characterized by recursive coupled backward Kolmogorov equations derived using the strong Markov property and Feynman–Kac representation.Source: §I · p. 1
  • For visits in any order, the framework solves backward over visited-region sets; its equation count grows exponentially but more slowly than enumerating every order.Source: §I · p. 1

II. SYSTEM DESCRIPTIONS

The system is modeled as a time-homogeneous Itô diffusion on a state space, with locally Lipschitz, linearly bounded coefficients and uniformly elliptic diffusion. The specification selects closed target regions, an initial set, and a finite horizon.

II. SYSTEM DESCRIPTIONS

  • The system is a time-homogeneous Itô process on a state space X, driven by standard Brownian motion, with drift f and diffusion coefficient g.Source: §II · p. 2
  • The standing assumption requires locally Lipschitz, linearly growing coefficients and uniform ellipticity, ensuring a unique strong solution with continuous sample paths.Source: §II · p. 2
  • The specification uses closed target regions U1 through UN, an initial set X0, and a finite time horizon T.Source: §II · p. 2

III. ORDERED SEQUENTIAL SAFETY

For the ordered specification, the paper defines stage-wise completion probabilities and characterizes them by recursively coupled backward Kolmogorov equations. A mode counter records progress through the prescribed sequence, allowing the initial-state safety probability to be computed from the first-stage value function.

III. ORDERED SEQUENTIAL SAFETY

  • The nondecreasing mode counter records ordered progress, credits a target only after its predecessor, and switches upon entering the next target region.Source: §III · p. 2
  • Analyzing each unsafe set separately, or treating their union as one set, provides only upper bounds on the sequential probability.Source: §III · p. 2
  • The value vi(t, x) is the probability of completing regions Ui+1 through UN in order by T, and verification checks v0(0, x0) against p for every x0 in X0.Source: §III · p. 2
  • Combining the diffusion with the mode counter yields a strong Markov process, enabling the ordered specification to be analyzed at stopping times.Source: §III · p. 3
  • Each stage value function is the unique solution of a backward terminal-boundary problem, with the next-stage value as boundary data and zero terminal value before completion.The completed stage has value one; the equations are solved backward from that final stage.Source: §III · p. 3
  • The backward PDE characterization follows by expressing stage completion through an exit-time expectation and applying Feynman–Kac to the stopped diffusion.Uniform ellipticity rules out a positive probability of hitting the terminal-boundary corner under the stated condition.Source: §III · p. 3

IV. UNORDERED SEQUENTIAL SAFETY

The unordered specification asks whether all target regions are visited by time T, in any order. Its probability is computed through coupled value functions indexed by which regions have already been visited.

  • The unordered specification requires visiting all N target regions by time T, without prescribing their order.Source: §IV · p. 4
  • The value function v_H gives the probability of visiting all regions by T, given the already-visited subset H and current state x.Source: §IV · p. 4
  • Theorem 2 characterizes these value functions by a coupled backward parabolic system, with boundary values linked to states in which another unvisited region has been reached.Source: §IV · p. 4
  • The system is solved backward from v_N ≡ 1, since the objective is met once every region has been visited.Source: §IV · pp. 4–5
  • The unordered computation uses 2^N−1 coupled PDEs, rather than independently solving for all N! possible visit orderings.Source: §IV · p. 5

V. NUMERICAL EXAMPLE

The numerical example models a vehicle’s longitudinal motion with stochastic position and velocity dynamics and proportional velocity tracking. The noise-free closed loop converges exponentially to the reference velocity.

  • The vehicle state is position and velocity, X_t = (D_t, V_t), evolving under longitudinal dynamics.Source: §V · p. 5
  • The model includes independent Brownian disturbances, friction and damping coefficient α, noise intensities σ_d and σ_v, and acceleration input u_t.Source: §V · p. 5
  • The position-channel perturbation models random-walk effects from wheel slip and odometry drift, making the dynamics an approximate rather than exact integrator.Source: §V · p. 5
  • A proportional velocity-tracking law closes the loop, and the noise-free closed loop converges exponentially to the reference velocity.Source: §V · p. 5

Sequential Safety Specification:

The vehicle specification concerns an ordered passage: first a speed-limit violation, then an obstacle encounter. The probability is computed through a two-stage PDE recursion.

Numerical Method:

The numerical method discretizes each stage PDE with a grid-based Markov chain and implicit Euler time stepping. The study also uses Euler–Maruyama simulation with Brownian-bridge corrections as an independent reference.

  • The PDE is discretized on a box by a grid Markov chain whose jump rates match the diffusion’s drift and noise.Source: Numerical Method · p. 5
  • Nonnegative jump rates make each computed value a weighted average of neighboring values, keeping it in [0, 1]; implicit Euler is stable for any step size.Source: Numerical Method · p. 5
  • The stage-1 solution is stored at every time step because it supplies time-varying boundary values for stage 0; the stage matrix is factorized once per stage.Source: Numerical Method · p. 5
  • An independent Euler–Maruyama estimate corrects first-passage discrete-monitoring bias with Brownian-bridge crossing probabilities.Source: Numerical Method · p. 5
  • Table II reports the vehicle example’s ordered sequential-passage probability, P_x0(τ1 ≤ τ2 ≤ T).Source: Table II · p. 6

Results:

As the speed threshold tightens while the obstacle remains unchanged, the sequential-passage probability falls, and the PDE estimates agree closely with Monte Carlo. Grid refinement also shows convergence for the reported discretization.

Results:

  • The values decrease monotonically under refinement, and the 301 × 176 grid used in Table II differs from the finest level by 1 × 10−4.At Nt = 2400, the time error is 8×10−5 on every grid.Source: Results · p. 6
  • Grid resolutions keep the initial state, speed threshold, and obstacle edges on grid nodes, avoiding changes to the specification across refinement levels.The table isolates spatial discretization error using Richardson extrapolation from Nt = 2400 and Nt = 1200.Source: Results · p. 6
  • The PDE value lies within the Monte Carlo 95% confidence interval in every case, with relative differences below 1%, as the probability falls from 0.602 to 0.041.The comparison varies the speed threshold while leaving the obstacle unchanged.Source: Results · p. 6

VI. CONCLUSION AND FUTURE WORK

The paper defines sequential safety for visiting closed target regions by a deadline, in a prescribed order or any order. It characterizes the probability through recursively coupled backward Kolmogorov equations and identifies data-driven controller synthesis as future work.

VI. CONCLUSION AND FUTURE WORK

  • Sequential safety concerns the probability that a trajectory visits a tuple of closed target regions by a deadline, either in a prescribed order or in any order.Source: §VI · p. 6
  • Augmenting the diffusion with a discrete mode that records sequential progress yields a strong Markov process, whose Feynman–Kac representation characterizes the probability through recursively coupled backward Kolmogorov equations.The system uses N equations for the ordered case and 2N −1 for the unordered case.Source: §VI · p. 6
  • Future work includes data-driven efficient controller synthesis for sequential safety specifications.Source: §VI · p. 6

Related papers

Loading 2610.37311v1…