近道発見装置
【課題】電子地図のデータベースに近道を自動的に追加することができ、その追加される近道が使用可能で且つ効率的な近道であるようにするシステム。
【解決手段】電子地図(20)は、ノード及びリンクの集合として記憶される。地図の道路には、経路探索の目的で優先順位が指定される。ノードの優先順位は、最初、ノードに関連した道路の優先順位に対応する。電子地図は、地図(20)に近道を追加することによって使用可能度を増すことができる。近道発生装置(22)は、複合リンクを構築し及び／又はあるノードの優先順位を高めることにより近道を形成する。複合リンクとは、電子地図(20)の多数のリンクに沿った移動を表すリンクである。
【解決手段】電子地図(20)は、ノード及びリンクの集合として記憶される。地図の道路には、経路探索の目的で優先順位が指定される。ノードの優先順位は、最初、ノードに関連した道路の優先順位に対応する。電子地図は、地図(20)に近道を追加することによって使用可能度を増すことができる。近道発生装置(22)は、複合リンクを構築し及び／又はあるノードの優先順位を高めることにより近道を形成する。複合リンクとは、電子地図(20)の多数のリンクに沿った移動を表すリンクである。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子地図から近道を発見する近道発見装置に係る。
【背景技術】
【０００２】
コンピュータは、地図の考え方を、位置を静的に示す画像から、物理的、社会的又は経済的システムを定量化する地理的に参照される電子データより成る電子地図へと根本的に変えた。電子地図に含まれる情報の範囲は、無限である。例えば、道路の電子地図は、要素間の距離、移動時間、区画番号、税金情報、通行者情報、処理時間、待機時間等を含むことができる。更に、地図を１つ以上のインテリジェントデータファイルとしてコンピュータに記憶することにより、そのデータを如何なるソフトウェアプリケーションが操作することも許されるようになる。
【０００３】
電子地図の１つの利点は、地図の種々の部分に関連したコストを記憶し、決定しそして利用できることである。コストは、最小又は最大にすることのできる変数である。コストとは、例えば、時間、距離、支払う通行料金、転換の容易さ、景色の良さ等を含む。通常、コストは、整数として表わされる。時々、コストは、実数値として表わすこともできる。コストに関する付加的な情報は、参考としてここに取り上げる１９９６年１１月２５日出願の「経路発見計算のために複数のコストレベルの使用(Using Multiple Levels Of Costs For A Pathfinding Computation)」と題する米国特許出願第０８／７５６，２６３号に見ることができる。
【０００４】
電子地図は、出発点と行き先との間のルートを計算する方法である経路発見に使用することができる。あるシステムは、推奨ルートを計算し、そして地図表示上にその推奨ルートをハイライト処理するか、又は曲がるたびに方向を指示する（紙、表示又は音声で）か、或いはその両方によって運転者を誘導する。経路発見システムが行き先への推奨ルートを計算するときには、ある特定の基準に基づいて最も望ましいルートを発見することによりそれを行う。これらの基準は、運転者によって指定されてもよいし、又は製造時に初期値として設定されてもよい。多くの場合に、システムは、あるコスト、例えば、運転時間を最小にする経路を発見するように使用される。
【０００５】
経路発見に使用される電子地図は、道路網の接続に関する情報、即ち道路の断片が互いに接続するか又は接続しない態様に関する情報、例えば、通常の交差点があるか、高架道路があるか、転換が制限されているか等々の情報を保持しなければならない。非常に広い範囲では、これが膨大な情報となる。電子地図は、数十又は数百メガバイトのデータを含む。このような膨大な量のデータを経済的に保持すると共に、ユーザが更新されたコピーと容易に交換できるようにするために、現在の多数の経路発見装置（経路探査ソフトウェアを伴う汎用コンピュータ、自動車用ナビゲーションシステム又は他の地図アプリケーション装置を含む）は、ＣＤ−ＲＯＭを使用して電子地図データを記憶している。
【０００６】
経路発見プロセスは多量のデータを分類しなければならないので、プロセスが低速となる。経路発見プロセスをスピードアップする１つの手段は、優先順位レベルを使用することである。優先順位レベルを使用すると、人間が経路発見プロセスを実行するのと同様のやり方で経路発見プロセスが経路を見つけることができ、最終的な経路は、人間が決定した経路と同様になる。経路を、人間が決定する経路と同様にすることで、経路は、より理解し易く且つユーザに馴染み易いものとなる。
【０００７】
紙の地図上で経路を手動で見つけるときには、ユーザは、通常、出発点と行き先を識別する。ユーザは、居住地道路を経て集合又は幹線道路のような主要道路へ進むように航行する。次いで、ユーザは、主要道路を経てハイウェイを見つけるように航行する。行き先に最も近いハイウェイ出口が見つかるまで、ハイウェイ上で経路を決定し続ける。ハイウェイ出口が見つかると、ユーザは、主要道路を経て行き先のできるだけ近くまで航行する。最終的に、ユーザは、主要道路上のその最至近点から、居住地道路を用いて行き先へ至る経路を見つける。従って、ユーザは、本来的に、優先順位レベルを使用している。即ち、１つの優先順位レベルは、居住地道路であり、第２の優先順位レベルは、主要道路であり、そして第３の優先順位レベルは、ハイウェイである。経路発見プロセス中の第１の地域において、ユーザは、居住地道路を経て航行する。第２の地域において、ユーザは、主要道路及び／又はハイウェイのみを経て航行する。第３の地域において、ユーザは、ハイウェイのみを経て航行し、等々となる。このプロセスは、非常に効率的である。というのは、ユーザが常に全ての道路を経て探す場合に、考慮すべきデータが著しく多数あり、経路が最も効率的な経路となり難いからである。
【０００８】
使用可能な経路を効率的に見つけるために、本願発明も、優先順位レベルを使用する。種々の経路発見システムは、異なる道路種別を異なるレベルに分割する。システムが３つのレベルを使用するか、４つのレベルを使用するか、５つのレベルを使用するか、６つのレベルを使用するか等は、ここでの説明にとって必ずしも重要ではない。テーブル１は、道路を６つの優先順位レベルに分割するシステムの一例を示す。
テーブル１
道路の種別 道路の種別に従う優先順位レベル
路地 ０
居住地道路 １
集合道路 ２
幹線道路 ３
重要度の低いハイウェイ ４
重要なハイウェイ ５
このように、道路の種別に従って、時間的により高いコスト（換言すると、単位距離移動するのにより長い時間）をもたらす道路の種別に対して、より低い優先順位レベルが付けられる。道路の種別と最高制限速度とが関連していることは一般に知られていることである。
【０００９】
明らかなように、テーブル１は、異なる道路を６つの道路種別、即ち路地、居住地道路、集合道路、幹線道路、重要度の低いハイウェイ及び重要なハイウェイに分割している。各道路の種別には優先順位レベルが指定される。１つの経路発見システムでは、システムが出発点から行き先への経路を決定するときに、システムは、優先順位レベル１及びそれより高い道路を探査し、出発点及び行き先から同時に経路探査を実行することにより処理を開始する。
本願発明では、この道路の種別に係る優先順位レベルを、道路の分岐点を意味するノード間の１方向の経路を意味するリンクのリンク優先順位レベルの初期値として使用する。
この経路探索は、促進基準が満足するまで続けられる。促進基準は、３組の基準を含む。第１基準は、促進閾値である。この促進閾値は、コストである。起点から現在考慮中の隣接ノードへ（又はノードから行先へ）移動するコストがこの促進閾値より高いときに、促進閾値が満足される。第２基準は、探査中に、低い優先順位（又はそれより高い）にあるノードの最小数に到達しなければならないことである。第３基準は、探査中に、高いリンク優先順位レベル（又はそれより高い）のリンクのノード数が最小数に到達しなければならないことである。例えば、リンク優先順位レベル１からレベル２へ促進するときには、リンク優先順位レベル１が低い優先順位であり、そしてリンク優先順位レベル２が高いリンク優先順位である。３つの基準全部が満足されたときに、促進基準が満足される。
【００１０】
１組の促進閾値の一例がテーブル２に示されている。例えば、最初の行は、レベル０（及びそれ以上）からレベル１（及びそれ以上）へ探査を促進するための促進閾値を表わすコスト（ミリ秒）を表わしている。
テーブル２
促進のための 促進閾値
リンク優先順位レベル （コスト、ミリ秒）
０ ０
０から１ 10,000
１から２ 10,000
２から３ 120,000
３から４ 300,000
４から５ 600,000
第２及び第３の促進基準に対する１組の値は、テーブル３に例示する。
【００１１】
テーブル３
低優先順位 高優先順位
促進のための （又はそれより高い） （又はそれより高い）
リンク優先順位レベル ノードの最小数 ノードの最小数
０から１ ２０ １
１から２ ２０ ２０
２から３ ３０ ３０
３から４ ４０ ４０
４から５ ５０ ２５
【００１２】
優先順位レベル１以上における探査のための促進基準を満足した後に、システムは、優先順位レベル２以上の道路のみを考慮することにより第２促進基準を満足するまで経路探索プロセスを継続する。この第２促進基準に到達した後に、システムは、電子地図を探査し続けるが、第３促進基準に到達するまでリンク優先順位レベル３以上の道路しか考慮しない。第３促進基準を満足した後、システムは、第４促進基準に到達するまでリンク優先順位レベル４以上の道路のみを考慮して電子地図を通して探査し続ける。この第４促進基準を満足した後、システムは、リンク優先順位レベル５の道路のみを考慮して電子地図を探査し続ける。
【００１３】
上述したリンク優先順位レベルを使用する幾つかの従来の経路発見システムに対してなされる１つの改善は、近道を含ませることであり、これは、経路発見プロセスをスピードアップし、良好な経路を形成する上で助けとなり、そして人間が紙の地図を使用して形成する経路により近い経路を形成する上で助けとなる。電子地図に近道を使用する幾つかの公知システムは、人間が電子地図のデータベースに手で近道を追加するものである。このプロセスは、低速で、冗長で且つ効率の悪いものである。
【００１４】
他の従来のシステムは、コンピュータを使用して近道を自動的に発生する。しかしながら、これらシステムは、コンピュータにより発生される近道が顧客にとって使用可能でない経路を含む傾向があるために問題となっている。即ち、特定の方法の要求を満足する適切な近道が発生されるが、その発生された近道より更に使用可能な近道又は経路が存在する。多くのユーザは、非常に短い時間内に最短の経路を決定できることをシステムに望むために経路発見システムにアクセスする。ユーザは、ユーザに馴染みのある近所にいて、経路発見システムのユーザが知っている近道より距離の長い近道をシステムが決定したときに、システムの性能に失望する。
【発明の概要】
【発明が解決しようとする課題】
【００１５】
それ故、電子地図のデータベースに近道を自動的に追加することができ、その追加される近道が使用可能で且つ効率的な近道であるようにするシステムが要望される。
【課題を解決するための手段】
【００１６】
本発明は、電子地図データベースから近道を発見することのできる近道発見装置を提供する。ここに開示する近道発生装置は、電子地図データベースにおいて、或るノード優先順位レベルを高めることにより近道を発見することができる。ここで、ノード優先順位レベルとは、ノードに接続される複数のリンクのリンク優先順位レベルの内で最大の優先順位レベルである。
【００１７】
本発明において、各リンクは、このリンクの道路の種別に応じたリンク優先順位レベルを有する。本発明は、出発点ノードから探査を開始する。この探査段階は、どのノードが使用可能でないか決定することを含む。探査中に探査されそして使用可能でないと決定されたノードで終端しないリンクのリンク優先順位レベルがより高いリンク優先順位レベルに切り替えられる。より高いリンク優先順位レベルに切り替えられるリンクが複数のリンクからなる複合リンクであってよい。
【００１８】
１つの実施形態において、本発明は、ノードに対するノード優先順位レベルを電子地図に記憶することを含む。新たなリンク優先順位レベルを有する１つ以上のリンクにより接続されたノードに対して新たなノード優先順位レベルが形成される。新たなノード優先順位レベルは、電子地図に記憶される。
【００１９】
１つの別の形態において、システムは、探査中に通過したＵターンを含む経路に対して１つ以上のＵターン指示を記憶する段階も含む。この実施形態では、新たなリンク優先順位レベルを付与する段階は、記憶されたＵターン指示に関連したリンク又は経路を考慮しない。
【００２０】
複合リンク及び新たなノード優先順位レベルを記憶するときには、新たなデータを既存の電子地図ファイルに記憶することができる。或いは又、新たなノード優先順位レベル及び複合リンクそして元のマップファイルからの適当なオリジナルデータを含む新たなファイルを発生することもできる
【００２１】
本発明は、ソフトウェア、ハードウェア或いはソフトウェアとハードウェアの組合せを用いて実施することができる。本発明の一部分又は全部をソフトウェアで実施する場合には、そのソフトウェアは、プロセッサ読み取り可能な記憶媒体に存在し得る。適当なプロセッサ読み取り可能な記憶媒体は、例えば、フロッピー（登録商標）ディスク、ハードディスク、ＣＤ ＲＯＭ、メモリＩＣ等を含む。システムがハードウェアを含むときには、ハードウェアは、出力装置（例えば、モニタ、スピーカ又はプリンタ）と、入力装置（例えば、キーボード、ポインティングデバイス及び／又はマイクロフォン）と、出力装置と通信するプロセッサと、プロセッサと通信するプロセッサ読み取り可能な記憶媒体とを含む。プロセッサ読み取り可能な記憶媒体は、本発明を実施する段階を実行するようにプロセッサをプログラミングすることのできるコードを記憶する。本発明のプロセスは、インターネットのウェブページにおいて実施することもできるし、又は電話線を経てアクセスできるサーバーにおいて実施することもできる。
【００２２】
以下に述べる動作段階の多くは、公知の近道発生装置に見られるものである。しかしながら、公知の近道発生装置は、以下に述べるように、ノード使用可能度を利用する手段を含んでいない。ここで、ノード使用可能度とは、複数ある前進リンクの内の最大のリンク使用可能度に変更されるパラメータであり、リンク使用可能度とは、リンクのコストの逆数と該リンク終端部のノード使用可能度との和である。
【００２３】
本発明のこれら及び他の目的並びに効果は、添付図面を参照した本発明の好ましい実施形態の以下の説明から明らかとなろう。
【図面の簡単な説明】
【００２４】
【図１】本発明の近道発生装置がどのように使用されるかを示すブロックダイヤグラム。
【図２】近道発生装置の出力がどのように使用されるかを示すブロックダイヤグラム。
【図３】電子地図の一部を表す有向グラフの例。
【図４】電子地図の一部を表す有向グラフの例。
【図５】電子地図の一部を表す有向グラフの例。
【図６】電子地図あるいは他のグラフにおける経路を発見するための例示的な方法を記載したフローチャート。
【図７】近道発生装置の動作を記述したフローチャート。
【図８Ａ】図７の（現在の探査レベルでの動作）ステップ３５０を実行するための方法を記述したフローチャート。
【図８Ｂ】図７の（現在の探査レベルでの動作）ステップ３５０を実行するための方法を記述したフローチャート。
【図９】図８Ａの（採択ノードから探査）ステップ４０６を実行する方法を記述したフローチャート。
【図１０】図９の（使用可能度チェック）ステップ５１４を実行する方法を記述したフローチャート。
【図１１】図８Ａの（後戻り）ステップ４１６を実行する方法を記述したフローチャート。
【図１２Ａ】図８Ｂの（各採択されたノードの実際のノード優先順位レベルを決定する）ステップ４２０を実行する方法を記述したフローチャート。
【図１２Ｂ】図１２Ａを説明する手助けするのに使用する、４つの前進リンクを有するノードを描写したもの。
【図１２Ｃ】図１２Ａを説明する手助けするのに使用する、３つの前進リンクを有するノードを描写したもの。
【図１３】近道発生装置および／又は経路発見システムを実行するために１つの例示的なハードウェアシステムのブロックダイヤグラムである。
【発明を実施するための形態】
【００２５】
図１は、本発明の近道発生器の使用方法を示すブロック図である。図１は、入力を受けて出力を出す近道発生器２２を示している。入力は、元の地図データ２０を含み、出力は、増補地図データ２４を含む。元の地図データ２０は、地図データベースを形成する１つまたはそれ以上のファイルの集成である。地図データベースの詳細については後述する。元の地図データベース２０は、モデム、電子メール、ファイル転送、ポインタ、ファンクションコール等を介して近道発生器２２によって受信されうる。元の地図データ２０は、プロセッサ読み取り可能な記憶媒体に記憶される。近道発生器２２は、元の地図データ地図２０を受け取り、後述するように、近道を加えて、増補地図データ２４を生成する。増補地図データ２４の生成は、新しい地図データ（すなわち、近道）を既存の元の地図データファイル２０に加えることを含みうる。別の仕方として、増補地図データ２４の生成は、近道発生器２２によって生成された新しいデータおよび元の地図データ２０からの古いデータのいくつかまたは全てを含む新しいファイルを生成することを含みうる。この結果として生ずる増補地図データ２４は、近道発生器２２によって生成される近道を含む１つまたはそれ以上のファイルに記憶される電子地図である。
【００２６】
図２に示されるように、増補地図データ２４は、経路発見システム３０への入力として使用されうる。オペレーション中、経路発見システム３０は、プロセッサ読み取り可能な記憶媒体に増補地図データ２４を記憶する。経路発見システム３０のユーザは、出発点および行き先を指定し、これらは経路発見システム３０によってプロセッサ読み取り可能な記憶媒体に記憶される。経路発見システム３０は、増補地図データ２４を使用して指定された出発点から指定された行き先までの経路を見つけ出しうる。経路発見システム３０の出力は、経路３２である。経路３２は、プロセッサ読み取り可能な記憶媒体に記憶され、経路発見システムのユーザへ報告される。
【００２７】
近道発生器２２がどのようにして増補地図データ２４を生成するかについて説明する前に、電子地図の基本的な説明をする。一般的に、経路発見のために使用される電子地図は、グラフを含む。グラフは、ノードおよびリンクの集成である。ノードは、グラフ上で分岐点を意味する印である。例えば、ノードが十字路交差点の場合は、右折、左折、または直進するかの選択を行うべき場所を示す。リンクは、２つのノードの間の接続である。グラフにおけるノードＡからノードＢまでの経路は、ノードのリストに、このリスト中の各ノードから次のノードまでのリンクが存在する如くに記述されている。グラフにおいて、各リンクはそれに関連した単一の方向を有する。ノードの所定の対の間には、各方向において１つずつ、２つのリンクがありうる。
【００２８】
図３のグラフは、プロセッサ読取り可能記憶媒体に記憶された電子地図データ構造を象徴的に理解するのに使用される。即ち、プロセッサ読取り可能記憶媒体は、前述のグラフの画像を実際には記憶しない。そうではなく、データ構造が記憶される。各ノードに付いて、データ構造は、ノードの位置（例えば、緯度と経度）と、隣接するノード（1つのリンク経由で行けるノード）のリストと、隣接するノードへ行くのに関連する色々のコストとを記憶する。本発明は、記述したのとは異なる多くの好適なデータ構造とともに使用することができる。更に、本発明は、グラフと共に使用する必要はない。本発明は、地図データベース全体、他のネットワーク、又は他の任意の好適な情報のサブセットと共に使用することができる。更に、データ構造の1つ又はそれ以上のエントリは、データのクラスタにグループ分けすることができる。データのクラスタは、関連データのグループ分けである。クラスタは性能を改善するが、本発明はクラスタなしでも使用することができる。クラスタに関するより多くの情報は、「Method of Clustering Multi-Dimensional Related Data In A Computer Database By Combining The Two Vertices of a Graph Connected by An Edge Having the Highest Score」という題の米国特許第5,706,503号に見出すことができ、この特許をここに参照する。
【００２９】
図１に戻ると、近道発生器２２は、元の地図データ２０に作用し、増補地図データ２４を生じる。第1に、近道発生器は、元の地図データ２０に加える新しいリンクを作る。第２に、近道発生器は、元の地図データ２０に現存するノードについて、新しい優先順位レベルを作る。新しいリンクと該新しいノード優先順位レベルは、増補地図データ２４に記憶される。近道発生器２２は、一般的に、電子地図内を移動するのに何のコストも変化させない。
【００３０】
近道発生器２２により作られる２種類のリンクがある。作られる第１の種類のリンクは、２つのより高いリンク優先順位レベルのリンク間を移動するのに使用可能なより低いリンク優先順位レベルの道路上の経路である。作られる第２の種類のリンクは、幾つかのより低いリンク優先順位レベルのリンクをスキップするより高いリンク優先順位レベルのリンクである。両方の種類のリンクを、図４と５を参照して説明する。
【００３１】
図４は、電子地図の一部のグラフの例を示す。図４は、ノード２１０、２１２、２１４、２１６、２１８、２２０、２２２を示す。これらのノードを結合するのは、リンク２３０、２３２、２３４、２３６、２３８、２４０、２４２、２４４、２４６、２４８、２５０、２５２、２５４、２５６である。例示の目的として、リンク２４２、２４４、２４６は、リンク優先順位レベル５の第１のハイウェイであるとする。リンク２３４、２３６は、リンク優先順位レベル５の第２のハイウェイであるとする。更に、リンク２３０、２３２、２３８、２４０、２５０、２５２は、リンク優先順位レベル５の第３のハイウェイであるとする。最後に、リンク２４６、２４８は、リンク優先順位レベル３の幹線道路に沿った通路であるとする。例示の目的で、使用者がノード２２０から２１０へ移動したいとする。１つの従来のナビゲーションシステムは、ノード２２０から２１０へハイウェイに沿ってのみ移動する経路を決定するかもしれない。このような経路は、リンク２５４、２４２、２３６、２３２に沿った経路を含む。本発明の近道発生器は、使用者がリンク２５４、２４８、２３８、２３２に沿って移動するような近道を生じる。これを達成するため、近道発生器２２は、近道リンク２４８を生じる。典型的には、近道２４８は、幹線道路に沿った２つ又はそれ以上のリンク上の移動を表す複合リンクである。リンク優先順位レベル３の２つ又はそれ以上のリンクは、リンク優先順位レベル５の近道リンク２４８で置きかえられる。従って、近道リンク２４８は、近道発生器２２により生じるリンクの１つの例であり、２つのより高いレベルの道路の間を移動するのに使用可能なより低いレベルにおける道路上の経路を表す。即ち、車のドライバーは、リンク２５４、２４２、２３６、２３２上を移動するより、リンク２５４、２４８、２３８、２３２を移動することにより行き先２１０により速く到達する。
【００３２】
図５は、複合リンクの例を示す。図５は、４つのノード２７０、２７２、２７４、２７６を示す。リンク２８０は、ノード２７０をノード２７２に接続する。リンク２８２は、ノード２７２をノード２７４に接続する。リンク２８４は、ノード２７２をノード２７４に接続する。この例では、リンク２８０、２８２、２８４は、全て同じリンク優先順位レベルの終端ノードを有する。リンクの終端ノードは、各リンクが終了するノードである。例えば、リンク２８４の終端ノードは、ノード２７６である。
【００３３】
近道発生器２２は、ノード２７０をノード２７６に結合する新しい複合リンク２８８を作っても良い。リンク２８８に関連付けられた終端ノードのリンク優先順位レベルは、リンク２８０と２８２の終端ノードのリンク優先順位レベルより高い。更に、ノード２７０と２７６のリンク優先順位レベルは、ノード２７２と２７４のリンク優先順位レベルより高い。リンク２８８は、近道発生器２２により作られる複合リンクの例である。
【００３４】
近道発生器２２が近道をどう発見するかを説明する前に、例示の経路発見システム３０が、出発点から行き先への経路をどのようにして求めるかを理解するのは有用である。
【００３５】
図６は、出発点から行き先への経路を求める方法を説明するフローチャートである。図６の方法は、公知の多くの経路発見方法の１例である。本発明と共に経路を発見する他の方法を使用することもできる。ステップ３０２で、システムは、経路発見探査を初期化する。即ち、システムは、経路の出発点と行き先を記憶し、２つの待ち行列、出発点優先順位待ち行列と行き先優先順位待ち行列を設定する。出発点優先順位待ち行列は、ノードの整列したリスト（出発点からその各々への経路は分かっている）と、各ノードへのキーからなる。待ち行列はキーに従ってソートされる。キーを求めるのに色々の他の方法がある。１つの方法では、キーは、出発点からノードへ移動する際の既知の最低コストである。他のキーは、出発点からノードへの最低コストと、ノードから行き先へ移動する予測コストとの合計を含む。この方法に適したノードから行き先への移動コストを予測する方法は色々ある。１つの例は、直線距離に単位距離当たりの予測コストをかける方法である。即ち、ノードとリンクを無視し、ノードと行き先の間の物理的距離を求め、その距離に単位距離当たりの予測コストをかけることである。
【００３６】
行き先優先順位待ち行列は、ノードを整列したリスト（その各々から行き先への経路は分かっている）と、各ノードへのキーからなる。待ち行列は、キーに従ってソートされる。行き先キーを求めるのに色々の他の方法がある。１つの方法では、ノードから行き先への分かっている最低コストの経路を使用する方法を含む。他のキーは、ノードから行き先へ移動する最低コストと、出発点からノードへの予測コストとの合計を含む。残りのコストを予測することを利用する出発点優先順位待ち行列について上述したキーは、出発点から行き先の方向へ偏った探査を生じる。同様に、行き先からの探査は、出発点の方向に偏っている。キーを計算する他の方法は、本発明の範囲内にある。
【００３７】
さらに、システムは出発点探査済ノードリスト及び行き先探査済ノードリストを設定する。出発点探査済ノードリストは出発点からの経路が知られているすべてのノードのリスト、出発点から各ノードへ移動するための最低コスト、及び最低コストの経路に沿った以前のノードを維持する。行き先探査済ノードリストは行き先への経路が知られている各ノードの名前、各ノードから行き先へ移動するための既知の最低コスト、及びその最低コストで行き先へ経路に沿った次のノードの識別子を記憶する。初期化段階３０２が完了した後、出発点の優先順位待ち行列及び出発点探査済ノードリストは出発点を含み、行き先優先順位待ち行列及び行き先探査済ノードリストは行き先を含んでいる。
【００３８】
一旦、システムが初期化されると、ステップ３０４において、システムは規則に従って待ち行列を選択する。本発明に適切な待ち行列を選ぶ多くの規則がある。１つのシステムでは、最小キーと関連する要素を含む待ち行列が選択される。この際、複数の待ち行列が選択されれば、いずれかを選ぶ任意の決定法が使用される。別のシステムでは、最小数の要素を含む待ち行列が選択される。待ち行列を選択するための規則の他の例は、出発点待ち行列と行き先待ち行列とを交替することを含む。即ち、一定回数の反復処理のために（又は一定期間中）出発点待ち行列を選択し、一定回数の反復処理のために行き先待ち行列に切換え、一定回数の反復処理のために出発点待ち行列に切換え戻すこと等を含んでいる。待ち行列はキーによりソートされるから、最小キーのノードは待ち行列の先頭にあるだろう。このノードは「先頭ノード」と呼ばれる。
【００３９】
ステップ３０６では、システムは選択された待ち行列の先頭ノードに対して隣接ノードであるすべてのノードを探し、それらのノードの１つを選択する。システムはちょうど作動開始したところであるから、出発点優先待ち行列のノードだけが出発点である。隣接ノードは、他のノードを通ることなく先頭ノードへ移動又は先頭ノードから移動することができるノードである。ステップ３０８では、システムは、隣接ノードのための探査済ノードリスト又は選択された優先待ち行列に既知のより低いコストがあるか否かを決定する。すなわち、システムは隣接ノードと先頭ノード間の移動コストを決定し、先頭ノードのために既に知られているコストにそのコストを追加し、合計のコストを得る。そのとき探査済ノードリストに既知のより低いコストがない場合、ステップ３１０において、システムは探査済ノードリスト及び優先待ち行列を編集し、隣接ノード及び合計のコストを追加する。既知のより低いコストがある場合、その後、探査済ノードリストは編集されず、システムをステップ３０６にループバックする。ステップ３１０の後、その方法はステップ３０６にループバックし、追加の隣接ノードが探査されないか否かを決定する。隣接ノードのすべてが探査された場合、その後、その方法はステップ３１２に進み、先頭ノードは優先待ち行列から取り除かれる。
【００４０】
ステップ３１４では、システムは停止状態が起こったか否かを決定する。本発明に適した多くの停止状態がある。適当な停止状態の１つの例は、同じノードが出発点優先待ち行列と行き先優先待ち行列の両方の先頭ノードであった時に停止することである。別の停止状態は、行き先優先待ち行列の先頭ノードから行き先への移動コストを加えた、出発点優先待ち行列の出発点から先頭ノードへ移動するコストが、最良の接続コストの全体コストより高いか又はそれに等しい時に停止することを含んでいる。接続ノードは行き先探査済ノードリスト及び出発点探査済ノードリストの両方に現れるノードである。接続ノードの全体コストは、接続ノードから行き先へのコストと出発点から接続ノードへのコストの和である。最良の接続ノードは最低の全体コストの接続ノードである。停止条件にまだ合致しない場合、システムはステップ３０４に進み、他の待ち行列を選択する。停止条件に合致した場合、システムはステップ３１６で経路を作る。ステップ３１８で、システムは経路を報告する。経路を報告することは、経路を示す地図を表示し、地図上で強調された経路の地図を表示し、方向指示を供給し、経路を説明する聴覚出力を供給し、経路を説明するデータのファイルを作り出すと共に渡し、経路を説明するデータにポインタを渡し、機能呼出しに応じて経路を説明するデータを渡すこと等を含んでいる。
【００４１】
経路を構築するステップ（ステップ３１６）は以下の通りである。規則は幾つかの接続ノードを選択する。そのような規則の１つは最良の接続ノードを選択することである。選択された接続ノードＫは出発点探査済ノードリストで調べられ、出発点からの経路上にある前のノードＰ1が見つけられる。Ｐ1が出発点でない場合には、その後、Ｐ1は探査済ノードリストで調べられ、前のノードＰ1が見つけられる。これは出発点に到着するまで続く。出発点がノードＰLとして到着されたと仮定しよう。同様に、Ｋは行き先探査済ノードリストで調べられ、次のノードＮ1が見つけられる。もしＮ1が行き先でない場合には、その後、Ｎ1は探査済ノードリストで調べられる。これは行き先に到着するまで続く。行き先がノードＮMとして到着されると仮定しよう。この点で、出発点から行き先への経路が分かった。それは、ＰL（出発点）からＰL-1まで、ＰL-2まで、…、Ｐ2まで、Ｐ1まで、Ｋまで、Ｎ1まで、…、ＮM-1まで、ＮM（行き先）までの経路である。経路発見についてのさらなる情報は、１９９７年２月２０日に出願された No.08/802,733の Richard Frederick Poppen、Rodney Jude Fernandez、及びJames Laurence Buxtonによる経路発見計算のためのキャッシング、及び１９９８年２月１３日に出願された No.09/023,504の Koji Amakawa、及びEdward Joseph Suranyiによる経路発見のためのシステムで見出すことができる。
【００４２】
上述したように、図６の処理は異なる優先順位レベルで行うことができる。例えば、道路は表１に示されているように異なる優先順位レベルに分割可能であり、経路発見処理は各レベル毎を使用可能である。
【００４３】
図７は近道発生器２２の動作を説明するフローチャートである。図７の第１ステップ３４８で初期化が行われる。この初期化のステップは出発点の地図データ２０を読み出すと共に記憶することを含んでいる。記憶された地図データはノード、リンク、そして、幾つかの実施例では、ノード及び又はリンクのための優先順位レベルを含んでいる。ステップ３５０では、近道発生器２２は各探査レベルで動作する。上述したように、道路網は、道路の種別に応じて、異なる優先順位レベルに分割される。近道発生器２２の動作はレベル毎に行うことができる。最初、ステップ３５０が実行された時は、探査レベルはレベル１である。ある探査レベルで動作後、近道発生器２２はより高い探査レベルがあるか否か、換言すると、現在の探査レベルが最高の探査レベル（例えば、レベル５）か否か、換言すると、現在の探査レベルが最高の探査レベル(例えば、レベル５)か否かを決定する（ステップ３５２）。より高い探査レベルがある場合には、その後、探査レベルはステップ３５４で次のレベルに変更される。したがって、ステップ３５０で、動作される現在の探査レベルがレベル１である場合には、その後、探査レベルはレベル２に変更され、システムはステップ３５０にループバックし、レベル２で動作する。レベル２での動作後、システムはステップ３５０〜３５４を通ってループし続け、レベル３、レベル４及びレベル５で動作する。（５レベルあると仮定すると）レベル５で動作後、ステップ３５２でシステムは動作するレベルがもうないと決定し、近道発生器２２は発見された近道のリンク及び該リンクのリンク優先順位レベルを地図データに追加することを含むステップ３５６に進む。本質的に、ステップ３５６は増補地図データ２４を作るステップを備えている。
【００４４】
図８Ａ及び図８Ｂは、図７のステップ３５０（ある探査レベルで動作）を記載するフローチャートを示す。すなわち、図８Ａ及び図８Ｂの方法は、各々の探査レベルに対して実施される。したがって、もし、５つの探査レベルがあるならば、図８Ａ及び図８Ｂの方法は５回実施される。図８Ａ及び図８Ｂはステップ４００−４４２を有する。図８Ａ及び図８Ｂの方法は探査レベル０に対しては実施されない。探査レベル２−５に対して、本方法はステップ４００で開始される。探査レベル１に対して、本方法はステップ４２２で開始される。
【００４５】
ステップ４００は現在の探査レベルにあるか、またはより高い、電子地図のデータベースにおける全てのノードを探すステップ及びこれらのノードをソートするステップを含む。これらのノードはソートされて、Ｋ−Ｄツリーを形成する。このソートは、地理的に近いノードはリストにおいて通常近くなるようにノードの直列的なリストを形成する。地図データベースにおける各々のリストとノードはリンク優先順位レベル及びノード優先順位レベルと呼ばれる属性を有している。リンク優先順位レベルは、どんな優先順位レベルのときにリンクが使用可能であるかを示している。図７の方法の開始のときに、各々に対するリンク優先順位レベルは、リンクと関連している道路の種別に基づく前述の優先順位レベルである。例外として、道路の種別が如何なる物であっても、リンクがＵターン経路に関するものであり、元のノードに戻る場合には、該リンクに、０の初期のリンク優先順位レベルが付けられる。更に、ノードの初期のノード優先順位レベルはノードに接続するとリンクのリンク優先順位レベルと同じである。ステップ４０２において、近道発生器２２は、処理すべきノードが更にあるか否かを判断する。もし、処理するノードが最早ないならば、本方法は、ステップ４２０（図８Ｂにある）へループする。もし、処理する更なるノードがあるなら、本方法はステップ４０４へループする。第１回目のステップ４０２がステップ４００の後に実行される際、処理するための多くのノードがあり、したがって、近道発生器２２がステップ４０４へ進められることが予期される。
【００４６】
ステップ４０４において、近道発生器２２は、ステップ４００で見出されるノードの１つを取り上げる。ステップ４０６に於いて、近道発生器２２は、ステップ４０４において取り上げられるノードから外へ向かって探査する。ステップ４０６における探査のステップは、図６の経路発見プロセスの変更バージョンである。幾つかの例外は、調査が現在の探査レベルと等しいか、現在の探査レベル以上か、または現在の探査レベルより１低いリンク優先順位レベルを伴うリンクに沿って探査することができるだけである。
【００４７】
図９は、図８Ａのステップ４０６（採択ノードから探査）を実現するための方法を説明するフローチャートである。図９のプロセスは、出発点から行き先までの経路を見つけ出さない。むしろ、図９の方法は、出発点から外へ向かって探査する。ステップ５００において、プロセスが開始される。すなわち、出発点優先順位待ち行列および出発点探査済ノードリストが設定される。図９のプロセスにおいて、探査済ノードリストおよび優先順位待ち行列は３つの追加のフィールド、すなわち使用可能度フィールド、同じ道路を逆方向に移動して同じノードに戻ることを示すＵターンフィールドおよび１つ前のノードが出発点か否かを示す先行フィールドを有する。もし、Ｕターンフィールドが設定されるなら（例えば、論理レベル１を格納する）、Ｕターンフィールドと関連するノードを含む経路はＵターンを有する。もし、特定のノードに対するＵターンフィールドが設定されないなら、そのノードを含む経路はＵターンを含まない。
【００４８】
先行フィールドは特定のノードへの最良の経路が出発点ノードからか、または他の先行ノードからであるかを信号として送るために用いられる。先行フィールドがゼロに等しいとき、特定ノードへの最良の経路は出発点ノードからである。先行フィールドが１に等しいとき（例えば、先行フィールドが設定される）、特定ノードへの最良の経路は他の先行ノードからである。先行ノードは３つの基準に合うノードである。第１の基準は、先行ノードから出発点ノードへの経路を示すリンクがあることである。第２の基準は、先行ノードから出発点ノード以外のノードへリンクがあることである。第３の基準は、出発点ノードへのリンク（第１の基準）および他のノードへのリンク（第２の基準）が現在の探査レベルか、現在の探査レベルより１つ低いか、現在の探査レベルより高いリンク優先順位レベルを持たなければならないことである。ステップ５００は全ての先行ノードを優先順位待ち行列および探査済ノードリストに先行フィールドを伴って設置するステップを有する。出発点は先行フィールドを有していない。
【００４９】
ステップ５０２において、各々のノードに対するノード使用可能度フィールドの値が最初に最大に設定される。ステップ５０２が完了したのち、図９のプロセスはステップ５０４へ進み、他の適切な隣接ノードがあるかを判断する。ステップ５０４は、適切な隣接ノードが、現在の探査レベルに等しいか、現在の探査レベルより１低いか、現在の探査レベルより上のリンク優先順位レベル有するリンクによって通過できる隣接ノードのみを含む点を除いてステップ３０６と同様である。もし、他の適切な隣接ノードがあるなら、プロセスはステップ５０６へ続き、そこで適切な隣接ノードの１つが取り上げられ、そして取り上げられた適切な隣接ノードが探査済ノードリストにあるか否かを判断する。もし、それが探査済ノードリストにあるなら、本方法は、ステップ５１０へ進みノードが探査済ノードリストにより高いコストを有するかを判断する。もし、それがより高いコストを有しているなら、本方法はステップ５１２へ進み、探査済ノードリストを編集し、新しいコストと新しい前のノードを探査済ノードリストへ加え、優先順位待ち行列がそれにより編集され、必要なら、Ｕターンフィールドが更新される。すなわち、もし、探査中の現在のノードへの移動がＵターンを必要とするなら、ＵターンフィールドはＵターンを示すために設定されなければならない。Ｕターンフィールドの使用が従来技術のシステムから改善を示す。ステップ５１２に於いて、もし、前のノード（探査済ノードリストにある）が１に設定された先行フィールドを有するなら、探査中の現在のノードに対する先行フィールドが１に設定される。ステップ５１２の後、プロセスはステップ５１４へ進む。もし、ステップ５１０において、探査済ノードリストにより高いコストがないことが判断されるなら、プロセスはステップ５１４を続ける。ステップ５１４において、近道発生器２２は探査中の現在の隣接ノードのノード使用可能度をチェックする（図１０を参照して以下に説明する）。ステップ５１４の後、プロセスはステップ５０４へ戻る。もし、ステップ５０６において、探査中の隣接ノードが探査済ノードリストになかったことが判断されたなら、本方法は、機能がステップ５１２と同じであるステップ５０８へ進む。このステップは、探査済ノードリストを編集し、優先順位待ち行列を編集し、もし必要なら、Ｕターンフィールドを更新し、そしてもし必要なら、先行フィールドを更新することを含む。ステップ５０８の後、本方法は、ステップ５０４へ戻る。
【００５０】
適切なリンク優先順位レベルのリンクによって隣接ノードに進められるかを判断することに加えて、ステップ５０４はノードが出発点の閾値コスト内にあるかも判断する。現在の調査に対する出発点は、図８Ａのステップ５０４において最も最近取り上げられたノードである。したがって、近道発生器２２は出発点から現在考慮中の隣接ノードへいくコストを判断する。このコストが閾値より小さいと判断されると、現在考慮中の隣接ノードは、適切な隣接ノードとして考えられる。閾値はリンク優先順位レベルによって変わる。テーブル４は探査レベル２−５用の閾値の例を提供する。
【００５１】
テーブル４
探査レベル 停止閾値
２ ３００秒
３ ９００秒
４ １／２時間
５ １時間
隣接ノードとみなされる現在考慮中の隣接ノードが閾値内にない場合には、その隣接ノードは適当な隣接ノードではない。従って、ステップ５０４のテストは、ノードが隣接ノードであるかどうか、そのノードに適当なリンク優先順位レベルのリンクが到達できるかどうか及び閾値内にあるかどうかである。
【００５２】
ステップ５０４において適当な隣接ノードがそれ以上ない場合には、システムがステップ５２０に進む。ステップ５２０は、優先順位待ち行列から先頭のノードを除去することを含む。ステップ５２２において、近道発生器２２は、優先順位待ち行列が空か否かを決定する。優先順位待ち行列が空でない場合には、図１０の方法は、ステップ５０４にループバックして続行される。
【００５３】
図１０は、図９のステップ５１４（使用可能度のチェック）を実施する方法を記載するフローチャートである。図１０の方法は、図９の探査時において探査中のノードが既に探査済ノードリストにある場合に実行される。ステップ５５０において、近道発生器２２は、探査中のノードに対する２つの経路のどちらが使用不可能経路であるか否かを決定する。すなわち、ノードは既に探査済ノードリストにあるので、そのノードに到達する経路は２つある。第１の経路は、（ステップ５１２より前の）探査済ノードリストにより指示された経路を含む。第２の経路は、優先順位待ち行列の現在の先頭ノードを介して探査中の現在の隣接ノードに到達する経路を含む。より大きなコストを有する経路が使用不可能経路とされる。
【００５４】
ステップ５５２において、近道発生器２２は、使用不可能経路に沿って１リンクだけ、戻って、探査中の現在の隣接ノードより一つだけ前のノードへ戻る。ステップ５５４において、近道発生器２２は、ステップ５５２で見つけられたノードを出る全ての前進リンクを考察する。前進リンクは、ノードを出る方向のリンクである。ステップ５５２で見つけられたノードからの前進リンクは、それが、より低コストを有する探査済ノードリストに既にあるノードに通じ、そのノードの前のノードがステップ５５２で見つけられたノード以外のノードである場合に、使用不可能であるとされる。探査中のノードからの前進リンクの少なくとも１つが使用不可能でない場合には、図１０のプロセスは完了する。前進リンクが全て使用不可能である場合には、近道発生器２２はステップ５５６に進み、ステップ５５２で見つけられたノードの使用可能度をゼロにリセットする。ステップ５５８において、近道発生器２２は、その使用可能度がゼロにリセットされたばかりのノードから１リンクだけ前のノードに戻る。ステップ５６０において、近道発生器２２は、ステップ５５８において戻ったノードを出る各前進リンクのリンク使用可能度を決定する。リンク使用可能度は、リンクのコストの逆数とリンクの標的ノードの使用可能度の和である。ステップ５５８において到達したノードの使用可能度フィールドは、複数ある前進リンクの内のリンク使用可能度に変更される。従って、移動できるリンクのいずれかが最大の使用可能度を有する場合には、ノードの使用可能度は最大にとどまる。ステップ５５８において戻されたノードが、その使用可能度がステップ５６２において変更された使用可能度を有する場合には、システムは、ステップ５５８にループバックし、ステップ５５８〜５６４を繰返す。これらのステップを設けた意味は、１つのノードだけが複数の使用不可能ノードに通じている場合には、そのノードもまた使用不可能であるためである。ステップ５６２においてノードの使用可能度が変更されなかった場合には、図１０のプロセスは完了する。一般に、従来技術の近道発生器は、別の経路によってより速い方法で移動できる場所に通じているので使用可能でなかった近道又は合成リンクを発見した。従って、図１０のステップは、より有効で且つより使用可能度のある近道を発見することにより従来技術に比べて大きな改良を提供する。
【００５５】
図８Ａのステップ４０６を完了した後、近道発生器２２は、探査済ノードリストを記憶する。ステップ４０８において、探査済ノードリストの１つのノードが選択される。ステップ４１０において、そのノードのノード優先順位レベルが現在の探査レベルにあるか又はより高いか否かが決定される。そのノードのノード優先順位レベルが現在の探査レベルにない場合には、その方法はステップ４１８にループする。ノードが現在の探査レベルにあるか又はより高い場合には、ステップ４１２において、システムが、探査中のノードについて先行フィールド又はＵ−ターンフィールドが設定されているか否かを決定する。先行フィールド又はＵ−ターンフィールドのいずれかが設定されている場合には、その方法はステップ４１８にループする。先行フィールド又はＵ−ターンフィールドのいずれも設定されていない場合には、そのシステムはステップ４１４にループして、ノード使用可能度が閾値よりも低いか否かを決定する。ノード使用可能度が閾値よりも小さくない場合には、システムは後戻りステップ（ステップ４１６）を実行する。後戻りした後、システムは、探査済ノードリストにまだノードが残されているか否かを決定する。まだノードが残されている場合には、システムはステップ４０８にループバックして探査済ノードリストの別のノードを選択する。探査済ノードリストにもうノードがない場合には、システムは、ステップ４０２にループバックして、ステップ４００において識別されたノードの組から探査するためのノードがまだあるか否かを決定する。ステップ４１４は、ステップ４０６の最新の繰り返しについて使用可能でないノードにおいて終端するリンクについての新しいリンク優先順位レベルの生成を防止する。
【００５６】
図１１は、図８Ａのステップ４１６（後戻り）のプロセスを説明するフローチャートである。図１１のプロセスは、ステップ４０８〜４１４において選択されているノードからスタートする。ステップ５７６において、近道発生器２２は、該選択されているノードから１リンクだけ戻って探査する。すなわち、探査済ノードリストには、該選択されているノードに到達する経路に沿って前のノードを指示する前のフィールドがある。ステップ５７６は、その前のノードに戻って探査することを含む。ステップ５７８において、前のノードに到達するように探査されたリンクのコストが出発点又は行き先のリンク閾値内にあるか否かをテストする。それが出発点又は行き先のリンク閾値内にある場合には、図１１の方法は、ステップ５８４にループする。リンクが出発点又は行き先のリンク閾値内にない場合には、方法は、ステップ５８０に進む。
【００５７】
ステップ５８０において、近道発生器２２は、前のノードに到達する探査リンクが現在の探査レベルよりも１レベル下のリンク優先順位レベルを有するか否かをテストする。有する場合には、そのリンクについて新しいリンク優先順位レベルが発生され古いリンク優先順位レベルと置き換えられる。ステップ５８２の後、システムはステップ５７６で探査されたノードが最新の探査の出発点であるか否かを決定する。出発点でない場合には、図１２の方法は、ステップ５７６にループバックする。出発点である場合には、図１２の方法は、完了する。ステップ５８０において、探査されたリンクが現在の探査レベルより１レベル下のリンク優先順位レベルでない場合には、その方法は、ステップ５８４にループする。図１２の方法は、或るリンクを使用促進するプロセスと考えてもよい。
【００５８】
図８Ａに戻って、ステップ４０２において識別されたノードが全て探査されたことが決定された場合には、図８Ａ〜８Ｂのプロセスはステップ４２０に進む。ステップ４２０において、近道発生器２２は、ステップ４００において選択された各ノードについてノード優先順位レベルを決定する。図１２Ａは、選択された各ノード（ステップ４２０）についてノード優先順位レベルを決定するプロセスを示すフローチャートである。図１２Ａのプロセスは、ステップ４００において識別された各ノードについて実行される。
【００５９】
ステップ６００において、近道発生器２２は、探査中の現在のノードについて全ての前進リンクを見る。図１２Ｂは、５つの前進リンクを有するノード６４０を示す。図１２Ｃは、３つの前進リンクを有するノード６６０を示す。各前進リンクに隣接する番号は、各リンクについてのリンク優先順位レベルを表す。ステップ６０２において、近道発生器２２は、前進リンクが選択される最高のリンク優先順位レベルを決定する。ステップ６０２のために、与えられたリンク優先順位レベルにおけるリンクも、その与えられたリンク優先順位レベルより下の優先順位レベルのどれかであるとみなされてもよい。例えば、図１２Ｂを見ると、一番上の前方レベルは、４のリンク優先順位レベルである。そのリンクもまたレベル３、レベル２又はレベル１とみなされてもよい。図１２Ｂを見ると、レベル４における２つの前進リンクの選択があり、レベル３における２つの前進リンクの選択があり、レベル２における４つの前進リンクの選択があり、及び、レベル１における５つの前進リンクの選択がある。前進リンクの選択がある最高のリンク優先順位レベルは、レベル４である。
【００６０】
図１２Ｃを参照すると、リンク優先順位レベル１、２及び３の前進リンクがある。従って、リンク優先順位レベル１で３つ及びリンク優先順位レベル２で２つのリンクの選択がある。リンク優先順位レベル３のリンクは１つしかない。それゆえ、前進リンクの選択がある最高レベルは、リンク優先順位レベル２である。
【００６１】
ステップ６０４において、探査中のノードが、ステップ６０２で決定されたリンク最高選択レベルに等しい「決定されたノード優先順位レベル」に割当てられる。ステップ６０６において、ステップ６０４で割当てられた「決定されたノード優先順位レベル」が、現在の探査レベル及び上記ノードに関連する道路のリンク優先順位レベルと比較される。ステップ６０４で割当てられた決定されたノード優先順位レベルが現在の探査レベルより低い場合、あるいは、上記決定されたノード優先順位レベルが上記ノードに関連する道路の優先順位レベルより高い場合、処理はステップ６０８に進み、そうでない場合には、処理はステップ６１０に進む。ステップ６０８において、該ノードに対する実際のノード優先順位レベルが、ステップ６０４において上記決定されたノード優先順位レベルに設定される。この実際のノード優先順位レベルは、プロセッサで読取り可能な記憶媒体の一時ファイルに記憶される。ステップ６１０において、最初にノードに関連する道路の優先順位レベルに等しく設定された該ノードの実際の優先順位レベルは、変更されない。この実際のノード優先順位レベルも、上記プロセッサ読取り可能な記憶媒体に記憶される。
【００６２】
図８Ｂのステップ４２０の完了後、近道生成器２２がステップ４２２を実行して、現在の探査レベル又はそれより高いレベルの全ノードを見つけて、ステップ４００で行ったソートと同様にそれらのノードを再度ソートする。ステップ４２４において、近道生成器２２は、ステップ４２２で識別されたノードの１つを選択する。ステップ４２６において、近道生成器２２は、現在の探査レベル又はそれより高いレベルのリンク優先順位を持つリンクに到達できる、ステップ４２４で選択されたノードに隣接するノードの全てを見つける。ステップ４２８において、それら隣接するものの１つが選択される。ステップ４３０において、近道生成器２２は、選択された上記隣接ノードからの前進リンクを探査して、現在の探査レベルまたはそれより高いレベルのリンクの選択が生じるまで更に前進リンクの探査を続ける。この選択に到達すると、複合リンクがステップ４３２で作られる。この複合リンクは、ステップ４２４で選択されたノードから始まり、リンクの選択がある場所（ステップ４３０参照）で終わる。
【００６３】
ステップ４３４において、システムは、「進入ノード」について追加の複合リンクを生成する。近道生成器２２は、ステップ４３２で作られた複合リンクの開始点である交差点に移動することを示すノードの全てを考察する。交差点に入るノードは、「進入ノード」と記される。この進入ノードから、ステップ４３２で作られた複合リンクの終点のノードへ至るリンクが追加される。この追加リンクは、ステップ４３４で作られた追加の複合リンクである。もし進入ノードの優先順位レベルがゼロであれば、ステップ４３４の新たな複合リンク生成を開始するために１リンクだけ後戻りする。
【００６４】
ステップ４３６において、ステップ４３２及び４３４で作られた複合リンクは、プロセッサ読取り可能な記憶媒体に記憶される。１実施例では、ステップ４３６の複合リンクとステップ６０８の新たなノード優先順位レベルとは、一時ファイルに記憶され、且つ、ステップ３５６の増補地図データ２４に永久的に（又は半永久的に）記憶される。別の実施例では、ステップ３５６を含まず、ステップ４３６と６０８とが、増補地図データ２４に上記新たなリンク及びリンク優先順位レベルを記憶する処理を含んでいる。
【００６５】
図８Ｂのステップ４４０において、近道生成器２２は、更に探査すべき隣接ノード（ステップ４２６参照）があるか否かを決定する。もし、更に探査すべき隣接ノードがあるならば、プロセスはステップ４２８へループする。もし、更に探査すべき隣接ノードがそれ以上ないならば、プロセスはステップ４４２へループして、探査すべきノード（ステップ４２２で見つかったノードの中のノード）があるか否かを決定する。更に探査すべきノードがない場合、図８Ａ及び８Ｂのプロセスは完了する。更に探査すべきノードがある場合、プロセスはステップ４２４へ戻るようにループする。
【００６６】
理解されるように、近道生成器２２は、各レベル毎のプロセスで作業する。近道生成器２２は、レベル１の道路を使用して、レベル２での全ての近道を見つけ出す。次に、近道生成器２２は、レベル３へ進行し、レベル２の道路（前のレベルを含む）を使用して、レベル３での全ての近道を見つける等。
【００６７】
本発明の近道生成器は、ハードウェアで実施することもできるし、ソフトウェアで実施することもできるし、ハードウェアとソフトウェアとで実施することもできる。１つの実施態様では、システムは、本書に記述した機能を実行できるプロセッサ命令を含む専用のプロセッサで構成できる。本書に記述した機能を実行するように、回路を開発してもよい。１つの実施例では、本発明は、ナビゲーションシステムの一部となる。ナビゲーションシステムの例が、米国特許第４，７９６，１５１号明細書、米国特許第４，９１４，６０５号明細書、米国特許第５，３１１，１９５号明細書、米国特許出願第０８／７４７，１６１号明細書に記載されており、これらの明細書に内容は、本願の参照文献として組入れられる。別の実施態様においては、本発明は、コンピュータシステムと一緒に使用するための命令を実行できる複数のプロセッサを含んでいる。コンピュータシステムにローディングする前に、ソフトウェアが、コンピュータで読取り可能な媒体（例えば、磁気フロッピー（登録商標）ディスクや磁気テープやＣＤ−ＲＯＭ）に存在する。
【００６８】
図１３は、近道発生装置および／または、経路発見システムを実行するのに使用することができるコンピュータシステムのハイレベルブロックダイヤグラムを図示したものである。図１３のコンピュータシステムはプロセッサユニット７１２およびメインメモリ７１４を備えている。プロセッサユニット７１２は、単一のマイクロプロセッサを含むことができ、あるいは、多数のプロセッサシステムとしてのコンピュータシステムを形成するための複数のマイクロプロセッサを含むことができる。メインメモリ７１４は、プロセッサユニット７１２によって実行される命令およびデータを一部、格納する。本発明のシステムが、全体的にまたは、部分的にソフトウェアで実行される場合には、メインメモリ７１４は動作中に実行可能なコードを記憶する。メインメモリ７１４ダイナミックランダムアクセスメモリ（ＤＲＡＭ）および高速キャッシュメモリのバンクを備えることができる。
【００６９】
図１３のシステムは、さらに大容量記憶装置７１６、周辺機器７１８、入力装置７２０、可搬式記憶媒体ドライブ７２２、グラフィックサブシステム７２４および出力ディスプレイ７２６を備える。簡単化するために、図１３に示される構成要素は、単一のバス７２８を介して接続されているように描かれている。しかし、構成物は、１つあるいはそれ以上の伝送手段を介して接続することができる。たとえば、プロセッサ７１２およびメインメモリ７１４はローカルマイクロプロセッサバスを介して接続することができる。そして、大容量記憶装置７１６、周辺機器７１８、可搬式記憶媒体ドライブ７２２およびグラフィックサブシステム７２４は、１つ以上の入出力（Ｉ／Ｏ）バスを介して接続することができる。大容量記憶装置７１６は、磁気ディスクドライブあるいは光学的ディスクドライブで実行することができるものであるが、プロセッサユニット７１２によって使用されるデータおよび命令を格納するための不揮発性記憶装置である。１つの実施例においては、大容量記憶装置７１６は、メインメモリ７１４へのローディングの目的で、本発明を実行するシステムソフトウェアを格納する。可搬式記憶媒体ドライブ７２２は、可搬式不揮発性記憶媒体、例えばフロッピー（登録商標）ディスク、に関連して動作するものであって、図１３のコンピュータシステムに対してデータおよびコードの入出力を行う。一つの実施例では、本発明を実行するためのシステムソフトウェアは、そのような可搬式媒体に記憶されており、該可搬式記憶媒体ドライブ７２２を介してコンピュータシステムに入力される。周辺機器７１８は、任意の形式のコンピュータ支持装置、例えば、入出力（Ｉ／Ｏ）インターフェース、を備えることができ、該コンピュータシステムに付加的な機能を追加する。たとえば、周辺機器７１８は、ネットワーク、モデム、等に対してコンピュータシステムを介在させるためのネットワークインターフェースカードを備えることができる。 入力装置７２０は、ユーザーインターフェースの一部を与える。入力装置７２０は、英数字およびその他のキー情報を入力するための英数字キーパッド、あるいはマウス、トラックボール、スタイラス、あるいはカーソル方向キーといった、ポインティングデバイスを備えることができる。テクスチャおよびグラフィック情報を表示するために、図１３のコンピュータシステムは、グラフィックサブシステム７２４および出力ディスプレイ７２６を備える。出力ディスプレイ７２６陰極線管（ＣＲＴ）ディスプレイ、液晶ディスプレイ（ＬＣＤ）あるいはその他の適当なディスプレイ装置を備えることができる。グラフィックサブシステム７２４は、テクスチャおよびグラフィカル情報を受信し、ディスプレイ７２６に出力するための情報を処理する。出力装置７２６は、経路発見判断の結果を報告し、地図を表示し、方向を表し、情報確認を表示し、および／または、ユーザーインターフェースの一部であるその他の情報を表示するのに使用することができる。図１３のシステムは、または、オーディオシステム７２８を備えており、このオーディオシステムは、マイクロフォンを備える。１つの実施例では、オーディオシステム７２８は、マイクロフォンからのオーディオ信号を受信するサウンドカードを備える。さらに、図１３のシステムは、出力装置７３２を備えている。適当な出力装置の例は、スピーカー、プリンター等を含む。
【００７０】
図１３のコンピュータシステムに含まれる構成要素は、汎用コンピュータシステムで見られる通常のものであり、周知のコンピュータ構成要素の広いカテゴリを表すものである。このように、図１３のコンピュータシステムはパソコン、ワークステーション、ミニコンピュータ、メインフレームコンピュータ等とすることができる。コンピュータはまた異なるバス形態、ネットワークプラットフォーム、マルチプロセッサプラットフォーム等を備えることができる。さまざまなオペレーティングシステムはユニックス(登録商標)、ウィンドウズ(登録商標)、マッキントッシュ(登録商標)ＯＳおよび他の適当なオペレーティングシステムを含んで使用することができる。
【００７１】
上記の本発明の詳細な記述は、説明および記述目的で提出されているものである。本発明を消尽し、あるいは開示された正確な形態に限定するつもりはなく、明らかに多くの修正および変形が上記の教示に照らして可能である。記載された説明は、本発明の原理を最も良く説明するために選択されたものであり、それによってその実質的な応用は、当業者がさまざまな実施形態で、考慮した特定の用途に適合するようにさまざまな修正を行って、最適に活用することを可能にするものである。本発明の範囲は添付の特許請求の範囲の記載によって画定されることを意図するものである。
【技術分野】
【０００１】
本発明は、電子地図から近道を発見する近道発見装置に係る。
【背景技術】
【０００２】
コンピュータは、地図の考え方を、位置を静的に示す画像から、物理的、社会的又は経済的システムを定量化する地理的に参照される電子データより成る電子地図へと根本的に変えた。電子地図に含まれる情報の範囲は、無限である。例えば、道路の電子地図は、要素間の距離、移動時間、区画番号、税金情報、通行者情報、処理時間、待機時間等を含むことができる。更に、地図を１つ以上のインテリジェントデータファイルとしてコンピュータに記憶することにより、そのデータを如何なるソフトウェアプリケーションが操作することも許されるようになる。
【０００３】
電子地図の１つの利点は、地図の種々の部分に関連したコストを記憶し、決定しそして利用できることである。コストは、最小又は最大にすることのできる変数である。コストとは、例えば、時間、距離、支払う通行料金、転換の容易さ、景色の良さ等を含む。通常、コストは、整数として表わされる。時々、コストは、実数値として表わすこともできる。コストに関する付加的な情報は、参考としてここに取り上げる１９９６年１１月２５日出願の「経路発見計算のために複数のコストレベルの使用(Using Multiple Levels Of Costs For A Pathfinding Computation)」と題する米国特許出願第０８／７５６，２６３号に見ることができる。
【０００４】
電子地図は、出発点と行き先との間のルートを計算する方法である経路発見に使用することができる。あるシステムは、推奨ルートを計算し、そして地図表示上にその推奨ルートをハイライト処理するか、又は曲がるたびに方向を指示する（紙、表示又は音声で）か、或いはその両方によって運転者を誘導する。経路発見システムが行き先への推奨ルートを計算するときには、ある特定の基準に基づいて最も望ましいルートを発見することによりそれを行う。これらの基準は、運転者によって指定されてもよいし、又は製造時に初期値として設定されてもよい。多くの場合に、システムは、あるコスト、例えば、運転時間を最小にする経路を発見するように使用される。
【０００５】
経路発見に使用される電子地図は、道路網の接続に関する情報、即ち道路の断片が互いに接続するか又は接続しない態様に関する情報、例えば、通常の交差点があるか、高架道路があるか、転換が制限されているか等々の情報を保持しなければならない。非常に広い範囲では、これが膨大な情報となる。電子地図は、数十又は数百メガバイトのデータを含む。このような膨大な量のデータを経済的に保持すると共に、ユーザが更新されたコピーと容易に交換できるようにするために、現在の多数の経路発見装置（経路探査ソフトウェアを伴う汎用コンピュータ、自動車用ナビゲーションシステム又は他の地図アプリケーション装置を含む）は、ＣＤ−ＲＯＭを使用して電子地図データを記憶している。
【０００６】
経路発見プロセスは多量のデータを分類しなければならないので、プロセスが低速となる。経路発見プロセスをスピードアップする１つの手段は、優先順位レベルを使用することである。優先順位レベルを使用すると、人間が経路発見プロセスを実行するのと同様のやり方で経路発見プロセスが経路を見つけることができ、最終的な経路は、人間が決定した経路と同様になる。経路を、人間が決定する経路と同様にすることで、経路は、より理解し易く且つユーザに馴染み易いものとなる。
【０００７】
紙の地図上で経路を手動で見つけるときには、ユーザは、通常、出発点と行き先を識別する。ユーザは、居住地道路を経て集合又は幹線道路のような主要道路へ進むように航行する。次いで、ユーザは、主要道路を経てハイウェイを見つけるように航行する。行き先に最も近いハイウェイ出口が見つかるまで、ハイウェイ上で経路を決定し続ける。ハイウェイ出口が見つかると、ユーザは、主要道路を経て行き先のできるだけ近くまで航行する。最終的に、ユーザは、主要道路上のその最至近点から、居住地道路を用いて行き先へ至る経路を見つける。従って、ユーザは、本来的に、優先順位レベルを使用している。即ち、１つの優先順位レベルは、居住地道路であり、第２の優先順位レベルは、主要道路であり、そして第３の優先順位レベルは、ハイウェイである。経路発見プロセス中の第１の地域において、ユーザは、居住地道路を経て航行する。第２の地域において、ユーザは、主要道路及び／又はハイウェイのみを経て航行する。第３の地域において、ユーザは、ハイウェイのみを経て航行し、等々となる。このプロセスは、非常に効率的である。というのは、ユーザが常に全ての道路を経て探す場合に、考慮すべきデータが著しく多数あり、経路が最も効率的な経路となり難いからである。
【０００８】
使用可能な経路を効率的に見つけるために、本願発明も、優先順位レベルを使用する。種々の経路発見システムは、異なる道路種別を異なるレベルに分割する。システムが３つのレベルを使用するか、４つのレベルを使用するか、５つのレベルを使用するか、６つのレベルを使用するか等は、ここでの説明にとって必ずしも重要ではない。テーブル１は、道路を６つの優先順位レベルに分割するシステムの一例を示す。
テーブル１
道路の種別 道路の種別に従う優先順位レベル
路地 ０
居住地道路 １
集合道路 ２
幹線道路 ３
重要度の低いハイウェイ ４
重要なハイウェイ ５
このように、道路の種別に従って、時間的により高いコスト（換言すると、単位距離移動するのにより長い時間）をもたらす道路の種別に対して、より低い優先順位レベルが付けられる。道路の種別と最高制限速度とが関連していることは一般に知られていることである。
【０００９】
明らかなように、テーブル１は、異なる道路を６つの道路種別、即ち路地、居住地道路、集合道路、幹線道路、重要度の低いハイウェイ及び重要なハイウェイに分割している。各道路の種別には優先順位レベルが指定される。１つの経路発見システムでは、システムが出発点から行き先への経路を決定するときに、システムは、優先順位レベル１及びそれより高い道路を探査し、出発点及び行き先から同時に経路探査を実行することにより処理を開始する。
本願発明では、この道路の種別に係る優先順位レベルを、道路の分岐点を意味するノード間の１方向の経路を意味するリンクのリンク優先順位レベルの初期値として使用する。
この経路探索は、促進基準が満足するまで続けられる。促進基準は、３組の基準を含む。第１基準は、促進閾値である。この促進閾値は、コストである。起点から現在考慮中の隣接ノードへ（又はノードから行先へ）移動するコストがこの促進閾値より高いときに、促進閾値が満足される。第２基準は、探査中に、低い優先順位（又はそれより高い）にあるノードの最小数に到達しなければならないことである。第３基準は、探査中に、高いリンク優先順位レベル（又はそれより高い）のリンクのノード数が最小数に到達しなければならないことである。例えば、リンク優先順位レベル１からレベル２へ促進するときには、リンク優先順位レベル１が低い優先順位であり、そしてリンク優先順位レベル２が高いリンク優先順位である。３つの基準全部が満足されたときに、促進基準が満足される。
【００１０】
１組の促進閾値の一例がテーブル２に示されている。例えば、最初の行は、レベル０（及びそれ以上）からレベル１（及びそれ以上）へ探査を促進するための促進閾値を表わすコスト（ミリ秒）を表わしている。
テーブル２
促進のための 促進閾値
リンク優先順位レベル （コスト、ミリ秒）
０ ０
０から１ 10,000
１から２ 10,000
２から３ 120,000
３から４ 300,000
４から５ 600,000
第２及び第３の促進基準に対する１組の値は、テーブル３に例示する。
【００１１】
テーブル３
低優先順位 高優先順位
促進のための （又はそれより高い） （又はそれより高い）
リンク優先順位レベル ノードの最小数 ノードの最小数
０から１ ２０ １
１から２ ２０ ２０
２から３ ３０ ３０
３から４ ４０ ４０
４から５ ５０ ２５
【００１２】
優先順位レベル１以上における探査のための促進基準を満足した後に、システムは、優先順位レベル２以上の道路のみを考慮することにより第２促進基準を満足するまで経路探索プロセスを継続する。この第２促進基準に到達した後に、システムは、電子地図を探査し続けるが、第３促進基準に到達するまでリンク優先順位レベル３以上の道路しか考慮しない。第３促進基準を満足した後、システムは、第４促進基準に到達するまでリンク優先順位レベル４以上の道路のみを考慮して電子地図を通して探査し続ける。この第４促進基準を満足した後、システムは、リンク優先順位レベル５の道路のみを考慮して電子地図を探査し続ける。
【００１３】
上述したリンク優先順位レベルを使用する幾つかの従来の経路発見システムに対してなされる１つの改善は、近道を含ませることであり、これは、経路発見プロセスをスピードアップし、良好な経路を形成する上で助けとなり、そして人間が紙の地図を使用して形成する経路により近い経路を形成する上で助けとなる。電子地図に近道を使用する幾つかの公知システムは、人間が電子地図のデータベースに手で近道を追加するものである。このプロセスは、低速で、冗長で且つ効率の悪いものである。
【００１４】
他の従来のシステムは、コンピュータを使用して近道を自動的に発生する。しかしながら、これらシステムは、コンピュータにより発生される近道が顧客にとって使用可能でない経路を含む傾向があるために問題となっている。即ち、特定の方法の要求を満足する適切な近道が発生されるが、その発生された近道より更に使用可能な近道又は経路が存在する。多くのユーザは、非常に短い時間内に最短の経路を決定できることをシステムに望むために経路発見システムにアクセスする。ユーザは、ユーザに馴染みのある近所にいて、経路発見システムのユーザが知っている近道より距離の長い近道をシステムが決定したときに、システムの性能に失望する。
【発明の概要】
【発明が解決しようとする課題】
【００１５】
それ故、電子地図のデータベースに近道を自動的に追加することができ、その追加される近道が使用可能で且つ効率的な近道であるようにするシステムが要望される。
【課題を解決するための手段】
【００１６】
本発明は、電子地図データベースから近道を発見することのできる近道発見装置を提供する。ここに開示する近道発生装置は、電子地図データベースにおいて、或るノード優先順位レベルを高めることにより近道を発見することができる。ここで、ノード優先順位レベルとは、ノードに接続される複数のリンクのリンク優先順位レベルの内で最大の優先順位レベルである。
【００１７】
本発明において、各リンクは、このリンクの道路の種別に応じたリンク優先順位レベルを有する。本発明は、出発点ノードから探査を開始する。この探査段階は、どのノードが使用可能でないか決定することを含む。探査中に探査されそして使用可能でないと決定されたノードで終端しないリンクのリンク優先順位レベルがより高いリンク優先順位レベルに切り替えられる。より高いリンク優先順位レベルに切り替えられるリンクが複数のリンクからなる複合リンクであってよい。
【００１８】
１つの実施形態において、本発明は、ノードに対するノード優先順位レベルを電子地図に記憶することを含む。新たなリンク優先順位レベルを有する１つ以上のリンクにより接続されたノードに対して新たなノード優先順位レベルが形成される。新たなノード優先順位レベルは、電子地図に記憶される。
【００１９】
１つの別の形態において、システムは、探査中に通過したＵターンを含む経路に対して１つ以上のＵターン指示を記憶する段階も含む。この実施形態では、新たなリンク優先順位レベルを付与する段階は、記憶されたＵターン指示に関連したリンク又は経路を考慮しない。
【００２０】
複合リンク及び新たなノード優先順位レベルを記憶するときには、新たなデータを既存の電子地図ファイルに記憶することができる。或いは又、新たなノード優先順位レベル及び複合リンクそして元のマップファイルからの適当なオリジナルデータを含む新たなファイルを発生することもできる
【００２１】
本発明は、ソフトウェア、ハードウェア或いはソフトウェアとハードウェアの組合せを用いて実施することができる。本発明の一部分又は全部をソフトウェアで実施する場合には、そのソフトウェアは、プロセッサ読み取り可能な記憶媒体に存在し得る。適当なプロセッサ読み取り可能な記憶媒体は、例えば、フロッピー（登録商標）ディスク、ハードディスク、ＣＤ ＲＯＭ、メモリＩＣ等を含む。システムがハードウェアを含むときには、ハードウェアは、出力装置（例えば、モニタ、スピーカ又はプリンタ）と、入力装置（例えば、キーボード、ポインティングデバイス及び／又はマイクロフォン）と、出力装置と通信するプロセッサと、プロセッサと通信するプロセッサ読み取り可能な記憶媒体とを含む。プロセッサ読み取り可能な記憶媒体は、本発明を実施する段階を実行するようにプロセッサをプログラミングすることのできるコードを記憶する。本発明のプロセスは、インターネットのウェブページにおいて実施することもできるし、又は電話線を経てアクセスできるサーバーにおいて実施することもできる。
【００２２】
以下に述べる動作段階の多くは、公知の近道発生装置に見られるものである。しかしながら、公知の近道発生装置は、以下に述べるように、ノード使用可能度を利用する手段を含んでいない。ここで、ノード使用可能度とは、複数ある前進リンクの内の最大のリンク使用可能度に変更されるパラメータであり、リンク使用可能度とは、リンクのコストの逆数と該リンク終端部のノード使用可能度との和である。
【００２３】
本発明のこれら及び他の目的並びに効果は、添付図面を参照した本発明の好ましい実施形態の以下の説明から明らかとなろう。
【図面の簡単な説明】
【００２４】
【図１】本発明の近道発生装置がどのように使用されるかを示すブロックダイヤグラム。
【図２】近道発生装置の出力がどのように使用されるかを示すブロックダイヤグラム。
【図３】電子地図の一部を表す有向グラフの例。
【図４】電子地図の一部を表す有向グラフの例。
【図５】電子地図の一部を表す有向グラフの例。
【図６】電子地図あるいは他のグラフにおける経路を発見するための例示的な方法を記載したフローチャート。
【図７】近道発生装置の動作を記述したフローチャート。
【図８Ａ】図７の（現在の探査レベルでの動作）ステップ３５０を実行するための方法を記述したフローチャート。
【図８Ｂ】図７の（現在の探査レベルでの動作）ステップ３５０を実行するための方法を記述したフローチャート。
【図９】図８Ａの（採択ノードから探査）ステップ４０６を実行する方法を記述したフローチャート。
【図１０】図９の（使用可能度チェック）ステップ５１４を実行する方法を記述したフローチャート。
【図１１】図８Ａの（後戻り）ステップ４１６を実行する方法を記述したフローチャート。
【図１２Ａ】図８Ｂの（各採択されたノードの実際のノード優先順位レベルを決定する）ステップ４２０を実行する方法を記述したフローチャート。
【図１２Ｂ】図１２Ａを説明する手助けするのに使用する、４つの前進リンクを有するノードを描写したもの。
【図１２Ｃ】図１２Ａを説明する手助けするのに使用する、３つの前進リンクを有するノードを描写したもの。
【図１３】近道発生装置および／又は経路発見システムを実行するために１つの例示的なハードウェアシステムのブロックダイヤグラムである。
【発明を実施するための形態】
【００２５】
図１は、本発明の近道発生器の使用方法を示すブロック図である。図１は、入力を受けて出力を出す近道発生器２２を示している。入力は、元の地図データ２０を含み、出力は、増補地図データ２４を含む。元の地図データ２０は、地図データベースを形成する１つまたはそれ以上のファイルの集成である。地図データベースの詳細については後述する。元の地図データベース２０は、モデム、電子メール、ファイル転送、ポインタ、ファンクションコール等を介して近道発生器２２によって受信されうる。元の地図データ２０は、プロセッサ読み取り可能な記憶媒体に記憶される。近道発生器２２は、元の地図データ地図２０を受け取り、後述するように、近道を加えて、増補地図データ２４を生成する。増補地図データ２４の生成は、新しい地図データ（すなわち、近道）を既存の元の地図データファイル２０に加えることを含みうる。別の仕方として、増補地図データ２４の生成は、近道発生器２２によって生成された新しいデータおよび元の地図データ２０からの古いデータのいくつかまたは全てを含む新しいファイルを生成することを含みうる。この結果として生ずる増補地図データ２４は、近道発生器２２によって生成される近道を含む１つまたはそれ以上のファイルに記憶される電子地図である。
【００２６】
図２に示されるように、増補地図データ２４は、経路発見システム３０への入力として使用されうる。オペレーション中、経路発見システム３０は、プロセッサ読み取り可能な記憶媒体に増補地図データ２４を記憶する。経路発見システム３０のユーザは、出発点および行き先を指定し、これらは経路発見システム３０によってプロセッサ読み取り可能な記憶媒体に記憶される。経路発見システム３０は、増補地図データ２４を使用して指定された出発点から指定された行き先までの経路を見つけ出しうる。経路発見システム３０の出力は、経路３２である。経路３２は、プロセッサ読み取り可能な記憶媒体に記憶され、経路発見システムのユーザへ報告される。
【００２７】
近道発生器２２がどのようにして増補地図データ２４を生成するかについて説明する前に、電子地図の基本的な説明をする。一般的に、経路発見のために使用される電子地図は、グラフを含む。グラフは、ノードおよびリンクの集成である。ノードは、グラフ上で分岐点を意味する印である。例えば、ノードが十字路交差点の場合は、右折、左折、または直進するかの選択を行うべき場所を示す。リンクは、２つのノードの間の接続である。グラフにおけるノードＡからノードＢまでの経路は、ノードのリストに、このリスト中の各ノードから次のノードまでのリンクが存在する如くに記述されている。グラフにおいて、各リンクはそれに関連した単一の方向を有する。ノードの所定の対の間には、各方向において１つずつ、２つのリンクがありうる。
【００２８】
図３のグラフは、プロセッサ読取り可能記憶媒体に記憶された電子地図データ構造を象徴的に理解するのに使用される。即ち、プロセッサ読取り可能記憶媒体は、前述のグラフの画像を実際には記憶しない。そうではなく、データ構造が記憶される。各ノードに付いて、データ構造は、ノードの位置（例えば、緯度と経度）と、隣接するノード（1つのリンク経由で行けるノード）のリストと、隣接するノードへ行くのに関連する色々のコストとを記憶する。本発明は、記述したのとは異なる多くの好適なデータ構造とともに使用することができる。更に、本発明は、グラフと共に使用する必要はない。本発明は、地図データベース全体、他のネットワーク、又は他の任意の好適な情報のサブセットと共に使用することができる。更に、データ構造の1つ又はそれ以上のエントリは、データのクラスタにグループ分けすることができる。データのクラスタは、関連データのグループ分けである。クラスタは性能を改善するが、本発明はクラスタなしでも使用することができる。クラスタに関するより多くの情報は、「Method of Clustering Multi-Dimensional Related Data In A Computer Database By Combining The Two Vertices of a Graph Connected by An Edge Having the Highest Score」という題の米国特許第5,706,503号に見出すことができ、この特許をここに参照する。
【００２９】
図１に戻ると、近道発生器２２は、元の地図データ２０に作用し、増補地図データ２４を生じる。第1に、近道発生器は、元の地図データ２０に加える新しいリンクを作る。第２に、近道発生器は、元の地図データ２０に現存するノードについて、新しい優先順位レベルを作る。新しいリンクと該新しいノード優先順位レベルは、増補地図データ２４に記憶される。近道発生器２２は、一般的に、電子地図内を移動するのに何のコストも変化させない。
【００３０】
近道発生器２２により作られる２種類のリンクがある。作られる第１の種類のリンクは、２つのより高いリンク優先順位レベルのリンク間を移動するのに使用可能なより低いリンク優先順位レベルの道路上の経路である。作られる第２の種類のリンクは、幾つかのより低いリンク優先順位レベルのリンクをスキップするより高いリンク優先順位レベルのリンクである。両方の種類のリンクを、図４と５を参照して説明する。
【００３１】
図４は、電子地図の一部のグラフの例を示す。図４は、ノード２１０、２１２、２１４、２１６、２１８、２２０、２２２を示す。これらのノードを結合するのは、リンク２３０、２３２、２３４、２３６、２３８、２４０、２４２、２４４、２４６、２４８、２５０、２５２、２５４、２５６である。例示の目的として、リンク２４２、２４４、２４６は、リンク優先順位レベル５の第１のハイウェイであるとする。リンク２３４、２３６は、リンク優先順位レベル５の第２のハイウェイであるとする。更に、リンク２３０、２３２、２３８、２４０、２５０、２５２は、リンク優先順位レベル５の第３のハイウェイであるとする。最後に、リンク２４６、２４８は、リンク優先順位レベル３の幹線道路に沿った通路であるとする。例示の目的で、使用者がノード２２０から２１０へ移動したいとする。１つの従来のナビゲーションシステムは、ノード２２０から２１０へハイウェイに沿ってのみ移動する経路を決定するかもしれない。このような経路は、リンク２５４、２４２、２３６、２３２に沿った経路を含む。本発明の近道発生器は、使用者がリンク２５４、２４８、２３８、２３２に沿って移動するような近道を生じる。これを達成するため、近道発生器２２は、近道リンク２４８を生じる。典型的には、近道２４８は、幹線道路に沿った２つ又はそれ以上のリンク上の移動を表す複合リンクである。リンク優先順位レベル３の２つ又はそれ以上のリンクは、リンク優先順位レベル５の近道リンク２４８で置きかえられる。従って、近道リンク２４８は、近道発生器２２により生じるリンクの１つの例であり、２つのより高いレベルの道路の間を移動するのに使用可能なより低いレベルにおける道路上の経路を表す。即ち、車のドライバーは、リンク２５４、２４２、２３６、２３２上を移動するより、リンク２５４、２４８、２３８、２３２を移動することにより行き先２１０により速く到達する。
【００３２】
図５は、複合リンクの例を示す。図５は、４つのノード２７０、２７２、２７４、２７６を示す。リンク２８０は、ノード２７０をノード２７２に接続する。リンク２８２は、ノード２７２をノード２７４に接続する。リンク２８４は、ノード２７２をノード２７４に接続する。この例では、リンク２８０、２８２、２８４は、全て同じリンク優先順位レベルの終端ノードを有する。リンクの終端ノードは、各リンクが終了するノードである。例えば、リンク２８４の終端ノードは、ノード２７６である。
【００３３】
近道発生器２２は、ノード２７０をノード２７６に結合する新しい複合リンク２８８を作っても良い。リンク２８８に関連付けられた終端ノードのリンク優先順位レベルは、リンク２８０と２８２の終端ノードのリンク優先順位レベルより高い。更に、ノード２７０と２７６のリンク優先順位レベルは、ノード２７２と２７４のリンク優先順位レベルより高い。リンク２８８は、近道発生器２２により作られる複合リンクの例である。
【００３４】
近道発生器２２が近道をどう発見するかを説明する前に、例示の経路発見システム３０が、出発点から行き先への経路をどのようにして求めるかを理解するのは有用である。
【００３５】
図６は、出発点から行き先への経路を求める方法を説明するフローチャートである。図６の方法は、公知の多くの経路発見方法の１例である。本発明と共に経路を発見する他の方法を使用することもできる。ステップ３０２で、システムは、経路発見探査を初期化する。即ち、システムは、経路の出発点と行き先を記憶し、２つの待ち行列、出発点優先順位待ち行列と行き先優先順位待ち行列を設定する。出発点優先順位待ち行列は、ノードの整列したリスト（出発点からその各々への経路は分かっている）と、各ノードへのキーからなる。待ち行列はキーに従ってソートされる。キーを求めるのに色々の他の方法がある。１つの方法では、キーは、出発点からノードへ移動する際の既知の最低コストである。他のキーは、出発点からノードへの最低コストと、ノードから行き先へ移動する予測コストとの合計を含む。この方法に適したノードから行き先への移動コストを予測する方法は色々ある。１つの例は、直線距離に単位距離当たりの予測コストをかける方法である。即ち、ノードとリンクを無視し、ノードと行き先の間の物理的距離を求め、その距離に単位距離当たりの予測コストをかけることである。
【００３６】
行き先優先順位待ち行列は、ノードを整列したリスト（その各々から行き先への経路は分かっている）と、各ノードへのキーからなる。待ち行列は、キーに従ってソートされる。行き先キーを求めるのに色々の他の方法がある。１つの方法では、ノードから行き先への分かっている最低コストの経路を使用する方法を含む。他のキーは、ノードから行き先へ移動する最低コストと、出発点からノードへの予測コストとの合計を含む。残りのコストを予測することを利用する出発点優先順位待ち行列について上述したキーは、出発点から行き先の方向へ偏った探査を生じる。同様に、行き先からの探査は、出発点の方向に偏っている。キーを計算する他の方法は、本発明の範囲内にある。
【００３７】
さらに、システムは出発点探査済ノードリスト及び行き先探査済ノードリストを設定する。出発点探査済ノードリストは出発点からの経路が知られているすべてのノードのリスト、出発点から各ノードへ移動するための最低コスト、及び最低コストの経路に沿った以前のノードを維持する。行き先探査済ノードリストは行き先への経路が知られている各ノードの名前、各ノードから行き先へ移動するための既知の最低コスト、及びその最低コストで行き先へ経路に沿った次のノードの識別子を記憶する。初期化段階３０２が完了した後、出発点の優先順位待ち行列及び出発点探査済ノードリストは出発点を含み、行き先優先順位待ち行列及び行き先探査済ノードリストは行き先を含んでいる。
【００３８】
一旦、システムが初期化されると、ステップ３０４において、システムは規則に従って待ち行列を選択する。本発明に適切な待ち行列を選ぶ多くの規則がある。１つのシステムでは、最小キーと関連する要素を含む待ち行列が選択される。この際、複数の待ち行列が選択されれば、いずれかを選ぶ任意の決定法が使用される。別のシステムでは、最小数の要素を含む待ち行列が選択される。待ち行列を選択するための規則の他の例は、出発点待ち行列と行き先待ち行列とを交替することを含む。即ち、一定回数の反復処理のために（又は一定期間中）出発点待ち行列を選択し、一定回数の反復処理のために行き先待ち行列に切換え、一定回数の反復処理のために出発点待ち行列に切換え戻すこと等を含んでいる。待ち行列はキーによりソートされるから、最小キーのノードは待ち行列の先頭にあるだろう。このノードは「先頭ノード」と呼ばれる。
【００３９】
ステップ３０６では、システムは選択された待ち行列の先頭ノードに対して隣接ノードであるすべてのノードを探し、それらのノードの１つを選択する。システムはちょうど作動開始したところであるから、出発点優先待ち行列のノードだけが出発点である。隣接ノードは、他のノードを通ることなく先頭ノードへ移動又は先頭ノードから移動することができるノードである。ステップ３０８では、システムは、隣接ノードのための探査済ノードリスト又は選択された優先待ち行列に既知のより低いコストがあるか否かを決定する。すなわち、システムは隣接ノードと先頭ノード間の移動コストを決定し、先頭ノードのために既に知られているコストにそのコストを追加し、合計のコストを得る。そのとき探査済ノードリストに既知のより低いコストがない場合、ステップ３１０において、システムは探査済ノードリスト及び優先待ち行列を編集し、隣接ノード及び合計のコストを追加する。既知のより低いコストがある場合、その後、探査済ノードリストは編集されず、システムをステップ３０６にループバックする。ステップ３１０の後、その方法はステップ３０６にループバックし、追加の隣接ノードが探査されないか否かを決定する。隣接ノードのすべてが探査された場合、その後、その方法はステップ３１２に進み、先頭ノードは優先待ち行列から取り除かれる。
【００４０】
ステップ３１４では、システムは停止状態が起こったか否かを決定する。本発明に適した多くの停止状態がある。適当な停止状態の１つの例は、同じノードが出発点優先待ち行列と行き先優先待ち行列の両方の先頭ノードであった時に停止することである。別の停止状態は、行き先優先待ち行列の先頭ノードから行き先への移動コストを加えた、出発点優先待ち行列の出発点から先頭ノードへ移動するコストが、最良の接続コストの全体コストより高いか又はそれに等しい時に停止することを含んでいる。接続ノードは行き先探査済ノードリスト及び出発点探査済ノードリストの両方に現れるノードである。接続ノードの全体コストは、接続ノードから行き先へのコストと出発点から接続ノードへのコストの和である。最良の接続ノードは最低の全体コストの接続ノードである。停止条件にまだ合致しない場合、システムはステップ３０４に進み、他の待ち行列を選択する。停止条件に合致した場合、システムはステップ３１６で経路を作る。ステップ３１８で、システムは経路を報告する。経路を報告することは、経路を示す地図を表示し、地図上で強調された経路の地図を表示し、方向指示を供給し、経路を説明する聴覚出力を供給し、経路を説明するデータのファイルを作り出すと共に渡し、経路を説明するデータにポインタを渡し、機能呼出しに応じて経路を説明するデータを渡すこと等を含んでいる。
【００４１】
経路を構築するステップ（ステップ３１６）は以下の通りである。規則は幾つかの接続ノードを選択する。そのような規則の１つは最良の接続ノードを選択することである。選択された接続ノードＫは出発点探査済ノードリストで調べられ、出発点からの経路上にある前のノードＰ1が見つけられる。Ｐ1が出発点でない場合には、その後、Ｐ1は探査済ノードリストで調べられ、前のノードＰ1が見つけられる。これは出発点に到着するまで続く。出発点がノードＰLとして到着されたと仮定しよう。同様に、Ｋは行き先探査済ノードリストで調べられ、次のノードＮ1が見つけられる。もしＮ1が行き先でない場合には、その後、Ｎ1は探査済ノードリストで調べられる。これは行き先に到着するまで続く。行き先がノードＮMとして到着されると仮定しよう。この点で、出発点から行き先への経路が分かった。それは、ＰL（出発点）からＰL-1まで、ＰL-2まで、…、Ｐ2まで、Ｐ1まで、Ｋまで、Ｎ1まで、…、ＮM-1まで、ＮM（行き先）までの経路である。経路発見についてのさらなる情報は、１９９７年２月２０日に出願された No.08/802,733の Richard Frederick Poppen、Rodney Jude Fernandez、及びJames Laurence Buxtonによる経路発見計算のためのキャッシング、及び１９９８年２月１３日に出願された No.09/023,504の Koji Amakawa、及びEdward Joseph Suranyiによる経路発見のためのシステムで見出すことができる。
【００４２】
上述したように、図６の処理は異なる優先順位レベルで行うことができる。例えば、道路は表１に示されているように異なる優先順位レベルに分割可能であり、経路発見処理は各レベル毎を使用可能である。
【００４３】
図７は近道発生器２２の動作を説明するフローチャートである。図７の第１ステップ３４８で初期化が行われる。この初期化のステップは出発点の地図データ２０を読み出すと共に記憶することを含んでいる。記憶された地図データはノード、リンク、そして、幾つかの実施例では、ノード及び又はリンクのための優先順位レベルを含んでいる。ステップ３５０では、近道発生器２２は各探査レベルで動作する。上述したように、道路網は、道路の種別に応じて、異なる優先順位レベルに分割される。近道発生器２２の動作はレベル毎に行うことができる。最初、ステップ３５０が実行された時は、探査レベルはレベル１である。ある探査レベルで動作後、近道発生器２２はより高い探査レベルがあるか否か、換言すると、現在の探査レベルが最高の探査レベル（例えば、レベル５）か否か、換言すると、現在の探査レベルが最高の探査レベル(例えば、レベル５)か否かを決定する（ステップ３５２）。より高い探査レベルがある場合には、その後、探査レベルはステップ３５４で次のレベルに変更される。したがって、ステップ３５０で、動作される現在の探査レベルがレベル１である場合には、その後、探査レベルはレベル２に変更され、システムはステップ３５０にループバックし、レベル２で動作する。レベル２での動作後、システムはステップ３５０〜３５４を通ってループし続け、レベル３、レベル４及びレベル５で動作する。（５レベルあると仮定すると）レベル５で動作後、ステップ３５２でシステムは動作するレベルがもうないと決定し、近道発生器２２は発見された近道のリンク及び該リンクのリンク優先順位レベルを地図データに追加することを含むステップ３５６に進む。本質的に、ステップ３５６は増補地図データ２４を作るステップを備えている。
【００４４】
図８Ａ及び図８Ｂは、図７のステップ３５０（ある探査レベルで動作）を記載するフローチャートを示す。すなわち、図８Ａ及び図８Ｂの方法は、各々の探査レベルに対して実施される。したがって、もし、５つの探査レベルがあるならば、図８Ａ及び図８Ｂの方法は５回実施される。図８Ａ及び図８Ｂはステップ４００−４４２を有する。図８Ａ及び図８Ｂの方法は探査レベル０に対しては実施されない。探査レベル２−５に対して、本方法はステップ４００で開始される。探査レベル１に対して、本方法はステップ４２２で開始される。
【００４５】
ステップ４００は現在の探査レベルにあるか、またはより高い、電子地図のデータベースにおける全てのノードを探すステップ及びこれらのノードをソートするステップを含む。これらのノードはソートされて、Ｋ−Ｄツリーを形成する。このソートは、地理的に近いノードはリストにおいて通常近くなるようにノードの直列的なリストを形成する。地図データベースにおける各々のリストとノードはリンク優先順位レベル及びノード優先順位レベルと呼ばれる属性を有している。リンク優先順位レベルは、どんな優先順位レベルのときにリンクが使用可能であるかを示している。図７の方法の開始のときに、各々に対するリンク優先順位レベルは、リンクと関連している道路の種別に基づく前述の優先順位レベルである。例外として、道路の種別が如何なる物であっても、リンクがＵターン経路に関するものであり、元のノードに戻る場合には、該リンクに、０の初期のリンク優先順位レベルが付けられる。更に、ノードの初期のノード優先順位レベルはノードに接続するとリンクのリンク優先順位レベルと同じである。ステップ４０２において、近道発生器２２は、処理すべきノードが更にあるか否かを判断する。もし、処理するノードが最早ないならば、本方法は、ステップ４２０（図８Ｂにある）へループする。もし、処理する更なるノードがあるなら、本方法はステップ４０４へループする。第１回目のステップ４０２がステップ４００の後に実行される際、処理するための多くのノードがあり、したがって、近道発生器２２がステップ４０４へ進められることが予期される。
【００４６】
ステップ４０４において、近道発生器２２は、ステップ４００で見出されるノードの１つを取り上げる。ステップ４０６に於いて、近道発生器２２は、ステップ４０４において取り上げられるノードから外へ向かって探査する。ステップ４０６における探査のステップは、図６の経路発見プロセスの変更バージョンである。幾つかの例外は、調査が現在の探査レベルと等しいか、現在の探査レベル以上か、または現在の探査レベルより１低いリンク優先順位レベルを伴うリンクに沿って探査することができるだけである。
【００４７】
図９は、図８Ａのステップ４０６（採択ノードから探査）を実現するための方法を説明するフローチャートである。図９のプロセスは、出発点から行き先までの経路を見つけ出さない。むしろ、図９の方法は、出発点から外へ向かって探査する。ステップ５００において、プロセスが開始される。すなわち、出発点優先順位待ち行列および出発点探査済ノードリストが設定される。図９のプロセスにおいて、探査済ノードリストおよび優先順位待ち行列は３つの追加のフィールド、すなわち使用可能度フィールド、同じ道路を逆方向に移動して同じノードに戻ることを示すＵターンフィールドおよび１つ前のノードが出発点か否かを示す先行フィールドを有する。もし、Ｕターンフィールドが設定されるなら（例えば、論理レベル１を格納する）、Ｕターンフィールドと関連するノードを含む経路はＵターンを有する。もし、特定のノードに対するＵターンフィールドが設定されないなら、そのノードを含む経路はＵターンを含まない。
【００４８】
先行フィールドは特定のノードへの最良の経路が出発点ノードからか、または他の先行ノードからであるかを信号として送るために用いられる。先行フィールドがゼロに等しいとき、特定ノードへの最良の経路は出発点ノードからである。先行フィールドが１に等しいとき（例えば、先行フィールドが設定される）、特定ノードへの最良の経路は他の先行ノードからである。先行ノードは３つの基準に合うノードである。第１の基準は、先行ノードから出発点ノードへの経路を示すリンクがあることである。第２の基準は、先行ノードから出発点ノード以外のノードへリンクがあることである。第３の基準は、出発点ノードへのリンク（第１の基準）および他のノードへのリンク（第２の基準）が現在の探査レベルか、現在の探査レベルより１つ低いか、現在の探査レベルより高いリンク優先順位レベルを持たなければならないことである。ステップ５００は全ての先行ノードを優先順位待ち行列および探査済ノードリストに先行フィールドを伴って設置するステップを有する。出発点は先行フィールドを有していない。
【００４９】
ステップ５０２において、各々のノードに対するノード使用可能度フィールドの値が最初に最大に設定される。ステップ５０２が完了したのち、図９のプロセスはステップ５０４へ進み、他の適切な隣接ノードがあるかを判断する。ステップ５０４は、適切な隣接ノードが、現在の探査レベルに等しいか、現在の探査レベルより１低いか、現在の探査レベルより上のリンク優先順位レベル有するリンクによって通過できる隣接ノードのみを含む点を除いてステップ３０６と同様である。もし、他の適切な隣接ノードがあるなら、プロセスはステップ５０６へ続き、そこで適切な隣接ノードの１つが取り上げられ、そして取り上げられた適切な隣接ノードが探査済ノードリストにあるか否かを判断する。もし、それが探査済ノードリストにあるなら、本方法は、ステップ５１０へ進みノードが探査済ノードリストにより高いコストを有するかを判断する。もし、それがより高いコストを有しているなら、本方法はステップ５１２へ進み、探査済ノードリストを編集し、新しいコストと新しい前のノードを探査済ノードリストへ加え、優先順位待ち行列がそれにより編集され、必要なら、Ｕターンフィールドが更新される。すなわち、もし、探査中の現在のノードへの移動がＵターンを必要とするなら、ＵターンフィールドはＵターンを示すために設定されなければならない。Ｕターンフィールドの使用が従来技術のシステムから改善を示す。ステップ５１２に於いて、もし、前のノード（探査済ノードリストにある）が１に設定された先行フィールドを有するなら、探査中の現在のノードに対する先行フィールドが１に設定される。ステップ５１２の後、プロセスはステップ５１４へ進む。もし、ステップ５１０において、探査済ノードリストにより高いコストがないことが判断されるなら、プロセスはステップ５１４を続ける。ステップ５１４において、近道発生器２２は探査中の現在の隣接ノードのノード使用可能度をチェックする（図１０を参照して以下に説明する）。ステップ５１４の後、プロセスはステップ５０４へ戻る。もし、ステップ５０６において、探査中の隣接ノードが探査済ノードリストになかったことが判断されたなら、本方法は、機能がステップ５１２と同じであるステップ５０８へ進む。このステップは、探査済ノードリストを編集し、優先順位待ち行列を編集し、もし必要なら、Ｕターンフィールドを更新し、そしてもし必要なら、先行フィールドを更新することを含む。ステップ５０８の後、本方法は、ステップ５０４へ戻る。
【００５０】
適切なリンク優先順位レベルのリンクによって隣接ノードに進められるかを判断することに加えて、ステップ５０４はノードが出発点の閾値コスト内にあるかも判断する。現在の調査に対する出発点は、図８Ａのステップ５０４において最も最近取り上げられたノードである。したがって、近道発生器２２は出発点から現在考慮中の隣接ノードへいくコストを判断する。このコストが閾値より小さいと判断されると、現在考慮中の隣接ノードは、適切な隣接ノードとして考えられる。閾値はリンク優先順位レベルによって変わる。テーブル４は探査レベル２−５用の閾値の例を提供する。
【００５１】
テーブル４
探査レベル 停止閾値
２ ３００秒
３ ９００秒
４ １／２時間
５ １時間
隣接ノードとみなされる現在考慮中の隣接ノードが閾値内にない場合には、その隣接ノードは適当な隣接ノードではない。従って、ステップ５０４のテストは、ノードが隣接ノードであるかどうか、そのノードに適当なリンク優先順位レベルのリンクが到達できるかどうか及び閾値内にあるかどうかである。
【００５２】
ステップ５０４において適当な隣接ノードがそれ以上ない場合には、システムがステップ５２０に進む。ステップ５２０は、優先順位待ち行列から先頭のノードを除去することを含む。ステップ５２２において、近道発生器２２は、優先順位待ち行列が空か否かを決定する。優先順位待ち行列が空でない場合には、図１０の方法は、ステップ５０４にループバックして続行される。
【００５３】
図１０は、図９のステップ５１４（使用可能度のチェック）を実施する方法を記載するフローチャートである。図１０の方法は、図９の探査時において探査中のノードが既に探査済ノードリストにある場合に実行される。ステップ５５０において、近道発生器２２は、探査中のノードに対する２つの経路のどちらが使用不可能経路であるか否かを決定する。すなわち、ノードは既に探査済ノードリストにあるので、そのノードに到達する経路は２つある。第１の経路は、（ステップ５１２より前の）探査済ノードリストにより指示された経路を含む。第２の経路は、優先順位待ち行列の現在の先頭ノードを介して探査中の現在の隣接ノードに到達する経路を含む。より大きなコストを有する経路が使用不可能経路とされる。
【００５４】
ステップ５５２において、近道発生器２２は、使用不可能経路に沿って１リンクだけ、戻って、探査中の現在の隣接ノードより一つだけ前のノードへ戻る。ステップ５５４において、近道発生器２２は、ステップ５５２で見つけられたノードを出る全ての前進リンクを考察する。前進リンクは、ノードを出る方向のリンクである。ステップ５５２で見つけられたノードからの前進リンクは、それが、より低コストを有する探査済ノードリストに既にあるノードに通じ、そのノードの前のノードがステップ５５２で見つけられたノード以外のノードである場合に、使用不可能であるとされる。探査中のノードからの前進リンクの少なくとも１つが使用不可能でない場合には、図１０のプロセスは完了する。前進リンクが全て使用不可能である場合には、近道発生器２２はステップ５５６に進み、ステップ５５２で見つけられたノードの使用可能度をゼロにリセットする。ステップ５５８において、近道発生器２２は、その使用可能度がゼロにリセットされたばかりのノードから１リンクだけ前のノードに戻る。ステップ５６０において、近道発生器２２は、ステップ５５８において戻ったノードを出る各前進リンクのリンク使用可能度を決定する。リンク使用可能度は、リンクのコストの逆数とリンクの標的ノードの使用可能度の和である。ステップ５５８において到達したノードの使用可能度フィールドは、複数ある前進リンクの内のリンク使用可能度に変更される。従って、移動できるリンクのいずれかが最大の使用可能度を有する場合には、ノードの使用可能度は最大にとどまる。ステップ５５８において戻されたノードが、その使用可能度がステップ５６２において変更された使用可能度を有する場合には、システムは、ステップ５５８にループバックし、ステップ５５８〜５６４を繰返す。これらのステップを設けた意味は、１つのノードだけが複数の使用不可能ノードに通じている場合には、そのノードもまた使用不可能であるためである。ステップ５６２においてノードの使用可能度が変更されなかった場合には、図１０のプロセスは完了する。一般に、従来技術の近道発生器は、別の経路によってより速い方法で移動できる場所に通じているので使用可能でなかった近道又は合成リンクを発見した。従って、図１０のステップは、より有効で且つより使用可能度のある近道を発見することにより従来技術に比べて大きな改良を提供する。
【００５５】
図８Ａのステップ４０６を完了した後、近道発生器２２は、探査済ノードリストを記憶する。ステップ４０８において、探査済ノードリストの１つのノードが選択される。ステップ４１０において、そのノードのノード優先順位レベルが現在の探査レベルにあるか又はより高いか否かが決定される。そのノードのノード優先順位レベルが現在の探査レベルにない場合には、その方法はステップ４１８にループする。ノードが現在の探査レベルにあるか又はより高い場合には、ステップ４１２において、システムが、探査中のノードについて先行フィールド又はＵ−ターンフィールドが設定されているか否かを決定する。先行フィールド又はＵ−ターンフィールドのいずれかが設定されている場合には、その方法はステップ４１８にループする。先行フィールド又はＵ−ターンフィールドのいずれも設定されていない場合には、そのシステムはステップ４１４にループして、ノード使用可能度が閾値よりも低いか否かを決定する。ノード使用可能度が閾値よりも小さくない場合には、システムは後戻りステップ（ステップ４１６）を実行する。後戻りした後、システムは、探査済ノードリストにまだノードが残されているか否かを決定する。まだノードが残されている場合には、システムはステップ４０８にループバックして探査済ノードリストの別のノードを選択する。探査済ノードリストにもうノードがない場合には、システムは、ステップ４０２にループバックして、ステップ４００において識別されたノードの組から探査するためのノードがまだあるか否かを決定する。ステップ４１４は、ステップ４０６の最新の繰り返しについて使用可能でないノードにおいて終端するリンクについての新しいリンク優先順位レベルの生成を防止する。
【００５６】
図１１は、図８Ａのステップ４１６（後戻り）のプロセスを説明するフローチャートである。図１１のプロセスは、ステップ４０８〜４１４において選択されているノードからスタートする。ステップ５７６において、近道発生器２２は、該選択されているノードから１リンクだけ戻って探査する。すなわち、探査済ノードリストには、該選択されているノードに到達する経路に沿って前のノードを指示する前のフィールドがある。ステップ５７６は、その前のノードに戻って探査することを含む。ステップ５７８において、前のノードに到達するように探査されたリンクのコストが出発点又は行き先のリンク閾値内にあるか否かをテストする。それが出発点又は行き先のリンク閾値内にある場合には、図１１の方法は、ステップ５８４にループする。リンクが出発点又は行き先のリンク閾値内にない場合には、方法は、ステップ５８０に進む。
【００５７】
ステップ５８０において、近道発生器２２は、前のノードに到達する探査リンクが現在の探査レベルよりも１レベル下のリンク優先順位レベルを有するか否かをテストする。有する場合には、そのリンクについて新しいリンク優先順位レベルが発生され古いリンク優先順位レベルと置き換えられる。ステップ５８２の後、システムはステップ５７６で探査されたノードが最新の探査の出発点であるか否かを決定する。出発点でない場合には、図１２の方法は、ステップ５７６にループバックする。出発点である場合には、図１２の方法は、完了する。ステップ５８０において、探査されたリンクが現在の探査レベルより１レベル下のリンク優先順位レベルでない場合には、その方法は、ステップ５８４にループする。図１２の方法は、或るリンクを使用促進するプロセスと考えてもよい。
【００５８】
図８Ａに戻って、ステップ４０２において識別されたノードが全て探査されたことが決定された場合には、図８Ａ〜８Ｂのプロセスはステップ４２０に進む。ステップ４２０において、近道発生器２２は、ステップ４００において選択された各ノードについてノード優先順位レベルを決定する。図１２Ａは、選択された各ノード（ステップ４２０）についてノード優先順位レベルを決定するプロセスを示すフローチャートである。図１２Ａのプロセスは、ステップ４００において識別された各ノードについて実行される。
【００５９】
ステップ６００において、近道発生器２２は、探査中の現在のノードについて全ての前進リンクを見る。図１２Ｂは、５つの前進リンクを有するノード６４０を示す。図１２Ｃは、３つの前進リンクを有するノード６６０を示す。各前進リンクに隣接する番号は、各リンクについてのリンク優先順位レベルを表す。ステップ６０２において、近道発生器２２は、前進リンクが選択される最高のリンク優先順位レベルを決定する。ステップ６０２のために、与えられたリンク優先順位レベルにおけるリンクも、その与えられたリンク優先順位レベルより下の優先順位レベルのどれかであるとみなされてもよい。例えば、図１２Ｂを見ると、一番上の前方レベルは、４のリンク優先順位レベルである。そのリンクもまたレベル３、レベル２又はレベル１とみなされてもよい。図１２Ｂを見ると、レベル４における２つの前進リンクの選択があり、レベル３における２つの前進リンクの選択があり、レベル２における４つの前進リンクの選択があり、及び、レベル１における５つの前進リンクの選択がある。前進リンクの選択がある最高のリンク優先順位レベルは、レベル４である。
【００６０】
図１２Ｃを参照すると、リンク優先順位レベル１、２及び３の前進リンクがある。従って、リンク優先順位レベル１で３つ及びリンク優先順位レベル２で２つのリンクの選択がある。リンク優先順位レベル３のリンクは１つしかない。それゆえ、前進リンクの選択がある最高レベルは、リンク優先順位レベル２である。
【００６１】
ステップ６０４において、探査中のノードが、ステップ６０２で決定されたリンク最高選択レベルに等しい「決定されたノード優先順位レベル」に割当てられる。ステップ６０６において、ステップ６０４で割当てられた「決定されたノード優先順位レベル」が、現在の探査レベル及び上記ノードに関連する道路のリンク優先順位レベルと比較される。ステップ６０４で割当てられた決定されたノード優先順位レベルが現在の探査レベルより低い場合、あるいは、上記決定されたノード優先順位レベルが上記ノードに関連する道路の優先順位レベルより高い場合、処理はステップ６０８に進み、そうでない場合には、処理はステップ６１０に進む。ステップ６０８において、該ノードに対する実際のノード優先順位レベルが、ステップ６０４において上記決定されたノード優先順位レベルに設定される。この実際のノード優先順位レベルは、プロセッサで読取り可能な記憶媒体の一時ファイルに記憶される。ステップ６１０において、最初にノードに関連する道路の優先順位レベルに等しく設定された該ノードの実際の優先順位レベルは、変更されない。この実際のノード優先順位レベルも、上記プロセッサ読取り可能な記憶媒体に記憶される。
【００６２】
図８Ｂのステップ４２０の完了後、近道生成器２２がステップ４２２を実行して、現在の探査レベル又はそれより高いレベルの全ノードを見つけて、ステップ４００で行ったソートと同様にそれらのノードを再度ソートする。ステップ４２４において、近道生成器２２は、ステップ４２２で識別されたノードの１つを選択する。ステップ４２６において、近道生成器２２は、現在の探査レベル又はそれより高いレベルのリンク優先順位を持つリンクに到達できる、ステップ４２４で選択されたノードに隣接するノードの全てを見つける。ステップ４２８において、それら隣接するものの１つが選択される。ステップ４３０において、近道生成器２２は、選択された上記隣接ノードからの前進リンクを探査して、現在の探査レベルまたはそれより高いレベルのリンクの選択が生じるまで更に前進リンクの探査を続ける。この選択に到達すると、複合リンクがステップ４３２で作られる。この複合リンクは、ステップ４２４で選択されたノードから始まり、リンクの選択がある場所（ステップ４３０参照）で終わる。
【００６３】
ステップ４３４において、システムは、「進入ノード」について追加の複合リンクを生成する。近道生成器２２は、ステップ４３２で作られた複合リンクの開始点である交差点に移動することを示すノードの全てを考察する。交差点に入るノードは、「進入ノード」と記される。この進入ノードから、ステップ４３２で作られた複合リンクの終点のノードへ至るリンクが追加される。この追加リンクは、ステップ４３４で作られた追加の複合リンクである。もし進入ノードの優先順位レベルがゼロであれば、ステップ４３４の新たな複合リンク生成を開始するために１リンクだけ後戻りする。
【００６４】
ステップ４３６において、ステップ４３２及び４３４で作られた複合リンクは、プロセッサ読取り可能な記憶媒体に記憶される。１実施例では、ステップ４３６の複合リンクとステップ６０８の新たなノード優先順位レベルとは、一時ファイルに記憶され、且つ、ステップ３５６の増補地図データ２４に永久的に（又は半永久的に）記憶される。別の実施例では、ステップ３５６を含まず、ステップ４３６と６０８とが、増補地図データ２４に上記新たなリンク及びリンク優先順位レベルを記憶する処理を含んでいる。
【００６５】
図８Ｂのステップ４４０において、近道生成器２２は、更に探査すべき隣接ノード（ステップ４２６参照）があるか否かを決定する。もし、更に探査すべき隣接ノードがあるならば、プロセスはステップ４２８へループする。もし、更に探査すべき隣接ノードがそれ以上ないならば、プロセスはステップ４４２へループして、探査すべきノード（ステップ４２２で見つかったノードの中のノード）があるか否かを決定する。更に探査すべきノードがない場合、図８Ａ及び８Ｂのプロセスは完了する。更に探査すべきノードがある場合、プロセスはステップ４２４へ戻るようにループする。
【００６６】
理解されるように、近道生成器２２は、各レベル毎のプロセスで作業する。近道生成器２２は、レベル１の道路を使用して、レベル２での全ての近道を見つけ出す。次に、近道生成器２２は、レベル３へ進行し、レベル２の道路（前のレベルを含む）を使用して、レベル３での全ての近道を見つける等。
【００６７】
本発明の近道生成器は、ハードウェアで実施することもできるし、ソフトウェアで実施することもできるし、ハードウェアとソフトウェアとで実施することもできる。１つの実施態様では、システムは、本書に記述した機能を実行できるプロセッサ命令を含む専用のプロセッサで構成できる。本書に記述した機能を実行するように、回路を開発してもよい。１つの実施例では、本発明は、ナビゲーションシステムの一部となる。ナビゲーションシステムの例が、米国特許第４，７９６，１５１号明細書、米国特許第４，９１４，６０５号明細書、米国特許第５，３１１，１９５号明細書、米国特許出願第０８／７４７，１６１号明細書に記載されており、これらの明細書に内容は、本願の参照文献として組入れられる。別の実施態様においては、本発明は、コンピュータシステムと一緒に使用するための命令を実行できる複数のプロセッサを含んでいる。コンピュータシステムにローディングする前に、ソフトウェアが、コンピュータで読取り可能な媒体（例えば、磁気フロッピー（登録商標）ディスクや磁気テープやＣＤ−ＲＯＭ）に存在する。
【００６８】
図１３は、近道発生装置および／または、経路発見システムを実行するのに使用することができるコンピュータシステムのハイレベルブロックダイヤグラムを図示したものである。図１３のコンピュータシステムはプロセッサユニット７１２およびメインメモリ７１４を備えている。プロセッサユニット７１２は、単一のマイクロプロセッサを含むことができ、あるいは、多数のプロセッサシステムとしてのコンピュータシステムを形成するための複数のマイクロプロセッサを含むことができる。メインメモリ７１４は、プロセッサユニット７１２によって実行される命令およびデータを一部、格納する。本発明のシステムが、全体的にまたは、部分的にソフトウェアで実行される場合には、メインメモリ７１４は動作中に実行可能なコードを記憶する。メインメモリ７１４ダイナミックランダムアクセスメモリ（ＤＲＡＭ）および高速キャッシュメモリのバンクを備えることができる。
【００６９】
図１３のシステムは、さらに大容量記憶装置７１６、周辺機器７１８、入力装置７２０、可搬式記憶媒体ドライブ７２２、グラフィックサブシステム７２４および出力ディスプレイ７２６を備える。簡単化するために、図１３に示される構成要素は、単一のバス７２８を介して接続されているように描かれている。しかし、構成物は、１つあるいはそれ以上の伝送手段を介して接続することができる。たとえば、プロセッサ７１２およびメインメモリ７１４はローカルマイクロプロセッサバスを介して接続することができる。そして、大容量記憶装置７１６、周辺機器７１８、可搬式記憶媒体ドライブ７２２およびグラフィックサブシステム７２４は、１つ以上の入出力（Ｉ／Ｏ）バスを介して接続することができる。大容量記憶装置７１６は、磁気ディスクドライブあるいは光学的ディスクドライブで実行することができるものであるが、プロセッサユニット７１２によって使用されるデータおよび命令を格納するための不揮発性記憶装置である。１つの実施例においては、大容量記憶装置７１６は、メインメモリ７１４へのローディングの目的で、本発明を実行するシステムソフトウェアを格納する。可搬式記憶媒体ドライブ７２２は、可搬式不揮発性記憶媒体、例えばフロッピー（登録商標）ディスク、に関連して動作するものであって、図１３のコンピュータシステムに対してデータおよびコードの入出力を行う。一つの実施例では、本発明を実行するためのシステムソフトウェアは、そのような可搬式媒体に記憶されており、該可搬式記憶媒体ドライブ７２２を介してコンピュータシステムに入力される。周辺機器７１８は、任意の形式のコンピュータ支持装置、例えば、入出力（Ｉ／Ｏ）インターフェース、を備えることができ、該コンピュータシステムに付加的な機能を追加する。たとえば、周辺機器７１８は、ネットワーク、モデム、等に対してコンピュータシステムを介在させるためのネットワークインターフェースカードを備えることができる。 入力装置７２０は、ユーザーインターフェースの一部を与える。入力装置７２０は、英数字およびその他のキー情報を入力するための英数字キーパッド、あるいはマウス、トラックボール、スタイラス、あるいはカーソル方向キーといった、ポインティングデバイスを備えることができる。テクスチャおよびグラフィック情報を表示するために、図１３のコンピュータシステムは、グラフィックサブシステム７２４および出力ディスプレイ７２６を備える。出力ディスプレイ７２６陰極線管（ＣＲＴ）ディスプレイ、液晶ディスプレイ（ＬＣＤ）あるいはその他の適当なディスプレイ装置を備えることができる。グラフィックサブシステム７２４は、テクスチャおよびグラフィカル情報を受信し、ディスプレイ７２６に出力するための情報を処理する。出力装置７２６は、経路発見判断の結果を報告し、地図を表示し、方向を表し、情報確認を表示し、および／または、ユーザーインターフェースの一部であるその他の情報を表示するのに使用することができる。図１３のシステムは、または、オーディオシステム７２８を備えており、このオーディオシステムは、マイクロフォンを備える。１つの実施例では、オーディオシステム７２８は、マイクロフォンからのオーディオ信号を受信するサウンドカードを備える。さらに、図１３のシステムは、出力装置７３２を備えている。適当な出力装置の例は、スピーカー、プリンター等を含む。
【００７０】
図１３のコンピュータシステムに含まれる構成要素は、汎用コンピュータシステムで見られる通常のものであり、周知のコンピュータ構成要素の広いカテゴリを表すものである。このように、図１３のコンピュータシステムはパソコン、ワークステーション、ミニコンピュータ、メインフレームコンピュータ等とすることができる。コンピュータはまた異なるバス形態、ネットワークプラットフォーム、マルチプロセッサプラットフォーム等を備えることができる。さまざまなオペレーティングシステムはユニックス(登録商標)、ウィンドウズ(登録商標)、マッキントッシュ(登録商標)ＯＳおよび他の適当なオペレーティングシステムを含んで使用することができる。
【００７１】
上記の本発明の詳細な記述は、説明および記述目的で提出されているものである。本発明を消尽し、あるいは開示された正確な形態に限定するつもりはなく、明らかに多くの修正および変形が上記の教示に照らして可能である。記載された説明は、本発明の原理を最も良く説明するために選択されたものであり、それによってその実質的な応用は、当業者がさまざまな実施形態で、考慮した特定の用途に適合するようにさまざまな修正を行って、最適に活用することを可能にするものである。本発明の範囲は添付の特許請求の範囲の記載によって画定されることを意図するものである。
【特許請求の範囲】
【請求項１】
電子地図に近道を追加する方法において、
上記電子地図のノード及びリンクの集合体を記憶し、該リンクにはリンク優先順位レベルが関連付けされ、
プロセッサを用いて上記ノードから外方に探査し、この探査段階は、どのノードが有用でないか決定することを含み、
上記探査中に通過されそして有用でないと決定されたノードで終了しない上記リンクの集合体に対して新たなリンク優先順位レベルを形成し、
上記新たなリンク優先順位レベルをもつ１つ以上のリンクを含む複合リンクを構築し、そして
上記複合リンクを上記電子地図に記憶し、上記複合リンクが上記近道を表わすことを特徴とする方法。
【請求項２】
上記ノードに対するノード優先順位レベルを上記電子地図に記憶し、
新たなリンク優先順位レベルを有する１つ以上の上記リンクにより接続された上記ノードの集合体に対して新たなノード優先順位レベルを形成し、そして
上記新たなノード優先順位レベルを上記電子地図に記憶する、
という段階を更に含む請求項１に記載の方法。
【請求項３】
上記探査中に通過したＵターンを含む経路に対して１つ以上のＵターン指示を記憶し、新たなリンク優先順位を形成する上記段階は、上記記憶されたＵターン指示に関連した経路上のリンクを考慮しない請求項２に記載の方法。
【請求項４】
元の地図ファイルを受け取る段階を更に含み、この元の地図ファイルは、上記電子地図における上記ノードを含み、上記新たなノード優先順位レベルを記憶する上記段階及び上記複合リンクを記憶する上記段階は、新たなファイルを発生することを含み、そしてこの新たなファイルは、上記新たなノード優先順位レベル、上記複合リンク、及び上記元の地図ファイルからの上記電子地図の上記ノードを含む請求項２に記載の方法。
【請求項５】
複合リンクを構築する上記段階は、少なくとも探査レベルのリンクの選択まで次々のリンクに沿って通過しそしてその通過した次々のリンクに沿った移動を表す新たなリンクを構築することを含む請求項２に記載の方法。
【請求項６】
外方に探査する上記段階は、
探査の前にノードの集合体に対する使用可能度を無限大に設定し、
探査中に特定ノードへ通過するときにその特定ノードの使用可能度をチェックし、
上記特定ノードが使用可能でない場合には上記特定ノードの使用可能度を変更し、
上記特定ノードが使用可能でない場合には上記特定ノードの背後にある１つ以上のノードに対して使用可能度をチェックし、そして
上記特定ノードの背後にある上記１つ以上のノードの適当なノードが使用可能でない場合には、上記特定ノードの背後にある上記１つ以上のノードの適当なノードに対して上記使用可能度を変更する、
という段階を含む請求項２に記載の方法。
【請求項７】
新たなリンク優先順位を形成する上記段階は、
上記探査段階中に訪問されそして現在の探査レベル以上の優先順位レベルにある第１ノードグループを識別し、
経路に沿って上記第１ノードグループへと後方追跡し、そして
上記経路に沿って、優先順位が上記現在の探査レベルより１レベル低いものに等しい上記第１ノードグループへ至るリンクに対し、優先順位を現在の探査レベルに変更する、
という段階を含む請求項２に記載の方法。
【請求項８】
新たなノード優先順位を形成する上記段階は、
考慮中のノードに対して前方リンクを検査し、
上記検査段階に基づいて、選択される最大優先順位レベルを決定し、そして
上記決定された最大優先順位が現在の探査レベルより低い場合には、上記新たなノード優先順位を上記決定された最大優先順位に設定する、
という段階を含む請求項２に記載の方法。
【請求項９】
前方リンクを検査し、最大優先順位レベルを決定しそして上記新たなノード優先順位を設定する上記段階は、現在の探査レベルにある各ノードに対して実行される請求項８に記載の方法。
【請求項１０】
上記外方に探査し、新たなリンク優先順位レベルを形成し、新たなノード優先順位レベルを形成し、そして複合リンクを構築する上記段階は、複数の探査レベルの各々において実行される請求項２に記載の方法。
【請求項１１】
上記現在の探査レベルにおいて上記探査段階が実行される前に現在探査レベルにおいて各ノードを識別する段階を更に含み、上記探査段階は、この識別段階で識別された各ノードにおいて実行される請求項１０に記載の方法。
【請求項１２】
プロセッサ読み取り可能なコードが実施されたプロセッサ読み取り可能な記憶媒体において、上記プロセッサ読み取り可能なコードは、
電子地図のノード及びリンクの集合体を記憶し、該リンクにはリンク優先順位レベルが関連付けされ、
プロセッサを用いて上記ノードから外方に探査し、この探査段階は、どのノードが有用でないか決定することを含み、
上記探査中に通過されそして有用でないと決定されたノードで終了しない上記リンクの集合体に対して新たなリンク優先順位レベルを形成し、
上記新たなリンク優先順位レベルをもつ１つ以上のリンクを含む複合リンクを構築し、そして
上記複合リンクを上記電子地図に記憶し、上記複合リンクが近道を表わす、という段階を含む方法を実行するようにプロセッサをプログラミングするためのものであることを特徴とするプロセッサ読み取り可能な記憶媒体。
【請求項１３】
入力デバイスと、
プロセッサ読み取り可能な記憶媒体と、
上記入力デバイス及び上記プロセッサ読み取り可能な記憶媒体と通信するプロセッサとを備え装置において、上記プロセッサ読み取り可能な記憶媒体は、
電子地図のノード及びリンクの集合体を記憶し、該リンクにはリンク優先順位が関連付けされ、
プロセッサを用いて上記ノードから外方に探査し、この探査段階は、どのノードが有用でないか決定することを含み、
上記探査中に通過されそして有用でないと決定されたノードで終了しない上記リンクの集合体に対して新たなリンク優先順位レベルを形成し、
上記新たなリンク優先順位をもつ１つ以上のリンクを含む複合リンクを構築し、そして
上記複合リンクを上記電子地図に記憶し、上記複合リンクが近道を表わす、という段階を含む方法を実行するように支援プロセッサをプログラミングするコードを記憶することを特徴とする装置。
【請求項１】
電子地図に近道を追加する方法において、
上記電子地図のノード及びリンクの集合体を記憶し、該リンクにはリンク優先順位レベルが関連付けされ、
プロセッサを用いて上記ノードから外方に探査し、この探査段階は、どのノードが有用でないか決定することを含み、
上記探査中に通過されそして有用でないと決定されたノードで終了しない上記リンクの集合体に対して新たなリンク優先順位レベルを形成し、
上記新たなリンク優先順位レベルをもつ１つ以上のリンクを含む複合リンクを構築し、そして
上記複合リンクを上記電子地図に記憶し、上記複合リンクが上記近道を表わすことを特徴とする方法。
【請求項２】
上記ノードに対するノード優先順位レベルを上記電子地図に記憶し、
新たなリンク優先順位レベルを有する１つ以上の上記リンクにより接続された上記ノードの集合体に対して新たなノード優先順位レベルを形成し、そして
上記新たなノード優先順位レベルを上記電子地図に記憶する、
という段階を更に含む請求項１に記載の方法。
【請求項３】
上記探査中に通過したＵターンを含む経路に対して１つ以上のＵターン指示を記憶し、新たなリンク優先順位を形成する上記段階は、上記記憶されたＵターン指示に関連した経路上のリンクを考慮しない請求項２に記載の方法。
【請求項４】
元の地図ファイルを受け取る段階を更に含み、この元の地図ファイルは、上記電子地図における上記ノードを含み、上記新たなノード優先順位レベルを記憶する上記段階及び上記複合リンクを記憶する上記段階は、新たなファイルを発生することを含み、そしてこの新たなファイルは、上記新たなノード優先順位レベル、上記複合リンク、及び上記元の地図ファイルからの上記電子地図の上記ノードを含む請求項２に記載の方法。
【請求項５】
複合リンクを構築する上記段階は、少なくとも探査レベルのリンクの選択まで次々のリンクに沿って通過しそしてその通過した次々のリンクに沿った移動を表す新たなリンクを構築することを含む請求項２に記載の方法。
【請求項６】
外方に探査する上記段階は、
探査の前にノードの集合体に対する使用可能度を無限大に設定し、
探査中に特定ノードへ通過するときにその特定ノードの使用可能度をチェックし、
上記特定ノードが使用可能でない場合には上記特定ノードの使用可能度を変更し、
上記特定ノードが使用可能でない場合には上記特定ノードの背後にある１つ以上のノードに対して使用可能度をチェックし、そして
上記特定ノードの背後にある上記１つ以上のノードの適当なノードが使用可能でない場合には、上記特定ノードの背後にある上記１つ以上のノードの適当なノードに対して上記使用可能度を変更する、
という段階を含む請求項２に記載の方法。
【請求項７】
新たなリンク優先順位を形成する上記段階は、
上記探査段階中に訪問されそして現在の探査レベル以上の優先順位レベルにある第１ノードグループを識別し、
経路に沿って上記第１ノードグループへと後方追跡し、そして
上記経路に沿って、優先順位が上記現在の探査レベルより１レベル低いものに等しい上記第１ノードグループへ至るリンクに対し、優先順位を現在の探査レベルに変更する、
という段階を含む請求項２に記載の方法。
【請求項８】
新たなノード優先順位を形成する上記段階は、
考慮中のノードに対して前方リンクを検査し、
上記検査段階に基づいて、選択される最大優先順位レベルを決定し、そして
上記決定された最大優先順位が現在の探査レベルより低い場合には、上記新たなノード優先順位を上記決定された最大優先順位に設定する、
という段階を含む請求項２に記載の方法。
【請求項９】
前方リンクを検査し、最大優先順位レベルを決定しそして上記新たなノード優先順位を設定する上記段階は、現在の探査レベルにある各ノードに対して実行される請求項８に記載の方法。
【請求項１０】
上記外方に探査し、新たなリンク優先順位レベルを形成し、新たなノード優先順位レベルを形成し、そして複合リンクを構築する上記段階は、複数の探査レベルの各々において実行される請求項２に記載の方法。
【請求項１１】
上記現在の探査レベルにおいて上記探査段階が実行される前に現在探査レベルにおいて各ノードを識別する段階を更に含み、上記探査段階は、この識別段階で識別された各ノードにおいて実行される請求項１０に記載の方法。
【請求項１２】
プロセッサ読み取り可能なコードが実施されたプロセッサ読み取り可能な記憶媒体において、上記プロセッサ読み取り可能なコードは、
電子地図のノード及びリンクの集合体を記憶し、該リンクにはリンク優先順位レベルが関連付けされ、
プロセッサを用いて上記ノードから外方に探査し、この探査段階は、どのノードが有用でないか決定することを含み、
上記探査中に通過されそして有用でないと決定されたノードで終了しない上記リンクの集合体に対して新たなリンク優先順位レベルを形成し、
上記新たなリンク優先順位レベルをもつ１つ以上のリンクを含む複合リンクを構築し、そして
上記複合リンクを上記電子地図に記憶し、上記複合リンクが近道を表わす、という段階を含む方法を実行するようにプロセッサをプログラミングするためのものであることを特徴とするプロセッサ読み取り可能な記憶媒体。
【請求項１３】
入力デバイスと、
プロセッサ読み取り可能な記憶媒体と、
上記入力デバイス及び上記プロセッサ読み取り可能な記憶媒体と通信するプロセッサとを備え装置において、上記プロセッサ読み取り可能な記憶媒体は、
電子地図のノード及びリンクの集合体を記憶し、該リンクにはリンク優先順位が関連付けされ、
プロセッサを用いて上記ノードから外方に探査し、この探査段階は、どのノードが有用でないか決定することを含み、
上記探査中に通過されそして有用でないと決定されたノードで終了しない上記リンクの集合体に対して新たなリンク優先順位レベルを形成し、
上記新たなリンク優先順位をもつ１つ以上のリンクを含む複合リンクを構築し、そして
上記複合リンクを上記電子地図に記憶し、上記複合リンクが近道を表わす、という段階を含む方法を実行するように支援プロセッサをプログラミングするコードを記憶することを特徴とする装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１２Ｃ】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１２Ｃ】
【図１３】
【公開番号】特開２０１３−１９９１０（Ｐ２０１３−１９９１０Ａ）
【公開日】平成２５年１月３１日（２０１３．１．３１）
【国際特許分類】
【出願番号】特願２０１２−２３２１８４（Ｐ２０１２−２３２１８４）
【出願日】平成２４年１０月１９日（２０１２．１０．１９）
【分割の表示】特願２０００−５８７２６５（Ｐ２０００−５８７２６５）の分割
【原出願日】平成１１年１２月８日（１９９９．１２．８）
【出願人】（５０１２３３６１７）テレ アトラス ノース アメリカ インコーポレイテッド (1)
【Ｆターム（参考）】
【公開日】平成２５年１月３１日（２０１３．１．３１）
【国際特許分類】
【出願日】平成２４年１０月１９日（２０１２．１０．１９）
【分割の表示】特願２０００−５８７２６５（Ｐ２０００−５８７２６５）の分割
【原出願日】平成１１年１２月８日（１９９９．１２．８）
【出願人】（５０１２３３６１７）テレ アトラス ノース アメリカ インコーポレイテッド (1)
【Ｆターム（参考）】
[ Back to top ]