文章基本信息

标题：Integrating Different Incomplete DCOP Algorithms with Quality Bounds
本地全文：下载
作者：Takuma Yato ; Toshihiro Matsui ; Hiroshi Matsuo 等
期刊名称：人工知能学会論文誌
印刷版ISSN：1346-0714
电子版ISSN：1346-8030
出版年度：2014
卷号：29
期号：3
页码：277-287
DOI：10.1527/tjsai.29.277
出版社：The Japanese Society for Artificial Intelligence
摘要：Distributed Constraint Optimization Problem (DCOP) is a basic framework of cooperative problem solving in multi-agent systems. A number of distributed resource allocation problems including sensor networks, smart grids and disaster response tasks are formulated as DCOPs. Since DCOPs are generally NP-hard, incomplete algorithms are practical for large scale applications. DALO is an incomplete algorithm that guarantees the solution quality based on k/t-optimality. The k-optimality defines local optimality criterion based on the size of the group of deviating agents. On the other hand, the t-optimality is based on a group of surrounding agents within a fixed distance of a central agent. In the recent study, C-optimality has been introduced to generalize those criteria. The C-optimality defines criteria for local optimality in any arbitrary regions. As another type of optimality criteria, the p-optimality that is based on the induced width of pseudo-trees on constraint networks has been proposed. With p-optimality, the original problem is approximated by removing back edges of the pseudo-tree. Both types of incomplete algorithms have different week points. Since DALO is based on local optimality criteria, its solution quality depends on limited information (e.g. agent’s values and constraints) within local regions. The solution quality of the p-optimal algorithms decreases when constraint graph consists of many cycles to be removed. In this paper, in order to achieve both lower computational complexity and better solution quality, we propose an integrated solution method based on both types of optimality criteria. Namely, we use information of the incomplete algorithm based on p-optimality and besides another method of C-optimality. Hence our aim is to employ complementary effects of both incomplete algorithms. Empirical results show that our integrated solution method obtain better solution quality than existing incomplete algorithms.
关键词：multi-agent ; distributed constraint optimization problem