マップデータを生成する方法及び装置、並びにマップデータを用いて経路を決定する方法及びナビゲーション装置
マップに含まれる領域内のナビゲーションできる経路の区域を表すナビゲーションできる複数の区域を含むマップデータを生成するために速度データを処理する方法であり、ある区域を異なる時刻の期間中に通る際に測定された移動速度を含む、少なくとも１つの区域に関する速度データを取得する工程と、各区域の速度データから、該区域を通る際の平均移動速度を含む、毎週繰り返される期間の少なくとも１つの正常速度プロファイルに関するデータを生成する工程と、少なくとも１つの毎週繰り返されない特定の期間に対して、該特定の期間中に前記区域を通る際の予想移動速度を含む異常速度プロファイルを、１つ以上の区域データの各々に対して少なくとも１つ生成する工程と、領域を渡る行路を決定するための経路計画アルゴリズムにおいてナビゲーション装置によって使用されるために、該マップデータの１つ以上の区域の各々に、対応する正常速度プロファイル及び異常速度プロファイルを割り当てる工程と、を含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マップ（地図）データ（特にナビゲーション装置に用いられるマップデータ）を生成する方法及び装置、並びにマップデータを用いて経路を決定する方法及び装置に関するものである。本発明は、携帯ナビゲーション装置において特に応用される。
【背景技術】
【０００２】
トムトムインタナショナルＢＶのＧＯ（登録商標）のようなＧＰＳ技術に基づく電子ナビゲーション装置のためのマップデータは、テレアトラスＮＶ（Ｔｅｌe Ａｔｌａｓ ＮＶ）のような専門的なマップ販売社から来ている。このような装置は携帯ナビゲーション装置（Ｐｏｒｔａｂｌｅ Ｎａｖｉｇａｔｉｏｎ Ｄｅｖｉｃｅ，ＰＮＤ）とも呼ばれている。マップデータは経路案内のアルゴリズムによって使用されるように特別にデザインされており、一般的にＧＰＳシステムからの位置データを使用する。例えば、道路は線、即ちベクトル（例：道路の始点、終点、及び方向。道路の全長は、夫々始点／終点方向のパラメータで独特に定められた、数百の区域で構成される）で表現することができる。したがって、マップはそのような複数の道路ベクトル、夫々のベクトルに関連付けられたデータ（制限速度、移動方向など）、関心のある場所 （Ｐｏｉｎｔ ｏｆ Ｉｎｔｅｒｅｓｔ， ＰＯＩ）、道路名、並びに公園の境界、川の境界など、全てベクトルで定義された地理的特徴のセットである。マップに含まれる全ての内容（例：道路ベクトル、ＰＯＩなど）は、ＧＰＳの座標系と一致または関連する座標系を用いて定義されており、ＧＰＳで決定された装置の位置を、マップに表示される道路に正しく位置付けることを可能にし、目的地までの最適な経路を計画することを可能にする。
【０００３】
テレアトラスはこのマップデータベースを作る作業を、イギリスのオーディナンス・サーベイなどの様々な情報源から得られる基本道路情報から始める。また、データの更新及び確認のための、多数の車両と他のマップ及び航空写真を調べる職員を持っている。このデータはテレアトラスのマップデータベースの中核 となる。このマップデータベースは地理的に関連付けられたデータを用いて継続的に改善されている。そして、データベースはその内容が確認され、トムトムのようなデバイス製造会社に年に４回公開される。
【０００４】
夫々の道路区域は、速度に関するパラメータが関連付けられており、該速度に関するパラメータは、その区域においてどのような速度で移動できるかに関する目安を表し、例えばテレアトラスのようなマップデータを生成したものの平均速度である。速度パラメータは、マップ処理を行うＰＮＤの経路計画アルゴリズムによって利用される。したがって、このような経路計画の精度は速度パラメータの精度に依存する。例えば、現在の装置の位置から目的地まで最も速い経路をＰＮＤに生成させるという選択肢を、ユーザはよくＰＮＤ上に提示される。速度パラメータが正確でなければ、ＰＮＤによって計算された経路は最も速い経路でなくなり得る。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
道路区域の速度プロファイルは交通の密度などのパラメータによって影響されやすいため、そのような速度プロファイルにおけるばらつきは、２つの地点の間に存在する最も速い経路は継続的に同じ経路ではないことを意味する。道路区域の速度パラメータにおける誤りは、不正確な到着予定時刻（Ｅｓｔｉｍａｔｅｄ Ｔｉｍｅ ｏｆ Ａｒｒｉｖａｌ， ＥＴＡ）及び最も速くはない経路の 選択につながり得る。
【０００６】
テレアトラスは、ＧＰＳデータがＰＮＤからアップロードされ、マップデータの区域の速度パラメータを与えるために使われるシステムを開発しており、一日中のあるいくつかの時刻 における、道路区域の実際の速度を示す速度パラメータを提供することを目的としている。
【課題を解決するための手段】
【０００７】
本発明の第１の実施形態によると、マップに含まれる領域内のナビゲーションできる経路の区域を表すナビゲーションできる複数の区域を含むマップデータを生成するために速度データを処理する方法であり、ある区域を異なる時刻の期間中に通る際に測定された移動速度を含む、少なくとも１つの区域に関する速度データを取得する工程と、各区域の前記速度データから、前記区域を通る際の平均移動速度を含む、毎週繰り返される期間の少なくとも１つの正常速度プロファイルに関するデータを生成する工程と、少なくとも１つの毎週繰り返されない特定の期間に対して、前記特定の期間中に前記区域を通る際の予想移動速度を含む異常速度プロファイルを、１つ以上の前記区域データの各々に対して少なくとも１つ生成する工程と、前記領域を渡る行路を決定するための経路計画アルゴリズムにおいてナビゲーション装置によって使用されるために、前記マップデータの１つ以上の前記区域の各々に、対応する前記正常速度プロファイル及び前記異常速度プロファイルを割り当てる工程と、を含むことを特徴とする方法が提供される。
【０００８】
そのような方法は、マップデータに含まれる領域内のナビゲーションできる各区域に、夫々関連付けられた異常速度プロファイルを持つことを確実にし、これらの異常速度プロファイルを用いることによって、正常速度プロファイルを用いた場合より、ナビゲーション装置が特定の時間における正確な交通の流れが得られる。例えば、特定の時間はクリスマスのような祝日、全国的なスポーツイベント又は国家的お祝い／喪のような国家的行事、及び／又は豪雨、豪雪、霧、猛暑などの交通に影響を及ぼし得る異常気象であり得る。そのような、ある道路区域の特定の時間における速度の改善された予想は、マップデータによって示される領域を渡る移動を決定する経路アルゴリズムの精度を上げられ得る。
【０００９】
「毎週繰り返される期間」という用語は、例えば月曜日、火曜日、水曜日、木曜日、金曜日、土曜日、日曜日、平日、週末、及びこれらの一部である月曜日の朝、火曜日の午前８〜９時、火曜日から木曜日までのような、全ての週において発生しなくても高い頻度で繰り返される期間を意味する。この用語は、一年中の特定の時期（例えば、春、夏、秋、冬の週に繰り返される期間）において毎週繰り返される期間を含み得る。
【００１０】
該方法は、各区域に、経路の決定においてナビゲーション装置が前記異常速度プロファイルをいつ使用するべきかを識別する識別子を割り当てる工程を含み得る。該識別子は、１つ以上の特定の期間及び／又は１つ以上の特定の条件（例えば、気候）であり得る。
【００１１】
該方法は、異常な交通振舞いの期間を同定する工程と、１つ以上の前記同定された期間において前記区域を通る際に測定された移動速度を前記速度データから同定することによって前記１つ以上の異常速度プロファイルの各々を生成する工程と、前記同定された速度データから前記区域を通る際の平均移動速度を１つ以上決定する工程とを含み得る。例えば、同定された期間はイギリスの銀行休業日及び／又はクリスマスのような過去の祝日であり得、異常速度プロファイルの１つは過去の祝日において区域を通る際の平均速度であり得る。
【００１２】
代わりに、１つ以上の速度プロファイルの各々を生成する工程は、正常速度プロファイルの平均速度を増加又は減少させることによって決定された速度を含み得る。例えば、特定の期間は、雪や雨などの異常気象が発生した期間であり得、異常気象の際の異常速度プロファイルは、正常速度プロファイルの平均速度を所定の因数で縮小させることで生成され得る。ある実施形態では、異常速度プロファイルは拡大又は縮小の倍率であり得、割り当ての工程は各区域に正常速度プロファイル及び倍数を割り当てることを含み得る。そのような倍数用いることは、特定の期間中の複数の平均速度を含む速度プロファイルを新たに用意することより、必要なメモリの容量が少なくなり得るため、有利であり得る。
【００１３】
該方法は、正常速度の平均速度を基準とする所定の範囲内に含まれない、過去の測定された移動速度の期間を同定する工程と、これらの同定された期間を未来の期間に関連付ける工程とを含む。このように、特定の期間は自動的に同定され得る。
【００１４】
該方法は、特定の期間が、毎月又は毎年のように、毎週繰り返される周期とは異なる周期で発生するかを確認する工程を含み得る。これは、特定の日が将来いつ発生するかを自動的に決定できるようにするために必要になり得る。
【００１５】
特定の期間は、イベントデータベースにおいて捜査することで同定され得る。これらのイベントデータベースは、例えば気象観測所、イベント主催者などの外部情報源から得られ得る。
【００１６】
該方法は、全国的なスポーツイベント、祝祭、天気などの同定された期間に発生する既知のイベントと該同定された期間とを関連付ける工程と、イベントデータベースから類似するイベントが将来いつ発生するかを決定することでいつ異常速度プロファイルを用いるかを同定する工程とを含み得る。
【００１７】
ナビゲーションできる区域は一般的に道路の区域を表すが、乗り物や人などによってナビゲーションできる他の通路、チャンネルなどの区域も表し得る。例えば、道、川、運河、サイクリングロード、運河、鉄道線路などの区域であり得る。
【００１８】
該方法は、ＧＰＳデータを取得する第１ステップを含み得る。そのようなＧＰＳデータの取得は、少なくとも１つで一般的には複数のＰＮＤよりＧＰＳデータをアップロードすることで行われ得る。そのような方法では、ＰＮＤからアップロードされたＧＰＳデータは、該方法の工程において処理されるために保存され得る。
【００１９】
ＧＰＳデータは、１つ以上のナビゲーションできる区域に関連付けられた速度データを生成するために処理され得る。そのような方法は、ある区域における交通の流れの速度はその区域の制限速度であると見込まず、ナビゲーションできる区域において実際に測定された速度が速度データに反映されるため有利である。したがって、ＰＮＤ又はマップデータを用いる他の装置においてより正確な経路計画が可能になる。
【００２０】
速度データは複数のＰＮＤ又は他のナビゲーション装置から受信したデータから生成され得る。複数の装置に基づいてデータを生成することによって、ナビゲーションできる区域の実際の状況により近い速度データが得られることは当業者には明らかであろう。
【００２１】
ある実施形態では、処理は各ナビゲーションできる区域において測定された毎日の速度プロファイルを生成し得る（即ち、ある日の具体的な速度プロファイル；この場合は、ある曜日の具体的な正常速度プロファイル）。特定の日に関しては、処理はある特定の日において測定された異常平均速度を生成し得る（例えば、クリスマスのような毎週繰り返されないイベント）。期間の単位としては、１日が第１の期間として考えられる。
【００２２】
他の実施形態では、処理は他の期間を含む、測定された速度プロファイルを生成することを目的とし得る（即ち、第１の期間より長くあり得る第２の期間）。例えば、ある実施形態では、処理は平日に測定された速度プロファイル及び／又は週末に測定された速度プロファイルを生成することを目的とし得る。他の実施形態では、１つの測定された速度プロファイルを週全体のおいて用い得る。速度プロファイルの期間をより細かくすることで（例えば、１日）、実際の交通の流れに近い速度プロファイルが得られることは当業者には明らかであろう。しかし、期間を細かくすると、測定された速度プロファイルを生成するために必要なデータ量も増加することも明らかであろう。
【００２３】
マップデータは、正常速度プロファイルがナビゲーションできる区域に関連付けられた、第１マップに関するデータと、特定の期間に用いられる、異常速度プロファイルがナビゲーションできる区域に関連付けられた少なくとも１つの第２マップに関するデータと、を含み得る。該方法は、要求に応じて第１マップに関するデータをナビゲーション装置に送信する工程と、第２マップが適用される特定の時間に関するマップデータが要求されると、第２マップの１つに関するデータを送信する工程と、を含み得る。
【００２４】
このように、ナビゲーション装置及び／又はユーザは、いつ交通状況が毎週繰り返される正常交通状況とは異なるかを決定し得、交通状況をより正確に表すデータに基づいてナビゲーション装置の経路アルゴリズムが経路を決定することを確実にするように、第２マップにおけるなデータを要求する。マップデータがナビゲーション装置から中央サーバに送られる方法に比べてダウンロード数を減らすために、第２マップデータにおけるデータは好ましくは中央処理サーバから受信される。
【００２５】
追加的に又は代わりに、１つ以上の第２マップにおけるデータは、第２マップが適用できる特定の期間／日に自動的にナビゲーション装置に送信され得る。このようにすることで、ナビゲーション装置は交通状況をより正確に表すマップデータでアップデートされる。
【００２６】
該方法は、未来の特定の期間にデータを受信する工程と、未来の特定の期間についてのデータを受信すると、異常速度プロファイル又はその１つを特定の期間に関連付ける工程とを含む。修正されたマップデータは該所定の期間に、又はその前にナビゲーション装置に送信され得る。例えば、該特定の期間は、スポーツイベントのような全国的イベントが行われる期間であり得、第２マップのデータはそのような全国的イベント中にマップのナビゲーションできる区域で発生する異常平均速度を含み得る。このように、ナビゲーション装置はマップデータからいつ異常速度データを用いるかを決定することができる。
【００２７】
本発明の第２の実施形態によると、機械可読な命令を記録するデータ記憶媒体であって、命令が機械によって読み込まれると第１の実施形態の方法を機械に実行させることを特徴とする記憶媒体が提供される。
【００２８】
本発明の第３の実施形態によると、マップに含まれる領域内のナビゲーションできる経路の区域を表すナビゲーションできる複数の区域を含むマップデータを生成するために速度データを処理する機械であって、ある区域を異なる時刻の期間中に通る際に測定された移動速度を含む、少なくとも１つの区域に関する速度データを取得する工程と、各区域の速度データから、該区域を通る際の平均移動速度を含む、毎週繰り返される期間の少なくとも１つの正常速度プロファイルに関するデータを生成する工程と、少なくとも１つの毎週繰り返されない特定の期間に対して、該特定の期間中に該区域を通る際の予想移動速度を含む異常速度プロファイルに関するデータを、１つ以上の該区域データの各々に対して少なくとも１つ生成する工程と、該領域を渡る行路を決定するための経路計画アルゴリズムにおいてナビゲーション装置によって使用されるために、該マップデータの１つ以上の区域の各々に、対応する正常速度プロファイル及び異常速度プロファイルを割り当てる工程と、を実行させるように構成されたプロセッサを含むことを特徴とする、機械が提供される。
【００２９】
本発明の第４の実施形態によると、機械可読な命令を記録するデータ記憶媒体であって、命令が機械によって読み込まれると、該機会を第３の実施形態の機械として機能させることを特徴とする記憶媒体が提供される。
【００３０】
本発明の第５の実施形態によると、マップデータに含まれる領域内のナビゲーションできる経路の区域を表すナビゲーションできる複数の区域を含むマップデータが提供され、各ナビゲーションできる区域は関連付けられた速度データがあり、少なくとも１つのナビゲーションできる区域には１つの正常速度プロファイルと、１つ以上の異常速度プロファイルと、ナビゲーション装置がどのような場合に前記正常速度プロファイルではなく前記異常速度プロファイルを経路計画アルゴリズムに用いるべきかを識別する識別子と、が関連付けられている。
【００３１】
本発明の第６の実施形態によると、第５の実施形態のマップデータが記録された、機械可読なデータ記憶媒体が提供される。
【００３２】
本発明の第７の実施形態によると、マップデータを用いて、ある領域を渡る経路を計画する方法であって、前記マップデータは、前記マップデータに含まれる領域における、ナビゲーションできる経路の区域を表す複数のナビゲーションできる区域を含み、前記ナビゲーションできる区域の少なくとも１つは、毎週繰り返される期間における正常速度プロファイルが関連付けられており、前記正常速度プロファイルは前記毎週繰り返される期間に前記区域を通る際の予想移動速度と、前記区域を通る移動時間が前記予想移動時間と大きく異なる場合の特定された条件とを含み、前記方法は、ナビゲーションできる経路の決定の要求を受信する工程と、移動時に前記特定された条件が満たされているかを確認する工程と、前記条件が満たされている場合は１つ以上の他の速度プロファイルを用いて経路を決定し、前記条件が満たされていない場合は前記正常速度プロファイルの前記移動時に対応する前記毎週繰り返される期間の移動速度を用いて経路を決定する工程と、を含む方法が提供される。
【００３３】
このように、該方法は、移動時の通行状況に適切な速度プロファイルを用いる。例えば、特定の状況は特定の日、時間及び日、時間及び／又は日及び位置、交通状況、又は天候状況などであり得る。
【００３４】
他の速度プロファイルは、移動時刻に対応しない毎週繰り返される期間における外区域の正常速度プロファイルであり得る。例えば、特定の状況が移動時刻が祝日であることであれば、経路決定に用いられる該他の速度プロファイルは、平日のプロファイルではなく土曜日又は日曜日の正常速度プロファイルであり得る。
【００３５】
マップデータは、特定の状況の期間において区域を通る際の移動速度を含む異常速度プロファイルを含み得、他の速度プロファイルは異常速度プロファイルであり得る。注文品の速度プロファイルを用いると、異常交通振舞いの時の速度をより正確な予測につながり得る。
【００３６】
ある実施形態では、該方法は影響される領域及び、イベント、交通、又は天候状況などの特定された条件に関するデータを取得する工程と、該影響される領域内にある区域に対して少なくとも１つの異常速度プロファイルを用い、該影響される領域外にある区域に対しては少なくとも１つの正常速度プロファイルを用いる工程と、を含む方法である。このように、該方法はある区域を通る際にその区域だけに局部的に影響を及ぼすイベントを考慮して経路を決定できる。例えば、影響される領域は、豪雪又は豪雨が降る領域、又は交通事故によって影響される領域であり得る。
【００３７】
したがって、該方法は、イベント、交通、及び天候などの状況に関するデータを受信する工程を含み得る。
【００３８】
ある実施形態では、該方法は交通事故又は他のイベントの位置に関するデータを受信する工程と、交通事故又は他のイベントから所定の距離内（例えば、５０ｋｍ又は１００ｋｍ）の区域を同定することによって、影響される領域を決定する工程とを含み得る。
【００３９】
追加的に又は代わりに、該方法はカレンダを用いて特定の状況が満たされたかを決定する工程を含み得る。例えば、カレンダは、祝日や祝祭などの特定の状況がいつ発生するかを同定し得る。
【００４０】
移動時間は、経路決定の要求が受信された時刻から決定され得、又は、経路決定の要求に指定された時刻から決定され得る。
【００４１】
本発明の第８の実施形態によると、マップデータを用いて、ある領域を渡る経路を決定するナビゲーション装置であって、マップデータに含まれる領域における、ナビゲーションできる経路の区域を表す複数のナビゲーションできる区域を含むマップデータであって、該ナビゲーションできる区域の少なくとも１つは、毎週繰り返される期間における正常速度プロファイルが関連付けられており、該正常速度プロファイルは毎週繰り返される期間に該区域を通る際の予想移動速度と、該区域を通る移動時間が外予想移動時間と大きく異なる場合の特定された条件とを含む、該マップデータが保存されたメモリと、ナビゲーションできる経路の決定の要求を受信するための入力と、該条件が満たされている場合は１つ以上の他の速度プロファイルを用いて経路を決定し、該条件が満たされていない場合は該正常速度プロファイルの該移動時に対応する該毎週繰り返される期間の移動速度を用いて経路を決定するように構成された経路計算機と、を含むことを特徴とするナビゲーション装置、が提供される。
【００４２】
該ナビゲーション装置は、交通及び天候状況及びイベントなどの、移動時の現在の状況に関するデータを受信するための受信機を含み得る。
【００４３】
メモリは、祝日及び祝祭のような特定の状況がいつ発生するかを同定するカレンダを保存し得る。
【００４４】
本発明の第９の実施形態によると、機械可読な命令を記録するデータ記憶媒体であって、命令がナビゲーション装置のプロセッサによって読み込まれると、該装置を第１０の実施形態のに従って機能させることを特徴とする記憶媒体が提供される。
【００４５】
道路区域に関連付けられる速度データがここで引用される。各道路区域は、マップを提供するマップデータに含まれるデータによって表されることは、当業者には明らかであろう。ある実施形態では、そのような道路区域を表すデータは速度データへの参照を提供する識別子を含み得る。例えば、該参照は生成された速度プロファイルへの参照を提供し得る。この参照は、参照テーブルの形で提供され得る。
【００４６】
本発明の上記実施形態のいずれにおいても、機械可読な記憶媒体は下記の媒体のいずれかを含み得る：フロッピディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ／ＲＡＭ（−Ｒ／−ＲＷ及び＋Ｒ／＋ＲＷを含む）、ハードディスク、メモリ（ＵＳＢメモリキー、ＳＤカード、メモリスティック（登録商標）、コンパクトフラッシュ（登録商標）カード、又は同様のもの）、テープ、他の光磁気記憶媒体、送信された信号（インターネットのダウンロード、ＦＴＰトランスファなどを含む）、ワイヤ、又は他の適切な媒体。
【図面の簡単な説明】
【００４７】
【図１】ナビゲーション装置によって利用できるＧＰＳシステムの例を概略的に示す図である。
【図２】ナビゲーション装置とサーバとの間における通信のための通信システムの概略図である。
【図３】図２のナビゲーション装置または他の適切なナビゲーション装置の電子構成要素の概略図である。
【図４】ナビゲーション装置の取り付け及び／又はドッキングの配置を示す概略図である。
【図５】図３のナビゲーション装置に使われる構成スタックの概略図である。
【図６】A trace内のＧＰＳの定置とマップとを関連付ける実施形態を概説するフローチャートである。
【図７】平均値を求めるための実施形態を概説するフローチャートである。
【図８】平均値について クラスタ形成を実行するための実施形態を概説するフローチャートである。
【図９】クラスタによって生成され、クラスタリング・アルゴリズムの出力である速度プロファイルのセットの一例を示す図である。
【図１０】道路の区域に関連付けられた、測定された速度プロファイルの質を改善させるために用いられるfallback strategyを概説するフローチャートである。
【図１１】測定された速度プロファイルデータの質がどのように改善されたかを概説するフローチャートである。
【図１２】クラスタによって生成された速度プロファイルが、少なくとも１つのマップの道路区域とどのように関連付けられるかを概説するフローチャートである。
【図１３】典型的でない交通の振る舞いの際に、どのように異常な速度プロファイルが生成されるかを概説するフローチャートである。
【図１４】典型的でない交通振る舞いの際に、ナビゲーション装置がどのように動作し、異常な速度プロファイルを利用するかを概説するフローチャートである。
【発明を実施するための形態】
【００４８】
下記の説明全体を通して、類似の要素には同じ参照番号が使用される。
【００４９】
本発明の実施形態は、ＰＮＤに関連付けられた形で説明される。しかし、本発明はＰＮＤに限定されるものではなく、ルートプランニング 及びナビゲーション機能を提供するようにナビゲーションソフトウェアを携帯形式で実行するように構成された任意の制御演算装置に普遍的に適用できることは明らかである。したがって、本発明によるナビゲーション装置は任意の（限定されることなく）経路計画及びナビゲーション装置も含むべきであり、ＰＮＤ、自動車のような乗り物、又は経路計画及びナビゲーションソフトウェアを実行する携帯用ＰＣ，移動電話、又はパーソナル・デジタル・アシスタント（ＰＤＡ）などのような携帯コンピューティング資源など、任意の実施形態でもよい。
【００５０】
さらに、本発明の実施得形態は道路区域に関連付けて説明されている。しかし、本発明は道、川、運河、サイクリングロード、運河、鉄道線路などの区域のような、ナビゲーションの対象となり得る区域に適用できることは明らかである。これらの区域は、参照の簡略化のため道路区域として一般的に参照される。
【００５１】
ある地点からもう１つの地点までをナビゲートするためでなく、単純にある場所の視覚的情報がほしい場合などでも本発明が用いられることは下記の説明によって明らかになる。そのような場合は、ユーザによって選択された「目的地」は、対応する出発点ではなくてもよく、したがってそのような場合は「目的地」の位置または「目的地」の視覚的情報を参照することは、経路の生成や「目的地」への移動が必要であることを意味することではない。また、目的地が存在することは、対応する出発点の指定が必要であることを意味することではない。
【００５２】
上記のことを念頭において、図１のＧＰＳ及び類似するものは様々な目的に用いられる。一般的に、ＧＰＳは衛星ラジオに基づいたナビゲーションシステムであり、連続的な位置、速度、時間、及び場合によっては制限されない数のユーザの道案内情報を決定することが可能である。以前はＮＡＶＳＴＡＲという名前で知られていたＧＰＳは、非常に正確な軌道で地球周りを回っている複数の人工衛星を含む。これらの正確な軌道に基づいて、ＧＰＳ人工衛星は自らの位置をＧＰＳデータとして任意の数の受信ユニットにでも中継することができる。しかし、ＧＬＯＮＡＳＳ，Ｅｕｒｏｐｅａｎ Ｇａｌｉｌｅｏ ｐｏｓｉｔｉｏｎｉｎｇ ｓｙｓｔｅｍ， Ｃｏｍｐａｓｓ ｐｏｓｉｔｉｏｎｉｎｇ ｓｙｓｔｅｍ，またはＩＲＮＳＳ（Ｉｎｄｉａｎ Ｒｅｇｉｏｎａｌ Ｎａｖｉｇａｔｉｏｎａｌ Ｓａｔｅｌｌｉｔｅ Ｓｙｓｔｅｍ）などのＧＰＳシステムが使われ得ることは理解されるべきである。
【００５３】
ＧＰＳシステムは、ＧＰＳデータを受信するように装備された装置がＧＰＳ人工衛星の信号を探してラジオ周波数をスキャンし始めると実施される。ＧＰＳ人工衛星からラジオ信号を受信すると、装置は複数の周知方法の１つの方法で該人工衛星の正確な位置を決定する。装置はほとんどの場合、３つ以上の異なる人工衛星の信号を得るまでラジオ信号のスキャンを続ける（他の三角測量方法を用いると、位置は２つの信号でも決定することができるが、一般的には行われない）。幾何学的な三角測量を実行する際には、受信機は３つの既知の位置を用いて、人工衛星に対する自らの２次元位置を決定する。これは周知の方法で可能である。更に、４つ目の人工衛星の信号を得ると、同じ幾何学的な計算を用いて周知の方法で受信機の３次元の位置を計算することが可能となる。位置及び速度データは制限されていない数のユーザによってリアルタイムで継続的に更新できる。
【００５４】
図１に示されているように、ＧＰＳシステム１００は地球の周りを回る複数の人工衛星１０２を備える。ＧＰＳ受信機１０６はスペクトラム拡散ＧＰＳ衛星データ信号１０８をデータとして複数の人工衛星１０２から受信する。スペクトラム拡散データ信号１０８は各人工衛星１０２から継続的に発信され、発信された夫々のスペクトラム拡散データ信号１０８はデータストリームと該データストリームが由来する特定の人工衛星１０２が識別できる情報とを含む。一般的にＧＰＳ受信機１０６は、２次元の位置を計算するために少なくとも３つの人工衛星１０２から来るスペクトラム拡散データ信号１０８を必要とする。４つ目のスペクトラム拡散データ信号を受信すると、ＧＰＳ１０６は周知方法を用いて３次元の位置を計算することが可能になる。
【００５５】
図２に示された，ＧＰＳ受信機１０６を備える、又はＧＰＳ受信機１０６につながっているナビゲーション装置２００（即ち、ＰＮＤ）は、移動電話、ＰＤＡ及び／又は移動電話機能を持つ任意の装置のようなモバイルデバイス（不図示）を介して、「モバイル」または電気通信ネットワークのネットワークハードウェアとのデータセッションを成立させることが必要に応じて可能であり、例えばブルートゥース技術を用いたデジタル接続のようなデジタル接続を成立させる。その後、携帯装置はネットワークプロバイダを介して（例えばインターネットを介して）サーバ１５０とネットワーク接続を成立させることができる。したがって、“モバイル”ネットワーク接続はナビゲーション装置２００（この装置は単独で及び／又は車両の中で移動するため「モバイル」であり得、多くの場合モバイルである）とサーバ１５０との間で成立でき、「リアルタイム」または少なくとも「最新」である情報のゲートウェイを提供する。
【００５６】
モバイル装置と、サーバ１５０のような異なる装置との間に（サービスプロバイダを介して）例えばインターネットを用いてネットワーク接続を成立させることは周知の方法で実行することができる。この点において、任意の数の適切なデータ通信プロトコール（例えばＴＣＰ／ＩＰレイヤード・プロトコール）も用いることができる。更に、モバイル装置はＣＤＭＡ２０００，ＩＥＥＥ８０２．１１，ａ／ｂ／ｃ／ｇ／ｎなどの任意の数の通信スタンダードも用いることができる。
【００５７】
したがって、インターネット接続が用いられることが理解でき、該インターネット接続は、例えばデータ接続、ナビゲーション装置２００に内在する移動電話または移動電話機能を介して得られる。
【００５８】
図示されていないが、ナビゲーション装置２００はもちろん移動電話機能を内蔵し得る（例えばアンテナを含むか、又は任意的にナビゲーション装置２００の内部アンテナを使用することを含む）。ナビゲーション装置２００に内蔵された移動電話機能は内部の部品及び／又は挿入式カード（例えば、加入者識別モジュール（ＳＩＭ）カード）を含み得、必要な移動電話機能及び／又はアンテナなどを含む。したがって、ナビゲーション装置２００に内蔵された移動電話機能はナビゲーション装置２００とサーバ１５０との間で、他の移動装置と同様にネットワーク接続を成立させることができる。
【００５９】
電話の設定には、常に変化する携帯電話のモデル、メーカなどと正しく対応できるようにブルートゥース対応のナビゲーション装置を使い得、また、例えばモデル／メーカごとの具体的な設定をナビゲーション装置側に保存して置くことが可能である。この情報のために保存されたデータは更新することができる。
【００６０】
図２には、ナビゲーション装置２００が一般的な（ｇｅｎｅｒｉｃ）通信チャンネル１５２を介してサーバ１５０とつながっている様子が示されており、該チャンネル１５２は数多くの異なる構成のどれを用いても実施できる。通信チャンネル１５２は一般的にナビゲーション装置２００とサーバ１５０とをつなげる、伝播媒体またはパス（Ｐａｔｈ）を表す。サーバ１５０及びナビゲーション装置２００は、その間に通信チャンネル１５２が成立されたとき通信が可能になる（そのような接続はモバイル装置を介するデータ接続、パソコンでインターネットを介する直接接続などであり得る）。
【００６１】
通信チャンネル１５２は特定の通信技術に限定されるものではない。更に、通信チャンネル１５２は１つの通信技術に限定されるものではない。つまり、チャンネル１５２は様々な技術を用いる複数の通信リンクを含み得る。例えば、通信チャンネル１５２は電気的、光学的、及び／又は電磁気的な通信などのための通路を提供するように構成され得る。したがって、通信チャンネル１５２は以下のもの及びその組み合わせを含むが、これらに限定されるものではない：電気回路、ワイヤ及び同軸ケーブルなどの導電体、光ファイバ・ケーブル、変換器、無線周波数（ＲＦ） 、大気、空間など。更に、通信チャンネル１５２はルータ、リピータ、バッファ、送信機、受信機などの中間装置を含み得る。
【００６２】
１つの例示的な構成では、通信チャンネル１５２は電話及びコンピュータネットワークを含む。更に、通信チャンネル１５２は、赤外線通信、マイクロ波周波数通信のような無線周波数通信などのワイヤレス通信を提供し得る。更に、通信チャンネル１５２は、人工衛星通信も可能である。
【００６３】
通信チャンネル１５２を介して発信される通信信号には、ある通信技術に必要又は好ましい信号を含むが、これらに限定されない。例えば、信号は時分割多元接続（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）、符号分割多元接続（ＣＤＭＡ）、グローバル・システム・フォー・モバイル・コミュニケーションズ（ＧＳＭ）、汎用パケット無線システム（ＧＰＲＳ）などの移動体通信技術を用いるように構成され得る。デジタル及びアナログの両方の信号が通信チャンネル１５２を介して送信され得る。これらの信号は通信技術に応じて調節、暗号化、及び／又は圧縮された信号であり得る。
【００６４】
サーバ１５０は、図示されていない要素に加えて、メモリ１５６に接続され、さらに有線又は無線接続１５８によって大量データ保存装置１６０に動作可能なように接続された、プロセッサ１５４を備える。大量データ保存装置１６０にはナビゲーションデータ及びマップ情報が保存されており、サーバ１５０とは別個の装置であり得、又はサーバ１５０の中に含まれ得る。プロセッサ１５４はさらに送信機１６２及び受信機１６４に動作可能なように接続されており、情報を通信チャンネル１５２を介してナビゲーション装置２００との送受信を行う。送受信された信号はデータ、通信、及び／又は他の伝播された信号であり得る。送信機１６２及び受信機１６４は、ナビゲーションシステム２００の通信構成に使用された通信要件及び通信技術に応じて選択または設計され得る。更に、送信機１６２及び受信機１６４の機能は、１つの送受信機に合体され得る。
【００６５】
上記のように、ナビゲーション装置２００は、通信チャンネル１５２を介してサーバとの通信が可能であり、通信チャンネル１５２を介して送信機１６６及び受信機１６８を用いて信号及び／又はデータを送受信する。これらの装置はサーバ１５０以外の装置との通信にも用いられ得る。更に、送信機１６６及び受信機１６８は、ナビゲーションシステム２００の通信構成に使用された通信要件及び通信技術に応じて選択または設計され、送信機１６６及び受信機１６８の機能は図２に関連付けて上記に説明されているように１つの送受信機に合体され得る。もちろん、ナビゲーション装置２００は他のハードウェア及び／又は機能的部品を備えており、これらは後で詳細に説明される。
【００６６】
サーバメモリ１５６に保存されたソフトウェアはプロセッサ１５４に命令を提供し、サーバ１５０がナビゲーション装置２００にサービスを提供できるようにする。サーバ１５０によって提供される１つのサービスは、ナビゲーション装置２００からのリクエストを処理することと、ナビゲーションデータを大量データ保存装置１６０からナビゲーション装置２００に送信することとを含む。サーバ１５０によって提供できるもう１つのサービスは、希望されるアプリケーションのために様々なアルゴリズムを用いてナビゲーションデータを処理することと、これらの計算の結果をナビゲーション装置２００に送信することとを含む。
【００６７】
サーバ１５０は、ナビゲーション装置２００が無線チャンネルを介してアクセスできる遠隔のデータ・ソースである。サーバ１５０は、ローカルエリア・ネットワーク（ＬＡＮ），広域ネットワーク（ＷＡＮ），仮想プライベート・ネットワーク（ＶＰＮ）などに含まれるネットワークサーバを含み得る。
【００６８】
サーバ１５０はデスクトップまたはノートブックのようなパソコンを含み得、通信チャンネル１５２はパソコンとナビゲーション装置２００とを接続させるケーブルであり得る。代わりに、パソコンをナビゲーション装置２００とサーバ１５０との間において接続させ、サーバ１５０とナビゲーション装置２００との間にインターネット接続を成立させるようにし得る。
【００６９】
ナビゲーション装置２００には情報ダウンロードを介してサーバ１５０から情報が提供され得、該情報は時々またはユーザがナビゲーション装置２００をサーバに接続させた際、自動的に更新され得、及び／又は無線移動接続装置及びＴＣＰ／ＩＰ接続などを介して、サーバ１５０とナビゲーション装置２００との間でより継続的で頻繁に接続が成立される場合はよりダイナミックに更新され得る。多くの計算を処理するためには、サーバ１５０にあるプロセッサ１５４を用いてその大半を処理することができるが、ナビゲーション装置２００のプロセッサ（不図示）も大量の処理や計算を行うことができ、多くの場合はサーバ１５０への接続と関係なくそのような作業が可能である。
図３を参照すると、ナビゲーション装置２００のブロック図はナビゲーション装置２００の全ての構成要素が含まれているのではなく、いくつかの例示的な部品を示していることが明らかである。ナビゲーション装置２００はハウジングの中に配置されている（不図示）。ナビゲーション装置２００は、例えば上記のプロセッサ２０２を備える処理回路を含み、プロセッサ２００は入力装置２０４及び表示画面２０６のような表示装置に連結されている。入力装置２０４の数はいくつでもよく、キーボード装置、音声入力装置、タッチパネル及び／又は他の周知の情報入力装置を含み得る。同様に、表示画面２０６は任意の表示画面であり得、例えば液晶表示（ＬＣＤ）などを含み得る。
【００７０】
ある構成では、入力装置２０４と表示画面２０６が、タッチパネルのような入力兼表示装置として一体化されており、一体化された入力兼表示装置は情報の入力（直接入力、メニュー選択など）及び情報の表示の両方を可能にするタッチパッドまたはタッチ画面入力２５０を含み、これによってユーザは常時画面２０６の一部をタッチすることだけで、表示された複数の選択肢の１つを選択したり、複数のバーチュアル或いは“ソフト”ボタンを押すことが可能となる。これに関しては、プロセッサ２０２は、タッチスクリーンとともに作動するグラフィカル・ユーザー・インターフェース（ＧＵＩ）を支持する。
【００７１】
ナビゲーション装置２００において、プロセッサ２０２は接続２１０を介して入力装置２０４に動作可能なように接続され、入力装置２０４からの入力情報を受信することができ、さらには少なくとも１つの表示画面２０６及び出力装置２０８に夫々の出力接続２１２を介して情報を出力するように接続されている。ナビゲーション装置２００は、例えば音声出力装置（例えばスピーカ）などの出力装置２０８を備え得る。出力装置２０８は、ナビゲーション装置２００のユーザに音声情報を生成できるように、入力装置２０４も同様にマイク及び音声入力指示を受け取るソフトウェアを含むことができる。更に、ナビゲーション装置２００は追加的な入力装置２０４及び／又は出力装置を備え得、例えば音声入力／出力装置を備え得る。
【００７２】
プロセッサ２０２は接続２１６を介してメモリ２１４に動作可能なように接続されており、接続２２０を介して入力／出力（Ｉ／Ｏ）ポート２１８と情報を送受信できるように構成されており、Ｉ／Ｏポート２１８はナビゲーション装置２００の外部装置であるＩ／Ｏ装置２２２に接続可能である。外部Ｉ／Ｏ装置２２２は、イヤピースのような外部聴取装置を含み得るが、これに限定されない。Ｉ／Ｏ装置２２２への接続は有線又は無線を介する任意の外部装置への接続であり得、例えばハンズフリー操作及び／又は音声作動を可能にするカーステレオユニットへの接続、イヤピースやヘッドフォンへの接続、及び／又は携帯電話への接続などがあり、携帯電話への接続はナビゲーション装置２００とインターネット又は他の任意のネットワークとの接続を成立させるために用いられ、及び／又はインターネットまたは他のネットワークを介してサーバへの接続を成立させるために用いられ得る。
【００７３】
ナビゲーション装置２００のメモリ２１４は不揮発性メモリ（例えばプログラムコードを保存するため）の一部、及び揮発性メモリ（例えばプログラムコードが実行されるとデータを保存するため）の一部を備える。ナビゲーション装置は更にポート２２８を備え、ポート２２８は接続２３０を介してプロセッサ２０２と通信し、取り外し可能なメモリカード（一般的にカードと呼ばれる）が装置２００に入れられるようにする。説明される実施形態では、ポートにはＳＤ（Ｓｅｃｕｒｅ Ｄｉｇｉｔａｌ）カードが加えられるように構成されている。他の実施形態では、ポートは異なる形式のメモリ（例えばコンパクトフラッシュ（登録商標）（ＣＦ）カード、メモリスティック（登録商標）、ｘＤメモリカード、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）フラッシュドライブ、ＭＭＣ（マルチメディア）カード、スマートメディアカード、マイクロドライブ等）が接続できるようにし得る。
【００７４】
図３は、接続２２６を介する、プロセッサ２０２とアンテナ／受信機２２４との間の動作可能接続をさらに示しており、アンテナ／受信機２２４は例えばＧＰＳアンテナ／受信機であり得、したがって図１のＧＰＳ受信機のように機能する。参照番号２２４で指定されたアンテナ及び受信機は、説明のために概略的に１つとしてあらわしているが、アンテナ及び受信機は異なる位置に配置される部品であり得、アンテナは例えばＧＰＳパッチアンテナ又はらせん状のアンテナであり得る。
【００７５】
当業者であれば、図３に示された電子部品は１つ以上の電源（不図示）によって従来のように電力が供給されることは明らかである。そのような電源は内部電池及び／又は低電圧直流（ＤＣ）電源の入力または他の任意の 適切な構成をも含み得る。当業者には明らかであるように、図３に示された部品の異なる配置も考えられる。例えば、図３に示された部品は、有線及び／又は無線の通信及びそのようなものによってお互いに通信し得る。したがって、ここに説明されるナビゲーション装置２００は携帯又はハンドヘルドのナビゲーション装置２００であり得る。
【００７６】
さらに、図３の携帯又はハンドヘルド・ナビゲーション装置２００は、周知の様式で自転車、オートバイ、車、又はボートのような乗り物につなげる、又は「ドッキング」させることができる。そのようなナビゲーション装置２００は、携帯又はハンドヘルド使用のためドッキング位置から取り外すことができる。異なる実施形態では、ユーザのナビゲーションを可能にするために、装置２００はハンドヘルド装置として構成され得る。
【００７７】
図４を参照すると、ナビゲーション装置２００は、一体化された入力兼表示装置２０６及び図２に示されたほかの部品（内部ＧＰＳ受信機２２４、プロセッサ２０２、電源（不図示）、メモリシステム２１４などを含むが、これらに限定されない）を含む１つのユニットであり得る。
【００７８】
ナビゲーション装置２００は、アーム２５２に固定され得、アーム２５２は乗り物のダッシュボード／窓などに吸着カップ２５４を用いて固定され得る。このアーム２５２は、ナビゲーション装置２００がドッキングされ得るドッキング・ステーションの一例である。ナビゲーション装置２００は、例えばアーム２５２にカチッとはまるような結合でドッキング又は結合され得る。すると、ナビゲーション装置２００はアーム２５２に対して回転可能になり得る。ナビゲーション装置２００とドッキング・ステーションとの結合を分離させるためには、例えば、ナビゲーション装置２００のボタンを押すことで外れるようにし得る。ナビゲーション装置２００とドッキング・ステーションとの結合及び分離に適している構成は、当業者には周知である。
【００７９】
図５を参照すると、プロセッサ２０２及びメモリ２１４はお互いに協力して、ナビゲーション装置２００の機能的ハードウェア部品２８０と、装置によって実行されるソフトウェアとの間のインタフェースとして機能するＢＩＯＳ（Ｂａｓｉｃ Ｉｎｐｕｔ／Ｏｕｔｐｕｔ Ｓｙｓｔｅｍ）を支持する。次に、プロセッサ２０２はメモリ２１４からオペレーティング・システム２８４をロードし、（既述したルート計画機能及びナビゲーション機能のいくつか又は全てを実行する）アプリケーションソフト２８６が実行できるような環境を整える。アプリケーションソフト２８６は、マップの表示、ルート計画、ナビゲーション機能及び他の関連する機能などのナビゲーション装置の中心的な機能をサポートするＧＵＩを含む、操作環境を提供する。この点において、アプリケーションソフト２８６の一部はビュー生成モジュール２８８を備える。
【００８０】
説明されている実施形態では、ナビゲーション装置のプロセッサ２０２は、アンテナによって受信されたＧＰＳデータを受信するように、そして時々そのＧＰＳデータをその受信時のタイムスタンプと共にメモリ２１４保存し、ナビゲーション装置の位置記録を蓄積するように、プログラムされている。そのように保存されたデータ記録はＧＰＳの測定位置と考えられ得る。即ち、ナビゲーション装置の位置の測定位置であり、緯度、経度、タイムスタンプ、及び精度レポートを備える。
【００８１】
ある実施形態では、データは実質的には定期的に保存され、例えば５秒ごとに保存され得る。当業者には他の間隔を用いることが可能であることが明らかであり、データの分解能とメモリの容量のバランスがあることが明らかである（即ち、データをより多くとることでデータ分解能は上がるが、そのデータを保存するためにより大きいメモリ容量が必要となる）。しかし、異なる実施形態では、データの分解能は実質的に１秒ごと、１０秒ごと、１５秒ごと２０秒ごと、３０秒ごと、４５秒ごと、１分ごと、２，５分ごと（または、これらの間の任意の間隔）であり得る。したがって、装置のメモリには、様々な時点における装置２００の位置に関する記録が蓄積されている。
【００８２】
ある実施形態では、間隔が長くなると、得られるデータの質が低下することがあり得、低下の程度はナビゲーション装置２００の移動速度にもよるが、間隔の時間として１５秒が、適切な上限となり得る。
【００８３】
ナビゲーション装置２００は一般的に自らの位置に関する記録を蓄積するように構成されているが、ある実施形態では移動の開始時又は終了時においてデータの記録を所定の期間行わない。そのような構成を用いることで、ユーザの家屋及びユーザが頻繁に訪れる場所などを保護することが可能となり、ナビゲーション装置２００のユーザのプライバシーを守ることができる。例えば、ナビゲーション装置２００は移動開始から約５分又は約１マイル（１．６ｋｍ）に関するデータを保存しないように構成され得る。
【００８４】
異なる実施形態では、ＧＰＳは定期的に保存される訳ではなく、所定のイベントが発生するとメモリに保存されるように構成され得る。例えば、プロセッサ２０２は、道路の分岐点、道路区域の変更、又はそのようなイベントが発生するとＧＰＳデータを保存するようにプログラムされ得る。
【００８５】
さらに、プロセッサ２０２は、時々装置２００の位置に関する記録（即ち、ＧＰＳデータ及びタイムスタンプ）をサーバ１５０にアップロードするように構成されている。ナビゲーション装置２００が常在又はほぼ常在する通信チャンネル１５２を持つような実施形態では、通信チャンネル１５２によるサーバ１５０への接続及びデータのアップロードは定期的に行われ、例えば２４時間ごとに行われ得る。当業者には、他の間隔を用いることも可能であることが明らかであり、その間隔は１５分、３０分、１時間、２時間、５時間、１２時間、２日、１週間、又はこれらの間の任意の間隔であっても良い。そのような実施形態においては、プロセッサ２０２は、位置の記録を実質的にリアルタイムでアップロードするように構成され得、このような構成はデータ送信の間隔が短くなることを意味し、疑似リアルタイムと考えることがより正しい。そのような疑似リアルタイム実施形態では、ナビゲーション装置はメモリ２１４内、又はポート２２８に挿入されたカード内にＧＰＳ測定位置をバッファできるように構成され得、又、所定の数の測定位置が保存されるとこれらを送信するように構成され得る。この所定の数は２０、３６、１００、２００程度、又はそれらの間の任意の数でもあり得る。当業者には、この所定の数はメモリ２１４／ポート２２８のカードの容量にある程度支配されることが明らかである。
【００８６】
常在する通信チャンネル１５２を持たない異なる実施形態では、プロセッサ２０２は、通信チャンネル１５２が作られるとサーバ１５０に記録をアップロードするように構成され得る。通信チャンネル１５２が作られることは、例えばナビゲーション装置２００がユーザのコンピュータに接続される時などである。このような実施形態でも、ナビゲーション装置２００はメモリ２１４内、又はポート２２８に挿入されたカード内においてＧＰＳ測定位置をバッファできるように構成され得る。メモリ２１４又はポート２２８に挿入されたカードがＧＰＳ測定位置 で満たされた場合はナビゲーション装置は最古のＧＰＳ測定位置を削除するように構成され得、したがって先入れ先出し（ＦＩＦＯ）バッファであると考えられる。
【００８７】
説明される実施形態では、位置の記録は１つ以上の軌跡を含み、夫々の軌跡は２４時間の期間内のナビゲーション装置２００の移動を表す。それぞれの２４時間の期間は暦日と一致するように構成されているが、必ずしもこのようにする必要はない。
【００８８】
一般的に、ナビゲーション装置２００のユーザは、装置の位置に関する記憶がサーバ１５０にアップロードされることに対して承認する。承認が得られなかった場合は、記録はサーバにアップロードされない。ナビゲーション装置及び／又は装置が接続されたコンピュータは、位置記録の使用に関してユーザに承認を要請するように構成され得る。
【００８９】
サーバ１５０は装置の位置記録を受信し、処理のため大量データ保存装置１６０に保存するように構成されている。したがって、ナビゲーション装置２００がアップロードした、複数の装置の位置記録が、時間とともに大量データ保存装置１６０に蓄積される。
【００９０】
上記のように、大量データ保存装置はマップデータも保存し得る。そのようなマップデータは、道路区域、注目すべき場所の位置など、マップに載っている一般的な情報を提供する。
【００９１】
最初の工程として、サーバ１５０はマップデータと、受信した位置記録に含まれるＧＰＳ測定位置とのマップマッチング機能を行うように構成されており、そのような工程は、図６に関連付けて説明されている。そのようなマップマッチングは、位置記録は受信されているため、いわゆるリアルタイムで行われてもよく、又は大量データ保存装置１６０から位置記録が再び読み込まれた際に行っても良い。
【００９２】
マップマッチングの精度を改善させるために、下記のように位置記録の前処理を行う。各ＧＰＳ軌跡（即ち、２４時間分のＧＰＳデータ）は１つ以上の移動に分けられ（６００）、各移動はナビゲーション装置２００の１つの移動であり、後の処理のために保存されたものを表す。
【００９３】
各移動において、ナビゲーション装置から受信したＧＰＳ測定位置の中で精度に関するレポートが十分に高くないものは拒絶される。したがって、ある実施形態では、ある測定位置に関して３つ未満の人工衛星１０２からのシグナルしかナビゲーション装置２００に受信できていない場合は、その測定位置は拒絶され得る。更に、各移動は、２つの測定位置間の報告された時間がある限界の値を超えると区切られる（６０４）。この前処理工程を通った各移動はマップマッチングの方に通される。
【００９４】
これに関連して、区切られた移動は、連続したＧＰＳ測定位置の間に、所定の時間よりも大きい所定の時間間隔が存在する移動である。 したがって、乗り物が停止したことが推論でき、最初の移動が終わり、2番目の移動が始まったと考えるべきである。したがって、区切られた移動は、２つの別個の移動となる。
【００９５】
しかし、ＧＰＳの信号が届かなかったことが原因でＧＰＳ定位の間にギャップが生じることもあり得るため、１つの移動を区切る前に、乗り物の位置が変わったかをチェックする。そして、そのような状況である場合は移動を区切ることは行わない。説明される実施形態では、この所定の時間はおおよそ３分である。しかし、１５秒、３０秒、１分、９０秒、２分、５分、１０分、又はこれらの間の任意の時間など、他の任意の適切な時間が該所定の時間として用いられることは当業者には明らかである。ここに説明されるように、ＧＰＳ測定位置を送信するナビゲーション装置２００の平均速度がある所定の限度より低い場合、ある実施形態では、データは後の処理において拒絶され得る。そのような実施形態は、衝突などの事故後に発生し得る渋滞に関する情報を排除し、定常状態の交通の流れをより正確に表すデータを残すため、有用であり得る。
【００９６】
次に、各移動を順に取り、その移動に含まれる定位をマップデータ内のマップにマッチングする。各マップは複数の道路区域を備えており、道路区域に沿って移動することが可能であり、各区域は直線のベクトルでマップ上に表わされている。
【００９７】
サーバ１５０のプロセッサ１５４において実行されているプログラムコードは、ある区域の中に位置する測定位置、又はある区域内で発生したと考えても良いほど（即ち、該区域の距離限度内にある）その区域に十分に近い測定位置が見つかるまで処理中の測定位置から離れるように構成されたマップマッチング機能 を提供する。この限度を用いることで、１００％以下のＧＰＳ精度を許し、道路を直線状のベクトルに分解して得られる圧縮効果を可能とする。
【００９８】
各移動は最初の測定位置（即ち、移動における１番目の測定位置）を持っており、この最初の測定位置は、区域の選択を絞るために使え得る同定された測定位置がまだ存在しないため、同じ移動内における他の測定位置より、区域と関連付けることが難しい。もし、複数の区域が１番目の測定位置の限度内に含まれる場合は（６０６）、アルゴリズムは、同じ移動内における次のＧＰＳ測定位置（即ち、２番目の測定位置）を参照し、２つの測定位置間（即ち、１番目の測定位置と２番目の測定位置の間）の距離に対応して可能な動きに基づいて、複数の区域からいくつかのルートのセットを生成する。２番目の測定位置を用いても、１番目の測定位置に関して１つの区域候補に至らない場合は、アルゴリズムは同じ移動内の３番目の測定位置に移り、１番目の測定位置に関して１つの候補を探し出すために、可能性のあるルートを生成し、比較する。この工程は、１つの移動における残りのＧＰＳ測定位置が処理されるまで続く。
【００９９】
このような実施形態の利点は、１番目の測定位置だけでは複数の区域の近辺に存在し得、そしてこれらの区域を区別することはできないが、更なる動き（即ち、２番目及び３番目の測定位置）を用いることで、１番目の測定位置に関連する区域の正体を決定することが可能になる。したがって、移動の１番目の区域はマップマッチング機能 によって決定される。移動の１番目の区域が決定されると、更なる区域を同定するために更なる測定位置を処理する。もちろん、次の測定位置が１番目の測定位置と同じ区域内に位置することは可能である（６１２）。
【０１００】
したがって、移動におけるその後の測定位置は、同じ区域の距離限度内に含まれるかを決定するために処理され（６１０）、マップマッチング機能はその区域と距離限度内に位置する測定位置とを関連付けるように構成されている。マップマッチング機能によって処理された測定位置が距離限度内に入っていないと、その測定位置に対応する新たな区域候補を生成するように構成されている。しかし、次の区域が、直前に処理された区域の端につながるようにする限定を加えることも可能である。これらの隣接する区域は、基礎をなすマップデータからマップマッチング機能によって得られる。
【０１０１】
距離限度内に存在する区域がないこと、又は１つの区域に絞ることができないことにより、前の区域に続くある測定位置に対してマップマッチング機能が区域を同定できない場合は、単独のマッチが成立する１つの区域を同定するまで移動を制約するために、マップマッチング機能は更なる測定位置を探り続ける（６１６）。つまり、ｎ番目の定位が１つだけの区域に関連付けられない場合、区域の同定をさらに絞るためにｎ＋１番目の測定位置を用いる。ｎ＋１番目の定位が１つの区域の同定につながらない場合は、ｎ＋２番目の測定位置を用いる。いくつかの実施形態では、この処理は１つだけの区域が同定されるまで、又は移動内の全てのＧＰＳ測定位置が同定されるまで、続けられる。
【０１０２】
マップマッチング機能は単独の区域を同定するように構成されている。説明される実施形態では、マップマッチング機能は継続する経路を作ることを試みることなく、ただ区域を測定位置にマッチングしていく。異なる実施形態では、マップマッチング機能は継続する経路を作ることが望ましい。
【０１０３】
したがって、処理が終わるとマップマッチング機能は、分析中の移動においてナビゲーション装置２００の動きが沿った道路区域の一連を取得する。次に、マップマッチング機能はこれらの道路区域を処理し、ＧＰＳ測定位置から進入時間及び該区域の通過時間を割り当てる。これらの割り当てられた時間は、後の処理のため大量データ保存装置１６０に保存される。各区域に複数のＧＰＳ測定位置が保存されていることもあり得る。しかし、各区域に対して関連付けられたＧＰＳ測定位置の数がいくつであれ、区域における平均速度は入っている時間、ＧＰＳ定位及び区域の長さ（この実施形態ではマップデータ内に保存されている）を用いて計算される。この平均速度は、対応する割り当てられた時間及び区域と関連付けられ、大量データ保存装置１６０に保存される。道路区域における交通の流れの速度に関連し、その区域に割り当てられた情報は、その道路区域の速度データにとして考えられ得る。
【０１０４】
サーバ１５０は、割り当てられた時間を処理し、それから１つ以上の平均値を下記のように生成する平均値機能を提供するために、平均値を計算するプログラムコードをプロセッサ１５４において実行するように構成されている。この実施形態で用いられる平均値計算工程は、図７を参照しながら説明される。
【０１０５】
工程の第１ステップ（７００）では、平均値機能は、処理中のマップにおける各道路区域の平均速度をグループ化する。各道路区域のグループにおいて、平均値機能は、所定の時間間隔内の平均速度をグループ化するようにさらに構成されている（７０２）。したがって、同じ時間内（たとえば、８：００ＡＭから８：５９ＡＭの間）で発生する平均速度は同じグループに含まれ、更に分析される。説明されている実施形態では、時間は１時間であるが、必ずしも１時間であることはなく、時間の長さを短くするとデータの分解能は上がるが、同時に保存に必要な容量も増えてしまうことは当業者には明らかであろう。他の適切な時間としては、実質的に、１分、５分、１０分、１５分、３０分、２時間、６時間、１２時間、またはこれらの間の任意の時間でもよい。
【０１０６】
ここで説明されている実施形態では、平均速度は、中央標準時間ではなく 、処理されるマップに含まれる領域の現地時間で保存されている。そのような方法は、交通に関するものに関する自然な基盤を提供するため、便利である。
【０１０７】
１つの移動において発生した平均速度が所定の時間にグループ化される前に、平均速度はデータの質を改善させるために選別される。この実施形態では、所定の範囲内に含まれる平均速度だけがグループに追加される。この実施形態では、所定の速度上限（１８０ｋｍ／ｈなど）を超える速度を排除し、所定の速度下限（２ｋｍ／ｈ）を下回る速度も排除する。当業者には、ある区域の平均速度をはるかに下回る速度は、その区域における交通の問題（例えば、渋滞など）と関連があり得ることが明らかであろう。したがって、そのような状況に関するデータを含むことは、通常の状態を示すものとして考える場合、全体の精度を低下させ得る。他の実施形態では、許可される最大の速度は、その区域の制限速度であり得るが、そのような情報は処理されるマップデータにおいては不正確であり得ること、そしてある区域の制限速度は実際にその区域の交通状況を正確に表すものではないこともあり得るというのは、当業者には明らかである。
【０１０８】
所定の時間にグループ化することが実行されると、道路区域ごとの平均速度が所定の時間ごとに計算される。例えば、８：００ＡＭから８：５９ＡＭまでの時間における全ての速度が、道路区域ごとに平均化される。平均速度を計算するためにはいくつかの選択肢があり、算術平均又は調和平均を用いる方法、或いは中央値を計算する方法がある。実際に、ある実施形態では、後の用途によって異なるデータセットに異なる重みを付けることができる。
【０１０９】
したがって、説明されている実施形態、及び処理されるマップには、マップの各道路区域には２４個の平均速度が生成されており、これらは所定の１時間の時間間隔における平均速度である。もし異なる長さの時間が用いられると、異なる数の平均速度が生成されることは明らかである。更に、全ての道路区域が全ての時間における平均速度を持っているとは限らないことも明らかであり、これは、ある道路は交通量が少なく、特に早朝などの時間帯は交通量が少ないためである。
【０１１０】
しかし、区域ごとの平均速度を更に使用する前に、品質のチェックが行われる（７０６）。この実施形態では、チェックによって所定の数以上の割り当てられた時間が平均速度の計算に用いられることを確実にする。このような条件に合わない平均速度は、更なる処理のために排除され、その区域のひとつ以上の時間においてギャップが生じるようになる。ある実施形態では、５つ以下の値が平均速度の計算に使われた場合、その平均速度は排除される。他の実施形態は、異なる数を用い得、例えば２，３，４，６，７，８，１０，２０個の値、又はこれらの間の任意の値をも用い得る。
【０１１１】
又、平均値の品質に関する更なるチェックが行われ、ここでは平均値ごとの標準偏差を、その区域のその時間の平均値を計算するために用いられたデータサンプルの数の平方根 で割る。この計算の結果が所定の限度を超える場合は、その平均値は排除され、その区域のその時間にはギャップが生じるようになる。
【０１１２】
更なる品質チェックを行い、下記のような平均値を排除することも可能である：データの偏差が所定の限度を超えているか、所定の限度を超える外れ値が所定の数以上あるか。当業者には、そのような統計的技術を用いてデータの品質を確実にすることは明らかであろう。
【０１１３】
ある道路区域の平均値のセットは、その道路区域の観測された速度プロファイル と考えられ得る。
【０１１４】
ある道路区域の測定された速度プロファイルに少数の速度値が欠けている場合（即ち、全て又は少なくとも大勢の所定期間は値を持っている）、その区域は処理され得、欠けている値は隠され得る。欠けた区域 の数が増えると、結果として生じるクラスタ分析の品質は低下する。したがって、幾つの期間が欠けても許可できるかは、品質に関する選択であり、ケースによって検討する必要がある。高品質の完全なデータだけを用いることは、高速道路のような交通量の多い道に過剰な重みを付けることを意味し得る。必要条件が低すぎると（即ち、多くの期間が欠けている道路区域をクラスタ化すること）は、現実的でないクラスタ及び不正確な分析をもたらす。
【０１１５】
これらの品質チェックを通った平均値は信頼性があるとみなされ、更なる処理に用いられることが許可される。 ステップ７０８では１つの道路区域当たりの平均速度のカバレージに関する分析が行われる。 信頼性のある平均値のカバレージが十分に高い場合は、マップデータは更なる処理を受ける。しかし、カバレージが所定の限度以下であればマップは排除される。許可可能なマップは、図８を参照して説明されているように、クラスタ形成のために通される。
【０１１６】
そのようなクラスタ形成は、毎週繰り返される、日などの期間についての標準的な速度プロファイルを自動的又は半自動的に抽出することを目的とする。後で述べるように、類似する分類の道路はその速度プロファイルも類似しているのであれば、大幅なデータの圧縮が達成できる。例えば、日曜日の午前１０時の、道路の第１区域における速度は、同じ道路の第２区域における同期間の速度と類似し得る。これらの道路区域における類似性が他の時間帯においても繰り返されている場合は、第１の区域と第２の区域は、同じ速度プロファイルで表わされていると考え得る。したがって、これから定義するクラスタ化はそのような類似性を見つけることを目的とするものである。速度プロファイルの正規化も、下記のように、速度プロファイルを異なる分類の道路に用いることを可能とし得る 。
【０１１７】
クラスタ化を行う前に、測定された速度プロファイルは夜間の期間を合併させるためにさらに処理される。この実施形態では、９ＰＭから５ＡＭ（即ち、８個の期間）までの平均速度が平均化され、この夜間平均がこれらの８個の期間のそれぞれとして用いられる。したがって、各速度プロファイルは９ＰＭから８ＡＭ の間には平らなプロファイルを持っており、その道路区域の交通の自由流れ速度であると言える。自由流れ速度は、通常車のような乗り物がその道路において移動する際の速度として考えることができ、自由流れ速度はその道路区域の制限速度とは異なり得る。また、自由流れ速度はその道路区域の制限速度とほぼ同じであり得る。
【０１１８】
第１のステップ８００では、クラスタの数を制限するために、測定された速度プロファイルを正規化させる。そのような正規化はいくつかの基準に従って行い得る。説明されている実施形態では、正規化は、ある平均速度と関連付けられた道路区域について計算された自由流れ速度に従って実行される。したがって、クラスタ化アルゴリズムに通される、道路区域ごとの平均速度は、０と１の間の値を持っている。そのような方法は、クラスタ化によって生成される速度プロファイルを、道路の種類から独立させることができ、同じ速度プロファイルのセットを、任意の種類の道路の区域にも用いることができるため、更なるデータ圧縮を可能にする。
【０１１９】
夜間の自由流れ速度を用いることは、夜間の速度値を考慮しないことを可能とするため、クラスタ形成の次元を減らせ得る。
更なる実施形態では、ある道路区域の平均速度又は制限速度を、正規化の更なる基準として用い得る。
【０１２０】
したがって、クラスタ化アルゴリズムを用いて類似した交通の振る舞いを見せる日を一緒にグループ化することができる。期待される交通の振る舞いが異なる場合は、クラスタ形成は独立的に実行されるべきである。クラスタ化アルゴリズムに入力されるパラメータは、希望されるクラスタの数であり、典型的な範囲は曜日ごとに１０〜７０個である。最適のクラスタにたどり着くための周知の方法がいくつかあり（例えば、何らかの品質指標を与えることや、トレンドによって数を増加／減少させることなど）、これらを用いてクラスタ化のアウトプットが容認できるかを決定し得る。
【０１２１】
ある実施形態では、クラスタ化アルゴリズムは約６０クラスタを生成するように構成されている。他の実施形態では、アルゴリズムは最初はより多い又はより少ないクラスタを生成するように構成される。結果として生じるクラスタは、満足できるものであるか（例えば、実質的に同じクラスタはないか？不連続的なクラスタはないか？）を調べるために処理される。問題のあるクラスタがあれば、アルゴリズムを再実行させ、１回目より少ない数のクラスタを生成することを目標とする。この反復工程は、満足できるクラスタのセットが決定されるまで繰り返される。
【０１２２】
ある実施形態では、クラスタが満足できるものか は、クラスタによって生成されるプロファイルが所定の限度以上の周波数を含む かを調べるステップを含む。そのような周波数は、クラスタによって生成されたプロファイルの中に高すぎる変化率を持つ（即ち、不連続性があり得る）ことを示し、もしそのようなデータを使用すると、ナビゲーション装置２００が不安定になるなどの問題が起こり得る。また、クラスタが満足できるものであるか否かは 、クラスタによって生成された速度プロファイルの各々をお互いに、又は少なくともいくつかをお互いに、比較する工程を含む。ある１つの実施形態では、これは最小二乗比較によって行われ得る。
【０１２３】
ある実施形態では、クラスタ 化はクラスタ分析によって行われ得るが、他のクラス構築方法を用いても良い。単純で効率的な方法としては、いわゆるＫ平均法がある。この非階層クラスタ分析方法は通常ｋランダム・シードから始まり、選択された測定基準に基づく最小エラー基準に従ってクラスのメンバの再分布を行う。このアルゴリズムは極小値にしか至らないため、最適な解決のためには複数回繰り返す必要がある。最終的なクラスタの重心は所定のクラスタを形成する。異なる実施形態では、異なるクラスタ化方法を用いられ、これらは階層的クラスタ分析及びファジークラスタリング法を含み得る。
【０１２４】
ある実施形態では、更なるクラスタを加え得る（８０４）。例えば、ある実施形態は、信頼できるパターンがない道路区域（例えば、データのカバレージが小さいため、又は交通に関連する問題などのため）に関しては、平らな線を速度プロファイルとして加え得る。
【０１２５】
クラスタによって生成された速度プロファイルを作成する最終的なステップ（８０６）として、クラスタは様々な時間分解能へと補間される。ある実施形態では、これは三次元スプラインを用いて行われるが、指数フィッティングなどの異なる方法も可能である。当業者にはそのような類似する方法が用いられ得ることが明らかである。
【０１２６】
クラスタ分析工程に用いられた時間分解能が、最終的に望まれるものより粗い場合（所定の時間において信頼性のある平均速度を確保するために、このようなことが起こり得る）においても、時間分解能を調整することがこの時点で可能となる。例えば、意図する使用の要件を満たすために、より細かい分解能に調整され得る。例えば、粗い時間分解能では時間的境界において大きな差が生じる個所では、より細かい時間分解能で継続的なプロファイルを用いることが有利であり得、より滑らかな経路を提供できる。説明される実施形態では、クラスタによって生成されるプロファイルは約５分の間隔の分解能を与えるために補間される。しかし他の間隔を用いても良い。そのような間隔は、クラスタによって生成された速度プロファイルを用いて処理するときに便利であり得る。
【０１２７】
図９は、クラスタ化アルゴリズムから得られる、マップに関する通常の結果を示しており、入力された平均速度値は、クラスタ化によって生成された独立した１６個の速度プロファイルにクラスタ化されている。他の実施形態において、クラスタの数が変更されると、１つの道路区域において可能な速度プロファイルの数も変更される。
【０１２８】
クラスタ化によって生成された速度プロファイルの適切なセットが決定されると（この実施形態では１６個が生成されている）、これらは１つ以上のマップに関連付けられる。一般的に、ある速度プロファイルのセットは、そのプロファイルの源となったマップに関してより正確であり得、これはそのマップに載っていない道路における交通現象が異なり得るからである。例えば、あるマップが１つの国を含んでいるとすると、異なる国における交通は少し違うパターンで動く可能性がある。
【０１２９】
しかし、異なる実施形態では、速度プロファイルは複数のマップと関連付けられ得る。このようなことは、例えばマップが国の一部を含む場合において適切であり、及び ／又はマップを複数の国に用いることが適切であり得る。
処理中のマップに存在する各道路区域は分析され、その区域に対する１週間分の予想移動速度を決定するために、クラスタ化によって生成された１つ以上の速度プロファイルを持ち得る（図９参照）。これらの速度プロファイルは、ルートを決定するためにナビゲーション装置によって使用される、既定速度プロファイル又は通常の速度プロファイルである。この工程は図１２を参照して説明される。ｎ＝１から始まり、ｎ番目の道路区域が処理される（１２００）。
【０１３０】
ＰＮＤが処理されたマップを用いることで正確な経路を生成できるようにするためには、各道路区域が夫々高い信頼性の速度プロファイルを持つことが望ましい（第１のステップとして、測定された速度プロファイルが適切であるか評価する）。したがって、前に行った品質評価によって、測定された速度プロファイルが品質の要件を満たさないと判断された場合は、代替作戦（Ｆａｌｌｂａｃｋ Ｓｔｒａｔｅｇｙ）を用いて、測定された速度プロファイルを、ＰＮＤ又は他の装置によって経路指定のために処理した際によりいい結果を出し得る速度データで置き換える。
【０１３１】
測定された速度プロファイルが実際に不適切であると判断された場合、測定された速度プロファイルの代わりに、その道路区域において収集された全ての速度データの平均値を含む処理された道路区域についての平均速度１０００を代替状態として用いる。即ち、各日の各期間において収集されたデータの平均値を求め、１つの速度を生成する。この１つの速度はやがて、フラット・クラスタ化によって生成された速度プロファイル（図９の１５番） に割り当てられ得る 。
【０１３２】
次に、ある区域に対して収集されたデータから得られた平均速度を受け入れられるかを決定する。平均値がこれらのチェックを通ると、その平均値はその道路区域に使用される。
【０１３３】
統計学の当業者には、平均値の品質を測るための方法が明らかであろう。例えば、ある実施形態では平均値は所定の数以上の速度から生成されなければならないという条件があり得、その数は例えば１０個の速度であり得る。平均値が最低値（例えば、２ｋｍ／ｈ）以上、及び／又は最高値（例えば、１５０ｋｍ／ｈ）以下のものであることを確実にするため、平均値に限度を適用し得る。また、平均値の品質が十分であるかを決定するために標準偏差を用い得る。
【０１３４】
道路区域は、マップデータ内において分類体系によって分類され得ることが知られており、それによって類似する特徴を持つ道路区域は同じ分類に分かれる。例えば、１つの関係者によって生成されたあるマップには、道路区域が分類される８個の分類がある。ある実施形態では、所定の道路区域についての分類に含まれる道路の所定の割合以上が、平均値の生成に使われる速度を提供することを保証するために、所定の道路区域の平均値が分析される。このテストが成功しないと、平均値が拒絶されることだけでなく、次に説明される、ギャップを埋める工程も省略され得る。
【０１３５】
道路区域における交通の流れが２つの方向に可能である場合、夫々の方向に対する平均速度が存在する。
【０１３６】
測定された速度プロファイルが代替作戦において置き換えられた場合、図９のクラスタ速度プロファイル１５番のような平らな線を含む速度プロファイルが事実上存在することが明らかであろう。また、速度プロファイル情報は正規化されているため、速度プロファイル１５番は、１つの平均速度が関連付けられたどんな道路区域を表すためにも用いられ得る。
【０１３７】
ある区域において収集されたデータから得られた平均速度がいまだに品質チェックを通らない場合は、代替作戦のつぎのステップ（１００２）が用いられ、図１１を用いて次に説明する、いわゆるギャップ埋め工程が使用される。第１ステップとして、処理されるマップに存在する各道路区域は、所定数の分類のうちの１つの分類として分類される（１１００）。当業者には、この分類が１回のみ行われればいいことが明らかであり、結果として生じる分類は、ギャップ埋め工程が行われるさらなる道路区域のために保たれる。もちろん、他の実施形態では、ギャップ埋め工程が行われるたびに計算しなおしてもよく、又は分類を即座に計算しても良い。
【０１３８】
説明される実施形態では、次の表１に示されているような４０の分類が存在する。これらの分類は、処理されるマップデータ、マップに含まれる領域、又は他の関連するいかなる要因によっても異なり得る。
【表１】
【０１３９】
各道路区域が分類されると、分類ごとの平均速度が計算され（１１０２）、この場合は４０の部類の平均速度が計算される。生成された分類ごとの平均は、分類ごとに１つの数字であり、このような平均を得るためには、各所定の時間ごとの速度を、本明細書に記載された任意の適切な平均値計算方法を用いて求める。当業者には、このステップが１回のみ行われればいいことが明らかであり、結果として生じる分類ごとの平均速度は、後に行われるギャップ埋め工程のために保たれる。
【０１４０】
しかし、この実施形態では、各分類の平均速度は、分類に含まれる全ての要素の、長さによって重み付けされた調和平均として計算されており、次のような計算式を用いる：
Ｖｍｅａｎ＝Ｌ／Σｌｉ／Ｖｉ
ここで
Ｖｍｅａｎは、分類ｊの平均速度、
ｌｉは、線ｉの長さ、
Ｌは、分類ｊに含まれる全ての線の長さ合計、
Ｖｉは、線ｉの平均速度である。
【０１４１】
これらの平均速度が更に使われる前に、十分な品質のものであり、その分類の道路の平均速度を正確に表しているかをチェックする。道路の分類の所定の時間に含まれるサンプルが少な過ぎたり、又は平均の計算に用いられるサンプルのばらつきが激しい場合、品質は不十分であり得る。したがって、各平均値の品質に関するチェックが下記のように行われる（１１０４）。
【０１４２】
４０の分類中のある１つの分類からの平均速度が、ｈｉｔ＿ｎｕｍｂｅｒ＿ｍｉｎ（本実施形態については、これは表２に示されている）より少ない数の区域に基づいている場合は、表３に示されているように、この平均値は異なる分類からの値で置き換えられる。説明される実施形態では、ヒット（ｈｉｔ）の最低限の数は１０であるが、他の実施形態では異なる数を用い得る。
【０１４３】
所定の分類のｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ａｂｓ及びｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ｒｅｌのいずれも図２に示された値以下でなければ、速度分類の平均値は図２に示されているように、割り当てられた置き換え分類の平均値によって置き換えられる。ｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ｒｅｌ＿ｍｉｎは、平均速度をヒットの数の平方根で除したものに対する％として表される、分類の相対的な標準偏差として与えられ、すなわちｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ａｂｓ＊１００／ｍｅａｎ＿ｓｐｅｅｄである。
【０１４４】
したがって、任意の分類の平均速度が使えるようになるまでパスしなければいけない３つの品質要素（Ｑｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ａｂｓ＿ｍｉｎ， ｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ｒｅｌ＿ｍｉｎ， ｈｉｔ＿ｎｕｍｂｅｒ＿ｍｉｎ）がある。品質要素をパスできない場合は、その平均速度は表３に従って置き換えられる。
【表２】
【表３】
【０１４５】
表２に示された値は例として示されており、他の実施形態では異なり得る。同様に、表３で用いられた置き換え値も、マップに含まれる領域、マップデータを生成した者などによって異なり得る。
【０１４６】
ある分類に含まれる任意の平均値が使えるようになる前に、品質チェックが行われる。これらのチェックをパスできない場合は、ギャップ埋め工程はその分類において失敗することとなる。これらの品質チェックは次のようなものである。
【０１４７】
分類の平均値は、次のように計算される最低限度のより高く、そして最高限度より低い値であり、ｍｉｎ及びｍａｘは最低関数及び最高関数の擬似的なコードである。
Ｍｉｎ＿ｓｐｅｅｄ＿ｔｈｒｅｓｈｏｌｄ＝ｍａｘ［ｍａｘ（ｍｉｎ−ｌｏｗｅｒ＿ｒｅｌａｔｉｖｅ＿ｄｅｖｉｓｉｏｎ＊ｍｉｎ／１００、ｍｉｎ−ｌｏｗｅｒ＿ａｂｓｏｌｕｔｅ＿ｄｅｖｉｓｉｏｎ），ｌｏｗｅｒ＿ｌｉｍｉｔ］
Ｍａｘ＿ｓｐｅｅｄ＿ｔｈｒｅｓｈｏｌｄ＝ｍｉｎ［ｍｉｎ（ｍｅａｎ＋ｕｐｐｅｒ＿ｒｅｌａｔｉｖｅ＿ｄｅｖｉｓｉｏｎ＊ｍｅａｎ／１００，ｍｅａｎ＋ｕｐｐｅｒ＿ａｂｓｏｌｕｔｅ＿ｄｅｖｉｓｉｏｎ），ｕｐｐｅｒ＿ｌｉｍｉｔ］
ここでｍｅａｎは、区域の適切な速度分類の平均速度である。他の値は表４に定義されている。
【０１４８】
ある区域に関連する速度がこれらの基準に合わない場合は、区域に関する速度が絶対的な速度制限に背かない限りその速度は平均速度に基づいてその閾値によって置き換えられ、そのような場合にはこの絶対的な速度制限をその区域の速度として用いる。
【表４】
当業者には、ここにおける計算は速度に関して行われており、時間に関して行われていないことが明らかであろう。
【０１４９】
したがって、ギャップ埋め工程が終わると、所定の４０の分類中の１つの分類内の道路区域に基づいた平均速度が生成され得る。しかし、それでもギャップ埋め工程が失敗することもある（即ち、品質チェックをパスする平均値が生成されていない）。
【０１５０】
したがって、関連する速度データを持たない道路区域は、ギャップ埋め工程によって生成された平均速度データ（ただし、この平均値が品質チェックにパスすれば）が割り当てられる（１１０８）。
【０１５１】
ギャップ埋めが失敗すると、ステップ１００４において、その道路区域に関連する速度は、Ｆｕｎｃｔｉｏｎａｌ Ｒｏａｄ Ｃｌａｓｓ（ＦＲＣ）に従ってマップデータ供給者から供給される速度に指定される。ＦＲＣは例えば大まかに８つの分類を含み得る（この数はマップデータ供給者によって異なり得る）。即ち、自由流れ速度はＦＲＣによる値に設定され、クラスタによって生成される速度プロファイルは、この実施形態では、プロファイル１５番である。
【０１５２】
次に、ある道路区域に関連する速度プロファイル（測定された速度プロファイル又はギャップ埋めによって挿入された平均値）は、ＰＮＤのようなナビゲーション装置で使用できるようなマップデータを生成するために、クラスタ化によって生成された１つの速度プロファイルに割り当てられる 。これは、速度プロファイルが測定された速度プロファイルであっても、クラスタ化によって生成された平らな速度プロファイル１５番を考慮した平均であっても、行い得る。
【０１５３】
ステップ１２１０では、最小二乗分析を用いて、クラスタ化によって生成された速度プロファイルのセット内のそれぞれ速度プロファイルに対して、得られた速度プロファイルが比較される。これらの１６の比較が行われた後、１６個のセットのうちのどの速度プロファイルが、該道路区域に関連する速度プロファイルに最も近いのかを判断できるようになり、ステップ１２２０では最も近いと判断された、クラスタ化によって生成された速度プロファイルへの参照が、その道路区域ついてのマップデータに保存される。該道路区域に関連して保存されるマップデータは、その道路区域の自由流れ速度であり、以前に計算されたものである。
【０１５４】
したがって、上記の参照及び自由流れ速度を用いて、各道路区域の平均速度に関する情報をマップデータ内に保存できる。交通量が多い区域は、平均速度情報は９ＡＭから５ＰＭまでの１時間ごとの平均に関する近似値を含むと考えることができる。交通量が少ない区域は、平均速度情報は全ての時間にわたって平均された平均速度と考えることができる。
【０１５５】
この工程は、マップ上の各道路速度に、クラスタ化によって生成された１６の速度プロファイルのうちの１つが関連付けられるまで繰り返される（１２３０）。
【０１５６】
マップデータが公開される前に、（測定値の代わりに挿入された平均値ではなく、）測定された速度プロファイルが関連付けられた道路区域の数が十分であるか最終チェックを行う。
【０１５７】
この最終チェックでは、各機能的道路分類（ファンクショナル・ロード・クラス：ＦＲＣ）についての道路区域の全長が計算される。下記の表５に示されているように、ＦＲＣは表２に示された４０の分類に関連している。各ＦＲＣ内において平均速度データを持つ道路区域の長さは、図５に示されているように、ＦＲＣ内の道路全長の所定の割合（限度）以上でなければならない。
【表５】
【０１５８】
ルーティング動作に一般的により大きい影響を及ぼす道路分類は、より高い割合の最低カバレージが必要となることがわかるようになるだろう。例えば、ＦＲＣ０（高速道路）は経路計画に大きい影響を及ぼすため６０％を有することが必要になるが、例えば二次道路は３０％の包含率が必要となっている。
【０１５９】
他の実施形態では、更なる代替作戦が提供され得る。そのような実施形態においては、第１の代替作戦が（測定された速度プロファイルが受け入れられないと判断された場合）、測定された速度プロファイルを夫々の日に用いることの代わりに、各日の所定の時間に関する速度プロファイルを合計し、結果として生じる合計速度プロファイルを各日に用いるものであり得る。したがって、そのような実施形態では、月曜日から金曜日までの同じ時間帯の期間を合計して週ごとの速度プロファイルが生成され、週末の速度プロファイルは土曜日及び日曜日の同じ時間帯の期間を合計することで生成される。週末の交通の流れは平日の交通の流れと異なり得ることが明らかであろう。
【０１６０】
そのように合計された速度プロファイルは、他の代替作戦を用いる前に、品質の要件を満たしているかがチェックされる。これらのチェックは、測定された速度プロファイルを評価するために用いられる要件と同じもの、又は少なくとも似たもので行われ得る。データの合計を行うことによってデータの品質が改善され、平日及び週末の両方が品質チェックをパスした場合、その速度プロファイルはその道路区域に用いられる。
【０１６１】
上記方法によって計算された速度プロファイルは、正常な週に道路区域を通る予想速度を定義しており、ナビゲーション経路を決定する際に用いる既定速度プロファイルである。したがって、これらの速度プロファイルは“正常”速度プロファイルと名付けられ、後で明らかになるように、毎週繰り返される複数の期間から合計された速度データを処理することによって決定されている。
【０１６２】
しかし、交通の振舞いは、通常の週には発生しないイベント（例えば、祝日、祭り、異常気象、交通事故など）が発生すると、正常速度プロファイルとは大幅に異なり得る。そのようなイベントによる異常な交通の振舞いの配慮するため、プロセッサ１５４はこれらのイベントが発生するものと特定された時間に用いる異常速度プロファイルを生成するために速度データを処理するように構成されている。
【０１６３】
これに関しては、図１３を参照しながら説明する。ステップ１３００では、プロセッサ２０２は、異常な交通の振舞いが発生した又は発生すると予想された過去の時刻を同定する。これはプロセッサ１５４によって、メモリ１５６に保存されたイベントカレンダ（不図示）において、交通の振舞いに影響を与えた可能性がある異常なイベントをサーチすることで行われ得る。
【０１６４】
異常な交通の振舞いが発生した又は発生すると予想された時刻が同定されると、プロセッサ１５４はステップ１３０１において区域に割り当てられる１つ以上の異常速度プロファイルを決定する。
【０１６５】
異常速度プロファイルは、異なる時間について用いられる正常速度プロファイルのうち１つを使うためのポインタであり得る。例えば、所定の時間はイギリスの銀行休業日のような祝日であり得、そのような場合の異常速度プロファイルは、日曜日の正常速度プロファイルを使うためのポインタであってもよく、（日曜日でない）祝日にも日曜日の正常速度プロファイルが用われるべきであることを特定する。
【０１６６】
プロセッサ１５４は、異常な交通の振舞いと同定され、共通する特質（例えば、祝日である、または激しい気象条件の時刻又は日である）を持つ全ての時間の速度データを抽出し、これらの速度データを合計し、図７〜１２を用いて説明した方法でこれらの速度データから異常速度プロファイルを生成してもよい。結果として、異常な交通の振舞い（祝日、異常気象など）の際における特別な一連の速度プロファイルが出来上がる。
【０１６７】
プロセッサ１５４は、既に計算された正常速度プロファイルを拡大又は縮小させて異常速度プロファイルを生成し得る（ほとんどの場合は縮小が行われる）。
【０１６８】
プロセッサ１５４はステップ１３０２で、マップデータの１つ以上の区域に各異常速度プロファイルを割り当て、どのような条件において異常速度プロファイルが使われるべきかを識別する識別子を割り当てる。これは、未来のイベントに関してはイベントカレンダから決定し得、又は過去に異常な交通の振舞いが発生した際に存在したと同定された条件のような異常な交通の振る舞いが起きる時の特定の条件を特定することにより決定し得る。
【０１６９】
作成されたマップデータはサーバ１５０によってナビゲーション装置２００に送信され、マップデータに含まれる領域における経路を決定するために使用される。
【０１７０】
図１４を参照すると、Ｉ／Ｏ装置２２２を介して経路決定の要求を受信すると、ナビゲーション装置２００のプロセッサ２０２は経路上でのに移動中の時刻における状況を同定する（１４００）。例えば、ナビゲーション装置２００は、メモリ２１４又はカードポート２２８のメモリカードに保存された、未来のイベントに関するイベントカレンダを含み、同じくメモリに保存される天気及び交通に関するリアルタイムのアップデートを受信する。経路決定の要求を受信すると、プロセッサ２０２はイベントカレンダ及び保存されたリアルタイムアップデートをサーチし、移動中の時刻の状況が、正常速度プロファイルではなく異常速度プロファイルを使う場合を示す、地図中の識別子の特定の状況に一致するかを決定する。一致する場合は、プロセッサ２０２は異常速度プロファイルを用いて経路を決定する。一致しない場合は、プロセッサ２０２は正常速度プロファイルを用いて経路を決定する。
【０１７１】
ある実施形態では、リアルタイムのアップデートは、交通事故又は異常気象が発生している／発生すると見込まれる場所を含み得る。経路決定の要求を受信すると、プロセッサ２０２は境界ボックス／影響される領域のアプローチを用いて、どの区域に正常速度プロファイルを用いてどの区域に異常速度プロファイルを用いるべきかを決定する。プロセッサ２０２は所定距離内（例えば５０又は１００ｋｍ）に事故や他のイベントなどが発生した区域を同定し、これらの区域には異常速度プロファイルを用い、これら（又は任意の影響を受ける領域）以外の区域には正常速度プロファイルを用いる。このようにすると、ナビゲーション装置は全体的でなく局部的な影響を与えるイベントに注意を払うことができる。
【０１７２】
異なる実施形態では、ナビゲーション装置２００のプロセッサ２０２は、移動時に特定の状況が同定されると、その時刻におけるその区域の正常速度プロファイルではなく、異なる正常速度プロファイルをその区域の移動速度として用い得る。このようにすることで、異常速度プロフィァイールをマップデータに含むことが必要ではなくなる。そのような機能は、特定の状況が祝日である場合適切であり得る。この状況が満たされると、プロセッサ２０２は祝日である曜日の速度プロファイルを用いるのではなく、土曜日又は日曜日の速度プロファイルを用いる。このような状況の１例は、イギリスの銀行休業日（通常月曜日になる）であり、そのような場合、プロセッサ２０２は（イギリスにおける経路を決定する場合）、月曜日の正常速度プロファイルの代わりに、日曜日の正常速度プロファイルを用いて経路を決定し得る。
【０１７３】
当業者には、ここに説明される方法を実行するために提供される装置はハードウェア、ソフトウェア、ファームウェア又はこれらの２つ以上の組み合わせであり得ることが明らかであろう。
【０１７４】
当業者には、図１を用いて説明されたようにＧＰＳから得られる位置データを参照するためにＧＰＳデータという用語を用いているが、他の位置データもここに説明された方法に似たような方法で処理できることが明らかであろう。したがって、ＧＰＳデータという用語は「位置データ」で置き換えが可能であり得る。そのような位置情報は、例えば移動電話の作動、料金所で受信したデータ、道路に埋め込まれた誘導ループシステムから得られるデータ、乗り物のナンバープレート認識システムから得られるデータ、又は他の適切なデータから抽出することができる。
【技術分野】
【０００１】
本発明は、マップ（地図）データ（特にナビゲーション装置に用いられるマップデータ）を生成する方法及び装置、並びにマップデータを用いて経路を決定する方法及び装置に関するものである。本発明は、携帯ナビゲーション装置において特に応用される。
【背景技術】
【０００２】
トムトムインタナショナルＢＶのＧＯ（登録商標）のようなＧＰＳ技術に基づく電子ナビゲーション装置のためのマップデータは、テレアトラスＮＶ（Ｔｅｌe Ａｔｌａｓ ＮＶ）のような専門的なマップ販売社から来ている。このような装置は携帯ナビゲーション装置（Ｐｏｒｔａｂｌｅ Ｎａｖｉｇａｔｉｏｎ Ｄｅｖｉｃｅ，ＰＮＤ）とも呼ばれている。マップデータは経路案内のアルゴリズムによって使用されるように特別にデザインされており、一般的にＧＰＳシステムからの位置データを使用する。例えば、道路は線、即ちベクトル（例：道路の始点、終点、及び方向。道路の全長は、夫々始点／終点方向のパラメータで独特に定められた、数百の区域で構成される）で表現することができる。したがって、マップはそのような複数の道路ベクトル、夫々のベクトルに関連付けられたデータ（制限速度、移動方向など）、関心のある場所 （Ｐｏｉｎｔ ｏｆ Ｉｎｔｅｒｅｓｔ， ＰＯＩ）、道路名、並びに公園の境界、川の境界など、全てベクトルで定義された地理的特徴のセットである。マップに含まれる全ての内容（例：道路ベクトル、ＰＯＩなど）は、ＧＰＳの座標系と一致または関連する座標系を用いて定義されており、ＧＰＳで決定された装置の位置を、マップに表示される道路に正しく位置付けることを可能にし、目的地までの最適な経路を計画することを可能にする。
【０００３】
テレアトラスはこのマップデータベースを作る作業を、イギリスのオーディナンス・サーベイなどの様々な情報源から得られる基本道路情報から始める。また、データの更新及び確認のための、多数の車両と他のマップ及び航空写真を調べる職員を持っている。このデータはテレアトラスのマップデータベースの中核 となる。このマップデータベースは地理的に関連付けられたデータを用いて継続的に改善されている。そして、データベースはその内容が確認され、トムトムのようなデバイス製造会社に年に４回公開される。
【０００４】
夫々の道路区域は、速度に関するパラメータが関連付けられており、該速度に関するパラメータは、その区域においてどのような速度で移動できるかに関する目安を表し、例えばテレアトラスのようなマップデータを生成したものの平均速度である。速度パラメータは、マップ処理を行うＰＮＤの経路計画アルゴリズムによって利用される。したがって、このような経路計画の精度は速度パラメータの精度に依存する。例えば、現在の装置の位置から目的地まで最も速い経路をＰＮＤに生成させるという選択肢を、ユーザはよくＰＮＤ上に提示される。速度パラメータが正確でなければ、ＰＮＤによって計算された経路は最も速い経路でなくなり得る。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
道路区域の速度プロファイルは交通の密度などのパラメータによって影響されやすいため、そのような速度プロファイルにおけるばらつきは、２つの地点の間に存在する最も速い経路は継続的に同じ経路ではないことを意味する。道路区域の速度パラメータにおける誤りは、不正確な到着予定時刻（Ｅｓｔｉｍａｔｅｄ Ｔｉｍｅ ｏｆ Ａｒｒｉｖａｌ， ＥＴＡ）及び最も速くはない経路の 選択につながり得る。
【０００６】
テレアトラスは、ＧＰＳデータがＰＮＤからアップロードされ、マップデータの区域の速度パラメータを与えるために使われるシステムを開発しており、一日中のあるいくつかの時刻 における、道路区域の実際の速度を示す速度パラメータを提供することを目的としている。
【課題を解決するための手段】
【０００７】
本発明の第１の実施形態によると、マップに含まれる領域内のナビゲーションできる経路の区域を表すナビゲーションできる複数の区域を含むマップデータを生成するために速度データを処理する方法であり、ある区域を異なる時刻の期間中に通る際に測定された移動速度を含む、少なくとも１つの区域に関する速度データを取得する工程と、各区域の前記速度データから、前記区域を通る際の平均移動速度を含む、毎週繰り返される期間の少なくとも１つの正常速度プロファイルに関するデータを生成する工程と、少なくとも１つの毎週繰り返されない特定の期間に対して、前記特定の期間中に前記区域を通る際の予想移動速度を含む異常速度プロファイルを、１つ以上の前記区域データの各々に対して少なくとも１つ生成する工程と、前記領域を渡る行路を決定するための経路計画アルゴリズムにおいてナビゲーション装置によって使用されるために、前記マップデータの１つ以上の前記区域の各々に、対応する前記正常速度プロファイル及び前記異常速度プロファイルを割り当てる工程と、を含むことを特徴とする方法が提供される。
【０００８】
そのような方法は、マップデータに含まれる領域内のナビゲーションできる各区域に、夫々関連付けられた異常速度プロファイルを持つことを確実にし、これらの異常速度プロファイルを用いることによって、正常速度プロファイルを用いた場合より、ナビゲーション装置が特定の時間における正確な交通の流れが得られる。例えば、特定の時間はクリスマスのような祝日、全国的なスポーツイベント又は国家的お祝い／喪のような国家的行事、及び／又は豪雨、豪雪、霧、猛暑などの交通に影響を及ぼし得る異常気象であり得る。そのような、ある道路区域の特定の時間における速度の改善された予想は、マップデータによって示される領域を渡る移動を決定する経路アルゴリズムの精度を上げられ得る。
【０００９】
「毎週繰り返される期間」という用語は、例えば月曜日、火曜日、水曜日、木曜日、金曜日、土曜日、日曜日、平日、週末、及びこれらの一部である月曜日の朝、火曜日の午前８〜９時、火曜日から木曜日までのような、全ての週において発生しなくても高い頻度で繰り返される期間を意味する。この用語は、一年中の特定の時期（例えば、春、夏、秋、冬の週に繰り返される期間）において毎週繰り返される期間を含み得る。
【００１０】
該方法は、各区域に、経路の決定においてナビゲーション装置が前記異常速度プロファイルをいつ使用するべきかを識別する識別子を割り当てる工程を含み得る。該識別子は、１つ以上の特定の期間及び／又は１つ以上の特定の条件（例えば、気候）であり得る。
【００１１】
該方法は、異常な交通振舞いの期間を同定する工程と、１つ以上の前記同定された期間において前記区域を通る際に測定された移動速度を前記速度データから同定することによって前記１つ以上の異常速度プロファイルの各々を生成する工程と、前記同定された速度データから前記区域を通る際の平均移動速度を１つ以上決定する工程とを含み得る。例えば、同定された期間はイギリスの銀行休業日及び／又はクリスマスのような過去の祝日であり得、異常速度プロファイルの１つは過去の祝日において区域を通る際の平均速度であり得る。
【００１２】
代わりに、１つ以上の速度プロファイルの各々を生成する工程は、正常速度プロファイルの平均速度を増加又は減少させることによって決定された速度を含み得る。例えば、特定の期間は、雪や雨などの異常気象が発生した期間であり得、異常気象の際の異常速度プロファイルは、正常速度プロファイルの平均速度を所定の因数で縮小させることで生成され得る。ある実施形態では、異常速度プロファイルは拡大又は縮小の倍率であり得、割り当ての工程は各区域に正常速度プロファイル及び倍数を割り当てることを含み得る。そのような倍数用いることは、特定の期間中の複数の平均速度を含む速度プロファイルを新たに用意することより、必要なメモリの容量が少なくなり得るため、有利であり得る。
【００１３】
該方法は、正常速度の平均速度を基準とする所定の範囲内に含まれない、過去の測定された移動速度の期間を同定する工程と、これらの同定された期間を未来の期間に関連付ける工程とを含む。このように、特定の期間は自動的に同定され得る。
【００１４】
該方法は、特定の期間が、毎月又は毎年のように、毎週繰り返される周期とは異なる周期で発生するかを確認する工程を含み得る。これは、特定の日が将来いつ発生するかを自動的に決定できるようにするために必要になり得る。
【００１５】
特定の期間は、イベントデータベースにおいて捜査することで同定され得る。これらのイベントデータベースは、例えば気象観測所、イベント主催者などの外部情報源から得られ得る。
【００１６】
該方法は、全国的なスポーツイベント、祝祭、天気などの同定された期間に発生する既知のイベントと該同定された期間とを関連付ける工程と、イベントデータベースから類似するイベントが将来いつ発生するかを決定することでいつ異常速度プロファイルを用いるかを同定する工程とを含み得る。
【００１７】
ナビゲーションできる区域は一般的に道路の区域を表すが、乗り物や人などによってナビゲーションできる他の通路、チャンネルなどの区域も表し得る。例えば、道、川、運河、サイクリングロード、運河、鉄道線路などの区域であり得る。
【００１８】
該方法は、ＧＰＳデータを取得する第１ステップを含み得る。そのようなＧＰＳデータの取得は、少なくとも１つで一般的には複数のＰＮＤよりＧＰＳデータをアップロードすることで行われ得る。そのような方法では、ＰＮＤからアップロードされたＧＰＳデータは、該方法の工程において処理されるために保存され得る。
【００１９】
ＧＰＳデータは、１つ以上のナビゲーションできる区域に関連付けられた速度データを生成するために処理され得る。そのような方法は、ある区域における交通の流れの速度はその区域の制限速度であると見込まず、ナビゲーションできる区域において実際に測定された速度が速度データに反映されるため有利である。したがって、ＰＮＤ又はマップデータを用いる他の装置においてより正確な経路計画が可能になる。
【００２０】
速度データは複数のＰＮＤ又は他のナビゲーション装置から受信したデータから生成され得る。複数の装置に基づいてデータを生成することによって、ナビゲーションできる区域の実際の状況により近い速度データが得られることは当業者には明らかであろう。
【００２１】
ある実施形態では、処理は各ナビゲーションできる区域において測定された毎日の速度プロファイルを生成し得る（即ち、ある日の具体的な速度プロファイル；この場合は、ある曜日の具体的な正常速度プロファイル）。特定の日に関しては、処理はある特定の日において測定された異常平均速度を生成し得る（例えば、クリスマスのような毎週繰り返されないイベント）。期間の単位としては、１日が第１の期間として考えられる。
【００２２】
他の実施形態では、処理は他の期間を含む、測定された速度プロファイルを生成することを目的とし得る（即ち、第１の期間より長くあり得る第２の期間）。例えば、ある実施形態では、処理は平日に測定された速度プロファイル及び／又は週末に測定された速度プロファイルを生成することを目的とし得る。他の実施形態では、１つの測定された速度プロファイルを週全体のおいて用い得る。速度プロファイルの期間をより細かくすることで（例えば、１日）、実際の交通の流れに近い速度プロファイルが得られることは当業者には明らかであろう。しかし、期間を細かくすると、測定された速度プロファイルを生成するために必要なデータ量も増加することも明らかであろう。
【００２３】
マップデータは、正常速度プロファイルがナビゲーションできる区域に関連付けられた、第１マップに関するデータと、特定の期間に用いられる、異常速度プロファイルがナビゲーションできる区域に関連付けられた少なくとも１つの第２マップに関するデータと、を含み得る。該方法は、要求に応じて第１マップに関するデータをナビゲーション装置に送信する工程と、第２マップが適用される特定の時間に関するマップデータが要求されると、第２マップの１つに関するデータを送信する工程と、を含み得る。
【００２４】
このように、ナビゲーション装置及び／又はユーザは、いつ交通状況が毎週繰り返される正常交通状況とは異なるかを決定し得、交通状況をより正確に表すデータに基づいてナビゲーション装置の経路アルゴリズムが経路を決定することを確実にするように、第２マップにおけるなデータを要求する。マップデータがナビゲーション装置から中央サーバに送られる方法に比べてダウンロード数を減らすために、第２マップデータにおけるデータは好ましくは中央処理サーバから受信される。
【００２５】
追加的に又は代わりに、１つ以上の第２マップにおけるデータは、第２マップが適用できる特定の期間／日に自動的にナビゲーション装置に送信され得る。このようにすることで、ナビゲーション装置は交通状況をより正確に表すマップデータでアップデートされる。
【００２６】
該方法は、未来の特定の期間にデータを受信する工程と、未来の特定の期間についてのデータを受信すると、異常速度プロファイル又はその１つを特定の期間に関連付ける工程とを含む。修正されたマップデータは該所定の期間に、又はその前にナビゲーション装置に送信され得る。例えば、該特定の期間は、スポーツイベントのような全国的イベントが行われる期間であり得、第２マップのデータはそのような全国的イベント中にマップのナビゲーションできる区域で発生する異常平均速度を含み得る。このように、ナビゲーション装置はマップデータからいつ異常速度データを用いるかを決定することができる。
【００２７】
本発明の第２の実施形態によると、機械可読な命令を記録するデータ記憶媒体であって、命令が機械によって読み込まれると第１の実施形態の方法を機械に実行させることを特徴とする記憶媒体が提供される。
【００２８】
本発明の第３の実施形態によると、マップに含まれる領域内のナビゲーションできる経路の区域を表すナビゲーションできる複数の区域を含むマップデータを生成するために速度データを処理する機械であって、ある区域を異なる時刻の期間中に通る際に測定された移動速度を含む、少なくとも１つの区域に関する速度データを取得する工程と、各区域の速度データから、該区域を通る際の平均移動速度を含む、毎週繰り返される期間の少なくとも１つの正常速度プロファイルに関するデータを生成する工程と、少なくとも１つの毎週繰り返されない特定の期間に対して、該特定の期間中に該区域を通る際の予想移動速度を含む異常速度プロファイルに関するデータを、１つ以上の該区域データの各々に対して少なくとも１つ生成する工程と、該領域を渡る行路を決定するための経路計画アルゴリズムにおいてナビゲーション装置によって使用されるために、該マップデータの１つ以上の区域の各々に、対応する正常速度プロファイル及び異常速度プロファイルを割り当てる工程と、を実行させるように構成されたプロセッサを含むことを特徴とする、機械が提供される。
【００２９】
本発明の第４の実施形態によると、機械可読な命令を記録するデータ記憶媒体であって、命令が機械によって読み込まれると、該機会を第３の実施形態の機械として機能させることを特徴とする記憶媒体が提供される。
【００３０】
本発明の第５の実施形態によると、マップデータに含まれる領域内のナビゲーションできる経路の区域を表すナビゲーションできる複数の区域を含むマップデータが提供され、各ナビゲーションできる区域は関連付けられた速度データがあり、少なくとも１つのナビゲーションできる区域には１つの正常速度プロファイルと、１つ以上の異常速度プロファイルと、ナビゲーション装置がどのような場合に前記正常速度プロファイルではなく前記異常速度プロファイルを経路計画アルゴリズムに用いるべきかを識別する識別子と、が関連付けられている。
【００３１】
本発明の第６の実施形態によると、第５の実施形態のマップデータが記録された、機械可読なデータ記憶媒体が提供される。
【００３２】
本発明の第７の実施形態によると、マップデータを用いて、ある領域を渡る経路を計画する方法であって、前記マップデータは、前記マップデータに含まれる領域における、ナビゲーションできる経路の区域を表す複数のナビゲーションできる区域を含み、前記ナビゲーションできる区域の少なくとも１つは、毎週繰り返される期間における正常速度プロファイルが関連付けられており、前記正常速度プロファイルは前記毎週繰り返される期間に前記区域を通る際の予想移動速度と、前記区域を通る移動時間が前記予想移動時間と大きく異なる場合の特定された条件とを含み、前記方法は、ナビゲーションできる経路の決定の要求を受信する工程と、移動時に前記特定された条件が満たされているかを確認する工程と、前記条件が満たされている場合は１つ以上の他の速度プロファイルを用いて経路を決定し、前記条件が満たされていない場合は前記正常速度プロファイルの前記移動時に対応する前記毎週繰り返される期間の移動速度を用いて経路を決定する工程と、を含む方法が提供される。
【００３３】
このように、該方法は、移動時の通行状況に適切な速度プロファイルを用いる。例えば、特定の状況は特定の日、時間及び日、時間及び／又は日及び位置、交通状況、又は天候状況などであり得る。
【００３４】
他の速度プロファイルは、移動時刻に対応しない毎週繰り返される期間における外区域の正常速度プロファイルであり得る。例えば、特定の状況が移動時刻が祝日であることであれば、経路決定に用いられる該他の速度プロファイルは、平日のプロファイルではなく土曜日又は日曜日の正常速度プロファイルであり得る。
【００３５】
マップデータは、特定の状況の期間において区域を通る際の移動速度を含む異常速度プロファイルを含み得、他の速度プロファイルは異常速度プロファイルであり得る。注文品の速度プロファイルを用いると、異常交通振舞いの時の速度をより正確な予測につながり得る。
【００３６】
ある実施形態では、該方法は影響される領域及び、イベント、交通、又は天候状況などの特定された条件に関するデータを取得する工程と、該影響される領域内にある区域に対して少なくとも１つの異常速度プロファイルを用い、該影響される領域外にある区域に対しては少なくとも１つの正常速度プロファイルを用いる工程と、を含む方法である。このように、該方法はある区域を通る際にその区域だけに局部的に影響を及ぼすイベントを考慮して経路を決定できる。例えば、影響される領域は、豪雪又は豪雨が降る領域、又は交通事故によって影響される領域であり得る。
【００３７】
したがって、該方法は、イベント、交通、及び天候などの状況に関するデータを受信する工程を含み得る。
【００３８】
ある実施形態では、該方法は交通事故又は他のイベントの位置に関するデータを受信する工程と、交通事故又は他のイベントから所定の距離内（例えば、５０ｋｍ又は１００ｋｍ）の区域を同定することによって、影響される領域を決定する工程とを含み得る。
【００３９】
追加的に又は代わりに、該方法はカレンダを用いて特定の状況が満たされたかを決定する工程を含み得る。例えば、カレンダは、祝日や祝祭などの特定の状況がいつ発生するかを同定し得る。
【００４０】
移動時間は、経路決定の要求が受信された時刻から決定され得、又は、経路決定の要求に指定された時刻から決定され得る。
【００４１】
本発明の第８の実施形態によると、マップデータを用いて、ある領域を渡る経路を決定するナビゲーション装置であって、マップデータに含まれる領域における、ナビゲーションできる経路の区域を表す複数のナビゲーションできる区域を含むマップデータであって、該ナビゲーションできる区域の少なくとも１つは、毎週繰り返される期間における正常速度プロファイルが関連付けられており、該正常速度プロファイルは毎週繰り返される期間に該区域を通る際の予想移動速度と、該区域を通る移動時間が外予想移動時間と大きく異なる場合の特定された条件とを含む、該マップデータが保存されたメモリと、ナビゲーションできる経路の決定の要求を受信するための入力と、該条件が満たされている場合は１つ以上の他の速度プロファイルを用いて経路を決定し、該条件が満たされていない場合は該正常速度プロファイルの該移動時に対応する該毎週繰り返される期間の移動速度を用いて経路を決定するように構成された経路計算機と、を含むことを特徴とするナビゲーション装置、が提供される。
【００４２】
該ナビゲーション装置は、交通及び天候状況及びイベントなどの、移動時の現在の状況に関するデータを受信するための受信機を含み得る。
【００４３】
メモリは、祝日及び祝祭のような特定の状況がいつ発生するかを同定するカレンダを保存し得る。
【００４４】
本発明の第９の実施形態によると、機械可読な命令を記録するデータ記憶媒体であって、命令がナビゲーション装置のプロセッサによって読み込まれると、該装置を第１０の実施形態のに従って機能させることを特徴とする記憶媒体が提供される。
【００４５】
道路区域に関連付けられる速度データがここで引用される。各道路区域は、マップを提供するマップデータに含まれるデータによって表されることは、当業者には明らかであろう。ある実施形態では、そのような道路区域を表すデータは速度データへの参照を提供する識別子を含み得る。例えば、該参照は生成された速度プロファイルへの参照を提供し得る。この参照は、参照テーブルの形で提供され得る。
【００４６】
本発明の上記実施形態のいずれにおいても、機械可読な記憶媒体は下記の媒体のいずれかを含み得る：フロッピディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ／ＲＡＭ（−Ｒ／−ＲＷ及び＋Ｒ／＋ＲＷを含む）、ハードディスク、メモリ（ＵＳＢメモリキー、ＳＤカード、メモリスティック（登録商標）、コンパクトフラッシュ（登録商標）カード、又は同様のもの）、テープ、他の光磁気記憶媒体、送信された信号（インターネットのダウンロード、ＦＴＰトランスファなどを含む）、ワイヤ、又は他の適切な媒体。
【図面の簡単な説明】
【００４７】
【図１】ナビゲーション装置によって利用できるＧＰＳシステムの例を概略的に示す図である。
【図２】ナビゲーション装置とサーバとの間における通信のための通信システムの概略図である。
【図３】図２のナビゲーション装置または他の適切なナビゲーション装置の電子構成要素の概略図である。
【図４】ナビゲーション装置の取り付け及び／又はドッキングの配置を示す概略図である。
【図５】図３のナビゲーション装置に使われる構成スタックの概略図である。
【図６】A trace内のＧＰＳの定置とマップとを関連付ける実施形態を概説するフローチャートである。
【図７】平均値を求めるための実施形態を概説するフローチャートである。
【図８】平均値について クラスタ形成を実行するための実施形態を概説するフローチャートである。
【図９】クラスタによって生成され、クラスタリング・アルゴリズムの出力である速度プロファイルのセットの一例を示す図である。
【図１０】道路の区域に関連付けられた、測定された速度プロファイルの質を改善させるために用いられるfallback strategyを概説するフローチャートである。
【図１１】測定された速度プロファイルデータの質がどのように改善されたかを概説するフローチャートである。
【図１２】クラスタによって生成された速度プロファイルが、少なくとも１つのマップの道路区域とどのように関連付けられるかを概説するフローチャートである。
【図１３】典型的でない交通の振る舞いの際に、どのように異常な速度プロファイルが生成されるかを概説するフローチャートである。
【図１４】典型的でない交通振る舞いの際に、ナビゲーション装置がどのように動作し、異常な速度プロファイルを利用するかを概説するフローチャートである。
【発明を実施するための形態】
【００４８】
下記の説明全体を通して、類似の要素には同じ参照番号が使用される。
【００４９】
本発明の実施形態は、ＰＮＤに関連付けられた形で説明される。しかし、本発明はＰＮＤに限定されるものではなく、ルートプランニング 及びナビゲーション機能を提供するようにナビゲーションソフトウェアを携帯形式で実行するように構成された任意の制御演算装置に普遍的に適用できることは明らかである。したがって、本発明によるナビゲーション装置は任意の（限定されることなく）経路計画及びナビゲーション装置も含むべきであり、ＰＮＤ、自動車のような乗り物、又は経路計画及びナビゲーションソフトウェアを実行する携帯用ＰＣ，移動電話、又はパーソナル・デジタル・アシスタント（ＰＤＡ）などのような携帯コンピューティング資源など、任意の実施形態でもよい。
【００５０】
さらに、本発明の実施得形態は道路区域に関連付けて説明されている。しかし、本発明は道、川、運河、サイクリングロード、運河、鉄道線路などの区域のような、ナビゲーションの対象となり得る区域に適用できることは明らかである。これらの区域は、参照の簡略化のため道路区域として一般的に参照される。
【００５１】
ある地点からもう１つの地点までをナビゲートするためでなく、単純にある場所の視覚的情報がほしい場合などでも本発明が用いられることは下記の説明によって明らかになる。そのような場合は、ユーザによって選択された「目的地」は、対応する出発点ではなくてもよく、したがってそのような場合は「目的地」の位置または「目的地」の視覚的情報を参照することは、経路の生成や「目的地」への移動が必要であることを意味することではない。また、目的地が存在することは、対応する出発点の指定が必要であることを意味することではない。
【００５２】
上記のことを念頭において、図１のＧＰＳ及び類似するものは様々な目的に用いられる。一般的に、ＧＰＳは衛星ラジオに基づいたナビゲーションシステムであり、連続的な位置、速度、時間、及び場合によっては制限されない数のユーザの道案内情報を決定することが可能である。以前はＮＡＶＳＴＡＲという名前で知られていたＧＰＳは、非常に正確な軌道で地球周りを回っている複数の人工衛星を含む。これらの正確な軌道に基づいて、ＧＰＳ人工衛星は自らの位置をＧＰＳデータとして任意の数の受信ユニットにでも中継することができる。しかし、ＧＬＯＮＡＳＳ，Ｅｕｒｏｐｅａｎ Ｇａｌｉｌｅｏ ｐｏｓｉｔｉｏｎｉｎｇ ｓｙｓｔｅｍ， Ｃｏｍｐａｓｓ ｐｏｓｉｔｉｏｎｉｎｇ ｓｙｓｔｅｍ，またはＩＲＮＳＳ（Ｉｎｄｉａｎ Ｒｅｇｉｏｎａｌ Ｎａｖｉｇａｔｉｏｎａｌ Ｓａｔｅｌｌｉｔｅ Ｓｙｓｔｅｍ）などのＧＰＳシステムが使われ得ることは理解されるべきである。
【００５３】
ＧＰＳシステムは、ＧＰＳデータを受信するように装備された装置がＧＰＳ人工衛星の信号を探してラジオ周波数をスキャンし始めると実施される。ＧＰＳ人工衛星からラジオ信号を受信すると、装置は複数の周知方法の１つの方法で該人工衛星の正確な位置を決定する。装置はほとんどの場合、３つ以上の異なる人工衛星の信号を得るまでラジオ信号のスキャンを続ける（他の三角測量方法を用いると、位置は２つの信号でも決定することができるが、一般的には行われない）。幾何学的な三角測量を実行する際には、受信機は３つの既知の位置を用いて、人工衛星に対する自らの２次元位置を決定する。これは周知の方法で可能である。更に、４つ目の人工衛星の信号を得ると、同じ幾何学的な計算を用いて周知の方法で受信機の３次元の位置を計算することが可能となる。位置及び速度データは制限されていない数のユーザによってリアルタイムで継続的に更新できる。
【００５４】
図１に示されているように、ＧＰＳシステム１００は地球の周りを回る複数の人工衛星１０２を備える。ＧＰＳ受信機１０６はスペクトラム拡散ＧＰＳ衛星データ信号１０８をデータとして複数の人工衛星１０２から受信する。スペクトラム拡散データ信号１０８は各人工衛星１０２から継続的に発信され、発信された夫々のスペクトラム拡散データ信号１０８はデータストリームと該データストリームが由来する特定の人工衛星１０２が識別できる情報とを含む。一般的にＧＰＳ受信機１０６は、２次元の位置を計算するために少なくとも３つの人工衛星１０２から来るスペクトラム拡散データ信号１０８を必要とする。４つ目のスペクトラム拡散データ信号を受信すると、ＧＰＳ１０６は周知方法を用いて３次元の位置を計算することが可能になる。
【００５５】
図２に示された，ＧＰＳ受信機１０６を備える、又はＧＰＳ受信機１０６につながっているナビゲーション装置２００（即ち、ＰＮＤ）は、移動電話、ＰＤＡ及び／又は移動電話機能を持つ任意の装置のようなモバイルデバイス（不図示）を介して、「モバイル」または電気通信ネットワークのネットワークハードウェアとのデータセッションを成立させることが必要に応じて可能であり、例えばブルートゥース技術を用いたデジタル接続のようなデジタル接続を成立させる。その後、携帯装置はネットワークプロバイダを介して（例えばインターネットを介して）サーバ１５０とネットワーク接続を成立させることができる。したがって、“モバイル”ネットワーク接続はナビゲーション装置２００（この装置は単独で及び／又は車両の中で移動するため「モバイル」であり得、多くの場合モバイルである）とサーバ１５０との間で成立でき、「リアルタイム」または少なくとも「最新」である情報のゲートウェイを提供する。
【００５６】
モバイル装置と、サーバ１５０のような異なる装置との間に（サービスプロバイダを介して）例えばインターネットを用いてネットワーク接続を成立させることは周知の方法で実行することができる。この点において、任意の数の適切なデータ通信プロトコール（例えばＴＣＰ／ＩＰレイヤード・プロトコール）も用いることができる。更に、モバイル装置はＣＤＭＡ２０００，ＩＥＥＥ８０２．１１，ａ／ｂ／ｃ／ｇ／ｎなどの任意の数の通信スタンダードも用いることができる。
【００５７】
したがって、インターネット接続が用いられることが理解でき、該インターネット接続は、例えばデータ接続、ナビゲーション装置２００に内在する移動電話または移動電話機能を介して得られる。
【００５８】
図示されていないが、ナビゲーション装置２００はもちろん移動電話機能を内蔵し得る（例えばアンテナを含むか、又は任意的にナビゲーション装置２００の内部アンテナを使用することを含む）。ナビゲーション装置２００に内蔵された移動電話機能は内部の部品及び／又は挿入式カード（例えば、加入者識別モジュール（ＳＩＭ）カード）を含み得、必要な移動電話機能及び／又はアンテナなどを含む。したがって、ナビゲーション装置２００に内蔵された移動電話機能はナビゲーション装置２００とサーバ１５０との間で、他の移動装置と同様にネットワーク接続を成立させることができる。
【００５９】
電話の設定には、常に変化する携帯電話のモデル、メーカなどと正しく対応できるようにブルートゥース対応のナビゲーション装置を使い得、また、例えばモデル／メーカごとの具体的な設定をナビゲーション装置側に保存して置くことが可能である。この情報のために保存されたデータは更新することができる。
【００６０】
図２には、ナビゲーション装置２００が一般的な（ｇｅｎｅｒｉｃ）通信チャンネル１５２を介してサーバ１５０とつながっている様子が示されており、該チャンネル１５２は数多くの異なる構成のどれを用いても実施できる。通信チャンネル１５２は一般的にナビゲーション装置２００とサーバ１５０とをつなげる、伝播媒体またはパス（Ｐａｔｈ）を表す。サーバ１５０及びナビゲーション装置２００は、その間に通信チャンネル１５２が成立されたとき通信が可能になる（そのような接続はモバイル装置を介するデータ接続、パソコンでインターネットを介する直接接続などであり得る）。
【００６１】
通信チャンネル１５２は特定の通信技術に限定されるものではない。更に、通信チャンネル１５２は１つの通信技術に限定されるものではない。つまり、チャンネル１５２は様々な技術を用いる複数の通信リンクを含み得る。例えば、通信チャンネル１５２は電気的、光学的、及び／又は電磁気的な通信などのための通路を提供するように構成され得る。したがって、通信チャンネル１５２は以下のもの及びその組み合わせを含むが、これらに限定されるものではない：電気回路、ワイヤ及び同軸ケーブルなどの導電体、光ファイバ・ケーブル、変換器、無線周波数（ＲＦ） 、大気、空間など。更に、通信チャンネル１５２はルータ、リピータ、バッファ、送信機、受信機などの中間装置を含み得る。
【００６２】
１つの例示的な構成では、通信チャンネル１５２は電話及びコンピュータネットワークを含む。更に、通信チャンネル１５２は、赤外線通信、マイクロ波周波数通信のような無線周波数通信などのワイヤレス通信を提供し得る。更に、通信チャンネル１５２は、人工衛星通信も可能である。
【００６３】
通信チャンネル１５２を介して発信される通信信号には、ある通信技術に必要又は好ましい信号を含むが、これらに限定されない。例えば、信号は時分割多元接続（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）、符号分割多元接続（ＣＤＭＡ）、グローバル・システム・フォー・モバイル・コミュニケーションズ（ＧＳＭ）、汎用パケット無線システム（ＧＰＲＳ）などの移動体通信技術を用いるように構成され得る。デジタル及びアナログの両方の信号が通信チャンネル１５２を介して送信され得る。これらの信号は通信技術に応じて調節、暗号化、及び／又は圧縮された信号であり得る。
【００６４】
サーバ１５０は、図示されていない要素に加えて、メモリ１５６に接続され、さらに有線又は無線接続１５８によって大量データ保存装置１６０に動作可能なように接続された、プロセッサ１５４を備える。大量データ保存装置１６０にはナビゲーションデータ及びマップ情報が保存されており、サーバ１５０とは別個の装置であり得、又はサーバ１５０の中に含まれ得る。プロセッサ１５４はさらに送信機１６２及び受信機１６４に動作可能なように接続されており、情報を通信チャンネル１５２を介してナビゲーション装置２００との送受信を行う。送受信された信号はデータ、通信、及び／又は他の伝播された信号であり得る。送信機１６２及び受信機１６４は、ナビゲーションシステム２００の通信構成に使用された通信要件及び通信技術に応じて選択または設計され得る。更に、送信機１６２及び受信機１６４の機能は、１つの送受信機に合体され得る。
【００６５】
上記のように、ナビゲーション装置２００は、通信チャンネル１５２を介してサーバとの通信が可能であり、通信チャンネル１５２を介して送信機１６６及び受信機１６８を用いて信号及び／又はデータを送受信する。これらの装置はサーバ１５０以外の装置との通信にも用いられ得る。更に、送信機１６６及び受信機１６８は、ナビゲーションシステム２００の通信構成に使用された通信要件及び通信技術に応じて選択または設計され、送信機１６６及び受信機１６８の機能は図２に関連付けて上記に説明されているように１つの送受信機に合体され得る。もちろん、ナビゲーション装置２００は他のハードウェア及び／又は機能的部品を備えており、これらは後で詳細に説明される。
【００６６】
サーバメモリ１５６に保存されたソフトウェアはプロセッサ１５４に命令を提供し、サーバ１５０がナビゲーション装置２００にサービスを提供できるようにする。サーバ１５０によって提供される１つのサービスは、ナビゲーション装置２００からのリクエストを処理することと、ナビゲーションデータを大量データ保存装置１６０からナビゲーション装置２００に送信することとを含む。サーバ１５０によって提供できるもう１つのサービスは、希望されるアプリケーションのために様々なアルゴリズムを用いてナビゲーションデータを処理することと、これらの計算の結果をナビゲーション装置２００に送信することとを含む。
【００６７】
サーバ１５０は、ナビゲーション装置２００が無線チャンネルを介してアクセスできる遠隔のデータ・ソースである。サーバ１５０は、ローカルエリア・ネットワーク（ＬＡＮ），広域ネットワーク（ＷＡＮ），仮想プライベート・ネットワーク（ＶＰＮ）などに含まれるネットワークサーバを含み得る。
【００６８】
サーバ１５０はデスクトップまたはノートブックのようなパソコンを含み得、通信チャンネル１５２はパソコンとナビゲーション装置２００とを接続させるケーブルであり得る。代わりに、パソコンをナビゲーション装置２００とサーバ１５０との間において接続させ、サーバ１５０とナビゲーション装置２００との間にインターネット接続を成立させるようにし得る。
【００６９】
ナビゲーション装置２００には情報ダウンロードを介してサーバ１５０から情報が提供され得、該情報は時々またはユーザがナビゲーション装置２００をサーバに接続させた際、自動的に更新され得、及び／又は無線移動接続装置及びＴＣＰ／ＩＰ接続などを介して、サーバ１５０とナビゲーション装置２００との間でより継続的で頻繁に接続が成立される場合はよりダイナミックに更新され得る。多くの計算を処理するためには、サーバ１５０にあるプロセッサ１５４を用いてその大半を処理することができるが、ナビゲーション装置２００のプロセッサ（不図示）も大量の処理や計算を行うことができ、多くの場合はサーバ１５０への接続と関係なくそのような作業が可能である。
図３を参照すると、ナビゲーション装置２００のブロック図はナビゲーション装置２００の全ての構成要素が含まれているのではなく、いくつかの例示的な部品を示していることが明らかである。ナビゲーション装置２００はハウジングの中に配置されている（不図示）。ナビゲーション装置２００は、例えば上記のプロセッサ２０２を備える処理回路を含み、プロセッサ２００は入力装置２０４及び表示画面２０６のような表示装置に連結されている。入力装置２０４の数はいくつでもよく、キーボード装置、音声入力装置、タッチパネル及び／又は他の周知の情報入力装置を含み得る。同様に、表示画面２０６は任意の表示画面であり得、例えば液晶表示（ＬＣＤ）などを含み得る。
【００７０】
ある構成では、入力装置２０４と表示画面２０６が、タッチパネルのような入力兼表示装置として一体化されており、一体化された入力兼表示装置は情報の入力（直接入力、メニュー選択など）及び情報の表示の両方を可能にするタッチパッドまたはタッチ画面入力２５０を含み、これによってユーザは常時画面２０６の一部をタッチすることだけで、表示された複数の選択肢の１つを選択したり、複数のバーチュアル或いは“ソフト”ボタンを押すことが可能となる。これに関しては、プロセッサ２０２は、タッチスクリーンとともに作動するグラフィカル・ユーザー・インターフェース（ＧＵＩ）を支持する。
【００７１】
ナビゲーション装置２００において、プロセッサ２０２は接続２１０を介して入力装置２０４に動作可能なように接続され、入力装置２０４からの入力情報を受信することができ、さらには少なくとも１つの表示画面２０６及び出力装置２０８に夫々の出力接続２１２を介して情報を出力するように接続されている。ナビゲーション装置２００は、例えば音声出力装置（例えばスピーカ）などの出力装置２０８を備え得る。出力装置２０８は、ナビゲーション装置２００のユーザに音声情報を生成できるように、入力装置２０４も同様にマイク及び音声入力指示を受け取るソフトウェアを含むことができる。更に、ナビゲーション装置２００は追加的な入力装置２０４及び／又は出力装置を備え得、例えば音声入力／出力装置を備え得る。
【００７２】
プロセッサ２０２は接続２１６を介してメモリ２１４に動作可能なように接続されており、接続２２０を介して入力／出力（Ｉ／Ｏ）ポート２１８と情報を送受信できるように構成されており、Ｉ／Ｏポート２１８はナビゲーション装置２００の外部装置であるＩ／Ｏ装置２２２に接続可能である。外部Ｉ／Ｏ装置２２２は、イヤピースのような外部聴取装置を含み得るが、これに限定されない。Ｉ／Ｏ装置２２２への接続は有線又は無線を介する任意の外部装置への接続であり得、例えばハンズフリー操作及び／又は音声作動を可能にするカーステレオユニットへの接続、イヤピースやヘッドフォンへの接続、及び／又は携帯電話への接続などがあり、携帯電話への接続はナビゲーション装置２００とインターネット又は他の任意のネットワークとの接続を成立させるために用いられ、及び／又はインターネットまたは他のネットワークを介してサーバへの接続を成立させるために用いられ得る。
【００７３】
ナビゲーション装置２００のメモリ２１４は不揮発性メモリ（例えばプログラムコードを保存するため）の一部、及び揮発性メモリ（例えばプログラムコードが実行されるとデータを保存するため）の一部を備える。ナビゲーション装置は更にポート２２８を備え、ポート２２８は接続２３０を介してプロセッサ２０２と通信し、取り外し可能なメモリカード（一般的にカードと呼ばれる）が装置２００に入れられるようにする。説明される実施形態では、ポートにはＳＤ（Ｓｅｃｕｒｅ Ｄｉｇｉｔａｌ）カードが加えられるように構成されている。他の実施形態では、ポートは異なる形式のメモリ（例えばコンパクトフラッシュ（登録商標）（ＣＦ）カード、メモリスティック（登録商標）、ｘＤメモリカード、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）フラッシュドライブ、ＭＭＣ（マルチメディア）カード、スマートメディアカード、マイクロドライブ等）が接続できるようにし得る。
【００７４】
図３は、接続２２６を介する、プロセッサ２０２とアンテナ／受信機２２４との間の動作可能接続をさらに示しており、アンテナ／受信機２２４は例えばＧＰＳアンテナ／受信機であり得、したがって図１のＧＰＳ受信機のように機能する。参照番号２２４で指定されたアンテナ及び受信機は、説明のために概略的に１つとしてあらわしているが、アンテナ及び受信機は異なる位置に配置される部品であり得、アンテナは例えばＧＰＳパッチアンテナ又はらせん状のアンテナであり得る。
【００７５】
当業者であれば、図３に示された電子部品は１つ以上の電源（不図示）によって従来のように電力が供給されることは明らかである。そのような電源は内部電池及び／又は低電圧直流（ＤＣ）電源の入力または他の任意の 適切な構成をも含み得る。当業者には明らかであるように、図３に示された部品の異なる配置も考えられる。例えば、図３に示された部品は、有線及び／又は無線の通信及びそのようなものによってお互いに通信し得る。したがって、ここに説明されるナビゲーション装置２００は携帯又はハンドヘルドのナビゲーション装置２００であり得る。
【００７６】
さらに、図３の携帯又はハンドヘルド・ナビゲーション装置２００は、周知の様式で自転車、オートバイ、車、又はボートのような乗り物につなげる、又は「ドッキング」させることができる。そのようなナビゲーション装置２００は、携帯又はハンドヘルド使用のためドッキング位置から取り外すことができる。異なる実施形態では、ユーザのナビゲーションを可能にするために、装置２００はハンドヘルド装置として構成され得る。
【００７７】
図４を参照すると、ナビゲーション装置２００は、一体化された入力兼表示装置２０６及び図２に示されたほかの部品（内部ＧＰＳ受信機２２４、プロセッサ２０２、電源（不図示）、メモリシステム２１４などを含むが、これらに限定されない）を含む１つのユニットであり得る。
【００７８】
ナビゲーション装置２００は、アーム２５２に固定され得、アーム２５２は乗り物のダッシュボード／窓などに吸着カップ２５４を用いて固定され得る。このアーム２５２は、ナビゲーション装置２００がドッキングされ得るドッキング・ステーションの一例である。ナビゲーション装置２００は、例えばアーム２５２にカチッとはまるような結合でドッキング又は結合され得る。すると、ナビゲーション装置２００はアーム２５２に対して回転可能になり得る。ナビゲーション装置２００とドッキング・ステーションとの結合を分離させるためには、例えば、ナビゲーション装置２００のボタンを押すことで外れるようにし得る。ナビゲーション装置２００とドッキング・ステーションとの結合及び分離に適している構成は、当業者には周知である。
【００７９】
図５を参照すると、プロセッサ２０２及びメモリ２１４はお互いに協力して、ナビゲーション装置２００の機能的ハードウェア部品２８０と、装置によって実行されるソフトウェアとの間のインタフェースとして機能するＢＩＯＳ（Ｂａｓｉｃ Ｉｎｐｕｔ／Ｏｕｔｐｕｔ Ｓｙｓｔｅｍ）を支持する。次に、プロセッサ２０２はメモリ２１４からオペレーティング・システム２８４をロードし、（既述したルート計画機能及びナビゲーション機能のいくつか又は全てを実行する）アプリケーションソフト２８６が実行できるような環境を整える。アプリケーションソフト２８６は、マップの表示、ルート計画、ナビゲーション機能及び他の関連する機能などのナビゲーション装置の中心的な機能をサポートするＧＵＩを含む、操作環境を提供する。この点において、アプリケーションソフト２８６の一部はビュー生成モジュール２８８を備える。
【００８０】
説明されている実施形態では、ナビゲーション装置のプロセッサ２０２は、アンテナによって受信されたＧＰＳデータを受信するように、そして時々そのＧＰＳデータをその受信時のタイムスタンプと共にメモリ２１４保存し、ナビゲーション装置の位置記録を蓄積するように、プログラムされている。そのように保存されたデータ記録はＧＰＳの測定位置と考えられ得る。即ち、ナビゲーション装置の位置の測定位置であり、緯度、経度、タイムスタンプ、及び精度レポートを備える。
【００８１】
ある実施形態では、データは実質的には定期的に保存され、例えば５秒ごとに保存され得る。当業者には他の間隔を用いることが可能であることが明らかであり、データの分解能とメモリの容量のバランスがあることが明らかである（即ち、データをより多くとることでデータ分解能は上がるが、そのデータを保存するためにより大きいメモリ容量が必要となる）。しかし、異なる実施形態では、データの分解能は実質的に１秒ごと、１０秒ごと、１５秒ごと２０秒ごと、３０秒ごと、４５秒ごと、１分ごと、２，５分ごと（または、これらの間の任意の間隔）であり得る。したがって、装置のメモリには、様々な時点における装置２００の位置に関する記録が蓄積されている。
【００８２】
ある実施形態では、間隔が長くなると、得られるデータの質が低下することがあり得、低下の程度はナビゲーション装置２００の移動速度にもよるが、間隔の時間として１５秒が、適切な上限となり得る。
【００８３】
ナビゲーション装置２００は一般的に自らの位置に関する記録を蓄積するように構成されているが、ある実施形態では移動の開始時又は終了時においてデータの記録を所定の期間行わない。そのような構成を用いることで、ユーザの家屋及びユーザが頻繁に訪れる場所などを保護することが可能となり、ナビゲーション装置２００のユーザのプライバシーを守ることができる。例えば、ナビゲーション装置２００は移動開始から約５分又は約１マイル（１．６ｋｍ）に関するデータを保存しないように構成され得る。
【００８４】
異なる実施形態では、ＧＰＳは定期的に保存される訳ではなく、所定のイベントが発生するとメモリに保存されるように構成され得る。例えば、プロセッサ２０２は、道路の分岐点、道路区域の変更、又はそのようなイベントが発生するとＧＰＳデータを保存するようにプログラムされ得る。
【００８５】
さらに、プロセッサ２０２は、時々装置２００の位置に関する記録（即ち、ＧＰＳデータ及びタイムスタンプ）をサーバ１５０にアップロードするように構成されている。ナビゲーション装置２００が常在又はほぼ常在する通信チャンネル１５２を持つような実施形態では、通信チャンネル１５２によるサーバ１５０への接続及びデータのアップロードは定期的に行われ、例えば２４時間ごとに行われ得る。当業者には、他の間隔を用いることも可能であることが明らかであり、その間隔は１５分、３０分、１時間、２時間、５時間、１２時間、２日、１週間、又はこれらの間の任意の間隔であっても良い。そのような実施形態においては、プロセッサ２０２は、位置の記録を実質的にリアルタイムでアップロードするように構成され得、このような構成はデータ送信の間隔が短くなることを意味し、疑似リアルタイムと考えることがより正しい。そのような疑似リアルタイム実施形態では、ナビゲーション装置はメモリ２１４内、又はポート２２８に挿入されたカード内にＧＰＳ測定位置をバッファできるように構成され得、又、所定の数の測定位置が保存されるとこれらを送信するように構成され得る。この所定の数は２０、３６、１００、２００程度、又はそれらの間の任意の数でもあり得る。当業者には、この所定の数はメモリ２１４／ポート２２８のカードの容量にある程度支配されることが明らかである。
【００８６】
常在する通信チャンネル１５２を持たない異なる実施形態では、プロセッサ２０２は、通信チャンネル１５２が作られるとサーバ１５０に記録をアップロードするように構成され得る。通信チャンネル１５２が作られることは、例えばナビゲーション装置２００がユーザのコンピュータに接続される時などである。このような実施形態でも、ナビゲーション装置２００はメモリ２１４内、又はポート２２８に挿入されたカード内においてＧＰＳ測定位置をバッファできるように構成され得る。メモリ２１４又はポート２２８に挿入されたカードがＧＰＳ測定位置 で満たされた場合はナビゲーション装置は最古のＧＰＳ測定位置を削除するように構成され得、したがって先入れ先出し（ＦＩＦＯ）バッファであると考えられる。
【００８７】
説明される実施形態では、位置の記録は１つ以上の軌跡を含み、夫々の軌跡は２４時間の期間内のナビゲーション装置２００の移動を表す。それぞれの２４時間の期間は暦日と一致するように構成されているが、必ずしもこのようにする必要はない。
【００８８】
一般的に、ナビゲーション装置２００のユーザは、装置の位置に関する記憶がサーバ１５０にアップロードされることに対して承認する。承認が得られなかった場合は、記録はサーバにアップロードされない。ナビゲーション装置及び／又は装置が接続されたコンピュータは、位置記録の使用に関してユーザに承認を要請するように構成され得る。
【００８９】
サーバ１５０は装置の位置記録を受信し、処理のため大量データ保存装置１６０に保存するように構成されている。したがって、ナビゲーション装置２００がアップロードした、複数の装置の位置記録が、時間とともに大量データ保存装置１６０に蓄積される。
【００９０】
上記のように、大量データ保存装置はマップデータも保存し得る。そのようなマップデータは、道路区域、注目すべき場所の位置など、マップに載っている一般的な情報を提供する。
【００９１】
最初の工程として、サーバ１５０はマップデータと、受信した位置記録に含まれるＧＰＳ測定位置とのマップマッチング機能を行うように構成されており、そのような工程は、図６に関連付けて説明されている。そのようなマップマッチングは、位置記録は受信されているため、いわゆるリアルタイムで行われてもよく、又は大量データ保存装置１６０から位置記録が再び読み込まれた際に行っても良い。
【００９２】
マップマッチングの精度を改善させるために、下記のように位置記録の前処理を行う。各ＧＰＳ軌跡（即ち、２４時間分のＧＰＳデータ）は１つ以上の移動に分けられ（６００）、各移動はナビゲーション装置２００の１つの移動であり、後の処理のために保存されたものを表す。
【００９３】
各移動において、ナビゲーション装置から受信したＧＰＳ測定位置の中で精度に関するレポートが十分に高くないものは拒絶される。したがって、ある実施形態では、ある測定位置に関して３つ未満の人工衛星１０２からのシグナルしかナビゲーション装置２００に受信できていない場合は、その測定位置は拒絶され得る。更に、各移動は、２つの測定位置間の報告された時間がある限界の値を超えると区切られる（６０４）。この前処理工程を通った各移動はマップマッチングの方に通される。
【００９４】
これに関連して、区切られた移動は、連続したＧＰＳ測定位置の間に、所定の時間よりも大きい所定の時間間隔が存在する移動である。 したがって、乗り物が停止したことが推論でき、最初の移動が終わり、2番目の移動が始まったと考えるべきである。したがって、区切られた移動は、２つの別個の移動となる。
【００９５】
しかし、ＧＰＳの信号が届かなかったことが原因でＧＰＳ定位の間にギャップが生じることもあり得るため、１つの移動を区切る前に、乗り物の位置が変わったかをチェックする。そして、そのような状況である場合は移動を区切ることは行わない。説明される実施形態では、この所定の時間はおおよそ３分である。しかし、１５秒、３０秒、１分、９０秒、２分、５分、１０分、又はこれらの間の任意の時間など、他の任意の適切な時間が該所定の時間として用いられることは当業者には明らかである。ここに説明されるように、ＧＰＳ測定位置を送信するナビゲーション装置２００の平均速度がある所定の限度より低い場合、ある実施形態では、データは後の処理において拒絶され得る。そのような実施形態は、衝突などの事故後に発生し得る渋滞に関する情報を排除し、定常状態の交通の流れをより正確に表すデータを残すため、有用であり得る。
【００９６】
次に、各移動を順に取り、その移動に含まれる定位をマップデータ内のマップにマッチングする。各マップは複数の道路区域を備えており、道路区域に沿って移動することが可能であり、各区域は直線のベクトルでマップ上に表わされている。
【００９７】
サーバ１５０のプロセッサ１５４において実行されているプログラムコードは、ある区域の中に位置する測定位置、又はある区域内で発生したと考えても良いほど（即ち、該区域の距離限度内にある）その区域に十分に近い測定位置が見つかるまで処理中の測定位置から離れるように構成されたマップマッチング機能 を提供する。この限度を用いることで、１００％以下のＧＰＳ精度を許し、道路を直線状のベクトルに分解して得られる圧縮効果を可能とする。
【００９８】
各移動は最初の測定位置（即ち、移動における１番目の測定位置）を持っており、この最初の測定位置は、区域の選択を絞るために使え得る同定された測定位置がまだ存在しないため、同じ移動内における他の測定位置より、区域と関連付けることが難しい。もし、複数の区域が１番目の測定位置の限度内に含まれる場合は（６０６）、アルゴリズムは、同じ移動内における次のＧＰＳ測定位置（即ち、２番目の測定位置）を参照し、２つの測定位置間（即ち、１番目の測定位置と２番目の測定位置の間）の距離に対応して可能な動きに基づいて、複数の区域からいくつかのルートのセットを生成する。２番目の測定位置を用いても、１番目の測定位置に関して１つの区域候補に至らない場合は、アルゴリズムは同じ移動内の３番目の測定位置に移り、１番目の測定位置に関して１つの候補を探し出すために、可能性のあるルートを生成し、比較する。この工程は、１つの移動における残りのＧＰＳ測定位置が処理されるまで続く。
【００９９】
このような実施形態の利点は、１番目の測定位置だけでは複数の区域の近辺に存在し得、そしてこれらの区域を区別することはできないが、更なる動き（即ち、２番目及び３番目の測定位置）を用いることで、１番目の測定位置に関連する区域の正体を決定することが可能になる。したがって、移動の１番目の区域はマップマッチング機能 によって決定される。移動の１番目の区域が決定されると、更なる区域を同定するために更なる測定位置を処理する。もちろん、次の測定位置が１番目の測定位置と同じ区域内に位置することは可能である（６１２）。
【０１００】
したがって、移動におけるその後の測定位置は、同じ区域の距離限度内に含まれるかを決定するために処理され（６１０）、マップマッチング機能はその区域と距離限度内に位置する測定位置とを関連付けるように構成されている。マップマッチング機能によって処理された測定位置が距離限度内に入っていないと、その測定位置に対応する新たな区域候補を生成するように構成されている。しかし、次の区域が、直前に処理された区域の端につながるようにする限定を加えることも可能である。これらの隣接する区域は、基礎をなすマップデータからマップマッチング機能によって得られる。
【０１０１】
距離限度内に存在する区域がないこと、又は１つの区域に絞ることができないことにより、前の区域に続くある測定位置に対してマップマッチング機能が区域を同定できない場合は、単独のマッチが成立する１つの区域を同定するまで移動を制約するために、マップマッチング機能は更なる測定位置を探り続ける（６１６）。つまり、ｎ番目の定位が１つだけの区域に関連付けられない場合、区域の同定をさらに絞るためにｎ＋１番目の測定位置を用いる。ｎ＋１番目の定位が１つの区域の同定につながらない場合は、ｎ＋２番目の測定位置を用いる。いくつかの実施形態では、この処理は１つだけの区域が同定されるまで、又は移動内の全てのＧＰＳ測定位置が同定されるまで、続けられる。
【０１０２】
マップマッチング機能は単独の区域を同定するように構成されている。説明される実施形態では、マップマッチング機能は継続する経路を作ることを試みることなく、ただ区域を測定位置にマッチングしていく。異なる実施形態では、マップマッチング機能は継続する経路を作ることが望ましい。
【０１０３】
したがって、処理が終わるとマップマッチング機能は、分析中の移動においてナビゲーション装置２００の動きが沿った道路区域の一連を取得する。次に、マップマッチング機能はこれらの道路区域を処理し、ＧＰＳ測定位置から進入時間及び該区域の通過時間を割り当てる。これらの割り当てられた時間は、後の処理のため大量データ保存装置１６０に保存される。各区域に複数のＧＰＳ測定位置が保存されていることもあり得る。しかし、各区域に対して関連付けられたＧＰＳ測定位置の数がいくつであれ、区域における平均速度は入っている時間、ＧＰＳ定位及び区域の長さ（この実施形態ではマップデータ内に保存されている）を用いて計算される。この平均速度は、対応する割り当てられた時間及び区域と関連付けられ、大量データ保存装置１６０に保存される。道路区域における交通の流れの速度に関連し、その区域に割り当てられた情報は、その道路区域の速度データにとして考えられ得る。
【０１０４】
サーバ１５０は、割り当てられた時間を処理し、それから１つ以上の平均値を下記のように生成する平均値機能を提供するために、平均値を計算するプログラムコードをプロセッサ１５４において実行するように構成されている。この実施形態で用いられる平均値計算工程は、図７を参照しながら説明される。
【０１０５】
工程の第１ステップ（７００）では、平均値機能は、処理中のマップにおける各道路区域の平均速度をグループ化する。各道路区域のグループにおいて、平均値機能は、所定の時間間隔内の平均速度をグループ化するようにさらに構成されている（７０２）。したがって、同じ時間内（たとえば、８：００ＡＭから８：５９ＡＭの間）で発生する平均速度は同じグループに含まれ、更に分析される。説明されている実施形態では、時間は１時間であるが、必ずしも１時間であることはなく、時間の長さを短くするとデータの分解能は上がるが、同時に保存に必要な容量も増えてしまうことは当業者には明らかであろう。他の適切な時間としては、実質的に、１分、５分、１０分、１５分、３０分、２時間、６時間、１２時間、またはこれらの間の任意の時間でもよい。
【０１０６】
ここで説明されている実施形態では、平均速度は、中央標準時間ではなく 、処理されるマップに含まれる領域の現地時間で保存されている。そのような方法は、交通に関するものに関する自然な基盤を提供するため、便利である。
【０１０７】
１つの移動において発生した平均速度が所定の時間にグループ化される前に、平均速度はデータの質を改善させるために選別される。この実施形態では、所定の範囲内に含まれる平均速度だけがグループに追加される。この実施形態では、所定の速度上限（１８０ｋｍ／ｈなど）を超える速度を排除し、所定の速度下限（２ｋｍ／ｈ）を下回る速度も排除する。当業者には、ある区域の平均速度をはるかに下回る速度は、その区域における交通の問題（例えば、渋滞など）と関連があり得ることが明らかであろう。したがって、そのような状況に関するデータを含むことは、通常の状態を示すものとして考える場合、全体の精度を低下させ得る。他の実施形態では、許可される最大の速度は、その区域の制限速度であり得るが、そのような情報は処理されるマップデータにおいては不正確であり得ること、そしてある区域の制限速度は実際にその区域の交通状況を正確に表すものではないこともあり得るというのは、当業者には明らかである。
【０１０８】
所定の時間にグループ化することが実行されると、道路区域ごとの平均速度が所定の時間ごとに計算される。例えば、８：００ＡＭから８：５９ＡＭまでの時間における全ての速度が、道路区域ごとに平均化される。平均速度を計算するためにはいくつかの選択肢があり、算術平均又は調和平均を用いる方法、或いは中央値を計算する方法がある。実際に、ある実施形態では、後の用途によって異なるデータセットに異なる重みを付けることができる。
【０１０９】
したがって、説明されている実施形態、及び処理されるマップには、マップの各道路区域には２４個の平均速度が生成されており、これらは所定の１時間の時間間隔における平均速度である。もし異なる長さの時間が用いられると、異なる数の平均速度が生成されることは明らかである。更に、全ての道路区域が全ての時間における平均速度を持っているとは限らないことも明らかであり、これは、ある道路は交通量が少なく、特に早朝などの時間帯は交通量が少ないためである。
【０１１０】
しかし、区域ごとの平均速度を更に使用する前に、品質のチェックが行われる（７０６）。この実施形態では、チェックによって所定の数以上の割り当てられた時間が平均速度の計算に用いられることを確実にする。このような条件に合わない平均速度は、更なる処理のために排除され、その区域のひとつ以上の時間においてギャップが生じるようになる。ある実施形態では、５つ以下の値が平均速度の計算に使われた場合、その平均速度は排除される。他の実施形態は、異なる数を用い得、例えば２，３，４，６，７，８，１０，２０個の値、又はこれらの間の任意の値をも用い得る。
【０１１１】
又、平均値の品質に関する更なるチェックが行われ、ここでは平均値ごとの標準偏差を、その区域のその時間の平均値を計算するために用いられたデータサンプルの数の平方根 で割る。この計算の結果が所定の限度を超える場合は、その平均値は排除され、その区域のその時間にはギャップが生じるようになる。
【０１１２】
更なる品質チェックを行い、下記のような平均値を排除することも可能である：データの偏差が所定の限度を超えているか、所定の限度を超える外れ値が所定の数以上あるか。当業者には、そのような統計的技術を用いてデータの品質を確実にすることは明らかであろう。
【０１１３】
ある道路区域の平均値のセットは、その道路区域の観測された速度プロファイル と考えられ得る。
【０１１４】
ある道路区域の測定された速度プロファイルに少数の速度値が欠けている場合（即ち、全て又は少なくとも大勢の所定期間は値を持っている）、その区域は処理され得、欠けている値は隠され得る。欠けた区域 の数が増えると、結果として生じるクラスタ分析の品質は低下する。したがって、幾つの期間が欠けても許可できるかは、品質に関する選択であり、ケースによって検討する必要がある。高品質の完全なデータだけを用いることは、高速道路のような交通量の多い道に過剰な重みを付けることを意味し得る。必要条件が低すぎると（即ち、多くの期間が欠けている道路区域をクラスタ化すること）は、現実的でないクラスタ及び不正確な分析をもたらす。
【０１１５】
これらの品質チェックを通った平均値は信頼性があるとみなされ、更なる処理に用いられることが許可される。 ステップ７０８では１つの道路区域当たりの平均速度のカバレージに関する分析が行われる。 信頼性のある平均値のカバレージが十分に高い場合は、マップデータは更なる処理を受ける。しかし、カバレージが所定の限度以下であればマップは排除される。許可可能なマップは、図８を参照して説明されているように、クラスタ形成のために通される。
【０１１６】
そのようなクラスタ形成は、毎週繰り返される、日などの期間についての標準的な速度プロファイルを自動的又は半自動的に抽出することを目的とする。後で述べるように、類似する分類の道路はその速度プロファイルも類似しているのであれば、大幅なデータの圧縮が達成できる。例えば、日曜日の午前１０時の、道路の第１区域における速度は、同じ道路の第２区域における同期間の速度と類似し得る。これらの道路区域における類似性が他の時間帯においても繰り返されている場合は、第１の区域と第２の区域は、同じ速度プロファイルで表わされていると考え得る。したがって、これから定義するクラスタ化はそのような類似性を見つけることを目的とするものである。速度プロファイルの正規化も、下記のように、速度プロファイルを異なる分類の道路に用いることを可能とし得る 。
【０１１７】
クラスタ化を行う前に、測定された速度プロファイルは夜間の期間を合併させるためにさらに処理される。この実施形態では、９ＰＭから５ＡＭ（即ち、８個の期間）までの平均速度が平均化され、この夜間平均がこれらの８個の期間のそれぞれとして用いられる。したがって、各速度プロファイルは９ＰＭから８ＡＭ の間には平らなプロファイルを持っており、その道路区域の交通の自由流れ速度であると言える。自由流れ速度は、通常車のような乗り物がその道路において移動する際の速度として考えることができ、自由流れ速度はその道路区域の制限速度とは異なり得る。また、自由流れ速度はその道路区域の制限速度とほぼ同じであり得る。
【０１１８】
第１のステップ８００では、クラスタの数を制限するために、測定された速度プロファイルを正規化させる。そのような正規化はいくつかの基準に従って行い得る。説明されている実施形態では、正規化は、ある平均速度と関連付けられた道路区域について計算された自由流れ速度に従って実行される。したがって、クラスタ化アルゴリズムに通される、道路区域ごとの平均速度は、０と１の間の値を持っている。そのような方法は、クラスタ化によって生成される速度プロファイルを、道路の種類から独立させることができ、同じ速度プロファイルのセットを、任意の種類の道路の区域にも用いることができるため、更なるデータ圧縮を可能にする。
【０１１９】
夜間の自由流れ速度を用いることは、夜間の速度値を考慮しないことを可能とするため、クラスタ形成の次元を減らせ得る。
更なる実施形態では、ある道路区域の平均速度又は制限速度を、正規化の更なる基準として用い得る。
【０１２０】
したがって、クラスタ化アルゴリズムを用いて類似した交通の振る舞いを見せる日を一緒にグループ化することができる。期待される交通の振る舞いが異なる場合は、クラスタ形成は独立的に実行されるべきである。クラスタ化アルゴリズムに入力されるパラメータは、希望されるクラスタの数であり、典型的な範囲は曜日ごとに１０〜７０個である。最適のクラスタにたどり着くための周知の方法がいくつかあり（例えば、何らかの品質指標を与えることや、トレンドによって数を増加／減少させることなど）、これらを用いてクラスタ化のアウトプットが容認できるかを決定し得る。
【０１２１】
ある実施形態では、クラスタ化アルゴリズムは約６０クラスタを生成するように構成されている。他の実施形態では、アルゴリズムは最初はより多い又はより少ないクラスタを生成するように構成される。結果として生じるクラスタは、満足できるものであるか（例えば、実質的に同じクラスタはないか？不連続的なクラスタはないか？）を調べるために処理される。問題のあるクラスタがあれば、アルゴリズムを再実行させ、１回目より少ない数のクラスタを生成することを目標とする。この反復工程は、満足できるクラスタのセットが決定されるまで繰り返される。
【０１２２】
ある実施形態では、クラスタが満足できるものか は、クラスタによって生成されるプロファイルが所定の限度以上の周波数を含む かを調べるステップを含む。そのような周波数は、クラスタによって生成されたプロファイルの中に高すぎる変化率を持つ（即ち、不連続性があり得る）ことを示し、もしそのようなデータを使用すると、ナビゲーション装置２００が不安定になるなどの問題が起こり得る。また、クラスタが満足できるものであるか否かは 、クラスタによって生成された速度プロファイルの各々をお互いに、又は少なくともいくつかをお互いに、比較する工程を含む。ある１つの実施形態では、これは最小二乗比較によって行われ得る。
【０１２３】
ある実施形態では、クラスタ 化はクラスタ分析によって行われ得るが、他のクラス構築方法を用いても良い。単純で効率的な方法としては、いわゆるＫ平均法がある。この非階層クラスタ分析方法は通常ｋランダム・シードから始まり、選択された測定基準に基づく最小エラー基準に従ってクラスのメンバの再分布を行う。このアルゴリズムは極小値にしか至らないため、最適な解決のためには複数回繰り返す必要がある。最終的なクラスタの重心は所定のクラスタを形成する。異なる実施形態では、異なるクラスタ化方法を用いられ、これらは階層的クラスタ分析及びファジークラスタリング法を含み得る。
【０１２４】
ある実施形態では、更なるクラスタを加え得る（８０４）。例えば、ある実施形態は、信頼できるパターンがない道路区域（例えば、データのカバレージが小さいため、又は交通に関連する問題などのため）に関しては、平らな線を速度プロファイルとして加え得る。
【０１２５】
クラスタによって生成された速度プロファイルを作成する最終的なステップ（８０６）として、クラスタは様々な時間分解能へと補間される。ある実施形態では、これは三次元スプラインを用いて行われるが、指数フィッティングなどの異なる方法も可能である。当業者にはそのような類似する方法が用いられ得ることが明らかである。
【０１２６】
クラスタ分析工程に用いられた時間分解能が、最終的に望まれるものより粗い場合（所定の時間において信頼性のある平均速度を確保するために、このようなことが起こり得る）においても、時間分解能を調整することがこの時点で可能となる。例えば、意図する使用の要件を満たすために、より細かい分解能に調整され得る。例えば、粗い時間分解能では時間的境界において大きな差が生じる個所では、より細かい時間分解能で継続的なプロファイルを用いることが有利であり得、より滑らかな経路を提供できる。説明される実施形態では、クラスタによって生成されるプロファイルは約５分の間隔の分解能を与えるために補間される。しかし他の間隔を用いても良い。そのような間隔は、クラスタによって生成された速度プロファイルを用いて処理するときに便利であり得る。
【０１２７】
図９は、クラスタ化アルゴリズムから得られる、マップに関する通常の結果を示しており、入力された平均速度値は、クラスタ化によって生成された独立した１６個の速度プロファイルにクラスタ化されている。他の実施形態において、クラスタの数が変更されると、１つの道路区域において可能な速度プロファイルの数も変更される。
【０１２８】
クラスタ化によって生成された速度プロファイルの適切なセットが決定されると（この実施形態では１６個が生成されている）、これらは１つ以上のマップに関連付けられる。一般的に、ある速度プロファイルのセットは、そのプロファイルの源となったマップに関してより正確であり得、これはそのマップに載っていない道路における交通現象が異なり得るからである。例えば、あるマップが１つの国を含んでいるとすると、異なる国における交通は少し違うパターンで動く可能性がある。
【０１２９】
しかし、異なる実施形態では、速度プロファイルは複数のマップと関連付けられ得る。このようなことは、例えばマップが国の一部を含む場合において適切であり、及び ／又はマップを複数の国に用いることが適切であり得る。
処理中のマップに存在する各道路区域は分析され、その区域に対する１週間分の予想移動速度を決定するために、クラスタ化によって生成された１つ以上の速度プロファイルを持ち得る（図９参照）。これらの速度プロファイルは、ルートを決定するためにナビゲーション装置によって使用される、既定速度プロファイル又は通常の速度プロファイルである。この工程は図１２を参照して説明される。ｎ＝１から始まり、ｎ番目の道路区域が処理される（１２００）。
【０１３０】
ＰＮＤが処理されたマップを用いることで正確な経路を生成できるようにするためには、各道路区域が夫々高い信頼性の速度プロファイルを持つことが望ましい（第１のステップとして、測定された速度プロファイルが適切であるか評価する）。したがって、前に行った品質評価によって、測定された速度プロファイルが品質の要件を満たさないと判断された場合は、代替作戦（Ｆａｌｌｂａｃｋ Ｓｔｒａｔｅｇｙ）を用いて、測定された速度プロファイルを、ＰＮＤ又は他の装置によって経路指定のために処理した際によりいい結果を出し得る速度データで置き換える。
【０１３１】
測定された速度プロファイルが実際に不適切であると判断された場合、測定された速度プロファイルの代わりに、その道路区域において収集された全ての速度データの平均値を含む処理された道路区域についての平均速度１０００を代替状態として用いる。即ち、各日の各期間において収集されたデータの平均値を求め、１つの速度を生成する。この１つの速度はやがて、フラット・クラスタ化によって生成された速度プロファイル（図９の１５番） に割り当てられ得る 。
【０１３２】
次に、ある区域に対して収集されたデータから得られた平均速度を受け入れられるかを決定する。平均値がこれらのチェックを通ると、その平均値はその道路区域に使用される。
【０１３３】
統計学の当業者には、平均値の品質を測るための方法が明らかであろう。例えば、ある実施形態では平均値は所定の数以上の速度から生成されなければならないという条件があり得、その数は例えば１０個の速度であり得る。平均値が最低値（例えば、２ｋｍ／ｈ）以上、及び／又は最高値（例えば、１５０ｋｍ／ｈ）以下のものであることを確実にするため、平均値に限度を適用し得る。また、平均値の品質が十分であるかを決定するために標準偏差を用い得る。
【０１３４】
道路区域は、マップデータ内において分類体系によって分類され得ることが知られており、それによって類似する特徴を持つ道路区域は同じ分類に分かれる。例えば、１つの関係者によって生成されたあるマップには、道路区域が分類される８個の分類がある。ある実施形態では、所定の道路区域についての分類に含まれる道路の所定の割合以上が、平均値の生成に使われる速度を提供することを保証するために、所定の道路区域の平均値が分析される。このテストが成功しないと、平均値が拒絶されることだけでなく、次に説明される、ギャップを埋める工程も省略され得る。
【０１３５】
道路区域における交通の流れが２つの方向に可能である場合、夫々の方向に対する平均速度が存在する。
【０１３６】
測定された速度プロファイルが代替作戦において置き換えられた場合、図９のクラスタ速度プロファイル１５番のような平らな線を含む速度プロファイルが事実上存在することが明らかであろう。また、速度プロファイル情報は正規化されているため、速度プロファイル１５番は、１つの平均速度が関連付けられたどんな道路区域を表すためにも用いられ得る。
【０１３７】
ある区域において収集されたデータから得られた平均速度がいまだに品質チェックを通らない場合は、代替作戦のつぎのステップ（１００２）が用いられ、図１１を用いて次に説明する、いわゆるギャップ埋め工程が使用される。第１ステップとして、処理されるマップに存在する各道路区域は、所定数の分類のうちの１つの分類として分類される（１１００）。当業者には、この分類が１回のみ行われればいいことが明らかであり、結果として生じる分類は、ギャップ埋め工程が行われるさらなる道路区域のために保たれる。もちろん、他の実施形態では、ギャップ埋め工程が行われるたびに計算しなおしてもよく、又は分類を即座に計算しても良い。
【０１３８】
説明される実施形態では、次の表１に示されているような４０の分類が存在する。これらの分類は、処理されるマップデータ、マップに含まれる領域、又は他の関連するいかなる要因によっても異なり得る。
【表１】
【０１３９】
各道路区域が分類されると、分類ごとの平均速度が計算され（１１０２）、この場合は４０の部類の平均速度が計算される。生成された分類ごとの平均は、分類ごとに１つの数字であり、このような平均を得るためには、各所定の時間ごとの速度を、本明細書に記載された任意の適切な平均値計算方法を用いて求める。当業者には、このステップが１回のみ行われればいいことが明らかであり、結果として生じる分類ごとの平均速度は、後に行われるギャップ埋め工程のために保たれる。
【０１４０】
しかし、この実施形態では、各分類の平均速度は、分類に含まれる全ての要素の、長さによって重み付けされた調和平均として計算されており、次のような計算式を用いる：
Ｖｍｅａｎ＝Ｌ／Σｌｉ／Ｖｉ
ここで
Ｖｍｅａｎは、分類ｊの平均速度、
ｌｉは、線ｉの長さ、
Ｌは、分類ｊに含まれる全ての線の長さ合計、
Ｖｉは、線ｉの平均速度である。
【０１４１】
これらの平均速度が更に使われる前に、十分な品質のものであり、その分類の道路の平均速度を正確に表しているかをチェックする。道路の分類の所定の時間に含まれるサンプルが少な過ぎたり、又は平均の計算に用いられるサンプルのばらつきが激しい場合、品質は不十分であり得る。したがって、各平均値の品質に関するチェックが下記のように行われる（１１０４）。
【０１４２】
４０の分類中のある１つの分類からの平均速度が、ｈｉｔ＿ｎｕｍｂｅｒ＿ｍｉｎ（本実施形態については、これは表２に示されている）より少ない数の区域に基づいている場合は、表３に示されているように、この平均値は異なる分類からの値で置き換えられる。説明される実施形態では、ヒット（ｈｉｔ）の最低限の数は１０であるが、他の実施形態では異なる数を用い得る。
【０１４３】
所定の分類のｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ａｂｓ及びｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ｒｅｌのいずれも図２に示された値以下でなければ、速度分類の平均値は図２に示されているように、割り当てられた置き換え分類の平均値によって置き換えられる。ｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ｒｅｌ＿ｍｉｎは、平均速度をヒットの数の平方根で除したものに対する％として表される、分類の相対的な標準偏差として与えられ、すなわちｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ａｂｓ＊１００／ｍｅａｎ＿ｓｐｅｅｄである。
【０１４４】
したがって、任意の分類の平均速度が使えるようになるまでパスしなければいけない３つの品質要素（Ｑｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ａｂｓ＿ｍｉｎ， ｑｕａｌｉｔｙ＿ｆａｃｔｏｒ＿ｒｅｌ＿ｍｉｎ， ｈｉｔ＿ｎｕｍｂｅｒ＿ｍｉｎ）がある。品質要素をパスできない場合は、その平均速度は表３に従って置き換えられる。
【表２】
【表３】
【０１４５】
表２に示された値は例として示されており、他の実施形態では異なり得る。同様に、表３で用いられた置き換え値も、マップに含まれる領域、マップデータを生成した者などによって異なり得る。
【０１４６】
ある分類に含まれる任意の平均値が使えるようになる前に、品質チェックが行われる。これらのチェックをパスできない場合は、ギャップ埋め工程はその分類において失敗することとなる。これらの品質チェックは次のようなものである。
【０１４７】
分類の平均値は、次のように計算される最低限度のより高く、そして最高限度より低い値であり、ｍｉｎ及びｍａｘは最低関数及び最高関数の擬似的なコードである。
Ｍｉｎ＿ｓｐｅｅｄ＿ｔｈｒｅｓｈｏｌｄ＝ｍａｘ［ｍａｘ（ｍｉｎ−ｌｏｗｅｒ＿ｒｅｌａｔｉｖｅ＿ｄｅｖｉｓｉｏｎ＊ｍｉｎ／１００、ｍｉｎ−ｌｏｗｅｒ＿ａｂｓｏｌｕｔｅ＿ｄｅｖｉｓｉｏｎ），ｌｏｗｅｒ＿ｌｉｍｉｔ］
Ｍａｘ＿ｓｐｅｅｄ＿ｔｈｒｅｓｈｏｌｄ＝ｍｉｎ［ｍｉｎ（ｍｅａｎ＋ｕｐｐｅｒ＿ｒｅｌａｔｉｖｅ＿ｄｅｖｉｓｉｏｎ＊ｍｅａｎ／１００，ｍｅａｎ＋ｕｐｐｅｒ＿ａｂｓｏｌｕｔｅ＿ｄｅｖｉｓｉｏｎ），ｕｐｐｅｒ＿ｌｉｍｉｔ］
ここでｍｅａｎは、区域の適切な速度分類の平均速度である。他の値は表４に定義されている。
【０１４８】
ある区域に関連する速度がこれらの基準に合わない場合は、区域に関する速度が絶対的な速度制限に背かない限りその速度は平均速度に基づいてその閾値によって置き換えられ、そのような場合にはこの絶対的な速度制限をその区域の速度として用いる。
【表４】
当業者には、ここにおける計算は速度に関して行われており、時間に関して行われていないことが明らかであろう。
【０１４９】
したがって、ギャップ埋め工程が終わると、所定の４０の分類中の１つの分類内の道路区域に基づいた平均速度が生成され得る。しかし、それでもギャップ埋め工程が失敗することもある（即ち、品質チェックをパスする平均値が生成されていない）。
【０１５０】
したがって、関連する速度データを持たない道路区域は、ギャップ埋め工程によって生成された平均速度データ（ただし、この平均値が品質チェックにパスすれば）が割り当てられる（１１０８）。
【０１５１】
ギャップ埋めが失敗すると、ステップ１００４において、その道路区域に関連する速度は、Ｆｕｎｃｔｉｏｎａｌ Ｒｏａｄ Ｃｌａｓｓ（ＦＲＣ）に従ってマップデータ供給者から供給される速度に指定される。ＦＲＣは例えば大まかに８つの分類を含み得る（この数はマップデータ供給者によって異なり得る）。即ち、自由流れ速度はＦＲＣによる値に設定され、クラスタによって生成される速度プロファイルは、この実施形態では、プロファイル１５番である。
【０１５２】
次に、ある道路区域に関連する速度プロファイル（測定された速度プロファイル又はギャップ埋めによって挿入された平均値）は、ＰＮＤのようなナビゲーション装置で使用できるようなマップデータを生成するために、クラスタ化によって生成された１つの速度プロファイルに割り当てられる 。これは、速度プロファイルが測定された速度プロファイルであっても、クラスタ化によって生成された平らな速度プロファイル１５番を考慮した平均であっても、行い得る。
【０１５３】
ステップ１２１０では、最小二乗分析を用いて、クラスタ化によって生成された速度プロファイルのセット内のそれぞれ速度プロファイルに対して、得られた速度プロファイルが比較される。これらの１６の比較が行われた後、１６個のセットのうちのどの速度プロファイルが、該道路区域に関連する速度プロファイルに最も近いのかを判断できるようになり、ステップ１２２０では最も近いと判断された、クラスタ化によって生成された速度プロファイルへの参照が、その道路区域ついてのマップデータに保存される。該道路区域に関連して保存されるマップデータは、その道路区域の自由流れ速度であり、以前に計算されたものである。
【０１５４】
したがって、上記の参照及び自由流れ速度を用いて、各道路区域の平均速度に関する情報をマップデータ内に保存できる。交通量が多い区域は、平均速度情報は９ＡＭから５ＰＭまでの１時間ごとの平均に関する近似値を含むと考えることができる。交通量が少ない区域は、平均速度情報は全ての時間にわたって平均された平均速度と考えることができる。
【０１５５】
この工程は、マップ上の各道路速度に、クラスタ化によって生成された１６の速度プロファイルのうちの１つが関連付けられるまで繰り返される（１２３０）。
【０１５６】
マップデータが公開される前に、（測定値の代わりに挿入された平均値ではなく、）測定された速度プロファイルが関連付けられた道路区域の数が十分であるか最終チェックを行う。
【０１５７】
この最終チェックでは、各機能的道路分類（ファンクショナル・ロード・クラス：ＦＲＣ）についての道路区域の全長が計算される。下記の表５に示されているように、ＦＲＣは表２に示された４０の分類に関連している。各ＦＲＣ内において平均速度データを持つ道路区域の長さは、図５に示されているように、ＦＲＣ内の道路全長の所定の割合（限度）以上でなければならない。
【表５】
【０１５８】
ルーティング動作に一般的により大きい影響を及ぼす道路分類は、より高い割合の最低カバレージが必要となることがわかるようになるだろう。例えば、ＦＲＣ０（高速道路）は経路計画に大きい影響を及ぼすため６０％を有することが必要になるが、例えば二次道路は３０％の包含率が必要となっている。
【０１５９】
他の実施形態では、更なる代替作戦が提供され得る。そのような実施形態においては、第１の代替作戦が（測定された速度プロファイルが受け入れられないと判断された場合）、測定された速度プロファイルを夫々の日に用いることの代わりに、各日の所定の時間に関する速度プロファイルを合計し、結果として生じる合計速度プロファイルを各日に用いるものであり得る。したがって、そのような実施形態では、月曜日から金曜日までの同じ時間帯の期間を合計して週ごとの速度プロファイルが生成され、週末の速度プロファイルは土曜日及び日曜日の同じ時間帯の期間を合計することで生成される。週末の交通の流れは平日の交通の流れと異なり得ることが明らかであろう。
【０１６０】
そのように合計された速度プロファイルは、他の代替作戦を用いる前に、品質の要件を満たしているかがチェックされる。これらのチェックは、測定された速度プロファイルを評価するために用いられる要件と同じもの、又は少なくとも似たもので行われ得る。データの合計を行うことによってデータの品質が改善され、平日及び週末の両方が品質チェックをパスした場合、その速度プロファイルはその道路区域に用いられる。
【０１６１】
上記方法によって計算された速度プロファイルは、正常な週に道路区域を通る予想速度を定義しており、ナビゲーション経路を決定する際に用いる既定速度プロファイルである。したがって、これらの速度プロファイルは“正常”速度プロファイルと名付けられ、後で明らかになるように、毎週繰り返される複数の期間から合計された速度データを処理することによって決定されている。
【０１６２】
しかし、交通の振舞いは、通常の週には発生しないイベント（例えば、祝日、祭り、異常気象、交通事故など）が発生すると、正常速度プロファイルとは大幅に異なり得る。そのようなイベントによる異常な交通の振舞いの配慮するため、プロセッサ１５４はこれらのイベントが発生するものと特定された時間に用いる異常速度プロファイルを生成するために速度データを処理するように構成されている。
【０１６３】
これに関しては、図１３を参照しながら説明する。ステップ１３００では、プロセッサ２０２は、異常な交通の振舞いが発生した又は発生すると予想された過去の時刻を同定する。これはプロセッサ１５４によって、メモリ１５６に保存されたイベントカレンダ（不図示）において、交通の振舞いに影響を与えた可能性がある異常なイベントをサーチすることで行われ得る。
【０１６４】
異常な交通の振舞いが発生した又は発生すると予想された時刻が同定されると、プロセッサ１５４はステップ１３０１において区域に割り当てられる１つ以上の異常速度プロファイルを決定する。
【０１６５】
異常速度プロファイルは、異なる時間について用いられる正常速度プロファイルのうち１つを使うためのポインタであり得る。例えば、所定の時間はイギリスの銀行休業日のような祝日であり得、そのような場合の異常速度プロファイルは、日曜日の正常速度プロファイルを使うためのポインタであってもよく、（日曜日でない）祝日にも日曜日の正常速度プロファイルが用われるべきであることを特定する。
【０１６６】
プロセッサ１５４は、異常な交通の振舞いと同定され、共通する特質（例えば、祝日である、または激しい気象条件の時刻又は日である）を持つ全ての時間の速度データを抽出し、これらの速度データを合計し、図７〜１２を用いて説明した方法でこれらの速度データから異常速度プロファイルを生成してもよい。結果として、異常な交通の振舞い（祝日、異常気象など）の際における特別な一連の速度プロファイルが出来上がる。
【０１６７】
プロセッサ１５４は、既に計算された正常速度プロファイルを拡大又は縮小させて異常速度プロファイルを生成し得る（ほとんどの場合は縮小が行われる）。
【０１６８】
プロセッサ１５４はステップ１３０２で、マップデータの１つ以上の区域に各異常速度プロファイルを割り当て、どのような条件において異常速度プロファイルが使われるべきかを識別する識別子を割り当てる。これは、未来のイベントに関してはイベントカレンダから決定し得、又は過去に異常な交通の振舞いが発生した際に存在したと同定された条件のような異常な交通の振る舞いが起きる時の特定の条件を特定することにより決定し得る。
【０１６９】
作成されたマップデータはサーバ１５０によってナビゲーション装置２００に送信され、マップデータに含まれる領域における経路を決定するために使用される。
【０１７０】
図１４を参照すると、Ｉ／Ｏ装置２２２を介して経路決定の要求を受信すると、ナビゲーション装置２００のプロセッサ２０２は経路上でのに移動中の時刻における状況を同定する（１４００）。例えば、ナビゲーション装置２００は、メモリ２１４又はカードポート２２８のメモリカードに保存された、未来のイベントに関するイベントカレンダを含み、同じくメモリに保存される天気及び交通に関するリアルタイムのアップデートを受信する。経路決定の要求を受信すると、プロセッサ２０２はイベントカレンダ及び保存されたリアルタイムアップデートをサーチし、移動中の時刻の状況が、正常速度プロファイルではなく異常速度プロファイルを使う場合を示す、地図中の識別子の特定の状況に一致するかを決定する。一致する場合は、プロセッサ２０２は異常速度プロファイルを用いて経路を決定する。一致しない場合は、プロセッサ２０２は正常速度プロファイルを用いて経路を決定する。
【０１７１】
ある実施形態では、リアルタイムのアップデートは、交通事故又は異常気象が発生している／発生すると見込まれる場所を含み得る。経路決定の要求を受信すると、プロセッサ２０２は境界ボックス／影響される領域のアプローチを用いて、どの区域に正常速度プロファイルを用いてどの区域に異常速度プロファイルを用いるべきかを決定する。プロセッサ２０２は所定距離内（例えば５０又は１００ｋｍ）に事故や他のイベントなどが発生した区域を同定し、これらの区域には異常速度プロファイルを用い、これら（又は任意の影響を受ける領域）以外の区域には正常速度プロファイルを用いる。このようにすると、ナビゲーション装置は全体的でなく局部的な影響を与えるイベントに注意を払うことができる。
【０１７２】
異なる実施形態では、ナビゲーション装置２００のプロセッサ２０２は、移動時に特定の状況が同定されると、その時刻におけるその区域の正常速度プロファイルではなく、異なる正常速度プロファイルをその区域の移動速度として用い得る。このようにすることで、異常速度プロフィァイールをマップデータに含むことが必要ではなくなる。そのような機能は、特定の状況が祝日である場合適切であり得る。この状況が満たされると、プロセッサ２０２は祝日である曜日の速度プロファイルを用いるのではなく、土曜日又は日曜日の速度プロファイルを用いる。このような状況の１例は、イギリスの銀行休業日（通常月曜日になる）であり、そのような場合、プロセッサ２０２は（イギリスにおける経路を決定する場合）、月曜日の正常速度プロファイルの代わりに、日曜日の正常速度プロファイルを用いて経路を決定し得る。
【０１７３】
当業者には、ここに説明される方法を実行するために提供される装置はハードウェア、ソフトウェア、ファームウェア又はこれらの２つ以上の組み合わせであり得ることが明らかであろう。
【０１７４】
当業者には、図１を用いて説明されたようにＧＰＳから得られる位置データを参照するためにＧＰＳデータという用語を用いているが、他の位置データもここに説明された方法に似たような方法で処理できることが明らかであろう。したがって、ＧＰＳデータという用語は「位置データ」で置き換えが可能であり得る。そのような位置情報は、例えば移動電話の作動、料金所で受信したデータ、道路に埋め込まれた誘導ループシステムから得られるデータ、乗り物のナンバープレート認識システムから得られるデータ、又は他の適切なデータから抽出することができる。
【特許請求の範囲】
【請求項１】
マップに含まれる領域内のナビゲーションできる経路の区域を表すナビゲーションできる複数の区域を含むマップデータを生成するために速度データを処理する方法であり、
（ｉ）ある区域を異なる時刻の期間中に通る際に測定された移動速度を含む、少なくとも１つの区域に関する速度データを取得する工程と、
（ｉｉ）各区域の前記速度データから、前記区域を通る際の平均移動速度を含む、毎週繰り返される期間の少なくとも１つの正常速度プロファイルに関するデータを生成する工程と、
（ｉｉｉ）少なくとも１つの毎週繰り返されない特定の期間に対して、前記特定の期間中に前記区域を通る際の予想移動速度を含む異常速度プロファイルを、１つ以上の前記区域データの各々に対して少なくとも１つ生成する工程と、
（ｉｖ）前記領域を渡る行路を決定するための経路計画アルゴリズムにおいてナビゲーション装置によって使用されるために、前記マップデータの１つ以上の前記区域の各々に、対応する前記正常速度プロファイル及び前記異常速度プロファイルを割り当てる工程と、を含むことを特徴とする方法。
【請求項２】
各区域に、経路の決定においてナビゲーション装置が前記異常速度プロファイルをいつ使用するべきかを識別する識別子を割り当てる工程を含むことを特徴とする、請求項１に記載の方法。
【請求項３】
毎週繰り返される通常の交通振舞いとは異なる振舞いの期間を同定する工程と、
１つ以上の前記同定された期間において前記区域を通る際に測定された移動速度を前記速度データから同定することによって前記１つ以上の異常速度プロファイルの各々を生成する工程と、
前記同定された速度データから前記区域を通る際の平均移動速度を１つ以上決定する工程と、を含むことを特徴とする、請求項１又は２に記載の方法。
【請求項４】
毎週繰り返される通常の交通振舞いとは異なる振舞いの期間を同定する前記工程は、交通の振舞いに影響を及ぼすイベントをイベントデータベースにおいて捜査する工程を含むことを特徴とする、請求項３に記載の方法。
【請求項５】
１つ以上の前記異常速度プロファイルの各々を生成する前記工程は、前記正常速度プロファイルの平均速度を増加又は減少させることによって決定された速度を含むことを特徴とする、請求項１又は２のいずれかに記載の方法。
【請求項６】
特定の期間についてのデータを受信する工程と、
未来の特定の期間についての前記データを受信すると、前記異常速度プロファイル又はその１つを前記特定の期間に関連付ける工程と、を含むことを特徴とする、請求項１乃至５のいずれかに記載の方法。
【請求項７】
前記マップデータは、
前記正常速度プロファイルが前記ナビゲーションできる区域に関連付けられた第１マップに関するデータと、
特定の期間に用いられる、前記異常速度プロファイルが前記ナビゲーションできる区域に関連付けられた少なくとも１つの第２マップに関するデータと、を含み、
要求に応じて前記第１マップに関するデータをナビゲーション装置に送信する工程と、
前記第２マップが適用される前記特定の時間に関するマップデータが要求されると、前記第２マップの１つに関するデータを送信する工程と、
を含むことを特徴とする、請求項１乃至６のいずれかに記載の方法。
【請求項８】
機械可読な命令を記録するデータ記憶媒体であって、前記命令が前記機械によって読み込まれると請求項１乃至７のいずれかに記載の方法を前記機械に実行させることを特徴とする記憶媒体。
【請求項９】
マップに含まれる領域内のナビゲーションできる経路の区域を表すナビゲーションできる複数の区域を含むマップデータを生成するために速度データを処理する機械であって、
（ｉ）ある区域を異なる時刻の期間中に通る際に測定された移動速度を含む、少なくとも１つの区域に関する速度データを取得する工程と、
（ｉｉ）各区域の前記速度データから、前記区域を通る際の平均移動速度を含む、毎週繰り返される期間の少なくとも１つの正常速度プロファイルに関するデータを生成する工程と、
（ｉｉｉ）少なくとも１つの毎週繰り返されない特定の期間に対して、前記特定の期間中に前記区域を通る際の予想移動速度を含む異常速度プロファイルに関するデータを、１つ以上の前記区域データの各々に対して少なくとも１つ生成する工程と、
（ｉｖ）前記領域を渡る行路を決定するための経路計画アルゴリズムにおいてナビゲーション装置によって使用されるために、前記マップデータの１つ以上の前記区域の各々に、対応する前記正常速度プロファイル及び前記異常速度プロファイルを割り当てる工程と、
を実行させるように構成されたプロセッサを含むことを特徴とする、機械。
【請求項１０】
マップデータに含まれる領域内のナビゲーションできる経路の区域を表す、ナビゲーションできる区域を含む前記マップデータを含む機械可読な記憶媒体であって、
前記ナビゲーションできる区域の各々は、関連付けられた速度データを持ち、少なくとも１つの前記区域が１つの正常速度プロファイルと、１つ以上の異常速度プロファイルと、ナビゲーション装置がどのような場合に前記正常速度プロファイルではなく前記異常速度プロファイルを経路計画アルゴリズムに用いるべきかを識別する識別子と、が関連付けられていることを特徴とする記憶媒体。
【請求項１１】
マップデータを用いて、ある領域を渡る経路を計画する方法であって、前記マップデータは、前記マップデータに含まれる領域における、ナビゲーションできる経路の区域を表す複数のナビゲーションできる区域を含み、
前記ナビゲーションできる区域の少なくとも１つは、毎週繰り返される期間における正常速度プロファイルが関連付けられており、
前記正常速度プロファイルは前記毎週繰り返される期間に前記区域を通る際の予想移動速度と、前記区域を通る移動時間が前記予想移動時間と大きく異なる場合の特定された条件とを含み、
前記方法は、
（ｉ）ナビゲーションできる経路の決定の要求を受信する工程と、
（ｉｉ）移動時に前記特定された条件が満たされているかを確認する工程と、
（ｉｉｉ）前記条件が満たされている場合は１つ以上の他の速度プロファイルを用いて経路を決定し、前記条件が満たされていない場合は前記正常速度プロファイルの前記移動時に対応する前記毎週繰り返される期間の移動速度を用いて経路を決定する工程と、
を含むことを特徴とする方法。
【請求項１２】
前記他の速度プロファイルは、前記移動時に対応しない、毎週繰り得される期間における前記区域の正常速度プロファイルであることを特徴とする、請求項１１に記載の方法。
【請求項１３】
前記マップデータは、前記特定された条件の期間における、前記区域を通る移動速度を含む異常速度プロファイルを含み、
前記他の速度プロファイルは前記異常速度プロファイルであることを特徴とする、請求項１１に記載の方法。
【請求項１４】
影響される領域及び特定された条件に関するデータを取得する工程と、
前記影響される領域内にある区域に対して少なくとも１つの前記異常速度プロファイルを用い、前記影響される領域外にある区域に対しては少なくとも１つの前記正常速度プロファイルを用いる工程と、を含むことを特徴とする、請求項１３に記載の方法。
【請求項１５】
交通事故又は他のイベントの位置に関するデータを受信する工程と、
前記交通事故又は他のイベントから所定の距離内の区域を同定することによって、前記影響される領域を決定する工程と、を含むことを特徴とする、請求項１４に記載の方法。
【請求項１６】
命令を含む、機械可読な記憶媒体であって、機械によって読み込まれると前記機械に請求項１１乃至１５のいずれかの方法を実行させることを特徴とする記憶媒体。
【請求項１７】
マップデータを用いて、ある領域を渡る経路を決定するナビゲーション装置であって、
マップデータに含まれる領域における、ナビゲーションできる経路の区域を表す複数のナビゲーションできる区域を含むマップデータであって、前記ナビゲーションできる区域の少なくとも１つは、毎週繰り返される期間における正常速度プロファイルが関連付けられており、前記正常速度プロファイルは毎週繰り返される期間に前記区域を通る際の予想移動速度と、前記区域を通る移動時間が前記予想移動時間と大きく異なる場合の特定された条件とを含む、前記マップデータが保存されたメモリと、
ナビゲーションできる経路の決定の要求を受信するための入力と、
前記条件が満たされている場合は１つ以上の他の速度プロファイルを用いて経路を決定し、前記条件が満たされていない場合は前記正常速度プロファイルの前記移動時に対応する前記毎週繰り返される期間の移動速度を用いて経路を決定するように構成された経路計算機と、を含むことを特徴とするナビゲーション装置。
【請求項１】
マップに含まれる領域内のナビゲーションできる経路の区域を表すナビゲーションできる複数の区域を含むマップデータを生成するために速度データを処理する方法であり、
（ｉ）ある区域を異なる時刻の期間中に通る際に測定された移動速度を含む、少なくとも１つの区域に関する速度データを取得する工程と、
（ｉｉ）各区域の前記速度データから、前記区域を通る際の平均移動速度を含む、毎週繰り返される期間の少なくとも１つの正常速度プロファイルに関するデータを生成する工程と、
（ｉｉｉ）少なくとも１つの毎週繰り返されない特定の期間に対して、前記特定の期間中に前記区域を通る際の予想移動速度を含む異常速度プロファイルを、１つ以上の前記区域データの各々に対して少なくとも１つ生成する工程と、
（ｉｖ）前記領域を渡る行路を決定するための経路計画アルゴリズムにおいてナビゲーション装置によって使用されるために、前記マップデータの１つ以上の前記区域の各々に、対応する前記正常速度プロファイル及び前記異常速度プロファイルを割り当てる工程と、を含むことを特徴とする方法。
【請求項２】
各区域に、経路の決定においてナビゲーション装置が前記異常速度プロファイルをいつ使用するべきかを識別する識別子を割り当てる工程を含むことを特徴とする、請求項１に記載の方法。
【請求項３】
毎週繰り返される通常の交通振舞いとは異なる振舞いの期間を同定する工程と、
１つ以上の前記同定された期間において前記区域を通る際に測定された移動速度を前記速度データから同定することによって前記１つ以上の異常速度プロファイルの各々を生成する工程と、
前記同定された速度データから前記区域を通る際の平均移動速度を１つ以上決定する工程と、を含むことを特徴とする、請求項１又は２に記載の方法。
【請求項４】
毎週繰り返される通常の交通振舞いとは異なる振舞いの期間を同定する前記工程は、交通の振舞いに影響を及ぼすイベントをイベントデータベースにおいて捜査する工程を含むことを特徴とする、請求項３に記載の方法。
【請求項５】
１つ以上の前記異常速度プロファイルの各々を生成する前記工程は、前記正常速度プロファイルの平均速度を増加又は減少させることによって決定された速度を含むことを特徴とする、請求項１又は２のいずれかに記載の方法。
【請求項６】
特定の期間についてのデータを受信する工程と、
未来の特定の期間についての前記データを受信すると、前記異常速度プロファイル又はその１つを前記特定の期間に関連付ける工程と、を含むことを特徴とする、請求項１乃至５のいずれかに記載の方法。
【請求項７】
前記マップデータは、
前記正常速度プロファイルが前記ナビゲーションできる区域に関連付けられた第１マップに関するデータと、
特定の期間に用いられる、前記異常速度プロファイルが前記ナビゲーションできる区域に関連付けられた少なくとも１つの第２マップに関するデータと、を含み、
要求に応じて前記第１マップに関するデータをナビゲーション装置に送信する工程と、
前記第２マップが適用される前記特定の時間に関するマップデータが要求されると、前記第２マップの１つに関するデータを送信する工程と、
を含むことを特徴とする、請求項１乃至６のいずれかに記載の方法。
【請求項８】
機械可読な命令を記録するデータ記憶媒体であって、前記命令が前記機械によって読み込まれると請求項１乃至７のいずれかに記載の方法を前記機械に実行させることを特徴とする記憶媒体。
【請求項９】
マップに含まれる領域内のナビゲーションできる経路の区域を表すナビゲーションできる複数の区域を含むマップデータを生成するために速度データを処理する機械であって、
（ｉ）ある区域を異なる時刻の期間中に通る際に測定された移動速度を含む、少なくとも１つの区域に関する速度データを取得する工程と、
（ｉｉ）各区域の前記速度データから、前記区域を通る際の平均移動速度を含む、毎週繰り返される期間の少なくとも１つの正常速度プロファイルに関するデータを生成する工程と、
（ｉｉｉ）少なくとも１つの毎週繰り返されない特定の期間に対して、前記特定の期間中に前記区域を通る際の予想移動速度を含む異常速度プロファイルに関するデータを、１つ以上の前記区域データの各々に対して少なくとも１つ生成する工程と、
（ｉｖ）前記領域を渡る行路を決定するための経路計画アルゴリズムにおいてナビゲーション装置によって使用されるために、前記マップデータの１つ以上の前記区域の各々に、対応する前記正常速度プロファイル及び前記異常速度プロファイルを割り当てる工程と、
を実行させるように構成されたプロセッサを含むことを特徴とする、機械。
【請求項１０】
マップデータに含まれる領域内のナビゲーションできる経路の区域を表す、ナビゲーションできる区域を含む前記マップデータを含む機械可読な記憶媒体であって、
前記ナビゲーションできる区域の各々は、関連付けられた速度データを持ち、少なくとも１つの前記区域が１つの正常速度プロファイルと、１つ以上の異常速度プロファイルと、ナビゲーション装置がどのような場合に前記正常速度プロファイルではなく前記異常速度プロファイルを経路計画アルゴリズムに用いるべきかを識別する識別子と、が関連付けられていることを特徴とする記憶媒体。
【請求項１１】
マップデータを用いて、ある領域を渡る経路を計画する方法であって、前記マップデータは、前記マップデータに含まれる領域における、ナビゲーションできる経路の区域を表す複数のナビゲーションできる区域を含み、
前記ナビゲーションできる区域の少なくとも１つは、毎週繰り返される期間における正常速度プロファイルが関連付けられており、
前記正常速度プロファイルは前記毎週繰り返される期間に前記区域を通る際の予想移動速度と、前記区域を通る移動時間が前記予想移動時間と大きく異なる場合の特定された条件とを含み、
前記方法は、
（ｉ）ナビゲーションできる経路の決定の要求を受信する工程と、
（ｉｉ）移動時に前記特定された条件が満たされているかを確認する工程と、
（ｉｉｉ）前記条件が満たされている場合は１つ以上の他の速度プロファイルを用いて経路を決定し、前記条件が満たされていない場合は前記正常速度プロファイルの前記移動時に対応する前記毎週繰り返される期間の移動速度を用いて経路を決定する工程と、
を含むことを特徴とする方法。
【請求項１２】
前記他の速度プロファイルは、前記移動時に対応しない、毎週繰り得される期間における前記区域の正常速度プロファイルであることを特徴とする、請求項１１に記載の方法。
【請求項１３】
前記マップデータは、前記特定された条件の期間における、前記区域を通る移動速度を含む異常速度プロファイルを含み、
前記他の速度プロファイルは前記異常速度プロファイルであることを特徴とする、請求項１１に記載の方法。
【請求項１４】
影響される領域及び特定された条件に関するデータを取得する工程と、
前記影響される領域内にある区域に対して少なくとも１つの前記異常速度プロファイルを用い、前記影響される領域外にある区域に対しては少なくとも１つの前記正常速度プロファイルを用いる工程と、を含むことを特徴とする、請求項１３に記載の方法。
【請求項１５】
交通事故又は他のイベントの位置に関するデータを受信する工程と、
前記交通事故又は他のイベントから所定の距離内の区域を同定することによって、前記影響される領域を決定する工程と、を含むことを特徴とする、請求項１４に記載の方法。
【請求項１６】
命令を含む、機械可読な記憶媒体であって、機械によって読み込まれると前記機械に請求項１１乃至１５のいずれかの方法を実行させることを特徴とする記憶媒体。
【請求項１７】
マップデータを用いて、ある領域を渡る経路を決定するナビゲーション装置であって、
マップデータに含まれる領域における、ナビゲーションできる経路の区域を表す複数のナビゲーションできる区域を含むマップデータであって、前記ナビゲーションできる区域の少なくとも１つは、毎週繰り返される期間における正常速度プロファイルが関連付けられており、前記正常速度プロファイルは毎週繰り返される期間に前記区域を通る際の予想移動速度と、前記区域を通る移動時間が前記予想移動時間と大きく異なる場合の特定された条件とを含む、前記マップデータが保存されたメモリと、
ナビゲーションできる経路の決定の要求を受信するための入力と、
前記条件が満たされている場合は１つ以上の他の速度プロファイルを用いて経路を決定し、前記条件が満たされていない場合は前記正常速度プロファイルの前記移動時に対応する前記毎週繰り返される期間の移動速度を用いて経路を決定するように構成された経路計算機と、を含むことを特徴とするナビゲーション装置。
【図１３】
【図１４】
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１４】
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公表番号】特表２０１１−５０１１７３（Ｐ２０１１−５０１１７３Ａ）
【公表日】平成２３年１月６日（２０１１．１．６）
【国際特許分類】
【出願番号】特願２０１０−５３０４４７（Ｐ２０１０−５３０４４７）
【出願日】平成２０年１０月２２日（２００８．１０．２２）
【国際出願番号】ＰＣＴ／ＥＰ２００８／０６４３１７
【国際公開番号】ＷＯ２００９／０５３４０５
【国際公開日】平成２１年４月３０日（２００９．４．３０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
【出願人】（３０７０４３２２３）トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【Ｆターム（参考）】
【公表日】平成２３年１月６日（２０１１．１．６）
【国際特許分類】
【出願日】平成２０年１０月２２日（２００８．１０．２２）
【国際出願番号】ＰＣＴ／ＥＰ２００８／０６４３１７
【国際公開番号】ＷＯ２００９／０５３４０５
【国際公開日】平成２１年４月３０日（２００９．４．３０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
【出願人】（３０７０４３２２３）トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【Ｆターム（参考）】
[ Back to top ]