FAULT-TOLERANT MULTI-AGENT EXACT BELIEF PROPAGATION

Multiply sectioned Bayesian networks (MSBNs) support multi-agent probabilistic inference in distributed large problem domains, where agents (subdomains) are organized by a tree structure (called hypertree). In earlier work, all belief updating methods on a hypertree are made of two rounds of propagation, each of which is implemented as a recursive process. Both processes need to be started from the same designated (root) hypernode. Agents perform local belief updating at most in a partial parallel manner. Such methods may not be suitable for practical multi-agent environments because they are easy to crush for the problems happened in communication or local belief updating. In this paper, we present a fault-tolerant belief updating method for multi-agent probabilistic inference. In this method, multiple agents concurrently perform exact belief updating in a complete parallel. Temporary problems happened from time to time at some agents or some communication channels would not prevent agents from eventually converging to the correct beliefs. Permanently disconnected communication channels would not keep the properly connected portions of the system from appropriately finishing their belief updating within portions. Compared to the previous traversal-based belief updating, the proposed approach is not only fault-tolerant but also robust and scalable.