Efficient Methods for Asynchronous Distributed Constraint Optimization Algorithm

T. Matsui, H. Matsuo, and A. Iwata (Japan)


Constraint optimization/satisfaction problem, Distributed search, Branch and bound, Multi agent system, Distributed Artificial Intelligence,


Effective methods to reduce number of message cycles of adopt algorithm which is a complete algorithm for dis tributed constraint optimization problems are proposed. The Adopt algorithm can perform branch and bound search asynchronously. However, it has overhead in backtracking and searches same partial solution repeatedly. To reduce overhead of backtracking, lower and upper bound of cost of partial solution are considered and some messages are sent to upper nodes by shortcut. Leaning of the lower and upper bound is used to reduce extra search. The results show the efficiency of the proposed methods.

Important Links:

Go Back