Journal article
Belief Propagation for Large-Variable-Domain Optimization on Factor Graphs: An Application to Decentralized Weather-Radar Coordination
IEEE transactions on systems, man, and cybernetics. Systems, v 43(2), pp 460-466
01 Mar 2013
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
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.
Metrics
Details
- Title
- Belief Propagation for Large-Variable-Domain Optimization on Factor Graphs: An Application to Decentralized Weather-Radar Coordination
- Creators
- Erik P. Vargo - University of VirginiaEllen J. Bass - University of VirginiaRandy Cogill - University of Virginia
- Publication Details
- IEEE transactions on systems, man, and cybernetics. Systems, v 43(2), pp 460-466
- Publisher
- IEEE
- Number of pages
- 7
- Grant note
- 0313747 / Engineering Research Centers Program of the National Science Foundation under NSF
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Information Science
- Web of Science ID
- WOS:000317614400019
- Scopus ID
- 2-s2.0-84887052984
- Other Identifier
- 991019292125204721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Automation & Control Systems
- Computer Science, Cybernetics