トップ :: G 物理学 :: G01 測定;試験




【発明の名称】 経路設定装置及びナビゲーション装置
【発明者】 【氏名】石嵜 貴士

【氏名】近江 眞宜
【要約】 【課題】復帰経路の計算に要する時間を増大させずに、その復帰経路の計算に用いる道路データを多くして経路品質を向上させる。

【解決手段】復帰点をコスト計算開始点１としてコスト計算を実行し記憶しておく。経路離脱時には、コスト計算結果に基づき、現在地２から復帰点１に至るまでの総コストが小さくなるリンクの接続にて復帰ルート３を設定する。ダイクストラ法では「コスト計算完了後は、計算開始点から計算範囲すべての地点への経路を計算できる」という特性があるため、復帰点１を計算開始点としてコスト計算を実行すれば、その計算結果を用いて、計算開始点１から計算範囲すべての地点への経路を計算できる。したがって、実際に経路を離脱した時の復帰ルート３の設定処理が非常に短時間でできる。また、コスト計算自体は比較的時間に余裕がある期間に行うので、多くの道路データを用いても問題なく、経路品質が向上する。
【特許請求の範囲】
【請求項１】ノード間を接続するリンクのリンク情報とリンク間の接続情報とに基づき、ダイクストラ法あるいはそれに準ずる探索手法を用いて計算開始点から各ノードに至るまでの最小の経路評価値を算出する評価値計算処理を行い、その評価値計算処理の結果に基づき、出発地から目的地に至るまでの総評価値が小さくなるリンクの接続によって目的地経路を設定する経路設定装置において、現在地を検出する現在地検出手段と、その現在地検出手段によって検出された現在地に基づき、経路を離脱したか否かを判定する経路離脱判定手段と、その経路離脱判定手段によって経路を離脱したと判定される以前に、その時点で使用中の道路データに基づき、前記目的地経路上の所定の復帰点を前記計算開始点として前記評価値計算処理を実行する復帰経路用評価値計算処理手段と、その復帰経路用評価値計算処理手段にて計算された結果を記憶しておく評価値計算結果記憶手段と、前記経路離脱判定手段によって経路を離脱したと判定された場合には、前記評価値計算結果記憶手段に記憶された評価値計算結果に基づき、現在地から前記復帰点に至るまでの総評価値が小さくなるリンクの接続によって復帰経路を設定する復帰経路設定手段とを備えていることを特徴とする経路設定装置。
【請求項２】請求項１記載の経路設定装置において、前記復帰点は、その使用中の道路データ内に存在する前記目的地経路上であり、且つ離脱地点よりも目的地側であって、離脱地点から前記目的地経路の道のりにおいて最も遠い位置である最遠点であることを特徴とする経路設定装置。
【請求項３】請求項１又は２記載の経路設定装置において、前記復帰経路用評価値計算処理手段は、前記現在地検出手段によって検出された現在地に基づき、道路データの境界を通過したか否かを判定し、道路データの境界通過の場合には、前記復帰経路用の評価値計算処理を実行し、前記評価値計算結果記憶手段は、前記復帰経路用評価値計算処理手段によって前記復帰経路用の評価値計算処理が実行される毎に、その計算結果を更新記憶しておくことを特徴とする経路設定装置。
【請求項４】請求項３記載の経路設定装置において、前記復帰経路用評価値計算処理手段は、前記道路データの境界をｎ回（ｎは自然数）通過する毎に、前記復帰経路用の評価値計算処理を実行することを特徴とする経路設定装置。
【請求項５】請求項１〜４のいずれか記載の経路設定装置において、前記復帰経路用評価値計算処理手段は、前記目的地を前記復帰点として前記復帰経路用の評価値計算処理を実行した場合には、その後、前記道路データの境界を通過しても、前記復帰経路用の評価値計算処理を実行しないことを特徴とする経路設定装置。
【請求項６】請求項１〜５のいずれか記載の経路設定装置において、前記道路データは、同一地域が複数の階層の道路データにてカバーされていると共に、上位階層の道路データほど広い地域をカバーするが収録している道路が限定されており、前記復帰経路用評価値計算処理手段は、前記複数階層の道路データを用いて前記復帰経路用の評価値計算処理を実行することを特徴とする経路設定装置。
【請求項７】請求項６記載の経路設定装置において、前記現在地について最下層の道路データを用いることを特徴とする経路設定装置。
【請求項８】請求項６又は７記載の経路設定装置において、前記目的地が使用中の上位階層の道路データ中に含まれている場合には、目的地の両方について最下層の道路データを用いることを特徴とする経路設定装置。
【請求項９】請求項１〜８のいずれか記載の経路設定装置において、前記評価値計算結果記憶手段は、２つの記憶領域を有しており、一方の記憶領域に既に計算結果が記憶されている場合には、他方の記憶領域を利用して前記復帰経路用評価値計算処理手段による計算がなされ、その計算結果が当該記憶領域に記憶された後で、もう一方の記憶領域内の計算結果が消去されることを特徴とする経路設定装置。
【請求項１０】請求項１〜９のいずれか記載の経路設定装置と、その経路設定装置によって設定された経路に対する走行案内を行う案内手段とを備えたことを特徴とするナビゲーション装置。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、目的地までの経路を設定し、さらにその目的地経路から離脱した場合の復帰経路の設定も可能な経路設定装置、及びその設定された経路に対する走行案内を行うナビゲーション装置に関する。
【０００２】
【従来の技術】車両の走行に伴ってＧＰＳ等により現在位置を検出し、その現在位置をディスプレイ上に道路地図と共に表示したり、現在地から目的地までの適切な経路を設定して走行案内するナビゲーションシステムが知られ、より円滑なドライブに寄与している。また、一旦設定した目的地経路から車両が離脱してしまった場合であっても、自動的に、あるいはユーザの指示に従って、元の経路に復帰するための復帰経路を設定できるようにされている。
【０００３】この復帰経路の設定に際しては、従来、車両の現在地が含まれる道路データを用いて行っていた。具体的には、現在使用中の道路データ内に存在する目的地経路上であって、現在地から最も遠くに位置する最遠点を計算終了点として現在地からの経路計算を行う。このようにして計算した経路を復帰経路とし、計算終了点である最遠点以降の経路については、離脱前の経路である目的地経路を再利用する。これによって、離脱後の現在地から目的地までの経路を再計算するよりも短時間で復帰経路を提供することができる。
【０００４】
【発明が解決しようとする課題】しかしながら、このような復帰経路の設定においては、次のような問題が発生する。例えば、使用する道路データが１辺４Ｋｍの矩形領域であったと仮定すると、上述した復帰点までの距離は、１辺４Ｋｍの矩形領域の対角長である５．７Ｋｍ程度がその上限となる。したがって、例えば山岳道路やバイパス道路などの場合で発生し易い状況であるが、使用中の道路データにおいて、離脱位置と復帰点の間に交差点が存在しない場合には、復帰経路が、離脱位置よりも後戻りするように設定されてしまう可能性がある。
【０００５】一方、隣接する道路データまで用いることによって復帰点をより遠くに設定できるようにすることはできるが、その場合には、次のような問題が生じる。つまり、従来技術においては、離脱後なるべく早期に復帰経路を設定することを目的としているため、経路計算に用いる道路データを減らすことで、経路品質はある程度犠牲にしてまでも早期に復帰経路を設定することを選択している。したがって、このように道路データを増やして従来手法をそのまま採用すれば、それは復帰経路の早期設定という根本的な要求を無視したものとなる。
【０００６】そこで本発明は、復帰経路の計算に要する時間を増大させずに、その復帰経路の計算に用いる道路データを多くして経路品質を向上させることを目的とする。
【０００７】
【課題を解決するための手段及び発明の効果】上記目的を達成するためになされた本発明の経路設定装置は、ノード間を接続するリンクのリンク情報とリンク間の接続情報とに基づき、ダイクストラ法あるいはそれに準ずる探索手法を用いて計算開始点から各ノードに至るまでの最小の経路評価値（経路コストとも称す）を算出する評価値計算処理を行い、その評価値計算処理の結果に基づき、出発地から目的地に至るまでの総評価値が小さくなるリンクの接続によって目的地経路を設定することを前提とする。
【０００８】ここで、復帰経路用評価値計算処理手段が、経路離脱判定手段によって経路を離脱したと判定される以前に、その時点で使用中の道路データに基づき、目的地経路上の所定の復帰点を計算開始点として評価値計算処理を実行する。この計算結果は評価値計算結果記憶手段に記憶される。そして、復帰経路設定手段が、経路離脱判定手段によって経路を離脱したと判定された場合には、評価値計算結果記憶手段に記憶された評価値計算結果に基づき、現在地から復帰点に至るまでの総評価値が小さくなるリンクの接続によって復帰経路を設定する。
【０００９】本発明の復帰経路の設定に際しては、ダイクストラ法あるいはそれに準ずる探索手法における次のような特性を利用している。すなわち、「評価値計算処理の完了後は、計算開始点から計算範囲すべての地点への経路を計算することができる」という特性である。この特定を用い、上述したように、目的地経路上の所定の復帰点を計算開始点として評価値計算処理を実行すれば、その計算結果を用いることで、計算開始点から計算範囲すべての地点への経路を計算することができる。したがって、経路離脱時に、現在地から復帰点に至るまでの総評価値が小さくなるリンクの接続によって復帰経路を設定するのが非常に短時間でできることとなる。
【００１０】従来手法の場合には、経路離脱後に復帰経路を早期に設定するため、復帰経路を設定するために用いる道路データをなるべく少なくしていた。上述例で言えば、４Ｋｍ四方の道路データのみ用いることとなる。したがって、必然的に経路品質はある程度犠牲になる。つまり、経路品質が落ちることを許容する代わりに復帰経路の早期設定というメリットを享受していたのである。
【００１１】それに対して、本発明の場合には、上述したように、実際に経路離脱時に行う復帰経路の設定は短時間で実現できるため、復帰経路の早期設定というメリットは享受できる。そして、従来手法では犠牲にしていた経路品質については、評価値計算処理をどのようにするかによって決まる。評価値計算処理は、経路離脱前に行うため、相対的に十分な時間がある。つまり、従来手法のような経路の早期設定の要求に応えるために時間が極端に制限されることはない。そのため、相対的に広い範囲の道路データを評価値計算処理の対象とすることができ、結果として経路品質を向上させることができる。このように、本発明の経路設定装置によれば、復帰経路の計算に要する時間を増大させずに、その復帰経路の計算に用いる道路データを多くして経路品質を向上させることが可能となる。
【００１２】なお、復帰点に関しては、例えば請求項２に示すような最遠点を採用することが好ましい。ここで、最遠点とは、次のように定義される。つまり、使用中の道路データ内に存在する目的地経路上であり、且つ離脱地点よりも目的地側であって、離脱地点から目的地経路の道のりにおいて最も遠い位置である。なお、当然ながら、使用中の道路データ内に目的地が存在する場合には、上記定義より、その目的地が最遠点として設定される。
【００１３】ここで、従来手法と本発明手法との差異により明確にするため、図面を参照して説明する。最初に、図１０中に示した番号（１〜８）について説明する。「１」は現在地の位置する道路データであり、例えば４Ｋｍ四方といった比較的狭い範囲をカバーするものである。「２」は元の経路（つまり既に設定されて案内に用いられていた目的地経路）であり、「３」は現在地である。また、「４」は理想の復帰ルートであり、「５」従来技術での復帰ルート、「６」は従来技術での復帰点を示している。さらに、「７」は隣接する道路データであり、「８」は本発明での復帰点である。
【００１４】従来手法においては、図１０で言えば、経路を離脱してから、現在地の位置する道路データ１のみを用いて復帰経路を設定していた。その際の復帰点６は、現在地の位置する道路データ１における最遠点である。この状況では、図１０中に「５」で示したルートが復帰ルートとして設定されることとなる。しかし、隣接する道路データ７も加味して考えると、結果的に、従来技術での復帰ルート５は遠回りしていることが判る。
【００１５】これに対して、本発明の場合には、隣接する道路データ７を用いても、経路離脱時に行う復帰経路の設定処理に要する時間が短くて済む。そのため、隣接する道路データ７まで加味した場合の復帰点８は、その隣接道路データ７を含めた最遠点となる。このようにすれば、理想の復帰ルート４を設定することができる。なお、この図１０では判りやすいように隣接する道路データまでを用いた具体例として説明したが、上述したように、評価値計算処理は経路離脱前に行うため、相対的に十分な時間がある。したがって、さらに広範囲の道路データを用いても問題なく、経路品質のさらなる向上を期待できる。
【００１６】ところで、復帰経路用評価値計算処理手段による計算タイミングとしては、請求項３に示すようにすることが考えられる。すなわち、現在地検出手段によって検出された現在地に基づき道路データの境界を通過したか否かを判定し、道路データの境界通過の場合には、復帰経路用の評価値計算処理を実行する。そして、復帰経路用評価値計算処理手段によって復帰経路用の評価値計算処理が実行される毎に、その計算結果を評価値計算結果記憶手段に更新記憶しておくことが考えられる。
【００１７】上述したように、評価値計算処理は経路離脱前に行う必要がある。但し経路離脱はいつ発生するかは判らない。そこで、道路データの境界を通過した場合に評価値計算処理を行っておけば、その後、どのようなタイミングで経路離脱が生じても、その計算結果を用いることができる。
【００１８】なお、請求項４に示すように、道路データの境界をｎ回（ｎは自然数）通過する毎に、復帰経路用の評価値計算処理を実行することが考えられる。ｎ＝１であれば、道路データの境界を通過する度に評価値計算処理を実行し、例えばｎ＝３であれば、３つの道路データの境界を通過する度に実行することとなる。毎回実行すればそれだけ精度は上がるが、処理負荷は増えるので、それらのバランスを考えてｎは設定すればよい。
【００１９】また、目的地を復帰点として復帰経路用の評価値計算処理を実行した場合には、その後に計算結果を更新記憶する必要はない。したがって、請求項５に示すように、そのような場合は、その後に道路データの境界を通過しても、復帰経路用の評価値計算処理を実行しないようにする。
【００２０】なお、評価値計算処理に用いる道路データとしては、例えば請求項６に示すように、複数階層の道路を用いることが考えられる。すなわち、同一地域が複数の階層の道路データにてカバーされていると共に、上位階層の道路データほど広い地域をカバーするが収録している道路が限定されているような道路データを用いる。例えば３層構造の場合、最下層である第１層の道路データが４Ｋｍ四方の領域をカバーしている場合、一つ上の階層である第２層の道路データは１６Ｋｍ四方の領域をカバーし、最上層である第３層の道路データは６４Ｋｍ四方の領域をカバーするように設定しておくのである。
【００２１】このように、複数階層の道路データを用いて復帰経路用の評価値計算処理を実行すると、次のような利点がある。
（１）復帰経路の品質のさらなる向上が期待できる。例えば、カバーする領域が最も狭い最下層の道路データのみを用いる場合には、元の経路が含まれる道路データをつなげていくと細長くなるため、復帰点を延長するほど計算範囲は細長くなる。したがって、設定される復帰経路は、元の経路に沿ったものとなる。しかし、元の経路に沿わない方がより適切な復帰経路となる場合もある。
【００２２】このような場合、上位階層の道路データを用いると、計算範囲が細長くなる事態を防止することが可能であるため、その場合には、より適切な復帰経路を設定できる可能性が高くなる。
（２）復帰点をさらに延長することができる。
【００２３】上述した３層構造の道路データを例にとって説明する。例えば４Ｋｍ四方の第１層の道路データのみを用いて１００Ｋｍ先を復帰点とするためには、２５枚の道路データが必要となる。これに対して、１６Ｋｍ四方の第２層の道路データも用いる場合には、第２層の道路データを７枚（１１２Ｋｍ分）と第１層の道路データ１枚の計８枚の道路データで済む。さらに、６４Ｋｍ四方の第３層の道路データも用いる場合には、第３層の道路データを２枚（１２８Ｋｍ分）と第２層の道路１枚、第１層の道路データ１枚の計４枚の道路データで済む。
【００２４】つまり、同じ復帰点までの距離を確保しようとする場合であっても、上位階層の道路データを用いれば使用する道路データ数を減らすことができる。評価値計算処理は経路離脱前に実行するため、相対的に時間の余裕があるとは言え、経路離脱がいつ生じるかが判らないことを鑑みると、早期に処理を終えることが好ましい。したがって、所定の処理時間内に処理を終了させることを前提とすれば、使用する道路データ数が少ない方がよく、少ない道路データ数でより遠くの地点を復帰点とするのであれば、上位階層の道路データを用いることが有効である。
【００２５】（３）評価値計算処理の高速化が期待できる。例えば復帰点として１００Ｋｍ先の地点を確保したい場合に、１００Ｋｍ先の地点が含まれる上位階層の道路データの境界を復帰点として設定する。第２層の道路データを用いた場合、現在地が第１層の道路データ単位で次の道路データに移行したとしても、その地点から１００Ｋｍ先の地点は、やはり同じ第２層の道路データ中に存在することが考えられる。このような状況では、１００Ｋｍ先の地点が異なる第２層の道路データ内に移動しない限り、第１層の道路データを用いた復帰経路の部分のみ更新するだけでよく、第２層の道路データを用いた復帰経路の部分はそのまま再利用することができる。したがって、評価値計算処理を高速化することができる。上述したように評価値計算処理はより早期に完了した方が好ましいため、このような処理の高速化は非常に有効である。
【００２６】なお、上位階層の道路データを用いる場合には、請求項７に示すように、現在地に関しては最下層の道路を用いることが好ましい。そして、請求項８に示すように、目的地が使用中の上位階層の道路データ中に含まれている場合には、目的地についても最下層の道路データを用いることが好ましい。この場合、同じ上位階層の道路データ中に現在地と目的地とが含まれている必要はない。例えば、隣接する上位階層の道路データを２枚使用している状況で１枚目に現在地、２枚目に目的地が含まれる場合、目的地についても最下層の道路データを用いることが好ましい。
【００２７】以上説明したように、本発明においては、経路を離脱した段階で復帰経路を設定するための評価値計算処理が完了していることが前提となる。但し、例えば道路データの境界を通過した直後など、復帰経路用の評価値計算処理を更新している最中に経路を離脱して復帰経路を計算する必要が生じた場合には、評価値の計算結果が存在していないといけない。そこで、このようなケースにも対応するために、請求項９に示す手法を採用しても良い。
【００２８】すなわち、評価値計算結果記憶手段に２つの記憶領域を準備し、一方の記憶領域に既に計算結果が記憶されている場合には、他方の記憶領域を利用して復帰経路用評価値計算処理手段による計算を行い、その計算結果が当該記憶領域に記憶された後で、もう一方の記憶領域内の計算結果を消去するのである。このようにすれば、評価値の計算結果の更新中に復帰経路を設定する必要が生じても、更新前の計算結果を用いて経路設定ができるため、上述したケースに適切に対応できることとなる。
【００２９】また、請求項１０に示すように、上述した経路設定装置と、その経路設定装置によって設定された経路に対する走行案内を行う案内手段とを備えたナビゲーション装置として実現することもできる。なお、上述した経路設定に関する処理をコンピュータシステムにて実現する機能は、例えば、コンピュータシステム側で起動するプログラムとして備えることができる。このようなプログラムの場合、例えば、フロッピーディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ハードディスク等のコンピュータ読み取り可能な記録媒体に記録し、必要に応じてコンピュータシステムにロードして起動することにより用いることができる。この他、ＲＯＭやバックアップＲＡＭをコンピュータ読み取り可能な記録媒体として前記プログラムを記録しておき、このＲＯＭあるいはバックアップＲＡＭをコンピュータシステムに組み込んで用いても良い。
【００３０】
【発明の実施の形態】以下、本発明が適用された実施例について図面を用いて説明する。なお、本発明の実施の形態は、下記の実施例に何ら限定されることなく、本発明の技術的範囲に属する限り、種々の形態を採り得ることは言うまでもない。
【００３１】図１は、車載用のナビゲーション装置１として適用した場合の概略構成図である。本実施例のナビゲーション装置１は、車両の現在位置を検出する位置検出器１２と、当該装置へ各種指令を入力するための操作スイッチ群２０と、その操作スイッチ群２０と同様の各種指令を入力可能な図示しないリモートコントロール端末（以下、リモコンと称す。）からの信号を入力するためのリモコンセンサ２１と、地図データ入力器２２と、地図表示画面やＴＶ画面等の各種表示を行うための表示装置２６と、スピーカ２８と、上述した位置検出器１２、操作スイッチ群２０、地図データ入力器２２及び図示しないリモコンからの入力に応じて各種処理を実行し、表示装置２６やスピーカ２８を制御するナビ制御回路３０とを備えている。
【００３２】位置検出器１２は、ＧＰＳ（Global Positioning System） 用の人工衛星からの送信電波をＧＰＳアンテナを介して受信し、車両の位置，方位，速度等を検出するＧＰＳ受信機１２ａと、車両に加えられる回転運動の大きさを検出するジャイロスコープ１２ｂと、車速センサや車輪センサ等からなり車両の走行距離を検出するための車速センサ１２ｃとを備えている。そして、これら各センサ等１２ａ〜１２ｃは、各々が性質の異なる誤差を有しているため、互いに補完しながら使用するように構成されている。なお、精度によっては、上述したセンサ等１２ａ〜１２ｃの中の一部のみを用いて構成してもよく、また、地磁気に基づいて絶対方位を検出する地磁気センサや左右操舵輪の回転差などから得られる車両のステアリング角を累積して方向を求めるセンサ等を用いてもよい。
【００３３】また、操作スイッチ群２０としては、表示装置２６と一体に構成され表示画面上に設定されるタッチスイッチ及び表示装置２６の周囲に設けられたメカニカルなキースイッチ等が用いられる。タッチスイッチは、表示装置２６の画面上に縦横無尽に配置された赤外線センサより構成されており、例えば指やタッチペンなどでその赤外線を遮断すると、その遮断した位置が２次元座標値（Ｘ，Ｙ）として検出される。これによって、表示画面を直接タッチすることで、所定の指示を入力できるようにされている。
【００３４】なお、これら操作スイッチ群２０は車載用ナビゲーション装置２０を操作するための各種スイッチであるが、具体的には、表示装置２６に表示させる表示内容を切り替えるためのスイッチや、利用者が目的地までのルート（経路）を設定するためのスイッチなどを含む。
【００３５】一方、地図データ入力器２２は、位置検出の精度向上のためのいわゆるマップマッチング用データ、道路の接続を表した道路データを含む各種データを記憶媒体から入力するための装置である。記憶媒体としては、そのデータ量からＣＤ−ＲＯＭやＤＶＤを用いるのが一般的であるが、例えばメモリカード等の他の媒体を用いても良い。
【００３６】ところで、この道路データのフォーマットには、リンク情報とノード情報、及びリンク間接続情報がある。リンク情報としては、リンクを特定するための固有の番号である「リンクＩＤ」や、例えば高速道路、有料道路、一般道あるいは取付道などを識別するための「リンククラス」や、リンクの「始端座標」および「終端座標」や、リンクの長さを示す「リンク長」などのリンク自体に関する情報がある。一方、ノード情報としては、リンクを結ぶノード固有の番号である「ノードＩＤ」や、交差点での右左折禁止や、信号機有無などの情報がある。また、リンク間接続情報には、例えば一方通行などの理由で通行が可か不可かを示すデータなどが設定されている。なお、同じリンクであっても、例えば一方通行の場合には、あるリンクからは通行可であるが別のリンクからは通行不可ということとなる。したがって、あくまでリンク間の接続態様によって通行可や通行不可が決定される。
【００３７】表示装置２６は、本実施例ではカラー表示装置であり、その画面には、位置検出器１２にて検出した車両の現在地を示すマークと、地図データ入力器２２より入力された道路データと、更に地図上に表示する案内経路、名称、目印等の付加データとを重ねて表示することができる。また、後述する案内用の報知や注意喚起用の報知のための表示もできる。
【００３８】スピーカ２８は、ナビ制御回路３０で処理された各種案内などのための音声情報を利用者に報知する。ナビ制御回路３０は、ＣＰＵ，ＲＯＭ，ＲＡＭからなる周知のマイクロコンピュータを中心に構成されており、装置全体の制御を司る。ここで、ナビ制御回路３０の内部構成を、図２に示す機能ブロック図を参照して説明する。
【００３９】図２に示すように、ナビ制御回路３０は、現在位置算出部３１と、目的地設定部３２と、表示制御部３３と、案内制御部３４と、経路算出部３５と、復帰ルート用コスト計算結果記憶部３６と、経路探索結果記憶部３７とを備えている。現在位置算出部３１は、ＧＰＳ受信機１２ａ、ジャイロスコープ１２ｂ及び車速センサ１２ｃからの入力、及び地図データ入力器２２を介して記憶媒体から取得した地図データを基にして現在位置を算出する。また、目的地設定部３２には、操作スイッチ群２０やリモコンセンサ２１を介して入力された目的地が記憶される。
【００４０】経路算出部３５は、現在位置算出部３１の出力する現在地を基に、現在地に該当する道路データ境界の通過を監視し、経路探索の終了後、及び道路データ境界の通過を認識した場合、地図データ入力２２を介して記憶媒体から必要な道路データを読み出し、復帰ルート探索用のコスト計算処理を行う、このコスト計算結果は、次回の道路データ境界通過まで、復帰ルート用コスト計算結果記憶部３６に記憶される。
【００４１】表示制御部３３は、経路探索結果記憶部３７に記憶されている経路探索結果を道路データに重ねて強調表示し、表示装置２６へ表示する。案内制御部３４は、現在位置算出部３１からの出力を基に、経路探索結果記憶部３７に記憶されている経路探索結果中の現在位置を検出し、スピーカ２８によって経路の進行方向などの音声案内を行う。また、現在位置が目的地経路上にないと判定した場合には、経路算出部３５へ復帰ルートの算出指示を行う。
【００４２】復帰ルートの算出指示を受けた経路算出部３５は、復帰ルート用コスト計算結果記憶部３６の記憶内容を基にして復帰ルートを作成し、経路探索結果記憶部３７へ格納する。経路算出部３５にて自動的に最適な経路を設定する際には、ダイクストラ法等の手法を用いる。
【００４３】このダイクストラ法では、まず、リンク上の計算開始点若しくは、計算開始点が位置するリンクの両端ノードに初期コストを設定する。その後、コスト最小値を持つノードを検索し、そのノードに接続するリンクのコストをそのノードのコストに加算し、リンク反対側のノードに設定する、という処理を繰り返す。このときリンクの反対側ノードにコストが設定済みである場合は、コストが小さくなる場合のみ更新する。
【００４４】なお、ダイクストラ法における各リンクでのコスト計算は、例えば次式を用いて行われる。コスト＝リンク長×道路幅員係数×道路種別係数ここで、道路幅員係数とは、道路幅に応じて設定される係数であり、道路種別係数とは有料道路等の道路種別に応じて設定される係数である。
【００４５】また、各ノードには、そのノードにコスト設定する際にコスト計算元となった前のリンク（若しくはノード）を記憶しておく。また、コスト最小値を持つノードとして検索されたノードは次回の検索対象から除外されるため、ノード数が有限である限り、いずれ計算は完了する。
【００４６】これら一連の処理を、コスト計算処理と呼ぶ。図３で言えば、「◎」で示した目的地１をコスト計算の開始点とし、そこから「○」で示すノードが細い矢印で示すリンクを介して網の目状につながっていく。そして、このコスト計算処理が完了した後で、計算終了点に該当するノード若しくはリンクをコスト計算処理結果から検索し、そのリンクからコスト計算処理結果内の前のリンク（若しくはノード）を順次辿っていくことで、計算開始点までの一連のリンク列が作成できる。これが経路探索結果となる。図３の場合には、現在地２が存在するノード若しくはリンクを計算終了点とし、そこから細い矢印を逆に辿って行けば、太い矢印で示す経路探索結果が作成されることとなる。
【００４７】これらの説明からも判るように、上述したコスト計算処理の完了までは、計算終了点は一切関係無いため、計算開始点を目的地とすると、コスト計算処理が完了した時点で、計算した範囲のあらゆる地点から目的地へ向かう経路が容易に算出できる状態となる。したがって、本実施例においては、この「計算した範囲のあらゆる地点から目的地へ向かう経路が容易に算出できる状態」を経路離脱前に作っておく。つまり、コスト計算処理を実行し、その計算結果を復帰ルート用コスト計算結果記憶部３６に記憶しておくのである。
【００４８】そして、経路離脱が発生して案内制御部３４から復帰ルートの算出指示を受けた経路算出部３５は、まず離脱時の現在位置のリンクを検出する。次に、復帰ルート用コスト計算結果記憶部３６の記憶内容を基にし、現在地から目的地（コスト計算開始点）までのリンク列を作成する。これだけで復帰ルートを作成することができる。この処理は非常に短時間で行うことができ、従来手法に比べて短時間で復帰ルートを提供することができる。
【００４９】上述したように、従来手法の場合には、復帰ルートを設定するために用いる道路データをなるべく少なくすることで、経路離脱後の復帰ルート早期設定を実現していた。したがって、必然的に経路品質はある程度犠牲になる。つまり、経路品質が落ちることを許容する代わりに復帰経路の早期設定というメリットを享受していたのである。
【００５０】それに対して、本実施例の場合には、時間を要するコスト計算処理を経路離脱前に実行して、実際の経路離脱時に行う復帰経路の設定は短時間で実現できるようにしたため、復帰ルートの早期設定というメリットは享受できる。そして、コスト計算処理を経路離脱前に行うことで次の利点も得られる。つまり、コスト計算処理のための時間が極端に制限されることはないため、相対的に広い範囲の道路データをコスト計算処理の対象とすることができ、結果として経路品質を向上させることができる。経路品質は、コスト計算の開始点となる復帰点が現在地から近いほど低くなり、逆に遠いほど高くなる。復帰点が現在地から近いと、元のルートに沿った復帰ルートが設定され、それは結果的には遠回りとなる可能性があるからである。したがって、広い範囲の道路データを用いれば、必然的に復帰点を遠くに設定でき、経路品質が高くなるのである。
【００５１】このように、本実施例のナビゲーション装置１によれば、復帰ルートの計算に要する時間を増大させずに、その復帰ルートの計算に用いる道路データを多くして経路品質を向上させることが可能となる。以上は、本実施例のナビゲーション装置１によって実行される復帰ルートの設定に関して、その基本的な特徴部分を説明したものであるが、以下に示すような、種々の態様にて実施できる。それを順番に説明していく。
【００５２】［復帰点に関して］復帰点に関しては、次に示す最遠点を採用することが好ましい。最遠点とは、使用中の道路データ内に存在する目的地経路上であり、且つ離脱地点よりも目的地側であって、離脱地点から目的地経路の道のりにおいて最も遠い位置である。この定義より、使用中の道路データ内に目的地が存在する場合には、当然ながら目的地が最遠点として設定される。
【００５３】［復帰ルート用のコスト計算結果の更新タイミングに関して］復帰ルート用のコスト計算結果は、定期的に更新することが好ましいので、次のようにする。図４（ａ）に示す状態は、目的地２までの案内中ルート（目的地経路）３が設定されている状態で、さらに復帰点４を計算開始点とした復帰ルート用コスト計算が完了した状態である。ここでは、現在地１を含む道路データから３つ先の道路データまで用いて復帰ルート用コスト計算を行うものとする。
【００５４】その状態から、図４（ｂ）に示すように隣の道路データ中に現在地１が移動した場合でも、図４（ａ）の状態にて得た復帰ルート用のコスト計算結果は使用可能である、しかし、現在地１から復帰点４までの距離が短くなるため、経路品質をより向上させるためには、更新した方がよい。そこで、図４（ｃ）に示すように、その時点での現在地１から４つ先の道路データを用いた場合の復帰点４を計算開始点とした復帰ルート用コスト計算を改めて実行し、その計算結果を更新記憶する。
【００５５】このように、道路データの境界を通過した場合にコスト計算結果を更新記憶しておけば、常に最新の計算結果を用いることができる。なお、その観点からすれば道路データの境界を通過する毎にコスト計算結果を更新記憶することが好ましい。但し、毎回実行すればそれだけ精度は上がるが、処理負荷は増えるので、例えば２以上の道路データの境界を通過する度に更新記憶するようにすることも考えられる。
【００５６】また、例えば図４に示す例で言えば、現在地１から４つ先の道路データ中に目的地２が含まれる状態となった場合はその目的地２を復帰点４とすればよく、その場合には、その後の道路データの境界通過に伴って、コスト計算結果を更新記憶する必要はなくなる。
【００５７】［コスト計算処理に用いる道路データに関して］道路データとしては、同一地域が複数の階層の道路データにてカバーされていると共に、上位階層の道路データほど広い地域をカバーするが収録している道路が限定されているような複数階層の道路データを用いる。ここでは３層構造として、次のようなカバー領域及び収録データとする。
【００５８】図５に示すように、最下層である第１層の道路データ１は、４Ｋｍ四方の領域をカバーしており、全ての道路が格納されている。また、一つ上の階層である第２層の道路データは、１６Ｋｍ四方の領域をカバーしており、国道・県道以上の道路が格納されている。さらに、最上層である第３層の道路データは、６４Ｋｍ四方の領域をカバーしており、国道以上の道路が格納されている。したがって、第１層、第２層の道路データは、それぞれ一つの上の階層の道路データである第２層、第３層の道路データ中に４×４枚含まれることとなる。
【００５９】そして、このような上位階層の道路データを用いた復帰ルート用コスト計算結果は図６に示すようになる。この場合には、第１層の道路データについては、現在地が含まれる１枚だけ用い、それ以外は第２層の道路データを用いる。したがって、復帰点４は第２層の道路データにおける最遠点とし、この復帰点４を計算開始点として復帰ルート用コスト計算を実行する。
【００６０】なお、図６においては第２層の道路データを１枚だけ用いているが、２枚以上用いてもよい。また、図６は第２層までの使用例であるが、さらに上位階層である第３層までを用いてもよい。そして、このように、複数階層の道路データを用いて復帰経路用の評価値計算処理を実行すると、次のような利点がある。
【００６１】（１）復帰経路の品質のさらなる向上が期待できる。第１層の道路データのみを用いる場合には、元の経路が含まれる道路データをつなげていくと細長くなるため、復帰点を延長するほど計算範囲は細長くなる。図７の例では、第１層の道路データ４を直列に４枚つなげているため、全体としては４Ｋｍ×１６Ｋｍという細長い範囲が復帰ルート用のコスト計算の対象範囲となる。このコスト計算にて使用した道路データ範囲を超えた復帰ルートの設定はできないため、設定される復帰ルート８は元の経路に沿ったものとなる。しかし、元の経路に沿わない方がより適切な復帰経路となる場合もある。
【００６２】このような場合、第２層の道路データ５を用いると、計算範囲が細長くなる事態を防止できるため、より適切な復帰経路を設定できる可能性が高くなる。例えば、図７において第２層の道路データ５まで使用して設定した復帰ルート９は、第１層の道路データ４のみを使用して設定した復帰ルート８よりも適切なものとなっていることが判る。
【００６３】（２）復帰点をさらに延長することができる。例えば、第１層の道路データのみを用いて１００Ｋｍ先を復帰点とするためには２５枚の道路データが必要となる。これに対して、第２層の道路データも用いる場合には、第２層の道路データを７枚（１１２Ｋｍ分）と第１層の道路データ１枚の計８枚の道路データで済む。さらに、第３層の道路データも用いる場合には、第３層の道路データを２枚（１２８Ｋｍ分）と第２層の道路データ１枚、第１層の道路データ１枚の計４枚の道路データで済む。
【００６４】つまり、同じ復帰点までの距離を確保しようとする場合であっても、上位階層の道路データを用いれば使用する道路データ数を減らすことができる。コスト計算処理は経路離脱前に実行するため、相対的に時間の余裕があるとは言え、経路離脱がいつ生じるかが判らないことを鑑みると、早期に処理を終えることが好ましい。したがって、所定の処理時間内に処理を終了させることを前提とすれば、使用する道路データ数が少ない方がよく、少ない道路データ数でより遠くの地点を復帰点とするのであれば、上位階層の道路データを用いることが有効である。
【００６５】（３）コスト計算処理の高速化が期待できる。例えば復帰点として１００Ｋｍ先の地点を確保したい場合に、図８に示すように、現在地１から１００Ｋｍ先の地点が含まれる第２層の道路データ５の境界を復帰点６として設定する。この場合には、現在地１から（１００＋α１）Ｋｍ先の地点が復帰点６となるため、現在地１が第１層の道路データ４単位で次の道路データに移行したとしても、その地点から１００Ｋｍ先の地点は、やはり同じ第２層の道路データ５中に存在する。この場合には、現在地１から（１００＋α２）Ｋｍ先の地点が復帰点６となる。なおα１＞α２である。
【００６６】このような状況では、１００Ｋｍ先の復帰点を確保する場合に、１００Ｋｍ先の地点が復帰点６の設定された第２層の道路データ５と異なる第２層の道路データ内に移動しない限り、第１層の道路データ４を用いた復帰ルート部分のみ更新するだけでよく、第２層の道路データ５を用いた復帰ルート部分はそのまま再利用することができる。したがって、コスト計算処理を高速化することができる。
【００６７】［上位階層の道路データを用いる場合の補足］上位階層の道路データを用いる場合には、現在地に関しては最下層の道路を用いることが好ましい。そして、図９に示すように、目的地が使用中の上位階層の道路データ中に含まれている場合には、目的地についても最下層の道路データを用いることが好ましい。例えば、図９に示す場合には現在地１と目的地２が同じ第２層の道路データ５中に含まれているが、この場合は現在地１に加えて目的地２についても第１層の道路データ４を用いる。なお、図９においては同じ第２層の道路データ５中に現在地１も目的地２も含れていたが、それぞれ別の第２層の道路データ５中に含まれていてもよい。例えば、隣接する第２層の道路データを２枚使用している状況で１枚目に現在地１、２枚目に目的地２が含まれる場合、目的地２についても第１層の道路データ４を用いることが好ましい。
【００６８】［その他］
（１）上記実施例においては、経路を離脱した段階で復帰ルートを設定するためのコスト計算処理が完了していることが前提となる。但し、例えば道路データの境界を通過した直後など、復帰ルート用のコスト計算処理を更新している最中に経路を離脱して復帰ルートを計算する必要が生じた場合には、コスト計算結果が存在していないといけない。このような不都合を回避するためには、次のような手法を採用すればよい。
【００６９】すなわち、図２に示す復帰ルート用コスト計算結果記憶部３６に２つの記憶領域を準備する。例えば第１記憶領域、第２記憶領域とする。そして、コスト計算結果を更新する必要が生じた場合は、その時点で空いている記憶領域（例えば第２記憶領域）を使用して復帰ルートの設定を行い、設定終了後、旧データが記憶されている第１記憶領域内のデータを消去する。このようにすれば、コスト計算結果の更新中に復帰ルートを設定する必要が生じても、更新前のコスト計算結果を用いて復帰ルートの設定ができるため、上述した不都合を回避できる。
【００７０】（２）上記実施例では、複数階層を用いる場合として３層構造を例に挙げたが、もちろん、２層構造でもよく、あるいは４層以上の構造であってもよい。また、上述した各階層の道路データのサイズについては、単なる一具体例であり、このような数値に何ら限定されることはない。
【００７１】（３）上記実施例では、静的情報源からの情報のみを用いて経路設定を行うことを前提として説明したが、例えば外部の情報センタなどの動的情報源からの情報も加味して経路設定を行ってもよい。例えば、図１に示した構成に加えて、外部情報源である情報センタと通信するための通信装置や、図示しないラジオアンテナを介してＦＭ放送信号を受信したり、道路近傍に配置されたＶＩＣＳサービス用の固定局から電波ビーコン信号及び光ビーコン信号を受信するための外部情報入出力装置を備える。このようにすれば、例えば渋滞情報などをリアルタイムで取得することができ、経路設定に際して道路の渋滞度を加味することができる。その場合には、コスト算出式を、例えば、リンク長×道路幅員係数×道路種別係数×渋滞度とする。
【出願人】 【識別番号】０００００４２６０
【氏名又は名称】株式会社デンソー
【出願日】 平成１１年１０月１３日（１９９９．１０．１３）
【代理人】 【識別番号】１０００８２５００
【弁理士】
【氏名又は名称】足立 勉
【公開番号】 特開２００１−１０８４７０（Ｐ２００１−１０８４７０Ａ）
【公開日】 平成１３年４月２０日（２００１．４．２０）
【出願番号】 特願平１１−２９１２４５