A new search algorithm for solving distributed constraint optimization problems (DisCOPs) is presented. Agents assign variables sequentially and compute bounds on partial assignments asynchronously. The asynchronous bounds computation is based on the propagation of partial assignments. The asynchronous forward-bounding algorithm (AFB) is a distributed optimization search algorithm that keeps one consistent partial assignment at all times. The algorithm is described in detail and its correctness proven. Experimental evaluation shows that AFB outperforms synchronous branch and bound by many orders of magnitude, and produces a phase transition as the tightness of the problem increases. This is an analogous effect to the phase transition that has been observed when local consistency maintenance is applied to MaxCSPs. The AFB algorithm is further enhanced by the addition of a backjumping mechanism, resulting in the AFB-BJ algorithm. Distributed backjumping is based on accumulated information on bounds of all values and on processing concurrently a queue of candidate goals for the next move back. The AFB-BJ algorithm is compared experimentally to other DisCOP algorithms (ADOPT, DPOP, OptAPO) and is shown to be a very efficient algorithm for DisCOPs.

该论文提出了用于解决分布式约束优化问题（DisCOPs）的一种新的搜索算法，即基于异步边界计算的异步前向绑定算法（AFB），该算法通过处理候选目标队列来进行分布式回溯搜索，实验结果表明，AFB相对于同步分支和界限搜索算法的效率提高了许多个数量级，并且在问题紧度增加时，产生相变的效果。而AFB-BJ算法则通过引入回跳机制进一步提高了算法效率，是DisCOPs的一种非常有效的算法。

分布式约束求解问题的异步前向边界算法