(57)【特許請求の範囲】
【請求項１】
ルートをナビゲーションシステムに提供する方法であって、前記方法が、
道路区分を含む道路データから前記ルートを算出するステップであって、前記道路区分がランクに階層的に分類されている、ステップと、
前記算出されたルート上の判断地点を決定するステップであって、少なくとも２つの道路区分が前記判断地点のそれぞれで互いに接続され、前記判断地点を決定することが、前記算出されたルートの全ての判断地点を識別することと、前記算出されたルートの２つの道路区分が互いに接続し、前記算出されたルートの前記２つの道路区分と比較して、より下位のランクである付加的な道路区分だけが接続される判断地点を無視することとを含む、ステップと、
前記決定された判断地点のデータをメモリに記憶するステップと、
前記決定された判断地点の前記記憶されたデータに基づいて前記ルートをエンコードするステップと
を含む、方法。
【請求項２】
前記判断地点を決定することが、前記算出されたルートの全ての判断地点を識別することと、２つの道路区分だけが互いに接続する判断地点を無視することとを含む、請求項１に記載の方法。
【請求項３】
前記算出されたルートが開始部分、中間部分及び終了部分を含み、前記判断地点を決定することが、前記算出されたルートの全ての判断地点を識別することと、前記算出されたルートの前記中間部分だけに対して、前記算出されたルートの前記２つの道路区分と比較して、より下位のランクである付加的な道路区分だけが接続される判断地点を無視することとを含む、請求項１または２に記載の方法。
【請求項４】
前記決定された判断地点の１つの判断地点の前記データを記憶することが、
前記判断地点の地理座標と、
前記判断地点に入る道路区分の地理方向と、
前記判断地点を去る道路区分の地理方向と、
道路区分が前記判断地点に入る道路のタイプと、
道路区分が前記判断地点から去る道路のタイプと、
前記判断地点から前記算出されたルートの以前の判断地点または前記算出されたルートの次の判断地点までのルート上の距離と
の少なくとも１つを記憶することを含む、請求項１〜３のいずれか１項に記載の方法。
【請求項５】
前記決定された判断地点の１つの判断地点の前記データを記憶することが、前記判断地点に以前の判断地点から到達する１つ以上の道路の前記ランク及び／または次の判断地点に前記判断地点から到達する１つ以上の道路の前記ランクを記憶することを含む、請求項３または４に記載の方法。
【請求項６】
前記エンコードされたルートをコンピューティングセンターから車内ナビゲーションシステムに送信すること、前記送信されたエンコードされたルートを前記車内ナビゲーションシステムで受信すること、及び前記受信されたエンコードされたルートを前記車内ナビゲーションシステムでデコードすることを更に含む、請求項１〜５のいずれか１項に記載の方法。
【請求項７】
請求項６に記載の、ルートをナビゲーションシステムに提供する方法の前記ステップを含み、前記デコードされたルートを前記車内ナビゲーションシステムのユーザに表すこと、特に、前記デコードされたルートを前記車内ナビゲーションシステムのスクリーン上に表示することを更に含む、ルートガイダンスの方法。
【請求項８】
前記ユーザによる入力に応答して、前記車内ナビゲーションシステムから前記コンピューティングセンターにルートを算出するための要求を送信すること、及び前記コンピューティングセンターによって前記ルートを算出することを更に含む、請求項７に記載の方法。
【請求項９】
前記車内ナビゲーションシステムで前記受信されたエンコードされたルートをデコードすることが、
前記受信されたエンコードされたルートの予め定められた出発地点から開始する前記受信されたエンコードされたルート上の第１の判断地点と、前記車内ナビゲーションシステムのナビゲーションデータベースに記憶された道路ネットワークを、前記第１の判断地点と関連した前記情報で前記道路ネットワークの全ての道路区分を決定することによって、照合することと、
前記決定された道路区分から始めて道路ネットワーク拡張を開始することと、
それぞれの拡張された道路区分をそれに到達した先例の道路区分と関連付けることと、
前記道路ネットワーク拡張が、前記第１の判断地点に続く前記受信されたエンコードされたルートの次の判断地点の特性を満たすジャンクションを横断する場合、前記ジャンクションから去る道路区分で前記道路ネットワーク拡張を終了して、前記ジャンクションから去る前記道路区分から新たな道路ネットワーク拡張を開始することと
を含む、請求項６〜８のいずれか１項に記載の方法。
【請求項１０】
請求項１〜９のいずれか１項に記載の方法の前記ステップを実行するためのコンピュータ実行可能命令を有する１つ以上のコンピュータ可読な媒体を含む、コンピュータプログラム製品。
【請求項１１】
ａ）車内ナビゲーションシステムと、
ｂ）前記車内ナビゲーションシステムの外部にある外部のコンピューティングセンターと
を含むナビゲーションシステムであって、
前記車内ナビゲーションシステムが、
前記外部のコンピューティングセンターとデータを交換するように構成される通信手段と、
デコードされたルートを取得するために、前記外部のコンピューティングセンターによってエンコードされて送信されるエンコードされたルートをデコードするように構成されるデータプロセッサと、
前記デコードされたルートを表示するように構成されるディスプレイ装置と
を含み、
前記データプロセッサは、前記エンコードされたルートに含まれる前記ルートの判断地点のデータに基づいて前記エンコードされたルートをデコードするように構成され、前記ルートの少なくとも２つの道路区分は、前記判断地点のそれぞれで互いに接続され、
前記外部のコンピューティングセンターが、
道路データを記憶するように構成されるコンピューティングセンターのデータベースと、
ランクに階層的に分類されている道路区分を含むルートを前記道路データから算出すること、前記算出されたルート上の判断地点を決定すること、前記決定された判断地点のデータに基づいて前記ルートをエンコードすること、及び前記エンコードされたルートを前記車内ナビゲーションシステムに送信することを実行するように構成されるデータプロセッサと
を含み、
前記判断地点を決定することが、前記算出されたルートの全ての判断地点を識別することと、前記算出されたルートの２つの道路区分が互いに接続し、前記算出されたルートの前記２つの道路区分と比較して、より下位のランクである付加的な道路区分だけが接続される判断地点を無視することとを含む、ナビゲーションシステム。
【請求項１２】
前記判断地点の前記データが、
前記判断地点の地理座標と、
前記判断地点に入る道路区分の地理方向と、
前記判断地点を去る道路区分の地理方向と、
道路区分が前記判断地点に入る道路のタイプと、
道路区分が前記判断地点から去る道路のタイプと、
前記判断地点から前記算出されたルートの以前の判断地点または前記算出されたルートの次の判断地点までのルート上の距離と
の少なくとも１つを含む、請求項１１に記載のナビゲーションシステム。
【請求項１３】
前記車内ナビゲーションシステムが、道路を記憶するように構成されるナビゲーションデータベースを含み、前記コンピューティングセンターのデータベース及び前記車内ナビゲーションシステムの前記ナビゲーションデータベースが前記ルートの同じ道路区分を記憶する、請求項１１に記載のナビゲーションシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーションシステムによるルートガイダンス及び車両のためのナビゲーションシステムに関する。特に、本発明は車両内ナビゲーションシステムへのナビゲート可能なルートの提供に関する。
【背景技術】
【０００２】
今日では、ナビゲーションシステムは、車両、例えば自動車にとっての標準器材になった。通常、このようなシステムは、ＧＰＳ（全地球測位システム）衛星無線信号を受信する。これらの無線信号は、車両のＧＰＳアンテナによって受信されて、車両のナビゲーションコンピュータに提供される。このコンピュータは受信したデータならびに、更に、ホイールセンサ及びジャイロスコープのような移動センサによって取得されるデータを処理し、それによって現在の車両の位置を判定する。
【０００３】
知られているナビゲーションシステムは、通常、電子マップを使用して、通り、建物及び川のような地図作成特徴を表し、コンパクトディスクまたはデジタルビデオディスクなどの媒体を利用して地図作成特徴に関するデータを記憶する。マップマッチングの後、ユーザの現在の位置は、デジタルマップに示される。音響及び／または視覚化された情報によって、ユーザは予め定められた目的地へ案内される。
【０００４】
いくつかのナビゲーションシステムは、予め定められた目的地までのルート、ジャンクションのような様々な場所で行うべき操作のタイプ、ならびに、例えばガソリンスタンド、ホテルまたはレストラン、更にはランドマークのような異なる種類の関心地点（ＰＯＩ）を示す、詳細なデジタルマップ及び／または３次元の詳細図を表示することができる。
【０００５】
ナビゲーション機能を提供するために、ナビゲーションシステムは、車線のためのビットマップ画像、標示ポスト情報、ランドマークなど、及び、例えば、地理的領域及び関心地点の物理特徴を表すデータを含むことができる１つ以上の詳細なデータベースを利用する。
【０００６】
原則として、出発地点から目的地点までのルートは、車両内ナビゲーションシステムによって、または外部で、より多くの計算能力、常に更新されるデータベース及びリアルタイム情報、例えば、交通情報を有するいくつかのコンピューティングセンターによって、算出することができる。ルートガイダンスのためのルートがコンピューティングセンターで算出される場合、それはエンコードして車内ナビゲーションシステムに発信されなければならず、そこで実際のルートガイダンス、例えば、ルート表示のためにデコードされることになる。各実行環境（車内ナビゲーションシステム及びコンピューティングセンター）がそれ自身のナビゲーションデータベースを有しており、それら自身のナビゲーションデータベースを参照するルートだけしか算出して表すことができないので、エンコード及びデコードが必要である。更に、異なるデータフォーマットが、異なる実行環境において使用され得る。このように、異なる実行環境の間のいかなる通信も、データのエンコード及びデコードに基づかなければならない。
【０００７】
エンコーディングの間に、算出ルートはデータベース依存的な記述からデータベースから独立した記述に変換され、デコーディングの間に、ルートはデータベースから独立した記述からデータベース依存的な記述に変換される。
【０００８】
技術的ににおいて、エンコーディング及びデコーディングの方法は、例えば、エンコーディング／デコーディングのために必要となるルートデータの属性の拡がり、及びルート発見処理のために用いるナビゲーションデータベースに含まれる詳細な道路ネットワーク記述のために、かなり時間がかかる。特に、長距離ルートの場合、受信したエンコードされたルート結果のデコーディングは、車内ナビゲーションシステム上の高い計算負荷、及びルートガイダンスの要求と外部で算出したルートの標示の間の大きな時間遅延という結果になる。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従って、従来技術のように時間がかからず、１つの実行環境から別の実行環境へのルートデータの高信頼の通信を可能とする、ルートガイダンス及び、特に、ルートのエンコーディング及びデコーディングを提供することが、本発明の根底にある課題である。
【課題を解決するための手段】
【００１０】
以下は、本発明のいくつかの態様の基本的な理解を提供するために、本発明の簡略化された概要を提示する。この概要は、本発明の網羅的な概要ではない。その唯一の目的は、後で述べられるより詳細な説明の序文としていくつかの概念を簡略形式で示すことである。
【００１１】
上述した課題は、道路区分を含む道路データ（ナビゲーションデータベースに記憶される）から算出されるルートを提供する方法によって解決される（本明細書において、用語「道路」及び「通り」は同義的に用いられることに注意されたい）。道路は、当技術分野で知られるようにその道路区分によって構成される。道路区分を含む道路データ（例えば、コンピューティングセンターのナビゲーションデータベースに記憶される）からルートを算出するステップ、ルート上の判断地点であって、判断地点のそれぞれで少なくとも２つの道路区分が互いに接続されている判断地点を決定するステップ、決定された判断地点のデータを（例えば、一時的にＲＡＭに、または、メモリディスクに）記憶するステップ、及び決定された判断地点の記憶データに基づいてルートをエンコードするステップを含む、ナビゲーションシステム（例えば、車内ナビゲーションシステム）にルートを提供するコンピュータ実行方法が提供される。データは、それが記憶される前に生成するかまたは、読み込むことができる。エンコーディングの本方法は、個々の道路区分の記憶／エンコーディングを含まず、判断地点のデータを記憶／エンコードするだけである。エンコードされたルートを提供するためには、判断地点のデータをエンコードすることしか必要ではない。このことにより、メモリ要求及び全体の計算の負荷は、従来技術と比較して大幅に削減することができる。
【００１２】
エンコード処理は、車両の外部にあるコンピューティングセンターで実行することができる。車両にインストールされたナビゲーションシステムによるルートガイダンスのために必要とされる算出ルートをエンコードした後に、エンコードされたルートは、それがデコードされる車両のナビゲーションシステムに送信することができる。デコードされたルートは車両のユーザに示すことができ、例えば、それは車内ナビゲーションシステムのスクリーンに表示することができる。コンピューティングセンターでのルートの算出は、車内ナビゲーションシステムのユーザによって開始することができる。コンピューティングセンター及び車内ナビゲーションシステムは両方とも、道路及び道路区分を記憶しているそれらの自身のナビゲーションデータベースを有することができる。コンピューティングセンターのデータベース及び車内ナビゲーションシステムのデータベースの両方とも、同じ道路／道路区分または同じ道路／道路区分のサブセットを記憶することができる。両方のデータベースは、階層的にランク付けされた道路及びそれによりランク付けされた道路区分を記憶することができる（以下に記述する）。
【００１３】
判断地点を決定することは不可欠である。判断地点を決定することは、異なる道路が交差する位置の位置データを読み出すことを含むことができる。一実施例によれば、判断地点を決定することは、ルートの全ての判断地点を識別することと、２つの道路区分だけが互いに接続する判断地点を無視することとを含む。このことにより、エンコーディング及びデコーディングのために必要とされるメモリスペースならびに計算資源に対する要求は、更に削減することができる。
【００１４】
例えば、コンピューティングセンター及び車内ナビゲーションシステムのデータベースに記憶される道路を構成している道路及び道路区分はランクに階層的に分類することができ、判断地点を決定することは、ルートの全ての判断地点を識別することと、ルートの２つの道路区分が互いに接続し、及び、ルートの２つの道路区分と比較して、より下位のランクである付加的な道路区分（ルートの一部である道路区分に付加的な）だけがそこに接続される判断地点を無視することとを含む。特定の判断地点を無視することは、無視された判断地点がルートのエンコーディング／デコーディングのために用いられないことを意味する。ランク付けはハイウェイ、幹線道路、都市道路、田園道路、全国横断道路、周辺道路などに関して道路の重要度に基づいて実行することができる。道路区分のランクはそれが帰属する道路のランクによって定義することができる。
【００１５】
概して、本発明の方法は、比較的長い移動ルート、例えば、５０ｋｍ、１００ｋｍまたは２００ｋｍを超える長さのルートに対して特に役立ち、時間及び計算負荷を節減する。階層的に分類された道路を利用する上記の実施例は、比較的長いルートの中間部分だけに対して、例えば、ルート全体の３０％または４０％または５０％から６０％または７０％または８０％を含むルートの中間部分に対して用いることができる。このように、一実施形態によれば、ルートは開始部分（ルートの出発地点、例えば、車内ナビゲーションシステムの実際の位置を含む）、中間部分及び終了部分（ルートの目的地点を含む）を含み、道路区分はランクに階層的に分類され、判断地点を決定することは、ルートの全ての判断地点を識別することと、ルートの中間部分だけに対して、ルートの２つの道路区分と比較して、より下位のランクである付加的な道路区分だけが接続される判断地点を無視することとを含む。
【００１６】
決定された判断地点の特定の種類のデータは、それに応じてエンコード／デコードされたルートに基づく信頼性が高いルートガイダンスに適していることが分かった。例えば、決定された判断地点の判断地点のデータを記憶することは、判断地点の地理座標、判断地点に入る道路区分の地理方向、判断地点を去る道路区分の地理方向、道路区分が判断地点に入る道路のタイプ、道路区分が判断地点から去る道路のタイプ、及び判断地点からルートの以前の判断地点またはルートの次の判断地点までのルート上の距離（ルートに沿った距離）、の少なくとも１つを記憶することを含むことができる。この例では、この種類のデータが、ルートをエンコードするために用いられる。
【００１７】
すでに述べたように、ルートを提供する方法は、エンコードされたルートをコンピューティングセンターから車内ナビゲーションシステムに送信すること、送信されたエンコードされたルートを車内ナビゲーションシステムで受信すること、及び受信したエンコードされたルートを車内ナビゲーションシステムでデコードすることを含むことができる。デコーディングの間に、以下の手順が非常に効率的であることが分かった。予め定められた出発地点から開始するルート上の第１の判断地点は、その判断地点と関連した情報と一致する道路ネットワークの全ての道路区分を決定することによって、ナビゲーションデータベースに記憶される道路ネットワークと照合される。例えば、判断地点の座標は、考慮中の道路区分のジオメトリの近くになければならず、判断地点から去る道路区分の地理方向は、判断地点のために記憶された、判断地点を去ることと関連した地理的方向に類似していなければならない、などである。
【００１８】
このようにして決定された道路区分を開始のセットとして使用して、道路ネットワーク拡張が始まる。ネットワーク拡張はルートの予め定められた出発地点から始めることができ、反復的に、知られている道路区分の後に続く道路区分が考慮され、このことによりルートの予め定められた目的地点に達するまで、道路ネットワークを拡大する。１つの道路区分から次のものへの移行は、適切なコスト関数によって特徴づけられることもある。
【００１９】
例えば、ネットワーク拡張はダイクストラもしくはＡ＊アルゴリズムまたは当技術分野で公知の技術の類似のアルゴリズムに基づいて実行することができ、判断地点と関連する可能性がある制約を遵守しなければならない場合もあり（例えば、道路区分のランクの制約）、各拡張された道路区分は、（ダイクストラまたはＡ＊の技術と共通であるように）それに到達した、先行する道路区分と関連している。道路ネットワーク拡張が次の判断地点の特性を満たすジャンクションを横断するとすぐに、道路ネットワーク拡張はジャンクションから去る道路区分で終了する。先行するもののシーケンスでバックトラックすることによって、デコードされたルートの現在の範囲は、決定される。それから、ジャンクションから去る道路区分は、次の（以前の拡張と同様の）判断地点などへの道路ネットワーク拡張を始めるために、予め定められた目的地点に最も近い最終的な判断地点に達するまで用いる。
【００２０】
道路ネットワーク拡張が、判断地点と関連した情報が独自にデコードされたルート上の道路区分を決定するのに十分であり、エンコーダ及びデコーダデータベース（例えば、コンピューティングセンター及び車内ナビゲーションシステムのデータベース）が（例えば、同じランク定義を用いて）十分によく一致する場合、デコードされたルート（パス）の拡張でしかなく、他のどの道路区分の拡張でもない点に留意する。これは提案された技術を非常に効率的にするが、それは、第１の判断地点だけが道路ネットワークに照合されればよく（費用のかかる計算の動作である可能性がある）、残りの判断地点は道路ネットワーク拡張（ほとんど計算のコストがかからない）の間に、実行しながら照合されるからである。
【００２１】
次の判断地点が道路ネットワーク拡張の１つの間に確実に識別されることができない場合、いくつかの可能性が生じ、それは、（１）デコーディングが失敗する、（２）拡張がゆるめたパラメータで繰り返される、（３）次の判断地点が道路ネットワークに能動的に照合され、道路ネットワーク拡張が逆方向に実行される、及び、（４）オプション（１）から（３）の組合せ、である。
【００２２】
特に、ナビゲーションデータベースの道路ネットワークは通常いくつかの間引きされた及び集約バージョンに記憶されて、長距離ルート算出の速度を上げる。例えば、全ての道路を含んでいる１バージョンがあり、主要道路を含んでいるだけの別のバージョンがあって、ここでは、下級道路に対する全てのジャンクションが取り除かれている、などである。この定義の１つは、Ｎａｖｉｇａｔｉｏｎ  Ｄａｔａ  Ｓｔａｎｄａｒｄ  ＮＤＳ、ｈｔｔｐ：／／ｗｗｗ．ｎｄｓ−ａｓｓｏｃｉａｔｉｏｎ．ｏｒｇ／において見つけることができる。ランクｒ＿｛ｋ｝がエンコードされたルートのｋ番目の部分と関係し、より高位のランクはより重要な道路（及び、関連ネットワークバージョンのより大きな間引き）を意味する場合、エンコードされたルートのｋ番目の部分はｍｉｎ（ｒ＿｛ｋ−１｝，ｒ＿｛ｋ｝，ｒ＿｛ｋ＋１｝）と関連したネットワークバージョンにデコードすることができる。これは、ルートのデコードの別の著しい高速化につながる。
【００２３】
更に、上記説明の実施例の１つによる方法のステップを実行するためのコンピュータ実行可能命令を有する、１つ以上のコンピュータ可読な媒体を含むコンピュータプログラム製品が提供される。
【００２４】
上述した課題はまた、道路を記憶するように構成されるそれ自身のナビゲーションデータベース、外部のコンピューティングセンターと（例えば、インターネットまたはモバイルネットワークを介して）データを交換するように構成される通信手段と、デコードされたルートを取得するために外部のコンピューティングセンターによってエンコードされて送信される、エンコードされたルートをデコードするように構成されるデータプロセッサ、及びデコードされたルートを表示するように構成されるディスプレイ装置を含むことができる、本明細書に開示された車内ナビゲーションシステムによって対処される。データプロセッサは、エンコードされたルートに含まれるルートの判断地点のデータに基づいてエンコードされたルートをデコードするように、構成される。判断地点の特性の説明を続ける。少なくとも２つの道路区分は、各判断地点に接続している。ルートは、道路区分を含んでコンピューティングセンターのデータベースに記憶される道路データから、外部のコンピューティングセンターによって算出される。車内ナビゲーションシステムのナビゲーションデータベース及びコンピューティングセンターのデータベースは両方とも、道路の表記を記憶した。表記の種類は、例えば、データフォーマット及び精度に関して、異なってもよい。
【００２５】
本発明の実施形態の方法を参照して上記に説明した通り、コンピューティングセンターによってエンコードされる判断地点のデータは、判断地点の地理座標、判断地点に入る道路区分の地理方向、判断地点を去る道路区分の地理方向、区分が判断地点に入る道路のタイプ、道路区分が判断地点から去る道路のタイプ、及び判断地点からルートの以前の判断地点またはルートの次の判断地点までのルート上の距離の少なくとも１つを、含むことができる。
【００２６】
更に、上記説明の実施例及び車内ナビゲーションシステムの外部のコンピューティングセンターの１つによる車内ナビゲーションシステムを含むナビゲーションシステムが提供される。コンピューティングセンターは、コンピューティングセンターのデータベース及び、コンピューティングセンターのデータベースに記憶されるデータに基づいてルートを算出し、算出ルートをルートの判断地点のデータに基づいてエンコードし、エンコードされたルートを車内ナビゲーションシステムに送信するように構成されるデータプロセッサを含む。本ナビゲーションシステムの一実施形態による車内ナビゲーションシステムは、道路を記憶するように構成されるナビゲーションデータベースを含み、コンピューティングセンターのデータベース及び車両内ナビゲーションシステムのナビゲーションデータベースはルートの同じ道路区分を（異なるデータフォーマットにおいてである可能性がある）記憶することができる。
本明細書は、例えば、以下の項目も提供する。
（項目１）
ルートをナビゲーションシステムに提供する方法であって、
道路区分を含む道路データから前記ルートを算出するステップと、
前記ルート上の判断地点を決定するステップであって、少なくとも２つの道路区分が前記判断地点のそれぞれで互いに接続される、前記ステップと、
前記決定された判断地点のデータをメモリに記憶するステップと、
前記決定された判断地点の前記記憶データに基づいて前記ルートをエンコードするステップと
を含む方法。
（項目２）
前記判断地点を決定することが、前記ルートの全ての判断地点を識別することと、２つの道路区分だけが互いに接続する判断地点を無視することとを含む、項目１に記載の方法。
（項目３）
前記道路区分がランクに階層的に分類され、前記判断地点を決定することが、前記ルートの全ての判断地点を識別することと、前記ルートの２つの道路区分が互いに接続し、及び前記ルートの前記２つの道路区分と比較して、より下位のランクである付加的な道路区分だけが接続される判断地点を無視することとを含む、項目１または２に記載の方法。
（項目４）
前記ルートが開始部分、中間部分及び終了部分を含み、前記道路区分がランクに階層的に分類され、前記判断地点を決定することが、前記ルートの全ての判断地点を識別することと、前記ルートの前記中間部分だけに対して、前記ルートの前記２つの道路区分と比較して、より下位のランクである付加的な道路区分だけが接続される判断地点を無視することとを含む、項目１または２に記載の方法。
（項目５）
前記決定された判断地点の１つの判断地点の前記データを記憶することが、
前記判断地点の地理座標と、
前記判断地点に入る道路区分の地理方向と、
前記判断地点を去る道路区分の地理方向と、
道路区分が前記判断地点に入る道路のタイプと、
道路区分が前記判断地点から去る道路のタイプと、
前記判断地点から前記ルートの以前の判断地点または前記ルートの次の判断地点までのルート上の距離と
の少なくとも１つを含む、先行項目のいずれか１項に記載の方法。
（項目６）
前記決定された判断地点の１つの判断地点の前記データを記憶することが、前記判断地点に以前の判断地点から到達する１つ以上の道路の前記ランク及び／または次の判断地点に前記判断地点から到達する１つ以上の道路の前記ランクを記憶することを含む、項目４または５に記載の方法。
（項目７）
前記エンコードされたルートをコンピューティングセンターから車内ナビゲーションシステムに送信すること、前記送信されたエンコードされたルートを前記車内ナビゲーションシステムで受信すること、及び前記受信したエンコードされたルートを前記車内ナビゲーションシステムでデコードすることを更に含む、先行項目のいずれか１項に記載の方法。
（項目８）
項目７に記載の、ルートをナビゲーションシステムに提供する方法の前記ステップを含み、前記デコードされたルートを前記車内ナビゲーションシステムのユーザに表すこと、特に、前記ルートを前記車内ナビゲーションシステムのスクリーン上に表示することを更に含む、ルートガイダンスの方法。
（項目９）
前記ユーザによる入力に応答して、前記車内ナビゲーションシステムから前記コンピューティングセンターにルートを算出するための要求を送信すること、及び前記コンピューティングセンターによって前記ルートを算出することを更に含む、項目８に記載の方法。
（項目１０）
前記車内ナビゲーションシステムで前記受信したエンコードされたルートをデコードすることが、
前記ルートの予め定められた出発地点から開始する前記ルート上の第１の判断地点と、前記車両内ナビゲーションシステムのナビゲーションデータベースに記憶された道路ネットワークを、前記第１の判断地点と関連した前記情報で前記道路ネットワークの全ての道路区分を決定することによって、照合することと、
前記決定された道路区分から始めて道路ネットワーク拡張を開始することと、
それぞれの拡張された道路区分をそれに到達した先例の道路区分と関連付けることと、
前記道路ネットワーク拡張が、前記第１の判断地点に続く前記ルートの次の判断地点の特性を満たすジャンクションを横断する場合、前記ジャンクションから去る道路区分で前記道路ネットワーク拡張を終了して、前記ジャンクションから去る前記道路区分から新たな道路ネットワーク拡張を開始することと
を含む、項目７から９のいずれか１項に記載の方法。
（項目１１）
先行項目のいずれか１項に記載の前記方法の前記ステップを実行するためのコンピュータ実行可能命令を有する１つ以上のコンピュータ可読な媒体を含む、コンピュータプログラム製品。
（項目１２）
外部のコンピューティングセンターとデータを交換するように構成される通信手段と、
デコードされたルートを取得するために、前記外部のコンピューティングセンターによってエンコードされて送信されるエンコードされたルートをデコードするように構成されるデータプロセッサと、
前記デコードされたルートを表示するように構成されるディスプレイ装置と
を含み、
前記データプロセッサは、前記エンコードされたルートに含まれる前記ルートの判断地点のデータに基づいて前記エンコードされたルートをデコードするように構成され、前記ルートの少なくとも２つの道路区分は、前記判断地点のそれぞれで互いに接続される、
車内ナビゲーションシステム。
（項目１３）
車内ナビゲーションシステムであって、前記判断地点の前記データが、
前記判断地点の地理座標と、
前記判断地点に入る道路区分の地理方向と、
前記判断地点を去る道路区分の地理方向と、
道路区分が前記判断地点に入る道路のタイプと、
道路区分が前記判断地点から去る道路のタイプと、
前記判断地点から前記ルートの以前の判断地点または前記ルートの次の判断地点までのルート上の距離と
の少なくとも１つを含む、項目１２に記載の前記車内ナビゲーションシステム。
（項目１４）
ナビゲーションシステムであって、
項目１１または１２に記載の車内ナビゲーションシステム及び前記車内ナビゲーションシステムの外部のコンピューティングセンター
を含み、
前記コンピューティングセンターは、道路を記憶するように構成されるコンピューティングセンターのデータベース及び、前記コンピューティングセンターのデータベースに記憶される前記道路データに基づいてルートを算出し、前記ルートの判断地点のデータに基づいて前記算出ルートをエンコーディングし、前記エンコードされたルートを前記車内ナビゲーションシステムに発信するように構成されるデータプロセッサを含む、
前記ナビゲーションシステム。
（項目１５）
前記車内ナビゲーションシステムが、道路を記憶するように構成されるナビゲーションデータベースを含み、前記コンピューティングセンターのデータベース及び前記車内ナビゲーションシステムの前記ナビゲーションデータベースが前記ルートの前記同じ道路区分を記憶する、項目１４に記載のナビゲーションシステム。
【００２７】
本発明の追加の特徴及び利点を図面に基づいて説明する。記述において、本発明の好ましい実施形態を例示するためのものである添付の図面が参照される。このような実施形態は、本発明の全ての範囲を表すものではないないと理解される。
【図面の簡単な説明】
【００２８】
【図１】車内ナビゲーションシステム及びコンピューティングセンターを含むナビゲーションシステムのコンポーネントを示す。
【図２】車内ナビゲーションシステムを統合することができるテレマティクスシステムを示す。
【図３】図１に示されるナビゲーションシステムの動作のフローチャートを示す。
【図４】道路区分及び判断地点の概念を例示する。
【図５】具体的に選択された判断地点によって表されるルートを例示する。
【発明を実施するための形態】
【００２９】
本開示が以下の詳細な記述ならびに図面において説明するような実施形態に関して記載されている一方で、以下の詳細な記述ならびに図面が、主題事項を開示される特定の例示の実施形態に制限することを意図するものではなく、むしろ、記載されている例示の実施形態は、その範囲が添付の請求の範囲によって定義される各種の態様を単に例証するだけであることを理解すべきである。
【００３０】
次に、本発明の各種の例示の実施形態を説明する。明快さのために、実際の実装の全ての特徴が、この仕様に記載されているというわけではない。もちろん、このような実際の実施形態の開発においては、実装によって変化するシステム関連の制約や業務関連の制約に従うなど、実装に特有な多くの決定を行って、開発者の特有の目的を達成しなければならないことが理解されよう。さらにそのような開発努力は、複雑かつ時間がかかるであろうが、それにもかかわらず、この開示の利益を受ける当業者にとってはシステム開発を始める通常手順であるということが理解されるであろう。
【００３１】
以下の実施形態は充分詳細に説明されており、当業者は本発明を利用することができる。本開示に基づいて、他の実施形態が明白であること、そのシステム、構造、処理または機械的な変更が本開示の範囲を逸脱せずになされ得ることは理解されるはずである。以下の記述では、数値的に具体的な詳細が、開示の完全な理解を提供するために与えられる。しかしながら、本開示の実施形態が具体的な詳細なしで実践可能であることは、明らかであろう。本開示を分かりにくくすることを避けるために、いくつかの周知の回路、システム構成、構造構成及び処理ステップは詳細には開示されない。
【００３２】
本開示は、ここから添付の図面を参照して説明する。各種の構造、システム及び装置は、説明の目的だけのために、及び当業者に周知である詳細によって本開示を分かりにくくしないように、図面では概略的に描写している。それにもかかわらず、添付図面は、本開示の解説的な実施例を記載して説明するために含まれる。本明細書において用いられる語句及びフレーズは、関連した技術に熟練した人々によるそれらの語句の理解と整合した意味を有する、と理解され解釈されなければならない。用語またはフレーズの特別な定義、すなわち、当業者によって理解されるように、通常であるか慣習的な意味とは異なる定義は、本明細書での用語またはフレーズの一貫した使用によってほのめかされることを意図していない。用語またはフレーズが特別な意味（すなわち、当業者によって理解される以外の意味）を有することを意図する限り、そのような特別な定義は、用語またはフレーズに対して直接、及び明解に特別な定義を与える明確な方法で仕様に明示的に記載される。
【００３３】
本発明によるナビゲーションシステムが図１に図示される。ナビゲーションシステムは車内ナビゲーションシステム１と外部のコンピューティングセンター２とを含む。車内ナビゲーションシステム１及び外部のコンピューティングセンター２は、データチャネルＣを介して互いと通信することができる。データチャネルはインターネットまたはモバイルネットワークによって実現することができる。車内ナビゲーションシステム１は、データプロセッサを含むコンピューティング装置（データ処理装置）１０ならびに揮発性及び不揮発性メモリを含む。コンピューティング装置１０は、道路データが記憶されるナビゲーションデータベース１１を含む。ナビゲーションデータベース１１は、関心地点及びグラフィカルオブジェクトについてのデータを保存することもできる。更に、コンピューティング装置１０は、ルートデコーダ１２、表示されたルートのルート地点を算出するためのルート表示生成器１３及びルートガイダンス命令を生成するためのルートガイダンス生成器１４ならびにルート算出コントローラ１５及び通信コントローラ１６を含む。コンピューティング装置１０は、ルートを算出するためのルート算出器（図１に示さず）を含むこともできる。
【００３４】
車内ナビゲーションシステム１は、加えて、ディスプレイ装置１７及びオペレータ制御１８を含む。ディスプレイ装置１７はルートガイダンスのために用いることができ、オペレータ制御１８はユーザ入力のために用いることができる。ルートディスプレイコントローラ１３及びルートガイダンスコントローラ１４は、ナビゲーションデータベース１１及びルート算出コントローラ１５とデータ通信を行い、それらは、それぞれ、ルート表示及びガイダンスを制御するように構成される。オペレータ制御１８を介したユーザによる適切な入力に応答して、ルート算出コントローラ１５は、車内ナビゲーションシステム１の通信コントローラ１６と外部のコンピューティングセンター２の通信コントローラ２５の間の通信を開始する。
【００３５】
コンピューティングセンター２は、コンピューティング装置２０を含む。コンピューティングセンターのデータベース２１のコンピューティング装置２０は、ルート算出器２２と、ルートエンコーダ２３と、ルート算出コントローラ２４と、通信コントローラ２５とを含む。データベース１１及び２１は両方とも、道路データを、特に、同じ道路上についてのデータを記憶するが、おそらく異なるフォーマット及び異なる解像度と詳細度のデータなどである。通信コントローラ２５から受信するデータに基づいて、ルート算出コントローラ２４はルート算出器２２によってルート算出を開始する。ルート算出器２２は、コンピューティングセンター２のコンピューティング装置２０のデータベース２１に記憶されるナビゲーションデータによって、予め定められた出発地点から予め定められた目的地（車両内ナビゲーションシステム１のユーザによって入力される）までのルートを算出する。算出ルートはルートエンコーダ２３によってエンコードされ、エンコードされたルートは、ルートデコーダ１２及びルートガイダンスによってデコードするための車内ナビゲーションシステム１に送信される。
【００３６】
車内ナビゲーションシステム１は、図２に示すようにより大きい自動車テレマティクスシステムに統合することができる。
【００３７】
コンポーネント１００〜１４５及び１７０〜１８２は車両内にインストールされ、その一方で、コンポーネント１５０〜１６１は自動車テレマティクスシステムの一部ではなく、車両のテレマティクスコンポーネントのいくつかと対話することができる外部コンポーネントである。
【００３８】
テレマティクスシステムを備える車両は、車両に配置される視覚フロントエンドインタフェースとして、ディスプレイ１０４（図１に示されるディスプレイ装置１７と同一であってもよい）を含むことができる。ユーザは、タッチ感知スクリーンを介して、ボタンを押すことを介して、聞き取り可能音声及び音声合成を介して、または、当技術分野で公知の他のＨＭＩ（人−マシン対話）コンポーネントを介して、インタフェースと対話することが可能で有り得る。聞き取り可能音声及び音声合成または分析を介した対話は、ユーザから入力を受け取るためのマイクロホン１３１及びＡ／Ｄ変換器１３０を介して、及びユーザに出力を与えるためのＤ／Ａ変換器１２０、増幅器１２１及び１つあるいは複数のスピーカ１２２を介して、行うことができる。視覚フロントエンドインタフェースは、テレマティクスシステムとのユーザの集中化した対話のためにヘッドユニットの一部でもよく、または、例えば、テレマティクスシステムの音声または電話コンポーネントとのユーザの対話のために、１つ以上の専用のヘッドユニット１０５と分離してもよい。
【００３９】
図２に示す例示の実施形態において、通常はＣＰＵまたはＧＰＵまたは組込みシステムである中央処理装置１００は、テレマティクスシステムの少なくとも一部の動作を制御する。しかしながら、本発明は、これに限られておらず、ハードディスクドライブ１４０のような記憶装置からムービーを表示するための後部座席娯楽用オーディオシステムの恐らく一部としてのビデオディスプレイ１４２を備えたＣＰＵ１４１として、特定のテレマティクスコンポーネントまたは一群のテレマティクスコンポーネントに割り当てられる、少なくとも１つの更なる処理ユニットを提供することができる。処理ユニットは、特にテレマティクスシステムのアプリケーションコンポーネントの一部として、命令、コマンド及びルーチンのオンボード処理を可能にする。処理ユニット１００は、非持続的及び持続的な記憶装置１４０に、更に接続することができる。この例示の実施形態において、非持続的な記憶装置はランダムアクセスメモリ（ＲＡＭ）であり、持続的な記憶装置はハードディスクドライブ（ＨＤＤ）またはフラッシュメモリである。
【００４０】
処理ユニット１００は、ユーザが処理ユニットとのインタフェースを取ることを可能にする多くの異なる入力を備えることもできる。この例示の実施形態において、マイクロホン１３１、補助入力１３２、ＵＳＢ入力１２３、ＧＰＳ入力１３３及びブルートゥース（登録商標）入力１０２の全てが設けられている。入力セレクタは、ユーザが各種の入力の間で交換することを可能にするために設けることができる。マイクロホン１３１への入力は、処理ユニットに渡す前に、Ａ／Ｄ変換器１３０によって、アナログからデジタルに変換される。
【００４１】
テレマティクスシステムからの出力は、ビデオディスプレイ１２４及びスピーカ１２２またはステレオ／サラウンド出力を含むが、これらに限定されるものではない。スピーカは、増幅器１２１に接続することができ、その信号を処理ユニット１００からデジタル−アナログ変換器１２０を介して受信することができる。出力は、ブルートゥース（登録商標）アンテナ１７２を有する個人ナビゲーション装置１７０のような遠隔ブルートゥース（登録商標）装置に、ブルートゥース（登録商標）アンテナ１０３を有するブルートゥース（登録商標）トランシーバ１０２を介して行うこともできる。個人ナビゲーション装置との通信は、ＵＳＢコネクタ１２３及び１７１を介して達成することもできる。テレマティクスシステムはナビゲーション装置１３４を更に含むことができ、特に図２に図示される車内ナビゲーションシステム１を含むことができる。ナビゲーション装置１３４は、基地局１５０及びマルチバンドアンテナ１１０または、移動端末１１１を介してＧＰＳユニット１３３及び／またはモバイルネットワーク１６０（プロバイダネットワーク）と対話することができる。しかしながら、本発明の端末システム及びそれを制御するための方法の一実施例によれば、処理ユニットはプロバイダネットワークに対する自身のアクセスはせず、むしろプロバイダネットワークに対する無線データ接続が、無線接続されるか固定してインストールされたネットワークアクセス装置（ＮＡＤ）によって提供されるだけである点に留意しなければならない。
【００４２】
ＮＡＤのための一実施例である移動端末１１１は、具体的に携帯電話、スマートフォン、ＰＤＡなどであってもよく、直接、ＵＳＢコネクタ１２３を介して、または、そのアンテナ１０３を有するブルートゥース（登録商標）トランシーバ１０２のいずれかを介して、処理ユニット１００に接続することができる。マルチバンドアンテナ１１０は、有線によって、または、モデム１０１によって無線で、処理ユニット１００とデータを交換することができる。ここで、基地局１５０及びネットワーク１６０は、テレマティクスシステムの一部ではなく、外側に車両の外部で提供される。いくつかの実施形態において、基地局１５０は、ＷｉＦｉアクセスポイントでもよい。事実、図１のコンピューティングセンター２は、図１の車両１のナビゲーションシステム（図２の参照符号１３４を参照）と、ネットワーク１６０を介して通信することができる。
【００４３】
データは、例えば、移動端末と関連したデータプラン、音声上のデータまたは、ＤＴＭＦトーンを利用して、中央処理装置１００とネットワーク１６０の間で通信することができる。マルチバンドアンテナ１１０及び移動端末１１１は両方とも、基地局またはＷｉＦｉアクセスポイント１５０と双方向にデータを交換することができる。モデム１０１は、セルラタワー１５０との通信によってネットワーク１６０と直接通信することもできる。非限定的な実施例として、モデム１０１はＵＳＢセルラ方式モデムでもよく、通信はセルラ方式通信でもよい。
【００４４】
１つの例示の実施形態において、処理ユニット１００はモデムアプリケーションソフトウェアと通信するためのＡＰＩを含むオペレーティングシステムを備える。モデムアプリケーションソフトウェアは、遠隔ブルートゥース（登録商標）トランシーバ（例えば移動端末１１１のもの）との無線通信を完了するために、ブルートゥース（登録商標）トランシーバ１０２上の埋め込みモジュールまたはファームウェアにアクセスすることができる。別の実施態様では、移動端末１１１は、音声帯域またはブロードバンドデータ通信のためのモデムを含むことができる。ユーザに移動端末１１１と関連したデータプランがある場合、データプランがブロードバンド送信を可能にし、テレマティクスシステムがかなりより広い（データ転送の速度を上げる）バンド幅を使用することができる可能性もある。更に別の実施形態では、移動端末１１１は、車両にインストールされるセルラ通信装置（例えば、限定されるものではないが、モデム１０１）と、置き換えることができる。また別の実施形態において、移動端末１１１は、例えば、８０２．１１ｇのネットワーク（すなわち、ＷｉＦｉ）またはＷｉＭａｘネットワーク上で通信ができる無線ローカルエリアネットワーク（ＬＡＮ）装置と置き換えることができる。一実施形態において、着信データは、音声上のデータまたはデータプランを介して、移動端末１１１を通過してオンボードブルートゥース（登録商標）トランシーバ１０２によって、中央処理装置１００に渡すことができる。
【００４５】
着信または発信または一時的なデータは、そのデータがもはや必要ではなくなる時まで、ＨＤＤ１４０上に、または、ＲＡＭ１４０または他のいかなる記憶媒体にも記憶することができる。ＨＤＤ１４０または他の記憶媒体は、生成されたログファイルを、レポータコンポーネントがそれらを外部分析コンポーネントに発信するまで記憶するためのメモリとして、特に用いることができる。外部分析コンポーネントへのこの移動は、モデム１０１、マルチバンドアンテナ１１０、ブルートゥース（登録商標）トランシーバ１０２または移動端末１１１を介して、例えば、モバイルネットワーク１６０または無線ネットワークに対して実行することができる。
【００４６】
中央処理装置は、様々な他の補助装置１８０と更に通信することができる。これらの装置は、無線１８２または有線１８１の接続（例えばＵＳＢ接続）によって接続することができる。更に、または、代わりに、ＣＰＵ１００は、例えばＷｉＦｉトランシーバ１０７を使用して、車両ベースの無線ルータ１０６に接続することができる。これによって、ＣＰＵがローカルルータ１０６の範囲内の遠隔ネットワークに接続可能なようにすることができる。
【００４７】
処理ユニット１００は、ラジオ、ＣＤプレーヤまたはＤＶＤプレーヤ１４３と更に対話して、オーディオ及び／またはビデオをステレオシステム１２２及び／またはビデオディスプレイ１４２に提供することができる。オーディオ及び／またはビデオは、車両の外部の放送送信機１５１を介してモバイルネットワーク１６０、無線ネットワークまたはデジタル放送プロバイダネットワーク１６１（デジタルオーディオ放送、デジタルビデオ放送）からマルチバンドアンテナ１１０または移動端末１１１を介して提供することもできる。オーディオ及びビデオデータは、上記で説明した接続によってダウンロードするかまたはストリーミングすることができる。ダウンロードの場合、データは、ＨＤＤ１４０または他の記憶装置に一時的にまたは持続的に記憶することができる。更なる処理ユニット１４１は、後でＨＤＤ１４０から記憶データを読み込むことができて、車両のスピーカシステム１２２またはビデオディスプレイ１４２によってビデオ及び／または音声サービスを提供することができる。
【００４８】
処理ユニット１００はマイクロホン１３１及び車両のスピーカシステム１２２と更に対話して、例えば移動端末１１１を介してハンズフリー電話を提供することができる。同様に、処理ユニット１００は移動端末１１１及び車両診断（図示せず）と対話して、緊急呼出しまたは故障呼出しを送信することができる（以下を更に参照）。
【００４９】
処理ユニット１００は、エンジン制御ユニット（ＥＣＵ）１４４と対話してエンジンパラメータを制御するかまたは車両のエンジンを監視することもできる。同様に、処理ユニット１００は、パワートレイン制御モジュール（ＰＣＭ）１４４及び、例えば、限定されるものではないが、タイヤ空気圧監視システム、道路状態センサ、駐車センサ、温度センサ、周囲光センサなどのような、一連のセンサシステム１４５と対話することができる。自動車テレマティクスシステムの範囲内の有線通信は、ＭＯＳＴ（Ｍｅｄｉａ  Ｏｒｉｅｎｔｅｄ  Ｓｙｓｔｅｍｓ  Ｔｒａｎｓｐｏｒｔ）、ＣＡＮ（Ｃｏｎｔｒｏｌｌｅｒ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＩＥＥＥ１３９４または当技術分野で知られる技術を使用して、行うことができる。
【００５０】
上記の通りに、車内ナビゲーションシステム１は、図１に示すようにコンピューティングセンター２に接続している可能性のある、より大きいテレマティクスシステムのフレームワークにおいて作動することができる。図１に示される車内ナビゲーションシステム１及びコンピューティングセンター２の以下の動作は、図３を参照して説明する。初期ステップとして、車内ナビゲーションシステム１のユーザは車内ナビゲーションシステム１のオペレータ制御１８を利用してユーザによって目的地入力までのルートの算出を要求し（５０）、そこにおいて、算出は車内ナビゲーションシステム１そのものよりもむしろ外部のコンピューティングセンター２によって実行されなければならない。コンピューティングセンター２にルートを算出させるユーザの決定の理由は、コンピューティングセンター２で利用可能なより強力な計算資源でもあり得て、または、より最新のナビゲーションデータ及び／または交通状態についての現在の情報にアクセスしたいという願望でもあり得る。ユーザによる要求があるとすぐに、コンピューティングセンター２（ＣＣ）に対する通信が起動される（５１）。例えば、車内ナビゲーションシステム１（ＩＶＮＤ）のルート算出コントローラ１５は通信コントローラ１６を起動させてコンピューティングセンター２の通信コントローラ２５に算出のための要求及びルートの供給を目的地に発信し、すなわち、ＩＶＮＤの通信コントローラ１６はＣＣの通信コントローラ２５からのルートを問い合わせる（５２）。
【００５１】
要求があり次第、ルートがＣＣで算出される（５３）。例えば、ＣＣの通信コントローラ２５は、ＣＣのルート算出コントローラ２４を起動し、それが次にルート算出器２２によるルート算出（５３）及びルートエンコーダ２３による算出ルートのエンコーディング（５４）を開始させる。エンコードされたルートは、ＣＣからＩＶＮＳに送信される（５５）。例えば、ＣＣのルート算出コントローラ２４は、ルートエンコーダ２３からエンコードされたルートを受け取って、ＣＣの通信コントローラ２５にこのエンコードされたルートを提供する。その後、ＣＣの通信コントローラ２５は、エンコードされたルートをＩＶＮＳの通信コントローラ１６送信し、それがＩＶＮＳのルート算出コントローラ１５に受信したエンコードされたルートを提供する。エンコードされたルートはルートデコーダ１２によってデコードされ（５６）、それをＩＶＮＳのナビゲーションデータベース１１の特定のナビゲーションデータ（フォーマット）と照合する。それから、ルートディスプレイコントローラは、ディスプレイ装置１７上にデコードされたルートの表示を開始する。
【００５２】
エンコーディング及びデコーディングは、車内ナビゲーションシステム１が、車内ナビゲーションシステム１そのものとは異なるデータ概念及びフォーマットを一般に使用する異なるシステム（すなわち、コンピューティングセンター）によって算出されるルートを使用することを可能にするために、必要である。コンピューティングセンター２によって送信されるコード化されたデータは、車内ナビゲーションシステム１のソフトウェアアプリケーション及びナビゲーションデータに適合するために、デコードすることができる。本発明により、エンコードされたデータは、ルートを構成している全てまたはいくつかの道路区分よりもむしろ、ルートの判断地点を表す。（ルートの）判断地点は、少なくとも２つの道路区分が判断地点に各々で接続されるという点で、定められる。
【００５３】
言い換えれば、エンコードされたルートは、例えば、ルートをエンコードする前に決定した判断地点の地理位置（地理座標）としてだけ、判断地点のデータを含む。判断地点のデータは、道路区分を表しているデータを含むのではなく、道路区分に関連しているデータを含むことができる。例えば、判断地点のデータは、判断地点に入る道路区分の地理方向及び／または、判断地点を去る道路区分の地理方向を含むことができる。更に、ルートのエンコーディングのために使用する判断地点のデータは、道路区分が判断地点に入る道路及び／または道路区分が判断地点から去る道路のタイプ含むことができる。更にまた、ルートのエンコーディングのために使用する判断地点のデータは、判断地点からルートの以前の判断地点及び／またはルートの次の判断地点までのルート上の距離を含むことができる。
【００５４】
判断地点だけ（及び、道路区分はない）を表しているエンコードされたルートデータは、特に車内ナビゲーションシステム１の側でメモリ需要及び計算の負荷を著しく減らすことを可能にする。図４は、コンピューティングセンター１のルート算出器２２によって算出される可能性のあるルートＲ（実線）を示す。ルートは、コンピューティングセンターのデータベース２１に記憶される道路の道路区分ＲＳによって、構成される。ルートの発見に関係する道路はまた、ルートＲの一部ではない道路区分ｒｓ（破線）を含む。
【００５５】
ルートＲを構成している道路区分ＲＳは、判断地点ＤＰで接続される。図４に示される判断地点ＤＰごとに、判断地点（例えば、左端の道路区分）ＤＰに到達する１つの道路区分ＲＳ及び判断地点ＤＰ（例えば、右端の道路区分）を去る１つの道路区分ＲＳは、識別することができる。判断地点ＤＰのデータは、ルートＲが算出されるコンピューティングセンター２からルートガイダンスのためのルートが必要である車内ナビゲーションシステム１まで、エンコードされた形で記憶されて、送信されることができる。ルートデコーダ１２によってデコードした後に、ルートガイダンスコントローラ１４に利用可能となる記憶された判断地点ＤＰに基づいて、ルートは、コンピューティングセンター２のコンピューティング装置２０で決定される判断地点ＤＰに基づいて、車内ナビゲーションシステム１のユーザに示すことができる。
【００５６】
別の実施形態によれば、全体の処理は更に加速することができ、エンコードされたルートデータに対してのみ特定の判断地点を選択することによって、計算の負荷は更に減らすことができる。図５は、特定の種類の判断地点を無視することを含んでルートをエンコードするための、判断地点を決定する手順を例示する。この手順は、コンピューティングセンターのデータベース２１及び車内ナビゲーションシステム１のナビゲーションデータベース１１に記憶される道路（及び、このことにより道路を構成している道路区分）が階層的にランク付けされる場合、適用することができる。階層的ランク付けは、例えば、道路の重要度に基づいて行うことができる。重要度は、道路のカテゴリ（ハイウェイ、幹線道路、都市道路、田園道路、全国横断道路、周辺道路など）で評価することができる。図５は、大きな重要度（例えば、ハイウェイ）、中間の重要度（例えば、幹線道路）及び小さな重要度（例えば、周辺道路）の道路区分または道路を示す。
【００５７】
算出ルートＲの出発地点ＳＰは、小さな重要度の道路にある。道路区分ＲＳは第１の判断地点ＤＰ１に到達し、別の道路区分は、第１の判断地点ＤＰ１を去って、第３の判断地点ＤＰ３に到達する更なるＲＳが去る第２の判断地点ＤＰ２に到達する。「去る」、「到達する」という用語は、ルートが進むことになっている方向に関連する。判断地点ＤＰ１及びＤＰ２で、互いに接続している２つの道路区分だけがある。明らかに、これらの判断地点は、無視することができて、ルートをエンコードするためには必要とされない。
【００５８】
これに反して、判断地点ＤＰ３は、ルートの一部でない判断地点ＤＰ３及びＤＰ４を接続しているルートの道路区分ＲＳと同じ重要度（ランク）の道路区分ｒｓが判断地点ＤＰ３に接続しているので、ルートをエンコードするために必要である。ルートをたどるためには右折をしなければならない、という情報が与えられなければならない。このように、判断地点ＤＰ３は、エンコードされたルートデータに含まれなければならない。同じことが、ルートの一部ではない２つの道路区分ｒｓ及びルートの一部である２つの他の道路区分ＲＳが互いに接続されている判断地点Ｄ４に対して当てはまる。情報は、判断地点ＤＰ４で右折して中間の重要度の道路に入るために伝えられなければならない。同様に、判断地点ＤＰ６、ＤＰ７、Ｄ１０、Ｄ１１及びＤ１２は、ルートＲをエンコードするために考慮されると決定されなければならない。例えば、判断地点ＤＰ７で、右折して大きな重要度の道路に入るための情報が与えられなければならない。
【００５９】
他方で、図示の例によれば、判断地点ＤＰ５、ＤＰ８及びＤＰ９は無視することができる。これらの判断地点のそれぞれにおいて、判断地点に到達しているそれぞれの道路区分ＲＳと同じランク／重要度のただ１つの道路区分ＲＳが存在し（すなわち、ルートの道路区分）、それに対して、これらの判断地点に接続している他の道路区分ｒｓは、無視される、より下位のランク／重要度の道路の部分である。
【００６０】
図５を参照して説明する手順は、出発地点を含む開始部分及びルートの目的地点を含む終了部分を接続している、ルートの中間部分だけに対して実行することができる。例えば、それは、出発地点（例えば、車内ナビゲーションシステムの実際の位置に対応する）から、車内ナビゲーションシステムのユーザによって入力される可能性のある目的地点までの範囲にわたるルート全体の、１０％から９０％、特に３０％〜７０％または４０％〜６０％の中間部分に対してのみ実行することができる。中間部分は、例えば、実空間の約１０ｋｍ〜約１００ｋｍの移動をカバーすることができる。
【００６１】
本発明が本明細書において教示の利点を有しながら、当業者にとって明らかな、異なるが、等価な方法で修正して、実施することができるので、上で開示される具体例は例示的なものでしかない。そこに含まれる例示的な方法及びステップは、任意の適切な方法で組み合わせることができる。
【図１】
0006781719.tif 000002
【図２】
0006781719.tif 000003
【図３】
0006781719.tif 000004
【図４】
0006781719.tif 000005
【図５】
0006781719.tif 000006