増分経路計算方法
【課題】地図データベースを有するビークルナビゲーションシステムを使用して源位置から最終行き先までの経路を決定する方法及び装置。
【解決手段】少なくとも１つの中間行き先を地図データベースから決定する。各中間行き先は源位置からの中間経路の他端にある。各中間行き先毎の費用値を計算する。少なくとも１つの中間行き先から最良中間行き先を選択する。最良中間行き先に対応する費用値は他のどの中間行き先に対応する費用値よりも低い。次いで最良中間行き先に対応する中間経路がビークルナビゲーションシステムの利用者に伝えられ、同時に最終行き先までの残りの経路が決定される。
【解決手段】少なくとも１つの中間行き先を地図データベースから決定する。各中間行き先は源位置からの中間経路の他端にある。各中間行き先毎の費用値を計算する。少なくとも１つの中間行き先から最良中間行き先を選択する。最良中間行き先に対応する費用値は他のどの中間行き先に対応する費用値よりも低い。次いで最良中間行き先に対応する中間経路がビークルナビゲーションシステムの利用者に伝えられ、同時に最終行き先までの残りの経路が決定される。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、ビークルナビゲーションシステムによる経路の決定に関する。より詳しくは本発明は、全経路の決定が、与えられた時間よりも長くかかる場合に、利用者の最終行き先までの中間経路を決定する方法及び装置を提供する。このようにすると、最終行き先までの全経路が決定される前に利用者は走行を開始することが可能になる。
【０００２】
【従来の技術】本発明は以下に列挙する特許及び特許出願に関係がある。
【０００３】Kao の米国特許第 5,345,382号“ CALIBRAION METHOD FOR A RELATIVE HEADING SENSOR”、Sniderの米国特許第 5,359,529号“ ROUTE GUIDANCE ON/OFF-ROUTOE STATE FILTER”、1993年１月５日に同時出願された米国特許出願第 08/000,950 号“ POSITIONCORRECTION METHOD FOR VEHICLE NAVIGATION SYSTEM ”、1993年７月29日に出願された米国特許出願第 08/099,207 号“ METHOD FOR SELECTING A DESTINATION IN A VEHICLE NAVIGATION SYSTEM”、1994年６月20日に出願された米国特許出願第 08/263,604 号“ METHOD FOR IDENTIFYING HIGHWAY ACCESS RAMPS FOR ROUTE CALCULATION IN A VEHICLE NAVIGATION SYSTEM ”、1994年８月19日に出願された米国特許出願第 08/293,856 号“ VEHICLE NAVIGATION SYSTEM WITH UPGRADEABLE NAVIGATION SOFTWARE AND A FLEXIBLE MEMORYCONFIGURATION ”。
【０００４】
【発明が解決しようとする課題】利用可能な地図データベースのカバレッジ及び特徴が高密度になるにつれて、長距離経路の計算に要する時間も相応して増加する。経路が特に長いか、もしくは複雑な場合には、利用者が始めの位置から出発するまでに望ましくない遅れがもたらされる。もし経路が計算される前に利用者が出発を決断すれば、利用者はナビゲーションシステムからの指示を受けずに運転することになるので、最終的には計算される経路から逸脱する恐れがあるから、計算が無用なものになってしまう。もし全経路の計算が完了する前に最初の幾つかの指示または誘導を決定してそれを利用者に伝える方法があれば、長い経路の計算時間の上述した効果を軽減することができる。
【０００５】
【課題を解決するための手段】本発明は、始めの出発位置、即ち源位置と、最終行き先との間のある位置までの中間経路を決定できる方法を提供する。一般にビークルナビゲーションシステムの利用者が走行を開始するためには、最寄りのハイウェイに到達するのに十分な情報だけがあればよい。この目的のために、本発明は、フリーウェイ入路ランプのような中間行き先を選択し、その中間行き先に到達するのに必要な誘導を利用者に伝え、同時に最終行き先までの残余の経路を計算する。全経路の計算よりも遥かに少ない計算量である中間位置までの経路の決定には数秒しかかからず、従って利用者は全経路を知る前に運転を開始することができる。
【０００６】本発明によれば、ビークルナビゲーションシステムを使用して源位置から最終行き先までの経路を決定する方法及び装置が開示される。特定の実施例では、少なくとも１つの中間行き先がシステムの地図データベースから決定される。各中間行き先は、源位置からの対応する中間経路の一端にある。１より多い中間行き先が見出された場合には、各行き先毎に費用値を計算し、それに基づいて、考え得る中間行き先の中から最良中間行き先、即ち最低の費用値を有する中間行き先が選択される。次に、この最良中間行き先に対応する中間経路がビークルナビゲーションシステムの利用者に伝えられ、同時に最終行き先までの残余の経路が決定される。
【０００７】本発明の別の実施例では、地図データベース内の道路は階層的に編成されており、各道路はそれに関連する階層レベルを有している。源位置は第１の階層レベルの源道路に対応する。この実施例では、中間行き先は以下のようにして決定される。源位置に接続されている第１の道路セグメントからの考え得る経路が、第１の階層レベルよりも高い第２の階層レベルを有する接続道路に出会うまで探査される。次に、この接続道路への入路点が中間行き先として指定される。これは源位置から伸びる各道路セグメント毎に繰り返される。
【０００８】別の実施例では、各中間道路は少なくとも１つのノードと、少なくとも１つの道路セグメントとを含み、これらは地図データベース内に記憶されており、またこれらは源位置をその中間経路に対応する中間行き先に接続している。地図データベース内の各ノードは関連するノード費用を有しており、地図データベース内の各道路セグメントは関連するセグメント費用を有している。この実施例では、中間行き先に関する費用値は以下のようにして計算される。中間経路内の道路セグメントに関するセグメント費用及びノードに関するノード費用が組合わされ、それによって中間経路に関する経路費用が生成される。次いで、中間経路に関連する中間行き先に関する発見的費用が決定される。この発見的費用は、中間行き先と最終行き先との間の距離に対応する。次に、経路費用と発見的費用とが組合わされ、それによって中間行き先に関する費用値が生成される。この手順は、残余のどの中間行き先についても繰り返される。種々の実施例では、セグメント費用は、ある道路セグメントを走行するのに必要な時間の推定に対応し、ノード費用はあるノードを走行するのに必要な時間の推定に対応し、そして第１の距離は第１の中間行き先と最終行き先との間の実質的に直線距離に対応する。
【０００９】更に別の実施例では、本発明は、タイムアウト時間が経過するまで最良中間行き先を選択するのを待機する。このようにする理由は、もしタイムアウト時間が経過する前に最終行き先までの全経路が決定されれば、中間経路を伝えることは不要になり、その代わりに全経路を伝えればよいからである。特定の実施例においては、与えられたタイムアウト時間が経過するまでに最終行き先までの全経路の決定が完了しなければ、システムは第１の中間行き先と最終行き先との間に別の中間行き先を決定する。始めに、少なくとも１つの次の中間行き先を地図データベースから決定する。先行実施例と同様に、もし１より多くの次の中間行き先が見出されれば、各中間行き先毎に費用値が計算され、最低の費用値を有する次の中間行き先が次の最良中間行き先として選択される。次いで、次の最良中間行き先に対応する次の中間経路が利用者に伝えられる。このプロセスは、全経路の残りが決定されてしまうまで繰り返すことができる。特定実施例では、全経路の残りの決定がプログラム可能なタイムアウト時間よりも長い時間を要する場合に限って、各中間経路が完全に決定され、利用者に伝えられる。
【００１０】本発明の本質及び長所は、以下の明細書の部分及び添付図面から明白になるであろう。
【００１１】
【発明の実施の形態】図１は、本発明と共に使用するビークルナビゲーションシステム１０の実施例のブロック線図である。センサ１２及び１４、及びＧＰＳ受信機１８がセンサ／ＧＰＳインタフェース２２を通して計算手段２０に結合されている。典型的な実施例では、距離センサ１２はオドメータ（走行距離計）からなり、角速度センサ１４はジャイロスコープ、もしくはビークルの車輪に結合されている差動オドメータからなる。汎地球測位システム（ＧＰＳ）データ受信機１８は、例えば衛星をベースとするナビゲーションシステムからの信号を受信するために設けられている。センサ／ＧＰＳインタフェース２２からのデータはＣＰＵ２４へ伝えられ、ＣＰＵ２４は較正、信号処理、位置推測、ビークル位置決め、及び経路案内機能を遂行する。地図情報を含むデータベースはデータベース媒体２６内に記憶させることができ、主メモリ２８内に記憶されている計算手段２０の動作をＣＰＵ２４によって実行させるようにソフトウェアが指示する。メモリ２８は読み出し専用メモリ（ＲＯＭ）、もしくはフラッシュメモリまたはＳＲＡＭのような再プログラム可能な非揮発性メモリからなっていてよい。システムＲＡＭ３０は、これらのソフトウェアプログラムを実行するのに必要な情報を読み出したり、書き込むことができる。データベース媒体２６は、デジタル化された地図情報が記憶されている非揮発性メモリ、ハードディスクドライブ、ＣＤ−ＲＯＭ、もしくは集積回路からなることができる。グラフィックスコントローラからなることができる出力コントローラ３２は、ＣＰＵ２４が処理したデータを受信し、そのデータを表示コンソール４０へ伝送する。表示コンソール４０は、通常は表示画面を備えている出力伝達装置３４を含む。利用者は、典型的にはキーボードからなるユーザインタフェース３６を通して、所望の行き先のようなデータを入力することができる。データベース媒体２６内に記憶されている地図データベースは、道路の交差点即ちノード、道路セグメント、陸標、及び関心のある点、及び他の地理的な情報を記述するための（例えば緯度及び経度座標のような）位置データを含んでいることが好ましい。データベースは、道路及び場所名のような地図上の道路もしくは場所の特徴、分岐、一方通行制限、表面、速度制限、形状、高度、その他の特性のような道路の特色を表すデータをも含むことができる。本発明の一実施例によれば地図データベースは、個々のノード及び道路セグメントに関連した費用値を含む。これらの費用値は、それぞれのノード及び道路セグメントを走行するための時間の推定に対応している。ノード費用値は、例えばビークルが対向車線の大きい交通量に遭遇して左（右）折操作が遅れるか否かのような情報を考えている。セグメント費用は、そのセグメントに沿って走行する際の走行時間に影響を与える速度制限及びセグメント長のような道路セグメント特性を反映している。地図データベース内の各道路にはその道路のカテゴリもしくは型に関係する階層値も組合わされている。例えば、最高レベルの階層のカテゴリにはフリーウェイ及び高速道路が含まれる。最低レベルには住宅地街路及び／または細い小道が含まれる。
【００１２】図１のビークルナビゲーションシステムを使用して源位置Ａから最終行き先Ｂまでの経路の決定は、図２を参照すると理解し易い。本発明の一実施例では、ビークルナビゲーションシステム１０は２端法( two-ended ) 経路計算アルゴリズムを使用する。即ち、システム１０は、点Ａから発する通路「及び」点Ｂから後方へ戻る通路を探査する。始めに、探索パターンが点Ａ及びＢの両方から全方向に発せられる。図２は、点Ａから発する４本の道路セグメントの１つが、どのようにしてその後の経路探査のために選択されるかを示している。各道路セグメントｎは関連するセグメント費用ｇ(n) を有し、各ノードｋは関連するノード費用ｇ(k) 及び発見的費用及びｈ(k) を有している。各セグメント毎のセグメント費用は、その端点のノード費用及び発見的費用に加算され、各々毎に総合費用値が求められる。最低の総合費用値を有する道路セグメントが、さらなる計算のために選択される。図２において、点Ｄで終端する道路セグメントが一次的に選択される。それは、点Ｄに関連する発見的費用、即ち点ＤとＢとの間の距離が点Ｃ、Ｅ、及びＦに関連する発見的費用よりも少ないからである。このプロセスは点Ｄに関して、及び新たに計算された各経路点に関して繰り返される。考え得る新しい各経路点毎の発見的費用が、その考え得る経路点と、探索の他端において最後に決定された経路点との間の距離に基づいて計算されることに注目されたい。
【００１３】これは経路計算の進行に伴って探索領域を向け直して狭めることになるので、探索は点Ａと点Ｂとの間の領域に一層集中するようになる。発見的費用が０である点にシステムが到達すると、経路計算は完了する。本発明の一実施例では、ある道路セグメントが先行道路セグメントよりも高いカテゴリの経路内に含まれていることを何れかの端における探索アルゴリズムが識別すると、残余の経路決定プロセスにおいては低いカテゴリの道路セグメントは無視されることにも注目されたい。これは、殆どの論理的経路は一般的に、始まりにおいて道路カテゴリが増加し、終わりにおいて道路カテゴリが減少するという事実を反映している。例えば、典型的な経路は住宅地街路から始まって一般主要道路へ進み、そしてフリーウェイへ移る。利用者は最終行き先付近までフリーウェイを走行し続けることが多く、その点に到達するとフリーウェイから一般主要道路へ出て、住宅地街路へ達して終わる。
【００１４】特に高密度のデジタル化された地図データベースの場合には、上述した手順が高度に複雑になって決定に時間がかかるので、経路指示の伝達及び間もなく行われる運転操作に遅れがもたらされることは明白である。前述したように本発明は始めの源位置に近い中間行き先を選択し、中間位置までの経路を計算し、中間経路を伝え、そして同時に最終行き先までの経路の決定を継続することによって、これらの遅れを回避する。しかしながら、システムはこの機能を使用する時点をどのようにして知るのであろうか？ 一実施例においては、この機能は、始めの源位置と最終行き先との間の既知の関係、及びそれらの地理的な周囲状態（例えば両位置は、まばらにデジタル化された田園、もしくはハイウェイ領域によって分離された高密度にデジタル化された市街領域内にある）のようなパラメタに基づいて選択することができる。別の実施例では常に中間行き先が決定されるが、全経路の決定がプログラム可能なタイムアウト時間よりも長くかからなければ最良中間行き先は選択されず、その中間経路が利用者に伝えられることはない。この実施例の詳細に関しては後述する。中間行き先を選択する本発明の方法を、図３を参照して説明する。
【００１５】図３には、源位置である点Ａと、最終行き先である点Ｂとが示されている。一般的には、点Ａは静止したビークル出発位置を表す。しかしながら、もしビークルの移動中に経路計算が遂行されるのであれば、点Ａは現在のビークルの位置より前方の位置に選択することができる。このような状況では、源位置の決定に際して、ビークルの向き及び速度のようなパラメタを考慮することができる。点Ａから、４箇所の異なる中間行き先２０２、２０４、２０６及び２０８までの４本の考え得る中間経路２０１、２０３、２０５及び２０７が示されている。この例では、中間行き先はハイウェイ２１０及び２１２への入路点である。ハイウェイ入路点は、それらが容易に識別できること、及び上述した理由からハイウェイ入路点からの順方向経路計算が簡易になることから選択されることが多い。本質的に、源位置の道路よりも高いカテゴリにあるどのような道路との交差点も、考え得る中間行き先として選択することができる。
【００１６】更に図３を参照する。ナビゲーションシステムは、タイムアウト時間中に地図データベース内の点Ａから発する幾つかの考え得る通路を探査し、この探査の後に、その中間行き先について最良候補を選択する。タイムアウト時間は多重レベル時間間隔であることができる。即ち、この時間は、もし３もしくはそれ以上の候補が見出されれば 10 秒であるように、またもし１もしくは２候補しか見出されなければ 20 秒であるるようにプログラムすることができる。図は、ある中間行き先について４候補、即ちハイウェイ入路点２０２、２０４、２０６及び２０８が見出された状況を示している。一旦候補が選択されると、システムは、その行き先に達する経路のセグメント費用ｇ(n) 及びノード費用ｇ(k) の全てと、その行き先に関連する発見的費用、即ちｈ(dest)とを組合わせることによって、考え得る各中間行き先に関する総合費用ｆ(dest)を計算する。特定実施例では、この関係は次の数１ように表される。
【００１７】
【数１】
ｆ(dest)＝［Σroute ｇ(n) ＋ｇ(k) ］＋ｈ(dest)各中間経路の総合費用値を導出するために、これらの値を組合わせることが可能な、または費用値を割り当てることが可能な異なる方法が多数存在していることを理解されたい。本発明は、上述した特定実施例に限定されるものではない。
【００１８】中間行き先を選択する別の方法が本発明によって提供される。この実施例によれば、ハイウェイ及び源位置から 10 マイル以内にあるハイウェイ入路点のリストが利用者に提示される。利用者は、所望のハイウェイ及び／または特定の入路点を選択することができる。この機能は、例えばあるハイウェイへ乗る必要はあるが、現在の位置からそのハイウェイに乗るためには経路計算が必要であることを利用者が知っている場合に有用である。
【００１９】一旦中間行き先が選択され、中間経路が生成されると、システム表示を介して適切な運転操作が利用者に伝えられる。一般にこれらは一連の画面からなり、各画面は、例えば次の操作までの距離、もしくは次の操作の性質（例えば、左折）のような利用者が遂行すべき次の操作に関する情報を伝える。システムはこの情報を利用者に提供しながら、その中間行き先を出発点として使用して最終行き先までの残余の経路及び対応操作を決定する。このようにすると、全経路が決定される前に走行が可能になり、それによって利用者は殆ど直ちに走行を開始することができる。
【００２０】先に概要を説明したように本発明の特定実施例によれば、ビークルナビゲーションシステムは中間行き先を選択する前にタイムアウト時間の経過を待機するようにプログラムすることができる。もし最終行き先までの全経路がタイムアウト時間内に決定されれば、中間経路の伝達は不要と考えられ、中間行き先は選択されない。しかしながら、もし最終行き先までの全経路がタイムアウト時間が経過する前に完了しなければ、システムは中間行き先を選択して上述したように動作する。もし別のタイムアウト時間が経過しても未だ全経路の決定が完了しなければ、システムは第１の中間行き先より遠い別の中間行き先を決定するようにプログラムすることができる。次の中間行き先の選択も、上述した第１の中間行き先の選択と同様に進められる。全経路の残りが決定されてしまうまで、このプロセスを繰り返すことができる。代替として、システムは、もし最終行き先までの経路の計算が未だに完了しないことが決定されれば、直ちに次の中間行き先の決定を開始するようにプログラムすることが可能である。第１の中間行き先の場合と同様に、システムは、全経路の残りの決定が未だに完了しないか、もしくはプログラム可能なタイムアウト時間をより長く必要とする場合に限って、各連続中間経路を完全に決定し、対応する操作を利用者に伝えるようにプログラムすることができる。
【００２１】中間位置が近くて、全経路の決定が完了する前にビークルがその中間行き先に到達すればどのようになるか。もし中間位置がハイウェイ入路点であれば、そのハイウェイへ乗るように利用者に伝えられ、それに付け加えて、例えば「ハイウェイを走行し続けて下さい・残りの経路を計算中です」のような指令が発せられる。次に、ハイウェイをどの方向に走行するかを、システムはどのようにして知り、伝えるか。本発明の種々の実施例は以下のようにしてこの問題に対処している。一実施例によれば、最終行き先までのハイウェイ入路点からの方向に基づいて走行方向を推理する。別の実施例では、図４に示すように何れかの入路点３０２もしくは３０３より前に第１の中間行き先３０１を選択することによって、ハイウェイの方向が何れであるかを選択することができる。一方、第１の中間行き先より遠い別の中間行き先までの経路は、第１の中間行き先に到達するまでの時間によって知られる。
【００２２】第１の中間行き先に到達する上記の問題の別の解決法は、さらなる中間行き先を決定することである。本発明のこの実施例では、もしビークルが中間行き先に到達する時点までに全経路の決定が未だに完了していなければ、システムはこの第１の中間行き先より遠い別の中間行き先を決定するようにプログラムすることができる。次の中間行き先の選択は、上述した第１の地位間行き先の選択と同様にして進められる。このプロセスは、全経路の残りが決定されてしまうまで繰り返すことができる。より特定な実施例では、全経路の残りの決定が、プログラム可能なタイムアウト時間よりも長くかかる場合に限って、各中間経路が完全に決定され、対応する操作が利用者に伝えられる。
【００２３】図５は本発明の特定実施例の動作を記述する流れ図５００である。始めにシステムは、行き先までの経路を計算する目的で、利用者が入力した行き先を受信する（段階５０２）。次いでシステムは、ビークルの現在の位置から所望の行き先までの経路を決定し始め、同時に少なくとも１つの中間行き先を決定する（段階５０４）。次にシステムは、各中間行き先毎に費用値を決定する（段階５０６）。もしプログラム可能な時間が経過したにも拘わらず、始めの位置から最終行き先までの全経路の決定が完了していなければ（段階５０８）、システムは最低の費用値を有する中間行き先を最良中間行き先として選択し（段階５１０）、利用者にその中間経路を伝える（段階５１２）。次いでシステムは、その中間行き先から最終行き先までの経路を決定し続ける（段階５１４）。一方、もし全経路の決定が完了すれば、その全経路が利用者に伝えられる（段階５１６）。
【００２４】もし最終行き先までの経路の決定が未だに完了していなければ（段階５１８）、システムは第１の中間行き先と最終行き先との間の中間行き先の別の群を決定し（段階５２０）、また各中間行き先毎に費用値を決定する（段階５２２）。もし第２のプログラム可能な時間間隔が経過しても経路計算が完了していなければ（段階５２４）、システムは再び最低費用値を有する中間行き先を選択し（段階５２６）、次の中間経路を利用者に伝える（段階５２８）。上記段階５１８−５２８は、最終行き先までの残りの経路が決定されるまで繰り返すことができ、残りの経路が決定されるとそれは利用者に伝えられる（段階５３０）。
【００２５】図６は本発明の実施例による複数の中間経路の選択を記述する流れ図６００である。システムは、道路セグメントの１つから発し、ビークルの始めの位置に直接接続されている考え得る経路を、始めの位置の道路の階層レベルよりも高い階層レベルを有するある接続道路に出会うまで探索する（段階６０２）。次いでシステムは、その接続道路への入路点を、中間行き先として指定する（段階６０４）。段階６０２及び６０４は、始めの位置から発する各道路セグメント毎に繰り返される（段階６０６）。
【００２６】図７は本発明の特定実施例による複数の中間行き先の費用値の決定を記述する流れ図７００である。システムは、ビークルの始めの位置から発する中間経路の１つの道路セグメントのセグメント費用とノードのノード費用とを組合わせ、それの中間経路の経路費用を生成する（段階７０２）。次いでシステムは、その中間経路に関連する中間行き先に関する発見的費用を決定する（段階７０４）。この発見的費用は、その中間行き先と最終行き先との間の距離に対応する。次にシステムは、経路費用と発見的費用とを組合わせて中間行き先に関する費用値を生成する（段階７０６）。段階７０２−７０６を各中間行き先毎に繰り返す（段階７０８）。
【００２７】以上に本発明を特定実施例に関して図示し、説明したが、本発明は本竜命の思想及び範囲から逸脱することなくその形状及び細部に上述した、及び他の変更を考案できることを理解されたい。
【図面の簡単な説明】
【図１】本発明と共に使用するビークルナビゲーションシステムのブロック線図である。
【図２】ビークルナビゲーションシステムに使用される本発明の特定実施例により実行される経路計算方法を説明する図である。
【図３】本発明の特定実施例による中間行き先選択方法を説明する図である。
【図４】ハイウェイを何れの方向にも走行可能にする中間行き先の選択を説明する図である。
【図５】本発明の特定実施例の動作を示す流れ図である。
【図６】本発明の特定実施例による複数の中間経路の選択を示す流れ図である。
【図７】本発明の特定実施例による複数の中間行き先の費用値の決定を示す流れ図である。
【符号の説明】
１０ ビークルナビゲーションシステム
１２ 距離センサ
１４ 角速度センサ
１８ ＧＰＳ受信機
２０ 計算手段
２２ センサ／ＧＰＳインタフェース
２４ ＣＰＵ
２６ データベース媒体
２８ 主メモリ
３０ システムＲＡＭ
３２ 出力コントローラ
３４ 出力伝達装置
３６ ユーザインタフェース
４０ 表示コンソール
【０００１】
【発明の属する技術分野】本発明は、ビークルナビゲーションシステムによる経路の決定に関する。より詳しくは本発明は、全経路の決定が、与えられた時間よりも長くかかる場合に、利用者の最終行き先までの中間経路を決定する方法及び装置を提供する。このようにすると、最終行き先までの全経路が決定される前に利用者は走行を開始することが可能になる。
【０００２】
【従来の技術】本発明は以下に列挙する特許及び特許出願に関係がある。
【０００３】Kao の米国特許第 5,345,382号“ CALIBRAION METHOD FOR A RELATIVE HEADING SENSOR”、Sniderの米国特許第 5,359,529号“ ROUTE GUIDANCE ON/OFF-ROUTOE STATE FILTER”、1993年１月５日に同時出願された米国特許出願第 08/000,950 号“ POSITIONCORRECTION METHOD FOR VEHICLE NAVIGATION SYSTEM ”、1993年７月29日に出願された米国特許出願第 08/099,207 号“ METHOD FOR SELECTING A DESTINATION IN A VEHICLE NAVIGATION SYSTEM”、1994年６月20日に出願された米国特許出願第 08/263,604 号“ METHOD FOR IDENTIFYING HIGHWAY ACCESS RAMPS FOR ROUTE CALCULATION IN A VEHICLE NAVIGATION SYSTEM ”、1994年８月19日に出願された米国特許出願第 08/293,856 号“ VEHICLE NAVIGATION SYSTEM WITH UPGRADEABLE NAVIGATION SOFTWARE AND A FLEXIBLE MEMORYCONFIGURATION ”。
【０００４】
【発明が解決しようとする課題】利用可能な地図データベースのカバレッジ及び特徴が高密度になるにつれて、長距離経路の計算に要する時間も相応して増加する。経路が特に長いか、もしくは複雑な場合には、利用者が始めの位置から出発するまでに望ましくない遅れがもたらされる。もし経路が計算される前に利用者が出発を決断すれば、利用者はナビゲーションシステムからの指示を受けずに運転することになるので、最終的には計算される経路から逸脱する恐れがあるから、計算が無用なものになってしまう。もし全経路の計算が完了する前に最初の幾つかの指示または誘導を決定してそれを利用者に伝える方法があれば、長い経路の計算時間の上述した効果を軽減することができる。
【０００５】
【課題を解決するための手段】本発明は、始めの出発位置、即ち源位置と、最終行き先との間のある位置までの中間経路を決定できる方法を提供する。一般にビークルナビゲーションシステムの利用者が走行を開始するためには、最寄りのハイウェイに到達するのに十分な情報だけがあればよい。この目的のために、本発明は、フリーウェイ入路ランプのような中間行き先を選択し、その中間行き先に到達するのに必要な誘導を利用者に伝え、同時に最終行き先までの残余の経路を計算する。全経路の計算よりも遥かに少ない計算量である中間位置までの経路の決定には数秒しかかからず、従って利用者は全経路を知る前に運転を開始することができる。
【０００６】本発明によれば、ビークルナビゲーションシステムを使用して源位置から最終行き先までの経路を決定する方法及び装置が開示される。特定の実施例では、少なくとも１つの中間行き先がシステムの地図データベースから決定される。各中間行き先は、源位置からの対応する中間経路の一端にある。１より多い中間行き先が見出された場合には、各行き先毎に費用値を計算し、それに基づいて、考え得る中間行き先の中から最良中間行き先、即ち最低の費用値を有する中間行き先が選択される。次に、この最良中間行き先に対応する中間経路がビークルナビゲーションシステムの利用者に伝えられ、同時に最終行き先までの残余の経路が決定される。
【０００７】本発明の別の実施例では、地図データベース内の道路は階層的に編成されており、各道路はそれに関連する階層レベルを有している。源位置は第１の階層レベルの源道路に対応する。この実施例では、中間行き先は以下のようにして決定される。源位置に接続されている第１の道路セグメントからの考え得る経路が、第１の階層レベルよりも高い第２の階層レベルを有する接続道路に出会うまで探査される。次に、この接続道路への入路点が中間行き先として指定される。これは源位置から伸びる各道路セグメント毎に繰り返される。
【０００８】別の実施例では、各中間道路は少なくとも１つのノードと、少なくとも１つの道路セグメントとを含み、これらは地図データベース内に記憶されており、またこれらは源位置をその中間経路に対応する中間行き先に接続している。地図データベース内の各ノードは関連するノード費用を有しており、地図データベース内の各道路セグメントは関連するセグメント費用を有している。この実施例では、中間行き先に関する費用値は以下のようにして計算される。中間経路内の道路セグメントに関するセグメント費用及びノードに関するノード費用が組合わされ、それによって中間経路に関する経路費用が生成される。次いで、中間経路に関連する中間行き先に関する発見的費用が決定される。この発見的費用は、中間行き先と最終行き先との間の距離に対応する。次に、経路費用と発見的費用とが組合わされ、それによって中間行き先に関する費用値が生成される。この手順は、残余のどの中間行き先についても繰り返される。種々の実施例では、セグメント費用は、ある道路セグメントを走行するのに必要な時間の推定に対応し、ノード費用はあるノードを走行するのに必要な時間の推定に対応し、そして第１の距離は第１の中間行き先と最終行き先との間の実質的に直線距離に対応する。
【０００９】更に別の実施例では、本発明は、タイムアウト時間が経過するまで最良中間行き先を選択するのを待機する。このようにする理由は、もしタイムアウト時間が経過する前に最終行き先までの全経路が決定されれば、中間経路を伝えることは不要になり、その代わりに全経路を伝えればよいからである。特定の実施例においては、与えられたタイムアウト時間が経過するまでに最終行き先までの全経路の決定が完了しなければ、システムは第１の中間行き先と最終行き先との間に別の中間行き先を決定する。始めに、少なくとも１つの次の中間行き先を地図データベースから決定する。先行実施例と同様に、もし１より多くの次の中間行き先が見出されれば、各中間行き先毎に費用値が計算され、最低の費用値を有する次の中間行き先が次の最良中間行き先として選択される。次いで、次の最良中間行き先に対応する次の中間経路が利用者に伝えられる。このプロセスは、全経路の残りが決定されてしまうまで繰り返すことができる。特定実施例では、全経路の残りの決定がプログラム可能なタイムアウト時間よりも長い時間を要する場合に限って、各中間経路が完全に決定され、利用者に伝えられる。
【００１０】本発明の本質及び長所は、以下の明細書の部分及び添付図面から明白になるであろう。
【００１１】
【発明の実施の形態】図１は、本発明と共に使用するビークルナビゲーションシステム１０の実施例のブロック線図である。センサ１２及び１４、及びＧＰＳ受信機１８がセンサ／ＧＰＳインタフェース２２を通して計算手段２０に結合されている。典型的な実施例では、距離センサ１２はオドメータ（走行距離計）からなり、角速度センサ１４はジャイロスコープ、もしくはビークルの車輪に結合されている差動オドメータからなる。汎地球測位システム（ＧＰＳ）データ受信機１８は、例えば衛星をベースとするナビゲーションシステムからの信号を受信するために設けられている。センサ／ＧＰＳインタフェース２２からのデータはＣＰＵ２４へ伝えられ、ＣＰＵ２４は較正、信号処理、位置推測、ビークル位置決め、及び経路案内機能を遂行する。地図情報を含むデータベースはデータベース媒体２６内に記憶させることができ、主メモリ２８内に記憶されている計算手段２０の動作をＣＰＵ２４によって実行させるようにソフトウェアが指示する。メモリ２８は読み出し専用メモリ（ＲＯＭ）、もしくはフラッシュメモリまたはＳＲＡＭのような再プログラム可能な非揮発性メモリからなっていてよい。システムＲＡＭ３０は、これらのソフトウェアプログラムを実行するのに必要な情報を読み出したり、書き込むことができる。データベース媒体２６は、デジタル化された地図情報が記憶されている非揮発性メモリ、ハードディスクドライブ、ＣＤ−ＲＯＭ、もしくは集積回路からなることができる。グラフィックスコントローラからなることができる出力コントローラ３２は、ＣＰＵ２４が処理したデータを受信し、そのデータを表示コンソール４０へ伝送する。表示コンソール４０は、通常は表示画面を備えている出力伝達装置３４を含む。利用者は、典型的にはキーボードからなるユーザインタフェース３６を通して、所望の行き先のようなデータを入力することができる。データベース媒体２６内に記憶されている地図データベースは、道路の交差点即ちノード、道路セグメント、陸標、及び関心のある点、及び他の地理的な情報を記述するための（例えば緯度及び経度座標のような）位置データを含んでいることが好ましい。データベースは、道路及び場所名のような地図上の道路もしくは場所の特徴、分岐、一方通行制限、表面、速度制限、形状、高度、その他の特性のような道路の特色を表すデータをも含むことができる。本発明の一実施例によれば地図データベースは、個々のノード及び道路セグメントに関連した費用値を含む。これらの費用値は、それぞれのノード及び道路セグメントを走行するための時間の推定に対応している。ノード費用値は、例えばビークルが対向車線の大きい交通量に遭遇して左（右）折操作が遅れるか否かのような情報を考えている。セグメント費用は、そのセグメントに沿って走行する際の走行時間に影響を与える速度制限及びセグメント長のような道路セグメント特性を反映している。地図データベース内の各道路にはその道路のカテゴリもしくは型に関係する階層値も組合わされている。例えば、最高レベルの階層のカテゴリにはフリーウェイ及び高速道路が含まれる。最低レベルには住宅地街路及び／または細い小道が含まれる。
【００１２】図１のビークルナビゲーションシステムを使用して源位置Ａから最終行き先Ｂまでの経路の決定は、図２を参照すると理解し易い。本発明の一実施例では、ビークルナビゲーションシステム１０は２端法( two-ended ) 経路計算アルゴリズムを使用する。即ち、システム１０は、点Ａから発する通路「及び」点Ｂから後方へ戻る通路を探査する。始めに、探索パターンが点Ａ及びＢの両方から全方向に発せられる。図２は、点Ａから発する４本の道路セグメントの１つが、どのようにしてその後の経路探査のために選択されるかを示している。各道路セグメントｎは関連するセグメント費用ｇ(n) を有し、各ノードｋは関連するノード費用ｇ(k) 及び発見的費用及びｈ(k) を有している。各セグメント毎のセグメント費用は、その端点のノード費用及び発見的費用に加算され、各々毎に総合費用値が求められる。最低の総合費用値を有する道路セグメントが、さらなる計算のために選択される。図２において、点Ｄで終端する道路セグメントが一次的に選択される。それは、点Ｄに関連する発見的費用、即ち点ＤとＢとの間の距離が点Ｃ、Ｅ、及びＦに関連する発見的費用よりも少ないからである。このプロセスは点Ｄに関して、及び新たに計算された各経路点に関して繰り返される。考え得る新しい各経路点毎の発見的費用が、その考え得る経路点と、探索の他端において最後に決定された経路点との間の距離に基づいて計算されることに注目されたい。
【００１３】これは経路計算の進行に伴って探索領域を向け直して狭めることになるので、探索は点Ａと点Ｂとの間の領域に一層集中するようになる。発見的費用が０である点にシステムが到達すると、経路計算は完了する。本発明の一実施例では、ある道路セグメントが先行道路セグメントよりも高いカテゴリの経路内に含まれていることを何れかの端における探索アルゴリズムが識別すると、残余の経路決定プロセスにおいては低いカテゴリの道路セグメントは無視されることにも注目されたい。これは、殆どの論理的経路は一般的に、始まりにおいて道路カテゴリが増加し、終わりにおいて道路カテゴリが減少するという事実を反映している。例えば、典型的な経路は住宅地街路から始まって一般主要道路へ進み、そしてフリーウェイへ移る。利用者は最終行き先付近までフリーウェイを走行し続けることが多く、その点に到達するとフリーウェイから一般主要道路へ出て、住宅地街路へ達して終わる。
【００１４】特に高密度のデジタル化された地図データベースの場合には、上述した手順が高度に複雑になって決定に時間がかかるので、経路指示の伝達及び間もなく行われる運転操作に遅れがもたらされることは明白である。前述したように本発明は始めの源位置に近い中間行き先を選択し、中間位置までの経路を計算し、中間経路を伝え、そして同時に最終行き先までの経路の決定を継続することによって、これらの遅れを回避する。しかしながら、システムはこの機能を使用する時点をどのようにして知るのであろうか？ 一実施例においては、この機能は、始めの源位置と最終行き先との間の既知の関係、及びそれらの地理的な周囲状態（例えば両位置は、まばらにデジタル化された田園、もしくはハイウェイ領域によって分離された高密度にデジタル化された市街領域内にある）のようなパラメタに基づいて選択することができる。別の実施例では常に中間行き先が決定されるが、全経路の決定がプログラム可能なタイムアウト時間よりも長くかからなければ最良中間行き先は選択されず、その中間経路が利用者に伝えられることはない。この実施例の詳細に関しては後述する。中間行き先を選択する本発明の方法を、図３を参照して説明する。
【００１５】図３には、源位置である点Ａと、最終行き先である点Ｂとが示されている。一般的には、点Ａは静止したビークル出発位置を表す。しかしながら、もしビークルの移動中に経路計算が遂行されるのであれば、点Ａは現在のビークルの位置より前方の位置に選択することができる。このような状況では、源位置の決定に際して、ビークルの向き及び速度のようなパラメタを考慮することができる。点Ａから、４箇所の異なる中間行き先２０２、２０４、２０６及び２０８までの４本の考え得る中間経路２０１、２０３、２０５及び２０７が示されている。この例では、中間行き先はハイウェイ２１０及び２１２への入路点である。ハイウェイ入路点は、それらが容易に識別できること、及び上述した理由からハイウェイ入路点からの順方向経路計算が簡易になることから選択されることが多い。本質的に、源位置の道路よりも高いカテゴリにあるどのような道路との交差点も、考え得る中間行き先として選択することができる。
【００１６】更に図３を参照する。ナビゲーションシステムは、タイムアウト時間中に地図データベース内の点Ａから発する幾つかの考え得る通路を探査し、この探査の後に、その中間行き先について最良候補を選択する。タイムアウト時間は多重レベル時間間隔であることができる。即ち、この時間は、もし３もしくはそれ以上の候補が見出されれば 10 秒であるように、またもし１もしくは２候補しか見出されなければ 20 秒であるるようにプログラムすることができる。図は、ある中間行き先について４候補、即ちハイウェイ入路点２０２、２０４、２０６及び２０８が見出された状況を示している。一旦候補が選択されると、システムは、その行き先に達する経路のセグメント費用ｇ(n) 及びノード費用ｇ(k) の全てと、その行き先に関連する発見的費用、即ちｈ(dest)とを組合わせることによって、考え得る各中間行き先に関する総合費用ｆ(dest)を計算する。特定実施例では、この関係は次の数１ように表される。
【００１７】
【数１】
ｆ(dest)＝［Σroute ｇ(n) ＋ｇ(k) ］＋ｈ(dest)各中間経路の総合費用値を導出するために、これらの値を組合わせることが可能な、または費用値を割り当てることが可能な異なる方法が多数存在していることを理解されたい。本発明は、上述した特定実施例に限定されるものではない。
【００１８】中間行き先を選択する別の方法が本発明によって提供される。この実施例によれば、ハイウェイ及び源位置から 10 マイル以内にあるハイウェイ入路点のリストが利用者に提示される。利用者は、所望のハイウェイ及び／または特定の入路点を選択することができる。この機能は、例えばあるハイウェイへ乗る必要はあるが、現在の位置からそのハイウェイに乗るためには経路計算が必要であることを利用者が知っている場合に有用である。
【００１９】一旦中間行き先が選択され、中間経路が生成されると、システム表示を介して適切な運転操作が利用者に伝えられる。一般にこれらは一連の画面からなり、各画面は、例えば次の操作までの距離、もしくは次の操作の性質（例えば、左折）のような利用者が遂行すべき次の操作に関する情報を伝える。システムはこの情報を利用者に提供しながら、その中間行き先を出発点として使用して最終行き先までの残余の経路及び対応操作を決定する。このようにすると、全経路が決定される前に走行が可能になり、それによって利用者は殆ど直ちに走行を開始することができる。
【００２０】先に概要を説明したように本発明の特定実施例によれば、ビークルナビゲーションシステムは中間行き先を選択する前にタイムアウト時間の経過を待機するようにプログラムすることができる。もし最終行き先までの全経路がタイムアウト時間内に決定されれば、中間経路の伝達は不要と考えられ、中間行き先は選択されない。しかしながら、もし最終行き先までの全経路がタイムアウト時間が経過する前に完了しなければ、システムは中間行き先を選択して上述したように動作する。もし別のタイムアウト時間が経過しても未だ全経路の決定が完了しなければ、システムは第１の中間行き先より遠い別の中間行き先を決定するようにプログラムすることができる。次の中間行き先の選択も、上述した第１の中間行き先の選択と同様に進められる。全経路の残りが決定されてしまうまで、このプロセスを繰り返すことができる。代替として、システムは、もし最終行き先までの経路の計算が未だに完了しないことが決定されれば、直ちに次の中間行き先の決定を開始するようにプログラムすることが可能である。第１の中間行き先の場合と同様に、システムは、全経路の残りの決定が未だに完了しないか、もしくはプログラム可能なタイムアウト時間をより長く必要とする場合に限って、各連続中間経路を完全に決定し、対応する操作を利用者に伝えるようにプログラムすることができる。
【００２１】中間位置が近くて、全経路の決定が完了する前にビークルがその中間行き先に到達すればどのようになるか。もし中間位置がハイウェイ入路点であれば、そのハイウェイへ乗るように利用者に伝えられ、それに付け加えて、例えば「ハイウェイを走行し続けて下さい・残りの経路を計算中です」のような指令が発せられる。次に、ハイウェイをどの方向に走行するかを、システムはどのようにして知り、伝えるか。本発明の種々の実施例は以下のようにしてこの問題に対処している。一実施例によれば、最終行き先までのハイウェイ入路点からの方向に基づいて走行方向を推理する。別の実施例では、図４に示すように何れかの入路点３０２もしくは３０３より前に第１の中間行き先３０１を選択することによって、ハイウェイの方向が何れであるかを選択することができる。一方、第１の中間行き先より遠い別の中間行き先までの経路は、第１の中間行き先に到達するまでの時間によって知られる。
【００２２】第１の中間行き先に到達する上記の問題の別の解決法は、さらなる中間行き先を決定することである。本発明のこの実施例では、もしビークルが中間行き先に到達する時点までに全経路の決定が未だに完了していなければ、システムはこの第１の中間行き先より遠い別の中間行き先を決定するようにプログラムすることができる。次の中間行き先の選択は、上述した第１の地位間行き先の選択と同様にして進められる。このプロセスは、全経路の残りが決定されてしまうまで繰り返すことができる。より特定な実施例では、全経路の残りの決定が、プログラム可能なタイムアウト時間よりも長くかかる場合に限って、各中間経路が完全に決定され、対応する操作が利用者に伝えられる。
【００２３】図５は本発明の特定実施例の動作を記述する流れ図５００である。始めにシステムは、行き先までの経路を計算する目的で、利用者が入力した行き先を受信する（段階５０２）。次いでシステムは、ビークルの現在の位置から所望の行き先までの経路を決定し始め、同時に少なくとも１つの中間行き先を決定する（段階５０４）。次にシステムは、各中間行き先毎に費用値を決定する（段階５０６）。もしプログラム可能な時間が経過したにも拘わらず、始めの位置から最終行き先までの全経路の決定が完了していなければ（段階５０８）、システムは最低の費用値を有する中間行き先を最良中間行き先として選択し（段階５１０）、利用者にその中間経路を伝える（段階５１２）。次いでシステムは、その中間行き先から最終行き先までの経路を決定し続ける（段階５１４）。一方、もし全経路の決定が完了すれば、その全経路が利用者に伝えられる（段階５１６）。
【００２４】もし最終行き先までの経路の決定が未だに完了していなければ（段階５１８）、システムは第１の中間行き先と最終行き先との間の中間行き先の別の群を決定し（段階５２０）、また各中間行き先毎に費用値を決定する（段階５２２）。もし第２のプログラム可能な時間間隔が経過しても経路計算が完了していなければ（段階５２４）、システムは再び最低費用値を有する中間行き先を選択し（段階５２６）、次の中間経路を利用者に伝える（段階５２８）。上記段階５１８−５２８は、最終行き先までの残りの経路が決定されるまで繰り返すことができ、残りの経路が決定されるとそれは利用者に伝えられる（段階５３０）。
【００２５】図６は本発明の実施例による複数の中間経路の選択を記述する流れ図６００である。システムは、道路セグメントの１つから発し、ビークルの始めの位置に直接接続されている考え得る経路を、始めの位置の道路の階層レベルよりも高い階層レベルを有するある接続道路に出会うまで探索する（段階６０２）。次いでシステムは、その接続道路への入路点を、中間行き先として指定する（段階６０４）。段階６０２及び６０４は、始めの位置から発する各道路セグメント毎に繰り返される（段階６０６）。
【００２６】図７は本発明の特定実施例による複数の中間行き先の費用値の決定を記述する流れ図７００である。システムは、ビークルの始めの位置から発する中間経路の１つの道路セグメントのセグメント費用とノードのノード費用とを組合わせ、それの中間経路の経路費用を生成する（段階７０２）。次いでシステムは、その中間経路に関連する中間行き先に関する発見的費用を決定する（段階７０４）。この発見的費用は、その中間行き先と最終行き先との間の距離に対応する。次にシステムは、経路費用と発見的費用とを組合わせて中間行き先に関する費用値を生成する（段階７０６）。段階７０２−７０６を各中間行き先毎に繰り返す（段階７０８）。
【００２７】以上に本発明を特定実施例に関して図示し、説明したが、本発明は本竜命の思想及び範囲から逸脱することなくその形状及び細部に上述した、及び他の変更を考案できることを理解されたい。
【図面の簡単な説明】
【図１】本発明と共に使用するビークルナビゲーションシステムのブロック線図である。
【図２】ビークルナビゲーションシステムに使用される本発明の特定実施例により実行される経路計算方法を説明する図である。
【図３】本発明の特定実施例による中間行き先選択方法を説明する図である。
【図４】ハイウェイを何れの方向にも走行可能にする中間行き先の選択を説明する図である。
【図５】本発明の特定実施例の動作を示す流れ図である。
【図６】本発明の特定実施例による複数の中間経路の選択を示す流れ図である。
【図７】本発明の特定実施例による複数の中間行き先の費用値の決定を示す流れ図である。
【符号の説明】
１０ ビークルナビゲーションシステム
１２ 距離センサ
１４ 角速度センサ
１８ ＧＰＳ受信機
２０ 計算手段
２２ センサ／ＧＰＳインタフェース
２４ ＣＰＵ
２６ データベース媒体
２８ 主メモリ
３０ システムＲＡＭ
３２ 出力コントローラ
３４ 出力伝達装置
３６ ユーザインタフェース
４０ 表示コンソール
【特許請求の範囲】
【請求項１】 地図データベースを有するビークルナビゲーションシステムを使用して源位置から最終行き先までの経路を決定する方法において、上記源位置からの対応する中間経路の一端にある最良中間行き先を地図データベースから選択する段階と、上記最良中間行き先に対応する中間経路をビークルナビゲーションシステムの利用者に伝える段階と、最終行き先までの残余の経路を決定する段階とを備えていることを特徴とする方法。
【請求項２】 上記最良中間行き先を選択する段階は、各々が上記源位置からの中間経路の一端にある中間行き先の中から、少なくとも１つの中間行き先を地図データベースから決定する段階と、各中間行き先毎に費用値を計算する段階と、他の如何なる中間行き先に対応する費用値よりも低い費用値に対応する最良中間行き先を選択する段階とを備えている請求項１に記載の方法。
【請求項３】 上記地図データベースはその中に記憶されている複数の道路からなり、各道路はそれに関連する階層レベルを有し、ある源道路に対応する上記源位置は第１の階層レベルを有しており、上記少なくとも１つの中間行き先を決定する段階は、上記源位置に接続されている第１の道路セグメントからの考え得る経路を、上記第１の階層レベルより高い第２の階層レベルを有し且つ関連入路を有する接続道路に出会うまで探索する段階と、上記接続道路への入路を中間行き先として指定する段階と、上記源位置に接続されている各道路セグメント毎に上記探索及び指定段階を繰り返す段階とを備えている請求項２に記載の方法。
【請求項４】 上記各中間経路は、上記源位置と上記中間経路に対応する上記中間行き先とを接続する上記地図データベース内の少なくとも１つのノード及び少なくとも１つの道路セグメントからなり、上記各ノードはそれに関連するノード費用を有し、上記各道路セグメントはそれに関連するセグメント費用を有し、上記各中間行き先毎に費用値を計算する段階は、（Ａ）第１の中間経路内の道路セグメントのセグメント費用とノードのノード費用とを組合わせて経路費用を生成する段階と、（Ｂ）上記第１の中間経路に関連する第１の中間行き先に関して、上記第１の中間行き先と上記最終行き先との間の第１の距離に対応する発見的費用を決定する段階と、（Ｃ）上記第１の中間経路の経路費用と上記第１の中間行き先の発見的費用とを組合わせて上記第１の中間行き先に関する第１の費用値を生成する段階と、（Ｄ）上記段階（Ａ）−（Ｃ）を、残余のどの中間行き先についても繰り返す段階とを備えている請求項２に記載の方法。
【請求項５】 上記各道路セグメントに関連する上記セグメント費用は、上記道路セグメントを走行するのに要する時間の推定に対応している請求項４に記載の方法。
【請求項６】 上記各ノードに関連する上記ノード費用は、上記ノードを走行するのに要する時間の推定に対応する請求項４に記載の方法。
【請求項７】 上記第１の距離は、上記第１の中間行き先と上記最終行き先との間の実質的に直線距離に対応している請求項４に記載の方法。
【請求項８】 上記最良中間行き先を選択して中間経路を伝える段階は、上記残余の経路を決定する段階がタイムアウト時間より長い時間を必要とする場合に限って遂行される請求項１に記載の方法。
【請求項９】 （Ａ）先に決定された中間行き先からの対応する次の中間経路の一端にある次の最良中間行き先を上記地図データベースから選択する段階と、（Ｂ）上記次の最良中間行き先に対応する次の中間経路をビークルナビゲーションシステムの利用者に伝える段階と、（Ｃ）上記段階（Ａ）−（Ｃ）を、残余の中間経路が決定されてしまうまで繰り返す段階とを備えている請求項１に記載の方法。
【請求項１０】 上記次の最良中間行き先を選択する段階は、各々が先に決定された中間行き先からの次の中間経路の一端にある次の中間行き先の中から、少なくとも１つの次の中間行き先を決定する段階と、各次の中間行き先に関して費用値を計算する段階と、他のどの次の中間行き先に対応する費用値よりも低い費用値に対応する次の最良中間行き先を選択する段階とを備えている請求項９に記載の方法。
【請求項１１】 上記次の最良中間行き先を選択して次の中間経路を伝える段階は、上記残余の経路を決定する段階がタイムアウト時間より長い時間を必要とする場合に限って遂行される請求項９に記載の方法。
【請求項１２】 上記地図データベースはその中に記憶されている複数の道路からなり、各道路はそれに関連する階層レベルを有し、ある源道路に対応する上記源位置は第１の階層レベルを有しており、上記最良中間行き先を選択する段階は、上記源位置に接続されている道路セグメントからの考え得る経路を、上記第１の階層レベルより高い第２の階層レベルを有し且つ関連入路を有する接続道路に出会うまで探索する段階と、上記接続道路への入路を最良中間行き先として指定する段階とを備えている請求項１に記載の方法。
【請求項１】 地図データベースを有するビークルナビゲーションシステムを使用して源位置から最終行き先までの経路を決定する方法において、上記源位置からの対応する中間経路の一端にある最良中間行き先を地図データベースから選択する段階と、上記最良中間行き先に対応する中間経路をビークルナビゲーションシステムの利用者に伝える段階と、最終行き先までの残余の経路を決定する段階とを備えていることを特徴とする方法。
【請求項２】 上記最良中間行き先を選択する段階は、各々が上記源位置からの中間経路の一端にある中間行き先の中から、少なくとも１つの中間行き先を地図データベースから決定する段階と、各中間行き先毎に費用値を計算する段階と、他の如何なる中間行き先に対応する費用値よりも低い費用値に対応する最良中間行き先を選択する段階とを備えている請求項１に記載の方法。
【請求項３】 上記地図データベースはその中に記憶されている複数の道路からなり、各道路はそれに関連する階層レベルを有し、ある源道路に対応する上記源位置は第１の階層レベルを有しており、上記少なくとも１つの中間行き先を決定する段階は、上記源位置に接続されている第１の道路セグメントからの考え得る経路を、上記第１の階層レベルより高い第２の階層レベルを有し且つ関連入路を有する接続道路に出会うまで探索する段階と、上記接続道路への入路を中間行き先として指定する段階と、上記源位置に接続されている各道路セグメント毎に上記探索及び指定段階を繰り返す段階とを備えている請求項２に記載の方法。
【請求項４】 上記各中間経路は、上記源位置と上記中間経路に対応する上記中間行き先とを接続する上記地図データベース内の少なくとも１つのノード及び少なくとも１つの道路セグメントからなり、上記各ノードはそれに関連するノード費用を有し、上記各道路セグメントはそれに関連するセグメント費用を有し、上記各中間行き先毎に費用値を計算する段階は、（Ａ）第１の中間経路内の道路セグメントのセグメント費用とノードのノード費用とを組合わせて経路費用を生成する段階と、（Ｂ）上記第１の中間経路に関連する第１の中間行き先に関して、上記第１の中間行き先と上記最終行き先との間の第１の距離に対応する発見的費用を決定する段階と、（Ｃ）上記第１の中間経路の経路費用と上記第１の中間行き先の発見的費用とを組合わせて上記第１の中間行き先に関する第１の費用値を生成する段階と、（Ｄ）上記段階（Ａ）−（Ｃ）を、残余のどの中間行き先についても繰り返す段階とを備えている請求項２に記載の方法。
【請求項５】 上記各道路セグメントに関連する上記セグメント費用は、上記道路セグメントを走行するのに要する時間の推定に対応している請求項４に記載の方法。
【請求項６】 上記各ノードに関連する上記ノード費用は、上記ノードを走行するのに要する時間の推定に対応する請求項４に記載の方法。
【請求項７】 上記第１の距離は、上記第１の中間行き先と上記最終行き先との間の実質的に直線距離に対応している請求項４に記載の方法。
【請求項８】 上記最良中間行き先を選択して中間経路を伝える段階は、上記残余の経路を決定する段階がタイムアウト時間より長い時間を必要とする場合に限って遂行される請求項１に記載の方法。
【請求項９】 （Ａ）先に決定された中間行き先からの対応する次の中間経路の一端にある次の最良中間行き先を上記地図データベースから選択する段階と、（Ｂ）上記次の最良中間行き先に対応する次の中間経路をビークルナビゲーションシステムの利用者に伝える段階と、（Ｃ）上記段階（Ａ）−（Ｃ）を、残余の中間経路が決定されてしまうまで繰り返す段階とを備えている請求項１に記載の方法。
【請求項１０】 上記次の最良中間行き先を選択する段階は、各々が先に決定された中間行き先からの次の中間経路の一端にある次の中間行き先の中から、少なくとも１つの次の中間行き先を決定する段階と、各次の中間行き先に関して費用値を計算する段階と、他のどの次の中間行き先に対応する費用値よりも低い費用値に対応する次の最良中間行き先を選択する段階とを備えている請求項９に記載の方法。
【請求項１１】 上記次の最良中間行き先を選択して次の中間経路を伝える段階は、上記残余の経路を決定する段階がタイムアウト時間より長い時間を必要とする場合に限って遂行される請求項９に記載の方法。
【請求項１２】 上記地図データベースはその中に記憶されている複数の道路からなり、各道路はそれに関連する階層レベルを有し、ある源道路に対応する上記源位置は第１の階層レベルを有しており、上記最良中間行き先を選択する段階は、上記源位置に接続されている道路セグメントからの考え得る経路を、上記第１の階層レベルより高い第２の階層レベルを有し且つ関連入路を有する接続道路に出会うまで探索する段階と、上記接続道路への入路を最良中間行き先として指定する段階とを備えている請求項１に記載の方法。
【図１】
【図２】
【図４】
【図３】
【図６】
【図５】
【図７】
【図２】
【図４】
【図３】
【図６】
【図５】
【図７】
【公開番号】特開平８−２６１７８３
【公開日】平成８年（１９９６）１０月１１日
【国際特許分類】
【出願番号】特願平８−１９５０５
【出願日】平成８年（１９９６）２月６日
【出願人】（０００００３３３３）株式会社ゼクセル (510)
【公開日】平成８年（１９９６）１０月１１日
【国際特許分類】
【出願日】平成８年（１９９６）２月６日
【出願人】（０００００３３３３）株式会社ゼクセル (510)
[ Back to top ]