Computational Methods for Verification of Stochastic Hybrid Systems
Authors:
- Derek RileyDRDerek Riley
- 3 March 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans
- Vol. 38 (2) , 385-396
Abstract
Stochastic hybrid system (SHS) 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 sound computational methods for verification is challenging because of the interaction between the discrete and the continuous stochastic dynamics. In this paper, we propose a probabilistic method for verification of SHSs based on discrete approximations focusing on reachability and safety problems. We show that reachability and safety can be characterized as a viscosity solution of a system of coupled Hamilton-Jacobi-Bellman equations. We present a numerical algorithm for computing the solution based on discrete approximations that are derived using finite-difference methods. An advantage of the method is that the solution converges to the one for the original system as the discretization becomes finer. We also prove that the algorithm is polynomial in the number of states of the discrete approximation. Finally, we illustrate the approach with two benchmarks: a navigation and a room heater example, which have been proposed for hybrid system verification.Keywords
This publication has 18 references indexed in Scilit:
- Safety Analysis of Sugar Cataract Development Using Stochastic Hybrid Systems2007
- A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic gamesIEEE Transactions on Automatic Control, 2005
- On reachability and minimum cost optimal controlAutomatica, 2004
- Structured Modeling of Concurrent Stochastic Hybrid SystemsLecture Notes in Computer Science, 2004
- Stochastic safety verification using barrier certificates2004
- Hierarchical modeling and analysis of embedded systemsProceedings of the IEEE, 2003
- Computational techniques for hybrid system verificationIEEE Transactions on Automatic Control, 2003
- Piecewise-Deterministic Processes and Viscosity Solutions1999
- Markov Models and Optimization1993
- Solving H-horizon, stationary Markov decision problems in time proportional to log(H)Operations Research Letters, 1990