マルチエージェントシステムにおける 交渉方式に関す

マルチエージェントシステムにおける
通信コストの構造依存性に関する解析
吉川 毅
北海道大学
2004.3.8, WINGS6
2
研究の背景(1)
マルチエージェントシステム
エージェント間の競合
解消・協調
合意形成
交渉による合意
2004.3.8
WINGS6
3
研究の背景(2)
エージェントが分散している環境
ネットワーク上に配置など
交渉の手続きに要するコストを考慮
2004.3.8
WINGS6
4
研究の目的
通信コストの分散構造依存性に関する考察
会議スケジューリング問題のシミュレーション
提案・返答・報告のためのメッセージ送信回数
(ネットワーク上での通信コスト)
2004.3.8
WINGS6
5
マルチエージェントシステム
エージェント
知識・信念に基づいて自律的に行動
それぞれ独自の目標
複数のエージェント間で競合
解消・協調
2004.3.8
合意形成
WINGS6
6
交渉方式
提案エージェント
案A
提案
返答(受理)
返答(却下)
・・・
2004.3.8
WINGS6
7
実験設定(1)
会議スケジューリング問題
{月~金}×{午前、昼、夕方}の15時間帯
会議数1
必要支持率以上の出席で会議成立
エージェントの持つ情報
会議の重要度(0:重要でない~9:重要)
各時間帯の不都合さ(0:都合が良い~9:不都合)
2004.3.8
WINGS6
8
実験設定(2)
 交渉手順
1. 提案エージェントにとって最も都合の良い時間帯の提
案
2. 提案された時間帯に対して次のように返答
 (重要度-不都合さ)>0 ⇒ 受理
 (重要度-不都合さ)<=0 ⇒ 却下
3. 受理数が必要支持数以上ならば合意として全エージェ
ントに報告
4. 合意が得られなければ、提案エージェントはその旨交
渉相手に報告
5. 全ての時間帯で合意が得られなければ、交渉失敗、そ
うでなければ次善案を提案し、2に戻る
2004.3.8
WINGS6
9
実験設定(3)
交渉相手数の制限による変化
エージェント数:10
交渉可能エージェント(接続)数:2~9、1刻み
連結グラフで表現できる構造
必要支持率:0.5,0.8
接続数×支持率ごとに1万回の平均
2004.3.8
WINGS6
10
接続数の例
接続数:3
提案エージェント
・・・
2004.3.8
WINGS6
11
実験結果(1)
コスト
全体平均通信コスト
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
実験結果(2)
交渉成功率
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
実験結果(3)
成功時平均通信コスト
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
実験結果(4)
失敗時平均通信コスト
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