JP3249140B2 - ルートを決定する方法および装置 - Google Patents
ルートを決定する方法および装置Info
- Publication number
- JP3249140B2 JP3249140B2 JP54994698A JP54994698A JP3249140B2 JP 3249140 B2 JP3249140 B2 JP 3249140B2 JP 54994698 A JP54994698 A JP 54994698A JP 54994698 A JP54994698 A JP 54994698A JP 3249140 B2 JP3249140 B2 JP 3249140B2
- Authority
- JP
- Japan
- Prior art keywords
- route
- complete
- partial
- new
- destination
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/20—Instruments for performing navigational calculations
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G01C21/3446—Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Navigation (AREA)
- Instructional Devices (AREA)
Description
【発明の詳細な説明】 発明の背景 産業上の利用分野 本発明は、ディジタル化された道路網上に配置された
出発地点から目的地点へのルートを決定する方法および
装置に関する。
出発地点から目的地点へのルートを決定する方法および
装置に関する。
Neukirchner等に対するアメリカ合衆国特許No.4,984,
168によれば、ナビゲーションシステムにおいて出発地
点と目的地点との間のルートを迅速かつ信頼性をもって
決定するためのプロセスについて開示されている。この
特許が基礎としている考えは、出発地点と目的地点が近
くであれば間道によって交通が形成されるのに対し、も
っと長い距離は幹線道路や高速道路によってカバーされ
ていることである。長距離交通を担う道路を非常に広い
範囲において考察するだけにしたことから、可能な道路
の多様性が減少し、それによってルート計算に必要な時
間が低減される。
168によれば、ナビゲーションシステムにおいて出発地
点と目的地点との間のルートを迅速かつ信頼性をもって
決定するためのプロセスについて開示されている。この
特許が基礎としている考えは、出発地点と目的地点が近
くであれば間道によって交通が形成されるのに対し、も
っと長い距離は幹線道路や高速道路によってカバーされ
ていることである。長距離交通を担う道路を非常に広い
範囲において考察するだけにしたことから、可能な道路
の多様性が減少し、それによってルート計算に必要な時
間が低減される。
また、ヨーロッパ特許出願EP 0 726 447 A1（対応ア
メリカ合衆国特許出願番号08/385,611）によれば、中間
目的地点を選択し代替ルート各々のコストを計算する技
術を用いて、出発地点から目的地点までのルートを探索
するシステムが知られている。この場合、中間目的地点
へのルートがシステムのユーザへ通報される一方で、中
間目的地点から最終目的地点への残りのルートが決定さ
れる。しかしこれは、中間目的地点へのルートが最終目
的地点への最適ルートの一部分であるか否かにかかわら
ず、ルート全体の計算が完了する前になされる。不都合
な中間目的地点から最終目的地点へのルートを加えるこ
とで、実質的な迂回路になるかもしれないし、さもなけ
れば不必要な回り道になるかもしれない。
メリカ合衆国特許出願番号08/385,611）によれば、中間
目的地点を選択し代替ルート各々のコストを計算する技
術を用いて、出発地点から目的地点までのルートを探索
するシステムが知られている。この場合、中間目的地点
へのルートがシステムのユーザへ通報される一方で、中
間目的地点から最終目的地点への残りのルートが決定さ
れる。しかしこれは、中間目的地点へのルートが最終目
的地点への最適ルートの一部分であるか否かにかかわら
ず、ルート全体の計算が完了する前になされる。不都合
な中間目的地点から最終目的地点へのルートを加えるこ
とで、実質的な迂回路になるかもしれないし、さもなけ
れば不必要な回り道になるかもしれない。
発明の概要 したがって本発明の課題は、走行ルートを決定する方
法および装置において、このような種々の形式によるこ
れまで周知の装置および方法の上述の欠点を克服し、出
発地点と目的地点との間のルートを迅速に決定し、ユー
ザをガイドする信頼性のある情報を提供できるようにす
ることである。
法および装置において、このような種々の形式によるこ
れまで周知の装置および方法の上述の欠点を克服し、出
発地点と目的地点との間のルートを迅速に決定し、ユー
ザをガイドする信頼性のある情報を提供できるようにす
ることである。
本発明によればこの課題は、ナビゲーションシステム
の不揮発記憶装置に格納されているディジタル化された
道路網上に位置する出発地点から目的地点までの走行ル
ートを決定する方法において、出発地点と目的地点との
間の中間目的地点を規定し、出発地点から中間目的地点
までの部分ルートを計算して、部分ルート情報をユーザ
インタフェースへ出力し、出発地点から目的地点までの
完全なルートを計算し、完全なルートと部分ルートとを
オーバラップさせ、完全なルートと部分ルートとの間の
交差地点を規定し、交差地点から始める完全なルート情
報を出力することを特徴とする、走行ルートを決定する
方法により解決される。
の不揮発記憶装置に格納されているディジタル化された
道路網上に位置する出発地点から目的地点までの走行ル
ートを決定する方法において、出発地点と目的地点との
間の中間目的地点を規定し、出発地点から中間目的地点
までの部分ルートを計算して、部分ルート情報をユーザ
インタフェースへ出力し、出発地点から目的地点までの
完全なルートを計算し、完全なルートと部分ルートとを
オーバラップさせ、完全なルートと部分ルートとの間の
交差地点を規定し、交差地点から始める完全なルート情
報を出力することを特徴とする、走行ルートを決定する
方法により解決される。
本発明によれば、ディジタル化された道路網上に配置
された出発地点から目的地点までのルートを、出発地点
から中間目的地点までの部分ルートを計算し、出発地点
から目的地点までの完全なルートを計算することにより
決定する。完全なルートを計算している間、部分ルート
の走行計画（maneuver）をユーザに出力することができ
る。したがってシステムのユーザは、目的地までの完全
なルートおよびその走行計画の決定を完了する前に進み
始めることができる。完全なルートが計算されてしまっ
たならば、部分ルートとオーバラップさせ、完全なルー
トと部分ルートとの間の交差地点を規定する。ついで、
計算された完全なルートの走行計画が、部分ルートと完
全なルートとの間の交差点から出発してユーザに出力さ
れる。
された出発地点から目的地点までのルートを、出発地点
から中間目的地点までの部分ルートを計算し、出発地点
から目的地点までの完全なルートを計算することにより
決定する。完全なルートを計算している間、部分ルート
の走行計画（maneuver）をユーザに出力することができ
る。したがってシステムのユーザは、目的地までの完全
なルートおよびその走行計画の決定を完了する前に進み
始めることができる。完全なルートが計算されてしまっ
たならば、部分ルートとオーバラップさせ、完全なルー
トと部分ルートとの間の交差地点を規定する。ついで、
計算された完全なルートの走行計画が、部分ルートと完
全なルートとの間の交差点から出発してユーザに出力さ
れる。
本発明は、ヨーロッパ特許出願EP 0 726 447 A1によ
り開示されているインクリメンタルルート計算（increm
ental route calculation）を使用したナビゲーション
システムに殊に適している。
り開示されているインクリメンタルルート計算（increm
ental route calculation）を使用したナビゲーション
システムに殊に適している。
本発明のさらに付加的な特徴によれば本発明による方
法は、部分ルートのための走行計画を発生させ、部分ル
ートの走行計画を部分ルート情報として表示させ、ま
た、完全なルートのための走行計画を発生させ、完全な
ルートの走行計画を完全なルート情報として表示させ
る。
法は、部分ルートのための走行計画を発生させ、部分ル
ートの走行計画を部分ルート情報として表示させ、ま
た、完全なルートのための走行計画を発生させ、完全な
ルートの走行計画を完全なルート情報として表示させ
る。
本発明の別の特徴によれば、部分ルートと完全なルー
トが、ユーザがまだ通過していない走行ルートの区間内
で交差していれば、交差地点から出発して完全なルート
の走行計画が出力される。
トが、ユーザがまだ通過していない走行ルートの区間内
で交差していれば、交差地点から出発して完全なルート
の走行計画が出力される。
オーバラップステップにおいて、部分ルートと完全な
ルートとの間で交差点が見つからなければ、出発地点に
向かう方向で、ユーザの現在位置までは遠くない中間目
的地点を戻し、新たな出発地点を規定し、次に新たな出
発地点から始まり新たな中間目的地点までの新たな部分
ルートを計算し、新たな部分ルート情報をユーザに出力
し、新たな出発地点から目的地点までの新たな完全なル
ートを計算し、新たな完全なルートと新たな部分ルート
をオーバラップさせ、新たな部分ルートと新たな完全な
ルートが少なくとも１つの交差地点を有しているなら
ば、交差地点から先に向かう新たな完全なルート情報を
出力する。
ルートとの間で交差点が見つからなければ、出発地点に
向かう方向で、ユーザの現在位置までは遠くない中間目
的地点を戻し、新たな出発地点を規定し、次に新たな出
発地点から始まり新たな中間目的地点までの新たな部分
ルートを計算し、新たな部分ルート情報をユーザに出力
し、新たな出発地点から目的地点までの新たな完全なル
ートを計算し、新たな完全なルートと新たな部分ルート
をオーバラップさせ、新たな部分ルートと新たな完全な
ルートが少なくとも１つの交差地点を有しているなら
ば、交差地点から先に向かう新たな完全なルート情報を
出力する。
本発明のさらに別の特徴によれば、新たな部分ルート
を先行する部分ルートとオーバラップさせ、新たな部分
ルートと先行の部分ルートが交差地点を有していれば、
新たな部分ルートが退けられ、そのような交差地点なく
別の新たな部分ルートが計算される。
を先行する部分ルートとオーバラップさせ、新たな部分
ルートと先行の部分ルートが交差地点を有していれば、
新たな部分ルートが退けられ、そのような交差地点なく
別の新たな部分ルートが計算される。
択一的に、新たな部分ルートと先行する部分ルートが
交差地点を有しているが、交差地点のない異なる部分ル
ートを計算できないとき、本発明による方法は、新たな
部分ルートのための走行計画を発生させ出力させるステ
ップを有する。
交差地点を有しているが、交差地点のない異なる部分ル
ートを計算できないとき、本発明による方法は、新たな
部分ルートのための走行計画を発生させ出力させるステ
ップを有する。
本発明の付加的な特徴によれば、中間目的地点に到達
する前に完全なルートの計算が完了しなければ、その中
間目的地点から出発してさらに別の目的地点までのさら
に別の部分レートを計算する。
する前に完全なルートの計算が完了しなければ、その中
間目的地点から出発してさらに別の目的地点までのさら
に別の部分レートを計算する。
本発明の付加的な特徴によれば、出発地点から中間目
的地点までの距離を、中間目的地点までにかかる推定走
行時間が完全なルートの計算にかかる推定期間よりも長
くなるよう、ルート計算に対する統計的な速度、ルート
形式および目下の速度の関数として決定する。
的地点までの距離を、中間目的地点までにかかる推定走
行時間が完全なルートの計算にかかる推定期間よりも長
くなるよう、ルート計算に対する統計的な速度、ルート
形式および目下の速度の関数として決定する。
さらに本発明によれば前述の課題は、出発地点から目
的地点までの走行ルートを決定するためのナビゲーショ
ンシステムにおいて、ディジタル化された道路網を格納
している不揮発性記憶装置と、前記不揮発性記憶装置と
接続されたマイクロプロセッサとユーザインタフェース
が設けられており、前記マイクロプロセッサは、出発地
点から目的地点までのルートを決定するようプログラミ
ングされていて、出発地点から中間目的地点までの部分
ルートを計算し、出発地点から目的地点までの完全なル
ートを計算し、出発地点から中間目的地点までの部分ル
ートを、出発地点から目的地点までの完全なルートとオ
ーバラップさせ、前記ユーザインタフェースは、完全な
ルートが計算され部分ルートとオーバラップするまで、
部分ルート情報をユーザに提供し、部分ルートから目的
地点までつながる完全なルート情報をユーザに提供する
ことにより解決される。
的地点までの走行ルートを決定するためのナビゲーショ
ンシステムにおいて、ディジタル化された道路網を格納
している不揮発性記憶装置と、前記不揮発性記憶装置と
接続されたマイクロプロセッサとユーザインタフェース
が設けられており、前記マイクロプロセッサは、出発地
点から目的地点までのルートを決定するようプログラミ
ングされていて、出発地点から中間目的地点までの部分
ルートを計算し、出発地点から目的地点までの完全なル
ートを計算し、出発地点から中間目的地点までの部分ル
ートを、出発地点から目的地点までの完全なルートとオ
ーバラップさせ、前記ユーザインタフェースは、完全な
ルートが計算され部分ルートとオーバラップするまで、
部分ルート情報をユーザに提供し、部分ルートから目的
地点までつながる完全なルート情報をユーザに提供する
ことにより解決される。
従属請求項には、本発明のその他の特徴が示されてい
る。
る。
本発明を、ルートを決定する方法および装置における
実現形態として説明してきたけれども、図示した詳細な
点に制約されるものではない。つまり本発明の着想を逸
脱せず請求の範囲の枠内で、様々な修正や変形を行うこ
とができる。
実現形態として説明してきたけれども、図示した詳細な
点に制約されるものではない。つまり本発明の着想を逸
脱せず請求の範囲の枠内で、様々な修正や変形を行うこ
とができる。
次に、本発明の構成や動作方法について図面を参照し
ながら以下の実施例に基づき説明する。
ながら以下の実施例に基づき説明する。
図面の簡単な説明 図１は、本発明で使用するための車両用ナビゲーショ
ンシステムのブロック図である。
ンシステムのブロック図である。
図２は、本発明の１つの実施形態の動作を説明するフ
ローチャートである。
ローチャートである。
有利な実施形態の説明 次に図面を参照すると、殊にそれらのうち図１を参照
すると、本発明で使用するための車両用ナビゲーション
システムの１つの実施形態に関するブロック図が示され
ている。この場合、マイクロプロセッサまたはCPU21
は、データバス10およびセンサインタフェース41を介し
て位置情報を受け取る。典型的にはセンサインタフェー
ス41には、走行距離センサ、角速度センサならびにGPS
センサが接続されている。CPU21は、このようにして受
信したセンサ信号から車両の現在位置を判定する。さら
にCPU21は信号を処理し、推測航法ならびにルートガイ
ダンス機能を実行する。
すると、本発明で使用するための車両用ナビゲーション
システムの１つの実施形態に関するブロック図が示され
ている。この場合、マイクロプロセッサまたはCPU21
は、データバス10およびセンサインタフェース41を介し
て位置情報を受け取る。典型的にはセンサインタフェー
ス41には、走行距離センサ、角速度センサならびにGPS
センサが接続されている。CPU21は、このようにして受
信したセンサ信号から車両の現在位置を判定する。さら
にCPU21は信号を処理し、推測航法ならびにルートガイ
ダンス機能を実行する。
CPU21のオペレーションを指示するソフトウェアは、R
AM22に格納されている。これに加えて、ナビゲーション
システムの基本オペレーティングシステムを有するリー
ドオンリーメモリ（ROM）を設けることができる。
AM22に格納されている。これに加えて、ナビゲーション
システムの基本オペレーティングシステムを有するリー
ドオンリーメモリ（ROM）を設けることができる。
CD−ROM23によってディジタル化された道路網情報が
提供され、これは出発地点からユーザにより選択された
目的地点までのルートを決定するためのベースとなる。
提供され、これは出発地点からユーザにより選択された
目的地点までのルートを決定するためのベースとなる。
CPU21はガイダンス情報を計算し、これは出力コント
ローラ31を介してディスプレイ32へ伝達される。光学的
出力ではなく、音響的出力を行うことも同様に可能であ
る。ディスプレイによりドライバまたはユーザに対し操
作が必要である旨警告が発せされ、これはその操作を行
うべき各々の位置に車両が到達する前の所定の時点で発
せられる。
ローラ31を介してディスプレイ32へ伝達される。光学的
出力ではなく、音響的出力を行うことも同様に可能であ
る。ディスプレイによりドライバまたはユーザに対し操
作が必要である旨警告が発せされ、これはその操作を行
うべき各々の位置に車両が到達する前の所定の時点で発
せられる。
次に図２を参照すると、そこに描かれているフローチ
ャートは、本発明によるナビゲーションシステムの１つ
の実施形態の動作を表している。ステップ100により、
部分ルート計算の開始が示されている。部分ルートは、
（たとえばユーザインタフェースにおいて現在位置を入
力し目下のGPS入力をシステムが読み出すようにするこ
とで）ドライバにより選択された出発地点から、CPU21
により求められた中間目的地点まで延びている。指標ｉ
が０にセットされ（ステップ101）、このことは部分ル
ートPRの決定に対する初めての試みであることを表す。
ユーザにより選択された出発地点すなわちソースSRC0か
ら中間目的地点すなわちテンポラリソースTSRC0までの
部分ルートPR0が、CPUにより計算される（ステップ10
2）。実際には、部分ルートの長さが最終目的地点まで
の完全なルートの長さの約10％にセットされていれば、
良好な結果を得ることができる。これによって、ソース
と中間目的地点と間の距離がかなり短くなり、きわめて
迅速に計算できるようになる。それに応じて、計算され
た部分ルートの追従に必要な走行計画（maneuver）が、
ドライバまたはユーザがその目的地点を選択した後、き
わめてすみやかに行われるようになる。とはいっても、
出発地点SRC0から選択された目的地点までの完全なルー
トの計算は通常、車両が中間目的地点TSRC0に到達する
前に終えることができる。しかしながら、完全なルート
の計算時間を考慮することにより、部分ルートの最適な
長さを求めることもできる。中間目的地点ないしは中間
目的地点および完全なルートの洗練された計算の詳細に
ついては、上述の刊行物ヨーロッパ特許出願EP 0 726 4
47 A1を参照のこと。なお、この刊行物を本願発明の参
考文献とする。
ャートは、本発明によるナビゲーションシステムの１つ
の実施形態の動作を表している。ステップ100により、
部分ルート計算の開始が示されている。部分ルートは、
（たとえばユーザインタフェースにおいて現在位置を入
力し目下のGPS入力をシステムが読み出すようにするこ
とで）ドライバにより選択された出発地点から、CPU21
により求められた中間目的地点まで延びている。指標ｉ
が０にセットされ（ステップ101）、このことは部分ル
ートPRの決定に対する初めての試みであることを表す。
ユーザにより選択された出発地点すなわちソースSRC0か
ら中間目的地点すなわちテンポラリソースTSRC0までの
部分ルートPR0が、CPUにより計算される（ステップ10
2）。実際には、部分ルートの長さが最終目的地点まで
の完全なルートの長さの約10％にセットされていれば、
良好な結果を得ることができる。これによって、ソース
と中間目的地点と間の距離がかなり短くなり、きわめて
迅速に計算できるようになる。それに応じて、計算され
た部分ルートの追従に必要な走行計画（maneuver）が、
ドライバまたはユーザがその目的地点を選択した後、き
わめてすみやかに行われるようになる。とはいっても、
出発地点SRC0から選択された目的地点までの完全なルー
トの計算は通常、車両が中間目的地点TSRC0に到達する
前に終えることができる。しかしながら、完全なルート
の計算時間を考慮することにより、部分ルートの最適な
長さを求めることもできる。中間目的地点ないしは中間
目的地点および完全なルートの洗練された計算の詳細に
ついては、上述の刊行物ヨーロッパ特許出願EP 0 726 4
47 A1を参照のこと。なお、この刊行物を本願発明の参
考文献とする。
（ステップ103の問い合わせにおいて）部分ルートが
以前に計算されていたことがわかれば、つまりｉ−１が
負の数すなわち−１であれば、部分ルートのための走行
計画が発生される（ステップ104）。
以前に計算されていたことがわかれば、つまりｉ−１が
負の数すなわち−１であれば、部分ルートのための走行
計画が発生される（ステップ104）。
部分ルートに対する個々の走行計画をユーザに通報し
ている間、ソースSRCiから目的地点への完全なルートが
バックグラウンドで計算される（ステップ105）。
ている間、ソースSRCiから目的地点への完全なルートが
バックグラウンドで計算される（ステップ105）。
完全なルートCRiと部分ルートPRiとの間の交差地点を
突き止める目的で、このようにして計算された完全なル
ートCRiが部分ルートPRiとオーバラップされる（ステッ
プ106）。
突き止める目的で、このようにして計算された完全なル
ートCRiが部分ルートPRiとオーバラップされる（ステッ
プ106）。
少なくとも１つの交差地点が存在しているならば、部
分ルートから完全なルートへの変更を許容できるか否か
が判定される（ステップ107）。目下表示されている走
行計画または命令と矛盾するならば、変更は認められな
い。これによって、ドライバを混乱させる要因が確実に
回避される。しかも、異なる道路への進路を変えること
が禁止されることになり、あるいは直前の適切な中間目
的地点がすでに通過していることになる。
分ルートから完全なルートへの変更を許容できるか否か
が判定される（ステップ107）。目下表示されている走
行計画または命令と矛盾するならば、変更は認められな
い。これによって、ドライバを混乱させる要因が確実に
回避される。しかも、異なる道路への進路を変えること
が禁止されることになり、あるいは直前の適切な中間目
的地点がすでに通過していることになる。
車両の現在位置、目下のガイダンス状態あるいは期限
の制約から、完全なルートへの変更が許されるならば、
部分ルートPRiと完全なルートCRiが結合される。したが
って部分ルートは、部分ルートPRiと完全なルートCRiと
の間の所定の交差地点へ進み、これに続いてその交差地
点から目的地点まで完全なルートが続く（ステップ10
8）。
の制約から、完全なルートへの変更が許されるならば、
部分ルートPRiと完全なルートCRiが結合される。したが
って部分ルートは、部分ルートPRiと完全なルートCRiと
の間の所定の交差地点へ進み、これに続いてその交差地
点から目的地点まで完全なルートが続く（ステップ10
8）。
オーバラップされたルートのための走行計画が交差地
点から目的地点まで発生され（ステップ109）、ルート
計算はステップ115で終了する。
点から目的地点まで発生され（ステップ109）、ルート
計算はステップ115で終了する。
約50％の事例で、所定の部分ルートは完全なルートが
計算されたときに見つけられた最適なルートと一致しな
いことから、部分ルートと完全なルートのオーバラップ
によって、完全なルートからの逸脱が最小化される。ま
た、約95％の事例において、部分ルートから完全なルー
トへの許容可能な変更を、部分ルートと完全なルートと
の最初のオーバラップで見出すことができるので、シス
テムはガイダンス時間全体にわたりビジー状態のままに
なることはない。最も多い事例では、部分ルートの計算
と完全なルートの計算のための時間しか必要とされな
い。
計算されたときに見つけられた最適なルートと一致しな
いことから、部分ルートと完全なルートのオーバラップ
によって、完全なルートからの逸脱が最小化される。ま
た、約95％の事例において、部分ルートから完全なルー
トへの許容可能な変更を、部分ルートと完全なルートと
の最初のオーバラップで見出すことができるので、シス
テムはガイダンス時間全体にわたりビジー状態のままに
なることはない。最も多い事例では、部分ルートの計算
と完全なルートの計算のための時間しか必要とされな
い。
部分ルートと完全なルートとの間に交差地点を見つけ
ることができないか（ステップ106）、あるいは部分ル
ートから完全なルートへの許容可能な変更が見出されな
ければ（ステップ107）、新たな「スターティングポイ
ント」つまりソースSRCi+1を規定する目的で、部分ルー
トが車両の現在位置へ向かう方向へ戻される（ステップ
110およびステップ102へのループバック中の指標インク
リメント）。車両の現在位置と新たなソースSRCi+1との
間の距離は、新たな部分ルートPRi+1の新たなソース計
算を、車両がその方向へ向かっている間に完了させるの
に十分な大きさにすべきである。このことにより、車両
のドライバに対し継続的に、矛盾のない走行計画や命令
を与えることができるようになる。
ることができないか（ステップ106）、あるいは部分ル
ートから完全なルートへの許容可能な変更が見出されな
ければ（ステップ107）、新たな「スターティングポイ
ント」つまりソースSRCi+1を規定する目的で、部分ルー
トが車両の現在位置へ向かう方向へ戻される（ステップ
110およびステップ102へのループバック中の指標インク
リメント）。車両の現在位置と新たなソースSRCi+1との
間の距離は、新たな部分ルートPRi+1の新たなソース計
算を、車両がその方向へ向かっている間に完了させるの
に十分な大きさにすべきである。このことにより、車両
のドライバに対し継続的に、矛盾のない走行計画や命令
を与えることができるようになる。
新たなソースSRCi+1から出発して、新たな中間目的地
点TSRCi+1までの新たな部分ルートPRi+1が計算される
（ステップ102）。
点TSRCi+1までの新たな部分ルートPRi+1が計算される
（ステップ102）。
この場合にはステップ102における問い合わせによっ
て、部分ルートPRｉ＝０のような以前の部分ルートが存
在していることが判別されることになる。
て、部分ルートPRｉ＝０のような以前の部分ルートが存
在していることが判別されることになる。
その後、以前の部分ルートPRi-1（たとえばPR0）と、
新たな部分ルートPRi（たとえばPR1）が結合される（ス
テップ111）。
新たな部分ルートPRi（たとえばPR1）が結合される（ス
テップ111）。
ついでシステムは、結合された２つの部分ルートにお
ける交差地点または共通のルート区間が存在するか否か
がチェックされる（ステップ112）。
ける交差地点または共通のルート区間が存在するか否か
がチェックされる（ステップ112）。
存在しなければ、プログラムはステップ104へジャン
プし、そこにおいて結合されたその部分ルートの走行計
画が発せられ、ステップ104から始まり先に述べたよう
にして後続のステップが実行される。
プし、そこにおいて結合されたその部分ルートの走行計
画が発せられ、ステップ104から始まり先に述べたよう
にして後続のステップが実行される。
結合された部分ルート上に交差地点または共通セグメ
ントが存在しているならば（ステップ112における問い
合わせ）システムは、この結合された部分ルートを交差
なく構成可能であるか否かを問い合わせる（ステップ11
3）。補正が不可能である場合、および補正を行うこと
ができたならば（ステップ114）、結合された部分ルー
トに対する走行計画が発せられ（ステップ104）、ステ
ップ105から始まって上述のように後続のステップが実
行される。
ントが存在しているならば（ステップ112における問い
合わせ）システムは、この結合された部分ルートを交差
なく構成可能であるか否かを問い合わせる（ステップ11
3）。補正が不可能である場合、および補正を行うこと
ができたならば（ステップ114）、結合された部分ルー
トに対する走行計画が発せられ（ステップ104）、ステ
ップ105から始まって上述のように後続のステップが実
行される。
フロントページの続き (56)参考文献 特開 平９−14985（ＪＰ，Ａ) 特開 平８−292059（ＪＰ，Ａ) 特開 平８−261783（ＪＰ，Ａ) 特開 平６−214977（ＪＰ，Ａ) 特開 平４−365088（ＪＰ，Ａ) (58)調査した分野(Int.Cl.7，ＤＢ名) G01C 21/00 G08G 1/0969 G09B 29/00 - 29/10
Claims (9)
- 【請求項１】ナビゲーションシステムの不揮発記憶装置
に格納されているディジタル化された道路網上に位置す
る出発地点から目的地点までの走行ルートを決定する方
法において、 出発地点と目的地点との間の中間目的地点を規定し、 出発地点から中間目的地点までの部分ルートを計算し
て、部分ルート情報をユーザインタフェースへ出力し、 出発地点から目的地点までの完全なルートを計算し、 完全なルートと部分ルートとをオーバラップさせ、完全
なルートと部分ルートとの間の交差地点を規定し、 交差地点から始める完全なルート情報を出力することを
特徴とする、 走行ルートを決定する方法。 - 【請求項２】部分ルートのための走行計画を発生させ、
部分ルートの走行計画を部分ルート情報として表示さ
せ、完全なルートのための走行計画を発生させ、完全な
ルートの走行計画を完全なルートの情報として表示させ
る、請求項１記載の方法。 - 【請求項３】部分ルートと完全なルートが、ユーザがま
だ通過していなかった走行ルートの区間内で交差してい
れば、完全なルートの走行計画を交差地点から出発して
出力する、請求項２記載の方法。 - 【請求項４】オーバラップステップにおいて、部分ルー
トと完全なルートとの間に交差地点が見出せなければ、 出発地点に向かう方向で、ユーザの現在位置よりは遠く
ない中間目的地点を戻し、 新たな出発地点を規定し、 次に新たな出発地点から始まり新たな中間目的地点まで
の新たな部分ルートを計算し、新たな部分ルート情報を
ユーザに出力し、 新たな出発地点から目的地点までの新たな完全なルート
を計算し、新たな完全なルートと新たな部分ルートをオ
ーバラップさせ、 新たな部分ルートと新たな完全なルートが少なくとも１
つの交差地点を有しているならば、交差地点から先に向
かう新たな完全なルート情報を出力する、 請求項１記載の方法。 - 【請求項５】新たな部分ルートと先行の部分ルートをオ
ーバラップさせ、新たな部分ルートと先行の部分ルート
が交差地点を有しているならば、新たな部分ルートを退
け、交差地点のない別の新たな部分ルートを計算する、
請求項４記載の方法。 - 【請求項６】新たな部分ルートと先行の部分ルートが交
差点を有しているが、交差地点のない別の部分ルートを
計算できなければ、新たな部分ルートのための走行計画
を発生させ出力させる、請求項４記載の方法。 - 【請求項７】中間目的地点に到達するために完全なルー
トの計算を完了できなければ、該中間目的地点から出発
してさらに別の目的地点までの別の部分ルートを計算す
る、請求項１記載の方法。 - 【請求項８】出発地点から中間目的地点までの距離を、
中間目的地点までにかかる推定走行時間が完全なルート
の計算にかかる推定期間よりも長くなるよう、ルート計
算のための統計的な速度、ルート形式および目下の速度
の関数として決定する、請求項１記載の方法。 - 【請求項９】出発地点から目的地点までの走行ルートを
決定するためのナビゲーションシステムにおいて、 ディジタル化された道路網を格納している不揮発性記憶
装置と、 前記不揮発性記憶装置と接続されたマイクロプロセッサ
とユーザインタフェースが設けられており、 前記マイクロプロセッサは、出発地点から目的地点まで
のルートを決定するようプログラミングされていて、出
発地点から中間目的地点までの部分ルートを計算し、出
発地点から目的地点までの完全なルートを計算し、出発
地点から中間目的地点までの部分ルートを、出発地点か
ら目的地点までの完全なルートとオーバラップさせ、 前記ユーザインタフェースは、完全なルートが計算され
部分ルートとオーバラップするまで、部分ルート情報を
ユーザに提供し、部分ルートから目的地点までつながる
完全なルート情報をユーザに提供することを特徴とす
る、 走行ルートを決定するためのナビゲーションシステム。
Applications Claiming Priority (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US861,855 | 1997-05-22 | ||
| US08/861,855 | 1997-05-22 | ||
| US08/861,855 US6112154A (en) | 1997-05-22 | 1997-05-22 | Method and apparatus for determining a route on a digitized road network stored in the memory of a navigation system |
| PCT/EP1998/002941 WO1998053274A1 (en) | 1997-05-22 | 1998-05-19 | Method and apparatus for determining a route |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2000513107A JP2000513107A (ja) | 2000-10-03 |
| JP3249140B2 true JP3249140B2 (ja) | 2002-01-21 |
Family
ID=25336948
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP54994698A Expired - Fee Related JP3249140B2 (ja) | 1997-05-22 | 1998-05-19 | ルートを決定する方法および装置 |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US6112154A (ja) |
| EP (1) | EP0983485B1 (ja) |
| JP (1) | JP3249140B2 (ja) |
| KR (1) | KR100371020B1 (ja) |
| DE (1) | DE69818452T2 (ja) |
| WO (1) | WO1998053274A1 (ja) |
Families Citing this family (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE19928295A1 (de) * | 1999-06-22 | 2000-12-28 | Bosch Gmbh Robert | Verfahren und Vorrichtung zum Bestimmen einer Route von einem Ausgangsort zu einem Zielort |
| US6456931B1 (en) * | 2001-03-07 | 2002-09-24 | Visteon Technologies, Llc | Indicating directions to destination and intermediate locations in vehicle navigation systems |
| EP1376061A1 (en) * | 2002-06-19 | 2004-01-02 | Siemens Aktiengesellschaft | A method for calculating a motor vehicle navigation route to a destination and a system and motor vehicle applying such method |
| DE10329507A1 (de) * | 2003-06-30 | 2005-02-10 | Siemens Ag | Verfahren und Navigationssystem zur Routenbestimmung mit Zwischenzielen |
| US8606516B2 (en) | 2004-11-30 | 2013-12-10 | Dash Navigation, Inc. | User interface system and method for a vehicle navigation device |
| DE102005021271B3 (de) * | 2005-05-09 | 2006-12-07 | Siemens Ag | Verfahren zur Berechnung einer Route in einem Navigationssystem |
| JP7151526B2 (ja) * | 2019-02-08 | 2022-10-12 | トヨタ自動車株式会社 | 自動駐車管理装置 |
Family Cites Families (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5422812A (en) * | 1985-05-30 | 1995-06-06 | Robert Bosch Gmbh | Enroute vehicle guidance system with heads up display |
| DE3719017A1 (de) * | 1987-06-06 | 1988-12-15 | Bosch Gmbh Robert | Verfahren und vorrichtung zur bestimmung einer fahrtroute zwischen einem startpunkt und einem zielpunkt |
| US5177685A (en) * | 1990-08-09 | 1993-01-05 | Massachusetts Institute Of Technology | Automobile navigation system using real time spoken driving instructions |
| US5412573A (en) * | 1993-05-20 | 1995-05-02 | Motorola Inc. | Multi-mode route guidance system and method therefor |
| JPH07294267A (ja) * | 1994-04-28 | 1995-11-10 | Pioneer Electron Corp | 経路設定方法及び経路設定装置 |
| US5712788A (en) * | 1995-02-09 | 1998-01-27 | Zexel Corporation | Incremental route calculation |
| JPH0914984A (ja) * | 1995-06-28 | 1997-01-17 | Aisin Aw Co Ltd | 車両用ナビゲーション装置 |
| JPH0914985A (ja) * | 1995-06-30 | 1997-01-17 | Hitachi Ltd | 経路探索方法および装置 |
| US5910177A (en) * | 1996-12-09 | 1999-06-08 | Visteon Technologies, Llc | Navigating close proximity routes with a vehicle navigation system |
-
1997
- 1997-05-22 US US08/861,855 patent/US6112154A/en not_active Expired - Lifetime
-
1998
- 1998-05-19 JP JP54994698A patent/JP3249140B2/ja not_active Expired - Fee Related
- 1998-05-19 WO PCT/EP1998/002941 patent/WO1998053274A1/en active IP Right Grant
- 1998-05-19 EP EP98930707A patent/EP0983485B1/en not_active Expired - Lifetime
- 1998-05-19 KR KR10-1999-7010705A patent/KR100371020B1/ko not_active IP Right Cessation
- 1998-05-19 DE DE69818452T patent/DE69818452T2/de not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| EP0983485B1 (en) | 2003-09-24 |
| WO1998053274A1 (en) | 1998-11-26 |
| US6112154A (en) | 2000-08-29 |
| DE69818452T2 (de) | 2004-05-06 |
| DE69818452D1 (de) | 2003-10-30 |
| KR100371020B1 (ko) | 2003-02-05 |
| KR20010012744A (ko) | 2001-02-26 |
| EP0983485A1 (en) | 2000-03-08 |
| JP2000513107A (ja) | 2000-10-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3065978B2 (ja) | 車両ナビゲーションシステムにおける代替ルートを決定する方法および装置 | |
| JP3384172B2 (ja) | 車両用走行案内装置 | |
| EP1086358B1 (en) | Navigation system | |
| EP0375817B1 (en) | Navigation apparatus | |
| JP3632706B2 (ja) | 車両用ナビゲーション装置 | |
| EP0901001B1 (en) | Method and apparatus for displaying current position of a vehicle | |
| US5904728A (en) | Voice guidance timing in a vehicle navigation system | |
| JP3322268B2 (ja) | 陸上車両の多重ナビゲーション経路装置 | |
| JP5209836B2 (ja) | ルート計算方法 | |
| JP3754110B2 (ja) | 動的経路探索方法およびナビゲーション装置 | |
| US20040068366A1 (en) | Car navigation system prioritizing automatic travel road | |
| JPH10185602A (ja) | 車両ナビゲーションシステムにより近接ルートを案内する方法及び装置 | |
| WO2002061377A1 (fr) | Procede de guidage routier jusqu'a une destination | |
| JP3064582B2 (ja) | 車両用経路探索装置 | |
| US20040181336A1 (en) | Navigation system | |
| JP3249140B2 (ja) | ルートを決定する方法および装置 | |
| JP3941605B2 (ja) | カーナビゲーション装置 | |
| JP2006350953A (ja) | カーナビゲーション装置 | |
| JPH0989579A (ja) | 走行軌跡表示機能を備えたナビゲーション装置 | |
| JP3328091B2 (ja) | 経路誘導装置 | |
| JP3718991B2 (ja) | 車載用ナビゲーション装置および記録媒体 | |
| JP3309670B2 (ja) | 車両用ナビゲーション装置 | |
| JP3033358B2 (ja) | ナビゲーション装置 | |
| JP3805413B2 (ja) | 車両用走行案内装置 | |
| JP2984645B2 (ja) | 車両用ナビゲーション装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20071109 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081109 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081109 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20091109 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101109 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111109 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111109 Year of fee payment: 10 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111109 Year of fee payment: 10 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111109 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121109 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121109 Year of fee payment: 11 |
|
| RD02 | Notification of acceptance of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: R3D02 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121109 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20131109 Year of fee payment: 12 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| LAPS | Cancellation because of no payment of annual fees |