Asynchronous Forward Bounding for Distributed COPs

Abstract

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.

Cited by in corpus (13)

• Distributed Constraint Optimization Problems and Applications: A Survey
• BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm
• Asymmetric Distributed Constraint Optimization Problems
• PT-ISABB: A Hybrid Tree-based Complete Algorithm to Solve Asymmetric Distributed Constraint Optimization Problems
• HS-CAI: A Hybrid DCOP Algorithm via Combining Search with Context-based Inference
• A Privacy Preserving Collusion Secure DCOP Algorithm
• Logic and Constraint Logic Programming for Distributed Constraint Optimization
• Solving Distributed Constraint Optimization Problems Using Logic Programming
• On Population-Based Algorithms for Distributed Constraint Optimization Problems
• Hybrid DCOP Solvers: Boosting Performance of Local Search Algorithms
• RMB-DPOP: Refining MB-DPOP by Reducing Redundant Inferences
• A Generic Approach for Accelerating Belief Propagation based DCOP Algorithms via A Branch-and-Bound Technique
• A Realistic Dataset for the Smart Home Device Scheduling Problem for DCOPs