マルチエージェントシステムにおける 通信コストの構造依存性に関する解析

Presentation on theme: "マルチエージェントシステムにおける 通信コストの構造依存性に関する解析"— Presentation transcript:

1 マルチエージェントシステムにおける 通信コストの構造依存性に関する解析
マルチエージェントシステムにおける 通信コストの構造依存性に関する解析 吉川　毅 北海道大学 , WINGS6

2 研究の背景（１） マルチエージェントシステム エージェント間の競合 解消・協調 合意形成 交渉による合意 WINGS6

3 研究の背景（２） エージェントが分散している環境 ネットワーク上に配置など 交渉の手続きに要するコストを考慮 WINGS6

4 研究の目的 通信コストの分散構造依存性に関する考察 会議スケジューリング問題のシミュレーション 提案・返答・報告のためのメッセージ送信回数
（ネットワーク上での通信コスト） WINGS6

5 マルチエージェントシステム エージェント 複数のエージェント間で競合 解消・協調 合意形成 知識・信念に基づいて自律的に行動
それぞれ独自の目標 複数のエージェント間で競合 解消・協調 合意形成 WINGS6

6 交渉方式 提案エージェント 提案 案A 返答（受理） 返答（却下） ･･･ WINGS6

7 実験設定（１） 会議スケジューリング問題 ｛月～金｝×｛午前、昼、夕方｝の１５時間帯 会議数１ 必要支持率以上の出席で会議成立
エージェントの持つ情報 会議の重要度（０：重要でない～９：重要） 各時間帯の不都合さ（０：都合が良い～９：不都合） WINGS6

8 実験設定（２） 交渉手順 提案エージェントにとって最も都合の良い時間帯の提案 提案された時間帯に対して次のように返答
（重要度－不都合さ）＞０　⇒　受理 （重要度－不都合さ）＜＝０　⇒　却下 受理数が必要支持数以上ならば合意として全エージェントに報告 合意が得られなければ、提案エージェントはその旨交渉相手に報告 全ての時間帯で合意が得られなければ、交渉失敗、そうでなければ次善案を提案し、２に戻る WINGS6

9 実験設定（３） 交渉相手数の制限による変化 エージェント数：１０ 交渉可能エージェント（接続）数：２～９、１刻み 連結グラフで表現できる構造
必要支持率：０．５，０．８ 接続数×支持率ごとに１万回の平均 WINGS6

10 接続数の例 接続数：３ 提案エージェント ･･･ WINGS6

11 実験結果（１） WINGS6

12 実験結果（２） WINGS6

13 実験結果（３） WINGS6

14 実験結果（４） WINGS6

15 まとめ マルチエージェントの合意形成 今後の課題 シミュレーションによる通信コストの一考察 不均一なコストの場合の考察
分散制約充足問題における解析 WINGS6