Dynamic Bayesian networks for formal verification of structured stochastic processes

Journal article

We study the problem of finite-horizon probabilistic invariance for discrete-time Markov processes over general (uncountable) state spaces. We compute discrete-time, finite-state Markov chains as formal abstractions of the given Markov processes. Our abstraction differs from existing approaches in two ways: first, we exploit the structure of the underlying Markov process to compute the abstraction separately for each dimension; second, we employ dynamic Bayesian networks (DBN) as compact representations of the abstraction. In contrast, approaches which represent and store the (exponentially large) Markov chain explicitly incur significantly higher memory requirements. In our experiments, explicit representations scaled to models of dimension less than half the size as those analyzable by DBN representations. We show how to construct a DBN abstraction of a Markov process satisfying an independence assumption on the driving process noise. We compute a guaranteed bound on the error in the abstraction w.r.t. the probabilistic invariance property—the dimension-dependent abstraction makes the error bounds more precise than existing approaches. Additionally, we show how factor graphs and the sum-product algorithm for DBNs can be used to solve the finite-horizon probabilistic invariance problem. Together, DBN-based representations and algorithms can be significantly more efficient than explicit representations of Markov chains for abstracting and model checking structured Markov processes.

Authors: Esmaeil Zadeh Soudjani, S; Abate, A; Majumdar, R

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer Berlin Heidelberg
• Journal: Acta Informatica
• Volume: 54
• Issue: 2
• Pages: 217–242
• Publication date: 2016-12-03
• Acceptance date: 2016-11-15
• DOI: 10.1007/s00236-016-0287-9
• EISSN: 1432-0525
• ISSN: 0001-5903