Compositional Analysis of Dynamic Bayesian Networks and Applications to CPS

Shahan Yang, Yuchen Zhou and John Baras

Dynamic Bayesian networks (DBNs) can be effectively
used to model various problems in CPS. We perform an
empirical investigation on compositional analysis of DBNs using
abstraction. In static systems and hidden Markov models, computation
of a metric called treewidth induces a tree decomposition
that can be used to perform logical or probabilistic inference
and max+ optimizations in time exponential in treewidth and
linear in overall system size. Intuitively, the linear scaling means
that very large systems can be analyzed as long as they are
sufficiently sparse and well structured. In these simple cases,
summary propagation, which uses two operations, summation
(projection) and product (composition), suffices to perform the
inference or optimization. Here, we begin an extension of this to
structured networks of communicating dynamic systems.
We define generalizations of projection and composition operators
that treat labeled Markov chains as primitive objects.
The projection operation, corresponding to summation, is implemented
as label deletion followed by exact state reduction
for Markov chains, similar to Hopcroft’s DFA minimization
algorithm, with O(n logm) complexity. The composition operation
is the product of state machines. We use canonical MDDs,
similar to BDDs, to capture logical dependencies symbolically.
Combining symbolic representations with Markov chain lumping
algorithms is a novel contribution. Using this approach, we
have created a tool leveraging model based systems engineering
technologies. The communicating Markov chains are specified
using UML Statecharts via Papyrus extended using an ANTLR
parsed domain specific language (DSL).

The tool reduces the number of states in networks of Markov
chains by several orders of magnitude. In one example, a network
having a product state space of more than 600 million states
is reduced to about 500 states. A feature of this technique is
that the state space is examined incrementally, meaning that the
full state space is never explicitly represented, even as an input
to the reduction algorithm. The primary reduction appears to
come from symmetry which is surprising because the technique
includes no explicit symmetry handling.We note that composition
is efficient at least for systems with high symmetry. We describe
applications to two CPSs: an aircrat power generation and
distribution network and a hospital intensive care unit (ICU).