(57)【要約】  本発明の実施形態は、予め定められた種類のロケーションが潜在的に発見されうる位置に各々対応する複数の潜在位置を示す情報を含む地図情報を記録する記録部（２３０、３０６）と、予め定められた種類のロケーションの発見可能性に基づく予め定められた効率尺度を用いて、少なくとも１つの前記潜在位置を訪れる探索経路を決定する探索経路モジュール（４９０）と、を有する経路計画（２００、３０２）に関する。
2013533964.tif 000002
【特許請求の範囲】
【請求項１】
複数の潜在位置を示す情報を含む地図情報を記録する記録部であって、
各潜在位置が予め定められた種類のロケーションが潜在的に発見されうる位置に対応する記録部（２３０、３０６）と、
前記予め定められた種類のロケーションの発見可能性に基づく予め定められた効率尺度を用いて、少なくとも１つの前記潜在位置を訪れる探索経路を決定する探索経路モジュール（４９０）と、を有する
ことを特徴とする経路計画装置（２００、３０２）。
【請求項２】
前記地図情報は、各潜在位置について、各潜在位置における前記予め定められた種類のロケーションの発見可能性に対応する確率情報を含むことを特徴とする請求項１に記載の装置（２００、３０２）。
【請求項３】
前記確率情報は、前記各潜在位置における予め定められた種類のロケーションの発見可能性に、時間的変化を示す時間的成分を含むことを特徴とする請求項２に記載の装置（２００、３０２）。
【請求項４】
前記潜在位置は、駐車スペースに対応し、
前記予め定められた種類のロケーションは、空車の駐車スペースに対応することを特徴とする請求項１乃至３のいずれか１項に記載の装置（２００、３０２）。
【請求項５】
前記探索経路は複数の前記潜在位置を訪れるように決定されることを特徴とする請求項１乃至４のいずれか１項に記載の装置（２００、３０２）。
【請求項６】
ユーザからの命令を受け付ける入力部（２２０）をさらに有し、
前記探索経路モジュール（４９０）は、前記入力部（２２０）を介してユーザが予め定められた種類の位置への探索経路が決定されるべきであることを指示する場合に、前記装置（２００、３０２）の現在位置を出発位置として設定し、
前記探索経路モジュール（４９０）は、前記出発位置から出発するように前記探索経路を決定する
ことを特徴とする請求項１乃至５のいずれか１項に記載の装置（２００、３０２）。
【請求項７】
前記予め定められた効率尺度は、前記出発位置及び前記潜在位置に関する予め定められた距離関数に少なくとも一部基づくことを特徴とする請求項６に記載の装置（２００、３０２）。
【請求項８】
前記探索経路モジュール（４９０）は、到達地位置（Ｘ）を示す到着地指示部を含み、  前記予め定められた効率尺度は、前記到着地位置（Ｘ）及び前記潜在位置に関する予め定められた距離関数に基づく
ことを特徴とする請求項１乃至７のいずれか１項に記載の装置（２００、３０２）。
【請求項９】
前記探索経路モジュール（４９０）は、訪問した潜在位置において予め定められた種類のロケーションが発見されたか否かを判断する結果判断モジュールをさらに有することを特徴とする請求項１乃至８のいずれか１項に記載の装置（２００、３０２）。
【請求項１０】
少なくとも前記装置（２００、３０２）の現在位置を含む現在位置情報を判断する位置情報判断部（３２４）をさらに有し、
前記結果判断モジュールは、
前記位置情報に基づいて、潜在位置に到達しているかを判断し、
前記装置（２００、３０２）が提供される乗物が駐車しているかを判断し、
前記潜在位置に到達しており、かつ前記乗物が駐車していると判断した場合に、前記潜在位置において前記予め定められた種類のロケーションが発見されたことを示し、
前記潜在位置に到達しており、かつ前記乗物が駐車していないと判断した場合に、前記予め定められた種類のロケーションが見つからなかったことを示す
ように構成される
ことを特徴とする請求項４を直接あるいは間接的に引用する請求項９に記載の装置（２００、３０２）。
【請求項１１】
前記装置（２００、３０２）は、特定の潜在位置において前記予め定められた種類のロケーションが発見されたことを示した後、前記乗物が前記特定の潜在位置を出発したか否かを判断し、前記乗物が前記特定の潜在位置を出発したと判断した場合に、
前記特定の潜在位置から出発していることをサーバ（３０２）に通信する、
前記特定の潜在位置から出発していることを他の経路計画装置（２００）に通信する、及び
前記確率情報に代えて一時的に使用される一時的な確率情報を設定または更新する
の少なくともいずれかを実行する
ことを特徴とする請求項１０に記載の装置（２００、３０２）。
【請求項１２】
前記結果判断モジュールの判断をサーバ（３０２）に通信する、
前記結果判断モジュールの判断を他の経路計画装置（２００）に通信する、
前記結果判断モジュールの判断に基づいて前記確率情報を更新する、及び
前記結果判断モジュールの判断に基づき、前記確率情報に代えて一時的に使用される一時的な確率情報を設定または更新する
の少なくともいずれかを実行する更新部をさらに有する
ことを特徴とする請求項２を直接あるいは間接的に引用する請求項９乃至１１のいずれか１項に記載の装置（２００、３０２）。
【請求項１３】
請求項１乃至５のいずれか１項に記載の前記装置と、
ネットワーク（３１８）を介して、遠隔装置（２００）からの探索経路要求を受信する受信部（３１０）と、
前記ネットワーク（３１８）を介して、前記探索経路モジュール（４９０）により決定された前記探索経路を送信する送信部（３０６）と、を有する
ことを特徴とするサーバ（３０２）。
【請求項１４】
更新部をさらに有し、
前記受信部（３１０）は、前記遠隔装置（２００）からの結果情報を受信するように構成され、
前記更新部は、前記結果情報に基づいて地図情報を調整するように構成される
ことを特徴とする請求項１３に記載のサーバ。
【請求項１５】
コンピュータにおいて実行される探索経路の提供方法であって、
予め定められた種類のロケーションへの探索経路を提供する要求を受信し、
地図情報から、前記予め定められた種類のロケーションが潜在的に発見されうる位置に各々対応する複数の潜在位置を示し、
前記予め定められた種類のロケーションの発見可能性に基づく予め定められた効率尺度を用いて、少なくとも１つの前記潜在位置を訪れる経路を決定し、
前記決定した経路を前記探索経路として出力する
ことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路計画用のナビゲーション装置及び方法に関する。本発明の例示する実施形態は、ポータブルナビゲーション装置（いわゆるＰＮＤ）に関し、特に全地球測位システム（ＧＰＳ）信号の受信及び処理機能、並びにそれと共に使用する地図データを備えるＰＮＤに関する。更に一般的には、他の実施形態は、地図データを使用する経路計画及び好ましくはナビゲーションの機能性を提供するためにナビゲーションソフトウェアを実行するように構成されるあらゆる種類の処理装置に関する。
【背景技術】
【０００２】
ＧＰＳ（全地球測位システム）信号の受信及び処理機能を備えるポータブルナビゲーション装置（ＰＮＤ）はよく知られており、車両搭載型又は他の車両ナビゲーションシステムとして広く採用されている。
【０００３】
一般的に、現在のＰＮＤは、プロセッサ、メモリ（揮発性及び不揮発性のうちの少なくとも一方、並びに一般的にはその双方）及び前記メモリ内に格納された地図データを含む。プロセッサ及びメモリは、ソフトウェアオペレーティングシステムが設置されうる実行環境を提供するように協働し、また、ＰＮＤの機能の制御を可能にし、且つ種々の他の機能を提供するために１以上の追加のソフトウェアプログラムが提供されることは一般的なことである。
【０００４】
通常、これらの装置は、ユーザが装置とインタラクションし、且つ装置を制御できるようにする１以上の入力インタフェース、及びユーザに情報を中継する１以上の出力インタフェースとを更に備える。出力インタフェースの例には、表示装置及び可聴出力用スピーカが含まれる。入力インタフェースの例には、オン／オフ動作又は装置の他の特徴を制御する１以上の物理ボタン（ボタンは必ずしも装置自体にある必要はなく、装置が車両に内蔵されている場合はステアリングホイール上にあってもよい）及びユーザ音声を検出するマイクが含まれる。特定の好適な１つの構成において、出力インタフェースディスプレイは、ユーザが触れることで装置を動作させる際に使用する入力インタフェースを更に提供するためにタッチセンシティブディスプレイとして（又はタッチセンシティブオーバレイ等を使用して）構成されてもよい。
【０００５】
多くの場合、この種の装置は、電力及びオプションとしてデータ信号を装置に対して送受信する際に使用する１以上の物理コネクタインタフェースを含み、オプションとして、セルラ電気通信、並びに例えばＷｉ−Ｆｉ及びＷｉ−Ｍａｘ ＧＳＭ等の他の信号及びデータネットワークを介する通信を可能にする１以上の無線送信機／受信機を含む。
【０００６】
この種のＰＮＤ装置は、場所データを含む衛星放送信号を受信し、且つその後装置の現在地を判定するために処理する際に使用するＧＰＳアンテナを更に含む。
【０００７】
ＰＮＤ装置は、現在の角度及び直線加速度、また、ＧＰＳ信号から導出された位置情報とともに速さ、並びに装置及び当該装置が搭載される車両の相対的な変位を判定するために処理される信号を生成する電子ジャイロスコープ及び加速度計を更に含んでもよい。通常、そのような機能は車両搭載型のナビゲーションシステムに提供されるのが最も一般的であるが、ＰＮＤ装置に備えることが得策である場合にはＰＮＤ装置に備えてもよい。
【０００８】
そのようなＰＮＤの有用性は、主に、第１の場所（一般に、出発地又は現在地）と第２の場所（一般に、目的地）との間の経路を判定する機能にある。装置のユーザは、多種多様な種々の方法、例えば郵便番号、道路名及び番地、以前に格納した「既知」の目的地（有名な場所、公共の場所（運動場又は水泳プール等）又は他の地点情報等）、並びにお気に入りの目的地又は最近訪れた目的地のいずれかにより、これらの場所を入力する。
【０００９】
一般にＰＮＤは、地図データから出発地の住所の場所と目的地の住所の場所との間の「最善」又は「最適」な経路を算出することがソフトウェアにより可能になる。「最善」又は「最適」な経路は、所定の基準に基づいて判定され、必ずしも最速又は最短の経路である必要はない。運転者を案内する経路の選択は非常に複雑となり得、選択された経路は、既存の予測された動的に且つ／又は無線で受信された交通及び道路情報、道路速度に関する履歴情報、並びに道路選択を判定する要因に対する運転者自身の好みを考慮してもよい（例えば運転者は、経路が高速道路又は有料道路を含むべきでないことを指定してもよい）。
【００１０】
更に装置は、道路及び交通状況を継続的に監視し、状況変化によりとられる残りの行路に対して経路を変更することを提案又は選択してもよい。種々の技術（例えば、移動電話データ交換、固定カメラ、ＧＰＳ車両追跡）に基づくリアルタイム交通監視システムは、交通遅滞を識別し、その情報を通知システムに供給するために使用されている。
【００１１】
この種のＰＮＤは、一般に、車両のダッシュボード又はフロントガラスに搭載されてもよいが、車両のラジオの内蔵コンピュータの一部又は実際には車両自体の制御システムの一部として形成されてもよい。ナビゲーション装置は、ＰＤＡ（ポータブルデジタルアシスタント）、メディアプレーヤ又は移動電話等のハンドヘルドシステムの一部であってもよい。これらの場合、ハンドヘルドシステムの標準的な機能は、経路計算及び計算された経路に沿ったナビゲーションの双方を実行するためにソフトウェアを装置にインストールすることにより拡張される。
【００１２】
経路計画及びナビゲーション機能は、適切なソフトウェアを実行するデスクトップ又は移動計算リソースにより提供されてもよい。例えば、ロイヤル・オートモービルクラブ（ＲＡＣ：Royal Automobile Club）は、http://www.rac.co.ukにおいてオンライン経路計画及びナビゲーション機能を提供する。この機能により、ユーザは出発地及び目的地を入力でき、その後ユーザのＰＣが接続されるサーバは、経路（経路の様子はユーザにより指定されてもよい）を計算し、地図を生成し、選択した出発地から選択した目的地までユーザを案内するための包括的なナビゲーション命令の集合を生成する。また当該機能は、計算経路の擬似３次元レンダリングを提供し、ユーザが経路に沿って移動することをシミュレートし、且つそれにより計算された経路のプレビューをユーザに提供する経路プレビュー機能を提供する。
【００１３】
ＰＮＤにおいて、経路が計算されると、ユーザはオプションとして提案された経路のリストから所望の計算された経路を選択するためにナビゲーション装置とインタラクションする。オプションとして、ユーザは、例えば特定の経路、道路、場所又は基準が特定の行程に対して回避されること又は必須であることを指定することにより経路選択処理を仲介又は誘導してもよい。ＰＮＤの経路計算の側面は１つの主要機能を形成し、そのような経路に沿ったナビゲーションは別の主要機能である。
【００１４】
計算された経路に沿ったナビゲーションがなされている間、このようなＰＮＤは、経路の終点、すなわち所望の目的地まで選択した経路に沿ってユーザを案内するための視覚的命令及び可聴命令の少なくともいずれかを提供するのが一般的である。また、ＰＮＤは、ナビゲーション中に画面上に地図情報を表示するのが一般的である。このような情報は、表示された地図情報が装置の現在地及び従って装置が車両搭載型のナビゲーションに使用されている場合はユーザの現在地又はユーザの車両の現在地を表すように画面上で定期的に更新される。
【００１５】
一般に画面上に表示されたアイコンは、装置の現在地を示し、装置の現在地近傍の現在の道路及び周囲の道路の地図情報と共に中央に置かれ、他の地図の特徴も表示される。更にナビゲーション情報は、オプションとして表示された地図情報の上側、下側又は片側のステータスバーに表示されてもよく、ナビゲーション情報の例には、ユーザが走行する必要のある現在の道路から次の進路変更までの距離が含まれ、場合によってはその進路変更の特性は、例えば左折又は右折である特定の種類の進路変更を示す更なるアイコンで表される。またナビゲーション機能は、経路に沿ってユーザを案内する際に使用される可聴命令の内容、継続時間及びタイミングを判定する。理解されるように、「１００ｍ先を左折」等の単純な命令は、かなりの処理及び分析を必要とする。上述したように、装置とのユーザインタラクションは、タッチスクリーンによって行われてもよく、更に又はあるいはステアリングコラムリモコン、音声起動又は他の適切なあらゆる方法によって行われてもよい。
【００１６】
装置により提供された更なる重要な機能は、ユーザがナビゲーション中に事前に計算された経路から外れた（偶然又は意図的に）場合、別の経路の方が適切であることをリアルタイム交通状況が指示し、且つ装置がそのような状況を自動的に認識することを適切に可能にされる場合、又はユーザが何らかの理由で能動的に装置に経路を再計算させる場合の自動経路再計算である。
【００１７】
またユーザが規定した基準で経路を計算できることは既知である。例えばユーザは、装置により景色のよい経路が計算されることを好んでもよく、あるいは交通渋滞が起こる可能性が高いか、起こることが予想されるか又は現在起こっているあらゆる道路を回避することを要求してもよい。次に、装置のソフトウェアは種々の経路を計算し、例えば景色が美しい所としてタグ付けされた地点情報（ＰＯＩとして既知である）を経路に沿って最も多く含む経路をより有利に重み付けするか、あるいは特定の道路上の交通状況を示す格納情報を使用することにより、起こる可能性のある渋滞又はそのために起こる遅滞のレベルに関して計算経路を順序付けする。更に他のＰＯＩに基づく経路計算及びナビゲーション基準、並びに交通情報に基づく経路計算及びナビゲーション基準が可能である。
【００１８】
経路計算及びナビゲーション機能はＰＮＤの全体的な有用性に対して必須であるが、装置を純粋に情報表示に使用できる。すなわち、装置の現在地に関連する地図情報のみが表示され、経路が全く計算されておらず、装置が現在ナビゲーションを全く実行していない「フリードライビング」用に使用できる。多くの場合、このような動作モードは、移動するのに使用するように要求される経路をユーザが既に認識しており、ナビゲーション支援を必要としない場合に適用可能である。
【００１９】
上述のこの種の装置、例えばＴｏｍＴｏｍ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂ．Ｖ．が製造及び供給する７２０Ｔモデルは、ユーザがある位置から別の位置まで運転できるようにする信頼できる手段を提供する。
【００２０】
ナビゲーション装置のための経路を計算するために、ナビゲーション装置により一意的に示されうる特定のロケーションを有する住所または地図参照のような目的地が提供される必要がある。これは、第一に特定の種類またはクラスの目的地への到達に関心があり、目的地の特定の位置をあまり気にしない、あるいはまったく気にしないユーザに対する、限定的な支援である。また、ある目的地は、ユーザが到達した際に十分でないことを示すが、理論的には、ユーザのニーズを満たしている。ナビゲーション装置は、経路計算時にこのような状況を考慮するキャパシティを有していない。本発明の実施形態は、該欠点に対処する目的を有する。
【発明の概要】
【課題を解決するための手段】
【００２１】
この目的のために、本発明の現在の好適な実施形態は、複数の潜在位置を示す情報を含む地図情報を記録する記録部であって、各潜在位置が予め定められた種類のロケーションが潜在的に発見されうる位置に対応する記録部と、予め定められた種類のロケーションの発見可能性に基づく予め定められた効率尺度を用いて、少なくとも１つの潜在位置を訪れる探索経路を決定する探索経路モジュールと、を有する経路計画装置を提供する。
【００２２】
これにより、効率的な方式で所望の種類のロケーションが発見されうる探索ルートの決定が可能となる。
【００２３】
一実施形態において地図情報は、各潜在位置について、各潜在位置における予め定められた種類のロケーションの発見可能性に対応する確率情報を含む。
【００２４】
これにより、ユーザ要求に実質的に合致する潜在位置の確率を考慮することにより実現される効率性が可能にされる。
【００２５】
確率情報は、各潜在位置における予め定められた種類のロケーションの発見可能性に、時間的変化を示す時間的成分を含んでもよい。
【００２６】
これにより、対象種類のロケーションを発見する実際（実世界）の確率の一時的な変化を反映する確率情報が可能にされる。
【００２７】
潜在位置は、駐車スペースに対応し、予め定められた種類のロケーションは、空車の駐車スペースに対応していてもよい。
【００２８】
従って、空車の駐車スペースについての効率的な探索を実行する指標がユーザに提供される。
【００２９】
探索経路は複数の潜在位置を訪れるように決定されてもよい。
【００３０】
所望の種類のロケーションの発見可能性を上昇させるために、複数の潜在位置を訪れる探索ルートが好ましい。
【００３１】
経路計画装置は、ユーザからの命令を受け付ける入力部であって、探索経路モジュールが、入力部を介してユーザが予め定められた種類の位置への探索経路が決定されるべきであることを指示する場合に、装置の現在位置を出発位置として設定し、探索経路モジュールが、出発位置から出発するように探索経路を決定する入力部を有していてもよい。
【００３２】
予め定められた効率尺度は、出発位置及び潜在位置に関する予め定められた距離関数に少なくとも一部基づいてもよい。
【００３３】
探索経路モジュールは、到達地位置を示す到着地指示部を含んでいてもよく、予め定められた効率尺度は、到着地位置及び潜在位置に関する予め定められた距離関数に基づいてもよい。
【００３４】
探索経路モジュールは、訪問した潜在位置において予め定められた種類のロケーションが発見されたか否かを判断する結果判断モジュールをさらに有していてもよい。
【００３５】
これにより、例えば探索経路の次の決定を改善するために用いられる探索結果の情報を可能にされる。
【００３６】
経路計画装置は、少なくとも装置の現在位置を含む現在位置情報を判断する位置情報判断部を有していてもよく、結果判断モジュールは、位置情報に基づいて、潜在位置に到達しているかを判断し、装置が提供される乗物が駐車しているかを判断し、潜在位置に到達しており、かつ乗物が駐車していると判断した場合に、潜在位置において予め定められた種類のロケーションが発見されたことを示し、潜在位置に到達しており、かつ乗物が駐車していないと判断した場合に、予め定められた種類のロケーションが見つからなかったことを示すように構成される。
【００３７】
これにより、訪れた潜在位置についての結果の自動判断が可能にされる。
【００３８】
経路計画装置は、特定の潜在位置において予め定められた種類のロケーションが発見されたことを示した後、乗物が特定の潜在位置を出発したか否かを判断し、乗物が特定の潜在位置を出発したと判断した場合に、特定の潜在位置から出発していることをサーバに通信する、特定の潜在位置から出発していることを他の経路計画装置に通信する、及び確率情報に代えて一時的に使用される一時的な確率情報を設定または更新する、の少なくともいずれかを実行するように構成されていてもよい。
【００３９】
これにより、例えば他の経路計画装置の探索経路を改良するために用いられる、特定の潜在位置から乗物が離れていることを示す情報が可能にされる。
【００４０】
経路計画装置は、結果判断モジュールの判断をサーバに通信する、結果判断モジュールの判断を他の経路計画装置に通信する、結果判断モジュールの判断に基づいて確率情報を更新する、及び結果判断モジュールの判断に基づき、確率情報に代えて一時的に使用される一時的な確率情報を設定または更新する、の少なくともいずれかを実行する更新部をさらに有していてもよい。
【００４１】
これにより、短期間の信頼性を有し、（例えば特定のロケーションにおいて駐車スペースが現在ないような）変化に従う情報の使用が可能にされる。
【００４２】
１つの実施形態は、経路計画装置と、ネットワークを介して、遠隔装置からの探索経路要求を受信する受信部と、ネットワークを介して該装置により決定された探索経路を送信する送信部と、を有するサーバを含む。
【００４３】
該実施形態は、移動装置に対して探索経路を提供するためのサーバを提供する。
【００４４】
サーバは、受信部が遠隔装置からの結果情報を受信するように構成され、更新部が結果情報に基づいて地図情報を調整するように構成される更新部を有していてもよい。
【００４５】
これにより、移動装置からの結果情報に基づいて地図情報を改良するサーバが可能にされる。好ましくは、地図情報は確率情報を含み、該確率情報が結果情報に基づいて更新される。
【００４６】
本発明の１つの態様によれば、コンピュータに実装された方法が探索経路を提供し、方法は、予め定められた種類のロケーションへの探索経路を提供する要求を受信し、地図情報から、予め定められた種類のロケーションが潜在的に発見されうる位置に各々対応する複数の潜在位置を示し、予め定められた種類のロケーションの発見可能性に基づく予め定められた効率尺度を用いて、少なくとも１つの潜在位置を訪れる経路を決定し、決定した経路を探索経路として出力する。
【００４７】
該方法により、効率的な方式で所望の種類のロケーションを発見しうる探索経路がユーザに提供されることが可能になる。
【００４８】
本発明の別の実施形態は、実行環境で実行された時に、プロセッサに上述した実施形態のモジュールまたは部分として機能させる、または上述の実施形態の方法を実行させるように動作可能である１以上のソフトウェアモジュールを含むコンピュータソフトウェアに関する。
【００４９】
これらの実施形態の利点については以下に説明する。これらの実施形態の各々の更なる詳細及び特徴は、添付の従属請求項及び以下の詳細な説明の中で規定される。
【００５０】
本発明の教示の種々の態様及びそれらの教示を採用する構成について、添付の図面を参照して例として以下に説明する。
【図面の簡単な説明】
【００５１】
【図１】全地球測位システム（ＧＰＳ）を示す概略図
【図２】ナビゲーション装置を提供するように構成された電子構成要素を示す概略図
【図３】ナビゲーション装置が無線通信チャネルを介して情報を受信できる方法を示す概略図
【図４Ａ】、
【図４Ｂ】ナビゲーション装置を示した透視図
【図５】ナビゲーション装置により採用されるソフトウェアの概略図
【図６】本発明の実施形態を例示する道路ネットワークの概略図
【図７】本発明の実施形態における確率情報の調整方法を示すフローチャート
【図８】本発明の実施形態における一時的確率情報の調整方法を示すフローチャート
【図９Ａ】本発明の実施形態における、ナビゲーション装置から中央サーバへの結果情報の通信方法を示すフローチャート
【図９Ｂ】本発明の実施形態における、中央サーバにより実行される方法を示すフローチャート
【図９Ｃ】本発明の実施形態により実行される方法を示すフローチャート
【発明を実施するための形態】
【００５２】
次に、本発明の好適な実施形態について、特にＰＮＤを参照して説明する。しかし、本発明の教示はＰＮＤに限定されず、経路計画及びナビゲーション機能を提供するためにナビゲーションソフトウェアを実行するように構成されるいかなる種類の処理装置にも例外なく適用可能である。故に、本出願において、ナビゲーション装置は、ＰＮＤ、車両に内蔵されたナビゲーション装置、あるいは実際には経路計画及びナビゲーションソフトウェアを実行するコンピューティング資源（デスクトップ又はポータブルパーソナルコンピュータ（ＰＣ）、移動電話、あるいはポータブルデジタルアシスタント（ＰＤＡ））として実装されるか否かにかかわらず、いかなる種類の経路計画及びナビゲーション装置も（無制限に）含むことを意図する。
【００５３】
ここで、セクションまたはモジュールとの参照は特定の限定を目的とするのではなく、このようなモジュールやセクションに起因する機能性は複数の構成要素により提供されうる。同様に、個々の構成要素は複数のセクション及び／またはモジュールの機能性を提供または機能性に寄与しうる。様々なセクション及びモジュールは、ハードウェア、ソフトウェア、あるいは２つの組み合わせで実装されうる。
【００５４】
格納されているデータまたは情報との参照は、（光学ディスク及び磁気ディスク等の）大容量記憶装置または（ＲＡＭのような）能動メモリを含む。「〜に格納された」または「〜における」データまたは情報との参照は、「〜を入手可能な」の省略表現として用いられ、前後関係がそれ以外を要求しない限り、記録媒体の物理位置を暗示しない。
【００５５】
説明の明確化のため、発明のいくつかの実施形態は、対象ロケーション種類として駐車スペースの例を用いて説明される。発明がこれに限定されるものではないことは、同一の技術分野に属する投票者にとって明らかであろう。実施形態は、当業者による必要以上の実験なしに、他の対象ロケーション種類に発明が適切に適用されるように変更可能である。
【００５６】
以下の説明において、発明の様々な実施形態が開示される。これらの実施形態の特徴が必要以上の実験なしに様々な方法で組み合わせ可能であることは、当業者にとって明らかであろう。
【００５７】
上記を踏まえ、図１はナビゲーション装置により使用可能な全地球測位システム（ＧＰＳ）の一例を示す図である。そのようなシステムは周知であり、種々の目的に使用される。一般に、ＧＰＳは、連続的な位置、速度、時間及びいくつかの例においては方向情報を無数のユーザに対して判定できる衛星無線ナビゲーションシステムである。
【００５８】
以前はＮＡＶＳＴＡＲとして周知であったが、ＧＰＳは極めて正確な軌道で地球と共に動作する複数の衛星を使用する。これらの正確な軌道に基づいて、ＧＰＳ衛星は、それらの場所を任意の数の受信装置に中継できる。
【００５９】
ＧＰＳデータを受信する能力を特別に備える装置がＧＰＳ衛星信号に対する無線周波数の走査を開始する場合、ＧＰＳシステムは実現される。ＧＰＳ衛星から無線信号を受信すると、装置は、複数の異なる従来の方法のうちの１つを用いて、その衛星の正確な場所を判定する。殆どの例において、装置は、少なくとも３つの異なる衛星信号を取得するまで信号の走査を継続する（尚、位置は、通常は２つの信号のみでは判定されないが、他の三角測量技術を使用して２つの信号から判定することもできる）。幾何学的三角測量を実現する場合、受信機は、３つの既知の位置を利用して、衛星に対する自身の２次元位置を判定する。これは、周知の方法で行われる。更に、第４の衛星信号を取得することにより、受信装置は、同一の幾何学計算によって周知の方法でその３次元位置を計算できる。位置及び速度データは、無数のユーザにより連続的にリアルタイムで更新可能である。
【００６０】
図１に示すように、ＧＰＳシステム全体を参照番号１００で示す。複数の衛星１２０は、地球１２４の周囲の軌道上にある。各衛星１２０の軌道は、他の衛星１２０の軌道と必ずしも同期せず、実際には非同期であることが多い。ＧＰＳ受信機１４０は、種々の衛星１２０からスペクトル拡散ＧＰＳ衛星信号１６０を受信するように示される。
【００６１】
各衛星１２０から連続的に送信されるスペクトル拡散信号１６０は、極めて正確な原子時計を用いて達成される非常に正確な周波数標準を利用する。各衛星１２０は、そのデータ信号送信１６０の一部として、その特定の衛星１２０を示すデータストリームを送信する。一般に、ＧＰＳ受信機１４０が三角測量によりその２次元位置を計算するために、ＧＰＳ受信機１４０は少なくとも３つの衛星１２０からスペクトル拡散ＧＰＳ衛星信号１６０を取得することが当業者には理解される。更なる信号を取得すると、全部で４つの衛星１２０から信号１６０を取得する結果となり、これによってＧＰＳ受信機１４０は、その３次元位置を周知の方法で計算できる。
【００６２】
図２は、本発明の好適な実施形態に係るナビゲーション装置２００の電子構成要素の実例となる図である。尚、ナビゲーション装置２００のブロック図は、ナビゲーション装置の全ての構成要素を含むものではなく、構成要素の多くの例を表すにすぎない。
【００６３】
ナビゲーション装置２００は、筐体（不図示）内に位置付けられる。筐体は、入力装置２２０及び表示画面２４０に接続されるプロセッサ２１０を含む。入力装置２２０は、キーボード装置、音声入力装置、タッチパネル、及び情報を入力するために利用される他の任意の周知の入力装置のうちの少なくとも１つを含むことができ、表示画面２４０は、例えばＬＣＤディスプレイ等の任意の種類の表示画面を含むことができる。特定の好適な構成において、入力装置２２０及び表示画面２４０は、タッチパッド又はタッチスクリーン入力を含む一体型入力表示装置に一体化され、その場合、ユーザは、複数の表示選択肢のうちの１つを選択するか又は複数の仮想ボタンのうちの１つを操作するために、表示画面２４０の一部分に接触するだけでよい。
【００６４】
ナビゲーション装置は、出力装置２６０、例えば可聴出力装置（例えばスピーカ）を含みうる。出力装置２６０がナビゲーション装置２００のユーザに対して可聴情報を生成できるため、同様に、入力装置２４０は入力音声コマンドを受信するマイク及びソフトウェアを更に含むことができると理解されるべきである。
【００６５】
ナビゲーション装置２００において、プロセッサ２１０は、接続２２５を介して入力装置２４０に動作可能に接続され且つ入力装置２２０から入力情報を受信するように設定される。また、プロセッサ２１０は、情報を出力するために、表示画面２４０及び出力装置２６０のうちの少なくとも一方に出力接続２４５を介して動作可能に接続される。更に、プロセッサ２１０は、接続２３５を介してメモリ資源２３０に動作可能に接続され、接続２７５を介して入出力（Ｉ／Ｏ）ポート２７０との間で情報を送受信するように更に構成される。この場合、Ｉ／Ｏポート２７０は、ナビゲーション装置２００の外部のＩ／Ｏ装置２８０に接続可能である。メモリ資源２３０は、例えばランダムアクセスメモリ（ＲＡＭ）のような揮発性メモリや、フラッシュメモリのようなデジタルメモリ等の不揮発性メモリを含む。外部Ｉ／Ｏ装置２８０は、例えばイヤホン等の外部聴音装置を含んでもよいが、これに限定されない。更に、Ｉ／Ｏ装置２８０への接続は、例えばハンズフリー動作と音声起動動作との少なくとも一方のため、イヤホン又はヘッドフォンへの接続のため、並びに／あるいは例えば移動電話への接続のためのカーステレオユニット等の他の任意の外部装置への有線接続又は無線接続であってもよい。この場合、移動電話接続は、ナビゲーション装置２００とインターネット又は例えば他の任意のネットワークとの間のデータ接続を確立するためと、インターネット又は例えば他の任意のネットワークを介するサーバへの接続を確立するためとの少なくとも一方のために使用されてもよい。
【００６６】
図２は、接続２５５を介するプロセッサ２１０とアンテナ／受信機２５０との間の動作可能な接続を更に示す。この場合、アンテナ／受信機２５０は、例えばＧＰＳアンテナ／受信機であってもよい。参照番号２５０で示されるアンテナ及び受信機は、図示のために概略的に組み合わされるが、アンテナ及び受信機は、別個に位置する構成要素であってもよく、アンテナは、例えばＧＰＳパッチアンテナ又はヘリカルアンテナであってもよいことが理解されるだろう。
【００６７】
更に、図２に示す電子構成要素が従来の方法で電源（不図示）により電力を供給されることが当業者には理解されるだろう。当業者により理解されるように、図２に示す構成要素の異なる構成が本願の範囲内で考えられる。例えば、図２に示す構成要素は、有線接続と無線接続との少なくとも一方等を介して互いに通信状態にあってもよい。従って、本願のナビゲーション装置２００の範囲は、ポータブル又はハンドヘルドナビゲーション装置２００を含む。
【００６８】
更に、図２のポータブル又はハンドヘルドナビゲーション装置２００は、例えば自転車、オートバイ、自動車又は船舶等の乗物に周知の方法で接続されるか又は「ドッキング」される。その場合、そのようなナビゲーション装置２００は、ポータブル又はハンドヘルドナビゲーションとして使用するために、ドッキング場所から取り外し可能である。
【００６９】
図３を参照すると、ナビゲーション装置２００は、デジタル接続（例えば、周知のＢｌｕｅｔｏｏｔｈ技術を介するデジタル接続）を確立する移動装置（図示せず）（移動電話、ＰＤＡ、及び移動電話技術を用いる任意の装置のうちの少なくとも１つ等）を介して、サーバ３０２との「モバイル」あるいは電気通信ネットワーク接続を確立してもよい。そうして、そのネットワークサービスプロバイダを介して、移動装置は、サーバ３０２とのネットワーク接続を（例えば、インターネットを介して）確立できる。そのため、「モバイル」ネットワーク接続は、情報に対する「リアルタイム」又は少なくとも非常に「最新」のゲートウェイを提供するために、ナビゲーション装置２００（単体時、及び車載走行時の少なくとも一方において移動可能であり且つ多くの場合移動している）とサーバ３０２との間に確立される。
【００７０】
例えばインターネット（ワールドワイドウェブ等）を使用して、移動装置（サービスプロバイダを介する）とサーバ３０２等の別の装置との間にネットワーク接続を確立することは、周知の方法で行われうる。これは、例えばＴＣＰ／ＩＰ層プロトコルの使用を含む。移動装置は、ＣＤＭＡ、ＧＳＭ、ＷＡＮ等の任意の数の通信規格を利用できる。
【００７１】
そのため、例えば移動電話又はナビゲーション装置２００内の移動電話技術を介するデータ接続を介して達成されるインターネット接続が利用されてもよい。この接続の場合、サーバ３０２とナビゲーション装置２００との間のインターネット接続が確立される。これは、例えば、移動電話又は他の移動装置及びＧＰＲＳ（汎用パケット無線サービス）接続（ＧＰＲＳ接続は、通信会社により提供される移動装置用高速データ接続であり、ＧＰＲＳはインターネットへの接続方法である）を介して行われうる。
【００７２】
更に、ナビゲーション装置２００は、移動装置とのデータ接続を完成し、例えば既存のＢｌｕｅｔｏｏｔｈ技術を介して周知の方法でインターネット及びサーバ３０２とのデータ接続を最終的に完成する。この場合、例えばデータプロトコルは、ＧＳＭ規格に対するデータプロトコル規格であるＧＳＲＭ１等の任意の数の規格を利用できる。
【００７３】
ナビゲーション装置２００は、ナビゲーション装置２００自身の中に、自身の移動電話技術を含んでもよい（例えばアンテナを含む、あるいはオプションとしてナビゲーション装置２００の内部アンテナを用いる）。ナビゲーション装置２００内の移動電話技術は、上述のような内部構成要素を含むことができ、且つ／又は例えば必要な移動電話技術とアンテナとの少なくとも一方を備える挿入可能なカード（例えば加入者識別モジュールあるいはＳＩＭカード）を含むことができる。そのため、ナビゲーション装置２００内の移動電話技術は、任意の移動装置の方法と同様の方法で、例えばインターネットを介して、ナビゲーション装置２００とサーバ３０２との間にネットワーク接続を同様に確立できる。
【００７４】
ＧＲＰＳ電話設定の場合、移動電話の機種、製造業者等の多様な範囲に関して正しく動作するために、Ｂｌｕｅｔｏｏｔｈ対応のナビゲーション装置が使用されてもよく、機種／製造業者専用設定は、例えばナビゲーション装置２００に格納されてもよい。この情報のために格納されたデータは更新されうる。
【００７５】
図３において、ナビゲーション装置２００は、多くの異なる、いずれの装置により実装されうる汎用通信チャネル３１８を介して、サーバ３０２と通信するものとして示されている。通信チャネル３１８を介する接続がサーバ３０２とナビゲーション装置２００との間に確立される場合、本願のサーバ３０２及びナビゲーション装置２００は通信可能である（尚、そのような接続は、移動装置を介するデータ接続、インターネットを介するパーソナルコンピュータを介する直接接続等である）。
【００７６】
サーバ３０２は、図示しない他の構成要素に加えて、メモリ３０６に動作可能に接続され且つ有線又は無線接続３１４を介して大容量データ記憶装置３１２に動作可能に更に接続されるプロセッサ３０４を含む。更に、プロセッサ３０４は、通信チャネル３１８を介してナビゲーション装置２００と情報の送受信を行うために、送信機３０８及び受信機３１０に動作可能に接続される。送受信される信号は、データ信号、通信信号及び又は他の伝搬信号を含んでもよい。送信機３０８及び受信機３１０は、ナビゲーション装置２００の通信設計において使用される通信条件及び通信技術に従って選択又は設計されてもよい。尚、送信機３０８及び受信機３１０の機能は、信号送受信機に組み合わされてもよい。  
【００７７】
サーバ３０２は、大容量記憶装置３１２に更に接続される（又は、大容量記憶装置３１２を含む）。尚、大容量記憶装置３１２は、通信リンク３１４を介してサーバ３０２に結合されてもよい。大容量記憶装置３１２は、ナビゲーションデータ及び地図情報のストアを含む。また、大容量記憶装置３１２は、サーバ３０２とは別個の装置であってもよく、サーバ３０２に組み込まれてもよい。
【００７８】
ナビゲーション装置２００は、通信チャネル３１８を介してサーバ３０２と通信するように構成され、図２に関して上述したように、プロセッサ、メモリ等を含み、更に、通信チャネル３１８を介して信号及び／又はデータを送出する送信機３２０及び受信する受信機３２２を含む。尚、これらの装置は、サーバ３０２以外の装置と通信するためにも使用される。更に、送信機３２０及び受信機３２２は、ナビゲーション装置２００の通信設計において使用される通信条件及び通信技術に従って選択又は設計され、送信機３２０及び受信機３２２の機能は、単一の送受信機に組み合わされてもよい。
【００７９】
サーバメモリ３０６に格納されるソフトウェアは、プロセッサ３０４に命令を提供し、サーバ３０２がナビゲーション装置２００にサービスを提供できるようにする。サーバ３０２により提供される１つのサービスは、ナビゲーション装置２００からの要求の処理及び大容量データ記憶装置３１２からナビゲーション装置２００へのナビゲーションデータの送信を含む。サーバ３０２により提供される別のサービスは、所望のアプリケーションに対する種々のアルゴリズムを使用したナビゲーションデータの処理及びナビゲーション装置２００へのこれらの計算の結果の送出を含む。
【００８０】
一般に、通信チャネル３１８は、ナビゲーション装置２００とサーバ３０２とを接続する伝搬媒体又はパスを表す。サーバ３０２及びナビゲーション装置２００の双方は、通信チャネルを介してデータを送信する送信機及び通信チャネルを介して送信されたデータを受信する受信機を含む。
【００８１】
通信チャネル３１８は、特定の通信技術に限定されない。更に、通信チャネル３１８は、単一の通信技術に限定されない。すなわち、チャネル３１８は、種々の技術を使用する複数の通信リンクを含んでもよい。例えば、通信チャネル３１８は、電気通信、光通信、及び電磁通信のうちの少なくとも１つ等のためのパスを提供するように構成されることができる。そのため、通信チャネル３１８は、電気回路、ワイヤ及び同軸ケーブル等の電気導体、光ファイバケーブル、コンバータ、無線周波数（ＲＦ）波、大気、空間等のうちの１つ又はそれらの組み合わせを含むが、それらに限定されない。更に、通信チャネル３１８は例えば、ルータ、リピータ、バッファ、送信機及び受信機等の中間装置を含むことができる。
【００８２】
１つの例示的な装置において、通信チャネル３１８は、電話及びコンピュータネットワークを含む。更に、通信チャネル３１８は、無線周波数、マイクロ波周波数、赤外線通信等の無線通信に適応できてもよい。更に、通信チャネル３１８は衛星通信に適応できる。  
【００８３】
通信チャネル３１８を介して送信される通信信号は、所定の通信技術に必要とされるか又は望まれる信号を含むが、それらに限定されない。例えば、信号は、時分割多元接続（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）、符号分割多元接続（ＣＤＭＡ）、グローバル・システム・フォー・モバイル・コミュニケーションズ(Global System for Mobile Communications)（ＧＳＭ）等のセルラ通信技術において使用されるように構成されてもよい。デジタル信号及びアナログ信号の双方が通信チャネル３１８を介して送信できる。これらの信号は、通信技術にとって望ましい変調信号、暗号化信号、及び圧縮信号のうちの少なくとも１つであってもよい。
【００８４】
サーバ３０２は、無線チャネルを介してナビゲーション装置２００によりアクセス可能なリモートサーバを含む。サーバ３０２は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、仮想プライベートネットワーク（ＶＰＮ）等に位置するネットワークサーバを含んでもよい。
【００８５】
サーバ３０２は、デスクトップ又はラップトップコンピュータ等のパーソナルコンピュータを含んでもよく、通信チャネル３１８は、パーソナルコンピュータとナビゲーション装置２００との間に接続されるケーブルであってもよい。あるいは、パーソナルコンピュータは、ナビゲーション装置２００とサーバ３０２との間に接続されて、サーバ３０２とナビゲーション装置２００との間にインターネット接続を確立してもよい。あるいは、インターネットを介してナビゲーション装置２００をサーバ３０２に接続するために、移動電話又は他のハンドヘルド装置がインターネットへの無線接続を確立してもよい。
【００８６】
ナビゲーション装置２００は、情報ダウンロードを介してサーバ３０２から情報を与えられてもよい。情報は、自動的あるいはユーザがナビゲーション装置２００をサーバ３０２に接続する場合に周期的に更新されてもよく、且つ／又は例えば無線移動接続装置及びＴＣＰ／ＩＰ接続を介してサーバ３０２とナビゲーション装置２００との間に接続がより継続して又は頻繁に確立される場合に更に動的に更新されてもよい。多くの動的計算のために、サーバ３０２内のプロセッサ３０４が大量の処理要求を処理するために使用されてもよい。しかし、ナビゲーション装置２００のプロセッサ２１０も同様に、多くの場合においてはサーバ３０２への接続に関係なく、多くの処理及び計算を処理できる。
【００８７】
図２に示す様に、ナビゲーション装置２００はプロセッサ２１０、入力装置２２０、表示画面２４０を含む。入力装置２２０及び表示画面２４０は、例えばタッチパネルスクリーンを介して情報（直接入力、メニュー選択など）を入力すること及び情報を表示することとの両方を可能にするために、一体型入力表示装置に統合される。このようなスクリーンは、当業者には周知のものであるように、例えばタッチ入力ＬＣＤスクリーンであってもよい。更に、ナビゲーション装置２００は、例えばオーディオ入力／出力装置などの、更なる任意の入力装置２２０と更なる任意の出力装置２４１との少なくとも一方を有しても良い。
【００８８】
図４Ａ及び図４Ｂは、ナビゲーション装置２００の斜視図を示している。図４Ａに示すように、ナビゲーション装置２００は、一体型入力表示装置２９０（例えばタッチパネル画面）と図２の他の構成要素（内蔵ＧＰＳ受信機２５０、マイクロプロセッサ２１０、電源、メモリシステム２３０などを含むがこれに限定されない）を含むユニットであっても良い。
【００８９】
ナビゲーション装置２００は、アーム２９２上に備え付けられても良い。このアーム２９２は、吸着カップ２９４を用いて、車両のダッシュボード／窓／等に固定されても良い。このアーム２９２は、ナビゲーション装置２００がドッキング可能なドッキングステーションの一例である。
【００９０】
図４Ｂに示すように、ナビゲーション装置２００は、例えば、アーム２９２に対してナビゲーション装置２９２をスナップ接続することで、ドッキングステーションのアーム２９２にドッキング若しくは接続することができる。図４Ｂにおける矢印で示すように、ナビゲーション装置２００は、アーム２９２上で回転可能である。ナビゲーション装置２００とドッキングステーションとの間の接続を解除するためには、例えば、ナビゲーション装置２００上のボタンを押下すればよい。ドッキングステーションに対してナビゲーション装置を結合及び分離する他の同等の適切な構成は当業者には既知である。
【００９１】
添付図面の図５を参照すると、メモリ資源２３０は、ブートロードプログラム（不図示）を格納する。該プログラムは、アプリケーションソフトウェア４８０が実行可能な環境を提供する機能ハードウェア構成要素による実行を目的として、メモリ資源２３０からオペレーティングシステム４７０をロードするために、プロセッサ２１０により実行される。オペレーティングシステム４７０は、機能ハードウェア構成要素を制御するように提供され、アプリケーションソフトウェア４８０と機能ハードウェア構成要素との間に設けられる。アプリケーションソフトウェア４８０は、例えば地図表示、経路計画、ナビゲーション機能、及びそれらとともに関連付けられたあらゆる他の機能のような、ナビゲーション装置２００のコア機能をサポートするＧＵＩを含む動作環境を提供する。本発明の公的な実施形態に関して、この機能性の一部は、探索経路モジュール４９０を有し、該機能は後続の図面と共に、以下、詳細に説明される。
【００９２】
発明の一実施形態によれば、ナビゲーション装置は、ロケーションへのまたは該ロケーションからの経路を装置に可能ならしめるのに十分な位置情報を含む、複数のロケーションに関する情報を格納する（あるいは入手可能である）。少なくともいくつかのロケーションは、ユーザ要求を満たす特定の種類のロケーション（即ち対象ロケーション種類のロケーション）の範囲に含まれるものとして識別されるが、そのような識別が保証されるものではない。これらのロケーションは、ユーザ要求を潜在的に満たす、（潜在位置における）潜在ロケーションとして考慮されうる。例えば、ユーザ要求が「空車の駐車スペース」である場合、対象ロケーション種類は駐車スペースとなりえる。本実施形態のナビゲーション装置は、空車の駐車スペースが見つかるまで、１以上の駐車スペース（特定の種類のロケーション）に至る探索経路をユーザに提供する。理想的には、駐車スペースへの距離、該駐車スペースにおける駐車料、及び他のロケーションと比較した該駐車スペースの実際の位置等の他の要素を可能な限り考慮しながら、探索経路は駐車スペースの発見に係る高い可能性を有すべきである。
【００９３】
他の種類のロケーションが等価的に適用可能であることは、本技術分野に属する当業者にとって明らかである。例えば、ユーザはホテルを必要とするが、要求を満たすかを決める前の人はホテルを見ることを望む。この時、ユーザは判断するために１以上のホテルを訪れる探索経路を要求しうる。ホテルの例は、徒歩旅行者用のナビゲーション装置や乗物に搭載された装置に適用可能である。一方で、空車の駐車スペース発見の例は、ナビゲーション装置が乗物に搭載されている場合に有用であると考えられる。利便性のため、駐車スペースの例が本実施形態の開示に用いられるが、これに限定されるものと考えられるべきではない。
【００９４】
空車の駐車スペースについてのユーザ要求に応じて、探索経路モジュールはメモリ２３０に格納された地図情報を探索し、ユーザにより要求された種類である複数のロケーション（対象ロケーション種類のロケーション）を決定する。そして探索経路モジュールは、要求種類のロケーションの発見可能性に基づき、予め定められた効率尺度を用いて経路を決定する。その後、ユーザは出力装置２６０及び／または表示装置２４０を介して経路の情報を取得する、あるいは経路はＩ／Ｏ装置を介して出力されうる。
【００９５】
一実施形態において、ナビゲーション装置２００は、図３に示されるような、少なくとも装置２００の現在位置の情報を提供するＧＰＳユニット３２４のような位置情報決定部を含み、装置２００の移動に係る方向及び／または速度の情報も提供しうる。位置情報決定部は、例えばＧＰＵを用いて実現されうる。ユーザが空車の駐車スペースを要求することを示した場合、探索経路モジュール４９０は、例えば少ない走行距離でできるだけ多くの駐車スペースを通過する探索経路を構築することにより、少ない走行距離で最大の駐車スペース発見可能性を有する、現在位置（装置２００の現在位置）から出発する経路を決定する。
【００９６】
このことは、短時間／短い走行距離で駐車スペースを発見する良好な可能性を有する探索経路を、ユーザに提供する。このことは、各駐車スペースを別々に選択し、任意の方式で一連の駐車スペースをユーザに指示することが好ましい。例えば、最も近い駐車場が小さく、反対方向にわずかに長い距離進んだ地点に多数の近接した大規模駐車場の集合が存在する場合に、大規模駐車場が、少ない走行距離で、空車の駐車スペースを発見する良好な可能性を有するものとして提供される。
【００９７】
例示の目的で、図６は道路Ｒ１〜Ｒ６の、簡略ロードネットワーク図を示している。各道路は任意の単位のＬ１〜Ｌ６の長さを有し、各道路において駐車が可能であるとする。各道路の駐車スペースの数Ｓｉは、地図情報に含まれうる、あるいは道路長及び道路の種類についてのあらゆる情報（例えばレーン数、既知の駐車条件）に基づいて推定されうる。本例において、長い道路ほど駐車するより多くのスペースを有するように、各道路Ｒｉの駐車スペースの数は１０×Ｌｉであるものとする。駐車場Ｒ７は道路Ｒ６の終端に配置され、本例では４０の駐車スペースを有する。ここで、簡単のためＲ７は「道路」として参照される。ユーザ及びナビゲーション装置は、分岐点Ｏに近づいており、ユーザは駐車スペースへの探索経路の計画をナビゲーション装置２００に指示しているものとする。本例によれば、道路Ｒ１〜Ｒ６はすべて、予め定められたカットオフ半径内の駐車スペースを可能にする道路である。あるいは予め定められた走行距離内に駐車スペースを有する。該カットオフ半径または走行距離は、ユーザが探索経路を要求した位置または分岐点Ｏから決定されうる。
【００９８】
探索経路モジュール４９０は、次の分岐点について利用可能な各経路、この場合は左折または右折経路について、コスト関数を評価する。ここで分岐点は、道路が分岐する、または２以上の経路の選択がある、あらゆるロケーションを説明するために用いられる。次の分岐点は、特定のロケーションから出発し、特定の方向に走行した際に到達する最初の分岐点である。特定の分岐点についてのＯｉは、該分岐点における（ｉが付された）特定の経路選択を行うことにより到達しうる道路のセットを示している。Ｏｉは一般的に位置及びロケーションに依存する。本例では、Ｏ１＝｛Ｒ１、Ｒ２、Ｒ３｝は左折により到達しうる道路のセットを示し、Ｏ２＝｛Ｒ４、Ｒ５、Ｒ６、Ｒ７｝は右折により到達しうる道路のセットを示す。コスト関数の第１の例は、
2013533964.tif 000003
である。ここで、Ｄｉは道路Ｒｉと分岐点Ｏとの距離である。本例では、道路における平均的な駐車スペースの位置を代表するように、Ｏから道路の中点までの距離が採用されるが、これは道路の一端に向かう重みのような、追加の情報により変更されうる。また、道路を複数のサブ道路に分割し、各サブ道路における様々な状態を考慮することもできる。本例のコスト関数の評価は、表１に示される。
【００９９】
【表１】
2013533964.tif 000004
【０１００】
表１からわかるように、右折についてのコスト関数（最終行）は左折についてのコスト関数よりも高くなるため、探索経路は右折となる。なお、ここで「コスト関数」は、最適状態において最大化または最小化された関数を意味する数学的な判断に用いられる。ここで、最大化されたコスト関数が好適な解となるが、最小化された場合に好適な結果を与えるように他のコスト関数が構成されてもよい。計算された探索経路に関して、ナビゲーション装置２００は、（表示装置２４０、スピーカ２６０、またはＩ／Ｏポート２７０を介して）ユーザに右折する方向を与える。
【０１０１】
コスト関数の第２の例によれば、地図情報は特定の道路における駐車スペースの発見可能性に関する確率情報を含む。図６は、各Ｒｉについての確率情報Ｐｉを例示しており、この場合、該確率は、道路のスペースを発見する総合的な確率（０≦Ｐｉ≦１）であるものとする。Ｐｉを用いたコスト関数の例は
2013533964.tif 000005
である。表２は、本例における該コスト関数を用いた結果を示している。
【０１０２】
【表２】
2013533964.tif 000006
【０１０３】
本例によれば、ナビゲーション装置は、左折についてのコスト関数が右折のものよりも大きいため、分岐点Ｏにおいて左折をユーザに示す。本例ではスペースの（推定）数と空きスペースの発見可能性との間にわずかな相関関係が存在するため、この結果は、コスト関数Ｃ１により与えられる方向と異なる。このように、本例は確率情報が利用可能な場合に、改良された探索経路を提供する。
【０１０４】
確率値Ｐｉは、道路の種類、及びレーン数、一方通行であるか双方通行であるか等の道路ルールの知識について予測されうる。また、確率値は例えば調査を実行することにより、経験的に決定されてもよい。
【０１０５】
コスト関数の第３の例は、ユーザが駐車スペースを発見した後に向かうつもりである最終目的地、または到達地を考慮する。本例のコスト関数を用いる本発明の実施形態によれば、装置はユーザから、空車の駐車スペースが要求されたことを示す情報、及び駐車スペースを発見した後にユーザが駐車スペースにおかれた乗物を離れて向かうつもりのさらなるロケーションＸの情報を受信するように構成される。図６においてＸは、Ｒ５またはＲ６から徒歩で到達しうる到達地を示し、ＸｉはＲｉの中心点（Ｒｉにおける駐車スペースの平均ロケーション）からＸへの距離を示している。この場合、コスト関数は
2013533964.tif 000007
であってよい。ここで、αはＤｉとＸｉの距離の相対的重要性を重みづける所定の定数である。例えば、ユーザが駐車スペースからＸに徒歩で行く場合、Ｘに近い駐車スペースを発見するために、より長い運転も許容にされうる。この場合αは１０に設定されてよい。図６の例において該コスト関数を用いた結果は、表３に示される。本例では単純にα＝１を用いている。
【０１０６】
【表３】
2013533964.tif 000008
【０１０７】
本例での確率は、コスト関数の第２の例と同様であるが、本例のナビゲーション装置はＸへの接近が駐車スペースの低減された発見確率を上回るように、右折（右がより高い値Ｃ３を与える）をユーザに示す。このことは、他のロケーションの位置に対する潜在位置のロケーション、及び対象種類のロケーションを発見する可能性を、探索経路について考慮することを可能にする。
【０１０８】
他の例のコスト関数は
2013533964.tif 000009
である。Ｃ４はＣ３に類似するが、ＤｉとＸｉ間の重みは、Ｘｉの増加に伴い、より大きくなる。このことは、駐車スペースから目的地への短い歩行は可能にするが、長い歩行は回避するコスト関数に対応しうる。
【０１０９】
コスト関数は、特定ロケーションにおける駐車料金に応じて、例えば
2013533964.tif 000010
のように重みづけられうる。ここでＦｉは道路Ｒｉに駐車するための駐車料金またはチャージである。
【０１１０】
他の例において、近場の探索経路（到達地Ｘが近い）は上述した方法と同様の方法で計算されるが、探索の出発地点として最終到達地Ｘ（または近くの道路）をとり、コスト関数
2013533964.tif 000011
を用いる。ここで、Ｎｊは道路セットであり、Ｏｊは上述したものと同様であるが、Ｘに近い出発地点から運行した場合に到達する最初の分岐点に基づく。そして、探索経路は、現在のロケーションから近場の探索経路の出発地点、または該近場の探索経路上のいくつかの他の地点への経路を計画することにより決定される。これは、到達地Ｘの近くの空車の駐車スペースの良好な発見可能性を有する近場探索経路を提供しうるが、探索経路の出発地点と駐車スペースとの間の距離についての重みづけを与えない。近場探索経路の出発地点から様々な方向をとることが可能な場合、探索経路は各方向について計算され、最も良好なものが近場探索経路に設定される。このことは探索経路の生成において、現在のロケーションを有することが探索経路の決定に重要であることを考慮しない。
【０１１１】
確率を用いる例において、確率は時間依存であってもよい。例えば、様々な確率が表４のように様々な時間間隔で設定されていてもよい。様々なロケーションは、１つの駐車場が「平日８時〜９時」及び「平日９時〜１０時」の間隔を有し、他の駐車場が「平日７時半〜８時半」及び「平日８時半〜１０時半」の間隔を有するように、様々な時間間隔が用いられてよい。そして経路は、探索経路が要求された場合に、現在の時刻に関連付けられた確率、または駐車スペースへの到達予測時刻に関連付けられた確率を用いて計算されうる。また確率は、将来使用される経路を計画するためにユーザにより選択された任意の時間について計算されてもよい。時間変化は、各駐車スペース（あるいは駐車スペースのグループ）について、様々な時間の確率を格納することにより実現されうる。また、時間変化を有するいくつかの数学関数が、時間と共に変化する確率を提供するために用いられうる。他の例では、特定の時間における確率は、格納された確率データの内挿または外挿により算出されうる。確率は、固定の間隔について設定されるものではなくむしろ、数学関数や内挿／外挿を用いる場合は特に、任意の小間隔に変更可能であってよい。ナビゲーション装置２００は、内部クロックから、あるいはデータ接続（例えばＩ／Ｏポート２７０）を介して外部ソースから現在の時刻を取得する、または例えば入力装置２２０を介してユーザからの入力を取得する。確率の時間変化を可能にすることは、潜在位置における対象種類のロケーションの発見確率を、より正確に確率情報に反映する。
【０１１２】
【表４】
2013533964.tif 000012
【０１１３】
上述の例は、例えば駐車スペースとナビゲーション装置の現在のロケーションとの距離、あるいは駐車スペースと到達地との距離に基づく測定基準を利用する。しかしながら、本発明は推定運行時間に基づく測定基準等、他の測定基準を用いて実現されてもよい。
【０１１４】
ユーザの現在の要望に適した探索経路を生成するために、ユーザにはコスト関数の選択、及びパラメータ（上述のＣ３及びＣ４におけるα等）変更の機会が与えられうる。例えば、ユーザが到達地の近くにいて、可能な限り早く駐車したい場合、Ｃ２が最良のコスト関数となりうる。一方、ユーザが長距離を歩くことができず、駐車後に特定の到達地を訪問するつもりである場合、高い値が設定されたαを有するＣ４がより適している。
【０１１５】
説明を簡単にするために、上述の例は探索経路が逆戻りすることを考慮していないが、該例は逆戻りを可能にするように変更されてよい。同様に、全ての道路は双方通行であり、道路のいずれのスペースも運行方向によらずアクセス可能であるものとしている。これらの前提を除外した適応的な実装は、同一の技術分野に属する当業者によって構築されうる。
【０１１６】
説明を簡単にするために、上述した例は次の分岐点において与えられる方向の観点から経路を計算している。しかしながら、代替的な実施形態において、ユーザが経路を要求した時点において、完全な探索経路が例えばいくつかの最大長に従って計算される。完全な探索経路は、全ての取りうる経路を計算し、最大探索経路長に従ってこれらの経路の各々を評価し、コスト関数に基づいて最良経路を選択するように構成されうる。理想的には、各ｋ経路について計算されるコスト関数は、道及び該道により訪問する駐車場のみに依存しうる。このような実施形態において用いられるコスト関数の例は、
2013533964.tif 000013
である。ここで、Ｑｊは道路Ｒｉを含む計算された道路であり、Ｄｉは現在位置から道路Ｒｉの平均的な駐車スペースまでの距離である。このコスト関数の例は上述したＣ２と同様であるが、Ｃ１、またはＣ３乃至Ｃ６と同様のコスト関数のような他のコスト関数が代わりに用いられてもよい。完全探索経路の計算は、より多い処理リソースを必要としうるが、改善された探索経路が提供されうる。
【０１１７】
従来技術において既知の経路計画アルゴリズムは、一般的に特定の位置を有する特定の到達値への経路を計画するために、距離あるいは時間に基づくコスト関数を採用する。いくつかの実施形態において、これらの既知のアルゴリズムの１つは、上述のものと同様なコスト関数を用いるように適用されてもよい。
【０１１８】
いくつかの実施形態によれば、ナビゲーション装置２００は探索が成功するか否か、探索が成功したのであれば対象ロケーションが発見されたロケーションを示す探索結果を判断する。１つの実施形態において、対象ロケーションが空車の駐車スペースである場合、空車の駐車スペースが発見されている際に、ユーザは入力装置２２０を介して確認するために、表示装置２４０を介して尋ねられる。また、駐車スペースが発見されていない場合にもユーザは確認のために尋ねられもよい。他の実施形態において、探索経路モジュール４９０は、位置情報決定部３２４からの情報に基づき、例えば予め定められた期間装置の動きが停止している場合に、駐車スペースが発見されたものと判断する。同様に、探索経路モジュール４９０は、ナビゲーション装置２００が潜在駐車スペースを通過し続けている場合に、空車の駐車スペースが発見されていないものと判断してもよい。他の実施形態において、探索経路モジュールは、ナビゲーション装置２００が乗物のイグニッションがスイッチされたことを検出した場合に、駐車スペースが発見されたと判断する。同様に、乗物のイグニッションがスイッチオフされず、ナビゲーション装置２００が潜在駐車スペースを通過している場合に、空車の駐車スペースが発見されていないものと判断されてもよい。
【０１１９】
いくつかの実施形態において、潜在駐車スペースまでの距離を計算するために、上述の例で駐車スペースは道路の中央にあるものされていたように、平均的な位置が駐車スペースに割り当てられる。しかしながら、駐車スペースを通過したかどうかを考慮する場合、例えば道路の遠端に到達したことを判断することにより、直近に可能であった駐車スペースを通過したかどうかを考慮することが、より適切であると思われる。
【０１２０】
探索結果を判断する実施形態において、結果は様々な方法で使用されうる。例えば、情報は、地図情報における確率情報の更新に用いられうる。また探索結果は、中央サーバ３０２がサーバ３０２に格納される確率情報を更新可能なように、あるいは他のナビゲーション装置２００による結果情報の使用を可能にする他のナビゲーション装置２００に結果を配信可能にするために、インターネットのような通信チャネル３１８を介して中央サーバ３０２に送信されてもよい。ナビゲーション装置２００が互いに直接通信可能である場合、結果情報は中央サーバ３０２を介するよりも、むしろ他のナビゲーション装置２００に直接提供されうる。またナビゲーション装置２００は、以下により詳細に説明するように、一時的な確率情報の更新に結果を用いてもよい。同様に、中央サーバ３０２や他のナビゲーション装置２００は、一時的な確率情報を更新するために、受信した探索結果情報を用いてもよい。またナビゲーション装置２００は、中央サーバ３０２や他のナビゲーション装置２００から結果情報を受信し、確率情報及び／または一時的な確率情報を更新するために受信した結果情報を使用してもよい。ナビゲーション装置２００と、中央サーバ３０２及び／または他のナビゲーション装置２００との通信は、移動通信ネットワークを介するインターネット接続のような、あらゆる適切な通信チャネル３１８を介してなされうる。
【０１２１】
図７は、一実施形態に係るナビゲーション装置２００における確率情報の更新方法を示している。方法はステップ７００で開始し、ステップ７１０で駐車スペースのような次の潜在位置に到達したか否かの判断がなされる。潜在位置が対象ロケーション種類である（例えば空車の駐車スペースが発見された）場合、方法は、確率情報が現在の潜在位置において対象種類のロケーションの発見確率を増加するために調整されるステップ７３０に進む。時間依存確率が用いられる場合、これは全時間、現在時刻のみ、または現在時刻周辺における確率の増加を伴いうる。確率の増加後、方法はステップ７４０に移る。ステップ７２０において対象種類のロケーションが潜在位置において発見されなかった（例えば空車の駐車スペースが見つからなかった）場合、方法は、現在の潜在位置における対象ロケーションの発見確率を減少させるステップ７５０に進む。そして方法はステップ７６０で、探索経路において他の潜在位置が残っているかどうかを判断する。更なる潜在位置がある場合、方法は次の潜在位置を現在の潜在位置として設定し（ステップ７７０）、ステップ７１０に戻る。更なる潜在位置がない場合、方法はステップ７４０に移る。
【０１２２】
確率は、ｙが成功であるｐ＝ｙ／Ｎの、以前の駐車スペースを発見しようとした試みＮに基づく。スペースの発見に成功した場合、新たな確率はｐ＝（ｙ＋１）／（Ｎ＋１）に、スペースが見つからなかった場合はｐ＋ｙ／（Ｎ＋１）となる。ｐの値が推定される場合、初期推定はｙ及びＮの値の設定により生成されうる。例えばＮは、値が大きいほど新たなデータに対しより緩やかに変化する確率を与えるように、推定における信頼性を反映し、ｙは特定の推定初期確率を与えるようにＮに基づいて設定されうる。時間と共に、各潜在位置において空車の駐車スペースを発見することにより、または発見しないことにより、及びそれにしたがって確率を更新することにより確率情報が改良されるように、実際の確率をより代表的な値に近づけるべきである。
【０１２３】
また、確率情報は、０〜１の間の数字として格納されてよい。このケースにおいて、空車の駐車スペースが発見された場合、確率は
2013533964.tif 000014
に従って増加されうる。ここで、ｐｎｅｗは調整された確率であり、ｐｏｌｄは調整前の確率である。β＋は、各時間で空車の駐車スペースが発見される確率を如何ほど変化させるかを調整する、１以上のパラメータである。該構成によれば、確率は１未満にとどまるだろう。空車の駐車スペースが見つからない場合、確率は
2013533964.tif 000015
に従って減少されうる。ここでβ−は、空車の駐車スペースが見つからない場合に確率を如何ほど変化させるかを調整する、１以上のパラメータである。この調整により、確率は０以上にとどまるだろう。これにより、確率情報がより正確になり、対象種類のロケーションを発見する実際の確率の変化に自動的に適応可能となる。
【０１２４】
図８は、ナビゲーション装置２００の一実施形態における一時的な確率の設定方法を示している。本実施形態によれば、一時的な確率は短時間設定され、基準の確率（即ち、例えば図７について上述した確率）に代わって用いられる。ステップ８００、８１０、８２０、８４０、８６０、及び８７０は、それぞれ図７のステップ７００、７１０、７２０、７４０、７６０、及び７７０に対応している。ステップ８５０で、ステップ８２０における現在の潜在位置において対象種類のロケーションが発見されなかったことが判断されたのち、一時的な確率は現在の潜在位置をゼロ、または他の低い値に設定される。空車の駐車スペースの探索する場合、例えばこれは現在の位置において今はスペースがないことを反映し、探索経路が近い将来再計算される場合に該情報が用いられることを可能にする。やがて、その駐車スペースに関する確率は、基準の確率に復帰するだろう。これは、所定の時間経過後に段階的に生じうる、あるいは例えば
2013533964.tif 000016
に従って徐々に生じうる。
【０１２５】
ここで、ｐ（ｔ）は時刻ｔにおける潜在位置に関係する、空車の駐車スペースがないとの判断から測定された確率を示す。ｐｂａｓｉｃは一時的な可能性がない場合に用いられる基準の可能性であり、Ｔは一時的な可能性が使用されている存続時間を判断するパラメータである。これにより、確率情報は存続期間の短い効力を有する情報を考慮して調整される。
【０１２６】
図９は、第１のナビゲーション装置２００により導かれた探索結果の情報が中央サーバ３０２に送信され、中央サーバ３０２が確率情報及び／または一時的な確率情報を更新するための情報を用いて、更新情報を第２のナビゲーション装置２００に提供しうる実施形態に係る方法を示している。このことは、ナビゲーション装置間の情報共有が、情報のサンプルサイズ及び正確性を改良するようになされることを可能にする。
【０１２７】
図９Ａは、第１のナビゲーション装置２００の実施形態により実行される方法を示している。ステップ９１０、９１１、９１２、９１４、９１６、及び９１７は、図７のステップ７００、７１０、７２０、７４０、７６０、及び７７０と同様である。ステップ９１２において対象種類のロケーションが特定の潜在位置において発見されたと判断された後、第１のナビゲーション装置２００は該情報を中央サーバ３２０に通信する。そして、方法はステップ９１４に移る。一方、ステップ９１２において対象種類のロケーションが潜在位置において発見されなかったと判断された場合、該情報はステップ９１５で中央サーバ３２０に通信される。そして方法はステップ９１６に進む。
【０１２８】
図９Ｂは、中央サーバ３２０の実施形態により実行される方法を示している。方法はステップ９２０で開始し、ステップ９２１で中央サーバ３２０は、ステップ９１４や９１６において第１のナビゲーション装置２００により通信された情報のような、結果情報がナビゲーション装置２００から受信されたかを判断する。結果情報が受信されている場合、方法は、結果情報が対象ロケーションが発見されたことを示すかどうかを判断するステップ９２２に進む。対象が見つからない場合、中央サーバ３２０はステップ９２３ａで、中央サーバにおいて格納される確率情報内の関連する（対象ロケーションが発見された潜在位置に対応する）確率を増加させる。このことは、ナビゲーション装置２００に関して上述したような、新たな情報を考慮して確率情報を改訂することにより、確率情報を改良する。ステップ９２３ａの代替として、あるいはステップ９２３ａに加えて、中央サーバ３２０に格納された一時的な確率は減少されてもよい。駐車スペースのケースでは、これは駐車し、スペースを使用している第１のナビゲーション装置２００に関連する乗物に応じて、現在の瞬間でのスペースの発見確率についての減少を反映する。中央サーバ３２０に格納される一時的な確率は、ナビゲーション装置２００について上述した一時的な確率と同様である。
【０１２９】
ステップ９２２において対象種類のロケーションが発見されなかったと判断した場合、中央サーバ３２０はステップ９２４ａで、中央サーバ３２０に格納されている確率情報の関連する（対象ロケーションが発見されなかった潜在位置に対応する）確率を減少させる。これは、ナビゲーション装置２００について上述した確率の調整と同様である。ステップ９２４ａの代替として、あるいはステップ９２４ａに加えて、中央サーバ３２０に格納される一時的な確率は、対象ロケーション種類が潜在位置において現在なく（例えば空車の駐車スペースが存在しない）、少なくとも短時間は見込みがないという情報を反映するように、ゼロ（または小さい数）に設定されうる。そして方法はステップ９２１に戻る。  
【０１３０】
ステップ９２１において、結果情報が受信されない場合、方法はステップ９２５に進み、情報についての要求をナビゲーション装置２００から受信したかどうかを判断する。要求は、対象ロケーションの種類、装置２００の現在のロケーション、探索経路の希望出発ロケーション、到達地Ｘ（最終目的地）、所望の移動（到達）時間、乗物の種類、及び探索経路についての他のユーザ設定のうちの１以上を含みうる要求情報を含む。同一の技術分野に属する当業者は、実装の詳細に応じて、要求情報に他の情報が含まれてもよいことを、理解するだろう。
【０１３１】
要求が受信されない場合、方法はステップ９２１に戻る。情報の要求が受信された場合、応答情報がナビゲーション装置に提供され（ステップ９２６）、そして方法はステップ９２１に戻る。ナビゲーション装置に提供される応答情報は、確率情報を決定するための適切な情報を有し、例えば、位置と確率データの組、予め定められた計算式に用いるパラメータが組み合わされた位置データ、または潜在位置に特にリンクされない、予め定められた計算式に用いるパラメータの形式で得られる。また中央サーバ３２０は探索経路を決定し、応答データは該探索経路を指定するデータであってよい。
【０１３２】
代替構成において、ナビゲーション装置２００は、探索経路が計画される場合に情報の要求を送信しない。その代わり、地図データまたはナビゲーション装置ソフトウェアが中央サーバ３２０により更新される（例えば定期更新）場合に、更新された確率及び／または一時的な確率情報が中央サーバ３２０からナビゲーション装置２００に送信される。一時的な情報の存続期間（対象ロケーションの種類に依存しうる）及び更新頻度に従い、本方法では一時的な情報が送信されることは実用的ではない。この場合、基準の確率情報のみが送信される。
【０１３３】
中央サーバ３２０により収集された結果情報は、将来生成されるナビゲーション装置２００の確率情報を改良するために用いられうる。故に、中央サーバ３２０への結果情報の送信は、中央サーバ３２０がナビゲーション装置２００に情報（改訂された確率情報等）を提供しない実施形態でさえも有用である。
【０１３４】
図９Ｃは、中央サーバ３２０からの情報を要求するナビゲーション装置２００の実施形態により実行される方法を示している。方法はステップ９３０で開始し、ステップ９３１で、ナビゲーション装置はユーザからの探索ルートを決定する決定するための要求を受信する。ステップ９３２で、ナビゲーション装置２００は要求情報を含む要求を、ステップ９２５において該要求を受信する中央サーバ３２０に送信する。ナビゲーション装置２００はステップ９３３で、ステップ９２６において中央サーバ３２０により通信された応答情報を受信する。ナビゲーション装置２００はステップ９３４で、応答情報（及びナビゲーション装置に格納される地図情報のような可能性がある追加情報）に基づいて、探索経路を決定する。探索経路の決定は、上述した実施形態または例示のいずれかに応じて実行されてよい。応答情報が探索経路を含む場合、ステップ９３４は省略される。探索経路はステップ９３５においてユーザに提供される。例えば、これは表示装置２４０を介して地図上に完全な探索ルートをユーザに示す形式、あるいは音声及び／または画像指示を提供する形式をとってもよい。
【０１３５】
いくつかの実施形態において、ナビゲーション装置２００は中央サーバ３２０を介すよりはむしろ、直接互いに通信しうる。この場合、例えば結果情報は局所領域における全てのナビゲーション装置２００（あるいは予め定められたグループ内のナビゲーション装置２００のようなサブセット）により通信されうる。結果情報が自動的に共有される実施形態について、要求情報を送信することは装置２００に不要であろう。他の実施形態において、要求情報はすべての局所ナビゲーション装置２００またはサブセットに対して送信され、該要求に応じて、ナビゲーション装置２００は応答情報を提供する。到達地Ｘがナビゲーション装置２００の現在のロケーションの近くではない場合、上述した「局所領域」は現在のロケーションよりもむしろ、到達地Ｘの近くの領域となりうる。
【０１３６】
ナビゲーション装置２００が乗物に関連付けられ（例えば搭載され）、駐車スペースが以前に発見された実施形態において、ナビゲーション装置２００は、乗物が駐車スペースから出発した、または立ち退いた場合に判断する。これは、ユーザからの入力、あるいはナビゲーション装置２００が位置情報に基づいて動いている方向に（いくつかの装置２００が例えば歩行者によるナビゲーションのために乗物から離れて使用されることも場合により考慮して）基づいていてよい。ナビゲーション装置２００が駐車スペースから立ち退いたことを判断した場合、該情報は中央サーバ３２０及び／または上述した局所領域内の他のナビゲーション装置２００に渡されうる。そして中央サーバ３２０及び／またはナビゲーション装置２００は、例えば一時的な確率を１に設定する、あるいは一時的な確率を所定の法則で（例えば基準の確率の調整について上述した記載に従って）増加させることにより、新たな空車の駐車スペースの存在を反映するように、上述した記載に従って一時的な確率を設定する。
【０１３７】
上述した実施形態において、装置２００はローカルメモリ２３０に全ての地図情報を格納する、あるいは他の通信チャネル３１８のインターネットを介してサーバ３２０からすべての地図情報を取得してもよい。
【０１３８】
他の実施形態においてナビゲーション装置２００は、上述した実施形態と同様の方法で動作することにより探索経路についてのユーザ要求に応答する経路計画ソフトウェアを実行する、デスクトップコンピュータのような経路計画装置である。他の計算装置は、同一の技術分野に属する当業者に明らかなように用いられてよい。また経路計画装置は、インターネットのようなネットワークを介してサーバ３２０に接続された情報端末（デスクトップコンピュータ及び携帯電話等）から要求を受信し、探索経路を記述した情報を応答するサーバ３２０内において実装されてもよい。このようなサーバは、上述した中央サーバ３２０のように動作してもよい。
【０１３９】
位置情報を判断するように用意されたナビゲーション装置２００の実施形態において、追従する経路を決定する必要がある移動において、あらゆる地点に、あるいはあらゆる地点のすぐ前に、方向がユーザに提供される。位置情報を判断する実施形態において、探索経路は、例えば（分岐点に到達した際、ユーザが探索経路から外れた際、あるいは探索経路の最後の計算から所定期間経過した際のような）到達しているいくつかの状態に応じて再計算されうる。
【０１４０】
本発明の教示が、予め定められた効率尺度に基づいて要求された種類の目的地の発見可能性を考慮した、最も効率的な探索ルートがユーザに提供される構成を提供することが上記より明らかとなる。
【０１４１】
本発明の種々の態様及び実施形態を説明したが、本発明の範囲は本明細書で説明した特定の構成に限定されず、添付の請求の範囲の範囲内の全ての構成、並びにそれらに対する変形例及び変更例を含むことが理解されるだろう。
【０１４２】
例えば上記の詳細な説明で説明した実施形態はＧＰＳを参照するが、ナビゲーション装置はＧＰＳの代わりに（又は実際にはＧＰＳに加えて）どんな種類の位置検出技術を利用してもよい。例えばナビゲーション装置は、欧州のGalileoシステム等の他のグローバルナビゲーション衛星システムを用いることにより有用であってもよい。同様に、ナビゲーション装置は、衛星を用いたものに限定されないが、地上ビーコン又は装置が地理的な場所を判定することを可能にする他の何らかの種類のシステムを使用して容易に機能できる。
【０１４３】
好適な実施形態はソフトウェアにより特定の機能性を実現するが、機能性はハードウェアのみで（例えば、１つ以上のＡＳＩＣ（特定用途向け集積回路）を使用して）又は実際にはハードウェア及びソフトウェアの組合せにより同等に実現可能であることが当業者にはよく理解されるだろう。従って、本発明の範囲は、ソフトウェアでのみ実現されることに限定されると解釈されるべきではない。
【０１４４】
最後に、添付の請求の範囲は本明細書で説明した特徴の特定の組合せを説明するが、本発明の範囲は以下に請求される特定の組合せに限定されず、特定の組合せが添付の請求の範囲において特に列挙されているかいないかに関わらず本明細書で開示された特徴又は実施形態のいかなる組合せも含む。
【図１】
2013533964.tif 000017
【図２】
2013533964.tif 000018
【図３】
2013533964.tif 000019
【図４Ａ】
2013533964.tif 000020
【図４Ｂ】
2013533964.tif 000021
【図５】
2013533964.tif 000022
【図６】
2013533964.tif 000023
【図７】
2013533964.tif 000024
【図８】
2013533964.tif 000025
【図９Ａ】
2013533964.tif 000026
【図９Ｂ】
2013533964.tif 000027
【図９Ｃ】
2013533964.tif 000028
【手続補正書】
【提出日】平成25年6月5日(2013.6.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の潜在位置を示す情報を含む地図情報を記録する記録部であって、
各潜在位置が予め定められた種類のロケーションが潜在的に発見されうる位置に対応する記録部（２３０、３０６）と、
前記予め定められた種類のロケーションの発見可能性に基づく予め定められた効率尺度を用いて、少なくとも１つの前記潜在位置を訪れる探索経路を決定する探索経路モジュール（４９０）と、を有する
ことを特徴とする経路計画装置（２００、３０２）。
【請求項２】
前記地図情報は、各潜在位置について、各潜在位置における前記予め定められた種類のロケーションの発見可能性に対応する確率情報を含むことを特徴とする請求項１に記載の装置（２００、３０２）。
【請求項３】
前記確率情報は、前記各潜在位置における予め定められた種類のロケーションの発見可能性に、時間的変化を示す時間的成分を含むことを特徴とする請求項２に記載の装置（２００、３０２）。
【請求項４】
前記潜在位置は、駐車スペースに対応し、
前記予め定められた種類のロケーションは、空車の駐車スペースに対応することを特徴とする請求項１乃至３のいずれか１項に記載の装置（２００、３０２）。
【請求項５】
前記探索経路は複数の前記潜在位置を訪れるように決定されることを特徴とする請求項１乃至４のいずれか１項に記載の装置（２００、３０２）。
【請求項６】
ユーザからの命令を受け付ける入力部（２２０）をさらに有し、
前記探索経路モジュール（４９０）は、前記入力部（２２０）を介してユーザが予め定められた種類の位置への探索経路が決定されるべきであることを指示する場合に、前記装置（２００、３０２）の現在位置を出発位置として設定し、
前記探索経路モジュール（４９０）は、前記出発位置から出発するように前記探索経路を決定する
ことを特徴とする請求項１乃至５のいずれか１項に記載の装置（２００、３０２）。
【請求項７】
前記予め定められた効率尺度は、前記出発位置及び前記潜在位置に関する予め定められた距離関数に少なくとも一部基づくことを特徴とする請求項６に記載の装置（２００、３０２）。
【請求項８】
前記探索経路モジュール（４９０）は、到着地位置（Ｘ）を示す到着地指示部を含み、  前記予め定められた効率尺度は、前記到着地位置（Ｘ）及び前記潜在位置に関する予め定められた距離関数に基づく
ことを特徴とする請求項１乃至７のいずれか１項に記載の装置（２００、３０２）。
【請求項９】
前記探索経路モジュール（４９０）は、訪問した潜在位置において予め定められた種類のロケーションが発見されたか否かを判断する結果判断モジュールをさらに有することを特徴とする請求項１乃至８のいずれか１項に記載の装置（２００、３０２）。
【請求項１０】
少なくとも前記装置（２００、３０２）の現在位置を含む現在位置情報を判断する位置情報判断部（３２４）をさらに有し、
前記結果判断モジュールは、
前記位置情報に基づいて、潜在位置に到達しているかを判断し、
前記装置（２００、３０２）が提供される乗物が駐車しているかを判断し、
前記潜在位置に到達しており、かつ前記乗物が駐車していると判断した場合に、前記潜在位置において前記予め定められた種類のロケーションが発見されたことを示し、
前記潜在位置に到達しており、かつ前記乗物が駐車していないと判断した場合に、前記予め定められた種類のロケーションが見つからなかったことを示す
ように構成される
ことを特徴とする請求項４を直接あるいは間接的に引用する請求項９に記載の装置（２００、３０２）。
【請求項１１】
前記装置（２００、３０２）は、特定の潜在位置において前記予め定められた種類のロケーションが発見されたことを示した後、前記乗物が前記特定の潜在位置を出発したか否かを判断し、前記乗物が前記特定の潜在位置を出発したと判断した場合に、
前記特定の潜在位置から出発していることをサーバ（３０２）に通信する、
前記特定の潜在位置から出発していることを他の経路計画装置（２００）に通信する、及び
前記確率情報に代えて一時的に使用される一時的な確率情報を設定または更新する
の少なくともいずれかを実行する
ことを特徴とする請求項１０に記載の装置（２００、３０２）。
【請求項１２】
前記結果判断モジュールの判断をサーバ（３０２）に通信する、
前記結果判断モジュールの判断を他の経路計画装置（２００）に通信する、
前記結果判断モジュールの判断に基づいて前記確率情報を更新する、及び
前記結果判断モジュールの判断に基づき、前記確率情報に代えて一時的に使用される一時的な確率情報を設定または更新する
の少なくともいずれかを実行する更新部をさらに有する
ことを特徴とする請求項２を直接あるいは間接的に引用する請求項９乃至１１のいずれか１項に記載の装置（２００、３０２）。
【請求項１３】
請求項１乃至５のいずれか１項に記載の前記装置と、
ネットワーク（３１８）を介して、遠隔装置（２００）からの探索経路要求を受信する受信部（３１０）と、
前記ネットワーク（３１８）を介して、前記探索経路モジュール（４９０）により決定された前記探索経路を送信する送信部（３０６）と、を有する
ことを特徴とするサーバ（３０２）。
【請求項１４】
更新部をさらに有し、
前記受信部（３１０）は、前記遠隔装置（２００）からの結果情報を受信するように構成され、
前記更新部は、前記結果情報に基づいて地図情報を調整するように構成される
ことを特徴とする請求項１３に記載のサーバ。
【請求項１５】
コンピュータにおいて実行される探索経路の提供方法であって、
予め定められた種類のロケーションへの探索経路を提供する要求を受信し、
地図情報から、前記予め定められた種類のロケーションが潜在的に発見されうる位置に各々対応する複数の潜在位置を示し、
前記予め定められた種類のロケーションの発見可能性に基づく予め定められた効率尺度を用いて、少なくとも１つの前記潜在位置を訪れる経路を決定し、
前記決定した経路を前記探索経路として出力する
ことを特徴とする方法。
【国際調査報告】
2013533964.tif 000029
2013533964.tif 000030
2013533964.tif 000031