Comments
Description
Transcript
修士論文 連続空間におけるマルチエージェント強化学習 玉越大輝
NAIST-IS-MT9851205
修士論文
連続空間におけるマルチエージェント 強化学習
玉越 大輝
2000 年 8 月 25 日
奈良先端科学技術大学院大学
情報科学研究科 情報処理学専攻
本論文は奈良先端科学技術大学院大学情報科学研究科に
修士 (工学) 授与の要件として提出した修士論文である。
玉越 大輝
審査委員：
伊藤 実 教授
小笠原 司 教授
石井 信 助教授
連続空間におけるマルチエージェント 強化学習3
玉越 大輝
内容梗概
複数のエージェントからなる系において、それぞれのエージェントが互いに協
力、競合しながら何らかの目的を達成するような問題がある。そのような問題を
解く手法の一つとして強化学習が挙げられる。現実的な問題は連続な状態を持つ
が、強化学習アルゴリズムの多くは状態空間が離散系であることを仮定している
ため、そのままでは学習不可能である。
本論文では学習アルゴリズムを拡張し 、連続空間で定義される問題に対しても
適用可能なアルゴ リズムを提案する。提案するアルゴ リズムは
Q 学習を基礎と
し 、学習における評価関数を関数近似器によって近似することで連続系の問題に
対処する。関数近似器として正規化ガウス関数ネットワークを用いる。提案する
アルゴ リズムを追跡問題に適応し 、その有効性を評価する。
また、Actor-Critic 法を用いる連続系アルゴ リズムを追跡退避問題に適用し 、
その有効性を実験により検証する。
キーワード
強化学習, 連続系, マルチエージェント , 正規化ガウス関数ネットワーク
3 奈良先端科学技術大学院大学 情報科学研究科 情報処理学専攻 修士論文,
MT9851205, 2000
年
8
月
25
日.
i
NAIST-IS-
Reinforcement Learning for Multi-agent
Systems in Continous Worlds3
Hiroki Tamakoshi
Abstract
We are interested in the problems in which several agents cooperate and/or
compete with each other to accomplish a task. Reinforcement learning(RL),
which is a sort of machine learning algorithms, have been used to solve such problems. Interesting real world problems such as controling robots have continuous
state and action spaces. Since conventional reinforcement learning algorithms
are dened so to deal with discrete worlds, however, the applications to such
problems have some problems.
Our study intends to propose a modied algorithm applicable to the multiagent problems dened on continuous state and action spaces. The modication
is done by combining the Q-learning and a function approximator. We employ
the normalized Gaussian Network as the function approximator to represent the
RL utility function. The proposed method is applied to a chase problem in a continuous world, which is an instance of cooperation problems. The experimental
result shows that the method works well.
Another algorithm based on the Actor-Critic method is shown. The algorithm
is also applicable to continuous world problems. In order to evaluate the method,
it is applied to a chase-and-escape problem, which is an instance of competetion
problems.
3 Master's
Thesis, Department of Information Processing, Graduate School of Information
Science, Nara Institute of Science and Technology, NAIST-IS-MT9851205,
ii
August 25, 2000.
Keywords:
reinforcement learning, continuous system, multi-agent, normalized Gaussian network
iii
目 次
1.
はじめに
1.1
1.2
2.
背景と目的
論文の概要
1
:::: ::::: ::::: ::::: ::::: :::: ::
:::: ::::: ::::: ::::: ::::: :::: ::
連続空間における強化学習
4
2.1 諸定義 : : : : : : : : : : : : : :
2.2 Q 学習 : : : : : : : : : : : : : :
2.3 正規化ガウス関数ネットワーク
2.4 連続空間における Q 学習 : : :
2.5 最良行動の選択 : : : : : : : : :
2.6 アニーリング : : : : : : : : : :
3.
4.
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
実験
3.1
3.2
1
3
:
:
:
:
:
:
4
5
5
6
7
7
8
連続空間におけるマルチエージェント強化学習問題
:: ::::: ::::: ::
3.2.1 問題設定 : : : : : : : : : :
3.2.2 捕獲者の行動選択 : : : : :
3.2.3 捕獲及び報酬の定義 : : :
3.2.4 実験結果 : : : : : : : : : :
追跡問題
追跡退避問題
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
: 8
: 8
: 8
: 9
: 11
: 11
17
4.1 Actor-Critic 法 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17
4.2 問題設定 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 18
4.3 実験結果 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19
5.
関連研究
22
6.
考察
23
6.1
今後の課題
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23
iv
謝辞
25
参考文献
26
v
図 目 次
1 追跡問題実験環境 : : : : : : : : : : : : : : :
2 行動選択の手法 : : : : : : : : : : : : : : : :
3 捕獲状態 : : : : : : : : : : : : : : : : : : : :
4 平均ステップ数の変化 : : : : : : : : : : : :
5 アニーリングなしにおけるステップ数の変化
6 捕獲の様子 : : : : : : : : : : : : : : : : : :
7 Q 関数値を描くための状態 : : : : : : : : : :
8 学習後の Q 関数値 : : : : : : : : : : : : : :
9 Actor-Critic architecture : : : : : : : : : : :
10 追跡退避問題 : : : : : : : : : : : : : : : : :
11 エージェントの動き : : : : : : : : : : : : :
12 学習後の Critic 値 : : : : : : : : : : : : : :
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
10
10
11
13
13
14
15
16
18
19
20
21
表 目 次
1
報酬の定義
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12
vi
1.
1.1
はじめに
背景と目的
古来より、人間は人間自身を知るという興味に対して哲学的考察を始め様々な
取り組みをしてきた。近年に入り、その興味は計算機械の出現と共に人工知能と
いう知性体の構築といったように様々に形を変えてきた。最近では「エージェン
ト 」という概念を導入し 、それを知的な一個体としてモデル化する試みがなされ
てきている。
エージェントシステムの構築手法には大きく分けて二つの考え方がある。一つ
は、エージェントの行動を予め決定し 、エージェントは決められた手順に基づき
動作するというもので 、もう一方はど う行動すればよいのかエージェントが自
律的に学習するという手法である。前者の手法に基づくエージェントシステムと
しては、計算機ネットワーク上を移動する自律個体としての研究がなされている
[5, 15]。このようなシステムでは、知的な個体のモデル化という点よりもむしろ
エージェントによる分散並列情報処理という応用に重点が置かれている。
しかし一方、古典的手法、つまり、エージェントの「知的な」行動を予め全て
決定する手法には限界があることが以前より指摘されている。例えば惑星探査ロ
ボットをエージェントと見なし 、その行動をプログラムすることを考える。その
時、探査する惑星の環境は未知であるから、古典的手法を適用することは不可能
である。また、環境が既知であるとしても全ての場合について行動を与えるのは
非現実的である。そのような場合にはエージェントが環境に応じて自律的に動作
を変化させるよう学習することが望まれ、また、より「知的」であると言えるで
あろう。それは、未知、或いは変化する環境にも適応していくという点で応用面
でも重要である。実際、例えばサッカーロボットなどに見られるように、近年の
ロボット研究では学習は重要な位置を占めてきている。我々の研究では、学習に
より自律的に行動するエージェントとして知的な個体をモデル化する。
マルチエージェントシステムは文字通り複数のエージェントを含むシステムで
ある。マルチエージェントシステムはそれ自体自然な分散並列情報処理システム
と捉えることが出来るが、むしろ個々のエージェントが各々環境に応じて学習し 、
1
自律行動を起こすという点に着目して、社会のような複雑な系のモデルであると
我々はとらえたい。このとき、社会現象として個々のエージェントが互いに協調
することや、各々の目的や価値観に基づき競合するような現象を学習により獲得
するような問題を考えたい。
各々のエージェントの学習には強化学習 [3] と呼ばれる手法を用いる。強化学習
は機械学習の一手法で、ある問題に対してエージェントが成功した、或いは失敗
したというような経験により、試行錯誤しながら適切な行動を学習していくとい
う概念が基本的な考え方になっている。機械学習の手法には他に大きく分けて教
師付き学習、教師なし学習があり、強化学習はその二つの中間にある学習方式で
あると言える。例えば我々の社会を考えてみる。そこでは一人ひとりがエージェ
ントである。我々はもちろん互いに教え合う部分はあるが、多くは自分で行動し 、
経験し 、それに基づき成長していく。一方教師付き学習ではあらゆる場合に対し
てど う行動すべきが教えてくれる教師がいることが前提になっており、また教師
なし学習ではその逆で行動の指針となる情報が与えられず、どちらも現実的でな
い。従って、エージェントの学習の手法として強化学習を使うことには意味があ
る。ただし 、強化学習は元々エージェントが一人しかいない場合を想定して考え
られたため、学習の収束性といった特性がマルチエージェントシステムにおいて
は未だ得られていない。しかし一方、その手法はマルチエージェントシステムに
おいても有効に働くことが様々な研究により実験的に確かめられている [13,
6]。
そこで、それらの先行研究に鑑み、我々も強化学習を用いる。
ロボットの制御などの現実的な問題では、エージェントを取り巻く環境は連続
空間であり、また行動も連続的である。よって、エージェントを内部状態及び行動
によって定義するとき、状態及び行動は共に連続的となる。一方、強化学習は理
論研究が先行しており、多くの研究は状態及び行動は離散的であると仮定してい
る。従って、従来の強化学習手法をそのまま連続空間におけるマルチエージェント
問題に適用することは困難である。一つの問題として、強化学習が内部で用いる
評価関数の表現の問題がある。この評価関数は、エージェントの状態及び行動の
上に定義される関数であり、ここでは連続空間上で定義されている。もし定義域
が離散ならば即ち有限であるからその関数関係をテーブル表現などで表現出来る
2
が、連続の場合には関数近似器などを用いて表現する必要がある。そこで、我々の
研究では関数近似器として正規化ガウス関数ネットワーク (normalized
Gaussian
network: NGnet)[10] を用いる。NGnet は多層型ニューラルネットワークの一種
であり、入力空間を「柔らかく」分割し 、分割された領域内で出力値を線形近似
するモデルである。
また、本研究ではアニーリングという処理を学習係数に施し 、学習を安定化す
る手法も試みる。アニーリングの効果は実験的に検証する。
本論文では、マルチエージェントシステムにおいてエージェントがとる状態及
び行動が連続である場合に適用出来る強化学習手法を提案する。提案した手法の
有効性を評価するため、連続空間におけるマルチエージェント追跡問題を用意し 、
それぞれに対して適用する。実験の結果、我々の手法が有効に働くことが検証さ
れた。また、ここで提案する学習手法の欠点を補う手法を紹介し 、その有効性を
マルチエージェントシステムにおいて検証するため、追跡退避問題を用意し 、実
験を行う。
1.2
論文の概要
この論文は以下のように構成されている。
2 章では連続空間内で定義される問題に適用可能な強化学習手法を解説す
る。まず基礎となる学習方式について述べ、次に NGnet について解説する。そし
第
てそれらを用いて新たな手法を提案する。最後にアニーリングについて述べる。
第
3 章では追跡問題による実験を行う。二体のエージェントが協力すると目標
を達成することが出来るように問題を作っている。
第 4 章では追跡退避問題による実験を行う。用いる学習アルゴリズムを簡単に
紹介し 、実験の結果を示す。
第 5 章では関連する研究について議論し、本研究の位置付けについて考察する。
最後に、第
6 章で本研究をまとめ、結びとする。
3
2.
連続空間における強化学習
後に複数のエージェントの学習手法を与えるが、まず一体のエージェントにつ
いて考える。
2.1
諸定義
本節では表記を定義すると共に、強化学習の基本概念を紹介する。
s := エージェントが知覚する環境状態
a := エージェントがとる行動
S := 状態 s の集合
A := 行動 a の集合
: S 7! A := ポリシー関数: この関数に基づき、現在の状態に対し行動を
起こす。
( 2 <)
報酬関数: この関数に基づき、各々の状態に対して報酬が与
r
:=
R : S 7! < :=
報酬
えられる。
エージェントは環境の状態を
在の状態に応じて
s として知覚する。エージェントの行動 a は現
によって決定されており、また行動を起こすことで環境の状
態を変化させることが出来る必要がある。更に、行動した結果としてエージェン
トは報酬
r を受け取る。報酬はその時の状態の瞬間的な評価を与えるもので、値
が大きい程よい状態であることを意味する。
エージェントは環境中で次のように活動する。
1.
現在の状態
2.
その行動により、環境と相互作用することで次の状態 s0 に遷移する。また、
s に対して、 により定まる行動 a を起こす。
その時報酬として
r を得る。この報酬は r = R(s0 ) により生成される。
エージェントはどのように行動すればよいか、直接は教えられない。報酬によっ
て間接的にその情報を得ることが出来、1., 2. を繰り返し試行錯誤することでより
4
よい行動を取るよう学習していく。その際、エージェントの目的は与えられた仕
事を達成することであるが、その時に報酬の和が最大になるように報酬関数を設
定する。従って、エージェントの目的は報酬の和を最大にすることと同義となる。
2.2 Q
学習
本研究で提案する学習手法は
Q 学習 [3, 14] を基礎としている。Q 学習では Q
関数を用いる。Q 関数は次のように定義される。
Q(s; a) :=
エージェントが状態
s で行動 a を起こし 、その後は最善の
行動を起こすとするときの報酬の和の期待値。
これより、最適な
Q 関数 Q3(s; a) が得られたとすると、a = arg maxa Q3(s; a)
よりいかなる状態においてもエージェントは最適な行動を選択することが出来る。
従って、問題は最適な
Q 関数を求めることに還元される。
Q 学習は次のように定義される。行動 a の結果状態 s から状態 s0 への遷移が
起こるごとに、次の更新則に則り Q 関数の値が更新される。
Q(s; a)
ここで
0
0
(1 0 t)Q(s; a) + t r + max Q(s ; a )
a
(1)
0
r は r = R(s0) により定まる報酬である。また t 及び はそれぞれ学習
係数及び減衰係数である。
(1) は入力 (s; a) のみについての
Q 値しか更新しないことである。連続状態、連続行動空間においては、(s; a) の
ここで注意しなければならないのは、更新則
組は無限にあるため、この更新則をそのまま適用していては無限の計算量が必要
になる。そこで関数近似器を用いて
Q 関数を表現することでその問題に対処す
る。本研究では関数近似器として正規化ガウス関数ネットワークを用いる。
2.3
正規化ガウス関数ネットワーク
正規化ガウス関数ネットワーク (NGnet)[10] は
N
次元入力ベクトル x と
D次
元出力ベクトル y との関数関係を以下のモデルで与える一種のニューラルネット
5
ワークである。
y
=
gi (x) =
入力空間は
M
M
X
i=1
Niwi =
M
X
i=1
!
gi (x)
w
PM
) i
k=1 gk (x!
2
1 exp 0 jx 0 i j
2i2
(2 ) N2 iN
(2)
(3)
個の正規化ガウス関数によって「柔く」分割され、出力値はそれぞ
れの分割領域における出力の重み付き和として表現される。gi は i 番目のガウス関
数ユニットであり、N 次元の中心ベクトル i と分散 i2 を持つ。wi は
D 次元の
ベクトルである。これより、モデルのパラメータは = fi ; i ; wi j i = 1; 1 1 1 ; M g
2
である。
NGnet の学習は出力誤差についての勾配法で行う。
E
D
X
21 jd 0 yj2 = 12 (dj 0 yj )2
0
j =1
@E
@
(4)
(5)
学習すべき出力 d と実際の出力 y との二乗誤差を
E とする。 は学習係数であ
る。それぞれのパラメータの偏微分は以下で与えられる。
D
X
@E
= (x 0 i)Ni i (yj 0 dj )(wij 0 yj )
@ i
j =1
D
Ni jx 0 j2 0 N X
@E
=
(d 0 y )(w 0 y )
i
@i
2
i j =1 j j ij j
@E
= (yj 0 dj )Ni
@wij
ここで
2.4
(6)
(7)
(8)
i i02 である。
連続空間における
Q
学習
Q 関数を NGnet を用いて
表現する。エージェントが状態を遷移するごとに更新則 (1) に基づき Q 値が計
算され、入力 (s; a) に対してその値を出力するよう NGnet は学習する。NGnet
本研究では連続状態、連続行動空間上で定義される
6
は各々のガウス関数ユニット間の関数値を滑らかに補間して表現するので、未だ
訪れたことのない状態やとったことのない行動についても以前に近い状態や似た
行動をとったときからの類推で近似することが期待出来る。よって、無限の状態
及び行動の組について試行する必要はなくなる。
2.5
最良行動の選択
学習が進むにつれ 、Q(s; a) は最適
Q
関数
Q3(s; a)
に近づくことが 予想さ
れる。従って、学習が進み、収束するためにはエージェントの行動として
a=
arg maxa Q(s; a) を選択することが必要となる。しかし 、行動空間は連続であり、
行動の候補としては無限の可能性があるため、最良の行動 arg maxa Q(s; a) を求
めるのは自明ではない。準最良行動を求める手法が提案されているが [2] 、本研究
では以下の手法を用いる。
現在の状態
s に対し 、選択可能な行動範囲内において 0 個の点をサンプリン
グし 、それぞれの点について
Q 関数の値を求める。その中で最も Q 関数値が大
a0 とする。次に、a0 を中心とするより狭い範囲内におい
て 1 個の点をサンプリングし、同様にその中で Q 関数値を最大化する行動を a1
きくなるような行動を
とする。以下同様にこの操作を繰り返し 、サンプリングする範囲が問題に対して
十分小さくなったとき、その時の行動 an をエージェントがとるようにする。た
だし 、この手法では局所最良行動しか求められないことに注意する。
2.6
アニーリング
学習を安定化させるために、Q 学習
(1) の学習係数 t についてアニーリング
を行う。学習係数を適切に変化させることで、確率近似法 [7] を行うことが出来
る。t を学習エピソード 数として、t t01 ; 0 < < 1 により学習係数を減衰
させる。 は減衰係数である。
7
3.
実験
3.1
連続空間におけるマルチエージェント 強化学習問題
前章において提案した学習手法はエージェント一体について考えた。この手法
はマルチエージェントシステムにも自然に拡張出来る。つまり、各々のエージェ
ントについて各々の状態があり、めいめいの行動を起こし 、それぞれ報酬を受け
取り、それらに基づきそれぞれの
Q 関数を更新していけばよい。
ここで、提案した手法を追跡問題と追い詰め問題の二つの問題に適用し 、有効
性を評価する。
3.2
3.2.1
追跡問題
問題設定
ここで考える問題は、離散空間内で定義された追跡問題 [13] を自然に連続空間
に拡張したものである。
エージェントを取り巻く世界は二次元の平面世界であり、端と端とはつながっ
ている。この世界の中でランダムに動く獲物 (prey) と、その獲物を捕まえる捕獲
者 (chaser) 二人との計三人からなるマルチエージェントシステムを考える。ここ
で個々のエージェントは大きさを持たない点であるとする。獲物は何も学習せず
ランダムに動くが、なるべく捕獲者のいる方向は避けて動く。また、それぞれの
エージェントが一度に動くことが出来る範囲は、自分を中心とする半径 1 の円内
とする。またエージェント
x と y との距離を Dxy で表す。x(y) は p; A; B のい
ずれかである。
獲物は次のように行動する。
1.
現在の自分の位置を中心とする半径
1 の円内の一点を一様乱数を用いて選
択する。選択した点に仮に移動したとして、DpA ; DpB を求める。
2. 1 0 (exp f0DpAg + exp f0DpB g) の確率でその点に移動する。移動しない
場合は 1 に戻って繰り返す。
8
DpA 或いは DpB が小さいほど小さくなる。DpA(DpB ) は仮に移動したと
する位置と捕獲者 A(B ) の現在の位置との距離であるから、この値が小さいとこ
上式は
ろほどその場所へは移動しにくくなる。これによりなるべく捕獲者を避ける動き
を実現する。
捕獲者はそれぞれ次のように行動する。
1.
獲物ともう一人の捕獲者がどこにいるか、自分からの相対位置を調べ、状
態
s として知覚する。この問題では s は相対座標を表す二次元ベクトル二
つからなる。
2. 2.5 節において議論したように、現在の状態 s に対して a = arg maxa Q(s; a)
となる行動を選択する。具体的な選択手法は 3.2.2 節で解説する。上述のよ
うに jaj 1 である。選択された行動に対し 、一様乱数で選択した方向に平
均 0, 分散 0.1 のガウスノイズを乗せ、それを実際の行動とする。これは現
実問題に鑑みると起こそうとした行動と実際に起こした行動の間のずれを
表し 、学習の観点から見ると探索空間を広めることに相当する。
3.
ノイズが乗った行動を起こし 、次の状態に遷移する。その状態に対して報
酬が与えられ、NGnet により表現されている
Q 関数を Q 学習により更新
する。
エージェントの行動の順序は予め決められている。まず獲物が動き、次に捕獲者
A が上に基づき行動し 、そして捕獲者 B が行動する。獲物が捕まるまで各々の
エージェントはこの順番で行動する。また、初期状態に置かれてから獲物を捕獲
するまでを
3.2.2
1 エピソードとする。
捕獲者の行動選択
捕獲者の行動選択は具体的に次のように行う。現在の状態を
s とする。a0 =
(0; 0) を中心とする半径 0.95(= I0) の円を考える (図 3 の大円)。この円を網目状
に切り、中心からそれぞれの格子点へのベクトルを行動ベクトルと見なす。その
とき、それぞれの行動ベクトル
a について、Q 関数値 Q(s; a) を求める。その中
9
prey
B
chaser
A
図
で最大の
1
追跡問題実験環境
Q 関数値を与える行動ベクトル a を求め、a1 とする。例として、図 2
a1 とする。
同様に、a1 を中心とし 、半径 I1 = 0:05I0 の円 (図 2 の中円) を更に細かく網
目状に切り、同じく繰り返す。In が十分小さくなったときの an を捕獲者は選択
において小円で表せられる点を
する。
なお、図
2 において便宜上網目は粗く描いてあるが、実際は円を縦横 20 等分
するような網目である。
図
2
行動選択の手法
10
3.2.3
捕獲及び報酬の定義
獲物の捕獲に必要な条件を次で定義する。獲物を中心とする半径 1 の円を考え
る。捕獲者のどちらかでもこの円内に存在しない場合を状態
1 とする。両方の捕
獲者が円内に存在する場合は更に次のように状態を分ける。
A から獲物を見たとき、もう一方の捕獲者 B が偏角 =6 の中に収まっ
ており、かつ DpA < DAB のとき、つまり図 3 において B が灰色の部分に存在
捕獲者
するとき、獲物を捕獲する可能性がある。この条件は捕獲者が獲物を両側から狭
んで捕まえるということを表している。この条件を満たさない場合を状態 2 とす
る。捕獲する可能性があるときには、捕獲者と獲物との距離が小さいほど捕まえ
易いとする。つまり、exp
状態
f0(DpA + DpB )g の確率で捕獲に成功し 、その状態を
3 とする。捕獲に失敗したときは状態 4 とする。
30degree
B
A
図
3
それぞれの状態に対して、報酬を表
捕獲状態
1 により定義する。この報酬は両方の捕獲
者に対して与えられる。
3.2.4
実験結果
実験は以下の条件の下行った。
世界の大きさは縦
7 横 7 とする。
11
1 -0.2
状態 2 -0.1
状態 3
1
状態 4
0
状態
表
1
報酬の定義
Q 学習のパラメータは 0 0:1; 0:9 とする。アニーリングの減衰係数
は 0:996 とする。
NGnet のパラメータは M 50; 0:1 とする。
エージェントの初期位置はエピソードごとに一様乱数を用いて決定する。
評価は初期状態から捕獲するまでのステップ数の変化、実際の動き、及び学習
Q 関数値を見ることで行う。
平均ステップ数の変化を図 4 に示す。横軸は学習エピソード 数、縦軸はステッ
プ数である。10 エピソードごとにかかったステップ数を平均する。同様の実験
を 5 回行い、それらのステップ数の平均の平均をとったものが図 4 である。実
後の
線はアニーリングありの、破線はアニーリングなしの結果を表す。この図から、
アニーリングありなしにかかわらず、学習が進行していることが分かる。
アニーリングしなかった場合の実験 1 回による結果を図 5 に示す。この図が示
すようにアニーリングしない場合には学習が不安定になる場合がある。従って、
アニーリングすることで学習を安定して進めることが出来ると言える。
次に、学習後の実際の動きを図
6 に示す。矢印はステップごとの動きを示し 、
最も細い矢印が獲物を、二番目に細い矢印が捕獲者
者
A を、最も太い矢印が捕獲
B を表す。また獲物が捕獲された地点を中心として半径 1 の円を描いてある。
Q 関数は 6 次元空間上で定義されているため、可視化が難しい。そこで典型
的ないくつかの状態に対して行動空間上での Q 関数値をスナップショット的に示
す。獲物と捕獲者 B との位置関係が図 7 で示される状態のとき、捕獲者 A がそ
れぞれ A-1, A-2, 及び A-3 の位置にいるとするときの捕獲者 A の Q(s; a) の値
12
図
average of steps (per 10 episodes)
5
average of steps (per 10 episodes)
700
600
500
400
300
200
100
0
700
600
500
400
300
200
100
0
0
0
200
図
200
400
4
400
600
800
1000
1200
episode counts
1000
1200
episode counts
800
1400
1400
1600
1600
平均ステップ数の変化
600
1800
1800
2000
2000
アニーリングなしにおけるステップ数の変化
13
7
7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1
1
0
0
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
7
7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1
1
0
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
7
6
5
4
3
2
1
0
図
6
捕獲の様子
14
6
7
8 に示す。x 軸、y 軸はそれぞれの方向への移動量、z 軸は Q 値である。図
7 における大円の半径は 1, 獲物と捕獲者 B との距離は 0.5 である。図 8 の左
の列が A-1 を、真ん中の列が A-2 を、右の列が A-3 の状態における Q 関数値
を示す。横の列はそれぞれ同一エージェントに対しての Q 関数値である。なお、
jaj 1 であるから、図 8 のうち実際に意味があるのは (0; 0) を中心とする半径
1 の円内の Q 関数値のみである。
を図
A-2
A-3
A-1
30 degree
B
図
問題設定より、捕獲者
7 Q 関数値を描くための状態
A は次に B がどのように動いても、なるべく獲物を挟
むように移動するよう学習しているはずである。従って、A-1 の状態では左に、
A-2 の状態では下に、A-3 の状態では右に移動するのがよい戦略であると予想さ
れる。行動選択は arg max Q(s; a) で行われるため、半径 1 の円内において最も
a
Q 関数値が大きい地点の行動を選択する。従って、図 8 より、予想される行動が
獲得されていることが確認出来る。
15
alue of Q function
alue of Q function
-0.8
alue of Q function
-0.8
-0.85
-0.9
-0.95
-1
-1.05
-1.1
-1.15
-1.2
-1.25
-0.85
-0.9
-0.95
-1
-1.05
-1.1
-1.15
-0.8
-0.85
-0.9
-0.95
-1
-1.05
-1.1
-1.15
-1.2
-1.25
1
1
0.5
-1
0
0.5
movement for x direction
-0.5
alue of Q function
0.5
0
movement
for y directi
-0.5
0
0.5
movement for x direction
1 -1
-0.5
-1
-1.05
-1.1
-1.04
-1.15
-1.2
-1.08
-1.25
-1.1
-1.3
1
0.5
-0.5
-1
0.5
0
movement
for y directi
-0.5
0
0.5
movement for x direction
1 -1
alue of Q function
-0.5
-0.95
-0.9
-1
-0.95
-1.05
-1
-1.1
-1.05
-1.15
-1.1
-1.3
1
movement for y directi
-0.5
1 -1
1
0.5
-1
0
0
-0.5
1 -1
1
0.5
-0.5
0
-0.92
-0.94
-0.96
-0.98
-1
-1.02
-1.04
-1.06
-1.08
-1.1
-1.12
-1.14
-1.25
-1.2
0
movement
for y directi
-0.5
alue of Q function
-1.2
-1.15
-1
0.5
movement for x direction
1 -1
alue of Q function
-0.85
0.5
movement for x direction
1
0.5
0
movement
for y directi
-1
-0.5
1 -1
-0.95
-1
-1.02
-1.06
0
0
-0.98
1
0.5
movement for x direction
0
movement
for y directi
-0.5
alue of Q function
-0.96
-0.5
-1
0.5
movement for x direction
1 -1
alue of Q function
-0.7
-0.75
-0.8
-0.85
-0.9
-0.95
-1
-1.05
-1.1
-1.15
-1
1
0.5
-1
0
movement
for y directi
-0.5
0
movement for y directi
-0.5
0
0.5
movement for x direction
図
8
-0.5
1 -1
学習後の
16
Q 関数値
0.5
-1
0
movement for y directi
-0.5
0
0.5
movement for x direction
-0.5
1 -1
4.
追跡退避問題
2.5 節では行動選択の手法としてヒューリスティクスを用いた。一方連続な行
動空間においてより適切に行動を選択する手法が提案されている [8, 9]。そこで、
連続空間内で定義される問題に適用可能な Actor-Critic 法に基づく学習手法を用
い、エージェント二体からなる追跡退避問題に適用し実験する。
4.1 Actor-Critic
法
Actor-Critic 法によるエージェントの学習は以下のようになる。
Actor := 現在の状態 s に対し 、とるべき行動 a を出力する。
Critic := 状態 s で行動 a をとったとき、その後に得られる報酬の和
の期待値。
Critic は Q 関数と同値。
Actor が状態 s で行動 a を選択する確率 (ajs) を
exp fQ(s; a)=T g
(ajs) R
fexp(Q(s; a)=T )g da
つまり
(9)
で定義する。
エージェントは次のように行動する。
1.
現在の状態
2.
状態は
s0 を知覚する。それに対し 、Actor に従って行動 a0 をとる。
s1 へと遷移し 、報酬 r0 を得る。
3. r0 + Q(s1 ; a1) を求め、(s0; a0) に対する出力として Critic を学習する。つ
まり Critic は基本的に Sarsa に似た学習を行う。
4.
同様に
s1 に対して Actor に従い行動 a1 を起こす。以上を 1 学習エピソー
ドが終了するまで繰り返す。
5. 1 学習エピソードが終了した後、s0 に対して a0 を 、s1 に対して a1 を 、
1 1 1 sTup に対して aTup (Tup は学習エピソードの終了時点 ) を保持するよう
Actor を学習する。
17
これらの関係をまとめたものが図
9 である (詳しくは [8] を参照せよ)。
Environment
State
Reward
Critic
Actor
Action
図
4.2
9 Actor-Critic architecture
問題設定
問題は大きさを持たない二体のエージェントからなり、世界は一次元空間であ
る。捕獲者 (chaser) は獲物 (prey) を追いかけ、また獲物は捕獲者から逃げる。エー
ジェントが一度に動ける範囲は、現在の地点から
10)。
[00:1; 0:1] の範囲内である (図
それぞれのエージェントは次のように行動する。
1.
もう一方のエージェントの自分からの相対位置を調べ、状態
する。この問題では
s として知覚
s は相対座標を表す一次元ベクトルである。
2.
状態
s に対して Actor により決定する行動 a をとる。この問題においては
行動は移動量であり、a は一次元ベクトルである。
3.
状態は s0 に遷移し 、報酬
r
R(s0) を得る。これを用いて Critic を学習
する。
18
4.
以上を繰り返し 、学習エピソードが終了すれば
Actor を学習する。
捕獲者と獲物はそれぞれ相手がどのように動いたかを観察することなしに同時に
行動を実行する。
Prey
図
10
Chaser
追跡退避問題
報酬関数はそれぞれ次で定義する。
捕獲者の報酬関数
(
!
1
j
sj2
j
sj2
Rc (s) exp 0
+ exp 0 2
c1
c2
獲物の報酬関数
jsj2
Rp(s) 1 0 exp 0
!
p
4.3
!)
(10)
(11)
実験結果
実験は以下の条件の下行った。
それぞれのエージェントの位置は
[00:5; 0:5] の範囲内で一様乱数を用いて
初期化する。
Critic の学習のパラメータは 0:9 とする。
捕獲者及び獲物の報酬関数パラメータはそれぞれ c1
0:8 とする。
1 エピソードは 15 ステップとする (Tup 15)。
19
0:1; c2 0:002; p 学習の評価は学習後のエージェントの動き、Critic 値を見ることで行う。
11 に示す。細い矢印が獲物、太い矢印が捕
獲者の動きを表している。横軸はエージェントの状態 (位置) を示し 、縦軸は時間
学習後のエージェントの動きを図
を示している。図より、捕獲者が獲物に近づき、また獲物の動きに追従している
16
16
14
14
12
12
10
10
time
time
ことが分かる。一方獲物は捕獲者から逃げ切れていない。
8
6
6
4
4
2
2
0
0
-2
-1.5
-1
-0.5
0
state
0.5
1
1.5
2
16
16
14
14
12
12
10
10
time
time
8
8
-1.5
-1
-0.5
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
state
8
6
6
4
4
2
2
0
-2
0
-2
-1.5
-1
-0.5
0
state
0.5
1
1.5
2
state
には左方向に動くことが多いことが読み取れる。
獲物についても同様に評価出来る。図より捕獲者がいる方向とは反対の方向に
動くことが多いことが分かる。従って、実際の動きからは分かりにくいが、獲物
は逃げる戦略を獲得していると言える。
value of Critic
value of Critic
3.5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
3
2.5
2
1.5
1
0.5
0
0.1
0.1
0.05
-1
0
-0.5
state
0
-0.05
0.5
1 -0.1
action
0.05
-1
0
-0.5
state
0
-0.05
0.5
1 -0.1
action
5.
関連研究
本研究の最初の動機付けは
Tan[13] によって与えられた。Tan の研究は離散空
間におけるものであり、本研究の最初の実験に用いた問題はそれを連続空間に拡
張したものである。
連続系の問題に対応出来るよう学習アルゴリズムを拡張した研究はいくつかあ
る [2, 11,
4, 9, 8]。Munos[11] は状態及び行動空間を問題に対して十分細かく離散
化した。しかし 、銅谷 [9] も指摘しているようにその手法では学習時間の増加や
必要な記憶容量の増加を招く。実際、Tan[13] らの実験により離散化が細かい程
学習時間が長くなり、解への収束も極めて遅くなることが示されている。Boyan
ら [4] は状態空間上で定義される評価関数を関数近似器を用いて表現している。
しかし一方行動空間は離散空間であることを仮定している。また Baird ら [1, 6]
も同様に行動は離散であるとし 、連続系であるのは状態空間のみであるとしてい
る。行動空間においても制御点を滑らかに補間することにより連続な行動表現を
している [2] が 、有限個の制御点の連結であり表現の精度もあまり高くないよう
である。
本論文で提案した手法では 、行動空間まで含めて関数近似器を用いて評価関
数を表現し 、連続系の問題を本質的にそのまま扱っている。しかし行動選択には
ヒューリスティクスを用いており、連続な行動空間をある意味離散化していると
言える。また実用の観点から見ても多くの計算資源を必要とするため実時間処理
は難しい。
一方吉本ら [8] や銅谷 [9] は連続状態、連続行動を持つ連続時間上で定義された
問題に適用可能なアルゴリズムを提案しており、前者は本論文においても後半の
問題に対して採用している。
22
6.
考察
本研究では、連続系でのマルチエージェント問題に適用可能な強化学習アルゴ
リズムを提案した。正規化ガウス関数ネットワークを関数近似器として用い、評価
関数を表現することで
Q 学習を自然に拡張し 、連続系の問題を扱い可能にした。
提案したアルゴリズムの収束性、解の最適性については証明されていないが、本
論文で取り上げた協調問題である追跡問題に対しては有効に働くことが示された。
しかし 、提案したアルゴ リズムでは行動選択に難点がある。真に連続な問題を
扱うアルゴリズムが提案されているため、その有効性をマルチエージェント競合
問題である追跡退避問題に適用し 、実験的に評価した。より精密な評価が必要で
はあるが、予期する結果のうちの一つを得ることが出来た。
6.1
今後の課題
マルチエージェントシステムではそれぞれのエージェントが互いに観察、協調、
競合、牽制しながら活動している。そのような系では解が複数或いは無限個存在
したり、場合によっては解と呼べるものが存在しない問題もある。そのため、工
学的な観点からは問題としてそもそも不適切であるようなものも存在する。しか
し一方、我々は社会の複雑性の解析をエージェントという視点からとらえること
も目的としている。それを踏まえて次の課題を考えたい。
本研究で取り上げた実験の更に精密な評価が必要である。マルチエージェ
ントシステムであるから、他のエージェントが及ぼす影響があり、学習は
一方通行で進むのではなく複雑な相互作用がある可能性がある。
本研究での実験においても、他のエージェントの位置を観測するという相
互作用はあるが、より積極的にコミュニケーションについて考えたい。コ
ミュニケーションはマルチエージェントシステムの重要な一面であり、ま
た他のエージェントと情報をやりとりすることによりエージェントの個性
の推測 [12] 、学習効率の上昇 [13] といった点が考えられる。またコミュニ
ケーションそのものの発現も重要な課題である。
23
マルチエージェントシステムは一般的に異種エージェントの集合である。そ
のような状況下では、エージェントは個性に応じて、或いは個性を作り出
し 、その結果役割分担が進むと推測される。そのような現象が観察出来れ
ば社会性の一端が見えるのではないかと期待する。
実際にロボットなどを実環境で協調動作させる場合には環境ノイズ、セン
サノイズ、動作ノイズなどの影響を考えなければならない。そのような実
際の応用面にも対応出来るよう、実ロボットを用いた実環境中での実験に
よりアルゴ リズムの検証と改善を考えたい。
24
謝辞
奈良先端科学技術大学院大学情報科学研究科知識工学講座の長行康男、吉本潤
一郎両氏にあたっては先行研究の紹介をはじめ研究内容やアルゴ リズムの検討な
ど 多くの知見を与えて下さいました。石井信助教授には研究の指針を示していた
だき、また研究に対する姿勢にも多く学ぶところがありました。ここに感謝の意
を表したいと思います。
25
参考文献
[1] Leemon C. Baird. Residual algorithms: Reinforcement learning with function approximation. In Armand Prieditis and editors Stuart Russell, editors,
Machine Learning: Proceedings of the Twelfth International Conference, 9-
, 1995. 22 Nov 95
12 July, Morgan Kaufman Publishers, San Francisco, CA
errata corrects errors in the published version.
[2] Leemon C. Baird and A. Harry. Klopf. Reinforcement learning with highdimensional, continuous actions. Technical Report WL-TR-93-1147, WrightPatterson Air Force Base Ohio: Wright Laboratory, 1993. Available from
the Defense Technical Information Center, Cameron Station, Alexandria, VA
22304-6145.
[3] Richard S. Sutton & Andrew G. Barto. Reinforment Learning:
duction, volume 432. MIT Press, Cambridge, MA, 1998.
An Intro-
[4] Justin A. Boyan and Andrew W. Moore. Generalization in reinforcement
learning: Safely approximating the value function. In G. Tesauro, D. S.
Touretzky, and T. K. Leen, editors, Advances in Neural Information Processing Systems 7, pages 369{376, Cambridge, MA, 1995. The MIT Press.
[5] Robert S. Gray. Agent Tcl: A transportable agent system. In Proceedings
of the CIKM Workshop on Intelligent Information Agents, Fourth International Conference on Information and Knowledge Management (CIKM 95)
Baltimore, Maryland, December 1995.
,
[6] Mance E. Harmon and Leemon C. Baird. Multi-player residual advantage
learning with general function approximation. Technical Report WL-TR1065, Wright-Patterson Air Force Base Ohio: Wright Laboratory, 1996.
Available from the Defense Technical Information Center, Cameron Station,
Alexandria, VA 22304-6145.
26
[7] Kushner H.J. and Yin G.G. Stochastic Approximation Algorithms and Applications. Springer-Verlag, 1997.
[8] S. Ishii J. Yoshimoto and M. Sato. On-line EM reinforcement learning. In
The IEEE-INNS-ENNS International Joint Conference on Neural Networks
(IJCNN 2000)
, to appear.
[9] Doya K. Reinforcement Learning In Continous Time and Space.
Computation, 12(1):243{269, 2000.
Neural
[10] J. Moody and C. J. Darken. Fast learning in networks of locally-tuned
processing units. Neural Computation, 1(2):281{294, 1989.
[11] R. Munos. A general convergence method for reinforcement learning in the
continuous case. In Claire Nedellec and Celine Rouveirol, editors, Proceedings of the 10th European Conference on Machine Learning (ECML-98),
volume 1398 of LNAI, pages 394{405, Berlin, April 21{23 1998. Springer.
[12] Ishii S. Nagayuki Y. and Doya K. Multi-agent reinforcement learning: an
approach based on the other agent's internal model. In Fourth International
Conference on Multi-Agent Systems, 2000.
[13] Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative
agents. In Proceedings of the Tenth International Conference on Machine
Learning, pages 330{337, June 1993.
[14] C. J. C. H. Watkins and P. Dayan. Q-learning. Machine Learning Journal,
8(3/4), May 1992. Special Issue on Reinforcement Learning.
[15]
永井保夫, 田原康之, 入江豊, 大須賀昭彦, and 本位田真一.
Plangent I: インテ
リジェント・ネットワークエージェント . Technical Report SIG-HOT/PPAI9603-6, Toshiba Corporation, November 1996.
27