交差点の通過時間を含む地図データを作成する方法
ある期間にわたり少なくとも1台の車両の位置(606)から導出された位置データから地図データを作成するコンピュータを使用した方法であり、地図データが地図によりカバーされる地域におけるナビゲート可能な経路(607)の区分(602、604)を表す複数のナビゲート可能な区分を含み且つナビゲート可能な経路における交差点を表すナビゲート可能な区分(602、604)の間の交差点を更に含む方法であって、i. 位置データを処理するステップと、ii. 地図データの交差点の少なくとも一部に対する通過時間又は通過時間の集合を位置データの処理から計算するステップと、iii. 交差点の少なくとも一部に対して計算が行われた交差点と関連付けられた計算された通過時間又は通過時間の集合を含む更なる地図データを生成するステップとを実行するために処理回路を使用することから成る方法。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、測位データを処理する方法に関し、特に、ナビゲーション装置及び特にポータブルナビゲーション装置(PND)、これに限定されない、で使用されるように構成された地図データを生成するために測位データを処理することに関する。更に本発明は、方法を提供するための関連した装置を提供する。
【背景技術】
【0002】
TomTom International BV GO(登録商標)のようなGPSを用いたパーソナルナビゲーション装置等の電子ナビゲーション装置のための地図データは、Tele Atlas NV等の地図専門メーカから得られる。そのような装置は、ポータブルナビゲーション装置(PND)とも呼ばれる。特に、この地図データは、一般にGPSシステムからの位置データを使用する経路ガイダンスアルゴリズムにより使用されるように設計される。例えば、道路は線、すなわちベクトル(例えば、道路の始点、終点、方向であり、道路全体は、各々が始点/終点方向パラメータにより一意に規定される数百の区分から構成される)として記述される。地図は、そのような道路区分、各区分と関連付けられたデータ(制限速度;移動方向等)+地点情報(POI)+道路名+公園の境界や川の境界等の他の地理的特徴の集合であり、それらは全てベクトルに関して規定される。全ての地図の特徴(例えば、道路区分、POI等)は、一般にGPS座標系に対応するか又は関連する座標系で定義され、GPSシステムを介して判定される装置の位置を地図に示される関連道路に配置することを可能にし、目的地までの最適な経路の計画を可能にする。
【0003】
この地図データベースを構築するために、Tele Atlasは、英国の道路のOrdnance Survey等の種々の情報源からの基本的な道路情報を利用する。これは、道路を走行する車両専用の大きなチーム、並びに他の地図及び空中写真を調査する担当者を配備して、自身のデータを更新及び調査することを更に含むがそれに限定されない。このデータがTele Atlasの地図データベースの中核を構成する。この地図データベースは、地理参照データにより継続的に向上されている。これは、1年に複数回調査され、TomTomのような装置製造業者に公表される。
【0004】
そのような各道路区分は、道路区分に対する関連する速度データを有し、速度データは、車両がその区分に沿って移動可能である速度の指示を与え、例えばTele Atlasであってもよい地図データを生成する者により生成された平均速度である。速度データは、地図が処理されるPND又は他の装置において経路計画アルゴリズムにより使用される。そのような経路計画の精度は、速度データの精度に依存する。例えば、ユーザはしばしば装置の現在地と目的地との間の最速経路を生成するためにPNDにオプションを提示される。速度データが不正確である場合、PNDにより計算された経路は最速経路ではない可能性がある。
【0005】
交通量等のパラメータが道路区分の速度プロファイルに重大な影響を及ぼすことは既知であり、そのような速度プロファイルのばらつきは、2つの地点間の最速経路が同一にとどまっていない可能性があることを意味する。道路区分の速度パラメータが不正確である場合、不正確な推定到着時間(ETA)を導き且つ次善の最速経路の選択を導くことになる。
【0006】
地図データは、道路区分間の交差点に対する時間許容を更に含む。これらの時間許容は、それらの時間許容が発生する道路区分の所定のカテゴリに対して固定値である傾向がある。経路指定アルゴリズムは、経路を判定するために地図データを処理している時にこの時間許容を使用するように構成される。
【0007】
Tele AtlasはGPSデータがPNDからアップロードされ、所定の時間帯の道路区分における実際の平均速度を示す速度パラメータを提供することを目的として地図データの区分に対する速度パラメータを提供するために使用されるシステムを開発した。
【発明の概要】
【発明が解決しようとする課題】
【0008】
経路計画の精度は、速度データの精度に依存する。例えば、ユーザはしばしば装置の現在地と目的地との間の最速経路を生成するためにPNDにオプションを提示される。速度データが不正確である場合、PNDにより計算された経路は最速経路ではない可能性がある。
【課題を解決するための手段】
【0009】
本発明の第1の側面によると、
ある期間にわたり少なくとも1台の車両の位置から導出された位置データから地図データを作成するコンピュータを使用した方法であり、前記地図データが地図によりカバーされる地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分を含み且つ地図データがナビゲート可能な経路における交差点を表すナビゲート可能な区分間の交差点を更に含む方法であって:
i.位置データを処理するステップと;
ii.地図データの交差点の少なくとも一部に対する通過時間又は通過時間の集合を位置データの処理から計算するステップと;
iii.交差点の少なくともいくつかに対して、計算が行われた交差点と関連付けられた計算された通過時間又は通過時間の集合を含む更なる地図データを生成するステップと
を実行するために処理回路を使用することから成る方法が提供される。
【0010】
位置データから交差点の通過時間を判定することにより、より明確な通過時間が交差点に割り当てられる。交差点の通過時間は、道路区分の通過時間と比較してより複雑な道路網の特性である。これは、所定の道路区分の属性ではなく、複数の道路区分にわたる運転行動の特性である。そのような「コスト」は、特定の状況下では大きい。その主な一例は、優先通行権を有する渋滞した道路(例えば、ラッシュアワーの時)に入りたいか又は横断したい車両の待ち時間である。従って、通過時間の精度を向上することにより、装置は地図データを使用してより正確な経路を計画できる。
【0011】
区分によりナビゲート可能な経路を表すどんな地図に対しても、区分の間に境界線を有する必要があること、すなわちその地図を使用して計画されたどんな経路も短くない限り複数の区分を移動する必要があることが当業者には理解されるだろう。これは、それらの境界線がナビゲート可能な経路の交差点において提供される場合に便利であるが、必ずしも当てはまらない。しかし、どのようにこれらの区分が配置されても、本発明の実施形態は、区分間を通過するための通過時間又は通過時間の集合を判定するために利用されてもよい。区分間の通過時間は、通過が発生するセグメントに対して平均速度又は速度プロファイルから導出できない可能性がある。
【0012】
この方法は、位置データ内で車両の移動を識別するために位置データを解析してもよい。
【0013】
この方法は、交差点を通る経路を判定することと位置データを解析することから構成されてもよく、交差点を通る判定された経路を通過する移動を判定するために、一般に位置データ内で識別された移動を解析するように構成されてもよい。上述したように、いずれか1つの交差点を通る種々の経路は、非常に異なる通過時間を有することができる。例えば接近してくる交通を横断する左折は、交通を横断しない左折よりかなり遅い可能性が高い。
【0014】
その後、判定された経路を通過するその移動又は各移動は、その移動が交差点を通過するのにかかる時間を判定するために、すなわち通過時間を判定するために、あるいは少なくとも通過時間の推定値を提供するために解析されてもよい。
【0015】
所定の経路のうちの1つを利用したと判定された移動の時間は平均され、それによりその所定の移動に対するより正確な全体の時間を与えてもよい。
【0016】
いくつかの実施形態において、平均値はあらかじめ設定された期間内にとられてもよい。一実施形態において、移動は移動にかかる時間に従って平均される。移動はあらかじめ設定された長さの期間にわたり平均されてもよい。交通の流れが1日の推移のうちでいちじるしく越えることができるため、あらかじめ設定された期間を使用することにより精度が向上されることが理解されるだろう。
【0017】
この方法のいくつかの実施形態は、平均値の品質を判定するために平均値を解析するように構成されてもよい。品質が所定の基準を満たさないと判定された場合、平均値は変更されてもよい。
【0018】
いくつかの実施形態において、あらかじめ設定された期間の長さが増加され、それによりいずれか1つの期間内の移動の数を増加してもよい。
【0019】
この方法は、交差点を通る移動を、交差点前のゾーン、交差点内のゾーン及び交差点後のゾーンのうちの少なくとも1つに分析するように更に構成されてもよい。この方法は、交差点前のゾーン、交差点内のゾーン及び交差点後のゾーンのうちの1つ以上を交差点と関連した通過時間として利用することを更に含んでもよい。
【0020】
この方法は交差点の周囲の道路区分に四角い境界(バウンディングボックス)を適用してもよい。そのような方法は、この位置データが交差点を通る進路の一部として考えられるべきであることを判定するのに便利である。
【0021】
バウンディングボックスは、交差点の1つの地点からの所定の距離に関して判定されてもよい。例えばバウンディングボックスは、交差点から約150mであると判定されてもよい。約50m、75m、100m、125m、175m、200mのうちのいずれかの距離等の他の距離が適切であってもよいことは、当業者には理解されるだろう。
【0022】
あるいは又は更に、バウンディングボックスは、交差点として判定された地点からの通過時間を使って判定されてもよい。
【0023】
交差点は種類に従って分類されてもよく、同一の又は少なくとも同様のカテゴリ内の交差点を通過するのにかかる移動時間は平均されてもよい。そのような方法は、平均値を改善する目的で先に判定された平均値に適用されてもよい。あるいは又は更に、交差点の種類は平均値を判定するために使用されてもよい。
【0024】
この方法は、交差点の通過時間が未知の変数である式の集合を判定するために位置データから導出された移動を使用するように構成されてもよい。
【0025】
更にこの方法は、少なくともいくつかの交差点の通過時間を判定するために式の集合を処理するように構成されてもよい。いくつかの実施形態において、方法は、交差点のカテゴリ毎に通過時間を判定して式の集合の誤差を最小限にすることにより通過時間を判定する。
【0026】
本発明の第2の側面によると、地図によりカバーされる地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分、並びに地図によりカバーされるナビゲート可能な経路の交差点を表す交差点を含む地図データを作成するように構成された装置であって、ある期間にわたり少なくとも1台の車両の位置から導出された位置データを処理するように構成された処理回路を備え、処理回路は:
i.位置データを処理し;
ii.地図データの交差点の少なくとも一部に対する通過時間又は通過時間の集合を位置データの処理から計算し;
iii.交差点の少なくともいくつかに対して計算が行われた交差点と関連付けられた計算による通過時間又は通過時間の集合を含む更なる地図データを生成する;
ようにプログラムされた装置が提供される。
【0027】
本発明の第3の側面によると、地図によりカバーされた地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分、並びに地図によりカバーされたナビゲート可能な区分間の交差点を表す交差点を含む地図データであって、交差点の少なくともいくつかは本発明の第1の側面の方法を使用して位置データを平均することにより導出された関連する通過時間を有する地図データが提供される。
【0028】
本発明の第4の側面によると、コンピュータにより読み出された時に本発明の第1の側面の方法をコンピュータに実行させる命令を含むコンピュータ読み取り可能な記録媒体が提供される。
【0029】
本発明の第5の側面によると、コンピュータにより読み出された時にそのコンピュータを本発明の第2の側面の装置として機能させる命令を含むコンピュータ読み取り可能な記録媒体が提供される。
【0030】
本発明の第6の側面によると、本発明の第3の側面の地図データを含む命令を含むコンピュータ読み取り可能な記録媒体が提供される。
【0031】
本発明の第7の側面によると、ある期間にわたり少なくとも1台の車両の位置から導出された位置データから地図データを作成するコンピュータを使用した方法であり、地図データが地図によりカバーされた地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分を含み且つナビゲート可能な経路における交差点を表すナビゲート可能な区分間の交差点を更に含む方法であって:
i.位置データを処理するステップと;
ii.地図データの交差点の少なくとも一部に対する通過時間又は通過時間の集合を位置データの処理から計算するステップと;
iii.通過時間から通過時間プロファイルを生成するために所定の期間内の計算された通過時間をクラスタリングするステップと;
iv. 交差点で判定された通過時間プロファイルを有する交差点の通過時間プロファイルを含む更なる地図データを生成するステップ;
とを実行するために処理回路を使用することから成る方法が提供される。
【0032】
本発明の第8の側面によると、ある期間にわたり少なくとも1台の車両の位置から導出された位置データから地図データを作成するコンピュータを使用した方法であり、地図データが地図によりカバーされた地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分を含み且つナビゲート可能な経路における交差点を表すナビゲート可能な区分間の交差点を更に含む方法であって:
i.位置データを処理するステップと;
ii.位置データの処理から交差点の通過時間が未知の変数である式の集合を生成するステップと;
iii.地図データの交差点の少なくとも一部の通過時間を式の集合から計算するステップと;
iv.交差点で計算された通過時間を有する交差点の通過時間を含む更なる地図データを生成するステップ;
とを実行するために処理回路を使用することから成る方法が提供される。
【0033】
本発明の上記側面のいずれかにおいて、コンピュータ読み取り可能な記録媒体は、フロッピディスク、CD ROM、DVD ROM/RAM(−R/−RW及び+R/+RWを含む)、ハードドライブ、固体メモリ(USBメモリキー、SDカード、Memorystick(登録商標)又はコンパクトフラッシュカード(登録商標)等を含む)、テープ、他のあらゆる形態の光磁気記憶装置、送信信号(インターネットダウンロード、FTP転送等を含む)、ワイヤ又は他のあらゆる適切な媒体のうちのいずれを含んでもよい。
【0034】
更に、本発明のいずれか1つの側面に関連して説明される特徴は、本発明の他の側面に対して適切に準用されることが当業者には理解されるだろう。
【図面の簡単な説明】
【0035】
本発明の教示の種々の側面及びそれらの教示を具体化する構成について、添付の図面を参照しながら図の例によって以下に説明する。
【図1】全地球測位システム(GPS)を示す概略図
【図2】ナビゲーション装置を提供するように構成された電子構成要素を示す概略図
【図3】ナビゲーション装置が無線通信チャネルを介して情報を受信する方法を示す概略図
【図4A】ナビゲーション装置の例を示す透視図
【図4B】ナビゲーション装置の例を示す透視図
【図5】ナビゲーション装置により採用されたソフトウェアの概略表現を示す図
【図6】2つの道路区分の間の交差点を概略的に示す図
【図7】第1の交差点の例を示す図
【図8】第1の交差点の例より複雑な第2の交差点の例を示す図
【図9】種々のノード間の経路の計画を示す図
【図10】本発明の実施形態の概略を示すフローチャート
【図11】本発明の実施形態の概略を示すフローチャート
【発明を実施するための形態】
【0036】
本発明の実施形態について、特にPND(ポータブルナビゲーション装置)を参照して説明する。しかし、本発明の教示はPNDに限定されず、経路計画及びナビゲーション機能性を提供するためにナビゲーションソフトウェアを実行するように構成されるどんな種類の処理装置にも例外なく適用可能である。従って、本出願において、ナビゲーション装置は、PND、車両に内蔵されたナビゲーション装置、地図サーバ(インターネットを介して経路及びナビゲーション機能性を提供する等)、あるいは実際には経路計画及びナビゲーションソフトウェアを実行する計算リソース(デスクトップ又はポータブルパーソナルコンピュータ(PC)、移動電話、あるいはポータブルデジタルアシスタント(PDA))として具体化されているか否かにかかわらず、どんな種類の経路計画及びナビゲーション装置も含むことを意図する(それに限定されない)。
【0037】
本発明の教示は、ユーザが1つの地点から別の地点までのナビゲーション方法に関する命令を要求していないが単に所定の場所のビューを提供してほしい状況においても有用であることが以下から明らかとなるだろう。そのような状況において、ユーザが選択した「目的地」の場所は、ユーザがナビゲーションを開始したい出発地に対応する必要はないため、本明細書で「目的地」の場所又は実際には「目的地」のビューを参照することは、経路の生成が不可欠であること、「目的地」まで移動する必要があること又は実際には目的地の存在が対応する出発地の指示を必要とすることを意味すると解釈されるべきではない。
【0038】
上記条件を考慮すると、図1は、ナビゲーション装置により使用可能な全地球測位システム(GPS)の一例を示す図である。そのようなシステムは既知であり、種々の目的で使用される。一般にGPSは、連続した位置、速度、時間及びいくつかの例においては無数のユーザに対する方向情報を判定できる衛星無線を使用したナビゲーションシステムである。以前はNAVSTARとして既知であったGPSは、極めて正確な軌道で地球を周回する複数の衛星からなる。これらの正確な軌道に基づいて、GPS衛星は自身の場所をいかなる数の受信ユニットにも中継できる。しかし、GLOSNASS、欧州のGalileo測位システム、COMPASS測位システム又はIRNSS(Indian Regional Navigation Satellite System)等の全地球測位システムが使用可能であることが理解されるだろう。
【0039】
GPSデータを受信する能力を特別に備える装置がGPS衛星信号に対する無線周波数の走査を開始すると、GPSシステムは実現される。GPS衛星から無線信号を受信すると、装置は、複数の異なる従来の方法のうちの1つを用いて、その衛星の正確な場所を判定する。殆どの例において、装置は、少なくとも3つの異なる衛星信号を取得するまで信号の走査を継続する(尚、位置は、通常は2つの信号のみでは判定されないが、他の三角測量技術を使用して2つの信号から判定することもできる)。幾何学的三角測量を実現する場合、受信機は、3つの既知の位置を利用して、衛星に対する自身の2次元位置を判定する。これは、周知の方法で行われる。更に、第4の衛星信号を取得することにより、受信装置は、周知の方法で同一の幾何学計算によりその3次元位置を計算できる。位置及び速度データは、無数のユーザにより連続的にリアルタイムで更新可能である。
【0040】
図1に示すように、GPSシステム全体を参照番号100で示す。複数の衛星120は、地球124の周囲の軌道上にある。各衛星120の軌道は、他の衛星120の軌道と必ずしも同期せず、実際には非同期であることが多い。本願の一実施形態のナビゲーション装置において利用可能なGPS受信機140は、種々の衛星120からスペクトル拡散GPS衛星信号160を受信するように示される。
【0041】
各衛星120から連続的に送信されるスペクトル拡散信号160は、極めて正確な原子時計を用いて達成される非常に正確な周波数標準を利用する。各衛星120は、そのデータ信号送信160の一部として、その特定の衛星120を示すデータストリームを送信する。一般に、GPS受信機140が三角測量によりその2次元位置を計算するために、GPS受信機140は少なくとも3つの衛星120からスペクトル拡散GPS衛星信号160を取得することが当業者には理解される。更なる信号を取得すると、全部で4つの衛星120から信号160を取得する結果となり、これによってGPS受信機140は、その3次元位置を周知の方法で計算できる。
【0042】
図2は、本願の一実施形態のナビゲーション装置200の電子構成要素の一例を、ブロック構成要素の形式で示す図である。尚、ナビゲーション装置200のブロック図は、ナビゲーション装置の全ての構成要素を含むものではなく、構成要素の多くの例を表すにすぎない。
【0043】
ナビゲーション装置200は、筐体(不図示)内に位置付けられる。筐体は、入力装置220及び表示画面240に接続されるプロセッサ210を含む。入力装置220は、キーボード装置、音声入力装置、タッチパネル、及び情報を入力するために利用される他の任意の周知の入力装置のうちの少なくとも1つを含むことができ、表示画面240は、例えばLCDディスプレイ等の任意の種類の表示画面を含むことができる。好適な実施形態において、入力装置220及び表示画面240は、タッチパッド又はタッチスクリーン入力を含む一体型入力表示装置に一体化され、その場合、ユーザは、複数の表示選択肢のうちの1つを選択するか又は複数の仮想ボタンのうちの1つを操作するために、表示画面240の一部分に接触するだけでよい。
【0044】
ナビゲーション装置は、例えば可聴出力装置(例えば、スピーカ)である出力装置260を含んでもよい。出力装置260がナビゲーション装置200のユーザに対して可聴情報を生成できるため、入力装置240は入力音声コマンドを受信するマイク及びソフトウェアを含むことができることが同等に理解されるべきである。
【0045】
ナビゲーション装置200において、プロセッサ210は、接続225を介して入力装置220に動作可能に接続され且つ入力装置220から入力情報を受信するように設定され、情報を出力するために出力接続245を介して表示画面240及び出力装置260のうち少なくとも一方に動作可能に接続される。更にプロセッサ210は、接続235を介してメモリリソース230に動作可能に結合され、接続275を介して入出力(I/O)ポート270に対して情報を送受信するように更に構成され、I/Oポート270は、ナビゲーション装置200の外部のI/O装置280に接続可能である。例えばメモリリソース230は、ランダムアクセスメモリ(RAM)等の揮発性メモリ及び例えばフラッシュメモリ等のデジタルメモリである不揮発性メモリを含む。
【0046】
プロセッサ210は、取外し可能なメモリカード(一般にカードと呼ばれる)が装置200に追加される際に使用されるポート234と接続236を介して通信してもよい。説明される実施形態において、ポートはSD(セキュアデジタル)カードが追加されることを可能にするように構成される。他の実施形態において、ポートは、他の形態のメモリが接続されるのを可能にしてもよい(コンパクトフラッシュ(CF)カード(登録商標)、Memory Stick(登録商標)、xDメモリカード、USB(Universal Serial Bus)フラッシュドライブ、MMC(マルチメディア)カード又はSmartMediaカード(登録商標)又はマイクロドライブ等)。
【0047】
外部I/O装置280は、例えばイヤホン等の外部リスニングデバイスを含んでもよいがこれに限定されない。I/O装置280への接続は、例えば、イヤホン又はヘッドホンへの接続及び移動電話への接続の少なくともいずれか一つのための例えばハンズフリー動作及び音声起動動作のいずれか一つを行うカーステレオユニット等のあらゆる他の外部装置への有線又は無線接続であってもよい。ここで、例えばナビゲーション装置200とインターネット又は他のネットワークとの間のデータ接続を確立するため、あるいは例えばインターネット又は他の何らかのネットワークを介してサーバとの接続を確立するための少なくともいずれか一つの接続に移動電話接続が使用されてもよい。
【0048】
図2は、接続255を介するプロセッサ210とアンテナ/受信機250との間の動作可能な接続を更に示す。この場合、アンテナ/受信機250は、例えばGPSアンテナ/受信機であってもよい。参照番号250で示されるアンテナ及び受信機は、図示のために概略的に組み合わされるが、アンテナ及び受信機は、別個に位置する構成要素であってもよく、アンテナは、例えばGPSパッチアンテナ又はヘリカルアンテナであってもよいことが理解されるだろう。
【0049】
更に、図2に示す電子構成要素が従来の方法で電源(不図示)により電力を供給されることが当業者には理解されるだろう。当業者により理解されるように、図2に示す構成要素の構成と異なるものが本願の範囲内で考えられる。例えば、図2に示す構成要素は、有線接続と無線接続との少なくとも一方を介して互いに通信状態にあってもよい。従って、本願のナビゲーション装置200の範囲は、ポータブル又はハンドヘルドナビゲーション装置200を含む。
【0050】
更に、図2のポータブル又はハンドヘルドナビゲーション装置200は、例えば自転車、モーターバイクや自動車又は船舶等の乗物に周知の方法で接続されるか又は「ドッキング」される。その場合、そのようなナビゲーション装置200は、ポータブル又はハンドヘルドナビゲーションとして使用するために、ドッキング場所から取り外し可能である。
【0051】
次に図3を参照すると、ナビゲーション装置200は、デジタル接続(例えば、既知のBluetooth技術を介するデジタル接続等)を確立する移動装置(不図示)(移動電話、PDA及び/又は移動電話技術を有するあらゆる装置等)を介してサーバ302との「モバイル」又は電気通信ネットワーク接続を確立してもよい。その後、移動装置は、そのネットワークサービスプロバイダを介してサーバ302とのネットワーク接続(例えば、インターネットを介する)を確立できる。従って、「モバイル」ネットワーク接続は、情報に対する「リアルタイム」又は少なくとも非常に「最新」のゲートウェイを提供するためにナビゲーション装置200(単独で且つ/又は車両に搭載されて移動するため移動装置であってもよく且つ多くの場合は移動装置である)とサーバ302との間に確立される。
【0052】
移動装置(サービスプロバイダを介する)とサーバ302等の別の装置との間のネットワーク接続は、例えばインターネット(ワールドワイドウェブ等)を使用して既知の方法で確立される。これは、例えばTCP/IPレイヤプロトコルを使用することを含むことができる。移動装置は、CDMA、GSM、WAN等のいかなる数の通信規格も利用できる。
【0053】
従って、例えばデータ接続を達成するために、移動電話又はナビゲーション装置200内の移動電話技術を介するインターネット接続が利用されてもよい。この接続のために、サーバ302とナビゲーション装置200との間のインターネット接続が確立される。これは、例えば移動電話又は他の移動装置及びGPRS(汎用パケット無線サービス)接続(GPRS接続はテレコムオペレータにより提供された移動装置に対する高速データ接続であり、GPRSはインターネットに接続するための方法である)を介して行われる。
【0054】
更に、ナビゲーション装置200は、移動装置とのデータ接続を完成し、例えば既存のBluetooth技術を介して周知の方法でインターネット及びサーバ302とのデータ接続を最終的に完成する。この場合、例えばデータプロトコルは、GSM規格に対するデータプロトコル規格であるGSRM等の任意の数の規格を利用できる。
【0055】
ナビゲーション装置200は、ナビゲーション装置200自身の中に、自身の移動電話技術を含んでもよい(例えばアンテナを含み、またはナビゲーション装置200の内部アンテナが選択されてもよい)。ナビゲーション装置200内の移動電話技術は、上述のような内部構成要素を含むことができ、挿入可能なカード(加入者識別モジュールやSIMカード)を含むこともでき、例えば必要な移動電話技術かアンテナの少なくとも一方を備える。そのため、ナビゲーション装置200内の移動電話技術は、任意の移動装置と同様の方法で、例えばインターネット410を介して、ナビゲーション装置200とサーバ302との間にネットワーク接続を同様に確立できる。
【0056】
GRPS電話設定の場合、移動電話の機種、製造業者等のたえず変わる範囲に関して正しく動作するために、Bluetooth対応のナビゲーション装置が使用されてもよく、機種や製造業者の専用設定は、例えばナビゲーション装置200に格納されてもよい。データは情報が更新されるよう格納される。
【0057】
図3は、多くの異なる構成で実施される汎用通信チャネル318を介してサーバ302と通信するナビゲーション装置200を示す図である。通信チャネル318を介する接続が本発明のサーバ302とナビゲーション装置200との間に確立される場合、本願のサーバ302及びナビゲーション装置200は通信可能である(尚、そのような接続は、移動装置を介するデータ接続やインターネットを介するパーソナルコンピュータを介する直接接続等である)。
【0058】
サーバ302は、図示しない他の構成要素に加えて、メモリ306に動作可能に接続され且つ有線又は無線接続314を介して大容量データ記憶装置312に動作可能に更に接続されるプロセッサ304を含む。更に、プロセッサ304は、通信チャネル318を介してナビゲーション装置200と情報の送受信を行うために、送信機308及び受信機310に動作可能に接続される。送受信される信号は、データ信号、通信信号又は他の伝搬信号の少なくともいずれか一つを含んでもよい。送信機308及び受信機310は、ナビゲーション装置200の通信設計において使用される通信条件及び通信技術に従って選択又は設計されてもよい。さらに送信機308及び受信機310の機能は、単一の信号送受信機に組み合わされてもよい。
【0059】
サーバ302は、大容量記憶装置312に更に接続される(又は含む)。なお、大容量記憶装置312は、通信リンク314を介してサーバ302に結合されてもよい。大容量記憶装置312は、ナビゲーションデータ及び地図情報のストアを含む。また、大容量記憶装置312は、サーバ302とは別個の装置であってもよく、サーバ302に組み込まれてもよい。
【0060】
ナビゲーション装置200は、通信チャネル318を介してサーバ302と通信するように構成され、図2に関して上述したように、プロセッサ、メモリ等を含み、更に、通信チャネル318を介して信号及びデータの少なくとも一方を送出する送信機320及び受信する受信機322を含む。尚、これらの装置は、サーバ302以外の装置と通信するためにも使用される。更に、送信機320及び受信機322は、ナビゲーション装置200の通信設計において使用される通信条件及び通信技術に従って選択又は設計され、送信機320及び受信機322の機能は、単一の信号送受信機に組み合わされてもよい。
【0061】
サーバメモリ306に格納されるソフトウェアは、プロセッサ304に命令を提供し、サーバ302がナビゲーション装置200にサービスを提供できるようにする。サーバ302により提供される1つのサービスは、ナビゲーション装置200からの要求の処理及び大容量データ記憶装置312からナビゲーション装置200へのナビゲーションデータの送信を含む。サーバ302により提供される別のサービスは、所望のアプリケーションに対する種々のアルゴリズムを使用したナビゲーションデータの処理及びナビゲーション装置200へのこれらの計算の結果の送出を含む。
【0062】
一般に、通信チャネル318は、ナビゲーション装置200とサーバ302とを接続する伝搬媒体又は進路を表す。サーバ302及びナビゲーション装置200の双方は、通信チャネルを介してデータを送信する送信機及び通信チャネルを介して送信されたデータを受信する受信機を含む。
【0063】
通信チャネル318は、特定の通信技術に限定されない。更に、通信チャネル318は、単一の通信技術に限定されない。すなわち、チャネル318は、種々の技術を使用する複数の通信リンクを含んでもよい。例えば、通信チャネル318は、電気通信、光通信、及び電磁通信等のうちの少なくとも1つのためのパスを提供するように構成されることができる。そのため、通信チャネル318は、電気回路、ワイヤ及び同軸ケーブル等の電気導体、光ファイバケーブル、コンバータ、無線周波数(rf)波、大気、空間等のうちの1つ又はそれらの組み合わせを含むが、それらに限定されない。更に、少なくとも1つの様々な実施形態に従えば、通信チャネル318は例えば、ルータ、リピータ、バッファ、送信機及び受信機等の中間装置を含むことができる。
【0064】
図示の構成では、通信チャネル318は、電話及びコンピュータネットワークを含む。更に、通信チャネル318は、無線周波数、マイクロ波周波数、赤外線通信等の無線通信に適応できてもよい。更に、通信チャネル318は衛星通信に適応できる。
【0065】
通信チャネル318を介して送信される通信信号は、所定の通信技術に必要とされるか又は望まれる信号を含むが、それらに限定されない。例えば、信号は、時分割多元接続(TDMA)、周波数分割多元接続(FDMA)、符号分割多元接続(CDMA)、グローバル・システム・フォー・モバイル・コミュニケーションズ(Global System for Mobile Communications)(GSM)等のセルラ通信技術において使用されるように構成されてもよい。デジタル信号及びアナログ信号の双方が通信チャネル318を介して送信できる。これらの信号は、通信技術にとって望ましい変調信号、暗号化信号、及び圧縮信号のうちの少なくとも1つであってもよい。
【0066】
サーバ302は、無線チャネルを介してナビゲーション装置200によりアクセス可能なリモートサーバを含む。サーバ302は、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)、仮想プライベートネットワーク(VPN)等に位置するネットワークサーバを含んでもよい。
サーバ302は、デスクトップ又はラップトップコンピュータ等のパーソナルコンピュータを含んでもよく、通信チャネル318は、パーソナルコンピュータとナビゲーション装置200との間に接続されるケーブルであってもよい。あるいは、パーソナルコンピュータは、ナビゲーション装置200とサーバ302との間に接続されて、サーバ302とナビゲーション装置200との間にインターネット接続を確立してもよい。あるいは、インターネットを介してナビゲーション装置200をサーバ302に接続するために、移動電話又は他のハンドヘルド装置がインターネットへの無線接続を確立してもよい。
【0067】
ナビゲーション装置200は、情報ダウンロードを介してサーバ302から情報を与えられてもよい。情報は、周期的に自動更新されたり、ユーザがナビゲーション装置200をサーバ302に接続する場合に更新されたり、例えば無線移動接続装置及びTCP/IP接続を介してサーバ302とナビゲーション装置200との間に接続がより継続して又は頻繁に確立される場合に更に動的に更新されてもよい。多くの動的計算のために、サーバ302内のプロセッサ304が大量の処理要求を処理するために使用されてもよい。しかし、ナビゲーション装置200のプロセッサ210も同様に、多くの場合においてはサーバ302への接続に関係なく、多くの処理及び計算を処理できる。
【0068】
更にプロセッサ210は、装置200の所在の記録(すなわち、GPSデータ及びタイムスタンプ)をサーバ302に時々アップロードするように構成される。ナビゲーション装置200が装置200をサーバ302に接続する永続的な又は少なくとも一般的に存在する通信チャネル318を有するいくつかの実施形態において、データのアップロードは定期的に、例えば24時間に1回行われる。当業者には他の周期が可能であり、実質的には15分、30分、1時間毎、2時間毎、5時間毎、12時間毎、2日毎、週毎又はそれらの時間の間のあらゆる時間のうちのいずれの周期であってもよいことが理解されるだろう。実際には、そのような実施形態において、プロセッサ210は、ほぼリアルタイムに所在の記録をアップロードするように構成されてもよい。これは、データが実際には送信の間の比較的に短い周期で時々送信されることを必然的に意味してよく、より正確には擬似リアルタイムであると考えられる。そのような擬似リアルタイムの実施形態において、ナビゲーション装置は、メモリ230又はポート234に挿入されたカードの少なくともいずれか一つにGPS座標(GPS fixes)をバッファリングし且つ所定の数が格納された時にそれらを送信するように構成されてもよい。この所定の数は、20、36、100、200又はそれらの間のどのような数であってもよい。所定の数は、メモリ230やポート234のカードのサイズにより部分的に決定されることが当業者には理解されるだろう。
【0069】
他の実施形態において、通常の時は通信チャネル318を有さないプロセッサ210は、通信チャネル318が作成される時に記録をサーバ302にアップロードするように構成されてもよい。例えばこれは、ナビゲーション装置200がユーザのコンピュータに接続される時であってもよい。ここでも、そのような実施形態において、ナビゲーション装置は、メモリ230内又はポート234に挿入されたカードにGPS座標をバッファリングするように構成されてもよい。メモリ230又はポート234に挿入されたカードがGPS座標決定で一杯になった場合、ナビゲーション装置は、最も古いGPS座標を削除するように構成されてもよいため、先入れ先出し(FIFO)バッファと考えられてもよい。
【0070】
説明される実施形態において、所在の記録は、各々が24時間以内のナビゲーション装置200の動きを表す1つ以上のトレースを含む。24時間の各期間はカレンダーの日付と一致するように構成されるが、他の実施形態においては一致する必要はない。
【0071】
一般に、ナビゲーション装置200のユーザは、装置の所在の記録がサーバ302にアップロードされることに対して同意する。同意されない場合、記録はサーバ302にアップロードされない。ナビゲーション装置自体及びナビゲーション装置が接続されるコンピュータの少なくともいずれか一方は、所在の記録のそのような使用に対する同意をユーザに求めるように構成されてもよい。
【0072】
サーバ302は、装置の所在の記録を受信し且つ処理するために大容量データ記憶装置312内にそのレコードを格納するように構成される。従って、時間の経過と共に、大容量データ記憶装置312はデータをアップロードした複数のナビゲーション装置200の所在の記録を蓄積する。
【0073】
大容量データ記憶装置312は地図データを更に含む。そのような地図データは、道路区分の場所、地点情報及び一般に地図で見つけられる他のそのような情報に関する情報を提供する。
【0074】
第1の処理として、サーバ302は、地図データと受信された所在の記録の中に含まれたGPS座標との間のマップマッチング機能を実行するように構成される。そのようなマップマッチングは、いわゆるリアルタイムに、すなわち所在の記録が受信されると実行されてもよく、あるいは所在の記録が後で大容量データ記憶装置312から再度呼び出されて実行されてもよい。
【0075】
マップマッチングの精度を向上するために、所在の記録の前処理は以下のように実行される。各GPSトレース(すなわち、24時間のGPSデータ)は、ナビゲーション装置200の1つの行程を表す1つ以上の移動に分割され、後の処理のために格納される。
【0076】
各移動内で、ナビゲーション装置から受信された精度レポートが十分に高くないGPS座標は廃棄される。従って、いくつかの実施形態において、GPS座標に関連して3つ未満の衛星102からの信号がナビゲーション装置200により受信されていたことを精度レポート示す場合、座標は廃棄されてもよい。更に、座標と座標の間の報告時間が閾値を上回る移動はクリップされる。この前処理段階を通過した各移動は、マップマッチングされるために渡される。
【0077】
図2に示す様に、ナビゲーション装置200はプロセッサ210、入力装置220、表示画面240を含む。入力装置220及び表示画面240は、例えばタッチパネルスクリーンを介して情報(直接入力、メニュー選択など)を入力すること及び情報を表示することとの両方を可能にするために、一体型入力表示装置に統合される。このようなスクリーンは、当業者には周知であるように、例えばタッチ入力LCDスクリーンであってもよい。更に、ナビゲーション装置200は、例えばオーディオ入力/出力装置などの、更なる任意の入力装置220と更なる任意の出力装置240との少なくとも一方を有しても良い。
【0078】
図4A及び図4Bは、ナビゲーション装置200のを示している。図4Aに示すように、ナビゲーション装置200は、一体型入力表示装置290(例えばタッチパネル画面)と図2の他の構成要素(内蔵GPS受信機250、マイクロプロセッサ210、電源、メモリシステム220などを含むがこれに限定されない)を含むユニットであっても良い。
【0079】
ナビゲーション装置200は、アーム292上に備え付けられても良い。このアーム292は、大きな吸着カップ294を用いて、車両のダッシュボード/窓/等に固定されても良い。このアーム292は、ナビゲーション装置200がドッキング可能なドッキングステーションの一例である。
【0080】
図4Bに示すように、ナビゲーション装置200は、例えば、アーム292に対してナビゲーション装置292をスナップ接続することで、ドッキングステーションのアーム292にドッキング若しくは接続することができる。図4Bにおける矢印で示すように、ナビゲーション装置200は、アーム292上で回転可能である。ナビゲーション装置200とドッキングステーションとの間の接続を解除するためには、例えば、ナビゲーション装置200上のボタンを押下すればよい。ナビゲーション装置をドッキングステーションに接続したり外したりするための他の等価で適した構成は当業者に知られている。
【0081】
次に添付の図面の図5を参照すると、メモリリソース230は、機能性ハードウェア構成要素460による実行のためにメモリリソース230からオペレーティングシステム470をロードするため、プロセッサ210により実行されるブートローダプログラム(不図示)を格納し、アプリケーションソフトウェア480が実行可能である環境を提供する。オペレーティングシステム470は、機能性ハードウェア構成要素460を制御し、アプリケーションソフトウェア480と機能性ハードウェア構成要素460との間に常駐する。アプリケーションソフトウェア480は、ナビゲーション装置200の中核機能、例えば地図閲覧、経路計画、ナビゲーション機能及びその他関連する機能などをサポートするGUIを含む動作環境を提供する。
【0082】
使用する際、PND(Portable Navigation Device)200は、地図データによりカバーされる地域内のナビゲート可能な経路を表す地図データをメモリ230又は他の場所に含む。そのようなナビゲート可能な経路600の一例を図6に示す。説明する例において、図6は第2の道路604を介して道路602を地点TCに接続するいわゆる「T字路」と共に地点TAからTBに伸びる道路602を示す。
【0083】
PND200が有用なのは、地図データによりカバーされる地域において使用されるときである。PND200は、その地域内を移動すると、上述したようにGPSシステムから自身の位置を周期的に判定し、その位置を記録する。これをドット606により図6に示す。システム内には元々不正確なところがあり、PND200は、自身の位置がドット606aで例示されるように道路区分602、604外にあることを判定できる。これは、後述するように後の処理で考慮され、当業者には完全に理解されるだろう。
【0084】
図6に示す経路において、PND200は、地点TAから地点TBに向けて移動607をとり、地点TCに向けて道路604に入るためにT字路で左折する。左折するために、移動しているPND200を搭載する車両は灰色のボックスで表されるゾーン608で減速する。このゾーン608は、減速(又は交差点前)ゾーン又は操作前の進路として考えられてもよい。車両は左折し、次にゾーン610(灰色のボックスにより表される)の間で加速する。従って、ゾーン610は、加速(又は交差点後)ゾーン又は操作後の進路として考えられてもよい。
【0085】
従って、図6に示す移動において、PND200が置かれる車両は、道路区分に沿って移動し、曲がり、第2の道路区分に沿って移動する。
【0086】
いくつかの実施形態において、道路区分(線形空間範囲を有する)毎に、区間の平均速度値として提供されてもよいその区分の速度プロファイルと称されるデータが地図データ内に保持される。他の実施形態において、速度プロファイルは、道路区分の長さを考慮して当該道路区分の平均通過時間と等価にモデル化されてもよい。分岐点/交差点/横断歩道が道路網のネットワークモデルにおいて空間範囲を有さないか又はより不明瞭で不自然にみえる空間範囲を有するとすると、交差点操作プロファイルは、平均速度に関して容易に表されず、通過時間又は通過時間の集合により容易に表される。交差点の通過時間を、減速、待機及び加速等をした時に「失われた」ある旅程に沿う道路区分通過時間の合計を補完する、通過時間オフセットとして表せてもよい。
【0087】
通過時間の集合は、通過時間プロファイルとして考えられてもよい。そのような通過時間プロファイルは、所定の間隔で通過時間を提供してもよい。例えば、通過時間プロファイルは1時間間隔で通過時間を提供してもよい。
【0088】
操作に関連した通過時間コストは、車両が交差点を走る際に沿う、一部又は全ての軌道、あるいは重要な軌道の部分集合と関連付けられてもよい。
【0089】
関連する軌道の一例は以下に検討される。図6に示す交差点は比較的に単純である。より複雑な交差点は図7に示され、一般に十字路と呼ばれる。方向転換の制限が考慮されるかどうか、そして許可される運転操作のみが処理されるかどうかは実行時の選択肢である。
【0090】
道路区分A、B、C及びD(A←→Cが優先権を有する)を含む4方向の交差点(すなわち、十字路)の場合、軌道B→C、B→D、B→A、D→A、D→B、D→Cは、通過時間プロファイルの最も明らかな候補である。
【0091】
更に、更なる候補(この例においては右側通行と仮定する)A→B及びC→Dが存在してもよく、左折に追加の時間がかかる可能性があるからである。例えば、交通渋滞中にはそのような操作に更に30秒を要する可能性があると考えられる。
【0092】
そのような情報は、減速ゾーン(例えば、A)に拠る方向転換前の、そして加速ゾーン(例えば、B)に拠る方向転換後の双方2つの道路区分の特性である。方向転換をするのにかかる時間はA、B両方の道路区分の特性であるため、「通過時間コスト」属性をAかBに付けることは、適切に方向転換をモデル化しない。従って、時間は有向対A→Bの属性であることが都合がよい。すなわち、交差点の通過時間は、交差点を通過する経路(及び交通量等の他の要因)に依存する。
【0093】
また、例えば中央分離帯、安全地帯又は反対の運転方向との間の他の種類の分離帯を仮定すると、A→A又はC→C等のUターンの例が範囲に含まれてもよい。
【0094】
最後に、上記に含まれなかった全ての対の残部、すなわちA→C、A→D、B→B、C→A、C→B、D→Dが範囲に含まれてもよい(デフォルト手段により黙示的又は明示的に)。
【0095】
多車線道路、侵入路等を含む複雑な交差点のより複雑な例において、モデルは図8に関連して詳述されるように3つ以上の区分に関連してもよい。図8は、多車線道路を含む4方向の一例を示し、関連する軌道は、多くは交差点内の連結部、すなわちAC、DB、CA及びBDを含み、ここでは潜在的な、付加的な方向転換専用車線又は侵入路を無視する。上述したように、A←→C(簡潔に言うと、A2→C2及びC1→A1)は、優先権を有し且つ右側通行であると仮定される。
【0096】
通過時間プロファイルの最も明らかな候補は以下の通りである。
【0097】
B1→BD→AC→C2
B1→BD→D1
B1→A1
D2→DB→CA→A1
D2→DB→B2
D2→C2
更なる候補は、A2→AC→DB→B2及びC1→CA→BD→D1であってもよく、左折はA←→Cに沿う交通渋滞中の追加の待ち時間により影響を受ける可能性がある。
【0098】
また、A2→AC→DB→CA→A1及びC1→CA→BD→AC→C2、並びにB1→BD→AC→DB→B2及びD2→DB→CA→BD→D1を含むUターンの例が範囲に含まれてもよく、上述したように、左折はA←→Cに沿う交通渋滞中の追加の待ち時間により影響を受ける可能性がある。
【0099】
最後に、上記で含まれなかった以下の全ての対の残部が範囲に含まれてもよい(デフォルト手段で黙示的又は明示的に)。
【0100】
A2→AC→C2
A2→D1
C1→CA→A1
C1→B2
運転者がA2に沿って運転し、B2に曲がりたいことを考慮すると、C1→A1の交通渋滞は、DBにいる間の長い待ち時間の原因になるだろう。同様に、DBでの待ち時間は、D2から接近してくる、A1又はB2が目的地方向の運転者にも起こる可能性がある。本発明の実施形態は、交差点を横断する移動時間を推定する時に考慮されることを許容する。これは、信号で規制される多車線道路の交差点等での待ち時間を含んでもよい。
【0101】
使用する際、道路区分及び交差点を通る経路と関連付けられた速度プロファイルは、位置データ及び特に上述したようにGPSトレースから導出された移動から作成される。説明される実施形態において、そのような位置データはPND及びそのGPS受信機から収集された。しかし、そのように収集される必要はない。
【0102】
特定の交差点を通る通過時間遅延を表す包括的なデータを判定するのに利用可能ないくつかの特殊な方法が存在してもよく、そのような2つの特殊な方法を以下に概略的に説明する。
【0103】
第1の方法は、個別化された通過時間プロファイルを対象とし、種々の交差点の軌道に対する時間の影響を評価するために位置データを解析し、所定の時間間隔で所定の操作に沿う低下した平均速度の影響による通過時間を提供しようとする。
【0104】
この方法は、各々が複数のステップを含む複数のサブタスクに細分されてもよい。第1のサブタスクにおいて、移動は地図データに保持された道路区分間の交差点と関連付けられる。
【0105】
このために、所定の交差点と関連する移動の集合が判定される。これは、以下のステップをその順番又は変更された順番(図10を参照して説明する)で含んでもよい。
【0106】
i. 地図データを使用して所定の交差点との接続性を判定する。この結果、当該交差点に対するサブネットワーク(すなわち、交差点と位相幾何学的に接続された全ての道路区分に関する「共通の境界線」)が得られる。
【0107】
ii. 当該交差点の周囲のバウンディングボックスを使用して処理されている移動内でGPS座標の空間フィルタリングを適用する。バウンディングボックスのサイズは、交差点のサブネットワークの空間範囲に基づいて、あるいはデータ検索のために最適化されたデフォルトの寸法に基づいて又は他の理由で選択されてもよい。すなわち、交差点を通過する移動の一部に対応するGPS座標を判定する―ステップ1000。GPSを使用する実施形態において、GPS座標は所定の時の車両の位置に対応することが当業者には理解されるだろう。
【0108】
iii. GPS座標毎に、交差点のサブネットワークと対応する道路区分において最も近接する位置(該当する場合)を判定することにより、空間フィルタリングされたGPS座標に対してマップマッチングを実行する(すなわち、たとえば606aのGPS座標は最も近接する道路区分602と関連付けられる)。マップマッチングは、より高度なマッチング基準をとってもよく、マッチング基準は、GPS&地図精度の状態、地理的な近さ、GPS速度&地図属性の近似、GPS&道路区分の方向性、隣接するデータ点の間の依存性を含むがこれらに限定されない。これもステップ1000の一部と考えられてもよい。
【0109】
あるいは、通過時間プロファイルの生成は、道路区分に対する速度プロファイルの生成等の他の目的で実行された位置データ処理を利用してもよく、通過時間プロファイルの副産物として、GPSトレース及びGPS移動の少なくともいずれか一方のマップマッチングレイヤが既に提供されていてもよい。
【0110】
所定の交差点に対する更なる位置データ処理ステップは以下を含む(この順番又は変更された順番で)。
【0111】
iv. マップマッチングされたGPS座標に対応する道路区分を横切る進路に関して、空間フィルタリング及びマップマッチングされた移動毎に交差点の軌道を判定する。これはステップ1002として示され、交差点を通る経路に応じて交差点に関連した位置データを分類すると考えられてもよい。
【0112】
v. 交差点を通る軌道に基づいて全ての移動をクラスタリングし、運転操作により移動を分類する(「操作にマッチしたGPS移動」として考えられてもよい)。当該交差点で開始又は終了するGPS移動は本実施形態において廃棄される。これは、ステップ1002の一部として考えられてもよい。
【0113】
vi. 考慮に入れる操作にマッチしたGPS移動の(最小の)長さを判定する。これを達成するために、以下の基準が適用されてもよい。所定の交差点の前(又は後)の十分なGPS座標の範囲は、以下の範囲にわたる。
【0114】
○速度プロファイルが確立される、少なくとも1つの道路区分全体又は複数の接続が可能にされた道路区分
○微調整が行われることを条件として、特定の所定の距離D(約150mとする)
○1つ又は複数の道路区分全体を選択するための道路区分の最小の長さ閾値である距離D。
【0115】
vii. 第1のサブ進路を判定するために各操作にマッチしたGPS移動のコアセグメンテーションを実行する:
○道路区分への接近(approaching road segment)にマッチしたGPS座標を含む操作前の進路。
【0116】
viii. オプションとして、他のサブ進路を更に判定するために各操作にマッチしたGPS移動のより包括的なセグメンテーションを実行する:
○地図データベース中の交差点表現の一部としてモデル化された道路区分にマッチしたGPS座標を含む操作中の進路
及び
○離れていく道路区分にマッチしたGPS座標を含む操作後の進路
の少なくともいずれか一方。これらのステップをステップ1004内に示す。
【0117】
サブ進路の境界において、GPS座標は、操作前の進路と操作中の進路又は操作中の進路と操作後の進路の双方にそれぞれに属してもよい。図7に示した上述のABCDの例等の「単純な」交差点/横断歩道の(一般的な)例において、所定のGPSトレースの操作中の進路は「空」であってもよく、GPS座標は操作前又は操作後の進路に属してもよい。
【0118】
ix. 繰り返しパターンに対応する通常の通過時間プロファイルを確立するために、時間帯毎/曜日毎の別個のタイムスロットのように定めた時間間隔スキームに基づいて操作にマッチしたGPS移動の第2のクラスタリングを適用する。
【0119】
例えば別個のタイムスロットは、例えば第1の時間(例えば、午前9時)と第2の時間(例えば、午前9時59分)との間に起こる各操作にマッチしたGPS移動が同一の時間範囲内に配置されるように、ほぼ1時間の長さの時間範囲に対応してもよい。時間範囲は、1時間以外の長さ、例えば約10分、15分、20分、30分、45分、2時間、6時間、12時間又はそれらの長さの間のあらゆる時間のうちのいずれかであってもよいことが当業者には理解されるだろう。
【0120】
これは、ステップ1006に示され、この例においては所定の長さである所定の期間内の時間を平均するものと考えられる。
【0121】
x. オプションとして、不規則なパターンに対応した異常通過時間プロファイルを確立し正常通過時間プロファイルを上書きするするために、国の祝日や祭典等の日毎や週毎に起こるのではない不規則な時間パターンに基づいて同じ操作にマッチしたGPS移動の第2の並列クラスタリングを適用する。異常通過時間プロファイルを考慮した操作にマッチしたGPS移動は、正常通過時間プロファイルに対して作成された第2のクラスタから除外される。
【0122】
そのような第2の並列クラスタリングにより、交通の流れが国の祝祭日のように「正常」パターンに当てはまらない日に対して交差点の通過時間プロファイルがマッピング可能になる。従って、速度プロファイルが経路計画に後で使用される場合、その日の交通の流れが「正常」である可能性が高いか又は「異常」である可能性が高いかに関わらず、可能性の高い交通の流れをより正確に反映する交差点の通過時間プロファイルを使用できる。
【0123】
xi. 操作にマッチしたGPS移動の第2のクラスタ毎を平均することにより操作前のGPS座標の時間的な挙動を評価する。特に、操作前のGPS座標の平均速度の低下(対応する道路区分の速度プロファイルと比較して)を観察できたかを評価する。
【0124】
○評価が肯定的である場合(すなわち、第2のクラスタにおける速度が道路区分全体の平均速度より遅い場合)、評価した操作と当該時間間隔に対する操作前の時間ペナルティを判定する。これは、対応する道路区分の長さを平均速度比較の絶対差分で除算した値に等しい
○これに対して、評価が否定的である場合(すなわち、第2のクラスタと道路区分の平均速度との間の速度差がない場合)、評価した操作と当該時間間隔に対して操作前の時間ペナルティはゼロとして宣言される(且つ/又は適用不可としてフラグが立てられる)。
【0125】
xii. 同様に、操作後の進路の包括的なセグメンテーションが適用可能である場合、操作にマッチしたGPSトレースの第2のクラスタ毎に平均することにより操作後のデータ点の時間挙動を評価する。
【0126】
○評価が肯定的である場合(すなわち、第2のクラスタにおける速度が道路区分の平均速度より遅い場合)、評価された操作と当該時間間隔とに対する操作後の時間ペナルティを判定する。これは、対応する道路区分の長さを平均速度比較の絶対差分で除算した値に等しい
○これに対して、評価が否定的である場合(すなわち、第2のクラスタにおける速度が道路区分の平均速度以上である場合)、評価された操作と当該時間間隔とに対して操作後の時間ペナルティはゼロとして宣言される(且つ/又は適用不可としてフラグが立てられる)。
【0127】
xiii. あるいは、操作後の進路の包括的なセグメンテーションが適用可能である場合、操作にマッチしたGPS移動の第2のクラスタ毎に平均することにより操作前と操作後のGPS座標の組み合わされた時間挙動を評価する。特に、平均して、何らかの所定の操作前の進路のGPS座標に対する最後(又は最後のいくつか)のタイムスタンプと関連する操作後の進路のGPS座標の最初(又は最初のいくつか)のタイムスタンプとの間の大きな時間差が観察されるかを評価する。
【0128】
○評価が肯定的である場合、もし該当する場合は、(明示的な)交差点内の遅延を含む平均された全部の時間差と等しい、当該評価された操作と時間間隔とに対する操作前後の時間ペナルティを判定する
○これに対して、評価が否定的である場合、当該評価された操作と時間間隔とに対して操作前後の時間ペナルティはゼロと宣言される(且つ/又は適用不可能としてフラグが立てられる)。
【0129】
xiv. 更に又はあるいは、操作中の進路の包括的なセグメンテーションが適用可能である場合、操作にマッチしたGPSトレースの第2のクラスタ毎に平均することにより操作中のGPS座標(存在する場合)の速度挙動を評価する。特に、操作中のデータ点と関連付けられた全ての速度の平均が関連する操作前及び操作後の平均速度より非常に遅いか(対応する道路区分の速度プロファイルと比較し、それにより全ての平均速度が同一の原理に従って判定される)を評価する:
○評価が肯定的である場合、当該評価した操作と時間間隔とに対する操作中の相対時間ペナルティを判定する。これは、操作中の進路の長さを平均速度比較の絶対差分により除算した値に等しい。更に又はあるいは、当該評価した操作と時間間隔とに対する絶対的な操作中の時間ペナルティを判定する。これは、操作中の進路の長さを操作中の進路の平均速度により除算した値に等しい
○これに対して、評価が否定的である場合、当該評価した操作と時間間隔とに対して操作中の時間ペナルティはゼロと宣言される(且つ/又は適用不可としてフラグが立てられる)。
【0130】
所定の交差点に対するGPS座標処理ステップの最後の集合は以下を含む。
【0131】
xv. 操作にマッチしたGPS移動の所定の第2のクラスタと所定の時間間隔とに対して導出された各時間ペナルティの統計的な有意性及び信頼度の少なくともいずれか一方を検査する。すなわち、クラスタリングから導出された平均値は、平均値を生成したデータが所定の品質基準ステップ1008を満たすかを判定するために解析される。
【0132】
○位置データが大まかすぎると検査が示す場合、フォールバック戦略(「ギャップフィリング」と呼ばれてもよい)を適用し、低解像度時間間隔法を適用することにより(当該時間間隔、あるいは同様の又は全ての時間間隔に対して)第2のクラスタリングステップ(及び次の時間操作挙動評価ステップ)を繰り返す。すなわち、時間範囲の時間の長さが1時間であった場合、より多くのGPS移動がより長い時間範囲に入るように、新しいより長い長さ(例えば、3時間の時間ビンが最初に設定されてもよい)にする。位置データが依然として大まかすぎる場合、時間範囲を更に長くしてもよい
・第1のフォールバック応答において、ラッシュアワー対残りの日中時間対夜間等のように、より長い期間にわたる操作にマッチしたGPS移動のより大きなサンプルの利用を一般化する。そのような時間間隔のマージは、道路区分の速度プロファイルに対して観察される交通量パターンに基づいてもよい
・第2のフォールバック応答として(十分なGPS座標の有効範囲及び/又は密度の不足が持続すると仮定する)、速度プロファイルが同様の特性を有する交差点の集合に対して作成されるように、比較及び統一された処理の基礎として交差点の分類を利用する(個々の交差点毎に速度プロファイルを形成しようとするのではない)。このように、同一あるいは同様の特性(道路種別、道路形態、接続された道路区分の速度プロファイル及び都市対非都市の設定等)を有する交差点に対する通過時間プロファイルは、不十分なGPS座標数を有する例におけるギャップフィリングに対して共有されてもよい
・第3のフォールバック応答として、通過時間遅延を判定する第2の特殊な方法は、以下に更に説明するように交差点方向転換分類に対する方法を詳述する
○オプションとして、位置データがより高い粒度を有する可能性があると検査が示す場合、高解像度時間間隔法を適用する(当該時間間隔、あるいは同様の又は全ての時間間隔に対して)ことにより第2のクラスタリングステップ(及び次の時間操作挙動評価ステップ)を繰り返す。
【0133】
xvi. 所定の時間間隔(すなわち、時間範囲)において操作にマッチしたGPS移動の所定のクラスタに対して所定の時間単位で測定した時間オフセット(合計の「時間損失」)を判定する。以下のように、種々の戦略が適用されてもよい。
【0134】
○最も一般的には、操作前の進路のコアセグメンテーションに基づくと、時間オフセットは操作前の時間ペナルティと等しい。交差点での時間損失の殆どは、減速が行われ且つ何らかの列ができる可能性が高い操作前の進路(図6の608)内で起こることが当業者には理解されるだろう
○あるいは、操作中の進路及び操作後の進路(必要に応じて)の少なくとも一方を含む包括的なセグメンテーションに基づくと、時間オフセットは、操作前の時間ペナルティ、操作後の時間ペナルティ、操作中の相対時間ペナルティ(該当する場合)の合計と等しい
○第2の別の例として、操作中の進路及び操作後の進路(必要に応じて)の少なくとも一方を含み且つ交差点内の連結部を除く道路区分に対する速度プロファイルの範囲を更に予想する包括的なセグメンテーションに基づくと、時間オフセットは、操作前の時間ペナルティ、操作後の時間ペナルティ、操作中の絶対時間ペナルティ(該当する場合)の合計と等しい
○第3の別の例として、少なくとも操作後の進路を含む包括的なセグメンテーションに基づくと、時間オフセットは、操作前後の時間ペナルティと等しくてもよい。
【0135】
xvii. 時間帯/曜日の関数、cそして該当する場合は異常時間間隔スキームの関数における時間オフセットに関して交差点の操作毎の時間コストのプロファイルをアセンブルする。
【0136】
方向転換コストプロファイルは、時間オフセットの離散平均又はパラメータ関数としてモデル化される。時間オフセットは、絶対の又は分類(符号化)された値又は時間オフセット関数のパラメータとして指定されてもよい。
【0137】
上記ステップ又はそれ以外に従って生成された通過時間プロファイルのデータセットは、一実施形態において、道路区分への接近→道路区分からの出(departing road segment)の全ての組み合わせを範囲に含む交差点毎の完全な時間依存方向転換コストマトリクス又は重要な方向転換のみ(地図データベースの交差点の全て又は部分集合に対する)を含む縮小されたマトリクスとして提供される。そのようなマトリクスは、データベース、テーブル又はリスト構造で編成されてもよい(道路区分に対する速度プロファイルと共に又は別個に)。それらのマトリクスは、コンテンツファイル、ソフトウェアライブラリとして又はウェブサービスを介して利用可能にされてもよい。通過時間プロファイルのデータセットは、地図データベースコンテンツの必須部分として格納及び管理されてもよく、あるいは補助的なルックアップテーブル等のアドオンデータとして処理されてもよい。
【0138】
上述の実施形態と同等の別の実施形態において、方向転換コストマトリクスのコンテンツは、種々の道路区分への接近に添付される属性集合へ時間オフセットプロファイルを転送することにより再計算(recast)されてもよい。これは、所定の道路区分の方向での特定の道路区分への接近の可能な操作毎に、以下を含む位相時間コストプロファイル属性が添付されることを意味する。
・交差点や横断歩道に対する方向性、及び交差点や横断歩道の地図データ参照(ID)のいずれか一方。
・出て行く道路区分に対応する地図データ参照(ID)。
・時間コストプロファイル。
【0139】
更に又は更なる別の例として、上述したモデル(道路区分への接近の属性の集合である時間コストプロファイル)は、位相的表現(「区分A→区分B」)の実際の操作の意味が地理的/幾何学的表現(「左折」、「+90°に曲がる」及び「北東に向けて曲がる」等)に変換される。従って、各通過時間プロファイルは、定量化された方向転換時の相対角度又は絶対角度、並びに/あるいは分類された相対的又は絶対的な方向転換の意味により記述される。操作に用いるために、そのような地理的や幾何学的な時間コストプロファイル属性は、地図データ参照(ID)を利用しないため、通過時間プロファイルに対する地図データベースモデルを簡略化する。1つのアプリケーションによる対象とされた用途に依存して、この属性モデルは利点(例えば、人間‐機械インタフェースのより直感的な表現)及び欠点(例えば、実行時に経路計画者による解釈を必要とする)の双方を有する。
【0140】
地理的や幾何学的な時間コストプロファイル属性は、視覚特性(可能性として、時間に依存し且つ/又は動的である他の道路又は環境特性と共に)に容易に変換されるという点で安全で効率的なアプリケーションの拡張機能を容易にする。所定の道路又は経路に沿うか又は所定の地域における可能な方向転換操作の範囲に対するカラー符号化アイコンは、例えばスループットレベルの評価のある形を示してもよい。
【0141】
更なる一実施形態において、方向転換コストプロファイルのデータの表し方は、ある道路区分への接近から直線(又はほぼ直線)の通過進路(through-path)に対応する、所定の交差点や横断歩道における主運転方向を考慮に入れる。主運転方向は、所定の時間/日付におけるそれぞれの時間オフセットに関して基準通過時間プロファイルとしての役割をする。すなわち、同一の道路区分への接近を有する当該交差点や横断歩道における残りの操作の時間オフセットプロファイルは、基準時間オフセットに対する差分ペナルティとして表される。その結果として、所定の方向転換及び所定の時間間隔に対する適用可能な差分ペナルティは、負でも正でもよい。すなわち、通過時間は遅延でも利得でも表示してよい(負が時間の遅延を示すか又は利得を示すかは実現する際の選択肢である)。道路区分に対する速度プロファイルが主方向に沿う速度や通過時間(交差点横断操作を含む)を十分に範囲に含むと仮定される場合、実際の基準時間オフセットはアプリケーションによりゼロと仮定されてもよく又は無視されてもよい。差分ペナルティプロファイルは最新の解決策を高め、解決策は時間依存プロファイルを使用しない場合には主方向以外の操作に対する一定のペナルティ又は何らかの分類されたペナルティのパターンを仮定する必要がある。
【0142】
上述の実施形態の一変形例は、所定の交差点での他の何かの操作に対する差分ペナルティプロファイルと当該道路区分への接近とを導出するための基準操作として「時間損失がゼロ」の操作又は「時間損失が最小」の操作を使用することである。「時間損失がゼロ」の操作又は「時間損失が最小」の操作の判定は通過時間プロファイルを生成する(説明したように又は別の方法で行われるように)処理に基づき、この処理は減速せず且つ時間オフセットなしで又は最小の減速及び最小の時間オフセットで操作が自然に継続されることを判定することを可能にする。判定されると、そのような自然な継続は所定の交差点及び道路区分への接近における他の何らかの方向転換に対する差分ペナルティプロファイルを生成する基準となる。本実施形態の変形例において、差分ペナルティは、常に負であり(又は実現する際の選択肢に従って常に正であり)、最速の基準操作又は最小の障害の基準操作と比較した時間遅延を常に示す。
【0143】
組み込まれた解決策(経路指定アプリケーションの道路網地図データベースの一部として管理される通過時間プロファイル)に対して、既存のデータ構造が再利用又は修正されてもよい。
− 事前に生成された方向転換コストマトリクス(特定の又は全ての種別の交差点や横断歩道に対する)を使用する経路指定アプリケーションの場合、静的な方向転換コストデータは、時間依存方向転換コストにより補完や置換されてもよい。
− 位相時間コストプロファイル属性の同等の表現を考慮すると、それらの属性は、経路指定アプリケーションが方向転換コストデータにアクセスし且つ処理する方法に対応してもしなくてもよい。
− 地理的や幾何学的な時間コストプロファイル属性は、一般に経路指定アプリケーションがアクセス可能であるようにする必要がある属性の新しい集合である。
− 差分ペナルティプロファイルは、実行時の計算の複雑さを最小限にするTomTom IQ Routes等の時間の影響を受ける経路指定エンジンの現在の手法を対象とする。交差点/横断歩道へ入る道路区分と関連付けられた速度プロファイルは、当該交差点/横断歩道への接近において可能な所定の操作に対する差分ペナルティを考慮する追加的な操作の影響を受ける通過時間プロファイルの集合により補完される。上述の図7の4方向の交差点のA/B/C/Dの例を参照すると、Aから接近する場合、道路区分Aの速度プロファイルは2つの更なる通過時間プロファイルにより補完される。一方のプロファイルはA→Bの方向転換操作に対応し、他方のプロファイルはA→Dの方向転換操作に対応する(各プロファイルは所定の時間や日付に対する速度と差分ペナルティとの組合せプロファイルに関す。)。基準操作である主方向A→Cの場合、差分ペナルティはゼロである(ゼロと仮定される)。
【0144】
通過時間遅延を判定する第2の方法について図9を参照して概略的に示す。図9は、方向転換の種類の分類に基づく一般的な通過時間コスト関数に特化している。
【0145】
あらゆる1つの移動は、方向転換が後続する多くのそのような道路区分のトラバーサル(traversal)から構成される。上述したように、各方向転換は、操作前、操作中及び操作後の部分として考えられる。しかし、図9を参照すると、SからEまでの移動は、A及びCにおける交差点と共に道路区分900(SA)、902(AC)及び904(CE)を含む。
【0146】
従って、その移動の特定の地点に到着するための時間コストとして考えられる合計の移動時間は、前の交差点からの道路区分を運転するのに必要な時間+方向転換コスト(その道路区分に到着するのに必要な時間;すなわち先の道路からの通過時間)の合計により与えられる。図9を考慮すると、交差点iから交差点jまでの運転コストをDi_jで示し、交差点i及びjの間の道路区分と交差点j及びkの間の道路区分との間を移動するための方向転換コストをTcij_jkで示す。
【0147】
この場合、ソースノードSからグラフ中の各ノードに到着するためのコストは以下の通りである。
【0148】
CS=0
CA=DS_A
CB=DS_A+TcSA_AB+DA_B
CC=DS_A+TcSA_AC+DA_C
CD=DS_A+TcSA_AC+DA_C+TcAC_CD+DC_D
CE=DS_A+TcSA_AC+DA_C+TcAC_CE+DC_E (式1)
道路区分に沿う運転時間は、線の長さと運転速度との間の比により与えられる。例えばDS_A=lSA/vSAである。長さは一般に一定であり、速度は処理されている位置データ、例えばGPS座標(すなわち、車両の位置)から測定される。比較すると、方向転換は地図表現において厳密であり、その一方で上述したように方向転換時間は実際の運転においてある距離にわたり分布し且つ複数の道路区分にわたり分布する可能性が高いため、方向転換コストはより非決定論的である。例えば方向転換時間は、交差点における時間(交差点内の時間)と共に操作前のゾーン及び操作後のゾーンにおける時間により構成される。
【0149】
これにより、交差点遅延を推定するのは困難になり、その値は同様の状況において異なる可能性がある。この点に関して、第2の方法である統計的方法が使用され、種々の方向転換コストは所定のカテゴリに分類され、交差点遅延の平均時間はカテゴリ毎に推定される。
【0150】
道路は、測定された速度(平均又は速度プロファイル)、道路の形状(高速道路、多車線道路、非分離道路等)を説明する道路形態又は道路網に対する道路の重要度のような属性を有する。交差点が2つの道路間のリンクとして考えられてもよいことを考慮すると、これらの属性のどのような組合せも交差点のカテゴリを規定できる。存在する入力データが多いほど、考慮されるカテゴリは多く、推定される通過時間はより正確である。しかし、カテゴリの数が多すぎると、冗長性がもたらされるという欠点がある。精度と過度な複雑さとの間の均衡がとられるだろう。
【0151】
方向転換コスト(図7に関連して上述したように交差点を通る経路に割り当てられる時間)をグループ化するいくつかの方法がある。
【0152】
例えば道路区分への入りと出との間の角度差を使用できてもよい。そのような一実施形態において、複数のセクタ(説明される実施形態においては8個であるが、4個、16個、32個等の他のどんな数であってもよい)が作成され、交差点をカテゴリに分類するために交差点における道路区分間の角度差が使用される。例えば現在の実施形態において、0〜44°はカテゴリ0であり、45°〜89°はカテゴリ1であり、90°〜134°はカテゴリ2であり、135°〜179°はカテゴリ3であり、180°〜224°はカテゴリ4であり、225°〜269°はカテゴリ5であり、270°〜314°はカテゴリ6であり、315°〜359°はカテゴリ7である。従って、各セクタは方向転換コストカテゴリになる。
【0153】
他の実施形態において、更に又はあるいは、交差点に対する入りと出の道路区分の道路の形態、種類又は重要度(道路分類)を使用できてもよい。
【0154】
他の実施形態において、更に又はあるいは、交差点に対する進入路区分と分岐路区分との間の運転速度の差分を使用できてもよい。この基準は、先の基準と部分的に重なる可能性があり、冗長性をもたらす可能性がある。
【0155】
道路網の構造が国毎に非常に異なる可能性があることを考慮すると、カテゴリは地図別又は国別であってもよい。
【0156】
各移動は、式1に類似する式により表されてもよい。従って、位置データから収集されるGPS移動は、そのような式により各移動を表すために処理される。図11を参照すると、第1のステップは、そのような式の集合を生成するために位置データを処理することである。従って、方向転換コストが未知の変数である一次方程式の集合が生成され、各道路区分の移動時間は区分速度プロファイル(地図データから取得されてもよく又は位置データから生成されてもよい)及び道路の長さから推定される。合計の移動時間は、開始時間と終了時間との間の差分により与えられる。
【0157】
収集された位置データを処理することにより、大量のGPS移動が解析可能になり、式の数は未知数の数を上回ることを意味する。結果として得られる線形系は、最小二乗平均で解かれる。これは、予測通過時間と実際の通過時間(GPS移動から既知である)との間の誤差を最小限にする方向転換コストの集合を見つけるだろうことを意味する。
【0158】
コスト構造は、運転コスト(すなわち、道路区分を運転する時間)及び方向転換コスト(すなわち、交差点における時間損失)から構成される。合計の移動コストSは、
【0159】
【0160】
により与えられる。式中、Diは道路に属する各道路の運転時間であり、Tcjは経路に沿う方向転換コスト(時間で表される)である。測定速度は正確であると仮定され、方法は方向転換コストによりその推定を最適化しようとする。
【0161】
方法は、コストモデルに規定された方向転換の種類がN個存在すると仮定する。上記説明を参照すると、道路区分への入りと出との間の角度の関係に関連して8つのカテゴリを使用した一実施形態においてはN=8である。方向転換の種類をTc1〜TcNにより示す場合、経路番号kに対して
【0162】
【0163】
を得るだろう。式中、
【0164】
【0165】
は経路に沿う運転時間であり、
【0166】
【0167】
は経路kの合計の方向転換コストにおける方向転換の各種類の頻度である。
【0168】
例えばN=8である本発明の実施形態において、
【0169】
【0170】
はまっすぐ運転した回数を示す、
【0171】
【0172】
は45度の右折を行った回数を示す。
【0173】
k=1,...,Lからいくつかの経路を考慮する場合、以下の線形系が得られる。
【0174】
【0175】
【0176】
を定義すると、線形系は以下のような短縮形式で書き換えられる。
【0177】
Ax=b
上述したように、経路数Lは未知の方向転換コスト変数の数よりはるかに大きい、すなわち、L>>Nであり、そうではあるが正確な解は存在しない。
【0178】
上記で提示された線形系は、最小二乗法x+=A+bで解かれる。式中、A+はムーアペンローズ疑似逆行列である。方向転換コストベクトルx+は、所定の地図と組み合わせて経路制御により使用される最適な方向転換コスト値を提供する。
【0179】
ムーアペンローズ疑似逆行列は、誤差ベクトルの第2のノルムの最小値を与える未知の方向転換コストに対する値の集合を計算するのを支援する。これは、
【0180】
【0181】
であることを意味する。
【0182】
これは、計算された経路に対する正確な推定時間を生成する方向転換コストの集合を計算することはできないが、グローバル推定誤差を最小限にする最適な値の集合を得ることを意味する。従って、一次方程式の集合に対する近似解を導出するために数学的方法が使用されてきた(ステップ1102)。
【0183】
誤差の第2のノルムを最小限にするから、疑似逆行列の方法は最小二乗法である。
【0184】
従って、この第2の方法は、例えば所定の角度関係を有する交差点を見いだせる実施形態において、どの1つのカテゴリにおいても方向転換の平均方向転換コストを判定する。
【0185】
最後にステップ1010及び1104において、更なる地図データが作成され、この地図データにおいて、計算された特性を有するどの交差点に対する通過時間もその交差点と関連付けられる。そのような関連付けは、明示的であってもよく(例えば、地図データの一部等としてルックアップテーブル形式に通過時間又は通過時間の集合を提供する)、あるいは通過時間又は通過時間の集合が推定される方法論を規定することにより(例えば、通過時間が計算されることを可能にする基本時間に対するオフセットを提供することにより)行われてもよい。
【0186】
GPSデータという用語は、例えば図1に関連して説明したようなGPS全地球測位システムから導出された測位データを参照するために使用されてきたことが当業者には理解されるだろう。本明細書で説明した方法と類似した方法で他の測位データを処理できる。従って、GPSデータという用語は、測位データという語句で置き換えられてもよい。そのような測位データは、例えば移動電話動作から導出された位置データ、料金所で受信したデータ、道路に埋設された誘導ループから取得したデータ、ナンバープレート認識システムから取得したデータ、自動車間通信から取得したデータ、周囲の移動オブジェクト及び静止オブジェクトを観察し且つ相対測位をサポートする搭載型センサ(例えば、レーザスキャナ)から取得したデータ、あるいは他のあらゆる適切なデータから導出される。
【0187】
本明細書で説明した実施形態はソフトウェアにより特定の機能性を実現するが、その機能性はハードウェアでのみ(例えば、1つ以上のASIC(特定用途向け集積回路)を使用することにより)又は実際にはハードウェアとソフトウェアとの組合せにより同様に実現可能であることが当業者には十分に理解されるだろう。従って、本発明の範囲は、ソフトウェアで実現されることにのみ限定されるものとして解釈されるべきではない。
【0188】
尚、最後に、添付の請求の範囲は本明細書で説明した特徴の特定の組合せを示すが、本発明の範囲は、以下に請求される特定の組合せに限定されず、特定の組合せが添付する請求の範囲に特に列挙されているか否かに関係なく、本明細書で開示された特徴又は実施形態のいかなる組合せも含む。
【技術分野】
【0001】
本発明は、測位データを処理する方法に関し、特に、ナビゲーション装置及び特にポータブルナビゲーション装置(PND)、これに限定されない、で使用されるように構成された地図データを生成するために測位データを処理することに関する。更に本発明は、方法を提供するための関連した装置を提供する。
【背景技術】
【0002】
TomTom International BV GO(登録商標)のようなGPSを用いたパーソナルナビゲーション装置等の電子ナビゲーション装置のための地図データは、Tele Atlas NV等の地図専門メーカから得られる。そのような装置は、ポータブルナビゲーション装置(PND)とも呼ばれる。特に、この地図データは、一般にGPSシステムからの位置データを使用する経路ガイダンスアルゴリズムにより使用されるように設計される。例えば、道路は線、すなわちベクトル(例えば、道路の始点、終点、方向であり、道路全体は、各々が始点/終点方向パラメータにより一意に規定される数百の区分から構成される)として記述される。地図は、そのような道路区分、各区分と関連付けられたデータ(制限速度;移動方向等)+地点情報(POI)+道路名+公園の境界や川の境界等の他の地理的特徴の集合であり、それらは全てベクトルに関して規定される。全ての地図の特徴(例えば、道路区分、POI等)は、一般にGPS座標系に対応するか又は関連する座標系で定義され、GPSシステムを介して判定される装置の位置を地図に示される関連道路に配置することを可能にし、目的地までの最適な経路の計画を可能にする。
【0003】
この地図データベースを構築するために、Tele Atlasは、英国の道路のOrdnance Survey等の種々の情報源からの基本的な道路情報を利用する。これは、道路を走行する車両専用の大きなチーム、並びに他の地図及び空中写真を調査する担当者を配備して、自身のデータを更新及び調査することを更に含むがそれに限定されない。このデータがTele Atlasの地図データベースの中核を構成する。この地図データベースは、地理参照データにより継続的に向上されている。これは、1年に複数回調査され、TomTomのような装置製造業者に公表される。
【0004】
そのような各道路区分は、道路区分に対する関連する速度データを有し、速度データは、車両がその区分に沿って移動可能である速度の指示を与え、例えばTele Atlasであってもよい地図データを生成する者により生成された平均速度である。速度データは、地図が処理されるPND又は他の装置において経路計画アルゴリズムにより使用される。そのような経路計画の精度は、速度データの精度に依存する。例えば、ユーザはしばしば装置の現在地と目的地との間の最速経路を生成するためにPNDにオプションを提示される。速度データが不正確である場合、PNDにより計算された経路は最速経路ではない可能性がある。
【0005】
交通量等のパラメータが道路区分の速度プロファイルに重大な影響を及ぼすことは既知であり、そのような速度プロファイルのばらつきは、2つの地点間の最速経路が同一にとどまっていない可能性があることを意味する。道路区分の速度パラメータが不正確である場合、不正確な推定到着時間(ETA)を導き且つ次善の最速経路の選択を導くことになる。
【0006】
地図データは、道路区分間の交差点に対する時間許容を更に含む。これらの時間許容は、それらの時間許容が発生する道路区分の所定のカテゴリに対して固定値である傾向がある。経路指定アルゴリズムは、経路を判定するために地図データを処理している時にこの時間許容を使用するように構成される。
【0007】
Tele AtlasはGPSデータがPNDからアップロードされ、所定の時間帯の道路区分における実際の平均速度を示す速度パラメータを提供することを目的として地図データの区分に対する速度パラメータを提供するために使用されるシステムを開発した。
【発明の概要】
【発明が解決しようとする課題】
【0008】
経路計画の精度は、速度データの精度に依存する。例えば、ユーザはしばしば装置の現在地と目的地との間の最速経路を生成するためにPNDにオプションを提示される。速度データが不正確である場合、PNDにより計算された経路は最速経路ではない可能性がある。
【課題を解決するための手段】
【0009】
本発明の第1の側面によると、
ある期間にわたり少なくとも1台の車両の位置から導出された位置データから地図データを作成するコンピュータを使用した方法であり、前記地図データが地図によりカバーされる地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分を含み且つ地図データがナビゲート可能な経路における交差点を表すナビゲート可能な区分間の交差点を更に含む方法であって:
i.位置データを処理するステップと;
ii.地図データの交差点の少なくとも一部に対する通過時間又は通過時間の集合を位置データの処理から計算するステップと;
iii.交差点の少なくともいくつかに対して、計算が行われた交差点と関連付けられた計算された通過時間又は通過時間の集合を含む更なる地図データを生成するステップと
を実行するために処理回路を使用することから成る方法が提供される。
【0010】
位置データから交差点の通過時間を判定することにより、より明確な通過時間が交差点に割り当てられる。交差点の通過時間は、道路区分の通過時間と比較してより複雑な道路網の特性である。これは、所定の道路区分の属性ではなく、複数の道路区分にわたる運転行動の特性である。そのような「コスト」は、特定の状況下では大きい。その主な一例は、優先通行権を有する渋滞した道路(例えば、ラッシュアワーの時)に入りたいか又は横断したい車両の待ち時間である。従って、通過時間の精度を向上することにより、装置は地図データを使用してより正確な経路を計画できる。
【0011】
区分によりナビゲート可能な経路を表すどんな地図に対しても、区分の間に境界線を有する必要があること、すなわちその地図を使用して計画されたどんな経路も短くない限り複数の区分を移動する必要があることが当業者には理解されるだろう。これは、それらの境界線がナビゲート可能な経路の交差点において提供される場合に便利であるが、必ずしも当てはまらない。しかし、どのようにこれらの区分が配置されても、本発明の実施形態は、区分間を通過するための通過時間又は通過時間の集合を判定するために利用されてもよい。区分間の通過時間は、通過が発生するセグメントに対して平均速度又は速度プロファイルから導出できない可能性がある。
【0012】
この方法は、位置データ内で車両の移動を識別するために位置データを解析してもよい。
【0013】
この方法は、交差点を通る経路を判定することと位置データを解析することから構成されてもよく、交差点を通る判定された経路を通過する移動を判定するために、一般に位置データ内で識別された移動を解析するように構成されてもよい。上述したように、いずれか1つの交差点を通る種々の経路は、非常に異なる通過時間を有することができる。例えば接近してくる交通を横断する左折は、交通を横断しない左折よりかなり遅い可能性が高い。
【0014】
その後、判定された経路を通過するその移動又は各移動は、その移動が交差点を通過するのにかかる時間を判定するために、すなわち通過時間を判定するために、あるいは少なくとも通過時間の推定値を提供するために解析されてもよい。
【0015】
所定の経路のうちの1つを利用したと判定された移動の時間は平均され、それによりその所定の移動に対するより正確な全体の時間を与えてもよい。
【0016】
いくつかの実施形態において、平均値はあらかじめ設定された期間内にとられてもよい。一実施形態において、移動は移動にかかる時間に従って平均される。移動はあらかじめ設定された長さの期間にわたり平均されてもよい。交通の流れが1日の推移のうちでいちじるしく越えることができるため、あらかじめ設定された期間を使用することにより精度が向上されることが理解されるだろう。
【0017】
この方法のいくつかの実施形態は、平均値の品質を判定するために平均値を解析するように構成されてもよい。品質が所定の基準を満たさないと判定された場合、平均値は変更されてもよい。
【0018】
いくつかの実施形態において、あらかじめ設定された期間の長さが増加され、それによりいずれか1つの期間内の移動の数を増加してもよい。
【0019】
この方法は、交差点を通る移動を、交差点前のゾーン、交差点内のゾーン及び交差点後のゾーンのうちの少なくとも1つに分析するように更に構成されてもよい。この方法は、交差点前のゾーン、交差点内のゾーン及び交差点後のゾーンのうちの1つ以上を交差点と関連した通過時間として利用することを更に含んでもよい。
【0020】
この方法は交差点の周囲の道路区分に四角い境界(バウンディングボックス)を適用してもよい。そのような方法は、この位置データが交差点を通る進路の一部として考えられるべきであることを判定するのに便利である。
【0021】
バウンディングボックスは、交差点の1つの地点からの所定の距離に関して判定されてもよい。例えばバウンディングボックスは、交差点から約150mであると判定されてもよい。約50m、75m、100m、125m、175m、200mのうちのいずれかの距離等の他の距離が適切であってもよいことは、当業者には理解されるだろう。
【0022】
あるいは又は更に、バウンディングボックスは、交差点として判定された地点からの通過時間を使って判定されてもよい。
【0023】
交差点は種類に従って分類されてもよく、同一の又は少なくとも同様のカテゴリ内の交差点を通過するのにかかる移動時間は平均されてもよい。そのような方法は、平均値を改善する目的で先に判定された平均値に適用されてもよい。あるいは又は更に、交差点の種類は平均値を判定するために使用されてもよい。
【0024】
この方法は、交差点の通過時間が未知の変数である式の集合を判定するために位置データから導出された移動を使用するように構成されてもよい。
【0025】
更にこの方法は、少なくともいくつかの交差点の通過時間を判定するために式の集合を処理するように構成されてもよい。いくつかの実施形態において、方法は、交差点のカテゴリ毎に通過時間を判定して式の集合の誤差を最小限にすることにより通過時間を判定する。
【0026】
本発明の第2の側面によると、地図によりカバーされる地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分、並びに地図によりカバーされるナビゲート可能な経路の交差点を表す交差点を含む地図データを作成するように構成された装置であって、ある期間にわたり少なくとも1台の車両の位置から導出された位置データを処理するように構成された処理回路を備え、処理回路は:
i.位置データを処理し;
ii.地図データの交差点の少なくとも一部に対する通過時間又は通過時間の集合を位置データの処理から計算し;
iii.交差点の少なくともいくつかに対して計算が行われた交差点と関連付けられた計算による通過時間又は通過時間の集合を含む更なる地図データを生成する;
ようにプログラムされた装置が提供される。
【0027】
本発明の第3の側面によると、地図によりカバーされた地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分、並びに地図によりカバーされたナビゲート可能な区分間の交差点を表す交差点を含む地図データであって、交差点の少なくともいくつかは本発明の第1の側面の方法を使用して位置データを平均することにより導出された関連する通過時間を有する地図データが提供される。
【0028】
本発明の第4の側面によると、コンピュータにより読み出された時に本発明の第1の側面の方法をコンピュータに実行させる命令を含むコンピュータ読み取り可能な記録媒体が提供される。
【0029】
本発明の第5の側面によると、コンピュータにより読み出された時にそのコンピュータを本発明の第2の側面の装置として機能させる命令を含むコンピュータ読み取り可能な記録媒体が提供される。
【0030】
本発明の第6の側面によると、本発明の第3の側面の地図データを含む命令を含むコンピュータ読み取り可能な記録媒体が提供される。
【0031】
本発明の第7の側面によると、ある期間にわたり少なくとも1台の車両の位置から導出された位置データから地図データを作成するコンピュータを使用した方法であり、地図データが地図によりカバーされた地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分を含み且つナビゲート可能な経路における交差点を表すナビゲート可能な区分間の交差点を更に含む方法であって:
i.位置データを処理するステップと;
ii.地図データの交差点の少なくとも一部に対する通過時間又は通過時間の集合を位置データの処理から計算するステップと;
iii.通過時間から通過時間プロファイルを生成するために所定の期間内の計算された通過時間をクラスタリングするステップと;
iv. 交差点で判定された通過時間プロファイルを有する交差点の通過時間プロファイルを含む更なる地図データを生成するステップ;
とを実行するために処理回路を使用することから成る方法が提供される。
【0032】
本発明の第8の側面によると、ある期間にわたり少なくとも1台の車両の位置から導出された位置データから地図データを作成するコンピュータを使用した方法であり、地図データが地図によりカバーされた地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分を含み且つナビゲート可能な経路における交差点を表すナビゲート可能な区分間の交差点を更に含む方法であって:
i.位置データを処理するステップと;
ii.位置データの処理から交差点の通過時間が未知の変数である式の集合を生成するステップと;
iii.地図データの交差点の少なくとも一部の通過時間を式の集合から計算するステップと;
iv.交差点で計算された通過時間を有する交差点の通過時間を含む更なる地図データを生成するステップ;
とを実行するために処理回路を使用することから成る方法が提供される。
【0033】
本発明の上記側面のいずれかにおいて、コンピュータ読み取り可能な記録媒体は、フロッピディスク、CD ROM、DVD ROM/RAM(−R/−RW及び+R/+RWを含む)、ハードドライブ、固体メモリ(USBメモリキー、SDカード、Memorystick(登録商標)又はコンパクトフラッシュカード(登録商標)等を含む)、テープ、他のあらゆる形態の光磁気記憶装置、送信信号(インターネットダウンロード、FTP転送等を含む)、ワイヤ又は他のあらゆる適切な媒体のうちのいずれを含んでもよい。
【0034】
更に、本発明のいずれか1つの側面に関連して説明される特徴は、本発明の他の側面に対して適切に準用されることが当業者には理解されるだろう。
【図面の簡単な説明】
【0035】
本発明の教示の種々の側面及びそれらの教示を具体化する構成について、添付の図面を参照しながら図の例によって以下に説明する。
【図1】全地球測位システム(GPS)を示す概略図
【図2】ナビゲーション装置を提供するように構成された電子構成要素を示す概略図
【図3】ナビゲーション装置が無線通信チャネルを介して情報を受信する方法を示す概略図
【図4A】ナビゲーション装置の例を示す透視図
【図4B】ナビゲーション装置の例を示す透視図
【図5】ナビゲーション装置により採用されたソフトウェアの概略表現を示す図
【図6】2つの道路区分の間の交差点を概略的に示す図
【図7】第1の交差点の例を示す図
【図8】第1の交差点の例より複雑な第2の交差点の例を示す図
【図9】種々のノード間の経路の計画を示す図
【図10】本発明の実施形態の概略を示すフローチャート
【図11】本発明の実施形態の概略を示すフローチャート
【発明を実施するための形態】
【0036】
本発明の実施形態について、特にPND(ポータブルナビゲーション装置)を参照して説明する。しかし、本発明の教示はPNDに限定されず、経路計画及びナビゲーション機能性を提供するためにナビゲーションソフトウェアを実行するように構成されるどんな種類の処理装置にも例外なく適用可能である。従って、本出願において、ナビゲーション装置は、PND、車両に内蔵されたナビゲーション装置、地図サーバ(インターネットを介して経路及びナビゲーション機能性を提供する等)、あるいは実際には経路計画及びナビゲーションソフトウェアを実行する計算リソース(デスクトップ又はポータブルパーソナルコンピュータ(PC)、移動電話、あるいはポータブルデジタルアシスタント(PDA))として具体化されているか否かにかかわらず、どんな種類の経路計画及びナビゲーション装置も含むことを意図する(それに限定されない)。
【0037】
本発明の教示は、ユーザが1つの地点から別の地点までのナビゲーション方法に関する命令を要求していないが単に所定の場所のビューを提供してほしい状況においても有用であることが以下から明らかとなるだろう。そのような状況において、ユーザが選択した「目的地」の場所は、ユーザがナビゲーションを開始したい出発地に対応する必要はないため、本明細書で「目的地」の場所又は実際には「目的地」のビューを参照することは、経路の生成が不可欠であること、「目的地」まで移動する必要があること又は実際には目的地の存在が対応する出発地の指示を必要とすることを意味すると解釈されるべきではない。
【0038】
上記条件を考慮すると、図1は、ナビゲーション装置により使用可能な全地球測位システム(GPS)の一例を示す図である。そのようなシステムは既知であり、種々の目的で使用される。一般にGPSは、連続した位置、速度、時間及びいくつかの例においては無数のユーザに対する方向情報を判定できる衛星無線を使用したナビゲーションシステムである。以前はNAVSTARとして既知であったGPSは、極めて正確な軌道で地球を周回する複数の衛星からなる。これらの正確な軌道に基づいて、GPS衛星は自身の場所をいかなる数の受信ユニットにも中継できる。しかし、GLOSNASS、欧州のGalileo測位システム、COMPASS測位システム又はIRNSS(Indian Regional Navigation Satellite System)等の全地球測位システムが使用可能であることが理解されるだろう。
【0039】
GPSデータを受信する能力を特別に備える装置がGPS衛星信号に対する無線周波数の走査を開始すると、GPSシステムは実現される。GPS衛星から無線信号を受信すると、装置は、複数の異なる従来の方法のうちの1つを用いて、その衛星の正確な場所を判定する。殆どの例において、装置は、少なくとも3つの異なる衛星信号を取得するまで信号の走査を継続する(尚、位置は、通常は2つの信号のみでは判定されないが、他の三角測量技術を使用して2つの信号から判定することもできる)。幾何学的三角測量を実現する場合、受信機は、3つの既知の位置を利用して、衛星に対する自身の2次元位置を判定する。これは、周知の方法で行われる。更に、第4の衛星信号を取得することにより、受信装置は、周知の方法で同一の幾何学計算によりその3次元位置を計算できる。位置及び速度データは、無数のユーザにより連続的にリアルタイムで更新可能である。
【0040】
図1に示すように、GPSシステム全体を参照番号100で示す。複数の衛星120は、地球124の周囲の軌道上にある。各衛星120の軌道は、他の衛星120の軌道と必ずしも同期せず、実際には非同期であることが多い。本願の一実施形態のナビゲーション装置において利用可能なGPS受信機140は、種々の衛星120からスペクトル拡散GPS衛星信号160を受信するように示される。
【0041】
各衛星120から連続的に送信されるスペクトル拡散信号160は、極めて正確な原子時計を用いて達成される非常に正確な周波数標準を利用する。各衛星120は、そのデータ信号送信160の一部として、その特定の衛星120を示すデータストリームを送信する。一般に、GPS受信機140が三角測量によりその2次元位置を計算するために、GPS受信機140は少なくとも3つの衛星120からスペクトル拡散GPS衛星信号160を取得することが当業者には理解される。更なる信号を取得すると、全部で4つの衛星120から信号160を取得する結果となり、これによってGPS受信機140は、その3次元位置を周知の方法で計算できる。
【0042】
図2は、本願の一実施形態のナビゲーション装置200の電子構成要素の一例を、ブロック構成要素の形式で示す図である。尚、ナビゲーション装置200のブロック図は、ナビゲーション装置の全ての構成要素を含むものではなく、構成要素の多くの例を表すにすぎない。
【0043】
ナビゲーション装置200は、筐体(不図示)内に位置付けられる。筐体は、入力装置220及び表示画面240に接続されるプロセッサ210を含む。入力装置220は、キーボード装置、音声入力装置、タッチパネル、及び情報を入力するために利用される他の任意の周知の入力装置のうちの少なくとも1つを含むことができ、表示画面240は、例えばLCDディスプレイ等の任意の種類の表示画面を含むことができる。好適な実施形態において、入力装置220及び表示画面240は、タッチパッド又はタッチスクリーン入力を含む一体型入力表示装置に一体化され、その場合、ユーザは、複数の表示選択肢のうちの1つを選択するか又は複数の仮想ボタンのうちの1つを操作するために、表示画面240の一部分に接触するだけでよい。
【0044】
ナビゲーション装置は、例えば可聴出力装置(例えば、スピーカ)である出力装置260を含んでもよい。出力装置260がナビゲーション装置200のユーザに対して可聴情報を生成できるため、入力装置240は入力音声コマンドを受信するマイク及びソフトウェアを含むことができることが同等に理解されるべきである。
【0045】
ナビゲーション装置200において、プロセッサ210は、接続225を介して入力装置220に動作可能に接続され且つ入力装置220から入力情報を受信するように設定され、情報を出力するために出力接続245を介して表示画面240及び出力装置260のうち少なくとも一方に動作可能に接続される。更にプロセッサ210は、接続235を介してメモリリソース230に動作可能に結合され、接続275を介して入出力(I/O)ポート270に対して情報を送受信するように更に構成され、I/Oポート270は、ナビゲーション装置200の外部のI/O装置280に接続可能である。例えばメモリリソース230は、ランダムアクセスメモリ(RAM)等の揮発性メモリ及び例えばフラッシュメモリ等のデジタルメモリである不揮発性メモリを含む。
【0046】
プロセッサ210は、取外し可能なメモリカード(一般にカードと呼ばれる)が装置200に追加される際に使用されるポート234と接続236を介して通信してもよい。説明される実施形態において、ポートはSD(セキュアデジタル)カードが追加されることを可能にするように構成される。他の実施形態において、ポートは、他の形態のメモリが接続されるのを可能にしてもよい(コンパクトフラッシュ(CF)カード(登録商標)、Memory Stick(登録商標)、xDメモリカード、USB(Universal Serial Bus)フラッシュドライブ、MMC(マルチメディア)カード又はSmartMediaカード(登録商標)又はマイクロドライブ等)。
【0047】
外部I/O装置280は、例えばイヤホン等の外部リスニングデバイスを含んでもよいがこれに限定されない。I/O装置280への接続は、例えば、イヤホン又はヘッドホンへの接続及び移動電話への接続の少なくともいずれか一つのための例えばハンズフリー動作及び音声起動動作のいずれか一つを行うカーステレオユニット等のあらゆる他の外部装置への有線又は無線接続であってもよい。ここで、例えばナビゲーション装置200とインターネット又は他のネットワークとの間のデータ接続を確立するため、あるいは例えばインターネット又は他の何らかのネットワークを介してサーバとの接続を確立するための少なくともいずれか一つの接続に移動電話接続が使用されてもよい。
【0048】
図2は、接続255を介するプロセッサ210とアンテナ/受信機250との間の動作可能な接続を更に示す。この場合、アンテナ/受信機250は、例えばGPSアンテナ/受信機であってもよい。参照番号250で示されるアンテナ及び受信機は、図示のために概略的に組み合わされるが、アンテナ及び受信機は、別個に位置する構成要素であってもよく、アンテナは、例えばGPSパッチアンテナ又はヘリカルアンテナであってもよいことが理解されるだろう。
【0049】
更に、図2に示す電子構成要素が従来の方法で電源(不図示)により電力を供給されることが当業者には理解されるだろう。当業者により理解されるように、図2に示す構成要素の構成と異なるものが本願の範囲内で考えられる。例えば、図2に示す構成要素は、有線接続と無線接続との少なくとも一方を介して互いに通信状態にあってもよい。従って、本願のナビゲーション装置200の範囲は、ポータブル又はハンドヘルドナビゲーション装置200を含む。
【0050】
更に、図2のポータブル又はハンドヘルドナビゲーション装置200は、例えば自転車、モーターバイクや自動車又は船舶等の乗物に周知の方法で接続されるか又は「ドッキング」される。その場合、そのようなナビゲーション装置200は、ポータブル又はハンドヘルドナビゲーションとして使用するために、ドッキング場所から取り外し可能である。
【0051】
次に図3を参照すると、ナビゲーション装置200は、デジタル接続(例えば、既知のBluetooth技術を介するデジタル接続等)を確立する移動装置(不図示)(移動電話、PDA及び/又は移動電話技術を有するあらゆる装置等)を介してサーバ302との「モバイル」又は電気通信ネットワーク接続を確立してもよい。その後、移動装置は、そのネットワークサービスプロバイダを介してサーバ302とのネットワーク接続(例えば、インターネットを介する)を確立できる。従って、「モバイル」ネットワーク接続は、情報に対する「リアルタイム」又は少なくとも非常に「最新」のゲートウェイを提供するためにナビゲーション装置200(単独で且つ/又は車両に搭載されて移動するため移動装置であってもよく且つ多くの場合は移動装置である)とサーバ302との間に確立される。
【0052】
移動装置(サービスプロバイダを介する)とサーバ302等の別の装置との間のネットワーク接続は、例えばインターネット(ワールドワイドウェブ等)を使用して既知の方法で確立される。これは、例えばTCP/IPレイヤプロトコルを使用することを含むことができる。移動装置は、CDMA、GSM、WAN等のいかなる数の通信規格も利用できる。
【0053】
従って、例えばデータ接続を達成するために、移動電話又はナビゲーション装置200内の移動電話技術を介するインターネット接続が利用されてもよい。この接続のために、サーバ302とナビゲーション装置200との間のインターネット接続が確立される。これは、例えば移動電話又は他の移動装置及びGPRS(汎用パケット無線サービス)接続(GPRS接続はテレコムオペレータにより提供された移動装置に対する高速データ接続であり、GPRSはインターネットに接続するための方法である)を介して行われる。
【0054】
更に、ナビゲーション装置200は、移動装置とのデータ接続を完成し、例えば既存のBluetooth技術を介して周知の方法でインターネット及びサーバ302とのデータ接続を最終的に完成する。この場合、例えばデータプロトコルは、GSM規格に対するデータプロトコル規格であるGSRM等の任意の数の規格を利用できる。
【0055】
ナビゲーション装置200は、ナビゲーション装置200自身の中に、自身の移動電話技術を含んでもよい(例えばアンテナを含み、またはナビゲーション装置200の内部アンテナが選択されてもよい)。ナビゲーション装置200内の移動電話技術は、上述のような内部構成要素を含むことができ、挿入可能なカード(加入者識別モジュールやSIMカード)を含むこともでき、例えば必要な移動電話技術かアンテナの少なくとも一方を備える。そのため、ナビゲーション装置200内の移動電話技術は、任意の移動装置と同様の方法で、例えばインターネット410を介して、ナビゲーション装置200とサーバ302との間にネットワーク接続を同様に確立できる。
【0056】
GRPS電話設定の場合、移動電話の機種、製造業者等のたえず変わる範囲に関して正しく動作するために、Bluetooth対応のナビゲーション装置が使用されてもよく、機種や製造業者の専用設定は、例えばナビゲーション装置200に格納されてもよい。データは情報が更新されるよう格納される。
【0057】
図3は、多くの異なる構成で実施される汎用通信チャネル318を介してサーバ302と通信するナビゲーション装置200を示す図である。通信チャネル318を介する接続が本発明のサーバ302とナビゲーション装置200との間に確立される場合、本願のサーバ302及びナビゲーション装置200は通信可能である(尚、そのような接続は、移動装置を介するデータ接続やインターネットを介するパーソナルコンピュータを介する直接接続等である)。
【0058】
サーバ302は、図示しない他の構成要素に加えて、メモリ306に動作可能に接続され且つ有線又は無線接続314を介して大容量データ記憶装置312に動作可能に更に接続されるプロセッサ304を含む。更に、プロセッサ304は、通信チャネル318を介してナビゲーション装置200と情報の送受信を行うために、送信機308及び受信機310に動作可能に接続される。送受信される信号は、データ信号、通信信号又は他の伝搬信号の少なくともいずれか一つを含んでもよい。送信機308及び受信機310は、ナビゲーション装置200の通信設計において使用される通信条件及び通信技術に従って選択又は設計されてもよい。さらに送信機308及び受信機310の機能は、単一の信号送受信機に組み合わされてもよい。
【0059】
サーバ302は、大容量記憶装置312に更に接続される(又は含む)。なお、大容量記憶装置312は、通信リンク314を介してサーバ302に結合されてもよい。大容量記憶装置312は、ナビゲーションデータ及び地図情報のストアを含む。また、大容量記憶装置312は、サーバ302とは別個の装置であってもよく、サーバ302に組み込まれてもよい。
【0060】
ナビゲーション装置200は、通信チャネル318を介してサーバ302と通信するように構成され、図2に関して上述したように、プロセッサ、メモリ等を含み、更に、通信チャネル318を介して信号及びデータの少なくとも一方を送出する送信機320及び受信する受信機322を含む。尚、これらの装置は、サーバ302以外の装置と通信するためにも使用される。更に、送信機320及び受信機322は、ナビゲーション装置200の通信設計において使用される通信条件及び通信技術に従って選択又は設計され、送信機320及び受信機322の機能は、単一の信号送受信機に組み合わされてもよい。
【0061】
サーバメモリ306に格納されるソフトウェアは、プロセッサ304に命令を提供し、サーバ302がナビゲーション装置200にサービスを提供できるようにする。サーバ302により提供される1つのサービスは、ナビゲーション装置200からの要求の処理及び大容量データ記憶装置312からナビゲーション装置200へのナビゲーションデータの送信を含む。サーバ302により提供される別のサービスは、所望のアプリケーションに対する種々のアルゴリズムを使用したナビゲーションデータの処理及びナビゲーション装置200へのこれらの計算の結果の送出を含む。
【0062】
一般に、通信チャネル318は、ナビゲーション装置200とサーバ302とを接続する伝搬媒体又は進路を表す。サーバ302及びナビゲーション装置200の双方は、通信チャネルを介してデータを送信する送信機及び通信チャネルを介して送信されたデータを受信する受信機を含む。
【0063】
通信チャネル318は、特定の通信技術に限定されない。更に、通信チャネル318は、単一の通信技術に限定されない。すなわち、チャネル318は、種々の技術を使用する複数の通信リンクを含んでもよい。例えば、通信チャネル318は、電気通信、光通信、及び電磁通信等のうちの少なくとも1つのためのパスを提供するように構成されることができる。そのため、通信チャネル318は、電気回路、ワイヤ及び同軸ケーブル等の電気導体、光ファイバケーブル、コンバータ、無線周波数(rf)波、大気、空間等のうちの1つ又はそれらの組み合わせを含むが、それらに限定されない。更に、少なくとも1つの様々な実施形態に従えば、通信チャネル318は例えば、ルータ、リピータ、バッファ、送信機及び受信機等の中間装置を含むことができる。
【0064】
図示の構成では、通信チャネル318は、電話及びコンピュータネットワークを含む。更に、通信チャネル318は、無線周波数、マイクロ波周波数、赤外線通信等の無線通信に適応できてもよい。更に、通信チャネル318は衛星通信に適応できる。
【0065】
通信チャネル318を介して送信される通信信号は、所定の通信技術に必要とされるか又は望まれる信号を含むが、それらに限定されない。例えば、信号は、時分割多元接続(TDMA)、周波数分割多元接続(FDMA)、符号分割多元接続(CDMA)、グローバル・システム・フォー・モバイル・コミュニケーションズ(Global System for Mobile Communications)(GSM)等のセルラ通信技術において使用されるように構成されてもよい。デジタル信号及びアナログ信号の双方が通信チャネル318を介して送信できる。これらの信号は、通信技術にとって望ましい変調信号、暗号化信号、及び圧縮信号のうちの少なくとも1つであってもよい。
【0066】
サーバ302は、無線チャネルを介してナビゲーション装置200によりアクセス可能なリモートサーバを含む。サーバ302は、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)、仮想プライベートネットワーク(VPN)等に位置するネットワークサーバを含んでもよい。
サーバ302は、デスクトップ又はラップトップコンピュータ等のパーソナルコンピュータを含んでもよく、通信チャネル318は、パーソナルコンピュータとナビゲーション装置200との間に接続されるケーブルであってもよい。あるいは、パーソナルコンピュータは、ナビゲーション装置200とサーバ302との間に接続されて、サーバ302とナビゲーション装置200との間にインターネット接続を確立してもよい。あるいは、インターネットを介してナビゲーション装置200をサーバ302に接続するために、移動電話又は他のハンドヘルド装置がインターネットへの無線接続を確立してもよい。
【0067】
ナビゲーション装置200は、情報ダウンロードを介してサーバ302から情報を与えられてもよい。情報は、周期的に自動更新されたり、ユーザがナビゲーション装置200をサーバ302に接続する場合に更新されたり、例えば無線移動接続装置及びTCP/IP接続を介してサーバ302とナビゲーション装置200との間に接続がより継続して又は頻繁に確立される場合に更に動的に更新されてもよい。多くの動的計算のために、サーバ302内のプロセッサ304が大量の処理要求を処理するために使用されてもよい。しかし、ナビゲーション装置200のプロセッサ210も同様に、多くの場合においてはサーバ302への接続に関係なく、多くの処理及び計算を処理できる。
【0068】
更にプロセッサ210は、装置200の所在の記録(すなわち、GPSデータ及びタイムスタンプ)をサーバ302に時々アップロードするように構成される。ナビゲーション装置200が装置200をサーバ302に接続する永続的な又は少なくとも一般的に存在する通信チャネル318を有するいくつかの実施形態において、データのアップロードは定期的に、例えば24時間に1回行われる。当業者には他の周期が可能であり、実質的には15分、30分、1時間毎、2時間毎、5時間毎、12時間毎、2日毎、週毎又はそれらの時間の間のあらゆる時間のうちのいずれの周期であってもよいことが理解されるだろう。実際には、そのような実施形態において、プロセッサ210は、ほぼリアルタイムに所在の記録をアップロードするように構成されてもよい。これは、データが実際には送信の間の比較的に短い周期で時々送信されることを必然的に意味してよく、より正確には擬似リアルタイムであると考えられる。そのような擬似リアルタイムの実施形態において、ナビゲーション装置は、メモリ230又はポート234に挿入されたカードの少なくともいずれか一つにGPS座標(GPS fixes)をバッファリングし且つ所定の数が格納された時にそれらを送信するように構成されてもよい。この所定の数は、20、36、100、200又はそれらの間のどのような数であってもよい。所定の数は、メモリ230やポート234のカードのサイズにより部分的に決定されることが当業者には理解されるだろう。
【0069】
他の実施形態において、通常の時は通信チャネル318を有さないプロセッサ210は、通信チャネル318が作成される時に記録をサーバ302にアップロードするように構成されてもよい。例えばこれは、ナビゲーション装置200がユーザのコンピュータに接続される時であってもよい。ここでも、そのような実施形態において、ナビゲーション装置は、メモリ230内又はポート234に挿入されたカードにGPS座標をバッファリングするように構成されてもよい。メモリ230又はポート234に挿入されたカードがGPS座標決定で一杯になった場合、ナビゲーション装置は、最も古いGPS座標を削除するように構成されてもよいため、先入れ先出し(FIFO)バッファと考えられてもよい。
【0070】
説明される実施形態において、所在の記録は、各々が24時間以内のナビゲーション装置200の動きを表す1つ以上のトレースを含む。24時間の各期間はカレンダーの日付と一致するように構成されるが、他の実施形態においては一致する必要はない。
【0071】
一般に、ナビゲーション装置200のユーザは、装置の所在の記録がサーバ302にアップロードされることに対して同意する。同意されない場合、記録はサーバ302にアップロードされない。ナビゲーション装置自体及びナビゲーション装置が接続されるコンピュータの少なくともいずれか一方は、所在の記録のそのような使用に対する同意をユーザに求めるように構成されてもよい。
【0072】
サーバ302は、装置の所在の記録を受信し且つ処理するために大容量データ記憶装置312内にそのレコードを格納するように構成される。従って、時間の経過と共に、大容量データ記憶装置312はデータをアップロードした複数のナビゲーション装置200の所在の記録を蓄積する。
【0073】
大容量データ記憶装置312は地図データを更に含む。そのような地図データは、道路区分の場所、地点情報及び一般に地図で見つけられる他のそのような情報に関する情報を提供する。
【0074】
第1の処理として、サーバ302は、地図データと受信された所在の記録の中に含まれたGPS座標との間のマップマッチング機能を実行するように構成される。そのようなマップマッチングは、いわゆるリアルタイムに、すなわち所在の記録が受信されると実行されてもよく、あるいは所在の記録が後で大容量データ記憶装置312から再度呼び出されて実行されてもよい。
【0075】
マップマッチングの精度を向上するために、所在の記録の前処理は以下のように実行される。各GPSトレース(すなわち、24時間のGPSデータ)は、ナビゲーション装置200の1つの行程を表す1つ以上の移動に分割され、後の処理のために格納される。
【0076】
各移動内で、ナビゲーション装置から受信された精度レポートが十分に高くないGPS座標は廃棄される。従って、いくつかの実施形態において、GPS座標に関連して3つ未満の衛星102からの信号がナビゲーション装置200により受信されていたことを精度レポート示す場合、座標は廃棄されてもよい。更に、座標と座標の間の報告時間が閾値を上回る移動はクリップされる。この前処理段階を通過した各移動は、マップマッチングされるために渡される。
【0077】
図2に示す様に、ナビゲーション装置200はプロセッサ210、入力装置220、表示画面240を含む。入力装置220及び表示画面240は、例えばタッチパネルスクリーンを介して情報(直接入力、メニュー選択など)を入力すること及び情報を表示することとの両方を可能にするために、一体型入力表示装置に統合される。このようなスクリーンは、当業者には周知であるように、例えばタッチ入力LCDスクリーンであってもよい。更に、ナビゲーション装置200は、例えばオーディオ入力/出力装置などの、更なる任意の入力装置220と更なる任意の出力装置240との少なくとも一方を有しても良い。
【0078】
図4A及び図4Bは、ナビゲーション装置200のを示している。図4Aに示すように、ナビゲーション装置200は、一体型入力表示装置290(例えばタッチパネル画面)と図2の他の構成要素(内蔵GPS受信機250、マイクロプロセッサ210、電源、メモリシステム220などを含むがこれに限定されない)を含むユニットであっても良い。
【0079】
ナビゲーション装置200は、アーム292上に備え付けられても良い。このアーム292は、大きな吸着カップ294を用いて、車両のダッシュボード/窓/等に固定されても良い。このアーム292は、ナビゲーション装置200がドッキング可能なドッキングステーションの一例である。
【0080】
図4Bに示すように、ナビゲーション装置200は、例えば、アーム292に対してナビゲーション装置292をスナップ接続することで、ドッキングステーションのアーム292にドッキング若しくは接続することができる。図4Bにおける矢印で示すように、ナビゲーション装置200は、アーム292上で回転可能である。ナビゲーション装置200とドッキングステーションとの間の接続を解除するためには、例えば、ナビゲーション装置200上のボタンを押下すればよい。ナビゲーション装置をドッキングステーションに接続したり外したりするための他の等価で適した構成は当業者に知られている。
【0081】
次に添付の図面の図5を参照すると、メモリリソース230は、機能性ハードウェア構成要素460による実行のためにメモリリソース230からオペレーティングシステム470をロードするため、プロセッサ210により実行されるブートローダプログラム(不図示)を格納し、アプリケーションソフトウェア480が実行可能である環境を提供する。オペレーティングシステム470は、機能性ハードウェア構成要素460を制御し、アプリケーションソフトウェア480と機能性ハードウェア構成要素460との間に常駐する。アプリケーションソフトウェア480は、ナビゲーション装置200の中核機能、例えば地図閲覧、経路計画、ナビゲーション機能及びその他関連する機能などをサポートするGUIを含む動作環境を提供する。
【0082】
使用する際、PND(Portable Navigation Device)200は、地図データによりカバーされる地域内のナビゲート可能な経路を表す地図データをメモリ230又は他の場所に含む。そのようなナビゲート可能な経路600の一例を図6に示す。説明する例において、図6は第2の道路604を介して道路602を地点TCに接続するいわゆる「T字路」と共に地点TAからTBに伸びる道路602を示す。
【0083】
PND200が有用なのは、地図データによりカバーされる地域において使用されるときである。PND200は、その地域内を移動すると、上述したようにGPSシステムから自身の位置を周期的に判定し、その位置を記録する。これをドット606により図6に示す。システム内には元々不正確なところがあり、PND200は、自身の位置がドット606aで例示されるように道路区分602、604外にあることを判定できる。これは、後述するように後の処理で考慮され、当業者には完全に理解されるだろう。
【0084】
図6に示す経路において、PND200は、地点TAから地点TBに向けて移動607をとり、地点TCに向けて道路604に入るためにT字路で左折する。左折するために、移動しているPND200を搭載する車両は灰色のボックスで表されるゾーン608で減速する。このゾーン608は、減速(又は交差点前)ゾーン又は操作前の進路として考えられてもよい。車両は左折し、次にゾーン610(灰色のボックスにより表される)の間で加速する。従って、ゾーン610は、加速(又は交差点後)ゾーン又は操作後の進路として考えられてもよい。
【0085】
従って、図6に示す移動において、PND200が置かれる車両は、道路区分に沿って移動し、曲がり、第2の道路区分に沿って移動する。
【0086】
いくつかの実施形態において、道路区分(線形空間範囲を有する)毎に、区間の平均速度値として提供されてもよいその区分の速度プロファイルと称されるデータが地図データ内に保持される。他の実施形態において、速度プロファイルは、道路区分の長さを考慮して当該道路区分の平均通過時間と等価にモデル化されてもよい。分岐点/交差点/横断歩道が道路網のネットワークモデルにおいて空間範囲を有さないか又はより不明瞭で不自然にみえる空間範囲を有するとすると、交差点操作プロファイルは、平均速度に関して容易に表されず、通過時間又は通過時間の集合により容易に表される。交差点の通過時間を、減速、待機及び加速等をした時に「失われた」ある旅程に沿う道路区分通過時間の合計を補完する、通過時間オフセットとして表せてもよい。
【0087】
通過時間の集合は、通過時間プロファイルとして考えられてもよい。そのような通過時間プロファイルは、所定の間隔で通過時間を提供してもよい。例えば、通過時間プロファイルは1時間間隔で通過時間を提供してもよい。
【0088】
操作に関連した通過時間コストは、車両が交差点を走る際に沿う、一部又は全ての軌道、あるいは重要な軌道の部分集合と関連付けられてもよい。
【0089】
関連する軌道の一例は以下に検討される。図6に示す交差点は比較的に単純である。より複雑な交差点は図7に示され、一般に十字路と呼ばれる。方向転換の制限が考慮されるかどうか、そして許可される運転操作のみが処理されるかどうかは実行時の選択肢である。
【0090】
道路区分A、B、C及びD(A←→Cが優先権を有する)を含む4方向の交差点(すなわち、十字路)の場合、軌道B→C、B→D、B→A、D→A、D→B、D→Cは、通過時間プロファイルの最も明らかな候補である。
【0091】
更に、更なる候補(この例においては右側通行と仮定する)A→B及びC→Dが存在してもよく、左折に追加の時間がかかる可能性があるからである。例えば、交通渋滞中にはそのような操作に更に30秒を要する可能性があると考えられる。
【0092】
そのような情報は、減速ゾーン(例えば、A)に拠る方向転換前の、そして加速ゾーン(例えば、B)に拠る方向転換後の双方2つの道路区分の特性である。方向転換をするのにかかる時間はA、B両方の道路区分の特性であるため、「通過時間コスト」属性をAかBに付けることは、適切に方向転換をモデル化しない。従って、時間は有向対A→Bの属性であることが都合がよい。すなわち、交差点の通過時間は、交差点を通過する経路(及び交通量等の他の要因)に依存する。
【0093】
また、例えば中央分離帯、安全地帯又は反対の運転方向との間の他の種類の分離帯を仮定すると、A→A又はC→C等のUターンの例が範囲に含まれてもよい。
【0094】
最後に、上記に含まれなかった全ての対の残部、すなわちA→C、A→D、B→B、C→A、C→B、D→Dが範囲に含まれてもよい(デフォルト手段により黙示的又は明示的に)。
【0095】
多車線道路、侵入路等を含む複雑な交差点のより複雑な例において、モデルは図8に関連して詳述されるように3つ以上の区分に関連してもよい。図8は、多車線道路を含む4方向の一例を示し、関連する軌道は、多くは交差点内の連結部、すなわちAC、DB、CA及びBDを含み、ここでは潜在的な、付加的な方向転換専用車線又は侵入路を無視する。上述したように、A←→C(簡潔に言うと、A2→C2及びC1→A1)は、優先権を有し且つ右側通行であると仮定される。
【0096】
通過時間プロファイルの最も明らかな候補は以下の通りである。
【0097】
B1→BD→AC→C2
B1→BD→D1
B1→A1
D2→DB→CA→A1
D2→DB→B2
D2→C2
更なる候補は、A2→AC→DB→B2及びC1→CA→BD→D1であってもよく、左折はA←→Cに沿う交通渋滞中の追加の待ち時間により影響を受ける可能性がある。
【0098】
また、A2→AC→DB→CA→A1及びC1→CA→BD→AC→C2、並びにB1→BD→AC→DB→B2及びD2→DB→CA→BD→D1を含むUターンの例が範囲に含まれてもよく、上述したように、左折はA←→Cに沿う交通渋滞中の追加の待ち時間により影響を受ける可能性がある。
【0099】
最後に、上記で含まれなかった以下の全ての対の残部が範囲に含まれてもよい(デフォルト手段で黙示的又は明示的に)。
【0100】
A2→AC→C2
A2→D1
C1→CA→A1
C1→B2
運転者がA2に沿って運転し、B2に曲がりたいことを考慮すると、C1→A1の交通渋滞は、DBにいる間の長い待ち時間の原因になるだろう。同様に、DBでの待ち時間は、D2から接近してくる、A1又はB2が目的地方向の運転者にも起こる可能性がある。本発明の実施形態は、交差点を横断する移動時間を推定する時に考慮されることを許容する。これは、信号で規制される多車線道路の交差点等での待ち時間を含んでもよい。
【0101】
使用する際、道路区分及び交差点を通る経路と関連付けられた速度プロファイルは、位置データ及び特に上述したようにGPSトレースから導出された移動から作成される。説明される実施形態において、そのような位置データはPND及びそのGPS受信機から収集された。しかし、そのように収集される必要はない。
【0102】
特定の交差点を通る通過時間遅延を表す包括的なデータを判定するのに利用可能ないくつかの特殊な方法が存在してもよく、そのような2つの特殊な方法を以下に概略的に説明する。
【0103】
第1の方法は、個別化された通過時間プロファイルを対象とし、種々の交差点の軌道に対する時間の影響を評価するために位置データを解析し、所定の時間間隔で所定の操作に沿う低下した平均速度の影響による通過時間を提供しようとする。
【0104】
この方法は、各々が複数のステップを含む複数のサブタスクに細分されてもよい。第1のサブタスクにおいて、移動は地図データに保持された道路区分間の交差点と関連付けられる。
【0105】
このために、所定の交差点と関連する移動の集合が判定される。これは、以下のステップをその順番又は変更された順番(図10を参照して説明する)で含んでもよい。
【0106】
i. 地図データを使用して所定の交差点との接続性を判定する。この結果、当該交差点に対するサブネットワーク(すなわち、交差点と位相幾何学的に接続された全ての道路区分に関する「共通の境界線」)が得られる。
【0107】
ii. 当該交差点の周囲のバウンディングボックスを使用して処理されている移動内でGPS座標の空間フィルタリングを適用する。バウンディングボックスのサイズは、交差点のサブネットワークの空間範囲に基づいて、あるいはデータ検索のために最適化されたデフォルトの寸法に基づいて又は他の理由で選択されてもよい。すなわち、交差点を通過する移動の一部に対応するGPS座標を判定する―ステップ1000。GPSを使用する実施形態において、GPS座標は所定の時の車両の位置に対応することが当業者には理解されるだろう。
【0108】
iii. GPS座標毎に、交差点のサブネットワークと対応する道路区分において最も近接する位置(該当する場合)を判定することにより、空間フィルタリングされたGPS座標に対してマップマッチングを実行する(すなわち、たとえば606aのGPS座標は最も近接する道路区分602と関連付けられる)。マップマッチングは、より高度なマッチング基準をとってもよく、マッチング基準は、GPS&地図精度の状態、地理的な近さ、GPS速度&地図属性の近似、GPS&道路区分の方向性、隣接するデータ点の間の依存性を含むがこれらに限定されない。これもステップ1000の一部と考えられてもよい。
【0109】
あるいは、通過時間プロファイルの生成は、道路区分に対する速度プロファイルの生成等の他の目的で実行された位置データ処理を利用してもよく、通過時間プロファイルの副産物として、GPSトレース及びGPS移動の少なくともいずれか一方のマップマッチングレイヤが既に提供されていてもよい。
【0110】
所定の交差点に対する更なる位置データ処理ステップは以下を含む(この順番又は変更された順番で)。
【0111】
iv. マップマッチングされたGPS座標に対応する道路区分を横切る進路に関して、空間フィルタリング及びマップマッチングされた移動毎に交差点の軌道を判定する。これはステップ1002として示され、交差点を通る経路に応じて交差点に関連した位置データを分類すると考えられてもよい。
【0112】
v. 交差点を通る軌道に基づいて全ての移動をクラスタリングし、運転操作により移動を分類する(「操作にマッチしたGPS移動」として考えられてもよい)。当該交差点で開始又は終了するGPS移動は本実施形態において廃棄される。これは、ステップ1002の一部として考えられてもよい。
【0113】
vi. 考慮に入れる操作にマッチしたGPS移動の(最小の)長さを判定する。これを達成するために、以下の基準が適用されてもよい。所定の交差点の前(又は後)の十分なGPS座標の範囲は、以下の範囲にわたる。
【0114】
○速度プロファイルが確立される、少なくとも1つの道路区分全体又は複数の接続が可能にされた道路区分
○微調整が行われることを条件として、特定の所定の距離D(約150mとする)
○1つ又は複数の道路区分全体を選択するための道路区分の最小の長さ閾値である距離D。
【0115】
vii. 第1のサブ進路を判定するために各操作にマッチしたGPS移動のコアセグメンテーションを実行する:
○道路区分への接近(approaching road segment)にマッチしたGPS座標を含む操作前の進路。
【0116】
viii. オプションとして、他のサブ進路を更に判定するために各操作にマッチしたGPS移動のより包括的なセグメンテーションを実行する:
○地図データベース中の交差点表現の一部としてモデル化された道路区分にマッチしたGPS座標を含む操作中の進路
及び
○離れていく道路区分にマッチしたGPS座標を含む操作後の進路
の少なくともいずれか一方。これらのステップをステップ1004内に示す。
【0117】
サブ進路の境界において、GPS座標は、操作前の進路と操作中の進路又は操作中の進路と操作後の進路の双方にそれぞれに属してもよい。図7に示した上述のABCDの例等の「単純な」交差点/横断歩道の(一般的な)例において、所定のGPSトレースの操作中の進路は「空」であってもよく、GPS座標は操作前又は操作後の進路に属してもよい。
【0118】
ix. 繰り返しパターンに対応する通常の通過時間プロファイルを確立するために、時間帯毎/曜日毎の別個のタイムスロットのように定めた時間間隔スキームに基づいて操作にマッチしたGPS移動の第2のクラスタリングを適用する。
【0119】
例えば別個のタイムスロットは、例えば第1の時間(例えば、午前9時)と第2の時間(例えば、午前9時59分)との間に起こる各操作にマッチしたGPS移動が同一の時間範囲内に配置されるように、ほぼ1時間の長さの時間範囲に対応してもよい。時間範囲は、1時間以外の長さ、例えば約10分、15分、20分、30分、45分、2時間、6時間、12時間又はそれらの長さの間のあらゆる時間のうちのいずれかであってもよいことが当業者には理解されるだろう。
【0120】
これは、ステップ1006に示され、この例においては所定の長さである所定の期間内の時間を平均するものと考えられる。
【0121】
x. オプションとして、不規則なパターンに対応した異常通過時間プロファイルを確立し正常通過時間プロファイルを上書きするするために、国の祝日や祭典等の日毎や週毎に起こるのではない不規則な時間パターンに基づいて同じ操作にマッチしたGPS移動の第2の並列クラスタリングを適用する。異常通過時間プロファイルを考慮した操作にマッチしたGPS移動は、正常通過時間プロファイルに対して作成された第2のクラスタから除外される。
【0122】
そのような第2の並列クラスタリングにより、交通の流れが国の祝祭日のように「正常」パターンに当てはまらない日に対して交差点の通過時間プロファイルがマッピング可能になる。従って、速度プロファイルが経路計画に後で使用される場合、その日の交通の流れが「正常」である可能性が高いか又は「異常」である可能性が高いかに関わらず、可能性の高い交通の流れをより正確に反映する交差点の通過時間プロファイルを使用できる。
【0123】
xi. 操作にマッチしたGPS移動の第2のクラスタ毎を平均することにより操作前のGPS座標の時間的な挙動を評価する。特に、操作前のGPS座標の平均速度の低下(対応する道路区分の速度プロファイルと比較して)を観察できたかを評価する。
【0124】
○評価が肯定的である場合(すなわち、第2のクラスタにおける速度が道路区分全体の平均速度より遅い場合)、評価した操作と当該時間間隔に対する操作前の時間ペナルティを判定する。これは、対応する道路区分の長さを平均速度比較の絶対差分で除算した値に等しい
○これに対して、評価が否定的である場合(すなわち、第2のクラスタと道路区分の平均速度との間の速度差がない場合)、評価した操作と当該時間間隔に対して操作前の時間ペナルティはゼロとして宣言される(且つ/又は適用不可としてフラグが立てられる)。
【0125】
xii. 同様に、操作後の進路の包括的なセグメンテーションが適用可能である場合、操作にマッチしたGPSトレースの第2のクラスタ毎に平均することにより操作後のデータ点の時間挙動を評価する。
【0126】
○評価が肯定的である場合(すなわち、第2のクラスタにおける速度が道路区分の平均速度より遅い場合)、評価された操作と当該時間間隔とに対する操作後の時間ペナルティを判定する。これは、対応する道路区分の長さを平均速度比較の絶対差分で除算した値に等しい
○これに対して、評価が否定的である場合(すなわち、第2のクラスタにおける速度が道路区分の平均速度以上である場合)、評価された操作と当該時間間隔とに対して操作後の時間ペナルティはゼロとして宣言される(且つ/又は適用不可としてフラグが立てられる)。
【0127】
xiii. あるいは、操作後の進路の包括的なセグメンテーションが適用可能である場合、操作にマッチしたGPS移動の第2のクラスタ毎に平均することにより操作前と操作後のGPS座標の組み合わされた時間挙動を評価する。特に、平均して、何らかの所定の操作前の進路のGPS座標に対する最後(又は最後のいくつか)のタイムスタンプと関連する操作後の進路のGPS座標の最初(又は最初のいくつか)のタイムスタンプとの間の大きな時間差が観察されるかを評価する。
【0128】
○評価が肯定的である場合、もし該当する場合は、(明示的な)交差点内の遅延を含む平均された全部の時間差と等しい、当該評価された操作と時間間隔とに対する操作前後の時間ペナルティを判定する
○これに対して、評価が否定的である場合、当該評価された操作と時間間隔とに対して操作前後の時間ペナルティはゼロと宣言される(且つ/又は適用不可能としてフラグが立てられる)。
【0129】
xiv. 更に又はあるいは、操作中の進路の包括的なセグメンテーションが適用可能である場合、操作にマッチしたGPSトレースの第2のクラスタ毎に平均することにより操作中のGPS座標(存在する場合)の速度挙動を評価する。特に、操作中のデータ点と関連付けられた全ての速度の平均が関連する操作前及び操作後の平均速度より非常に遅いか(対応する道路区分の速度プロファイルと比較し、それにより全ての平均速度が同一の原理に従って判定される)を評価する:
○評価が肯定的である場合、当該評価した操作と時間間隔とに対する操作中の相対時間ペナルティを判定する。これは、操作中の進路の長さを平均速度比較の絶対差分により除算した値に等しい。更に又はあるいは、当該評価した操作と時間間隔とに対する絶対的な操作中の時間ペナルティを判定する。これは、操作中の進路の長さを操作中の進路の平均速度により除算した値に等しい
○これに対して、評価が否定的である場合、当該評価した操作と時間間隔とに対して操作中の時間ペナルティはゼロと宣言される(且つ/又は適用不可としてフラグが立てられる)。
【0130】
所定の交差点に対するGPS座標処理ステップの最後の集合は以下を含む。
【0131】
xv. 操作にマッチしたGPS移動の所定の第2のクラスタと所定の時間間隔とに対して導出された各時間ペナルティの統計的な有意性及び信頼度の少なくともいずれか一方を検査する。すなわち、クラスタリングから導出された平均値は、平均値を生成したデータが所定の品質基準ステップ1008を満たすかを判定するために解析される。
【0132】
○位置データが大まかすぎると検査が示す場合、フォールバック戦略(「ギャップフィリング」と呼ばれてもよい)を適用し、低解像度時間間隔法を適用することにより(当該時間間隔、あるいは同様の又は全ての時間間隔に対して)第2のクラスタリングステップ(及び次の時間操作挙動評価ステップ)を繰り返す。すなわち、時間範囲の時間の長さが1時間であった場合、より多くのGPS移動がより長い時間範囲に入るように、新しいより長い長さ(例えば、3時間の時間ビンが最初に設定されてもよい)にする。位置データが依然として大まかすぎる場合、時間範囲を更に長くしてもよい
・第1のフォールバック応答において、ラッシュアワー対残りの日中時間対夜間等のように、より長い期間にわたる操作にマッチしたGPS移動のより大きなサンプルの利用を一般化する。そのような時間間隔のマージは、道路区分の速度プロファイルに対して観察される交通量パターンに基づいてもよい
・第2のフォールバック応答として(十分なGPS座標の有効範囲及び/又は密度の不足が持続すると仮定する)、速度プロファイルが同様の特性を有する交差点の集合に対して作成されるように、比較及び統一された処理の基礎として交差点の分類を利用する(個々の交差点毎に速度プロファイルを形成しようとするのではない)。このように、同一あるいは同様の特性(道路種別、道路形態、接続された道路区分の速度プロファイル及び都市対非都市の設定等)を有する交差点に対する通過時間プロファイルは、不十分なGPS座標数を有する例におけるギャップフィリングに対して共有されてもよい
・第3のフォールバック応答として、通過時間遅延を判定する第2の特殊な方法は、以下に更に説明するように交差点方向転換分類に対する方法を詳述する
○オプションとして、位置データがより高い粒度を有する可能性があると検査が示す場合、高解像度時間間隔法を適用する(当該時間間隔、あるいは同様の又は全ての時間間隔に対して)ことにより第2のクラスタリングステップ(及び次の時間操作挙動評価ステップ)を繰り返す。
【0133】
xvi. 所定の時間間隔(すなわち、時間範囲)において操作にマッチしたGPS移動の所定のクラスタに対して所定の時間単位で測定した時間オフセット(合計の「時間損失」)を判定する。以下のように、種々の戦略が適用されてもよい。
【0134】
○最も一般的には、操作前の進路のコアセグメンテーションに基づくと、時間オフセットは操作前の時間ペナルティと等しい。交差点での時間損失の殆どは、減速が行われ且つ何らかの列ができる可能性が高い操作前の進路(図6の608)内で起こることが当業者には理解されるだろう
○あるいは、操作中の進路及び操作後の進路(必要に応じて)の少なくとも一方を含む包括的なセグメンテーションに基づくと、時間オフセットは、操作前の時間ペナルティ、操作後の時間ペナルティ、操作中の相対時間ペナルティ(該当する場合)の合計と等しい
○第2の別の例として、操作中の進路及び操作後の進路(必要に応じて)の少なくとも一方を含み且つ交差点内の連結部を除く道路区分に対する速度プロファイルの範囲を更に予想する包括的なセグメンテーションに基づくと、時間オフセットは、操作前の時間ペナルティ、操作後の時間ペナルティ、操作中の絶対時間ペナルティ(該当する場合)の合計と等しい
○第3の別の例として、少なくとも操作後の進路を含む包括的なセグメンテーションに基づくと、時間オフセットは、操作前後の時間ペナルティと等しくてもよい。
【0135】
xvii. 時間帯/曜日の関数、cそして該当する場合は異常時間間隔スキームの関数における時間オフセットに関して交差点の操作毎の時間コストのプロファイルをアセンブルする。
【0136】
方向転換コストプロファイルは、時間オフセットの離散平均又はパラメータ関数としてモデル化される。時間オフセットは、絶対の又は分類(符号化)された値又は時間オフセット関数のパラメータとして指定されてもよい。
【0137】
上記ステップ又はそれ以外に従って生成された通過時間プロファイルのデータセットは、一実施形態において、道路区分への接近→道路区分からの出(departing road segment)の全ての組み合わせを範囲に含む交差点毎の完全な時間依存方向転換コストマトリクス又は重要な方向転換のみ(地図データベースの交差点の全て又は部分集合に対する)を含む縮小されたマトリクスとして提供される。そのようなマトリクスは、データベース、テーブル又はリスト構造で編成されてもよい(道路区分に対する速度プロファイルと共に又は別個に)。それらのマトリクスは、コンテンツファイル、ソフトウェアライブラリとして又はウェブサービスを介して利用可能にされてもよい。通過時間プロファイルのデータセットは、地図データベースコンテンツの必須部分として格納及び管理されてもよく、あるいは補助的なルックアップテーブル等のアドオンデータとして処理されてもよい。
【0138】
上述の実施形態と同等の別の実施形態において、方向転換コストマトリクスのコンテンツは、種々の道路区分への接近に添付される属性集合へ時間オフセットプロファイルを転送することにより再計算(recast)されてもよい。これは、所定の道路区分の方向での特定の道路区分への接近の可能な操作毎に、以下を含む位相時間コストプロファイル属性が添付されることを意味する。
・交差点や横断歩道に対する方向性、及び交差点や横断歩道の地図データ参照(ID)のいずれか一方。
・出て行く道路区分に対応する地図データ参照(ID)。
・時間コストプロファイル。
【0139】
更に又は更なる別の例として、上述したモデル(道路区分への接近の属性の集合である時間コストプロファイル)は、位相的表現(「区分A→区分B」)の実際の操作の意味が地理的/幾何学的表現(「左折」、「+90°に曲がる」及び「北東に向けて曲がる」等)に変換される。従って、各通過時間プロファイルは、定量化された方向転換時の相対角度又は絶対角度、並びに/あるいは分類された相対的又は絶対的な方向転換の意味により記述される。操作に用いるために、そのような地理的や幾何学的な時間コストプロファイル属性は、地図データ参照(ID)を利用しないため、通過時間プロファイルに対する地図データベースモデルを簡略化する。1つのアプリケーションによる対象とされた用途に依存して、この属性モデルは利点(例えば、人間‐機械インタフェースのより直感的な表現)及び欠点(例えば、実行時に経路計画者による解釈を必要とする)の双方を有する。
【0140】
地理的や幾何学的な時間コストプロファイル属性は、視覚特性(可能性として、時間に依存し且つ/又は動的である他の道路又は環境特性と共に)に容易に変換されるという点で安全で効率的なアプリケーションの拡張機能を容易にする。所定の道路又は経路に沿うか又は所定の地域における可能な方向転換操作の範囲に対するカラー符号化アイコンは、例えばスループットレベルの評価のある形を示してもよい。
【0141】
更なる一実施形態において、方向転換コストプロファイルのデータの表し方は、ある道路区分への接近から直線(又はほぼ直線)の通過進路(through-path)に対応する、所定の交差点や横断歩道における主運転方向を考慮に入れる。主運転方向は、所定の時間/日付におけるそれぞれの時間オフセットに関して基準通過時間プロファイルとしての役割をする。すなわち、同一の道路区分への接近を有する当該交差点や横断歩道における残りの操作の時間オフセットプロファイルは、基準時間オフセットに対する差分ペナルティとして表される。その結果として、所定の方向転換及び所定の時間間隔に対する適用可能な差分ペナルティは、負でも正でもよい。すなわち、通過時間は遅延でも利得でも表示してよい(負が時間の遅延を示すか又は利得を示すかは実現する際の選択肢である)。道路区分に対する速度プロファイルが主方向に沿う速度や通過時間(交差点横断操作を含む)を十分に範囲に含むと仮定される場合、実際の基準時間オフセットはアプリケーションによりゼロと仮定されてもよく又は無視されてもよい。差分ペナルティプロファイルは最新の解決策を高め、解決策は時間依存プロファイルを使用しない場合には主方向以外の操作に対する一定のペナルティ又は何らかの分類されたペナルティのパターンを仮定する必要がある。
【0142】
上述の実施形態の一変形例は、所定の交差点での他の何かの操作に対する差分ペナルティプロファイルと当該道路区分への接近とを導出するための基準操作として「時間損失がゼロ」の操作又は「時間損失が最小」の操作を使用することである。「時間損失がゼロ」の操作又は「時間損失が最小」の操作の判定は通過時間プロファイルを生成する(説明したように又は別の方法で行われるように)処理に基づき、この処理は減速せず且つ時間オフセットなしで又は最小の減速及び最小の時間オフセットで操作が自然に継続されることを判定することを可能にする。判定されると、そのような自然な継続は所定の交差点及び道路区分への接近における他の何らかの方向転換に対する差分ペナルティプロファイルを生成する基準となる。本実施形態の変形例において、差分ペナルティは、常に負であり(又は実現する際の選択肢に従って常に正であり)、最速の基準操作又は最小の障害の基準操作と比較した時間遅延を常に示す。
【0143】
組み込まれた解決策(経路指定アプリケーションの道路網地図データベースの一部として管理される通過時間プロファイル)に対して、既存のデータ構造が再利用又は修正されてもよい。
− 事前に生成された方向転換コストマトリクス(特定の又は全ての種別の交差点や横断歩道に対する)を使用する経路指定アプリケーションの場合、静的な方向転換コストデータは、時間依存方向転換コストにより補完や置換されてもよい。
− 位相時間コストプロファイル属性の同等の表現を考慮すると、それらの属性は、経路指定アプリケーションが方向転換コストデータにアクセスし且つ処理する方法に対応してもしなくてもよい。
− 地理的や幾何学的な時間コストプロファイル属性は、一般に経路指定アプリケーションがアクセス可能であるようにする必要がある属性の新しい集合である。
− 差分ペナルティプロファイルは、実行時の計算の複雑さを最小限にするTomTom IQ Routes等の時間の影響を受ける経路指定エンジンの現在の手法を対象とする。交差点/横断歩道へ入る道路区分と関連付けられた速度プロファイルは、当該交差点/横断歩道への接近において可能な所定の操作に対する差分ペナルティを考慮する追加的な操作の影響を受ける通過時間プロファイルの集合により補完される。上述の図7の4方向の交差点のA/B/C/Dの例を参照すると、Aから接近する場合、道路区分Aの速度プロファイルは2つの更なる通過時間プロファイルにより補完される。一方のプロファイルはA→Bの方向転換操作に対応し、他方のプロファイルはA→Dの方向転換操作に対応する(各プロファイルは所定の時間や日付に対する速度と差分ペナルティとの組合せプロファイルに関す。)。基準操作である主方向A→Cの場合、差分ペナルティはゼロである(ゼロと仮定される)。
【0144】
通過時間遅延を判定する第2の方法について図9を参照して概略的に示す。図9は、方向転換の種類の分類に基づく一般的な通過時間コスト関数に特化している。
【0145】
あらゆる1つの移動は、方向転換が後続する多くのそのような道路区分のトラバーサル(traversal)から構成される。上述したように、各方向転換は、操作前、操作中及び操作後の部分として考えられる。しかし、図9を参照すると、SからEまでの移動は、A及びCにおける交差点と共に道路区分900(SA)、902(AC)及び904(CE)を含む。
【0146】
従って、その移動の特定の地点に到着するための時間コストとして考えられる合計の移動時間は、前の交差点からの道路区分を運転するのに必要な時間+方向転換コスト(その道路区分に到着するのに必要な時間;すなわち先の道路からの通過時間)の合計により与えられる。図9を考慮すると、交差点iから交差点jまでの運転コストをDi_jで示し、交差点i及びjの間の道路区分と交差点j及びkの間の道路区分との間を移動するための方向転換コストをTcij_jkで示す。
【0147】
この場合、ソースノードSからグラフ中の各ノードに到着するためのコストは以下の通りである。
【0148】
CS=0
CA=DS_A
CB=DS_A+TcSA_AB+DA_B
CC=DS_A+TcSA_AC+DA_C
CD=DS_A+TcSA_AC+DA_C+TcAC_CD+DC_D
CE=DS_A+TcSA_AC+DA_C+TcAC_CE+DC_E (式1)
道路区分に沿う運転時間は、線の長さと運転速度との間の比により与えられる。例えばDS_A=lSA/vSAである。長さは一般に一定であり、速度は処理されている位置データ、例えばGPS座標(すなわち、車両の位置)から測定される。比較すると、方向転換は地図表現において厳密であり、その一方で上述したように方向転換時間は実際の運転においてある距離にわたり分布し且つ複数の道路区分にわたり分布する可能性が高いため、方向転換コストはより非決定論的である。例えば方向転換時間は、交差点における時間(交差点内の時間)と共に操作前のゾーン及び操作後のゾーンにおける時間により構成される。
【0149】
これにより、交差点遅延を推定するのは困難になり、その値は同様の状況において異なる可能性がある。この点に関して、第2の方法である統計的方法が使用され、種々の方向転換コストは所定のカテゴリに分類され、交差点遅延の平均時間はカテゴリ毎に推定される。
【0150】
道路は、測定された速度(平均又は速度プロファイル)、道路の形状(高速道路、多車線道路、非分離道路等)を説明する道路形態又は道路網に対する道路の重要度のような属性を有する。交差点が2つの道路間のリンクとして考えられてもよいことを考慮すると、これらの属性のどのような組合せも交差点のカテゴリを規定できる。存在する入力データが多いほど、考慮されるカテゴリは多く、推定される通過時間はより正確である。しかし、カテゴリの数が多すぎると、冗長性がもたらされるという欠点がある。精度と過度な複雑さとの間の均衡がとられるだろう。
【0151】
方向転換コスト(図7に関連して上述したように交差点を通る経路に割り当てられる時間)をグループ化するいくつかの方法がある。
【0152】
例えば道路区分への入りと出との間の角度差を使用できてもよい。そのような一実施形態において、複数のセクタ(説明される実施形態においては8個であるが、4個、16個、32個等の他のどんな数であってもよい)が作成され、交差点をカテゴリに分類するために交差点における道路区分間の角度差が使用される。例えば現在の実施形態において、0〜44°はカテゴリ0であり、45°〜89°はカテゴリ1であり、90°〜134°はカテゴリ2であり、135°〜179°はカテゴリ3であり、180°〜224°はカテゴリ4であり、225°〜269°はカテゴリ5であり、270°〜314°はカテゴリ6であり、315°〜359°はカテゴリ7である。従って、各セクタは方向転換コストカテゴリになる。
【0153】
他の実施形態において、更に又はあるいは、交差点に対する入りと出の道路区分の道路の形態、種類又は重要度(道路分類)を使用できてもよい。
【0154】
他の実施形態において、更に又はあるいは、交差点に対する進入路区分と分岐路区分との間の運転速度の差分を使用できてもよい。この基準は、先の基準と部分的に重なる可能性があり、冗長性をもたらす可能性がある。
【0155】
道路網の構造が国毎に非常に異なる可能性があることを考慮すると、カテゴリは地図別又は国別であってもよい。
【0156】
各移動は、式1に類似する式により表されてもよい。従って、位置データから収集されるGPS移動は、そのような式により各移動を表すために処理される。図11を参照すると、第1のステップは、そのような式の集合を生成するために位置データを処理することである。従って、方向転換コストが未知の変数である一次方程式の集合が生成され、各道路区分の移動時間は区分速度プロファイル(地図データから取得されてもよく又は位置データから生成されてもよい)及び道路の長さから推定される。合計の移動時間は、開始時間と終了時間との間の差分により与えられる。
【0157】
収集された位置データを処理することにより、大量のGPS移動が解析可能になり、式の数は未知数の数を上回ることを意味する。結果として得られる線形系は、最小二乗平均で解かれる。これは、予測通過時間と実際の通過時間(GPS移動から既知である)との間の誤差を最小限にする方向転換コストの集合を見つけるだろうことを意味する。
【0158】
コスト構造は、運転コスト(すなわち、道路区分を運転する時間)及び方向転換コスト(すなわち、交差点における時間損失)から構成される。合計の移動コストSは、
【0159】
【0160】
により与えられる。式中、Diは道路に属する各道路の運転時間であり、Tcjは経路に沿う方向転換コスト(時間で表される)である。測定速度は正確であると仮定され、方法は方向転換コストによりその推定を最適化しようとする。
【0161】
方法は、コストモデルに規定された方向転換の種類がN個存在すると仮定する。上記説明を参照すると、道路区分への入りと出との間の角度の関係に関連して8つのカテゴリを使用した一実施形態においてはN=8である。方向転換の種類をTc1〜TcNにより示す場合、経路番号kに対して
【0162】
【0163】
を得るだろう。式中、
【0164】
【0165】
は経路に沿う運転時間であり、
【0166】
【0167】
は経路kの合計の方向転換コストにおける方向転換の各種類の頻度である。
【0168】
例えばN=8である本発明の実施形態において、
【0169】
【0170】
はまっすぐ運転した回数を示す、
【0171】
【0172】
は45度の右折を行った回数を示す。
【0173】
k=1,...,Lからいくつかの経路を考慮する場合、以下の線形系が得られる。
【0174】
【0175】
【0176】
を定義すると、線形系は以下のような短縮形式で書き換えられる。
【0177】
Ax=b
上述したように、経路数Lは未知の方向転換コスト変数の数よりはるかに大きい、すなわち、L>>Nであり、そうではあるが正確な解は存在しない。
【0178】
上記で提示された線形系は、最小二乗法x+=A+bで解かれる。式中、A+はムーアペンローズ疑似逆行列である。方向転換コストベクトルx+は、所定の地図と組み合わせて経路制御により使用される最適な方向転換コスト値を提供する。
【0179】
ムーアペンローズ疑似逆行列は、誤差ベクトルの第2のノルムの最小値を与える未知の方向転換コストに対する値の集合を計算するのを支援する。これは、
【0180】
【0181】
であることを意味する。
【0182】
これは、計算された経路に対する正確な推定時間を生成する方向転換コストの集合を計算することはできないが、グローバル推定誤差を最小限にする最適な値の集合を得ることを意味する。従って、一次方程式の集合に対する近似解を導出するために数学的方法が使用されてきた(ステップ1102)。
【0183】
誤差の第2のノルムを最小限にするから、疑似逆行列の方法は最小二乗法である。
【0184】
従って、この第2の方法は、例えば所定の角度関係を有する交差点を見いだせる実施形態において、どの1つのカテゴリにおいても方向転換の平均方向転換コストを判定する。
【0185】
最後にステップ1010及び1104において、更なる地図データが作成され、この地図データにおいて、計算された特性を有するどの交差点に対する通過時間もその交差点と関連付けられる。そのような関連付けは、明示的であってもよく(例えば、地図データの一部等としてルックアップテーブル形式に通過時間又は通過時間の集合を提供する)、あるいは通過時間又は通過時間の集合が推定される方法論を規定することにより(例えば、通過時間が計算されることを可能にする基本時間に対するオフセットを提供することにより)行われてもよい。
【0186】
GPSデータという用語は、例えば図1に関連して説明したようなGPS全地球測位システムから導出された測位データを参照するために使用されてきたことが当業者には理解されるだろう。本明細書で説明した方法と類似した方法で他の測位データを処理できる。従って、GPSデータという用語は、測位データという語句で置き換えられてもよい。そのような測位データは、例えば移動電話動作から導出された位置データ、料金所で受信したデータ、道路に埋設された誘導ループから取得したデータ、ナンバープレート認識システムから取得したデータ、自動車間通信から取得したデータ、周囲の移動オブジェクト及び静止オブジェクトを観察し且つ相対測位をサポートする搭載型センサ(例えば、レーザスキャナ)から取得したデータ、あるいは他のあらゆる適切なデータから導出される。
【0187】
本明細書で説明した実施形態はソフトウェアにより特定の機能性を実現するが、その機能性はハードウェアでのみ(例えば、1つ以上のASIC(特定用途向け集積回路)を使用することにより)又は実際にはハードウェアとソフトウェアとの組合せにより同様に実現可能であることが当業者には十分に理解されるだろう。従って、本発明の範囲は、ソフトウェアで実現されることにのみ限定されるものとして解釈されるべきではない。
【0188】
尚、最後に、添付の請求の範囲は本明細書で説明した特徴の特定の組合せを示すが、本発明の範囲は、以下に請求される特定の組合せに限定されず、特定の組合せが添付する請求の範囲に特に列挙されているか否かに関係なく、本明細書で開示された特徴又は実施形態のいかなる組合せも含む。
【特許請求の範囲】
【請求項1】
ある期間にわたり少なくとも1台の車両の位置から導出された位置データから地図データを作成するコンピュータを使用した方法であり、前記地図データが地図によりカバーされた地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分を含み且つ前記地図データが前記ナビゲート可能な経路における交差点を表すナビゲート可能な区分間の交差点を更に含む方法であって、処理回路を用いて
i. 前記位置データを処理するステップと、
ii. 前記地図データの前記交差点の少なくとも一部に対する通過時間又は通過時間の集合を前記位置データの前記処理から計算するステップと、
iii. 前記交差点の少なくとも一部に対して、前記計算が行われた前記交差点と関連付けられた前記計算された通過時間又は通過時間の集合を含む更なる地図データを生成するステップと、
を実行する方法。
【請求項2】
前記地図データ内の交差点に関連した分類スキームが生成され、前記位置データの前記処理の結果は前記分類スキーム内に格納されることを特徴とする請求項1記載の方法。
【請求項3】
前記分類スキームは、
前記交差点を通る経路、
前記交差点における前記道路区分(入りと出の少なくともいずれか一方)の種別、種類又は重要度、
交差点における道路区分の角度、
信号機の存在、
前記区分への前記入りと前記出の間の運転速度の差分、
前記道路区分の前記入り及び前記出のいずれか一方の前記速度範囲、
の少なくとも1つを含むことを特徴とする請求項2記載の方法。
【請求項4】
前記位置データは、交差点を通過した車両の移動の一部に対応する位置データを判定するために解析され、その判定は前記位置データ内の車両の位置が、
前記交差点の所定の距離、
前記交差点の所定の時間、
車両カテゴリの定義済みの種別、
定義済みの移動方向又は進行方向、
の少なくとも1つの範囲内にあるかどうかを判定することにより行われることを特徴とする請求項1から3のいずれか1項に記載の方法。
【請求項5】
交差点を通過した車両の移動の一部に関連すると判定されたデータは、前記車両が前記交差点を通過するのにかかった前記時間を判定するために解析され、
交差点前のゾーンにおいて前記交差点に接近するのにかかった前記時間、
交差点内のゾーンにおいて前記交差点でかかった前記時間、
及び交差点後のゾーンにおいて前記交差点の後にかかった前記時間、
のうちの1つ以上を判定するために更に解析されることを特徴とする請求項4記載の方法。
【請求項6】
データはいずれか1つの交差点に対して平均され、前記データは所定の長さの所定の期間内に平均されることを特徴とする請求項4又は5記載の方法。
【請求項7】
前記平均時間は、前記平均値を生成した前記データが所定の品質基準を満たすかどうかを判定するために解析され、前記平均時間が前記所定の品質基準を満たさない場合に更なる分類スキームを適用することを特徴とする請求項6記載の方法。
【請求項8】
式の集合を、前記位置データ内の車両移動データから判定し、前記式の既知のパラメータが道路区分の移動時間であり且つ未知のパラメータが交差点の通過時間であることを特徴とする請求項1から3のいずれか1項に記載の方法。
【請求項9】
前記式に対する近似解は、最小二乗法を使用して誤差を最小限にすることを含む数学的近似を使用して判定されることを特徴とする請求項8記載の方法。
【請求項10】
地図によりカバーされる地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分、並びに前記地図によりカバーされる前記ナビゲート可能な区分間の交差点を表す交差点を含む地図データを作成するように構成された装置であって、ある期間にわたり少なくとも1台の車両の前記位置から導出された位置データを処理するように構成された処理回路を含み、前記処理回路は:
i. 前記位置データを処理し、
ii. 前記地図データの前記交差点の少なくとも一部に対する通過時間又は通過時間の集合を前記位置データの前記処理から計算し、
iii. 前記交差点の少なくとも一部に対して前記計算が行われた前記交差点と関連付けられた前記計算された通過時間又は通過時間の集合を含む更なる地図データを生成する、
ようにプログラムされる装置。
【請求項11】
地図によりカバーされた地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分、並びに前記地図によりカバーされた前記ナビゲート可能な区分間の交差点を表す交差点を含む地図データであって、前記交差点の少なくとも一部は請求項1から9のいずれか1項に記載の方法を使用して位置データを平均することにより導出された関連する通過時間又は通過時間の集合を有する地図データ。
【請求項12】
地図によりカバーされる地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分並びに前記地図によりカバーされる前記ナビゲート可能な区分間の交差点を表す交差点とを含む地図データと相関して、クラスタリング(又は交差点の種類)に基づいて通過時間の最適な推定を可能にする地図パラメータの集合。
【請求項13】
次のうちいずれか1つを含むコンピュータにより読み取り可能な記録媒体。
i. コンピュータにより読み出された時に請求項1から9のいずれか1項に記載の方法を前記コンピュータに実行させる命令と、
ii. コンピュータにより読み出された時に請求項10記載の装置と同様に前記コンピュータに実行させる命令と、
iii. 請求項11記載の地図データ、
【請求項1】
ある期間にわたり少なくとも1台の車両の位置から導出された位置データから地図データを作成するコンピュータを使用した方法であり、前記地図データが地図によりカバーされた地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分を含み且つ前記地図データが前記ナビゲート可能な経路における交差点を表すナビゲート可能な区分間の交差点を更に含む方法であって、処理回路を用いて
i. 前記位置データを処理するステップと、
ii. 前記地図データの前記交差点の少なくとも一部に対する通過時間又は通過時間の集合を前記位置データの前記処理から計算するステップと、
iii. 前記交差点の少なくとも一部に対して、前記計算が行われた前記交差点と関連付けられた前記計算された通過時間又は通過時間の集合を含む更なる地図データを生成するステップと、
を実行する方法。
【請求項2】
前記地図データ内の交差点に関連した分類スキームが生成され、前記位置データの前記処理の結果は前記分類スキーム内に格納されることを特徴とする請求項1記載の方法。
【請求項3】
前記分類スキームは、
前記交差点を通る経路、
前記交差点における前記道路区分(入りと出の少なくともいずれか一方)の種別、種類又は重要度、
交差点における道路区分の角度、
信号機の存在、
前記区分への前記入りと前記出の間の運転速度の差分、
前記道路区分の前記入り及び前記出のいずれか一方の前記速度範囲、
の少なくとも1つを含むことを特徴とする請求項2記載の方法。
【請求項4】
前記位置データは、交差点を通過した車両の移動の一部に対応する位置データを判定するために解析され、その判定は前記位置データ内の車両の位置が、
前記交差点の所定の距離、
前記交差点の所定の時間、
車両カテゴリの定義済みの種別、
定義済みの移動方向又は進行方向、
の少なくとも1つの範囲内にあるかどうかを判定することにより行われることを特徴とする請求項1から3のいずれか1項に記載の方法。
【請求項5】
交差点を通過した車両の移動の一部に関連すると判定されたデータは、前記車両が前記交差点を通過するのにかかった前記時間を判定するために解析され、
交差点前のゾーンにおいて前記交差点に接近するのにかかった前記時間、
交差点内のゾーンにおいて前記交差点でかかった前記時間、
及び交差点後のゾーンにおいて前記交差点の後にかかった前記時間、
のうちの1つ以上を判定するために更に解析されることを特徴とする請求項4記載の方法。
【請求項6】
データはいずれか1つの交差点に対して平均され、前記データは所定の長さの所定の期間内に平均されることを特徴とする請求項4又は5記載の方法。
【請求項7】
前記平均時間は、前記平均値を生成した前記データが所定の品質基準を満たすかどうかを判定するために解析され、前記平均時間が前記所定の品質基準を満たさない場合に更なる分類スキームを適用することを特徴とする請求項6記載の方法。
【請求項8】
式の集合を、前記位置データ内の車両移動データから判定し、前記式の既知のパラメータが道路区分の移動時間であり且つ未知のパラメータが交差点の通過時間であることを特徴とする請求項1から3のいずれか1項に記載の方法。
【請求項9】
前記式に対する近似解は、最小二乗法を使用して誤差を最小限にすることを含む数学的近似を使用して判定されることを特徴とする請求項8記載の方法。
【請求項10】
地図によりカバーされる地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分、並びに前記地図によりカバーされる前記ナビゲート可能な区分間の交差点を表す交差点を含む地図データを作成するように構成された装置であって、ある期間にわたり少なくとも1台の車両の前記位置から導出された位置データを処理するように構成された処理回路を含み、前記処理回路は:
i. 前記位置データを処理し、
ii. 前記地図データの前記交差点の少なくとも一部に対する通過時間又は通過時間の集合を前記位置データの前記処理から計算し、
iii. 前記交差点の少なくとも一部に対して前記計算が行われた前記交差点と関連付けられた前記計算された通過時間又は通過時間の集合を含む更なる地図データを生成する、
ようにプログラムされる装置。
【請求項11】
地図によりカバーされた地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分、並びに前記地図によりカバーされた前記ナビゲート可能な区分間の交差点を表す交差点を含む地図データであって、前記交差点の少なくとも一部は請求項1から9のいずれか1項に記載の方法を使用して位置データを平均することにより導出された関連する通過時間又は通過時間の集合を有する地図データ。
【請求項12】
地図によりカバーされる地域におけるナビゲート可能な経路の区分を表す複数のナビゲート可能な区分並びに前記地図によりカバーされる前記ナビゲート可能な区分間の交差点を表す交差点とを含む地図データと相関して、クラスタリング(又は交差点の種類)に基づいて通過時間の最適な推定を可能にする地図パラメータの集合。
【請求項13】
次のうちいずれか1つを含むコンピュータにより読み取り可能な記録媒体。
i. コンピュータにより読み出された時に請求項1から9のいずれか1項に記載の方法を前記コンピュータに実行させる命令と、
ii. コンピュータにより読み出された時に請求項10記載の装置と同様に前記コンピュータに実行させる命令と、
iii. 請求項11記載の地図データ、
【図1】
【図2】
【図3】
【図4A】
【図4B】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4A】
【図4B】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公表番号】特表2012−510647(P2012−510647A)
【公表日】平成24年5月10日(2012.5.10)
【国際特許分類】
【出願番号】特願2011−538916(P2011−538916)
【出願日】平成21年10月12日(2009.10.12)
【国際出願番号】PCT/EP2009/063261
【国際公開番号】WO2010/063508
【国際公開日】平成22年6月10日(2010.6.10)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Bluetooth
2.GSM
【出願人】(307043223)トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【出願人】(509097563)テレ アトラス ベスローテン フエンノートシャップ (23)
【氏名又は名称原語表記】Tele Atlas B.V.
【Fターム(参考)】
【公表日】平成24年5月10日(2012.5.10)
【国際特許分類】
【出願日】平成21年10月12日(2009.10.12)
【国際出願番号】PCT/EP2009/063261
【国際公開番号】WO2010/063508
【国際公開日】平成22年6月10日(2010.6.10)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Bluetooth
2.GSM
【出願人】(307043223)トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【出願人】(509097563)テレ アトラス ベスローテン フエンノートシャップ (23)
【氏名又は名称原語表記】Tele Atlas B.V.
【Fターム(参考)】
[ Back to top ]