Asynchronous Breadth-First Search DCOP Algorithm
Redouane Ezzahir, Mohammed, Christian Bessière, Imade Benelallam · 2008
In MultiAgent systems, Distributed Constraint Optimization Prob-lem (DCOP) has been used as a formalism to model a wide range of agents coordination issues. The Asynchronous forward-bounding with backjumping (AFB-BJ) algorithm was recently proposed as a new way to solve DCOP. The AFB-BJ shows better performance in comparison 1838 R. Ezzahir et al. to Adopt algorithm. In this paper, we introduce Asynchronous Breadth-First Search DCOP algorithm (ABFS) that improves AFB-BJ. In ABFS we use a new search strategy based on tree structure where the agents are ordered on a breadth first search traversal. Detailed experimen-tal results show that on benchmark problems (random Max-DisCSPs, graph coloring and Meeting Schedule problems) the proposed algorithm (ABFS) obtains more improvements than AFB-BJ algorithm.