地図データ作成方法及び経路探索方法並びに装置
【目的】探索した経路品位を保ち、かつ経路探索を高速化する「地図データ作成方法及び経路探索方法並びに装置」を提供することである。
【構成】詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法において、所定レベルにおける任意の２つのメッシュM1,M2の組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定するデータを探索範囲情報として地図データに含める。ナビゲーション装置は経路探索に際してこの探索範囲情報を使用する。
【構成】詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法において、所定レベルにおける任意の２つのメッシュM1,M2の組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定するデータを探索範囲情報として地図データに含める。ナビゲーション装置は経路探索に際してこの探索範囲情報を使用する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データ作成方法及び経路探索方法並びに装置に係わり、特に詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法及び経路探索方法並びに該方法を実現する装置に関する。
【背景技術】
【０００２】
ナビゲーション装置は、車両の現在位置に応じた地図データをCD−ROM、DVD，HDDなどの地図記憶媒体から読み出してディスプレイ画面に描画すると共に、車両マークをディスプレイ画面の一定位置に固定表示し、走行に応じて地図をスクロ−ル表示する。また、ナビゲーション装置は以上に加えて、出発地から目的地に到る誘導経路あるいは出発地から指定された経由点を経由して目的地に到る誘導経路を探索し、該誘導経路を地図上に表示する経路誘導機能を備えている。かかる経路探索を高速に行う第１従来技術として、メッシュからメッシュへの専用のネットワークを地図データに格納し、該専用ネットワークを用いて探索枝数を減らし、探索の高速化を行なう方法がある（特許文献１）。又、第２の従来技術として、専用ネットワークを用いずに、階層化構造を有する地図データを用いて、階層型の探索を行う方法がある（特許文献２）。
【０００３】
第１従来技術は、図１５の（Ａ）に示すように、詳細度に応じて５つのレベルを設け、各レベルの道路情報と専用ネットワーク情報により地図の道路情報を構成している。各レベルの基本部は該レベルに応じた領域に存在する道路の道路情報を特定する部分であり、レベル１及びレベル２の拡張部は高速探索用の情報部分である。専用ネットワークは、任意の２つのレベル２領域の組み合わせに対応させて、これら２つのレベル２領域間を接続ずる経路を探索する必要な経路情報(リンクやノード情報)を保持している。
図１５の（Ｂ）に示すように出発地Sが特定されると、該出発地が含まれるレベル１領域A１と該レベル１領域A１が含まれるレベル２領域Ｃ１を特定する。同様に、目的地Ｅが特定されると、該目的地が含まれるレベル１領域Ａ２と該レベル１領域Ａ２が含まれるレベル２領域Ｃ２を特定する。専用ネットワーク情報は、これら２つのレベル２領域Ｃ１，Ｃ２の組み合わせに応じて設けられているから、該専用ネットワーク情報を用いて経路探索を行う。具体的には、出発地と目的地に対応する上位移行ノードＰ１１，Ｐ１２，Ｐ１３；Ｑ１１，Ｑ１２，Ｑ１３を、レベル１の地図情報及び専用ネットワークの拡張情報を用いて抽出する。ついで、上位移行ノードに対応する上位ノードＮ１１，Ｎ１２，Ｎ１３と上位ノード１１，Ｍ１２，Ｍ１３間の複数の経路を専用ネットワーク情報(リンクやノード情報)を用いて探索し、最小コストの経路を誘導経路として決定する。
【０００４】
第２従来技術は、図１６に示すように地図をレベル１−４に階層化して道路情報を構成している。レベル1は誘導経路対象道路と非誘導経路対象道路（細街路）の地図情報を特定する部分、レベル2は誘導経路対象道路の道路情報を特定する部分、レベル３は主要道路の地図情報を特定する部分、レベル４は更に主要な道路(県道、国道、高速道路)の地図情報を特定する部分である。出発地Sおよび目的地Ｅが特定されると、レベル２において出発地Ｓからレベル３の上位ノードに移行するノードｂ１０を求め、ついで、ノードｂ１０からレベル４の上位ノードに移行するノードｃ１０を求め、出発地Sから上位ノードｃ１０に到る経路を求める。同様に、目的地Ｅより最上位レベル４の上位ノードＣ２０に到る経路をもとめる。ついで、出発地側の上位ノードｃ１０から目的地側の上位ノードｃ２０へ到る経路をレベル４の道路情報を用いて探索し、最終的に出発地から目的地へ到るコスト最小の経路を探索する。
【特許文献１】特開２００３−３３７０３４号公報
【特許文献２】特開２００４−２８６５２４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
第１従来技術では、専用ネットワークの数が非常に多いので、道路情報のデータサイズが大きくなる問題がある。ま地図データの更新を、差分データを作成して行う場合、専用ネットワーク情報の差分データ量が大きくなってしまい、該差分データを通信で取得するには通信時間が非常に長くなって通信コストが高くなり、また、地図更新時間が長くなる問題がある。
第２従来技術の階層化構造の探索では、ヒューリスティックコストをかけ、出来るだけ無駄に探索枝をのばさないで目的地までの最適解を得る方法が存在する。しかし、それでも余計に探索枝がのびてしまい、探索時間が長くなる問題がある。図１７は、東京駅→大阪駅の経路探索における探索枝ののびかたを示すもので、塗りつぶし部分が探索枝がのびたところを示している。
以上から、本発明の目的は、探索した経路品位を保ち、かつ経路探索を高速化することである。
【課題を解決するための手段】
【０００６】
・地図データ作成方法
上記課題は本発明によれば、詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法において、所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として作成して地図データに含めることにより達成される。
前記探索範囲情報を作成するための第１の方法は、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するステップ、任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索するステップ、探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記探索範囲情報を作成するステップを有している。
前記探索範囲情報を作成するための第１の方法は、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するステップ、任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求めるステップ、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求めるステップ、前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成するステップを有している。
・経路探索方法
上記課題は本発明によれば、目的地までの経路を探索するナビゲーション装置の経路探索方法により達成される。本発明の経路探索方法は、(1)詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、最上位レベルの次のレベル(準最上位レベル)における任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定するデータを探索範囲情報とし、該探索範囲情報を各レベルのメッシュ毎の道路情報と共に地図データに含め、更に、最上位レベルの道路情報を構成するリンクが前記準最上位レベルのメッシュをまたがらないようにすると共に該リンクのリンクレコードに該リンクが存在する前記準最上位レベルのメッシュの識別データを含ませるステップ、(2)最上位レベルのノード間の経路探索に際して、前記探索範囲情報により経路探索に使用するとされたメッシュのメッシュ識別データを有する最上レベルリンクを用いて経路探索を行うステップ、を有している。
【０００７】
・地図データ作成装置、
また、上記課題は本発明によれば、詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成装置により達成される。
本発明の第１の地図データ作成装置は、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索する探索部、探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部を備えている。
本発明の第２の地図データ作成装置は、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照して前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求める経路探索部、前記各経路を構成するリンクが属するメッシュを特定するデータにより、前記第１のメッシュから第２のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部を備えている。
【０００８】
・ナビゲーション装置、
また、上記課題は本発明によれば目的地までの経路を探索するナビゲーション装置により達成される。本発明のナビゲーション装置は、(１) 上位レベルの次のレベル(準最上位レベル)における任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定するデータを探索範囲情報とし、該探索範囲情報を各レベルのメッシュ毎の道路情報と共に地図データに含め、更に、最上位レベルの道路情報を構成するリンクが前記準最上位レベルのメッシュをまたがらないようにすると共に該リンクのリンクレコードに該リンクが存在する準最上位レベルのメッシュの識別データを含ませてなる地図データを記憶する地図データ記憶部、(2)目的地を設定する目的地設定部、(3)出発地側及び目的地側の最上位レベルのノードを求め、該ノード間の経路探索に際して、前記探索範囲情報により経路探索に際して使用するとされているメッシュのメッシュ番号を有する最上位レベルのリンクを用いて経路探索を行う経路探索部を備えている。
【発明の効果】
【０００９】
本発明によれば、所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含めるようにしたから、該探索範囲情報を用いることにより探索範囲を狭めることができ、高速の経路探索が可能になった。
又、本発明によれば、探索範囲情報として探索すべきメッシュの識別データを保存するだけでよいため、該探索範囲情報のサイズを少なくでき、しかも、地図更新時における差分データサイズを小さくできる。
又、本発明によれば、任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求め、前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成するようにしたから、高速に探索範囲データを作成することができるようになった。
【発明を実施するための最良の形態】
【００１０】
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法において、所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含める。
この探索範囲情報は、以下のように作成する。第１の探索範囲情報作成方法では、(1) メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、(2)任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索し、(3)探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記探索範囲情報を作成する。
第２の探索範囲情報作成方法では、（1）任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、(2)同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求め、(3)前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成する。
【実施例】
【００１１】
(Ａ)本発明の概要
図１は本発明の地図データに含まれる道路情報の説明図である。詳細度に応じて複数のレベル(レベル１〜レベル４)を設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報RI1〜RI4と、経路探索に際して利用する探索範囲データSRDとで道路情報を構成する。
レベル1は誘導経路対象道路と非誘導経路対象道路の地図情報を特定する部分、レベル2は誘導経路対象道路の道路情報を特定する部分、レベル３は主要道路の地図情報を特定する部分、レベル４は更に主要な道路(県道、国道、高速道路)の地図情報を特定する部分である。
探索範囲データSRDは、図２に示すように、所定レベル(例えばレベル３)における任意の２つのメッシュM1,M2の組み合わせ毎に、一方のメッシュM1から他方のメッシュM2に到る経路を探索する際に使用するメッシュ(太枠線内のメッシュ)を特定するデータを探索範囲データとして地図データに含める。
この探索範囲データSRDは、例えば、以下のように作成する。(１)各メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、(２)任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路PT1，PT2，…を探索し、(３)探索された各経路を構成するリンクが属するメッシュを特定するデータにより、該２つのメッシュの組み合わせに応じた探索範囲データとし、全てのメッシュの組み合わせについて探索範囲データを作成する。
【００１２】
図３はメッシュの一例の説明図である。地図はカバーするエリアの広さからレベル４のメッシュ，レベル３のメッシュ、レベル３のメッシュ、レベル２のメッシュ、レベル１のメッシュと階層化されている。レベル４のメッシュに相当する領域Ｒ４は、複数(図では４つ)のレベル３メッシュの領域Ｒ３で構成され、同様に、レベル３のメッシュに相当する領域Ｒ３は、４つのレベル２メッシュの領域Ｒ２で構成され、レベル２のメッシュに相当する領域Ｒ２は、４つのレベル１メッシュの領域Ｒ１で構成されている。
【００１３】
図４は道路情報に含まれるリンクレコードの構成説明図である。リンクとは交差点から交差点までの道路部分であり、リンクレコードは、（Ａ）に示すように(1)リンクID、(2)道路種別、(3)リンク距離、(4)車線数、(5)リンク形状を特定する形状情報(始点ノード、中間のノード、終点ノードの位置データ)を有している。各リンクレコードはメッシュ番号に対応させて地図に含まれており、リンクが属するメッシュのメッシュ番号がわかるようになっている。また、レベル４のリンクはレベル３領域Ｒ３をまたがらないように形成されており、該レベル４のリンクレコードには図４(Ｂ)に示すようにレベル３領域のメッシュ番号が含まれている。
図５はレベル４のリンクがレベル３領域をまたがらないように形成することを説明する説明図であり、交差点Ｎ１，Ｎ２を始点、終点とするリンクLKがレベル３領域R3a，R3bを横切っている。かかる場合、リンクLKをレベル３領域Ｒ３の境界線で二分し、二分された２つのリンクLK1（N1−NB），LK2（NB−N2）をレベル４のリンクとし、夫々についてリンクレコードを作成し、それぞれにレベル３領域R3a．R3bのメッシュ番号を持たせる。
【００１４】
（Ｂ）探索データ作成
図６は本発明の地図作成装置の要部構成図、図７は本発明の地図作成処理説明図である。
リンクデータ入力部１はレベル３メッシュのリンクレコードをリスト作成部２と経路探索部３に入力する。リスト作成部２は、レベル３メッシュのリンクレコードを参照し、全レベル３メッシュについて、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成する。図７（A）は、境界脱出リンクの説明図であり、レベル３メッシュの着目領域R3から隣接メッシュへ移動する際に通る境界リンクS1〜S6が境界脱出リンクである。図７（B）は、境界進入リンクの説明図であり、隣接メッシュからレベル３メッシュの着目領域R3へ進入する際に通る境界リンクE1〜E6が境界進入リンクである
経路探索部３は、任意の２つのレベル３メッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクS1〜S6から他方のメッシュの各境界進入リンクE1〜E6に到る全経路を所定の経路探索方法により、例えばダイクストラ法により探索する。すなわち、図7(C),(D)に示すように経路探索部３は、
・境界脱出リンクS1から各境界進入リンクE1〜E6に到る全経路、
・境界脱出リンクS2から各境界進入リンクE1〜E6に到る全経路、
・境界脱出リンクS3から各境界進入リンクE1〜E6に到る全経路、
・・・・・・・
・境界脱出リンクS6から各境界進入リンクE1〜E6に到る全経路、
を探索する。
【００１５】
探索範囲データ作成部４は、経路探索部３により探索された上記の各経路を構成するレベル３リンクが属するレベル３メッシュのメッシュ番号を記憶することにより、任意の2つのレベル3メッシュの組み合わせに対応させて探索範囲データを作成してメモリ５に保存する。なお、探索範囲データを保存するために、任意の２つのメッシュの組み合わせに対応させてメモリ５にKバイトを用意し、Kバイトの各ビットにより上記経路を構成するリンクが所定のメッシュに含まれているか否かを記録する。すなわち、Kバイトの第1ビット〜第8×Kビットをメッシュ番号１〜メッシュ番号8×Kに対応させ、上記経路を構成するリンクが所定のメッシュに属する場合には、該メッシュに対応するビットに”1”を記入し、これにより探索範囲データを作成して保存する。全てのメッシュの組み合わせに対して上記処理を行って、探索範囲データをメモリ５に保存する。
地図データ作成部６は各レベルの道路情報および前記作成された探索範囲データを用いて道路レイヤ情報を作成してたとえばDVD ７に記録する。
【００１６】
（C）経路探索法
・ダイクストラ法
図８はコストを距離とした場合のダイクストラ法の概略説明図で、道路を直線、交差点を直線の交点としてグラフ化したものである。各交差点間の距離は既知で、Ｐsは出発点(自車位置)、Ｐdは目的地である。ダイクストラ法では、出発地Ｐsに隣接する１次交差点Ａ1〜Ａ4を求め、各１次交差点Ａ1〜Ａ4に対応させて０次の交差点（出発点）及び出発点からの距離を記憶する。ついで、各１次交差点Ａ1〜Ａ4について２次交差点Ｂijを求め、各２次交差点に対応させて１次交差点を経由する出発点からの距離を求めて記憶する。例えば、１次交差点Ａ1については３つの２次交差点Ｂ11，Ｂ12，Ｂ13が求まり、各２次交差点Ｂ11，Ｂ12，Ｂ13に対応させて、
Ｂ11：１次交差点Ａ1を経由する出発点からの距離d11
Ｂ12：１次交差点Ａ1を経由する出発点からの距離d12
Ｂ13：１次交差点Ａ1を経由する出発点からの距離d13・・・・(a)
を記憶する。又、1次交差点Ａ2について３つの２次交差点Ｂ21，Ｂ22，Ｂ23が求まり、各２次交差点Ｂ21，Ｂ22，Ｂ23に対応させて、
Ｂ21：１次交差点Ａ2を経由する出発点からの距離d21 ・・・・（b）
Ｂ22：１次交差点Ａ2を経由する出発点からの距離d22
Ｂ23：１次交差点Ａ2を経由する出発点からの距離d23
を記憶し、他の１次交差点Ａ3，Ａ4についても同様に２次交差点を求めて所定のデータを記憶する。
ところで、交差点Ｂ13とＢ21は同一の交差点である。このように、データを記憶すべき交差点が重複すると、出発点からの距離d13とd21の大小を比較し、小さい方のデータのみを記憶する。たとえば、d13＞ｄ21であれば、交差点Ｂ13（＝Ｂ21)のデータとして(b)のデータが最終的に記憶される。
以後、同様に、各２次交差点について３次交差点Ｃijを求め、各３次交差点に対応させて２次交差点を経由する出発点からの距離を求めて記憶し、一般に各第ｉ次交差点について第(i+1)次交差点を求め、各第(i+1)次交差点に対応させて第ｉ次交差点を経由する出発点からの累計距離を求めて記憶してゆけば、最終的に目的点Ｐｄに到達する。以上はノードに着目してダイクストラ法を説明したがリンクに着目して説明することもできる。
【００１７】
・ダイクストラ法を用いた経路探索処理
図９はダイクストラ法を用いた経路探索処理のフローであり、距離をコストとする場合であり、目的地が存在するメッシュを目的側メッシュ、出発地が存在するメッシュを出発側メッシュという。
所定の出発側メッシュの第j境界脱出リンクを選択し、該リンクの検索次数nを１にし（１→ｎ、ステップ１０１）、第ｎ次リンクに接続するリンクが存在するか調べる（ステップ１０２）。１次リンクは出発点Ｐsに接続するリンクである。第次ｎリンクLnに接続するリンク(隣接リンクという)が存在すれば、出発点Ｐsから第ｎ次リンクLnを経由して隣接リンクLajの終端までの累計距離Ｄを計算する（ステップ１０３）。
出発点から第ｎ次リンクの終点までの距離ｄnは後述するように、該第次ｎリンクに対応させて記憶に記憶してあり、また隣接リンクLajの距離dajはリンクレコードに記憶してあるから、次式
ｄn＋ｄaj→Ｄ
により出発点Ｐsから隣接リンクLajの終点までの累計距離Ｄが求まる。
ついで、隣接リンクLajの検索次数が(n+1)かチェックし（ステップ１０４）、(n+1)でなければ、隣接リンクLajに対応させて、以下のデータ
(1) 現在着目している第ｎ次リンクのシ−ケンシャル番号、
(2) 出発点から当該隣接リンクLajの終点までの累計距離Ｄ、
(3) 当該隣接リンクLaj の検索次数として(n+1)、
(4) メッシュ３番号
(5) リンクLajのリンク番号
を記憶部に記憶し（ステップ１０５）、以後、ステップ１０２に戻り、着目している第ｎ次リンクに接続するリンクが、なお残存するか調べて以降の処理を繰り返す。
一方、ステップ１０４において、隣接リンクの次数が(n+1)の場合には、換言すれば、該隣接リンクが別の第ｎ次リンクに隣接するリンクとして参照されていれば（ステップ１０５で既に上記(1)〜(5) のデータが記憶されていれば）、該隣接リンクに対応して記憶してある出発点からの距離D′とステップ１０３で求めた距離Dの大小を比較する（ステップ１０６）。D＜D′であれば、当該隣接リンクLajに対応して記憶部に記憶してある、第ｎ次リンクのシ−ケンシャル番号を現在着目している第ｎ次リンクのシ−ケンシャル番号で置き換えると共に、累計距離Ｄ′をＤで書き替え（Ｄ→Ｄ′，ステップ１０７）、以後、ステップ１０２に戻り、着目している第ｎ次リンクに接続するリンクが、なお残存するか調べて以降の処理を繰り返す。又、D≧D′の場合には、当該隣接リンクに対応して記憶部に記憶してある内容を変更せずステップ１０２に戻る。
【００１８】
ステップ１０２において、着目している第ｎ次リンクに接続するリンクが存在しなくなれば、別の第ｎ次リンクが存在するか調べ（ステップ１０８）、存在すれば、該別の第ｎ次リンクを新たに第ｎ次リンクとして（ステップ１０９）、ステップ１０２以降の処理を繰り返す。ステップ１０８において、別の第ｎ次リンクが存在しなければ、目的側メッシュの進入リンクに到達したかチェックし(ステップ１１０)、到達していなければ検索次数を１つ歩進し（ｎ＋１→ｎ，ステップ１１１）、ステップ１０２以降の処理を繰り返す。しかし、目的側メッシュの進入リンクに到達していれば、探索処理を終了する。以上では、距離をコストとみなした場合であるが、コストが距離以外の要素をも含む場合には距離の代わりにコストＣを用いることができる。
以上により、探索処理が完了後、目的側メッシュにおける所定の境界進入リンクに着目し、
(1)該境界進入リンク（M次のリンクとする）→(2)該境界進入リンクに対応させて記憶してある（M−１）次のリンク→(3)該（M−１）次のリンクに対応させて記憶してある（M−２）次のリンク→・・・→(4)2次のリンクに対応させて記憶してある１次リンク（第i目的側メッシュの第j境界脱出リンク）
と順次接続することにより、１次リンクである第i目的側メッシュの第j境界脱出リンクから目的側メッシュにおける所定の境界進入リンクに到るコスト(距離)最小の経路をもとめることができる。
なお、後述する図１０の探索範囲データ作成処理フローのステップ２０８では、上記求めた経路を構成するリンクのメッシュ３番号に対応するビットを“１”にして探索範囲データを作成する。
また、図１１の第２の探索範囲データ作成処理フローのステップ３０３の探索処理では、上記ステップ１１０において探索枝を延ばせるか判別し、探索枝を延ばせれば検索次数を１つ歩進し（ｎ＋１→ｎ，ステップ１１１）、ステップ１０２以降の処理を繰り返す。しかし、探索枝を延ばせず、探索が不可能になれば探索処理を終了する。
【００１９】
（D）探索範囲データの作成処理
・第１の探索範囲データ作成処理
図１０は本発明の第１の探索範囲データ作成処理フローである。
まず、レベル３メッシュのリンクレコードを参照し、全レベル３メッシュについて、メッシュ毎に該メッシュから隣接メッシュへ脱出する境界脱出リンクのリストを作成し(ステップ２０１)、ついで、該メッシュに隣接メッシュから進入する境界進入リンクのリストを作成する(ステップ２０２)。
ついで、出発側メッシュ番号を示すi、目的側メッシュ番号を示すk、出発側メッシュにおける境界脱出リンク番号を示すj、目的側メッシュにおける境界進入リンク番号を示すmをすべて１に初期化する(ステップ２０３〜２０６)。
ついで、第i出発側メッシュの第j境界脱出リンクから第k目的側メッシュの第m境界進入リンクまでの経路を探索する(ステップ２０７)。なお、i=kの場合にはステップ２０７以降の処理を行わない。
経路探索処理が終了すれば、第m境界進入リンクから逆方向にたどって第j境界脱出リンクに至る経路が通過するメッシュのメッシュ対応ビットを“1”にする(ステップ２０８)。しかる後、第k目的側メッシュの全境界進入リンクまでの経路探索が完了したかチェックし(ステップ２０９)、完了してなければmを歩進して(m＝m+1,ステップ２１０)、ステップ２０７以降の処理を繰り返す。
ステップ２０９において、第k目的側メッシュの全境界進入リンクまでの経路探索が完了すれば、第i出発側メッシュの全境界脱出リンクからの経路探索が完了したかチェックし(ステップ２１１)、完了してなければｊを歩進して(ｊ＝ｊ+1,ステップ２１２)、ステップ２０６以降の処理を繰り返す。ステップ２１１において、第i出発側メッシュの全境界脱出リンクからの経路探索が完了すれば、メッシュ番号(i,k)の組み合わせに対応する探索範囲データの作成が完了する。
ついで、全目的側メッシュについて上記処理が終了したかチェックし(ステップ２１３)、終了してなければkを歩進して(k＝k+1,ステップ２１４)、ステップ２０５以降の処理を繰り返す。ステップ２１３において、全目的側メッシュについて上記処理が終了すれば、第i出発側メッシュから他の全目的側メッシュに対する探索範囲データの作成が完了する。
しかる後、全出発側メッシュについて上記処理が終了したかチェックし(ステップ２１５)、終了してなければiを歩進して(i＝i+1,ステップ２１６)、ステップ２０４以降の処理を繰り返す。ステップ２１５において、全出発側メッシュについて上記処理が終了すれば、探索範囲データの作成が完了する。
【００２０】
・第２の探索範囲データ作成処理
図１１は本発明の第２の探索範囲データ作成処理フローである。なお、各メッシュの境界脱出リンクおよび境界進入リンクのリストの作成は完了しているものとする。
まず、出発側メッシュ番号を示すi、出発側メッシュにおける境界脱出リンク番号を示すjを１に初期化する(ステップ３０１〜３０２)。
ついで、第i出発側メッシュの第j境界脱出リンクからダイクストラ法を用いて経路探索処理を探索が不可能となるまで、すなわち、探索枝を延ばせなくなるまで行う(ステップ３０３)。探索終了後、目的側メッシュ番号を示すk、目的側メッシュにおける境界進入リンク番号を示す番号mをそれぞれ１に初期化する(ステップ３０４〜３０５)。
ついで、第k目的側メッシュの第m境界進入リンクから逆方向にたどって第i出発側メッシュの第j境界脱出リンクに至る経路が通過するメッシュのメッシュ対応ビットを“1”にする(ステップ３０６)。しかる後、第k目的側メッシュの全境界進入リンクについてステップ３０６の処理が完了したかチェックし(ステップ３０７)、完了してなければmを歩進して(m＝m+1,ステップ３０８)、ステップ３０６以降の処理を繰り返す。
ステップ３０７において、第k目的側メッシュの全境界進入リンクについてステップ３０６の処理が完了すれば、全目的側メッシュについて上記処理が終了したかチェックし(ステップ３０９)、終了してなければkを歩進して(k＝k+1,ステップ３１０)、ステップ３０５以降の処理を繰り返す。
ステップ３０９において、全目的側メッシュについて上記処理が終了すれば、第i出発側メッシュの第ｊ境界脱出リンクから全目的側メッシュの全境界脱出リンクに至る探索範囲データの作成が完了する。ついで、第i出発側メッシュの全境界脱出リンクについて上記処理が完了したかチェックし(ステップ３１１)、完了してなければｊを歩進して(ｊ＝ｊ+1,ステップ３１２)、ステップ３０３以降の処理を繰り返す。
ステップ３１１において、第i出発側メッシュの全境界脱出リンクからの経路探索が完了すれば、メッシュ番号iのメッシュと他のすべてのメッシュとの組み合わせに対応する探索範囲データの作成が完了する。
ついで、全出発側メッシュについて上記処理が終了したかチェックし(ステップ３１３)、終了してなければiを歩進して(i＝i+1,ステップ３１４)、ステップ３０２以降の処理を繰り返す。ステップ３１３において、全出発側メッシュについて上記処理が終了すれば、探索範囲データの作成が完了する。
【００２１】
（E）ナビゲーション装置
図１２は本発明のナビゲーション装置の構成図である。
地図記録媒体(CD-ROM、DVDなど）１１には図６の地図作成装置が作成した地図データが記録されており、必要に応じて読み取られるようになっている。操作部１２はナビゲーション制御装置１０を操作するものでリモコン、操作用のハードキーなどを有している。GPS受信機１３はGPS衛星から送られてくるGPS信号を受信し、車両の絶対的現在位置(GPS位置)や進行方向を算出し、自立航法センサー部１４は、所定時間毎に進行方向変化および走行距離を検出してナビゲーション制御装置１０に入力する。
タッチパネル式ディスプレイ装置１５はナビゲーション制御装置１０からの指示に従って車両周辺地図、誘導経路、メニュー、車両位置マーク等を表示する。また、タッチパネル式ディスプレイ装置１５は、スクリーンに表示したソフトキーが押下されたとき所定のコマンドをナビゲーション制御装置１０に入力するようになっている。
ナビゲーション制御装置１０において、位置推定制御部２０はGPS受信機１３及び自立航法センサー部１４からの信号に基づいて車両位置を推定してナビゲーション制御部２２に入力する。地図バッファ２１は地図記録媒体から読み取った地図データを保存する。ナビゲーション制御部２２は、図示しないが、入力される各種情報、コマンドに基づいて、車両位置周辺の地図データを地図バッファ２１に読み出す地図読み出し制御部、誘導経路探索制御及び経路誘導制御を実行する誘導経路制御部、各種操作画面、車両マークの発生制御を実行する操作画面発生制御部などを有している。
地図描画部２３は地図バッファ２１に読み出された地図データを用いて地図画像を生成してVRAM ２４に書込み、画像読み出し部２５は制御部２２からの指示に従ってVRAM ２４から所定の画像部分を切り取って画像合成部２６に入力する。
誘導経路メモリ２７は、制御部２２の誘導経路制御部により探索された目的地までの誘導経路情報、すなわち、誘導経路を構成する全リンクデータを出発地から目的地まで記録する。誘導経路描画部２８は誘導経路情報を用いて誘導経路画像を発生して画像合成部２６に入力し、描画地図上に強調表示する。操作画面発生部２９は各種メニュー画面(操作画面)を生成して画像合成部２６に入力し、マーク発生部３０は車両位置マークやカーソル等の各種マークを生成して画像合成部26に入力する。画像合成部２６は、VRAM ２４から読み出した地図画像に各種マークや誘導経路画像を重ね合わせてスクリーン全体に表示する。
【００２２】
（F）誘導経路探索
図１３は出発地と目的地が特定された際の本発明の誘導経路探索処理フローである。
レベル１メッシュの出発地からレベル４のメッシュのリンクまでの経路を探索する(ステップ４０１)。同様に、レベル１メッシュの目的地からレベル４のメッシュのリンクまでの経路を探索する(ステップ４０２)。ついで、レベル４メッシュの出発側リンクおよびレベル４メッシュの目的側リンクがそれぞれ存在するレベル３メッシュ番号を求める(ステップ４０３)。この求めたレベル３メッシュの組み合わせにより、経路探索に際してどの探索範囲データを使用するかがわかる。
しかる後、該探索範囲データを参照しつつ、レベル４の道路情報(リンクレコード)を用いて出発地から目的地までの経路を探索する(ステップ４０４)。すなわち、経路探索に際して、レベル４リンクのリンクレコードに含まれるレベル３メッシュ番号に対応する探索範囲データのビット位置を参照し(図１４参照)、“１”(オン)であれば、該レベル４リンクは経路探索対象リンクであるとみなして該リンクを用いて経路探索処理を行い、“０”(オフ)であれば、該レベル４リンクは経路探索対象リンクでないとみなして経路探索に使用しない。
ステップ４０１においてレベル１の出発地からレベル４メッシュのリンクまでの経路は複数見つかるから、夫々について出発地から目的地までの経路を探索し、最小コストの経路を誘導経路として取得する(ステップ４０５)。
以上本発明によれば階層型探索において、探索範囲を経路品位に影響する事無く絞り込む事が出来て、探索時間を削減する事が出来る。
【図面の簡単な説明】
【００２３】
【図１】本発明の地図データに含まれる道路情報の説明図である。
【図２】探索範囲データSRDの説明図である。
【図３】図３はメッシュの一例説明図である。
【図４】道路情報に含まれるリンクレコードの構成説明図である。
【図５】レベル４のリンクがレベル３領域をまたがらないように形成することを説明する説明図である。
【図６】本発明の地図作成装置の要部構成図である。
【図７】本発明の地図作成処理説明図である。
【図８】コストを距離とした場合のダイクストラ法の概略説明図である。
【図９】ダイクストラ法を用いた経路探索処理のフローである。
【図１０】本発明の第１の探索範囲データ作成処理フローである。
【図１１】本発明の第２の探索範囲データ作成処理フローである。
【図１２】本発明のナビゲーション装置の構成図である。
【図１３】出発地と目的地が入力された際の本発明の誘導経路探索処理フローである。
【図１４】レベル４リンクを経路探索に使用するか否かを判断する説明図である。
【図１５】第１従来技術説明図である。
【図１６】第２従来技術説明図である。
【図１７】第２従来技術の問題点説明図である。
【符号の説明】
【００２４】
１ リンクデータ入力部
２ リスト作成部
３ 経路探索部
４ 探索範囲データ作成部
５ メモリ
６ 地図データ作成部
７ DVD
【技術分野】
【０００１】
本発明は、地図データ作成方法及び経路探索方法並びに装置に係わり、特に詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法及び経路探索方法並びに該方法を実現する装置に関する。
【背景技術】
【０００２】
ナビゲーション装置は、車両の現在位置に応じた地図データをCD−ROM、DVD，HDDなどの地図記憶媒体から読み出してディスプレイ画面に描画すると共に、車両マークをディスプレイ画面の一定位置に固定表示し、走行に応じて地図をスクロ−ル表示する。また、ナビゲーション装置は以上に加えて、出発地から目的地に到る誘導経路あるいは出発地から指定された経由点を経由して目的地に到る誘導経路を探索し、該誘導経路を地図上に表示する経路誘導機能を備えている。かかる経路探索を高速に行う第１従来技術として、メッシュからメッシュへの専用のネットワークを地図データに格納し、該専用ネットワークを用いて探索枝数を減らし、探索の高速化を行なう方法がある（特許文献１）。又、第２の従来技術として、専用ネットワークを用いずに、階層化構造を有する地図データを用いて、階層型の探索を行う方法がある（特許文献２）。
【０００３】
第１従来技術は、図１５の（Ａ）に示すように、詳細度に応じて５つのレベルを設け、各レベルの道路情報と専用ネットワーク情報により地図の道路情報を構成している。各レベルの基本部は該レベルに応じた領域に存在する道路の道路情報を特定する部分であり、レベル１及びレベル２の拡張部は高速探索用の情報部分である。専用ネットワークは、任意の２つのレベル２領域の組み合わせに対応させて、これら２つのレベル２領域間を接続ずる経路を探索する必要な経路情報(リンクやノード情報)を保持している。
図１５の（Ｂ）に示すように出発地Sが特定されると、該出発地が含まれるレベル１領域A１と該レベル１領域A１が含まれるレベル２領域Ｃ１を特定する。同様に、目的地Ｅが特定されると、該目的地が含まれるレベル１領域Ａ２と該レベル１領域Ａ２が含まれるレベル２領域Ｃ２を特定する。専用ネットワーク情報は、これら２つのレベル２領域Ｃ１，Ｃ２の組み合わせに応じて設けられているから、該専用ネットワーク情報を用いて経路探索を行う。具体的には、出発地と目的地に対応する上位移行ノードＰ１１，Ｐ１２，Ｐ１３；Ｑ１１，Ｑ１２，Ｑ１３を、レベル１の地図情報及び専用ネットワークの拡張情報を用いて抽出する。ついで、上位移行ノードに対応する上位ノードＮ１１，Ｎ１２，Ｎ１３と上位ノード１１，Ｍ１２，Ｍ１３間の複数の経路を専用ネットワーク情報(リンクやノード情報)を用いて探索し、最小コストの経路を誘導経路として決定する。
【０００４】
第２従来技術は、図１６に示すように地図をレベル１−４に階層化して道路情報を構成している。レベル1は誘導経路対象道路と非誘導経路対象道路（細街路）の地図情報を特定する部分、レベル2は誘導経路対象道路の道路情報を特定する部分、レベル３は主要道路の地図情報を特定する部分、レベル４は更に主要な道路(県道、国道、高速道路)の地図情報を特定する部分である。出発地Sおよび目的地Ｅが特定されると、レベル２において出発地Ｓからレベル３の上位ノードに移行するノードｂ１０を求め、ついで、ノードｂ１０からレベル４の上位ノードに移行するノードｃ１０を求め、出発地Sから上位ノードｃ１０に到る経路を求める。同様に、目的地Ｅより最上位レベル４の上位ノードＣ２０に到る経路をもとめる。ついで、出発地側の上位ノードｃ１０から目的地側の上位ノードｃ２０へ到る経路をレベル４の道路情報を用いて探索し、最終的に出発地から目的地へ到るコスト最小の経路を探索する。
【特許文献１】特開２００３−３３７０３４号公報
【特許文献２】特開２００４−２８６５２４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
第１従来技術では、専用ネットワークの数が非常に多いので、道路情報のデータサイズが大きくなる問題がある。ま地図データの更新を、差分データを作成して行う場合、専用ネットワーク情報の差分データ量が大きくなってしまい、該差分データを通信で取得するには通信時間が非常に長くなって通信コストが高くなり、また、地図更新時間が長くなる問題がある。
第２従来技術の階層化構造の探索では、ヒューリスティックコストをかけ、出来るだけ無駄に探索枝をのばさないで目的地までの最適解を得る方法が存在する。しかし、それでも余計に探索枝がのびてしまい、探索時間が長くなる問題がある。図１７は、東京駅→大阪駅の経路探索における探索枝ののびかたを示すもので、塗りつぶし部分が探索枝がのびたところを示している。
以上から、本発明の目的は、探索した経路品位を保ち、かつ経路探索を高速化することである。
【課題を解決するための手段】
【０００６】
・地図データ作成方法
上記課題は本発明によれば、詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法において、所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として作成して地図データに含めることにより達成される。
前記探索範囲情報を作成するための第１の方法は、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するステップ、任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索するステップ、探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記探索範囲情報を作成するステップを有している。
前記探索範囲情報を作成するための第１の方法は、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するステップ、任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求めるステップ、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求めるステップ、前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成するステップを有している。
・経路探索方法
上記課題は本発明によれば、目的地までの経路を探索するナビゲーション装置の経路探索方法により達成される。本発明の経路探索方法は、(1)詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、最上位レベルの次のレベル(準最上位レベル)における任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定するデータを探索範囲情報とし、該探索範囲情報を各レベルのメッシュ毎の道路情報と共に地図データに含め、更に、最上位レベルの道路情報を構成するリンクが前記準最上位レベルのメッシュをまたがらないようにすると共に該リンクのリンクレコードに該リンクが存在する前記準最上位レベルのメッシュの識別データを含ませるステップ、(2)最上位レベルのノード間の経路探索に際して、前記探索範囲情報により経路探索に使用するとされたメッシュのメッシュ識別データを有する最上レベルリンクを用いて経路探索を行うステップ、を有している。
【０００７】
・地図データ作成装置、
また、上記課題は本発明によれば、詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成装置により達成される。
本発明の第１の地図データ作成装置は、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索する探索部、探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部を備えている。
本発明の第２の地図データ作成装置は、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照して前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求める経路探索部、前記各経路を構成するリンクが属するメッシュを特定するデータにより、前記第１のメッシュから第２のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部を備えている。
【０００８】
・ナビゲーション装置、
また、上記課題は本発明によれば目的地までの経路を探索するナビゲーション装置により達成される。本発明のナビゲーション装置は、(１) 上位レベルの次のレベル(準最上位レベル)における任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定するデータを探索範囲情報とし、該探索範囲情報を各レベルのメッシュ毎の道路情報と共に地図データに含め、更に、最上位レベルの道路情報を構成するリンクが前記準最上位レベルのメッシュをまたがらないようにすると共に該リンクのリンクレコードに該リンクが存在する準最上位レベルのメッシュの識別データを含ませてなる地図データを記憶する地図データ記憶部、(2)目的地を設定する目的地設定部、(3)出発地側及び目的地側の最上位レベルのノードを求め、該ノード間の経路探索に際して、前記探索範囲情報により経路探索に際して使用するとされているメッシュのメッシュ番号を有する最上位レベルのリンクを用いて経路探索を行う経路探索部を備えている。
【発明の効果】
【０００９】
本発明によれば、所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含めるようにしたから、該探索範囲情報を用いることにより探索範囲を狭めることができ、高速の経路探索が可能になった。
又、本発明によれば、探索範囲情報として探索すべきメッシュの識別データを保存するだけでよいため、該探索範囲情報のサイズを少なくでき、しかも、地図更新時における差分データサイズを小さくできる。
又、本発明によれば、任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求め、前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成するようにしたから、高速に探索範囲データを作成することができるようになった。
【発明を実施するための最良の形態】
【００１０】
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法において、所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含める。
この探索範囲情報は、以下のように作成する。第１の探索範囲情報作成方法では、(1) メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、(2)任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索し、(3)探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記探索範囲情報を作成する。
第２の探索範囲情報作成方法では、（1）任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、(2)同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求め、(3)前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成する。
【実施例】
【００１１】
(Ａ)本発明の概要
図１は本発明の地図データに含まれる道路情報の説明図である。詳細度に応じて複数のレベル(レベル１〜レベル４)を設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報RI1〜RI4と、経路探索に際して利用する探索範囲データSRDとで道路情報を構成する。
レベル1は誘導経路対象道路と非誘導経路対象道路の地図情報を特定する部分、レベル2は誘導経路対象道路の道路情報を特定する部分、レベル３は主要道路の地図情報を特定する部分、レベル４は更に主要な道路(県道、国道、高速道路)の地図情報を特定する部分である。
探索範囲データSRDは、図２に示すように、所定レベル(例えばレベル３)における任意の２つのメッシュM1,M2の組み合わせ毎に、一方のメッシュM1から他方のメッシュM2に到る経路を探索する際に使用するメッシュ(太枠線内のメッシュ)を特定するデータを探索範囲データとして地図データに含める。
この探索範囲データSRDは、例えば、以下のように作成する。(１)各メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、(２)任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路PT1，PT2，…を探索し、(３)探索された各経路を構成するリンクが属するメッシュを特定するデータにより、該２つのメッシュの組み合わせに応じた探索範囲データとし、全てのメッシュの組み合わせについて探索範囲データを作成する。
【００１２】
図３はメッシュの一例の説明図である。地図はカバーするエリアの広さからレベル４のメッシュ，レベル３のメッシュ、レベル３のメッシュ、レベル２のメッシュ、レベル１のメッシュと階層化されている。レベル４のメッシュに相当する領域Ｒ４は、複数(図では４つ)のレベル３メッシュの領域Ｒ３で構成され、同様に、レベル３のメッシュに相当する領域Ｒ３は、４つのレベル２メッシュの領域Ｒ２で構成され、レベル２のメッシュに相当する領域Ｒ２は、４つのレベル１メッシュの領域Ｒ１で構成されている。
【００１３】
図４は道路情報に含まれるリンクレコードの構成説明図である。リンクとは交差点から交差点までの道路部分であり、リンクレコードは、（Ａ）に示すように(1)リンクID、(2)道路種別、(3)リンク距離、(4)車線数、(5)リンク形状を特定する形状情報(始点ノード、中間のノード、終点ノードの位置データ)を有している。各リンクレコードはメッシュ番号に対応させて地図に含まれており、リンクが属するメッシュのメッシュ番号がわかるようになっている。また、レベル４のリンクはレベル３領域Ｒ３をまたがらないように形成されており、該レベル４のリンクレコードには図４(Ｂ)に示すようにレベル３領域のメッシュ番号が含まれている。
図５はレベル４のリンクがレベル３領域をまたがらないように形成することを説明する説明図であり、交差点Ｎ１，Ｎ２を始点、終点とするリンクLKがレベル３領域R3a，R3bを横切っている。かかる場合、リンクLKをレベル３領域Ｒ３の境界線で二分し、二分された２つのリンクLK1（N1−NB），LK2（NB−N2）をレベル４のリンクとし、夫々についてリンクレコードを作成し、それぞれにレベル３領域R3a．R3bのメッシュ番号を持たせる。
【００１４】
（Ｂ）探索データ作成
図６は本発明の地図作成装置の要部構成図、図７は本発明の地図作成処理説明図である。
リンクデータ入力部１はレベル３メッシュのリンクレコードをリスト作成部２と経路探索部３に入力する。リスト作成部２は、レベル３メッシュのリンクレコードを参照し、全レベル３メッシュについて、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成する。図７（A）は、境界脱出リンクの説明図であり、レベル３メッシュの着目領域R3から隣接メッシュへ移動する際に通る境界リンクS1〜S6が境界脱出リンクである。図７（B）は、境界進入リンクの説明図であり、隣接メッシュからレベル３メッシュの着目領域R3へ進入する際に通る境界リンクE1〜E6が境界進入リンクである
経路探索部３は、任意の２つのレベル３メッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクS1〜S6から他方のメッシュの各境界進入リンクE1〜E6に到る全経路を所定の経路探索方法により、例えばダイクストラ法により探索する。すなわち、図7(C),(D)に示すように経路探索部３は、
・境界脱出リンクS1から各境界進入リンクE1〜E6に到る全経路、
・境界脱出リンクS2から各境界進入リンクE1〜E6に到る全経路、
・境界脱出リンクS3から各境界進入リンクE1〜E6に到る全経路、
・・・・・・・
・境界脱出リンクS6から各境界進入リンクE1〜E6に到る全経路、
を探索する。
【００１５】
探索範囲データ作成部４は、経路探索部３により探索された上記の各経路を構成するレベル３リンクが属するレベル３メッシュのメッシュ番号を記憶することにより、任意の2つのレベル3メッシュの組み合わせに対応させて探索範囲データを作成してメモリ５に保存する。なお、探索範囲データを保存するために、任意の２つのメッシュの組み合わせに対応させてメモリ５にKバイトを用意し、Kバイトの各ビットにより上記経路を構成するリンクが所定のメッシュに含まれているか否かを記録する。すなわち、Kバイトの第1ビット〜第8×Kビットをメッシュ番号１〜メッシュ番号8×Kに対応させ、上記経路を構成するリンクが所定のメッシュに属する場合には、該メッシュに対応するビットに”1”を記入し、これにより探索範囲データを作成して保存する。全てのメッシュの組み合わせに対して上記処理を行って、探索範囲データをメモリ５に保存する。
地図データ作成部６は各レベルの道路情報および前記作成された探索範囲データを用いて道路レイヤ情報を作成してたとえばDVD ７に記録する。
【００１６】
（C）経路探索法
・ダイクストラ法
図８はコストを距離とした場合のダイクストラ法の概略説明図で、道路を直線、交差点を直線の交点としてグラフ化したものである。各交差点間の距離は既知で、Ｐsは出発点(自車位置)、Ｐdは目的地である。ダイクストラ法では、出発地Ｐsに隣接する１次交差点Ａ1〜Ａ4を求め、各１次交差点Ａ1〜Ａ4に対応させて０次の交差点（出発点）及び出発点からの距離を記憶する。ついで、各１次交差点Ａ1〜Ａ4について２次交差点Ｂijを求め、各２次交差点に対応させて１次交差点を経由する出発点からの距離を求めて記憶する。例えば、１次交差点Ａ1については３つの２次交差点Ｂ11，Ｂ12，Ｂ13が求まり、各２次交差点Ｂ11，Ｂ12，Ｂ13に対応させて、
Ｂ11：１次交差点Ａ1を経由する出発点からの距離d11
Ｂ12：１次交差点Ａ1を経由する出発点からの距離d12
Ｂ13：１次交差点Ａ1を経由する出発点からの距離d13・・・・(a)
を記憶する。又、1次交差点Ａ2について３つの２次交差点Ｂ21，Ｂ22，Ｂ23が求まり、各２次交差点Ｂ21，Ｂ22，Ｂ23に対応させて、
Ｂ21：１次交差点Ａ2を経由する出発点からの距離d21 ・・・・（b）
Ｂ22：１次交差点Ａ2を経由する出発点からの距離d22
Ｂ23：１次交差点Ａ2を経由する出発点からの距離d23
を記憶し、他の１次交差点Ａ3，Ａ4についても同様に２次交差点を求めて所定のデータを記憶する。
ところで、交差点Ｂ13とＢ21は同一の交差点である。このように、データを記憶すべき交差点が重複すると、出発点からの距離d13とd21の大小を比較し、小さい方のデータのみを記憶する。たとえば、d13＞ｄ21であれば、交差点Ｂ13（＝Ｂ21)のデータとして(b)のデータが最終的に記憶される。
以後、同様に、各２次交差点について３次交差点Ｃijを求め、各３次交差点に対応させて２次交差点を経由する出発点からの距離を求めて記憶し、一般に各第ｉ次交差点について第(i+1)次交差点を求め、各第(i+1)次交差点に対応させて第ｉ次交差点を経由する出発点からの累計距離を求めて記憶してゆけば、最終的に目的点Ｐｄに到達する。以上はノードに着目してダイクストラ法を説明したがリンクに着目して説明することもできる。
【００１７】
・ダイクストラ法を用いた経路探索処理
図９はダイクストラ法を用いた経路探索処理のフローであり、距離をコストとする場合であり、目的地が存在するメッシュを目的側メッシュ、出発地が存在するメッシュを出発側メッシュという。
所定の出発側メッシュの第j境界脱出リンクを選択し、該リンクの検索次数nを１にし（１→ｎ、ステップ１０１）、第ｎ次リンクに接続するリンクが存在するか調べる（ステップ１０２）。１次リンクは出発点Ｐsに接続するリンクである。第次ｎリンクLnに接続するリンク(隣接リンクという)が存在すれば、出発点Ｐsから第ｎ次リンクLnを経由して隣接リンクLajの終端までの累計距離Ｄを計算する（ステップ１０３）。
出発点から第ｎ次リンクの終点までの距離ｄnは後述するように、該第次ｎリンクに対応させて記憶に記憶してあり、また隣接リンクLajの距離dajはリンクレコードに記憶してあるから、次式
ｄn＋ｄaj→Ｄ
により出発点Ｐsから隣接リンクLajの終点までの累計距離Ｄが求まる。
ついで、隣接リンクLajの検索次数が(n+1)かチェックし（ステップ１０４）、(n+1)でなければ、隣接リンクLajに対応させて、以下のデータ
(1) 現在着目している第ｎ次リンクのシ−ケンシャル番号、
(2) 出発点から当該隣接リンクLajの終点までの累計距離Ｄ、
(3) 当該隣接リンクLaj の検索次数として(n+1)、
(4) メッシュ３番号
(5) リンクLajのリンク番号
を記憶部に記憶し（ステップ１０５）、以後、ステップ１０２に戻り、着目している第ｎ次リンクに接続するリンクが、なお残存するか調べて以降の処理を繰り返す。
一方、ステップ１０４において、隣接リンクの次数が(n+1)の場合には、換言すれば、該隣接リンクが別の第ｎ次リンクに隣接するリンクとして参照されていれば（ステップ１０５で既に上記(1)〜(5) のデータが記憶されていれば）、該隣接リンクに対応して記憶してある出発点からの距離D′とステップ１０３で求めた距離Dの大小を比較する（ステップ１０６）。D＜D′であれば、当該隣接リンクLajに対応して記憶部に記憶してある、第ｎ次リンクのシ−ケンシャル番号を現在着目している第ｎ次リンクのシ−ケンシャル番号で置き換えると共に、累計距離Ｄ′をＤで書き替え（Ｄ→Ｄ′，ステップ１０７）、以後、ステップ１０２に戻り、着目している第ｎ次リンクに接続するリンクが、なお残存するか調べて以降の処理を繰り返す。又、D≧D′の場合には、当該隣接リンクに対応して記憶部に記憶してある内容を変更せずステップ１０２に戻る。
【００１８】
ステップ１０２において、着目している第ｎ次リンクに接続するリンクが存在しなくなれば、別の第ｎ次リンクが存在するか調べ（ステップ１０８）、存在すれば、該別の第ｎ次リンクを新たに第ｎ次リンクとして（ステップ１０９）、ステップ１０２以降の処理を繰り返す。ステップ１０８において、別の第ｎ次リンクが存在しなければ、目的側メッシュの進入リンクに到達したかチェックし(ステップ１１０)、到達していなければ検索次数を１つ歩進し（ｎ＋１→ｎ，ステップ１１１）、ステップ１０２以降の処理を繰り返す。しかし、目的側メッシュの進入リンクに到達していれば、探索処理を終了する。以上では、距離をコストとみなした場合であるが、コストが距離以外の要素をも含む場合には距離の代わりにコストＣを用いることができる。
以上により、探索処理が完了後、目的側メッシュにおける所定の境界進入リンクに着目し、
(1)該境界進入リンク（M次のリンクとする）→(2)該境界進入リンクに対応させて記憶してある（M−１）次のリンク→(3)該（M−１）次のリンクに対応させて記憶してある（M−２）次のリンク→・・・→(4)2次のリンクに対応させて記憶してある１次リンク（第i目的側メッシュの第j境界脱出リンク）
と順次接続することにより、１次リンクである第i目的側メッシュの第j境界脱出リンクから目的側メッシュにおける所定の境界進入リンクに到るコスト(距離)最小の経路をもとめることができる。
なお、後述する図１０の探索範囲データ作成処理フローのステップ２０８では、上記求めた経路を構成するリンクのメッシュ３番号に対応するビットを“１”にして探索範囲データを作成する。
また、図１１の第２の探索範囲データ作成処理フローのステップ３０３の探索処理では、上記ステップ１１０において探索枝を延ばせるか判別し、探索枝を延ばせれば検索次数を１つ歩進し（ｎ＋１→ｎ，ステップ１１１）、ステップ１０２以降の処理を繰り返す。しかし、探索枝を延ばせず、探索が不可能になれば探索処理を終了する。
【００１９】
（D）探索範囲データの作成処理
・第１の探索範囲データ作成処理
図１０は本発明の第１の探索範囲データ作成処理フローである。
まず、レベル３メッシュのリンクレコードを参照し、全レベル３メッシュについて、メッシュ毎に該メッシュから隣接メッシュへ脱出する境界脱出リンクのリストを作成し(ステップ２０１)、ついで、該メッシュに隣接メッシュから進入する境界進入リンクのリストを作成する(ステップ２０２)。
ついで、出発側メッシュ番号を示すi、目的側メッシュ番号を示すk、出発側メッシュにおける境界脱出リンク番号を示すj、目的側メッシュにおける境界進入リンク番号を示すmをすべて１に初期化する(ステップ２０３〜２０６)。
ついで、第i出発側メッシュの第j境界脱出リンクから第k目的側メッシュの第m境界進入リンクまでの経路を探索する(ステップ２０７)。なお、i=kの場合にはステップ２０７以降の処理を行わない。
経路探索処理が終了すれば、第m境界進入リンクから逆方向にたどって第j境界脱出リンクに至る経路が通過するメッシュのメッシュ対応ビットを“1”にする(ステップ２０８)。しかる後、第k目的側メッシュの全境界進入リンクまでの経路探索が完了したかチェックし(ステップ２０９)、完了してなければmを歩進して(m＝m+1,ステップ２１０)、ステップ２０７以降の処理を繰り返す。
ステップ２０９において、第k目的側メッシュの全境界進入リンクまでの経路探索が完了すれば、第i出発側メッシュの全境界脱出リンクからの経路探索が完了したかチェックし(ステップ２１１)、完了してなければｊを歩進して(ｊ＝ｊ+1,ステップ２１２)、ステップ２０６以降の処理を繰り返す。ステップ２１１において、第i出発側メッシュの全境界脱出リンクからの経路探索が完了すれば、メッシュ番号(i,k)の組み合わせに対応する探索範囲データの作成が完了する。
ついで、全目的側メッシュについて上記処理が終了したかチェックし(ステップ２１３)、終了してなければkを歩進して(k＝k+1,ステップ２１４)、ステップ２０５以降の処理を繰り返す。ステップ２１３において、全目的側メッシュについて上記処理が終了すれば、第i出発側メッシュから他の全目的側メッシュに対する探索範囲データの作成が完了する。
しかる後、全出発側メッシュについて上記処理が終了したかチェックし(ステップ２１５)、終了してなければiを歩進して(i＝i+1,ステップ２１６)、ステップ２０４以降の処理を繰り返す。ステップ２１５において、全出発側メッシュについて上記処理が終了すれば、探索範囲データの作成が完了する。
【００２０】
・第２の探索範囲データ作成処理
図１１は本発明の第２の探索範囲データ作成処理フローである。なお、各メッシュの境界脱出リンクおよび境界進入リンクのリストの作成は完了しているものとする。
まず、出発側メッシュ番号を示すi、出発側メッシュにおける境界脱出リンク番号を示すjを１に初期化する(ステップ３０１〜３０２)。
ついで、第i出発側メッシュの第j境界脱出リンクからダイクストラ法を用いて経路探索処理を探索が不可能となるまで、すなわち、探索枝を延ばせなくなるまで行う(ステップ３０３)。探索終了後、目的側メッシュ番号を示すk、目的側メッシュにおける境界進入リンク番号を示す番号mをそれぞれ１に初期化する(ステップ３０４〜３０５)。
ついで、第k目的側メッシュの第m境界進入リンクから逆方向にたどって第i出発側メッシュの第j境界脱出リンクに至る経路が通過するメッシュのメッシュ対応ビットを“1”にする(ステップ３０６)。しかる後、第k目的側メッシュの全境界進入リンクについてステップ３０６の処理が完了したかチェックし(ステップ３０７)、完了してなければmを歩進して(m＝m+1,ステップ３０８)、ステップ３０６以降の処理を繰り返す。
ステップ３０７において、第k目的側メッシュの全境界進入リンクについてステップ３０６の処理が完了すれば、全目的側メッシュについて上記処理が終了したかチェックし(ステップ３０９)、終了してなければkを歩進して(k＝k+1,ステップ３１０)、ステップ３０５以降の処理を繰り返す。
ステップ３０９において、全目的側メッシュについて上記処理が終了すれば、第i出発側メッシュの第ｊ境界脱出リンクから全目的側メッシュの全境界脱出リンクに至る探索範囲データの作成が完了する。ついで、第i出発側メッシュの全境界脱出リンクについて上記処理が完了したかチェックし(ステップ３１１)、完了してなければｊを歩進して(ｊ＝ｊ+1,ステップ３１２)、ステップ３０３以降の処理を繰り返す。
ステップ３１１において、第i出発側メッシュの全境界脱出リンクからの経路探索が完了すれば、メッシュ番号iのメッシュと他のすべてのメッシュとの組み合わせに対応する探索範囲データの作成が完了する。
ついで、全出発側メッシュについて上記処理が終了したかチェックし(ステップ３１３)、終了してなければiを歩進して(i＝i+1,ステップ３１４)、ステップ３０２以降の処理を繰り返す。ステップ３１３において、全出発側メッシュについて上記処理が終了すれば、探索範囲データの作成が完了する。
【００２１】
（E）ナビゲーション装置
図１２は本発明のナビゲーション装置の構成図である。
地図記録媒体(CD-ROM、DVDなど）１１には図６の地図作成装置が作成した地図データが記録されており、必要に応じて読み取られるようになっている。操作部１２はナビゲーション制御装置１０を操作するものでリモコン、操作用のハードキーなどを有している。GPS受信機１３はGPS衛星から送られてくるGPS信号を受信し、車両の絶対的現在位置(GPS位置)や進行方向を算出し、自立航法センサー部１４は、所定時間毎に進行方向変化および走行距離を検出してナビゲーション制御装置１０に入力する。
タッチパネル式ディスプレイ装置１５はナビゲーション制御装置１０からの指示に従って車両周辺地図、誘導経路、メニュー、車両位置マーク等を表示する。また、タッチパネル式ディスプレイ装置１５は、スクリーンに表示したソフトキーが押下されたとき所定のコマンドをナビゲーション制御装置１０に入力するようになっている。
ナビゲーション制御装置１０において、位置推定制御部２０はGPS受信機１３及び自立航法センサー部１４からの信号に基づいて車両位置を推定してナビゲーション制御部２２に入力する。地図バッファ２１は地図記録媒体から読み取った地図データを保存する。ナビゲーション制御部２２は、図示しないが、入力される各種情報、コマンドに基づいて、車両位置周辺の地図データを地図バッファ２１に読み出す地図読み出し制御部、誘導経路探索制御及び経路誘導制御を実行する誘導経路制御部、各種操作画面、車両マークの発生制御を実行する操作画面発生制御部などを有している。
地図描画部２３は地図バッファ２１に読み出された地図データを用いて地図画像を生成してVRAM ２４に書込み、画像読み出し部２５は制御部２２からの指示に従ってVRAM ２４から所定の画像部分を切り取って画像合成部２６に入力する。
誘導経路メモリ２７は、制御部２２の誘導経路制御部により探索された目的地までの誘導経路情報、すなわち、誘導経路を構成する全リンクデータを出発地から目的地まで記録する。誘導経路描画部２８は誘導経路情報を用いて誘導経路画像を発生して画像合成部２６に入力し、描画地図上に強調表示する。操作画面発生部２９は各種メニュー画面(操作画面)を生成して画像合成部２６に入力し、マーク発生部３０は車両位置マークやカーソル等の各種マークを生成して画像合成部26に入力する。画像合成部２６は、VRAM ２４から読み出した地図画像に各種マークや誘導経路画像を重ね合わせてスクリーン全体に表示する。
【００２２】
（F）誘導経路探索
図１３は出発地と目的地が特定された際の本発明の誘導経路探索処理フローである。
レベル１メッシュの出発地からレベル４のメッシュのリンクまでの経路を探索する(ステップ４０１)。同様に、レベル１メッシュの目的地からレベル４のメッシュのリンクまでの経路を探索する(ステップ４０２)。ついで、レベル４メッシュの出発側リンクおよびレベル４メッシュの目的側リンクがそれぞれ存在するレベル３メッシュ番号を求める(ステップ４０３)。この求めたレベル３メッシュの組み合わせにより、経路探索に際してどの探索範囲データを使用するかがわかる。
しかる後、該探索範囲データを参照しつつ、レベル４の道路情報(リンクレコード)を用いて出発地から目的地までの経路を探索する(ステップ４０４)。すなわち、経路探索に際して、レベル４リンクのリンクレコードに含まれるレベル３メッシュ番号に対応する探索範囲データのビット位置を参照し(図１４参照)、“１”(オン)であれば、該レベル４リンクは経路探索対象リンクであるとみなして該リンクを用いて経路探索処理を行い、“０”(オフ)であれば、該レベル４リンクは経路探索対象リンクでないとみなして経路探索に使用しない。
ステップ４０１においてレベル１の出発地からレベル４メッシュのリンクまでの経路は複数見つかるから、夫々について出発地から目的地までの経路を探索し、最小コストの経路を誘導経路として取得する(ステップ４０５)。
以上本発明によれば階層型探索において、探索範囲を経路品位に影響する事無く絞り込む事が出来て、探索時間を削減する事が出来る。
【図面の簡単な説明】
【００２３】
【図１】本発明の地図データに含まれる道路情報の説明図である。
【図２】探索範囲データSRDの説明図である。
【図３】図３はメッシュの一例説明図である。
【図４】道路情報に含まれるリンクレコードの構成説明図である。
【図５】レベル４のリンクがレベル３領域をまたがらないように形成することを説明する説明図である。
【図６】本発明の地図作成装置の要部構成図である。
【図７】本発明の地図作成処理説明図である。
【図８】コストを距離とした場合のダイクストラ法の概略説明図である。
【図９】ダイクストラ法を用いた経路探索処理のフローである。
【図１０】本発明の第１の探索範囲データ作成処理フローである。
【図１１】本発明の第２の探索範囲データ作成処理フローである。
【図１２】本発明のナビゲーション装置の構成図である。
【図１３】出発地と目的地が入力された際の本発明の誘導経路探索処理フローである。
【図１４】レベル４リンクを経路探索に使用するか否かを判断する説明図である。
【図１５】第１従来技術説明図である。
【図１６】第２従来技術説明図である。
【図１７】第２従来技術の問題点説明図である。
【符号の説明】
【００２４】
１ リンクデータ入力部
２ リスト作成部
３ 経路探索部
４ 探索範囲データ作成部
５ メモリ
６ 地図データ作成部
７ DVD
【特許請求の範囲】
【請求項１】
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法において、
所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含めることを特徴とする地図データ作成方法。
【請求項２】
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、
任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索し、探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記探索範囲情報を作成する、
ことを特徴とする請求項１記載の地図データ作成方法。
【請求項３】
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、
任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、
同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求め、
前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成する、
ことを特徴とする請求項１記載の地図データ作成方法。
【請求項４】
前記メッシュのレベルは最上位レベルの次のレベル(準最上位レベル)であり、最上位レベルの道路情報を構成するリンクは前記準最上位レベルのメッシュをまたがらないようにし、かつ、該リンクのリンクレコードに該リンクが存在する前記準最上位レベルのメッシュの識別データを含ませることを特徴とする請求項1乃至３記載の地図データ作成方法。
【請求項５】
目的地までの経路を探索するナビゲーション装置の経路探索方法において、
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、最上位レベルの次のレベル(準最上位レベル)における任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定するデータを探索範囲情報とし、該探索範囲情報を各レベルのメッシュ毎の道路情報と共に地図データに含め、更に、最上位レベルの道路情報を構成するリンクが前記準最上位レベルのメッシュをまたがらないようにすると共に該リンクのリンクレコードに該リンクが存在する前記準最上位レベルのメッシュの識別データを含ませ、
最上位レベルのノード間の経路探索に際して、前記探索範囲情報により経路探索に使用するとされたメッシュのメッシュ識別データを有する最上レベルリンクを用いて経路探索を行う、
ことを特徴とする経路探索方法。
【請求項６】
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成装置において、
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、
任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索する探索部、
探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部、
を備えたことを特徴とする地図データ作成装置。
【請求項７】
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成装置において、
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、
任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照して前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求める経路探索部、
前記各経路を構成するリンクが属するメッシュを特定するデータにより、前記第１のメッシュから第２のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部、
を備えたことを特徴とする地図データ作成装置。
【請求項８】
目的地までの経路を探索するナビゲーション装置において、
上位レベルの次のレベル(準最上位レベル)における任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定するデータを探索範囲情報とし、該探索範囲情報を各レベルのメッシュ毎の道路情報と共に地図データに含め、更に、最上位レベルの道路情報を構成するリンクが前記準最上位レベルのメッシュをまたがらないようにすると共に該リンクのリンクレコードに該リンクが存在する準最上位レベルのメッシュの識別データを含ませてなる地図データを記憶する地図データ記憶部、
目的地を設定する目的地設定部、
出発地側及び目的地側の最上位レベルのノードを求め、該ノード間の経路探索に際して、前記探索範囲情報により経路探索に際して使用するとされているメッシュのメッシュ番号を有する最上位レベルのリンクを用いて経路探索を行う経路探索部、
を備えたことを特徴とするナビゲーション装置。
【請求項１】
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法において、
所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含めることを特徴とする地図データ作成方法。
【請求項２】
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、
任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索し、探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記探索範囲情報を作成する、
ことを特徴とする請求項１記載の地図データ作成方法。
【請求項３】
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、
任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、
同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求め、
前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成する、
ことを特徴とする請求項１記載の地図データ作成方法。
【請求項４】
前記メッシュのレベルは最上位レベルの次のレベル(準最上位レベル)であり、最上位レベルの道路情報を構成するリンクは前記準最上位レベルのメッシュをまたがらないようにし、かつ、該リンクのリンクレコードに該リンクが存在する前記準最上位レベルのメッシュの識別データを含ませることを特徴とする請求項1乃至３記載の地図データ作成方法。
【請求項５】
目的地までの経路を探索するナビゲーション装置の経路探索方法において、
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、最上位レベルの次のレベル(準最上位レベル)における任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定するデータを探索範囲情報とし、該探索範囲情報を各レベルのメッシュ毎の道路情報と共に地図データに含め、更に、最上位レベルの道路情報を構成するリンクが前記準最上位レベルのメッシュをまたがらないようにすると共に該リンクのリンクレコードに該リンクが存在する前記準最上位レベルのメッシュの識別データを含ませ、
最上位レベルのノード間の経路探索に際して、前記探索範囲情報により経路探索に使用するとされたメッシュのメッシュ識別データを有する最上レベルリンクを用いて経路探索を行う、
ことを特徴とする経路探索方法。
【請求項６】
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成装置において、
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、
任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索する探索部、
探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部、
を備えたことを特徴とする地図データ作成装置。
【請求項７】
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成装置において、
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、
任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照して前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求める経路探索部、
前記各経路を構成するリンクが属するメッシュを特定するデータにより、前記第１のメッシュから第２のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部、
を備えたことを特徴とする地図データ作成装置。
【請求項８】
目的地までの経路を探索するナビゲーション装置において、
上位レベルの次のレベル(準最上位レベル)における任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定するデータを探索範囲情報とし、該探索範囲情報を各レベルのメッシュ毎の道路情報と共に地図データに含め、更に、最上位レベルの道路情報を構成するリンクが前記準最上位レベルのメッシュをまたがらないようにすると共に該リンクのリンクレコードに該リンクが存在する準最上位レベルのメッシュの識別データを含ませてなる地図データを記憶する地図データ記憶部、
目的地を設定する目的地設定部、
出発地側及び目的地側の最上位レベルのノードを求め、該ノード間の経路探索に際して、前記探索範囲情報により経路探索に際して使用するとされているメッシュのメッシュ番号を有する最上位レベルのリンクを用いて経路探索を行う経路探索部、
を備えたことを特徴とするナビゲーション装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２００７−１９９５７５（Ｐ２００７−１９９５７５Ａ）
【公開日】平成１９年８月９日（２００７．８．９）
【国際特許分類】
【出願番号】特願２００６−２０４３６（Ｐ２００６−２０４３６）
【出願日】平成１８年１月３０日（２００６．１．３０）
【出願人】（０００１０１７３２）アルパイン株式会社 (2,424)
【出願人】（５００２３０３４７）株式会社エムビーエイ (22)
【Ｆターム（参考）】
【公開日】平成１９年８月９日（２００７．８．９）
【国際特許分類】
【出願日】平成１８年１月３０日（２００６．１．３０）
【出願人】（０００１０１７３２）アルパイン株式会社 (2,424)
【出願人】（５００２３０３４７）株式会社エムビーエイ (22)
【Ｆターム（参考）】
[ Back to top ]