(57)【特許請求の範囲】
【請求項１】
経路推定装置であって、
複数のリンクを含む道情報を記憶する記憶手段と、
当該経路推定装置の移動方向を推定する移動方向推定手段と、
当該経路推定装置の移動元の位置を基準として、移動先の候補点を複数生成する生成手段と、
前記記憶手段に記憶されている道情報に含まれている前記複数のリンクの中から、前記生成手段により生成された複数の移動先の候補点と関連付けられる１以上の候補リンクを特定する候補リンク特定手段と、
前記１以上の候補リンクと、前記移動方向とに基づいて、当該経路推定装置が移動しているリンクを含む１以上のリンクが接続されてなる経路を推定する経路推定手段と、
前記１以上の候補リンクの各端点の中から、前記経路推定手段により推定される経路の端点を構成する経路端点を抽出する経路端点抽出手段と、を備え、
前記経路端点抽出手段は、前記１以上の候補リンクの各端点の中から、複数の候補リンクと接続されていない何れかの端点を前記経路端点として抽出する
ことを特徴とする経路推定装置。
【請求項２】
前記経路端点抽出手段は、更に、
前記１以上の候補リンクの各端点の中から、当該１以上の候補リンクのうちの一の候補リンクの前記移動方向側の端点であり、且つ、当該移動方向側の端点に接続されている前記一の候補リンク以外の候補リンクが当該移動方向側の端点から見て前記移動方向側に延在していない端点、及び、前記一の候補リンクの前記移動方向とは反対側の端点であり、且つ、当該移動方向とは反対側の端点に接続されている前記一の候補リンク以外の全ての候補リンクが移動方向側に延在している端点のうち、少なくとも一方の端点を前記経路端点として抽出することを特徴とする請求項１に記載の経路推定装置。
【請求項３】
前記１以上の候補リンクのうちの前記経路端点抽出手段により抽出された前記経路端点を含む含経路端点候補リンクの中から、前記経路推定手段により推定される経路を構成する経路構成リンクを抽出する経路構成リンク抽出手段を更に備え、
前記経路構成リンク抽出手段は、
前記含経路端点候補リンクのうちの一の含経路端点候補リンクであって、当該一の含経路端点候補リンクの両方の端点のうち、前記経路端点とは反対側の端点が、当該経路端点から見て前記移動方向側にある前記一の含経路端点候補リンクを、前記経路構成リンクとして抽出することを特徴とする請求項１又は２に記載の経路推定装置。
【請求項４】
前記経路端点抽出手段により抽出された前記経路端点を含む含経路端点候補リンクの中から、当該含経路端点候補リンクの前記経路端点とは反対側の端点が、当該含経路端点候補リンクの前記経路端点から見て前記移動方向側にあり、且つ、当該反対側の端点が、前記経路端点抽出手段により抽出されている他の前記経路端点でない、前記含経路端点候補リンクを第１リンクとして特定する第１特定手段と、
前記第１特定手段により特定される前記第１リンクの端点のうち前記経路端点とは反対側の端点を接続端点として特定する接続端点特定手段と、
前記１以上の候補リンクのうち、前記接続端点特定手段により特定された前記接続端点を端点とし、且つ、前記第１リンク以外の前記候補リンクを第２リンクとして特定する第２特定手段と、
を更に備え、
前記経路構成リンク抽出手段は、
前記第２特定手段により特定された前記第２リンクのうち、当該第２リンクの前記接続端点とは反対側の端点が、当該第２リンクの前記接続端点から見て前記移動方向側にある前記第２リンクを前記経路構成リンクとして抽出することを特徴とする請求項３に記載の経路推定装置。
【請求項５】
前記第１特定手段は、前記第２特定手段により特定された前記第２リンクのうち、当該第２リンクの前記接続端点とは反対側の端点が、前記経路端点抽出手段により抽出されている前記経路端点でない前記第２リンクを前記第１リンクとして再度特定し、
前記接続端点特定手段は、前記第１特定手段により再度特定された前記第１リンクの前記接続端点とは反対側の端点を接続端点として再度特定することを特徴とする請求項４に記載の経路推定装置。
【請求項６】
前記生成手段により生成された複数の移動先の候補点のうち、前記経路推定手段により推定された経路を構成するリンクと関連する候補点の尤度をそれぞれ算出する算出手段と、
前記算出手段により算出された移動先の候補点の尤度に基づいて、前記経路推定手段により推定された経路上での当該経路推定装置の存する位置を推定する位置推定手段と、
を更に備えたことを特徴とする請求項１〜５の何れか一項に記載の経路推定装置。
【請求項７】
複数のリンクを含む道情報を記憶する記憶手段を備える経路推定装置を用いた経路推定方法であって、
当該経路推定装置の移動方向を推定する処理と、
当該経路推定装置の移動元の位置を基準として、移動先の候補点を複数生成する処理と、
前記記憶手段に記憶されている道情報に含まれている前記複数のリンクの中から、生成された複数の移動先の候補点と関連付けられる１以上の候補リンクを特定する処理と、
前記１以上の候補リンクと、前記移動方向とに基づいて、当該経路推定装置が移動しているリンクを含む１以上のリンクが接続されてなる経路を推定する処理と、
前記１以上の候補リンクの各端点の中から、前記推定される経路の端点を構成する経路端点を抽出する処理と、を含み、
前記経路端点を抽出する処理は、前記１以上の候補リンクの各端点の中から、複数の候補リンクと接続されていない何れかの端点を前記経路端点として抽出する
ことを特徴とする経路推定方法。
【請求項８】
複数のリンクを含む道情報を記憶する記憶手段を備える経路推定装置のコンピュータを、
当該経路推定装置の移動方向を推定する移動方向推定手段、
当該経路推定装置の移動元の位置を基準として、移動先の候補点を複数生成する生成手段、
前記記憶手段に記憶されている道情報に含まれている前記複数のリンクの中から、前記生成手段により生成された複数の移動先の候補点と関連付けられる１以上の候補リンクを特定する候補リンク特定手段、
前記１以上の候補リンクと、前記移動方向とに基づいて、当該経路推定装置が移動しているリンクを含む１以上のリンクが接続されてなる経路を推定する経路推定手段、
前記１以上の候補リンクの各端点の中から、前記経路推定手段により推定される経路の端点を構成する経路端点を抽出する経路端点抽出手段、として機能させ、
前記経路端点抽出手段は、前記１以上の候補リンクの各端点の中から、複数の候補リンクと接続されていない何れかの端点を前記経路端点として抽出する
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路推定装置、経路推定方法及びプログラムに関する。
【背景技術】
【０００２】
従来、移動中に、所定の測位手段を利用して位置を測定し、測位された位置と移動方向を算出して、候補リンクと逐次照合する技術が知られている（例えば、特許文献１参照）。また、ある時刻の推定位置の確率密度分布を近似表現するためのパーティクルフィルタ（粒子フィルタ）を用いて、位置を照合する手法も知られている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−９４４３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、パーティクルフィルタでは、候補点となる各粒子の尤度分布から代表値（例えば、重心）を現在位置として推定するようになっているが、例えば、交差点など経路が複雑な状況で、経路の構造を考慮せずに代表値が選択されると、位置の照合を適正に行うことができなくなるといった問題がある。
【０００５】
そこで、本発明の課題は、経路の推定を適正に行うことができる経路推定装置、経路推定方法及びプログラムを提供することである。
【課題を解決するための手段】
【０００６】
上記課題を解決するため、本発明に係る経路推定装置は、
複数のリンクを含む道情報を記憶する記憶手段と、
当該経路推定装置の移動方向を推定する移動方向推定手段と、
当該経路推定装置の移動元の位置を基準として、移動先の候補点を複数生成する生成手段と、
前記記憶手段に記憶されている道情報に含まれている前記複数のリンクの中から、前記生成手段により生成された複数の移動先の候補点と関連付けられる１以上の候補リンクを特定する候補リンク特定手段と、
前記１以上の候補リンクと、前記移動方向とに基づいて、当該経路推定装置が移動しているリンクを含む１以上のリンクが接続されてなる経路を推定する経路推定手段と、
前記１以上の候補リンクの各端点の中から、前記経路推定手段により推定される経路の端点を構成する経路端点を抽出する経路端点抽出手段と、を備え、
前記経路端点抽出手段は、前記１以上の候補リンクの各端点の中から、複数の候補リンクと接続されていない何れかの端点を前記経路端点として抽出する
ことを特徴としている。
【発明の効果】
【０００７】
本発明によれば、経路の推定を適正に行うことができる。
【図面の簡単な説明】
【０００８】
【図１】本発明を適用した一実施形態の経路推定装置の概略構成を示すブロック図である。
【図２】図１の経路推定装置による位置照合処理に係る動作の一例を示すフローチャートである。
【図３】図２の位置照合処理における候補リンク特定処理に係る動作の一例を示すフローチャートである。
【図４】図３の候補リンク特定処理を説明するための図である。
【図５】図２の位置照合処理における経路端点抽出処理に係る動作の一例を示すフローチャートである。
【図６】図５の経路端点抽出処理を説明するための図である。
【図７】図２の位置照合処理における経路構成リンク抽出処理に係る動作の一例を示すフローチャートである。
【図８】図７の経路構成リンク抽出処理におけるループ処理に係る動作の一例を示すフローチャートである。
【図９】図７の経路構成リンク抽出処理を説明するための図である。
【図１０】図７の経路構成リンク抽出処理を説明するための図である。
【図１１】図２の位置照合処理における位置推定処理に係る動作の一例を示すフローチャートである。
【図１２】図１１の位置推定処理を説明するための図である。
【発明を実施するための形態】
【０００９】
以下に、本発明について、図面を用いて具体的な態様を説明する。ただし、発明の範囲は、図示例に限定されない。
【００１０】
図１は、本発明を適用した一実施形態の経路推定装置１００の概略構成を示すブロック図である。
図１に示すように、経路推定装置１００は、中央制御部１と、メモリ２と、第１測位処理部３と、センサ部４と、第２測位処理部５と、記憶部６と、位置照合部７と、表示部８と、操作入力部９等を備えている。
また、中央制御部１、第１測位処理部３、センサ部４、第２測位処理部５、位置照合部７、記憶部６、位置照合部７及び表示部８は、バスライン１０を介して接続されている。
【００１１】
中央制御部１は、経路推定装置１００の各部を統括的に制御する。
具体的には、中央制御部１は、経路推定装置１００の各部を制御するＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）を備え（何れも図示略）、経路推定装置１００用の各種処理プログラム（図示略）に従って各種の制御動作を行う。
【００１２】
メモリ２は、例えば、ＤＲＡＭ（Dynamic Random Access Memory）等により構成され、中央制御部１の他、当該経路推定装置１００の各部によって処理されるデータ等を一時的に記憶する。
【００１３】
また、メモリ２は、移動履歴データ２ａを記憶している。
移動履歴データ２ａは、位置照合処理（後述）によって取得された当該経路推定装置１００の一連の位置データが順次登録されるものである。すなわち、位置照合処理において、ＧＰＳ測位や自律航法測位等により測定された各地点の位置データが、位置照合部７により地図データベース６ａの道上で照合されることで移動履歴データ２ａが形成される。
【００１４】
第１測位処理部３は、例えば、ＧＰＳ（Global Positioning System）衛星等の測位衛星Ｓから送信された信号を受信して、当該経路推定装置１００の存する現在位置を測位する（ＧＰＳ測位）。
すなわち、第１測位処理部３は、例えば、地球低軌道に打ち上げられた複数の測位衛星Ｓから送信される信号（例えば、Ｃ／Ａ（Coarse and Acquisitions）コードやＰ（Precise）コード等の測位符号、アルマナック情報（概略軌道情報）やエフェメリス情報（詳細軌道情報）等の航法メッセージなど）を所定のタイミングで受信アンテナ３ａにより受信する。
そして、第１測位処理部３は、受信アンテナ３ａにより受信された信号に基づいて、例えば、３次元測位モードで経路推定装置１００の３次元の現在位置（緯度、経度、高度）を測定する測位処理を行う。具体的には、第１測位処理部３は、受信アンテナ３ａにより受信された信号に含まれる航法メッセージ（例えば、エフェメリス情報等）に基づいて所定の演算を行って各測位衛星Ｓの位置を算出する。例えば、３次元測位モードの場合、第１測位処理部３は、４つ以上の測位衛星Ｓの各々に対応する擬似距離情報を算出した後、各測位衛星Ｓの位置に基づいて所定の演算を行うことで、当該経路推定装置１００の存する現在位置の３次元の座標（ｘ、ｙ、ｚ）や経路推定装置１００の時計の誤差等を算出する。
なお、第１測位処理部３により生成された経路推定装置１００の存する現在位置の位置データは、メモリ２に出力されて、当該メモリ２に一時的に記憶されても良い。
【００１５】
センサ部４は、自律航法用センサとして、３軸地磁気センサ４ａ、３軸加速度センサ４ｂ及び気圧センサ４ｃを備えている。
【００１６】
３軸地磁気センサ４ａは、互いに直交する３軸方向の地磁気の大きさをそれぞれ検出する。そして、３軸地磁気センサ４ａは、検出された各軸の検出信号を第２測位処理部５に出力する。
３軸加速度センサ４ｂは、自律航法用センサであり、互いに直交する３軸方向の加速度をそれぞれ検出する。そして、３軸加速度センサ４ｂは、検出された各軸の検出信号を所定の周波数でサンプリングして、第２測位処理部５に出力する。
気圧センサ４ｃは、高低差を求めるために気圧を検出するセンサである。また、気圧センサ４ｃは、検出された気圧の検出信号を第２測位処理部５に出力する。
【００１７】
第２測位処理部５は、３軸地磁気センサ４ａ、３軸加速度センサ４ｂ及び気圧センサ４ｃ等により検出された検出データに基づいて、自律航法の測位演算を連続的に行う（自律航法測位）。
すなわち、第２測位処理部５は、例えば、所定のサンプリング周期で３軸地磁気センサ４ａ及び３軸加速度センサ４ｂにより検出された検出データを取得して、これらの検出データから経路推定装置１００の移動方向及び移動量を算出していく。
【００１８】
また、第２測位処理部５は、移動方向推定部５ａを具備している。
移動方向推定部（移動方向推定手段）５ａは、当該経路推定装置１００の存する位置の変化方向に基づいて、移動方向を推定する。具体的には、移動方向推定部５ａは、例えば、３軸地磁気センサ４ａの出力に現れる特有の出力変動パターンを抽出し、基準時点における当該経路推定装置１００の存する位置に対して単位時間経過後における当該経路推定装置１００の存する位置が変化した方向を変化方向ベクトルとして検出する。そして、移動方向推定部５ａは、所定時間範囲（例えば、５秒間等）内に検出された所定数（例えば、５つ）の変化方向を統合することで、経路推定装置１００の移動方向を推定する。例えば、時点ｔにおける経路推定装置１００の移動方向を推定する場合、移動方向推定部５ａは、時点ｔを基準とする所定時間範囲内に検出された所定数の変化方向ベクトルの各単位ベクトルを算出し、算出された所定数の単位ベクトルの合成ベクトル（単位ベクトル）を時点ｔにおける経路推定装置１００の移動方向として推定する。
また、移動方向推定部５ａにより推定された経路推定装置１００の移動方向は、図４等において矢印を用いて表されている。
なお、上記した移動方向の推定手法は、一例であってこれに限られるものではなく、適宜任意に変更可能であり、例えば、ＧＰＳ測位の結果を利用しても良い。また、時間の計測には、図示しない計時部を用いても良い。
【００１９】
記憶部６は、例えば、不揮発性メモリなどにより構成され、地図データベース６ａ等が記憶されている。
【００２０】
地図データベース６ａは、例えば、所定範囲内の地図を表示部８に表示するための地図データが位置座標と対応付けて記憶されている。すなわち、地図データベース６ａは、都道府県や市町村等の行政区画、番地等の住所情報や、建物、施設、店舗、公園、鉄道に関する情報、地形情報、道情報等を表す地図データと、緯度、経度、高度等の座標情報とが対応付けられている。
地図データの道情報は、ネットワーク情報を構成し、具体的には、直線道路を示すリンク（詳細後述）の情報と、リンクどうしのつなぎ目を示すノードの情報等を主とするデータ構造をなしている。リンクの情報には、当該リンクの長さ（実際の距離）、接続されるノード、方位、勾配、道幅等の情報が含まれている。ノードの情報には、緯度経度情報、接続されるリンク等の情報が含まれている。
なお、上記した地図データベース６ａのデータ構成は、一例であってこれに限られるものではなく、当該地図データベース６ａに記憶される情報の内容等は適宜任意に変更可能である。
このように、記憶部６は、記憶手段として、複数のリンクを含む道情報を記憶している。
【００２１】
位置照合部７は、経路推定装置１００の存する現在位置を地図データベース６ａの道上で照合する。具体的には、位置照合部７は、候補点生成部７ａと、候補リンク特定部７ｂと、経路端点抽出部７ｃと、第１リンク特定部７ｄと、接続端点特定部７ｅと、第２リンク特定部７ｆと、構成リンク抽出部７ｇと、経路推定部７ｈと、尤度算出部７ｉと、位置推定部７ｊとを具備している。
なお、位置照合部７の各部は、例えば、所定のロジック回路から構成されているが、当該構成は一例であってこれに限られるものではない。
【００２２】
候補点生成部７ａは、移動先の候補点を複数生成する。
すなわち、候補点生成部（生成手段）７ａは、当該経路推定装置１００の移動元となる位置を基準として、移動先の候補点を複数生成する。具体的には、候補点生成部７ａは、例えば、粒子（候補点）の運動モデルとして、センサ部４からの出力信号に基づいて算出される移動情報（例えば、移動方向推定部５ａにより推定される移動方向や現在時刻から所定時間範囲内の移動量等）を用い、粒子の尤度に作用する観測モデルとして、地図データベース６ａや第１測位処理部３による測位結果を用いるパーティクルフィルタにより、地図データの道情報に含まれている少なくとも一のリンクにより形成される空間に対して、現在位置からの移動先の候補点となる粒子（パーティクル；図４中、白丸で表す）を複数分布させる（図４参照）。
なお、図４にあっては、リンクＡ〜Ｅのうち、後述する候補リンクとして特定されるリンクＡ〜Ｄを実線で表し、候補リンクとして特定されないリンクＥを破線で表している。また、各リンクの端点（ノード）を黒丸で表しているが、図４以降の図でも同様となっている。
【００２３】
候補リンク特定部７ｂは、移動先の候補点と関連付けられる１以上の候補リンクを特定する。
すなわち、候補リンク特定部（候補リンク特定手段）７ｂは、記憶部６に記憶されている道情報に含まれている複数のリンクの中から、候補点生成部７ａにより生成された複数の移動先の候補点と関連付けられる１以上の候補リンクを特定する。
具体的には、候補リンク特定部７ｂは、候補リンク特定処理（図３参照；詳細後述）を行って、候補点生成部７ａにより移動先の候補点として分布された複数の粒子の各々に対して最も近距離のリンクや、所定の距離範囲内のリンクを、移動先の候補点と関連付けられる候補リンクとして特定する（図４参照）。例えば、図４に示すように、リンクＡ〜Ｅのうち、リンクＡ〜Ｄが候補リンクとして特定され、リンクＥについては、その近傍に粒子が存在しないため候補リンクとしては特定されない。
【００２４】
経路端点抽出部７ｃは、候補リンクの端点の中から、経路端点を抽出する。
すなわち、経路端点抽出部（経路端点抽出手段）７ｃは、候補リンク特定部７ｂにより特定された１以上の候補リンクの各端点の中から、後述する経路推定部７ｈにより推定される複数のリンク（経路構成リンク；後述）が接続されてなる経路の端点を構成する経路端点を抽出する。
具体的には、経路端点抽出部７ｃは、経路端点抽出処理（図５参照；詳細後述）を行って、候補リンク特定部７ｂにより特定された複数の候補リンクの両方の端点（一方の端点から見て移動方向側の端点及び他方の端点から見て移動方向とは反対側の端点）の中で、他の候補リンクと接続されていない何れかの端点（例えば、リンクＢの端点ｂ１やリンクＣの端点ｃ１等；図６（ａ）参照、リンクＡの端点ａ１等；図６（ｃ）参照）を経路端点として抽出する。言い換えれば、経路端点抽出部７ｃは、経路端点抽出処理を行って、候補リンク特定部７ｂにより特定された複数の候補リンクの両方の端点のうち、複数の候補リンクと接続されていない何れかの端点を経路端点として抽出する。
また、経路端点抽出部７ｃは、複数の候補リンクの端点の中で、移動方向推定部５ａにより推定された経路推定装置１００の移動方向側の端点であり、且つ、当該端点に接続されている他の候補リンクが移動方向側に延在していない端点（例えば、リンクＦの端点ｆ１等；図６（ｂ）参照）を経路端点として抽出する。また、経路端点抽出部７ｃは、複数の候補リンクの端点の中で、推定された経路推定装置１００の移動方向とは反対側の端点であり、且つ、当該端点に接続されている全ての他の候補リンクが移動方向側に延在している端点（例えば、リンクＧの端点ｇ１等；図６（ｄ）参照）を経路端点として抽出する。言い換えれば、経路端点抽出部７ｃは、更に、複数の候補リンクの各端点の中から、該複数の候補リンクのうちの一の候補リンクの移動方向側の端点であり、且つ、該移動方向側の端点に接続されている一の候補リンク以外の候補リンクが該移動方向側の端点から見て移動方向側に延在していない端点、及び、該一の候補リンクの移動方向とは反対側の端点であり、且つ、該移動方向とは反対側の端点に接続されている一の候補リンク以外の全ての候補リンクが移動方向側に延在している端点のうち、少なくとも一方の端点を経路端点として抽出する。
【００２５】
なお、経路推定装置１００の移動方向側にあるか否かは、例えば、推定された移動方向に延在する直線に対して所定の角度範囲（例えば、９０°等）内にあるか否かに応じて判断されるものとする。
また、図６（ａ）及び図６（ｃ）は、図４にて候補リンクとして特定されたリンクＡ〜Ｄに対応し、図６（ｂ）及び図６（ｄ）には、リンクＡ〜Ｄとは異なる候補リンクの一例を表している。また、経路端点が抽出された候補リンクを実線で表すとともに経路端点を白丸で表し、経路端点が抽出されていない候補リンクを二点鎖線で表している。
【００２６】
第１リンク特定部７ｄは、候補リンクの中から、第１リンクを特定する。
すなわち、第１リンク特定部（第１特定手段）７ｄは、経路端点抽出部７ｃにより抽出された経路端点を構成する候補リンク（含経路端点候補リンク）の中で、経路端点とは反対側の端点が、移動方向推定部５ａにより推定された経路推定装置１００の移動方向側にあり、且つ、経路端点抽出部７ｃにより抽出されている他の経路端点でない候補リンク（例えば、リンクＡ；図９（ａ）参照）を第１リンクとして特定する。
なお、図９（ａ）にあっては、第１リンクとして特定されたリンクＡを実線で表すとともに経路端点を白丸で表し、第１リンク以外の候補リンクとしてのリンクＢ〜Ｄを二点鎖線で表している。
【００２７】
さらに、第１リンク特定部７ｄは、後述する第２リンク特定部７ｆにより特定された第２リンクのうち、当該第２リンクの接続端点とは反対側の端点が、推定された経路推定装置１００の移動方向側にあり、且つ、経路端点抽出部７ｃにより抽出されている経路端点でない第２リンク（例えば、リンクＣ；図１０（ｂ）参照）を第１リンクとして再度特定する。
なお、図１０（ｂ）にあっては、第１リンクとしてのリンクＡ、リンクＣを破線で表すとともに経路端点を白丸で表し、経路構成リンク（後述）として特定されるリンクＢ、Ｅを実線で表し、経路構成リンクとして特定されないリンクＤを二点鎖線で表している。
【００２８】
接続端点特定部７ｅは、候補リンクどうしが接続している接続端点を特定する。
すなわち、接続端点特定部（接続端点特定手段）７ｅは、第１リンク特定部７ｄにより特定される第１リンクの経路端点とは反対側の端点を接続端点として特定する（図９（ａ）等参照）。具体的には、接続端点特定部７ｅは、経路端点とは反対側の端点であって、移動方向推定部５ａにより推定された経路推定装置１００の移動方向側にあり、且つ、経路端点抽出部７ｃにより抽出されている他の経路端点でない端点を接続端点として特定する。
さらに、接続端点特定部７ｅは、第１リンク特定部７ｄにより第１リンクが再度特定されると、当該第１リンクの接続端点とは反対側の端点（例えば、リンクＣの端点ｃ１；図１０（ｂ）参照）を接続端点として再度特定する。
【００２９】
第２リンク特定部７ｆは、候補リンクの中から、第２リンクを特定する。
第２リンク特定部（第２特定手段）７ｆは、１以上の候補リンクのうち、接続端点特定部７ｅにより特定された接続端点を経路端点とは反対側の端点とし、且つ、第１リンク以外の候補リンク（例えば、リンクＢ〜Ｄ；図９（ｂ）参照）を第２リンクとして特定する。
なお、図９（ｂ）にあっては、第２リンクとして特定されたリンクＢ〜Ｄを実線で表し、第１リンクとしてのリンクＡを二点鎖線で表すとともに経路端点を白丸で表している。
【００３０】
構成リンク抽出部７ｇは、候補リンクの中から、経路構成リンクを抽出する。
すなわち、構成リンク抽出部（経路構成リンク抽出手段）７ｇは、１以上の候補リンクのうちの経路端点抽出部７ｃにより抽出された経路端点を含む候補リンク（含経路端点候補リンク）の中から、後述する経路推定部７ｈにより推定される経路を構成する経路構成リンクを抽出する。具体的には、構成リンク抽出部７ｇは、経路構成リンク抽出処理（図７参照；詳細後述）を行って、経路端点抽出部７ｃにより抽出された経路端点を構成する候補リンク（含経路端点候補リンク）の中で、両方の端点のうちの経路端点とは反対側の端点が、当該経路端点から見て経路推定装置１００の移動方向側にある候補リンク（例えば、リンクＡ；図９（ａ）参照）を経路構成リンクとして抽出する。
また、構成リンク抽出部７ｇは、第２リンク特定部７ｆにより特定された第２リンクのうち、当該第２リンクの接続端点とは反対側の端点が、当該第２リンクの接続端点から見て経路推定装置１００の移動方向側にある第２リンク（例えば、リンクＢやリンクＣ；図１０（ａ）参照、リンクＥ；図１０（ｂ）参照）を経路構成リンクとして抽出する。
なお、図１０（ａ）にあっては、第１リンクとしてのリンクＡを破線で表すとともに経路端点を白丸で表し、経路構成リンクとして特定されたリンクＢ、Ｃを実線で表し、経路構成リンクとして特定されないリンクＤを二点鎖線で表している。
【００３１】
経路推定部７ｈは、当該経路推定装置１００が移動しているリンクを含む１以上のリンクが接続されてなる経路を推定する。
すなわち、経路推定部（経路推定手段）７ｈは、候補リンク特定部７ｂによりそれぞれ特定された候補リンクと、移動方向推定部５ａにより推定された経路推定装置１００の移動方向とに基づいて、当該経路推定装置１００が移動しているリンクを含む１以上のリンクが接続されてなる経路を推定する。具体的には、経路推定部７ｈは、構成リンク抽出部７ｇにより抽出された経路構成リンクが接続されてなる経路（例えば、リンクＡ＋リンクＢの経路１やリンクＡ＋リンクＣの経路２等；図１２（ａ）及び図１２（ｂ）参照）を推定する。
なお、図１２（ａ）にあっては、経路１を構成する経路構成リンクとしてのリンクＡ、Ｂを実線で表し、経路１を構成しないリンクＣを二点鎖線で表している。また、図１２（ｂ）にあっては、経路２を構成する経路構成リンクとしてのリンクＡ、Ｃを実線で表し、経路２を構成しないリンクＢを二点鎖線で表している。
【００３２】
尤度算出部７ｉは、経路構成リンクに対応する複数の粒子の尤度を算出する。
すなわち、尤度算出部（算出手段）７ｉは、候補点生成部７ａにより移動先の候補点として生成された複数の粒子のうち、経路推定部７ｈにより推定された経路を構成する経路構成リンクと関連する粒子の尤度をそれぞれ算出する。具体的には、尤度算出部７ｉは、推定された経路（例えば、経路１、２）毎に、推定された経路構成リンク（例えば、経路１の場合、リンクＡやリンクＢ等）と関連する粒子（例えば、経路構成リンクまで所定の距離範囲内の粒子）を特定する（図１２（ａ）及び図１２（ｂ）参照）。その後、尤度算出部７ｉは、経路構成リンクの延在方向と移動方向とのなす角度θ、経路構成リンクと粒子との距離Dist、一定距離未満の場合のクリップ用計数Cwidth等に基づいて、下記式（１）に従って粒子の尤度Siを算出する。
尤度＝cosθ/max(|Dist|,Cwidth)  …式（１）
【００３３】
なお、上記した粒子の尤度Siを計算する手法は、一例であってこれに限られるものではなく、適宜任意に変更可能である。また、図１２（ａ）及び図１２（ｂ）にあっては、各経路を構成する経路構成リンクと関連する粒子をドット付きの丸で表し、それ以外の粒子を白丸で表している。
【００３４】
位置推定部７ｊは、経路上での当該経路推定装置１００の存する位置を推定する。
すなわち、位置推定部（位置推定手段）７ｊは、尤度算出部７ｉにより算出された複数の移動先の候補点としての粒子の尤度に基づいて、経路推定部７ｈにより推定された経路上での当該経路推定装置１００の存する位置を推定する。具体的には、位置推定部７ｊは、位置推定処理（図１１参照；詳細後述）を行って、推定された経路（例えば、経路１、２）毎に、尤度算出部７ｉにより尤度Siが算出された複数の粒子について経路上で対応する位置を算出し、算出された位置Xiに尤度Siを重みとして乗算したものの総和Sum2を、算出された尤度Siの総和Sum1で除算した値を、経路上での当該経路推定装置１００の存する位置Ｐとして推定する（式（２）及び式（３）参照）。
Sum1＝Sum1＋Si  …式（２）
Sum2＝Sum2＋Xi・Si  …式（３）
【００３５】
なお、上記した経路上での当該経路推定装置１００の存する位置Ｐの推定手法は、一例であってこれに限られるものではなく、例えば、位置推定部７ｊは、各経路を構成する経路構成リンクと関連する粒子の尤度から、代表となる粒子を特定し、特定された粒子の経路上で対応する位置を当該経路推定装置１００の存する位置Ｐとして推定しても良い。
【００３６】
表示部８は、例えば、中央制御部１のＣＰＵの制御下にて各種情報を表示領域内に表示する。具体的には、表示部８は、図示しない表示制御部により生成された画像データを、例えば、液晶表示パネルや有機ＥＬ（Electro-Luminescence）表示パネル等の表示パネルの表示領域内に各種情報を表示する。
【００３７】
操作入力部９は、経路推定装置１００に対して各種指示を入力するためのものである。
具体的には、操作入力部９は、経路推定装置１００の電源のＯＮ／ＯＦＦに係る電源ボタン、モードや機能等の選択指示に係る上下左右のカーソルボタンや決定ボタン等の各種ボタン（何れも図示略）を備えている。
そして、ユーザにより各種ボタンが操作されると、操作入力部９は、操作されたボタンに応じた操作指示を中央制御部１に出力する。中央制御部１は、操作入力部９から出力され入力された操作指示に従って所定の動作を各部に実行させる。
【００３８】
なお、操作入力部９は、表示部８の表示パネルと一体となって設けられたタッチパネルを有していても良く、ユーザによるタッチパネルの所定操作に基づいて、当該所定操作に応じた操作指示を中央制御部１に出力しても良い。
【００３９】
＜位置照合処理＞
次に、本実施形態の経路推定装置１００による位置照合処理について、図２〜図１２を参照して説明する。
図２は、位置照合処理に係る動作の一例を示すフローチャートである。
なお、以下に説明する位置照合処理は、所定の時間間隔を空けて逐次行われる。また、移動方向推定部５ａにより経路推定装置１００の移動方向の推定が逐次行われているものとする。
【００４０】
図２に示すように、先ず、位置照合部７は、移動先の候補点と関連付けられる候補リンクを特定する候補リンク特定処理（図３参照）を行い（ステップＳ１）、次に、候補リンクの各端点の中から、経路端点を抽出する経路端点抽出処理（図５参照）を行って（ステップＳ２）、続けて、候補リンクの中から、経路構成リンクを抽出する経路構成リンク抽出処理（図７参照）を行う（ステップＳ３）。その後、位置照合部７は、推定された経路上での当該経路推定装置１００の存する位置を推定する位置推定処理（図１１参照）を行う（ステップＳ４）。
【００４１】
＜候補リンク特定処理＞
以下に、候補リンク特定処理について、図３及び図４を参照して説明する。
図３は、位置照合処理における候補リンク特定処理に係る動作の一例を示すフローチャートである。また、図４は、候補リンク特定処理を説明するための図であり、リンクＡ〜Ｅに対して粒子（白丸で表す）を分布させた状態を模式的に表している。
【００４２】
図３に示すように、先ず、候補点生成部７ａは、パーティクルフィルタにより、地図データの道情報に含まれている少なくとも一のリンクにより形成される空間に対して、現在位置からの移動先の候補点として粒子を複数分布させる（ステップＳ１１；図４参照）。
次に、候補リンク特定部７ｂは、候補点生成部７ａにより移動先の候補点として分布された全ての粒子を、例えば、メモリ２の粒子リスト（図示略）に追加する（ステップＳ１２）。
【００４３】
そして、候補リンク特定部７ｂは、粒子リストから何れか一の粒子を処理対象として選択し（ステップＳ１３）、選択された粒子の近傍の候補リンク（例えば、最も近距離のリンクや、所定の距離範囲内のリンク等）を探索する（ステップＳ１４）。
その後、候補リンク特定部７ｂは、探索された候補リンクが抽出済みであるか否かを判定する（ステップＳ１５）。なお、候補リンクが抽出済みであるか否かは、例えば、後述する抽出リンクリストに登録されているか否かに応じて判定される。
【００４４】
ステップＳ１５にて、候補リンクが抽出済みでないと判定されると（ステップＳ１５；ＮＯ）、候補リンク特定部７ｂは、探索された候補リンクを、例えば、メモリ２の抽出リンクリスト（図示略）に追加した後（ステップＳ１６）、ステップＳ１３にて処理対象として選択されている粒子を粒子リストから削除する（ステップＳ１７）。
一方、ステップＳ１５にて、候補リンクが抽出済みであると判定されると（ステップＳ１５；ＹＥＳ）、候補リンク特定部７ｂは、ステップＳ１６をスキップし、ステップＳ１７にて、同様に、処理対象として選択されている粒子を粒子リストから削除する。
【００４５】
その後、候補リンク特定部７ｂは、粒子リストに未選択の粒子が残っているか否かを判定する（ステップＳ１８）。
ここで、粒子リストに未選択の粒子が残っていると判定されると（ステップＳ１８；ＹＥＳ）、候補リンク特定部７ｂは、処理をステップＳ１３に戻し、粒子リストから未選択の何れか一の粒子を処理対象として選択し（ステップＳ１３）、それ以降の各処理を行う。
候補リンク特定部７ｂは、上記の各処理を、ステップＳ１８にて、粒子リストに未選択の粒子が残っていないと判定（ステップＳ１８；ＮＯ）されるまで繰り返し行うことで、例えば、リンクＡ〜Ｅのうち、実線で表すリンクＡ〜Ｄを候補リンクとして特定し、近傍に粒子が存在しない破線で表すリンクＥについては候補リンクとして特定しない（図４参照）。
【００４６】
一方、ステップＳ１８にて、粒子リストに未選択の粒子が残っていないと判定されると（ステップＳ１８；ＮＯ）、候補リンク特定部７ｂは、候補リンク特定処理を終了する。
【００４７】
＜経路端点抽出処理＞
以下に、経路端点抽出処理について、図５〜図６（ｄ）を参照して説明する。
図５は、位置照合処理における経路端点抽出処理に係る動作の一例を示すフローチャートである。また、図６（ａ）〜図６（ｄ）は、経路端点抽出処理を説明するための図であり、候補リンクの一例を模式的に表している。
【００４８】
図５に示すように、先ず、経路端点抽出部７ｃは、抽出リンクリストから何れか一の候補リンクを処理対象として選択する（ステップＳ２１）。
次に、経路端点抽出部７ｃは、選択された候補リンクの両端点のうち、移動方向推定部５ａにより推定された経路推定装置１００の移動方向側の端点を選択し（ステップＳ２２）、選択された端点が抽出済みの他の候補リンクと接続されているか否かを判定する（ステップＳ２３）。
【００４９】
ステップＳ２３にて、選択された端点が抽出済みの他の候補リンクと接続されていないと判定されると（ステップＳ２３；ＮＯ）、経路端点抽出部７ｃは、選択された端点が抽出済みであるか否かを判定する（ステップＳ２４）。なお、端点が抽出済みであるか否かは、例えば、後述する経路端点リストに登録されているか否かに応じて判定される。
ここで、端点が抽出済みでないと判定されると（ステップＳ２４；ＮＯ）、経路端点抽出部７ｃは、処理対象の端点（例えば、リンクＢの端点ｂ１やリンクＣの端点ｃ１等；図６（ａ）参照）を経路端点（図中、白丸で表す）として、例えば、メモリ２の経路端点リスト（図示略）に追加する（ステップＳ２５）。
【００５０】
一方、ステップＳ２３にて、選択された端点が抽出済みの他の候補リンクと接続されていると判定されると（ステップＳ２３；ＹＥＳ）、経路端点抽出部７ｃは、当該端点に接続されている他の候補リンクが経路推定装置１００の移動方向側に延在しているか否かを判定する（ステップＳ２６）。
ここで、他の候補リンクが経路推定装置１００の移動方向側に延在していないと判定されると（ステップＳ２６；ＮＯ）、経路端点抽出部７ｃは、処理をステップＳ２４に移行し、同様に、選択された端点が抽出済みであるか否かを判定する。
ステップＳ２４にて、端点が抽出済みでないと判定されると（ステップＳ２４；ＮＯ）、経路端点抽出部７ｃは、処理対象の端点（例えば、リンクＦの端点ｆ１等；図６（ｂ）参照）を経路端点として経路端点リストに追加する（ステップＳ２５）。
【００５１】
一方、ステップＳ２６にて、他の候補リンクが経路推定装置１００の移動方向側に延在していると判定されると（ステップＳ２６；ＹＥＳ）、経路端点抽出部７ｃは、選択された候補リンクの両端点のうち、経路推定装置１００の移動方向とは反対側の端点を選択する（ステップＳ２７）。また、ステップＳ２４にて、端点が抽出済みであると判定された場合や（ステップＳ２４；ＹＥＳ）、ステップＳ２５にて、処理対象の端点を経路端点リストに追加した後（ステップＳ２５）、経路端点抽出部７ｃは、処理をステップＳ２７に移行し、候補リンクの経路推定装置１００の移動方向とは反対側の端点を選択する。
その後、経路端点抽出部７ｃは、選択された端点が抽出済みの他の候補リンクと接続されているか否かを判定する（ステップＳ２８）。
【００５２】
ステップＳ２８にて、選択された端点が抽出済みの他の候補リンクと接続されていないと判定されると（ステップＳ２８；ＮＯ）、経路端点抽出部７ｃは、ステップＳ２４と同様に、選択された端点が抽出済みであるか否かを判定する（ステップＳ２９）。
ここで、端点が抽出済みでないと判定されると（ステップＳ２９；ＮＯ）、経路端点抽出部７ｃは、処理対象の端点（例えば、リンクＡの端点ａ１等；図６（ｃ）参照）を経路端点として経路端点リストに追加する（ステップＳ３０）。
【００５３】
一方、ステップＳ２８にて、選択された端点が抽出済みの他の候補リンクと接続されていると判定されると（ステップＳ２８；ＹＥＳ）、経路端点抽出部７ｃは、当該端点に接続されている全ての他の候補リンクが経路推定装置１００の移動方向側に延在しているか否かを判定する（ステップＳ３１）。
ここで、全ての他の候補リンクが経路推定装置１００の移動方向側に延在していると判定されると（ステップＳ３１；ＹＥＳ）、経路端点抽出部７ｃは、処理をステップＳ２９に移行し、同様に、選択された端点が抽出済みであるか否かを判定する。
ステップＳ２９にて、端点が抽出済みでないと判定されると（ステップＳ２９；ＮＯ）、経路端点抽出部７ｃは、処理対象の端点（例えば、リンクＧの端点ｇ１等；図６（ｄ）参照）を経路端点として経路端点リストに追加する（ステップＳ３０）。
【００５４】
一方、ステップＳ３１にて、全ての他の候補リンクが経路推定装置１００の移動方向側に延在していないと判定されると（ステップＳ３１；ＮＯ）、経路端点抽出部７ｃは、ステップＳ２１にて処理対象として選択されている候補リンクを抽出リンクリストから削除する（ステップＳ３２）。また、ステップＳ２９にて、端点が抽出済みであると判定された場合や（ステップＳ２９；ＹＥＳ）、ステップＳ３０にて、処理対象の端点を経路端点リストに追加した後（ステップＳ３０）、経路端点抽出部７ｃは、処理をステップＳ３２に移行し、処理対象として選択されている候補リンクを抽出リンクリストから削除する。
その後、経路端点抽出部７ｃは、抽出リンクリストに未選択の候補リンクが残っているか否かを判定する（ステップＳ３３）。
【００５５】
ステップＳ３３にて、抽出リンクリストに未選択の候補リンクが残っていると判定されると（ステップＳ３３；ＹＥＳ）、経路端点抽出部７ｃは、処理をステップＳ２１に戻し、抽出リンクリストから未選択の何れか一の候補リンクを処理対象として選択し（ステップＳ２１）、それ以降の各処理を行う。
経路端点抽出部７ｃは、上記の各処理を、ステップＳ３３にて、抽出リンクリストに未選択の候補リンクが残っていないと判定（ステップＳ３３；ＮＯ）されるまで繰り返し行う。
【００５６】
一方、ステップＳ３３にて、抽出リンクリストに未選択の候補リンクが残っていないと判定されると（ステップＳ３３；ＮＯ）、経路端点抽出部７ｃは、経路端点抽出処理を終了する。
【００５７】
＜経路構成リンク抽出処理＞
以下に、経路構成リンク抽出処理について、図７〜図１０（ｂ）を参照して説明する。
図７は、位置照合処理における経路構成リンク抽出処理に係る動作の一例を示すフローチャートである。また、図８は、経路構成リンク抽出処理におけるループ処理に係る動作の一例を示すフローチャートである。また、図９（ａ）〜図１０（ｂ）は、経路構成リンク抽出処理を説明するための図である。
【００５８】
図７に示すように、先ず、構成リンク抽出部７ｇは、経路端点リストから何れか一の経路端点を処理対象として選択し（ステップＳ４１）、選択された経路端点を端点とする全ての候補リンクを、例えば、メモリ２の第１リンクリスト（図示略）に追加する（ステップＳ４２）。
【００５９】
次に、構成リンク抽出部７ｇは、第１リンクリストから何れか一の候補リンクを処理対象として選択する（ステップＳ４３）。続けて、構成リンク抽出部７ｇは、例えば、メモリ２の経路リンクバッファをクリアした後（ステップＳ４４）、ステップＳ４１にて処理対象として選択された経路端点とは反対側の端点が、移動方向推定部５ａにより推定された経路推定装置１００の移動方向側にあるか否かを判定する（ステップＳ４５）。
ここで、経路端点とは反対側の端点が、経路推定装置１００の移動方向側にあると判定されると（ステップＳ４５；ＹＥＳ）、構成リンク抽出部７ｇは、ステップＳ４３にて処理対象として選択された候補リンク（例えば、リンクＡ；図９（ａ）参照）を経路構成リンク（図中、実線で表す）として経路リンクバッファに追加する（ステップＳ４６）。
【００６０】
その後、構成リンク抽出部７ｇは、経路端点リストを参照して、処理対象として選択されている経路端点とは反対側の端点が抽出済みの他の経路端点であるか否かを判定する（ステップＳ４７）。
ここで、経路端点とは反対側の端点が抽出済みの他の経路端点であると判定されると（ステップＳ４７；ＹＥＳ）、経路推定部７ｈは、経路リンクバッファ内の経路構成リンク（候補リンク）を、例えば、メモリ２の抽出済み経路（図示略）に追加する（ステップＳ４８）。
【００６１】
その後、構成リンク抽出部７ｇは、処理対象として選択されている候補リンクを第１リンクリストから削除する（ステップＳ４９）。また、ステップＳ４５にて、経路端点とは反対側の端点が、経路推定装置１００の移動方向側にないと判定された場合にも（ステップＳ４５；ＮＯ）、構成リンク抽出部７ｇは、処理をステップＳ４９に移行し、処理対象として選択されている候補リンクを第１リンクリストから削除する。
そして、構成リンク抽出部７ｇは、第１リンクリストに未選択の候補リンクが残っているか否かを判定する（ステップＳ５０）。
【００６２】
ステップＳ５０にて、第１リンクリストに未選択の候補リンクが残っていると判定されると（ステップＳ５０；ＹＥＳ）、構成リンク抽出部７ｇは、処理をステップＳ４３に戻し、第１リンクリストから未選択の何れか一の候補リンクを処理対象として選択し（ステップＳ４３）、それ以降の各処理を行う。
構成リンク抽出部７ｇは、上記の各処理を、ステップＳ５０にて、第１リンクリストに未選択の候補リンクが残っていないと判定（ステップＳ５０；ＮＯ）されるまで繰り返し行う。
【００６３】
一方、ステップＳ５０にて、第１リンクリストに未選択の候補リンクが残っていないと判定されると（ステップＳ５０；ＮＯ）、構成リンク抽出部７ｇは、ステップＳ４１にて処理対象として選択された経路端点を経路端点リストから削除した後（ステップＳ５１）、経路端点リストに未選択の経路端点が残っているか否かを判定する（ステップＳ５２）。
ここで、経路端点リストに未選択の経路端点が残っていると判定されると（ステップＳ５２；ＹＥＳ）、構成リンク抽出部７ｇは、処理をステップＳ４１に戻し、経路端点リストから未選択の何れか一の経路端点を処理対象として選択し（ステップＳ４１）、それ以降の各処理を行う。
構成リンク抽出部７ｇは、上記の各処理を、ステップＳ５２にて、経路端点リストに未選択の経路端点が残っていないと判定（ステップＳ５２；ＮＯ）されるまで繰り返し行う。
【００６４】
一方、ステップＳ４７にて、経路端点とは反対側の端点が抽出済みの他の経路端点でないと判定されると（ステップＳ４７；ＮＯ）、接続端点特定部７ｅは、この経路端点とは反対側の端点（例えば、図６（ａ）等における端点ｏ等）を接続端点として特定し（ステップＳ５３）、第１リンク特定部７ｄは、ステップＳ４３にて処理対象として選択された候補リンク（例えば、リンクＡ；図９（ａ）参照）を第１リンクとして特定する（ステップＳ５４）。
なお、ステップＳ５３における接続端点の特定と、ステップＳ５４における第１リンクの特定の順序は、一例であってこれに限られるものではなく、逆であっても良い。
【００６５】
その後、位置照合部７は、第１リンクと接続される第２リンクの中から、経路構成リンクを抽出するためのループ処理（図８参照）をサブルーチンとして行う（ステップＳ５５）。
以下に、ループ処理について詳細に説明する。
【００６６】
＜ループ処理＞
図８に示すように、先ず、第２リンク特定部７ｆは、第１リンクリストの中から、接続端点特定部７ｅにより特定された接続端点を経路端点とは反対側の端点とし、且つ、第１リンク特定部７ｄにより特定された第１リンク以外の候補リンクを探索し（ステップＳ６１）、探索された候補リンク（例えば、リンクＢ〜Ｄ；図９（ｂ）参照）を第２リンクとして特定し、例えば、メモリ２の第２リンクリスト（図示略）に追加する（ステップＳ６２）。
【００６７】
次に、第２リンク特定部７ｆは、第２リンクリストから何れか一の第２リンクを処理対象として選択し（ステップＳ６３）、選択された第２リンクの接続端点とは反対側の端点が、移動方向推定部５ａにより推定された経路推定装置１００の移動方向側にあるか否かを判定する（ステップＳ６４）。
ここで、第２リンクの接続端点とは反対側の端点が、経路推定装置１００の移動方向側にあると判定されると（ステップＳ６４；ＹＥＳ）、構成リンク抽出部７ｇは、ステップＳ６３にて処理対象として選択された第２リンク（例えば、リンクＢやリンクＣ；図１０（ａ）参照）を経路構成リンク（図中、実線で表す）として経路リンクバッファに追加する（ステップＳ６５）。
【００６８】
その後、第２リンク特定部７ｆは、経路端点リストを参照して、処理対象として選択されている第２リンクの接続端点とは反対側の端点が抽出済みの他の経路端点であるか否かを判定する（ステップＳ６６）。
ここで、第２リンクの接続端点とは反対側の端点が抽出済みの他の経路端点であると判定されると（ステップＳ６６；ＹＥＳ）、経路推定部７ｈは、経路リンクバッファ内の経路構成リンク（第２リンク）を抽出済み経路に追加する（ステップＳ６７）。
【００６９】
その後、第２リンク特定部７ｆは、処理対象として選択されている第２リンクを第２リンクリストから削除する（ステップＳ６８）。また、ステップＳ６４にて、第２リンクの接続端点とは反対側の端点が、経路推定装置１００の移動方向側にないと判定された場合にも（ステップＳ６４；ＮＯ）、第２リンク特定部７ｆは、処理をステップＳ６８に移行し、処理対象として選択されている第２リンクを第２リンクリストから削除する。
そして、第２リンク特定部７ｆは、第２リンクリストに未選択の第２リンクが残っているか否かを判定する（ステップＳ６９）。
【００７０】
ステップＳ６９にて、第２リンクリストに未選択の第２リンクが残っていると判定されると（ステップＳ６９；ＹＥＳ）、第２リンク特定部７ｆは、処理をステップＳ６３に戻し、第２リンクリストから未選択の何れか一の第２リンクを処理対象として選択し（ステップＳ６３）、それ以降の各処理を行う。
第２リンク特定部７ｆは、上記の各処理を、ステップＳ６８にて、第２リンクリストに未選択の第２リンクが残っていないと判定（ステップＳ６８；ＮＯ）されるまで繰り返し行う。
【００７１】
一方、ステップＳ６６にて、第２リンクの接続端点とは反対側の端点が抽出済みの他の経路端点でないと判定されると（ステップＳ６６；ＮＯ）、接続端点特定部７ｅは、この接続端点とは反対側の端点（例えば、図１０（ｂ）におけるリンクＣの端点ｃ１等）を接続端点として再度特定し（ステップＳ７０）、第１リンク特定部７ｄは、ステップＳ６３にて処理対象として選択された第２リンク（例えば、リンクＣ；図１０（ｂ）参照）を第１リンクとして再度特定する（ステップＳ７１）。
なお、ステップＳ７０における接続端点の特定と、ステップＳ７１における第１リンクの特定の順序は、一例であってこれに限られるものではなく、逆であっても良い。
【００７２】
その後、位置照合部７は、当該ループ処理（図８参照）をサブルーチンとして行う（ステップＳ７２）。つまり、図８に示すループ処理中に、ステップＳ７０にて接続端点の再度の特定が行われ、ステップＳ７１にて第１リンクの再度の特定が行われると、特定された第１リンクと接続される第２リンクの中から、経路構成リンクを抽出するためのループ処理がサブルーチンとして行われる。
すなわち、ステップＳ６５にて、構成リンク抽出部７ｇは、処理対象として選択されている第２リンクの接続端点とは反対側の端点が、経路推定装置１００の移動方向側にある第２リンク（例えば、リンクＥ；図１０（ｂ）参照）を経路構成リンクとして経路リンクバッファに追加し、ステップＳ６７にて、経路推定部７ｈは、経路リンクバッファ内の経路構成リンク（第２リンク）を抽出済み経路に追加する。
【００７３】
そして、ステップＳ７２のループ処理後、第２リンク特定部７ｆは、処理をステップＳ６８に移行し、処理対象として選択されている第２リンクを第２リンクリストから削除した後、ステップＳ６９にて、第２リンクリストに未選択の第２リンクが残っているか否かを判定する。
ステップＳ６９にて、第２リンクリストに未選択の第２リンクが残っていないと判定されると（ステップＳ６９；ＮＯ）、位置照合部７は、当該ループ処理を終了する。
【００７４】
図７に戻り、ステップＳ５５のループ処理後、構成リンク抽出部７ｇは、処理をステップＳ４９に移行し、処理対象として選択されている候補リンクを第１リンクリストから削除した後、それ以降の各処理を行う。
上記の各処理が、ステップＳ５２にて、経路端点リストに未選択の経路端点が残っていないと判定（ステップＳ５２；ＮＯ）されるまで繰り返し行われることで、抽出済み経路に、例えば、リンクＡ〜Ｃが経路構成リンクとして追加された状態となり、リンクＡ〜Ｃの何れかを組み合わせてなる経路１（リンクＡ＋リンクＢ）と経路２（リンクＡ＋リンクＣ）が推定される。
【００７５】
一方、ステップＳ５２にて、経路端点リストに未選択の経路端点が残っていないと判定されると（ステップＳ５２；ＮＯ）、構成リンク抽出部７ｇは、経路構成リンク抽出処理を終了する。
【００７６】
＜位置推定処理＞
以下に、位置推定処理について、図１１〜図１２（ｂ）を参照して説明する。
図１１は、位置照合処理における位置推定処理に係る動作の一例を示すフローチャートである。また、図１２（ａ）及び図１２（ｂ）は、位置推定処理を説明するための図であり、推定された経路を構成する経路構成リンクと粒子との関係性を模式的に表している。
【００７７】
図１１に示すように、先ず、位置推定部７ｊは、抽出済み経路から何れか一の経路（例えば、経路１）を処理対象として選択した後（ステップＳ８１）、尤度算出部７ｉは、選択された経路を構成する経路構成リンク（例えば、経路１の場合、リンクＡやリンクＢ等）と関連する粒子（図中、ドット付きの丸で表す）を特定して、例えば、メモリ２の経路構成粒子リスト（図示略）に追加する（ステップＳ８２；図１２（ａ）参照）。
【００７８】
次に、尤度算出部７ｉは、経路構成粒子リストから何れか一の粒子を処理対象として選択し（ステップＳ８３）、経路構成リンク毎に、経路構成リンクの延在方向と移動方向とのなす角度θ、経路構成リンクと粒子との距離Dist、一定距離未満の場合のクリップ用計数Cwidth等に基づいて、上記式（１）に従って粒子の尤度を算出する（ステップＳ８４）。そして、尤度算出部７ｉは、算出された尤度の最も大きい経路構成リンクを選択し、その尤度を粒子の尤度Siとする（ステップＳ８５）。
【００７９】
次に、位置推定部７ｊは、選択された経路構成リンクに対して処理対象の粒子から垂線をおろし、その交点を算出した後（ステップＳ８６）、処理対象の経路の原点（例えば、移動方向とは反対側の経路構成リンクの経路端点等）から交点までの距離を計算して、粒子の経路上で対応する位置Xiを算出する（ステップＳ８７）。そして、位置推定部７ｊは、ステップＳ８５にて算出された尤度Siの総和Sum1と、ステップＳ８７にて算出された粒子の経路上で対応する位置Xiに尤度Siを重みとして乗算したものの総和Sum2を、上記式（２）及び式（３）に従って算出する（ステップＳ８８）。
【００８０】
次に、尤度算出部７ｉは、経路構成粒子リストに未選択の粒子が残っているか否かを判定する（ステップＳ８９）。
ここで、経路構成粒子リストに未選択の粒子が残っていると判定されると（ステップＳ８９；ＹＥＳ）、尤度算出部７ｉは、処理をステップＳ８３に戻し、尤度算出部７ｉは、経路構成粒子リストから未選択の何れか一の粒子を処理対象として選択し（ステップＳ８３）、それ以降の各処理を行う。
上記の各処理が、ステップＳ８９にて、経路構成粒子リストに未選択の粒子が残っていないと判定（ステップＳ８３；ＮＯ）されるまで繰り返し行われることで、経路構成粒子リストに追加されている全ての粒子について、尤度Siと経路上で対応する位置Xiが算出されていき、ステップＳ８８にて、尤度Siの総和Sum1と、粒子の経路上で対応する位置Xiに尤度Siを重みとして乗算したものの総和Sum2とが算出される。
【００８１】
ステップＳ８９にて、経路構成粒子リストに未選択の粒子が残っていないと判定されると（ステップＳ８９；ＮＯ）、位置推定部７ｊは、総和Sum2を総和Sum1で除算して、処理対象の経路上での当該経路推定装置１００の存する位置Ｐを算出する（ステップＳ９０）。
【００８２】
続けて、位置推定部７ｊは、抽出済み経路に未選択の経路が残っているか否かを判定する（ステップＳ９１）。
ここで、抽出済み経路に未選択の経路が残っていると判定されると（ステップＳ９１；ＹＥＳ）、位置推定部７ｊは、処理をステップＳ８１に戻し、抽出済み経路から未選択の何れか一の経路を処理対象として選択し（ステップＳ８１）、それ以降の各処理を行う。
上記の各処理が、ステップＳ９１にて、抽出済み経路に未選択の経路が残っていないと判定（ステップＳ９１；ＮＯ）されるまで繰り返し行われることで、処理対象の経路毎に、この経路上での当該経路推定装置１００の存する位置Ｐが算出される。
【００８３】
一方、ステップＳ９１にて、抽出済み経路に未選択の経路が残っていないと判定されると（ステップＳ９１；ＮＯ）、位置推定部７ｊは、位置推定処理を終了する。
【００８４】
以上のように、本実施形態の経路推定装置１００によれば、複数の移動先の候補点と関連付けられる候補リンクと、推定された経路推定装置１００の移動方向とに基づいて、当該経路推定装置１００の移動している経路構成リンクが接続されてなる経路を推定するので、例えば、交差点などの複数の候補リンクが接続された複雑な経路であっても、経路推定装置１００の移動方向を考慮することで、候補リンクの端点が移動方向側にあるか、或いは、移動方向とは反対側にあるかを特定することができることとなって、接続されている複数の候補リンクの中から経路構成リンクの推定を適正に行うことができ、結果として、経路の推定を適正に行うことができる。
【００８５】
また、候補リンクの移動方向側や移動方向とは反対側の端点の中から、他の候補リンクと接続されていない何れかの端点を経路端点として抽出するので、複数の候補リンクが接続されている複雑な経路であっても、一の候補リンクの他の候補リンクと接続されていない端点については、推定される経路の端点となる可能性が高い経路端点として抽出することができる。
さらに、候補リンクの各端点の中から、推定された経路推定装置１００の移動方向側の端点であり、且つ、当該端点に接続されている他の候補リンクが移動方向側に延在していない端点、及び、推定された経路推定装置１００の移動方向とは反対側の端点であり、且つ、当該端点に接続されている全ての他の候補リンクが移動方向側に延在している端点を経路端点として抽出するので、経路推定装置１００の移動方向を考慮することで、一の候補リンクの他の候補リンクと接続されている端点であっても、移動方向側の端点であれば、この端点に接続されている他の候補リンクが移動方向側に延在していなければ、経路端点として抽出することができ、また、移動方向とは反対側の端点であれば、この端点に接続されている全ての他の候補リンクが移動方向側に延在していれば、経路端点として抽出することができる。
そして、経路端点を含む候補リンクの中で、経路端点とは反対側の端点が、当該経路端点から見て経路推定装置１００の移動方向側にある候補リンク（例えば、リンクＡ；図９（ａ）参照）を、経路構成リンクとして抽出するので、複数の候補リンクが接続されている複雑な経路であっても、経路推定装置１００の移動方向を考慮することで、当該経路推定装置１００における複数の候補リンクが接続されている部分（例えば、交差点等）に向かう方向の移動に対応する経路構成リンクを適正に抽出することができる。
【００８６】
さらに、経路端点を含む候補リンクの中で、経路端点とは反対側の端点が、経路端点から見て経路推定装置１００の移動方向側にあり、且つ、抽出されている他の経路端点でない、候補リンクを第１リンクとして特定し、第１リンクの経路端点とは反対側の端点を接続端点として特定し、候補リンクの中で、特定された接続端点を端点とし、且つ、第１リンク以外の候補リンクを第２リンクとして特定することで、特定された第２リンクのうち、接続端点とは反対側の端点が、接続端点から見て経路推定装置１００の移動方向側にある第２リンク（例えば、リンクＢやリンクＣ；図１０（ａ）参照）を経路構成リンクとして抽出することができる。つまり、複数の候補リンクが接続されている複雑な経路であっても、経路推定装置１００の移動方向を考慮することで、当該経路推定装置１００における複数の候補リンクが接続されている部分（例えば、交差点等）から離れる方向の移動に対応する経路構成リンクを適正に抽出することができる。
加えて、第２リンクのうち、接続端点とは反対側の端点が、抽出されている経路端点でない第２リンクを第１リンクとして再度特定し、再度特定された第１リンクの接続端点とは反対側の端点を接続端点として再度特定することで、例えば、３つ以上の候補リンクが連設されている経路であっても、経路推定装置１００の移動方向を考慮することで、当該経路推定装置１００における複数の候補リンクが接続されている部分から離れる方向の移動に対応し、且つ、移動方向側の端点が経路端点を構成する経路構成リンク（例えば、リンクＥ；図１０（ｂ）参照）を適正に抽出することができる。
【００８７】
また、複数の移動先の候補点のうち、推定された経路を構成する経路構成リンクと関連する候補点の尤度に基づいて、推定された経路上での当該経路推定装置１００の存する位置を推定するので、複数の移動先の候補点の中で、複数の経路構成リンクが接続されている経路の構造を考慮して適切な候補点を特定して、その候補点の尤度を用いて経路上での当該経路推定装置１００の存する位置を適正に推定することができる。
【００８８】
なお、本発明は、上記実施形態に限定されることなく、本発明の趣旨を逸脱しない範囲において、種々の改良並びに設計の変更を行っても良い。
例えば、経路推定装置１００の移動しているリンクが接続されてなる経路の推定後に、推定された経路上での当該経路推定装置１００の存する位置を推定するようにしたが、一例であってこれに限られるものではなく、必ずしも当該経路推定装置１００の存する位置を推定する必要はない。すなわち、尤度算出部７ｉ及び位置推定部７ｊを具備するか否かは適宜任意に変更可能である。
【００８９】
また、上記実施形態にあっては、経路端点抽出処理にて、候補リンクの端点の中で、推定された経路推定装置１００の移動方向側の端点であり、且つ、当該端点に接続されている他の候補リンクが移動方向側に延在していない端点、及び、推定された経路推定装置１００の移動方向とは反対側の端点であり、且つ、当該端点に接続されている全ての他の候補リンクが移動方向側に延在している端点の両方を経路端点として抽出するようにしたが、一例であってこれに限られるものではなく、少なくとも一方の端点を抽出するように構成しても良い。
【００９０】
さらに、経路推定装置１００の構成は、上記実施形態に例示したものは一例であり、これに限られるものではない。例えば、必ずしも第１測位処理部３及び第２測位処理部５を備える必要はない。
【００９１】
加えて、上記実施形態にあっては、中央制御部１のＣＰＵの制御下にて、移動方向推定部５ａ、候補点生成部７ａ、候補リンク特定部７ｂ、経路推定部７ｈが駆動する構成としたが、これに限られるものではなく、中央制御部１によって所定のプログラム等が実行されることにより実現される構成としても良い。
すなわち、プログラムを記憶するプログラムメモリ（図示略）に、移動方向推定処理ルーチン、生成処理ルーチン、候補リンク特定処理ルーチン、経路推定処理ルーチンを含むプログラムを記憶しておく。そして、移動方向推定処理ルーチンにより中央制御部１のＣＰＵを、経路推定装置１００の移動方向を推定する手段として機能させるようにしても良い。また、生成処理ルーチンにより中央制御部１のＣＰＵを、当該経路推定装置の移動元の位置を基準として、移動先の候補点を複数生成する手段として機能させるようにしても良い。また、候補リンク特定処理ルーチンにより中央制御部１のＣＰＵを、記憶されている道情報に含まれている複数のリンクの中から、生成された複数の移動先の候補点と関連付けられる１以上の候補リンクを特定する手段として機能させるようにしても良い。また、経路推定処理ルーチンにより中央制御部１のＣＰＵを、１以上の候補リンクと、経路推定装置１００の移動方向とに基づいて、当該経路推定装置１００が移動しているリンクを含む１以上のリンクが接続されてなる経路を推定する手段として機能させるようにしても良い。
【００９２】
同様に、経路端点抽出手段、経路構成リンク抽出手段、第１特定手段、接続端点特定手段、第２特定手段、算出手段、位置推定手段についても、中央制御部１のＣＰＵによって所定のプログラム等が実行されることにより実現される構成としても良い。
【００９３】
さらに、上記の各処理を実行するためのプログラムを格納したコンピュータ読み取り可能な媒体として、ＲＯＭやハードディスク等の他、フラッシュメモリ等の不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬型記憶媒体を適用することも可能である。また、プログラムのデータを所定の通信回線を介して提供する媒体としては、キャリアウェーブ（搬送波）も適用される。
【００９４】
本発明のいくつかの実施形態を説明したが、本発明の範囲は、上述の実施の形態に限定するものではなく、特許請求の範囲に記載された発明の範囲とその均等の範囲を含む。
以下に、この出願の願書に最初に添付した特許請求の範囲に記載した発明を付記する。付記に記載した請求項の項番は、この出願の願書に最初に添付した特許請求の範囲の通りである。
〔付記〕
＜請求項１＞
経路推定装置であって、
複数のリンクを含む道情報を記憶する記憶手段と、
当該経路推定装置の移動方向を推定する移動方向推定手段と、
当該経路推定装置の移動元の位置を基準として、移動先の候補点を複数生成する生成手段と、
前記記憶手段に記憶されている道情報に含まれている前記複数のリンクの中から、前記生成手段により生成された複数の移動先の候補点と関連付けられる１以上の候補リンクを特定する候補リンク特定手段と、
前記１以上の候補リンクと、前記移動方向とに基づいて、当該経路推定装置が移動しているリンクを含む１以上のリンクが接続されてなる経路を推定する経路推定手段と、
を備えたことを特徴とする経路推定装置。
＜請求項２＞
前記１以上の候補リンクの各端点の中から、前記経路推定手段により推定される経路の端点を構成する経路端点を抽出する経路端点抽出手段を更に備え、
前記経路端点抽出手段は、
前記１以上の候補リンクの各端点の中から、複数の候補リンクと接続されていない何れかの端点を前記経路端点として抽出することを特徴とする請求項１に記載の経路推定装置。
＜請求項３＞
前記経路端点抽出手段は、更に、
前記１以上の候補リンクの各端点の中から、当該１以上の候補リンクのうちの一の候補リンクの前記移動方向側の端点であり、且つ、当該移動方向側の端点に接続されている前記一の候補リンク以外の候補リンクが当該移動方向側の端点から見て前記移動方向側に延在していない端点、及び、前記一の候補リンクの前記移動方向とは反対側の端点であり、且つ、当該移動方向とは反対側の端点に接続されている前記一の候補リンク以外の全ての候補リンクが移動方向側に延在している端点のうち、少なくとも一方の端点を前記経路端点として抽出することを特徴とする請求項２に記載の経路推定装置。
＜請求項４＞
前記１以上の候補リンクのうちの前記経路端点抽出手段により抽出された前記経路端点を含む含経路端点候補リンクの中から、前記経路推定手段により推定される経路を構成する経路構成リンクを抽出する経路構成リンク抽出手段を更に備え、
前記経路構成リンク抽出手段は、
前記含経路端点候補リンクのうちの一の含経路端点候補リンクであって、当該一の含経路端点候補リンクの両方の端点のうち、前記経路端点とは反対側の端点が、当該経路端点から見て前記移動方向側にある前記一の含経路端点候補リンクを、前記経路構成リンクとして抽出することを特徴とする請求項２又は３に記載の経路推定装置。
＜請求項５＞
前記経路端点抽出手段により抽出された前記経路端点を含む含経路端点候補リンクの中から、当該含経路端点候補リンクの前記経路端点とは反対側の端点が、当該含経路端点候補リンクの前記経路端点から見て前記移動方向側にあり、且つ、当該反対側の端点が、前記経路端点抽出手段により抽出されている他の前記経路端点でない、前記含経路端点候補リンクを第１リンクとして特定する第１特定手段と、
前記第１特定手段により特定される前記第１リンクの端点のうち前記経路端点とは反対側の端点を接続端点として特定する接続端点特定手段と、
前記１以上の候補リンクのうち、前記接続端点特定手段により特定された前記接続端点を端点とし、且つ、前記第１リンク以外の前記候補リンクを第２リンクとして特定する第２特定手段と、
を更に備え、
前記経路構成リンク抽出手段は、
前記第２特定手段により特定された前記第２リンクのうち、当該第２リンクの前記接続端点とは反対側の端点が、当該第２リンクの前記接続端点から見て前記移動方向側にある前記第２リンクを前記経路構成リンクとして抽出することを特徴とする請求項４に記載の経路推定装置。
＜請求項６＞
前記第１特定手段は、前記第２特定手段により特定された前記第２リンクのうち、当該第２リンクの前記接続端点とは反対側の端点が、前記経路端点抽出手段により抽出されている前記経路端点でない前記第２リンクを前記第１リンクとして再度特定し、
前記接続端点特定手段は、前記第１特定手段により再度特定された前記第１リンクの前記接続端点とは反対側の端点を接続端点として再度特定することを特徴とする請求項５に記載の経路推定装置。
＜請求項７＞
前記生成手段により生成された複数の移動先の候補点のうち、前記経路推定手段により推定された経路を構成するリンクと関連する候補点の尤度をそれぞれ算出する算出手段と、
前記算出手段により算出された移動先の候補点の尤度に基づいて、前記経路推定手段により推定された経路上での当該経路推定装置の存する位置を推定する位置推定手段と、
を更に備えたことを特徴とする請求項１〜６の何れか一項に記載の経路推定装置。
＜請求項８＞
複数のリンクを含む道情報を記憶する記憶手段を備える経路推定装置を用いた経路推定方法であって、
当該経路推定装置の移動方向を推定する処理と、
当該経路推定装置の移動元の位置を基準として、移動先の候補点を複数生成する処理と、
前記記憶手段に記憶されている道情報に含まれている前記複数のリンクの中から、生成された複数の移動先の候補点と関連付けられる１以上の候補リンクを特定する処理と、
前記１以上の候補リンクと、前記移動方向とに基づいて、当該経路推定装置が移動しているリンクを含む１以上のリンクが接続されてなる経路を推定する処理と、
を含むことを特徴とする経路推定方法。
＜請求項９＞
複数のリンクを含む道情報を記憶する記憶手段を備える経路推定装置のコンピュータを、
当該経路推定装置の移動方向を推定する移動方向推定手段、
当該経路推定装置の移動元の位置を基準として、移動先の候補点を複数生成する生成手段、
前記記憶手段に記憶されている道情報に含まれている前記複数のリンクの中から、前記生成手段により生成された複数の移動先の候補点と関連付けられる１以上の候補リンクを特定する候補リンク特定手段、
前記１以上の候補リンクと、前記移動方向とに基づいて、当該経路推定装置が移動しているリンクを含む１以上のリンクが接続されてなる経路を推定する経路推定手段、
として機能させることを特徴とするプログラム。
【符号の説明】
【００９５】
１００  経路推定装置
１      中央制御部
５      第２測位処理部
５ａ    移動方向推定部
６      記憶部
６ａ    地図データベース
７      位置照合部
７ａ    候補点生成部
７ｂ    候補リンク特定部
７ｃ    経路端点抽出部
７ｄ    第１リンク特定部
７ｅ    接続端点特定部
７ｆ    第２リンク特定部
７ｇ    構成リンク抽出部
７ｈ    経路推定部
７ｉ    尤度算出部
７ｊ    位置推定部
【図１】
0006696253.tif 000002
【図２】
0006696253.tif 000003
【図３】
0006696253.tif 000004
【図４】
0006696253.tif 000005
【図５】
0006696253.tif 000006
【図６】
0006696253.tif 000007
【図７】
0006696253.tif 000008
【図８】
0006696253.tif 000009
【図９】
0006696253.tif 000010
【図１０】
0006696253.tif 000011
【図１１】
0006696253.tif 000012
【図１２】
0006696253.tif 000013