Dynamic Backtracking for Distributed Constraint Optimization
Redouane Ezzahir, Christian Bessière, Imade Benelallam, Bouyakhf El Houssine, Mustapha Belaissaoui · Frontiers in artificial intelligence and applications · 2008
We propose a new algorithm for solving Distributed Constraint Optimization Problems (DCOPs). Our algorithm, called DyBop, is based on branch and bound search with dynamic ordering of agents. A distinctive feature of this algorithm is that it uses the concept of valued nogood. Combining lower bounds on inferred valued nogoods computed cooperatively helps pruning dynamically unfeasible sub-problems and speeds up the search. DyBop requires a polynomial space at each agent. Experiments show that DyBop has significantly better performance than other DCOP algorithms.