Asynchronous Forward Bounding for Distributed COPs
  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.
