Improvement of efficiency in pseudo-tree based distributed best first search
Toshihiro Matsui, Hiroshi Matsuo · 2007
Distributed constraint optimization problem is an area of research in multi agent system. In recent years, a distributed constraint optimization algorithm, which performs best-first search in bottom up manner according to pseudo tree, was proposed. In this paper, we propose several efficient methods for the distributed bottom up best-first search. Deriva- tion of partial solution is introduced to decrease num- ber of backtracking among agents, Synchronization control method is applied to decrease number of com- munication message cycles. In addition, error bounds are applied to obtain quasi optimal solution within less number of message cycles. Experiment results are shown for the efficiency evaluation of the proposed heuristics methods.