Computational Methods for Reachability Analysis of Stochastic Hybrid

Abstract. Stochastic hybrid system models can be used to analyze and design complex embedded systems that operate in the presence of uncertainty and variability. Verification of reachability properties for such systems is a critical problem. Developing algorithms for reachability analysis is challenging because of the interaction between the discrete and continuous stochastic dynamics. In this paper, we propose a probabilistic method for reachability analysis based on discrete approximations. The contribution of the paper is twofold. First, we show that reachability can be characterized as a viscosity solution of a system of coupled Hamilton-Jacobi-Bellman equations. Second, we present a numerical method for computing the solution based on discrete approximations and we show that this solution converges to the one for the original system as the discretization becomes finer. Finally, we illustrate the approach with a navigation benchmark that has been proposed for hybrid system verification.