(57)【特許請求の範囲】
【請求項１】
指定された出発地から目的地までのルート探索を行なってルートを設定し、設定されたルートにしたがって経路案内を行なうナビゲーション装置であって、道路網の情報量をもとに階層構造にして道路網の情報の多い下位階層から道路網の情報の少ない上位階層へと階層を展開するとともに、各階層の接続情報を有する地図データ記憶する記憶手段と、前記地図データに基づき前記指定された出発地および目的地を含む階層を特定し、前記各階層間の接続情報に基づき、特定された階層において上位階層へ接続する点までルート探索を行ない、さらに上位階層に移行して前記接続する点からのルート探索を繰り返し行なうことによって出発地から目的地までのルート探索を行なう経路探索手段とを備え、  地図データには、上位／下位の階層にわたるリンクについて、上位階層の地図データのリンクを下位階層の地図データのリンクに対応付けて記述され、上位階層の地図データのリンク形状を下位階層の地図データに格納し、
下位階層のルート探索に際して、当該下位階層のリンクが上位階層のリンクに対応したときルート探索を下位階層から上位階層へ移行させ、前記下位階層から上位階層へルート探索を移行したとき、上位階層の対応するリンクの両端までルート探索処理を完了可能にしたことを特徴とするナビゲーション装置。
【請求項２】
ルート探索を行なうために、下位階層の地図データに、リンク形状として、下位階層の地図データのリンクに対応する上位階層の地図データのリンクと、その上位階層の地図データのリンクの到達先ノードとが記述され、この記述に基づいてルート形状を表示するようにしたことを特徴とする請求項１記載のナビゲーション装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ナビゲーション装置、特に地図データを階層構造にしてルート探索を行ない、且つ表示手段への探索経路の表示を高速で行なうことができるようにしたナビゲーション装置に関する。
【０００２】
【従来の技術】
車載用ナビゲーション装置は、地理の不案内な運転者に対して目的地までルート案内を行なうものである。この車載用ナビゲーション装置は、速度センサと方位センサから得られた走行軌跡道路形状との相関、あるいはＧｌｏｂａｌ  ＰｏｓｉｔｉｏｎｉｎｇＳｙｓｔｅｍ  （  以下、ＧＰＳとする。）の絶対位置を復号して検出した車両位置を中心に周囲の地図を表示することで利用者に車両位置を知らせている。ユーザは、このようなナビゲーション装置に対して、予め走行前に出発地および目的地を入力することによって出発地から目的地までのルートを設定し、その設定されたルートにしたがってナビゲーションを行なう。ナビゲーションでは、ルートを指示する場合、表示手段の画面に地図を表示し、その上にルートを重ねて表示したりする。
【０００３】
このようなナビゲーション装置において、ルート探索を行なうのに、出発地から目的地までの距離が長くなったり、或いは道路網の密度が高くなった場合、それだけルート探索の対象となる交差点が多くなり、ルート探索に要する計算時間や探索処理に用いるメモリの記憶容量が増えるのを防止する技術の開発が盛んに行なわれている。その１つの解決方法として、地図データを、道路網の情報量を基に階層構造にして道路網の情報の多い下位階層から、道路網の情報の少ない上位階層への階層を展開するとともに、各階層間の接続情報を有するデータ構造とし、この地図データに基づき、指定された出発地および目的地を含む階層を特定し、前記各階層間の接続情報に基づき、特定された階層において上位階層へ接続する点或いは部分までルート探索を行ない、さらに上位階層に移行して前記接続点  （部分）からのルート探索を繰り返し行なうようにしたものがある。
【０００４】
そのような階層構造の地図データに基づいてルート探索を行なう従来技術としては、例えば図９に示すものがある。図９において、１０１は上位レイヤを表し、この上位レイヤ１０１は交差点番号ａ，ｂ，ｃ，・・・を持つ主要幹線道路網の地図であり１つのブロックＡを構成している。１０２は下位レイヤを表し、この上位レイヤ２は、上位レイヤ１０１の主要幹線道路網に連結される支線の道路網も含めた地図であり、複数のブロックＢ，Ｃ，Ｄ，・・・で構成されている。そして下位レイヤ１０２においては、ブロック間の接続道路には、下位レイヤ１０２のブロックＣ、Ｄ間の交差点番号ｂとｃのように、ブロックで処理単位を構成することができるように擬似的に交差点を設定している。ブロックの数は、各ブロックＡ，Ｂ，Ｃ，Ｄ，・・・で情報量がほぼ同程度になるよう設定されている。
【０００５】
かかる地図データの構造を有するナビゲーション装置におけるルート探索手法について述べる。例えば出発地が下位レイヤのブロックＢにある交差点番号ｃであり、また目的地が同じく下位レイヤのブロックＤにある交差点番号ｄであるとする。この場合まず出発地側のブロックＢにおいて、上位レイヤ１０１にあり出発地の近くに対応する交差点番号を見つけ、その交差点番号ｄ（上位レイヤ１０１ではブロックＡの交差点番号ａが対応する）までのルートを探索して上位階層へ上がる。他方、目的地側のブロックＤにおいても同様に、上位レイヤ１０１にあり目的地の近くに対応する交差点番号を見つけ、その交差点番号ａ（上位レイヤ１０１ではブロックＡの交差点番号ｅが対応する）までのルートを探索して上位階層へ上がる。次に上位レイヤ１０１では、下位レイヤ１０２でルート探索を行なった情報と合わせてブロックＡにおける交差点番号ａから交差点番号ｅまでのルート探索を実行する。このようにして、上位レイヤ１０１ではルート１０３が探索され、出発地から目的地までのルート探索が行なわれる。
【０００６】
【発明が解決しようとする課題】
しかしながら、上記従来の車載用ナビゲーション装置にあっては、従来例１の方法では、下位の地図データからルート形状を求める際には、リンクをその中間の部分で分割することは生じないが、各リンクの形状の補間点が表示のための分解能に対して必要以上に多く、さらにリンク本数も複数となるため、表示用データのデータ量が増大する虞があり、経路案内表示の高速化を妨げる要因となっていた。
【０００７】
本発明は、このような従来の問題点を解決するものであり、地図データを階層構造にしてルート探索を行ない、且つ表示手段への探索経路の表示を高速で行なうことが可能なナビゲーション装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】
本発明は、上記目的を達成するため、地図データを、道路網の情報量を基に階層構造にして道路網の情報の多い下位階層から、道路網の情報の少ない上位階層への階層を展開するとともに、各階層間において共通する道路を対応付けた接続情報を有するデータ構造とし、この地図データに基づき、指定された出発地および目的地を含む階層を特定し、前記各階層間の接続情報に基づき、特定された階層において上位階層へ接続する点までルート探索を行ない、さらに上位階層に移行して前記接続点からのルート探索を繰り返し行なうようにし、地図データには、上位／下位の階層にわたるリンクについて、上位階層の地図データのリンクを下位階層の地図データのリンクに対応付けて記述され、上位階層の地図データのリンク形状を下位階層の地図データに格納し、下位階層のルート探索に際して、当該下位階層のリンクが上位階層のリンクに対応したときルート探索を下位階層から上位階層へ移行させ、前記下位階層から上位階層へルート探索を移行したとき、上位階層の対応するリンクの両端までルート探索処理を完了可能にしたことを要旨とする。また、本発明の別の態様として、ルート探索を行なうために、下位階層の地図データに、リンク形状として、下位階層の地図データのリンクに対応する上位階層の地図データのリンクと、その上位階層の地図データのリンクの到達先ノードとが記述され、この記述に基づいてルート形状を表示するようにすることもできる。
【０００９】
本発明では、上位／下位の階層にわたる道路の形状（リンク形状）を地図データに格納する。そのための条件は、
（１）上位／下位の階層にわたるリンク形状は、上位階層の地図データのリンクを下位階層の地図データのリンクに対応付けて記述する。
（２）該当するリンク形状は、上位階層のリンク形状と同数、同精度の補間点で構成する。
というものである。
【００１０】
かかる構成にすることにより、ルート探索が高速に行なわれるのみでなく、ルート探索の結果得られたルートを表示するに際しても高速で表示することができるようになり、ルート探索による経路案内処理操作全体の高速化を図ることができる。
【００１１】
【発明の実施の形態】
以下、本発明の実施の形態について、図面を参照しながら説明する。図１は本発明の一実施の形態に係るナビゲーション装置の構成を示すブロック図である。図１において、１は方位センサであり、この方位センサ１は自動車の絶対走行方位を検出する光ジャイロが使用される。２は車輪の回転数に応じたパルスを発生する距離センサー、３はブレーキスイッチ、パーキングスイッチなどのオン、オフ信号、電源電圧監視用信号などの各種センサー信号である。４は方位センサー１、距離センサー２などのセンサー信号を処理するセンサー信号処理部、５はＧＰＳレシーバであり、このＧＰＳレシーバ５は複数の衛星から送信される電波を受信し演算することにより受信点の位置（緯度、経度）を求めることができるものである。６はＣＤ−ＲＯＭドライバーであり、このＣＤ−ＲＯＭドライバー６は、地図データが記録されたＣＤ−ＲＯＭ７から地図データを読み出すものである。８は車室内に設置される表示・操作部であり、この表示・操作部８は、地図および自動車の現在走行位置、方位等をカラー表示する液晶ディスプレー８Ａ、この液晶ディスプレー８Ａの前面に設けられたタッチパネル８Ｂとからなり、タッチパネル８Ｂには表示地図の拡大、縮小などを指示するためのスイッチ、ルート探索を指示するスイッチ、液晶ディスプレー８Ａに表示された地名の中から目的地を選択するスイッチなどが具備されている。９は装置本体であり、この装置本体９は自動車のトランクルームなどに設置される。
【００１２】
次に装置本体９の構成について説明する。１０は各種の演算を行なうＣＰＵ  （中央処理装置）、１１はＣＰＵ１０で行なう各種の演算のプログラムが記憶されたＲＯＭ（リードオンリーメモリ）、１２は方位センサー１、距離センサー２、ＧＰＳレシーバ５、ＣＤ−ＲＯＭドライバー６等からのデータやＣＰＵ１０での演算結果等を記憶するメモリ（ＤＲＡＭ）、１３は装置本体９への電源供給が停止した際にも必要なデータを保持しておくためのバックアップ用メモリ（ＳＲＡＭ）、１４は液晶ディスプレー８Ａに表示する文字、記号などのパターンが記憶されたメモリ（漢字、フォントＲＯＭ）、１５は地図データや自車の現在位置データなどの基づいて表示画像を形成するための画像プロセッサ、１６はＣＰＵ１０から出力される地図データ、現在位置データおよび漢字、フォントＲＯＭ１４から出力される町名、高速道路などの道路名などの漢字、フォントを合成して液晶ディスプレー８Ａに表示する画像を記憶するメモリ（ＶＲＡＭ）、１７はＶＲＡＭ１６の出力データを色信号に変換するためのＲＧＢ変換回路であり、色信号はＲＧＢ変換回路１７から液晶ディスプレー８Ａに出力される。１８は通信インタフェースである。液晶ディスプレー８Ａには、高速道路、他の道路などが道路名、施設名などとともに表示され、さらに表示地図上に自車の現在位置を表示する自車マークが表示されるようになっている。
【００１３】
図２はＣＤ−ＲＯＭ７に記憶されている地図データのフォーマットの一例を示す図である。図２において、２０はディスクラベル、２１は描画パラメータ、２２は図葉管理情報、２３、２４は図葉（地図）、２５は経路探索用の地図データが格納された経路地図であり、上記図葉２３、２４には背景データ、文字データ、道路データなどが記憶されており、日本全国の地形図を緯度、経度によって分割した単位地図毎のデータが記憶されている。図葉には広い地域を粗く記述した図葉（レベル２）から狭い地域を詳細に記述した図葉（レベル０）が設定されていることにより地図データが階層構造になっている。各図葉は同一の地域を記述した地図表示レベルＡ，Ｂ，Ｃから構成されている。この地図表示レベルとは、地図の詳細度合いをランク分けにしたものであり、地図表示レベルＡ，Ｂ，Ｃは、ＡよりＢ、ＢよりＣがより詳細に記述されている。また、各地図表示レベルＡ，Ｂ，Ｃは地図表示レベル管理情報と複数のユニットから構成されている。ユニットは各地図表示レベルの地域を複数に分割した分割地域を記述したものであり、各ユニットはユニットヘッダ、文字レイヤ、背景レイヤ、道路レイヤ、オプションレイヤなどから構成される。文字レイヤには地図に表示される地名道路名、施設名などが記憶され、背景レイヤには道路、施設などを描画するためのデータ及び液晶ディスプレー８Ａで表示する道路、施設、海、背景などのカラーを指定するためのカラーパレットが記憶されている。また、道路レイヤには、交差点を含む道路を記述する座標（ノード）と線（リンク）に関するデータ、例えばノードのノード番号、緯度、経度、リンクのリンク番号、リンク距離などが記憶されている。また、道路レイヤには、道路の種類、例えば高速道路、有料道路、国道、県道、主要地方道路などの種類が記憶されている。
【００１４】
図３は図２における経路地図２５に格納された経路地図データのフォーマットの一例を別の表現で表して説明する図である。図３において、３１は経路地図データの全体構成を表し、この経路地図データは、管理情報３２と上位の地図データ３３と、中位の地図データ３４と、下位の地図データ３５とから成っている。管理情報には上位地図のアドレスとサイズのテーブル３６と、中位地図のアドレスとサイズのテーブル３７と、下位地図のアドレスとサイズのテーブル３８が設けられている。上位の地図データの内訳としては、上位の地図データがＮｏ．１，Ｎｏ．２，Ｎｏ．３，・・・というように格納され、中位の地図データの内訳としては、中位の地図データがＮｏ．１，Ｎｏ．２，Ｎｏ．３，・・・というように格納され、下位の地図データの内訳としては、下位の地図データがＮｏ．１，Ｎｏ．２，Ｎｏ．３，・・・というように格納されている。
【００１５】
図４は１つの階層における経路地図データ内の管理情報のデータフォーマットの一例を示す図である。この管理情報は、各種データのメモリ内におけるアドレスとそのサイズを記述したアドレス・サイズテーブル４０と、地図データ上のノードデータを記述したノードテーブル４１と、ノードとノードとを結ぶリンクデータを記述したリンクテーブル４２と、ノード座標データを記述したノード座標テーブル４３と、リンクの形状データを記述したリンク形状テーブル４４とを有している。そして、座標テーブル４３の各ノード座標はノードテーブル４１の各ノードデータに対応した座標データが格納され、またリンク形状テーブル４４の各リンク形状はリンクテーブル４２の各リンクデータに対応したリンク形状データが格納されている。
【００１６】
かかる構成を有するナビゲーション装置のルート探索動作について、図４および図５を参照して以下説明する。図５は本実施の形態においてルート探索を行なうときのアルゴリズムを説明するための一モデル図である。図５において、ｎ１，ｎ２，ｎ３，ｎ４，ｎ５はそれぞれノードを表し、図４におけるノードテーブル４１のノードデータＮｏ．１，Ｎｏ．２，Ｎｏ．３，・・・で表される。これらのノードｎ１，ｎ２，ｎ３，ｎ４，ｎ５は例えば地図上における交差点に対応する。またｌ（エル）１，ｌ２，ｌ３，ｌ４，ｌ５はそれぞれリンクを表し、図４におけるリンクテーブル４２のリンクデータＮｏ．１，Ｎｏ．２，Ｎｏ．３，・・・で表される。これらのリンクｌ１，ｌ２，ｌ３，ｌ４，ｌ５は例えば地図上における交差点と交差点の間の道路に対応する。
【００１７】
本実施の形態におけるルート探索では、先ず第１段階として、図５においてｎ１を出発点としてノードｎ１に接続するリンク本数分のリンクを図４のリンクテーブル４２から取得する。図５の例ではノードｎ１には３本のリンクｌ１，ｌ２，ｌ１が接続しているからノードテーブル４１のノードデータＮｏ．１からリンクテーブル４２のリンクデータＮｏ．１，Ｎｏ．２，Ｎｏ．３へとデータの取得が行なわれる。
【００１８】
次に第２段階として、各リンクデータの接続先のノード番号を取得し、各ノードのノードデータをノードテーブル４１から取得する。上記事例では、リンクデータＮｏ．１の接続先はノードｌ２であり、リンクデータＮｏ．２の接続先はノードｌ３であり、リンクデータＮｏ．３の接続先はノードｌ３である。したがって、リンクテーブル４２のリンクデータＮｏ．１からノードテーブル４１のノードデータＮｏ．２へとデータの取得が行なわれ、また、リンクテーブル４２のリンクデータＮｏ．２からノードテーブル４１のノードデータＮｏ．３へとデータの取得が行なわれる。
【００１９】
次に、最初のノードに隣接する次のノードを新たな起点として、当該ノードに接続リンクをリンクテーブル４２から取得し、その後再び第２段階の処理に戻る。
【００２０】
以上の処理を下位の階層の地図データ上で繰り返し行なって、下位の階層のノードまたはリンクが上位の階層のリンクに対応したら、上位の階層のルートと下位の階層のルートとが一致したと認定し下位の階層から上位の階層へ移行するための探索を終了する。
【００２１】
次に、上記アルゴリズムにおいて下位の階層の地図データから上位の階層の地図データへ移行するための動作について説明する。図６は道路ノードを使用した下位階層から上位階層への移行動作を説明する図である。図６において、上位階層の地図データではその地図データＮｏ．ｍのノードｋのノードデータ番号がＮｏ．ｋであると設定されている。また下位階層の地図データではその地図データのノードｐのノードデータ番号がＮｏ．ｐであると設定されている。そして、下位階層の地図データのノードテーブル４１内のノードデータには、当該下位階層の地図データにおけるノードｐは上位階層の地図データＮｏ．ｍのノード番号Ｎｏ．ｋが対応することが記述されている。そして、この対応付けデータが上位階層の地図データと下位階層の地図データとの接続情報となる。これにより、下位階層の地図データでルート探索が完了した状態を、上位階層と下位階層に共通して存在するノード（下位階層のＮｏ．ｐと上位階層のＮｏ．ｋ）を通して移し替える。そして、上位階層の地図データに下位階層での探索が済んだノードの状態を移し替えた後に、上位階層の地図データでルート探索を進めることによりルート探索の上位階層への移行が完了する。
【００２２】
図７は道路リンクを使用した下位階層から上位階層への移行動作を説明する図である。図７において、下位階層の地図データで、上記アルゴリズムによるルート探索を行なってその地図データ中のリンク（下位地図データのリンクＮｏ．１およびＮｏ．２）が選択される。これらのリンクが上位地図データの特定のリンク  （上位地図データリンクＮｏ．２）に対応するものであるときは、下位階層の地図データのリンクテーブル４２内のリンクデータには、図８に示すように、当該下位階層の地図データにおけるリンク（Ｎｏ．１、Ｎｏ．２）は上位階層の地図データＮｏ．ｍのリンク番号Ｎｏ．２が対応し、そのリンクの到達先ノードはノードＮｏ．ａ、Ｎｏ．ｂであることが記述されている。これにより、下位階層の地図データでルート探索が完了した状態を、上位階層と下位階層に共通して存在するリンクを接続情報として移し替える。この共通リンクにより階層を移行する場合は、下位階層の地図データから上位階層の地図データへルート探索処理を移行する際に、下位階層のノードに対応するノードが上位階層の地図データに存在しなくても、上位階層の対応するリンクに含まれる点（すなわち上位階層と下位階層に共通して存在するリンクの端点）であればよい。したがって、上位の階層の地図データの上記対応するリンクの両端のノードを探索済みの状態に設定することができ、処理の高速化が図れる。
【００２３】
【発明の効果】
本発明は、以上の説明から明らかなように、車載用ナビゲーション装置に、地図データを、道路網の情報量を基に階層構造にして道路網の情報の多い下位階層から、道路網の情報の少ない上位階層への階層を展開するとともに、各階層間において共通する道路を対応付けた接続情報を有するデータ構造とし、この地図データに基づき、指定された出発地および目的地を含む階層を特定し、前記各階層間の接続情報に基づき、特定された階層において上位階層へ接続する点までルート探索を行ない、さらに上位階層に移行して前記接続点からのルート探索を繰り返し行なうようにし、地図データには、上位／下位の階層にわたるリンクについて、上位階層の地図データのリンクを下位階層の地図データのリンクに対応付けて記述され、上位階層の地図データのリンク形状を下位階層の地図データに格納し、下位階層のルート探索に際して、当該下位階層のリンクが上位階層のリンクに対応したときルート探索を下位階層から上位階層へ移行させ、前記下位階層から上位階層へルート探索を移行したとき、上位階層の対応するリンクの両端までルート探索処理を完了可能にしたため、ルート探索が高速に行なわれるのみでなく、ルート探索の結果得られたルートを表示するに際しても高速で表示することができるようになり、ルート探索による経路案内処理操作全体の高速化を図ることができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態における車載用ナビゲーション装置の構成を示すブロック図
【図２】前記実施の形態において用いられる地図データのフォーマット例を示す図
【図３】前記実施の形態における地図データのフォーマットの一例を別の表現で表して説明する図
【図４】前記実施の形態における１つの階層における地図データ内の管理情報のデータフォーマットの一例を示す図
【図５】前記実施の形態においてルート探索を行なうときのアルゴリズムを説明するための一モデル図
【図６】前記実施の形態における道路ノードを使用した下位階層から上位階層への移行動作を説明する図
【図７】前記実施の形態における道路リンクを使用した下位階層から上位階層への移行動作を説明する図
【図８】前記実施の形態における下位階層の地図データにおけるリンクと上位階層の地図データにおけるリンクとの対応を示すデータ構成図
【図９】従来のナビゲーション装置におけるルート探索手法を説明する図
【符号の説明】
１  方位センサ
２  距離センサ
３  センサー信号
４  センサー信号処理部
５  ＧＰＳレシーバ
６  ＣＤ−ＲＯＭドライバー
７  ＣＤ−ＲＯＭ
８  表示・操作部
８Ａ  液晶ディスプレー
９  装置本体
１０  ＣＰＵ  （中央処理装置）
１１  ＲＯＭ（リードオンリーメモリ）
１２  メモリ（ＤＲＡＭ）
１３  バックアップ用メモリ（ＳＲＡＭ）
１４  メモリ（漢字、フォントＲＯＭ）
１５  画像プロセッサ
１６  メモリ（ＶＲＡＭ）
１７  ＲＧＢ変換回路
１８  通信インタフェース
２０  ディスクラベル
２１  描画パラメータ
２２  図葉管理情報
２３、２４  図葉
３１  地図データの全体構成
３２  管理情報
３３  上位の地図データ
３４  中位の地図データ
３５  下位の地図データ
３６  上位地図のアドレスとサイズのテーブル
３７  中位地図のアドレスとサイズのテーブル
３８  下位地図のアドレスとサイズのテーブル
４０  アドレス・サイズテーブル
４１  ノードテーブル
４２  リンクテーブル
４３  ノード座標テーブル
４４  リンク形状テーブル
【図１】
0003547644.tif 000002
【図２】
0003547644.tif 000003
【図３】
0003547644.tif 000004
【図４】
0003547644.tif 000005
【図５】
0003547644.tif 000006
【図６】
0003547644.tif 000007
【図７】
0003547644.tif 000008
【図８】
0003547644.tif 000009
【図９】
0003547644.tif 000010