When designing controllers for complex real-world systems—such as autonomous vehicles, smart power grids, or multi-agent robotics—we must navigate two fundamental challenges: continuous state spaces and inherent randomness. These systems are formally modeled as stochastic hybrid systems or continuous-state stochastic processes.
Analyzing these systems directly is notoriously difficult. Because the state space is infinite (uncountable), we cannot exhaustively check every possible trajectory to guarantee safety or performance. To make this tractable, researchers use formal abstractions: they simplify the continuous, noisy system into a discrete, finite-state model, such as a Finite Markov Decision Process (MDP). Once a finite abstraction is built, standard automated verification and synthesis tools can easily compute an optimal, "correct-by-construction" control policy.
However, this abstraction step introduces a critical vulnerability. Discretizing a continuous space inherently creates approximation errors. If a controller is designed to be perfectly safe on a simplified grid, how can we be certain it won't cause a catastrophic failure when deployed on the true, noisy, continuous system? As emphasized by Soudjani et al. in their work on the FAUST$^2$ framework, without a rigorous mathematical method to quantify these approximation errors, any safety guarantees verified on the abstract model are functionally unreliable for the original system.
The solution lies in a mathematical bridge known as stochastic simulation functions. These functions allow us to precisely bound the probabilistic distance between a complex system and its abstraction, ensuring that control strategies transfer reliably from the model to reality.
The Intuition: Tracking Error as Energy
To understand why stochastic simulation functions work, it helps to recall Lyapunov functions from classical control theory. A Lyapunov function acts like an "energy" metric for a system's state: if you can prove that this energy always decreases over time, the system is guaranteed to be stable.
A stochastic simulation function applies this exact intuition to the error between two different systems. Instead of measuring the energy of a single system, it measures the "discrepancy energy" between the state of the original continuous system ($x$) and the state of its simplified abstraction ($\hat{x}$).
In a foundational paper, A. Agung Julius et al. formalized this concept. A stochastic simulation function $V(x, \hat{x})$ is a scalar function that satisfies two core properties:
- Bounded Growth: It provides an upper bound on the actual physical distance between the outputs of the two systems. If $V(x, \hat{x})$ is small, the real system's behavior is close to the abstraction's behavior.
- Expectation Dissipation: When the systems evolve over a time step, the expected value of the function at the next step is bounded by a fraction of its current value plus a constant factor related to the noise and discretization resolution.
By establishing these properties, the function acts as a mathematical guarantee. It ensures that the abstract model can "simulate" the original system within a tightly controlled envelope. If the abstract system moves to a new state, we can mathematically predict where the concrete system will land, bounding the maximum deviation in both output values and transition probabilities.
From Error Bounds to Correct-by-Construction Control
Once a stochastic simulation function is established, it provides an explicit $(\epsilon, \delta)$ accuracy margin. This margin guarantees that the trajectories of the real system will remain within a spatial distance of $\epsilon$ from the abstract trajectories with a probability of at least $1-\delta$.
This quantitative relationship changes how we synthesize controllers for complex temporal logic specifications (such as "reach the target within 10 seconds while avoiding obstacles"). For instance, Haesaert et al. leverage these simulation relations within a robust dynamic programming framework. Instead of calculating a single probability of success, they use the quantified error bounds to compute guaranteed upper and lower bounds on the probability that the real system satisfies the specification.
+----------------------------+
| Continuous Real System | <-- Hard to verify directly
+----------------------------+
^
| Stochastic Simulation Function V(x, x̂)
| Provides formal (ε, δ) error bounds
v
+----------------------------+
| Discrete Finite Abstract | <-- Synthesize robust controller here
+----------------------------+
This allows for a strategy called robust controller synthesis. If we know the real system might deviate from the abstraction by at most $\epsilon$, we can shrink our target zones and expand our obstacle zones in the abstract model by that same margin $\epsilon$. If we can find a controller that satisfies the task on this "tightened" abstract model, the simulation relation guarantees that the real system will successfully complete the original task despite its noise and continuous drift.
This methodology is highly versatile. Zamani et al. demonstrated that specific incremental stability properties (like $\delta$-ISS-$M_q$) allow for the automated construction of these approximately bisimilar finite abstractions. Furthermore, the framework accommodates modern constraints beyond safety; for example, Xu et al. utilize bisimulation functions to maintain formal performance guarantees even when random noise is deliberately injected into multi-agent systems to ensure differential privacy.
Beating the Curse of Dimensionality: Compositional Dissipativity
While computing a stochastic simulation function works well for low-dimensional systems, a major bottleneck arises when dealing with large-scale interconnected networks, such as a traffic grid or a power network. As the number of variables grows, the computational cost of generating a global abstraction and its corresponding simulation function explodes exponentially—a phenomenon known as the curse of dimensionality.
To bypass this obstacle, researchers shift from a centralized approach to a compositional ("divide and conquer") framework. Instead of analyzing the massive network all at once, the network is broken down into smaller, low-dimensional subsystems.
This is where stochastic storage functions and dissipativity theory become essential. Derived from thermodynamics and control engineering, dissipativity theory tracks how "energy" flows between interconnected components. In this context, the energy being tracked is the abstraction error.
As detailed by Lavaei et al., the process works as follows:
- Local Storage Functions: For each individual subsystem, researchers construct a stochastic storage function. This function acts like a local bucket that quantifies the abstraction error within that specific component.
- Supply Rates: The authors define "supply rates" that mathematically model how error or disturbances are passed between neighboring subsystems through their physical interconnections.
- Compositional Synthesis: By verifying that the interconnected network satisfies a global balance condition (often evaluated using standard numerical optimization tools like linear matrix inequalities), the individual storage functions can be compositionally combined into a global stochastic simulation function.
This compositional strategy is powerful because it shifts the computational burden. Instead of solving one massive, intractable problem, we solve multiple small, easily digestible problems. Lavaei et al. and Lavaei et al. demonstrated that this approach provides a highly flexible way to analyze complex physical networks, allowing controllers to be designed subsystem-by-subsystem while still yielding a mathematically rigorous, global guarantee on the entire network's performance.
Summary
Stochastic simulation and storage functions transform the problem of verifying continuous, noisy systems from an intractable guessing game into a structured optimization problem. By treating approximation error as a form of dissipating energy, they provide the mathematical guarantees required to safely abstract the continuous world into discrete models, enabling the automated synthesis of robust, correct-by-construction controllers.
Key Foundational Work
Approximations of Stochastic Hybrid Systems (2009) — contributed 6 concept elements to this direction.
Probabilistic testing for stochastic hybrid systems (2008) — contributed 3 concept elements to this direction.