JP3374805B2 - 経路設定装置及びナビゲーション装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、目的地までの経路
を設定し、さらにその目的地経路から離脱した場合の復
帰経路の設定も可能な経路設定装置、及びその設定され
た経路に対する走行案内を行うナビゲーション装置に関
する。

【０００２】

【従来の技術】車両の走行に伴ってＧＰＳ等により現在
位置を検出し、その現在位置をディスプレイ上に道路地
図と共に表示したり、現在地から目的地までの適切な経
路を設定して走行案内するナビゲーションシステムが知
られ、より円滑なドライブに寄与している。また、一旦
設定した目的地経路から車両が離脱してしまった場合で
あっても、自動的に、あるいはユーザの指示に従って、
元の経路に復帰するための復帰経路を設定できるように
されている。

【０００３】この復帰経路の設定に際しては、従来、車
両の現在地が含まれる道路データを用いて行っていた。
具体的には、現在使用中の道路データ内に存在する目的
地経路上であって、現在地から最も遠くに位置する最遠
点を計算終了点として現在地からの経路計算を行う。こ
のようにして計算した経路を復帰経路とし、計算終了点
である最遠点以降の経路については、離脱前の経路であ
る目的地経路を再利用する。これによって、離脱後の現
在地から目的地までの経路を再計算するよりも短時間で
復帰経路を提供することができる。

【０００４】

【発明が解決しようとする課題】しかしながら、このよ
うな復帰経路の設定においては、次のような問題が発生
する。例えば、使用する道路データが１辺４Ｋｍの矩形
領域であったと仮定すると、上述した復帰点までの距離
は、１辺４Ｋｍの矩形領域の対角長である５．７Ｋｍ程
度がその上限となる。したがって、例えば山岳道路やバ
イパス道路などの場合で発生し易い状況であるが、使用
中の道路データにおいて、離脱位置と復帰点の間に交差
点が存在しない場合には、復帰経路が、離脱位置よりも
後戻りするように設定されてしまう可能性がある。

【０００５】一方、隣接する道路データまで用いること
によって復帰点をより遠くに設定できるようにすること
はできるが、その場合には、次のような問題が生じる。
つまり、従来技術においては、離脱後なるべく早期に復
帰経路を設定することを目的としているため、経路計算
に用いる道路データを減らすことで、経路品質はある程
度犠牲にしてまでも早期に復帰経路を設定することを選
択している。したがって、このように道路データを増や
して従来手法をそのまま採用すれば、それは復帰経路の
早期設定という根本的な要求を無視したものとなる。

【０００６】そこで本発明は、復帰経路の計算に要する
時間を増大させずに、その復帰経路の計算に用いる道路
データを多くして経路品質を向上させることを目的とす
る。

【０００７】

【課題を解決するための手段及び発明の効果】上記目的
を達成するためになされた本発明の経路設定装置は、ノ
ード間を接続するリンクのリンク情報とリンク間の接続
情報とに基づき、ダイクストラ法あるいはそれに準ずる
探索手法を用いて計算開始点から各ノードに至るまでの
最小の経路評価値（経路コストとも称す）を算出する評
価値計算処理を行い、その評価値計算処理の結果に基づ
き、出発地から目的地に至るまでの総評価値が小さくな
るリンクの接続によって目的地経路を設定することを前
提とする。

【０００８】ここで、復帰経路用評価値計算処理手段
が、経路離脱判定手段によって経路を離脱したと判定さ
れる以前に、その時点で使用中の道路データに基づき、
目的地経路上の所定の復帰点を計算開始点として評価値
計算処理を実行する。この計算結果は評価値計算結果記
憶手段に記憶される。そして、復帰経路設定手段が、経
路離脱判定手段によって経路を離脱したと判定された場
合には、評価値計算結果記憶手段に記憶された評価値計
算結果に基づき、現在地から復帰点に至るまでの総評価
値が小さくなるリンクの接続によって復帰経路を設定す
る。

【０００９】本発明の復帰経路の設定に際しては、ダイ
クストラ法あるいはそれに準ずる探索手法における次の
ような特性を利用している。すなわち、「評価値計算処
理の完了後は、計算開始点から計算範囲すべての地点へ
の経路を計算することができる」という特性である。こ
の特定を用い、上述したように、目的地経路上の所定の
復帰点を計算開始点として評価値計算処理を実行すれ
ば、その計算結果を用いることで、計算開始点から計算
範囲すべての地点への経路を計算することができる。し
たがって、経路離脱時に、現在地から復帰点に至るまで
の総評価値が小さくなるリンクの接続によって復帰経路
を設定するのが非常に短時間でできることとなる。

【００１０】従来手法の場合には、経路離脱後に復帰経
路を早期に設定するため、復帰経路を設定するために用
いる道路データをなるべく少なくしていた。上述例で言
えば、４Ｋｍ四方の道路データのみ用いることとなる。
したがって、必然的に経路品質はある程度犠牲になる。
つまり、経路品質が落ちることを許容する代わりに復帰
経路の早期設定というメリットを享受していたのであ
る。

【００１１】それに対して、本発明の場合には、上述し
たように、実際に経路離脱時に行う復帰経路の設定は短
時間で実現できるため、復帰経路の早期設定というメリ
ットは享受できる。そして、従来手法では犠牲にしてい
た経路品質については、評価値計算処理をどのようにす
るかによって決まる。評価値計算処理は、経路離脱前に
行うため、相対的に十分な時間がある。つまり、従来手
法のような経路の早期設定の要求に応えるために時間が
極端に制限されることはない。そのため、相対的に広い
範囲の道路データを評価値計算処理の対象とすることが
でき、結果として経路品質を向上させることができる。
このように、本発明の経路設定装置によれば、復帰経路
の計算に要する時間を増大させずに、その復帰経路の計
算に用いる道路データを多くして経路品質を向上させる
ことが可能となる。また、目的地を復帰点として復帰経
路用の評価値計算処理を実行した場合には、その後に計
算結果を更新記憶する必要はない。したがって、本発明
の経路設定装置によれば、そのような場合は、その後に
道路データの境界を通過しても、復帰経路用の評価値計
算処理を実行しないようにする。

【００１２】なお、復帰点に関しては、例えば請求項３
に示すような最遠点を採用することが好ましい。ここ
で、最遠点とは、次のように定義される。つまり、使用
中の道路データ内に存在する目的地経路上であり、且つ
離脱地点よりも目的地側であって、離脱地点から目的地
経路の道のりにおいて最も遠い位置である。なお、当然
ながら、使用中の道路データ内に目的地が存在する場合
には、上記定義より、その目的地が最遠点として設定さ
れる。

【００１３】ここで、従来手法と本発明手法との差異に
より明確にするため、図面を参照して説明する。最初
に、図１０中に示した番号（１〜８）について説明す
る。「１」は現在地の位置する道路データであり、例え
ば４Ｋｍ四方といった比較的狭い範囲をカバーするもの
である。「２」は元の経路（つまり既に設定されて案内
に用いられていた目的地経路）であり、「３」は現在地
である。また、「４」は理想の復帰ルートであり、
「５」従来技術での復帰ルート、「６」は従来技術での
復帰点を示している。さらに、「７」は隣接する道路デ
ータであり、「８」は本発明での復帰点である。

【００１４】従来手法においては、図１０で言えば、経
路を離脱してから、現在地の位置する道路データ１のみ
を用いて復帰経路を設定していた。その際の復帰点６
は、現在地の位置する道路データ１における最遠点であ
る。この状況では、図１０中に「５」で示したルートが
復帰ルートとして設定されることとなる。しかし、隣接
する道路データ７も加味して考えると、結果的に、従来
技術での復帰ルート５は遠回りしていることが判る。

【００１５】これに対して、本発明の場合には、隣接す
る道路データ７を用いても、経路離脱時に行う復帰経路
の設定処理に要する時間が短くて済む。そのため、隣接
する道路データ７まで加味した場合の復帰点８は、その
隣接道路データ７を含めた最遠点となる。このようにす
れば、理想の復帰ルート４を設定することができる。な
お、この図１０では判りやすいように隣接する道路デー
タまでを用いた具体例として説明したが、上述したよう
に、評価値計算処理は経路離脱前に行うため、相対的に
十分な時間がある。したがって、さらに広範囲の道路デ
ータを用いても問題なく、経路品質のさらなる向上を期
待できる。

【００１６】ところで、復帰経路用評価値計算処理手段
による計算タイミングとしては、請求項４に示すように
することが考えられる。すなわち、現在地検出手段によ
って検出された現在地に基づき道路データの境界を通過
したか否かを判定し、道路データの境界通過の場合に
は、復帰経路用の評価値計算処理を実行する。そして、
復帰経路用評価値計算処理手段によって復帰経路用の評
価値計算処理が実行される毎に、その計算結果を評価値
計算結果記憶手段に更新記憶しておくことが考えられ
る。

【００１７】上述したように、評価値計算処理は経路離
脱前に行う必要がある。但し経路離脱はいつ発生するか
は判らない。そこで、道路データの境界を通過した場合
に評価値計算処理を行っておけば、その後、どのような
タイミングで経路離脱が生じても、その計算結果を用い
ることができる。

【００１８】なお、請求項５に示すように、道路データ
の境界をｎ回（ｎは自然数）通過する毎に、復帰経路用
の評価値計算処理を実行することが考えられる。ｎ＝１
であれば、道路データの境界を通過する度に評価値計算
処理を実行し、例えばｎ＝３であれば、３つの道路デー
タの境界を通過する度に実行することとなる。毎回実行
すればそれだけ精度は上がるが、処理負荷は増えるの
で、それらのバランスを考えてｎは設定すればよい。

【００１９】

【００２０】なお、評価値計算処理に用いる道路データ
としては、例えば請求項６に示すように、複数階層の道
路を用いることが考えられる。すなわち、同一地域が複
数の階層の道路データにてカバーされていると共に、上
位階層の道路データほど広い地域をカバーするが収録し
ている道路が限定されているような道路データを用い
る。例えば３層構造の場合、最下層である第１層の道路
データが４Ｋｍ四方の領域をカバーしている場合、一つ
上の階層である第２層の道路データは１６Ｋｍ四方の領
域をカバーし、最上層である第３層の道路データは６４
Ｋｍ四方の領域をカバーするように設定しておくのであ
る。

【００２１】このように、複数階層の道路データを用い
て復帰経路用の評価値計算処理を実行すると、次のよう
な利点がある。 （１）復帰経路の品質のさらなる向上が期待できる。例
えば、カバーする領域が最も狭い最下層の道路データの
みを用いる場合には、元の経路が含まれる道路データを
つなげていくと細長くなるため、復帰点を延長するほど
計算範囲は細長くなる。したがって、設定される復帰経
路は、元の経路に沿ったものとなる。しかし、元の経路
に沿わない方がより適切な復帰経路となる場合もある。

【００２２】このような場合、上位階層の道路データを
用いると、計算範囲が細長くなる事態を防止することが
可能であるため、その場合には、より適切な復帰経路を
設定できる可能性が高くなる。 （２）復帰点をさらに延長することができる。

【００２３】上述した３層構造の道路データを例にとっ
て説明する。例えば４Ｋｍ四方の第１層の道路データの
みを用いて１００Ｋｍ先を復帰点とするためには、２５
枚の道路データが必要となる。これに対して、１６Ｋｍ
四方の第２層の道路データも用いる場合には、第２層の
道路データを７枚（１１２Ｋｍ分）と第１層の道路デー
タ１枚の計８枚の道路データで済む。さらに、６４Ｋｍ
四方の第３層の道路データも用いる場合には、第３層の
道路データを２枚（１２８Ｋｍ分）と第２層の道路１
枚、第１層の道路データ１枚の計４枚の道路データで済
む。

【００２４】つまり、同じ復帰点までの距離を確保しよ
うとする場合であっても、上位階層の道路データを用い
れば使用する道路データ数を減らすことができる。評価
値計算処理は経路離脱前に実行するため、相対的に時間
の余裕があるとは言え、経路離脱がいつ生じるかが判ら
ないことを鑑みると、早期に処理を終えることが好まし
い。したがって、所定の処理時間内に処理を終了させる
ことを前提とすれば、使用する道路データ数が少ない方
がよく、少ない道路データ数でより遠くの地点を復帰点
とするのであれば、上位階層の道路データを用いること
が有効である。

【００２５】（３）評価値計算処理の高速化が期待でき
る。例えば復帰点として１００Ｋｍ先の地点を確保した
い場合に、１００Ｋｍ先の地点が含まれる上位階層の道
路データの境界を復帰点として設定する。第２層の道路
データを用いた場合、現在地が第１層の道路データ単位
で次の道路データに移行したとしても、その地点から１
００Ｋｍ先の地点は、やはり同じ第２層の道路データ中
に存在することが考えられる。このような状況では、１
００Ｋｍ先の地点が異なる第２層の道路データ内に移動
しない限り、第１層の道路データを用いた復帰経路の部
分のみ更新するだけでよく、第２層の道路データを用い
た復帰経路の部分はそのまま再利用することができる。
したがって、評価値計算処理を高速化することができ
る。上述したように評価値計算処理はより早期に完了し
た方が好ましいため、このような処理の高速化は非常に
有効である。

【００２６】なお、上位階層の道路データを用いる場合
には、請求項７に示すように、現在地に関しては最下層
の道路を用いることが好ましい。そして、請求項８に示
すように、目的地が使用中の上位階層の道路データ中に
含まれている場合には、目的地についても最下層の道路
データを用いることが好ましい。この場合、同じ上位階
層の道路データ中に現在地と目的地とが含まれている必
要はない。例えば、隣接する上位階層の道路データを２
枚使用している状況で１枚目に現在地、２枚目に目的地
が含まれる場合、目的地についても最下層の道路データ
を用いることが好ましい。

【００２７】以上説明したように、本発明においては、
経路を離脱した段階で復帰経路を設定するための評価値
計算処理が完了していることが前提となる。但し、例え
ば道路データの境界を通過した直後など、復帰経路用の
評価値計算処理を更新している最中に経路を離脱して復
帰経路を計算する必要が生じた場合には、評価値の計算
結果が存在していないといけない。そこで、このような
ケースにも対応するために、請求項２に示す手法を採用
しても良い。

【００２８】すなわち、評価値計算結果記憶手段に２つ
の記憶領域を準備し、一方の記憶領域に既に計算結果が
記憶されている場合には、他方の記憶領域を利用して復
帰経路用評価値計算処理手段による計算を行い、その計
算結果が当該記憶領域に記憶された後で、もう一方の記
憶領域内の計算結果を消去するのである。このようにす
れば、評価値の計算結果の更新中に復帰経路を設定する
必要が生じても、更新前の計算結果を用いて経路設定が
できるため、上述したケースに適切に対応できることと
なる。

【００２９】また、請求項９に示すように、上述した経
路設定装置と、その経路設定装置によって設定された経
路に対する走行案内を行う案内手段とを備えたナビゲー
ション装置として実現することもできる。なお、上述し
た経路設定に関する処理をコンピュータシステムにて実
現する機能は、例えば、コンピュータシステム側で起動
するプログラムとして備えることができる。このような
プログラムの場合、例えば、ＦＤ、光磁気ディスク、Ｃ
Ｄ−ＲＯＭ、ハードディスク等のコンピュータ読み取り
可能な記録媒体に記録し、必要に応じてコンピュータシ
ステムにロードして起動することにより用いることがで
きる。この他、ＲＯＭやバックアップＲＡＭをコンピュ
ータ読み取り可能な記録媒体として前記プログラムを記
録しておき、このＲＯＭあるいはバックアップＲＡＭを
コンピュータシステムに組み込んで用いても良い。

【００３０】

【発明の実施の形態】以下、本発明が適用された実施例
について図面を用いて説明する。なお、本発明の実施の
形態は、下記の実施例に何ら限定されることなく、本発
明の技術的範囲に属する限り、種々の形態を採り得るこ
とは言うまでもない。

【００３１】図１は、車載用のナビゲーション装置１と
して適用した場合の概略構成図である。本実施例のナビ
ゲーション装置１は、車両の現在位置を検出する位置検
出器１２と、当該装置へ各種指令を入力するための操作
スイッチ群２０と、その操作スイッチ群２０と同様の各
種指令を入力可能な図示しないリモートコントロール端
末（以下、リモコンと称す。）からの信号を入力するた
めのリモコンセンサ２１と、地図データ入力器２２と、
地図表示画面やＴＶ画面等の各種表示を行うための表示
装置２６と、スピーカ２８と、上述した位置検出器１
２、操作スイッチ群２０、地図データ入力器２２及び図
示しないリモコンからの入力に応じて各種処理を実行
し、表示装置２６やスピーカ２８を制御するナビ制御回
路３０とを備えている。

【００３２】位置検出器１２は、ＧＰＳ（Global Posit
ioning System） 用の人工衛星からの送信電波をＧＰＳ
アンテナを介して受信し、車両の位置，方位，速度等を
検出するＧＰＳ受信機１２ａと、車両に加えられる回転
運動の大きさを検出するジャイロスコープ１２ｂと、車
速センサや車輪センサ等からなり車両の走行距離を検出
するための車速センサ１２ｃとを備えている。そして、
これら各センサ等１２ａ〜１２ｃは、各々が性質の異な
る誤差を有しているため、互いに補完しながら使用する
ように構成されている。なお、精度によっては、上述し
たセンサ等１２ａ〜１２ｃの中の一部のみを用いて構成
してもよく、また、地磁気に基づいて絶対方位を検出す
る地磁気センサや左右操舵輪の回転差などから得られる
車両のステアリング角を累積して方向を求めるセンサ等
を用いてもよい。

【００３３】また、操作スイッチ群２０としては、表示
装置２６と一体に構成され表示画面上に設定されるタッ
チスイッチ及び表示装置２６の周囲に設けられたメカニ
カルなキースイッチ等が用いられる。タッチスイッチ
は、表示装置２６の画面上に縦横無尽に配置された赤外
線センサより構成されており、例えば指やタッチペンな
どでその赤外線を遮断すると、その遮断した位置が２次
元座標値（Ｘ，Ｙ）として検出される。これによって、
表示画面を直接タッチすることで、所定の指示を入力で
きるようにされている。

【００３４】なお、これら操作スイッチ群２０は車載用
ナビゲーション装置２０を操作するための各種スイッチ
であるが、具体的には、表示装置２６に表示させる表示
内容を切り替えるためのスイッチや、利用者が目的地ま
でのルート（経路）を設定するためのスイッチなどを含
む。

【００３５】一方、地図データ入力器２２は、位置検出
の精度向上のためのいわゆるマップマッチング用デー
タ、道路の接続を表した道路データを含む各種データを
記憶媒体から入力するための装置である。記憶媒体とし
ては、そのデータ量からＣＤ−ＲＯＭやＤＶＤを用いる
のが一般的であるが、例えばメモリカード等の他の媒体
を用いても良い。

【００３６】ところで、この道路データのフォーマット
には、リンク情報とノード情報、及びリンク間接続情報
がある。リンク情報としては、リンクを特定するための
固有の番号である「リンクＩＤ」や、例えば高速道路、
有料道路、一般道あるいは取付道などを識別するための
「リンククラス」や、リンクの「始端座標」および「終
端座標」や、リンクの長さを示す「リンク長」などのリ
ンク自体に関する情報がある。一方、ノード情報として
は、リンクを結ぶノード固有の番号である「ノードＩ
Ｄ」や、交差点での右左折禁止や、信号機有無などの情
報がある。また、リンク間接続情報には、例えば一方通
行などの理由で通行が可か不可かを示すデータなどが設
定されている。なお、同じリンクであっても、例えば一
方通行の場合には、あるリンクからは通行可であるが別
のリンクからは通行不可ということとなる。したがっ
て、あくまでリンク間の接続態様によって通行可や通行
不可が決定される。

【００３７】表示装置２６は、本実施例ではカラー表示
装置であり、その画面には、位置検出器１２にて検出し
た車両の現在地を示すマークと、地図データ入力器２２
より入力された道路データと、更に地図上に表示する案
内経路、名称、目印等の付加データとを重ねて表示する
ことができる。また、後述する案内用の報知や注意喚起
用の報知のための表示もできる。

【００３８】スピーカ２８は、ナビ制御回路３０で処理
された各種案内などのための音声情報を利用者に報知す
る。ナビ制御回路３０は、ＣＰＵ，ＲＯＭ，ＲＡＭから
なる周知のマイクロコンピュータを中心に構成されてお
り、装置全体の制御を司る。ここで、ナビ制御回路３０
の内部構成を、図２に示す機能ブロック図を参照して説
明する。

【００３９】図２に示すように、ナビ制御回路３０は、
現在位置算出部３１と、目的地設定部３２と、表示制御
部３３と、案内制御部３４と、経路算出部３５と、復帰
ルート用コスト計算結果記憶部３６と、経路探索結果記
憶部３７とを備えている。現在位置算出部３１は、ＧＰ
Ｓ受信機１２ａ、ジャイロスコープ１２ｂ及び車速セン
サ１２ｃからの入力、及び地図データ入力器２２を介し
て記憶媒体から取得した地図データを基にして現在位置
を算出する。また、目的地設定部３２には、操作スイッ
チ群２０やリモコンセンサ２１を介して入力された目的
地が記憶される。

【００４０】経路算出部３５は、現在位置算出部３１の
出力する現在地を基に、現在地に該当する道路データ境
界の通過を監視し、経路探索の終了後、及び道路データ
境界の通過を認識した場合、地図データ入力２２を介し
て記憶媒体から必要な道路データを読み出し、復帰ルー
ト探索用のコスト計算処理を行う、このコスト計算結果
は、次回の道路データ境界通過まで、復帰ルート用コス
ト計算結果記憶部３６に記憶される。

【００４１】表示制御部３３は、経路探索結果記憶部３
７に記憶されている経路探索結果を道路データに重ねて
強調表示し、表示装置２６へ表示する。案内制御部３４
は、現在位置算出部３１からの出力を基に、経路探索結
果記憶部３７に記憶されている経路探索結果中の現在位
置を検出し、スピーカ２８によって経路の進行方向など
の音声案内を行う。また、現在位置が目的地経路上にな
いと判定した場合には、経路算出部３５へ復帰ルートの
算出指示を行う。

【００４２】復帰ルートの算出指示を受けた経路算出部
３５は、復帰ルート用コスト計算結果記憶部３６の記憶
内容を基にして復帰ルートを作成し、経路探索結果記憶
部３７へ格納する。経路算出部３５にて自動的に最適な
経路を設定する際には、ダイクストラ法等の手法を用い
る。

【００４３】このダイクストラ法では、まず、リンク上
の計算開始点若しくは、計算開始点が位置するリンクの
両端ノードに初期コストを設定する。その後、コスト最
小値を持つノードを検索し、そのノードに接続するリン
クのコストをそのノードのコストに加算し、リンク反対
側のノードに設定する、という処理を繰り返す。このと
きリンクの反対側ノードにコストが設定済みである場合
は、コストが小さくなる場合のみ更新する。

【００４４】なお、ダイクストラ法における各リンクで
のコスト計算は、例えば次式を用いて行われる。コスト
＝リンク長×道路幅員係数×道路種別係数ここで、道路
幅員係数とは、道路幅に応じて設定される係数であり、
道路種別係数とは有料道路等の道路種別に応じて設定さ
れる係数である。

【００４５】また、各ノードには、そのノードにコスト
設定する際にコスト計算元となった前のリンク（若しく
はノード）を記憶しておく。また、コスト最小値を持つ
ノードとして検索されたノードは次回の検索対象から除
外されるため、ノード数が有限である限り、いずれ計算
は完了する。

【００４６】これら一連の処理を、コスト計算処理と呼
ぶ。図３で言えば、「◎」で示した目的地１をコスト計
算の開始点とし、そこから「○」で示すノードが細い矢
印で示すリンクを介して網の目状につながっていく。そ
して、このコスト計算処理が完了した後で、計算終了点
に該当するノード若しくはリンクをコスト計算処理結果
から検索し、そのリンクからコスト計算処理結果内の前
のリンク（若しくはノード）を順次辿っていくことで、
計算開始点までの一連のリンク列が作成できる。これが
経路探索結果となる。図３の場合には、現在地２が存在
するノード若しくはリンクを計算終了点とし、そこから
細い矢印を逆に辿って行けば、太い矢印で示す経路探索
結果が作成されることとなる。

【００４７】これらの説明からも判るように、上述した
コスト計算処理の完了までは、計算終了点は一切関係無
いため、計算開始点を目的地とすると、コスト計算処理
が完了した時点で、計算した範囲のあらゆる地点から目
的地へ向かう経路が容易に算出できる状態となる。した
がって、本実施例においては、この「計算した範囲のあ
らゆる地点から目的地へ向かう経路が容易に算出できる
状態」を経路離脱前に作っておく。つまり、コスト計算
処理を実行し、その計算結果を復帰ルート用コスト計算
結果記憶部３６に記憶しておくのである。

【００４８】そして、経路離脱が発生して案内制御部３
４から復帰ルートの算出指示を受けた経路算出部３５
は、まず離脱時の現在位置のリンクを検出する。次に、
復帰ルート用コスト計算結果記憶部３６の記憶内容を基
にし、現在地から目的地（コスト計算開始点）までのリ
ンク列を作成する。これだけで復帰ルートを作成するこ
とができる。この処理は非常に短時間で行うことがで
き、従来手法に比べて短時間で復帰ルートを提供するこ
とができる。

【００４９】上述したように、従来手法の場合には、復
帰ルートを設定するために用いる道路データをなるべく
少なくすることで、経路離脱後の復帰ルート早期設定を
実現していた。したがって、必然的に経路品質はある程
度犠牲になる。つまり、経路品質が落ちることを許容す
る代わりに復帰経路の早期設定というメリットを享受し
ていたのである。

【００５０】それに対して、本実施例の場合には、時間
を要するコスト計算処理を経路離脱前に実行して、実際
の経路離脱時に行う復帰経路の設定は短時間で実現でき
るようにしたため、復帰ルートの早期設定というメリッ
トは享受できる。そして、コスト計算処理を経路離脱前
に行うことで次の利点も得られる。つまり、コスト計算
処理のための時間が極端に制限されることはないため、
相対的に広い範囲の道路データをコスト計算処理の対象
とすることができ、結果として経路品質を向上させるこ
とができる。経路品質は、コスト計算の開始点となる復
帰点が現在地から近いほど低くなり、逆に遠いほど高く
なる。復帰点が現在地から近いと、元のルートに沿った
復帰ルートが設定され、それは結果的には遠回りとなる
可能性があるからである。したがって、広い範囲の道路
データを用いれば、必然的に復帰点を遠くに設定でき、
経路品質が高くなるのである。

【００５１】このように、本実施例のナビゲーション装
置１によれば、復帰ルートの計算に要する時間を増大さ
せずに、その復帰ルートの計算に用いる道路データを多
くして経路品質を向上させることが可能となる。以上
は、本実施例のナビゲーション装置１によって実行され
る復帰ルートの設定に関して、その基本的な特徴部分を
説明したものであるが、以下に示すような、種々の態様
にて実施できる。それを順番に説明していく。

【００５２】［復帰点に関して］復帰点に関しては、次
に示す最遠点を採用することが好ましい。最遠点とは、
使用中の道路データ内に存在する目的地経路上であり、
且つ離脱地点よりも目的地側であって、離脱地点から目
的地経路の道のりにおいて最も遠い位置である。この定
義より、使用中の道路データ内に目的地が存在する場合
には、当然ながら目的地が最遠点として設定される。

【００５３】［復帰ルート用のコスト計算結果の更新タ
イミングに関して］復帰ルート用のコスト計算結果は、
定期的に更新することが好ましいので、次のようにす
る。図４（ａ）に示す状態は、目的地２までの案内中ル
ート（目的地経路）３が設定されている状態で、さらに
復帰点４を計算開始点とした復帰ルート用コスト計算が
完了した状態である。ここでは、現在地１を含む道路デ
ータから３つ先の道路データまで用いて復帰ルート用コ
スト計算を行うものとする。

【００５４】その状態から、図４（ｂ）に示すように隣
の道路データ中に現在地１が移動した場合でも、図４
（ａ）の状態にて得た復帰ルート用のコスト計算結果は
使用可能である、しかし、現在地１から復帰点４までの
距離が短くなるため、経路品質をより向上させるために
は、更新した方がよい。そこで、図４（ｃ）に示すよう
に、その時点での現在地１から４つ先の道路データを用
いた場合の復帰点４を計算開始点とした復帰ルート用コ
スト計算を改めて実行し、その計算結果を更新記憶す
る。

【００５５】このように、道路データの境界を通過した
場合にコスト計算結果を更新記憶しておけば、常に最新
の計算結果を用いることができる。なお、その観点から
すれば道路データの境界を通過する毎にコスト計算結果
を更新記憶することが好ましい。但し、毎回実行すれば
それだけ精度は上がるが、処理負荷は増えるので、例え
ば２以上の道路データの境界を通過する度に更新記憶す
るようにすることも考えられる。

【００５６】また、例えば図４に示す例で言えば、現在
地１から４つ先の道路データ中に目的地２が含まれる状
態となった場合はその目的地２を復帰点４とすればよ
く、その場合には、その後の道路データの境界通過に伴
って、コスト計算結果を更新記憶する必要はなくなる。

【００５７】［コスト計算処理に用いる道路データに関
して］道路データとしては、同一地域が複数の階層の道
路データにてカバーされていると共に、上位階層の道路
データほど広い地域をカバーするが収録している道路が
限定されているような複数階層の道路データを用いる。
ここでは３層構造として、次のようなカバー領域及び収
録データとする。

【００５８】図５に示すように、最下層である第１層の
道路データ１は、４Ｋｍ四方の領域をカバーしており、
全ての道路が格納されている。また、一つ上の階層であ
る第２層の道路データは、１６Ｋｍ四方の領域をカバー
しており、国道・県道以上の道路が格納されている。さ
らに、最上層である第３層の道路データは、６４Ｋｍ四
方の領域をカバーしており、国道以上の道路が格納され
ている。したがって、第１層、第２層の道路データは、
それぞれ一つの上の階層の道路データである第２層、第
３層の道路データ中に４×４枚含まれることとなる。

【００５９】そして、このような上位階層の道路データ
を用いた復帰ルート用コスト計算結果は図６に示すよう
になる。この場合には、第１層の道路データについて
は、現在地が含まれる１枚だけ用い、それ以外は第２層
の道路データを用いる。したがって、復帰点４は第２層
の道路データにおける最遠点とし、この復帰点４を計算
開始点として復帰ルート用コスト計算を実行する。

【００６０】なお、図６においては第２層の道路データ
を１枚だけ用いているが、２枚以上用いてもよい。ま
た、図６は第２層までの使用例であるが、さらに上位階
層である第３層までを用いてもよい。そして、このよう
に、複数階層の道路データを用いて復帰経路用の評価値
計算処理を実行すると、次のような利点がある。

【００６１】（１）復帰経路の品質のさらなる向上が期
待できる。第１層の道路データのみを用いる場合には、
元の経路が含まれる道路データをつなげていくと細長く
なるため、復帰点を延長するほど計算範囲は細長くな
る。図７の例では、第１層の道路データ４を直列に４枚
つなげているため、全体としては４Ｋｍ×１６Ｋｍとい
う細長い範囲が復帰ルート用のコスト計算の対象範囲と
なる。このコスト計算にて使用した道路データ範囲を超
えた復帰ルートの設定はできないため、設定される復帰
ルート８は元の経路に沿ったものとなる。しかし、元の
経路に沿わない方がより適切な復帰経路となる場合もあ
る。

【００６２】このような場合、第２層の道路データ５を
用いると、計算範囲が細長くなる事態を防止できるた
め、より適切な復帰経路を設定できる可能性が高くな
る。例えば、図７において第２層の道路データ５まで使
用して設定した復帰ルート９は、第１層の道路データ４
のみを使用して設定した復帰ルート８よりも適切なもの
となっていることが判る。

【００６３】（２）復帰点をさらに延長することができ
る。例えば、第１層の道路データのみを用いて１００Ｋ
ｍ先を復帰点とするためには２５枚の道路データが必要
となる。これに対して、第２層の道路データも用いる場
合には、第２層の道路データを７枚（１１２Ｋｍ分）と
第１層の道路データ１枚の計８枚の道路データで済む。
さらに、第３層の道路データも用いる場合には、第３層
の道路データを２枚（１２８Ｋｍ分）と第２層の道路デ
ータ１枚、第１層の道路データ１枚の計４枚の道路デー
タで済む。

【００６４】つまり、同じ復帰点までの距離を確保しよ
うとする場合であっても、上位階層の道路データを用い
れば使用する道路データ数を減らすことができる。コス
ト計算処理は経路離脱前に実行するため、相対的に時間
の余裕があるとは言え、経路離脱がいつ生じるかが判ら
ないことを鑑みると、早期に処理を終えることが好まし
い。したがって、所定の処理時間内に処理を終了させる
ことを前提とすれば、使用する道路データ数が少ない方
がよく、少ない道路データ数でより遠くの地点を復帰点
とするのであれば、上位階層の道路データを用いること
が有効である。

【００６５】（３）コスト計算処理の高速化が期待でき
る。例えば復帰点として１００Ｋｍ先の地点を確保した
い場合に、図８に示すように、現在地１から１００Ｋｍ
先の地点が含まれる第２層の道路データ５の境界を復帰
点６として設定する。この場合には、現在地１から（１
００＋α１）Ｋｍ先の地点が復帰点６となるため、現在
地１が第１層の道路データ４単位で次の道路データに移
行したとしても、その地点から１００Ｋｍ先の地点は、
やはり同じ第２層の道路データ５中に存在する。この場
合には、現在地１から（１００＋α２）Ｋｍ先の地点が
復帰点６となる。なおα１＞α２である。

【００６６】このような状況では、１００Ｋｍ先の復帰
点を確保する場合に、１００Ｋｍ先の地点が復帰点６の
設定された第２層の道路データ５と異なる第２層の道路
データ内に移動しない限り、第１層の道路データ４を用
いた復帰ルート部分のみ更新するだけでよく、第２層の
道路データ５を用いた復帰ルート部分はそのまま再利用
することができる。したがって、コスト計算処理を高速
化することができる。

【００６７】［上位階層の道路データを用いる場合の補
足］上位階層の道路データを用いる場合には、現在地に
関しては最下層の道路を用いることが好ましい。そし
て、図９に示すように、目的地が使用中の上位階層の道
路データ中に含まれている場合には、目的地についても
最下層の道路データを用いることが好ましい。例えば、
図９に示す場合には現在地１と目的地２が同じ第２層の
道路データ５中に含まれているが、この場合は現在地１
に加えて目的地２についても第１層の道路データ４を用
いる。なお、図９においては同じ第２層の道路データ５
中に現在地１も目的地２も含れていたが、それぞれ別の
第２層の道路データ５中に含まれていてもよい。例え
ば、隣接する第２層の道路データを２枚使用している状
況で１枚目に現在地１、２枚目に目的地２が含まれる場
合、目的地２についても第１層の道路データ４を用いる
ことが好ましい。

【００６８】［その他］ （１）上記実施例においては、経路を離脱した段階で復
帰ルートを設定するためのコスト計算処理が完了してい
ることが前提となる。但し、例えば道路データの境界を
通過した直後など、復帰ルート用のコスト計算処理を更
新している最中に経路を離脱して復帰ルートを計算する
必要が生じた場合には、コスト計算結果が存在していな
いといけない。このような不都合を回避するためには、
次のような手法を採用すればよい。

【００６９】すなわち、図２に示す復帰ルート用コスト
計算結果記憶部３６に２つの記憶領域を準備する。例え
ば第１記憶領域、第２記憶領域とする。そして、コスト
計算結果を更新する必要が生じた場合は、その時点で空
いている記憶領域（例えば第２記憶領域）を使用して復
帰ルートの設定を行い、設定終了後、旧データが記憶さ
れている第１記憶領域内のデータを消去する。このよう
にすれば、コスト計算結果の更新中に復帰ルートを設定
する必要が生じても、更新前のコスト計算結果を用いて
復帰ルートの設定ができるため、上述した不都合を回避
できる。

【００７０】（２）上記実施例では、複数階層を用いる
場合として３層構造を例に挙げたが、もちろん、２層構
造でもよく、あるいは４層以上の構造であってもよい。
また、上述した各階層の道路データのサイズについて
は、単なる一具体例であり、このような数値に何ら限定
されることはない。

【００７１】（３）上記実施例では、静的情報源からの
情報のみを用いて経路設定を行うことを前提として説明
したが、例えば外部の情報センタなどの動的情報源から
の情報も加味して経路設定を行ってもよい。例えば、図
１に示した構成に加えて、外部情報源である情報センタ
と通信するための通信装置や、図示しないラジオアンテ
ナを介してＦＭ放送信号を受信したり、道路近傍に配置
されたＶＩＣＳサービス用の固定局から電波ビーコン信
号及び光ビーコン信号を受信するための外部情報入出力
装置を備える。このようにすれば、例えば渋滞情報など
をリアルタイムで取得することができ、経路設定に際し
て道路の渋滞度を加味することができる。その場合に
は、コスト算出式を、例えば、リンク長×道路幅員係数
×道路種別係数×渋滞度とする。

【図面の簡単な説明】

【図１】 本発明の実施例としてのナビゲーション装置
の全体構成を示すブロック図である。

【図２】 実施例のナビ制御回路の機能ブロック図であ
る。

【図３】 ダイクストラ法を用いたコスト計算処理を概
要及び結果を示す説明するである。

【図４】 復帰ルート用のコスト計算結果の更新タイミ
ングの説明図である。

【図５】 コスト計算処理に用いる複数階層の道路デー
タの説明図である。

【図６】 上位階層の道路データを用いた復帰ルート用
コスト計算結果を示す説明図である。

【図７】 上位階層の道路データを用いた場合に復帰経
路の品質が向上することの説明図である。

【図８】 上位階層の道路データを用いた場合にコスト
計算処理の高速化が期待できることを示す説明図であ
る。

【図９】 現在地と目的地が同じ上位階層の道路データ
中に含まれる場合の対処を示す説明図である。

【図１０】 従来技術と本発明とによる経路設定の違い
を具体的に示す説明図である。

【符号の説明】

１…ナビゲーション装置 １２…位置検出器 １２ａ…ＧＰＳ受信機 １２ｂ…ジャイ
ロスコープ １２ｃ…車速センサ ２０…操作ス
イッチ群 ２１…リモコンセンサ ２２…地図デー
タ入力器 ２６…表示装置 ２８…スピーカ ３０…ナビ制御回路 ３１…現在位置
算出部 ３２…目的地設定部 ３３…表示制御
部 ３４…案内制御部 ３５…経路算出
部 ３６…復帰ルート用コスト計算結果記憶部 ３７…経路探索結果記憶部

───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.⁷，ＤＢ名) G01C 21/00 G08G 1/0969

Claims (9)

(57)【特許請求の範囲】
1. 【請求項１】ノード間を接続するリンクのリンク情報と
   リンク間の接続情報とに基づき、ダイクストラ法あるい
   はそれに準ずる探索手法を用いて計算開始点から各ノー
   ドに至るまでの最小の経路評価値を算出する評価値計算
   処理を行い、その評価値計算処理の結果に基づき、出発
   地から目的地に至るまでの総評価値が小さくなるリンク
   の接続によって目的地経路を設定する経路設定装置にお
   いて、 現在地を検出する現在地検出手段と、 その現在地検出手段によって検出された現在地に基づ
   き、経路を離脱したか否かを判定する経路離脱判定手段
   と、 その経路離脱判定手段によって経路を離脱したと判定さ
   れる以前に、その時点で使用中の道路データに基づき、
   前記目的地経路上の所定の復帰点を前記計算開始点とし
   て前記評価値計算処理を実行する復帰経路用評価値計算
   処理手段と、 その復帰経路用評価値計算処理手段にて計算された結果
   を記憶しておく評価値計算結果記憶手段と、 前記経路離脱判定手段によって経路を離脱したと判定さ
   れた場合には、前記評価値計算結果記憶手段に記憶され
   た評価値計算結果に基づき、現在地から前記復帰点に至
   るまでの総評価値が小さくなるリンクの接続によって復
   帰経路を設定する復帰経路設定手段とを備え、 前記復帰経路用評価値計算処理手段は、前記目的地を前
   記復帰点として前記復帰経路用の評価値計算処理を実行
   した場合には、その後、前記道路データの境界を通過し
   ても、前記復帰経路用の評価値計算処理を実行しない こ
   とを特徴とする経路設定装置。
2. 【請求項２】ノード間を接続するリンクのリンク情報と
   リンク間の接続情報とに基づき、ダイクストラ法あるい
   はそれに準ずる探索手法を用いて計算開始点から各ノー
   ドに至るまでの最小の経路評価値を算出する評価値計算
   処理を行い、その評価値計算処理の結果に基づき、出発
   地から目的地に至るまでの総評価値が小さくなるリン ク
   の接続によって目的地経路を設定する経路設定装置にお
   いて、現在地を検出する現在地検出手段と、 その現在地検出手段によって検出された現在地に基づ
   き、経路を離脱したか否かを判定する経路離脱判定手段
   と、 その経路離脱判定手段によって経路を離脱したと判定さ
   れる以前に、その時点で使用中の道路データに基づき、
   前記目的地経路上の所定の復帰点を前記計算開始点とし
   て前記評価値計算処理を実行する復帰経路用評価値計算
   処理手段と、 その復帰経路用評価値計算処理手段にて計算された結果
   を記憶しておく評価値計算結果記憶手段と、 前記経路離脱判定手段によって経路を離脱したと判定さ
   れた場合には、前記評価値計算結果記憶手段に記憶され
   た評価値計算結果に基づき、現在地から前記復帰点に至
   るまでの総評価値が小さくなるリンクの接続によって復
   帰経路を設定する復帰経路設定手段と を備え、 前記評価値計算結果記憶手段は、２つの記憶領域を有し
   ており、一方の記憶領域に既に計算結果が記憶されてい
   る場合には、他方の記憶領域を利用して前記復帰経路用
   評価値計算処理手段による計算がなされ、その計算結果
   が当該記憶領域に記憶された後で、もう一方の記憶領域
   内の計算結果が消去される ことを特徴とする経路設定装
   置。
3. 【請求項３】請求項１又は２記載の経路設定装置におい
   て、 前記復帰点は、その使用中の道路データ内に存在する前
   記目的地経路上であり、且つ離脱地点よりも目的地側で
   あって、離脱地点から前記目的地経路の道のりにおいて
   最も遠い位置である最遠点であることを特徴とする経路
   設定装置。
4. 【請求項４】請求項１〜３のいずれか記載の経路設定装
   置において、 前記復帰経路用評価値計算処理手段は、前記現在地検出
   手段によって検出された現在地に基づき、道路データの
   境界を通過したか否かを判定し、道路データの境界通過
   の場合には、前記復帰経路用の評価値計算処理を実行
   し、 前記評価値計算結果記憶手段は、前記復帰経路用評価値
   計算処理手段によって前記復帰経路用の評価値計算処理
   が実行される毎に、その計算結果を更新記憶しておくこ
   とを特徴とする経路設定装置。
5. 【請求項５】請求項４記載の経路設定装置において、 前記復帰経路用評価値計算処理手段は、前記道路データ
   の境界をｎ回（ｎは自然数）通過する毎に、前記復帰経
   路用の評価値計算処理を実行することを特徴とする経路
   設定装置。
6. 【請求項６】請求項１〜５のいずれか記載の経路設定装
   置において、 前記道路データは、同一地域が複数の階層の道路データ
   にてカバーされていると共に、上位階層の道路データほ
   ど広い地域をカバーするが収録している道路が限定され
   ており、 前記復帰経路用評価値計算処理手段は、前記複数階層の
   道路データを用いて前記復帰経路用の評価値計算処理を
   実行することを特徴とする経路設定装置。
7. 【請求項７】請求項６記載の経路設定装置において、 前記現在地について最下層の道路データを用いることを
   特徴とする経路設定装置。
8. 【請求項８】請求項６又は７記載の経路設定装置におい
   て、 前記目的地が使用中の上位階層の道路データ中に含まれ
   ている場合には、目的地の両方について最下層の道路デ
   ータを用いることを特徴とする経路設定装置。
9. 【請求項９】請求項１〜８のいずれか記載の経路設定装
   置と、 その経路設定装置によって設定された経路に対する走行
   案内を行う案内手段とを備えたことを特徴とするナビゲ
   ーション装置。