A class of iterative refined Max-sum algorithms via non-consecutive value propagation strategies

摘要

As an important technique to solve distributed constraint optimization problems, Max-sum has drawn a lot of attention and successfully been deployed in real applications. Unfortunately, Max-sum fails to converge in cyclic problems and usually traverses states with low quality. Max-sum_AD and Max-sum_ADVP were proposed to guarantee the single phase convergence and the cross phase convergence respectively, and greatly improve the solution quality of Max-sum. However, the solution quality is closely related to the timing for starting value propagation in Max-sum_ADVP. In other words, low-quality initial assignments will lead to a poor result. In this paper, we prove that value propagation could restrict the exploration ability brought by Max-sum and eventually makes Max-sum_ADVP equivalent to a sequential greedy local search algorithm. For getting a balance between exploration and exploitation, several non-consecutive value propagation strategies are proposed to relax the restriction caused by value propagation: single-side value propagation which executes value propagation and Max-sum_AD in an interleaved way, probabilistic value propagation which performs value propagation stochastically and hybrid belief/value propagation where agents perform Max-sum_AD and value propagation in one round. We illustrate that agents in our algorithms can make decisions beyond local functions. Our empirical evaluations demonstrate the superiority of our methods over Max-sum and its variants. It also can be found that our methods are independent of the value propagation timing which is a major concern in Max-sum_ADVP.