オブジェクトの将来の動きを予測するための装置および方法
車輌等のオブジェクトの将来の動きを予測するための装置を提供する。ＧＰＳレシーバ（６）等の場所および時刻決定システムは、車輌の地理的な場所および現在の時刻を決定し、プログラムメモリ（２）を有するコンピュータ（１）等のプロセッサにこれを提供する。プロセッサは、定期的に場所および時刻を記録し、車輌の観察記録を生成する。プロセッサ（１，２）は、記録に含まれる以前に記録した観察と、最近の観察にかかるシーケンスとを比較し、一致するシーケンスを検出する。一致するシーケンスとは、所定の最小距離にわたって一致を示す行路区分である。プロセッサ（１，２）は、一致するシーケンスに続くいくつかの観察を検索し、これらから例えば車輌の採りそうな将来のルートや目的地等の将来の動きを予測する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば車輌等のオブジェクトの将来の動きを予測するための装置および方法に関する。また、本発明は、コンピュータを制御して、当該方法を実行させるプログラム、当該プログラムを伝える搬送媒体、データネットワーク等の通信路を介した当該プログラムの伝送、および当該プログラムがプログラムされたコンピュータに関する。
【背景技術】
【０００２】
Marmasse and Schmandt著（非特許文献１）は、車輌またはユーザが頻繁にしばらく静止する場所を記録することにより、よく訪れる場所を学習するためのシステムを開示する。ユーザは当該場所を命名するように促され、よってそれを予測のための候補とする。また、学習段階があり、そこでは使用する行路モデルには、開発者がルートとして分類した試験的行路があてはめられる。この段階は、ルートの試験的走行を特定のモデルと関連付ける工程を含むため、ユーザによる多くの介入を要し、そのため、自動システムに適さない。各ルートのための学習データを用いて、例えばベイズ分類器、ヒストグラムモデリングおよび隠れマルコフモデル等の様々なモデルを学習する。
【０００３】
US 2002/0161517 A1（特許文献１）は、目的地を予測するためのシステムを開示する。当該システムは以下を含む。（ａ）ユーザが過去に入力したそれらの目的地、（ｂ）道路地図データベース、（ｃ）現在の行路の最近の履歴、および（ｄ）道路地図データベースに対し、過去の行路を一致させ、走行情報データベースを形成すること。当該目的地が一度特定されれば、後は目的地に使用されるルートを記録し始めるだけである。従って、それは一般に、それが使用される前に目的地を特定するユーザ介入を必要とする。システムが、車輌のエンジンを一様に停止する位置を検出し、そしてそれを目的地ポイントとして記録できることが提案されている。その後、ユーザが目的地としてそのポイントを選択すれば、システムはルートを学習し、自動的にその目的地を予測するようになる。しかしながら、ユーザは、まだいくつかの段階において手動で目的地としてそのポイントを選択しなければならない。
【０００４】
EP0967460 A1（特許文献２）は、通勤ルート、すなわち、運転手が最も頻繁に走行するたった１つのルートを学習するためのシステムを開示する。当該システムにおいては、通勤ルートが生成される間、ユーザが時刻窓に入力することを必要とするか、または、初期時刻設定を使用する。そして、直前に使用したルートを保存するか、出自が未定義の合成ルートを保存するか、または当該時刻窓の間に横断した回数を、各道路区分について、地図データベースを用いて計数し、最も頻繁に走行した道路区分を通勤ルートとして用いるかして、通勤ルートを推定しようと試みる。
【０００５】
【特許文献１】米国特許出願公開第２００２／０１６１５１７号明細書
【特許文献２】欧州特許出願公開第０９６７４６０号明細書
【非特許文献１】マーマッセとシュマント（Marmasse and Schmandt）著「ユーザセンタードロケーションモデル（A User-centred Location Model）」パーソナルおよびユビキタス・コンピューティング ２００２ ６巻，ロンドン・シュプリンガー出版株式会社，ｐ３１８−３２１
【発明の開示】
【発明が解決しようとする課題】
【０００６】
非特許文献１のよく訪れる場所を学習するためのシステムには、学習段階がある。この段階は、ルートの試験的走行を特定のモデルと関連付ける工程を含むため、ユーザによる多くの介入を要し、そのため、自動システムに適さない。
【０００７】
特許文献１の目的地を予測するためのシステムにおいて、ユーザは、まだいくつかの段階において手動で目的地としてそのポイントを選択しなければならない。
【０００８】
特許文献２の最も頻繁に走行するたった１つのルートを学習するためのシステムにおいて、通勤ルートが生成される間、ユーザが時刻窓に入力すること等を必要とする。
【課題を解決するための手段】
【０００９】
本発明の第１の態様により、添付された請求項１において定義される装置を提供する。
【００１０】
本発明の他の態様および実施の形態は、添付された他の請求項において定義される。
【００１１】
このようにして、オブジェクトの観察シーケンスを記録し、保持し、または保存したシーケンスと最近のシーケンスとの一致をとることで、オブジェクトの将来の動きを予測可能にする情報を導出するように構成することができる。一致をとる工程は、少なくとも最も一般化した形式においては、２次元のデータにおいて１次元の一致をとる操作と表現することができる。例えば前述の従来のシステムは、観察記録を保持せず、当該一致を実行しない。従って、本願の手法は、オブジェクトの将来の動きのより正確な予測を可能にする。追加データを各観察に付随して保存し、より様々な予測をしてもよい。例えば、当該予測は、単なるオブジェクトの将来の動きまたは場所の予測を越えて拡大してもよい。
【発明を実施するための最良の形態】
【００１２】
一例として添付図面を参照して、本発明をさらに説明する。
【００１３】
下記は、その意味の説明付きの、以下に使用される用語の用語解説である。
【００１４】
一連の観察により示される動作（motion）中の休止は、観察により示される場所があまり変化しない期間である。位置決めシステムの誤差特性により引き起こされるわずかなずれがあってもよい。また、抑止された場合または位置決めシステムの電源が切れている場合、観察が全くなくてもよい。
【００１５】
外部の位置は、外部の座標系において、あるオブジェクトがどこで検出されるか、またはある事象がどこで起こるかを記述するのに使用される。高度のあるなしにかかわらず、ユニバーサル横メルカトル図法（Universal Transverse Mercator（ＵＴＭ））等の地図投影法による格子点により、世界測地標準１９８４（World Geodetic Standard 1984（ＷＧＳ８４））等のデータの緯度および経度により、またはＷＧＳ８４地球中心・地球固定直交座標系（Earth Centred Earth Fixed（ＥＣＥＦ））等の直交座標系により、それらを示せばよい。
【００１６】
ＧＰＳは、米国全地球測位システム（United States Global Positioning System）であり、良好な信号条件下でアンテナ位置を数メートル内に検出可能とするいくつかの衛星によるナビゲーションシステムの１つである。また、１マイクロ秒より高精度で時間情報を提供する。
【００１７】
ＧＰＳ時刻は、協定世界時（Universal Time Coordinated(ＵＴＣ)）にしたがう絶対時刻標準であり、地球の自転に基づく観測時刻標準の１つである。ＧＰＳ時刻は、１マイクロ秒以下のＵＴＣとの誤差を有するが、２００ｎｓよりよい値になるように較正される。ＧＰＳ時刻は、太陽の周りを回る地球の公転周期に適合（うるう秒適合）しないので、わずかな整数秒を加算するＵＴＣとずれる。ＵＴＣ、ＧＰＳ時刻が基準の秒数を取得する調整されない原子による時刻尺度を、ＴＡＩ（国際原子時）という。従って、ＧＰＳ時刻を引いたＴＡＩは、一定の整数秒にとても近く、それは、ＧＰＳ時刻が１９８０年に始まったとき、ＴＡＩとＵＴＣの間において、１９秒の時刻ずれがあった。
【００１８】
行路は、その行路の端を生成する２つの重要な場所の間の観察シーケンスである。このシステムにおいて、行路を重要な休止の間の観察シーケンスと定義する。休止が重要であるとみなされるか否かは、使用する特定のアルゴリズムおよびパラメータにより定義されるが、一般には、比較的長い動作にかかる期間における比較的短い休止を除外するようにパラメータを設定する。適切な設定により、途中で食事をするための１時間の休止のある３時間の運転は、ただ１つの行路とみなされる一方、他方においては１５分間の買い物のための１５分の移動は、その後の１５分の帰宅行路にかかる１５分間の外出とで、２つ別々の行路とみなされる。
【００１９】
事象の場所は、使用する座標系において示される位置である。例えば、浮動小数点数値として示されるＷＧＳ８４データにおいて、緯度、経度、高度を使用する。高度の使用は任意であるが、ある場合ソフトウェアの様々な特性を強化するために使用され得る。
【００２０】
観察は、オブジェクトの場所およびオブジェクトがその場所で検出されたときの時刻の記録である。
【００２１】
観察配列は、配列に保存される観察の記録のシーケンスである
【００２２】
観察索引は、観察配列の要素を特定する整数値である。
【００２３】
ポイントは、特に別に選択された観察索引である。かかる観察の場所は、ディスプレイ画面上の特定の画素に位置することが分かっている場所であるか、または、所与の場所もしくは時刻に対する近接性といった他の基準を用いて選択される。多数のポイントは同じ画素に配置されてもよい。だが、データベースのすべての場所を、ポイントとして示さずともよく、例えば、昨年取得された観察だけを表示すればよい。ユーザはマウス、カーソルキー、または他の入力手段を使用してポイントを選択することができ、ソフトウェアは、選択されたポイントに対応した場所を判別することができる。
【００２４】
ポイントセットは、ポイントの順番および重複に意味を持たないポイントの集まりである。なお、これがより効率的に処理できるなら、それらは昇順にソートし、重複を解消してもよい。
【００２５】
ポイントリストには、それ自身の明確に定めた順番があり、重複にも意味を持つ場合がある。
【００２６】
ＷＧＳ８４は、１９８４年の世界測地系であり、ＧＰＳにより使用される主要な座標系である。それは、座標系の原点が地球の質量中心に近く（数メートル内）なるように、地球の周りのステーション（局）の座標を定める直線座標系である。従って、特にＧＰＳ等の衛星を利用したシステムにとって有用である。当該座標系は、地心座標系（Earth Centred Earth Fixed(ECEF)）という。地質断層ラインに沿っての動き等の広範囲にわたる地殻変動があった場合、局の座標は調整され、座標系全体において不連続を解消することができる。ｚ軸は国際地球自転サービス（International Earth Rotation Service）により定義される地球の自転軸に合わせられ、ｘおよびｙ軸はグリニッジ子午線に近い、採用される子午線を参照することにより定義される。また、座標もＷＧＳ８４データにおける緯度、経度および高度で示すことを可能にする、関連楕円体も存在する。
【００２７】
図１は、自動車等の車輌において組み込まれるＲＯＭ、フラッシュメモリ、ハードディスクドライブ、および／または光学ディスクドライブ等のプログラムメモリ２を有するコンピュータ１の形の装置を示す。しかしながら、本発明の実施形態は、車輌における使用に限定されず、他のオブジェクトに取り付けられてもよいし、組み込まれてもよい。例えばこのような装置は、例えば地理的な場所および現在の時刻についての情報を受信するタイプの携帯電話に組み込まれてもよい。
【００２８】
車輌は車輌の電子装置３を備え、それは車載の多数のシステムを監視し、制御する。従って、コンピュータ１は、以下に記述される車輌の現況に関する複数の観点による情報を受信することができる。
【００２９】
車輌は、さらにＧＰＳレシーバ４を備え、アンテナ５を介してＧＰＳより受信する信号から車輌の位置および現在の時刻を決定する。この情報は、車輌の電子回路３にも送られ、例えば衛星ナビゲーションまたは「サット・ナヴィ（Ｓａｔ Ｎａｖ）」システムの機能を提供する。
【００３０】
また、コンピュータ１は、出力装置６を備え、もって、コンピュータ１が生成する車輌の将来の動きの予測を、人間が認識可能な形態の出力として提供する。出力装置６は、例えばＳａｔ Ｎａｖシステムまたは車載の娯楽システムの一部を構成するディスプレイ形態を有する。その代わりにまたはそれに加えて、スピーカ等の音声出力機器形態を有してもよい。
【００３１】
コンピュータ１、プログラムメモリ２およびレシーバ４は図１において別々のアイテムとして図１に示されているが、ディスプレイ６も含め、ただ１つの装置に統合してもよい。
【００３２】
コンピュータは車輌の観察記録を保存し、これら観察を、車輌の電子装置３より与えられる車輌の状態に関する情報を任意的に併せて処理して、運転手に１以上の車輌の将来の動きにかかる予測を示す。観察記録は、車輌の過去および現在の行路の記録を形成し、観察は少なくとも＜位置、時刻＞の組から成る。これらは、さらに、イグニッションキーの使用、シートメモリの使用、ドアの使用、ウィンドウ位置、ミラー位置、送信設定、座席利用率または重さ、選択される娯楽チャンネル、電話の着信もしくは発信、外部および内部温度、軸重、レインセンサ出力、けん引棒の使用、交通情報、汚染度、および換気設備または空調設備の設定等の他の情報を追加してもよい。当該情報は、コンピュータ１により処理される。そうすることによって、例えば、採りそうな目的地、ルート、速さ、停止、ブレーキング、加速、コーナリングに関する予測並びに行路記録の一部を形成する追加情報を出力する。例えば燃料消費、注意散漫レベルおよび疲労度等他のパラメータは、当該予測から算定すればよい。予測は、一致を判定するために空間と時間の両方のデータを使用し、過去の行路記録における観察シーケンスと最新の観察の一致をとって行う。コンピュータ１が車輌の電子装置３から上述した追加情報、つまり、イグニッションキーの使用、乗員の数、娯楽用設備の設定等を入手可能であるならば、それらを考慮して一致をとってもよい。
【００３３】
装置が車輌に組み込まれ、作動すると、車輌の行路に関する情報を記録し始める。特に、車輌のイグニッションがオンの間、車輌の場所を車載のＧＰＳレシーバ６から受けて頻繁に記録する。１秒につき１回の割合で場所を更新するのが、通例、本願の用途に適する。そうすることで、たいていの場合、５０メートル（５０ｍ）以内の場所の精度を得ることができる。１メートル（１ｍ）より高精度で、ＷＧＳ８４データを使用して、緯度、経度、および高度として位置を記録する。これは、うまい具合に全世界的に定義された座標系であるが、例えばＷＧＳ８４地球中心・地球固定直交座標系（Earth Centred Earth Fixed（ＥＣＥＦ））、陸地測量図グリッド（Ordnance Survey Grid）、ユニバーサル横メルカトル図法（ＵＴＭ）等の他のほとんどの２または３次元の座標系で十分である。
【００３４】
高度は多くのアプリケーションに必要なく、場所システムによっては検知しない。そのようなアプリケーションにとって、高度を省略可能な座標系が望ましい。高度が含まれる場合、それは以下のように使用してもよい。
それらは例えば、
・以下に記述されるいくつかの２次元的マッチングのアルゴリズムを３次元に拡張すること、
・例えば勾配および高架交差路を見分けることにより、追加のフィードバックをユーザに与えること、および
・三次元において走行したルートの状況を分析すること、である。
車輌の移動が地球表面に拘束されない場合、例えば、飛行機の場合には、高度を使用することの重要性は増大する。
【００３５】
車輌がそれぞれの場所にある時刻も記録する。場所と、使用するのであれば高度と、時刻との組み合わせを観察と称する。時刻を、今週における秒数として単精度浮動小数点数で保存し、一連の観察群をファイルに保存し、ファイル名をユリウス暦の日とすることで、いずれの観察の絶対時刻の計算も単純なタスクとなる。使用する時刻の基準はＧＰＳ時刻であり、それは国際的な時刻標準ＵＴＣに従うが、計算を簡単にするためうるう秒を含まない。同様にして、ＵＴＣやＴＡＩ等の他の時刻システムも、使用することができる。ＧＰＳの位置の絶対精度は、通常約１０ｍであるが、相対誤差をうまく利用することで、速さ等のデータを計算するときに、大きい量子化誤差を加算しないようにするので、より高精度（１ｍ）で記録することができる。
【００３６】
使用される数の書式は、ＩＥＥＥ７５４単精度であり、チェックとして各観察記録の最後に追加のバイト（改行０ｘ０Ａ）を追加し、どのファイルが破損しても、不適切なフォーマットになっても、検索を支援する。各観察は以下の１７バイトを有する。
０〜３バイト：ラジアン系のＷＧＳ８４の緯度（latという）
４〜７バイト：ラジアン系のＷＧＳ８４の経度（lonという）
８〜１１バイト：メートル系のＷＧＳ８４の高度（altという）
１２〜１５バイト：秒で示す週のＧＰＳ時刻（時刻という）
１６バイト：０ｘ０Ａ（セパレータという）
【００３７】
保存コストをさらに継続して下げ、そしてＧＰＳ等の一般的な位置決めシステムの精度をさらに継続して上げるように、他の実施形態は、倍精度浮動小数点フォーマットや、緯度および経度のマイクロラジアンもしくはミリ度に基づく整数フォーマットや、またはＮＭＥＡ０１８３で使用する度（degree）および１０進法の度等のＡＳＣＩＩフォーマットを使用することを選択してもよい。
【００３８】
観察シーケンスは、「ｙｙｍｍｄｄｘｘ．ｐａｔ」の仕様に従う名前のファイルに保存される。ｙｙは年度の最後の２桁であり、ｍｍは月の指標であり、ｄｄはその月内の日であり、ｘｘは同日に記録される複数のファイルを区別するためにインクリメントされるアルファベットのフィールドである。ファイル名には、そのファイルにおける最初の観察が選択される。例えば、ファイル０３０８２１ＡＡ．ｐａｔと０３０８２１ＡＢ．ｐａｔは２００３年８月２１日に始まったファイルの最初の２つである。
【００３９】
車輌のイグニッションをつけたときは、常に観察が自動的にこれらのファイルに保存され、エンジンを起動するたびに、新しいファイルが作られる。電力面に関して可能であれば、イグニッションを切ったときも、観察が保存され、カー・フェリー行路等の状況をカバーし、またはシステムが少しの動きも見逃さないようにする。この場合、少なくとも毎日、恐らくは毎時間、新しいファイルを始めるのが都合がよい。複数の小さなファイルに観察を保存する理由は、開いたり、バックアップしたり、通信したりすることを容易にし、ディスクまたはファイリングシステム障害に対して復元力を与え、そして限定的リソースで構成したコンピュータシステムで簡単にそれらを操作できるようにするためである。
【００４０】
実装例には、場合によって、データベースソフトウェアの制御下で、ただ１つのファイルに観察のすべてを保存することを選択してもよい。他の情報は、これらのファイルに保存され得る。例えば、観察が参照する車輌の登録番号、運転手の名前、交通情報といった外部的事象、気象情報、観察の後の処理に関連しているかもしれないあらゆる物事を保存してもよい。説明を簡単にするために、緯度、経度、高度および時刻情報だけを含む観察ファイルの例を考察する。
【００４１】
他の事象は、外部ファイルに保存され、ディレクトリ階層のそれらの位置により（例えば、車輌の登録番号の名を有するディレクトリに、ある特定の車輌の観察ファイルのすべてをグループ化することにより）、または、観察の時刻により（例えば、特定の運転手が車輌を始動させ、そして停止させた時刻を記録し、そのときそれらの時間に最も近い観察を検出することにより）、これらの観察と関連付けし得る。
【００４２】
まず、観察ファイルは時刻昇順にソートされ、そのとき場所はその順に各ファイルから、ただ１つの系列を有するリストへ抽出される。抽出処理の一部として、観察はすべての値が実用にかなった範囲内にあるかどうかのチェックを受ける。範囲内にない場合、ファイルの内容全体がリストから除外され、エラーレポートが生成される。また、抽出処理の一部として、リストに保存される観察の時刻を、１９８０年１月１日にＧＰＳ時刻が始まってからの秒数として示し、原初のファイル名との関連性を除去する。
【００４３】
次に、各連続する観察の時刻は前のもの以上であるように、１つのリストをソートする。ポイントを抽出する前に、ソート処理の大半はファイルをその名前によりソートすることにより実施されるので、このソート動作は非常に効果的である。ファイルが車輌追跡や携帯電話追跡等の異なるシステムからまとめられた場合、または時計を調整した場合、そのポイントそれ自身のソートが必要である。最初および最後の観察で規定する範囲、および２つの時刻順に連続する観察間の速さに基づいて、現在適当な範囲外にある観察シーケンスを拒絶することができるので、これはデータのインテグリティのさらなるチェックを提供する。
【００４４】
「前の観察」および「次の観察」という言葉を使用するとき、このただ１つの規則リスト内の位置を参照している。このリストは、連続してlat/lon/alt/時刻/セパレータのシーケンスを含むバイトのただ１つのシーケンスとして、lat、lon、altおよび時刻の個別のシーケンスとして、または観察配列またはリスト、緯度、経度、高度および時刻等のデータ構造として、ディスク又はメモリ上に保存されてもよい。記憶装置フォーマットの詳細な選択は、ソフトウェアが実行される特定のコンピュータの構成により決定されるが、索引またはポインタが後で観察情報を検索するために参照用に使用されるかもしれないので、索引またはポインタにより順次的に観察を検索する基本動作に常に対応する。メモリ内で使用するフォーマットは構造体の配列（記録）である。各構造体は、特定の観察の緯度、経度、高度および時刻を含む。シーケンス内において一番前の観察である第１の要素（要素０）と最新の観察である最後の要素を有する配列は、前述のように時刻順にソートされる。このタイプの構造体は、図２において説明される。
【００４５】
行路は、最初に朝家を出て、後で職場に着く等の２つの重要な事象間のある観察シーケンスである。行路を構成するただ１つの定義もなく、それはユーザ、情況および行路情報がどんな方法で使用されるかにより決まる。車輌がある期間止まっているなら、この期間を「休止期間」と呼び、それぞれの周囲の行路の終了と開始として、休止期間における最初と最後の観察を特定する。
【００４６】
車輌に有効である簡単な行路の一例は、新しい行路の開始として車輌のイグニッショをつける時刻と、行路の終わりとして次にイグニッショを切る時刻を使用する。コンピュータにイグニッション回路の状態またはイグニッショキーの位置を感知させることにより、現在イグニッショがついているか切れているかを検出し、タイムスタンプできてもよい。また、位置決めシステムは、イグニッションをつけている間のみ、観察を生成するためだけに用意されてもよい。従って、観察のない長い期間は、行路間の休止を示すことができる。また、イグニッショがついている間、観察を保存するプロセッサの電源を入れることができ、この場合も行路間の休止として観察のない長い期間を解釈することができる。
【００４７】
イグニッションを切っている間でも位置を生成するシステムに都合がよい他の定義は、車輌がほんの少しまたは全く動いていない期間を探すことである。ここで、直接または２つの連続する観察間の速さを計算することにより測定される車輌の速度が、ある期間（例えば、１分以上）動かない車輌（例えば、１ｍｐｈ）のために測定される最大限の誤差速度により決定されるある閾値より小さい状態である観察シーケンスを行路間の休止として検索し、行路の終了としてシーケンス内の第１の観察に印を付け、行路の開始としてシーケンス内の最後の観察に印を付ける。これには、だれかが小包を配達する間運転手が待つ場合等のイグニッショを切らなくてもよい短い行路を特定可能であること、電車が踏み切りを通過する間等のほんの短い間イグニッショを切る場合に行路を分断しないこと、イグニッショの状態の正確な検出に依存しなくてもよいこと、といった利点がある。
【００４８】
車輌が長期間とてもゆっくり動いている場合、速度ベースの経験則（heuristics）による改良点は、車輌が、ある期間（これをＢｍｉｎといい、一般的に３分）より長い期間において同じ位置のある許容誤差（一般的に５０ｍ）内にとどまる場合、または、Ｂｍｉｎより長く観察同士が離れている場合、シーケンスにおいてすべての期間に印を付けることである。
【００４９】
休止を特定するために使用されるアルゴリズムは、使用中の特定の位置決めシステムの特性に依存する。例えば、ＧＰＳシステムは進行にかかわらず毎秒１つの観察を生成してもよい。この場合、車輌は連続する観察間で５０ｍをカバーするために１１０ｍｐｈ（１８０ｋｍ／ｈ）より速く動かなければならない。従って、休止を特定するために、多くの観察を見なければならない。
【００５０】
適切なアルゴリズムは、時刻に関しＢｍｉｎ離れた観察シーケンスを見て、車輌がその時間にどれくらい遠くに移動したかを見る。例は、次の通りである。
【００５１】
ステップ１：一番前の観察を観察Ａとし、観察Ａと等しい観察Ｘを設定する。
【００５２】
ステップ２：各観察Ａに対して、その観察の時刻が観察Ａの時刻から３分未満である、最も遠い後の観察を検出する。それを観察Ｂとする。
ステップ３ａ：観察Ｂが観察Ｘから５０ｍ未満しか離れていない場合、観察Ａから観察Ｂまでのすべての観察に休止期間の一部として印を付け、観察Ｘは変えず、観察Ａを観察Ａの後の次の観察にする。
【００５３】
ステップ３ｂ：観察Ｂが観察Ｘから５０ｍ以上離れている場合、どんな休止観察も印を付けず、新しい観察Ａおよび新しい観察Ｘを観察Ａの後の次の観察にする。
【００５４】
ステップ４：観察Ａが観察リストの最後に至るまで、ステップ２から繰り返し、そうでない場合は、すべての休止期間の印付けを完了する。
【００５５】
このアルゴリズムは、車輌が非常にゆっくり動いていた（３秒で５０ｍ未満または約０．６ｍｐｈ（１ｋｍ／ｈ））ときでさえ、長い休止に印付けることができる。従って、これは、行路間の見込み休止であるとみなされる。印を付けられた休止期間の例を、図３に示す。
【００５６】
異なる動きが要求され、特定の位置決めシステムのドリフト（drift）及びドロップアウト（dropout）特性に依存する場合、このアルゴリズムへの様々な変更は使用され得る。
【００５７】
見込み休止期間を特定したので、休止期間の間の各移動期間のための行路記録を生成する。この行路記録は、最初の休止期間の最後の観察への参照、および次の休止のちょうど最初の観察への参照を含む。行路記録のための最初と最後の参照がある。行路のラベル付けを、図４に示す。
【００５８】
現在、計算しているアプリケーションにとって、それらの休止のうちのどれが重要であるかを決定した方がよい。
【００５９】
時間内の一番前から始まり、時間内の一番後ろまでずっと、順に各休止期間を検討する。休止期間の時間の長さが、先行するまたは続いて起こる行路の時間の長さより短い場合、およびある閾値（これをＢｍａｘといい、一般的に３０分）より短い場合は、これがより長い行路の途中の一時停止であったという理由で、それらの行路を１つの新しいものにまとめる。これは、図５に示される。
【００６０】
例えば、特に、恐らくガソリンで車を満たすためにまたは近くの店で何かを買うために出かける、５分の運転の後に、６分の停止が続き、その後に５分の運転が続くシーケンスは、２つの異なる行路であると見なされる。恐らく、１時間の運転の後に、ガソリンを入れたり軽食をとったりするために停止する６分の停止が続き、その後に３０分の運転が続くシーケンスは、すべてどこかへ向かう１つの行路であると見なされる。
【００６１】
閾値Ｂｍａｘより短いすべての休止期間が、その休止期間より短い長さの少なくとも１つの行路の横に位置づけられるまで、そのまとめる処理を繰り返す。
【００６２】
行路を特定するために使用される多数の類似した経験則がある。あるアプリケーションにおいて、例えば、異なる経験則を使用することにより、またはＢｍａｘ、Ｂｍｉｎ等のパラメータを調整することにより、行路の定義付けをアプリケーションの特定の要件に合わせて調整するのは、有利である。
【００６３】
例えば、図１７は、より大きな黒い点を使用することにより強調されている各特定される行路の最初の１０個と最後の１０個の観察を有する、多数の観察の地図を示す。行路が特定されるとすぐに、それぞれのためにコンピュータにおいて記録を生成する。この記録は、行路の開始および終了を示すメインリストにおける観察を参照する。これらの観察は、行路の開始および終了の位置および時刻を含む。その行路におけるすべてのポイントを含む最も小さい境界ボックスの緯度および経度を、各行路記録に追加する。この情報は、過去の行路を検索または表示する多数のアルゴリズムの速度を上げるのに使用される。
【００６４】
他の有用な最適化は、リスト全体が最初にソートされるとき、一番前の観察（観察０という）から各観察の累積的な距離を計算することである。このように、ある観察Ｘから観察Ｙまでの累積的な距離は、観察０から観察Ｘまでの累積的な距離を観察０から観察Ｙまでの累積的な距離から減算することにより得られる。従って、多数のささいな計算を減少させる。
【００６５】
また、シーケンスの各部分により示される速さおよび加速度は、さらなる計算および表示に、そして観測結果の正当性チェックとして有用である。５ポイントからなるすべてのグループのために速さと加速度を計算し、これらが車輌の能力の限界のおよびセンサーシステムの特有の誤差特性を示す、一定の正当性の境界内にあるかをチェックする。これらのポイントが正当な境界外になる場合、例えば速さが１５０ｍｐｈ（２４０ｋｍ／ｈ）である場合、または加速度が位置決めセンサの既知の瞬間的な誤差よりも長い距離にわたって１０ｍｓ−２より大きい場合、これらの５つのポイントと、前および後で一般的に１分に相当する多数のポイントも排除する。残ったポイントについて、後の計算に有効と認めたポイントと共に、速さと加速度も、コンピュータメモリ上にキャッシュまたはディスク上に保存することを選択できる。
【００６６】
一致は、一定の方法において、本車輌、他の車両の過去の動きまたは予めロードされた動き例のうちで、本車輌の最近の動きと似たものを検出する。当該一致を検出するのに使用される多数の異なるアルゴリズムがある。ここでは、２つの例がここに与えられ、１つはタイト（tight）であり、１つはルース（loose）である。ルースなアルゴリズムは、現在の行路において一定距離（例えば５００ｍ）後方を見て、車輌が５００ｍ＋−１０％を走行して、その位置から現在の位置まで移動した過去の行路を検出する。
【００６７】
また、タイトなアルゴリズムは、現在の行路において一定距離後方を見て、車輌が最近記録された軌跡の一定の誤差限界（例えば５０ｍ）内に留まりながら、その位置から現在の位置まで移動した過去の行路を検出する。恐らく環状交差か高架交差か、地方道路か高速道路か、または多車線高速道路の異なる車線のどれを使用するかの違いに起因する軌跡の細かな差異を取得できる。
【００６８】
両方の一致アルゴリズムは、最新の観察（観察Ｂという）を取得することから開始し、始まり、走行距離が例えば５００ｍを超える最初の観察が検出されるまで、引き続いて最近の観察シーケンスにおいてさらに後方を見て、次の各観察から走行距離を累積する。これを観察Ａという。今、最新の５００ｍの走行から観察を効率よく選択した。使用中の位置決めシステムの精度をかなり上回って一筋の道路をカバーし（cover）、ほとんどの分岐合流点の横断をカバーするのに十分とするように、５００ｍは選択された。この距離を一致距離Ｍという。一致にどの程度の精度を望むか、車輌および位置決めシステムの特性、または検出される一致の数により、一致距離Ｍを変更することができる。
【００６９】
ルースなアルゴリズムは、現在の行路の最後Ｍメートルの最初および最後の観察を使用して、中間位置を無視する。記録された観察シーケンスにおいて後方を見る。観察Ａから開始し、位置が観察Ｂの位置のある誤差限界（一般的に１００ｍ）内にある観察を検索しながら、逆時刻順に進む。アルゴリズムのこのステージをステージＸという。
【００７０】
観察が検出される場合、観察Ｂの位置の他の誤差限界（一般的に１００ｍ）外にある最初の観察を探しながら、さらに後方に進む。これを候補Ｂという。
【００７１】
候補Ｂから０．９×Ｍより長い累積距離を有する観察に達するまで、観察間の走行距離を累積しながら、後方に進む。これは第１の候補Ａである。
【００７２】
候補Ａの位置が観察Ａの位置の誤差限界（一般的に１００ｍ）内にあるかを判定し、それが誤差限界内にある場合、候補Ｂを現在の位置および最近の動きの潜在的一致として記録する。当該ペアは、候補Ｂ１および候補Ａ１並びに後のイタレーションに関して候補Ｂ２および候補Ａ２として、図６および図７で示される。
【００７３】
候補Ａが観察Ａに十分に近くない場合、各観察を新しい候補Ａとしながら、候補Ａの位置が観察Ａの位置に十分に近いものを検出し、潜在的一致として候補Ｂを記録するまで、または候補Ｂが潜在的一致でないと判断する場合、累積される距離が１．１×Ｍより長くなるまで、記録される観察シーケンスにおいて、引き続きさらに後方に移動する。
【００７４】
いずれにしても、観察Ｂの位置のある誤差限界（一般的に１００ｍ）内に位置するものを検出するまで、観察シーケンスにおいて候補Ｂから後方を見ることにより、再度開始する。
【００７５】
次に、ステージＸから上記処理を繰り返す。
【００７６】
十分な潜在的一致（一般的に１０００）を検出した場合、または一番前に記録された観察まで後方に進んだ場合、アルゴリズムは終了する。
【００７７】
要約すれば、このアルゴリズムは、現在の行路の最後のＭメートルの記録を検出し、最初及び最後の観察（観察Ａおよび観察Ｂ）を取得し、次に、候補Ａは観察Ａに近く、候補Ｂは観察Ｂに近く、候補Ａから候補Ｂまでの走行距離はＭメートルプラスマイナス１０％である候補Ａおよび候補Ｂの観察のため、その記録において後方を見る。記録が空になるまで、または十分なものが検出されるまで当該候補Ａおよび候補Ｂの観察の検出を繰り返す。一致リストという候補Ｂの観察のリストを生成する。アルゴリズムのこのステージをステージＹという。
【００７８】
タイトな一致アルゴリズムは、観察Ａから観察Ｂまでの観察シーケンスからある誤差限界Ｒより外れない候補Ａおよび候補Ｂの間の観察シーケンスを探すことを除いては、同様の方法で動作する。
【００７９】
このアルゴリズムは、まず観察Ａに近い一番前の観察（候補Ａという）を検出することにより動作する。次に、どっちのポインタを動かしたら、２つのポインタが近くなるかを選択することにより、観察Ａおよびこられのポインタ間の距離を最小にするような候補Ａから、時刻順に前方へ２つのポインタを移動する。過去の位置（pastP）は過去の観察において候補Ａと候補Ｂとの間を移動し、現在の位置（currentP）は最新の観察において観察Ａと観察Ｂとの間を移動するので、ポインタをそれぞれ過去の位置、現在の位置という。両方のポインタが、誤差限界Ｒよりさらに離れて移動することなしに、それぞれの最後のポイント（観察Ｂおよび候補Ｂ）に達する場合、観察Ａから観察Ｂまでの最近の道にきっちりと続く候補Ａから候補Ｂまでの従来の道を検出する。従って、一致可能なものの最初の索引のリスト上に候補Ａの索引を記録する。ポインタがどのステージにおいても極端に離れて移動する場合、一致することを中止し、リスト上にこの候補Ａを記録しない。
【００８０】
観察Ａから十分遠くに移動するまで、最後の候補Ａから前方へ移動することにより新しい候補Ａを検出し、これまでたどってきた道を考察する。そして再度、観察Ａに近い次の観察を探す。これが、新しい候補Ａとなる。
【００８１】
観察において、トンネル、他の障害物、他のシステムからの妨害、一時的な電力損失による場所情報の一時的な損失により引き起こされる途絶がある場合、アルゴリズムは、個別的に移動するように過去の位置および現在の位置のポインタにより参照される場所を与える制御方法により、強化される。過去の位置または現在の位置の１つまたは２つの更新のためさらに個別的に移動することができるが、それらはかなりの時間、誤差限界より離れた状態であろうとも、それらは常により近づくように移動しなければならない。
【００８２】
強化されたタイトな一致アルゴリズムにおいて、記録された観察の初めから開始し、観察Ａのある誤差限界内に位置する観察を順方向に検索する。これが、候補Ａとなる。
【００８３】
アルゴリズムのこのステージをステージＺという。
【００８４】
繰り返して候補Ａの後の観察を見て、それが観察Ａの位置により近い場合、新しい候補Ａを生成する。今、その前または後ろの観察より観察Ａに近い候補Ａを有する。候補Ａが観察Ａ自身に達するまでに、時間的にかなり遠く前方へ移動する場合には、すべての一致可能なものを検出して、アルゴリズムのこのフェーズを終了しフィルタリングに移る。
【００８５】
次に、常に観察Ａから観察Ｂまでの道に近いままであり続けながら、位置が観察Ｂのある誤差限界内にある時まで、候補Ａから前方へ観察の道をたどることができるか否かを考察する。
【００８６】
ポインタ間の距離を短く保ちながら、（候補Ａからの）過去の道および（観察Ａからの）現在の道両方に沿ってポインタを前方へ動かすことにより、これを実行する。そのポインタをそれぞれ過去の位置および現在の位置という。現在の位置が観察Ｂに達する場合、一致を検出し、一致可能なもののリスト（一致リスト）に過去の位置を追加する。
【００８７】
最初は、過去の位置は候補Ａを示し、現在の位置は観察Ａを示す。２つの距離、過去の移動距離および現在の移動距離を計算する。過去の移動距離は、過去の位置の後の観察と現在の位置の観察との間の距離、すなわち、過去の位置をその後ろの次の観察を指すように、移動させた場合における、過去の位置と現在の位置の間にある距離である。現在の移動距離は、過去の位置の観察と現在の位置の後の観察との間の距離、すなわち、現在の位置をその後ろの次の観察を指すように移動させた場合における、過去の位置と現在の位置の間にある距離である。
【００８８】
過去の移動距離は現在の移動距離以下である場合、過去の位置を移動させる。これを実行するために、過去の位置を更新し、過去の位置がその後の観察を指すようにする。
【００８９】
また、過去の移動距離が現在の移動距離より長い場合、現在の位置の後の観察を示すように現在の位置を更新することにより現在の位置を移動させる。
【００９０】
このように、過去の位置と現在の位置の距離をできるだけ短くするように試みる。図９から図１１までは、ポインタが一般的なシナリオにおいて更新する方法を示す。
【００９１】
図９において、過去の移動距離は短いので、過去の位置を更新し、再計算し、図１０を与える。現在の移動距離は短いので、現在の位置を更新し、再計算し、図１１を与える。
【００９２】
過去の位置と現在の位置の間の距離は、時々短くなったり時々長くなったり、更新が進むにつれて変化する。ある誤差限界（一般的に５０ｍ）より小さい間は、一致を継続する。誤差限界より大きくなった場合、すぐに一致を中止しない。この理由は、例えば車輌がトンネルまたは木の下を通って走行したとき等、観察において時々ギャップがあるかもしれないことである。それにより、一わたりの道において、一方の道には、観察が存在し、他方の道には観察が存在しないため、距離が誤差限界を超える原因となる。このことを勘案し、過去の位置と現在の位置の間の距離が誤差限界より大きくなり、最後のＮ個の更新の間増大するまで、一致を中止しない。Ｎは一般的に２に設定される。距離は急に２００ｍに増大し、次の２０の更新の間誤差限界より大きいままであるが、２つの連続する更新の間、増大しないのであれば、まだ、道の間の一致とする可能性は残る。
【００９３】
図１２において、現在の移動距離が過去の移動距離未満であるため、現在の位置を移動させ、図１３を与える。現在の移動距離が過去の移動距離以上であるため、過去の位置を移動させ、図１４を与える。現在、現在の位置と過去の位置の間の距離は、閾値（５０ｍ）を越え、それをさらにＮ−１回増大することができるだけである。Ｎ＝２の場合、もう一度だけ増大することができるだけである。現在の移動距離が過去の移動距離未満であるため、現在の位置を移動させ、図１５を与える。現在、現在の位置と過去の位置の間の距離は、再度増大してもよい。従って、さらにＮ−２回（この場合０回）増大することができるだけである。小さくなる前に再度増大する場合、この道を一致から除外する。現在の移動距離が過去の移動距離以上であるため、過去の位置を移動させ、図１６を与える。現在、現在の位置と過去の位置の間の距離は、５０ｍよりは長いが、短かくなった。従って、計数をリセットし、一致を中止する前にさらにＮ回増大できる。この特定例において、別のドロップアウトに達するまで、再度増大しない。なぜなら、現在の移動距離が過去の移動距離以上であるため、過去の位置を移動させ、過去の位置は再度現在の位置の５０ｍ範囲内になるからである。このようにして、トンネルによるドロップアウトをうまく切り抜ける。
【００９４】
また、木等のオブジェクトが原因の両方の道における多数の異なるドロップアウトシーケンスは、同じ方法で切り抜けられる。
【００９５】
一致を中止する場合、または現在の位置が観察Ｂに達したことを検出する場合、再度過去の位置を開始するための新しい候補Ａが必要である。これを検出するために、候補Ａの後の観察を見て、新しい候補Ａを生成する。候補Ａから観察Ａまでの距離が誤差限界より長くなるまで、または候補Ａが観察Ａに達するまで、これを繰り返す。この場合、すべての一致可能なものを検出しており、このアルゴリズムのフェーズを終了する。候補Ａがまだ観察Ａに達していない場合、上記ポイントステージＺから一致処理を継続する。候補Ａが観察Ａに達した場合、一致可能なもののリスト（一致リスト）を完成し、再度これをアルゴリズムのステージＹという。
【００９６】
車輌の来し方に対する依存度を高めるために、一致距離Ｍを、恐らく２ｋｍまで、または現在の行路のいっぱいの範囲までも増加させることができる。
【００９７】
通常、たとえ観察Ｂより前の行路に観察Ａを取得しても、一致距離を使用する。これには、前の行路の最後に取得されたルートの依存を導入するという効果がある。そしてそれは、予測の精度を上げるために有益な付加的依存である。また、当該状況においては、一致距離を、減少させ、現在の行路でこれまで走行した距離にできる。そしてそれは、フィルタリングアルゴリズムにより後で精選される、より多くの潜在的な一致を含む。走行方向に関係なく、そのポイントの周りで生成されるすべての過去の観察から成る一致リストを返すという効果があるので、これは行路の始期において、特に有益であるが、これらは、後で一週間周期の時刻または一日周期の時刻によりフィルタをかけられる。行路が進むと、一致距離は増加し、その後の一致リストは、それまでにたどったルートにさらに依存する。
【００９８】
タイトな一致アルゴリズムとルースな一致アルゴリズムの両方は、時刻順にリスト化した観察記録を前方へ検索または後方へ検索して実行される。また、それらはいくつかの観察を飛ばすことにより最適化され得る。そしてそれは、ちょうど場所システムが低い更新率を使用したかのようである。異なる経験則は、例えばそれらが最後に考察した候補点から少なくともｄメートルであるべきことを要求する、新しい候補点を選択するのに使用され得る。これらの選択が、可能な最大の一致の数を取得し、できるだけ早く１セットの一致を取得し、またはそれらが動くコンピュータシステムのメモリアーキテクチャとアルゴリズムとの相互作用を最大限に利用するために個別的になされてもよい。
【００９９】
ルースなアルゴリズムまたはタイトなアルゴリズムのどちらか一方のステージＹから、時刻、運転情報、気象情報等の他のフィルタを利用して、潜在的な一致の数を減少させることができる。例えば、各候補Ｂが観察Ｂの一週間周期の時刻のプラスマイナス１時間内であることを要求した場合、潜在的な一致がいくつ残っているかをチェックしてもよい。それが十分な一致を残した場合、減少させたリストを新しいリストにする。一週間周期の時刻に対して不十分な数の一致が残る場合、各候補Ｂが観察Ｂの一日周期の時刻のプラスマイナス１時間内にあることを要求したとき、潜在的な一致がいくつ残っているかチェックする。それが十分な一致を残した場合、減少させたリストを新しいリストにする。
【０１００】
一般に生成される行路は当初同じルートを共有するため、時刻ベースのフィルタリングは、それらのルートが分岐する前にそれらを区別するのを助ける。例えば、午前８時の平日の行路の開始は、仕事のための多数の過去の行路と一致してもよい。一方、週末の同様の開始は、買い物や親戚への過去の行路と一致してもよい。
【０１０１】
また、一致リストが十分長い場合、観察の時期によりフィルタをかけてもよい。このように、システムは、職場、学校等の変更のための、運転パターンにおける変更により速く適応する。ユーザからの入力により、古いルートの中止があったことを知れば、当該フィルタリングは強化され得る。当該時期ベースのフィルタリングは、まれな古い一致はいくつかのアプリケーションのために適切に考慮され得るので、後の予測ステージにおける一致リストの重み付けとして適用されてもよい。
【０１０２】
この新しいリストを取得し、そして使用可能な運転手識別情報がある場合、各候補Ｂが観察Ｂと同じ運転手であることを要求したとき、潜在的な一致がいくつ残っているかをチェックしてもよい。それが十分な一致を残した場合、減少させたリストを新しいリストにする。
【０１０３】
このように、多数の他のフィルタを適用できる。ほとんどのＣＰＵおよびメモリの過酷な処理は、一致するタスクを実行することに集中する。どのようなアプリケーションが情報を処理するがに依存して複数の異なるフィルタリングスキームを適用することおいて、利点があるかもしれない。例えば、行路時間予測を生成したい場合、必ず時刻によりフィルタをかけ、最新の行路を優先すべきだが、大きな交通事故が警告の正当な理由となる（warrant）か否かを決定する場合、最新のものと同様にまれな行路を考慮する。
【０１０４】
フィルタをかけた一致可能なもののリストで、関心事の特性を見ることができる。一致リストにおける各一致から、観察シーケンスにおいて前方を見て、車輌で進行している動きが過去において何であったかを調べる。これらの動きは、車輌で進行している動作の現在の時刻からの予測として使用され得る。例として、車輌が毎分その位置を報告することになっている場合、各一致から１分前を見て、そして位置が互いのある誤差限界（一般的に５００ｍ）内にある場合、１分毎に、車輌の予測位置としてそれらの位置の平均を現在位置と共に送信することで、通信帯域幅およびレイテンシを減少させる。１分毎の代わりに２分毎に１つのメッセージを送信しさえすればよい。これは、２分、３分またはそれ以上前を見ることまで広がり、より多くの通信オーバーヘッドが減少される。まれに、その時間よりも前に車輌が予測位置からある誤差限界（一般的に５００ｍ）より大きくそれる場合、最後の位置および予測と共にさらなるメッセージが送信され、状況を修正することができる。
【０１０５】
また、車輌の過去の観察履歴のデータベースを、時折ダウンロードし、遠隔地にて保存しなければならないが、この機能は、車輌とは離れて、車輌から受信される最後の観察から同様の一致アルゴリズムを適用することにより、実行され得る。
【０１０６】
異常な交通状態についての警報を受信する手段がある場合、または恐らく交通渋滞が起こるいつもの時間および場所（問題の箇所）のデータベースにアクセスする場合、車輌がそれらのどれかに遭遇しそうであるか否かを知りたいと思うかもしれない。
【０１０７】
一致リストの各観察から前方へ、その観察を含む行路の最後までを調査することにより、これを行う。それらの行路毎の各ポイントに対して、一致した観察からそこに到達するのにかかる時間またはルート選定ソフトウェアにより予測される時刻に基づいて、そこに到達する時間（３０分以内）にその付近（１００ｍ以内）に交通警報または既知の問題の箇所があるか否かをチェックする。そのような警報がある場合、適切な行動をとれるように次の安全な機会において運転手に警告し、ルート案内や車輌追跡システム等の他のシステムにこの情報を渡す。ルート選定は平均速度計算値で距離を割るような単純なものでよい。ここで、距離は一致した行路から知られる。またあるいは、スマートナビ（SmartNav）システムにおけるトラフィックマスタ（TrafficMaster）で使用されるもののように道路タイプおよび予測交通レベルを考慮に入れる完全なルート検索アルゴリズムであってもよい。
【０１０８】
運転手に交通、ルート、サービス、電話または他の注意を散漫にさせる可能性がある情報を提示したいと思う場合、加速、減速、コーナリングまたは分岐合流点がほとんどなかった時間を見つけるために過去において車輌で進行した動きを見ることが有用であることが分かる。これらの状況が、一致リストにおける大部分の観察において同じ進行期間Ｐで満足される場合、その期間Ｐの始まりは、今後運転手に情報を提示するのに良い時間である。
【０１０９】
逆に、過去において進行した動きのいずれかに対して、注意散漫の痕跡が、すぐに続いて起こるある期間（一般的に運転手が情報を理解するのにかかる時間）にわたってあったか否かをチェックしてもよい。当該痕跡が検出されなかった場合、すぐにその情報を提示する。当該痕跡が検出された場合、情報がとにかく提示するのに十分重要であるか否かを決定するか、もはやとても古いので有用ではないとして情報を捨てるか、または次の予測更新後、処理を繰り返すかしなければならない。
【０１１０】
現在の行路の目的地を予測したいと思う場合、一致可能なものの１つを含む各過去の行路の終点を見てもよい。それらの終点は、相対的な近接性によりクラスタに分類され得る。１つのアルゴリズムが、アルゴリズムの備える固有のクラスタに各ポイントを入れることにより始まる。次に、各クラスタは順番に取得され、各ポイントは他のすべてのクラスタのポイントと比較される。いずれか同士が互いにＰメートル内にあることが検出された場合、それらのクラスタは１つにまとめられる。すべてのクラスタが１つにまとめられるか、または異なるクラスタにおいて互いにＰメートル内にあるポイントが検出されなくなるまで、各クラスタを順番に取得するこの処理は何度も繰り返される。他のこのようなクラスタリングアルゴリズムは、情報科学テキストに記載される。
【０１１１】
今、各クラスタにおいていくつの行路が終了するかを見て、この行路がその中でほとんどの終点を有するクラスタにおけるあるポイントの近傍Ｐメートル内で終了するであろうことを予測する。（地域を名前と関連付ける地名辞典を参照することにより）これを位置のテキスト記述として表現するか、またはクラスタ内のポイントの平均的な位置および最大限の範囲を与える。それが有用である点は、終点の数が一番多いクラスタからそのような予測のリストを生成することができる点である。
【０１１２】
予測目的地が得られれば、ユーザにより入力される目的地に対しすることすべてをすることができる。例えば、交通情報をフィルタにかけたり、ルート選定およびルート案内を実行したり、行路時間とその変動幅を見積もったり等。ただ１つの最も密集したクラスタまたはそれらのうちのいくつかのためにこれができる。ユーザに可能性を示し、１つを選択するかまたはそれら全部を拒絶できるオプションを与える。
【０１１３】
目的地情報を表示する１つの有用な方法は、道路標識に似通った形であってもよいが、それは車輌の以前の動きによって変化してもよい。それは以下のような情報を与えてもよい。
バーミンガムセンタ（Birmingham center） ４０マイル ４５分
エグゾスパン社（Exospan limited） ６７マイル １時間３５分 遅延Ｍ６Ｊ１２
ＮＥＣ ２５マイル ２５分
【０１１４】
運転手はただこれらの案内標識を見ることだけを選択してもよい。またはそれらから音声またはボタンインターフェイスによりそれらから特定のラインを受諾または拒絶することができる。１つのラインを受諾する場合、それは既知の目的地として設定され得る。そして車輌は代わりのルートを計算するかまたは他のシステムに知らせてもよい。１つのラインを拒絶する場合、それはディスプレイから取り除かれ、そしてそれを生成した一致する観察を含む行路は、現在の行路の残りの部分に対する考察から取り除かれ得る。従って、不適切な交通警報を削減し、行路時刻、運転手の行動等の予測の制度を上げる。
【０１１５】
有用な付加的拡張は、時間順とは逆に、過去の観察に対して現在の行路の最近の部分を一致させようと試みることである。現在の行路が観察Ａから観察Ｂまで移動した場合、観察Ｂの近く（ここでもこの観察を候補Ｂという）から観察Ａの近く（ここでもこれを候補Ａという）まで移動した過去の行路区分を検出する。過去の候補Ｂにつながるものを使用することができ、観察Ｂの後今起こるかもしれないことを予測することができる。
【０１１６】
この逆ルート一致は、新しいルートの帰りの区間に使うと非常に効果がある。以前にその方向に走行したことがないかもしれないが、いずれにせよ行きの行路で走行したのと同じ帰り道をたどる。例えば、行路目的地は行きの行路の始点であると予測されてもよく、適した交通情報や代わりのルートが与えられてもよい。
【０１１７】
一般的に、前方向において十分な一致がない（だいたい１０より小さい）場合、逆ルート一致が試みられてもよい。
【０１１８】
走行されたルートがほとんどないときはじめにシステムを助けるため、または初めて新しいルートが走行されるとき助けるため、他の車両から記録されるルートまたはルート選定システムから計算されるルートに沿って創り出される観察を有するシステムをあらかじめ組み込んでもよい。幹線道路ネットワークのためのそのようなあらかじめ組み込まれる観察を持つことは特に効果的である。このような創り出される観察は記録され、実在する観察との一致がどれもよい一致を見つけ出さない場合、最後の手段として使用されるか、またはそれらはすべての一致するサイクルにおいて使用されるが、実在する観察が増加するに従って予測へのそれらの効果を減少させるためには、時期および希少性でフィルタをかければよい。
【図面の簡単な説明】
【０１１９】
【図１】本発明の実施形態を構成する装置を示すブロック図
【図２】行路および行路区分を決定するための観察記録および分析を示す図
【図３】行路および行路区分を決定するための観察記録および分析を示す図
【図４】行路および行路区分を決定するための観察記録および分析を示す図
【図５】行路および行路区分を決定するための観察記録および分析を示す図
【図６】行路区分間の一致を決定するための第１の手法を示す図
【図７】行路区分間の一致を決定するための第１の手法を示す図
【図８】行路区分間の一致を決定するための第１の手法を示す図
【図９】行路区分を一致させるための他の手法を示す図
【図１０】行路区分を一致させるための他の手法を示す図
【図１１】行路区分を一致させるための他の手法を示す図
【図１２】行路区分を一致させるための他の手法を示す図
【図１３】行路区分を一致させるための他の手法を示す図
【図１４】行路区分を一致させるための他の手法を示す図
【図１５】行路区分を一致させるための他の手法を示す図
【図１６】行路区分を一致させるための他の手法を示す図
【図１７】行路分析を示す図
【技術分野】
【０００１】
本発明は、例えば車輌等のオブジェクトの将来の動きを予測するための装置および方法に関する。また、本発明は、コンピュータを制御して、当該方法を実行させるプログラム、当該プログラムを伝える搬送媒体、データネットワーク等の通信路を介した当該プログラムの伝送、および当該プログラムがプログラムされたコンピュータに関する。
【背景技術】
【０００２】
Marmasse and Schmandt著（非特許文献１）は、車輌またはユーザが頻繁にしばらく静止する場所を記録することにより、よく訪れる場所を学習するためのシステムを開示する。ユーザは当該場所を命名するように促され、よってそれを予測のための候補とする。また、学習段階があり、そこでは使用する行路モデルには、開発者がルートとして分類した試験的行路があてはめられる。この段階は、ルートの試験的走行を特定のモデルと関連付ける工程を含むため、ユーザによる多くの介入を要し、そのため、自動システムに適さない。各ルートのための学習データを用いて、例えばベイズ分類器、ヒストグラムモデリングおよび隠れマルコフモデル等の様々なモデルを学習する。
【０００３】
US 2002/0161517 A1（特許文献１）は、目的地を予測するためのシステムを開示する。当該システムは以下を含む。（ａ）ユーザが過去に入力したそれらの目的地、（ｂ）道路地図データベース、（ｃ）現在の行路の最近の履歴、および（ｄ）道路地図データベースに対し、過去の行路を一致させ、走行情報データベースを形成すること。当該目的地が一度特定されれば、後は目的地に使用されるルートを記録し始めるだけである。従って、それは一般に、それが使用される前に目的地を特定するユーザ介入を必要とする。システムが、車輌のエンジンを一様に停止する位置を検出し、そしてそれを目的地ポイントとして記録できることが提案されている。その後、ユーザが目的地としてそのポイントを選択すれば、システムはルートを学習し、自動的にその目的地を予測するようになる。しかしながら、ユーザは、まだいくつかの段階において手動で目的地としてそのポイントを選択しなければならない。
【０００４】
EP0967460 A1（特許文献２）は、通勤ルート、すなわち、運転手が最も頻繁に走行するたった１つのルートを学習するためのシステムを開示する。当該システムにおいては、通勤ルートが生成される間、ユーザが時刻窓に入力することを必要とするか、または、初期時刻設定を使用する。そして、直前に使用したルートを保存するか、出自が未定義の合成ルートを保存するか、または当該時刻窓の間に横断した回数を、各道路区分について、地図データベースを用いて計数し、最も頻繁に走行した道路区分を通勤ルートとして用いるかして、通勤ルートを推定しようと試みる。
【０００５】
【特許文献１】米国特許出願公開第２００２／０１６１５１７号明細書
【特許文献２】欧州特許出願公開第０９６７４６０号明細書
【非特許文献１】マーマッセとシュマント（Marmasse and Schmandt）著「ユーザセンタードロケーションモデル（A User-centred Location Model）」パーソナルおよびユビキタス・コンピューティング ２００２ ６巻，ロンドン・シュプリンガー出版株式会社，ｐ３１８−３２１
【発明の開示】
【発明が解決しようとする課題】
【０００６】
非特許文献１のよく訪れる場所を学習するためのシステムには、学習段階がある。この段階は、ルートの試験的走行を特定のモデルと関連付ける工程を含むため、ユーザによる多くの介入を要し、そのため、自動システムに適さない。
【０００７】
特許文献１の目的地を予測するためのシステムにおいて、ユーザは、まだいくつかの段階において手動で目的地としてそのポイントを選択しなければならない。
【０００８】
特許文献２の最も頻繁に走行するたった１つのルートを学習するためのシステムにおいて、通勤ルートが生成される間、ユーザが時刻窓に入力すること等を必要とする。
【課題を解決するための手段】
【０００９】
本発明の第１の態様により、添付された請求項１において定義される装置を提供する。
【００１０】
本発明の他の態様および実施の形態は、添付された他の請求項において定義される。
【００１１】
このようにして、オブジェクトの観察シーケンスを記録し、保持し、または保存したシーケンスと最近のシーケンスとの一致をとることで、オブジェクトの将来の動きを予測可能にする情報を導出するように構成することができる。一致をとる工程は、少なくとも最も一般化した形式においては、２次元のデータにおいて１次元の一致をとる操作と表現することができる。例えば前述の従来のシステムは、観察記録を保持せず、当該一致を実行しない。従って、本願の手法は、オブジェクトの将来の動きのより正確な予測を可能にする。追加データを各観察に付随して保存し、より様々な予測をしてもよい。例えば、当該予測は、単なるオブジェクトの将来の動きまたは場所の予測を越えて拡大してもよい。
【発明を実施するための最良の形態】
【００１２】
一例として添付図面を参照して、本発明をさらに説明する。
【００１３】
下記は、その意味の説明付きの、以下に使用される用語の用語解説である。
【００１４】
一連の観察により示される動作（motion）中の休止は、観察により示される場所があまり変化しない期間である。位置決めシステムの誤差特性により引き起こされるわずかなずれがあってもよい。また、抑止された場合または位置決めシステムの電源が切れている場合、観察が全くなくてもよい。
【００１５】
外部の位置は、外部の座標系において、あるオブジェクトがどこで検出されるか、またはある事象がどこで起こるかを記述するのに使用される。高度のあるなしにかかわらず、ユニバーサル横メルカトル図法（Universal Transverse Mercator（ＵＴＭ））等の地図投影法による格子点により、世界測地標準１９８４（World Geodetic Standard 1984（ＷＧＳ８４））等のデータの緯度および経度により、またはＷＧＳ８４地球中心・地球固定直交座標系（Earth Centred Earth Fixed（ＥＣＥＦ））等の直交座標系により、それらを示せばよい。
【００１６】
ＧＰＳは、米国全地球測位システム（United States Global Positioning System）であり、良好な信号条件下でアンテナ位置を数メートル内に検出可能とするいくつかの衛星によるナビゲーションシステムの１つである。また、１マイクロ秒より高精度で時間情報を提供する。
【００１７】
ＧＰＳ時刻は、協定世界時（Universal Time Coordinated(ＵＴＣ)）にしたがう絶対時刻標準であり、地球の自転に基づく観測時刻標準の１つである。ＧＰＳ時刻は、１マイクロ秒以下のＵＴＣとの誤差を有するが、２００ｎｓよりよい値になるように較正される。ＧＰＳ時刻は、太陽の周りを回る地球の公転周期に適合（うるう秒適合）しないので、わずかな整数秒を加算するＵＴＣとずれる。ＵＴＣ、ＧＰＳ時刻が基準の秒数を取得する調整されない原子による時刻尺度を、ＴＡＩ（国際原子時）という。従って、ＧＰＳ時刻を引いたＴＡＩは、一定の整数秒にとても近く、それは、ＧＰＳ時刻が１９８０年に始まったとき、ＴＡＩとＵＴＣの間において、１９秒の時刻ずれがあった。
【００１８】
行路は、その行路の端を生成する２つの重要な場所の間の観察シーケンスである。このシステムにおいて、行路を重要な休止の間の観察シーケンスと定義する。休止が重要であるとみなされるか否かは、使用する特定のアルゴリズムおよびパラメータにより定義されるが、一般には、比較的長い動作にかかる期間における比較的短い休止を除外するようにパラメータを設定する。適切な設定により、途中で食事をするための１時間の休止のある３時間の運転は、ただ１つの行路とみなされる一方、他方においては１５分間の買い物のための１５分の移動は、その後の１５分の帰宅行路にかかる１５分間の外出とで、２つ別々の行路とみなされる。
【００１９】
事象の場所は、使用する座標系において示される位置である。例えば、浮動小数点数値として示されるＷＧＳ８４データにおいて、緯度、経度、高度を使用する。高度の使用は任意であるが、ある場合ソフトウェアの様々な特性を強化するために使用され得る。
【００２０】
観察は、オブジェクトの場所およびオブジェクトがその場所で検出されたときの時刻の記録である。
【００２１】
観察配列は、配列に保存される観察の記録のシーケンスである
【００２２】
観察索引は、観察配列の要素を特定する整数値である。
【００２３】
ポイントは、特に別に選択された観察索引である。かかる観察の場所は、ディスプレイ画面上の特定の画素に位置することが分かっている場所であるか、または、所与の場所もしくは時刻に対する近接性といった他の基準を用いて選択される。多数のポイントは同じ画素に配置されてもよい。だが、データベースのすべての場所を、ポイントとして示さずともよく、例えば、昨年取得された観察だけを表示すればよい。ユーザはマウス、カーソルキー、または他の入力手段を使用してポイントを選択することができ、ソフトウェアは、選択されたポイントに対応した場所を判別することができる。
【００２４】
ポイントセットは、ポイントの順番および重複に意味を持たないポイントの集まりである。なお、これがより効率的に処理できるなら、それらは昇順にソートし、重複を解消してもよい。
【００２５】
ポイントリストには、それ自身の明確に定めた順番があり、重複にも意味を持つ場合がある。
【００２６】
ＷＧＳ８４は、１９８４年の世界測地系であり、ＧＰＳにより使用される主要な座標系である。それは、座標系の原点が地球の質量中心に近く（数メートル内）なるように、地球の周りのステーション（局）の座標を定める直線座標系である。従って、特にＧＰＳ等の衛星を利用したシステムにとって有用である。当該座標系は、地心座標系（Earth Centred Earth Fixed(ECEF)）という。地質断層ラインに沿っての動き等の広範囲にわたる地殻変動があった場合、局の座標は調整され、座標系全体において不連続を解消することができる。ｚ軸は国際地球自転サービス（International Earth Rotation Service）により定義される地球の自転軸に合わせられ、ｘおよびｙ軸はグリニッジ子午線に近い、採用される子午線を参照することにより定義される。また、座標もＷＧＳ８４データにおける緯度、経度および高度で示すことを可能にする、関連楕円体も存在する。
【００２７】
図１は、自動車等の車輌において組み込まれるＲＯＭ、フラッシュメモリ、ハードディスクドライブ、および／または光学ディスクドライブ等のプログラムメモリ２を有するコンピュータ１の形の装置を示す。しかしながら、本発明の実施形態は、車輌における使用に限定されず、他のオブジェクトに取り付けられてもよいし、組み込まれてもよい。例えばこのような装置は、例えば地理的な場所および現在の時刻についての情報を受信するタイプの携帯電話に組み込まれてもよい。
【００２８】
車輌は車輌の電子装置３を備え、それは車載の多数のシステムを監視し、制御する。従って、コンピュータ１は、以下に記述される車輌の現況に関する複数の観点による情報を受信することができる。
【００２９】
車輌は、さらにＧＰＳレシーバ４を備え、アンテナ５を介してＧＰＳより受信する信号から車輌の位置および現在の時刻を決定する。この情報は、車輌の電子回路３にも送られ、例えば衛星ナビゲーションまたは「サット・ナヴィ（Ｓａｔ Ｎａｖ）」システムの機能を提供する。
【００３０】
また、コンピュータ１は、出力装置６を備え、もって、コンピュータ１が生成する車輌の将来の動きの予測を、人間が認識可能な形態の出力として提供する。出力装置６は、例えばＳａｔ Ｎａｖシステムまたは車載の娯楽システムの一部を構成するディスプレイ形態を有する。その代わりにまたはそれに加えて、スピーカ等の音声出力機器形態を有してもよい。
【００３１】
コンピュータ１、プログラムメモリ２およびレシーバ４は図１において別々のアイテムとして図１に示されているが、ディスプレイ６も含め、ただ１つの装置に統合してもよい。
【００３２】
コンピュータは車輌の観察記録を保存し、これら観察を、車輌の電子装置３より与えられる車輌の状態に関する情報を任意的に併せて処理して、運転手に１以上の車輌の将来の動きにかかる予測を示す。観察記録は、車輌の過去および現在の行路の記録を形成し、観察は少なくとも＜位置、時刻＞の組から成る。これらは、さらに、イグニッションキーの使用、シートメモリの使用、ドアの使用、ウィンドウ位置、ミラー位置、送信設定、座席利用率または重さ、選択される娯楽チャンネル、電話の着信もしくは発信、外部および内部温度、軸重、レインセンサ出力、けん引棒の使用、交通情報、汚染度、および換気設備または空調設備の設定等の他の情報を追加してもよい。当該情報は、コンピュータ１により処理される。そうすることによって、例えば、採りそうな目的地、ルート、速さ、停止、ブレーキング、加速、コーナリングに関する予測並びに行路記録の一部を形成する追加情報を出力する。例えば燃料消費、注意散漫レベルおよび疲労度等他のパラメータは、当該予測から算定すればよい。予測は、一致を判定するために空間と時間の両方のデータを使用し、過去の行路記録における観察シーケンスと最新の観察の一致をとって行う。コンピュータ１が車輌の電子装置３から上述した追加情報、つまり、イグニッションキーの使用、乗員の数、娯楽用設備の設定等を入手可能であるならば、それらを考慮して一致をとってもよい。
【００３３】
装置が車輌に組み込まれ、作動すると、車輌の行路に関する情報を記録し始める。特に、車輌のイグニッションがオンの間、車輌の場所を車載のＧＰＳレシーバ６から受けて頻繁に記録する。１秒につき１回の割合で場所を更新するのが、通例、本願の用途に適する。そうすることで、たいていの場合、５０メートル（５０ｍ）以内の場所の精度を得ることができる。１メートル（１ｍ）より高精度で、ＷＧＳ８４データを使用して、緯度、経度、および高度として位置を記録する。これは、うまい具合に全世界的に定義された座標系であるが、例えばＷＧＳ８４地球中心・地球固定直交座標系（Earth Centred Earth Fixed（ＥＣＥＦ））、陸地測量図グリッド（Ordnance Survey Grid）、ユニバーサル横メルカトル図法（ＵＴＭ）等の他のほとんどの２または３次元の座標系で十分である。
【００３４】
高度は多くのアプリケーションに必要なく、場所システムによっては検知しない。そのようなアプリケーションにとって、高度を省略可能な座標系が望ましい。高度が含まれる場合、それは以下のように使用してもよい。
それらは例えば、
・以下に記述されるいくつかの２次元的マッチングのアルゴリズムを３次元に拡張すること、
・例えば勾配および高架交差路を見分けることにより、追加のフィードバックをユーザに与えること、および
・三次元において走行したルートの状況を分析すること、である。
車輌の移動が地球表面に拘束されない場合、例えば、飛行機の場合には、高度を使用することの重要性は増大する。
【００３５】
車輌がそれぞれの場所にある時刻も記録する。場所と、使用するのであれば高度と、時刻との組み合わせを観察と称する。時刻を、今週における秒数として単精度浮動小数点数で保存し、一連の観察群をファイルに保存し、ファイル名をユリウス暦の日とすることで、いずれの観察の絶対時刻の計算も単純なタスクとなる。使用する時刻の基準はＧＰＳ時刻であり、それは国際的な時刻標準ＵＴＣに従うが、計算を簡単にするためうるう秒を含まない。同様にして、ＵＴＣやＴＡＩ等の他の時刻システムも、使用することができる。ＧＰＳの位置の絶対精度は、通常約１０ｍであるが、相対誤差をうまく利用することで、速さ等のデータを計算するときに、大きい量子化誤差を加算しないようにするので、より高精度（１ｍ）で記録することができる。
【００３６】
使用される数の書式は、ＩＥＥＥ７５４単精度であり、チェックとして各観察記録の最後に追加のバイト（改行０ｘ０Ａ）を追加し、どのファイルが破損しても、不適切なフォーマットになっても、検索を支援する。各観察は以下の１７バイトを有する。
０〜３バイト：ラジアン系のＷＧＳ８４の緯度（latという）
４〜７バイト：ラジアン系のＷＧＳ８４の経度（lonという）
８〜１１バイト：メートル系のＷＧＳ８４の高度（altという）
１２〜１５バイト：秒で示す週のＧＰＳ時刻（時刻という）
１６バイト：０ｘ０Ａ（セパレータという）
【００３７】
保存コストをさらに継続して下げ、そしてＧＰＳ等の一般的な位置決めシステムの精度をさらに継続して上げるように、他の実施形態は、倍精度浮動小数点フォーマットや、緯度および経度のマイクロラジアンもしくはミリ度に基づく整数フォーマットや、またはＮＭＥＡ０１８３で使用する度（degree）および１０進法の度等のＡＳＣＩＩフォーマットを使用することを選択してもよい。
【００３８】
観察シーケンスは、「ｙｙｍｍｄｄｘｘ．ｐａｔ」の仕様に従う名前のファイルに保存される。ｙｙは年度の最後の２桁であり、ｍｍは月の指標であり、ｄｄはその月内の日であり、ｘｘは同日に記録される複数のファイルを区別するためにインクリメントされるアルファベットのフィールドである。ファイル名には、そのファイルにおける最初の観察が選択される。例えば、ファイル０３０８２１ＡＡ．ｐａｔと０３０８２１ＡＢ．ｐａｔは２００３年８月２１日に始まったファイルの最初の２つである。
【００３９】
車輌のイグニッションをつけたときは、常に観察が自動的にこれらのファイルに保存され、エンジンを起動するたびに、新しいファイルが作られる。電力面に関して可能であれば、イグニッションを切ったときも、観察が保存され、カー・フェリー行路等の状況をカバーし、またはシステムが少しの動きも見逃さないようにする。この場合、少なくとも毎日、恐らくは毎時間、新しいファイルを始めるのが都合がよい。複数の小さなファイルに観察を保存する理由は、開いたり、バックアップしたり、通信したりすることを容易にし、ディスクまたはファイリングシステム障害に対して復元力を与え、そして限定的リソースで構成したコンピュータシステムで簡単にそれらを操作できるようにするためである。
【００４０】
実装例には、場合によって、データベースソフトウェアの制御下で、ただ１つのファイルに観察のすべてを保存することを選択してもよい。他の情報は、これらのファイルに保存され得る。例えば、観察が参照する車輌の登録番号、運転手の名前、交通情報といった外部的事象、気象情報、観察の後の処理に関連しているかもしれないあらゆる物事を保存してもよい。説明を簡単にするために、緯度、経度、高度および時刻情報だけを含む観察ファイルの例を考察する。
【００４１】
他の事象は、外部ファイルに保存され、ディレクトリ階層のそれらの位置により（例えば、車輌の登録番号の名を有するディレクトリに、ある特定の車輌の観察ファイルのすべてをグループ化することにより）、または、観察の時刻により（例えば、特定の運転手が車輌を始動させ、そして停止させた時刻を記録し、そのときそれらの時間に最も近い観察を検出することにより）、これらの観察と関連付けし得る。
【００４２】
まず、観察ファイルは時刻昇順にソートされ、そのとき場所はその順に各ファイルから、ただ１つの系列を有するリストへ抽出される。抽出処理の一部として、観察はすべての値が実用にかなった範囲内にあるかどうかのチェックを受ける。範囲内にない場合、ファイルの内容全体がリストから除外され、エラーレポートが生成される。また、抽出処理の一部として、リストに保存される観察の時刻を、１９８０年１月１日にＧＰＳ時刻が始まってからの秒数として示し、原初のファイル名との関連性を除去する。
【００４３】
次に、各連続する観察の時刻は前のもの以上であるように、１つのリストをソートする。ポイントを抽出する前に、ソート処理の大半はファイルをその名前によりソートすることにより実施されるので、このソート動作は非常に効果的である。ファイルが車輌追跡や携帯電話追跡等の異なるシステムからまとめられた場合、または時計を調整した場合、そのポイントそれ自身のソートが必要である。最初および最後の観察で規定する範囲、および２つの時刻順に連続する観察間の速さに基づいて、現在適当な範囲外にある観察シーケンスを拒絶することができるので、これはデータのインテグリティのさらなるチェックを提供する。
【００４４】
「前の観察」および「次の観察」という言葉を使用するとき、このただ１つの規則リスト内の位置を参照している。このリストは、連続してlat/lon/alt/時刻/セパレータのシーケンスを含むバイトのただ１つのシーケンスとして、lat、lon、altおよび時刻の個別のシーケンスとして、または観察配列またはリスト、緯度、経度、高度および時刻等のデータ構造として、ディスク又はメモリ上に保存されてもよい。記憶装置フォーマットの詳細な選択は、ソフトウェアが実行される特定のコンピュータの構成により決定されるが、索引またはポインタが後で観察情報を検索するために参照用に使用されるかもしれないので、索引またはポインタにより順次的に観察を検索する基本動作に常に対応する。メモリ内で使用するフォーマットは構造体の配列（記録）である。各構造体は、特定の観察の緯度、経度、高度および時刻を含む。シーケンス内において一番前の観察である第１の要素（要素０）と最新の観察である最後の要素を有する配列は、前述のように時刻順にソートされる。このタイプの構造体は、図２において説明される。
【００４５】
行路は、最初に朝家を出て、後で職場に着く等の２つの重要な事象間のある観察シーケンスである。行路を構成するただ１つの定義もなく、それはユーザ、情況および行路情報がどんな方法で使用されるかにより決まる。車輌がある期間止まっているなら、この期間を「休止期間」と呼び、それぞれの周囲の行路の終了と開始として、休止期間における最初と最後の観察を特定する。
【００４６】
車輌に有効である簡単な行路の一例は、新しい行路の開始として車輌のイグニッショをつける時刻と、行路の終わりとして次にイグニッショを切る時刻を使用する。コンピュータにイグニッション回路の状態またはイグニッショキーの位置を感知させることにより、現在イグニッショがついているか切れているかを検出し、タイムスタンプできてもよい。また、位置決めシステムは、イグニッションをつけている間のみ、観察を生成するためだけに用意されてもよい。従って、観察のない長い期間は、行路間の休止を示すことができる。また、イグニッショがついている間、観察を保存するプロセッサの電源を入れることができ、この場合も行路間の休止として観察のない長い期間を解釈することができる。
【００４７】
イグニッションを切っている間でも位置を生成するシステムに都合がよい他の定義は、車輌がほんの少しまたは全く動いていない期間を探すことである。ここで、直接または２つの連続する観察間の速さを計算することにより測定される車輌の速度が、ある期間（例えば、１分以上）動かない車輌（例えば、１ｍｐｈ）のために測定される最大限の誤差速度により決定されるある閾値より小さい状態である観察シーケンスを行路間の休止として検索し、行路の終了としてシーケンス内の第１の観察に印を付け、行路の開始としてシーケンス内の最後の観察に印を付ける。これには、だれかが小包を配達する間運転手が待つ場合等のイグニッショを切らなくてもよい短い行路を特定可能であること、電車が踏み切りを通過する間等のほんの短い間イグニッショを切る場合に行路を分断しないこと、イグニッショの状態の正確な検出に依存しなくてもよいこと、といった利点がある。
【００４８】
車輌が長期間とてもゆっくり動いている場合、速度ベースの経験則（heuristics）による改良点は、車輌が、ある期間（これをＢｍｉｎといい、一般的に３分）より長い期間において同じ位置のある許容誤差（一般的に５０ｍ）内にとどまる場合、または、Ｂｍｉｎより長く観察同士が離れている場合、シーケンスにおいてすべての期間に印を付けることである。
【００４９】
休止を特定するために使用されるアルゴリズムは、使用中の特定の位置決めシステムの特性に依存する。例えば、ＧＰＳシステムは進行にかかわらず毎秒１つの観察を生成してもよい。この場合、車輌は連続する観察間で５０ｍをカバーするために１１０ｍｐｈ（１８０ｋｍ／ｈ）より速く動かなければならない。従って、休止を特定するために、多くの観察を見なければならない。
【００５０】
適切なアルゴリズムは、時刻に関しＢｍｉｎ離れた観察シーケンスを見て、車輌がその時間にどれくらい遠くに移動したかを見る。例は、次の通りである。
【００５１】
ステップ１：一番前の観察を観察Ａとし、観察Ａと等しい観察Ｘを設定する。
【００５２】
ステップ２：各観察Ａに対して、その観察の時刻が観察Ａの時刻から３分未満である、最も遠い後の観察を検出する。それを観察Ｂとする。
ステップ３ａ：観察Ｂが観察Ｘから５０ｍ未満しか離れていない場合、観察Ａから観察Ｂまでのすべての観察に休止期間の一部として印を付け、観察Ｘは変えず、観察Ａを観察Ａの後の次の観察にする。
【００５３】
ステップ３ｂ：観察Ｂが観察Ｘから５０ｍ以上離れている場合、どんな休止観察も印を付けず、新しい観察Ａおよび新しい観察Ｘを観察Ａの後の次の観察にする。
【００５４】
ステップ４：観察Ａが観察リストの最後に至るまで、ステップ２から繰り返し、そうでない場合は、すべての休止期間の印付けを完了する。
【００５５】
このアルゴリズムは、車輌が非常にゆっくり動いていた（３秒で５０ｍ未満または約０．６ｍｐｈ（１ｋｍ／ｈ））ときでさえ、長い休止に印付けることができる。従って、これは、行路間の見込み休止であるとみなされる。印を付けられた休止期間の例を、図３に示す。
【００５６】
異なる動きが要求され、特定の位置決めシステムのドリフト（drift）及びドロップアウト（dropout）特性に依存する場合、このアルゴリズムへの様々な変更は使用され得る。
【００５７】
見込み休止期間を特定したので、休止期間の間の各移動期間のための行路記録を生成する。この行路記録は、最初の休止期間の最後の観察への参照、および次の休止のちょうど最初の観察への参照を含む。行路記録のための最初と最後の参照がある。行路のラベル付けを、図４に示す。
【００５８】
現在、計算しているアプリケーションにとって、それらの休止のうちのどれが重要であるかを決定した方がよい。
【００５９】
時間内の一番前から始まり、時間内の一番後ろまでずっと、順に各休止期間を検討する。休止期間の時間の長さが、先行するまたは続いて起こる行路の時間の長さより短い場合、およびある閾値（これをＢｍａｘといい、一般的に３０分）より短い場合は、これがより長い行路の途中の一時停止であったという理由で、それらの行路を１つの新しいものにまとめる。これは、図５に示される。
【００６０】
例えば、特に、恐らくガソリンで車を満たすためにまたは近くの店で何かを買うために出かける、５分の運転の後に、６分の停止が続き、その後に５分の運転が続くシーケンスは、２つの異なる行路であると見なされる。恐らく、１時間の運転の後に、ガソリンを入れたり軽食をとったりするために停止する６分の停止が続き、その後に３０分の運転が続くシーケンスは、すべてどこかへ向かう１つの行路であると見なされる。
【００６１】
閾値Ｂｍａｘより短いすべての休止期間が、その休止期間より短い長さの少なくとも１つの行路の横に位置づけられるまで、そのまとめる処理を繰り返す。
【００６２】
行路を特定するために使用される多数の類似した経験則がある。あるアプリケーションにおいて、例えば、異なる経験則を使用することにより、またはＢｍａｘ、Ｂｍｉｎ等のパラメータを調整することにより、行路の定義付けをアプリケーションの特定の要件に合わせて調整するのは、有利である。
【００６３】
例えば、図１７は、より大きな黒い点を使用することにより強調されている各特定される行路の最初の１０個と最後の１０個の観察を有する、多数の観察の地図を示す。行路が特定されるとすぐに、それぞれのためにコンピュータにおいて記録を生成する。この記録は、行路の開始および終了を示すメインリストにおける観察を参照する。これらの観察は、行路の開始および終了の位置および時刻を含む。その行路におけるすべてのポイントを含む最も小さい境界ボックスの緯度および経度を、各行路記録に追加する。この情報は、過去の行路を検索または表示する多数のアルゴリズムの速度を上げるのに使用される。
【００６４】
他の有用な最適化は、リスト全体が最初にソートされるとき、一番前の観察（観察０という）から各観察の累積的な距離を計算することである。このように、ある観察Ｘから観察Ｙまでの累積的な距離は、観察０から観察Ｘまでの累積的な距離を観察０から観察Ｙまでの累積的な距離から減算することにより得られる。従って、多数のささいな計算を減少させる。
【００６５】
また、シーケンスの各部分により示される速さおよび加速度は、さらなる計算および表示に、そして観測結果の正当性チェックとして有用である。５ポイントからなるすべてのグループのために速さと加速度を計算し、これらが車輌の能力の限界のおよびセンサーシステムの特有の誤差特性を示す、一定の正当性の境界内にあるかをチェックする。これらのポイントが正当な境界外になる場合、例えば速さが１５０ｍｐｈ（２４０ｋｍ／ｈ）である場合、または加速度が位置決めセンサの既知の瞬間的な誤差よりも長い距離にわたって１０ｍｓ−２より大きい場合、これらの５つのポイントと、前および後で一般的に１分に相当する多数のポイントも排除する。残ったポイントについて、後の計算に有効と認めたポイントと共に、速さと加速度も、コンピュータメモリ上にキャッシュまたはディスク上に保存することを選択できる。
【００６６】
一致は、一定の方法において、本車輌、他の車両の過去の動きまたは予めロードされた動き例のうちで、本車輌の最近の動きと似たものを検出する。当該一致を検出するのに使用される多数の異なるアルゴリズムがある。ここでは、２つの例がここに与えられ、１つはタイト（tight）であり、１つはルース（loose）である。ルースなアルゴリズムは、現在の行路において一定距離（例えば５００ｍ）後方を見て、車輌が５００ｍ＋−１０％を走行して、その位置から現在の位置まで移動した過去の行路を検出する。
【００６７】
また、タイトなアルゴリズムは、現在の行路において一定距離後方を見て、車輌が最近記録された軌跡の一定の誤差限界（例えば５０ｍ）内に留まりながら、その位置から現在の位置まで移動した過去の行路を検出する。恐らく環状交差か高架交差か、地方道路か高速道路か、または多車線高速道路の異なる車線のどれを使用するかの違いに起因する軌跡の細かな差異を取得できる。
【００６８】
両方の一致アルゴリズムは、最新の観察（観察Ｂという）を取得することから開始し、始まり、走行距離が例えば５００ｍを超える最初の観察が検出されるまで、引き続いて最近の観察シーケンスにおいてさらに後方を見て、次の各観察から走行距離を累積する。これを観察Ａという。今、最新の５００ｍの走行から観察を効率よく選択した。使用中の位置決めシステムの精度をかなり上回って一筋の道路をカバーし（cover）、ほとんどの分岐合流点の横断をカバーするのに十分とするように、５００ｍは選択された。この距離を一致距離Ｍという。一致にどの程度の精度を望むか、車輌および位置決めシステムの特性、または検出される一致の数により、一致距離Ｍを変更することができる。
【００６９】
ルースなアルゴリズムは、現在の行路の最後Ｍメートルの最初および最後の観察を使用して、中間位置を無視する。記録された観察シーケンスにおいて後方を見る。観察Ａから開始し、位置が観察Ｂの位置のある誤差限界（一般的に１００ｍ）内にある観察を検索しながら、逆時刻順に進む。アルゴリズムのこのステージをステージＸという。
【００７０】
観察が検出される場合、観察Ｂの位置の他の誤差限界（一般的に１００ｍ）外にある最初の観察を探しながら、さらに後方に進む。これを候補Ｂという。
【００７１】
候補Ｂから０．９×Ｍより長い累積距離を有する観察に達するまで、観察間の走行距離を累積しながら、後方に進む。これは第１の候補Ａである。
【００７２】
候補Ａの位置が観察Ａの位置の誤差限界（一般的に１００ｍ）内にあるかを判定し、それが誤差限界内にある場合、候補Ｂを現在の位置および最近の動きの潜在的一致として記録する。当該ペアは、候補Ｂ１および候補Ａ１並びに後のイタレーションに関して候補Ｂ２および候補Ａ２として、図６および図７で示される。
【００７３】
候補Ａが観察Ａに十分に近くない場合、各観察を新しい候補Ａとしながら、候補Ａの位置が観察Ａの位置に十分に近いものを検出し、潜在的一致として候補Ｂを記録するまで、または候補Ｂが潜在的一致でないと判断する場合、累積される距離が１．１×Ｍより長くなるまで、記録される観察シーケンスにおいて、引き続きさらに後方に移動する。
【００７４】
いずれにしても、観察Ｂの位置のある誤差限界（一般的に１００ｍ）内に位置するものを検出するまで、観察シーケンスにおいて候補Ｂから後方を見ることにより、再度開始する。
【００７５】
次に、ステージＸから上記処理を繰り返す。
【００７６】
十分な潜在的一致（一般的に１０００）を検出した場合、または一番前に記録された観察まで後方に進んだ場合、アルゴリズムは終了する。
【００７７】
要約すれば、このアルゴリズムは、現在の行路の最後のＭメートルの記録を検出し、最初及び最後の観察（観察Ａおよび観察Ｂ）を取得し、次に、候補Ａは観察Ａに近く、候補Ｂは観察Ｂに近く、候補Ａから候補Ｂまでの走行距離はＭメートルプラスマイナス１０％である候補Ａおよび候補Ｂの観察のため、その記録において後方を見る。記録が空になるまで、または十分なものが検出されるまで当該候補Ａおよび候補Ｂの観察の検出を繰り返す。一致リストという候補Ｂの観察のリストを生成する。アルゴリズムのこのステージをステージＹという。
【００７８】
タイトな一致アルゴリズムは、観察Ａから観察Ｂまでの観察シーケンスからある誤差限界Ｒより外れない候補Ａおよび候補Ｂの間の観察シーケンスを探すことを除いては、同様の方法で動作する。
【００７９】
このアルゴリズムは、まず観察Ａに近い一番前の観察（候補Ａという）を検出することにより動作する。次に、どっちのポインタを動かしたら、２つのポインタが近くなるかを選択することにより、観察Ａおよびこられのポインタ間の距離を最小にするような候補Ａから、時刻順に前方へ２つのポインタを移動する。過去の位置（pastP）は過去の観察において候補Ａと候補Ｂとの間を移動し、現在の位置（currentP）は最新の観察において観察Ａと観察Ｂとの間を移動するので、ポインタをそれぞれ過去の位置、現在の位置という。両方のポインタが、誤差限界Ｒよりさらに離れて移動することなしに、それぞれの最後のポイント（観察Ｂおよび候補Ｂ）に達する場合、観察Ａから観察Ｂまでの最近の道にきっちりと続く候補Ａから候補Ｂまでの従来の道を検出する。従って、一致可能なものの最初の索引のリスト上に候補Ａの索引を記録する。ポインタがどのステージにおいても極端に離れて移動する場合、一致することを中止し、リスト上にこの候補Ａを記録しない。
【００８０】
観察Ａから十分遠くに移動するまで、最後の候補Ａから前方へ移動することにより新しい候補Ａを検出し、これまでたどってきた道を考察する。そして再度、観察Ａに近い次の観察を探す。これが、新しい候補Ａとなる。
【００８１】
観察において、トンネル、他の障害物、他のシステムからの妨害、一時的な電力損失による場所情報の一時的な損失により引き起こされる途絶がある場合、アルゴリズムは、個別的に移動するように過去の位置および現在の位置のポインタにより参照される場所を与える制御方法により、強化される。過去の位置または現在の位置の１つまたは２つの更新のためさらに個別的に移動することができるが、それらはかなりの時間、誤差限界より離れた状態であろうとも、それらは常により近づくように移動しなければならない。
【００８２】
強化されたタイトな一致アルゴリズムにおいて、記録された観察の初めから開始し、観察Ａのある誤差限界内に位置する観察を順方向に検索する。これが、候補Ａとなる。
【００８３】
アルゴリズムのこのステージをステージＺという。
【００８４】
繰り返して候補Ａの後の観察を見て、それが観察Ａの位置により近い場合、新しい候補Ａを生成する。今、その前または後ろの観察より観察Ａに近い候補Ａを有する。候補Ａが観察Ａ自身に達するまでに、時間的にかなり遠く前方へ移動する場合には、すべての一致可能なものを検出して、アルゴリズムのこのフェーズを終了しフィルタリングに移る。
【００８５】
次に、常に観察Ａから観察Ｂまでの道に近いままであり続けながら、位置が観察Ｂのある誤差限界内にある時まで、候補Ａから前方へ観察の道をたどることができるか否かを考察する。
【００８６】
ポインタ間の距離を短く保ちながら、（候補Ａからの）過去の道および（観察Ａからの）現在の道両方に沿ってポインタを前方へ動かすことにより、これを実行する。そのポインタをそれぞれ過去の位置および現在の位置という。現在の位置が観察Ｂに達する場合、一致を検出し、一致可能なもののリスト（一致リスト）に過去の位置を追加する。
【００８７】
最初は、過去の位置は候補Ａを示し、現在の位置は観察Ａを示す。２つの距離、過去の移動距離および現在の移動距離を計算する。過去の移動距離は、過去の位置の後の観察と現在の位置の観察との間の距離、すなわち、過去の位置をその後ろの次の観察を指すように、移動させた場合における、過去の位置と現在の位置の間にある距離である。現在の移動距離は、過去の位置の観察と現在の位置の後の観察との間の距離、すなわち、現在の位置をその後ろの次の観察を指すように移動させた場合における、過去の位置と現在の位置の間にある距離である。
【００８８】
過去の移動距離は現在の移動距離以下である場合、過去の位置を移動させる。これを実行するために、過去の位置を更新し、過去の位置がその後の観察を指すようにする。
【００８９】
また、過去の移動距離が現在の移動距離より長い場合、現在の位置の後の観察を示すように現在の位置を更新することにより現在の位置を移動させる。
【００９０】
このように、過去の位置と現在の位置の距離をできるだけ短くするように試みる。図９から図１１までは、ポインタが一般的なシナリオにおいて更新する方法を示す。
【００９１】
図９において、過去の移動距離は短いので、過去の位置を更新し、再計算し、図１０を与える。現在の移動距離は短いので、現在の位置を更新し、再計算し、図１１を与える。
【００９２】
過去の位置と現在の位置の間の距離は、時々短くなったり時々長くなったり、更新が進むにつれて変化する。ある誤差限界（一般的に５０ｍ）より小さい間は、一致を継続する。誤差限界より大きくなった場合、すぐに一致を中止しない。この理由は、例えば車輌がトンネルまたは木の下を通って走行したとき等、観察において時々ギャップがあるかもしれないことである。それにより、一わたりの道において、一方の道には、観察が存在し、他方の道には観察が存在しないため、距離が誤差限界を超える原因となる。このことを勘案し、過去の位置と現在の位置の間の距離が誤差限界より大きくなり、最後のＮ個の更新の間増大するまで、一致を中止しない。Ｎは一般的に２に設定される。距離は急に２００ｍに増大し、次の２０の更新の間誤差限界より大きいままであるが、２つの連続する更新の間、増大しないのであれば、まだ、道の間の一致とする可能性は残る。
【００９３】
図１２において、現在の移動距離が過去の移動距離未満であるため、現在の位置を移動させ、図１３を与える。現在の移動距離が過去の移動距離以上であるため、過去の位置を移動させ、図１４を与える。現在、現在の位置と過去の位置の間の距離は、閾値（５０ｍ）を越え、それをさらにＮ−１回増大することができるだけである。Ｎ＝２の場合、もう一度だけ増大することができるだけである。現在の移動距離が過去の移動距離未満であるため、現在の位置を移動させ、図１５を与える。現在、現在の位置と過去の位置の間の距離は、再度増大してもよい。従って、さらにＮ−２回（この場合０回）増大することができるだけである。小さくなる前に再度増大する場合、この道を一致から除外する。現在の移動距離が過去の移動距離以上であるため、過去の位置を移動させ、図１６を与える。現在、現在の位置と過去の位置の間の距離は、５０ｍよりは長いが、短かくなった。従って、計数をリセットし、一致を中止する前にさらにＮ回増大できる。この特定例において、別のドロップアウトに達するまで、再度増大しない。なぜなら、現在の移動距離が過去の移動距離以上であるため、過去の位置を移動させ、過去の位置は再度現在の位置の５０ｍ範囲内になるからである。このようにして、トンネルによるドロップアウトをうまく切り抜ける。
【００９４】
また、木等のオブジェクトが原因の両方の道における多数の異なるドロップアウトシーケンスは、同じ方法で切り抜けられる。
【００９５】
一致を中止する場合、または現在の位置が観察Ｂに達したことを検出する場合、再度過去の位置を開始するための新しい候補Ａが必要である。これを検出するために、候補Ａの後の観察を見て、新しい候補Ａを生成する。候補Ａから観察Ａまでの距離が誤差限界より長くなるまで、または候補Ａが観察Ａに達するまで、これを繰り返す。この場合、すべての一致可能なものを検出しており、このアルゴリズムのフェーズを終了する。候補Ａがまだ観察Ａに達していない場合、上記ポイントステージＺから一致処理を継続する。候補Ａが観察Ａに達した場合、一致可能なもののリスト（一致リスト）を完成し、再度これをアルゴリズムのステージＹという。
【００９６】
車輌の来し方に対する依存度を高めるために、一致距離Ｍを、恐らく２ｋｍまで、または現在の行路のいっぱいの範囲までも増加させることができる。
【００９７】
通常、たとえ観察Ｂより前の行路に観察Ａを取得しても、一致距離を使用する。これには、前の行路の最後に取得されたルートの依存を導入するという効果がある。そしてそれは、予測の精度を上げるために有益な付加的依存である。また、当該状況においては、一致距離を、減少させ、現在の行路でこれまで走行した距離にできる。そしてそれは、フィルタリングアルゴリズムにより後で精選される、より多くの潜在的な一致を含む。走行方向に関係なく、そのポイントの周りで生成されるすべての過去の観察から成る一致リストを返すという効果があるので、これは行路の始期において、特に有益であるが、これらは、後で一週間周期の時刻または一日周期の時刻によりフィルタをかけられる。行路が進むと、一致距離は増加し、その後の一致リストは、それまでにたどったルートにさらに依存する。
【００９８】
タイトな一致アルゴリズムとルースな一致アルゴリズムの両方は、時刻順にリスト化した観察記録を前方へ検索または後方へ検索して実行される。また、それらはいくつかの観察を飛ばすことにより最適化され得る。そしてそれは、ちょうど場所システムが低い更新率を使用したかのようである。異なる経験則は、例えばそれらが最後に考察した候補点から少なくともｄメートルであるべきことを要求する、新しい候補点を選択するのに使用され得る。これらの選択が、可能な最大の一致の数を取得し、できるだけ早く１セットの一致を取得し、またはそれらが動くコンピュータシステムのメモリアーキテクチャとアルゴリズムとの相互作用を最大限に利用するために個別的になされてもよい。
【００９９】
ルースなアルゴリズムまたはタイトなアルゴリズムのどちらか一方のステージＹから、時刻、運転情報、気象情報等の他のフィルタを利用して、潜在的な一致の数を減少させることができる。例えば、各候補Ｂが観察Ｂの一週間周期の時刻のプラスマイナス１時間内であることを要求した場合、潜在的な一致がいくつ残っているかをチェックしてもよい。それが十分な一致を残した場合、減少させたリストを新しいリストにする。一週間周期の時刻に対して不十分な数の一致が残る場合、各候補Ｂが観察Ｂの一日周期の時刻のプラスマイナス１時間内にあることを要求したとき、潜在的な一致がいくつ残っているかチェックする。それが十分な一致を残した場合、減少させたリストを新しいリストにする。
【０１００】
一般に生成される行路は当初同じルートを共有するため、時刻ベースのフィルタリングは、それらのルートが分岐する前にそれらを区別するのを助ける。例えば、午前８時の平日の行路の開始は、仕事のための多数の過去の行路と一致してもよい。一方、週末の同様の開始は、買い物や親戚への過去の行路と一致してもよい。
【０１０１】
また、一致リストが十分長い場合、観察の時期によりフィルタをかけてもよい。このように、システムは、職場、学校等の変更のための、運転パターンにおける変更により速く適応する。ユーザからの入力により、古いルートの中止があったことを知れば、当該フィルタリングは強化され得る。当該時期ベースのフィルタリングは、まれな古い一致はいくつかのアプリケーションのために適切に考慮され得るので、後の予測ステージにおける一致リストの重み付けとして適用されてもよい。
【０１０２】
この新しいリストを取得し、そして使用可能な運転手識別情報がある場合、各候補Ｂが観察Ｂと同じ運転手であることを要求したとき、潜在的な一致がいくつ残っているかをチェックしてもよい。それが十分な一致を残した場合、減少させたリストを新しいリストにする。
【０１０３】
このように、多数の他のフィルタを適用できる。ほとんどのＣＰＵおよびメモリの過酷な処理は、一致するタスクを実行することに集中する。どのようなアプリケーションが情報を処理するがに依存して複数の異なるフィルタリングスキームを適用することおいて、利点があるかもしれない。例えば、行路時間予測を生成したい場合、必ず時刻によりフィルタをかけ、最新の行路を優先すべきだが、大きな交通事故が警告の正当な理由となる（warrant）か否かを決定する場合、最新のものと同様にまれな行路を考慮する。
【０１０４】
フィルタをかけた一致可能なもののリストで、関心事の特性を見ることができる。一致リストにおける各一致から、観察シーケンスにおいて前方を見て、車輌で進行している動きが過去において何であったかを調べる。これらの動きは、車輌で進行している動作の現在の時刻からの予測として使用され得る。例として、車輌が毎分その位置を報告することになっている場合、各一致から１分前を見て、そして位置が互いのある誤差限界（一般的に５００ｍ）内にある場合、１分毎に、車輌の予測位置としてそれらの位置の平均を現在位置と共に送信することで、通信帯域幅およびレイテンシを減少させる。１分毎の代わりに２分毎に１つのメッセージを送信しさえすればよい。これは、２分、３分またはそれ以上前を見ることまで広がり、より多くの通信オーバーヘッドが減少される。まれに、その時間よりも前に車輌が予測位置からある誤差限界（一般的に５００ｍ）より大きくそれる場合、最後の位置および予測と共にさらなるメッセージが送信され、状況を修正することができる。
【０１０５】
また、車輌の過去の観察履歴のデータベースを、時折ダウンロードし、遠隔地にて保存しなければならないが、この機能は、車輌とは離れて、車輌から受信される最後の観察から同様の一致アルゴリズムを適用することにより、実行され得る。
【０１０６】
異常な交通状態についての警報を受信する手段がある場合、または恐らく交通渋滞が起こるいつもの時間および場所（問題の箇所）のデータベースにアクセスする場合、車輌がそれらのどれかに遭遇しそうであるか否かを知りたいと思うかもしれない。
【０１０７】
一致リストの各観察から前方へ、その観察を含む行路の最後までを調査することにより、これを行う。それらの行路毎の各ポイントに対して、一致した観察からそこに到達するのにかかる時間またはルート選定ソフトウェアにより予測される時刻に基づいて、そこに到達する時間（３０分以内）にその付近（１００ｍ以内）に交通警報または既知の問題の箇所があるか否かをチェックする。そのような警報がある場合、適切な行動をとれるように次の安全な機会において運転手に警告し、ルート案内や車輌追跡システム等の他のシステムにこの情報を渡す。ルート選定は平均速度計算値で距離を割るような単純なものでよい。ここで、距離は一致した行路から知られる。またあるいは、スマートナビ（SmartNav）システムにおけるトラフィックマスタ（TrafficMaster）で使用されるもののように道路タイプおよび予測交通レベルを考慮に入れる完全なルート検索アルゴリズムであってもよい。
【０１０８】
運転手に交通、ルート、サービス、電話または他の注意を散漫にさせる可能性がある情報を提示したいと思う場合、加速、減速、コーナリングまたは分岐合流点がほとんどなかった時間を見つけるために過去において車輌で進行した動きを見ることが有用であることが分かる。これらの状況が、一致リストにおける大部分の観察において同じ進行期間Ｐで満足される場合、その期間Ｐの始まりは、今後運転手に情報を提示するのに良い時間である。
【０１０９】
逆に、過去において進行した動きのいずれかに対して、注意散漫の痕跡が、すぐに続いて起こるある期間（一般的に運転手が情報を理解するのにかかる時間）にわたってあったか否かをチェックしてもよい。当該痕跡が検出されなかった場合、すぐにその情報を提示する。当該痕跡が検出された場合、情報がとにかく提示するのに十分重要であるか否かを決定するか、もはやとても古いので有用ではないとして情報を捨てるか、または次の予測更新後、処理を繰り返すかしなければならない。
【０１１０】
現在の行路の目的地を予測したいと思う場合、一致可能なものの１つを含む各過去の行路の終点を見てもよい。それらの終点は、相対的な近接性によりクラスタに分類され得る。１つのアルゴリズムが、アルゴリズムの備える固有のクラスタに各ポイントを入れることにより始まる。次に、各クラスタは順番に取得され、各ポイントは他のすべてのクラスタのポイントと比較される。いずれか同士が互いにＰメートル内にあることが検出された場合、それらのクラスタは１つにまとめられる。すべてのクラスタが１つにまとめられるか、または異なるクラスタにおいて互いにＰメートル内にあるポイントが検出されなくなるまで、各クラスタを順番に取得するこの処理は何度も繰り返される。他のこのようなクラスタリングアルゴリズムは、情報科学テキストに記載される。
【０１１１】
今、各クラスタにおいていくつの行路が終了するかを見て、この行路がその中でほとんどの終点を有するクラスタにおけるあるポイントの近傍Ｐメートル内で終了するであろうことを予測する。（地域を名前と関連付ける地名辞典を参照することにより）これを位置のテキスト記述として表現するか、またはクラスタ内のポイントの平均的な位置および最大限の範囲を与える。それが有用である点は、終点の数が一番多いクラスタからそのような予測のリストを生成することができる点である。
【０１１２】
予測目的地が得られれば、ユーザにより入力される目的地に対しすることすべてをすることができる。例えば、交通情報をフィルタにかけたり、ルート選定およびルート案内を実行したり、行路時間とその変動幅を見積もったり等。ただ１つの最も密集したクラスタまたはそれらのうちのいくつかのためにこれができる。ユーザに可能性を示し、１つを選択するかまたはそれら全部を拒絶できるオプションを与える。
【０１１３】
目的地情報を表示する１つの有用な方法は、道路標識に似通った形であってもよいが、それは車輌の以前の動きによって変化してもよい。それは以下のような情報を与えてもよい。
バーミンガムセンタ（Birmingham center） ４０マイル ４５分
エグゾスパン社（Exospan limited） ６７マイル １時間３５分 遅延Ｍ６Ｊ１２
ＮＥＣ ２５マイル ２５分
【０１１４】
運転手はただこれらの案内標識を見ることだけを選択してもよい。またはそれらから音声またはボタンインターフェイスによりそれらから特定のラインを受諾または拒絶することができる。１つのラインを受諾する場合、それは既知の目的地として設定され得る。そして車輌は代わりのルートを計算するかまたは他のシステムに知らせてもよい。１つのラインを拒絶する場合、それはディスプレイから取り除かれ、そしてそれを生成した一致する観察を含む行路は、現在の行路の残りの部分に対する考察から取り除かれ得る。従って、不適切な交通警報を削減し、行路時刻、運転手の行動等の予測の制度を上げる。
【０１１５】
有用な付加的拡張は、時間順とは逆に、過去の観察に対して現在の行路の最近の部分を一致させようと試みることである。現在の行路が観察Ａから観察Ｂまで移動した場合、観察Ｂの近く（ここでもこの観察を候補Ｂという）から観察Ａの近く（ここでもこれを候補Ａという）まで移動した過去の行路区分を検出する。過去の候補Ｂにつながるものを使用することができ、観察Ｂの後今起こるかもしれないことを予測することができる。
【０１１６】
この逆ルート一致は、新しいルートの帰りの区間に使うと非常に効果がある。以前にその方向に走行したことがないかもしれないが、いずれにせよ行きの行路で走行したのと同じ帰り道をたどる。例えば、行路目的地は行きの行路の始点であると予測されてもよく、適した交通情報や代わりのルートが与えられてもよい。
【０１１７】
一般的に、前方向において十分な一致がない（だいたい１０より小さい）場合、逆ルート一致が試みられてもよい。
【０１１８】
走行されたルートがほとんどないときはじめにシステムを助けるため、または初めて新しいルートが走行されるとき助けるため、他の車両から記録されるルートまたはルート選定システムから計算されるルートに沿って創り出される観察を有するシステムをあらかじめ組み込んでもよい。幹線道路ネットワークのためのそのようなあらかじめ組み込まれる観察を持つことは特に効果的である。このような創り出される観察は記録され、実在する観察との一致がどれもよい一致を見つけ出さない場合、最後の手段として使用されるか、またはそれらはすべての一致するサイクルにおいて使用されるが、実在する観察が増加するに従って予測へのそれらの効果を減少させるためには、時期および希少性でフィルタをかければよい。
【図面の簡単な説明】
【０１１９】
【図１】本発明の実施形態を構成する装置を示すブロック図
【図２】行路および行路区分を決定するための観察記録および分析を示す図
【図３】行路および行路区分を決定するための観察記録および分析を示す図
【図４】行路および行路区分を決定するための観察記録および分析を示す図
【図５】行路および行路区分を決定するための観察記録および分析を示す図
【図６】行路区分間の一致を決定するための第１の手法を示す図
【図７】行路区分間の一致を決定するための第１の手法を示す図
【図８】行路区分間の一致を決定するための第１の手法を示す図
【図９】行路区分を一致させるための他の手法を示す図
【図１０】行路区分を一致させるための他の手法を示す図
【図１１】行路区分を一致させるための他の手法を示す図
【図１２】行路区分を一致させるための他の手法を示す図
【図１３】行路区分を一致させるための他の手法を示す図
【図１４】行路区分を一致させるための他の手法を示す図
【図１５】行路区分を一致させるための他の手法を示す図
【図１６】行路区分を一致させるための他の手法を示す図
【図１７】行路分析を示す図
【特許請求の範囲】
【請求項１】
オブジェクトの地理的な場所および当座の時刻を決定するための、場所および時刻決定システムを備えるオブジェクトの将来の動きを予測するための装置であって、
前記装置はプロセッサを備え、
前記プロセッサは、
（ａ）少なくともオブジェクトが移動する間、定期的に場所および時刻を記録し、観察記録を生成し、
（ｂ）最近の観察シーケンスを、前記記録に含まれる以前に記憶した観察と比較することにより、少なくとも所定の距離にわたり前記最近の観察シーケンスと一致する以前の観察シーケンスを明らかにし、もって、最近の観察シーケンスが表す行路区分を、少なくとも前記所定の距離にわたり前記以前の観察シーケンスが表す行路区分と一致させ、
（ｃ）少なくとも前記一致するシーケンスのいずれかにかかる観察に続く後続の観察を検索し、
（ｄ）前記検索で取得した観察から将来の動きに関する予測を少なくとも１つ導出する、ことを特徴とする装置。
【請求項２】
前記オブジェクトと共に移動する構成を有することを特徴とする請求項１に記載の装置。
【請求項３】
前記オブジェクトに取り付けられ、または、前記オブジェクトの部分を形成することを特徴とする請求項２に記載の装置。
【請求項４】
前記所定の距離は、実質的に５００ｍに等しいことを特徴とする請求項１乃至３のいずれかに記載の装置。
【請求項５】
前記地理的な場所は、高度を含むことを特徴とする請求項１乃至４のいずれかに記載の装置。
【請求項６】
前記最近の観察シーケンスは、最新の観察を含むことを特徴とする請求項１乃至５のいずれかに記載の装置。
【請求項７】
前記プロセッサは、前記最新の観察が記録されるとすぐに前記（ｂ）を実行する構成を有することを特徴とする請求項６に記載の装置。
【請求項８】
前記プロセッサは、各Ｎ番目の最近の観察について、前記（ｂ）を実行する構成を有し、ここで前記Ｎは、０より大きい整数値である、ことを特徴とする請求項１乃至７のいずれかに記載の装置。
【請求項９】
前記プロセッサは、前記（ａ）と前記（ｂ）の間に、前記記録を、相異なる行路に分解することを特徴とする請求項１乃至８のいずれかに記載の装置。
【請求項１０】
各以前のシーケンスは、単一の行路を含むことを特徴とする請求項９に記載の装置。
【請求項１１】
一致するシーケンスの数が所定の最大値より多い場合には、前記プロセッサは、前記最近の観察シーケンスに記録された時刻と所定の関係にある時刻が記録された当該一致するシーケンスを選択する構成を有することを特徴とする請求項１乃至１０のいずれかに記載の装置。
【請求項１２】
前記所定の関係は、一日周期の時刻において所定の範囲内であることを特徴とする請求項１１に記載の装置。
【請求項１３】
前記所定の関係は、一日周期の時刻において所定の範囲内であり且つ一週間周期の同じ日であることを特徴とする請求項１１に記載の装置。
【請求項１４】
前記所定の関係は、一日周期の時刻において所定の範囲内であり且つ一週間周期の同じタイプの日であり、前記日のタイプは平日および週末であることを特徴とする請求項１１に記載の装置。
【請求項１５】
一致するシーケンスの数が所定の最小値より少ない場合には、前記プロセッサは、前記（ｂ）において、さらに逆時刻順で、前記以前に記録した観察と前記最近の観察シーケンスを比較することを特徴とする請求項１乃至１４のいずれかに記載の装置。
【請求項１６】
前記最近の観察シーケンスの最初および最後の観察の位置が、前記以前のシーケンスの最初および最後の観察の位置とそれぞれ、第１および第２の量未満だけ異なり、且つ、前記最近の観察シーケンスの中間部にある観察を通じて移動した距離測定量が、前記以前のシーケンスの中間部にある観察を通じて移動した移動測定量と、第３の量未満だけ異なる場合には、一致するシーケンスを明示することを特徴とする請求項１乃至１５のいずれかに記載の装置。
【請求項１７】
前記最近の観察シーケンスの最初および最後の観察の位置が、前記以前のシーケンスの最初および最後の観察の位置とそれぞれ、第１および第２の量未満だけ異なり、且つ、前記最近の観察シーケンスと前記以前のシーケンスとの間で最近接した観察の一対が、第３の量未満だけ異なる場合、一致するシーケンスを明示することを特徴とする請求項１乃至１５のいずれかに記載の装置。
【請求項１８】
前記オブジェクトは、車両であることを特徴とする請求項１乃至１７のいずれかに記載の装置。
【請求項１９】
前記車両は、自動車であることを特徴とする請求項１８に記載の装置。
【請求項２０】
前記プロセッサは、イグニッションキーの使用、シートメモリの使用、ドアの使用、ウィンドウ位置、ミラー位置、送信設定、座席利用率または重さ、選択される娯楽チャンネル、外部温度、内部温度、レインセンサ出力、軸重、けん引棒の使用、交通情報、汚染度、および換気設備の設定のうちの少なくとも１つを、前記（ａ）において記録し、前記（ｂ）において比較することを特徴とする請求項１８または１９に記載の装置。
【請求項２１】
前記プロセッサは、前記一致するシーケンスのそれぞれに対する検索により取得した観察から、予測を導出することにより、前記（ｄ）を実行することを特徴とする請求項１乃至２０のいずれかに記載の装置。
【請求項２２】
前記プロセッサは、前記一致するシーケンスのいずれかにかかる観察の後のオブジェクトの動きを、前記少なくとも１つの予測として導出することにより、前記（ｄ）を実行することを特徴とする請求項１乃至２１のいずれかに記載の装置。
【請求項２３】
前記将来の動きは、少なくとも１つのオブジェクトの採りそうな将来の場所を含むことを特徴とする請求項１乃至２２のいずれかに記載の装置。
【請求項２４】
前記少なくとも１つの将来の場所は、少なくとも１つの採りそうな将来の目的地を含むことを特徴とする請求項２３に記載の装置。
【請求項２５】
前記少なくとも１つの採りそうな将来の場所は、前記最近の観察シーケンスからの少なくとも１つの可能な将来のルートを含むことを特徴とする請求項２３または２４に記載の装置。
【請求項２６】
前記将来の動きは、速さ、停止、ブレーキング、加速、コーナリング、燃料消費、注意散漫レベルおよび疲労度のうちの少なくとも１つを含むことを特徴とする請求項１８乃至２０、または請求項１８乃至２０のいずれかを引用する請求項２１乃至２５のいずれかに記載の装置。
【請求項２７】
人間が感知できる形で少なくとも１つの予測を表示するための出力装置を備えることを特徴とする請求項１乃至２６のいずれかに記載の装置。
【請求項２８】
請求項１乃至２７のいずれかに記載の装置と、前記場所および時刻決定システムの結合体。
【請求項２９】
オブジェクトの将来の動きを予測する方法であって、
（i）少なくともオブジェクトが移動する間、定期的にオブジェクトの場所および当座の時刻を記録し、観察記録を生成するステップと、
（ii）最近の観察シーケンスを、前記記録に含まれる以前に記録した観察と比較することにより、少なくとも所定の距離にわたり前記最近の観察シーケンスと一致する以前の観察シーケンスを明らかにし、もって、前記最近の観察シーケンスが表す行路区分を、少なくとも前記所定の距離にわたり前記以前の観察シーケンスが表す行路区分と一致させるステップと、
（iii）少なくとも前記一致するシーケンスのいずれかにかかる観察に続く後続の観察を検索するステップと、
（iv）前記検索で取得した観察から将来の動きに関する予測を少なくとも１つ導出するステップとを含むことを特徴とする方法。
【請求項３０】
コンピュータを制御し、請求項２９に記載の方法を実行させるプログラム。
【請求項３１】
請求項３０に記載のプログラムを伝える搬送媒体。
【請求項３２】
請求項３０に記載のプログラムの通信路を介した伝送。
【請求項３３】
請求項３０に記載のプログラムがプログラムされたコンピュータ。
【請求項１】
オブジェクトの地理的な場所および当座の時刻を決定するための、場所および時刻決定システムを備えるオブジェクトの将来の動きを予測するための装置であって、
前記装置はプロセッサを備え、
前記プロセッサは、
（ａ）少なくともオブジェクトが移動する間、定期的に場所および時刻を記録し、観察記録を生成し、
（ｂ）最近の観察シーケンスを、前記記録に含まれる以前に記憶した観察と比較することにより、少なくとも所定の距離にわたり前記最近の観察シーケンスと一致する以前の観察シーケンスを明らかにし、もって、最近の観察シーケンスが表す行路区分を、少なくとも前記所定の距離にわたり前記以前の観察シーケンスが表す行路区分と一致させ、
（ｃ）少なくとも前記一致するシーケンスのいずれかにかかる観察に続く後続の観察を検索し、
（ｄ）前記検索で取得した観察から将来の動きに関する予測を少なくとも１つ導出する、ことを特徴とする装置。
【請求項２】
前記オブジェクトと共に移動する構成を有することを特徴とする請求項１に記載の装置。
【請求項３】
前記オブジェクトに取り付けられ、または、前記オブジェクトの部分を形成することを特徴とする請求項２に記載の装置。
【請求項４】
前記所定の距離は、実質的に５００ｍに等しいことを特徴とする請求項１乃至３のいずれかに記載の装置。
【請求項５】
前記地理的な場所は、高度を含むことを特徴とする請求項１乃至４のいずれかに記載の装置。
【請求項６】
前記最近の観察シーケンスは、最新の観察を含むことを特徴とする請求項１乃至５のいずれかに記載の装置。
【請求項７】
前記プロセッサは、前記最新の観察が記録されるとすぐに前記（ｂ）を実行する構成を有することを特徴とする請求項６に記載の装置。
【請求項８】
前記プロセッサは、各Ｎ番目の最近の観察について、前記（ｂ）を実行する構成を有し、ここで前記Ｎは、０より大きい整数値である、ことを特徴とする請求項１乃至７のいずれかに記載の装置。
【請求項９】
前記プロセッサは、前記（ａ）と前記（ｂ）の間に、前記記録を、相異なる行路に分解することを特徴とする請求項１乃至８のいずれかに記載の装置。
【請求項１０】
各以前のシーケンスは、単一の行路を含むことを特徴とする請求項９に記載の装置。
【請求項１１】
一致するシーケンスの数が所定の最大値より多い場合には、前記プロセッサは、前記最近の観察シーケンスに記録された時刻と所定の関係にある時刻が記録された当該一致するシーケンスを選択する構成を有することを特徴とする請求項１乃至１０のいずれかに記載の装置。
【請求項１２】
前記所定の関係は、一日周期の時刻において所定の範囲内であることを特徴とする請求項１１に記載の装置。
【請求項１３】
前記所定の関係は、一日周期の時刻において所定の範囲内であり且つ一週間周期の同じ日であることを特徴とする請求項１１に記載の装置。
【請求項１４】
前記所定の関係は、一日周期の時刻において所定の範囲内であり且つ一週間周期の同じタイプの日であり、前記日のタイプは平日および週末であることを特徴とする請求項１１に記載の装置。
【請求項１５】
一致するシーケンスの数が所定の最小値より少ない場合には、前記プロセッサは、前記（ｂ）において、さらに逆時刻順で、前記以前に記録した観察と前記最近の観察シーケンスを比較することを特徴とする請求項１乃至１４のいずれかに記載の装置。
【請求項１６】
前記最近の観察シーケンスの最初および最後の観察の位置が、前記以前のシーケンスの最初および最後の観察の位置とそれぞれ、第１および第２の量未満だけ異なり、且つ、前記最近の観察シーケンスの中間部にある観察を通じて移動した距離測定量が、前記以前のシーケンスの中間部にある観察を通じて移動した移動測定量と、第３の量未満だけ異なる場合には、一致するシーケンスを明示することを特徴とする請求項１乃至１５のいずれかに記載の装置。
【請求項１７】
前記最近の観察シーケンスの最初および最後の観察の位置が、前記以前のシーケンスの最初および最後の観察の位置とそれぞれ、第１および第２の量未満だけ異なり、且つ、前記最近の観察シーケンスと前記以前のシーケンスとの間で最近接した観察の一対が、第３の量未満だけ異なる場合、一致するシーケンスを明示することを特徴とする請求項１乃至１５のいずれかに記載の装置。
【請求項１８】
前記オブジェクトは、車両であることを特徴とする請求項１乃至１７のいずれかに記載の装置。
【請求項１９】
前記車両は、自動車であることを特徴とする請求項１８に記載の装置。
【請求項２０】
前記プロセッサは、イグニッションキーの使用、シートメモリの使用、ドアの使用、ウィンドウ位置、ミラー位置、送信設定、座席利用率または重さ、選択される娯楽チャンネル、外部温度、内部温度、レインセンサ出力、軸重、けん引棒の使用、交通情報、汚染度、および換気設備の設定のうちの少なくとも１つを、前記（ａ）において記録し、前記（ｂ）において比較することを特徴とする請求項１８または１９に記載の装置。
【請求項２１】
前記プロセッサは、前記一致するシーケンスのそれぞれに対する検索により取得した観察から、予測を導出することにより、前記（ｄ）を実行することを特徴とする請求項１乃至２０のいずれかに記載の装置。
【請求項２２】
前記プロセッサは、前記一致するシーケンスのいずれかにかかる観察の後のオブジェクトの動きを、前記少なくとも１つの予測として導出することにより、前記（ｄ）を実行することを特徴とする請求項１乃至２１のいずれかに記載の装置。
【請求項２３】
前記将来の動きは、少なくとも１つのオブジェクトの採りそうな将来の場所を含むことを特徴とする請求項１乃至２２のいずれかに記載の装置。
【請求項２４】
前記少なくとも１つの将来の場所は、少なくとも１つの採りそうな将来の目的地を含むことを特徴とする請求項２３に記載の装置。
【請求項２５】
前記少なくとも１つの採りそうな将来の場所は、前記最近の観察シーケンスからの少なくとも１つの可能な将来のルートを含むことを特徴とする請求項２３または２４に記載の装置。
【請求項２６】
前記将来の動きは、速さ、停止、ブレーキング、加速、コーナリング、燃料消費、注意散漫レベルおよび疲労度のうちの少なくとも１つを含むことを特徴とする請求項１８乃至２０、または請求項１８乃至２０のいずれかを引用する請求項２１乃至２５のいずれかに記載の装置。
【請求項２７】
人間が感知できる形で少なくとも１つの予測を表示するための出力装置を備えることを特徴とする請求項１乃至２６のいずれかに記載の装置。
【請求項２８】
請求項１乃至２７のいずれかに記載の装置と、前記場所および時刻決定システムの結合体。
【請求項２９】
オブジェクトの将来の動きを予測する方法であって、
（i）少なくともオブジェクトが移動する間、定期的にオブジェクトの場所および当座の時刻を記録し、観察記録を生成するステップと、
（ii）最近の観察シーケンスを、前記記録に含まれる以前に記録した観察と比較することにより、少なくとも所定の距離にわたり前記最近の観察シーケンスと一致する以前の観察シーケンスを明らかにし、もって、前記最近の観察シーケンスが表す行路区分を、少なくとも前記所定の距離にわたり前記以前の観察シーケンスが表す行路区分と一致させるステップと、
（iii）少なくとも前記一致するシーケンスのいずれかにかかる観察に続く後続の観察を検索するステップと、
（iv）前記検索で取得した観察から将来の動きに関する予測を少なくとも１つ導出するステップとを含むことを特徴とする方法。
【請求項３０】
コンピュータを制御し、請求項２９に記載の方法を実行させるプログラム。
【請求項３１】
請求項３０に記載のプログラムを伝える搬送媒体。
【請求項３２】
請求項３０に記載のプログラムの通信路を介した伝送。
【請求項３３】
請求項３０に記載のプログラムがプログラムされたコンピュータ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公表番号】特表２００８−５１２６６２（Ｐ２００８−５１２６６２Ａ）
【公表日】平成２０年４月２４日（２００８．４．２４）
【国際特許分類】
【出願番号】特願２００７−５３０７０８（Ｐ２００７−５３０７０８）
【出願日】平成１７年９月６日（２００５．９．６）
【国際出願番号】ＰＣＴ／ＥＰ２００５／０５４３８６
【国際公開番号】ＷＯ２００６／０２７３５６
【国際公開日】平成１８年３月１６日（２００６．３．１６）
【出願人】（５０７０７８０８３）コタレス・リミテッド (5)
【氏名又は名称原語表記】ＣＯＴＡＲＥＳ ＬＩＭＩＴＥＤ
【Ｆターム（参考）】
【公表日】平成２０年４月２４日（２００８．４．２４）
【国際特許分類】
【出願日】平成１７年９月６日（２００５．９．６）
【国際出願番号】ＰＣＴ／ＥＰ２００５／０５４３８６
【国際公開番号】ＷＯ２００６／０２７３５６
【国際公開日】平成１８年３月１６日（２００６．３．１６）
【出願人】（５０７０７８０８３）コタレス・リミテッド (5)
【氏名又は名称原語表記】ＣＯＴＡＲＥＳ ＬＩＭＩＴＥＤ
【Ｆターム（参考）】
[ Back to top ]