一般化状態における協調と競合のためのエージェント内部機構

パターンベースのエージェント間の協調競合技術
目的
実世界情報を利用して自律学習を行うマルチエージェン
トアーキテクチャーにおいて、パターン情報を用いて内
部エージェント間の協調競合を行う技術を開発する。
従来技術
パターンを扱う技術 → 協調競合技術が不十分
– Subsumptionアーキテクチャ(Brooks)
– 強化学習
協調競合技術 → パターン情報への適用が不十分
– 黒板モデル
– 契約ネット
– ゲームと交渉
一般化状態とゴール伝播の双方向性
• CITTA (Cognition base InTelligent
Transaction Architecture)
エージェント内部だけでなくエージェント間の
結合の学習により内部表現を自律的に獲得す
ることを目指して開発されているエージェント・
ネットワーク型の認知アーキテクチャー
• 一般化状態
協調を行うマルチエージェント環境下ではセン
サ入力に対する欲求からも行動を実現し得る
との考えから、CITTAではセンサ入力と動作
出力を区別しない一般化状態を用いる。
• ゴール伝播の双方向性
あるエージェントが取込んだゴールは協調の
起動条件と、競合相手の両方として扱い得る
もので、それを一意に決定できない性質 →
上のエージェントが下の情報を参照し、
ゴールを書き込む。
これに対応できる協調競合機構が必要
結合されたエージェント間で
のゴールの交換時に協調
や競合が発生する。
MOB
MOB
MOB
B-node
MOB
MOB
MOB
B-node
P(g out | s, g i n)
A
g
s
B
双方向的な
ゴール伝播
L-node
OB
S-node M
MOB
OB
S-node M
MO B
MOB
MO B
C
L-node
D
L-node
ゴールの競合発生例
AのL-node(下側)とBの
L-node(下側)からの
ゴール出力が、CのBnode(上側)で重ね合わ
される。
無出力行動と確率的動作による協調競合機構
分散AI領域で様々な協調競合機構が提案されているが、パターンを利用した領
域において強化学習とうまく統合できる協調競合機構とはどんなものだろうか？
ポイント１: 無出力行動(Invalid) を用いる
パターン分野での入出力装置では出力しない行動を取り扱う例は殆ど無い。他の
エージェントのゴール出力をアクセプトする機構を無出力行動として実現する。
ポイント２: 確率的動作を用いる
局所的に最適な行動ではなく、効用に応じて確率的に動作出力を行う。
ポイント３: 強化学習で用いられる効用を流用する
Q学習での、Q(センサ、行動)を一般化状態に拡張したQ(状態、ゴール)を用いる。
協調競合機構による状態遷移(一次元の場合)
初期確率
入力ゴール(i)に対するゴール出力(j)の確率
m
f bg

ji
m
N bg

i
ji
bg
bgt
bg
m
m
m
p0 I M bg
0  p0 A M bg
i  p0V M bg
j
o
3
m
bg
f
 ji
j 1
m
bg
f
m
Fjibg
 ji
m
N ibg
他者のゴールをアクセプ
トする確率がその入力
ゴールの効用に依存する
(δ ijはクロネッカのデルタ)
p0I: 無出力行動
p0A :無出力行動(アクセプト)
p0V :通常出力
効用からの影響
M (m) (i) :
i :ゴールの状態番号で
0は出力無を表す
m: エージェントID
効用関数を用いた確率的交渉機構(一次元)
実験設定
各々に効用関数M(m)(x)を持つ、二つのエージェント
(AとB)が3状態を持つゴールについてC上で交渉。
この例では両者にとって妥協的である状態２の確率
が、交渉機構によって増加することが示された。
A
B
エージェント毎の効用からの影響
状態
M(A)(x)
M(B)(x)
Invalid 1
1
10
1
1
2
9
9
3
1
10
初期確率の設定
無出力行動が行われ
た場合にはC上のゴー
ル状態は変化しない。
従来
無出力有
0
1
1
無出力+アクセプト
0
0
1
1
1
1
C
従来機構における交互出力
0.7
0.7
0.7
0.6
0.6
0.5
0.5
0.5
0.4
エージェントA
エージェントB
0.3
0.4
従来
従来
Invalid有り
無出力行動
交渉有り
無出力
+アクセプト
0.3
0.2
0.2
従来
従来
Invalid有り
無出力行動
無出力
交渉有り
+アクセプト
0.4
0.3
0.2
0.1
0.1
選択確率
0.6
選択確率
選択確率
交互平均値の比較(交渉収束後)
交渉による変化(交渉収束後)
0.1
0
0
1
1
2
選択状態
3
2
選択状態
3
0
1
2
選択状態
交渉ファクターp0Aによって状態２の選択確率が高まる
3
多次元でのエージェント毎の競合協調機構
2次元に拡張した場合の説明
・外部からゴールが与えられない間は、
効用関数からの影響Mによって確率
分布が決定。
・外部からゴールが与えられるとaccept
の確率が０でなくなる。
(1) 外部から与えられるゴール無し
ゴール:x
出力無
出力有り
出力無アクセプト 1
2
3
ゴ出力無 P00 M00 P0A M01 P01 M01 P02 M02 P03 M03
0
0
0
0
0
ー accept
1 P10 M10 P1A M11 P11 M11 P12 M12 P13 M13
ル
: 出力有 2 P20 M20 P2A M21 P21 M21 P22 M22 P23 M23
ｙ
3 P30 M30 P3A M31 P31 M31 P32 M32 P33 M33
(3) 外部からx=1､y=2が与えられる
ゴール:x
ゴール:x
出力無
出力無アクセプト 1
0 P01 M01
ゴ出力無 P00 M00
0
0
0
ー accept
1 P10 M10
0 P11 M11
ル
: 出力有 2 P20 M20
0 P21 M21
ｙ
3 P30 M30
0 P31 M31
(2) 外部からx=1が与えられる
出力有
2
P02 M02
0
P12 M12
P22 M22
P32 M32
3
P03 M03
0
P13 M13
P23 M23
P33 M33
出力無
出力無アクセプト 1
ゴ出力無 P00 M00 P0A M0１ P01 M01
ー accept PA0 M20 PAA M21 PA1 M21
ル
1 P10 M10 P1A M11 P11 M11
: 出力有 2 P M P M P M
20 20
2A 21
21 21
ｙ
3 P30 M30 P3A M31 P31 M31
出力有
2
P02 M02
PA2 M22
P12 M12
P22 M22
P32 M32
3
P03 M03
PA3 M23
P13 M13
P23 M23
P33 M33
到達エージェントと回避エージェントの交渉
•
•
乱数発生器として実装
10x10に離散化された平面
を移動するロボットにおいて、
到達エージェントと回避エー
ジェントが交互に確率的に
出力をして競合解消を行う。
ロボットが左下にいる瞬間
での交渉を示している。
(図中 0はInvalidを示す)
•
•
到達エージェントの効用
回避エージェントの効用
10
10
9
9
8
8
7
7
6
6
25-30
20-25
15-20
10-15
5-10
0-5
5 Y
4
3
2
5 Y
4
3
2
1
1
0
1
2
3
4
5
6
7
8
25-30
20-25
15-20
10-15
5-10
0-5
0
9 10
0
1
2
3
4
5
6
7
8
0
9 10
X
X
移動ロボット
ターゲット
障害物
10､000回の試行における選択頻度
最初の到達動作後の選択頻度
10
9
8
7
6
5 Y
4
3
2
0
1
2
3
4
5
X
6
7
8
1
0
9 10
10回目の回避動作後の選択頻度
次の回避動作後の選択頻度
480-510
450-480
420-450
390-420
360-390
330-360
300-330
270-300
240-270
210-240
180-210
150-180
120-150
90-120
60-90
30-60
0-30
10
10
9
9
8
7
6
5 Y
4
3
2
1
0
1
2
3
4
5
X
6
7
8
9
0
10
8
300-330
270-300
240-270
210-240
180-210
150-180
120-150
90-120
60-90
30-60
0-30
7
6
5 Y
4
3
2
1
0
1
2
3
4
5
6
7
8
9
0
10
330-360
300-330
270-300
240-270
210-240
180-210
150-180
120-150
90-120
60-90
30-60
0-30
X
回避しながらターゲットに近づく行動(ゴール出力として)の頻度が増加した
宣言的知識によるゴール伝播
• 典型的な宣言的知識
Lineエージェントの効用
10
–ゴール間の関係を記述
–状態には独立
9
8
7
6
15-20
10-15
5-10
0-5
5 Y
• 双方向性問題に対処 →
4
3
2
ゴール間の連想的な処理により、
x,yの何れからゴールが伝播されて
も動作できる
1
0
1
2
3
4
5
6
7
0
9 10
8
X
Ｘ＝Ｙに対応する宣言的知識
(図中 0はInvalidを示す)
10､000回の試行における選択頻度
9000-10000
8000-9000
7000-8000
6000-7000
5000-6000
4000-5000
3000-4000
2000-3000
1000-2000
0-1000
8
4
X
10
6
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000
0
8
8
X
0
Y
9000-10000
8000-9000
7000-8000
6000-7000
5000-6000
4000-5000
3000-4000
2000-3000
1000-2000
0-1000
4
2
4
3
6
0
Y
10
10
8
4
6
X
9
6
0
0
4
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000
0
10イテレーション動作後の選択頻度
0
9000-10000
8000-9000
7000-8000
6000-7000
5000-6000
4000-5000
3000-4000
2000-3000
1000-2000
0-1000
8
2
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000
0
最初のLine動作後の選択頻度
2
外部からのゴール入力
0
Y
おわりに
• まとめ
Q学習などで用いられる効用関数を用いてパターンな情報を
扱うマルチエージェントシステムにおいて、無出力行動と確率
的動作により協調競合機構を導入する方法を提案し、簡単な
シミュレーションにより動作を検証した。
• 課題など
– 計算効率の問題
• エージェント毎にO(3D) (Dは次元数)の時間複雑性を持つ
– ブラックボックス vs. グラスボックスエージェント
• パターンな技術として交渉で交換する情報をどの程度ま
でRichにすることが妥当であるか。
– より適切な協調競合技術との結合

Download Report