多目的タスクにおけるタスク空間分割を利用した multi

情報処理学会第 76 回全国大会
2U-2
多目的タスクにおけるタスク空間分割を利用した
multi-agent profit sharing
木田 椋子
長行 康男
大手前大学 現代社会学部
1
はじめに
複数の行動主体（エージェント）が存在する環境（マルチ
エージェント環境）において，個々のエージェントが自分自
身の役割を強化学習[1]により獲得するマルチエージェント
強化学習の研究が近年注目を集めており，数多くの研究成果
が報告されている[2]．ところで，これらの研究で取り扱わ
れているタスクは，エージェントの学習目的が単一のものが
ほとんどで，学習目的が複数存在するタスクでの研究はあま
り報告されていない．しかしながら，学習目的が単一である
環境は特別な環境で，現実的な環境においては，一般に学習
目的は複数存在する．
Whitehead らは，学習目的が複数存在するシングルエージ
ェント環境において，学習目的ごとにタスク空間を分割して
学習を行う Q 学習[1]に基づいた強化学習法を提案し，その
有効性を示した[3]．また，我々は学習目的が複数存在する
マルチエージェント環境においても Whitehead らの手法[3]
（Q 学習に基づいた手法）が有効であることを示した[4]．
ところで，マルチエージェント環境における強化学習では，
Q 学習よりも profit sharing[1]の方が，学習性能が良いこ
とが報告されている[5]．
そこで本研究では，学習目的が複数存在するマルチエージ
ェント環境において，学習目的ごとにタスク空間を分割して
学習を行う profit sharing に基づいた一強化学習法を提案
し，その学習性能の有効性を評価する．
2
追跡問題
本研究では，実験タスクとして追跡問題を採用する．追跡
問題は，ハンターが獲物を追いかけて捕獲する課題である．
以下に，本研究における追跡問題の問題設定を示す．





2 次元（7×7）のトーラス状グリッド空間中に，2 体の
ハ ン タ ー （ hunter_1, hunter_2 ） と 2 体 の 獲 物
（prey_1, prey_2）が存在する（図 1）．
本研究では，ハンターを『エージェント』と定義する．
各時間ステップで，すべてのハンターと獲物は，それ
ぞれ１つの行動を同期して実行する．ここで，ハンタ
ー，獲物が実行可能な行動は，隣接する上，下，左，
右のグリッドへ移動する（図 1(a)の矢印），現在位置
に留まる，の 5 通りとする．
ハンターの目標は，どちらか 1 体の獲物を捕獲するこ
ととする．ここで獲物捕獲の定義は，『2 体のハンタ
ーが獲物を上下，あるいは左右から挟んだ状態』とす
る（図 1(b)）．ハンターが獲物を捕獲したとき，ハン
ターは環境から報酬を受け取る．
獲物が各時間ステップで実行する行動は確率的で，
prey_1 の行動確率は，左への移動を 0.25，右へ移動を
0.75，その他の行動を 0 としている．また，prey_2
の行動確率は，上への移動を 0.5，左，下への移動を
そ
(a)
グリッド空間
(b)
捕獲状態の例
○：hunter_1，●：hunter_2，△：prey_1，▲：prey_2
図1

追跡問題のグリッド空間
それぞれ 0.25，その他の行動を 0 としている．これら
の行動確率は時不変とする．
初期配置から，どちらかの獲物が捕獲されるまでを『1
エピソード』とする．どちらか一方でも獲物が捕獲さ
れると，すべてのハンター，獲物はグリッド空間中に
ランダムに初期配置され，新たにエピソードを開始す
る．
本研究では，上記の追跡問題において，個々のエージェン
ト（ハンター）がそれぞれ独立に強化学習を行うことにより，
獲物捕獲行動（協調行動）を学習することを考える．
3 マルチエージェント強化学習
3.1 profit sharing
本研究で採用する強化学習法である profit sharing を上
記の追跡問題にそのまま適用した場合の学習の流れを次に示
す．
エピソードごとに，以下の手続き①～手続き④を獲物を捕
獲するまで繰り返す．
①
②
③
Multi-agent profit sharing by decomposing the task space in a
multipurpose task
Ryoko Kida and Yasuo Nagayuki
Faculty of Moden Social Studies, Otemae University
2-615
ある時間 t において（各エピソードの開始時を t=0 と
する），hunter_i（i=1,2）は，現在の環境状態 st ∈S
（S は環境状態の集合）を観測する．ここで，環境状態
s は，自分（hunter_i）から見た，hunter_j（j≠i），
prey_1，prey_2 のそれぞれの相対位置の組合せとする．
例えば，図 1(a)における hunter_1 から見た環境状態 s
は（[1,2]，[3,3],[-3,-1]）である．
hunter_i は，環境状態 st における行動決定関数 ω(st,
a) を基に，時間 t で実行すべき行動 at∈A（A は行動
の集合）を選択する．この行動選択は確率的で，確率ε
で実行可能な全ての行動の中からランダムに行動を選択
し，残りの確率 1-εで，行動決定関数ωの値が最大で
ある行動を選択する．
hunter_i は，手続き②で選択した行動 at を実行する．
このとき，hunter_j，prey_1，prey_2 も同期して行動
を実行する．これらの行動により，環境状態は st から
st+1 へ遷移する．
Copyright 2014 Information Processing Society of Japan.
All Rights Reserved.
情報処理学会第 76 回全国大会
④
環境状態 st+1 が獲物捕獲状態でなければ，t に 1 を加え
て，手続き①に戻る．
環境状態 st+1 が獲物捕獲状態であれば，hunter_i は,
環境から報酬 r を受け取り，x=0,1,…,t のすべての x
において，行動決定関数ωの値を式(1)の更新式に従っ
て更新（学習）し，このエピソードを終了する．
ω(sx, ax) ← ω(sx, ax) + r × ct-x
(1)
ここで，c∈[0,1] はパラメータ（公比）である．
3.2
タスク空間分割を利用したprofit sharing
複数の学習目的が存在する環境において，従来の profit
sharing をそのまま適用した場合，前節の学習の流れの手続
き①のように，すべての学習目的（獲物）をまとめて一つの
環境状態として扱うことになる．この場合，タスク空間の状
態数（環境状態の集合 S の要素数）は，学習目的の増加に対
して指数関数的に増大する．例えば，上記の追跡問題におけ
るタスク空間の状態数は，49×49×49（「“他エージェント
との相対位置”のパターン数」×「“prey_1 との相対位
置”のパターン数」×「“prey_2 との相対位置”のパター
ン数」）となり，獲物 1 体ごとにタスク空間のサイズは 49
倍となる．強化学習において，タスク空間サイズの指数関数
的増大は，学習の収束を大幅に遅らせる要因となる．
ところで，我々人間が上記の追跡問題のハンターの立場に
置かれた場合，タスク空間を上記のように一枚岩としては捉
えず，獲物ごとにタスク空間を分けて捉えるはずである．そ
の方が効率が良いからである．
本研究で提案する手法では，我々人間が行うであろう方法
と同様，複数の学習目的を 1 つのタスク空間としては扱わず，
学習目的ごとにタスク空間を分割する．これによりタスク空
間の指数関数的増大を防ぐことができ，学習の収束が速くな
ることが期待できる．上記の追跡問題では，自分
（hunter_i）から見た環境状態を，hunter_j，prey_1 のそ
れぞれの相対位置の組合せ（s1 とする）と，hunter_j，
prey_2 のそれぞれの相対位置の組合せ（s2 とする）の 2 つ
に分割する．例えば，図 1(a)における hunter_1 から見た環
境状態 s1 は（[1,2]，[3,3]）, s2 は（[1,2],[-3,-1]）とな
る．そして，それぞれの状態空間に対応した行動決定関数ω
1
(s1,a)，ω 2(s2,a) を用意し，それぞれの行動決定関数で
別々に行動学習を行う．提案手法における学習の流れは，以
下の 3 点を除いて，前節の手続き①～手続き④と同様である．



4
①で観測する環境状態を s から s1 ，s2 に変更する．
②の行動選択では，確率εで，実行可能な全ての行動
の中からランダムに行動を選択し，確率 1-εで，ω
1
(s1t,a)，ω2(s2t,a) の両方の行動決定関数値（10 個）
の中で，値が最大である行動を選択する．
④の行動学習では，ω 1(s1,a)，ω 2(s2,a)の両方の行動
決定関数を式(1)と同様の更新式で更新（学習）する．
実験結果
前章で述べた「従来の profit sharing（PS）」，前章で
提 案 し た 「 タ ス ク 空 間 分 割 を 利 用 し た profit sharing
(PS_dts)」，「従来の Q 学習(Q)」，「タスク空間分割を利
用した Q 学習[4](Q_dts)」の 4 つの強化学習法を上記の追跡
問題に適用し，コンピュータシミュレーション実験を行った．
ここで，実験に使用したパラメータは，PS と PS_dts で
c=0.2，Q と Q_dts で学習率α= 0.2，割引率γ= 0.9 を使用
した．また，PS と Q でε= 0.3×0.99977num_ep（num_ep は学
習エピソード数），PS_dts と Q_dts でε= 0.3×0.99885num_ep
を使用した．また，獲物捕獲時の報酬 r=1.0 とした．
図2
獲物捕獲までに費やした平均時間ステップ数
実験結果を図 2 に示す．図 2 の横軸は学習エピソード数，
縦軸は 1 エピソード中で獲物捕獲までに費やした平均時間ス
テップ数を表す．図 2 の結果は，10 学習エピソード毎に，
そのときまでの学習性能を評価するため，初期配置を変えた
100 評価エピソード（このエピソードでは学習を行わない）
の実験を行い，その平均時間ステップ数を表示したものであ
る．図 2 の Q と PS，Q_dts と PS_dts を比較することにより，
Q 学習より profit sharing の方が学習の収束が速く，収束
値も profit sharing の方が優れていることが分かる．また，
PS と PS_dts（Q と Q_dts）を比較することにより，タスク空
間を学習目的ごとに分割することで，学習が収束するまでの
速度が圧倒的に速くなっていることがわかる．これは学習空
間を大幅に削減できたことが理由であると考えれる．また，
最終的な収束値も，本研究で提案した PS_dts が，他のすべ
ての手法より優れており，提案手法が最も有効な学習法であ
ることがわかる．
５
おわりに
本稿では，複数の学習目的が存在するマルチエージェント
環境において，学習目的ごとにタスク空間を分割して学習を
行う profit sharing に基づく一強化学習法を提案し，その
学習性能の有効性を評価した．コンピュータシミュレーショ
ン実験により，学習目的ごとにタスク空間を分割することで
学習が高速になることがわかった．また，複数の学習目的が
存在するマルチエージェント環境においては，タスク空間を
分割した場合でも，分割しない場合でも，Q 学習よりも
profit sharing の方が学習の収束が速く，収束値も良いこ
とが分かった．
参考文献
[1] 宮崎和光, 小林重信, “離散マルコフ決定過程下での強化
学習”, 人工知能学会誌, Vol.12, No.6, pp.811-821, 1997.
[2] L. Busoniu, R. Babuska and B.D. Schutter, “A
Comprehensive Survey of Multi-Agent Reinforcement
Learning”, IEEE Transactions on Systems, Man, and,
Cybernetics, Part C,vol.38, no.2, pp.156-172, 2008.
[3] S. Whitehead, J. Karlsson and J. Tenenberg, “Learning
Multiple Goal Behavior via Task Decomposition and
Dynamic Policy Merging”, In Robot Learning, Kluwer
Academic Publishers, pp.45-78, 1993.
[4] 橋本佑馬, 長行康男,“多目的タスクにおけるタスク空間分
割を利用したマルチエージェント強化学習”，情報処理学会
創立 50 周年記念（第 72 回）全国大会講演論文集, Vol.2,
pp.437-438, 2010
[5] 荒井幸代, 宮崎和光, 小林重信,“マルチエージェント強化
学習の方法論－Q-Learning と Profit Sharing による接近
－”, 人工知能学会誌, Vol.13, No. 4, pp.609-618, 1998.
2-616
Copyright 2014 Information Processing Society of Japan.
All Rights Reserved.