Abstract
The formal verification and controller synthesis for Markov decision processes that evolve over uncountable state spaces are computationally hard and thus generally rely on the use of approximations. In this work, we consider the correct-by-design control of general Markov decision processes (gMDPs) with respect to temporal logic properties by leveraging approximate probabilistic relations between the original model and its abstraction. We newly work with a robust satisfaction for the construction and verification of control strategies, which allows for both deviations in the outputs of the gMDPs and in the probabilistic transitions. The computation is done over the reduced or abstracted models, such that when a property is robustly satisfied on the abstract model, it is also satisfied on the original model with respect to a refined control strategy.
Introduction
In fields such as robotics, power grids, and synthetic biology, systems are often modeled as Markov processes. However, real-world cyber-physical systems typically evolve over continuous or uncountable state spaces. Formally verifying that such a system will satisfy a safety property (e.g., "never enter a danger zone") or a complex mission (e.g., "visit point A, then B, while avoiding C") is computationally exhausting or even impossible due to the "curse of dimensionality."
To address this, researchers create simplified "abstractions" of the system. The challenge lies in the inherent gap between the simplified model and reality. This paper presents a framework to bridge this gap mathematically, ensuring that a controller designed for a simplified model works reliably on the original, complex system.
The $(\epsilon, \delta)$-Probabilistic Simulation Framework
The core of this methodology is the $(\epsilon, \delta)$-probabilistic simulation relation. This relation serves as a quantitative bridge between two models:
- $\epsilon$ represents the maximum deviation in the system's output (spatial distance).
- $\delta$ represents the maximum deviation in transition probabilities.
By quantifying these errors, the authors can guarantee that if a property is satisfied on the abstract model with a certain "robustness margin," it will be satisfied on the original model.
Methodology: Robust Satisfaction and Policy Refinement
The framework utilizes several key technical pillars to achieve correct-by-design control:
- Robust Satisfaction: Instead of standard satisfaction, the authors develop robust versions of Bellman equations for dynamic programming. These equations bake the $\delta$ error directly into the calculation, creating a safety buffer.
- scLTL to DFA Product: The paper focuses on syntactically co-safe Linear Temporal Logic (scLTL)—properties verifiable in finite time. These logic formulas are converted into Deterministic Finite Automata (DFA). By taking the "product" of the gMDP and the DFA, the complex logic problem is transformed into a simpler probabilistic reachability problem.
- Policy Refinement: An algorithm is provided to "lift" a control strategy from the abstract model back to the original model. This interaction is visualized in the execution semantics of the controlled model, showing how the controller (C) interacts with the gMDP (M) over time.
Experimental Validation
The theory was evaluated using a synthetic "game of tag" involving a 3D linear stochastic dynamical system. The abstract model was created via balanced truncation and state-space discretization.
Key results from this validation include:
- Theoretical Guarantees: The authors proved that reachability probabilities on the abstract model serve as rigorous bounds for the original model.
- Numerical Success: In the simulation, the $(\epsilon, \delta)$-robust satisfaction probability remained high (between 0.8 and 1.0), and the original model successfully followed the intended behavior despite the significant reduction in model complexity.
Conclusion and Future Work
This framework allows researchers to explicitly trade off model simplicity for certainty. If a simpler model is desired (resulting in larger $\epsilon$ and $\delta$), the property must simply be satisfied with a higher robust margin.
While the synthesized controller is efficient, the primary limitation remains the computational cost of the initial abstraction process for very high-dimensional or non-linear systems. Future work will focus on developing better software tools to automate this process for industrial-scale problems and extending these robust relations to broader classes of stochastic systems.
Summary updated