Max-sum Revisited: The Real Power of Damping

摘要

Max-sum is a version of Belief propagation, used for solving DCOPs. On tree-structured problems, Max-sum converges to the optimal solution in linear time. Unfortunately when the constraint graph representing the problem includes multiple cycles (as in many standard DCOP benchmarks), Max-sum does not converge and explores low quality solutions. Recent attempts to address this limitation proposed versions of Max-sum that guarantee convergence, by changing the constraint graph structure. Damping is a method that is often used for increasing the chances that Belief propagation will converge, however, it was not mentioned in studies that proposed Max-sum for solving DCOPs. In this paper we investigate the effect of damping on Max-sum. We prove that, while it slows down the propagation of information among agents, on tree-structured graphs, Max-sum with damping is guaranteed to converge to the optimal solution in weakly polynomial time. Our empirical results demonstrate a drastic improvement in the performance of Max-sum, when using damping. However, in contrast to the common assumption, that it performs best when converging, we demonstrate that non converging versions perform efficient exploration, and produce high quality results, when implemented within an anytime framework. On most benchmarks, the best results were achieved using a high damping factor (A preliminary version of this paper was accepted as a two page extended abstract to a coming up conference.)