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