Role-based Context-specific Multiagent Q

先端論文紹介ゼミ
Role-based Context-specific
Multiagent Q-learning
M1 倉野直
目次
Abstract
Introduction
Collaborative multiagent MDPs and
einforcement learning
Role-based context-specific Q-learning
Experiments
Conclusion
2011/1/21
先端論文紹介ゼミ
2
Abstract
 マルチエージェント強化学習における主な問題はエージェ
ント数に従い行動状態空間サイズが指数関数的に増大
すること。
 本稿では行動空間の増加を軽減するために「roles and
context - specific coordination graphs」を利用する。
 全体結合Q関数を部分的Q関数に分解する。
 部分的Q関数は小グループのエージェントで構成され価
値ルールの組で構成される。
 自動的に各価値ルールの重みを学習するマルチエージェ
ントQ学習アルゴリズムを提案する。
2011/1/21
先端論文紹介ゼミ
3
Introduction
 マルチエージェントシステムとは複数のエージェントとの
相互作用で共存するエージェント群。
 マルチエージェントシステムの研究ではエージェントの行
動管理の問題に焦点を当てている。
 本稿では全てのエージェントが共通の目標をもつ完全集
中型マルチエージェントシステムに焦点を当てる。
 エージェントの個々の行動を確認するプロセスはグルー
プ全体の最適政策を学習する。
2011/1/21
先端論文紹介ゼミ
4
Introduction
マルチエージェントシステムを単一の「大きな」エージェント
として扱い、最適政策を学習させる方法。
行動空間が指数関数的に増加するため詳細な設計が難しい
各エージェントが独立した自身の政策を学習する方法。
各エージェントが他のエージェントの情報なしに学習を行う。
収束が学習エージェントの政策に依存するため、安定しない。
2011/1/21
先端論文紹介ゼミ
5
Introduction
 行動空間のサイズを軽減するために最近の研究は
“context-specific coordination graph (CG)”を使用する。
 CGの考え方：
エージェントが個々に行動できる中で少数のエージェン
トの行動の調整を行う。
例）ロボットサッカーにおいて他のロボットが自己の独立した
行動をするなかで、ボールの保持者やその周りのプレイ
ヤーの行動を調整する必要がある。
2011/1/21
先端論文紹介ゼミ
6
Introduction
 本論文ではCGに基づいたマルチエージェントQ学習を提
案する。
 オフライン設計段階では役割に対する価値ルールを定義
する。
 オンライン割り当て段階では、役割割当アルゴリズムを用
いて、エージェントに役割を割当て、エージェントが役割に
対応した価値ルールを得る。
 提案手法ではCGの重みを学習する。
 CGの重みはQ学習から派生した更新式を利用する。
2011/1/21
先端論文紹介ゼミ
7
Collaborative multiagent MDPs (CMMDP)and
reinforcement learning
 マルコフ決定過程を拡張したCMMDP構造を使用する。
 CMMDPは5つの要素＜n,S,A,R,T>より成り立つ。
（n:エージェント数、
S:有限状態空間、
A：行動空間、
R：報酬、
T：状態sのエージェントが行動aを選択し状態s’に遷移した場合に取
る行動の確率）
 Q学習は以下の式を用いて更新される。

Q( s, a)  Q( s, a)   R( s, a)   max Q( s' , a' )  Q( s, a)
a'

(1)
γは報酬割引率、αは学習率とする。
2011/1/21
先端論文紹介ゼミ
8
Collaborative multiagent MDPs (CMMDP)and
reinforcement learning
 Joint action learners （JAL)
この手法はマルチエージェントシステム（MASの）を単一の「大きな」
エージェントとして扱う。
エージェントの状態-行動の組は結合状態空間と元のMASの結合
行動空間である。
「大きな」エージェントの学習にはQ学習を用いる。
欠点：
学習エージェントの状態と行動の組がエージェント数に従い指数関
数的に増加する。
2011/1/21
先端論文紹介ゼミ
9
Collaborative multiagent MDPs (CMMDP)and
reinforcement learning
 Independent learners （IL)
この手法はエージェントが他のエージェントの情報なしに独立した学
習を行う。
指数関数的な結合行動空間を考慮する必要はない。
欠点：
他のエージェントの政策に依存するため、学習の収束が安定しない。
2011/1/21
先端論文紹介ゼミ
10
Role-based context-specific Q-learning
 Context-specific coordination graphs and roles
協調の依存関係はCGを用いて表すことができる。
価値ルールはエージェントが協調行動を実行する文脈を
定義する。
協調の依存関係をG=(V,E)で定義する。
全体結合Q関数を部分的Q関数の和で近似される。
2011/1/21
先端論文紹介ゼミ
11
Role-based context-specific Q-learning
 Context-specific coordination graphs and roles
定義2：
価値ルール   s  a : v  は現在の状態がsであり、
統一行動aを行った時、  ( s, a)  v となる。それ以外は０と
する。
定義3：
Agent[Qi ]  { Ai  A | Ai  Dom[Qi ]}
Qi ( s, a) 
(2)
n

j 1
j
( s, a )
(3)
ここで Agent[  j ]  Agent[Qi ]  0
2011/1/21
先端論文紹介ゼミ
12
Role-based context-specific Q-learning
 Context-specific coordination graphs and roles
定義4：
「役割」の要素は  m, Pm , ri ,m  とする。
（m：役割の数、
Pm：役割mに関連付けられておる価値ルールの組、
ri , m ：はエージェントiが現在の状態で役割mが適当であるかのポテン
シャル関数）
「役割」を2つの段階を用いてCGに内蔵する。
・オフライン設計段階
・オンライン割当段階
2011/1/21
先端論文紹介ゼミ
13
Role-based context-specific Q-learning
 Context-specific coordination graphs and roles
オフライン設計段階
エージェントに対する価値ルールの定義の代わりに役割に対する価
値ルールを定義する。
オフライン設計段階
エージェントに役割を割り当てる役割割当アルゴリズムを使用する。
エージェントは割り当てられた役割から価値ルールを得る。
2011/1/21
先端論文紹介ゼミ
14
Role-based context-specific Q-learning
 Context-specific coordination graphs and roles
役割割当アルゴリズム
|M|>nのとき配列Mを定義する。（M：役割の数、n：エージェント数）
役割の重要度により順序付けされる。
同じ役割は複数のエージェントに割り当てることができる。
エージェントが複数の役割をもつことはできない。
エージェントiと役割mからポテンシャル ri , m を算出する。
2011/1/21
先端論文紹介ゼミ
15
Role-based context-specific Q-learning
 Q-learning in context-specific coordination graphs
定義5： Q i ( s, a ) はエージェントiに対する部分的Q値
Q i ( s, a )   j
 ij (s, a)
nj
(4)
 ij ( s, a) はエージェントiを含む価値ルール。
njはエージェントiを含むそのルールに関係するエージェントの数。
2011/1/21
先端論文紹介ゼミ
16
Role-based context-specific Q-learning
 Q-learning in context-specific coordination graphs
定理１：価値ルール  j ( s, a )は以下の式で更新する。
Q i ( s, a)
 j ( s, a )   j ( s, a )   
ni
i 1
nj
(10)
njはρjに関するエージェントの数。
niは状態ｓで統一行動aが一致しているインスタンスの価値ルール
のエージェントiの出現回数。
2011/1/21
先端論文紹介ゼミ
17
Role-based context-specific Q-learning
 Q-learning in context-specific coordination graphs
学習アルゴリズム
2011/1/21
先端論文紹介ゼミ
18
Experiments
 提案手法RQをJAL、ILと比較する。
 問題設定は追跡問題を適用する。
 10*10のグリッド平面に２体のハンターと１体の獲物を配
置
 ハンターと獲物の行動は上下左右静止の５行動。
 獲物はランダム行動を行う。
 捕獲条件は獲物と同セルおよび
隣接セルに両ハンターが移動。
2011/1/21
先端論文紹介ゼミ
19
Experiments
 RQアルゴリズムにおいて役割を二つ用意する。
capture：獲物を捕獲するように行動する。
Supporter:捕獲者のサポートをする行動を取る。
役割割当の配列は M  {capture, sup porter} となる。
 captureの役割のポテンシャルはハンターと獲物のマン
ハッタン距離に基づく。
1
ri ,capture 
(15)
max( 1, d i , p )
Where d i , p is the distance between predator i and the prey
2011/1/21
先端論文紹介ゼミ
20
Experiments
各ハンターが得る報酬は以下に示す。
50.0　エージェント iが他のハンターの支援を受けて捕獲した場合

 50.0　他のハンターと衝突した場合
Ri ( s, a)  
（ 16）

10
.
0
エージェント
i
が支援なしに獲物の方
へ移動する場合


 1.0　それ以外
2011/1/21
先端論文紹介ゼミ
21
Experiments
実行結果
2011/1/21
先端論文紹介ゼミ
手法
平均捕獲ス
テップ
RQ
12.92
JAL
12.78
IL
17.02
22
Conclusion
 role-based context-specific multiagent Q-learning手法
を提案。
 Role and context-specific coordinarion graphsを使用。
 自動的に各価値ルールの重みを学習するQ学習アルゴリ
ズムを提案。
 実験は従来のマルチエージェント強化学習より大幅に速
い学習速度で同じ政策に収束することを示した。
2011/1/21
先端論文紹介ゼミ
23
ご清聴ありがとうございました。
2011/1/21
先端論文紹介ゼミ
24
Role-based context-specific Q-learning
 補足1
例）状態ｓと状態s0が以下の規則をもつ。
 1 ; s  a1  : v1    5 ; s ' a1  : v5 
  2 ; s  a1  a 2 : v 2    6 ; s ' a1   a 2 : v6 
  3 ; s  a 2  a3 : v3    7 ; s ' a 2  a3 : v7 
  4 ; s  a 2  a3 : v 4    8 ; s ' a 2  a3 : v8 
エージェントは状態ｓに協調行動a＝{a1,a2,a3}を行い、状態はs’に
*
遷移する。状態s’での最適行動は a  {a1 , a2 , a3 } である。
従って状態sにおいてルールρ1、ρ2、ρ4が表れ、状態s’において
ルールρ5とρ7が表れる。
2011/1/21
先端論文紹介ゼミ
25
Role-based context-specific Q-learning
 補足1
次のようにρ1、ρ2、ρ4を更新する。
v5
v 
v
 1  2 
1
2 
 1
v7
v 
v
Q 2 ( s , a )  R 2 ( s , a )  
 2  4 
2
2 
 2
v7
v
Q 3 ( s , a )  R3 ( s , a )  
 4
2
2
Q 1 ( s , a )
 1 ( s, a )  v1  
2
 Q 1 ( s , a )
Q 2 ( s , a ) 
 2 ( s, a )  v 2   


2
2


Q 1 ( s , a )  R1 ( s , a )  
 3 ( s, a )  v3
2011/1/21
 Q 2 ( s , a )
Q 3 ( s , a ) 



2
1


先端論文紹介ゼミ
26
Experiments
 補足2:生成される価値ルールの一例
 1captuer ; ai  moveTo(dir ) : 100 
  2captuer ; has  role  sup porter ( j )
 is  adjacent  to  prey ( j )
 ai  moveToprey()
 a j  moveTo(center) : 100 
価値ルールρ1は捕獲者の役割が他の支援者となるハンターの支援
がなくても獲物をほかうしようとするべきと示す。
ルールρ2は捕獲者が獲物の位置に動き、支援者が現在の位置で静
止する連携文脈である。
2011/1/21
先端論文紹介ゼミ
27

Download Report