Probabilistic reachability analysis for large scale stochastic hybrid systems

Blom, Henk A.P.; Bakker, G.J. (Bert); Krystul, Jaroslav · 2007 · OpenAlex-citations

DOI: 10.1109/cdc.2007.4434095

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of probabilistic reachability analysis for large-scale stochastic hybrid systems (SHS), specifically focusing on safety verification where the probability of entering an unsafe set is extremely low. The research is motivated by the need to verify the safety of advanced air traffic control concepts, which are modeled as controlled SHS. Traditional dynamic programming approaches are computationally intractable for large-scale systems, while standard Monte Carlo simulations require impractically large sample sizes to estimate rare events accurately. Although sequential Monte Carlo methods have been developed for rare event estimation, existing approaches fail when the reach probability is driven by rare switching between discrete modes rather than diffusion behavior, particularly when the number of discrete modes is very large. To overcome these limitations, the authors propose a novel Hierarchical Hybrid Interacting Particle System (HHIPS) algorithm. The method introduces an aggregation of the discrete modes, partitioning the large set of modes into a smaller set of aggregation modes. This allows the application of importance sampling relative to the switching between these aggregated modes, rather than individual modes. The approach builds upon the theoretical framework of Del Moral et al., which characterizes the reach probability as a multiplicative function of conditional probabilities across a nested sequence of subsets. The HHIPS algorithm estimates these conditional probabilities using a recursive sequential Monte Carlo simulation. It employs a hierarchical interaction scheme where particles are resampled and weighted to maintain a fixed number of particles per aggregation mode, ensuring computational tractability even when the original mode space is vast. Theoretical results, including Theorems 1 and 2, provide the probabilistic characterizations necessary for unbiased estimation and proper weight compensation during the prediction and resampling steps. The practical effectiveness of the HHIPS approach is demonstrated through the safety verification of an advanced air traffic control scenario. The authors show that while previous sequential Monte Carlo methods failed for scenarios where rare discrete mode switching significantly contributed to the reach probability, the proposed aggregation-based method successfully handles these demanding cases. The algorithm provides an unbiased estimate of the reach probability with bounded error, enabling the analysis of large-scale SHS that were previously intractable. The significance of this work lies in its ability to extend rare event estimation theory to large-scale stochastic hybrid systems with numerous discrete modes. By aggregating modes and applying importance sampling to the aggregated process, the method makes probabilistic reachability analysis feasible for complex systems like future air traffic operations. This contributes to the field of control theory and safety verification by providing a computationally efficient tool for assessing the risk of rare but critical events in systems characterized by both continuous dynamics and discrete mode switching.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• naturalistic crash near crash