外部アプリケーションへデータを供給するための方法
【課題】外部アプリケーションへデータを供給するための方法が提供される。
【解決手段】移動する対象物が静止している場所を、場所と時刻からなるサイティングの記録を形成すべく定期的に記録される。そして、サイティングの記録は、データが供給される外部アプリケーションによって特定される少なくとも１つの規準に従って分析される。少なくとも１つの規準に合致する記録からサイティングのリストが、外部アプリケーションの使用のために供給される。
【解決手段】移動する対象物が静止している場所を、場所と時刻からなるサイティングの記録を形成すべく定期的に記録される。そして、サイティングの記録は、データが供給される外部アプリケーションによって特定される少なくとも１つの規準に従って分析される。少なくとも１つの規準に合致する記録からサイティングのリストが、外部アプリケーションの使用のために供給される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、外部アプリケーションへデータを供給するための方法に関する。本発明は、また、上記方法を実行するようコンピュータを制御するためにプログラム、このプログラムを記録する記録媒体およびデータ網のような通信路を横切る上記プログラムの伝送および上記プログラムでプログラムされたコンピュータに関する。
【背景技術】
【０００２】
MarmasseおよびSchmandtによる「ユーザ集中型場所モデル」、パーソナル・ユビキタスコンピューティング、2002年、vol.6、pp 318-321、Springer-Verlagロンドン・リミテッド版は、車両またはユーザが或る時間の静止していた場所を書き留めることによって頻繁に訪れる場所を学習するためのシステムを開示する。そして、ユーザは、斯かる場所を名付けるように求められ、名付けられたときにその場所は、予測の候補になる。また、トレーニングフェーズがあり、このトレーニングフェーズでは、研究者によって既に分類されて類別が既知のルートが、使用中の走行モデルに与えられる。しかし、このトレーニングフェーズは、随伴するその特別なモデルによるそのルートの試運転を含むユーザの多くの介在を必要とし、自動化システムには適していない。各ルートのトレーニングデータは、ベイズ・クラシファイヤ、ヒストグラムモデル、隠れマルコフモデルなどの種々のモデルを訓練するために用いられる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
パイオニアによるUS 2002/0161517 A1は、次のものを用いて目的地を予測するシステムを開示する。即ち、(a)ユーザが過去において訪れた目的地、(b)道路マッピングデータベース、(c)現在の走行の最近の履歴、および(d)過去の走行を道路マッピングデータベースに突き合わせることによって構築された走行情報データベースを用いる。しかし、このシステムは、斯かる目的地が識別されて初めて、目的地へ向かって用いられるルートを記録し始めるにすぎない。従って、このシステムは、使用可能になる前に、目的地を識別するためにユーザの介在を全般に必要とする。この文献には、システムが車両のエンジンが停止された場所を定期的に検出し、それを目的地点として記録することができると示唆されている。その後、ユーザが目的地としてその場所を選択すれば、システムは、その場所へのルートを学習し、そのルートを自動的に予測し始めることができると書かれている。しかし、ユーザは、依然として或る段階で目的地としてその場所を手動で選択しなければならない。
【０００４】
EP 0967460 A1は、コミュート(通勤)ルート、つまりドライバが最も頻繁に通る単一ルートを学習するためのシステムを開示する。このシステムは、コミュート中にユーザが時間窓に入力する必要があるか、ディフォールトの時間設定を用い、次いで極最近に用いられたルートを格納すること、由来が未定義の合成ルートを格納すること、または時間窓の間にマッピングデータベースからの各道路セグメントが何度横切られたかを数えることによって、コミュートルートを推論し、最も頻繁に走行された道路セグメントをコミュートルートとするものである。
【課題を解決するための手段】
【０００５】
本発明の第1の態様によれば、請求項１で定義される方法が提供される。
【０００６】
本発明の他の態様および実施形態は、他の請求項で定義される。
【発明を実施するための最良の形態】
【０００７】
本発明を、図示の実施形態により次に説明する。
【０００８】
まず、以降に用いられる用語の意味を解説する。
【０００９】
一連のサイティングによって表わされる運動におけるブレイクとは、サイティングによって表わされる場所が著しく変わらない期間である。測位システムの誤差特性によって生じる僅かなドリフトがあったり、停止されていたり、測位システムの電源が落とされている場合は、サイティングが全くないこともある。
【００１０】
外部位置は、対象物が見つけ出される場所や事象が生じる場所が座標系外であることを表すために用いられる。外部位置は、高度ありまたはなしのユニバーサル横メルカトル図法(UTM)などの地図投影法グリッドの形、世界測地規格1984(WGS84)などの測量基準の緯度と経度の形、または地球中心地球固定(ECEF)のWGS84などの直線の座標系の形で与えられる。
【００１１】
GPSとは、米国の全地球測位システムであり、良好な信号状態下でアンテナの位置を数ｍ以内で決定できる人工衛星航法システムの１つである。また、GPSは、１マイクロ秒以上の精度で時間情報を提供できる。
【００１２】
GPS時間とは、協定世界時(UTC)、つまり地球の毎日の回転に基づく観測上の時間の規格のうちの1つを辿る絶対時刻標準である。GPS時間は、UTCと最大で１マイクロ秒の差があるが、UTCに対して200ナノ秒以内に較正できる。GPS時間は、太陽の周りを回る地球の回転周期に対して調整(閏秒調整)されていないので、UTCと小整数秒の追加の差がある。UTC時間およびGPS時間が秒の主たる尺度を得ている未調整の原子時間尺度は、TAI(国際原子時)と呼ばれていて、TAIからGPSを差し引いた時間は、一定整数秒に非常に近く、1980年にGPS時間が始まったとき、TAIとUTCの差は19秒であった。
【００１３】
走行(journey)とは、走行の両端をなす２つの重要な場所の間の一連のサイティングを言う。このシステムでは、走行を重要なブレイク間の一連のサイティングと定義する。ブレイクが重要であるか否かは、用いられる特定のアルゴリズムとパラメータによって決定されるが、一般に、長期間の運動中の短いブレイクを除外するようにパラメータが設定されている。適切な設定によって、食事のための１時間のブレイクを中途に挟んだ３時間の運転は、単一の走行と見られるが、15分の買い物のための15分の走行とこれに続く帰宅のための15分の走行は、２つの別個の走行と見られる。
【００１４】
事象(event)の場所とは、用いられる座標系で表された事象の生じた場所を言い、例えば、浮動小数点値で表された緯度,経度,高度のWGS84データが用いられる。高度の使用は、オプションであるが、在るとすればソフトウェアの種々の特徴を強化するために用いることができる。
【００１５】
サイティングとは、対象物の位置を、その対象物がその位置で検出された時間と共に記録したものを言う。
【００１６】
サイティングアレイとは、アレイ状に格納された一連のサイティングの記録を言う。
【００１７】
サイティングインデックスとは、サイティングアレイの要素を特定する整数を言う。
【００１８】
ポイントとは、特に選ばれたサイティングインデックスを言い、そのサイティングの場所が、表示画面上の特定の画素にマッピングされると知られているか、所定の場所または時間の近傍などの他の基準によって選択されているものを言う。多くのポイントが同じ画素にマッピングされる一方、例えば昨年得られたサイティングのみが表示されるなど、データベース内の総ての場所がポイントとして表示される訳でもない。ユーザは、マウス、カーソルキーまたは他の入力手段を用いて、ポイントを選択でき、ソフトウェアは、どの場所が選択されたポイントに相当するかを決めることができる。
【００１９】
ポイント組とは、ポイントの順序に関係し、ポイントの複写に関係しないポイントの集合を言う。ポイント組は、より効率的な処理が可能になるなら、昇順にソートされ、複写ポイントが削除される。
【００２０】
ポイントのリストは、それ自身の定義された順序を持っており、複写が重要になることもある。
【００２１】
WGS84とは、1984の世界測地学システムで、GPSによって用いられる基本的座標系を言う。WGS84 は、座標系の原点が地球の重心に(数ｍ以内に)接近するように地球の周りのステーションのための座標を採用して定義された直線の座標系であり、GPSのような衛星に基づくシステムに対して特に有用にされたものである。斯かる座標系は、地球中心地球固定(ECEF)と呼ばれる。地質断層線に沿った移動のような主な妨害がある場合、ステーション座標は、全座標系における不連続を回避するように調節することができる。この座標系のz軸は、国際地球回転観測事業(IERS)によって定義された地球の自転軸に一致し、x軸とyの軸は、採用されたグリニッジ子午線に近い子午線を参照して定義されている。また、座標がWGS84データにおける緯度,経度,高度として表せるような随伴の楕円面がある。
【００２２】
図１は、自動車のような車両に取り付けられ、ROM,フラッシュメモリ,ハードディスクドライブ,光ディスクドライブなどのプログラムメモリ２を備えたコンピュータ１の形をなす本発明の装置を示している。しかし、発明の実施形態は、車両内の使用に限られず、他の対象物に取り付けることができる。例えば、この装置は、その地理的場所および現在時間に関する情報を受信する種類のセル電話や携帯に取り付けることができる。
【００２３】
車両は、車両に搭載されたシステムの多くを監視し,制御する車両電子システム３を含む。従って、コンピュータ１は、以下に述べる車両の現在状況の種々の態様に関する情報を受信できる。
【００２４】
更に、車両には、アンテナ５を介してGPSから受信した信号から車両の位置および現在時刻を決定するためのGPS受信器４が設けられている。この情報は、例えば衛星航法つまり"Sat Nav"システムの機能を提供できるように車両電子システム３にも供給される。
【００２５】
コンピュータ１には、人間が知覚できる出力を提供すべく出力装置６も設けられ、この出力装置６は、例えばSat Navシステムまたは車両内娯楽装置の一部をなすディスプレイの形で図示されているが、これに代えてあるいは加えてスピーカのようなオーディオ出力装置で構成されてもよい。
【００２６】
図１では、コンピュータ１,プログラムメモリ２,受信器４は、別個の部材として示されているが、ディスプレイ６を含む単一の装置によって具体化されてもよい。
【００２７】
使用時に、コンピュータは、車両のサイティングの記録を格納し、このサイティングを車両電子システム３からの車両状態に関する更なるオプションとしての情報と共に処理して、車両の将来の挙動に関する１つ以上の予測をドライバに提供する。サイティングの記録は、過去および現在の車両走行のログの形態をなし、サイティングは、少なくとも<場所,時間>の組を含む。サイティングの記録は、点火キーの使用,使用中の座部メモリ,ドアの使用,窓の位置,ミラー位置,トランスミッションの設定,座席の占有または重量,娯楽チャネルの選択,通話の送受信,外部と内部の温度,車軸荷重,雨センサの出力,牽引棒の使用,交通情報,大気汚染度,換気または空気調和の設定などの他の情報を更に追加されうる。このような情報は、コンピュータ１によって処理されて、例えば、可能な目的地,ルート,速度,停止,ブレーキ,加速,コーナリングなどの走行ログの一部をなす追加情報の予測が出力される。燃料消費,散漫度,疲労などの他のパラメータは、このような予測からコンピュータで計算できる。予測は、極最近のサイティングを、空間的,時間的データを用いて過去の走行ログの一連のサイティングと突き合わせて識別することに基づいている。また、マッチング(突き合わせ)は、点火キーの使用,乗客の数,娯楽装置の設定など上述の付加的データを、これらが車両の電子システム３からコンピュータ１が利用可能になるとき、考慮することができる。
【００２８】
この装置は、車両に取り付けられて権限を与えられると、車両走行に関する情報の記録を開始する。この記録は、特に車両の点火プラグがオンのときなどに頻繁な間隔で搭載されたGPS受信器６ からの車両の場所を記録することによって行われる。毎秒1つの場所データ更新率は、本出願の装置に対して概ね十分であり、50ｍ以内の場所精度が一般に利用できる。WGS84データを用いれば、場所を緯度,経度,高度として１ｍ以内の精度で記録できる。WGS84は、地球全体に亘って定義された良好な座標系であるが、地球中心地球固定(ECEF)のWGS84,英国陸地測量部グリッド,ユニバーサル横メルカトル図法(UTM)などの他の２次元,３次元座標系でも十分である。
【００２９】
高度は、多くのアプリケーションに不要で、幾つかの位置システムでは検出されない。斯かるアプリケーションについては、高度を省略した座標系が好ましい。高度がある場合は、高度は、
・後述する２次元マッチングの幾つかを３次元マッチングに拡張する
・例えば傾斜や高架道などを識別することによって、ユーザに特別なフィードバックを与える
・走行するルートの外観を３次元で解析することなどに用いることができる。
【００３０】
高度の使用は、車両自体が地球の表面を走行するものに限られないなら、航空機などにとってより重要になる。
【００３１】
車両が各場所にあった時刻も記録される。場所と時刻と用いられる場合は高度の組合せは、サイティングと呼ばれる。時刻は、現週内の秒数として単精度浮動小数点数で格納され、各一連のサイティングは、名前がユリウス暦の日で同定されるファイルに格納される。従って、各サイティングの絶対時刻を計算することは単純なタスクである。用いられる時刻基準は、協定世界時(UTC)を辿るが、計算単純化のため閏秒を含まないGPS時間である。UTCまたはTAIなどの他の時刻系も、同様に良好に用いることができる。GPS位置の絶対精度は通常約10ｍであるが、GPS位置をより高精度(1 ｍ)で記録して、GPSのより良い相対誤差を利用し、速度などのデータを計算する際に大きな量子化誤差が加わらないようにしている。
【００３２】
用いた数のフォーマットは、IEEE 754の単精度であるが、各サイティング記録の最後にチェック用の余分バイト(newline 0x0A)を加えて、欠陥ファイルや誤フォーマットファイルを検出する助けにしている。各サイティングは、次の17バイトからなる。
バイト0-3：ラジアン単位のWGS84緯度(latと称す)
バイト4-7：ラジアン単位のWGS84経度(lonと称す)
バイト8-11：ｍ単位のWGS84高度(altと称す)
バイト12-15：秒単位のGPS時刻(timeと称す)
バイト16：0x0A(セパレータと称す)
【００３３】
格納コストを持続的に減じ、GPSのような共通の測位システムの精度を増すべく、倍精度浮動小数点フォーマット、マイクロラジアンまたはミリ度に基づく緯度,経度の整数フォーマット、更にはNMEA 0183規格で用いられる度および１０進度などのASCIIフォーマットを用いた他の実施形態を選らんでもよい。
【００３４】
一連のサイティングは、名前が従来の「yymmddxx.pat」に従うファイルに格納される。ここで、yyは該当年の最後の２桁の数字、mmは該当月の数字、ddは該当月内の該当日の数字、xxは同日に記録された複数のファイルの識別に用いられるインクリメントする英字のフィールドである。ファイル名は、そのファイル中の最初のサイティングの時刻で選択される。例えば、ファイル030821AA.patおよびファイル030821AB.patは2003年8月21日に始まった最初の２つのファイルである。
【００３５】
車両の点火プラグがオンになる場合は常に、サイティングが、これらのファイルに格納され、エンジンが始動するごとに、新しいファイルが始まる。能力が許せば、カーフェリーによる走行などの状況に応じ、あるいはシステムが移動を見落としていないことを確認するために、点火プラグがオフのときも、サイティングを格納することができる。この場合、毎日あるいは場合によっては毎時間、新しいファイルを開始することが便利かも知れない。サイティングを複数の小さなファイルに格納する理由は、サイティングの一部を開き,バックアップし,通信するために容易に選択できるようにし、ディスクやファイルシステムの欠陥に対する回復力を与え、コンピュータが限られたリソースでもって容易にファイルを処理できるようにするためである。
【００３６】
他の実施形態の選択肢は、恐らくデータベース・ソフトウェアの制御下で、総てのサイティングを単一のファイルに格納することである。サイティングが参照する車両の登録番号、ドライバの名前、交通情報,天候などこれらサイティングの後の処理に関係する実に総ての情報も、上記ファイルに格納できる。説明を単純にするため、緯度,経度,高度,時刻の情報だけを含むサイティングファイルの場合を考えることにする。
【００３７】
他の事象は、外部ファイルに格納でき、ディレクトリ階層における事象の位置(例えば車両の登録番号によって名付けられたディレクトリ内の幾つかの特定の車両に対してサイティングの総てのファイルを分類する)によって、あるいは(例えば特定の運転手が車両を発進,停止させ、その時刻に最も近いサイティングを見つけることによる)サイティングの時刻によってサイティングと関連付けられる。
【００３８】
まず、サイティングのファイルは、時間の昇順にソートされ、次に各ファイルから場所が抽出されて、単一順序のリストに格納される。抽出処理の一部として、サイティングは、総ての値が知覚可能な限界内にあることを保証すべくチェックされ、限界内にない場合は、ファイルの全内容がリストから除外され、エラー報告が生成される。また、抽出処理の一部として、GPS時刻の起点が1980年1月1日なので当初のファイル名が最早無関係になるから、リストに格納されたサイティングの時刻が、秒数で表される。
【００３９】
次に、単一のリストは、連続するサイティングの夫々の時刻が、前のサイティングの時刻と等しいか大きくなるようにソートされる。このソート操作は、ポイントが抽出される前にファイルの名前によって一括して行われるので、極めて効率的である。ポイント自体のソートは、車両追跡または携帯電話追跡など異なった系からのファイルを統合する場合、あるいはクロックが調節された場合に必要となる。これは、データの完全性を更にチェックする機会を提供する。なぜなら、最古から最新に至るまでのサイティングのうちで合理的な限界外の一連のサイティングを拒否できるからである。
【００４０】
「前のサイティング」および「次のサイティング」という用語は、順序付けられた単一のリスト内の位置を意味する。このリストは、lat/lon/alt/time/セパレータの遡るシーケンスを含む１つの単一のバイト列、lat,lon,alt,timeの別個のシーケンス、またはサイティング,緯度,経度,高度,時刻のアレイやリストなどのデータ構造としてディスクやメモリに格納されうる。記憶フォーマットの詳細な選択は、ソフトウェアが実行される特定のコンピュータの構成によって決定されるが、インデックスまたはポインタによってサイティングを連続して検索するという基本操作を常にサポートし、後にサイティング情報を検索するために参照としてインデックスまたはポインタが用いられる。メモリで用いるフォーマットは、構造(記録)の配列である。各構造は、特定のサイティングの緯度,経度,高度,時刻を含む。配列は、既述の如く時刻順にソーティングされていて、シーケンスにおける最初の要素(要素0)が最古のサイティングで、最後の要素が最新のサイティングである。この種の構造は、図２に示されている。
【００４１】
走行は、まず朝に家を出て、後に仕事場に着くなどの２つの重要な事象の間の幾つかのサイティングのシーケンスである。何が走行を構成するかについては、走行がユーザとコンテキスト(前後関係)と走行情報が如何に用いられるかに依存することから、単一の定義はない。車両が或る期間の静止している場合、この期間を「ブレイク期間」と呼び、ブレイク期間における最初のサイティングは隣接する走行の終端に、最後のサイティングは隣接する走行の始端に夫々識別される。
【００４２】
車両における走行の単純な定義の１つは、新たな走行の始まりに車両の点火プラグがオンにされる時刻と、走行の終わりに車両の点火プラグがオフにされる時刻を用いることである。点火プラグの実際のオンとオフは、点火回路の状態または点火キーの位置をコンピュータに検出させることで検出して、タイムスタンプを押すことができる。これと択一的に、点火プラグがオンのときのみに、測位システムがサイティングを生成するようにして、サイティングが長期間ない場合が走行の間のブレイクを表すと判定してもよい。また、サイティングを格納するプロセッサを、点火プラグがオンのときだけ電源オンにして、サイティングが長期間ない場合が走行の間のブレイクを表すと判定してもよい。
【００４３】
点火プラグがオフであっても位置が生成されるシステムにおける走行の他の定義は、車両が極僅かに進行するか、全く進行しない期間を探すことである。この場合、(直接測定される,あるいは２つの隣接するサイティング間の速度を計算することによる)車両の速度が、所定期間(例えば1分以上)静止している車両について測定される最大可能誤差速度(例えば毎時１ｍ)で定義される所定閾値以下であるようなサイティングを走行間のブレイクとして探し、そのシーケンスの最初および最後のサイティングを走行の夫々終端および始端とすることである。この定義は、同乗者が小荷物を配達する間ドライバが待っているなどの点火プラグがオンのままの短い走行や、平面交差で列車が通過するのを待っているなどの点火プラグが短時間オフにされるブレイクなしの走行を、点火プラグの状態の適切な検出や記録に頼らずに潜在的に識別できるという利点を有する。
【００４４】
車両が長期間の非常に遅い速度で動いている場合、速度に基づくヒューリスティックの改善は、車両が所定期間(B分と称し,典型的には３分)以上,同じ位置の所定誤差マージン(典型的には50ｍ) 内に滞在するか、B分以上の期間にサイティングのすれがあるようなシーケンスにおける総ての期間をマークすることである。
【００４５】
ブレイクを識別するために用いられるアルゴリズムは、用いられる特定の測位システムの特性に依存する。例えばGPSシステムは、車両の進行に無関係にサイティングを毎秒生成する。この場合、車両は、隣接するサイティング間の50ｍ(所定誤差マージン)を通過すべく毎時110マイル(180km/h)以上の速度で動かなければならない。従って、ブレイクを識別するには、複数のサイティングを横切って見なければならない。
【００４６】
適切なアルゴリズムは、時間でB分隔たったサイティングのシーケンスを、このB分の間に車両が幾らの距離を動いたかを調べることであり、例えば次のようになる。
ステップ１：最初のサイティングであるサイティングAを呼んで、サイティングXにサイティングAをセットする。
ステップ２：各サイティングAについて、サイティングAの時刻から３分以内の時刻の後続のサイティングのうち最も遠いサイティングを見つけ出し、それをサイティングBとする。
ステップ３a：サイティングBがサイティングXから50ｍ未満で離れていれば、サイティングAからサイティングBまでの総てのサイティングをブレイク期間の一部であるとマークし、サイティングXを変更せず、サイティングAの次のサイティングをサイティングAとする。
ステップ３b：サイティングBがサイティングXから50m以上離れていれば、どのサイティングもブレイクサイティングにマークせず、新たなサイティングAとその次のサイティングである新たなサイティングXを生成する。
ステップ４：サイティングAがサイティングのリストの終端に達していなければ、ステップ２から繰り返し、終端に達していれば、全ブレイク期間のマーキングが完了したとする。
【００４７】
このアルゴリズムは、車両が非常に遅い速度(３分で50ｍ以下または約毎時0.6マイル(1km/h)以下)で動いている場合でも、長いブレイクをマークすることができるので、これも走行間の潜在的ブレイクであると考えられる。マークされたブレイク期間の例を、図３に示す。
【００４８】
異なった挙動が必要な場合や用いられている特定の測位システムのドリフトやドロップアウトに応じて、上記アルゴリズムを種々変更して用いることができる。
【００４９】
潜在的なブレイク時間が識別されたので、ブレイク期間の間にある各移動の期間の走行記録が作成される。この走行記録は、最初のブレイク期間の直後にあるサイティングへの参照と、次のブレイクの直前にあるサイティングへの参照を含んでいる。走行記録の始めおよび終わりへの参照がある。このような走行のラベル付けを、図４に示す。
【００５０】
ここで、計算される上記ブレイクのうち、どのブレイクがアプリケーションにとって重要な意義を持つかを決定したい。
【００５１】
各ブレイク期間を、時刻の最も早いものから時刻の最も遅いものへと順々に考察する。ブレイク期間の時間が、そのブレイクに先行または後続する走行の時間よりも短く、かつ、所定の閾値(Bmaxと称し、典型的には30分)よりも小さければ、これは長い走行の途中の一時的停止であるという理由で、これらの走行を合体させて１つの走行とする。これを、図５に示す。
【００５２】
例えば、５分の運転,６ 分の停止,５ 分の運転のシーケンスは、自動車にガソリンを入れるか、近くの店で何かを買うかのために特に外出したと思われ、２つの別個の走行であると考える。１時間の運転,６ 分の停止,半時間の運転のシーケンスは、どこかへ行く途中での給油またはスナック購入と思われ、全体を１つの走行と考える。
【００５３】
上記ブレイク期間に基づく走行の合体は、閾値Bmax未満の総てのブレイク期間の片側に、そのブレイク期間よりも短い少なくとも１つの走行が隣接するまで繰り返される。
【００５４】
走行を識別するために用いることができる多くの同様のヒューリスティックスがあり、幾つかのアプリケーションでは、例えば異なるヒューリスティックを用いたり、BmaxやBminなどのパラメータを調節したりして、走行の定義をアプリケーションの特別な要求に適合させることが有利である。
【００５５】
一旦走行が識別されると、各走行の記録をコンピュータに作成する。この記録は、走行の始めと終わりのサイティングをメインリスト上で参照する。各走行記録には、その走行における総てのポイントを含む最小の境界ボックスの緯度と経度が追加される。この情報は、過去の走行を検索し, 表示するアルゴリズムの迅速化に用いられる。
【００５６】
例えば、図９は、識別された各走行の最初と最後の夫々１０個のサイティングを大きな黒い点で表示した地図を示している。
【００５７】
もう一つの有用な最適化は、全リストが最初にソートされたき、最も早いサイティング(サイティング0と称す)からの各サイティングの累積距離を計算することである。こうすれば、或るサイティングXからサイティングYまでの累積距離は、サイティング0からサイティングYまでの累積距離からサイティング0からサイティングXまでの累積距離を減算することで求まり、多くの小さな計算を省略することができる。
【００５８】
シーケンスの各部分で表わされる速度と加速度も、更なる計算と表示さらには観察の有効性のチェックに有用である。車両の能力とそのセンサシステムに固有の誤差特性が与えられれば、５つのポイントからなる各群に対して速度と加速度が計算され、計算値が所定の有効限度内にあるか否かがチェックされる。例えば、速度が毎時150マイル以上(240km/h)または加速度が10ｍ/s2以上であるなど、位置センサで既知の即時誤差よりも長い距離に亘って、ポイントが有効限度外にある場合、これらの５つのポイントおよびその前後の幾つか(典型的には１分に相当する個数)のポイントは拒否される。残ったポイントについて、有効なポイントをもつ速度および加速度を選択してコンピュータメモリのキャッシュやディスクに格納し、後のコンピュータによる計算に用いる。
【００５９】
サイティングの集合(典型的にはサイティングの記録へのインデックスまたは参照の配列として格納される)を指して「選択セット」という用語が用いられ、その場合、集合中のサイティングのいかなる配列および複製も、重要性を持たない。従って、選択セットは、それに実行される操作に応じて、順序付けありまたはなしのフォーマットで、複製ありまたはなしで格納される。
【００６０】
ユーザまたはアプリケーションソフトによるサイティングの選択は、幾つかの方法で行われる。
【００６１】
サイティングを選択する１つの方法は、ロードされたサイティングのセット内で単にサイティングのシーケンス番号によって行われる。この方法は、サイティングを通して一つずつ進む場合またはサイティングの範囲を時間に遅れずに定義する場合に有用である。
【００６２】
サイティングを選択する別の方法は、サイティングの時刻と日付によるもので、典型的には、与えられた日または時間の中間点に最も近いサイティング、またはこのような２つの日と時刻の間の範囲のサイティングを選択して行われる。これと択一的に、サイティングは、例えば午前９時〜午前１０時または月曜日〜金曜日に総てのサイティングを行うなど日,週または年の単位で繰り返す時間範囲で選択することができる。
【００６３】
その後、サイティングを選択するための位置の使用がある。これらの位置は、他のソフトウェアから入力されるか、あるいはボタンがクリックまたは押し下げられるときの画面上のマウスの位置によって画定される。有用な位置選択モードは、入力された位置に最も(位置が)近いサイティングを見つけるか、入力された位置の周りの特定の領域(矩形または円形)内の総てのサイティングを見つけるか、入力された位置の周りの特定の領域内の最も古いまたは最も新しいサイティングを見つけることである。ユーザがマウスをクリックし,ドラッグして位置を入力するとき、ポイントが選択されるべき領域を表示するカーソルをマウスポインタの周りに描くことは有用である。
【００６４】
上述の総ての選択モードのうちで、特に選択されたポイントがユーザによって選ばれている場合、選択セット内にあるポイントをディスプレイ上でハイライト表示することはしばしば有用である。これと択一的に、走行分析などの機能に対して、選択されたサイティングが一部をなすような総ての走行など選択されたセットのみならずそれ以上をハイライト表示することは有用である。このようなハイライト表示モードは、典型的にはプルダウン・メニューまたはツールバー上のボタンによってグラフィカルユーザインターフェースによって制御される。
【００６５】
総ての選択方法は、それらが適用される毎に新しいポイントのセットを定義できるか、幾つかの独立したアプリケーションに亘ってポイントを累積できるようになっている。
【００６６】
一旦幾つかのポイントが選択されると、選択されたセットからポイントを削除する１セットの対応する操作がある。この削除操作は、ポイント(削除ポイント)の新しいセットを画定するために同じ選択規準を用いる。削除セットに含まれる元のポイントのセットは、総て元のセットから削除される。この削除を行う便利な方法の１つは、マウスの左ボタンで累積選択機能を働かせ、右のマウスボタンで削除機能を働かせることである。そして、広範囲のポイントは、マウスの左ボタンを押し下げたままディスプレイを横切ってマウスを掃引することにより選択することができ、間違って含めたポイントは、マウスの右ボタンを押し下げたままそのポイント上でマウスカーソルを動かすことによって削除することができる。
【００６７】
一旦サイティングのセットが選択で画定されると、検索や予測や他のアルゴリズムを開始または終了するサイティングを設定するなど後の使用のため上記セットを保存(セーブ)する場合が多々ある。続く操作をより容易にするため、選択されたセットが保存されると、サイティングへの参照が、単一順序(例えば、総てのサイティングの時刻順のリストにおけるサイティングのインデックスによる)にソートされ、複製も総て除去される。そして、このリストは、時刻,持続時間,速度またはサイティングのセットから引き出せる他の総ての特性を分析し、検索の開始または終了を設定するユーザによるコマンドを受けて、他のソフトウェアが複製し,操作するために利用できる。
【００６８】
複数の選択されたセットが用いられる場合、全セットを１つのオペレーションで操作できることがしばしば有利である。共通の例は、開始と終了のポイントのセットが用いられる場合である。始点として総てのポイントのセットをロンドンに持ち、終点として総てのポイントのセットをケンブリッジに持つ場合を想定する。最も近い１対の(時刻)ポイントであって、１番目のポイントが開始点のセットに、２番目のポイントが終了点のセットに属するものを見つけ出した場合、始点内の任意のポイントから終点内の任意のポイントへの最速の横断(必ずしも１走行でない)、つまりロンドンからケンブリッジへ行った最速の走行の始点と終点を見つけたことになる。逆のボタンは、始点セットを構成していたポイントが終点セットを構成し、終点セットを構成していたポイントが始点セットを構成するように２つのセットの名前を入れ替える。分析が繰り返されるならば、ユーザがポイントのセットを再選択せずとも、ケンブリッジからロンドンへの最速の横断が見つけられる。
【００６９】
単純な探索は、所定時間範囲内のサイティングを総て調べるか、あるいは或る場所に近いサイティングを調べることを含む。両者とも、規準に合致するサイティングを保持しつつ、各サイティングを順々に調べることによって行うことができる。
【００７０】
これをより効率的に行う方法は、一度に1000個ほどのサイティングについて一連のセグメント・レコードを作成することであり(毎秒１サイティングの割合で約16分間)、各セグメント・レコードは、そのうちの最初と最後のサイティングを参照するとともに、コンピュータ計算で求められ、そのサイティングの総てが含まれる緯度と経度の最小境界ボックスを有している。このセグメント・レコードは、上記走行を記述するために用いられる記録と典型的には同じ構造であり、ポイントの包括的な範囲が必要とされる他の場所でも用いられる。境界ボックスを常に準備しておくことによって、空間座標によるオーバーラップのいかなる計算も、境界ボックスのオーバーラップ領域を最初に計算することによって加速することができる。この好い例は、ディスプレイのためにセグメントを考える場合、セグメントの境界ボックスが表示された区域の境界ボックスと重ならないとき、そのセグメントを迅速に却下できることです。同様に、時間のいかなるオーバーラップも、セグメントによって参照される最初と最後のセグメントの時刻を考慮することによって迅速に決定することができる。
【００７１】
セグメント・レコードを加えることは、或る形態の質問により効率的に答えることを可能にする。この質問とは、例えば、与えられた時間範囲内のサイティングの場所はどこか、典型的には所定場所の周りの円または矩形である与えられた区域内のサイティングの時刻はいつかなどである。
【００７２】
これらの質問自体は、より高レベルの質問に答えるために用いることができる。その例は、ディジタル写真が撮られた時刻頃に作られたサイティングを見つけることである。この時刻は、画像フォーマット中またはファイル作成時刻としてしばしば写真と一緒に格納される。写真の直前および直後のサイティングを見つけ、写真が撮られた時刻に車両や携帯電話や他の追跡対象がどこにあったのかが分かるように地図表示上でハイライト表示するなどしてユーザに示すことは簡単なことである。
【００７３】
各ポイントのハイライト表示を生じさせるように写真の記録を維持すれば、総ての写真の場所をハイライト表示された点として地図上に表示することができる。これは、各写真が撮られた直前および直後に作られたサイティングをハイライト表示することによって行われる。そうすれば、ハイライト表示された場所のユーザによる選択が可能になり、関連する写真を表示することができる。このように、たとえカメラや写真自体が場所情報を含んでいなくても、場所によって写真をブラウズすることができる。
【００７４】
写真の時刻から導き出した場所は、車両または他の追跡対象がその場所の近くにあったサイティングデータベース中の総ての時刻を見つけるためにを用いることができる。そして、それらの時刻は、関連する他の写真や日記記入事項などを見つけるために用いることができる。
【００７５】
写真の相互関係に含まれる一連の操作の例を、図６に示す。このシステムは、次の３つの部分に分けられる。
・ユーザが何を見、何と相互作用したかを反映するユーザ・インタフェース、
・相互関係の詳細な操作を実行するファインダ・アプリケーション、
・ファインダがサイティングデータベースと相互作用することを可能にするサイティング・アナライザ。
【００７６】
最初の操作は(A)であり、ユーザが写真を選択し、同じ場所で撮られた他の写真を見つけるためにファインダ・アプリケーションを起動する。ファインダ・アプリケーションは、一般に用いられるJPEGフォーマットで保存された時刻記録などの写真ファイルから時刻を抽出する。この時刻は、(B)でサイティング・アナライザに渡され、サイティング・アナライザは、その時系列のリストを捜し、(C)で上記時刻の直前および直後のサイティングの場所を返す。(D)において、ファインダ・アプリケーションは、上記２つのサイティングの中間のポイントを取り、このポイントを中心とする一辺500ｍの矩形区域を作る。この区域は、測位システムにおける誤差を考慮して、車両が異なった場所で駐車したかもしれない先行または後続の訪問地を確実に取り囲み、木やビルのような障害物によってもたらされうるサイティング記録におけるギャップを見込んでいる。この区域は、(E)でサイティング・アナライザに与えられ、サイティング・アナライザは、この区域内にある総てのサイティングを選択し、選択したサイティングの時刻シーケンスを次に検索し、(F)で各時刻シーケンスの開始と終了の時刻を返す。そこで、ファインダ・アプリケーションは、総ての写真( または時刻スタンプが押された他のメディア)を調べ、時刻スタンプが上記時刻範囲内にある写真( メディア)を総て選んで、そのようなメディアのリストを(G)で生成する。続いて、ユーザ・インタフェースが(H)で呼び出され、上記リストがファイル名,サムネール,スライドショーなどとしてユーザに示される。
【００７７】
更なる改良は、(D)で一辺500ｍの矩形で始めても、例えば１０個未満といった僅かな写真しか見つからない場合、隣接する１０枚の写真がユーザに示せるまで、矩形の一辺を1km,2km,5kmと順に拡大していくことである。
【００７８】
他の選択肢のうちで、(D)における区域は、円形や長方形または(C)における２つの基の場所に焦点をもつ楕円形にできる。効率的な選択肢は、(C)における２つの基の場所に夫々中心をもつ一辺500ｍの２つの正方形を用い、時刻範囲を抽出する前にサイティングを組み合わせることである。
【００７９】
ユーザが、サイティングがされたであろう時刻を与え、地図上で選択し、座標を与え、あるいは場所が参照できるアドレスや地名を与えることによって場所を記述することができるならば、その場所を検索の原点として用い、その近傍の総てのサイティングを見つけて、それらサイティングに亘る時刻範囲を見つけ、その時刻範囲内で撮られた総ての写真を見つけることができる。
【００８０】
同様のプロセスは、計算機化された日記アプリケーションに適用することができる。日記の過去の記入事項が特定の時刻に「アクメ株式会社を訪問」であるならば、その時刻の近辺でなされたサイティングを再び見つけることができる。これは、サイティングがその近辺でなされたときに過去の他の時刻を見つけるための写真の例と同じ手法を用いて行うことができ、データは、カレンダ上でユーザに対してハイライト表示でき、あるいはユーザが関連する日記のページを順に繰ることができるたとえシステムが「アクメ株式会社」の場所を必ずしも伝えられなくても、その場所を約束の時刻になされたサイティングから推論することができ、同じ会社が訪問された可能性のある時刻を引き出すことができる。
【００８１】
日記プロセスは、図７に詳しく示されている。ユーザは、関心ある時刻または時刻範囲を画定する日記記入事項の選択から始める。(A)で再び時刻を抽出をし、これをサイティング・アナライザに渡す。単一時刻の写真例の場合、日記例は典型的には或る期間に亘って広がる事象(出来事)を調べるので、上記期間はサイティング・アナライザ(SA)に与えられる。SAは、その期間の直前から直後までの総てのサイティングを見つけることができるだろうが、写真例とのもう一つの相違点がある。相違点は、ユーザがその約束場所に日記に書かれた時刻丁度にいなかったかもしれず、特に、時刻よりも遅く到着し、時刻よりも早く出発したかもしれないということである。従って、上記時刻範囲内の総てのサイティングの検索は、場所の精度を鈍らせるような約束場所へのまたは約束場所からの走行の本質的部分を容易に含むうることになる。これに代えて、約束の開始時刻に進行中であった走行セグメントまたはブレイク期間を見つけるように走行セグメントのリストを調べることができる。そして、見つけた走行の終点またはブレイクの始点を、最も可能性のある場所として用いる。同様に、約束の終了時刻にいた最も可能性のある場所として、オーバーラップする走行の始点またはオーバーラップするブレイクの終点(続く走行の始点でもある)を用いる。日記期間に亘る他の走行があるならば、その走行の始点と終点を場所リストに追加するか、例外を設けて、例えば約束の開始と終了をモニターして時刻についてより詳しく入力するようにユーザに頼むことができる。
【００８２】
(C)で場所リストに戻る。ファインダ・アプリケーションは、(D)で写真の場合と同様に１つ以上の囲む区域を計算し、(E)でSAへ総ての時刻範囲を要求する。SAは、(F)で関連する時刻範囲を返し、ファインダ・アプリケーションは、この時刻範囲の夫々を総ての日記記入事項のタイムスパンと比較し、タイムスパンとオーバーラップする総ての日記記入事項を返す。写真アプリケーションとのもう一つの相違点は、長い日記記入事項との短い時間のオーバーラップが重要ではないということである。この例で、2003年6月15日に、ユーザは基の日記記入事項にある場所を通って運転していたであろうが、その場所の近辺に２分間(12:23〜12:24)居ただけである。ユーザがその場所を訪れていた可能性は明らかに少ないか、その場所の近辺に長時間居たかであるので、この時刻範囲は無視される。典型的には、５分未満の時刻範囲および日記記入事項のオーバーラップ期間の１／４ 未満のオーバーラップは無視される。そして、(H)で残った日記記入事項を取って、それをカレンダ上にハイライト表示したり、図７に示すようなハイライト表示した一連の日ページとしてユーザに示す。
【００８３】
これらのプロセスは、100%正確である必要はない。同じ場所で撮られなかったことを示す少数の写真や異なった場所を訪れていたときの日記の時刻は、それらがユーザに有用なヒントの多くの部分を適切にもたらす限りにおいて許される。それは、インターネット・サーチエンジンが、ユーザの質問に関連しない僅かのヒントを作ることを許されているのと同様である。
【００８４】
サイティングの全シーケンスを走行に分割することは、走行の途中の何時,何処にブレイクが入ったかというさらに効率的な質問のメカニズムを与える。走行の始点と終点が一旦分かれば、場所や日時などを含むようにその走行を洗練することができる。例えば、昼食のために停車した場所を英国北部で見つけたいなら、英国北部を囲む緯度と経度の特定の境界ボックス内の総ての走行終点のうち正午から午後２時までにある半時間を超えるブレイク(停止)を捜すことができる。このことは、地図上に表示でき、あるいは近くの場所を調べることによってテキストに翻訳できる可能性を直ちにユーザに提供する。
【００８５】
もう一つの有用な分析は、或るポイントのセットから他のポイントのセットへ車両がブレイクなしで走行したサイティングのシーケンスを総て見つけることである。まず、ユーザは、上述のいずれかの手段によってポイントを選択する。このポイントのセットは、始点として用いられる。次に、ユーザは、終点として記録されるもう一つのポイントのセットを選択する。すると、プログラムは、最初のサイティングから最後のサイティングに至るまでのサイティングの全シーケンスにおいて、同じ走行が後続している開始ポイントを、他の開始ポイントに遭遇する前の終了ポイントによって効率的に検索する。
【００８６】
このような各<開始,終了>ポイント対は、(セグメントとして)格納され、検索は始点を捜すステップに戻る。総てのサイティングの検索が終わると、始点と終点の間を移動する走行セグメントのリストが出来上がる。
【００８７】
効率的というのは、この検索が、始点と終点の対として格納されたポイントのインデックスと走行セグメントのみを用いて行うことができるからである。ポイントのインデックスリストの総ては、まず昇順にソートされる。このアルゴリズムは、総ての中間のサイティングを考慮する必要がなく、始点と終点のインデックスの順序付けられたリストおよび総ての走行の始点と終点を単純に通し検索するだけで済むので、時間的に非常に効率的で、数百万のポイントの集合に適用することができる。
【００８８】
その後、各セグメントは、持続時間,長さおよび走行時間を計算するために分析され、このデータは、１セグメント当たり１行のテキストボックスでユーザに表示される。これらの行は、ポイントからポイントへの走行をどれだけの速度でどれだけ頻繁に行ったかがユーザに一目で分かるように、持続時間の昇順または日付の昇順にソートされる。例えば、異なったルートが用いられた場合、ルートが持続時間でソートされているなら、最も速いルートは、表の先頭に来るので直ちに明白になる。
【００８９】
追加の洗練は、ユーザがこのテキストボックスの１つ以上の行を選択し、その特定のセグメントおよび走行をハイライト表示してディスプレイ上で見ることを可能にする。このような選択の例を、図８に示す。例えば、セグメントの始点の以前の各走行の部分は緑のハイライトで、そのセグメントの始点と終点の間は黄色のハイライトで、そのセグメントの終点からその走行の終点までは赤色のハイライトで夫々表示される。このようにして、ユーザは、ポイント間の走行が最速および最遅であるルートを容易に知ることができる。
【００９０】
従来のルート計画ツールは、典型的にはユーザがルートの始点と終点の場所を選択することを可能にする。本発明のツールは、ルートの始点と終点の夫々から所定範囲(典型的には100ｍ)内の総てのポイントを見つけることによって、始点と終点のセットを自動的に生成する。記録された走行から抽出されたデータは、ルート計画ツールによって予測されたルートおよび持続時間と比較することができる。ルート計画ツールが、ルートが順に通過しなければならない「経由」や「停止」として場所セットを有しているなら、ルート計画ツールは、選択したルートのセグメントが通過しなければならない特別のポイントのセットも生成することができる。
【００９１】
ルート計画ツールは、(連合する終点場所と速度情報をもつ)データベースにおける各道路リンクを考慮し、その道路リンクを横断する走行を見つけるためにこの分析を行なうことによって、より高精度にすることができる。これは、所定範囲(典型的に100ｍ)内のリンクの一端を始点に、この所定範囲内の上記リンクの他端を終点に夫々設定し、上述の総ての可能な走行セグメントを見つけ出し、道路リンクの長さの所定マージン(典型的には20％)内の走行距離であるものだけを保存することによって行うことができる。
【００９２】
接続遅れが一度だけ考慮されるのを確実にするため、接続遅れは、横断の最初また最後の両方にではなく一方のみに加えられる。接続遅れを各横断の最後に加えるには、そのリンクの始点の近傍が残っている最も早い時刻を横断の開始時刻とし、そのリンクの終点の近傍が残っている最も遅い時刻または走行の終点のいずれか早い方を横断の終了時刻とする。
【００９３】
各横断の持続時間は、その横断の曜日と時刻のための道路リンク速度を更新するために用いることができる。
【００９４】
このように、ルート計画ツールは、ユーザの特定の運転スタイルをより良く反映する。いくつかの横断が、同じ道路リンクについて類似の曜日および時刻に見つかった場合、早期の横断は、システムを運転スタイルや道路状況の変化に徐々に順応させるべく無視することができる。
【００９５】
横断の持続時間の変化も、例えば持続時間の標準偏差と分散を計算することによって、道路リンクの変動性を評価するために用いることができ、分散は全ルートに亘って合計して、全走行時間で期待される変動の推定値を与えることができる。上記分散の平方根は、全走行時間で期待される標準偏差の推定値を与える。ルート計画ツールは、ルート時間の推定における１つまたは２つの標準偏差を含み、最低のものを選ぶことによって、悲観的時間が最良であるようなルートを提供するように、あるいは持続時間を分散を含まずに合計し、最低のものを選ぶことによって、平均時間が最良であるようなルートを提供するように構成することができる。
【００９６】
ルート計画ツールは、道路リンクがどれくらい頻繁(かつ最近)に走行されたかを各道路リンクについて書き留めることもでき、ユーザが通常の「最短距離」,「最頻使用道路」,「最速」よりも、いわゆる「最も馴染み」のオプションを選ぶ場合、上記道路リンクに優先度を与えることができる。ユーザが最近走行した道路リンクよりも「余り馴染みのない」や「驚かす」に重みを付けたオプションが実際にあり得る。このような技術について、次に詳細に述べる。
【００９７】
車両用の殆どのルート計画システムは、ジャンクション(接続)用のエントリおよびその間の道路セグメントを含んだデータベースを用いる。ルート計画ツールの幾つかの実例では、接続または道路セグメントは、それらの間の接続性を記述するデータ構造中のポインタとして暗黙に存在し、あるいは、名前,場所座標,道路や接続の種類などの情報を含んだ明示的なデータオブジェクトである。例えば道路が行き止まりなどの場合には、道路セグメント終端は接続でないこともある。このような場合に応じるべく、ルート計画の文脈中で道路セグメントの終端を意味する用語「ポイント」を用いる。道路セグメントが２つのポイントを接続し、１つのポイントが(a)１つ,(b)２つ,(c)２つを超える道路セグメントを持っている場合、夫々を例えば(a)行き止まり,(b)道路の角または他の重要点,(c)接続点と理解する。一方通行や回転禁止などの道路制限も更なるデータとしてコード化される。
【００９８】
単一ペアのルート・プランナは、データベース中のある場所から他の場所、つまりポイントAからポイントBまでの(与えられた規準下で)最適の走行を計画するために道路データベースを用いるソフトウェアである。単一ソースのルート・プランナは、データベース中のポイントAから他の総てのポイントまでの最適の走行を計画する。全ペアのルート・プランナは、データベース中の総てのポイントから他の総てのポイントまでの最適の走行を計画する。これらの各問題に対して異なったアルゴリズムが備えられているが、これらのアルゴリズムの殆どは、馴染みを考慮して次に述べるような修正をすることができる。車両アプリケーションに最も一般に用いられているのは単一ペアのルート・プランナであるので、単一ペアのルート・プランナの説明に専念するが、この技術は非常に広範囲の問題に適用できると理解されなければならない。
【００９９】
これらのアルゴリズムの殆どは、道路網での使用のみに限定されず、グラフ中の各リンクの使用に伴って費用増分が生じるグラフで表現できるいかなるネットワーク上でも一般に作動する。これらのアルゴリズムは、費用が実際の経路長さと全く関係のない抽象的な費用なのだが、「最短経路」のアルゴリズムとしばしば呼ばれる。グラフは、全費用が負であるような循環をグラフ中に有しないものか、最短経路がこのような循環の周りの無限数の走行を含むものに通常拘束される。この技術は、道路網のためのルート・プランナの文脈で説明されるが、他の多くのネットワークに同様に適用できると理解されなければならない。
【０１００】
典型的には可能な多くのルートがあるので、検索は、与えられた規準の下で最適なルートを見つけ出すようにされなければならない。その選択を制御するパラメータは、典型的には全走行時間, 横断される道路の種類または走行の燃料費の或る組合せである。これらは、各道路セグメント毎に漸増的に働く線型の費用関数として通常表現されるが、金銭上の費用ではなく、異なった種類の優先パラメータの相対的重み付けを反映した抽象的な費用である。即ち、費用関数は、特定の道路セグメントを加えたルートの(時間,種類,燃料費に換算した)抽象的費用を計算することができる。この費用関数が与えられれば、全費用が最低のAからBへのルートを見つけるための周知なアルゴリズムがある。ルート・プランナのユーザは、上記費用関数の要素の重み付けを自分の好みに応じて変更する機会をしばしば与えられるので、ルートは、他の要素に対しては必ずしもそうではないが特定の要素に対して最適になる。
【０１０１】
或るシステムでは、与えられた道路セグメントの費用が、時刻に依存することがある。例えば、ラッシュアワーでは他の時刻よりもその道路セグメントを横断するに要する時間が長くなるから、費用関数は、車両が横断する予定の各道路セグメントの時刻に依存する。
【０１０２】
或るシステムでは、全費用関数が、個々の道路セグメントの費用の線形一次結合でないこともある。これは、ルートを見つけるアルゴリズムを、より複雑あるいは時間を要するものにするが、道路セグメントを横断する時間や漸増する燃料費のような基本的パラメータは、各道路セグメントについて依然与えられている。
【０１０３】
次に、各道路セグメントにパラメータとしてどのように馴染みを加え、新しいルート検索の能力を提供する全費用関数にどのように馴染みを組み込むことができるかについて述べる。
【０１０４】
新たな要素は、ルート・プランナが用いている費用関数に、ドライバが各道路セグメントにどのくらい馴染み(または不馴染み)でありそうかを表すものとして導入される。この要素は、典型的にはそれ自体では用いられないが、上述のように計算される各道路セグメントの費用を更に10％または20％だけ変化させるだろう。従って、道路セグメントの費用は、その道路セグメントが非常に馴染みだと思われれば20％だけ減じ、少し馴染みだと思われれば10％だけ減じられる。ユーザが馴染みのないルートを求めていれば、道路セグメントの費用は、非常に馴染みなものは20％だけ増し、少し馴染みなものは10％だけ増される。もちろん、これらの値は代表例であり、馴染みにどれだけの影響力を与えたいかに応じて様々に選ぶことができる。通常、システムは、「非常に不馴染み」(最大で40％の費用増)、「不馴染み」(最大で20%の費用増)、「少し不馴染み」(最大で10％の費用増)、「気にしない」(費用の変更なし)、「少し馴染み」(最大で10%の費用減)、「馴染み」(最大で20％の費用減)、「非常に馴染み」(最大で40%の費用減)といったスペクトルなどの馴染みのレベルを形成する手段をユーザに提供する。
【０１０５】
馴染みのルートは、ドライバが、走行するレーンが狭いか,回転が難しいか,横断歩道があるかなどジャンクションレイアウトに何が来るかについて精通しているので、より安全であるに違いない。
【０１０６】
馴染みのルートは、例えば或る道路は雨が降たり凍たりすると危険になり、或る道路はより空いているとか,より汚染されないとか,有用な停止場所を通るとかいった道路データベース中でコード化されないという理由によって好まれて、頻繁に用いられる。馴染みの概念は、これらや他の多くの個人的好みを明示的にプログラムする必要なく考慮に入れてルート計画を最適化するのに役立つ。
【０１０７】
従来のルート・プランナは、時々道路や交通さらにドライバを全く知らないでルートを計画し、ドライバが幾つかの場所で最適でないことを知っているルートを計画する。そのとき、ドライバは、ルートに通過しなければならない余分なウェイポイントを追加する。これらは、「vias」と時々呼ばれる。十分なviasが一旦置かれれば、これはルート・プランナをしてドライバが望む道を採らせる。このように特定のルートを強いることは、デスクトップのルート・プランナでは煩わしいことであるが、少なくとも全ルートをグラフィックに見ることができ、マウスを用いて好みのルートに沿ってviasを置くことができ、新しいルートを高解像度で地図に表示して確認することができる。ディスプレイと入力手段が制約された車両用のシステムにおいて、これは実際に非常に困難なタスクになり、馴染みあるルーティングは、特に魅力のあるものになる。
【０１０８】
ルート選択を「馴染みのない」ルートの使用に有利なように重み付けすることは、馴染みのルートに問題があり、最近用いていない別の良いルートがあるかどうかを知りたいとき有利である。この重み付けは、例えば同じルートを用いることに厭きたドライバが異なるルートが良いか否かを試したいときにも用いられる。さらに、この重み付けは、休日に毎回異なったルートを用いたため、そのルートが馴染みになり、「馴染みのない」ルートの使用に有利なようにルート選択が重み付けされていれば、そのルートが再び選択される可能性が少なくなる場合に用いられる。このように、AからBまでの一連の走行において、ルーティングエンジンは、異なった馴染みのないルートを毎日示唆し、ユーザは周辺地域をもっと見るであろう。
【０１０９】
各道路セグメントの馴染みのレベルは、0(全く走行せず)から1(代表的な馴染み)の間の実数として一般論の損失なしでコード化することができる。このレベルの解釈は、レベルが費用関数にどのように重み付けするかによって支配される。このレベルは、道路セグメントやそのセットを選択するユーザによって、テキストまたはグラフィックスツールを用いて名前または場所で設定される。あるいは、車両が過去に通った経路が何らかの形で利用できる場合は、その経路から馴染みレベルを計算することができる。
【０１１０】
各道路セグメントの馴染みレベルは、その道路セグメントが、どれくらい頻繁に以前に用いられていたかを考慮する。これに代えてまたは加えて、各道路セグメントの馴染みレベルは、その道路セグメントが、どれくらい最近用いられたかを考慮する。
【０１１１】
道路網の各部分は、典型的にはルート選択処理で用いられる関連する費用関数を有する。費用関数の用い方は、選択された道路網の部分に関連する費用関数をその部分の以前の使用に基づいて変更することである。
【０１１２】
ルート選択は、以前に用いられたことがない道路セグメントに対する優先を以前に用いられた道路セグメントの使用に与える(あるいは、より一般的には、馴染みが低レベルの道路セグメントに対する馴染みが高レベルの道路セグメントの使用に優先を与える)。これと択一的に、ルート選択は、以前に用いられた道路セグメントに対する優先を以前に用いられたことがない道路セグメントの使用に与える(あるいは、より一般的には、馴染みが高レベルの道路セグメントに対する馴染みが低レベルの道路セグメントの使用に優先を与える)。
【０１１３】
考慮されるべき走行は、特定の車両または特定の車両のセット(例えば、配達車両の一団)あるいは特定のドライバ(例えば、自動車キーの機密保護コードまたは適合されたメモリシート設定によって同定される)または特定のドライバのセット(例えば、特定の会社で働く、または家族に属している)によって行われる総ての走行である。
【０１１４】
この方法は、ルートを決めるべき対象物と一緒に移動するように配置された例えば車両搭載装置などの装置によって行われる。この場合、装置は、リアルタイムで対象物の位置の決定を可能にすべく、衛星航法システムを有している。
【０１１５】
或る実施例では、馴染みレベルは、どの道路セグメントが最近横切られたかについてのデータが、例えば地図照合航行システムや位置座標のシーケンスを道路セグメントデータベースに照合させることによって漸増的に供給されることで連続的に保持される。新たな横断が夫々同定されたので、それに応じてその道路セグメントの馴染みレベルが変更される。
【０１１６】
例えば、ドライバが特定の道路セグメントを特定の方向へ何回横断したかを数えることによって馴染み度を計算することができ、計数値を10で割って馴染みレベル１とする。これによって、0〜1までの所望の馴染みレベルが与えられる。その横断がどれくらい最近行われたかを考慮するには、前月にされた横断を夫々１点とし、横断が始まった月から勘定した合計点を１点につき2％で減じる。この時間に関する指数関数形崩壊の使用は、各道路セグメントが計数値(例えば4.5)とその計数値であった日付(例えば2001年1月5日)を保存するだけで済むという点で、エレガントな実行方法といえる。そして、その道路セグメントをｍヶ月(例えば5ヶ月)前に横断して以来全く横断していない場合は、4.5に0.98ｍを乗算して新たな計数値を得て、この場合では2001年1月5日において計数値4.5×0.904=4.07と書き換えるのである。これは、計数値4.5を構成する各要素は、毎月同じ率で崩壊するので、各要素の合計も同じ率で崩壊するからである。
【０１１７】
もちろん、崩壊を滑らかにするために、実際、任意の時間単位(秒またはミリ秒)を用いて表される崩壊の連続的計測を用い、任意の崩壊時間間隔に対する正確な崩壊係数を計算するために、実数冪の指数関数を用いる。ドライバが道路セグメントを横断するとき、上述の指数関数処理によってこの横断時点での計数値をまず計算し、１点を加えて、この横断の直後に新計数値として格納する。
【０１１８】
非常に馴染みのルートが支配的になり過ぎないように、計数値が所定値(例えば10)を超えた場合、計数値を所定値で割って、馴染み指数を0〜1の値に制限する。
【０１１９】
或る期間(10年)よりも古い横断がルーティングに影響しないようにしたければ、(横断後の年数に0.1を乗じる)計算をし、計算結果を１から減じ、減算結果が負であれば０とする代替手法を用いる。この手法では、１年前の横断は別勘定で0.9点となり、９年前の横断は別勘定で0.1点となる。これは、最初１で１０年後に０になる年単位の効果的線型崩壊であり、例えば秒,ミリ秒などの時間の格納に用いられる単位で表された円滑な崩壊関数によって典型的に実行される。この場合、各セグメントについて格納されるデータはより多くなる。その理由は、各過去の横断からの点は、同じ率で崩壊しないからである。むしろ、これらの点は、１０年に達するまでは所定時間間隔当たり一定量で崩壊し、１０年になると０になってそれ以上崩壊しない。この手法による集合点は、各寄与因子が何時１０年に達して崩壊しなくなるかを別に記録する必要があるので、指数関数崩壊の点のように単純には減衰しない。その代りに、各過去の横断の時期を１０年になるまで格納し、１０年になったとき永久に削除する。こうして、要求があればいつでも、与えられた時期から合計点を計算できる。繰り返して言えば、合計点に１０年の制限を設け、１０で割って馴染み指数を得る。１０年よりも若いとマークされた横断を全く持たない道路セグメントを見つけた場合、そのリストと道路セグメントを削除し、その横断が恰もなかったと同じにする。
【０１２０】
ルートが或る道路セグメントを用いようとしているとき、その道路セグメントの馴染みレベルＦを一旦計算すると、この馴染みレベルを費用関数の重み付けに用いる。例えば、道路セグメントが横断されるときの走行時間がＴ秒でその予測増分を表す費用関数がある場合、走行時間Ｔに(1-0.2×Ｆ)を乗じ、馴染み指数が１(非常に高い)の道路セグメントは、恰も20％も速い道路セグメントであるように計算され、横断に0.8Ｔしか要さない一方、馴染み指数が0.2(非常に小さい)の道路セグメントは4％だけ速いと計算され、横断に0.96Ｔを要する。もちろん、この人為的に減じられた横断時間は、人為的に縮小された横断時間は、どのルートが全体として最良なのかを決めるためにのみに用いられる。これは走行に要すると予想される実際の時間なので、ユーザは、最低の費用関数をもつ真の合計横断時間を知らされる。馴染みのルーティングを用いると、最低の全費用関数をもつルートは、最低費用や馴染みの道路使用などに対する好み(優先度)が最速のルートをもたらさないのと同様、走行時間が最短のものではない。
【０１２１】
上述の漸増的費用関数で動作する単一ペアのルート・プランナのための既知のアルゴリズムは、多くある。或るアルゴリズムは、２点の間の距離は２点を結ぶ直線が最短であるなどの道路網に関する特別の知識を利用している。例えば、「Dijkstraのアルゴリズム」は、ごく僅かな拘束下でグラフ上の１点から他の総ての点への最適ルートを見つけ出す周知の方法である。負の長さや横断時間のない道路に適用する場合、選択された１点への最適ルートが決まったとき、計算を停止させる特別の終了チェック手段が追加される。
【０１２２】
別の種類のルータは、C.Y.リー「経路接続性およびその出願用のアルゴリズム」、IRE会報 電子計算機について、Vol.10, No.3、1961年9月、pp.346-365 に記載された「リー・ルータ」に類似している。
【０１２３】
このようなルータにどのように馴染みを加えることができるかを示すため、まず単純なルータの操作について述べ、次に、馴染みがパラメータとしてどのように加えられるかについて述べる。そして、ルータに加えることができる典型的な最適化を述べ、この最適化が馴染みを組み込むためにどのように適合されるかについて述べる。これら総ては、この技術を用いた殆どのルータに馴染みがどのように加えられるかを示す実施例である。
【０１２４】
この実施例ルータは、所定の点Aから他の所定の点Bへの最速の予測走行時間をもつルートを見つけるために用いることができる。この手法の概要をアルゴリズムA1で述べ、追加の重要かつ周知の最適化をアルゴリズムA2で述べて、馴染みを如何に改善されたルータに組み込むことができるかを示すことにする。
【０１２５】
アルゴリズムA1
このルータは、始点(点A)から出る総ての道路セグメントを、各道路セグメントの終点への到着時刻が最も早いものに注意を払いつつ検査することによって動作を開始する。この終点での最も早い到着時刻を最早到着時刻(Te)と呼ぶ。ルータは、決して拡張されない点Bを除いて最初は総て拡張されるのを待っていると設定される点が、夫々拡張されるのを待っているか否かにも注意を払う。まず、始点(点A)は拡張されるのを待っていないとマークされる。次のステップは、ステップSと呼ばれる。ステップSで、ルータは、最早到着時刻(時間Te)が既知で、かつ、拡張されるのを待っている点を調べる。そして、そのような点が見つかると、この点を点Pと呼ぶ。このステップは、通常、拡張されるのを待っている点およびその点の最早到着時刻TeをTeの昇順に並べたリストを保持することによってより効率的に行われる。次に、ルータは、点Pから出る各道路セグメントを夫々独立に検査し、点Pから点Qへの道路セグメントの横断時間(Tpq)を点Pでの最早到着時刻(Te)に加えてセグメントの他端(点Q)で予測される到着時刻(Tc)を計算する。つまり、Tc=Tpq+Te。他端の点Qについて格納された最早到着時刻がない場合または格納された最早到着時刻が計算された到着時刻Tcよりも大きい場合、点Qについて格納された最早到着時刻をTcとし、点Qを拡張されるのを待っているとマークする。状況によっては、以前の繰り返し処理で点Qが拡張されるのを待っていないとマークされうるが、より早い到着時刻が見つかったとき、再び拡張されるのを待っているとマークされる。次いでアルゴリズムはステップSに戻って繰り返される。
【０１２６】
このアルゴリズムは、終点(点B)が最早到着時刻(Te)でラベル付けされ、かつ、拡張されるのを待っているとマークされた他の総ての点が、点Bの最早到着時刻よりも遅い最早到着時刻をもつとき、終了する。この条件は、拡張されることを待っている点およびその点の最早到着時刻TeをTeの昇順に並べたリストを保持していることを再び有利に用いてステップSでチェックされる。
【０１２７】
馴染みを組込むには、道路セグメントの横断時間を既述の馴染みに依存する百分率によって変更することで十分である。これは、横断時間を、横断時間と馴染みの両方に依存する抽象的な費用関数に有効に変える。そして、アルゴリズムは、走行時間と馴染みの全体的組合せに対して最適なルートを提供する。これは、最適ルートがAとBの間の最速ルートでないにしても、最速ルートよりも馴染みがあり、全横断時間として長すぎないことを意味する。もちろん、馴染みで修正された横断時間から計算された最早到着時刻は、真の時刻であり得ない。ルート・プランナの出力が、横断時間または全時間を含んでいるなら、修正された横断時間から最適ルートが一旦求まったとき、真の時刻を導き出すために修正されていない横断時間を用いればよい。
【０１２８】
終了に際して、最短時間ルートは、点Bから逆方向へ道路セグメントに沿って辿ると、Teが減少し、２つの終端でのTeの差(点QのTe−点PのTe)が(既知の算術誤差の範囲内で)その道路セグメントをPからQに向かって横切る横断時間に等しくなることによって見つけられる。こうして、Teは点Aに達するまで減少し、そこで逆トレースが終了する。逆トレースの横断時間の合計は、(既知の算術誤差の範囲内で)Teの差の合計、つまり点Bにおける最早到時刻から点Aの出発時刻を減じた値に等しいことが確証され、逆トレース経路はAからBへの最速ルートでなければならない。
【０１２９】
算術誤差を定量化するのが難しい場合の逆トレースに代わる手法は、点Qに対して新しいTe値が出る毎にこの値を格納し、この値の変化をその拡張がもたらした点Pの指数(インデックス)をQと一緒に格納することである。そして、終了後、点Bは、ルート中の前の点を表すような指数を持ち、前の点はその前の点を表すような指数を持つから、点Aに至るまでこれを繰り返せば、全ルートが再構築されることになる。
【０１３０】
このアルゴリズムは、時間に代えて正値費用関数と共に用いることができ、その場合、各道路セグメントは、それを用いるための費用増分(コスト・インクリメント)でラベル付けされ、結果のルートは、点Aと点Bの間の最小費用ルートである。幾つかの道路セグメントの費用は、全費用が負の道路網において可能な循環がない限り、負になりうる。
【０１３１】
地理的に見た場合、拡張されるのを待っている点群は、(非常に大まかに言って)始点Aを中心にして半径が全方向に均等に延びる円をなす傾向がある。これは、終了条件が満たされるとき、点Bから点Aと反対側にある道路セグメントについての計算時間が非常に節約されることを意味し、このような計算は、大抵の場合、労力の無駄であるが、格別に速い点Bへの直接道路に希にヒットすることがある。
【０１３２】
アルゴリズムA2
このルータにおける上述の無駄な計算を避ける助けになる通例の最適化は、ステップSで、Tzを点Pから終点Bまでをデータベース中の最速の道路セグメントの速度で直線走行するに要する時間として、(Te+Tz)が最小値になるような点Pを見つけることである。これは、各点の地理的座標が必ず既知で直線距離が計算でき、データベース中の総ての道路セグメントについて最速の横断速度を既に必ず見つけていることを意味する。この最速の横断速度は、最良の結果を得るべく、各道路セグメントの終点までの直線距離をその道路セグメントの横断時間でコンピュータ除算して求められる。繰り返して言えば、拡張されるのを待っている点を(Te+Tz)値で順序付けてリストに保持することによって、より計算を効率的にするのである。
【０１３３】
さて、地理的に見た場合、拡張されるのを待っている点群は、始点Aを中心にし、計算された最速に対するその道路の平均速度の比に依存して点Bに向かって延びる概ね楕円をなす傾向がある。そして、終了条件は、拡張されるのを待っている総ての点の(Te+Tz)値が、点Bについて見つかった最早到着時刻(Te)よりも大きいことである。この終了条件が満たされると、拡張された点群は、最適化されていないインク汚点ルータにおけるばあいよりも遙かに少ないので、最適化されたルータは、より速く動作し、消費電力がより少ない。
【０１３４】
この最適化されたアルゴリズムに追加の費用関数として馴染みを用いたい場合、各道路セグメントの横断時間を、既述の如く馴染みレベルに依存した百分率で単に修正するだけで済む。しかし、最適化されたこのアルゴリズムA2の場合、データベース中の総ての道路セグメントについて最大修正横断速度を、各道路セグメントの始点から終点までの直線距離をそのセグメントの修正横断速度で除して求めなければならない。こうすると、しない場合よりも最大速度が少し高くなる一方、アルゴリズムの調べる点が、馴染みの重み付けをしない場合に比して少し増える傾向がある。
【０１３５】
馴染みのないルートを捜す場合は、走行時間を人為的に所定百分率だけ増やした馴染みレベルが用いられるので、各道路セグメントで遭遇する最大速度は、少し減少する。従って、最適化されたアルゴリズムは、少し速く動作する。
【０１３６】
ルーティングアルゴリズムには、例えば事前のコンピュータ計算や時刻(１日における時刻)によって変化する横断時間の処理などを含む他の多くの変形例があると理解されなければならない。これらの変形例にも、アルゴリズムA2で述べたと類似の方法で、馴染みを考慮させることができるが、費用関数のみならずルータが依存する仮定を変更することにも注意しなければならない。
【０１３７】
このように馴染みに順応したルータは、殆どの場合、既存のルータのアプリケーションに代えて用いることができる。例えば、所定の目的地へのルートを計算し、最小費用ルートを動的に再計算し、あるいは更に幾つかの地点を必ずしも順番にではなく訪れる(例えば、巡回セールスマン問題)最小費用を計算する車両搭載のナビゲーションシステムに用いることができる。これらのルートの総ては、どの道路セグメントが(可能なら)何時横断されたかをオンボードで観察することから導き出される馴染みによる費用関数を適用することによって、或る部類のドライバに対して改善されることができる。
【０１３８】
同様に、フリート(一団)ユーザに対する集中ルート選定は、一団の車両がどこを走行しているかについての(ライブまたは一括の)情報入力をしばしば備え、この情報が費用関数の馴染みの追加に用いられる。車両がその位置を報告してこない場合でも、車両へ送出されるルートを用いられた道路セグメントを推定する強力なヒントとして用いて、再び馴染みレベルを計算することができる。フリート・マネジャが、全フリートおよび配達スケジュールに亘って最適化を行っていれば、各ドライバに対する馴染みの組み込みは、熟知のルートにドライバを確実に割り当てる助けになる。不馴染みによるあるいは人手による馴染み設定オプションは、ドライバが新しいルートを学びことを希望する場合や配達スケジュールが厳しくない場合に用いることができる。
【０１３９】
デスクトップコンピュータまたは携帯情報端末用のルートプラナは、非常に流行しており、馴染みルーティングから大きな利益を得ている。ここでは、全区域または全道路を馴染みに設定する手による馴染み入力が行われている。より良くは、車両がどこを通ったかを記録でき、その記録をリアルタイムまたは後に一括で、ワィファイ(Wi-Fi),ＧＭＳ(Global Systen for Mobile Communications)データ,ＧＰＲＳ(General Packet Radio Service)などの通信リンクを介する送信またはコンパクトフラッシュ（登録商標）やＳＤメモリなどのリムーバブルメモリ媒体を用いて情報処理装置に利用できるように特別に変更された車両が増えてきている。
【０１４０】
これらは、ルーティングアルゴリズムがどこで用いられるのかを示す例であるが、この技術は、馴染みに関する情報が利用できる総てのルータに適用することができる。
【０１４１】
ここで、２つの例によってどのようにして道路セグメント横断情報が得られるかを述べる。
【０１４２】
サイティング履歴のマッチング
１つの方法は、車両のサイティング(例えば、<緯度,経度,高度>)の履歴を、大多数のGPS衛星測位受信器で用いられているWGS84緯度,経度が通例である座標系に保存することに基づいている。ルート計画データベース中のどの道路セグメントがいつ横断されたかを見つけ出すため、まず、各道路セグメントの終点をそのセグメントの代表として取り上げ、非常に長いセグメントでは、それに沿って100ｍごとに余分に点を設ける。この例では、一方の端点を選んで、この点をP1と呼ぶ。そして、P1から離れる順に一連の中間点P2,P3,…,Pn(他方の端点, nは点の総数)を選ぶ。次に、測位システム(この例ではGPS)の誤差を補償すべく各点から50ｍ以内のサイティングを総て考慮しつつ、選んだ各点の近傍に匹敵するサイティングの履歴を調べ、サイティングの各シーケンス中で最も近いサイティング(大抵の場合、点からの距離が10ｍ以下）をその点に対して匹敵するものに選ぶ。そして、マッチ(匹敵)した２つのサイティングの間に記録された一連のサイティングの総てがその道路セグメント自体に近いままであるか否かを調べる。これを調べる方法は２つあり、１つであるルーズマッチング法は、マッチした一連の点の間の累積距離を道路データベースから分かるその道路セグメントの長さと比較する。累積距離が道路データベースの距離の±10％以内であれば、マッチしたとして受け入れる。横断の方向は、サイティングの時刻から導き出す。即ち、P1のマッチがPnのマッチよりも早いなら、P1からP2への横断であり、そうでなければ、PnからP1への横断であるとする。もう１つのタイトマッチング法は、P1のマッチとPnのマッチの間にある一連の点総てが、その道路セグメントの或る部分の誤差限界(典型的には、GPSに基づくサイティングに対して50ｍ)内にあるか否かをチェックする。このタイトマッチング法は、道路レイアウトが変化すると進路が著しく変化する長い道路セグメント(例えば500ｍ以上)に対して好適に用いられ、道路セグメントの全長が著しく変化しない場合でも、進路の著しい変化を識別することができる。
【０１４３】
このマッチングアルゴリズムは、新たなマッピングデータベースがインストールされた場合は常に、新しい道路データベースに対して車両からのサイティング履歴を作動させることによって一括モードで実行できる。同様に、或る車両から他の車両へサイティング履歴が移された場合、これら車両は全く異なる道路データベースを持ちうるので、馴染みレベルを決めるべく、新しい道路データベースに対してサイティングのリストをマッチングさせることができる。
【０１４４】
リアルタイムのサイティングが利用できる場合、アルゴリズムは、サイティングが入力されると作動できる。この場合、最近のサイティングの位置が用いられ、道路データベースは、このサイティングの位置に最も近い道路を抽出するように調べられる。一連のサイティングについてこの処理が終了すると、道路が比較され、一連のサイティングの総てが十分広い範囲(例えばセグメント長の1/2以上)に亘って同じ道路セグメントにマッチすれば、この道路セグメントに一連のサイティングが最も良くマッチする方向への１の馴染み度を与える。このとき、同じ道路セグメントに留まる限り測位システムの誤動は馴染み度を１回を超えてインクリメントし得ないという理由で、所定期間(典型的には10秒)にこのセグメントから50ｍ以上離れた位置を見つけるまでは、上記道路セグメントは上記方向に再度インクリメントされないことを書き留める。
【０１４５】
道路の直接マッチング
多くのナビゲーションシステムは、道路データベース自体を推測航法システムにおける拘束として用いることによって動作する。推測航法は、典型的には、走行距離を与える車両の路程計からのパルスと、あらゆる回転の角度を与える角度センサからのパルスを用いて行われる。他に赤外線による道路面観察と磁石方位測量を用いて行うこともできる。これらのシステムは、まず、車両がいる道路セグメントとこのセグメントに沿った車両の位置と走行の方向を知る必要がある。これは、車両が動いていた最後の時間から思い出すことができる。車両が行方不明になった場合、これらは、短い一連のGPS位置を取り、これらの位置に最も近い道路セグメントを見つけることによって導き出せる。GPS位置は、各セグメントの所定誤差限界(例えば50ｍ)内にあるかを調べられる。セグメントに沿う位置は、セグメント内の最後のGPS位置に最も近い点として、セグメントに沿う走行の方向は、セグメント内の最初のGPS位置に最も近い点から最後のGPS位置に最も近い点への方向として夫々導き出される。この分析で最も適合するセグメントがどれであろうと、それが最適のセグメントとして選ばれる。車両が路程計のパルスから移動していることが知られていれば、GPS位置は、数秒離れて取られ、道路セグメントとのマッチングが失敗したときは、GPS位置の新たな組によってマッチングが繰り返される。
【０１４６】
一旦、最初のセグメントと位置と方向が推定されれば、車両が現在の道路セグメント上にあるという仮定の下に路程計の読みから、次の位置が導き出される。位置誤差の見積もりは、車両が進むにつれて増加する。角度センサが著しい回転を示した場合、このような回転が推定位置の誤差限界内にあるか否かを調べるべく、道路データベースがチェックされる。そして、誤差限界内にあれば、データベースからその位置は回転位置だと推定され、回転の角度に応じて新たな道路セグメントが選択され、車両が進んでいる新たな道路に沿う位置を導き出すために、再び路程計が用いられる。このアルゴリズムがどの段階で失敗しても、データベース内の別の始点を見つけるため、再びGPSを用いることができる。
【０１４７】
大抵の地図マッチングシステムは、上で述べたよりも複雑化されているが、車両がどの道路セグメントを横切っているかの情報によって大抵の場合動作している。従って、地図マッチングシステムは、横断がされているときはいつもそれに注目して、１点を計数し、馴染み度の計数および馴染みレベルを導き出すべく、上述のアルゴリズムを適用することができる。
【０１４８】
地図マッチングが失敗して、測位のためにGPSを用いる理由には、車両がデータベースにない道路を用いていることもある。この場合、GPS位置は、サイティング履歴のマッチングで述べたように、後のマッチングのために更新に備えてデータベースに格納される。地図マッチングが働いているときは、各道路セグメントについて馴染みレベルとその更新に必要なパラメータ(例えば、計数値)を格納するだけで済む。この場合、地図データベースが更新されるとき、より問題が生じうる。新たに加えられた道路に新たな識別番号を与えるとか、検索精度を上げるためにデータベースを再度セグメント化するとかして、新たに加えられた道路を上手く処理する必要がある。その場合、古い道路セグメントを、サイティング履歴と同様に、新しい道路セグメントと照合する必要があるが、サイティングが与えるような全詳細は不要である。より良い実行方法は、サイティングを、GPSおよび/またはマップマッチングから導き出される座標として保存し、馴染みレベルの再計算が必要になったときにいつでも、保存したデータを新データベースとの一括照合に用いることである。
【図面の簡単な説明】
【０１４９】
【図１】図１は、本発明の実施形態を示す概略ブロック図である。
【図２】図２は、サイティングの記録および走行と走行セグメントを決定する分析を示す図である。
【図３】図３は、サイティングの記録および走行と走行セグメントを決定する分析を示す図である。
【図４】図４は、サイティングの記録および走行と走行セグメントを決定する分析を示す図である。
【図５】図５は、サイティングの記録および走行と走行セグメントを決定する分析を示す図である。
【図６】図６は、相互関連する写真のステップを示すフロー図である。
【図７】図７は、相互関連する日記記載事項のステップを示すフロー図である。
【図８】図８は、走行分析を示す図である。
【図９】図９は、走行分析を示す図である。
【技術分野】
【０００１】
本発明は、外部アプリケーションへデータを供給するための方法に関する。本発明は、また、上記方法を実行するようコンピュータを制御するためにプログラム、このプログラムを記録する記録媒体およびデータ網のような通信路を横切る上記プログラムの伝送および上記プログラムでプログラムされたコンピュータに関する。
【背景技術】
【０００２】
MarmasseおよびSchmandtによる「ユーザ集中型場所モデル」、パーソナル・ユビキタスコンピューティング、2002年、vol.6、pp 318-321、Springer-Verlagロンドン・リミテッド版は、車両またはユーザが或る時間の静止していた場所を書き留めることによって頻繁に訪れる場所を学習するためのシステムを開示する。そして、ユーザは、斯かる場所を名付けるように求められ、名付けられたときにその場所は、予測の候補になる。また、トレーニングフェーズがあり、このトレーニングフェーズでは、研究者によって既に分類されて類別が既知のルートが、使用中の走行モデルに与えられる。しかし、このトレーニングフェーズは、随伴するその特別なモデルによるそのルートの試運転を含むユーザの多くの介在を必要とし、自動化システムには適していない。各ルートのトレーニングデータは、ベイズ・クラシファイヤ、ヒストグラムモデル、隠れマルコフモデルなどの種々のモデルを訓練するために用いられる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
パイオニアによるUS 2002/0161517 A1は、次のものを用いて目的地を予測するシステムを開示する。即ち、(a)ユーザが過去において訪れた目的地、(b)道路マッピングデータベース、(c)現在の走行の最近の履歴、および(d)過去の走行を道路マッピングデータベースに突き合わせることによって構築された走行情報データベースを用いる。しかし、このシステムは、斯かる目的地が識別されて初めて、目的地へ向かって用いられるルートを記録し始めるにすぎない。従って、このシステムは、使用可能になる前に、目的地を識別するためにユーザの介在を全般に必要とする。この文献には、システムが車両のエンジンが停止された場所を定期的に検出し、それを目的地点として記録することができると示唆されている。その後、ユーザが目的地としてその場所を選択すれば、システムは、その場所へのルートを学習し、そのルートを自動的に予測し始めることができると書かれている。しかし、ユーザは、依然として或る段階で目的地としてその場所を手動で選択しなければならない。
【０００４】
EP 0967460 A1は、コミュート(通勤)ルート、つまりドライバが最も頻繁に通る単一ルートを学習するためのシステムを開示する。このシステムは、コミュート中にユーザが時間窓に入力する必要があるか、ディフォールトの時間設定を用い、次いで極最近に用いられたルートを格納すること、由来が未定義の合成ルートを格納すること、または時間窓の間にマッピングデータベースからの各道路セグメントが何度横切られたかを数えることによって、コミュートルートを推論し、最も頻繁に走行された道路セグメントをコミュートルートとするものである。
【課題を解決するための手段】
【０００５】
本発明の第1の態様によれば、請求項１で定義される方法が提供される。
【０００６】
本発明の他の態様および実施形態は、他の請求項で定義される。
【発明を実施するための最良の形態】
【０００７】
本発明を、図示の実施形態により次に説明する。
【０００８】
まず、以降に用いられる用語の意味を解説する。
【０００９】
一連のサイティングによって表わされる運動におけるブレイクとは、サイティングによって表わされる場所が著しく変わらない期間である。測位システムの誤差特性によって生じる僅かなドリフトがあったり、停止されていたり、測位システムの電源が落とされている場合は、サイティングが全くないこともある。
【００１０】
外部位置は、対象物が見つけ出される場所や事象が生じる場所が座標系外であることを表すために用いられる。外部位置は、高度ありまたはなしのユニバーサル横メルカトル図法(UTM)などの地図投影法グリッドの形、世界測地規格1984(WGS84)などの測量基準の緯度と経度の形、または地球中心地球固定(ECEF)のWGS84などの直線の座標系の形で与えられる。
【００１１】
GPSとは、米国の全地球測位システムであり、良好な信号状態下でアンテナの位置を数ｍ以内で決定できる人工衛星航法システムの１つである。また、GPSは、１マイクロ秒以上の精度で時間情報を提供できる。
【００１２】
GPS時間とは、協定世界時(UTC)、つまり地球の毎日の回転に基づく観測上の時間の規格のうちの1つを辿る絶対時刻標準である。GPS時間は、UTCと最大で１マイクロ秒の差があるが、UTCに対して200ナノ秒以内に較正できる。GPS時間は、太陽の周りを回る地球の回転周期に対して調整(閏秒調整)されていないので、UTCと小整数秒の追加の差がある。UTC時間およびGPS時間が秒の主たる尺度を得ている未調整の原子時間尺度は、TAI(国際原子時)と呼ばれていて、TAIからGPSを差し引いた時間は、一定整数秒に非常に近く、1980年にGPS時間が始まったとき、TAIとUTCの差は19秒であった。
【００１３】
走行(journey)とは、走行の両端をなす２つの重要な場所の間の一連のサイティングを言う。このシステムでは、走行を重要なブレイク間の一連のサイティングと定義する。ブレイクが重要であるか否かは、用いられる特定のアルゴリズムとパラメータによって決定されるが、一般に、長期間の運動中の短いブレイクを除外するようにパラメータが設定されている。適切な設定によって、食事のための１時間のブレイクを中途に挟んだ３時間の運転は、単一の走行と見られるが、15分の買い物のための15分の走行とこれに続く帰宅のための15分の走行は、２つの別個の走行と見られる。
【００１４】
事象(event)の場所とは、用いられる座標系で表された事象の生じた場所を言い、例えば、浮動小数点値で表された緯度,経度,高度のWGS84データが用いられる。高度の使用は、オプションであるが、在るとすればソフトウェアの種々の特徴を強化するために用いることができる。
【００１５】
サイティングとは、対象物の位置を、その対象物がその位置で検出された時間と共に記録したものを言う。
【００１６】
サイティングアレイとは、アレイ状に格納された一連のサイティングの記録を言う。
【００１７】
サイティングインデックスとは、サイティングアレイの要素を特定する整数を言う。
【００１８】
ポイントとは、特に選ばれたサイティングインデックスを言い、そのサイティングの場所が、表示画面上の特定の画素にマッピングされると知られているか、所定の場所または時間の近傍などの他の基準によって選択されているものを言う。多くのポイントが同じ画素にマッピングされる一方、例えば昨年得られたサイティングのみが表示されるなど、データベース内の総ての場所がポイントとして表示される訳でもない。ユーザは、マウス、カーソルキーまたは他の入力手段を用いて、ポイントを選択でき、ソフトウェアは、どの場所が選択されたポイントに相当するかを決めることができる。
【００１９】
ポイント組とは、ポイントの順序に関係し、ポイントの複写に関係しないポイントの集合を言う。ポイント組は、より効率的な処理が可能になるなら、昇順にソートされ、複写ポイントが削除される。
【００２０】
ポイントのリストは、それ自身の定義された順序を持っており、複写が重要になることもある。
【００２１】
WGS84とは、1984の世界測地学システムで、GPSによって用いられる基本的座標系を言う。WGS84 は、座標系の原点が地球の重心に(数ｍ以内に)接近するように地球の周りのステーションのための座標を採用して定義された直線の座標系であり、GPSのような衛星に基づくシステムに対して特に有用にされたものである。斯かる座標系は、地球中心地球固定(ECEF)と呼ばれる。地質断層線に沿った移動のような主な妨害がある場合、ステーション座標は、全座標系における不連続を回避するように調節することができる。この座標系のz軸は、国際地球回転観測事業(IERS)によって定義された地球の自転軸に一致し、x軸とyの軸は、採用されたグリニッジ子午線に近い子午線を参照して定義されている。また、座標がWGS84データにおける緯度,経度,高度として表せるような随伴の楕円面がある。
【００２２】
図１は、自動車のような車両に取り付けられ、ROM,フラッシュメモリ,ハードディスクドライブ,光ディスクドライブなどのプログラムメモリ２を備えたコンピュータ１の形をなす本発明の装置を示している。しかし、発明の実施形態は、車両内の使用に限られず、他の対象物に取り付けることができる。例えば、この装置は、その地理的場所および現在時間に関する情報を受信する種類のセル電話や携帯に取り付けることができる。
【００２３】
車両は、車両に搭載されたシステムの多くを監視し,制御する車両電子システム３を含む。従って、コンピュータ１は、以下に述べる車両の現在状況の種々の態様に関する情報を受信できる。
【００２４】
更に、車両には、アンテナ５を介してGPSから受信した信号から車両の位置および現在時刻を決定するためのGPS受信器４が設けられている。この情報は、例えば衛星航法つまり"Sat Nav"システムの機能を提供できるように車両電子システム３にも供給される。
【００２５】
コンピュータ１には、人間が知覚できる出力を提供すべく出力装置６も設けられ、この出力装置６は、例えばSat Navシステムまたは車両内娯楽装置の一部をなすディスプレイの形で図示されているが、これに代えてあるいは加えてスピーカのようなオーディオ出力装置で構成されてもよい。
【００２６】
図１では、コンピュータ１,プログラムメモリ２,受信器４は、別個の部材として示されているが、ディスプレイ６を含む単一の装置によって具体化されてもよい。
【００２７】
使用時に、コンピュータは、車両のサイティングの記録を格納し、このサイティングを車両電子システム３からの車両状態に関する更なるオプションとしての情報と共に処理して、車両の将来の挙動に関する１つ以上の予測をドライバに提供する。サイティングの記録は、過去および現在の車両走行のログの形態をなし、サイティングは、少なくとも<場所,時間>の組を含む。サイティングの記録は、点火キーの使用,使用中の座部メモリ,ドアの使用,窓の位置,ミラー位置,トランスミッションの設定,座席の占有または重量,娯楽チャネルの選択,通話の送受信,外部と内部の温度,車軸荷重,雨センサの出力,牽引棒の使用,交通情報,大気汚染度,換気または空気調和の設定などの他の情報を更に追加されうる。このような情報は、コンピュータ１によって処理されて、例えば、可能な目的地,ルート,速度,停止,ブレーキ,加速,コーナリングなどの走行ログの一部をなす追加情報の予測が出力される。燃料消費,散漫度,疲労などの他のパラメータは、このような予測からコンピュータで計算できる。予測は、極最近のサイティングを、空間的,時間的データを用いて過去の走行ログの一連のサイティングと突き合わせて識別することに基づいている。また、マッチング(突き合わせ)は、点火キーの使用,乗客の数,娯楽装置の設定など上述の付加的データを、これらが車両の電子システム３からコンピュータ１が利用可能になるとき、考慮することができる。
【００２８】
この装置は、車両に取り付けられて権限を与えられると、車両走行に関する情報の記録を開始する。この記録は、特に車両の点火プラグがオンのときなどに頻繁な間隔で搭載されたGPS受信器６ からの車両の場所を記録することによって行われる。毎秒1つの場所データ更新率は、本出願の装置に対して概ね十分であり、50ｍ以内の場所精度が一般に利用できる。WGS84データを用いれば、場所を緯度,経度,高度として１ｍ以内の精度で記録できる。WGS84は、地球全体に亘って定義された良好な座標系であるが、地球中心地球固定(ECEF)のWGS84,英国陸地測量部グリッド,ユニバーサル横メルカトル図法(UTM)などの他の２次元,３次元座標系でも十分である。
【００２９】
高度は、多くのアプリケーションに不要で、幾つかの位置システムでは検出されない。斯かるアプリケーションについては、高度を省略した座標系が好ましい。高度がある場合は、高度は、
・後述する２次元マッチングの幾つかを３次元マッチングに拡張する
・例えば傾斜や高架道などを識別することによって、ユーザに特別なフィードバックを与える
・走行するルートの外観を３次元で解析することなどに用いることができる。
【００３０】
高度の使用は、車両自体が地球の表面を走行するものに限られないなら、航空機などにとってより重要になる。
【００３１】
車両が各場所にあった時刻も記録される。場所と時刻と用いられる場合は高度の組合せは、サイティングと呼ばれる。時刻は、現週内の秒数として単精度浮動小数点数で格納され、各一連のサイティングは、名前がユリウス暦の日で同定されるファイルに格納される。従って、各サイティングの絶対時刻を計算することは単純なタスクである。用いられる時刻基準は、協定世界時(UTC)を辿るが、計算単純化のため閏秒を含まないGPS時間である。UTCまたはTAIなどの他の時刻系も、同様に良好に用いることができる。GPS位置の絶対精度は通常約10ｍであるが、GPS位置をより高精度(1 ｍ)で記録して、GPSのより良い相対誤差を利用し、速度などのデータを計算する際に大きな量子化誤差が加わらないようにしている。
【００３２】
用いた数のフォーマットは、IEEE 754の単精度であるが、各サイティング記録の最後にチェック用の余分バイト(newline 0x0A)を加えて、欠陥ファイルや誤フォーマットファイルを検出する助けにしている。各サイティングは、次の17バイトからなる。
バイト0-3：ラジアン単位のWGS84緯度(latと称す)
バイト4-7：ラジアン単位のWGS84経度(lonと称す)
バイト8-11：ｍ単位のWGS84高度(altと称す)
バイト12-15：秒単位のGPS時刻(timeと称す)
バイト16：0x0A(セパレータと称す)
【００３３】
格納コストを持続的に減じ、GPSのような共通の測位システムの精度を増すべく、倍精度浮動小数点フォーマット、マイクロラジアンまたはミリ度に基づく緯度,経度の整数フォーマット、更にはNMEA 0183規格で用いられる度および１０進度などのASCIIフォーマットを用いた他の実施形態を選らんでもよい。
【００３４】
一連のサイティングは、名前が従来の「yymmddxx.pat」に従うファイルに格納される。ここで、yyは該当年の最後の２桁の数字、mmは該当月の数字、ddは該当月内の該当日の数字、xxは同日に記録された複数のファイルの識別に用いられるインクリメントする英字のフィールドである。ファイル名は、そのファイル中の最初のサイティングの時刻で選択される。例えば、ファイル030821AA.patおよびファイル030821AB.patは2003年8月21日に始まった最初の２つのファイルである。
【００３５】
車両の点火プラグがオンになる場合は常に、サイティングが、これらのファイルに格納され、エンジンが始動するごとに、新しいファイルが始まる。能力が許せば、カーフェリーによる走行などの状況に応じ、あるいはシステムが移動を見落としていないことを確認するために、点火プラグがオフのときも、サイティングを格納することができる。この場合、毎日あるいは場合によっては毎時間、新しいファイルを開始することが便利かも知れない。サイティングを複数の小さなファイルに格納する理由は、サイティングの一部を開き,バックアップし,通信するために容易に選択できるようにし、ディスクやファイルシステムの欠陥に対する回復力を与え、コンピュータが限られたリソースでもって容易にファイルを処理できるようにするためである。
【００３６】
他の実施形態の選択肢は、恐らくデータベース・ソフトウェアの制御下で、総てのサイティングを単一のファイルに格納することである。サイティングが参照する車両の登録番号、ドライバの名前、交通情報,天候などこれらサイティングの後の処理に関係する実に総ての情報も、上記ファイルに格納できる。説明を単純にするため、緯度,経度,高度,時刻の情報だけを含むサイティングファイルの場合を考えることにする。
【００３７】
他の事象は、外部ファイルに格納でき、ディレクトリ階層における事象の位置(例えば車両の登録番号によって名付けられたディレクトリ内の幾つかの特定の車両に対してサイティングの総てのファイルを分類する)によって、あるいは(例えば特定の運転手が車両を発進,停止させ、その時刻に最も近いサイティングを見つけることによる)サイティングの時刻によってサイティングと関連付けられる。
【００３８】
まず、サイティングのファイルは、時間の昇順にソートされ、次に各ファイルから場所が抽出されて、単一順序のリストに格納される。抽出処理の一部として、サイティングは、総ての値が知覚可能な限界内にあることを保証すべくチェックされ、限界内にない場合は、ファイルの全内容がリストから除外され、エラー報告が生成される。また、抽出処理の一部として、GPS時刻の起点が1980年1月1日なので当初のファイル名が最早無関係になるから、リストに格納されたサイティングの時刻が、秒数で表される。
【００３９】
次に、単一のリストは、連続するサイティングの夫々の時刻が、前のサイティングの時刻と等しいか大きくなるようにソートされる。このソート操作は、ポイントが抽出される前にファイルの名前によって一括して行われるので、極めて効率的である。ポイント自体のソートは、車両追跡または携帯電話追跡など異なった系からのファイルを統合する場合、あるいはクロックが調節された場合に必要となる。これは、データの完全性を更にチェックする機会を提供する。なぜなら、最古から最新に至るまでのサイティングのうちで合理的な限界外の一連のサイティングを拒否できるからである。
【００４０】
「前のサイティング」および「次のサイティング」という用語は、順序付けられた単一のリスト内の位置を意味する。このリストは、lat/lon/alt/time/セパレータの遡るシーケンスを含む１つの単一のバイト列、lat,lon,alt,timeの別個のシーケンス、またはサイティング,緯度,経度,高度,時刻のアレイやリストなどのデータ構造としてディスクやメモリに格納されうる。記憶フォーマットの詳細な選択は、ソフトウェアが実行される特定のコンピュータの構成によって決定されるが、インデックスまたはポインタによってサイティングを連続して検索するという基本操作を常にサポートし、後にサイティング情報を検索するために参照としてインデックスまたはポインタが用いられる。メモリで用いるフォーマットは、構造(記録)の配列である。各構造は、特定のサイティングの緯度,経度,高度,時刻を含む。配列は、既述の如く時刻順にソーティングされていて、シーケンスにおける最初の要素(要素0)が最古のサイティングで、最後の要素が最新のサイティングである。この種の構造は、図２に示されている。
【００４１】
走行は、まず朝に家を出て、後に仕事場に着くなどの２つの重要な事象の間の幾つかのサイティングのシーケンスである。何が走行を構成するかについては、走行がユーザとコンテキスト(前後関係)と走行情報が如何に用いられるかに依存することから、単一の定義はない。車両が或る期間の静止している場合、この期間を「ブレイク期間」と呼び、ブレイク期間における最初のサイティングは隣接する走行の終端に、最後のサイティングは隣接する走行の始端に夫々識別される。
【００４２】
車両における走行の単純な定義の１つは、新たな走行の始まりに車両の点火プラグがオンにされる時刻と、走行の終わりに車両の点火プラグがオフにされる時刻を用いることである。点火プラグの実際のオンとオフは、点火回路の状態または点火キーの位置をコンピュータに検出させることで検出して、タイムスタンプを押すことができる。これと択一的に、点火プラグがオンのときのみに、測位システムがサイティングを生成するようにして、サイティングが長期間ない場合が走行の間のブレイクを表すと判定してもよい。また、サイティングを格納するプロセッサを、点火プラグがオンのときだけ電源オンにして、サイティングが長期間ない場合が走行の間のブレイクを表すと判定してもよい。
【００４３】
点火プラグがオフであっても位置が生成されるシステムにおける走行の他の定義は、車両が極僅かに進行するか、全く進行しない期間を探すことである。この場合、(直接測定される,あるいは２つの隣接するサイティング間の速度を計算することによる)車両の速度が、所定期間(例えば1分以上)静止している車両について測定される最大可能誤差速度(例えば毎時１ｍ)で定義される所定閾値以下であるようなサイティングを走行間のブレイクとして探し、そのシーケンスの最初および最後のサイティングを走行の夫々終端および始端とすることである。この定義は、同乗者が小荷物を配達する間ドライバが待っているなどの点火プラグがオンのままの短い走行や、平面交差で列車が通過するのを待っているなどの点火プラグが短時間オフにされるブレイクなしの走行を、点火プラグの状態の適切な検出や記録に頼らずに潜在的に識別できるという利点を有する。
【００４４】
車両が長期間の非常に遅い速度で動いている場合、速度に基づくヒューリスティックの改善は、車両が所定期間(B分と称し,典型的には３分)以上,同じ位置の所定誤差マージン(典型的には50ｍ) 内に滞在するか、B分以上の期間にサイティングのすれがあるようなシーケンスにおける総ての期間をマークすることである。
【００４５】
ブレイクを識別するために用いられるアルゴリズムは、用いられる特定の測位システムの特性に依存する。例えばGPSシステムは、車両の進行に無関係にサイティングを毎秒生成する。この場合、車両は、隣接するサイティング間の50ｍ(所定誤差マージン)を通過すべく毎時110マイル(180km/h)以上の速度で動かなければならない。従って、ブレイクを識別するには、複数のサイティングを横切って見なければならない。
【００４６】
適切なアルゴリズムは、時間でB分隔たったサイティングのシーケンスを、このB分の間に車両が幾らの距離を動いたかを調べることであり、例えば次のようになる。
ステップ１：最初のサイティングであるサイティングAを呼んで、サイティングXにサイティングAをセットする。
ステップ２：各サイティングAについて、サイティングAの時刻から３分以内の時刻の後続のサイティングのうち最も遠いサイティングを見つけ出し、それをサイティングBとする。
ステップ３a：サイティングBがサイティングXから50ｍ未満で離れていれば、サイティングAからサイティングBまでの総てのサイティングをブレイク期間の一部であるとマークし、サイティングXを変更せず、サイティングAの次のサイティングをサイティングAとする。
ステップ３b：サイティングBがサイティングXから50m以上離れていれば、どのサイティングもブレイクサイティングにマークせず、新たなサイティングAとその次のサイティングである新たなサイティングXを生成する。
ステップ４：サイティングAがサイティングのリストの終端に達していなければ、ステップ２から繰り返し、終端に達していれば、全ブレイク期間のマーキングが完了したとする。
【００４７】
このアルゴリズムは、車両が非常に遅い速度(３分で50ｍ以下または約毎時0.6マイル(1km/h)以下)で動いている場合でも、長いブレイクをマークすることができるので、これも走行間の潜在的ブレイクであると考えられる。マークされたブレイク期間の例を、図３に示す。
【００４８】
異なった挙動が必要な場合や用いられている特定の測位システムのドリフトやドロップアウトに応じて、上記アルゴリズムを種々変更して用いることができる。
【００４９】
潜在的なブレイク時間が識別されたので、ブレイク期間の間にある各移動の期間の走行記録が作成される。この走行記録は、最初のブレイク期間の直後にあるサイティングへの参照と、次のブレイクの直前にあるサイティングへの参照を含んでいる。走行記録の始めおよび終わりへの参照がある。このような走行のラベル付けを、図４に示す。
【００５０】
ここで、計算される上記ブレイクのうち、どのブレイクがアプリケーションにとって重要な意義を持つかを決定したい。
【００５１】
各ブレイク期間を、時刻の最も早いものから時刻の最も遅いものへと順々に考察する。ブレイク期間の時間が、そのブレイクに先行または後続する走行の時間よりも短く、かつ、所定の閾値(Bmaxと称し、典型的には30分)よりも小さければ、これは長い走行の途中の一時的停止であるという理由で、これらの走行を合体させて１つの走行とする。これを、図５に示す。
【００５２】
例えば、５分の運転,６ 分の停止,５ 分の運転のシーケンスは、自動車にガソリンを入れるか、近くの店で何かを買うかのために特に外出したと思われ、２つの別個の走行であると考える。１時間の運転,６ 分の停止,半時間の運転のシーケンスは、どこかへ行く途中での給油またはスナック購入と思われ、全体を１つの走行と考える。
【００５３】
上記ブレイク期間に基づく走行の合体は、閾値Bmax未満の総てのブレイク期間の片側に、そのブレイク期間よりも短い少なくとも１つの走行が隣接するまで繰り返される。
【００５４】
走行を識別するために用いることができる多くの同様のヒューリスティックスがあり、幾つかのアプリケーションでは、例えば異なるヒューリスティックを用いたり、BmaxやBminなどのパラメータを調節したりして、走行の定義をアプリケーションの特別な要求に適合させることが有利である。
【００５５】
一旦走行が識別されると、各走行の記録をコンピュータに作成する。この記録は、走行の始めと終わりのサイティングをメインリスト上で参照する。各走行記録には、その走行における総てのポイントを含む最小の境界ボックスの緯度と経度が追加される。この情報は、過去の走行を検索し, 表示するアルゴリズムの迅速化に用いられる。
【００５６】
例えば、図９は、識別された各走行の最初と最後の夫々１０個のサイティングを大きな黒い点で表示した地図を示している。
【００５７】
もう一つの有用な最適化は、全リストが最初にソートされたき、最も早いサイティング(サイティング0と称す)からの各サイティングの累積距離を計算することである。こうすれば、或るサイティングXからサイティングYまでの累積距離は、サイティング0からサイティングYまでの累積距離からサイティング0からサイティングXまでの累積距離を減算することで求まり、多くの小さな計算を省略することができる。
【００５８】
シーケンスの各部分で表わされる速度と加速度も、更なる計算と表示さらには観察の有効性のチェックに有用である。車両の能力とそのセンサシステムに固有の誤差特性が与えられれば、５つのポイントからなる各群に対して速度と加速度が計算され、計算値が所定の有効限度内にあるか否かがチェックされる。例えば、速度が毎時150マイル以上(240km/h)または加速度が10ｍ/s2以上であるなど、位置センサで既知の即時誤差よりも長い距離に亘って、ポイントが有効限度外にある場合、これらの５つのポイントおよびその前後の幾つか(典型的には１分に相当する個数)のポイントは拒否される。残ったポイントについて、有効なポイントをもつ速度および加速度を選択してコンピュータメモリのキャッシュやディスクに格納し、後のコンピュータによる計算に用いる。
【００５９】
サイティングの集合(典型的にはサイティングの記録へのインデックスまたは参照の配列として格納される)を指して「選択セット」という用語が用いられ、その場合、集合中のサイティングのいかなる配列および複製も、重要性を持たない。従って、選択セットは、それに実行される操作に応じて、順序付けありまたはなしのフォーマットで、複製ありまたはなしで格納される。
【００６０】
ユーザまたはアプリケーションソフトによるサイティングの選択は、幾つかの方法で行われる。
【００６１】
サイティングを選択する１つの方法は、ロードされたサイティングのセット内で単にサイティングのシーケンス番号によって行われる。この方法は、サイティングを通して一つずつ進む場合またはサイティングの範囲を時間に遅れずに定義する場合に有用である。
【００６２】
サイティングを選択する別の方法は、サイティングの時刻と日付によるもので、典型的には、与えられた日または時間の中間点に最も近いサイティング、またはこのような２つの日と時刻の間の範囲のサイティングを選択して行われる。これと択一的に、サイティングは、例えば午前９時〜午前１０時または月曜日〜金曜日に総てのサイティングを行うなど日,週または年の単位で繰り返す時間範囲で選択することができる。
【００６３】
その後、サイティングを選択するための位置の使用がある。これらの位置は、他のソフトウェアから入力されるか、あるいはボタンがクリックまたは押し下げられるときの画面上のマウスの位置によって画定される。有用な位置選択モードは、入力された位置に最も(位置が)近いサイティングを見つけるか、入力された位置の周りの特定の領域(矩形または円形)内の総てのサイティングを見つけるか、入力された位置の周りの特定の領域内の最も古いまたは最も新しいサイティングを見つけることである。ユーザがマウスをクリックし,ドラッグして位置を入力するとき、ポイントが選択されるべき領域を表示するカーソルをマウスポインタの周りに描くことは有用である。
【００６４】
上述の総ての選択モードのうちで、特に選択されたポイントがユーザによって選ばれている場合、選択セット内にあるポイントをディスプレイ上でハイライト表示することはしばしば有用である。これと択一的に、走行分析などの機能に対して、選択されたサイティングが一部をなすような総ての走行など選択されたセットのみならずそれ以上をハイライト表示することは有用である。このようなハイライト表示モードは、典型的にはプルダウン・メニューまたはツールバー上のボタンによってグラフィカルユーザインターフェースによって制御される。
【００６５】
総ての選択方法は、それらが適用される毎に新しいポイントのセットを定義できるか、幾つかの独立したアプリケーションに亘ってポイントを累積できるようになっている。
【００６６】
一旦幾つかのポイントが選択されると、選択されたセットからポイントを削除する１セットの対応する操作がある。この削除操作は、ポイント(削除ポイント)の新しいセットを画定するために同じ選択規準を用いる。削除セットに含まれる元のポイントのセットは、総て元のセットから削除される。この削除を行う便利な方法の１つは、マウスの左ボタンで累積選択機能を働かせ、右のマウスボタンで削除機能を働かせることである。そして、広範囲のポイントは、マウスの左ボタンを押し下げたままディスプレイを横切ってマウスを掃引することにより選択することができ、間違って含めたポイントは、マウスの右ボタンを押し下げたままそのポイント上でマウスカーソルを動かすことによって削除することができる。
【００６７】
一旦サイティングのセットが選択で画定されると、検索や予測や他のアルゴリズムを開始または終了するサイティングを設定するなど後の使用のため上記セットを保存(セーブ)する場合が多々ある。続く操作をより容易にするため、選択されたセットが保存されると、サイティングへの参照が、単一順序(例えば、総てのサイティングの時刻順のリストにおけるサイティングのインデックスによる)にソートされ、複製も総て除去される。そして、このリストは、時刻,持続時間,速度またはサイティングのセットから引き出せる他の総ての特性を分析し、検索の開始または終了を設定するユーザによるコマンドを受けて、他のソフトウェアが複製し,操作するために利用できる。
【００６８】
複数の選択されたセットが用いられる場合、全セットを１つのオペレーションで操作できることがしばしば有利である。共通の例は、開始と終了のポイントのセットが用いられる場合である。始点として総てのポイントのセットをロンドンに持ち、終点として総てのポイントのセットをケンブリッジに持つ場合を想定する。最も近い１対の(時刻)ポイントであって、１番目のポイントが開始点のセットに、２番目のポイントが終了点のセットに属するものを見つけ出した場合、始点内の任意のポイントから終点内の任意のポイントへの最速の横断(必ずしも１走行でない)、つまりロンドンからケンブリッジへ行った最速の走行の始点と終点を見つけたことになる。逆のボタンは、始点セットを構成していたポイントが終点セットを構成し、終点セットを構成していたポイントが始点セットを構成するように２つのセットの名前を入れ替える。分析が繰り返されるならば、ユーザがポイントのセットを再選択せずとも、ケンブリッジからロンドンへの最速の横断が見つけられる。
【００６９】
単純な探索は、所定時間範囲内のサイティングを総て調べるか、あるいは或る場所に近いサイティングを調べることを含む。両者とも、規準に合致するサイティングを保持しつつ、各サイティングを順々に調べることによって行うことができる。
【００７０】
これをより効率的に行う方法は、一度に1000個ほどのサイティングについて一連のセグメント・レコードを作成することであり(毎秒１サイティングの割合で約16分間)、各セグメント・レコードは、そのうちの最初と最後のサイティングを参照するとともに、コンピュータ計算で求められ、そのサイティングの総てが含まれる緯度と経度の最小境界ボックスを有している。このセグメント・レコードは、上記走行を記述するために用いられる記録と典型的には同じ構造であり、ポイントの包括的な範囲が必要とされる他の場所でも用いられる。境界ボックスを常に準備しておくことによって、空間座標によるオーバーラップのいかなる計算も、境界ボックスのオーバーラップ領域を最初に計算することによって加速することができる。この好い例は、ディスプレイのためにセグメントを考える場合、セグメントの境界ボックスが表示された区域の境界ボックスと重ならないとき、そのセグメントを迅速に却下できることです。同様に、時間のいかなるオーバーラップも、セグメントによって参照される最初と最後のセグメントの時刻を考慮することによって迅速に決定することができる。
【００７１】
セグメント・レコードを加えることは、或る形態の質問により効率的に答えることを可能にする。この質問とは、例えば、与えられた時間範囲内のサイティングの場所はどこか、典型的には所定場所の周りの円または矩形である与えられた区域内のサイティングの時刻はいつかなどである。
【００７２】
これらの質問自体は、より高レベルの質問に答えるために用いることができる。その例は、ディジタル写真が撮られた時刻頃に作られたサイティングを見つけることである。この時刻は、画像フォーマット中またはファイル作成時刻としてしばしば写真と一緒に格納される。写真の直前および直後のサイティングを見つけ、写真が撮られた時刻に車両や携帯電話や他の追跡対象がどこにあったのかが分かるように地図表示上でハイライト表示するなどしてユーザに示すことは簡単なことである。
【００７３】
各ポイントのハイライト表示を生じさせるように写真の記録を維持すれば、総ての写真の場所をハイライト表示された点として地図上に表示することができる。これは、各写真が撮られた直前および直後に作られたサイティングをハイライト表示することによって行われる。そうすれば、ハイライト表示された場所のユーザによる選択が可能になり、関連する写真を表示することができる。このように、たとえカメラや写真自体が場所情報を含んでいなくても、場所によって写真をブラウズすることができる。
【００７４】
写真の時刻から導き出した場所は、車両または他の追跡対象がその場所の近くにあったサイティングデータベース中の総ての時刻を見つけるためにを用いることができる。そして、それらの時刻は、関連する他の写真や日記記入事項などを見つけるために用いることができる。
【００７５】
写真の相互関係に含まれる一連の操作の例を、図６に示す。このシステムは、次の３つの部分に分けられる。
・ユーザが何を見、何と相互作用したかを反映するユーザ・インタフェース、
・相互関係の詳細な操作を実行するファインダ・アプリケーション、
・ファインダがサイティングデータベースと相互作用することを可能にするサイティング・アナライザ。
【００７６】
最初の操作は(A)であり、ユーザが写真を選択し、同じ場所で撮られた他の写真を見つけるためにファインダ・アプリケーションを起動する。ファインダ・アプリケーションは、一般に用いられるJPEGフォーマットで保存された時刻記録などの写真ファイルから時刻を抽出する。この時刻は、(B)でサイティング・アナライザに渡され、サイティング・アナライザは、その時系列のリストを捜し、(C)で上記時刻の直前および直後のサイティングの場所を返す。(D)において、ファインダ・アプリケーションは、上記２つのサイティングの中間のポイントを取り、このポイントを中心とする一辺500ｍの矩形区域を作る。この区域は、測位システムにおける誤差を考慮して、車両が異なった場所で駐車したかもしれない先行または後続の訪問地を確実に取り囲み、木やビルのような障害物によってもたらされうるサイティング記録におけるギャップを見込んでいる。この区域は、(E)でサイティング・アナライザに与えられ、サイティング・アナライザは、この区域内にある総てのサイティングを選択し、選択したサイティングの時刻シーケンスを次に検索し、(F)で各時刻シーケンスの開始と終了の時刻を返す。そこで、ファインダ・アプリケーションは、総ての写真( または時刻スタンプが押された他のメディア)を調べ、時刻スタンプが上記時刻範囲内にある写真( メディア)を総て選んで、そのようなメディアのリストを(G)で生成する。続いて、ユーザ・インタフェースが(H)で呼び出され、上記リストがファイル名,サムネール,スライドショーなどとしてユーザに示される。
【００７７】
更なる改良は、(D)で一辺500ｍの矩形で始めても、例えば１０個未満といった僅かな写真しか見つからない場合、隣接する１０枚の写真がユーザに示せるまで、矩形の一辺を1km,2km,5kmと順に拡大していくことである。
【００７８】
他の選択肢のうちで、(D)における区域は、円形や長方形または(C)における２つの基の場所に焦点をもつ楕円形にできる。効率的な選択肢は、(C)における２つの基の場所に夫々中心をもつ一辺500ｍの２つの正方形を用い、時刻範囲を抽出する前にサイティングを組み合わせることである。
【００７９】
ユーザが、サイティングがされたであろう時刻を与え、地図上で選択し、座標を与え、あるいは場所が参照できるアドレスや地名を与えることによって場所を記述することができるならば、その場所を検索の原点として用い、その近傍の総てのサイティングを見つけて、それらサイティングに亘る時刻範囲を見つけ、その時刻範囲内で撮られた総ての写真を見つけることができる。
【００８０】
同様のプロセスは、計算機化された日記アプリケーションに適用することができる。日記の過去の記入事項が特定の時刻に「アクメ株式会社を訪問」であるならば、その時刻の近辺でなされたサイティングを再び見つけることができる。これは、サイティングがその近辺でなされたときに過去の他の時刻を見つけるための写真の例と同じ手法を用いて行うことができ、データは、カレンダ上でユーザに対してハイライト表示でき、あるいはユーザが関連する日記のページを順に繰ることができるたとえシステムが「アクメ株式会社」の場所を必ずしも伝えられなくても、その場所を約束の時刻になされたサイティングから推論することができ、同じ会社が訪問された可能性のある時刻を引き出すことができる。
【００８１】
日記プロセスは、図７に詳しく示されている。ユーザは、関心ある時刻または時刻範囲を画定する日記記入事項の選択から始める。(A)で再び時刻を抽出をし、これをサイティング・アナライザに渡す。単一時刻の写真例の場合、日記例は典型的には或る期間に亘って広がる事象(出来事)を調べるので、上記期間はサイティング・アナライザ(SA)に与えられる。SAは、その期間の直前から直後までの総てのサイティングを見つけることができるだろうが、写真例とのもう一つの相違点がある。相違点は、ユーザがその約束場所に日記に書かれた時刻丁度にいなかったかもしれず、特に、時刻よりも遅く到着し、時刻よりも早く出発したかもしれないということである。従って、上記時刻範囲内の総てのサイティングの検索は、場所の精度を鈍らせるような約束場所へのまたは約束場所からの走行の本質的部分を容易に含むうることになる。これに代えて、約束の開始時刻に進行中であった走行セグメントまたはブレイク期間を見つけるように走行セグメントのリストを調べることができる。そして、見つけた走行の終点またはブレイクの始点を、最も可能性のある場所として用いる。同様に、約束の終了時刻にいた最も可能性のある場所として、オーバーラップする走行の始点またはオーバーラップするブレイクの終点(続く走行の始点でもある)を用いる。日記期間に亘る他の走行があるならば、その走行の始点と終点を場所リストに追加するか、例外を設けて、例えば約束の開始と終了をモニターして時刻についてより詳しく入力するようにユーザに頼むことができる。
【００８２】
(C)で場所リストに戻る。ファインダ・アプリケーションは、(D)で写真の場合と同様に１つ以上の囲む区域を計算し、(E)でSAへ総ての時刻範囲を要求する。SAは、(F)で関連する時刻範囲を返し、ファインダ・アプリケーションは、この時刻範囲の夫々を総ての日記記入事項のタイムスパンと比較し、タイムスパンとオーバーラップする総ての日記記入事項を返す。写真アプリケーションとのもう一つの相違点は、長い日記記入事項との短い時間のオーバーラップが重要ではないということである。この例で、2003年6月15日に、ユーザは基の日記記入事項にある場所を通って運転していたであろうが、その場所の近辺に２分間(12:23〜12:24)居ただけである。ユーザがその場所を訪れていた可能性は明らかに少ないか、その場所の近辺に長時間居たかであるので、この時刻範囲は無視される。典型的には、５分未満の時刻範囲および日記記入事項のオーバーラップ期間の１／４ 未満のオーバーラップは無視される。そして、(H)で残った日記記入事項を取って、それをカレンダ上にハイライト表示したり、図７に示すようなハイライト表示した一連の日ページとしてユーザに示す。
【００８３】
これらのプロセスは、100%正確である必要はない。同じ場所で撮られなかったことを示す少数の写真や異なった場所を訪れていたときの日記の時刻は、それらがユーザに有用なヒントの多くの部分を適切にもたらす限りにおいて許される。それは、インターネット・サーチエンジンが、ユーザの質問に関連しない僅かのヒントを作ることを許されているのと同様である。
【００８４】
サイティングの全シーケンスを走行に分割することは、走行の途中の何時,何処にブレイクが入ったかというさらに効率的な質問のメカニズムを与える。走行の始点と終点が一旦分かれば、場所や日時などを含むようにその走行を洗練することができる。例えば、昼食のために停車した場所を英国北部で見つけたいなら、英国北部を囲む緯度と経度の特定の境界ボックス内の総ての走行終点のうち正午から午後２時までにある半時間を超えるブレイク(停止)を捜すことができる。このことは、地図上に表示でき、あるいは近くの場所を調べることによってテキストに翻訳できる可能性を直ちにユーザに提供する。
【００８５】
もう一つの有用な分析は、或るポイントのセットから他のポイントのセットへ車両がブレイクなしで走行したサイティングのシーケンスを総て見つけることである。まず、ユーザは、上述のいずれかの手段によってポイントを選択する。このポイントのセットは、始点として用いられる。次に、ユーザは、終点として記録されるもう一つのポイントのセットを選択する。すると、プログラムは、最初のサイティングから最後のサイティングに至るまでのサイティングの全シーケンスにおいて、同じ走行が後続している開始ポイントを、他の開始ポイントに遭遇する前の終了ポイントによって効率的に検索する。
【００８６】
このような各<開始,終了>ポイント対は、(セグメントとして)格納され、検索は始点を捜すステップに戻る。総てのサイティングの検索が終わると、始点と終点の間を移動する走行セグメントのリストが出来上がる。
【００８７】
効率的というのは、この検索が、始点と終点の対として格納されたポイントのインデックスと走行セグメントのみを用いて行うことができるからである。ポイントのインデックスリストの総ては、まず昇順にソートされる。このアルゴリズムは、総ての中間のサイティングを考慮する必要がなく、始点と終点のインデックスの順序付けられたリストおよび総ての走行の始点と終点を単純に通し検索するだけで済むので、時間的に非常に効率的で、数百万のポイントの集合に適用することができる。
【００８８】
その後、各セグメントは、持続時間,長さおよび走行時間を計算するために分析され、このデータは、１セグメント当たり１行のテキストボックスでユーザに表示される。これらの行は、ポイントからポイントへの走行をどれだけの速度でどれだけ頻繁に行ったかがユーザに一目で分かるように、持続時間の昇順または日付の昇順にソートされる。例えば、異なったルートが用いられた場合、ルートが持続時間でソートされているなら、最も速いルートは、表の先頭に来るので直ちに明白になる。
【００８９】
追加の洗練は、ユーザがこのテキストボックスの１つ以上の行を選択し、その特定のセグメントおよび走行をハイライト表示してディスプレイ上で見ることを可能にする。このような選択の例を、図８に示す。例えば、セグメントの始点の以前の各走行の部分は緑のハイライトで、そのセグメントの始点と終点の間は黄色のハイライトで、そのセグメントの終点からその走行の終点までは赤色のハイライトで夫々表示される。このようにして、ユーザは、ポイント間の走行が最速および最遅であるルートを容易に知ることができる。
【００９０】
従来のルート計画ツールは、典型的にはユーザがルートの始点と終点の場所を選択することを可能にする。本発明のツールは、ルートの始点と終点の夫々から所定範囲(典型的には100ｍ)内の総てのポイントを見つけることによって、始点と終点のセットを自動的に生成する。記録された走行から抽出されたデータは、ルート計画ツールによって予測されたルートおよび持続時間と比較することができる。ルート計画ツールが、ルートが順に通過しなければならない「経由」や「停止」として場所セットを有しているなら、ルート計画ツールは、選択したルートのセグメントが通過しなければならない特別のポイントのセットも生成することができる。
【００９１】
ルート計画ツールは、(連合する終点場所と速度情報をもつ)データベースにおける各道路リンクを考慮し、その道路リンクを横断する走行を見つけるためにこの分析を行なうことによって、より高精度にすることができる。これは、所定範囲(典型的に100ｍ)内のリンクの一端を始点に、この所定範囲内の上記リンクの他端を終点に夫々設定し、上述の総ての可能な走行セグメントを見つけ出し、道路リンクの長さの所定マージン(典型的には20％)内の走行距離であるものだけを保存することによって行うことができる。
【００９２】
接続遅れが一度だけ考慮されるのを確実にするため、接続遅れは、横断の最初また最後の両方にではなく一方のみに加えられる。接続遅れを各横断の最後に加えるには、そのリンクの始点の近傍が残っている最も早い時刻を横断の開始時刻とし、そのリンクの終点の近傍が残っている最も遅い時刻または走行の終点のいずれか早い方を横断の終了時刻とする。
【００９３】
各横断の持続時間は、その横断の曜日と時刻のための道路リンク速度を更新するために用いることができる。
【００９４】
このように、ルート計画ツールは、ユーザの特定の運転スタイルをより良く反映する。いくつかの横断が、同じ道路リンクについて類似の曜日および時刻に見つかった場合、早期の横断は、システムを運転スタイルや道路状況の変化に徐々に順応させるべく無視することができる。
【００９５】
横断の持続時間の変化も、例えば持続時間の標準偏差と分散を計算することによって、道路リンクの変動性を評価するために用いることができ、分散は全ルートに亘って合計して、全走行時間で期待される変動の推定値を与えることができる。上記分散の平方根は、全走行時間で期待される標準偏差の推定値を与える。ルート計画ツールは、ルート時間の推定における１つまたは２つの標準偏差を含み、最低のものを選ぶことによって、悲観的時間が最良であるようなルートを提供するように、あるいは持続時間を分散を含まずに合計し、最低のものを選ぶことによって、平均時間が最良であるようなルートを提供するように構成することができる。
【００９６】
ルート計画ツールは、道路リンクがどれくらい頻繁(かつ最近)に走行されたかを各道路リンクについて書き留めることもでき、ユーザが通常の「最短距離」,「最頻使用道路」,「最速」よりも、いわゆる「最も馴染み」のオプションを選ぶ場合、上記道路リンクに優先度を与えることができる。ユーザが最近走行した道路リンクよりも「余り馴染みのない」や「驚かす」に重みを付けたオプションが実際にあり得る。このような技術について、次に詳細に述べる。
【００９７】
車両用の殆どのルート計画システムは、ジャンクション(接続)用のエントリおよびその間の道路セグメントを含んだデータベースを用いる。ルート計画ツールの幾つかの実例では、接続または道路セグメントは、それらの間の接続性を記述するデータ構造中のポインタとして暗黙に存在し、あるいは、名前,場所座標,道路や接続の種類などの情報を含んだ明示的なデータオブジェクトである。例えば道路が行き止まりなどの場合には、道路セグメント終端は接続でないこともある。このような場合に応じるべく、ルート計画の文脈中で道路セグメントの終端を意味する用語「ポイント」を用いる。道路セグメントが２つのポイントを接続し、１つのポイントが(a)１つ,(b)２つ,(c)２つを超える道路セグメントを持っている場合、夫々を例えば(a)行き止まり,(b)道路の角または他の重要点,(c)接続点と理解する。一方通行や回転禁止などの道路制限も更なるデータとしてコード化される。
【００９８】
単一ペアのルート・プランナは、データベース中のある場所から他の場所、つまりポイントAからポイントBまでの(与えられた規準下で)最適の走行を計画するために道路データベースを用いるソフトウェアである。単一ソースのルート・プランナは、データベース中のポイントAから他の総てのポイントまでの最適の走行を計画する。全ペアのルート・プランナは、データベース中の総てのポイントから他の総てのポイントまでの最適の走行を計画する。これらの各問題に対して異なったアルゴリズムが備えられているが、これらのアルゴリズムの殆どは、馴染みを考慮して次に述べるような修正をすることができる。車両アプリケーションに最も一般に用いられているのは単一ペアのルート・プランナであるので、単一ペアのルート・プランナの説明に専念するが、この技術は非常に広範囲の問題に適用できると理解されなければならない。
【００９９】
これらのアルゴリズムの殆どは、道路網での使用のみに限定されず、グラフ中の各リンクの使用に伴って費用増分が生じるグラフで表現できるいかなるネットワーク上でも一般に作動する。これらのアルゴリズムは、費用が実際の経路長さと全く関係のない抽象的な費用なのだが、「最短経路」のアルゴリズムとしばしば呼ばれる。グラフは、全費用が負であるような循環をグラフ中に有しないものか、最短経路がこのような循環の周りの無限数の走行を含むものに通常拘束される。この技術は、道路網のためのルート・プランナの文脈で説明されるが、他の多くのネットワークに同様に適用できると理解されなければならない。
【０１００】
典型的には可能な多くのルートがあるので、検索は、与えられた規準の下で最適なルートを見つけ出すようにされなければならない。その選択を制御するパラメータは、典型的には全走行時間, 横断される道路の種類または走行の燃料費の或る組合せである。これらは、各道路セグメント毎に漸増的に働く線型の費用関数として通常表現されるが、金銭上の費用ではなく、異なった種類の優先パラメータの相対的重み付けを反映した抽象的な費用である。即ち、費用関数は、特定の道路セグメントを加えたルートの(時間,種類,燃料費に換算した)抽象的費用を計算することができる。この費用関数が与えられれば、全費用が最低のAからBへのルートを見つけるための周知なアルゴリズムがある。ルート・プランナのユーザは、上記費用関数の要素の重み付けを自分の好みに応じて変更する機会をしばしば与えられるので、ルートは、他の要素に対しては必ずしもそうではないが特定の要素に対して最適になる。
【０１０１】
或るシステムでは、与えられた道路セグメントの費用が、時刻に依存することがある。例えば、ラッシュアワーでは他の時刻よりもその道路セグメントを横断するに要する時間が長くなるから、費用関数は、車両が横断する予定の各道路セグメントの時刻に依存する。
【０１０２】
或るシステムでは、全費用関数が、個々の道路セグメントの費用の線形一次結合でないこともある。これは、ルートを見つけるアルゴリズムを、より複雑あるいは時間を要するものにするが、道路セグメントを横断する時間や漸増する燃料費のような基本的パラメータは、各道路セグメントについて依然与えられている。
【０１０３】
次に、各道路セグメントにパラメータとしてどのように馴染みを加え、新しいルート検索の能力を提供する全費用関数にどのように馴染みを組み込むことができるかについて述べる。
【０１０４】
新たな要素は、ルート・プランナが用いている費用関数に、ドライバが各道路セグメントにどのくらい馴染み(または不馴染み)でありそうかを表すものとして導入される。この要素は、典型的にはそれ自体では用いられないが、上述のように計算される各道路セグメントの費用を更に10％または20％だけ変化させるだろう。従って、道路セグメントの費用は、その道路セグメントが非常に馴染みだと思われれば20％だけ減じ、少し馴染みだと思われれば10％だけ減じられる。ユーザが馴染みのないルートを求めていれば、道路セグメントの費用は、非常に馴染みなものは20％だけ増し、少し馴染みなものは10％だけ増される。もちろん、これらの値は代表例であり、馴染みにどれだけの影響力を与えたいかに応じて様々に選ぶことができる。通常、システムは、「非常に不馴染み」(最大で40％の費用増)、「不馴染み」(最大で20%の費用増)、「少し不馴染み」(最大で10％の費用増)、「気にしない」(費用の変更なし)、「少し馴染み」(最大で10%の費用減)、「馴染み」(最大で20％の費用減)、「非常に馴染み」(最大で40%の費用減)といったスペクトルなどの馴染みのレベルを形成する手段をユーザに提供する。
【０１０５】
馴染みのルートは、ドライバが、走行するレーンが狭いか,回転が難しいか,横断歩道があるかなどジャンクションレイアウトに何が来るかについて精通しているので、より安全であるに違いない。
【０１０６】
馴染みのルートは、例えば或る道路は雨が降たり凍たりすると危険になり、或る道路はより空いているとか,より汚染されないとか,有用な停止場所を通るとかいった道路データベース中でコード化されないという理由によって好まれて、頻繁に用いられる。馴染みの概念は、これらや他の多くの個人的好みを明示的にプログラムする必要なく考慮に入れてルート計画を最適化するのに役立つ。
【０１０７】
従来のルート・プランナは、時々道路や交通さらにドライバを全く知らないでルートを計画し、ドライバが幾つかの場所で最適でないことを知っているルートを計画する。そのとき、ドライバは、ルートに通過しなければならない余分なウェイポイントを追加する。これらは、「vias」と時々呼ばれる。十分なviasが一旦置かれれば、これはルート・プランナをしてドライバが望む道を採らせる。このように特定のルートを強いることは、デスクトップのルート・プランナでは煩わしいことであるが、少なくとも全ルートをグラフィックに見ることができ、マウスを用いて好みのルートに沿ってviasを置くことができ、新しいルートを高解像度で地図に表示して確認することができる。ディスプレイと入力手段が制約された車両用のシステムにおいて、これは実際に非常に困難なタスクになり、馴染みあるルーティングは、特に魅力のあるものになる。
【０１０８】
ルート選択を「馴染みのない」ルートの使用に有利なように重み付けすることは、馴染みのルートに問題があり、最近用いていない別の良いルートがあるかどうかを知りたいとき有利である。この重み付けは、例えば同じルートを用いることに厭きたドライバが異なるルートが良いか否かを試したいときにも用いられる。さらに、この重み付けは、休日に毎回異なったルートを用いたため、そのルートが馴染みになり、「馴染みのない」ルートの使用に有利なようにルート選択が重み付けされていれば、そのルートが再び選択される可能性が少なくなる場合に用いられる。このように、AからBまでの一連の走行において、ルーティングエンジンは、異なった馴染みのないルートを毎日示唆し、ユーザは周辺地域をもっと見るであろう。
【０１０９】
各道路セグメントの馴染みのレベルは、0(全く走行せず)から1(代表的な馴染み)の間の実数として一般論の損失なしでコード化することができる。このレベルの解釈は、レベルが費用関数にどのように重み付けするかによって支配される。このレベルは、道路セグメントやそのセットを選択するユーザによって、テキストまたはグラフィックスツールを用いて名前または場所で設定される。あるいは、車両が過去に通った経路が何らかの形で利用できる場合は、その経路から馴染みレベルを計算することができる。
【０１１０】
各道路セグメントの馴染みレベルは、その道路セグメントが、どれくらい頻繁に以前に用いられていたかを考慮する。これに代えてまたは加えて、各道路セグメントの馴染みレベルは、その道路セグメントが、どれくらい最近用いられたかを考慮する。
【０１１１】
道路網の各部分は、典型的にはルート選択処理で用いられる関連する費用関数を有する。費用関数の用い方は、選択された道路網の部分に関連する費用関数をその部分の以前の使用に基づいて変更することである。
【０１１２】
ルート選択は、以前に用いられたことがない道路セグメントに対する優先を以前に用いられた道路セグメントの使用に与える(あるいは、より一般的には、馴染みが低レベルの道路セグメントに対する馴染みが高レベルの道路セグメントの使用に優先を与える)。これと択一的に、ルート選択は、以前に用いられた道路セグメントに対する優先を以前に用いられたことがない道路セグメントの使用に与える(あるいは、より一般的には、馴染みが高レベルの道路セグメントに対する馴染みが低レベルの道路セグメントの使用に優先を与える)。
【０１１３】
考慮されるべき走行は、特定の車両または特定の車両のセット(例えば、配達車両の一団)あるいは特定のドライバ(例えば、自動車キーの機密保護コードまたは適合されたメモリシート設定によって同定される)または特定のドライバのセット(例えば、特定の会社で働く、または家族に属している)によって行われる総ての走行である。
【０１１４】
この方法は、ルートを決めるべき対象物と一緒に移動するように配置された例えば車両搭載装置などの装置によって行われる。この場合、装置は、リアルタイムで対象物の位置の決定を可能にすべく、衛星航法システムを有している。
【０１１５】
或る実施例では、馴染みレベルは、どの道路セグメントが最近横切られたかについてのデータが、例えば地図照合航行システムや位置座標のシーケンスを道路セグメントデータベースに照合させることによって漸増的に供給されることで連続的に保持される。新たな横断が夫々同定されたので、それに応じてその道路セグメントの馴染みレベルが変更される。
【０１１６】
例えば、ドライバが特定の道路セグメントを特定の方向へ何回横断したかを数えることによって馴染み度を計算することができ、計数値を10で割って馴染みレベル１とする。これによって、0〜1までの所望の馴染みレベルが与えられる。その横断がどれくらい最近行われたかを考慮するには、前月にされた横断を夫々１点とし、横断が始まった月から勘定した合計点を１点につき2％で減じる。この時間に関する指数関数形崩壊の使用は、各道路セグメントが計数値(例えば4.5)とその計数値であった日付(例えば2001年1月5日)を保存するだけで済むという点で、エレガントな実行方法といえる。そして、その道路セグメントをｍヶ月(例えば5ヶ月)前に横断して以来全く横断していない場合は、4.5に0.98ｍを乗算して新たな計数値を得て、この場合では2001年1月5日において計数値4.5×0.904=4.07と書き換えるのである。これは、計数値4.5を構成する各要素は、毎月同じ率で崩壊するので、各要素の合計も同じ率で崩壊するからである。
【０１１７】
もちろん、崩壊を滑らかにするために、実際、任意の時間単位(秒またはミリ秒)を用いて表される崩壊の連続的計測を用い、任意の崩壊時間間隔に対する正確な崩壊係数を計算するために、実数冪の指数関数を用いる。ドライバが道路セグメントを横断するとき、上述の指数関数処理によってこの横断時点での計数値をまず計算し、１点を加えて、この横断の直後に新計数値として格納する。
【０１１８】
非常に馴染みのルートが支配的になり過ぎないように、計数値が所定値(例えば10)を超えた場合、計数値を所定値で割って、馴染み指数を0〜1の値に制限する。
【０１１９】
或る期間(10年)よりも古い横断がルーティングに影響しないようにしたければ、(横断後の年数に0.1を乗じる)計算をし、計算結果を１から減じ、減算結果が負であれば０とする代替手法を用いる。この手法では、１年前の横断は別勘定で0.9点となり、９年前の横断は別勘定で0.1点となる。これは、最初１で１０年後に０になる年単位の効果的線型崩壊であり、例えば秒,ミリ秒などの時間の格納に用いられる単位で表された円滑な崩壊関数によって典型的に実行される。この場合、各セグメントについて格納されるデータはより多くなる。その理由は、各過去の横断からの点は、同じ率で崩壊しないからである。むしろ、これらの点は、１０年に達するまでは所定時間間隔当たり一定量で崩壊し、１０年になると０になってそれ以上崩壊しない。この手法による集合点は、各寄与因子が何時１０年に達して崩壊しなくなるかを別に記録する必要があるので、指数関数崩壊の点のように単純には減衰しない。その代りに、各過去の横断の時期を１０年になるまで格納し、１０年になったとき永久に削除する。こうして、要求があればいつでも、与えられた時期から合計点を計算できる。繰り返して言えば、合計点に１０年の制限を設け、１０で割って馴染み指数を得る。１０年よりも若いとマークされた横断を全く持たない道路セグメントを見つけた場合、そのリストと道路セグメントを削除し、その横断が恰もなかったと同じにする。
【０１２０】
ルートが或る道路セグメントを用いようとしているとき、その道路セグメントの馴染みレベルＦを一旦計算すると、この馴染みレベルを費用関数の重み付けに用いる。例えば、道路セグメントが横断されるときの走行時間がＴ秒でその予測増分を表す費用関数がある場合、走行時間Ｔに(1-0.2×Ｆ)を乗じ、馴染み指数が１(非常に高い)の道路セグメントは、恰も20％も速い道路セグメントであるように計算され、横断に0.8Ｔしか要さない一方、馴染み指数が0.2(非常に小さい)の道路セグメントは4％だけ速いと計算され、横断に0.96Ｔを要する。もちろん、この人為的に減じられた横断時間は、人為的に縮小された横断時間は、どのルートが全体として最良なのかを決めるためにのみに用いられる。これは走行に要すると予想される実際の時間なので、ユーザは、最低の費用関数をもつ真の合計横断時間を知らされる。馴染みのルーティングを用いると、最低の全費用関数をもつルートは、最低費用や馴染みの道路使用などに対する好み(優先度)が最速のルートをもたらさないのと同様、走行時間が最短のものではない。
【０１２１】
上述の漸増的費用関数で動作する単一ペアのルート・プランナのための既知のアルゴリズムは、多くある。或るアルゴリズムは、２点の間の距離は２点を結ぶ直線が最短であるなどの道路網に関する特別の知識を利用している。例えば、「Dijkstraのアルゴリズム」は、ごく僅かな拘束下でグラフ上の１点から他の総ての点への最適ルートを見つけ出す周知の方法である。負の長さや横断時間のない道路に適用する場合、選択された１点への最適ルートが決まったとき、計算を停止させる特別の終了チェック手段が追加される。
【０１２２】
別の種類のルータは、C.Y.リー「経路接続性およびその出願用のアルゴリズム」、IRE会報 電子計算機について、Vol.10, No.3、1961年9月、pp.346-365 に記載された「リー・ルータ」に類似している。
【０１２３】
このようなルータにどのように馴染みを加えることができるかを示すため、まず単純なルータの操作について述べ、次に、馴染みがパラメータとしてどのように加えられるかについて述べる。そして、ルータに加えることができる典型的な最適化を述べ、この最適化が馴染みを組み込むためにどのように適合されるかについて述べる。これら総ては、この技術を用いた殆どのルータに馴染みがどのように加えられるかを示す実施例である。
【０１２４】
この実施例ルータは、所定の点Aから他の所定の点Bへの最速の予測走行時間をもつルートを見つけるために用いることができる。この手法の概要をアルゴリズムA1で述べ、追加の重要かつ周知の最適化をアルゴリズムA2で述べて、馴染みを如何に改善されたルータに組み込むことができるかを示すことにする。
【０１２５】
アルゴリズムA1
このルータは、始点(点A)から出る総ての道路セグメントを、各道路セグメントの終点への到着時刻が最も早いものに注意を払いつつ検査することによって動作を開始する。この終点での最も早い到着時刻を最早到着時刻(Te)と呼ぶ。ルータは、決して拡張されない点Bを除いて最初は総て拡張されるのを待っていると設定される点が、夫々拡張されるのを待っているか否かにも注意を払う。まず、始点(点A)は拡張されるのを待っていないとマークされる。次のステップは、ステップSと呼ばれる。ステップSで、ルータは、最早到着時刻(時間Te)が既知で、かつ、拡張されるのを待っている点を調べる。そして、そのような点が見つかると、この点を点Pと呼ぶ。このステップは、通常、拡張されるのを待っている点およびその点の最早到着時刻TeをTeの昇順に並べたリストを保持することによってより効率的に行われる。次に、ルータは、点Pから出る各道路セグメントを夫々独立に検査し、点Pから点Qへの道路セグメントの横断時間(Tpq)を点Pでの最早到着時刻(Te)に加えてセグメントの他端(点Q)で予測される到着時刻(Tc)を計算する。つまり、Tc=Tpq+Te。他端の点Qについて格納された最早到着時刻がない場合または格納された最早到着時刻が計算された到着時刻Tcよりも大きい場合、点Qについて格納された最早到着時刻をTcとし、点Qを拡張されるのを待っているとマークする。状況によっては、以前の繰り返し処理で点Qが拡張されるのを待っていないとマークされうるが、より早い到着時刻が見つかったとき、再び拡張されるのを待っているとマークされる。次いでアルゴリズムはステップSに戻って繰り返される。
【０１２６】
このアルゴリズムは、終点(点B)が最早到着時刻(Te)でラベル付けされ、かつ、拡張されるのを待っているとマークされた他の総ての点が、点Bの最早到着時刻よりも遅い最早到着時刻をもつとき、終了する。この条件は、拡張されることを待っている点およびその点の最早到着時刻TeをTeの昇順に並べたリストを保持していることを再び有利に用いてステップSでチェックされる。
【０１２７】
馴染みを組込むには、道路セグメントの横断時間を既述の馴染みに依存する百分率によって変更することで十分である。これは、横断時間を、横断時間と馴染みの両方に依存する抽象的な費用関数に有効に変える。そして、アルゴリズムは、走行時間と馴染みの全体的組合せに対して最適なルートを提供する。これは、最適ルートがAとBの間の最速ルートでないにしても、最速ルートよりも馴染みがあり、全横断時間として長すぎないことを意味する。もちろん、馴染みで修正された横断時間から計算された最早到着時刻は、真の時刻であり得ない。ルート・プランナの出力が、横断時間または全時間を含んでいるなら、修正された横断時間から最適ルートが一旦求まったとき、真の時刻を導き出すために修正されていない横断時間を用いればよい。
【０１２８】
終了に際して、最短時間ルートは、点Bから逆方向へ道路セグメントに沿って辿ると、Teが減少し、２つの終端でのTeの差(点QのTe−点PのTe)が(既知の算術誤差の範囲内で)その道路セグメントをPからQに向かって横切る横断時間に等しくなることによって見つけられる。こうして、Teは点Aに達するまで減少し、そこで逆トレースが終了する。逆トレースの横断時間の合計は、(既知の算術誤差の範囲内で)Teの差の合計、つまり点Bにおける最早到時刻から点Aの出発時刻を減じた値に等しいことが確証され、逆トレース経路はAからBへの最速ルートでなければならない。
【０１２９】
算術誤差を定量化するのが難しい場合の逆トレースに代わる手法は、点Qに対して新しいTe値が出る毎にこの値を格納し、この値の変化をその拡張がもたらした点Pの指数(インデックス)をQと一緒に格納することである。そして、終了後、点Bは、ルート中の前の点を表すような指数を持ち、前の点はその前の点を表すような指数を持つから、点Aに至るまでこれを繰り返せば、全ルートが再構築されることになる。
【０１３０】
このアルゴリズムは、時間に代えて正値費用関数と共に用いることができ、その場合、各道路セグメントは、それを用いるための費用増分(コスト・インクリメント)でラベル付けされ、結果のルートは、点Aと点Bの間の最小費用ルートである。幾つかの道路セグメントの費用は、全費用が負の道路網において可能な循環がない限り、負になりうる。
【０１３１】
地理的に見た場合、拡張されるのを待っている点群は、(非常に大まかに言って)始点Aを中心にして半径が全方向に均等に延びる円をなす傾向がある。これは、終了条件が満たされるとき、点Bから点Aと反対側にある道路セグメントについての計算時間が非常に節約されることを意味し、このような計算は、大抵の場合、労力の無駄であるが、格別に速い点Bへの直接道路に希にヒットすることがある。
【０１３２】
アルゴリズムA2
このルータにおける上述の無駄な計算を避ける助けになる通例の最適化は、ステップSで、Tzを点Pから終点Bまでをデータベース中の最速の道路セグメントの速度で直線走行するに要する時間として、(Te+Tz)が最小値になるような点Pを見つけることである。これは、各点の地理的座標が必ず既知で直線距離が計算でき、データベース中の総ての道路セグメントについて最速の横断速度を既に必ず見つけていることを意味する。この最速の横断速度は、最良の結果を得るべく、各道路セグメントの終点までの直線距離をその道路セグメントの横断時間でコンピュータ除算して求められる。繰り返して言えば、拡張されるのを待っている点を(Te+Tz)値で順序付けてリストに保持することによって、より計算を効率的にするのである。
【０１３３】
さて、地理的に見た場合、拡張されるのを待っている点群は、始点Aを中心にし、計算された最速に対するその道路の平均速度の比に依存して点Bに向かって延びる概ね楕円をなす傾向がある。そして、終了条件は、拡張されるのを待っている総ての点の(Te+Tz)値が、点Bについて見つかった最早到着時刻(Te)よりも大きいことである。この終了条件が満たされると、拡張された点群は、最適化されていないインク汚点ルータにおけるばあいよりも遙かに少ないので、最適化されたルータは、より速く動作し、消費電力がより少ない。
【０１３４】
この最適化されたアルゴリズムに追加の費用関数として馴染みを用いたい場合、各道路セグメントの横断時間を、既述の如く馴染みレベルに依存した百分率で単に修正するだけで済む。しかし、最適化されたこのアルゴリズムA2の場合、データベース中の総ての道路セグメントについて最大修正横断速度を、各道路セグメントの始点から終点までの直線距離をそのセグメントの修正横断速度で除して求めなければならない。こうすると、しない場合よりも最大速度が少し高くなる一方、アルゴリズムの調べる点が、馴染みの重み付けをしない場合に比して少し増える傾向がある。
【０１３５】
馴染みのないルートを捜す場合は、走行時間を人為的に所定百分率だけ増やした馴染みレベルが用いられるので、各道路セグメントで遭遇する最大速度は、少し減少する。従って、最適化されたアルゴリズムは、少し速く動作する。
【０１３６】
ルーティングアルゴリズムには、例えば事前のコンピュータ計算や時刻(１日における時刻)によって変化する横断時間の処理などを含む他の多くの変形例があると理解されなければならない。これらの変形例にも、アルゴリズムA2で述べたと類似の方法で、馴染みを考慮させることができるが、費用関数のみならずルータが依存する仮定を変更することにも注意しなければならない。
【０１３７】
このように馴染みに順応したルータは、殆どの場合、既存のルータのアプリケーションに代えて用いることができる。例えば、所定の目的地へのルートを計算し、最小費用ルートを動的に再計算し、あるいは更に幾つかの地点を必ずしも順番にではなく訪れる(例えば、巡回セールスマン問題)最小費用を計算する車両搭載のナビゲーションシステムに用いることができる。これらのルートの総ては、どの道路セグメントが(可能なら)何時横断されたかをオンボードで観察することから導き出される馴染みによる費用関数を適用することによって、或る部類のドライバに対して改善されることができる。
【０１３８】
同様に、フリート(一団)ユーザに対する集中ルート選定は、一団の車両がどこを走行しているかについての(ライブまたは一括の)情報入力をしばしば備え、この情報が費用関数の馴染みの追加に用いられる。車両がその位置を報告してこない場合でも、車両へ送出されるルートを用いられた道路セグメントを推定する強力なヒントとして用いて、再び馴染みレベルを計算することができる。フリート・マネジャが、全フリートおよび配達スケジュールに亘って最適化を行っていれば、各ドライバに対する馴染みの組み込みは、熟知のルートにドライバを確実に割り当てる助けになる。不馴染みによるあるいは人手による馴染み設定オプションは、ドライバが新しいルートを学びことを希望する場合や配達スケジュールが厳しくない場合に用いることができる。
【０１３９】
デスクトップコンピュータまたは携帯情報端末用のルートプラナは、非常に流行しており、馴染みルーティングから大きな利益を得ている。ここでは、全区域または全道路を馴染みに設定する手による馴染み入力が行われている。より良くは、車両がどこを通ったかを記録でき、その記録をリアルタイムまたは後に一括で、ワィファイ(Wi-Fi),ＧＭＳ(Global Systen for Mobile Communications)データ,ＧＰＲＳ(General Packet Radio Service)などの通信リンクを介する送信またはコンパクトフラッシュ（登録商標）やＳＤメモリなどのリムーバブルメモリ媒体を用いて情報処理装置に利用できるように特別に変更された車両が増えてきている。
【０１４０】
これらは、ルーティングアルゴリズムがどこで用いられるのかを示す例であるが、この技術は、馴染みに関する情報が利用できる総てのルータに適用することができる。
【０１４１】
ここで、２つの例によってどのようにして道路セグメント横断情報が得られるかを述べる。
【０１４２】
サイティング履歴のマッチング
１つの方法は、車両のサイティング(例えば、<緯度,経度,高度>)の履歴を、大多数のGPS衛星測位受信器で用いられているWGS84緯度,経度が通例である座標系に保存することに基づいている。ルート計画データベース中のどの道路セグメントがいつ横断されたかを見つけ出すため、まず、各道路セグメントの終点をそのセグメントの代表として取り上げ、非常に長いセグメントでは、それに沿って100ｍごとに余分に点を設ける。この例では、一方の端点を選んで、この点をP1と呼ぶ。そして、P1から離れる順に一連の中間点P2,P3,…,Pn(他方の端点, nは点の総数)を選ぶ。次に、測位システム(この例ではGPS)の誤差を補償すべく各点から50ｍ以内のサイティングを総て考慮しつつ、選んだ各点の近傍に匹敵するサイティングの履歴を調べ、サイティングの各シーケンス中で最も近いサイティング(大抵の場合、点からの距離が10ｍ以下）をその点に対して匹敵するものに選ぶ。そして、マッチ(匹敵)した２つのサイティングの間に記録された一連のサイティングの総てがその道路セグメント自体に近いままであるか否かを調べる。これを調べる方法は２つあり、１つであるルーズマッチング法は、マッチした一連の点の間の累積距離を道路データベースから分かるその道路セグメントの長さと比較する。累積距離が道路データベースの距離の±10％以内であれば、マッチしたとして受け入れる。横断の方向は、サイティングの時刻から導き出す。即ち、P1のマッチがPnのマッチよりも早いなら、P1からP2への横断であり、そうでなければ、PnからP1への横断であるとする。もう１つのタイトマッチング法は、P1のマッチとPnのマッチの間にある一連の点総てが、その道路セグメントの或る部分の誤差限界(典型的には、GPSに基づくサイティングに対して50ｍ)内にあるか否かをチェックする。このタイトマッチング法は、道路レイアウトが変化すると進路が著しく変化する長い道路セグメント(例えば500ｍ以上)に対して好適に用いられ、道路セグメントの全長が著しく変化しない場合でも、進路の著しい変化を識別することができる。
【０１４３】
このマッチングアルゴリズムは、新たなマッピングデータベースがインストールされた場合は常に、新しい道路データベースに対して車両からのサイティング履歴を作動させることによって一括モードで実行できる。同様に、或る車両から他の車両へサイティング履歴が移された場合、これら車両は全く異なる道路データベースを持ちうるので、馴染みレベルを決めるべく、新しい道路データベースに対してサイティングのリストをマッチングさせることができる。
【０１４４】
リアルタイムのサイティングが利用できる場合、アルゴリズムは、サイティングが入力されると作動できる。この場合、最近のサイティングの位置が用いられ、道路データベースは、このサイティングの位置に最も近い道路を抽出するように調べられる。一連のサイティングについてこの処理が終了すると、道路が比較され、一連のサイティングの総てが十分広い範囲(例えばセグメント長の1/2以上)に亘って同じ道路セグメントにマッチすれば、この道路セグメントに一連のサイティングが最も良くマッチする方向への１の馴染み度を与える。このとき、同じ道路セグメントに留まる限り測位システムの誤動は馴染み度を１回を超えてインクリメントし得ないという理由で、所定期間(典型的には10秒)にこのセグメントから50ｍ以上離れた位置を見つけるまでは、上記道路セグメントは上記方向に再度インクリメントされないことを書き留める。
【０１４５】
道路の直接マッチング
多くのナビゲーションシステムは、道路データベース自体を推測航法システムにおける拘束として用いることによって動作する。推測航法は、典型的には、走行距離を与える車両の路程計からのパルスと、あらゆる回転の角度を与える角度センサからのパルスを用いて行われる。他に赤外線による道路面観察と磁石方位測量を用いて行うこともできる。これらのシステムは、まず、車両がいる道路セグメントとこのセグメントに沿った車両の位置と走行の方向を知る必要がある。これは、車両が動いていた最後の時間から思い出すことができる。車両が行方不明になった場合、これらは、短い一連のGPS位置を取り、これらの位置に最も近い道路セグメントを見つけることによって導き出せる。GPS位置は、各セグメントの所定誤差限界(例えば50ｍ)内にあるかを調べられる。セグメントに沿う位置は、セグメント内の最後のGPS位置に最も近い点として、セグメントに沿う走行の方向は、セグメント内の最初のGPS位置に最も近い点から最後のGPS位置に最も近い点への方向として夫々導き出される。この分析で最も適合するセグメントがどれであろうと、それが最適のセグメントとして選ばれる。車両が路程計のパルスから移動していることが知られていれば、GPS位置は、数秒離れて取られ、道路セグメントとのマッチングが失敗したときは、GPS位置の新たな組によってマッチングが繰り返される。
【０１４６】
一旦、最初のセグメントと位置と方向が推定されれば、車両が現在の道路セグメント上にあるという仮定の下に路程計の読みから、次の位置が導き出される。位置誤差の見積もりは、車両が進むにつれて増加する。角度センサが著しい回転を示した場合、このような回転が推定位置の誤差限界内にあるか否かを調べるべく、道路データベースがチェックされる。そして、誤差限界内にあれば、データベースからその位置は回転位置だと推定され、回転の角度に応じて新たな道路セグメントが選択され、車両が進んでいる新たな道路に沿う位置を導き出すために、再び路程計が用いられる。このアルゴリズムがどの段階で失敗しても、データベース内の別の始点を見つけるため、再びGPSを用いることができる。
【０１４７】
大抵の地図マッチングシステムは、上で述べたよりも複雑化されているが、車両がどの道路セグメントを横切っているかの情報によって大抵の場合動作している。従って、地図マッチングシステムは、横断がされているときはいつもそれに注目して、１点を計数し、馴染み度の計数および馴染みレベルを導き出すべく、上述のアルゴリズムを適用することができる。
【０１４８】
地図マッチングが失敗して、測位のためにGPSを用いる理由には、車両がデータベースにない道路を用いていることもある。この場合、GPS位置は、サイティング履歴のマッチングで述べたように、後のマッチングのために更新に備えてデータベースに格納される。地図マッチングが働いているときは、各道路セグメントについて馴染みレベルとその更新に必要なパラメータ(例えば、計数値)を格納するだけで済む。この場合、地図データベースが更新されるとき、より問題が生じうる。新たに加えられた道路に新たな識別番号を与えるとか、検索精度を上げるためにデータベースを再度セグメント化するとかして、新たに加えられた道路を上手く処理する必要がある。その場合、古い道路セグメントを、サイティング履歴と同様に、新しい道路セグメントと照合する必要があるが、サイティングが与えるような全詳細は不要である。より良い実行方法は、サイティングを、GPSおよび/またはマップマッチングから導き出される座標として保存し、馴染みレベルの再計算が必要になったときにいつでも、保存したデータを新データベースとの一括照合に用いることである。
【図面の簡単な説明】
【０１４９】
【図１】図１は、本発明の実施形態を示す概略ブロック図である。
【図２】図２は、サイティングの記録および走行と走行セグメントを決定する分析を示す図である。
【図３】図３は、サイティングの記録および走行と走行セグメントを決定する分析を示す図である。
【図４】図４は、サイティングの記録および走行と走行セグメントを決定する分析を示す図である。
【図５】図５は、サイティングの記録および走行と走行セグメントを決定する分析を示す図である。
【図６】図６は、相互関連する写真のステップを示すフロー図である。
【図７】図７は、相互関連する日記記載事項のステップを示すフロー図である。
【図８】図８は、走行分析を示す図である。
【図９】図９は、走行分析を示す図である。
【特許請求の範囲】
【請求項１】
移動する対象物が静止している場所を、場所と時刻からなる各サイティングの記録から選択する方法において、
上記対象物の移動のブレイクを識別するステップと、
上記移動のブレイクの持続時間を、そのブレイクの前と後の移動の期間と比較して、持続時間が上記移動の期間の持続と予め定義された関係にあるブレイクを決定するステップと、
上記移動する対象物が静止している場所として、上記決定されたブレイクの場所を選択するステップと
を備えたことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、上記移動する対象物は、点火プラグをもつ車両であり、上記対象物の移動のブレイク識別するステップは、上記車両の点火プラグがオフされたサイティングの組を識別することからなることを特徴とする方法。
【請求項３】
請求項１に記載の方法において、上記対象物の移動のブレイクを識別するステップは、所定の時間を超える期間の間、全く信号が受信されなかった期間を識別することからなることを特徴とする方法。
【請求項４】
請求項１に記載の方法において、上記対象物の移動のブレイクを識別するステップは、後続の場所の組みの総てが、その場所の組のうちの最も早い場所から予め定められた距離以内に、少なくとも所定の最小時間の間だけあるような場所を識別することからなることを特徴とする方法。
【請求項５】
請求項１乃至４のいずれか１つに記載の方法において、上記予め定義された関係は、ブレイクの持続時間が、そのブレイクの前と後の移動の期間の少なくともいずれかよりも長いことであることを特徴とする方法。
【請求項６】
場所と時刻からなる対象物の各サイティングのデータベースに、このデータベースに関係なく与えられる場所と時刻の少なくとも１つに関連する第１の事象を、少なくとも１つの更なる事象と関連づけるためにアクセスする方法において、
サイティングを取り戻すために、上記第１の事象に関連する場所と時刻の少なくとも１つを上記データベースに質問し、
上記場所と時刻のうち取り戻したサイティングのために前回の質問で使わなかった他の１つを返し、
サイティングを更に取り戻すため、返された上記他の１つを上記データベースに質問し、
上記場所と時刻のうち更に取り戻したサイティングのために前回の質問で使わなかった他の１つを返し、
更に取り戻したサイティングの場所と時刻のうちの返された他の１つを用いて、上記第１の事象に関連する上記更なる事象の位置を決定することを特徴とする方法。
【請求項７】
請求項６に記載の方法において、上記第１および少なくとも１つの更なる事象は、日記に記入することを特徴とする方法。
【請求項８】
請求項６に記載の方法において、上記第１および少なくとも１つの更なる事象は、写真画像を記録することであることを特徴とする方法。
【請求項９】
場所と時刻からなる対象物の各サイティングの記録に従ってルート計画システム内でルート計画パラメータを較正する方法において、
少なくとも１つのルート開始位置および少なくとも１つのルート終了位置を受けて、
上記少なくとも１つのルート開始位置と少なくとも１つのルート終了位置の間のルートのための少なくとも１つのルート計画パラメータの値を導き出すために、少なくとも幾つかのサイティングを分析し、
導き出された値に従って上記少なくとも１つのルート計画パラメータを変更し、
上記少なくとも幾つかのサイティングの分析は、受けたルート開始位置とルート終了位置の間を移動するセグメントのリストを決定することであり、この決定は、
上記対象物の移動のブレイクを識別し、移動のブレイクの持続時間をそのブレイクの前と後の移動の期間と比較して、持続時間が上記移動の期間の持続と予め定義された関係にあるようなブレイクを決定し、そのような各セグメントが、上記予め定義された関係を満たすブレイクのない走行であると決定することによって行われることを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、上記記録から導き出された共通の目的地およびルートの少なくともいずれかによって、上記ルート計画システムを増加することを備えたことを特徴とする方法。
【請求項１１】
請求項９に記載の方法において、上記少なくとも１つのパラメータは、平均と分散であることを特徴とする方法。
【請求項１２】
請求項９に記載の方法において、上記少なくとも１つのパラメータは、ルートセグメントの走行時刻であることを特徴とする方法。
【請求項１】
移動する対象物が静止している場所を、場所と時刻からなる各サイティングの記録から選択する方法において、
上記対象物の移動のブレイクを識別するステップと、
上記移動のブレイクの持続時間を、そのブレイクの前と後の移動の期間と比較して、持続時間が上記移動の期間の持続と予め定義された関係にあるブレイクを決定するステップと、
上記移動する対象物が静止している場所として、上記決定されたブレイクの場所を選択するステップと
を備えたことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、上記移動する対象物は、点火プラグをもつ車両であり、上記対象物の移動のブレイク識別するステップは、上記車両の点火プラグがオフされたサイティングの組を識別することからなることを特徴とする方法。
【請求項３】
請求項１に記載の方法において、上記対象物の移動のブレイクを識別するステップは、所定の時間を超える期間の間、全く信号が受信されなかった期間を識別することからなることを特徴とする方法。
【請求項４】
請求項１に記載の方法において、上記対象物の移動のブレイクを識別するステップは、後続の場所の組みの総てが、その場所の組のうちの最も早い場所から予め定められた距離以内に、少なくとも所定の最小時間の間だけあるような場所を識別することからなることを特徴とする方法。
【請求項５】
請求項１乃至４のいずれか１つに記載の方法において、上記予め定義された関係は、ブレイクの持続時間が、そのブレイクの前と後の移動の期間の少なくともいずれかよりも長いことであることを特徴とする方法。
【請求項６】
場所と時刻からなる対象物の各サイティングのデータベースに、このデータベースに関係なく与えられる場所と時刻の少なくとも１つに関連する第１の事象を、少なくとも１つの更なる事象と関連づけるためにアクセスする方法において、
サイティングを取り戻すために、上記第１の事象に関連する場所と時刻の少なくとも１つを上記データベースに質問し、
上記場所と時刻のうち取り戻したサイティングのために前回の質問で使わなかった他の１つを返し、
サイティングを更に取り戻すため、返された上記他の１つを上記データベースに質問し、
上記場所と時刻のうち更に取り戻したサイティングのために前回の質問で使わなかった他の１つを返し、
更に取り戻したサイティングの場所と時刻のうちの返された他の１つを用いて、上記第１の事象に関連する上記更なる事象の位置を決定することを特徴とする方法。
【請求項７】
請求項６に記載の方法において、上記第１および少なくとも１つの更なる事象は、日記に記入することを特徴とする方法。
【請求項８】
請求項６に記載の方法において、上記第１および少なくとも１つの更なる事象は、写真画像を記録することであることを特徴とする方法。
【請求項９】
場所と時刻からなる対象物の各サイティングの記録に従ってルート計画システム内でルート計画パラメータを較正する方法において、
少なくとも１つのルート開始位置および少なくとも１つのルート終了位置を受けて、
上記少なくとも１つのルート開始位置と少なくとも１つのルート終了位置の間のルートのための少なくとも１つのルート計画パラメータの値を導き出すために、少なくとも幾つかのサイティングを分析し、
導き出された値に従って上記少なくとも１つのルート計画パラメータを変更し、
上記少なくとも幾つかのサイティングの分析は、受けたルート開始位置とルート終了位置の間を移動するセグメントのリストを決定することであり、この決定は、
上記対象物の移動のブレイクを識別し、移動のブレイクの持続時間をそのブレイクの前と後の移動の期間と比較して、持続時間が上記移動の期間の持続と予め定義された関係にあるようなブレイクを決定し、そのような各セグメントが、上記予め定義された関係を満たすブレイクのない走行であると決定することによって行われることを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、上記記録から導き出された共通の目的地およびルートの少なくともいずれかによって、上記ルート計画システムを増加することを備えたことを特徴とする方法。
【請求項１１】
請求項９に記載の方法において、上記少なくとも１つのパラメータは、平均と分散であることを特徴とする方法。
【請求項１２】
請求項９に記載の方法において、上記少なくとも１つのパラメータは、ルートセグメントの走行時刻であることを特徴とする方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−１９８２３３（Ｐ２０１２−１９８２３３Ａ）
【公開日】平成２４年１０月１８日（２０１２．１０．１８）
【国際特許分類】
【出願番号】特願２０１２−１２４６４９（Ｐ２０１２−１２４６４９）
【出願日】平成２４年５月３１日（２０１２．５．３１）
【分割の表示】特願２０１０−２２５７２８（Ｐ２０１０−２２５７２８）の分割
【原出願日】平成１７年９月６日（２００５．９．６）
【出願人】（５０７０７８０８３）コタレス・リミテッド (5)
【氏名又は名称原語表記】ＣＯＴＡＲＥＳ ＬＩＭＩＴＥＤ
【Ｆターム（参考）】
【公開日】平成２４年１０月１８日（２０１２．１０．１８）
【国際特許分類】
【出願日】平成２４年５月３１日（２０１２．５．３１）
【分割の表示】特願２０１０−２２５７２８（Ｐ２０１０−２２５７２８）の分割
【原出願日】平成１７年９月６日（２００５．９．６）
【出願人】（５０７０７８０８３）コタレス・リミテッド (5)
【氏名又は名称原語表記】ＣＯＴＡＲＥＳ ＬＩＭＩＴＥＤ
【Ｆターム（参考）】
[ Back to top ]