第6章：確率的最短路問題 - 動的
章の概要
第5章では、リンクの動的に変化する移動時間について何も知らないか、あるいは旅行者がいる交差点に接続されたリンクの時間のみを観測できる(それより先の将来の情報は得られない)という前提のもとで、最短経路問題を提起した。
ここで、我々がGoogleマップのようなサービスであり、ネットワーク全体にわたるリアルタイム情報にアクセスできると想像してみよう。さらに、この情報はリアルタイムで更新されており、Googleは旅行者の目的地までの推奨経路を更新し続けている。この情報は、モデルに大きな変化をもたらし、第5章で示した手法を用いる可能性を完全に排除してしまう。
この問題に対して我々が用いるアプローチは、不確実な値についていわゆる「最良推定値」を用いて将来を計画することで解くあらゆる問題に適用できる。これは、我々が直接先読み近似と呼ぶ第4のクラスの方策を初めて使用する場面を提供する。我々はこの設定を用いて、決定論的な先読みモデルから出発し、不確実性のもとで時間とともにより良く機能するようにパラメータを導入していくという、動的な設定(すなわち不確実性下)で決定を下すための実践的かつ強力な手法を示す。
ナラティブ
我々は再び確率的最短経路問題に取り組むが、今回はGoogleマップ(あるいは任意の商用ナビゲーションシステム)で行われているのと同じように取り組む。交通ネットワークには、しばしば予測可能な渋滞パターンと、日常の自然な出来事の中で生じるランダムな変動の両方が存在することは、誰もが認識するところである。例えば、事故が発生すると滞留が生じ、我々はその事故の結果として移動遅延がどのように進展するかを推定するかもしれない。
静的な最短経路問題からの出発点は、将来のコストに関する我々の推定値が時間とともに変化していくという点である。我々は、コストが確率的である問題に立ち戻るが、ノード$i$に到達したとき、ノード$i$からのコストの実際の実現値を見ることはできない。しかし、ネットワーク全体にわたるコストの更新された推定値が与えられると仮定する。これらの推定値は予測とみなすことができる。すなわち、あるアークを通過する際に実際にかかるコストは、平均としてはその予測に等しい(つまり予測に偏りはない)が、これらの予測はネットワークの状況に関する更新情報を得るにつれて時間とともに変化していくと仮定する。
問題の枠組み
3つの枠組み設定の質問に対する答えは以下の通りである。
- メトリクス: 我々は期待移動時間を最小化したい。ここで、目標到着時刻より後に到着した場合のペナルティも含めてよい。
- 決定: ノード$i$にいる旅行者に対し、次にどのノード$j$へ移動すべきかを教えたい。
- 不確実性: 推定移動時間は、旅行者が下流ノードへのリンクを通過するたびにランダムに変化する。リンクを通過する際の実際の時間は、推定値とは異なる。
基本モデル
時刻$t$において決定を下さなければならないとき、我々は(スマートフォンが交通の中をどのくらいの速さで移動しているかを追跡することで)現在の渋滞レベルに基づく移動コストの更新された推定値を持っていると仮定する。これらの時間を、時刻$t$における知識に基づく推定値を用いて、時刻$t$におけるリンク$(k,\ell)$を通過する推定コストである$\cbar_{tk\ell}$を用いて表すことにする。
ここでは、時刻$t$における知識のもとで、時点$t’ > t$に到達した場合のコストをモデル化しようとはしない。したがって、午後3時に、あるリンクに午後5時に到達すると推定するかもしれないが、我々は(現在のGoogleがそうしているように)午後3時時点の推定値を使用する。
状態変数
時刻$t$にノード$N_t = i$にいる旅行者は、予測の集合$\cbar_{t} = (\cbar_{ttk\ell})_{k, \ell \in \Ncal}$、すなわち時刻$t$に既知の情報のもとでの時刻$t$におけるリンク$(k, \ell)$の通過コストの推定値のベクトルが与えられていると仮定する。時刻$t$における旅行者の状態$S_t$は、次のようになる
\[S_t = (N_t, \cbar_t).\]この状態変数は非常に大きいことに注意されたい。それは、ネットワーク内のすべてのリンクに対するリンクコストの推定値のベクトルから構成される。
決定変数
決定変数は、静的な確率的最短経路問題と同じである
\[x_{tij} = \begin{cases} 1 & \text{if we traverse link } i \text{ to } j \text{ when we are at } i \text{ at time } t, \\ 0 & \text{otherwise.} \end{cases}\]この決定は、状態$N_t = i$にあるとき、$i$が目的地でない限り何らかの行動をとるという制約に従わなければならない。この制約は次のように書ける
\[\begin{align} \sum_j x_{t,i,j} = 1 \quad \text{for } N_t = i \text{ other than the destination.} \label{dynamicshorestpathconstraint} \end{align}\]目的地にいる場合は何もしないので、$i$が目的地に等しいときは$x_{tij} = 0$、$i$がその他のノード$j$のときは別の式となる。
上と同様に、$X^\pi(S_t)$を、制約$\eqref{dynamicshorestpathconstraint}$を満たさなければならないベクトル$x_t$を決定するための我々の方策とする。
外生情報
この問題には2種類の外生情報がある。1つ目は観測されたコストである:$\chat_{t+1,ij}$、すなわち旅行者が時刻$t$にこのリンクを通過するという決定を下した後の、リンク$(i,j)$を通過する実際のコストである。旅行者がリンク$(i,j)$を通過した場合にのみ$\chat_{t+1,ij}$を観測することに注意されたい(通過しないリンクについては単に0を挿入すればよい。これらの値は使用しないためである)。
2つ目の新しい情報の種類は、リンクコストの推定値$\cbar_t$の更新である。我々は外生情報を推定値の変化としてモデル化する:
\[\delta \cbar_{t+1,k\ell} = \begin{cases} \cbar_{t+1,k\ell} - \cbar_{tk\ell} & \text{if } x_{tk\ell}=1, \\ 0 & \text{otherwise.} \end{cases}\] \[\delta \cbar_{t+1} = (\delta \cbar_{t+1,k\ell})_{(k,\ell)\in\Ncal}.\]したがって、我々の外生情報変数は次のように与えられる
\[W_{t+1} = (\chat_{t+1}, \delta \cbar_{t+1}).\]遷移関数
$\chat_{t+1}$は外生情報として到着すると仮定する(コストの変化を外生情報とすることもできたが、こちらの方がより自然である)。
予測に対する遷移関数は次のように発展する
\[\begin{align} \cbar_{t+1,k\ell} = \cbar_{tk\ell} + \delta \cbar_{t+1,k\ell}. \label{eq:shortestpathdynamictransition1} \end{align}\]最後に、次式を用いて物理状態$N_t$を更新する
\[\begin{align} N_{t+1} = \{j\vert x_{t,N_t,j} = 1\}. \label{eq:shortestpathdynamictransition2} \end{align}\]言い換えると、ノード$i=N_t$にいて決定$x_{tij}= 1$を下す場合(これはノード$i$にいることを要求する。そうでなければ$x_{tij} = 0$となる)、$N_{t+1} = j$となる。
$\chat_{t+1}$の更新、すなわち予測$\cbar_{t+1}$に対する式$\eqref{eq:shortestpathdynamictransition1}$と、我々の物理状態$R_t$に対する式$\eqref{eq:shortestpathdynamictransition2}$が、我々の遷移関数を構成する
\[S_{t+1} = S^M(S_t, X^\pi(S_t), W_{t+1}).\]目的関数
これで、我々の目的関数を次のように書くことができる
\[\begin{align} \min_\pi F^\pi(S_0) = \E \left\{\sum_{t=0}^T \sum_{(i,j)\in\Ncal} \chat_{t+1,i,j}X^\pi(S_t)\vert S_0 \right\}. \label{eq:shortestpathdynamicobjective} \end{align}\]我々の方策$X^\pi(S_t)$は、時刻$t$における知識($S_t$に反映される)に基づいて、次に移動するリンクの選択を行うことに注意されたい。
不確実性のモデリング
実際には、コスト(および予測)の動的な更新は実システムから得られるものであり、これはデータ駆動であることを意味する。この場合、リンクコストの数学的モデルは使用しない。その代替として、ランダムな情報$W^{n+1}$の数学的モデルを持つという方法がある。
シミュレーションを実行したい場合、$\chat_t$で捉えられるコストの実現値、および予測の系列をモデル化するという課題に直面する。このモデルには相当な注意を払う必要がある。まず、$\delta \ctilde_{t+1}$で表される$\ctilde_t$の推定値の変化は、平均$0$を持つ分布から引き出されなければならない。さらに、実現値$\chat_{t+1}$は平均$\ctilde_t$を持つ分布から引き出されなければならない。
我々は、現実的な確率モデルを構築することの困難さを軽視したくはない。リンクコストの変化は、自然な交通変動、天候、事故、そしてネットワークの他の場所での渋滞に対応するドライバーの流れの変化など、さまざまな要因から生じる。リンクコストの確率的変動は非定常であり、時間的にも、リンク間でも独立ではない。しかし、この困難な課題を認識すること以上に、より現実的なモデルを構築することは本書の議論の範囲を超えている。
方策の設計
我々がベルマン方程式を(近似的にさえも)使用しないであろうことを示す手がかりは、状態変数の大きさである。それは今やネットワーク内のすべてのリンクの移動コストの予測を含んでいる。
その代わりに、我々は先読みモデルと呼ぶ特別なモデルに基づいて方策を構築する。例えば、時刻$t$において、状態$S_t$、決定$x_t$、外生情報$W_{t+1}$からなるモデルを作成できるが、我々の基本問題では状態変数$S_t = (N_t, \cbar_t)$はかなり複雑である。
その代わりに、我々はまず基本モデルの変数の近似値であることが典型的な、新しい変数の集合を作成する、より単純なモデルを作成する。我々は、先読みモデルの変数にチルダを付けることで、先読みモデル用の新しい変数の集合を区別し、2つの時間添字でインデックス付けする。すなわち、決定が下される時刻$t$と、先読みモデル内の時刻を表す第2の添字$t’$である。
先読みモデルにおける状態、決定、外生情報の系列は、次のように書ける
\[(\Stilde_{tt}, \xtilde_{tt}, \Wtilde_{t,t+1}, \ldots, \Stilde_{tt'}, \xtilde_{tt'}, \Wtilde_{t,t'+1}, \ldots ).\]我々のコストのベクトル$\cbar_t$は、ベクトル$\ctilde_{tt’}$に置き換えられる。ここで我々は、先読みモデル内で$\xtilde_{tt’}$を決定する$\Xtilde_{tt’}(\Stilde_{tt’})$と呼べる先読み方策を設計するという課題に直面する。以下では2つの戦略を提案するが、どちらも単純な最短経路アルゴリズムを用いて解くことができる。
決定論的先読み方策
先読みモデルにおけるコスト$\ctilde_{tt’}$は固定されており、現在の推定値に等しいと仮定することで問題を近似する。すなわち
\[\ctilde_{tt'k\ell} = \cbar_{tk\ell}.\]これは、外生情報変数$\Wtilde_{tt’}$がもはや存在しないことを意味し、決定論的な先読みモデルが得られる。
これにより、コスト推定値$\ctilde_{tt’,k\ell}$を確率変数ではなく正しいコストとして扱い、我々の先読みモデルを決定論的に解くことができる。この場合、我々の状態変数は再び単純に、(先読みモデル内で)旅行者がいるノードとなる。
我々は、この問題を標準的な最短経路アルゴリズムで解くことができる。第5章で見たように、これはベルマン方程式で解くことができる決定論的な動的計画法である。まず、我々の先読みモデルにおいて時刻$t’$にノード$i$にいることの「価値」を求めることから始める。我々は、先読みモデルの終端時刻$t$における価値をゼロと設定することで、これらの価値を計算できる
\[\Vtilde_{t,t+H}(i) = 0,\ \text{for all } i.\]そして、(先読みモデル内で)$t’ = t+H-1, t+H-2, \ldots, t$について時間をさかのぼり、各ノード$i$について次を計算する:
\[\begin{align} \Vtilde_{tt'}(i) = \min_{j\in\Ncal^+_i} (\ctilde_{tt',ij} + \Vtilde_{t,t'+1}(j)). \label{eq:shortestpathdetlookahead} \end{align}\]我々の先読み方策は、次のように与えられる
\[\begin{align} \Xtilde^\pi_{tt'}(\Stilde_{tt'}=i) = \argmin_{j\in\Ncal^+_i} \big(\ctilde_{tt',ij} + \Vtilde_{t,t'+1}(\Stilde_{t,t'+1}=j)\big). \label{eq:shortestpathbellmandetlookahead} \end{align}\]最後に、ノード$i$にいる場合に基本モデルで実装する方策は、次のようになる
\[X^\pi_t(S_t = i) = \Xtilde^\pi_{tt}(S_t = i).\]これは、ナビゲーションシステムに従う際に我々が使用している方策である。決定論的な先読みモデルに基づいて決定を下すことは、不確実性下の逐次決定問題において決定を下すための最も広く用いられている手法の1つである。
図6.1は、ローリング先読みプロセスを示している。時刻$t$、$t+1$、$t+2$、$\ldots$において、我々は知り得るコストの推定値を用いて先読みモデルを作成し、解く。そして、我々は最短経路問題を解く。これは、すべてのノード$j$に対する決定$\xtilde_{tt’}(j)$として表現されるが、実際には時刻$t$に我々がいるノード$i$に対する決定$\xtilde_{tt}(i)$のみを実装する。
動的に変化する変数を先読みモデル内で一定に保つとき、この変数を先読みモデルにおける潜在変数と呼ぶ。「潜在変数」という用語は技術的には隠れた変数を意味する。この文脈では、(先読みモデル内で)時間とともに変化しない変数を指し、その場合、我々はそれを状態変数から除外する。つまり、それは(繰り返すが、先読みモデル内で)隠されているのである。
これは、先読みモデルにおいて行うことができるさまざまなタイプの近似の1つに過ぎない。我々が行っている最も明らかな近似は、決定論的な将来を用いるということである。すなわち、リンクコストの推定値は、基本モデルでは変化し続けているにもかかわらず、先読みモデル内では一定に保たれている。
したがって、先読みモデルはそれ自体の特性を持つ独自のモデルであり、これが我々がチルダ付きの変数を使用する理由である。これにより、$S_t$や$x_t$といった変数を用いる我々の基本モデルと、$\Stilde_{tt’}$や$\xtilde_{tt’}$といった変数を用いる先読みモデルとを区別することができる。
次に、この方法が不確実性の下でよりよく機能するようにするための小さな工夫を提案する。
パラメータ化された確定的先読み方策
我々の動的最短路問題における不確実性を扱う単純な戦略として、リンク$(k,\ell)$を時刻$t$に通過するコストに対する点推定値$\ctilde_{tt’k\ell}=\cbar_{tk\ell}$を、例えばコストの$\theta$パーセンタイルに置き換えるという方法がある。これは、コストを$\ctilde_{tt’,k\ell}(\theta) = \cbar_{tij}(\theta)$のように書くことを示唆している。このロジックは、例えば、時にひどく混雑してコストが非常に高くなりうるエリアを通る経路を避けるのに役立つ。
この方策は、点推定値$\cbar_t$を使用した場合と同様に容易に解ける確定的最短路問題を依然として生成する。上記の式$\eqref{eq:shortestpathdetlookahead}$–$\eqref{eq:shortestpathbellmandetlookahead}$を、$\theta$パーセンタイルのリンクコストを用いるように単純に修正すればよい。そして、パラメータ$\theta$への依存性を示すために価値関数$\Vtilde_{tt’}(i\vert \theta)$を指定するが、これは次式を用いて計算される。
\[\begin{align} \Vtilde_{tt'}(i\vert \theta) = \min_{j\in\Ncal^+_i} \big(\ctilde_{tt',ij}(\theta) + \Vtilde_{t,t'+1}(j\vert \theta)\big). \label{eq:shortestpaththetalookahead} \end{align}\]我々の先読み方策は次のように与えられる。
\[\begin{align} \Xtilde^\pi_{tt'}(\Stilde_{tt'}=i\vert \theta) = \argmin_{j\in\Ncal^+_i} \big(\ctilde_{tt',ij}(\theta) + \Vtilde_{tt'}(\Stilde_{t,t'+1}=j)\big). \label{eq:shortestpathbellmanthetalookahead} \end{align}\]そして、ベースモデル（実際に実装される決定を与えるもの）に対するパラメータ化された方策を次のように書く。
\[X^\pi_t(S_t = i\vert \theta) = \Xtilde_{tt}(S_t = i\vert \theta).\]これは、一つの大きな例外を除いて、我々の元の確定的先読みモデルと等価である。すなわち、次式を最適化することで$\theta$を調整する必要がある。
\[\begin{align} \min_\theta F^\pi(\theta\vert S_0) = \E \left\{\sum_{t=0}^T C(S_t,X^\pi(S_t\vert \theta))\vert S_0\right\}. \label{eq:tuneshortestpathcfa} \end{align}\]ここで$S_{t+1} = S^M(S_t,X^\pi(S_t\vert \theta), W_{t+1})$（式$\eqref{eq:shortestpathdynamictransition1}$–$\eqref{eq:shortestpathdynamictransition2}$を参照）は、$W_1, \ldots, W_T$のランダムな実現値を生成するための何らかの方法を用いる。
$\eqref{eq:tuneshortestpathcfa}$における最適化問題自体は困難な問題であるが、$\theta$が0から1の間のスカラーであることが助けになる。$\eqref{eq:tuneshortestpathcfa}$における目的関数を最適化するための実用的なアルゴリズムは、通常、シミュレーションを実行してこの関数のノイズを含んだ観測値を得ることを伴う。
当然の疑問として、$\theta = 0.5$とは異なるパーセンタイルを使用することで結果が改善されるかどうかというものがある。我々の経験では、到着遅延に対するペナルティが存在する場合（例えば、午前9時の約束に間に合いたい場合）にはこれが当てはまる。
何を学んだか？
- コストの推定値が時間とともに変化する動的ネットワーク問題をどのようにモデル化するかを示した。今回は、システムの状態は、旅行者の位置とネットワーク内のすべてのリンクに関するコストの推定値からなる。
- 近似先読みモデルという考え方を導入した。この場合は確定的先読みであり、最短路問題として解くことができる。これは最適解ではあるものの、近似先読みモデルを、たとえ最適に解いたとしても、それは最適方策ではない。
- 潜在変数について説明した。これは動的な変数（リンク上のコスト）であり、先読みモデルでは一定に保たれる（そのため、もはや状態変数には含まれない）。
- 確定的先読みを、パラメータ化された確定的先読みへと修正する方法を示した。各リンクの期待コストを使用する代わりに、リンクがどれだけ悪くなりうるかを考慮するために$\theta$パーセンタイルを使用することができる。パラメータ$\theta$は調整する必要があり、これにより、パラメータ化された確定的先読み近似（DLA方策）と、CFA方策の一形態としての性質を併せ持つハイブリッドなDLA/CFA方策となる。
演習問題
復習問題
- なぜ[第5章](/sdam/ja/chapter-5/)の近似動的計画法の手法を用いて、我々の動的問題を解くことができなかったのか。
- 先読みモデルにおいて、外生過程$W_t$をどのようにモデル化しているか。
- 先読み方策とは何を意味するのか、言葉で説明せよ。
問題解決演習
- 我々の方策として確定的先読みモデルを解く。これは確定的問題を最適に解く。なぜこれは最適方策ではないのか。
- 我々の確定的先読みモデル（修正されたコスト$\cbar_{ij}(\theta)$を用いる場合もある）を、ベルマン方程式を用いた確定的動的計画法として解く。なぜこの場合、動的計画法を用いてベースモデルを解いているとは言えないのか。
- 起点ノードからできるだけ遅く出発したいが、目的地ノードへの遅延到着に対して高いペナルティが課されるとする。コスト$\cbar_{tij}(\theta)$の$\theta$パーセンタイルについて最適化する場合、このロジックはどのようにして遅延到着を回避するのに役立つか。
- 演習問題6の洞察を踏まえて、遅延到着の可能性を考慮せず単に総移動時間を最小化しようとする問題に対して、$\theta$パーセンタイルコストを使用することがどのように役立つと考えられるか。
- ノード$i$から出るリンクのコスト$\chat_{tij}$が、旅行者がノード$i$に到着し、どのリンクを通過するかを決定する前に明らかになる設定について、完全なモデル（状態変数、決定変数、……）を示せ。経路上の累積コストを最小化していることを忘れないこと。方策を設計する必要はなく、方策を指定せずに方策$X^\pi(S_t)$を導入するという我々の標準的な慣習に従うこと。
- 起点からできるだけ遅く出発したいが、午前9時までに目的地に到着する必要がある最短路問題を解きたいとする。午前9時以降に到着する各分に対してペナルティ$\eta$を課すとする。この問題を解くためのベースモデルとパラメータ化された先読み方策を説明せよ。ベースモデルの状態変数は何か。先読みモデルの状態変数は何か。
プログラミング演習
これらの演習では、tinyurl.com/sdagithubにあるPythonモジュールStochasticShortestPath_Dynamicを使用する。
- 本文で行ったのと同様に確定的先読みモデルを使用するが、各リンクの期待コストを使用する代わりに、$\theta^{cost}$で表されるパーセンタイルを使用する。例えば、$\theta^{cost} = 0.8$であれば、コストの80パーセンタイルを使用することになる（これは、コストがどれだけ大きくなりうるかの推定値を使用していると考えればよい）。$\cbar_{tij}(\theta^{cost})$を、時刻$t$における既知の情報の下でのリンク$(i,j)$の$\theta^{cost}$パーセンタイルコストとする。
- （本書で行ったように）コスト$\cbar_{tij}(\theta^{cost})$を用いた確定的最短路である先読みモデルを書き出せ。このモデルを用いて先読み方策$X^{DLA}(S_{tj}\vert \theta^{cost})$を形式的に定義せよ。
- 動的問題の状態変数は何か。状態変数には、決定を下すために使用される（コストや制約の計算を含む）すべての動的に変化する情報、および$t$から$t + 1$への遷移の計算に必要な情報が含まれることを忘れないこと。
- 我々の先読み方策を評価するために使用される目的関数を書き出せ。
- これで$\theta^{cost}$によってパラメータ化された方策$X^{DLA}(S_{tj}\vert \theta^{cost})$が得られた。PythonモジュールStochasticShortestPath_Dynamicを使用して、$\theta^{cost} = (0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0)$についてこの方策をシミュレートせよ。方策の各バージョンを100回シミュレートし、実際の総コスト（$\theta^{cost}$パーセンタイルではなく）の平均を取れ。また、「遅延」のリスク、すなわち実際の総コストが与えられた閾値を超える確率についても考察せよ。結果をプロットし、比較せよ。