情報処理装置、情報処理方法、およびプログラム
【課題】少ない消費電力で、必要十分な移動履歴データを蓄積することができるようにする。
【解決手段】類似検索部は、過去履歴DBに記憶されている検索用データのなかから、位置センサ部で取得された、時系列の位置データでなる直近の移動履歴と類似する過去の経路を検索する。適合判定部は、類似検索部で検索された過去の経路と、直近の移動履歴との適合度が所定の閾値以上であるかを判定する。センサ制御部は、適合判定部の判定結果に応じて、位置センサ部の位置データの取得間隔を制御する。この開示の技術は、例えば、位置データを取得して予測経路を予測する予測装置に適用できる。
【解決手段】類似検索部は、過去履歴DBに記憶されている検索用データのなかから、位置センサ部で取得された、時系列の位置データでなる直近の移動履歴と類似する過去の経路を検索する。適合判定部は、類似検索部で検索された過去の経路と、直近の移動履歴との適合度が所定の閾値以上であるかを判定する。センサ制御部は、適合判定部の判定結果に応じて、位置センサ部の位置データの取得間隔を制御する。この開示の技術は、例えば、位置データを取得して予測経路を予測する予測装置に適用できる。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、情報処理装置、情報処理方法、およびプログラムに関し、特に、少ない消費電力で、必要十分な移動履歴データを蓄積することができるようにする情報処理装置、情報処理方法、およびプログラムに関する。
【背景技術】
【０００２】
現在地を起点として、これからの移動経路を予測する方法として、現在の移動履歴と類似する経路を過去の移動履歴のデータベースから検索し、その結果得られた経路を予測経路として出力するものがある（例えば、特許文献１参照）。
【０００３】
このような予測方法では、データベースである過去の移動履歴を十分に蓄積することが必要である。また、蓄積された過去の移動履歴のデータの精度がよいことも重要である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−１５５１６７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
精度のよい移動履歴を蓄積するための一つの方法として、現在位置を取得する位置センサの取得間隔を短く設定することが挙げられる。
【０００６】
しかしながら、例えば、位置センサを搭載した携帯端末などでは、単純に取得間隔を短く設定すると電力消費が大きくなってしまうため、バッテリの持ち時間が短くなってしまう。
【０００７】
本技術は、このような状況に鑑みてなされたものであり、少ない消費電力で、必要十分な移動履歴データを蓄積することができるようにするものである。
【課題を解決するための手段】
【０００８】
本技術の一側面の情報処理装置は、時系列の位置データでなる直近の移動履歴を取得する位置センサ部と、検索用データを記憶する過去履歴DBと、前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索する類似検索部と、前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部とを備える。
【０００９】
本技術の一側面の情報処理方法は、検索用データを記憶する過去履歴DBを備える情報処理装置が、時系列の位置データでなる直近の移動履歴を取得し、前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索し、検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定し、判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するステップを含む。
【００１０】
本技術の一側面のプログラムは、コンピュータを、過去履歴DBに記憶されている検索用データのなかから、位置センサ部で取得された、時系列の位置データでなる直近の移動履歴と類似する過去の経路を検索する類似検索部と、前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部として機能させるためのものである。
【００１１】
本技術の一側面においては、過去履歴DBに記憶されている検索用データのなかから、位置センサ部で取得された、時系列の位置データでなる直近の移動履歴と類似する過去の経路が検索され、検索された過去の経路と、直近の移動履歴との適合度が所定の閾値以上であるかが判定され、その判定結果に応じて、位置センサ部の位置データの取得間隔が制御される。
【００１２】
プログラムは、伝送媒体を介して伝送することにより、又は、記録媒体に記録して、提供することができる。
【００１３】
情報処理装置は、独立した装置であっても良いし、１つの装置を構成している内部ブロックであっても良い。
【発明の効果】
【００１４】
本技術の一側面によれば、少ない消費電力で、必要十分な移動履歴データを蓄積することができる。
【図面の簡単な説明】
【００１５】
【図１】本技術を適用した予測装置の構成例を示すブロック図である。
【図２】予測処理を説明するフローチャートである。
【図３】第１のセンサ制御処理を説明するフローチャートである。
【図４】第２のセンサ制御処理を説明するフローチャートである。
【図５】データ修正処理を説明するフローチャートである。
【図６】予測装置の第１の実施の形態の構成例を示すブロック図である。
【図７】経路ログDBに記憶される過去の移動履歴のデータ例を示す図である。
【図８】目的地リストの例を示す図である。
【図９】過去の移動履歴と目的地を地図上に示した図である。
【図１０】予測値算出部による予測結果を示した図である。
【図１１】直近の移動履歴の修正について説明する図である。
【図１２】第１の実施の形態における予測処理を説明するフローチャートである。
【図１３】第１の実施の形態の絶対の出発予測時刻を用いた第２のセンサ制御処理を説明するフローチャートである。
【図１４】第１の実施の形態の相対の出発予測時刻を用いた第２のセンサ制御処理を説明するフローチャートである。
【図１５】第１の実施の形態のデータ修正処理を説明するフローチャートである。
【図１６】予測装置の第２の実施の形態の構成例を示すブロック図である。
【図１７】確率遷移モデルの概念図である。
【図１８】HMMの各状態ノードの観測モデルと内部モデルの例を示す図である。
【図１９】HMMに学習させたときの学習結果を地図上に示した図である。
【図２０】直近の移動履歴の修正について説明する図である。
【図２１】その他の直近の移動履歴の修正について説明する図である。
【図２２】学習装置の構成例を示すブロック図である。
【図２３】図２２の状態ノード割り当て部の詳細構成例を示すブロック図である。
【図２４】学習処理を説明するフローチャートである。
【図２５】適合度算出処理を説明するフローチャートである。
【図２６】既存ノード割り当て処理を説明するフローチャートである。
【図２７】新規ノード割り当て処理を説明するフローチャートである。
【図２８】モデル再構成処理を説明するフローチャートである。
【図２９】遷移頻度テーブルの例を示す図である。
【図３０】第２の実施の形態における予測処理を説明するフローチャートである。
【図３１】第２の実施の形態の絶対の出発予測時刻を用いた第２のセンサ制御処理を説明するフローチャートである。
【図３２】第２の実施の形態の相対の出発予測時刻を用いた第２のセンサ制御処理を説明するフローチャートである。
【図３３】第２の実施の形態のデータ修正処理を説明するフローチャートである。
【図３４】予測装置の第３の実施の形態の構成例を示すブロック図である。
【図３５】予測装置の第４の実施の形態の構成例を示すブロック図である。
【図３６】予測装置の第４の実施の形態の構成例を示すブロック図である。
【図３７】本技術が適用されたコンピュータの一実施の形態の構成例を示すブロック図である。
【発明を実施するための形態】
【００１６】
以下、本技術を実施するための形態（以下、実施の形態という）について説明する。なお、説明は以下の順序で行う。
１．予測装置の処理の概要
２．第１の実施の形態（経路ログのデータベースに基づく制御を行う構成例）
３．第２の実施の形態（確率遷移モデルのデータベースに基づく制御を行う構成例）
４．第３の実施の形態（第１の実施の形態と第２の実施の形態を選択的に実行可能な構成例）
５．第４の実施の形態（センサ制御機能とデータ修正機能のいずれか一方のみを備える構成例）
【００１７】
＜１．予測装置の処理の概要＞
［予測装置の構成例］
図１は、本技術が適用された予測装置の構成例を示すブロック図である。
【００１８】
図１の予測装置１は、GPS (Global Positioning System )センサ等の位置センサから取得した位置情報を基に、ユーザの移動経路を予測し、目的地と、その目的地に到達するまでの経路や予測時間などを予測する装置である。この予測装置１は、それ単独の携帯型の装置として構成されたり、あるいは、携帯電話機、タブレット端末、等の携帯端末の一部の装置として構成される。
【００１９】
予測装置１は、位置センサ部１１、バッファ１２、過去履歴DB１３、類似検索部１４、適合判定部１５、予測経路抽出部１６、出発時刻予測部１７、予測値算出部１８、センサ制御部１９、およびDB修正部２０により構成される。
【００２０】
位置センサ部１１は、自身の現在の位置を示す緯度経度のデータを、センサ制御部１９の制御により決定された一定の時間間隔で順次取得する。位置センサ部１１は、取得時刻（現在時刻）と、そのときの緯度、経度（のデータ）を、バッファ１２に供給する。
【００２１】
バッファ１２は、位置センサ部１１から供給される、時刻、緯度、及び経度のデータを、所定時間分だけ、一時的に保持する。そして、位置センサ部１１が時刻、緯度、及び経度のデータを取得する１回の動作を１ステップと呼ぶことにすると、バッファ１２は、現在時刻から所定ステップ数前までの時刻、緯度、及び経度の時系列データ（以下、直近の移動履歴と称する。）を類似検索部１４に供給する。
【００２２】
過去履歴DB１３は、予測装置１が移動経路や目的地を予測するのに必要な検索用データを記憶する。検索用データは、過去の移動履歴そのもの、あるいはそれを必要に応じて修正したもの、または、過去の移動履歴に対応する学習モデルである。なお、過去履歴DB１３に記憶される検索用データは、予測結果を利用するユーザ本人により生成されたものが望ましいが、他のユーザにより生成されたものでもよい。
【００２３】
また、過去履歴DB１３は、過去の移動履歴において目的地とされたリストである目的地リストも記憶する。目的地リストは、例えば、ユーザにより事前に入力されたり、所定時間（例えば、１時間）以上所定範囲（１００ｍ）以内に滞在している場所等を検出することで作成される。
【００２４】
類似検索部１４は、過去履歴DB１３に記憶された検索用データのなかから、バッファ１２から供給される直近の移動履歴と類似する過去の経路を検索し、検索結果を適合判定部１５に供給する。
【００２５】
適合判定部１５は、類似検索部１４で検索された検索用データの類似の経路が、取得された直近の移動履歴と適合するか否かを判定する。換言すれば、適合判定部１５は、取得された直近の移動履歴が、検索用データとして取得されている既知の経路であるか否かを、検索して得られた検索用データの類似の経路と、直近の移動履歴との適合度が所定の閾値以上であるか否かにより判定する。検索して得られた検索用データの類似の経路と、直近の移動履歴との適合度が所定の閾値以上である場合、適合判定部１５は、直近の移動経路を既知の経路と判定する。一方、検索された検索用データの類似の経路と、直近の移動履歴との適合度が所定の閾値未満である場合、適合判定部１５は、直近の移動経路を未知の経路と判定する。
【００２６】
適合判定部１５は、既知または未知の判定結果を、センサ制御部１９に供給する。また、適合判定部１５は、既知の経路と判定した場合、直近の移動経路を、予測経路抽出部１６およびDB修正部２０に供給する。
【００２７】
予測経路抽出部１６は、適合判定部１５から供給される既知の直近の移動履歴に基づいて、過去履歴DB１３の検索用データから予測経路を抽出する（ユーザの移動経路を予測する）。
【００２８】
また、予測経路抽出部１６は、抽出した予測経路から到達可能な目的地を、目的地リストに基づいてリストアップする。そして、予測経路抽出部１６は、抽出された目的地とそこに到達するための予測経路を予測値算出部１８に供給し、予測経路を出発時刻予測部１７に供給する。
【００２９】
出発時刻予測部１７は、ユーザが現在移動中か、または、止まっているかに関わらず、現在の位置を離れる時刻である出発時刻を、絶対値または相対値のいずれかで予測する。即ち、出発時刻予測部１７は、現在の位置から離れる出発時刻を絶対時刻として予測する。あるいは、出発時刻予測部１７は、現在の位置から離れるまでの時間（出発時間）を相対時刻として予測する。絶対時刻または相対時刻のいずれを使用するかは、例えば、ユーザの選択を受け付けて決定するようにしてもよい。出発時刻予測部１７は、予測結果である出発予測時刻をセンサ制御部１９に供給する。
【００３０】
予測値算出部１８は、予測経路抽出部１６から供給される、既知の直近の移動履歴に基づいて得られた目的地と予測経路に基づいて、予測値として、目的地までの到達時間、経路、および到達確率を算出して出力する。予測値算出部１８から出力された予測結果が、例えば、図示せぬディスプレイ等に表示される。また、予測値算出部１８の後段において、予測結果を用いた携帯端末の制御などが行われる。
【００３１】
センサ制御部１９には、適合判定部１５から、既知または未知の判定結果が供給される。また、センサ制御部１９には、出発時刻予測部１７から、絶対時刻または相対時刻のいずれかで表された出発予測時刻が供給される。
【００３２】
センサ制御部１９は、既知または未知の判定結果に応じて、位置センサ部１１が位置データを取得するデータ取得間隔を制御する。具体的には、センサ制御部１９は、既知の判定結果が供給された場合、データ取得間隔が短くなるように制御し、未知の判定結果が供給された場合、データ取得間隔が長くなるように制御する。
【００３３】
また、センサ制御部１９は、出発時刻予測部１７から供給される出発予測時刻に応じて、位置センサ部１１のデータ取得間隔を制御することもできる。具体的には、センサ制御部１９は、出発時刻まで余裕がある場合には、データ取得間隔が短くなるように制御し、出発時刻がすぐである場合、データ取得間隔が長くなるように制御する。出発時刻がすぐである場合には、ユーザが移動中である場合も含まれる。
【００３４】
DB修正部２０には、既知の直近の移動履歴が適合判定部１５から供給される。DB修正部２０は、過去履歴DB１３に記憶されている検索用データに基づいて、適合判定部１５から供給された既知の直近の移動履歴を修正し、過去履歴DB１３に供給する。
【００３５】
従って、図１では図示を省略しているが、予測経路抽出部１６、予測値算出部１８、DB修正部２０などは、必要に応じて過去履歴DB１３の検索用データを取得して処理を行う。
【００３６】
以上のように構成される予測装置１は、位置センサ部１１で取得される直近の既知の移動履歴に基づいて、ユーザの、現在地からの移動経路、目的地、目的地に行くまでにかかる時間等を予測する予測処理を行う。
【００３７】
また、予測装置１は、位置センサ部１１で取得される直近の移動履歴が既知かまたは未知かに基づいて、位置センサ部１１のデータ取得間隔を制御（変更）するセンサ制御処理を行う。
【００３８】
さらに、予測装置１は、位置センサ部１１で取得される既知の直近の移動履歴に基づいて、直近の移動履歴（のデータ）を修正するデータ修正処理を行う。
【００３９】
以下、予測処理、センサ制御処理、およびデータ修正処理のそれぞれについて、図２乃至図５のフローチャートを参照して説明する。
【００４０】
［予測処理のフローチャート］
図２は、図１の予測装置１が行う予測処理のフローチャートである。なお図２乃至図５においては、位置センサ部１１のデータ取得およびバッファ１２のバッファリングは常時行われているものとする。
【００４１】
初めに、ステップＳ１では、類似検索部１４は、過去履歴DB１３から、検索用データを取得する。
【００４２】
ステップＳ２において、類似検索部１４は、バッファ１２から、直近の移動履歴を取得する。
【００４３】
ステップＳ３において、類似検索部１４は、取得した検索用データのなかから、直近の移動履歴と類似する経路を検索し、検索結果を適合判定部１５に供給する。直近の移動履歴が検索用データのどの経路と類似するかの検索は、直近の移動履歴と検索用データの経路との適合度（類似度）を、全ての検索用データについて算出することにより行われる。
【００４４】
ステップＳ４において、適合判定部１５は、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であるかを判定する。
【００４５】
ステップＳ４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値未満であると判定された場合、予測処理は終了する。即ち、直近の移動履歴が未知の経路である場合には、予測ができないとして処理を終了する。
【００４６】
一方、ステップＳ４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であると判定された場合、処理はステップＳ５に進み、予測経路抽出部１６は、過去履歴DB１３の検索用データから、目的地と予測経路を抽出する。
【００４７】
そして、ステップＳ６において、予測値算出部１８は、抽出された予測経路に基づいて、目的地までの到達時間、経路、及び到達確率を、予測値として算出して出力し、処理を終了する。
【００４８】
［第１のセンサ制御処理のフローチャート］
図３は、適合判定部１５からの既知または未知の判定結果のみに基づいて、位置センサ部１１のデータ取得間隔を制御する第１のセンサ制御処理のフローチャートである。
【００４９】
初めに、ステップＳ１１において、類似検索部１４は、過去履歴DB１３から、検索用データを取得する。
【００５０】
ステップＳ１２において、類似検索部１４は、バッファ１２から、直近の移動履歴を取得する。
【００５１】
ステップＳ１３において、類似検索部１４は、取得した検索用データのなかから、直近の移動履歴と類似する経路を検索し、検索結果を適合判定部１５に供給する。直近の移動履歴が検索用データのどの経路と類似するかの検索は、直近の移動履歴と検索用データの経路との適合度（類似度）を、全ての検索用データについて算出することにより行われる。
【００５２】
ステップＳ１４において、適合判定部１５は、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であるかを判定する。
【００５３】
以上のステップＳ１１乃至Ｓ１４の処理は、図１のステップＳ１乃至Ｓ４の処理と同一であり、１つの処理を、予測処理とセンサ制御処理が共通に利用している。
【００５４】
ステップＳ１４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値未満であると判定された場合、即ち、直近の移動履歴が未知の経路である場合、処理はステップＳ１５に進み、センサ制御部１９は、データ取得間隔が短くなるように制御して、処理を終了する。
【００５５】
一方、ステップＳ１４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であると判定された場合、即ち、直近の移動履歴が既知の経路である場合、処理はステップＳ１６に進み、センサ制御部１９は、データ取得間隔が長くなるように制御して、処理を終了する。
【００５６】
図３の処理は繰り返し実行される。
【００５７】
以上のように、第１のセンサ制御処理では、直近の移動履歴が既知であれば、既に学習している経路であるので、データ取得間隔が長く設定される。一方、直近の移動履歴が未知であれば、検索用データとして蓄積する必要があるので、精密なデータを取得するため、データ取得間隔が短く設定される。これにより、不要な時にはデータ取得間隔を長くすることができるので、少ない消費電力で、必要十分な移動履歴データを蓄積することができる。
【００５８】
［第２のセンサ制御処理のフローチャート］
図４は、既知または未知の判定結果と出発予測時刻に基づいて、位置センサ部１１のデータ取得間隔を制御する第２のセンサ制御処理のフローチャートである。
【００５９】
図４のステップＳ２１乃至Ｓ２５は、図３のステップＳ１１乃至Ｓ１５とそれぞれ同様であるので、その説明は省略する。
【００６０】
ステップＳ２４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であると判定された場合、処理はステップＳ２６に進み、出発時刻予測部１７は、現在の位置を離れる時刻である出発時刻を、絶対時刻または相対時刻のいずれかで予測する。出発時刻予測部１７の予測結果である出発予測時刻は、センサ制御部１９に供給される。
【００６１】
そして、ステップＳ２７において、センサ制御部１９は、出発時刻予測部１７から供給された出発予測時刻が所定時間より後であるかを判定する。
【００６２】
ステップＳ２７で、出発予測時刻が所定時間より後ではないと判定された場合、即ち、移動中のときのように、出発時刻がすぐである場合、処理はステップＳ２８に進み、センサ制御部１９は、データ取得間隔が短くなるように制御する。
【００６３】
一方、ステップＳ２７で、出発予測時刻が所定時間より後であると判定された場合、即ち、出発時刻まで余裕がある場合、処理はステップＳ２９に進み、センサ制御部１９は、データ取得間隔が長くなるように制御する。
【００６４】
図４の処理は繰り返し実行される。
【００６５】
以上のように、第２のセンサ制御処理では、直近の移動経路が既知であっても、例えば、移動中である場合には、データ取得間隔が短く設定され、目的地に滞在していたり、電車待ちなど、現在地からしばらく動かない場合には、データ取得間隔が長く設定される。
【００６６】
これにより、不要な時にはデータ取得間隔を長くすることができるので、少ない消費電力で、必要十分な移動履歴データを蓄積することができる。
【００６７】
なお、上述した例では、データ取得間隔を、短い設定時間（例えば、１分）と、長い設定時間（例えば、５分）の二段階としたが、三段階以上に分けてもよい。
【００６８】
［データ修正処理のフローチャート］
図５は、図１の予測装置１が行うデータ修正処理のフローチャートである。
【００６９】
図５のステップＳ４１乃至Ｓ４４の処理は、図１のステップＳ１乃至Ｓ４、および図２のステップＳ１１乃至Ｓ１４の処理と同様であるので、その説明は省略する。即ち、ステップＳ４１乃至Ｓ４４の処理は、１つの処理を、予測処理、センサ制御処理、及びデータ修正処理が共通に利用している。
【００７０】
ステップＳ４４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値未満であると判定された場合、データ修正処理は終了する。即ち、直近の移動履歴が未知の経路である場合には、検索用データとしての蓄積がないため、修正ができないとして処理を終了する。
【００７１】
一方、ステップＳ４４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であると判定された場合、処理はステップＳ４５に進み、DB修正部２０は、検索用データを用いて直近の移動履歴を修正する。そして、DB修正部２０は、修正後の直近の移動履歴を過去履歴DB１３に供給して、処理を終了する。
【００７２】
図５の処理は繰り返し実行される。
【００７３】
以上のように、データ修正処理では、検索用データに基づいて、直近の移動履歴を修正して、過去履歴DB１３に供給することができるので、過去の移動履歴として蓄積するデータ（検索用データ）の精度を向上させることができる。
【００７４】
以上、図１乃至図５を参照して、図１の予測装置１の処理の概要について説明した。
【００７５】
図１の予測装置１は、検索用データを過去履歴DB１３にどのように持たせるかによって、予測処理、センサ制御処理、およびデータ修正処理のそれぞれを、異なる方法で実行することができる。
【００７６】
１つは、取得された時刻、緯度、および経度の時系列データである経路ログを検索用データとして過去履歴DB１３に記憶させ、その経路ログを用いて行う方法である。他の１つは、取得された時刻、緯度、および経度の時系列データを学習した学習モデルを検索用データとして過去履歴DB１３に記憶させ、その学習モデルを用いて行う方法である。学習モデルには、例えば、確率遷移モデルが採用される。
【００７７】
以下では、経路ログを用いて行う場合を、予測装置１の第１の実施の形態として説明し、学習モデルを用いて行う場合を、予測装置１の第２の実施の形態として説明する。
【００７８】
＜２．第１の実施の形態＞
［第１の実施の形態の予測装置１の構成例］
図６は、第１の実施の形態における予測装置１の構成例を示すブロック図である。
【００７９】
図６の経路ログDB１３A、類似経路検索部１４A、適合判定部１５A、予測経路ログ抽出部１６A、出発時刻予測部１７A、予測値算出部１８A、および検索ログ修正部２０Aが、図１の過去履歴DB１３、類似検索部１４、適合判定部１５、予測経路抽出部１６、出発時刻予測部１７、予測値算出部１８、およびDB修正部２０に対応する。
【００８０】
経路ログDB１３Aは、過去の移動履歴と、目的地リストを記憶する。
【００８１】
図７は、経路ログDB１３Aに記憶される過去の移動履歴のデータ例を示している。図７に示されるように、取得された時刻と位置（経度、緯度）が、取得された時間順に記憶される。取得間隔は、センサ制御部１９により制御された所定の時間間隔である。
【００８２】
なお、位置センサ部１１が位置のデータを一定間隔に取得することができない場合もある。例えば、トンネルや地下にいる場合などには、人工衛星を捕捉することができず、取得間隔が長くなることもある。そのような場合には、例えば、線形補間により等間隔に補間されてから記憶される。過去の移動履歴には、取得時刻の古い順に、例えば、通し番号等が付されて記憶されている。
【００８３】
図８は、経路ログDB１３Aに記憶される目的地リストの例を示している。
【００８４】
目的地リストは、目的地に対して順に付されたインデックスと、目的地の位置（経度、緯度）とから構成される。
【００８５】
図９は、経路ログDB１３Aに記憶されている、過去の移動履歴と、目的地リストに記載されている目的地を地図上に示した図である。
【００８６】
図９において、丸（○）で囲まれた位置の中心が目的地であり、それらをつなぐように示される灰色の点が、過去の移動履歴をプロットしたものである。
【００８７】
図６に戻り、類似経路検索部１４Aは、経路ログDB１３Aの過去の移動履歴をスキャンして、バッファ１２から供給される直近の移動履歴と、過去の移動履歴の各箇所（位置）との類似度を算出する。
【００８８】
類似経路検索部１４Aにおいて、過去の移動履歴のｉ番目の箇所と、直近の移動履歴との類似度Ｄ（ｉ）は、次式（１）で計算される。
【数１】
【００８９】
式（１）のｘpastは、過去の移動履歴を表し、ｘcurrentは、直近の移動履歴を表す。右下の添え字は、過去の移動履歴または直近の移動履歴の通し番号を表す。また、式（１）のDistance(x,y)は、二つの箇所ｘとｙとの距離を求める関数であり、ユークリッド距離、若しくは、市街地距離（直交方向の差ベクトルの成分の和）、または、それらの二乗などとすることができる。Σは、Kステップ分についての和を表す。
【００９０】
従って、式（１）の類似度Ｄ（ｉ）は、バッファ１２から供給される直近の移動履歴がＫステップ分の位置データであり、Ｋステップ分の直近の移動履歴と、過去の移動履歴のなかのｉ番目から過去Ｋステップ分の移動履歴との、対応するステップ間の距離（総和）に相当する。
【００９１】
なお、式（１）でマイナスを乗じているのは、類似するほど、類似度Ｄ（ｉ）が大きい値となるようにするためである。
【００９２】
式（１）の類似度Ｄ（ｉ）は、Kステップ分についての和を、さらにステップ数Kで除算して、距離の平均としてもよい。
【００９３】
なお、類似度Ｄ（ｉ）の算出方法は、これに限定されるものではない。例えば、もっと簡便に、直近の移動履歴の中から、直近の箇所と、所定時間前のもう一箇所を選択し、過去の移動履歴の中から、選択した直近の二箇所に近く、また、所定時間程度の間隔にある二箇所を検出して、検出された二箇所と直近の二箇所の対応する箇所どうしの距離を利用するものでもよい。
【００９４】
類似経路検索部１４Aは、式（１）の類似度Ｄ（ｉ）を適合度として求め、適合判定部１５Aに供給する。
【００９５】
適合判定部１５Aは、類似経路検索部１４Aにより求められた、過去の移動履歴の各箇所と直近の移動履歴の適合度が、所定の閾値以上であるかを判定し、取得された直近の移動履歴と適合する過去の移動履歴があるかを判定する。
【００９６】
予測経路ログ抽出部１６Aは、所定の閾値以上であるとして検出された過去の移動履歴の箇所に対して、経路ログDB１３Aの目的地リストのいずれかに至るまでの移動履歴を、予測経路として抽出する。所定の閾値以上であるとして検出された過去の移動履歴の箇所は、複数検出されることがある。
【００９７】
予測経路ログ抽出部１６Aは、抽出した予測経路から到達可能な目的地を、経路ログDB１３Aの目的地リストに基づいて、目的地ごとにリストアップする。
【００９８】
予測値算出部１８Aは、リストアップされた目的地ごとに、目的地への経路リストおよび代表経路、到達確率、並びに所要時間を算出する。
【００９９】
目的地への代表経路には、抽出された目的地への経路リストのうち、例えば、所要時間の最も短いものが採用される。その他、抽出された複数の予測経路の平均所要時間に最も近い予測経路を、代表経路としてもよい。
【０１００】
目的地の到達確率は、抽出された予測経路の全数を分母として、その目的地へ到達できる予測経路の本数を分子として算出することができる。
【０１０１】
目的地の所要時間は、その目的地への予測経路それぞれの所要時間の平均値とすることができる。なお、目的地の所要時間の算出には、明らかな異常値の予測経路については除外した平均値としてもよい。
【０１０２】
図１０は、予測値算出部１８Aにより得られた各目的地と、それぞれの目的地への到達確率と所要時間を地図上に示した例である。
【０１０３】
図６に戻り、出発時刻予測部１７Aは、予測経路ログ抽出部１６Aにより抽出された、適合度が所定の閾値以上の箇所を起点とした１以上の予測経路から、絶対または相対の出発時刻を算出し、センサ制御部１９に供給する。
【０１０４】
絶対の出発時刻を求める場合には、出発時刻予測部１７Aは、起点を中心とする所定の範囲（例えば、半径１００ｍ）を設定範囲として、初めて設定範囲から外にでるときの過去の時刻の平均値を算出し、絶対の出発時刻とする。
【０１０５】
相対の出発時刻を求める場合には、出発時刻予測部１７Aは、起点を中心とする所定の範囲（例えば、半径１００ｍ）を設定範囲として、設定範囲内にどれくらいのステップ数（時間）だけ滞在していたかを算出し、その平均値を相対の出発時刻（予測滞在時間）とする。
【０１０６】
絶対時刻は、例えば、オフィスへの出勤、退勤など習慣があり、行動の時間帯に規則性がある場合の予測に適している。一方、相対時刻は、休日の外出（買い物や散髪など）など、行動の時間帯に規則性がない場合の予測に適している。
【０１０７】
検索ログ修正部２０Aは、所定の閾値以上であるとして検出された過去の移動履歴を用いて、直近の移動履歴を修正し、修正後の直近の移動履歴を経路ログDB１３Aに供給する。
【０１０８】
図１１を参照して、検索ログ修正部２０Aによる直近の移動履歴の修正について説明する。
【０１０９】
検索ログ修正部２０Aは、所定の閾値以上であるとして検出された過去の移動履歴の箇所を起点とする、直近の移動履歴と同ステップ数（Kステップ）の過去の移動履歴を、経路ログDB１３A内で検索し、検索データとして切り出す。
【０１１０】
そして、検索ログ修正部２０Aは、切り出された１以上の検索データに対して、ステップごとの平均値を算出し、理想系列を生成する。さらに、検索ログ修正部２０Aは、理想系列と直近の移動履歴の平均を算出し、修正後の直近の移動履歴を生成する。
【０１１１】
図１１において、直近の移動履歴の黒丸（●）が最新の位置データ（箇所）であり、検索データの黒三角（▲）が、最新の位置データに対応する過去の移動履歴の箇所（起点）である。同様に、理想系列の白三角（△）と、修正後の移動履歴の白丸（○）も、直近の移動履歴の最新の位置データに対応する箇所である。
【０１１２】
なお、この例では、起点からのステップ数を、類似度を求める場合のステップ数と同一としたが、類似度を求める場合と異なるステップ数としてもよい。
【０１１３】
また、上述した例では、修正後の直近の移動履歴を単純平均により求めたが、理想系列と直近の移動履歴とで、理想系列に対する重みを重く設定した重み付け平均により求めてもよい。同様に、理想系列を求める場合も、より過去の移動履歴については重みを小さく設定するような重み付き平均により求めてもよい。
【０１１４】
この修正処理により、直近の移動履歴を、自動的に統計的に処理された位置に修正して、経路ログDB１３Aに蓄積させることができる。
【０１１５】
［予測処理のフローチャート］
図１２のフローチャートを参照して、第１の実施の形態における予測処理について説明する。
【０１１６】
初めに、ステップＳ６１において、類似経路検索部１４Aは、過去の移動履歴と目的地リストを経路ログDB１３Aから取得する。
【０１１７】
ステップＳ６２において、類似経路検索部１４Aは、バッファ１２から、直近の移動履歴を取得する。
【０１１８】
ステップＳ６３において、類似経路検索部１４Aは、過去の移動履歴をスキャンして、過去の移動履歴の各箇所（位置）について、直近の移動履歴との適合度を算出する。ここで、適合度には、例えば、式（１）の類似度Ｄ（ｉ）が採用される。
【０１１９】
ステップＳ６４において、適合判定部１５Aは、類似経路検索部１４Aにより求められた適合度に基づいて、所定の閾値以上の適合度を有する箇所が１以上あるかを判定する。
【０１２０】
ステップＳ６４で、所定の閾値以上の適合度を有する箇所が１つもないと判定された場合、予測処理は終了する。一方、ステップＳ６４で、所定の閾値以上の適合度を有する箇所が１以上あると判定された場合、処理はステップＳ６５に進む。
【０１２１】
ステップＳ６５において、予測経路ログ抽出部１６Aは、所定の閾値以上の適合度を有する箇所を選択する。
【０１２２】
そして、ステップＳ６６において、予測経路ログ抽出部１６Aは、選択した箇所（選択箇所）それぞれについて、選択箇所からいずれかの目的地に至るまでの過去の移動履歴を、予測経路として抽出する。
【０１２３】
ステップＳ６７において、予測経路ログ抽出部１６Aは、抽出した予測経路から到達可能な目的地を、経路ログDB１３Aの目的地リストに基づいて、目的地ごとにリストアップする。
【０１２４】
そして、ステップＳ６８において、予測値算出部１８Aは、リストアップされた目的地ごとに、目的地への経路リストおよび代表経路を算出する。代表経路には、例えば、目的地への複数の予測経路のうち、所要時間の最も短いものが採用される。
【０１２５】
ステップＳ６９において、予測値算出部１８Aは、各目的地への到達確率を算出し、ステップＳ７０において、各目的地への所要時間を算出して出力し、処理を終了する。
【０１２６】
［絶対の出発予測時刻を用いた第２のセンサ制御処理のフローチャート］
次に、図１３のフローチャートを参照して、第１の実施の形態における、絶対の出発予測時刻を用いた第２のセンサ制御処理について説明する。
【０１２７】
図１３のステップＳ８１乃至Ｓ８４は、図１２のステップＳ６１乃至Ｓ６４と同様であるので、その説明は省略する。
【０１２８】
ステップＳ８４で、所定の閾値以上の適合度を有する箇所が１つもないと判定された場合、処理はステップＳ８５に進み、センサ制御部１９は、位置センサ部１１を、データ取得間隔が短くなるように制御して、処理を終了する。
【０１２９】
一方、ステップＳ８４で、所定の閾値以上の適合度を有する箇所が１以上あると判定された場合、処理はステップＳ８６に進み、予測経路ログ抽出部１６Aは、所定の閾値以上の適合度を有する箇所を選択する。
【０１３０】
ステップＳ８７において、出発時刻予測部１７Aは、適合度が所定の閾値以上の選択箇所から、最初に設定範囲外に出るときの過去の時刻の平均値を算出し、絶対の出発時刻とする。算出された絶対の出発時刻は、センサ制御部１９に供給される。
【０１３１】
ステップＳ８８において、センサ制御部１９は、出発時刻予測部１７Aから供給された絶対の出発時刻と、現在時刻との差分を算出する。
【０１３２】
そして、ステップＳ８９において、センサ制御部１９は、算出された差分が所定の閾値（以下、出発時刻閾値という。）より大であるかを判定する。
【０１３３】
ステップＳ８９で、算出された差分が出発時刻閾値以下であると判定された場合、処理はステップＳ９０に進み、センサ制御部１９は、データ取得間隔が短くなるように制御して、処理を終了する。
【０１３４】
一方、ステップＳ８９で、算出された差分が出発時刻閾値より大であると判定された場合、処理はステップＳ９１に進み、センサ制御部１９は、データ取得間隔が長くなるように制御して、処理を終了する。
【０１３５】
第１の実施の形態における第１のセンサ制御処理は、上述したステップＳ８６乃至Ｓ９０を省略した処理となる。
【０１３６】
［相対の出発予測時刻を用いた第２のセンサ制御処理のフローチャート］
図１４のフローチャートを参照して、第１の実施の形態における、相対の出発予測時刻を用いた第２のセンサ制御処理について説明する。
【０１３７】
図１４の相対の出発予測時刻を用いた第２のセンサ制御処理は、図１３の絶対の出発予測時刻を用いた第２のセンサ制御処理と比較すると、図１３のステップＳ８７乃至Ｓ８９に対応するステップＳ１０７およびＳ１０８が異なるのみである。従って、図１４では、ステップＳ１０７およびＳ１０８の処理のみ説明し、それ以外の説明は省略する。
【０１３８】
ステップＳ１０７において、出発時刻予測部１７Aは、選択箇所を中心とする設定範囲内を離れるまでの時間（ステップ数）の平均値を予測滞在時間として算出する。
【０１３９】
ステップＳ１０８において、出発時刻予測部１７Aは、算出された予測滞在時間が所定の閾値（以下、滞在時間閾値という。）より大であるかを判定する。
【０１４０】
ステップＳ１０８で、算出された予測滞在時間が滞在時間閾値以下であると判定された場合、処理はステップＳ１０９に進む。
【０１４１】
一方、ステップＳ１０８で、算出された予測滞在時間が滞在時間閾値より大であると判定された場合、処理はステップＳ１１０に進む。
【０１４２】
ステップＳ１０９またはＳ１１０において、所定のデータ取得間隔がセンサ制御部１９に設定されて、処理は終了する。
【０１４３】
以上のように、絶対の出発予測時刻を用いた第２のセンサ制御処理、または、相対の出発予測時刻を用いた第２のセンサ制御処理は行われるが、両者の処理結果を組み合わせた結果に基づいて、最終的にデータ取得間隔を決定するようにしてもよい。
【０１４４】
［データ修正処理のフローチャート］
次に、図１５のフローチャートを参照して、第１の実施の形態における、データ修正処理について説明する。
【０１４５】
図１５のステップＳ１２１乃至Ｓ１２５は、図１２のステップＳ６１乃至Ｓ６５と同様であるので、その説明は省略する。
【０１４６】
ステップＳ１２６において、検索ログ修正部２０Aは、選択箇所を起点とする数ステップ（Kステップ）の過去の移動履歴を、経路ログDB１３A内で検索し、検索データとして切り出す。これにより、１以上の検索データが切り出される。
【０１４７】
ステップＳ１２７において、検索ログ修正部２０Aは、切り出した１以上の検索データに対して、ステップごとの平均値を算出し、理想系列を生成する。
【０１４８】
ステップＳ１２８において、検索ログ修正部２０Aは、理想系列と直近の移動履歴の平均を算出することで、修正後の直近の移動履歴を生成して、処理を終了する。
【０１４９】
以上のように、予測装置１の第１の実施の形態では、過去履歴DB１３に記憶されている経路ログを用いて、予測処理、センサ制御処理、およびデータ修正処理を行うことができる。
【０１５０】
＜３．第２の実施の形態＞
［第２の実施の形態の予測装置１の構成例］
図１６は、第２の実施の形態における予測装置１の構成例を示すブロック図である。
【０１５１】
図１６の確率遷移モデルDB１３B、類似ノード検索部１４B、適合判定部１５B、予測ノード探索部１６B、出発時刻予測部１７B、予測値算出部１８B、およびモデル用データ修正部２０Bが、図１の過去履歴DB１３、類似検索部１４、適合判定部１５、予測経路抽出部１６、出発時刻予測部１７、予測値算出部１８、およびDB修正部２０に対応する。
【０１５２】
確率遷移モデルDB１３Bは、過去の移動履歴を学習モデルとしての確率遷移モデルにより学習した結果を記憶する。換言すれば、確率遷移モデルDB１３Bには、過去の移動履歴を学習モデルとしての確率遷移モデルで学習して得られたパラメータが検索用データとして記憶される。
【０１５３】
また、確率遷移モデルDB１３Bには、モデル用データ修正部２０Bから、新たな移動履歴が供給されるので、確率遷移モデルDB１３Bは、所定のタイミングで（例えば、一日おき、一週間おきなど）新たな移動履歴を用いて確率遷移モデルのパラメータを更新し、記憶する。
【０１５４】
さらに、確率遷移モデルDB１３Bは、第１の実施の形態における経路ログDB１３Aと同様に、目的地リストも記憶する。
【０１５５】
図１７は、過去の移動履歴を学習するための確率遷移モデルの概念図である。
【０１５６】
図１７に示される確率遷移モデルは、状態数が３（N=３）の隠れマルコフモデル（以下、HMMという。）を示している。HMMは、複数の離散化された状態ノードsiで構成される。さらに詳しく言えば、HMMは、複数の離散化された状態ノードsiについての、正規分布を持つ確率変数などで表される状態を決めるパラメータと、状態遷移を決めるパラメータで表現される。以下では、状態を決めるパラメータと状態遷移を決めるパラメータの両者を合わせて、HMMのパラメータともいい、状態ノードは、単に状態ともいう。
【０１５７】
状態を決めるパラメータは、状態ノードsiの観測モデルであり、状態ノードsiの中心値（平均値）μiと分散値σi2で構成される。状態遷移を決めるパラメータは、状態ノードsiの内部モデルであり、状態ノードsiから状態ノードsjへの状態遷移確率aijで構成される。
【０１５８】
図１８は、学習モデルとしてのHMMに過去の移動履歴を学習させた場合の、HMMの各状態ノードの観測モデルと内部モデルの例を示している。
【０１５９】
内部モデルとしての状態遷移確率aijには、自分の状態ノードsiへ遷移する自己遷移確率も存在する。観測モデルとしての状態ノードsiの中心値μiと分散値σi2は、時刻、経度、及び緯度のそれぞれについて求められる。なお、学習初期の各状態ノードsiには、初期状態を表す初期値が適宜設定される。
【０１６０】
図１９は、図９に示した過去の移動履歴と目的地を確率遷移モデルとしてのHMMに学習させたときの学習結果を地図上に示した図である。図１９において、経路上をつなぐように示される略楕円が、学習された各状態ノードを示している。
【０１６１】
HMMのパラメータを推定する方法としては、Baum-Welchの再尤推定法が広く利用されている。Baum-Welchの再尤推定法は、EMアルゴリズム(EM(Expectation-Maximization) algorithm)に基づくパラメータの推定方法である。
【０１６２】
Baum-Welchの再尤推定法によれば、観測される時系列データx=x1,x2,・・・,xTに基づき、その時系列データが観測（生起）される確率である生起確率から求まる尤度を最大化するように、HMMのパラメータの推定が行われる。ここで、xtは、時刻tに観測される信号（サンプル値）を表し、Tは、時系列データの長さ（サンプル数）を表す。
【０１６３】
Baum-Welchの再尤推定法については、例えば、“パターン認識と学習のアルゴリズム”，上坂吉則・尾関和彦著，文一総合出版，P.121に記載されている。
【０１６４】
図１６に戻り、類似ノード検索部１４Bは、バッファ１２から供給される直近の移動履歴に対応する確率遷移モデルの状態ノードを検索する。換言すれば、類似ノード検索部１４Bは、直近の移動履歴の現在地（最新の箇所）に対応する状態ノードの状態確率が最大となる状態ノードを探索（選択）する。
【０１６５】
適合判定部１５Bは、直近の移動履歴の現在地に対応する状態ノードの適合度が、所定の閾値以上であるかを判定する。確率遷移モデルを用いた場合の適合度の算出方法については後述する。直近の移動履歴の現在地に対応する状態ノードの適合度が所定の閾値以上である場合、既知の判定結果が、センサ制御部１９、予測ノード探索部１６B、およびモデル用データ修正部２０Bに供給される。また、探索して得られた状態ノードが、予測ノード探索部１６Bとモデル用データ修正部２０Bに供給される。一方、直近の移動履歴（の現在地）に対応する状態ノードの適合度が所定の閾値未満である場合、未知の判定結果が、センサ制御部１９に供給される。
【０１６６】
予測ノード探索部１６Bは、適合判定部１５B供給される、探索して得られた現在地に対応する状態ノードから、遷移可能な目的地の状態ノード（目的地ノード）をツリー探索することにより、目的地を探索する。そして、予測ノード探索部１６Bは、探索された目的地を、目的地ごとにリストアップする。
【０１６７】
予測値算出部１８Bは、リストアップされた目的地ごとに、目的地への経路リストおよび代表経路、到達確率、並びに、所要時間を算出する。
【０１６８】
出発時刻予測部１７Bは、探索して得られた現在地に対応する状態ノードに基づいて、絶対または相対の出発時刻を算出し、センサ制御部１９に供給する。
【０１６９】
絶対の出発時刻は、探索して得られた現在地に対応する状態ノードの自己遷移以外の１以上の遷移先の時刻の中心値の平均により求めることができる。あるいは、探索して得られた現在地に対応する状態ノードの自己遷移以外の遷移先の時刻のなかで、最も現在時刻に近い将来の時刻を中心値としてもつものを、絶対の出発時刻として選択するようにしてもよい。
【０１７０】
また、相対の出発時刻（予測滞在時間）は、探索して得られた現在地に対応する状態ノードの自己遷移確率を用いた次式（２）に、単位ステップの時間を乗算した値により求めることができる。
【０１７１】
【数２】
式（２）において、ｔstayが予測滞在時間を表し、ａssは、探索して得られた状態ノードを表す。なお、式（２）は、自己遷移確率が１であるとき発散するので、予測滞在時間には上限値を設定しておく方がよい。
【０１７２】
モデル用データ修正部２０Bは、直近の移動履歴に対応する状態ノードの状態ノード系列を用いて、直近の移動履歴を修正し、修正後の直近の移動履歴を確率遷移モデルDB１３Bに供給する。
【０１７３】
図２０を参照して、モデル用データ修正部２０Bによる直近の移動履歴の修正について説明する。
【０１７４】
モデル用データ修正部２０Bは、直近の移動履歴に対応する状態ノードの状態ノード系列（対応ノード系列）を生成し、生成された対応ノード系列の中心値の系列を、理想系列として生成する。そして、モデル用データ修正部２０Bは、理想系列と直近の移動履歴の平均を算出し、修正後の直近の移動履歴を生成する。
【０１７５】
図２１は、モデル用データ修正部２０Bによる、その他の修正方法を示している。
【０１７６】
図２１に示される修正方法が、図２０に示した修正方法と異なる点は、直近の移動履歴の各ステップに対して、確率遷移モデルを構成する各状態ノードの確率を用いる点である。即ち、図２１では、直近の移動履歴の各ステップに対する各状態ノードの確率δj(t)が確率テーブルとして示されている。直近の移動履歴の各ステップに対する各状態ノードの確率δj(t)の算出方法は、後述する式（５）で求められる。
【０１７７】
モデル用データ修正部２０Bは、直近の移動履歴に対応する理想系列を、確率テーブルを用いた次式（３）で算出する。
【数３】
【０１７８】
式（３）は、直近の移動履歴の各ステップについて、各状態ノードの緯度および経度の中心値μjを、状態ノードの確率δj(t)で重み付けして加算した値を、直近の移動履歴の各ステップに対応する理想系列の位置<xt>とすることを表す。ここで、tは、直近の移動履歴の各ステップの取得時刻に対応するステップ数（通し番号）である。
【０１７９】
[学習装置の構成例]
次に、確率遷移モデルDB１３Bに記憶される確率遷移モデルを学習する学習装置について説明する。
【０１８０】
図２２は、確率遷移モデルDB１３Bに記憶される確率遷移モデルのパラメータを求める学習装置６０の構成例を示している。
【０１８１】
学習装置６０は、ログ取得部６１、前処理部６２、状態ノード割り当て部６３、モデル再構成部６４、目的地リスト修正部６５、およびモデル記憶部６６により構成される。
【０１８２】
ログ取得部６１は、学習データとしての過去の移動履歴を取得し、前処理部６２に供給する。
【０１８３】
前処理部６２は、学習データの一時的なデータの欠落部分に対し、線形補間等の補間処理を行うことで補間して、処理後の過去の移動履歴を状態ノード割り当て部６３に供給する。
【０１８４】
状態ノード割り当て部６３は、前処理部６２から供給された過去の移動履歴に対し、確率遷移モデルの状態ノードを割り当てる。より具体的には、状態ノード割り当て部６３は、学習データである過去の移動履歴の各位置データに対して既存の確率遷移モデルとの適合度を算出し、適合度が所定の閾値以上であるか否かを判定する。そして、適合度が所定の閾値以上である場合、状態ノード割り当て部６３は、その位置データに対しては既存の状態ノードを割り当てる。一方、適合度が所定の閾値未満である場合、状態ノード割り当て部６３は、その位置データに対しては新規の状態ノードを割り当てる。そして、過去の移動履歴に対応して割り当てられた、状態ノードのノード番号の系列データ（対応ノード系列）が、モデル再構成部６４に供給される。
【０１８５】
モデル再構成部６４は、状態ノード割り当て部６３からの対応ノード系列に基づいて、確率遷移モデルを再構成するモデル再構成処理を行う。即ち、モデル再構成部６４は、現在の確率遷移モデルの状態ノードのパラメータの修正、および、新たな状態ノードのパラメータの追加を行う。
【０１８６】
目的地リスト修正部６５は、過去の移動履歴に新たな目的地が追加された場合、モデル記憶部６６に記憶されている目的地リストを修正する。
【０１８７】
モデル記憶部６６は、学習モデルとしての確率遷移モデルのパラメータを記憶する。また、モデル記憶部６６は、目的地リストも記憶する。
【０１８８】
図２３は、図２２の状態ノード割り当て部６３の詳細構成例を示している。
【０１８９】
状態ノード割り当て部６３は、モデル取得部７１、対応ノード系列推定部７２、適合度閾値判定部７３、既存ノード割り当て部７４、および新規ノード割り当て部７５により構成される。
【０１９０】
モデル取得部７１は、モデル記憶部６６から、確率遷移モデルのパラメータを取得して、対応ノード系列推定部７２に供給する。
【０１９１】
対応ノード系列推定部７２は、学習データである過去の移動履歴に対して、既存の確率遷移モデルを用いて、対応する状態ノード系列である対応ノード系列を生成（推定）する。
【０１９２】
適合度閾値判定部７３は、対応ノード系列推定部７２で推定された対応ノード系列を構成する状態ノードそれぞれについて、適合度が所定の閾値以上であるか否かを判定する。換言すれば、適合度閾値判定部７３は、学習データとして供給された過去の移動履歴が既知の経路であるか、または、未知の経路であるかを判定する。そして、適合度閾値判定部７３は、適合度が所定の閾値以上である（既知の経路である）と判定された学習データ（過去の移動履歴）を、既存ノード割り当て部７４に供給し、適合度が所定の閾値未満である（未知の経路である）と判定された学習データを、新規ノード割り当て部７５に供給する。
【０１９３】
既存ノード割り当て部７４は、適合度閾値判定部７３から供給された既知経路の学習データに対して、既存の確率遷移モデルの状態ノードを割り当てる既存ノード割り当て処理を行う。
【０１９４】
新規ノード割り当て部７５は、適合度閾値判定部７３から供給された未知経路の学習データに対し、新規の確率遷移モデルの状態ノードを割り当てる新規ノード割り当て処理を行う。
【０１９５】
既存ノード割り当て処理および新規ノード割り当て処理によって割り当てられた状態ノードのノード系列が、図２２のモデル再構成部６４に供給される。
【０１９６】
[学習処理のフローチャート]
図２４は、学習装置６０による学習処理のフローチャートを示している。
【０１９７】
初めに、ステップＳ１６１において、ログ取得部６１は、学習データとしての過去の移動履歴を取得し、前処理部６２に供給する。
【０１９８】
ステップＳ１６２において、前処理部６２は、学習データの一時的なデータの欠落部分に対し、線形補間等の補間処理を行うことで補間して、処理後の過去の移動履歴を状態ノード割り当て部６３に供給する。
【０１９９】
ステップＳ１６３において、状態ノード割り当て部６３のモデル取得部７１は、モデル記憶部６６から、確率遷移モデルのパラメータを取得して、対応ノード系列推定部７２に供給する。
【０２００】
ステップＳ１６４において、状態ノード割り当て部６３の対応ノード系列推定部７２は、学習データである過去の移動履歴の各位置データに対して既存の確率遷移モデルとの適合度を算出する適合度算出処理を行う。
【０２０１】
ステップＳ１６５において、状態ノード割り当て部６３の適合度閾値判定部７３は、学習データを構成する各位置データを識別するステップ番号ｉに１をセットして、ステップＳ１６６に進み、ｉステップ目の適合度が所定の閾値以上であるかを判定する。
【０２０２】
ステップＳ１６６で、ｉステップ目の適合度が所定の閾値以上であると判定された場合、処理はステップＳ１６７に進み、適合度閾値判定部７３は、学習データのステップ番号ｉの位置データは既存ノードに対応すると判定する。
【０２０３】
一方、ステップＳ１６６で、ｉステップ目の適合度が所定の閾値未満であると判定された場合、処理はステップＳ１６８に進み、適合度閾値判定部７３は、学習データのステップ番号ｉの位置データは新規ノードに対応すると判定する。
【０２０４】
ステップＳ１６９において、適合度閾値判定部７３は、全ての学習データについて既存ノードかまたは新規ノードを判定したかを判定する。
【０２０５】
ステップＳ１６９で、全ての学習データについて判定していないと判定された場合、処理はステップＳ１７０に進み、適合度閾値判定部７３は、ステップ番号を１だけインクリメントして、処理はステップＳ１６６に戻る。
【０２０６】
一方、ステップＳ１６９で、全ての学習データについて判定したと判定された場合、処理はステップＳ１７１に進み、状態ノード割り当て部６３の既存ノード割り当て部７４は、既知経路の学習データに対して、既存の確率遷移モデルの状態ノードを割り当てる既存ノード割り当て処理を行う。
【０２０７】
次に、ステップＳ１７２において、状態ノード割り当て部６３の新規ノード割り当て部７５は、未知経路の学習データに対し、新規の確率遷移モデルの状態ノードを割り当てる新規ノード割り当て処理を行う。
【０２０８】
ステップＳ１７１とＳ１７２の処理は並行して実行することができる。
【０２０９】
そして、ステップＳ１７３において、モデル再構成部６４は、状態ノード割り当て部６３からの対応ノード系列に基づいて、確率遷移モデルを再構成するモデル再構成処理を行う。
【０２１０】
ステップＳ１７４において、目的地リスト修正部６５は、過去の移動履歴に新たな目的地が追加された場合、追加された目的地をモデル記憶部６６に記憶されている目的地リストに追加して、処理を終了する。なお、追加の目的地がない場合には、ステップＳ１７４の処理は省略される。
【０２１１】
［適合度算出処理のフロー］
図２５は、図２４のステップＳ１６４で実行される適合度算出処理のフローチャートである。
【０２１２】
この処理では、初めに、ステップＳ１８１において、状態ノード割り当て部６３は、学習データを構成する各位置データを識別するステップ番号ｉに１をセットする。
【０２１３】
そして、ステップＳ１８２において、状態ノード割り当て部６３は、次式（４）により、ステップｉにおける各状態の観測尤度を算出する。
【数４】
式（４）の観測尤度は、中心値μiと分散値σi2の正規分布を持つ状態ノードsiから、データxiが観測される尤度を表す。なお、Π｛xd｝は、ｄ＝１，２，３としたときのxdを乗算することを表し、ｄ＝１，２，３は、それぞれ、過去の移動経路の時刻、緯度、および経度を表す。
【０２１４】
ステップＳ１８３において、状態ノード割り当て部６３は、次式（５）により、ステップｉにおける各状態の状態確率を算出する。
【数５】
式（５）において、δi(1)は、先頭ステップで状態siである確率を表す。また、δi(t)は、ステップtで、状態sjである確率を表す。式（５）のmax［aijδi(t-1)］は、状態sjに至る状態遷移のうち、ステップt-1での状態確率と、その場所からの遷移確率の積が最大となるものを選択することを意味している。なお、式（５）におけるZtは規格化パラメータであり、全ての状態siでのδi(t)の和である。
【０２１５】
式（５）によれば、状態ノード間の遷移で構成されるトポロジーを反映した状態履歴の推定を行うことができる。
【０２１６】
ステップＳ１８４において、状態ノード割り当て部６３は、次式（６）により、ステップｉにおける観測尤度の期待値を算出し、適合度とする。
【数６】
式（６）は、時刻tでの状態ｓjの尤度P(xt|μj，ｓj)について、状態確率δj(t)を用いて期待値を算出したものである。
【０２１７】
ステップＳ１８５において、状態ノード割り当て部６３は、ステップｉが最終ステップであるかを判定する。
【０２１８】
ステップＳ１８５で、ステップｉが最終ステップではないと判定された場合、処理はステップＳ１８６に進み、状態ノード割り当て部６３は、ステップ番号ｉを１だけインクリメントして、処理はステップＳ１８２に戻る。
【０２１９】
一方、ステップＳ１８５で、ステップｉが最終ステップであると判定された場合、処理は図２４に戻る。
【０２２０】
［既存ノード割り当て処理のフロー］
次に、図２６のフローチャートを参照して、図２４のステップＳ１７１で実行される既存ノード割り当て処理について説明する。
【０２２１】
図２６のステップＳ２０１乃至Ｓ２０３は、上述した図２５のステップＳ１８１乃至Ｓ１８３と同様であるので、その説明は省略する。ただし、既存ノード割り当て処理でのステップ番号は、既存ノードと判定された学習データに対するステップ番号となる。
【０２２２】
ステップＳ２０４において、状態ノード割り当て部６３は、ステップｉにおける各状態に至る親ノードを記憶する。より具体的には、状態ノード割り当て部６３は、次式（７）で計算される状態ノードの番号を求め、記憶する。
【数７】
式（７）のΨj(t)は、ステップt-1での状態確率と、その場所からの遷移確率の積が最大となる状態ノードのノード番号となる。argmaxi［x］は、添え字iを、1からNまでの範囲の整数に変えて得られるｘを最大にする添え字iを表す。
【０２２３】
ステップＳ２０５において、状態ノード割り当て部６３は、ステップｉが最終ステップであるかを判定する。
【０２２４】
ステップＳ２０５で、ステップｉが最終ステップではないと判定された場合、処理はステップＳ２０６に進み、状態ノード割り当て部６３は、ステップ番号ｉを１だけインクリメントして、処理はステップＳ２０２に戻る。
【０２２５】
一方、ステップＳ２０５で、ステップｉが最終ステップであると判定された場合、処理はステップＳ２０７に進み、状態ノード割り当て部６３は、最終ステップで状態確率を最大にする状態ノードを選択する。
【０２２６】
より具体的には、ステップＳ２０７の処理は、最終ステップを例えば、ｔ＝Tとすると、S(T)＝argmaxi［δi(T)］とする処理であり、最終的に最も状態確率の高い状態ノードを、既知経路の学習データの最終ステップに対応させる処理である。
【０２２７】
ステップＳ２０８において、状態ノード割り当て部６３は、ステップＳ２０７で選択された状態ノードから、ステップＳ２０４で記憶しておいた親ノードを逆向きに探索する。
【０２２８】
ステップＳ２０８の処理は、S(t-1)＝Ψ(S(t))とする処理である。これにより、移動履歴のｔステップ目に対応する状態ノードS(t)を順次求めることができ、最終的に、既知の移動履歴に対応する状態ノード系列が得られる。
【０２２９】
ステップＳ２０９において、状態ノード割り当て部６３は、ステップＳ２０８で得られた状態ノード系列を、学習データである既知の移動履歴と対応付けて内部に記憶し、図２４に戻る。
【０２３０】
［新規ノード割り当て処理のフロー］
次に、図２７のフローチャートを参照して、図２４のステップＳ１７２で実行される新規ノード割り当て処理について説明する。
【０２３１】
初めに、ステップＳ２２１において、状態ノード割り当て部６３は、学習データである未知の移動履歴をHMM（確率遷移モデル）で学習する。ステップＳ２２１では、未知の移動履歴の１ステップごとに新しい状態ノードが割り当てられ、未知の移動履歴に対応するHMMのパラメータが求められる。
【０２３２】
ステップＳ２２２において、状態ノード割り当て部６３は、学習により得られた状態ノードに、既存のHMM（確率遷移モデル）に付加する状態ノードとしての新たなノード番号を割り当てる。
【０２３３】
ステップＳ２２３において、状態ノード割り当て部６３は、学習データである未知の移動履歴と、対応する新たなノード番号の状態ノード系列を内部に記憶し、図２４に戻る。
【０２３４】
[モデル再構成処理のフロー]
次に、図２８のフローチャートを参照して、図２４のステップＳ１７３で実行されるモデル再構成処理について説明する。
【０２３５】
初めに、ステップＳ２４１において、モデル再構成部６４は、遷移頻度テーブルを作成する。
【０２３６】
図２９は、ステップＳ２４１で作成される遷移頻度テーブルの例を示している。遷移頻度テーブルは、図１８に示したHMMの状態遷移確率aijが、遷移頻度とされたものである。
【０２３７】
ステップＳ２４２において、モデル再構成部６４は、遷移頻度テーブルの遷移頻度から、次式（８）により、状態頻度テーブルを生成する。
【数８】
式（８）は、状態siの状態頻度ｆiが状態siの遷移頻度ｆijの総和により得られることを表している。
【０２３８】
ステップＳ２４３において、モデル再構成部６４は、状態頻度テーブルを用いて、次式（９）により、状態頻度の中心値Ｍiと分散Σi2とからなる統計量テーブルを生成する。
Ｍi＝μi・ｆi ，Σi2＝（σi2＋μi）・ｆi ・・・・・（９）
【０２３９】
ステップＳ２４４において、モデル再構成部６４は、図２６の既存ノード割り当て処理、および、図２７の新規ノード割り当て処理により生成されて記憶されている、学習データに対応する状態ノード系列を用いて、遷移頻度テーブルを更新する。ここで、更新後の遷移頻度ｆijは遷移頻度ｆij’で表し、更新後の状態頻度テーブルはｆi’で表される。
【０２４０】
ステップＳ２４５において、モデル再構成部６４は、図２６の既存ノード割り当て処理、および、図２７の新規ノード割り当て処理で出現する状態ノードに対応する位置データと、その二乗値を、状態頻度の中心値Ｍiと分散Σi2に加算することにより、式（９）の統計量テーブルを更新する。更新後の統計量テーブルの状態頻度の中心値Ｍiと分散Σi2は、Ｍi’，Σi2’で表される。
【０２４１】
ステップＳ２４６において、モデル再構成部６４は、次式（１０）により、図２６の既存ノード割り当て処理、および、図２７の新規ノード割り当て処理で出現する状態ノードの中心値μiと分散値σi2を、μi’とσi2’に更新して、図２４に戻る。
μi’＝Ｍi’/ｆi’ ，σi2’＝Σi2’/ｆi’−μi’2）・ ・・・・・（１０）
【０２４２】
以上、図２４乃至図２８を参照して説明した学習処理により、新たに入力された移動履歴に基づいて、既存の学習モデルを修正（更新）、拡張することができる。なお、既存モデルが存在しない最初の学習処理は、入力された移動履歴が全て未知経路と判定されて確率遷移モデルが学習される処理であり、上述した処理で対応可能である。
【０２４３】
［予測処理のフローチャート］
次に、図３０のフローチャートを参照して、第２の実施の形態における予測処理について説明する。
【０２４４】
初めに、ステップＳ３０１において、類似ノード検索部１４Bは、事前の学習により得られた確率遷移モデル（のパラメータ）と目的地リストを確率遷移モデルDB１３Bから取得する。
【０２４５】
ステップＳ３０２において、類似ノード検索部１４Bは、バッファ１２から、直近の移動履歴を取得する。
【０２４６】
ステップＳ３０３において、類似ノード検索部１４Bは、直近の移動履歴に対応する状態ノードを探索して、選択する。具体的には、類似ノード検索部１４Bは、上述した学習処理で説明した適合度算出処理（図２４のステップＳ１６４、図２５）を行い、既存ノード割り当て処理（図２４のステップＳ１７１、図２６）を行うことにより、直近の移動履歴に対応する状態ノードを探索して、選択する。
【０２４７】
ステップＳ３０４において、適合判定部１５Bは、類似ノード検索部１４Bにより選択された状態ノードの適合度が所定の閾値以上であるかを判定する。
【０２４８】
ステップＳ３０４で、選択された状態ノードの適合度が所定の閾値未満であると判定された場合、予測処理は終了する。
【０２４９】
一方、ステップＳ３０４で、選択された状態ノードの適合度が所定の閾値以上であると判定された場合、処理はステップＳ３０５に進む。ステップＳ３０５では、予測ノード探索部１６Bは、選択された状態ノードから遷移可能な目的地ノードをツリー探索することにより目的地を探索する。
【０２５０】
ステップＳ３０６において、予測ノード探索部１６Bは、探索された目的地を、目的地ごとにリストアップする。
【０２５１】
ステップＳ３０７において、予測値算出部１８Bは、リストアップされた目的地ごとに、目的地への経路リストおよび代表経路を算出する。
【０２５２】
目的地iへの代表経路ｒiは、例えば、次式（１１）により求めることができる
【数９】
式（１１）において、Ｔjは、ｊ番目の経路リストの長さ（ステップ数）を表し、ａ(ｓk，ｓk+1)は、状態ノードｓkから状態ノードｓk+1への遷移確率を表す。したがって、ｓjkは、ｊ番目の経路リストのｋ番目の状態ノードを表し、ｓj１は現在地ノードであり、ｓjTjはｊ番目の経路リストの目的地ノードを表す。
【０２５３】
したがって、式（１１）は、目的地ｉについては最も生起確率の高いｒ番目の経路ｒiを代表経路とし、代表経路ｒiは、｛ｓ1，ｓ2，ｓ3，・・・，ｓTr｝の状態ノード系列を有することを意味している。代表経路の選択方法は、これ以外の方法を用いてもよい。
【０２５４】
ステップＳ３０８において、予測値算出部１８Bは、各目的地への到達確率を算出する。
【０２５５】
目的地iへの到達確率ｐiは、例えば、次式（１２）により求めることができる
【数１０】
式（１２）において、Niは、現在地ノードから、目的地ｉに到達する経路リストの本数を表す。
【０２５６】
ステップＳ３０９において、各目的地への所要時間を算出して出力し、処理を終了する。
【０２５７】
目的地iへの代表経路ｒiの所要時間ｔiは、例えば、次式（１３）により求めることができる
【数１１】
式（１３）において、ｓkは、代表経路ｒの状態ノード系列のｋ番目の状態ノードであり、Ｔは、代表経路の経路リストの長さ（ステップ数）であり、t=1が現在地ノードで、t=Tが目的地ノードである。
【０２５８】
また、式（１３）において、ｐs1(1)は、ステップ１に状態ノードｓ１にいる確率を表す。ｐsk(t)は、ステップtに状態ノードｓkにいる確率を表し、一つ前のステップにおいて状態ノードｓkにいて自己遷移した確率と、一つ前のステップにおいて状態ノードｓk-1にいて遷移してきた確率の和である。
【０２５９】
さらに、式（１３）の所要時間ｔiは、時刻t-1に目的地ノードｓTの一つ手前の状態ノードｓT-1にいて、時刻tで初めて目的地ノードｓTに移るときのｔの期待値である。
【０２６０】
［絶対の出発予測時刻を用いた第２のセンサ制御処理のフローチャート］
次に、図３１のフローチャートを参照して、第２の実施の形態における、絶対の出発予測時刻を用いた第２のセンサ制御処理について説明する。
【０２６１】
図３１のステップＳ３２１乃至Ｓ３２４は、図３０のステップＳ３０１乃至Ｓ３０４と同様であるので、その説明は省略する。
【０２６２】
ステップＳ３２４で、選択された状態ノードの適合度が所定の閾値未満であると判定された場合、処理はステップＳ３２５に進み、センサ制御部１９は、位置センサ部１１を、データ取得間隔が短くなるように制御して、処理を終了する。
【０２６３】
一方、ステップＳ３２４で、選択された状態ノードの適合度が所定の閾値以上であると判定された場合、処理はステップＳ３２６に進む。
【０２６４】
ステップＳ３２６において、出発時刻予測部１７Bは、選択された状態ノードの自己遷移以外の１以上の遷移先の状態ノードの時刻の中心値の平均（平均時刻）を、絶対の出発時刻として算出する。算出された絶対の出発時刻は、センサ制御部１９に供給される。
【０２６５】
ステップＳ３２７において、センサ制御部１９は、出発時刻予測部１７Bから供給された絶対の出発時刻と、現在時刻との差分を算出する。
【０２６６】
ステップＳ３２８において、センサ制御部１９は、算出された差分が所定の閾値（出発時刻閾値）より大であるかを判定する。
【０２６７】
ステップＳ３２８で、算出された差分が出発時刻閾値以下であると判定された場合、処理はステップＳ３２９に進み、センサ制御部１９は、データ取得間隔が短くなるように制御して、処理を終了する。
【０２６８】
一方、ステップＳ３２８で、算出された差分が出発時刻閾値より大であると判定された場合、処理はステップＳ３３０に進み、センサ制御部１９は、データ取得間隔が長くなるように制御して、処理を終了する。
【０２６９】
第２の実施の形態における第１のセンサ制御処理は、上述したステップＳ３２６乃至Ｓ３２９を省略した処理となる。
【０２７０】
［相対の出発予測時刻を用いた第２のセンサ制御処理のフローチャート］
次に、図３２のフローチャートを参照して、第２の実施の形態における、相対の出発予測時刻を用いた第２のセンサ制御処理について説明する。
【０２７１】
図３２の相対の出発予測時刻を用いた第２のセンサ制御処理は、図３１の絶対の出発予測時刻を用いた第２のセンサ制御処理と比較すると、図３１のステップＳ３２６乃至Ｓ３２８に対応するステップＳ３４６およびＳ３４７が異なるのみである。従って、図３２では、ステップＳ３４６およびＳ３４７の処理のみ説明し、それ以外の説明は省略する。
【０２７２】
ステップＳ３４６において、出発時刻予測部１７Bは、選択された状態ノードの自己遷移確率から、相対の出発時刻（予測滞在時間）を算出する。すなわち、選択された状態ノードの自己遷移確率を用いた式（２）に、単位ステップの時間を乗算することにより、予測滞在時間が求められ、センサ制御部１９に供給される。
【０２７３】
ステップＳ３４７において、出発時刻予測部１７Bは、算出された予測滞在時間が所定の閾値（滞在時間閾値）より大であるかを判定する。
【０２７４】
ステップＳ３４７で、算出された予測滞在時間が滞在時間閾値以下であると判定された場合、処理はステップＳ３４８に進む。
【０２７５】
一方、ステップＳ３４７で、算出された予測滞在時間が滞在時間閾値より大であると判定された場合、処理はステップＳ３４９に進む。
【０２７６】
ステップＳ３４８またはＳ３４９において、所定のデータ取得間隔がセンサ制御部１９に設定されて、処理は終了する。
【０２７７】
以上のように、絶対の出発予測時刻を用いた第２のセンサ制御処理、または、相対の出発予測時刻を用いた第２のセンサ制御処理が行われるが、両者の処理結果を組み合わせた結果に基づいて、最終的にデータ取得間隔を決定してもよい。
【０２７８】
［データ修正処理のフローチャート］
次に、図３３のフローチャートを参照して、第２の実施の形態における、データ修正処理について説明する。
【０２７９】
図３３のステップＳ３６１乃至Ｓ３６４は、図３０のステップＳ３０１乃至Ｓ３０４と同様であるので、その説明は省略する。
【０２８０】
ステップＳ３６５において、モデル用データ修正部２０Bは、直近の移動履歴の各ステップに対応する各状態ノードの確率δj(t)を取得する。
【０２８１】
ステップＳ３６６において、モデル用データ修正部２０Bは、式（３）により、直近の移動履歴に対応する理想系列を生成する。すなわち、モデル用データ修正部２０Bは、直近の移動履歴の各ステップに対応する各状態ノードの中心値に、状態ノードの確率δj(t)を重み付け加算することにより、理想系列を生成する。
【０２８２】
ステップＳ３６７において、モデル用データ修正部２０Bは、理想系列と直近の移動履歴の平均を算出することで、修正後の直近の移動履歴を生成して、処理を終了する。
【０２８３】
以上のように、予測装置１の第２の実施の形態では、確率遷移モデルDB１３Bに記憶されている確率遷移モデルを用いて、予測処理、センサ制御処理、およびデータ修正処理を行うことができる。
【０２８４】
＜４．第３実施の形態＞
［第３実施の形態の予測装置１の構成例］
上述した例では、予測装置１が、過去履歴DB１３の検索用データとして経路ログか、または、確率遷移モデルのいずれか一方を用いて、予測処理、センサ制御処理、およびデータ修正処理を行う例について説明した。
【０２８５】
しかしながら、予測装置１は、過去履歴DB１３の検索用データとして、経路ログ、および、確率遷移モデルの両方を有し、選択的に実行するようにしてもよい。
【０２８６】
図３４は、そのような予測装置１の構成例を示すブロック図である。すなわち、図３４は、経路ログ、および、確率遷移モデルの両方を有し、それらを選択的に実行する第３の実施の形態の予測装置１の構成例を示している。
【０２８７】
過去履歴DB１３は、第１の実施の形態の経路ログDB１３Aと第２の実施の形態の確率遷移モデルDB１３Bを有する。
【０２８８】
類似検索部１４は、第１の実施の形態の類似経路探索部１４Aと第２の実施の形態の類似ノード探索部１４Bを有する。
【０２８９】
適合判定部１５は、第１の実施の形態の適合判定部１５Aと第２の実施の形態の適合判定部１５Bを有する。
【０２９０】
予測経路抽出部１６は、第１の実施の形態の予測経路ログ抽出部１６Aと第２の実施の形態の予測ノード探索部１６Bを有する。
【０２９１】
出発時刻予測部１７、第１の実施の形態の出発時刻予測部１７Aと第２の実施の形態の出発時刻予測部１７Bを有する。
【０２９２】
DB修正部２０は、第１の実施の形態の検索ログ修正部２０と第２の実施の形態のモデル用データ修正部２０Bを有する。
【０２９３】
第３の実施の形態においては、例えば、経路ログ、または、確率遷移モデルのどちらを使用するかが、図示せぬ操作部でユーザにより選択される。経路ログを使用することが選択された場合には、第１の実施の形態として説明した処理が実行される。一方、確率遷移モデルを使用することが選択された場合には、第２の実施の形態として説明した処理が実行される。
【０２９４】
＜５．第４実施の形態＞
［第４実施の形態の予測装置１の構成例］
【０２９５】
上述した実施の形態では、予測装置１が、位置センサ部１１のデータ取得間隔を制御するセンサ制御機能と、直近の移動履歴を検索用データに基づいて修正するデータ修正機能の両方を有していた。
【０２９６】
しかしながら、予測装置１は、センサ制御機能、または、データ修正機能のいずれか一方のみを有するものでもよい。
【０２９７】
図３５は、予測装置１の第４の実施の形態としての、センサ制御機能のみを有する予測装置１の構成例を示すブロック図である。
【０２９８】
図３６は、予測装置１の第４の実施の形態としての、データ修正機能のみを有する予測装置１の構成例を示すブロック図である。
【０２９９】
第４の実施の形態の予測装置１の処理（動作）については、上述した説明と重複するので省略する。
【０３００】
［コンピュータの構成例］
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここで、コンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどが含まれる。
【０３０１】
図３７は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。
【０３０２】
コンピュータにおいて、CPU（Central Processing Unit）１０１，ROM（Read Only Memory）１０２，RAM（Random Access Memory）１０３は、バス１０４により相互に接続されている。
【０３０３】
バス１０４には、さらに、入出力インタフェース１０５が接続されている。入出力インタフェース１０５には、入力部１０６、出力部１０７、記憶部１０８、通信部１０９、及びドライブ１１０が接続されている。
【０３０４】
入力部１０６は、キーボード、マウス、マイクロホンなどよりなる。出力部１０７は、ディスプレイ、スピーカなどよりなる。記憶部１０８は、ハードディスクや不揮発性のメモリなどよりなる。通信部１０９は、ネットワークインタフェースなどよりなる。ドライブ１１０は、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブル記録媒体１１１を駆動する。
【０３０５】
以上のように構成されるコンピュータでは、CPU１０１が、例えば、記憶部１０８に記憶されているプログラムを、入出力インタフェース１０５及びバス１０４を介して、RAM１０３にロードして実行することにより、上述した一連の処理が行われる。
【０３０６】
コンピュータでは、プログラムは、リムーバブル記録媒体１１１をドライブ１１０に装着することにより、入出力インタフェース１０５を介して、記憶部１０８にインストールすることができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して、通信部１０９で受信し、記憶部１０８にインストールすることができる。その他、プログラムは、ROM１０２や記憶部１０８に、あらかじめインストールしておくことができる。
【０３０７】
なお、本明細書において、フローチャートに記述されたステップは、記載された順序に沿って時系列的に行われる場合はもちろん、必ずしも時系列的に処理されなくとも、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで実行されてもよい。
【０３０８】
上述した実施の形態において、各種の条件を判定するための閾値は、それぞれ適切な値を適宜設定することができる。
【０３０９】
本技術の実施の形態は、上述した実施の形態に限定されるものではなく、本技術の要旨を逸脱しない範囲において種々の変更が可能である。
【０３１０】
なお、本技術は以下のような構成も取ることができる。
（１）
時系列の位置データでなる直近の移動履歴を取得する位置センサ部と、
検索用データを記憶する過去履歴DBと、
前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索する類似検索部と、
前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、
前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部と
を備える情報処理装置。
（２）
前記センサ制御部は、前記適合度が前記所定の閾値以上である場合に、前記位置データの取得間隔が、前記所定の閾値未満である場合よりも長くなるように制御する
前記（１）に記載の情報処理装置。
（３）
現在の位置を離れる時刻である出発時刻を予測する出発時刻予測部をさらに備え、
前記センサ制御部は、前記適合度が前記所定の閾値以上であり、かつ、前記出発時刻予測部で予測された出発予測時刻が所定時間より後である場合に、前記位置データの取得間隔が、前記所定の閾値未満である場合よりも長くなるように制御する
前記（１）または（２）に記載の情報処理装置。
（４）
前記出発時刻予測部は、絶対時刻または相対時刻のいずれかで前記出発時刻を予測する
前記（３）に記載の情報処理装置。
（５）
前記過去履歴DBは、過去の移動履歴を前記検索用データとして記憶し、
前記類似検索部は、前記適合度として、前記過去の移動履歴と前記直近の移動履歴との距離を用いて、前記直近の移動履歴と類似するものを検索する
前記（１）ないし（４）のいずれかに記載の情報処理装置。
（６）
前記過去履歴DBは、過去の移動履歴を確率遷移モデルで学習したときのパラメータを前記検索用データとして記憶し、
前記類似検索部は、前記適合度として、前記直近の移動履歴に対して算出される前記確率遷移モデルの尤度を用いて、前記直近の移動履歴と類似するものを検索する
前記（１）ないし（５）のいずれかに記載の情報処理装置。
（７）
検索用データを記憶する過去履歴DBを備える情報処理装置が、
時系列の位置データでなる直近の移動履歴を取得し、
前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索し、
検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定し、
判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御する
ステップを含む情報処理方法。
（８）
コンピュータを、
過去履歴DBに記憶されている検索用データのなかから、位置センサ部で取得された、時系列の位置データでなる直近の移動履歴と類似する過去の経路を検索する類似検索部と、
前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、
前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部
として機能させるためのプログラム。
【符号の説明】
【０３１１】
１ 予測装置， １１ 位置センサ部， １３ 過去履歴DB， １４ 類似検索部， １５ 適合判定部， １６ 予測経路抽出部， １７ 出発時刻予測部， １８ 予測値算出部， １９ センサ制御部， ２０ DB修正部
【技術分野】
【０００１】
本技術は、情報処理装置、情報処理方法、およびプログラムに関し、特に、少ない消費電力で、必要十分な移動履歴データを蓄積することができるようにする情報処理装置、情報処理方法、およびプログラムに関する。
【背景技術】
【０００２】
現在地を起点として、これからの移動経路を予測する方法として、現在の移動履歴と類似する経路を過去の移動履歴のデータベースから検索し、その結果得られた経路を予測経路として出力するものがある（例えば、特許文献１参照）。
【０００３】
このような予測方法では、データベースである過去の移動履歴を十分に蓄積することが必要である。また、蓄積された過去の移動履歴のデータの精度がよいことも重要である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−１５５１６７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
精度のよい移動履歴を蓄積するための一つの方法として、現在位置を取得する位置センサの取得間隔を短く設定することが挙げられる。
【０００６】
しかしながら、例えば、位置センサを搭載した携帯端末などでは、単純に取得間隔を短く設定すると電力消費が大きくなってしまうため、バッテリの持ち時間が短くなってしまう。
【０００７】
本技術は、このような状況に鑑みてなされたものであり、少ない消費電力で、必要十分な移動履歴データを蓄積することができるようにするものである。
【課題を解決するための手段】
【０００８】
本技術の一側面の情報処理装置は、時系列の位置データでなる直近の移動履歴を取得する位置センサ部と、検索用データを記憶する過去履歴DBと、前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索する類似検索部と、前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部とを備える。
【０００９】
本技術の一側面の情報処理方法は、検索用データを記憶する過去履歴DBを備える情報処理装置が、時系列の位置データでなる直近の移動履歴を取得し、前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索し、検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定し、判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するステップを含む。
【００１０】
本技術の一側面のプログラムは、コンピュータを、過去履歴DBに記憶されている検索用データのなかから、位置センサ部で取得された、時系列の位置データでなる直近の移動履歴と類似する過去の経路を検索する類似検索部と、前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部として機能させるためのものである。
【００１１】
本技術の一側面においては、過去履歴DBに記憶されている検索用データのなかから、位置センサ部で取得された、時系列の位置データでなる直近の移動履歴と類似する過去の経路が検索され、検索された過去の経路と、直近の移動履歴との適合度が所定の閾値以上であるかが判定され、その判定結果に応じて、位置センサ部の位置データの取得間隔が制御される。
【００１２】
プログラムは、伝送媒体を介して伝送することにより、又は、記録媒体に記録して、提供することができる。
【００１３】
情報処理装置は、独立した装置であっても良いし、１つの装置を構成している内部ブロックであっても良い。
【発明の効果】
【００１４】
本技術の一側面によれば、少ない消費電力で、必要十分な移動履歴データを蓄積することができる。
【図面の簡単な説明】
【００１５】
【図１】本技術を適用した予測装置の構成例を示すブロック図である。
【図２】予測処理を説明するフローチャートである。
【図３】第１のセンサ制御処理を説明するフローチャートである。
【図４】第２のセンサ制御処理を説明するフローチャートである。
【図５】データ修正処理を説明するフローチャートである。
【図６】予測装置の第１の実施の形態の構成例を示すブロック図である。
【図７】経路ログDBに記憶される過去の移動履歴のデータ例を示す図である。
【図８】目的地リストの例を示す図である。
【図９】過去の移動履歴と目的地を地図上に示した図である。
【図１０】予測値算出部による予測結果を示した図である。
【図１１】直近の移動履歴の修正について説明する図である。
【図１２】第１の実施の形態における予測処理を説明するフローチャートである。
【図１３】第１の実施の形態の絶対の出発予測時刻を用いた第２のセンサ制御処理を説明するフローチャートである。
【図１４】第１の実施の形態の相対の出発予測時刻を用いた第２のセンサ制御処理を説明するフローチャートである。
【図１５】第１の実施の形態のデータ修正処理を説明するフローチャートである。
【図１６】予測装置の第２の実施の形態の構成例を示すブロック図である。
【図１７】確率遷移モデルの概念図である。
【図１８】HMMの各状態ノードの観測モデルと内部モデルの例を示す図である。
【図１９】HMMに学習させたときの学習結果を地図上に示した図である。
【図２０】直近の移動履歴の修正について説明する図である。
【図２１】その他の直近の移動履歴の修正について説明する図である。
【図２２】学習装置の構成例を示すブロック図である。
【図２３】図２２の状態ノード割り当て部の詳細構成例を示すブロック図である。
【図２４】学習処理を説明するフローチャートである。
【図２５】適合度算出処理を説明するフローチャートである。
【図２６】既存ノード割り当て処理を説明するフローチャートである。
【図２７】新規ノード割り当て処理を説明するフローチャートである。
【図２８】モデル再構成処理を説明するフローチャートである。
【図２９】遷移頻度テーブルの例を示す図である。
【図３０】第２の実施の形態における予測処理を説明するフローチャートである。
【図３１】第２の実施の形態の絶対の出発予測時刻を用いた第２のセンサ制御処理を説明するフローチャートである。
【図３２】第２の実施の形態の相対の出発予測時刻を用いた第２のセンサ制御処理を説明するフローチャートである。
【図３３】第２の実施の形態のデータ修正処理を説明するフローチャートである。
【図３４】予測装置の第３の実施の形態の構成例を示すブロック図である。
【図３５】予測装置の第４の実施の形態の構成例を示すブロック図である。
【図３６】予測装置の第４の実施の形態の構成例を示すブロック図である。
【図３７】本技術が適用されたコンピュータの一実施の形態の構成例を示すブロック図である。
【発明を実施するための形態】
【００１６】
以下、本技術を実施するための形態（以下、実施の形態という）について説明する。なお、説明は以下の順序で行う。
１．予測装置の処理の概要
２．第１の実施の形態（経路ログのデータベースに基づく制御を行う構成例）
３．第２の実施の形態（確率遷移モデルのデータベースに基づく制御を行う構成例）
４．第３の実施の形態（第１の実施の形態と第２の実施の形態を選択的に実行可能な構成例）
５．第４の実施の形態（センサ制御機能とデータ修正機能のいずれか一方のみを備える構成例）
【００１７】
＜１．予測装置の処理の概要＞
［予測装置の構成例］
図１は、本技術が適用された予測装置の構成例を示すブロック図である。
【００１８】
図１の予測装置１は、GPS (Global Positioning System )センサ等の位置センサから取得した位置情報を基に、ユーザの移動経路を予測し、目的地と、その目的地に到達するまでの経路や予測時間などを予測する装置である。この予測装置１は、それ単独の携帯型の装置として構成されたり、あるいは、携帯電話機、タブレット端末、等の携帯端末の一部の装置として構成される。
【００１９】
予測装置１は、位置センサ部１１、バッファ１２、過去履歴DB１３、類似検索部１４、適合判定部１５、予測経路抽出部１６、出発時刻予測部１７、予測値算出部１８、センサ制御部１９、およびDB修正部２０により構成される。
【００２０】
位置センサ部１１は、自身の現在の位置を示す緯度経度のデータを、センサ制御部１９の制御により決定された一定の時間間隔で順次取得する。位置センサ部１１は、取得時刻（現在時刻）と、そのときの緯度、経度（のデータ）を、バッファ１２に供給する。
【００２１】
バッファ１２は、位置センサ部１１から供給される、時刻、緯度、及び経度のデータを、所定時間分だけ、一時的に保持する。そして、位置センサ部１１が時刻、緯度、及び経度のデータを取得する１回の動作を１ステップと呼ぶことにすると、バッファ１２は、現在時刻から所定ステップ数前までの時刻、緯度、及び経度の時系列データ（以下、直近の移動履歴と称する。）を類似検索部１４に供給する。
【００２２】
過去履歴DB１３は、予測装置１が移動経路や目的地を予測するのに必要な検索用データを記憶する。検索用データは、過去の移動履歴そのもの、あるいはそれを必要に応じて修正したもの、または、過去の移動履歴に対応する学習モデルである。なお、過去履歴DB１３に記憶される検索用データは、予測結果を利用するユーザ本人により生成されたものが望ましいが、他のユーザにより生成されたものでもよい。
【００２３】
また、過去履歴DB１３は、過去の移動履歴において目的地とされたリストである目的地リストも記憶する。目的地リストは、例えば、ユーザにより事前に入力されたり、所定時間（例えば、１時間）以上所定範囲（１００ｍ）以内に滞在している場所等を検出することで作成される。
【００２４】
類似検索部１４は、過去履歴DB１３に記憶された検索用データのなかから、バッファ１２から供給される直近の移動履歴と類似する過去の経路を検索し、検索結果を適合判定部１５に供給する。
【００２５】
適合判定部１５は、類似検索部１４で検索された検索用データの類似の経路が、取得された直近の移動履歴と適合するか否かを判定する。換言すれば、適合判定部１５は、取得された直近の移動履歴が、検索用データとして取得されている既知の経路であるか否かを、検索して得られた検索用データの類似の経路と、直近の移動履歴との適合度が所定の閾値以上であるか否かにより判定する。検索して得られた検索用データの類似の経路と、直近の移動履歴との適合度が所定の閾値以上である場合、適合判定部１５は、直近の移動経路を既知の経路と判定する。一方、検索された検索用データの類似の経路と、直近の移動履歴との適合度が所定の閾値未満である場合、適合判定部１５は、直近の移動経路を未知の経路と判定する。
【００２６】
適合判定部１５は、既知または未知の判定結果を、センサ制御部１９に供給する。また、適合判定部１５は、既知の経路と判定した場合、直近の移動経路を、予測経路抽出部１６およびDB修正部２０に供給する。
【００２７】
予測経路抽出部１６は、適合判定部１５から供給される既知の直近の移動履歴に基づいて、過去履歴DB１３の検索用データから予測経路を抽出する（ユーザの移動経路を予測する）。
【００２８】
また、予測経路抽出部１６は、抽出した予測経路から到達可能な目的地を、目的地リストに基づいてリストアップする。そして、予測経路抽出部１６は、抽出された目的地とそこに到達するための予測経路を予測値算出部１８に供給し、予測経路を出発時刻予測部１７に供給する。
【００２９】
出発時刻予測部１７は、ユーザが現在移動中か、または、止まっているかに関わらず、現在の位置を離れる時刻である出発時刻を、絶対値または相対値のいずれかで予測する。即ち、出発時刻予測部１７は、現在の位置から離れる出発時刻を絶対時刻として予測する。あるいは、出発時刻予測部１７は、現在の位置から離れるまでの時間（出発時間）を相対時刻として予測する。絶対時刻または相対時刻のいずれを使用するかは、例えば、ユーザの選択を受け付けて決定するようにしてもよい。出発時刻予測部１７は、予測結果である出発予測時刻をセンサ制御部１９に供給する。
【００３０】
予測値算出部１８は、予測経路抽出部１６から供給される、既知の直近の移動履歴に基づいて得られた目的地と予測経路に基づいて、予測値として、目的地までの到達時間、経路、および到達確率を算出して出力する。予測値算出部１８から出力された予測結果が、例えば、図示せぬディスプレイ等に表示される。また、予測値算出部１８の後段において、予測結果を用いた携帯端末の制御などが行われる。
【００３１】
センサ制御部１９には、適合判定部１５から、既知または未知の判定結果が供給される。また、センサ制御部１９には、出発時刻予測部１７から、絶対時刻または相対時刻のいずれかで表された出発予測時刻が供給される。
【００３２】
センサ制御部１９は、既知または未知の判定結果に応じて、位置センサ部１１が位置データを取得するデータ取得間隔を制御する。具体的には、センサ制御部１９は、既知の判定結果が供給された場合、データ取得間隔が短くなるように制御し、未知の判定結果が供給された場合、データ取得間隔が長くなるように制御する。
【００３３】
また、センサ制御部１９は、出発時刻予測部１７から供給される出発予測時刻に応じて、位置センサ部１１のデータ取得間隔を制御することもできる。具体的には、センサ制御部１９は、出発時刻まで余裕がある場合には、データ取得間隔が短くなるように制御し、出発時刻がすぐである場合、データ取得間隔が長くなるように制御する。出発時刻がすぐである場合には、ユーザが移動中である場合も含まれる。
【００３４】
DB修正部２０には、既知の直近の移動履歴が適合判定部１５から供給される。DB修正部２０は、過去履歴DB１３に記憶されている検索用データに基づいて、適合判定部１５から供給された既知の直近の移動履歴を修正し、過去履歴DB１３に供給する。
【００３５】
従って、図１では図示を省略しているが、予測経路抽出部１６、予測値算出部１８、DB修正部２０などは、必要に応じて過去履歴DB１３の検索用データを取得して処理を行う。
【００３６】
以上のように構成される予測装置１は、位置センサ部１１で取得される直近の既知の移動履歴に基づいて、ユーザの、現在地からの移動経路、目的地、目的地に行くまでにかかる時間等を予測する予測処理を行う。
【００３７】
また、予測装置１は、位置センサ部１１で取得される直近の移動履歴が既知かまたは未知かに基づいて、位置センサ部１１のデータ取得間隔を制御（変更）するセンサ制御処理を行う。
【００３８】
さらに、予測装置１は、位置センサ部１１で取得される既知の直近の移動履歴に基づいて、直近の移動履歴（のデータ）を修正するデータ修正処理を行う。
【００３９】
以下、予測処理、センサ制御処理、およびデータ修正処理のそれぞれについて、図２乃至図５のフローチャートを参照して説明する。
【００４０】
［予測処理のフローチャート］
図２は、図１の予測装置１が行う予測処理のフローチャートである。なお図２乃至図５においては、位置センサ部１１のデータ取得およびバッファ１２のバッファリングは常時行われているものとする。
【００４１】
初めに、ステップＳ１では、類似検索部１４は、過去履歴DB１３から、検索用データを取得する。
【００４２】
ステップＳ２において、類似検索部１４は、バッファ１２から、直近の移動履歴を取得する。
【００４３】
ステップＳ３において、類似検索部１４は、取得した検索用データのなかから、直近の移動履歴と類似する経路を検索し、検索結果を適合判定部１５に供給する。直近の移動履歴が検索用データのどの経路と類似するかの検索は、直近の移動履歴と検索用データの経路との適合度（類似度）を、全ての検索用データについて算出することにより行われる。
【００４４】
ステップＳ４において、適合判定部１５は、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であるかを判定する。
【００４５】
ステップＳ４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値未満であると判定された場合、予測処理は終了する。即ち、直近の移動履歴が未知の経路である場合には、予測ができないとして処理を終了する。
【００４６】
一方、ステップＳ４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であると判定された場合、処理はステップＳ５に進み、予測経路抽出部１６は、過去履歴DB１３の検索用データから、目的地と予測経路を抽出する。
【００４７】
そして、ステップＳ６において、予測値算出部１８は、抽出された予測経路に基づいて、目的地までの到達時間、経路、及び到達確率を、予測値として算出して出力し、処理を終了する。
【００４８】
［第１のセンサ制御処理のフローチャート］
図３は、適合判定部１５からの既知または未知の判定結果のみに基づいて、位置センサ部１１のデータ取得間隔を制御する第１のセンサ制御処理のフローチャートである。
【００４９】
初めに、ステップＳ１１において、類似検索部１４は、過去履歴DB１３から、検索用データを取得する。
【００５０】
ステップＳ１２において、類似検索部１４は、バッファ１２から、直近の移動履歴を取得する。
【００５１】
ステップＳ１３において、類似検索部１４は、取得した検索用データのなかから、直近の移動履歴と類似する経路を検索し、検索結果を適合判定部１５に供給する。直近の移動履歴が検索用データのどの経路と類似するかの検索は、直近の移動履歴と検索用データの経路との適合度（類似度）を、全ての検索用データについて算出することにより行われる。
【００５２】
ステップＳ１４において、適合判定部１５は、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であるかを判定する。
【００５３】
以上のステップＳ１１乃至Ｓ１４の処理は、図１のステップＳ１乃至Ｓ４の処理と同一であり、１つの処理を、予測処理とセンサ制御処理が共通に利用している。
【００５４】
ステップＳ１４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値未満であると判定された場合、即ち、直近の移動履歴が未知の経路である場合、処理はステップＳ１５に進み、センサ制御部１９は、データ取得間隔が短くなるように制御して、処理を終了する。
【００５５】
一方、ステップＳ１４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であると判定された場合、即ち、直近の移動履歴が既知の経路である場合、処理はステップＳ１６に進み、センサ制御部１９は、データ取得間隔が長くなるように制御して、処理を終了する。
【００５６】
図３の処理は繰り返し実行される。
【００５７】
以上のように、第１のセンサ制御処理では、直近の移動履歴が既知であれば、既に学習している経路であるので、データ取得間隔が長く設定される。一方、直近の移動履歴が未知であれば、検索用データとして蓄積する必要があるので、精密なデータを取得するため、データ取得間隔が短く設定される。これにより、不要な時にはデータ取得間隔を長くすることができるので、少ない消費電力で、必要十分な移動履歴データを蓄積することができる。
【００５８】
［第２のセンサ制御処理のフローチャート］
図４は、既知または未知の判定結果と出発予測時刻に基づいて、位置センサ部１１のデータ取得間隔を制御する第２のセンサ制御処理のフローチャートである。
【００５９】
図４のステップＳ２１乃至Ｓ２５は、図３のステップＳ１１乃至Ｓ１５とそれぞれ同様であるので、その説明は省略する。
【００６０】
ステップＳ２４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であると判定された場合、処理はステップＳ２６に進み、出発時刻予測部１７は、現在の位置を離れる時刻である出発時刻を、絶対時刻または相対時刻のいずれかで予測する。出発時刻予測部１７の予測結果である出発予測時刻は、センサ制御部１９に供給される。
【００６１】
そして、ステップＳ２７において、センサ制御部１９は、出発時刻予測部１７から供給された出発予測時刻が所定時間より後であるかを判定する。
【００６２】
ステップＳ２７で、出発予測時刻が所定時間より後ではないと判定された場合、即ち、移動中のときのように、出発時刻がすぐである場合、処理はステップＳ２８に進み、センサ制御部１９は、データ取得間隔が短くなるように制御する。
【００６３】
一方、ステップＳ２７で、出発予測時刻が所定時間より後であると判定された場合、即ち、出発時刻まで余裕がある場合、処理はステップＳ２９に進み、センサ制御部１９は、データ取得間隔が長くなるように制御する。
【００６４】
図４の処理は繰り返し実行される。
【００６５】
以上のように、第２のセンサ制御処理では、直近の移動経路が既知であっても、例えば、移動中である場合には、データ取得間隔が短く設定され、目的地に滞在していたり、電車待ちなど、現在地からしばらく動かない場合には、データ取得間隔が長く設定される。
【００６６】
これにより、不要な時にはデータ取得間隔を長くすることができるので、少ない消費電力で、必要十分な移動履歴データを蓄積することができる。
【００６７】
なお、上述した例では、データ取得間隔を、短い設定時間（例えば、１分）と、長い設定時間（例えば、５分）の二段階としたが、三段階以上に分けてもよい。
【００６８】
［データ修正処理のフローチャート］
図５は、図１の予測装置１が行うデータ修正処理のフローチャートである。
【００６９】
図５のステップＳ４１乃至Ｓ４４の処理は、図１のステップＳ１乃至Ｓ４、および図２のステップＳ１１乃至Ｓ１４の処理と同様であるので、その説明は省略する。即ち、ステップＳ４１乃至Ｓ４４の処理は、１つの処理を、予測処理、センサ制御処理、及びデータ修正処理が共通に利用している。
【００７０】
ステップＳ４４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値未満であると判定された場合、データ修正処理は終了する。即ち、直近の移動履歴が未知の経路である場合には、検索用データとしての蓄積がないため、修正ができないとして処理を終了する。
【００７１】
一方、ステップＳ４４で、直近の移動履歴と検索用データの経路との適合度が所定の閾値以上であると判定された場合、処理はステップＳ４５に進み、DB修正部２０は、検索用データを用いて直近の移動履歴を修正する。そして、DB修正部２０は、修正後の直近の移動履歴を過去履歴DB１３に供給して、処理を終了する。
【００７２】
図５の処理は繰り返し実行される。
【００７３】
以上のように、データ修正処理では、検索用データに基づいて、直近の移動履歴を修正して、過去履歴DB１３に供給することができるので、過去の移動履歴として蓄積するデータ（検索用データ）の精度を向上させることができる。
【００７４】
以上、図１乃至図５を参照して、図１の予測装置１の処理の概要について説明した。
【００７５】
図１の予測装置１は、検索用データを過去履歴DB１３にどのように持たせるかによって、予測処理、センサ制御処理、およびデータ修正処理のそれぞれを、異なる方法で実行することができる。
【００７６】
１つは、取得された時刻、緯度、および経度の時系列データである経路ログを検索用データとして過去履歴DB１３に記憶させ、その経路ログを用いて行う方法である。他の１つは、取得された時刻、緯度、および経度の時系列データを学習した学習モデルを検索用データとして過去履歴DB１３に記憶させ、その学習モデルを用いて行う方法である。学習モデルには、例えば、確率遷移モデルが採用される。
【００７７】
以下では、経路ログを用いて行う場合を、予測装置１の第１の実施の形態として説明し、学習モデルを用いて行う場合を、予測装置１の第２の実施の形態として説明する。
【００７８】
＜２．第１の実施の形態＞
［第１の実施の形態の予測装置１の構成例］
図６は、第１の実施の形態における予測装置１の構成例を示すブロック図である。
【００７９】
図６の経路ログDB１３A、類似経路検索部１４A、適合判定部１５A、予測経路ログ抽出部１６A、出発時刻予測部１７A、予測値算出部１８A、および検索ログ修正部２０Aが、図１の過去履歴DB１３、類似検索部１４、適合判定部１５、予測経路抽出部１６、出発時刻予測部１７、予測値算出部１８、およびDB修正部２０に対応する。
【００８０】
経路ログDB１３Aは、過去の移動履歴と、目的地リストを記憶する。
【００８１】
図７は、経路ログDB１３Aに記憶される過去の移動履歴のデータ例を示している。図７に示されるように、取得された時刻と位置（経度、緯度）が、取得された時間順に記憶される。取得間隔は、センサ制御部１９により制御された所定の時間間隔である。
【００８２】
なお、位置センサ部１１が位置のデータを一定間隔に取得することができない場合もある。例えば、トンネルや地下にいる場合などには、人工衛星を捕捉することができず、取得間隔が長くなることもある。そのような場合には、例えば、線形補間により等間隔に補間されてから記憶される。過去の移動履歴には、取得時刻の古い順に、例えば、通し番号等が付されて記憶されている。
【００８３】
図８は、経路ログDB１３Aに記憶される目的地リストの例を示している。
【００８４】
目的地リストは、目的地に対して順に付されたインデックスと、目的地の位置（経度、緯度）とから構成される。
【００８５】
図９は、経路ログDB１３Aに記憶されている、過去の移動履歴と、目的地リストに記載されている目的地を地図上に示した図である。
【００８６】
図９において、丸（○）で囲まれた位置の中心が目的地であり、それらをつなぐように示される灰色の点が、過去の移動履歴をプロットしたものである。
【００８７】
図６に戻り、類似経路検索部１４Aは、経路ログDB１３Aの過去の移動履歴をスキャンして、バッファ１２から供給される直近の移動履歴と、過去の移動履歴の各箇所（位置）との類似度を算出する。
【００８８】
類似経路検索部１４Aにおいて、過去の移動履歴のｉ番目の箇所と、直近の移動履歴との類似度Ｄ（ｉ）は、次式（１）で計算される。
【数１】
【００８９】
式（１）のｘpastは、過去の移動履歴を表し、ｘcurrentは、直近の移動履歴を表す。右下の添え字は、過去の移動履歴または直近の移動履歴の通し番号を表す。また、式（１）のDistance(x,y)は、二つの箇所ｘとｙとの距離を求める関数であり、ユークリッド距離、若しくは、市街地距離（直交方向の差ベクトルの成分の和）、または、それらの二乗などとすることができる。Σは、Kステップ分についての和を表す。
【００９０】
従って、式（１）の類似度Ｄ（ｉ）は、バッファ１２から供給される直近の移動履歴がＫステップ分の位置データであり、Ｋステップ分の直近の移動履歴と、過去の移動履歴のなかのｉ番目から過去Ｋステップ分の移動履歴との、対応するステップ間の距離（総和）に相当する。
【００９１】
なお、式（１）でマイナスを乗じているのは、類似するほど、類似度Ｄ（ｉ）が大きい値となるようにするためである。
【００９２】
式（１）の類似度Ｄ（ｉ）は、Kステップ分についての和を、さらにステップ数Kで除算して、距離の平均としてもよい。
【００９３】
なお、類似度Ｄ（ｉ）の算出方法は、これに限定されるものではない。例えば、もっと簡便に、直近の移動履歴の中から、直近の箇所と、所定時間前のもう一箇所を選択し、過去の移動履歴の中から、選択した直近の二箇所に近く、また、所定時間程度の間隔にある二箇所を検出して、検出された二箇所と直近の二箇所の対応する箇所どうしの距離を利用するものでもよい。
【００９４】
類似経路検索部１４Aは、式（１）の類似度Ｄ（ｉ）を適合度として求め、適合判定部１５Aに供給する。
【００９５】
適合判定部１５Aは、類似経路検索部１４Aにより求められた、過去の移動履歴の各箇所と直近の移動履歴の適合度が、所定の閾値以上であるかを判定し、取得された直近の移動履歴と適合する過去の移動履歴があるかを判定する。
【００９６】
予測経路ログ抽出部１６Aは、所定の閾値以上であるとして検出された過去の移動履歴の箇所に対して、経路ログDB１３Aの目的地リストのいずれかに至るまでの移動履歴を、予測経路として抽出する。所定の閾値以上であるとして検出された過去の移動履歴の箇所は、複数検出されることがある。
【００９７】
予測経路ログ抽出部１６Aは、抽出した予測経路から到達可能な目的地を、経路ログDB１３Aの目的地リストに基づいて、目的地ごとにリストアップする。
【００９８】
予測値算出部１８Aは、リストアップされた目的地ごとに、目的地への経路リストおよび代表経路、到達確率、並びに所要時間を算出する。
【００９９】
目的地への代表経路には、抽出された目的地への経路リストのうち、例えば、所要時間の最も短いものが採用される。その他、抽出された複数の予測経路の平均所要時間に最も近い予測経路を、代表経路としてもよい。
【０１００】
目的地の到達確率は、抽出された予測経路の全数を分母として、その目的地へ到達できる予測経路の本数を分子として算出することができる。
【０１０１】
目的地の所要時間は、その目的地への予測経路それぞれの所要時間の平均値とすることができる。なお、目的地の所要時間の算出には、明らかな異常値の予測経路については除外した平均値としてもよい。
【０１０２】
図１０は、予測値算出部１８Aにより得られた各目的地と、それぞれの目的地への到達確率と所要時間を地図上に示した例である。
【０１０３】
図６に戻り、出発時刻予測部１７Aは、予測経路ログ抽出部１６Aにより抽出された、適合度が所定の閾値以上の箇所を起点とした１以上の予測経路から、絶対または相対の出発時刻を算出し、センサ制御部１９に供給する。
【０１０４】
絶対の出発時刻を求める場合には、出発時刻予測部１７Aは、起点を中心とする所定の範囲（例えば、半径１００ｍ）を設定範囲として、初めて設定範囲から外にでるときの過去の時刻の平均値を算出し、絶対の出発時刻とする。
【０１０５】
相対の出発時刻を求める場合には、出発時刻予測部１７Aは、起点を中心とする所定の範囲（例えば、半径１００ｍ）を設定範囲として、設定範囲内にどれくらいのステップ数（時間）だけ滞在していたかを算出し、その平均値を相対の出発時刻（予測滞在時間）とする。
【０１０６】
絶対時刻は、例えば、オフィスへの出勤、退勤など習慣があり、行動の時間帯に規則性がある場合の予測に適している。一方、相対時刻は、休日の外出（買い物や散髪など）など、行動の時間帯に規則性がない場合の予測に適している。
【０１０７】
検索ログ修正部２０Aは、所定の閾値以上であるとして検出された過去の移動履歴を用いて、直近の移動履歴を修正し、修正後の直近の移動履歴を経路ログDB１３Aに供給する。
【０１０８】
図１１を参照して、検索ログ修正部２０Aによる直近の移動履歴の修正について説明する。
【０１０９】
検索ログ修正部２０Aは、所定の閾値以上であるとして検出された過去の移動履歴の箇所を起点とする、直近の移動履歴と同ステップ数（Kステップ）の過去の移動履歴を、経路ログDB１３A内で検索し、検索データとして切り出す。
【０１１０】
そして、検索ログ修正部２０Aは、切り出された１以上の検索データに対して、ステップごとの平均値を算出し、理想系列を生成する。さらに、検索ログ修正部２０Aは、理想系列と直近の移動履歴の平均を算出し、修正後の直近の移動履歴を生成する。
【０１１１】
図１１において、直近の移動履歴の黒丸（●）が最新の位置データ（箇所）であり、検索データの黒三角（▲）が、最新の位置データに対応する過去の移動履歴の箇所（起点）である。同様に、理想系列の白三角（△）と、修正後の移動履歴の白丸（○）も、直近の移動履歴の最新の位置データに対応する箇所である。
【０１１２】
なお、この例では、起点からのステップ数を、類似度を求める場合のステップ数と同一としたが、類似度を求める場合と異なるステップ数としてもよい。
【０１１３】
また、上述した例では、修正後の直近の移動履歴を単純平均により求めたが、理想系列と直近の移動履歴とで、理想系列に対する重みを重く設定した重み付け平均により求めてもよい。同様に、理想系列を求める場合も、より過去の移動履歴については重みを小さく設定するような重み付き平均により求めてもよい。
【０１１４】
この修正処理により、直近の移動履歴を、自動的に統計的に処理された位置に修正して、経路ログDB１３Aに蓄積させることができる。
【０１１５】
［予測処理のフローチャート］
図１２のフローチャートを参照して、第１の実施の形態における予測処理について説明する。
【０１１６】
初めに、ステップＳ６１において、類似経路検索部１４Aは、過去の移動履歴と目的地リストを経路ログDB１３Aから取得する。
【０１１７】
ステップＳ６２において、類似経路検索部１４Aは、バッファ１２から、直近の移動履歴を取得する。
【０１１８】
ステップＳ６３において、類似経路検索部１４Aは、過去の移動履歴をスキャンして、過去の移動履歴の各箇所（位置）について、直近の移動履歴との適合度を算出する。ここで、適合度には、例えば、式（１）の類似度Ｄ（ｉ）が採用される。
【０１１９】
ステップＳ６４において、適合判定部１５Aは、類似経路検索部１４Aにより求められた適合度に基づいて、所定の閾値以上の適合度を有する箇所が１以上あるかを判定する。
【０１２０】
ステップＳ６４で、所定の閾値以上の適合度を有する箇所が１つもないと判定された場合、予測処理は終了する。一方、ステップＳ６４で、所定の閾値以上の適合度を有する箇所が１以上あると判定された場合、処理はステップＳ６５に進む。
【０１２１】
ステップＳ６５において、予測経路ログ抽出部１６Aは、所定の閾値以上の適合度を有する箇所を選択する。
【０１２２】
そして、ステップＳ６６において、予測経路ログ抽出部１６Aは、選択した箇所（選択箇所）それぞれについて、選択箇所からいずれかの目的地に至るまでの過去の移動履歴を、予測経路として抽出する。
【０１２３】
ステップＳ６７において、予測経路ログ抽出部１６Aは、抽出した予測経路から到達可能な目的地を、経路ログDB１３Aの目的地リストに基づいて、目的地ごとにリストアップする。
【０１２４】
そして、ステップＳ６８において、予測値算出部１８Aは、リストアップされた目的地ごとに、目的地への経路リストおよび代表経路を算出する。代表経路には、例えば、目的地への複数の予測経路のうち、所要時間の最も短いものが採用される。
【０１２５】
ステップＳ６９において、予測値算出部１８Aは、各目的地への到達確率を算出し、ステップＳ７０において、各目的地への所要時間を算出して出力し、処理を終了する。
【０１２６】
［絶対の出発予測時刻を用いた第２のセンサ制御処理のフローチャート］
次に、図１３のフローチャートを参照して、第１の実施の形態における、絶対の出発予測時刻を用いた第２のセンサ制御処理について説明する。
【０１２７】
図１３のステップＳ８１乃至Ｓ８４は、図１２のステップＳ６１乃至Ｓ６４と同様であるので、その説明は省略する。
【０１２８】
ステップＳ８４で、所定の閾値以上の適合度を有する箇所が１つもないと判定された場合、処理はステップＳ８５に進み、センサ制御部１９は、位置センサ部１１を、データ取得間隔が短くなるように制御して、処理を終了する。
【０１２９】
一方、ステップＳ８４で、所定の閾値以上の適合度を有する箇所が１以上あると判定された場合、処理はステップＳ８６に進み、予測経路ログ抽出部１６Aは、所定の閾値以上の適合度を有する箇所を選択する。
【０１３０】
ステップＳ８７において、出発時刻予測部１７Aは、適合度が所定の閾値以上の選択箇所から、最初に設定範囲外に出るときの過去の時刻の平均値を算出し、絶対の出発時刻とする。算出された絶対の出発時刻は、センサ制御部１９に供給される。
【０１３１】
ステップＳ８８において、センサ制御部１９は、出発時刻予測部１７Aから供給された絶対の出発時刻と、現在時刻との差分を算出する。
【０１３２】
そして、ステップＳ８９において、センサ制御部１９は、算出された差分が所定の閾値（以下、出発時刻閾値という。）より大であるかを判定する。
【０１３３】
ステップＳ８９で、算出された差分が出発時刻閾値以下であると判定された場合、処理はステップＳ９０に進み、センサ制御部１９は、データ取得間隔が短くなるように制御して、処理を終了する。
【０１３４】
一方、ステップＳ８９で、算出された差分が出発時刻閾値より大であると判定された場合、処理はステップＳ９１に進み、センサ制御部１９は、データ取得間隔が長くなるように制御して、処理を終了する。
【０１３５】
第１の実施の形態における第１のセンサ制御処理は、上述したステップＳ８６乃至Ｓ９０を省略した処理となる。
【０１３６】
［相対の出発予測時刻を用いた第２のセンサ制御処理のフローチャート］
図１４のフローチャートを参照して、第１の実施の形態における、相対の出発予測時刻を用いた第２のセンサ制御処理について説明する。
【０１３７】
図１４の相対の出発予測時刻を用いた第２のセンサ制御処理は、図１３の絶対の出発予測時刻を用いた第２のセンサ制御処理と比較すると、図１３のステップＳ８７乃至Ｓ８９に対応するステップＳ１０７およびＳ１０８が異なるのみである。従って、図１４では、ステップＳ１０７およびＳ１０８の処理のみ説明し、それ以外の説明は省略する。
【０１３８】
ステップＳ１０７において、出発時刻予測部１７Aは、選択箇所を中心とする設定範囲内を離れるまでの時間（ステップ数）の平均値を予測滞在時間として算出する。
【０１３９】
ステップＳ１０８において、出発時刻予測部１７Aは、算出された予測滞在時間が所定の閾値（以下、滞在時間閾値という。）より大であるかを判定する。
【０１４０】
ステップＳ１０８で、算出された予測滞在時間が滞在時間閾値以下であると判定された場合、処理はステップＳ１０９に進む。
【０１４１】
一方、ステップＳ１０８で、算出された予測滞在時間が滞在時間閾値より大であると判定された場合、処理はステップＳ１１０に進む。
【０１４２】
ステップＳ１０９またはＳ１１０において、所定のデータ取得間隔がセンサ制御部１９に設定されて、処理は終了する。
【０１４３】
以上のように、絶対の出発予測時刻を用いた第２のセンサ制御処理、または、相対の出発予測時刻を用いた第２のセンサ制御処理は行われるが、両者の処理結果を組み合わせた結果に基づいて、最終的にデータ取得間隔を決定するようにしてもよい。
【０１４４】
［データ修正処理のフローチャート］
次に、図１５のフローチャートを参照して、第１の実施の形態における、データ修正処理について説明する。
【０１４５】
図１５のステップＳ１２１乃至Ｓ１２５は、図１２のステップＳ６１乃至Ｓ６５と同様であるので、その説明は省略する。
【０１４６】
ステップＳ１２６において、検索ログ修正部２０Aは、選択箇所を起点とする数ステップ（Kステップ）の過去の移動履歴を、経路ログDB１３A内で検索し、検索データとして切り出す。これにより、１以上の検索データが切り出される。
【０１４７】
ステップＳ１２７において、検索ログ修正部２０Aは、切り出した１以上の検索データに対して、ステップごとの平均値を算出し、理想系列を生成する。
【０１４８】
ステップＳ１２８において、検索ログ修正部２０Aは、理想系列と直近の移動履歴の平均を算出することで、修正後の直近の移動履歴を生成して、処理を終了する。
【０１４９】
以上のように、予測装置１の第１の実施の形態では、過去履歴DB１３に記憶されている経路ログを用いて、予測処理、センサ制御処理、およびデータ修正処理を行うことができる。
【０１５０】
＜３．第２の実施の形態＞
［第２の実施の形態の予測装置１の構成例］
図１６は、第２の実施の形態における予測装置１の構成例を示すブロック図である。
【０１５１】
図１６の確率遷移モデルDB１３B、類似ノード検索部１４B、適合判定部１５B、予測ノード探索部１６B、出発時刻予測部１７B、予測値算出部１８B、およびモデル用データ修正部２０Bが、図１の過去履歴DB１３、類似検索部１４、適合判定部１５、予測経路抽出部１６、出発時刻予測部１７、予測値算出部１８、およびDB修正部２０に対応する。
【０１５２】
確率遷移モデルDB１３Bは、過去の移動履歴を学習モデルとしての確率遷移モデルにより学習した結果を記憶する。換言すれば、確率遷移モデルDB１３Bには、過去の移動履歴を学習モデルとしての確率遷移モデルで学習して得られたパラメータが検索用データとして記憶される。
【０１５３】
また、確率遷移モデルDB１３Bには、モデル用データ修正部２０Bから、新たな移動履歴が供給されるので、確率遷移モデルDB１３Bは、所定のタイミングで（例えば、一日おき、一週間おきなど）新たな移動履歴を用いて確率遷移モデルのパラメータを更新し、記憶する。
【０１５４】
さらに、確率遷移モデルDB１３Bは、第１の実施の形態における経路ログDB１３Aと同様に、目的地リストも記憶する。
【０１５５】
図１７は、過去の移動履歴を学習するための確率遷移モデルの概念図である。
【０１５６】
図１７に示される確率遷移モデルは、状態数が３（N=３）の隠れマルコフモデル（以下、HMMという。）を示している。HMMは、複数の離散化された状態ノードsiで構成される。さらに詳しく言えば、HMMは、複数の離散化された状態ノードsiについての、正規分布を持つ確率変数などで表される状態を決めるパラメータと、状態遷移を決めるパラメータで表現される。以下では、状態を決めるパラメータと状態遷移を決めるパラメータの両者を合わせて、HMMのパラメータともいい、状態ノードは、単に状態ともいう。
【０１５７】
状態を決めるパラメータは、状態ノードsiの観測モデルであり、状態ノードsiの中心値（平均値）μiと分散値σi2で構成される。状態遷移を決めるパラメータは、状態ノードsiの内部モデルであり、状態ノードsiから状態ノードsjへの状態遷移確率aijで構成される。
【０１５８】
図１８は、学習モデルとしてのHMMに過去の移動履歴を学習させた場合の、HMMの各状態ノードの観測モデルと内部モデルの例を示している。
【０１５９】
内部モデルとしての状態遷移確率aijには、自分の状態ノードsiへ遷移する自己遷移確率も存在する。観測モデルとしての状態ノードsiの中心値μiと分散値σi2は、時刻、経度、及び緯度のそれぞれについて求められる。なお、学習初期の各状態ノードsiには、初期状態を表す初期値が適宜設定される。
【０１６０】
図１９は、図９に示した過去の移動履歴と目的地を確率遷移モデルとしてのHMMに学習させたときの学習結果を地図上に示した図である。図１９において、経路上をつなぐように示される略楕円が、学習された各状態ノードを示している。
【０１６１】
HMMのパラメータを推定する方法としては、Baum-Welchの再尤推定法が広く利用されている。Baum-Welchの再尤推定法は、EMアルゴリズム(EM(Expectation-Maximization) algorithm)に基づくパラメータの推定方法である。
【０１６２】
Baum-Welchの再尤推定法によれば、観測される時系列データx=x1,x2,・・・,xTに基づき、その時系列データが観測（生起）される確率である生起確率から求まる尤度を最大化するように、HMMのパラメータの推定が行われる。ここで、xtは、時刻tに観測される信号（サンプル値）を表し、Tは、時系列データの長さ（サンプル数）を表す。
【０１６３】
Baum-Welchの再尤推定法については、例えば、“パターン認識と学習のアルゴリズム”，上坂吉則・尾関和彦著，文一総合出版，P.121に記載されている。
【０１６４】
図１６に戻り、類似ノード検索部１４Bは、バッファ１２から供給される直近の移動履歴に対応する確率遷移モデルの状態ノードを検索する。換言すれば、類似ノード検索部１４Bは、直近の移動履歴の現在地（最新の箇所）に対応する状態ノードの状態確率が最大となる状態ノードを探索（選択）する。
【０１６５】
適合判定部１５Bは、直近の移動履歴の現在地に対応する状態ノードの適合度が、所定の閾値以上であるかを判定する。確率遷移モデルを用いた場合の適合度の算出方法については後述する。直近の移動履歴の現在地に対応する状態ノードの適合度が所定の閾値以上である場合、既知の判定結果が、センサ制御部１９、予測ノード探索部１６B、およびモデル用データ修正部２０Bに供給される。また、探索して得られた状態ノードが、予測ノード探索部１６Bとモデル用データ修正部２０Bに供給される。一方、直近の移動履歴（の現在地）に対応する状態ノードの適合度が所定の閾値未満である場合、未知の判定結果が、センサ制御部１９に供給される。
【０１６６】
予測ノード探索部１６Bは、適合判定部１５B供給される、探索して得られた現在地に対応する状態ノードから、遷移可能な目的地の状態ノード（目的地ノード）をツリー探索することにより、目的地を探索する。そして、予測ノード探索部１６Bは、探索された目的地を、目的地ごとにリストアップする。
【０１６７】
予測値算出部１８Bは、リストアップされた目的地ごとに、目的地への経路リストおよび代表経路、到達確率、並びに、所要時間を算出する。
【０１６８】
出発時刻予測部１７Bは、探索して得られた現在地に対応する状態ノードに基づいて、絶対または相対の出発時刻を算出し、センサ制御部１９に供給する。
【０１６９】
絶対の出発時刻は、探索して得られた現在地に対応する状態ノードの自己遷移以外の１以上の遷移先の時刻の中心値の平均により求めることができる。あるいは、探索して得られた現在地に対応する状態ノードの自己遷移以外の遷移先の時刻のなかで、最も現在時刻に近い将来の時刻を中心値としてもつものを、絶対の出発時刻として選択するようにしてもよい。
【０１７０】
また、相対の出発時刻（予測滞在時間）は、探索して得られた現在地に対応する状態ノードの自己遷移確率を用いた次式（２）に、単位ステップの時間を乗算した値により求めることができる。
【０１７１】
【数２】
式（２）において、ｔstayが予測滞在時間を表し、ａssは、探索して得られた状態ノードを表す。なお、式（２）は、自己遷移確率が１であるとき発散するので、予測滞在時間には上限値を設定しておく方がよい。
【０１７２】
モデル用データ修正部２０Bは、直近の移動履歴に対応する状態ノードの状態ノード系列を用いて、直近の移動履歴を修正し、修正後の直近の移動履歴を確率遷移モデルDB１３Bに供給する。
【０１７３】
図２０を参照して、モデル用データ修正部２０Bによる直近の移動履歴の修正について説明する。
【０１７４】
モデル用データ修正部２０Bは、直近の移動履歴に対応する状態ノードの状態ノード系列（対応ノード系列）を生成し、生成された対応ノード系列の中心値の系列を、理想系列として生成する。そして、モデル用データ修正部２０Bは、理想系列と直近の移動履歴の平均を算出し、修正後の直近の移動履歴を生成する。
【０１７５】
図２１は、モデル用データ修正部２０Bによる、その他の修正方法を示している。
【０１７６】
図２１に示される修正方法が、図２０に示した修正方法と異なる点は、直近の移動履歴の各ステップに対して、確率遷移モデルを構成する各状態ノードの確率を用いる点である。即ち、図２１では、直近の移動履歴の各ステップに対する各状態ノードの確率δj(t)が確率テーブルとして示されている。直近の移動履歴の各ステップに対する各状態ノードの確率δj(t)の算出方法は、後述する式（５）で求められる。
【０１７７】
モデル用データ修正部２０Bは、直近の移動履歴に対応する理想系列を、確率テーブルを用いた次式（３）で算出する。
【数３】
【０１７８】
式（３）は、直近の移動履歴の各ステップについて、各状態ノードの緯度および経度の中心値μjを、状態ノードの確率δj(t)で重み付けして加算した値を、直近の移動履歴の各ステップに対応する理想系列の位置<xt>とすることを表す。ここで、tは、直近の移動履歴の各ステップの取得時刻に対応するステップ数（通し番号）である。
【０１７９】
[学習装置の構成例]
次に、確率遷移モデルDB１３Bに記憶される確率遷移モデルを学習する学習装置について説明する。
【０１８０】
図２２は、確率遷移モデルDB１３Bに記憶される確率遷移モデルのパラメータを求める学習装置６０の構成例を示している。
【０１８１】
学習装置６０は、ログ取得部６１、前処理部６２、状態ノード割り当て部６３、モデル再構成部６４、目的地リスト修正部６５、およびモデル記憶部６６により構成される。
【０１８２】
ログ取得部６１は、学習データとしての過去の移動履歴を取得し、前処理部６２に供給する。
【０１８３】
前処理部６２は、学習データの一時的なデータの欠落部分に対し、線形補間等の補間処理を行うことで補間して、処理後の過去の移動履歴を状態ノード割り当て部６３に供給する。
【０１８４】
状態ノード割り当て部６３は、前処理部６２から供給された過去の移動履歴に対し、確率遷移モデルの状態ノードを割り当てる。より具体的には、状態ノード割り当て部６３は、学習データである過去の移動履歴の各位置データに対して既存の確率遷移モデルとの適合度を算出し、適合度が所定の閾値以上であるか否かを判定する。そして、適合度が所定の閾値以上である場合、状態ノード割り当て部６３は、その位置データに対しては既存の状態ノードを割り当てる。一方、適合度が所定の閾値未満である場合、状態ノード割り当て部６３は、その位置データに対しては新規の状態ノードを割り当てる。そして、過去の移動履歴に対応して割り当てられた、状態ノードのノード番号の系列データ（対応ノード系列）が、モデル再構成部６４に供給される。
【０１８５】
モデル再構成部６４は、状態ノード割り当て部６３からの対応ノード系列に基づいて、確率遷移モデルを再構成するモデル再構成処理を行う。即ち、モデル再構成部６４は、現在の確率遷移モデルの状態ノードのパラメータの修正、および、新たな状態ノードのパラメータの追加を行う。
【０１８６】
目的地リスト修正部６５は、過去の移動履歴に新たな目的地が追加された場合、モデル記憶部６６に記憶されている目的地リストを修正する。
【０１８７】
モデル記憶部６６は、学習モデルとしての確率遷移モデルのパラメータを記憶する。また、モデル記憶部６６は、目的地リストも記憶する。
【０１８８】
図２３は、図２２の状態ノード割り当て部６３の詳細構成例を示している。
【０１８９】
状態ノード割り当て部６３は、モデル取得部７１、対応ノード系列推定部７２、適合度閾値判定部７３、既存ノード割り当て部７４、および新規ノード割り当て部７５により構成される。
【０１９０】
モデル取得部７１は、モデル記憶部６６から、確率遷移モデルのパラメータを取得して、対応ノード系列推定部７２に供給する。
【０１９１】
対応ノード系列推定部７２は、学習データである過去の移動履歴に対して、既存の確率遷移モデルを用いて、対応する状態ノード系列である対応ノード系列を生成（推定）する。
【０１９２】
適合度閾値判定部７３は、対応ノード系列推定部７２で推定された対応ノード系列を構成する状態ノードそれぞれについて、適合度が所定の閾値以上であるか否かを判定する。換言すれば、適合度閾値判定部７３は、学習データとして供給された過去の移動履歴が既知の経路であるか、または、未知の経路であるかを判定する。そして、適合度閾値判定部７３は、適合度が所定の閾値以上である（既知の経路である）と判定された学習データ（過去の移動履歴）を、既存ノード割り当て部７４に供給し、適合度が所定の閾値未満である（未知の経路である）と判定された学習データを、新規ノード割り当て部７５に供給する。
【０１９３】
既存ノード割り当て部７４は、適合度閾値判定部７３から供給された既知経路の学習データに対して、既存の確率遷移モデルの状態ノードを割り当てる既存ノード割り当て処理を行う。
【０１９４】
新規ノード割り当て部７５は、適合度閾値判定部７３から供給された未知経路の学習データに対し、新規の確率遷移モデルの状態ノードを割り当てる新規ノード割り当て処理を行う。
【０１９５】
既存ノード割り当て処理および新規ノード割り当て処理によって割り当てられた状態ノードのノード系列が、図２２のモデル再構成部６４に供給される。
【０１９６】
[学習処理のフローチャート]
図２４は、学習装置６０による学習処理のフローチャートを示している。
【０１９７】
初めに、ステップＳ１６１において、ログ取得部６１は、学習データとしての過去の移動履歴を取得し、前処理部６２に供給する。
【０１９８】
ステップＳ１６２において、前処理部６２は、学習データの一時的なデータの欠落部分に対し、線形補間等の補間処理を行うことで補間して、処理後の過去の移動履歴を状態ノード割り当て部６３に供給する。
【０１９９】
ステップＳ１６３において、状態ノード割り当て部６３のモデル取得部７１は、モデル記憶部６６から、確率遷移モデルのパラメータを取得して、対応ノード系列推定部７２に供給する。
【０２００】
ステップＳ１６４において、状態ノード割り当て部６３の対応ノード系列推定部７２は、学習データである過去の移動履歴の各位置データに対して既存の確率遷移モデルとの適合度を算出する適合度算出処理を行う。
【０２０１】
ステップＳ１６５において、状態ノード割り当て部６３の適合度閾値判定部７３は、学習データを構成する各位置データを識別するステップ番号ｉに１をセットして、ステップＳ１６６に進み、ｉステップ目の適合度が所定の閾値以上であるかを判定する。
【０２０２】
ステップＳ１６６で、ｉステップ目の適合度が所定の閾値以上であると判定された場合、処理はステップＳ１６７に進み、適合度閾値判定部７３は、学習データのステップ番号ｉの位置データは既存ノードに対応すると判定する。
【０２０３】
一方、ステップＳ１６６で、ｉステップ目の適合度が所定の閾値未満であると判定された場合、処理はステップＳ１６８に進み、適合度閾値判定部７３は、学習データのステップ番号ｉの位置データは新規ノードに対応すると判定する。
【０２０４】
ステップＳ１６９において、適合度閾値判定部７３は、全ての学習データについて既存ノードかまたは新規ノードを判定したかを判定する。
【０２０５】
ステップＳ１６９で、全ての学習データについて判定していないと判定された場合、処理はステップＳ１７０に進み、適合度閾値判定部７３は、ステップ番号を１だけインクリメントして、処理はステップＳ１６６に戻る。
【０２０６】
一方、ステップＳ１６９で、全ての学習データについて判定したと判定された場合、処理はステップＳ１７１に進み、状態ノード割り当て部６３の既存ノード割り当て部７４は、既知経路の学習データに対して、既存の確率遷移モデルの状態ノードを割り当てる既存ノード割り当て処理を行う。
【０２０７】
次に、ステップＳ１７２において、状態ノード割り当て部６３の新規ノード割り当て部７５は、未知経路の学習データに対し、新規の確率遷移モデルの状態ノードを割り当てる新規ノード割り当て処理を行う。
【０２０８】
ステップＳ１７１とＳ１７２の処理は並行して実行することができる。
【０２０９】
そして、ステップＳ１７３において、モデル再構成部６４は、状態ノード割り当て部６３からの対応ノード系列に基づいて、確率遷移モデルを再構成するモデル再構成処理を行う。
【０２１０】
ステップＳ１７４において、目的地リスト修正部６５は、過去の移動履歴に新たな目的地が追加された場合、追加された目的地をモデル記憶部６６に記憶されている目的地リストに追加して、処理を終了する。なお、追加の目的地がない場合には、ステップＳ１７４の処理は省略される。
【０２１１】
［適合度算出処理のフロー］
図２５は、図２４のステップＳ１６４で実行される適合度算出処理のフローチャートである。
【０２１２】
この処理では、初めに、ステップＳ１８１において、状態ノード割り当て部６３は、学習データを構成する各位置データを識別するステップ番号ｉに１をセットする。
【０２１３】
そして、ステップＳ１８２において、状態ノード割り当て部６３は、次式（４）により、ステップｉにおける各状態の観測尤度を算出する。
【数４】
式（４）の観測尤度は、中心値μiと分散値σi2の正規分布を持つ状態ノードsiから、データxiが観測される尤度を表す。なお、Π｛xd｝は、ｄ＝１，２，３としたときのxdを乗算することを表し、ｄ＝１，２，３は、それぞれ、過去の移動経路の時刻、緯度、および経度を表す。
【０２１４】
ステップＳ１８３において、状態ノード割り当て部６３は、次式（５）により、ステップｉにおける各状態の状態確率を算出する。
【数５】
式（５）において、δi(1)は、先頭ステップで状態siである確率を表す。また、δi(t)は、ステップtで、状態sjである確率を表す。式（５）のmax［aijδi(t-1)］は、状態sjに至る状態遷移のうち、ステップt-1での状態確率と、その場所からの遷移確率の積が最大となるものを選択することを意味している。なお、式（５）におけるZtは規格化パラメータであり、全ての状態siでのδi(t)の和である。
【０２１５】
式（５）によれば、状態ノード間の遷移で構成されるトポロジーを反映した状態履歴の推定を行うことができる。
【０２１６】
ステップＳ１８４において、状態ノード割り当て部６３は、次式（６）により、ステップｉにおける観測尤度の期待値を算出し、適合度とする。
【数６】
式（６）は、時刻tでの状態ｓjの尤度P(xt|μj，ｓj)について、状態確率δj(t)を用いて期待値を算出したものである。
【０２１７】
ステップＳ１８５において、状態ノード割り当て部６３は、ステップｉが最終ステップであるかを判定する。
【０２１８】
ステップＳ１８５で、ステップｉが最終ステップではないと判定された場合、処理はステップＳ１８６に進み、状態ノード割り当て部６３は、ステップ番号ｉを１だけインクリメントして、処理はステップＳ１８２に戻る。
【０２１９】
一方、ステップＳ１８５で、ステップｉが最終ステップであると判定された場合、処理は図２４に戻る。
【０２２０】
［既存ノード割り当て処理のフロー］
次に、図２６のフローチャートを参照して、図２４のステップＳ１７１で実行される既存ノード割り当て処理について説明する。
【０２２１】
図２６のステップＳ２０１乃至Ｓ２０３は、上述した図２５のステップＳ１８１乃至Ｓ１８３と同様であるので、その説明は省略する。ただし、既存ノード割り当て処理でのステップ番号は、既存ノードと判定された学習データに対するステップ番号となる。
【０２２２】
ステップＳ２０４において、状態ノード割り当て部６３は、ステップｉにおける各状態に至る親ノードを記憶する。より具体的には、状態ノード割り当て部６３は、次式（７）で計算される状態ノードの番号を求め、記憶する。
【数７】
式（７）のΨj(t)は、ステップt-1での状態確率と、その場所からの遷移確率の積が最大となる状態ノードのノード番号となる。argmaxi［x］は、添え字iを、1からNまでの範囲の整数に変えて得られるｘを最大にする添え字iを表す。
【０２２３】
ステップＳ２０５において、状態ノード割り当て部６３は、ステップｉが最終ステップであるかを判定する。
【０２２４】
ステップＳ２０５で、ステップｉが最終ステップではないと判定された場合、処理はステップＳ２０６に進み、状態ノード割り当て部６３は、ステップ番号ｉを１だけインクリメントして、処理はステップＳ２０２に戻る。
【０２２５】
一方、ステップＳ２０５で、ステップｉが最終ステップであると判定された場合、処理はステップＳ２０７に進み、状態ノード割り当て部６３は、最終ステップで状態確率を最大にする状態ノードを選択する。
【０２２６】
より具体的には、ステップＳ２０７の処理は、最終ステップを例えば、ｔ＝Tとすると、S(T)＝argmaxi［δi(T)］とする処理であり、最終的に最も状態確率の高い状態ノードを、既知経路の学習データの最終ステップに対応させる処理である。
【０２２７】
ステップＳ２０８において、状態ノード割り当て部６３は、ステップＳ２０７で選択された状態ノードから、ステップＳ２０４で記憶しておいた親ノードを逆向きに探索する。
【０２２８】
ステップＳ２０８の処理は、S(t-1)＝Ψ(S(t))とする処理である。これにより、移動履歴のｔステップ目に対応する状態ノードS(t)を順次求めることができ、最終的に、既知の移動履歴に対応する状態ノード系列が得られる。
【０２２９】
ステップＳ２０９において、状態ノード割り当て部６３は、ステップＳ２０８で得られた状態ノード系列を、学習データである既知の移動履歴と対応付けて内部に記憶し、図２４に戻る。
【０２３０】
［新規ノード割り当て処理のフロー］
次に、図２７のフローチャートを参照して、図２４のステップＳ１７２で実行される新規ノード割り当て処理について説明する。
【０２３１】
初めに、ステップＳ２２１において、状態ノード割り当て部６３は、学習データである未知の移動履歴をHMM（確率遷移モデル）で学習する。ステップＳ２２１では、未知の移動履歴の１ステップごとに新しい状態ノードが割り当てられ、未知の移動履歴に対応するHMMのパラメータが求められる。
【０２３２】
ステップＳ２２２において、状態ノード割り当て部６３は、学習により得られた状態ノードに、既存のHMM（確率遷移モデル）に付加する状態ノードとしての新たなノード番号を割り当てる。
【０２３３】
ステップＳ２２３において、状態ノード割り当て部６３は、学習データである未知の移動履歴と、対応する新たなノード番号の状態ノード系列を内部に記憶し、図２４に戻る。
【０２３４】
[モデル再構成処理のフロー]
次に、図２８のフローチャートを参照して、図２４のステップＳ１７３で実行されるモデル再構成処理について説明する。
【０２３５】
初めに、ステップＳ２４１において、モデル再構成部６４は、遷移頻度テーブルを作成する。
【０２３６】
図２９は、ステップＳ２４１で作成される遷移頻度テーブルの例を示している。遷移頻度テーブルは、図１８に示したHMMの状態遷移確率aijが、遷移頻度とされたものである。
【０２３７】
ステップＳ２４２において、モデル再構成部６４は、遷移頻度テーブルの遷移頻度から、次式（８）により、状態頻度テーブルを生成する。
【数８】
式（８）は、状態siの状態頻度ｆiが状態siの遷移頻度ｆijの総和により得られることを表している。
【０２３８】
ステップＳ２４３において、モデル再構成部６４は、状態頻度テーブルを用いて、次式（９）により、状態頻度の中心値Ｍiと分散Σi2とからなる統計量テーブルを生成する。
Ｍi＝μi・ｆi ，Σi2＝（σi2＋μi）・ｆi ・・・・・（９）
【０２３９】
ステップＳ２４４において、モデル再構成部６４は、図２６の既存ノード割り当て処理、および、図２７の新規ノード割り当て処理により生成されて記憶されている、学習データに対応する状態ノード系列を用いて、遷移頻度テーブルを更新する。ここで、更新後の遷移頻度ｆijは遷移頻度ｆij’で表し、更新後の状態頻度テーブルはｆi’で表される。
【０２４０】
ステップＳ２４５において、モデル再構成部６４は、図２６の既存ノード割り当て処理、および、図２７の新規ノード割り当て処理で出現する状態ノードに対応する位置データと、その二乗値を、状態頻度の中心値Ｍiと分散Σi2に加算することにより、式（９）の統計量テーブルを更新する。更新後の統計量テーブルの状態頻度の中心値Ｍiと分散Σi2は、Ｍi’，Σi2’で表される。
【０２４１】
ステップＳ２４６において、モデル再構成部６４は、次式（１０）により、図２６の既存ノード割り当て処理、および、図２７の新規ノード割り当て処理で出現する状態ノードの中心値μiと分散値σi2を、μi’とσi2’に更新して、図２４に戻る。
μi’＝Ｍi’/ｆi’ ，σi2’＝Σi2’/ｆi’−μi’2）・ ・・・・・（１０）
【０２４２】
以上、図２４乃至図２８を参照して説明した学習処理により、新たに入力された移動履歴に基づいて、既存の学習モデルを修正（更新）、拡張することができる。なお、既存モデルが存在しない最初の学習処理は、入力された移動履歴が全て未知経路と判定されて確率遷移モデルが学習される処理であり、上述した処理で対応可能である。
【０２４３】
［予測処理のフローチャート］
次に、図３０のフローチャートを参照して、第２の実施の形態における予測処理について説明する。
【０２４４】
初めに、ステップＳ３０１において、類似ノード検索部１４Bは、事前の学習により得られた確率遷移モデル（のパラメータ）と目的地リストを確率遷移モデルDB１３Bから取得する。
【０２４５】
ステップＳ３０２において、類似ノード検索部１４Bは、バッファ１２から、直近の移動履歴を取得する。
【０２４６】
ステップＳ３０３において、類似ノード検索部１４Bは、直近の移動履歴に対応する状態ノードを探索して、選択する。具体的には、類似ノード検索部１４Bは、上述した学習処理で説明した適合度算出処理（図２４のステップＳ１６４、図２５）を行い、既存ノード割り当て処理（図２４のステップＳ１７１、図２６）を行うことにより、直近の移動履歴に対応する状態ノードを探索して、選択する。
【０２４７】
ステップＳ３０４において、適合判定部１５Bは、類似ノード検索部１４Bにより選択された状態ノードの適合度が所定の閾値以上であるかを判定する。
【０２４８】
ステップＳ３０４で、選択された状態ノードの適合度が所定の閾値未満であると判定された場合、予測処理は終了する。
【０２４９】
一方、ステップＳ３０４で、選択された状態ノードの適合度が所定の閾値以上であると判定された場合、処理はステップＳ３０５に進む。ステップＳ３０５では、予測ノード探索部１６Bは、選択された状態ノードから遷移可能な目的地ノードをツリー探索することにより目的地を探索する。
【０２５０】
ステップＳ３０６において、予測ノード探索部１６Bは、探索された目的地を、目的地ごとにリストアップする。
【０２５１】
ステップＳ３０７において、予測値算出部１８Bは、リストアップされた目的地ごとに、目的地への経路リストおよび代表経路を算出する。
【０２５２】
目的地iへの代表経路ｒiは、例えば、次式（１１）により求めることができる
【数９】
式（１１）において、Ｔjは、ｊ番目の経路リストの長さ（ステップ数）を表し、ａ(ｓk，ｓk+1)は、状態ノードｓkから状態ノードｓk+1への遷移確率を表す。したがって、ｓjkは、ｊ番目の経路リストのｋ番目の状態ノードを表し、ｓj１は現在地ノードであり、ｓjTjはｊ番目の経路リストの目的地ノードを表す。
【０２５３】
したがって、式（１１）は、目的地ｉについては最も生起確率の高いｒ番目の経路ｒiを代表経路とし、代表経路ｒiは、｛ｓ1，ｓ2，ｓ3，・・・，ｓTr｝の状態ノード系列を有することを意味している。代表経路の選択方法は、これ以外の方法を用いてもよい。
【０２５４】
ステップＳ３０８において、予測値算出部１８Bは、各目的地への到達確率を算出する。
【０２５５】
目的地iへの到達確率ｐiは、例えば、次式（１２）により求めることができる
【数１０】
式（１２）において、Niは、現在地ノードから、目的地ｉに到達する経路リストの本数を表す。
【０２５６】
ステップＳ３０９において、各目的地への所要時間を算出して出力し、処理を終了する。
【０２５７】
目的地iへの代表経路ｒiの所要時間ｔiは、例えば、次式（１３）により求めることができる
【数１１】
式（１３）において、ｓkは、代表経路ｒの状態ノード系列のｋ番目の状態ノードであり、Ｔは、代表経路の経路リストの長さ（ステップ数）であり、t=1が現在地ノードで、t=Tが目的地ノードである。
【０２５８】
また、式（１３）において、ｐs1(1)は、ステップ１に状態ノードｓ１にいる確率を表す。ｐsk(t)は、ステップtに状態ノードｓkにいる確率を表し、一つ前のステップにおいて状態ノードｓkにいて自己遷移した確率と、一つ前のステップにおいて状態ノードｓk-1にいて遷移してきた確率の和である。
【０２５９】
さらに、式（１３）の所要時間ｔiは、時刻t-1に目的地ノードｓTの一つ手前の状態ノードｓT-1にいて、時刻tで初めて目的地ノードｓTに移るときのｔの期待値である。
【０２６０】
［絶対の出発予測時刻を用いた第２のセンサ制御処理のフローチャート］
次に、図３１のフローチャートを参照して、第２の実施の形態における、絶対の出発予測時刻を用いた第２のセンサ制御処理について説明する。
【０２６１】
図３１のステップＳ３２１乃至Ｓ３２４は、図３０のステップＳ３０１乃至Ｓ３０４と同様であるので、その説明は省略する。
【０２６２】
ステップＳ３２４で、選択された状態ノードの適合度が所定の閾値未満であると判定された場合、処理はステップＳ３２５に進み、センサ制御部１９は、位置センサ部１１を、データ取得間隔が短くなるように制御して、処理を終了する。
【０２６３】
一方、ステップＳ３２４で、選択された状態ノードの適合度が所定の閾値以上であると判定された場合、処理はステップＳ３２６に進む。
【０２６４】
ステップＳ３２６において、出発時刻予測部１７Bは、選択された状態ノードの自己遷移以外の１以上の遷移先の状態ノードの時刻の中心値の平均（平均時刻）を、絶対の出発時刻として算出する。算出された絶対の出発時刻は、センサ制御部１９に供給される。
【０２６５】
ステップＳ３２７において、センサ制御部１９は、出発時刻予測部１７Bから供給された絶対の出発時刻と、現在時刻との差分を算出する。
【０２６６】
ステップＳ３２８において、センサ制御部１９は、算出された差分が所定の閾値（出発時刻閾値）より大であるかを判定する。
【０２６７】
ステップＳ３２８で、算出された差分が出発時刻閾値以下であると判定された場合、処理はステップＳ３２９に進み、センサ制御部１９は、データ取得間隔が短くなるように制御して、処理を終了する。
【０２６８】
一方、ステップＳ３２８で、算出された差分が出発時刻閾値より大であると判定された場合、処理はステップＳ３３０に進み、センサ制御部１９は、データ取得間隔が長くなるように制御して、処理を終了する。
【０２６９】
第２の実施の形態における第１のセンサ制御処理は、上述したステップＳ３２６乃至Ｓ３２９を省略した処理となる。
【０２７０】
［相対の出発予測時刻を用いた第２のセンサ制御処理のフローチャート］
次に、図３２のフローチャートを参照して、第２の実施の形態における、相対の出発予測時刻を用いた第２のセンサ制御処理について説明する。
【０２７１】
図３２の相対の出発予測時刻を用いた第２のセンサ制御処理は、図３１の絶対の出発予測時刻を用いた第２のセンサ制御処理と比較すると、図３１のステップＳ３２６乃至Ｓ３２８に対応するステップＳ３４６およびＳ３４７が異なるのみである。従って、図３２では、ステップＳ３４６およびＳ３４７の処理のみ説明し、それ以外の説明は省略する。
【０２７２】
ステップＳ３４６において、出発時刻予測部１７Bは、選択された状態ノードの自己遷移確率から、相対の出発時刻（予測滞在時間）を算出する。すなわち、選択された状態ノードの自己遷移確率を用いた式（２）に、単位ステップの時間を乗算することにより、予測滞在時間が求められ、センサ制御部１９に供給される。
【０２７３】
ステップＳ３４７において、出発時刻予測部１７Bは、算出された予測滞在時間が所定の閾値（滞在時間閾値）より大であるかを判定する。
【０２７４】
ステップＳ３４７で、算出された予測滞在時間が滞在時間閾値以下であると判定された場合、処理はステップＳ３４８に進む。
【０２７５】
一方、ステップＳ３４７で、算出された予測滞在時間が滞在時間閾値より大であると判定された場合、処理はステップＳ３４９に進む。
【０２７６】
ステップＳ３４８またはＳ３４９において、所定のデータ取得間隔がセンサ制御部１９に設定されて、処理は終了する。
【０２７７】
以上のように、絶対の出発予測時刻を用いた第２のセンサ制御処理、または、相対の出発予測時刻を用いた第２のセンサ制御処理が行われるが、両者の処理結果を組み合わせた結果に基づいて、最終的にデータ取得間隔を決定してもよい。
【０２７８】
［データ修正処理のフローチャート］
次に、図３３のフローチャートを参照して、第２の実施の形態における、データ修正処理について説明する。
【０２７９】
図３３のステップＳ３６１乃至Ｓ３６４は、図３０のステップＳ３０１乃至Ｓ３０４と同様であるので、その説明は省略する。
【０２８０】
ステップＳ３６５において、モデル用データ修正部２０Bは、直近の移動履歴の各ステップに対応する各状態ノードの確率δj(t)を取得する。
【０２８１】
ステップＳ３６６において、モデル用データ修正部２０Bは、式（３）により、直近の移動履歴に対応する理想系列を生成する。すなわち、モデル用データ修正部２０Bは、直近の移動履歴の各ステップに対応する各状態ノードの中心値に、状態ノードの確率δj(t)を重み付け加算することにより、理想系列を生成する。
【０２８２】
ステップＳ３６７において、モデル用データ修正部２０Bは、理想系列と直近の移動履歴の平均を算出することで、修正後の直近の移動履歴を生成して、処理を終了する。
【０２８３】
以上のように、予測装置１の第２の実施の形態では、確率遷移モデルDB１３Bに記憶されている確率遷移モデルを用いて、予測処理、センサ制御処理、およびデータ修正処理を行うことができる。
【０２８４】
＜４．第３実施の形態＞
［第３実施の形態の予測装置１の構成例］
上述した例では、予測装置１が、過去履歴DB１３の検索用データとして経路ログか、または、確率遷移モデルのいずれか一方を用いて、予測処理、センサ制御処理、およびデータ修正処理を行う例について説明した。
【０２８５】
しかしながら、予測装置１は、過去履歴DB１３の検索用データとして、経路ログ、および、確率遷移モデルの両方を有し、選択的に実行するようにしてもよい。
【０２８６】
図３４は、そのような予測装置１の構成例を示すブロック図である。すなわち、図３４は、経路ログ、および、確率遷移モデルの両方を有し、それらを選択的に実行する第３の実施の形態の予測装置１の構成例を示している。
【０２８７】
過去履歴DB１３は、第１の実施の形態の経路ログDB１３Aと第２の実施の形態の確率遷移モデルDB１３Bを有する。
【０２８８】
類似検索部１４は、第１の実施の形態の類似経路探索部１４Aと第２の実施の形態の類似ノード探索部１４Bを有する。
【０２８９】
適合判定部１５は、第１の実施の形態の適合判定部１５Aと第２の実施の形態の適合判定部１５Bを有する。
【０２９０】
予測経路抽出部１６は、第１の実施の形態の予測経路ログ抽出部１６Aと第２の実施の形態の予測ノード探索部１６Bを有する。
【０２９１】
出発時刻予測部１７、第１の実施の形態の出発時刻予測部１７Aと第２の実施の形態の出発時刻予測部１７Bを有する。
【０２９２】
DB修正部２０は、第１の実施の形態の検索ログ修正部２０と第２の実施の形態のモデル用データ修正部２０Bを有する。
【０２９３】
第３の実施の形態においては、例えば、経路ログ、または、確率遷移モデルのどちらを使用するかが、図示せぬ操作部でユーザにより選択される。経路ログを使用することが選択された場合には、第１の実施の形態として説明した処理が実行される。一方、確率遷移モデルを使用することが選択された場合には、第２の実施の形態として説明した処理が実行される。
【０２９４】
＜５．第４実施の形態＞
［第４実施の形態の予測装置１の構成例］
【０２９５】
上述した実施の形態では、予測装置１が、位置センサ部１１のデータ取得間隔を制御するセンサ制御機能と、直近の移動履歴を検索用データに基づいて修正するデータ修正機能の両方を有していた。
【０２９６】
しかしながら、予測装置１は、センサ制御機能、または、データ修正機能のいずれか一方のみを有するものでもよい。
【０２９７】
図３５は、予測装置１の第４の実施の形態としての、センサ制御機能のみを有する予測装置１の構成例を示すブロック図である。
【０２９８】
図３６は、予測装置１の第４の実施の形態としての、データ修正機能のみを有する予測装置１の構成例を示すブロック図である。
【０２９９】
第４の実施の形態の予測装置１の処理（動作）については、上述した説明と重複するので省略する。
【０３００】
［コンピュータの構成例］
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここで、コンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどが含まれる。
【０３０１】
図３７は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。
【０３０２】
コンピュータにおいて、CPU（Central Processing Unit）１０１，ROM（Read Only Memory）１０２，RAM（Random Access Memory）１０３は、バス１０４により相互に接続されている。
【０３０３】
バス１０４には、さらに、入出力インタフェース１０５が接続されている。入出力インタフェース１０５には、入力部１０６、出力部１０７、記憶部１０８、通信部１０９、及びドライブ１１０が接続されている。
【０３０４】
入力部１０６は、キーボード、マウス、マイクロホンなどよりなる。出力部１０７は、ディスプレイ、スピーカなどよりなる。記憶部１０８は、ハードディスクや不揮発性のメモリなどよりなる。通信部１０９は、ネットワークインタフェースなどよりなる。ドライブ１１０は、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブル記録媒体１１１を駆動する。
【０３０５】
以上のように構成されるコンピュータでは、CPU１０１が、例えば、記憶部１０８に記憶されているプログラムを、入出力インタフェース１０５及びバス１０４を介して、RAM１０３にロードして実行することにより、上述した一連の処理が行われる。
【０３０６】
コンピュータでは、プログラムは、リムーバブル記録媒体１１１をドライブ１１０に装着することにより、入出力インタフェース１０５を介して、記憶部１０８にインストールすることができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して、通信部１０９で受信し、記憶部１０８にインストールすることができる。その他、プログラムは、ROM１０２や記憶部１０８に、あらかじめインストールしておくことができる。
【０３０７】
なお、本明細書において、フローチャートに記述されたステップは、記載された順序に沿って時系列的に行われる場合はもちろん、必ずしも時系列的に処理されなくとも、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで実行されてもよい。
【０３０８】
上述した実施の形態において、各種の条件を判定するための閾値は、それぞれ適切な値を適宜設定することができる。
【０３０９】
本技術の実施の形態は、上述した実施の形態に限定されるものではなく、本技術の要旨を逸脱しない範囲において種々の変更が可能である。
【０３１０】
なお、本技術は以下のような構成も取ることができる。
（１）
時系列の位置データでなる直近の移動履歴を取得する位置センサ部と、
検索用データを記憶する過去履歴DBと、
前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索する類似検索部と、
前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、
前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部と
を備える情報処理装置。
（２）
前記センサ制御部は、前記適合度が前記所定の閾値以上である場合に、前記位置データの取得間隔が、前記所定の閾値未満である場合よりも長くなるように制御する
前記（１）に記載の情報処理装置。
（３）
現在の位置を離れる時刻である出発時刻を予測する出発時刻予測部をさらに備え、
前記センサ制御部は、前記適合度が前記所定の閾値以上であり、かつ、前記出発時刻予測部で予測された出発予測時刻が所定時間より後である場合に、前記位置データの取得間隔が、前記所定の閾値未満である場合よりも長くなるように制御する
前記（１）または（２）に記載の情報処理装置。
（４）
前記出発時刻予測部は、絶対時刻または相対時刻のいずれかで前記出発時刻を予測する
前記（３）に記載の情報処理装置。
（５）
前記過去履歴DBは、過去の移動履歴を前記検索用データとして記憶し、
前記類似検索部は、前記適合度として、前記過去の移動履歴と前記直近の移動履歴との距離を用いて、前記直近の移動履歴と類似するものを検索する
前記（１）ないし（４）のいずれかに記載の情報処理装置。
（６）
前記過去履歴DBは、過去の移動履歴を確率遷移モデルで学習したときのパラメータを前記検索用データとして記憶し、
前記類似検索部は、前記適合度として、前記直近の移動履歴に対して算出される前記確率遷移モデルの尤度を用いて、前記直近の移動履歴と類似するものを検索する
前記（１）ないし（５）のいずれかに記載の情報処理装置。
（７）
検索用データを記憶する過去履歴DBを備える情報処理装置が、
時系列の位置データでなる直近の移動履歴を取得し、
前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索し、
検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定し、
判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御する
ステップを含む情報処理方法。
（８）
コンピュータを、
過去履歴DBに記憶されている検索用データのなかから、位置センサ部で取得された、時系列の位置データでなる直近の移動履歴と類似する過去の経路を検索する類似検索部と、
前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、
前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部
として機能させるためのプログラム。
【符号の説明】
【０３１１】
１ 予測装置， １１ 位置センサ部， １３ 過去履歴DB， １４ 類似検索部， １５ 適合判定部， １６ 予測経路抽出部， １７ 出発時刻予測部， １８ 予測値算出部， １９ センサ制御部， ２０ DB修正部
【特許請求の範囲】
【請求項１】
時系列の位置データでなる直近の移動履歴を取得する位置センサ部と、
検索用データを記憶する過去履歴DBと、
前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索する類似検索部と、
前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、
前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部と
を備える情報処理装置。
【請求項２】
前記センサ制御部は、前記適合度が前記所定の閾値以上である場合に、前記位置データの取得間隔が、前記所定の閾値未満である場合よりも長くなるように制御する
請求項１に記載の情報処理装置。
【請求項３】
現在の位置を離れる時刻である出発時刻を予測する出発時刻予測部をさらに備え、
前記センサ制御部は、前記適合度が前記所定の閾値以上であり、かつ、前記出発時刻予測部で予測された出発予測時刻が所定時間より後である場合に、前記位置データの取得間隔が、前記所定の閾値未満である場合よりも長くなるように制御する
請求項１に記載の情報処理装置。
【請求項４】
前記出発時刻予測部は、絶対時刻または相対時刻のいずれかで前記出発時刻を予測する
請求項３に記載の情報処理装置。
【請求項５】
前記過去履歴DBは、過去の移動履歴を前記検索用データとして記憶し、
前記類似検索部は、前記適合度として、前記過去の移動履歴と前記直近の移動履歴との距離を用いて、前記直近の移動履歴と類似するものを検索する
請求項１に記載の情報処理装置。
【請求項６】
前記過去履歴DBは、過去の移動履歴を確率遷移モデルで学習したときのパラメータを前記検索用データとして記憶し、
前記類似検索部は、前記適合度として、前記直近の移動履歴に対して算出される前記確率遷移モデルの尤度を用いて、前記直近の移動履歴と類似するものを検索する
請求項１に記載の情報処理装置。
【請求項７】
検索用データを記憶する過去履歴DBを備える情報処理装置が、
時系列の位置データでなる直近の移動履歴を取得し、
前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索し、
検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定し、
判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御する
ステップを含む情報処理方法。
【請求項８】
コンピュータを、
過去履歴DBに記憶されている検索用データのなかから、位置センサ部で取得された、時系列の位置データでなる直近の移動履歴と類似する過去の経路を検索する類似検索部と、
前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、
前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部
として機能させるためのプログラム。
【請求項１】
時系列の位置データでなる直近の移動履歴を取得する位置センサ部と、
検索用データを記憶する過去履歴DBと、
前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索する類似検索部と、
前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、
前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部と
を備える情報処理装置。
【請求項２】
前記センサ制御部は、前記適合度が前記所定の閾値以上である場合に、前記位置データの取得間隔が、前記所定の閾値未満である場合よりも長くなるように制御する
請求項１に記載の情報処理装置。
【請求項３】
現在の位置を離れる時刻である出発時刻を予測する出発時刻予測部をさらに備え、
前記センサ制御部は、前記適合度が前記所定の閾値以上であり、かつ、前記出発時刻予測部で予測された出発予測時刻が所定時間より後である場合に、前記位置データの取得間隔が、前記所定の閾値未満である場合よりも長くなるように制御する
請求項１に記載の情報処理装置。
【請求項４】
前記出発時刻予測部は、絶対時刻または相対時刻のいずれかで前記出発時刻を予測する
請求項３に記載の情報処理装置。
【請求項５】
前記過去履歴DBは、過去の移動履歴を前記検索用データとして記憶し、
前記類似検索部は、前記適合度として、前記過去の移動履歴と前記直近の移動履歴との距離を用いて、前記直近の移動履歴と類似するものを検索する
請求項１に記載の情報処理装置。
【請求項６】
前記過去履歴DBは、過去の移動履歴を確率遷移モデルで学習したときのパラメータを前記検索用データとして記憶し、
前記類似検索部は、前記適合度として、前記直近の移動履歴に対して算出される前記確率遷移モデルの尤度を用いて、前記直近の移動履歴と類似するものを検索する
請求項１に記載の情報処理装置。
【請求項７】
検索用データを記憶する過去履歴DBを備える情報処理装置が、
時系列の位置データでなる直近の移動履歴を取得し、
前記検索用データのなかから、前記直近の移動履歴と類似する過去の経路を検索し、
検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定し、
判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御する
ステップを含む情報処理方法。
【請求項８】
コンピュータを、
過去履歴DBに記憶されている検索用データのなかから、位置センサ部で取得された、時系列の位置データでなる直近の移動履歴と類似する過去の経路を検索する類似検索部と、
前記類似検索部で検索された前記過去の経路と、前記直近の移動履歴との適合度が所定の閾値以上であるかを判定する適合判定部と、
前記適合判定部の判定結果に応じて、前記位置センサ部の前記位置データの取得間隔を制御するセンサ制御部
として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【公開番号】特開２０１２−２０２７９６（Ｐ２０１２−２０２７９６Ａ）
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【出願番号】特願２０１１−６７１３７（Ｐ２０１１−６７１３７）
【出願日】平成２３年３月２５日（２０１１．３．２５）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【出願日】平成２３年３月２５日（２０１１．３．２５）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]