A Hybrid Algorithm for Distributed Constraint Optimization

Tenda OKIMOTO  Masashi YAMAMOTO  Yuko SAKURAI  Makoto YOKOO  Katsumi INOUE  

D - Abstracts of IEICE TRANSACTIONS on Information and Systems (Japanese Edition)   Vol.J96-D   No.12   pp.2920-2928
Publication Date: 2013/12/01
Online ISSN: 1881-0225
Print ISSN: 1880-4535
Type of Manuscript: Special Section PAPER (Special Section on Software Agent and Its Applications)
distributed constraint optimization problem,  search algorithm,  pseudo-tree,  p-optimality,  

Full Text(in Japanese): PDF(640.2KB)
>>Buy this Article

A Distributed Constraint Optimization Problem (DCOP) is a fundamental problem that can formalize various applications related to multi-agent cooperation. Considering a pseudo-tree based search algorithm is important in DCOPs. Their memory requirements are polynomial in the number of agents but they have a large run time. Thus, how to speed up pseudo-tree based search algorithms is one of the major issues in DCOPs. In this paper, we propose a novel hybrid algorithm which combines a complete algorithm with an incomplete algorithm. We show that this algorithm outperforms existing DCOP search algorithms.