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.
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}$.
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