マルチエージェントシステムにおける 通信コストの構造依存性に関する解析 2003.9.12 マルチエージェントシステムにおける 通信コストの構造依存性に関する解析 吉川 毅 北海道大学 2004.3.8, WINGS6
研究の背景（１） マルチエージェントシステム エージェント間の競合 解消・協調 合意形成 交渉による合意 2004.3.8 WINGS6
研究の背景（２） エージェントが分散している環境 ネットワーク上に配置など 交渉の手続きに要するコストを考慮 2004.3.8 WINGS6
研究の目的 通信コストの分散構造依存性に関する考察 会議スケジューリング問題のシミュレーション 提案・返答・報告のためのメッセージ送信回数 （ネットワーク上での通信コスト） 2004.3.8 WINGS6
マルチエージェントシステム エージェント 複数のエージェント間で競合 解消・協調 合意形成 知識・信念に基づいて自律的に行動 それぞれ独自の目標 複数のエージェント間で競合 解消・協調 合意形成 2004.3.8 WINGS6
交渉方式 提案エージェント 提案 案A 返答（受理） 返答（却下） ･･･ 2004.3.8 WINGS6
実験設定（１） 会議スケジューリング問題 ｛月～金｝×｛午前、昼、夕方｝の１５時間帯 会議数１ 必要支持率以上の出席で会議成立 エージェントの持つ情報 会議の重要度（０：重要でない～９：重要） 各時間帯の不都合さ（０：都合が良い～９：不都合） 2004.3.8 WINGS6
実験設定（２） 交渉手順 提案エージェントにとって最も都合の良い時間帯の提案 提案された時間帯に対して次のように返答 （重要度－不都合さ）＞０ ⇒ 受理 （重要度－不都合さ）＜＝０ ⇒ 却下 受理数が必要支持数以上ならば合意として全エージェントに報告 合意が得られなければ、提案エージェントはその旨交渉相手に報告 全ての時間帯で合意が得られなければ、交渉失敗、そうでなければ次善案を提案し、２に戻る 2004.3.8 WINGS6
実験設定（３） 交渉相手数の制限による変化 エージェント数：１０ 交渉可能エージェント（接続）数：２～９、１刻み 連結グラフで表現できる構造 必要支持率：０．５，０．８ 接続数×支持率ごとに１万回の平均 2004.3.8 WINGS6
接続数の例 接続数：３ 提案エージェント ･･･ 2004.3.8 WINGS6
実験結果（１） 2004.3.8 WINGS6
実験結果（２） 2004.3.8 WINGS6
実験結果（３） 2004.3.8 WINGS6
実験結果（４） 2004.3.8 WINGS6
まとめ マルチエージェントの合意形成 今後の課題 シミュレーションによる通信コストの一考察 不均一なコストの場合の考察 分散制約充足問題における解析 2004.3.8 WINGS6