Integrating Different Incomplete DCOP Algorithms with Quality Bounds

DOI Web Site BIBCODE 6 References Open Access

Bibliographic Information

Other Title
  • 分散制約最適化問題の異なる精度保証付き非厳密解法の統合手法

Abstract

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.

Journal

References(6)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top