EFFICIENT METHODS FOR ASYNCHRONOUS DISTRIBUTED CONSTRAINT OPTIMIZATION ALGORITHM

摘要

Effective methods to reduce number of message cycles of adopt algorithm which is a complete algorithm for distributed 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.