Beyond Uninformed Search: Improving Branch-and-bound Based Acceleration Algorithms for Belief Propagation via Heuristic Strategies

Belief propagation algorithms including Max-sum and its variants are important methods for solving DCOPs. However, they may face a tough challenge when handling n-ary constraints since the computational overheads grow exponentially with the number of variables that a utility function holds. In this paper, we update the state-of-the-art technique called Function Decomposing and State Pruning (FDSP) which can significantly reduce such an expenditure, by introducing two heuristic techniques. By introducing a round-robin mechanism to control the order of exploration, we propose Concurrent-search-based FDSP (CONC-FDSP). Besides, we propose Best-first-search-based FDSP (BFS-FDSP) by using the 𝐴 * search to find the optimal path to the solution. Finally, we demonstrate their efficiency in solving the benchmarks compared with the state-of-the-art.