For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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)
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.