(57)【特許請求の範囲】
【請求項１】
道路ネットワークにそって、物、人または車両をその最初の位置から目的地までガイドするためのガイド方法（１０）であって、
ａ．  目的地の位置を取得し、さらに、前記物、人または車両の最初の位置を決定または取得する（１２）ステップと、
ｂ．  サーバが、道路ネットワークを示すグラフの前記最初の位置から前記目的地の位置の間で、該グラフ上の全ての頂点から前記目的地の頂点への最小コストとなる全ルートを含む完全なルートガイダンスツリーを決定し、決定した前記完全なルートガイダンスツリーを前記サーバ内に保存する（１４）ステップと、
ｃ．  完全なルートガイダンスツリーから、前記最初の位置に最も近い部分的なルートガイダンスツリーを抽出する（１６）ステップと、
ｄ．  現在位置を測定する（１８）ステップと、
ｅ．  前記現在位置が前記部分的なルートガイダンスツリーの範囲内かどうかを決定する（２０）ステップと、
ｆ．  前記現在位置が前記部分的なルートガイダンスツリーの範囲内であれば、前記部分的なルートガイダンスツリーを表示し（２２）、前記現在位置が前記部分的なルートガイダンスツリーの範囲内でなければ、前記現在位置に最も近く、前記完全なルートガイダンスツリーを構成する別の部分的なルートガイダンスツリーを、保存された前記完全なルートガイダンスツリーから前記サーバが抽出する（２４）ステップと、
ｇ．  以降は、前記目的地に到着するまで、または方法が中断されるまで、現在位置を測定し、現在位置が、直近に抽出された部分的なルートガイダンスツリーの範囲内かどうかを決定し（２０）、範囲内であれば、当該部分的なルートガイダンスツリーを表示し（２２）、範囲内でなければ、前記現在位置に最も近く、前記完全なルートガイダンスツリーを構成する別の部分的なルートガイダンスツリーを、前記完全なルートガイダンスツリーから抽出することを繰り返すステップと、
を含むガイド方法。
【請求項２】
前記道路ネットワークを示す前記グラフは、通りセグメントおよびその通行方向をエッジとして、セグメント間の交差点を頂点として示す請求項１のガイド方法。
【請求項３】
前記現在位置から最も近い部分的なルートガイダンスツリーを抽出する際の「最も近い」は、前記現在位置から所定数のエッジ以内にある頂点に基づく請求項２に記載のガイド方法。
【請求項４】
前記現在位置から最も近い部分的なルートガイダンスツリーを抽出する際の「最も近い」は、前記現在位置から所定数内にある頂点に基づく請求項２に記載のガイド方法。
【請求項５】
前記現在位置から最も近い部分的なルートガイダンスツリーを抽出する際の「最も近い」は、前記現在位置からの所定量の見積もり時間内にある頂点に基づく請求項２に記載のガイド方法。
【請求項６】
前記道路ネットワークを示す前記グラフは、通りセグメントおよびその通行方向を頂点として、各通りセグメント間の許容される移動をエッジとして示す請求項１のガイド方法。
【請求項７】
前記現在位置から最も近い部分的なルートガイダンスツリーを抽出する際の「最も近い」は、前記現在位置から所定数のエッジ以内にある頂点に基づく請求項６に記載のガイド方法。
【請求項８】
前記現在位置から最も近い部分的なルートガイダンスツリーを抽出する際の「最も近い」は、前記現在位置から所定数内にある頂点に基づく請求項６に記載のガイド方法。
【請求項９】
前記現在位置から最も近い部分的なルートガイダンスツリーを抽出する際の「最も近い」は、前記現在位置からの所定量の見積もり時間内にある頂点に基づく請求項６に記載のガイド方法。
【請求項１０】
道路ネットワークにそって、物、人または車両をその最初の位置から目的地までガイドするためのガイドシステムであって、
ａ．  物理的道路ネットワークを示すデータベースを格納し、該道路ネットワークを示すグラフの前記最初の位置から前記目的地の位置の間で、該グラフ上の全ての頂点から前記目的地の頂点への最小コストとなる全ルートを含む完全なルートガイダンスツリーを決定し、決定した前記完全なルートガイダンスツリーを保存して（１４）、前記完全なルートガイダンスツリーから、部分的なルートガイダンスツリーを抽出する（１６）サーバ手段（２８）と、
ｂ．  前記サーバ手段および少なくとも一つのクライアント手段間の情報の通過のための通信手段（３０、３２、３４、３６）と、
ｃ．前記目的地の位置を取得して（１２）、前記クライアント手段の現在位置を測定して（１８）、前記通信手段を用いて前記サーバ手段に目的地および現在位置を送信し、前記通信手段を用いて前記サーバ手段から部分的なルートガイダンスツリーを受信する前記クライアント手段（２６）と、を有し、
前記サーバ手段は、まず、前記最初の位置に最も近い部分的なルートガイダンスツリーを抽出して、前記クライアント手段に送信し、
前記クライアント手段は、前記現在位置が前記最初の位置に最も近い部分的なルートガイダンスツリーの範囲内かどうかを決定し（２０）、範囲内であれば、当該部分的なルートガイダンスツリーを表示し（２２）、範囲内でなければ、前記通信手段を用いて前記現在位置に最も近く、前記完全なルートガイダンスツリーを構成する別の部分的なルートガイダンスツリーを、前記完全なルートガイダンスツリーから抽出（２４）すべくさらに前記サーバ手段に要求（３６）し、
以降は、前記クライアント手段は、前記目的地に到着するまで、現在位置を測定し（１８）、現在位置が、直近に前記サーバ手段によって抽出された前記部分的なルートガイダンスツリーの範囲内かどうかを決定し（２０）、範囲内であれば、当該部分的なルートガイダンスツリーを表示し（２２）、範囲内でなければ、前記通信手段を用いて前記現在位置に最も近く、前記完全なルートガイダンスツリーを構成する別の部分的なルートガイダンスツリーを、前記完全なルートガイダンスツリーから抽出（２４）すべくさらに前記サーバ手段に要求（３６）することを繰り返すガイドシステム。
【請求項１１】
前記物理的道路ネットワークは、車道を含む請求項１０に記載のガイドシステム。
【請求項１２】
前記物理的道路ネットワークが示すグラフは通りセグメントおよびその通行方向をエッジとして、セグメント間の交差点を頂点として示す請求項１１に記載のガイドシステム。
【請求項１３】
前記物理的道路ネットワークが示すグラフは、通りセグメントおよびその通行方向を頂点として、各通りセグメント間の許容される移動をエッジとして示す請求項１１に記載のガイドシステム。
【請求項１４】
前記現在位置から最も近い部分的なルートガイダンスツリーを受信する際の「最も近い」は、前記現在位置から所定数のエッジ以内にある頂点に基づく請求項１０に記載のガイドシステム。
【請求項１５】
前記現在位置から最も近い部分的なルートガイダンスツリーを受信する際の「最も近い」は、前記現在位置から所定数内にある頂点に基づく請求項１０に記載のガイドシステム。
【請求項１６】
前記現在位置から最も近い部分的なルートガイダンスツリーを受信する際の「最も近い」は、前記現在位置からの所定量の見積もり時間内にある頂点に基づく請求項１０に記載のガイドシステム。
【請求項１７】
前記現在位置から最も近い部分的なルートガイダンスツリーを受信する際の「最も近い」は、前記現在位置から所定数のエッジ以内にある頂点に基づく請求項１２に記載のガイドシステム。
【請求項１８】
前記現在位置から最も近い部分的なルートガイダンスツリーを受信する際の「最も近い」は、前記現在位置から所定数内にある頂点に基づく請求項１２に記載のガイドシステム。
【請求項１９】
前記現在位置から最も近い部分的なルートガイダンスツリーを受信する際の「最も近い」は、前記現在位置からの所定量の見積もり時間内にある頂点に基づく請求項１２に記載のガイドシステム。
【請求項２０】
前記現在位置から最も近い部分的なルートガイダンスツリーを受信する際の「最も近い」は、前記現在位置から所定数のエッジ以内にある頂点に基づく請求項１３に記載のガイドシステム。
【請求項２１】
前記現在位置から最も近い部分的なルートガイダンスツリーを受信する際の「最も近い」は、前記現在位置から所定数内にある頂点に基づく請求項１３に記載のガイドシステム。
【請求項２２】
前記現在位置から最も近い部分的なルートガイダンスツリーを受信する際の「最も近い」は、前記現在位置からの所定量の見積もり時間内にある頂点に基づく請求項１３に記載のガイドシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
発明者：            アライン  エル．コーンハウザー
デビッド  バーンステイン
マーク  エー．ホルナング
関連出願に対するクロスリファレンス
この出願は、アライン  エル．  コーンハウザー、デビッド  バーンステインおよびマーク  ホルナングによるタイトル「シン・クライアントナビゲーションおよびルートガイダンスシステム」、２００１年２月２６日出願の暫定米国出願Ｎｏ．６０／２７１，３９３号に基づく優先権を主張し、これによって、その全内容および実態は、引用によって全体的に組み込まれる。
【０００２】
発明の背景
１．  発明の技術分野
本発明は、道路ネットワークに沿った、物、人または車両によるナビゲーションおよびルートガイダンスのためのシステムおよび方法に関する。
２．  従来技術の説明
目的地への道を見つけてうまく到着することは、旅路においてコストを上回る価値として充分な効果を有する。この作業を補助するために様々なシステムおよび装置が発明されている。少し例を挙げれば、見通し線、マップ、方向、コンパスおよび六分儀である。これらのシステムおよび装置の多くは、コンピュータに接続されており、新しいシステムが現在も開発されている。
【０００３】
人が自分で道を探す特別なケースには、旅行中に道路ネットワークの関連および交差が抑制されたときである。これは、概して陸上の旅行中のケースであり、人は、進路または道からはぐれることによって、すぐにトラブルに巻き込まれる。船員および宇宙飛行士を除いて、大部分の人間（および多くの動物）は、主に道路ネットワーク上で旅行し、それらの道路ネットワークに沿って航行する。
【０００４】
多くのコンピュータ化されたシステムは、道路ネットワークに沿ったナビゲーション、ルート発見およびルートガイダンスの援助のために開発された。現在利用可能なシステムは、３つのタイプに分類されることができる。第一世代のシステムは、マップと、該マップを見て問い合わせる機能とを提供する。第二世代のシステムは、一般的にグローバルポジショニングシステム（ＧＰＳ）受信機による現在位置の自動測定、および該現在位置の地図上の表示まで拡張された。第三世代のシステムは、道路ネットワーク上でユーザの現在位置および目的地を見つけることによって、ユーザの目的地への曲がり角ごとの方向を示し、途中の推薦されたルートを計算する。
【０００５】
全３種類のシステムは、スタンドアロン構成およびクライアント／サーバ構成で実行されている。スタンドアロン構成では、一つのコンピュータが全ての必要なマップデータを記憶し、全ての必要な計算を実行するため、充分な資源を有する。クライアント／サーバ構成では、通信により接続されるクライアントおよびサーバの少なくとも２台のコンピュータ間で作業が分配される。クライアント／サーバ構成は、ほとんどのデータおよび計算がクライアント上にあるシック・クライアントでなされてもよく、または、ほとんどのデータおよび計算がクライアント上にあるシン・クライアントでなされてもよい。
【０００６】
シン・クライアント構成ではサーバが大部分の作業をするので、クライアントコンピュータは、比較的小さく、低出力で安価にできる。これは、ルートガイダンスのようなモバイルアプリケーションのためには、魅力的な目標である。しかし、クライアントは、サーバとの信頼性および応答性が高い無線通信に依存する。残念なことに、無線データ通信は、貧弱な受信により生じるギャップのため比較的信頼性が低く、ネットワークを介するパケットのスイッチングの遅れのために反応が遅く、高価である。その結果、既存の第三世代のシン・クライアントナビゲーションシステムは、それらのスタンドアロンの均等物に比べて実行が貧弱である。なぜなら、それらのシステムは、ユーザがルートから逸脱したとき（たとえば、ユーザが曲がり間違えたときや、回り道を強いられたとき）に、たよりにならず、迅速にルートを探せないからである。
【０００７】
他方、スタンドアロンシステムでは、現在の交通渋滞情報、天気（氷、雪、強風など）、新しく出来た道、封鎖された道、改良された道の情報、よいルートを見つけるための他の現在の貴重な情報が得られず、より大きく、より高価で、より消費電力の大きなクライアントコンピュータを必要とすることに我慢しなくてはならない。
【０００８】
シック・クライアントシステムでは、極端に遅く、また極端に高価な通信バンド幅を必要とし、さらに、より大きく、より高価で、より消費電力の大きなクライアントコンピュータを必要とすることに我慢しなくてはならない。
【０００９】
これらの理由のために、シン・クライアントナビゲーションシステムでは、クライアント装置上のマップデータの大部分および演算を効率的に緩和するための方法を見つけ、短い遅延やサーバとの通信の切断にもかかわらず、勧めたルートからユーザが逸脱してもガイダンスを提供し続けられることが望まれている。
【００１０】
米国特許６，０５２，６４５号は、クライアントが主要な道のマップを永久に格納し、必要に応じてサーバから詳細なマップを請求するシステムを開示している。クライアントは、マップを使用してルート計算を実行する。これは、クライアントが主要な道を記憶し、強力なプロセッサがルート計算を実行するために、かなりの記憶容量を必要とするので、シック・クライアントシステムである。クライアントは、ルートから逸脱したことを検出すると、クライアントが新たなルートを計算するために用いる該逸脱ポイント周辺の詳細マップをサーバに要求する。そのような要求を満たすために、モバイルコミュニケーション道路ネットワークはスループットが低下し、まるで中断しているようになり、一旦詳細なマップデータを受信してからかなりの時間が新たなルートの計算に費やされ、このシステムのユーザは、詳細マップが表示され、および／または新しい曲がり指示が与えられるまでに、我慢できないほど長い時間待たなければならない。
【００１１】
米国特許６，１０７，９４４号は、サーバがマップの格納およびルート計算を実行し、コンパクトな操作（曲がり）指示をクライアントに伝えるシステムを開示している。これは、クライアントがコンパクトな曲がり指示を保存するだけの単に小さな記憶容量と、それらの指示を表示するために小さなプロセッサとが必要なので、シン・クライアントシステムである。クライアントに与えられる曲がり指示は、充分詳細に提供された場合、正面のルートから逸脱したことを検出するために使用される。しかし、一度ルートの逸脱を検出すると、クライアントは、新しい指示の組をサーバから受信するまで待機しなくてはならない。このシステムのユーザは、ルート逸脱検出の利益を得られず、新しい曲がり指示が与えられるまでに我慢できないほど長い時間を待たなければならない。
【００１２】
以下の米国特許は、関連すると考えられ得るナビゲーションおよびルートガイダンスシステムの一般的な説明として引用される。米国特許５，１７７，６８５号、５，２９３，１６３号、５，６５２，７０６号、５，６７５，４９２号、５，８６２，５０９号、５，８７５，４１２号、５，８９３，０８１号、５，９１６，２９９号、６，０１４，６０７号、６，０１６，４８５号、６，０３８，５０９号、６，０６４，９４１号、６，０７０，１２２号、６，１９２，３１３号、６，１９２，３１４号、６，１９９，００９号、６，１９９，０１３号、６，２１１，７９８号。
【００１３】
発明の概要
本発明は、簡単には、多種多様なサーバ、クライアント、および通信チャネルに適用でき、シン・クライアントを用いたクライアントサーバ操作に適したナビゲーションおよびルートガイダンスシステムの方法である。
【００１４】
本発明によれば、シン・クライアントは、ユーザの行き先の入力を確実に受け付け、ＧＰＳや他の手段を用いて現在位置を測定し、ルートガイダンス指示および／またはマップを表示する。サーバは、完全なマップデータを格納し、クライアントからのルート要求を受け入れ、実行する。
【００１５】
本発明の特徴は、ルートが要求されて、編成されて、クライアントに交付される方法である。具体的には、サーバはクライアントの行き先に関連した道路ネットワーク上のあらゆる場所から最もよいルートを決定する。それから、クライアントの現在位置から最も近いそれらのルートの部分だけをクライアントに送信する。クライアントは、移動するので、現在位置と以前受信したルートの部分とを比較し、もしそれらのルートの境界に近づいている場合、サーバに新たな部分を送信するように要求する。これは、クライアントに局所的に記憶するには大きすぎる道路ネットワーク上でルートガイダンスの提供を可能にすると共に、クライアントがオリジナルルートから逸脱した場合でも、サーバから新たなルートを受信するために待つことなく、新たなガイダンスを与えることを可能にする。
本発明は、以下の図面を参照することでより完全に理解される。
【００１６】
図面の簡単な説明
図１は、円（ポイント）により示される頂点（ノード）と、矢印（直線）により示されるエッジ（リンクまたは弧）からなるグラフである。
【００１７】
図２Ａは、一方通行または両面交通の通りの交差点の道路ネットワークを示す図である。
【００１８】
図２Ｂは、頂点および各通りセグメントによって示される各交差点およびエッジによって示される進行方向を伴うグラフとして、図２Ａと同じ道路ネットワークを示す図である。
【００１９】
図２Ｃは、図２Ａおよび図２Ｂの道路ネットワークを異なるグラフとして示す図であって、各通りセグメントおよび進行方向を頂点により表し、通りセグメント間の許容される各移動をエッジにより表している。
【００２０】
図３Ａは、図２Ｂのグラフを示す図であって、各エッジがそのコストの値によってラベルを付けられ、特定の頂点にＯとＤのラベルが付けられている。
【００２１】
図３Ｂは、図３Ａのグラフにおいて頂点Ｄ以外の頂点から頂点Ｄへの最小コストのパス（経路）をなぞるガイダンスツリーを示す図であって、各頂点には該頂点からＤに到達するまでの合計コストのラベルが付され、特定の頂点には参照文字のラベルが付されている。
【００２２】
図４Ａは、図３Ｂ中のガイダンスツリーの頂点Ｏから頂点Ｄへのローカルなガイダンスツリーを示す図である。
【００２３】
図４Ｂは、図３Ｂ中のガイダンスツリーの頂点Ａから頂点Ｄへのローカルなガイダンスツリーを示す図である。
【００２４】
図５は、本発明のシステムおよび方法の好適な実施形態を示すフローチャートである。
【００２５】
好適な実施形態の詳細な説明
以下の説明では、異なる図面においても、同じ要素を識別するために同じ文字を使用している。
【００２６】
本発明の要点は、ガイダンスツリーにある。
【００２７】
ガイダンスツリーを理解するために、グラフと、道路ネットワークがグラフとしてどのように表されるかとを理解することが必要である。
【００２８】
グラフは、数学的な概念を包含する。それは、頂点（ノード）の集合およびエッジ（リンクまたは弧）の組から構成されている。図示するように、頂点は円として表され、エッジは該円を接続する矢印として表される。この図示の規則に従って表されるグラフの例は、図１に示される。
【００２９】
道路ネットワークは、多くの異なる方法のグラフとして示される。例えば、図２Ａに示される通りと交差点からなる小さい道路ネットワークについて検討する。この道路ネットワークからグラフを描く手法の一つは、各交差点を頂点によって示し、各通りセグメントおよびその通行方向をエッジによって示すことである。これは、図２Ｂに図示される。道路ネットワークからグラフを描く他の方法は、各通りセグメントおよび通行方向を頂点により示し、各通りセグメント間の可能な移動をエッジによって示すことである。これは、図２Ｃに図示される。
【００３０】
ガイダンスツリーは、基礎をなす道路ネットワーク表現に関係なく、いかなるグラフからも造られる。ガイダンスツリーは、あらゆる頂点から特定の目的地を結ぶ最善ルート上にある全てのグラフ中の頂点およびエッジからなる。
【００３１】
最善のルートは、エッジの合計本数が最小となるようにした二頂点間のエッジの連続として示される。例えば、図３Ａに示すグラフを考えて、ユーザの目的地が頂点Ｄとすると、彼女／彼は、目的地までの最少コスト（最短時間、最短距離、および／または最安値）のルートに関心がある。ここで、各エッジの隣に見られる数値はそのエッジを通過するためのコストである。
【００３２】
頂点Ｄへのガイダンスツリーの結果は、図３Ｂに示す通りである。この図では、各頂点の隣の数値は、最小コストのルートに沿ったノードから目的地までのコストを示す。各頂点から出るエッジは、ユーザが最小コストの経路上に残るために使用しなければならない。
【００３３】
図３Ｂのガイダンスツリーは、グラフ上の全ての頂点から頂点Ｄへの最小コストのルートを示す完全なガイダンスツリーである。ユーザが推薦されたルートから逸脱した場合、いかなる理由であっても、ガイダンスツリーは、常に彼／彼女に頂点Ｄへ有効かつ充分なガイドを与える。例えば、ユーザが頂点Ｏを出発して頂点Ａに進み、Ａにおいて偶然左折したら、真直ぐＢに行くのではなく、Ｃに向かったと想定する。ここでも、ガイダンスツリーは有効に持続し、頂点Ｃから頂点Ｅを経て頂点Ｄへ行く最小コストのルートを示す。
【００３４】
代表的なルートガイダンスアプリケーションにおいて、道路ネットワーク、また、その結果としてのグラフおよびガイダンスツリーは、非常に大きくなる。例えば、北アメリカの自動車運転手は、大陸のどの公道でも自由に運転できると考えられる。代表的なシン・クライアントのクライアント／サーバ環境において、サーバおよびクライアント間の通信バンド幅は、ユーザが許容できる範囲ですばやくツリー全体を送信するには不十分であり、シン・クライアント装置のデータ記憶容量は、完全なガイダンスツリーを保持するのに充分ではない。この問題を解決するために、本発明は、ローカルガイダンスツリーを利用する。
【００３５】
ローカルガイダンスツリーは、完全なガイダンスツリーの一部である。ローカルガイダンスツリーでは、クライアントの現在位置に近い頂点だけが含まれる。近くの頂点をつなぐエッジは個々に含まれ、近くの頂点から目的地をつなぐエッジは一緒に集合される。
【００３６】
図４Ａは、図３Ｂの完全なガイダンスツリーから分割したローカルガイダンスツリーの実施例を示す図である。この実施例では、ユーザの現在位置は頂点Ｏである。ユーザの目的地は、頂点Ｄである。ローカルガイダンスツリーは、頂点Ｏから届くエッジおよび頂点を、エッジが３つ以下（この数は、この実施例のためにだけに選択されたものである）で含む。ローカルガイダンスツリーは、また、頂点Ｄと頂点Ｄに最も近い頂点Ｏから３つのエッジ以内の頂点との間で集合されたエッジを含む。ローカルガイダンスツリーを用いる本実施例では、サーバが送信し、クライアントが格納するのは、図４Ａに示すようにたった６つの頂点と５つのエッジだけであり、図３Ｂに示すように１４個の頂点と１１個のエッジまでは必要としない。
【００３７】
ユーザが彼／彼女のルートを進むので、クライアントは、周期的にローカルガイダンスツリーを下流へ埋め合わせていく必要がある。例えば、ユーザが頂点Ａに到達すると、クライアントは、新規なローカルガイダンスツリーを要求して、図４Ｂに示すローカルガイダンスツリーが送信される。
【００３８】
ユーザの現在位置に最も近いガイダンスツリーの一部を決定するために様々な方法が使用されている。図４Ａおよび図４Ｂの実施例では、ユーザの位置から３つ以内のエッジが含まれる。他の方法は、ユーザの位置から特定時間内（コストの一種）の頂点、例えば、ユーザの位置から１０分以内の頂点を含む。実際問題として、ローカルガイダンスツリーのサイズは、クライアントの能力、通信手段、および道路ネットワークの密度に関係する進行速度に依存する。
【００３９】
本発明のサーバは、１つの主な機能、すなわち、ローカルガイダンスツリーを有するクライアントを提供することを実行する。特定のローカルガイダンスツリーが提供するものは、クライアントの位置、ユーザの目的地、クライアント上に記憶できるデータ容量、並びに、サーバおよびクライアント間の通信の信頼性、応答性、バンド幅およびスピードによって決定され、ユーザがどうやって早くツリーを通過できるかに関する。
【００４０】
この機能を実行するためのサーバは、ローカルガイダンスツリーを生成できなくてはならない。サーバは、グラフから完全なガイダンスツリーを計算する能力を有する。それは、また、ガイダンスツリーを記憶し、検索する能力を有する。したがって、サーバは、ある場合には、ローカルガイダンスツリーを造るために、データベースから予め演算されたガイダンスツリーを検索し、その他の場合、特に、与えられた目的地のためにガイダンスツリーが初めて要求された場合には、ガイダンスツリーを演算する。
【００４１】
シン・デバイスに適するように、この発明に係るクライアントは、最小のメモリおよび計算能力を有する。
【００４２】
クライアントは、規則正しく緯度および経度を測定し（例えば、１分間に２０回）、（任意に）その進行方向を取得するために、車両位置システム（例えば、全地球位置測定システムおよび／または推測航法）を使用する。クライアントは、これを車両の緯度および経度ならびに現在格納されているローカルガイダンスツリーのエッジと比較して、車両がどのエッジ上またはどのエッジに最も近いかを決定する。そのマップ上の位置が現在のローカルガイダンスツリーの境界に近い場合や、または目的地が変わった場合には、クライアントは、サーバに新たなローカルガイダンスツリーを要求する。その要求は、目的地およびマップ上の位置を含む。クライアントは、サーバからローカルガイダンスツリーを受信し、それを用いて、曲がり指示および／またはマップの形式としてルートガイダンス情報をユーザに提供する。つまり、後述する図５のフローチャートに示すように、部分的なルートガイダンスツリーを表示して（２２）、ルートガイダンス情報をユーザに提供する。
【００４３】
このようなサーバおよびクライアント間の方法および応答性の分配は、フローチャートの形式により図５に示されている。
【００４４】
本発明はその好適な実施形態を参照して詳述されているが、本発明の技術的思想の範囲から逸脱することなく、当業者によって、本発明のシステムおよび方法を改変することができる。
【図面の簡単な説明】
【００４５】
【図１】円（ポイント）により示される頂点（ノード）と、矢印（直線）により示されるエッジ（リンクまたは弧）からなるグラフである。
【図２Ａ】一方通行または両面交通の通りの交差点の道路ネットワークを示す図である。
【図２Ｂ】頂点および各通りセグメントによって示される各交差点およびエッジによって示される進行方向を伴うグラフとして、図２Ａと同じ道路ネットワークを示す図である。
【図２Ｃ】図２Ａおよび図２Ｂの道路ネットワークを異なるグラフとして示す図であって、各通りセグメントおよび進行方向を頂点により表し、通りセグメント間の許容される各移動をエッジにより表している。
【図３Ａ】図２Ｂのグラフを示す図であって、各エッジがそのコストの値によってラベルを付けられ、特定の頂点にＯとＤのラベルが付けられている。
【図３Ｂ】図３Ａのグラフにおいて頂点Ｄ以外の頂点から頂点Ｄへの最小コストのパス（経路）をなぞるガイダンスツリーを示す図であって、各頂点には該頂点からＤに到達するまでの合計コストのラベルが付され、特定の頂点には参照文字のラベルが付されている。
【図４Ａ】図３Ｂ中のガイダンスツリーの頂点Ｏから頂点Ｄへのローカルなガイダンスツリーを示す図である。
【図４Ｂ】図３Ｂ中のガイダンスツリーの頂点Ａから頂点Ｄへのローカルなガイダンスツリーを示す図である。
【図５】本発明のシステムおよび方法の好適な実施形態を示すフローチャートである。
【符号の説明】
【００４６】
２６    クライアント、
２８    サーバ、
３０、３２、３４、３６    通信手段。
【図１】
0004648612.tif 000002
【図２Ａ】
0004648612.tif 000003
【図２Ｂ】
0004648612.tif 000004
【図２Ｃ】
0004648612.tif 000005
【図３Ａ】
0004648612.tif 000006
【図３Ｂ】
0004648612.tif 000007
【図４Ａ】
0004648612.tif 000008
【図４Ｂ】
0004648612.tif 000009
【図５】
0004648612.tif 000010