Optimization of Inter-Subnet Belief Updating in Multiply Sectioned
  Bayesian Networks
  Recent developments show that Multiply Sectioned Bayesian Networks (MSBNs)
can be used for diagnosis of natural systems as well as for model-based
diagnosis of artificial systems. They can be applied to single-agent oriented
reasoning systems as well as multi-agent distributed probabilistic reasoning
systems. Belief propagation between a pair of subnets plays a central role in
maintenance of global consistency in a MSBN. This paper studies the operation
UpdateBelief, presented originally with MSBNs, for inter-subnet propagation. We
analyze how the operation achieves its intended functionality, which provides
hints as for how its efficiency can be improved. We then define two new
versions of UpdateBelief that reduce the computation time for inter-subnet
propagation. One of them is optimal in the sense that the minimum amount of
computation for coordinating multi-linkage belief propagation is required. The
optimization problem is solved through the solution of a graph-theoretic
problem: the minimum weight open tour in a tree.
