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

Mon Oct 24 10:36:51 JST 2016 (modified: Fri Nov 29 17:22:47 JST 2019)
views: 823, 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で記述すると、数値計算を行うことができる
• ただし、いろいろ面倒なこともある
  • どうやって状態を離散化するか
  • 数値計算の計算量を現実的なレベルに抑えるにはどうするべきか