マルチエージェント強化学習による協調性獲得の検証 ―追跡問題を例として― 理学研究科博士前期課程 2年本田研究室櫻井祐輔研究の背景 • 近年，ネットワークやシステムの大規模化・複雑化が進んでいる • それに伴い，分散処理・並列処理という観点からマルチエージェントシステムの応用が期待されている 2 マルチエージェント(システム)とは • 複数の自律的に行動するエージェントで構成されるシステム • エージェントが互いに協調しあうことで，問題解決能力の向上や処理の高速化が望める • 扱う問題が複雑になるほど協調動作の実装が難しい実装方法として強化学習が有効な手段強化学習(Reinforcement Learning) • 強化学習とは – 試行錯誤を繰り返すことで環境に適応していく学習法 – 報酬を頼りに行動戦略を改善することで学習環境E 状態s 行動a 報酬r 環境E 状態s’ 報酬r’ 行動a’ ・・・ Agent(戦略A) Agent(戦略A’) 目標強化学習の問題点 • 学習結果が関数など人間にとって理解しにくい形をしている • マルチエージェント問題で得られた行動の協調性の検討が必要本研究の目的 • マルチエージェント問題に対する強化学習の効果を協調性に着目して評価する – 追跡問題を例に – 捕獲直前の状態に対してエージェントが獲得した行動を抽出し，協調性を評価 • 異なる学習アルゴリズムによる協調動作の獲得傾向の違いを見る – Q-LearningとProfit Sharingを使用 Q-Learningの学習アルゴリズム Q値と呼ばれる行動価値関数Q（s,a）を逐次更新する [Watkins,1992] Q値の更新式： Q ( s t , a t ) ← Q ( s t , a t ) + α[ rｔ＋１ + γmax Q ( s t + 1 , a ) － Q ( s t , a t )] a α=1 rt + 1 αの割合で近づける未来の報酬の近似値 α=0 α : 学習率 , γ ：割引率（いずれも遷移先の状態で最大の γ maxQ( st +1 , a) a Q ( st , a t ) 状態 s t at 他の選択可能な行動 [ 0 ,1 ]） max Q( s t +1 , a) a 状態 s t +1 報酬 rt + 1 Q値を推定 a = arg max Q( st +1 , a ) a 他の選択可能な行動 Q(λ)の学習アルゴリズム Q-Learningに適格度トレースを組み合わせた手法 Q値の更新式： Q( st , at ) ← Q( st , at ) +α[rｔ＋１ +γmaxQ( st +1 , a ) － Q( st , at )] a 強化値をγλ(0≦λ≦1)で減衰しながら過去の全てのQ値を一括強化強化量 Q t−3 Q（λ） ( γ λ) 3 倍 t−3 t−2 t −1 (γ λ) 2 倍 t−2 t λの値が大きいほど時刻過去への伝播量が大きくより遠くの過去へ伝播 t +1 γ λ倍 t −1 時刻 t t +1 Profit Sharingの学習アルゴリズム報酬を獲得した時に全てのルールの重みを一括強化 [Grefenstette,88] z x x a y ルール xa yb zb xa ya ルールの重み F ( xa ) F ( yb) F (zb ) F ( xa ) F ( ya ) 状態行動 b b f f 3 f f f 0 R 強化値 1 fi = f i − 1 , i = 1, 2 ,..., W − 1 . f 0 = R [宮崎 94] M M : 行動数 W : 報酬獲得までのステップ数 y a a 報酬 1 2 4 時間追跡問題 • ハンター（hunter）が獲物（target）を追跡・捕獲する問題 2 l × l のグリッド環境（ l = 15 ）辺で隣接したら捕獲行動 = ｛上，下，左，右，停滞｝視野：｛周囲8方向＋視野外｝の9通り対獲物の視野：周囲7マス対ハンターの視野：周囲1マス 1 ■：ハンター，■：獲物獲物ともう一方のハンターの位置の組み合わせ81通りの状態を知覚実験条件項目内容問題追跡問題(ハンター数2，獲物の数1) 学習アルゴリズム Q(λ)，λ=0，0.5，0.9 Profit Sharing 報酬 Q(λ)：捕獲時に0，それ以外は-1 Profit Sharing：捕獲時に100 試行回数 100回学習結果の例1 学習結果の例2 獲得した協調動作の例獲得した協調動作の例獲物を右側に各ハンターと獲物が横一直線に並んだ状態を例に 2 譲り合い待ち伏せ挟み撃ち追従 1 ■：ハンター，■：獲物各動作の獲得率(%) 赤：譲り合い緑：待ち伏せ黄色：挟み撃ち水色：追従譲り合いの獲得率が最も高く追従の獲得率がもっとも低い協調動作全体の獲得率 100 各行動対の獲得率(%) 90 挟み撃ち 80 70 待ち伏せ 60 50 40 追従 30 20 譲り合い 10 0 Q(0) Q(0.5) Q(0.9) 学習アルゴリズム Profit Sharing 捕獲ステップ数との比較学習アルゴリズム協調行動獲得率(%) 捕獲までのステップ数 Q(0) 61 377 Q(0.5) 70 46 Q(0.9) 52 72 Profit Sharing 89 47 強化値伝播のモデル 1.2 1 強化値 0.8 0.6 Profit Sharing Q(0.9) 0.4 Q(0.5) 0.2 Q(0) 0 T-4 T-3 T-2 時刻 T-1 T 結論と今後の課題結論 • マルチエージェント問題に強化学習を実装することで協調性は獲得できる。 • Profit Sharingが最も適した学習アルゴリズムであり，Q-Learningはパラメータ設定に工夫が必要。今後の課題 • より複雑な問題での協調動作の検証 • 得られた学習結果から汎用的ルールの抽出 – 決定木を用いて構造的なルールの生成以上で発表を終わります。ご清聴ありがとうございました。リファレンス • 強化学習： Richard S.Sutton and Andrew G.Barto，三上貞芳・皆川雅章共訳（森北出版，2000） • 電気通信大学情報通信工学科/専攻情報メディア工学講座人間コミュニケーション学専攻メディアコミュニケーション学講座 HP • マルチエージェント（協調）問題の調査：藤田佳久，三木光範，廣安知之(ISDL Report No.20040802004 ) • [内海06]：マルチエージェント強化学習におけるProfit Sharingの有効性検証～追跡問題を例に～，高知大学理学部数理情報科学科卒業論文 • [櫻井05] 強化学習によるエージェント形成と決定木による評価～追跡問題を例に～，高知大学理学部数理情報科学科卒業論文 • [黄04]：強化学習による学習エージェントの構成，高知大学理学部数理情報科学科卒業論文実験結果2（Profit Sharingの結果）ターゲットを右側に各ハンターとターゲットが横一直線に並んだ状態想定される位置関係 h1とh2の行動の組み合わせの獲得回数 PS h1 の行動 2 1 U 2 1 ●：hunter gent ▲：target U D 2 L R S U:上 2 1 0 D:下 5 2 0 0 L:左 0 2 0 0 h２ D の行 L 動 R 3 6 1 S 2 3 1 R:右 S:停滞 0 学習の流れ • 基本的な強化学習ゴール状態 (目標)を設定始状態と報酬の計測行動価値の更新終行動 a の選択方策(行動戦略)に基づき選択する学習の流れを物語に例え、エピソードと呼ぶ行動 a の実行間接報酬の与え方 • 間接報酬による解の劣化を避けるために協力 – 報酬 R を割り引いた値を間接報酬として与える – μ Rはマルチエージェント系におけるProfit Sharingの合理性定理[宮崎他99]を満たす以下の値とする μ< (M W エージェントエージェントゴール（目標）エージェントエージェント報酬直接報酬間接報酬 1 M : 行動の選択肢の数 − 1)( n − 1) W : エピソードの長さ n : エージェントの個数強化学習に決定木を組み合わせる追跡問題Ａｇｅｎｔ1 強化学習環境Ａｇｅｎｔ2 •人間にとって分かりやすい形 •汎用性の確保(環境が変化しても再学習の必要なし) 決定木学習構造化された if,thenルールの作成決定木学習属性１ • 決定木とはデータ項目間の関係を木構造で表示する分析手法（葉：ラベル根、節：属性） YES NO 属性2 ラベル3 YES NO ラベル１ラベル2 状態と行動から決定木を学習状態属性決定木化強化学習行動ラベル構造化されたif,thenルール Profit Sharingの学習アルゴリズムエピソード（長さW）迂回系列 z x x a y ルール xa yb zb xa ya ルールの重み F ( xa ) F ( yb) F (zb ) F ( xa ) F ( ya ) 状態行動 b b a y a 報酬 R 実験結果協調性が必要とされる状態を抽出し獲得された行動の比較ターゲットを右側に各ハンターとターゲットが一直線に並んだ状態を例に Profit Sharing Q学習 2 1 Q 学習 h ２の行動 2 1 h1 の行動 PS U D L R S U 1 1 2 0 D 1 0 2 1 L 1 1 2 1 R 3 5 6 S 0 1 2 0 h1 の行動 U D L R S h ２の行動 U:上 D:下 U 2 2 1 0 D 5 2 0 0 L 0 2 0 0 R:右 R 3 6 1 S:停滞 S 2 3 1 0 L:左 Q学習はh1が右に動く傾向が強い Profit Sharingはh1が上か下に動くと傾向が強い ●：hunter gent ▲：target Profit Sharingは捕獲に近い状態に対しより強い影響を受けるためだと考えられる