(57)【特許請求の範囲】
【請求項１】
入力された、移動する対象物が状態間を遷移した履歴を表す遷移履歴データ、及び状態間の基本遷移確率に基づいて、各状態についての目的地らしさを表す報酬関数を推定する報酬関数推定部と、
入力された、状態遷移確率の変化に関するデータに基づいて、前記状態間の基本遷移確率を更新する障害物有り基本遷移関数計算部と、
前記報酬関数推定部によって推定された前記報酬関数と、前記障害物有り基本遷移関数計算部によって更新された前記状態間の基本遷移確率とに基づいて、各状態の目的地への到達しやすさを表す価値関数を計算する価値関数計算部と、
前記価値関数計算部によって計算された前記価値関数と、前記障害物有り基本遷移確率計算部によって更新された前記状態間の基本遷移確率とに基づいて、状態間の前記対象物の移動を予測するＷｈａｔ−ｉｆ予測確率を推定するＷｈａｔ−ｉｆ予測確率計算部と、
を含むＷｈａｔ−ｉｆシミュレーション装置。
【請求項２】
前記報酬関数推定部は、入力された前記遷移履歴データ及び前記状態間の基本遷移確率に基づいて、前記遷移履歴データに対する前記価値関数の尤もらしさを表す目的関数を最適化するように、前記価値関数を推定し、前記推定された前記価値関数と、前記状態間の基本遷移確率とに基づいて、前記報酬関数を推定する請求項１記載のＷｈａｔ−ｉｆシミュレーション装置。
【請求項３】
報酬関数推定部が、入力された、移動する対象物が状態間を遷移した履歴を表す遷移履歴データ、及び状態間の基本遷移確率に基づいて、各状態についての目的地らしさを表す報酬関数を推定するステップと、
障害物有り基本遷移関数計算部が、入力された、状態遷移確率の変化に関するデータに基づいて、前記状態間の基本遷移確率を更新するステップと、
価値関数計算部が、前記報酬関数推定部によって推定された前記報酬関数と、前記障害物有り基本遷移関数計算部によって更新された前記状態間の基本遷移確率とに基づいて、各状態の目的地への到達しやすさを表す価値関数を計算するステップと、
Ｗｈａｔ−ｉｆ予測確率計算部が、前記価値関数計算部によって計算された前記価値関数と、前記障害物有り基本遷移確率計算部によって更新された前記状態間の基本遷移確率とに基づいて、状態間の前記対象物の移動を予測するＷｈａｔ−ｉｆ予測確率を推定するステップと、
を含むＷｈａｔ−ｉｆシミュレーション方法。
【請求項４】
前記報酬関数推定部が推定するステップは、入力された前記遷移履歴データ及び前記状態間の基本遷移確率に基づいて、前記遷移履歴データに対する前記価値関数の尤もらしさを表す目的関数を最適化するように、前記価値関数を推定し、前記推定された前記価値関数と、前記状態間の基本遷移確率とに基づいて、前記報酬関数を推定する請求項３記載のＷｈａｔ−ｉｆシミュレーション方法。
【請求項５】
コンピュータを、請求項１又は請求項２に記載のＷｈａｔ−ｉｆシミュレーション装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｗｈａｔ−ｉｆシミュレーション装置、方法、及びプログラムに係り、特に、対象物の流れを予測するためのＷｈａｔ−ｉｆシミュレーション装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
本発明における背景技術は、蓄積させたデータを基に人やモノ等に代表される対象物の流れを予測する技術である。人の流れの一例としては、例えば「自宅→最寄り駅→東京駅→勤務地」、のようなある個人の移動系列のことを示し、予測とは、過去に蓄積された系列データをもとに、東京駅の後にどこを訪れるかを推測すること、又は、東京駅の後に各場所（たとえば勤務地）を訪れる確率がいくつであるかを算出することを示す。移動系列は上記の例のように必ずしも具体的な場所名の系列で表現される必要はなく、緯度経度情報が連続するようなＧＰＳデータであってもよい。また人以外のモノの流れについても同様に表現可能である。例えば、動物が住処を変える移動の履歴や、車やタクシーの移動履歴も、同様の移動系列として表現できることがわかる。これ以後は人の流れの例を用いて述べるが、それとまったく同様にモノの流れの予測にも適用可能であることを述べておく。また、ここでいうモノとは自然法則によって全て動きが説明されるもの、及びされないもの両方を含むが、自然法則で説明できない人間の意思で制御及びコントロールされるモノ、自己の判断で動く動物の行動を予測ができることに本技術の利点がある。
【０００３】
人やモノなどの流れを予測する手法として最も代表的なものとして、マルコフモデルがある。このマルコフモデルでは、次の状態は現在の状態にのみ依存して確率的に決まるとされる。したがって、例えば系列データとしてＡ→Ｂ→Ｃ、Ａ→Ｃ、Ａ→Ｂという３つのデータが蓄積されていたとすると、状態Ａから始まる遷移にはＡ→Ｂが２回、Ａ→Ｃが１回の計３回観測されていることから、Ａの後にＢへ移動する確率は２／３、Ｃへ移動する確率は１／３と、遷移の確率をデータから推定する。上記のマルコフモデルはある個人のデータだけを用いて推定を行えば、その個人の次の状態の予測も行えるし、個人による遷移の違いが無いとして全員のデータを用い、推定を行うこともできる。また、マルコフモデルは多様な拡張がなされている。例えば上記のマルコフモデルでは、１ステップ後の遷移しか考えていないが、Ｎステップ前の状態から１ステップ前の状態全てに依存して次の状態が決定するＮ次マルコフ連鎖と呼ばれる方法も可能である。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記の手法では、データが得られた環境と全く異なる環境における予測を行うことができない。したがって、例えば、普段の東京駅付近の人の流れが蓄積されたデータを所有していたとしても、自然災害によって東京駅に近づくことが不可能となった時に、人の流れを予測することは不可能である。
【０００５】
本発明は、上記問題点を解決するために成されたものであり、障害物が存在する状況における、対象物の流れを予測することができるＷｈａｔ−ｉｆシミュレーション装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、第１の発明に係るＷｈａｔ−ｉｆシミュレーション装置は、入力された、移動する対象物が状態間を遷移した履歴を表す遷移履歴データ、及び状態間の基本遷移確率に基づいて、各状態についての目的地らしさを表す報酬関数を推定する報酬関数推定部と、入力された、状態遷移確率の変化に関するデータに基づいて、前記状態間の基本遷移確率を更新する障害物有り基本遷移関数計算部と、前記報酬関数推定部によって推定された前記報酬関数と、前記障害物有り基本遷移関数計算部によって更新された前記状態間の基本遷移確率とに基づいて、各状態の目的地への到達しやすさを表す価値関数を計算する価値関数計算部と、前記価値関数計算部によって計算された前記価値関数と、前記障害物有り基本遷移確率計算部によって更新された前記状態間の基本遷移確率とに基づいて、状態間の前記対象物の移動を予測するＷｈａｔ−ｉｆ予測確率を推定するＷｈａｔ−ｉｆ予測確率計算部と、を含んで構成されている。
【０００７】
また、第１の発明に係るＷｈａｔ−ｉｆシミュレーション装置において、前記報酬関数推定部は、入力された前記遷移履歴データ及び前記状態間の基本遷移確率に基づいて、前記遷移履歴データに対する前記価値関数の尤もらしさを表す目的関数を最適化するように、前記価値関数を推定し、前記推定された前記価値関数と、前記状態間の基本遷移確率とに基づいて、前記報酬関数を推定するようにしてもよい。
【０００８】
第２の発明に係るＷｈａｔ−ｉｆシミュレーション方法は、報酬関数推定部が、入力された、移動する対象物が状態間を遷移した履歴を表す遷移履歴データ、及び状態間の基本遷移確率に基づいて、各状態についての目的地らしさを表す報酬関数を推定するステップと、障害物有り基本遷移関数計算部が、入力された、状態遷移確率の変化に関するデータに基づいて、前記状態間の基本遷移確率を更新するステップと、価値関数計算部が、前記報酬関数推定部によって推定された前記報酬関数と、前記障害物有り基本遷移関数計算部によって更新された前記状態間の基本遷移確率とに基づいて、各状態の目的地への到達しやすさを表す価値関数を計算するステップと、Ｗｈａｔ−ｉｆ予測確率計算部が、前記価値関数計算部によって計算された前記価値関数と、前記障害物有り基本遷移確率計算部によって更新された前記状態間の基本遷移確率とに基づいて、状態間の前記対象物の移動を予測するステップと、を含んで実行することを特徴とする。
【０００９】
また、第１の発明に係るＷｈａｔ−ｉｆシミュレーション方法において、前記報酬関数推定部が推定するステップは、入力された前記遷移履歴データ及び前記状態間の基本遷移確率に基づいて、前記遷移履歴データに対する前記価値関数の尤もらしさを表す目的関数を最適化するように、前記価値関数を推定し、前記推定された前記価値関数と、前記状態間の基本遷移確率とに基づいて、前記報酬関数を推定するようにしてもよい。
【００１０】
第３の発明に係るプログラムは、コンピュータを、上記第１の発明に係るＷｈａｔ−ｉｆシミュレーション装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１１】
本発明のＷｈａｔ−ｉｆシミュレーション装置、方法、及びプログラムによれば、移動する対象物が状態間を遷移した履歴を表す遷移履歴データ、及び状態間の基本遷移確率に基づいて、各状態についての目的地らしさを表す報酬関数を推定し、障害物が置かれた状態の集合を表す障害物データに基づいて、状態間の基本遷移確率を更新し、推定された報酬関数と、更新された状態間の基本遷移確率とに基づいて、各状態の目的地への到達しやすさを表す価値関数を計算し、計算された価値関数と、更新された状態間の基本遷移確率とに基づいて、状態間の対象物の移動を予測するＷｈａｔ−ｉｆ予測確率を推定することにより、障害物が存在する状況における、対象物の流れを予測することができる、という効果が得られる。
【図面の簡単な説明】
【００１２】
【図１】線形可解マルコフ決定過程（ＭＬＤＰ）における状態集合、基本遷移関数、及び報酬関数の一例を示す抽象図である。
【図２】障害物設置による基本遷移関数の変化の一例を示す抽象図である。
【図３】本発明の実施の形態に係るＷｈａｔ−ｉｆシミュレーション装置の構成を示すブロック図である。
【図４】本発明の実施の形態に係るＷｈａｔ−ｉｆシミュレーション装置におけるＷｈａｔ−ｉｆシミュレーション処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１４】
＜本発明の実施の形態に係る概要＞
【００１５】
まず、本発明の実施の形態に係る概要を説明する。
【００１６】
本発明の実施の形態における技術の新規性は、自然災害発生時などの、データが蓄積された環境とは全く異なる環境における人の流れを予測可能としたことにある。実際に自然災害が起こった時の予測に使えることはもちろん、「もし起こったときにどうなるか」というＷｈａｔ−ｉｆ予測も可能とすることができる。なお、本実施の形態では人の流れの予測に焦点を置いて説明するが、これに限定されるものではなく、対象物となるものであれば、人以外にも車、動物等のあらゆるモノの流れの予測が可能である。
【００１７】
本実施の形態において提案する手法では、「通常時において蓄積された系列データ」と自然災害によってある場所が侵入禁止となったなどの「変化した環境における通行可能・不可能を表すデータ」を用いる。提案手法の鍵となるアイディアは「通常時において蓄積された系列データ」から、人の流れの到達点を推定することにある。到達点を推定することの有効性は次の例を考えるとわかりやすい。例えば、帰宅ラッシュ時間に東京駅近辺で大規模火災が発生し、東京駅に近づくことが不可能となった場合を考える。このとき、人々の動きは新橋駅や品川駅まで徒歩移動したのちに電車を利用するなど、移動の仕方について劇的な変化が生じると考えられる。しかし、流れの到達点、すなわち人々の帰宅先は変わらない。よって、提案手法では、火災が発生していない通常時に推定した、人の流れの到達点に関する情報をそのまま転用することができる。この人の流れの到達点に関する情報に「変化した環境における通行可能・不可能を表すデータ」を組み合わせ、利用可能な経路を限定することで、「変化後の環境における系列データ」を利用することなく人の流れを予測することを実現する。
【００１８】
また、変化する人の流れの予測が可能になることによって、多様なサービスの実現が見込まれる。例えば、ある個人が次に駅に到着することがわかれば、ユーザの入力なしにスマートフォン上に時刻表を表示させることができるし、飲食店の多いエリアに到着することがわかれば、そのエリア店舗のクーポンを表示させることもできる。他にも、ショッピングセンター内などの施設内である店舗を訪れる人の数が通行を妨げるレベルで増大することが予測されれば、施設運営者は行列整理のための人員を派遣するなどの対策をとることも可能となる。
【００１９】
［本発明の実施の形態におけるアイディア］
【００２０】
上記のアイディアを、本発明の実施の形態では、次の３つのアプローチから実現する。
【００２１】
第１のアプローチは、「流れの到達点」の推定として「逆強化学習による報酬推定」を利用する事である。
【００２２】
第２のアプローチは、「変化した環境における通行可能・不可能を表すデータ」から局所的な遷移の変化を計算することである。
【００２３】
第３のアプローチは、流れの到達点の推定結果、及び局所的な遷移の変化を組み合わせて人の流れを予測することである。
【００２４】
［逆強化学習による報酬推定］
【００２５】
本発明の実施の形態では、後述する報酬関数について逆強化学習を行う。逆強化学習とはその名の通り、強化学習と呼ばれる問題の逆問題を表しており、そのためまずは強化学習について簡単に述べる。また、本発明の実施の形態では強化学習の中でも、線形可解マルコフ決定過程（Ｌｉｎｅａｒｌｙ Ｓｏｌｖａｂｌｅ Ｍａｒｋｏｖ Ｄｅｃｉｓｉｏｎ Ｐｒｏｃｅｓｓ、以下、ＬＭＤＰと称する）と呼ばれる参考文献１に記載の枠組みを利用したものを考える。
【００２６】
［参考文献１］Emanuel Todorov. Linearly-solvable markov decision problems. In Advances in neural information processing systems, pages 1369{1376, 2006.
【００２７】
ＬＭＤＰは、参考文献２に記載のマルコフ決定過程（Ｍａｒｋｏｖ Ｄｅｃｉｓｉｏｎ Ｐｒｏｃｅｓｓ、以下、ＭＤＰと称する）と同様にロボットと外界の相互作用を記述したものである。
【００２８】
［参考文献２］RichardS Sutton and AndrewG Barto. Reinforcement learning: An introduction. MIT press Cambridge, 1998. 邦題: 強化学習訳: 三上貞芳, 皆川雅章. 
【００２９】
ＭＤＰは、ロボットがとりうる状態の集合、状態間の遷移の仕方を定める関数、コスト関数で定義される。各状態で行動をとることで、状態間の遷移の仕方をある程度コントロールすることが許され、ＬＭＤＰ、及びＭＤＰではコスト和を最小化する、各状態でどの行動を選択するかを定める方策（最適方策と呼ぶ）を求める順問題が考察される。ロボット制御の文脈でよく説明される上記の順問題の具体例として、迷路にいるロボットの例が挙げられる。迷路のどこにいるかを定めているのが「状態」、ロボットが右に行くか左に行くかが「行動」であり、どこがゴールであるかを定めているのが「報酬関数」である。迷路を最短に脱出する手段（迷路の各場所で右に行くが、左に行くかを決定する）が「最適方策」である。よって最適方策を求める、という問題はこの場合、迷路の脱出手段をロボットが自動で獲得する、ということに対応する。上記の順問題の説明を含むＭＤＰの適用例は、上記参考文献２に詳しい。ＬＭＤＰではＭＤＰと比較して容易に最適方策を求めることができる。なお、正確にはＬＭＤＰとＭＤＰとでは問題の定義が少々異なるがここでは説明を省略する。
【００３０】
また、ＬＭＤＰは、参考文献３に記載されているように、逆問題（ＩｎｖｅｒｓｅＬＭＤＰ）も非常に効率的に解くことができるという利点がある。
【００３１】
［参考文献３］Krishnamurthy Dvijotham and Emanuel Todorov. Inverse optimal control with linearly-solvable mdps. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 335{342, 2010.
【００３２】
ＬＭＤＰの逆問題は、順問題とは入出力が異なり、ロボットの移動系列データと基本遷移関数から、報酬関数を推定する問題として定式化される。移動系列データは、最適方策にしたがってロボットが行動した遷移の履歴であるとみなすことで、背後にある未知の報酬関数を推定するのである。よってこのＩｎｖｅｒｓｅＬＭＤＰの定式化を用いることで、「蓄積された人の流れの系列データ」から「各場所の目的地（ゴール）としての度合い」を定める報酬関数を効率的に推定することができる。
【００３３】
［シナリオデータと基本遷移関数］
【００３４】
次に「変化した環境における通行可能・不可能を表すデータ」の利用方法について述べる。このデータは、「もし東京駅に入らないとき」というＷｈａｔ−ｉｆのｉｆに対応する部分のデータであり、シナリオデータと呼ぶことにする。本発明の実施の形態では、シナリオデータによって、ＬＭＤＰにおける基本遷移関数Ｐを変更することを考える。例えば、東京駅利用不可の例でいえば、ある場所から東京駅への基本遷移確率が０より大きいある値を持っていたが、それが０になったと考える。これは先ほどの迷路ロボットの例でいえば、新たに通行不可能な障害物が追加されたケースを想定していることと非常に類似する。他にも、例えばデータが収集されたエリアが駅構内であり、駅構内の人の移動を予測するケースを考えてみる。この場合、立ち入り禁止以外にも、特定エリアを一方通行にすることなどが考えられるが、このようなケースもまた基本遷移関数の変化として表現可能である。このように本技術は、Ｗｈａｔ−ｉｆのシナリオとして基本遷移関数の変化として表現できるものを考える。
【００３５】
［Ｗｈａｔ−ｉｆ予測］
【００３６】
最後にＷｈａｔ−ｉｆ予測を行う際には、ＬＭＤＰの順問題の定式化を利用する。つまり、蓄積された人の流れの系列データから推定した報酬関数、シナリオデータを用いて計算された新しい基本遷移関数、の２つを入力として、最適方策を求める。人はこの最適方策に従って行動を選択するとして予測を行うことで変化した環境における予測や、Ｗｈａｔ−ｉｆ予測を行う。
【００３７】
＜本発明の実施の形態に係る原理＞
【００３８】
次に、本発明の実施の形態に係る原理を説明する。ここでは、実施の形態の構成及び作用において用いる記号、アルゴリズムについて記述する。
【００３９】
［線形可解マルコフ決定過程（ＬＭＤＰ）の定義］
【００４０】
まず、上記参考文献１を参照して、線形可解マルコフ決定過程（ＬＭＤＰ）について説明する。ＬＭＤＰでは、状態集合
【００４１】
【数１】
0006464075.tif 000002
【００４２】
、基本遷移関数
【００４３】
【数２】
0006464075.tif 000003
【００４４】
、及び報酬関数
【００４５】
【数３】
0006464075.tif 000004
【００４６】
の３つ組
【００４７】
【数４】
0006464075.tif 000005
【００４８】
で定義された環境を考える。上記３つ組の具体例を図１に示す。図１中の各グリッドが状態集合
【００４９】
【数５】
0006464075.tif 000006
【００５０】
中のいずれかの状態ｓｉに対応し、各グリッド間の“基本的な”遷移の確率が基本遷移関数
【００５１】
【数６】
0006464075.tif 000007
【００５２】
によって決められている。“基本的な”と注釈をつけたのは、ＬＭＤＰでは行動
【００５３】
【数７】
0006464075.tif 000008
【００５４】
を実行し、行動コストを支払うことでこの遷移の確率を変更することが許されているからである。具体的には、行動
【００５５】
【数８】
0006464075.tif 000009
【００５６】
を実行することで、状態ｉから状態ｊへの遷移の確率を
【００５７】
【数９】
0006464075.tif 000010
【００５８】
から以下（１）式に示す
【００５９】
【数１０】
0006464075.tif 000011
【００６０】
に変更することができる。
【００６１】
【数１１】
0006464075.tif 000012
【００６２】
上記（１）式では、ａｊの値が大きければ大きいほど、状態ｊへの遷移の確率を増加できることがわかる。ただし、
【００６３】
【数１２】
0006464075.tif 000013
【００６４】
の値は確率の和が１となることを満たすもの、すなわち
【００６５】
【数１３】
0006464075.tif 000014
【００６６】
を満たすものに限られる。
【００６７】
【数１４】
0006464075.tif 000015
【００６８】
また、上記の行動のように、状態ｉで行動
【００６９】
【数１５】
0006464075.tif 000016
【００７０】
を実行することにより発生するコスト
【００７１】
【数１６】
0006464075.tif 000017
【００７２】
は、確率分布の類似度を図る尺度であるＫＬ距離を用いて以下（３）式のように定義される。ＫＬ距離は、値が小さいほど類似していることを表し、一致すれば０となる。
【００７３】
【数１７】
0006464075.tif 000018
【００７４】
つまり、上記（３）式においては遷移の確率を￣ｐｉｊから変化させればさせるほど、支払うコストが高くなる。上記の行動コストとは別に状態のみに依存した状態コストを表すのが、報酬関数
【００７５】
【数１８】
0006464075.tif 000019
【００７６】
である。図１の例で示すように、この報酬関数の値を本実施の形態では“目的地らしさ”に対応した値とみなし、値が小さいほど目的地らしいものとする。さらに、各状態ｓｉにおいて実行する行動
【００７７】
【数１９】
0006464075.tif 000020
【００７８】
を定めたものを方策
【００７９】
【数２０】
0006464075.tif 000021
【００８０】
と呼ぶこととする。
【００８１】
方策πにしたがって行動するロボットや人を考えると、上記（１）式にしたがって確率的に状態間を遷移し、遷移する度に行動コストと状態コストとの和
【００８２】
【数２１】
0006464075.tif 000022
【００８３】
を支払う動きがモデリングできる。状態遷移を十分な回数繰り返した際に、遷移の過程で支払ったコスト（行動コストと状態コストとの和）の累積和の期待値が最小になるような方策を最適方策と呼び、
【００８４】
【数２２】
0006464075.tif 000023
【００８５】
と書く。すなわち、最適方策とは、できるだけ少ない行動コストで状態コストの低い目的地に早く到達できる方策であり、直感的には、目的地に到達する最適な手順を表しているとみなせる。このように、基本遷移関数
【００８６】
【数２３】
0006464075.tif 000024
【００８７】
と報酬関数
【００８８】
【数２４】
0006464075.tif 000025
【００８９】
が既知の時に、最適方策
【００９０】
【数２５】
0006464075.tif 000026
【００９１】
を求める問題が、ＬＭＤＰにおける順問題である。最適方策は、以下（４）式の最適性方程式を満たす価値関数
【００９２】
【数２６】
0006464075.tif 000027
【００９３】
を求めることで、次の（６）式のように算出できる。なお、上記（４）式から（５）式への式展開は上記参考文献３を参照できる。また、価値関数は、各状態の目的地への到達しやすさを表す。価値関数の求め方は後述する。
【００９４】
【数２７】
0006464075.tif 000028
【００９５】
ここで、上記（６）式により得られたａ＊ｉｊの値を上記（１）式に代入することで、最適方策により行動を選択する場合の遷移確率は、以下（７）式で与えられることがわかる。
【００９６】
【数２８】
0006464075.tif 000029
【００９７】
したがって、価値関数
【００９８】
【数２９】
0006464075.tif 000030
【００９９】
が計算できれば、ＬＭＤＰの順問題が解けることになる。
【０１００】
［価値関数計算アルゴリズム］
【０１０１】
次に、参考文献１を参照して価値関数を計算するアルゴリズムについて説明する。価値関数を計算するアルゴリズムは上記（５）式から導かれる。両辺の符号を変換したのち、指数をとると、以下の（８）式が求まる。
【０１０２】
【数３０】
0006464075.tif 000031
【０１０３】
ここで
【０１０４】
【数３１】
0006464075.tif 000032
【０１０５】
と定義すると、上記（８）式は以下（９）式のようにベクトル表記できる。
【０１０６】
【数３２】
0006464075.tif 000033
【０１０７】
これより明らかに
【０１０８】
【数３３】
0006464075.tif 000034
【０１０９】
は行列
【０１１０】
【数３４】
0006464075.tif 000035
【０１１１】
の固有値１の固有ベクトルであることがわかる。また、これが最大固有ベクトルであることも示せる。よって、以下（１０）式に従い、
【０１１２】
【数３５】
0006464075.tif 000036
【０１１３】
と収束するまで更新することで上記（９）式を満たす
【０１１４】
【数３６】
0006464075.tif 000037
【０１１５】
を求めることができる。
【０１１６】
【数３７】
0006464075.tif 000038
【０１１７】
最後に上記（９）式の定義より、
【０１１８】
【数３８】
0006464075.tif 000039
【０１１９】
と変換することで価値関数
【０１２０】
【数３９】
0006464075.tif 000040
【０１２１】
が求まる。以上がＬＭＤＰの順問題の解法である。
【０１２２】
［逆問題の解法］
【０１２３】
次に参考文献３を参照してＬＭＤＰの逆問題を説明する。ＬＭＤＰの逆問題は、人、ロボットの遷移の系列と基本遷移関数
【０１２４】
【数４０】
0006464075.tif 000041
【０１２５】
とを入力とし、報酬関数
【０１２６】
【数４１】
0006464075.tif 000042
【０１２７】
を推定する問題、として定式化される。逆問題における解法の鍵は、人、ロボットの遷移は上記（７）式の最適方策による遷移確率にしたがって得られているとみなすことにある。入力の遷移系列データ
【０１２８】
【数４２】
0006464075.tif 000043
【０１２９】
を（遷移前の状態，遷移後の状態）という１ステップの遷移の履歴の集合で表現し、ｎｉを状態ｉが遷移前の状態として現れた回数、ｎ´ｉを状態ｉが遷移後の状態として現れた回数とする。
【０１３０】
上記（７）式における価値関数
【０１３１】
【数４３】
0006464075.tif 000044
【０１３２】
を未知のパラメタとみなすと、以下（１１）に示す負の対数尤度関数
【０１３３】
【数４４】
0006464075.tif 000045
【０１３４】
を最小化する
【０１３５】
【数４５】
0006464075.tif 000046
【０１３６】
が、最も入力の遷移の履歴を生成する確率の高い最尤推定量
【０１３７】
【数４６】
0006464075.tif 000047
【０１３８】
となる。
【０１３９】
【数４７】
0006464075.tif 000048
【０１４０】
上記（１１）式の関数の最小化には、最急降下法やニュートン法など任意の方法が適用できる。そして、上記（５）式に最尤推定量
【０１４１】
【数４８】
0006464075.tif 000049
【０１４２】
を代入すれば、報酬関数は次の（１２）式により求めることができる。
【０１４３】
【数４９】
0006464075.tif 000050
【０１４４】
以上がＬＭＤＰの逆問題の解法である。
【０１４５】
［障害物データ（シナリオデータ）による基本遷移確率の変化］
【０１４６】
前述したように、本発明の実施の形態では、変化した環境における通行可能・不可能を表すデータである、シナリオデータを利用する。シナリオデータの形式には多様なものが考えられるが、後述する構成では、（障害物の種類、及び設置場所）を表すものとしてシナリオデータが与えられるケースを想定する。よって以後シナリオデータを障害物データと呼ぶ。なお、障害物データが状態遷移確率の変化に関するデータの一例である。
【０１４７】
障害物の種類には、立ち入り禁止、一方通行などが挙げられる。図２に障害物が設置されたことによる基本遷移関数の変化前、変化後の値の例を示す。障害物設置後の基本遷移関数を障害物有り基本遷移関数
【０１４８】
【数５０】
0006464075.tif 000051
【０１４９】
と書くと、障害物［種類：立ち入り禁止］、障害物［種類：右一方通行］が追加された際の
【０１５０】
【数５１】
0006464075.tif 000052
【０１５１】
の計算式には、たとえば次の（１３）式のようなものが考えられる。
【０１５２】
【数５２】
0006464075.tif 000053
【０１５３】
ただし、
【０１５４】
【数５３】
0006464075.tif 000054
【０１５５】
が障害物［種類：立ち入り禁止］が置かれた状態の集合、
【０１５６】
【数５４】
0006464075.tif 000055
【０１５７】
が障害物［種類：右一方通行］が置かれた状態の集合を表す。上記（１３）以外の式を考える場合にも、本発明の実施の形態に適用可能である。
【０１５８】
［Ｗｈａｔ−ｉｆ予測］
【０１５９】
最後にＷｈａｔ−ｉｆ予測の全体像について述べる。まず初めにＩｎｖｅｒｓｅＬＭＤＰの枠組みで報酬関数を推定する。すなわち、入力として、人の遷移履歴データ
【０１６０】
【数５５】
0006464075.tif 000056
【０１６１】
と、このデータが収集された際の基本遷移関数
【０１６２】
【数５６】
0006464075.tif 000057
【０１６３】
を利用し、報酬関数
【０１６４】
【数５７】
0006464075.tif 000058
【０１６５】
と、価値関数
【０１６６】
【数５８】
0006464075.tif 000059
【０１６７】
とを推定する。次に障害物データと、基本遷移関数
【０１６８】
【数５９】
0006464075.tif 000060
【０１６９】
とを入力として、障害物有り基本遷移関数
【０１７０】
【数６０】
0006464075.tif 000061
【０１７１】
を求める。最後に、ＬＭＤＰの順問題を解く。障害物有り基本遷移関数
【０１７２】
【数６１】
0006464075.tif 000062
【０１７３】
と、データから推定した報酬関数
【０１７４】
【数６２】
0006464075.tif 000063
【０１７５】
を入力とすることで、障害物が存在するときの価値関数
【０１７６】
【数６３】
0006464075.tif 000064
【０１７７】
を求める。最後に障害物有り基本遷移関数
【０１７８】
【数６４】
0006464075.tif 000065
【０１７９】
と、価値関数
【０１８０】
【数６５】
0006464075.tif 000066
【０１８１】
とを上記（７）式に代入して、以下の（１４）式で与えられるＷｈａｔ−ｉｆ予測確率
【０１８２】
【数６６】
0006464075.tif 000067
【０１８３】
を用いて予測を行う。
【０１８４】
【数６７】
0006464075.tif 000068
【０１８５】
＜本発明の実施の形態に係るＷｈａｔ−ｉｆシミュレーション装置の構成＞
【０１８６】
次に、本発明の実施の形態に係るＷｈａｔ−ｉｆシミュレーション装置の構成について説明する。図３に示すように、本発明の実施の形態に係るＷｈａｔ−ｉｆシミュレーション装置１００は、ＣＰＵと、ＲＡＭと、後述するＷｈａｔ−ｉｆシミュレーション処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このＷｈａｔ−ｉｆシミュレーション装置１００は、機能的には図３に示すように入出力部１５０と、遷移履歴処理部１０と、基本遷移関数処理部２０と、報酬関数推定部３０と、障害物処理部４０と、障害物有り基本遷移関数計算部５０と、価値関数計算部６０と、Ｗｈａｔ−ｉｆ予測確率計算部７０と、Ｗｈａｔ−ｉｆ予測確率処理部８０と、記録部９０とを備えている。
【０１８７】
入出力部１５０は、外部装置２００から出力された、人が状態間を遷移した履歴を表す遷移履歴データ
【０１８８】
【数６８】
0006464075.tif 000069
【０１８９】
、状態間の基本遷移確率からなる基本遷移関数
【０１９０】
【数６９】
0006464075.tif 000070
【０１９１】
、及び障害物が置かれた状態の集合を表す障害物データを受け付ける。また、入出力部１５０は、Ｗｈａｔ−ｉｆ予測確率処理部８０による予測結果を、外部装置２００へ出力する。
【０１９２】
記録部９０は、遷移履歴記録部９１、基本遷移関数記録部９２、報酬関数記録部９３、障害物記録部９４、障害物有り基本遷移関数記録部９５、価値関数記録部９６、及びＷｈａｔ−ｉｆ予測確率記録部９７を有する。
【０１９３】
遷移履歴処理部１０は、入出力部１５０により受け付けた、人が状態間を遷移した履歴を表す遷移履歴データ
【０１９４】
【数７０】
0006464075.tif 000071
【０１９５】
を遷移履歴記録部９１に格納する。
【０１９６】
基本遷移関数処理部２０は、入出力部１５０により受け付けた、状態間の基本遷移確率からなる基本遷移関数
【０１９７】
【数７１】
0006464075.tif 000072
【０１９８】
を基本遷移関数記録部９２に格納する。
【０１９９】
報酬関数推定部３０は、遷移履歴記録部９１に格納された遷移履歴データ
【０２００】
【数７２】
0006464075.tif 000073
【０２０１】
と、基本遷移関数記録部９２に格納された基本遷移関数
【０２０２】
【数７３】
0006464075.tif 000074
【０２０３】
における状態間の基本遷移確率とに基づいて、状態ｉが遷移前の状態として現れた回数をｎｉ、状態ｉが遷移後の状態として現れた回数をｎ´ｉ、状態ｊの推定量をｖｊとして、上記（１１）式に示す、遷移履歴データに対する価値関数の尤もらしさを表す目的関数を最適化するように、価値関数の最尤推定量
【０２０４】
【数７４】
0006464075.tif 000075
【０２０５】
を求めることにより、各状態の目的地への到達しやすさを表す価値関数を推定する。そして、推定された価値関数と、状態間の基本遷移確率とに基づいて、最尤推定量
【０２０６】
【数７５】
0006464075.tif 000076
【０２０７】
を、上記（１２）式に代入することで報酬関数
【０２０８】
【数７６】
0006464075.tif 000077
【０２０９】
を推定し、報酬関数記録部９３に格納する。
【０２１０】
障害物処理部４０は、入出力部１５０により受け付けた、障害物が置かれた状態の集合を表す障害物データを障害物記録部９４に格納する。
【０２１１】
障害物有り基本遷移関数計算部５０は、基本遷移関数記録部９２に格納された基本遷移関数
【０２１２】
【数７７】
0006464075.tif 000078
【０２１３】
と、障害物記録部９４に格納された障害物データとに基づいて、障害物［種類：立ち入り禁止］が置かれた状態の集合を
【０２１４】
【数７８】
0006464075.tif 000079
【０２１５】
、障害物［種類：右一方通行］が置かれた状態の集合を
【０２１６】
【数７９】
0006464075.tif 000080
【０２１７】
として、上記（１３）式によって障害物有り基本遷移関数
【０２１８】
【数８０】
0006464075.tif 000081
【０２１９】
を計算することにより更新し、障害物有り基本遷移関数記録部９５に格納する。
【０２２０】
価値関数計算部６０は、報酬関数記録部９３に格納された報酬関数
【０２２１】
【数８１】
0006464075.tif 000082
【０２２２】
と、障害物有り基本遷移関数記録部９５に格納された障害物有り基本遷移関数
【０２２３】
【数８２】
0006464075.tif 000083
【０２２４】
における状態間の基本遷移確率とに基づいて、上記（１０）式に従って価値関数
【０２２５】
【数８３】
0006464075.tif 000084
【０２２６】
を計算し、価値関数記録部９６に格納する。
【０２２７】
Ｗｈａｔ−ｉｆ予測確率計算部７０は、価値関数記録部９６に格納された価値関数
【０２２８】
【数８４】
0006464075.tif 000085
【０２２９】
と、障害物有り基本遷移関数記録部９５に格納された障害物有り基本遷移関数
【０２３０】
【数８５】
0006464075.tif 000086
【０２３１】
における状態間の基本遷移確率とに基づいて、上記（１４）式に従って、状態間の人の移動を予測するＷｈａｔ−ｉｆ予測確率
【０２３２】
【数８６】
0006464075.tif 000087
【０２３３】
を推定し、Ｗｈａｔ−ｉｆ予測確率記録部９７に格納する。
【０２３４】
Ｗｈａｔ−ｉｆ予測確率処理部８０は、Ｗｈａｔ−ｉｆ予測確率記録部９７に格納されたＷｈａｔ−ｉｆ予測確率
【０２３５】
【数８７】
0006464075.tif 000088
【０２３６】
を外部装置２００に出力する。
【０２３７】
＜本発明の実施の形態に係るＷｈａｔ−ｉｆシミュレーション装置の作用＞
【０２３８】
次に、本発明の実施の形態に係るＷｈａｔ−ｉｆシミュレーション装置１００の作用について説明する。入出力部１５０において遷移履歴データを受け付け遷移履歴記録部９１に格納し、状態間の基本遷移確率からなる基本遷移関数を受け付け基本遷移関数記録部９２に格納し、及び障害物が置かれた状態の集合を表す障害物データを受け付け障害物記録部９４に格納すると、Ｗｈａｔ−ｉｆシミュレーション装置１００は、図４に示すＷｈａｔ−ｉｆシミュレーション処理ルーチンを実行する。
【０２３９】
まず、ステップＳ１００では、遷移履歴記録部９１に格納された遷移履歴データと、基本遷移関数記録部９２に格納された基本遷移関数における状態間の基本遷移確率とに基づいて、状態ｉが遷移前の状態として現れた回数をｎｉ、状態ｉが遷移後の状態として現れた回数をｎ´ｉ、状態ｊの推定量をｖｊとして、上記（１１）式に示す、遷移履歴データに対する価値関数の尤もらしさを表す目的関数を最適化するように、価値関数の最尤推定量を求めることにより、各状態の目的地への到達しやすさを表す価値関数を推定する。
【０２４０】
次に、ステップＳ１０２では、ステップＳ１００で推定された価値関数と、状態間の基本遷移確率とに基づいて、最尤推定量を、上記（１２）式に代入することで報酬関数を推定し、報酬関数記録部９３に格納する。
【０２４１】
ステップＳ１０４では、基本遷移関数記録部９２に格納された基本遷移関数と、障害物記録部９４に格納された障害物データとに基づいて、障害物［種類：立ち入り禁止］が置かれた状態の集合を
【０２４２】
【数８８】
0006464075.tif 000089
【０２４３】
、障害物［種類：右一方通行］が置かれた状態の集合を
【０２４４】
【数８９】
0006464075.tif 000090
【０２４５】
として、上記（１３）式によって障害物有り基本遷移関数を計算し、障害物有り基本遷移関数記録部９５に格納する。
【０２４６】
ステップＳ１０６では、報酬関数記録部９３に格納された報酬関数と、障害物有り基本遷移関数記録部９５に格納された障害物有り基本遷移関数における状態間の基本遷移確率とに基づいて、上記（１０）式に従って価値関数を計算し、価値関数記録部９６に格納する。
【０２４７】
ステップＳ１０８では、価値関数記録部９６に格納された価値関数と、障害物有り基本遷移関数記録部９５に格納された障害物有り基本遷移関数における状態間の基本遷移確率とに基づいて、上記（１４）式に従って、状態間の対象物の移動を予測するＷｈａｔ−ｉｆ予測確率を推定し、Ｗｈａｔ−ｉｆ予測確率記録部９７に格納する。
【０２４８】
ステップＳ１１０では、Ｗｈａｔ−ｉｆ予測確率記録部９７に格納されたＷｈａｔ−ｉｆ予測確率を外部装置２００に出力し、処理を終了する。
【０２４９】
以上説明したように、本発明の実施の形態に係るＷｈａｔ−ｉｆシミュレーション装置によれば、人が状態間を遷移した履歴を表す遷移履歴データ、及び状態間の基本遷移確率に基づいて、上記（１１）式及び（１２）式を用いて、各状態についての目的地らしさを表す報酬関数を推定し、障害物が置かれた状態の集合を表す障害物データに基づいて、上記（１３）式によって、状態間の基本遷移確率を更新し、推定された報酬関数と、更新された状態間の基本遷移確率とに基づいて、上記（１０）式に従って、各状態の目的地への到達しやすさを表す価値関数を計算し、計算された価値関数と、更新された状態間の基本遷移確率とに基づいて、上記（１４）式に従って、状態間の対象物の移動を予測するＷｈａｔ−ｉｆ予測確率を推定することにより、障害物が存在する状況における、人の流れを予測することができる。
【０２５０】
また、本発明の実施の形態に係るＷｈａｔ−ｉｆシミュレーション装置によって、これまで一度も発生したことのない自然災害などが起こった際の人の流れを予測することができるようになる。実際に自然災害が起こった時の予測に使えることはもちろん、もし起こったときにどうなるかというＷｈａｔ−ｉｆ予測も可能とすることができる。例えばＷｈａｔ−ｉｆ予測によって、東京駅が封鎖された際には、品川駅へ向かう人が増大し、ある道路が非常に混雑することが予測できれば、その道路に警官を配備するプランをあらかじめ策定しておくなどの対応策を検討しておくことができる。
【０２５１】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０２５２】
例えば、上記の実施の形態では、障害物データが入力として与えられ、上記（１３）式をもとに障害物有り基本遷移関数
【数９０】
0006464075.tif 000091
が求められているが、この例に限定されることはない。例えば、障害物有り基本遷移関数
【数９１】
0006464075.tif 000092
そのものが入力として与えられる場合を考えてもよい。また、上記の実施の形態の図３に示すＷｈａｔ−ｉｆシミュレーション装置は、各構成要素の動作をプログラムとして構築し、Ｗｈａｔ−ｉｆ予測装置として利用されるコンピュータにインストールして実行させる、またはネットワークを介して流通させることが可能である。
【０２５３】
また、移動する対象物が、人物である場合を例に説明したが、これに限定されるものではなく、移動する対象物として、人物以外のもの、例えば、ロボット、動物、車両などであってもよい。
【０２５４】
また、上述した実施の形態では、障害物データを用いて障害物有り基本遷移関数を計算する場合を例に説明したが、これに限定されるものではなく、障害物でない形式で記述されるデータ、例えばある状態間の遷移は不可、というような状態間の関係性で記述される状態遷移確率の変化に関するデータを用いて、状態遷移確率の変化を考慮した基本遷移関数を計算するようにしてもよい。
【符号の説明】
【０２５５】
１０   遷移履歴処理部
２０   基本遷移関数処理部
３０   報酬関数推定部
４０   障害物処理部
５０   障害物有り基本遷移関数計算部
６０   価値関数計算部
７０   Ｗｈａｔ−ｉｆ予測確率計算部
８０   Ｗｈａｔ−ｉｆ予測確率処理部
９０   記録部
９１   遷移履歴記録部
９２   基本遷移関数記録部
９３   報酬関数記録部
９４   障害物記録部
９５   障害物有り基本遷移関数記録部
９６   価値関数記録部
９７   Ｗｈａｔ−ｉｆ予測確率記録部
１００ Ｗｈａｔ−ｉｆシミュレーション装置
１５０ 入出力部
２００ 外部装置
【図１】
0006464075.tif 000093
【図２】
0006464075.tif 000094
【図３】
0006464075.tif 000095
【図４】
0006464075.tif 000096