マルチエージェント強化学習による 協調性獲得の検証

マルチエージェント強化学習による
協調性獲得の検証
―追跡問題を例として―
高知大学大学院
理学研究科
櫻井
数理情報科学専攻
祐輔
2008 年 2 月 12 日
要旨
マルチエージェントシステムは複数の自律的に動作する主体(エージェント)によ
り構成されるシステムであり，自律性，協調性などによる柔軟な問題解決能力が期
待されている。一方，強化学習は試行錯誤を繰り返し，目的にかなった行動をとっ
た時に得られる報酬に基づき適切な行動を学習する手法であり，マルチエージェン
トシステムの実装法として非常に有効な手段である。
本研究では，マルチエージェント問題に対し強化学習を適用し，得られるエージ
ェント間の行動の評価を行う。問題としては 2 つのエージェントが 1 つのターゲッ
トを追跡・捕獲する追跡問題を扱う。追跡問題では，捕獲直前に譲り合いなどの協
調的動作が表れると期待される。学習アルゴリズムは Q(λ)学習と Profit Sharing
の 2 種類を考慮した。Q(λ)学習では得た報酬をλの値で減衰させながら伝播させる
ことで過去にとった行動の強化を制御できるため，λの値を 0，0.5，0.9 の 3 種類
設定する。これに Profit Sharing を加えた計 4 種類で強化学習を行い，協調動作が
期待できる状態においてエージェントが獲得した行動を評価した。
実験結果の一例としてターゲットを右端に 2 つのハンターが横一直線上に並んだ
状態を挙げる。この場合の協調的動作の獲得率は Q(0)が 62％，Q(0.5)が 71％，Q(0.9)
が 52％，Profit Sharing が 90％となり，アルゴリズムによって協調的動作の獲得率
に差が生じた。捕獲までのステップ数を比較すると Q(0.5)と Profit Sharing が最も
捕獲が早く平均 50 ステップ，次に Q(0.9)が平均 80 ステップで捕獲に成功している。
それに対し，Q(0)は捕獲までに平均 400 ステップを要した。これはλの値による影
響で，λが 0 の時は過去に報酬を伝播しないため捕獲直前に至るまでの行動の強化
ができず，0.9 の時は報酬の伝播量が大き過ぎ，過去の良くない行動まで強化してし
まったためと考えられる。以上より，協調動作の獲得には Profit Sharing が有効で
あり，また，Q(λ)学習はλの値を調整することで柔軟な学習ができることが判った。
1
1．はじめに
１
2．マルチエージェントシステムと強化学習
２
2.1 マルチエージェントシステム
２
2.2 マルチエージェントシステムに関する研究例
２
2.3 マルチエージェントシステムの利点
３
2.4 強化学習
４
2.4.1 強化学習の構成要素
４
2.4.2 強化学習の枠組み
７
2.5 強化学習の学習アルゴリズム
2.5.1
７
Q-Learning
2.5.1.1
７
Q-Learning の学習アルゴリズム
2.5.1.2 適格度トレースと Q(λ)
2.5.2
８
Profit Sharing
2.5.2.1
７
10
Profit Sharing の学習アルゴリズム
2.5.2.2 合理ルールと非合理ルール
10
10
3．過去の研究例と本研究の目的
14
3.1 過去の研究例
14
3.2 本研究の目的
14
4．マルチエージェント強化学習によるエージェントの協調動作の検証
4.1 問題設定
15
15
4.1.1 追跡問題
15
4.1.2 使用するアルゴリズムとパラメータ設定
17
4.1.2.1
Q-Learning の設定
17
4.1.2.2
Profit Sharing の設定
18
4.2 アルゴリズムとパラメータ設定の違いによる学習効率の比較
18
4.2.1 評価の方法
18
4.2.2 実験結果と考察
19
4.3 獲得した動作の協調性の評価
21
4.3.1 評価の方法
23
4.3.2 検証結果
25
4.3.3 考察
31
4.3.4 今後の課題
32
5．まとめ
33
謝辞
34
参考文献
35
付録
2
１．はじめに
近年，システムの並列処理，分散処理といった観点からマルチエージェントシステム
の応用が期待されている。マルチエージェントシステムは，複数のエージェントがそれ
ぞれ自分に与えられた目標を達成することでシステム全体の目標を達成するというシ
ステムである。マルチエージェントシステムではエージェントの行動が互いに影響を及
ぼしあうため，各エージェント間の協調性が非常に重要な意味を持ってくる。しかしな
がら，扱う問題が複雑になるほどエージェント間の相互作用の実装は困難になる。そこ
で，マルチエージェントシステムの実装方法として強化学習が注目されている。
強化学習(Reinforcement Learning)は，試行錯誤を繰り返すことで得られる報酬
(reward)という値を手がかりに，適切な行動を学習していく機械学習法の一種である。
目標とする状態が自明であれば，そこに報酬を設定してやるだけで自律的に学習を行う
のでマルチエージェントシステムの実装方法として非常に有効な手段であるといえる。
しかし，機械学習によって学習した行動ルールが協調的であるかどうかには疑問が残る。
本研究では強化学習によってエージェントが学習した行動の協調性という点に焦点
を当てる。Q-Learning と Profit Sharing の 2 種類の学習アルゴリズムを取り上げ，マ
ルチエージェント系の代表的なベンチマークである追跡問題への適用を通じて各エー
ジェントが学習した行動の協調性の検証を行った。
以下，2 章ではまずマルチエージェントシステムと強化学習について述べる。3 章で
はこれまでに行われてきたマルチエージェント強化学習に関する研究の一例を紹介す
る。4 章では，強化学習に用いる追跡問題の設定と学習アルゴリズムのパラメータ設定，
実験の手法，実験結果，協調性の評価の方法とその検証結果及び考察を述べる。5 章は
まとめで本研究の成果と今後の研究課題について論じる。
3
2．マルチエージェントシステムと強化学習
2.1 マルチエージェントシステム
マルチエージェントシステムとは，複数のエージェントから構成されるシステムであ
る。各エージェントは自分が置かれている環境情報を知覚し，自分に与えられた目標を
達成するように行動をすることで，システム全体の目標を達成するという枠組みになっ
ている。この枠組みを利用してタスク割り当て問題やスケジューリング問題などの組み
合わせ問題の解決や，パターン認識，自律ロボットなどの分野で応用が試みられている。
マルチエージェントシステムではエージェントが相互に影響を及ぼし合うため，それが
各エージェントの行動選択基準にも影響を与える。そのため協調的な行動ルールの実装
が重要となってくるが，その実装が手動では難しいという問題点がある。マルチエージ
ェントシステムにおけるエージェントの行動ルールには，全てのエージェントが同じ行
動ルールで動く Homogeneous（均質）型と各エージェントが異なる行動ルールで動く
Heterogeneous（異質）型があり，それぞれ表 2.1 のような利点と欠点を持つ。
表 2.1
Homogeneous 型と Heterogeneous 型の利点・欠点
利点
Homogeneous 型
Heterogeneous 型
欠点
役割分担など複雑な協調動
構造が単純
作が困難
役割分担など複雑な協調動
プログラムのサイズが大き
作が可能
くなってしまう
2.2 マルチエージェントシステムに関する研究例
マルチエージェントシステムの実世界への適用例として，以下のような研究がある。
(Ⅰ)RoboCup[1]
(ⅰ)RoboCupSoccer
ロボット工学と人工知能の発展を目的とした，自律移動ロボットによるサッ
カー大会。1992 年に発足，1997 年に第一回世界大会が開催される。以後，毎
年世界各地で大会が行われており，2050 年までに人間の世界チャンピオン・
チームに勝てる自律ロボットのチームを作ることを目標に掲げている。
4
(ⅱ)RoboCupRescue
RoboCupSoccer で培われた技術を災害時の救助に利用しようというプロジ
ェクト。阪神・淡路大震災や新潟県中越地震などの大規模災害発生時を想定し
て救助戦略を発展させようというシミュレーションと，災害現場で救助に役立
つ自律型ロボットの開発を目的とした活動である。
(Ⅱ)大規模交通制御（中丁ら 2002[2]），（北田・田中 2005[3]）
ドライバー間で移動情報を共有することで，動的に移動経路の変更を行い移動時
間の削減を可能にする「協調カーナビ」や乗客の需要に合わせて運行経路を変更
する「デマンドバス」への適用などがある。
(Ⅲ)株価変動予測（池田・時永 2007[4]）
マルチエージェントを用いて市場株価の時系列のカオス性・フラクタル性の分
析を行う。これを用いて，株価変動の予測シミュレーションを行う。
2.3 マルチエージェントシステムの利点
マルチエージェントシステムは，以下のような利点を持っている。
●問題解決能力の向上
単体のエージェントでは解決できない問題でも，複数のエージェントが集まることで
解決することができる。また，1 つ 1 つのエージェントの能力が低くても，複数で協
調しあうことでより高度な問題を解決できる可能性がある。
●適応能力
エージェントが自律的に行動するため，問題の変更や問題規模の拡大・複雑化などに
対して非常に柔軟に対応することができる。また，外乱や不測の事態が生じた時も同
様の効果が期待できる。
●ロバスト性
あるエージェントが故障や暴走などにより使いものにならなくなっても，他のエージ
ェント達が代役をすることで，システム全体の機能を維持することができる。したが
ってより安定で信頼性のあるシステムを構築できる。
●並列性
エージェント間の整合性をとる処理，あるいはオーバーヘッドなどが少ない問題の場
合，各エージェントは並列的かつ非同期的に動作することができるため，システム全体
の処理速度の高速化，処理効率の向上などが期待できる。
5
●モジュール性
マルチエージェントシステムはエージェント単位でモジュール化されているので，初
めからシステムの詳細設計をし直さなくても既に設計済みのエージェントを再利用，ま
たは組み合わせることで，設計コストと時間を抑えることができる。また，システムの
テスト実験や維持管理もエージェント単位で行うことができる。
2.4 強化学習
エージェントの行動ルールの実装方法の１つとして強化学習がある。強化学習とは機
械学習の一種で，離散的な時間ステップ t = 0,1,2,3 ･･･における状態 s t に対し試行錯誤を
繰り返し目的にかなった行動をとった時に得られる報酬という値に基づき環境に対す
る適切な行動を学習していくという手法である。逐次的な教師信号を不要とし，目標と
する状態が既知であればその状態にたどり着いた時に報酬を与えるように設定すれば
よい。強化学習はマルチエージェントシステムにおけるエージェントの実装方法として
非常に有効である。本項では強化学習の構成要素と枠組みについて説明する。
2.4.1
強化学習の構成要素
強化学習には 4 つの主な構成要素がある。それは方策(policy)，報酬関数(reward
function)，価値関数(value function)，環境のモデル(model)である。本項ではこの 4 つ
の構成要素について説明する。
(1)方策(policy)
方策は，ある時点でのエージェントの振る舞い方を定義する。言い換えると現在知覚
している状態から，その状態で実行可能な行動を選択する確率への写像である。π ( s, a)
で表現し，状態 s において行動 a を選択する確率を意味する。この方策に従ってエージ
ェントの行動は決定される。方策を用いた学習法を方策オン型手法といい，用いない学
習法を方策オフ方手法という。方策は一般的にソフト(soft)であり，これは，全ての
s ∈ S , a ∈ A( s) に対して π ( s, a) > 0 （ S は状態 s の集合， A(s) は状態 s において選択可
能な行動 a の集合）であることを意味している。また方策オン型手法には種々の変形手
法がある。その一例としてグリーディ(greedy)方策とε-グリーディ(ε-greedy)方策を
紹介する。
・グリーディ(greedy)方策
常に最も選択確率が高い(グリーディ)行動を選択する方策。
・ε-グリーディ(ε-greedy)方策
確率ε(0≦ε≦1)で行動をランダムに選択し，１－εでグリーディな行動を選
6
択する方策。つまり
ε
A(s )
で非グリーディ行動を選択し， 1 − ε +
ε
A( s )
でグリ
ーディな行動を選択することになる。これはε＞0 な値であれば，全ての状態
群と行動群に対して π ( s, a ) ≥
ε
A( s )
である方策として定義される。
(2)報酬関数(reward function)
報酬は強化学習問題における目標を意味する。報酬関数は最終的に得られる報酬の総
和を定義しており，収益と呼ぶ。強化学習エージェントの目的はこの収益を最大化する
ことにある。ある時間ステップ t 以降に獲得した報酬の系列を rt +1 , rt + 2 , rt + 3 , ･･･と表すな
ら収益 Rt は
Rt = rt +1 + rt + 2 + rt + 3･･･ + rT
(2.1)
となる。ここで，T は最終時間ステップ，つまり目標達成時刻を意味する。この時の状
態を終端状態といい，学習の開始から終端状態までをエピソードと呼び，エピソードを
伴うタスクはエピソード的タスクと呼ばれる。一方，ロボットアームの制御のように一
定の状態を維持し続けることを目的としたタスクのように終端状態が存在しないタス
クや，学習を行うのに長いライフスパンを必要とするロボットへの応用などは連続タス
クと呼ぶ。連続タスクにおいて式(2.1)に従い収益を計算した場合，問題が起こる。連続
タスクにおいて最終時間ステップは T =∞で収益を最大化することを考えた場合，容易
に無限の値をとりうるからである(例えば，エージェントが目的にかなった状態を維持
している場合は各時間ステップにおいて＋１の報酬を与えるとした場合， Rt = ∞ とな
りうる)。そこで，割引という概念を必要とする。
∞
Rt = rt +1 + γ rt + 2 + γ rt + 3 + ・・・＝ ∑ γ k rt + k +1
2
k =0
(2.2)
式(2.2)は割引の概念を適用した減衰収益である。ここで γ は割引率(discount rate)と呼
ばれるパラメータで 0 ≤ γ ≤ 1 である。連続タスクにおいてはこの割引率 γ によって減衰
した収益を最大化するような行動を学習する。
(3)価値関数(value function)
ほとんどの強化学習アルゴリズムは価値関数に基づく評価を行っている。この価値関
数は状態（または状態行動対）の関数で，エージェントがある状態にいることがどれだ
け良いか（または，ある状態において，ある行動をとることがどれだけ良いか）を評価
する。ここで「どれだけ良いか」という概念は将来における収益に関して定義される。
エージェントが将来にわたり受け取ることができる報酬は，エージェントがどのような
7
行動をとるかに依存する。したがって，価値関数は特定の方策に関して定義される。方
策πのもとでの状態 s の価値を状態価値関数(state-value function)と呼び，状態 s で方
策πに従った時の期待収益を次の式で定義する。
⎧∞
⎫
V π ( s ) = Eπ {Rt | st = s} = Eπ ⎨∑ γ k rt + k +1 | st = s ⎬
⎩ k =0
⎭
(2.3)
同様に方策πのもとで状態 s に対して行動 a をとることの価値を行動価値関数
(action-value function)と呼び，状態 s において行動 a をとり，その後に方策πに従った
時の期待収益を次の式で定義する。
⎧∞
⎫
Q π ( s, a) = Eπ {Rt | st = s, at = a} = Eπ ⎨∑ γ k rt + k +1 | st = s, at = a ⎬
⎩ k =0
⎭
(2.4)
(4)環境のモデル
環境のモデルとは，環境の挙動を模倣するものである。状態と行動が与えられた時，
モデルは結果として生じる次の状態とその時の報酬を予測する。モデルはプランニング
(実際に起こる前の可能な将来の状況を考慮して動作を決定する方法)のために用いら
れる。
8
2.4.2
強化学習の枠組み
強化学習の枠組みを図 2.2 に示す。
エージェント(学習主体)
状態観測x t
行動a t
報酬rt
方策π
環境(制御対象)
図 2.2
強化学習の枠組み
強化学習の大きな特徴は正しい行動を誰かから教えられるのではなく，実際にエージ
ェントが行動をとり，その行動を評価することで学習を行う点である。それは次のよう
なプロセスで行われる。
まず，エージェントは制御対象である環境の時刻 t における状態 x t を知覚する。そし
て方策π(行動を決めるルール)に従い行動 a t を実行する。行動 a t を実行したことにより
報酬 rt を獲得する。獲得した報酬から価値関数を生成し，その値を用いて方策πの評価
と改善を行う。つまり強化学習とは方策の評価・改善を行うことで報酬関数を最大化す
るような方策πを構築する手法である。
2.5
強化学習の学習アルゴリズム
ここで，本研究で使用する強化学習の学習アルゴリズムについて説明する。
2.5.1
2.5.1.1
Q-Learning
Q-Learning の学習アルゴリズム
Q-Learning（Watkins 92[5]）は強化学習の代表的アルゴリズムである。学習の各ス
テップにおいて Q 値と呼ばれる行動価値関数 Q( s, a ) を更新していくことで学習を行う。
式(2.5)に更新式を示す。
9
Q ( s t , a t ) ← Q ( s t , a t ) + α [ rt +1 + γ
max Q ( s
t +1
, a ) − Q ( s t , a t ) ] (2.5)
a
ここで，γは割引率(0≦γ≦1)，αは学習率(0＜α≦1)である。時間ステップ t におけ
る状態 s t において行動 a t をとった時に遷移した次状態 s t +1 において最適な行動 at +1 を
選択した時に得られる行動価値 Q ( st +1 , at +1 ) を割引率γで割り引いた値とその時に得ら
れた報酬 rt +1 の和に，現在の Q 値 Q ( s, a ) をαの割合で近づけるように更新を行う。こ
うすることにより，最適な行動を選択し続けた時の収益に近づけることができる。図
2.3 に Q-Learning のアルゴリズムを示す。
（１）． Q ( s, a )を任意に初期化
（２）．各エピソード に対して以下を繰り返 す：
（ a）．sを初期化
（ b）．エピソードの各ス テップに対して以下を 繰り返す：
（ⅰ）． Qから導かれる方策を用 いて状態 sでとる行動 aを選択する
（ⅱ）． 行動 aをとり，報酬 rと次状態 s ' を観測する
Q ( s, a ) ← Q ( s, a ) + α [ r + γ max a ' Q ( s ' , a ' ) − Q ( s, a )]
s ← s '
(c)．sが終端状態であれば繰 り返し終了
図 2.3 Q-Learning のアルゴリズム
2.5.1.2
適格度トレースと Q(λ)
Q-Learning には適格度トレースという手法を適用した Q(λ)と呼ばれる学習手法が
ある。適格度トレースは時間的信用割当て（temporal credit assignment）の基本的メ
カニズムの一つである。ある状態 s において行動 a をとることの適格度を示す。現在の
*
状態と行動に対応する適格度トレース e( s, a) を 1 だけ増加させ，a = arg max a Q ( s ' , a )
となる行動 a を選択した時に過去に経由した全ての状態行動対 ( s, a) に対しては割引率
γとトレース減衰パラメータλの値で減衰させた γλ e ( s , a ) の値を加えていく。図 2.4
に Q(λ)のアルゴリズムを示す。
10
（１）． Q ( s, a )を任意に初期化し，全 てのs , aに対して e( s , a ) = 0とする。
（２）．各エピソード に対して以下を繰り返 す：
(a )．s , aを初期化
（ b）．エピソードの各ス テップに対して以下を 繰り返し：
（ⅰ） ．行動 aをとり， r , s 'を観測する
（ⅱ） ．Qから導かれる方策を用 いてs ' でとる行動 a 'を選択する
a * ← arg max a Q ( s ' , a )
(a ' の場合と最大値が等し いならば， a * ← a ' )
δ ← r + γQ ( s ' , a * ) − Q ( s, a )
e( s , a ) ← e( s, a ) + 1
すべての s, aについて：
Q ( s, a ) ← Q ( s, a ) + αδe( s, a )
もし a ' = a *ならば， e( s, a ) ← γλe( s, a )
それ以外 e( s, a ) ← 0
s ← s ' ; a ← a '
（ c）． sが終端状態であれば繰 り返し終了
図 2.4
Q(λ)のアルゴリズム
11
2.5.2
2.5.2.1
Profit Sharing
Profit Sharing の学習アルゴリズム
Profit Sharing（Grefenstette 88[6]）は遺伝的アルゴリズム（genetic algorithm，
GA）を併用するクラシファイアシステム（条件部と行動部を持つルールの集合からな
るシステム）での信用割り当て（credit assignment）の方法として提唱された。現在
では GA だけでなく強化学習の枠組みにおいても利用され，マルチエージェント環境に
おいても応用が期待されている。Profit Sharing は，Q-Learning のようにエピソード
の各ステップにおいて逐次更新を行うといった学習アルゴリズム(環境同定型)ではな
く，報酬を得た時にそれまでのルール系列を一括で強化する学習アルゴリズム(経験強
化型)である。ある感覚入力（状態）x にたいして実行可能な行動 a の組をルール ri とし，
if　x　then　a というルールを xa と書くものとする。すべてのルール ri には重み S ri が
存在し，エージェントは各ルールの重み値に従って確率的な行動を選択し，実行する。
そして各エピソードにおいて報酬を得るまでのルール系列を記憶しておき，報酬を得た
時点でそれまで記憶しておいたルール系列を強化する。
S ri = S ri + f i , i = 0 ,1, 2 ,..., W − 1
(2.6)
式(2.6)は Profit Sharing の強化式である。ここで S ri はルール系列上の i 番目のルールの
重み， f i は強化関数と呼ばれ，報酬獲得時点から i ステップ前の強化値を意味する。また W
は報酬獲得までのステップ数である。
2.5.2.2
合理ルールと非合理ルール
あるエピソード上で，同一の感覚入力（状態）に対して異なるルールが選択されてい
る時，その間のルール系列を迂回系列（detour）という。
エピソード
迂回系列
x
y
z
x
y
行動
a
b
b
a
a
図 2.5
エピソードと迂回系列
12
報酬
状態
図 2.5 では状態 y において a という行動をとるルール ya を適用すれば，報酬を得られ
るが，一度目に状態 y を知覚した時に行動 b をとるルール yb を適用しているため，報
酬を得られるまでのエピソード長が長くなってしまっている。この迂回系列上のルール
系列を非合理ルールといい，それ以外のルール系列を合理ルールという。Profit Sharing
ではこの非合理ルールの強化を抑制しながら合理ルールの強化を行う必要がある。これ
を満たす条件を式(2.7)に示す。
W
L∑ f j < f j −1 , ∀i = 1,2,...,W .
(2.7)
j =0
ここで， W はエピソードの最大長， L は同一感覚入力下に存在する合理ルールの最大
個数である。これを満たす簡単な強化関数として，式(2.8)のような等比減少関数が考え
られる。
fi =
1
f i −1 , i = 1,2,..., W − 1.
M
(2.8)
ここで，M (但し，M ≥ L + 1) を報酬割引率という。式(2.8)はシングルエージェント系に
おける合理性定理を満たす（宮崎ら 1994[7]）。合理性定理とは，非合理ルールの強化
を抑制しつつ合理ルールの強化を行うための条件を意味する。マルチエージェント系で
は直接報酬を受けるエージェントは式(2.8)にしたがった強化を行い，その他のエージェ
ントは f 0 = μR　( μ ≥ 0) として強化を行う。図 2.6 に式(2.8)を用いて非合理ルールを抑
制しながら合理ルールの強化を行っているモデル図を，図 2.7 に Profit Sharing の学習
アルゴリズムを示す。
13
f
f
f
f
3
0
強化値
f
1
2
4
時間
エピソード（長さW）
迂回系列
z
x
x a
y
ルール
xa
yb
zb
xa
ya
ルール
の重み
F ( xa )
F ( yb)
F (zb )
F ( xa )
F ( ya )
状態
行動
図 2.6
b
b
a
非合理ルールを抑制した強化モデル
14
y a
（１）．　S ri を任意に初期化
（２）．　各エピソードに対して以下を繰り返し
(a)．ri , Wを初期化
(b)．エピソードの各ステップに対して以下を繰 り返し
（ⅰ ）．S ri から導かれる方策を用いて状態xでの行動aを選択する
（ⅱ ）．行動aをとり，次状態x'と報酬Rを観測
（ⅲ ）．全てのiに対して，i ← i + 1としてr0 = xaを保存
（ⅳ ）．R ≠ 0の場合，f 0 = Rとして以下の処理を行う。
S ri = S ri + f i , i = 0,1,...,W − 1.
但し， f i =
1
f i −1 , i = 1,2,...,W − 1.とする
M
（ⅴ ）．x ← x' , W ← W + 1;
（c）．xが終端状態ならば繰り返しを終了
図 2.7
Profit Sharing の学習アルゴリズム
15
３．過去の研究例
3.1
過去の研究例
マルチエージェントと強化学習に関する研究として多くの研究例がある。荒井ら
(1998)[8]では，Q-Learning と Profit Sharing の 2 種類の学習アルゴリズムを取り上げ，
追跡問題への適用を通じて Profit Sharing の優位性を主張している。また宮崎ら
(1999)[9]では，Profit Sharing の報酬配分について理論的考察を行い，間接報酬 μ の値
が μ ≤ 0.3 の範囲であれば常に最適方策が得られることを証明している。また実ロボッ
トへの応用例としてロボットの歩行動作の獲得を試みた木村ら(1999)[10]や RoboCup
Soccor の Keepaway タスクの制御における報酬設計の実験を行った荒井ら(2006)[11]
などがあり，実機における 実験でも強化学習の有用性を示している。
この問題については高知大学理学部本田研究室でもいくつかの先行研究がおこなわ
れている。黄(2004)[12]はシングルエージェント問題で Q -Leaning による強化学習を
行い，その学習結果から決定木を用いて汎用性を持ったエージェントの構成を試みた。
櫻井(2006)[13]は，さらにこの検討をマルチエージェントの追跡問題に拡張した。また，
内海(2007)[14]は，追跡問題に Profit Sharing を使用した際のエージェント間の協調動
作の獲得性を定性的に確認したが，定量的な議論までは行っておらず，Q-Learning と
の比較検討はなされていなかった。
3.2
本研究の目的
本研究ではマルチエージェント問題において強化学習により学習を行ったエージェ
ントが，どれだけ協調的な動作を学習できているかという点に着目し，追跡問題を例と
して Q-Learning と Profit Sharing を用いて強化学習を行う。その学習結果から捕獲直
前の状態において各エージェントが獲得した行動の組み合わせを抜き出し，それを用い
て協調性の評価を行う。また Q-Learning のパラメータ設定を 3 種類用意し，Profit
Sharing を含めた計 4 種類の学習アルゴリズムでそれぞれ実験を行い，アルゴリズムの
違いによる動作の獲得傾向の違いについても検証を行う。
16
４．マルチエージェント強化学習によるエージェントの協調性の検証
4.1
問題設定
本研究ではマルチエージェント問題の１つである追跡問題を扱う。本項では追跡問題
の設定と使用するアルゴリズムのパラメータ設定について説明する。
4.1.1
追跡問題
追跡問題とは，複数のハンター(hunter)が獲物(target)を追跡捕獲するという問題で
あり，マルチエージェント系でベンチマークをとるための環境として多くの研究で用い
られている。図 4.1 にその模式図を示す。追跡問題ではグリッド(格子)状のマップの上
にハンターと獲物を置きハンターが獲物を取り囲めば捕獲成功(目標達成)となる。本研
究では，15×15 マスのマップ上に 2 つのハンターと 1 つの獲物をランダムに配置した
状態で学習を行う。各端側は壁とみなし，各ハンターが獲物に対して辺で隣接したら捕
獲成功(目標達成)とする。ハンターと獲物はそれぞれ｛上，下，左，右，｝に１マス移
動，または現在存在しているセルに留まる停滞の計 5 種類の行動が可能である。
まず獲物がランダムに行動を行い，両ハンターがその状態を知覚し，ハンター1，ハ
ンター2 の順に行動を行う。これを１ステップとし，ハンターが目標を達成するか 1000
ステップ繰り返した時にそのエピソードを終了とする。
ハンターには視野を設定しており，獲物ともう一方のハンターの位置を｛上，右上，
右，右下，下，左下，左，左上｝の周囲 8 方向と視野外の計 9 通りの状態を知覚できる
ものとする。今回の実験では，視野の範囲は対獲物に VX＝VY＝15(ハンター周囲 7 マ
スの範囲)，対ハンターに VX＝VY＝3(ハンターの周囲 1 マスの範囲)に設定した。各ハ
ンターは獲物の位置ともう一方のハンターの位置の組み合わせ 81 通りで状態を知覚し，
各状態に対する適切な行動を学習していく。また，Q-Learning における Q 値と Profit
Sharing におけるルールの重みはハンターごとに設定するものとする。
なお，このように視野と行動順を固定し，協力相手のエージェントに対する視野を限
定することで，協調動作が有効な状況を認識し，協調動作が取得され，各ハンターが役
割分担を持つことが期待できる。
図 4.2 はハンターの視野を示したものである。緑のマスがハンター1 と 2，赤いマス
が獲物を表している。水色のマスがハンター1 の獲物に対する視野，ピンクのマスがハ
ンター2 の獲物に対する視野を意味し，紫のマスはお互いの視野が重なっている部分を
意味する。オレンジのマスはもう一方のハンターに対する視野を意味している。表 4.3
に追跡問題の設定をまとめておく。
17
1
2
図 4.1
追跡問題の環境と捕獲状態の例。緑のマスがハンター，赤のマスが獲物を表し
ている。
2
VX
VY
1
図 4.2
ハンターの視野。緑のマスがそれぞれハンター１，ハンター２，赤いマスが獲
物を意味しており，水色のマスがハンター１の視野，ピンクのマスがハンター2 の視野
となる VX は横方向の視野，VY は縦方向の視野の範囲を意味している。マップ中央の
紫のマスはハンター１とハンター2 の視野が重なっている部分になる。
18
表 4.3
追跡問題の問題設定
項目
4.1.2
設定値
マップのサイズ
15×15 マス
ハンターの数
2
獲物の数
1
環境の初期状態
各ハンターと獲物をランダムに配置
目標状態
各ハンターが獲物に対して辺で隣接
ハンターの行動
｛上，下，左，右，停滞｝の 5 種類
獲物の行動
｛上，下，左，右，停滞｝の 5 種類
ハンターに対する視野
VX＝VY＝15(自分の周囲 7 マスの範囲)
獲物に対する視野
VX＝VY＝3(自分の周囲 1 マスの範囲)
最大ステップ数
1000
使用する学習アルゴリズムとパラメータ設定
本研究では 2.5 で説明した Q-Learning と Profit Sharing の 2 種類を学習アルゴリズ
ムとして使用する。これは，学習アルゴリズムの違いによって協調行動の獲得傾向に違
いが出るかを見るためである。本項では Q-Learning と Profit Sharing のパラメータ設
定について説明する。
4.1.2.1
Q-Learning の設定
表 4.4 に Q-learning のパラメータ設定値を示す。Q-Learning は適格度トレースλの
値を 0≦λ≦1 の範囲で自由に設定でき，その値によって学習の仕方を制御できるため
λ=0，0.5，0.9 の 3 種類の値を用いることにする。方策はε-greedy 方策を使用する。
ε-greedy 方策とは，確率ε(0≦ε≦1)で探索的(ランダム)な行動をとり，それ以外の場
合は最適な行動をとるというものである。εの値はε=0，0.2 の 2 種類を用いる。報酬
は捕獲時に 0，それ以外の場合は 1 ステップ毎に－1 の報酬を与える。これは，より短
いステップ数で捕獲することを学習させるためである。エピソード数は 6000 とし，こ
れを 1 試行として各設定においてそれぞれ 100 回試行を行った。
19
表 4.4
Q-Learning の設定
パラメータ
設定値
適格度トレースλ
λ=0，0.5，0.9
方策
ε-greedy 方策(ε=0，0.2)
捕獲時に 0
報酬
4.1.2.2
それ以外の場合は 1 ステップ毎に－1
エピソード数
6000
試行回数
100
Profit Sharing の設定
表 4.5 に Profit Sharing のパラメータの設定値を示す。Profit Sharing は目標達成時
に与える報酬を R = 100 として宮崎ら(1994)[7]により証明されている合理性定理に従
って与える。間接報酬 μR は μ = 1.0 に設定した。本実験ではハンターの数が 2 でどちら
のハンターも目標達成に直接貢献するからである。エピソード数は 3000 とし，これを
1 試行とし 100 回試行を行った。
表 4.5
Profit Sharing のパラメータ設定値
パラメータ
間接報酬
R =100
μR = 100, μ = 1.0
強化式
fi =
報酬
4.2
設定値
エピソード数
3000
試行回数
100
1
f i −1 , i = 1,2,...,W − 1.　M = 5
M
アルゴリズムとパラメータ設定の違いによる学習効果の比較
本項では学習効果の違いの比較を行う。具体的には学習が収束するまでの時間(エピ
ソード数)と，学習精度(捕獲までのステップ数)について比較を行う。
4.2.1
評価の方法
学習効果の評価の方法について説明する。学習が収束するまでの時間は各学習ケース
(100 回分)の各エピソードでの捕獲までのステップ数の平均値を算出し，その値の 50
区間の移動平均から評価を行う。捕獲までのステップ数は Q-Learning のε=0.2 の場合
が，確率 0.2 でランダムな行動をとってしまい，正確な捕獲ステップ数がわからないた
め，学習結果をε=0 の状態で再実行した時の結果を用いる。
20
4.2.2
実験結果と考察
まず，図 4.6 に Q-learning，ε=0 の学習結果を示す。ここでは，縦軸が各エピソー
ドの報酬の平均，横軸がエピソード数を表している。 Q-Learning は捕獲成功時以外の
場合は 1 ステップ毎に－1 の報酬を与えているため，報酬の絶対値が捕獲までのステッ
プ数を意味する。ε=0 の場合は学習の初期段階(1~500 エピソード)ではλ=0.9 が最も
良い学習結果を出しており Q(0)が最も学習の立ち上がりが遅い。最終的な学習結果は
Q(0.5)が最も良い学習結果を出しており，Q(0.9)は最も悪い結果に終わっている。学習
の収束は Q(0)が 4000 エピソード，Q(0.5)が 2750 エピソード，Q(0.9)が 1000 エピソー
ドで Q(0.9)が最も早く収束する。
λの値の違いによる比較（ε=0.0）
0
-100
-200
報酬の平均(100回)
-300
-400
-500
Q(0)
-600
Q(0.5)
-700
Q(0.9)
-800
50 区間移動平均 (Q(0))
50 区間移動平均 (Q(0.5))
-900
50 区間移動平均 (Q(0.9))
-1000
1
501
1001
1501
2001
2501
3001
3501
4001
4501
5001
5501
エピソード数
図 4.6
Q-Learning(ε=0)の学習結果
次に，図 4.7 に Q-Learning でε=0.2 としたときの学習結果を示す。ε=0.2 の場合
も，ε=0 の時と同様に学習の初期段階では Q(0.9)が最も良い学習結果を出しているが，
最終的には Q(0.5)が最も良い結果を出し，Q(0)と Q(0.9)がそれに劣る結果に終わって
いる。
なお，図 4.7 は Q-Learning，ε=0.2 で学習を行った結果で，確率 0.2 でランダムな
行動をとるように設定したため，正確な学習精度ではない。そこで，図 4.8 には
Q-Learning，ε=0.2 の学習結果を使ってε=0 の状態で試行した結果を示す。図 4.7 と
図 4.8 を比べると同じアルゴリズムでも捕獲ステップ数に違いが見られる。Q(0.5)と
Q(0.9)は，ε=0.2 で試行した場合よりも短いステップ数で捕獲していることがわかる。
逆に Q(0)はε=0.2 で試行した場合より捕獲ステップ数が多くなっている。これは 0.2
21
の確率でとるランダムな行動が Q(0.5)と Q(0.9)に対しては悪い影響を与え，Q(0)に対
しては良い影響を与えていたためであると考えられる。
このことから Q-Learning では，
ε=0.2，λ＝0.5 に設定したときに最も良い結果が得られることが判った。
λの値の違いによる比較(ε=0.2)
0
-100
-200
報酬の平均(100回)
-300
-400
-500
Q(0)
-600
Q(0.5)
-700
Q(0.9)
-800
50 区間移動平均 (Q(0))
50 区間移動平均 (Q(0.5))
-900
50 区間移動平均 (Q(0.9))
-1000
1
501
1001
1501
2001
2501
3001
3501
4001
4501
5001
5501
エピソード数
図 4.7
Q-Learning，ε=0.2 の学習結果
Q-Learning(ε=0.2)の学習結果をを(ε=0)の状態で試行した結果
0
-100
-200
報酬の平均(100回)
-300
-400
-500
-600
Q(0)
-700
Q(0.5)
Q(0.9)
-800
50 区間移動平均 (Q(0))
50 区間移動平均 (Q(0.5))
-900
50 区間移動平均 (Q(0.9))
-1000
1
501
1001
1501
2001
2501
3001
3501
4001
4501
5001
5501
エピソード数
図 4.8
Q-Learning，ε=0.2 の学習結果をε=0 の状態で試行した結果
22
次に，図 4.9 に Profit Sharing の学習結果を示す。Profit Sharing は Q-Learning
に比べると学習の収束が非常に早い。また学習収束後は Q-Learning のように学習結果
にばらつきがなく，ほぼ一定の学習結果を出している。また，学習精度も Q-Learnig
の中で最も良い結果を出した Q(0.5)，ε=0.2 の結果と同等の精度を持っている。以降
では，Q-Learning，ε=0.2 と Profit Sharing について獲得した行動の協調性について
評価を行うことにする。
Profit Sharingの学習結果
0
100
捕獲ステップ数の平均
200
300
400
500
600
700
Profit Sharing
800
50 区間移動平均 (Profit Sharing)
900
1000
1
501
1001
図 4.9
4.3
1501
エピソード数
2001
2501
Profit Sharing の学習結果
獲得した行動の協調性の検証
本項では Q-Learning，ε=0.2 と Profit Sharing による学習で得られた行動の協調性
について検証する。特に協調性が必要とされる状態において各ハンターが獲得した行動
をダイアグラムにして，その獲得回数や獲得傾向に注目し評価を行う。まず，図 4.10
に実際に見られた協調行動の例を示す。
23
図 4.10
捕獲直前 4 ステップのエージェントの動き。左上から右下にかけて時系列に
従い表示している。青マスの 0，1 はそれぞれハンター1，ハンター2 を赤マスが獲物を
意味している。水色のマスはハンターの視野をあらわしている。上記の図ではハンター
1 とハンター2 が同時に移動しているが，プログラム上ではハンター1 が行動を選択し
てからハンター2 が行動を選択するようになっている。2 ステップ目から 3 ステップ目
にかけてハンター1 がハンター2 に場所を譲る動作が見られる。
24
4.3.1
評価の方法
協調性の評価の方法について説明する。ハンターの協調性について検証するため特に
協調性を必要とされる状態について各ハンターが獲得した行動の組み合わせに着目す
る。検証の対象は獲物を端側にして各ハンターと獲物が一直線にならんだ状態とする。
本研究ではハンターのターゲットに対する視野を VX=VY=15(自分の周囲 7 マスの範
囲)に設定したため，1 つの状態から想定されるハンターと獲物の位置関係が複数ある。
大別するとハンターと獲物が隣接している場合とそうでない場合で必要とする協調動
作が異なるため，各状態につきハンターと獲物が隣接している位置関係とそうでない位
置関係に分けて考えることにする。図 4.11 に対象とする状態と位置関係の分類の仕方
を示す。
2
2
1
2
1
1
パターン1
2
1
2
1
2
1
パターン2
図 4.11 検証の対象とする状態とその分類の仕方。獲物は赤いマスのいずれか 1 つに
存在する。
25
ここで，各パターンにおける協調動作の定義をしておく。図 4.12 にパターン 1 に対
して考えられる協調動作の例を示す。例えばパターン 1 のハンターと獲物が隣接してい
る場合では，ハンター1 が上か下に移動し，ハンター2 が右に移動する行動の組み合わ
せが最も協調的な動作といえる。これを「譲り合い」と定義する。他にも次の行動で獲
物が左に動くことを期待してハンター1 が上か下に移動し，ハンター2 がその場に停滞
する行動や上下で挟み込もうとする行動も協調的であるといえる。これをそれぞれ「待
ち伏せ」，「挟み撃ち」と定義する。ハンター1 と獲物が隣接していない位置関係では，
各ハンターが右に移動するのが最も協調的な動作である。これを「追従」と定義する。
「譲り合い」
「待ち伏せ」
「挟み撃ち」
「追従」の 4 つの動作を協調的な動作とする。表
4.13 にパターン 1 における協調動作の組を列挙して示す。
1
1
2
2
1
2
2
1
譲り合い
待ち伏せ
1
2
1
2
2
1
1
2
待ち伏せ
図 4.12
追従
パターン 1 における協調動作の具体例
表 4.13
パターン 1 における協調動作
協調動作
各ハンターの行動の組み合わせ
譲り合い
ハンター1 が上または下に移動，ハンター2 が右に移動
待ち伏せ
ハンター1 が上または下に移動，ハンター2 が停滞
挟み撃ち
追従
ハンター1 が上に移動，ハンター2 が下に移動
またはハンター1 が下に移動，ハンター2 が上に移動
ハンター1，ハンター2 が共に右に移動
26
なお，パターン 2 についても同様の定義が可能である。図 4.14 にパターン２の配置
に対して考えられる協調動作の例を示し，表 4.15 にパターン 2 における具体的な協調
動作の組を列挙して示す。
2
2
1
2
1
1
譲り合い
2
2
1
待ち伏せ
2
1
2
1
1
2
1
待ち伏せ
図 4.14
挟み撃ち
パターン 2 の状態における協調動作の具体例
表 4.15
協調動作
各ハンターの行動の組み合わせ
譲り合い
ハンター1 が右または左に移動，ハンター2 が下に移動
待ち伏せ
ハンター1 が右または左に移動，ハンター2 が停滞
挟み撃ち
追従
4.3.2
パターン 2 における協調動作
ハンター1 が右に移動，ハンター2 が左に移動
またはハンター1 が左に移動，ハンター2 が右に移動
ハンター1，ハンター2 が共に下に移動
検証結果
各状態におけるハンター1 とハンター2 が獲得した行動の組み合わせの獲得割合をダ
イアグラムにしたものと獲得した協調行動を種類別に棒グラフ化したものを示す。
図 4.16 と図 4.17 はそれぞれパターン 1 とパターン 2 の状態において各ハンターが獲
得した行動の組み合わせの獲得回数を学習アルゴリズム別に表したダイアグラムであ
る。h1，h2 はそれぞれハンター1，ハンター2 を指す。
｛U，D，L，R，S｝はそれぞれ
｛上，下，左，右，停滞｝を意味する。色がついている部分はそれぞれ協調動作に該当
し，赤：譲り合い，黄色：待ち伏せ，緑：挟み撃ち，水色：追従を意味する。青線で囲
27
まれている部分はハンターと獲物が隣接している時にとることができない行動の組み
合わせになっている。
h1 の 行 動
h1 の 行 動
Q(0)
h2
の
行
動
Q(0.5)
U
D
U
1
D
L
R
S
2
0
2
2
3
0
2
L
2
3
8
5
R
22 20
0
S
7
8
8
h2
の
行
動
U
D
U
0
D
R
S
1
0
5
0
3
0
0
L
1
2
1
0
R
31 30
1
S
2
5
5
h1 の 行 動
図 4.16
5
3
h1 の 行 動
Q(0.9)
h2
の
行
動
L
PS
U
D
U
7
D
R
S
7
5
3
7
2
1
4
L
6
8
4
0
R
14 13
2
S
3
6
6
L
h2
の
行
動
2
U
D
U
2
D
R
S
3
1
0
5
3
1
0
L
0
3
0
0
R
38 34
0
S
2
1
7
L
2
パターン 1 の状態において各ハンターが獲得した行動の組み合わせの獲得割
合(％)。左上から右下に向かって Q(0)，Q(0.5)，Q(0.9)，Profit Sharing の結果となっ
ている。赤マスは譲り合い，水色のマスは追従，緑のマスは待ち伏せ，黄色のマスは挟
み撃ちの動作の獲得割合を示している。青のラインで囲まれたマスは，捕獲直前(ハン
ター1 と獲物が隣接する位置関係)においてとることのできない行動の組み合わせを意
味しており，×がついているマスはこの状態で常にとることができない行動の組み合わ
せを意味している。
28
h1 の 行 動
h1 の 行 動
Q(0)
Q(0.5)
U
h2
の
行
動
D
L
R
S
U
12
5
4
6
D
1
20 19
L
0
3
3
0
R
0
0
0
1
S
11
5
7
3
U
h2
の
行
動
D
L
R
S
U
2
5
0
4
D
0
32 30
L
1
1
1
3
R
0
4
2
3
S
2
4
3
3
h1 の 行 動
h1 の 行 動
Q(0.9)
PS
U
h2
の
行
動
図 4.17
D
L
R
S
U
0
5
7
3
D
3
18 17
L
3
4
5
2
R
4
4
4
3
S
3
7
7
1
U
h2
の
行
動
D
L
R
S
U
1
3
2
0
D
4
30 34
L
2
0
4
1
R
3
4
0
0
S
0
6
6
0
パターン 2 の状態において各ハンターが獲得した行動の組み合わせ。図の見
方は図 4.16 と同様。
図 4.18 にパターン 1 の状態に対し各ハンターが獲得した行動の組み合わせ(行動対)
の獲得率を，図 4.19 にパターン 2 の状態に対し各ハンターが獲得した行動の組み合わ
せの獲得率を示す。実験結果より，どのアルゴリズムも 50％以上の割合で協調行動を
獲得していることが判る。Q-Learning の獲得した協調動作の内訳を見てやると Q(0.5)
は譲り合いの動作を獲得している割合がパターン 1 の状態では 61％，パターン 2 の状
態では 62％と高い。Q(0)と Q(0.9)は譲り合いの動作を獲得している割合が Q(0.5)に比
べ低いが，挟み撃ちや待ち伏せといった動作を獲得している割合が Q(0.5)よりも高い。
Profit Sharing は協調動作の獲得率がパターン 1，パターン 2 共に最も高く 90％近い獲
得率である。譲り合いの動作を Q (0.5)と同程度の割合で獲得しており，待ち伏せや挟
29
み撃ちの動作を獲得率も Q(0)や Q(0.9)並みに高い。ハンターと獲物が隣接していない
位置関係に遭遇することの方が確率的に高いにも関わらず，追従の動作の獲得率は極端
に低い。これは，より捕獲に近い状態であるハンターと獲物が隣接した状態での行動が，
より大きな報酬を獲得しているため，その影響を強く受けたものと考えられる。
30
各行動の獲得率
100
90
挟み撃ち
各行動対の獲得率(%)
80
70
待ち伏せ
60
50
追従
40
30
譲り合い
20
10
0
Q(0)
図 4.18
Q(0.5)
Q(0.9)
学習アルゴリズム
Profit Sharing
パターン 1 の状態で各アルゴリズムが獲得した協調行動の獲得率
各行動の獲得率
100
90
挟み撃ち
各行動対の獲得率(%)
80
70
待ち伏せ
60
50
追従
40
30
譲り合い
20
10
0
Q(0)
図 4.19
Q(0.5)
Q(0.9)
学習アルゴリズム
Profit Sharing
パターン 2 の状態で各アルゴリズムが獲得した協調行動の獲得率
31
表 4.20 に各学習アルゴリズムについて協調動作獲得率と捕獲までの平均ステップ数
の関係をまとめておく。捕獲までの平均ステップ数は Profit Sharing とそれに次ぐ協調
動作の獲得率の Q(0.5)がそれぞれ 46、47 ステップと最も短く、次に Q(0.9)が 72 ステ
ップ、そして、Q(0)においては平均 377 ステップと、他の 3 つのアルゴリズムに比べ
て極端に性能が劣化していることがわかる。この順番は、協調動作の獲得率をほぼ反映
しているが、特に Q(0)の性能の低下は、協調動作の獲得率の低下の程度をはるかに上
回っている。このことから捕獲直前における協調動作の獲得率の上昇は大まかには性能
の向上に影響しているが、それ以外の効果も影響（特に Q(0)の場合）していることが
考えられる。
次節では，こうした結果を“過去にとった行動への報酬の伝播”という観点で考察し
ていく。
表 4.20
各学習アルゴリズムにおける協調性獲得率と捕獲までの平均ステップ数
学習アルゴリズム
パターン 1 における パターン 2 における 捕 獲 ま で の 平 均 ス
協調動作獲得率(%)
協調動作獲得率(%)
Q(0)
61
50
377
Q(0.5)
70
74
46
Q(0.9)
51
61
72
Profit Sharing
89
98
47
32
テップ数
4.3.3
考察
Q-Learning では獲得した報酬値を，パラメータλと割引率γを用いてγλで減衰
させながら過去に経験した全ての状態行動価値関数に報酬を伝播することで強化の制
御ができ，Profit Sharing は報酬を獲得した時に式(2.8)の等比減少関数に従った強化を
行う。
図 4.21 に各学習アルゴリズムの報酬の伝播の仕方のモデル図を示す。図 4.21 から判
るように Q(0)は過去に全く報酬を伝播せず，Q(0.9)はより遠い過去まで報酬を伝播する
ことがわかる。このことから，λ=0 の時は直前の行動価値関数にしか報酬を与えない
ため，近視眼的な学習を行ってしまい，捕獲直前の強調動作は獲得しても，そこに至る
までの過程を学習できていないため図 4.9 のような結果になったと考えられる。λ=0.9
の時は過去に伝播する報酬の値が大きく，遠くまで伝播したため，不適切な行動まで強
化しすぎてしまい Q(0.5)より学習精度が低くなってしまったと考えられる。また，
Q(0.5)と Profit Sharing の協調動作の獲得の傾向が似ているのは報酬の過去への伝播
の仕方が似ているためだと考えられる。
1.2
1
報酬値
0.8
Profit
Sharing
0.6
Q(0.9)
0.4
Q(0.5)
0.2
Q(0)
0
T-4
T-3
T-2
T-1
T
時刻
図 4.21 各学習アルゴリズムの報酬の伝播の仕方のモデル図。時刻 T で捕獲し，得ら
れた報酬値を 1 とした場合の過去への報酬伝播の仕方を表している。
以上のことから協調的動作を学習させるには Profit Sharing が最も適切な学習アル
ゴリズムであり，Q-Learning はパラメータの値を調整することで学習のさせ方を変え
られるという柔軟な性質を持っていることがわかった。また，捕獲直前の状態における
協調動作を学習していても，それがシステム全体の処理(本研究においてはハンターが
33
獲物を捕獲すること)に反映されていない場合があることもわかった。今回，
Q-Learning においてλ=0.5 に設定した時に最も良い結果を得ることができたのは，獲
物の行動がランダムであったため，長期にわたる行動戦略が有効でなかったためと考え
られる。そのため獲物が一定のルールに従い行動するような環境やチェスなどのように
長期的な戦略を必要とする問題においては異なる結果が得られることも想定できる。
4.3.4
今後の課題
以上よりマルチエージェント系の問題である追跡問題において強化学習を適用する
ことで，エージェントが協調動作を獲得できることがわかったが，ここでは残された課
題にふれておく。
本研究の追跡問題の設定では，マップの各端側は壁とみなし，獲物の行動はランダム
に選択するという設定で行った。今後は追跡問題の設定を変えたときにどのような結果
が得られるか見ていく必要がある。例えば，マップ環境をトーラス状(上端と下端，左
端と右端が繋がっている状態)に変更したときや，獲物の行動を逃避的なものに変更に
したときに，それに対応した協調動作が獲得できるか検証していく必要がある。また，
斜め方向への移動など行動数を増やした時に，より高度な協調動作を獲得することが期
待できる。
さらに今回の実験では，ハンターに視野を設定し，獲物に対する視野ともう一方のハ
ンターに対する視野の組み合わせ計 81 通りに分割し，ハンターが知覚できる状態とし
た。しかし，ターゲットに対する視野を 7 に設定したため，1 つの状態から想定される
ハンターとエージェントの位置関係が複数存在し，その位置関係次第では異なる協調動
作が必要とされた。より詳細に協調性を評価するためにはこのような状況を回避するた
めに状態の分類をより細かく設定することが必要だと考えられる。また，それに伴う学
習時間やメモリの増加の問題の解決が必要となってくる。
34
５．まとめ
本研究では，マルチエージェント強化学習によって獲得したエージェントの行動につ
いて協調性という点に着目し検証を行ってきた。マルチエージェント系の代表的な問題
である追跡問題を例として，Q-Learning と Profit Sharing の 2 種類の学習アルゴリズ
ムでそれぞれ学習を行い，その結果から特に協調性を必要とする捕獲直前の状態におい
て，各ハンターが獲得した行動の評価を行った。その結果，どちらのアルゴリズムでも
50％以上の割合で強調動作を獲得できることが判った。Q-Learning はパラメータの値
を調整することで学習の制御ができるため，問題設定に応じて柔軟な学習ができると期
待できる。しかし，言い換えれば Q-Learning はパラメータに非常に敏感な学習アルゴ
リズムであるため適切な学習を行うためにはパラメータ設定に工夫が必要であるとい
える。Profit Sharing は協調動作の獲得率が最も高く，学習精度も高いため，マルチエ
ージェント問題において協調行動を学習させるのに非常に適した学習アルゴリズムで
あるといえる。ただし，これらの結果は獲物がランダムに行動を選択するという今回の
問題設定に対する結果であり，Q(λ)における適切なλの値や Q-Learning と Profit
Sharing のどちらが有効的な学習アルゴリズムであるかという点は，扱う問題によって
変わりうるため，さらに多くの問題で検討してみることが必要だと考えられる。
今後の課題は追跡問題の問題設定を変更した時（マップの状態をトーラス状にする，
エージェントの行動数を増やす)にそれに対応した協調動作の検証，状態の分割の仕方
の見直しが残っている。また強化学習は，環境の設定が変わると再学習が必要になると
いう問題点がある。この問題を解決するために決定木などのマイニングツールを用いて，
学習結果から汎化ルールを抽出し，その汎用性の検証などを行う必要がある。
35
謝辞
本研究に際して，数々の丁寧な御指導をしていただいた理学部数理情報科学科
本田理恵
准教授に感謝の意を表し，心からお礼申し上げます。また，研究に関して様々な相談や協
力をしていただいた本田研究室の皆様にもこの場を借りてお礼申し上げます。ここに謹ん
で謝辞を申し上げます。
36
参考文献
[1].RoboCup：ロボカップ日本委員会公式ホームページ，(http://www.robocup.or.jp/)(2008)
[2].[中丁ら 2002] 中丁和也，宮本俊幸，熊谷貞俊：マルチエージェントネットを用いたデマンドバ
スシミュレーションシステム，電子情報通信学会技術研究報告. CST, コンカレント工学，Vol.102,
No.96 pp. 23-29(2002)
[3].[北田・田中 2005] 北田 悟史，田中 敦：マルチエージェント手法による巡回バスのデマンド対
応の効果，電子情報通信学会技術研究報告. NLP, 非線形問題，Vol.105 No.50 pp. 1-4(2005)
[4].[池田・時永 2007] 池田 欽一，時永 祥三：エージェント行動により生成されるマルチフラクタ
ル表面の分析と予測・平滑化手法に基づく特徴抽出，電子情報通信学会技術研究報告. NLP,
非線形問題，Vol.106, No.573 pp. 47-52
[5]. [Watkins 1992] Watkins ， C.J.C.H. ， and Dayan ， P. ： Q-Learning. Machine Learning ，
8:279-292(1992)
[6].[Grefenstette 1988] Grefenstette，J.J.：Credit assignment in rule discovery systems based on
genetic algorithms，Machine Learning，Vol.3，pp.225-245(1988)
[7]. [宮崎ら 1994] 宮崎和光，山村雅幸，小林重信：強化学習における報酬割当の理論的考察，
人工知能学会時，Vol.9 No.4，pp.580-587(1994)
[8]. [荒井ら 1998] 荒井幸代，宮崎和光，小林重信：マルチエージェント強化学習の方法論―
Q-Learning と Profit Sharing による接近―，人工知能学会誌，Vol.13 No.4，pp.609-618(1998)
[9]. [宮崎ら 1999] 宮崎和光，荒井幸代，小林重信：Profit Sharing を用いたマルチエージェント強
化学習における報酬配分の理論的考察，人工知能学会誌，Vol.14 No.6，pp.148-156(1999)
[10]. [木村ら 1999] 木村元，宮崎和光，小林重信：強化学習システムの設計指針，計測と制御，
Vol.38 No.10，特集 展望
[11]. [荒井ら 2006] 荒井幸代，田中信行：マルチエージェント連続タスクにおける報酬設計の理
論的考察―RoboCup Soccer Keepaway タスクを例として―，人工知能学会誌，Vol.21 No.6，
pp.537-546(2006)
[12].[黄 2004] 黄嵩：強化学習による学習エージェントの構成，高知大学理学部数理情報科学科
卒業論文(2004)
[13] [櫻井 2006] 櫻井祐輔：強化学習によるエージェント形成と決定木による評価－追跡問題を
例として－，高知大学理学部数理情報科学科卒業論文(2006)
[14].[内海 2007] 内海朋秀：マルチエージェント強化学習における Profit Sharing の有効性検証
－ 追跡問題を例に―，高知大学理学部数理情報科学科卒業論文(2007)
[15]. [Richaed，Andrew 1998] Ruchard S.Sutton and Andrew G.Barto：強化学習，(三上貞芳，皆川
雅章 共訳)，(森北出版,2000)
37
付録
Ⅰ.Q-Learning の学習アルゴリズム
ⅱ
Ⅰ-A.エージェントの追跡問題(メインプログラム)
ⅱ
Ⅰ-B.エージェントの追跡問題(ヘッダファイル)
ⅵ
Ⅱ.Profit Sharing の学習アルゴリズム
xxxi
Ⅲ.使用方法
xliii
i
付録
Ⅰ．Q-Learning の学習プログラム
Ⅰ-A．エージェントの追跡問題（メインプログラム）
// エージェントの追跡学習
#include "sample15.h"
main(){
int maze[IM][JM];
int agentP[2][2];
//int aP[2][2];
int preyP[2];
//int startP[2][2];
//int startpreyP[2];
int goalP[2];
int agentPreP[2][2];
int iter;
int i,j,k;
int point[2];
int ans;
int cycle;
int show_ans = 1;
char cans;
char gans[10];
char qans[10];
char fname[30];
FILE *fp;
char ofname[10]; /*エピソード毎の報酬記録ファイル */
int sumR = 0;
/*報酬の合計*/
int episode = 0; /*エピソード数*/
int dum;
int renewID=1;
double eps=EPS;
ii
srandom(time(NULL)%RAND_MAX);/*乱数発生系列の初期化*/
printf("create new maze?[y/n]¥n"); /*新の迷路の作成*/
scanf("%c", &cans);
if (cans=='y') {
init_maze(maze, IM, JM);
create_maze(maze, IM, JM);
}
else {
/*記録した迷路を読み込む*/
printf("enter maze filename.¥n");
scanf("%s",fname);
read_maze(maze,IM,JM,fname);
}
initState(agentP,preyP);
show_maze(maze, agentP, preyP);
printf("Sarsa or Qlearing ?[s/q]¥n");
/*sarsa と q 学習を選択*/
scanf("%s",gans);
initAgent();
printf("read q from a file?[y/n]¥n");
/*記録した q 値の読み込み*/
scanf("%s", qans);
if (strcmp(qans,"y")==0) {
for (k=0;k<numH;++k) {
printf("enter qfilename for agent %d.¥n",k);
scanf("%s",fname);
read_q(fname,k);
}
}
sprintf(ofname,"%s_%3.1f.d", gans,lambda);
iii
/*episode と sumR を記録*/
printf("text¥n");
printf("%s¥n",ofname);
fp = fopen(ofname,"w");
if (fp == NULL){
perror(fname);
}
printf("F¥n");
/*maxEpisode 数まで繰り返し*/
for (episode = 0;episode < maxEpisode;++episode)
{
//printf("initState¥n");
initState(agentP,preyP);
if (episode==maxEpisode-1)
show_ans=1;
else
show_ans=0;
sumR=Learn(maze, agentP, preyP, episode,5000,qans,renewID,0,eps);
initState(agentP,preyP);
sumR=Learn(maze, agentP, preyP, episode,5000,qans,0,show_ans,0);
printf("episode = %d
fprintf(fp,"%d
sumR = %d¥n",episode,sumR);
%d¥n",episode,sumR);
}
fclose(fp);
printf("write q into a file?[y/n]¥n");
/*q 値を記録*/
scanf("%s", gans);
if (strcmp(gans,"y")==0) {
for (k=0;k<numH;++k) {
printf("enter qfilename for agent %d.¥n", k);
scanf("%s",fname);
write_q(fname,k);
}
}
iv
printf("write amax into a file (for 2 attributes)?[y/n]¥n");
/*q 値を記録*/
scanf("%s", gans);
if (strcmp(gans,"y")==0) {
for (k=0;k<numH;++k) {
printf("enter filename for agent %d.¥n",k);
scanf("%s",fname);
write_q2(fname,1,k);
}
}
printf("write amax into a file (for 4 attributes) ?[y/n]¥n");
scanf("%s", gans);
if (strcmp(gans,"y")==0) {
for (k=0;k<numH;++k) {
printf("enter filename for agent %d.¥n",k);
scanf("%s",fname);
write_q2(fname,0,k);
}
}
printf("record maze?[y/n]¥n");
/*迷路を記録*/
scanf("%s", &gans);
if (strcmp(gans,"y")==0) {
printf("enter maze filename.¥n");
scanf("%s",fname);
write_maze(maze,IM,JM,fname);
}
}
v
/*q 値を記録*/
Ⅰ-B．エージェントの追跡問題（ヘッダファイル）
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
#undef RAND_MAX
#define RAND_MAX 2147483647
#define IM 15
/*行数*/
#define JM 15
/*列数*/
//#define numS 289
#define numS 100
/*状態数*/
#define numA 5
/*行動数*/
#define numH 2
#define VX
7
/*-VX,VX view of agent for prey*/
#define VY
7
/*-VY,VY view of agent for prey*/
#define AVX
1
/*-VAX,AVX view of agent for colleague*/
#define AVY
1
/*-AVY,AVY view of agent for colleague*/
double Q[numH][numS][numA];
/*Q 値*/
double e[numH][numS][numA];
/*適格度トレース*/
double tdError;
int next_rand(int rmax); /*乱数生成器*/
double alpha = 0.1;
/*学習率*/
double EPS = 0.0;
/*探査的行動を行う確率*/
double gma = 0.95;
/*割引率*/
double lambda = 0.0;
/*トレースの減衰値
0 の時，Q 学習
それ以外，Q(λ)学習*/
int maxEpisode = 5000;
/*エピソード数*/
vi
/*配列*/
void setp(int point[],int x,int y){
point[0] = x;
point[1] = y;
}
void setp2(int p[], int q[]){
q[0] = p[0];
q[1] = p[1];
}
int samePt(int p[2], int q[2])
{
int ans=0;
if (p[0]==q[0]&&p[1]==q[1]) ans=1;
return(ans);
}
int exPt(int p[2], int ppre[2], int q[2], int qpre[2])
{
int ans=0;
if (samePt(p,qpre)==1&&samePt(q,ppre)==1) ans=1;
return(ans);
}
/*迷路の初期化*/
void init_maze(int maze[IM][JM],int im,int jm)
{
int i,j;
for(i=0;i<im;i++)
for(j=0;j<jm;j++)
maze[i][j] = 0;
}
vii
/*迷路を描く*/
void show_maze(int maze[IM][JM],int aP[2][2], int preyP[2])
{
int i,j;
int x,y;
int k;
int gmaze[IM][JM];
for (j=0;j<JM;j++){
for (i=0;i<IM;i++){
gmaze[i][j] = maze[i][j];
}
}
/*エージェントの始点を描画*/
for (k = 0; k<2; ++k){
i = aP[k][0];
j = aP[k][1];
gmaze[i][j] = -k-1;
}
i = preyP[0];
j = preyP[1];
gmaze[i][j] = -3;
/*迷路をコンソールに表示*/
for(j=0;j<JM;j++) {
for(i=0;i<IM;i++) {
if (gmaze[i][j] == 0)
printf("
",gmaze[i][j]);
else if (gmaze[i][j] == 1)
printf("W ",gmaze[i][j]);
else if (gmaze[i][j] == -2)
printf("B ",gmaze[i][j]);
else if (gmaze[i][j] == -1)
printf("A ",gmaze[i][j]);
else if (gmaze[i][j] == -3)
viii
printf("P ",gmaze[i][j]);
}
printf("¥n");
}
}
/*ランダムに迷路を生成*/
void create_maze(int maze[IM][JM],int im,int jm)
{
int i,j,r;
/*外壁の設定*/
/*上下側*/
for(i=0;i<im;i++){
maze[i][0] = 1;
maze[i][jm-1] = 1;
}
/*左右側*/
for(j=0;j<jm;j++){
maze[0][j] = 1;
maze[im-1][j] = 1;
}
/*1 マスおきに壁を作る*/
for(i=0;i<im;i+=2){
for(j=0;j<jm;j+=2){
maze[i][j] = 1;
}
//srandom(time(NULL)%RAND_MAX);/*乱数発生系列の初期化*/
}
/*一番左の壁は 0:上，1:右，2:下，3:左のいずれかに壁を延ばす*/
for (i=2; i<im-1; i+=2) {
r = next_rand(3);
switch (r) {
case 0:
maze[i-1][2] = 1;
break;
case 1:
ix
maze[i][3] = 1;
break;
case 2:
maze[i+1][2] = 1;
break;
case 3:
maze[i][1] = 1;
break;
}
}
/*それ以外は 0:上，1:右，2:下のいずれかに壁を延ばす*/
for (i=2; i<im-1; i+=2) {
for (j=4; j<jm-1; j+=2) {
r = next_rand(2);
switch (r) {
case 0:
maze[i-1][j] = 1;
break;
case 1:
maze[i][j+1] = 1;
break;
case 2:
maze[i+1][j] = 1;
break;
}
}
}
}
/*乱数*/
int next_rand2(int rmax)
{
int r;
r=random();/*乱数の取り出し*/
while (r==RAND_MAX) r=random();
return((int)((double)r/RAND_MAX*rmax));
}
x
int next_rand(int rmax)
{
int r;
double dr,rr;
//srandom(time(NULL)%RAND_MAX);/*乱数発生系列の初期化*/
dr=1.0/(rmax+1);
//printf("dr=%f¥n",dr);
rr=(double)random()/RAND_MAX;
r=(int)(rr/dr);
//printf("%f %d¥n", rr, r);
return(r);
}
/*迷路をファイルに書き込む*/
void write_maze(int maze[IM][JM],int im,int jm,char fname[])
{
int i,j;
FILE *fp;
fp = fopen(fname,"w");
if (fp == NULL){
perror(fname);
}
for(j=0;j<jm;j++)
{
for(i=0;i<im;i++)
{
fprintf(fp,"%d ",maze[i][j]);
}
fprintf(fp,"¥n");
}
fclose(fp);
xi
}
/*ファイルから迷路を読み込む*/
void read_maze(int maze[IM][JM],int im,int jm,char fname[])
{
int i,j;
FILE *fp;
fp = fopen(fname,"r");
if (fp == NULL){
perror(fname);
}
for(j=0;j<jm;j++){
for(i=0;i<im;i++) {
fscanf(fp,"%d",&maze[i][j]);
}
}
fclose(fp);
}
/*Q 値の初期化*/
void initQFunc()
{
int s,a,h;
for(h=0;h<numH;h++)
for(s=0;s<numS;s++)
for(a=0;a<numA;a++)
Q[h][s][a] = 0.0;
}
/*適格度トレースの初期化*/
void initTrace()
{
int s,a,h;
for(h=0;h<numH;h++)
for(s=0;s<numS;s++)
for(a=0;a<numA;a++)
e[h][s][a] = 0.0;
xii
}
/*エージェントを初期化*/
void initAgent()
{
initQFunc();
initTrace();
}
/*状態が state であるときの行動を返す*/
int selectAction(int state, double epsilon, int h)
{
int action;
int maxAction;
/*最大の Q 値を持つ行動を探索*/
int a;
double rr;
rr=(double)random()/RAND_MAX;
if (rr < epsilon
){
action = next_rand(numA-1);
}
else{
action = selectMaxAction(state,h);
}
return (action);
}
/*状態が state であるときの行動を返す(方策は max 選択)*/
int selectMaxAction(int state, int h)
{
int maxAction;
/*最大の Q 値をもつ行動*/
int a;
maxAction = 0;
/*与えられた状態 state で最大 Q 値を持つ行動を探索*/
for (a=0;a<numA;a++) {
if (Q[h][state][a] > Q[h][state][maxAction])
xiii
maxAction = a;
}
return (maxAction);
}
/*Q 値の更新*/
void updateQFunc(int s,int a,int r,int nextS,int nextA, int h)
{
double tdError;
/*TD 誤差*/
int i,j;
/*TD 誤差の計算*/
tdError = (double)r + gma * Q[h][nextS][nextA] - Q[h][s][a];
/*(s,a)の適格度トレースを＋１する*/
e[h][s][a] += 1;
for (i=0;i<numS;i++){
for (j=0;j<numA;j++){
/*Q 値の更新*/
Q[h][i][j] = Q[h][i][j] + alpha * tdError * e[h][i][j];
/*適格度トレースの更新*/
e[h][i][j] = gma * lambda * e[h][i][j];
}
}
}
/*Q 値をファイルに書き込む*/
void write_q(char fname[], int k)
{
int i,j;
FILE *fp;
fp = fopen(fname,"w");
if (fp == NULL){
perror(fname);
}
for (i=0;i<numS;i++){
for (j=0;j<numA;j++){
fprintf(fp,"%f
%f ",Q[k][i][j],tdError);
xiv
}
fprintf(fp,"¥n");
}
fclose(fp);
}
void write_q2(char fname[], int id, int k)
{
int i,j;
double max;
int amax;
double sumQ;
FILE *fp;
char action[numA+1][20];
char state[10][20];
strcpy(action[0],"leftward");
strcpy(action[1],"downward");
strcpy(action[2],"rightward");
strcpy(action[3],"upward");
strcpy(action[4],"stay");
strcpy(action[5],"?");
if (id==0) {
strcpy(state[0],"C,C");
strcpy(state[1],"U,C");
strcpy(state[2],"U,R");
strcpy(state[3],"C,R");
strcpy(state[4],"D,R");
strcpy(state[5],"D,C");
strcpy(state[6],"D,L");
xv
strcpy(state[7],"C,L");
strcpy(state[8],"U,L");
strcpy(state[9],"O,O");
}
else {
strcpy(state[0],"CC");
strcpy(state[1],"UC");
strcpy(state[2],"UR");
strcpy(state[3],"CR");
strcpy(state[4],"DR");
strcpy(state[5],"DC");
strcpy(state[6],"DL");
strcpy(state[7],"CL");
strcpy(state[8],"UL");
strcpy(state[9],"OO");
}
fp = fopen(fname,"w");
if (fp == NULL){
perror(fname);
}
for (i=0;i<numS;i++){
max=-1e25;
amax=0;
sumQ=0;
for (j=0;j<numA;j++){
if (Q[k][i][j]>max) {
max=Q[k][i][j];
amax=j;
sumQ+=Q[k][i][j];
}
//fprintf(fp,"%f
%f
}
if (sumQ==0) amax=5;
xvi
",Q[i][j],tdError);
printf("%s,%s,%s¥n",state[(int)(i/10)],state[i%10],action[amax]);
fprintf(fp,"%s,%s,%s¥n",state[(int)(i/10)],state[i%10],action[amax]);
//fprintf(fp,"¥n");
}
fclose(fp);
}
/*Q 値をファイルから読み込む*/
void read_q(char fname[], int k)
{
int i,j;
FILE *fp;
fp = fopen(fname,"r");
if (fp == NULL){
perror(fname);
}
for (i=0;i<numS;i++){
for (j=0;j<numA;j++){
fscanf(fp,"%f
%f
",&Q[k][i][j],&tdError);
}
}
fclose(fp);
}
/*エージェントの座標から状態を求める*/
int getState(int point[])
{
/*迷路の各部屋を 1 つの状態とし，左上から状態番号を割り当てる
エージェントのいる位置が環境の状態となる*/
return(point[1] * JM + point[0]);
}
int getState2(int aP[], int preyP[], int vx, int vy)
{
//
812
xvii
//
703
//
654
//
otherwise 9
int dist[2];
int k;
int s;
for (k=0;k<2;++k) {
dist[k]=preyP[k]-aP[k];
}
if (dist[0] >= -vx && dist[0] <= vx && dist[1] >= -vy && dist[1] <= vy) {
if (dist[0]==0){
if (dist[1]==0)
s=0;
else if (dist[1]<0)
s=1;
else if (dist[1]>0)
s=5;
}
else if (dist[0]>0){
if (dist[1]<0)
s=2;
else if (dist[1]==0)
s=3;
else if (dist[1]>0)
s=4;
}
else if (dist[0]<0){
if (dist[1]<0)
s=8;
else if (dist[1]==0)
s=7;
else if (dist[1]>0) s=6;
}
}
else s=9;
return s;
}
int getState2C(int aP[], int apo[], int preyP[])
{
//
812
//
703
xviii
//
654
//
otherwise 9
int sp,sa;
int k;
int s;
sa=getState2(aP,apo,AVX,AVY); /*position of the other agent*/
sp=getState2(aP,preyP,VX,VY); /*position of prey */
return sa+sp*10;
}
/*環境状態の初期化*/
void initState(int aP[2][2],int preyP[2])
{
int s;
int k;
int ax,ay;
aP[0][0]=next_rand(IM-3)+1;
aP[0][1]=next_rand(JM-3)+1;
ax=next_rand(IM-3)+1;
ay=next_rand(JM-3)+1;
while (ax==aP[0][0] && ay==aP[0][1]){
ax=next_rand(IM-3)+1;
ay=next_rand(JM-3)+1;
}
aP[1][0]=ax;
aP[1][1]=ay;
ax=next_rand(IM-3)+1;
xix
ay=next_rand(JM-3)+1;
while ( (ax==aP[0][0] && ay==aP[0][1]) || (ax==aP[1][0] && ay==aP[1][1]) ){
ax=next_rand(IM-3)+1;
ay=next_rand(JM-3)+1;
}
preyP[0]=ax;
preyP[1]=ay;
}
/*エージェントが現状態に対し行動をとった時の報酬を返す*/
int getReward(int aP[2][2],int aPP[2][2],int maze[IM][JM],int im,int jm)
{
int reward;
/*もし正しい選択を取れば報酬は 0*/
if (agentatWall(aPP,maze) == 1 && leftWall(aP,aPP,maze) == 1)reward=0;
else if (agentatConter(aPP,maze) == 1 &&agentatWall(aP,maze) ==1
&& leftWall(aP,aPP,maze) == 1)reward=0;
/*それ以外なら報酬は-1*/
else reward = -1;
return(reward);
}
/*エージェントが現状態に対し行動をとった時の報酬を返す*/
int getReward2(int aP[2][2], int preyP[2])
{
int reward;
int count=0;
count=agentContactsPrey(aP[0],preyP)+agentContactsPrey(aP[1],preyP);
if (count==2) reward=0;
else reward = -1;
return(reward);
xx
}
int agentLostPrey(int s, int sPre)
{
int ans;
if (sPre!= 9 && sPre == 9) ans = 1;
else ans = 0;
return(ans);
}
int agentContactsPrey(int aP[2],int preyP[2])
{
int ans=0;
int i;
int dv[2];
for (i=0;i<2;++i) {
dv[i]=abs(preyP[i]-aP[i]);
}
if ((dv[0]==0&&dv[1]==1)||(dv[0]==1&&dv[1]==0)) ans=1;
else ans=0;
return(ans);
}
/*壁が上下左右にある時*/
int agentatWall(int aP[2], int maze[IM][JM])
{
int x,y;
int ans=0;
x=aP[0];
y=aP[1];
if
(maze[x][y+1]==1
||
maze[x][y-1]==1
maze[x-1][y]==1 ) ans=1;
xxi
||
maze[x+1][y]==1
||
return(ans);
}
/*壁がコーナーにある時*/
int agentatConter(int aP[2], int maze[IM][JM])
{
int x,y;
int ans=0;
x=aP[0];
y=aP[1];
if (agentatWall(aP,maze) == 0 && (maze[x-1][y+1]==1 || maze[x-1][y-1]==1 ||
maze[x+1][y+1]==1 || maze[x+1][y-1]==1)) ans=1;
return(ans);
}
/*左側の壁*/
int leftWall(int aP[2], int aPP[2], int maze[IM][JM])
{
int x,y;
int ans=0;
x=aPP[0];
y=aPP[1];
if (((aP[0] - aPP[0]) == -1 && (aP[1] - aPP[1]) == 0)
&&(maze[x][y+1] == 1 || maze[x-1][y+1] == 1 )) ans=1;
else if (((aP[0] - aPP[0]) == 0 && (aP[1] - aPP[1]) == -1)
&&(maze[x-1][y] == 1 || maze[x-1][y-1] == 1 )) ans=1;
else if (((aP[0] - aPP[0]) == 1 && (aP[1] - aPP[1]) == 0)
&&(maze[x][y-1] == 1 || maze[x+1][y-1] == 1 )) ans=1;
else if (((aP[0] - aPP[0]) == 0 && (aP[1] - aPP[1]) == 1)
&&(maze[x+1][y] == 1 || maze[x+1][y+1] == 1 )) ans=1;
return(ans);
}
/*現状態に対し行動 a をとり，環境の状態を更新してその状態を返す*/
int moveAgent(int maze[IM][JM],int agentP[2], int a)
xxii
{
int i,j;
i = agentP[0];
j = agentP[1];
/*行動 a={0,1,2,3,4}={左，上，右，下，その場に停滞}*/
/*迷路は道=0，壁=1 とする*/
switch(a){
case 0:
/*壁がなければ，エージェントを下へ１マス進め*/
i--;
break;
case 1:
/*壁がなければ，エージェントを右へ１マス進める*/
j++;
break;
case 2:
/*壁がなければ，エージェントを左へ１マス進める*/
i++;
break;
case 3:
/*壁がなければ，エージェントを下へ１マス進める*/
j--;
break;
case 4:
break;
}
if (maze[i][j]==0) setp(agentP,i,j);
}
/*現状態に対し行動 a をとり，環境の状態を更新し，その状態を返す*/
void nextState(int maze[IM][JM],int a[2],int agentP[2][2],int preyP[2], int s[2])
{
int agentPreP[2][2];
int i;
int k;
for (i=0; i<2;++i) {
xxiii
for (k=0; k<2; ++k){
agentPreP[k][i] = agentP[k][i];
}
}
for (k=0; k<2; ++k){
moveAgent(maze,agentP[k],a[k]);
}
/* collision*/
if
(samePt(agentP[0],preyP)==1||samePt(agentP[1],preyP)==1||samePt(agentP[0],agen
tP[1])==1) {
for (i=0; i<2;++i) {
for (k=0; k<2; ++k){
agentP[k][i] = agentPreP[k][i];
}
}
}
s[0]= getState2C(agentP[0],agentP[1],preyP);
s[1]= getState2C(agentP[1],agentP[0],preyP);
}
void moveAgents(int maze[IM][JM],int a,int agentP[2],int aP1[2],int aP2[2])
{
int agentPreP[2];
int i;
int k;
setp2(agentP,agentPreP);
moveAgent(maze,agentP,a);
/* collision*/
if (samePt(agentP,aP1)+samePt(agentP,aP2)!=0) {
xxiv
setp2(agentPreP,agentP);
}
}
/*強化学習によって得られた属性ベクトルをファイルに書き込む*/
/*上*/
void upward(int aP[2])
{
aP[1] -= 1;
}
/*左*/
void leftward(int aP[2])
{
aP[0] -= 1;
}
/*右*/
void rightward(int aP[2])
{
aP[0] += 1;
}
/*下*/
void downward(int aP[2])
{
aP[1] += 1;
}
/*エージェント 0 の行動*/
void MoveAgentByRuleZero(int aP[],int maze[IM][JM])
/*オールゼロ属性を含む場
合*/
{
int i,j;
int upperleft,left,lowerleft,up,down,upperright,right,lowerright;
i = aP[0];
j = aP[1];
xxv
upperleft = maze[i-1][j-1];
left = maze[i-1][j];
lowerleft = maze[i-1][j+1];
up = maze[i][j-1];
down = maze[i][j+1];
upperright = maze[i+1][j-1];
right = maze[i+1][j];
lowerright = maze[i+1][j+1];
if(left == 0)
{
if(lowerleft == 1)leftward(aP);
if(lowerleft == 0){
if(right == 0){
if(upperright == 1)rightward(aP);
if(upperright == 0){
if(upperleft == 0){
if(lowerright
0)leftward(aP);
else if(lowerright == 1){
if(down == 0)downward(aP);
else if(down == 1)leftward(aP);
}
}
else if(upperleft == 1){
if(up == 0)upward(aP);
else if(up == 1)rightward(aP);
}
}
}
else if(right == 1){
if(down == 0)downward(aP);
else if(down == 1)leftward(aP);
}
}
}
xxvi
==
if(left == 1)
{
if(up == 0)upward(aP);
else if(up == 1)rightward(aP);
}
}
/*エージェント 1 の行動*/
void MoveAgentByRuleOne(int aP[],int maze[IM][JM])
/*オールゼロ属性を除く場
合*/
{
int i,j;
int upperleft,left,lowerleft,up,down,upperright,right,lowerright;
i = aP[0];
j = aP[1];
upperleft = maze[i-1][j-1];
left = maze[i-1][j];
lowerleft = maze[i-1][j+1];
up = maze[i][j-1];
down = maze[i][j+1];
upperright = maze[i+1][j-1];
right = maze[i+1][j];
lowerright = maze[i+1][j+1];
if(left == 1)
{
if(up == 0)upward(aP);
else if(up == 1)rightward(aP);
}
if(left == 0)
{
if(lowerleft == 1)leftward(aP);
else if(lowerleft == 0){
if(down == 1)leftward(aP);
xxvii
else if(down == 0){
if(lowerright == 1)downward(aP);
else if(lowerright == 0){
if(right == 1)downward(aP);
else if(right == 0){
if(upperright == 1)rightward(aP);
else if(upperright == 0){
if(up == 0)upward(aP);
else if(up ==1)rightward(aP);
}
}
}
}
}
}
}
/*Q-Learning の強化関数*/
int Learn(int maze[IM][JM], int aP[2][2], int preyP[], int episode, int step, char qans[],
int renewID, int showID, double eps)
{
int sumR=0;
int show_ans;
int iter;
int s[2];
/*現状態*/
int a[2];
/*現在の行動*/
int nextS[2];
/*次状態*/
int nextA[2];
/**次の状態の行動*/
int k;
int r;
/*報酬*/
show_ans=showID;
xxviii
//show_ans=1;
iter=0;
r=-2;
/*エピソードの各ステップに対してゴール状態になるまで繰り返し*/
while (iter<1000 && r!=0) {
if (iter==0){
initTrace();
s[0]=getState2C(aP[0],aP[1],preyP);
s[1]=getState2C(aP[1],aP[0],preyP);
for (k=0; k<2; ++k){
//
s[k] = getState2(aP[k], preyP);
/*環境の状態を初期化*/
/*適格度トレースを初期化*/
/*状態 s における行動 a を選択，epsilon-greety*/
/*sarsa 学習*/
a[k] = selectAction(s[k],eps,k);
}
}
/*現状態に対し行動 a をとり，次状態 nextS と報酬 r を観測する*/
if (strcmp(qans,"q")==0) {
/*Q-Laening*/
for (k=0; k<2; ++k) {
a[k] = selectAction(s[k],eps,k);
}
}
moveAgents(maze,a[0],aP[0],aP[1],preyP);
moveAgents(maze,a[1],aP[1],aP[0],preyP);
r = getReward2(aP,preyP);
xxix
if (show_ans == 1 ){
show_maze(maze,aP,preyP);
printf("¥nEnter 1 to keep showing, otherwise 0¥n");
scanf("%d",&show_ans);
}
/* move prey */
moveAgents(maze,next_rand(numA-1),preyP,aP[0],aP[1]);
//printf("nextStep¥n");
/*nextS における行動 nextA を選択する(方策：max)*/
nextS[0]=getState2C(aP[0],aP[1],preyP);
nextS[1]=getState2C(aP[1],aP[0],preyP);
for (k=0; k<2; ++k){
nextA[k] = selectAction(nextS[k],eps,k);
}
/*Q 値の更新*/
if (renewID==1) {
for(k=0; k<2; ++k){
updateQFunc(s[k],a[k],r,nextS[k],nextA[k],k);
}
}
/*次状態へ遷移*/
sumR += r;
for(k=0; k<2; ++k){
s[k] = nextS[k];
a[k] = nextA[k];
}
iter++;
}
return(sumR);
xxx
}
Ⅱ．Profit Sharing の学習プログラム
Ⅱ-A．エージェントの追跡問題
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
public class PSm4 extends JFrame implements ActionListener,Runnable{
MyCanvas c1;
JButton b1,b3;
Thread t1;
int width =800;
int height=800;
boolean KissOfDeath;
int i0,i1,j0,j1;
int an=2;
/*エージェントの数*/
int am=5;
/*行動の数*/
int sn=100;
/*状態の数*/
int tavx=7;
/*ターゲットに対する横の視野*/
int tavy=7;
/*ターゲットに対する縦の視野*/
int avx=1;
/*他のエージェントに対する横の視野*/
int avy=1;
/*他のエージェントに対する縦の視野*/
int w=5; /*強化区間*/
int st1;
/*状態*/
int st2;
int sa=0;
int a;
/*選択されたエージェント*/
/*選択された行動*/
int a1;
int a2;
int ra1; /*実行した行動*/
int ra2;
int maxstep=1000;
xxxi
int maxepisode=6000;
String logfile="080126-05."+maxstep+"."+maxepisode+"log.d";
String weightfile="080126-05."+maxstep+"."+maxepisode+"weight.d";
double r=0;
/*報酬*/
int mp=14;
/*初期配置の最大値*/
int ax;
/*初期配置*/
int ay;
Rule2 rule2;
Rule2 rule;
Map map;
Agent [] h = new Agent[an];
Agent ta ;
Episod eps;
int step;
int episode;
int NN = 50000;
int [] epscap = new int [NN];
int [] stepcap = new int [NN];
int capno = 0;
PSm4() {
super();
setTitle("Profit Sharing");
setBounds( 0, 0, 1200, 600);
Container c = getContentPane();
BorderLayout layout = new BorderLayout();
c.setLayout(layout);
i0=10;
j0=10;
i1=810;
j1=810;
KissOfDeath = false;
c1 = new MyCanvas();
c.add(c1,layout.CENTER);
JPanel jc= new JPanel();
b1 = new JButton("GO/STOP");
xxxii
//b1.setBounds(25,200,50,25);
b1.addActionListener(this);
jc.add(b1, new BorderLayout().WEST);
b3 = new JButton("reset");
//b3.setBounds(175,200,50,25);
b3.addActionListener(this);
jc.add(b3, new BorderLayout().EAST);
c.add(jc,layout.SOUTH);
//resetTime();
episode=0;
rule2 = new Rule2(an,sn,am,w);
rule = new Rule2(an,10,am,w);
/*rule.readsrdata("07.01.27-21sr.1000.300weight.d");
for(int i=0;i<an;++i){
for(int j=0;j<10;++j){
for(int k=0;k<am;++k){
for(int l=0;l<10;++l){
rule2.sr[i][j+l*10][k]=rule.sr[i][j][k];
}
}
}
}*/
//rule2.readsrdata("07.01.29-53.1000.2000weight.d");
//rule2.hyojiSr();
}
public static void main(String args[]){
JFrame f = new PSm4();
f.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
f.setSize( 1200, 600);
//ww.pack();
f.setVisible( true );
}
public void actionPerformed(ActionEvent ev) {
xxxiii
if (ev.getSource() == b1) {
KissOfDeath = ! KissOfDeath;
if (KissOfDeath){
t1 = new Thread(this);
t1.start();
}
}
else if (ev.getSource() == b3) {
//resetTime();
c1.repaint();
}
}
public void run(){
try {
while(KissOfDeath && episode<maxepisode){
//rule = new Rule(an,sn,am,w);
//for(int j=0;j<maxepisode;++j){
r=0;
map = new Map(17,17);
//map.show();
/*h[0] = new Agent(1,1,map,false,0);
h[1] = new Agent(15,15,map,false,1);
ta = new Agent(8,8,map,true,0);*/
h[0]
=
new
Agent(getNextRand(mp)+1,getNextRand(mp)+1,map,false,0);
ax
=
getNextRand(mp)+1;
ay
=
getNextRand(mp)+1;
while(ax==h[0].x && ay==h[0].y){
ax = getNextRand(mp)+1; ay =
getNextRand(mp)+1;
}
h[1] = new Agent(ax,ay,map,false,1);
ax
=
getNextRand(mp)+1;
ay
=
getNextRand(mp)+1;
while((ax==h[0].x
xxxiv
&&
ay==h[0].y)||(ax==h[1].x && ay==h[1].y)){
ax = getNextRand(mp)+1; ay =
getNextRand(mp)+1;
}
ta = new Agent(ax,ay,map,true,0);
eps = new Episod(an);
step=0;
while(r==0 && step<maxstep){
//System.out.println("*****time="+step);
//for(a=0;a<am;++a){
//sa=getNextRand(an);
//System.out.println(sa);
a=getNextRand(am);
ta.move(a,map,0);
//Agent１の状態
st1
=
h[0].getstate(ta,tavx,tavy)+h[0].getstate(h[1],avx,avy)*10;
a1 = rule2.selectaction(0,st1);
//Agent２の状態
st2
=
h[1].getstate(ta,tavx,tavy)+h[1].getstate(h[0],avx,avy)*10;
a2 = rule2.selectaction(1,st2);
//a=getNextRand(am);
//System.out.println("sa="+sa+"
s="+st+" a="+a);
ra1 = h[0].move(a1,map,0);
a1 = ra1;
eps.hozon(0,st1,a1);
ra2 = h[1].move(a2,map,1);
a2 = ra2;
eps.hozon(1,st2,a2);
//System.out.println("(after
sa="+sa+" s="+st+" a="+a);
//h[0].move(a, map, 0);
xxxv
move)
//System.out.println(ta.hokaku(an,h));
r = h[1].getreward(an,h,ta,map);
//System.out.println(r);
//h[0].move
//map.show();
/*for(int j=0;j<an;++j){
System.out.println(j+"
"+h[j].getstate(ta));
}*/
//eps.hyouji();
step++;
if (episode%999999==0) {
c1.repaint();
t1.sleep(1);
}
//t++;
}
if(r!=0){
//System.out.println("myu="+u);
//eps.hyouji();
rule2.kyouka(r,1, eps);
//rule.hyojiSr();
c1.repaint();
//KissOfDeath=false;
System.out.println("episode="+episode+"で捕獲"+" step="+step);
epscap[capno]=episode;
stepcap[capno]=step;
capno++;
}else{
epscap[capno]=episode;
stepcap[capno]=step;
capno++;
}
episode++;
}
xxxvi
rule2.hyojiSr();
savelogdata(logfile);
rule2.saveweightdata(weightfile);
//}
}
catch(Exception e){
System.out.println(e);
}
}
class MyCanvas extends JLabel{
MyCanvas(){
}
public void paintComponent(Graphics g ){
//super.paintComponent(g);
//Graphics2D g2= (Graphics2D) g;
showmap(g);
}
public void showmap(Graphics g){
int x0=10;
int y0=10;
int w=480;
int h=480;
float dw=w/(float)map.width;
float dh=h/(float)map.height;
g.setColor(Color.LIGHT_GRAY);
g.fillRect(x0,y0,w,h);
g.setColor(Color.BLACK);
g.drawString("agent=0",510,10);
g.drawString("selectaction="+a1,510,30);
g.drawString("action="+ra1,510,50);
xxxvii
g.drawString("agent=1",510,70);
g.drawString("selectaction="+a2,510,90);
g.drawString("action="+ra2,510,110);
g.drawString("episode="+episode+" step="+step,510,150);
//g.drawString(, 510, 110)
//Episod eps = new Episod(an);
String stra,strs;
for(int i=0;i<an;++i){
//g.drawString("agentid="+i+"
length="+eps.length[i],510,110+60*i);
stra="";
strs="";
for(int j=0;j<eps.length[i];++j){
strs+=eps.sn[i][j];
stra+=eps.acn[i][j];
}
//g.drawString(strs,510,130+60*i);
//g.drawString(stra,510,150+60*i);
}
int jstart=10;
int istart=800;
for(int i=0;i<an;++i){
istart=800;
g.drawString("agentid="+i,istart,jstart);
jstart+=20;
String strsr;
for(int j=0;j<am;++j){
//strsr="";
istart=800;
g.setColor(Color.BLACK);
g.drawString("a"+j,istart,jstart);
istart+=60;
for(int k=0;k<sn;++k){
if(rule2.sr[i][k][j]==10.){
g.setColor(Color.BLACK);
}else g.setColor(Color.RED);
xxxviii
strsr=Math.round(rule2.sr[i][k][j]*10000)/10000.+" ";
g.drawString(strsr,istart,jstart);
istart+=60;
}
jstart+=20;
//System.out.println(" "+strsr);
//System.out.printf("¥n");
}
}
for (int j=0;j<map.height;++j) {
for (int i=0;i<map.width;++i) {
if (map.st[i][j]==1) g.setColor(Color.BLACK);
else g.setColor(Color.LIGHT_GRAY);
g.fillRect((int)(x0+dw*i), (int)(y0+dh*j), (int)(dw),
(int)(dh));
}
}
for (int j=0;j<map.height;++j) {
for (int i=0;i<map.width;++i) {
if (map.st[i][j]>=2) {
g.setColor(Color.CYAN);
int vxmin=i-tavx;
int vxmax=i+tavx;
int vymin=j-tavy;
int vymax=j+tavy;
if(vxmin<1) vxmin=1;
if(vxmax>map.width-2)
vxmax=map.width-2;
if(vymin<1) vymin=1;
if(vymax>map.height-2)
vymax=map.height-2;
xxxix
for(int ii=vxmin;ii<=vxmax;++ii){
for(int
jj=vymin;jj<=vymax;++jj){
g.fillRect((int)(x0+dw*ii), (int)(y0+dh*jj), (int)(dw), (int)(dh));
}
}
}
}
}
for (int j=0;j<map.height;++j) {
for (int i=0;i<map.width;++i) {
if (map.st[i][j]>=2) {
g.setColor(Color.BLUE);
g.fillRect((int)(x0+dw*i),
(int)(y0+dh*j),
(int)(dw), (int)(dh));
g.setColor(Color.YELLOW);
g.drawString(""+(map.st[i][j]-2),(int)(x0+dw*(i+0.5)),(int)(y0+dh*(j+0.5)));
}
else if (map.st[i][j]==-1) {
g.setColor(Color.RED);
g.fillRect((int)(x0+dw*i),
(int)(y0+dh*j),
(int)(dw), (int)(dh));
}
}
}
g.setColor(Color.BLACK);
for(int i=0;i<map.width+1;++i) g.drawLine((int)(x0+dw*i), y0, (int)(x0+dw*i),
y0+h);
for(int
j=0;j<map.height+1;++j)
x0+w,(int)(y0+dh*j));
}
xl
g.drawLine(x0,(int)(y0+dh*j),
}
public int getNextRand(int n){
int a;
double r=Math.random();
//System.out.println(r+"
"+r/(1.0/am)+"
"+(int)(r/(1.0/am))+"
"+Math.round(r/(1.0/am)));
a=(int)(Math.abs(r-0.0000000001)/(1.0/n));
return a;
}
public void savelogdata(String logfile){
double sumstep = 0;
double v=0;
for(int j=0;j<capno;++j){
sumstep += stepcap[j];
}
sumstep = sumstep/capno;
for(int k=0;k<capno;++k){
v += Math.pow(sumstep-stepcap[k],2);
}
v = Math.sqrt(v/capno);
try{
BufferedWriter
bo
=
new
BufferedWriter(new
FileWriter(logfile));
for(int i=0;i<capno;++i){
String
logdata="episode=
"+stepcap[i];//+" average= "+sumstep+" v= "+v;
bo.write(logdata);
bo.newLine();
}
bo.close();
xli
"+epscap[i]+"
step=
}
catch(Exception e){System.out.println(e);}
}
}
xlii
Ⅲ.各プログラムの使用方法
●Q-Learning のプログラムについて
メインプログラムとヘッダファイルを同一のディレクトリにおいてコンパイルしてから実
行。
create new maze?[y/n]では n を選択し，maze2.d を読みこむ。
Sarsa or Qlearing?[s/q]で学習アルゴリズムの選択を行う
read q from a file?[y/n]学習を行う場合は n，過去の学習結果を用いて実行したい場合は y
を選択して使用したい Q ファイルを読み込む。
以上の設定を行ったら学習を開始する。最大ステップ数や最大エピソード数を変更したい
場合はヘッダファイル内の iter と maxEpisode の値を任意で変更する。
学習終了後，Q 値等の学習結果の保存が可能。
●Profit Sharing のプログラムについて
Java で実装されている。Eclipse 等で実行。
String logfile,String weightfile に保存するファイル名を入力。
logfile は各エピソードの捕獲ステップ数，weightfile はルールの重みを出力
過去の学習結果を読み込む場合は、rule.readsrdata に読み込むファイル名を入力。
新しく学習させる場合は。その部分をコメントアウト。
実行中の動作を見たい場合は、そのまま実行。
学習させるために飛ばしたい場合は if(episode%1==0)の 1 を適当に大きい数字に変える。
プログラムのその他各種初期設定はプログラム中の数値を変えて行う。
xliii