説明

ナビゲーション装置、方法及びシステム

【課題】 経路探索を短時間で行うことができるナビゲーション装置を提供する。
【解決手段】 地図DB22には、道路地図を構成する複数のブロックの各々に含まれるノードの位置情報が記憶され、交通情報取得部24は、車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する。ブロック内情報記憶部26は、ブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び/または転出ノードとして定め、転入ノードから転出ノードに至る経路を示すブロック内経路情報を記憶する。ブロック内経路生成部28は、個々の前記ブロックにおける、転入ノードから転出ノードに至る最適経路を探索し、探索された経路情報をブロック内経路情報として更新する。全体経路探索部30は、複数のブロック内経路情報を組み合わせて、現在位置から前記目的地までの経路情報を生成する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、目的地までの経路を示す経路情報を提供するナビゲーション装置に関する。
【背景技術】
【0002】
カーナビゲーションシステム等に用いられるナビゲーション装置では、出発地から目的地までの経路を探索する機能を備えている。経路探索の方法としては、経路ネットワークを構成するノードやリンクに対して重み係数(コストパラメータ)を設定し、目的地までの総コストが最小となるような経路を、例えばダイクストラ法によって決定する。コストパラメータとしては、例えば距離、道路種別、道幅、信号機の有無、右左折等のパラメータが用いられる。
【0003】
また、特許文献1では、コストパラメータを記憶するコストテーブルを、所定地域ごとに個別に設定しておき、これらコストテーブルを用いて目的地までの経路コストを算出するナビゲーション装置が開示されている。
【0004】
さらに、特許文献2では、複数のコストテーブルを備えておき、時間帯や平日/休日といった短期的に変化するパラメータに基づき、ベイジアンネットワークを用いて条件付確率が最も高いコストテーブルを選択することで、運転手の好みが反映された経路を探索することができるナビゲーションシステムが開示されている。
【先行技術文献】
【特許文献】
【0005】
【特許文献1】特開2005−181063号公報
【特許文献2】特開2007−10571号公報
【発明の概要】
【発明が解決しようとする課題】
【0006】
しかしながら、上記特許文献に記載の技術では、車両の現在位置(起点)から目的地(終点)に至る全ての経路について経路探索を行うため、経路探索に時間がかかってしまうという問題があった。特に、車両に搭載されたナビゲーション装置から、地図データを記憶する記憶装置を省略し、経路探索の機能を車両に接続された中央サーバで一元的に行うことが、装置のコスト削減の観点から好ましいところ、上記特許文献に記載の技術では、多数の車両から同時に経路探索要求がなされた場合に、迅速に経路探索を行うことができなかった。
【0007】
本発明は、上記事情に鑑みなされたものであり、経路探索を短時間で効率的に行うことができるナビゲーション装置を提供することを目的とする。
【課題を解決するための手段】
【0008】
本発明のナビゲーション装置は、車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する情報取得部と、道路地図を構成する複数のブロックの各々に含まれるノードの位置情報を記憶する地図情報記憶部と、前記ブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び/または転出ノードとして定め、前記転入ノードから前記転出ノードに至る経路を示すブロック内経路情報を記憶するブロック内情報記憶部と、個々の前記ブロックにおける、前記転入ノードから前記転出ノードに至る最適経路を探索し、探索された経路情報を前記ブロック内経路情報として更新するブロック内経路生成部と、複数の前記ブロック内経路情報を組み合わせて、前記現在位置から前記目的地までの経路情報を生成する全体経路探索部とを備えた構成を有している。
【0009】
この構成により、道路地図を分割したブロックの各々について最適経路を算出し、得られたブロック毎の最適経路情報を組み合わせることで、現在地から目的地に至る経路情報を抽出するようにしたから、経路探索に要する時間を短縮することができる。
【0010】
本発明のナビゲーション装置において、ブロック内情報記憶部は、前記転入ノードから前記転出ノードに至る経路のリンクコスト情報を、前記ブロック内経路情報と対応付けて記憶する最適経路テーブルを備えている。これにより、道路種別や渋滞状況といったリンクコストを用いて、ブロック内の最適経路を探索することができるから、経路探索の向上を図ることができる。
【0011】
本発明のナビゲーション装置において、ブロック内情報記憶部は、ブロック内の隣接ノード間の移動確率を示す移動確率テーブルを備え、前記ブロック内経路生成部は、前記移動確率テーブルに記憶された移動確率に基づき、前記転入ノードから前記転出ノードに至る最適経路を探索する。ブロック内のノード間のフェロモン量を示すフェロモン量テーブルと、前記ブロック内のノード間の前記リンクコストを示すリンクコストテーブルを備え、前記ブロック内経路生成部は、所定時間毎に、前記フェロモン量テーブル及び/又は前記リンクコストテーブルを更新するとともに、前記ノード間の前記フェロモン量及び前記リンクコストに基づいて前記移動確率を更新することが好ましい。これにより、移動確率の最も高いノードの組合せを最適経路として定めることができるから、最適な経路を効率よく抽出することができる。
【0012】
本発明のナビゲーション装置において、全体経路探索部は、前記最適経路テーブルに記憶された前記転入ノードから前記転出ノードへの経路を1つのリンクとみなして、前記現在位置から前記目的地までの経路情報を生成する。これにより、ブロック毎に予め定められた最適経路を組み合わせることで、目的地までの経路を探索することができるから、経路探索を短時間で効率的に行うことができる。
【0013】
本発明のナビゲーション装置において、前記車両の通過経路を示す前記転入ノード及び前記転出ノードの情報を記憶する経路情報記憶部と、前記ブロック内の経路状態が変動したことを示す変動情報を、前記転入ノード及び前記転出ノードの組合せ毎に記憶する変動情報記憶部と、経路状態が変動した前記転入ノード及び前記転出ノードの組合せを通過経路に含む前記車両に対して、経路検索を促す通知を発する通知判定部とを備えた構成を有する。通知を受けた車両において、ナビゲーション装置に対して経路再探索を要求することができる。この構成により、目的地までの全体の最適経路が変動した場合に、ナビゲーション装置から車両に通知を行うようにしたので、目的地までの走行経路のアップデートを効率よく行うことができる。また、ナビゲーション装置において不必要な経路検索が行われることがなくなるから、処理の効率化、通信コストの削減を図ることができる。ここで、前記変動情報は、前記転入ノードから前記転出ノードに至る最適経路が変更されたか否かを示す情報とすることが好ましく、これにより、各ブロックにおける最適経路が変動した場合に、最適経路の変更を車両に通知することができる。
【0014】
本発明のナビゲーション装置は、前記ブロックにおける最適経路情報を更新する前記ブロック内経路生成部を複数備えた構成を有する。この構成により、複数のブロックにおける最適経路の探索を並列して行うことができるから、最適経路の抽出処理に要する時間を短縮することができる。
【0015】
本発明のナビゲーション方法は、車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する情報取得ステップと、道路地図を構成する複数のブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び/または転出ノードとして定め、前記転入ノードから前記転出ノードに至る経路を示すブロック内経路情報を記憶するブロック内情報記憶ステップと、個々の前記ブロックにおける、前記転入ノードから前記転出ノードに至る最適経路を探索し、探索された経路情報を前記ブロック内経路情報として更新するブロック内経路生成ステップと、複数の前記ブロック内経路情報を組み合わせて、前記現在位置から前記目的地までの経路情報を生成する全体経路探索ステップを備えた構成を有する。この構成によっても、上記と同様に、道路地図を構成する各ブロックにおける最適経路を算出し、これらを組み合わせることで、現在地から目的地に至る経路情報を抽出するので、経路探索に要する時間を短縮することができる。
【0016】
本発明のナビゲーションシステムは、道路地図を複数のブロックに分割するとともに、分割された各ブロック内における最適経路情報を生成する複数の経路生成装置と、前記経路生成装置と接続されたナビゲーション装置を備え、前記ナビゲーション装置は、車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する情報取得部と、道路地図を構成する複数のブロックの各々に含まれるノードの位置情報を記憶する地図情報記憶部と、前記ブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び/または転出ノードとして定め、前記転入ノードから前記転出ノードへの最適経路を示すブロック内最適経路情報を記憶する最適経路記憶部と、複数の前記ブロック内経路情報を組み合わせて、前記現在位置から前記目的地までの経路情報を生成する全体経路探索部を備え、前記経路生成装置は、前記ブロックの各々について、前記転入ノードから前記転出ノードに至る経路を示すブロック内経路情報を記憶するブロック内情報記憶部と、個々の前記ブロックにおける、前記転入ノードから前記転出ノードに至る最適経路を探索し、探索された経路情報を前記ブロック内経路情報として更新するブロック内経路生成部とを備え、前記ナビゲーション装置は、前記ブロック内経路生成部で探索された前記経路情報に基づき、前記ブロック内最適経路情報を更新する。この構成によっても、上記と同様に、道路地図を構成する各ブロックにおける最適経路を算出し、これらを組み合わせることで、現在地から目的地に至る経路情報を抽出するので、経路探索に要する時間を短縮することができる。
【発明の効果】
【0017】
本発明によれば、道路地図を複数のブロックに分割し、各ブロックにおける最適経路を算出するとともに、これら各ブロックの最適経路を組み合わせることで、現在地から目的地に至る経路情報を抽出するようにしたから、経路探索を短時間で効率的に行うことができる。
【図面の簡単な説明】
【0018】
【図1】本発明の実施形態に係るナビゲーション装置から車両に経路情報を送信する例を示すブロック図
【図2】本発明の実施形態に係るナビゲーション装置の構成を示すブロック図
【図3】道路地図を複数のブロックに分割した例を示す説明図
【図4】道路地図を構成するブロック内の経路図の一例を示す説明図
【図5】ブロック内情報記憶部のデータ構成の一例を示す説明図
【図6】隣接ノード間の位置関係と各パラメータを示す説明図
【図7】フェロモン量テーブルのデータ構成の一例を示す説明図
【図8】エージェント経路テーブルのデータ構成の一例を示す説明図
【図9】最適経路テーブルのデータ構成の一例を示す説明図
【図10】あるエージェントによる走行経路の一例を示す説明図
【図11】別のエージェントによる走行経路の一例を示す説明図
【図12】探索された経路の一例を示す説明図
【図13】ブロック内の各種テーブルの更新処理の一例を示すフローチャート
【図14】車両の現在位置から目的地までの経路探索処理の一例を示すフローチャート
【図15】本発明の別の実施形態に係るナビゲーションシステムの構成を示すブロック図
【図16】本発明のさらに別の実施形態に係るナビゲーションシステムの構成を示すブロック図
【図17】図15のシステムを構成するナビゲーション装置と経路生成装置の構成を示すブロック図
【図18】本発明のさらに別の実施形態に係るナビゲーションシステムの構成を示すブロック図
【図19】渋滞の発生によりブロック内の最短経路が変更された様子を説明するための図
【図20】ブロック内の変化フラグテーブルの一例を示す説明図
【図21】経路情報記憶部の一例を示す説明図
【図22】ナビゲーション装置の動作の一例を示すフローチャート
【発明を実施するための形態】
【0019】
(第1実施形態)
以下、図面を参照して、本発明の第1実施形態に係るナビゲーション装置について説明する。図1において、本実施形態に係るナビゲーション装置10は、道路上を走行する複数の車両12と例えば無線通信回線によって接続されており、目的地までの経路要求を車両12から受信したときに、後述する手順により目的地までの経路を探索し、経路情報として車両12に対して送信する。また、ナビゲーション装置10は、VICS(登録商標)センター14に接続されており、渋滞情報や交通規制情報等の各種の交通情報を受信する。
【0020】
図2において、ナビゲーション装置10は、通信部20、地図DB22、交通情報取得部24、ブロック内情報記憶部26、経路生成部28、全体経路探索部30を備えており、図示しない制御回路によりその動作が制御されている。
【0021】
通信部20は、例えばインターネット回線に接続可能な無線通信モジュールであり、車両12から現在位置及び目的地の情報を含む経路要求を受信するとともに、経路要求を発した車両12に経路情報を送信する。また、通信部20は、VICS(登録商標)センター14からの交通情報を受信する受信手段を備える。なお、通信部20は、例えば車両との間で公知の路車間通信を行う通信装置との間で、情報の送受信を行う無線通信モジュールを備えても良い。
【0022】
地図DB22は、道路地図を構成する各区間(リンク)の位置情報、各リンクの端点(ノード)の位置情報、ノード及びリンクのコストを示すコスト情報(例えば、距離、道路種別、道幅、渋滞の程度、交通規制の有無、信号機の有無、右左折等の情報)、道路上の施設情報などのデータを含む。この地図DB22内の情報は、例えばVICS(登録商標)センター14からの交通情報に基づき更新される。
【0023】
図3に示すように、地図DB22に含まれる道路地図40は、複数のブロック42に区分けされており、区分けされた各ブロックの境界位置を示す情報(例えば、境界上のノードの位置情報)を記憶している。なお、道路地図40の分割方法としては、図3に示されているような格子形状に限られることはなく、例えば市区町村ごとに個別のブロックを形成しても良い。
【0024】
図4は、図3の道路地図を構成する一つのブロック44を拡大したものである。ブロック44は、例えば、隣接するブロックとの境界上に設けられたノードO1〜O3,D1〜D3と、ブロック44内のリンクの端点を示すノードN1〜N4とを有する。また、図4において、ブロック44内の矢印46は道路(リンク)を示している。なお、これらノード及びリンクの位置情報は、地図DB22に記憶されている。
【0025】
図4において、「O1」と示されているのは、当該ブロックに車両が入る際に通過するノード(転入ノード)であり、「D1」と示されているのは、当該ブロックから別のブロックに車両が出る際に通過するノード(転出ノード)である。図4の例では、ノードO1〜O3,D1〜D3を通過する道路を介して、隣接ブロックと接続されていることが示されている。これら転入ノードは、ブロックを構成する各辺ごとに定められている。すなわち、各ブロックを構成する上下左右の辺ごとに、転入ノード及び転出ノードが設けられており、図4ではブロックの左辺を転入ノードとする例が示されている。なお、ブロックの他辺を転入ノードとする例については、図4の例と同様であるため、説明を省略する。
【0026】
なお、図4の例では、転入ノードO1〜O3及び転出ノードD1〜D3が3つずつ設けられているが、転入ノード及び転出ノードの数はこれに限定されることはなく、ブロックをまたぐ道路の数に応じて、転入及び転出ノードを定めることができる。また、図4の例では、ブロックの上辺及び下辺に転出ノードが設けられていないが、ブロックの上辺あるいは下辺を通過する道路が存在する場合には、転出ノードが設けられることはもちろんである。
【0027】
図2において、交通情報取得部24は、経路要求を発した車両12の位置情報及び目的地情報を取得するとともに、地図DB22に記憶された各ブロックの境界ノードの位置情報を参照して、当該車両12及び目的地の場所に対応するブロックの識別情報を取得する。また、交通情報取得部24は、VICS(登録商標)センター14からの渋滞情報や交通規制情報等の各種交通情報を一時的に記憶し、地図DB22内の情報を更新する。
【0028】
ブロック内情報記憶部26は、道路地図を構成する各ブロックの情報を記憶するものであり、図5に示すように、フェロモン量テーブル50、移動確率テーブル52、リンクコストテーブル54、エージェント経路テーブル56、最適経路テーブル58を備える。これら各種テーブル50〜58は、道路地図を構成するブロックごとに設けられている。
【0029】
ここで、フェロモン量とは、あるリンク(ノード間)における車両の存在量を示す指標であり、例えば、「車両が5台存在する場合に10である」といった基準によって定められる。フェロモン量は、例えば時間tの関数として定められ、時間tの経過とともに減衰していくものであり、例えば1秒間に1割の程度で減衰する。なお、減衰させる時間は1秒間隔に限られず、また、減衰割合も1割に限られることはない。ノードXとノードY間のフェロモン量τxyは、例えば次式で表される。
【0030】
【数1】

【0031】
ここで、τxy(t)は、時間tにおけるフェロモン量、ρは減衰率であり、Δτxyは、時間tから時間(t+1)の間に増加するフェロモン量(後述するエージェントの通過数)である。なお、フェロモン量τxyは、上式に限られることはなく、例えば、隣接するリンクから一定割合で伝達する(伝達フェロモン)成分を含んでも良い。また、所定時間、フェロモン量が増加しない場合(Δτが所定時間ゼロの場合)には、τの値をゼロにしても良い。
【0032】
リンクコストとは、あるリンク(ノード間)における距離を示す重み値ηであり、地図DB22に記憶されているノードの位置情報に基づき算出される。リンク間の距離が短い場合はηの値は小さく、リンクの距離が長い場合にはηの値が大きくなる。
【0033】
また、移動確率ρは、あるノードから隣接する別ノードに移動する確率を示すものであり、移動確率ρが大きいほど、車両が通過する割合が高く、最適な走行経路であることが示される。ノードXからノードYに向かう移動確率ρxyは、例えば次式で表すことができる。
【0034】
【数2】

【0035】
ここで、ηxy(t)は、時間tにおけるノードX・Y間のリンクコスト、αは正の定数、βは負の定数である。また、上式において、Yは、あるノードXと隣接するノードを示す。上式によれば、フェロモンτの値が大きい場合や、リンクコストηの値が小さい場合はノード間の移動確率が高くなり、フェロモンτの値が小さい場合や、リンクコストηの値が大きい場合はノード間の移動確率が低くなる。
【0036】
図6は、ブロック内の隣接ノード間の関係の一例を示したものである。図6の例では、ノードNxと隣接するY1,Y2,Y3の3つのノードが定められ、各ノード間において、移動確率ρ、フェロモン量τ、リンクコストηが定められており、これらの値が、フェロモン量テーブル50、移動確率テーブル52、リンクコストテーブル54にそれぞれ記憶されている。
【0037】
図7は、フェロモン量テーブル50のデータ構成の一例を示したものである。フェロモン量テーブル50は、ブロック44の転出ノードD1〜D3ごとに、当該ブロック44内におけるノード間のフェロモン量τのデータを記憶している。
【0038】
図7において、τO1N1(D1)は、転出ノードをD1としたときの、ノードO1とノードN1との間のフェロモン量を示す。フェロモン量テーブル50に記憶されたフェロモン量のデータは、後述するエージェントによるノード探索処理が行われる毎に更新される。同様に、移動確率テーブル52、リンクコストテーブル54は、それぞれ、ブロック44内のノード間の移動確率p及びリンクコストηを、転出ノードD1〜D3ごとに記憶している。なお、フェロモン量テーブル50、移動確率テーブル52、リンクコストテーブル54は、全ての転入ノード(本実施形態ではO1〜O3)に共通である。
【0039】
エージェント経路テーブル56は、後述するエージェントによる、ブロック44内の転入及び転出ノードに至る経路を一時的に記憶するものである。ここで、エージェントとは、ブロック44内を移動する車両を仮想的に示したものであり、エージェントの各々は、複数の転入ノードからランダムに決定された転入ノードを出発点、予め定められた転出ノードを目的点として移動するとともに、ブロック内のノード間の移動は、移動確率テーブルに記憶された移動確率に従う。すなわち、あるノード(例えば、図6におけるノードX)と隣接するノードが複数存在する場合(例えば、図6におけるノードY1,Y2,Y3)、移動確率が高いノード間(例えば、Pxy1が最も大きい場合は、ノードX・Y1間)を通過する確率が高くなる。
【0040】
また、エージェント経路テーブル56には、エージェントが通過した経路が、転入ノード・転出ノード間の最適経路であるか否かを示す最適フラグが設けられている。この最短フラグは、後述する最適経路テーブル58に記憶されている最適経由ノードと、エージェントの通過経由ノードとが一致した場合に「1」が、異なる場合に「0」が記憶される。これにより、各エージェントの走行経路が最適であるか否かを検出することができる。
【0041】
最適経路テーブル58は、ブロック44内の転入及び転出ノード毎に、最適経路を示す経路ノードの情報と、経路長の情報が記憶されている。本実施形態において、最適経路とは、転入ノードから転出ノードに至る最短経路を意味する。例えば、転入ノードを「O1」、転出ノードを「D1」とする場合の最適経路は、ノードO1、ノードN1、ノードN3、ノードD1となり、その経路による経路長はL11となる。同様に、転入ノードを「O2」、転出ノードを「D3」とする場合の最適経路は、ノードO2、ノードN1、ノードN4、ノードD3となり、その経路による経路長はL23となる。
【0042】
ブロック内経路生成部28は、各ブロック44における、転入ノード・転出ノード間の最適経路を抽出する。この最適経路の抽出は、前述したエージェントを用いた経路探索の方法により行うことができる。すなわち、ブロック内経路生成部28は、エージェントの転出ノードを固定するとともに、転入ノードをランダムに決定する。そして、ランダムに決定された転入ノードを出発点とし、移動確率テーブル52に記憶されたノード間の移動確率に従い、移動すべきノードを決定する。そして、移動先のノードにおいて、同様に、移動確率テーブル52内の移動確率に従い、次に移動すべきノードを決定する。このようにして、エージェントがノード間を移動する。
【0043】
ブロック内経路生成部28は、各エージェントの移動回数の上限値THを予め定めており、起点ノードからTH回の移動によっても、目的地としての転出ノードに到達しない場合は、当該エージェントによる経路移動を中止する。そして、別のエージェントを、ランダムに決定された転入ノードに配置し、同様にしてエージェントを移動させる。ブロック内経路生成部28は、設定された転出ノードに達したエージェントにつき、その走行経路(経由ノード)の情報を、エージェント経路テーブル56に記憶する。
【0044】
図10は、エージェントの移動経路の一例を示したものである。このエージェントAG1は、起点としての転入ノードが「O1」と定められ、ノード間の移動確率に従い、ノード間を移動する。エージェントAG1は、ノードN2、ノードN3を経由して、目的地である転出ノードD1に到達する。そして、ブロック内経路生成部28は、当該エージェントAG1による経由ノードと、最適経路テーブル58に記憶された経由ノードとを比較し、異なる場合には、当該エージェントAG1の経路が最適ではないと判定し、エージェント経由テーブル56内の対応する最適フラグを「0」とする。
【0045】
図11は、別のエージェントAG2の移動経路の一例を示したものである。このエージェントAG2は、起点としての転入ノードが「O2」と定められ、ノード間の移動確率に従いノード間を移動する。エージェントAG2は、ノードN1、ノードN3を経由して、目的地である転出ノードD1に到達する。そして、ブロック内経路生成部28は、当該エージェントAG2による経由ノードと、最適経路テーブル58に記憶された経由ノードとを比較し、一致する場合には、当該エージェントAG2の経路が最適であると判定し、エージェント経由テーブル56内の対応する最適フラグを「1」とする。
【0046】
ブロック内経路生成部28は、目的地である転出ノードD1に到達したエージェントの数が、予め定められた所定値mに達したときに、エージェントによる経路探索を終了する。そして、ブロック内経路生成部28は、エージェント経由テーブル56に記憶された全エージェントの走行経路情報に基づき、フェロモン量テーブル50、移動確率テーブル52及び最適経路テーブル58を更新する。
【0047】
すなわち、ブロック内経路生成部28は、エージェント経由テーブル56に記憶された経由ノード情報より、全エージェントの通過リンク数を、リンク毎に集計する。そして、例えばリンクXY間におけるエージェントの通過回数を、前記(1)式のΔτXYと定め、前記(1)式により、リンクXY間のフェロモン量を更新する(ローカル更新)。このようなローカル更新処理は、リンク毎及び転出ノード毎に行われる。
【0048】
さらに、ブロック内経路生成部28は、最適経路テーブル58に記憶された最適経路情報と一致する経路を通過したエージェントがある場合には、当該エージェントが通過した経路に対応するリンクについて、前記(1)式のΔτXYの値に一定量を加算する(グローバル更新)。例えば、転入ノード「O1」、転出ノード「D1」に対応する最適経由ノード「O1,N1,N3,D1」と同じ経由ノードを通過したエージェントが存在する場合には、ΔτO1,N1、ΔτN1,N3、ΔτN3,N1の値に、それぞれ一定量を加算する。これにより、最適経路に対して多くのフェロモンが集まるので、最適経路を効率よく抽出することができる。
【0049】
そして、ブロック内経路生成部28は、フェロモン量テーブル50を更新した後、前記(2)式に基づき、各ノード間の移動確率を更新する。また、ブロック内経路生成部28は、最適経路テーブル58に記憶された経路よりもコストの低い(距離が短い)経路が、エージェント経由テーブル56に記憶されている場合には、当該エージェント経由テーブル56に記憶された経路に置き換える。これにより、最適経路を更新することができる。
【0050】
ブロック内経路生成部28は、道路地図40を構成する各ブロック44について、フェロモン量テーブル50、移動確率テーブル52及び最適経路テーブル58を更新する。
【0051】
全体経路探索部30は、ブロック内経路生成部28によって生成された各ブロックの最適経路テーブル28を参照して、各ブロックの転入ノードから転出ノードに至る距離情報を抽出し、これらを組み合わせることで、車両の現在位置から目的地に至る走行経路を抽出する。
【0052】
図12は、全体経路探索部30において、車両の現在位置に対応する始点ノードONから、車両の目的地である終点ノードDNに至る走行経路を抽出する一例を示したものである。全体経路探索部30は、車両12から送信され、交通情報取得部24において取得した車両の位置情報に基づき、車両12が存在するブロック(始点ブロック)64と、始点ノードONを特定する。同様に、車両12から送信された目的地情報に基づき、目的地が存在するブロック(終点ブロック)65と、当該目的地の終点ノードDNを特定する。
【0053】
全体経路探索部30は、始点ブロック及び終点ブロックにおけるノード情報及びコストテーブルを地図DB22から読み出すとともに、始点ブロック及び終点ブロックを含む一定範囲のブロックに対応する最適経路テーブル58から、各ブロックの転入ノード及び転出ノードの情報とこれら転入・転出ノード間のコスト情報(距離情報)を読み出す。そして、そして、全体経路探索部30は、読み出されたノード間距離情報に基づき、例えばダイクストラ法により、始点ノードONから終点ノードDNに至る走行経路を抽出する。図12の例では、始点ノードONから隣接するブロックの転入ノード66及び転出ノード67が求められ、以後同様にして、各ブロックの転入ノード及び転出ノードが算出される。そして、終点ブロックの転入ノード(終点ブロックに隣接するブロックの流出ノード)68を経由して、終点ノードDNまでの走行経路が抽出される。
【0054】
以下、上記構成によるナビゲーション装置の動作について、図13,14のフローチャートを用いて説明する。図13は、ブロック内経路生成部28において、各ブロックにおける最適経路を抽出する処理を示すフローチャートである。ブロック内経路生成部28は、ブロックごとに、エージェントの到達目標としての転出ノードを設定し(S10)、エージェントの転入ノードをランダムに選択し、選択された転入ノードにエージェントを配置する(S11)。
【0055】
次に、ブロック内経路生成部28は、移動確率テーブル52に記憶されたノード間の移動確率に従い、ブロック内でエージェントを移動させるとともに、当該エージェントが通過したノード(経由ノード)の情報を、エージェント経路テーブル56に記憶する(S12)。
【0056】
ブロック内経路生成部28は、各エージェントが、転入ノードから所定回数TH内の移動により、設定された転出ノードに到達したか否かを検出する(S13)。エージェントが所定回数TH内に転出ノードに到達していない場合(ステップS13において「N」)は、当該エージェントの通過ノードの情報を削除する。これにより、通過経路が多く、最適経路の抽出に寄与しないエージェントの情報を確実に排除することができる。
【0057】
このエージェントが所定回数TH内の移動により転出ノードに到達した場合(ステップS13において「Y」)には、ブロック内経路生成部28は、m個のエージェントが転出ノードに到達したか否か、すなわち、エージェント経路テーブル56に記憶されたエージェントの数がmに達したか否かを検出する(S15)。その結果、転出ノードに達したエージェント数がm未満である場合には、再びステップS11に戻り、別のエージェントを転入ノードに配置して、上記と同様にしてブロック内でエージェントを移動させる。これにより、フェロモン量テーブル50、移動確率テーブル52及び最適経路テーブル58の更新に必要な数のエージェントの通過ノード情報を得ることができる。
【0058】
一方、転出ノードに達したエージェント数がmに達した場合には、ブロック内経路生成部28は、エージェント経路テーブル56に記憶されたエージェントの通過ノード情報に基づき、フェロモン量テーブル50を更新し、更新後のフェロモン量テーブル50に基づいて移動確率テーブル52を更新する(S16)。これにより、最適な経路に対するフェロモン量及び移動確率を高くすることができ、最適経路を効率よく抽出することができる。
【0059】
また、ブロック内経路生成部28は、エージェント経路テーブル56に記憶されたエージェントの通過ノード情報から得られる、転入ノードから転出ノードまでの距離が、最適経路テーブル58に記憶された距離よりも短い場合には、当該最適経路テーブル58の情報を更新する(S17)。これにより、各ブロックにおける最適経路が更新される。
【0060】
そして、ブロック内経路生成部28は、ブロック内に定められた全ての転出ノードについて、上述した処理(各種テーブルの更新処理)が行われたか否かを検出する(S18)。各種テーブルの更新処理が終了していない転出ノードが残っている場合(ステップS18において「N」)は、再びステップS10に戻り、別の転出ノードに対して、同様の更新処理を行う。
【0061】
一方、ブロック内の全ての転出ノードに対して更新処理が終了した場合(ステップS18において「Y」)には、ブロック内における最適経路の抽出処理が終了する。ブロック内経路生成部28は、上述した最適経路の抽出処理を、継続的に(あるいは一定時間間隔)で行う。これにより、各ブロックにおける最適経路を精度良く抽出することができる。なお、上述した最適経路の抽出処理は、地図画像を構成する全てのブロックについて行われる。
【0062】
図14は、車両12からの経路探索要求に応答して最適経路を抽出する処理を示すフローチャートである。ナビゲーション装置10は、車両12より経路探索要求を受信したか否かを検出する(S20)。そして、経路探索要求を受信したことが検出されると(ステップS20において「Y」)、交通情報取得部24は、経路探索要求を発した車両の位置情報に基づき、出発点としての始点ノード及び始点ブロックの情報を、地図DB22内の情報に基づき取得する。同様に、交通情報取得部24は、経路探索要求に含まれる目的地情報に基づき、目的地としての終点ノード及び終点ブロックの情報を取得する(S21)。
【0063】
次に、全体経路探索部30は、起点・終点ブロックを含む一定範囲のブロックに対応する最適経路テーブル58を、ブロック内情報記憶部26より読み出す(S22)。そして、全体経路探索部30は、各ブロックにおける転入・転出ノード間の距離情報に基づき、ブロック単位で、起点ノードから終点ノードに至る走行経路を探索する(S23)。各ブロックで抽出された最適経路の情報に基づき、ブロック単位で走行経路を探索することができるので、各ブロック内の走行経路の探索を省略することができ、処理時間を短縮することができる。
【0064】
全体経路探索部30は、探索された走行経路情報に基づき、車両の現在地点から目的地までの走行経路を示すノード情報を生成し、ナビゲーション装置10は、通信部20を介して、目的地に至るノード情報を送信する。これにより、目的地までの走行経路の情報が、車両12に備えられたディスプレイに表示される。したがって、地図情報を備えていない車両においても、目的地までの走行経路の情報を迅速に取得することができる。
【0065】
上記実施形態では、ノード間のコストパラメータとして、リンクの距離のみを用いているが、本発明はこれに限られることはなく、道路種別(高速道路、国道、県道など)、道幅、渋滞の程度、交通量、交通規制(通行止め、速度規制等)の有無、信号機の有無、右左折の有無といった各種のパラメータを考慮して、ノード間のコストηの値を決定しても良い。これらのパラメータは、例えば、地図DB22に記憶されている道路地図や、VICS(登録商標)センター14からの交通情報に基づいて取得することができる。
【0066】
さらに、渋滞状況や交通規制の変化に応じて、リンクコストηの値を変動させても良い。この場合において、上述したフェロモン量テーブル50や移動確率テーブル52の更新処理と同じタイミングで、リンクコストテーブル54内の情報を更新することができる。これにより、交通状況の変化を反映した経路情報を抽出することができるので、経路探索の精度を向上することができる。この場合においても、ブロック毎に、転入及び転出ノード間の最適経路を算出した最適経路テーブルを備えているため、車両12からの経路要求に迅速に対応することができる。
【0067】
上記実施形態では、最適経路として、転入及び転出ノード間の最短経路を適用しているが、本発明はこれに限られることはなく、例えば、フェロモン量が最も多いノード間の組合せや、移動確率が最も高い組合せを、転入及び転出ノード間の最短経路と定めても良い。フェロモン量が多い経路、移動確率が高い経路は、多くの車両が走行する経路であり、適切な走行経路である場合が多いことから、このような経路を最適経路として定めることで、適切な走行経路を抽出することができる。
【0068】
なお、各ブロックにおける渋滞情報は、例えば、特開2007−219990号公報に記載の方法により算出された、所定時間経過後(例えば1時間後)の渋滞予測情報を用いても良い。すなわち、道路リンクごとに車両の存在量を取得し、取得された存在量を含む時間関数存在量(発生フェロモン)と時間関数伝達量(伝達フェロモン)を算出し、これら時間関数存在量及び時間関数伝達量に基づき、所定時間経過後(例えば5分後)の渋滞予測情報を求めることができる。あるいは、VICS(登録商標)サーバから送信される渋滞情報と、地図DB22に記憶された地図情報とを照合して、各リンクにおける渋滞情報を取得しても良い。
【0069】
(第2実施形態)
図15は、本発明の第2実施形態に係るナビゲーション装置70の構成を示すブロック図である。この第2実施形態に係るナビゲーション装置70は、第1実施形態と比較して、ブロック内経路生成部72が複数の経路生成ユニット74から構成される点で相違する。なお、上記第1実施形態と同じ構成部材については、同一の符番を付して詳細な説明を省略する。
【0070】
ブロック内経路生成部72は、複数の経路生成ユニット74から構成されており、個々の経路生成ユニット74は、道路地図を構成する複数のブロックのうち、少なくとも1つのブロックが割り当てられている。経路生成ユニット74は、割り当てられたブロックに対して、上記第1実施形態で説明したのと同様にして、フェロモン量テーブル50、移動確率テーブル52及び最適経路テーブル58の更新処理を行う。全体経路探索部30は、これら複数の経路生成ユニット74によって更新された最適経路テーブル58の情報に基づき、車両の位置から目的地に至る最適経路を抽出する。
【0071】
このように、複数の経路生成ユニット74により、個々のブロックにおける最適経路テーブルの更新処理を並列的に行うことで、道路地図を構成する全ブロックの最適経路テーブルの更新処理に要する時間を短縮することができる。
【0072】
(第3実施形態)
図16は、本発明の第3実施形態に係るナビゲーションシステムの構成を示すブロック図である。この第3実施形態は、第1実施形態と比較して、車両の位置から目的地に至る最適経路を抽出するナビゲーション装置80と、ブロック毎の最適経路テーブルを更新する経路生成装置82とを別個に設け、通信回線84を介して互いに接続した点で相違する。なお、上記第1実施形態と同じ構成部材については、同一の符番を付して詳細な説明を省略する。
【0073】
図17は、本発明の第3実施形態に係るナビゲーション装置80と経路生成装置82の各々の構成を示すブロック図である。ナビゲーション装置80は、第1実施形態におけるブロック内情報記憶部の代わりに最適経路記憶部86を備えており、この最適経路記憶部86は、道路地図を構成する各ブロックの転入及び転出ノードの最短経路情報及び最短距離情報(あるいは最小コスト情報)を記憶する。
【0074】
経路生成装置82は、ブロック内情報記憶部88と、経路生成ユニット89と通信部20とを備えており、ナビゲーション装置80との間で、各種の交通情報や各ブロックの最適経路情報等の情報を送受信する。経路生成装置82の各々は、道路地図を構成する複数のブロックのうち、少なくとも1つのブロックが割り当てられており、ブロック内情報記憶部88は、当該経路生成装置82に割り当てられたブロックに対する、フェロモン量テーブル、移動確率テーブル、リンクコストテーブル、エージェント経路テーブル、最適経路テーブルが設けられている。これら各種テーブルの内容については、第1実施形態で説明したのと同様であり、詳細な説明を省略する。
【0075】
経路生成ユニット89は、割り当てられたブロックに対して、上記第1実施形態で説明したのと同様にして、フェロモン量テーブル、移動確率テーブル及び最適経路テーブルの更新処理を行う。そして、更新された最適経路テーブルの情報が、通信部20を介して、ナビゲーション装置80に送信され、最適経路記憶部86に記憶される。ナビゲーション装置80の全体経路生成部30は、最適経路記憶部86に記憶された情報に基づき、車両の位置から目的地に至る最適経路を抽出する。
【0076】
このように、道路地図を構成する複数ブロックにおける最適経路の算出を、ネットワークで接続された複数の装置で行うことにより、最適経路の算出処理を分散化することができ、しかも、複数ブロックにおける処理を並列して行うことができるから、処理速度及び処理効率が向上する。
【0077】
(第4実施形態)
図18は、本発明の第4実施形態に係るナビゲーション装置90の構成を示すブロック図であり、ナビゲーション装置90は、道路上を走行する複数の車両92a〜92cと例えば無線通信回線によって接続されており、一定時間間隔で各ブロック内の最短経路情報を更新するとともに、変更された最短経路を通過する予定の車両に対して、経路再探索を促すための通知を発する。
【0078】
ナビゲーション装置90は、第1実施形態と比較して、ブロック内情報記憶部93に備えられた変化フラグテーブル96(本発明の変動情報記憶部に対応。図20参照)と、経路情報記憶部94と通知判定部98が設けられている点で相違する。なお、上記第1実施形態と同じ構成部材については、同一の符番を付して詳細な説明を省略する。
【0079】
図19,20は、渋滞や通行止めといった交通状況の変化により、ブロック内の最短経路が変化した様子を示す説明図である。ここで、図19,20では、ブロック内のノードN1とN3を結ぶ区間に渋滞が発生した場合を例にして説明するが、本発明はこれに限られない。
【0080】
図19において、ブロック(B6)のノードN1とN3を結ぶ区間に渋滞が発生し、当該区間のリンクコストが増加した結果、ノードO2からノードD2に至る最短経路が、「O2,N1,N3,D2」(符番95a)から「O2,N1,N4,D2」(符番95b)へと変化する。
【0081】
図20は、変化フラグテーブル96に記憶されたデータ構成の一例を示すものであり、最短経路が変化した入出力ノードの組合せに対して「1」が、変化していない入出力ノードの組合せに対して「0」が、それぞれ記憶される。図19において、ノードO2からノードD2に至る最短経路が変化したことから、図20の例では、当該ノードに対応する変化フラグが、「1」となっている。この変化フラグテーブル96への変化フラグの更新は、ナビゲーション装置90においてブロック毎の最短経路検索を行う毎に行われる。
【0082】
経路情報記憶部98は、ナビゲーション装置90と接続された車両が走行予定の経路情報が記憶されている。図21は、経路情報記憶部98に記憶された経路情報の一例であり、車両(クライアントID)毎に、経由するブロック(経由ブロック)と、当該経由ブロックにおける入出力ノードの情報が記憶されている。なお、図21では、図面を簡略化するために、渋滞が発生したブロックB6のみ、入出力ノードの情報を記載しているが、実際は全ての経由ブロックに対して、入出力ノードの情報が記憶されている。
【0083】
通知判定部98は、経路情報記憶部94に記憶された経路情報と、変化フラグテーブル96に記憶された変化フラグの情報を参照して、各車両の経路情報に、変化フラグが「1」となっているブロックの入出力ノードが含まれているか否かを判定する。そして、対応する入出力ノードが含まれている場合には、その車両に対してのみ、最短経路の変化を通知する。車両への通知の方法としては、ナビゲーション装置90から車両に対して一方的に通知を行う方法(周知のPUSH型)の他、一定時間毎に車両からナビゲーション装置90にアクセスした際に通知を行う方法(疑似PUSH)、車両とナビゲーション装置90との間で接続(セッション)を確立して通知を行う方法(例えば、Comet、XMPP(eXtensible Messaging and Presence Protocol))を用いることができる。
【0084】
図20,21の例では、変化フラグが「1」となった入出力ノードが、「ブロックB6:ノードO2,D2」であり、この情報は、クライアントID「2」に対応する車両の2番目の経由ブロックに該当することから、通知判定部98は、車両92bのみに対して、最短経路が変化したことを通知する。
【0085】
図22は、本実施形態に係るナビゲーション装置90の動作を示すフローチャートである。ナビゲーション装置90では、ユーザ(車両)からの経路探索要求を受けて、目的地までの経路(経由ブロック)を算出し、その結果が経路情報記憶部94に記憶されている。ナビゲーション装置90は、一定時間毎に、交通情報取得部24で取得した道路情報に基づき、各ブロックを構成するリンクのコストをアップデートする(S30)。
【0086】
ブロック内経路生成部28では、更新されたリンクコストに基づき,各ブロックにおける入出力ノードごとに、最短経路情報を検索し、最適コストテーブル58を更新する(S31)。このとき、最適コストテーブル58の内容に変更があったか否かの判定が行われ(S32)、変更があった場合には、対応する入出力ノードの変化フラグを「1」とする(S33)。
【0087】
そして、通知判定部98は、経路情報記憶部94と変化フラグテーブル96とを参照して、各車両の経路情報に、変化フラグが「1」となっているブロックの入出力ノードが含まれているか否かを判定する(S34)。そして、通知判定部98は、対応する入出力ノードが経路情報に含まれている車両に対してのみ、最短経路の変化を通知する(S35)。通知を受けた車両において、ナビゲーション装置90に対して、目的地までの経路再探索を要求する。
【0088】
このように、各ブロックの最短経路が変化した場合に、経路再探索を促す通知をナビゲーション装置から車両に通知を行うようにしたので、目的地までの走行経路のアップデートを効率よく行うことができる。また、ナビゲーション装置において不必要な経路検索が行われることがなくなるから、処理の効率化、通信コストの削減を図ることができる。
【0089】
なお、この第4実施形態において、ブロック内の最適コストテーブルの更新があった場合にのみ、最短経路の変化を通知しているが、例えばブロック内の全ての経路で渋滞が発生した場合には、ブロック内の最短経路が変化しないが、出発地から目的地に至る全体の経路については、最適経路が変化している場合がある。このため、ブロック内の最適コストテーブルが更新された場合のみならず、例えば、(ア)ブロック内の最適経路の所要時間が閾値を超えた場合、あるいは、(イ)ブロック内の全ての入出力ノードに対応する最適経路の平均値の変化が閾値を超えた場合に、目的地までの全体の最適経路が変動したとして、当該ブロックを通過する車両に対して、経路再探索を促す通知を発するようにしても良い。
【0090】
また、隣接するブロックのリンクコストが大きく低下した場合には、対象ブロックのリンクコストの変動が小さくとも、全体の最適経路は変動する。このため、対象ブロックと隣接するブロック内の最適経路の所要時間が閾値を超えて変動した場合にも、当該対象ブロックを通過する車両に対して、経路再探索を促す通知を発するようにしても良い。
【0091】
上記実施形態では、いずれも、道路地図を分割した各ブロックの最適経路情報を組み合わせることで、道路地図全体における経路情報の探索を行っているが、複数(例えば4つ)のブロック(小ブロック)を組み合わせた中ブロックを設けても良い。この場合、小ブロックにおける最適経路情報に基づき、中ブロックにおける最適経路情報を算出し、この中ブロックにおける最適経路情報に基づき、道路地図全体における経路情報を探索するようにしても良い。
【0092】
上記実施形態では、いずれも、車両に対して経路情報を提供しているが、本発明はこれに限られることはなく、例えば、歩行者が有する携帯端末に対して、目的地までの経路情報を提供するようにしても良い。
【産業上の利用可能性】
【0093】
以上説明したように、本発明によれば、目的地に至る経路探索を短時間で効率的に行うことができ、ナビゲーション装置として有用である。
【符号の説明】
【0094】
10,70,80,90 ナビゲーション装置
12,92a〜92c 車両
22 地図DB
24 交通情報取得部
26,88,93 ブロック内情報記憶部
28,72 ブロック内経路生成部
30 全体経路生成部
40 道路地図
42,44 ブロック
50 フェロモン量テーブル
52 移動確率テーブル
54 リンクコストテーブル
56 エージェント経路テーブル
58 最適経路テーブル
74,89 経路生成ユニット
82 経路生成装置
86 最適経路記憶部
94 経路情報記憶部
98 通知判定部

【特許請求の範囲】
【請求項1】
車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する情報取得部と、
道路地図を構成する複数のブロックの各々に含まれるノードの位置情報を記憶する地図情報記憶部と、
前記ブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び/または転出ノードとして定め、前記転入ノードから前記転出ノードに至る経路を示すブロック内経路情報を記憶するブロック内情報記憶部と、
個々の前記ブロックにおける、前記転入ノードから前記転出ノードに至る最適経路を探索し、探索された経路情報を前記ブロック内経路情報として更新するブロック内経路生成部と、
複数の前記ブロック内経路情報を組み合わせて、前記現在位置から前記目的地までの経路情報を生成する全体経路探索部とを備えたことを特徴とするナビゲーション装置。
【請求項2】
前記ブロック内情報記憶部は、前記転入ノードから前記転出ノードに至る経路のリンクコスト情報を、前記ブロック内経路情報と対応付けて記憶する最適経路テーブルを備えたことを特徴とする、請求項1記載のナビゲーション装置。
【請求項3】
前記ブロック内情報記憶部は、ブロック内の隣接ノード間の移動確率を示す移動確率テーブルを備え、
前記ブロック内経路生成部は、前記移動確率テーブルに記憶された移動確率に基づき、前記転入ノードから前記転出ノードに至る最適経路を探索することを特徴とする、請求項2記載のナビゲーション装置。
【請求項4】
前記ブロック内情報記憶部は、前記ブロック内のノード間のフェロモン量を示すフェロモン量テーブルと、前記ブロック内のノード間の前記リンクコストを示すリンクコストテーブルを備え、
前記ブロック内経路生成部は、所定時間毎に、前記フェロモン量テーブル及び/又は前記リンクコストテーブルを更新するとともに、前記ノード間の前記フェロモン量及び前記リンクコストに基づいて前記移動確率を更新することを特徴とする、請求項3記載のナビゲーション装置。
【請求項5】
前記車両の通過経路を示す前記転入ノード及び前記転出ノードの情報を記憶する経路情報記憶部と、前記ブロック内の経路状態が変動したことを示す変動情報を、前記転入ノード及び前記転出ノードの組合せ毎に記憶する変動情報記憶部と、経路状態が変動した前記転入ノード及び前記転出ノードの組合せを通過経路に含む前記車両に対して、経路検索を促す通知を発する通知判定部とを備えたことを特徴とする、請求項1記載のナビゲーション装置。
【請求項6】
前記変動情報は、前記転入ノードから前記転出ノードに至る最適経路が変更されたか否かを示す情報であることを特徴とする、請求項5記載のナビゲーション装置。
【請求項7】
前記全体経路探索部は、前記最適経路テーブルに記憶された前記転入ノードから前記転出ノードへの経路を1つのリンクとみなして、前記現在位置から前記目的地までの経路情報を生成することを特徴とする、請求項2ないし6のいずれか1項に記載のナビゲーション装置。
【請求項8】
前記ブロックにおける最適経路情報を更新する前記ブロック内経路生成部を複数備えたことを特徴とする、請求項1ないし7のいずれか1項に記載のナビゲーション装置。
【請求項9】
車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する情報取得ステップと、
道路地図を構成する複数のブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び/または転出ノードとして定め、前記転入ノードから前記転出ノードに至る経路を示すブロック内経路情報を記憶するブロック内情報記憶ステップと、
個々の前記ブロックにおける、前記転入ノードから前記転出ノードに至る最適経路を探索し、探索された経路情報を前記ブロック内経路情報として更新するブロック内経路生成ステップと、
複数の前記ブロック内経路情報を組み合わせて、前記現在位置から前記目的地までの経路情報を生成する全体経路探索ステップを備えたことを特徴とするナビゲーション方法。
【請求項10】
道路地図を複数のブロックに分割するとともに、分割された各ブロック内における最適経路情報を生成する複数の経路生成装置と、前記経路生成装置と接続されたナビゲーション装置を有するナビゲーションシステムにおいて、
前記ナビゲーション装置は、
車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する情報取得部と、
道路地図を構成する複数のブロックの各々に含まれるノードの位置情報を記憶する地図情報記憶部と、
前記ブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び/または転出ノードとして定め、前記転入ノードから前記転出ノードへの最適経路を示すブロック内最適経路情報を記憶する最適経路記憶部と、
複数の前記ブロック内経路情報を組み合わせて、前記現在位置から前記目的地までの経路情報を生成する全体経路探索部を備え、
前記経路生成装置は、
前記ブロックの各々について、前記転入ノードから前記転出ノードに至る経路を示すブロック内経路情報を記憶するブロック内情報記憶部と、
個々の前記ブロックにおける、前記転入ノードから前記転出ノードに至る最適経路を探索し、探索された経路情報を前記ブロック内経路情報として更新するブロック内経路生成部とを備え、
前記ナビゲーション装置は、前記ブロック内経路生成部で探索された前記経路情報に基づき、前記ブロック内最適経路情報を更新することを特徴とするナビゲーションシステム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate


【公開番号】特開2012−215571(P2012−215571A)
【公開日】平成24年11月8日(2012.11.8)
【国際特許分類】
【出願番号】特願2012−66696(P2012−66696)
【出願日】平成24年3月23日(2012.3.23)
【出願人】(502324066)株式会社デンソーアイティーラボラトリ (332)
【Fターム(参考)】