MC-netsを用いた提携構造形成アルゴリズムの拡張：負の利得と外部性の導入

一村　良  長谷川　隆人  上田　俊  岩崎　敦  横尾　真  

誌名
電子情報通信学会論文誌 D   Vol.J94-D   No.11   pp.1707-1715
発行日: 2011/11/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (ソフトウェアエージェントとその応用論文特集)
専門分野: 理論
キーワード: 
提携構造形成問題,  協力ゲーム,  エージェント協調技術,  アルゴリズム,  

本文: PDF(458.5KB)
>>論文を購入

あらまし: 
エージェント間で社会的に望ましい協調関係（提携）を形作ること，すなわち提携構造形成問題は，AIやマルチエージェントシステムの分野における重要な研究領域である．従来研究では，提携のもたらす効用は特性関数と呼ばれるブラックボックス関数で与えられるとしていたが，特性関数の記述量はエージェントの数に対して指数的に増加するため，エージェント数の多い提携構造形成問題の解を現実的な時間で算出することは困難だった．Ohtaらは，特性関数をルールの集合を用いて簡略に記述する手法を利用することで高速に最適解を算出する手法を提案しているが，この手法には負の利得をもつルールが存在する場合や外部性が存在する場合に適切に解を発見できないという問題があった．本論文ではまず，提携構造形成問題の記述にダミールールを追加することで，負の利得をもつルールを扱えるようにOhtaらのアルゴリズムを拡張した．更に，これにMichalakらの組込みMC-netsを合わせて利用することで外部性が存在する場合の提携構造形成問題を扱えるようにした．最後に，提案アルゴリズムを用いることで，従来のアルゴリズムと比べて，計算時間を大幅に増加させずに，負の利得をもつルールや外部性が存在する場合の提携構造形成問題の最適解を算出できることを計算機実験で示した．