CIT自律ロボット研究室

千葉工業大学 先進工学部 未来ロボティクス学科 上田隆一研究室

お知らせ: 本研究室所属の3年生チームがAWS Robot Delivery Challengeで優勝しました / 

確率ロボティクス2016第5回

Mon Oct 24 10:36:51 JST 2016 (modified: Fri Nov 29 17:22:47 JST 2019)
views: 125, keywords:

  このエントリーをはてなブックマークに追加 
   

確率ロボティクス

第5/6回

上田 隆一

2016年10月26日\@千葉工業大学

本日の内容

  • 有限マルコフ決定過程

有限マルコフ決定過程

  • finite Markov decision processes (finite MDPs)
  •  ロボットの行動を考えるときによく使う
    • 何が「最適」なのか?
    • 最適にするにはロボットがどうすべきか?
  • 昔ながらの(今も使われる)経路計画の定式化も有限MDPの部分問題

有限MDPの考え方

  • ロボット(環境)の状態は制御出力により遷移
    • これまでの話と同じ
    • 雑音が伴う
  • 状態をエージェントは観察できる
    • これまでとは違う
  • 「こういう状態になったら終わり」という状態が存在
    • 「終端状態」 
      • 移動ロボットが目的地に入った状態
      • ロボットが川に落ちた
  • 状態遷移にはコストやペナルティーが伴う
    • コスト: 時間、電力消費、燃料消費等
    • ペナルティー: ルール違反、危険な行為に対して

定式化(状態と行動)

  • 状態
    •  離散状態の集合を考える
      • [latex]\\mathcal{S}= \\{s^{(i)} | i=1,2,\\dots,N \\}[/latex]
      • 状態が連続の場合は離散化
        • [latex]\\mathcal{X}[/latex]を区切る
    • 終端状態
      • [latex]s_\\text{f} \\in \\mathcal{S}_\\text{f} \\subset \\mathcal{S}[/latex]
      • この状態に到達するとそれ以上時間が進まない
        • タスクの終わり
  • 制御出力(行動)
    • 有限個の行動の集合から選択
      • [latex]\\mathcal{A} = \\{ a^{(j)} | j = 1,2,\\dots,M \\}[/latex]
      • 連続系の[latex]\\mathcal{U}[/latex]から何種類か選んで有限個に
  • この資料では[latex]s_i,a_j[/latex]と書くときは時刻を表すことにします

定式化(状態遷移)

  • 状態遷移
    • [latex]s' \\sim P(s' | s,a)[/latex]
      • [latex]s,s'[/latex]はそれぞれ遷移前、遷移後の状態を示す
    • [latex]P(s' | s,a)[/latex]を[latex]\\mathcal{P}^a_{ss'}[/latex]と表記しましょう
      • [latex]s \\in \\mathcal{S} - \\mathcal{S}_\\text{f}[/latex]から[latex]a \\in \\mathcal{A}[/latex]を選択した時、[latex]s' \\in \\mathcal{S}[/latex]に遷移する確率

定式化(状態遷移の評価)

  • 状態遷移の評価
    • [latex]R(s,a,s') \\in \\Re[/latex]
      • 評価は常に実数で行われる
      • 時刻に依存しないと仮定しましょう
  • 評価軸がいくつあっても実数に置き換えて一元化
    • 例: 移動ロボットが水たまりを踏んだら1回につき3分のペナルティー、等
  • [latex]R(s,a,s')[/latex]を[latex]\\mathcal{R}^a_{ss'}[/latex]と表記

定式化(終端状態の評価)

  • どの終端状態に行くかも評価の対象
  • 終端状態の価値
    • [latex]V(s)\\in \\Re[/latex] where [latex]\\forall s \\in \\mathcal{S}_\\text{f}[/latex]
    • この値も[latex]\\mathcal{R}^a_{ss'}[/latex]と同じ評価軸の上にある

行動の評価

  • ある状態からスタートして、ある終端状態に入った時の評価の和
  • 状態遷移と行動が[latex]s_0,a_1,s_1,a_2,\\dots,s_T[/latex]だったときの評価:
    • [latex]J(s_{0:T},a_{1:T})[/latex] [latex] = \\mathcal{R}^{a_1}_{s_0s_1} +\\mathcal{R}^{a_2}_{s_1s_2} +\\mathcal{R}^{a_3}_{s_2s_3} + \\dots +\\mathcal{R}^{a_T}_{s_{T-1}s_T} + V(s_T)[/latex] [latex] = \\sum_{t=1}^T \\mathcal{R}^{a_t}_{s_{t-1}s_t} + V(s_T)  [/latex]
    • [latex]J(s_{0:T},a_{1:T})[/latex]は毎回違う
      • [latex]\\mathcal{P}^a_{ss'}[/latex]で、事後の状態[latex]s'[/latex]がばらつく

有限MDPでの最適な行動

  • [latex]J(s_{0:T},a_{1:T})[/latex]の期待値が最大になる行動決定則
    • 毎回、事後状態がばらつくのにどうやって求めるの?
    • 結構難しい
      • 識別の問題なら判断は1回
      • 行動決定の場合は終端状態に至るまで何度も判断

状態のマルコフ性と最適性の原理

  • これまでなんとなく仮定してきた
  • [latex]\\mathcal{P}^a_{ss'}[/latex]が過去に依存しないこと
    • 違う時刻に同じ状態に来たら、同じ行動をとれば同じ確率分布で次の状態に遷移する
  • これが成り立つと・・・
    • ある試行の状態遷移[latex]s_0,s_1,s_2,\\dots,s_N[/latex]のうち、どこを初期状態にしても、[latex]J(s_{0:T},a_{1:T})[/latex]の期待値を最大にする問題は、同じ問題になる。

状態の価値

  • [latex]J(s_{0:T},a_{1:T})[/latex]の期待値の最大値を考えてみる
  • 先ほどの議論から、[latex]J(s_{0:T},a_{1:T})[/latex]の期待値の最大値が存在すると仮定すると、初期状態だろうがなかろうが、ある状態[latex]s[/latex]から先の行動決定を考えると、この期待値の最大値が存在するし、それは、その状態[latex]s[/latex]の関数となる
  • これをその状態の(エージェントが最適な行動を取った時の)「価値」と言う
  • 終端状態の価値[latex]V(s) ( s \\in \\mathcal{S}_\\text{f})[/latex]を拡張して、状態空間全体の関数: [latex]V^*: \\mathcal{S} \\to \\Re[/latex]とする
    • [latex]V^*[/latex]: 最適状態価値関数

価値の性質 (ベルマン方程式

  • [latex]V^* (s) = \\max_{a\\in\\mathcal{A}} \\sum_{s' \\in \\mathcal{S}} \\mathcal{P}_{ss'}^a \\left[ V^*(s') + \\mathcal{R}_{ss'}^a \\right] [/latex]
    • もし最適状態価値関数が存在するなら、ある状態[latex]\\forall s \\in \\mathcal{S}-\\mathcal{S}_\\text{f}[/latex]の値[latex]V^*(s)[/latex]は、以下の値を最大にする行動[latex]a \\in \\mathcal{A}[/latex]を選んだ時の値になる
      • [latex]s[/latex]から遷移した先の値[latex]V^*(s')[/latex]と、その状態遷移に対する評価[latex]\\mathcal{R}_{ss'}^a[/latex]を足した値を考える。遷移先は確率的にばらつくので、この値について[latex]\\mathcal{P}_{ss'}^a[/latex]で重み付き平均を求めたもの。

  • ・・・黒板で

価値の計算(価値反復)

  • ある状態[latex]s[/latex]の[latex]V^*(s)[/latex]だけ分からない。あとの状態の[latex]V^*[/latex]の値は分かるという、都合の良い状況を考えてみましょう。
    • 価値の計算式はベルマン方程式そのものとなる
      • [latex]V^* (s) =\\max_{a\\in\\mathcal{A}} \\sum_{s' \\in \\mathcal{S}} \\mathcal{P}_{ss'}^a \\left[ V^*(s') + \\mathcal{R}_{ss'}^a \\right] [/latex]
  • 価値反復アルゴリズム
    • この計算を[latex]\\forall s \\in \\mathcal{S} - \\mathcal{S}_\\text{f}[/latex]に対して何度も計算していく
      • (状態を適切に設定すると)終端状態に(遷移数という意味で)近い状態から[latex]V^* (s)[/latex]の値が収束していく

最適方策

  • 最適状態価値関数が分かっていると、ベルマン方程式を成立させるための行動が求まる
  • 最適な行動: [latex]\\text{argmax}_a \\sum_{s' \\in \\mathcal{S}} \\mathcal{P}_{ss'}^a \\left[ V^*(s') + \\mathcal{R}_{ss'}^a \\right] [/latex]
  • 「最適方策」という関数: [latex]\\qquad\\qquad\\pi^*: \\mathcal{S}-\\mathcal{S}_\\text{f} \\to \\mathcal{A}[/latex] を考える
  • 最適方策は状態と行動を対にしたリストとなる
    • 時刻は全く関係ない
    • [latex]\\pi^*[/latex]を知っているロボットは、置き直されたりタスクを妨害されたりしても、その後に自身の状態を知覚できれば、最適な行動をとることが可能

古典的な定式化との比較

  • 経路計画問題を有限MDPで記述すると、確率的な遷移や途中の行動でのペナルティーや報酬を扱える
  • 解析的な軌道生成の問題を有限MDPで記述すると、数値計算を行うことができる
  • ただし、いろいろ面倒なこともある
    • どうやって状態を離散化するか
    • 数値計算の計算量を現実的なレベルに抑えるにはどうするべきか