擬似木に基づく分散制約最適化問題の精度保証付き非厳密解法の提案

• Item type: Journal(1)
• 公開日: 2011-12-15
• タイトル: 擬似木に基づく分散制約最適化問題の精度保証付き非厳密解法の提案
• タイトル / 言語: en
• タイトル: Pseudo-tree-based Incomplete Algorithm for Distributed Constraint Optimization with Quality Bounds
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 一般論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 九州大学大学院システム情報科学府情報学専攻横尾研究室
• 著者所属: 九州大学大学院システム情報科学府情報学専攻横尾研究室
• 著者所属: 九州大学大学院システム情報科学府情報学専攻横尾研究室
• 著者所属: 九州大学大学院システム情報科学府情報学専攻横尾研究室
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者名: 沖本, 天太; ジョヨンジュン; 岩崎, 敦; 横尾, 真
• 著者名(英): Tenda, Okimoto; Yongjoon, Joe; Atsushi, Iwasaki; Makoto, Yokoo
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 分散制約最適化問題（DCOP）はマルチエージェントシステムにおける協調問題解決の基本的な枠組みである．DCOPはNP-hardであるため，大規模な問題に対して，比較的少ない計算で近似解を探索する非厳密解法を考える必要がある．しかしながら，既存の非厳密解法のほとんどは解品質を保証しない．数少ない例外としてDALO，bounded max-sum解法，ADPOPがある．本論文では，近似解の新しい評価基準$p$-optimalityに基づく非厳密解法を提案する．本解法の特徴を以下に示す．本解法は，(i)得られる解の絶対/相対誤差の上界をそれぞれ事前/事後に与えることができる，(ii) DCOPの厳密解法で広く用いられている擬似木に基づく解法である，(iii)エージェント数nに関して多項式時間で実行可能なone-shot typeの解法である，(iv)調整可能なパラメータpを持つ．実験では本解法が，解品質を保証する既存の非厳密解法と比べ，より高品質な解および高精度な誤差の上界を与えることを示した．さらに本解法は，これらの非厳密解法と比べ，より高速に求解可能であることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A Distributed Constraint Optimization Problem (DCOP) is a fundamental problem that can formalize various applications related to multi-agent cooperation. Since it is NP-hard, considering faster incomplete algorithms is necessary for large-scale applications. Most incomplete algorithms generally do not provide any guarantees on the quality of solutions. Some notable exceptions are DALO, the bounded max-sum algorithm, and ADPOP. In this paper, we develop a new solution criterion called p-optimality and an incomplete algorithm for obtaining a p-optimal solution. The characteristics of this algorithm are as follows: (i) it can provide the upper bounds of the absolute/relative errors of the solution, which can be obtained a priori/a posteriori, respectively, (ii) it is based on a pseudo-tree, which is a widely used graph structure in complete DCOP algorithms, (iii) it is a one-shot type algorithm, and (iv) it has adjustable parameter p, The evaluation results illustrate that this algorithm can obtain better quality solutions and bounds compared to existing bounded incomplete algorithms, while the run time of this algorithm is shorter.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 52, 号 12, p. 3786-3795, 発行日 2011-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764