(57)【特許請求の範囲】
【請求項１】
処理部（５２０）と、前記処理部に応答して出力を提供する出力部（５３０）とを備えるナビゲーション装置であって、
前記処理部（５２０）は、地図データ（５４０）と望ましくない場所を識別する情報を含む回避データ（５５０）とにアクセスでき、
前記処理部（５２０）は、
前記地図データ（５４０）に関連して地理的な場所及び移動の方向を表す場所情報を受信し、
各々がナビゲーション決定地点からの前方経路に対応する複数のナビゲーション選択肢を有するナビゲーション決定地点に前記地理的な場所及び移動の方向が接近するかを前記場所情報及び地図データ（５４０）に基づいて確認し、
前記地図データ（５４０）及び回避データ（５５０）に基づいて、前記ナビゲーション決定地点からの少なくとも１つの前方経路に対して、前記前方経路が望ましくない場所を含むことが不可避であるかを判定し、
少なくとも部分的に前記判定に基づいて結果情報を前記出力部（５３０）に提供するように構成され、
（ｉ）次のナビゲーション決定地点の前に望ましくない場所に到達する場合、又は
（ｉｉ）前記次のナビゲーション決定地点の前に望ましくない場所に到達しないなら、前記次のナビゲーション決定地点からの全ての後続する経路が望ましくない場所を含む場合、
前記少なくとも１つの前方経路が、望ましくない場所を不可避的に含むと判定され、
前記結果情報は、望ましくない場所と関連付けられたコストが、前記望ましくない場所に到着する予想時間から所定時間経過後に低減される場合には、望ましくない場所が望ましくない程度を低減するために前記所定時間待機することの助言を含み、
前記結果情報は、前記所定の待機時間が閾値を超える場合は前記助言を含まず、
前記結果情報は、望ましくない場所と関連付けられたコストが、前記望ましくない場所に到着する予想時間から前記所定時間経過後に増加する場合には、待機または迂回によりコストが増加することを示す忠告を含む
ことを特徴とするナビゲーション装置（５００）。
【請求項２】
前記処理部（５２０）は、
接近するナビゲーション決定地点からの各前方経路、
前記決定地点に接近する経路の継続に対応する前記接近するナビゲーション決定地点からの前方経路、
接近するナビゲーション決定地点からの、事前計画された経路に沿う前方経路、
のいずれかに対して判定を実行することを特徴とする請求項１に記載のナビゲーション装置（５００）。
【請求項３】
前記回避データ（５５０）は、有料道路、課税対象となる経路、渋滞課金ゾーン、高さ制限のある経路、幅制限のある経路及び重量制限のある経路のうちの少なくとも１つを望ましくないと識別することを特徴とする請求項１又は２に記載のナビゲーション装置（５００）。
【請求項４】
前記ナビゲーション装置（５００）は、望ましくない場所に到達する予想時間又は現在の時間の少なくとも一方を表す時間データを受信するように構成されており、
前記回避データ（５５０）は時間に依存し、
前記処理部（５２０）は少なくとも部分的に前記時間データに基づいて前記判定を実行することを特徴とする請求項１乃至３の何れか１項に記載のナビゲーション装置（５００）。
【請求項５】
前記処理部（５２０）は、望ましくない場所が望ましくない程度が所定期間内に変化するかを調査し、
この調査の結果は、前記前方経路が望ましくない場所を含むことが不可避であるかの判定において使用され、且つ／又は
前記出力部（５３０）に提供される結果情報はこの調査の結果を含むことを特徴とする請求項４に記載のナビゲーション装置（５００）。
【請求項６】
前記出力部（５３０）からの前記出力は、望ましくない場所を回避するための経路又は方向を含むことを特徴とする請求項１乃至５の何れか１項に記載のナビゲーション装置（５００）。
【請求項７】
前記判定を実行する時、
決定地点への進入路で折り返すナビゲーション決定地点からの経路、
決定地点への進入路を後戻りするナビゲーション決定地点からの経路、あるいは
閉ループを形成するナビゲーション決定地点からの経路
のうちの少なくとも１つは、前記処理部により前記決定地点からの前方経路であると判断されないことを特徴とする請求項１乃至６の何れか１項に記載のナビゲーション装置（５００）。
【請求項８】
前記出力部（５３０）からの前記出力は、前記処理部（５２０）から受信した前記結果情報に基づく警告を含むことを特徴とする請求項１乃至７の何れか１項に記載のナビゲーション装置（５００）。
【請求項９】
前記ナビゲーション装置（５００）は位置決め装置（３１５）を含み、前記位置決め装置（３１５）は、場所情報を判定するように構成され、前記場所情報は、前記位置決め装置（３１５）の地理的な場所及び移動方向を表すことを特徴とする請求項１乃至８の何れか１項に記載のナビゲーション装置（５００）。
【請求項１０】
前記ナビゲーション装置（５００）はサーバであり、前記場所情報はリモート装置から受信されることを特徴とする請求項１乃至７の何れか１項に記載のナビゲーション装置。
【請求項１１】
請求項１０に記載のナビゲーション装置（５００；１５００）と、
前記リモート装置と、を備えるシステムであって、
前記リモート装置は、前記場所情報を判定するように構成された位置決め装置（３１５）であり、前記場所情報は、前記位置決め装置（３１５）の地理的な場所及び移動方向を表すことを特徴とするシステム。
【請求項１２】
ナビゲーション装置におけるナビゲーション方法であって、
前記ナビゲーション装置が、地理的な場所及び移動方向を表す場所情報を受信する工程と、
前記ナビゲーション装置が、各々がナビゲーション決定地点からの前方経路に対応する複数のナビゲーション選択肢を有するナビゲーション決定地点に前記地理的な場所及び移動方向が接近するかを前記場所情報に基づいて確認する工程と、
前記ナビゲーション装置が、望ましくない場所を識別する情報にアクセスする工程と、
前記ナビゲーション装置が、望ましくない場所を識別する前記情報に基づいて、ナビゲーション決定地点からの少なくとも１つの前方経路に対して前記前方経路が望ましくない場所を含むことが不可避であるかを判定する工程と、
前記ナビゲーション装置が、前記判定に応答して結果情報を出力する工程と
を備え、
（ｉ）次のナビゲーション決定地点の前に望ましくない場所に到達する場合、又は
（ｉｉ）前記次のナビゲーション決定地点の前に望ましくない場所に到達しないなら、前記次のナビゲーション決定地点からの全ての後続する経路が望ましくない場所を含む場合、
前記少なくとも１つの前方経路が、望ましくない場所を不可避的に含むと判定され、
前記結果情報は、望ましくない場所と関連付けられたコストが、前記望ましくない場所に到着する予想時間から所定時間経過後に低減される場合には、望ましくない場所が望ましくない程度を低減するために待機することの助言を含み、
前記結果情報は、待機時間が閾値を超える場合は前記助言を含まず、
前記結果情報は、望ましくない場所と関連付けられたコストが、前記望ましくない場所に到着する予想時間から前記所定時間経過後に増加する場合には、待機または迂回によりコストが増加することを示す忠告を含む
ことを特徴とする方法。
【請求項１３】
ナビゲーション装置の処理部で実行された場合に、前記ナビゲーション装置に請求項１２に記載の方法を実行させる命令を含むコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置、システム及び方法に関する。本発明の例示的な実施形態は、ポータブルナビゲーション装置（いわゆるＰＮＤ）に関し、特に全地球測位システム（ＧＰＳ）信号受信及び処理機能性を含むＰＮＤに関する。他の実施形態は、更に一般的には、経路計画及び／又はナビゲーションの機能性を提供するためにナビゲーションソフトウェアを実行するように構成されるあらゆる種類の処理装置に関する。
【背景技術】
【０００２】
ＧＰＳ（全地球測位システム）信号の受信及び処理機能性を含むポータブルナビゲーション装置（ＰＮＤ）は既知であり、車両搭載型又は他の車両ナビゲーションシステムとして広く採用されている。
【０００３】
一般的に、現在のＰＮＤは、プロセッサ、メモリ（揮発性及び不揮発性のうちの少なくとも一方、並びに一般的にはその双方）及び前記メモリ内に格納された地図データを含む。プロセッサ及びメモリは、ソフトウェアオペレーティングシステムが確立される実行環境を提供するように協働し、また、ＰＮＤの機能性の制御を可能にし且つ種々の他の機能を提供するために１つ以上の追加のソフトウェアプログラムが提供されることは一般的なことである。
【０００４】
通常、これらの装置は、ユーザが装置と対話し且つ装置を制御できるようにする１つ以上の入力インタフェースと、ユーザに情報を中継する１つ以上の出力インタフェースとを更に含む。出力インタフェースの例には、表示装置及び可聴出力用スピーカが含まれる。入力インタフェースの例には、オン／オフ動作又は装置の他の機能を制御する１つ以上の物理ボタン（ボタンは必ずしも装置自体にある必要はなく、装置が車両に内蔵されている場合はステアリングホイール上にあってもよい）及びユーザ音声を検出するマイクが含まれる。特定の好適な１つの構成において、出力インタフェースディスプレイは、ユーザがタッチすることで装置を動作させる際に使用する入力インタフェースを更に提供するためにタッチセンシティブディスプレイとして（又はタッチセンシティブオーバレイ等を使用して）構成されてもよい。
【０００５】
多くの場合、この種の装置は、電力及びオプションとしてデータ信号を装置に対して送受信する際に使用する１つ以上の物理コネクタインタフェースを含み、オプションとして、セルラ電気通信、並びに例えばＷｉ−Ｆｉ及びＷｉ−Ｍａｘ  ＧＳＭ等の他の信号及びデータネットワークを介する通信を可能にする１つ以上の無線送信機／受信機を含む。
【０００６】
この種のＰＮＤ装置は、場所データを含む衛星放送信号を受信し且つその後装置の現在地を判定するために処理する際に使用するＧＰＳアンテナを更に含む。
【０００７】
ＰＮＤ装置は、現在の角度及び直線加速度、また、ＧＰＳ信号から導出された場所情報に関連して、装置及びそれが搭載される車両の相対的な変位及び速さを判定するために処理される信号を生成する電子ジャイロスコープ及び加速度計を更に含んでもよい。通常、そのような機能は車両搭載型のナビゲーションシステムに備えるのが最も一般的であるが、ＰＮＤ装置に備えることが得策である場合にはＰＮＤ装置に備えてもよい。
【０００８】
そのようなＰＮＤの有用性は、主に、第１の場所（一般に、出発地又は現在地）と第２の場所（一般に、目的地）との間の経路を判定する機能にある。装置のユーザは、多種多様な種々の方法、例えば郵便番号、道路名及び番地、以前に格納した「既知」の目的地（有名な場所、公共の場所（運動場又は水泳プール等）又は他の地点情報等）、並びにお気に入りの目的地又は最近訪れた目的地のいずれかにより、これらの場所を入力できる。
【０００９】
一般にＰＮＤは、地図データから出発地の住所の場所と目的地の住所の場所との間の「最善」又は「最適」な経路を算出することがソフトウェアにより可能になる。「最善」又は「最適」な経路は、所定の基準に基づいて判定され、必ずしも最速又は最短の経路である必要はない。運転者を案内する経路の選択は非常に高度である可能性があり、選択された経路は、既存の予測された動的に且つ／又は無線で受信された交通及び道路情報、道路速度に関する履歴情報、並びに道路の選択肢を判定する要因に対する運転者自身の好みを考慮してもよい（例えば運転者は、経路が高速道路又は有料道路を含むべきでないことを指定してもよい）。
【００１０】
更に装置は、道路及び交通状況を継続的に監視し、状況変化によりとられる残りの行程に対して経路を変更することを提案又は選択してもよい。種々の技術（例えば、移動電話データ交換、固定カメラ、ＧＰＳフリートトラッキング）に基づくリアルタイム交通監視システムは、交通遅滞を識別し、その情報を通知システムに供給するために使用されている。
【００１１】
この種のＰＮＤは、一般に、車両のダッシュボード又はフロントガラスに搭載されてもよいが、車両のラジオの内蔵コンピュータの一部又は実際には車両自体の制御システムの一部として形成されてもよい。ナビゲーション装置は、ＰＤＡ（ポータブルデジタルアシスタント）、メディアプレーヤ又は移動電話等のハンドヘルドシステムの一部であってもよい。これらの場合、ハンドヘルドシステムの標準的な機能性は、経路計算及び計算経路に沿うナビゲーションの双方を実行するためにソフトウェアを装置にインストールすることにより拡張される。
【００１２】
経路計画及びナビゲーション機能性は、適切なソフトウェアを実行するデスクトップ又は移動計算リソースにより提供されてもよい。例えば、Ｒｏｙａｌ  Ａｕｔｏｍｏｂｉｌｅ  Ｃｌｕｂ（ＲＡＣ）は、ｈｔｔｐ：／／ｗｗｗ．ｒａｃ．ｃｏ．ｕｋにおいてオンライン経路計画及びナビゲーション機能を提供する。この機能により、ユーザは出発地及び目的地を入力でき、その後ユーザのＰＣが接続されるサーバは、経路（経路の方位はユーザにより指定されてもよい）を計算し、地図を生成し、選択した出発地から選択した目的地までユーザを案内するための全ナビゲーション命令の集合を生成する。更にこの機能は、計算経路の擬似３次元レンダリングを提供し、ユーザが経路に沿って移動することをシミュレートし且つそれにより計算経路のプレビューをユーザに提供する経路プレビュー機能性を提供する。
【００１３】
ＰＮＤにおいて、経路が計算されると、ユーザはオプションとして提案された経路のリストから所望の計算経路を選択するためにナビゲーション装置と対話する。オプションとして、ユーザは、例えば特定の経路、道路、場所又は基準が特定の行程に対して回避されること又は必須であることを指定することにより経路選択処理を仲介又は誘導してもよい。ＰＮＤの経路計算の側面は１つの主な機能を形成し、そのような経路に沿うナビゲーションは別の主な機能である。
【００１４】
計算経路に沿うナビゲーション中、そのようなＰＮＤは、経路の終点、すなわち所望の目的地まで選択した経路に沿ってユーザを案内するための視覚命令及び／又は可聴命令を提供するのが一般的である。また、ＰＮＤは、ナビゲーション中に画面上に地図情報を表示するのが一般的である。そのような情報は、表示された地図情報が装置の現在地及び従って装置が車両搭載型のナビゲーションに使用されている場合はユーザの現在地又はユーザの車両の現在地を表すように画面上で定期的に更新される。
【００１５】
一般に画面上に表示されたアイコンは、装置の現在地を示し、装置の現在地近傍の現在の道路及び周囲の道路の地図情報と共に中央に置かれ、他の地図の特徴も表示される。更にナビゲーション情報は、オプションとして表示された地図情報の上側、下側又は片側のステータスバーに表示されてもよく、ナビゲーション情報の例には、ユーザが走行する必要のある現在の道路から次の進路変更までの距離が含まれ、場合によってはその進路変更の特性は、例えば左折又は右折である特定の種類の進路変更を示す更なるアイコンで表される。更にナビゲーション機能は、経路に沿ってユーザを案内する際に使用される可聴命令の内容、継続時間及びタイミングを判定する。理解されるように、「１００ｍ先で左折」等の単純な命令は、かなりの処理及び解析を必要とする。上述したように、装置とのユーザ対話は、タッチスクリーンによって行われてもよく、更に又はあるいはステアリングコラムリモコン、音声起動又は他の適切なあらゆる方法によって行われてもよい。
【００１６】
装置により提供された更なる重要な機能は、ユーザがナビゲーション中に事前に計算された経路から外れた（偶然又は意図的に）場合、別の経路の方が適切であることをリアルタイム交通状況が指示し且つ装置がそのような状況を自動的に認識することを適切に可能にされる場合、又はユーザが何らかの理由で装置に能動的に経路再計算を実行させる場合の自動経路再計算である。
【００１７】
更に、ユーザが規定した基準で経路を計算できることは既知である。例えばユーザは、装置により景色のよい経路が計算されることを好んでもよく、あるいは交通渋滞が起こる可能性が高いか、起こることが予想されるか又は現在起こっているあらゆる道路を回避することを要求してもよい。次に、装置のソフトウェアは種々の経路を計算し、例えば景色が美しい所としてタグ付けされた地点情報（ＰＯＩとして既知である）を経路に沿って最も多く含む経路をより有利に重み付けするか、あるいは特定の道路上の交通状況を示す格納情報を使用することにより、起こる可能性のある渋滞又はそのために起こる遅滞のレベルに関して計算経路を順序付けする。更に他のＰＯＩに基づく経路計算及びナビゲーション基準、並びに交通情報に基づく経路計算及びナビゲーション基準が可能である。
【００１８】
経路計算及びナビゲーション機能はＰＮＤの全体的な有用性に対して必須であるが、装置を純粋に情報表示に使用できる。すなわち、装置の現在地に関連する地図情報のみが表示され、経路が全く計算されておらず、装置が現在ナビゲーションを全く実行していない「フリードライビング」用に使用できる。多くの場合、そのような動作モードは、移動するのに使用するように要求される経路をユーザが既に認識しており且つナビゲーション支援を必要としない場合に適用可能である。
【００１９】
上述したこの種の装置、例えばトムトム社（ＴｏｍＴｏｍ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂ．Ｖ．）が製造及び供給する７２０Ｔモデルは、ユーザがある位置から別の位置までナビゲートできるようにする信頼できる手段を提供する。
【００２０】
目的地までの経路が行程を開始する前に計算される場合、経路で遭遇する可能性のある望ましくない場所をユーザに通知できる。望ましくない場所の例には、有料道路、低い橋、狭い道路、重量制限のある道路等がある。ユーザは、その経路を受け入れるか又は別の経路を使用するかを選択できてもよい。しかし、フリードライビングの場合、装置は、ユーザがどこに向かって運転しようとしているか認識できないため、事前計算された経路の望ましくない場所をチェックすることにより望ましくない場所をユーザに事前に通知できない。
【００２１】
事前計算された経路に従う場合、望ましくない場所に対するユーザの許容度は、移動中に変化する可能性がある。すなわち、例えばユーザが予定より遅れている場合、有料道路はより望ましくなる可能性がある。従って、ユーザは望ましくない場所を回避するか否かの決定を遅らせたい場合がある。場合によっては、経路が最初に計算された後、特定の時間に無料となる有料道路等の場所が望ましくなくなる可能性がある。そのような場合、その場所への到着時間は、望ましくないか否か又は望ましくない程度に影響を及ぼす可能性がある。すなわち、その場所への実際の到着時間は、経路が最初に計算された時の予想到着時間と非常に異なることがある。
【００２２】
いくつかの欧州の国において計画されている道路課税方式は、望ましくない場所に関する情報をユーザに提供することの要望を高める可能性が高く、望ましくない場所と考えられるものの複雑さを増加するだろう。例えばオランダにおいて、車両はＧＰＳを使用して追跡され、車種、使用法、使用される道路及び車両が走行した時間に基づいて課税されることが計画されている。特に、税額は利用される経路及びその経路を使用する時間に依存することになる。従って、使用するのに高額な道路ほど望ましくなくなる。場合によっては、コストは時間に依存する。現在の装置は、そのような経路計画の課題に関するユーザの要望に対処していない。
【００２３】
本発明の目的は、上記の１つ以上の問題に対処することである。
【発明の概要】
【００２４】
この目的のために、本発明の１つの側面は、処理部（５２０）と、処理部に応答して出力を提供する出力部（５３０）とを備えるナビゲーション装置を提供する。処理部（５２０）は、地図データ（５４０）と望ましくない場所を識別する情報を含む回避データ（５５０）とにアクセスでき、処理部（５２０）は、地図データ（５４０）に関連して地理的な場所及び移動の方向を表す場所情報を受信し、各々がナビゲーション決定地点からの前方経路に対応する複数のナビゲーション選択肢を有するナビゲーション決定地点に地理的な場所及び移動の方向が接近するかを場所情報及び地図データ（５４０）に基づいて確認し、地図データ（５４０）及び回避データ（５５０）に基づいて、ナビゲーション決定地点からの少なくとも１つの前方経路に対して、前方経路が望ましくない場所を含むことが不可避であるかを判定し、少なくとも部分的にその判定に基づいて結果情報を出力部（５３０）に提供するように構成される。
【００２５】
前方経路に沿って次のナビゲーション決定地点の前に望ましくない場所に到達する場合、前方経路は望ましくない場所を含むことが不可避であると判定されてもよい。
【００２６】
前方経路に沿って後続するナビゲーション決定地点からの後続する全ての経路が望ましくない場所を含む場合、前方経路は望ましくない場所に至ることが不可避であると判定されてもよい。
【００２７】
処理部は、接近するナビゲーション決定地点からの各前方経路、決定地点に接近するように経路を進むことに対応する接近するナビゲーション決定地点からの前方経路、接近するナビゲーション決定地点からの前方経路、事前計画された経路に沿う前方経路のいずれかに対して判定を実行してもよい。
【００２８】
回避データは、有料道路、課税対象となる経路、渋滞課金ゾーン、高さ制限のある経路、幅制限のある経路及び重量制限のある経路のうちの少なくとも１つを望ましくないと識別してもよい。
【００２９】
ナビゲーション装置は、望ましくない場所に到達する予想時間又は現在の時間の少なくとも一方を表す時間データを受信するように構成されてもよい。ここで、回避データは時間に依存し、処理部は少なくとも部分的に時間データに基づいて判定を実行する。
【００３０】
処理装置は、望ましくない場所が望ましくない程度が所定期間内に変化するかを調査してもよく、この調査の結果は、前方経路が望ましくない場所を含むことが不可避であるかの判定において使用されてもよく、且つ／又は出力部に提供される結果情報はこの調査の結果を含んでもよい。
【００３１】
結果情報は、望ましくない場所が望ましくない程度を低減するために待機することの助言を含んでもよい。
【００３２】
出力装置からの出力は、望ましくない場所を回避するための経路又は方向を含んでもよい。
【００３３】
いくつかの実施形態において、判定を実行する時、決定地点への進入路で折り返すナビゲーション決定地点からの経路、決定地点への進入路を後戻りするナビゲーション決定地点からの経路、あるいは閉ループを形成するナビゲーション決定地点からの経路のうちの少なくとも１つは、処理部により決定地点からの前方経路であると考えられない。
【００３４】
出力装置からの出力は、処理部から受信した結果情報に基づく警告を含んでもよい。
【００３５】
ナビゲーション装置は位置決め装置を含んでもよい。位置決め装置は、場所情報を判定するように構成され、場所情報は、位置決め装置の地理的な場所及び移動方向を表す。
【００３６】
ナビゲーション装置はサーバであってもよく、場所情報はリモート装置から受信される。
【００３７】
本発明の別の態様は、ナビゲーション装置とリモート装置とを備えるシステムを提供する。リモート装置は、場所情報を判定するように構成された位置決め装置であり、場所情報は、位置決め装置の地理的な場所及び移動方向を表す。
【００３８】
本発明の別の態様は、機械により実現されるナビゲーション方法であって、地理的な場所及び移動方向を表す場所情報を受信することと、各々がナビゲーション決定地点からの前方経路に対応する複数のナビゲーション選択肢を有するナビゲーション決定地点に地理的な場所及び移動方向が接近するかを場所情報に基づいて確認することと、望ましくない場所を識別する情報に基づいて、ナビゲーション決定地点からの少なくとも１つの前方経路に対して前方経路が望ましくない場所を含むことが不可避であるかを判定することと、判定に応答して結果情報を出力することとを備える方法を提供する。
【００３９】
別の態様によると、ナビゲーション装置は、コスト関数に基づいて地図データに対して規定される経路のコストを評価するための情報を含むコストデータ及び地図データを格納するように構成される記憶部と、記憶部により格納されたデータにアクセスできる処理部と、処理部による判定に基づいて出力を提供するように構成される出力部とを備える。コストデータは時間依存コストデータを含み、時間依存コストデータは、対応する経路を走行する時間に依存して変化し、処理部は、出発位置、出発時間及び地図データに対する経路を受信し、経路に対するコストが待機することにより低減されるか又は経路の一部分に関連するコストがその経路の一部分に到達する前に待機することにより増加するかの少なくとも一方を判定し、判定に基づいて出力部の出力を制御するように構成される。
【００４０】
これらの実施形態の利点を以下に説明する。これらの実施形態の各々の更なる詳細及び特徴は、添付の従属請求項及び以下の詳細な説明において規定する。
【図面の簡単な説明】
【００４１】
添付の図面を参照して、本発明の教示の種々の態様及びそれらの教示を具体化する構成について以下に例として説明する。
【図１】図１は、全地球測位システム（ＧＰＳ）を示す概略図である。
【図２】図２は、ナビゲーション装置を提供するように構成された電子構成要素を示す概略図である。
【図３】図３は、ナビゲーション装置が無線通信チャネルを介して情報を受信する方法を示す概略図である。
【図４ａ】、
【図４ｂ】図４ａ及び図４ｂは、ナビゲーション装置を示す透視図である。
【図５】図５は、本発明の一実施形態に係るナビゲーション装置を示す図である。
【図６】図６は、本発明の一実施形態に係るナビゲーション装置により実行される方法を示すフローチャートである。
【図７】図７は、図６の方法を示す道路網の一例を示す図である。
【図８】図８は、本発明の別の実施形態に係るナビゲーション装置により実行される方法を示すフローチャートである。
【図９】図９は、図８の方法を示す道路網の一例を示す図である。
【図１０】図１０は、ユーザの方向を単に逆にする経路の一例を示す図である。
【図１１】図１１は、本発明の別の実施形態に係るナビゲーション装置により実行される方法を示すフローチャートである。
【図１２ａ】図１２ａは、本発明の一実施形態に係る方法を示す道路網の一例を示す図である。
【図１２ｂ】図１２ｂは、図１１の方法に従って図１２ａの道路網における可能な経路を示す図である。
【図１３】図１３は、本発明の一実施形態に係るナビゲーション装置を示す図である。
【発明を実施するための形態】
【００４２】
本発明の好適な実施形態について、特にＰＮＤを参照して説明する。しかし、本発明の教示はＰＮＤに限定されず、経路計画及びナビゲーション機能性を提供するためにナビゲーションソフトウェアを実行するように構成されるどんな種類の処理装置にも例外なく適用可能である。従って、本出願において、ナビゲーション装置は、ＰＮＤ、車両に内蔵されたナビゲーション装置、あるいは実際には経路計画及びナビゲーションソフトウェアを実行する計算リソース（デスクトップ又はポータブルパーソナルコンピュータ（ＰＣ）、移動電話、あるいはポータブルデジタルアシスタント（ＰＤＡ）等）として実装されるかにかかわらず、どんな種類の経路計画及びナビゲーション装置も含むことを意図する（これに限定されない）。
【００４３】
本明細書における部又はモジュールに対する参照は、特に限定することを意図せず、そのようなモジュール又は部の機能性は複数の構成要素により提供されてもよい。同様に、個々の構成要素は、複数の部及び／又はモジュールの機能性を提供するか又はそれに寄与する。種々の部及びモジュールは、ハードウェア、ソフトウェア又はそれら２つの組み合わせで実現されてもよい。特に指定のない限り、種々の部又はモジュールは種々の場所に提供されてもよく、個々のモジュールは複数の場所の間で分散されてもよい。
【００４４】
格納されているデータ又は情報に対する参照は、大容量記憶装置（光ディスク及び磁気ディスク等）又はアクティブメモリ（ＲＡＭ等）による記憶を含む。「〜に格納された」又は「〜の」データ又は情報に対する参照は、「〜にアクセス可能な」に対する省略表現として使用され、特に指定のない限り、記憶装置の物理的な場所を示さない。
【００４５】
本発明の種々の実施形態を以下に説明する。これらの実施形態の特徴は、必要以上の実験をせずに種々の方法で組み合わせることができることが当業者には明らかだろう。
【００４６】
上記条件を考慮すると、図１は、ナビゲーション装置により使用可能な全地球測位システム（ＧＰＳ）の例を示す図である。そのようなシステムは既知であり、種々の目的で使用される。一般に、ＧＰＳは、連続した位置、速度、時間及びいくつかの例においては無数のユーザに対する方向情報を判定できる衛星無線を使用したナビゲーションシステムである。以前はＮＡＶＳＴＡＲとして既知であったＧＰＳは、極めて正確な軌道で地球を周回する複数の衛星を含む。これらの正確な軌道に基づいて、ＧＰＳ衛星は自身の場所を１つ又は複数の受信ユニットに中継できる。
【００４７】
特にＧＰＳデータを受信する機能を備える装置がＧＰＳ衛星信号に対する無線周波数の走査を開始すると、ＧＰＳシステムは実現される。ＧＰＳ衛星から無線信号を受信すると、装置は、複数の種々の従来の方法のうちの１つを使用してその衛星の正確な場所を判定する。殆どの例において、装置は、少なくとも３つの異なる衛星信号を取得するまで信号の走査を継続する（尚、標準的な方法ではないが、２つの信号だけでも他の三角測量技術を使用して位置を判定できる）。幾何学的三角測量を実現すると、受信機は、３つの既知の位置を利用して、衛星に対する自身の２次元位置を判定する。これは既知の方法で行われる。更に、第４の衛星信号を取得することにより、受信装置は、同一の幾何学計算によって既知の方法でその３次元位置を計算できる。位置及び速度データは、無数のユーザにより連続的にリアルタイムで更新可能である。
【００４８】
図１に示すように、ＧＰＳシステム全体を図中符号１００で示す。複数の衛星１２０は、地球１２４の周囲の軌道上にある。各衛星１２０の軌道は、他の衛星１２０の軌道と必ずしも同期せず、実際には非同期である可能性が高い。ＧＰＳ受信機１４０は、種々の衛星１２０からスペクトル拡散ＧＰＳ衛星信号１６０を受信するものとして示される。
【００４９】
各衛星１２０から連続的に送信されるスペクトル拡散信号１６０は、非常に正確な原子時計を使用して達成された非常に正確な周波数標準を利用する。そのデータ信号送信１６０の一部である各衛星１２０は、その特定の衛星１２０を示すデータストリームを送信する。一般に、ＧＰＳ受信機装置１４０が、ＧＰＳ受信機装置１４０に対する少なくとも３つの衛星１２０からスペクトル拡散ＧＰＳ衛星信号１６０を取得し、三角測量によりその２次元位置を計算することが当業者には理解される。追加の信号を取得した結果、合計４つの衛星１２０から信号１６０を取得することになり、これによりＧＰＳ受信機装置１４０は、既知の方法でその３次元位置を計算できる。
【００５０】
図２は、ブロック構成要素の形式で本発明の好適な一実施形態に係るナビゲーション装置２００の電子構成要素の表現を示す図である。尚、ナビゲーション装置２００のブロック図は、ナビゲーション装置の全ての構成要素を含むものではなく、構成要素の多くの例を表すだけである。
【００５１】
ナビゲーション装置２００は筺体（不図示）内に配置される。筐体は、入力装置２２０及び表示画面２４０に接続されたプロセッサ２１０を含む。入力装置２２０は、キーボード装置、音声入力装置、タッチパネル及び／又は情報を入力するのに利用される他のあらゆる既知の入力装置を含むことができる。表示画面２４０は、例えばＬＣＤディスプレイ等のあらゆる種類の表示画面を含むことができる。特に好適な構成において、ユーザが複数の表示選択肢のうちの１つを選択するか又は複数の仮想ボタンのうちの１つを有効にするために表示画面２４０の一部分にタッチすることのみが必要であるように、入力装置２２０及び表示画面２４０はタッチパッド又はタッチスクリーン入力を含む一体型入力表示装置に一体化される。
【００５２】
ナビゲーション装置は、例えば可聴出力装置（例えば、スピーカ）である出力装置２６０を含んでもよい。出力装置２６０がナビゲーション装置２００のユーザに対して可聴情報を生成できるため、入力装置２４０は入力音声コマンドを受信するマイク及びソフトウェアを更に含むことができることが同様に理解されるべきである。
【００５３】
ナビゲーション装置２００において、プロセッサ２１０は、接続２２５を介して入力装置２２０に動作可能に接続され且つ入力装置２２０から入力情報を受信するように設定され、また、出力接続２４５を介して表示画面２４０及び出力装置２６０のうち少なくとも一方に動作可能に接続されて出力情報を出力する。更にプロセッサ２１０は、接続２３５を介してメモリ２３０に動作可能に接続され、接続２７５を介して入出力（Ｉ／Ｏ）ポート２７０との間で情報を送受信するように更に構成される。ここで、Ｉ／Ｏポート２７０は、ナビゲーション装置２００の外部のＩ／Ｏ装置２８０に接続可能である。外部Ｉ／Ｏ装置２８０は、例えばイヤホン等の外部リスニング装置を含んでもよいが、これに限定されない。更にＩ／Ｏ装置２８０への接続は、例えばイヤホン又はヘッドフォンへの接続のため及び／又は移動電話への接続のためのハンズフリー動作及び／又は音声起動動作のために、カーステレオユニット等の他のいかなる外部装置への有線接続又は無線接続であってもよい。移動電話接続は、例えばナビゲーション装置２００とインターネット又は他のあらゆるネットワークとの間のデータ接続を確立するため、並びに／あるいは例えばインターネット又は他のネットワークを介するサーバへの接続を確立するために使用されてもよい。
【００５４】
図２は、接続２５５を介するプロセッサ２１０とアンテナ／受信機２５０との間の動作可能な接続を更に示す。アンテナ／受信機２５０は、例えばＧＰＳアンテナ／受信機であってもよい。図中符号２５０で示すアンテナ及び受信機は図示するために概略的に組み合わされるが、アンテナ及び受信機は別個に配置される構成要素であってもよく、例えばアンテナはＧＰＳパッチアンテナ又はヘリカルアンテナであってもよいことが理解されるだろう。
【００５５】
更に、図２に示す電子構成要素が従来の方法で電源（不図示）により電力を供給されることが当業者には理解されるだろう。当業者により理解されるように、図２に示す構成要素の種々の構成が本出願の範囲内であると考えられる。例えば図２に示す構成要素は、有線接続及び／又は無線接続等を介して互いに通信していてもよい。従って、本出願のナビゲーション装置２００の範囲は、ポータブル又はハンドヘルドナビゲーション装置２００を含む。
【００５６】
また、図２のポータブル又はハンドヘルドナビゲーション装置２００は、例えば自転車、モータバイク、自動車又は船舶等の乗り物に既知の方法で接続されるか又は「ドッキング」される。そのようなナビゲーション装置２００は、ポータブルナビゲーション又はハンドヘルドナビゲーション用にドッキング場所から取り外し可能である。
【００５７】
次に図３を参照すると、ナビゲーション装置２００は、デジタル接続（例えば、既知のＢｌｕｅｔｏｏｔｈ技術を介するデジタル接続等）を確立する移動装置（不図示）（移動電話、ＰＤＡ及び／又は移動電話技術を有するあらゆる装置等）を介してサーバ３０２との「モバイル」又は電気通信ネットワーク接続を確立してもよい。その後、移動装置は、そのネットワークサービスプロバイダを介してサーバ３０２とのネットワーク接続（例えば、インターネットを介する）を確立できる。従って、「モバイル」ネットワーク接続は、ナビゲーション装置２００（単独で且つ／又は車両に搭載されて移動するため移動装置であってもよく且つ多くの場合は移動装置である）とサーバ３０２との間に確立され、情報に対する「リアルタイム」又は少なくとも「最新」のゲートウェイを提供する。
【００５８】
移動装置（サービスプロバイダを介する）とサーバ３０２等の別の装置との間のネットワーク接続は、例えばインターネット（ワールドワイドウェブ等）を使用して既知の方法で確立される。これは、例えばＴＣＰ／ＩＰレイヤプロトコルを使用することを含むことができる。移動装置は、ＣＤＭＡ、ＧＳＭ、ＷＡＮ等の１つ又は複数の通信規格を利用できる。
【００５９】
従って、例えば移動電話又はナビゲーション装置２００内の移動電話技術を介したデータ接続を介して達成されるインターネット接続が利用されてもよい。この接続に対して、サーバ３０２とナビゲーション装置２００との間のインターネット接続が確立される。これは、例えば移動電話又は他の移動装置及びＧＰＲＳ（汎用パケット無線サービス）接続（ＧＰＲＳ接続はテレコムオペレータにより提供された移動装置に対する高速データ接続であり、ＧＰＲＳはインターネットに接続する方法である）を介して行われる。
【００６０】
更にナビゲーション装置２００は、既知の方法で、例えば既存のＢｌｕｅｔｏｏｔｈ技術を介する移動装置とのデータ接続及び最終的にはインターネット及びサーバ３０２とのデータ接続を完成できる。ここで、データプロトコルは、例えばＧＳＲＭ、ＧＳＭ規格に対するデータプロトコル規格等の１つ又は複数の規格を利用できる。
【００６１】
ナビゲーション装置２００は、ナビゲーション装置２００自体に自身の移動電話技術を含んでもよい（例えばアンテナを含むか又はオプションとしてナビゲーション装置２００の内蔵アンテナを使用する）。ナビゲーション装置２００内の移動電話技術は、上記で指定したような内蔵構成要素を含むことができ且つ／又は挿入可能なカード（例えば、加入者識別モジュール、すなわちＳＩＭカード）を含むことができ、例えば必要な移動電話技術及び／又はアンテナにより完成される。従って、ナビゲーション装置２００内の移動電話技術は、あらゆる移動装置と同様の方法で例えばインターネットを介してナビゲーション装置２００とサーバ３０２との間のネットワーク接続を同様に確立できる。
【００６２】
ＧＲＰＳ電話設定に対して、Ｂｌｕｅｔｏｏｔｈ対応ナビゲーション装置は、移動電話の機種、製造業者等のあらゆる範囲で正確に動作するために使用されてもよく、機種／製造業者別の設定は、例えばナビゲーション装置２００に格納されてもよい。この情報に対して格納されたデータは更新可能である。
【００６３】
図３において、ナビゲーション装置２００は、多くの種々の構成のうちのいずれかにより実現される汎用通信チャネル３１８を介してサーバ３０２と通信しているものとして示される。サーバ３０２及びナビゲーション装置２００は、通信チャネル３１８を介する接続がサーバ３０２とナビゲーション装置２００との間に確立された時に通信できる（尚、そのような接続は移動装置を介するデータ接続、インターネットを介するパーソナルコンピュータを介した直接接続等であってもよい）。
【００６４】
サーバ３０２は、図示されない他の構成要素に加えて、メモリ３０６に動作可能に接続され且つ有線又は無線接続３１４を介して大容量データ記憶装置３１２に動作可能に接続されるプロセッサ３０４を含む。プロセッサ３０４は、送信機３０８及び受信機３１０に動作可能に更に接続され、通信チャネル３１８を介してナビゲーション装置２００に対して情報を送受信する。送受信される信号は、データ、通信及び／又は他の伝播信号を含んでもよい。送信機３０８及び受信機３１０は、ナビゲーションシステム２００の通信設計において使用される通信技術及び通信要件に従って選択又は設計されてもよい。尚、送信機３０８及び受信機３１０の機能は信号送受信機に組み合わされてもよい。
【００６５】
サーバ３０２は、大容量記憶装置３１２に更に接続される（又は大容量記憶装置３１２を含む）。尚、大容量記憶装置３１２は、通信リンク３１４を介してサーバ３０２に結合されてもよい。大容量記憶装置３１２は、ナビゲーションデータ及び地図情報のストアを含み、サーバ３０２とは別の装置であってもよく又はサーバ３０２に内蔵されてもよい。
【００６６】
ナビゲーション装置２００は、通信チャネル３１８を介してサーバ３０２と通信するように構成され、図２に関して上述したようなプロセッサ、メモリ等、並びに通信チャネル３１８を介して信号及び／又はデータを送受信するための送信機３２０及び受信機３２２を含む。尚、これらの装置は、サーバ３０２以外の装置と通信するために更に使用される。また、送信機３２０及び受信機３２２は、ナビゲーション装置２００の通信設計において使用される通信技術及び通信要件に従って選択又は設計され、送信機３２０及び受信機３２２の機能は単一の送受信機に組み合わされてもよい。
【００６７】
サーバのメモリ３０６に格納されたソフトウェアは、プロセッサ３０４に対して命令を提供し、サーバ３０２がナビゲーション装置２００にサービスを提供することを可能にする。サーバ３０２により提供される１つのサービスは、ナビゲーション装置２００からの要求を処理することと、大容量データ記憶装置３１２からナビゲーション装置２００にナビゲーションデータを送信することとを含む。サーバ３０２により提供される別のサービスは、所望のアプリケーションのために種々のアルゴリズムを使用してナビゲーションデータを処理することと、それらの計算の結果をナビゲーション装置２００に送出することとを含む。
【００６８】
一般に通信チャネル３１８は、ナビゲーション装置２００及びサーバ３０２を接続する伝播媒体又はパスを表す。サーバ３０２及びナビゲーション装置２００の双方は、通信チャネルを介してデータを送信する送信機と、通信チャネルを介して送信されたデータを受信する受信機とを含む。
【００６９】
通信チャネル３１８は、特定の通信技術に限定されない。また、通信チャネル３１８は単一の通信技術に限定されない。すなわち、チャネル３１８は、種々の技術を使用するいくつかの通信リンクを含んでもよい。例えば通信チャネル３１８は、電気通信、光通信及び／又は電磁通信等のためにパスを提供するように構成される。従って、通信チャネル３１８は、電気回路、ワイヤ及び同軸ケーブル等の電気導体、光ファイバケーブル、変換器、無線周波数（ＲＦ）波、大気、空所等のうち１つ又はそれらの組み合わせを含むが、それらに限定されない。更に通信チャネル３１８は、例えばルータ、中継器、バッファ、送信機及び受信機等の中間装置を含むことができる。
【００７０】
例示的な一構成において、通信チャネル３１８は電話及びコンピュータネットワークを含む。更に通信チャネル３１８は、無線周波数通信、マイクロ波周波数通信、赤外線通信等の無線通信に対応できてもよい。また、通信チャネル３１８は衛星通信に対応できる。
【００７１】
通信チャネル３１８を介して送信された通信信号は、所定の通信技術に対して要求又は要望される可能性があるような信号を含むが、それに限定されない。例えば信号は、時分割多元接続（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）、符号分割多元接続（ＣＤＭＡ）、汎ヨーロッパデジタル移動通信システム（ＧＳＭ）等のセルラ通信技術において使用されるように構成されてもよい。デジタル信号及びアナログ信号の双方とも、通信チャネル３１８を介して送信可能である。これらの信号は、通信技術に対して所望されるような変調、暗号化及び／又は圧縮された信号であってもよい。
【００７２】
サーバ３０２は、無線チャネルを介してナビゲーション装置２００によりアクセス可能なリモートサーバを含む。サーバ３０２は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、仮想プライベートネットワーク（ＶＰＮ）等に配置されたネットワークサーバを含んでもよい。
【００７３】
サーバ３０２は、デスクトップコンピュータ又はラップトップコンピュータ等のパーソナルコンピュータを含んでもよく、通信チャネル３１８は、パーソナルコンピュータとナビゲーション装置２００との間に接続されたケーブルであってもよい。あるいは、パーソナルコンピュータは、ナビゲーション装置２００とサーバ３０２との間に接続され、サーバ３０２とナビゲーション装置２００との間にインターネット接続を確立してもよい。あるいは、移動電話又は他のハンドヘルド装置は、インターネットを介してナビゲーション装置２００をサーバ３０２に接続するためにインターネットへの無線接続を確立してもよい。
【００７４】
ナビゲーション装置２００は、情報のダウンロードを介してサーバ３０２から情報を提供される。情報のダウンロードは、定期的に自動更新されるか又はユーザがナビゲーション装置２００をサーバ３０２に接続した時に更新されてもよく、且つ／あるいは例えば無線移動接続装置及びＴＣＰ／ＩＰ接続を介してサーバ３０２とナビゲーション装置２００との間でより継続的に又はより頻繁に接続された時により動的であってもよい。多くの動的計算に対して、サーバ３０２のプロセッサ３０４は大量の処理要求を処理するために使用されてもよいが、ナビゲーション装置２００のプロセッサ２１０も、多くの場合にサーバ３０２への接続とは無関係に大量の処理及び計算を処理できる。
【００７５】
図２において上記で示したように、ナビゲーション装置２００は、プロセッサ２１０、入力装置２２０及び表示画面２４０を含む。入力装置２２０及び表示画面２４０は、例えばタッチパネル画面を介する情報の入力（直接入力、メニュー選択等を介する）及び情報の表示の双方を可能にするために一体型入力表示装置に一体化される。そのような画面は、当業者には周知であるようにタッチ入力ＬＣＤ画面であってもよい。更にナビゲーション装置２００は、例えばオーディオ入出力装置等のあらゆる追加の入力装置２２０及び／又はあらゆる追加の出力装置２４１を含むことができる。
【００７６】
図４Ａ及び図４Ｂは、ナビゲーション装置２００を示す透視図である。図４Ａに示すように、ナビゲーション装置２００は、一体型入力表示装置２９０（例えば、タッチパネル画面）及び図２の他の構成要素（内蔵ＧＰＳ受信機２５０、マイクロプロセッサ２１０、電源、メモリシステム２３０等を含むがこれらに限定されない）を含むユニットであってもよい。
【００７７】
ナビゲーション装置２００は、吸着カップ２９４を使用して車両のダッシュボード／窓等に固定されてもよいアーム２９２に位置してもよい。このアーム２９２は、ナビゲーション装置２００がドッキングされるドッキングステーションの一例である。
【００７８】
図４Ｂに示すように、ナビゲーション装置２００は、例えばナビゲーション装置２９２をアーム２９２に嵌合接続することにより、ドッキングステーションのアーム２９２にドッキング又は接続される。ナビゲーション装置２００は、図４Ｂの矢印で示すようにアーム２９２上で回転可能であってもよい。ナビゲーション装置２００とドッキングステーションとの接続を解除するために、例えばナビゲーション装置２００上のボタンが押下されてもよい。ナビゲーション装置をドッキングステーションに結合し且つドッキングステーションから分離する他の同様の適切な構成は、当業者には周知である。
【００７９】
望ましくない経路の判定
図５は、本発明の一実施形態に係るナビゲーション装置５００を示す。ナビゲーション装置５００は、地図データ５４０及び回避データ５５０を含むデータを格納する記憶部を有する。いくつかの実施形態において、地図データ５４０及び回避データ５５０は組み合わされる。ナビゲーション装置は、記憶部５１０にアクセスできる（情報通信している）処理部５２０を更に含む。処理部５２０は出力部５３０と通信し、出力部５３０は処理部から通信された結果に基づいて出力を行う。ナビゲーション装置５００は、ＰＮＤに提供又は実現されるか、あるいはサーバに提供される。ナビゲーション装置がＰＮＤに提供される場合、処理部５００はプロセッサ２１０により具体化される。ＧＰＳ部３１５は位置決め装置として動作し、自身の位置及び方向を含む場所情報を判定する。処理部５００は、ＧＰＳ部３１５から場所情報を受信し、地図データ５３０及び場所情報に基づいて望ましくない場所をユーザに通知するのが適切であるかを判定する（ここで、ユーザは、位置決め装置を使用して移動しており且つ同一の場所情報を有する仮定される）。判定は、記憶部５３０に格納された好みの情報に基づいてもよい。ユーザが通知されるべきであると判定される場合、プロセッサ５２０は、出力部５３０によりユーザに通知する。出力部は、出力装置２６０又は表示装置２４０であってもよい。更に又はあるいは、出力装置はＩ／Ｏポート２７０であってもよい。
【００８０】
ナビゲーション装置５００がサーバに含まれる場合、記憶部は大容量データ記憶装置３１２により実現されてもよく、処理部はプロセッサ３０４により実現されてもよく、出力部は送信機３０８により実現されてもよい。プロセッサは、通信チャネル３１８及び受信機３１０を介してＰＮＤから場所情報を受信し、地図データ５４０、回避データ５５０及び場所情報に基づいて、望ましくない場所をユーザに通知するのが適切であるかを判定する。判定は、記憶部５３０に格納されるか又は通信チャネル３１８及び受信機３１０を介して提供される好みの情報に基づいてもよい。ユーザが通知されるべきであると判定される場合、プロセッサ５２０は、出力部５３０により送信機３０８を介して情報を送信して、ＰＮＤによりユーザに通知する。通常、ＰＮＤはユーザに視覚的及び／又は聴覚的に通知する。ＰＮＤからの出力は警告の形式であってもよい。
【００８１】
地図データは複数の決定地点を含む。決定地点は、ユーザが決定地点からの１つ以上の経路（前方経路）を提示されるいずれかの地点であり、そのうちの１つの経路が行程を継続するために選択される必要がある。通常の走行条件下において、多くの場合、ユーザはＵターン又は三点方向転換等の操作（ここで、操作は通常の交通の流れから離れる移動を示す）を行うことにより経路を変更できる。プロセッサが利用可能な前方経路を判定した場合、そのような操作の結果は、特に地図データにおいて許可されない限り、プロセッサにより考慮されない。すなわち、「前方経路」と考えられない。
【００８２】
図６は、本実施形態のナビゲーション装置５００の処理部５２０により実行される方法を示す。位置決め装置の位置及び動きの方向に関する情報は、処理部５２０に提供され、処理部５２０は、地図データ５４０に基づいて位置決め装置が決定地点に接近しているかを判定する（ステップ６０５）。位置決め装置が決定地点に向かって移動しており且つ決定地点から事前設定距離内にいる場合、決定地点に接近していると考えられてもよい。あるいは、位置決め装置がその速度を判定し且つそれを処理部に提供する場合、現在の速度が維持されると仮定すると位置決め装置が事前設定時間内に決定地点に到着する場合に決定地点に接近していると考えられてもよい。これらの基準又は他の基準の組み合わせが使用されてもよい。判定は、道路の種類に依存してもよく、例えばルックアップテーブルは、現在の道路が一車線、二車線、高速道路等であるかに依存して事前設定された距離及び／又は時間を判定するために使用される。本明細書において、処理部により接近していると判定される決定地点を接近決定地点と呼ぶ。
【００８３】
処理部が決定地点に接近していると判定した場合、決定地点からの前方経路の１つが選択される（ステップ６１０）。処理部は、その経路に沿って決定地点の前に望ましくない場所に到達するかを判定する（ステップ６１５）。そのような経路は、本実施形態に関連して「望ましくない経路」と呼ばれる。ステップ６１５の判定は、全ての前方経路が考慮されるまで、接近決定地点からの各前方経路に対して繰り返される。本実施形態によると、これは、接近決定地点からの全ての前方経路が考慮されたか（すなわち、ステップ６１５に従う判定を行われたか）を判定することにより達成される。いずれかの前方経路がまだ考慮されていない場合、ステップ６２５は、考慮されていない経路から１つの経路を選択してステップ６１５に戻り、その経路に対して判定が実行される。ステップ６２０において全ての前方経路が考慮されたと判定された場合、処理部は、接近決定地点からの前方経路のいずれかが望ましくない前方経路であると判定されたかを判定する。いずれの前方経路も望ましくないと判定されなかった場合、ステップ６３５において次の決定地点が考慮される。
【００８４】
一実施形態において、ステップ６３５に到達すると、処理部は、接近決定地点を通過するまで待機し、ステップ６０５に戻り、別の決定地点に接近しているかが判定される。ステップ６３５において接近決定地点を通過するまで待機することにより、同一の決定地点に対して処理（ステップ６０５〜６４０）を繰り返すことが回避され、処理部に対する不必要な負荷を軽減する。この場合、移動方向に沿う最も近い決定地点のみが「接近」していると考えられる。
【００８５】
一実施形態において、ステップ６３５に到達すると、接近決定地点を通過していない場合、ステップ６０５（又はステップ６１０）に戻り、処理（ステップ６１０〜６３０）が同一の決定地点に対して繰り返される。これは、回避データが時間に依存し且つステップ６１５の判定結果が変化する可能性がある場合に利点を有する。処理部は、ステップ６１０〜６３０を継続的に繰り返してもよく、あるいはある時間だけ遅れてステップ６１０〜６３０を繰り返してもよい。処理部は、回避データが時間に依存するか（特にステップ６１５に関連する望ましくないいずれかの場所に関する回避データ）及び次の決定地点に到達するまでの予想時間等の要因に基づいてステップ６１０〜６３０を繰り返すか否かを判定してもよい。本実施形態において、ナビゲーション装置は、時間情報（現在の時間等）を処理部に提供するために計時部を備えてもよい。あるいは、時間情報は外部ソースにより提供されてもよい。
【００８６】
前方経路のいずれか（１つ以上）が望ましくない（すなわち、決定地点に到達する前に望ましくない場所に到達する）と判定される場合、ステップ６４０は、適切な出力を出力部に提供する。ナビゲーション装置がＰＮＤである場合、出力部は、次の決定地点において前方経路の１つ以上が望ましくないエリアに至ることをユーザに注意するために可聴警告及び／又は可視警告を提供してもよい。警告は、望ましくない前方経路及び望ましくない各経路と関連付けられた望ましくない場所の種類を指定してもよい。ナビゲーション装置がサーバである場合、出力部は、位置決め装置と関連付けられた装置に結果を提供する。結果は、ユーザが注意できるように、接近決定地点からの１つ以上の前方経路が望ましくないことを単に示してもよい。この場合、１つの望ましくない経路が見つけられた後に望ましくない経路のチェックを継続する必要はないため、ステップ６２０は、「望ましくない経路が見つけられたか又は全ての前方経路が考慮されたか？」で置き換えられてもよい。しかし、情報をユーザが使用できるように、結果は望ましくない経路及び望ましくない場所の種類を示すのが好ましい。
【００８７】
上記実施形態によると、ユーザは、次の決定地点において望ましくない場所に至ることが不可避である（操作がない）望ましくない経路をとる危険性があることを認識させられる。これは、接近決定地点が望ましくない場所に直接至ることがない経路を少なくとも１つ提供するため、ユーザに時宜を得た警告を提供する。決定地点に接近した時にユーザに通知することにより、警告はユーザの心に鮮明に残っており、ユーザは警告を決定点に容易に関連付けられる。これに対して、経路が最初に計画された時に与えられた警告は忘れられる可能性があるか、あるいはユーザは警告が関連しているエリアに到達したことに気付かない可能性がある。更に本実施形態は、計画した経路が望ましくない経路に従わない場合でもユーザに注意するために警告を提供してもよい。これにより、ユーザは、決定地点からの前方経路を選択する時に十分に注意することができる。
【００８８】
本実施形態は、ユーザがフリードライビングしている時に特に利点を有する。フリードライビングしている時、経路は計画されておらず、ナビゲーション装置はユーザが走行する経路に関する情報を有さない。従って、行程の前に（例えば、経路計画段階において）望ましくない場所に関する警告を提供できない。
【００８９】
図７は、ナビゲーション決定地点である２つの分岐点７１５及び７２０を含む主要道路７１０を含む道路網の一例を示す。ユーザが主要道路７１０に沿って図面の上部に向かって地点７２５から移動している時、分岐点７１５に最初に到着し、ここで主要道路を進むか又は道路７３０に右折できる。道路７３０は分岐点７５０に至る。分岐点７１５から主要道路に沿って進むと、分岐点７２０に至り、ここで主要道路に沿って進むか又は分岐点７５５に至る道路７３５に左折できる。分岐点７２０から主要道路に沿って進むと、有料の橋等の望ましくない場所７４０に至る。主要道路は、図面の上端を越えて継続する。地図データは図７に示す道路に関する情報を含み、回避データは望ましくない場所に関する情報を含む。
【００９０】
ユーザが地点７２５において分岐点７１５（決定地点）に向かって移動している時、処理部は、ユーザが分岐点７１５に到達する前に分岐点７１５が接近決定地点の基準を満たすと判定する（ステップ６０５）。処理部は、決定地点からの前方経路を選択し（ステップ６１０）、例えば道路７１０に沿って進む。ステップ６１５において、この経路に沿って望ましくない場所に到達する前に決定地点７２０に到達するため、道路７１０を進むことは望ましくない前方経路ではないと判定される。道路７３０に沿う経路が考慮されていないため、ステップ６２０は「Ｎｏ」を返し、ステップ６２５において道路７３０に沿う経路が選択される（まだ選択されていない前方経路のみ）。望ましくない場所の前に分岐７５０に到着するため、ステップ６１５は、この経路が望ましくない経路ではないと判定する。分岐点７１５からの全ての前方経路が考慮されたため、ステップ６２０は「Ｙｅｓ」を返し、ステップ６３０に進む。いずれの前方経路も望ましくないと判定されなかったため、ステップ６３５に進む。分岐点７１５を通過して主要道路７１０を進んだ後、処理部はステップ６０５において決定地点に接近しているかのチェックを開始する。この例において、ユーザが地点７４５に到達した時、分岐点７２０が接近決定地点の基準を満たす。その後、ステップ６１０に進み、主要道路７１０に沿う分岐点７２０からの前方経路が選択される。分岐点７２０と望ましくない場所７４０との間に決定地点がないため、ステップ６１５において、道路７１０に沿う分岐点７２０からの経路は望ましくない経路であると判定される。道路７３５に沿う経路が考慮されていないため、ステップ６２０及び６２５を介してステップ６１５に戻る。道路７３５が望ましくない場所に到達せずに分岐点７５５に至るため、ステップ６１５において、この経路は望ましくないと判定されない。全ての経路が考慮されたため、ステップ６３０に進む。ステップ６３０において少なくとも１つの経路が望ましくないと判定されたため、ステップ６４０においてユーザは警告される。その後、ステップ６３５に戻り、分岐点７２０を通過するまで待機する。
【００９１】
図６の実施形態の変形例において、ステップ６１０は、決定地点を通過して現在の経路に残っているユーザに対応する前方経路を選択する。例えば決定地点が小さい道路への分岐点に対応する主要道路において、現在の経路は主要道路に残ることに対応する。現在の道路がＴ字路等の決定地点を越えて継続しない場合、全ての前方経路が考慮されてもよく、あるいは前方経路が全く考慮されなくてもよい。この変形例において、現在の経路のみがステップ６１５で考慮され、ステップ６３０がステップ６１５に後続する（ステップ６２０をスキップする）。この変形例は、決定地点を越えて現在の経路に沿って進むことにより望ましくない場所に到達する場合にのみユーザに警告を与える。これは、ユーザが現在の経路を外れる可能性が少なく、副経路に関する警告が迷惑となる可能性ある場合により適切だろう。同様の変形例は、ユーザが事前計画された経路（ナビゲーション装置により判定されるか又はユーザによりナビゲーション装置に提供される）を走行している時に適切だろう。この場合、他の経路はユーザにより不適切であると考えられるため、事前計画された経路に対応する前方経路が望ましくない場所に至るかを判定することのみが望ましい。事前計画された経路に従う場合、最終目的地が望ましくない場所内にある場合又は望ましくない場所を通過せずに最終目的地に到達できない場合、望ましくない場所に接近しているという警告は抑制されてもよい。
【００９２】
回避データが時間に依存するいくつかの実施形態において、前方経路に沿って望ましくない場所に到達するかを判定する時、処理部は、その経路に従う場合に望ましくない場所に到達する時間を推定してもよく、前方経路が望ましくないかを判定する時にその望ましくない場所に対して推定時間に対応する回避情報を使用してもよい。例えば現在の時間が午前１時４５分であり、有料道路まで約３０分の移動であり、有料道路が例えば午前２時から終夜無料である場合、処理部は午前２時１５分（予想到着時間）に対応する有料道路の回避データを使用し、有料道路は望ましくない場所と考えられない。
【００９３】
望ましくない経路の別の判定
図８は、一実施形態に係る処理部５２０により実行されてもよい別の方法を示す。ステップ８０５、８１０、８２０、８２５、８３０、８３５及び８４０は、図６に関連して説明したステップ６０５、６１０、６２０、６２５、６３０、６３５及び６４０にそれぞれ対応する。ステップ８１５はステップ６１５とは異なる。ステップ８１５において、処理部は、選択された前方経路に沿って全ての後続する利用可能な経路が望ましくない場所を含むか（望ましくない場所に到達するか）を判定する。図８の実施形態によると、望ましくない経路は、望ましくない場所に直接至るか又は望ましくない経路にのみ至る経路と規定される。
【００９４】
いくつかの例において、道路の分岐点から離れる全ての経路は望ましくない場所（又は複数の望ましくない場所）に至る可能性がある。そのような場合、道路の分岐点は望ましくない場所を回避する機会を提供せず、最後の機会は前の分岐点（決定地点）に対応する。本実施形態によると、望ましくない場所に関する警告又は情報は、望ましくない場所を回避する最後の機会に到達する前に提供されてもよい。これにより、警告又は情報が時宜を得て提供されることが保証される。
【００９５】
図９は、ナビゲーション決定地点である３つの分岐点９１３、９１５及び９２０を含む主要道路９１０を有する道路網を示す。ユーザが主要道路９１０に沿って図面の上部に向かって地点９２５から移動している時、分岐点９１３に最初に到着し、ここで主要道路を進むか又は道路９７５に左折できる。道路９７５は分岐点９８０に至り、この例の目的のため、分岐点９５０からの経路のいずれも望ましくない場所に至らない。主要道路９１０に沿って進むと、到着する次の分岐点は分岐点９１５であり、ここで主要道路を進むか又は道路９３０に右折できる。道路９３０は分岐点９５０に至り、分岐点９５０からの経路は望ましくない場所に至らない。分岐点９１５から主要道路に沿って進むと、分岐点９２０に至り、ここで主要道路に沿って進むか又は分岐点９５５に至る道路９３５に左折できる。分岐点９５５において道路９６０に右折する（図面の上部に向かう）と、例えば渋滞課金ゾーンであってもよい望ましくない場所９４０ａに直接至る。分岐点９５５において道路９６５に沿って図面の左に向かって進むと、有料の橋又は狭い道路等であってもよい望ましくない場所９４０ｂに至る。分岐点９２０から図面の上部に向かって主要道路に沿って進んでも、望ましくない場所９４０ａに至る。
【００９６】
道路９１０にいるユーザの観点から、図面の上部に向かって移動すると、道路９１０ｄの部分は、望ましくない場所９４０ａに直接至るため望ましくない経路である。同様に、分岐点９５５から離れる方向に移動する道路９６０及び９６５に沿う経路は、望ましくない場所に直接至るため望ましくない経路である。分岐点９５５からの前方経路が望ましくない経路（道路９６０及び９６５に沿う）であるため、分岐点９２０から分岐点９５５までの道路９３５に沿って移動する経路も望ましくない経路である。分岐点９２０からの全ての経路（道路９１０ｄ及び９３５に沿う）が望ましくない経路であるため、分岐点９１５から道路９１０ｃに沿う経路は望ましくない経路である。道路９３０に沿う分岐点９１５からの経路は望ましくない場所に至らず、分岐点９５０からの後続する経路も望ましくない経路ではないため、道路９３０に沿う経路も望ましくない経路ではない。分岐点９３０からの全ての経路が望ましくない経路ではないため、道路９１０ｂに沿う分岐点９１３からの経路は望ましくない経路ではない。同様の理由により、分岐点９１３から道路９７５に沿う経路及び分岐点９１３への９１０ａに沿う経路は望ましくない経路ではないことが示される。
【００９７】
ユーザが地点９２５において分岐点９１３（決定地点）に向かって移動している場合、処理部は、ユーザが分岐点９１３に到達する前に、分岐点９１３が接近決定地点の基準を満たすと判定する（ステップ８０５）。処理部は、例えば道路９７５である決定地点からの前方経路を選択する（ステップ８１０）。ステップ８１５において、道路９７５は望ましくない経路ではないと判定される（上述した理由のため）。その後、ステップ８２０及び８２５を介してステップ８１５に戻り、道路９１０ｂに沿って進むことは望ましくない経路であるかを考慮する。上述したように、道路９１０ｂは望ましくない経路ではない。
【００９８】
道路９１０ｂに沿う経路が望ましくないかを判定する際、ステップ８１５は、選択した経路から継続する全ての可能な経路を考慮してもよい（例えば、道路９３０及び９１０ｃが望ましくないかを考慮することにより考慮してもよく、これは分岐点９５０からの道路並びに道路９１０ｄ、９３５、９６０及び９６５の各々を考慮する必要がある）。あるいは、ステップ８１５は、分岐点９１５からのいずれかの経路が望ましくない経路ではないと分かった時に停止してもよい。例えば道路９３０に沿う経路がまず考慮され且つ望ましくない経路ではないと分かった場合、ステップ８１５は、道路９１０ｃに沿う経路を考慮せずに停止してもよい（道路９１０ｃ、９１０ｄ、９３５、９６０、９６５を考慮する必要性を回避する）。このように、ステップ８１５は、望ましくない場所に到着しない選択した経路（ステップ８１０又は８２５で選択された）から継続する経路が少なくとも１つあるかを判定し、これにより、選択した経路（ステップ８１０又は８２５で選択された）に従う場合に接近決定地点が望ましくない場所を回避する最後の機会ではないことを保証する。
【００９９】
９１０ｂに沿う経路が望ましくない経路ではないと決定されると、ステップ８２０に進み、全ての前方経路が考慮されたと判定され、ステップ８３０に進む。道路９７５及び９１０ｂに沿ういずれの経路も望ましくない経路ではないため、ステップ８３５に継続する。
【０１００】
ユーザが決定地点（分岐点９１３）を通過した場合、ステップ８０５に戻り、ユーザが分岐点９１５に到達する前に、処理部は、分岐点９１５が接近決定地点であると判定する。ステップ８１０は、例えば道路９３０に沿う分岐点９１５からの前方経路を選択する。道路９３０は望ましくない経路ではないため、ステップ８１５の結果は否定である。ステップ８２０及び８２５を介して、９１０ｃに沿う経路を選択経路としてステップ８１５に戻る。この経路は、ステップ８１５において望ましくないと判定され、ステップ８２０を介してステップ８３０に進む。前方経路（道路９１０ｃに沿う）のうちの少なくとも１つが望ましくないと判定されたため、出力部は適切な出力を実行し（ステップ８４０）、ステップ８３５に進む。
【０１０１】
この方法によると、更に決定地点が存在するがそれら全てが望ましくない場所に至ることが不可避であると判定されたため、地点９４５において、ユーザは分岐点９１５が望ましくない場所を回避する最後の機会であることを警告される。一方、分岐点９１３は望ましくない場所を回避する最後の機会ではない（分岐点９１５が次の機会を提供する）ため、この警告は、ユーザが地点９２５にいる時には発行されない。
【０１０２】
ユーザは、望ましくない場所及び／又は望ましくない経路の存在に関して他の時間に警告（又は忠告）されてもよいことが理解されるべきである。しかし、本発明の構成により、ユーザは正確な「最後の機会」の警告又は指示を提供されるため、ユーザは、接近している分岐点の潜在的な意味を完全に理解できる。
【０１０３】
場合によっては、後続する経路が望ましくない場所を「逃れた」と仮定される（すなわち、経路が望ましくない場所を含まないと判定される）近道を規定するのが実用的である。近道の先の経路の分岐は考慮される必要がなく、道路網が大きい場合にステップ８１５の判定を容易にする。例えばステップ８１５において、位置決めデバイスからの経路の長さが３ｋｍ等の特定の距離を越える場合、後続する経路は望ましくない場所に到達しないと考えられる可能性がある。あるいは、近道は、位置決め装置を中心に所定の半径（例えば、５ｋｍ）の円により規定され、経路に沿って円の半径内で望ましくない場所に到達しない場合に経路は望ましくない場所に到達しないと考えられる。近道は、後続する経路が通過する決定地点数に関して規定できる。例えば後続する経路が望ましくない場所に到達せずに１０個を越える決定地点を通過する場合。例えばそれらの組み合わせは、望ましくない場所に到達しないと判定される前に後続する経路が最短距離及び最小決定地点数を有することを要求することにより使用される。これにより、単に道路の長さが後続する経路の長さの近道の制限を越えるために望ましくない場所に至らないと判定される分岐点のない長い道路が回避される。
【０１０４】
図６に関連して上述したように、１つの前方経路のみが考慮され、ステップ９２０及び９２５が省略されてもよい可能性がある。
【０１０５】
場合によっては、決定地点は、ユーザがその決定地点に入った経路に沿って逆方向に出ることを可能にしてもよい。ロータリー１００５の例を図１０に示す。図１０において、経路１０１０は、図面の下部において道路１０１５に入り、図面の上部に向かって移動し、ロータリーをほぼ完全に回って、同一の道路１０１５により出る。上記実施形態のいくつかの変形例によると、ステップ８１５で選択された前方経路は、ユーザの方向を単に逆にするような経路を除外する。これらの変形例によると、ユーザが経路を後戻りする必要がある尤度を低減できる。例えば図１０において、道路１０２０、２０２５及び１０３０が全て望ましくない場合、ユーザは道路１０１５で方向転換する前に（図１０の下部からはみ出している決定地点において）望ましくないエリアを回避する最後の機会を警告される。ユーザは、警告を受信する前にロータリー１００５に到達し且つ道路１０１５に沿って戻る必要があるのではなく、前の決定地点に到達した時に別の経路をとることができる。これにより無駄な時間及び無駄な燃料が低減される。類推から、処理部は、ユーザが同一経路を後戻り又は折り返すようにするあらゆる経路、あるいは閉ループを完成させるあらゆる経路をステップ８１５における考慮対象から省いてもよい。行き止まりに至るだけの経路も、ユーザがその場所への事前設定された経路に従っていない限り除外されてもよい。
【０１０６】
いくつかの実施形態において、ユーザが計画された経路に従っている場合、ステップ８１５は、設定された限界だけ計画された経路から外れるあらゆる経路を除外してもよい。この場合、「最後の機会」の警告は、計画された経路から大きく外れずに望ましくない場所を回避する最後の機会に対応する。例えばステップ８１５において、移動距離又は予想移動時間の過度な増加を招く（最終的な目的地まで拡張した時に）いずれの前方経路も考慮されない。過度な増加は、事前に設定された値であってもよく、あるいは計画された行程距離／予想移動時間の比率であってもよい。同様に、フリードライビングの際、経路は、ユーザが移動している現在の方向又は行程の開始から現在地への平均方向とほぼ同一方向でない場合にステップ８１５から除外される。これらの実施形態において、決定地点から離れる経路だけでなく事前設定された基準内で事前計画された経路又は現在の移動方向に適合する決定地点から離れる経路も必要とするために「前方経路」が利用される。
【０１０７】
望ましくない経路及び望ましくない経路ではない経路に関して実施形態を説明した。経路は、例えば数値で示される望ましくないレベルを有することができる。この値は、特定の経路を使用するコストを反映できる。場合によっては、望ましくない最大レベルを示す値等が割り当てられてもよく、経路は使用されない。例えば位置決め装置が車高の高い車両に配置される場合、空き高が不十分な道路は使用されるべきではなく、有料道路はオプションとして使用されてもよい。望ましくないレベルを割り当てることにより、ユーザに提供される情報は、状況により適切になるように調整される。
【０１０８】
遅延の助言
従来のナビゲーション装置は、最適な経路を選択するためにコスト関数を最小にする（又はコスト関数を最小にしようとする）。コスト関数は、例えば経路の長さ、経路を走行するのにかかる時間、経路に関連する消費燃料の見込み又はそれらの組み合わせを反映してもよい。経路計画の際、ユーザの要望に適した「最善」の経路を見つけるために既知のアルゴリズムが使用される。コスト関数を評価するために、各道路の長さ及び／又は道路における交通の速度（例えば、一般的な速度の推定を可能にするリアルタイム情報又は制限速度からの）等の関連情報が格納される必要がある。コスト関数を評価するための情報は、例えば実際の交通の流れの情報の場合のように時間に依存してもよい。しかし、多くの場合、時間に依存する情報は、現在の時間にのみ関連し、経路に関連するコストの可能性のある変化の信頼できる予測を可能にしない。本明細書において、コストは、経路又は経路の一部分に対するコスト関数の値を示し、金銭的なコストと関連付けられる必要はない。
【０１０９】
利用される経路及び経路を使用する時間に依存してユーザが課金される道路課税方式の提案により、行程の価格決めが複雑になる可能性があり、ユーザが時間及び金銭的な要望のバランスのとれた最善の経路を判定するのは困難になるだろう。従って、この点に関してユーザを支援できる装置を提供するのが望ましい。更に、特定の時間に特定の経路と関連付けられた税のコストは、明確であると予想され、信頼できる予測ができる。これは、現在は最大限に利用されていない予測可能な時間依存データを利用する機会を提供する。これらの課題の少なくとも一部は、以下の実施形態により対処される。
【０１１０】
本実施形態のナビゲーション装置を図１３に示す。図１３の要素は、図５の実施形態の対応する番号をつけられた要素と類似する。図１３において、時間依存コストデータ１５５０は、記憶部５１０に提供される。コストデータは、回避データ５５０に加えて又はその代わりに提供されてもよい。回避データ５１０と同様に、時間依存コストデータ１５５０は、地図データ５４０と組み合わされてもよい。
【０１１１】
図１１は、ナビゲーション装置のプロセッサにより実行される方法を示す。図１１のステップ１１０５において、経路が判定される。これは、従来のナビゲーション装置と同様に行程を開始する前の経路の計算である。ここで、開始位置及び終了位置が提供され、経路は、開始地点と終了地点との間の行程のコストを最小限にする。経路のコストは、記憶部に提供されたコストデータを使用して評価される所定のコスト関数に基づく。ステップ１１０５は、行程中に経路を計算（又は再計算）することにより具体化される。終了位置が与えられない場合（例えば、フリードライビングの場合）、ステップ１０５の計算経路は、現在位置と次の決定地点との間の経路又は可能な前方経路（例えば、上述した近道の線に沿って近道まで及ぶ経路）の選択の１つであってもよい。
【０１１２】
ステップ１１１０において、経路はコスト関数により評価されるようなコストに対する時間に依存する関係を含むかが判定される。例えば経路中の特定の道路が混雑時間にのみ課税対象となる場合、これらの道路を使用する金銭的なコストは経時変化する（閑散時対混雑時）。時間に依存する関係がない場合、方法はステップ１１３０で終了する。
【０１１３】
経路が時間依存部分を含む場合、ステップ１１０５は、待機することにより経路のコスト（コスト関数により評価されるような）が低減されるか否かを判定する。待機することにより経路のコストが低減されると判定された場合、方法はステップ１１３０で終了する。
【０１１４】
待機することにより経路のコストが低減されると判定された場合、ステップ１１２０に進み、コストを低減するのに必要な待機時間が閾値と比較される。要求される待機時間が閾値を超える場合、待機時間は長すぎると判定され、方法はステップ１１３０で終了する。閾値は固定時間（例えば、５分）であってもよく、あるいは予想行程時間に依存してもよい（予想行程時間の５％等）。待機時間が長すぎると判定されない場合、出力部は、ステップ１１２５において適切な出力を提供するように命令される。ナビゲーション装置がＰＮＤである場合、これは、ユーザに対する可聴プロンプト又は可視プロンプトの形式をとることができ、待機することに利点があることを通知し、好ましくは待機するのに適切な場所への方向を提供する。一方、ナビゲーション装置がサーバである場合、出力は、位置決め装置（又は情報を要求した他の装置）に送信された情報の形式であり、送信された情報により、位置決め装置（又は他の装置）はユーザに入力指示できる。
【０１１５】
別の構成において、ステップ１１１５において待機時間が過度であるかが考慮され、ステップ１１２０が省略される。ステップ１１１５は、コスト関数に時間成分を含むことにより待機時間を考慮するように構成される。これにより、待機時間がコスト関数の利得に対して相殺される。例えば課税に基づくが行程時間に関連する項を含むコスト関数の場合、待機することの金銭的な利点は、待機するのに費やされる追加の時間に対して自動的に重み付けされる。コスト関数の一例は以下のとおりである。
【０１１６】
Ｆ＝Σ（ｍ＋αＴ）
式中、Ｆはコスト関数であり、経路中の道路（経路の区分又は部分）に対して加算が行われ、ｍは特定の時間において道路を使用する金銭的なコストであり、Ｔはその道路（又は道路の一部分）の予想移動時間である。Ｔは、例えば混雑時間におけるより遅い交通を考慮するために時間に依存してもよい。Ｔは、待機時間を含むこともできる。αは、金銭的なコストと時間との間の重み付けを調整するためのパラメータである。
【０１１７】
ステップ１１１５の判定は、種々の方法で判定される。一例において、プロセッサは、経路の一部分と関連付けられたコストが経路のその部分への予想到着時間より遅い時間において低減されるかをコストデータに基づいて判定してもよい。プロセッサは、経路のその部分における予想到着時間前後の時間の範囲のみ考慮してもよい。時間の範囲は、設定された期間（例えば、予想到着時間の１５分以内）であってもよく、あるいは予想移動時間に基づいてもよい。時間の範囲に対するステップ１１１５の制限は、ステップ１１２０の判定の代わりに又はそれに加えて行われてもよい。
【０１１８】
好適な一実施形態において、ステップ１１１５は、別の経路として待機時間を考慮することにより実行される。これにより、待機することによりコストが低減されるかを判定するために同一又は同様の処理が使用可能となる。特にコスト関数が時間成分を有する場合、待機する利点及び欠点は経路の初期計算と同一の相対的な重要性を使用して比較される。オプションとして、コスト関数は、待機することが苛立ちとなると考えられる可能性があることを反映するように修正される。
【０１１９】
図１２ａは、待機することを表すために別の経路の追加を示す道路網の一例を示す。図１２ａにおいて、ユーザは地点１２０５から目的地１２２５に向かって移動している。経路は、関連付けられた金銭的なコスト（例えば、道路の税金）を有する点線で示す道路１２２０を使用する。しかし、道路１２２０への予想到着時間のすぐ後で、この道路を使用する金銭的なコストが低減される。プロセッサは、経路を計算（又は再計算）する時に、道路１２１５及び１２２０に沿う単一の経路を図１２ｂに概略的に示す２つの概念的な経路で置換する。最初、双方の経路が道路１２１５に従っているが、道路１２１５の終端に到達する前に概念的な経路が分岐する。図１２ｂの直線に進む経路は、待機することなく道路１２１５及び１２２０に沿って目的１２２５まで進むことを表す。他方の経路は、道路１２１５及び１２２０に沿って進む前に駐車場１２１０に停止し且つ待機することを表す。この場合、金銭的なコストの時間依存の特性のため、この経路に沿って道路１２２０を使用する金銭的なコストは異なる。
【０１２０】
待機することに利点があるかを判定するためにコスト関数が使用されるいくつかの実施形態において、ステップ１１２０は省略されてもよい。いくつかの実施形態において、ステップ１１１０は省略されてもよく、経路は計算に含まれる概念的な待機経路を含むスクラッチから再計算される。これにより、例えばユーザが遅延し、経路に沿う地点への予想到着時間が変更される場合、異なる経路が好ましくなる可能性がある。経路はコスト関数を使用して評価され、好ましい経路は通常通り選択される。時間に依存するコストを有する経路の部分が多く存在する場合、好適な経路は、標準的な経路計画アルゴリズムを使用して種々の地点で待機する累積効果を考慮に入れて計算される。
【０１２１】
いくつかの実施形態において、プロセッサは、待機することが可能である可能性が高く且つそれに従って出力が調整されるかを判定する。例えば、高速道路で待機することが要求される場合、高速道路では停止できないため、ユーザに待機するように提案することは抑制される。
【０１２２】
追加の経路が考慮される図１１の処理は、ステップ１１０５で異なる経路を選択することにより繰り返されてもよい。例えば、ユーザがフリードライビングをしており、目的地（終了地点）が規定されていない場合、近道内の全ての経路は考慮されてもよく、ユーザは待機することによりそれら経路のいずれかにおいてコストが低減されるかを通知されてもよい。
【０１２３】
別の実施形態において、上述した処理に類似する処理は、経路の一部分と関連付けられたコストが、ユーザがその部分に到着する予想時間のすぐ後に増加するかを判定するために使用されてもよい。「すぐ後」とは、例えば所定の期間として規定されてもよく、あるいは出発地又は現在地と経路の部分との間の予想移動時間の比率に基づいて規定されてもよい。コストが増加すると判定される場合、ユーザは忠告されてもよい。これにより、休憩をとったり計画されていない回り道をしたりする等の行程に対する遅延は、結果として経路を完了するのに追加の金銭的なコスト又は時間遅延（あるいは、コスト関数により反映される他の悪影響）を招く可能性があることにユーザは気付く。
【０１２４】
本明細書において、場所、道路又は経路の一部分への「到着」の参照は、経路又は経路の一部分と関連付けられたコストを判定するのに使用される適切な時間で置き換え可能である。予想到着時間の代わりに、経路又は一部分を出発する予想時間が使用可能であり、あるいは到着時間及び出発時間の双方が使用可能である。これは、その経路に対する１つ以上の時間依存コスト及びそれらの評価方法に依存する。
【０１２５】
いくつかの実施形態において、コスト関数は、待機することの金銭的なコストを考慮するように構成される。例えばユーザは、車両のマイル毎のコスト、運転者の分毎のコスト及び後で出発するための待機時間の分毎のコストを提供してもよく、ナビゲーション装置は、例えば最も安価な経路及び出発時間を判定することにより移動に対するコストを最適化できる。
【０１２６】
本発明の教示は、ユーザが望ましくない場所をより容易に回避でき且つ／又は時間に依存する要因を考慮に入れて経路計画ができるナビゲーション装置を提供することが上述から明らかとなるだろう。
【０１２７】
本発明の種々の態様及び実施形態について説明したが、本発明の範囲は本明細書で説明される特定の構成に限定されず、添付の特許請求の範囲の範囲内に入る全ての構成、並びにそれらに対する変形及び変更を範囲に含むことが理解されるだろう。
【０１２８】
例えば上述した詳細な説明で説明した実施形態はＧＰＳを参照するが、ナビゲーション装置はＧＰＳの代わりに（又は実際にはそれに加えて）あらゆる種類の位置検出技術を利用してもよい。例えばナビゲーション装置は、欧州のガリレオシステム等の他のグローバルナビゲーションサテライトシステムを使用してもよい。同様に、ナビゲーション装置は、衛星を使用するものに限定されず、地上ビーコン又は装置が地理的な場所を判定することを可能にする他のあらゆる種類のシステムを使用して容易に機能できる。
【０１２９】
好適な実施形態は、ソフトウェアを使用して特定の機能性を実現するが、その機能性は同様にハードウェア単独で（例えば、１つ以上のＡＳＩＣ（特定用途向け集積回路）を使用して）実現可能であるか、あるいは実際にはハードウェア及びソフトウェアの組み合わせにより実現可能であることがよく理解されるだろう。従って、本発明の範囲は、ソフトウェアで実現されるものに限定されるものとして解釈されるべきではない。
【０１３０】
最後に、添付の特許請求の範囲は本明細書で説明した特徴の特定の組み合わせを説明するが、本発明の範囲は、以下に請求される特定の組み合わせに限定されず、特定の組み合わせが添付の特許請求の範囲で特に列挙されたか否かに関係なく本明細書で開示される実施形態又は特徴のあらゆる組み合わせを含む。
【図１】
0005856157.tif 000002
【図２】
0005856157.tif 000003
【図３】
0005856157.tif 000004
【図４ａ】
0005856157.tif 000005
【図４ｂ】
0005856157.tif 000006
【図５】
0005856157.tif 000007
【図６】
0005856157.tif 000008
【図７】
0005856157.tif 000009
【図８】
0005856157.tif 000010
【図９】
0005856157.tif 000011
【図１０】
0005856157.tif 000012
【図１１】
0005856157.tif 000013
【図１２ａ】
0005856157.tif 000014
【図１２ｂ】
0005856157.tif 000015
【図１３】
0005856157.tif 000016