ナビゲーション装置および方法
位置センサから信号を受信する受信機と、シード位置とエリア内でナビゲート可能なルートのマップとを備えるマップデータを内部に格納したメモリと、現在位置を出力する、ディスプレイまたはスピーカ等の出力装置とを備えるナビゲーション装置。前記ナビゲーション装置は、前記信号から移動距離および方位変化を判定する工程および前記マップデータの前記ナビゲート可能なルートの一つにおける前記現在位置を推定する工程のためのプロセッサと、をさらに備える。前記推定する工程は、前記移動距離および前記方位変化を使用して、前記ナビゲーション装置が移動していたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、前記ナビゲーション装置が当該経路を移動した確率を各経路に割り当てることを含む。方位変化について、前記プロセッサは、各経路を拡張し、前記ナビゲーション装置が当該経路を移動した確率を再計算する。前記プロセッサは、前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置およびナビゲーション装置のための方法に関する。本発明の例示的な実施形態は、ポータブルナビゲーション装置（いわゆるＰＮＤ）に関し、特に全地球測位システム（ＧＮＳＳ）信号の受信処理機能を含むＰＮＤに関する。他の実施形態は、より一般的に、ルートプランニング、および好適にはナビゲーション機能を提供するためにナビゲーションソフトウェアを実行するように構成された任意のタイプの処理装置に関する。
【背景技術】
【０００２】
ＧＮＳＳ信号の受信処理機能を含むポータブルナビゲーション装置（ＰＮＤ）がよく知られており、車載あるいは他の乗り物のナビゲーションシステムとして広く用いられている。
【０００３】
一般的には、現在のＰＮＤは、プロセッサ、メモリ（揮発性、不揮発性、通常は両者の少なくとも１つ）、そのメモリに格納されたマップデータを備えている。プロセッサおよびメモリは、協働して、ソフトウェア・オペレーティングシステムが構築されてもよい実行環境を提供し、さらには１以上の追加ソフトウェアプログラムが、ＰＮＤの機能が制御されるのを可能にするために、および他の機能を提供するのを可能にするために提供されることが通常である。
【０００４】
典型的には、これらの装置は、ユーザが装置と情報をやり取りして装置を制御するのを可能にする１以上の入力インタフェース、および情報がユーザに伝達されてもよい１以上の出力インタフェースを備える。出力インタフェースの実例はビジュアルディスプレイおよび可聴出力のためのスピーカを含む。入力インタフェースの実例は、装置のオン／オフ動作または他の特徴を制御するための１以上の物理ボタン（装置が乗り物に内蔵されている場合、そのボタンは必ずしも装置自体の上にある必要はなくハンドル上にありうる）、およびユーザの発話を検出するマイクロホンを含む。特に好適な構成では、出力インタフェースディスプレイは、（タッチセンサオーバーレイまたは他の方法で）タッチセンサディスプレイとして、ユーザがタッチによって装置を動作しうる入力インタフェースを追加的に提供するように構成されてもよい。
【０００５】
このタイプの装置は、電力および選択的なデータ信号が、装置へ送信され、および当該装置から受信されうる１以上の物理コネクタインタフェース、および、選択的には、セルラ通信および他の信号データネットワーク、例えばＷｉ−Ｆｉ、Ｗｉ−Ｍａｘ、ＧＳＭ（登録商標）、ＣＤＭＡ等、を通じた通信を可能にする１以上の無線送受信機もしばしば含むだろう。
【０００６】
このタイプのＰＮＤ装置は、位置決めデータを含む衛星ブロードキャスト信号が受信されて、装置の現在位置を判定するために次に処理されうるＧＮＳＳアンテナも含む。
【０００７】
ＰＮＤ装置は、現在の角加速度および直線加速度を判定するために、次に、ＧＮＳＳ信号から取得される位置情報と併せて、速度、および、装置と当該装置が取り付けられた乗り物との相対移動（変位）を判定するために、処理されうる信号を生成する電子ジャイロスコープおよび加速度計も含んでもよい。典型的にはそのような特徴は、車載ナビゲーションシステムに通常提供されているが、そのようにするのが好都合であるならＰＮＤ装置にも提供されてもよい。
【０００８】
そのようなＰＮＤの有用性は、第１の位置（典型的には出発位置または現在位置）と第２の位置（典型的には目的地）との間のルートを判定する機能に主に現れる。これらの位置は任意の様々な異なる方法、例えば郵便番号、ストリート名称、番地、従前に格納された（有名な位置、（スポーツグラウンドまたは室内プール等の）地方自治体の位置、または他の着目地点等の）“よく知られた”目的地、およびお気に入りの目的地あるいは最近訪れた目的地によって、装置のユーザによって入力されうる。
【０００９】
典型的には、ＰＮＤは、マップデータから出発地住所位置と目的地住所位置との間の“最良の”または“最適な”ルートを計算するソフトウェアによって可能になる。“最良の”または“最適な”ルートは所定の基準に基づいて判定され、必ずしも最速ルートまたは最短ルートである必要はない。ドライバーをガイドするルートの選択は非常に高機能でありえ、選択されるルートは、現存する、予測される、および動的におよび／または無線で受信される交通道路情報、道路スピードの履歴情報、および道路の選択を判定する要因についてのドライバー自身の嗜好（例えば、ドライバーはルートが高速道路または有料道路を含まないように特定するかもしれない）を考慮してもよい。
【００１０】
さらに、装置は道路状況および交通状況を継続的に監視してもよく、旅の残りが変更された状況によってなされるようにルート変更を申し出または選択してもよい。様々な科学技術（例えば、携帯電話データ交換、固定カメラ、ＧＰＳフリートトラッキング（ＧＰＳ車両追跡））に基づくリアルタイム交通監視システムが、交通遅延を特定して、情報を通知システムへ供給するために使用されている。
【００１１】
このタイプのＰＮＤは、典型的には乗り物のダッシュボードまたはフロントガラスに取り付けられてもよいが、乗り物ラジオのオンボードコンピュータの一部として、あるいは実際には乗り物自体の制御システムの一部として形成されてもよい。ナビゲーション装置は、ＰＤＡ（携帯情報端末）、メディアプレーヤ、携帯電話等のハンドヘルドシステムの一部であってもよく、これらの場合、ハンドヘルドシステムの通常の機能は、ルート計算および計算されたルートに沿ったナビゲーションの両方を実行するソフトウェアの装置へのインストールによって拡張される。
【００１２】
ルートプランニングおよびナビゲーション機能は、適切なデスクトップまたはモバイルコンピューティング・リソース・実行ソフトウェアによって提供されてもよい。例えば、ロイヤル・オートモービル・クラブ（ＲＡＣ）は、http:/www.rac.co.ukにおいてオンラインでのルートプランニングおよびナビゲーション設備を提供しており、その設備はユーザが出発地点および目的地を入力するのを可能にし、そしてユーザのＰＣが接続されるサーバがルートを計算し（その側面はユーザにより特定されてもよい）、マップを生成し、選択された出発地点から選択された目的地へユーザをガイドする一連の包括的ナビゲーション命令を生成する。その設備は、計算されたルートの疑似三次元レンダリングや、ルートに沿ってユーザが移動するのをシミュレーションし、それによって、計算されたルートのプレビューをユーザへ提供するルートプレビュー機能も提供する。
【００１３】
ＰＮＤに関連して、ひとたびルートが計算されると、ユーザはナビゲーション装置と情報をやり取りして、提案されたルートのリストから任意に所望の計算されたルートを選択する。選択的に、ユーザは、例えば、あるルート、道路、位置または基準が回避されるべきこと、あるいは特定の旅に対しては義務的であることを特定することによって、ルート選択プロセスに干渉したり、ガイドしたりしてもよい。ＰＮＤのルート計算側面は一つの主要な機能を形成し、そのようなルートに沿ったナビゲーションは別の主要な機能である。
【００１４】
計算されたルートに沿ったナビゲーションの間、選択ルートに沿ってそのルートの終わり、すなわち所望の目的地までユーザをガイドする視覚的および／または可聴的な命令を提供することがそのようなＰＮＤにとって通常である。ナビゲーションの間画面上にマップ情報を表示することもそのようなＰＮＤにとって通常であり、表示されるマップ情報が、装置の、ひいてはユーザの、あるいは装置が車載ナビゲーションに使用されているならユーザの乗り物の現在位置を表すように、そのような情報は定期的に画面上で更新される。
【００１５】
画面上に表示されるアイコンは、典型的には装置の現在位置を示しており、ＧＮＳＳ受信機を使用してＰＮＤによって判定された、装置の現在位置の近くの現在の道路および周囲の道路のマップ情報とともに置かれ、および他のマップ特徴も表示される。さらには、表示されたマップ情報の上下左右のステータスバーに選択的にナビゲーション情報が表示されてもよく、ナビゲーション情報の例は、ユーザによって取られることが要求される現在の道路からの次の逸脱までの距離を含んでおり、その逸脱の性質は場合によっては例えば左折または右折等の特定のタイプの逸脱を示唆するさらなるアイコンによって表される。ナビゲーション機能は、ユーザがルートに沿ってガイドされうる可聴命令の内容、期間およびタイミングも判定する。理解されるように、“１００ｍで左折”等のシンプルな命令も十分な処理および解析を必要とする。前述したように、装置とのユーザの情報のやり取りはタッチスクリーンによってもよく、あるいは追加的にまたは代替的に、ステアリングコラム取り付け遠隔制御によって、音声起動によって、あるいは任意の他の適した方法によってもよい。
【００１６】
装置によって提供されるさらなる重要な機能は、ユーザが（偶然または故意の何れかによって）ナビゲーション中に従前に計算されたルートから逸脱する、代替ルートがより好都合であるとリアルタイム交通状況が決定づけ、装置がそのような状況を自動的に認識することが適切に可能である、あるいは、任意の理由でユーザが積極的に装置にルート再計算を実行させる、場合における自動ルート再計算である。
【００１７】
ユーザが定義した基準でルートが計算されるのを可能にすることも知られている。例えば、ユーザは景色の良いルートが装置により計算されることを好んでもよく、交通渋滞が起こりそうな、予期される、あるいは現在起こっている道路を回避することを望んでもよい。装置のソフトウェアは、その場合様々なルートを計算し、ルートに沿った景色の美しい例としてタグ付けられた最多数の（ＰＯＩとして知られる）着目地点を含む、より好ましいルートに重み付けし、または、特定の道路における現在の交通状況を示す格納された情報を使用して、起こりそうな渋滞または渋滞による遅延のレベルの観点で、計算されたルートを順序付けるだろう。他のＰＯＩベースおよび交通情報ベースのルート計算およびナビゲーション基準も可能である。
【００１８】
ルート計算およびナビゲーション機能はＰＮＤ全体の有用性に欠かせないけれども、純粋に情報表示のために、すなわち装置の現在位置と関連するマップ情報のみが表示され、ルートが計算されておらず、装置によってナビゲーションが現在実行されていない“フリードライビング”のために装置を使用することが可能である。そのような動作モードは、ユーザが移動することを望むルートを既に知っており、ナビゲーション補助を必要としない場合に、しばしば適用可能である。
【００１９】
上述したタイプの装置、例えばトムトムインターナショナル・ベステーロン・フエンノートシャップによって製造および供給される７２０Ｔモデルは、一つの位置から別の位置へユーザをナビゲートするのを可能にする信頼性のある手段を提供する。
【００２０】
時にはナビゲーションの間、現在位置を判定するためにナビゲーション装置によって使用されるＧＰＳ信号が利用不可能になるかもしれない。そのような場合、ＧＰＳを介して取得された位置の、表示マップ上の位置とのマッチングはもはや可能ではない。
【００２１】
デッドレコニング（dead reckoning）を使用してＧＰＳカバレッジの間隙の間に位置推定を提供し、この問題を解決することが知られている。デッドレコニングの１つの既知の方法は、ジャイロスコープや加速度計等の移動センサから取得される、乗り物が移動する角度および距離の変化に基づいて、既知の位置（位置情報）から乗り物が移動する経路を推定することである。この推定経路は、次に、道路ネットワークのマップ等のマップデータにマッチングされる。
【００２２】
そのような技術の問題は、位置センサによってなされる測定での誤差が、誤った経路が推定される結果をもたらしうることである。乗り物の回転速度計（タコメータ）から位置データを取得する内蔵式ナビゲーション装置について、特に、位置データの変化率を測定するセンサ（種々のセンサ）からの複数の信号を積分することによって位置データが取得される場合に、これらの誤差はかなり大きくなりうる。例えば、測定された加速度の二重積分を通じて加速度計から距離を取得する。位置データは測定値の積分を通じて取得されるので、測定値の誤差の小さな線形増加は、その測定値から取得される位置データの誤差の大きな非線形増加をもたらす。これらの大きな誤差は、位置推定において大きな誤差をもたらし、および結果として乗り物の経路／位置のマップ上での誤表示をもたらしうる。
【発明の概要】
【００２３】
本発明の第1の側面によれば、位置センサから信号を受信する受信機と、シード位置とエリア内でナビゲート可能なルートのマップとを備えるマップデータを内部に格納したメモリと、現在位置を出力する出力装置と、前記信号から移動距離および方位変化を判定する工程および前記マップデータの前記ナビゲート可能なルートの一つにおける前記現在位置を推定する工程のためのプロセッサと、を備えるナビゲーション装置であって、前記推定する工程は、
前記移動距離および前記方位変化を使用して、前記ナビゲーション装置が移動していたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、前記ナビゲーション装置が当該経路を移動した確率を各経路に割り当て、
方位変化について、各経路を拡張し、前記ナビゲーション装置が当該経路を移動した確率を再計算し、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる
ことを含むことを特徴とする。
【００２４】
本発明のナビゲーション装置は、センサから受信する信号に基づく位置データ（距離および方向）における誤差のせいでマップにおける現在位置が不正確になるなら、さらなる位置データおよびこのさらなる位置データのマップデータとのマッチングに基づいて、この誤差は後に補正されるかもしれないという有利な点を有するかもしれない。例えば、初期に可能性のある経路は、位置データの内在誤差のために高い確率を有するかもしれないが、さらなる位置データが受信されるにつれて、この経路の確率は、別の経路が最も可能性の高い移動経路になるほどまで低減するかもしれず、ナビゲーション装置が現在位置を今のところより可能性の高い経路上の位置に変更するかもしれない。決定地点（交差点または経路のルート関節）を通過しても他の可能性のある経路を判定することがない従来の装置では、この“回帰（regression）”は可能ではない。
【００２５】
各経路がナビゲーション装置が移動した経路である確率は、方位変化と、前記経路のナビゲート可能なルートの対応する角度変化とを比較することによって判定されてもよい。例えば、方位変化は、２つのナビゲート可能なルートの交差点またはナビゲート可能なルート自体のカーブにおけるターンの結果であってもよい。特定の一連の方位変化が、経路を形成する、例えば道路セグメント等の、特定のナビゲート可能なルートに沿った移動に対応する確率を判定することによって、経路の確率が判定されてもよい。例えば、経路の確率は、経路を構成する各ナビゲート可能なルートの別個の確率を判定して、これらの確率を共に乗じたり足し合わせたりすることによって計算されてもよい。ルートは１以上の経路と関連付けられることができ、ルートはそれと関連付けられた複数の確率、各経路に対する確率、を有してもよい。
【００２６】
方位変化は、所定の角度閾値を超える単位時間当たりの、例えば１秒当たり数度を超えての、角度変化が検出されてから、単位時間当たりの角度変化が再び安定し前記所定の閾値より少なくなるまでの、離散的イベントであってもよい。このようにして、拡張および確率の再計算は操作の完了に応じて実行され、より連続的なプロセスと比較して処理量を低減する。
【００２７】
前記現在位置を推定する工程は、各経路を拡張し、距離変化について前記ナビゲーション装置が当該経路を移動した前記確率を再計算することをさらに含む。方位変化と同様に、経路の拡張および確率の再計算が実行される地点における距離変化は、所定の距離閾値、例えば数十メートル、数百メートル、を超える距離変化であってもよい。
【００２８】
前記プロセッサは、前記ナビゲーション装置が当該経路を移動した前記確率が所定の確率閾値を下回る場合に、さらなる拡張および計算から経路を破棄するように構成されてもよい。
【００２９】
例えば、経路が破棄される前記確率閾値は、前記経路がＮ個の最も可能性のある経路の１つでない場合である。Ｎの値が大きいほど、プロセッサは各方位変化／方向変化についてより多くの処理を実行しなければならないだろうが、ナビゲーション装置によって移動される最も可能性の高い経路に後になるかもしれない経路が破棄される可能性はより低くなる。多くの状況において、２つの最も可能性の高い経路を除いて破棄することは、もし誤った経路が初期に最も可能性の高い経路として識別されているなら、正確な経路を後に見つけるのに十分ロバストである。
【００３０】
追加的にあるいは代替的に、経路が破棄される確率閾値は設定数であってもよい。例えば、経路の確率が設定数を下回る場合に経路が破棄され、または、経路の確率の、現在のところ最も可能性の高い経路である経路の確率に対する比が、設定された比よりも小さい場合に経路が破棄される。
【００３１】
前記プロセッサは、前記経路の拡張数が所定の拡張閾値を超える場合に、さらなる拡張および計算から前記最高確率を有する経路でない各経路を破棄するように構成されてもよい。同様に、適切な拡張閾値を設定することは、受容可能なレベルに必要な処理量を維持するのに使用されうる。拡張閾値は、２、３、４または５個の拡張等の数個の拡張であってもよい。
【００３２】
経路の拡張の間、経路が分岐するシード地点が作成されるだろう（従って２以上の経路を形成する）。初期のシード地点は２以上の経路が作成される第１のシード地点である。もし経路が無視されるなら、初期のシード地点は新しい位置へ移動することになるかもしれない。前記プロセッサは、初期のシード地点の前にあるルートの経路確率への寄与を無視するように構成されてもよい。このようにして、プロセッサは不必要な計算を実行せず、または大容量データを不必要に格納しない。
【００３３】
前記プロセッサは、（他の経路が破棄され、または他の可能性のある経路が存在しない、という結果として）単一の可能性のある経路しか存在しない場合に、メモリにおける前記シード位置を前記現在位置に設定し、および／または、シード地点に設定するように構成されてもよい。
【００３４】
前記位置センサは、加速度、速度、距離、時間および角度変化のうち少なくとも１つを測定するセンサを備えてもよい。一実施形態において、前記位置センサは、加速度計とジャイロスコープとの少なくとも何れか１つを備えてもよい。ナビゲーション装置が位置センサを備えてもよく、または、ナビゲーション装置は位置センサと接続する入力部を備えてもよい。
【００３５】
前記出力装置は、ディスプレイとスピーカとの少なくとも何れか１つであってもよい。
【００３６】
ナビゲーション装置は、全地球測位システム（ＧＮＳＳ）受信機またはＧＮＳＳ受信機と接続された入力部を備えてもよく、プロセッサは、ＧＮＳＳ信号が利用可能である場合にはＧＮＳＳ受信機によって受信される信号から現在位置を推定し、ＧＮＳＳ信号が利用不可能である場合には上述した工程に従って現在位置を推定するように構成される。このようにして、ナビゲーション装置は、ＧＮＳＳ信号が受信されない場合であっても継続して位置を追跡することができる。
【００３７】
本発明の第２の側面によれば、シード位置とエリア内でナビゲート可能なルートのマップとを備えるマップデータを内部に格納したメモリと接続されたプロセッサによって実行される場合に、前記プロセッサに、移動距離および方位変化に関する位置データを受信させ、前記位置データからマップデータの複数のナビゲート可能なルートの１つにおける現在位置を推定させ、出力装置に現在位置を出力させる命令を格納したデータキャリアであって、前記推定する工程は、
前記移動距離および前記方位変化を使用して、前記ナビゲーション装置が移動していたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、前記ナビゲーション装置が当該経路を移動した確率を各経路に割り当て、
方位変化について、各経路を拡張し、前記ナビゲーション装置が当該経路を移動した確率を再計算し、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる
ことを含むことを特徴とするデータキャリアが提供される。
【００３８】
本発明の第３の側面によれば、位置データを使用してナビゲート可能なルートのマップにおける現在位置を推定する方法であって、前記方法は、
前記位置データから移動距離および方位変化を判定する工程と、
前記移動距離および前記方位変化を使用して、前記移動されていたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、当該経路が移動された確率を各経路に割り当てる工程と、
方位変化について、各経路を拡張し、ナビゲーション装置が当該経路を移動した確率を再計算する工程と、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる工程と、
を有することを特徴とする方法が提供される。
【図面の簡単な説明】
【００３９】
本発明の教示の様々な側面、およびこれらの教示を具体化する構成が、添付の図面を参照して実例によって以下説明されるだろう。
【図１】図１は、全地球測位システム（ＧＮＳＳ）と通信するナビゲーション装置の概略図である。
【図２】図２は、本発明の第１実施形態に従ったナビゲーション装置を提供するように構成された電子構成要素の概略図である。
【図３】図３は、ナビゲーション装置が無線通信チャネルを通じてサーバから情報を受信してもよい方法の概略図である。
【図４Ａ】、
【図４Ｂ】図４Ａおよび図４Ｂは、ナビゲーション装置の例示的斜視図である。
【図５Ａ】、
【図５Ｂ】図５は、本発明の実施形態に従ったナビゲーション装置によって実行される方法を示す。
【図６】図６は、本発明の実施形態に従ってナビゲーション装置によって計算されうる多くの可能性のある経路の例である。
【発明を実施するための形態】
【００４０】
本発明の好適な実施形態が、特にＰＮＤを参照して説明されるだろう。しかしながら、本発明の教示はＰＮＤに限定されず、現在位置をマップに位置付ける他のタイプのナビゲーション装置に広く適用可能であることに留意されたい。それ故、本願に関連して、ナビゲーション装置は、その装置が、ＰＮＤ、乗り物に内蔵されるナビゲーション装置、あるいは実際ルートプランニングおよびナビゲーションソフトウェアを実行する（デスクトップまたはポータブル・パーソナル・コンピュータ（ＰＣ）、携帯電話、携帯情報端末（ＰＤＡ）等の）コンピュータ資源、として具体化されるかどうかに関わらず、（制限なく）ナビゲーション装置を含むことが意図される。
【００４１】
上記の条件を考慮して、図１は、ナビゲーション装置１４０によって使用可能な、全地球測位システム（ＧＮＳＳ）１００の例示を説明する。一般に、ＧＮＳＳは、連続的な位置、速度、時間および場合によっては方向情報を判定することができる衛星無線ベースのナビゲーションシステムである。ＧＮＳＳは、地球１２４の軌道上に複数の衛星１２０を備えている。各衛星１２０の軌道は、他の衛星１２０の軌道と必ずしも同期しておらず、実際恐らく非同期である。ＧＮＳＳ衛星は、信号１６０を介して受信ユニット１４０へ自身の位置を中継する。ＧＮＳＳ受信機１４０は、スペクトラム拡散ＧＮＳＳ衛星信号１６０を受信し、衛星によって中継された位置情報からその位置を判定する。
【００４２】
本発明のナビゲーション装置は、ＮＡＶＳＴＡＲ、Ｇａｌｉｌｅｏ、ＧＬＯＳＮＡＳＳまたは任意の他の適切なGNSSとしてかつて知られているＧＰＳを使用してもよい。ＧＮＳＳは非常に性格な軌道で地球を周回する複数の衛星１２０を組み込んでいる。
【００４３】
各衛星１２０から継続して送信される、スペクトラム拡散信号１６０は、極めて正確な原子時計により達成される極めて正確な周波数標準を利用する。各衛星１２０は、そのデータ信号送信１６０の一部として、その特定の衛星１２０を示すデータストリームを送信する。ＧＮＳＳ受信機装置１４０は一般に、少なくとも３つの衛星１２０からスペクトラム拡散ＧＮＳＳ衛星信号１６０をＧＮＳＳ受信機装置１４０について取得して三角測量によってその二次元位置を計算することが、関連技術の当業者によって理解される。全部で４つの衛星１２０からの信号１６０をもたらす、追加信号の取得は、ＧＮＳＳ受信機装置１４０が既知の方法でその三次元位置を計算するのを可能にする。
【００４４】
ＧＮＳＳシステムは、特にＧＮＳＳデータを受信する設備が整った装置が、ＧＮＳＳ衛星信号の無線周波数をスキャンし始める場合に実施される。ＧＮＳＳ衛星から無線信号を受信すると、装置は、複数の異なる従来の方法の１つを介してその衛星の正確な位置を判定する。装置は、大抵の場合、少なくとも３つの異なる衛星信号を取得するまで、信号のスキャンを継続するだろう（位置は、通常はそうではないが、他の三角測量技術を使用して２つの信号のみで判定されうることに留意されたい）。幾何学的三角測量を実施すると、受信機は、３つの既知の位置を利用して、衛星と比較した自身の二次元位置を判定する。これは既知の方法でなされうる。さらに、第４の衛星信号を取得することにより、受信装置がその三次元位置を計算することが、既知の方法での同じ幾何学的計算によって可能になるだろう。位置および速度データは、無限のユーザによって常にリアルタイムに更新されうる。
【００４５】
図２は、本発明の好適な実施形態に従ったナビゲーション装置２００の電子構成要素の、ブロック構成形式での代表図である。ナビゲーション装置２００のブロック図は、ナビゲーション装置の全ての構成要素を含んでおらず、多くの例示的構成要素の代表のみであることに留意されたい。
【００４６】
ナビゲーション装置２００の電子的構成要素は、図４Ａおよび図４Ｂに示されるような筐体内に位置している。ナビゲーション装置は、入力装置２２０と接続された処理装置２１０、および処理装置２１０と接続されたバックライトドライバ２４１を備える、ディスプレイスクリーン、本実施形態ではＬＣＤ２４０、を含む。入力装置２２０は、キーボード装置、音声入力装置、タッチパネルおよび／または情報を入力するために利用される任意の他の既知の入力装置を含み、ディスプレイスクリーン２４０は、例えばＬＣＤディスプレイ等の任意のタイプのディスプレイスクリーンを含みうる。この構成では、入力装置２２０およびディスプレイスクリーン２４０は、複数のディスプレイ選択の１つを選択するために、または、複数の仮想ボタンの１つを起動するために、ディスプレイスクリーン２４０の一部をユーザがタッチすることのみが必要であるように、タッチパッドまたはタッチスクリーン入力を含む一体型入力表示装置に統合されている。
【００４７】
ナビゲーション装置は、例えばスピーカ２６１、音声増幅器２６２、および音声コーデック２６０等の、出力装置２６０−２６２を含んでもよい。音声装置２６０−２６２は、判定されたナビゲート可能なルートに従ってユーザを指示する音声命令を生成しうる。
【００４８】
ナビゲーション装置２００において、処理装置２１０は、接続２２５を介して入力装置２２０と動作可能に接続されて、当該入力装置２２０から入力情報を受信するように設定されており、および、出力接続２４５および２４６を介してディスプレイスクリーン２４０および出力装置２６０のうち少なくとも１つと動作可能に接続され、そこへ現在位置を含む情報を出力する。さらに、処理装置２１０は接続２３５を介してメモリ資源２３０と連結される。メモリ資源２３０は、例えばランダムアクセスメモリ（ＲＡＭ）等の揮発性メモリ、および、例えばフラッシュメモリ等のデジタルメモリである不揮発性メモリを備える。メモリ資源は、エリア内のナビゲート可能なルートのマップ、例えば、イギリスまたはオランダ等の国におけるナビゲート可能なルートのマップを備えるマップデータを内部に格納している。この実施形態においては、マップデータの各ルートは、各セグメントと関連付けられた例えば速度制限、交通プロファイル（traffic profile）、他の道路規制等の、そのセグメントの属性を規定したデータを含む各セグメントで分けられている。
【００４９】
ナビゲーション装置２００は、セルラネットワークの基地局から、ＢＣＣＨ等の、ブロードキャスト信号を受信する、携帯電話等のセルラモデム２８０と取り外し可能に接続する接続２７０をさらに備える。接続２７０は、ナビゲーション装置２００と例えばインターネットまたは任意の他のネットワークとの間のデータ接続を確立するために、および／または、例えばインターネットまたはいくつかの他のネットワークを介してサーバへの接続を確立するために、使用されてもよい。別の実施形態において、装置２８０はテレビジョン受信機またはＴＭＳ／ＲＤＳ情報を受信しうる無線受信機であってもよい。
【００５０】
図２は、接続２５５を介して、処理装置２１０と、ＧＮＳＳアンテナ２５０と、受信機２５１との間の動作可能な接続をさらに説明する。アンテナは例えばＧＮＳＳパッチアンテナまたはヘリカルアンテナであってもよい。
【００５１】
さらに、図２に示される電子的構成要素は、電源２９０、この場合は従来のように電源管理集積回路２９０、によって動作されることが当業者によって理解されるだろう。
【００５２】
有線接続２７６、この実施形態ではＵＳＢ接続は、処理装置２１０をコンピュータ等と接続するために提供される。そのような接続はソフトウェア／ファームウェアの更新および／またはマップの更新のために使用されうる。
【００５３】
ナビゲーション装置２００は、位置センサ、この実施形態ではジャイロスコープ２９６および加速度計２９７、と接続するこの実施形態ではコネクタである受信機２９５を備えており、ＣＰＵ２１０はジャイロスコープ２９６および加速度計２９７から信号を受信することができる。
【００５４】
当業者によって理解されるように、図２に示される構成要素の異なる構成が、本願の範囲に含まれると考えられる。例えば、図２に示される構成要素は、有線接続および／または無線接続等を介して相互に通信してもよい。従って、本願のナビゲーション装置２００の範囲は、ポータブルまたはハンドヘルドナビゲーション装置２００を含む。
【００５５】
さらに、図２のポータブルまたはハンドヘルドナビゲーション装置２００は、例えば図５ａおよび図５ｂに示される取付装置２９２／２９４を使用することによって、自転車、バイク、自動車またはボート等の乗り物と、既知の方法で接続あるいは“ドッキング”されうる。そのようなナビゲーション装置２００は、ポータブルまたはハンドヘルドナビゲーション使用のためにドッキングされた位置から取り外し可能である。
【００５６】
次に図３を参照すると、ナビゲーション装置２００は、（例えば既知のＢｌｕｅｔｏｏｔｈ（登録商標）技術を介したデジタル接続等の）デジタル接続を構築するセルラモデム２８０を介してサーバ３０２との“モバイル”または通信ネットワーク接続を構築してもよい。その後、そのネットワークサービスプロバイダを通じて、セルラ装置はサーバ３０２と（例えばインターネットを通じて）ネットワーク接続を構築しうる。そのようにして、“リアルタイム”または少なくとも非常に“最新の”ゲートウェイに情報を提供するために、（単独および／または乗り物で移動するにつれて多くの場合動きうる）ナビゲーション装置２００とサーバ３０２との間に“モバイル”ネットワーク接続が構築される。
【００５７】
例えば（ワールド・ワイド・ウェブ等の）インターネットを使用して、（サービスプロバイダを介した）モバイル装置とサーバ３０２等の別の装置との間でのネットワーク接続を構築することは、既知の方法で行われうる。これは例えばＴＣＰ／ＩＰレイヤプロトコルの使用を含みうる。モバイル装置は、ＤＶＢ−Ｈ、ＤＶＢ−Ｔ、ＣＤＭＡ、ＧＳＭ、Ｗｉ−Ｍａｘ、ＴＭＣ／ＲＤＳ等の任意の数の通信標準を利用することができる。
【００５８】
そのようなものとして、例えば、携帯電話またはナビゲーション装置２００内の携帯電話技術を介した、データ接続を介して達成されるインターネット接続が利用されてもよい。この接続について、サーバ３０２とナビゲーション装置２００との間でインターネット接続が構築される。これは、例えば携帯電話または他のモバイル装置およびＧＰＲＳ（ジェネラル・パケット・ラジオ・サービス）接続を通じて実行されうる（ＧＰＲＳ接続は通信会社によって提供されるモバイル装置のための高速データ接続であり、ＧＰＲＳはインターネットと接続するための方法である）。
【００５９】
ナビゲーション装置２００はさらに、モバイル装置とのデータ接続、ひいては、既知の方法で、例えば既存のＢｌｕｅｔｏｏｔｈ（登録商標）技術を介して、インターネットおよびサーバ３０２との接続を完了することができ、ここでデータプロトコルは、例えばＧＳＲＭ、ＧＳＭ標準のためのデータプロトコル標準等の、任意の数の標準を利用することができる。
【００６０】
ＧＰＲＳ電話設定について、Ｂｌｕｅｔｏｏｔｈ（登録商標）可能なナビゲーション装置は、携帯電話モデル、製造業者等の絶え間なく変化しているスペクトルと正確に連動するように使用されてもよく、例えばモデル／製造業者に特有の設定がナビゲーション装置２００に格納されてもよい。この情報について格納されるデータは更新されうる。
【００６１】
図３において、ナビゲーション装置２００は、任意の多数の異なる構成によって実施されうる汎用通信チャネル３１８を介してサーバ３０２と通信しているものとして描写されている。サーバ３０２およびナビゲーション装置２００は、通信チャネル３１８を介してサーバ３０２とナビゲーション装置２００との間に接続が構築された場合に通信することができる（そのような接続は、モバイル装置を介したデータ接続、インターネットを介しパーソナル・コンピュータを通じた直接接続等でありうることに留意されたい）。
【００６２】
サーバ３０２は、説明されていない他の構成要素に加えて、メモリ３０６と動作可能に接続され、有線または無線接続３１４を介して大容量記憶装置３１２とさらに動作可能に接続された処理装置３０４を含む。処理装置３０４は、通信チャネル３１８を介してナビゲーション装置２００へ情報を送信および送出し、当該ナビゲーション装置２００から情報を受信するために、送信機３０８および受信機３１０と動作可能にさらに接続される。送受信される信号は、データ、通信、および／または他の伝播信号を含んでもよい。送信機３０８および受信機３１０は、ナビゲーションシステム２００のための通信設計で使用される通信要件および通信技術に従って選択または設計されてもよい。さらに、送信機３０８および受信機３１０の機能は単一の送受信機に一体化されてもよいことに留意されたい。
【００６３】
サーバ３０２は、大容量記憶装置３１２とさらに接続されており（あるいは大容量記憶装置３１２を含んでおり）、大容量記憶装置３１２は、通信リンク３１４を介してサーバ３０２と連結されてもよいことに留意されたい。大容量記憶装置３１２は、ナビゲーションデータおよびマップ情報の格納を含んでおり、サーバ３０２とは別個の装置でありえ、あるいは、サーバ３０２に組み込まれうる。
【００６４】
ナビゲーション装置２００は、通信チャネル３１８を通じてサーバ３０２と通信するように構成されており、図２および３に関して前に説明したように、通信チャネル３１８を通じて信号および／またはデータを送受信するための送信機３２０および受信機３２２だけでなく、処理装置、メモリ等を含み、これらの装置はサーバ３０２以外の装置と通信するためにさらに使用されうることに留意されたい。さらに、送信機３２０および受信機３２２は、ナビゲーションシステム２００のための通信設計で使用される通信要件および通信技術に従って選択または設計され、送信機３２０および受信機３２２の機能は単一の送受信機に一体化されてもよい。
【００６５】
サーバメモリ３０６に格納されたソフトウェアは、処理装置３０４に命令を提供し、サーバ３０２がナビゲーション装置２００へサービスを提供するのを可能にする。サーバ３０２によって提供される一つのサービスは、ナビゲーション装置２００からの要求を処理して、大容量記憶装置３１２からナビゲーション装置２００へナビゲーションデータを送信することを含む。サーバ３０２によって提供される別のサービスは、所望のアプリケーションの様々なアルゴリズムを使用してナビゲーションデータを処理して、これらの計算の結果をナビゲーション装置２００へ送信することを含む。
【００６６】
通信チャネル３１８は、一般に、ナビゲーション装置２００およびサーバ３０２を接続する伝播媒体または経路を表す。サーバ３０２およびナビゲーション装置２００は、通信チャネルを通じてデータを送信する送信機および通信チャネルを通じて送信されているデータを受信する受信機を含む。
【００６７】
通信チャネル３１８は、特定の通信技術に限定されない。さらに、通信チャネル３１８は、単一の通信技術に限定されない。すなわち、通信チャネル３１８は、様々な技術を使用するいくつかの通信リンクを含んでもよい。例えば、通信チャネル３１８は、電気的、光学的、および／または電磁気的な通信等の経路を提供するように構成されうる。そのようなものとして、通信チャネル３１８は、電気回路、有線同軸ケーブル等の導電体、光ファイバケーブル、コンバータ、無線周波数（ＲＦ）波、大気、空間等のうちの１つまたは組み合わせを含むがこれらに限定されない。
【００６８】
さらに、通信チャネル３１８は、例えばルータ、リピータ、バッファ、送信機、および受信機等の媒介装置を含みうる。
【００６９】
一つの例示的な構成において、通信チャネル３１８は、電話およびコンピュータネットワークを含む。さらに、通信チャネル３１８は、無線周波数、マイクロ波周波数、赤外線通信等の無線通信に適合可能であってもよい。さらに、通信チャネル３１８は、衛星通信に適合しうる。
【００７０】
通信チャネル３１８を通じて送信される通信信号は、所与の通信技術に必要とされる、あるいは望まれる信号を含むが、それらに限定されない。例えば、信号は、時分割多重アクセス（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）、符号分割多元接続（ＣＤＭＡ）、グローバル・システム・フォー・モバイル・コミュニケーションズ（ＧＳＭ）等のセルラ通信技術で使用されるように構成されてもよい。デジタル信号およびアナログ信号の両方が、通信チャネル３１８を通じて送信されうる。これらの信号は、変調され、暗号化され、および／または圧縮された、通信技術に望ましい信号であってもよい。
【００７１】
自動的またはユーザがサーバ３０２へナビゲーション装置２００を接続することに応じて定期的に更新されてもよく、および／または、例えばより定常的な接続またはより頻繁な接続が無線モバイル接続装置およびＴＣＰ／ＩＰ接続を介してサーバ３０２とナビゲーション装置２００との間でなされることに応じてより動的であってもよい、情報ダウンロードを介して、ナビゲーション装置２００はサーバ３０２から情報を提供されてもよい。多くの動的計算について、サーバ３０２における処理装置３０４は、処理ニーズの大部分を扱うために使用されてもよいが、しかしながら、ナビゲーション装置２００の処理装置２１０は、サーバ３０２との接続とはしばしば独立して、多くの処理および計算を扱うこともできる。
【００７２】
図４Ａおよび図４Ｂは、ナビゲーション装置２００の斜視図である。図４Ａに示されるように、ナビゲーション装置２００は、一体型入力表示装置２９０（例えばタッチパネルスクリーン）および（内部ＧＰＳ受信機２５０、処理装置２１０、電力供給、メモリシステム２３０等を含むがこれらに限定されない）図２および図３の他の構成要素を含むユニットであってもよい。
【００７３】
ナビゲーション装置２００は、吸着カップ２９４を使用して乗り物のダッシュボード／ウィンドウ等に固定されてもよいアーム２９２上に据え付いてもよい。このアーム２９２は、ナビゲーション装置２００がドッキングされうるドッキング・ステーションの一例である。
【００７４】
図４Ｂに示されるように、ナビゲーション装置２００は、例えばナビゲーション装置２００をアーム２９２とスナップ接続することによって、ドッキング・ステーションのアーム２９２とドッキングまたは別の方法で接続されうる。その場合ナビゲーション装置２００は、図４Ｂの矢印によって示されるように、アーム２９２上で回転可能であってもよい。ナビゲーション装置２００とドッキング・ステーションとの間の接続を解放するために、例えばナビゲーション装置２００上のボタンが押下されてもよい。ナビゲーション装置をドッキング・ステーションと連結およびドッキング・ステーションから分断するための他の同様な適切な構成が当業者に広く知られている。
【００７５】
このユーザがＰＮＤのスイッチを入れると、その装置は、ＧＮＳＳ ｆｉｘを取得し、（既知の方法で）ＰＮＤの現在位置を計算する。この現在位置を使用して、ＰＮＤは、従来のアルゴリズムに従ってナビゲート可能なルートを判定しうる。
【００７６】
次に図５を参照すると、メモリ資源２３０に格納されるのは、プロセッサ２１０によって実行される場合に、そのプロセッサに次に説明する方法のステップを実行させる命令を備えるコンピュータプログラムである。
【００７７】
ステップ４０１において、プロセッサ２１０は、ＧＮＳＳ信号がＧＮＳＳ受信機２５１によって受信されているかどうかを判定する。ＧＮＳＳ信号が受信されているなら、プロセッサ２１０は、ステップ４０２において、ＧＮＳＳ信号から、および選択的にはジャイロスコープ２９６および加速度計２９７から受信される信号からも、マップデータにおける現在位置を判定する。ＧＮＳＳ信号と併せてジャイロスコープ２９６および加速度計２９７からの信号を使用する利点は、より正確な位置が判定されることである。ＧＮＳＳ信号から判定される各新しい位置について、シード（seed）位置がこの新しい位置で更新される（ステップ４０３）。次に方法はステップ４０１へループして戻る。
【００７８】
ＧＮＳＳ受信機２５１が（例えばＧＮＳＳネットワークカバレッジが存在しないために）衛星１２０からＧＮＳＳ信号を受信していない場合、ステップ４０１において、方法はデッドレコニング技術の第１の部分としてステップ４０４へ進む。ステップ４０４において、プロセッサ２１０は、複数の可能性のある経路が、ジャイロスコープ２９６および加速度計２９７から受信された位置決めデータから判定された現在位置の従前の推定に基づいて、既に計算されているかどうかを判定確認する。ＧＮＳＳ信号がロストされたために、デッドレコニング技術によって位置が推定されるのが初めてであるなら、ナビゲーション装置が移動した可能性のある経路はまだ判定されていないだろう。従って、そのような状況においては、プロセッサはステップ４０５へ進み、最後の（最新の）シード位置が判定されたので、プロセッサはジャイロスコープ２９６および加速度計２９７から信号を受信し、その信号から、移動距離および方位変化（位置データ）を判定する。
【００７９】
プロセッサ２１０は、ステップ４０６において、メモリ資源２３０からシード位置を読み出し、移動距離および任意の方位変化を使用して、ナビゲーション装置２００によって移動される可能性のある経路をそのシード位置から推定する。この実施形態においては、プロセッサ２１０は、移動距離および／または方位変化が所定の閾値を超える場合に、可能性のある移動経路の第１の計算を実行する。各経路がナビゲーション装置２００が移動した経路である確率は、方位変化と、対応する経路のナビゲート可能なルートの角度変化とを比較することによって、判定されてもよい。例えば、方位変化は、２つのナビゲート可能なルートの交差点でなされるターンまたはナビゲート可能なルート自体のカーブの結果であってもよい。
【００８０】
このことが達成されうる１つの方法の例が、図６に関して次に説明されるだろう。点線５０１は、ジャイロスコープ２９６および加速度計２９７からの信号によって示される経路を示している。しかしながら、測定誤差のせいで、これは、マップデータのナビゲート可能なルート５０２−５０９と合致していない。従って、プロセッサ２１０は、方位変化および移動距離の測定値がマップデータのナビゲート可能なルート５０３−５０９の方位および距離の変化にどの程度近いかに基づいて、各ナビゲート可能なルート５０３−５０９が移動された確率を割り当てる。所与の例では、ナビゲーション装置が最初にわずかに左に移動するにつれて方位変化が生じると、第１の判定が実行される。左への移動は、ＢからＤへのルート５０４よりはＢからＣへのルート５０３に沿って移動することによりぴったりと合致するので、ルート５０３に沿ったこの最初の方位変化の経路には、ルート５０４に沿った経路よりも高い確率が与えられる。
【００８１】
各経路に割り当てられる確率は、経路を構成するルートの個々の確率の重み付けされた合計である（すなわち、全ての可能性のある経路を構成する全てのルートの確率全体によって除算された経路を構成するルートの確率の合計）。従って、まず第１に、経路を構成するルート５０３、５０４に確率が割り当てられ、次に、経路の確率がルートについて判定された確率から判定される。図６に示される例では、ＢからＤへの経路に割り当てられる確率はおよそ０．４８６であり、ＢからＣへの経路に割り当てられる確率はおよそ０．５１４である。ステップ４０７において、これらの確率が経路に割り当てられ、メモリ資源２３０に格納される。ある状況では、ルートは複数の経路に属することができ、それと関連付けられた複数の確率、ルートが属する各経路について１つの確率、を有することが理解されるだろう。
【００８２】
ステップ４０８において、プロセッサ２１０は、経路に割り当てられた確率を比較し、その確率が所定の閾値を下回るなら、その経路は破棄される。
【００８３】
例えば、経路が破棄される閾値は、Ｎ個の最も可能性の高い経路のうちの１つではない場合であってもよい。Ｎの値が大きいほど、プロセッサは、各方位変化／方向変化についてより多くの処理を実行しなければならないだろうが、後にナビゲーション装置によって移動される最も可能性の高い経路になるかもしれない経路が破棄される可能性はより低くなる。多くの状況において、誤った経路が初期に最も可能性の高い経路として特定されるなら、２つの最も可能性の高い経路以外を破棄することは、後に正確な経路を見つけるのに十分ロバストである。こうした要求の代わりとして、またはこうした要求に加えて、他の要求が使用されてもよく、例えば、プロセッサ２１０は、経路の拡張数が所定の拡張閾値を超える場合、さらなる拡張および計算から最も高い確率を有する経路ではない各経路を破棄するように構成されてもよく、および／または、ナビゲーション装置が経路を移動した確率が所定の閾値を下回る場合に当該経路が破棄されてもよいことが理解されるだろう。
【００８４】
従って、図６に示される例では、プロセッサ２１０が初期の方位変化から判定するルート５０２および５０３に沿った初期の２つの経路は、それらが２つの最も可能性の高い経路であって高い確率を有するので破棄されない。ステップ４０９において、プロセッサ２１０は、ナビゲーション装置２００の現在位置を、最も高い確率を有する経路上の位置になるように割り当てる。計算された初期の２つの経路について、これは、この経路が０．４８６に対して０．５１４というより高い確率を有するので、ルート５０３上で予測される位置であるだろう。この現在位置は、ナビゲーション装置によって、例えばディスプレイ２４０上のグラフィックとして次に出力される。
【００８５】
ステップ４１６において、プロセッサ２１０は、もはや関連しないルートを経路から取り除く。破棄されるルートは、経路が分岐する初期地点（初期シード地点）の前に生じるルートを含む。図６に示される例では、地点Ｂが初期シード地点であり、そのためルート５０２によって寄与される経路の確率に対する任意の寄与が除外される。
【００８６】
ステップ４１０において、プロセッサ２１０は、複数の経路が残っているかどうか判定確認し、複数の経路が存在するならプロセッサは、ステップ４０１へ戻る。結果として、プロセッサ２１０は、ＧＮＳＳ信号が受信されうるかどうか再び見て確認する。いまだにＧＮＳＳカバレッジが存在しないなら、ステップ４０４において、プロセッサ２１０は、複数の経路が残っているかどうか判定確認する。図６に示される例では、初期の方位変化の後に、２つの可能性のある経路が保持されている。従って、プロセッサ２１０は、ステップ４１２へ進む。ステップ４１２において、プロセッサは、ジャイロスコープ２９６および加速度計２９７から受信される信号から移動距離および方位変化を判定し、ステップ４１３において、プロセッサ２１０は、既に判定されている経路から拡張して、可能性のある経路の新しいセットを判定する。再び図６を参照すると、これは、例えばルート５０３が地点Ｃにおいてルート５０５へと左へ進むこと、およびルート５０４が地点Ｄにおいてルート５０６および５０７へ分岐すること等、移動距離のセットにおいて生じる予測交差のために、および／または、さらなる方位変化、図６において右への移動、のために、実行されてもよい。
【００８７】
以前のループと同様に、ステップ４０７において、経路の新しいセットの各可能性のある経路について確率が計算される。ルート５０５が移動されている可能性は非常に低く０．１であり、ＢからＥへの経路が、ナビゲーション装置が移動した経路である確率は、ルート５０３およびルート５０５がともに移動されている確率の重み付け合計（加重和）を実行することによって計算される。これは、およそ０．２６というこの経路の確率を与える。他の可能性のある経路は、（ルート５０４および５０６、および、ルート５０４および５０７をそれぞれ含む）ＢからＧおよびＢからＦであり、同様にしてこれらの経路について確率が計算され、それぞれ０．４５および０．２９を与える。ステップ４０８において、プロセッサ２１０は最も可能性の高い確率を有する２つの経路を保持するのみであるため、ルート５０３および５０５を含む経路が破棄される。ステップ４０９において、ナビゲーション装置２００によって出力される現在位置は、ルート５０４および５０６を含む経路上の予測位置へ変更される。複数の可能性のある経路が残っているので、プロセッサは、ステップ４１１へ進み、ステップ４０１へループして戻る。
【００８８】
ＢからＥまでの経路が破棄されているので、地点Ｂはもはやシード地点（経路が分岐する地点）ではない。新しい初期シード地点はＤである。ステップ４１６において、現在の新しい初期シード地点（地点Ｄ）の前に生じるルートの寄与は除外され、２つの経路ＤからＦおよびＤからＧについての確率はそれぞれおよそ０．３０８およびおよそ０．６９である。
【００８９】
このプロセスは、さらなる方位および距離の変化について次に繰り返され、経路が推定され、新しい経路が形成されて、これら新しい経路について確率が計算される。図６に示される例では、残っている経路は、新しい経路ＤからＨおよびＤからＩを与えるように推定され、経路ＤからＩはルート５０６および５０９を含み、経路ＤからＨはルート５０７および５０８を含み、０．８４および０．１６という確率を有する。ステップ４０８において、プロセッサ２１０は、この経路の確率は所定の閾値０．２を下回るので、ルート５０７および５０８を含む経路ＤからＨを破棄してもよい。従って、現在位置はＤからＩへの経路上の位置に割り当てられる。１つの経路のみ残っているので、プロセッサ２１０は、ステップ４１４へ進み、唯一残っている経路上における現在の予測位置でシード位置を更新し、次にステップ４０１へループして戻り、ＧＮＳＳ信号が受信されえない限りプロセスが再び開始される。
【００９０】
可能性のある経路の各推定／拡張は、方位および／または距離の変化が所定の閾値を超える場合、例えば、単位時間当たりの角度変化が所定の角度閾値、例えば１秒当たり数度、を超える、あるいは、距離変化が所定の距離閾値、例えば数十メートルまたは数百メートル、を超える場合にのみ実行されもよいことが理解されるだろう。
【００９１】
さらに、本発明のデッドレコニング技術は、例えば、サーバ３０２のプロセッサ３０４によるナビゲーション装置とは離れた別の処理装置によって実行されることができ、この処理によって判定される現在位置は、通信リンク３１８を通じてナビゲーション装置へ送信し返されることが理解されるだろう。
【技術分野】
【０００１】
本発明は、ナビゲーション装置およびナビゲーション装置のための方法に関する。本発明の例示的な実施形態は、ポータブルナビゲーション装置（いわゆるＰＮＤ）に関し、特に全地球測位システム（ＧＮＳＳ）信号の受信処理機能を含むＰＮＤに関する。他の実施形態は、より一般的に、ルートプランニング、および好適にはナビゲーション機能を提供するためにナビゲーションソフトウェアを実行するように構成された任意のタイプの処理装置に関する。
【背景技術】
【０００２】
ＧＮＳＳ信号の受信処理機能を含むポータブルナビゲーション装置（ＰＮＤ）がよく知られており、車載あるいは他の乗り物のナビゲーションシステムとして広く用いられている。
【０００３】
一般的には、現在のＰＮＤは、プロセッサ、メモリ（揮発性、不揮発性、通常は両者の少なくとも１つ）、そのメモリに格納されたマップデータを備えている。プロセッサおよびメモリは、協働して、ソフトウェア・オペレーティングシステムが構築されてもよい実行環境を提供し、さらには１以上の追加ソフトウェアプログラムが、ＰＮＤの機能が制御されるのを可能にするために、および他の機能を提供するのを可能にするために提供されることが通常である。
【０００４】
典型的には、これらの装置は、ユーザが装置と情報をやり取りして装置を制御するのを可能にする１以上の入力インタフェース、および情報がユーザに伝達されてもよい１以上の出力インタフェースを備える。出力インタフェースの実例はビジュアルディスプレイおよび可聴出力のためのスピーカを含む。入力インタフェースの実例は、装置のオン／オフ動作または他の特徴を制御するための１以上の物理ボタン（装置が乗り物に内蔵されている場合、そのボタンは必ずしも装置自体の上にある必要はなくハンドル上にありうる）、およびユーザの発話を検出するマイクロホンを含む。特に好適な構成では、出力インタフェースディスプレイは、（タッチセンサオーバーレイまたは他の方法で）タッチセンサディスプレイとして、ユーザがタッチによって装置を動作しうる入力インタフェースを追加的に提供するように構成されてもよい。
【０００５】
このタイプの装置は、電力および選択的なデータ信号が、装置へ送信され、および当該装置から受信されうる１以上の物理コネクタインタフェース、および、選択的には、セルラ通信および他の信号データネットワーク、例えばＷｉ−Ｆｉ、Ｗｉ−Ｍａｘ、ＧＳＭ（登録商標）、ＣＤＭＡ等、を通じた通信を可能にする１以上の無線送受信機もしばしば含むだろう。
【０００６】
このタイプのＰＮＤ装置は、位置決めデータを含む衛星ブロードキャスト信号が受信されて、装置の現在位置を判定するために次に処理されうるＧＮＳＳアンテナも含む。
【０００７】
ＰＮＤ装置は、現在の角加速度および直線加速度を判定するために、次に、ＧＮＳＳ信号から取得される位置情報と併せて、速度、および、装置と当該装置が取り付けられた乗り物との相対移動（変位）を判定するために、処理されうる信号を生成する電子ジャイロスコープおよび加速度計も含んでもよい。典型的にはそのような特徴は、車載ナビゲーションシステムに通常提供されているが、そのようにするのが好都合であるならＰＮＤ装置にも提供されてもよい。
【０００８】
そのようなＰＮＤの有用性は、第１の位置（典型的には出発位置または現在位置）と第２の位置（典型的には目的地）との間のルートを判定する機能に主に現れる。これらの位置は任意の様々な異なる方法、例えば郵便番号、ストリート名称、番地、従前に格納された（有名な位置、（スポーツグラウンドまたは室内プール等の）地方自治体の位置、または他の着目地点等の）“よく知られた”目的地、およびお気に入りの目的地あるいは最近訪れた目的地によって、装置のユーザによって入力されうる。
【０００９】
典型的には、ＰＮＤは、マップデータから出発地住所位置と目的地住所位置との間の“最良の”または“最適な”ルートを計算するソフトウェアによって可能になる。“最良の”または“最適な”ルートは所定の基準に基づいて判定され、必ずしも最速ルートまたは最短ルートである必要はない。ドライバーをガイドするルートの選択は非常に高機能でありえ、選択されるルートは、現存する、予測される、および動的におよび／または無線で受信される交通道路情報、道路スピードの履歴情報、および道路の選択を判定する要因についてのドライバー自身の嗜好（例えば、ドライバーはルートが高速道路または有料道路を含まないように特定するかもしれない）を考慮してもよい。
【００１０】
さらに、装置は道路状況および交通状況を継続的に監視してもよく、旅の残りが変更された状況によってなされるようにルート変更を申し出または選択してもよい。様々な科学技術（例えば、携帯電話データ交換、固定カメラ、ＧＰＳフリートトラッキング（ＧＰＳ車両追跡））に基づくリアルタイム交通監視システムが、交通遅延を特定して、情報を通知システムへ供給するために使用されている。
【００１１】
このタイプのＰＮＤは、典型的には乗り物のダッシュボードまたはフロントガラスに取り付けられてもよいが、乗り物ラジオのオンボードコンピュータの一部として、あるいは実際には乗り物自体の制御システムの一部として形成されてもよい。ナビゲーション装置は、ＰＤＡ（携帯情報端末）、メディアプレーヤ、携帯電話等のハンドヘルドシステムの一部であってもよく、これらの場合、ハンドヘルドシステムの通常の機能は、ルート計算および計算されたルートに沿ったナビゲーションの両方を実行するソフトウェアの装置へのインストールによって拡張される。
【００１２】
ルートプランニングおよびナビゲーション機能は、適切なデスクトップまたはモバイルコンピューティング・リソース・実行ソフトウェアによって提供されてもよい。例えば、ロイヤル・オートモービル・クラブ（ＲＡＣ）は、http:/www.rac.co.ukにおいてオンラインでのルートプランニングおよびナビゲーション設備を提供しており、その設備はユーザが出発地点および目的地を入力するのを可能にし、そしてユーザのＰＣが接続されるサーバがルートを計算し（その側面はユーザにより特定されてもよい）、マップを生成し、選択された出発地点から選択された目的地へユーザをガイドする一連の包括的ナビゲーション命令を生成する。その設備は、計算されたルートの疑似三次元レンダリングや、ルートに沿ってユーザが移動するのをシミュレーションし、それによって、計算されたルートのプレビューをユーザへ提供するルートプレビュー機能も提供する。
【００１３】
ＰＮＤに関連して、ひとたびルートが計算されると、ユーザはナビゲーション装置と情報をやり取りして、提案されたルートのリストから任意に所望の計算されたルートを選択する。選択的に、ユーザは、例えば、あるルート、道路、位置または基準が回避されるべきこと、あるいは特定の旅に対しては義務的であることを特定することによって、ルート選択プロセスに干渉したり、ガイドしたりしてもよい。ＰＮＤのルート計算側面は一つの主要な機能を形成し、そのようなルートに沿ったナビゲーションは別の主要な機能である。
【００１４】
計算されたルートに沿ったナビゲーションの間、選択ルートに沿ってそのルートの終わり、すなわち所望の目的地までユーザをガイドする視覚的および／または可聴的な命令を提供することがそのようなＰＮＤにとって通常である。ナビゲーションの間画面上にマップ情報を表示することもそのようなＰＮＤにとって通常であり、表示されるマップ情報が、装置の、ひいてはユーザの、あるいは装置が車載ナビゲーションに使用されているならユーザの乗り物の現在位置を表すように、そのような情報は定期的に画面上で更新される。
【００１５】
画面上に表示されるアイコンは、典型的には装置の現在位置を示しており、ＧＮＳＳ受信機を使用してＰＮＤによって判定された、装置の現在位置の近くの現在の道路および周囲の道路のマップ情報とともに置かれ、および他のマップ特徴も表示される。さらには、表示されたマップ情報の上下左右のステータスバーに選択的にナビゲーション情報が表示されてもよく、ナビゲーション情報の例は、ユーザによって取られることが要求される現在の道路からの次の逸脱までの距離を含んでおり、その逸脱の性質は場合によっては例えば左折または右折等の特定のタイプの逸脱を示唆するさらなるアイコンによって表される。ナビゲーション機能は、ユーザがルートに沿ってガイドされうる可聴命令の内容、期間およびタイミングも判定する。理解されるように、“１００ｍで左折”等のシンプルな命令も十分な処理および解析を必要とする。前述したように、装置とのユーザの情報のやり取りはタッチスクリーンによってもよく、あるいは追加的にまたは代替的に、ステアリングコラム取り付け遠隔制御によって、音声起動によって、あるいは任意の他の適した方法によってもよい。
【００１６】
装置によって提供されるさらなる重要な機能は、ユーザが（偶然または故意の何れかによって）ナビゲーション中に従前に計算されたルートから逸脱する、代替ルートがより好都合であるとリアルタイム交通状況が決定づけ、装置がそのような状況を自動的に認識することが適切に可能である、あるいは、任意の理由でユーザが積極的に装置にルート再計算を実行させる、場合における自動ルート再計算である。
【００１７】
ユーザが定義した基準でルートが計算されるのを可能にすることも知られている。例えば、ユーザは景色の良いルートが装置により計算されることを好んでもよく、交通渋滞が起こりそうな、予期される、あるいは現在起こっている道路を回避することを望んでもよい。装置のソフトウェアは、その場合様々なルートを計算し、ルートに沿った景色の美しい例としてタグ付けられた最多数の（ＰＯＩとして知られる）着目地点を含む、より好ましいルートに重み付けし、または、特定の道路における現在の交通状況を示す格納された情報を使用して、起こりそうな渋滞または渋滞による遅延のレベルの観点で、計算されたルートを順序付けるだろう。他のＰＯＩベースおよび交通情報ベースのルート計算およびナビゲーション基準も可能である。
【００１８】
ルート計算およびナビゲーション機能はＰＮＤ全体の有用性に欠かせないけれども、純粋に情報表示のために、すなわち装置の現在位置と関連するマップ情報のみが表示され、ルートが計算されておらず、装置によってナビゲーションが現在実行されていない“フリードライビング”のために装置を使用することが可能である。そのような動作モードは、ユーザが移動することを望むルートを既に知っており、ナビゲーション補助を必要としない場合に、しばしば適用可能である。
【００１９】
上述したタイプの装置、例えばトムトムインターナショナル・ベステーロン・フエンノートシャップによって製造および供給される７２０Ｔモデルは、一つの位置から別の位置へユーザをナビゲートするのを可能にする信頼性のある手段を提供する。
【００２０】
時にはナビゲーションの間、現在位置を判定するためにナビゲーション装置によって使用されるＧＰＳ信号が利用不可能になるかもしれない。そのような場合、ＧＰＳを介して取得された位置の、表示マップ上の位置とのマッチングはもはや可能ではない。
【００２１】
デッドレコニング（dead reckoning）を使用してＧＰＳカバレッジの間隙の間に位置推定を提供し、この問題を解決することが知られている。デッドレコニングの１つの既知の方法は、ジャイロスコープや加速度計等の移動センサから取得される、乗り物が移動する角度および距離の変化に基づいて、既知の位置（位置情報）から乗り物が移動する経路を推定することである。この推定経路は、次に、道路ネットワークのマップ等のマップデータにマッチングされる。
【００２２】
そのような技術の問題は、位置センサによってなされる測定での誤差が、誤った経路が推定される結果をもたらしうることである。乗り物の回転速度計（タコメータ）から位置データを取得する内蔵式ナビゲーション装置について、特に、位置データの変化率を測定するセンサ（種々のセンサ）からの複数の信号を積分することによって位置データが取得される場合に、これらの誤差はかなり大きくなりうる。例えば、測定された加速度の二重積分を通じて加速度計から距離を取得する。位置データは測定値の積分を通じて取得されるので、測定値の誤差の小さな線形増加は、その測定値から取得される位置データの誤差の大きな非線形増加をもたらす。これらの大きな誤差は、位置推定において大きな誤差をもたらし、および結果として乗り物の経路／位置のマップ上での誤表示をもたらしうる。
【発明の概要】
【００２３】
本発明の第1の側面によれば、位置センサから信号を受信する受信機と、シード位置とエリア内でナビゲート可能なルートのマップとを備えるマップデータを内部に格納したメモリと、現在位置を出力する出力装置と、前記信号から移動距離および方位変化を判定する工程および前記マップデータの前記ナビゲート可能なルートの一つにおける前記現在位置を推定する工程のためのプロセッサと、を備えるナビゲーション装置であって、前記推定する工程は、
前記移動距離および前記方位変化を使用して、前記ナビゲーション装置が移動していたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、前記ナビゲーション装置が当該経路を移動した確率を各経路に割り当て、
方位変化について、各経路を拡張し、前記ナビゲーション装置が当該経路を移動した確率を再計算し、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる
ことを含むことを特徴とする。
【００２４】
本発明のナビゲーション装置は、センサから受信する信号に基づく位置データ（距離および方向）における誤差のせいでマップにおける現在位置が不正確になるなら、さらなる位置データおよびこのさらなる位置データのマップデータとのマッチングに基づいて、この誤差は後に補正されるかもしれないという有利な点を有するかもしれない。例えば、初期に可能性のある経路は、位置データの内在誤差のために高い確率を有するかもしれないが、さらなる位置データが受信されるにつれて、この経路の確率は、別の経路が最も可能性の高い移動経路になるほどまで低減するかもしれず、ナビゲーション装置が現在位置を今のところより可能性の高い経路上の位置に変更するかもしれない。決定地点（交差点または経路のルート関節）を通過しても他の可能性のある経路を判定することがない従来の装置では、この“回帰（regression）”は可能ではない。
【００２５】
各経路がナビゲーション装置が移動した経路である確率は、方位変化と、前記経路のナビゲート可能なルートの対応する角度変化とを比較することによって判定されてもよい。例えば、方位変化は、２つのナビゲート可能なルートの交差点またはナビゲート可能なルート自体のカーブにおけるターンの結果であってもよい。特定の一連の方位変化が、経路を形成する、例えば道路セグメント等の、特定のナビゲート可能なルートに沿った移動に対応する確率を判定することによって、経路の確率が判定されてもよい。例えば、経路の確率は、経路を構成する各ナビゲート可能なルートの別個の確率を判定して、これらの確率を共に乗じたり足し合わせたりすることによって計算されてもよい。ルートは１以上の経路と関連付けられることができ、ルートはそれと関連付けられた複数の確率、各経路に対する確率、を有してもよい。
【００２６】
方位変化は、所定の角度閾値を超える単位時間当たりの、例えば１秒当たり数度を超えての、角度変化が検出されてから、単位時間当たりの角度変化が再び安定し前記所定の閾値より少なくなるまでの、離散的イベントであってもよい。このようにして、拡張および確率の再計算は操作の完了に応じて実行され、より連続的なプロセスと比較して処理量を低減する。
【００２７】
前記現在位置を推定する工程は、各経路を拡張し、距離変化について前記ナビゲーション装置が当該経路を移動した前記確率を再計算することをさらに含む。方位変化と同様に、経路の拡張および確率の再計算が実行される地点における距離変化は、所定の距離閾値、例えば数十メートル、数百メートル、を超える距離変化であってもよい。
【００２８】
前記プロセッサは、前記ナビゲーション装置が当該経路を移動した前記確率が所定の確率閾値を下回る場合に、さらなる拡張および計算から経路を破棄するように構成されてもよい。
【００２９】
例えば、経路が破棄される前記確率閾値は、前記経路がＮ個の最も可能性のある経路の１つでない場合である。Ｎの値が大きいほど、プロセッサは各方位変化／方向変化についてより多くの処理を実行しなければならないだろうが、ナビゲーション装置によって移動される最も可能性の高い経路に後になるかもしれない経路が破棄される可能性はより低くなる。多くの状況において、２つの最も可能性の高い経路を除いて破棄することは、もし誤った経路が初期に最も可能性の高い経路として識別されているなら、正確な経路を後に見つけるのに十分ロバストである。
【００３０】
追加的にあるいは代替的に、経路が破棄される確率閾値は設定数であってもよい。例えば、経路の確率が設定数を下回る場合に経路が破棄され、または、経路の確率の、現在のところ最も可能性の高い経路である経路の確率に対する比が、設定された比よりも小さい場合に経路が破棄される。
【００３１】
前記プロセッサは、前記経路の拡張数が所定の拡張閾値を超える場合に、さらなる拡張および計算から前記最高確率を有する経路でない各経路を破棄するように構成されてもよい。同様に、適切な拡張閾値を設定することは、受容可能なレベルに必要な処理量を維持するのに使用されうる。拡張閾値は、２、３、４または５個の拡張等の数個の拡張であってもよい。
【００３２】
経路の拡張の間、経路が分岐するシード地点が作成されるだろう（従って２以上の経路を形成する）。初期のシード地点は２以上の経路が作成される第１のシード地点である。もし経路が無視されるなら、初期のシード地点は新しい位置へ移動することになるかもしれない。前記プロセッサは、初期のシード地点の前にあるルートの経路確率への寄与を無視するように構成されてもよい。このようにして、プロセッサは不必要な計算を実行せず、または大容量データを不必要に格納しない。
【００３３】
前記プロセッサは、（他の経路が破棄され、または他の可能性のある経路が存在しない、という結果として）単一の可能性のある経路しか存在しない場合に、メモリにおける前記シード位置を前記現在位置に設定し、および／または、シード地点に設定するように構成されてもよい。
【００３４】
前記位置センサは、加速度、速度、距離、時間および角度変化のうち少なくとも１つを測定するセンサを備えてもよい。一実施形態において、前記位置センサは、加速度計とジャイロスコープとの少なくとも何れか１つを備えてもよい。ナビゲーション装置が位置センサを備えてもよく、または、ナビゲーション装置は位置センサと接続する入力部を備えてもよい。
【００３５】
前記出力装置は、ディスプレイとスピーカとの少なくとも何れか１つであってもよい。
【００３６】
ナビゲーション装置は、全地球測位システム（ＧＮＳＳ）受信機またはＧＮＳＳ受信機と接続された入力部を備えてもよく、プロセッサは、ＧＮＳＳ信号が利用可能である場合にはＧＮＳＳ受信機によって受信される信号から現在位置を推定し、ＧＮＳＳ信号が利用不可能である場合には上述した工程に従って現在位置を推定するように構成される。このようにして、ナビゲーション装置は、ＧＮＳＳ信号が受信されない場合であっても継続して位置を追跡することができる。
【００３７】
本発明の第２の側面によれば、シード位置とエリア内でナビゲート可能なルートのマップとを備えるマップデータを内部に格納したメモリと接続されたプロセッサによって実行される場合に、前記プロセッサに、移動距離および方位変化に関する位置データを受信させ、前記位置データからマップデータの複数のナビゲート可能なルートの１つにおける現在位置を推定させ、出力装置に現在位置を出力させる命令を格納したデータキャリアであって、前記推定する工程は、
前記移動距離および前記方位変化を使用して、前記ナビゲーション装置が移動していたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、前記ナビゲーション装置が当該経路を移動した確率を各経路に割り当て、
方位変化について、各経路を拡張し、前記ナビゲーション装置が当該経路を移動した確率を再計算し、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる
ことを含むことを特徴とするデータキャリアが提供される。
【００３８】
本発明の第３の側面によれば、位置データを使用してナビゲート可能なルートのマップにおける現在位置を推定する方法であって、前記方法は、
前記位置データから移動距離および方位変化を判定する工程と、
前記移動距離および前記方位変化を使用して、前記移動されていたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、当該経路が移動された確率を各経路に割り当てる工程と、
方位変化について、各経路を拡張し、ナビゲーション装置が当該経路を移動した確率を再計算する工程と、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる工程と、
を有することを特徴とする方法が提供される。
【図面の簡単な説明】
【００３９】
本発明の教示の様々な側面、およびこれらの教示を具体化する構成が、添付の図面を参照して実例によって以下説明されるだろう。
【図１】図１は、全地球測位システム（ＧＮＳＳ）と通信するナビゲーション装置の概略図である。
【図２】図２は、本発明の第１実施形態に従ったナビゲーション装置を提供するように構成された電子構成要素の概略図である。
【図３】図３は、ナビゲーション装置が無線通信チャネルを通じてサーバから情報を受信してもよい方法の概略図である。
【図４Ａ】、
【図４Ｂ】図４Ａおよび図４Ｂは、ナビゲーション装置の例示的斜視図である。
【図５Ａ】、
【図５Ｂ】図５は、本発明の実施形態に従ったナビゲーション装置によって実行される方法を示す。
【図６】図６は、本発明の実施形態に従ってナビゲーション装置によって計算されうる多くの可能性のある経路の例である。
【発明を実施するための形態】
【００４０】
本発明の好適な実施形態が、特にＰＮＤを参照して説明されるだろう。しかしながら、本発明の教示はＰＮＤに限定されず、現在位置をマップに位置付ける他のタイプのナビゲーション装置に広く適用可能であることに留意されたい。それ故、本願に関連して、ナビゲーション装置は、その装置が、ＰＮＤ、乗り物に内蔵されるナビゲーション装置、あるいは実際ルートプランニングおよびナビゲーションソフトウェアを実行する（デスクトップまたはポータブル・パーソナル・コンピュータ（ＰＣ）、携帯電話、携帯情報端末（ＰＤＡ）等の）コンピュータ資源、として具体化されるかどうかに関わらず、（制限なく）ナビゲーション装置を含むことが意図される。
【００４１】
上記の条件を考慮して、図１は、ナビゲーション装置１４０によって使用可能な、全地球測位システム（ＧＮＳＳ）１００の例示を説明する。一般に、ＧＮＳＳは、連続的な位置、速度、時間および場合によっては方向情報を判定することができる衛星無線ベースのナビゲーションシステムである。ＧＮＳＳは、地球１２４の軌道上に複数の衛星１２０を備えている。各衛星１２０の軌道は、他の衛星１２０の軌道と必ずしも同期しておらず、実際恐らく非同期である。ＧＮＳＳ衛星は、信号１６０を介して受信ユニット１４０へ自身の位置を中継する。ＧＮＳＳ受信機１４０は、スペクトラム拡散ＧＮＳＳ衛星信号１６０を受信し、衛星によって中継された位置情報からその位置を判定する。
【００４２】
本発明のナビゲーション装置は、ＮＡＶＳＴＡＲ、Ｇａｌｉｌｅｏ、ＧＬＯＳＮＡＳＳまたは任意の他の適切なGNSSとしてかつて知られているＧＰＳを使用してもよい。ＧＮＳＳは非常に性格な軌道で地球を周回する複数の衛星１２０を組み込んでいる。
【００４３】
各衛星１２０から継続して送信される、スペクトラム拡散信号１６０は、極めて正確な原子時計により達成される極めて正確な周波数標準を利用する。各衛星１２０は、そのデータ信号送信１６０の一部として、その特定の衛星１２０を示すデータストリームを送信する。ＧＮＳＳ受信機装置１４０は一般に、少なくとも３つの衛星１２０からスペクトラム拡散ＧＮＳＳ衛星信号１６０をＧＮＳＳ受信機装置１４０について取得して三角測量によってその二次元位置を計算することが、関連技術の当業者によって理解される。全部で４つの衛星１２０からの信号１６０をもたらす、追加信号の取得は、ＧＮＳＳ受信機装置１４０が既知の方法でその三次元位置を計算するのを可能にする。
【００４４】
ＧＮＳＳシステムは、特にＧＮＳＳデータを受信する設備が整った装置が、ＧＮＳＳ衛星信号の無線周波数をスキャンし始める場合に実施される。ＧＮＳＳ衛星から無線信号を受信すると、装置は、複数の異なる従来の方法の１つを介してその衛星の正確な位置を判定する。装置は、大抵の場合、少なくとも３つの異なる衛星信号を取得するまで、信号のスキャンを継続するだろう（位置は、通常はそうではないが、他の三角測量技術を使用して２つの信号のみで判定されうることに留意されたい）。幾何学的三角測量を実施すると、受信機は、３つの既知の位置を利用して、衛星と比較した自身の二次元位置を判定する。これは既知の方法でなされうる。さらに、第４の衛星信号を取得することにより、受信装置がその三次元位置を計算することが、既知の方法での同じ幾何学的計算によって可能になるだろう。位置および速度データは、無限のユーザによって常にリアルタイムに更新されうる。
【００４５】
図２は、本発明の好適な実施形態に従ったナビゲーション装置２００の電子構成要素の、ブロック構成形式での代表図である。ナビゲーション装置２００のブロック図は、ナビゲーション装置の全ての構成要素を含んでおらず、多くの例示的構成要素の代表のみであることに留意されたい。
【００４６】
ナビゲーション装置２００の電子的構成要素は、図４Ａおよび図４Ｂに示されるような筐体内に位置している。ナビゲーション装置は、入力装置２２０と接続された処理装置２１０、および処理装置２１０と接続されたバックライトドライバ２４１を備える、ディスプレイスクリーン、本実施形態ではＬＣＤ２４０、を含む。入力装置２２０は、キーボード装置、音声入力装置、タッチパネルおよび／または情報を入力するために利用される任意の他の既知の入力装置を含み、ディスプレイスクリーン２４０は、例えばＬＣＤディスプレイ等の任意のタイプのディスプレイスクリーンを含みうる。この構成では、入力装置２２０およびディスプレイスクリーン２４０は、複数のディスプレイ選択の１つを選択するために、または、複数の仮想ボタンの１つを起動するために、ディスプレイスクリーン２４０の一部をユーザがタッチすることのみが必要であるように、タッチパッドまたはタッチスクリーン入力を含む一体型入力表示装置に統合されている。
【００４７】
ナビゲーション装置は、例えばスピーカ２６１、音声増幅器２６２、および音声コーデック２６０等の、出力装置２６０−２６２を含んでもよい。音声装置２６０−２６２は、判定されたナビゲート可能なルートに従ってユーザを指示する音声命令を生成しうる。
【００４８】
ナビゲーション装置２００において、処理装置２１０は、接続２２５を介して入力装置２２０と動作可能に接続されて、当該入力装置２２０から入力情報を受信するように設定されており、および、出力接続２４５および２４６を介してディスプレイスクリーン２４０および出力装置２６０のうち少なくとも１つと動作可能に接続され、そこへ現在位置を含む情報を出力する。さらに、処理装置２１０は接続２３５を介してメモリ資源２３０と連結される。メモリ資源２３０は、例えばランダムアクセスメモリ（ＲＡＭ）等の揮発性メモリ、および、例えばフラッシュメモリ等のデジタルメモリである不揮発性メモリを備える。メモリ資源は、エリア内のナビゲート可能なルートのマップ、例えば、イギリスまたはオランダ等の国におけるナビゲート可能なルートのマップを備えるマップデータを内部に格納している。この実施形態においては、マップデータの各ルートは、各セグメントと関連付けられた例えば速度制限、交通プロファイル（traffic profile）、他の道路規制等の、そのセグメントの属性を規定したデータを含む各セグメントで分けられている。
【００４９】
ナビゲーション装置２００は、セルラネットワークの基地局から、ＢＣＣＨ等の、ブロードキャスト信号を受信する、携帯電話等のセルラモデム２８０と取り外し可能に接続する接続２７０をさらに備える。接続２７０は、ナビゲーション装置２００と例えばインターネットまたは任意の他のネットワークとの間のデータ接続を確立するために、および／または、例えばインターネットまたはいくつかの他のネットワークを介してサーバへの接続を確立するために、使用されてもよい。別の実施形態において、装置２８０はテレビジョン受信機またはＴＭＳ／ＲＤＳ情報を受信しうる無線受信機であってもよい。
【００５０】
図２は、接続２５５を介して、処理装置２１０と、ＧＮＳＳアンテナ２５０と、受信機２５１との間の動作可能な接続をさらに説明する。アンテナは例えばＧＮＳＳパッチアンテナまたはヘリカルアンテナであってもよい。
【００５１】
さらに、図２に示される電子的構成要素は、電源２９０、この場合は従来のように電源管理集積回路２９０、によって動作されることが当業者によって理解されるだろう。
【００５２】
有線接続２７６、この実施形態ではＵＳＢ接続は、処理装置２１０をコンピュータ等と接続するために提供される。そのような接続はソフトウェア／ファームウェアの更新および／またはマップの更新のために使用されうる。
【００５３】
ナビゲーション装置２００は、位置センサ、この実施形態ではジャイロスコープ２９６および加速度計２９７、と接続するこの実施形態ではコネクタである受信機２９５を備えており、ＣＰＵ２１０はジャイロスコープ２９６および加速度計２９７から信号を受信することができる。
【００５４】
当業者によって理解されるように、図２に示される構成要素の異なる構成が、本願の範囲に含まれると考えられる。例えば、図２に示される構成要素は、有線接続および／または無線接続等を介して相互に通信してもよい。従って、本願のナビゲーション装置２００の範囲は、ポータブルまたはハンドヘルドナビゲーション装置２００を含む。
【００５５】
さらに、図２のポータブルまたはハンドヘルドナビゲーション装置２００は、例えば図５ａおよび図５ｂに示される取付装置２９２／２９４を使用することによって、自転車、バイク、自動車またはボート等の乗り物と、既知の方法で接続あるいは“ドッキング”されうる。そのようなナビゲーション装置２００は、ポータブルまたはハンドヘルドナビゲーション使用のためにドッキングされた位置から取り外し可能である。
【００５６】
次に図３を参照すると、ナビゲーション装置２００は、（例えば既知のＢｌｕｅｔｏｏｔｈ（登録商標）技術を介したデジタル接続等の）デジタル接続を構築するセルラモデム２８０を介してサーバ３０２との“モバイル”または通信ネットワーク接続を構築してもよい。その後、そのネットワークサービスプロバイダを通じて、セルラ装置はサーバ３０２と（例えばインターネットを通じて）ネットワーク接続を構築しうる。そのようにして、“リアルタイム”または少なくとも非常に“最新の”ゲートウェイに情報を提供するために、（単独および／または乗り物で移動するにつれて多くの場合動きうる）ナビゲーション装置２００とサーバ３０２との間に“モバイル”ネットワーク接続が構築される。
【００５７】
例えば（ワールド・ワイド・ウェブ等の）インターネットを使用して、（サービスプロバイダを介した）モバイル装置とサーバ３０２等の別の装置との間でのネットワーク接続を構築することは、既知の方法で行われうる。これは例えばＴＣＰ／ＩＰレイヤプロトコルの使用を含みうる。モバイル装置は、ＤＶＢ−Ｈ、ＤＶＢ−Ｔ、ＣＤＭＡ、ＧＳＭ、Ｗｉ−Ｍａｘ、ＴＭＣ／ＲＤＳ等の任意の数の通信標準を利用することができる。
【００５８】
そのようなものとして、例えば、携帯電話またはナビゲーション装置２００内の携帯電話技術を介した、データ接続を介して達成されるインターネット接続が利用されてもよい。この接続について、サーバ３０２とナビゲーション装置２００との間でインターネット接続が構築される。これは、例えば携帯電話または他のモバイル装置およびＧＰＲＳ（ジェネラル・パケット・ラジオ・サービス）接続を通じて実行されうる（ＧＰＲＳ接続は通信会社によって提供されるモバイル装置のための高速データ接続であり、ＧＰＲＳはインターネットと接続するための方法である）。
【００５９】
ナビゲーション装置２００はさらに、モバイル装置とのデータ接続、ひいては、既知の方法で、例えば既存のＢｌｕｅｔｏｏｔｈ（登録商標）技術を介して、インターネットおよびサーバ３０２との接続を完了することができ、ここでデータプロトコルは、例えばＧＳＲＭ、ＧＳＭ標準のためのデータプロトコル標準等の、任意の数の標準を利用することができる。
【００６０】
ＧＰＲＳ電話設定について、Ｂｌｕｅｔｏｏｔｈ（登録商標）可能なナビゲーション装置は、携帯電話モデル、製造業者等の絶え間なく変化しているスペクトルと正確に連動するように使用されてもよく、例えばモデル／製造業者に特有の設定がナビゲーション装置２００に格納されてもよい。この情報について格納されるデータは更新されうる。
【００６１】
図３において、ナビゲーション装置２００は、任意の多数の異なる構成によって実施されうる汎用通信チャネル３１８を介してサーバ３０２と通信しているものとして描写されている。サーバ３０２およびナビゲーション装置２００は、通信チャネル３１８を介してサーバ３０２とナビゲーション装置２００との間に接続が構築された場合に通信することができる（そのような接続は、モバイル装置を介したデータ接続、インターネットを介しパーソナル・コンピュータを通じた直接接続等でありうることに留意されたい）。
【００６２】
サーバ３０２は、説明されていない他の構成要素に加えて、メモリ３０６と動作可能に接続され、有線または無線接続３１４を介して大容量記憶装置３１２とさらに動作可能に接続された処理装置３０４を含む。処理装置３０４は、通信チャネル３１８を介してナビゲーション装置２００へ情報を送信および送出し、当該ナビゲーション装置２００から情報を受信するために、送信機３０８および受信機３１０と動作可能にさらに接続される。送受信される信号は、データ、通信、および／または他の伝播信号を含んでもよい。送信機３０８および受信機３１０は、ナビゲーションシステム２００のための通信設計で使用される通信要件および通信技術に従って選択または設計されてもよい。さらに、送信機３０８および受信機３１０の機能は単一の送受信機に一体化されてもよいことに留意されたい。
【００６３】
サーバ３０２は、大容量記憶装置３１２とさらに接続されており（あるいは大容量記憶装置３１２を含んでおり）、大容量記憶装置３１２は、通信リンク３１４を介してサーバ３０２と連結されてもよいことに留意されたい。大容量記憶装置３１２は、ナビゲーションデータおよびマップ情報の格納を含んでおり、サーバ３０２とは別個の装置でありえ、あるいは、サーバ３０２に組み込まれうる。
【００６４】
ナビゲーション装置２００は、通信チャネル３１８を通じてサーバ３０２と通信するように構成されており、図２および３に関して前に説明したように、通信チャネル３１８を通じて信号および／またはデータを送受信するための送信機３２０および受信機３２２だけでなく、処理装置、メモリ等を含み、これらの装置はサーバ３０２以外の装置と通信するためにさらに使用されうることに留意されたい。さらに、送信機３２０および受信機３２２は、ナビゲーションシステム２００のための通信設計で使用される通信要件および通信技術に従って選択または設計され、送信機３２０および受信機３２２の機能は単一の送受信機に一体化されてもよい。
【００６５】
サーバメモリ３０６に格納されたソフトウェアは、処理装置３０４に命令を提供し、サーバ３０２がナビゲーション装置２００へサービスを提供するのを可能にする。サーバ３０２によって提供される一つのサービスは、ナビゲーション装置２００からの要求を処理して、大容量記憶装置３１２からナビゲーション装置２００へナビゲーションデータを送信することを含む。サーバ３０２によって提供される別のサービスは、所望のアプリケーションの様々なアルゴリズムを使用してナビゲーションデータを処理して、これらの計算の結果をナビゲーション装置２００へ送信することを含む。
【００６６】
通信チャネル３１８は、一般に、ナビゲーション装置２００およびサーバ３０２を接続する伝播媒体または経路を表す。サーバ３０２およびナビゲーション装置２００は、通信チャネルを通じてデータを送信する送信機および通信チャネルを通じて送信されているデータを受信する受信機を含む。
【００６７】
通信チャネル３１８は、特定の通信技術に限定されない。さらに、通信チャネル３１８は、単一の通信技術に限定されない。すなわち、通信チャネル３１８は、様々な技術を使用するいくつかの通信リンクを含んでもよい。例えば、通信チャネル３１８は、電気的、光学的、および／または電磁気的な通信等の経路を提供するように構成されうる。そのようなものとして、通信チャネル３１８は、電気回路、有線同軸ケーブル等の導電体、光ファイバケーブル、コンバータ、無線周波数（ＲＦ）波、大気、空間等のうちの１つまたは組み合わせを含むがこれらに限定されない。
【００６８】
さらに、通信チャネル３１８は、例えばルータ、リピータ、バッファ、送信機、および受信機等の媒介装置を含みうる。
【００６９】
一つの例示的な構成において、通信チャネル３１８は、電話およびコンピュータネットワークを含む。さらに、通信チャネル３１８は、無線周波数、マイクロ波周波数、赤外線通信等の無線通信に適合可能であってもよい。さらに、通信チャネル３１８は、衛星通信に適合しうる。
【００７０】
通信チャネル３１８を通じて送信される通信信号は、所与の通信技術に必要とされる、あるいは望まれる信号を含むが、それらに限定されない。例えば、信号は、時分割多重アクセス（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）、符号分割多元接続（ＣＤＭＡ）、グローバル・システム・フォー・モバイル・コミュニケーションズ（ＧＳＭ）等のセルラ通信技術で使用されるように構成されてもよい。デジタル信号およびアナログ信号の両方が、通信チャネル３１８を通じて送信されうる。これらの信号は、変調され、暗号化され、および／または圧縮された、通信技術に望ましい信号であってもよい。
【００７１】
自動的またはユーザがサーバ３０２へナビゲーション装置２００を接続することに応じて定期的に更新されてもよく、および／または、例えばより定常的な接続またはより頻繁な接続が無線モバイル接続装置およびＴＣＰ／ＩＰ接続を介してサーバ３０２とナビゲーション装置２００との間でなされることに応じてより動的であってもよい、情報ダウンロードを介して、ナビゲーション装置２００はサーバ３０２から情報を提供されてもよい。多くの動的計算について、サーバ３０２における処理装置３０４は、処理ニーズの大部分を扱うために使用されてもよいが、しかしながら、ナビゲーション装置２００の処理装置２１０は、サーバ３０２との接続とはしばしば独立して、多くの処理および計算を扱うこともできる。
【００７２】
図４Ａおよび図４Ｂは、ナビゲーション装置２００の斜視図である。図４Ａに示されるように、ナビゲーション装置２００は、一体型入力表示装置２９０（例えばタッチパネルスクリーン）および（内部ＧＰＳ受信機２５０、処理装置２１０、電力供給、メモリシステム２３０等を含むがこれらに限定されない）図２および図３の他の構成要素を含むユニットであってもよい。
【００７３】
ナビゲーション装置２００は、吸着カップ２９４を使用して乗り物のダッシュボード／ウィンドウ等に固定されてもよいアーム２９２上に据え付いてもよい。このアーム２９２は、ナビゲーション装置２００がドッキングされうるドッキング・ステーションの一例である。
【００７４】
図４Ｂに示されるように、ナビゲーション装置２００は、例えばナビゲーション装置２００をアーム２９２とスナップ接続することによって、ドッキング・ステーションのアーム２９２とドッキングまたは別の方法で接続されうる。その場合ナビゲーション装置２００は、図４Ｂの矢印によって示されるように、アーム２９２上で回転可能であってもよい。ナビゲーション装置２００とドッキング・ステーションとの間の接続を解放するために、例えばナビゲーション装置２００上のボタンが押下されてもよい。ナビゲーション装置をドッキング・ステーションと連結およびドッキング・ステーションから分断するための他の同様な適切な構成が当業者に広く知られている。
【００７５】
このユーザがＰＮＤのスイッチを入れると、その装置は、ＧＮＳＳ ｆｉｘを取得し、（既知の方法で）ＰＮＤの現在位置を計算する。この現在位置を使用して、ＰＮＤは、従来のアルゴリズムに従ってナビゲート可能なルートを判定しうる。
【００７６】
次に図５を参照すると、メモリ資源２３０に格納されるのは、プロセッサ２１０によって実行される場合に、そのプロセッサに次に説明する方法のステップを実行させる命令を備えるコンピュータプログラムである。
【００７７】
ステップ４０１において、プロセッサ２１０は、ＧＮＳＳ信号がＧＮＳＳ受信機２５１によって受信されているかどうかを判定する。ＧＮＳＳ信号が受信されているなら、プロセッサ２１０は、ステップ４０２において、ＧＮＳＳ信号から、および選択的にはジャイロスコープ２９６および加速度計２９７から受信される信号からも、マップデータにおける現在位置を判定する。ＧＮＳＳ信号と併せてジャイロスコープ２９６および加速度計２９７からの信号を使用する利点は、より正確な位置が判定されることである。ＧＮＳＳ信号から判定される各新しい位置について、シード（seed）位置がこの新しい位置で更新される（ステップ４０３）。次に方法はステップ４０１へループして戻る。
【００７８】
ＧＮＳＳ受信機２５１が（例えばＧＮＳＳネットワークカバレッジが存在しないために）衛星１２０からＧＮＳＳ信号を受信していない場合、ステップ４０１において、方法はデッドレコニング技術の第１の部分としてステップ４０４へ進む。ステップ４０４において、プロセッサ２１０は、複数の可能性のある経路が、ジャイロスコープ２９６および加速度計２９７から受信された位置決めデータから判定された現在位置の従前の推定に基づいて、既に計算されているかどうかを判定確認する。ＧＮＳＳ信号がロストされたために、デッドレコニング技術によって位置が推定されるのが初めてであるなら、ナビゲーション装置が移動した可能性のある経路はまだ判定されていないだろう。従って、そのような状況においては、プロセッサはステップ４０５へ進み、最後の（最新の）シード位置が判定されたので、プロセッサはジャイロスコープ２９６および加速度計２９７から信号を受信し、その信号から、移動距離および方位変化（位置データ）を判定する。
【００７９】
プロセッサ２１０は、ステップ４０６において、メモリ資源２３０からシード位置を読み出し、移動距離および任意の方位変化を使用して、ナビゲーション装置２００によって移動される可能性のある経路をそのシード位置から推定する。この実施形態においては、プロセッサ２１０は、移動距離および／または方位変化が所定の閾値を超える場合に、可能性のある移動経路の第１の計算を実行する。各経路がナビゲーション装置２００が移動した経路である確率は、方位変化と、対応する経路のナビゲート可能なルートの角度変化とを比較することによって、判定されてもよい。例えば、方位変化は、２つのナビゲート可能なルートの交差点でなされるターンまたはナビゲート可能なルート自体のカーブの結果であってもよい。
【００８０】
このことが達成されうる１つの方法の例が、図６に関して次に説明されるだろう。点線５０１は、ジャイロスコープ２９６および加速度計２９７からの信号によって示される経路を示している。しかしながら、測定誤差のせいで、これは、マップデータのナビゲート可能なルート５０２−５０９と合致していない。従って、プロセッサ２１０は、方位変化および移動距離の測定値がマップデータのナビゲート可能なルート５０３−５０９の方位および距離の変化にどの程度近いかに基づいて、各ナビゲート可能なルート５０３−５０９が移動された確率を割り当てる。所与の例では、ナビゲーション装置が最初にわずかに左に移動するにつれて方位変化が生じると、第１の判定が実行される。左への移動は、ＢからＤへのルート５０４よりはＢからＣへのルート５０３に沿って移動することによりぴったりと合致するので、ルート５０３に沿ったこの最初の方位変化の経路には、ルート５０４に沿った経路よりも高い確率が与えられる。
【００８１】
各経路に割り当てられる確率は、経路を構成するルートの個々の確率の重み付けされた合計である（すなわち、全ての可能性のある経路を構成する全てのルートの確率全体によって除算された経路を構成するルートの確率の合計）。従って、まず第１に、経路を構成するルート５０３、５０４に確率が割り当てられ、次に、経路の確率がルートについて判定された確率から判定される。図６に示される例では、ＢからＤへの経路に割り当てられる確率はおよそ０．４８６であり、ＢからＣへの経路に割り当てられる確率はおよそ０．５１４である。ステップ４０７において、これらの確率が経路に割り当てられ、メモリ資源２３０に格納される。ある状況では、ルートは複数の経路に属することができ、それと関連付けられた複数の確率、ルートが属する各経路について１つの確率、を有することが理解されるだろう。
【００８２】
ステップ４０８において、プロセッサ２１０は、経路に割り当てられた確率を比較し、その確率が所定の閾値を下回るなら、その経路は破棄される。
【００８３】
例えば、経路が破棄される閾値は、Ｎ個の最も可能性の高い経路のうちの１つではない場合であってもよい。Ｎの値が大きいほど、プロセッサは、各方位変化／方向変化についてより多くの処理を実行しなければならないだろうが、後にナビゲーション装置によって移動される最も可能性の高い経路になるかもしれない経路が破棄される可能性はより低くなる。多くの状況において、誤った経路が初期に最も可能性の高い経路として特定されるなら、２つの最も可能性の高い経路以外を破棄することは、後に正確な経路を見つけるのに十分ロバストである。こうした要求の代わりとして、またはこうした要求に加えて、他の要求が使用されてもよく、例えば、プロセッサ２１０は、経路の拡張数が所定の拡張閾値を超える場合、さらなる拡張および計算から最も高い確率を有する経路ではない各経路を破棄するように構成されてもよく、および／または、ナビゲーション装置が経路を移動した確率が所定の閾値を下回る場合に当該経路が破棄されてもよいことが理解されるだろう。
【００８４】
従って、図６に示される例では、プロセッサ２１０が初期の方位変化から判定するルート５０２および５０３に沿った初期の２つの経路は、それらが２つの最も可能性の高い経路であって高い確率を有するので破棄されない。ステップ４０９において、プロセッサ２１０は、ナビゲーション装置２００の現在位置を、最も高い確率を有する経路上の位置になるように割り当てる。計算された初期の２つの経路について、これは、この経路が０．４８６に対して０．５１４というより高い確率を有するので、ルート５０３上で予測される位置であるだろう。この現在位置は、ナビゲーション装置によって、例えばディスプレイ２４０上のグラフィックとして次に出力される。
【００８５】
ステップ４１６において、プロセッサ２１０は、もはや関連しないルートを経路から取り除く。破棄されるルートは、経路が分岐する初期地点（初期シード地点）の前に生じるルートを含む。図６に示される例では、地点Ｂが初期シード地点であり、そのためルート５０２によって寄与される経路の確率に対する任意の寄与が除外される。
【００８６】
ステップ４１０において、プロセッサ２１０は、複数の経路が残っているかどうか判定確認し、複数の経路が存在するならプロセッサは、ステップ４０１へ戻る。結果として、プロセッサ２１０は、ＧＮＳＳ信号が受信されうるかどうか再び見て確認する。いまだにＧＮＳＳカバレッジが存在しないなら、ステップ４０４において、プロセッサ２１０は、複数の経路が残っているかどうか判定確認する。図６に示される例では、初期の方位変化の後に、２つの可能性のある経路が保持されている。従って、プロセッサ２１０は、ステップ４１２へ進む。ステップ４１２において、プロセッサは、ジャイロスコープ２９６および加速度計２９７から受信される信号から移動距離および方位変化を判定し、ステップ４１３において、プロセッサ２１０は、既に判定されている経路から拡張して、可能性のある経路の新しいセットを判定する。再び図６を参照すると、これは、例えばルート５０３が地点Ｃにおいてルート５０５へと左へ進むこと、およびルート５０４が地点Ｄにおいてルート５０６および５０７へ分岐すること等、移動距離のセットにおいて生じる予測交差のために、および／または、さらなる方位変化、図６において右への移動、のために、実行されてもよい。
【００８７】
以前のループと同様に、ステップ４０７において、経路の新しいセットの各可能性のある経路について確率が計算される。ルート５０５が移動されている可能性は非常に低く０．１であり、ＢからＥへの経路が、ナビゲーション装置が移動した経路である確率は、ルート５０３およびルート５０５がともに移動されている確率の重み付け合計（加重和）を実行することによって計算される。これは、およそ０．２６というこの経路の確率を与える。他の可能性のある経路は、（ルート５０４および５０６、および、ルート５０４および５０７をそれぞれ含む）ＢからＧおよびＢからＦであり、同様にしてこれらの経路について確率が計算され、それぞれ０．４５および０．２９を与える。ステップ４０８において、プロセッサ２１０は最も可能性の高い確率を有する２つの経路を保持するのみであるため、ルート５０３および５０５を含む経路が破棄される。ステップ４０９において、ナビゲーション装置２００によって出力される現在位置は、ルート５０４および５０６を含む経路上の予測位置へ変更される。複数の可能性のある経路が残っているので、プロセッサは、ステップ４１１へ進み、ステップ４０１へループして戻る。
【００８８】
ＢからＥまでの経路が破棄されているので、地点Ｂはもはやシード地点（経路が分岐する地点）ではない。新しい初期シード地点はＤである。ステップ４１６において、現在の新しい初期シード地点（地点Ｄ）の前に生じるルートの寄与は除外され、２つの経路ＤからＦおよびＤからＧについての確率はそれぞれおよそ０．３０８およびおよそ０．６９である。
【００８９】
このプロセスは、さらなる方位および距離の変化について次に繰り返され、経路が推定され、新しい経路が形成されて、これら新しい経路について確率が計算される。図６に示される例では、残っている経路は、新しい経路ＤからＨおよびＤからＩを与えるように推定され、経路ＤからＩはルート５０６および５０９を含み、経路ＤからＨはルート５０７および５０８を含み、０．８４および０．１６という確率を有する。ステップ４０８において、プロセッサ２１０は、この経路の確率は所定の閾値０．２を下回るので、ルート５０７および５０８を含む経路ＤからＨを破棄してもよい。従って、現在位置はＤからＩへの経路上の位置に割り当てられる。１つの経路のみ残っているので、プロセッサ２１０は、ステップ４１４へ進み、唯一残っている経路上における現在の予測位置でシード位置を更新し、次にステップ４０１へループして戻り、ＧＮＳＳ信号が受信されえない限りプロセスが再び開始される。
【００９０】
可能性のある経路の各推定／拡張は、方位および／または距離の変化が所定の閾値を超える場合、例えば、単位時間当たりの角度変化が所定の角度閾値、例えば１秒当たり数度、を超える、あるいは、距離変化が所定の距離閾値、例えば数十メートルまたは数百メートル、を超える場合にのみ実行されもよいことが理解されるだろう。
【００９１】
さらに、本発明のデッドレコニング技術は、例えば、サーバ３０２のプロセッサ３０４によるナビゲーション装置とは離れた別の処理装置によって実行されることができ、この処理によって判定される現在位置は、通信リンク３１８を通じてナビゲーション装置へ送信し返されることが理解されるだろう。
【特許請求の範囲】
【請求項１】
位置センサから信号を受信する受信機と、シード位置とエリア内でナビゲート可能なルートのマップとを備えるマップデータを内部に格納したメモリと、現在位置を出力する出力装置と、前記信号から移動距離および方位変化を判定する工程および前記マップデータの前記ナビゲート可能なルートの一つにおける前記現在位置を推定する工程のためのプロセッサと、を備えるナビゲーション装置であって、前記推定する工程は、
前記移動距離および前記方位変化を使用して、前記ナビゲーション装置が移動していたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、前記ナビゲーション装置が当該経路を移動した確率を各経路に割り当て、
方位変化について、各経路を拡張し、前記ナビゲーション装置が当該経路を移動した確率を再計算し、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる
ことを含むことを特徴とするナビゲーション装置。
【請求項２】
各経路が前記ナビゲーション装置が移動した経路である前記確率は、前記方位変化と、前記経路の前記ナビゲート可能なルートの対応する角度変化とを比較することによって判定されることを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
方位変化は、所定の角度閾値を超える単位時間当たりの角度変化が検出されてから、単位時間当たりの角度変化が再び安定し前記所定の閾値より少なくなるまでの、離散的イベントであることを特徴とする請求項２に記載のナビゲーション装置。
【請求項４】
前記現在位置を推定する工程は、各経路を拡張し、距離変化について前記ナビゲーション装置が当該経路を移動した前記確率を再計算することをさらに含むことを特徴とする請求項１乃至３の何れか１項に記載のナビゲーション装置。
【請求項５】
前記経路の拡張および前記確率の再計算は、前記距離変化が所定の距離閾値を超えている場合に実行されることを特徴とする請求項４に記載のナビゲーション装置。
【請求項６】
経路の確率は、特定の方位変化と距離変化との少なくとも１つが前記経路を形成する特定のナビゲート可能なルートに沿った移動に対応する確率を判定し、および、この確率を、前記経路を形成する他のナビゲート可能なルートに沿った移動に対応する他の方位変化と距離変化との少なくとも１つについて計算された確率で乗じることによって、判定されることを特徴とする請求項１乃至５の何れか１項に記載のナビゲーション装置。
【請求項７】
前記プロセッサは、前記ナビゲーション装置が経路を移動した前記確率が所定の確率閾値を下回る場合に、さらなる拡張および計算から当該経路を破棄するように構成されることを特徴とする請求項１乃至６の何れか１項に記載のナビゲーション装置。
【請求項８】
経路が破棄される前記確率閾値は、前記経路がＮ個の最も可能性のある経路の１つでない場合であることを特徴とする請求項７に記載のナビゲーション装置。
【請求項９】
前記プロセッサは、前記経路の拡張数が所定の拡張閾値を超える場合に、さらなる拡張および計算から前記最高確率を有する経路でない各経路を破棄するように構成されることを特徴とする請求項１乃至８の何れか１項に記載のナビゲーション装置。
【請求項１０】
前記プロセッサは、単一の可能性のある経路しか存在しない場合に、メモリにおける前記シード位置を前記現在位置に設定するように構成されることを特徴とする請求項１乃至９の何れか１項に記載のナビゲーション装置。
【請求項１１】
前記プロセッサは、前記経路が分岐する初期のシード地点の前にあるルートの経路確率への寄与を無視するように構成されることを特徴とする請求項１乃至１０の何れか１項に記載のナビゲーション装置。
【請求項１２】
前記位置センサは、加速度、速度、距離、時間および角度変化のうち少なくとも１つを測定するセンサを備えることを特徴とする請求項１乃至１１の何れか１項に記載のナビゲーション装置。
【請求項１３】
前記位置センサは、加速度計とジャイロスコープとの少なくとも何れか１つを備えることを特徴とする請求項１２に記載のナビゲーション装置。
【請求項１４】
前記出力装置は、ディスプレイとスピーカとの少なくとも何れか１つであることを特徴とする請求項１乃至１３の何れか１項に記載のナビゲーション装置。
【請求項１５】
シード位置とエリア内でナビゲート可能なルートのマップとを備えるマップデータを内部に格納したメモリと接続されたプロセッサによって実行される場合に、前記プロセッサに、移動距離および方位変化に関する位置データを受信させ、前記位置データからマップデータの複数のナビゲート可能なルートの１つにおける現在位置を推定させ、出力装置に現在位置を出力させる命令を格納したデータキャリアであって、前記推定する工程は、
前記移動距離および前記方位変化を使用して、前記ナビゲーション装置が移動していたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、前記ナビゲーション装置が当該経路を移動した確率を各経路に割り当て、
方位変化について、各経路を拡張し、前記ナビゲーション装置が当該経路を移動した確率を再計算し、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる
ことを含むことを特徴とするデータキャリア。
【請求項１６】
位置データを使用してナビゲート可能なルートのマップにおける現在位置を推定する方法であって、前記方法は、
前記位置データから移動距離および方位変化を判定する工程と、
前記移動距離および前記方位変化を使用して、前記移動されていたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、当該経路が移動された確率を各経路に割り当てる工程と、
方位変化について、各経路を拡張し、ナビゲーション装置が当該経路を移動した確率を再計算する工程と、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる工程と、
を有することを特徴とする方法。
【請求項１】
位置センサから信号を受信する受信機と、シード位置とエリア内でナビゲート可能なルートのマップとを備えるマップデータを内部に格納したメモリと、現在位置を出力する出力装置と、前記信号から移動距離および方位変化を判定する工程および前記マップデータの前記ナビゲート可能なルートの一つにおける前記現在位置を推定する工程のためのプロセッサと、を備えるナビゲーション装置であって、前記推定する工程は、
前記移動距離および前記方位変化を使用して、前記ナビゲーション装置が移動していたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、前記ナビゲーション装置が当該経路を移動した確率を各経路に割り当て、
方位変化について、各経路を拡張し、前記ナビゲーション装置が当該経路を移動した確率を再計算し、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる
ことを含むことを特徴とするナビゲーション装置。
【請求項２】
各経路が前記ナビゲーション装置が移動した経路である前記確率は、前記方位変化と、前記経路の前記ナビゲート可能なルートの対応する角度変化とを比較することによって判定されることを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
方位変化は、所定の角度閾値を超える単位時間当たりの角度変化が検出されてから、単位時間当たりの角度変化が再び安定し前記所定の閾値より少なくなるまでの、離散的イベントであることを特徴とする請求項２に記載のナビゲーション装置。
【請求項４】
前記現在位置を推定する工程は、各経路を拡張し、距離変化について前記ナビゲーション装置が当該経路を移動した前記確率を再計算することをさらに含むことを特徴とする請求項１乃至３の何れか１項に記載のナビゲーション装置。
【請求項５】
前記経路の拡張および前記確率の再計算は、前記距離変化が所定の距離閾値を超えている場合に実行されることを特徴とする請求項４に記載のナビゲーション装置。
【請求項６】
経路の確率は、特定の方位変化と距離変化との少なくとも１つが前記経路を形成する特定のナビゲート可能なルートに沿った移動に対応する確率を判定し、および、この確率を、前記経路を形成する他のナビゲート可能なルートに沿った移動に対応する他の方位変化と距離変化との少なくとも１つについて計算された確率で乗じることによって、判定されることを特徴とする請求項１乃至５の何れか１項に記載のナビゲーション装置。
【請求項７】
前記プロセッサは、前記ナビゲーション装置が経路を移動した前記確率が所定の確率閾値を下回る場合に、さらなる拡張および計算から当該経路を破棄するように構成されることを特徴とする請求項１乃至６の何れか１項に記載のナビゲーション装置。
【請求項８】
経路が破棄される前記確率閾値は、前記経路がＮ個の最も可能性のある経路の１つでない場合であることを特徴とする請求項７に記載のナビゲーション装置。
【請求項９】
前記プロセッサは、前記経路の拡張数が所定の拡張閾値を超える場合に、さらなる拡張および計算から前記最高確率を有する経路でない各経路を破棄するように構成されることを特徴とする請求項１乃至８の何れか１項に記載のナビゲーション装置。
【請求項１０】
前記プロセッサは、単一の可能性のある経路しか存在しない場合に、メモリにおける前記シード位置を前記現在位置に設定するように構成されることを特徴とする請求項１乃至９の何れか１項に記載のナビゲーション装置。
【請求項１１】
前記プロセッサは、前記経路が分岐する初期のシード地点の前にあるルートの経路確率への寄与を無視するように構成されることを特徴とする請求項１乃至１０の何れか１項に記載のナビゲーション装置。
【請求項１２】
前記位置センサは、加速度、速度、距離、時間および角度変化のうち少なくとも１つを測定するセンサを備えることを特徴とする請求項１乃至１１の何れか１項に記載のナビゲーション装置。
【請求項１３】
前記位置センサは、加速度計とジャイロスコープとの少なくとも何れか１つを備えることを特徴とする請求項１２に記載のナビゲーション装置。
【請求項１４】
前記出力装置は、ディスプレイとスピーカとの少なくとも何れか１つであることを特徴とする請求項１乃至１３の何れか１項に記載のナビゲーション装置。
【請求項１５】
シード位置とエリア内でナビゲート可能なルートのマップとを備えるマップデータを内部に格納したメモリと接続されたプロセッサによって実行される場合に、前記プロセッサに、移動距離および方位変化に関する位置データを受信させ、前記位置データからマップデータの複数のナビゲート可能なルートの１つにおける現在位置を推定させ、出力装置に現在位置を出力させる命令を格納したデータキャリアであって、前記推定する工程は、
前記移動距離および前記方位変化を使用して、前記ナビゲーション装置が移動していたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、前記ナビゲーション装置が当該経路を移動した確率を各経路に割り当て、
方位変化について、各経路を拡張し、前記ナビゲーション装置が当該経路を移動した確率を再計算し、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる
ことを含むことを特徴とするデータキャリア。
【請求項１６】
位置データを使用してナビゲート可能なルートのマップにおける現在位置を推定する方法であって、前記方法は、
前記位置データから移動距離および方位変化を判定する工程と、
前記移動距離および前記方位変化を使用して、前記移動されていたかもしれない前記ナビゲート可能なルートに沿った可能性のある経路を前記シード位置から推定し、当該経路が移動された確率を各経路に割り当てる工程と、
方位変化について、各経路を拡張し、ナビゲーション装置が当該経路を移動した確率を再計算する工程と、
前記現在位置を、最高確率を有する経路上で現在の予測位置になるように割り当てる工程と、
を有することを特徴とする方法。
【図１】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図５Ａ】
【図５Ｂ】
【図６】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図５Ａ】
【図５Ｂ】
【図６】
【公表番号】特表２０１３−５０７６２２（Ｐ２０１３−５０７６２２Ａ）
【公表日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【出願番号】特願２０１２−５３３４８５（Ｐ２０１２−５３３４８５）
【出願日】平成２１年１０月１２日（２００９．１０．１２）
【国際出願番号】ＰＣＴ／ＥＰ２００９／０６３２６３
【国際公開番号】ＷＯ２０１１／０４４９２３
【国際公開日】平成２３年４月２１日（２０１１．４．２１）
【出願人】（３０７０４３２２３）トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【Ｆターム（参考）】
【公表日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【出願日】平成２１年１０月１２日（２００９．１０．１２）
【国際出願番号】ＰＣＴ／ＥＰ２００９／０６３２６３
【国際公開番号】ＷＯ２０１１／０４４９２３
【国際公開日】平成２３年４月２１日（２０１１．４．２１）
【出願人】（３０７０４３２２３）トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【Ｆターム（参考）】
[ Back to top ]