閉路をもつ因子グラフのための分散制約最適化手法の一般化

松井 俊浩  松尾 啓志  

誌名
電子情報通信学会論文誌 D   Vol.J101-D   No.9   pp.1305-1315
発行日: 2018/09/01
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2017SAP0021
論文種別: 特集論文 (ソフトウェアエージェントとその応用論文特集)
専門分野: 理論
キーワード: 
Max-Sumアルゴリズム,  因子グラフ,  擬似木,  分散制約最適化,  マルチエージェントシステム,  

本文: PDF(1MB)
>>論文を購入


あらまし: 
分散制約最適化問題(DCOP)はマルチエージェントシステムの基礎的な問題として研究されている.DCOPの解法としてMax-Sumアルゴリズムが提案されている.この解法は変数と関数を頂点とする二部グラフである因子グラフに基づく.従来の制約グラフは二項関数しか表現できないが,因子グラフは任意の項数の関数を表現できる.Max-Sumアルゴリズムは無閉路の因子グラフにおける厳密解法であるが,閉路を含む因子グラフでは最適解に収束しない可能性がある.本研究では,一般化された擬似木であるcross-edged pseudo-treeにより因子グラフを分解する手法を提案する.これにより,従来の制約グラフ上の動的計画法やMax-Sumアルゴリズムに基づく,DCOPのための因子グラフ上の厳密解法を示す.更に,この厳密解法の部分問題の規模を抑制するために,擬似木に基づく解法の近似手法であるMini-bucketsアルゴリズムを適用する.