Probabilistic Alternating Simulations for Policy Synthesis in Uncertain Stochastic Dynamical Systems
Thom Badings, Alessandro Abate · 2025
Read Probabilistic Alternating Simulations for Policy Synthesis in Uncertain Stochastic Dynamical Systems by Thom Badings, Alessandro Abate (2025) 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-2508-05062.txt.
Introduction
Thom Badings and Alessandro Abate forge a kin tie for wild yet ruled craft in a 2025 paper. To steer a craft by law, hands first shrink it to a small state twin, then prove the twin's acts hold for the true craft.
Old ties fail when the craft bears two wilds at once: dice throws in its path, and foes that shove it by set plays. The new tie splits the two: dice are met by chance sums, foes by worst-case guard. It grows the old ties in use for such checks. A test on a four-mark craft that turns like a jet showed the tie can bear real steer work. The authors give the tie as a base for proof-held plans in wild worlds.
Catalog record
| CREATOR | Thom Badings, Alessandro Abate |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-05062
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Probabilistic Alternating Simulations for Policy Synthesis in Uncertain Stochastic Dynamical Systems Thom Badings, Alessandro Abate Abstract A classical approach to formal policy synthesis in stochastic dynamical systems is to construct a finite-state abstraction, often represented as a Markov decision process (MDP). The correctness of these approaches hinges on a behavioural relation between the dynamical system and its abstraction, such as a probabilistic simulation relation. However, probabilistic simulation relations do not suffice when the system dynamics are, next to being stochastic, also subject to nondeterministic (i.e., set-valued) disturbances. In this work, we extend probabilistic simulation relations to systems with both stochastic and nondeterministic disturbances. Our relation, which is inspired by a notion of alternating simulation, generalises existing relations used for verification and policy synthesis used in several works. Intuitively, our relation allows reasoning probabilistically over stochastic uncertainty, while reasoning robustly (i.e., adversarially) over nondeterministic disturbances. We experimentally demonstrate the applicability of our relations for policy synthesis in a 4D-state Dubins vehicle. I Introduction The synthesis of (control) policies for dynamical systems that provably satisfy specific requirements is crucial for their deployment in safety-critical scenarios. We consider systems modelled as Markov decision processes (MDPs) [ 1 ] with continuous state and action spaces. These (continuous) MDPs capture nonlinear and stochastic dynamics and are thus widely applicable for modelling systems in uncertain environments. Classical objectives in automatic control, such as stabilisation and tracking, are insufficient to capture the complex objectives needed for many systems. Instead, we consider objectives in temporal logic, such as linear temporal logic (LTL) and probabilistic computation tree logic (PCTL). Temporal logic enables formulating complex, high-level objectives involving periodic, sequential, or reactive tasks [ 2 ] . Approaches to policy synthesis with temporal logic specifications broadly fall into two categories. First, certificate-based approaches aim to find a (Lyapunov-like) function that implies the satisfaction of a specification [ 3 , 4 ] . The second category, which we focus on in this paper, replaces the continuous MDP (the “ concrete ” system) with a simpler, finite MDP (the “ abstraction ”) and uses model checking techniques [ 2 ] to compute a policy on this abstraction. These abstractions are classically model-based [ 5 , 6 , 7 , 8 , 9 ] , but recent works study data-driven approaches as well [ 10 , 11 , 12 ] . Although abstractions tend to explode with the state dimension, they can handle rich specifications and natively capture stochasticity [ 13 ] . The correctness of abstraction techniques hinges on a behavioural relation between the concrete system and the abstraction [ 14 ] . Such a relation ensures that any policy for the abstraction can be refined into a policy for the concrete system with equivalent performance guarantees . Relations for synthesis in nonstochastic systems have been well-studied, leading to, e.g., (approximate) simulation relations [ 15 ] , feedback refinement relations [ 16 ] , and memoryless concretisation relations [ 17 ] . For stochastic systems such as MDPs, most papers leverage (approximate) probabilistic simulations to ensure the soundness of abstraction techniques [ 18 , 8 ] . Loosely speaking, the system (I) probabilistically simulates another system (II) if, for every policy of system (II), there exists a policy for system (I) such that their output behaviour is equivalent. Technically, probabilistic simulation thus requires that the closed-loop system under a given policy is a stochastic process. As a result, probabilistic simulation does not allow for nondeterministic (i.e., set-valued) disturbances in the MDP’s dynamics. Such disturbances naturally arise in systems with uncertain parameters and multi-agent systems [ 2 ] . To solve this problem, we extend probabilistic simulation relations to systems with both stochastic and nondeterministic dynamics. We model such systems as robust MDPs (RMDPs), which extend MDPs with sets of probability distributions , often as convex polytopes for tractability [ 19 , 20 ] . While RMDPs with finite state and action spaces (and with finite state but continuous action spaces [ 21 ] ) are well-studied [ 22 ] , we consider their full generalisation to continuous spaces. We develop a behavioural relation for continuous RMDPs, inspired by the notion of alternating simulation for two-player (stochastic) games [ 23 , 24 ] . Much like [ 18 ] extends probabilistic simulation to continuous MDPs, we extend probabilistic alternating simulation to continuous MDPs with set-valued dynamics . Our relation treats the nondeterminism as a second player in a game, which allows robust reasoning against these disturbances. Thus, probabilistic alternating simulations allow reasoning probabilistically over stochasticity, and robustly over nondeterministic disturbances. Our relations are closely related to [ 25 ] , which follows a slightly different formalisation not based on alternating notions of simulation. In summary, our main contribution is a novel probabilistic alternating simulation for stochastic dynamical systems with uncertain dynamics. After the preliminaries in section II , we present our theoretical results in sections III and IV . We also discuss how our relations generalise some others used in existing works. To showcase the applicability, we use our results in section V to synthesise policies with reach-avoid guarantees for a Dubins vehicle with a 4D state space. II Preliminaries A Polish space is a separable completely metrisable topological space. The power set over X is written 2^{X} . A probability space \left(\Omega,\mathcal{F},\mathbb{P}\right) consists of a sample space \Omega , a \sigma -algebra \mathcal{F} , and a probability measure \mathbb{P}\colon\mathcal{F}\to[0,1] . We denote the Borel \sigma -algebra over a set X by \mathcal{B}(X) . The set of all distributions over an (in)finite set X is denoted by \mathcal{P}(X) . A set \mathcal{R}\subseteq X\times Y is called a binary relation between sets X and Y , for which we write \mathcal{R}({x})\coloneqq\{y\in Y:(x,y)\in\mathcal{R}\} and \mathcal{R}^{-1}({y})\coloneqq\{x\in X:(x,y)\in\mathcal{R}\} . For subsets X^{\prime}\subset X and Y^{\prime}\subset Y , we write \mathcal{R}({X^{\prime}})\coloneqq\{y\in Y:\exists x\in X^{\prime},(x,y)\in\mathcal{R}\} and \mathcal{R}^{-1}({Y^{\prime}})\coloneqq\{x\in X:\exists y\in Y^{\prime},(x,y)\in\mathcal{R}\} . The relation \mathcal{R} is single-valued if |\mathcal{R}({x})|=1 for all x\in X , in which case \mathcal{R} induces a partition into equivalence classes. II-A Continuous Markov decision processes We consider discrete-time nonlinear stochastic systems, modelled as a (continuous) Markov decision process (MDP). Definition 1 (MDP) A (continuous) Markov decision process (MDP) is a tuple \mathcal{D}=\left(\mathbb{X},\bar{x},\mathbb{U},\mathbb{T},\mathbb{L},h\right) , where • \mathbb{X} is a Polish space, called the state space , • \bar{x}\in\mathcal{P}(\mathbb{X}) is a probability measure on (\mathbb{X},\mathcal{B}(\mathbb{X})) modelling the initial state distribution , • \mathbb{U} is a Polish space, called the action space , • \mathbb{T} is a stochastic kernel that assigns to each x\in\mathbb{X} and u\in\mathbb{U} a probability measure \mathbb{T}(\cdot\mid x,u) over (\mathbb{X},\mathcal{B}(\mathbb{X})) , • \mathbb{L} is a finite set of labels, and • h\colon\mathcal{B}(\mathbb{X})\to 2^{\mathbb{L}} is a measurable labelling function that assigns to each state a (possibly empty) subset of labels. Example 1 Consider a Dubins vehicle with a 4D state [x_{k},y_{k},\theta_{k},V_{k}]\in\mathbb{R}^{4} , whose dynamics are defined as \displaystyle\begin{bmatrix}x_{k+1}\\ y_{k+1}\\ \theta_{k+1}\\ V_{k+1}\end{bmatrix}=\begin{bmatrix}x_{k}\\ y_{k}\\ \theta_{k}\\ \beta\cdot V_{k}\end{bmatrix}+\delta\cdot\begin{bmatrix}V_{k}\cdot\cos{\theta_{k}}\\ V_{k}\cdot\sin{\theta_{k}}\\ \alpha\cdot u_{k}+w_{k}\\ u^{\prime}_{k},\end{bmatrix}, (1) with time discretization \delta>0 , steering sensitivity \alpha>0 , drag coefficient \beta>0 , and Gaussian noise w_{k}\sim\mathcal{N}(0,0.1) . We model this system as MDP \mathcal{D} with states \mathbb{X}=\mathbb{R}^{4} , inputs [u_{k},u^{\prime}_{k}]\in\mathbb{U}\subset\mathbb{R}^{2} , and stochastic kernel \mathbb{T} given by eq. 1 . Policies. The actions in an MDP are selected by a Markov policy, which acts as a