(57)【特許請求の範囲】
【請求項１】
車両の走行可能距離を判定するシステムであって、
車両に関連するパラメータのセットを記憶するストレージ要素と、
前記車両の位置に関連する地理的区域に関する情報を読み出す地図評価要素であり、読み出された前記情報は、前記地理的区域の使用可能な道路に関連する複数のリンクを有し、各々のリンクはコスト価値を含む、前記地図評価要素と、
前記パラメータのセットおよび読み出された前記情報の少なくとも一部に基づいて、前記車両の位置から外側に延びる複数の経路を識別するために前記複数のリンクを評価することにより、前記車両の前記走行可能距離を判定し、更に走行可能距離を示すポリゴンを生成する処理要素であり、前記経路の各々は、目標コストより低い、合計されたコスト価値を有するリンクのセットを有する前記処理要素と、
を備える、システム。
【請求項２】
読み出された前記情報は、前記地理的区域の使用可能な道路に関連するリンクのセットを含む請求項１に記載のシステム。
【請求項３】
前記リンクのセットの各リンクは、関連する道路エネルギコスト係数および関連する空気抵抗エネルギーコスト係数を有し、前記各係数は記憶されまたは算出される請求項２に記載のシステム。
【請求項４】
前記道路エネルギコスト係数および前記空気抵抗コスト係数は、前記車両とは独立している請求項３に記載のシステム。
【請求項５】
道路リンク間における移動は、それぞれ関連するエネルギコストを有する請求項３に記載のシステム。
【請求項６】
前記処理要素は、ビットマップベースのアルゴリズムを実行することにより前記走行可能距離を判定する請求項１に記載のシステム。
【請求項７】
前記パラメータのセットは、質量、断面積および使用可能な燃料を含む請求項１に記載のシステム。
【請求項８】
コンピュータシステムを用いて車両の走行可能距離を予測する自動化された方法であって、
複数のリンクを含んだ地理的区域に関する地図情報を読み出し、
前記読み出された情報の少なくとも一部に基づいて、前記車両から複数の方向で半径方向外側に延びる複数の経路を識別するために前記複数のリンクを評価することにより、走行可能距離リンクのセットを生成し、
前記走行可能距離リンクのセットの少なくとも一部に基づいてバイナリビットマップを生成し、
前記バイナリビットマップ内において前記走行可能距離リンクのセットをレンダリングし、
前記レンダリングしたリンクをトレースすることにより前記車両の走行可能距離の多角形輪郭を生成する、方法。
【請求項９】
さらに、前記ビットマップの基本座標およびスケール係数を算出する請求項８に記載の自動化された方法。
【請求項１０】
複数の走行可能距離に関連付けられた複数のバイナリビットマップを更に生成し、
前記複数の走行可能距離の各走行可能距離は使用可能な燃料の相対量に関連する請求項８に記載の自動化された方法。
【請求項１１】
前記複数の走行可能距離は、使用可能な燃料の５０％、使用可能な燃料の７５％、および使用可能な燃料の１００％に相当する請求項１０に記載の自動化された方法。
【請求項１２】
前記走行可能距離リンクのセットをレンダリングすることは、前記走行可能距離リンクのセットを受信することを含み、各リンクは、ノードのセットおよび形状点のセットを含み、すべての点が評価されるまで、
第１の点を前記ノードのセットまたは前記形状点のセットから読み出すことと、
次の点を前記ノードのセットまたは前記形状点のセットから読み出すことと、
前記の点が重ならない場合は、前記第１の点と前記次の点との間に線を引くことと、
を繰り返し実行する、請求項８に記載の自動化された方法。
【請求項１３】
さらに、前記車両に関連する動作パラメータを読み出す請求項８に記載の自動化された方法。
【請求項１４】
さらに、前記車両の運転手に関連する情報を読み出す請求項８に記載の自動化された方法。
【請求項１５】
コンピュータシステムを用いて、車両の走行可能距離の予測のために地図データを分割して保存する自動化された方法であって、
地図の区域に対応するデータを読み出し、
前記地図の区域をタイルのセットに分割し、
前記読み出されたデータの一部を、前記タイルのセットの各タイルと関連付け、
前記タイルのセット内の各タイルと関連づけられたタイルデータ構造を、前記タイルデータ構造が読み出され解析されるように、生成及び保存する、方法。
【請求項１６】
前記タイルのセットの各タイルは、前記セット内の他のタイルと同じ大きさである請求項１５に記載の自動化された方法。
【請求項１７】
前記読み出されたデータは、複数のリンクおよび複数のノードを含む請求項１５に記載の自動化された方法。
【請求項１８】
さらに、
前記複数のリンクの各リンクを評価して、前記リンクが前記タイルのセット内の複数のタイルにわたるかどうかを判定し、
前記リンクが複数のタイルにわたる場合には、前記リンクが２つのタイルの境界を通過する各点にノードを追加することによって、前記リンクを少なくとも２つのサブリンクに分割する、請求項１７に記載の自動化された方法。
【請求項１９】
各リンクは、長さ、速度、複数の形状点および接続されたノードのセットを含む請求項１７に記載の自動化された方法。
【請求項２０】
さらに、各リンクと、各リンクの接続されたリンクのセットのコストを判定することによって前記読み出されたデータを最適化し、前記コストと各タイルの接続されたリンクのセットを記憶する、請求項１９に記載の自動化された方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への相互参照
本出願は、２０１３年６月２１日出願の米国特許出願番号第１３／９２４，５１２号、および２０１３年３月１５日出願の米国仮特許出願番号第６１／８０１，０１１号に対する優先権を主張する。
【背景技術】
【０００２】
車両は社会のいたるところに存在する。車両運転者は、車両の走行可能距離を正確に判定可能となる情報を持たない。さらに、走行可能距離を推測する現在の方法（例えば、車両の残りの燃料に平均的な燃費を乗ずること）では、正確な結果を得られず、それを原因として、または他の要因と組み合わさって、予測した距離と実際の距離との間に重大な誤差が生じることもある。
【０００３】
さらに、電気自動車（ＥＶ）は、ますます社会に普及してきている。ただし、利用可能な社会基盤が限られているため、ＥＶの運転者の多くは、充電スタンドの場所を見つけることができないこともあり、または車両がスタンドに到着するかを判断することができないこともある。
【０００４】
したがって、車両の走行可能距離を正確に予測可能であり、ユーザフレンドリーな地図を用いるインターフェースを提供可能なシステムに対する需要がある。
【発明の概要】
【０００５】
いくつかの実施形態は、車両に関連するデータを受信し、少なくとも１つの多角形を決定することができるシステムを提供する。多角形は、車両が使用可能な燃料を使いきるまで、任意の使用可能なパスウェイに沿って走行可能な走行可能距離を示す。
【０００６】
本発明の第１の代表的な実施形態は、予測される車両の走行可能距離を判定するように適応されるシステムを提供する。システムは、車両に関連するパラメータのセットを記憶するように適応されるストレージ要素と、車両の位置に関連する地理的区域に関する情報を読み出すように適応される地図評価要素と、予測された車両の走行可能距離を、少なくとも部分的にパラメータのセットおよび読み出された情報に基づいて、判定するように適応される処理要素とを含む。
【０００７】
本発明の第２の代表的な実施形態は、コンピュータシステムを用いて車両の走行可能距離を予測する自動化された方法を提供する。当該方法は、地理的区域に関する複数のリンクを備える地図情報を読み出すことと、走行可能距離の予測リンクのセットを少なくとも部分的に読み出された情報に基づいて生成することと、モノクロムビットマップを少なくとも部分的に走行可能距離の予測リンクのセットに基づいて生成することと、モノクロムビットマップ内の走行可能距離の予測リンクのセットをレンダリングすることと、レンダリングしたリンクをトレースして、車両の走行可能距離の多角形輪郭を生成することとを含む。
【０００８】
本発明の第３の代表的な実施形態 は、コンピュータシステムを用いて、車両の走行可能距離予測のために地図データをキャッシングする自動化された方法を提供する。当該方法は、地図の区域に対応するデータを読み出すことと、地図区域をタイルのセットに分割することと、読み出されたデータの一部分を、タイルのセットの各タイルと関連付けることとを含む。
【０００９】
前述の発明の概要は、本発明のいくつかの実施形態を簡潔に紹介することを目的とする。本書に開示されるすべての主題の紹介または概要であることを意図するものではない。以下の発明を実施するための形態および発明を実施するための形態で参照される図面（または「図」または「ＦＩＧ」）は、さらに概要で説明した実施形態および他の実施形態を説明している。したがって、本明細書に記載するすべての実施形態を理解するためには、発明の概要、発明を実施するための形態および図面が必要である。さらに、請求される主題は、発明の概要、発明を実施するための形態および図面概要制限の例示的な詳細には限定されず、添付請求項によって定義される。なぜなら、請求される主題は、本発明の精神から逸脱せずに、他の特定の形式においても実現されうるからである。
【図面の簡単な説明】
【００１０】
本発明の新規な特徴は添付の請求項に規定される。ただし、説明を目的として、本発明の複数の実施形態を以下の図面で説明する。
【００１１】
図１は、本発明の代表的な実施形態による車載システムの概略ブロック図を例示する。
【００１２】
図２は、いくつかの実施形態の独立型システムの概略ブロック図を例示する。
【００１３】
図３は、いくつかの実施形態のソフトウェアシステムの概略ブロック図を例示する。
【００１４】
図４は、いくつかの実施形態が提供するグラフィカルユーザインターフェース（ＧＵＩ）の様々な例を例示する。
【００１５】
図５は、道路構造例に基づいて車両区分を有する概念的な地図を例示する。
【００１６】
図６は、端部点および複数の順序付き形状点を有するリンクを例示する。
【００１７】
図７は、いくつかの実施形態が用いる形状点のセットおよび関連するパスの傾斜を表すｘ−ｙプロットを例示する。
【００１８】
図８は、パスの傾斜を近似するために用いるアルゴリズムに関連するｘ−ｙプロットを例示する。
【００１９】
図９は、いくつかの実施形態の車両コストモデルを用いるシステムの概略ブロック図を例示する。
【００２０】
図１０は、いくつかの実施形態における、適応モデルを実施するために用いる概念的なシステムの概略ブロック図を例示する。
【００２１】
図１１は、いくつかの実施形態における、適応モデルを実施するために用いるオンライン／オフラインシステムの概略ブロック図を例示する。
【００２２】
図１２は、いくつかの実施形態における、車両排気ガスの推定を生成するために用いるシステムの概略ブロック図を例示する。
【００２３】
図１３は、いくつかの実施形態が用いる、データ構造の概念的なセットのデータ構造図を例示する。
【００２４】
図１４は、いくつかの実施形態がセンタアウト実装で用いるデータ構造の概念的なセットのデータ構造図を例示する。
【００２５】
図１５は、いくつかの実施形態が走行可能距離の予測を生成するために用いる概念的な処理のフローチャートを例示する。
【００２６】
図１６は、いくつかの実施形態がマルチステージ走行可能距離の予測計算および／または表示を実装するために用いる概念的な処理のフローチャートを例示する。
【００２７】
図１７は、いくつかの実施形態のマルチステージ予測アルゴリズムに関連する複数のＧＵＩ例を例示する。
【００２８】
図１８は、展開アルゴリズムを用いて車両の走行可能距離を判定するために用いる処理のフローチャートを例示する。
【００２９】
図１９は、図１８の処理の結果を表すいくつかの実施形態のＧＵＩ例を例示する。
【００３０】
図２０は、センタアウトアルゴリズムを用いて車両の走行可能距離を判定するために用いる処理のフローチャートを例示する。
【００３１】
図２１は、いくつかの実施形態における、最も近いノードを特定するために用いる処理のフローチャートを例示する。
【００３２】
図２２は、識別された最も近いノードが候補ノードに置換可能かどうかを判定するために用いる処理のフローチャートを例示する。
【００３３】
図２３は、図２２の処理の評価基準を示すグラフィカル表示を例示する。
【００３４】
図２４は、いくつかの実施形態における、多角形を予測する際に自己横断する線を排除するために行われうる補正を示すグラフィカル表示を例示する。
【００３５】
図２５は、既存の多角形が横断されるいくつかの実施形態における、複雑な形状を有する多角形の例および対応する検証を示すグラフィカル表示を例示する。
【００３６】
図２６は、図２０の処理と同様なセンタアウト予測の結果を表すいくつかの実施形態のＧＵＩ例を例示する。
【００３７】
図２７は、ビットマップベースのアルゴリズムを用いて、車両の走行可能距離を予測するために用いる処理のフローチャートを例示する。
【００３８】
図２８は、図２７の処理の結果を表すいくつかの実施形態のＧＵＩ例を例示する。
【００３９】
図２９は、いくつかの実施形態における、制限区域の処理に関連する概念的な地図を例示する。
【００４０】
図３０は、いくつかの実施形態が地図区域内の制限区域を特定し、このような区域と境界を接する道路にマークを付けるために用いる概念的な処理のフローチャートを例示する。
【００４１】
図３１は、図３０の処理の入力および出力を表すいくつかの実施形態のＧＵＩ例を例示する。
【００４２】
図３２は、効率的なデータ消費およびアクセスを促進するために用いられうる部分（または「タイル」）に分割された地図区域のグラフィカル表示を例示する。
【００４３】
図３３は、データに必要なメモリが小さくなるように、地図データをキャッシュするために用いられうるデータ構造図を例示する。
【００４４】
図３４は、地図データの読み出しおよび使用を最適化するためにいくつかの実施形態が用いる処理のフローチャートを例示する。
【００４５】
図３５は、車両の走行可能距離を色付きのリンクを用いて表示するいくつかの実施形態のＧＵＩ例を例示する。
【００４６】
図３６は、混色リンクを用いて車両の走行可能距離を表示するいくつかの実施形態のＧＵＩ例を例示する。
【００４７】
図３７は、本発明のいくつかの実施形態を実装可能なコンピュータシステムの概略ブロック図を概念的に例示する。
【発明を実施するための形態】
【００４８】
本発明の以下の詳細な説明において、本発明の実施例および実施形態を記載し、説明する。ただし、本発明は記載される実施形態に限定されず、本発明を特定の詳細および実施例を用いずに実施されうることは、当業者には明白であり、明らかであろう。
【００４９】
上記または下記の様々な実施例は、走行可能距離の予測、走行可能距離の予測アルゴリズム、および／または走行可能距離に関連する他の要因に関するが、走行可能距離は、いくつかの実施形態の性能の一例として用いられる。さらに車両の走行可能距離の予測に加えて（またはその代わりに）、いくつかの実施形態は、車両ルートを決定する性能および／または上記または下記に記載するものと同一のシステム、アルゴリズム、データ構造などを用いた車両排気ガスを推定する性能を含んでいてもよい。
【００５０】
上記または以下に記載する特徴は、適切な種々の車両および／または車両の種類に適用される。例えば、いくつかの実施形態は、自動車、トラック、バン、オートバイ、ＥＶなどの「路上」車両で用いられうる。別の例では、いくつかの実施形態はスノーモービル、全地形万能車（ＡＴＶ）などのオフロード車で用いられうる。さらに別の実施例では、いくつかの実施形態は、個人用の船、ボート、シップ、潜水艦、水中スクータ（ＤＰＤ）などの様々な種類の船舶で用いられうる。別の例では、いくつかの実施形態は、飛行機、ヘリコプタなどの様々な種類の航空機で用いられうる。さらに別の例では、いくつかの実施形態は宇宙船、月面車などの様々な種類の有人または無人車両で用いられうる。
【００５１】
本発明のさらに複数の詳細な実施形態を以下のセクションに記載する。セクションＩはいくつかの実施形態のシステムの概念的な概要を提供する。次に、セクションＩＩは、車両性能をモデルとするために用いる様々なアルゴリズムおよび構造を記載する。次に、セクションＩＩＩは、様々な走行可能距離の予測アルゴリズムを記載する。次に、セクションＩＶは、いくつかの実施形態の表示アルゴリズムおよびＧＵＩを記載する。最後に、セクションＶは、本発明の実施形態のいくつかを実装するコンピュータシステムを記載する。
Ｉ．システム概要
【００５２】
サブセクションＩ．Ａはいくつかの実施形態のハードウェアアーキテクチャの概念的な説明を提示する。次に、サブセクションＩ．Ｂはいくつかの実施形態の概念的なソフトウェアアーキテクチャを説明する。次に、サブセクションＩ．Ｃはいくつかの実施形態のＧＵＩ例を説明する。最後に、サブセクションＩ．Ｄはいくつかの実施形態に関連する様々な地図の属性を説明する。
【００５３】
上記および／または以下に記載の様々なシステム、構成部品、処理、および／または他の特徴は、様々の異なる方法で実装しうる。例えば、いくつかの実施形態は、ハードウェア要素およびソフトウェア要素の組み合わせを含んでいてもよい。別の例では、様々なシステム要素は、様々な個別の装置または要素（例えば、スマートフォン、車両通信バス、車載用ヘッドユニットまたはインフォテインメントユニットなど）によって提供される。いくつかの実施形態は、完全な車載システムとして提供される。このようなシステムは、必要に応じて或いは好みに応じて、外部装置と相互作用することができうる。いくつかの実施形態は、ユーザと通信し（例えば、リアルタイムに運転手にフィードバックし、運転手の性能データをフリート監督者にダウンロードするなど）、様々なシステム要素および／または特徴と相互作用することができる要素および／または特徴を含んでいてもよい。
Ａ．ハードウェアアーキテクチャ
【００５４】
図１は、本発明の代表的な実施形態による車載システム１００の概略ブロック図を例示する。具体的には、本図は様々な概念的なモジュールを示す。モジュールによって、システムは車両と相互作用し、走行可能距離の予測を判定し、および／またはユーザ（例えば、車両の運転者または乗客）と相互作用することができる。
【００５５】
図示するように、システムは、１または複数の入力要素１１０、燃料計１２０、位置センサ１３０、環境センサ１４０、および／または他の車両センサ１５０を含んでいる。さらに、システムは、１または複数のプロセッサ１６０、オプションのグラフィックスプロセッシングユニット（ＧＰＵ）および／またはフィールドプログラマブルゲートアレイ（ＦＰＧＡ）、少なくとも１つの表示要素１８０、ストレージ１９０のセット、およびオプションの通信（または接続）モジュール１９５を含んでいてもよい。
【００５６】
各入力要素１１０によって、ユーザはシステムと相互作用できる。このような要素はタッチ画面、キーボード、ハンドル制御装置、回転つまみ、ブルートゥースまたは外部入力装置への無線リンクなどを含んでいてもよい。
【００５７】
各燃料計１２０は、車両が利用可能な燃料の量（および／または相対量）を判定可能である。このような燃料計は、適切な種々の要素を適切な種々のユニットを用いて計測してもよい。例えば、ガソリンのレベル（例えば、ガロン単位、満タンに対する割合など）、バッテリ充電レベル（例えば、ワット時（Ｗ−ｈ）、完全充電に対する割合など）などを計測してもよい。単一の種類の燃料計（例えば、ガソリン燃料の車両のガソリン計、電気自動車のバッテリ充電計、圧縮天然ガス（ＣＮＧ）車両用のガソリンガロン当量（ＧＧＥ）など）を備えうる車両もあれば、複数の種類の燃料計（例えば、ハイブリッド車両のガソリン計およびバッテリ充電計）を備えうる車両もある。
【００５８】
位置センサ１３０のセットは、車両の位置を様々な適切な方法で判定可能である。このような位置センサは、例えば、全地球型測位システム（ＧＮＳＳ）センサ（ＧＰＳ、全地球型測位システム（ＧＬＯＮＡＳＳ）、ガリレオ、北斗衛星測位システム（ＢＤＳ）など）、ＧＮＳＳ補強システム、慣性および絶対位置センサ（ジャイロスコープ、加速度計、車速パルスセンサ、差速パルス、コンパスなど）、無線信号位置決めシステム（Ｗｉ−Ｆｉ位置決め、携帯電話用基地局の三角測量など）、および任意の関連するハードウェアおよび／またはソフトウェアを含んでいてもよい。
【００５９】
各環境センサ１４０は、適切な環境要因を計測可能である。例えば、このようなセンサは（内部および／または外部）温度、湿度、高度、気圧などを計測してもよい。
【００６０】
他の各車両センサ１５０（および／またはセンサのセット）は、車両の性能に影響し得る様々な他の適切なパラメータを計測しうる。このようなパラメータは、例えば、車両の重量、乗客数、タイヤ圧、修理履歴、流体温度などを含んでいてもよい。
【００６１】
様々な要素１１０〜１５０はそれぞれ、必要に応じて（例えば、バス、ネットワーク、および／または車両に関連する他の通信要素によって）、要素の操作に影響を与えることもある命令および／またはデータを受信可能である。いくつかの実施形態では、様々な要素は、様々な適切なハードウェアおよび／またはソフトウェアインターフェース（例えば、様々なケーブル、コネクタ、入力モジュール、変換モジュール（例えば、アナログからデジタル、デジタルからアナログなど）、コントローラ区域ネットワーク（ＣＡＮ）バス、メディアオリエンテッドシステムトランスポート（ＭＯＳＴ）バス、車載診断（ＯＢＤ）インターフェースなど）によって、プロセッサに接続してもよい。
【００６２】
各プロセッサ１６０は、様々な適切な方法で命令を実行し、および／またはデータを処理する。プロセッサは、他のシステム要素間で、必要に応じて通信可能である。
【００６３】
各ＧＰＵおよび／またはＦＰＧＡ１７０は、様々な計算および／または表示処理機能を提供し、それによって、通常はプロセッサ１６０によって実施されることもある一部の操作をオフロードして、効率的なシステムの操作を可能にしてもよい。
【００６４】
各表示要素１８０によって、ユーザはシステム１００の様々な出力を見ることができる。例えば、表示要素１８０は、様々な地図、走行可能距離の予測、ユーザインターフェースなどを必要に応じて表示してもよい。いくつかの実施形態では、表示要素を入力要素１１０と組み合わせ、タッチ画面要素を提供してもよい。
【００６５】
ストレージ１９０のセットは、操作中に様々なシステム構成部品で用いられる。様々なセットの命令および／またはデータ要素を記憶することができてもよい。さらに、ストレージは、いくつかの実施形態により利用されうる地図データを記憶してもよい。このような地図データは、プロセッサ１６０およびいくつかの実施形態の関連ソフトウェアを用いることによって、特定され、読み出され、記憶され、および／または他の方法で操作されうる。
【００６６】
通信モジュール１９５は、他のリモートおよび／またはローカルシステムと、１または複数のネットワークを通じて通信しうる。通信モジュールは、例えば、スマートフォン、テレマティクスサーバ、様々なウェブサービスプロバイダ、１または複数の車載インフォテインメントシステムなどと通信できる。このような通信モジュールは、必要に応じて、ローカルまたはグローバルネットワークを通じて（例えば、イーサネット、Ｗｉ−Ｆｉ、ブルートゥース、３Ｇ、ＬＴＥなど）通信してもよい。したがって、システム１００は例えば、現在の天気または天気予報、リアルタイムまたは予測される交通状況などの環境情報をリモートシステムから、受信してもよい。システム１００はまた、リモートサーバ、スマートフォン、タブレット、および／または他の適切な装置に、推定走行可能距離、ロギング情報、状態情報、表示範囲の多角形などを表示または送信してもよい。
【００６７】
操作中に、ユーザは走行可能距離の予測システム１００を（例えば、入力要素１１０を操作することによって）呼び出すことができる。システム１００は次に、様々な入力要素１１０〜１５０を監視し、および／または通信して、様々な適切なパラメータを読み出す。プロセッサ１６０は、少なくとも部分的に読み出されパラメータに基づいて様々な操作を実施する。このような操作は、少なくとも部分的に、ストレージ１９０から読み出されたデータおよび／または命令に基づいていてもよい。プロセッサ１６０はまた、ＧＰＵ／ＦＰＧＡ１７０および／または他の要素と相互作用して、ユーザに提示する視覚表示を作成してもよい。このような表示は、表示要素１８０に送信されて出力される。
【００６８】
当業者は、システム１００は元来概念的なものであり、本発明の精神から逸脱せずに様々な特定の方法で実装されうることを認識するであろう。例えば、具体的な構成部品および通信パスの方法を有するシステムを記載してきたが、異なるシステムは、様々な他の構成部品を含んでいても（および／または様々な構成部品を除去しても）よく、および／または様々な他の通信パスウェイ（例えば、様々な構成部品のそれぞれにアクセス可能な通信バス）を含んでいてもよい。
【００６９】
図２は、いくつかの実施形態の独立型（つまり、車外の）システム２００の概略ブロック図を例示する。具体的には、本図はシステムを示す。本システムは、オフラインデータ（例えば、ログファイル）および／または（例えば、車両からリアルタイムに受信する）オンラインデータを用いて動作してもよい。図示するように、システムは、図１に関して前述したものと同一のプロセッサ１６０、ＧＰＵ／ＦＰＧＡ１７０、表示要素１８０、およびストレージ１９０を含む。
【００７０】
システム２００はさらに、ストレージ２１０の第１のセット、テレマティクスサーバ２２０、およびテレマティクスサーバ２２０に関連するストレージ２３０の第２のセットを含む。ストレージ２１０の第１のセットは、様々なログファイルを含んでいてもよい。ログファイルは、様々な入力要素（例えば、前述の要素１１０〜１５０）から受信する情報と類似の情報を含む。テレマティクスサーバ２２０は、情報通信技術（例えば、インターネット、ローカルエリアネットワーク（ＬＡＮ）、無線ローカルエリアネットワーク（ＷＬＡＮ）など）を利用して、システム２００と相互作用するように適応されうる。ストレージ２３０は、テレマティクスサーバ２２０によって用いられる様々な命令および／またはデータを含んでいてもよい。
【００７１】
システム２００はさらに、１または複数のウェブサービス２４０と相互作用する。ウェブサービス２４０は、地図データ、気象条件（過去、現在および予想）、交通情報（リアルタイム、過去、予測）などの追加の関連情報を提供してもよい。このようなウェブサービスは、１または複数の第三者（例えば、ＡＰＩまたは他の適切なインターフェースまたはリソース）によって提供されてもよい。
【００７２】
操作中に、データはストレージ２１０および／またはテレマティクスサーバ２２０間で転送されうる。このような情報は、システム２００によって用いられ、前述のシステム１００と類似の方法で動作してもよい。
【００７３】
当業者は、システム２００は元来概念的なものであり、本発明の精神から逸脱せずに様々な特定の方法で実装されうることを認識するであろう。例えば、具体的な構成部品および通信パスの方法を有するシステムを記載してきたが、異なるシステムは、様々な他の構成部品を含んでいても（および／または様々な構成部品を除去しても）よく、および／または様々な他の通信パスウェイ（例えば、様々な構成部品のそれぞれにアクセス可能な通信バス）を含んでいてもよい。さらに、システムは独立型として説明してきたが、ログベースまたはテレマティクスベースのシステムも、車載または他の適切な方法（例えば、スマートフォン、タブレットなどのユーザ装置）で提供されてもよい。
Ｂ．ソフトウェアアーキテクチャ
【００７４】
図３は、いくつかの実施形態のソフトウェアシステム３００の概略ブロック図を例示する。図示するように、システムは、１または複数の車両インターフェース３１０、１または複数の他のインターフェース３２０、予測エンジン３３０、ＧＰＵ／ＦＰＧＡインターフェース３４０、表示インターフェース３５０、およびデータベースのセット３６０を含んでいる。
【００７５】
各車両インターフェース３１０は、プロセッサ１６０と１または複数の入力装置（例えば、前述の入力要素１１０〜１５０）との間で通信できる。他のインターフェース３２０はそれぞれ、１または複数の他の要素および／またはシステム（例えば、スマートフォン、カーナビシステムなどの装置）と通信するように適応されてもよい。
【００７６】
予測エンジン３３０は、データおよび／または命令を、様々な他のシステム要素の中から必要に応じて送信および受信する。エンジンは様々な計算アルゴリズム（例えば、走行可能距離の予測、ルート計算、排出量推定など）を用いて、関連する予測を判定し、および／または様々なユーザインターフェースを生成して、判定された予測を表示することができる。
【００７７】
ＧＰＵ／ＦＰＧＡインターフェース３４０によって、予測エンジン３３０は１または複数のＧＰＵおよび／またはＦＰＧＡと必要に応じて通信できる。表示インターフェース３５０によって、システムは表示データを視覚表示（例えば、車載用ヘッドユニット、スマートフォン画面など）に提供できてもよい。データベース３６０は、いくつかの実施形態の様々なシステム構成部品の操作に関連する様々なデータ要素（例えば、地図データベース、車両プロファイル、地理的情報など）を含んでいてもよい。
【００７８】
操作中に、予測エンジン３３０はデータを様々な入力インターフェース３１０〜３２０から受信し、受信したデータを処理してもよい（処理はＤＢ３６０から受信したデータに少なくとも部分的に基づいていてもよい）。データ処理は、データをＧＰＵ／ＦＰＧＡインターフェース３４０から関連するＧＰＵおよび／またはＦＰＧＡまで送ることによって、少なくとも部分的に実施されてもよい。処理されたデータは、表示インターフェース３５０に、関連する表示がデータをユーザに提供できるような形で提供されてもよい。
【００７９】
システム３００は、様々な組み合わせのクライアントアプリケーション（つまり、クライアント装置上で動作するアプリケーション）、サーバアプリケーション（つまり、１または複数のリモートサーバ装置上で動作するアプリケーション）などを用いて実装されうる。さらに、このようなシステムは、様々な組み合わせのハードウェア要素（例えば、スマートフォン、車載用ヘッドユニット、サーバなど）を用いて実装されうる。
【００８０】
当業者は、システム３００は元来概念的なものであり、本発明の精神から逸脱せずに様々な特定の方法で実装されうることを認識するであろう。例えば、具体的な構成部品および通信パスの方法を有するシステムを記載してきたが、異なるシステムは、様々な他の構成部品を含んでいても（および／または様々な構成部品を除去しても）よく、および／または様々な他の通信パスウェイ（例えば、様々な構成部品のそれぞれにアクセス可能な通信バス）を含んでいてもよい。さらに、予測エンジン３３０は単一の要素として説明してきたが、異なる実施形態は、様々な異なるサブ要素（例えば、多角計算エンジン、環境評価エンジンなど）を含んでいてもよい。
Ｃ．グラフィカルユーザインターフェース例
【００８１】
図４は、表示区域４００を例示する。表示区域４００は、いくつかの実施形態によって提供される様々なグラフィカルユーザインターフェース（ＧＵＩ）４１０〜４２０の例を表示可能である。表示区域４００は、１または複数の適切な視覚表示要素（例えば、要素１８０）によって提供されてもよい。
【００８２】
図示するように、第１のＧＵＩ４１０は、表示区域４００にグラフィカル要素のセットを表示してもよい。このような要素は、例えば、車両位置４３０、制限区域４４０（つまり、湖、公園、湾、軍基地など車両が侵入することができない区域、または侵入が制限されている）、１または複数の主要道路４５０、および／または１または複数の細い道路４６０を表示してもよい。
【００８３】
第２のＧＵＩ４２０は、使用可能な燃料の５０％に関連する走行可能距離（または何らかの他の閾値および／またはパラメータ）を示す区域４７０、使用可能な燃料の７５％に関連する走行可能距離を示す区域４８０、および使用可能な燃料の１００％に関連する走行可能距離を示す区域４９０の指示を表示してもよい。
【００８４】
下記のように、様々な走行可能距離は、様々な適切な方法で表示されうる。例えば、いくつかの実施形態は、異なる色、陰影のパターンまたは濃度などを用いて走行可能距離４７０〜４９０を差別化してもよい。
【００８５】
当業者は、ＧＵＩ４１０〜４２０は元来概念的なものであり、本発明の精神から逸脱せずに様々な特定の方法で実装されうることを認識するであろう。例えば、具体的な視覚構成部品および特徴を有するＧＵＩを記載してきたが、異なるＧＵＩは、様々な他の構成部品を含んでいても（および／または様々な構成部品を除去しても）よく、および／または様々な他の特徴を含んでいてもよい。
Ｄ．地図属性
【００８６】
様々な地図の属性は、いくつかの実施形態の様々な要素に適用されるアルゴリズムによって用いられる。例えば、いくつかの実施形態は、長さ（例えば、２つの形状点の間の長さ、リンクの長さなど）、速度（例えば、速度制限情報、道路の種類ごとの平均速度など）、傾斜および／または高さ（例えば、各形状点に関連する高度情報、形状点に関連する傾斜勾配または下り傾斜勾配など）、道路のカーブ、交通パターン（例えば、過去の交通速度、実際の交通速度など）、種類の道路（例えば、「レベル１」または主要道路、「レベル２」または二級道路など）、および／または他の要素を使用してもよい。
【００８７】
図５は、道路構造例に基づく車両区分５１０〜５２０を有する概念的な地図５００を例示する。本実施例では、一方通行５１０の車両区分もあれば、両方向通行５２０の車両区分もある。区分は、交差点、横断歩道、信号、停止標識などの物理的な特徴内で関連属性（例えば速度、道路の級など）が同一である連続した一本の道路として定義されてもよい。本実施例では、白丸５３０を用いて、区分のノード（例えば、信号、交差点など）を指定する。
【００８８】
図６は、端部点（または「ノード」）６１０および複数の順序付き形状点６２０を有するリンク（または「区分」）６００を例示する。本実施例では、第１のノード（または「参照ノード」）６１０はリンクの起点である。第２のノードはリンクの端部点である。リンクは、様々な属性（例えば、道路の級、掲示された速度制限、平均速度、長さ、車線の数、進行方向など）を含んでいてもよい。２つのノード６１０に加えて、リンクは、複数の順序付き形状点６２０を含んでいてもよい。形状点６２０は、形状点の世界座標（経度および緯度）、高度、および／または傾斜、カーブ、向きなどの他の適切な形状点の属性を含んでいてもよい。本実施例では、形状点は左から右に（および「Ａ」から「Ｈ」にアルファベット順に）進んでいる。データベースまたはメモリに記憶されるとき、形状点の座標は絶対座標、相対座標（デルタ）、近似曲線（例えばスプライン）などとして提示されてもよく、標準的な圧縮方法を用いて圧縮されてもよい。
【００８９】
各区分（および／または形状点）は、適切な種々の属性を有していてもよい。例えば、各区分は、１または複数の方向（例えば、本来の方向、進行方向など）に関連してもよい。区分（または「リンク」）の本来の方向は、リンクの形状点の順序に基づいていてもよい。いくつかの地図データベースは、例えば、点を左から右に（または西から東に）および上から下に（または北から南に）順序付けてもよい。
【００９０】
リンクの進行方向は、以下の様々な適切な方法で定義されてもよい（例えば、なし：進行はまったく認められない、順方向：本来の順方向に進行が認められる、逆方向：本来の方向とは逆方向に進行が認められる、進行は順方向と逆方向両方に認められるなど）。
【００９１】
当業者は、図５〜６の地図構造は、本発明の精神から逸脱せずに様々な特定の方法で実装されうることを認識するであろう。例えば、異なる実施形態では、各リンクに含まれる点の数が異なっていてもよい。別の例では、異なる実施形態は、様々な他の特徴または種類の道路（例えば、高速道路、有料道路などの複数車線の道路）を含んでいてもよい。
【００９２】
図７はいくつかの実施形態による形状点およびパスの関連する傾斜７１０のセットを表すｘ−ｙプロット７００を例示する。ｘ−ｙプロット７００は、本例の高度対直線距離を示す。図示するように、パス７１０は点７２０で開始し、点７３０まで伸びる。様々な形状点７４０はパス７１０に沿って含まれている。各形状点は、その点の傾斜角度を含んでいてもよく、起点７２０から終点７３０までのパス７１０の地理を画定してもよい。
【００９３】
異なる実施形態は、様々に異なる方法で形状点を画定してもよい（例えば、各形状点を具体的な高度に関連付けてもよく、各形状点は従前の形状点に基づいて傾斜の変化を画定してもよいなど）。
【００９４】
図８は、パスの傾斜を近似するために用いるアルゴリズムに関連するｘ−ｙプロット８００を例示する。プロットは、ｘ軸に距離およびｙ軸に高度を描く。図示するように、プロットは、実際のパス８１０（および関連する傾斜情報）、直線近似パス８２０、最大湾曲点８４０および最小湾曲点８５０を含む改良した近似傾斜パス８３０、最大高度８６０、最小高度８７０、および現在の高度８８０を含む。
【００９５】
いくつかの実施形態では、最大湾曲点８４０（プロット８００のｘ軸に沿った値として表される）は、リンク距離（または長さ）と、最大高度８６０と現在の高度８８０との間の差を最大高度８６０と最小高度８７０との間の差で割った数の積として算出されてもよい。同様に、いくつかの実施形態では、最小湾曲点８５０（プロット８００のｘ軸に沿った値として表される）は、リンク距離と、現在の高度８８０と最小高度８７０との差を最大高度８６０と最小高度８７０との差で割った数の積として算出されてもよい。
【００９６】
図８に示すように、傾斜を近似化するこのような手法によって、直線近似に対して結果が改良されてもよい。
ＩＩ．車両のモデリング
【００９７】
サブセクションＩＩ．Ａは、いくつかの実施形態が提供する基本的なコストモデルの概念的な説明を提供する。次に、サブセクションＩＩ．Ｂはいくつかの実施形態による車両のプロファイルを記載する。次に、サブセクションＩＩ．Ｃは、いくつかの実施形態における、基本的な車両のモデリングを実装するシステムの概念的な説明を提供する。サブセクションＩＩ．Ｄは、次に、いくつかの実施形態の適応コストモデルを説明する。次に、サブセクションＩＩ．Ｅは、いくつかの実施形態における、基本的な車両のモデリングを実装するシステムの概念的な説明を提供する。最後に、サブセクションＩＩ．Ｆは車両排気ガスの推定を記載する。
【００９８】
車両「コスト」は、様々な要素（例えば、エネルギ消費量、燃料消費量、運転時間、運転距離など）を含んでいてもよい。このように、いくつかの実施形態では、具体的なルートがエネルギ消費量の走行可能距離内にあるかを判定するだけではなく、具体的な目的地が時間の閾値内であるかを判定してもよい。
Ａ．基本的コストモデル
【００９９】
異なるコストモデルは、様々な異なるパラメータを含んでいてもよく、様々な判定可能な基準に関連していてもよい。このような基準は、すべての場合において判定可能でなくても（および／または他の方法で既知でなくても）よく、したがって、そのように推定されても、または他の方法で確認されてもよい。さらに、異なる具体的な実施形態は、異なるセットの動作基準を含んでいてもよい。このような基準は、例えば、空気抵抗、車両重量、傾斜勾配および／または高度、速度、交通特徴（例えば、停止標識、信号など）、回転コスト（例えば、典型的な回転に関連する減速および加速）、リアルタイムの交通（例えば、暑い日の交通渋滞は、通常の条件に対して不均衡な量のエネルギを使用する空調を使う原因となることもある）、運転スタイル、道路カーブなどを含んでいてもよい。
【０１００】
いくつかの実施形態では、エネルギコスト、ＥＣを下記の方程式（１）を用いて算出してもよい。式中、ＥＣはＷ−ｈ単位のエネルギコスト、Ｅｌｉｎｋはリンクを横切るためのエネルギコストであり（Ｗ−ｈ単位）、およびＥｎｏｄｅは、（例えば、回転することによって）リンクから接続するリンクに進むためのＷ−ｈ単位のコストである。
ＥＣ＝Ｅｌｉｎｋ＋Ｅｎｏｄｅ      （１）
【０１０１】
リンクコストは少なくとも部分的に道路の所定の直線部分を通るのに必要なエネルギ（つまり、走行抵抗）に基づいて算出される。走行抵抗を決定する際の主要な要因は、道路の転がり抵抗、空力抵抗、および登攀抵抗を含んでいてもよい。
【０１０２】
走行抵抗Ｆｗは、以下の方程式（２）を用いてニュートン単位で算出される。式中、ＦＲｏはニュートン単位の転がり抵抗であり、ＦＬはニュートン単位の空力抵抗であり、ＦＳｔはニュートン単位の登攀抵抗である。
Ｆｗ＝ＦＲｏ＋ＦＬ＋ＦＳｔ      （２）
【０１０３】
転がり抵抗ＦＲｏは、以下の方程式（３）を用いてニュートン単位で算出される。式中、ｆは転がり抵抗の係数（適切な値、例えば、０．００９、０．０１０、０．０１１などに設定）であり、ｍはキログラム単位の車両質量（ｍは車両の総重量、乗客の重量、および任意の他の負荷を含んでいてもよく、乗客の重量および他の負荷が不明の場合は推定してもよい）であり、ｇは毎秒平方メートル単位の重力加速定数であり、およびθは弧度法による道路の傾斜角度である。
ＦＲｏ＝ｆ・ｍ・ｇ・ｃｏｓ（θ）      （３）
【０１０４】
空力抵抗ＦＬは、以下の方程式（４）を用いてニュートン単位で算出される。式中、ｐは立法メートル当たりの重さ単位の空気密度（例えば、海抜高度２００メートルで１．２０２ｋｇ／ｍ３）であり、ｃｗは抵抗係数であり、少なくとも部分的に車両プロファイルに関連するパラメータに基づいていてもよい。Ａは平米単位で最大の車両の断面積であり、少なくとも部分的に車両プロファイルに関連するパラメータに基づいていてもよい。ｖはメートル単位の秒速の車両速度であり、ｖｏはメートル単位の秒速の逆風速度である（不明の場合はゼロにセットされてもよい）。
ＦＬ＝０．５・ｐ・ｃｗ・Ａ・（ｖ＋ｖｏ）２      （４）
【０１０５】
登攀抵抗ＦＳｔは、以下の方程式（５）を用いてニュートン単位で算出される。式中、ｍはキログラム単位の車両質量（ｍは車両の総重量、乗客の重量、および任意の他の負荷を含んでいてもよく、乗客の重量および他の負荷が不明の場合は推定してもよい）であり、ｇは毎秒平方メートル単位の重力加速定数であり、およびθは弧度法による道路の傾斜角度である。
ＦＳｔ＝ｍ・ｇ・ｓｉｎ（θ）      （５）
【０１０６】
走行抵抗Ｆｗは、道路エネルギコスト、Ｅｒｏａｄに以下の方程式（６）を用いて変換される。式中、ｄはメートル単位の進行した距離である（ｄはリンクの長さ、形状点間の距離などから求めてもよい）。
Ｅｒｏａｄ＝Ｆｗ・ｄ／３６００      （６）
【０１０７】
道路エネルギは、方程式（３）、（４）および（５）を方程式（２）に、次に（６）に代入し、結果として生じる下記方程式（７）によって算出される。
Ｅｒｏａｄ＝ｍ・（ｇ・ｄ／３６００）・（ｆ・ｃｏｓ（θ）＋ｓｉｎ（θ））＋Ａ・（０．５・ｐ・ｃｗ・ｖ２・ｄ）／３６００      （７）
【０１０８】
方程式（７）は以下の方程式（８）〜（１０）で書き換えられてもよい。
Ｅｒｏａｄ＝ｍ・ＣＲ＋Ａ・ＣＡ      （８）
式中、ＣＲ＝（ｇ・ｄ／３６００）・（ｆ・ｃｏｓ（θ）＋ｓｉｎ（θ））      （９）
ＣＡ＝（０．５・ｐ・ｃｗ・ｖ２・ｄ）／３６００      （１０）
【０１０９】
道路エネルギコスト係数ＣＲは次に、車両質量に係数を乗じて、実際のエネルギ値を算出することによって任意の車両に適用される。同様に、空気抵抗エネルギコスト係数ＣＡは、車両断面積Ａに係数を乗じて、実際のエネルギ値を算出することによって任意の車両に適用される。リンクエネルギＥｌｉｎｋは、リンク距離にわたる道路エネルギの値Ｅｒｏａｄとして算出されてもよい。
【０１１０】
いくつかの実施形態では、道路エネルギコスト係数および空気抵抗エネルギコスト係数は、道路リンクごとに事前に算出され、地図データベースと共に記憶される。それによって、アルゴリズムのより効率的なランタイム実装が可能となりうる。
【０１１１】
停止のエネルギコストＥｓｔｏｐは、以下の方程式（１１）を用いてＷ−ｈ単位で算出される。Ｅａｃｃは車両の加速中に使用されるエネルギであり、以下の方程式（１２）を用いて算出される。Ｅｒｅｇｅｎは回生ブレーキ（使用可能な場合）作動中に車両に戻るエネルギであり、以下の方程式（１３）を用いて算出される。方程式（１２）では、ＰｍａｘはＷａｔｔ単位の最大の車両の動力であり（車両のプロファイルパラメータから導かれてもよい）、ｔは秒単位の加速時間であり、ｖは車両の速度である。いくつかの実施形態では、加速時間ｔは、加速係数（車両のプロファイルパラメータから導かれてもよい）をｖに乗じることによって近似されてもよい。方程式（１３）では、Ｃｒｅｇｅｎは（車両のプロファイルパラメータから導かれてもよい）再生係数である。いくつかの実施形態は、他の係数（例えば、歯車動力の損失に関連する係数）を含んでいてもよい。
Ｅｓｔｏｐ＝Ｅａｃｃ−Ｅｒｅｇｅｎ      （１１）
Ｅａｃｃ＝Ｐｍａｘ・ｔ（ｖ）／３６００      （１２）
Ｅｒｅｇｅｎ＝（Ｃｒｅｇｅｎ・ｍ・ｖ２／２）／３６００      （１３）
【０１１２】
ノードコストは、ノードおよび／またはノードに関連する他の要因（例えば、交通密度、速度制限など）の種類に応じて、様々に異なる方法で算出される。
【０１１３】
例えば停止標識のノードコストΕｎｏｄｅは、以下の方程式（１４）を用いて算出される。式中、Ｅｓｔｏｐは、例えば方程式（１１）を用いて算出される停止のエネルギコストである。
Ｅｎｏｄｅ＝Ｅｓｔｏｐ      （１４）
【０１１４】
例えば交通信号のノードコストΕｎｏｄｅは、以下の方程式（１５）を用いて算出される。式中、ｐは赤信号に出会う確率（例えば、３０％）である。
Ｅｎｏｄｅ＝ｐ・Ｅｓｔｏｐ      （１５）
【０１１５】
他のすべての事例に対するノードコストΕｎｏｄｅは、以下の方程式（１６）を用いて算出される。Ｅｔｒａｎｓは、直線で、またはわずかな角度で進んだ場合の１つのリンクから別のリンクへの移動コストを表す。ａは回転角度であり、φは最小角度閾値であり、回転を特定するように用いられてもよい。Ｅｔ＿ｎｏｒｍは（例えば、右側通行の国における右折、一方通報の道路からの左折など）「直角」回転のために消費されるエネルギである。Ｅｔｒａｎｓは、接続するリンクの速度が同一の場合はゼロに設定されてもよく、第２のリンク（ｖ２）の速度が第１の（ｖ１）速度より早い場合はＥａｃｃ（ｖ２−ｖ１）として算出されてもよく、または第２のリンクの速度が第１のリンクの速度よりも遅い場合はＥｒｅｇｅｎ（ｖ１−ｖ２）として算出されてもよい。
ａ＜φの場合  Ｅｎｏｄｅ＝Ｅｔｒａｎｓ      （１６）
右折の場合  ＝Ｅｔ＿ｎｏｒｍ
左折の場合  ＝Ｅｓｔｏｐ
【０１１６】
直角回転コストＥｔ＿ｎｏｒｍは、以下の方程式（１７）を用いて算出される。式中、ｖ１は現在の（または「出発した」）リンクの速度であり、ｖ２は次の（または「目的とする」）リンクの速度であり、ｖｓは回転するために安全な速度であり、回転するために危険な速度に基づいて以下の求心加速方程式（１８）を用いて算出されてもよい。式中、Ｒｖは車両の回転半径であり（車両のプロファイルパラメータから導かれてもよい）、ｆｆはタイヤと道路との間の摩擦要因であり、最小予測値（例えば、０．３）に設定されてもよい。安全な速度ｖｓが、リンク速度（ｖ１またはｖ２）を上回る場合は、関連エネルギ構成部品（例えば、ＥａｃｃまたはＥｒｅｇｅｎ）はゼロに設定されてもよい。
Ｅｔ＿ｎｏｒｍ＝Ｅａｃｃ（ｖ２−ｖｓ）−Ｅｒｅｇｅｎ（ｖ１−ｖｓ）      （１７）
ｖｓ＝√（ｇ・Ｒｖ・ｆｆ）      （１８）
【０１１７】
リンクコストＥｌｉｎｋおよび前述のノードコストＥｎｏｄｅは、車両力学を用いて算出されてもよく、機械エネルギを表示してもよい。ただし、車両は異なる形（例えば、電気エネルギ）でエネルギを貯蔵してもよい燃料源（例えば、ガソリンタンク、バッテリなど）を有するであろう。このように、貯蔵されたエネルギは機械エネルギに変換されなければならないこともある。一例として、以下の方程式（１９）を用いて、ＥＶが所定の量の機械エネルギＥｍを生成するために必要な電気エネルギＥｅを算出してもよい。式中、ＰＴＥ（ｖ）は動力トレイン効率要因である（後述するように、様々な車両のプロファイルパラメータから導かれてもよい）。
Ｅｅ＝Ｅｍ／ＰＴＥ（ｖ）      （１９）
【０１１８】
エネルギコストＥｅは、（例えば、ガソリン動力車両では）エネルギコストを適切な変換係数で割ることによって、燃料量に変換される。いくつかの実施形態では、すべてのコスト計算は機械エネルギ値を用いて実施される。このように、任意の入力エネルギコストＥｅは、動力トレイン効率要因ＰＴＥ（ｖ）によって、下記の方程式（２０）で示すように低減されるべきである。
Ｅｃｏｓｔ＝Ｅｅ・ＰＴＥ（ｖ）      （２０）
【０１１９】
動力トレイン効率要因ＰＴＥ（ｖ）は、下記の方程式（２１）に示すように算出される。式中、ｖは速度であり、ａ、ｂ、ｃ、およびｄは関数のパラメータである。より正確な表示が望ましい場合は、高次多項式を用いてもよい。多項式関数は、（車両メーカーから入手可能な、または経験的に判定可能な）事前に既知の車両動力トレインデータ点から算出されてもよく、適切な方法（例えば、最小二乗）を用いてｎ次の多項式関数に補間されてもよい。
ＰＴＥ（ｖ）＝ａｖ３＋ｂｖ２＋ｃｖ＋ｄ      （２１）
【０１２０】
いくつかの実施形態は、動力トレイン効率（および／または他の適切な変数）を表として表示しうる。このような表を用いて、経験データ（例えば、動力トレイン効率値および関連する速度）を記憶してもよく、経験データ点間の直線近似を用いて値を生成してもよい。このような手法によって、効率的かつ容易な実装が可能となり、様々な値（例えば、動力トレイン効率）を判定するために必要な計算量および／またはメモリを削減することができる。
【０１２１】
いくつかの実施形態は、辞書（または「地図」）を用いてこのような表データを記憶してもよい。辞書の要点は速度（例えば、ｋｍ／ｈで測定）であり、値は対応する効率である。代替的に、表は速度と効率要因のペアで記憶されたアレイとして実装されてもよい。
【０１２２】
効率要因が所定の速度で必要とされる場合、二分探索法を用いて最近似値を検出してもよく、次に、直線近似を用いて必要な中間値を算出してもよい。
【０１２３】
ランタイム効率を改善するために、いくつかの実施形態では、表をフォーマットして、速度（例えば、ゼロから１６０ｋｍ／ｈまでの各整数値に対して）と、それぞれに対応する効率値とを固定したセットで持たせる。各効率値は前もって算出しておく。このような手法の結果として、要素がアレイで示され、記号は速度であり、値は効率要因である。正確さは、アレイの要素の数を増やすことによって改良されてもよい。所定の速度の効率値がランタイムに必要な場合は、最も近い値を見出しで迅速に検索しうる。
【０１２４】
いくつかの実施形態は、各要素に対して、値が補間か、または経験的に導出されるかを示す追加のフィールドを含んでいる。このようなフィールドは、例えば、ブールフラグとして実装されてもよい。
【０１２５】
いくつかの実施形態は、要素ごとに値が表で更新された時間を表すタイムスタンプを含んでいる（値が補間であるか、または経験的に導出されたかも表してもよい）。このようなタイムスタンプは、例えば、規定の開始時間からの分数または日数であってもよい。タイムスタンプの利用可能性によって、追加された新しい経験値に基づいて近似値を再計算することができる。タイムスタンプを用いて、このような計算に重み付けを提供してもよい（例えば、新しい値は古い値よりも重みを付ける等）。
【０１２６】
サブセクションＩＩ．Ａの様々な計算アルゴリズム、方程式、パラメータ、係数、定数などを、様々な具体的な詳細を参照して説明してきたが、当業者は、異なる実施形態を様々に異なる方法で実施しうると認識するであろう。例えば、異なる実施形態は異なる単位を用いてもよい（例えば、米国で操作されることを意図する車両ではキロメートルの代わりにマイルを用いる等）。別の例では、いくつかの実施形態は、様々な他のパラメータ、要因などに基づいて、前述の計算とは別の追加の計算を含んでいてもよい。例えば、いくつかの実施形態は、サブセクションＩＩ．Ｄを参照して後述する適応コストモデルを用いて、コスト予測を最適化してもよい。
Ｂ．車両プロファイル
【０１２７】
車両のプロファイルは、車両に関連する様々なパラメータを記憶してもよいデータ構造であってもよい（例えば、目的物）。このようなパラメータは、例えば、質量（または重量）、抵抗係数、断面積、最大動力、加速係数（例えば、速度で秒速１メートル増加を達成するために必要な時間の量）、ブレーキ再生効率係数、駆動トレイン効率係数、および／または他の適切なパラメータを含んでいてもよい。
【０１２８】
車両のプロファイルに含まれるパラメータは、車両特定のデータが使用可能でないか、および／または適切ではない場合に用いてもよい規定の単位および／または値を含んでいてもよい。
Ｃ．基本的コストモデルシステム
【０１２９】
図９は、システムの概略ブロック図を例示する。システムは、いくつかの実施形態の車両コストモデル９００を用いる。図示するように、システム（または「エンジン」）は、ルート計算要素（または「モジュール」）９１０、地図表示要素９２０、走行可能距離予測要素９４０、車両コスト要素９４０、およびルートコスト要素９５０を含んでいる。
【０１３０】
いくつかの実施形態では、ルート計算モジュール９１０は、車両に利用可能な様々な仮想ルートを特定するように適応される。このようなルートは、様々な適切な方法（例えば、車両が進行する地図の区域における道路、交差点などを検討すること、車両および／またはルートに関連するナビ情報を受信することなど）で特定されてもよい。ルート計算モジュールはルートコスト要素９５０を用いて、エネルギ消費が最小である最適なルート（エネルギ効率の良いルート）、マルチコストルートを算出してもよい。マルチコストルートでは、ルートが１つのパラメータ（例えば、時間）によって最適化され、別のパラメータ（例えば、エネルギ、充電スタンド経由のルートなど）によって抑制される。
【０１３１】
地図表示モジュール９２０は、コスト情報および関連する情報を、表示するために地図の一部をレンダリングして受信するように適応される。走行可能距離の予測モジュール９３０は他のモジュールから受信したデータ（例えば、使用可能な燃料、傾斜、距離、温度など）を評価し、車両が利用可能な具体的なパスに沿った走行可能距離を判定する。車両コストモジュール９４０は、様々な条件下で車両を動作するコストに関連する情報を提供するように適応される。車両コストモジュールは、様々な種類の動作条件下で、様々な種類の車両（例えば、ガソリン動力車、ハイブリッド車両、ＥＶ、ＣＮＧ車両など）を操作することに関連するコスト情報を提供するように適応されてもよい。ルートコストモジュール９５０は、計算コストクラスを提供するように適応されてもよい。コストの実装は、標準的なルート作成モード（例えば、最速、最短、最良のエネルギ効率など）で提供されてもよい。
【０１３２】
当業者は、システム９００は元来概念的なものであり、本発明の精神から逸脱せずに様々な特定の方法で実装されうることを認識するであろう。例えば、様々な他のモジュール、ストレージ、インターフェースなどがいくつかの実施形態に含まれてもよい。さらに、様々なモジュールはいくつかの実施形態において削除されてもよい。
【０１３３】
車両コストを計算する際に様々な地図の属性を利用してもよい。例えば、いくつかの実施形態では、長さ（例えば、メートル単位のリンクの長さ）、速度（例えば、速度制限情報、平均速度など）、傾斜、カーブ（各形状点に関連する円の半径として提供されてもよい）、停止標識、信号、および／または他の信号要素、および／または交通パターン情報を用いてもよい。
Ｄ．適応コストモデル
【０１３４】
いくつかの実施形態では、単一の一般的な調整要因ｆＧＡを下記の方程式（２２）を用いて算出する。式中、ｅＢは車両の基本的なエネルギ効率であり、前述のサブセクションＩＩ．Ａの基本的なエネルギモデルを用いて算出される。ｅＡは、システムから受信した（または算出された）車両の実際のエネルギ効率要因、またはユーザによって入力された車両の実際のエネルギ効率要因である。
ｆＧＡ＝ｅＡ／ｅＢ      （２２）
【０１３５】
このような要因は、直接的なフィードバックをエンジンから受信しないが、平均的な燃料またはエネルギの使用量を報告するシステムにとって特に有用である。例えば、いくつかの電気自動車１マイル当たりの平均的なＷ−ｈ消費量を報告する。この情報は、システムに提供されてもよく、またはユーザが１または複数の適切なＧＵＩを用いて情報を入力してもよい。
【０１３６】
次に、下記の方程式（２３）に示すように、要因を基本的なモデル計算に適用してもよい。式中、ＥｅＢａｓｉｃは基本的な車両モデルを用いて算出したエネルギコストであり、ＥｅＡｃｔｕａｌは調整要因ｆＧＡに基づいた正確な計算である。
ＥｅＡｃｔｕａｌ＝ＥｅＢａｓｉｃ・ｆＧＡ      （２３）
【０１３７】
一般的な調整要因を用いることによって、実際の車両から予測される性能の基本的な近似が可能となる。ただし、このような要因は、すべての性能変数（例えば、運転スタイル、特定の車両特性など）の要因とはされないことになる。いくつかの実施形態では、一般的な調整要因は少なくとも部分的に他の変数（例えば、天候、移動の長さなど）に基づいていてもよい。
【０１３８】
一般的な要因は、平均的な燃料効率を監視する車載コンピュータシステムを有する様々な車両の種類（例えば、電気、ガソリンなど）で用いられてもよい。このようなパラメータは運転スタイルおよび特定の車両特性を含有する。多くの車両では、所定の移動をするための実際のエネルギ消費（または全体的な）は車両バス（例えば、ＣＡＮ、ＭＯＳＴ、ＯＢＤなど）から直接読み出すことができる。
【０１３９】
いくつかの実施形態は、より正確な適応モデリング技法を実装する。この技法では、複数の個別の要因を利用し、道路構造を考慮し、および／または車両、移動および／または運転手の特定の要因を識別してもよい。
【０１４０】
いくつかの実施形態では、下記の方程式（２４）で示すように、このようなマルチ要因の適応モデルを実装してもよい。式中、ＥｅＢａｓｉｃは、基本的な車両モデルを用いて算出したＷ−ｈ単位のエネルギであり、ＥｅＡｃｔｕａｌはマルチ要因調整に基づいた正確な計算であり、ｆｖ（Ｖ）は車両要因、ｔｆｖ（Ｖ）は移動する車両要因、ｆＤＳ（ｖ、ＦＣ、Ｗ、Ｇｓ）は運転手のスタイルの要因、ＥＡｃｃ（ＴＯ、ｔ）は、温度および進行時間の関数としての付属品が消費するエネルギ（例えば、空調、ヒータなど）、ｆＡｃｃ（ＴＯ）は付属品消費要因、およびｔｆＡｃｃ（ＴＯ）は温度の関数としての移動の付属品消費要因である。
ＥｅＡｃｔｕａｌ＝ＥｅＢａｓｉｃ・ｆｖ（Ｖ）・ｔｆｖ（Ｖ）・ｆＤＳ（ｖ、ＦＣ、Ｗ、Ｇｓ）＋ＥＡｃｃ（ＴＯ、ｔ）・ｆＡｃｃ（ＴＯ）・ｔｆＡｃｃ（ＴＯ）      （２４）
【０１４１】
運転手スタイル要因ｆＤＳ（ｖ、ＦＣ、Ｗ、Ｇｓ）は、現在の運転手の効率要因を様々なパラメータに基づいて測定する関数であってよい。このようなパラメータは、例えばｖ、つまり道路の直線部分に関連する速度であり、異なる運転手は異なる加速および／または減速プロファイルを有していてもよく、ＦＣ、つまり道路の級の関数、Ｗ、つまり天候条件、Ｇｓ、つまり傾斜、および／または他の適切な要因を含んでいてもよい。
【０１４２】
道路の級の関数ＦＣによって、複数の道路の等級（例えば、幹線道路または高速道路、主要道路、ローカル道路など）が存在する。道路の等級によって、運転手の行動は異なる。幹線道路では、運転手は速度を出しがちであるが、例えば、ローカル道路では突然のブレーキまたは加速の例が多くなりえる。等級の関数は、ある程度まで速度条件によって反映されるが、明確な級の割り当てによって、さらに正確な表示が可能となる。各等級は、例えば、異なる値（例えば、１から５までの整数、１が幹線道路および高速道路を示し、２が主要道路を示すなど）によって表示されてもよい。
【０１４３】
天候条件Ｗは、規定のセットの可能性（例えば、「晴れ」または１、「雨」または２、「雪」または３など）の中から特定の環境条件を表す数である。天候条件は、少なくとも部分的に車両センサから受信した情報（例えば、温度、ワイパの状態、霜取の状態など）、および／または１または複数の外部源から受信した情報（例えば、現在の情報および／または予想、緊急天候警報システムなどを提供するウェブサービス）に基づいていてもよい。
【０１４４】
傾斜勾配Ｇｓは、例えば、地図データベースから取得した道路傾斜の勾配レベルを表す数字である。効率を良くするために、傾斜は、限定された数の別々の勾配レベル（例えば、「平坦」またはゼロ、「低勾配」または１、「中勾配」または２、「高勾配」または３など）で定義されてもよい。代替的に、傾斜は、傾斜、割合の上昇、および／または他の適切な方法で定義されてもよい。
【０１４５】
当業者は、前述した様々な運転手特有の（および／または車両−特定の）変数は、いくつかの実施形態に含まれてもよい変数のすべての組み合わせを含むわけではないと認識するであろう。例えば、前述した以外の様々な他の変数、条件、パラメータなど（例えば、時刻、可視度、道路の区間に関する履歴情報など）は、既存の要素に類似した方法で含まれていてもよい（つまり、限られた数の別々のレベルを用いて各要素を定量化する）。このような変数は様々に異なる方法で（例えば、１または複数の一次関数または非線形関数などに基づいてルックアップテーブルを用いる）適用されてもよい。
【０１４６】
ｆＤＳはマルチパラメータ関数ｆＤＳ、および／または他のマルチパラメータ関数であるため、必要に応じて個別の表（または関数）に分けてもよい。例えば、いくつかの実施形態では、速度に基づいて一次元のアレイを実装する、複合運転スタイル関数を利用してもよい。いくつかの実施形態では、実際の（および／または特定の）条件の情報が制限されているとき、または存在しないとき、このような複合運転スタイル関数を用いてもよい。いくつかの実施形態では、運転スタイルを関数のアレイとして表示してもよく、各関数は異なるセットの変数（例えば、道路の級、天候、傾斜など）に基づき、これらの変数はセットの変数（例えば、速度）によって見出しを付けられてもよい。
【０１４７】
いくつかの実施形態では、マルチパラメータ関数を入力変数のセットを用いて評価して、対応する表を見つける。具体的な変数（例えば、入力速度）に対する表内の最近似経験値（つまり、要因が以前に記録された最も近い速度）を見つけることができる。次に、類似の条件以前に記録した要因があるかどうか、および／または以前に記録した要因が現在の速度にどのくらい近いかによって、駆動スタイル要因を選択してもよい。記録した要因速度と現在の速度との絶対差が最小閾値（例えば、１０ｋｍ／ｈ）内である場合は、ルックアップテーブルからの直線近似が返されてもよい。代替的に、絶対差が最小閾値より大きく、最大閾値（例えば、２０ｋｍ／ｈ）より小さい場合は、要因は複合要因およびマルチパラメータ要因の一次結合として算出されてもよい。絶対差が最大閾値より大きい場合は、複合要因を用いてもよい。
【０１４８】
運転スタイル要因関数は、各道路リンクで動的に更新されうる。本要因は、速度（例えば、地図データベースからの）が同一であり、傾斜勾配も同一の道路（または道路リンク）の直線部分ごとに算出されてもよい。地図データベースからの予測速度を用いて、および現在の車両要因を含め、サブセクションＩＩ．Ａで前述した基本的なエネルギモデルを使用して、道路の所定の直線部分コストを算出してもよい。道路のこの直線部分に対しての車両から報告されたエネルギ効率と結果を比較してもよい。差を用いて、運転スタイル要因関数を更新してもよい。複合運転スタイル関数および特定の道路条件に対する関数は（例えば、道路の級、天候、傾斜要因などを考慮して）必要に応じて更新されてもよい。
【０１４９】
いくつかの実施形態では、単一の運転スタイル要因を複数の要因に分割し、全体的なエネルギ計算ではなく、リンクおよびノードレベルでのエネルギ計算の要因を含んでいる。一例として、リンク調整要因は少なくとも部分的に１または複数の変数（例えば、速度、登攀抵抗、道路級、天候条件、傾斜など）に基づいていてもよい。
【０１５０】
他の例としては、開始停止要因は少なくとも部分的に停止すべき速度および停止後にそこまで加速する目標速度に基づいていてもよい。このような要因は、常に更新されるスカラ値、または２つの速度の関数（例えば、停止の起点となる速度と、加速の目標速度）であってもよい。要因は各ノード（または交差点）のエネルギコスト計算に適用されてもよい。要因は使用されている車両から停止が検出されるごとに算出されてもよく、推定エネルギ使用量を車両が報告するエネルギ消費量と比較してもよい。
【０１５１】
さらに別の例は、少なくとも部分的に回転角度に基づく交差点曲折要因である。このような要因は運転手が交差点でどの程度大胆に曲折するかを反映していてもよく、車両が右折または左折をすると予測されるノードに適用されてもよい。要因は交差点で、推定エネルギ使用量および車両が報告する実際の使用量に基づいてリアルタイムに算出されてもよい。
Ｅ．適応コストモデルシステム
【０１５２】
図１０は、いくつかの実施形態において適応モデリングを実施するために用いる概念的なシステム１０００の概略ブロック図を例示する。図示するように、本システムは基本的なコストモデル要素１０１０、車両属性要素１０２０、運転手行動要素１０３０、および環境要因要素１０４０、コスト分析エンジン１０５０、および適応コストモデル要素１０６０を含んでいる。
【０１５３】
基本的なコストモデル１０１０は、任意の具体的な運転手または車両に特有ではないモデリング情報を含んでいてもよい（例えば、サブセクションＩＩ．Ａに前述したアルゴリズムは一般的で基本的なコストモデルを用いてもよい）。車両属性要素１０２０は、具体的な車両および／または車両の種類に特有の情報を含んでいてもよい。例えば、いくつかの車両属性は、総重量、最大エンジン動力などの種類または型式に関連してもよい（例えば、配送バンの一群は、車両の単一の型およびモデルを含んでいてもよい）。別の車両属性は、具体的な車両（例えば、保守情報、履歴燃費データなど）に関連してもよい。運転手行動要素１０３０は、様々な車両の運転手に関する情報（例えば、速度行動、停止および加速プロファイルなど）を含んでいてもよい。環境要因要素１０４０は、様々な適切な環境要因に関する情報（例えば、温度、湿度など）を含んでいてもよい。
【０１５４】
適応コストモデル１０６０は、特定の車両、運転手、特定の環境条件、および／または他の適切な要素に関する情報を含んでいてもよい。コスト分析エンジン１０５０は、他の要素から受信した情報を処理して、適応コストモデル１０６０を改良するように適応されてもよい。
【０１５５】
１つの特定の例として、適応コストモデル１０６０は最初に、基本的なコストモデル１０１０に関連する燃費推定（例えば、規定の燃費推定）を用いてもよい。適応コストモデル１０６０は、様々な車両属性１０２０（例えば、車両種類に特定の燃費、実際の車両の過去の燃費など）、運転手属性１０３０（例えば、特定の運転手は大抵相対的に素早く加速することもあり、停止および開始運転条件では特に燃費が悪くなるなど）、環境要因１０４０（例えば、燃費は温度、高度に影響されるなど）、および／または適応コストモデル１０６０自体（例えば、過去の燃費値は現在の走行から得られる燃費に基づいて更新されてもよい）に基づいて改良した燃費推定で更新されてもよい。
【０１５６】
当業者は、システム１０００は元来概念的なものであり、異なる実施形態において様々に異なる方法で、実装されうることを認識するであろう。例えば、異なる実施形態は、異なる特定の要素を含んでいてもよい。別の例では、様々な構成部品はいくつかの実施形態において組み合わされてもよく、および／または様々な構成部品はいくつかの実施形態においてサブ構成部品に分割されてもよい。
【０１５７】
図１１は、いくつかの実施形態において適応モデリングを実施するために用いられるオンライン／オフラインシステム１１００の概略ブロック図を例示する。図示するように、本システムは、車両バス１１０５、テレマティクスサーバ１１１０、サードパーティデータサーバ１１１５、車両データサーバ１１２０、適応車両モデル推定器（ＡＶＭＥ）１１２５、適応車両のプロファイル１１３０、車両のプロファイル１１３５、様々な位置決めセンサ１１４０、地図マッチングモジュール１１４５、車両モデル推定器（ＶＭＥ）１１５０、地図データベース１１５５、および１または複数のアプリケーション１１６０を含んでいる。いくつかの実施形態では、点線で表す構成部品はシステム１１００の外部であってもよい（例えば、車両バス１１０５、テレマティクスサーバ１１１０、サードパーティデータサーバ１１１５、車両データサーバ１１２０、および位置決めセンサ１１４０）。いくつかの実施形態では、位置決めセンサは１または複数の車両ログで代用されてもよく、それによってオフライン分析が可能となる。
【０１５８】
いくつかの実施形態のリアルタイムの車両推定システム（ＲＴＶＥＳ）は、システム１１００の実線の構成部品（つまり、オンラインおよびオフライン状況どちらでも用いられる内部構成部品）を含んでいてもよい。ＲＴＶＥＳは、リアルタイムの車両情報および様々な目的のための車両モデリングの形（例えばルート計算、走行可能距離の予測、安全性、排出量推定など）を用いるハードウェアおよび／またはソフトウェアを含んでいてもよい。ＲＴＶＥＳは車両内の車載ブラックボックス、インフォテインメントユニット内のアプリケーション、スマートフォンのアプリケーションなどに含まれていてもよい。ＲＴＶＥＳは車両情報を直接車両バスから、テレマティクスサーバを通じて、および／または他の適切な情報源から受信してもよい。ＲＴＶＥＳはまた、位置決め情報を車両および／または装置上のセンサから受信してもよい。
【０１５９】
ＡＶＭＥ１１２５は、適応車両のプロファイル１１３０を計算する役割を担っている。ＡＶＭＥ１１２５は、車両バス１１０５、テレマティクスサーバ１１１０、および／または他の適切なリソースからのリアルタイムの車両データを用いてもよい。ＡＶＭＥ１１２５は、ＶＭＥ１１５０が返す（静的車両プロファイルに基づく）推定車両モデルを、車両から読み取ったデータと比較してもよい。ＡＶＭＥ１１２５は次に、適応車両のプロファイル１１３０を算出および更新する。ＡＶＭＥ１１２５は位置決めセンサ１１４０、地図マッチングモジュール１１４５および地図データベース１１５５を用いて、データを用いて適応車両値を算出できるか、できる場合はその方法を判定してもよい。ＡＶＭＥ１１２５は、いくつかの実施形態の様々な適応アルゴリズムを用いてもよい。
【０１６０】
車両からの入力に加えて、ＡＶＭＥはアプリケーション１１６０からの入力を受信してもよい。ユーザは特定の好みまたは車両が報告する値を入力してもよく、それによって適応車両のプロファイル１１３０を調整することを支援する。この能力を用いて、例えば、車両とはいかなる方法でも接続していないスマートフォンのアプリケーションから単一の一般的な要因を設定してもよい。
【０１６１】
適応車両のプロファイル１１３０は、ＡＶＭＥ１１２５が算出する現在の車両に特定のパラメータを記憶可能なファイルまたはローカルデータベースであってもよい。プロファイル１１３０は、車両データサーバ１１２０にアップロードされて、集計および記憶されてもよい。プロファイル１１３０はまた、システム起動時にサーバ１１２０からダウンロードされてもよい。
【０１６２】
ＶＭＥ１１５０は、静的車両のプロファイル１１３５および動的適応車両のプロファイル１１３０に基づいて、車両モデル推定を算出してもよい。ＶＭＥ１１５０は、位置決めセンサ１１４０、地図マッチングモジュール１１４５および／または地図データベース１１５５からの情報を利用して、エネルギ使用量、燃料使用量、排出量などの道路に関する様々な車両パラメータを推定してもよい。ＶＭＥ１１５０は基本的なおよび／または適応エネルギモデルを用いてもよい。ＶＭＥ１１５０はまた、様々なセットのアプリケーション１１６０によって用いられてもよい。
【０１６３】
車両のプロファイル１１３５はファイルまたはデータベースであってもよく、選択した車両の型式、モデルおよび製造年のメーカー情報に基づく静的車両情報を含む。車両のプロファイル１１３５を用いて、いくつかの実施形態の基本的なエネルギモデルを展開してもよい。
【０１６４】
アプリケーション１１６０は、ＶＭＥ１１５０を用いたＲＶＥＳ上で動作する異なる種類のモジュールまたはアプリケーションを表す。アプリケーション１１６０は、ルート計算、走行可能距離の予測、排出量推定、および／または他の適切な関数を提供してもよい。
【０１６５】
地図マッチングモジュール１１４５は、位置決めセンサ１１４０のデータを受信してもよく、道路ネットワーク（地図データベース１１５５が返すように）上で車両が位置する場所を判定してもよい。この情報はＡＶＭＥ１１２５、ＶＭＥ１１５０および／またはアプリケーション１１６０によって用いられてもよい。
【０１６６】
地図データベース１１５５は、車両周囲の道路ネットワークに関する情報を含んでいてもよい。地図データベースは、道路接続、道路属性（速度、道路級など）、停止標識、信号に関する情報などを含んでいてもよい。
【０１６７】
車両バス１１０５は、車両センサおよび内部コンピュータへのアクセスを提供するサブシステムであってもよい。ＲＴＶＥＳは、車両バスに、例えばＯＢＤポートを介して接続してもよく、直接ＣＡＮ、ＭＯＳＴまたは他の車両バスインターフェースを介して、および／または他の適切な方法で接続してもよい。
【０１６８】
テレマティクスサーバ１１１０は、車両のテレマティクスユニット（ＴＵ）と通信してもよい。テレマティクスサーバは、リアルタイムの車両情報を受信してもよく、ウェブサービスアプリケーションプログラミングインターフェース（ＡＰＩ）をＲＴＶＥＳに提供してもよい。
【０１６９】
位置決めセンサ１１４０は、ＲＴＶＥＳに使用可能な様々な位置決めセンサを含んでいる。位置決めセンサは、ＧＮＳＳセンサ（ＧＰＳ、ＧＬＯＮＡＳＳ、ガリレオ、ＢＤＳなど）、ＧＮＳＳ補強システム、慣性および絶対位置決めセンサ（ジャイロスコープ、加速度計、車速パルスセンサ、差速パルス、コンパスなど）、無線信号位置決めシステム（Ｗｉ−Ｆｉ位置決め、携帯電話用基地局の三角測量など）、および任意の関連ハードウェアおよび／またはソフトウェアを含んでいてもよい。位置決めセンサは、車両バス（例えば、ＣＡＮ、ＭＯＳＴなど）を通じて車両上で使用可能であってもよい。またはインフォテインメントユニット上で使用可能なセンサであってもよく、またはユーザのスマートフォンが社内で使用される場合には、スマートフォンのセンサであってもよい。
【０１７０】
車両データサーバ３４２０を用いて、車両プロファイル１１３０〜１１３５を管理する。車両データサーバ３４２０は、所定の車両の種類の適応プロファイルを集計し、分析を実行し、フィードバックを運転手に提供し、または静的情報を更新する。
【０１７１】
サードパーティデータサーバ１１１５は、気象条件、温度など車両モデリングに用いることができる追加の環境情報を提供する。
【０１７２】
当業者は、システム１１００は元来概念的なものであり、本発明の精神から逸脱せずに様々に異なる方法で実装されうることを認識するであろう。例えば、様々な異なる構成部品が含まれていてもよく、様々な例示される構成部品は省略されてもよいことなどがあげられる。
Ｆ．排出量推定
【０１７３】
図１２は、いくつかの実施形態において車両排気ガス推定を生成するために用いるシステム１２００の概略ブロック図を例示する。図示するように、本システムは、地図要素１２１０、ルート計算要素１２２０、ルートインポートモジュール１２３０、燃料（および／または炭素）範囲の予測要素１２４０、排出量計算エンジン１２５０、および１または複数の排出量推定要素１２６０を含んでいる。
【０１７４】
このようなシステム１２００は、車載システムとして実装されてもよい。システムは、リアルタイムのフィードバックを提供し、および／または運転手行動、現在のエンジン条件、および／または他の関連リアルタイムの要因に基づいて値を算出するように適応される。システムは報告基準および／または排出量上限値に合わせるように支援可能である。
【０１７５】
地図要素１２１０はそれぞれ、様々な地理的区域に関する情報を含む（例えば、高度、停止／出発点、リアルタイムの交通、速度など）。ルート計算要素１２２０は、様々なセットのリンク、形状点、および／または他の適切な種類のルートの情報を含んでいてもよい。ルートインポートモジュール１２３０は、様々なルートを処理し、および／またはフォーマットし、それによって、排出量計算エンジン１２５０はデータを効率的な方法で操作することができる。燃料範囲の予測１２４０は、走行可能距離の様々な多角形、距離、および／または他の適切な計測を表すデータを含んでいてもよい。
【０１７６】
排出量計算エンジン１２５０は、様々な適切な種類の情報を受信し、１または複数の排出量推定１２６０を生成するように適応される。いくつかの実施形態では、排出量推定計算を下記の方程式（２１）を用いて実施する。式中、Ｑｆは必要な機械エネルギＥｍを生成するために必要な燃料量である。Ｅｍは所定のリンクを移動するために必要な機械エネルギである。機械エネルギは様々な前述のアルゴリズム、システム、およびモデル（適応モデルを含む）を用いて判定されてもよい。このような要因は、待機エネルギ（例えば、車両のエンジンはかかっているが停止している場合）を含んでいてもよい。ＧＧＥはガソリンガロン当量であり、燃料１ガロンから生成可能なワット時間数を定義する。ＴＥ（ｖ）は速度に基づく車両モータの熱効率である（関数としてモデル化され、車両プロファイルに含まれる表から導かれてもよい）。
Ｑｆ＝Ｅｍ／（ＧＧＥ・ＴＥ（ｖ））      （２１）
【０１７７】
いくつかの実施形態では、排出量推定を（例えば、システム１２００などのシステムを用いて）ウェブサービスＡＰＩを用いて提供してもよい。このようなＡＰＩによって、サードパーティはバックエンド要素を組み込むことができる。前述の様々な特徴が提供されてもよく、例を以下にあげる。ルート計算（例えば、エネルギ効率的なルート、推定燃費（ＥＦＣ）、推定移動排出量（ＥＴＥ）などを計算することによって）、ルートインポート（例えば、既存のルートの様々な種類のファイルのインポートを支援することによって、およびＥＦＣおよび／またはＥＴＥ値を生成することによって）、トレールインポート（例えば、実際の進路データに基づいて）、炭素または燃料距離の予測（例えば、走行可能距離の予測アルゴリズムを拡大して走行可能距離に基づいてＣ０２排出量または特定の量の燃料を、１ドル当たりの走行可能距離として算出することなど）。
【０１７８】
当業者は、システム１２００は元来概念的なものであり、本発明の精神から逸脱せずに様々に異なる方法で実装されうることを認識するであろう。例えば、様々な異なる構成部品が含まれていてもよく、様々な例示される構成部品は省略されてもよいことなどがあげられる。
ＩＩＩ．予測アルゴリズム
【０１７９】
サブセクションＩＩＩ．Ａは、いくつかの実施形態が用いる概念的なデータ構造の説明を提供する。次に、サブセクションＩＩＩ．Ｂは、いくつかの実施形態の基本的な走行可能距離の予測アルゴリズムを説明する。サブセクションＩＩＩ．Ｃは次に、いくつかの実施形態のマルチステージ予測アルゴリズムを説明する。次に、サブセクションＩＩＩ．Ｄは、いくつかの実施形態のファンアウトアルゴリズムを説明する。サブセクションＩＩＩ．Ｅは次に、いくつかの実施形態のセンタアウトアルゴリズムを説明する。次に、サブセクションＩＩＩ．Ｆは、いくつかの実施形態のビットマップベースのアルゴリズムを説明する。サブセクションＩＩＩ．Ｇは次に、いくつかの実施形態による制限区域の取り扱いを説明する。最後に、サブセクションＩＩＩ．Ｈはいくつかの実施形態が用いる、データキャッシュおよび読み出しアルゴリズムを説明する。
【０１８０】
下記のデータ構造およびアルゴリズムは、代替的におよび／または組み合わせて、図１〜３を参照して前述したシステム、または図３７を参照して後述するシステム、および／または他の適切なシステムを用いて実装されうる。様々な処理は様々な適切な時間に実施されてもよい（例えば、ソフトウェアおよび／またはデータのコンパイル中、実行時など）。
Ａ．データ構造
【０１８１】
図１３は、いくつかの実施形態が用いる、データ構造の概念的なセットのデータ構造１３００を例示する。このようなデータ構造は、いくつかの実施形態における基本的な走行可能距離の予測に関連してもよい。図示するように、データ構造は、初期リンク１３０５、目標コスト１３１０、ルートステップ１３２０のセットを参照するオープンキュー１３１５を含む。ルートステップ１３２０のそれぞれは、サブ要素１３２５のセットを参照してもよい。サブ要素１３２５はさらに、サブ要素１３３０を含んでいてもよい。データ構造はさらに、結果ステップ１３４０のセットを参照する結果ステップリスト１３３５、および末端ステップ１３５５のセットを参照する末端ステップリスト１３５０を含んでいてもよい。結果ステップ１３４０のそれぞれは、様々なサブ要素１３４５を参照してもよい。末端ステップ１３５５のセットはそれぞれ、様々なサブ要素１３６０を参照してもよい。
【０１８２】
いくつかの実施形態では、走行可能距離の予測がリクエストされる場合に、初期リンク１３０５および目標コスト１３１０が提供される。このような要素は適切なリクエストに含まれていてもよい。オープンキュー１３１５は、コストによって分類されるルートステップ１３２０のリストを含んでいてもよい。各ルートステップは、リンク（それ自体がノードおよび／または形状点のセットを参照してもよい）またはリンクのセット、ルートステップおよび後続ルート（ある場合）のリストを含むパスに関連する蓄積コスト、および／または他のサブ要素などの様々なサブ要素１３２５を参照してもよい。各後続ルートは、リンクおよびリンクに関連する移動コスト（および／または横断コスト）および先行ルートステップに関連するリンクに対する移動コスト（および／または横断コスト）などの様々なサブ要素１３３０を参照してもよい。
【０１８３】
各結果ステップ１３４０は、様々なサブ要素１３４５（例えば、リンク、蓄積コストなど）を含む。結果ステップを用いて、いくつかの実施形態における走行可能距離の多角形を画定してもよい。各リンクは、１または複数のノード、形状点、および／または他の適切なサブ要素（図示せず）への参照を含んでいてもよい。
【０１８４】
各末端ステップ１３５５は、様々なサブ要素１３６０（例えば、リンク、蓄積コストなど）を含む。末端ステップを用いて、いくつかの実施形態による走行可能距離の多角形の境界を画定してもよい。各リンクは、１または複数のノード、形状点、および／または他の適切なサブ要素（図示せず）への参照を含んでいてもよい。
【０１８５】
結果ステップリスト１３３５は、すべてのアクセス可能なリンク（つまり、走行可能距離内のリンク）を参照してもよい。末端ステップリスト１３５０は、末端リンク（つまり、目標コストが達成されたリンク、行き止まりのリンク、および／または後続がない他のリンク）を参照してもよい。
【０１８６】
いくつかの実施形態では、各末端ステップ１３５５、結果ステップ１３４０、および／またはルートステップ１３３０は、進行方向を参照するサブ要素（図示せず）を含んでいる。このように、いくつかの実施形態では、各リンクに関連し、走行可能距離の予測区域の外側境界を画定するノードを判定してもよい。
【０１８７】
図１４は、センタアウトの実装でいくつかの実施形態が用いる、データ構造の概念的なセットのデータ構造１４００を例示する。図示するように、データ構造は、走行可能距離のセンタ要素１４０５、複数の走行可能距離ノード（または形状点）１４１０、オープンキュー１４１５、処理されたキュー１４２０、多角形リスト１４２５、および多角形角度リスト１４３０を含む。
【０１８８】
各走行可能距離のセンタ要素１４０５は、予測される走行可能距離の中心（例えば、現在の車両位置）を表すデータを含んでいてもよく、様々な適切な方法でフォーマットされるデータ（例えば、極座標、ｘ／ｙ座標など）を含んでいてもよい。
【０１８９】
各走行可能距離ノード１４１０は、距離、向きなどの様々なサブ要素１４３５を含んでいてもよい。オープンキュー１４１５は、すでに処理済みの走行可能距離ノードに対する走行可能距離ノード参照１４４０を含んでいてもよい。処理されたキュー１４２０は、すでに処理済みの走行可能距離ノードに対する走行可能距離ノード参照１４４０を含んでいてもよい。多角形リスト１４２５は、特定の多角形（例えば、走行可能距離の予測多角形）に含まれる走行可能距離ノードを参照する走行可能距離ノード参照１４４０のセットを含んでいてもよい。多角形角度リスト１４３０は、いくつかの実施形態の多角形の先端に沿って角度を定義する走行可能距離ノード参照１４４０のセットを含んでいてもよい。
【０１９０】
当業者は、図１３〜１４に提示するデータ構造は例示目的のみであり、様々な異なる実施形態で様々な異なるデータ構造を用いて、データの様々な異なる級、データ要素の参照などを含めて、実装されうることを認識するであろう。
Ｂ．基本的走行可能距離予測
【０１９１】
図１５は、いくつかの実施形態が走行可能距離の予測を生成するために用いる概念的な処理１５００のフローチャートを例示する。処理は、図１３を参照して前述のデータ構造を用いて実装されてもよい。このような処理は、例えば、特定のリクエストが行われたときに開始されてもよい。いくつかの実施形態では、処理１５００は開始リンクおよび目標コスト（例えば、エネルギ消費、燃料消費の閾値に関連するコストなど）を受信してもよい。
【０１９２】
次に、処理は（１５０５で）オープンキューを生成し、初期ステップをキューに追加する。初期ステップはまた、結果ステップリストに追加されてもよい。初期ステップは少なくとも部分的に開始リンクに基づいて生成されてもよく、リンクおよび関連コストを含んでいてもよい。複数のコストが記憶されてもよく、および／または各ルートステップ（例えば、エネルギ、時間など）に対して算出されてもよい。処理１５００は次に（１５１０で）キューの次のステップ（つまり、最低コストのステップ）を読み出し、読み出されたステップをキューから削除することによって、現在のステップをオープンキューから浮かび上がらせる。オープンキューはコストによって分類されてもよい（および現在のステップがキューから浮かび上がるたびに再分類されてもよい）。
【０１９３】
処理は次に、（１５１５で）現在のステップのコストが目標コストを超えているかどうかを判定する。処理が現在のステップのコストの方が大きいと判断する場合は、（オープンキューはコストによって分類されており、高いコストを持つステップは走行可能距離を延ばすためには用いられないため）、処理を終了する。
【０１９４】
代替的に、処理は（１５１５で）現在のステップコストが目標コスト未満であることを判定する場合は、処理は次に、（１５２０で）代替リンクまたはステップのリストを生成する（つまり、現在のステップから達成可能なリンクを含むステップ）。このようなリストは様々な適切な方法で生成されてもよい。例えば、各リンク、およびしたがって各ステップは、現在のリンクに接続する他のリンクへの様々な参照を含んでいてもよい。代替的に、各ノードは、接続するリンクのセットへの参照を含んでいてもよい。
【０１９５】
処理１５００は次に、（１５２５で）次の後続ステップをリストから読み出し、（１５３０で）後続のステップの蓄積コストが目標コスト未満であるかを判定する。図１３を参照して前述したように、各後続ステップは、リンク、移動コスト、蓄積コスト、および／または他の適切な要素を参照してもよい。処理が（１５３０で）コストが目標コストを超えると判定する場合は、処理が（１５３０で）コストが目標コスト未満であると判定するまで、処理は操作１５２５〜１５３０を繰り返してもよい。
【０１９６】
処理は（１５３０で）後続のステップのコストが目標コスト未満であることを判定する場合は、処理は次に、（１５３５で）後続のステップに基づいてルートステップを生成し、ルートステップをオープンキューに追加する。ルートステップはまた、結果ステップリストに追加されてもよい。このようなルートステップは様々な適切な方法で生成されてもよく、様々なサブ要素（例えば、リンク、蓄積コスト、代替リンクまたはステップなど）を含んでいてもよい。いくつかの実施形態では、後続のステップはさらに分析されて、結果ステップリストがすでにリンクを含むかを判定してもよく、もしそうであれば、後続のリンクの蓄積コストが結果ステップリストに以前に記憶されたリンクのコスト未満である場合にのみ、後続のリンクをオープンキューに追加する。このように、アルゴリズムは、すでに処理されたリンクを再探索することを避けてもよく、したがって蓄積コストが改善する可能性を提供しない。
【０１９７】
次に、処理１５００は、（１５４０で）現在のステップのすべての後続リンクが分析されているかを判定する。処理が、すべての後続リンクが分析されていないと判定する場合は、処理は、すべての後続リンクが分析されたと判定されるまで、操作１５２５〜１５４０を繰り返す。
【０１９８】
処理が（１５４０で）すべての後続が分析されたと判定する場合、処理は次に、（１５４５で）任意の良い後続（つまり、蓄積コストが目標コスト未満である後続）があるかどうかを判定する。処理が良い後続がないと判定する場合は、処理は（１５５０で）現在のステップを末端ステップリストに追加する。（１５５０で）現在のステップを追加後または、処理が（１５４５で）よい後続があると判定する場合は、処理は、（１５５５で）オープンキューが空であるかを判定する。
【０１９９】
処理が（１５５５で）オープンキューは空であると判定する場合は、処理を終了する。代替的に、処理がオープンキューは空ではないと判定する場合は、処理が（１５１５で）コストが目標コストを上回ると判定するまで、または処理が（１５５５で）オープンキューは空であると判定して、次に終了するまで、処理は操作１５１０〜１５５５を繰り返してもよい。
【０２００】
処理１５００を様々な特定の詳細を参照して説明してきたが、当業者は、処理は様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、様々な操作はいくつかの実施形態では省略されてもよく、および／または様々な他の操作はいくつかの実施形態では追加されてもよい。別の例では、異なる実施形態は、操作を異なる順序で実施してもよい。さらに別の実施例では、処理はサブ処理のセットに分割されてもよく、および／またはサブ処理としてマクロ処理に含まれてもよい。さらに、異なる実施形態は、処理を少なくとも部分的に様々な基準（例えば、受信したリクエストごとに、継続して、規則的な間隔で）に基づいて実施してもよい。
Ｃ．マルチステージ予測
【０２０１】
図１６は、概念的な処理１６００のフローチャートを例示する。本処理１６００は、いくつかの実施形態が、マルチステージ走行可能距離の予測計算および／または表示を実施するために用いる。このような処理は、例えば、ユーザがいくつかの実施形態の適用を開始するとき、予測のリクエストが行われたときなどに開始してもよい。
【０２０２】
図示するように、処理１６００は、（１６１０で）道路の第１のレベル（または他の適切なデータ種類）で開始する。いくつかのアプリケーションでは、各道路に関連するレベルを含む地図データが提供されてもよい（「道路」は車両が使用可能であり、予測が求められる任意の進行方向を指してもよい）。いくつかの実施形態では、第１のレベルは主要道路（例えば、高速道路、州道など）に関連してもよい。
【０２０３】
次に、処理は（１６２０で）現在のレベルに関連するデータを読み出す。このようなデータは、適切な地図データベース、ストレージ、および／または他の適切なリソースから読み出されてもよい。処理は次に、（１６３０で）少なくとも部分的に読み出されたデータに基づいて予測を更新してもよい。第１のレベルの事例では、（１６３０で）既存の予測がないので、初期予測が生成されてもよい。
【０２０４】
処理は次に、（１６４０で）更新される予測を表示し、および／または更新される予測をクライアント装置に送信する。このような表示は、適切なレスポンスオブジェクトをフォーマットし、且つ、オブジェクトをクライアントまでネットワーク接続（有線または無線）を介して送信しながら、データをレンダリングして（および／または他の方法でフォーマットする）適切なリソース（例えば、車載用ヘッドユニット、スマートフォン画面）上に表示させることを含んでいてもよい。
【０２０５】
次に、処理１６００は、（１６５０で）すべての使用可能なレベルが分析されているかを判定する。このような判定は様々な適切な方法で行われてもよい（例えば、地図データベースは複数の使用可能なレベルを特定してもよく、ユーザは用いる複数のレベルを選択してもよく、規定の設定を適用してもよい）。処理がすべてのレベルをまだ分析していないと判定される場合は、処理は（１６６０で）レベルを上げる（例えば、レベル１からレベル２へ、レベル２からレベル３へ）。処理が（１６５０で）すべてのレベルが分析されていると判定し、処理を終了するときまで、操作１６２０〜１６６０を反復してレベルごとに繰り返してもよい。
【０２０６】
処理１６００を様々な特定の詳細を参照して説明してきたが、当業者は、処理は様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、様々な操作はいくつかの実施形態では省略されてもよく、および／または様々な他の操作はいくつかの実施形態では追加されてもよい。別の例では、異なる実施形態は、操作を異なる順序で実施してもよい。さらに別の実施例では、処理はサブ処理のセットに分割されてもよく、および／またはサブ処理としてマクロ処理に含まれてもよい。さらに、異なる実施形態は、処理を少なくとも部分的に様々な基準（例えば、受信したリクエストごとに、継続して、規則的な間隔で）に基づいて実施してもよい。
【０２０７】
図１７は、いくつかの実施形態のマルチステージ予測アルゴリズムに関連する複数のＧＵＩ１７１０〜１７３０を例示する。具体的には、本図は、操作中にユーザに表示される走行可能距離の予測多角形の進行を示す。図示するように、ＧＵＩは表示区域４００に表示される。
【０２０８】
本実施例では、第１のＧＵＩ１７１０は、第１の走行可能距離の予測（例えば、道路の第１の等級のみを用いる「大まかな」予測）に関連する、第１の多角形１７４０を示す。第２のＧＵＩ１７２０は、（例えば、道路の第２の等級を予測アルゴリズムに組み込むことによって）「主要」路上レベルと評価された第２の多角形１７５０を示す。第３のＧＵＩ１７３０は、（例えば、道路の第３の等級を予測アルゴリズムに組み込むことによって）さらに「細い」路上レベルまで精密にされた第３の多角形１７６０を示す。異なる実施形態においては、予測多角形を、異なる特徴、道路の種類、および／または必要に応じて他の関連パラメータに関連する、異なるレベル（および異なる数のレベルおよび／または予測）まで精密にしてもよい。
【０２０９】
操作中に、表示要素は、走行可能距離探索リクエストを受信後すぐに、第１の多角形１７４０をユーザに提供する。第２の多角形１７５０は、システムが走行可能距離を改良するにしたがって、少し後に表示される。第３の多角形１７６０は、システムがさらに走行可能距離を改善するにしたがって、一定の時間の後に表示される。このように、ユーザは、走行可能距離を迅速に直観的な指示で受信し、さらに走行可能距離は処理時間が長くかけられるほどさらに改善される。
【０２１０】
当業者は、ＧＵＩ１７１０〜１７３０は本発明の精神から逸脱せずに様々に異なる方法で実装されうることを認識するであろう。例えば、様々な走行可能距離の予測区域は異なる色、陰影のなどで表示されてもよい。別の例では、異なる実施形態は異なる数のステージを用いて予測を改善してもよい。さらに別の実施例では、いくつかの実施形態においてユーザは様々な表示オプションを選択してもよい。表示オプションは、表示された区域およびこのような表示に関連する様々なパラメータの進行を部分的に判定してもよい（例えば、ユーザは、表示更新を起動してもよい複数の正確さの閾値を選択してもよく、ユーザは更新された走行可能距離に認められる様々な時間閾値を選択してもよい）。
Ｄ．ファンアウト予測
【０２１１】
図１８は、展開アルゴリズムを用いて、車両の走行可能距離の多角形を決定するために用いる処理１８００のフローチャートを例示する。処理１８００の結果の概念的なグラフィカル表示を以下の図１９に示す。このような処理１８００は、例えば、ユーザがいくつかの実施形態の走行可能距離探索アプリケーションを開始するときに開始する。
【０２１２】
処理は次に、（１８１０で）現在の位置を（例えば、ＧＰＳ情報を適切なリソースから読み出すことによって）判定する。次に、処理は、（１８２０で）基本的な走行可能距離の予測を、前述したように処理３２００を参照して判定し、末端ノード（または「点」）を基本的な走行可能距離の予測に基づいて算出する。末端ノードは末端ステップリストを用いて、走行可能距離の予測探索の方向のリンクの端部点を用いて判定されてもよい。処理１８００は次に、（１８３０で）放射断面を生成する。放射断面は予測の中心を起点とし、すべての方向に一定の角度を開けて延在する。
【０２１３】
次に、処理は（１８４０で）次の末端点（または、適切な場合は第１の点）を評価のために選択する。処理は次に、（１８５０で）点を含む部分を選択する。
【０２１４】
処理は次に、（１８６０で）特定された部分について、次の点が現在の位置から記憶された点よりも離れているかを判定する。処理が次の点の方が遠いと判定するとき（またはいずれの点も以前に記憶されていないと判定するとき）、処理は（１８７０で）記憶された点を交換する。代替的に、処理は操作１８８０に続いてもよい。
【０２１５】
（１８７０で）記憶された点を交換後、または（１８６０で）記憶された点の方が次の点よりも予測多角形の中心に近いと判定した後、処理は（１８８０で）すべての点が分析されているかを判定する。処理がすべての点が分析されていないと判定する場合は、処理は操作１８４０に戻る。操作１８４０〜１８８０は次に、処理が（１８８０で）すべての点が分析されたと判定し、そこで処理が終了する時点まで反復して実施されてもよい。
【０２１６】
したがって、このような処理は、末端点を車両の走行可能距離内の各部分内にあり、かつ評価走行可能距離の中心（つまり、現在の車両位置）から最も離れている点を特定してもよい。
【０２１７】
処理１８００を様々な特定の詳細を参照して説明してきたが、当業者は、処理は様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、様々な操作はいくつかの実施形態では省略されてもよく、および／または様々な他の操作はいくつかの実施形態では追加されてもよい。別の例では、異なる実施形態は、操作を異なる順序で実施してもよい。さらに別の実施例では、処理はサブ処理のセットに分割されてもよく、および／またはサブ処理としてマクロ処理に含まれてもよい。さらに、異なる実施形態は、処理を少なくとも部分的に様々な基準（例えば、受信したリクエストごとに、継続して、規則的な間隔で）に基づいて実施してもよい。
【０２１８】
図１９は、処理１８００の結果を表す、いくつかの実施形態のＧＵＩ例１９００を例示する。図示するように、ＧＵＩ１９００は、地図の部分１９１０、円１９２０、放射断面を画定するスポーク１９３０のセット、最も遠い点１９４０のセットおよび結果として生じる多角形１９５０を含む。円１９２０およびスポーク１９３０はユーザに提示される典型的なＧＵＩでは表示されなくてもよいが、説明を目的として本図に含む。
【０２１９】
円１９２０の各放射断面は、多角形１９５０の外側の先端を画定するために用いられる単一の点１９４０を含んでいてもよい。各点１９４０は、隣接する各放射断面内の点と、直線で接続してもよい。
【０２２０】
当業者は、ＧＵＩ１９００は様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、異なる実施形態は異なる特定の表示要素を含んでいてもよい。別の例では、異なる実施形態は、異なる色、線のスタイル、および／または他の特徴を用いて、様々な項目間で区別を図ってもよい。さらに、異なる実施形態は、様々な異なる数の放射断面、表示区域１９１０に対して異なる半径などを含んでいてもよい。
Ｅ．センタアウト予測
【０２２１】
図２０は、センタアウトアルゴリズムを用いて車両の走行可能距離を判定するために用いる処理２０００のフローチャートを例示する。処理２０００の結果の概念的なグラフィカル表示を下記の図２６に示す。このような処理２０００は、例えば、ユーザがいくつかの実施形態の走行可能距離探求アプリケーションを起動するときに開始してもよい。
【０２２２】
図示するように、処理は（２０１０で）基本的な走行可能距離の予測を判定する。基本的な走行可能距離の予測は、処理３２００を参照して記載したように末端点のセットを算出してもよく、末端点をオープンキューに追加してもよい。次に、処理２０００は（２０２０で）走行可能距離中心を判定し、中心を多角形リストに追加する。走行可能距離の中心は様々な適切な座標システムを用いて特定されてもよい。次に、処理は、（２０３０で）次の２つの走行可能距離ノードをオープンキューから読み出し、ノードを多角形リストおよび多角形角度リストに追加する。オープンキューは、まだ分析されていないすべての使用可能な末端ノードを含んでいてもよい。
【０２２３】
処理は次に、（２０４０で）第１の末端ノードを現在のノードとして記憶する。次に、処理は、（２０５０で）現在のノードに最も近いノードを多角形リストから判定し、ノードを第１の候補ノードとして記憶する。処理は次に、（２０６０で）最も近い距離のノードを囲むノードを多角形リストから読み出し、ノードを第２（必要に応じてさらに第３、第４など）の候補ノードとして記憶する。次に、処理は（２０７０で）現在のノードが任意の（またはすべての）候補ノードに置換されてもよいかを判定する。
【０２２４】
次に、処理は（２０８０で）すべてのノードが分析されているかを判定する。このような判定は様々な適切な方法で行われてもよい（例えば、オープンキュー内のすべてのノードが分析されているかを判定することによって）。
【０２２５】
処理が、すべてのノードが分析されていないと判定すると、処理が（２０８０で）すべてのノードが分析され、その時点で処理が終了してもよいことを判定するまで、処理は操作２０５０〜２０８０を繰り返す。
【０２２６】
処理２０００を様々な特定の詳細を参照して説明してきたが、当業者は、処理は様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、様々な操作はいくつかの実施形態では省略されてもよく、および／または様々な他の操作はいくつかの実施形態では追加されてもよい。別の例では、異なる実施形態は、操作を異なる順序で実施してもよい。さらに別の実施例では、処理はサブ処理のセットに分割されてもよく、および／またはサブ処理としてマクロ処理に含まれてもよい。さらに、異なる実施形態は、処理を少なくとも部分的に様々な基準（例えば、受信したリクエストごとに、継続して、規則的な間隔で）に基づいて実施してもよい。
【０２２７】
図２１は、いくつかの実施形態において最も近いノードを特定するために用いる処理２１００のフローチャートを例示する。このような処理は、例えば、処理２０００を参照して前述した操作２０４０の少なくとも一部として実装される。
【０２２８】
図示するように、処理は（２１１０で）多角形角度リストから、現在のノード角度に最も近い角度を検索し、関連ノードを最も近い角度ノードとして記憶する。次に、処理は、少なくとも部分的に最も近い角度ノードに基づいて、（２１２０で）閾値のセット内の正および負の角度方向で、次および前のノードを多角形角度リストから読み出す。
【０２２９】
処理２１００は次に、（２１３０で）現在のノードと任意の読み出されたノードとの間の直線距離を算出する。次に、処理は、（２１４０で）最小距離ノードを直線距離計算に基づいて判定し、最小距離ノードを最も近いノードとして記憶する。そして処理が終了する。
【０２３０】
処理２１００を様々な特定の詳細を参照して説明してきたが、当業者は、処理は様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、様々な操作はいくつかの実施形態では省略されてもよく、および／または様々な他の操作はいくつかの実施形態では追加されてもよい。別の例では、異なる実施形態は、操作を異なる順序で実施してもよい。さらに別の実施例では、処理はサブ処理のセットに分割されてもよく、および／またはサブ処理としてマクロ処理に含まれてもよい。さらに、異なる実施形態は、処理を少なくとも部分的に様々な基準（例えば、受信したリクエストごとに、継続して、規則的な間隔で）に基づいて実施してもよい。
【０２３１】
図２２は、識別された最も近いノードが候補ノードと置換できるかを判定するために用いられる、処理２２００のフローチャートを例示する。このような処理は、例えば、処理２０００を参照して前述した操作２０６０の少なくとも一部として実装される。
【０２３２】
図示するように、処理２２００は、（２２１０で）候補ノード、現在のノード、多角形リスト、および処理されたノードキューを受信する。次に、処理は、（２２２０で）前のノードおよび次のノードを多角形リストから読み出す。処理は次に、（２２３０で）角度走行可能距離をノードから判定する。処理は次に、（２２４０で）最小距離ノードを、前および次のノードから判定する。
【０２３３】
処理は次に、（２２５０で）キューの次のノードを読み出す。処理は次に、（２２６０で）読み出されたノードが評価基準に合致するかを判定する（図２３を参照して評価基準の一例を後述する）。処理２２００が（２２６０で）読み出されたノードが基準に合致すると判定する場合は、処理は、（２２７０で）読み出されたノードを記憶する。代替的に、処理は（２２８０で）読み出されたノードを拒絶する。
【０２３４】
処理２２００は次に、（２２９０で）すべてのノードが評価されたかを判定する。処理がすべてのノードが評価されていないと判定する場合は、処理が（２２９０で）すべてのノードが評価されたことを判定し、次に、（２２９５で）候補ノードを読み出されたノードで置換して、終了するまで、処理は操作２２５０〜２２９０を反復して実施する。
【０２３５】
処理２２００を様々な特定の詳細を参照して説明してきたが、当業者は、処理は様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、様々な操作はいくつかの実施形態では省略されてもよく、および／または様々な他の操作はいくつかの実施形態では追加されてもよい。別の例では、異なる実施形態は、操作を異なる順序で実施してもよい。さらに別の実施例では、処理はサブ処理のセットに分割されてもよく、および／またはサブ処理としてマクロ処理に含まれてもよい。さらに、異なる実施形態は、処理を少なくとも部分的に様々な基準（例えば、受信したリクエストごとに、継続して、規則的な間隔で）に基づいて実施してもよい。
【０２３６】
図２３は、処理２２００の評価基準を示すグラフィカル表示２３００〜２３１０を例示する。第１の表示２３００は、走行可能距離の中心２３２０、前のノード２３３０、現在のノード２３４０、次のノード２３５０、およびチェックノード２３６０を含む。いくつかの実施形態では、チェックノード２３６０の角度の判定は、チェックノードが最小と最大角度閾値内にあるかを判定するために行われてもよい（例えば、チェックノード２３６０と走行可能距離の中心２３２０を結ぶ線の角度が、前のノード２３３０および次のノード２３５０によって画定される角度の範囲内にあるか）。チェックノード２３６０が最小および最大角度閾値内にない場合は、ノードは拒絶され、キューの次のノードが読み出されてもよい。チェックノードが閾値内の場合は、評価は継続してもよい。
【０２３７】
次に、いくつかの実施形態では、走行可能距離中心２３２０からチェックノード２３６０まで形成されたリンクが、前のノード２３３０から現在のノード２３４０までの線、または現在のノードから次のノード２３５０までの線を横断するかを判定する。表示２３００の例では、走行可能距離の中心２３２０からチェックノード２３６０までの線は、現在のノード２３４０から次のノード２３５０までの線を横断する。このように、次のノード２３５０は「起点」ノードとして割り当てられる。走行可能距離の中心２３２０からチェックノード２３６０の距離が、走行可能距離の中心２３２０から起点ノードまでの距離よりも短い場合は、チェックノード２３６０は候補として拒絶され、キューの次のノードが読み出される。
【０２３８】
または、チェックノード２３６０が表示例２３１０で示すように、走行可能距離の中心２３２０、現在のノード２３４０、および起点ノード２３７０で形成される多角形の外側にある場合は、現在のノード２３４０候補として拒絶され、次の候補ノードが評価される。これ以上探求するノードがなくなると、現在のノード２３６０は多角形リスト内の候補ノードに置換可能であってもよく、多角形角度リストがそれにしたがって更新されてもよい。
【０２３９】
異なる実施形態は、性能が改善される様々な修正を含んでいてもよい。例えば、処理されたノードに接続する最後のリンクの形状点は、走行可能距離ノードと考えられてもよい（つまり、最適化パスの端部、行き止まりの道路、または制限区域近辺として、予測アルゴリズムが到達した末端ノード）。このような走行可能距離ノードは、走行可能距離の中心からの距離および向きの角度によって画定されてもよい。いくつかの実施形態は、予測内のすべてのノードを走行可能距離ノードとして含んでいてもよく、したがって、さらに詳細でかつ正確な形態を作成できる。
【０２４０】
図２４は、グラフィカル表示２４００〜２４１０を例示する。いくつかの実施形態において、多角形を予測する際に自己横断する線を排除するために行われる補正を示す。いくつかの実施形態では、多角形リストの点は、特定の方向（例えば、時計回り）に順序を付けられてもよい。点は角度が増えるように（時計回り方向に）リストに挿入されてもよい。いくつかの実施形態では、評価されている線を組み合わせると、現在のノードが時計回りまたは反時計回りに向く三角形を形成するかを判定してもよい。
【０２４１】
例えば、表示２４００の例では、様々な点２４２０は時計回り方向に流れるように示される。さらに、現在のノード２４３０は、点２４２０で形成される多角形の外側にあり、したがって、１または複数の点と置換する点の候補となる。
【０２４２】
表示２４１０は、現在のノード２４３０および２つの候補ノードから形成される第１の三角形２４４０と、現在のノード２４３０および２つの他の候補ノードから形成される第２の三角形２４５０を含む。ノード２４３０は、第１の三角形２４４０の場合は、三角形が時計回りに向いているため拒絶されてもよい。一方、ノードは第２の三角形２４５０の場合は、三角形が反時計回りに向いているため評価されてもよい。このような判定は様々な適切な方法で行われてもよい（例えば、ベクトルを３セットの座標でかけて合計した外積を用いて、結果が正か負かを判定することによって）。
【０２４３】
図２５は、グラフィカル表示２５００を例示する。複雑な形状を有する多角形の例３６１０を示し、いくつかの実施形態において、既存の多角形が横断するという対応する検証を示す。図示するように、現在のノード２５２０は、現在は１または複数の候補ノード２５３０を置換することを考慮されている。三角形は現在のノード２５２０および候補ノード２５３０によって形成される。次に、任意の他のノードが三角形内にあるか判定が行われてもよい（本例では、ノード２５４０が図示するように三角形内にある）。このような判定は、表示２３１０で前述したように類似の方法で行われてもよい。
【０２４４】
当業者は、図２４〜２５の表示例は、例えば例示のみを目的とするものであり、異なる実施形態がこのような特徴を様々に異なる方法で、本発明の精神から逸脱せずに実装しうることを認識するであろう。
【０２４５】
図２６は、処理２０００と同様なセンタアウト予測の結果を表すいくつかの実施形態のＧＵＩ例２６００を例示する。図示するように、ＧＵＩ２６００は、地図の部分２６１０と、結果として生じる多角形２６２０を含む。
【０２４６】
当業者は、ＧＵＩ２６００が様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、異なる実施形態は、異なる特定の表示要素を含んでいてもよい。別の例では、異なる実施形態は、異なる色、線のスタイル、および／または他の特徴を用いて、様々な項目の中から識別してもよい。
Ｆ．ビットマップベースの予測
【０２４７】
図２７は、ビットマップベースのアルゴリズムを用いて、車両の走行可能距離を予測するために用いる処理２７００のフローチャートを例示する。このような処理は、例えば、ユーザが走行可能距離の予測をいくつかの実施形態のアプリケーションを用いてリクエストするときに、開始してもよい。
【０２４８】
図示するように、処理は次に、（２７１０で）結果ステップリスト（走行可能距離内のすべてのリンクを含む）を、基本的な走行可能距離の予測アルゴリズムを用いて、前述の処理３２００を参照して生成する。次に、処理は、（２７２０で）インメモリモノクロムビットマップを車両の走行可能距離に基づいて固定サイズまたは動的サイズのいずれかで生成する。次に、処理は（２７３０で）基本座標およびスケール係数を算出する。例えば、いくつかの実施形態において、基本座標は、評価中の地図空域の左下角に関連してもよい（つまり、南西の角）。スケール係数は、ビットマップのサイズおよび／または基本的な走行可能距離の予測アルゴリズムを用いて判定される車両の最大走行可能距離に関連してもよい。
【０２４９】
処理２７００は次に、（２７４０で）関連走行可能距離リンク（または「区分」または「先端」）をモノクロムビットマップにレンダリングする。関連リンクは、基本的な予測アルゴリズムを用いて実施した走行可能距離計算の結果として車両がアクセス可能である任意のリンク（例えば、結果のステップリストに含まれるすべてのリンク）を含んでいてもよい。広い走行可能距離に対して、アルゴリズムは走行可能距離の外側のリンクのみを含むように最適化されてもよく（例えば、距離、コスト、および／または他の適切な要因および／またはパラメータに基づいた走行可能距離の外側の２０パーセント）、これにより処理の負荷が低減する。
【０２５０】
各先端は例えば、起点と端部ノードとの間の単一の線として描かれてもよい。各先端はすべての形状点と共に描かれてもよく、それぞれが適切な厚さで描かれてもよい（例えば、１ピクセル、４ピクセルなど）。先端を描くために、第１の点が読み出され、現在の点として割り当てられてもよい。現在の点はピクセル座標に変換されてもよい。次の点が読み出され、次の点として割り当てられ、（例えば、経度および緯度座標を基本座標から引き、ピクセル倍率によって変換されて）ピクセル座標に変換されてもよい。変換された点が合致しない場合は（つまり、変換された現在の点および次の点が重ならない場合は）、次に、ビットマップ上の２つの点の間に線を引いてもよい。次の点を現在の点に割り当ててもよく、すべての点を検査するまで、次の点を呼び出してもよい。
【０２５１】
その結果として、モノクロムビットマップは、アクセス可能な場所に対してＴＲＵＥ（またはロジック「１」）と定義されるビットを含んでいてもよい。アクセス不可能なであり、および／または道路がない場所に対してＦＡＬＳＥ（またはロジック「０」）と定義されビットを含んでいてもよい。
【０２５２】
処理は次に、（２７５０で）選択したビット（例えば、走行可能距離内のビット）をトレースし、選択したビットの多角形の輪郭を生成する。このようなトレースは、起点を特定することによって実施されてもよい（例えば、画像を右下の角からスキャンして、空ではない最も右のピクセルを探す等）。
【０２５３】
起点は、現在の点として設定されてもよく、現在の方向を「上」として定義してもよい。次に、現在の点を選択した輪郭一般化アルゴリズムに基づいて、結果アルゴリズムに追加してもよい。その後、任意のノンピクセルが現在の方向から開始して現在の点の周りに反時計回り方向にあるかを調べることによって、次に最善な方向を判定する。
【０２５４】
アルゴリズムは次に、選択した方向の次の点に移動し、現在の点を次の点に設定し、現在の方向を新しい方向に（変更する場合は）設定し、現在の点が起点とは異なる場合は、現在の点を結果として得られる多角形に追加してもよい。多角形の輪郭に追加された各結果点は、スケール係数を用いてピクセル座標を変換し、基本座標に追加することによって、世界座標に逆変換されてもよい。
【０２５５】
異なる実施形態は、異なる輪郭一般化アルゴリズムを用いてもよい。例えば、いくつかの実施形態は、一般化を用いなくてもよい（例えば、各輪郭点を結果として生じる多角形に追加してもよい）。これによって、最も詳細な多角形が生成されるが、地図を描くときには（および／または多角形がサーバから無線接続によって送信される必要があるときには）、実行が遅くなりえる多くの点を含むことになる。
【０２５６】
別の例では、いくつかの実施形態は、区域一般化を用いて、新しい点それぞれが、前の点からあまり広い面積にわたらないように確認する。面積の表示（例えば、前の点、中間点、および端部点から形成され、前の点から中間点までのベクトル、および中間点から端部点までを２で割ったベクトルをスパンした外積平行四辺形を用いて算出される三角形）は、最小および／または最大閾値と比較され（例えば、符号付き平行四辺形の面積は閾値区域のセットと比較されてもよい）、中間点を新しい点で置換すべきかどうかを判定してもよい。
【０２５７】
さらに別の例では、いくつかの実施形態は、角度ベースの一般化を用いて、新しい点まで延在する輪郭の最後の線の新しい角度が、最後の線が通る線の角度の範囲を延在し、閾値を超えるかどうかを判定してもよい。閾値を超える場合は、最後の線は新しい点まで延在しなくてもよく、新しい線は輪郭の最後の点を新しい点に接続する。代替的に、角度範囲が受容可能な場合は、線は新しい点まで延在されてもよい。
【０２５８】
処理２７００を様々な特定の詳細を参照して説明してきたが、当業者は、処理は様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、様々な操作はいくつかの実施形態では省略されてもよく、および／または様々な他の操作はいくつかの実施形態では追加されてもよい。別の例では、異なる実施形態は、操作を異なる順序で実施してもよい。さらに別の実施例では、処理はサブ処理のセットに分割されてもよく、および／またはサブ処理としてマクロ処理に含まれてもよい。さらに、異なる実施形態は、処理を少なくとも部分的に様々な基準（例えば、受信したリクエストごとに、継続して、規則的な間隔で）に基づいて実施してもよい。
【０２５９】
図２８は、処理２７００の結果を表す、いくつかの実施形態のＧＵＩ例２８００を例示する。図示するように、ＧＵＩ２８００は、地図の部分２８１０および結果として生じる多角形２８２０を含む。
【０２６０】
当業者は、ＧＵＩ２８００は、様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、異なる実施形態は、異なる特定の表示要素を含んでいてもよい。別の例では、異なる実施形態は、異なる色、線のスタイル、および／または他の特徴を用いて、様々な項目の中から識別してもよい。
Ｇ．制限区域の処理
【０２６１】
前述したように、走行可能距離の予測多角形は端部末端点を様々な適切なアルゴリズムを用いて接続することによって生成されうる。ただし、一部の状況では、車両が侵入できない自然および／または人工の（または指定された）制限区域がある。このような区域の例は湖、湾、海、軍隊基地、公園などである。このような区域が走行可能距離の予測領域に、またはその周辺に存在するという状況では、走行可能距離パスの端部点を単に接続するだけの多角形は、このような区域を横切るか、または完全に含有する。制限区域のこのような処理は、不正確な走行可能距離の予測地図をユーザに提供する結果となることもある。
【０２６２】
いくつかの実施形態は、（地図データベースの）特別なフラグを、このような制限区域と境界を接するノードまたはリンクに関連付けることによって、制限区域を処理する効率的な方法を提供する。隣接するリンクを発見し、それらをそのようなマークして処理することは、地図編集者によって地図編集処理中に実施されてもよい。実際の走行可能距離作成処理では、この特別なフラグを持つリンクに到達すると、それらは端部ノードとしてマークされ、最終多角形に含まれてもよい。このように、演算処理のオーバーヘッドを最小限としつつ、走行可能距離の多角形は制限区域の輪郭をたどる。
【０２６３】
走行可能距離予測は、計算的な負荷の重い処理である。道路図全体を規定の位置から、すべての方向に所望するコストに到達するまで（電気自動車の場合はエネルギレベル）探求しなければならないためである。走行可能距離の予測多角形は各パスの端部点から構築されてもよい。パスの端部はリンクであってよく、所望するコストに到達するか、または行き止まりの道路である。
【０２６４】
一部の事例では、自然のまたは人工の制限区域があり、走行可能距離の多角形が隣接する道路の輪郭をたどることが望ましい。車が到達できる限界が、その輪郭だからである。ただし、多角形がパスの端部ノードまたは行き止まりの道路で構成されている場合は、結果として生じる多角形は、制限区域を横断し得る。
【０２６５】
多角形はパスの端部点または行き止まりを接続するだけである場合は、車両が制限区域（例えば、湾）に近付くと、海岸線を走る道路は含まれず、（所望するエネルギレベルの走行可能距離内であるため）結果として、多角形が湾を通ることになる。この問題に対処する１つの方法は、道路の形状点を分析し、それらを多角形の線と比較し、次に内部の点を含む多角形の形状を調整することである。ただし、この手法には、多角形内部のすべてのノードの分析が必要であるため、演算負荷が非常に重くなる上に、正確な形状が作成されるという保証もない。
【０２６６】
他の手法は、前述の規則に基づいて多角形を作成することであるが、次に、本来の特徴の多角形で前述の多角形を横切ることである。これによって、見かけのよい走行可能距離の予測多角形が実現されるが、まだ不正確でありえる。多角形は運転可能距離を表示すべきであり、境界点はユーザが車両で到達できる場所を識別すべきである。ただし、本来の特徴の多角形を用いる場合は、最も近い道路が走行可能距離の予測境界から離れていることもありえる。なぜなら、クリッピングは実際の道路ではなく、本来の特徴境界に対して行われるためである。多角形のクリッピングはまた、演算負荷が非常に重い操作であり、装置によっては十分高速に実行されないこともある。
【０２６７】
上記の問題に対するより良い解決法は、境界制限区域と境界を接するノードまたはリンクを特別なフラグでマークすることである。フラグが設定され、前述の基本的な走行可能距離の予測アルゴリズムがこのようなノードまたはリンク点に到達すると、点は自動的に末端ステップリストに含まれる（場合によっては、走行可能距離の予測多角形において）。フラグは、１つのビットを利用してもよく、サイズは劇的にまたはまったく、全体的なデータベースのサイズは増えない。走行可能距離の予測アルゴリズムは、したがって、単純かつ効率的に維持されてもよく、リンクが予測多角形に追加されるべきであると判定するには、特別なフラグに単純なチェックが必要なだけである。
【０２６８】
図２９は、制限区域処理に関連するいくつかの実施形態における概念的な地図２９００の画像を例示する。図示するように、制限区域２９１０は、様々なノード２９２０によって囲まれていてもよい。最も近い道路のノードまたはリンクは、フラグまたは他の適切な表示２９３０を含んでいてもよく、それによって、制限区域に最も近い道路のノード（またはリンク）が識別される。このような表示は例えば例示目的として記載し、実際の実装では、フラグまたは、任意の表示上には見えないこともある他のデータ要素であってもよい。いくつかの実施形態では旗の付いたノードは、制限区域周囲の境界を画定してもよい。
【０２６９】
図３０は、いくつかの実施形態が、地図区域内の制限区域を特定するため、およびこのような区域を囲む道路をマークするために用いる、概念的な処理３０００のフローチャートを例示する。このような処理は、例えば、いくつかの実施形態に関連する地図データが生成されるとき、および／またはアクセスされるときに開始される。
【０２７０】
図示するように、処理は、（３０１０で）編集すべき地図データを受信する。次に、処理は、（３０２０で）多角形のリストを生成する。多角形のリストは、受信した地図データが表す地理的区域内の制限区域（例えば、湾、湖、海、軍隊基地、公園など）を表す。このようなリストは、少なくとも部分的に、様々なノード、フラグ、特徴、および／または受信した地図データの他の要素、様々なパラメータ（例えば、ユーザの好み、地図データの正確さなど）、および／または他の適切な要因（例えば、リストは閾値サイズより大きい制限区域のみを含む、一定の種類の制限区域のみを含むなど）に基づいて生成されてもよい。
【０２７１】
次に、処理は、（３０３０で）リストの次の多角形を選択する。処理３０００は次に、反復し、多角の頂点ごとに、頂点に最も近い道路（ノードのセットおよび／または形状点のセットによって画定される）を探す。このような近い道路は特定されてもよく、例えば、各多角形に関連する境界の長方形を用いて初期検索を行い、近い道路を迅速に探してもよい。次に、最も近い道路から多角形の各頂点までが特定されてもよい。
【０２７２】
処理は次に、（３０５０で）各識別された最も近い道路が閾値距離内にあるか（および／または他の適切な評価基準を順守しているか）を判定する。このような距離は、システムの規定値、ユーザの好み、および／または他の適切な要因および／またはパラメータにしたがって画定されてもよい。道路が閾値距離内にあると判定された場合は、処理は（３０６０で）特別なフラグで道路部分に関連するノード（またはリンク）をマークしてもよい。最も近い道路の一部をマーク後、または最も近い道路は閾値外部であると（３０５０で）判定後、処理は（３０７０で）すべての制限区域（または多角形）が評価されたかを判定する。
【０２７３】
処理が、（３０７０で）すべての制限区域が評価されたと判定する場合は、処理を終了する。代替的に、処理がすべての制限区域が評価されていないと判定する場合は、処理は（３０７０で）すべての制限区域が評価されたと判定して終了するまで、操作３０３０〜３０７０が繰り返えされる。
【０２７４】
このような評価の結果として、いくつかの実施形態の地図データベースは、特別なフラグでマークされた制限区域を囲むリンクおよび／またはノードを含んでいてもよい。様々な走行可能距離の予測アルゴリズムは、正確な道路のみをたどるはるかに詳細な多角形を作成してもよい。より正確な走行可能距離の予測多角形のために、道路の形状点さえも（ノードだけではなく）評価されてもよい。これは、特別なフラグセットを備える２つのリンク間の任意の形状点に対して行い得る。ただし、さらに効率的なのは、ノード全体の多角形点のカウントを低く保つノードのみを用いることであり、これでも受容可能な視覚効果を算出すべきである。
【０２７５】
いくつかの実施形態では、方向属性は、各識別された制限区域点（例えば、特別なフラグでマークされた各点）に関連してもよい。方向は、点に関する制限区域の相対的な位置を示していてもよい。例えば、制限区域は、各点および関連方向によって画定されるように、ベクトルの片側にあると想定してもよい（例えば、ベクトルの左側、反時計回りに９０度ベクトルから回転する等）。このように、処理３０００などの処理は、各制限点が走行可能距離多角形の一部であることを保証してもよく（つまり、多角形内部にはないこと）、他の制限区域点のベクトルが多角形によって横断されないように配置されることを保証してもよい。
【０２７６】
処理３０００を様々な特定の詳細を参照して説明してきたが、当業者は、処理は様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、様々な操作はいくつかの実施形態では省略されてもよく、および／または様々な他の操作はいくつかの実施形態では追加されてもよい。別の例では、異なる実施形態は、操作を異なる順序で実施してもよい。さらに別の実施例では、処理はサブ処理のセットに分割されてもよく、および／またはサブ処理としてマクロ処理に含まれてもよい。さらに、異なる実施形態は、処理を少なくとも部分的に様々な基準（例えば、受信したリクエストごとに、継続して、規則的な間隔で）に基づいて実施してもよい。
【０２７７】
図３１は、いくつかの実施形態の、処理３０００（および／または他の適切な処理）の入力および出力を表すＧＵＩ例３１００〜３１１０を例示する。第１のＧＵＩ３１００は、表示された地図の一部３１２０と、制限区域の一部３１４０（本例では、制限区域は海の入り江または湾）と重なる予測多角形３１３０を含む。
【０２７８】
第２のＧＵＩ３１１０は、同一の表示された地図の一部３１２０と、制限区域と重ならないように修正された多角形予測３１５０を含む。
【０２７９】
当業者は、ＧＵＩ３１００が様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、異なる実施形態は、異なる特定の表示要素を含んでいてもよい。別の例では、異なる実施形態は、異なる色、線のスタイル、および／または他の特徴を用いて、様々な項目の中から識別してもよい。
Ｈ．地図データキャッシングおよび読み出し
【０２８０】
図３２は、地図区域３２００のグラフィカル表示を例示する。表示は部分（または「タイル」）３２１０に分割され、効率的なデータ使用およびアクセスを促進するために用いられる。
【０２８１】
図示するように、地図区域３２００は、典型的には長方形として表され、ユーザに表示されてもよい（例えば、車載用ヘッドユニット、スマートフォンなどを用いて）。地図区域は垂直な線３２２０および水平な線３２３０の概念的なセットによって、サブセクション３２１０に分割されてもよい。異なる実施形態では、区域３２００をタイル３２１０が評価に適切なサイズとなるように分割してもよい（例えば、タイルは含まれるデータが使用されている装置のメモリにロードされるようなサイズにされてもよく、タイルは地図区域３２００に描く領域の寸法および特徴に基づいて分割されてもよい等）。異なる実施形態は、異なる数の分割線、異なる数の結果タイル、異なる形の長方形（例えば、高さより幅の方が大きい長方形、幅より高さの方が大きい長方形、または正方形）を含んでいてもよい。
【０２８２】
各タイル３２１０内で、各リンク３２４０は、ノード３２５０が各タイルの区切り３２２０〜３２３０で作成されるように画定される。図示するように、各リンクは完全に単一のタイル３２１０に含まれる。このように、予測アルゴリズムが一部の地図データを必要とする場合、近くのリンクがデータを再ロードしなくても分析に使用可能であるように、すべてのタイルはロードされてもよい。さらに、いくつかの実施形態では、データがリクエストされるときに、隣接するタイルを動的にロードしてもよい（このような「隣接する」タイルは、リクエストされたタイルの隣のタイル、タイルの走行可能距離内のタイルなどを含んでいてもよい）。
【０２８３】
当業者は、図３２の表示は元来概念的なものであり、本発明の精神から逸脱せずに様々な異なる方法で実装されうることを認識するであろう。例えば、異なる実施形態では、地図区域を異なる数の列と行に分割してもよい
【０２８４】
図３３は、データ構造図３３００を例示する。地図データはキャッシュされ、データが少量のメモリしか必要としないように、地図データをキャッシュするために用いる。図示するように、典型的なリンクデータ要素３３１０は、様々なサブ要素（例えば、長さまたは距離、速度、形状点、開始ノード、端部ノード、路上名など）を含んでいる。地図領域（例えば、タイル）は様々な数のリンク（またはリンクなし）を含んでいてもよく、それぞれが関連サブ要素を有する。
【０２８５】
データ要素３３２０は、最適化されたデータ要素を表す。本実施例では、各リンクは、リンクのコスト、および接続するリンクのリストのみを含む（および接続するリンクに移動するための関連コスト）。このように、各リンクに関連するデータは、いくつかの実施形態の予測またはルート計算アルゴリズムで用いるために最適化されてもよい。このような最適化によって、広範囲な地図区域がメモリにロードされ、メモリ空間が必要となるため、データを削除およびリロードしながら効率的な方法で分析される（例えば、ランダムアクセスメモリ（ＲＡＭ）、キャッシュなど）。
【０２８６】
いくつかの実施形態では、オリジナルデータ要素３３１０および最適化されたデータ要素３３２０は、単一のタイルに関連するリンクのリストを含んでいる。このように、タイルがロードされるとき、すべてのリンクは一度にロードされるタイルに関連する。
【０２８７】
当業者は、図３３の表示は元来概念的なものであり、本発明の精神から逸脱せずに様々な特定の方法で実装されうることを認識するであろう。例えば、異なる実施形態は、各リンクに関連する異なる特定のサブ要素を含んでいてもよい。
【０２８８】
図３４は、いくつかの実施形態が地図データの読み出しおよび使用量を最適化するために用いる処理３４００のフローチャートを例示する。いくつかの実施形態では、処理３４００は、最適化されたハードウェアおよび／またはソフトウェアを用いて実装されてもよい（例えば、物理的なおよび／または仮想キャッシュで用いられて、データベース情報を記憶し、素早く読み出してもよい）。このような処理は、例えば、いくつかの実施形態の走行可能距離探求アプリケーションが起動されるときに開始される。
【０２８９】
次に、処理は（３４１０で）情報のリクエストを受信する。このようなリクエストは、様々な適切な基準に基づいて様々な適切な方法で受信してもよい（例えば、アプリケーションは１または複数の適切な要素を用いて現在の位置を判定してもよく、次に現在の位置の周囲の区域の地図情報をリクエストしてもよい）。
【０２９０】
処理は次に、（３４２０で）リクエストされた情報が以前にストレージから読み出されたかを判定する。例えば、いくつかの実施形態において、処理はリクエストされた情報が以前にＲＡＭに記憶されたかを判定してもよい。
【０２９１】
処理３４００が（３４２０で）リクエストされた情報が以前に読み出されていないと判定する場合は、処理は（３４３０で）ロードに使用可能なタイルがあるかを判定する。いくつかの実施形態では、このようなタイルは、リクエストされたリンクの近くのリンクの情報を含んでいてもよく、すべての関連情報がデータのセットに含まれるような構造であってもよい。処理がロードに使用可能なタイルがあると判定する場合は、処理は（３４４０で）タイルを生成する。タイルの生成は、図３２に関して前述したように、地図区域を部分に分割することを含んでいてもよい。代替的に、処理が（３４３０で）タイルがすでに使用可能であると判定する場合は、処理は（３４５０で）関連情報のセットを読み出してもよい。
【０２９２】
情報を読み出した後で（３４５０で）、処理は（３４６０で）読み出された情報を最適化する。このような最適化は図３３に関して前述したように実現されてもよい。いくつかの実施形態では、読み出された情報は、地図データベースの完全な一部を含んでいてもよい（例えば、北米などの地理的区域に関連する地図データベースの情報）。
【０２９３】
読み出された情報を（３４６０で）最適化し、または（３４２０で）情報が以前に読み出されていることを判定した後に、処理は、（３４７０で）読み出された情報を提供する。読み出されたデータを（３４７０で）提供後に、処理を終了する。
【０２９４】
いくつかの実施形態では、すべての使用可能な地図データを起動時（または地図がロードするとき、または他の適切な時間）にロードしてもよい。このように、予測がリクエストされるとき、地図データはすでに分割され、読み出し前に最適化されている。
【０２９５】
処理３４００を様々な特定の詳細を参照して説明してきたが、当業者は、処理は様々に異なる方法で本発明の精神から逸脱せずに実装されうることを認識するであろう。例えば、様々な操作はいくつかの実施形態では省略されてもよく、および／または様々な他の操作はいくつかの実施形態では追加されてもよい。別の例では、異なる実施形態は、操作を異なる順序で実施してもよい。さらに別の実施例では、処理はサブ処理のセットに分割されてもよく、および／またはサブ処理としてマクロ処理に含まれてもよい。さらに、異なる実施形態は、処理を少なくとも部分的に様々な基準（例えば、受信したリクエストごとに、継続して、規則的な間隔で）に基づいて実施してもよい。
ＩＶ．表示アルゴリズムおよびグラフィカルユーザインターフェース
【０２９６】
図３５は、色付きのリンクを用いて車両の走行可能距離を表示するいくつかの実施形態のＧＵＩ例３５００を例示する。このようなＧＵＩは、直観的なユーザインターフェースを提供してもよい。各リンクは色で表示され、各色は予測に対応する（例えば、第１の色は、使用可能な燃料の２５％に基づく走行可能距離内のリンクに関連し、第２の色は使用可能な燃料の５０％に基づく走行可能距離内のリンクに関連する等）。
【０２９７】
本実施例では、地図区域３５１０は様々なリンクと共に表示される。様々なリンクは第１の色３５２０（本例では実線で表す）、第２の色３５３０（本例では第１の種類の点線で表す）、第３の色３５４０（本例では第２の種類の点線で表す）、第４の色３５５０（本例では第３の種類の点線で表す）を有する。
【０２９８】
異なる実施形態は、異なる色の数（および／または異なる線の濃さ、線のパターンなど他の適切な表示）を含んでいてもよい。また、表示装置の性能、ユーザの好み、規定の設定、および／または他の適切な基準によって異なっていてもよい。
【０２９９】
当業者は、ＧＵＩ３５００は本発明の精神から逸脱せずに様々な特定の方法で実装されうることを認識するであろう。例えば、異なる実施形態は異なる特定の表示要素を含んでいてもよい。別の例では、異なる実施形態は異なる色、線のスタイル、および／または他の特徴を用いて、様々な項目間で区別を図ってもよい。
【０３００】
図３６は、混色のリンクを用いて車両の走行可能距離を表示するいくつかの実施形態のＧＵＩ例３６００を例示する。本実施例では、地図区域３５１０は様々な混色の区域で表示される。様々な混色の区域は、第１の色３６１０（本例では第１の調合種類で表す）、第２の色３６２０（本例では第２の調合種類で表す）、第３の色３６３０（本例では第３の調合種類で表す）、および第４の色３６４０（本例では第４の調合種類で表す）を有する。
【０３０１】
いくつかの実施形態では、区域３５１０の各ピクセルを通して繰り返し、混色を判定してもよい。いくつかのピクセルは、すでに関連色を有するリンクに関連してもよい（例えば、図３５のリンク）。関連色を持たない各ピクセルでは、いくつかの実施形態は（割り当てられた色を有する）隣接するピクセルの平均的な色を判定してもよい。いくつかの実施形態は、色が変更されてもよいかを示す各ピクセルのフラグを含んでいてもよい（例えば、混色アルゴリズムを用いて色を生成したか、または色付きのリンクで画定されているか）。
【０３０２】
当業者は、ＧＵＩ３６００は本発明の精神から逸脱せずに様々な特定の方法で実装されうることを認識するであろう。例えば、異なる実施形態は異なる特定の表示要素を含んでいてもよい。別の例では、異なる実施形態は異なる色、線のスタイル、および／または他の特徴を用いて、様々な項目間で区別を図ってもよい。
Ｖ．コンピュータシステム
【０３０３】
多くの前述の処理およびモジュールは、不揮発性ストレージ媒体に記録した少なくとも１つのセットの命令に特有のソフトウェア処理として実装されてもよい。これらの命令が１または複数のコンピュータ要素によって実施されるとき（例えば、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）など）命令によってコンピュータ要素は、命令内で特定されたアクションを実施する。
【０３０４】
図３７は、本発明のいくつかの実施形態が実装されてもよいコンピュータシステム３７００の概略ブロック図を概念的に例示する。例えば、前述のシステムは図１〜３および図９〜１２を参照して、コンピュータシステム３７００を用いて少なくとも部分的に実装されてもよい（代替的に、および／または様々な組み合わせで）。別の例では、記載した処理は、図１６、図１８、図２０〜２２、図２７、図３０、および図３４を参照して、コンピュータシステム３７００を用いて実行される命令のセットを用いて、少なくとも部分的に実装されてもよい。
【０３０５】
コンピュータシステム３７００は、様々な適切な装置を用いて実装されてもよい。例えば、コンピュータシステムは１または複数の個人用コンピュータ（ＰＣ）、サーバ、携帯装置（例えば、スマートフォン）、タブレット装置、および／または任意の他の適切な装置を用いて実装されてもよい。様々な装置は単独で動作し（例えば、コンピュータシステムは単一のＰＣとして実装されてもよい）、または組み合わせて動作してもよい（例えば、コンピュータシステムのいくつかの構成部品は携帯装置によって提供されてもよく、他の構成部品はタブレット装置によって提供されてもよい）。
【０３０６】
コンピュータシステム３７００は、バス３７０５、少なくとも１つの処理要素３７１０、システムメモリ３７１５、リードオンリーメモリ（ＲＯＭ）３７２０、他の構成部品（例えば、グラフィックスプロセッシングユニット）３７２５、入力装置３７３０、出力装置３７３５、永久ストレージ装置３７４０、および／またはネットワークインターフェース３７４５を含む。コンピュータシステム３７００の構成部品は、デジタルおよび／またはアナログ入力信号に基づいた操作を自動的に実施できる電子装置であってもよい。
【０３０７】
バス３７０５はコンピュータシステム３７００の要素のうち、すべての通信パスウェイを表す。このようなパスウェイは、有線、無線、光学、および／または他の適切な通信パスウェイを含んでいてもよい。例えば、入力装置３７３０および／または出力装置３７３５はシステム３７００に無線接続プロトコルまたはシステムを用いて接続してもよい。プロセッサ３７１０は、いくつかの実施形態の処理を実行するために、実行する命令および処理するデータを構成部品から読み出す。構成部品には、システムメモリ３７１５、ＲＯＭ３７２０、および永久ストレージ装置３７４０などがある。このような命令およびデータはバス３７０５に送られる。
【０３０８】
ＲＯＭ３７２０は、静的データおよび命令を記憶する。静的データおよび命令は、プロセッサ３７１０および／またはコンピュータシステムの他の要素で用いられてもよい。永久ストレージ装置３７４０は、リードアンドライトメモリ装置である。この装置は、コンピュータシステム３７００がオフまたは電源が入っていない場合であっても、命令およびデータを記憶する不揮発性メモリユニットである。永久ストレージ装置３７４０は、マスストレージ装置（磁気または光学ディスクおよび対応するディスクドライブなど）を含んでいてもよい。
【０３０９】
コンピュータシステム３７００は、取り外し可能なストレージ装置および／またはリモートストレージ装置を永久ストレージ装置として用いてもよい。システムメモリ３７１５は、ランダムアクセスメモリ（ＲＡＭ）などの揮発性リードアンドライトメモリである。システムメモリは、命令の一部およびプロセッサがランタイム時に用いるデータを記憶する。いくつかの実施形態を実装するために用いられる命令および／またはデータのセットは、システムメモリ３７１５、永久ストレージ装置３７４０、および／またはリードオンリーメモリ３７２０に記憶されてもよい。他の構成部品３７２５は様々な他の機能を実施してもよい。これらの機能は、車両センサと接続することを含んでいてもよい。
【０３１０】
ユーザは、入力装置３７３０によって情報をコンピュータシステムに入力でき、および／またはシステムの様々な操作を行うことができる。入力装置は、キーボード、カーソル制御装置、音声入力装置、映像入力装置、ハンドル制御装置、つまみボタン、および／または他の入力装置を含んでいてもよい。出力装置３７３５は、プリンタ、ディスプレイ、音声装置、触覚フィードバック装置、および／または他の出力装置を含んでいてもよい。一部のまたはすべての入力および／または出力装置は、無線または光学でコンピュータシステムと接続する。
【０３１１】
最後に、図３７に図示するように、コンピュータシステム３７００はネットワーク３７５０にネットワークインターフェース３７４５を通じて接続される。例えば、コンピュータシステム３７００は、インターネットのウェブサーバに接続してもよい。それによって、コンピュータシステム３７００上で実行するウェブブラウザは、ユーザがウェブブラウザで動作するインターフェースと相互作用するとき、ウェブサーバと相互作用してもよい。いくつかの実施形態では、ネットワークインターフェース３７４５は、１または複数のＡＰＩを含んでいてもよい。ネットワークインターフェースおよび関連ネットワーク３７５０によって、システム３７００は様々なリモートストレージ３７６０および／または他の外部構成部品３７６５（例えば、サードパーティサーバ）にアクセスすることができる。
【０３１２】
本明細書および本出願の請求項で用いる「コンピュータ」、「サーバ」、「プロセッサ」、および「メモリ」という用語はすべて電子装置を指す。これらの用語は人または人のグループを排除する。本明細書および本出願の請求項で用いる用語「一時的ストレージ媒体」は完全に有形の、物理的な目的物に制限され、情報を電子装置可読な形式で保存する。これらの用語は任意の無線または他の一時的信号は排除する。
【０３１３】
当業者には、任意のまたはすべてのコンピュータシステム３７００の構成部品は本発明と共に用いられてもよいことが認識されよう。さらに、当業者には多くの他のシステム構成もまた、本発明または本発明の構成部品と共に用いられてもよいことが理解されよう。
【０３１４】
さらに、示した実施例は多くの独立したモジュールを個別の要素として例示したが、当業者にはこれらのモジュールを単一の機能ブロックまたは要素として組み合わせてもよいことが認識されよう。当業者はまた、単一のモジュールを複数のモジュールに分割してよいことも認識されよう。
【０３１５】
本発明は多数の特定の詳細を参照して説明してきたが、当業者には本発明は他の特定の形式で本発明の精神から逸脱せずに実現できることを認識するであろう。例えば、複数の実施形態を具体的な特徴および／または構成部品を参照して説明した。ただし、当業者には他の実施形態も他の種類の特徴および構成部品を用いて実装しえることを認識するであろう。当業者は、本発明が前述の例示的詳細によって制限されず、添付の請求項によって、定義されることを理解するであろう。
【図１】
0006384876.tif 000002
【図２】
0006384876.tif 000003
【図３】
0006384876.tif 000004
【図４】
0006384876.tif 000005
【図５】
0006384876.tif 000006
【図６】
0006384876.tif 000007
【図７】
0006384876.tif 000008
【図８】
0006384876.tif 000009
【図９】
0006384876.tif 000010
【図１０】
0006384876.tif 000011
【図１１】
0006384876.tif 000012
【図１２】
0006384876.tif 000013
【図１３】
0006384876.tif 000014
【図１４】
0006384876.tif 000015
【図１５】
0006384876.tif 000016
【図１６】
0006384876.tif 000017
【図１７】
0006384876.tif 000018
【図１８】
0006384876.tif 000019
【図１９】
0006384876.tif 000020
【図２０】
0006384876.tif 000021
【図２１】
0006384876.tif 000022
【図２２】
0006384876.tif 000023
【図２３】
0006384876.tif 000024
【図２４】
0006384876.tif 000025
【図２５】
0006384876.tif 000026
【図２６】
0006384876.tif 000027
【図２７】
0006384876.tif 000028
【図２８】
0006384876.tif 000029
【図２９】
0006384876.tif 000030
【図３０】
0006384876.tif 000031
【図３１】
0006384876.tif 000032
【図３２】
0006384876.tif 000033
【図３３】
0006384876.tif 000034
【図３４】
0006384876.tif 000035
【図３５】
0006384876.tif 000036
【図３６】
0006384876.tif 000037
【図３７】
0006384876.tif 000038