(57)【要約】人間又は車両により移動可能な距離を制約するパラメータの出発地ノード又は現在地での初期値を所与として、目的地ノード又はホーム位置に到達するまでの間、前記出発地ノード又は前記現在地から人間又は車両により到達されうる複数の位置を含むエリアを判定して表示する方法が開示される。前記方法は、ポータブルナビゲーション装置等の移動装置及び／又はサーバ又はコンピュータで実施されてもよし、或いは、コンピュータプログラムとして提供されてもよい。【選択図】図１
2019515266.tif 000002
【特許請求の範囲】
【請求項１】
出発地ノード及び目的地ノードの間を移動する際に移動されてもよいエリアを判定する方法であって、
第１の値のパラメータを所与として人間又は車両が複数の位置から前記目的地ノードまで移動してもよい当該複数の位置を表す前記目的地ノードの周囲の第１のエリアを包含する第１の境界を示すデータを判定又は取得することであって、前記パラメータの値は、前記人間又は車両により移動可能な距離を制約する、前記判定又は取得することと、
前記出発地ノード及び前記目的地ノード以外の、前記第１の境界内の第１の位置に前記人間又は車両がいる場合の前記パラメータの値を、前記出発地ノードでの前記パラメータの初期値と、前記出発地ノードから前記第１の位置までの移動と関連付けられた前記パラメータの値の推定される変化とに基づいて、推定することと、
前記パラメータの前記初期値を所与として、前記目的地ノードに到達するまでの間に、前記第１の位置が前記人間又は車両により前記出発地ノードから到達されうるかどうかを判定するために、前記第１の位置での前記パラメータの前記推定された値と、前記第１の値とを比較することと、
を含むことを特徴とする方法。
【請求項２】
前記目的地ノードの周囲の複数の異なる境界を示すデータを判定又は取得することであって、各異なる境界は前記パラメータの異なるそれぞれの値と関連付けられており、前記異なる境界は当該境界と関連付けられた前記パラメータの前記値を所与として人間又は車両が前記目的地ノードへ移動してもよい位置を表す前記目的地ノードの周囲のエリアを包含する、前記判定又は取得することを含み、
前記方法は、前記第１の位置が存在する２つの隣接する前記境界間を判定することと、前記出発地ノードから前記人間又は車両により前記第１の位置が到達されうるかどうかを判定するために、前記第１の位置での前記パラメータの前記推定される値と、前記２つの境界のうち外側境界及び／又は内側境界と関連付けられた前記パラメータの前記値とを比較することと、をさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記人間又は車両が、前記出発地ノード及び前記目的地ノード及び前記第１の位置以外の、前記第１の境界内における及び／又は前記複数の境界のうちの隣接する２つの間における第２の位置にいる場合の前記パラメータの値を、前記出発地ノードでの前記パラメータの初期値と、前記出発地ノードから前記第２の位置までの移動と関連付けられた前記パラメータの値の前記推定される変化とに基づいて、推定することと、
前記パラメータの前記初期値を所与として、前記目的地ノードに到達するまでの間に前記人間又は車両により前記出発地ノードから前記第２の位置が到達されうるかどうかを判定するために、前記第２の位置での前記パラメータの前記推定される値を、前記第１の値と、及び／又は、前記２つの境界のうち外側境界及び／又は内側境界と関連付けられた前記パラメータの前記値と、比較することと
をさらに含むことを特徴とする請求項１又は２に記載の方法。
【請求項４】
前記パラメータの前記初期値に基づいて前記人間又は車両が前記出発地ノードから移動してもよい位置を表す前記出発地ノードの周囲のエリアを判定することと、
前記第１の境界、及び／又は、前記複数の異なる境界の少なくともいくつかを使用して、前記出発地ノードの周囲の前記エリア内の複数の前記位置の各々について、前記目的地ノードに到達するまでの間に前記複数の位置の各々が到達されうるかどうかを判定することと
を含むことを特徴とする請求項１乃至３の何れか１項に記載の方法。
【請求項５】
選択的にリアルタイムに、前記パラメータの前記初期値に基づいて、前記目的地ノードに到達するまでの間に前記出発地ノードから到達されうる前記出発地ノード及び前記目的地ノードの間の位置を含む、エリアの地図データを作成し、且つ／又は、エリアを表示するために前記方法を使用することをさらに含むことを特徴とする請求項１乃至４の何れか１項に記載の方法。
【請求項６】
前記パラメータの前記初期値に基づいて前記人間又は車両が前記出発地ノードから移動してもよい範囲を表す前記出発地ノードの地図データを作成すること、且つ／又は、当該出発地ノードの周囲の前記又はあるエリアを表示することを含むことを特徴とする請求項１乃至５の何れか１項に記載の方法。
【請求項７】
前記出発地ノードは、前記人間又は車両の現在地であり、前記初期値は前記パラメータの現在の値であることを特徴とする請求項１乃至６の何れか１項に記載の方法。
【請求項８】
前記方法は、前記現在地及び前記パラメータの現在の値が変化するにつれてリアルタイムに、前記第１の位置での前記パラメータの前記値を推定するステップと、前記第１の位置での前記パラメータの前記推定された値と、前記第１の値とを比較するステップとを繰り返すことを含むことを特徴とする請求項７に記載の方法。
【請求項９】
（ｉ）前記パラメータは、燃料量又は充電レベルであり、且つ／又は、
（ｉｉ）前記パラメータは、移動時間又は移動距離を表しており、且つ／又は、
（ｉｉｉ）前記パラメータの前記第１の値は、前記第１の境界から前記目的地ノードまでの移動時間又は移動距離であり、前記パラメータの前記初期値は、所望の又は最大の移動時間又は移動距離であり、前記第１の位置での前記パラメータの前記推定された値は、前記出発地ノードから前記第１の位置までの移動後の推定された残りの移動時間又は移動距離であることを特徴とする請求項１乃至８の何れか１項に記載の方法。
【請求項１０】
前記目的地ノードは固定位置であり、且つ／又は、前記目的地ノードの周囲の１又は複数の境界は格納データ又は履歴データを使用して判定されるか、或いは、それらから取得されることを特徴とする請求項１乃至９の何れか１項に記載の方法。
【請求項１１】
出発地ノードと目的地ノードとの間をナビゲートする、選択的にはナビゲーション装置である移動装置であって、
メモリと、
プロセッサとを備え、前記プロセッサは、
第１の値のパラメータを所与として前記装置を運ぶ人間又は車両が複数の位置から前記目的地ノードまで移動してもよい当該複数の位置を表す前記目的地ノードの周囲の第１のエリアを包含する第１の境界を示すデータを判定又は取得し、ここで前記パラメータの値は、前記装置を運ぶ前記人間又は車両により移動可能な距離を制約し、
前記出発地ノード及び前記目的地ノード以外の、前記第１の境界内の第１の位置に前記装置を運ぶ前記人間又は車両がいる場合の前記パラメータの値を、前記出発地ノードでの前記パラメータの初期値と、前記出発地ノードから前記第１の位置までの移動と関連付けられた前記パラメータの値の推定される変化とに基づいて、推定し、
前記パラメータの前記初期値を所与として、前記目的地ノードに到達するまでの間に、前記第１の位置が前記装置を運ぶ前記人間又は車両により前記出発地ノードから到達されうるかどうかを判定するために、前記第１の位置での前記パラメータの前記推定された値と、前記第１の値とを比較する、
ように構成されることを特徴とする移動装置。
【請求項１２】
出発地ノード及び目的地ノード間をナビゲートするシステムであって、
メモリ及びプロセッサを有する移動装置と、
サーバとを備え、前記移動装置は前記サーバと通信するように構成されており、
前記サーバ及び／又は前記プロセッサは、
第１の値のパラメータを所与として前記装置を運ぶ人間又は車両が複数の位置から前記目的地ノードまで移動してもよい当該複数の位置を表す前記目的地ノードの周囲の第１のエリアを包含する第１の境界を示すデータを判定又は取得し、ここで前記パラメータの値は、前記装置を運ぶ前記人間又は車両により移動可能な距離を制約し、
前記出発地ノード及び前記目的地ノード以外の、前記第１の境界内の第１の位置に前記装置を運ぶ前記人間又は車両がいる場合の前記パラメータの値を、前記出発地ノードでの前記パラメータの初期値と、前記出発地ノードから前記第１の位置までの移動と関連付けられた前記パラメータの値の推定される変化とに基づいて、推定し、
前記パラメータの前記初期値を所与として、前記目的地ノードに到達するまでの間に、前記第１の位置が前記装置を運ぶ前記人間又は車両により前記出発地ノードから到達されうるかどうかを判定するために、前記第１の位置での前記パラメータの前記推定された値と、前記第１の値とを比較する、
ように配置且つ構成されることを特徴とするシステム。
【請求項１３】
前記目的地ノードの周囲の前記第１のエリアを包含する前記第１の境界を示すデータは、前記メモリの永続メモリ部分に格納されることを特徴とする請求項１１又は１２に記載の装置又はシステム。
【請求項１４】
前記目的地ノードの周囲の前記第１のエリアを包含する前記第１の境界を示すデータは、前記サーバ又は外部サーバから取得されることを特徴とする請求項１１又は１２に記載の装置又はシステム。
【請求項１５】
選択的には継続性のあるコンピュータ可読媒体に格納され、装置又はシステムの少なくとも１つのプロセッサにより実行される場合に、請求項１乃至１０の何れか１項に記載の方法を前記装置又はシステムに実行させるコンピュータ可読命令を含むコンピュータプログラム。
【請求項１６】
移動されうるナビゲート可能ネットワークの量を制限するパラメータの値を所与として、前記ナビゲート可能ネットワーク上の第２の位置が到達されることが可能である間に、前記ナビゲート可能ネットワーク上の第１の位置から到達可能なエリアを表すナビゲート可能ネットワークを含む地理的エリアの一部を包含する第１の境界を判定する方法であって、前記ナビゲート可能ネットワークが、前記ナビゲート可能ネットワークのナビゲート可能要素を表す複数の区分を含む電子地図により表される、前記方法は、
前記第１の位置を表す区分の位置を判定し、前記判定された位置での前記パラメータの前記値を取得することと、
関連するコスト関数を有する検索アルゴリズムを使用して前記第１の位置を表す前記判定された位置から前記電子地図の前記区分を探索することと、探索されて到達可能であると判定された区分について、前記パラメータの前記取得された値よりも小さい前記第１の位置を表す前記判定された位置から最適コスト経路を移動することに起因する前記パラメータの値と関連付けられるのであれば区分は到達可能であり、前記パラメータの前記取得された値と、前記区分と関連付けられた前記パラメータの前記値との差よりも大きい前記パラメータの値と関連付けられた第２の境界内に区分が存在するかどうかを判定することであって、前記第２の境界は、複数の所定の第２の境界のうちの１つであり、各々は前記パラメータの異なる値と関連付けられており、各々は、前記パラメータの前記関連付けられた値を所与としてエリアから前記第２の位置が到達されうる当該エリアを表す前記第２の位置の周囲の前記地理的エリアの一部を包含する、前記判定することと、
前記第１の境界を判定するために前記第２の境界内にあると判定された前記区分を使用することと、
を含むことを特徴とする方法。
【請求項１７】
前記第１の位置は、ユーザ又は移動装置の現在地であることを特徴とする請求項１６に記載の方法。
【請求項１８】
前記第２の位置は、ホーム位置等の所定の位置であることを特徴とする請求項１６又は１７に記載の方法。
【請求項１９】
位置の選択を受信することと、前記選択された位置を前記第２の位置として設定することとをさらに含むことを特徴とする請求項１６乃至１８の何れか１項に記載の方法。
【請求項２０】
前記複数の第２の境界を示すデータはメモリに格納されており、前記方法は、前記第２の境界を示すデータを取得するために前記格納されたデータにアクセスすることをさらに含むことを特徴とする請求項１６乃至１９の何れか１項に記載の方法。
【請求項２１】
前記複数の第２の境界を判定することをさらに含み、前記パラメータの所定値についての第２の境界の前記判定は、
前記第２の位置を示す区分の位置を判定することと、
関連するコスト関数を有する検索アルゴリズムを使用して前記判定された位置から前記電子地図の前記区分を探索することと、探索される区分について、前記パラメータの前記所定値を所与として前記第２の位置を表す前記位置が前記区分から到達可能であるかどうかを判定することと
を含むことを特徴とする請求項１６乃至２０の何れか１項に記載の方法。
【請求項２２】
（ｉ）ディスプレイに、前記第１の境界、又はそれにより包含される前記エリアの少なくともいくつかを表す情報を表示すること、及び（ｉｉ）前記第１の境界、又はそれにより包含される前記エリアの少なくともいくつかを表す情報を表示のために移動装置へ送信すること、のうちの少なくとも１つをさらに含むことを特徴とする請求項１６乃至２１の何れか１項に記載の方法。
【請求項２３】
前記第１の位置での前記パラメータの前記取得された値を所与として、前記第１の位置の周囲の前記地理的エリアの一部を包含し、且つ、前記第１の位置から到達可能なエリアを表す、第３の境界を判定することを特徴とする請求項１６乃至２２の何れか１項に記載の方法。
【請求項２４】
（ｉ）ディスプレイに、前記第３の境界、又はそれにより包含される前記エリアの少なくともいくつかを表す情報を表示すること、及び（ｉｉ）前記第３の境界、又はそれにより包含される前記エリアの少なくともいくつかを表す情報を表示のために移動装置へ送信すること、のうちの少なくとも１つをさらに含むことを特徴とする請求項１６乃至２３の何れか１項に記載の方法。
【請求項２５】
移動されうるナビゲート可能ネットワークの量を制限するパラメータの値を所与として、前記ナビゲート可能ネットワーク上の第２の位置が到達されることが可能である間に、前記ナビゲート可能ネットワーク上の第１の位置から到達可能なエリアを表すナビゲート可能ネットワークを含む地理的エリアの一部を包含する第１の境界を判定するシステムであって、前記ナビゲート可能ネットワークが、前記ナビゲート可能ネットワークのナビゲート可能要素を表す複数の区分を含む電子地図により表される、前記システムは、
前記第１の位置を表す区分の位置を判定し、前記判定された位置での前記パラメータの前記値を取得する手段と、
関連するコスト関数を有する検索アルゴリズムを使用して前記第１の位置を表す前記判定された位置から前記電子地図の前記区分を探索し、探索されて到達可能であると判定された区分について、前記パラメータの前記取得された値よりも小さい前記第１の位置を表す前記判定された位置から最適コスト経路を移動することに起因する前記パラメータの値と関連付けられるのであれば区分は到達可能であり、前記パラメータの前記取得された値と、前記区分と関連付けられた前記パラメータの前記値との差よりも大きい前記パラメータの値と関連付けられた第２の境界内に区分が存在するかどうかを判定する手段であって、前記第２の境界は、複数の所定の第２の境界のうちの１つであり、各々は前記パラメータの異なる値と関連付けられており、各々は、前記パラメータの前記関連付けられた値を所与としてエリアから前記第２の位置が到達されうる当該エリアを表す前記第２の位置の周囲の前記地理的エリアの一部を包含する、前記手段と、
前記第１の境界を判定するために前記第２の境界内にあると判定された前記区分を使用する手段と、
を備えることを特徴とするシステム。
【請求項２６】
選択的には継続性のあるコンピュータ可読媒体に格納され、システムの少なくとも１つのプロセッサにより実行される場合に、請求項１６乃至２４の何れか１項に記載の方法を前記システムに実行させるコンピュータ可読命令を含むコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、出発地ノード及び目的地ノード間を移動する際に移動されてもよいエリアを判定する方法に関するものである。本発明は、当該方法を実施する移動装置、選択的にはポータブルナビゲーションシステム、システム及びコンピュータプログラムにも及ぶ。方法はコンピュータで実施されてもよい。本発明の例示的な実施形態は、ポータブルナビゲーション装置（いわゆるＰＮＤ）に関し、特に、全地球測位システム（ＧＰＳ）信号受信処理機能を含むＰＮＤに関するものである。他の実施形態は、より一般的に、経路計画機能、及び好適にはナビゲーション機能も提供するようにナビゲーションソフトウェアを実行するように構成された任意の種類の移動処理装置に関するものである。
【背景技術】
【０００２】
信号受信機能性及び信号処理機能性を含むポータブルナビゲーション装置（ＰＮＤ）はよく知られており、車載ナビゲーションシステム又は他の車両ナビゲーションシステムとして広く使用されている。
【０００３】
一般に、最近のＰＮＤは、プロセッサ、メモリ（揮発性及び不揮発性のうち少なくとも一方であり、通常は双方）及び前記メモリ内に格納された地図データを備える。プロセッサ及びメモリは協働して、ソフトウェアオペレーティングシステムが確立される実行環境を提供する。更に、ＰＮＤの機能性を制御可能にするため及び種々の他の機能を提供するために１つ以上の追加のソフトウェアプログラムが提供されることは一般的である。
【０００４】
通常、これらの装置は、ユーザが装置と対話し且つ装置を制御できるようにする１つ以上の入力インタフェースと、情報がユーザに中継されるようにする１つ以上の出力インタフェースとを更に備える。出力インタフェースの例は、表示装置及び可聴出力用スピーカを含む。入力インタフェースの例は、装置のオン／オフ動作又は他の特徴を制御するための１つ以上の物理ボタン（これらのボタンは、必ずしも装置自体に存在する必要はなく、装置が車両に組み込まれる場合はステアリングホイール上に存在してもよい）及びユーザの音声を検出するためのマイクを含む。特に好適な構成において、出力インタフェースディスプレイは、ユーザが触れることにより装置を操作できるようにする入力インタフェースを更に提供するためにタッチセンシティブディスプレイとして（例えば、タッチセンシティブオーバレイによって）構成される。
【０００５】
また、この種の装置は、装置との間で電力及びオプションとしてのデータ信号を送受信可能にする１つ以上の物理コネクタインタフェースと、オプションとして、セルラ通信、並びに例えばＷｉ−Ｆｉ及びＷｉ−Ｍａｘ  ＧＳＭなどである他の信号／データネットワークを介する通信を可能にする１つ以上の無線送信機／受信機とを含む場合が多い。
【０００６】
この種のＰＮＤ装置はＧＰＳアンテナを更に含み、これにより、場所データを含む衛星放送信号を受信でき、その後、装置の現在地を判定するために衛星放送信号を処理できる。
【０００７】
ＰＮＤ装置は、現在の角加速度及び直線加速度を判定し、ＧＰＳ信号から導出された場所情報と関連して装置及び装置が搭載されている車両の速度及び相対変位を判定するために処理可能な信号を生成する電子ジャイロスコープ及び加速度計を更に含んでもよい。通常、そのような特徴を車両搭載型のナビゲーションシステムに提供するのが最も一般的であるが、ＰＮＤ装置に提供するのが好都合な場合はＰＮＤ装置に提供する。
【０００８】
そのようなＰＮＤの有用性は、第１の場所（通常は出発地又は現在地）と第２の場所（通常は目的地）との間で経路を判定する機能において主に示される。これらの場所は、装置のユーザにより、種々の異なる方法のうちいずれかで、例えば郵便番号、道路名及び番地、事前に格納された「既知の」目的地（有名な場所、公営の場所（運動場又は水泳プールなど）又は他の関心地点など）により入力可能である。
【０００９】
通常、ＰＮＤは、地図データから出発地の住所の場所と目的地の住所の場所との間の「最善」又は「最適」な経路を計算するためにソフトウェアにより有効化される。「最善」又は「最適」な経路は、所定の基準に基づいて計算され、必ずしも最速又は最短の経路である必要はない。運転者を案内する経路の選択は非常に高度であり、選択される経路は、既存の交通道路情報、予測される交通道路情報、動的な交通道路情報及び／又は無線で受信される交通道路情報、履歴を考慮に入れてもよい。
【００１０】
更に、装置は、道路及び交通状況を継続的に監視し、状況変化によって残る行程で取るべき経路を変更することを提案又は選択してもよい。種々の技術（例えば、移動電話データ交換、固定カメラ、ＧＰＳフリートトラッキング）に基づくリアルタイム交通監視システムが、交通遅滞を識別し且つ通知システムに情報を供給するために使用されている。
【００１１】
この種のＰＮＤは、通常は車両のダッシュボード又はフロントガラスに搭載されるが、車両の無線装置の内蔵コンピュータの一部又は実際は車両自体の制御システムの一部として形成されてもよい。ナビゲーション装置は、ＰＤＡ（ポータブルデジタルアシスタント）メディアプレイヤー又は移動電話などのハンドヘルドシステムの一部であってもよく、その場合、ハンドヘルドシステムの標準的な機能性は、経路の計算及び計算された経路に沿ったナビゲーションの双方を実行するために装置にソフトウェアをインストールすることにより拡張される。
【００１２】
経路計画／ナビゲーション機能性は、適切なソフトウェアを実行するデスクトップ又は移動演算資源により更に提供される。例えば、王立自動車クラブ（ＲＡＣ）は、ｈｔｔｐ：／／ｗｗｗ.ｒａｃ.ｃｏ.ｕｋでオンライン経路計画／ナビゲーション機能性を提供するが、この機能を使用することにより、ユーザは、出発地及び目的地を入力でき、その後、ユーザのＰＣと接続されているサーバが経路（経路のアスペクトはユーザにより指定される）を計算し、地図を生成し、選択された出発地から選択された目的地までユーザを案内するための徹底したナビゲーション命令のセットを生成する。この機能は、更に、計算された経路を疑似３次元レンダリングし、その経路に沿って進むユーザをシミュレートする経路プレビュー機能性を提供し、それにより、計算された経路のプレビューをユーザに提供する。
【００１３】
ＰＮＤの場合、経路が計算されると、ユーザは、ナビゲーション装置と対話し、オプションとして、提案された経路のリストから所望の計算された経路を選択する。オプションとして、ユーザは、例えば、ある特定の行程に関して特定の経路、道路、場所又は基準が回避されるべきであるか又は必須であると指定することにより、経路選択処理を仲介又は誘導する。ＰＮＤの経路計算の面は１つの主要な機能を形成し、そのような経路に沿ったナビゲーションは別の主要な機能である。
【００１４】
計算された経路に沿ったナビゲーション中、そのようなＰＮＤが、選択された経路に沿ってその経路の終点、すなわち所望の目的地にユーザを案内するための視覚命令及び／又は可聴命令を提供することは一般的である。また、ＰＮＤがナビゲーション中に地図情報を画面上に表示することも一般的であり、そのような情報は、表示される地図情報が装置の現在地を示し、従って、装置が車両ナビゲーションに使用されている場合にユーザ又はユーザの車両の現在地を示すように、画面上で定期的に更新される。
【００１５】
画面上に表示されるアイコンは、通常は装置の現在地を示し、装置の現在地の近傍の現在の道路及び周辺の道路の地図情報、並びに同様に表示されている他の地図特徴と共に中央に配置される。更に、ナビゲーション情報は、オプションとして、表示された地図情報の上方、下方又は片側のステータスバーに表示される。ナビゲーション情報の例は、ユーザが走行する必要のある現在の道路から次の進路変更までの距離を含み、その進路変更の特性は、例えば左折又は右折である特定の種類の進路変更を示す更なるアイコンにより示される。ナビゲーション機能は、経路に沿ってユーザを案内する可聴命令の内容、継続時間及びタイミングを更に判定する。理解されるように、「１００ｍ先で左折」などの単純な命令は、膨大な処理及び解析を必要とする。上述のように、ユーザと装置との対話はタッチスクリーンにより行われてもよく、それに加えて又はその代わりに、ステアリングコラムリモコン、音声起動又は他の何らかの適切な方法により行われてもよい。
【００１６】
装置により提供される更なる重要な機能は、ユーザがナビゲーション中に事前に計算された経路から外れる（誤って又は故意に）場合、別の経路がより適切であるとリアルタイムの交通状況が示し且つ装置がそのような状況を適切に自動認識できる場合、あるいはユーザが何らかの理由で能動的に装置に経路の再計算を実行させる場合における自動経路再計算である。
【００１７】
経路計算機能及びナビゲーション機能はＰＮＤの総合的な実用性の基本になるものであるが、装置を単に情報表示、すなわち「フリードライビング」のために使用することが可能である。この場合、装置の現在地に関連する地図情報のみが表示され、経路は計算されておらず、ナビゲーションは現時点で装置により実行されていない。そのような動作モードは、ユーザが走行するのが望ましい経路を既に認識しており且つナビゲーション支援を必要としない場合に適用可能であることが多い。
【００１８】
以上説明した種類の装置は、ユーザを１つの位置から別の位置へナビゲートすることを可能にする信頼性の高い手段を提供する。
【００１９】
ナビゲーションユーザは、特定の制約を所与として車両でどのくらい遠くまで移動できるかにしばしば関心があるかもしれない。例えば、ユーザにとって、従来の燃焼エンジン車両の場合、ガソリン、ディーゼル等の現在の燃料量に基づいて、或いは、次第に増えている電動車両（ＥＶ）の場合、車両バッテリにより運ばれる電荷電流の量に基づいてどのくらい遠くまで移動できるかを知ることは重要である。そのような関心は一般に“走行距離不安症”と称され、ユーザは、立ち往生することなくホーム位置又は充電地点等の目的地へ到達することに関心がある。
【００２０】
簡略化して、現在の車両位置及び燃料量に基づく３６０度方向の到達可能範囲が、地図上にユーザに対して表示されうる。例えば、欧州特許出願公開第０６３８８８７号明細書は、任意の量の残存燃料について到達可能な範囲を算出し且つ表示する１つの方法を記載している。ナビゲーション装置の経路計画嗜好も考慮する改良方法が、国際公開２０１４／００１５６５号に記載されている。欧州特許出願公開第１９２６０７４号明細書は、特定の基準地点、すなわちユーザ車両の現在位置からアクセス可能な任意の地点までの移動時間に関する移動時間情報を算出する検索手段を含む地図表示装置を開示している。
【００２１】
しかしながら、これらの方法は、装置から現在到達可能なエリアに関する情報を表示するだけであり、ユーザが現在の燃料量又は他の制約を所与として地図上の所与の区分に到達し、次に所望の目的地にさらに到達することができるかどうかに関する情報を提供するものではない。これは、現在の燃料量又は他の制約を所与とした装置の現在地と所望の目的地との間の“安全な戻り範囲”と称されるかもしれない。
【００２２】
理想的には、車両から現在到達可能な範囲、及び、目的地がさらに到達されうる安全な戻り範囲の両方が、両方の範囲が共にユーザに対して表示されるように、或いは、少なくとも両方がユーザへの分離表示に即座に利用可能であるように、同時に維持されるだろう。しかしながら、残念ながら、所与の地点から到達されうるエリアを判定することは、本質的に計算コストが高い。安全な戻り範囲を算出することは、地図領域内の大多数の位置、例えば現在到達可能な範囲内の全ての可能な位置、について到達可能なエリアを判定することを含んでもよく、それははるかに計算コストが高い。従って、従来の技術を使用して現在到達可能なエリア及び安全な戻り範囲の両方の計算に必要な労力を費やすことは一般に実現可能なことではない。これは特に、運転者のスマートフォン等の制限された処理能力の移動装置に当てはまる。
【００２３】
それ故、本発明は、いわゆる“走行距離不安症”を低減するための改良された方法及びシステムを提供することを目的とする。
【発明の概要】
【００２４】
本発明の第１の態様によれば、出発地ノード及び目的地ノードの間を移動する際に移動されてもよいエリアを判定する方法であって、
第１の値のパラメータを所与として人間又は車両が前記目的地ノードまで移動してもよい複数の位置を表す前記目的地ノードの周囲の第１のエリアを包含する第１の境界を示すデータを判定又は取得することであって、前記パラメータの前記値は、前記人間又は車両により移動可能な距離を制約する、前記判定又は取得することと、
前記出発地ノード及び前記目的地ノード以外の、前記第１の境界内の第１の位置に前記人間又は車両がいる場合の前記パラメータの値を、前記出発地ノードでの前記パラメータの初期値と、前記出発地ノードから前記第１の位置までの移動と関連付けられた前記パラメータの値の推定される変化とに基づいて、推定することと、
前記パラメータの前記初期値を所与として、前記目的地ノードに到達するまでの間に、前記第１の位置が前記人間又は車両により前記出発地ノードから到達されうるかどうかを判定するために、前記第１の位置での前記パラメータの前記推定された値と、前記第１の値とを比較することと、
を含むことを特徴とする方法が提供される。
【００２５】
実施形態は、その値が前記人間又は車両により移動可能な距離を制約するいくつかのパラメータの前記出発地ノードでの前記初期値を所与として、前記目的地ノードに到達するまでの間に任意の特定の位置が出発地ノードから到達されうるかどうかの判定を可能にする。それ故、これらの位置全体は、前記目的地ノードに到達するまでの間に前記人間又は車両が移動しうるエリアを表し、そのためこの判定はユーザの走行距離不安症を低減するのを助けることができる。
【００２６】
さらに、重要なことに、この判定は、所与の位置（例えば前記第１の位置）での前記出発地ノードから当該位置までの移動後の前記パラメータの前記予期される値と、前記第１の位置が範囲内の前記境界と関連付けられた前記パラメータの前記値との間の比較的単純な比較を通じた比較的少ない計算オーバーヘッドで行われうる。例えば、前記第１の位置での前記パラメータの前記予期される値が、前記目的地ノードが前記第１の位置から到達されうると判定されるものであるなら、前記第１の位置は前記目的地ノードの安全な戻り範囲内にある。一例として、前記パラメータが電動車両の充電レベルである場合、前記第１の境界内にある前記第１の位置での前記予期される残りの充電レベルが５０％であり、且つ、前記第１の境界が、１０％の充電のみが前記目的地ノードに到達するのに必要とされることを表すなら、前記第１の位置は、前記目的地ノードに到達するまでの間に前記出発地ノードから到達可能であると判定されるだろう。前記目的地ノードの周囲の前記第１のエリアは前記パラメータの特定値と関連付けられて予め判定される（すなわち、前記方法の初期ステップで判定又は取得される）ので、前記第１の位置が前記第１のエリア内にあるかどうかをチェックし、上記の２つの値を比較することのみが必要である。従って、前記第１の位置が、前記パラメータの前記初期値を所与として前記目的地ノードに到達するまでの間に前記出発地ノードから到達されうるかどうかの判定は、前記第１の位置からの前記到達可能なエリアを別途計算する必要無しに、この比較を通じて直接判定されてもよいことが理解されるだろう。これは、前記パラメータの前記初期値を所与として、前記目的地ノードに到達するまでの間に前記出発地ノードから他の位置が到達されうるかどうかを判定するために前記方法が繰り返される場合に特に、前記方法の前記計算オーバーヘッドを低減する。
【００２７】
従って、前記パラメータの前記初期値を所与として前記目的地ノードに到達するまでの間に前記出発地ノードから到達されてもよい前記複数の位置を含む前記安全な戻り範囲は、比較的限定された処理能力の移動装置上で実施されてもよい方法で比較的単純に判定されてもよい。
【００２８】
本明細書で使用される用語“安全な戻り範囲”は、前記パラメータの前記初期値を所与として前記目的地ノードに到達するまでの間に前記出発地ノードから到達されうる複数位置の範囲を参照することが理解されるだろう。
【００２９】
前記パラメータの前記値は、特定の開始位置から前記人間又は車両により移動可能な距離を制約する。それ故、前記第１の境界は、前記パラメータの前記第１の値を所与として前記人間又は車両が前記目的地ノードへ移動してもよい最大限到達可能な地点を表す。同様に、以下で言及される前記目的地ノードの周囲の前記複数の異なる境界は、前記複数の境界の各々と関連付けられた前記パラメータのそれぞれの値を所与として前記人間又は車両が前記目的地ノードへ移動してもよい最大限到達可能な地点を表す。前記出発地ノードの周囲の特定の境界は、一般に前記目的地ノードの周囲の複数の地点を使用して構成されてもよく、それら地点は前記境界の形状を規定するために相互接続されている。例えば前記境界が特定のノードからの任意の距離で判定されるのみである場合、境界は前記目的地ノードを囲む完全な連続境界である必要はないことが理解されるだろう。判定がリアルタイムに行われている場合、前記パラメータの前記初期値又は前記出発地ノードの変化が起こる前に前記境界の全範囲を判定することは実践的ではないかもしれないことも理解されるだろう。
【００３０】
一般に、移動可能な距離は１つ以上のパラメータにより制約されてもよく、それ故、前記方法は、１より多いパラメータを考慮してもよいことが熟考される。しかしながら、通常、単一の制約パラメータのみが考慮されるだろう。
【００３１】
一般に、前記方法は、デジタル地図データに基づいて出発地ノード及び目的地ノードの間を移動する際、内部を移動されてもよいエリアを判定する方法に関してもよく、前記デジタル地図データは、ネットワークのナビゲート可能なパスを表すノードにより接続された複数のリンクを含む。それ故、前記出発地ノード、目的地ノード及び第１の位置は各々、前記ネットワーク内のそれぞれのリンク又はノードを含んでもよい。それ故、ノードの周囲の前記境界及びエリアは、単純に前記ネットワーク内の多数のリンク又はノードを含んでもよい。
【００３２】
本明細書に記載される、移動可能な距離を制約するパラメータの特定の値と関連付けられた所与のノードの周囲の境界は、一般に、前記パラメータの前記特定の値に基づいて前記ノードから（又は前記ノードへ）移動可能な距離を判定する任意の適当な方法を使用して判定されてもよい。例えば、実施形態において、前記境界は、前記パラメータの前記それぞれの値、および、前記人間又は車両と関連付けられた前記ナビゲーション装置の経路計画嗜好を考慮する経路計画アルゴリズムに基づいて判定されてもよいことが熟考される。前記経路計画アルゴリズムは、前記パラメータの前記第１の値を所与として前記ノードと、人間又は車両が前記ノードへ移動してもよい任意の特定の位置との間の、最短経路、最速経路、又は最も燃料又はエネルギー効率の良い経路を優先的に選択するために、例えば、特定のノードの周囲に延びる経路を規定する複数のリンクの各々と関連付けられた長さ、移動時間及び／又は移動速度等の経路計画関数を考慮してもよい。一般的には、前記アルゴリズムは、１対多の検索アルゴリズムを使用して前記目的地ノードの周囲のリンクを探索するだろう。前記目的地ノードと、ある位置との間の任意の所与の経路について、前記経路に沿った前記リンクの各々は、前記経路が前記パラメータの観点で及び選択的には経路計画関数の観点で累積値又は累積コストを有するように、前記パラメータの観点で及び選択的には経路計画関数の観点で任意の値又はコストを割り当てられるだろう。従って、前記パラメータの任意の値と関連付けられた境界は、前記パラメータの累積コスト又は累積値が当該値と一致する経路の端点により判定されてもよい。通常、前記到達可能なエリア又は境界を判定するために使用される前記アルゴリズムは、前記目的地により近いリンクを遠方のリンクよりもより詳細に探索してもよい。
【００３３】
前記第１の境界及び／又は前記複数の境界は、前記方法の最初のステップとして判定されてもよく、或いは予め判定されてもよく、（例えば、前記方法を実施する装置の永続メモリから、或いは、外部サーバから）前記境界を示すデータが取得されて、後続の比較のステップで使用される。前記目的地ノードは通常は固定地点であるので、前記目的地ノードの周囲の前記到達可能なエリアは、時間と共に劇的に変化する傾向は無いことが理解されるだろう。前記目的地ノードの周囲の前記判定された到達可能なエリア又は境界は、前記地図領域を通じた多数の異なる移動例について、再使用されうるか、或いは、少なくとも比較的少ない計算オーバーヘッドで再判定されうる。
【００３４】
前記目的地ノードは通常、例えば、ホーム位置、又はいくつかの他の予め決定された位置に対応する前記地図上の固定位置である。例えば、前記パラメータが車両の燃料量又は電動車両の充電レベルである場合、前記目的地ノードは、特定の燃料補給地点又は再充電地点を含んでもよい。前記目的地ノードの前記位置は通常は固定なので、前記目的地ノードの周囲の前記到達可能なエリアは、時間と共に比較的一定になることが予期されてもよいことが理解されるだろう。
【００３５】
多数の固定の目的地ノードが存在してもよく、前記方法は、これらの何れか又は全てへの前記安全な戻り範囲を判定してもよいことも熟考される。例えば、前記方法は、ある目的ノードの安全な戻り範囲から出て、別の目的地ノードの安全な戻り範囲に入ることに応じてリアルタイムに使用されている前記目的地ノードを変更してもよい。或いは、異なる目的地ノードと関連付けられた前記安全な戻り範囲は、例えば地図上で異なる色を使用して共に視覚化されてもよい。
【００３６】
前記第１の位置は、一般に、前記出発地ノードから前記現在到達可能なエリア内の位置である。前記第１の位置は、前記目的地ノードの周囲の到達可能なエリア（すなわち前記第１の境界内の、前記第１のエリア）内の位置でもある。前記目的地ノードの到達可能なエリア又は境界内にない前記出発地ノードから前記現在到達可能なエリア内の他の位置については、前記目的地ノードへ安全に戻ることが可能ではなく、そのため、これらは常に前記安全な戻り範囲は外にあるだろう。
【００３７】
前記方法は、一般に、移動ナビゲーション装置、又は、当該移動ナビゲーション装置が取り付けられる車両について、出発地ノード及び目的地ノードの間を移動する際に、内部を移動されてもよいエリアを判定する方法であってもよい。前記装置は、例えば背景技術の欄で上記された種類のポータブルナビゲーション装置（ＰＮＤ）であってもよい。
【００３８】
例えば、前記第１の位置での前記パラメータの前記値は、前記第１の位置での前記パラメータの予期される値の推定に過ぎないこと、そして、例えば、前記交通条件の変化が前記推定値からの逸脱をもたらすかもしれないことが理解されるだろう。従って、前記方法は、人間又は車両により移動可能な距離を制約するパラメータの初期値を所与として出発地ノード及び目的地ノードの間を移動する際に内部を移動されてもよいエリアを近似する方法であることが考慮されてもよい。
【００３９】
実施形態において、前記方法は、前記目的地ノードの周囲の複数の異なる境界を示すデータを判定又は取得することであって、各異なる境界は前記パラメータの異なるそれぞれの値と関連付けられており、前記異なる境界は当該境界と関連付けられた前記パラメータの前記値を所与として人間又は車両が前記目的地ノードへ移動してもよい前記位置を表す前記目的地ノードの周囲のエリアを包含する、前記判定又は取得することを含み、前記方法は、前記第１の位置が存在する２つの隣接する前記境界間を判定することと、前記出発地ノードから前記人間又は車両により前記第１の位置が到達されうるかどうかを判定するために、前記第１の位置での前記パラメータの前記推定される値と、前記２つの境界のうち外側境界及び／又は内側境界と関連付けられた前記パラメータの前記値とを比較することと、をさらに含む。
【００４０】
通常、前記第１の位置での前記パラメータの前記推定される値と、前記第１の位置が存在する前記２つの境界のうちの外側境界と関連付けられた前記パラメータの前記値との間で、前記比較が行われる。従って、前記内側境界は、どの外側境界を比較に使用すべきかを識別する働きだけをする。しかしながら、前記比較は、前記第１の位置が存在する前記２つの境界のうちの前記内側境界と関連付けられた前記パラメータの前記値に、或いは、更に基づいてもよいことが理解されるだろう。前記外側境界は、前記目的地ノードから最も遠い境界である。
【００４１】
各境界が前記目的地ノードから移動可能な次第に増加する距離を表すように、各境界は次第に増加する前記パラメータの値と関連付けられてもよい。例えば、前記境界は、前記目的地ノードの周囲に同心円状に構成されてもよい。しかしながら、どのように前記パラメータが規定されるかに依存して、各境界が前記目的地ノードから移動可能な次第に増加する距離を表すように、各境界は次第に減少する前記パラメータの値と関連付けられてもよいことが理解されるだろう。
【００４２】
前記複数の境界は、一般に、隣接境界が前記目的地ノードの周囲の一連のリング状エリアを規定するように、前記目的地ノードへの一連の次第に増加する移動可能な距離を表す。従って、前記方法は、何れの前記リング状エリアに特定の位置が内部に存在するかを判定することと、当該位置での前記パラメータの前記予期される値と、当該リング状エリアと関連付けられた前記パラメータの値とを比較することとを含んでもよい。隣接するリング状エリアは、前記パラメータの隣接する範囲又は値に対応する移動可能な距離の範囲と関連付けられてもよい。すなわち、各リング状エリアは、前記パラメータの前記値の変化と関連付けられた更なる到達可能な範囲を表す。例えば、前記パラメータの第１の値と関連付けられた内部境界と、前記パラメータの第２の値と関連付けられた外部境界との間の前記リング状エリアは、前記第１の値より小さい（又は等しい）値から前記第１の値と前記第２の値との間の値まで前記パラメータの前記値を変更することと関連付けられた更なる移動可能な距離を表す。
【００４３】
実施形態において、前記方法は、
前記人間又は車両が、前記出発地ノード及び前記目的地ノード及び前記第１の位置以外の、前記第１の境界内における及び／又は前記複数の境界のうちの隣接する２つの間における第２の位置にいる場合の前記パラメータの値を、前記出発地ノードでの前記パラメータの初期値と、前記出発地ノードから前記第２の位置までの移動と関連付けられた前記パラメータの値の前記推定される変化とに基づいて、推定することと、
前記パラメータの前記初期値を所与として、前記目的地ノードに到達するまでの間に前記人間又は車両により前記出発地ノードから前記第２の位置が到達されうるかどうかを判定するために、前記第２の位置での前記パラメータの前記推定される値を、前記第１の値と、及び／又は、前記２つの境界のうち外側境界及び／又は内側境界と関連付けられた前記パラメータの前記値と、比較することと
をさらに含む。
【００４４】
前記第２の位置は、前記第１の境界により囲まれた前記第１のエリア内にあってもよく、或いは、前記複数の境界のうちの隣接する２つの間に規定された種々のエリア内にあってもよい。従って、前記方法は、前記パラメータの前記初期値を所与として、前記目的地ノードに到達するまでの間に前記人間又は車両により前記出発地ノードから前記第２の位置が到達されうるかどうかを判定するために、前記第２の位置での前記パラメータの前記推定される値を、それが存在する前記エリアと関連付けられた前記パラメータの前記値と比較することを含んでもよい。
【００４５】
前記方法は、前記第１の境界内における及び／又は前記複数の境界のうちの隣接する２つの間における（前記出発地ノード及び目的地ノード及び前記第１の位置及び第２の位置以外の）第３の位置又は更なる位置に前記人間又は車両がいる場合に、前記出発地ノードでの前記パラメータの初期値と、前記出発地ノードから前記第３の位置又は更なる位置までの移動と関連付けられた前記パラメータの値の前記推定される変化とに基づいて、前記パラメータの値を推定することと、前記パラメータの前記初期値を所与として、前記目的地ノードに到達するまでの間に前記人間又は車両により前記出発地ノードから前記第３の位置又は更なる位置が到達されうるかどうかを判定するために、前記第３の位置又は更なる位置での前記パラメータの前記推定される値を、前記第１の境界と関連付けられた、及び／又は、前記２つの境界のうち前記外側境界及び／又は前記内側境界と関連付けられた、前記パラメータの前記値と比較することとを含んでもよい。
【００４６】
前記方法は、前記パラメータの値を推定するステップと、複数の位置の各々での上記の前記パラメータの前記推定される値を比較するステップとを含んでもよい。
【００４７】
前記方法は通常、前記第１の位置及び第２の位置、或いは、前記第１の位置、第２の位置、第３の位置及び更なる位置が、同一の出発地ノードから、すなわち前記出発地ノードが単一の固定位置である場合に、前記人間又は車両により到達されうるかどうかを判定することを含む。これは、例えば以下でより詳細に議論されるように、前記出発地ノードが移動する又は更新されるにつれて、異なる出発地ノードの前記（又は異なる）第１の位置、第２の位置、第３の位置及び／又は更なる位置について繰り返されてもよい。
【００４８】
実施形態において、前記方法は、
前記パラメータの前記初期値に基づいて前記人間又は車両が前記出発地ノードから移動してもよい前記位置を表す前記出発地ノードの周囲のエリアを判定することと、
前記第１の境界、及び／又は、前記複数の異なる境界の少なくともいくつかを使用して、前記出発地ノードの周囲の前記エリア内の複数の前記位置の各々について、前記目的地ノードに到達するまでの間に前記複数の位置の各々が到達されうるかどうかを判定することと
を含む。
【００４９】
前記パラメータの前記初期値に基づいて前記人間又は車両が前記出発地ノードから移動してもよい前記位置を表す前記出発地ノードの周囲の前記エリアは、例えば前記出発地ノードの周囲の現在到達可能なエリアを判定する任意の適当な方法を使用して判定されてもよい。例えば、前記パラメータの前記初期値に基づく前記現在到達可能なエリアは、前記目的地ノードの周囲の前記１又は複数の境界を判定するために使用されたのと同一の方法を使用して判定されてもよい。
【００５０】
前記複数の位の各々について、前記目的地ノードの到達可能なエリア又は境界内に前記位置が存在するか否かが最初に判定されてもよい。
【００５１】
特定の位置が、前記目的地ノードへの最も遠い到達可能なエリアの外側（すなわち前記パラメータの最大値（又は最小値）と関連付けられた前記境界の外側）にあるなら、当該位置は、前記目的地ノードに到達するまでの間に前記出発地ノードから決して到達されることはない。前記目的地への前記最も遠い到達可能なエリアの外側にある位置は無視されてもよく、或いは、解析には含まれてもよいが、前記パラメータの前記現在値を所与として、それらが常に到達可能ではないと判定されるように、例えば効率的に前記パラメータの無限の値と比較されてもよい。
【００５２】
しかしながら、前記目的地ノードの到達可能なエリア又は境界内にある（すなわち、前記第１の境界内の及び／又は前記複数の境界の１つ以上内の）位置について、前記目的地ノードにさらに到達することが可能であるか否かを判定するために、前記位置での前記パラメータの前記値が、前記位置がある前記目的地ノードの周囲の前記エリアと関連付けられた前記パラメータの前記値と比較されるように、前記方法が上記のように進行してもよい。
【００５３】
前記パラメータの前記初期値に基づいて前記出発地ノードから前記人間又は車両が移動してもよい前記位置を表す前記出発地ノードの周囲の前記エリアは、本来、前記出発地ノードから前記現在到達可能なエリアを表すことが理解されるだろう。従って、前記実施形態は、前記目的地ノードに対する前記安全な戻り範囲が、前記計算量の著しい増加無しに前記現在到達可能なエリアの前記判定に基づいて直接計算されることを可能にする。
【００５４】
前記パラメータの前記初期値に基づいて前記人間又は車両が前記出発地ノードから移動してもよい前記位置を表す前記出発地ノードの周囲の前記エリアは、前記出発地ノード及び前記目的地ノードを含む前記地図の前記領域内の現在の又は最新野交通条件を反映した、ライブ位置データ、例えばライブＧＰＳデータを使用して判定されてもよい。
【００５５】
実施形態において、前記方法は、選択的にリアルタイムに、前記パラメータの前記初期値に基づいて、前記目的地ノードに到達するまでの間に前記出発地ノードから到達されうる前記出発地ノード及び前記目的地ノードの間の位置を含む、エリアの地図データを作成すること、且つ／又は、エリアを表示するために前記方法を使用することをさらに含む。
【００５６】
前記作成された地図データは、例えば表示のために当該情報をユーザが選択することに応じて、例えばユーザへの後続の表示のために維持されてもよい。前記パラメータの前記初期値に基づいて前記目的地ノードに到達するまでの間に前記出発地ノードから到達されうる前記出発地ノード及び前記目的地ノードの間の位置を含む前記エリアを表示することによって、前記ユーザは、前記目的地ノードに到達するまでの間に到達されうる前記エリアの視覚近似を提供され、従って、運転者の走行距離不安症を低減するのに役立つ。前記エリアは、任意の適当な方法で視覚化されて表示されてもよい。一般に、前記エリアは、複数の離散的な地点により規定されるだろう。これらの地点のいくつかは前記エリアを形作るために相互接続される。
【００５７】
前記出発地ノード及び前記パラメータの前記初期値は時間と共に変化してもよく、その場合、前記方法は、前記安全な戻り範囲が継続的に再判定されるように継続的に実行されてもよい。それ故、表示されるべき前記エリアは、前記出発地ノード及び／又は延期パラメータの初期値が変化するにつれてリアルタイムに変化してもよい。
【００５８】
実施形態において、前記方法は、前記パラメータの前記初期値に基づいて前記人間又は車両が前記出発地ノードから移動してもよい範囲を表す前記出発地ノードの地図データを作成すること、且つ／又は、当該出発地ノードの周囲の前記又はあるエリアを表示することを含む。
【００５９】
前記範囲は、前記出発地ノードの周囲の前記現在到達可能なエリアに対応してもよい。選択的に、この範囲の前記地図データ、又はこの範囲は、リアルタイムに表示されてもよい。前記出発地ノードから前記現在到達可能なエリア及び前記目的地ノードへの前記安全な戻りエリアは、表示のために同時に利用可能であってもよく、或いは同時に表示されてもよい。
【００６０】
実施形態において、前記出発地ノードは、前記人間又は車両の現在地であり、前記初期値は前記パラメータの現在の値である。
【００６１】
前記方法は、前記現在地及び前記パラメータの現在の値が変化するにつれてリアルタイムに、前記第１の位置での前記パラメータの前記値を推定するステップと、前記第１の位置での前記パラメータの前記推定された値と、前記第１の値とを比較するステップとを繰り返すことを含んでもよい。
【００６２】
前記人間又は車両の前記現在地は、前記人間又は車両が前記地図領域の環境内を移動するにつれて継続的に又は定期的に更新される、例えばＧＰＳにより提供される、ライブ位置データから判定されてもよい。
【００６３】
前記パラメータの前記値を推定するステップ及び前記パラメータの前記推定された値を比較するステップは、前記又はある第２の位置又は更なる位置で繰り返されてもよく、前記第２の位置又は更なる位置での前記パラメータの前記推定される値は、前記第２の位置又は更なる位置がある前記エリア又は境界と関連付けられた前記パラメータの前記値と比較される。
【００６４】
実施形態において、（ｉ）前記パラメータは、燃料量又は充電レベルであってもよく、且つ／又は、（ｉｉ）前記パラメータは、移動時間又は移動距離を表してもよく、且つ／又は、（ｉｉｉ）前記パラメータの前記第１の値は、前記第１の境界から前記目的地ノードまでの移動時間又は移動距離であってもよく、前記パラメータの前記初期値は、所望の又は最大の移動時間又は移動距離であってもよく、前記第１の位置での前記パラメータの前記推定された値は、前記出発地ノードから前記第１の位置までの移動後の推定された残りの移動時間又は移動距離であってもよい。
【００６５】
例えば、前記パラメータが移動時間である場合、前記制約は、所望の最大移動時間又は前記目的地ノードへの所望の到着時間であってもよい。同様に、前記パラメータが移動距離である場合、前記制約は、所望の最大移動距離であってもよい。前記パラメータが燃料量又は電気的な充電レベルである場合、前記制約は、前記燃料量又は電気的な充電レベルの初期値又は現在値であってもよい。
【００６６】
前記パラメータの前記値は、前記人間又は車両が、前記出発地ノードから前記目的地ノードまで移動するにつれて、本来、時間と共に増加せずに次第に減少（或いは減少せずに次第に増加）してもよい。前記方法は、例えば専用の燃料補給地点又は再充電地点で前記車両に燃料を補給する或いは前記車両を再充電するステップ無しに、前記目的地ノードへ到達するまでの間に特定の位置が前記人間又は車両により前記出発地ノードから到達されうるかどうかを判定してもよい。
【００６７】
前記目的地ノードは固定位置であってもよく、且つ／又は、前記目的地ノードの周囲の１又は複数の境界は、格納データ又は履歴データを使用して判定されてもよいし、或いは、それらから取得されてもよい。
【００６８】
前記第１の境界及び／又は前記目的地ノードの周囲の前記複数の境界が、時間と共に著しく変化しないことが予期されるように、前記目的地ノードは前記地図上の固定位置であってもよい。従って、前記境界は、格納データ又は履歴データを使用して判定されてもよく、或いは、それらから取得されてもよく、これは、前記安全な戻り範囲の良好な近似をさらに提供してもよい。前記格納データ又は履歴データは、例えば前記方法の多数の異なるパフォーマンスに対応する或いは前記地図領域内の多数の異なる移動に対応する拡張された期間に渡って、再使用又は複数回使用されてもよい。
【００６９】
前記目的地ノード及び当該目的地ノードの周囲の前記境界の前記位置は、前記方法が完了し、及び／又は、前記移動装置が電源をオフにされた後であっても、このデータが後続の使用のために保持されるように、例えば移動装置の永続メモリに半永久的に格納されてもよい。
【００７０】
別の態様から、出発地ノードと目的地ノードとの間をナビゲートする、選択的にはナビゲーション装置である移動装置であって、
メモリと、
プロセッサとを備え、前記プロセッサは、
第１の値のパラメータを所与として前記装置を運ぶ人間又は車両が前記目的地ノードまで移動してもよい複数の位置を表す前記目的地ノードの周囲の第１のエリアを包含する第１の境界を示すデータを判定又は取得し、ここで前記パラメータの前記値は、前記装置を運ぶ前記人間又は車両により移動可能な距離を制約し、
前記出発地ノード及び前記目的地ノード以外の、前記第１の境界内の第１の位置に前記装置を運ぶ前記人間又は車両がいる場合の前記パラメータの値を、前記出発地ノードでの前記パラメータの初期値と、前記出発地ノードから前記第１の位置までの移動と関連付けられた前記パラメータの値の推定される変化とに基づいて、推定し、
前記パラメータの前記初期値を所与として、前記目的地ノードに到達するまでの間に、前記第１の位置が前記装置を運ぶ前記人間又は車両により前記出発地ノードから到達されうるかどうかを判定するために、前記第１の位置での前記パラメータの前記推定された値と、前記第１の値とを比較する、
ように構成される移動装置が提供される。
【００７１】
更なる態様から、出発地ノード及び目的地ノード間をナビゲートするシステムであって、
メモリ及びプロセッサを有する移動装置と、
サーバとを備え、前記移動装置は前記サーバと通信するように構成されており、
前記サーバ及び／又は前記プロセッサは、
第１の値のパラメータを所与として前記装置を運ぶ人間又は車両が前記目的地ノードまで移動してもよい複数の位置を表す前記目的地ノードの周囲の第１のエリアを包含する第１の境界を示すデータを判定又は取得し、ここで前記パラメータの前記値は、前記装置を運ぶ前記人間又は車両により移動可能な距離を制約し、
前記出発地ノード及び前記目的地ノード以外の、前記第１の境界内の第１の位置に前記装置を運ぶ前記人間又は車両がいる場合の前記パラメータの値を、前記出発地ノードでの前記パラメータの初期値と、前記出発地ノードから前記第１の位置までの移動と関連付けられた前記パラメータの値の推定される変化とに基づいて、推定し、
前記パラメータの前記初期値を所与として、前記目的地ノードに到達するまでの間に、前記第１の位置が前記装置を運ぶ前記人間又は車両により前記出発地ノードから到達されうるかどうかを判定するために、前記第１の位置での前記パラメータの前記推定された値と、前記第１の値とを比較する、
ように配置且つ構成されるシステムが提供される。
【００７２】
前記移動装置は、例えば、適切なソフトウェアを動作するユーザのスマートフォン又はスマートウォッチであってもよい。或いは、前記移動装置は、例えば上記背景技術の欄に記載した特徴の何れかを有する専用のポータブルナビゲーション装置であってもよい。一般的には、前記移動装置は、ＧＰＳ機能性を有し、前記移動装置を囲む前記領域に関するライブデータにアクセスするだろう。このライブデータは、外部サーバからの無線接続を介して前記移動装置へ通信されてもよい。通常、前記移動装置は、前記安全な戻り範囲が前記ユーザに対して視覚化されて表示されてもよいようにディスプレイを有するだろう。
【００７３】
前記プロセッサは上記の機能性を提供するように配置且つ構成されてもよく、前記サーバは単に、これらのステップを実行する際に前記プロセッサによる使用のために情報又はデータを提供する。例えば、前記サーバは、前記パラメータの前記値を推定するために使用されてもよい現在の地図条件を表すライブデータを提供してもよい。他の実施形態では、前記記載された機能性のいくつか又は全てが前記サーバで提供されてもよく、結果又は当該結果を示すデータは、例えば前記プロセッサによる後続の使用のために及び／又は前記ユーザへの後続の表示のために移動装置へ通信される。前記サーバ及びプロセッサは、前記記載された機能性を提供するように協働するように配置且つ構成されてもよいことも熟考される。
【００７４】
前記プロセッサ及び／又はサーバは、前記第１の態様に関して上記された前記方法のステップの何れか又は全てを、少なくともそれらが相互に排他的ではない程度に、実行するように配置且つ構成されてもよく、或いはそれらを更に実行するように構成されてもよい。再び、これらのステップは、前記移動装置の前記プロセッサにより直接実行されてもよく、或いは、前記方法のステップは、前記サーバにより実行されてもよく、その結果又は当該結果を示すデータは、例えば前記ユーザへの後の表示のために前記移動装置へ通信される。
【００７５】
実施形態において、前記目的地ノードの周囲の前記第１のエリアを包含する前記第１の境界を示すデータは、前記メモリの永続メモリ部分に格納されてもよい。
【００７６】
他の実施形態において、前記目的地ノードの周囲の前記第１のエリアを包含する前記第１の境界を示すデータは、前記サーバ又は外部サーバから取得されてもよい。
【００７７】
前記目的地ノードの周囲の複数の境界が使用される場合、前記複数の境界の各々を示すデータは、前記メモリの永続メモリ部分に格納されてもよいか、或いは、前記サーバから又は外部サーバから取得されてもよいことが理解されるだろう。
【００７８】
もっと更なる態様から、実質的に上記のような方法を含む、出発地ノード及び目的地ノードの間を移動する際に内部を移動されてもよいエリアを判定するコンピュータ実施方法が提供される。
【００７９】
別の態様から、コンピュータ実施される場合に、前記コンピュータに、実質的に上記のような方法を実行させるコンピュータ可読命令を含むコンピュータプログラム製品が提供される。
【００８０】
上記のような本発明の態様及び実施形態は、以下のように、更に又は代替的に記載されうる。
【００８１】
本発明の別の態様によれば、移動されうるナビゲート可能ネットワークの量を制限するパラメータの値を所与として、前記ナビゲート可能ネットワーク上の第２の位置が到達されることが可能である間に、前記ナビゲート可能ネットワーク上の第１の位置から到達可能なエリアを表すナビゲート可能ネットワークを含む地理的エリアの一部を包含する第１の境界を判定する方法であって、前記ナビゲート可能ネットワークが、前記ナビゲート可能ネットワークのナビゲート可能要素を表す複数の区分を含む電子地図により表される、前記方法は、
前記第１の位置を表す区分の位置を判定し、前記判定された位置での前記パラメータの前記値を取得することと、
関連するコスト関数を有する検索アルゴリズムを使用して前記第１の位置を表す前記判定された位置から前記電子地図の前記区分を探索することと、探索されて到達可能であると判定された区分について、前記パラメータの前記取得された値よりも小さい前記第１の位置を表す前記判定された位置から最適コスト経路を移動することに起因する前記パラメータの値と関連付けられるのであれば区分は到達可能であり、前記パラメータの前記取得された値と、前記区分と関連付けられた前記パラメータの前記値との差よりも大きい前記パラメータの値と関連付けられた第２の境界内に区分が存在するかどうかを判定することであって、前記第２の境界は、複数の所定の第２の境界のうちの１つであり、各々は前記パラメータの異なる値と関連付けられており、各々は、前記パラメータの前記関連付けられた値を所与として前記第２の位置が到達されうる前記エリアを表す前記第２の位置の周囲の前記地理的エリアの一部を包含する、前記判定することと、
前記第１の境界を判定するために前記第２の境界内にあると判定された前記区分を使用することと、
を含む方法が提供される。
【００８２】
本発明は、いわゆる“安全な戻り範囲”、すなわち、移動されうる前記ナビゲート可能ネットワークの前記量を限定するパラメータの値を所与として所定の“ホーム位置”等の第２の位置が到達されることが可能である間に、現在位置等の第１の位置から到達されうるナビゲート可能ネットワークの部分、を判定する方法を提供する。以下でより詳細に議論されるように、前記パラメータは、車両の燃料量又はエネルギーレベルであることができ、或いは、他の実施形態では、移動にかかりうる最大時間又は最大距離であってもよく、従って、前記第１の位置、例えば現在位置、と関連付けられた前記パラメータの前記値は、前記車両の現在の燃料量又はエネルギーレベル（すなわちゼロ、すなわち空と、最大値、すなわち満タンとの間の値）又は移動されうる残りの距離又は時間を反映しうる。
【００８３】
本発明は、本明細書に記載の本発明の態様又は実施形態の何れかに従った方法を実行するシステムに及ぶ。
【００８４】
従って、本発明の更なる態様によれば、移動されうるナビゲート可能ネットワークの量を制限するパラメータの値を所与として、前記ナビゲート可能ネットワーク上の第２の位置が到達されることが可能である間に、前記ナビゲート可能ネットワーク上の第１の位置から到達可能なエリアを表すナビゲート可能ネットワークを含む地理的エリアの一部を包含する第１の境界を判定するシステムであって、前記ナビゲート可能ネットワークが、前記ナビゲート可能ネットワークのナビゲート可能要素を表す複数の区分を含む電子地図により表される、前記システムは、
前記第１の位置を表す区分の位置を判定し、前記判定された位置での前記パラメータの前記値を取得する手段と、
関連するコスト関数を有する検索アルゴリズムを使用して前記第１の位置を表す前記判定された位置から前記電子地図の前記区分を探索し、探索されて到達可能であると判定された区分について、前記パラメータの前記取得された値よりも小さい前記第１の位置を表す前記判定された位置から最適コスト経路を移動することに起因する前記パラメータの値と関連付けられるのであれば区分は到達可能であり、前記パラメータの前記取得された値と、前記区分と関連付けられた前記パラメータの前記値との差よりも大きい前記パラメータの値と関連付けられた第２の境界内に区分が存在するかどうかを判定する手段であって、前記第２の境界は、複数の所定の第２の境界のうちの１つであり、各々は前記パラメータの異なる値と関連付けられており、各々は、前記パラメータの前記関連付けられた値を所与として前記第２の位置が到達されうる前記エリアを表す前記第２の位置の周囲の前記地理的エリアの一部を包含する、前記手段と、
前記第１の境界を判定するために前記第２の境界内にあると判定された前記区分を使用する手段と、
を備えるシステムが提供される。
【００８５】
当業者により理解されるように、本発明のこの更なる態様は、必要に応じて、本発明の他の態様の何れかに関して本明細書に記載された本発明の好適且つ選択的な特徴のうちの１つ以上又は全てを含みうるし、好適には含む。明示的に述べられていなくても、本発明のシステムは、何れかの態様又は実施形態における本発明の方法に関して記載された何れかのステップを実行する手段を備えてもよく、その逆もまた同様である。本発明はコンピュータ実施発明であり、本発明の何れかの態様又は実施形態に関して記載されたステップの何れかは、１つ以上のプロセッサのセットの制御下で実行されてもよい。前記システムに関して記載された何れかのステップを実行する前記手段は、１つ以上のプロセッサのセットであってもよい。
【００８６】
何れかの態様又は実施形態における本発明の前記システムは、ナビゲーション装置等の任意の適当な装置の形態であってもよい。一般に、本発明の前記システムは、少なくとも１つの処理装置であってもよい。前記又はある処理装置は、ポータブルナビゲーション装置（ＰＮＤ）又は一体型装置であろうとなかろうと、ナビゲーション装置等の移動装置の装置であってもよく、或いは、サーバの装置であってもよい。
【００８７】
好適な実施形態において本発明の前記方法はその態様又は実施形態の何れかにおいて、ナビゲーション装置等の移動装置を使用して実行され、本発明は、本発明の態様又は実施形態の何れかの前記方法のステップを実行するように構成された移動装置、例えばナビゲーション装置に及ぶ。前記ナビゲーション装置は、ポータブルナビゲーション装置（ＰＮＤ）又は一体型装置、例えば車載装置であってもよい。
【００８８】
本発明の態様又は実施形態の何れかによれば、前記システム、例えばナビゲーション装置は、前記判定された第１の境界の少なくとも表現と共に、電子地図をユーザへ表示するためのディスプレイと、電子地図データにアクセスして前記ディスプレイを介してユーザへ電子地図が表示されるようにするように構成された１つ以上のプロセッサのセットと、ユーザが前記装置と対話するのを可能にするために前記ユーザにより操作可能なユーザインタフェースとを備えてもよい。
【００８９】
その実施に関わらず、何れかの態様又は実施形態における本発明に従って使用された装置、例えばナビゲーション装置は、プロセッサ、メモリ及び前記メモリ内に格納されたデジタル地図データ（又は電子地図）を備えてもよい。前記プロセッサ及びメモリは、ソフトウェアオペレーティングシステムが構築されてもよい実行環境を協働して提供する。１つ以上の追加のソフトウェアプログラムが、前記装置の前記機能性が制御されるのを可能にするために、且つ、様々な他の機能を提供するために提供されてもよい。前記装置、例えばナビゲーション装置は、例えばＧＰＳ又はＧＬＯＮＡＳＳ等の全地球的航法衛星システム（ＧＮＳＳ）の信号受信処理機能性を好適には含んでもよい。理解されるように、前記装置は、例えば地上波ビーコン、移動体通信ネットワーク等、所望のようにその現在位置を判定するための他の手段を使用してもよい。前記装置は、情報がユーザへ伝達されてもよい１つ以上の出力インタフェースを備えてもよい。前記出力インタフェースは、前記視覚表示に加えて可聴出力のためのスピーカを含んでもよい。前記装置は、前記装置のオン／オフ操作又は他の特徴を制御するための１つ以上の物理ボタンを含む入力インタフェースを備えてもよい。
【００９０】
他の実施形態において、本発明の前記方法はその態様又は実施形態の何れかにおいて、サーバにより実行されてもよく、本発明は、本発明の態様又は実施形態の何れかの前記方法のステップを実行するように構成されたサーバに及ぶ。何れかの態様又は実施形態の本発明の前記システムは、システム、例えばサーバの処理装置であってもよい。もちろん、本発明の前記方法のステップは、その態様又は実施形態の何れかにおいて、サーバにより部分的に実行されて、ナビゲーション装置により部分的に実行されてもよい。例えば、前記第１の境界は、例えばナビゲーション装置の要求に応じて、サーバにより判定されて、ユーザへの出力のために前記装置へ提供されてもよい。前記方法のステップは、排他的にサーバ上で実行されてもよく、いくつかはサーバ上で、他はナビゲーション装置上で任意の組み合わせで実行されてもよく、或いは、排他的にナビゲーション装置上で実行されてもよい。前記サーバ上での前記ステップの１つ以上のパフォーマンスは、効率的であってもよく、ナビゲーション装置にかかる計算負荷を低減してもよい。或いは、１つ以上のステップが前記ナビゲート装置上で実行されるなら、これは、ネットワーク通信に必要とされる帯域幅を低減してもよい。従って、本発明の前記システムは、部分的にナビゲーション装置又は他の移動装置により提供され、部分的にサーバにより提供されてもよい。
【００９１】
前記ナビゲート可能ネットワークは電子地図により表される。前記電子地図はノードにより接続された複数の区分を含む。前記電子地図（又は、場合によって知られているように、数学的グラフ）は、その単純な形態において、効果的には、ノード、最も一般的には道路交差点を表すデータ、及び、当該交差点間の道路を表す当該ノード間の線を含むデータベースである。より詳細なデジタル地図において、線は開始ノード及び終了ノードにより規定された区分に分割されてもよい。数ある中で、特定のストレッチ（長さ）の道路の形状情報を提供するために、又は、当該道路のいくつかの特徴、例えば速度制限、が変化する道路に沿った位置を特定する手段を提供するために、これらのノードは、それらが最少３つの線又は区分が交差する道路交差点を表す点で“リアル”であってもよく、或いは、それらは、それらがリアルノードにより一端又は両端で規定されていない区分のアンカとして提供される点で“人口的”であってもよい。前記ノード又は区分は、前記データベースにおけるデータにより再び表される様々な属性により更に規定される。例えば、各ノードは通常、その現実世界位置、例えば緯度及び経度、を規定するために地理的座標を有するだろう。ノードは通常、それと関連付けられた操作データであって、交差点において１つの道路から別の道路へ移動することが可能であるかを示す操作データも有するだろうし、一方で、前記区分は法定速度制限等の関連する属性も有するだろう。前記区分は関連する移動方向も有し、前記移動方向は前記区分が移動されうる可能な方向を示す。例えば、前記ナビゲート可能ネットワークが道路ネットワークである場合、区分は、一方通行道路を表してもよく、或いは、高速道路の一方の側の車線を表してもよく、従って、前記区分は、１つのノードから別のノードへの移動を可能にするが他の方向には可能にしない単一方向であるだろう。或いは、通常はよくあることであるが、前記区分は、１つのノードから別のノードへの移動を可能にし及びその逆もまた同様に可能にする双方向であってもよい。それ故、双方向区分は常に、ソフトな位置のエリアから出ていく区分でありうるが、これは単一方向区分には当てはまらない。
【００９２】
本発明の実施形態は道路区分に関連して説明されるが、歩道、河川、運河、自転車道路、航路又は鉄道線路などの区分のような他のナビゲート可能区分にも本発明を適用可能であってもよいことを理解すべきである。参照を容易にするために、これらは一般に道路区分として表されるが、“道路区分”へのあらゆる参照は、“ナビゲート可能区分”又はあらゆる特定の種類のそのような区分への参照により置き換えられてもよい。
【００９３】
本発明において、第１の位置を表すデータが取得される。前記第１の位置は、好適にはユーザ又は移動装置の現在位置であるが、ユーザが移動を開始することを望む任意の位置でありうる。それ故、前記第１の位置が前記移動装置の現在位置である場合、前記第１の位置を表す前記データは、ＧＮＳＳ受信機等の前記移動装置の位置判定手段から取得されうる。或いは、前記第１の位置を表す前記データは、例えばユーザが住所を提供し、或いは、電子地図の表現上で位置をマーク付けする場合、前記ユーザから受け付けられた情報に基づきうる。前記第１の位置を表す前記データは、前記第１の位置に対応する前記電子地図の区分上の位置を判定するために使用される。前記区分上の前記位置は、前記区分に沿った位置でありうるし、或いは、前記区分を規定する前記ノードの一方又は他方でありうる。前記区分上の前記位置での、すなわち前記第１の位置での前記パラメータの値も取得される。前記パラメータの前記値は、例えば前記装置が動作可能に前記車両と接続される際に、有線接続又は無線接続の何れかにより、前記車両から受信されうる。これは、例えば前記パラメータが前記車両の燃料量又はエネルギーレベルを反映する場合に当てはまりうる。或いは、前記パラメータの前記値は、ユーザから受信されうる。例えば前記ユーザは前記装置の適当な入力手段を使用して前記値を提供する。これは、例えば前記パラメータが、移動されるべき残りの（又は最大の）時間又は距離を反映する場合に当てはまりうる。理解されるように、自動的に、或いは、受信したユーザ入力に基づいて取得される前記パラメータの前記値は、好適にはゼロ（例えば空の燃料タンクを表す）と最大値（例えば満たされた燃料タンク）との間の値であるだろう。前記方法で使用される前記パラメータの前記値が、受信される前記値と直接一致しなくてもよいように、前記パラメータの前記値は、例えば前記車両又はユーザから受信された情報に基づきうることも理解されるだろう。
【００９４】
本発明において、前記電子地図の区分は、関連するコスト関数を有する検索（又は経路計画）アルゴリズムを使用して前記判定された位置から探索される。前記検索アルゴリズムは、好適には無向（undirected）検索を含み、従って、前記第１の位置を表す前記判定された位置から前記電子地図を通る（ひいては前記ナビゲート可能ネットワークを通る）最適パス又は経路、例えば通常は最小コストパスを識別するように動作する。従って、前記検索（又は経路計画）アルゴリズムは、意図される移動方向が前記第１の位置から外向きであるので、好適には“フォワード”検索である。前記検索は、所定の目的地又はゴールが無いという点で無向である。換言すれば、前記検索アルゴリズムは一対多のアルゴリズムであると考えられ、従って、前記第１の位置を表す前記判定された位置から前記電子地図の複数のノードへの最適パス又は経路を識別するように動作する。理解されるように、一対多の経路計画アルゴリズムは一対一の経路計画アルゴリズムとは、後者のアルゴリズムは前記電子地図における２つの位置の間の最適パスを判定するように設計されている点で、区別される。本発明の前記経路計画アルゴリズムは、ダイクストラアルゴリズム又は類似物に基づくもの等の、所望の任意の適当な形態をとりうる。本明細書で参照され且つ前記経路計画アルゴリズムにより判定される前記最適（又は最小コスト）経路は、前記関連するコスト関数の参照により最適なものである。前記コスト関数は、予め判定されてもよく、或いは、所望のように前記ユーザにより選択されてもよく、例えば２つの位置の間の最短距離、前記２つの位置の間の最速移動時間、前記２つの位置の間の最少燃料消費、又はこれらの所望の組み合わせ、を有する前記２つの位置の間の経路を識別することを目的としてもよい。経路の前記コストは、前記経路を形成する前記少なくとも１つの区分を移動するコストの合計として判定されてもよく、各区分を移動する前記コストは、前記コスト関数を使用して判定され、通常は、少なくとも１つの属性が、例えば前記区分の長さ、前記区分に沿った予想移動速度、前記区分に沿った高さの変化、前記区分の曲率（又は形状）等が、前記各区分と関連付けられている。
【００９５】
前記探索ステップは、前記第１の位置での前記パラメータの前記取得された値を所与として、前記経路計画アルゴリズムにより探索される区分が、前記第１の位置を表す前記位置から到達可能であるかどうかを判定することを含む。上で議論されたように、前記パラメータの前記取得された値よりも小さい、前記第１の位置を表す前記位置から最適コスト経路、例えば最小コスト経路を移動することに起因する前記パラメータの値と関連付けられているなら、区分は到達可能であると判定される。換言すれば、探索される各区分について、コストの観点で最適である、例えば最小コスト経路である前記第１の位置を表す前記位置からの１つ以上の区分を含む判定されたパスがある。理解されるように、特定の区分への前記パスを形成する前記１つ以上の区分の各々は、前記第１の位置から、当の前記区分により表された前記ネットワークの前記ナビゲート可能要素までの前記ナビゲート可能ネットワークの移動と関連付けられている前記パラメータの値となる。換言すれば、前記ナビゲート可能ネットワークを移動することは、例えば、任意の量の時間、距離又は消費される燃料を必要とする。従って、例えば、前記経路計画アルゴリズムと関連付けられた前記コスト関数が、区分を移動するための第１のコストを判定するために使用され、一方、目的関数が、前記区分を移動するための第２のコストを判定するために使用され、ここで、例えば、前記第２のコストは時間、距離、燃料又はエネルギーである。前記区分への前記最適パスは、例えば最小の累積された第１のコストを有するパスである。そうした実施形態では、探索された区分と関連付けられた前記パラメータは、前記第１の位置と関連付けられた前記位置から前記区分への最適パスを形成する前記１つ以上の区分の累積された第２のコストであり、例えば、前記パスを移動するのに必要とされる時間、前記パスの距離、前記パスを移動するのに必要とされる燃料量等である。それ故、前記検索アルゴリズムは、好適には、前記パラメータが全ての探索されたパスに関する前記取得された値を超過する場合に停止する無向フォワード検索を含むことが理解されるだろう。
【００９６】
本発明は探索された区分が到達可能であるかどうかを判定することを含むので、前記安全な戻り範囲を表す前記第１の境界を判定する前記方法は、前記第１の位置での前記パラメータの前記取得された値を所与として前記第１の位置から到達可能なエリアを表す前記地理的エリアにおける前記ナビゲート可能ネットワークの部分を包含する第３の境界を判定することも含みうる。実際、好適には、前記第１の境界及び第３の境界は、両境界の表現がユーザに対して表示されうるように、例えば同時に表示されうるように、本発明の前記方法で判定される。
【００９７】
上で議論されるように、前記第１の境界及び／又は第３の境界は、前記地理的エリアの部分を囲む。前記境界は任意の適当且つ所望の方法で規定されうる。例えば、前記境界は、前記電子地図の複数のノード等の複数の離散的な位置により規定されうるものであり、前記境界はこれらの位置を相互接続することにより規定される。例えば、前記第１の境界の場合、前記第１の位置から最も遠い前記探索されたパスの各々に沿った前記区分の前記ノードが、前記複数の離散的な位置として使用されうる。例えば、その全内容が参照により本明細書に組み込まれる国際公開２０１４／００１５６５号に記載されているように、前記第１の位置の周囲の前記地理的エリアの前記部分は、複数のセクタ、例えば１６個のセクタに分割されうるものであり、各セクタについて、前記第１の位置から、前記判定された境界の最も遠い地点、例えばノード、が格納される。前記離散的な位置、例えばノードは、好適には、連続境界を形成するように、線、例えば弧により接続される。
【００９８】
本発明において、探索されて到達可能であるとみなされる区分について、前記方法は、前記それぞれの区分と関連付けられた前記パラメータの前記値よりも大きい前記パラメータの値と関連付けられた第２の境界内に区分があるかどうかを判定することを含む。前記第２の位置は、好適にはユーザにより選択された位置であり、好適には前記ユーザによりよく使用される位置を表すものである。例えば、前記第２の位置は“ホーム”位置であることができ、従って、前記安全な戻り範囲は、前記ユーザのホームが到達可能である間に、前記ナビゲート可能ネットワーク上の前記第１の位置、例えば現在位置から到達可能なエリアである。しかしながら、前記第２の位置は、ユーザの“勤務”位置又は家族の家等の、任意の所定の位置でありうることが理解されるだろう。
【００９９】
前記第２の境界は、複数の所定の第２の境界のうちの１つであり、その各々は、前記パラメータの異なる値と関連付けられている。前記複数の第２の境界が効果的に前記第２の位置の周囲の一連のリング又はレイヤを形成するように、各第２の境界は、前記第２の位置が到達されうる前記エリアを示す前記第２の位置の周囲の前記地理的エリアの部分を囲む。前記複数の第２の境界を示すデータは、前記装置のメモリに好適に格納される。前記データは、例えば前記装置が電源をオンオフされても前記データが保持されるように、好適には不揮発性メモリに格納される。前記方法は、前記複数の第２の境界を判定することを好適には含む。
【０１００】
前記パラメータの値についての第２の境界の前記判定は、好適には、前記第２の位置を表す前記区分上の位置を判定することと、関連するコスト関数を有する検索（又は経路計画）アルゴリズムを使用して前記第２の位置を表す前記判定された位置から前記電子地図の前記区分を探索することとを含む。前記検索アルゴリズムは好適には無向検索を含み、従って、前記第２の位置を表す前記判定された位置で終了する前記電子地図を通る（ひいては前記ナビゲート可能ネットワークを通る）最適パス又は経路、例えば通常は最小コストパスを識別するように動作する。従って、前記検索（又は経路計画）アルゴリズムは、意図される移動方向が前記第２の位置へ向かうものなので、好適には“バックワード”検索である。前記検索は、所定の目的地又はゴールが無いという点で無向である。換言すれば、前記検索アルゴリズムは一対多のアルゴリズムであると考えられ、従って、前記電子地図の複数のノードから前記第２の位置を表す前記判定された位置への最適パス又は経路を識別するように動作する。本発明の前記経路計画アルゴリズムは、ダイクストラアルゴリズム又は類似物に基づくもの等の、所望の任意の適当な形態をとりうる。上で議論されたように、本明細書で参照され且つ前記経路計画アルゴリズムにより判定される前記最適（又は最小コスト）経路は、前記関連するコスト関数の参照により最適なものである。前記コスト関数は、予め判定されてもよく、或いは、所望のように前記ユーザにより選択されてもよく、例えば２つの位置の間の最短距離、前記２つの位置の間の最速移動時間、前記２つの位置の間の最少燃料消費、又はこれらの所望の組み合わせ、を有する前記２つの位置の間の経路を識別することを目的としてもよい。経路の前記コストは、前記経路を形成する前記少なくとも１つの区分を移動するコストの合計として判定されてもよく、各区分を移動する前記コストは、前記コスト関数を使用して判定され、通常は、少なくとも１つの属性が、例えば前記区分の長さ、前記区分に沿った予想移動速度、前記区分に沿った高さの変化、前記区分の曲率（又は形状）等が、前記各区分と関連付けられている。好適な実施形態において、前記複数の第２の境界を判定するために使用される前記検索（又は経路計画）アルゴリズムと関連付けられる（及び使用される）のと、同一のコスト関数が、前記第１の境界、及び選択的に前記第３の境界も判定するために使用される前記検索（又は経路計画）アルゴリズムと関連付けられる（及び使用される）。
【０１０１】
前記複数の第２の境界を判定するために使用される前記方法の前記探索ステップは、前記パラメータの所定値を所与として前記第２の位置を表す前記位置が区分から到達可能であるかどうかを判定することを含む。前記区分から最適経路、例えば最小コスト経路を移動することに起因する前記パラメータの前記値が、前記パラメータの前記所定値よりも小さいなら、前記第２の位置は区分から到達可能であると判定される。反対に、前記区分から最適経路、例えば最小コスト経路を移動することに起因する前記パラメータの前記値が、前記パラメータの前記所定値よりも大きいなら、前記第２の位置は到達可能でないと判定される。換言すれば、探索される各区分について、前記区分から、コストの観点で最適である、例えば最小コスト経路である前記第２の位置を表す前記位置への１つ以上の区分を含む判定されたパスがある。理解されるように、前記第２の位置を表す前記位置への前記パスを形成する前記１つ以上の区分の各々は、例えば前記ナビゲート可能ネットワークを移動することは、例えば任意の量の時間、距離又は消費される燃料を必要とするので、前記パラメータの値と関連付けられている。従って、例えば、前記経路計画アルゴリズムと関連付けられた前記コスト関数が、区分を移動するための第１のコストを判定するために使用され、一方、目的関数が、前記区分を移動するための第２のコストを判定するために使用され、ここで、例えば、前記第２のコストは時間、距離、燃料又はエネルギーである。前記区分への前記最適パスは、例えば最小の累積された第１のコストを有するパスである。そうした実施形態では、探索された区分と関連付けられた前記パラメータは、前記区分から、前記第２の位置と関連付けられた前記位置への最適パスを形成する前記１つ以上の区分の累積された第２のコストであり、例えば、前記パスを移動するのに必要とされる時間、前記パスの距離、前記パスを移動するのに必要とされる燃料量等である。それ故、前記検索アルゴリズムは、好適には、例えば前記パラメータは前記第２の位置でゼロ、例えば空とされるので、前記パラメータが全ての探索されたパスに関して最大値、例えば満、に到達する場合に停止する無向バックワード検索を含むことが理解されるだろう。完全検索により規定された到達可能範囲は、最も外側の第２の境界を形成し、他の第２の境界は、ゼロと最大値との間の中間パラメータ値である。
【０１０２】
前記第２の境界の各々は、前記第２の境界が前記第２の位置の周囲の一連のレイヤ又はリングを効果的に形成するように、前記パラメータの異なる値と関連付けられる。例えば、前記パラメータが車両の燃料量又はエネルギーレベルを表す実施形態では、前記最も外側の第２の境界は、すなわち前記地理的エリアの最も大きい部分を囲むものは、燃料又はエネルギーの最大量を所与として前記第２の位置が到達されうる前記ナビゲート可能ネットワークの前記部分を表す。残りの第２の境界は、それらは前記最大量よりも小さい前記車両の燃料又はエネルギーレベルと関連付けられているので、前記地理的エリアの次第により小さくなる部分を表す。例えば、境界は、１０％、２０％、３０％…１００％満タンの前記車両の燃料又はエネルギーレベルについて判定されてもよい。しかしながら、任意の数の境界が所望のように判定されうるものであり、例えば境界は、前記第２の位置から最大到達可能距離まで、５ｋｍ又は１０ｋｍの距離間隔で、すなわち当該距離範囲と同等な燃料又はエネルギーレベルについて判定されうることが理解されるだろう。前記パラメータが移動にかかりうる時間又は距離を示し、前記パラメータの前記取得される値が最大時間又は距離であり、前記取得される値が所定範囲から選択された１つである実施形態では、前記複数の境界は、前記所定範囲内の選択された時間間隔又は距離間隔について判定されうる。
【０１０３】
実施形態において、前記複数の第２の境界は、所定のトリガイベントが起こると何時でも再計算されうる。前記トリガイベントは以下のうちの１つでありうる。前記第２の位置の変化；前記電子地図の変化；前記経路計画アルゴリズムで使用される選択されたコスト関数の変化；（前記方法が実行される）前記移動装置が再開される時、すなわちオフ状態から電源をオンにされる時；（前記方法を実行する）前記ソフトウェアアプリケーションがオープンにされる時、すなわちソフトウェアランチャアプリケーションにより実行される時。理解されるように、前記移動装置及び／又はソフトウェアアプリケーションが開始するたびに前記複数の第２の境界の前記再計算をトリガすることによって、これにより、前記複数の第２の境界が、前記ナビゲート可能ネットワークの現在の条件、例えば道路閉鎖、重要な交通渋滞イベント等と共に、比較的最新のまま維持されることを可能にする。
【０１０４】
当業者により、前記第１の境界、及び選択的に前記第３の境界を判定するために使用される前記経路計画アルゴリズムは、（利用可能な時は）前記ナビゲート可能ネットワークのリアルタイムの交通条件又は他の移動条件を常に考慮し、一方、前記複数の第２の境界は予め判定されて格納されるので、それらは、前記ナビゲート可能ネットワークの現在の交通移動条件を常に表すとは限らないことが理解されるだろう。それ故、本発明の前記方法により判定された前記安全な戻り範囲は、実際の範囲の推定であるだろう。従って、実施形態において、本発明で使用された前記パラメータは、前記車両の実際の燃料又はエネルギーレベルに対応しなくてもよいが、例えば前記最も外側の第２の境界が、１００％の燃料又は充電レベルではなく、９５％の燃料又は充電レベルに対応してもよいように、バッファを含んでもよい。
【０１０５】
前記複数の第２の境界の各々は、前記地理的エリアの部分を囲み、任意の適当且つ所望の方法で規定されうる。例えば、前記境界は、前記電子地図の複数のノード等の複数の離散的な位置により規定されうるものであり、前記境界はこれらの位置を相互接続することにより規定される。例えば、国際公開２０１４／００１５６５号に記載されているように、前記第２の位置の周囲の前記地理的エリアの前記部分は、複数のセクタ、例えば１６個のセクタに分割されうるものであり、各セクタについて、前記第２の位置から、前記判定された境界の最も遠い地点、例えばノード、が格納される。前記離散的な位置、例えばノードは、好適には、連続境界を形成するように、線、例えば弧により接続される。
【０１０６】
上で議論されるように、本発明において、探索されて到達可能であるとみなされる区分について、前記方法は、前記パラメータの前記取得された値と前記区分と関連付けられた前記パラメータの前記値との差よりも大きい前記パラメータの値と関連付けられた第２の境界内に前記区分があるかどうかを判定することを含む。各第２の境界は、再び上で議論されたように、当の特定の第２の境界と関連付けられた前記パラメータの前記値を所与として前記第２の位置が到達されうる、前記地理的エリアの前記部分ひいては前記ナビゲート可能ネットワークの部分を表す。それ故、理解されるように、前記第１の位置を表す前記位置からパスが探索されるにつれて、各パスに沿ったいくつかの地点で適切な第２の境界内に入る区分であって、それ故前記第２の位置が到達されうる区分が識別されるだろうし、一方、（前記第１の位置から離れた）前記パスにおける次の区分は、前記第２の境界内に入らず、それ故、そこから前記第２の位置は到達されない。
【０１０７】
本発明の実施形態において、探索されている前記現在の区分の前記位置は、前記区分が発見されうる最も外側の境界を識別するために、前記複数の第２の境界の前記地理的範囲と比較される。前記パラメータの前記取得された値と、前記区分と関連付けられた前記パラメータの前記値との差、すなわち差分値は、好適には、前記識別された境界と関連付けられた前記パラメータと比較されうる。前記差分値が、前記境界と関連付けられた前記パラメータよりも大きい場合、前記区分は前記安全な戻り範囲内にあり、そうでない場合、前記区分は前記安全な戻り範囲外にあると判定されうる。実施形態において、前記安全な戻り範囲の前記境界を規定する前記離散的な地点を判定するために、前記第２の境界内にあるパスに沿った区分と、前記第２の境界の少なくとも部分的に外側にある前記パスに沿った隣接する（近傍の）区分との間のノードが、全ての他のパスについてのノードと共に、使用されうる。
【０１０８】
本発明の他の実施形態において、前記第２の境界は好適には、前記差分値に基づいて前記複数の第２の境界から選択される。前記選択された第２の境界は、好適には、前記差分値に最も近い前記パラメータの値と関連付けられた第２の境界であり、より好適には、前記差分値に最も近く且つそれよりも小さい前記パラメータの値と関連付けられた第２の境界である。換言すれば、前記選択された第２の境界は、当の前記区分について前記差分値よりも小さい前記パラメータの値と関連付けられた最も外側の第２の境界である。従って、前記区分が、前記選択された第２の境界により囲まれた前記地理的エリア内に位置するなら、前記ナビゲート可能ネットワークを移動することによって前記第２の位置に到達することが可能であり、従って、前記区分は前記第１の境界を判定するために使用されるべきである。反対に、前記区分が、前記選択された第２の境界により囲まれた前記地理的エリア外に位置するなら、前記ナビゲート可能ネットワークを移動することによって前記第２の位置に到達することは可能ではなく、従って、前記区分は前記第１の境界を判定するために使用されるべきではない。
【０１０９】
本発明の実施形態において、前記第１の境界、又はそれにより囲まれた前記エリア、の少なくともいくつか及び好適には全てを表す情報が、例えば前記移動装置と関連付けられた、ディスプレイ上でユーザに対して表示される。或いは、実施形態において、前記第３の境界、又はそれにより囲まれた前記エリア、の少なくともいくつか及び好適には全てを表す情報が、好適には前記第１の境界を表す前記情報と同時に、例えば前記移動装置と関連付けられた、ディスプレイ上でユーザに対して表示される。理解されるように、前記複数の第２の境界は、前記第１の境界を判定するために使用されることが意図され、好適には前記ユーザへ表示されることは意図されていない。前記方法が移動装置により実行される実施形態では、前記第１の境界及び／又は第３の境界、又はその部分は、前記移動装置のディスプレイに表示されうる。或いは、前記方法がサーバにより実行される実施形態では、前記第１の境界及び／又は第３の境界、又はそれらにより囲まれた１又は複数のエリアの少なくともいくつか及び好適には全てを表す前記情報は、移動装置へ、そこでの表示のために送信されうる。
【０１１０】
理解されるように、前記第１の位置が移動装置の現在位置を表す実施形態では、前記第１の境界及び選択的には前記第３の境界が継続的に再計算されて、好適にはごく最近計算された１又は複数の境界が前記ユーザに示されるように、前記方法は、好適には前記移動装置の位置が変化するにつれて繰り返される。前記方法は、例えば、任意の期間の後、任意の距離が移動された後、任意の量の燃料又はエネルギーが使用された後等、任意の所望の頻度で実行されてもよい。
【０１１１】
実施形態では、前記方法は、複数の第２の位置の各々について複数の第２の境界を示すデータを判定及び／又は当該データにアクセスことに及んでもよいことが想定される。それ故、安全な戻り範囲は、例えば、所望のようにユーザの“ホーム”、“勤務地”、“ジム”等について判定されうる。そうした実施形態では、前記方法は、例えば受信されたユーザ入力に基づいて複数の所定の第２の位置のうちの１つの選択を取得することと、前記選択された所定の第２の位置に関して上記の方法を実行することとを含んでもよい。
【０１１２】
本発明に従った方法の何れかは、少なくとも部分的にソフトウェア、例えばコンピュータプログラムを使用して実施されてもよい。従って、本発明は、本発明の態様又は実施形態の何れかに従った方法を行うこと或いはナビゲーション装置及び／又はサーバに行わせることを実行可能なコンピュータ可読命令を含むコンピュータプログラムにも及ぶ。
【０１１３】
本発明は、データ処理手段を含むシステム又は装置を動作させるために使用される場合に、前記データ処理手段と共に、前記装置又はシステムに、本発明の方法のステップを実行させる当該ソフトウェアを含むコンピュータソフトウェアキャリアにも相応に及ぶ。そうしたコンピュータソフトウェアキャリアは、ＲＯＭチップ、ＣＤＲＯＭ又はディスク等の非一時的な（継続性のある）物理的な記憶媒体でありえ、或いは、有線の電気信号、光学信号又は衛星に関する無線信号等の信号でありうる。本発明は、機械により読み出された場合に、本発明の態様又は実施形態の何れかの方法に従って前記機械を動作させる命令を含む機械可読媒体を提供する。
【０１１４】
その実施に関わらず、本発明に従って使用されるナビゲーション装置は、プロセッサ、メモリ、及び前記メモリ内に格納されたデジタル地図データを含んでもよい。前記プロセッサ及びメモリは、ソフトウェアオペレーティングシステムが構築されてもよい実行環境を協働して提供する。１以上の追加のソフトウェアプログラムが、前記装置の機能性が制御されること、様々な他の機能を提供することを可能にするために提供されてもよい。本発明のナビゲーション装置は、好適には、ＧＰＳ（全地球測位システム）信号受信処理機能を含んでもよい。前記装置は、前記ユーザに情報が伝達されてもよい１以上の出力インタフェースを備えてもよい。前記出力インタフェースは、視覚ディスプレイに加えて可聴出力のためのスピーカを含んでもよい。前記装置は、前記装置のオン／オフ動作又は他の特徴を制御するための１以上の物理ボタンを含む入力インタフェースを備えてもよい。
【０１１５】
他の実施形態では、前記ナビゲーション装置は、特定のナビゲーション装置の一部を構成しない処理装置のアプリケーションにより少なくとも部分的に実施されてもよい。例えば、本発明は、ナビゲーションソフトウェアを実行するように構成された適当なコンピュータシステムを使用して実施されてもよい。前記システムは、モバイル又はポータブルのコンピュータシステム、例えば携帯電話又はラップトップであってもよいし、或いは、デスクトップシステムであってもよい。
【０１１６】
明示的に述べられていなくても、本発明は、その態様の何れかにおいて、相互に排他的ではない程度に本発明の他の態様又は実施形態に関して記載された特徴の何れか又は全てを含んでもよいことが理解されるだろう。特に、前記方法で及び前記装置により実行されてもよい様々な実施形態の動作が記載されているが、これらの動作の何れか１つ以上又は全てが、前記方法及び前記装置により、必要に応じて、所望のように、任意の組み合わせで実行されてもよいことが理解されるだろう。
【０１１７】
上記の実施形態の利点は以下に記載され、上記の各実施形態の更なる詳細及び特徴は添付の従属請求項及び以下の詳細な説明中で定義される。
【図面の簡単な説明】
【０１１８】
添付図面を参照しながらほんの一例として様々な実施形態が記載されるだろう。
【図１】図１は、本発明の一実施形態の概略図である。
【図２】図２は、本発明の実施形態を例示するフローチャートである。
【図３】図３は、ユーザへの表示のために到達可能なエリアが視覚化されてもよい方法の例である。
【発明を実施するための形態】
【０１１９】
特にＰＮＤを参照して、本発明の実施形態を以下に説明する。尚、本発明の教示はＰＮＤに限定されず、経路計画／ナビゲーション機能性を提供するためにナビゲーションソフトウェアを実行するように構成されるどんな種類の処理装置にも例外なく適用可能である。従って、本出願において、ナビゲーション装置は、ＰＮＤ、車両に内蔵されたナビゲーション装置、あるいは実際は経路計画／ナビゲーションソフトウェアを実行する演算リソース（デスクトップ又はポータブルパーソナルコンピュータ（ＰＣ）、移動電話、あるいはポータブルデジタルアシスタント（ＰＤＡ）等）として実現されるかに関わらず、どんな種類の経路計画／ナビゲーション装置も含む（それらに限定されない）ことを意図する。
【０１２０】
本発明の実施形態は、現在地（出発地ノード）から到達されうる一方で、到達可能な距離を制約するパラメータの現在値を所与としてホーム位置又は任意の他の予め定義された位置（目的地ノード）に更に到達する、エリアの概略の判定を可能にする。この、いわゆる“安全な戻り範囲”は、ユーザの走行距離不安症を低減するのを助けるために地図上でユーザに対して視覚化され或いは表示されてもよい。例えば、パラメータが車両の現在の燃料量又は充電レベルである場合、安全に到達されうる一方、燃料又は充電が無くなることなくホーム位置に更に到達する、現在位置とホーム位置との間の位置の範囲を表す安全な戻り範囲が表示されうる。
【０１２１】
以下の記載の本発明の実施形態ではパラメータは電動車両の充電レベルであるが、本明細書に記載の技術は、この場合に限定されるものではなく、任意の他の適当な制約と共に適用されてもよいことが理解されるだろう。例えば、パラメータは、移動時間又は移動距離を表してもよい。もちろん、ある燃料量又は充電レベルは、ある到達量又は移動時間を提供するので、最大移動時間又は最大移動距離は、現在の燃料量又は充電レベルに関連してもよい。しかしながら、制約は単純に、ホーム位置が到達されなければならない時間又はユーザが例えばランニングにより移動したい距離でありうることも熟考される。複数の制約因子又はパラメータが存在してもよく、本明細書に記載の技術は一般にこれらのうちの１つ以上を考慮することも理解されるだろう。
【０１２２】
本発明の実施形態において、安全な戻り範囲は、現在到達可能なエリアの計算を使用する２つのステップで本来計算される。最初に、種々のそれぞれ予め定義されたパラメータの値（例えば充電レベル）についてホーム位置が到達されうるエリアを表す一連の境界が取得又は判定される。例えば、一連の離散的に増加するパラメータの値について境界が取得又は判定されてもよい。次に、車両又は装置の現在地の周囲の現在到達可能なエリアが、パラメータの現在値（例えば現在の充電レベル）に基づいて判定される。種々の値のパラメータについてホーム位置の周囲の到達可能なエリアの境界が、最初のステップで既に取得又は判定されているので、パラメータの現在値を所与として、現在到達可能なエリア内の任意の所与の位置が、ホーム位置への到達可能なエリア内にもあるか否かを、その位置でのパラメータの推定値と、その位置からホーム位置へ到達するのに必要なパラメータの値とを単純に比較することによって、判定することは容易である（最初のステップから取得された境界を使用して判定されるので）。従って、現在到達可能な範囲と安全な戻り範囲との両方を別個に計算する必要が無い。任意の所与の位置がホーム位置の安全な戻り範囲内にあるかどうかの判定は、計算労力を著しく増大させること無く、現在到達可能なエリアの計算から直接行われうる。
【０１２３】
この方法は、移動可能距離がバッテリに格納された充電のレベルにより制約される電動車両の場合について図１に概略的に示される。
【０１２４】
図１は、固定のホーム位置２の周囲の地図データの領域を概略的に示しており、車両は現在地１を有する。図１には示されていないが、領域は一般に、車両が沿って移動してもよい一連の相互接続されたノード及びリンク、すなわち道路及びジャンクションを含むネットワークを含むことが理解されるだろう。従って、車両は、あるリンクに沿って移動するように制約され、一般に、領域内の任意の２つのノード又は地点の間には直線経路が存在しないかもしれない。ホーム位置２の周囲に一連の境界２１、２２、２３、２４、２５が示されており、各境界２１、２２、２３、２４、２５は、次第に増加する充電レベルでホーム位置２が到達されうる距離を表すエリアを囲むものである。例えば、第１の境界２１は、２０％の充電残量でホーム位置２がちょうど到達されうる一連の地点を表してもよい。第２の境界２２は、４０％の充電残量でホーム位置２がちょうど到達されうる一連の地点を表してもよく、第３の境界２３は６０％の充電残量で、第４の境界２４は８０％の充電残量で、第５の境界２５は満充電（１００％）バッテリでホーム位置２がちょうど到達されうる一連の地点を表してもよい。ホーム位置２へ移動するのに１００％超を必要とする第５の境界２５の外側にある地点については、（例えばバッテリが再充電されない限り）ホーム位置２は到達可能ではなく、そこで、これらの地点は常に安全な戻り範囲の外側にある。
【０１２５】
各境界２１、２２、２３、２４、２５は、当該境界と関連付けられた充電レベルで潜在的に到達されうる位置を表すエリアを囲むものであることが理解されるだろう。従って、隣接する境界間に規定されたリング状エリアは、２つの境界間で規定されるような充電レベルの範囲で到達されうる位置を規定する。例えば、第１の境界２１及び第２の境界２２の間に規定されたリングは、２０％の充電で到達可能なエリアを表す第１の境界２１により囲まれたエリアと比較して、４０％の充電で到達可能な追加のエリアを表す。境界２１、２２、２３、２４、２５の形状及び範囲は一般に、以下でより詳細に議論されるように、地図データ及び経路検索アルゴリズムを使用して判定され、一般に、境界を判定するために使用されたホーム位置と境界との間のネットワークを通る経路を表す、任意の形状のポリゴンであることが理解されるだろう。しかしながら、その最も単純な実施において、境界はホーム位置の周囲の一連の円として近似されうる。
【０１２６】
図１は、現在地１の周囲の現在到達可能なエリア３も示しており、それはライブ地図データ等の地図データ、及び現在の充電値に基づいてリアルタイムに判定されてもよい。車両の現在地１はＧＰＳデータを使用して判定されてもよい。“ライブ”地図データは、例えば、地図領域のネットワークのリンクを通じた移動時間及び／又は移動速度に影響を与えるかもしれない交通条件及び天候条件を含む、現在の又は比較的現在の地図領域における条件に関する情報を参照することが理解されるだろう。そのようなライブデータは、当業者に既知のように、外部サーバからダウンロードされることを介して、装置へ提供されてもよく、定期的に更新されてもよい。境界２１、２２、２３、２４、２５を使用して、現在到達可能なエリア３内の任意の所与の位置１２についてホーム位置２への安全な戻り範囲が、容易に判定されうる。例えば、現在到達可能なエリア３内の所与の位置１２について、ホーム位置の周囲の境界２１、２２、２３、２４、２５のうちの何れの２つの間に位置１２が存在するかを判定することは容易であり、例示されたケースでは、位置１２は第１の境界２１及び第２の境界２２の間に存在する。位置１２がホーム位置２への安全な戻り範囲内にあるかどうかを判定するために、その場合に必要な全ては、現在地１から当該位置１２まで（例えば経路１１２に沿って）移動した後に予期される残りの充電と、対応する境界２２と関連付けられた充電値とを比較することである。例えば、位置１２での残りの充電レベルが５０％であるなら、位置１２はホーム位置２の周囲の４０％境界内にあるので、（例えば、経路計画アルゴリズムを使用して位置１２とホーム位置２との間の最短経路として選択されてもよい経路１２２に沿って移動することによって）ホーム位置２に到達するまでの間に現在地１から当該位置１２に到達することは可能だろう。しかしながら、位置１３での残りの充電がわずか２０％（以下）であるなら、位置が２０％境界を超えた所にあるので、ホーム位置２は到達可能ではないだろう。
【０１２７】
例えば、充電値のより小さいインクリメントに対応するより近い間隔の境界を使用することにより原則として近似の精度は増加するかもしれないことが理解されるだろう。しかしながら、境界自体は近似に過ぎず、任意の所与の位置での予期される充電値はせいぜい推定であることも理解されるだろう。境界は近似に過ぎないので、各境界と関連付けられた充電レベルにいくらかのバッファを含むことが望まれてもよく、その結果、２０％の充電レベルとしてユーザに識別された境界２１は実際には例えば１８％の充電レベルに対応してもよい。特定の位置について安全な戻り範囲内にある当該位置と関連付けられた信頼レベル（信頼度）をユーザに対して表示することも望まれてもよい。例えば、ちょうど安全な戻り範囲内にあるとだけ判定される位置は、十分安全な戻り範囲内にあると予期される位置とは異なる影又は色で示されてもよい。
【０１２８】
図２は、図１に関連して上に記載した実施形態をより詳細に示すフローチャートである。それ故、図２は再び、電動車両内に取り付けられたＰＮＤのホーム位置への安全な戻り範囲を判定することに関する実施形態を記載する。
【０１２９】
第１のステップ１０１では、各々が次第に増加する充電レベル（又は例えばキロメートルのリーチ）と関連付けられた一連の境界を生成するためにホーム位置からの“逆方向”経路検索が実行される。それ故、各境界は、特定の充電レベルを所与として到達可能である位置を含むエリアを囲むものである。それ故、一連の境界は、ホーム位置の周囲の一連の同心のエリア又はリング状エリアを規定し、各リング状エリアは異なる範囲の充電値と関連付けられている（すなわち、それらは当該リング状エリアを規定する２つの隣接する境界と関連付けられている）。例えば、２０％境界と４０％境界との間で囲まれるリング状エリアは、最大２０％の充電でホーム位置が到達されうる２０％境界により囲まれた位置と比較して、最大４０％の充電でホーム位置が到達されうる追加の位置を表す。
【０１３０】
所与の充電レベルについて到達可能なエリアを囲む境界は、例えば国際公開第２０１４／００１５６５号に記載の方法を含む任意の適当な方法により判定されてもよい。一般的には、本発明の目的のために、制約パラメータの特定値の所与のノード（例えばホーム位置）の周囲の境界は、一連の接続されたリンクを含む各経路が、当該経路に沿って各リンクを移動することと関連付けられたコストに対応する関連累積コストを有するように、単一ノードから延びる多数の可能なリンクを探索し且つ制約パラメータの観点で各リンクにコストを割り当てる一対多の検索アルゴリズムを使用して判定されてもよい。従って、経路の終わりの任意の所与の地点は、ノードでのパラメータの初期値に関する任意の閾値を累積コストが超過しない限り、到達可能であるものと判定される。従って、パラメータの任意の値と関連付けられた特定の境界が、そのパラメータの値でちょうど到達可能である地点のセットを使用して判定される。これらの最大限到達可能な地点位置は、ステップ１０５に関して以下でより詳細に記載されるように、例えば視覚化目的で、境界を規定するために接続されてもよい。
【０１３１】
例えば、制約パラメータが電動車両の充電レベルである場合、上記の特定の実施形態のように、検索アルゴリズムは、ノードから延びるリンクを探索するために地図上で検索し、当該リンクを移動するのに必要とされる充電レベル、すなわち充電量の観点で各リンクにコストを割り当てることによって進行する。電気的充電の特定のケースについて、リンクと関連付けられたコストが正又は負であってもよいように、例えば電動車両が下り坂を移動しているならバッテリが再充電されてもよいことが理解されるだろう。それ故、ノードから地図上の特定の地点までの任意の所与の経路は、経路に沿ってリンクの各々を移動するための累積コストを表す関連コストを有する。当該地点は、ノードでの特定の充電レベルを所与として、ノードからその地点に到達するための累積コストが、そのノードでの充電レベルを超過しない限り、到達可能であると判定される。任意の充電レベルでちょうど到達可能である地点のセットは、当該充電レベルと関連付けられた境界を規定する。パラメータが充電レベルではない場合に、到達可能な境界の判定が同様に進行してもよいことが理解されるだろう。例えば、制約パラメータが時間である場合、境界は、各リンクを移動するのにかかる時間、従って各経路を移動するための全体時間を使用して判定されてもよい。
【０１３２】
到達可能なエリアの判定は、１つ以上の経路計画基準に基づいてもよい。すなわち、検索アルゴリズムは、ナビゲーションシステムの経路化嗜好および制約パラメータを考慮してもよい。例えば、経路計画アルゴリズムは、最短移動時間又は最短移動距離を有する経路又は最もエネルギー又は燃料が効率的である経路に沿うようにユーザを案内してもよく、或いは、ユーザを任意の道路種別から離れるように案内してもよい。経路計画基準は、経路計画関数のコストの観点で規定されてもよい。例えば、経路計画基準が、ノード及び特定の地点の間の最速経路を判定することである場合、各リンクは、当該リンクを移動するのにかかる時間に基づいてコストを割り当てられてもよく、経路に沿った累積移動時間を最小化する一連のリンクに基づいて経路が選択される。他の経路計画基準は、例えばリンクの長さ、リンクに沿った平均速度、又はリンクの移動と関連付けられた予期される燃料又はエネルギー消費に基づいてコストを割り当ててもよい。それ故、経路化嗜好および制約パラメータを考慮した適当な検索アルゴリズムは、各経路が、パラメータの観点での第１の累積コストおよび第２のコストの最小／最大の累積である第２の累積コストを有するように、パラメータ（すなわち充電）の観点での第１のコストおよび経路化アルゴリズムと関連付けられたコスト関数を使用する第２のコストを各リンクに割り当てることを含んでもよい。到達可能なエリアは、経路計画基準に基づいて選択される経路に沿って、例えば最短経路又は最速経路に沿って、パラメータの初期値に基づいて到達されうる複数の地点により規定される。
【０１３３】
ホーム位置は一般的にしばしば変化しない固定位置であるので、特定の充電値についてホーム位置から到達可能なエリアは劇的には変わらないことが想定されうる。従って、ステップ１０１で判定されたホーム位置についての一連の境界及び／又は到達可能なエリアは、それらが装置のリブートを乗り切るように、移動装置の永続メモリに格納されてもよい。境界及び／又は到達可能なエリアは、ホーム位置の変更又は地図データの変更等の任意の環境下で再計算されることを必要としさえすればよい。従って、ステップ１０１で判定された境界及び／又は一連のエリアは、これらを再計算する必要無しに装置のメモリから取得されてもよい。この利点は計算負荷をさらに低減する。
【０１３４】
ステップ１０２では、ホーム位置と関連付けられた到達可能なエリアが判定及び／又は取得されると、現在の充電レベルに基づいて装置の現在地から現在到達可能なエリアが経路検索により計算される。現在到達可能なエリアの判定は、上記の方法で実行されてもよく、選択的に、ナビゲーション装置の経路嗜好を考慮もする。経路検索において到達される現在到達可能なエリアにおける各地点について、現在地から当該地点に到達することと関連付けられたコストに基づいて、当該地点で予期される残りの充電値が判定される。
【０１３５】
ステップ１０３では、経路検索で到達される現在到達可能なエリアにおける各地点について、ホーム位置の周囲のリング状エリアの何れが当該地点を含むか、すなわち、隣接境界の何れの間に当該地点が存在するか、に関するチェックが行われる。当該地点での電動車両の予期される残りの充電レベルと、当該地点が内部に存在するリング状エリア及び／又は境界と関連付けられた充電レベルとの比較が行われる（ステップ１０４）。それ故、この比較を通じて、現在到達可能なエリアにおける任意の所与の地点が、ホーム位置の安全な戻り範囲内にもあるか否かを容易に判定することが可能である。例えば、所与の区分において、電動車両の予期される残りの充電レベルが５０％であり、当該区分がホーム位置の４０％の到達可能なエリア内にあるなら、ホーム位置が到達可能だろう。しかしながら、当該区分がホーム位置の６０％の到達可能なエリア内にあるなら、ホーム位置は到達可能ではない。
【０１３６】
方法が無制限に実行されるなら、或いは、例えばオフラインで実行されるなら、これらのチェック及び比較のステップ（ステップ１０３及び１０４）は、現在到達可能なエリア内の全ての地点について実行されてもよい。しかしながら、特に、方法がリアルタイムに実行される場合、このステップは、現在到達可能なエリア内の地点のいくつかについてのみ実行されてもよい。通常、チェック及び比較のステップ（ステップ１０３及び１０４）は、現在到達可能なエリアにおける各地点について、当該地点が経路検索アルゴリズムにより到達される限り、すなわち経路検索（ステップ１０２）が実行中の間に、実行されるだろう。チェック及び比較のステップ（ステップ１０３及び１０４）は比較的単純であり、それ故、計算負荷又は処理時間を著しく増大させること無しに経路検索（ステップ１０２）中に容易に実行されうる。
【０１３７】
ステップ１０４で判定されるように現在の充電レベルを所与としてホーム位置がさらに到達可能である現在の到達可能な地点を含む安全な戻り範囲が、次に視覚化されてステップ１０５で運転者に対して表示される。安全な戻り範囲を視覚化して表示するために任意の適当な技術が使用されてもよい。例えば、現在到達可能な範囲を描写するために使用されるのと同一の視覚化技術（例えば国際公開第２０１４／００１５６５号に記載の技術）が、安全な戻り範囲を視覚化するために使用されうる。安全な戻り範囲及び現在到達可能な範囲が同時に運転者に対して表示されてもよく、或いは、運転者が即座に表示間を切り替えることができるように、少なくとも同時に利用可能であってもよい。一般的に、現在到達可能なエリア及び／又は安全な戻り範囲は、複数の離散的な地点位置を含むだろう。エリア／範囲は、これらの地点位置又は選択された数のこれらの地点位置を相互接続することにより形作られてもよい。例えば、視覚化処理は、現在地の周囲の領域を、複数のセクタに分割することを含んでもよく、各セクタからの地点位置はエリアを視覚化するために使用される。視覚化処理で使用されるセクタ／地点の数が増加することによって表示の解像度が増加されうる。これは国際公開第２０１４／００１５６５号に記載されている。視覚化を容易にするために、エリアを形作るために使用される離散的な地点は、概略的な安全な戻り範囲を反映する、滑らかなエリアを提供するために弓状線により接続されてもよい。安全な戻り範囲と関連付けられた精度又は信頼レベルが、影付け又は色付けによりディスプレイ上で示されてもよい。例えば、安全な戻り範囲の境界に近い地点について、十分な安全な戻り範囲内にある地点よりも、より明るい／より暗い影が、使用されてもよい。
【０１３８】
図３は、一般的にどのようにして到達可能なエリアが視覚化されてもよいかを示す。図３に示されたケースでは、ノード２３の周囲の到達可能なエリアは、一連の最大限到達可能な地点３３、３４を相互接続することにより判定される。その地点は、到達可能なエリアの境界を提供するために直接３６相互接続されてもよい。しかしながら、視覚化を容易にするために、滑らかな近似３０としてユーザへ到達可能なエリアを表示することがしばしばより良いことである。従って、到達可能なエリアの外周の周囲の隣接地点３３、３４の間の接続は、ユーザへの表示のために到達可能なエリア３０の滑らかな表現を提供するために弓状線により近似されてもよい。この技術は、装置の現在地から現在到達可能なエリア視覚化と、安全な戻り範囲の視覚化との両方のために使用されてもよい。ホーム位置の周囲の到達可能なエリア又は境界を表示することが望まれるなら、同一又は類似の技術が使用されうる。
【０１３９】
ステップ１０２−１０５は通常、電動車両の現在位置（及び現在の充電レベル）が変化するにつれて、繰り返し、継続的に、リアルタイムに実行される。現在地は継続的に変化しているので、経路検索アルゴリズムは、現在地の周囲のリンク又は到達可能な地点の各々を探索する時間を持たないかもしれず、そのため、これらのステップで生成されて視覚化されるエリアは不完全かもしれないことが理解されるだろう。
【０１４０】
上記の実施形態において、ホーム位置の周囲の到達可能なエリア又は境界は、永続装置メモリに格納されて、例外的な環境を除いて再使用される。従って、ホーム位置から到達可能なエリアは、地図における静的データのみを使用して判定され、例えば現在の交通条件を示す受信されたライブデータから成るものではない。ホーム位置が変化しないであろうこと、そして静的データはユーザの走行距離不安症を低減するために安全な戻り範囲の十分な近似を提供しうることが想定されうるので、これは作用するのである。到達可能なエリアを永続メモリに格納し、現在到達可能な範囲内の位置との比較のためにそれらを取得することは利点がありうる。これは、（例えば、ホーム位置の変化、又は地図データの変化を説明するために）必要でない限り到達可能なエリアを継続的に再計算するのは計算コストが高いので、当該技術が、限定された処理能力の装置、例えばユーザのスマートフォンで実行されている場合に特に利点がある。しかしながら、例えば、処理能力がより限定されないように方法がサーバ上で適用される場合、例えば現在又は最近の交通条件を説明するより正確な近似を提供するために、ホーム位置の周囲の到達可能なエリア及び境界は、より定期的に再計算されてもよいことも熟考される。
【０１４１】
本発明が任意の実施形態を参照して記載されてきたが、添付の特許請求の範囲に記載の本発明の範囲から逸脱することなく形態及び詳細の様々な変更がなされてもよいことが当業者により理解されるだろう。
【図１】
2019515266.tif 000003
【図２】
2019515266.tif 000004
【図３】
2019515266.tif 000005
【国際調査報告】
2019515266.tif 000006
2019515266.tif 000007