制限された環境下における学習型行動プランニング

(1)

修士論文

制限された環境下における学習型行動プランニング

―状況に特化したプランナー選択に基づく手法―

平成

25

年度修了三重大学工学研究科

博士前期課程電気電子工学専攻

篠原駿介

(2)

1

章はじめに

1

第

2

章研究で使用するアルゴリズム

4 2.1 Aアルゴリズム . . . .* 4

2.2 Q

学習

. . . . 5

第

3

章題材とする環境

8 3.1

ゲームベンチマーク

. . . . 8

3.2 Inﬁnite Tux . . . . 9

3.3

優勝アルゴリズムの問題点

. . . . 11

第

4

章提案

15 4.1

提案手法

. . . . 15

4.2 A*

アルゴリズムと

Q

学習の組合せ

. . . . 16

4.3

行動のために得られるデータが限られた環境における提案手法の有効性

. . . . 22

第

5

章実験

24 5.1

各プランナーの性能の評価尺度

. . . . 24

5.2

実験

1：提案手法の性能に関する実験 . . . . 24

5.2.1

実験

1：実験条件 . . . . 25

5.2.2

実験

1

：実験結果と考察

. . . . 26

5.3

実験

2：他手法との比較 . . . . 28

5.3.1

実験

2

：実験条件

. . . . 28

5.3.2

実験

2：実験結果と考察 . . . . 29

第

6

章まとめと今後の課題

30

謝辞

32

(3)

参考文献

33

発表論文

35

(4)

第 1 ^{章はじめに}

近年，PCの性能の向上に伴い，その性能を活かした知的システムの研究が盛んに行われている．知的システムとは，機械やコンピュータの持つ特徴を生かし，さらに人間などの生物がもつ，適応，学習などの優れた機能を取り込んだシステムのことである

[1]．近年では，プロの棋士に勝利したコンピュータプログラム「GPS

将棋」

[2]

，「ツツカナ」

[3]

，「

ponanza

」

[4]

などが話題となっている．また，アメリカにおいては，クイズに挑戦した「Watson」[5]という質問応答システムが話題となった．これら「

GPS

将棋」や「

Watson

」等は複数台の

PC

を利用し，並列クラスタ処理を行うことにより，成果を挙げている

[6][7]．更に， GPGPU(General-purpose computing on graphics processing units)

といわれる技術も注目されている

[8][9]．

この技術は，コンピュータを構成するものの１つである

GPU(Graphics Processing

Unit)

を用いて並列に計算を行うものである．これも

PC

の性能向上に伴って生ま

れた技術であり，

GPGPU

を用いたニューラルネットワーク学習の高速化といった知的システムへの応用も近年報告されている

[10]．

しかし，計算リソース等が少ない，計算のための時間が短いなど，計算コストが制限された場合においては，これらのような高性能化した

PC

の機能を活用した知的システムを構築することは難しい．そのような場合の例として，組み込みシステムがある．組み込みシステムには一般的に，厳しいリソース制約の下，リアルタイム性や，即応性が求められている．例えば，カーナビゲーションにおいて経路探索などでは，運転中に目的地を変更する可能性がある．そのようなときに，経路探索に数十分もかかってしまうことはあってはならない．そのため，専用

LSI

のような専用演算器を開発し，利用することで高速化等が図られているが，

そのような専用

LSI

は一般的に，価格や消費電力等のコストが高くなる．組み込みシステムは低コストで開発が要求されるため，高性能

LSI

を多用することは難しい

[11]

．そのため，前述したような高性能なプロセッサによる並列計算処理を利用することは難しい．

そのため，使用できる計算リソースや計算時間といった計算コストが限られて

(5)

いる環境でも，効果的な知的システムの開発が求められている．そこで本研究では，計算コストが限られた環境下で，効率よく目的を達成することが可能なアルゴリズムの開発を目指す．

制限された環境としては，組み込みシステム以外にもさまざまな環境が考えられる．特に，本研究ではそのような環境として「ビデオゲーム」に着目した．近年盛んに開催されているビデオゲームを題材とした

AI

コンペティションは，さまざまな制限がかけられている．特に，プラットホームゲームベンチマークを題材とした

Platformer AI Competition[12]

では，ベンチマークそのものが，他の問題よりも複雑であり，コンペティションにおける制限も厳しく定められている．そこで，本研究では，制限された複雑な環境として，Platformer AI Competitionで使用された「

Inﬁnite Tux

」

[13]

を使用する．

複雑な環境下において目的を達成するために，プランニングという方法がしばしば用いられる．これは，目的達成のための行動方針，つまりプランを立てることにより，効率よく目的を達成するという方法である．例えば，単純にある状況から行動を直接決定するエージェント（意思決定・行動を行うもの）の場合，その行動後の状況まで考慮していない．その結果，全体で見ると効率のよい行動ができない場合がある．そのような場合において，プランニングを行うことで，一つ一つの行動は最適でなくても，全体で見ると結果として効率の良い行動となることができる．プランニングは，ロボットの行動やナビゲーションの経路探索等様々な分野で用いられている

[14][15]．プランニングを利用する手法においては，プラ

ンナー

(

プランニングを行うもの

)

の性能を向上させれば，システム全体の性能も向上する．しかしながら，制限された環境下において，計算リソース等のコストの問題から，１つのプランナーで考えられるすべての状況に対して適切なプランニングを行うことは難しい．

そこで，本研究では，特定の状況において適切なプランニングを行うプランナーを複数用意し，状況に合わせて適切なプランナーを選択することにより，効率よくプランニングを行う手法を提案する．提案の実装として

A*アルゴリズムと Q

学習の組合せ手法を作成した．本手法は，実際の行動選択は

A*

アルゴリズムで探索することによって行い，プランナーは

Q

学習により

A*アルゴリズムの目標節点の

位置をプランニングするものを複数用意する．各プランナーには，特定の状況においてのみプランニングを行うようにし，限られた計算リソースの下でも効果的にプランニングできるようにする．提案手法の性能は，各プランナーの性能と，選択可能なプランナー数に大きく依存する．これらの要因とプランニング性能との

(6)

関係を実験により調査し，検討する．また，提案手法の有効性を他手法との比較することで確かめる．

本論文の構成を以下に示す．２章では，本研究で使用する

A*アルゴリズムと Q

学習の

2

つのアルゴリズムについて説明する．

3

章では，題材とするプラットホームゲームベンチマーク「Inﬁnite Tux」について説明し，更に

Inﬁnite Tux

を使用したコンペティションにおいて優秀な成績を収めたアルゴリズムとその問題について述べる．

4

章では，効率よくプランニングを行うための手法を提案し，実装と

して

A*アルゴリズムと Q

学習の組合せについて述べる．5章では，提案手法の有

効性を実験によって確認し，最後に

6

章で本研究をまとめる．

(7)

第 2 章研究で使用するアルゴリズム

本章では，本研究で使用する

A*アルゴリズムと，Q

学習について説明する．

2.1 A*

^{アルゴリズム}

A*アルゴリズムは探索アルゴリズムの代表的な手法の一つである [16]．ある節

点から次の節点に移動するときのコストが定められた状態空間を考える．根節点からある節点

n

を通って，目標節点までたどり着くときのコストが最小となる経路を考えた時，根節点から節点

n

までの最小コストを

g(n)

，節点

n

から目標節点までの最小コストを

h(n)

とすると，この経路のコスト

f(n)

は式

2.1

で与えられる．

f (n) = g(n) + h(n) (2.1)

この時，実際に根節点

n

までの最小コスト

g(n)

は探索中に求めることが可能である．目標節点までの最小コスト

h(n)

が不明な場合，

h(n)

の推定を

h

^∗

(n)

とすると，

ある節点

n

を通る最短経路のコスト

f

^∗

(n)

は式

2.2

で見積もることができる．

f

^∗

(n) = g(n) + h

^∗

(n)

(2.2)

式

2.2

において，節点

n

を根節点から目標節点まで近づけながら，コストを小さくする

n

を順に決定することで，最終的に根節点から目標節点までの最短経路を探索することが可能となる．この時の

h

^∗

(n)

をヒューリスティック関数といい，ヒューリスティック関数

h

^∗

(n)

が，目標までの実際のコストを決して超えない見積もりになるように選ぶとき，最適

(いくつかの解があるとき，最も良いの解を見つける)

であり，完全

(解が一つ存在するときに，それを見つけることが保証されている)

である

[16]

．このようなアルゴリズムを

A*

アルゴリズムという．図

2.1

に，

A*

アルゴリズムの例を示す．図中の丸印が節点，節点内の数字が，その節点から目標節点までの推定コスト，矢印がその節点から展開可能な枝，枝に書かれている数字が実際のコストである．図

2.1

の例で，根接点

S

から目標節点

G

までの最短経路

(8)

図

2.1: A*

アルゴリズムの例

を探索する．まず，根接点

S

から，節点

a

を通る最短経路を考えるとき，式

2.2

より，

f

^∗

(a) = 120 + 650 = 770

となる．同様に，

f

^∗

(b) = 1000

，

f

^∗

(c) = 650

となるため，まず節点

c

を通る経路が最小コストの経路となる．これを，図

2.1

内のカッコつき数字の順で評価していくことで探索を行う．結果として，図

2.1

では，二重矢印が根接点

S

から目標節点

G

まで経路探索した結果の解となる．

A*アルゴリズムの問題点として，生成したすべての節点をメモリに記憶してお

くために，探索範囲が広くなると膨大なメモリが必要となることと，ヒューリスティック関数の誤差が実際の経路コストの対数より早く増加する，つまり式

2.3

にあてはまる場合，計算量の指数的爆発が起こることがあげれらる．

| h(n) − h

^∗

(n) | > O(log h

^∗

(n)) (2.3)

2.2 Q

^学習

Q

学習は，強化学習における代表的な学習手法の一つである

[17]．強化学習は，

意思決定を行うエージェントが環境と以下のやり取りを行うことで，学習する

(

図

2.2)．ここで，Q

学習における環境とはエージェントが相互作用を行う対象のこと

を示す．

(9)

図

2.2:

強化学習の枠組み

1.

エージェントは環境から状態

s

を観測する．

2.

エージェントは観測した状態

s

に基づいて行動

a

を選択，実行する．

3.

エージェントは，その行動

a

の結果，行動

a

に対する価値に応じた報酬

r

を環境から与えられる．

4. 1〜3

を繰り返す．

Q

学習において，エージェントは環境から報酬を受け取り，式

(2.4)

の更新式を用い，図

2.3

の手順に従い

Q(s, a)

を更新する．

Q(s

_t

, a

_t

) ← Q(s

_t

, a

_t

) + α(r

_t+1

+ γ max

at+1

Q(s

_t+1

, a

_t+1

) − Q(s

_t

, a

_t

))

(2.4)

ここで，

α

は学習率

(

行動価値観数の更新の度合い

)

，

γ

は割引率

(

将来に得られると期待される報酬が現在においてどれだけの価値があるかの度合い)，sは状態，

a

は行動，

r

は報酬，添字の

t

は時刻を表す．行動価値関数

Q(s

_t

, a

_t

)

の集合を

Q

表と呼ぶ．エージェントは

Q

表を参照することにより，規則に従い行動を選択する．そのため，環境に合わせた

Q

表の作成が必要となる．そこで，行動価値観数

Q(s

_t

, a

_t

)

を最大の報酬を得られるような最適行動価値関数

Q

^∗

(s

t

, a

t

)

の集合である

Q

表を学習によって作成する．Q学習においては，学習率

α

に関する通常の確率近似の条件のもとで，確率

1

で

Q

は

Q

^∗に収束することが示されている

[18]

．

エージェント

状態

5 I

報酬

r I

行動Q

￨環境

(10)

図

2.3: Q

学習の手順

行動選択規則には，現在の状態

s

_tにおける

Q(s

_t

, a

_t

)

から，常に

max

_a_t

Q(s

_t

, a

_t

)

となるような行動を選択する

greedy

行動選択規則，少ない確率で現在の状態

s

_tにおける

Q(s

t

, a

t

)

からランダムに選択し，残りの確率で

max

at

Q(s

t

, a

t

)

を選択する

ϵ-greedy

行動選択規則，現在の状態

s

_tにおける

Q(s

_t

, a

_t

)

から確率的に選択するソ

フトマックス行動選択規則等がある．本研究では，行動選択手法にはソフトマックス手法を用いる．ソフトマックス行動選択規則は，推定価値を等級付けした関数によって，行動確率を変化させる

[17]．すなわち，価値が最も高い行動には最も高

い選択確率が与えられ，他のすべての行動は，その推定価値に従って重みをかけられ，ランク付けさせられる．具体的には，

t

回目の行動

a

を次の確率で選択する．

e

^Q^t^(a)/τ

∑

n

b=1

e

^Q^t^(b)/τ

(2.5)

ここで，τは温度パラメータである．温度が高い場合，すべての行動がほぼ同程度に起こる．逆に低い場合は，価値の推定が異なる動作の選択確率の差がより大きく異なるように設定される．

Q ( s

，

α )

を任意に初期化

各エピソードに対して繰り返し:

Sを初期化

エピソード、の各ステップに対して繰り返し.

Q

から導かれる方策(例えばQに対するソフトマックス行動選択規則) を使って，

s

での行動

α

を選択する

行動

α

を取り，報酬

r

，次の状態どを観測する

Q ( s

，

α )← Q ( s

，

α)+α [ r + Y m a X a ' Q ( s '

，

a ' ) ‑ Q ( s

，

α ) ] s

←‑

s '

s

が終端状態なら繰り返し終了

(11)

第 3 ^{章題材とする環境}

本章では，まず制限された環境の代表的な１つとして，ゲームベンチマークについて説明する．次に，本研究で題材とする制限された環境であるプラットホームゲームベンチマーク「Inﬁnite Tux」と，IEEEで開催されたコンペティション

「Platformer AI Competition」において優秀な成績を得たアルゴリズムについて説明する．

3.1

ゲームベンチマーク

知的システムの性能を測る場合，しばしばゲームを題材としたゲームベンチマークが利用される．例えば，IEEEの学術コンペティションとして，プラットホームゲームを題材とした「

Platformer AI Competition

」，リアルタイムストラテジーゲームを題材とした「StarCraft RTS AI Competition」，巡回セールスマン問題を題材とした「

Physical Travelling Salesman Problem(PTST)

」等，様々なゲームを題材としたコンペティションが開催されている．これらのゲームベンチマークは，

基本的に以下のような特徴を持っている．

1.

複雑な環境である

2.

様々な制限がある

3.

基本的に一般配布されている

本研究では，プラットホームゲームの特徴と，コンペティションの制限の観点から，「

Platformer AI Competition

」に着目する．次節では，本コンペティションにおいて使用されているプラットホームベームベンチマークについて説明する．

(12)

3.2 Infinite Tux

本研究では，様々な制限が課せられている環境として，プラットホームゲームベンチマーク「Inﬁnite Tux」(図

3.1)

を題材とする．IEEEの学術コンペティションとして，2009年から「Platformer AI Competition」が開催されている．本コンペティションでは，プラットホームゲーム「Inﬁnite Tux」が題材として利用されている．プラットホームゲームとは，キャラクターを操作することで台（プラットホーム）を飛び移り，敵キャラクターや障害物を避けながらゴールを目指すゲームの総称のことである．例えば，任天堂株式会社によって発売された「スーパーマリオブラザーズ」等がこれに該当する．

「Inﬁnite Tux」ベンチマークは，意思決定行動を行うエージェントと，ブロックや壁などの障害物，動き回る敵キャラクター，様々なアイテムなどで構成されている．エージェントは，障害物や敵キャラクターを左右移動やジャンプ等で避けつつ，右端にあるゴール地点まで進むことを目的としており，これらに基づいたスコアーによりその性能が評価される．本ベンチマークにおいてエージェントが観測する状態は，エージェントのステータスと位置情報，画面に表示されているブロックなどの障害物の位置情報や種類，動き回る敵キャラクターの位置情報や種類である．エージェントの行動は上下左右移動，ダッシュ，ジャンプ，飛び道具での攻撃の計

7

種類の行動の組合せである．本ベンチマークにおいて，１つのステージは，図

3.1

に表示されている画面の

16

倍の長さであり，エージェントが移動することにより図

3.1

の画面がスクロールする．エージェントは，図

3.1

に表示されている範囲内の情報しか取得できない．エージェントは刻一刻と変化する周囲の状況に合わせて行動する必要が有るため，単純な迷路問題や他のゲームベンチマークと比べ，非常に複雑な環境であるといえる．

更に，本ベンチマークを使用したコンペティションでは，以下の３つの制限が課せられている．

1.

エージェントの一回の行動を決定するまでの計算時間は，約

40[ms]

まで

2.

意思決定を行うために，事前に得ることができるデータは，最大

10000

ス

テージ分のプレイ情報

3.

エージェントの行動を決定する際に使用できる計算機は

1

台のみ（スペックは指定）

(13)

そのため，本ベンチマークにおいては，これらの制限を考慮したアルゴリズムの開発が必要となる．具体的には，以下の二つの条件を満たすアルゴリズムである必要がある．

1.

少ない計算リソースで動作する

(

計算時間や，使用メモリの制限

) 2.

少ない情報量でも適切な行動選択が可能である

(データ量の制限)

実際に「

Platformer AI Competition

」において，優秀な成績を収めたアルゴリズムを表

3.1

に示す．次節では，各アルゴリズムについての簡単な説明と，その問題点を述べる．

図

3.1: Inﬁnite Tux[julian togelius, 2009]

(14)

表

3.1: Platformer AI Competition

における優勝アルゴリズム

[20]

開催年度

2009

年

2010

年

優勝アルゴリズム

A*アルゴリズム

［Robin Baumgarten, 2009］

ルールベースシステム

＋

遺伝アルゴリズム

＋

A*アルゴリズム

［Slawomir Bojarski, 2010］

3.3

優勝アルゴリズムの問題点

3.2

節で述べたとおり，

Inﬁnite Tux

は非常に複雑な環境である．そのため，単純な機械学習や深さ優先探索といった系統的探索アルゴリズムのみを使用する手法では，エージェントを効率よく行動させることは難しい．

A*アルゴリズムは，ヒュー

リスティックを用いた発見的探索アルゴリズムであり，

2.1

節で述べたように効率よく最適な行動を探索することが可能である．そのため，複雑な環境下において

A*

アルゴリズムは有効なアルゴリズムといえる．実際，表

3.1

を見ると，両年と

も

A*アルゴリズムを用いた手法が優秀な成績を収めていることがわかる．

しかしながら，

Inﬁnite Tux

に単純に

A*アルゴリズムを用いるのには大きな問題

がある．それは，

Inﬁnite Tux

の持つ制限の１つである，エージェントの一回の行動を決定するまでの計算時間により引き起こされる．

2009

年度に使用された

A*ア

ルゴリズムは，表示されている

Inﬁnite Tux

の画面右端を

A*

アルゴリズムの目標節点として固定し，表示される画面が切り替わる度に経路探索を行っている

[21]．

図

3.3(a)

のように目標節点までの移動距離が短い場合，

Inﬁnite Tux

の計算時間の制限内に探索が可能である．しかしながら，図

3.3(b)

のように，目標節点までの移動距離が長い場合，Inﬁnite Tuxの計算時間の制限を超過してしまい，適切な行動ができなくなってしまう．

2009

年度

Platformer AI Competition

は図

3.3(a)

のようなステージ構成がほとんであったが，2010年度からは図

3.3(b)

のような状況が出現するステージ構成が追加された．そのため，

2010

年度に

A*

アルゴリズム単体を用いた手法は優勝できなかった．

2010

年度の優勝アルゴリズムは単純な

A*アルゴリズムでなく，それにルール

ベースシステムを加え，遺伝的アルゴリズムによってルールの調整を行っている

(15)

[22]

．こうすることで，大雑把なプランニングをルールベースで行い，その方針にしたがって

A*アルゴリズムで実際の行動を探索している．そのため，本手法は計

算時間の問題を解決している．しかしながら，ルールの作成自体は開発者が行う必要がある．これは，アルゴリズム開発者にとって大きな負担となる．論文

[23]

では，Inﬁnite Tuxに

Deep Boltzman Machine[24]

を適用した結果，ほとんどのシーンが異なったものであったことが報告されている．そのため，大量のシーンを考慮したルール作成が必要となる．さらに，コンペティションで勝利するためには

Inﬁnite Tux

に最適なルールのキャリブレーションを必要とするため，ルールベー

スシステムを使用する手法は

Inﬁnite Tux

に特化してしまう可能性がある．本手法は，2010年度コンペティションでは優勝しているが，本手法の解説をしている論文において，

2009

年度の

A*

アルゴリズム単体には勝利することができなかったことが述べられている．

2009

年度の手法をフローチャートで表すと，図

3.2(a)

のようになる．このような手法は，状況の変化に対応することができない．具体的には，先程述べたように，目標節点までの移動距離が長い場合，A*アルゴリズムでは膨大な計算時間を必要とする．そのため，

3.2

節で述べた，少ない計算リソースで動作するという条件を満たすことができていない．このようなアルゴリズムで性能を向上させるためには，

CPU

の性能の向上や並列計算処理といったことが必要となるが，これは計算リソースを増やすことに繋がるため，本環境下ではこの問題を解決するため，

2010

年度では，ルールベースシステムをプランナーとしてプランニングしている．

これは，図

3.2(b)

のように行動決定の前に大域的な意志決定であるプランニングを行うことで，先の問題を解決しているといえる．しかしながら，単一のプランナーによるプランニングは，そのプランナーのみがすべての状況に対応する必要があるため，このようなアルゴリズムで適切な行動選択をしようとすると，プランナーが必要とする情報量は膨大なものとなることが予測される．このようなアルゴリズムは，

3.2

節で述べた，少ない情報量でも適切な行動選択が可能であるという条件を満たすことができていない．更に，一つのプランナーが複雑な計算を行う必要がある可能性があるため，プランナーのプランニングの仕方によっては，

少ない計算リソースで動作する条件も満たすことができない可能性がある．

そこで，本研究では複数のプランナーを状況に応じて切り替えることで，これらの問題を解決することができる手法を提案する．次章では，提案手法について詳しく説明する．

(16)

(a)

反射的な行動選択

(b)

単一プランナーによるプランニング

図

3.2:

従来の主な手法のフローチャート

状態の入力状態の入力

プランニング

行動選択行動選択

(17)

(a)

探索に成功する場合

(b)

探索が成功しない場合

図

3.3: A*アルゴリズムで探索が成功する場合と成功しない場合

目標節点

(18)

第 4 ^{章提案}

本章では，Inﬁnite Tuxにおける計算時間や計算リソースといった制限を満たしつつ，

3.3

節で述べたアルゴリズムの問題点を解決するアルゴリズムについて説明する．

4.1

^提案手法

本研究では，エージェントが遭遇する状況に合わせて学習型のプランナーそのものを選択することにより，全体の行動をプランニングするアルゴリズムを提案する．提案手法のフローチャートを図

4.1

に示す．図

4.1

のフローチャートにおいて，

状態とはエージェントがその周囲を観測することによって得る情報とし，状態を入力した結果エージェントが判断するものを状況とする．本手法において，エージェントは状況に合わせて，その状況を担当する学習型プランナーを選択する．選択されたプランナーは，学習によって得られた結果より，その状況において目標達成のためのプランニングを行う．最後に，プランニング結果に従い，実際に行動を行う．例えば，図

4.1

において，エージェントが状況

A

に遭遇した場合，プランナー

A

を選択する．選択されたプランナー

A

は，その状況に対応したプランニングを行う．その結果に従い，行動を行う．

このような手順をとることで，前章で述べた計算リソースの問題を解消することが期待できる．各プランナーではそれぞれが限定された状況下でのプランニングを行えばよいので，すべての状況に対応しなければならないルールベースシステムをベースとした従来手法と比べ，一回の行動決定のための計算時間を大幅に短縮できることが期待される．更に，複数のプランナーが同時にプランニングを行う必要もなく，複数台

PC

をつなげた並列計算処理も行う必要がないため，計算リソースの増加も必要としない．つまり，提案手法は少ない計算リソース下でも動作可能となることが期待される．また，複数のプランナーを用意することはアルゴリズム設計者の負担を増すが，各プランナーに学習により機能を獲得するも

(19)

のを用いることで，設計者はプランナー選択部分のみを設計するれば良くなる．

次節では，提案手法の実装として，A*アルゴリズムと

Q

学習を組み合わせた手法について説明する．

図

4.1:

提案手法のフローチャート

4.2 A*

Q

学習の組合せ

3.1

節で述べたとおり，

A*

アルゴリズムは

Inﬁnite Tux

において有効である．特に，文献

[25]

を見ると，コンペティションではルールベースシステムや遺伝的アルゴリズムを使用するエージェントも参加しているが，

A*

アルゴリズムを使用したエージェントが上位を独占していることがわかる．このことからも，A*アルゴ

リズムは

Inﬁnite Tux

の制限下でも，目標節点までの移動距離が十分短い場合に

は，有効であることがわかる．そこで，本手法において，行動選択には

A*

アルゴリズムを利用し，目標節点の位置の調整をプランナーによるプランニングによって行う．

4

犬!I!の入力

グ

ンコ

ニ包

w p

舵ブ

グ

ン対ンニ宛丸

‑

ヲ

パ刊

吋プ

ナ市

HH

U 一グ

トド .

一ンH吋

: ‑

一そ肌

一フパ刊

ブ

行動

• • •

(20)

各プランナーは，

A*

アルゴリズムの目標節点を学習により選択する．本手法では，学習アルゴリズムとして

Q

学習を使用する．Q学習は解を開発者が示す必要なしに，目的を効果的に達成する（報酬を最大にする）行動を自律的に獲得できる．そのため，人手によるルールベースシステムにおけるルールの作成やキャリブレーションといった手間を必要としない．

図

4.2

に

A*

Q

学習の組合せ手法のフローチャートを示す．本手法において，図

3.3(a)

のような状況を状況

A，図 3.3(b)

のような状況を場合に応じて状況

B，状況 C，・

・・とする．各状況には，その状況に特化されたプランナーが存在する．本手法において，状況

A

においては，表示されている画面右端に

A*

アルゴリズムの目標節点を固定するようにプランニングするプランナーとし，状況

B

以降では

A*

アルゴリズムの目標節点の位置を

Q

学習によって選択することによってプランニングするプランナーとする．

例えば，図

3.3(b)

のように前方に大きな壁がある状況を状況

B

とする．この時，

エージェントの周囲

10

×

10

格子の内，足場がある格子を

Q

学習で選択可能な

A*

アルゴリズムの目標節点の位置とする．図

4.3(a)，図 4.3(b)

のエージェント周囲の格子が，

Q

学習で選択可能な範囲であり，図中の丸印が実際に選択可能な目標節点の位置を示している．これらの図のように，選択可能な目標節点は，エージェントを中心とし，相対位置を扱う．こうすることで，

A*

アルゴリズムで探索しなければならない行動数が少なくなるため，3.3節で述べた計算時間の問題の解決が期待できる．

プランナーの選択方法には，さまざまに考えることが可能である．具体的には，

敵との距離や袋小路の有無によって，プランナーを変える方法などがあげられる．

本稿では，隆起している壁の高さに応じて，プランナーを選択するようにしている．図

4.4

に，プランナーの選択方法を示す．図中の塗りつぶされている範囲は，

エージェントが隆起している壁の高さを判別する際に，どの程度細かく判断するかを表す．例えば，図

4.4(a)

のように，画面右側の範囲で大きな壁があるかどうかで見る場合，プランナー数は，

1.

画面右端に目標節点を固定

2.

画面右側に大きな壁がある場合に

Q

学習により目標節点を選択

の２種類となる．また，図

4.4(b)

のように，画面右下半分と，画面右上半分の２つの領域に分け，画面右側に出現する壁の高さがどちらの領域まで到達しているかによって判断することで，プランナー数は，

(21)

1.

画面右端に目標節点を固定

2.

画面右下半分までの高さの壁がある場合に

Q

学習により目標節点を選択

3.

画面右上半分までの高さの壁がある場合に

Q

学習により目標節点を選択の

3

種類となる．同様に，図

4.4(c)

の場合は

4

種類となり，更に分解能を上げることでプランナー数は増加し，最大

16

種類のプランナーを使用することができる．

具体的に，提案手法の動作を説明する．まずエージェントは，図

4.5(a)

のように，Q学習により

Aアルゴリズムの目標節点を選択する．次に， Aアルゴリズム

を用いて，その目標節点までの経路を探索し，実際に行動する．エージェントが目標節点に到達したとき，再び画面右端を目標節点とし，探索を試みる．この時，

探索が成功しなければ，図

4.5(b)

のように到達した地点を新たな探索開始地点とし，

Q

学習により目標節点を選択する．この動作を繰り返し，図

4.5(c)

のように画面右端までの経路が探索可能となった時，再びプランナー

A

が目標節点を固定し，探索を続ける．こうすることで，ステージ全体の行動をプランニングする．

図

4.2: A*アルゴリズムと Q

学習の組合せ手法のフローチャート

(22)

(a)

選択可能な目標節点

(1)

(b)

選択可能な目標節点

(2)

図

4.3: Q

学習により選択可能な目標節点の位置

•

(23)

(a)

プランナー数：2

(b)

(c)

図

4.4:

プランナー数の決定方法

(24)

(a) Q

学習により探索可能な位置に目標節点を変更

(1)

(b) Q

学習により探索可能な位置に目標節点を変更

(2)

(c)

再び目標節点を画面右端に固定

図

4.5:

プランナーによる目標節点の変更の様子

(25)

4.3

行動のために得られるデータが限られた環境における提案手法の有効性

4.1

，

4.2

節において，コンペティションにおける制限のうち，計算時間と計算リソースに対する提案を行った．予備実験

(論文 [c])

より，

A*アルゴリズム単体で計

算時間の問題から探索不可能な状況においても，A*アルゴリズムと

Q

学習の組合せ手法においては，十分に短い時間で探索し，行動できていることが確認できた．

このことから，提案手法は，コンペティションの計算リソースの制限を満たしていることがわかる．

コンペティションでは，この他に学習に用いることのできるステージ数といったデータ量も限られている．本手法は，状況に特化したプランナーを複数用意し，

それらを学習する必要がある．したがって，各プランナーは元々限られた学習用のデータをさらに分け合って利用することとなる．そのため，この点について検討する必要がある．予備実験

(

論文

[d])

より，

Q

学習を行動選択に使用したアルゴリズムで

3000

ステージ学習しても，複雑なステージでは目標達成できていなかったが，プランナー数が

3

の場合の提案手法は，

100

ステージ分の学習により，約

60%

のステージにおいて有効的なプランニングを行うことができたことが確認できた．

このことからも，提案手法は制限された環境下においてもある程度有効的にプランニングできることがわかる．しかし，プランナー数を変更できる場合，提案手法の性能はプランナー数によって変化することが予測される．仮に，全てのプランナーが大量の学習データを持つことが可能ならば，プランナー数は多ければ多いほど，あらゆる状況において適切なプランニングが可能となる．しかし，得られるデータ量に制限がある環境下においては，限られたデータを各プランナーで分け合うため，十分に学習できないプランナーができる可能性がある．そのため，

単純にプランナー数を増加させても，全てのプランナーがそれぞれの対応する状況で適切なプランニングを行うことが可能とはならない．

用いることのできるデータ量の制限が制限された環境下における提案手法の性能については，主に以下の二つの要素が関係している．

1.

各プランナーそれぞれの性能

2.

プランナー数

項目

1

における性能とは，各プランナーが担当する状況おいて，持っているデータ量に対して正しくプランニングができるかどうかを表す．仮に各プランナーの

(26)

性能が低い場合，そのプランナーが担当する状況に対して正しくプランニングできず，結果として全体の行動プランニングの性能も低下する．

また，与えられるデータ量が制限されている本環境において，項目

2

のプランナー数も関係する．仮に，エージェントが得たデータを各プランナーに均等に配分するとする．プランナー数が少なすぎると，それぞれのプランナーが得られるデータ量は多くなるが，それぞれのプランナーが担当しなければならない状況が増えるため，各プランナーにかかる負担が大きくなり，結果としてそれぞれのプランナーが性能を発揮できなくなる可能性がある．しかし，逆に多すぎるとそれぞれのプランナーに与えられるデータ量が少なくなりすぎ，各プランナーの性能が悪くなる可能性がある．

次章では，これらの要素と，提案手法の性能に関して実際に実験を行い調査する．更に他の手法と比較実験を行い，提案手法が実際に有効であるかどうかを実験により確認する．

(27)

第 5 ^{章実験}

本章では，提案法の有効性を実験を通じ確認する．まず

5.1

節で，提案手法が効率よくプランニングできる時の条件を実験により調査し，次に

5.2

節で他の手法と比較することで，提案手法の有効性を示す．

5.1

各プランナーの性能の評価尺度

本手法において，Q学習によるプランナーは学習時に獲得した

Q

表に従って行動を選択する．

Q

表は学習開始時，全て

‘0’

であり，学習を繰り返すことでその値が増減する．学習終了時に

Q

表の

‘0’

を選択するのは，以下の様な場合である．

1.

学習時にその状況に遭遇していない

2.

その状況に有効な行動を学習できていない（‘0’以外の行動が負）

3.

ソフトマックス行動選択規則により確率的に選択される

この中で，項目

3

のランダム選択を行う確率は小さなものであるため，

‘0’

を選択する原因は主に項目

1，項目 2

となる．この

2

つの項目は，学習が不十分，つまり

Q

学習を用いるプランナーにおいては，その性能が十分でないことを示している．

このことから，本手法において各プランナーの性能は

Q

表の

‘0’

を選択する回数に関係すると考え，これも各プランナーの性能の尺度として，実験により評価する．

5.2

実験

1

：提案手法の性能に関する実験

5.1

節で定義した各プランナーの性能，プランナー数とプランニング手法の性能についての関係について，実験により調査する．

(28)

5.2.1

実験

1

：実験条件

今回の実験では，学習に用いたデータ量，プランナー数は，表

5.1

とした．

Q

学習のパラメータとして，学習率，割引率はそれぞれ，本研究室でよく利用される

[26]0.05

，

0.95

とする．報酬は表

5.2

の通りとする．行動選択にはソフトマックス手法を使用し，温度係数は

1.0

とした．Q学習の状態はエージェントの現在の高さとし，行動は目標節点を選択する範囲の決定とした．エージェントは決定された範囲のうち，着地可能な位置を抽出し，ランダムで１つの目標節点を決定する．

A*アルゴリズムは，目標節点に到達するまでの時間が最小となるような経路を

探索し，敵キャラクターからダメージを受ける，穴に落ちるといった経路にペナルティとして大きなコストを与えた．

提示する実験結果は，乱数系列を変えて行った

5

回の実験の平均である．実験に使用するステージは表

5.3

のとおりである．

表

5.1:

提案手法の性能に関する項目

学習に用いたデータ量

[ステージ数] 50，100，1000，または 2000

プランナー数

2,3,4,5,6,8,

または

16

個内訳

:

目標節点右端固定

1

個

+

目標節点学習

1,2,3,4,5,6,7,

または

15

個

表

5.2: Q

学習の報酬

条件報酬

選択した目標節点まで探索不可

-10.0

選択した目標節点まで探索可能その目標節点から画面右端まで探索可能

10.0

その目標節点から画面右端まで探索不可

-1.0

表

5.3:

実験に使用するステージ

level seed

値オプション

学習フェーズ

1 0

〜最大

1999

敵出現

:

無し，大きな壁

:

有りプランニングフェーズ

1 10000

〜

10499

敵出現

:

無し，大きな壁

:

有り

(29)

5.2.2

実験

1

実験の結果を図

5.1

，図

5.2

に示す．図

5.1

において，縦軸は

500

ステージでプランニングした際の

Q

表の

‘0’

を選択した回数，横軸はプランナー数を示す．図

5.2

において，縦軸は

500

ステージでプランニングした際のクリアステージ数，横軸はプランナー数を示す．また，それぞれのグラフのエラーバーは標準偏差である．

図

5.1

より，

Q

表と各プランナーの性能について考察する．学習に用いたデータ量が少ない場合，プランナーの数が増えるにつれ

‘0’

を選択する回数が増加していることがわかる．プランナー数が増加するにつれ，各プランナーが獲得できる情報量は減少する．そのため，学習に用いたデータ量が少ない場合，各プランナーが十分なデータを獲得できず，結果として

Q

表の

‘0’

を選択しなければならない状況に多数陥っている．逆に，学習に用いたデータ量が十分に多い場合，プランナー数がある程度までは

Q

表の

‘0’

を選択した回数はほぼ

0

回である．また，プランナー数が最大の

16

種類の場合は，少し

‘0’

を選択した回数が増加しているが，学習に用いたデータ量が少ない場合と比べて非常に少ない回数に収まっている．これは，各プランナーが十分に学習できているためである．つまり，Q表の

‘0’

を選択する回数は学習に用いたデータ量に大きく依存しており，データ量が十分多ければ，各プランナーの性能も十分なものとなる可能性が高い．

ここで示した結果は，学習に用いたデータ量は最大でも

2000

ステージ分の結果であり，

Platformer AI Competition

における制限内には十分に収まっている．そのため，プランナー数をこの程度に増やしても，コンペティションの制約には全く抵触せずに，十分に学習できるといえる．

次に，図

5.2

より，プランナー数と手法の有効性について考察する．図

5.2

を見ると，学習に用いたデータ量が少ない場合，プランナー数が少ない場合と多い場合でクリア回数に大きな差が出ていない．このような状況下では，先に示したとおり各プランナーの学習が十分ではなく，各プランナーが状況に合わせたプランニングを行うことができず，

Q

表の

‘0’

を選択しランダムに行動した結果だと考えられる．次に，学習に用いたデータ量が多い場合については，以下に示す傾向が現れた．プランナー数が少ない場合はデータ量が少ないときと比べてもより少ないクリア回数となっている．逆に，プランナー数がある程度多い場合は，データ量が少ないときと比べてクリア回数が多くなっている．これは，プランナー数が少なすぎる場合，各プランナーが学習した時に，環境のエイリアス問題が発生してしまい，Q表の値が次々に変更され続け，結果として各プランナーが担当する

(30)

状況に有効なプランナーでなくなっていたためだと考える．プランナー数がある程度多い場合，各プランナーが担当する各状況に対して十分に学習ができており，

結果として良いプランニングができているということである．しかしながら，プランナー数が過剰な場合，各プランナーが取得できるデータが少なくなり，結果として各プランナーの性能が悪くなり，プランニングの性能も悪くなっている．

今回の結果から，提案手法は環境に合わせて学習に用いるデータ量とプランナー数を調整するだけで，プランニングの性能を調整することが可能である事がわかる．特に，今回の条件においては，学習に用いるデータ量は

2000

ステージ，プランナー数

8

の場合が最もプランニング性能が良いことがわかる．

図

5.1:

実験結果：Q表の

‘0’

を使用した回数

(31)

図

5.2:

実験結果：プランニングの有効性

5.3

^実験

2

^{：他手法との比較}

5.2

節で確認した最も良い性能となる条件における提案手法と，他の手法とを実験により比較し，有効性を確認する．

5.3.1

実験

2

：実験条件

比較対象として，本家

Platformer AI Competition

優勝アルゴリズム，2012年度に開催された国内

Platformer AI Competition

優勝アルゴリズムを使用する．

2010

年度優勝アルゴリズムについては，それを解説した論文内において，A*アルゴリズム単体と比べスコアが劣っていると述べられていることから，今回は

2009

年度優勝アルゴリズムである

A*

アルゴリズム単体と比較する．国内

Platformer AI

Competition

優勝アルゴリズムは遺伝アルゴリズムであり，学習は

10000

ステージ

分とした．提案手法は，学習に使用したステージ数が

2000

，プランナー数

8

のものを使用する．

実験に使用するステージは，表

5.3

のプランニングフェーズに用いたものと同様とする．手法の優劣として，500ステージの内のクリア回数と，2012年度国内

(32)

Platformer AI Competition

で使用されたスコア計算方法

(

エージェントの進んだ合計距離)の二通りで比較する．

5.3.2

実験

2

実験結果を図

5.4

に示す．まず，FSS2012で優勝したアルゴリズムである遺伝アルゴリズムは，学習のみで行動している．

Inﬁnite Tux

において，１つのステージをクリアするためには，非常に多くの行動の組合せから選択する必要がある．そのため，学習のみでそれらを取得しようとする場合，

10000

ステージ分のデータ量でも十分ではない．そのため，スコア基準ではある程度の点数を得ることはできたが，大きな壁が出現するようなステージではクリアするまでには至らなかった．対して，提案手法の学習は先程も述べたとおり，プランの学習であり，2000 ステージ分という少ないデータ量でも十分に学習ができた．結果として，遺伝アルゴリズムとは大きな差がついたことがわかる．

更に，A*アルゴリズムと提案手法を比較すると，クリア回数では約

29.9%

，スコアでは約

11.4%

の性能向上が見られた．これから，提案手法は

2009

年度優勝アルゴリズムとくらべても有効であることがわかる．これは，A*アルゴリズム単体で進むことができない状況においても，Q学習によりプランニングすることでその状況を突破することが可能となったためである．クリア回数とスコアで性能に変化があった理由としては，A*アルゴリズム単体で進む場合，ステージ中に大きな壁が出現するまでは，提案手法と同じように進むことが可能であるため，クリアできないステージでもある程度のスコアを得ることができたからである．

これらの結果から，プランナー数と学習に用いるデータ量を適切に調節することができれば，制限された環境下において有効であることがわかる．

表

5.4:

提案手法と他手法の比較

クリアステージ数コンペティションスコア

提案手法

330.2 1,735,076

A*

アルゴリズム単体

254.2 1,512,285

遺伝アルゴリズム

制限された環境下における学習型行動 プランニング