2 - 山口大学 生体情報システム工学研究室

Report
2010/10/15
先端論文紹介ゼミ
「A layered approach to learning
coordination knowledge
in multiagent environments」
(マルチエージェント環境で知識を調整学習するレイヤー型アプローチ)
山口大学大学院 理工学研究科
M2 兼平 龍
1
1. イントロダクション-Introduction



かつては強化学習についての研究は主にシングルエー
ジェントでのシステムに集中していました.
しかし、自律的シミュレーションなどの複雑なアプリケー
ションが増えていく中マルチエージェントシステムが重要
になり様々な研究が行われてきました.
本論文では追跡問題において新しいマルチエージェント
学習アルゴリズムを提案した.
アプローチの独創性として…
・2レベル学習アルゴリズム
・ハンター間における潜在的コミュニケーション
があります.
2
2.強化学習-Reinforcement learning

強化学習とは環境からの試行錯誤的なインタラクションにより最適な
行動を学ぶ事です.一般的なものとしてQ学習・Sarsaがあります.
Q学習はQ値を政策を用いて行動決定に利用します.Q学習において
状態-行動の組の価値はQテーブルに置かれ、以下の公式に従い更
新されます.
・行動選択メカニズム
今回使用するボルツマン選択は各々の行
動を選ぶ可能性を計算します.温度tは可能性
を調整するパラメータで、徐々に減少させます.
3
2.強化学習-Reinforcement learning
マルチエージェント強化学習
シングルエージェント強化学習を複数のエージェントに広げた
ものです.しかし、ロボティクスやネット上のソフトウェアのような
現実問題にQ値(状態-行動の組)を適応させる事は困難です.

階層型強化学習(HRL)
そこで、状態空間が階層的に構築される強化学習の研究が
されてきました.HRL方法はより早く政策を学びますが、現在は
シングルエージェントでの研究であり、マルチエージェントの様
な複雑な問題では実用されていません.
4
3.問題設定-Problem domain追跡問題の解説

・
・
・
・

2種類(ハンター・獲物)のエージェント
エージェントは視覚の深さdで観測することが出来ます
ハンターと獲物は別々のステップで行動します
ハンターが獲物の周りを囲んだ時、終了(捕獲)とします
獲物
・ 獲物は大小2つのタイプがある.
大きい獲物[P]:2体以上のハンターで捕まえる
図.2 深さ3のハンターH1の観測範囲
小さい獲物[p]:1体のハンターで捕まえる
・ 獲物の観測範囲内にハンターがいる場合、最も近いハンターのマンハッタン距離が
最大になるように動く(ハンターから逃げる)

ハンター
・ ハンターは観測範囲内で獲物・最も近いハンターを観測する(状態空間節約のため)
5
4.コミュニケーションによる2レベル強化学習
-Two-level reinforcement learning with communication-
開発したアルゴリズム.
4.1利己的ハンター(SRL,NRLハンター)
 SRLハンター:他のハンターを考慮しない
ハンターは環境として大小の獲物を観測し行動します.

協力するハンターがいるにも関わらず小さい獲物に続いたり.反対
に誰もいないのに大きい獲物を選んでしまう事がある.

NRLハンター:近いハンターを状態空間の1部に含む
行動を選ぶ際に近いハンターの位置情報も観測します.
他ハンターと大小の獲物を含むため状態空間は大きく、学習は遅く
なるが潜在的な協調行動を示すようになるかもしれない.
6
4.コミュニケーションによる2レベル強化学習
-Two-level reinforcement learning with communication-
4.2 2レベル強化学習コミュニケーションエージェント
・第1レベル:協力的(隣のハンターの後を追う)か、自己的
(自身が大きい獲物を捕まえる)かの決定を行う.
・第2レベル:第1での決定により行動を選ぶ.
2
レ
ベ
ル
強
化
学
習
法
・2LRL-1.1「1:レベル1の学習無し」
 2LRL-1「1:大きい獲物のみの環境」
・2LRL-1.2「2:レベル1の学習あり」
 2LRL-2「2:大小の獲物がいる環境」
・2LRL-2.1「1:レベル1の学習無し」
・2LRL-2.2「2:レベル1の学習あり」
※コミュニケーションとして隣にいるハンターは近い大きい獲物の距離を送ります.
7
4.2.1大きい獲物のみの環境の2LRL-1アルゴリズム
第1レベル
第2レベル
Aの観測情報
Bからの獲物の位置
Q
テ
ー
ブ
ル
・Qfollow(状態:観測[位置]情報×送られた獲物位置,行動:あとに続くor続かない)
・QOwn(状態:大きい獲物の位置,行動:上下左右止の5行動)
・QOther(状態:観測情報×大きな獲物の距離,行動:上下左右止の5行動)
8
4.2.1大きい獲物のみの環境の2LRL-1アルゴリズム

2LRL-1.1:バージョン1(レベル1の学習なく、指示がある)
・ 隣のハンターの後に続く、続かないという決定はない.
・ 自己の観測情報とコミュニケーション情報が与えられる.
・ 2ハンター間(自己、隣)で獲物までの距離を比較し、自己の距離
が遠い場合QOtherより後を追うようになる.

2LRL-1.2:バージョン2(レベル1の学習あり、指示が無い)
・ 隣のハンターに続くかどうか学習をする.
・ このバージョンでは自己と隣の大獲物の距離を比較して…
・自分の距離が小さいなら:自身に従い行動する
・自分の距離が大きいなら:隣のハンターの後を追う行動をする
を学習します.
9
4.2.2大小の獲物のいる環境の2LRL-2アルゴリズム
※ハンターの観測情報や隣との情報は省略
小さい獲物を追いかける
大小の獲物の選択に使用
大きい獲物を追いかける
・Qfollow:ハンターの後に続くか、獲物を追うかの選択に使用.
・Qprey:大小どちらの獲物を選ぶかの選択に使用.
・QOwnp:獲物を追う場合での小さい獲物を追いかける際の行動に使
用.
・QOwnP:獲物を追う場合での大きい獲物を追いかける際の行動に使
用.
こちらも
レベル1の学習ありなしで
2LRL-2.1(レベル1なし)
2LRL-2.2(レベル1あり)
…分けられ10
4.2.2 2LRL-2アルゴリズムでの行動選択例
Lv1 A:3マス<B:5マス・・・Lv2 Aに続く:↓行動
5マス
4マス
Lv1 A:3マス<B:5マス・・・獲物を追う
3マス
Lv2 p:4マス<P1:3マス・・・P1を追う:↓行動
11
4.3 2レベル強化学習アルゴリズムの利点
1. 状態空間のサイズがエージェントタイプ(ハンター,大小
の獲物)ごとに異なるQテーブルを用いているため大幅
に減少される.
2. ハンターの行動選択の第1レベルにおいて目標を学び
、第2レベルにおいて目標を追いかけます.つまり、小さ
い獲物を追いかけるハンターは大きい獲物の観測情報
を考慮しないで済むという事です.
3. アルゴリズムに関しては多くの獲物が存在する環境に
も適用できる.
12
5.シミュレーション結果
表.入力セット

・
・
・
・
今回実装したアルゴリズム
SRL(利己的)ハンター
NRL(隣の情報もある)ハンター
2LRL-1(大きい獲物だけの2レベルRL)
- 2LRL-1.1(レベル1なし)
- 2LRL-1.2(レベル1あり)
2LRL-2(大小の獲物がいる2レベルRL)
- 2LRL-2.1(レベル1なし)
- 2LRL-2.2(レベル1あり)
※Q値が収束するまでトレーニングを行い
のちにテストを行う.
sg:グリッド(sg×sg)の一辺のサイズ
H:ハンター数
p:小さい獲物の数
P:大きい獲物の数
13
5.1温度定数の決定
Ntest:テスト期間でゴールまでのステップ数
異なる温度で入力セットIn1を使用したSRLの結果.
tを1から0.3へ減少させる事にした.
14
5.2.1~各アルゴリズムの比較結果

SRLとNRLの比較
⇒NRLの方が悪い結果となった.原
因としてはエージェントがQテーブル
を切り離す方法では全ての組を探索
できなかった事がある.

SRLと2LRL-1.1の比較(小さいグリッド)
⇒結果として、SRLと2LRL-1.1との違
いはあまり表れなかった.しかし2LRL1.1がわずかに良かった点としてSRL
には見られなかった協調行動が確認
できた事です.
15
5.2.1~各アルゴリズムの比較結果

SRLと2LRL-1.1の比較(大きいグリッド)
⇒協調行動の重要性を強調するた
めに大きいグリッドでテストした.ま
た、有利に働く初期位置の場合も行
い2LRL-1.1はさらに良い結果を示し
た.

2LRL-1.1と2LRL-1.2の比較
⇒2LRL-1.2ではQテーブルが多いた
め学習までに時間がかかったが、
2LRL-1.1と同等の結果となった.
16
5.2.1~各アルゴリズムの比較結果

SRLと2LRL-2.1の比較
⇒2LRL-2.1はSRLと比較して良い結
果となった.

2LRL-2.1と2LRL-2.2の比較
⇒2LRL-2.2では、隣のハンターに続く
か続かないという正しい行動はできた
が、Qpreyテーブルが収束することが
出来ず大小の獲物を決め追いかける
学習が出来なかった.
17
6.結論と今後




マルチエージェント学習における、コミュニケーションによる
2レベル決定メカニズムを開発しました.
2つの階層的なレベルに分ける事でハンターの観測範囲内
での全て状態を考慮する代わりに、状態空間のサイズを一
定にすることを可能にしました.
しかしハンター間での協調行動は確認できたが、きちんと
近い獲物を追いかける学習はできませんでした.
今回は特定の問題設定であったが、使用の修正により多く
のハンターのいる集団行動のメカニズムでも良い結果を示
すかもしれません.
18

similar documents