Formal Abstraction of General Stochastic Systems via Noise Partitioning

John Skovbekk, Luca Laurenti, Eric W. Frew, Morteza Lahijanian

Abstract

Ensuring the safety of autonomous systems requires formal verification, which is often hindered by complex stochastic dynamics and the "state-explosion" problem. This paper introduces a novel abstraction framework that partitions the noise domain rather than the state space to construct Interval Markov Chains (IMCs). This approach allows for formal safety guarantees in systems with non-standard noise distributions and nonlinear dynamics. Furthermore, a refinement-free clustering algorithm is proposed to improve verification accuracy without increasing the number of states.

Introduction

Autonomous systems, such as self-driving vehicles and medical robots, operate in inherently uncertain environments. Verifying their safety involves continuous-space stochastic models, which are typically abstracted into finite discrete models like Markov Chains. However, traditional abstraction techniques often suffer from two major drawbacks: they assume simplified noise distributions (e.g., Gaussian) and rely on state-space refinement, which leads to exponential growth in computational complexity. This work addresses these challenges by shifting the focus from state partitioning to noise partitioning.

Methodology

Noise Partitioning and Interval Markov Chains

The proposed method utilizes Interval Markov Chains (IMCs) to represent the uncertainty in transition probabilities. Instead of fixed values, transitions are defined by lower and upper bounds. The core innovation lies in Theorem 1, which establishes that partitioning the noise domain $W$ into finite sets allows for bounding the transition kernel using the system's reachable set (the Post operator). This "distribution-agnostic" approach remains valid until the final integration step, accommodating complex noise models like multiplicative or mixture distributions. For monotonic systems, the authors define optimal noise partitions that minimize transition intervals with minimal computational overhead.

Refinement-free Improvement via Clustering

To mitigate the state-explosion problem, the authors introduce a clustering-based improvement algorithm (Algorithm 1). Unlike traditional methods that split states to increase precision, this approach strategically merges states within the IMC. By leveraging the structure of transition intervals, clustering can actually tighten the satisfaction bounds.

Visualization of the refinement-free clustering process showing initial states, clustering steps, and final verification.

Case Studies and Evaluation

The framework was evaluated on several benchmarks, including systems with multiplicative noise, data-driven dynamics learned via Gaussian Process (GP) regression, and complex nonlinear models like the Duffing Oscillator and a 3D Dubin’s Aircraft.

Comparative Performance

In linear system benchmarks, the noise partitioning method achieved results nearly identical to specialized direct-search methods, with a negligible average probability difference of $8 \times 10^{-4}$.

Comparison of safety verification results between the proposed method and existing techniques.

Efficiency and Flexibility

The method successfully identified safe starting states for a 3D Dubin's car with non-standard mixture noise—states that standard Gaussian-based methods would fail to classify. Additionally, the clustering algorithm improved lower-bound satisfaction probabilities by an average of 10% in data-driven scenarios without adding new states. Most examples computed within minutes, demonstrating the practical efficiency of the approach.

Conclusion

By partitioning the noise domain and employing a refinement-free clustering strategy, this research provides a scalable and flexible approach to the formal verification of general stochastic systems. Future work will focus on incorporating measurement noise and optimizing clustering heuristics for highly non-monotonic systems.

Summary updated

Abstract

Verifying the performance of safety-critical, stochastic systems with complex noise distributions is difficult. We introduce a general procedure for the finite abstraction of nonlinear stochastic systems with non-standard (e.g., non-affine, non-symmetric, non-unimodal) noise distributions for verification purposes. The method uses a finite partitioning of the noise domain to construct an interval Markov chain (IMC) abstraction of the system via transition probability intervals. Noise partitioning allows for a general class of distributions and structures, including multiplicative and mixture models, and admits both known and data-driven systems. The partitions required for optimal transition bounds are specified for systems that are monotonic with respect to the noise, and explicit partitions are provided for affine and multiplicative structures. By the soundness of the abstraction procedure, verification on the IMC provides guarantees on the stochastic system against a temporal logic specification. In addition, we present a novel refinement-free algorithm that improves the verification results. Case studies on linear and nonlinear systems with non-Gaussian noise, including a data-driven example, demonstrate the generality and effectiveness of the method without introducing excessive conservatism.
BibTeX
@inproceedings{skovbekk2023formal,
  author = {John Skovbekk and Luca Laurenti and Eric W. Frew and Morteza Lahijanian},
  title = {{Formal Abstraction of General Stochastic Systems via Noise Partitioning}},
  booktitle = {IEEE Control. Syst. Lett},
  year = {2023},
  url = {https://openreview.net/forum?id=QCjuYxpy9s},
}
Figure