JP2014527617A5 - - Google Patents

Description

情報の収集および抽出を通じたルート提供 従来技術

多くのシステムでは、運転、ウォーキング、または公共輸送における道順(direction)を提供する。ＢＩＮＧ ＭａｐｓやＭａｐＱｕｅｓｔのようなＷｅｂサイトは１つの場所から他の場所へのこれらの道順を提供することができる。自動車ナビゲーション・ボックスおよびダッシュボード・コンソールのような様々な独立型システムがあり、同様に道順を提供することができる。通常、１つの地点から他の地点への道順を見つけることの課題は、地図を表す、端加重(edge-weighted)有向グラフを用い、またＤｉｊｋｓｔｒａのアルゴリズム、即ちＡ＊を適用してそのグラフを通じて最も低コストな経路を見つけることによって解決される。

このようにして道順を提供することに伴う課題は、それが、グラフが正しい連結性情報を有し且つ最新であることを仮定しているということである。連結性は、グラフ上の分岐が実世界の地理(geography)上ですることができるターン(turn)を正確に表すという特性に関連する。例えば、ノードＡ，Ｂ，Ｃが地図上で場所を表し、且つ、ノードＡからの１つのグラフがノードＢまたはノードＣのいずれかに分岐できる場合には、実世界において分岐の内どちらを取ることが可能であると想定される。これら分岐に対応するターンを実世界で行うことができない場合には、グラフ内の連結性情報は正確ではない。更に、実世界において、道路が追加され若しくは工事のために閉鎖され、または再編成されるために、グラフ内の情報は最新のものでなくなることもある。

デジタル地図プロバイダは、リソースを費やして、それらグラフを正確に且つ最新に維持することを試みている。しかしながら、そうすることは困難であり得るし、また、それらの技術を用いて提供される多くの道順は正確でないこともあり得る。

既存のルートに関する情報は、人々が実際に移動するルートに基づいて、継続的に収集することができる。これらのルートは、格納されることができる。ある人が道順を要求するときは、実世界におけるルートが抽出され、道順を提供することができる。地点Ａから地点Ｂへの完全なルートがストレージ内にないときは、ストレージ内に存在するルートが、特定の特性を満たすように相互に重なり合う限り、これらルートで繋ぎ合わすことができる。このようにして、道順を提供するという課題は、抽象的なグラフからの計算よりも、むしろ情報抽出性の課題へと効果的に緩和される。人々が移動したルートを使用することは、どのルートに信頼性が存在するかということに関する情報を生成する。更に、どのルートを人々が移動したかについての情報は、継続的に収集することができるので、どのルートが利用可能かに関する情報を最新のものとすることができる。

人々が移動したルートについての情報を収集するために、多くの人々が、自分の位置を正確に特定することができるデバイス、例えば、ナビゲーション・ボックス、汎地球測位システム（ＧＰＳ）受信機を備えたスマートフォン等のデバイスを携行するものと認められる。一部の人々は、プライバシーのために、これら機能をオフにする選択(choose)をすることもある一方で、他の人々は、継続的にデバイスに自分の位置を判断させるように「選択(opt-in)」し、サービスによって収集されるこの情報を有することに意欲的になることもある。十分な人々が、収集されるこの種の情報を有するのに意欲的である場合には、収集される未加工の地理的座標は、人々がどんなルートを移動するかについて継続的に更新する情報を提供する。更に、収集される情報は実際のルートを表すので、地図上に現れるどのターンが実際に実世界で行われるか、そのルートを移動するのにどれくらいの時間を要するか、移動時間およびターンの有効性が日時と相関するか、移動時間およびターンの有効性が車両の人々の数とどれくらい相関するか、そしてその他の要因について、その情報は継続的な検証を提供する。

ルートについてデータベースが収集されるときには、そのデータベースは道順の要求に応答するために用いることができる。誰かが地点Ａから地点Ｂへのルートを要求する場合、データベースを検索して、このようなルートがデータベース内に格納されているかどうかを判断することができる。仮にルートが格納されている場合、その経路は道順として抽出および提供することができる。仮にこのようなルートがストレージ内に存在しない場合には、データベースが検索されて、地点Ａから地点Ｂまでに続く最長のルート（即ち、一例としては、より短いルートに一致する長いルートのレグ(leg)の点で補強された最長のルート）を見つけ出す。データベースは次いで、検索されて、実際の地点Ａおよび地点Ｂに対する長距離経路が有する入口地点および出口地点に続くルートを見つける。実際のところは、処理は、最初に長いルートを探すとよく、次いで、完全な道順のセットが生成されるまで、繋ぎ合わせることになるより短いルートを連続して探すとよい。

地図上に存在するターンは実世界に存在してもよく、または存在しなくてもよいので、完全なルートを生成するために部分的なルートを結合するシステムは、接合されることになるルートが幾つかのターンを共有すべきことを主張する。このような状況は、実世界で検証されていないルートについてそのシステムが提供するのを防止する。なお、ルートを連結するためのこの基準は、ルートが上記のような実世界のデータを通じて決定されるか、関連する地理上の抽象表現から単に計算したルートであるかに拘わらず、適用することができる注意されたい。

本要旨は、次の発明の詳細な説明において更に説明する単純化した形態の概念の選択を導入するために提供する。本要旨は、特許請求した主題について主要な特徴または必須の特徴を識別することを意図するのではなく、また、特許請求した主題の範囲を限定することを意図するものでもない。

図１は、どのルートを移動できるかに対する例示の地図についてのブロック図である。 図２は、既知のルートのデータベースを構築するために用いることができる例示のコンポーネントのセットについてのブロック図である。 図３は、ＧＰＳ追跡記録に基づいてルートのデータベースを構築することについての例示の処理についてのフロー図である。 図４は、ルートの問合せに応答するために使用することができる例示のシステムについてのブロック図である。 図５は、既存で既知のルートを抽出することによるルート・クエリに応答することについての例示の処理のフロー図である。 図６は、本願明細書において説明する主題の実装に関し、使用することができる例示のコンポーネントについてのブロック図である。

多くのシステムが地点Ａから地点Ｂへの道順(direction)を提供する。例えば、ＢＩＮＧ ＭａｐｓやＭａｐＱｕｅｓｔのようなＷｅｂサイトは、地図上の任意の位置間における運転、ウォーキングまたは公共輸送の道順を提供することができる。自動車ナビゲーション・ボックスおよびダッシュボード・ナビゲーション・コンソールは、同様に道順を提供することができる。通常、道順は、地図を表す端加重の有向グラフから計算される。具体的には、地図は、ノードのセット、ノード間の有向端(directed edges)、および各端に関連付けられる加重として表すことができる。各ノードは、地図上の交差地点(intersection)を表す。各端は、１つの交差地点から他のものまでの経路を表し、それら交差地点の間の経路が存在すると考えられるときはいつでも端が存在する。そして、各端に関連付けられた加重が、経路に沿って移動するためのコスト（例えば、移動時間）となる。Ｄｉｊｋｓｔｒａのアルゴリズム、即ちＡ＊のようなアルゴリズムは、グラフにおいて１つのノードから他のものまでの最低コストの経路を見つけるのに用いることができる。このようにして、グラフは、地点Ａから地点Ｂへの道順を計算するのに用いることができる。

このようにして道順を提供する場合、特定の課題が生じ得る。第一に、グラフは通常、既存の地図から、または地理上の大規模な写真の分析から構築され、これらのデータ・ソースは、連結性に関する情報を正確には提供しない可能性がある。地図は２つの道路の交差地点を示すことができるが、１つの道路から他のものにターンすることが尚も可能ではない可能性がある。例えば、何故ならば１つの道路が高架交差路にわたって通じているから、何故ならば地方自治体が「ターンするな」という標識を掲げたから、または、何故ならば交通量が多すぎて運転者は実際その交差地点でターンするのを回避するからである。例えば、ある人がＭａｎｈａｔｔａｎにおり、１１番アベニューおよび４２番ストリートのコーナーから、６番ストリートおよびＣｅｎｔｒａｌＰａｒｋ南のコーナーまで移動したい場合には、グラフは、４２番ストリートを東側に移動して、６番アベニューを左にターンし、そしてＣｅｎｔｒａｌＰａｒｋまで北に続くことが可能であることを示す可能性がある。このようなルートは、実世界では理論的には可能であるが、ＮｅｗＹｏｒｋ市が、６番アベニューにおける４２番ストリートで左にターンすることに時間規制を課しており、ターンすることが許される日昼帯においてでさえ、渋滞によりこのターンをするのにとても時間が掛かり、非常に勇敢な運転者のみがこれを試みることになるということを考慮していない。特に、先に述べたマンハッタンの交差地点のような既知で経路理論上(pathological)の場合において、地図プロバイダは、リソースを投じて、これら課題について知識を収集し、その知識をそれら地理的モデルに組み込むこともある。しかしながら、現実性が地図上に示されるものと一致しない多くの場所があり、このような状況の全て特定およびモデル化することは困難である。上記の例は、次の連結性の課題を例示する。即ち、２つの道路間の連結が地図上に存在するように見えるが、実際のところはその連結は存在しないか若しくは特定の日時にのみ存在する、または、作りだすことがとても困難であるため、運転の道順のセットにおいて連結を含むことを回避する理由があるということである。

生じる第２の課題としては、移動できる道路が経時的に変化する傾向にあるということである。新規の道路は追加される。古い道路は、一時的にメンテナンスのために利用できず、または再編成される。交通量のパターンは変化し、このことは、一度は移動するのが容易であった道路を移動するのをより困難にする。新規の交通規制が追加され、一度は許可されたターンを行うのを違法にする。地図プロバイダがこれらの種類の変化に追従することは困難である。何故ならば、情報の収集および分析するためのリソースの増大を伴い、また、その情報を地理モデル（グラフやその他のもの）に追加し当該地理モデルから道順を計算するためのリソースの増大を伴うものだからである。

また、端加重有向グラフは一般的に、加重（コスト）をグラフ上の、即ち１つのノードから他のものへの経路上の端への関連付けを行う。しかしながら、実世界では、移動の内最もコストがかかる（例えば時間がかかる）部分は、交差地点におけるところであって直線経路ではない。例えば、先に述べたＭａｎｈａｔｔａｎの例において、４２番ストリートを運転で下るのにたった１分しかかからず、６番アベニューを運転で上るのに他に１分しかかからないかもしれないが、（ターンが許可される日昼帯の時間であっても）１つの道路から他の道路に左にターンするのに５分かかることもある。言い換えれば、特定ノードからの特定分岐を採用するコストを考慮していない端加重グラフは、ターンをするコストを差し引くことをせず、これによって、全体のルートを実世界よりも低コストに見えるようにしている。しかし、地点Ａから地点Ｂへの最速ルートを探している運転者は、このターンがどれくらいの時間がかかるかを非常に気にすることもあろう。

本明細書において説明する主題は、運転の道順を提供する課題について、これを情報の収集および抽出の課題として対処する。実際に移動することができるルートに関する情報は、実世界では、人々が実際に移動するルートに基づいて収集される。全ての交差地点をグラフ内のノードとして対処する地図の抽象モデルから道順を構築するのではなく、本主題は、既知の情報のセットを、実際に人々が移動したルートのセットとしてモデル化し、また、既知の重なり合うルートから１つのルートを接合することによって、道順のセットを構築する。

ルートについての知識は、人々によって担持されまたは人々の車両に組み込まれるデバイスの全地球測位システム（ＧＰＳ）追跡記録から収集される。（先に注記したように、プライバシーのために、人々の中には、彼らの位置が追跡されることから外れるのを選択することもあるが、多くの人々は、彼らの位置および移動について追跡されるのに同意するであろう。人々がこの種の追跡に明示的に同意するのを促進するインセンティブを与える場合もあろう。）ＧＰＳを装備したデバイスからの経時的な生の地理的座標は、地図に対して相互参照され、その結果、この生データを人々が移動する実際のルートに変換することができる。（例えば、ある座標は、１０秒毎に受け取られるとしてもよい。これは、経時的な変化を実際の地図を比して、その人が移動したルートを決定することにより行なわれる。）移動したルートは、データベースに格納される。ルート自体に加えて、ルートを移動した日時、ルートを移動するのに要した時間、ルートを移動した際に車両に乗っていた人数、使用した車両の種類に関する情報、その他任意の種他の情報があるのがよい。この情報は、特定のルートが特定の日時において混雑していたか、ルートのうち特定の部分が時間的な制約（例えば、午前９時から午後５時までは左ターン禁止）を受けていたか、または、ルートのうち特定の部分が専有若しくは車種による制約を受けていたか（例えば、このルートが、自動車内に少なくとも３人を要するが、ビジネスや単一人のオートバイは許可されるＨｉｇｈＯｃｃｕｐａｎｃｙＶｅｈｉｃｌｅ（ＨＯＶ）レーンを含むこともあり得る）について判断する際に重要となる。（上記の例は、位置情報がＧＰＳ追跡記録から収集されることを想定している一方で、それがまた他の技術、例えば、ＷｉＦｉローカライゼーション、慣性センサ、三角測量等を通じて収集することもできる。ＧＰＳ追跡記録に関しては、このような情報は、ユーザからの適切な受信の許可に従って収集することができる。）

（上記の技術を用いて収集したような）既知のルートのセットを収容する、あるデータベースの存在を想定すると、道順を提供するシステムは、既存のルートからの道順のセットを繋ぎ合わせることができる。ルートは「レグ」で構成される。「レグ」は交差地点間のセグメントである。（「交差地点」とはこの場合、２つ以上の道順においてターンが可能な地点のことである。）ある人が地点Ａと地点Ｂの間の道順を求める場合には、システムは、データベース内を参照して、実際のルートがそれら２つの地点間に存在するかを判断する。このようなルートが存在する場合には、そのルートを道順として提供することができる（但し、システムはまた、より小さいルートのセットからより低コストなルートを構築するのを試みることもある）。一般的に、ルートが長いほどより情報量が多い(informative)と考えられる。何故ならば、ルートがより長いということは、１つの地点から他の地点に行く方法について実際の人により行なわれる判断のセットもより多くなることを示すためである。（この状況を考察する１つの方法は、より長いルートは、より小さいルートから共に接合されるルートよりも、１つの言語から他のものへの完全な文章の翻訳は、その文章の個々の単語から共に接合した翻訳よりもより信頼性があるということと同一の意味で、より信頼性があるということである。）より長いルートはまた、ルート決めの処理を単純化および高速化することもできる。何故ならば、より長いルートは、１つの地点から他の地点までの距離のうち重要な部分をカバーすることもあり、これにより、より短いルートが使用される場合になされる必要がある接合の量を減らすからである。（長いルートが１人の人によって無計画に移動され得ることに注意することになろうが、場合によっては、１つのルートが、経時的に何人かの人々によって移動されなかった場合には信頼すべきものとはみなされないこともある。または、長いルートは、そのレグが他のより短いルートの部分としてあわせて移動された限りにおいて信頼すべきものとみなされることもあり、これにより、長いロートについての精度および／または知識に対し確証を提供する。）しかしながら、地点Ａから地点Ｂまでの全ての距離をカバーするルートが利用可能ではない場合には、本システムは、他のルートを組み合わせるよう試行することができる。

ルートを結合するために、本システムは、少なくとも１つのレグにおいて重なり合う、また、共通して少なくとも１つのターンを有する複数のルートを探す。複数のルートが共通してターンを有するという状態は、本システムが、道順のセットにおいて、実世界では検証されなかった、１つのルートから他のルートへのターンを有しないことを確証する。このようなターンを回避することは、先に説明した、地図上に存在するように見えるが、実世界では不可能であるかまたは非実用的なターンを含むことについての課題を回避する。連結されることになるルートが共通してターンを有するという条件を課すことは、道順に含まれるターンが（少なくとも人々、が行なった実世界の移動からルートが導出される場合の例では）可能であり実用的であると実際の人々によって検証されたのを確証する。（場合によっては、本システムは、２つ若しくは３つまたはｎ個の連続する共通のターンを、ルートを共に連結するための条件として強要することもあり、このことはより現実的なルートを導き得る。しかしながら、本明細書の主題は、このような条件を用いるシステムには限定されない。）

先に注記したように、長いルートの方が短いルートよりもより情報量が多いと考えることができる。既知のルートからの道順のセットを繋ぎ合わせるときは、本システムは、（おそらくは長いルートのレグが、他のより短いルートの部分として移動したことにより補強されるという状況を受けて）長いルートで開始することができる。その一方で、より短いルートを用いてギャップまたはエンドポイントへの接続を満たす。例えば、ある人がカリフォルニア州のＢｅｒｋｅｌｅｙからニュージャージー州のＰｒｉｎｃｅｔｏｎに移動することを望む場合は、Ｂｅｒｋｅｌｅｙからネバダ州のＷｉｎｎｅｍｕｃｃａまでのルート、次いでＷｉｎｎｅｍｕｃｃａからアイダホ州のＰｏｃａｔｅｌｌｏまでのルート、次いでＰｏｃａｔｅｌｌｏからモンタナ州のＷｅｓｔＹｅｌｌｏｗｓｔｏｎｅまでのルート、次いでＷｅｓｔＹｅｌｌｏｗｓｔｏｎｅから ワイオミング州のＣｏｄｙまでのルート等を組み合わせることによってこのルートを接合することが可能であろう。しかしながら、このようにしてルートを接合するのではなく、一例ではシステムは、Ｂｅｒｋｅｌｅｙの近くにある地点からＰｒｉｎｃｅｔｏｎの近くにある地点までのより長いルートを探してもよい。このように、本システムは、ＳａｎＦｒａｎｃｉｓｃｏからＮｅｗＹｏｒｋまでのルートで開始してもよく、また、Ｂｅｒｋｅｌｅｙからそのルートに沿って最も近いフリーウェイの入り口までのより短いルート、およびフリーウィエの出口からＰｒｉｎｃｅｔｏｎまでのより短いルートを探してもよい。即ち、Ｂｅｒｋｅｌｅｙから近くのフリーウェイの入口までの既知のルートがない場合には、本システムは、更に非常に細かい(finer-grained)ルート、例えば、ＢｅｒｅｌｅｙのダウンタウンからＢｅｒｋｅｌｅｙのＳｈａｔｔｕｃｋアベニューまでのルート、およびＳｈａｔｔｕｃｋアベニューからＩ−５８０までのルートを探してもよい。一般的に、本システムは、より長いルートから開始し、次いで、地点Ａから地点Ｂまでの道順の完全なセットが生成されるまで、繋ぎ入れるための非常に細かいルートを連続して探してもよい。

これより図面を参照する。図１は例示の地図１００を示し、この地図の上のルートを移動することができる。地図１００は、この例では、複数のストリートを直角に有する矩形グリッドとして示される。しかしながら、地図が如何なる形状の経路をもフォローし、且つ如何なるやり方でも交差する、如何なるストリートのセットをも示すことができることが理解されよう。

地図１００では、水平方向に（１番ストリートから７番ストリートまで）番号付けがされ、垂直方向に（ＡストリートからＧストリートまで）文字付けがされている。これらのストリートに沿った既知のルートは、ストリートに沿うより暗く太い線で示されている。先に注記したように、人がこれらのルートに沿って移動するのが実際に観察されたという意味で、これらのルートは「既知」のものとすることができる。しかしながら、ルートは、人がそのルートを移動したという実際の観察ではない幾らかの機構を通じて既知とすることができる。図１に示すルートは、ルートおよびルートが存在する地図についての様々な特性を実際に示している。これらの特性について以下に説明する。

ルート１０２は、６番およびＡストリートのコーナーで開始するルートであり、また、７番およびＢストリートのコーナーで終了する。ルート１０２は、２つのレグ１０４および１０６を有する。「レグ」は、ルートの一部であり、そのルートから逸れる可能性がない。つまり、レグ１０４は、６番およびＡストリートのコーナーから６番およびＢストリートのコーナーまで続くルート１０２の一部をカバーする。それら２つのコーナー間に交差地点がないので、それら２つのコーナー間のルート１０２部分はレグとなる。同様に、６番およびＢストリートのコーナーと７番およびＢストリートのコーナーの間には交差地点がないので、ルート１０２の当該部分もまたレグ（レグ１０６）となる。同様に、ルート１０８は、レグ１１０，１１２，１１４を含んでいる３レグのルートである。ルート１０８は、如何なる「ターン」もなしていないように見える（ルート１０８は６番ストリートに沿って直進する）ものの、ルート１０８は、それが、移動する者がどこに向かうかについて判断する必要がある２つの交差地点を越えるという意味で「ターン」を有するとみなされる。例えば、６番およびＤストリートの交差地点において、左にターン、右にターンまたは直進することが可能であるので、その交差地点を通過して６番ストリートを直進するとの判断が「ターン」として理解される。ルート１０８に沿ったこのような交差地点は、そのルートを３つのレグに分割している。

交差地点を通じて直進することを「ターン」と解釈することができるのと丁度同様に、物理的なコーナーを通じて進むルートは、非ターンとして理解することができる。例えば、ルート１１６は、Ｇストリートを進み、次いでＮｕｌｌストリートのコーナー９０度を通じて進む。しかしながら、Ｇストリートが終了し、またＮｕｌｌストリートがこの９０度の角度の地点で開始するので、この角度を通じた前進は、幾つのレグがルート上にあるかを判断する目的としての「ターン」とはみなされない。何故ならば、Ｇストリートに沿ってＮｕｌｌストリートまで移動する者は、Ｎｕｌｌストリートに向けて左にターンする以外の選択がないからである。

様々な他のルートがまた示される。ルート１１８は、１番およびＡストリートのコーナーから３番およびＣストリートのコーナーまで進む。先に説明した理由により、１番およびＢ、１番およびＣ、並びに２番およびＣの交差地点は、全てターンとみなされる。このような３つの交差地点があるので、ルート１１８は、４レグのルートとなる。ルート１２０は、１番およびＣストリートから４番およびＥストリートまで進む５レグのルートである。ルート１２２は、３番およびＤストリートから５番およびＦストリートまで進む６レグのルートである。ルート１２４は、１番およびＣストリートから５番およびＦストリートまで進む７レグのルートである。これらのルートを以下に用いて、どのようにして既知のルートが結合されて道順のセットを提供するかについて様々な態様を実証する。

ルート１０２，１０８，１１６，１１８，１２０，１２２，１２４がデータベースに格納されており、また、ある人が地点Ｘ（１番およびＡのコーナー）から地点Ｙ（５番およびＦのコーナー）への道順について尋ねたとする。地点Ｘから地点Ｙに実際に続く既知の単一のルートがないものと認められるであろう。しかしながら、この要求を処理しているシステム（例えば、自動ナビゲーション・システム、またはＢＩＮＧＭａｐｓのようなウェブサイト）は、既存の複数のルートを結合して、ＸからＹへの道順を生成する。本システムは、最初にルート１１８の第１の２つのレグをルート１２４の全てのレグと結合しようと試みる。しかしながら、ルート１１８および１２４は、共通のレグまたはターンを有しない。先に述べたように、一例では、本明細書の主題は、実世界で検証されていないターンの生成を回避できることであり、よって、本システムはこれらルートの結合を回避することができる。ルートが共通して交差地点を有するように見える（すなわち、１番およびＣストリートのコーナー）ものの、この交差地点は共通のターンを表すものではない。何故ならば、これらのルートは、何者かが、１番ストリートに沿ってＣストリートの交差地点を通じて直進することを示さないからである。言い換えれば、Ｃストリートを通じた直進は、本システムに「既知」のルート部分ではない。何故ならば、何者かがこのルートを移動した証拠がないからである。（例えば、その交差地点には、直進するのを妨げるコンクリートの障害物があるかもしれない。但し、このようなバリアは地図からは明らかではない。）

システムはまた、ルート１１８，１２０，１２４を接合しようと試みることができる。図示のように、ルート１１８および１２０は２つの重なり合うレグ（１番およびＣから２番およびＣへのレグ、並びに２番およびＣから３番およびＣへのレグ）を有する。しかしながら、ルート１２０の終了がどこでルート１２０が終端するかについてあたかもピックアップできるかのように見えるものの、ルート１２０および１２４は共通したレグおよびターンを有していないことに注意されたい。むしろ、ルート１２０は、４番およびＥストリートのコーナーにおいてルート１２４と直角をなして終了する。よって、４番ストリートからＥストリートへのターンを含む既知のルートはない。つまり、ルート１２４は、ルート１１８および１２０の組合せに付加することができない。しかしながら、ルート１２２はルート１２０と共通した２つのレグを有している。即ち、３番およびＤから４番およびDへのレグ、並びに、４番およびＤから４番およびＥへのレグである。つまり、ＸからＹへのルートは、ルート１１８，１２０，１２２の部分を結合することによって構築することができる。なお、ルート１１８，１２０，１２２を結合することによって作成されるルートは、遠回りのように見える点に注意されたい。何故ならば、Ｅストリートに沿って５番ストリートから６番ストリートに進み、次いでＦストリートに沿って６番から５番に戻ることを伴うからである。しかしながら、ルート１２２をルート１２４と結合することによって、このルートは、幾らか短縮化することができる。ルート１２２および１２４は共通してレグを有する（４番およびＥから５番およびＥへのレグ）ので、ルート１２２をルート１２４の最後の２つのレグと結合して、この遠回りのルートを採用するのを回避できることができるかもしれない。（しかしながら、実施においては、２つのルートを結合する前に、２つのルートが２つ以上のレグを共通して有することを強要するものもある。共通したより多数のレグを有するルートは、実世界の移動では、より円滑で、余り「変わりやすい(choppy)」ことのないものと感じる結果とすることができる。何故ならば、このようなルートは、実際に人々が移動した複数レグによる拡張(stretch)を有するからである。

道順のセットがルート１１８，１２０，１２２，１２４から生成される場合、地点Ｘから地点Ｙへの完全な道順は点鎖線（線１２６）によって示される。これらの道順は、既知のルートのセットを共に接合して構築され、要求した者に、地点Ａから地点Ｂへ行き着く方法として提供される。このようにして、道順を提供する課題は、既知のルートのデータベースからルートの正しい組み合わせを抽出するという課題や、それらルートを共に接合するための特定の規則に従うという課題を減らす。

なお、図１の例に示したルートは、矢印によって示されるように有向性がある(directional)ことに注意されたい。例えば、ルート１０２は、６番およびＡストリートのコーナーから７番およびＢストリートのコーナーまで続くルートである。７番およびＢストリートのコーナーから６番およびＡストリートのコーナーまでという逆方向に続くものはルートではない。本明細書の主題の一態様は、人々が実際に移動したルートについての情報をレバレッジすることであり、また、一方向にルートを移動することがそのルートを反対方向に移動することとは異なる課題を提示することができる。（例えば、ストリートが一方通行かもしれないし、または、特定のターンが、そのターンの方向やどの道を移動しているかによっては違法となるかもしれない。）しかしながら、本明細書の主題は、有向のルートに限定されず、非有向性のルートを用いるシステムを含む。

図２は、既知のルートについてのデータベースを構築するのに使用することができるコンポーネントのセットの一例を示す。図２の例は、人々が実際に移動したルートから構築されているデータベースを示す。しかしながら、先に注記したように、本明細書の主題についての特定の態様は、既知のルートがこのようにして収集される場合に限定されない。

図２において、車両２０２は、（矢印２０４で指示されるような）ルートに沿って移動する。車両２０２は自動車による例で示される。但し、車両２０２は、任意の種類の車両、例えば、バス、トラック、オートバイ、自転車とすることができる。更に、図２の例では車両が移動しているルートを示す一方で、他の例では、ルートは、車両は如何なる種類の車両なしで動く歩行者により移動されるものとすることができる。

車両２０２にはＧＰＳデバイス２０６が備わっている。ＧＰＳ装置２０６は、携帯用ナビゲーション・ボックス、ダッシュボード搭載ナビゲーション・コンソール、ＧＰＳ受信機を具備するスマートフォン、その他任意の種類のデバイスとしてもよい。ＧＰＳデバイス２０６は、地球上のその現在位置を決定することができ、また、その位置の座標を受信機に送信することができる。（先に注記したように、プライバシーのために、ある人が彼／彼女の位置を追跡または送信されないように選択するかもしれないが、人々の中には、自ら進んで、彼らの位置が送信されるのを許可するよう選択することになる者もいる。）ＧＰＳデバイス２０６は、その情報を（例えば、セルラ・フォン・ネットワークを介して）ＧＰＳ追跡記録受信機２０８に送信する。

ＧＰＳ追跡記録受信機２０８が受信する情報は、ある時間期間にわたり展開される(spread out)座標のストリームとすることができる。例えば、車両２０２が移動している全ての時間にわたり、ＧＰＳ追跡記録受信機２０８は、１０秒毎に座標を受信してもよい。これらの座標を用いて、どのルートを車両２０２が移動したか、そのルートを移動するのにどれくらい要したか、そして、ルートの特定部分を移動するのにどれくらい要したかさえも決定することができる。ＧＰＳ追跡記録受信機は、この情報を地図対ＧＰＳ追跡記録対応付けエンジン２１０に提供する。当該エンジン２１０は、ＧＰＳ追跡記録に基づくルートの生成者として動作する。座標は単に生の位置データ（例えば、緯度と経度座標）であるので、エンジン２１０はこれらの座標を実際の地図に適用して、どんなルートを車両２０２が移動したかを判断することができる。例えば、ＧＰＳ追跡記録受信機は、車両２０２が次の時刻で次の位置にあったことを見つけ出すことができる。即ち、

しかしながら、これら時刻および座標は、車両２０２がＭａｄｉｓｏｎストリートとＵｎｉｏｎストリートの間で、Ｓｅａｔｔｌｅの４番ストリートを北進しているのを示すことをエンジン２１０は判断することができる。

どの実際のルート２１２がＧＰＳ追跡記録に対応するかについてエンジン２１０が一旦判断すると、エンジン２１０はルート２１２をルート・データベース２１４に格納することができる。ルート・データベース２１４は、車両２０２から（および多数の他の車両から）識別された各ルート２１２を収容することができる。更に、ルートごとに、データベース２１４は、時間情報２１６および／またはコスト情報２１８を格納することができる。時間情報２１６は、ルートが観察された時刻、また移動に要した時間を示す。先に検討したように、ルートによっては、一日の内ある時間で利用可能であるが、他の時間では利用可能でない場合もあり得る。（例えば、ラッシュアワーの間は左にターンをすることに対する制限があることもあり、あるレーンでは朝と夕方のラッシュアワーの間で方向がスイッチすることもある。）つまり、既知のルートからの道順のセットを生成する際は、何時にそのルートが観察されたかを知ることが重要となり得る。コスト情報２１８は、特定ルートを移動するためのコストを示すことができる。そのコストは、時間に基づくものとすることができる。（例えば、移動に長時間を要するルートは、より短い時間で移動できるルートよりもより高い「コスト」を有するものと見られる。）しかしながら、コストはまた、他の要因に基づくことにもなり得る。例えば、距離、速度制限、既知のスピード監視区間の存在、通行料金の存在有無、その他任意の情報である。ルートを移動するコストは、コスト分析機２２０によって決定することができる。コスト分析機２２０は、これら要因（または他の要因）を考慮することができ、また、コスト情報２１８を任意の所与のルートについて決定することもできる。

図３は、フローチャートの形態で、ＧＰＳ追跡記録に基づいてデータベースを構築する例示の処理を示す。図３の説明に行く前に、本明細書（図３および図５の両方）に含まれるフロー図は、図１、図２および図４に示したコンポーネントに関し、例示の方法により説明される。但し、これらの方法は如何なるシステムでも実行されることができ、図１、図２および図４に示したシナリオに限定されないことに注意されたい。また、図３および図５のフロー図のそれぞれは、処理の段階が特定の順序で実行されることを、ブロックを接続する線によって示した一例を示しているが、これらダイヤグラムに示される様々な段階が任意の順序で、または任意の組み合わせ若しくは下位の組み合わせで実施することができる。

３０２において、ＧＰＳ追跡記録を受信することができる。３０４において、ＧＰＳ追跡記録を地図に適用して、その結果、ＧＰＳ追跡記録によって表されるルート、例えば、座標を取得することができ、また、それら座標を受信する時刻を分析して、これら座標を報告するＧＰＳデバイスが、どの道路（１または複数）を移動したか、いつ道路を移動したか、およびどの方向に移動したかについて判断することができる。

３０６において、ルートが複数のレグを有するかを判断する。先に注記したように、レグとは、可能なターンが存在しないルートにおけるセグメントのことである。１つのレグだけを有するルートは、他のルートと結合されることができないルートである。何故ならば、１レグのルートは異なるルートにターンする方法を含まないからである。つまり、仮にルートが２つ以上のレグを有していない場合には、そのルートは格納されない（３０８において）。一方で、仮にルートが２つ以上のレグを有する場合には、３１０において、そのルートはデータベースに格納される。

格納されたルートごとに、そのルートと関連付けられるコストを算出することができる（３１２において）。コストは、様々な要因に基づくものとすることができる。それらの要因３１４の幾つかの例について、図３に示す。

要因の一例は、ルートを移動するのに要した時間である（ブロック３１６）。人々が１つの場所から他の場所への最速のルートを求める傾向にあるのを想定すると、移動するのにより長く時間を要するルートは、移動により時間を要しないルートよりもより高いコストを有するものと見られる。考慮し得る他の要因は、ルートにおいて各ターンに関連付けられる時間である（ブロック３１８）。（交通量がない）直進道路に沿って移動することは、比較的速くできるので、ルートを移動するのに費やされる時間の多くはターンにおいて費やされ得る。つまり、ターンがどれくらいの時間高コストかを知ることが重要となろう。加えて、ルート部分が共に結合されて道順のセットを生成するので、そのルートを移動する全体のコストとは別個に、且つそれとは離れて、特定のターンを行うのに要する時間がどれくらいかを知ることが重要となることもある。何故ならば、ターンのコストは、２つのルートを接合するのがどれくらいのコストがかかるかを判断するからである。つまり、ルートにおいてターンを行うのに要する時間は、全体コストを算出する際に考慮されるのがよく、また、全体のコストとは別に格納するのがよい。

考慮するとよい他の要因は、ルートを移動した日時である（ブロック３２０）。例えば、ルートを午前３時００分に移動して、移動に２０分要した場合、このことは、午後５時００分にルートを移動するのに２０分要した場合よりも、コスト算出において別個に見られるのがよい。何故ならば、午後５時００分ではより多くの交通量があったと予想されることになるからである。つまり、そのルートを実際に移動した日時は、ルートの全体コストを決定するのに考慮することができる。場合によっては、異なるコストは異なる日時について算出するのがよい。何故ならば、移動が発生した日時は、どのルートを人に推奨するかを判断するのに非常に重要なものとすることができるからである。

考慮するとよい他の要因は、ルートが観察された時の車両の搭乗者数である（ブロック３２２）。（この情報は、車両の運転者によって自己報告するのがよい）搭乗者の数が関係する理由は、幾らかのレーンは、占有規制を有しており（例えば、ワシントン州のＳＲ―５２０は、少なくとも３人の搭乗者がいう車だけが使用することができるＨＯＶレーンを有する）、通行料金を課金する幾らかの道路は、車両内の搭乗者数に基づいてディスカウントをすることがある（例えば、少なくとも３人の搭乗者がいる自動車はリンカーン・トンネルを東に渡るために、通常の８ドルではなく２ドルを払う）からである。つまり、コストは、何人の搭乗者が車両にいるに基づくものとすることができる。ラッシュ時間の間にＨＯＶレーンを使用できるということは、ルートを移動するのに要する時間を著しく低減することができ、また、通行料金の額を削減することは、他の方法による移動のコストを削減する。したがって、場合によっては、ルートについての異なるコストを、車両内の人々の異なる数について算出するのがよい。

上記はルートのコストに関連付けられる例示の要因についてのリストである。このリストはまた、どのルートを推奨するべきかについて判断するのに使用することもできる。しかしながら、運転者が地域の住民、若しくはそのエリアへの訪問者か（訪問者は地元の人よりもより単純なルートを好む傾向にある）、または車両の種類（高さのある車両は特定の高架交差路の下を通行する困難性を有することがあり、長い車両は特定のターンを行う困難性を有することがあり、商用のトラックは秤量所で停車する必要がある）のような他の要因をも考慮するのがよい。

３２４において、算出されたコストを格納することができる。なお、コストは数でもよいが、特定の変数に基づいて発生する数を用いた関数とすることもできる点に注意されたい。例えば、ルートを移動するためのコストが、当該ルートを移動した時刻（ｔ）および車両内の人数（ｎ）に基づくものである場合、その「コスト」は、実際のところはＣ（ｔ，ｎ）のような関数とすることができ、当該関数は、ルートを移動するためのコストを計算にする際に時間および車両の占有を考慮している。他の種類のコストがまた、例えば買い物での移動についての状況や文脈に従って計算することもでき、数多くの停車が（たとえ、当該停車がその移動をより長いものにする場合であっても）その移動のコストを低減させるものとして解釈するとよい。何故ならば、ある人が多くの店を訪れる買い物での移動は、ある人が停車をすることなく素早く道路に沿って移動する買い物の移動よりもより効率的と考えるとよいからである。

ルートのデータベースが一旦構築されると、それらのルートはルート・クエリに対し応答するのに用いることができる。（しかしながら、先に注記したように、本明細書で説明する技術は、基地のルートのデータベースが実際のＧＰＳ追跡記録から生成されるか、またはある他の方法で生成されたかに拘わらずルート・クエリに応答するのに用いることができる。）図４は、ルート・クエリに応答するために用いることができるシステムの一例を示す。

クエリ・プロセッサー４０２は、ルート・クエリ４０４を受け取る。一例のルート・クエリは「ＣＡ州のＢｅｒｋｌｅｙからＮＪ州のＰｒｉｎｃｅｔｏｎまで」であり、これは、このようなクエリが地図のＷｅｂサイトに入力することができる形態である。しかしながら、ナビゲーション・ボックスへの宛先の入力のようなクエリはいかなる形態ともすることができる。ナビゲーション・ボックスは、該ナビゲーション・ボックスの現在位置からどこの行先への道順についてもクエリを効率的に構成する。（その結果、現在位置および指定した行先はクエリの２つのエンドポイントとして扱われる。）
既知のルートは、ルート・データベース２１４に格納される。つまり、クエリ・プロセッサー４０２は、どんな既知のルートがクエリ４０４に応答するために使用できるかについて判断するために、ルート・データベース２１４を参照することができる。クエリ４０４で特定されるエンドポイント間を走るルートがルート・データベース内に場合には、このルートを検索することができ、また、道順４０６として提供することができる。（図４に示すように、道順４０６の一例は、「メインストリートに左にターンし、Ｉ−８０のフリーウェイに進入し、９００マイル東に移動する・・・」である。)
クエリ・プロセッサー４０２は、ルート合成機４０８を含むことができる。ルート合成機４０８は、データベース２１４内のルートを共に接合して、新規のルートを組み立てることができるソフトウェアおよび／またはハードウェアを構成する。ルートがデータベース２１４内のクエリのエンドポイント間にない場合には、ルート合成機４０８は、既に存在する既知のルートからルートを構築することができ、この構築されたルートを道順として提供することができる。ルート合成機４０８は、図１に関連して上で説明し、また次の図５にも関連して追加で詳細に説明する技術を用いたようなルートを構築することができる。

図５は、既に存在する既知のルートを抽出することにより、ルート・クエリに応答する処理の一例を示す。５０２において、ルート・クエリ（例えば、「ＣＡ州ＢｅｒｌｅｌｅｙからＮＪ州Ｐｒｉｎｃｅｔｏｎまで」）が抽出される。５０４において、本処理は、ルート・データベース２１４内で、クエリのエンドポイントにアプローチする最長ルートを探すことができる。場合によっては、ルート・データベース２１４は、実際には、クエリにおける２つのエンドポイント間のルートを収容することになり、この場合、本処理は、道順のセットの形態でこのルートを提供することによって単純に応答することができる。しかしながら、多くの場合には、ルート・データベース２１４は、必ずしもクエリにおけるエンドポイントに一致するルートを含むわけではない。この場合、図５の本処理は、他のルートからそれらエンドポイント間のルートを構築することを試みる。

このようなルートを構築するために、本処理は、クエリの開始地点に近い場所からクエリの終了地点まで続く長いルートを見つけることを最初に試みることによって、既存のルートの長さを考慮することができる。例えば、ＢｅｒｋｅｌｙからＰｒｉｎｃｅｔｏｎへのクエリに関しては、ＳａｎＦｒａｎｃｉｓｃｏがＢｅｒｋｅｌｅｙの近くにあり、ＮｅｗＹｏｒｋがＰｒｉｃｅｔｏｎの近くにある。データベース２１４がＳａｎ ＦｒａｎｃｉｓｃｏからＮｅｗＹｏｒｋへのルートを収容する場合には、ルートは、ＢｅｒｋｅｌｙからＰｒｉｎｃｅｔｏｎへのルートを構築するための基礎として使用することができる。ＳａｎＦｒａｎｃｉｓｃｏからＮｅｗＹｏｒｋへのルートは、開始地点として選ぶことができる。この例では、何故ならば、クエリが特定するエンドポイントへのルートについて開始地点と終了地点の近接度により、ＳａｎＦｒａｎｃｉｓｃｏからＮｅｗＹｏｒｋへのルートが選ばれるからである。データベースに存在する長いルートは、特に信頼性が高いものとみなされ得る。何故ならば、１つの地点から他の地点に移動する方法についてのある人の実際の選択をそれは表すからである。つまり、図５の処理は、長いルートを探すことによって開始することができ、また、ギャップを満たすために短いルートを使用することができる。このように、データベースから抽出される１つ以上のルートは、ルート・クエリにおいて名付けられる１つのエンドポイントから他のエンドポイントに、単独または組み合わせのいずれかで続くルートとなる。

従って、長いルートが一旦選択されると、５０６において、本処理は、小さいルートを連続して探して、より大きなルートへのエンドポイントに接合する。例えば、ＳａｎＦｒａｎｃｉｓｃｏからＮｅｗＹｏｒｋへの長いルートが、ＢｅｒｋｅｌｅｙからＰｒｉｎｃｅｔｏｎへのルートを構築する基礎として選ばれたときには、本処理は、Ｂｅｒｋｅｌｅｙからその長いルート上の交差地点に続くルート、およびその長いルートの交差地点からＰｒｉｎｃｅｔｏｎに続く他のルートを探すことができる。ＳａｎＦｒａｎｃｉｓｃｏからＮｅｗＹｏｒｋへのルートに対してＢｅｒｋｅｌｅｙと交差地点の間にルートが存在しない場合には、本処理は、より小さいルートを連続的に探してこのようなルートを構築する。先に説明したとおり、ルートを選ぶ処理を支配することができる規則の一例は、２つのルートの重なり合いの程度がある基準（例えば、それらが共通して幾らかの数のレグを有する場合や、１つのルートから他のルートに対するターンがあるとき）を満たす場合にのみその２つのルートを接合することである。

共通のレグを有するルートが一旦識別されると、（５０８において）これらのルートは共通のレグにおいて接合することができる。ルートを見つけ出す処理は、繰り返し実行することができ、また、いくつかのルートを作成することができる。５１０において、これらの競合するルートのコストを比較することができる。５１２において、本処理は、最低コストのルートに基づいて道順を提供することによって、５０２において受け取ったクエリに応答することができる。

図６は、本明細書に説明する主題の態様を展開した例示の環境を示す。
コンピューター６００は、１つ以上のプロセッサー６０２および１つ以上のデータ記憶コンポーネント６０４を含む。プロセッサー（１または複数）６０２は、通例、例えば、パーソナル・デスクトップまたはラップトップ・コンピュータ、サーバ、ハンドヘルドコンピューター、その他の種類のコンピューティング・デバイスに見受けられるようなマイクロプロセッサーである。データ記憶コンポーネント（１または複数）６０４は、短い期間または長い期間にわたりデータを格納することができるコンポーネントである。データ記憶コンポーネント（１または複数）６０４の例には、ハードディスク、リムーバブル・ディスク（光および磁気ディスクを含む）、揮発性および不揮発性のランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリ・専用メモリ（ＲＯＭ）、フラッシュ・メモリ、磁気テープ等が含まれる。データ記憶コンポーネント（１または複数）は、コンピューター可読記憶媒体の例である。コンピューター６００は、ディスプレイ６１２を備えるか、これに付随することができる。ディスプレイ６１２は、陰極線管（ＣＲＴ）モニタ、液晶ディスプレイ（ＬＣＤ）モニタ、または他の任意の種類のモニタとしてもよい。

ソフトウェアは、データ記憶コンポーネント（１または複数）６０４に記憶することができ、１つ以上のプロセッサー（１または複数）６０２上で実行することができる。このようなソフトウェアの一例がルート検索・構築ソフトウェア６０６であり、図１から図５に関して先に説明した一部またはすべての機能を実装することができる。但し、如何なる種類のソフトウェアも使用することができる。ソフトウェア６０６は、例えば、１つ以上のコンポーネントを通じて実装することができ、分散システムにおけるコンポーネント、別個のファイル、別個の関数、別個のオブジェクト、別個のコード・ライン等としてもよい。（例えば、パーソナル・コンピューター、サーバ・コンピューター、ハンドヘルドコンピューター等の）コンピューターは、プログラムがハードディスクに格納され、ＲＡＭにロードされ、コンピューターのプロセッサー（１または複数）で実行され、図６に示したシナリオを類型化する。但し、本明細書において説明した主題はこの例示に限定されない。

本明細書に記載した主題は、１つ以上のデータ記憶コンポーネント（１または複数）６０４に格納される、また、１つ以上のプロセッサー（１または複数）上で実行されるソフトウェアとして実装することができる。他の例では、本主題は、１つ以上のコンピューター可読記憶媒体またはコンピューター可読記憶メモリに格納される命令として実装することができる。光ディスクまたは磁気ディスクのような有形媒体は、記憶媒体の例示である。命令は、非一時媒体上に存在させることができる。このような命令は、コンピューターまたは他のマシンによって実行されるときに、該コンピューターまたは他のマシンに、方法が有する１つ以上の行為を実行させることができる。それら行為を実行させる命令は、１つの媒体に保存することができ、または、複数のメディア全体に拡散することができる。その結果、この命令は、全ての命令がたまたま同一の媒体上にあるか否かに拘わらず、１つ以上のコンピューター可読記憶媒体上に集合しているように見えることもある。なお、信号が「格納」される媒体と、これと対比して伝播信号を送信する媒体との間には相違がある点に注意されたい。ＤＶＤ、フラッシュ・メモリ、磁気ディスク等は、記憶媒体の例示である。他方で、信号が短命に存在するワイヤまたはファイバは一時信号媒体の例示である。

加えて、本明細書に記載（図に示すか否かを問わず）した如何なる行為も、方法の一部としてプロセッサー（例えば、１つ以上のプロセッサー６０２）によって実行することができる。つまり、行為Ａ，Ｂ，Ｃを本明細書に説明する場合には、Ａ、ＢおよびＣの行為を含む方法を実行することができる。更には、行為Ａ，Ｂ，Ｃを本明細書に説明する場合には、プロセッサーを用いることを含む方法を実行して、行為Ａ，Ｂ，Ｃを実行することができる。

一例としての環境では、コンピューター６００は、ネットワーク６０８を通じて１つ以上の他のデバイスに通信により接続することができる。コンピューター６１０は、構造上はコンピューター６００と同様とすることができ、コンピューター６００に接続することができるデバイスである。但し、他のタイプのデバイスもまた接続することができる。

本主題について、構造上の特徴および／または方法論的な行為に特有の言語で記載したものの、添付の特許請求の範囲に定められる主題が、先に説明した特定の特徴や行為に必ずしも限定されるものではないことが理解されるべきである。むしろ、先に説明した特定の特徴や行為は、特許請求の範囲を実施する例示の形態として開示するものである。

Claims (20)

1. 道順提供方法であって、
   全地球測位システム（ＧＰＳ）データを収集し、該ＧＰＳデータを地図に適用することによって、人々が移動した第１の複数の経路を取得するステップと、
   前記第１の複数の経路をデータベースに格納するステップと、
   処理装置を用いて、
   第１地点および第２地点を示す問い合わせを受け取るステップと、
   前記第１の複数の経路の組み合わせによる、前記第１地点から前記第２地点まで続く第２の複数の経路について、前記データベースを検索するステップと、
   前記第２の複数の経路を前記データベースから抽出するステップと、
   １つ以上の部分で重なり合う２つ以上の経路を結合することによって、前記第２の複数の経路に基づいて道順の組を生成するステップと、
   前記道順の組を人に提供するステップと
   を含む行為を実行するステップと
   を含む、方法。
2. 請求項１記載の方法であって、前記行為が、更に、
   前記第２の複数の経路を共に結合して、前記第１地点から前記第２地点への完全な経路を生成するステップを含み、
   前記結合は、共に結合されるために、経路が有することになる重なり合いの量を特定する規則によって支配される、方法。
3. 請求項２記載の方法において、前記規則は、共に結合されるために経路が共通して有することになる区間の数を特定し、各区間が方向変更を有さない経路の一部である、方法。
4. 請求項１記載の方法において、前記道順の組が、前記データベース内の経路の一部として採られた方向変更のみを含む、方法。
5. 請求項１記載の方法において、
   前記データベース内の各経路は、該経路を移動した日時、または該経路を移動した車両内の人数を考慮したコストに関連付けられており、前記行為が、更に、
   前記コストに基づくと共に、前記問い合わせを受け取った日時か前記道順を使用することになる車両内の人数のいずれかに基づいて、前記道順において使用するために、前記第２の複数の経路の内いずれかを選ぶステップを含む、方法。
6. 請求項１記載の方法において、前記検索するステップが、
   最初により長い経路を探すことにより、前記経路の長さに基づいて経路を検索し、次いでより短い経路を連続して探すことを含む、方法。
7. 請求項１記載の方法において、前記検索するステップが、
   前記データベースにおいて、第１経路を見つけ出すステップであって、前記第１経路の開始地点および前記第１地点の間の近接度に基づくと共に、前記第１経路の終了地点および前記第２地点の間の近接度に基づく、ステップと、
   前記データベースにおいて、前記第１地点から前記第１経路に沿う交差地点までの第２経路を見つけ出すステップと、
   前記データベースにおいて、第１経路に沿う交差地点から前記第２地点までの第３経路を見つけ出すステップと
   を含む、方法。
8. 道順を提供するために実行可能命令を格納する１つ以上のコンピュータ可読記憶媒体であって、コンピュータによって実行されるときに、前記実行可能命令が前記コンピュータに、
   第１地点および第２地点を示す問い合わせを受け取るステップと、
   複数の経路を抽出するステップと、
   ルールによって特定される重なり合いの程度を有する経路を接合することによって、前記複数の経路を結合して、完全な経路を生成するステップであって、前記ルールが、共に接合されるために経路が共通して有することになる区間の数を特定するステップと、
   前記完全な経路に基づいて道順の組を生成するステップと、
   前記道順の組を人に提供するステップと
   を含む行為を実行させる、コンピュータ可読記憶媒体。
9. 請求項８記載の１つ以上のコンピュータ可読記憶媒体において、
   前記経路が、移動した経路のＧＰＳ追跡記録から取得され、
   前記経路が、データベース内に格納され、
   前記抽出するステップが、前記データベースから前記経路を抽出する、
   コンピュータ可読記憶媒体。
10. 請求項８記載の１つ以上のコンピュータ可読記憶媒体において、前記完全な経路を生成するステップが、
    前記完全な経路において、移動した経路内に観察された方向変更のみを用いることを含む、コンピュータ可読記憶媒体。
11. 請求項８記載の１つ以上のコンピュータ可読記憶媒体において、
    前記複数の経路が、移動した実際の経路のＧＰＳ追跡記録から取得される経路であり、前記複数の経路の各々がコストに関連付けられ、
    前記結合するステップが前記コストを考慮し、前記コストは、各経路を移動した日時に基づく、コンピュータ可読記憶媒体。
12. 請求項８記載の１つ以上のコンピュータ可読記憶媒体において、
    前記複数の経路が、移動した実際の経路のＧＰＳ追跡記録から取得される経路であり、前記複数の経路の各々がコストに関連付けられ、
    前記結合するステップが前記コストを考慮し、前記コストは、各経路を移動したときの車両内の人数に基づく、コンピュータ可読記憶媒体。
13. 請求項８記載の１つ以上のコンピュータ可読記憶媒体において、
    前記抽出するステップが、最初により長い経路を探すことにより、前記経路の長さに基づいて経路を検索し、次いでより短い経路を連続して探すことを含む、コンピュータ可読記憶媒体。
14. 道順提供システムであって、
    デバイスから全地球測位システム（ＧＰＳ）追跡記録を受信するＧＰＳ追跡記録受信機と、
    経路データベースと、
    移動した経路を前記ＧＰＳ追跡記録に基づいて識別すると共に、該経路を前記経路データベースに格納する経路生成機と、
    メモリと、
    該メモリに格納する問い合わせ処理要素であって、第１地点および第２地点を含む経路の問い合わせを受け取ると共に、前記第１地点から前記第２地点まで集合的に続く複数の重なり合う経路を前記データベースから抽出する、問い合わせ処理要素と、
    前記重なり合う経路の内どれが重なり合いの程度を支配する規則を満たすかに基づいて、前記重なり合う経路を共に接合し、その結果、前記第１地点から前記第２地点への完全な経路を生成する経路合成機であって、
    前記規則は、接合されるために前記経路が共通して有することになる区間の数を特定し、前記問い合わせ処理要素が前記完全な経路に基づいて道順の組を人に提供する、経路合成機と
    を備えるシステム。
15. 前記経路合成機が、前記ＧＰＳ追跡記録から生成された経路で行われた方向変更のみを前記完全な経路に含める、請求項１４記載のシステム。
16. 請求項１４記載のシステムにおいて、前記経路合成機は、どの経路を前記完全な経路に使用すべきかを決定するときに、前記経路のそれぞれのコストを考慮し、該コストが、前記経路を移動した日時または前記経路を移動した車両内の人数に基づく、システム。
17. 請求項１４記載のシステムにおいて、前記問い合わせ処理要素が
    最初により長い経路を探すことにより、前記経路の長さに基づいて経路を検索し、次いでより短い経路を連続して探すことを含む、システム。
18. 請求項１４記載のシステムにおいて、
    前記問い合わせ処理要素が、前記データベースにおいて、第１経路の開始地点および前記第１地点の間の近接度に基づくと共に、前記第１経路の終了地点および前記第２地点の間の近接度に基づいて、当該第１経路を見つけ出し、
    前記問い合わせ処理要素が、前記データベースにおいて、前記第１地点から前記第１経路に沿う交差地点への第２経路を見つけ出し、
    前記問い合わせ処理要素が、前記データベースにおいて、前記第１経路に沿う交差地点から前記第２地点への第３経路を見つけ出す、システム。
19. 接合されるために前記経路が２以上の区間で重なり合うのを特定する、請求項８記載の１つ以上のコンピュータ可読記憶媒体。
20. 接合されるために前記経路が２以上の区間で重なり合うのを特定する、請求項１４記載のシステム。