(57)【要約】ナビゲート可能ネットワークを通る出発地から目的地までのルーティングポリシを生成する方法であって、前記ナビゲート可能ネットワークは、前記ナビゲート可能ネットワークのナビゲート可能区分を表す複数の区分を含む電子地図により表され、各区分は当該区分に沿う予想移動時間を示すデータと関連付けられている。決定論ルーティングアルゴリズムを使用して最短予想移動時間を有する前記出発地から前記目的地までの経路を判定するために前記電子地図のそれぞれの区分に対する前記予想移動時間が使用される。次に、前記出発地から時間予算内に前記目的地に到着する確率を最大化するルーティングポリシを生成するために確率論ルーティングアルゴリズムが使用される。ここで、前記時間予算は前記判定された最短予想移動時間に少なくとも基づくものである。前記出発地から前記目的地までの経路は、各区分が前記それぞれの区分の前記予想移動時間を示すデータに基づく時間に通過されるシナリオに対して前記ルーティングポリシを適用することにより生成されうる。
2018510335.tif 000002
【特許請求の範囲】
【請求項１】
ナビゲート可能ネットワークを通る出発地から目的地までのルーティングポリシを生成する方法であって、前記ナビゲート可能ネットワークは、前記ナビゲート可能ネットワークのナビゲート可能区分を表す複数の区分を含む電子地図により表され、各区分は当該区分に沿う予想移動時間を示すデータと関連付けられており、前記方法は、
決定論ルーティングアルゴリズムを使用して最短予想移動時間を有する前記出発地から前記目的地までの経路を判定するために前記電子地図のそれぞれの区分の前記予想移動時間を使用することと、
前記出発地から時間予算内に前記目的地に到着する確率を最大化するルーティングポリシを生成するために確率論ルーティングアルゴリズムを使用することであって、前記時間予算は前記判定された最短予想移動時間に少なくとも基づくものである、前記使用することと、
を含むことを特徴とする方法。
【請求項２】
前記ルーティングポリシは、前記時間予算内に前記目的地に到着する前記確率が最大化されるように、前記出発地から前記電子地図のノードに到達するのにかかる移動時間に基づいて前記ノードで取る次の区分を判定する非線形方程式の集合に対するソリューションであることを特徴とする請求項１に記載の方法。
【請求項３】
前記時間予算は、ユーザからの入力、曜日、前記出発地と前記目的地との距離、及び、交通量及び天気等の前記ナビゲート可能ネットワークのコンディションのうちの１つ以上にさらに基づくものであることを特徴とする請求項１又は２に記載の方法。
【請求項４】
前記時間予算は、スケーリング因子を乗算された前記最短予想移動時間と同じか、あるいは、それに基づくものであることを特徴とする請求項１又は２に記載の方法。
【請求項５】
前記スケーリング因子は、ユーザからの入力、曜日、前記出発地と前記目的地との距離、及び、交通量及び天気等の前記ナビゲート可能ネットワークのコンディションのうちの１つ以上に基づくものであることを特徴とする請求項４に記載の方法。
【請求項６】
前記電子地図における各区分は、ノードにより別の区分と接続されており、前記方法は、
ノードへの到着時間が、前記出発地から前記ノードまでの経路を形成する前記区分の前記予想移動時間の合計であるように、各区分が当該それぞれの区分の前記予想移動時間を示すデータに基づく時間に通過されるシナリオに対して、前記生成されたルーティングポリシを適用することにより、前記出発地から前記目的地までの経路を生成することをさらに含むことを特徴とする請求項１乃至５の何れか１項に記載の方法。
【請求項７】
ナビゲート可能ネットワークを通る出発地と目的地との間の経路を生成する方法であって、前記ナビゲート可能ネットワークは、前記ナビゲート可能ネットワークのナビゲート可能区分を表す複数の区分を含む電子地図により表され、各区分はノードにより別の区分と接続されており、各区分は当該区分に沿う予想移動時間を示すデータと関連付けられており、前記方法は、
所定の時間予算内に前記目的地に到着する確率を最大化するルーティングポリシにアクセスすることと、
ノードへの到着時間が、前記出発地から前記ノードまでの経路を形成する前記区分の前記予想移動時間の合計であるように、各区分が当該それぞれの区分の前記予想移動時間を示すデータに基づく時間に通過されるシナリオに対して、前記ルーティングポリシを適用することにより、前記出発地から前記目的地までの経路を生成することと、
を含むことを特徴とする方法。
【請求項８】
前記経路は、各区分が前記それぞれの区分の前記予想移動時間に通過されるシナリオに対して前記ルーティングポリシを適用することにより生成されることを特徴とする請求項６又は７に記載の方法。
【請求項９】
前記生成された経路を表示装置上でユーザに対して表示することを含むことを特徴とする請求項６乃至８の何れか１項に記載の方法。
【請求項１０】
前記出発地から前記目的地までの複数の経路を生成することを含み、各経路は、前記生成されてルーティングポリシを異なるシナリオに適用することにより生成され、少なくともいくつかの前記区分の通過の時間はシナリオ間で異なることを特徴とする請求項６乃至９の何れか１項に記載の方法。
【請求項１１】
各区分が前記それぞれの区分の前記予想移動時間に通過されるシナリオに対して、前記ルーティングポリシを適用することにより、第１の経路を生成することと、前記区分の何れも前記それぞれの区分の前記予想移動時間に通過されないか、あるいは、前記区分のいくつかだけが前記それぞれの区分の前記予想移動時間に通過されるシナリオに対して、前記ルーティングポリシを適用することにより、第２の経路を生成することとを含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
複数のルーティングポリシにアクセスすることであって、各ルーティングポリシは、異なる所定の時間予算内に前記目的地に到着する確率を最大化する、前記アクセスすることと、ノードへの到着時間が、前記出発地から前記ノードまでの経路を形成する前記区分の前記予想移動時間の合計であるように、各区分が前記それぞれの区分の前記予想移動時間を示すデータに基づく時間に通過されるシナリオに対して、前記複数のルーティングポリシの各々を適用することにより、前記出発地から前記目的地までの複数の経路を生成することとを含むことを特徴とする請求項６乃至１１の何れか１項に記載の方法。
【請求項１３】
表示装置上でユーザに対して前記生成された複数の経路を、選択的には同時に、表示することを含むことを特徴とする請求項１０乃至１２の何れか１項に記載の方法。
【請求項１４】
前記表示された複数の生成された経路に基づいて前記ユーザから前記複数のルーティングポリシの１つの選択を受け付けることを含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
生成されたルーティングポリシに基づいて前記出発地から前記目的地まで前記ユーザをガイドするナビゲーション命令を出力することを含むことを特徴とする請求項１乃至１４の何れか１項に記載の方法。
【請求項１６】
各区分と関連付けられた区分に沿う予想移動時間を示すデータは、当該それぞれの区分を通過した１以上のユーザから収集された位置データから取得されることを特徴とする請求項１乃至１５の何れか１項に記載の方法。
【請求項１７】
ナビゲート可能ネットワークを通る出発地から目的地までのルーティングポリシを生成するシステムであって、前記ナビゲート可能ネットワークは、前記ナビゲート可能ネットワークのナビゲート可能区分を表す複数の区分を含む電子地図により表され、各区分は当該区分に沿う予想移動時間を示すデータと関連付けられており、前記システムは、
決定論ルーティングアルゴリズムを使用して最短予想移動時間を有する前記出発地から前記目的地までの経路を判定するために前記電子地図のそれぞれの区分の前記予想移動時間を使用する手段と、
前記出発地から時間予算内に前記目的地に到着する確率を最大化するルーティングポリシを生成するために確率論ルーティングアルゴリズムを使用する手段であって、前記時間予算は前記判定された最短予想移動時間に少なくとも基づくものである、前記使用する手段と、
を備えることを特徴とするシステム。
【請求項１８】
ナビゲート可能ネットワークを通る出発地と目的地との間の経路を生成するシステムであって、前記ナビゲート可能ネットワークは、前記ナビゲート可能ネットワークのナビゲート可能区分を表す複数の区分を含む電子地図により表され、各区分はノードにより別の区分と接続されており、各区分は当該区分に沿う予想移動時間を示すデータと関連付けられており、前記システムは、
所定の時間予算内に前記目的地に到着する確率を最大化するルーティングポリシにアクセスする手段と、
ノードへの到着時間が、前記出発地から前記ノードまでの経路を形成する前記区分を移動するための時間の合計であるように、各区分が当該それぞれの区分と関連付けられた前記予想移動時間を示すデータに基づく時間に通過されるシナリオに対して、前記ルーティングポリシを適用することにより、前記出発地から前記目的地までの経路を生成する手段と、
を備えることを特徴とするシステム。
【請求項１９】
前記システムは、ポータブルナビゲーション装置又は車載一体型ナビゲーション装置を含むことを特徴とする請求項１７又は１８に記載のシステム。
【請求項２０】
計算装置の少なくとも１つのプロセッサにより実行される場合に、前記計算装置を請求項１乃至１６の何れか１項に記載の方法に従って動作させる命令を含むコンピュータプログラム。
【請求項２１】
請求項２０に記載のコンピュータプログラムを有する非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルーティングポリシ及び経路を生成する方法及びシステムに関し、経路を生成するナビゲーション装置及びサーバに及ぶ。
【背景技術】
【０００２】
ＧＰＳ（グローバル・ポジショニング・システム）信号受信及び処理機能を含むナビゲーション装置が既知であり、車載ナビゲーションシステムに広く採用されている。通常、ナビゲーション装置は、デジタル地図により表されるナビゲーションネットワーク上の出発地と目的地との間の、最速、最短、最も燃料効率の良い等の“最適な”経路を計算するためにアルゴリズムを使用する。
【０００３】
デジタル地図（又は数学的グラフとしても既知である）は、その最もシンプルな形式では、実際上ノードを表すデータを含むデータベースであり、最も一般的には、道路交差点、及び、当該交差点間の道路を表す当該ノード間の車線を表す。より詳細なデジタル地図では、車線は、開始ノード及び終了ノードにより規定される区分に分割されてもよい。これらのノードは、それらが最少で３つの車線又は区分が交差する道路交差点を表すという点で“リアル”であるかもしれず、また、これらのノードは、数ある中で、道路の特定のストレッチ（ひと続き）の形状情報を提供するためにリアルノードにより一端又は両端で規定されていない区分のアンカとして、あるいは、例えば速度制限等の道路のいくつかの特性が変化する道路に沿った位置を特定する手段、として提供される点で“人工的”であるかもしれない。ノード及び区分はデータベースにおけるデータにより再び表される様々な属性によりさらに規定される。例えば、各ノードは、一般的にその現実世界の位置、例えば緯度及び経度を規定するための地理的座標を有するだろう。ノードは、一般に、交差点において一方の道路から他方の道路へ移動することが可能かどうかを示す、当該ノードと関連付けられた操作データも有するだろうし、区分は、法定速度制限等の関連属性も有するだろう。
【０００４】
最適経路を判定するために使用されるアルゴリズムは、道路又は交通に関する履歴の、既存の、又は予測の情報を考慮してもよい。目的地までの最適経路は、一般に、経路の区分の全てに沿った最低全体コストを有する経路を判定するために、各区分に（固定又は時間依存であってもよい）コストが割り当てられており且つ出発地と目的地との間の様々な可能な経路が探索される決定論ルーティングアルゴリズムを使用して算出される。
【０００５】
正確な、時間依存経路を生成するために、いくつかのルーティングアルゴリズムは、複数の異なる期間でにおける区分に沿った予想移動速度を示すデータを使用し、そのデータは一般的にデジタル地図の関連区分と関連付けられている。このデータは、一般に、過去に区分を移動した複数の車両から収集された位置データ、例えば履歴データから取得されて且つ従って時間依存の平均速度とみなされることができ、従って車両が区分に沿って移動することが期待されるあらゆる時刻での速度を判定するために使用されうる。要素と関連付けられた平均速度は、国際公開第２００９／０５３４１１号に記載された方法に従って判定でき、その全内容が参照により組み込まれる。
【０００６】
ルーティングアルゴリズムは、現在の移動速度又は移動時間を反映して区分の履歴予想移動速度又は移動時間を調整するために、ライブ位置データ等のリアルタイム交通情報を使用してもよく、ひいては、例えば交通量、天気等のナビゲート可能ネットワークの一部分に沿った移動に影響を及ぼす現在のイベントを考慮する。ライブデータは、比較的現在のデータであり且つ各ナビゲート可能な区分における比較的現在のコンディション（条件）の指標を提供するデータとしてみなされてもよい。ライブデータは、一般に最新の３０分、１５分、１０分又は５分内の要素のコンディション（条件）に関するものであってもよい。
【０００７】
しかしながら、ユーザが（例えば、特定の電車に乗るために又は予定のビジネス会議に参加するために）特定の時間までに目的地に到着したい場合のそのような決定論ルーティングアルゴリズムにより生成された経路は、必ずしも理想的ではない。例えば、ユーザは、移動の開始時と比較して最速経路に従う場合に特定の時間までに目的地に到着することを期待するように導かれてもよい。しかしながら、そうした経路には、ユーザを予想時間よりも遅く到着させうる渋滞、事故、道路工事等による列等の、予測不可能な遅延がありがちかもしれない。一般的により遅くてもより移動に要する時間と一致する経路は、要求される時間までに目的地にユーザを到達させる、より高い可能性を有するかもしれない。たとえユーザが特定の時間までに目的地に到着する必要がなくても、もしより遅い経路が全移動時間の変動が少ないなら、平均して速い経路よりも、平均して少々遅い経路をより好むかもしれない。従って、そのような経路を生成できるナビゲーション装置が望まれる。
【０００８】
所定の時間予算内に目的地にと直する確率を最大化するルーティングポリシを生成できる非決定論（確率論）ルーティングアルゴリズムが開発されている。例えば、その内容が参照によりここに組み込まれるＹ．Ｆａｎ及びＹ．ＮｉｅによるＮｅｔｗｏｒｋｓ  ａｎｄ  Ｓｐａｔｉａｌ  Ｅｃｏｎｏｍｉｃｓ，ｖｏｌｕｍｅ  ６：３−４，ｐｐ．３３３ − ３４４，Ｓｐｒｉｎｇｅｒ ２００６のジャーナル記事“移動時間の信頼性を最大化する最適ルーティング（Ｏｐｔｉｍａｌ  Ｒｏｕｔｉｎｇ  ｆｏｒ  Ｍａｘｉｍｉｚｉｎｇ  ｔｈｅ  Ｔｒａｖｅｌ  Ｔｉｍｅ  Ｒｅｌｉａｂｉｌｉｔｙ”は、そのようなルーティングポリシを生成できる"確率論的時間通りの到着（Ｓｔｏｃｈａｓｔｉｃ Ｏｎ−Ｔｉｍｅ Ａｒｒｉｖａｌ （ＳＯＴＡ））アルゴリズムを記載する。それぞれの道路区分について単純なコスト値を使用するのではなく、そのアルゴリズムは、それぞれの道路区分について確率密度関数又は確率質量関数を使用する。これらの関数は、区分について可能性のある移動時間の集合に確率を割り当てる。
【０００９】
そのようなアルゴリズムにより生成されたルーティングポリシは、単一の経路ではなく、非線形方程式の集合により規定される。そのようなルーティングポリシに基づく移動のパスは、移動者が各特定のノードへ到達するのにかかる実際の時間に基づいて変化するだろう（それは目的地に到達するまで所定の時間予算からどの程度多くの時間が残っているか判定（決定）する）。それ故、式は、出発地から目的地まで移動するための動的ルーティングストラテジを提供し、それは、移動するにつれて経路を適合させるためにノード間を移動するのにかかる実際の時間を考慮する。目的地までナビゲートするためのルーティングポリシを使用する場合、交差点でどのパスを取るかに関する決定は（決定論アルゴリズムと同様に）事前に判定されていないが、時間予算内に目的地に到着する確率を最大化するように、残りの時間予算に基づいて、ユーザが交差点に到着すると行われる。従って、ユーザが移動の第１の行程（ファーストレグ）を予想よりも早く移動したら、第２の行程（セカンドレグ）について、もしかするとより遅いが、より信頼性の高い経路を取るように指示されてもよい。逆に、ユーザが移動の第１の行程を期待よりも遅く移動したら、第２の行程について、より速いがよりリスクのある経路を取るように指示されてもよい。
【００１０】
完全性のために、ＳＯＴＡモデルは以下の方法に要約できる。有向ネットワークＧ（Ｎ，Ａ）を考慮する。ここで、｜Ｎ｜＝ｎノード、｜Ａ｜＝ｍリンクである。各リンク（ｉ，ｊ）∈Ａの重みは、リンク（ｉ，ｊ）上の移動時間を表す確率密度関数ｐｉｊ（・）を有する確率変数である。時間予算Ｔが与えられると、最適ルーティングストラテジが、時間Ｔ内に目的地ノードｓに到着する確率を最大化するポリシであるように規定される。ルーティングポリシは、ネットワーク内の各ノードにおける最適パスを、その地点に対して認識された移動時間に基づいて判定する適応ソリューション（adaptive solution）である。これは、出発前に全体パスを判定する演繹ソリューション（a-priori solution）とは対照的である。ノードｉ∈Ｎ、時間予算ｔが与えられると、ｕｉ（ｔ）は、最適ポリシに従う場合に時間ｔよりも少なくノードｉからノードｓへ到着する確率を示す。各ノードｉにおいて、移動者は、目的地に時間通りに到着する確率を最大化するリンク（ｉ，ｊ）を選ぶべきである。もしｊがノードｉの後に訪問されている次のノードであり、ωがリンク（ｉ，ｊ）で費やされる時間であるなら、時間予算ｔ内にノードｉから開始する移動者は、以下の式に記載されるように、ｊから目的地へ移動するのにｔ−ωの時間予算を有し、
【００１１】
【数１】
2018510335.tif 000003
【００１２】
【数２】
2018510335.tif 000004
【００１３】
ｐｉｊ（・）はリンク（ｉ，ｊ）における移動時間分布である。関数ｐｉｊ（・）は、例えば平均移動時間を判定することに関連して上述したように、例えば履歴及び／又はライブの位置データを使用して取得される。関数ｐｉｊ（・）は時間に依存しうるものであり、例えばＴｒａｎｓｐｏｒｔａｔｉｏｎ  Ｒｅｓｅａｒｃｈ  Ｐａｒｔ  Ｃ：  Ｅｍｅｒｇｉｎｇ  Ｔｅｃｈｎｏｌｏｇｉｅｓ, ｖｏｌｕｍｅ ２０：１, ｐｐ. １９９−２１７, Ｐｅｒｇａｍｏｎ ２０１２でのＳａｍａｒａｎａｙａｋｅ等による"Ａ  ｔｒａｃｔａｂｌｅ  ｃｌａｓｓ  ｏｆ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｒｅｌｉａｂｌｅ  ｒｏｕｔｉｎｇ  ｉｎ  ｓｔｏｃｈａｓｔｉｃ  ｎｅｔｗｏｒｋｓ"、その内容が参照によりここに組み込まれる、に記載のように、リンク間の空間的及び／又は時間的な相関も含みうる。
【００１４】
そのようなルーティングポリシの生成が理論的なレベルで研究されているが、この理論がどのようにしてユーザフレンドリーなナビゲーション装置で効果的に活用されうるのかは自明ではない。
【発明の概要】
【００１５】
本発明の第１の態様によれば、ナビゲート可能ネットワークを通る出発地から目的地までのルーティングポリシを生成する方法であって、前記ナビゲート可能ネットワークは、前記ナビゲート可能ネットワークのナビゲート可能区分を表す複数の区分を含む電子地図により表され、各区分は当該区分に沿う予想移動時間を示すデータと関連付けられており、前記方法は、
決定論ルーティングアルゴリズムを使用して最短予想移動時間を有する前記出発地から前記目的地までの経路を判定するために前記電子地図のそれぞれの区分の前記予想移動時間を使用することと、
前記出発地から時間予算内に前記目的地に到着する確率を最大化するルーティングポリシを生成するために確率論ルーティングアルゴリズムを使用することであって、前記時間予算は前記判定された最短予想移動時間に少なくとも基づくものである、前記使用することと、
を含む方法が提供される。
【００１６】
本発明の方法のステップはその態様又は実施形態の何れかにおいて、部分的にサーバにより且つ部分的にナビゲーション装置又はデバイスにより実行されてもよい。本発明の方法は、排他的にサーバ上で実行されてもよく、あるいは、いくつかがサーバ上でその他がナビゲーション装置又はデバイス上で任意の組み合わせで実行されてもよく、あるいは、排他的にナビゲーション装置又はデバイス上で実行されてもよい。従って、本発明のシステムは、以下で議論されるその更なる態様において部分的にナビゲーションデバイス又は他のモバイルデバイスにより、及び、部分的にサーバにより提供されてもよい。
【００１７】
本発明は、ここに記載される本発明の任意の態様又は実施形態に従った方法を実行するシステムにも及ぶ。
【００１８】
本発明の別の態様によれば、ナビゲート可能ネットワークを通る出発地から目的地までのルーティングポリシを生成するシステムであって、前記ナビゲート可能ネットワークは、前記ナビゲート可能ネットワークのナビゲート可能区分を表す複数の区分を含む電子地図により表され、各区分は当該区分に沿う予想移動時間を示すデータと関連付けられており、前記システムは、
決定論ルーティングアルゴリズムを使用して最短予想移動時間を有する前記出発地から前記目的地までの経路を判定するために前記電子地図のそれぞれの区分の前記予想移動時間を使用する手段と、
前記出発地から時間予算内に前記目的地に到着する確率を最大化するルーティングポリシを生成するために確率論ルーティングアルゴリズムを使用する手段であって、前記時間予算は前記判定された最短予想移動時間に少なくとも基づくものである、前記使用する手段と、
を備えるシステムが提供される。
【００１９】
当業者に理解されるように、本発明のこの更なる態様は、必要に応じて、本発明の他の態様の何れかに関してここで記載される本発明の好適且つ最適な特徴の何れか１つ以上又は全てを含むことができ、好適には含む。明示的に述べられていなくても、ここでの本発明のシステムは、本発明の態様又は実施形態の何れかにおける本発明の方法に関連して記載された任意のステップを実行する手段を備えてもよく、その逆もまた同じである。
【００２０】
従って、当業者は、本発明のこれらの態様に従って、ルーティングポリシのための時間予算が最短予想移動時間に基づいて設定されることが分かるだろう。上述したように、前記ルーティングポリシは、前記時間予算内に前記目的地に到着する前記確率が最大化されるように、前記出発地から前記電子地図のノードに到達するのにかかる移動時間に基づいて前記ノードで取る次の区分を判定する非線形方程式の集合に対するソリューションである。実施形態において、前記時間予算は、スケーリング因子を乗算された前記最短の予想移動時間と同じでありうる。理解されるように、前記時間予算と前記最短予想移動時間との間の依存関係は、所望の任意の他の形式でありうる。前記スケーリング因子は、必要に応じて時間予算を調整するために使用されうるが、前記最短予想移動時間への依存を維持する。前記スケーリング因子は、前記時間予算が前記最短予想移動時間よりも常に大きくなるように、通常１よりも大きいだろう。他の実施形態において、前記スケーリング因子は１と等しくてもよいが、その場合、前記時間予算は単純に前記最短予想移動時間と等しい。前記スケーリング因子が小さい（例えば１に近い）場合、前記ルーティングポリシは、最速の可能性が高いが、非常に可変的な期間を有するかもしれない経路に沿ってユーザを導くだろう。これは、平均して速いことが予想される経路に固執する場合にはタイトな時間予算のみが保持されうるからである。前記スケーリング因子がより大きい場合、前記ユーザは、より遅いが、より多くの任意の到着時間を有する経路に沿って導かれる可能性が高い。
【００２１】
このようにして時間予算を規定することは、ユーザが時間予算を決定することを求めなければないないことを回避する。これは少なくとも２つの理由で望ましい。１つ目は、ユーザが目的地（この可能性は排除できないが）を超えた任意の情報を入力することを余儀なくさせることなく経路が判定可能であることである。２つ目は、到達するには短すぎるかもしれない、又は、不必要に長い（それ故ユーザの時間及び／又は燃料の無駄となる）かもしれない、不適切な時間予算が選択されることを回避することである。
【００２２】
スケーリング因子はユーザにより設定されてもよい。いくつかの実施形態では、スケーリング因子の値を判定してもよい数値入力がユーザから受け付けられてもよい。しかしながら、好適な実施形態では、スケーリング因子が取得される質的入力がユーザから受け付けられる。例えば、ユーザは、入力位置の所定の関数に従ってスケーリング因子の値を判定してもよい一次元入力機構、タッチスクリーンインタフェース上のグラフィカルスライダ、と対話してもよい。一次元入力の第１の端部は、１と同等のあるいは近いスケーリング因子と一致してもよい。一次元入力の第２の端部は、（実験的に判定されてもよい）スケーリング因子の所定の最大値と一致してもよい。一次元入力の２つの端部間の位置では、それら端部での値の間の線形スケールに従って、あるいは、任意の他の適当な関数に従って、スケーリング因子を判定してもよい。
【００２３】
スケーリング因子は代わりに予め定められてもよい（すなわちユーザにより直接設定されない）。適切なスケーリング因子は実験的に判定されてもよい。例えば、スケーリング因子の種々の値を使用してルーティングシミュレーションを行い、どの値が、（例えば経路の少なくとも５０％上で）十分に最速経路から逸脱するものの予想移動時間の許容不可能な増加（例えば１０％超）には至らないルーティングポリシを生むのかを判定することによって判定されてもよい。
【００２４】
所望の時間予算、好適にはスケーリング因子は、例えば１以上の所定の関係又は関数に従って、時間又は天気等の環境因子に依存して、あるいは、経路又はナビゲート可能ネットワークの特性に依存して変化してもよい。例えば、所望の時間予算は、好適にはスケーリング因子は、ユーザ入力（例えば上述したような）；日時；曜日；出発地及び／又は目的地及び／又は出発地と目的地との間のナビゲート可能ネットワークの一部又は全部についての型分類（例えば“都会”又は“田舎”）；及び出発地と目的地との間の距離から成るセットから選択された１以上の因子に依存してもよい。
【００２５】
いくつかの実施形態では、スケーリング因子は、（ｉ）量的又は質的なユーザ入力、及び（ｉｉ）（例えば前のパラグラフで記載したように）ユーザにより直接設定されていない値、の２つの入力の関数であってもよい。スケーリング因子は、例えば、ユーザにより判定された値と、意図された移動の時間又は特性等の因子に基づく値との積と等しくてもよい。
【００２６】
いくつかの例では、スケーリング因子は１よりも小さいかもしれないが、好適には、時間予算内に移動者が到着するチャンスをより大きくするので、スケーリング因子は１以上である。
【００２７】
時間予算が、スケーリング因子により乗算された、最短予測移動時間と実質的に等しい（例えばそのプラスマイナス５％又は１０％以内）実施形態に本発明が及ぶことが理解されるだろう。
【００２８】
確率論的アルゴリズムは、上述したようなＳＯＴＡアルゴリズムであってもよく、あるいは、出発地を出てから時間予算内に目的地に到着する確率を最大化するルーティングポリシを生成できる任意の他のアルゴリズムであってもよい。アルゴリズムは、好適にはそれぞれの区分に沿う移動時間の確率分布を使用する。これらの確率分布は、時間、例えば日時、曜日等に依存してもよい。確率分布は、空間的／時間的な区分間の相関の使用を通じてより複雑に作られることもでき、たとえば、（ｉ）確率分布は、例えば交通信号での待ち時間、複雑な操縦の実行を考慮するために、該当区分に入るために使用された前の区分に依存して異なってもよく、（ｉｉ）確率分布は、ある区分でのある時間における交通条件に依存して異なってもよく、例えば、時間ｘにおいて道路Ａ上の交通流れが通常ゆっくりである場合、時間ｘ＋ｙにおける道路Ｂ上の交通流れがゆっくりである確率が増加する。
【００２９】
電子地図の区分の予想移動時間は、履歴データから取得されてもよい。いくつかの実施形態では、それらは、ルーティングポリシを生成するために使用された確率分布データから別々に生成及び／又は格納されてもよい（例えば各区分の確率密度関数又は確率質量関数）。それらは、例えば、正規化された区分速度プロファイルの限定セットに基づくものであってもよい（例えば１６個の正規化プロファイル、ここで、電子地図におけるあらゆる道路区分にはそれらプロファイルの１つが割り当てられる）。予想移動時間におけるあらゆる時間依存性の粒度（例えば週に渡る５分間隔ごとの値）は、確率分布の粒度と異なってもよい。しかしながら、いくつかの実施形態では、予想移動時間は、ルーティングポリシを生成するために使用された確率分布データと数学的に関連してもよく、あるいはそれから取得されてもよい。１つのセットの実施形態では、各区分は関連する確率密度関数ｆ（ｘ）を有しており、その区分の予想移動時間は、全てのｘに渡ったｘ．ｆ（ｘ）の積分値と等しい。別のセットの実施形態では、各区分は関連する確率質量関数ｆ（ｘ）を有しており、その区分の予想移動時間は、全てのｘに渡ったｘ．ｆ（ｘ）の合計値と等しい。方法は、確率密度データから電子地図の少なくともいくつかの区分の予想移動時間を算出するステップを含んでもよい。
【００３０】
最短予想移動時間を有する経路（すなわち最速経路）は、ダイクストラ（Dijkstra）アルゴリズムに基づくもの等の、任意の適切な決定論アルゴリズムを使用して判定されてもよい。
【００３１】
生成されたルーティングポリシは、好適には、ナビゲート可能ネットワークを通るユーザの移動に関するデータ（例えば、ナビゲーション衛星システム、例えばＧＰＳ等の、ユーザと関連付けられた測位装置から判定されるようなタイムスタンプ位置データ）に基づいて、出発地から目的地までユーザをガイドする方向を生成するために使用される。
【００３２】
そのようなアプローチは、ユーザは出発地を出る前に目的地までの推奨経路の詳細を受信することに慣れているが、進む経路は、予め既知ではない、実際の移動時間に基づいて、移動進捗としてのみ固定されるので、ルーティングポリシを使用する場合はそうした経路が存在しないという点で、欠点がある。経路が算出されているナビゲーション装置からの任意の指標無しに移動に乗り出すことはユーザにとって不安をかきたてるかもしれない。
【００３３】
従って、本発明の更なる態様に従って、ナビゲート可能ネットワークを通る出発地と目的地との間の経路を生成する方法であって、前記ナビゲート可能ネットワークは、前記ナビゲート可能ネットワークのナビゲート可能区分を表す複数の区分を含む電子地図により表され、各区分はノードにより別の区分と接続されており、各区分は当該区分に沿う予想移動時間を示すデータと関連付けられており、前記方法は、
所定の時間予算内に前記目的地に到着する確率を最大化するルーティングポリシにアクセスすることと、
ノードへの前記到着時間が、前記出発地から前記ノードまでの経路を形成する前記区分の前記予想移動時間の合計であるように、各区分が前記それぞれの区分の前記予想移動時間を示すデータに基づく時間に通過されるシナリオに対して、前記ルーティングポリシを適用することにより、前記出発地から前記目的地までの経路を生成することと、
を含む方法が提供される。
【００３４】
本発明は、ここで記載した本発明の態様又は実施形態の何れかに従った方法を実行するシステムに及ぶ。
【００３５】
それ故、本発明の別の態様に従って、ナビゲート可能ネットワークを通る出発地と目的地との間の経路を生成するシステムであって、前記ナビゲート可能ネットワークは、前記ナビゲート可能ネットワークのナビゲート可能区分を表す複数の区分を含む電子地図により表され、各区分はノードにより別の区分と接続されており、各区分は当該区分に沿う予想移動時間を示すデータと関連付けられており、前記システムは、
所定の時間予算内に前記目的地に到着する確率を最大化するルーティングポリシにアクセスする手段と、
ノードへの前記到着時間が、前記出発地から前記ノードまでの経路を形成する前記区分を移動するための時間の合計であるように、各区分が前記それぞれの区分と関連付けられた前記予想移動時間を示すデータに基づく時間に通過されるシナリオに対して、前記ルーティングポリシを適用することにより、前記出発地から前記目的地までの経路を生成する手段と、
を備えるシステムが提供される。
【００３６】
当業者に理解されるように、この本発明の更なる態様は、必要に応じて、本発明の他の何れかの態様に関してここで記載した本発明の好適且つ最適な特徴の１つ以上又は全ての何れかを含むことができ、好適には含む。明示的に述べられていなくても、ここでの本発明のシステムは、本発明の態様又は実施形態の何れかにおいて本発明の方法に関連して記載された任意のステップを実行する手段を備えてもよく、その逆もまた同じである。
【００３７】
従って、当業者により、本発明のこれらの態様に従って、出発地から出発する前に、例えばユーザへの表示のために経路がルーティングポリシから抽出されうることが分かるだろう。これは、各区分と関連付けられた予想移動時間に基づく時間に各区分が移動される状況（シチュエーション）にルーティングポリシを適用することにより達成される。例えば、実施形態において、ルーティングポリシは、それぞれの区分と関連付けられた予想移動時間に各区分が移動される状況に適用される。抽出された経路は、必ずしも特定の場合に実際に移動されるだろう経路ではないが、最も可能性の高い経路の中の１つの良好な指標を提供し、それ故、推奨経路又は指示経路としてユーザに表示されうる。
【００３８】
経路に関する情報（例えば、地図上のパス、又は、方向のセット）は好適にはユーザに表示される。ユーザは好適にはルーティングポリシに従って（単純に生成された経路に従うのではなく）目的地へガイドされる。
【００３９】
区分の予想移動時間は、例えば上述したような履歴データ及び／又はライブデータから取得されてもよい。いくつかの実施形態では、それらは、ルーティングポリシが基づいている確率分布データとは別に生成及び／又は格納されてもよい。それらは、例えば、正規化された区分速度プロファイルの限定セットに基づくものであってもよい（例えば１６個の正規化プロファイル、ここで、電子地図におけるあらゆる道路区分にはそれらプロファイルの１つが割り当てられる）。それらは時間に依存してもよく、その場合、特定の出発時間についてシナリオが提供され、予想移動時間は、様々な各区分がそのシナリオ化で通過される予想時間と一致するように選択されてもよい。予想移動時間におけるあらゆる時間依存性の粒度（例えば週に渡る５分間隔ごとの値）は、ルーティングポリシの確率分布の粒度と異なってもよい。しかしながら、いくつかの実施形態では、予想移動時間は、例えば上述した方法の１つにおいて、ルーティングポリシを生成するために使用された確率分布データと数学的に関連してもよく、あるいはそれから取得されてもよい。
【００４０】
予想移動時間は、ユーザ、例えば車両が、ナビゲート可能ネットワークの区分を移動する平均移動時間又はモード（最頻値）移動時間であってもよい。
【００４１】
区分に沿う予想移動時間を示すデータは予想移動時間を含んでもよく、あるいは、区分の長さに基づく区分の予想移動時間に変換できる予想速度を含んでもよい。各区分と関連付けられたデータは電子地図に格納されてもよく、あるいは、当該データは、電子地図とは別に、例えばナビゲート可能ネットワークのライブ条件に基づくデータで動的に更新されうるサイドファイルに格納されてもよい。
【００４２】
ルーティングポリシはシステムの外で生成されてもよいが、好適には当該システムにより生成される。ルーティングポリシにアクセスすることは、メモリから、ルーティングポリシを表す、又は、それに関するデータにアクセスすることを含んでもよい。それは、いくつかの実施形態では、本発明の前の態様を参照して上述したように生成されてもよい。より一般的には、前の態様又は実施形態の何れかの任意の特徴は、本態様の実施形態の特徴であってもよい。
【００４３】
いくつかの実施形態では、複数のルーティングポリシがアクセス又は生成されてもよく、その各々は異なるそれぞれの時間予算内に目的地に到着する確率を最大化する。それぞれの複数の経路は、各区分と関連付けられた予想移動時間を示すデータに基づく時間に各区分が通過されるシナリオに各ルーティングポリシを適用することによって、ルーティングポリシから生成されてもよい。これら抽出された経路は、出発地から目的地までの代替経路のセットとしてユーザに提示されてもよい。発明者は、運転手が特定の経路の代替を望む場合には、しばしば（意識的に又は非意識的に）より信頼できる経路を探すかもしれないことを認識している。異なる時間予算に基づいてユーザに２つ以上の経路を提示することによって、ユーザは速度と信頼性との所望のバランスを与える経路を選択可能である。そのような実施形態では、ユーザは、選択された経路が生成されたルーティングポリシに従うようにガイドされてもよい。
【００４４】
異なるそれぞれの時間予算は、上述したように、異なるそれぞれのスケーリング因子を共通の最短移動時間に適用することによって設定されてもよい。これら異なるスケーリング因子は、スケーリング因子の所定のセット（例えば５つか６つのスケーリング因子の固定セット）であってもよく、あるいは、それらの値は、日時；曜日；出発地及び／又は目的地及び／又は出発地と目的地との間のナビゲート可能ネットワークの一部又は全部についての型分類（例えば“都会”又は“田舎”）；及び出発地と目的地との間の距離から成るセットから選択された１つ以上の因子に依存してもよい。
【００４５】
好適には、ルーティングポリシは、異なる時間予算のセットのうち最大のものについて最初に生成される。これは、多くのＳＯＴＡアルゴリズムについて、所与の時間予算を有する、所与の出発地及び目的地に対するルーティングポリシは、本質的に、同じ出発地及び目的地についてより少ない時間予算を有する全てのルーティングポリシを含むので利点がある。従って、異なる時間予算を有する、いくつかの代替が望まれる場合であっても、単一のＳＯＴＡ計算を行うことが可能であり、それにより必要な計算量を低減することができる。
【００４６】
いくつかの実施形態では、単一のルーティングポリシがアクセス及び生成されてもよく、区分と関連付けられた予想移動時間を示すデータに基づく複数のシナリオにルーティングポリシを適用することによって出発地から目的地までの複数の経路が生成されてもよい。従って、いくつかの実施形態では、経路の全てに沿う各区分が各区分の予想移動時間に通過されるシナリオにルーティングポリシを適用することによって、ただ単一の経路が生成される。しかしながら、他の実施形態では、ルーティングポリシを異なるシナリオに適用することによって単一のルーティングポリシから２つ以上の経路が生成されてもよい。例えば、第１の経路が、区分が当該区分の予想移動時間に通過されるシナリオを使用してルーティングポリシから抽出されてもよい。次に、第２の経路が、経路に沿う区分の何れも各区分の予想移動時間に通過されないか、経路に沿う区分のいくつかのみ、全てではない、が各区分の予想移動時間に通過されるシナリオを使用して抽出されてもよい。経路に沿う他の区分は予想移動時間以外の時間に通過されてもよい。例えば、調整された予想移動時間が、出発地からの第１の抽出経路の所定の部分を形成する区分に関して使用されてもよい（例えば第１の抽出経路の最初の２０％）。調整された予想移動時間は、ユーザ、例えば車両が、ナビゲート可能ネットワークの区分を移動する移動時間の異なるパーセンタイルを含んでもよい。例えば、区分の予想移動時間が平均と比較して増大されるように３０番目のパーセンタイルが使用されてもよい。あるいは、区分の予想移動時間が平均と比較して減少されるように７０番目のパーセンタイルが使用されてもよい。理解されるように、所望に任意の他のパーセンタイル値が使用されてもよい。他の実施形態では、異なるパーセンタイル値を使用するというよりはむしろ、分布の最も速いｎ％及び／又は最も遅いｍ％が無視されてもよく（ｎ及びｍという任意の適当な値）、平均、最頻値又は他のパーセンタイル値が、調整された予想移動時間を判定するために再計算される。一例ではｎ及びｍは５％であってもよいが、所望に任意の値が使用されうることが理解されるだろう。より多くの代替が望まれる場合、結果として生じる代替に関して処理が繰り返されてもよく、第２の抽出経路の区分の少なくともいくつか、可能であれば全部について異なる予想移動時間を想定する。前の通り、そのような複数の経路は、出発地から目的地までの代替経路のセットとしてユーザに提示されてもよい。
【００４７】
いくつかの実施形態では、代替経路を生成するためのこれら２つの異なるアプローチは、その少なくとも１つ（及び潜在的には全て）が複数の経路を生成するために使用される複数のルーティングポリシから代替経路のセットを生成するように、（多数のルーティングポリシに基づいて、及び、単一のルーティングポリシから多数の経路を抽出することに基づいて）組み合わされてもよい。
【００４８】
一般に、ここでの確率分布への言及は、確率密度関数、又は確率質量関数、又は任意の他の適当な分布を含んでもよい。そうした確率分布は、測定データから（例えば、道路ネットワークの周囲の車両の移動を追跡することから）生成されてもよい。それは概算値又は推定値であってもよい。それは、速度、又は移動時間、又は任意の他の適当な値の観点で表現されてもよい。それは、確率分布が複数の所定の期間の各々について（例えば日又は週の５分間隔ごとに）判定されるように、時間に依存してもよい。確率分布は、区分間の空間的及び／又は時間的な相関を表してもよい。例えば、区分の確率分布は、どの前の区分が該当区分に入るために使用されたかに依存して異なってもよい。このように、それは、交通信号での待ち時間、又は複雑な操縦の実行等を考慮してもよい。別の例として、区分の確率分布は、１つ以上の他の区分上での１つ以上の時間における条件に依存して異なってもよく、例えば、時間ｘにおいて道路Ａ上の交通流れが通常ゆっくりである場合、時間ｘ＋ｙにおける道路Ｂ上の交通流れがゆっくりである確率が増加する、等の効果を得る。
【００４９】
確率分布及び／又はルーティングポリシ及び／又は予想移動時間情報は任意の適当なフォーマットで格納されてもよく、１つ以上のストレージ媒体に配信されてもよい。それは、単純化された、あるいは圧縮された、あるいは数学的に同等なフォーマットで格納されてもよい。
【００５０】
一般に、本発明のシステムはその実施形態の何れかにおいて少なくとも１つの処理装置であってもよく、あるいはそれを含んでもよい。そのような処理装置は、ポータブルナビゲーション装置（ＰＮＤ）又は一体型装置であろうとなかろうと、ナビゲーション装置等のモバイル装置の構成要素であってもよく、あるいはサーバの構成要素であってもよい。
【００５１】
本発明の方法は、好適にはナビゲーション動作との関連で実施される。従って、方法は、好適にはナビゲーション機能を有する装置又はシステムの１つ以上のプロセッサのセットにより実行される。  しかしながら、方法は、必ずしもナビゲーション機能ではなく、経路生成能力を有する任意の適当なシステムにより実行されてもよいことが理解されるだろう。例えば、方法は、ナビゲーション機能を有しない（例えば自身の位置を判定しない）、例えばデスクトップシステム又はラップトップシステム等のコンピュータシステムにより実施されてもよい。
【００５２】
好適な実施形態において、本発明の態様又は実施形態のうちいずれかにおける本発明の方法は、ナビゲーション装置を使用して実行され、本発明は、本発明の態様又は実施形態のうちいずれかの方法のステップを実行するように構成されるナビゲーション装置に拡張される。ナビゲーション装置は、ＰＮＤ又は一体型装置、例えば車載型装置であってもよい。
【００５３】
本発明の態様又は実施形態のいずれかによれば、ナビゲーション装置は、使用者に電子地図を表示するディスプレイを備えてもよい。ナビゲーション装置は、電子地図データにアクセスし、ディスプレイを介して使用者に対して電子地図を表示させるように構成された１つ以上のプロセッサの集合を備えてもよい。ナビゲーション装置は、使用者が装置と対話することを可能にするために使用者により操作可能なユーザインタフェースとを備えてもよい。従って、本発明のシステムは、ナビゲーション装置のシステム、例えば処理装置であってもよい。
【００５４】
他の実施形態において、本発明の態様又は実施形態のうちいずれかにおける本発明の方法はサーバにより実行されてもよく、本発明は本発明の態様又は実施形態のうちいずれかの方法のステップを実行するように構成される１以上のサーバに拡張される。本発明の態様又は実施形態のうちいずれかにおける本発明のシステムは、サーバのシステム、例えば処理装置であってもよい。
【００５５】
本発明の態様又は実施形態のうちいずれかにおける本発明の方法のステップは当然のことながら一部はサーバにより実行され、一部はナビゲーション装置により実行されてもよい。例えば、経路生成又はルーティングポリシ生成は、例えばナビゲーション装置の要求に応じてサーバにより実行されてもよく、当該生成の出力が前記装置に提供されてもよく、ユーザに経路を提供するため又はユーザをガイドするためにそれを使用してもよい。方法のステップはサーバでのみ実行されてもよいが、何らかの組み合わせで一部のステップはサーバで実行され、その他のステップはナビゲーション装置で実行されてもよい。サーバにおける１つ以上のステップの実行は効率がよく、ナビゲーション装置に課される計算負荷を低減させるだろう。あるいは１つ以上のステップがナビゲーション装置で実行される場合、これはネットワーク通信のために要求されるあらゆる帯域幅を減少させる恐れがある。従って、本発明のシステムは一部をナビゲーション装置又は他の移動装置により提供され、一部をサーバにより提供されてもよい。
【００５６】
出発地及び目的地は任意に適当な方法で取得されてもよい。例えば、出発地及び／又は目的地はユーザにより特定されてもよい。あるいは、出発地はユーザの現在地であってもよい。他の構成では、出発地及び／又は目的地は、ユーザのパス、又は以前に移動した経路等から推論されてもよい。
【００５７】
好適には、本発明の方法は、生成されたルーティングポリシ又は生成された経路を表す、又は示すデータを格納するステップに及ぶ。
【００５８】
１つ以上の生成された経路を示すデータが出力されてもよい。例えば、１つ以上の生成された経路はユーザに対して表示されてもよい。実施形態では、複数の経路、すなわち代替経路が（単一のルーティングポリシから、あるいは、複数のルーティングポリシから）生成される場合、複数の生成された経路がユーザに対して同時に表示されてもよい。そのようなステップは、ナビゲーション機能を有してもよく、あるいは、有していなくてもよい任意の適当な装置により実行されてもよい。いくつかの実施形態では、装置は、ＰＮＤ又は一体型ナビゲーション装置等のナビゲーション装置である。ナビゲーション装置は車両と関連付けられてもよい。
【００５９】
本発明の方法は、ナビゲーション命令のセットを生成し、選択的に、生成された又は選択されたルーティングポリシに基づいて前記命令を出力するステップを含んでもよい。実施形態では、複数のルーティングポリシから複数の代替経路が生成される場合、ユーザはルーティングポリシの１つの選択を行ってもよく、前記選択されたルーティングポリシを使用して、ナビゲーション命令のセットが生成されて選択的に出力される。ルーティングポリシの選択は、表示されている複数の代替経路に基づいてなされてもよい。
【００６０】
１つ以上の区分に関して、“関連付けられた（associated with）”及び“のための（for）”というフレーズは、データストレージ位置に何らかの特定の制限を要するものと解釈されるべきではないことが留意されるべきである。そのフレーズは特徴が区分と識別可能に関連していることだけを要求する。それ故、関連付けは、例えば、遠隔サーバに潜在的に位置する、サイドファイルへの参照によって達成されてもよい。
【００６１】
ここで使用される用語“区分”は当該技術における通常の意味を持つ。区分は、２つのノードを接続するナビゲート可能なリンク又はその任意の部分であってもよい。本発明のいくつかの実施形態は道路区分に関連して説明されるが、歩道、河川、運河、自転車道路、航路又は鉄道線路などの区分のような他のナビゲート可能区分にも本発明を適用可能であってもよいことを理解すべきである。参照を容易にするために、これらは一般に道路区分として表されるが、“道路区分”へのあらゆる参照は、“ナビゲート可能区分”又はあらゆる特定の種類のそのような区分への参照により置き換えられてもよい。
【００６２】
本発明に係る方法のいずれかは、少なくとも部分的にソフトウェア、例えばコンピュータプログラムを使用して実現されてもよい。従って、本発明は本発明の態様又は実施形態のうちいずれかに係る方法を実行するために、あるいは、ナビゲーション装置及び／又はサーバに実行させるために、実行可能なコンピュータ可読命令を備えるコンピュータプログラムに更に拡張される。
【００６３】
本発明はデータ処理手段を備えるシステム又は装置を動作させるために使用される場合に、前記装置又はシステムに本発明の方法のステップを実行させるようなソフトウェアを含むコンピュータソフトウェアキャリアに拡張される。そのようなコンピュータソフトウェアキャリアは、ＲＯＭチップ、不揮発性メモリチップ、ＣＤ−ＲＯＭ又はディスクなどの非一時的物理格納媒体であることが可能であるか、あるいは回線を介する電子信号、光信号又は衛星などへの無線信号のような信号であることが可能だろう。
【００６４】
その実施に関わらず、本発明の任意の態様又は実施形態に従って使用される装置、例えばナビゲーション装置は、プロセッサ、メモリ、及び当該メモリに格納されたデジタル地図データ（又は電子地図）を備えてもよい。プロセッサ及びメモリは、ソフトウェアオペレーティングシステムが構築されてもよい実行環境を協同して提供する。１つ以上の追加のソフトウェアプログラムが、装置の機能性を制御可能にするために、あるいは様々な他の機能を提供するために提供されてもよい。本発明のナビゲーション装置は、好適にはグローバル・ナビゲーション衛星システム（ＧＮＳＳ）、例えばＧＰＳ又はＧＬＯＮＡＳＳ、信号受信処理機能を含んでもよい。理解されるように、ナビゲーション装置は、所望の現在位置を判定する他の手段、例えば地上波ビーコン、移動体通信ネットワーク等を使用してもよい装置は、情報がユーザに中継されてもよい１つ以上の出力インタフェースを備えてもよい。出力インタフェースは、視覚ディスプレイに加えて可聴出力のためのスピーカを含んでもよい。装置は、ＯＮ／ＯＦＦ動作又は装置の他の特徴を制御するための１つ以上の物理ボタンを含む入力インタフェースを備えてもよい。
【００６５】
他の実施形態では、ナビゲーション装置は、特定のナビゲーション装置の一部を形成しない処理装置のアプリケーションによって少なくとも一部が実施されてもよい。例えば、本発明はナビゲーションソフトウェアを実行するように構成された適当なコンピュータシステムを使用して実施されてもよい。システムは、モバイル又はポータブルのコンピュータシステム、例えば携帯電話又はラップトップであってもよいし、あるいは、デスクトップシステムであってもよい。
【００６６】
ここで記載される態様又は実施形態の特徴は、適切な場合には、ここで記載される任意の他の態様又は実施形態に適用されてもよい。それとは逆に、明示的に述べられていなくても、本発明を具体化するシステムは、本発明の任意の態様又は実施形態の方法に関して記載された任意のステップを実行する手段を備えてもよく、その逆もまた同様である。異なる実施形態又は実施形態のセットへの言及がなされる場合、これらは必ずしも別個である必要はなく、重複してもよいことが理解されるべきである。
【００６７】
以下に、それらの実施形態の利点が記載され、それらの実施形態の各々の更なる詳細及び特徴は、添付の従属特許請求の範囲及び以下の詳細な説明のいずれかの箇所で定義される。
【図面の簡単な説明】
【００６８】
添付の図面を参照して、例として本発明の任意の好適な実施形態を以下に説明する。
【図１】図１は、ナビゲーション装置により使用可能な全地球測位システム（ＧＰＳ）の例示的な一部分を概略的に示す図である。
【図２】図２は、ナビゲーション装置とサーバとの間の通信のための通信システムを示す概略図である。
【図３】図３は、図２のナビゲーション装置又は他の何らかの適切なナビゲーション装置の電子構成要素を示す概略図である。
【図４】図４は、ナビゲーション装置を取り付け且つ／又はドッキングする構成を示す概略図である。
【図５】図５は、ルーティングポリシを生成する方法のステップを概略化したフローチャートである。
【図６】図６は、ユーザがディスプレイと対話する概略図である。
【図７】図７は、ルーティングポリシから経路を生成する方法のステップを概略化したフローチャートである。
【発明を実施するための形態】
【００６９】
特にポータブルナビゲーション装置（ＰＮＤ）に関連させて、本発明の実施形態を説明する。しかし、本発明の教示はＰＮＤに限定されず、経路計画機能性及びナビゲーション機能性を提供するようにポータブル構成でナビゲーションソフトウェアを実行するように構成されたどのような種類の処理装置にも広く本発明を適用可能であることを忘れてはならない。従って本出願に関連して、ナビゲーション装置は装置がＰＮＤとして具現化されるか、自動車などの車両として具現化されるか、あるいはポータブル計算資源、経路計画ソフトウェア及びナビゲーションソフトウェアを実行するポータブルパーソナルコンピュータ（ＰＣ）等、移動電話又はパーソナルデジタルアシスタント（ＰＤＡ）として具現化されるかにかかわらず、どのような種類の経路計画／ナビゲーション装置も（制限なく）含んでもよい。
【００７０】
更に、本発明の実施形態は道路区分に関連して説明される。歩道、河川、運河、自転車道路、航路又は鉄道線路などの他のナビゲート可能区分にも本発明を適用可能であってもよいことを認識すべきである。
【００７１】
また、使用者が１つの地点から別の地点までどのようにナビゲートすべきかに関する命令を求めておらず、単に所定の場所のビューの提供を希望しているだけであるような状況でも、本発明の教示を利用可能であることも以下の説明から明らかになるだろう。そのような状況では、使用者により選択される「目的」地は、使用者がナビゲートを開始することを望む対応する出発地を有する必要はなく、そのため本明細書において「目的」地又は実際には「目的地」のビューは経路の生成が不可欠であること、「目的地」までの走行が実際に起こらなければならないこと、又は実際に目的地の存在が対応する出発地の指定を必要とすることを意味しないと解釈されるべきである。
【００７２】
以上の条件に留意して、図１の全地球測位システム（ＧＰＳ）などは多様な目的のために使用される。一般に、ＧＰＳは連続した位置、速度、時間及び場合によっては無限の数の使用者に関する方向情報を判定することが可能な衛星無線を利用するナビゲーションシステムである。以前はＮＡＶＳＴＡＲとして知られていたＧＰＳは、きわめて精密な軌道で地球を周回する複数の衛星を含む。それらの精密な軌道に基づいて、ＧＰＳ衛星は自身の場所をＧＰＳデータとして何らかの数の受信ユニットへ中継できる。しかし、ＧＬＯＳＮＡＳＳ、全地球測位衛星システム、ＣＯＭＰＡＳＳ測位システム又はＩＲＮＳＳ（インド地域航法衛星システム）などの全地球測位システムも使用可能だろうということが理解される。
【００７３】
ＧＰＳデータを受信するように特別に装備された装置がＧＰＳ衛星信号に関して無線周波数のスキャンを開始した場合に、ＧＰＳシステムは実現される。ＧＰＳ衛星から無線信号を受信すると、装置は複数の異なる従来の方法のうち１つの方法によってその衛星の正確な場所を判定する。装置は多くの場合に、少なくとも３つの異なる衛星信号を取得するまで信号に関するスキャンを継続する（尚、通常、２つの信号のみでは位置は判定されないが、他の三角測量技術を使用して２つの信号のみで位置を判定することは可能である）。幾何学的三角測量を実現すると、受信機は３つの既知の位置を利用して衛星に対する受信機自体の２次元位置を判定する。これは既知の方法で実行可能である。更に、第４の衛星信号を取得することにより、受信装置は既知の方法で同一の幾何学的計算により受信装置自体の３次元位置を計算できる。位置及び速度のデータは無限の数の使用者により連続的にリアルタイムで更新可能である。
【００７４】
図１に示されるように、ＧＰＳシステム１００は地球１０４を周回する複数の衛星１０２を備える。ＧＰＳ受信機１０６は複数の衛星１０２のうちいくつかの衛星からＧＰＳデータをスペクトラム拡散ＧＰＳ衛星データ信号１０８として受信する。スペクトラム拡散データ信号１０８は各衛星１０２から連続的に送信され、送信される各スペクトラム拡散データ信号１０８はそのデータストリームを発信している特定の衛星１０２を識別する情報を含むデータストリームを含む。２次元位置を計算可能にするために、ＧＰＳ受信機１０６は、一般に少なくとも３つの衛星１０２からのスペクトラム拡散データ信号１０８を必要とする。第４のスペクトラム拡散データ信号を受信すると、ＧＰＳ受信機１０６は既知の技術を使用して３次元位置を計算することが可能である。
【００７５】
図２を参照すると、ＧＰＳ受信装置１０６を備えるか又はＧＰＳ受信装置１０６に結合されたナビゲーション装置２００（すなわち、ＰＮＤ）はデジタル接続、例えば既知のＢｌｕｅｔｏｏｔｈ技術によるデジタル接続を確立するために、移動装置（図示せず）、例えば移動電話、ＰＤＡ及び／又は移動電話技術を備える何らかの装置を介して「移動」通信網又は電気通信網のネットワークハードウェアとのデータセッションを必要に応じて確立することが可能である。その後、移動装置はネットワークサービスプロバイダを介してサーバ１５０との間にネットワーク接続（例えば、インターネットを介する）を確立できる。従って、「リアルタイム」の又は少なくともごく「最新」の情報のゲートウェイを提供するために、ナビゲーション装置２００（単独で及び／又は車両に搭載されて走行する間に走行可能であり、多くの場合に走行する）とサーバ１５０との間で「移動」ネットワーク接続を確立できる。
【００７６】
移動装置（サービスプロバイダを介する）と、サーバ１５０などの別の装置との間で例えばインターネットを使用してネットワーク接続を確立することは既知の方法で実行可能である。この点に関して、例えばＴＣＰ／ＩＰレイヤプロトコルなどの何らかの数の適切なデータ通信プロトコルを採用可能である。更に、移動装置はＣＤＭＡ２０００、ＧＳＭ、ＩＥＥＥ８０２．１１ａ／ｂ／ｃ／ｇ／ｎなどの何らかの数の通信規格を利用できる。
【００７７】
従って、データ接続を介して、例えば移動電話又はナビゲーション装置２００内部の移動電話技術を介して実現可能なインターネット接続が利用されてもよいことがわかる。
【００７８】
図示されていないが、ナビゲーション装置２００はナビゲーション装置２００自体の中に独自の移動電話技術を当然含んでもよい（例えば、アンテナを含むか、又はオプションとしてナビゲーション装置２００の内部アンテナを使用する）。ナビゲーション装置２００内部の移動電話技術は、内部構成要素を含むことができ及び／又は例えば必要な移動電話技術及び／又はアンテナによって完成する挿入可能なカード（例えば、サブスクライバアイデンティティモジュール（ＳＩＭ）カード）を含むことができる。このためナビゲーション装置２００内部の移動電話技術は、同様にナビゲーション装置２００とサーバ１５０との間でいずれかの移動装置に類似する方法で、例えばインターネットを介するネットワーク接続を確立できる。
【００７９】
電話設定に関して、絶えず変化している移動電話の型式、メーカーなどに対して正確に動作するためにＢｌｕｅｔｏｏｔｈ有効化ナビゲーション装置が使用され、例えば型式／メーカー別設定がナビゲーション装置２００に記憶されてもよい。この情報に関して記憶されるデータは更新可能である。
【００８０】
図２では、ナビゲーション装置２００はいくつかの異なる構成のうちいずれかの構成により実現可能な汎用通信チャネル１５２を介してサーバ１５０と通信しているものとして示される。通信チャネル１５２は、一般にナビゲーション装置２００とサーバ１５０を接続する伝搬媒体又は伝搬経路を表す。サーバ１５０とナビゲーション装置２００との間に通信チャネル１５２を介する接続が確立された場合に、サーバ１５０及びナビゲーション装置２００は通信できる（尚、そのような接続は、移動装置を介するデータ接続、パーソナルコンピュータを使用するインターネットを介する直接接続などであることが可能である）。
【００８１】
通信チャネル１５２は特定の通信技術に限定されない。更に、通信チャネル１５２は単一の通信技術に限定されない。すなわち、チャネル１５２は多様な技術を使用するいくつかの通信リンクを含んでもよい。例えば通信チャネル１５２は電気通信、光通信及び／又は電磁通信などのための経路を提供するように構成可能である。従って、通信チャネル１５２は電気回路、ワイヤ及び同軸ケーブルなどの電気導体、光ファイバケーブル、変換器、無線周波数（ＲＦ）波、大気、自由空間などのうち１つ又はそれらの組み合わせを含むが、それらに限定されない。更に、通信チャネル１５２は、例えばルータ、中継器、バッファ、送信機及び受信機などの中間装置を含むことができる。
【００８２】
１つの例示的な構成において、通信チャネル１５２は電話網及びコンピュータネットワークを含む。更に、通信チャネル１５２は無線通信、例えば赤外線通信、マイクロ波周波数通信などの無線周波数通信に対応可能であってもよい。また、通信チャネル１５２は衛星通信に対応できる。
【００８３】
通信チャネル１５２を介して送信される通信信号は、所定の通信技術に必要とされる又は望まれる信号を含むが、それに限定されない。例えば信号は時分割多元接続（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）、符号分割多元接続（ＣＤＭＡ）、汎欧州デジタル移動電話方式（ＧＳＭ）、汎用パケット無線サービス（ＧＰＲＳ）などのセルラ通信技術で使用されるように構成されてもよい。通信チャネル１５２を介して、デジタル信号及びアナログ信号の双方を送信可能である。それらの信号は通信技術で望まれるような変調信号、暗号化信号及び／又は圧縮信号であってもよい。
【００８４】
サーバ１５０は図示されなくてもよい他の構成要素に加えて、メモリ１５６に動作可能に接続され、有線接続又は無線接続１５８を介して大容量記憶装置１６０にも動作可能に接続されたプロセッサ１５４を含む。大容量記憶装置１６０は、ナビゲーションデータ及び地図情報を格納し、サーバ１５０とは別の装置であることが可能であるか、あるいはサーバ１５０に組み込まれてよい。プロセッサ１５４は通信チャネル１５２を介してナビゲーション装置２００との間で情報を送受信するために、送信機１６２及び受信機１６４にも動作可能に接続される。送受信される信号はデータ信号、通信信号及び／又は他の伝搬信号を含んでもよい。送信機１６２及び受信機１６４は、ナビゲーションシステム２００の通信設計で使用される通信要件及び通信技術に従って選択又は設計されてもよい。更に、送信機１６２及び受信機１６４の機能は１つのトランシーバに組み合わされてもよい。
【００８５】
前述のように、ナビゲーション装置２００は通信チャネル１５２を介して信号及び／又はデータを送受信するために送信機１６６及び受信機１６８を使用して、通信チャネル１５２を介してサーバ１５０と通信するように構成可能であるが、これらの装置はサーバ１５０以外の装置と通信するためにも使用可能である。更に、送信機１６６及び受信機１６８はナビゲーション装置２００の通信設計で使用される通信要件及び通信技術に従って選択又は設計され、送信機１６６及び受信機１６８の機能は先に説明したような１つのトランシーバに組み合わされてもよい。ナビゲーション装置２００はいくつかが以下に更に詳細に説明されるように、他のハードウェア部分及び／又は機能部分を当然備えている。
【００８６】
サーバメモリ１５６に格納されたソフトウェアはプロセッサ１５４に関する命令を提供し、このソフトウェアによりサーバ１５０はナビゲーション装置２００にサービスを提供できる。サーバ１５０により提供されるサービスの１つは、ナビゲーション装置２００からの要求を処理すること及び大容量データ記憶装置１６０からナビゲーション装置２００へナビゲーションデータを送信することを含む。サーバ１５０により提供可能な別のサービスは、所望のアプリケーションに関して種々のアルゴリズムを使用してナビゲーションデータを処理すること及びこれらの計算の結果をナビゲーション装置２００へ送信することを含む。
【００８７】
サーバ１５０は、無線チャネルを介してナビゲーション装置２００によりアクセス可能な遠隔データソースを構成する。サーバ１５０はローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、仮想プライベートネットワーク（ＶＰＮ）などに配置されたネットワークサーバを含んでもよい。
【００８８】
サーバ１５０はデスクトップ又はラップトップコンピュータなどのパーソナルコンピュータを含んでもよく、通信チャネル１５２はパーソナルコンピュータとナビゲーション装置２００との間に接続されたケーブルであってもよい。あるいは、サーバ１５０とナビゲーション装置２００との間にインターネット接続を確立するために、パーソナルコンピュータはナビゲーション装置２００とサーバ１５０との間に接続されてもよい。
【００８９】
ナビゲーション装置２００は自動的に、随時又は使用者がナビゲーション装置２００をサーバ１５０に接続した時点で更新されてもよい情報ダウンロードを介してサーバ１５０から情報を提供されてもよく、且つ／又は例えば無線移動接続装置及びＴＣＰ／ＩＰ接続を介してサーバ１５０とナビゲーション装置２００との間でより一定の又は頻繁な接続が実行されるのに応じて更に動的であってもよい。多くの動的計算に関して、サーバ１５０のプロセッサ１５４は大量の処理要求を処理するために使用されてもよいが、ナビゲーション装置２００のプロセッサ（図２には図示せず）も多くの場合にサーバ１５０への接続から独立して、大量の処理及び計算を処理できる。
【００９０】
図３を参照すると、ナビゲーション装置２００のブロック図はナビゲーション装置のすべての構成要素を含んではおらず、多くの構成要素の例を表しているだけであることに注意すべきである。ナビゲーション装置２００は筐体（図示せず）の中に配置される。ナビゲーション装置２００は、例えば先に説明したプロセッサ２０２を備える処理回路網を含み、プロセッサ２０２は入力デバイス２０４と、ディスプレイデバイス、例えば表示画面２０６とに結合される。ここでは入力デバイス２０４は単数であるものとして参照するが、入力デバイス２０４がキーボードデバイス、音声入力デバイス、タッチパネル及び／又は情報を入力するために利用される他のあらゆる既知の入力デバイスを含む何らかの数の入力デバイスを表していることを当業者は理解すべきである。同様に、表示画面２０６は、例えば液晶ディスプレイ（ＬＣＤ）のような何らかの種類の表示画面を含むことができる。
【００９１】
１つの構成において、複数の表示選択肢の中の１つを選択するために又は複数の仮想ボタン又は「ソフト」ボタンの中の１つを起動するために使用者が表示画面２０６の一部にタッチするだけでよいように、入力デバイス２０４、タッチパネル及び表示画面２０６の１つの態様は、情報の入力（直接入力、メニュー選択などによる）及びタッチパネル画面を介する情報の表示の双方を可能にするためにタッチパッド又はタッチスクリーン入力部２５０（図４）を含む一体型入力／ディスプレイデバイスを提供するように統合される。この点に関して、プロセッサ２０２はタッチスクリーンと関連して動作するグラフィカルユーザインタフェース（ＧＵＩ）を支援する。
【００９２】
ナビゲーション装置２００において、プロセッサ２０２は接続２１０を介して入力デバイス２０４に動作可能に接続され、入力デバイス２０４から接続２１０を介して入力情報を受信可能であり、また表示画面２０６及び出力デバイス２０８へ情報を出力するために、対応する出力接続２１２を介して表示画面２０６及び出力デバイス２０８のうち少なくとも一方に動作可能に接続される。ナビゲーション装置２００は出力デバイス２０８、例えば可聴出力デバイス（例えばスピーカ）を含んでもよい。出力デバイス２０８はナビゲーション装置２００の使用者に対して可聴情報を生成できるので、入力デバイス２０４も入力音声コマンドを受信するためのマイク及びソフトウェアを含むことができることを同様に理解すべきである。更に、ナビゲーション装置２００は、例えばオーディオ入力／出力デバイスのような何らかの追加入力デバイス２０４及び／又は何らかの追加出力デバイスを含むこともできる。
【００９３】
プロセッサ２０２は、接続２１６を介してメモリ２１４に動作可能に接続され、接続２２０を介して入出力（Ｉ／Ｏ）ポート２１８との間で情報を受信／送信するように更に構成され、Ｉ／Ｏポート２１８は、ナビゲーション装置２００の外部のＩ／Ｏデバイス２２２に接続可能である。外部Ｉ／Ｏデバイス２２２は、例えばイヤホンなどの外部聴取デバイスを含んでもよいが、それに限定されない。更に、Ｉ／Ｏデバイス２２２への接続は、例えばハンズフリー操作及び／又は音声起動動作、イヤホン又はヘッドホンへの接続及び／又は例えば移動電話への接続のためのカーステレオユニットなどの他の何らかの外部デバイスへの有線接続又は無線接続であることが可能であり、移動電話接続はナビゲーション装置２００と例えばインターネット又は他の何らかのネットワークとの間のデータ接続を確立し且つ／又は例えばインターネット又は他の何らかのネットワークを介するサーバへの接続を確立するために使用可能である。
【００９４】
ナビゲーション装置２００のメモリ２１４は、不揮発性メモリの一部（例えば、プログラムコードを格納するため）及び揮発性メモリの一部（例えば、プログラムコードが実行される場合にデータを格納するため）を備える。ナビゲーション装置は、取り外し可能メモリカード（一般にカードと呼ばれる）を装置２００に追加できるようにするために接続２３０を介してプロセッサ２０２と通信するポート２２８を更に備える。説明されている実施形態では、ポートはＳＤ（セキュアデジタル）カードを追加できるように構成される。他の実施形態では、ポートは他のフォーマットのメモリ（コンパクトフラッシュ（ＣＦ）カード、メモリスティック、ｘＤメモリカード、ＵＳＢ（ユニバーサルシリアルバス）フラッシュドライブ、ＭＭＣ（マルチメディア）カード、スマートメディアカード、マイクロドライブなど）の接続を可能にしてもよい。
【００９５】
図３は、プロセッサ２０２とアンテナ／受信機２２４との間の接続２２６を介する動作接続を更に示し、アンテナ／受信機２２４は、例えばＧＰＳアンテナ／受信機であり、従って図１のＧＰＳ受信機１０６と同様に機能するだろう。尚、図中符号２２４により示されるアンテナ及び受信機は、図示の便宜上概略的に組み合わされているが、アンテナ及び受信機は個別に配置された構成要素であってもよく、アンテナは、例えばＧＰＳパッチアンテナ又はヘリカルアンテナであってもよいことを理解すべきである。
【００９６】
図３に示される電子構成要素が従来のように１つ以上の電源（図示せず）により給電されることは当業者には当然理解されるだろう。そのような電源は、内部バッテリ及び／又は低電圧ＤＣ電源又は他の何らかの適切な構造に対応する入力部を含んでもよい。当業者には理解されるように、図３に示される構成要素の異なる組み合わせも考えられる。例えば図３に示される構成要素は、有線接続及び／又は無線接続などを介して互いに通信していてもよい。従って、本明細書において説明されるナビゲーション装置２００は、ポータブル又はハンドヘルドナビゲーション装置２００であることが可能である。
【００９７】
更に、図３のポータブル又はハンドヘルドナビゲーション装置２００は、例えば自転車、バイク、自動車又はボートなどの車両に既知の方法で接続又は「ドッキング」させることが可能である。その場合ナビゲーション装置２００は、ポータブル又はハンドヘルドナビゲーションに使用するためにドッキング場所から取り外し可能である。実際他の実施形態では、装置２００は使用者のナビゲーションのためにハンドヘルドになるように構成されてもよい。
【００９８】
図４を参照すると、ナビゲーション装置２００は図２の一体型入力／ディスプレイデバイス２０６及び他の構成要素（内部ＧＰＳ受信機２２４、プロセッサ２０２、電源（図示せず）、メモリシステム２１４などを含むが、それらに限定されない）を含むユニットであってもよい。
【００９９】
ナビゲーション装置２００はアーム２５２に載置されてもよく、アーム２５２自体は吸引カップ２５４を使用して車両のダッシュボード／ウィンドウなどに固定されてもよい。このアーム２５２はナビゲーション装置２００をドッキングできるドッキング場所の一例である。ナビゲーション装置２００は、例えばナビゲーション装置２００をアーム２５２にスナップ結合することによりドッキング場所のアーム２５２にドッキングされるか又は他の方法で結合されることが可能である。ナビゲーション装置２００はアーム２５２で回転可能であってもよい。ナビゲーション装置２００とドッキング場所との結合を解除するために、例えばナビゲーション装置２００にあるボタン（図示せず）を押してもよい。ナビゲーション装置２００をドッキング場所に着脱するための他の同などに適切な構造は、当業者には周知である。
【０１００】
説明されている実施形態では、ナビゲーション装置のプロセッサ２０２はアンテナ２２４により受信されたＧＰＳデータを受信し、そのＧＰＳデータをＧＰＳデータが受信されたときのタイムスタンプと共に随時格納するようにプログラムされ、メモリ２１４はナビゲーション装置の場所のレコードを作成する。そのように格納される各データレコードはＧＰＳ測位場所であると考えてよく、すなわちこれはナビゲーション装置の測位場所であり、緯度、経度、タイムスタンプ及び正確度レポートを含む。
【０１０１】
一実施形態において、データは、例えば５秒ごとにほぼ定期的に格納される。他の周期も可能であり、データ分解能とメモリ容量との間で均衡が保たれることは当業者には理解されるだろう。すなわち、より多くのサンプルを取り入れることによりデータの分解能が向上するにつれて、そのデータを保持するために更に多くのメモリが要求される。しかし、他の実施形態では、分解能はほぼ１秒ごと、１０秒ごと、１５秒ごと、２０秒ごと、３０秒ごと、４５秒ごと、１分ごと、２．５分ごと（又は実際にはそれらの周期の間の任意の周期）であってもよいだろう。従って、装置のメモリの中では複数の時点で装置２００の所在地のレコードが作成されている。
【０１０２】
いくつかの実施形態において、周期が長くなるにつれて取り込まれるデータの品質は低下し、劣化の程度はナビゲーション装置２００が移動していた速度に少なくとも部分的に従属し、約１５秒の周期が適切な上限を提供してもよいことがわかる。
【０１０３】
ナビゲーション装置２００は、一般に装置の所在地のレコードを作成するように構成されるが、実施形態によっては行程の開始時又は終了時に所定の周期及び／又は距離に関するデータを記録しない。そのような構成はおそらくはナビゲーション装置２００の使用者の自宅及び他の頻繁に訪れる目的地の所在を保護するので、使用者のプライバシーを保護するのに有用である。例えばナビゲーション装置２００は、行程の最初の約５分間に関して及び／又は行程の最初の約１マイルに関してはデータを格納しないように構成されてもよい。
【０１０４】
他の実施形態では、ＧＰＳは定期的に格納されず、所定のイベントが発生した時点でメモリに格納されてもよい。例えばプロセッサ２０２は装置が道路のジャンクションを通過するか、道路区分の変更又は他のそのようなイベントが発生した時点でＧＰＳデータを格納するようにプログラムされてもよい。
【０１０５】
更に、プロセッサ２０２は装置２００の所在地のレコード（すなわち、ＧＰＳデータ及びタイムスタンプ）を随時サーバ１５０にアップロードするように構成される。ナビゲーション装置２００がナビゲーション装置２００をサーバ１５０に接続する通信チャネル１５２を永久的に有するか又はほぼ常に有するいくつかの実施形態において、データのアップロードは、例えば２４時間ごとに一度などの周期で起こる。他の周期も可能であり、実質的に１５分ごと、３０分ごと、毎時間、２時間ごと、５時間ごと、１２時間ごと、１日おき、毎週又はそれらの間の任意の時点などの周期のうちいずれか１つであってもよいことは当業者には理解されるだろう。実際そのような実施形態では、プロセッサ２０２はほぼリアルタイムで装置の所在地のレコードをアップロードするように構成されてもよいが、これは実際にデータが相対的に短い送信間周期で随時送信され、そのため疑似リアルタイムであると考えるのがより正確であることを必然的に意味してもよい。そのような疑似リアルタイムの実施形態において、ナビゲーション装置はメモリ２１４の中及び／又はポート２２８に挿入されたカードにＧＰＳ測位場所をバッファし、所定の数が格納された時点でそれらのデータを送信するように構成されてもよい。この所定の数は２０、３６、１００、２００又はそれらの間の任意の数であってもよい。所定の数はメモリ２１４又はポート２２８の中のカードのサイズにより部分的に管理されることが当業者には理解されるだろう。
【０１０６】
ほぼ常に存在する通信チャネル１５２を備えていない他の実施形態では、プロセッサ２０２は通信チャネル１５２が作成された時点でレコードをサーバ１５２にアップロードするように構成されてもよい。これは例えばナビゲーション装置２００が使用者のコンピュータに接続された時点であってもよい。このような実施形態でも、ナビゲーション装置はメモリ２１４の中又はポート２２８に挿入されたカードにＧＰＳ測位場所をバッファするように構成されてもよい。メモリ２１４又はポート２２８に挿入されたカードがＧＰＳ測位場所で満杯になった場合、ナビゲーション装置は最も古いＧＰＳ測位場所を削除するように構成されてもよく、そのため先入れ先出し（ＦＩＦＯ）バッファであると考えられてもよい。
【０１０７】
説明されている実施形態において、所在地のレコードは１つ以上のトレースを含み、各トレースは２４時間の周期の中のそのナビゲーション装置２００の移動を表す。各２４時間は暦上の１日と一致するように構成されるが、他の実施形態ではこれは必須ではない。
【０１０８】
一般に、ナビゲーション装置２００の使用者はサーバ１５０にアップロードされる装置の所在地のレコードに同意する。同意が得られない場合、サーバ１５０にレコードはアップロードされない。ナビゲーション装置自体及び／又はナビゲーション装置が接続されているコンピュータは、そのような所在地のレコードの使用に関して使用者の同意を求めるように構成されてもよい。
【０１０９】
サーバ１５０は装置の所在地のレコードを受信し、処理のためにレコードを大容量データ記憶装置１６０の中に格納するように構成される。従って、時間の経過に伴って、大容量記憶装置１６０は、データをアップロードしていたナビゲーション装置２００の所在地の複数のレコードを累積する。
【０１１０】
そのような多数の装置２００からアップロードされた軌跡が解析されて、異なる道路区分の可能性のある分布を生成するために使用されてもよい。それらは異なる道路区分の予測移動時間を生成するためにも使用されてもよい。
【０１１１】
先に説明したように、大容量データ記憶装置１６０は地図データを更に格納する。そのような地図データは、道路区分の場所に関する情報、関心地点に関する情報及び地図上で一般に見られる他のそのような情報を提供する。
【０１１２】
図５は、本発明の実施形態に従ったルーティングポリシを生成する方法を実施するために使用されてもよい例示的なシステムを示す。
【０１１３】
ある地点において、ナビゲーション装置２００は、電子地図データ１６０により表されるナビゲート可能ネットワークを通じてユーザをガイドするためのナビゲーション命令を出力する、例えばユーザに対して表示される必要があってもよい。出発地及び目的地はユーザにより特定されてもよい。しかしながら、本発明は、何らかの理由でナビゲーション装置により要求されてもよい任意の第１及び第２の場所の間の経路の生成に等しく適用可能であり、ここで第１及び第２の場所の１つ又は両方がナビゲーション装置又はユーザにより判定されてもよい。例えば、第１の場所は装置の現在の場所であってもよい。
【０１１４】
電子地図データ１６０は、好適には、地図データ１６０の一部として格納された、あるいは、大容量データ記憶装置１６０に分離して格納された、地図によりカバーされる道路ネットワークの各区分と関連付けられた（不連続的な又は連続的な）移動時間確率分布データを含む。（選択的には特定の期間の）各区分の予想移動時間は大容量データ記憶装置１６０に格納されてもよく、あるいは、サーバ１５０が確率分布データから予想移動時間を取得するように構成されてもよい。
【０１１５】
ナビゲーション装置２００は、通信チャネル１５２を通じてサーバ１５０へ出発地及び目的地を通信（伝達）する。サーバ１５０は、第１のステップ５０１において、最短予想移動時間を有する出発地から目的地までの経路（すなわち“最速”経路）を判定するために地図データ１６０の区分の予想移動時間を使用する。これを達成するために、従来の決定論的ルーティングアルゴリズムが使用されてもよい。
【０１１６】
あるいは、ナビゲーション装置２００は、そうした最速経路を判定するためにローカルに格納された地図データ及び予想移動時間の情報を使用してもよい。その場合、選択的に、この経路又はその予想移動時間をサーバ１５０に通信（伝達）してもよい。
【０１１７】
サーバ１５０は、第２のステップ５０２において、出発地を出てから時間予算内に目的地に到着する確率を最大化するルーティングポリシを生成するために確率論（非決定論）ルーティングアルゴリズムを使用する。ここで時間予算は、スケーリング因子αを乗算されたこの最速予想移動時間と等しい。次にサーバ１５０は、通信チャネル１５２を通じてナビゲーション装置２００にルーティングポリシを通信（伝達）してもよく、あるいは、それをサーバメモリ１５６に格納してもよい。
【０１１８】
サーバ１５０又はナビゲーション装置２００は、ユーザを目的地にガイドするための命令を生成するために、生成されたルーティングポリシをナビゲーション装置のライブＧＰＳｆｉｘデータに適用してもよい。サーバ１５０がルーティングポリシを適用するのであれば、ナビゲーション装置２００からライブ場所情報を受信する必要があり、ユーザに表示される命令をナビゲーション装置２００に送信して戻すだろう。
【０１１９】
αの値は固定されてもよい（例えば１．２又は１．６）。しかしながら、ユーザによって少なくとも部分的に制御されてもよい。
【０１２０】
図６は、ユーザ６０１がナビゲーション装置２００のタッチスクリーン２５０と対話することを示している。タッチスクリーン２５０は、左端６００Ａが"より速く"であり、右端６００Ｂが"より信頼できる"であるスライダインタフェース６００を表示している。ユーザ６０１は、一端又は他端６００Ａ、６００Ｂあるいはそれらの間のどこかの所望の位置にスライダインタフェースを設定するために指を使用できる。スライダ設定は、適切なマッピングに従ってαの数値に変換されてもよい。マッピングは静的であってもよいし、あるいは、状況に応じて（例えば出発地及び／又は目的地により判定（決定）される特性に従って）変化してもよい。それは測定されたデータ又はシミュレーションされたデータに基づいてもよい。αの値はα＝αｕ・α０であってもよく、ここで、αｕはスライダ設定から取得されたユーザにより判定（決定）された値であり、α０は固定パラメータである。
【０１２１】
図５を参照して記載したステップは、出発地から目的地までユーザを向けるのに十分であるが、それにも関わらず、例えば、ナビゲーション装置２００が正確な出発地及び目的地を識別したこと、あるいは、それが正確に機能しているという安心感を提供するために、出発前に指示経路を見ることがユーザにとって望ましいかもしれない。
【０１２２】
図７は、上述したようなルーティングポリシが受信されるか、アクセスされる第１ステップを示している。これはナビゲーション装置２００又はサーバ１５０で行われてもよい。ルーティングポリシは外部ソースから受信されてもよく、あるいは、単純に、関連装置により、例えば内部メモリ２１４又は１５６からアクセスされてもよい。第２ステップ７０２では、経路のいくつか又は全部に沿って各区分が区分の予想移動時間に通過されるシナリオにルーティングポリシを適用することによって、経路が生成される。
【０１２３】
この経路は、必要に応じて、サーバ１５０からナビゲーション装置２００へ通信（伝達）されてもよく、レビューのためにナビゲーション装置２００によりユーザに対して表示されてもよい。
【０１２４】
単一の経路を表示するのではなく、いくつかの実施形態は２つ以上の代替経路のセットを生成し、それらをユーザに表示してもよい。これは、２つ以上のシナリオを考慮することによって行われてもよく、そこでは、予想移動時間以外の時間がシナリオの１つ以上において移動のいくつかに対して使用され、予想移動時間が当該移動の残りに対してのみ使用される。それは、各々が１つ以上の経路を生成するために使用されてもよい２つ以上のルーティングポリシを生成するために２つ以上の異なるαの値を使用することによって行われてもよい。
【０１２５】
要約すると、ＳＯＴＡに基づき魅力的なエンドユーザ特徴を設計する際の主要な障害は、各移動に対して時間予算を明示的に特定する必要性である。別の挑戦は、通常ユーザは出発前に推奨経路全体を見たいが、（単純な経路とは対照的に）ルーティングポリシは１つの単一経路を規定しないという事実である。本発明の実施形態は、ルーティングポリシから１つの経路を抽出する方法に関するものであり、異なる状況に対して適正な時間予算の自動判定を可能にする方法に関するものである。
【０１２６】
ルーティングポリシから経路を判定
賢明な最初の経路が、以下のようにルーティングポリシからユーザへの表示のために抽出されうる。我々は、ユーザが全ての道路区分上で正確な予想移動時間を必要とする状況にルーティングポリシを適用することから生じるであろう経路として出発前にユーザへ表示される経路を規定する。
【０１２７】
基本信頼性ルーティング
所与の出発地及び目的地に対して１つの信頼できる基本経路を計算するために、最速経路に関する予想移動時間ｔに基づく時間予算ｂを使用する。固定パラメータα０≧１を選択して、
【０１２８】
【数３】
2018510335.tif 000005
を定義する。
【０１２９】
小さな値のαは、最速経路に非常に近くなるルーティングポリシを生み、平均して速いことが予想される経路に固執する場合にタイトな時間予算が維持されうるのみである。大きな値のαは非常に信頼できる経路となるが、予想移動時間の著しい増加を招くかもしれない。
【０１３０】
ユーザ嗜好に基づく信頼性ルーティング
経路信頼度をユーザ嗜好に設定する権限をユーザに持たせるために、固定パラメータα０をユーザ定義パラメータαｕに置き換える。この状況では、ＳＯＴＡの時間予算は、
【０１３１】
【数４】
2018510335.tif 000006
に設定されるだろう。
【０１３２】
この概念及び上述した基本信頼性ルーティングの概念の組み合わせを通じて、ユーザ嗜好ベースの経路信頼度は、時間、地図領域、及び／又は出発地と目的地との距離に基づいて行われる調整から恩恵を受けることもできるだろう。
【０１３３】
【数５】
2018510335.tif 000007
【０１３４】
ユーザインタフェースについて、ユーザが数字を入力しなければならない問題に直面することは賢明ではないかもしれないが、代わりに経路信頼度を調整するためにスライダを使用することが賢明かもしれないことが特定されている。
【０１３５】
変化する信頼度を伴う代替経路
経路信頼度がパラメータαを介して調整されうる場合、変化する信頼度の代替経路を計算するためにＳＯＴＡを使用することもできる。事実、運転手は、代替経路を望む多くの状況において、より信頼できる代替を実際に（恐らく無意識に）探していると思われる。
【０１３６】
この線に沿って、異なる時間予算（すなわち異なる値のパラメータα）について計算されたいくつかのルーティングポリシから上述したようにして経路を抽出することによって、代替経路のネットワークが計算されうる。これらの異なる値のパラメータαは、固定セットの値から生じるか、あるいは、代替計算のために使用されるパラメータのセットは、時間、地図領域、移動距離等に依存しうる。
【０１３７】
異なる交通状況を予想した代替経路
代替経路を計算するためにＳＯＴＡを採用する別の方法は、計算されたルーティングポリシを直接利用することである。上述したように、ルーティングポリシは本質的に、今までに経路に要した移動時間に依存した、目的地に向けて進み続ける方法のルールのセットである。結果として、１つのルーティングポリシは、経路に沿って異なる移動時間を招く場合に多くの異なる経路に至ってもよい。
【０１３８】
従って、経路のあるセクションに関する異なる移動時間を想定して、１つのルーティングポリシを実行することにより（複数の）代替経路が計算されうる。例えば、“ルーティングポリシから経路を判定”というセクションに記載したように経路がルーティングポリシから生成でき、経路の最初、例えば２０％の異なる移動時間を想定できる。想定移動時間は、例えば、分布の最速及び最遅の５％を無視して、残りの分布から等距離にあるサンプルを拾うことによって、対応する移動時間分布から抽出されうる。
【０１３９】
経路のこの最初の部分における各想定移動時間は、代替経路を規定する、この部分における又はこの部分から少し後における異なる経路決定に至ってもよい。より多くの代替が望まれる場合、プロセスは、各代替の分岐部分の最初の例えば２０％の異なる移動時間を想定し、結果として生じる代替に繰り返されうる。
【０１４０】
（あらゆる添付の請求項、要約書、図面を含む）この明細書で開示される特徴の全て、及び／又は、そのように開示されたあらゆる方法又はプロセスのステップの全ては、そうした特徴及び／又はステップの少なくともいくつかが相互に排他的となる組み合わせを除いて、あらゆる組み合わせで組み合わされてもよい。
【０１４１】
（あらゆる添付の請求項、要約書、図面を含む）この明細書に開示される各特徴は、同一の、均等の又は類似の目的を果たす代替特徴により置き換えられてもよい。従って、明確にそうでないと述べられていない限り、開示される各特徴は均等な又は類似の特徴の汎用シリーズの一例である。
【０１４２】
本発明は、任意の前述の実施形態に限定されない。本発明は、（あらゆる添付の請求項、要約書、図面を含む）この明細書に開示される特徴の任意の新規な１つ又は任意の新規な組み合わせに及び、あるいは、開示された任意の方法又はプロセスのステップの任意の新規な１つ又は任意の新規な組み合わせに及ぶ。請求項は、前述の実施形態を単にカバーするものと解釈されるべきではなく、請求項の範囲に入るあらゆる実施形態もカバーされると解釈されるべきである。
【図１】
2018510335.tif 000008
【図２】
2018510335.tif 000009
【図３】
2018510335.tif 000010
【図４】
2018510335.tif 000011
【図５】
2018510335.tif 000012
【図６】
2018510335.tif 000013
【図７】
2018510335.tif 000014
【国際調査報告】
2018510335.tif 000015
2018510335.tif 000016