部分観測マルコフ決定過程のソースを表示

'''部分観測マルコフ決定過程'''(ぶぶんかんそくマルコフけっていかてい、{{lang-en-short|partially observable Markov decision process; POMDP}})は[[マルコフ決定過程|マルコフ決定過程 (MDP)]] の一般化であり、状態を直接観測できないような意思決定過程におけるモデル化の枠組みを与える。

POMDP は実世界におけるあらゆる逐次的な意思決定過程をモデル化するのに十分であり、ロボットのナビゲーションや機械整備 (machine maintenance)、および不確実な状況下でのプランニングなどに応用されている。
POMDP は[[オペレーションズ・リサーチ|オペレーションズリサーチ]]を起源とし、のちに人工知能や[[自動計画]]のコミュニティに引き継がれた。

== 定義 ==
{{See also|マルコフ決定過程#定義}}
POMDP は、マルコフ決定過程に観測を表現するための要素を追加することで定義される{{sfn|Kaelbling|1998}}。
まず、マルコフ決定過程は次に挙げる 4 つの要素の組 <math>(\mathcal{S}, \mathcal{A}, T, R)</math> として定義される。
* <math>\mathcal{S}</math> は環境のもつ状態 (state) の有限集合であり、状態空間 (state space) とも呼ばれる。
* <math>\mathcal{A}</math> は意思決定者の取ることが出来る行動 (action) の有限集合である。
* <math>T \colon \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to [0,1]</math> は状態遷移関数 (state transition function) と呼ばれ、ある行動のもとでの状態遷移確率 <math>T(s_t, a_t, s_{t+1}) = \Pr(s_{t+1} \mid s_t, a_t)</math> を定める。
* <math>R \colon \mathcal{S} \times \mathcal{A} \to \mathbb{R}</math> は報酬関数 (reward function) と呼ばれ、即時報酬の期待値 (expected immediate reward) <math>R(s_t, a_t) = \mathbb{E}[ r_{t+1} \mid s_t, a_t ]</math> を定める。

POMDP は、上に加えて次の 2 つを加えた 6 要素の組 <math>(\mathcal{S}, \mathcal{A}, T, R, \Omega, O)</math> によって定義される。
* <math>\Omega</math> は意思決定者が環境から受け取る可能性のある観測 (observation) の有限集合である。
* <math>O \colon \mathcal{S} \times \mathcal{A} \times \Omega \to [0,1]</math> は観測の条件付き確率分布 <math>O(s_{t+1}, a_t, o_{t+1}) = \Pr(o_{t+1} \mid s_{t+1}, a_t)</math> を定める。

形式的には、POMDP は[[隠れマルコフモデル]]に行動、および（行動を変更する動機を与える）報酬を付与したものと解釈することができる。

== Belief MDP ==
=== 信念状態 ===
MDP とは異なり、POMDP による問題設定では環境の状態を直接取得することが出来ない。
したがって、方策を定めるために意思決定者は自身が過去に取った行動および環境から受け取った観測の履歴をもとに状態を推定する必要がある。
この状態の推定値は一般に状態空間 <math>\mathcal{S}</math> 上の（主観）確率分布で記述され、'''信念状態 (belief state)''' と呼ばれる。
具体的には、ある時刻 <math>t</math> における信念状態 <math>b_t</math> は、初期時点における信念の値 <math>b_0</math> と過去の行動と観測の履歴 <math>\mathcal{H}</math> が与えられたもとでの条件付き確率分布 <math display="inline">b_t(s) = \Pr(S_t = s \mid b_0, \mathcal{H})</math> である。

=== 信念の更新 ===
モデルのマルコフ性により、信念状態は直前における値と、直近に取った行動と観測の値のみから修正することが出来る。
いま、ある時刻 <math>t</math> における信念状態 <math>b_t</math> に対し意思決定者が行動 <math>a_t</math> を選択し、その結果として観測値 <math>o_{t+1}</math> が得られたとする。
このとき、次ステップでの信念状態 <math>b_{t+1}(s_{t+1})</math> の更新式は次のように記述される:
{{NumBlk||<math display="block">
\begin{align}
  b_{t+1}(s_{t+1})
    &= \frac{\Pr(o_{t+1} \mid b_t, a_t, s_{t+1}) \times \Pr(s_{t+1} \mid b_t, a_t)}{\Pr(o_{t+1} \mid b_t, a_t)} \\
    &= \eta \cdot O(s_{t+1}, a_t, o_{t+1}) \sum_{s \in \mathcal{S}} T(s_t, a_t, s_{t+1}) b_t(s_t)
\end{align}
</math>|{{EquationRef|1}}}}
ここで <math>\eta = 1 / \Pr(o_{t+1} \mid a_t, b_t)</math> は正規化定数である。確率 <math>\Pr(o_{t+1} \mid a_t, b_t)</math> は次式で与えられる。
<math display="block">
  \Pr(o_{t+1} \mid b_t a_t) = \sum_{s' \in \mathcal S} O(s_{t+1}, a_t, o_{t+1}) \sum_{s \in \mathcal S} T(s, a, s) b_t(s)
</math>

=== Belief MDP の定式化 ===
式 ({{EquationNote|1}}) は現在取る行動 <math>a_t</math> と得られる観測 <math>o_{t+1}</math> が既知の場合における信念状態 <math>b_t</math> から <math>b_{t+1}</math> への（決定論的な）遷移関係と解釈することが出来る。
すなわち、信念状態を介することで POMDP を（部分観測でない）マルコフ決定過程として扱うことが出来る。
このようにして構成される MDP のことを '''belief MDP''' と呼ぶ。
形式的には、belief MDP は次の要素からなる組 <math>(\mathcal{B}, \mathcal{A}, \tau, r)</math> として定義される:
* <math display="inline">\mathcal{B} = \{ b \colon S \to [0,1] \mid \sum_{s \in \mathcal{S}} b(s) = 1 \}</math> : 信念状態が取り得る値の集合
* <math>\mathcal{A}</math> : belief MDP における行動集合（元々の POMDP と共通）
* <math>\tau \colon \mathcal{B} \times \mathcal{A} \times \mathcal{B} \to [0,1]</math> : 信念状態空間における状態遷移確率
* <math>r \colon \mathcal{B} \times \mathcal{A} \to \mathbb{R}</math> : 信念状態空間における報酬関数
ここで <math>\tau</math> および <math>r</math> はそれぞれ次のように求められる。
<math display="block">
\begin{align}
  \tau(b_t, a_t, b_{t+1})
    &= \sum_{o_{t+1} \in \Omega} \Pr(b_{t+1} \mid b_t, a_t, o_{t+1}) \Pr(o_{t+1} \mid b_t, a_t) \\
  r(b_t, a_t)
    &= \sum_{s_t \in \mathcal{S}} b_t(s_t) R(s_t, a_t) \\
\end{align}
</math>
ただし、<math>\Pr(b_{t+1} \mid b_t, a_t, o_{t+1})</math> は <math>b_{t+1}</math> が <math>b_t,a_t,o_{t+1}</math> をもとに式 ({{EquationNote|1}}) によって得られる値の場合 1 を、それ以外のとき 0 を取るように定められる。

=== 方策関数・価値関数 ===
任意の信念 <math>b</math> に対する特定の行動 <math>a = \pi(b)</math> を<math>\pi</math> と表す。
ここで目的関数は無限ホライズンの期待割引報酬和 (expected total discounted reward) と仮定する。<math>R</math> がコストとして定義される場合、目的関数は期待コストの最小化となる。

信念の初期値を <math>b_0</math> としたときの方策 <math>\pi</math> に対する期待報酬 (expected reward) は次のように定義される:
<math display="block">
  V^\pi(b_0) = \sum_{t=0}^\infty  \gamma^t r(b_t, a_t) = \sum_{t=0}^\infty \gamma^t E\Bigl[ R(s_t,a_t) \mid b_0, \pi \Bigr]
</math>
ここで <math>\gamma<1</math> は割引因子である。
最適な方策 <math>\pi^*</math>は長期的な報酬の最適化により次のように得られる:

<math display="block">
  \pi^* = \underset{\pi}{\mbox{argmax}}\ V^\pi(b_0)
</math>

ここで <math>b_0</math> は初期信念である。

最適方策 (optimal policy) は <math>\pi^*</math> で表され、任意の信念状態において期待報酬の最大値（最適価値関数 (optimal value function) <math>V^*</math> で表す）を与える。
価値関数は[[ベルマン方程式|ベルマンの最適性方程式]]の解である:

<math display="block">
  V^*(b) = \max_{a\in A}\Bigl[ r(b,a) + \gamma\sum_{o\in \Omega} O(o\mid b,a) V^*(\tau(b,a,o)) \Bigr]
</math>

有限ホライズンの POMDP では、最適な価値関数は凸な区分線形関数となる{{sfn|Sondik|1971}} 。
これは有限個のベクトルの集合で表現することが出来る。
無限ホライズンでは、有限次元ベクトルを用いることで凸性を維持するよう任意に綿密に <math>V^*</math> を近似することができる{{sfn|Sondik|1973}}。

価値反復法は動的計画法を用いて、区分線形性と収束性は区分線形性と凸性を維持しながら、収束するまで価値関数の値を更新する。
価値関数の値を更新することで、方策は改善される。
もう一つの動的計画法に基づくテクニックは方策反復法と呼ばれ、これは方策を明示的に更新する{{sfn|Sondik|1978}}{{sfn|Hansen|1998}}。

== POMDP の近似解法 ==
[[組合せ爆発|組み合わせ爆発]]の問題をはらむため、POMDP の厳密解を求めることは実用上困難であることが多い。
そのため、POMDP の解を近似する手法が複数提案されている{{sfn|Hauskrecht|2000a}}。
グリッドベースのアルゴリズム{{sfn|Lovejoy|1991}}では価値関数を信念空間内の点集合として計算し、最適行動を決定するための計算など、グリッドの点集合に含まれない信念状態の値が必要な場合は補完する。
より最近の研究では、サンプリングや一般化 (genelization technique)、および問題の構造を利用する手法などが用いられ、膨大な状態を伴うより大きい領域を扱うよう POMDP を拡張する{{sfn|Hoey|2007}}{{sfn|Hoey|2010}}。
例えば、点ベースの手法では、信念空間において関連する領域への計画を拘束するため、到達可能な信念をランダムにサンプルする{{sfn|Pineau|2003}}。
主成分分析を用いた次元削減も調べられている{{sfn|Roy|2003}}。

== POMDP の応用 ==
POMDP は実世界の多くの種類の問題に用いることが出来る。
注目すべき応用には、虚血性心疾患の患者の特別療法に対する POMDP の活用{{sfn|Hauskrecht|2000b}}、痴呆患者の支援技術{{sfn|Hoey|2010}}、
絶滅の危機に瀕し発見の難しいスマトラトラの保護{{sfn|Chadès|2008}}、および航空機の衝突回避が含まれる{{sfn|Kochenderfer|2015}}。

== 参考文献 ==
{{reflist hide}}
{{refbegin|2}}

* {{cite journal
    |doi=10.1016/S0004-3702(98)00023-X
    |author1=Kaelbling, L.P.
    |author2=Littman, M.L.
    |author3=Cassandra, A.R.
    |title=Planning and acting in partially observable stochastic domains
    |journal=Artificial Intelligence Journal
    |volume=101
    |pages=99–134
    |year=1998}}

* {{cite thesis
    |degree=PhD
    |title=The optimal control of partially observable Markov processes
    |last=Sondik
    |first=E.J.
    |year=1971
    |publisher=Stanford University }}

* {{cite journal
    |doi=10.1287/opre.21.5.1071
    |author1=Smallwood, R.D.
    |author2=Sondik, E.J.
    |title=The optimal control of partially observable Markov decision processes over a finite horizon
    |journal=Operations Research
    |volume=21
    |issue=5
    |pages=1071–88
    |year=1973 }}

* {{cite journal
    |doi=10.1287/opre.26.2.282
    |author=Sondik, E.J.
    |title=The optimal control of partially observable Markov processes over the infinite horizon: discounted cost
    |journal=Operations Research
    |volume=26
    |issue=2
    |pages=282–304
    |year=1978 }}

* {{cite conference
    |book-title=Proceedings of the Fourteenth International Conference on Uncertainty In Artificial Intelligence (UAI-98)
    |title=Solving POMDPs by searching in policy space
    |author=Hansen, E.
    |year=1998 }}

* {{cite journal
    |doi=10.1613/jair.678
    |author=Hauskrecht, M.
    |title=Value function approximations for partially observable Markov decision processes
    |journal=Journal of Artificial Intelligence Research
    |volume=13
    |pages=33–94
    |year=2000a}}

* {{cite journal
    |doi=10.1287/opre.39.1.162
    |author=Lovejoy, W.
    |title=Computationally feasible bounds for partially observed Markov decision processes
    |journal=Operations Research
    |volume=39
    |pages=162–175
    |year=1991 }}

* {{cite conference
    |title=Assisting Persons with Dementia during Handwashing Using a Partially Observable Markov Decision Process
    |author1=Jesse Hoey
    |author2=Axel von Bertoldi
    |author3=Pascal Poupart
    |author4=Alex Mihailidis
    |book-title=Proc. International Conference on Computer Vision Systems (ICVS)
    |date=2007
    |doi=10.2390/biecoll-icvs2007-89}}

* {{cite journal
    |doi=10.1016/j.cviu.2009.06.008
    |title=Automated Handwashing Assistance For Persons With Dementia Using Video and a Partially Observable Markov Decision Process
    |author1=Jesse Hoey
    |author2=Pascal Poupart
    |author3=Axel von Bertoldi
    |author4=Tammy Craig
    |author5=Craig Boutilier
    |author6=Alex Mihailidis.
    |journal=Computer Vision and Image Understanding (CVIU)
    |volume=114
    |number=5
    | year=2010}}

* {{cite conference
    |title=Point-based value iteration: An anytime algorithm for POMDPs
    |author=Pineau, J., Gordon, G., Thrun, S.
    |book-title=International Joint Conference on Artificial Intelligence (IJCAI). Acapulco, Mexico
    |date=August 2003 |pages=1025–32 }}

* {{cite book
    |author1=Roy, Nicholas
    |author2=Gordon, Geoffrey
    |chapter=Exponential Family PCA for Belief Compression in POMDPs
    |title=Advances in Neural Information Processing Systems
    |year=2003 }}

* {{cite journal
    |author=Hauskrecht, M. , Fraser, H.
    |year=2000b
    |title=Planning treatment of ischemic heart disease with partially observable Markov decision processes
    |journal=Artificial Intelligence in Medicine
    |volume=18
    |issue=3
    |pages=221–244
    |doi=10.1016/S0933-3657(99)00042-1}}

* {{cite journal
    |author=Chadès, I., McDonald-Madden, E., McCarthy, M.A., Wintle, B., Linkie, M., Possingham, H.P.
    |date=16 September 2008
    |title=When to stop managing or surveying cryptic threatened species
    |url=http://www.pnas.org/content/105/37/13936.abstract|journal=Proc. Natl. Acad. Sci. U.S.A.
    |volume=105
    |issue=37
    |pages=13936–40
    |bibcode=2008PNAS..10513936C
    |pmid=18779594
    |pmc=2544557
    |doi=10.1073/pnas.0805265105}}

* {{cite book
    |author=Kochenderfer, Mykel J.
    |title=Decision Making Under Uncertainty
    |year=2015
    |publisher=The MIT Press
    |chapter=Optimized Airborne Collision Avoidance}}
{{refend}}

== 外部リンク ==
* [http://www.cassandra.org/pomdp/index.shtml Tony Cassandra's POMDP pages] with a tutorial, examples of problems modeled as POMDPs, and software for solving them.
* [http://www.cs.cmu.edu/~trey/zmdp/ zmdp], a POMDP solver by Trey Smith
* [http://bigbird.comp.nus.edu.sg/pmwiki/farm/appl/index.php?n=Main.HomePage APPL], a fast point-based POMDP solver
* [http://www.cs.uwaterloo.ca/~jhoey/research/spudd/ SPUDD], a factored structured (PO)MDP solver that uses algebraic decision diagrams (ADDs).
* [http://bitbucket.org/bami/pypomdp pyPOMDP], a (PO)MDP toolbox (simulator, solver, learner, file reader) for Python by Oliver Stollmann and Bastian Migge
* [http://www.cs.uwaterloo.ca/~mgrzes/code/IsoFreeBB/ Finite-state Controllers using Branch-and-Bound] An Exact POMDP Solver for Policies of a Bounded Size

{{確率論}}
{{デフォルトソート:ふふんかんそくまるこふけつていかてい}}
{{Computer-stub}}
[[Category:理論計算機科学]]
[[Category:確率過程]]
[[Category:機械学習]]
[[Category:数学に関する記事]]