Optimization of Inter-agent 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 arti cial 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 in a MSBN plays a central role in maintenance of global consistency. This paper studies the operation UpdateBelief for inter-subnet propagation originally presented with MSBNs. We analyze how the operation achieves its functionality, which provides hints as for how its eciency can be improved. We then dene two new implementations of UpdateBelief that reduce the computational time for inter-subnet propagation. One of them is optimal in the sense that the minimal 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 minimal weight open tour in a tree