(57)【要約】  ナビゲーションルートを生成するための技法は、ユーザが以前に通過した、それぞれの出発地と目的地との間の複数のルートを示すルートデータを取得すること(702)を含む。技法は、地図データを使用して、複数のルート内の第1のタイプのルートセグメントおよび少なくとも1つの他のタイプのルートセグメントを識別して、ルートセグメントデータを生成すること(704)と、ルートデータおよびルートセグメントデータを使用して、ユーザによるナビゲーションルートの選択の際の第1のタイプのルートのルートセグメントの属性と少なくとも1つの他のタイプのルートセグメントの属性との間のトレードオフを測定するための定量的メトリックを決定すること(706)とをさらに含む。出発地および目的地の指示が受信された(708)後で、技法は、ルートセグメントの選択を制約するために定量的メトリックを適用することを含めて、ユーザ用の出発地と目的地との間のナビゲーションルートを生成すること(710)を含む。
2021533334.tif 000002
【特許請求の範囲】
【請求項１】
ナビゲーションルートを生成するための方法であって、
処理ハードウェアによって、ユーザが以前に通過した、それぞれの出発地と目的地との間の複数のルートを示すルートデータを取得するステップと、
前記処理ハードウェアによって、地図データを使用して、前記複数のルート内の第1のタイプのルートセグメントおよび少なくとも1つの他のタイプのルートセグメントを識別して、ルートセグメントデータを生成するステップと、
前記処理ハードウェアによって、前記ルートデータおよび前記ルートセグメントデータを使用して、前記ユーザによるナビゲーションルートの選択の際の前記第1のタイプのルートのルートセグメントの第1の属性と前記少なくとも1つの他のタイプのルートセグメントの第2の属性との間のトレードオフを測定するための定量的メトリックを決定するステップと、
前記処理ハードウェアによって、出発地および目的地の指示を受信するステップと、
前記処理ハードウェアによって、ルートセグメントの選択を制約するために前記定量的メトリックを適用するステップを含めて、前記ユーザ用の前記出発地と前記目的地との間のナビゲーションルートを生成するステップと
を含む、方法。
【請求項２】
前記定量的メトリックを決定するステップが、前記ユーザが移動した1対の位置間の第1のルートと前記ユーザが移動した前記1対の位置間の第2のルートとの時間量の差異を算定するステップを含み、前記第1のルートが、前記第1のタイプのルートセグメントを含み、前記第2のルートが、前記第2のタイプのルートセグメントを含まない、請求項1に記載の方法。
【請求項３】
前記処理ハードウェアによって、前記ユーザが前記目的地に到着しなければならない時間を示す、時間制約パラメータを受信するステップ
をさらに含み、
前記ナビゲーションルートを生成するステップが、ルートセグメントの選択をさらに制約するために前記時間制約パラメータを適用するステップを含む、
請求項1または2に記載の方法。
【請求項４】
前記処理ハードウェアによって、前記出発地と前記目的地との間で前記ユーザにとってカープーリングが利用可能かどうかを示す、カープーリングパラメータを受信するステップ
をさらに含み、
前記ナビゲーションルートを生成するステップが、ルートセグメントの選択をさらに制約するために前記カープーリングパラメータを適用するステップを含む、
請求項1から3のいずれか一項に記載の方法。
【請求項５】
前記処理ハードウェアによって、前記出発地と前記目的地との間を前記ユーザが移動する予定の時間を示す、移動時間パラメータを受信するステップ
をさらに含み、
前記ナビゲーションルートを生成するステップが、ルートセグメントの選択をさらに制約するために前記移動時間パラメータを適用するステップを含む、
請求項1から4のいずれか一項に記載の方法。
【請求項６】
前記処理ハードウェアによって、前記ルートデータおよび前記ルートセグメントデータを使用して機械学習モデルをトレーニングするステップであって、前記機械学習モデルが、指定された位置間のルート候補を生成するように構成される、ステップ
をさらに含む、請求項1から5のいずれか一項に記載の方法。
【請求項７】
前記定量的メトリックを決定するステップが、
コンピューティングデバイスのユーザインターフェースを介して、前記第1のタイプのルートセグメントと前記少なくとも1つの他のタイプのルートセグメントとの間の前記トレードオフを指定するための対話型コントロールを提供するステップと、
前記ユーザインターフェース内に提供された前記対話型コントロールを介して、前記定量的メトリックを受信するステップと
を含む、請求項1から6のいずれか一項に記載の方法。
【請求項８】
前記ルートデータが、追加データなしに前記定量的メトリックを決定するには不十分であるとの判定に応答して、前記定量的メトリックをさらに、前記出発地と前記目的地との間のルートについて前記第1の属性および前記第2の属性に関する他のユーザの嗜好を示す指示を使用して決定するステップ
をさらに含む、請求項1から7のいずれか一項に記載の方法。
【請求項９】
コンピューティングシステムであって、
1つまたは複数のプロセッサと、
命令をその上に格納するコンピュータ可読メモリであって、前記命令が前記1つまたは複数のプロセッサによって実行されると前記コンピューティングシステムに、
ユーザが以前に通過した、それぞれの出発地と目的地との間の複数のルートを示すルートデータを取得すること、
地図データを使用して、前記複数のルート内の第1のタイプのルートセグメントおよび少なくとも1つの他のタイプのルートセグメントを識別して、ルートセグメントデータを生成すること、
前記ルートデータおよび前記ルートセグメントデータを使用して、前記ユーザによるナビゲーションルートの選択の際の前記第1のタイプのルートのルートセグメントの第1の属性と前記少なくとも1つの他のタイプのルートセグメントの第2の属性との間のトレードオフを測定するための定量的メトリックを決定すること、
出発地および目的地の指示を受信すること、ならびに
ルートセグメントの選択を制約するために前記定量的メトリックを適用することを含めて、前記ユーザ用の前記出発地と前記目的地との間のナビゲーションルートを生成すること
を行わせる、コンピュータ可読メモリと
を備える、コンピューティングシステム。
【請求項１０】
前記定量的メトリックを決定するために、前記命令が前記システムに、前記ユーザが移動した1対の位置間の第1のルートと前記ユーザが移動した前記1対の位置間の第2のルートとの時間量の差異を算定することを行わせ、前記第1のルートが、前記第1のタイプのルートセグメントを含み、前記第2のルートが、前記第2のタイプのルートセグメントを含まない、請求項9に記載のコンピューティングシステム。
【請求項１１】
前記命令が前記システムに、
前記ユーザが前記目的地に到着しなければならない時間を示す、時間制約パラメータを受信すること
をさらに行わせ、
前記ナビゲーションルートを生成するために、前記命令が前記システムに、ルートセグメントの選択をさらに制約するために前記時間制約パラメータを適用することを行わせる、
請求項9または10に記載のコンピューティングシステム。
【請求項１２】
前記命令が前記システムに、
前記出発地と前記目的地との間で前記ユーザにとってカープーリングが利用可能かどうかを示す、カープーリングパラメータを受信すること
を行わせ、
前記ナビゲーションルートを生成するために、前記命令が前記システムに、ルートセグメントの選択をさらに制約するために前記カープーリングパラメータを適用することを行わせる、
請求項9から11のいずれか一項に記載のコンピューティングシステム。
【請求項１３】
前記命令が前記システムに、
前記出発地と前記目的地との間を前記ユーザが移動する予定の時間を示す、移動時間パラメータを受信すること
をさらに行わせ、
前記ナビゲーションルートを生成するために、前記命令が、ルートセグメントの選択をさらに制約するために前記移動時間パラメータを適用する、
請求項9から12のいずれか一項に記載のコンピューティングシステム。
【請求項１４】
前記命令が前記システムに、
前記ルートデータおよび前記ルートセグメントデータを使用して機械学習モデルをトレーニングすることであって、前記機械学習モデルが、指定された位置間のルート候補を生成するように構成される、トレーニングすること
をさらに行わせる、請求項9から13のいずれか一項に記載のコンピューティングシステム。
【請求項１５】
前記定量的メトリックを決定するために、前記命令が前記システムに、
コンピューティングデバイスのユーザインターフェースを介して、前記第1のタイプのルートセグメントと前記少なくとも1つの他のタイプのルートセグメントとの間の前記トレードオフを指定するための対話型コントロールを提供することと、
前記ユーザインターフェース内に提供された前記対話型コントロールを介して、前記定量的メトリックを受信することと
を行わせる、請求項9から14のいずれか一項に記載のコンピューティングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、ナビゲーションシステムに関し、より詳細には、ユーザによるナビゲーション上の決定の際のパラメータ間のトレードオフを示す定量的メトリック(quantitative metric)を計算し、適用することに関する。
【背景技術】
【０００２】
本明細書において提供される背景技術の記述は、本開示の背景(context)を概略提示するためのものである。現在名を連ねている発明者らの、本背景技術セクションにおいて記述されている範囲内の研究、ならびに普通なら出願時に従来技術として見なされることのない本記述の態様は、明示的にも黙示的にも本開示に対する従来技術として認められるものではない。
【０００３】
今日、パーソナルコンピュータ、タブレット、モバイル電話、専用ナビゲータなど、多数の電子デバイスは、地理的領域のデジタル地図、および地理的位置間のナビゲーションのためのステップバイステップの指示を提供している。ナビゲーションサービスは、ナビゲーション指示と、場合によっては関連のデジタル地図とを、地図作成アプリケーションおよびナビゲーションアプリケーションなどの専用ソフトウェアアプリケーションを介して、またウェブブラウザなどの汎用ソフトウェアアプリケーションを介して、提供することができる。運転指示に加えて、ナビゲーションサービスは、歩行指示、公共交通機関指示、自転車運転指示などを提供することもできる。
【０００４】
ナビゲーションサービスは、典型的には、ユーザからナビゲーション指示要求を受領し、時間や距離などの因子の、ある特定の所定の順序に従って、ナビゲーションルートを生成する。より具体的には、ナビゲーションサービスは、いくつかのナビゲーションルート候補を生成し、これらの候補を、合計距離または合計移動時間の長くなる順番に提示することができる。ナビゲーションサーバは、時間に関してナビゲーションルートを最適化しようと、すなわち最小時間量を必要とするルートを生成しようと試み、または距離に関してナビゲーションルートを最適化しようと、すなわち利用可能な最短ルートを特定しようと試みる。場合によっては、ナビゲーションサービスは、ナビゲーションルート候補を生成し、セグメントがある特定の基準、例えば通行料徴収、と一致するナビゲーションルートを特定するための、追加のコントロールを提供する。これらの指示は0か1か(binary)であり、したがって、ナビゲーションルートまたはそのルートの一部分が基準を満たすかどうかを示すにすぎない。
【０００５】
しかし、ナビゲーションサービスは、ユーザによる過去のナビゲーションルートの選択または他のナビゲーション上の決定の際のナビゲーションルートのパラメータ間の関係を定量的に反映させたナビゲーションルートを生成しない。
【発明の概要】
【課題を解決するための手段】
【０００６】
一般的に言えば、本開示のシステムは、ユーザ用に、あるタイプ(「ターゲットタイプ」)のルートセグメントと別のタイプのルートセグメントとの間のトレードオフを測定するための定量的メトリックを生成し、この定量的メトリックを、ナビゲーション指示(より具体的には、出発地から目的地までのナビゲーションルート)を生成するときに適用するように構成される。定量的メトリックを生成するために、システムは、ユーザが通過した過去のナビゲーションルートの指示を処理することができる。例えば、ある特定の出発地およびある特定の目的地に関して、システムは、ユーザがターゲットタイプのNキロメートルのルートセグメントのあるナビゲーションルートを辿っており、このタイプのルートセグメントの全くない代替ナビゲーションルートなら余計にM分必要となったであろう、との判定をすることができる。システムは、この事例を、ユーザがターゲットタイプのNキロメートルのルートセグメントをM分の時間とトレードオフすることを選ぶ一例として使用することができる。同様の計算の複数の事例を使用して、システムは、ユーザが将来的に選ぶことになる起こり得るトレードオフを予測するための定量的メトリックを生成することができる。システムは次いで、このメトリックを、ユーザまたは自律車両用のナビゲーションルートを生成する際の制約として使用し、したがって、これらのルートを要件セットに合わせてより良好に最適化することができる。
【０００７】
システムは、ナビゲーションルートのうちの1つまたは複数をデバイスに、ユーザに表示するために出力することができる。他の実装形態では、システムは、ナビゲーションルートを自律車両のコントローラに提供することができる。
【０００８】
システムは、いくつかの実装形態では、定量的メトリックを、他のコンテキスト信号を考慮して動的に調整することができる。例えば、システムは、時間制約(例えば目的地におけるある特定の既知の時間のアポイントメント)が、定量的メトリックに基づく制約に勝るかまたは優先することができると決定することができる。
【０００９】
いくつかの実装形態では、システムは、ユーザが通過した複数のナビゲーション経路の指示、どのルートセグメントが、ユーザがトレードオフを適用する可能性のあるタイプに対応するかを示す指示、また場合によっては他の信号を使用して、機械学習モデルをトレーニングすることができる。より具体的な例として、機械学習モデルをトレーニングする際、システムは、目的関数のルートセグメントを選択することが移動時間の削減の関数となる特徴を、適用することができる。
【００１０】
システムが本開示の技法を適用することのできるターゲットタイプの特定の一例が、ルートセグメントの難易度である。システムは難易度を、運転者からのフィードバックのような信号、ある時間期間にわたって報告された事故件数、道路幾何形状(例えば急カーブ、2本以上の道路の交差点、狭い車線)の解析、道路タイプ(例えば未舗装道路)の指示などを使用して、概算することができる。ターゲットタイプの別の例が、車両がルートセグメントを通過することによって発生する概算燃料排出量であり、これは、例えばルートセグメントの道路表面タイプまたは路上速度に関係する場合がある。ターゲットタイプの別の例は、ルートセグメントを通過するための通行料を支払う必要性である。システムはこの場合、代替案が利用可能なときはルートセグメントに関する余計にかかる単位時間(例えば1分間)の大まかな経済的コストを算定し、ユーザ用の定量的メトリックがこのコストを上回るかそれとも下回るかを判定することができる。
【００１１】
さらに、本開示のシステムは、ターゲットタイプのルートセグメントに基づいてナビゲーションルートの累積評価を行うことなどのさらなる特徴を実施することができる。例えば、システムは、ナビゲーションルートに関連する1つまたは複数の通行料、ナビゲーションルートの全体的な難易度、または全体的な燃料コストを概算することによって、ナビゲーションルートの全体的な経済的コストを提供することができる。システムは、これらの累積評価を、例えばナビゲーションルート候補をランク付けする際に使用することができる。そのような特徴の別の例として、システムは、システムが普通ならユーザ用に計算した定量的メトリックに鑑みてユーザに推奨しないはずであるカープーリングが、ナビゲーションルートの全体的な経済的コストを十分に削減するという状況を、自動的に識別することができる。例えば、複数乗車車両(HOV)専用車線を使用すると、時間および/またはコストの削減が可能である。
【００１２】
本開示の技法の例示的な一実施形態は、ナビゲーションサーバの1つまたは複数のプロセッサなどの処理ハードウェアによって実行され得る、ナビゲーションルートを生成するための方法である。方法は、ユーザが以前に通過した、それぞれの出発地と目的地との間の複数のルートを示すルートデータを取得することと、地図データを使用して、複数のルート内の第1のタイプのルートセグメントおよび少なくとも1つの他のタイプのルートセグメントを識別して、ルートセグメントデータを生成することと、ルートデータおよびルートセグメントデータを使用して、ユーザによるナビゲーションルートの選択の際の第1のタイプのルートのルートセグメントの属性と少なくとも1つの他のタイプのルートセグメントの属性との間のトレードオフを測定するための定量的メトリックを決定することとを含む。出発地および目的地の指示が受信されると、方法は、ルートセグメントの選択を制約するために定量的メトリックを適用することを含めて、ユーザ用の出発地と目的地との間のナビゲーションルートを生成することを含む。
【００１３】
別の例示的な実施形態は、1つまたは複数のプロセッサと、コンピュータ可読メモリとを含むシステムである。メモリは命令を格納し、命令は1つまたは複数のプロセッサによって実行されるとシステムに、ユーザが以前に通過した、それぞれの出発地と目的地との間の複数のルートを示すルートデータを取得することを行わせる。命令はさらにシステムに、地図データを使用して、複数のルート内の第1のタイプのルートセグメントおよび少なくとも1つの他のタイプのルートセグメントを識別して、ルートセグメントデータを生成することと、ルートデータおよびルートセグメントデータを使用して、ユーザによるナビゲーションルートの選択の際の第1のタイプのルートのルートセグメントと少なくとも1つの他のタイプのルートセグメントとの間のトレードオフを測定するための定量的メトリックを決定することとを行わせる。出発地および目的地の指示が受信されると、命令はシステムに、ルートセグメントの選択を制約するために定量的メトリックを適用することを含めて、ユーザ用の出発地と目的地との間のナビゲーションルートを生成することを行わせる。
【図面の簡単な説明】
【００１４】
【図１】パラメータ間のトレードオフを考慮してナビゲーションルートを生成するための技法を実施することのできるシステムのブロック図である。
【図２Ａ】図1のシステムの一コンポーネントとして動作することのできる、トレードオフコントローラがナビゲーションルート候補をランク付けするように構成されるサブシステムのブロック図である。
【図２Ｂ】図1のシステムの一コンポーネントとして動作することのできる、トレードオフコントローラを含むルートジェネレータがランク付きナビゲーションルート候補を生成するサブシステムのブロック図である。
【図３】図1のシステムにおいて実施することのできる、パラメータ間のトレードオフを示す1つまたは複数の定量的メトリックを考慮してランク付きナビゲーションルート候補を生成するための例示的な方法の流れ図である。
【図４】図1のシステムが実施することのできる全体的な通行料の計算を目的としたナビゲーションルートのセグメント化の様子を概略的に示す図である。
【図５】図1のシステムがそれを利用してパラメータ間のトレードオフを示す定量的メトリックを生成することのできる、例示的な機械学習モデルのブロック図である。
【図６Ａ】図1に示す地理的アプリケーション(geographic application)が、ある特定のナビゲーションルートに関する通行料概算値を提供するために生成することのできる、例示的なユーザインターフェーススクリーンの図である。
【図６Ｂ】図1に示す地理的アプリケーションが、複数の代替ナビゲーションルートに関するそれぞれの通行料概算値を提供するために生成することのできる、例示的なユーザインターフェーススクリーンの図である。
【図６Ｃ】図1に示す地理的アプリケーションが、ある特定のナビゲーションルートに関する通行料概算値を提供するために生成することのできる、別の例示的なユーザインターフェーススクリーンの図である。
【図６Ｄ】図1に示す地理的アプリケーションが、複数の代替ナビゲーションルートに関するそれぞれの通行料概算値を提供するために生成することのできる、例示的なユーザインターフェーススクリーンの図である。
【図６Ｅ】図1に示す地理的アプリケーションが、通行料および複数乗車車両(HOV)支払情報を提供するために生成することのできる、例示的なユーザインターフェーススクリーンの図である。
【図６Ｆ】図1に示す地理的アプリケーションがユーザに、トレードオフ設定値の調整を目的として提供することのできる、例示的なユーザインターフェーススクリーンの図である。
【図７】図1のシステムにおいて実施することのできる、パラメータ間のトレードオフを示す定量的メトリックを使用して出発地と目的地との間のナビゲーションルートを生成するための例示的な方法の流れ図である。
【図８Ａ】図1のシステムにおいて実施することのできる、単独運転者シナリオとHOVシナリオとの間のコストの差異に基づいて潜在的なカープーリングマッチングに関する信号を生成するための例示的な方法の流れ図である。
【図８Ｂ】カープーリングが関与する迂回路を含むルートオプションを概略的に示す図である。
【図８Ｃ】図1のシステムが実施することのできる、図8Bに示すオプションによる迂回路のコストを概算するための例示的な方法の流れ図である。
【図９】図1のシステムにおいて実施することのできる、有料道路に関係するリマインダを生成するための例示的な方法の流れ図である。
【発明を実施するための形態】
【００１５】
本開示は、ユーザによるナビゲーション上の決定の際のパラメータ間のトレードオフを示す定量的メトリックを計算し、適用するための技法、ならびにナビゲーション指示を生成するための他の技法について説明する。下で論じるように、定量的メトリックは、地理的サービスがどのように、時間、距離、難易度、コストなどによってパラメータ化されたナビゲーションルートを、あるパラメータの別のパラメータに対する相対的な重要性を考慮して生成すべきか、を示すことができる。地理的サービスはこのメトリックを自動的に、または明示的なユーザ入力に従って、決定することができる。
【００１６】
最初に、これらの技法を実施することのできる例示的な通信システム100について、図1を参照して論じ、それに続いて、トレードオフコントローラがナビゲーションルート候補を生成し、ランク付けする例示的なサブシステムについて、図2Aおよび図2Bを参照して論じる。
【００１７】
通信システム100は、クライアントコンピューティングデバイス102を含み、これは例えば、パーソナルコンピュータ、タブレットコンピュータやスマートフォンなどのポータブルデバイス、ウェアラブルコンピューティングデバイス、専用カーナビゲータ、車両のヘッドユニット(head unit)に埋め込まれたデバイスなどとすることができる。通信システム100は、一般に、任意の適切な数のクライアントコンピューティングデバイスを含むことができる。
【００１８】
通信システム100は、地図作成サービスおよびナビゲーションサービスのプロバイダによって運営される1つまたは複数の地理的データサーバ104をさらに含む。サーバ104は、地図データおよびナビゲーションデータをクライアントコンピューティングデバイス102および他のクライアントデバイスに提供することができる。通信システム100は、一般に、列車、バス、フェリーなどのスケジューリングおよびルーティング情報のプロバイダなど、交通機関に関係するコンテンツおよび/またはデータベースの任意の適切な数のプロバイダを含むことができる。
【００１９】
さらに、通信システム100は、ある特定の位置に関する通行料情報(例えば各種車両タイプ、時刻、曜日、占有レベルに関する料金)をサーバ104に提供することのできるサードパーティ道路情報プロバイダ106、ならびにサーバ104がそれと通信することにより、通行料支払を促進し、支払状態をチェックし、サブスクリプションを管理することなどができる、支払システム108を含むことができる。
【００２０】
サーバ104は、さまざまな地理的領域に関する地図データを格納する地図データベース140に通信可能に結合させることができる。地図データは、道路、建造物、湖、河川、公園などの地理的特徴の、形状および各種属性を指定することができる。地図データは、ベクタグラフィックス、ラスタ化画像、ラベル用テキストなど、任意の適切なフォーマットに従い、任意の適切な原則(例えばある特定のズームレベルにおいて正方形の地図タイルが同じ領域量をカバーする)に従って編成することができる。地図データは、さまざまな視点から撮影された路上の画像および写真を含むこともできる。さらに、地理的領域に関する地図データは、その地理的領域内のそれぞれに対応する位置に位置する実店舗型ビジネスについての、営業時間、製品およびサービスについての説明、ユーザレビューなどの情報を含むことができる。
【００２１】
サーバ104は道路セグメント属性データベース142にも結合され、道路セグメント属性データベース142は、さまざまな道路セグメントS1、S2などに関して、例えばさまざまな運転者によって個人の経験に基づいて報告された、または事故報告件数に基づいて決定された難易度など、ある特定の属性の指示を格納する。いくつかの実装形態では、道路セグメント属性データベース142は、ある特定のセグメントに関する通行料情報を格納する。データベース142内のレコードは、例えば、道路セグメントSiの通過には支払の必要があることを示すことができる。シナリオに応じて、レコードは、異なるタイプの車両、時刻、曜日などに関して、異なる金額を示すことができる。レコードは、通行料を徴収する当局、支払のタイプ(例えば手動ベース、電子ベース、カメラベース)、HOVディスカウントの利用可能性などを特定することもできる。さらに、レコードは、下でより詳細に論じるように、計算に適用されるルールを示すことができる。データベース142は、料金所および/または自動通行料徴収機の位置、道路入口または出口付近、グローバルポジショニングシステム(GPS)の座標などによってのような任意の適切な様式で、道路セグメントを区切ることができる。
【００２２】
さらに、サーバ104は過去ルートデータベース144に結合され、過去ルートデータベース144は、複数のユーザに関する匿名化された軌跡を格納し、軌跡はそれぞれ、位置/時間の組(tuple)から構成された時系列とすることができる。いくつかの実装形態では、ユーザは、ある特定のコントロールを操作し、かつ/またはある特定のアプリケーションをインストールし、それによって、サーバ104が自身の過去ルートデータを使用して、ルートセグメントのパラメータ間のトレードオフをユーザがどのように評価するかを示す定量的メトリックを含めて、ナビゲーションに関するユーザの嗜好を決定してよい、ということを示す。
【００２３】
より具体的な例として、データベース144内のデータは、ユーザが位置L1とL2との間を、いくつかの通行料セグメントStoll1、Stoll2、...StollNを含むナビゲーションルートに沿って移動すること、およびユーザがそのナビゲーションルートの通過に平均時間Tを費やすことを示すことができる。地理的データサーバ104は、このデータを、地図データベース140と、場合によっては他の関連データ(例えば交通データ)ソースとともに使用して、L1とL2との間の代替ナビゲーションルートは通行料セグメントを含まないが、通過に平均で別の時間量T'を必要とすると算定することができる。地理的データサーバ104はそれに応じて、全体的な通行料を時間TとT'との間の差異と比較することができる。
【００２４】
さらに、データベース144は、場合によっては、ユーザによる過去のナビゲーションルートの選択を示す、より明示的な信号を格納する。例えば、ユーザは、目的地までのナビゲーション指示を要求し、地理的データサーバ104から、あるナビゲーションルート候補は通行料を含むがそれほど時間を必要とせず、一方、別のナビゲーションルート候補は通行料を含まないがより多くの時間を必要とするといった、いくつかのナビゲーションルート候補を受信し、これらの候補の中からナビゲーションルートを明示的に選ぶことができる。一般に、ユーザは、ユーザが明示的に要求し選択したナビゲーションルートに関して、または(例えばユーザがその位置データを共有することを選んだときには)要求したナビゲーションルートとは無関係のナビゲーションルートに関して、データベース144に過去のナビゲーションルートの指示を任意の適切なフォーマットで提供することを選ぶことができる。
【００２５】
ユーザ嗜好データベース146は、ユーザによって報告された追加の嗜好を格納することができる。例えば、ユーザは、自身が通行料の回避を嗜好していることを示すように、自身の個人プロファイルを構成することができる。さらに、システム100のいくつかの実装形態では、ユーザはさらに、サーバ104がそれに基づいて道路パラメータ間のトレードオフに関する定量的メトリックを生成するルールを指定する。例えば、ユーザは、クライアントコンピューティングデバイス102を操作して、自身がN分の時間短縮につきXドル以下の通行料支払と価格評価しているとの明示的な指定をすることができる。
【００２６】
より具体的には、クライアントコンピューティングデバイス102は、1つまたは複数のプロセッサ152などの処理ハードウェア、非一時的メモリ150(例えば永続的および/または非永続的記憶コンポーネントを実装するためのハードディスク、フラッシュドライブ)、ならびにタッチスクリーン、キーボード、マイクロホンなどの入力デバイスとスクリーン、スピーカなどの出力デバイスとの任意の適切な組合せを含むことのできるユーザインターフェース154を含むことができる。メモリ150は、サーバ104からナビゲーションルートおよび他のナビゲーションデータを受信し、ユーザインターフェース154を介してナビゲーションルートを含むナビゲーション指示を提供するように構成された、地理的アプリケーション160を実施する命令を格納する。地理的アプリケーション160は、さまざまな実装形態では、対話型デジタル地図、測位情報などを提供することもできる。クライアントコンピューティングデバイス102は、クライアントコンピューティングデバイス102の位置を検出するためのグローバルポジショニングシステム(GPS)モジュール、クライアントコンピューティングデバイス102の方位を特定するためのコンパス、回転および傾きを特定するためのジャイロスコープ、加速度計など、さまざまなセンサ(煩雑にならないように図示せず)を含むこともできる。
【００２７】
いくつかのシナリオでは、クライアントデバイス102は、いわゆるプロジェクテッドモード(projected mode)で動作するように、車両のヘッドユニットに結合される。より具体的には、クライアントデバイス102は、ヘッドユニットに組み込まれたタッチスクリーン、車両内のスピーカなどを介して、出力を提供し、それに応じて、タッチスクリーン、ヘッドユニットに組み込まれたマイクロホンなどを介して、入力を受領することができる。クライアントデバイス102およびヘッドユニットは、ユニバーサルシリアルバス(USB)リンク、Bluetooth(登録商標)または別の適切なワイヤレスパーソナルエリアネットワーク(WPAN)リンク、WiFi(登録商標)または別の適切なワイヤレスローカルエリアネットワーク(WLAN)リンクなど、短距離の有線通信リンクまたはワイヤレス通信リンクを介して、通信することができる。
【００２８】
引き続き図1を参照すると、サーバ104は、クラウドソーシング技法を実施し、運転者から道路セグメント属性の指示を受信する。例えば、車両120A、120B、120Cなどの運転者は、それらが遭遇する通行料を、ポータブルデバイスを使用して(例えば地理的アプリケーション160に類似の地理的アプリケーション124A、124Bを介して)、または対応する車両に組み込まれたコンポーネント124Cを使用して、報告することができる。より一般には、サーバ104は、サードパーティフィード、道路上に設置されたセンサ、道路標識または電子料金収受(ETC)設備を識別すべくクライアントデバイスまたはダッシュボードカメラによって捕捉された画像を処理するイメージングソフトウェアなど、任意の適切なソースから、道路セグメント属性に関する情報を受信することができる。
【００２９】
サーバ104、サードパーティ道路情報プロバイダ106、および支払システム108は、ネットワーク110を介して相互接続することができ、ネットワーク110は、例えばインターネットなどの広域ネットワークとすることができ、有線通信リンクおよび/またはワイヤレス通信リンクを含むことができる。クライアントコンピューティングデバイス102も、ネットワーク110を介してサーバ104にアクセスすることができ、車両120A、120B、120C、および/またはこれらの車両内で動作するポータブルデバイスは、ネットワーク110を介してサーバ104にアクセスすることができる。
【００３０】
図1に示すように、サーバ104は、パラメータ概算モジュール172とトレードオフコントローラ174とを含むルーティングエンジン170を含むことができる。動作の際には、モジュール172が、さまざまな道路セグメント、または道路セグメントを含む経路に関する、概算値を生成する。例えば、モジュール172は、通行料徴収に関連するいくつかの道路セグメントの通過にかかる経済的コストを概算し、または運転者が過去にそれに関して難易度を報告したいくつかのセグメントを含むルートの全体的な難易度を概算することができる。ルーティングエンジン170は、指定された出発地および目的地に関するナビゲーションルートを、トレードオフコントローラ174を使用して道路パラメータ間の関係(例えば時間と難易度、時間とコスト)を考慮してナビゲーションルートの選択を制約することによって、生成する。
【００３１】
さらに分かりやすくするために、図2Aおよび図2Bは、トレードオフコントローラを含むサブシステムのいくつかの例示的な実装形態を示す。これらのサブシステムのコンポーネントは、ハードウェア、ソフトウェア、ファームウェア、またはハードウェアと、ソフトウェアと、ファームウェアとの任意の適切な組合せを使用して、実装することができる。
【００３２】
最初に図2Aを参照すると、サブシステム200Aは、ルートジェネレータ202Aに結合されたトレードオフコントローラ204Aおよび通行料概算モジュール206Aを含む。ルートジェネレータ202Aおよび通行料概算モジュール206Aはそれぞれ、トレードオフコントローラ174およびパラメータ概算モジュール172として動作することができ、図2Aに示す他のモジュールも、図1のルーティングエンジン170のコンポーネントとして動作することができる。下でより詳細に論じるように、トレードオフコントローラ204Aは、ルートジェネレータ202Aが出力したナビゲーションルート候補をランク付けするように構成される。
【００３３】
具体的には、ルートジェネレータ202Aは、例えば出発地および目的地信号210、要求時間212、カープーリング情報214などを含む、ユーザのナビゲーション指示要求を表す信号を受信する。ルートジェネレータ202Aは、例えば地図データ220、交通データ222、気象データ224、燃料価格データ226(1回または複数回のガソリンタンク補充を必要とするのに十分なほどルートが長い場合)など、ユーザに固有ではない信号も受信する。一般に、ルートジェネレータ202Aは、より少ない信号を使用することもでき、あるいは反対に、ユーザの車両の燃料状態、給油所の位置、燃料消費など、任意数の追加の信号を、使用することもできる。トレードオフコントローラ204Aは、入力として、ナビゲーション指示要求に関連するタイミング要件216(例えば「目的地に午後3:00までに到着しなければならない」)、ルートジェネレータ202Aが出力したルート候補240、および通行料概算モジュール206Aがルート候補240に基づいて生成した概算値242を受領する。さらに、サブシステム200Aは、ユーザ嗜好機械学習モデル230を利用して、道路の難易度と時間との間の、または通行料金額と時間と間のトレードオフを測定するための定量的メトリックなど、ユーザ用の1つまたは複数の定量的メトリックを概算することができる。ユーザ嗜好機械学習モデル230は、この例示的な実装形態では、トレードオフコントローラ204Aに1つまたは複数のメトリックを追加の入力232として提供する。トレードオフコントローラ204Aは、ルート候補240に基づいて、またユーザメトリック232を考慮して、ランク付きルート候補250Aを生成する。
【００３４】
動作の際には、ルートジェネレータ202Aが、信号210によって指定された出発地と目的地との間のいくつかのナビゲーションルート候補R1、R2、...RNを生成することができる。この目的のために、ルートジェネレータ202Aは、(地図データ220において提供される)実世界の地理の表現物を使用して位置間の経路を特定するための任意の適切な技法を適用することができ、またナビゲーションルート候補R1、R2、...RNを例えば時間または距離の点から最適化しようと試みることができる。ルートジェネレータ202Aは、特に要求時間(信号212)に関してルートを最適化するために、(信号222を使用して)交通などの実時間因子を補償することができる。いくつかの実装形態では、ルートジェネレータ202Aは、燃料価格データ226およびカープーリング情報214も、ルート候補を特定するための追加の重みとして適用する。
【００３５】
ユーザ嗜好機械学習モデル230によって出力されるユーザメトリック232は、ある特定のパラメータ(例えばルート難易度、コスト)の、別のパラメータ(例えば時間)に対して特定的に測定された推定重みを示すことができる。したがって、例えば、機械学習モデル230は、ユーザがN分の時間短縮をXドルと価格評価していることを示すユーザメトリック232を生成することができる。下で図5を参照してより詳細に論じるように、機械学習モデル230はこの信号を、ユーザが以前に通過したナビゲーション経路に関係するさまざまな信号のセットに基づいて生成することができる。あるいは、別のコンポーネントが、入力232をアルゴリズム的に(例えばある特定数値の通行料と対応する短縮される分(minute)の数値との比を計算することによって)生成する。さらに別の代替手段として、地理的アプリケーション160などのソフトウェアアプリケーションが、ユーザメトリック232をユーザ入力に基づいて生成することができる。
【００３６】
いくつかの実装形態では、モデル230が、ユーザメトリック232の一部として、コンテキスト固有メトリックのセットを生成する。例えば、モデル230は、ユーザが相対的に長い経路(例えば50マイル以上)を通過するときの時間とコストとの間のトレードオフに関するあるメトリック、およびユーザが相対的に短い距離を通過するときの時間とコストとの間のトレードオフに関する別のメトリックを生成することができる。これらの複数のメトリックは、ある特定の例示的なユーザに関して、一方では移動が長いときにコストを削減することを優先する嗜好、他方では移動が短いときに時間を削減することを優先する嗜好を、より良好に反映させることができる。別の例として、モデル230は、ユーザが日中運転するときの時間とルート難易度との間のトレードオフに関するあるメトリック、およびユーザが夜間に運転するときの時間とルート難易度との間のトレードオフに関する別のメトリックを生成することができる。例えば、ある特定のユーザが、暗くなると、事故が起こりやすいルートセグメント上での運転を回避することを嗜好する場合があるが、この同じユーザは、日中(または空が曇っていないとき)に類似のルートセグメント上を運転することは構わない。
【００３７】
図2Bは、サブシステム200Bを示し、サブシステム200Bは、サブシステム200Aに概して類似しているが、本実装形態では、ルートジェネレータ202Bが通行料概算モジュール206Bおよびトレードオフコントローラ204Bを含んでいる。ルートジェネレータ202Bおよび通行料概算モジュール206Bはそれぞれ、トレードオフコントローラ174およびパラメータ概算モジュール172として動作することができ、図2Bに示す他のモジュールも、図1のルーティングエンジン170のコンポーネントとして動作することができる。図2Aの実装形態とは異なり、トレードオフコントローラ204Bおよび通行料概算モジュール206Bは、ルートジェネレータ202Bのコンポーネントとして、ランク付きルート候補250Bを生成するように動作する。換言すれば、本実装形態におけるルートジェネレータ202Bは、トレードオフコントローラ204Bの出力を使用して、ルート候補250Bを選択し、ランク付けする。
【００３８】
いくつかのシナリオでは、モデル230は、ユーザに関するデータが欠如しているため、ユーザ固有メトリック232を生成することができない。トレードオフコントローラ134Aまたは134Bは、これらの場合、他のユーザの嗜好を使用して、ユーザメトリックの初期値を決定することができる。例えば、トレードオフコントローラ134Aまたは134Bは、ある特定の出発地およびある特定の目的地に関して、ユーザの76%がより安いルートよりもより速いルートのほうを嗜好するとの判定をし、メトリック232をこの値に初期設定することができる。
【００３９】
次に図3を参照すると、パラメータ間のトレードオフを示す1つまたは複数の定量的メトリックを考慮してランク付きナビゲーションルート候補を生成するための例示的な方法300は、地理的データサーバ104または別の適切なデバイスもしくはデバイスグループにおいて実施することができる(便宜上、この方法については下で地理的データサーバ104を参照して説明する)。方法300は、1つまたは複数のプロセッサなどの処理ハードウェアによって実行可能な命令のセットとして実施することができる。
【００４０】
ブロック302において、地理的データサーバ104が、ナビゲーション指示要求を受信する。要求は、出発地および目的地を任意の適切なフォーマット(例えば関心地点、住所、GPS座標)で示すことができる。いくつかのシナリオでは、クライアントデバイス102が、ユーザが明示的または黙示的に(例えば対話型地図上で関心地点を選択することによって)初期のナビゲーション指示要求をサブミットしたときに、ナビゲーション指示要求を生成する。他のシナリオでは、クライアントデバイス102は、以前に受信したナビゲーション指示にクライアントコンピューティングデバイス102が従っている間に、定期的に、または事故による速度急低下や事故などの事象に応答して、更新されたナビゲーション指示要求を生成する。さらに、クライアントデバイス102のユーザは、場合によっては、ルートに別の立寄地を追加するか、その他の方法でルートを修正することを選ぶことができ、クライアントデバイス102はそれに応じて、新たなパラメータを含む更新された要求を地理的データサーバ104に送信することができる。さらに、図6Fを参照してより一層論じるように、ユーザは、1つまたは複数のトレードオフを修正する(例えば暗くなってきたので安全なルートの重要性を時間が経つにつれて上げる)ことを選ぶことができる。
【００４１】
次に、ブロック304において、地理的データサーバ104は、要求された到着時間などのタイミング要件、および/または例えばカープーリングパートナーの潜在的な存在など、他のコンテキスト信号を受信する。
【００４２】
次に、ブロック306において、地理的データサーバ104は、ルートパラメータ間のトレードオフの、1つまたは複数のユーザ固有定量的メトリックを取得する。上で論じたように、この定量的メトリックは、時間などのあるパラメータがコストなどの別のパラメータにどのように関係するかを測定することができる。換言すれば、地理的データサーバ104は、ナビゲーションルートの選択を、あるパラメータを別のパラメータの点から表現する関数によって、制約することができる。次いで、ブロック308において、地理的データサーバ104は、1つまたは複数のメトリックを考慮して、ルート候補を生成し、ランク付けする。次いで、地理的データサーバ104は、ランク付きルート候補をクライアントコンピューティングデバイス102などのデバイスに、例えば地理的アプリケーション160によってユーザに表示するために、送信することができる。
【００４３】
図4は、図1のパラメータ概算モジュール172または別の適切なモジュールが実施することのできる全体的な通行料の計算を目的とした出発地402と目的地404との間のナビゲーションルート406Aのセグメント化の様子を概略的に示す。ナビゲーションルート406Aは、通過にある特定の時間量T1を必要とし、通行料に関連するいくつかの区間、具体的には区間410、412、および414を含む。図4は、同じ出発地402と同じ目的地404との間の代替ルート406Bも示す。代替ルート406Bは、通行料徴収に関連する区間を含まないが、通過に平均でより多くの時間(T2)を必要とする。
【００４４】
いくつかのシナリオでは、サーバ104は、地図データベース140および道路セグメント属性データベース142内の情報を使用して、ナビゲーションルート406Aおよび406Bの表現物を生成する。過去ルートデータ144が、ユーザがナビゲーションルート406Aおよび/またはナビゲーションルート406Bを通過したことを示す指示を含むとき、サーバ104は、ナビゲーションルート406Aおよび406Bに関して、時間T1とT2、ならびにそれぞれの通行料支払があればそれを、比較することができる。サーバ104は、これらの差異を、ユーザ用のコストと時間との間のトレードオフを測定する定量的メトリックを計算する際のデータ点のうちの1つとして使用することができる。
【００４５】
セグメント410、412、および414の全体的なコストを算定するために、概算モジュール172は、適用可能な価格設定モデルを選択することができる。一例として、概算モジュール172は、固定通行料モデルを適用することができ、そのモデルによれば、各セグメント410、412、および414に関連するそれぞれの固定コストがある。概算モジュール172がインクリメンタル通行料モデルを適用するとき、ユーザが支払う予定の全体的な金額は、ユーザがどれだけ多くの時間を道路上で過ごすか、かつ/または運転者がどれだけ多くの連続するセグメントを通過するかに従って変化する。したがって、例えば、一連のセグメント410、412、および414を含む、全体ルート406Aのセグメントの通過にかかるコストは、各セグメント410、412、および414の個別の通過にかかるコストの和よりも高額になることがある。
【００４６】
さらに、概算モジュール172は、場合によっては、動的通行料モデルを適用することができ、そのモデルによれば、コストは特定の時間における交通状況に応じて変わる。より具体的な例として、セグメント410に関する通行料は、例えば、交通量の増加とともに増加し、したがって交通量の減少とともに減少することがある。さらに、通行料は、ユーザの車両内に複数の乗員がいるかどうかに応じて変わる(例えばユーザがカープーリングに参加すると減少する)ことがある。
【００４７】
さらに、概算モジュール172は、車両タイプ(例えば自動車のサイズによって金額が異なる、ハイブリッドまたは電気自動車の場合には通行料がより低額であるかまたは全くない、モータサイクルの場合には通行料がより低額であるかまたは全くない、トラックの場合には通行料がより高額である)、一部のユーザが有していることがある、支払サービスに対する特別な許可および/またはサブスクリプション、曜日(例えば週末には通行料がより低額である)、時刻、祝祭日などの特別な日など、追加の信号を考慮して、通行料金額を概算することができる。
【００４８】
いずれにせよ、ナビゲーションルート406Aがユーザのナビゲーション指示要求に対応するときに、概算モジュール172は、図4の例において、ナビゲーションルート406Aに関する通行料支払の概算値を生成することができ、地理的アプリケーションが、ユーザインターフェース154(図6Aを参照されたい)を介して、通行料の概算合計を表示することができる。一方で、ナビゲーションルート406Aが、ユーザが以前に通過したルートに対応するときにも、概算モジュール172は同様に、合計の通行料金額を概算することができる(下の図5を参照されたい)。
【００４９】
図4のシナリオには、道路上で徴収される通行料のみが関与するが、一般に、概算モジュール172は、他の移動モードならびに多モードナビゲーションルートに関する概算値を生成することができる。そのような多モードナビゲーション指示の一例には、自動車によって通過されるセグメントおよび車両がフェリーによって輸送される別のセグメントが含まれる。他の例は、クライアントデバイス102のユーザがそれに従って、ルートの一部分を公共交通機関を使用して通過し、別の部分を徒歩で通過する、ルートの一部分を運転し、別の部分を公共交通機関を使用して通過する、ルートの一部分を自転車で行き、別の部分を徒歩で行く、などの、ナビゲーション指示を含むことができる。これらの場合、概算モジュール172は、上で論じたモデルの任意の適切な組合せを適用することができる。
【００５０】
次に、図5を参照すると、ルーティングエンジン170は、いくつかの実装形態では、(図2Aおよび図2Bに示すようにユーザメトリックをトレードオフコントローラに提供することのできる)ユーザ嗜好機械学習モデル230を、さまざまな入力信号、対応するラベル、ユーザフィードバックデータなどを使用してトレーニングする。ルーティングエンジン170は、過去ルートデータベース144からさまざまな入力をトレーニングデータとして受領し、このデータを、特徴抽出関数502を介してモデル230に適用することができる。
【００５１】
例えば、特徴抽出関数502は、位置間のルート(信号510)、ユーザがルートを通過したときの時間を示す指示(信号512)、ルートの全体的なコストの概算値(信号514)、ルートを通過する際にユーザがHOV専用車線を使用したかどうか、またその際のHOV価格設定などを示すカープーリング情報(信号520)、ユーザがルートを通過したときの時刻(信号522)、ユーザがルートを通過した時点の気象(信号524)などを受領することができる。特徴抽出関数502は、信号510、512、520、522、524などを、ユーザが通過した過去ルートを表すデータの一部として受領することができる。概算コスト信号514を生成するために、パラメータ概算モジュール172は、上で図4を参照して論じたような適切な通行料計算技法を適用することができる。他のシナリオでは、コスト信号514は、ユーザによって報告された金額に対応する。より一般には、特徴抽出関数502は、ルート、または移動が行われたコンテキストに直接関係する、任意数のパラメータを受領することができる。
【００５２】
モデル230をより効率的にトレーニングするために(すなわち高信頼の予測値により迅速に収束するために)、特徴抽出関数502は、例示的な一実装形態では、(時間パラメータとコストパラメータを別々に補償するのではなく、または別々に補償することに加えて)時間パラメータ時間とコストパラメータとの間の関係を補償する特徴ベクトル504を生成する。したがって、特徴抽出関数502は、モデル230を関数F(コスト,時間)を使用してトレーニングするものと見なすことができる。特徴ベクトル504は、この特定の例では、要素として出発地および目的地(L1、L2)の組、位置L1とL2との間の、通行料を含むナビゲーションルートを使用した移動に関連する時間、位置L1とL2との間の、通行料を含むナビゲーションルートを使用した移動に関連するコスト、位置L1とL2との間の、通行料を含まないナビゲーションルートを使用した移動に関連する時間、位置L1とL2との間の、通行料を含まないナビゲーションルートを使用した移動に関連するコスト、および例えば移動時間などのコンテキスト信号を含むベクトルである。特徴ベクトル504は、ユーザが通行料ありのナビゲーションルートを選んだか、それとも通行料無料のルートを選んだかを示す指示などのラベルを含むことができる。
【００５３】
ルーティングエンジン170は、モデル230を、特徴ベクトル504の複数のインスタンス、ならびに地図データ220および/または全てのユーザにとって共通の他のデータを使用して、トレーニングすることができる。ルーティングエンジン170は、時間とコストとの間のトレードオフを測定するための定量的メトリック232を生成することができる。モデル230は、ユーザが将来的にいくつかのルート候補の中からどのナビゲーションルートを選択するかについての予測530を生成することもできる。フィードバック処理540が、(例えば予測の後でユーザがどのオプションを選択したかを示す指示を処理することによって)予測530の質を評価し、フィードバックデータを特徴抽出関数502に提供して、モデル230をトレーニングし続けることができる。
【００５４】
いくつかの実装形態では、モデル230はまた、ユーザに関する過去ルートデータに基づいて、ユーザが将来的に、ある特定の時間期間の間に通行料として支払うことになる可能性のある金額を概算する。地理的データサーバ104は、この概算値を支払システム108から受領したパスまたはサブスクリプションの価格と自動的に比較し、場合によっては、ユーザのために、通行料支払プランに加入するという提案を生成することができる。より一般には、モデル230は、サーバ104がそれに基づいてユーザにとって最適な有料道路の計画を決定することのできる予測を生成することができる。
【００５５】
図6Aは、地理的アプリケーション160が、ナビゲーションルートに関する通行料概算値を提供するために生成することのできる、例示的なユーザインターフェーススクリーン602である。図6Aに示すように、ユーザインターフェーススクリーン602は、運転者が目的地へと向かう途中で支払う予定の全体的な概算通行料の指示を含む。地理的データサーバ104は、ナビゲーションルートが通行料を含むという指示を単に提供するのではなく、(例えば図4を参照して論じた技法を使用して)ルートの全体的なコストを概算し、その概算値を地理的データサーバ104に、ユーザインターフェース154を介して表示するために提供する。
【００５６】
図6Bの例示的なユーザインターフェーススクリーン604は、複数の代替ナビゲーションルートに関するそれぞれの通行料概算値を含む。図6Bに示すように、第3のナビゲーションルート候補は、車両内に3人以上の場合のHOVオプションを含む。図6Cは、地理的アプリケーション160が、ある特定のナビゲーションルートに関する通行料概算値を提供するために生成することのできる、別の例示的なユーザインターフェーススクリーン606を示し、図6Dは、地理的アプリケーション160が、複数の代替ナビゲーションルートに関するそれぞれの通行料概算値を提供するために生成することのできる、例示的なユーザインターフェーススクリーン608である。図6Eは、地理的アプリケーション160が、通行料および複数乗車車両(HOV)支払情報を提供するために生成することのできる、例示的なユーザインターフェーススクリーン610である。
【００５７】
図6Fを参照すると、地理的アプリケーション160は、ユーザがそれを介してトレードオフに関する自身の嗜好を指定することのできる対話型コントロール620〜626を含む、ユーザインターフェーススクリーン612を生成することができる。この例示的な実装形態では、ユーザは、時間と通行料コストとの間、時間と距離との間、時間とカーボンフットプリントとの間、時間と困難な気象状況下での運転との間の、トレードオフの数値表現を調整することができる。より一般には、地理的アプリケーション160は、ルートセグメントの任意のパラメータ対(または3つ以上のパラメータのグループ)に関するトレードオフコントロールを提供することができる。この例示的な実装形態では、ユーザは、仮想ノブを回転させて、あるパラメータの別のパラメータに対する相対的な重要性を指定することができる。ユーザは、図6に示すシナリオにおいて、仮想ノブ620を操作して、時間のほうが通行料よりも大いに重要であるとの指定をしている。ユーザは、仮想ノブ620を反時計回りに回転させて、時間を通行料よりもさらに重要にすることもでき、あるいは反対に、仮想ノブ620を時計回りに回転させて、時間が重要性の点で通行料と同等であるとの、または通行料のほうが時間よりも重要であるとの指定をすることもできる。仮想ノブ620〜626は、一般に、ユーザが任意数の中間値を任意の所望の粒度で指定することを、可能にすることができる。
【００５８】
地理的アプリケーション160がユーザインターフェーススクリーン612をユーザに提供する際、地理的アプリケーション160は、ユーザが通過した過去のナビゲーションルートの指示を使用して地理的データサーバ104が生成した定量的メトリックに基づく、仮想ノブ620〜626のそれぞれについての初期設定値を取得することができる。例えば、トレードオフコントローラ204Aは、1つまたは複数のメトリック232を生成し、これらのメトリックを、クライアントデバイス102上で実行される地理的アプリケーション160に提供することができる。次いで、地理的アプリケーション160は、ノブ620〜626を、これらのメトリックに対応する初期設定値を用いて表示することができる。ユーザは、これらの設定値を受容することもでき、あるいは設定値のうちの1つまたは複数を手動で修正し、それにより、対応するトレードオフの定量的メトリックを調整することもできる。次いで、地理的アプリケーション160は、新たな定量的メトリックを地理的データサーバ104に送信することができる。
【００５９】
地理的アプリケーション160はユーザインターフェーススクリーン612を、ユーザがナビゲーション指示要求をサブミットする前に、または特定のナビゲーションルートに関連して、提供することができる。後者の場合、地理的アプリケーション160は、要求のコンテキストを考慮して、ノブ620〜626のうちのどれを表示すべきか、またどの初期設定値を用いるか、を決定することができる。上で示したように、トレードオフコントローラ134は、ルートの距離、時刻、曜日、自動車内の乗員数、ユーザのカレンダが目的地におけるイベントを含むかどうかなどを考慮して、同一パラメータ対間のトレードオフの、異なるメトリックを適用することができる。
【００６０】
次いで、地理的データサーバ104および/または地理的アプリケーション160が実施することのできるいくつかの例示的な方法について、次に図7〜図9を参照して論じる。
【００６１】
最初に図7を参照すると、ルーティングエンジン170は、パラメータ間のトレードオフを示す定量的メトリックを使用して出発地と目的地との間のナビゲーションルートを生成するための例示的な方法700を実施することができる。
【００６２】
ブロック702において、ルーティングエンジン170は、ユーザが以前に通過したルートを示すルートデータを取得する。この目的のために、ルーティングエンジンは、過去ルートデータベース144を使用することができる。ある特定のルートに関して、ルートデータは、出発地、目的地、出発地と目的地との間の一連のルートセグメントなどを指定することができる。ルートデータは、場合によっては、ルートが関連するコンテキスト、例えばユーザがルートに沿って移動した時刻、曜日、同乗者の有無などの指示も含む。
【００６３】
次に、ブロック704において、ルーティングエンジン170は、ある特定のタイプのルートセグメントならびに少なくとも1つの他のタイプのセグメントを識別する。例えば、ルーティングエンジン170は、幾何形状(例えば平均よりもある特定のパーセンテージだけ狭い車線、ある特定のしきい値を上回る道路の曲率、交差点において車道が一点に集まる、ある特定のしきい値よりも小さい角度)のため困難なルートセグメント、ならびに困難ではない車線をそれぞれ識別して、第1のタイプおよび別のタイプを定めることができる。別の例として、ルーティングエンジン170は、通行料に関連するルートセグメントならびに通行料無料のルートセグメントを識別することができる。
【００６４】
ブロック706において、ルーティングエンジン170は、ルートデータおよびルートセグメントデータを使用して、これらの異なるタイプのルートセグメントの選択間のトレードオフの定量的メトリックを生成することができる。トレードオフは、全体的な時間、コスト、難易度など、結果として得られるナビゲーションルートの属性に対応することができる。より具体的な例として、トレードオフの定量的メトリックは、ユーザが時間を節約するために受容する傾向にあるルート難易度の関数F1、すなわちF1(難易度,時間)とすることができる。別の例として、トレードオフの定量的メトリックは、ユーザが同様に移動時間を削減するために支払う意向のあるコストの関数F2、すなわちF2(コスト,時間)とすることができる。ルーティングエンジン170は、図5を参照して論じたような機械学習技法、適切なアルゴリズム、または明示的なユーザ入力を実施して、定量的メトリックを生成することができる。より一般には、定量的メトリックは、ナビゲーションルートの任意の属性対間の関係を表すことができる。
【００６５】
次に、ブロック708において、ルーティングエンジン170は、ある特定の出発地から目的地までのナビゲーション指示要求を受信する。さまざまなシナリオでは、要求は、例えばタイミング制約などの追加の信号を含むことができる。次いで、ブロック710において、ルーティングエンジン170は、ナビゲーションルートを生成する。ルーティングエンジン170は、ナビゲーションルートの選択を制約するために定量的メトリックを適用する。例えば、上で図2Aおよび図2Bを参照して論じたように、ルーティングエンジンは、ナビゲーションルート候補を生成し、トレードオフコントローラを使用して、定量的メトリックを考慮してナビゲーションルート候補のランキングを生成するか、またはトレードオフコントローラを使用して、定量的メトリックを他の信号とともに適用し、それによって、ナビゲーションルート候補を生成することができる。
【００６６】
次に図8Aを参照すると、地理的データサーバ104は、単独運転者シナリオとHOVシナリオとの間のコストの差異に基づいて潜在的なカープールマッチングに関する信号を生成するための方法800を実施することができる。方法800は、サーバ104が出発地から目的地までのナビゲーションルートを生成するブロック802から開始する。次いで、ブロック804において、サーバ104は、ユーザが単独で運転しているという仮定に従って、ナビゲーションルートの全体的なコストを計算する。ブロック806において、サーバ104は、ナビゲーションルートがHOV専用車線を含むかどうかを判定し、含む場合、フローはブロック808に進む。そうでない場合、フローは直接ブロック816に進む。
【００６７】
ブロック808において、サーバ104は、ナビゲーションルートの全体的なコストを、今回はユーザの車両が複数乗車車両になるという仮定に従って計算する。ブロック810において、サーバ104は、ブロック804において計算されたコスト概算値とブロック808において計算されたコスト概算値との間の差異を計算する。ブロック812において、サーバ104が、ある特定のしきい値を差異が超えると判定した場合、フローはブロック814に進み、そうでない場合、フローはブロック816に進む。ブロック814において、サーバ104は、潜在的なカープールマッチングに関する信号を生成する。例えば、サーバ104はユーザのために、ユーザがカープーリングに参加した場合にルートのコストが減少し得る分の金額を示す提案を生成することができる。いくつかの実装形態では、ブロック812において、サーバ104は、コストの差異を利用するだけではなく、いくつかのパラメータ間の関係を示す定量的メトリックも適用することができる。
【００６８】
サーバ104は、さまざまなナビゲーションルート候補および/またはさまざまなカープールの相手候補を得るために、方法800を複数回実施することができる。したがって、例えば、サーバ104は、カープーリングが関与し、時間またはコストの点から単独運転者ルートに比べて有利な、2つ以上のルート候補を特定することができる。次いで、サーバ104は、これらの候補の中から、提案されたナビゲーションルートを選択することができる。
【００６９】
次に、時間または距離の点から迂回路のコストを概算するための例示的な方法について、図8C、および図8Bのいくつかのルートオプションの概略図を参照して論じる。図8Bの例示的な方式830によれば、ユーザは、起点832と目的地834との間を、直接的に(ルートRDに沿って)、または1つもしくは複数のピックアップ位置およびドロップオフ位置を経由して間接的に(ルートRIに沿って)、移動することができる。この例では、ユーザは、起点832からピックアップ位置842まで移動して同乗者をピックアップし、ドロップオフ位置844においてその同乗者をドロップオフし、引き続き目的地834へと向かうことができる。より一般には、間接的ルートRIは、任意の適切な数のピックアップ位置およびドロップオフ位置を含むことができる。
【００７０】
直接的ルートRDおよび間接的ルートRIのそれぞれについて、ルーティングエンジン170は、起点832と目的地834との間の距離、起点832と目的地834との間の移動時間、起点832と目的地834との間を移動するのにかかるコストなどのうちの1つまたは複数を算定することができる。ルーティングエンジン170は、これらの概算値を使用して、直接的ルートと、カープーリングの関与する間接的ルートとの間のトレードオフを評価することができる。
【００７１】
図8Cを参照すると、ルーティングエンジン170は、1つまたは複数のプロセッサなどの処理ハードウェアによって実行可能な命令のセットとしての例示的な方法850を実施することができる。便宜上、この方法については下で地理的データサーバ104を参照して、より具体的にはルーティングエンジン170を参照して論じる。
【００７２】
方法850は、ルーティングエンジン170が出発地(または起点)、目的地、少なくとも1つのピックアップ位置、および少なくとも1つのドロップオフ位置の指示を受信するブロック852から開始する。例えば、ルーティングエンジン170は、位置832、834、842、および844の住所、座標、または他の任意の適切な指示を受信することができる。ルーティングエンジン170は、一般に、ユーザがそれを介して乗車を募ることのできるライドシェアサービスなど、任意の適切なソースから、位置842および844の指示を受信することができる。1つのそのような例として、ルーティングエンジン170とは独立して動作しているライドシェアサービスが、ルーティングエンジン170に、適切なAPIを介して、ある特定の時間期間内のピックアップ位置842とドロップオフ位置844との間の移動に関するライドシェアマッチを探し出せとの要求を行うことができる。ルーティングエンジン170は、位置832と834との間を移動しているユーザが、ライドシェアリングに自身が参加したいという要望を示しているかどうかを判定し、次いで、上で論じたように位置842および844を経由した迂回路に関連するトレードオフを決定することができる。いくつかの実装形態では、ルーティングエンジン170はこの解析を、運転者および潜在的なライドシェアの相手が、ソーシャルグラフ上で互いにある特定の距離内にいる場合にのみ実施する。
【００７３】
別の例として、ルーティングエンジン170は、ソーシャルグラフ内である特定の近さにある2人のユーザが、互いにある特定の時間期間内に、近接する出発地から近接する目的地まで移動しようとしているところであるとの判定をすることができる。この目的のために、ルーティングエンジン170は、この2人のユーザがカープーリングに参加したいという自身の意向を示しているかどうかをチェックする。
【００７４】
より具体的な例として、起点832から目的地834まで移動しようと計画しているユーザは、潜在的なカープールマッチングを嗜好することを示すように自身のプロファイルを構成することができる。図6Fを再度参照すると、地理的アプリケーション160はユーザに、仮想ノブ620、622などに概して類似した、コストとカープーリングとの間のトレードオフを指定するためのインターフェースを提示することができる。したがって、例えば、ユーザは、単独での乗車を一般に嗜好することを示すことができ、この場合、カープーリングは、節約が単独での乗車に比べて少なくとも30%という金額になるときに受容可能なオプションとなる。別の実装形態では、ユーザは単に、自身がカープーリングを考慮に入れる意向があるかどうかを示す。さらに、ユーザは、ソーシャルグラフ上でのライドシェアの相手の近さに制限を設けることができる。
【００７５】
ブロック854において、ルーティングエンジン170は、例示的な一実装形態では、起点と目的地との間の直接的移動時間TDを概算する。次に、ブロック856において、ルーティングエンジン170は、ピックアップ位置およびドロップオフ位置を経由した起点と目的地との間の間接的移動時間TIを概算する。ルーティングエンジン170は、別の実装形態では、移動時間の代わりに、またはそれに加えて、直接的移動距離DDおよび間接的移動距離DIを概算する。より一般には、ルーティングエンジン170は、直接的ルートRDと間接的ルートRIを比較するための任意の適切な定量的メトリックを生成することができる。
【００７６】
ブロック858において、ルーティングエンジン170は、ブロック854および856において算定された概算値を使用して、ピックアップ位置およびドロップオフ位置を経由した迂回路CDETOURのコストを算定することができる。例示的な一実装形態では、ルーティングエンジン170は、例えばTDとTIとの間、またはDDとDIとの間の差異および/または比を計算する。別の例示的な実装形態では、ルーティングエンジン170は、TDとTIとの間、DDとDIとの間などの比を計算する。ユーザがカープーリングをしている際の通行料のコストを計算するために、ルーティングエンジン170は、個別運転者に適したモデルとは異なるモデルを適用することができる。
【００７７】
いずれにしても、次いで、ルーティングエンジン170は、CDETOURの算定されたコストを使用して、地理的データサーバ104が潜在的なカープールマッチングに関する信号を生成すべきかどうかを判定することができる。ルーティングエンジン170がこの信号を生成するシナリオでは、地理的データサーバ104は、潜在的なカープールの相手の指示をユーザに提供することができる。ルーティングエンジン170は、いくつかの実装形態では、潜在的なカープールの相手に関する通知も自動的に生成し、ユーザは、例えば地理的アプリケーション160を介して、ルーティングエンジン170がこれらの通知を特定された潜在的なカープールの相手に送信することを要求することができる。
【００７８】
図9は、地理的アプリケーション160が実施することのできる、有料道路に関係するリマインダを生成するための例示的な方法900のフロー図である。ブロック902において、地理的アプリケーション160は、ユーザが通行料システムに関連するルートセグメントを通過したとの判定をすることができる。例えば、クライアントコンピューティングデバイス102のユーザが、ある特定のコントロールを操作して、地理的アプリケーション160がユーザの現在の位置を特定できるようにすることができる。より具体的な例として、地理的アプリケーション160は、サーバ104からナビゲーション指示を受信し、対話型デジタル地図の上にナビゲーションルートを表示している間に、ユーザが通行料に関連するセグメントに到着したとの判定をすることができる。
【００７９】
ブロック904において、地理的アプリケーション160は、通行料セグメントの通過のタイムスタンプ付き記録を生成することができる。地理的アプリケーション160は、この記録をメモリ150内に格納することができる。地理的アプリケーション160はまた、ブロック906において、通行料を支払うようにとのリマインダを生成するためのタイマ(例えば1時間、3時間、10時間)をセットすることができる。地理的アプリケーション160は、例えば、深夜または早朝の通知をさせないように、時刻に基づいてタイマ期間を調整することができる。ブロック908において、地理的アプリケーション160はタイマ満了を検出し、ブロック910において、通行料を支払うようにとのリマインダを出す。
【００８０】
あるいは、地理的アプリケーション160は、ネットワーク110を介して支払システム108に自動的にコンタクトし、支払を電子的に行うことができる。地理的アプリケーション160は、支払システム108に実時間で(すなわちユーザの車両が通行料のかかるルートセグメントを通過するときに、または例えば固定のスケジュールに従って)コンタクトすることができる。
【００８１】
追加の考慮事項
以下の追加の考慮事項は、前述の議論に適用される。本明細書全体を通して、複数のインスタンスは、単一のインスタンスとして説明したコンポーネント、動作、または構造を実装してもよい。1つまたは複数の方法の個別の動作については、別々の動作として図示し説明しているが、個別の動作のうちの1つまたは複数は同時に実施されてもよく、動作を図示の順序で実施することは要求されない。例示的な構成において別々のコンポーネントとして提示した構造および機能は、組み合わされた構造またはコンポーネントとして実装されてもよい。同様に、単一のコンポーネントとして提示した構造および機能は、別々のコンポーネントとして実装されてもよい。これらおよび他の変形、修正、追加、および改善は、本開示の主題の範囲に含まれる。
【００８２】
加えて、ある特定の実施形態が、本明細書において、ロジック、またはいくつかのコンポーネント、モジュール、もしくは機構を含むものとして説明されている。モジュールは、ソフトウェアモジュール(例えば機械可読媒体上に格納されたコード)とハードウェアモジュールのどちらかをなしてよい。ハードウェアモジュールは、ある特定の動作を実施することの可能な有形のユニットであり、ある特定の様式で構成または配置されてよい。例示的な実施形態では、1つもしくは複数のコンピュータシステム(例えばスタンドアロンコンピュータシステム、クライアントコンピュータシステム、もしくはサーバコンピュータシステム)、またはコンピュータシステムの1つもしくは複数のハードウェアモジュール(例えばプロセッサもしくはプロセッサグループ)は、ソフトウェア(例えばアプリケーションまたはアプリケーションの部分)によって、本明細書において説明したある特定の動作を実施するように動作するハードウェアモジュールとして構成されてよい。
【００８３】
さまざまな実施形態では、ハードウェアモジュールは、機械的に実装されてもよく、電子的に実装されてもよい。例えば、ハードウェアモジュールは、ある特定の動作を実施するように(例えば、フィールドプログラマブルゲートアレイ(FPGA)や特定用途向け集積回路(ASIC)などの専用プロセッサとして)永久的に構成された専用の回路またはロジックを備えてよい。ハードウェアモジュールは、ある特定の動作を実施するようにソフトウェアによって一時的に構成された(例えば汎用プロセッサまたは他のプログラマブルプロセッサに包含される)プログラマブルロジックまたはプログラマブル回路を備えてもよい。ハードウェアモジュールを機械的に、専用の永久的に構成された回路として実装するか、それとも(例えばソフトウェアによって構成される)一時的に構成された回路として実装するかの決定は、コストおよび時間を考慮することにより行われてよいことが理解されよう。
【００８４】
したがって、ハードウェアという用語は、有形のエンティティが、ある特定の様式で動作するかまたは本明細書において説明したある特定の動作を実施するように、物理的に構築されたエンティティであろうと、永久的に構成された(例えばハードワイヤードの)エンティティであろうと、一時的に構成された(例えばプログラムされた)エンティティであろうと、その有形のエンティティを包含するものと理解されたい。本明細書では、「ハードウェア実装モジュール(hardware-implemented module)」とは、ハードウェアモジュールを指す。複数のハードウェアモジュールが一時的に構成される(例えばプログラムされる)実施形態を考えると、各ハードウェアモジュールは、任意の一時点において構成またはインスタンス化される必要はない。例えば、ハードウェアモジュールが、ソフトウェアを使用して構成される汎用プロセッサを備える場合、汎用プロセッサは、別々の時間に、それぞれの異なるハードウェアモジュールとして構成されてよい。ソフトウェアはそれに応じてプロセッサを、例えば、ある時点において特定のハードウェアモジュールをなし、異なる時点において異なるハードウェアモジュールをなすように、構成してよい。
【００８５】
ハードウェアモジュールは、情報を他のハードウェアに提供し、他のハードウェアから情報を受領することができる。したがって、説明したハードウェアモジュール同士は、通信可能に結合されていると見なされてよい。複数のそのようなハードウェアモジュールが同時に存在する場合、通信は、ハードウェアモジュール同士を接続する(例えば適切な回路およびバス経由での)信号伝送を通じて達成されてよい。複数のハードウェアモジュールが、別々の時間に構成またはインスタンス化される実施形態では、そのようなハードウェアモジュール間の通信は、例えば、その複数のハードウェアモジュールがアクセスすることのできるメモリ構造内への情報の格納およびそのメモリ構造内の情報の取出しを通じて達成されてよい。例えば、あるハードウェアモジュールが、動作を実施し、その動作の出力をそのハードウェアモジュールが通信可能に結合されたメモリデバイス内に格納してよい。その場合、別のハードウェアモジュールが後に、そのメモリデバイスにアクセスして、格納された出力を取り出し、処理してよい。ハードウェアモジュールは、入力デバイスまたは出力デバイスとの通信を開始してもよく、リソース(例えば情報の集合)に作用を及ぼすことができる。
【００８６】
方法800および900は、有形のコンピュータ実行可能命令の形態をとる、1つまたは複数の機能ブロック、モジュール、個別機能、またはルーチンを含んでよく、その命令は、非一時的コンピュータ可読記憶媒体内に格納され、コンピューティングデバイス(例えば、本明細書において説明した、サーバデバイス、パーソナルコンピュータ、スマートフォン、タブレットコンピュータ、スマートウォッチ、モバイルコンピューティングデバイス、または他のクライアントコンピューティングデバイス)のプロセッサを使用して実行される。方法800および900は、任意のバックエンドサーバ(例えば、本明細書において説明した、拡張現実サーバ、ライドシェアリングサーバ、地図データサーバ、ナビゲーションサーバ、もしくは他の任意のタイプのサーバコンピューティングデバイス)、例えば例示的な環境のクライアントコンピューティングデバイスモジュールの部分として、またはそのような環境の外部のモジュールの部分として、含められてよい。図については、説明を簡単にするために他の図を参照して説明されることがあるが、方法800および900は、他のオブジェクトおよびユーザインターフェースと一緒に利用することができる。さらに、上の説明は、方法800および900が(拡張現実サーバ110、ドライバクライアントデバイス10、またはライダクライアントデバイス28などの)特定のデバイスによって実施されるステップについて説明しているが、これは例示を目的としてなされているにすぎない。方法800および900のブロックは、本環境の1つまたは複数のデバイスまたは他の部分によって実施されてよい。
【００８７】
本明細書において説明した例示的な方法のさまざまな動作は、少なくとも一部には、関連の動作を実施するように(例えばソフトウェアによって)一時的に構成されたかまたは永久的に構成された1つまたは複数のプロセッサによって、実施されてよい。一時的に構成されようと、永久的に構成されようと、そのようなプロセッサは、1つまたは複数の動作または機能を実施するように動作するプロセッサ実装モジュール(processor-implemented module)をなしてよい。本明細書において言及されるモジュールは、いくつかの例示的な実施形態では、プロセッサ実装モジュールを備えてよい。
【００８８】
同様に、本明細書において説明した方法またはルーチンも、少なくとも一部には、プロセッサ実装されてよい。例えば、方法の動作のうちの少なくともいくつかが、1つまたは複数のプロセッサ、またはプロセッサ実装ハードウェアモジュールによって実施されてよい。動作のうちのいくつかの実施は、単一のマシン内に存在するのみならずいくつかのマシンにわたってデプロイされた1つまたは複数のプロセッサの間で分散されてよい。いくつかの例示的な実施形態では、1つまたは複数のプロセッサが、単一の位置に(例えば家庭環境内に、オフィス環境内に、またはサーバファームとして)位置付けられてよく、一方、他の実施形態では、プロセッサが、いくつかの位置またはデバイスにわたって分散されてよい。
【００８９】
1つまたは複数のプロセッサは、「クラウドコンピューティング」環境における、またはSaaSとしての、関連の動作の実施をサポートするように動作してもよい。例えば、上で示したように、動作のうちの少なくともいくつかは、(プロセッサを含むマシンの例としての)コンピュータのグループによって実施されてよく、これらの動作には、ネットワーク(例えばインターネット)を介して、かつ1つまたは複数の適切なインターフェース(例えばAPI)を介して、アクセス可能である。
【符号の説明】
【００９０】
10  ドライバクライアントデバイス
28  ライダクライアントデバイス
100  通信システム
102  クライアントコンピューティングデバイス、クライアントデバイス
104  地理的データサーバ
106  サードパーティ道路情報プロバイダ
108  支払システム
110  ネットワーク、拡張現実サーバ
120A  車両
120B  車両
120C  車両
124A  地理的アプリケーション
124B  地理的アプリケーション
124C  コンポーネント
134  トレードオフコントローラ
134A  トレードオフコントローラ
134B  トレードオフコントローラ
140  地図データベース
142  道路セグメント属性データベース
144  過去ルートデータベース、過去ルートデータ
146  ユーザ嗜好データベース
150  非一時的メモリ
152  プロセッサ
154  ユーザインターフェース
160  地理的アプリケーション
170  ルーティングエンジン
172  パラメータ概算モジュール
174  トレードオフコントローラ
200A  サブシステム
200B  サブシステム
202A  ルートジェネレータ
202B  ルートジェネレータ
204A  トレードオフコントローラ
204B  トレードオフコントローラ
206A  通行料概算モジュール
206B  通行料概算モジュール
210  出発地および目的地信号
212  要求時間、信号
214  カープーリング情報
216  タイミング要件
220  地図データ
222  交通データ、信号
224  気象データ
226  燃料価格データ
230  ユーザ嗜好機械学習モデル
232  追加の入力、ユーザメトリック、ユーザ固有メトリック、定量的メトリック
240  ルート候補
242  概算値
250A  ランク付きルート候補
250B  ランク付きルート候補
300  方法
402  出発地
404  目的地
406A  ナビゲーションルート、全体ルート
406B  代替ルート、ナビゲーションルート
410  区間、セグメント
412  区間、セグメント
414  区間、セグメント
502  特徴抽出関数
504  特徴ベクトル
510  信号
512  信号
514  概算コスト信号
520  信号
522  信号
524  信号
530  予測
540  フィードバック処理
602  ユーザインターフェーススクリーン
604  ユーザインターフェーススクリーン
606  ユーザインターフェーススクリーン
608  ユーザインターフェーススクリーン
610  ユーザインターフェーススクリーン
612  ユーザインターフェーススクリーン
620  対話型コントロール、仮想ノブ
622  対話型コントロール、仮想ノブ
624  対話型コントロール、仮想ノブ
626  対話型コントロール、仮想ノブ
700  方法
800  方法
830  方式
832  起点、位置
834  目的地、位置
842  ピックアップ位置
844  ドロップオフ位置
850  方法
900  方法
CDETOUR  迂回路
DD  直接的移動距離
DI  間接的移動距離
L1  位置、出発地
L2  位置、目的地
Stoll1、Stoll2、...StollN  通行料セグメント
S1  道路セグメント
S2  道路セグメント
Si  道路セグメント
T  平均時間
T'  時間量、時間
TD  直接的移動時間
TI  間接的移動時間
T1  時間量、時間
T2  時間
R1、R2、...RN  ナビゲーションルート候補
RD  直接的ルート
RI  間接的ルート
【図１】
2021533334.tif 000003
【図２Ａ】
2021533334.tif 000004
【図２Ｂ】
2021533334.tif 000005
【図３】
2021533334.tif 000006
【図４】
2021533334.tif 000007
【図５】
2021533334.tif 000008
【図６Ａ】
2021533334.tif 000009
【図６Ｂ】
2021533334.tif 000010
【図６Ｃ】
2021533334.tif 000011
【図６Ｄ】
2021533334.tif 000012
【図６Ｅ】
2021533334.tif 000013
【図６Ｆ】
2021533334.tif 000014
【図７】
2021533334.tif 000015
【図８Ａ】
2021533334.tif 000016
【図８Ｂ】
2021533334.tif 000017
【図８Ｃ】
2021533334.tif 000018
【図９】
2021533334.tif 000019
【手続補正書】
【提出日】令和3年2月24日(2021.2.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ナビゲーションルートを生成するための方法であって、
処理ハードウェアによって、ユーザが以前に通過した、それぞれの出発地と目的地との間の複数のルートを示すルートデータを取得するステップと、
前記処理ハードウェアによって、地図データを使用して、前記複数のルート内の第1のタイプのルートセグメントおよび少なくとも1つの他のタイプのルートセグメントを識別して、ルートセグメントデータを生成するステップと、
前記処理ハードウェアによって、前記ルートデータおよび前記ルートセグメントデータを使用して、前記ユーザによるナビゲーションルートの選択の際の前記第1のタイプのルートのルートセグメントの第1の属性と前記少なくとも1つの他のタイプのルートセグメントの第2の属性との間のトレードオフを測定するための定量的メトリックを決定するステップと、
前記処理ハードウェアによって、出発地および目的地の指示を受信するステップと、
前記処理ハードウェアによって、ルートセグメントの選択を制約するために前記定量的メトリックを適用するステップを含めて、前記ユーザ用の前記出発地と前記目的地との間のナビゲーションルートを生成するステップと
を含む、方法。
【請求項２】
前記定量的メトリックを決定するステップが、前記ユーザが移動した1対の位置間の第1のルートと前記ユーザが移動した前記1対の位置間の第2のルートとの時間量の差異を算定するステップを含み、前記第1のルートが、前記第1のタイプのルートセグメントを含み、前記第2のルートが、第2のタイプのルートセグメントを含まない、請求項1に記載の方法。
【請求項３】
前記処理ハードウェアによって、前記ユーザが前記目的地に到着しなければならない時間を示す、時間制約パラメータを受信するステップ
をさらに含み、
前記ナビゲーションルートを生成するステップが、ルートセグメントの選択をさらに制約するために前記時間制約パラメータを適用するステップを含む、
請求項1または2に記載の方法。
【請求項４】
前記処理ハードウェアによって、前記出発地と前記目的地との間で前記ユーザにとってカープーリングが利用可能かどうかを示す、カープーリングパラメータを受信するステップ
をさらに含み、
前記ナビゲーションルートを生成するステップが、ルートセグメントの選択をさらに制約するために前記カープーリングパラメータを適用するステップを含む、
請求項1から3のいずれか一項に記載の方法。
【請求項５】
前記処理ハードウェアによって、前記出発地と前記目的地との間を前記ユーザが移動する予定の時間を示す、移動時間パラメータを受信するステップ
をさらに含み、
前記ナビゲーションルートを生成するステップが、ルートセグメントの選択をさらに制約するために前記移動時間パラメータを適用するステップを含む、
請求項1から4のいずれか一項に記載の方法。
【請求項６】
前記処理ハードウェアによって、前記ルートデータおよび前記ルートセグメントデータを使用して機械学習モデルをトレーニングするステップであって、前記機械学習モデルが、指定された位置間のルート候補を生成するように構成される、ステップ
をさらに含む、請求項1から5のいずれか一項に記載の方法。
【請求項７】
前記定量的メトリックを決定するステップが、
コンピューティングデバイスのユーザインターフェースを介して、前記第1のタイプのルートセグメントと前記少なくとも1つの他のタイプのルートセグメントとの間の前記トレードオフを指定するための対話型コントロールを提供するステップと、
前記ユーザインターフェース内に提供された前記対話型コントロールを介して、前記定量的メトリックを受信するステップと
を含む、請求項1から6のいずれか一項に記載の方法。
【請求項８】
前記ルートデータが、追加データなしに前記定量的メトリックを決定するには不十分であるとの判定に応答して、前記定量的メトリックをさらに、前記出発地と前記目的地との間のルートについて前記第1の属性および前記第2の属性に関する他のユーザの嗜好を示す指示を使用して、前記処理ハードウェアによって決定するステップ
をさらに含む、請求項1から7のいずれか一項に記載の方法。
【請求項９】
コンピューティングシステムであって、
1つまたは複数のプロセッサと、
命令をその上に格納するコンピュータ可読メモリであって、前記命令が前記1つまたは複数のプロセッサによって実行されると前記コンピューティングシステムに、
ユーザが以前に通過した、それぞれの出発地と目的地との間の複数のルートを示すルートデータを取得すること、
地図データを使用して、前記複数のルート内の第1のタイプのルートセグメントおよび少なくとも1つの他のタイプのルートセグメントを識別して、ルートセグメントデータを生成すること、
前記ルートデータおよび前記ルートセグメントデータを使用して、前記ユーザによるナビゲーションルートの選択の際の前記第1のタイプのルートのルートセグメントの第1の属性と前記少なくとも1つの他のタイプのルートセグメントの第2の属性との間のトレードオフを測定するための定量的メトリックを決定すること、
出発地および目的地の指示を受信すること、ならびに
ルートセグメントの選択を制約するために前記定量的メトリックを適用することを含めて、前記ユーザ用の前記出発地と前記目的地との間のナビゲーションルートを生成すること
を行わせる、コンピュータ可読メモリと
を備える、コンピューティングシステム。
【請求項１０】
前記定量的メトリックを決定するために、前記命令が前記コンピューティングシステムに、前記ユーザが移動した1対の位置間の第1のルートと前記ユーザが移動した前記1対の位置間の第2のルートとの時間量の差異を算定することを行わせ、前記第1のルートが、前記第1のタイプのルートセグメントを含み、前記第2のルートが、第2のタイプのルートセグメントを含まない、請求項9に記載のコンピューティングシステム。
【請求項１１】
前記命令が前記コンピューティングシステムに、
前記ユーザが前記目的地に到着しなければならない時間を示す、時間制約パラメータを受信すること
をさらに行わせ、
前記ナビゲーションルートを生成するために、前記命令が前記コンピューティングシステムに、ルートセグメントの選択をさらに制約するために前記時間制約パラメータを適用することを行わせる、
請求項9または10に記載のコンピューティングシステム。
【請求項１２】
前記命令が前記コンピューティングシステムに、
前記出発地と前記目的地との間で前記ユーザにとってカープーリングが利用可能かどうかを示す、カープーリングパラメータを受信すること
を行わせ、
前記ナビゲーションルートを生成するために、前記命令が前記コンピューティングシステムに、ルートセグメントの選択をさらに制約するために前記カープーリングパラメータを適用することを行わせる、
請求項9から11のいずれか一項に記載のコンピューティングシステム。
【請求項１３】
前記命令が前記コンピューティングシステムに、
前記出発地と前記目的地との間を前記ユーザが移動する予定の時間を示す、移動時間パラメータを受信すること
をさらに行わせ、
前記ナビゲーションルートを生成するために、前記命令が、ルートセグメントの選択をさらに制約するために前記移動時間パラメータを適用する、
請求項9から12のいずれか一項に記載のコンピューティングシステム。
【請求項１４】
前記命令が前記コンピューティングシステムに、
前記ルートデータおよび前記ルートセグメントデータを使用して機械学習モデルをトレーニングすることであって、前記機械学習モデルが、指定された位置間のルート候補を生成するように構成される、トレーニングすること
をさらに行わせる、請求項9から13のいずれか一項に記載のコンピューティングシステム。
【請求項１５】
前記定量的メトリックを決定するために、前記命令が前記コンピューティングシステムに、
コンピューティングデバイスのユーザインターフェースを介して、前記第1のタイプのルートセグメントと前記少なくとも1つの他のタイプのルートセグメントとの間の前記トレードオフを指定するための対話型コントロールを提供することと、
前記ユーザインターフェース内に提供された前記対話型コントロールを介して、前記定量的メトリックを受信することと
を行わせる、請求項9から14のいずれか一項に記載のコンピューティングシステム。
【国際調査報告】
2021533334.tif 000020
2021533334.tif 000021
2021533334.tif 000022
2021533334.tif 000023
2021533334.tif 000024