(57)【要約】  ナビゲーションアプリケーションの性能を評価するために、ナビゲーション性能評価システムは、複数のユーザのクライアントデバイス上で動作するナビゲーションアプリケーションによって生成された複数のルートの指示を、ルートの完了時に受信する。次いで、ナビゲーション性能評価システムは、より高速なルートを生成できたかどうかを決定するために、ルートの事後判明分析を提供する。この事後判明分析は、ルートと同じ地理的エリア内の道路区間の実トラバーサル時間に基づいて、各ルートの事後判明ルートを生成することによって実行される。実トラバーサル時間は、ユーザがルートに対応するナビゲーション方向を要求した時間前後に道路区間を移動している車両に基づいて決定される。ナビゲーション性能評価システムは、事後判明の分析に基づいて、ナビゲーションアプリケーションが最速のルートを特定する能力を示すルートの全体的な性能測定基準を生成する。
2021521411.tif 000002
【特許請求の範囲】
【請求項１】
宛先位置までの最適なルートを特定するナビゲーションアプリケーションの性能を評価するための方法であって、
複数の宛先位置までのナビゲーションアプリケーションによって生成された複数のルートの各々について、
1つまたは複数のプロセッサにおいて、複数の道路区間を含む開始位置から宛先位置までのナビゲーション方向についてのユーザによる要求に応答して、前記ナビゲーションアプリケーションによって生成された前記ルートの指示を受信するステップと、
前記1つまたは複数のプロセッサによって、前記複数の道路区間をトラバースするためのおよび代替道路区間をトラバースするための実時間量に基づいて、前記ユーザが前記ナビゲーション方向を要求した時点における、最短の時間量で前記開始位置から前記宛先位置まで移動するための事後判明ルートを決定するステップであって、前記事後判明ルートは、前記ユーザが前記宛先位置に到着した後に決定される、ステップと、
前記1つまたは複数のプロセッサによって、前記ルートについての性能測定基準を決定するために、前記事後判明ルートと前記ルートを比較するステップと、
前記1つまたは複数のプロセッサによって、前記複数のルートの各々についての前記性能測定基準に基づいて、前記ナビゲーションアプリケーションの全体的な性能測定基準を提供するステップと
を含む、方法。
【請求項２】
前記1つまたは複数のプロセッサにおいて、前記ユーザが前記ナビゲーション方向を要求した時点において計算された、前記ルートをトラバースするための予測時間量の指示を受信するステップと、
前記1つまたは複数のプロセッサにおいて、前記ユーザが前記宛先位置に到着した後に計算された、前記ルートをトラバースするのにかかった実時間量の指示を受信するステップと、
前記1つまたは複数のプロセッサによって、前記ルートの前記性能測定基準を決定するために、前記事後判明ルートと前記ルートを、および前記ルートをトラバースするのにかかった前記実時間量と前記ルートをトラバースするための前記予測時間量を比較するステップと
をさらに含む、請求項1に記載の方法。
【請求項３】
前記ルートについての性能測定基準を決定するために、前記事後判明ルートと前記ルートを比較するステップは、前記1つまたは複数のプロセッサによって、
前記ルートと前記事後判明ルートの両方に含まれる道路区間の数、
前記事後判明ルートに含まれる代替道路区間の数、
前記ルートをトラバースするための前記予測時間量と前記ルートをトラバースするのにかかった前記実時間量との差、
前記ルートをトラバースするのにかかった前記実時間量と前記事後判明ルートをトラバースするのにかかるであろう時間量との差、または
前記ルートをトラバースするための前記予測時間量と前記事後判明ルートをトラバースするのにかかるであろう前記時間量との差
のうちの少なくとも1つに基づいて前記性能測定基準を決定するステップを含む、請求項2に記載の方法。
【請求項４】
前記1つまたは複数のプロセッサによって、前記全体的な性能測定基準、および前記ナビゲーションアプリケーションによって生成された前記複数のルートと前記事後判明ルートとの間の不一致に基づいて、前記ナビゲーションアプリケーションによって実行されるルート決定方法のエラーを特定するステップと、
前記1つまたは複数のプロセッサによって、修正アクションを実行するための前記ルート決定方法の前記エラーの原因を決定するステップと
をさらに含む、請求項1に記載の方法。
【請求項５】
前記ナビゲーションアプリケーションによって実行されるルート決定方法のエラーを特定するステップは、
前記ルートの前記性能測定基準がしきい値を下回ると判定するステップと、
前記ルート上の道路区間では予測トラバーサル時間よりも実トラバーサル時間の方が長いことを特定するために前記ルートを分析するステップと、
前記道路区間の前記予測トラバーサル時間のエラーを特定するステップと
を含む、請求項4に記載の方法。
【請求項６】
前記1つまたは複数のプロセッサによって、前記全体的な性能測定基準に基づいて、宛先位置までのルートを特定するためのルート決定モデルを調整するステップ
をさらに含む、請求項1に記載の方法。
【請求項７】
事後判明ルートを決定するステップは、
前記1つまたは複数のプロセッサにおいて、ユーザが前記宛先位置までの前記ルートをトラバースした時間期間と同じ時間期間内の複数の時間インスタンスにおける測位データを1つまたは複数のコンピューティングデバイスから受信するステップと、
前記1つまたは複数のプロセッサによって、道路区間をトラバースするための時間量を決定するために、前記複数の時間インスタンスにおける前記測位データを分析するステップと、
前記1つまたは複数のプロセッサによって、前記道路区間をトラバースするための前記決定された時間量を使用して、前記最短の時間量で前記開始位置から前記宛先位置まで移動するための前記事後判明ルートを決定するステップと
を含む、請求項1に記載の方法。
【請求項８】
前記1つまたは複数のプロセッサによって、前記道路区間上の前記複数の時間インスタンスにおける前記測位データに基づいて、各道路区間の速度値を決定するステップと、
前記1つまたは複数のプロセッサによって、前記道路区間の前記速度値に基づいて、各道路区間をトラバースするための時間量を決定するステップと、
前記1つまたは複数のプロセッサによって、前記宛先位置までの総時間量を最小にする前記開始位置から前記宛先位置までの道路区間の組合せを特定することによって、前記最短の時間量で前記開始位置から前記宛先位置まで移動するための前記事後判明ルートを決定するステップと
をさらに含む、請求項7に記載の方法。
【請求項９】
宛先位置までの最適なルートを特定するナビゲーションアプリケーションの性能を評価するためのサーバデバイスであって、
1つまたは複数のプロセッサと、
前記1つまたは複数のプロセッサに結合され、前記1つまたは複数のプロセッサによって実行されると、前記サーバデバイスに、
複数の宛先位置までのナビゲーションアプリケーションによって生成された複数のルートの各々について、
複数の道路区間を含む開始位置から宛先位置までのナビゲーション方向についてのユーザによる要求に応答して、前記ナビゲーションアプリケーションによって生成された前記ルートの指示を受信することと、
前記複数の道路区間をトラバースするためのおよび代替道路区間をトラバースするための実時間量に基づいて、前記ユーザが前記ナビゲーション方向を要求した時点における、最短の時間量で前記開始位置から前記宛先位置まで移動するための事後判明ルートを決定することであって、前記事後判明ルートは、前記ユーザが前記宛先位置に到着した後に決定される、ことと、
前記ルートについての性能測定基準を決定するために、前記事後判明ルートと前記ルートを比較することと、
前記複数のルートの各々についての前記性能測定基準に基づいて、前記ナビゲーションアプリケーションの全体的な性能測定基準を提供することと
をさせる命令を記憶する非一時的コンピュータ可読メモリと
を含む、サーバデバイス。
【請求項１０】
前記命令は、さらに、前記サーバデバイスに、
前記ユーザが前記ナビゲーション方向を要求した時点において計算された、前記ルートをトラバースするための予測時間量の指示を受信することと、
前記ユーザが前記宛先位置に到着した後に計算された、前記ルートをトラバースするのにかかった実時間量の指示を受信することと、
前記ルートの前記性能測定基準を決定するために、前記事後判明ルートと前記ルートを、および前記ルートをトラバースするのにかかった前記実時間量と前記ルートをトラバースするための前記予測時間量を比較することと
をさせる、請求項9に記載のサーバデバイス。
【請求項１１】
前記性能測定基準は、
前記ルートと前記事後判明ルートの両方に含まれる道路区間の数、
前記事後判明ルートに含まれる代替道路区間の数、
前記ルートをトラバースするための前記予測時間量と前記ルートをトラバースするのにかかった前記実時間量との差、
前記ルートをトラバースするのにかかった前記実時間量と前記事後判明ルートをトラバースするのにかかるであろう時間量との差、または
前記ルートをトラバースするための前記予測時間量と前記事後判明ルートをトラバースするのにかかるであろう前記時間量との差
のうちの少なくとも1つに基づいて決定される、請求項10に記載のサーバデバイス。
【請求項１２】
前記命令は、さらに、前記サーバデバイスに、
前記全体的な性能測定基準に基づいて、前記ナビゲーションアプリケーションによって実行されるルート決定方法におけるエラーを特定することと、
修正アクションを実行するための前記ルート決定方法の前記エラーの原因を決定することと
をさせる、請求項9に記載のサーバデバイス。
【請求項１３】
前記命令は、さらに、前記サーバデバイスに、
前記全体的な性能測定基準に基づいて、宛先位置までのルートを特定するためのルート決定モデルを調整すること
をさせる、請求項9に記載のサーバデバイス。
【請求項１４】
事後判明ルートを決定するために、前記命令は、前記サーバデバイスに、
ユーザが前記宛先位置までの前記ルートをトラバースした時間期間と同じ時間期間内の複数の時間インスタンスにおける測位データを1つまたは複数のコンピューティングデバイスから受信することと、
道路区間をトラバースするための時間量を決定するために、前記複数の時間インスタンスにおける前記測位データを分析することと、
前記道路区間をトラバースするための前記決定された時間量を使用して、前記最短の時間量で前記開始位置から前記宛先位置まで移動するための前記事後判明ルートを決定することと
をさせる、請求項9に記載のサーバデバイス。
【請求項１５】
前記命令は、さらに、前記サーバデバイスに、
前記道路区間上の前記複数の時間インスタンスにおける前記測位データに基づいて、各道路区間の速度値を決定することと、
道路区間の前記速度値に基づいて、各道路区間をトラバースするための時間量を決定することと、
前記宛先位置までの総時間量を最小にする前記開始位置から前記宛先位置までの道路区間の組合せを特定することによって、前記最短の時間量で前記開始位置から前記宛先位置まで移動するための前記事後判明ルートを決定することと
をさせる、請求項14に記載のサーバデバイス。
【請求項１６】
コンピューティングデバイス内の1つまたは複数のプロセッサによって実行されると、前記1つまたは複数のプロセッサに、
複数の宛先位置までのナビゲーションアプリケーションによって生成された複数のルートの各々について、
複数の道路区間を含む開始位置から宛先位置までのナビゲーション方向についてのユーザによる要求に応答して、前記ナビゲーションアプリケーションによって生成された前記ルートの指示を受信することと、
前記複数の道路区間をトラバースするためのおよび代替道路区間をトラバースするための実時間量に基づいて、前記ユーザが前記ナビゲーション方向を要求した時点における、最短の時間量で前記開始位置から前記宛先位置まで移動するための事後判明ルートを決定することであって、前記事後判明ルートは、前記ユーザが前記宛先位置に到着した後に決定される、ことと、
前記ルートについての性能測定基準を決定するために、前記事後判明ルートと前記ルートを比較することと、
前記複数のルートの各々についての前記性能測定基準に基づいて、前記ナビゲーションアプリケーションの全体的な性能測定基準を提供することと
をさせる命令を記憶した、非一時的コンピュータ可読媒体。
【請求項１７】
前記命令はさらに、前記1つまたは複数のプロセッサに、
前記ユーザが前記ナビゲーション方向を要求した時点において計算された、前記ルートをトラバースするための予測時間量の指示を受信することと、
前記ユーザが前記宛先位置に到着した後に計算された、前記ルートをトラバースするのにかかった実時間量の指示を受信することと、
前記ルートの前記性能測定基準を決定するために、前記事後判明ルートと前記ルートを、および前記ルートをトラバースするのにかかった前記実時間量と前記ルートをトラバースするための前記予測時間量を比較することと
をさせる、請求項16に記載のコンピュータ可読媒体。
【請求項１８】
前記性能測定基準は、
前記ルートと前記事後判明ルートの両方に含まれる道路区間の数、
前記事後判明ルートに含まれる代替道路区間の数、
前記ルートをトラバースするための前記予測時間量と前記ルートをトラバースするのにかかった前記実時間量との差、
前記ルートをトラバースするのにかかった前記実時間量と前記事後判明ルートをトラバースするのにかかるであろう時間量との差、または
前記ルートをトラバースするための前記予測時間量と前記事後判明ルートをトラバースするのにかかるであろう前記時間量との差
のうちの少なくとも1つに基づいて決定される、請求項17に記載のコンピュータ可読媒体。
【請求項１９】
前記命令はさらに、前記1つまたは複数のプロセッサに、
前記全体的な性能測定基準に基づいて、前記ナビゲーションアプリケーションによって実行されるルート決定方法におけるエラーを特定することと、
修正アクションを実行するための前記ルート決定方法の前記エラーの原因を決定することと
をさせる、請求項16に記載のコンピュータ可読媒体。
【請求項２０】
前記命令はさらに、前記1つまたは複数のプロセッサに、
前記全体的な性能測定基準に基づいて、宛先位置までのルートを特定するためのルート決定モデルを調整すること
をさせる、請求項16に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、デジタルマッピングデータに関し、より詳細には、ナビゲーションアプリケーションにおけるルート決定方法の性能の評価に関する。
【背景技術】
【０００２】
本明細書で提供される「背景技術」の記載は、本開示の文脈を全般的に提示するためのものである。この背景技術セクションに記載されている範囲で、現在指名されている発明者の研究、ならびに、そうでなければ出願時に従来技術として認められない可能性のある記載の態様は、本開示に対する従来技術として明示的または暗黙的に認められない。
【０００３】
今日、コンピュータ、スマートフォン、埋め込みデバイスなどで実行されるソフトウェアアプリケーションは、トラフィックデータを含む可能性のある段階的なナビゲーション方向を生成する。典型的には、ユーザが開始位置および宛先位置を指定し、ソフトウェアアプリケーションは、直ちに、および/または、ユーザが開始位置から宛先位置まで移動するにつれて、道順を表示する。ソフトウェアアプリケーションは、典型的には、最短の時間量で宛先位置までユーザを連れて行くルートの道順を生成する。最短の時間量は、ルートの様々な区間をトラバースするための予測時間量に基づいてもよい。
【発明の概要】
【課題を解決するための手段】
【０００４】
開始位置から宛先位置までのルートを生成するナビゲーションアプリケーションの性能を評価するために、性能評価サーバは、複数のユーザのクライアントデバイスにおいて動作するナビゲーションアプリケーションによって生成される複数のルートの指示を受信する。また、ルートごとに、性能評価サーバは、ナビゲーションアプリケーションによって生成されたルートをトラバースするための予測時間量の指示、およびユーザが宛先位置までのナビゲーション方向を要求した日時または時間期間の指示も受信する。さらに、ユーザが位置および他のセンサーデータを共有することに同意したとき、性能評価サーバは、宛先位置に移動中のユーザのクライアントデバイスから、ならびに位置および他のセンサーデータを共有することに同意した他のユーザのクライアントデバイスから、測位データおよび他のセンサーデータを取得する。
【０００５】
性能評価サーバは、測位データおよび/または他のセンサーデータに基づいて、ユーザが宛先位置に到着した後、ユーザが宛先位置までの移動にかかった実時間量を決定する。また、性能評価サーバは、測位データおよび/または他のセンサーデータに基づいて、ユーザがナビゲーション方向を要求したときに開始して、最短の時間量で開始位置から宛先位置まで移動するための事後判明ルート(hindsight route)を決定する。より詳細には、ユーザのクライアントデバイスからの測位データに従って、ユーザがルートに含まれる各道路区間をトラバースするのにかかった実時間量を算出することによって、事後判明ルートが決定される。また、性能評価サーバは、他のユーザがルートに含まれていない代替道路区間をトラバースするのにかかった実時間量も決定する。次いで、性能評価サーバは、実際のルート上の道路区間と代替道路区間との組合せとして、事後判明ルートを特定し、組合せは、宛先位置までの最短の時間量を有するルートをもたらす。
【０００６】
次いで、性能評価サーバは、実際のルートと事後判明ルートとの差に基づいて、ルートについての性能測定基準を生成する。性能測定基準は、実際のルートのうち事後判明ルートに含まれていた実際のルートの道路区間の割合、または実際のルートに含まれていた事後判明ルートの合計距離の割合を含み得る。また、性能測定基準は、ルートをトラバースするための予測時間量とルートをトラバースするための実時間量との差、ルートをトラバースするための実時間量と事後判明ルートをトラバースするためにかかったであろう時間量との差、およびルートをトラバースするための予測時間量と事後判明ルートをトラバースするためにかかったであろう時間量との差を含んでいてもよい。また、ルートごとの性能測定基準に基づいて、ナビゲーションアプリケーションの全体的な性能測定基準が生成されてもよい。
【０００７】
次いで、性能評価サーバは、ルートの各々についての性能測定基準または全体的な性能測定基準を、ユーザインターフェース上に表示するために提供し得る。たとえば、表示は、時間が95%となった最速のルートをナビゲーションアプリケーションが特定することを示し得る。また、性能測定基準は、ルート決定アルゴリズムにおけるエラーを特定し、そのエラーの原因を決定するために根本原因分析を実行するために使用されてもよい。さらに、性能測定基準は、開始位置から宛先位置までのルートを生成するために使用されるルート決定モデルを調整するために使用されてもよい。たとえば、ルート決定モデルは、特定の道路区間をルートに含めるかどうかを決定するための複数のパラメータの組合せを含んでもよい。各パラメータは重み付けされてもよく、性能評価サーバは、性能測定基準に基づいてパラメータの重みを調整してもよい。
【０００８】
特に、本開示の技法の例示的な実施形態は、宛先位置までの最適なルートを特定するナビゲーションアプリケーションの性能を評価するための方法である。複数の宛先位置までのナビゲーションアプリケーションによって生成された複数のルートの各々について、方法は、複数の道路区間を含む開始位置から宛先位置までのナビゲーション方向についてのユーザによる要求に応答して、ナビゲーションアプリケーションによって生成されたルートの指示を受信するステップと、複数の道路区間をトラバースするためのおよび代替道路区間をトラバースするための実時間量に基づいて、ユーザがナビゲーション方向を要求した時点における、最短の時間量で開始位置から宛先位置まで移動するための事後判明ルートを決定するステップであって、事後判明ルートは、ユーザが宛先位置に到着した後に決定される、ステップと、ルートについての性能測定基準を決定するために、ルートを事後判明ルートと比較するステップとを含む。方法は、複数のルートの各々についての性能測定基準に基づいて、ナビゲーションアプリケーションの全体的な性能測定基準を提供するステップをさらに含む。
【０００９】
これらの技法の別の実施形態は、宛先位置までの最適なルートを特定するナビゲーションアプリケーションの性能を評価するためのサーバデバイスである。サーバデバイスは、1つまたは複数のプロセッサ、および命令を記憶する非一時的コンピュータ可読メモリを含む。1つまたは複数のプロセッサによって実行されると、命令は、複数の宛先位置までのナビゲーションアプリケーションによって生成された複数のルートの各々について、サーバデバイスに、複数の道路区間を含む開始位置から宛先位置までのナビゲーション方向についてのユーザによる要求に応答して、ナビゲーションアプリケーションによって生成されたルートの指示を受信させる。命令はさらに、サーバデバイスに、複数の道路区間をトラバースするためのおよび代替道路区間をトラバースするための実時間量に基づいて、ユーザがナビゲーション方向を要求した時点における、最短の時間量で開始位置から宛先位置まで移動するための事後判明ルートを決定させ、事後判明ルートは、ユーザが宛先位置に到着した後に決定され、ルートについての性能測定基準を決定するために、ルートを事後判明ルートと比較させる。さらに、命令は、サーバデバイスに、複数のルートの各々についての性能測定基準に基づいて、ナビゲーションアプリケーションの全体的な性能測定基準を提供させる。
【００１０】
これらの技法のさらに別の実施形態は、命令を記憶した非一時的コンピュータ可読媒体である。1つまたは複数のプロセッサによって実行されると、命令は、複数の宛先位置までのナビゲーションアプリケーションによって生成された複数のルートの各々について、1つまたは複数のプロセッサに、複数の道路区間を含む開始位置から宛先位置までのナビゲーション方向についてのユーザによる要求に応答して、ナビゲーションアプリケーションによって生成されたルートの指示を受信させる。命令はさらに、1つまたは複数のプロセッサに、複数の道路区間をトラバースするためのおよび代替道路区間をトラバースするための実時間量に基づいて、ユーザがナビゲーション方向を要求した時点における、最短の時間量で開始位置から宛先位置まで移動するための事後判明ルートを決定させ、事後判明ルートは、ユーザが宛先位置に到着した後に決定され、ルートについての性能測定基準を決定するために、ルートを事後判明ルートと比較させる。さらに、命令は、1つまたは複数のプロセッサに、複数のルートの各々についての性能測定基準に基づいて、ナビゲーションアプリケーションの全体的な性能測定基準を提供させる。
【図面の簡単な説明】
【００１１】
【図１】ナビゲーションアプリケーションの性能を評価するための技法を実装することができる例示的な通信システムのブロック図である。
【図２Ａ】ナビゲーションアプリケーションによって生成された開始位置から宛先位置までのルートを含む例示的なナビゲーションの表示を示す図である。
【図２Ｂ】ユーザが宛先位置に到着した後、図2Aと同じ宛先位置までの事後判明ルートを生成するための事後判明ナビゲーションデータの例示的な表示を示す図である。
【図３Ａ】道路区間、および最も低い集約された重みを有するパスに基づいて目的地までの事後判明ルートを生成するための各道路区間に割り当てられたそれぞれの重みを含む例示的なマップディスプレイである。
【図３Ｂ】最小コストパス分析を使用して事後判明ルートを生成するための例示的なグラフである。
【図４】性能評価サーバによって実行することができるナビゲーションアプリケーションの性能を評価するための例示的な方法を示すフロー図である。
【発明を実施するための形態】
【００１２】
一般的に言えば、ナビゲーションアプリケーションの性能を評価するための技法を、1つまたは複数のクライアントコンピューティングデバイス、1つまたは複数のネットワークサーバ、またはこれらのデバイスの組合せを含むシステムに実装することができる。しかしながら、明快のために、以下の例は、ナビゲーションアプリケーションがクライアントコンピューティングデバイス上で実行され、ナビゲーションデータサーバによって決定されたルートを介した開始位置から宛先位置までのナビゲーション方向を提示する実施形態に主に焦点を当てている。ナビゲーションアプリケーションは、宛先位置に到着するまでの時間量の推定も提示し得る。宛先位置に到着した後、ユーザが位置および他のセンサーデータを共有することに同意すると、ナビゲーションアプリケーションは、性能評価サーバに、生成されたルートの指示、宛先位置に到着するまでの推定時間量、ユーザが宛先位置までのナビゲーション方向を要求した日時または時間期間の指示、および/または宛先に到着するまで、またはルートに沿って様々な道路区間をトラバースするのにかかった実時間量(本明細書では「トラバーサル時間」とも呼ばれる)の指示を提供してもよい。性能評価サーバは、複数のユーザのクライアントコンピューティングデバイス上で、ナビゲーションアプリケーションによって提示された複数のルートについての同様のルート情報を受信してもよい。
【００１３】
さらに、性能評価サーバは、ユーザと同じ時間枠でユーザと同じ地理的エリア内を移動していたユーザのクライアントコンピューティングデバイスから、測位データおよび他のセンサーデータを取得してもよい。
【００１４】
次いで、性能評価サーバは、ユーザがナビゲーション方向を要求したときに開始して、最短の時間量で開始位置から宛先位置まで移動するための事後判明ルートを生成してもよい。事後判明ルートは、ユーザがルートに沿って様々な道路区間をトラバースするのにかかった実時間量、および他のユーザが地理的エリア内の様々な道路区間をトラバースするのにかかった実時間量に基づいて生成されてもよい。さらに、事後判明ルートは、ユーザによってトラバースされた道路区間と他のユーザによってトラバースされた道路区間との組合せを含んでいてもよい。
【００１５】
次いで、性能評価サーバは、ルートについての性能測定基準を生成するために、事後判明ルートをナビゲーションアプリケーションによって生成されたルートと比較してもよい。性能評価サーバは、ルートについての性能測定基準を、事後判明ルートの指示およびナビゲーションアプリケーションによって生成されたルートとともにクライアントコンピューティングデバイスに提供してもよい。このようにして、クライアントコンピューティングデバイスは、ナビゲーションアプリケーションの性能をレビューするユーザに、性能測定基準と、事後判明ルートおよび/またはナビゲーションアプリケーションによって生成されたルートの指示とを提示してもよい。性能評価サーバはまた、様々なユーザのクライアントコンピューティングデバイス上でナビゲーションアプリケーションによって生成された複数のルートについての性能測定基準に基づいて、ナビゲーションアプリケーションの全体的な性能測定基準を生成してもよい。クライアントコンピューティングデバイスは、ナビゲーションアプリケーションの全体的な性能測定基準を、たとえば、ナビゲーションソフトウェアおよびサービスをライセンス供与している顧客またはパートナーに提示してもよい。ナビゲーションアプリケーションの全体的な性能測定基準および/または様々なルートまたは道路区間のため個々の性能測定基準は、ナビゲーションアプリケーションによって生成されたルートの品質を決定するために、ナビゲーションアプリケーションを作成した組織の従業員または他のメンバーに提示されてもよい。組織のメンバーはまた、ルート決定方法の欠陥を発見し、および/またはこれらの欠陥において根本原因分析を実行するために、性能測定基準を閲覧してもよい。
【００１６】
例示的なハードウェアおよびソフトウェア構成要素
図1を参照すると、ナビゲーション性能評価システムが実装され得る例示的な通信システム100は、クライアントコンピューティングデバイス10(本明細書では「クライアントデバイス」とも呼ばれる)、および「ナビゲーションアプリケーション84」と呼ぶこともできる地理アプリケーション84を実行するように構成されたコンピューティングデバイスなど複数の他のクライアントデバイス82a〜nを含む。実施形態によっては、アプリケーション84は、対話式のデジタルマップを表示し、ルーティングデータを要求し受信して、運転、徒歩、または他のナビゲーション方向を提供し、様々な地理的に配置されたコンテンツを提供したりすることができる。クライアントデバイス82a〜nの各々は、ユーザが様々な場所にナビゲートしながらデジタルマップを表示することによって操作されてもよい。
【００１７】
クライアントデバイス10および他のクライアントデバイス82a〜nに加えて、通信システム100は、ナビゲーションアプリケーションの全体的な性能測定基準および/またはルートもしくは道路区間についての個々の性能測定基準をクライアントデバイス10に提供するように構成された性能評価サーバ60を含む。性能評価サーバ60は、例示的な実装形態では、ナビゲーションアプリケーション84によって以前に生成されたルートについてのルート情報、および特定の日、日時などに開始位置から宛先位置まで移動するための歴史的に最も速いルートを示す事後判明ルートを記憶するデータベース80に通信的に結合され得る。
【００１８】
より一般的には、性能評価サーバ60は、任意のタイプの適切な地理空間的情報または情報を記憶する1つまたは複数のデータベースと通信することができる。通信システム100はまた、たとえばナビゲーションアプリケーション84を介して提示するために、運転、徒歩、自転車、または公共交通機関の道順を提供するナビゲーションデータサーバ34を含むことができる。さらに、通信システム100は、マップディスプレイ86を生成するために、クライアントデバイス82a〜nにマップデータを提供するマップデータサーバ50を含むことができる。通信システム100において動作するデバイスは、通信ネットワーク30を介して相互に接続することができる。
【００１９】
クライアントデバイス10は、たとえば、スマートフォンやタブレットコンピュータなどのポータブルデバイスであってもよい。また、クライアントデバイス10は、ラップトップコンピュータ、デスクトップコンピュータ、パーソナルデジタルアシスタント(PDA)、スマートウォッチやスマートグラスなどのウェアラブルデバイスなどであってもよい。また、クライアントデバイス10は、第4世代または第3世代のセルラーネットワーク(それぞれ4Gまたは3G)などの有線または無線の通信ネットワーク30を介して、様々なコンテンツプロバイダ、サーバなどと通信することができる。クライアントデバイス10は、メモリ20、1つまたは複数のプロセッサ(CPU)16、グラフィックス処理ユニット(GPU)12、I/Oモジュール14、およびユーザインターフェース(UI)32を含み得る。メモリ20は、非一時的メモリとすることができ、ランダムアクセスメモリ(RAM)、読取り専用メモリ(ROM)、フラッシュメモリ、他のタイプの永続メモリなど、1つまたは複数の適切なメモリモジュールを含むことができる。I/Oモジュール14は、たとえばタッチスクリーンであってもよい。様々な実施形態では、クライアントデバイス10は、図1に示されているよりも少ない構成要素を含むことができ、または逆に、追加の構成要素を含むことができる。
【００２０】
メモリ20は、任意のタイプの適切なモバイルまたは汎用オペレーティングシステムとすることができるオペレーティングシステム(OS)26を記憶する。メモリ20はまた、ナビゲーションアプリケーションの全体的な性能測定基準、ナビゲーションアプリケーションによって生成されたルートもしくは道路区間についての個々の性能測定基準、ならびに/またはナビゲーションアプリケーションによって生成されたルートおよび対応する事後判明ルートの指示など、ナビゲーションアプリケーションに関連する他のナビゲーション性能データを受信するように構成された性能測定基準ディスプレイ22を記憶する。性能測定基準ディスプレイ22は、ナビゲーション性能データをユーザインターフェース32に提示するように構成されている。
【００２１】
上述したように、各クライアントデバイス82a〜nは、ユーザがマップデータを表示することによって操作されてもよい。各クライアントデバイス82a〜nは、スマートフォンまたはタブレットコンピュータであってもよく、1つまたは複数のセンサを有していてもよい。さらに、各クライアントデバイス82a〜nは、オペレーティングシステム(OS)を記憶するメモリ、ならびに、上記のように、対話式のデジタルマップを生成する、および/または他の地理的機能を実行するように構成されたナビゲーションアプリケーション84を含み得る。ナビゲーションアプリケーション84は、マップデータサーバ50からラスタ(たとえば、ビットマップ)または非ラスタ(たとえば、ベクターグラフィックス)形式のマップデータを受信し、マップディスプレイ86を介してマップデータを提示することができる。いくつかの場合には、マップデータは、道路、街路、自然地形などを描いた基本レイヤ、現在の交通状態を描いた交通レイヤ、現在の天候状態を描いた天候レイヤ、目的地に到達するためのパスを描いたナビゲーションレイヤなどのレイヤに編成することができる。ナビゲーションアプリケーション84はまた、運転、徒歩、またはトランジットの方向を表示することができ、一般に、マップディスプレイ86を介して地理、ジオロケーション、ナビゲーションなどに関連する機能を提供する。
【００２２】
図1は、ナビゲーションアプリケーション84をスタンドアロンアプリケーションとして示しているが、ナビゲーションアプリケーション84の機能は、クライアントデバイス82a〜nにおいて実行されるウェブブラウザを介してアクセス可能なオンラインサービスの形態で、クライアントデバイス82a〜nにおいて実行される別のソフトウェアアプリケーションのためのプラグインまたは拡張機能などとして提供することもできることに留意されたい。ナビゲーションアプリケーション84は、一般に、異なるそれぞれのオペレーティングシステムについての異なるバージョンで提供され得る。たとえば、クライアントデバイス82a〜nのメーカーは、Android(商標)プラットフォーム用のナビゲーションアプリケーション84を含むソフトウェア開発キット(SDK)、iOS(商標)プラットフォーム用の別のSDKなどを提供することができる。
【００２３】
いくつかの実装形態では、性能評価サーバ60は、1つまたは複数のプロセッサ62およびメモリ64を含む。メモリ64は、有形の非一時的メモリであってもよく、ランダムアクセスメモリ(RAM)、読取り専用メモリ(ROM)、フラッシュメモリ、他のタイプの永続メモリなどを含む、任意のタイプの適切なメモリモジュールを含み得る。メモリ64は、ナビゲーションアプリケーションの全体的な性能測定基準、ナビゲーションアプリケーションによって生成されたルートまたは道路区間についての個々の性能測定基準、または都市、州、国など特定の地政学的地域内でナビゲーションアプリケーションによって生成されたルートについての地域的な性能測定基準を生成することができる、性能評価エンジン68を構成するプロセッサ62上で実行可能な命令を記憶する。性能評価エンジン68はまた、クライアントデバイス10の性能測定基準ディスプレイ22によって表示されるナビゲーション性能データを提供してもよい。
【００２４】
性能評価エンジン68および性能測定基準ディスプレイ22は、ナビゲーション性能評価システムの構成要素として動作することができる。あるいは、ナビゲーション性能評価システムは、サーバ側構成要素のみを含み、単にナビゲーション性能データを表示するための命令を性能測定基準ディスプレイ22に提供することができる。言い換えれば、これらの実施形態におけるナビゲーション性能評価技法は、性能測定基準ディスプレイ22に対して透過的に実装することができる。別の代替として、性能評価エンジン68の機能全体を性能測定基準ディスプレイ22に実装することができる。
【００２５】
簡単のために、図1は、性能評価サーバ60をサーバのただ1つのインスタンスとして示している。しかしながら、いくつかの実装形態による性能評価サーバ60は、各々が1つまたは複数のプロセッサを備え、他のサーバデバイスとは独立して動作可能な1つまたは複数のサーバデバイスのグループを含む。そのようなグループ内で動作するサーバデバイスは、クライアントデバイス10からの要求を、個別に(たとえば、可用性に基づいて)、要求の処理に関連する1つの動作が1つのサーバデバイス上で実行される一方で、同じ要求の処理に関連する別の動作が別のサーバデバイス上で実行されるような分散型の方法で、または任意の他の適切な技法に従って処理することができる。本議論の目的のために、「サーバデバイス」という用語は、個々のサーバデバイスを指す場合もあれば、2つ以上のサーバデバイスのグループを指す場合もある。
【００２６】
動作中、クライアントデバイス10において動作する性能測定基準ディスプレイ22は、データを受信し、性能評価サーバ60に送信する。したがって、一例では、クライアントデバイス10は、(性能評価サーバ60において実装されている)性能評価エンジン68にナビゲーション性能データを要求する通信を送信してもよい。要求は、特定の開始位置/宛先位置のペアについてであってもよく、特定の開始位置から開始するすべてのルートまたは特定の宛先位置に到着するすべてのルートについてであってもよく、特定の地理的地域について(たとえば、カリフォルニア、シアトルなど、米国にわたってナビゲーションアプリケーションによって生成されたルートのナビゲーション性能データについて)であってもよく、または世界中であってもよい。
【００２７】
したがって、性能評価エンジン68は、指定された地理的領域内で生成されたルートについて、クライアントデバイス82a〜nからルート情報を取得してもよい。ルート情報は、ルートの開始位置および宛先位置、ルートに含まれる道路区間および/または操作の各々の指示、ナビゲーション方向が要求された日にちおよび/または時刻、ルート上を移動するときに目的地に到達するための予測時間量などを含み得る。性能評価エンジン68はまた、ナビゲーションアプリケーション84を実行している地理的領域内を移動しているクライアントデバイス82a〜nから、測位データおよび/または他のセンサーデータを取得してもよい。測位データおよび/または他のセンサーデータは、ルートに対応するナビゲーション方向を要求したユーザのための測位データおよび/または他のセンサーデータを含んでもよい。
【００２８】
したがって、性能評価エンジン68は、ユーザが開始位置から宛先位置までのルートを完了するための実トラバーサル時間、ユーザがルート上の各道路区間をトラバースするための実トラバーサル時間、ユーザが様々な道路区間を移動した速度、または各道路区間の平均速度などを決定するように、測位データおよび/または他のセンサーデータを分析してもよい。測位データおよび/または他のセンサーデータは、ルートに対応するナビゲーション方向を要求しなかった他のクライアントデバイス82a〜nの他のユーザのための測位データおよび/または他のセンサーデータを含んでもよい。測位データおよび/または他のセンサーデータは、ユーザがルートに対応するナビゲーション方向を要求した時間期間と同じ時間期間からのものであってもよい。たとえば、ユーザが2018年8月21日午後3時にルートに対応するナビゲーション方向を要求したとき、性能評価エンジン68は、2018年8月21日午後2時30分から3時30分までの間に、他のクライアントデバイス82a〜nから測位データおよび/または他のセンサーデータを取得してもよい。
【００２９】
このようにして、性能評価エンジン68は、ルート上になかった代替道路区間のトラバーサル時間、他のユーザが代替道路区間上を移動した速度、または各代替道路区間の平均速度などを決定するように、測位データおよび/または他のセンサーデータを分析してもよい。次いで、性能評価エンジン68は、ルートが完了した後、ユーザがルートに対応するナビゲーション方向を要求した日時における様々な道路区間の実トラバーサル時間および速度に基づいて、開始位置から宛先位置までの実際の最速のルートを示す事後判明ルートを生成してもよい。
【００３０】
性能評価エンジン68は、開始位置および宛先位置を含む地理的エリア内の道路区間にトラバーサル時間を割り当て、最短の時間量で開始位置から宛先位置まで移動するための道路区間の組合せを特定することによって、事後判明ルートを生成してもよい。たとえば、ナビゲーションアプリケーション84は、2018年8月21日の午後3時に、位置A、位置B、位置C、位置Zまでの移動を含む、位置Aから位置Zまでのナビゲーション方向を提示した可能性があり、このルートで位置Aから位置Zまでの移動にユーザが20分かかった可能性がある。しかしながら、事後判明で、性能評価エンジン68は、2018年8月21日の午後2時30分から午後3時30分までの間に移動したユーザが、場所Aから場所Dに移動し、場所Dから場所Cに移動するのに平均12分かかったのに対し、ユーザが場所A、場所B、場所Cに移動するのに15分かかったので、場所A、場所D、場所C、場所Zに移動する方がより高速であったと決定することができる。
【００３１】
次いで、性能評価エンジン68は、事後判明ルートをナビゲーションアプリケーションによって生成されたルートと比較して、ルートについての性能測定基準を決定してもよい。性能測定基準は、実際のルートのうち事後判明ルートに含まれていた道路区間の割合、または実際のルートに含まれていた事後判明ルートの合計距離の割合を含み得る。また、性能測定基準は、ルートをトラバースするための予測時間量とルートをトラバースするための実時間量との差、ルートをトラバースするための実時間量と事後判明ルートをトラバースするためにかかったであろう時間量との差、およびルートをトラバースするための予測時間量と事後判明ルートをトラバースするためにかかったであろう時間量との差を含んでいてもよい。
【００３２】
さらに、性能評価エンジン68は、事後判明ルートを生成し、指定された地理的領域内の複数のルートについての性能測定基準を決定してもよい。いくつかの実装形態では、性能評価エンジン68は、ルートまたは道路区間についての個々の性能測定基準に基づいて、ナビゲーションアプリケーションおよび/または指定された地理的領域についての全体的な性能測定基準を生成してもよい。たとえば、全体的な性能測定基準は、個々の性能測定基準の平均、移動平均または時間減衰平均など、個々の性能測定基準の加重平均、個々の性能測定基準の総計、または個々の性能測定基準の任意の適切な組合せであってもよい。
【００３３】
いずれにしても、性能評価エンジン68は、クライアントデバイス10上の表示のために、全体的な性能測定基準および/または個々の性能測定基準を提供してもよい。次いで、性能測定基準ディスプレイ22は、クライアントデバイス10のユーザインターフェース32上に、全体的な性能測定基準および/または個々の性能測定基準を提示してもよい。このようにして、ナビゲーションソフトウェアおよびサービスをライセンス供与している顧客またはパートナーは、ナビゲーション性能データを閲覧してもよい。さらに、ナビゲーションアプリケーションを作成した組織の従業員または他のメンバーは、ナビゲーションアプリケーションによって生成されたルートの品質を決定する、ルート決定方法の欠陥を見つける、これらの欠陥において根本原因分析を実行するなどのために、ナビゲーション性能データを閲覧してもよい。
【００３４】
図2Aは、ユーザのクライアントデバイス82a〜n上のナビゲーションアプリケーション84によって提示された、ユーザの現在位置からユーザの事業所までの例示的なルートを示す。図2Bは、開始位置および宛先位置を含む地理的エリア内の道路区間をトラバースするための実際の時間間隔に基づいて、ユーザの現在位置からユーザの事業所までの最速ルートを、事後判明で決定するための例示的な事後判明ルート候補を示す。より具体的には、図2Aのナビゲーションディスプレイ200は、ユーザの現在位置202からユーザの事業所212までの例示的なルート216を含む。ルート216は、複数の道路区間(たとえば、メインストリートとステートストリートのコーナーからメインストリートとグリーンストリートのコーナーまで)および操作(たとえば、左折および右折)を含む。また、ナビゲーションディスプレイ200は、ルート218をトラバースするための予測時間量を含む。ルート216は、たとえば、ナビゲーションデータサーバ34によって2018年7月25日午前10時34分に生成され得る。いくつかの実装形態では、ナビゲーションデータサーバ34は、開始位置(ユーザの現在位置)および宛先位置(ユーザの事業所)をルート決定モデルに適用することを含むルート決定方法を使用してルート216を生成する。ルート決定モデルは、複数のパラメータおよび/または各パラメータに割り当てられた重みを含んでいてもよく、過去のナビゲーションデータに基づいて生成されてもよい。たとえば、ルート決定モデルは、様々な時刻、天候状態、交通状態、季節などにおいて、道路区間を以前にトラバースした車両からの訓練データに基づいて、機械学習技法を使用して生成されてもよい。したがって、ナビゲーションデータサーバ34は、ルート決定モデルからの過去のデータに基づく近未来予測を使用して、ルート216を生成し、ルート218をトラバースするための時間量を予測してもよい。
【００３５】
ユーザが自分の事業所212に到着した後、クライアントデバイス82a〜nは、ルート216、およびルート218をトラバースするための予測時間量の指示を性能評価サーバ60に提供してもよい。また、クライアントデバイス82a〜nは、ルートに沿って、クライアントデバイス82a〜nの測位データおよび/または他のセンサーデータを提供してもよい。これは、クライアントデバイス82a〜nが開始位置を出発した時刻、およびクライアントデバイス82a〜nが宛先位置に到着した時刻を含む、ルートに沿った様々な時刻におけるクライアントデバイス82a〜nの位置の指示を含み得る。このようにして、性能評価エンジン68は、ルートの実トラバーサル時間を決定してもよい。さらに、性能評価エンジン68は、ルート上の各道路区間の実トラバーサル時間および/またはルート上の各道路区間をトラバースするための平均速度を決定してもよい。いくつかの場合、性能評価エンジン68は、クライアントデバイス82a〜nがしきい値を超える時間量(たとえば、5分)の間移動しなかったことを決定してもよい。したがって、性能評価エンジン68は、ユーザがルートから休憩を取った(たとえば、ガソリンまたはドライブスルーのために停止するため)と判定し、この時間期間をルートの総トラバーサル時間から差し引いてもよい。
【００３６】
いずれにしても、性能評価エンジン68は、また、ユーザと同じ時間枠内にユーザと同じ地理的エリア内を移動している他のクライアントデバイス82a〜nから測位データおよび/または他のセンサーデータを取得してもよい。たとえば、地理的エリアは、開始位置と宛先位置の両方を含むnマイル×nマイルのエリアであってもよく、ここで、nは、開始位置と宛先位置との間の距離に比例する(たとえば、nは、開始位置と宛先位置との間の距離に等しい、開始位置と宛先位置との間の距離の2倍などであってもよい)。時間枠は、ユーザがナビゲーション方向を要求したときを含む1時間間隔、2時間間隔などであってもよい。
【００３７】
次いで、性能評価エンジン68は、ルート216に対応するナビゲーション方向を要求したクライアントデバイス82a〜nから、ならびに同じ時間枠内に同じ地理的エリア内を移動する他のクライアントデバイス82a〜nからの測位データおよび/または他のセンサーデータを使用して、ユーザがナビゲーション方向を要求したときに地理的エリア内の道路区間についての実トラバーサル時間を生成してもよい。性能評価エンジン68は、車両が道路区間に進入した時間と道路区間を出た時間との間の差に基づいて、特定の道路区間の実トラバーサル時間を決定してもよい。性能評価エンジン68が、同じ道路区間について複数のクライアントデバイス82a〜nからセンサーデータを受信すると、性能評価エンジン68は、各クライアントデバイス82a〜nによって示された実トラバーサル時間の平均として、道路区間の実トラバーサル時間を決定してもよい。性能評価エンジン68はまた、たとえば、ユーザがナビゲーション方向を要求した時間前後に道路区間上を移動しているクライアントデバイス82a-nがより高い重み付けがされるなど、実トラバーサル時間の加重平均として道路区間の実トラバーサル時間を決定してもよい。さらに、性能評価エンジン68は、各クライアントデバイス82a〜nによって示されるトラバーサル時間の任意の他の適切な組合せに基づいて、道路区間についての実トラバーサル時間を決定してもよい。他の実装形態では、性能評価エンジン68は、車両が道路区間上を移動した平均速度および道路区間の長さに基づいて、特定の道路区間の実トラバーサル時間を決定してもよい。
【００３８】
図2Bは、開始位置202から宛先位置212への事後判明ルート候補を特定するための地理的エリア252内の事後判明ナビゲーションデータのディスプレイ250を示す。事後判明ナビゲーションデータは、ルート216上の道路区間(たとえば、道路区間254)、およびルート216上にはなかった地理的エリア内の代替道路区間(たとえば、代替道路区間256)について、性能評価エンジン68によって決定された実トラバーサル時間を含む。ディスプレイ250は、地理的エリア252に含まれる道路区間のサブセットについての実トラバーサル時間を含むが、これは説明を容易にするためだけのものにすぎない。性能評価エンジン68は、地理的エリア252内の道路区間の各々についての実トラバーサル時間を決定してもよい。いずれにしても、性能評価エンジン68は、パスファインディングアルゴリズムを使用して、開始位置202から宛先位置212までの事後判明ルート候補を特定してもよく、各道路区間には、その道路区間の実トラバーサル時間に対応する重みが割り当てられている。
【００３９】
たとえば、開始位置202から始まり、道路区間254〜274の各々は、道路区間候補のセットに含まれる。性能評価エンジン68は、開始位置202に接続されている最も低い重みを有する道路区間を特定し、特定された道路区間をセットから削除してもよい。この例では、開始位置202に接続されている唯一の道路区間は、5の重みを有する道路区間254であるので、性能評価エンジン68は、道路区間254を特定し、セットから道路区間254を削除する。次に、性能評価エンジン68は、道路区間254に接続されている最も低い重みを有するセットに残っている道路区間を特定し、特定された道路区間をセットから削除する。このプロセスは、宛先位置に到達するまで繰り返される。この例では、道路区間254に接続されているセット内に残っている道路区間は、道路区間256および258である。道路区間256は、より低い重み7を有しており、したがって、特定され、セットから削除される。道路区間256に接続されているセット内に残っている道路区間は、道路区間260および262である。道路区間260は、より低い重み3を有しており、したがって、特定され、セットから削除される。道路区間264、270、272、274もまた、事後判明ルート候補のために特定される。したがって、事後判明ルート候補の総重量の合計または総トラバーサル時間は23分である。
【００４０】
このプロセスは、次いで、第1の反復で選択されなかった道路区間(たとえば、道路区間258、262、266、268)について繰り返される。第2の反復では、性能評価エンジン68は、19分の第2の事後判明ルート候補の総重量または総トラバーサル時間を有する道路区間254、258、266、268、および274を含む第2の事後判明ルート候補を特定する。第3の反復では、性能評価エンジン68は、20分の第3の事後判明ルート候補の総重量または総トラバーサル時間を有する道路区間254、256、262、268、および274を含む第3の事後判明ルート候補を特定する。第3の反復の後、性能評価エンジン68は、道路区間254〜274の各々を選択し、プロセスが終了する。次いで、性能評価エンジン68は、3つの事後判明ルート候補を比較し、第2の事後判明ルート候補が19分の宛先位置までの最速の時間を有することを決定する。したがって、性能評価エンジン68は、第2の事後判明ルート候補を事後判明ルートとして選択する。
【００４１】
他の実装形態では、性能評価エンジン68は、道路区間から宛先位置までの時間量を推定する各道路区間に追加の重みを割り当てることによって、事後判明ルート候補を特定する。追加の重みは、ヒューリスティック関数を使用して決定されてもよい。たとえば、追加の重みに対応する推定は、道路区間から宛先位置までの物理的距離に基づいてもよい。宛先位置に近い道路区間は、宛先位置からさらに遠い道路区間よりも低い追加の重みが割り当てられてもよい。たとえば、道路区間256は7の重みを有し得るが、道路区間258は8の重みを有する。しかしながら、道路区間256は、道路区間258が宛先位置に近いので、道路区間258よりも高い追加の重みを有してもよい。性能評価エンジン68は、重みと開始位置202に接続された追加の重みとの最も低い組合せを有する道路区間を特定し得る。次いで、性能評価エンジン68は、重みと特定された道路区間に接続された追加の重みとの最も低い組合せを有する道路区間を特定してもよく、宛先位置に到達するまでこのプロセスを繰り返してもよい。このようにして、性能評価エンジン68によって特定された第1の事後判明ルート候補は、宛先位置までの最速の時間を有する事後判明ルートであってもよく、性能評価エンジン68は、第1の反復で特定されなかった道路区間を反復する必要がない場合がある。
【００４２】
図3Aおよび図3Bは、開始位置から宛先位置までの事後判明ルート候補を特定するための地理的エリア300、350内の事後判明ナビゲーションデータの追加の例示的な表示を示す。図3Aは、道路区間A、B、C、D、E、F、およびGを有する地理的エリア302のディスプレイ300を含む。道路区間Aの重みは8、道路区間Bの重みは3、道路区間Cの重みは1、道路区間Dの重みは3、道路区間Eの重みは1、道路区間Fの重みは4、道路区間Gの重みは5である。重みを使用して、性能評価エンジン68は、地理的エリア302内の開始位置から宛先位置まで移動するための事後判明ルートを決定してもよい。
【００４３】
図3Bは、道路区間O、P、S、T、U、V、およびWを有する地理的エリア352の別の例示的なディスプレイ350を含む。道路区間Pの重みは6、道路区間Tの重みは1、道路区間Uの重みは1.5、道路区間VおよびWの重みは0.5である。いくつかの実装形態では、性能評価エンジン68は、道路区間から次の道路区間への操作、前の道路区間から道路区間への操作、またはこれらの任意の適切な組合せに応じて、同じ道路区間の異なるトラバーサル時間を決定してもよい。たとえば、道路区間は、数台の車両が左折する一方で、数台の車両が右折する高速道路の出口であってもよい。したがって、道路区間のトラバーサル時間は、道路区間から次の道路区間への左折を行うとき、右折を行うときよりも高くなり得る。別の例では、ある道路区間から別の道路区間に左折することは非常に困難であり、したがって、車両が交差点に到達してから左折するまでに、追加で平均3分かかる可能性がある。したがって、道路区間のトラバース時間は、道路区間から次の道路区間への左折を行うとき、次の道路区間に引き続き直進するときよりも高くなる場合がある。その結果、性能評価エンジン68は、道路区間から次の道路区間への操作、前の道路区間から道路区間への操作、またはこれらの任意の適切な組合せに応じて、同じ道路区間のいくつかのトラバーサル時間を特定してもよい。道路区間から次の道路区間への操作に依存する道路区間のためのトラバーサル時間は、道路区間を移動し、ルートが生成されたのと同じ時間枠内に次の道路区間に特定の操作を行う車両のトラバーサル時間に基づいていてもよい。
【００４４】
例示的なディスプレイ350では、道路区間Oは、道路区間Oを移動し、道路区間Pに引き続き直進するときの第1の重み5、および道路区間Oを移動し、道路区間Sに右折するときの第2の重み4を含む2つの重みを有する。また、道路区間Sは、道路区間Sを移動し、道路区間Tに左折するときの第1の重み3、および道路区間Sを移動し、道路区間Uに右折するときの第2の重み2を含む2つの重みを有している。開始位置354から宛先位置356までの事後判明ルートを決定するとき、性能評価エンジン68は、道路区間OおよびSを特定し得る。次いで、性能評価エンジン68は、道路区間SおよびTの道路区間Tを含む総合重量が4であり、道路区間SおよびUの道路区間Uを含む総合重量が3.5であると決定し得る。したがって、道路区間Uに右折するときよりも道路区間Tに左折するときの方が道路区間Sの重みが大きいので、性能評価エンジン68は、道路区間Tが道路区間Uよりも低い重みを有しているにもかかわらず、道路区間O、S、U、およびWを含むものとして事後判明ルートを選択する。
【００４５】
図4は、たとえば、ネットワークサーバ(性能評価サーバ60など)において実装することができる、宛先位置までの最適なルートを特定するナビゲーションアプリケーションの性能を評価するための例示的な方法400を示す。方法は、コンピュータ可読メモリに記憶され、性能評価サーバ60の1つまたは複数のプロセッサで実行可能な命令のセットにおいて実装することができる。たとえば、方法は、性能評価エンジン68によって実装することができる。
【００４６】
ブロック402において、開始位置から宛先位置までのルートの指示が、たとえば、ルートに対応するナビゲーション方向を要求したユーザのクライアントデバイス82a〜nから受信される。なお、ルートの指示は、ルートが完了した後に、性能評価サーバ60に提供されてもよい。さらに、ルートの指示は、ルートをトラバースするための予測時間量、ルートの開始位置、ルートの宛先位置、ルート上の道路区間および操作、各道路区間をトラバースするための予測時間量などを含み得る。
【００４７】
次いで、ブロック404において、性能評価サーバ60は、ルートの実際のトラバース時間を決定する。より具体的には、クライアントデバイス82a〜nは、ルートの移動時に、測位データおよび/または他のセンサーデータを性能評価サーバ60に提供してもよい。これは、ルートの開始時間、ユーザが宛先位置に到着した時間、および/またはルートに沿ったユーザの様々な場所に対応する時間を含み得る。
【００４８】
性能評価サーバ60はまた、ルートと同じ地理的エリア内でルートと同じ時間枠内に移動するクライアントデバイス82a〜nから測位データおよび/または他のセンサーデータを受信する。たとえば、地理的エリアは、開始位置と宛先位置の両方を含むnマイル×nマイルのエリアであってもよく、ここで、nは、開始位置と宛先位置との間の距離に比例する(たとえば、nは、開始位置と宛先位置との間の距離に等しい、開始位置と宛先位置との間の距離の2倍などであってもよい)。時間フレームは、ユーザがナビゲーション方向を要求したときを含む1時間間隔、2時間間隔などであってもよい。
【００４９】
次いで、性能評価エンジン68は、ルートに対応するナビゲーション方向を要求したクライアントデバイス82a〜nから、ならびに同じ時間枠内に同じ地理的エリア内を移動する他のクライアントデバイス82a〜nからの測位データおよび/または他のセンサーデータを使用して、ユーザがナビゲーション方向を要求したときに地理的エリア内の道路区間についての実トラバーサル時間を生成してもよい(ブロック406)。性能評価エンジン68は、車両が道路区間に進入した時間と道路区間を出た時間との間の差に基づいて、特定の道路区間の実トラバーサル時間を決定してもよい。他の実装形態では、性能評価エンジン68は、車両が道路区間上を移動した平均速度および道路区間の長さに基づいて、特定の道路区間の実トラバーサル時間を決定してもよい。
【００５０】
次いで、性能評価エンジン68は、地理的エリア内の道路区間の移動時間に基づいて、ユーザがナビゲーション方向を要求した時点における、最短の時間量で開始位置から宛先位置まで移動するための事後判明ルートを決定する(ブロック408)。より具体的には、性能評価エンジン68は、パスファインディングアルゴリズムを使用して、開始位置から宛先位置までの事後判明ルート候補を特定してもよく、ここで、各道路区間には、その道路区間の実トラバーサル時間に対応する重みが割り当てられている。いくつかの実装形態では、性能評価エンジン68は、開始位置から宛先位置までの道路区間の各組合せを、事後判明ルート候補として特定してもよい。各事後判明ルート候補には、事後判明ルート候補上の道路区間の重みの総計が事後判明ルート候補のスコアとして割り当てられてもよい。性能評価エンジン68は、最も低いスコアを有する事後判明ルート候補を事後判明ルートとして選択してもよい。
【００５１】
他の実装形態では、各道路区間には、道路区間の実際の移動時間に対応する第1の重み、および道路区間から宛先位置までの時間量の推定に対応する第2の重みが割り当てられる。次いで、性能評価エンジン68は、開始位置に接続されている第1の重みと第2の重みの最も低い組合せを有する道路区間を特定してもよい。次いで、性能評価エンジン68は、特定された道路区間に接続された第1および第2の重みとの最も低い組合せを有する道路区間を特定してもよく、宛先位置に到達するまでこのプロセスを繰り返してもよい。このようにして、性能評価エンジン68は、開始位置から宛先位置までの第1の事後判明ルートを事後判明ルートとして選択してもよく、複数の事後判明ルート候補を特定しないようにしてもよい。
【００５２】
いずれにしても、ブロック410において、性能評価エンジン68は、事後判明ルートを、クライアントデバイス82a〜n上で実行されるナビゲーションアプリケーションによって生成されたルートと比較する。性能評価エンジン68はまた、ルートをトラバースするための予測時間量を、ルートをトラバースするための実時間量、および/または事後判明ルートをトラバースするための時間量と比較してもよい。
【００５３】
したがって、性能評価エンジン68は、事後判明ルートとナビゲーションアプリケーションによって生成されたルートとの比較、および/またはルートをトラバースするための予測時間量とルートをトラバースするための実時間量および/または事後判明ルートをトラバースするための時間量との比較に基づいて、ルートについての性能測定基準を生成してもよい(ブロック412)。性能測定基準は、実際のルートのうち事後判明ルートに含まれていた道路区間の割合、または実際のルートに含まれていた事後判明ルートの合計距離の割合を含み得る。また、性能測定基準は、ルートをトラバースするための予測時間量とルートをトラバースするための実時間量との差、ルートをトラバースするための実時間量と事後判明ルートをトラバースするためにかかったであろう時間量との差、およびルートをトラバースするための予測時間量と事後判明ルートをトラバースするためにかかったであろう時間量との差を含んでいてもよい。
【００５４】
より具体的には、性能評価エンジン68は、以下の要因、(i)実際のルートのうち事後判明ルートに含まれていた道路区間の数または割合、(ii)事後判明ルートに含まれていた代替道路区間の数または割合、(iii)ルートをトラバースするための予測時間量とルートをトラバースするための実時間量との差、(iv)ルートをトラバースするための実時間量と、事後判明ルートをトラバースするのにかかるであろう時間量との差、(v)ルートをトラバースするための予測時間量と、事後判明ルートをトラバースするのにかかるであろう時間量との差、(vi)実際のルートに含まれていた事後判明ルートの合計距離の割合のうちの1つまたは複数に基づいて性能測定基準を生成してもよい。性能評価エンジン68は、各要因に応じてルートのための複数の性能測定基準を生成してもよく、または性能評価エンジン68は、これらの要因の任意の適切な組合せに基づいて性能測定基準を生成してもよい。たとえば、性能評価エンジン68は、要因ごとにスコアを割り当ててもよく、要因固有のスコアを任意の適切な方法で集約または結合して、性能測定基準として使用され得る合計スコアを生成してもよい。合計スコアは、平均または要因固有のスコア、各要因が異なる重みを割り当てられている要因固有のスコアの加重平均、要因固有のスコアの合計などであってもよい。
【００５５】
さらに、性能評価エンジン68は、事後判明ルートを生成し、指定された地理的領域(たとえば、都市、州、国など)内の複数のルートについての性能測定基準を決定してもよい。次いで、性能評価エンジン68は、ルートまたはルート上の道路区間についての個々の性能測定基準に基づいて、ナビゲーションアプリケーションおよび/または特定の地理的領域についての全体的な性能測定基準を生成してもよい。たとえば、全体的な性能測定基準は、個々の性能測定基準の平均、移動平均または時間減衰平均など個々の性能測定基準の加重平均、個々の性能測定基準の総計、または個々の性能測定基準の任意の適切な組合せであってもよい。
【００５６】
さらに、性能評価エンジン68は、クライアントデバイス10上の表示のために、全体的な性能測定基準および/または個々の性能測定基準を提供してもよい(ブロック414)。次いで、性能測定基準ディスプレイ22は、クライアントデバイス10のユーザインターフェース32上に、全体的な性能測定基準および/または個々の性能測定基準を提示してもよい。このようにして、ナビゲーションソフトウェアおよびサービスをライセンス供与している顧客またはパートナーは、ナビゲーション性能データを閲覧してもよい。さらに、ナビゲーションアプリケーションを作成した組織の従業員または他のメンバーは、ナビゲーションアプリケーションによって生成されたルートの品質を決定する、ルート決定方法の欠陥を見つける、これらの欠陥について根本原因分析を実行するなどのために、ナビゲーション性能データを閲覧してもよい。
【００５７】
いくつかの実装形態では、クライアントデバイス10、性能評価サーバ60、および/またはナビゲーションデータサーバ34は、性能測定基準および/または事後判明ルートに基づいて、ナビゲーションデータサーバ34によって使用されるルート決定方法のエラーを特定してもよい。たとえば、道路区間についての個々の性能測定基準がしきい値未満であるとき、性能評価サーバ60は、ナビゲーションアプリケーションによって生成されたルートと事後判明ルートとの間の不一致を特定するために、ルートを分析してもよい。たとえば、性能評価サーバ60は、たとえば、複数の時間帯、異なる天候や交通状態など複数のインスタンスにおいて、ルート決定方法による道路区間の予測トラバーサル時間よりも道路区間の実トラバーサル時間の方が長いことを特定し、それによって、ルート決定方法のエラーを特定し得る。したがって、性能評価サーバ60および/またはナビゲーションデータサーバ34は、道路区間により長い予測トラバーサル時間が割り当てられるようにルート決定方法を調整するなどの修正アクションを実行してもよい。
【００５８】
また、性能評価サーバ60は、ナビゲーションアプリケーションによって生成されたルートと事後判明ルートとの不一致を分析することによって、根本原因分析を実行してもよい。たとえば、性能評価サーバ60は、道路区間から、生成されたルートの大部分が難しい左折を含む、次の区間への難しい左折のために、ある道路区間が予測トラバーサル時間よりも実トラバーサル時間の方が長いと決定し得る。したがって、性能評価サーバ60は、不一致の原因が難しい左折によるものであると決定してもよい。いくつかの場合には、性能評価サーバ60は、ルート決定モデルのパラメータを調整するために、根本原因分析の結果をナビゲーションデータサーバ34に提供してもよい。たとえば、ルート決定モデルは、特定の道路区間をルートに含めるかどうかを決定するための複数のパラメータの組合せを含んでもよい。各パラメータは重み付けされてもよく、パラメータの重みは性能測定基準に基づいて調整されてもよい。
追加の考慮事項
【００５９】
以下の追加の考慮事項が、上記の説明に適用される。本明細書を通して、複数のインスタンスは、単一のインスタンスとして説明された構成要素、動作、または構造を実装し得る。1つまたは複数の方法の個々の動作が別々の動作として図示され説明されているが、1つまたは複数の個々の動作が同時に実行されてもよく、動作が示した順序で実行される必要はない。例示的な構成において別個の構成要素として提示される構造および機能は、結合された構造または構成要素として実装されてもよい。同様に、単一の構成要素として提示される構造および機能は、別個の構成要素として実装されてもよい。これらおよび他の変形、修正、追加、および改良は、本開示の主題の範囲内に入る。
【００６０】
さらに、いくつかの実施形態は、本明細書では、論理またはいくつかの構成要素、モジュール、または機構を含むものとして説明されている。モジュールは、ソフトウェアモジュール(たとえば、機械可読媒体上に記憶されるコード)またはハードウェアモジュールのいずれかを構成し得る。ハードウェアモジュールは、いくつかの動作を実行することができる有形のユニットであり、ある方法で構成または配置され得る。例示的な実施形態では、(たとえば、スタンドアロン、クライアント、またはサーバコンピュータシステムなど)1つもしくは複数のコンピュータシステムまたは(たとえば、プロセッサまたはプロセッサ群など)コンピュータシステムの1つもしくは複数のハードウェアモジュールは、ソフトウェア(たとえば、アプリケーションまたはアプリケーション部分)によって、本明細書で説明したいくつかの動作を実行するように動作するハードウェアモジュールとして構成されてもよい。
【００６１】
様々な実施形態では、ハードウェアモジュールは、機械的または電子的に実装されてもよい。たとえば、ハードウェアモジュールは、いくつかの動作を実行するように永続的に構成された(たとえば、フィールドプログラマブルゲートアレイ(FPGA)または特定用途向け集積回路(ASIC)などの専用プロセッサとして)専用の回路または論理を含み得る。ハードウェアモジュールはまた、いくつかの動作を実行するためにソフトウェアによって一時的に構成される(たとえば、汎用プロセッサまたは他のプログラマブルプロセッサ内に包含される)プログラマブル論理または回路を含み得る。ハードウェアモジュールを機械的に、専用の永続的に構成された回路、または一時的に構成された回路(たとえば、ソフトウェアによって構成された)で実装するかの決定は、コストおよび時間の考慮事項によって駆動され得ることが諒解されよう。
【００６２】
したがって、ハードウェアという用語は、ある方法で動作するように、または本明細書に記載したいくつかの動作を実行するように、物理的に構築された、永続的に構成された(たとえば、ハードワイヤードされた)、または一時的に構成された(たとえば、プログラムされた)エンティティである、有形のエンティティを包含すると理解されるものとする。ハードウェアモジュールが一時的に構成されている(たとえば、プログラムされている)実施形態を考慮すると、ハードウェアモジュールの各々は、時間的に任意の1つのインスタンスで構成またはインスタンス化される必要はない。たとえば、ハードウェアモジュールがソフトウェアを使用して構成された汎用プロセッサを含む場合、汎用プロセッサは、異なるときにそれぞれ異なるハードウェアモジュールとして構成されてもよい。ソフトウェアは、それに応じて、たとえば、ある時間インスタンスに特定のハードウェアモジュールを構成し、異なる時間インスタンスに異なるハードウェアモジュールを構成するようにプロセッサを構成してもよい。
【００６３】
ハードウェアおよびソフトウェアモジュールは、他のハードウェアおよび/またはソフトウェアモジュールに情報を提供し、それから情報を受信することができる。したがって、記載されたハードウェアモジュールは、通信可能に結合されているものとみなされ得る。複数のそのようなハードウェアまたはソフトウェアモジュールが同時に存在する場合、通信は、ハードウェアまたはソフトウェアモジュールを接続する信号送信を介して(たとえば、適切な回路およびバスを介して)達成されてもよい。複数のハードウェアモジュールまたはソフトウェアが異なるときに構成またはインスタンス化される実施形態では、そのようなハードウェアまたはソフトウェアモジュール間の通信は、たとえば、複数のハードウェアまたはソフトウェアモジュールがアクセス可能なメモリ構造内の情報の記憶および検索を介して達成されてもよい。たとえば、1つのハードウェアまたはソフトウェアモジュールは、ある動作を実行し、その動作の出力を、それが通信可能に結合されているメモリデバイスに記憶してもよい。さらなるハードウェアまたはソフトウェアモジュールは、次いで、後で、メモリデバイスにアクセスして、記憶された出力を取得して処理することができる。また、ハードウェアおよびソフトウェアモジュールは、入力または出力デバイスとの通信を開始してもよく、リソース(たとえば、情報の集合)上で動作することができる。
【００６４】
本明細書に記載された例示的な方法の様々な動作は、関連する動作を実行するように一時的に構成された(たとえば、ソフトウェアによって)または永続的に構成された1つまたは複数のプロセッサによって、少なくとも部分的に実行されてもよい。一時的に構成されていても永続的に構成されていても、そのようなプロセッサは、1つまたは複数の動作または機能を実行するように動作するプロセッサ実装モジュールを構成し得る。本明細書で言及されるモジュールは、いくつかの例示的な実施形態では、プロセッサ実装モジュールを含み得る。
【００６５】
同様に、本明細書に記載される方法またはルーチンは、少なくとも部分的にプロセッサ実装であってもよい。たとえば、方法の少なくとも一部の動作は、1つまたは複数のプロセッサまたはプロセッサ実装ハードウェアモジュールによって実行されてもよい。いくつかの動作の性能は、単一のマシン内に存在するだけでなく、いくつかのマシンにわたって配置された1つまたは複数のプロセッサの間で分散されてもよい。いくつかの例示的な実施形態では、プロセッサは、単一の場所(たとえば、家庭環境内、オフィス環境内、またはサーバファームとして)に配置されてもよく、他の実施形態では、プロセッサは、いくつかの場所に分散されてもよい。
【００６６】
また、1つまたは複数のプロセッサは、「クラウドコンピューティング」環境において、またはSaaSとして、関連する動作の性能をサポートするように動作してもよい。たとえば、上記のように、少なくとも一部の動作は、(プロセッサを含むマシンの例として)コンピュータのグループによって実行されてもよく、これらの動作は、ネットワーク(たとえば、インターネット)を介して、1つまたは複数の適切なインターフェース(たとえば、API)を介してアクセス可能である。
【００６７】
いくつかの動作の性能は、単一のマシン内に存在するだけでなく、いくつかのマシンにわたって配置された、1つまたは複数のプロセッサ間で分散されていてもよい。いくつかの例示的な実施形態では、1つまたは複数のプロセッサまたはプロセッサ実装モジュールは、単一の地理的位置(たとえば、家庭環境、オフィス環境、またはサーバファーム内)に配置されてもよい。他の例示的な実施形態では、1つまたは複数のプロセッサまたはプロセッサ実装モジュールは、いくつかの地理的位置に分散されていてもよい。
【００６８】
本明細書のいくつかの部分は、マシンメモリ(たとえば、コンピュータメモリ)内のビットまたはバイナリデジタル信号として記憶されたデータにおける動作のアルゴリズムまたは記号表現で提示される。これらのアルゴリズムまたは記号表現は、その仕事の内容を他の当業者に伝えるためにデータ処理分野の当業者によって使用される技法の例である。本明細書で使用する「アルゴリズム」または「ルーチン」は、所望の結果につながる自己矛盾のない一連の動作または類似の処理である。この文脈では、アルゴリズム、ルーチン、および動作は、物理量の物理的操作を伴う。典型的には、必ずしもそうではないが、そのような量は、マシンによって記憶、アクセス、転送、結合、比較、またはさもなければ操作することができる電気信号、磁気信号、または光学信号の形態をとることができる。「データ」、「コンテンツ」、「ビット」、「値」、「要素」、「シンボル」、「文字」、「用語」、「数」、「数字」などの単語を使用して、そのような信号を呼ぶことは、主に一般的な用法という理由で、時として便利である。しかしながら、これらの単語は、単に便利なラベルに過ぎず、適切な物理量と関連付けられるものとする。
【００６９】
特に明記しない限り、「処理する」、「計算する」、「算出する」、「決定する」、「提示する」、「表示する」などの単語を使用する本明細書の説明は、1つまたは複数のメモリ(たとえば、揮発性メモリ、不揮発性メモリ、またはそれらの組合せ)、レジスタ、または情報を受信、記憶、送信、または表示する他の機械構成要素内の物理的(たとえば、電子的、磁気的、または光学的)量として表されるデータを操作または変換するマシン(たとえば、コンピュータ)のアクションまたはプロセスを指し得る。
【００７０】
本明細書で使用される「一実施形態」または「実施形態」の任意の言及は、実施形態に関連して説明される特定の要素、特徴、構造、または特性が少なくとも1つの実施形態に含まれることを意味する。本明細書の様々な場所における「一実施形態では」という句の出現は、必ずしもすべてが同じ実施形態を指しているわけではない。
【００７１】
いくつかの実施形態は、それらの派生語とともに「結合された」および「接続された」という表現を使用して説明されてもよい。たとえば、いくつかの実施形態は、2つ以上の要素が物理的または電気的に直接的に接触していることを示すために「結合された」という用語を使用して説明され得る。しかしながら、「結合された」という用語は、2つ以上の要素が互いに直接接触していないが、依然として互いに協働しまたは相互作用していることも意味し得る。実施形態は、この文脈に限定されない。
【００７２】
本明細書で使用される「備える」「備えている」「含む」「含んでいる」「有する」「有している」またはその任意の他の変形は、非排他的な包含をカバーすることが意図される。たとえば、要素のリストを含むプロセス、方法、物品、または装置は、必ずしもそれらの要素のみに限定されるものではなく、明示的に列挙されていないかまたはそのようなプロセス、方法、物品または装置に固有の他の要素を含み得る。さらに、反対のことが明記されていない限り、「または」は排他的ではなく包括的なまたはを指す。たとえば、条件Aまたは条件Bは、次のうちのいずれかによって満たされる。Aが真(または存在する)、Bが偽(または存在しない)、Aが偽(または存在しない)、Bが真(または存在する)、AとBの両方が真(または存在する)である。
【００７３】
さらに、「a」または「an」の使用は、本明細書の実施形態の要素および構成要素を記載するために使用される。これは、単に便宜上であり、説明の一般的な意味を与えるために行われる。この説明は、1つまたは少なくとも1つを含むように読まれるものとし、単数形は、それが他の意味であることが明らかでない限り、複数形も含む。
【００７４】
本開示を読めば、当業者であれば、本明細書に開示されている原理により、ナビゲーションアプリケーションの性能を評価するための、さらに追加の代替的な構造的および機能的設計を理解するであろう。したがって、特定の実施形態および用途を図示および説明してきたが、開示された実施形態は、本明細書に開示される厳密な構成および構成要素に限定されないことを理解されたい。添付の特許請求の範囲に定義された意図および範囲から逸脱することなく、本明細書に開示された方法および装置の配置、動作および詳細において、当業者には明らかであろう様々な修正、変更および変形がなされ得る。
【符号の説明】
【００７５】
10  クライアントコンピューティングデバイス
12  グラフィックス処理ユニット(GPU)
14  I/Oモジュール
16  プロセッサ(CPU)
20  メモリ
22  性能測定基準ディスプレイ
26  オペレーティングシステム(OS)
30  通信ネットワーク
32  ユーザインターフェース(UI)
34  ナビゲーションデータサーバ
50  マップデータサーバ
60  性能評価サーバ
62  プロセッサ
64  メモリ
68  性能評価エンジン
80  データベース
82a〜n  クライアントデバイス
84  地理アプリケーション
86  マップディスプレイ
100  通信システム
200  ナビゲーションディスプレイ
202  現在位置
202  開始位置
212  事業所
212  宛先位置
216  ルート
218  ルート
250  ディスプレイ
252  地理的エリア
254〜274  道路区間
256  代替道路区間
300  地理的エリア
300  ディスプレイ
302  地理的エリア
350  地理的エリア
350  ディスプレイ
352  地理的エリア
354  開始位置
356  宛先位置
【図１】
2021521411.tif 000003
【図２Ａ】
2021521411.tif 000004
【図２Ｂ】
2021521411.tif 000005
【図３Ａ】
2021521411.tif 000006
【図３Ｂ】
2021521411.tif 000007
【図４】
2021521411.tif 000008
【手続補正書】
【提出日】令和2年6月25日(2020.6.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
宛先位置までの最適なルートを特定するナビゲーションアプリケーションの性能を評価するための方法であって、
複数の宛先位置までのナビゲーションアプリケーションによって生成された複数のルートの各々について、
1つまたは複数のプロセッサにおいて、複数の道路区間を含む開始位置から宛先位置までのナビゲーション方向についてのユーザによる要求に応答して、前記ナビゲーションアプリケーションによって生成された前記ルートの指示を受信するステップと、
前記1つまたは複数のプロセッサによって、前記複数の道路区間をトラバースするためのおよび代替道路区間をトラバースするための実時間量に基づいて、前記ユーザが前記ナビゲーション方向を要求した時点における、最短の時間量で前記開始位置から前記宛先位置まで移動するための事後判明ルートを決定するステップであって、前記事後判明ルートは、前記ユーザが前記宛先位置に到着した後に決定される、ステップと、
前記1つまたは複数のプロセッサによって、道路区間の数または時間量に関連した前記ルートについての性能測定基準を決定するために、前記事後判明ルートと前記ルートを比較するステップと、
前記1つまたは複数のプロセッサによって、前記複数のルートの各々についての前記性能測定基準に基づいて、前記ナビゲーションアプリケーションの全体的な性能測定基準を提供するステップと
を含む、方法。
【請求項２】
前記1つまたは複数のプロセッサにおいて、前記ユーザが前記ナビゲーション方向を要求した時点において計算された、前記ルートをトラバースするための予測時間量の指示を受信するステップと、
前記1つまたは複数のプロセッサにおいて、前記ユーザが前記宛先位置に到着した後に計算された、前記ルートをトラバースするのにかかった実時間量の指示を受信するステップと
をさらに含み、
前記ルートの前記性能測定基準の前記決定は、前記ルートをトラバースするのにかかった前記実時間量と前記ルートをトラバースするための前記予測時間量を比較することにさらに基づく、請求項1に記載の方法。
【請求項３】
前記ルートについての性能測定基準を決定するために、前記事後判明ルートと前記ルートを比較するステップは、前記1つまたは複数のプロセッサによって、
前記ルートと前記事後判明ルートの両方に含まれる道路区間の数、
前記事後判明ルートに含まれる代替道路区間の数、
前記ルートをトラバースするための前記予測時間量と前記ルートをトラバースするのにかかった前記実時間量との差、
前記ルートをトラバースするのにかかった前記実時間量と前記事後判明ルートをトラバースするのにかかるであろう時間量との差、または
前記ルートをトラバースするための前記予測時間量と前記事後判明ルートをトラバースするのにかかるであろう前記時間量との差
のうちの少なくとも1つに基づいて前記性能測定基準を決定するステップを含む、請求項2に記載の方法。
【請求項４】
前記1つまたは複数のプロセッサによって、前記全体的な性能測定基準、および前記ナビゲーションアプリケーションによって生成された前記複数のルートと前記事後判明ルートとの間の不一致に基づいて、前記ナビゲーションアプリケーションによって実行されるルート決定方法のエラーを特定するステップと、
前記1つまたは複数のプロセッサによって、修正アクションを実行するための前記ルート決定方法の前記エラーの原因を決定するステップと
をさらに含む、請求項1に記載の方法。
【請求項５】
前記ナビゲーションアプリケーションによって実行されるルート決定方法のエラーを特定するステップは、
前記ルートの前記性能測定基準がしきい値を下回ると判定するステップと、
前記ルート上の道路区間では予測トラバーサル時間よりも実トラバーサル時間の方が長いことを特定するために前記ルートを分析するステップと、
前記道路区間の前記予測トラバーサル時間のエラーを特定するステップと
を含む、請求項4に記載の方法。
【請求項６】
前記1つまたは複数のプロセッサによって、前記全体的な性能測定基準に基づいて、宛先位置までのルートを特定するためのルート決定モデルを調整するステップ
をさらに含む、請求項1に記載の方法。
【請求項７】
事後判明ルートを決定するステップは、
前記1つまたは複数のプロセッサにおいて、ユーザが前記宛先位置までの前記ルートをトラバースした時間期間と同じ時間期間内の複数の時間インスタンスにおける測位データを1つまたは複数のコンピューティングデバイスから受信するステップと、
前記1つまたは複数のプロセッサによって、道路区間をトラバースするための時間量を決定するために、前記複数の時間インスタンスにおける前記測位データを分析するステップと、
前記1つまたは複数のプロセッサによって、前記道路区間をトラバースするための前記決定された時間量を使用して、前記最短の時間量で前記開始位置から前記宛先位置まで移動するための前記事後判明ルートを決定するステップと
を含む、請求項1に記載の方法。
【請求項８】
前記1つまたは複数のプロセッサによって、前記道路区間上の前記複数の時間インスタンスにおける前記測位データに基づいて、各道路区間の速度値を決定するステップと、
前記1つまたは複数のプロセッサによって、前記道路区間の前記速度値に基づいて、各道路区間をトラバースするための時間量を決定するステップと、
前記1つまたは複数のプロセッサによって、前記宛先位置までの総時間量を最小にする前記開始位置から前記宛先位置までの道路区間の組合せを特定することによって、前記最短の時間量で前記開始位置から前記宛先位置まで移動するための前記事後判明ルートを決定するステップと
をさらに含む、請求項7に記載の方法。
【請求項９】
宛先位置までの最適なルートを特定するナビゲーションアプリケーションの性能を評価するためのサーバデバイスであって、
1つまたは複数のプロセッサと、
前記1つまたは複数のプロセッサに結合され、前記1つまたは複数のプロセッサによって実行されると、前記サーバデバイスに、
複数の宛先位置までのナビゲーションアプリケーションによって生成された複数のルートの各々について、
複数の道路区間を含む開始位置から宛先位置までのナビゲーション方向についてのユーザによる要求に応答して、前記ナビゲーションアプリケーションによって生成された前記ルートの指示を受信することと、
前記複数の道路区間をトラバースするためのおよび代替道路区間をトラバースするための実時間量に基づいて、前記ユーザが前記ナビゲーション方向を要求した時点における、最短の時間量で前記開始位置から前記宛先位置まで移動するための事後判明ルートを決定することであって、前記事後判明ルートは、前記ユーザが前記宛先位置に到着した後に決定される、ことと、
道路区間の数または時間量に関連した前記ルートについての性能測定基準を決定するために、前記事後判明ルートと前記ルートを比較することと、
前記複数のルートの各々についての前記性能測定基準に基づいて、前記ナビゲーションアプリケーションの全体的な性能測定基準を提供することと
をさせる命令を記憶する非一時的コンピュータ可読メモリと
を含む、サーバデバイス。
【請求項１０】
前記命令は、さらに、前記サーバデバイスに、
前記ユーザが前記ナビゲーション方向を要求した時点において計算された、前記ルートをトラバースするための予測時間量の指示を受信することと、
前記ユーザが前記宛先位置に到着した後に計算された、前記ルートをトラバースするのにかかった実時間量の指示を受信することと
をさせ、
前記ルートの前記性能測定基準の前記決定は、前記ルートをトラバースするのにかかった前記実時間量と前記ルートをトラバースするための前記予測時間量を比較することにさらに基づく、請求項9に記載のサーバデバイス。
【請求項１１】
前記性能測定基準は、
前記ルートと前記事後判明ルートの両方に含まれる道路区間の数、
前記事後判明ルートに含まれる代替道路区間の数、
前記ルートをトラバースするための前記予測時間量と前記ルートをトラバースするのにかかった前記実時間量との差、
前記ルートをトラバースするのにかかった前記実時間量と前記事後判明ルートをトラバースするのにかかるであろう時間量との差、または
前記ルートをトラバースするための前記予測時間量と前記事後判明ルートをトラバースするのにかかるであろう前記時間量との差
のうちの少なくとも1つに基づいて決定される、請求項10に記載のサーバデバイス。
【請求項１２】
前記命令は、さらに、前記サーバデバイスに、
前記全体的な性能測定基準に基づいて、前記ナビゲーションアプリケーションによって実行されるルート決定方法におけるエラーを特定することと、
修正アクションを実行するための前記ルート決定方法の前記エラーの原因を決定することと
をさせる、請求項9に記載のサーバデバイス。
【請求項１３】
前記命令は、さらに、前記サーバデバイスに、
前記全体的な性能測定基準に基づいて、宛先位置までのルートを特定するためのルート決定モデルを調整すること
をさせる、請求項9に記載のサーバデバイス。
【請求項１４】
事後判明ルートを決定するために、前記命令は、前記サーバデバイスに、
ユーザが前記宛先位置までの前記ルートをトラバースした時間期間と同じ時間期間内の複数の時間インスタンスにおける測位データを1つまたは複数のコンピューティングデバイスから受信することと、
道路区間をトラバースするための時間量を決定するために、前記複数の時間インスタンスにおける前記測位データを分析することと、
前記道路区間をトラバースするための前記決定された時間量を使用して、前記最短の時間量で前記開始位置から前記宛先位置まで移動するための前記事後判明ルートを決定することと
をさせる、請求項9に記載のサーバデバイス。
【請求項１５】
前記命令は、さらに、前記サーバデバイスに、
前記道路区間上の前記複数の時間インスタンスにおける前記測位データに基づいて、各道路区間の速度値を決定することと、
道路区間の前記速度値に基づいて、各道路区間をトラバースするための時間量を決定することと、
前記宛先位置までの総時間量を最小にする前記開始位置から前記宛先位置までの道路区間の組合せを特定することによって、前記最短の時間量で前記開始位置から前記宛先位置まで移動するための前記事後判明ルートを決定することと
をさせる、請求項14に記載のサーバデバイス。
【請求項１６】
コンピューティングデバイス内の1つまたは複数のプロセッサによって実行されると、前記1つまたは複数のプロセッサに、
複数の宛先位置までのナビゲーションアプリケーションによって生成された複数のルートの各々について、
複数の道路区間を含む開始位置から宛先位置までのナビゲーション方向についてのユーザによる要求に応答して、前記ナビゲーションアプリケーションによって生成された前記ルートの指示を受信することと、
前記複数の道路区間をトラバースするためのおよび代替道路区間をトラバースするための実時間量に基づいて、前記ユーザが前記ナビゲーション方向を要求した時点における、最短の時間量で前記開始位置から前記宛先位置まで移動するための事後判明ルートを決定することであって、前記事後判明ルートは、前記ユーザが前記宛先位置に到着した後に決定される、ことと、
道路区間の数または時間量に関連した前記ルートについての性能測定基準を決定するために、前記事後判明ルートと前記ルートを比較することと、
前記複数のルートの各々についての前記性能測定基準に基づいて、前記ナビゲーションアプリケーションの全体的な性能測定基準を提供することと
をさせる命令を記憶した、コンピュータ可読記憶媒体。
【請求項１７】
前記命令はさらに、前記1つまたは複数のプロセッサに、
前記ユーザが前記ナビゲーション方向を要求した時点において計算された、前記ルートをトラバースするための予測時間量の指示を受信することと、
前記ユーザが前記宛先位置に到着した後に計算された、前記ルートをトラバースするのにかかった実時間量の指示を受信することと
をさせ、
前記ルートの前記性能測定基準の前記決定は、前記ルートをトラバースするのにかかった前記実時間量と前記ルートをトラバースするための前記予測時間量を比較することにさらに基づく、請求項16に記載のコンピュータ可読記憶媒体。
【請求項１８】
前記性能測定基準は、
前記ルートと前記事後判明ルートの両方に含まれる道路区間の数、
前記事後判明ルートに含まれる代替道路区間の数、
前記ルートをトラバースするための前記予測時間量と前記ルートをトラバースするのにかかった前記実時間量との差、
前記ルートをトラバースするのにかかった前記実時間量と前記事後判明ルートをトラバースするのにかかるであろう時間量との差、または
前記ルートをトラバースするための前記予測時間量と前記事後判明ルートをトラバースするのにかかるであろう前記時間量との差
のうちの少なくとも1つに基づいて決定される、請求項17に記載のコンピュータ可読記憶媒体。
【請求項１９】
前記命令はさらに、前記1つまたは複数のプロセッサに、
前記全体的な性能測定基準に基づいて、前記ナビゲーションアプリケーションによって実行されるルート決定方法におけるエラーを特定することと、
修正アクションを実行するための前記ルート決定方法の前記エラーの原因を決定することと
をさせる、請求項16に記載のコンピュータ可読記憶媒体。
【請求項２０】
前記命令はさらに、前記1つまたは複数のプロセッサに、
前記全体的な性能測定基準に基づいて、宛先位置までのルートを特定するためのルート決定モデルを調整すること
をさせる、請求項16に記載のコンピュータ可読記憶媒体。
【国際調査報告】
2021521411.tif 000009
2021521411.tif 000010