文献

J-GLOBAL ID：201302293597452944   整理番号：13A0848214

制約充足や最適化に関するエージェント研究の最近の動向

著者 (2件)： 平山勝敏 (神戸大 大学院海事科学研究科) ,  松井俊浩 (名古屋工大 大学院工学研究科)
資料名： 人工知能学会誌  (Journal of the Japanese Society for Artificial Intelligence)
巻： 28  号： 3  ページ： 380-388  発行年： 2013年05月01日 
JST資料番号： X0330A  ISSN： 0912-8085  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本論文では,分散協調問題解決の1つである分散制約充足問題(DisCSP)及び分散制約最適化問題(DCOP)が,マルチエージェントシステムにおける様々な応用問題をモデル化できることを解説した。まず,DisCSPは制約充足問題における変数と制約,DCOPは制約最適化問題における関数を複数のエージェントに分散した問題であり,局所的に記述した問題をエージェント間のメッセージ通信によって集めずに充足/最適化することを説明した。次に,DisCSPアルゴリズムとして,1)木探索に基づく非同期バックトラッキングアルゴリズム,2)局所探索に基づく分散ブレイクアウトアルゴリズムとその改訂版を示した。また,i)局所探索法,ii)動的計画法,iii)木探索に基づくDCOPアルゴリズムや大規模問題への近似解法,DCOPの拡張問題について述べた。それらアルゴリズムの評価ではサイクル数,NCCCs(non-concurrent constraint checks),メッセージ数,メッセージサイズ,メモリ使用量,プライバシーの損失度合いなどをアルゴリズムに応じて用いる必要がある。さらに,センサ網や電力網における資源割り当て,複雑な構造を持つスケジューリング問題,災害対応,複数ロボットの行動調整の失敗原因診断,提携構造形成問題への適用例を示した。

シソーラス用語： *マルチエージェントシステム ,  *制約充足問題 ,  *制約付最適化問題 ,  分散処理 ,  エージェント ,  メッセージ伝送 ,  *木探索 ,  *バックトラッキング ,  破壊 ,  近傍探索法 ,  *近似法 ,  プライバシー ,  スケジューリング ,  資源割付 ,  国際会議 ,  凝固シェルブレークアウト
準シソーラス用語： ブレークアウト【凝固シェル】 ,  メッセージ通信 ,  局所探索法 ,  *分散制約充足問題 ,  *分散制約付最適化問題

分類 (3件)： 人工知能  (JE08000Z) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  数値計算  (JE02000J)

引用文献 (61件)：

• BABA, S. Cooperative problem solving against adversary : Quantified distributed constraint satisfaction problem. AAMAS-2010. 2010, 781-788
• BEJAR, R. Sensor networks and distributed CSP : Communication, computation and complexity. Artificial Intelligence. 2005, 161, 1-2, 117-147
• BESSIERE, C. Asynchronous backtracking without adding links : A new member in the ABT family. Artificial Intelligence. 2005, 161, 1-2, 7-24
• BESSIERE, C. Agile asynchronous backtracking for distributed constraint satisfaction problems. ICTAI-2011. 2011, 777-784
• BRITO, I. Connecting ABT with arc consistency. CP-2008. 2008, 387-401

タイトルに関連する用語 (5件)： 制約充足 ,  最適化 ,  エージェント ,  研究 ,  動向