Asynchronous Forward Bounding Revisited

International audienceThe Distributed Constraint Optimization Problem (DCOP) is a powerful framework for modeling and solving applications in multi-agent coordination. Asynchronous Forward Bounding (AFB_BJ) is one of the best algorithms to solve DCOPs.We propose AFB_BJ + , a revisited version of AFB_BJ in which we refine the lower bound computations. We also propose to compute lower bounds for the whole domain of the last assigned agent instead of only doing this for its current assignment. This reduces both the number of messages needed and the time future agents remain idle. In addition, these lower bounds can be used as a value ordering heuristic in AFB_BJ + . The experimental evaluation on standard benchmark problems shows the efficiency of AFB_BJ + compared to other algorithms for DCOPs