Belief Propagation for Large-Variable-Domain Optimization on Factor Graphs: An Application to Decentralized Weather-Radar Coordination

Due to the NP-hardness of factor-graph optimization, obtaining exact solutions to problems with a large variable domain is generally not possible. Max-sum (max-product) belief propagation (BP) is a distributed message-passing heuristic that has found popularity due to its ability to generate approximate solutions to such factor-graph problems in a distributed fashion. Because max-sum BP generally provides no indication of solution quality, researchers have sought alternative algorithms to generate approximate (and, in some cases, exact) solutions, the most successful of which operate on a relaxation of the integer programming form of an equivalent maximum a posteriori estimation problem. While such linear-programming-based algorithms perform well in empirical studies, there are limits to the variable domain size for which they are tractable. Via a case study in weather-radar coordination, we demonstrate that the decentralized max-sum BP algorithm remains useful for generating quality solutions to problems with a large variable domain. Our custom simulation tool facilitates a comparison of the performance of algorithms with respect to adaptive weather-radar scanning resource allocation across three weather scenarios. In addition to no adaptive scanning, the algorithms include four max-sum-BP-based algorithms: decentralized distributed max-sum BP, self-terminating tree-based bounded approximation, tabu search implemented in a centralized fashion, and a combination of the latter two. Performance is measured by the end-user utility for all algorithms and by two types of approximation ratios for the tree-based bounded approximation. BP-based decentralized algorithms are found to exhibit comparable performance with a centralized algorithm and superior performance to no adaptive scanning. Furthermore, our analysis demonstrates that max-sum BP is capable of generating solutions within 67% of optimal (and typically much better) across the weather scenarios.