(57)【特許請求の範囲】
【請求項１】
一階層構造の道路地図データを用いて、出発地から目的地までの経路を探索する経路探索方法において、
経路探索の広がりに応じて、前記道路地図データの階層化を行い、前記階層化で得られた道路地図データを用いて経路探索を続けることを特徴とする経路探索方法。
【請求項２】
前記道路地図データの階層化を、前記道路地図データに含まれるリンクの道路ランクまたは道路種別に基づいて行うことを特徴とする請求項１に記載の経路探索方法。
【請求項３】
前記道路地図データの階層化を、前記道路地図データが格納された記憶媒体から前記道路地図データのユニットを読み込むときに行うことを特徴とする請求項１または２に記載の経路探索方法。
【請求項４】
前記道路地図データの階層化を、ノードに接続する接続リンクの中から経路探索の対象となるリンクを選択するときに行うことを特徴とする請求項１または２に記載の経路探索方法。
【請求項５】
前記一階層構造の道路地図データの地図データフォーマットにおけるリンクレコードの並び順を、道路ランク順に設定することを特徴とする請求項１に記載の経路探索方法。
【請求項６】
前記階層化で得られた道路地図データの上位階層への移行の後、下位階層への移行を行い、前記出発地及び目的地の一方から他方に至る片方向の探索により経路を求めることを特徴とする請求項１に記載の経路探索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ナビゲーション装置での経路探索方法に関し、特に、一階層の地図データを用いて経路探索を高速で行うことを可能にするものである。
【０００２】
【従来の技術】
従来のナビゲーション装置は、道路地図データが蓄積されたＣＤ−ＲＯＭやＤＶＤなどの記録装置を具備し、出発地及び目的地が入力されると、出発地から目的地に至る地図上の最適経路を探索する経路探索機能を備えている。また、特開平８−１２８８４３号、特開平８−３３４３７５号、特開平１１−２４８４７４号などの各公報に記載されているように、従来のナビゲーション装置は、経路探索の高速化を図るため、記録装置に詳細度の異なる多階層の道路地図データが蓄積されており、それを用いて経路探索が行われる。
【０００３】
図９は、多階層の道路地図データの一例として三階層で構成された道路地図データを模式的に示している。道路地図データは、交差点を表すノードデータと、各ノード間の道路を表すリンクデータとを含んでおり、ノードデータは、各ノードについて、当該ノードを一意に表すノード番号、当該ノードの緯度経度座標、当該ノードに接続するリンク番号などが記述されたノードレコードの集まりで構成され、また、リンクデータは、各リンクについて、当該リンクを一意に表すリンク番号、距離や旅行時間などで表された当該リンクのコスト、道路種別や車線数などを示す当該リンクの属性、当該リンク両端に接続するノードのノード番号などが記述されたリンクレコードの集まりで構成される。
【０００４】
最下位階層であるレベル０の階層の道路地図データは、ランク２に属する高速道路や国道などのリンクデータと、ランク１に属する県道などのリンクデータと、ランク０に属する市道などのリンクデータと、各リンク間のノードデータとで構成され、その上のレベル１の階層の道路地図データは、ランク２のリンクデータと、ランク１のリンクデータと、それらのリンク間のノードデータとで構成され、また、最上位階層に当たるレベル２の道路地図データは、ランク２のリンクデータと、そのリンク間のノードデータとで構成されている。
【０００５】
図９は、同一領域に対応する各レベルの道路地図データで表される道路形状を模式的に示しており、また、図１０は、各レベルの道路地図データに含まれるリンクレコードを示している。
【０００６】
この多階層の道路地図データを用いて、出発地及び目的地の周辺は、詳細なレベル０の地図データで、また、中間経路は、より粗いレベル１やレベル２の地図データで探索が行われる。従来から広く知られているボトムアップ方式の経路探索方法では、出発地及び目的地の両方からレベル０の地図データに基づいて経路探索が開始される。そして、探索経路がランク１の道路のノードに到達すると、レベル１の地図データを用いて経路探索が続けられ、出発地及び目的地の各々から探索を進めた経路がランク２の道路のノードに到達すると、レベル２の地図データを用いて、それらのノードを連結するランク２の経路が探索され、出発地から目的地に至る最適経路が求められる。
【０００７】
また、各階層の道路地図データは、それぞれ、複数のブロックに分割されて記録装置に記録されており、探索に必要なブロックの地図データだけが、記録装置から順次読み出される。こうすることにより、１回に読み出す地図データの量を少なくすることができ、地図データのアクセスに要する時間を短縮化できる。
【０００８】
この場合、各ブロックにおいて、周辺ブロックとの境界で、そこを横切る道路が分断される。各ブロック間でこの分断された道路の対応関係が取れるように、図９に示すように、ブロックの周辺の道路位置には仮想ノードが設けられる。
【０００９】
また、仮想ノードを用いない方式では、前記特開平１１−２４８４７４号公報に記載されているように、各ブロックの周囲に、周辺ブロックに重なるオーバーラップ領域を設け、当該ブロックとオーバーラップ領域とを合わせた領域を１区画として、記録装置に地図データが記録される。
【００１０】
このナビゲーション用の多階層道路地図データは、メーカーが、一階層の道路地図データベースから、各階層の地図データを抽出し、さらに、階層間の移行に必要な上下階層の対応データを付加して作成しており、作成された道路地図データがＣＤ−ＲＯＭやＤＶＤ等の記録媒体に記録され、ナビゲーション装置に搭載される。
【００１１】
【発明が解決しようとする課題】
多階層の道路地図データを用いる経路探索方法は、経路探索の高速化を図る上で極めて有効な方法であるが、しかし、次のような問題点を有している。
【００１２】
道路が新設されたり、道路の一部区間が変更されたりすると、道路地図データの更新が必要になる。従来、ナビゲーション装置に保持された道路地図データの更新は、道路地図データが蓄積された記録媒体を交換することによって行われており、多階層の道路地図データを更新する場合は、まず、基になる一階層の道路地図データベースを更新し、このデータベースから生成した多階層の道路地図データを記録媒体に記録して、ナビゲーション装置の古い記録媒体と入れ換えている。
【００１３】
しかし、記録媒体の交換は、コストが嵩み、また、データ更新の即時性に欠けるため、道路地図データの変更箇所のデータを放送や通信でダウンロードし、それに基づいて、ナビゲーション装置の記録媒体のデータを更新する差分更新の方法が検討されている。
【００１４】
ただし、ナビゲーション装置に保持された多階層の道路地図データに対して差分更新を適用することは実際上不可能である。これは、階層化された道路地図データでは、更新すべき地図データが複数のレベルの道路地図データに及ぶためであり、図９の例で云えば、高速道路のリンクデータが更新された場合、レベル０、レベル１及びレベル２の全ての道路地図データを更新し、さらに、それに伴って上下階層の対応データを更新しなければならない。これらの処理を差分データのダウンロードで行うことは、極めて難しい。
【００１５】
そうかと云って、一階層の地図だけを用いて経路探索を行うことは、探索に多くの時間が掛かり、探索性能の劣化が著しい。
【００１６】
本発明は、こうした課題に応えるものであり、差分更新が可能な道路地図データを用いて、高速で経路探索を行うことができる経路探索方法を提供することを目的としている。
【００１７】
【課題を解決するための手段】
そこで、本発明では、一階層構造の道路地図データを用いて、出発地から目的地までの経路を探索する経路探索方法において、経路探索の広がりに応じて、前記道路地図データの階層化を行い、階層化で得られた道路地図データを用いて経路探索を続けるようにしている。
【００１８】
そのため、一階層構造の道路地図データに対して、差分更新を適用することができ、また、動的な階層化により、経路探索の高速化を図ることができる。
【００１９】
【発明の実施の形態】
本発明の実施形態の経路探索方法を実施するナビゲーション装置は、図１に示すように、ＣＤ−ＲＯＭやＤＶＤ等の光ディスク、ハードディスク、大容量メモリ等で構成される、道路地図データを記憶する道路地図データ記憶部１と、ＧＰＳ、車速センサ、角速度センサ、絶対方位センサなどを含み、現在位置を検出する現在位置検出部２と、リモートコントローラ、タッチセンサ、キーボード、マウス等によりユーザが入力操作を行う操作部３と、地図情報や誘導経路情報などを画像や音声で表示する表示部６と、操作部３から入力されたデータや道路地図データ記憶部１から読み込まれたデータなどを記憶するメモリ５と、各部を制御して経路探索処理を実行する中央制御部４とを備えている。
【００２０】
道路地図データ記憶部１には、図２に示すように、一階層構造の道路地図データが複数のブロックに分割されて格納されている。このブロックの１つずつは地図の管理単位であり、この管理単位を「ユニット」と呼ぶことにする。この実施形態では、前述する仮想ノードを持つブロックをユニットとする場合について説明するが、オーバーラップ領域を持つブロックをユニットとすることも可能である。
【００２１】
各ユニットの道路地図データにおけるリンクデータは、図３に示すように、ランク２の道路のリンクレコード、ランク１の道路のリンクレコード、次いで、ランク０の道路のリンクレコードの順番で、道路ランクの高い順に道路地図データ記憶部１に格納されている。
【００２２】
この装置の中央制御部４は、経路探索処理を進める過程で、必要が生じたときに、一階層構造の道路地図データに含まれる特定の道路ランクのデータだけに着目することにより、動的に道路地図データの階層化を行う。
【００２３】
この動的な階層化は、例えば、メモリ５に蓄積するためのユニット単位の道路地図データを道路地図データ記憶部１から読み込む際に行われる。
【００２４】
図４は、この場合の動的な階層化の様子を示している。道路地図データ記憶部１には、図４（ａ）に示す一階層構造の道路地図データが格納されている。ここで、道路に付した数字は、リンクレコードにリンク属性として記述された道路ランクを表している。
【００２５】
中央制御部４は、レベル２の階層の道路地図データを必要とする場合に、図４（ａ）の道路地図データから道路ランク２のリンクのみを抽出して、図４（ｂ）に示す道路地図データをメモリ５に蓄積する。このとき、元の道路地図データのリンクデータから抽出されるリンクレコードの範囲を図３にレベル２として示している。また、レベル１の階層の道路地図データを必要とする場合は、図４（ａ）の道路地図データから道路ランク２及び道路ランク１のリンクを抽出して、図４（ｃ）に示す道路地図データをメモリ５に蓄積する。このとき、元の道路地図データのリンクデータから抽出されるリンクレコードの範囲を図３にレベル１として示している。また、レベル０の階層の道路地図データを必要とする場合は、図４（ａ）の道路地図データの全てを抽出して、図４（ｄ）に示す道路地図データをメモリ５に蓄積する。このとき、元の道路地図データのリンクデータから抽出されるリンクレコードの範囲を図３にレベル０として示している。
【００２６】
こうして動的に階層化された道路地図データの各々は、従来の多階層の道路地図データ（図９）の各階層の道路地図データに対応している。ただ、動的な階層化で得られた道路地図データでは、レベル１やレベル２など、上位階層の道路地図データの中に、道路ランクが低い道路との交差点を示すノードが含まれており、この点が従来の多階層の道路地図データと相違している。
【００２７】
動的な階層化により道路地図データ記憶部１から読み込むユニット単位の道路地図データのレベルは、操作部３から入力された出発地（現在位置検出部２で検出された現在位置を出発地としても良い）及び目的地からの距離に応じて設定することができる。
【００２８】
図７は、動的な階層化により順次読み込まれたユニット単位の道路地図データを、探索経路に沿って模式的に一覧表示している。ユニット内の左上の数字は、当該ユニットを読み込む際の指定レベルを表しており、出発地及び目的地が属するユニットではレベル０を指定し、出発地及び目的地から近い隣接ユニットではレベル１を指定し、また、出発地及び目的地から遠く離れたその他のユニットではレベル２を指定している。
【００２９】
また、動的な階層化は、ノードに接続するリンクの中から経路探索の対象とすべき接続リンクを選択する場合にも行われる。図５は、この場合の動的な階層化の様子を示している。いま、道路ランク１のリンクＡから探索が進み、ノードＢに到達したとする。ノードＢには、道路ランク１のリンクＣ、道路ランク２のリンクＤ、及び道路ランク０のリンクＥが接続している。このとき、道路ランク１以上の接続リンクを辿って探索を広げる場合には、中央制御部４は、メモリ５に蓄積された道路地図データの中からリンクＣ及びリンクＤのリンクデータだけを読み込み、探索を実行する。
【００３０】
このように、接続リンクの選択に当たって、動的な階層化を行うことにより、経路探索の効率化が可能になる。動的な階層化によって選択する接続リンクのレベルは、出発地及び目的地からの距離に応じて設定することができる。図８は、出発地Ａからの距離に応じて接続リンクのレベルを設定して、経路探索を実施したときの経路探索の広がりを示している。この場合、出発地Ａから半径Ｒ１の範囲内では、レベル０の道路地図データに含まれる接続リンクを経路探索の対象に指定し、出発地Ａから半径Ｒ１〜Ｒ２の範囲内では、レベル１の道路地図データに含まれる接続リンクのみを経路探索の対象に指定し、また、出発地Ａから半径Ｒ２を超える範囲では、レベル２の道路地図データに含まれる接続リンクのみを経路探索の対象に指定している。
【００３１】
また、目的地の近傍においても、同様に、目的地からの距離に応じて、経路探索の対象にすべき接続リンクを指定することができる。
【００３２】
図６は、この装置の中央制御部４が、道路地図データの動的な階層化を行いながら、経路探索を実行する手順を示している。
ステップ１：道路地図データ記憶部１から、出発地が属するユニットのレベル０の道路地図データをメモリ５に読み込み、出発地リンクを設定する。
ステップ２：出発地及び目的地からの距離に応じて設定したレベル以上の接続リンクを辿り、探索を広げる。この探索は、探索経路がユニットの仮想ノードに達し、隣接ユニットの読み込みが必要になるまで続ける。
ステップ３：隣接ユニットの読み込みが必要になると、
ステップ４：道路地図データ記憶部１から、出発地及び目的地からの距離に応じて設定したレベルの隣接ユニットの道路地図データをメモリ５に読み込む。
ステップ５：目的地リンクに到達するまで、ステップ２以降の手順を繰り返し、目的地リンクに到達すると、経路探索処理を終了する。
経路探索の結果は、表示部６に表示される。
【００３３】
この装置では、図６の手順に従って、一階層構造の道路地図データの出発地から経路探索を広げながら、この広がりに応じて動的に道路地図データの階層化を行い、階層化で得られた上位階層の道路地図データへの移行を順次行う。また、探索経路が目的地に近づくと、動的な階層化で得られた下位階層の道路地図データに順次移行し、最終的に一階層構造の道路地図データの目的地への経路を探索する。また、逆に、目的地を経路探索のスタート地点とし、上位階層移行の後、出発地の近くで下位階層に移行し、目的地から出発地に至る経路を探索するようにしても良い。
【００３４】
このように、本発明の経路探索方法では、片方向からの探索が可能であるが、これは、動的な階層化で得られる上位階層の道路地図データに、下位階層への下り口となるノードのデータが含まれているためである。出発地及び目的地の両方向から経路探索を開始する従来方式では、経路探索処理の二分化で演算が複雑になり、また、両方向から突き合わせた経路が最適経路であるかどうかの判定が難しいが、片方向からの経路探索では、こうした複雑な要素が無く、経路探索処理の演算が容易である。
【００３５】
また、ここでは、図３に示すように、リンクデータでのリンクレコードの並び順が道路ランクの高い順となるように、道路地図データ記憶部１に格納する道路地図データのフォーマット（ＰＳＦ）を設定している。そのため、道路地図データ記憶部１からユニット単位の上位階層の道路地図データを読み込んで動的な階層化を行う場合に、道路地図データ記憶部１の狭い領域に格納されたデータを読み込むだけで足りるので、動的な階層化を高速で行うことができる。
【００３６】
また、道路地図データ記憶部１に格納する道路地図データは一階層構造であるため、この道路地図データに対して差分更新を行うことが可能である。
【００３７】
なお、ここでは、動的な階層化を、リンクレコードのリンク属性に記述された道路ランクに基づいて行う場合について説明したが、リンク属性の道路種別を基に階層化を行うことも可能である。
【００３８】
【発明の効果】
以上の説明から明らかなように、本発明の経路探索方法では、差分更新が可能な一階層の道路地図データを用いて、経路探索を高速で行うことができる。従って、差分更新の適用による道路地図データの高精度化と、経路探索の高性能化との両立が可能であり、最適経路を的確に、且つ、短時間で探索することが可能となる。
【図面の簡単な説明】
【図１】本発明の実施形態における経路探索方法を実施する装置の構成を示すブロック図、
【図２】実施形態の経路探索方法で使用する一階層の道路地図データを示す図、
【図３】実施形態の経路探索方法で使用する一階層の道路地図データのリンクデータの構造を示す図、
【図４】実施形態の経路探索方法によりユニット単位を対象として動的な階層化を行う処理を説明する図、
【図５】実施形態の経路探索方法により接続リンクを対象として動的な階層化を行う処理を説明する図、
【図６】実施形態の経路探索方法の手順を示すフロー図、
【図７】実施形態の経路探索方法で使用する道路地図データの階層化レベルを経路に沿って示す図、
【図８】実施形態の経路探索方法により出発地からの距離に応じて接続リンクの階層を選択した経路探索の広がりを示す図、
【図９】従来のナビゲーション装置に格納された多階層の道路地図データを示す図、
【図１０】従来のナビゲーション装置に格納された多階層の道路地図データのリンクデータの構造を示す図である。
【符号の説明】
１  道路地図データ記憶部
２  現在位置検出部
３  操作部
４  中央制御部
５  メモリ
６  表示部
【図１】
0003789306.tif 000002
【図２】
0003789306.tif 000003
【図３】
0003789306.tif 000004
【図４】
0003789306.tif 000005
【図５】
0003789306.tif 000006
【図６】
0003789306.tif 000007
【図７】
0003789306.tif 000008
【図８】
0003789306.tif 000009
【図９】
0003789306.tif 000010
【図１０】
0003789306.tif 000011