オープン・ワールド・モデリング法およびクローズド・ワールド・モデリング法を用いて部分的軌跡から目的地を予測する方法
本特許請求対象は、ユーザの目的地および／または経路に対する確率分布を、トリップのコンテクストおよび部分的軌跡についての観察から推論することを容易にするシステムおよび／または方法を提供する。トリップの目的地は、受け取られた入力データに少なくとも部分的に基づく事前確率および尤度の少なくとも一方に基づく。目的地推定コンポーネントは、個人の目的地事前確率、時刻および曜日、グランド・カバー事前確率、候補場所に関連付けられた運転効率、およびトリップ時間尤度のうちの１つまたは複数を用いて、目的地を確率論的に予測することが可能である。さらに、以前に訪問されていない場所を訪問する尤度について母集団から収集されたデータと、そのような場所の空間的構成とを用いて、目的地および経路の予測を強化することが可能である。
【発明の詳細な説明】
【背景技術】
【０００１】
位置（location）は、個人のコンテクストの重要な要素であるとすることができる。個人の地理的位置、および個人が移動中であれば、その目的地の地理的位置には、膨大な量の情報を関連付けることが可能である。従来は、個人が、ある位置から別の位置へ移動する際には、地図をガイドとして用いるのが一般的であった。しかしながら、地図を利用するためには、現在位置から目的地まで通過（トラバース）すべき経路を、個人が識別しなければならない場合がある。さらに、そのような移動者は、一般に、現在位置または目的地に関連する情報を、口コミや個人的親交などを通じて知らされるだけである。例えば、移動者は、自分が一度も訪問したことがない場所では、ガソリン・スタンドやレストランなどの場所がわからない可能性があり、したがって、助けを求めたり、道沿いの看板に注意したりするしかない可能性がある。さらに、例えば、地図を利用する運転者は、交通渋滞に関しては、そのような情報を提供するラジオ局の放送を注意して聞くしか知る術がない可能性がある。
【０００２】
出発点から目的地までのマップを生成することをサポートするアプリケーションが、いくつも市販されている。例えば、そのようなアプリケーションは、出発地点から目的地までの経路を表示した地図だけでなく、運転方向ユーザに提供することが可能である。一例では、ユーザが出発点と終着点とを入力すると、アプリケーションは、対応する運転方向（directions）および／または（例えば、経路をハイライトした）マップ（map(s)）を生成することが可能である。これらのアプリケーションは、パーソナル・コンピュータ、ラップトップ・コンピュータ、ハンドヘルド、携帯電話などのような機器と接続して利用することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
近年、全地球測位システム（ＧＰＳ）装置の利用が広まりつつあり、これは、この装置に関連付けられた位置を識別することが可能である。例えば、ＧＰＳは、自動車の運転者に運転方向を示す自動車用ナビゲーション・システムに用いることが可能である。この例によれば、ナビゲーション・システムは、自動車の位置変化に応じて更新されるマップを表示することが可能である。さらに、ナビゲーション・システムは、自動車が移動している間、（例えば、表示、スピーカなどで）運転者に逐一指示を与えることが可能である。しかしながら、ＧＰＳ（ならびに他の従来技術）を用いた従来システムは、ユーザが目的地を直接入力しなければならないのが一般的である。例えば、一般的なＧＰＳ装置は、自動車の運転者が目的地の場所を指示しない限り、運転者に運転方向を示さない。さらに、ユーザは、移動のたびに目的地を入力するとは限らず、したがって、目的地に関連する警報および／または関連付けられた経路がユーザに提示されない場合がある。例えば、ユーザは、職場、自宅、学校などに頻繁に行く、行き先に向う場合には目的地を入力しないことがあり、その場合は、関連する警報がユーザに提示されないことになる。
【課題を解決するための手段】
【０００４】
以下では、簡単な概要が、本明細書に記載のいくつかの態様についての基本的理解が得られるように、提供される。この概要は、本特許請求対象の包括的な概説ではない。この概要は、本特許請求対象の重要な要素を示すものではなく、本特許請求対象の範囲を説明するものでもない。この概要の唯一の目的は、後で示される詳細な説明の前置きとして、いくつかの概念を簡単な形で示すことである。
【０００５】
本特許請求対象は、目的地（destination(s)）を確率論的に（probabilistically）予測することを容易にするシステムおよび／または方法に関する。ユーザ、ユーザの履歴（例えば、履歴データ）、別のユーザおよびその履歴、地理的領域の地勢図（例えば、グランド・カバー（ground cover）データ）、効率的な経路、トリップ時間分布、現在のトリップ（例えば、位置、位置変化、時刻など）、その他に関連する入力データを入手できる。これらの入力データは、任意のソース（例えば、位置特定コンポーネント、タイマ・コンポーネント、データ・ストア、インターネット、その他）から取得可能であることが予期される。予測は、１つ以上の事前確率（priors）および／または１つ以上の尤度（likelihoods）を利用して、実施することが可能である。例えば、この事前確率は、個人的な目的地（personal destinations）事前確率および／またはグランド・カバー事前確率とすることができる。さらに、この尤度は、効率的運転尤度（efficient driving likelihood）および／またはトリップ時間尤度とすることができる。１つ以上の事前確率、１つ以上の尤度、または事前確率と尤度の組合せを利用して、予測目的地（predicted destination(s)）を生成することが可能であることを理解されたい。
【０００６】
本特許請求対象の各種態様によれば、目的地推定コンポーネントが、事前確率（prior(s)）および／または尤度（likelihood(s)）に基づいて、トリップの目的地を確率論的（probabilistically）に予測することが可能である。目的地推定コンポーネントを用いて、事前確率（prior(s)）および／または尤度（likelihood(s)）を選択および／または結合することにより、予測目的地を生成することが可能である。一例によれば、ベイズ規則を利用することにより、事前確率（prior(s)）および／または尤度（likelihood(s)）の任意の組合せを目的地推定コンポーネントで用いることが可能である。
【０００７】
本特許請求対象の１つまたは複数の態様によれば、目的地推定コンポーネントは、個人的な目的地事前確率、グランド・カバー事前確率、効率的運転尤度、および／またはトリップ時間尤度を用いることが可能である。個人的な目的地事前確率は、ユーザの過去の複数の目的地からなる集合に基づくことが可能であり、したがって、履歴データを評価して個人的な目的地事前確率を生成することが可能である。例えば、個人的な目的地事前確率を取得することに関連して、オープン・ワールド・モデリング（open world modeling）および／またはクローズド・ワールド・モデリング（closed world modeling）を用いることが可能である。オープン・ワールド解析および／またはクローズド・ワールド解析を、位置予測に組み込むことが可能であり、したがって、この解析は、運転者が以前に観察されていない場所を訪問する尤度（観察範囲（observation horizon）の関数として）、新しい複数の場所、複数の所定の事前確率位置についての空間的関係、の両方についての予測を含むことが可能である。複数の人物を一定期間観察することによって、オープン・ワールド推論用のパラメータを得ることが可能であり、それを個人にマッピングすることが可能である。さらに、オープン・ワールド・モデリングにおいて、デモグラフィック情報（demographic information：人口学的情報）を考慮に入れることが可能である。さらに、グランド・カバー事前確率は、特定セルが目的地である確率を特定セル内のグランド・カバーに基づいて与えるグランド・カバー・データに基づくことが可能である。さらに、効率的運転尤度は、移動者がトリップの進行とともに到着までの時間を減らし続けると仮定できる場合には、候補目的地に到着するまでの時間の変化に基づくことが可能である。例えば、各候補目的地に関連付けられた、算出された運転効率を、最終的な位置特定の証拠として利用することが可能である。トリップ時間尤度は、トリップ時間分布および／または経過トリップ時間に基づくことが可能である。さらに別の例によれば、時刻、曜日（例えば、週末か平日か）、休日ステータス、季節、月などのようなコンテクスチュアルな特徴を、解析の一部として利用することが可能である。
【０００８】
本特許請求対象の各種態様によれば、目的地、目的地までの途上で人々が選択しそうな経路、などを識別するために、推論（reasoning）を適用することが可能である。さらに、アプリケーションが、識別された目的地および／または経路を利用して、関連情報をユーザに提示することが可能である。一例によれば、アプリケーションは、交通（traffic）、工事（construction）、前方の安全性（safety issues ahead）などについて警告メッセージを示したり、掲示されている広告を案内したり、指示（directions）、経路の助言（routing advice）、最新情報などを与えたりすることが可能である。例えば、ユーザに提示される情報は、予測目的地（predicted destination(s)）に関連するものであることが可能である。さらに、または代替として、その情報が、経路に関連付けられた場所（例えば、その経路に沿って通過する場所）に関連するものになるように、予測目的地（predicted destination(s)）への経路を評価することが可能である。このような関連情報として、例えば、交通に関連する警告メッセージ、ナビゲーション支援（navigation assistance）、イベント、目標となる広告、施設（establishments）、目立つ建造物（landmarks）などがある。関連情報は、任意の様式（例えば、音声信号、視覚情報など）で配信可能であることを理解されたい。さらに、示される関連情報は、ユーザの好みに基づいてカスタマイズされることが可能である。
【０００９】
以下の記述および添付図面は、本特許請求対象の特定の例示的態様を詳細に説明するものである。しかしながら、それらの態様は、本特許請求対象の原理を用いることが可能な様々な様式のうちのいくつかを示すものに過ぎず、本特許請求対象は、そのような態様およびそれらの等価物をすべて包含するものとする。以下の詳細な記述を添付図面と併せて考察することにより、他の利点および新規な特徴が明らかになるであろう。
【発明を実施するための最良の形態】
【００１０】
本特許請求対象について、図面を参照しながら説明する。図面全体を通して、類似の参照符号は、類似の要素を表している。以下の記述では、説明のために、多数の具体的詳細を示して、本発明が十分理解されるようにする。しかしながら、これらの具体的詳細がなくても本特許請求対象が実施可能であることは自明であろう。他の例では、本発明の説明を容易にするために、周知の構造および装置をブロック図の形式で示している。
【００１１】
本明細書で用いられる「コンポーネント」、「システム」などの用語は、コンピュータ関連のエンティティ（ハードウェア、（例えば、実行中の）ソフトウェア、および／またはファームウェア）を意味するものとする。例えば、コンポーネントは、プロセッサで実行中のプロセス、プロセッサ、オブジェクト、実行可能ファイル、プログラム、および／またはコンピュータであってよい。例えば、サーバで実行中のアプリケーションもサーバもコンポーネントであってよい。１つまたは複数のコンポーネントがプロセス内に常駐することが可能であり、コンポーネントは、１台のコンピュータに集中していても、２台以上のコンピュータに分散していても、その両方であってもよい。
【００１２】
さらに、本特許請求対象は、標準的なプログラミング手法および／または設計手法を用いて、本開示対象を実施するようにコンピュータを制御するソフトウェア、ファームウェア、ハードウェア、またはこれらの任意の組合せを実現する方法、装置、または製品として実装されることが可能である。本明細書で用いられる「製品（article of manufacture）」という用語は、任意のコンピュータ読み取り可能な装置、搬送波、または媒体からのアクセスが可能なコンピュータ・プログラムを包含するものとする。例えば、コンピュータ可読媒体としては、磁気記憶装置（例えば、ハードディスク、フロッピー（登録商標）ディスク、磁気ストリップなど）、光ディスク（例えば、コンパクト・ディスク（ＣＤ）、デジタル多用途ディスク（ＤＶＤ）など）、スマート・カード、フラッシュ・メモリ装置（例えば、カード、スティック、キー・ドライブなど）などがあるが、これらに限定されない。さらに、電子メールの送受信や、インターネットまたはローカル・エリア・ネットワーク（ＬＡＮ）のようなネットワークへのアクセスに用いられるような搬送波を用いて、コンピュータ可読な電子データを搬送することが可能であることを理解されたい。もちろん、当業者であれば理解されるように、本特許請求対象の範囲または趣旨から逸脱することなく、その構成に様々な修正を施すことが可能である。さらに、本明細書で用いられる「例示的」という用語は、例、事例、または実例として機能することを意味する。「例示的」として本明細書に記載される態様または設計は、いずれも、他の態様または設計より好ましい（あるいは、有利である）として解釈されるべきものでは必ずしもない。
【００１３】
以下、各図面を見ていく。図１は、ユーザの目的地（destination(s)）を特定することを容易にするシステム１００を示す。システム１００は、ユーザ、ユーザの履歴、地理的領域の地勢図、トリップ、効率的な経路などに関連しうる入力データを受け取るインターフェース・コンポーネント１０２を含む。インターフェース・コンポーネント１０２は、任意のソースから入力データを受け取ることが可能である。例えば、インターフェース・コンポーネント１０２は、ユーザの位置および／または位置変化を特定することを可能にする任意のコンポーネント（図示せず）から入力データを取得することが可能であり、そのようなコンポーネントとして、例えば、全地球測位システム（ＧＰＳ）、衛星ナビゲーション・システム、ＧＬＯＮＡＳＳ、Ｇａｌｉｌｅｏ、Ｅｕｒｏｐｅａｎ Ｇｅｏｓｔａｔｉｏｎａｒｙ Ｎａｖｉｇａｔｉｏｎ Ｏｖｅｒｌａｙ Ｓｙｓｔｅｍ（ＥＧＮＯＳ）、Ｂｅｉｄｏｕ、Ｄｅｃｃａ Ｎａｖｉｇａｔｏｒ Ｓｙｓｔｅｍ、通信塔間の三角測量など、をサポートするコンポーネントが挙げられる。別の例として、インターフェース・コンポーネント１０２は、ユーザが以前に行ったことがある目的地に関連付けられた入力データを（例えば、データ・ストア、ユーザ入力などから）受け取ることが可能である。さらに、あるいは、代替として、インターフェース・コンポーネント１０２は、ユーザが（例えば、現在のトリップの期間に）現時点において移動中の時間量を決定することが可能なタイマ・コンポーネント（図示せず）から入力データを取得することが可能である。さらに、インターフェース・コンポーネント１０２は、グランド・カバー・データを受け取ることが可能である。例えば、そのようなデータは、データ・ストア（図示せず）から取得可能である。インターフェース・コンポーネント１０２は、入力データをいつでも受け取ることが可能であることを理解されたい。例えば、インターフェース・コンポーネント１０２は、ユーザのトリップの進行中でも（例えば、リアルタイムで）、ユーザがトリップを開始する前でも、それ以外のときでも、入力データを取得することが可能である。
【００１４】
入力データは、インターフェース・コンポーネント１０２から目的地推定コンポーネント１０４にわたされることが可能であり、目的地推定コンポーネント１０４は、入力データを評価して目的地（destination(s)）を確率論的に（probabilistically）予測することが可能である。目的地推定コンポーネント１０４は、入力データに少なくとも部分的に基づく事前確率（prior(s)）および／または尤度（likelihood(s)）を利用して、予測目的地（predicted destination(s)）を生成することが可能である。例えば、目的地推定コンポーネント１０４は、個人的な目的地事前確率、グランド・カバー事前確率、効率的運転尤度、および／またはトリップ時間尤度を用いることが可能である。予測目的地（predicted destination(s)）を生成するために、任意の数の事前確率および／または任意の数の尤度を組み合わせて用いることが可能であることを理解されたい。一例では、目的地推定コンポーネント１０４は、トリップに関連付けられた目的地を確率論的に（probabilistically）予測する場合には、グランド・カバー事前確率のみを利用することが可能である。別の例によれば、目的地推定コンポーネント１０４は、目的地（destination(s)）を確率論的に（probabilistically）予測する場合には、個人的な目的地事前確率、グランド・カバー事前確率、効率的運転尤度、およびトリップ時間尤度を用いることが可能である。本特許請求対象は、これらの例に限定されないことを理解されたい。
【００１５】
目的地推定コンポーネント１０４は、様々なソースからのデータを評価して、移動中の個人が目指している場所を予測することが可能である。一例によれば、目的地推定コンポーネント１０４は、トリップの開始前（例えば、ユーザが自動車に乗り込んだときなど）、またはトリップ中の任意の時点で、目的地を確率論的に（probabilistically）予測することが可能である。したがって、入力データは、現在のトリップに関連するデータ（例えば、現在位置、位置変化、現在のトリップに関連付けられた任意の数の場所、現在のトリップに関連付けられた時間量など）を含むことが可能である。さらに、一例によれば、そのようなトリップが進行するにつれて、目的地推定コンポーネント１０４は、トリップからの入力データを利用して、目的地（destination(s)）の予測（prediction(s)）を動的に更新することが可能である。代替として、目的地推定コンポーネント１０４は、ユーザの現在のトリップに関連付けられた情報が含まれない入力データを解析し、それに従って、共通点のない色々な情報（例えば、グランド・カバー・データ、履歴データなど）に基づく予測を生成することが可能である。
【００１６】
図示されたように、目的地推定コンポーネント１０４は、予測目的地（predicted destination(s)）を出力することが可能である。さらに、その予測目的地（predicted destination(s)）は、目的地推定コンポーネント１０４からインターフェース・コンポーネント１０２に伝えられることが可能であり、インターフェース・コンポーネント１０２は、その目的地（destination(s)）の予測（prediction(s)）を出力することが可能であることが企図されている。予測目的地（predicted destination(s)）は、ユーザに提示されることが可能であることを理解されたい。一例によれば、予測目的地（predicted destination(s)）を表示した地図をユーザに提示することが可能である。さらに、その地図は、現在のトリップにおいて、それまでにトラバースした経路、および／または、予測目的地（predicted destination(s)）に到着するための、トリップの残りに関連付けられた方向などの情報を含むことが可能である。また、そのような地図は、目標とされた広告の情報を提示することが可能であり、そのような広告の内容は、（例えば、ユーザが、ガソリンＢよりガソリンＡを好み、ファスト・フード・レストランＤよりファスト・フード・レストランＣを好む、というような）ユーザの好みを考慮して選択的に出力されることが可能である。予測目的地（ predicted destination(s)）は、任意のタイプの可聴信号および／または可視信号を利用してユーザに提示されることが可能であることが企図されている。さらに、ユーザは、予測目的地（predicted destination(s)）に関連付けられたフィードバックを返すことが可能である（例えば、一群の予測目的地から１つの目的地を選択したり、予測目的地が正しくないことを伝えたりすることが可能である）。別の例によれば、目的地（destination(s)）の予測（prediction(s)）は、その予測（prediction(s)）を利用して、（例えば、警告として）ユーザに提示されることが可能な関連情報（例えば、近くの関心対象ポイント、場所ごとのサービス、目的地に関連付けられた気象関連情報、目的地（destination(s)）に関連付けられた交通関連情報、目標とされた広告、イベントに関連付けられた情報など）を生成することが可能な、まったく別のコンポーネント（図示せず）に送られることが可能である。
【００１７】
目的地推定コンポーネント１０４は、グランド・カバー・データ、移動者（例えば、運転者）は効率的な経路を利用するのが普通であるという事実、および／またはトリップ時間（trip times）についての測定された分布に少なくとも部分的に基づいて、可能性の高い目的地を評価することが可能である。さらに、目的地推定コンポーネント１０４は、これらの手がかり（例えば、入力データ）をベイズ規則と組み合わせて、目的地（destination(s)）を確率論的に（probabilistically）予測することが可能である。さらに、目的地推定コンポーネント１０４は、ユーザおよび／または別のユーザの以前の目的地（destination(s)）（例えば、履歴データ）を考慮することも可能である。しかしながら、本特許請求対象は、前述の例に限定されない。目的地推定コンポーネント１０４はさらに、時間とともに、ユーザに関連付けられたトレーニング・データが取得されるにつれて、精度を向上させることが可能である。別の例によれば、目的地推定コンポーネント１０４は、どんな場所でも、可能な目的地にすることが可能である。別の例によれば、目的地推定コンポーネント１０４は、可能な目的地を道路網上に限定することが可能である。これにより、多くの実際の目的地が道路上または道路のそばになるため、精度を向上させることが可能である。しかしながら、本特許請求対象は、そのようには限定されない。また、目的地推定コンポーネント１０４は、例えば、時刻、曜日（例えば、週末か平日か）、休日ステータス、季節、月などのようなコンテクスチュアルな情報を考慮することも可能である。
【００１８】
インターフェース・コンポーネント１０２は、目的地推定コンポーネント１０４とは別々であるように描かれているが、目的地推定コンポーネント１０４がインターフェース・コンポーネント１０２またはその一部を含むことも企図されている。さらに、インターフェース・コンポーネント１０２は、目的地推定コンポーネント１０４との対話を可能にするために、様々なアダプタ、コネクタ、チャネル、通信パスなどを設けることが可能である。
【００１９】
個人（例えば、運転者）の目的地についての知識は、個人の移動中（例えば、トリップ中）に有用な情報を提供するための重要なパラメータとなる可能性がある。例えば、車載ナビゲーション・システムは、運転者が移動中に遭遇することが予想される交通渋滞、ガソリン・スタンド、レストラン、その他の関心対象ポイントを、自動的に表示することが可能である。さらに、車載ナビゲーション・システムは、運転者が向かっているだいたいの地域を正確に推定できる場合には、表示する情報をインテリジェントにフィルタリングして、認識負荷（cognitive load）を軽減することが可能である。さらに、目的地について運転者に直接尋ねることが可能な場合もあるが、トリップの開始時に必ずこの情報を出すよう運転者に要求することを少なくするのが有利である。システム１００は、例えば、「運転者は、目的地までの、適度に効率的な経路を選択するものである」という直観的真実に基づいて運転の目的地を予測するアルゴリズムを利用することにより、目的地（destinations）の自動予測を可能にすることが可能である。一態様によれば、個人の移動行動（travel behavior）をモデリングすることなく（例えば、運転者の日常的な目的地（職場、自宅、学校など）について事前に知っていることを仮定することなく）、予測を生成することが可能である。しかしながら、本特許請求対象は、そのようには限定されない。この例によれば、システム１００は、新車、レンタカー、または運転者が訪問したことのない都市において利用することが可能である。
【００２０】
図２は、目的地（destination(s)）を確率論的に（probabilistically）予測することに関連して利用可能な確率論的（probabilistic）グリッドおよび／または複数の位置間の経路（route(s)）を生成するシステム２００を示す。システム２００は、入力データを取得して目的地推定コンポーネント１０４にわたすインターフェース・コンポーネント１０２を含むことが可能である。目的地推定コンポーネント１０４は、入力データに関連付けられた目的地を確率論的に（probabilistically）予測することが可能である。目的地推定コンポーネント１０４は、グリッド・コンポーネント２０２によって生成された確率論的（probabilistic）グリッド、および／または経路計画コンポーネント２０４によって生成された複数の位置間の任意の数の経路（およびこれらに関連付けられた任意のデータ）を利用して、可能性の高い目的地（destination(s)）を識別することが可能である。
【００２１】
一例によれば、グリッド・コンポーネント２０２は、地図に関連付けられることが可能な確率論的（probabilistic）グリッドを生成することが可能である。例えば、四辺形の二次元グリッド（例えば、セル）を、その四辺形（例えば、セル）が任意の実際の物理的地理的領域に関連付けられるように（例えば、１キロメートルがグリッドの各四辺形の各辺に対応するように）、地図に関連付けることが可能である。さらに、グリッド・コンポーネント２０２によって生成されたグリッドが、四辺形のセルではない（または、四辺形のセルに加えて）１つまたは複数の任意の形状（例えば、Ｍ個の辺を有する多角形（Ｍは３以上の正の整数）、円など）のセルを含むことが可能であることが企図されている。これらのセルは、離散的な位置を表すことが可能であり、任意のタイリング、サイズ、および番号に関連付けられることが可能である。これらのセルは、それぞれに一意のインデックス（例えば、ｉ＝１，２，３，．．．，Ｎ。Ｎは任意の正の整数）が割り当てられることが可能であり、目的地推定コンポーネント１０４は、ユーザがその中でトリップを終えそうな１つまたは複数のセル（例えば、目的地）を識別することが可能である。
【００２２】
目的地推定コンポーネント１０４は、各セルが目的地になる確率を算出することが可能である。例えば、Ｐ（Ｄ＝ｉ｜Ｘ＝ｘ）を評価することにより、確率を求めることが可能である。ここで、Ｄは、目的地を表すランダム変数であり、Ｘは、そこまでのトリップから観察される特徴のベクトルを表すランダム変数である。さらに、尤度および／または事前確率を利用することが可能であり、ベイズ規則を適用して、以下を与えることが可能である。
【００２３】
【数１】
【００２４】
したがって、Ｎを、グリッド内のセルの数とすることが可能であり、Ｐ（Ｄ＝ｉ）を、目的地がセルｉである事前確率とすることが可能である。この事前確率は、例えば、個人の目的地事前確率および／またはグランド・カバー事前確率を用いて算出することが可能である。さらに、Ｐ（Ｘ＝ｘ｜Ｄ＝ｉ）を、観察された測定値Ｘに基づく、セルｉが目的地である尤度とすることが可能であり、Ｘは、様々なソースから算出された地図情報であることが可能である。例えば、尤度は、効率的運転尤度および／またはトリップ時間尤度とすることができる。分母は、すべてのセルの確率を合計すると１になるように算出されることが可能な正規化係数とすることができる。
【００２５】
経路計画コンポーネント２０４は、複数のペアのセル間の経路、および／またはグリッド・コンポーネント２０２によって生成されたグリッド内の各ペアのセル間の運転時間の推定を出力することが可能である。経路計画コンポーネント２０４は、セルの各ペアのセル間のユークリッド距離および概算速度を利用して運転時間を見積もることが可能である。さらに、または代替として、経路計画コンポーネント２０４は、ペアのセルの中心点（緯度、経度）間の運転経路を計画して、より高精度の運転時間推定値を与えることが可能である。したがって、経路計画コンポーネント２０４は、セル間の道路網および速度制限に少なくとも部分的に基づいて出力を与えることが可能である。
【００２６】
図３は、グランド・カバー・データに少なくとも部分的に基づいて予測目的地（predicted destination(s)）を与えるシステム３００を示す。システム３００は、グランド・カバー・データを含むことが可能な入力データを受け取るインターフェース・コンポーネント１０２を備える。システム３００はさらに、グランド・カバー・コンポーネント３０２によって生成されたグランド・カバー事前確率に少なくとも部分的に基づいて予測目的地（predicted destination(s)）を生成することが可能な目的地推定コンポーネント１０４を含む。
【００２７】
このグランド・カバー・コンポーネント３０２は、あるセルが目的地である確率を、その特定のセルに関連付けられたグランド・カバー・データに基づいて評価することを容易にすることが可能である。グランド・カバー事前確率を、位置に関連するトポロジ（地勢学）に関連付けることが可能である。例えば、湖や海の真ん中は、運転者にとってよくある目的地とは言えず、商業地域は、永続的に氷と雪で覆われた場所よりも魅力的な目的地である。インターフェース・コンポーネント１０２は、例えば、グランド・カバー・コンポーネント３０２がアメリカ地質調査所（United States Geological Survey）（ＵＳＧＳ）グランド・カバー地図に基づいてグリッド内のセルを特徴づけることを可能にすることが可能な、グランド・カバー地図を取得することを容易にすることが可能である。しかしながら、本特許請求対象は、そのようには限定されず、任意のグランド・カバー・データを利用してセルを特徴づけることが可能であることが企図されている。例えば、ＵＳＧＳグランド・カバー地図は、米国の３０ｍ×３０ｍの各正方形を、２１の異なるタイプのグランド・カバー（例えば、挺水草本湿地帯（emergent herbaceous wetlands）、樹木湿地（woody wetlands）、果樹園、永続的な氷（perennial ice）、小穀物（small grains）、条植え作物（row crops）、岩肌（bare rock）、休閑地（fallow）、市街地（urban）、高密集度住宅地（high intensity residential）、中間形態（transitional）、採石場（quarry）、牧草地（pasture）、水域（water）、草原（grasslands）、混交林（mixed forest）、低木地（shrub land）、落葉樹林（deciduous forest）、常緑樹林（evergreen forest）、低密集度住宅地（low intensity residential）、商業地（commercial）など）の一つに分類することが可能である。グランド・カバー・コンポーネント３０２は、例えば、データセット内の各トリップ目的地の緯度および／または経度を評価して、複数のグランド・カバー・タイプ（例えば、２１のグランド・カバー・タイプ）に対する正規化ヒストグラムを作成することが可能である。水域は、一般的な目的地とは言えないが、他のいくつかのカテゴリ（例えば、挺水草本湿地、樹木湿地など）よりは一般的であり、商業地域は、氷と雪に覆われた地域よりは魅力的であろう。より一般的な目的地は、「商業地」と「低密集度住宅地」であろう。これらについて、ＵＳＧＳは、次のように記載している。
【００２８】
商業／工業／輸送（Commercial/Industrial/Transportation）−「インフラストラクチャ（例えば、道路、鉄道など）と、高密集度住宅地には分類されない、高度に発展したすべての地域とを含む。」
【００２９】
低密集度住宅地−「建造物と植物とが混在した地域を含む。建造物は、グランド・カバーの３０〜８０パーセントを占める。植物は、グランド・カバーの２０〜７０パーセントを占める。これらの地域は、一戸建て住宅（single-family housing units）を最も一般的に含む。人口密度は、高密集度住宅地より低い。」
【００３０】
「水域」カテゴリは、非ゼロの尤度に関連付けられることが可能である。これは、３０ｍ×３０ｍのＵＳＧＳ正方形の最大２５％が陸地であっても水域と分類される場合があり、正方形がどのように配置されるかによって、海辺やウォーターフロントの土地が含まれる可能性があるためである。様々な領域を、グランド・カバーの様々な混在に関連付けることが可能であること、ならびに、別の領域の居住者が、グランド・カバーのタイプに関連して、様々な行動をとる可能性があることが想定されている。
【００３１】
一例によれば、グランド・カバー・コンポーネント３０２は、目的地セルがグランド・カバー・タイプｊ（ｊ＝１，２，３，．．．，２１）によって完全に覆われている場合には、目的地セルの確率を、Ｐ（Ｄ＝ｉ｜Ｇ＝ｊ）を評価することによって決定することが可能である。一例によれば、グランド・カバー・コンポーネント３０２が１ｋｍ×１ｋｍセルの確率諭的（probabilistic）グリッドを利用する場合、各セルは、約１１１１個の３０ｍ×３０ｍグランド・カバー・ラベルを含むことが可能である（例えば、多くの場合、セルは、同じタイプのグランド・カバーで完全には覆われない）。グランド・カバー・コンポーネント３０２は、各セルについて、Ｐｉ（Ｇ＝ｊ）で表される、グランド・カバー・タイプの分布を算出することが可能である。一例として、グランド・カバー・コンポーネント３０２は、次のようにセル内のグランド・カバー・タイプを敢えて過小評価することにより、各セルの事前確率を算出することが可能である。
【００３２】
【数２】
【００３３】
ＰＧ（Ｄ＝ｉ）は、グランド・カバーに基づいて、目的地セルの事前確率に関連付けられることが可能である。したがって、グランド・カバー・コンポーネント３０２は、例えば、水域および田園地帯を、より確率が低い目的地である可能性があると判定することができる。グランド・カバー・コンポーネント３０２によって生成されたグランド・カバー事前確率（および後述されるようなユーザ履歴コンポーネントを利用して取得された個人の目的地事前確率）は、これらが、通常、ユーザの現在の運転についての測定された特性（measured features）に基づかないことから、事前確率分布を与えることができる。
【００３４】
図４は、履歴データに基づいて目的地（destination(s)）を予測するシステム４００を示す。システム４００は、入力データを受け取るインターフェース・コンポーネント１０２を含む。入力データは、例えば、履歴データを含むことが可能である。履歴データは、特定のユーザ、別のユーザ、および／または複数のユーザの集合に関連するものであることが可能である。例えば、履歴データは、ユーザの以前の目的地の集合に関連するものであることが可能である。一例として、インターフェース・コンポーネント１０２は、履歴データをデータストア（図示せず）から取得することが可能である。さらに、インターフェース・コンポーネント１０２は、履歴データを含む入力データを目的地推定コンポーネント１０４にわたすことが可能であり、目的地推定コンポーネント１０４は、そのようなデータに基づいて目的地（destination(s)）を確率論的に（probabilistically）予測する。
【００３５】
目的地推定コンポーネント１０４はさらに、履歴データを評価して個人の目的地事前確率を生成するユーザ履歴コンポーネント４０２を備えることが可能である。したがって、目的地推定コンポーネント１０４は、個人の目的地事前確率を用いて、目的地の予測を容易にすることが可能である。目的地推定コンポーネント１０４は、ユーザ履歴コンポーネント４０２を単独で用いるか、かつ／または、別の事前確率および／または１つまたは複数の尤度との組合せで用いることによって得られた個人の目的地事前確率を利用することが可能であることを理解されたい。
【００３６】
ユーザ履歴コンポーネント４０２は、運転者は、以前に行ったことがある場所に行くことが多く、そのような場所には、より高い目的地確率を与えるべきである、という直観的真実に基づくことが可能である。例えば、ユーザ履歴コンポーネント４０２は、ＧＰＳ信号が失われたことを利用して、ユーザが建物の中に入ったことを示すことが可能である。そのユーザが同じ建物に何度も入る場合、その場所は、将来の予測の候補目的地としてマーキングされることが可能である。さらに、ユーザがしきい値（例えば、１０分）を超える時間量をそこで費やした、ＧＰＳで測定された、場所をクラスタ化して、可能性の高い目的地を推論することが可能である。さらに、長く滞在した場所をクラスタ化して、目的地を推論することも可能である。また、潜在的な目的地は、目的地のサイズおよび滞在時間の規模の変化の理由を明示的に説明するとともに、推論されることもできる。
【００３７】
別の例によれば、ユーザ履歴コンポーネント４０２は、個人の目的地（personal destinations）を、セグメント化された複数のトリップの複数の終点を含むグリッド・セルとしてモデリングすることが可能である。したがって、候補目的地の空間的規模を、セルのサイズと同じにすることが可能であり、目的（destination）と見なされるべき滞在時間を、トリップ・セグメンテーション・パラメータによって決定することが可能である（例えば、５分）。
【００３８】
ユーザ履歴コンポーネント４０２は、個人の目的地データ（destinations data）に基づく、まったく別の仮定を利用することが可能である。それらは、クローズド・ワールド仮定とオープン・ワールド仮定である。ユーザ履歴コンポーネント４０２は、オープン・ワールド解析および／またはクローズド・ワールド解析を利用することが可能であり、それらの両方を位置予測に組み込むことが可能である。したがって、ユーザ履歴コンポーネント４０２によって実施される解析は、運転者が、以前に観察されていない場所を訪問する尤度（観察範囲の関数として）、および事前確率場所に対する、新しい複数の場所の空間的関係の両方についての予測を含むことが可能である。さらに、複数の人物を一定期間観察することによって、オープン・ワールド推論用のパラメータを得ることが可能であり、それを個人にマッピングすることが可能である。さらに、オープン・ワールド・モデリングにおいて、デモグラフィック情報（例えば、年齢、性別、職種、宗教、政治的所属など）を考慮に入れることが可能である。一例として、クローズド・ワールド仮定を、「運転者は、過去に訪問したことが観察されている目的地だけを訪問する」と仮定することに関連付けることが可能である。これをクローズド・ワールド仮定と呼ぶことが可能であり、対応する解析をクローズド・ワールド解析と呼ぶことが可能である。ユーザ履歴コンポーネント４０２は、クローズド・ワールド仮定を行うことにより、運転者のトリップが終了した地点を調査して、Ｎ個のセルに対するヒストグラムを作成することが可能である。正規化により、確率関数Ｐｃｌｏｓｅｄ（Ｄ＝ｉ）、（ｉ＝１，２，３，．．．，Ｎ）が与えられる。ここで、添え字のｃｌｏｓｅｄは、この確率が個人の目的地に基づくことを示している。あるセルをユーザが訪問したことが観察されていない場合は、そのセルの個人の目的地確率をゼロにすることが可能である。これは、各セルの事後目的地確率を算出するために、ベイズ計算において、この確率に、Ｎ個のセルに対する他の確率が乗じられるためである。セルがゼロ事前確率を有する場合、そのセルは、可能性のある目的地として残らない可能性がある。
【００３９】
クローズド・ワールド仮定は、「人々が、過去に訪問したことが観察されていない目的地を訪問する可能性が実際にはある」という点で、先入的知識がない（naive）。このケースは、一般であるが、新しい目的地についてのそのような観察は、特に、運転者の観察の早い段階において顕著である可能性がある。上記の「新しい」場所は、運転者にとってまったく新しい目的地だけでなく、運転者が以前に訪問していても、調査（例えば、ユーザの観察／追跡）の過程の間に訪問したことが観察されていない場所も含む。したがって、運転者の目的地の確率を推論する方法として、より精度が高くなる可能性があるのは、まだ見たことがない目的地を見る尤度を考慮すること、したがって、「オープン・ワールド」モデルを活用することであると考えられる。この作用をモデリングすることにより、調査（例えば、運転者の観察）の早い時点で取得されるクローズド・ワールド確率関数を、調査終了時以降に観察されることが可能な定常状態確率の概算値に変換することが可能である。次に、このオープン・ワールド・モデルがＰｃｌｏｓｅｄ（Ｄ＝ｉ）に取って代わり、対象が訪問しそうな場所の、より高精度のモデルを生成することが可能である。
【００４０】
図５は、オープン・ワールド・モデリングを利用して目的地を予測するシステム５００を示す。システム５００は、インターフェース・コンポーネント１０２および目的地推定コンポーネント１０４を含む。さらに、目的地推定コンポーネント１０４は、取得された入力データに含まれる履歴データを評価するユーザ履歴コンポーネント４０２を含む。ユーザ履歴コンポーネント４０２はさらに、まだ観察されていない新しい目的地（例えば、履歴データの一部として含まれていない目的地）の尤度および位置を明示的に考慮するオープン・ワールド・モデリング・コンポーネント５０２を含む。
【００４１】
オープン・ワールド・モデリング・コンポーネント５０２は、未訪問の場所を様々な様式でモデリングすることが可能である。例えば、目的地がクラスタ化しそうだという観察に基づいて、オープン・ワールド・モデリング・コンポーネント５０２を用いて未訪問の場所をモデリングすることが可能である。一例として、運転者は、時間を節約するために、互いに近くにある複数の場所に行く傾向があるかもしれない。あるいは、運転者は、自分になじみのある地域ばかりに行く傾向があるかもしれない。例えば、職場の近くにあるガソリン・スタンドや食料雑貨店を選択するかもしれない。オープン・ワールド・モデリング・コンポーネント５０２は、この作用を、以前に訪問された地点からの距離に対する離散化確率分布（discretized probability distribution）としてモデリングすることが可能である。この分布は、図６に示されるような、段を付けたウェディング・ケーキのような全体形状を有することが可能である（図６は、以前に訪問された場所の周囲の４つのしきい値半径に対する、離散化された４層確率分布６００の一例を示す）。各層は、以前に訪問された目的地の周辺の新しい目的地の確率を与えることが可能である。ウェディング・ケーキの各層は、中心からのいくつかの半径における一定確率の同心環とすることが可能であり、定常状態における目的地の最終的なクラスタ化をモデリングすることを意図したものである。
【００４２】
別の例によれば、図５において、オープン・ワールド・モデリング・コンポーネント５０２は、各対象のＧＰＳ調査の、まったく異なる日々におけるグリッド上の目的地の正規化ヒストグラムを調べることにより、クラスタ化傾向を測定することが可能である。ある日の各目的地について、その目的地のまわりの１０層ウェディング・ケーキの各環の最終的な定常状態において、まだ訪問されていない目的地が現れる確率を算出することが可能である。各環は、幅１キロメートル、中心半径ｒ＝｛１，２，．．，１０｝キロメートルの環であることが可能であり、定常状態は、全調査期間にわたって訪問されたすべての目的地から取得されることが可能である。調査の初日では、訪問済みの目的地の近くで未訪問の定常状態の目的地が見つかる確率は、比較的高い可能性がある。日が経つにつれ、各対象が徐々に、それぞれの日常的な目的地のほとんどを訪問するため、上記確率は下がる。一日ごとに、中心近くの層が、外側エッジ近くの層より高くなる。操作的には、所与の日からの所与のクローズド・ワールド確率Ｐｃｌｏｓｅｄ（Ｄ＝ｉ）に対し、しかるべき日の確率値を有するウェディング・ケーキに置き換えられた、各非ゼロＰｃｌｏｓｅｄ（Ｄ＝ｉ）の未訪問の近隣地の別の確率を算出することが可能である。これにより、定常状態の予想される広がりを（spread）シミュレーションが可能である。１に正規化された後のウェディング・ケーキを、Ｗ（Ｄ＝ｉ）とする。これは、各対象ごとに別々に行われることが可能である。
【００４３】
定常状態の目的地はクラスタ化する傾向があるが、孤立した目的地もありうる。この作用は、定常状態の目的地が、定常状態の前に訪問された目的地のまわりの１０層ウェディング・ケーキによって覆われない確率を算出することによって特徴づけられることが可能である。この確率を、βとする。新しい、孤立した目的地の確率は、時間とともに低下する可能性がある。この背景確率（background probability）をモデリングする１つの方法は、全グリッド・セルにわたる均一分布を用いる方法である。しかしながら、これは、湖の真ん中のような誰も行かない場所に確率を与える可能性がある。オープン・ワールド・モデリング・コンポーネント５０２は、均一分布の代わりに、背景をＰＧ（Ｄ＝ｉ）として用いることが可能である。これは、既述のグランド・カバー事前確率である。
【００４４】
これらの作用を組み合わせて、定常状態の確率をより高い精度でモデリングする、目的地の確率分布を算出することが可能である。それら３つの成分は、クローズド・ワールド事前確率Ｐｃｌｏｓｅｄ（Ｄ＝ｉ）、前述のウェディング・ケーキ形状の分布Ｗ（Ｄ＝ｉ）で表される、パラメータ化された広がり、および孤立した目的地をモデリングする背景確率ＰＧ（Ｄ＝ｉ）である。全確率のうちの、Ｗ（Ｄ＝ｉ）に対する割合αを配分することが可能である。ここで、αは、該当する日の各層の合計である。ユーザが層状分布の先にある場所に移動する確率を取り込む、確率の学習された割合βが、背景（background）に割り当てられる。したがって、運転者の目的地の確率に対するオープン・ワールドのバージョンは、事前確率であって、次のように計算される。
Ｐｏｐｅｎ（Ｄ＝ｉ）＝（１−α−β）Ｐｃｌｏｓｅｄ（Ｄ＝ｉ）＋αＷ（Ｄ＝ｉ）＋βＰＧ（Ｄ＝ｉ）
これを、オープン・ワールド事前確率分布と呼ぶ。さらに、オープン・ワールド・モデリング・コンポーネント５０２は、これをベイズ公式で利用することが可能である。
【００４５】
時間の経過とともに、αおよびβは減少する傾向があり、それによって、各対象の実際の学習された目的地を優先する形で、クラスタ化および背景確率の調整分の効果を重視しなくなる。このことは、人が新しい場所を（特に観察期間の早い時期に、あるいは長時間運転において）訪問する可能性があるという事実を適切に考慮するオープン・ワールド・モデルの豊かさ（richness）を示している。
【００４６】
オープン・ワールド事前確率分布Ｐｏｐｅｎ（Ｄ＝ｉ）は、先入的知識がない（naive）クローズド・ワールド事前確率Ｐｃｌｏｓｅｄ（Ｄ＝ｉ）よりも良好に、対象の目的地の定常状態分布を概算することが可能である。さらに、オープン・ワールド事前確率は、クローズドワールドモデルの場合よりも、実際の定常状態にずっと近い事前確率で動作することが可能である。
【００４７】
図７は、効率的な経路のデータに少なくとも部分的に基づいて目的地の予測を生成するシステム７００を示す。システム７００は、入力データを取得することが可能なインターフェース・コンポーネント１０２を含む。入力データは、経路計画コンポーネント（例えば、図２の経路計画コンポーネント２０４）などによって生成され、データ・ストア（図示せず）に格納可能な、効率的な経路のデータを含むことが可能である。さらに、または代替として、インターフェース・コンポーネント１０２は、ユーザの現在のトリップに関連付けられたデータ（例えば、位置に関連するデータ、位置変化、トリップの所要時間など）を取得することが可能である。入力データは、目的地推定コンポーネント１０４によって評価されることが可能であり、目的地推定コンポーネント１０４はさらに、効率コンポーネント７０２を備えることが可能である。したがって、目的地推定コンポーネント１０４は、効率コンポーネント７０２によって提供される効率的運転尤度に基づいて、予測目的地を生成することが可能である。効率コンポーネント７０２は、最終的な位置／目的地についての根拠として、候補目的地の集合（例えば、各候補目的地）に関連付けられた運転効率を算出することが可能であり、これを、目的地推定コンポーネント１０４が利用することが可能である。
【００４８】
効率コンポーネント７０２によって生成される効率的運転尤度は、候補目的地に到着するまでの時間変化に基づくことが可能である。例えば、効率的運転尤度は、ユーザの現在のトリップに基づくことが可能である。効率的運転尤度（ならびに他の任意の尤度）は、Ｐ（Ｘ＝ｘ｜Ｄ＝ｉ）の形式とすることができる（ｘは、現在のトリップの何らかの測定される特徴である）。効率的運転尤度に関連付けられた、測定される特徴は、運転者が既にトラバースしたセルのリストとすることができ、この効率的運転尤度の背後の直観的真実は、一般に運転者は、目的地へ効率的な態様で到着する機会を逃さない、ということとすることができる。
【００４９】
効率コンポーネント７０２は、運転者の経路上の地点と候補目的地との間の運転時間を用いて効率を定量化することが可能である。したがって、効率コンポーネント７０２は、確率論的（probabilistic）グリッド内のセルの各ペア（ｉ，ｊ）について、それらのセルの間の運転時間Ｔｉ，ｊを推定するか、かつ／または、効率的な経路のデータの一部として推定を受け取ることが可能である。一例によれば、効率コンポーネント７０２が、各ペアのセル間の単純なユークリッド距離および速度概算値を利用して、運転時間の第１の近似値を生成することが可能である。さらに、または代替として、効率コンポーネント７０２は、デスクトップ・マッピング・ソフトウェアを用いて、各ペアのセルの中心点（緯度、経度）間の運転経路を計画することが可能である。このマッピング・ソフトウェアは、計画された経路の推定運転時間を与えることが可能なプログラマチック・インターフェースを提供することが可能である。運転経路プランナを用いることにより、セル間の道路網および速度制限の明細が明らかになり、より精度の高い運転時間推定値が得られる。Ｎ個のセルの場合、同一セルのペアを除き、Ｎ（Ｎ−１）個の異なる順序ペアが存在することができる。さらに、セルｉからセルｊまでの移動時間が、セルｊからセルｉまでと同じである（すなわち、Ｔｉ，ｊ＝Ｔｊ，ｉ）と仮定することによって、経路を計画することが可能である。なお、この計算は、個々のグリッドについて一度実行するだけでよい場合がある。
【００５０】
効率コンポーネント７０２は、運転者が目的地に早く到着できる機会を逃さない、と仮定することが可能である。例えば、運転者がトリップ中のある時点で目的地の近くまで来た場合、その後、目的地から離れるように運転する可能性は低い。言い換えると、トリップが進行するにつれて、目的地に到着することに関連付けられた時間は、単調に減少しうると予想することが可能である。一例によれば、効率コンポーネント７０２は、トリップデータを用いてこの過程を検証することを可能にする。この例によれば、各トリップを、トラバースされたセルの（隣接する繰り返しセルがない）シーケンスに変換し、各シーケンスを、一度に１セルずつ検証することが可能である。各シーケンスを検証しながら、これまでトラバースされたセルを通る、目的地セルまでの最短時間を追跡することが可能である。効率的な経路であれば、シーケンスが進むにつれて、この最短時間を減らすことが可能である。シーケンス内のセル間の遷移ごとに、Δｔを算出することが可能である（Δｔは、これまでに発生した、目的地までの最短時間を経て新しいセルに遷移することによって達成される、推定運転時間の変化であることが可能である）。Δｔは負であることが可能であり、したがって、セル間遷移によって、目的地までの時間を減らすことが可能である。
【００５１】
Δｔの正規化ヒストグラムは、Ｐ（ΔＴ＝Δｔ）の推定値であることが可能であり、運転者がそれまでに目的地に最も近づいた場合を基準に、運転者が次のセルに遷移することによって引き起こされるトリップ時間の変化の確率を与える。運転者が目的地までの最短時間を減らす確率は、例えば、
【００５２】
【数３】
【００５３】
になる。この例によれば、１−ｐ＝０．３７５、すなわち、この時間の３７．５％では、運転者が新しいセルに移動することによって、目的地までの時間が実際には増えたことになる。しかしながら、この数値は、経路プランナが持つことのできない、運転者の特別な知識（近道、道路網の変化、交通状態など）のために、見かけ上高くなる場合がある。さらに、空間を離散化することは、セルからセルへの経路が、セルの中心がどこになるかに応じて、運転者が通過するだけであれば、そうせざるを得ないい高速道路の入口および出口を考慮に入れなければならないことを意味する。Ｐ（ΔＴ＝Δｔ）の平均値および中央値は、それぞれ、−２２．２秒および−３９．０秒である。したがって、平均では、データは、運転者が、大まかには、グリッド内の新しいセルに遷移するたびに目的地に向かって進んでいることを示していると言える。
【００５４】
効率コンポーネント７０２は、ＰＥ（Ｓ＝ｓ｜Ｄ＝ｉ）を算出することが可能である。これは、Ｓ、これまでのトリップ、所定の目的地の確率である。このトリップＳは、これまでにトラバースされたセルの（隣接する繰り返しを含まない）系列Ｓ＝｛ｓ１，ｓ２，ｓ３，．．．，ｓｎ｝として表される。各セルｓｊにおいて、運転者は、次にどのセルに行くかを、他に依存せずに決定すると仮定することが可能である。これは、この尤度が次のように計算できることを意味する。
【００５５】
【数４】
【００５６】
ここで、ｎは、そのトリップでこれまでにトラバースされたグリッド・セルの数である。この式では、新しいセルが以前のどのセルよりも目的地ｉに近い場合（これは、運転者がセルｉまでの推定時間を減らす動きをしたことを表す）にｐを乗じ、それ以外の場合は、１−ｐを乗じる。ｐ＞０．５である限り、この尤度は、運転者が向かっているセルを優先する。
【００５７】
この尤度および均一事前確率を利用して、事後分布を、効率コンポーネント７０２を使用して取得することが可能である。例えば、トリップが特定の位置から特定の方向（例えば、南）に開始される場合は、目的地としては除外してよいセルがある（例えば、北に向かうセルは、目的地としては除外してよい）。この場合は、例えば、目的地の確率を地図上に描くことが可能である。さらに南へ移動した後は、南側部分を除くすべてを除外することが可能である。
【００５８】
一例によれば、運転者は、本当の目的地が近くなったとき（例えば、トリップの終了時）にくらべ、トリップの開始時には、よりランダムな、とりとめのない（meandering）走行をする可能性がある。したがって、各時間ステップにおける、運転者が最終目的地に近づく確率ｐは、トリップの経過時間に応じて変化する可能性がある。したがって、ｐは、トリップの終了時より開始時のほうが低い可能性がある。
【００５９】
別の例によれば、効率コンポーネント７０２は、トリップの開始セルｓと候補目的地セルｉとに基づいて効率を測定することが可能である。運転者の経路が効率的であれば、これら２つのセルの間を行く全所要時間は約Ｔｓ，ｉであるはずである。運転者が現在セルｊにいる場合、候補目的地ｉに到着するまでの時間は約Ｔｊ，ｉであるはずである。ｉが本当に目的地であって、運転者が効率的な経路をたどっているとすれば、運転者は、時間Ｔｓ，ｉ−Ｔｊ，ｉで現在のセルｊに到着したはずである。運転者が効率的でない経路をとっているとすれば、運転者の、この地点までの実際のトリップ時間Δｔは、Ｔｓ，ｉ−Ｔｊ，ｉより長くなる。したがって、効率コンポーネント７０２は、効率を、次式のように、運転者が候補目的地に向かって移動することに費やすべきだった時間を、実際に発生した時間で割った比として測定することが可能である。
【００６０】
【数５】
【００６１】
そのような比は、ｓとｉとの間の効率的なトリップの場合には約１であることが期待される。ＧＰＳ調査データを用いれば、効率値の分布は、既知のトリップとそれらの対応する目的地とに基づいて算出されることが可能である。効率尤度ＰＥ（Ｅ＝ｅ｜Ｄ＝ｉ）は、運転者が目的地への途上で実際に生み出す効率を表す。候補目的地が低尤度の効率を呈した場合、その事後確率は、ＰＥ（Ｅ＝ｅ｜Ｄ＝ｉ）がベイズ規則に組み込まれたときに、対応して低くなる可能性がある。効率の尤度は、トリップの一部分に応じて変化する可能性がある。したがって、そのようなトリップの開始時近辺の分布は、短いトリップに対して正確な移動時間を与えることができないために非現実的なものになる可能性がある。運転者によっては、すべてのトリップ部分に対し、スピードを出すか、理想的トリップ時間推定値の間違いによって、効率が１．０より高くなる可能性がある。目的地の予測にこの尤度を用いる効果は、運転者が候補目的地から離れつつあるように見える場合に、その目的地の確率が低くなる、ということである。
【００６２】
図８は、目的地を予測することと関連してトリップ時間を評価するシステム８００を示す。システム８００は、入力データを取得するインターフェース・コンポーネント１０２と、入力データを評価して予測目的地を生成する目的地推定コンポーネント１０４とを含む。目的地推定コンポーネント１０４はさらに、候補目的地までの推定時間および／または現在のトリップに関連する経過トリップ時間に関連付けられた尤度を評価するトリップ時間コンポーネント８０２を含むことが可能である。
【００６３】
トリップ時間コンポーネント８０２は、入力データの一部として含まれることが可能なトリップ時間分布データに少なくとも部分的に基づいてトリップ時間尤度を生成することが可能である。例えば、トリップ時間分布データは、全米世帯移動調査（National Household Transportation Survey）（ＮＨＴＳ）から得られるが、本特許請求対象はそのように限定されない。一例として、２００１年からのＮＨＴＳは、全米の約６６０００世帯からの、日常の移動および／または長距離旅行に関するデータを含む。さらに、調査結果はＷｅｂインターフェースからも利用可能であり、トリップ時間のヒストグラムを生成することが可能である。
【００６４】
トリップ時間を支配する尤度は、ＰＴ（ＴＳ＝ｔｓ｜Ｄ＝ｉ）である（ＴＳは、これまでのトリップ時間を表すランダム変数である）ことが可能である。この尤度を用いるために、トリップ時間コンポーネント８０２は、ヒストグラムに関連付けられたビンに従ってトリップ時間を量子化することが可能である。ヒストグラムは、トリップの開始前の目的地時間の分布（例えば、Ｐ（ＴＤ＝ｔＤ）（ＴＤは全トリップ時間を表す））を表すことが可能である。トリップにおいて一定時間が経過すると、経過した時間帯の確率はゼロになり、次式を与える正規化を行うことが可能である。
【００６５】
【数６】
【００６６】
候補目的地についての尤度を算出するために、ｔＳを、これまでのトリップの長さとし、ｔＤを、Ｔｉ，ｊの推定トリップ時間に基づく、現在のセルから候補目的地までの推定時間とすることができる。この尤度および／または均一事前確率を利用して、事後分布を取得することが可能である。
【００６７】
図９は、事前確率および／または尤度を組み合わせて目的地の予測を容易にすることを可能にするシステム９００を示す。システム９００は、入力データを取得することが可能なインターフェース・コンポーネント１０２を含む。さらに、システム９００は、事前確率および／または尤度を用いて目的地を確率論的に（probabilistically）予測する目的地推定コンポーネント１０４を含む。目的地推定コンポーネント１０４はさらに、個人の目的地事前確率を生成するユーザ履歴コンポーネント４０２、グランド・カバー事前確率を生成するグランド・カバー・コンポーネント３０２、効率的運転尤度を提供する効率コンポーネント７０２、および／またはトリップ時間尤度を生成するトリップ時間コンポーネント８０２を備えることが可能である。
【００６８】
目的地推定コンポーネント１０４はさらに、目的地を確率論的に（probabilistically）予測することに関連して利用する事前確率および／または尤度を選択することを可能にする融合（fusing）コンポーネント９０２と結合されることが可能である。融合コンポーネント９０２は、選択された事前確率および／または尤度を組み合わせることが可能である。例えば、融合コンポーネント９０２は、選択された事前確率および／または尤度に関連付けられた１つの確率分布を生成することが可能である。一例として、個人の目的地事前確率が選択されることが可能であり、したがって、融合コンポーネント９０２は、個人の目的地事前確率に基づく確率分布を生成することが可能である。別の例によれば、グランド・カバー事前確率、効率的運転尤度、およびトリップ時間尤度が選択されることが可能であり、したがって、融合コンポーネント９０２は、これらの選択された事前確率および尤度を組み合わせることが可能である。本特許請求対象は、これらの例に限定されないことを理解されたい。
【００６９】
融合コンポーネント９０２は、目的地に対して、効率的運転尤度およびトリップ時間尤度の独立性を仮定することが可能であり、各目的地について、ベイズ規則を用いて、これら２つの要素と事前確率とを組み合わせて、１つの事後確率にすることが可能である。したがって、目的地の確率は次のようになる。
【００７０】
【数７】
【００７１】
そのような独立性を考慮することを、ベイジアン更新のナイーブ・ベイズ公式化（naive Bayes formulation）と呼ぶ。独立性の仮定を緩めて、より濃密な確率論的（probabilistic）依存性を可能にすることにより、予測の精度を高めることが可能である。これは、現実的な依存性を導入することによって、確率論的（probabilistic）影響の「過大評価」が最小限に抑えられるためである。この場合は、運転効率とトリップ時間との関係を考慮することができない。さらに、上述の目的地の確率の式の評価は、確率論的（probabilistic）成分のそれぞれについてスカラのグリッドを計算し、対応するセルのスカラ同士を掛け合わせ、正規化して積の合計を１にすることによって行われることが可能である。
【００７２】
目的地予測の確率論的（probabilistic）公式化は、運転者の真の目的地の不確定性を、首尾一貫した様式で表すことが可能であることを意味する。したがって、目的地推定コンポーネント１０４のようなシステムに構築されたアプリケーションは、運転者の目的地の避けがたい不確定性を明らかにすることが可能である。例えば、運転者の目的地の近くのレストランまたはガソリン・スタンドを示すアプリケーションは、目的地がより確定するにつれて、徐々に、より詳細を表示し、より狭い範囲を表示することが可能であろう。交通の問題に関する警告は、その問題に遭遇する確実性が特定のしきい値を超えるまで抑えられることが可能である。認識力が弱まって、意図した目的地からずれている人々に対しては、ずれがほぼ確定した場合のみ警告することが可能である。
【００７３】
図１０は、予測目的地に関連する可能性がある情報を提供するシステム１０００を示す。システム１０００は、入力データを受け取るインターフェース・コンポーネント１０２と、入力データに基づいて目的地を確率論的に（probabilistically）予測する目的地推定コンポーネント１０４とを含む。例えば、目的地推定コンポーネント１０４は、１つ以上の事前確率および／または１つ以上の尤度を利用して予測を生成することが可能である。予測目的地はさらに、コンテンツ・コンポーネント１００２に伝えられることが可能である。コンテンツ・コンポーネント１００２は、予測目的地に関連付けられた関連情報を提供する。例えば、コンテンツ・コンポーネント１００２は、交通（traffic）、工事（construction）、前方の安全性の問題(safety issues ahead）などについて警告メッセージを示したり、掲示されている広告を案内したり、指示（directions）、経路の助言（routing advice）、最新情報などを与えたりすることが可能である。
【００７４】
コンテンツ・コンポーネント１００２は、予測目的地に関連する任意の情報を提供することが可能である。例えば、コンテンツ・コンポーネント１００２は、レストラン、交通、ナビゲーション支援、ガソリン・スタンド、目立つ建造物、小売店などに関連する情報を生成することが可能である。一例によれば、特定の目的地を、コンテンツ・コンポーネント１００２に伝えることが可能である。この例によれば、コンテンツ・コンポーネント１００２は、特定の場所に関連付けられた情報および／または現在位置と目的地との間の経路のそばの任意の場所に関連付けられた情報を含む警告を出力することが可能である。したがって、コンテンツ・コンポーネント１００２は、ある場所でイベントが行われていることや、交通が混雑していることなどを示すことが可能である。別の例によれば、コンテンツ・コンポーネント１００２は、目的地および／または経路付近に位置する商店に関連付けられた広告情報を提供することが可能である。別の例によれば、ユーザが迷ったと思われる場合に、コンテンツ・コンポーネント１００２が警告を出力して、ユーザが、予測目的地までの正しい経路をたどり続けることができるようにすることが可能である。
【００７５】
コンテンツ・コンポーネント１００２は、コンテンツ・コンポーネント１００２から提供される関連情報を、ユーザ関連設定に基づいて特定ユーザに適合させるカスタマイズ・コンポーネント１００４を含むことが可能である。例えば、ユーザ関連設定は、ユーザが広告を一切受け取らないことを望んでいることを示している場合があり、その場合は、カスタマイズ・コンポーネント１００４が、そのような関連情報の送信を低減することが可能である。別の例によれば、ユーザが、目的地までの経路沿いにおけるすべての交通事故について通知されることを望んでいる場合があり、その場合、カスタマイズ・コンポーネント１００４は、コンテンツ・コンポーネント１００２がそのような情報を提供することを可能にすること、および／または交通関連情報を、コンテンツ・コンポーネント１００２から提供されるそれ以外の情報より優先することが可能である。本特許請求対象は、前述の例に限定されないことを理解されたい。
【００７６】
図１１は、トリップ中に目的地を確率論的に（probabilistically）予測するシステム１１００を示す。システム１１００は、インターフェース・コンポーネント１０２および目的地推定コンポーネント１０４を含む。さらに、システム１１００は、ユーザおよび／または端末の現在位置および／または位置変化を識別する位置特定コンポーネント１１０２を含む。例えば、位置特定コンポーネント１１０２は、ＧＰＳ、衛星ナビゲーション・システム、ＧＬＯＮＡＳＳ、Ｇａｌｉｌｅｏ、Ｅｕｒｏｐｅａｎ Ｇｅｏｓｔａｔｉｏｎａｒｙ Ｎａｖｉｇａｔｉｏｎ Ｏｖｅｒｌａｙ Ｓｙｓｔｅｍ（ＥＧＮＯＳ）、Ｂｅｉｄｏｕ、Ｄｅｃｃａ Ｎａｖｉｇａｔｏｒ Ｓｙｓｔｅｍ、通信塔間の三角測量などに関連付けられることが可能である。位置特定コンポーネント１１０２は、位置関連データをインターフェース・コンポーネント１０２に提供して、さらなる評価を可能にすることが可能である。
【００７７】
システム１１００はさらに、時間関連データをインターフェース・コンポーネント１０２に提供するタイマ・コンポーネント１１０４を含むことが可能である。タイマ・コンポーネント１１０４は、例えば、現在のトリップに関連付けられた時間量、動きがほとんどまたはまったくないことに関連付けられた時間量などを含む時間関連データを提供することが可能である。さらに、位置特定コンポーネント１１０２およびタイマ・コンポーネント１１０４は別々のコンポーネントとして図示されているが、両者が一体型のコンポーネントであってよいことも企図されている。
【００７８】
インターフェース・コンポーネント１０２は、データ・ストア１１０６と結合されていてもよい。データ・ストア１１０６は、例えば、ユーザ、ユーザの履歴、地理的領域の地勢図、トリップ、効率的な経路などに関連するデータを含むことが可能である。さらに、位置特定コンポーネント１１０２から提供される位置関連データおよび／またはタイマ・コンポーネント１１０４から取得される時間関連データを、データ・ストア１１０６に格納することが可能である。データ・ストア１１０６は、例えば、揮発性メモリまたは不揮発性メモリであってよく、あるいは、揮発性メモリおよび不揮発性メモリの両方を含んでもよい。限定ではなく例として、不揮発性メモリとしては、読み出し専用メモリ（ＲＯＭ）、書き込み可能ＲＯＭ（ＰＲＯＭ）、電気的書き込み可能ＲＯＭ（ＥＰＲＯＭ）、電気的消去可能書き込み可能ＲＯＭ（ＥＥＰＲＯＭ）、フラッシュ・メモリなどがある。揮発性メモリとしては、ランダム・アクセス・メモリ（ＲＡＭ）があり、これは外部キャッシュ・メモリとして動作する。ＲＡＭは、様々な形式で使用可能であり、限定ではなく例として、スタティックＲＡＭ（ＳＲＡＭ）、ダイナミックＲＡＭ（ＤＲＡＭ）、シンクロナスＤＲＡＭ（ＳＤＲＡＭ）、ダブル・データ・レートＳＤＲＡＭ（ＤＤＲ ＳＤＲＡＭ）、エンハンストＳＤＲＡＭ（ＥＳＤＲＡＭ）、シンクリンクＤＲＡＭ（ＳＬＤＲＡＭ）、ランバス・ダイレクトＲＡＭ（ＲＤＲＡＭ）、ダイレクト・ランバス・ダイナミックＲＡＭ（ＤＲＤＲＡＭ）、ランバス・ダイナミックＲＡＭ（ＲＤＲＡＭ）などの形式で使用可能である。本対象のシステムおよび方法のデータ・ストア１１０６は、これらのメモリおよび他の任意の好適なタイプのメモリを備えること、およびそれらに限定されないことを意図している。さらに、データ・ストア１１０６は、サーバ、データベース、ハード・ドライブなどであってよいことを理解されたい。
【００７９】
さらに、目的地推定コンポーネント１０４は、実時間トリップ・コンポーネント１１０８を含むことが可能であり、実時間トリップ・コンポーネント１１０８は、現在のトリップに関連付けられたデータを利用して、目的地を確率論的に（probabilistically）予測することが可能である。しかしながら、予測目的地の生成にはそのようなデータを利用する必要がないことも企図されている。例えば、実時間トリップ・コンポーネント１１０８は、位置特定コンポーネント１１０２から提供されることが可能な、特定のトリップに関連付けられた位置データを組み合わせることが可能である。組み合わせられた位置データは、予測の生成に利用されることが可能である。
【００８０】
図１２は、予測目的地の生成を容易にするシステム１２００を示す。システム１２００は、インターフェース・コンポーネント１０２および目的地推定コンポーネント１０４を含むことが可能であり、これらは前述のそれぞれのコンポーネントと実質的に同様であってよい。システム１２００はさらに、インテリジェント・コンポーネント１２０２を含むことが可能である。インテリジェント・コンポーネント１２０２は、入力データに関連付けられた目的地の予測を容易にするために目的地推定コンポーネント１０４によって利用されることが可能である。例えば、インテリジェント・コンポーネント１２０２は、ユーザが予測目的地へのトラバースに近道を用いたことを識別することが可能である。したがって、識別された近道は、記憶され、かつ／または将来の目的地を評価することに関連して利用されることが可能である。別の例によれば、インテリジェント・コンポーネント１２０２は、（例えば、現在の組合せにくらべて）より精度の高い目的地予測を生成できる事前確率および／または尤度の組合せ（あるいは、１つの事前確率または１つの尤度）を決定することが可能である。その後、目的地推定コンポーネント１０４は、インテリジェント・コンポーネント１２０２によって識別された組合せを用いることが可能である。
【００８１】
インテリジェント・コンポーネント１２０２は、イベントおよび／またはデータの形で取り込まれた観察結果の集合から、システム、環境、および／またはユーザの状態についての推論に必要なものを供給することが可能であることを理解されたい。例えば、推論は、特定のコンテクストまたはアクションを識別するために用いられることが可能であり、あるいは、各状態に対する確率分布を生成することが可能である。推論は、確率論的（probabilistic）であることが可能である。すなわち、データおよびイベントの考慮に基づく、関心対象の各状態に対する確率分布の算出であることが可能である。推論はまた、イベントおよび／またはデータの集合から、より高レベルのイベントを構成するために用いられる手法を指すことも可能である。そのような推論は、観察されたイベントおよび／または記憶されたイベントデータの集合から新しいイベントまたはアクションを構築することにつながる。それらのイベントは、時間的に近いもの同士が互いに関連していてもいなくてもよく、また、それらのイベントおよびデータが由来するイベントおよびデータ・ソースは１つであっても複数であってもよい。本特許請求対象に関連して自動的な、かつ／または推論されたアクションを実行することに関連して、様々な（明示的かつ／または暗黙的にトレーニングされる）分類スキームおよび／またはシステム（例えば、サポート・ベクトル・マシン、ニューラル・ネットワーク、エキスパート・システム、ベイジアン信念ネットワーク、ファジーロジック、データ・フュージョン・エンジンなど）を用いることが可能である。
【００８２】
分類子（classifier）は、入力属性ベクトルｘ＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘｎ）を、入力がクラスに属するという確実性（confidence）にマッピングする関数、すなわち、ｆ（ｘ）＝ｃｏｎｆｉｄｅｎｃｅ（ｃｌａｓｓ）である。そのような分類は、確率論的（probabilistic）および／または統計に基づく解析（例えば、解析ユーティリティおよびコストに分解する解析）を用いて、自動的に実行されることをユーザが望むアクションを予測または推定することが可能である。サポート・ベクトル・マシン（ＳＶＭ）は、使用することが可能な分類子の一例である。ＳＶＭは、可能な入力の空間における超曲面（hypersurface）を見つけることによって動作し、この超曲面は、トリガ基準を非トリガ・イベントから分離しようとする。これは、直観的には、トレーニング・データの近くにあってトレーニング・データと同一ではないデータを検査する場合に、分類を正しいものにする。他の有向および非有向のモデル分類手法としては、例えば、ナイーブ・ベイズ（naive Bayes）、ベイジアン・ネットワーク、決定木、ニューラル・ネットワーク、ファジー・ロジック・モデルを含み、様々なパターンの独立性を提供する確率論的（probabilistic）分類モデルを用いることができる。本明細書で用いられる「分類」には、優先度モデルを開発することに利用される統計的回帰も含まれる。
【００８３】
プレゼンテーション・コンポーネント１２０４は、様々なタイプのユーザ・インターフェースを提供して、ユーザと、目的地推定コンポーネント１０４に結合されたすべてのコンポーネントとの間の対話を容易にすることが可能である。図示されるように、プレゼンテーション・コンポーネント１２０４は、目的地推定コンポーネント１０４とともに利用されることが可能な、独立したエンティティである。しかしながら、プレゼンテーション・コンポーネント１２０４および／または同様のビュー・コンポーネントは、目的地推定コンポーネント１０４（および／またはインターフェース・コンポーネント１０２）および／またはスタンドアロン・ユニットに組み込まれることが可能であることを理解されたい。プレゼンテーション・コンポーネント１２０４は、１つまたは複数のグラフィカル・ユーザ・インターフェース（ＧＵＩ）、コマンド・ライン・インターフェースなどを提供することが可能である。例えば、データのロード、インポート、読み込みなどを行う領域または手段をユーザに提供するＧＵＩが描画されることが可能であり、さらに、このＧＵＩは、そのような操作の結果を表示する領域を含むことが可能である。これらの領域は、ダイアログ・ボックス、スタティック・コントロール、ドロップ・ダウン・メニュー、リスト・ボックス、ポップアップ・メニュー、エディット・コントロール、コンボ・ボックス、ラジオ・ボタン、チェック・ボックス、プッシュ・ボタン、およびグラフィックボックスを備える、既知のテキスト領域および／またはグラフィック領域を備えることが可能である。さらに、ナビゲーション用垂直および／または水平スクロール・バーや、領域を見えるようにするかどうかを決定するツール・ボタンなどの表示を容易にするユーティリティを用いることが可能である。例えば、ユーザは、目的地推定コンポーネント１０４に結合されたコンポーネントのうちの１つまたは複数と対話することが可能である。
【００８４】
ユーザはさらに、それらの領域との対話において、様々な装置（例えば、マウス、ローラーボール、キーパッド、キーボード、ペン、および／または音声アクティベーション）を用いて情報を選択および入力することが可能である。一般に、検索を開始する場合は、情報を入力した後に、プッシュ・ボタンや、キーボードのＥｎｔｅｒキーのようなメカニズムを用いることが可能である。しかしながら、本特許請求対象は、そのように限定されないことを理解されたい。例えば、チェック・ボックスをハイライトするだけで、情報の伝達を開始することも可能である。別の例では、コマンド・ライン・インターフェースを用いることが可能である。例えば、コマンド・ライン・インターフェースは、（例えば、ディスプレイ上のテキスト・メッセージまたは音声トーンにより）情報をテキスト・メッセージで入力するようにユーザを促す（プロンプトする）ことが可能である。それに対し、ユーザは、適切な情報（例えば、インターフェース・プロンプト内に示された選択肢に対応する英数字入力、またはプロンプト内に提起された質問に対する答え）を入力することが可能である。コマンド・ライン・インターフェースは、ＧＵＩおよび／またはＡＰＩと関連して用いられることが可能であることを理解されたい。さらに、コマンド・ライン・インターフェースは、ハードウェア（例えば、ビデオ・カード）および／または限定的なグラフィック・サポートのディスプレイ（例えば、白黒でＥＧＡ）、および／または低帯域幅通信チャネルと関連して用いられることが可能である。
【００８５】
図１３〜１４は、本特許請求対象による方法論を示す。説明を簡潔にするために、この方法論を、一連の操作として図示および説明する。本発明は、図示された操作および／または操作の順序によって限定されるものではなく、例えば、各操作は、様々な順序で、かつ／または同時に行われうるものであり、さらに、本明細書に提示および説明されていない他の操作とともに行われることも可能であることを理解されたい。さらに、本特許請求対象による方法の実装には、図示されている操作のすべてが必要であるとは限らない。さらに、当業者であれば理解されるように、本方法は、代替として、状態図またはイベントによって、一連の相互に関連する状態として表されることが可能である。
【００８６】
図１３は、目的地（destination(s)）を確率論的に（probabilistically）予測することを容易にする方法１３００を示す。１３０２で、地理的場所に関連付けられた確率論的（probabilistic）グリッドを生成する。地理的場所は、任意のサイズであってよいことが企図されている。例えば、地理的場所は、市、郡、任意の数の街区、州、国などに関連付けられることが可能である。さらに、グリッドは、任意の数のセルを含むことが可能であり、セルは任意のサイズ、形などであってよい。
【００８７】
１３０４で、トリップに関連付けられたデータを評価して、事前確率（prior(s)）および／または尤度（likelihood(s)）を決定する。例えば、評価されたデータは、グランド・カバー・データ、履歴データ、効率的な経路のデータ、トリップ時間分布データ、現在のトリップに関連する実時間位置特定データなどであってよい。データは、例えば、任意のソースから取得可能である。さらに、例えば、現在のトリップに関連する実時間位置データは、事前確率または尤度を決定する際に考慮されることが可能である。代替として、実時間位置データを利用することなく、事前確率または尤度を識別することが可能である。１３０６で、事前確率（prior(s)）および／または尤度（likelihood(s)）を確率論的に（probabilistically）組み合わせることにより、グリッドを利用して、トリップに関連する目的地を予測する。１つ以上の事前確率および／または１つ以上の尤度を選択して組み合わせることが可能である。したがって、一例によれば、目的地の予測に用いるために、グランド・カバー事前確率とトリップ時間尤度とを選択することが可能である。しかしながら、本特許請求対象は、そのような例に限定されない。この、事前確率（prior(s)）および／または尤度（likelihood(s)）の組合せを用いて、予測目的地を生成することが可能である。
【００８８】
図１４は、組み合わせられることが可能な事前確率（prior(s)）および／または尤度（likelihood(s)）に基づいて予測可能な目的地に関連する情報を提供する方法１４００を示す。１４０２で、個人の目的地事前確率、グランド・カバー事前確率、効率的運転尤度、およびトリップ時間尤度のうちの１つまたは複数を選択する。例えば、個人の目的地事前確率は、ユーザの以前の目的地の集合（例えば、履歴データ）に基づくことが可能である。さらに、グランド・カバー事前確率は、地理的場所に関連する確率論的（probabilistic）グリッドの中のあるセルが目的地である、そのセル内のグランド・カバーに基づく確率に関連付けられることが可能である。さらに、効率的運転尤度は、候補目的地に到着するまでの時間の変化に基づくことが可能である。したがって、ペアのセル間の経路は、効率的運転尤度に関連して評価されることが可能である。トリップ時間尤度は、例えば、経過トリップ時間および／またはトリップ時間分布データに関連付けることができる。
【００８９】
１４０４で、選択された事前確率（prior(s)）および／または尤度（likelihood(s)）を組み合わせる。例えば、選択された事前確率（prior(s)）および／または尤度（likelihood(s)）を組み合わせることに関連して、ベイズ規則を利用することが可能である。１４０６で、この組合せを利用して、目的地を確率論的に（probabilistically）予測する。したがって、例えば、確率論的（probabilistic）グリッドにある特定のセルを、目的地として識別することが可能である。１４０８で、予測目的地に関連する情報を提供する。例えば、その情報は、目的地、および／または目的地までの経路沿いの場所に関連付けることが可能である。別の例として、関連情報は、交通関連の情報、天候関連の情報、目標となる広告に関連付けられた情報、ナビゲーション支援を与えることに関連付けられた情報、関心対象である可能性があるイベントに関連付けられた情報などであってよい。
【００９０】
図１５〜１８は、運転者の行動および目的地の予測のモデリングに関連する様々な態様を描いた例示的グリッドおよび対応する地図を示す。これらのグリッドおよび地図は例であって、本特許請求対象はそのように限定されないことを理解されたい。図１５は、特定ユーザに関連する個人の目的地事前確率に関連付けられた目的地セルを描いたグリッド１５００を示す。図１６は、グランド・カバー事前確率を示すグリッド１６００を示す。より暗い色の輪郭は、より確率が高い目的地セルを示している。図１７は、効率的運転尤度に関連するグリッド１７００を示す。具体的には、グリッド１７００は、南方向に４セル分移動した後に、北東セクションのほとんどを除外してよいことを示している。さらに、図１８に描かれたグリッド１８００は、ユーザがさらに南に移動し続け、グリッド１７００の場合よりさらに多くのグリッドをグリッド１８００から除外してよいことを示している。
【００９１】
本特許請求対象の各種態様を実装するためのさらなるコンテクストを与えるために、以下では、図１９〜２０を参照しながら、本発明の各種態様を実装することに好適なコンピューティング環境を、簡潔かつ一般的に説明する。ここまでは、本特許請求対象を、ローカル・コンピュータおよび／またはリモート・コンピュータで実行されるコンピュータ・プログラムの、コンピュータで実行可能な命令の一般的コンテクストで説明してきたが、当業者であれば理解されるように、本発明は、他のプログラム・モジュールと組み合わせて実装されることも可能である。一般に、プログラム・モジュールは、特定のタスクの実行および／または特定の抽象データ型の実装を行うルーチン、プログラム、コンポーネント、データ構造体などを含む。
【００９２】
さらに、当業者であれば理解されるように、本発明の方法は、他のコンピュータ・システム構成でも実施可能であり、そのような構成として、シングル・プロセッサまたはマルチ・プロセッサのコンピュータ・システム、ミニ・コンピュータ、メインフレーム・コンピュータ、ならびにパーソナル・コンピュータ、ハンドヘルド・コンピューティング装置、マイクロ・プロセッサ・ベースおよび／またはプログラマブルの家庭用電子機器などがあり、これらのそれぞれが、１つまたは複数の関連装置と通信するように動作可能である。本特許請求対象の図示された各態様は、分散コンピューティング環境でも実施可能である。分散コンピューティング環境では、ある一定のタスクが、通信ネットワークでリンクされているリモート処理装置で実行される。しかしながら、本発明の態様のうちの、すべてではなくともいくつかは、スタンドアロン・コンピュータで実施可能である。分散コンピューティング環境では、プログラム・モジュールを、ローカルおよび／またはリモートのメモリ・ストレージ装置に置くことが可能である。
【００９３】
図１９は、本特許請求対象が対話することが可能な例示的コンピューティング環境１９００の概略ブロック図である。システム１９００は、１つまたは複数のクライアント１９１０を含む。クライアント１９１０は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティング装置）であってよい。システム１９００はさらに、１つまたは複数のサーバ１９２０を含む。サーバ１９２０は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティング装置）であってよい。サーバ１９２０は、例えば、本発明を用いることにより、変換を実行するスレッドを収容することが可能である。
【００９４】
クライアント１９１０とサーバ１９２０との間の可能な一通信は、２つ以上のコンピュータ・プロセスの間で伝送されるように適合されたデータ・パケットの形式で行われることが可能である。システム１９００は、クライアント１９１０とサーバ１９２０との間の通信を容易にするために用いられることが可能な通信フレームワーク１９４０を含む。クライアント１９１０は、クライアント１９１０のローカルな情報を格納するために用いられることが可能な１つまたは複数のクライアント・データ・ストア１９５０に、動作可能なように結合される。同様に、サーバ１９２０は、サーバ１９２０のローカルな情報を格納するために用いられることが可能な１つまたは複数のサーバ・データ・ストア１９３０に、動作可能なように結合される。
【００９５】
図２０は、本特許請求対象の各種態様を実装するための例示的環境２０００を示し、例示的環境２０００はコンピュータ２０１２を含む。コンピュータ２０１２は、処理ユニット２０１４、システム・メモリ２０１６、およびシステム・バス２０１８を含む。システム・バス２０１８は、システム・メモリ２０１６を含み、これに限定されないシステムコンポーネントを処理ユニット２０１４に結合する。処理ユニット２０１４は、利用可能な各種のプロセッサのどれでもよい。デュアル・マイクロ・プロセッサや他のマルチプ・ロセッサ・アーキテクチャを、処理ユニット２０１４として用いることも可能である。
【００９６】
システム・バス２０１８は、任意の様々な利用可能バス・アーキテクチャを用いる、メモリ・バスまたはメモリ・コントローラ、ペリフェラル・バスまたは外部バス、および／またはローカル・バスを含む、様々なタイプのバス構造のいずれかであってよく、利用可能バス・アーキテクチャとしては、Ｉｎｄｕｓｔｒｉａｌ Ｓｔａｎｄａｒｄ Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＳＡ）、Ｍｉｃｒｏ−Ｃｈａｎｎｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ（ＭＳＡ）、Ｅｘｔｅｎｄｅｄ ＩＳＡ（ＥＩＳＡ）、Ｉｎｔｅｌｌｉｇｅｎｔ Ｄｒｉｖｅ ＥＩｅｃｔｒｏｎｉｃｓ（ＩＤＥ）、ＶＥＳＡ Ｌｏｃａｌ Ｂｕｓ（ＶＬＢ）、Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）、Ｃａｒｄ Ｂｕｓ、Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ（ＵＳＢ）、Ａｄｖａｎｃｅｄ Ｇｒａｐｈｉｃｓ Ｐｏｒｔ（ＡＧＰ）、Ｐｅｒｓｏｎａｌ Ｃｏｍｐｕｔｅｒ Ｍｅｍｏｒｙ Ｃａｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ａｓｓｏｃｉａｔｉｏｎバス（ＰＣＭＣＩＡ）、Ｆｉｒｅｗｉｒｅ（ＩＥＥＥ １３９４）、Ｓｍａｌｌ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍｓ Ｉｎｔｅｒｆａｃｅ（ＳＣＳＩ）などがあり、これらに限定されない。
【００９７】
システム・メモリ２０１６は、揮発性メモリ２０２０および不揮発性メモリ２０２２を含む。基本入出力システム（ＢＩＯＳ）は、起動時などに、コンピュータ２０１２内の要素間で情報を転送する基本ルーチンを含み、不揮発性メモリ２０２２に格納される。限定ではなく例として、不揮発性メモリ２０２２としては、読み出し専用メモリ（ＲＯＭ）、書き込み可能ＲＯＭ（ＰＲＯＭ）、電気的書き込み可能ＲＯＭ（ＥＰＲＯＭ）、電気的消去可能書き込み可能ＲＯＭ（ＥＥＰＲＯＭ）、フラッシュ・メモリなどがある。揮発性メモリ２０２０としては、ランダム・アクセス・メモリ（ＲＡＭ）があり、これは外部キャッシュ・メモリとして動作する。ＲＡＭは、様々な形式で使用可能であり、限定ではなく例として、スタティックＲＡＭ（ＳＲＡＭ）、ダイナミックＲＡＭ（ＤＲＡＭ）、シンクロナスＤＲＡＭ（ＳＤＲＡＭ）、ダブル・データ・レートＳＤＲＡＭ（ＤＤＲ ＳＤＲＡＭ）、エンハンストＳＤＲＡＭ（ＥＳＤＲＡＭ）、シンクリンクＤＲＡＭ（ＳＬＤＲＡＭ）、ランバス・ダイレクトＲＡＭ（ＲＤＲＡＭ）、ダイレクト・ランバス・ダイナミックＲＡＭ（ＤＲＤＲＡＭ）、ランバス・ダイナミックＲＡＭ（ＲＤＲＡＭ）などの形式で使用可能である。
【００９８】
コンピュータ２０１２はさらに、リムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータストレージ媒体を含む。図２０は、例えば、ディスク・ストレージ２０２４を示している。ディスク・ストレージ２０２４は、磁気ディスク・ドライブ、フロッピー（登録商標）ディスク・ドライブ、テープ・ドライブ、Ｊａｚドライブ、Ｚｉｐドライブ、ＬＳ−１００ドライブ、フラッシュ・メモリ・カード、またはメモリ・スティックのような装置を含み、これらに限定されない。さらに、ディスク・ストレージ２０２４は、独立に、または他のストレージ媒体との組合せでストレージ媒体を含むことが可能であり、他のストレージ媒体としては、コンパクト・ディスクＲＯＭ装置（ＣＤ−ＲＯＭ）、追記型ＣＤドライブ（ＣＤ−Ｒドライブ）、書き換え可能ＣＤドライブ（ＣＤ−ＲＷドライブ）、またはデジタル多用途ディスクＲＯＭドライブ（ＤＶＤ−ＲＯＭ）などの光ディスク・ドライブがあり、これらに限定されない。ディスク・ストレージ装置２０２４とシステム・バス２０１８との接続を容易にするために、典型的には、インターフェース２０２６のようなリムーバブルまたは非リムーバブル・インターフェースが用いられる。
【００９９】
図２０では、ユーザと、好適なオペレーティング環境２０００内に示されている基本コンピュータリソースとの媒介として動作するソフトウェアが示されていることを理解されたい。そのようなソフトウェアは、オペレーティング・システム２０２８を含む。オペレーティング・システム２０２８は、ディスク・ストレージ２０２４に格納可能であって、コンピュータ・システム２０１２のリソースの制御および割り当てを行うように動作する。システム・アプリケーション２０３０は、システム・メモリ２０１６またはディスク・ストレージ２０２４に格納されているプログラム・モジュール２０３２およびプログラムデータ２０３４を用いて、オペレーティング・システム２０２８によるリソースの管理を利用する。本特許請求対象は、様々なオペレーティング・システムまたはオペレーティング・システムの組合せとともに実装されることが可能であることを理解されたい。
【０１００】
ユーザが、コマンドまたは情報を、入力装置２０３６からコンピュータ２０１２に入力する。入力装置２０３６としては、マウスなどのポインティング装置、トラックボール、スタイラス、タッチパッド、キーボード、マイク、ジョイスティック、ゲームパッド、パラボラ・アンテナ、スキャナ、ＴＶチューナ・カード、デジタル・カメラ、デジタル・ビデオ・カメラ、Ｗｅｂカメラなどがあり、これらに限定されない。これらおよび他の入力装置は、インターフェース・ポート２０３８からシステム・バス２０１８を経て処理ユニット２０１４に接続される。インターフェース・ポート２０３８は、例えば、シリアル・ポート、パラレル・ポート、ゲーム・ポート、およびユニバーサル・シリアル・バス（ＵＳＢ）を含む。出力装置２０４０は、入力装置２０３６と同じタイプのポートのいくつかを使用する。したがって、例えば、ＵＳＢポートを用いて、コンピュータ２０１２に入力を与えること、およびコンピュータ２０１２から出力装置２０４０に情報を出力することが可能である。出力アダプタ２０４２が設けられているのは、出力装置２０４０の中でも特に、モニタ、スピーカ、プリンタなど、いくつかの出力装置２０４０が専用アダプタを必要とするためである。出力アダプタ２０４２としては、例えば、出力装置２０４０とシステム・バス２０１８との間の接続手段を与えるビデオ・カードやサウンド・カードなどがあり、これらに限定されない。なお、他の装置および／または装置のシステムは、リモート・コンピュータ２０４４のように、入力および出力の両方の機能を提供する。
【０１０１】
コンピュータ２０１２は、１つまたは複数のリモート・コンピュータ（リモート・コンピュータ２０４４など）との論理接続を使用して、ネットワーク環境で動作することが可能である。リモート・コンピュータ２０４４は、パーソナル・コンピュータ、サーバ、ルータ、ネットワークＰＣ、ワークステーション、マイクロ・プロセッサ・ベースの電気器具、ピア装置または他の共通ネットワークノードなどであってよく、典型的には、コンピュータ２０１２に関して説明された要素の多くまたはすべてを含む。簡潔さのために、メモリ・ストレージ装置２０４６だけを、リモート・コンピュータ２０４４とともに示した。リモート・コンピュータ２０４４は、ネットワーク・インターフェース２０４８を介してコンピュータ２０１２と論理的に接続され、物理的にはさらに、通信接続２０５０を介して接続される。ネットワーク・インターフェース２０４８は、ローカル・エリア・ネットワーク（ＬＡＮ）やワイド・エリア・ネットワーク（ＷＡＮ）のような有線および／または無線通信ネットワークを包含する。ＬＡＮテクノロジとしては、Ｆｉｂｅｒ Ｄｉｓｔｒｉｂｕｔｅｄ Ｄａｔａ Ｉｎｔｅｒｆａｃｅ（ＦＤＤＩ）、Ｃｏｐｐｅｒ Ｄｉｓｔｒｉｂｕｔｅｄ Ｄａｔａ Ｉｎｔｅｒｆａｃｅ（ＣＤＤＩ）、イーサネット（登録商標）、トークンリングなどがある。ＷＡＮテクノロジとしては、ポイントツーポイントリンク、統合サービスデジタル網（ＩＳＤＮ）およびその変形形態のような回路交換網、パケット交換網、デジタル加入者回線（ＤＳＬ）などがあり、これらに限定されない。
【０１０２】
通信接続２０５０は、ネットワーク・インターフェース２０４８をバス２０１８に接続するために用いられるハードウェア／ソフトウェアを意味する。通信接続２０５０は、説明を明確にするために、コンピュータ２０１２の内部にあるように示されているが、コンピュータ２０１２の外部にあってもよい。ネットワーク・インターフェース２０４８との接続に必要なハードウェア／ソフトウェアは、あくまで例であるが、標準の電話グレードのモデム、ケーブル・モデム、およびＤＳＬモデムを含むモデム、ＩＳＤＮアダプタ、イーサネット（登録商標）カードなどの内部装置および外部装置を含む。
【０１０３】
ここまで説明してきた内容は、本発明の例を含む。本特許請求対象の説明のために、コンポーネントまたは方法の、考えられるあらゆる組合せを説明するのはもちろん不可能であるが、当業者であれば理解されるように、本発明の、多くの別の組合せおよび並べ替えが可能である。したがって、本特許請求対象は、添付の特許請求項の趣旨および範囲に当てはまるそのような変更、修正、および変形をすべて包含するものとする。
【０１０４】
特に、前述のコンポーネント、装置、回路、システムなどによって実行される各種機能に関して、そのようなコンポーネントを記述するために用いられる用語（「手段」への言及を含む）は、特に断らない限り、構造的には開示の構造と等価でなくても、記述されたコンポーネント（例えば、機能的等価物）の指定された機能を実行し、本明細書に記載された、本特許請求対象の例示的態様の機能を実行する、任意のコンポーネントに対応するものとする。この点において、本発明は、本特許請求対象の各種方法の操作および／またはイベントを実行するためのシステムだけでなく、そのための、コンピュータで実行可能な命令を有するコンピュータ可読媒体も含むことを理解されよう。
【０１０５】
さらに、本発明の具体的な特徴が、いくつかある実施態様のうちの１つだけについて開示されているが、そのような特徴は、他の実施態様の１つまたは複数の他の特徴と組み合わせられることが可能であり、このことは、任意または特定の用途にとって望ましく、かつ有利であろう。さらに、用語「含む」（「ｉｎｃｌｕｄｅｓ」および「ｉｎｃｌｕｄｉｎｇ」）およびその変形は、詳細説明または特許請求項において用いられる限りにおいては、用語「含む、備える」（「ｃｏｍｐｒｉｓｉｎｇ」）と同様に包含的であるものとする。
【図面の簡単な説明】
【０１０６】
【図１】ユーザの目的地を決定することを容易にする例示的システムのブロック図である。
【図２】目的地を確率論的（probabilistically）に予測することに関連して利用可能な確率論的（probabilistic）グリッドおよび／または位置間経路を生成する例示的システムのブロック図である。
【図３】履歴データに基づいて目的地を予測する例示的システムのブロック図である。
【図４】オープン・ワールド・モデリングを利用して目的地を予測する例示的システムのブロック図である。
【図５】グランド・カバー・データに少なくとも部分的に基づいて予測目的地を与える例示的システムのブロック図である。
【図６】以前に訪問された場所からの４つのしきい値半径に対する、離散化された４層確率分布の一例を示す図である。
【図７】効率的な経路のデータに少なくとも部分的に基づいて目的地の予測を生成する例示的システムのブロック図である。
【図８】目的地を予測することと関連してトリップ時間を評価する例示的システムのブロック図である。
【図９】事前確率および／または尤度を組み合わせて目的地の予測を容易にすることを可能にする例示的システムのブロック図である。
【図１０】予測目的地に関連する可能性がある情報を提供する例示的システムのブロック図である。
【図１１】トリップ中に目的地を確率論的（probabilistically）に予測する例示的システムのブロック図である。
【図１２】予測目的地の生成を容易にする例示的システムのブロック図である。
【図１３】目的地を確率論的（probabilistically）に予測することを容易にする例示的方法を示す図である。
【図１４】組み合わせられることが可能な事前確率および／または尤度に基づいて予測可能な目的地に関連する情報を提供する例示的方法を示す図である。
【図１５】運転者の行動および目的地の予測のモデリングに関連する様々な態様を描いた例示的グリッドおよび対応する地図を示す図である。
【図１６】運転者の行動および目的地の予測のモデリングに関連する様々な態様を描いた例示的グリッドおよび対応する地図を示す図である。
【図１７】運転者の行動および目的地の予測のモデリングに関連する様々な態様を描いた例示的グリッドおよび対応する地図を示す図である。
【図１８】運転者の行動および目的地の予測のモデリングに関連する様々な態様を描いた例示的グリッドおよび対応する地図を示す図である。
【図１９】本特許請求対象の新規な態様を用いることが可能な例示的ネットワーキング環境を示す図である。
【図２０】本特許請求対象に従って用いられることが可能な例示的オペレーティング環境を示す図である。
【背景技術】
【０００１】
位置（location）は、個人のコンテクストの重要な要素であるとすることができる。個人の地理的位置、および個人が移動中であれば、その目的地の地理的位置には、膨大な量の情報を関連付けることが可能である。従来は、個人が、ある位置から別の位置へ移動する際には、地図をガイドとして用いるのが一般的であった。しかしながら、地図を利用するためには、現在位置から目的地まで通過（トラバース）すべき経路を、個人が識別しなければならない場合がある。さらに、そのような移動者は、一般に、現在位置または目的地に関連する情報を、口コミや個人的親交などを通じて知らされるだけである。例えば、移動者は、自分が一度も訪問したことがない場所では、ガソリン・スタンドやレストランなどの場所がわからない可能性があり、したがって、助けを求めたり、道沿いの看板に注意したりするしかない可能性がある。さらに、例えば、地図を利用する運転者は、交通渋滞に関しては、そのような情報を提供するラジオ局の放送を注意して聞くしか知る術がない可能性がある。
【０００２】
出発点から目的地までのマップを生成することをサポートするアプリケーションが、いくつも市販されている。例えば、そのようなアプリケーションは、出発地点から目的地までの経路を表示した地図だけでなく、運転方向ユーザに提供することが可能である。一例では、ユーザが出発点と終着点とを入力すると、アプリケーションは、対応する運転方向（directions）および／または（例えば、経路をハイライトした）マップ（map(s)）を生成することが可能である。これらのアプリケーションは、パーソナル・コンピュータ、ラップトップ・コンピュータ、ハンドヘルド、携帯電話などのような機器と接続して利用することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
近年、全地球測位システム（ＧＰＳ）装置の利用が広まりつつあり、これは、この装置に関連付けられた位置を識別することが可能である。例えば、ＧＰＳは、自動車の運転者に運転方向を示す自動車用ナビゲーション・システムに用いることが可能である。この例によれば、ナビゲーション・システムは、自動車の位置変化に応じて更新されるマップを表示することが可能である。さらに、ナビゲーション・システムは、自動車が移動している間、（例えば、表示、スピーカなどで）運転者に逐一指示を与えることが可能である。しかしながら、ＧＰＳ（ならびに他の従来技術）を用いた従来システムは、ユーザが目的地を直接入力しなければならないのが一般的である。例えば、一般的なＧＰＳ装置は、自動車の運転者が目的地の場所を指示しない限り、運転者に運転方向を示さない。さらに、ユーザは、移動のたびに目的地を入力するとは限らず、したがって、目的地に関連する警報および／または関連付けられた経路がユーザに提示されない場合がある。例えば、ユーザは、職場、自宅、学校などに頻繁に行く、行き先に向う場合には目的地を入力しないことがあり、その場合は、関連する警報がユーザに提示されないことになる。
【課題を解決するための手段】
【０００４】
以下では、簡単な概要が、本明細書に記載のいくつかの態様についての基本的理解が得られるように、提供される。この概要は、本特許請求対象の包括的な概説ではない。この概要は、本特許請求対象の重要な要素を示すものではなく、本特許請求対象の範囲を説明するものでもない。この概要の唯一の目的は、後で示される詳細な説明の前置きとして、いくつかの概念を簡単な形で示すことである。
【０００５】
本特許請求対象は、目的地（destination(s)）を確率論的に（probabilistically）予測することを容易にするシステムおよび／または方法に関する。ユーザ、ユーザの履歴（例えば、履歴データ）、別のユーザおよびその履歴、地理的領域の地勢図（例えば、グランド・カバー（ground cover）データ）、効率的な経路、トリップ時間分布、現在のトリップ（例えば、位置、位置変化、時刻など）、その他に関連する入力データを入手できる。これらの入力データは、任意のソース（例えば、位置特定コンポーネント、タイマ・コンポーネント、データ・ストア、インターネット、その他）から取得可能であることが予期される。予測は、１つ以上の事前確率（priors）および／または１つ以上の尤度（likelihoods）を利用して、実施することが可能である。例えば、この事前確率は、個人的な目的地（personal destinations）事前確率および／またはグランド・カバー事前確率とすることができる。さらに、この尤度は、効率的運転尤度（efficient driving likelihood）および／またはトリップ時間尤度とすることができる。１つ以上の事前確率、１つ以上の尤度、または事前確率と尤度の組合せを利用して、予測目的地（predicted destination(s)）を生成することが可能であることを理解されたい。
【０００６】
本特許請求対象の各種態様によれば、目的地推定コンポーネントが、事前確率（prior(s)）および／または尤度（likelihood(s)）に基づいて、トリップの目的地を確率論的（probabilistically）に予測することが可能である。目的地推定コンポーネントを用いて、事前確率（prior(s)）および／または尤度（likelihood(s)）を選択および／または結合することにより、予測目的地を生成することが可能である。一例によれば、ベイズ規則を利用することにより、事前確率（prior(s)）および／または尤度（likelihood(s)）の任意の組合せを目的地推定コンポーネントで用いることが可能である。
【０００７】
本特許請求対象の１つまたは複数の態様によれば、目的地推定コンポーネントは、個人的な目的地事前確率、グランド・カバー事前確率、効率的運転尤度、および／またはトリップ時間尤度を用いることが可能である。個人的な目的地事前確率は、ユーザの過去の複数の目的地からなる集合に基づくことが可能であり、したがって、履歴データを評価して個人的な目的地事前確率を生成することが可能である。例えば、個人的な目的地事前確率を取得することに関連して、オープン・ワールド・モデリング（open world modeling）および／またはクローズド・ワールド・モデリング（closed world modeling）を用いることが可能である。オープン・ワールド解析および／またはクローズド・ワールド解析を、位置予測に組み込むことが可能であり、したがって、この解析は、運転者が以前に観察されていない場所を訪問する尤度（観察範囲（observation horizon）の関数として）、新しい複数の場所、複数の所定の事前確率位置についての空間的関係、の両方についての予測を含むことが可能である。複数の人物を一定期間観察することによって、オープン・ワールド推論用のパラメータを得ることが可能であり、それを個人にマッピングすることが可能である。さらに、オープン・ワールド・モデリングにおいて、デモグラフィック情報（demographic information：人口学的情報）を考慮に入れることが可能である。さらに、グランド・カバー事前確率は、特定セルが目的地である確率を特定セル内のグランド・カバーに基づいて与えるグランド・カバー・データに基づくことが可能である。さらに、効率的運転尤度は、移動者がトリップの進行とともに到着までの時間を減らし続けると仮定できる場合には、候補目的地に到着するまでの時間の変化に基づくことが可能である。例えば、各候補目的地に関連付けられた、算出された運転効率を、最終的な位置特定の証拠として利用することが可能である。トリップ時間尤度は、トリップ時間分布および／または経過トリップ時間に基づくことが可能である。さらに別の例によれば、時刻、曜日（例えば、週末か平日か）、休日ステータス、季節、月などのようなコンテクスチュアルな特徴を、解析の一部として利用することが可能である。
【０００８】
本特許請求対象の各種態様によれば、目的地、目的地までの途上で人々が選択しそうな経路、などを識別するために、推論（reasoning）を適用することが可能である。さらに、アプリケーションが、識別された目的地および／または経路を利用して、関連情報をユーザに提示することが可能である。一例によれば、アプリケーションは、交通（traffic）、工事（construction）、前方の安全性（safety issues ahead）などについて警告メッセージを示したり、掲示されている広告を案内したり、指示（directions）、経路の助言（routing advice）、最新情報などを与えたりすることが可能である。例えば、ユーザに提示される情報は、予測目的地（predicted destination(s)）に関連するものであることが可能である。さらに、または代替として、その情報が、経路に関連付けられた場所（例えば、その経路に沿って通過する場所）に関連するものになるように、予測目的地（predicted destination(s)）への経路を評価することが可能である。このような関連情報として、例えば、交通に関連する警告メッセージ、ナビゲーション支援（navigation assistance）、イベント、目標となる広告、施設（establishments）、目立つ建造物（landmarks）などがある。関連情報は、任意の様式（例えば、音声信号、視覚情報など）で配信可能であることを理解されたい。さらに、示される関連情報は、ユーザの好みに基づいてカスタマイズされることが可能である。
【０００９】
以下の記述および添付図面は、本特許請求対象の特定の例示的態様を詳細に説明するものである。しかしながら、それらの態様は、本特許請求対象の原理を用いることが可能な様々な様式のうちのいくつかを示すものに過ぎず、本特許請求対象は、そのような態様およびそれらの等価物をすべて包含するものとする。以下の詳細な記述を添付図面と併せて考察することにより、他の利点および新規な特徴が明らかになるであろう。
【発明を実施するための最良の形態】
【００１０】
本特許請求対象について、図面を参照しながら説明する。図面全体を通して、類似の参照符号は、類似の要素を表している。以下の記述では、説明のために、多数の具体的詳細を示して、本発明が十分理解されるようにする。しかしながら、これらの具体的詳細がなくても本特許請求対象が実施可能であることは自明であろう。他の例では、本発明の説明を容易にするために、周知の構造および装置をブロック図の形式で示している。
【００１１】
本明細書で用いられる「コンポーネント」、「システム」などの用語は、コンピュータ関連のエンティティ（ハードウェア、（例えば、実行中の）ソフトウェア、および／またはファームウェア）を意味するものとする。例えば、コンポーネントは、プロセッサで実行中のプロセス、プロセッサ、オブジェクト、実行可能ファイル、プログラム、および／またはコンピュータであってよい。例えば、サーバで実行中のアプリケーションもサーバもコンポーネントであってよい。１つまたは複数のコンポーネントがプロセス内に常駐することが可能であり、コンポーネントは、１台のコンピュータに集中していても、２台以上のコンピュータに分散していても、その両方であってもよい。
【００１２】
さらに、本特許請求対象は、標準的なプログラミング手法および／または設計手法を用いて、本開示対象を実施するようにコンピュータを制御するソフトウェア、ファームウェア、ハードウェア、またはこれらの任意の組合せを実現する方法、装置、または製品として実装されることが可能である。本明細書で用いられる「製品（article of manufacture）」という用語は、任意のコンピュータ読み取り可能な装置、搬送波、または媒体からのアクセスが可能なコンピュータ・プログラムを包含するものとする。例えば、コンピュータ可読媒体としては、磁気記憶装置（例えば、ハードディスク、フロッピー（登録商標）ディスク、磁気ストリップなど）、光ディスク（例えば、コンパクト・ディスク（ＣＤ）、デジタル多用途ディスク（ＤＶＤ）など）、スマート・カード、フラッシュ・メモリ装置（例えば、カード、スティック、キー・ドライブなど）などがあるが、これらに限定されない。さらに、電子メールの送受信や、インターネットまたはローカル・エリア・ネットワーク（ＬＡＮ）のようなネットワークへのアクセスに用いられるような搬送波を用いて、コンピュータ可読な電子データを搬送することが可能であることを理解されたい。もちろん、当業者であれば理解されるように、本特許請求対象の範囲または趣旨から逸脱することなく、その構成に様々な修正を施すことが可能である。さらに、本明細書で用いられる「例示的」という用語は、例、事例、または実例として機能することを意味する。「例示的」として本明細書に記載される態様または設計は、いずれも、他の態様または設計より好ましい（あるいは、有利である）として解釈されるべきものでは必ずしもない。
【００１３】
以下、各図面を見ていく。図１は、ユーザの目的地（destination(s)）を特定することを容易にするシステム１００を示す。システム１００は、ユーザ、ユーザの履歴、地理的領域の地勢図、トリップ、効率的な経路などに関連しうる入力データを受け取るインターフェース・コンポーネント１０２を含む。インターフェース・コンポーネント１０２は、任意のソースから入力データを受け取ることが可能である。例えば、インターフェース・コンポーネント１０２は、ユーザの位置および／または位置変化を特定することを可能にする任意のコンポーネント（図示せず）から入力データを取得することが可能であり、そのようなコンポーネントとして、例えば、全地球測位システム（ＧＰＳ）、衛星ナビゲーション・システム、ＧＬＯＮＡＳＳ、Ｇａｌｉｌｅｏ、Ｅｕｒｏｐｅａｎ Ｇｅｏｓｔａｔｉｏｎａｒｙ Ｎａｖｉｇａｔｉｏｎ Ｏｖｅｒｌａｙ Ｓｙｓｔｅｍ（ＥＧＮＯＳ）、Ｂｅｉｄｏｕ、Ｄｅｃｃａ Ｎａｖｉｇａｔｏｒ Ｓｙｓｔｅｍ、通信塔間の三角測量など、をサポートするコンポーネントが挙げられる。別の例として、インターフェース・コンポーネント１０２は、ユーザが以前に行ったことがある目的地に関連付けられた入力データを（例えば、データ・ストア、ユーザ入力などから）受け取ることが可能である。さらに、あるいは、代替として、インターフェース・コンポーネント１０２は、ユーザが（例えば、現在のトリップの期間に）現時点において移動中の時間量を決定することが可能なタイマ・コンポーネント（図示せず）から入力データを取得することが可能である。さらに、インターフェース・コンポーネント１０２は、グランド・カバー・データを受け取ることが可能である。例えば、そのようなデータは、データ・ストア（図示せず）から取得可能である。インターフェース・コンポーネント１０２は、入力データをいつでも受け取ることが可能であることを理解されたい。例えば、インターフェース・コンポーネント１０２は、ユーザのトリップの進行中でも（例えば、リアルタイムで）、ユーザがトリップを開始する前でも、それ以外のときでも、入力データを取得することが可能である。
【００１４】
入力データは、インターフェース・コンポーネント１０２から目的地推定コンポーネント１０４にわたされることが可能であり、目的地推定コンポーネント１０４は、入力データを評価して目的地（destination(s)）を確率論的に（probabilistically）予測することが可能である。目的地推定コンポーネント１０４は、入力データに少なくとも部分的に基づく事前確率（prior(s)）および／または尤度（likelihood(s)）を利用して、予測目的地（predicted destination(s)）を生成することが可能である。例えば、目的地推定コンポーネント１０４は、個人的な目的地事前確率、グランド・カバー事前確率、効率的運転尤度、および／またはトリップ時間尤度を用いることが可能である。予測目的地（predicted destination(s)）を生成するために、任意の数の事前確率および／または任意の数の尤度を組み合わせて用いることが可能であることを理解されたい。一例では、目的地推定コンポーネント１０４は、トリップに関連付けられた目的地を確率論的に（probabilistically）予測する場合には、グランド・カバー事前確率のみを利用することが可能である。別の例によれば、目的地推定コンポーネント１０４は、目的地（destination(s)）を確率論的に（probabilistically）予測する場合には、個人的な目的地事前確率、グランド・カバー事前確率、効率的運転尤度、およびトリップ時間尤度を用いることが可能である。本特許請求対象は、これらの例に限定されないことを理解されたい。
【００１５】
目的地推定コンポーネント１０４は、様々なソースからのデータを評価して、移動中の個人が目指している場所を予測することが可能である。一例によれば、目的地推定コンポーネント１０４は、トリップの開始前（例えば、ユーザが自動車に乗り込んだときなど）、またはトリップ中の任意の時点で、目的地を確率論的に（probabilistically）予測することが可能である。したがって、入力データは、現在のトリップに関連するデータ（例えば、現在位置、位置変化、現在のトリップに関連付けられた任意の数の場所、現在のトリップに関連付けられた時間量など）を含むことが可能である。さらに、一例によれば、そのようなトリップが進行するにつれて、目的地推定コンポーネント１０４は、トリップからの入力データを利用して、目的地（destination(s)）の予測（prediction(s)）を動的に更新することが可能である。代替として、目的地推定コンポーネント１０４は、ユーザの現在のトリップに関連付けられた情報が含まれない入力データを解析し、それに従って、共通点のない色々な情報（例えば、グランド・カバー・データ、履歴データなど）に基づく予測を生成することが可能である。
【００１６】
図示されたように、目的地推定コンポーネント１０４は、予測目的地（predicted destination(s)）を出力することが可能である。さらに、その予測目的地（predicted destination(s)）は、目的地推定コンポーネント１０４からインターフェース・コンポーネント１０２に伝えられることが可能であり、インターフェース・コンポーネント１０２は、その目的地（destination(s)）の予測（prediction(s)）を出力することが可能であることが企図されている。予測目的地（predicted destination(s)）は、ユーザに提示されることが可能であることを理解されたい。一例によれば、予測目的地（predicted destination(s)）を表示した地図をユーザに提示することが可能である。さらに、その地図は、現在のトリップにおいて、それまでにトラバースした経路、および／または、予測目的地（predicted destination(s)）に到着するための、トリップの残りに関連付けられた方向などの情報を含むことが可能である。また、そのような地図は、目標とされた広告の情報を提示することが可能であり、そのような広告の内容は、（例えば、ユーザが、ガソリンＢよりガソリンＡを好み、ファスト・フード・レストランＤよりファスト・フード・レストランＣを好む、というような）ユーザの好みを考慮して選択的に出力されることが可能である。予測目的地（ predicted destination(s)）は、任意のタイプの可聴信号および／または可視信号を利用してユーザに提示されることが可能であることが企図されている。さらに、ユーザは、予測目的地（predicted destination(s)）に関連付けられたフィードバックを返すことが可能である（例えば、一群の予測目的地から１つの目的地を選択したり、予測目的地が正しくないことを伝えたりすることが可能である）。別の例によれば、目的地（destination(s)）の予測（prediction(s)）は、その予測（prediction(s)）を利用して、（例えば、警告として）ユーザに提示されることが可能な関連情報（例えば、近くの関心対象ポイント、場所ごとのサービス、目的地に関連付けられた気象関連情報、目的地（destination(s)）に関連付けられた交通関連情報、目標とされた広告、イベントに関連付けられた情報など）を生成することが可能な、まったく別のコンポーネント（図示せず）に送られることが可能である。
【００１７】
目的地推定コンポーネント１０４は、グランド・カバー・データ、移動者（例えば、運転者）は効率的な経路を利用するのが普通であるという事実、および／またはトリップ時間（trip times）についての測定された分布に少なくとも部分的に基づいて、可能性の高い目的地を評価することが可能である。さらに、目的地推定コンポーネント１０４は、これらの手がかり（例えば、入力データ）をベイズ規則と組み合わせて、目的地（destination(s)）を確率論的に（probabilistically）予測することが可能である。さらに、目的地推定コンポーネント１０４は、ユーザおよび／または別のユーザの以前の目的地（destination(s)）（例えば、履歴データ）を考慮することも可能である。しかしながら、本特許請求対象は、前述の例に限定されない。目的地推定コンポーネント１０４はさらに、時間とともに、ユーザに関連付けられたトレーニング・データが取得されるにつれて、精度を向上させることが可能である。別の例によれば、目的地推定コンポーネント１０４は、どんな場所でも、可能な目的地にすることが可能である。別の例によれば、目的地推定コンポーネント１０４は、可能な目的地を道路網上に限定することが可能である。これにより、多くの実際の目的地が道路上または道路のそばになるため、精度を向上させることが可能である。しかしながら、本特許請求対象は、そのようには限定されない。また、目的地推定コンポーネント１０４は、例えば、時刻、曜日（例えば、週末か平日か）、休日ステータス、季節、月などのようなコンテクスチュアルな情報を考慮することも可能である。
【００１８】
インターフェース・コンポーネント１０２は、目的地推定コンポーネント１０４とは別々であるように描かれているが、目的地推定コンポーネント１０４がインターフェース・コンポーネント１０２またはその一部を含むことも企図されている。さらに、インターフェース・コンポーネント１０２は、目的地推定コンポーネント１０４との対話を可能にするために、様々なアダプタ、コネクタ、チャネル、通信パスなどを設けることが可能である。
【００１９】
個人（例えば、運転者）の目的地についての知識は、個人の移動中（例えば、トリップ中）に有用な情報を提供するための重要なパラメータとなる可能性がある。例えば、車載ナビゲーション・システムは、運転者が移動中に遭遇することが予想される交通渋滞、ガソリン・スタンド、レストラン、その他の関心対象ポイントを、自動的に表示することが可能である。さらに、車載ナビゲーション・システムは、運転者が向かっているだいたいの地域を正確に推定できる場合には、表示する情報をインテリジェントにフィルタリングして、認識負荷（cognitive load）を軽減することが可能である。さらに、目的地について運転者に直接尋ねることが可能な場合もあるが、トリップの開始時に必ずこの情報を出すよう運転者に要求することを少なくするのが有利である。システム１００は、例えば、「運転者は、目的地までの、適度に効率的な経路を選択するものである」という直観的真実に基づいて運転の目的地を予測するアルゴリズムを利用することにより、目的地（destinations）の自動予測を可能にすることが可能である。一態様によれば、個人の移動行動（travel behavior）をモデリングすることなく（例えば、運転者の日常的な目的地（職場、自宅、学校など）について事前に知っていることを仮定することなく）、予測を生成することが可能である。しかしながら、本特許請求対象は、そのようには限定されない。この例によれば、システム１００は、新車、レンタカー、または運転者が訪問したことのない都市において利用することが可能である。
【００２０】
図２は、目的地（destination(s)）を確率論的に（probabilistically）予測することに関連して利用可能な確率論的（probabilistic）グリッドおよび／または複数の位置間の経路（route(s)）を生成するシステム２００を示す。システム２００は、入力データを取得して目的地推定コンポーネント１０４にわたすインターフェース・コンポーネント１０２を含むことが可能である。目的地推定コンポーネント１０４は、入力データに関連付けられた目的地を確率論的に（probabilistically）予測することが可能である。目的地推定コンポーネント１０４は、グリッド・コンポーネント２０２によって生成された確率論的（probabilistic）グリッド、および／または経路計画コンポーネント２０４によって生成された複数の位置間の任意の数の経路（およびこれらに関連付けられた任意のデータ）を利用して、可能性の高い目的地（destination(s)）を識別することが可能である。
【００２１】
一例によれば、グリッド・コンポーネント２０２は、地図に関連付けられることが可能な確率論的（probabilistic）グリッドを生成することが可能である。例えば、四辺形の二次元グリッド（例えば、セル）を、その四辺形（例えば、セル）が任意の実際の物理的地理的領域に関連付けられるように（例えば、１キロメートルがグリッドの各四辺形の各辺に対応するように）、地図に関連付けることが可能である。さらに、グリッド・コンポーネント２０２によって生成されたグリッドが、四辺形のセルではない（または、四辺形のセルに加えて）１つまたは複数の任意の形状（例えば、Ｍ個の辺を有する多角形（Ｍは３以上の正の整数）、円など）のセルを含むことが可能であることが企図されている。これらのセルは、離散的な位置を表すことが可能であり、任意のタイリング、サイズ、および番号に関連付けられることが可能である。これらのセルは、それぞれに一意のインデックス（例えば、ｉ＝１，２，３，．．．，Ｎ。Ｎは任意の正の整数）が割り当てられることが可能であり、目的地推定コンポーネント１０４は、ユーザがその中でトリップを終えそうな１つまたは複数のセル（例えば、目的地）を識別することが可能である。
【００２２】
目的地推定コンポーネント１０４は、各セルが目的地になる確率を算出することが可能である。例えば、Ｐ（Ｄ＝ｉ｜Ｘ＝ｘ）を評価することにより、確率を求めることが可能である。ここで、Ｄは、目的地を表すランダム変数であり、Ｘは、そこまでのトリップから観察される特徴のベクトルを表すランダム変数である。さらに、尤度および／または事前確率を利用することが可能であり、ベイズ規則を適用して、以下を与えることが可能である。
【００２３】
【数１】
【００２４】
したがって、Ｎを、グリッド内のセルの数とすることが可能であり、Ｐ（Ｄ＝ｉ）を、目的地がセルｉである事前確率とすることが可能である。この事前確率は、例えば、個人の目的地事前確率および／またはグランド・カバー事前確率を用いて算出することが可能である。さらに、Ｐ（Ｘ＝ｘ｜Ｄ＝ｉ）を、観察された測定値Ｘに基づく、セルｉが目的地である尤度とすることが可能であり、Ｘは、様々なソースから算出された地図情報であることが可能である。例えば、尤度は、効率的運転尤度および／またはトリップ時間尤度とすることができる。分母は、すべてのセルの確率を合計すると１になるように算出されることが可能な正規化係数とすることができる。
【００２５】
経路計画コンポーネント２０４は、複数のペアのセル間の経路、および／またはグリッド・コンポーネント２０２によって生成されたグリッド内の各ペアのセル間の運転時間の推定を出力することが可能である。経路計画コンポーネント２０４は、セルの各ペアのセル間のユークリッド距離および概算速度を利用して運転時間を見積もることが可能である。さらに、または代替として、経路計画コンポーネント２０４は、ペアのセルの中心点（緯度、経度）間の運転経路を計画して、より高精度の運転時間推定値を与えることが可能である。したがって、経路計画コンポーネント２０４は、セル間の道路網および速度制限に少なくとも部分的に基づいて出力を与えることが可能である。
【００２６】
図３は、グランド・カバー・データに少なくとも部分的に基づいて予測目的地（predicted destination(s)）を与えるシステム３００を示す。システム３００は、グランド・カバー・データを含むことが可能な入力データを受け取るインターフェース・コンポーネント１０２を備える。システム３００はさらに、グランド・カバー・コンポーネント３０２によって生成されたグランド・カバー事前確率に少なくとも部分的に基づいて予測目的地（predicted destination(s)）を生成することが可能な目的地推定コンポーネント１０４を含む。
【００２７】
このグランド・カバー・コンポーネント３０２は、あるセルが目的地である確率を、その特定のセルに関連付けられたグランド・カバー・データに基づいて評価することを容易にすることが可能である。グランド・カバー事前確率を、位置に関連するトポロジ（地勢学）に関連付けることが可能である。例えば、湖や海の真ん中は、運転者にとってよくある目的地とは言えず、商業地域は、永続的に氷と雪で覆われた場所よりも魅力的な目的地である。インターフェース・コンポーネント１０２は、例えば、グランド・カバー・コンポーネント３０２がアメリカ地質調査所（United States Geological Survey）（ＵＳＧＳ）グランド・カバー地図に基づいてグリッド内のセルを特徴づけることを可能にすることが可能な、グランド・カバー地図を取得することを容易にすることが可能である。しかしながら、本特許請求対象は、そのようには限定されず、任意のグランド・カバー・データを利用してセルを特徴づけることが可能であることが企図されている。例えば、ＵＳＧＳグランド・カバー地図は、米国の３０ｍ×３０ｍの各正方形を、２１の異なるタイプのグランド・カバー（例えば、挺水草本湿地帯（emergent herbaceous wetlands）、樹木湿地（woody wetlands）、果樹園、永続的な氷（perennial ice）、小穀物（small grains）、条植え作物（row crops）、岩肌（bare rock）、休閑地（fallow）、市街地（urban）、高密集度住宅地（high intensity residential）、中間形態（transitional）、採石場（quarry）、牧草地（pasture）、水域（water）、草原（grasslands）、混交林（mixed forest）、低木地（shrub land）、落葉樹林（deciduous forest）、常緑樹林（evergreen forest）、低密集度住宅地（low intensity residential）、商業地（commercial）など）の一つに分類することが可能である。グランド・カバー・コンポーネント３０２は、例えば、データセット内の各トリップ目的地の緯度および／または経度を評価して、複数のグランド・カバー・タイプ（例えば、２１のグランド・カバー・タイプ）に対する正規化ヒストグラムを作成することが可能である。水域は、一般的な目的地とは言えないが、他のいくつかのカテゴリ（例えば、挺水草本湿地、樹木湿地など）よりは一般的であり、商業地域は、氷と雪に覆われた地域よりは魅力的であろう。より一般的な目的地は、「商業地」と「低密集度住宅地」であろう。これらについて、ＵＳＧＳは、次のように記載している。
【００２８】
商業／工業／輸送（Commercial/Industrial/Transportation）−「インフラストラクチャ（例えば、道路、鉄道など）と、高密集度住宅地には分類されない、高度に発展したすべての地域とを含む。」
【００２９】
低密集度住宅地−「建造物と植物とが混在した地域を含む。建造物は、グランド・カバーの３０〜８０パーセントを占める。植物は、グランド・カバーの２０〜７０パーセントを占める。これらの地域は、一戸建て住宅（single-family housing units）を最も一般的に含む。人口密度は、高密集度住宅地より低い。」
【００３０】
「水域」カテゴリは、非ゼロの尤度に関連付けられることが可能である。これは、３０ｍ×３０ｍのＵＳＧＳ正方形の最大２５％が陸地であっても水域と分類される場合があり、正方形がどのように配置されるかによって、海辺やウォーターフロントの土地が含まれる可能性があるためである。様々な領域を、グランド・カバーの様々な混在に関連付けることが可能であること、ならびに、別の領域の居住者が、グランド・カバーのタイプに関連して、様々な行動をとる可能性があることが想定されている。
【００３１】
一例によれば、グランド・カバー・コンポーネント３０２は、目的地セルがグランド・カバー・タイプｊ（ｊ＝１，２，３，．．．，２１）によって完全に覆われている場合には、目的地セルの確率を、Ｐ（Ｄ＝ｉ｜Ｇ＝ｊ）を評価することによって決定することが可能である。一例によれば、グランド・カバー・コンポーネント３０２が１ｋｍ×１ｋｍセルの確率諭的（probabilistic）グリッドを利用する場合、各セルは、約１１１１個の３０ｍ×３０ｍグランド・カバー・ラベルを含むことが可能である（例えば、多くの場合、セルは、同じタイプのグランド・カバーで完全には覆われない）。グランド・カバー・コンポーネント３０２は、各セルについて、Ｐｉ（Ｇ＝ｊ）で表される、グランド・カバー・タイプの分布を算出することが可能である。一例として、グランド・カバー・コンポーネント３０２は、次のようにセル内のグランド・カバー・タイプを敢えて過小評価することにより、各セルの事前確率を算出することが可能である。
【００３２】
【数２】
【００３３】
ＰＧ（Ｄ＝ｉ）は、グランド・カバーに基づいて、目的地セルの事前確率に関連付けられることが可能である。したがって、グランド・カバー・コンポーネント３０２は、例えば、水域および田園地帯を、より確率が低い目的地である可能性があると判定することができる。グランド・カバー・コンポーネント３０２によって生成されたグランド・カバー事前確率（および後述されるようなユーザ履歴コンポーネントを利用して取得された個人の目的地事前確率）は、これらが、通常、ユーザの現在の運転についての測定された特性（measured features）に基づかないことから、事前確率分布を与えることができる。
【００３４】
図４は、履歴データに基づいて目的地（destination(s)）を予測するシステム４００を示す。システム４００は、入力データを受け取るインターフェース・コンポーネント１０２を含む。入力データは、例えば、履歴データを含むことが可能である。履歴データは、特定のユーザ、別のユーザ、および／または複数のユーザの集合に関連するものであることが可能である。例えば、履歴データは、ユーザの以前の目的地の集合に関連するものであることが可能である。一例として、インターフェース・コンポーネント１０２は、履歴データをデータストア（図示せず）から取得することが可能である。さらに、インターフェース・コンポーネント１０２は、履歴データを含む入力データを目的地推定コンポーネント１０４にわたすことが可能であり、目的地推定コンポーネント１０４は、そのようなデータに基づいて目的地（destination(s)）を確率論的に（probabilistically）予測する。
【００３５】
目的地推定コンポーネント１０４はさらに、履歴データを評価して個人の目的地事前確率を生成するユーザ履歴コンポーネント４０２を備えることが可能である。したがって、目的地推定コンポーネント１０４は、個人の目的地事前確率を用いて、目的地の予測を容易にすることが可能である。目的地推定コンポーネント１０４は、ユーザ履歴コンポーネント４０２を単独で用いるか、かつ／または、別の事前確率および／または１つまたは複数の尤度との組合せで用いることによって得られた個人の目的地事前確率を利用することが可能であることを理解されたい。
【００３６】
ユーザ履歴コンポーネント４０２は、運転者は、以前に行ったことがある場所に行くことが多く、そのような場所には、より高い目的地確率を与えるべきである、という直観的真実に基づくことが可能である。例えば、ユーザ履歴コンポーネント４０２は、ＧＰＳ信号が失われたことを利用して、ユーザが建物の中に入ったことを示すことが可能である。そのユーザが同じ建物に何度も入る場合、その場所は、将来の予測の候補目的地としてマーキングされることが可能である。さらに、ユーザがしきい値（例えば、１０分）を超える時間量をそこで費やした、ＧＰＳで測定された、場所をクラスタ化して、可能性の高い目的地を推論することが可能である。さらに、長く滞在した場所をクラスタ化して、目的地を推論することも可能である。また、潜在的な目的地は、目的地のサイズおよび滞在時間の規模の変化の理由を明示的に説明するとともに、推論されることもできる。
【００３７】
別の例によれば、ユーザ履歴コンポーネント４０２は、個人の目的地（personal destinations）を、セグメント化された複数のトリップの複数の終点を含むグリッド・セルとしてモデリングすることが可能である。したがって、候補目的地の空間的規模を、セルのサイズと同じにすることが可能であり、目的（destination）と見なされるべき滞在時間を、トリップ・セグメンテーション・パラメータによって決定することが可能である（例えば、５分）。
【００３８】
ユーザ履歴コンポーネント４０２は、個人の目的地データ（destinations data）に基づく、まったく別の仮定を利用することが可能である。それらは、クローズド・ワールド仮定とオープン・ワールド仮定である。ユーザ履歴コンポーネント４０２は、オープン・ワールド解析および／またはクローズド・ワールド解析を利用することが可能であり、それらの両方を位置予測に組み込むことが可能である。したがって、ユーザ履歴コンポーネント４０２によって実施される解析は、運転者が、以前に観察されていない場所を訪問する尤度（観察範囲の関数として）、および事前確率場所に対する、新しい複数の場所の空間的関係の両方についての予測を含むことが可能である。さらに、複数の人物を一定期間観察することによって、オープン・ワールド推論用のパラメータを得ることが可能であり、それを個人にマッピングすることが可能である。さらに、オープン・ワールド・モデリングにおいて、デモグラフィック情報（例えば、年齢、性別、職種、宗教、政治的所属など）を考慮に入れることが可能である。一例として、クローズド・ワールド仮定を、「運転者は、過去に訪問したことが観察されている目的地だけを訪問する」と仮定することに関連付けることが可能である。これをクローズド・ワールド仮定と呼ぶことが可能であり、対応する解析をクローズド・ワールド解析と呼ぶことが可能である。ユーザ履歴コンポーネント４０２は、クローズド・ワールド仮定を行うことにより、運転者のトリップが終了した地点を調査して、Ｎ個のセルに対するヒストグラムを作成することが可能である。正規化により、確率関数Ｐｃｌｏｓｅｄ（Ｄ＝ｉ）、（ｉ＝１，２，３，．．．，Ｎ）が与えられる。ここで、添え字のｃｌｏｓｅｄは、この確率が個人の目的地に基づくことを示している。あるセルをユーザが訪問したことが観察されていない場合は、そのセルの個人の目的地確率をゼロにすることが可能である。これは、各セルの事後目的地確率を算出するために、ベイズ計算において、この確率に、Ｎ個のセルに対する他の確率が乗じられるためである。セルがゼロ事前確率を有する場合、そのセルは、可能性のある目的地として残らない可能性がある。
【００３９】
クローズド・ワールド仮定は、「人々が、過去に訪問したことが観察されていない目的地を訪問する可能性が実際にはある」という点で、先入的知識がない（naive）。このケースは、一般であるが、新しい目的地についてのそのような観察は、特に、運転者の観察の早い段階において顕著である可能性がある。上記の「新しい」場所は、運転者にとってまったく新しい目的地だけでなく、運転者が以前に訪問していても、調査（例えば、ユーザの観察／追跡）の過程の間に訪問したことが観察されていない場所も含む。したがって、運転者の目的地の確率を推論する方法として、より精度が高くなる可能性があるのは、まだ見たことがない目的地を見る尤度を考慮すること、したがって、「オープン・ワールド」モデルを活用することであると考えられる。この作用をモデリングすることにより、調査（例えば、運転者の観察）の早い時点で取得されるクローズド・ワールド確率関数を、調査終了時以降に観察されることが可能な定常状態確率の概算値に変換することが可能である。次に、このオープン・ワールド・モデルがＰｃｌｏｓｅｄ（Ｄ＝ｉ）に取って代わり、対象が訪問しそうな場所の、より高精度のモデルを生成することが可能である。
【００４０】
図５は、オープン・ワールド・モデリングを利用して目的地を予測するシステム５００を示す。システム５００は、インターフェース・コンポーネント１０２および目的地推定コンポーネント１０４を含む。さらに、目的地推定コンポーネント１０４は、取得された入力データに含まれる履歴データを評価するユーザ履歴コンポーネント４０２を含む。ユーザ履歴コンポーネント４０２はさらに、まだ観察されていない新しい目的地（例えば、履歴データの一部として含まれていない目的地）の尤度および位置を明示的に考慮するオープン・ワールド・モデリング・コンポーネント５０２を含む。
【００４１】
オープン・ワールド・モデリング・コンポーネント５０２は、未訪問の場所を様々な様式でモデリングすることが可能である。例えば、目的地がクラスタ化しそうだという観察に基づいて、オープン・ワールド・モデリング・コンポーネント５０２を用いて未訪問の場所をモデリングすることが可能である。一例として、運転者は、時間を節約するために、互いに近くにある複数の場所に行く傾向があるかもしれない。あるいは、運転者は、自分になじみのある地域ばかりに行く傾向があるかもしれない。例えば、職場の近くにあるガソリン・スタンドや食料雑貨店を選択するかもしれない。オープン・ワールド・モデリング・コンポーネント５０２は、この作用を、以前に訪問された地点からの距離に対する離散化確率分布（discretized probability distribution）としてモデリングすることが可能である。この分布は、図６に示されるような、段を付けたウェディング・ケーキのような全体形状を有することが可能である（図６は、以前に訪問された場所の周囲の４つのしきい値半径に対する、離散化された４層確率分布６００の一例を示す）。各層は、以前に訪問された目的地の周辺の新しい目的地の確率を与えることが可能である。ウェディング・ケーキの各層は、中心からのいくつかの半径における一定確率の同心環とすることが可能であり、定常状態における目的地の最終的なクラスタ化をモデリングすることを意図したものである。
【００４２】
別の例によれば、図５において、オープン・ワールド・モデリング・コンポーネント５０２は、各対象のＧＰＳ調査の、まったく異なる日々におけるグリッド上の目的地の正規化ヒストグラムを調べることにより、クラスタ化傾向を測定することが可能である。ある日の各目的地について、その目的地のまわりの１０層ウェディング・ケーキの各環の最終的な定常状態において、まだ訪問されていない目的地が現れる確率を算出することが可能である。各環は、幅１キロメートル、中心半径ｒ＝｛１，２，．．，１０｝キロメートルの環であることが可能であり、定常状態は、全調査期間にわたって訪問されたすべての目的地から取得されることが可能である。調査の初日では、訪問済みの目的地の近くで未訪問の定常状態の目的地が見つかる確率は、比較的高い可能性がある。日が経つにつれ、各対象が徐々に、それぞれの日常的な目的地のほとんどを訪問するため、上記確率は下がる。一日ごとに、中心近くの層が、外側エッジ近くの層より高くなる。操作的には、所与の日からの所与のクローズド・ワールド確率Ｐｃｌｏｓｅｄ（Ｄ＝ｉ）に対し、しかるべき日の確率値を有するウェディング・ケーキに置き換えられた、各非ゼロＰｃｌｏｓｅｄ（Ｄ＝ｉ）の未訪問の近隣地の別の確率を算出することが可能である。これにより、定常状態の予想される広がりを（spread）シミュレーションが可能である。１に正規化された後のウェディング・ケーキを、Ｗ（Ｄ＝ｉ）とする。これは、各対象ごとに別々に行われることが可能である。
【００４３】
定常状態の目的地はクラスタ化する傾向があるが、孤立した目的地もありうる。この作用は、定常状態の目的地が、定常状態の前に訪問された目的地のまわりの１０層ウェディング・ケーキによって覆われない確率を算出することによって特徴づけられることが可能である。この確率を、βとする。新しい、孤立した目的地の確率は、時間とともに低下する可能性がある。この背景確率（background probability）をモデリングする１つの方法は、全グリッド・セルにわたる均一分布を用いる方法である。しかしながら、これは、湖の真ん中のような誰も行かない場所に確率を与える可能性がある。オープン・ワールド・モデリング・コンポーネント５０２は、均一分布の代わりに、背景をＰＧ（Ｄ＝ｉ）として用いることが可能である。これは、既述のグランド・カバー事前確率である。
【００４４】
これらの作用を組み合わせて、定常状態の確率をより高い精度でモデリングする、目的地の確率分布を算出することが可能である。それら３つの成分は、クローズド・ワールド事前確率Ｐｃｌｏｓｅｄ（Ｄ＝ｉ）、前述のウェディング・ケーキ形状の分布Ｗ（Ｄ＝ｉ）で表される、パラメータ化された広がり、および孤立した目的地をモデリングする背景確率ＰＧ（Ｄ＝ｉ）である。全確率のうちの、Ｗ（Ｄ＝ｉ）に対する割合αを配分することが可能である。ここで、αは、該当する日の各層の合計である。ユーザが層状分布の先にある場所に移動する確率を取り込む、確率の学習された割合βが、背景（background）に割り当てられる。したがって、運転者の目的地の確率に対するオープン・ワールドのバージョンは、事前確率であって、次のように計算される。
Ｐｏｐｅｎ（Ｄ＝ｉ）＝（１−α−β）Ｐｃｌｏｓｅｄ（Ｄ＝ｉ）＋αＷ（Ｄ＝ｉ）＋βＰＧ（Ｄ＝ｉ）
これを、オープン・ワールド事前確率分布と呼ぶ。さらに、オープン・ワールド・モデリング・コンポーネント５０２は、これをベイズ公式で利用することが可能である。
【００４５】
時間の経過とともに、αおよびβは減少する傾向があり、それによって、各対象の実際の学習された目的地を優先する形で、クラスタ化および背景確率の調整分の効果を重視しなくなる。このことは、人が新しい場所を（特に観察期間の早い時期に、あるいは長時間運転において）訪問する可能性があるという事実を適切に考慮するオープン・ワールド・モデルの豊かさ（richness）を示している。
【００４６】
オープン・ワールド事前確率分布Ｐｏｐｅｎ（Ｄ＝ｉ）は、先入的知識がない（naive）クローズド・ワールド事前確率Ｐｃｌｏｓｅｄ（Ｄ＝ｉ）よりも良好に、対象の目的地の定常状態分布を概算することが可能である。さらに、オープン・ワールド事前確率は、クローズドワールドモデルの場合よりも、実際の定常状態にずっと近い事前確率で動作することが可能である。
【００４７】
図７は、効率的な経路のデータに少なくとも部分的に基づいて目的地の予測を生成するシステム７００を示す。システム７００は、入力データを取得することが可能なインターフェース・コンポーネント１０２を含む。入力データは、経路計画コンポーネント（例えば、図２の経路計画コンポーネント２０４）などによって生成され、データ・ストア（図示せず）に格納可能な、効率的な経路のデータを含むことが可能である。さらに、または代替として、インターフェース・コンポーネント１０２は、ユーザの現在のトリップに関連付けられたデータ（例えば、位置に関連するデータ、位置変化、トリップの所要時間など）を取得することが可能である。入力データは、目的地推定コンポーネント１０４によって評価されることが可能であり、目的地推定コンポーネント１０４はさらに、効率コンポーネント７０２を備えることが可能である。したがって、目的地推定コンポーネント１０４は、効率コンポーネント７０２によって提供される効率的運転尤度に基づいて、予測目的地を生成することが可能である。効率コンポーネント７０２は、最終的な位置／目的地についての根拠として、候補目的地の集合（例えば、各候補目的地）に関連付けられた運転効率を算出することが可能であり、これを、目的地推定コンポーネント１０４が利用することが可能である。
【００４８】
効率コンポーネント７０２によって生成される効率的運転尤度は、候補目的地に到着するまでの時間変化に基づくことが可能である。例えば、効率的運転尤度は、ユーザの現在のトリップに基づくことが可能である。効率的運転尤度（ならびに他の任意の尤度）は、Ｐ（Ｘ＝ｘ｜Ｄ＝ｉ）の形式とすることができる（ｘは、現在のトリップの何らかの測定される特徴である）。効率的運転尤度に関連付けられた、測定される特徴は、運転者が既にトラバースしたセルのリストとすることができ、この効率的運転尤度の背後の直観的真実は、一般に運転者は、目的地へ効率的な態様で到着する機会を逃さない、ということとすることができる。
【００４９】
効率コンポーネント７０２は、運転者の経路上の地点と候補目的地との間の運転時間を用いて効率を定量化することが可能である。したがって、効率コンポーネント７０２は、確率論的（probabilistic）グリッド内のセルの各ペア（ｉ，ｊ）について、それらのセルの間の運転時間Ｔｉ，ｊを推定するか、かつ／または、効率的な経路のデータの一部として推定を受け取ることが可能である。一例によれば、効率コンポーネント７０２が、各ペアのセル間の単純なユークリッド距離および速度概算値を利用して、運転時間の第１の近似値を生成することが可能である。さらに、または代替として、効率コンポーネント７０２は、デスクトップ・マッピング・ソフトウェアを用いて、各ペアのセルの中心点（緯度、経度）間の運転経路を計画することが可能である。このマッピング・ソフトウェアは、計画された経路の推定運転時間を与えることが可能なプログラマチック・インターフェースを提供することが可能である。運転経路プランナを用いることにより、セル間の道路網および速度制限の明細が明らかになり、より精度の高い運転時間推定値が得られる。Ｎ個のセルの場合、同一セルのペアを除き、Ｎ（Ｎ−１）個の異なる順序ペアが存在することができる。さらに、セルｉからセルｊまでの移動時間が、セルｊからセルｉまでと同じである（すなわち、Ｔｉ，ｊ＝Ｔｊ，ｉ）と仮定することによって、経路を計画することが可能である。なお、この計算は、個々のグリッドについて一度実行するだけでよい場合がある。
【００５０】
効率コンポーネント７０２は、運転者が目的地に早く到着できる機会を逃さない、と仮定することが可能である。例えば、運転者がトリップ中のある時点で目的地の近くまで来た場合、その後、目的地から離れるように運転する可能性は低い。言い換えると、トリップが進行するにつれて、目的地に到着することに関連付けられた時間は、単調に減少しうると予想することが可能である。一例によれば、効率コンポーネント７０２は、トリップデータを用いてこの過程を検証することを可能にする。この例によれば、各トリップを、トラバースされたセルの（隣接する繰り返しセルがない）シーケンスに変換し、各シーケンスを、一度に１セルずつ検証することが可能である。各シーケンスを検証しながら、これまでトラバースされたセルを通る、目的地セルまでの最短時間を追跡することが可能である。効率的な経路であれば、シーケンスが進むにつれて、この最短時間を減らすことが可能である。シーケンス内のセル間の遷移ごとに、Δｔを算出することが可能である（Δｔは、これまでに発生した、目的地までの最短時間を経て新しいセルに遷移することによって達成される、推定運転時間の変化であることが可能である）。Δｔは負であることが可能であり、したがって、セル間遷移によって、目的地までの時間を減らすことが可能である。
【００５１】
Δｔの正規化ヒストグラムは、Ｐ（ΔＴ＝Δｔ）の推定値であることが可能であり、運転者がそれまでに目的地に最も近づいた場合を基準に、運転者が次のセルに遷移することによって引き起こされるトリップ時間の変化の確率を与える。運転者が目的地までの最短時間を減らす確率は、例えば、
【００５２】
【数３】
【００５３】
になる。この例によれば、１−ｐ＝０．３７５、すなわち、この時間の３７．５％では、運転者が新しいセルに移動することによって、目的地までの時間が実際には増えたことになる。しかしながら、この数値は、経路プランナが持つことのできない、運転者の特別な知識（近道、道路網の変化、交通状態など）のために、見かけ上高くなる場合がある。さらに、空間を離散化することは、セルからセルへの経路が、セルの中心がどこになるかに応じて、運転者が通過するだけであれば、そうせざるを得ないい高速道路の入口および出口を考慮に入れなければならないことを意味する。Ｐ（ΔＴ＝Δｔ）の平均値および中央値は、それぞれ、−２２．２秒および−３９．０秒である。したがって、平均では、データは、運転者が、大まかには、グリッド内の新しいセルに遷移するたびに目的地に向かって進んでいることを示していると言える。
【００５４】
効率コンポーネント７０２は、ＰＥ（Ｓ＝ｓ｜Ｄ＝ｉ）を算出することが可能である。これは、Ｓ、これまでのトリップ、所定の目的地の確率である。このトリップＳは、これまでにトラバースされたセルの（隣接する繰り返しを含まない）系列Ｓ＝｛ｓ１，ｓ２，ｓ３，．．．，ｓｎ｝として表される。各セルｓｊにおいて、運転者は、次にどのセルに行くかを、他に依存せずに決定すると仮定することが可能である。これは、この尤度が次のように計算できることを意味する。
【００５５】
【数４】
【００５６】
ここで、ｎは、そのトリップでこれまでにトラバースされたグリッド・セルの数である。この式では、新しいセルが以前のどのセルよりも目的地ｉに近い場合（これは、運転者がセルｉまでの推定時間を減らす動きをしたことを表す）にｐを乗じ、それ以外の場合は、１−ｐを乗じる。ｐ＞０．５である限り、この尤度は、運転者が向かっているセルを優先する。
【００５７】
この尤度および均一事前確率を利用して、事後分布を、効率コンポーネント７０２を使用して取得することが可能である。例えば、トリップが特定の位置から特定の方向（例えば、南）に開始される場合は、目的地としては除外してよいセルがある（例えば、北に向かうセルは、目的地としては除外してよい）。この場合は、例えば、目的地の確率を地図上に描くことが可能である。さらに南へ移動した後は、南側部分を除くすべてを除外することが可能である。
【００５８】
一例によれば、運転者は、本当の目的地が近くなったとき（例えば、トリップの終了時）にくらべ、トリップの開始時には、よりランダムな、とりとめのない（meandering）走行をする可能性がある。したがって、各時間ステップにおける、運転者が最終目的地に近づく確率ｐは、トリップの経過時間に応じて変化する可能性がある。したがって、ｐは、トリップの終了時より開始時のほうが低い可能性がある。
【００５９】
別の例によれば、効率コンポーネント７０２は、トリップの開始セルｓと候補目的地セルｉとに基づいて効率を測定することが可能である。運転者の経路が効率的であれば、これら２つのセルの間を行く全所要時間は約Ｔｓ，ｉであるはずである。運転者が現在セルｊにいる場合、候補目的地ｉに到着するまでの時間は約Ｔｊ，ｉであるはずである。ｉが本当に目的地であって、運転者が効率的な経路をたどっているとすれば、運転者は、時間Ｔｓ，ｉ−Ｔｊ，ｉで現在のセルｊに到着したはずである。運転者が効率的でない経路をとっているとすれば、運転者の、この地点までの実際のトリップ時間Δｔは、Ｔｓ，ｉ−Ｔｊ，ｉより長くなる。したがって、効率コンポーネント７０２は、効率を、次式のように、運転者が候補目的地に向かって移動することに費やすべきだった時間を、実際に発生した時間で割った比として測定することが可能である。
【００６０】
【数５】
【００６１】
そのような比は、ｓとｉとの間の効率的なトリップの場合には約１であることが期待される。ＧＰＳ調査データを用いれば、効率値の分布は、既知のトリップとそれらの対応する目的地とに基づいて算出されることが可能である。効率尤度ＰＥ（Ｅ＝ｅ｜Ｄ＝ｉ）は、運転者が目的地への途上で実際に生み出す効率を表す。候補目的地が低尤度の効率を呈した場合、その事後確率は、ＰＥ（Ｅ＝ｅ｜Ｄ＝ｉ）がベイズ規則に組み込まれたときに、対応して低くなる可能性がある。効率の尤度は、トリップの一部分に応じて変化する可能性がある。したがって、そのようなトリップの開始時近辺の分布は、短いトリップに対して正確な移動時間を与えることができないために非現実的なものになる可能性がある。運転者によっては、すべてのトリップ部分に対し、スピードを出すか、理想的トリップ時間推定値の間違いによって、効率が１．０より高くなる可能性がある。目的地の予測にこの尤度を用いる効果は、運転者が候補目的地から離れつつあるように見える場合に、その目的地の確率が低くなる、ということである。
【００６２】
図８は、目的地を予測することと関連してトリップ時間を評価するシステム８００を示す。システム８００は、入力データを取得するインターフェース・コンポーネント１０２と、入力データを評価して予測目的地を生成する目的地推定コンポーネント１０４とを含む。目的地推定コンポーネント１０４はさらに、候補目的地までの推定時間および／または現在のトリップに関連する経過トリップ時間に関連付けられた尤度を評価するトリップ時間コンポーネント８０２を含むことが可能である。
【００６３】
トリップ時間コンポーネント８０２は、入力データの一部として含まれることが可能なトリップ時間分布データに少なくとも部分的に基づいてトリップ時間尤度を生成することが可能である。例えば、トリップ時間分布データは、全米世帯移動調査（National Household Transportation Survey）（ＮＨＴＳ）から得られるが、本特許請求対象はそのように限定されない。一例として、２００１年からのＮＨＴＳは、全米の約６６０００世帯からの、日常の移動および／または長距離旅行に関するデータを含む。さらに、調査結果はＷｅｂインターフェースからも利用可能であり、トリップ時間のヒストグラムを生成することが可能である。
【００６４】
トリップ時間を支配する尤度は、ＰＴ（ＴＳ＝ｔｓ｜Ｄ＝ｉ）である（ＴＳは、これまでのトリップ時間を表すランダム変数である）ことが可能である。この尤度を用いるために、トリップ時間コンポーネント８０２は、ヒストグラムに関連付けられたビンに従ってトリップ時間を量子化することが可能である。ヒストグラムは、トリップの開始前の目的地時間の分布（例えば、Ｐ（ＴＤ＝ｔＤ）（ＴＤは全トリップ時間を表す））を表すことが可能である。トリップにおいて一定時間が経過すると、経過した時間帯の確率はゼロになり、次式を与える正規化を行うことが可能である。
【００６５】
【数６】
【００６６】
候補目的地についての尤度を算出するために、ｔＳを、これまでのトリップの長さとし、ｔＤを、Ｔｉ，ｊの推定トリップ時間に基づく、現在のセルから候補目的地までの推定時間とすることができる。この尤度および／または均一事前確率を利用して、事後分布を取得することが可能である。
【００６７】
図９は、事前確率および／または尤度を組み合わせて目的地の予測を容易にすることを可能にするシステム９００を示す。システム９００は、入力データを取得することが可能なインターフェース・コンポーネント１０２を含む。さらに、システム９００は、事前確率および／または尤度を用いて目的地を確率論的に（probabilistically）予測する目的地推定コンポーネント１０４を含む。目的地推定コンポーネント１０４はさらに、個人の目的地事前確率を生成するユーザ履歴コンポーネント４０２、グランド・カバー事前確率を生成するグランド・カバー・コンポーネント３０２、効率的運転尤度を提供する効率コンポーネント７０２、および／またはトリップ時間尤度を生成するトリップ時間コンポーネント８０２を備えることが可能である。
【００６８】
目的地推定コンポーネント１０４はさらに、目的地を確率論的に（probabilistically）予測することに関連して利用する事前確率および／または尤度を選択することを可能にする融合（fusing）コンポーネント９０２と結合されることが可能である。融合コンポーネント９０２は、選択された事前確率および／または尤度を組み合わせることが可能である。例えば、融合コンポーネント９０２は、選択された事前確率および／または尤度に関連付けられた１つの確率分布を生成することが可能である。一例として、個人の目的地事前確率が選択されることが可能であり、したがって、融合コンポーネント９０２は、個人の目的地事前確率に基づく確率分布を生成することが可能である。別の例によれば、グランド・カバー事前確率、効率的運転尤度、およびトリップ時間尤度が選択されることが可能であり、したがって、融合コンポーネント９０２は、これらの選択された事前確率および尤度を組み合わせることが可能である。本特許請求対象は、これらの例に限定されないことを理解されたい。
【００６９】
融合コンポーネント９０２は、目的地に対して、効率的運転尤度およびトリップ時間尤度の独立性を仮定することが可能であり、各目的地について、ベイズ規則を用いて、これら２つの要素と事前確率とを組み合わせて、１つの事後確率にすることが可能である。したがって、目的地の確率は次のようになる。
【００７０】
【数７】
【００７１】
そのような独立性を考慮することを、ベイジアン更新のナイーブ・ベイズ公式化（naive Bayes formulation）と呼ぶ。独立性の仮定を緩めて、より濃密な確率論的（probabilistic）依存性を可能にすることにより、予測の精度を高めることが可能である。これは、現実的な依存性を導入することによって、確率論的（probabilistic）影響の「過大評価」が最小限に抑えられるためである。この場合は、運転効率とトリップ時間との関係を考慮することができない。さらに、上述の目的地の確率の式の評価は、確率論的（probabilistic）成分のそれぞれについてスカラのグリッドを計算し、対応するセルのスカラ同士を掛け合わせ、正規化して積の合計を１にすることによって行われることが可能である。
【００７２】
目的地予測の確率論的（probabilistic）公式化は、運転者の真の目的地の不確定性を、首尾一貫した様式で表すことが可能であることを意味する。したがって、目的地推定コンポーネント１０４のようなシステムに構築されたアプリケーションは、運転者の目的地の避けがたい不確定性を明らかにすることが可能である。例えば、運転者の目的地の近くのレストランまたはガソリン・スタンドを示すアプリケーションは、目的地がより確定するにつれて、徐々に、より詳細を表示し、より狭い範囲を表示することが可能であろう。交通の問題に関する警告は、その問題に遭遇する確実性が特定のしきい値を超えるまで抑えられることが可能である。認識力が弱まって、意図した目的地からずれている人々に対しては、ずれがほぼ確定した場合のみ警告することが可能である。
【００７３】
図１０は、予測目的地に関連する可能性がある情報を提供するシステム１０００を示す。システム１０００は、入力データを受け取るインターフェース・コンポーネント１０２と、入力データに基づいて目的地を確率論的に（probabilistically）予測する目的地推定コンポーネント１０４とを含む。例えば、目的地推定コンポーネント１０４は、１つ以上の事前確率および／または１つ以上の尤度を利用して予測を生成することが可能である。予測目的地はさらに、コンテンツ・コンポーネント１００２に伝えられることが可能である。コンテンツ・コンポーネント１００２は、予測目的地に関連付けられた関連情報を提供する。例えば、コンテンツ・コンポーネント１００２は、交通（traffic）、工事（construction）、前方の安全性の問題(safety issues ahead）などについて警告メッセージを示したり、掲示されている広告を案内したり、指示（directions）、経路の助言（routing advice）、最新情報などを与えたりすることが可能である。
【００７４】
コンテンツ・コンポーネント１００２は、予測目的地に関連する任意の情報を提供することが可能である。例えば、コンテンツ・コンポーネント１００２は、レストラン、交通、ナビゲーション支援、ガソリン・スタンド、目立つ建造物、小売店などに関連する情報を生成することが可能である。一例によれば、特定の目的地を、コンテンツ・コンポーネント１００２に伝えることが可能である。この例によれば、コンテンツ・コンポーネント１００２は、特定の場所に関連付けられた情報および／または現在位置と目的地との間の経路のそばの任意の場所に関連付けられた情報を含む警告を出力することが可能である。したがって、コンテンツ・コンポーネント１００２は、ある場所でイベントが行われていることや、交通が混雑していることなどを示すことが可能である。別の例によれば、コンテンツ・コンポーネント１００２は、目的地および／または経路付近に位置する商店に関連付けられた広告情報を提供することが可能である。別の例によれば、ユーザが迷ったと思われる場合に、コンテンツ・コンポーネント１００２が警告を出力して、ユーザが、予測目的地までの正しい経路をたどり続けることができるようにすることが可能である。
【００７５】
コンテンツ・コンポーネント１００２は、コンテンツ・コンポーネント１００２から提供される関連情報を、ユーザ関連設定に基づいて特定ユーザに適合させるカスタマイズ・コンポーネント１００４を含むことが可能である。例えば、ユーザ関連設定は、ユーザが広告を一切受け取らないことを望んでいることを示している場合があり、その場合は、カスタマイズ・コンポーネント１００４が、そのような関連情報の送信を低減することが可能である。別の例によれば、ユーザが、目的地までの経路沿いにおけるすべての交通事故について通知されることを望んでいる場合があり、その場合、カスタマイズ・コンポーネント１００４は、コンテンツ・コンポーネント１００２がそのような情報を提供することを可能にすること、および／または交通関連情報を、コンテンツ・コンポーネント１００２から提供されるそれ以外の情報より優先することが可能である。本特許請求対象は、前述の例に限定されないことを理解されたい。
【００７６】
図１１は、トリップ中に目的地を確率論的に（probabilistically）予測するシステム１１００を示す。システム１１００は、インターフェース・コンポーネント１０２および目的地推定コンポーネント１０４を含む。さらに、システム１１００は、ユーザおよび／または端末の現在位置および／または位置変化を識別する位置特定コンポーネント１１０２を含む。例えば、位置特定コンポーネント１１０２は、ＧＰＳ、衛星ナビゲーション・システム、ＧＬＯＮＡＳＳ、Ｇａｌｉｌｅｏ、Ｅｕｒｏｐｅａｎ Ｇｅｏｓｔａｔｉｏｎａｒｙ Ｎａｖｉｇａｔｉｏｎ Ｏｖｅｒｌａｙ Ｓｙｓｔｅｍ（ＥＧＮＯＳ）、Ｂｅｉｄｏｕ、Ｄｅｃｃａ Ｎａｖｉｇａｔｏｒ Ｓｙｓｔｅｍ、通信塔間の三角測量などに関連付けられることが可能である。位置特定コンポーネント１１０２は、位置関連データをインターフェース・コンポーネント１０２に提供して、さらなる評価を可能にすることが可能である。
【００７７】
システム１１００はさらに、時間関連データをインターフェース・コンポーネント１０２に提供するタイマ・コンポーネント１１０４を含むことが可能である。タイマ・コンポーネント１１０４は、例えば、現在のトリップに関連付けられた時間量、動きがほとんどまたはまったくないことに関連付けられた時間量などを含む時間関連データを提供することが可能である。さらに、位置特定コンポーネント１１０２およびタイマ・コンポーネント１１０４は別々のコンポーネントとして図示されているが、両者が一体型のコンポーネントであってよいことも企図されている。
【００７８】
インターフェース・コンポーネント１０２は、データ・ストア１１０６と結合されていてもよい。データ・ストア１１０６は、例えば、ユーザ、ユーザの履歴、地理的領域の地勢図、トリップ、効率的な経路などに関連するデータを含むことが可能である。さらに、位置特定コンポーネント１１０２から提供される位置関連データおよび／またはタイマ・コンポーネント１１０４から取得される時間関連データを、データ・ストア１１０６に格納することが可能である。データ・ストア１１０６は、例えば、揮発性メモリまたは不揮発性メモリであってよく、あるいは、揮発性メモリおよび不揮発性メモリの両方を含んでもよい。限定ではなく例として、不揮発性メモリとしては、読み出し専用メモリ（ＲＯＭ）、書き込み可能ＲＯＭ（ＰＲＯＭ）、電気的書き込み可能ＲＯＭ（ＥＰＲＯＭ）、電気的消去可能書き込み可能ＲＯＭ（ＥＥＰＲＯＭ）、フラッシュ・メモリなどがある。揮発性メモリとしては、ランダム・アクセス・メモリ（ＲＡＭ）があり、これは外部キャッシュ・メモリとして動作する。ＲＡＭは、様々な形式で使用可能であり、限定ではなく例として、スタティックＲＡＭ（ＳＲＡＭ）、ダイナミックＲＡＭ（ＤＲＡＭ）、シンクロナスＤＲＡＭ（ＳＤＲＡＭ）、ダブル・データ・レートＳＤＲＡＭ（ＤＤＲ ＳＤＲＡＭ）、エンハンストＳＤＲＡＭ（ＥＳＤＲＡＭ）、シンクリンクＤＲＡＭ（ＳＬＤＲＡＭ）、ランバス・ダイレクトＲＡＭ（ＲＤＲＡＭ）、ダイレクト・ランバス・ダイナミックＲＡＭ（ＤＲＤＲＡＭ）、ランバス・ダイナミックＲＡＭ（ＲＤＲＡＭ）などの形式で使用可能である。本対象のシステムおよび方法のデータ・ストア１１０６は、これらのメモリおよび他の任意の好適なタイプのメモリを備えること、およびそれらに限定されないことを意図している。さらに、データ・ストア１１０６は、サーバ、データベース、ハード・ドライブなどであってよいことを理解されたい。
【００７９】
さらに、目的地推定コンポーネント１０４は、実時間トリップ・コンポーネント１１０８を含むことが可能であり、実時間トリップ・コンポーネント１１０８は、現在のトリップに関連付けられたデータを利用して、目的地を確率論的に（probabilistically）予測することが可能である。しかしながら、予測目的地の生成にはそのようなデータを利用する必要がないことも企図されている。例えば、実時間トリップ・コンポーネント１１０８は、位置特定コンポーネント１１０２から提供されることが可能な、特定のトリップに関連付けられた位置データを組み合わせることが可能である。組み合わせられた位置データは、予測の生成に利用されることが可能である。
【００８０】
図１２は、予測目的地の生成を容易にするシステム１２００を示す。システム１２００は、インターフェース・コンポーネント１０２および目的地推定コンポーネント１０４を含むことが可能であり、これらは前述のそれぞれのコンポーネントと実質的に同様であってよい。システム１２００はさらに、インテリジェント・コンポーネント１２０２を含むことが可能である。インテリジェント・コンポーネント１２０２は、入力データに関連付けられた目的地の予測を容易にするために目的地推定コンポーネント１０４によって利用されることが可能である。例えば、インテリジェント・コンポーネント１２０２は、ユーザが予測目的地へのトラバースに近道を用いたことを識別することが可能である。したがって、識別された近道は、記憶され、かつ／または将来の目的地を評価することに関連して利用されることが可能である。別の例によれば、インテリジェント・コンポーネント１２０２は、（例えば、現在の組合せにくらべて）より精度の高い目的地予測を生成できる事前確率および／または尤度の組合せ（あるいは、１つの事前確率または１つの尤度）を決定することが可能である。その後、目的地推定コンポーネント１０４は、インテリジェント・コンポーネント１２０２によって識別された組合せを用いることが可能である。
【００８１】
インテリジェント・コンポーネント１２０２は、イベントおよび／またはデータの形で取り込まれた観察結果の集合から、システム、環境、および／またはユーザの状態についての推論に必要なものを供給することが可能であることを理解されたい。例えば、推論は、特定のコンテクストまたはアクションを識別するために用いられることが可能であり、あるいは、各状態に対する確率分布を生成することが可能である。推論は、確率論的（probabilistic）であることが可能である。すなわち、データおよびイベントの考慮に基づく、関心対象の各状態に対する確率分布の算出であることが可能である。推論はまた、イベントおよび／またはデータの集合から、より高レベルのイベントを構成するために用いられる手法を指すことも可能である。そのような推論は、観察されたイベントおよび／または記憶されたイベントデータの集合から新しいイベントまたはアクションを構築することにつながる。それらのイベントは、時間的に近いもの同士が互いに関連していてもいなくてもよく、また、それらのイベントおよびデータが由来するイベントおよびデータ・ソースは１つであっても複数であってもよい。本特許請求対象に関連して自動的な、かつ／または推論されたアクションを実行することに関連して、様々な（明示的かつ／または暗黙的にトレーニングされる）分類スキームおよび／またはシステム（例えば、サポート・ベクトル・マシン、ニューラル・ネットワーク、エキスパート・システム、ベイジアン信念ネットワーク、ファジーロジック、データ・フュージョン・エンジンなど）を用いることが可能である。
【００８２】
分類子（classifier）は、入力属性ベクトルｘ＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘｎ）を、入力がクラスに属するという確実性（confidence）にマッピングする関数、すなわち、ｆ（ｘ）＝ｃｏｎｆｉｄｅｎｃｅ（ｃｌａｓｓ）である。そのような分類は、確率論的（probabilistic）および／または統計に基づく解析（例えば、解析ユーティリティおよびコストに分解する解析）を用いて、自動的に実行されることをユーザが望むアクションを予測または推定することが可能である。サポート・ベクトル・マシン（ＳＶＭ）は、使用することが可能な分類子の一例である。ＳＶＭは、可能な入力の空間における超曲面（hypersurface）を見つけることによって動作し、この超曲面は、トリガ基準を非トリガ・イベントから分離しようとする。これは、直観的には、トレーニング・データの近くにあってトレーニング・データと同一ではないデータを検査する場合に、分類を正しいものにする。他の有向および非有向のモデル分類手法としては、例えば、ナイーブ・ベイズ（naive Bayes）、ベイジアン・ネットワーク、決定木、ニューラル・ネットワーク、ファジー・ロジック・モデルを含み、様々なパターンの独立性を提供する確率論的（probabilistic）分類モデルを用いることができる。本明細書で用いられる「分類」には、優先度モデルを開発することに利用される統計的回帰も含まれる。
【００８３】
プレゼンテーション・コンポーネント１２０４は、様々なタイプのユーザ・インターフェースを提供して、ユーザと、目的地推定コンポーネント１０４に結合されたすべてのコンポーネントとの間の対話を容易にすることが可能である。図示されるように、プレゼンテーション・コンポーネント１２０４は、目的地推定コンポーネント１０４とともに利用されることが可能な、独立したエンティティである。しかしながら、プレゼンテーション・コンポーネント１２０４および／または同様のビュー・コンポーネントは、目的地推定コンポーネント１０４（および／またはインターフェース・コンポーネント１０２）および／またはスタンドアロン・ユニットに組み込まれることが可能であることを理解されたい。プレゼンテーション・コンポーネント１２０４は、１つまたは複数のグラフィカル・ユーザ・インターフェース（ＧＵＩ）、コマンド・ライン・インターフェースなどを提供することが可能である。例えば、データのロード、インポート、読み込みなどを行う領域または手段をユーザに提供するＧＵＩが描画されることが可能であり、さらに、このＧＵＩは、そのような操作の結果を表示する領域を含むことが可能である。これらの領域は、ダイアログ・ボックス、スタティック・コントロール、ドロップ・ダウン・メニュー、リスト・ボックス、ポップアップ・メニュー、エディット・コントロール、コンボ・ボックス、ラジオ・ボタン、チェック・ボックス、プッシュ・ボタン、およびグラフィックボックスを備える、既知のテキスト領域および／またはグラフィック領域を備えることが可能である。さらに、ナビゲーション用垂直および／または水平スクロール・バーや、領域を見えるようにするかどうかを決定するツール・ボタンなどの表示を容易にするユーティリティを用いることが可能である。例えば、ユーザは、目的地推定コンポーネント１０４に結合されたコンポーネントのうちの１つまたは複数と対話することが可能である。
【００８４】
ユーザはさらに、それらの領域との対話において、様々な装置（例えば、マウス、ローラーボール、キーパッド、キーボード、ペン、および／または音声アクティベーション）を用いて情報を選択および入力することが可能である。一般に、検索を開始する場合は、情報を入力した後に、プッシュ・ボタンや、キーボードのＥｎｔｅｒキーのようなメカニズムを用いることが可能である。しかしながら、本特許請求対象は、そのように限定されないことを理解されたい。例えば、チェック・ボックスをハイライトするだけで、情報の伝達を開始することも可能である。別の例では、コマンド・ライン・インターフェースを用いることが可能である。例えば、コマンド・ライン・インターフェースは、（例えば、ディスプレイ上のテキスト・メッセージまたは音声トーンにより）情報をテキスト・メッセージで入力するようにユーザを促す（プロンプトする）ことが可能である。それに対し、ユーザは、適切な情報（例えば、インターフェース・プロンプト内に示された選択肢に対応する英数字入力、またはプロンプト内に提起された質問に対する答え）を入力することが可能である。コマンド・ライン・インターフェースは、ＧＵＩおよび／またはＡＰＩと関連して用いられることが可能であることを理解されたい。さらに、コマンド・ライン・インターフェースは、ハードウェア（例えば、ビデオ・カード）および／または限定的なグラフィック・サポートのディスプレイ（例えば、白黒でＥＧＡ）、および／または低帯域幅通信チャネルと関連して用いられることが可能である。
【００８５】
図１３〜１４は、本特許請求対象による方法論を示す。説明を簡潔にするために、この方法論を、一連の操作として図示および説明する。本発明は、図示された操作および／または操作の順序によって限定されるものではなく、例えば、各操作は、様々な順序で、かつ／または同時に行われうるものであり、さらに、本明細書に提示および説明されていない他の操作とともに行われることも可能であることを理解されたい。さらに、本特許請求対象による方法の実装には、図示されている操作のすべてが必要であるとは限らない。さらに、当業者であれば理解されるように、本方法は、代替として、状態図またはイベントによって、一連の相互に関連する状態として表されることが可能である。
【００８６】
図１３は、目的地（destination(s)）を確率論的に（probabilistically）予測することを容易にする方法１３００を示す。１３０２で、地理的場所に関連付けられた確率論的（probabilistic）グリッドを生成する。地理的場所は、任意のサイズであってよいことが企図されている。例えば、地理的場所は、市、郡、任意の数の街区、州、国などに関連付けられることが可能である。さらに、グリッドは、任意の数のセルを含むことが可能であり、セルは任意のサイズ、形などであってよい。
【００８７】
１３０４で、トリップに関連付けられたデータを評価して、事前確率（prior(s)）および／または尤度（likelihood(s)）を決定する。例えば、評価されたデータは、グランド・カバー・データ、履歴データ、効率的な経路のデータ、トリップ時間分布データ、現在のトリップに関連する実時間位置特定データなどであってよい。データは、例えば、任意のソースから取得可能である。さらに、例えば、現在のトリップに関連する実時間位置データは、事前確率または尤度を決定する際に考慮されることが可能である。代替として、実時間位置データを利用することなく、事前確率または尤度を識別することが可能である。１３０６で、事前確率（prior(s)）および／または尤度（likelihood(s)）を確率論的に（probabilistically）組み合わせることにより、グリッドを利用して、トリップに関連する目的地を予測する。１つ以上の事前確率および／または１つ以上の尤度を選択して組み合わせることが可能である。したがって、一例によれば、目的地の予測に用いるために、グランド・カバー事前確率とトリップ時間尤度とを選択することが可能である。しかしながら、本特許請求対象は、そのような例に限定されない。この、事前確率（prior(s)）および／または尤度（likelihood(s)）の組合せを用いて、予測目的地を生成することが可能である。
【００８８】
図１４は、組み合わせられることが可能な事前確率（prior(s)）および／または尤度（likelihood(s)）に基づいて予測可能な目的地に関連する情報を提供する方法１４００を示す。１４０２で、個人の目的地事前確率、グランド・カバー事前確率、効率的運転尤度、およびトリップ時間尤度のうちの１つまたは複数を選択する。例えば、個人の目的地事前確率は、ユーザの以前の目的地の集合（例えば、履歴データ）に基づくことが可能である。さらに、グランド・カバー事前確率は、地理的場所に関連する確率論的（probabilistic）グリッドの中のあるセルが目的地である、そのセル内のグランド・カバーに基づく確率に関連付けられることが可能である。さらに、効率的運転尤度は、候補目的地に到着するまでの時間の変化に基づくことが可能である。したがって、ペアのセル間の経路は、効率的運転尤度に関連して評価されることが可能である。トリップ時間尤度は、例えば、経過トリップ時間および／またはトリップ時間分布データに関連付けることができる。
【００８９】
１４０４で、選択された事前確率（prior(s)）および／または尤度（likelihood(s)）を組み合わせる。例えば、選択された事前確率（prior(s)）および／または尤度（likelihood(s)）を組み合わせることに関連して、ベイズ規則を利用することが可能である。１４０６で、この組合せを利用して、目的地を確率論的に（probabilistically）予測する。したがって、例えば、確率論的（probabilistic）グリッドにある特定のセルを、目的地として識別することが可能である。１４０８で、予測目的地に関連する情報を提供する。例えば、その情報は、目的地、および／または目的地までの経路沿いの場所に関連付けることが可能である。別の例として、関連情報は、交通関連の情報、天候関連の情報、目標となる広告に関連付けられた情報、ナビゲーション支援を与えることに関連付けられた情報、関心対象である可能性があるイベントに関連付けられた情報などであってよい。
【００９０】
図１５〜１８は、運転者の行動および目的地の予測のモデリングに関連する様々な態様を描いた例示的グリッドおよび対応する地図を示す。これらのグリッドおよび地図は例であって、本特許請求対象はそのように限定されないことを理解されたい。図１５は、特定ユーザに関連する個人の目的地事前確率に関連付けられた目的地セルを描いたグリッド１５００を示す。図１６は、グランド・カバー事前確率を示すグリッド１６００を示す。より暗い色の輪郭は、より確率が高い目的地セルを示している。図１７は、効率的運転尤度に関連するグリッド１７００を示す。具体的には、グリッド１７００は、南方向に４セル分移動した後に、北東セクションのほとんどを除外してよいことを示している。さらに、図１８に描かれたグリッド１８００は、ユーザがさらに南に移動し続け、グリッド１７００の場合よりさらに多くのグリッドをグリッド１８００から除外してよいことを示している。
【００９１】
本特許請求対象の各種態様を実装するためのさらなるコンテクストを与えるために、以下では、図１９〜２０を参照しながら、本発明の各種態様を実装することに好適なコンピューティング環境を、簡潔かつ一般的に説明する。ここまでは、本特許請求対象を、ローカル・コンピュータおよび／またはリモート・コンピュータで実行されるコンピュータ・プログラムの、コンピュータで実行可能な命令の一般的コンテクストで説明してきたが、当業者であれば理解されるように、本発明は、他のプログラム・モジュールと組み合わせて実装されることも可能である。一般に、プログラム・モジュールは、特定のタスクの実行および／または特定の抽象データ型の実装を行うルーチン、プログラム、コンポーネント、データ構造体などを含む。
【００９２】
さらに、当業者であれば理解されるように、本発明の方法は、他のコンピュータ・システム構成でも実施可能であり、そのような構成として、シングル・プロセッサまたはマルチ・プロセッサのコンピュータ・システム、ミニ・コンピュータ、メインフレーム・コンピュータ、ならびにパーソナル・コンピュータ、ハンドヘルド・コンピューティング装置、マイクロ・プロセッサ・ベースおよび／またはプログラマブルの家庭用電子機器などがあり、これらのそれぞれが、１つまたは複数の関連装置と通信するように動作可能である。本特許請求対象の図示された各態様は、分散コンピューティング環境でも実施可能である。分散コンピューティング環境では、ある一定のタスクが、通信ネットワークでリンクされているリモート処理装置で実行される。しかしながら、本発明の態様のうちの、すべてではなくともいくつかは、スタンドアロン・コンピュータで実施可能である。分散コンピューティング環境では、プログラム・モジュールを、ローカルおよび／またはリモートのメモリ・ストレージ装置に置くことが可能である。
【００９３】
図１９は、本特許請求対象が対話することが可能な例示的コンピューティング環境１９００の概略ブロック図である。システム１９００は、１つまたは複数のクライアント１９１０を含む。クライアント１９１０は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティング装置）であってよい。システム１９００はさらに、１つまたは複数のサーバ１９２０を含む。サーバ１９２０は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティング装置）であってよい。サーバ１９２０は、例えば、本発明を用いることにより、変換を実行するスレッドを収容することが可能である。
【００９４】
クライアント１９１０とサーバ１９２０との間の可能な一通信は、２つ以上のコンピュータ・プロセスの間で伝送されるように適合されたデータ・パケットの形式で行われることが可能である。システム１９００は、クライアント１９１０とサーバ１９２０との間の通信を容易にするために用いられることが可能な通信フレームワーク１９４０を含む。クライアント１９１０は、クライアント１９１０のローカルな情報を格納するために用いられることが可能な１つまたは複数のクライアント・データ・ストア１９５０に、動作可能なように結合される。同様に、サーバ１９２０は、サーバ１９２０のローカルな情報を格納するために用いられることが可能な１つまたは複数のサーバ・データ・ストア１９３０に、動作可能なように結合される。
【００９５】
図２０は、本特許請求対象の各種態様を実装するための例示的環境２０００を示し、例示的環境２０００はコンピュータ２０１２を含む。コンピュータ２０１２は、処理ユニット２０１４、システム・メモリ２０１６、およびシステム・バス２０１８を含む。システム・バス２０１８は、システム・メモリ２０１６を含み、これに限定されないシステムコンポーネントを処理ユニット２０１４に結合する。処理ユニット２０１４は、利用可能な各種のプロセッサのどれでもよい。デュアル・マイクロ・プロセッサや他のマルチプ・ロセッサ・アーキテクチャを、処理ユニット２０１４として用いることも可能である。
【００９６】
システム・バス２０１８は、任意の様々な利用可能バス・アーキテクチャを用いる、メモリ・バスまたはメモリ・コントローラ、ペリフェラル・バスまたは外部バス、および／またはローカル・バスを含む、様々なタイプのバス構造のいずれかであってよく、利用可能バス・アーキテクチャとしては、Ｉｎｄｕｓｔｒｉａｌ Ｓｔａｎｄａｒｄ Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＳＡ）、Ｍｉｃｒｏ−Ｃｈａｎｎｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ（ＭＳＡ）、Ｅｘｔｅｎｄｅｄ ＩＳＡ（ＥＩＳＡ）、Ｉｎｔｅｌｌｉｇｅｎｔ Ｄｒｉｖｅ ＥＩｅｃｔｒｏｎｉｃｓ（ＩＤＥ）、ＶＥＳＡ Ｌｏｃａｌ Ｂｕｓ（ＶＬＢ）、Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）、Ｃａｒｄ Ｂｕｓ、Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ（ＵＳＢ）、Ａｄｖａｎｃｅｄ Ｇｒａｐｈｉｃｓ Ｐｏｒｔ（ＡＧＰ）、Ｐｅｒｓｏｎａｌ Ｃｏｍｐｕｔｅｒ Ｍｅｍｏｒｙ Ｃａｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ａｓｓｏｃｉａｔｉｏｎバス（ＰＣＭＣＩＡ）、Ｆｉｒｅｗｉｒｅ（ＩＥＥＥ １３９４）、Ｓｍａｌｌ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍｓ Ｉｎｔｅｒｆａｃｅ（ＳＣＳＩ）などがあり、これらに限定されない。
【００９７】
システム・メモリ２０１６は、揮発性メモリ２０２０および不揮発性メモリ２０２２を含む。基本入出力システム（ＢＩＯＳ）は、起動時などに、コンピュータ２０１２内の要素間で情報を転送する基本ルーチンを含み、不揮発性メモリ２０２２に格納される。限定ではなく例として、不揮発性メモリ２０２２としては、読み出し専用メモリ（ＲＯＭ）、書き込み可能ＲＯＭ（ＰＲＯＭ）、電気的書き込み可能ＲＯＭ（ＥＰＲＯＭ）、電気的消去可能書き込み可能ＲＯＭ（ＥＥＰＲＯＭ）、フラッシュ・メモリなどがある。揮発性メモリ２０２０としては、ランダム・アクセス・メモリ（ＲＡＭ）があり、これは外部キャッシュ・メモリとして動作する。ＲＡＭは、様々な形式で使用可能であり、限定ではなく例として、スタティックＲＡＭ（ＳＲＡＭ）、ダイナミックＲＡＭ（ＤＲＡＭ）、シンクロナスＤＲＡＭ（ＳＤＲＡＭ）、ダブル・データ・レートＳＤＲＡＭ（ＤＤＲ ＳＤＲＡＭ）、エンハンストＳＤＲＡＭ（ＥＳＤＲＡＭ）、シンクリンクＤＲＡＭ（ＳＬＤＲＡＭ）、ランバス・ダイレクトＲＡＭ（ＲＤＲＡＭ）、ダイレクト・ランバス・ダイナミックＲＡＭ（ＤＲＤＲＡＭ）、ランバス・ダイナミックＲＡＭ（ＲＤＲＡＭ）などの形式で使用可能である。
【００９８】
コンピュータ２０１２はさらに、リムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータストレージ媒体を含む。図２０は、例えば、ディスク・ストレージ２０２４を示している。ディスク・ストレージ２０２４は、磁気ディスク・ドライブ、フロッピー（登録商標）ディスク・ドライブ、テープ・ドライブ、Ｊａｚドライブ、Ｚｉｐドライブ、ＬＳ−１００ドライブ、フラッシュ・メモリ・カード、またはメモリ・スティックのような装置を含み、これらに限定されない。さらに、ディスク・ストレージ２０２４は、独立に、または他のストレージ媒体との組合せでストレージ媒体を含むことが可能であり、他のストレージ媒体としては、コンパクト・ディスクＲＯＭ装置（ＣＤ−ＲＯＭ）、追記型ＣＤドライブ（ＣＤ−Ｒドライブ）、書き換え可能ＣＤドライブ（ＣＤ−ＲＷドライブ）、またはデジタル多用途ディスクＲＯＭドライブ（ＤＶＤ−ＲＯＭ）などの光ディスク・ドライブがあり、これらに限定されない。ディスク・ストレージ装置２０２４とシステム・バス２０１８との接続を容易にするために、典型的には、インターフェース２０２６のようなリムーバブルまたは非リムーバブル・インターフェースが用いられる。
【００９９】
図２０では、ユーザと、好適なオペレーティング環境２０００内に示されている基本コンピュータリソースとの媒介として動作するソフトウェアが示されていることを理解されたい。そのようなソフトウェアは、オペレーティング・システム２０２８を含む。オペレーティング・システム２０２８は、ディスク・ストレージ２０２４に格納可能であって、コンピュータ・システム２０１２のリソースの制御および割り当てを行うように動作する。システム・アプリケーション２０３０は、システム・メモリ２０１６またはディスク・ストレージ２０２４に格納されているプログラム・モジュール２０３２およびプログラムデータ２０３４を用いて、オペレーティング・システム２０２８によるリソースの管理を利用する。本特許請求対象は、様々なオペレーティング・システムまたはオペレーティング・システムの組合せとともに実装されることが可能であることを理解されたい。
【０１００】
ユーザが、コマンドまたは情報を、入力装置２０３６からコンピュータ２０１２に入力する。入力装置２０３６としては、マウスなどのポインティング装置、トラックボール、スタイラス、タッチパッド、キーボード、マイク、ジョイスティック、ゲームパッド、パラボラ・アンテナ、スキャナ、ＴＶチューナ・カード、デジタル・カメラ、デジタル・ビデオ・カメラ、Ｗｅｂカメラなどがあり、これらに限定されない。これらおよび他の入力装置は、インターフェース・ポート２０３８からシステム・バス２０１８を経て処理ユニット２０１４に接続される。インターフェース・ポート２０３８は、例えば、シリアル・ポート、パラレル・ポート、ゲーム・ポート、およびユニバーサル・シリアル・バス（ＵＳＢ）を含む。出力装置２０４０は、入力装置２０３６と同じタイプのポートのいくつかを使用する。したがって、例えば、ＵＳＢポートを用いて、コンピュータ２０１２に入力を与えること、およびコンピュータ２０１２から出力装置２０４０に情報を出力することが可能である。出力アダプタ２０４２が設けられているのは、出力装置２０４０の中でも特に、モニタ、スピーカ、プリンタなど、いくつかの出力装置２０４０が専用アダプタを必要とするためである。出力アダプタ２０４２としては、例えば、出力装置２０４０とシステム・バス２０１８との間の接続手段を与えるビデオ・カードやサウンド・カードなどがあり、これらに限定されない。なお、他の装置および／または装置のシステムは、リモート・コンピュータ２０４４のように、入力および出力の両方の機能を提供する。
【０１０１】
コンピュータ２０１２は、１つまたは複数のリモート・コンピュータ（リモート・コンピュータ２０４４など）との論理接続を使用して、ネットワーク環境で動作することが可能である。リモート・コンピュータ２０４４は、パーソナル・コンピュータ、サーバ、ルータ、ネットワークＰＣ、ワークステーション、マイクロ・プロセッサ・ベースの電気器具、ピア装置または他の共通ネットワークノードなどであってよく、典型的には、コンピュータ２０１２に関して説明された要素の多くまたはすべてを含む。簡潔さのために、メモリ・ストレージ装置２０４６だけを、リモート・コンピュータ２０４４とともに示した。リモート・コンピュータ２０４４は、ネットワーク・インターフェース２０４８を介してコンピュータ２０１２と論理的に接続され、物理的にはさらに、通信接続２０５０を介して接続される。ネットワーク・インターフェース２０４８は、ローカル・エリア・ネットワーク（ＬＡＮ）やワイド・エリア・ネットワーク（ＷＡＮ）のような有線および／または無線通信ネットワークを包含する。ＬＡＮテクノロジとしては、Ｆｉｂｅｒ Ｄｉｓｔｒｉｂｕｔｅｄ Ｄａｔａ Ｉｎｔｅｒｆａｃｅ（ＦＤＤＩ）、Ｃｏｐｐｅｒ Ｄｉｓｔｒｉｂｕｔｅｄ Ｄａｔａ Ｉｎｔｅｒｆａｃｅ（ＣＤＤＩ）、イーサネット（登録商標）、トークンリングなどがある。ＷＡＮテクノロジとしては、ポイントツーポイントリンク、統合サービスデジタル網（ＩＳＤＮ）およびその変形形態のような回路交換網、パケット交換網、デジタル加入者回線（ＤＳＬ）などがあり、これらに限定されない。
【０１０２】
通信接続２０５０は、ネットワーク・インターフェース２０４８をバス２０１８に接続するために用いられるハードウェア／ソフトウェアを意味する。通信接続２０５０は、説明を明確にするために、コンピュータ２０１２の内部にあるように示されているが、コンピュータ２０１２の外部にあってもよい。ネットワーク・インターフェース２０４８との接続に必要なハードウェア／ソフトウェアは、あくまで例であるが、標準の電話グレードのモデム、ケーブル・モデム、およびＤＳＬモデムを含むモデム、ＩＳＤＮアダプタ、イーサネット（登録商標）カードなどの内部装置および外部装置を含む。
【０１０３】
ここまで説明してきた内容は、本発明の例を含む。本特許請求対象の説明のために、コンポーネントまたは方法の、考えられるあらゆる組合せを説明するのはもちろん不可能であるが、当業者であれば理解されるように、本発明の、多くの別の組合せおよび並べ替えが可能である。したがって、本特許請求対象は、添付の特許請求項の趣旨および範囲に当てはまるそのような変更、修正、および変形をすべて包含するものとする。
【０１０４】
特に、前述のコンポーネント、装置、回路、システムなどによって実行される各種機能に関して、そのようなコンポーネントを記述するために用いられる用語（「手段」への言及を含む）は、特に断らない限り、構造的には開示の構造と等価でなくても、記述されたコンポーネント（例えば、機能的等価物）の指定された機能を実行し、本明細書に記載された、本特許請求対象の例示的態様の機能を実行する、任意のコンポーネントに対応するものとする。この点において、本発明は、本特許請求対象の各種方法の操作および／またはイベントを実行するためのシステムだけでなく、そのための、コンピュータで実行可能な命令を有するコンピュータ可読媒体も含むことを理解されよう。
【０１０５】
さらに、本発明の具体的な特徴が、いくつかある実施態様のうちの１つだけについて開示されているが、そのような特徴は、他の実施態様の１つまたは複数の他の特徴と組み合わせられることが可能であり、このことは、任意または特定の用途にとって望ましく、かつ有利であろう。さらに、用語「含む」（「ｉｎｃｌｕｄｅｓ」および「ｉｎｃｌｕｄｉｎｇ」）およびその変形は、詳細説明または特許請求項において用いられる限りにおいては、用語「含む、備える」（「ｃｏｍｐｒｉｓｉｎｇ」）と同様に包含的であるものとする。
【図面の簡単な説明】
【０１０６】
【図１】ユーザの目的地を決定することを容易にする例示的システムのブロック図である。
【図２】目的地を確率論的（probabilistically）に予測することに関連して利用可能な確率論的（probabilistic）グリッドおよび／または位置間経路を生成する例示的システムのブロック図である。
【図３】履歴データに基づいて目的地を予測する例示的システムのブロック図である。
【図４】オープン・ワールド・モデリングを利用して目的地を予測する例示的システムのブロック図である。
【図５】グランド・カバー・データに少なくとも部分的に基づいて予測目的地を与える例示的システムのブロック図である。
【図６】以前に訪問された場所からの４つのしきい値半径に対する、離散化された４層確率分布の一例を示す図である。
【図７】効率的な経路のデータに少なくとも部分的に基づいて目的地の予測を生成する例示的システムのブロック図である。
【図８】目的地を予測することと関連してトリップ時間を評価する例示的システムのブロック図である。
【図９】事前確率および／または尤度を組み合わせて目的地の予測を容易にすることを可能にする例示的システムのブロック図である。
【図１０】予測目的地に関連する可能性がある情報を提供する例示的システムのブロック図である。
【図１１】トリップ中に目的地を確率論的（probabilistically）に予測する例示的システムのブロック図である。
【図１２】予測目的地の生成を容易にする例示的システムのブロック図である。
【図１３】目的地を確率論的（probabilistically）に予測することを容易にする例示的方法を示す図である。
【図１４】組み合わせられることが可能な事前確率および／または尤度に基づいて予測可能な目的地に関連する情報を提供する例示的方法を示す図である。
【図１５】運転者の行動および目的地の予測のモデリングに関連する様々な態様を描いた例示的グリッドおよび対応する地図を示す図である。
【図１６】運転者の行動および目的地の予測のモデリングに関連する様々な態様を描いた例示的グリッドおよび対応する地図を示す図である。
【図１７】運転者の行動および目的地の予測のモデリングに関連する様々な態様を描いた例示的グリッドおよび対応する地図を示す図である。
【図１８】運転者の行動および目的地の予測のモデリングに関連する様々な態様を描いた例示的グリッドおよび対応する地図を示す図である。
【図１９】本特許請求対象の新規な態様を用いることが可能な例示的ネットワーキング環境を示す図である。
【図２０】本特許請求対象に従って用いられることが可能な例示的オペレーティング環境を示す図である。
【特許請求の範囲】
【請求項１】
ユーザの１つまたは複数の目的地を決定することを容易にするシステムであって、
入力データを受け取るインターフェース・コンポーネント（１０２）、および
前記受け取られた入力データに少なくとも部分的に基づく事前確率および尤度のうちの少なくとも一つに基づいて、トリップの１つまたは複数の目的地を確率論的に予測する目的地推定コンポーネント（１０４）
を備えることを特徴とするシステム。
【請求項２】
前記事前確率は、ユーザの以前の目的地の集合に関連する、個人の目的地事前確率であることを特徴とする請求項１に記載のシステム。
【請求項３】
前記事前確率は、セルが、前記セル内のグランド・カバーに基づく前記目的地であることの確率に関連付けられたグランド・カバー事前確率であることを特徴とする請求項１に記載のシステム。
【請求項４】
前記尤度は、候補目的地に到着するまでの時間の変化に基づく効率的運転尤度であり、前記効率的運転尤度は、最終的な位置についての根拠を与える候補目的地の集合に関連付けられた、算出された運転効率に関連することを特徴とする請求項１に記載のシステム。
【請求項５】
前記尤度は、候補目的地までの推定時間および経過トリップ時間に少なくとも部分的に基づくトリップ時間尤度であることを特徴とする請求項１に記載のシステム。
【請求項６】
前記目的地推定コンポーネントは、ベイズ規則を利用して前記１つまたは複数の目的地を確率論的に予測することを特徴とする請求項１に記載のシステム。
【請求項７】
個人の目的地事前確率、グランド・カバー事前確率、効率的運転尤度、およびトリップ時間尤度のうちの少なくとも１つを選択して組み合わせて、前記１つまたは複数の目的地を確率論的に予測することを可能にする融合（fusing）コンポーネントをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項８】
前記１つまたは複数の予測目的地に関連付けられた関連情報を提供するコンテンツ・コンポーネントをさらに備え、前記コンテンツ・コンポーネントは、交通（traffic）、工事、前方の安全性の問題、掲示されている広告、指示、経路の助言、最新情報の少なくとも１つについて警告を与えることを特徴とする請求項１に記載のシステム。
【請求項９】
前記コンテンツ・コンポーネントから提供される前記関連情報を、ユーザ関連設定に適合させるカスタマイズ・コンポーネントをさらに備えることを特徴とする請求項８に記載のシステム。
【請求項１０】
前記目的地推定コンポーネントは、実時間位置特定データを利用して、移動中に前記１つまたは複数の目的地を予測することを特徴とする請求項１に記載のシステム。
【請求項１１】
前記目的地推定コンポーネントによって、前記１つまたは複数の目的地を予測するために用いられる、地理的位置の地図に関連付けられた確率論的グリッドを生成するグリッド・コンポーネントをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項１２】
候補目的地への移動に利用される可能性が高い経路を生成し、前記経路に関連付けられた時間推定値を決定する経路計画コンポーネントをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項１３】
前記目的地推定コンポーネントは、オープン・ワールド解析およびクローズド・ワールド解析を位置予測に組み込み、前記目的地推定コンポーネントは、運転者が以前に観察されていない場所を訪問する尤度、および、新しい複数の場所、複数の場所の事前確率観察の空間的関係についての予測を実施することを特徴とする請求項１に記載のシステム。
【請求項１４】
ユーザの目的地を決定することを容易にする方法であって、
地理的位置に関連付けられた確率論的グリッドを生成すること、
トリップに関連付けられたデータを評価して、事前確率および尤度の一つまたは複数を決定すること、および
前記事前確率および前記尤度の前記一つまたは複数を確率論的に組み合わせることによって、前記グリッドを利用して、前記トリップに関連する１つまたは複数の目的地を予測すること
を含むことを特徴とする方法。
【請求項１５】
前記事前確率および前記尤度の前記一つまたは複数を選択して確率論的に組み合わせることをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記１つまたは複数の目的地を、前記トリップの進行中に予測することをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１７】
前記１つまたは複数の予測目的地に関連付けられた関連情報を提供することをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１８】
ユーザの以前の目的地と、前記セル内のグランド・カバーに基づいて当該セルが前記目的地であることの確率との集合の１つまたは複数に基づいて、前記事前確率を生成することをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１９】
候補目的地に到着するまでの時間の変化、および経過トリップ時間の、一つまたは複数に基づいて前記尤度を生成することをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項２０】
ユーザの１つまたは複数の目的地を決定することを容易にするシステムであって、
１つ以上の事前確率および１つ以上の尤度の少なくとも一つに関連付けられた入力データを受け取る手段（１０２）、および
１つ以上の事前確率および１つ以上の尤度の前記少なくとも一つの組合せに基づいて、１つまたは複数の目的地を確率論的に予測する手段（１０４）
を備えることを特徴とするシステム。
【請求項１】
ユーザの１つまたは複数の目的地を決定することを容易にするシステムであって、
入力データを受け取るインターフェース・コンポーネント（１０２）、および
前記受け取られた入力データに少なくとも部分的に基づく事前確率および尤度のうちの少なくとも一つに基づいて、トリップの１つまたは複数の目的地を確率論的に予測する目的地推定コンポーネント（１０４）
を備えることを特徴とするシステム。
【請求項２】
前記事前確率は、ユーザの以前の目的地の集合に関連する、個人の目的地事前確率であることを特徴とする請求項１に記載のシステム。
【請求項３】
前記事前確率は、セルが、前記セル内のグランド・カバーに基づく前記目的地であることの確率に関連付けられたグランド・カバー事前確率であることを特徴とする請求項１に記載のシステム。
【請求項４】
前記尤度は、候補目的地に到着するまでの時間の変化に基づく効率的運転尤度であり、前記効率的運転尤度は、最終的な位置についての根拠を与える候補目的地の集合に関連付けられた、算出された運転効率に関連することを特徴とする請求項１に記載のシステム。
【請求項５】
前記尤度は、候補目的地までの推定時間および経過トリップ時間に少なくとも部分的に基づくトリップ時間尤度であることを特徴とする請求項１に記載のシステム。
【請求項６】
前記目的地推定コンポーネントは、ベイズ規則を利用して前記１つまたは複数の目的地を確率論的に予測することを特徴とする請求項１に記載のシステム。
【請求項７】
個人の目的地事前確率、グランド・カバー事前確率、効率的運転尤度、およびトリップ時間尤度のうちの少なくとも１つを選択して組み合わせて、前記１つまたは複数の目的地を確率論的に予測することを可能にする融合（fusing）コンポーネントをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項８】
前記１つまたは複数の予測目的地に関連付けられた関連情報を提供するコンテンツ・コンポーネントをさらに備え、前記コンテンツ・コンポーネントは、交通（traffic）、工事、前方の安全性の問題、掲示されている広告、指示、経路の助言、最新情報の少なくとも１つについて警告を与えることを特徴とする請求項１に記載のシステム。
【請求項９】
前記コンテンツ・コンポーネントから提供される前記関連情報を、ユーザ関連設定に適合させるカスタマイズ・コンポーネントをさらに備えることを特徴とする請求項８に記載のシステム。
【請求項１０】
前記目的地推定コンポーネントは、実時間位置特定データを利用して、移動中に前記１つまたは複数の目的地を予測することを特徴とする請求項１に記載のシステム。
【請求項１１】
前記目的地推定コンポーネントによって、前記１つまたは複数の目的地を予測するために用いられる、地理的位置の地図に関連付けられた確率論的グリッドを生成するグリッド・コンポーネントをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項１２】
候補目的地への移動に利用される可能性が高い経路を生成し、前記経路に関連付けられた時間推定値を決定する経路計画コンポーネントをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項１３】
前記目的地推定コンポーネントは、オープン・ワールド解析およびクローズド・ワールド解析を位置予測に組み込み、前記目的地推定コンポーネントは、運転者が以前に観察されていない場所を訪問する尤度、および、新しい複数の場所、複数の場所の事前確率観察の空間的関係についての予測を実施することを特徴とする請求項１に記載のシステム。
【請求項１４】
ユーザの目的地を決定することを容易にする方法であって、
地理的位置に関連付けられた確率論的グリッドを生成すること、
トリップに関連付けられたデータを評価して、事前確率および尤度の一つまたは複数を決定すること、および
前記事前確率および前記尤度の前記一つまたは複数を確率論的に組み合わせることによって、前記グリッドを利用して、前記トリップに関連する１つまたは複数の目的地を予測すること
を含むことを特徴とする方法。
【請求項１５】
前記事前確率および前記尤度の前記一つまたは複数を選択して確率論的に組み合わせることをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記１つまたは複数の目的地を、前記トリップの進行中に予測することをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１７】
前記１つまたは複数の予測目的地に関連付けられた関連情報を提供することをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１８】
ユーザの以前の目的地と、前記セル内のグランド・カバーに基づいて当該セルが前記目的地であることの確率との集合の１つまたは複数に基づいて、前記事前確率を生成することをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１９】
候補目的地に到着するまでの時間の変化、および経過トリップ時間の、一つまたは複数に基づいて前記尤度を生成することをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項２０】
ユーザの１つまたは複数の目的地を決定することを容易にするシステムであって、
１つ以上の事前確率および１つ以上の尤度の少なくとも一つに関連付けられた入力データを受け取る手段（１０２）、および
１つ以上の事前確率および１つ以上の尤度の前記少なくとも一つの組合せに基づいて、１つまたは複数の目的地を確率論的に予測する手段（１０４）
を備えることを特徴とするシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公表番号】特表２００９−５２１６６５（Ｐ２００９−５２１６６５Ａ）
【公表日】平成２１年６月４日（２００９．６．４）
【国際特許分類】
【出願番号】特願２００８−５３３３７７（Ｐ２００８−５３３３７７）
【出願日】平成１８年９月５日（２００６．９．５）
【国際出願番号】ＰＣＴ／ＵＳ２００６／０３４６０８
【国際公開番号】ＷＯ２００７／０４０８９１
【国際公開日】平成１９年４月１２日（２００７．４．１２）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
【公表日】平成２１年６月４日（２００９．６．４）
【国際特許分類】
【出願日】平成１８年９月５日（２００６．９．５）
【国際出願番号】ＰＣＴ／ＵＳ２００６／０３４６０８
【国際公開番号】ＷＯ２００７／０４０８９１
【国際公開日】平成１９年４月１２日（２００７．４．１２）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
[ Back to top ]