走行ルートの記述を簡略化するための方法
本発明は、複数のルート点（１−９，１０４）のリストによって表されている走行ルート（１００）の記述を簡略化するための方法（２００）に関する。本方法（２００）は、各ルート点（１０４）がディジタル道路マップに由来する走行ルート（１００）の異なる部分セグメント（１０２）を表す、複数のルート点（１０４）によって表されているルート点（１０４）のリストによってマッピングされる走行ルート（１００）を読み込むステップ（２１０）と、走行ルート（１００）を表す、複数のルート点（１−９）の変更されたリストを取得するために、所定のアルゴリズムに応じて複数のルート点（１０４）のリストを変更するステップ（２２０）と、走行ルート（１００）の記述の簡略化を達成するために、複数のルート点（１−９）の変更されたリストを記憶するステップ（２３０）とを備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、請求項１又は９に記載されている方法、請求項１０に記載されているナビゲーション装置並びに請求項１１に記載されているコンピュータプログラム製品に関する。
【０００２】
従来のナビゲーションシステムにおいては、更新に起因してディジタルマップを交換することが必要になる可能性がある。この場合には、マップ内の走行ルートを特徴付ける既存の複数のルート点を場合によっては、新たなマップにおいて相応の経路区間にもはやマッピングできない可能性があるので、例えば、ナビゲーション装置に記憶されている頻繁に走行する既存のルートをもはや使用できなくなる可能性がある。例えばこのことは、新たな道路マップが、以前に使用していたディジタルマップを提供したマップメーカが使用するものとは異なる地理的な格子網を使用する別のマップメーカに由来することによって生じる。そのような場合には、記憶されている複数の基準点又はルート点が新たな地図において、実際の道路区間上には存在しない位置にマッピングされる虞がある。従って、それにもかかわらず、記憶されているそれらの走行ルートを更に使用できるようにするために、走行ルートを新たに使用すべき道路マップに適合させることが必要になる。また、例えば、所定の位置における建設計画によって、新たに使用すべきディジタルマップにおいて考慮されている道路の拡張部又はロータリーが新たに建設された場合には、マップの更新によって道路が僅かにずれることも考えられる。従来技術においては、新たなディジタルマップを考慮して、記憶されている走行ルートのその種の転用をどのように実施することができるかについてのアプローチは公知ではない。
【０００３】
従来技術においては、道路網のディジタルマップ内のある場所の決定（いわゆるコーディング）、及び第２のディジタルマップにおける同一の場所の（機械による）同定を意味する、いわゆる位置参照（Location Referencing）しか公知でない。場所、いわゆるロケーションとして、個々の点、線形の区間部分、部分グラフ又は抽象的な領域が考えられる。従来の位置参照方法は、線形の区間部分に焦点を合わせて発展した。道路グラフの道路網又は部分グラフを転用するための複数のアプローチが存在しており、それらのアプローチにおいては道路網が複数の線形のロケーションに分割される。しかしながらこれまでは、この分割がどのように機能するかについての正確な記述は存在していない。更には、それらのアプローチはまだテストされていない。
【０００４】
発明の概要
これを背景として、本発明によって、独立請求項に記載されている方法、更にはこの方法を使用するナビゲーション装置、相応のコンピュータプログラム製品が提供される。有利な実施の形態は、それぞれの従属請求項及び以下の説明より明らかになる。
【０００５】
本発明によって、複数のルート点のリストによって表されている走行ルートの記述を簡略化するための方法が提供される。本方法は以下のステップを備えている：
−各ルート点がディジタル道路マップに由来する走行ルートの異なる部分セグメントを表す複数のルート点によって表されているルート点のリストによってマッピングされる走行ルートを読み込むステップ；
−走行ルートを表す、複数のルート点の変更されたリストを取得するために、所定のアルゴリズムに応じて複数のルート点のリストを変更するステップ；
−走行ルートの記述の簡略化を達成するために、複数のルート点の変更されたリストを記憶するステップ。
【０００６】
更に、本発明によって、複数のルート点のリストに由来する車両の走行ルートをデコーディングするための方法が提供される。本方法は以下のステップを備えている：
−ルート点の各々がディジタル道路マップに由来するデコーディングすべき走行ルートの別個の部分区間を表す、複数のルート点を読み込むステップ；
−ディジタル道路マップを受信するステップ；
−複数のルート点の中から少なくとも二つのルート点を選択し、選択されたルート点をディジタル道路マップ内の、車両によって選択すべき走行ルートの考えられる部分区間を表す異なる第１の区間にマッピングするステップ；
−ディジタル道路マップに由来する個々の第１の区間の長さに基づき求められる第１の総経路長を決定するステップ；
−選択されたルート点を、車両によって選択すべき走行ルートの考えられる部分区間を表す、ディジタル道路マップの異なる第２の区間にマッピングするステップ；
−ディジタル道路マップに由来する個々の第２の区間の長さに基づき求められる第２の総経路長を決定するステップ；
−所定の第１の経路長が所定の第２の経路長よりも短い場合には、ルート点を第１の区間に対応付けるステップ。
【０００７】
更に本発明によって、本発明による方法のステップを実施又は使用するために構成されているナビゲーション装置が提供される。
【０００８】
ナビゲーション装置の形の本発明のこの変形の形態によっても、本発明が基礎とする課題を迅速且つ効果的に解決することができる。
【０００９】
本発明においてナビゲーション装置とは、一つ又は複数のセンサ信号を処理する電気機器又は計算ユニットであると解される。ナビゲーション装置は、ハードウェア及び／又はソフトウェアによって構成することができるインタフェースを有することができる。ハードウェアによって構成されている場合には、インタフェースは例えば、ナビゲーション装置の種々の機能を含んでいるいわゆるシステムＡＳＩＣの一部であって良い。しかしながらまた、インタフェースが固有の集積回路であること、又は少なくとも部分的に離散的な構成素子から構成されることも考えられる。ソフトウェアによって構成されている場合には、インタフェースは例えば、マイクロコントローラ上に別のソフトウェアモジュールと並列して設けられるソフトウェアモジュールであっても良い。
【００１０】
また、半導体メモリ、ハードディスクメモリ又は光学メモリのような機械読取可能な担体上に記憶されており、プログラムがナビゲーション装置において実行される場合に、本発明の実施の形態による方法を実施するために使用される、プログラムコードを有するコンピュータプログラム製品も有利である。
【００１１】
本発明は、走行できる走行ルートが僅かなルート点によって表される場合には、道路網の部分グラフの簡単な区分が実現されるという知識を基礎としている。可能な限り僅かなルート点によって走行ルートをそのように表すことを実現するために、先ず、走行ルートのコーディングの際に、可能な限り少ないルート点を有しているリストが、選択すべき又は選択された走行ルートを可能な限り正確に記述するように、ルート点の低減が行われるべきである。このために所定のアルゴリズムが使用され、例えば、非常に短い経路長を有している、道路網における走行ルートの部分区間を表すルート点が消去されることによってルート点のリストの変更が行われる。また複数のルート点のリストを簡略化するために、第２、第３・・・の各ルート点をリストから消去することができ、これによって、確かに走行ルートの記述は比較的不正確になるが、しかしながら、残りのルート点がディジタルマップに転用され、例えば走行ルートの部分区間としてそれらのルート点間の最短のコネクションが求められる場合には、依然として十分に正確に再構成することができる。このようにして、ディジタルマップを基礎として求められた所望の走行ルートも第２のディジタルマップに転用することできる。この場合には、走行ルートのデコーディングがルート点のリストに基づき、例えば、複数のルート点がリストから第２のディジタルマップに転用されるように実施される。例えば相応の複数のルート点を形成する地理的な座標が第２のディジタルマップにおいて道路又は走行可能な経路上に位置していないことが確認されると、このルート点を直近の道路又は直近の経路にシフトさせることができる。この場合には、第２のディジタルマップを使用して、ルート点間又は相応のシフトされたルート点間の最短コネクションを形成する、第２のディジタルマップに由来する道路又は経路が所望の走行ルートの部分区間として選択されるように所望の走行ルートをデコーディングすることができる。
【００１２】
本発明は、第１に、従来から既知の頻繁に走行した走行ルートを、非常に簡単にメモリスペースを節約して、前述の複数のルート点の短いリストによって記憶することができるという利点を提供する。第２に、所望の走行ルート又は走行すべき走行ルートの別のディジタルマップへの転用を簡略化するために、複数のルート点のリストを非常に効率的に使用することができる。この場合、前述の第１の態様においても前述の第２の態様においても、本発明を使用又は実現するために僅かな算術的又は回路技術的な手間しか必要とされない。
【００１３】
本発明の一つの実施の形態によれば、走行ルートを読み込むステップにおいて、地理的な座標を表す複数のルート点を読み込むことができる。本発明のその種の実施の形態は、地理的な座標の記述によって複数のルート点を非常に正確に決定できるという利点を提供する。複数のルート点を生成した第１のディジタルマップの格子網が、複数のルート点のリストが使用されるべき第２のディジタルマップと異なる場合であっても、非常に簡単な相応の変換を介して、ルート点の相応のシフト及び一義的な対応付けを新たな第２のディジタルマップにおいても実施することができる。
【００１４】
また本発明の別の実施の形態では、変更のステップにおいて、所定の経路長よりも短い経路区間をマッピングする走行ルートの部分セグメントを表す複数のルート点がリストから除去されるアルゴリズムを使用することができる。本発明のその種の実施の形態は、重要な情報が失われることを心配する必要なく、ルート点のリストにおけるルート点の数を低減することを非常に簡単に実現することができる。例えば、１００ｍよりも短いディジタル道路マップ内の経路又は道路をマッピングする走行ルートの部分セグメントを表す全てのルート点をリストから除去することができる。
【００１５】
更に好適には、変更のステップにおいて、その適用時に各ｎ（但し変数ｎは自然数である）番目のルート点がリストから除去されるアルゴリズムが使用される。本発明のその種の実施の形態は、所望の走行ルートの再構成の実現性が顕著に劣化することなく、複数のルート点をルート点のリストから簡単なやり方で除去することができるという利点を提供する。
【００１６】
本発明の別の実施の形態においては、方法は更に、複数の別のルート点を受信するステップを備えることができ、それら別のルート点は走行ルートのある区間の代替区間の部分セグメントを表す。変更のステップにおいては、それら複数の別のルート点の内の少なくとも一つがルート点のリストに記録される。特に有利には、変更のステップにおいて、複数の付加的なルート点が走行ルートに関するルート点のリストに記録される。それら複数の付加的なルート点は走行ルートのある区間の代替区間の部分セグメントを表す。本発明のその種の実施の形態は、簡単なやり方で種々の代替的な走行ルートを記憶することができ、その際に、それらの代替的な走行ルートの各々に関してルート点の固有の別個のリストを生成する必要が無いという利点を提供する。
【００１７】
付加的又は代替的に、本方法を車両の走行中に繰り返し実施することもできる。本方法の先行の実施サイクルの終了後の、本方法の後続の実施サイクルにおける読み込みのステップにおいて、車両の走行中に、車両の目下の位置を表す少なくとも一つの新たなルート点が読み込まれ、本方法の反復的な実施によって車両の走行ルートが更新される。本発明のその種の実施の形態は、事前に規定された走行ルートに対してのみ最適化を実施できるのではなく、走行中にも目下走行している走行ルートを記録することもできるという利点を提供する。走行ルートの記録を、メモリスペースを節約するやり方でルート点のリストに格納することができ、このリストを上記と同様のやり方で最適化することができる。
【００１８】
また、ディジタル道路マップのこれまで走行したことのない部分区間への走行ルートも効率的に記憶できるようにするために、本発明の別の実施の形態においては、本方法は更に、車両の目下の位置を検出するステップを備えることができる。更に本方法は、検出された車両の目下の位置を、ルート点によって表される走行ルートの部分区間を用いて調整することができる。リストの変更のステップにおいては、走行ルートの目下走行している部分区間を表すルート点がリストに記憶されていない場合には、走行ルートの目下走行している部分区間を表すルート点がリストに追加される。
【００１９】
以下では、添付の図面に基づいて本発明を例示的により詳細に説明する。
【図面の簡単な説明】
【００２０】
【図１】出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図２】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図３】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図４】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図５】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図６】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図７】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図８】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図９】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図１０】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図１１】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図１２】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図１３】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図１４】方法としての本発明の実施例のフローチャートを示す。
【図１５】方法としての本発明の別の実施例のフローチャートを示す。
【図１６】ナビゲーション装置を使用する本発明の実施例のブロック回路図を示す。
【発明を実施するための形態】
【００２１】
図中、同一又は同様の構成要素には同一又は同様の参照番号を付してあるので、反復的な説明は省略する。更には、図面における各図、それら図面の説明並びに請求項は、多数の特徴の組み合わせを含んでいる。それらの特徴を個別に考察できること、また、それらの特徴をここでは明示的に示さない別の組み合わせに統合できることも当業者には明らかである。更に以下の説明においては、種々の尺度及び寸法を使用して本発明を説明するが、本発明はそれらの尺度及び寸法に限定されるべきものではない。更に、本発明による方法のステップを繰り返し実施することができ、また上記の順序とは異なる順序で実施することもできる。第１の特徴／ステップと第２の特徴／ステップとの間に「及び／又は」の接続詞を含む実施例の場合、この実施例は、第１の実施の形態によれば第１の特徴／第１のステップも、第２の特徴／第２のステップも有するものであり、また別の実施の形態によれば、第１の特徴／第１のステップのみを有するか、第２の特徴／第２のステップのみを有するものと解される。
【００２２】
本発明の重要な目標は、ドライバの自然なルート選択によって生じ、従って通常の場合は関連性がある、道路グラフの（特に所望の走行ルートに関する）部分グラフを参照するための方式を発展させることである。この場合には特に、部分グラフを次第に許容可能な時間内でデコーディングすることができ、それによって、ここで提案される方式が用途に適したものとなるようにするために、走行区間又は走行ルートの参照すべき区間への分割に関する問題が解決されるべきである。
【００２３】
従って、以下において提案するアプローチは、例えばドライバの走行した区間から次第に生じる、道路グラフの部分グラフの参照に関係する。参照すべき区間への分割は、例えば出発すべき区間に平行に行われる。ここで提案されるアプローチの重要な態様は、道路網内の固定の複数の位置、いわゆるルーティングポイント又はルート点を決定することであり、この決定に関して親子関係が考慮される。続いて、これらのルート点をリストに記憶することができるので、親子関係も一緒に記憶される。連続するルート点は参照すべき区間を限定する。連続する二つのルート点の位置及びそれらルート点間の距離の選択には、第２のマップにおける同定を実現する（実現すべき）所定の条件が課される。この同定ではルート点のペアから出発して、全体の部分グラフが次第に、幅優先探索のような相応のアルゴリズムを用いてデコーディングされる。
【００２４】
以下では、参照方式のコーディング及びデコーディングを詳細に説明する。連続するルート点の選択及びその距離の選択には、第２のマップにおける同定を実現すべき所定の条件が課される。例えば、ここでは、標準ＡＧＯＲＡ−Ｃからのいわゆる「ルーティング・ポイント・ルール」を使用することができる。
【００２５】
先ず、ルート点への走行ルートのコーディングを本発明の種々の実施例に基づき詳細に説明する。コーディングに関連する本発明の重要な態様は、ルート点の選択及び位置決めである。どの属性又は方式でもってこのルート点が記述されるかは第２のステップである。以下では、走行した区間に沿ったルート点を選択するための二つの異なるアプローチを説明する。
【００２６】
第１のヴァリエーションの説明は図１から出発する。この図１においては、出発地Ａから目的地Ｂまでの走行ルート１００が複数のルート点によってマーキングされているディジタルマップが示されている。ドライバは位置Ａから出発して、方向Ｂに向かって走行することを想定する。各リンク１０２、即ち、ドライバが走行する、二つの限定的な点によって表されている各道路部分には、黒い点によって表されているルート点１０４が一つセットされる。リンク１０２上の位置決めは、ＭＥＩ−ＬＩＮ方式において使用されるような特別な品質判定基準によって行われるか、常にリンクの中心にあるような固定的な規則に従い行われる。所定の区間を走行した後に、又は、ドライバが未知のリンクから既知のリンクに進入すると、冗長的なルート点１０４は以下のように除去される。先ず例えば、図２において線を引いて消されているルート点のような、「短い」リンク上の全てのルート点１０２が消去され、これは連続するルート点に関して上述の条件がその都度満たされている限り継続される。属性「短い」をメートル単位の長さ（例えば実際の区間に関して、郊外の道路では１００ｍよりも短い走行ルート、又は市街地の道路では５０ｍよりも短い走行ルート）に依存させることができるか、又は、複雑な交差点への所属に依存させることもできる。
【００２７】
第２のステップにおいては、図３から見て取れるように、別のルート点１０２が除去される。この除去は例えば、各２番目の点１０４’を反復的に除去するような、所定のやり方で行われる。他方では、ルート点１０４に関する品質判定基準を適用することも考えられ、この品質判定基準は、第２のマップにおいてより良好に再び発見することができる点１０４を高く評価する。それらの点としては例えば、道路の交差点の非常に近傍に位置しており、その結果、第２のマップにおいても相応の位置を容易に求めることができる点１０４が考えられる。この場合には、走行ルートの再構成にとって「高位」又は「重要」と見なされるそれらの点が除去されることを回避することができる。続いて、「高位」と評価されず、従って「重要」と見なされなかったルート点の少なくとも一部の除去がこの品質判定基準に従い行われ、これは、上述の条件が満たされる限り継続される。図４は、出発地Ａから目的地Ｂまでに残存する、従って必要なルート点（番号２から５が付されている）の例を示す。
【００２８】
更には各リンクについて、そのリンクが既に走行されたか否かが記憶されることが望ましい。ドライバが部分的に既知であり且つ部分的に既知でないルートを選択すると、例えば、「新しい」リンク（即ち走行ルートの部分区間）にのみルート点１０８がセットされれば良い。これは同様のやり方で図５に示されたように行われ、既にセットされたルート点１０４に対する新たなルート点１０８の相応の親子関係のみが、そのような場合に更新される。新たなルート点１０８の個々のルート点が例えば前述のステップの内の一つに応じて除去された後には、図６に例示的に示されているように、二つの新たなルート点（参照番号６及び７が付されている）が存在する。全体として、図７に示されているようなシナリオが生じる。残存するルート点はリストにエントリされて記憶される。このリストには、個々のルート点の関係、それらルート点の親及び子もマークされている。
【００２９】
本発明により提案されるアプローチの第２の考えられるヴァリエーションにおいては、ルート点がリンク１０２を実際に走行した直後に規定される。従って、このヴァリエーションは「as-you-go」選択と称することもできる。ドライバが例えば、図８に示されているような地点Ａから出発すると（この際、目的地Ｂはまだ既知である必要はなく、従って図８においては示されていない）、先ず、「短くない」各リンク上にルート点１０４がセットされる。例えば上記において挙げた判定基準を満たしている、（所望の）走行ルートのリンク１０２又は部分区間を「短い」と見なすことができる。ドライバがそれぞれのリンク１０２を通過し、新たなリンク１０２に進入すると、連続するルート点１０４の除去に関する条件が検査されることによって、事前にセットされたルート点１０４を除去することができるか否かが検査される。即ち、図８以降において示されている例においては、図９に示されているように、事前にセットされたルート点１１０を除去することができる。図１０は例えば最初に必要とされるルート点１を示す。何故ならば、他方では、地点Ａとルート点１に続くルート点１１２との間に、ほぼ等しい長さであり、従って考えられるデコーディング規則を損なわせる虞がある二つの異なる経路が存在するからである。このアプローチを広範に継続することができるので、図１１に示されているような必要なルート点を有している、出発地Ａと目的地Ｂとの間の走行ルートを構築することができる。従って、走行ルートの未知の部分区画又は部分区間に関する構成は走行ルートが完全に既知である場合の構成と全く同様に機能し、また、親子関係は、前述の第１のヴァリエーションと同様に機能すると考えられる。
【００３０】
所望の走行ルートを表し、例えば前述の構成に応じて作成された複数のルート点のリストが取得されると、より大きな手間を必要とすることなく、この走行ルートを第２のディジタル道路マップにも転用（即ちデコーディング）することができる。デコーディングはルート点の識別に合わせられており、これによって、二つのルート点間の参照すべき部分区画を次第に識別することができる。先ず、例えば、車両に関して地理的な座標から求められた実際の位置の近傍における、ルート点のリストに由来するルート点の親子のペアから出発する。親及び子に関して、それらを記述する属性又はメソッドに応じて、図１２に示されているような複数の考えられる位置が存在する。この例における点６及び点７はそれぞれ二つの代替点を有しており、それらは図１２において参照番号６’及び６’’又は７’及び７’’が付されている。続いて、全ての代替点間のルート（即ち６’と７’との間のルート、６’’と７’との間のルート、６’’との間のルート又は６’’と７’’との間のルート）が算出される。ルート点の一つのペアの間にのみ、（ルート点ペア間の親子関係に関する属性として長さが記憶された場合には）例えば転用された長さに近似する長さを有しているルート（即ち経路長）が存在する場合には、適切なルート点が識別されている。
【００３１】
その他の場合には、一つのペアが一義的に識別できるまで、子の子を用いて走行するか、又は、選択された子についての別の親を用いて走行する。この場合、この開始ペアは他の関連するルート点の識別を容易にする。図１３の例においては、６’’及び７’’を除去できるようにするために、例えば点２’と点８’との間のルート、又は６’と８’との間のルートを算出することも考えられる。何故ならば、それら二つの点に関しては、それぞれ一つの考えられる位置しか存在しないからである。
【００３２】
代替点の除去に関する手間を低減するために、ＭＥＩ−ＬＩＮのような方式を使用し、ルート点を参照し、代替点を早期に排除することも考えられる。即ち、開始ペアが識別されている場合には、別の点が所定のアルゴリズム、例えば幅優先探索に従い次第に除去され、全体の部分グラフを許容可能な時間内にデコーディングすることができる。更に、ルーティングアルゴリズムは道路クラスに相対的な重みを考慮すべきであり、これによってより重要な道路が優先される。
【００３３】
図１４に示した実施例によれば、本発明は、複数のルート点のリストによって表されている走行ルートの記述を簡略化するための方法２００を提供し、この方法は、複数のルート点によって表されているルート点のリストによってマッピングされる走行ルートを読み込むステップ２１０を備えている。各ルート点はディジタル道路マップに由来する走行ルートの異なる部分セグメントを表す。更に方法２００は、走行ルートを表す、ルート点の変更されたリストを取得するために、所定のアルゴリズムに応じてルート点のリストを変更するステップ２２０を備えている。最後に方法は、走行ルートの記述の簡略化を達成するために、ルート点の変更されたリストを記憶するステップ２３０を備えている。
【００３４】
図１５に示した別の実施例によれば、本発明は、複数のルート点のリストに由来する車両の走行ルートをデコーディングするための方法３００を提供し、この方法は、ルート点のリストを読み込むステップ３１０を備えている。各ルート点はディジタル道路マップに由来するデコーディングすべき走行ルートの別個の部分区間を表す。更に方法は、ディジタル道路マップを受信するステップ３２０と、複数のルート点の内の少なくとも二つのルート点を選択し、選択されたルート点をディジタル道路マップ内の種々の第１の区間にマッピングするステップ３３０とを備えている。種々の第１の区間は、車両によって選択すべき走行ルートの考えられる部分区間を表す。更に方法３００は、全体の第１の経路長を決定するステップ３４０を備えている。全体の第１の経路長は、ディジタルマップに由来する個々の第１の区間の長さに基づき求められる。また、方法３００の別のステップにおいては、選択されたルート点をディジタル道路マップの種々の第２の区間にマッピングするステップ３５０が実施される。種々の第２の区間は、車両によって選択すべき走行ルートの考えられる部分区間を表す。方法３００の別のステップ３６０においては、全体の第２の経路長の決定が実施される。全体の第２の経路長は、ディジタルマップに由来する個々の第２の区間の長さに基づき求められる。最後に、方法３００のステップ３７０においては、所定の第１の経路長が所定の第２の経路長よりも短い場合には、複数のルート点の第１の区間への対応付けが実施される。
【００３５】
更に本発明を、図１６に示されているように、車両４００のナビゲーション装置４１０において実施することができる。ナビゲーション４１０は衛星ナビゲーション信号用の受信器４２０によってデータを受信し、それらのデータを、例えばディジタルマップのためのメモリ４３０からナビゲーション装置４１０にロードされるディジタルマップと結合することができる。続いて、ナビゲーション装置４１０においては、複数のルート点のリストを記憶することができるので、メモリ４３０におけるディジタル道路網の更新の際には、所望の走行ルートをナビゲーション装置４１０に記憶されている複数のルート点のリストに基づき実現することができる。
【技術分野】
【０００１】
本発明は、請求項１又は９に記載されている方法、請求項１０に記載されているナビゲーション装置並びに請求項１１に記載されているコンピュータプログラム製品に関する。
【０００２】
従来のナビゲーションシステムにおいては、更新に起因してディジタルマップを交換することが必要になる可能性がある。この場合には、マップ内の走行ルートを特徴付ける既存の複数のルート点を場合によっては、新たなマップにおいて相応の経路区間にもはやマッピングできない可能性があるので、例えば、ナビゲーション装置に記憶されている頻繁に走行する既存のルートをもはや使用できなくなる可能性がある。例えばこのことは、新たな道路マップが、以前に使用していたディジタルマップを提供したマップメーカが使用するものとは異なる地理的な格子網を使用する別のマップメーカに由来することによって生じる。そのような場合には、記憶されている複数の基準点又はルート点が新たな地図において、実際の道路区間上には存在しない位置にマッピングされる虞がある。従って、それにもかかわらず、記憶されているそれらの走行ルートを更に使用できるようにするために、走行ルートを新たに使用すべき道路マップに適合させることが必要になる。また、例えば、所定の位置における建設計画によって、新たに使用すべきディジタルマップにおいて考慮されている道路の拡張部又はロータリーが新たに建設された場合には、マップの更新によって道路が僅かにずれることも考えられる。従来技術においては、新たなディジタルマップを考慮して、記憶されている走行ルートのその種の転用をどのように実施することができるかについてのアプローチは公知ではない。
【０００３】
従来技術においては、道路網のディジタルマップ内のある場所の決定（いわゆるコーディング）、及び第２のディジタルマップにおける同一の場所の（機械による）同定を意味する、いわゆる位置参照（Location Referencing）しか公知でない。場所、いわゆるロケーションとして、個々の点、線形の区間部分、部分グラフ又は抽象的な領域が考えられる。従来の位置参照方法は、線形の区間部分に焦点を合わせて発展した。道路グラフの道路網又は部分グラフを転用するための複数のアプローチが存在しており、それらのアプローチにおいては道路網が複数の線形のロケーションに分割される。しかしながらこれまでは、この分割がどのように機能するかについての正確な記述は存在していない。更には、それらのアプローチはまだテストされていない。
【０００４】
発明の概要
これを背景として、本発明によって、独立請求項に記載されている方法、更にはこの方法を使用するナビゲーション装置、相応のコンピュータプログラム製品が提供される。有利な実施の形態は、それぞれの従属請求項及び以下の説明より明らかになる。
【０００５】
本発明によって、複数のルート点のリストによって表されている走行ルートの記述を簡略化するための方法が提供される。本方法は以下のステップを備えている：
−各ルート点がディジタル道路マップに由来する走行ルートの異なる部分セグメントを表す複数のルート点によって表されているルート点のリストによってマッピングされる走行ルートを読み込むステップ；
−走行ルートを表す、複数のルート点の変更されたリストを取得するために、所定のアルゴリズムに応じて複数のルート点のリストを変更するステップ；
−走行ルートの記述の簡略化を達成するために、複数のルート点の変更されたリストを記憶するステップ。
【０００６】
更に、本発明によって、複数のルート点のリストに由来する車両の走行ルートをデコーディングするための方法が提供される。本方法は以下のステップを備えている：
−ルート点の各々がディジタル道路マップに由来するデコーディングすべき走行ルートの別個の部分区間を表す、複数のルート点を読み込むステップ；
−ディジタル道路マップを受信するステップ；
−複数のルート点の中から少なくとも二つのルート点を選択し、選択されたルート点をディジタル道路マップ内の、車両によって選択すべき走行ルートの考えられる部分区間を表す異なる第１の区間にマッピングするステップ；
−ディジタル道路マップに由来する個々の第１の区間の長さに基づき求められる第１の総経路長を決定するステップ；
−選択されたルート点を、車両によって選択すべき走行ルートの考えられる部分区間を表す、ディジタル道路マップの異なる第２の区間にマッピングするステップ；
−ディジタル道路マップに由来する個々の第２の区間の長さに基づき求められる第２の総経路長を決定するステップ；
−所定の第１の経路長が所定の第２の経路長よりも短い場合には、ルート点を第１の区間に対応付けるステップ。
【０００７】
更に本発明によって、本発明による方法のステップを実施又は使用するために構成されているナビゲーション装置が提供される。
【０００８】
ナビゲーション装置の形の本発明のこの変形の形態によっても、本発明が基礎とする課題を迅速且つ効果的に解決することができる。
【０００９】
本発明においてナビゲーション装置とは、一つ又は複数のセンサ信号を処理する電気機器又は計算ユニットであると解される。ナビゲーション装置は、ハードウェア及び／又はソフトウェアによって構成することができるインタフェースを有することができる。ハードウェアによって構成されている場合には、インタフェースは例えば、ナビゲーション装置の種々の機能を含んでいるいわゆるシステムＡＳＩＣの一部であって良い。しかしながらまた、インタフェースが固有の集積回路であること、又は少なくとも部分的に離散的な構成素子から構成されることも考えられる。ソフトウェアによって構成されている場合には、インタフェースは例えば、マイクロコントローラ上に別のソフトウェアモジュールと並列して設けられるソフトウェアモジュールであっても良い。
【００１０】
また、半導体メモリ、ハードディスクメモリ又は光学メモリのような機械読取可能な担体上に記憶されており、プログラムがナビゲーション装置において実行される場合に、本発明の実施の形態による方法を実施するために使用される、プログラムコードを有するコンピュータプログラム製品も有利である。
【００１１】
本発明は、走行できる走行ルートが僅かなルート点によって表される場合には、道路網の部分グラフの簡単な区分が実現されるという知識を基礎としている。可能な限り僅かなルート点によって走行ルートをそのように表すことを実現するために、先ず、走行ルートのコーディングの際に、可能な限り少ないルート点を有しているリストが、選択すべき又は選択された走行ルートを可能な限り正確に記述するように、ルート点の低減が行われるべきである。このために所定のアルゴリズムが使用され、例えば、非常に短い経路長を有している、道路網における走行ルートの部分区間を表すルート点が消去されることによってルート点のリストの変更が行われる。また複数のルート点のリストを簡略化するために、第２、第３・・・の各ルート点をリストから消去することができ、これによって、確かに走行ルートの記述は比較的不正確になるが、しかしながら、残りのルート点がディジタルマップに転用され、例えば走行ルートの部分区間としてそれらのルート点間の最短のコネクションが求められる場合には、依然として十分に正確に再構成することができる。このようにして、ディジタルマップを基礎として求められた所望の走行ルートも第２のディジタルマップに転用することできる。この場合には、走行ルートのデコーディングがルート点のリストに基づき、例えば、複数のルート点がリストから第２のディジタルマップに転用されるように実施される。例えば相応の複数のルート点を形成する地理的な座標が第２のディジタルマップにおいて道路又は走行可能な経路上に位置していないことが確認されると、このルート点を直近の道路又は直近の経路にシフトさせることができる。この場合には、第２のディジタルマップを使用して、ルート点間又は相応のシフトされたルート点間の最短コネクションを形成する、第２のディジタルマップに由来する道路又は経路が所望の走行ルートの部分区間として選択されるように所望の走行ルートをデコーディングすることができる。
【００１２】
本発明は、第１に、従来から既知の頻繁に走行した走行ルートを、非常に簡単にメモリスペースを節約して、前述の複数のルート点の短いリストによって記憶することができるという利点を提供する。第２に、所望の走行ルート又は走行すべき走行ルートの別のディジタルマップへの転用を簡略化するために、複数のルート点のリストを非常に効率的に使用することができる。この場合、前述の第１の態様においても前述の第２の態様においても、本発明を使用又は実現するために僅かな算術的又は回路技術的な手間しか必要とされない。
【００１３】
本発明の一つの実施の形態によれば、走行ルートを読み込むステップにおいて、地理的な座標を表す複数のルート点を読み込むことができる。本発明のその種の実施の形態は、地理的な座標の記述によって複数のルート点を非常に正確に決定できるという利点を提供する。複数のルート点を生成した第１のディジタルマップの格子網が、複数のルート点のリストが使用されるべき第２のディジタルマップと異なる場合であっても、非常に簡単な相応の変換を介して、ルート点の相応のシフト及び一義的な対応付けを新たな第２のディジタルマップにおいても実施することができる。
【００１４】
また本発明の別の実施の形態では、変更のステップにおいて、所定の経路長よりも短い経路区間をマッピングする走行ルートの部分セグメントを表す複数のルート点がリストから除去されるアルゴリズムを使用することができる。本発明のその種の実施の形態は、重要な情報が失われることを心配する必要なく、ルート点のリストにおけるルート点の数を低減することを非常に簡単に実現することができる。例えば、１００ｍよりも短いディジタル道路マップ内の経路又は道路をマッピングする走行ルートの部分セグメントを表す全てのルート点をリストから除去することができる。
【００１５】
更に好適には、変更のステップにおいて、その適用時に各ｎ（但し変数ｎは自然数である）番目のルート点がリストから除去されるアルゴリズムが使用される。本発明のその種の実施の形態は、所望の走行ルートの再構成の実現性が顕著に劣化することなく、複数のルート点をルート点のリストから簡単なやり方で除去することができるという利点を提供する。
【００１６】
本発明の別の実施の形態においては、方法は更に、複数の別のルート点を受信するステップを備えることができ、それら別のルート点は走行ルートのある区間の代替区間の部分セグメントを表す。変更のステップにおいては、それら複数の別のルート点の内の少なくとも一つがルート点のリストに記録される。特に有利には、変更のステップにおいて、複数の付加的なルート点が走行ルートに関するルート点のリストに記録される。それら複数の付加的なルート点は走行ルートのある区間の代替区間の部分セグメントを表す。本発明のその種の実施の形態は、簡単なやり方で種々の代替的な走行ルートを記憶することができ、その際に、それらの代替的な走行ルートの各々に関してルート点の固有の別個のリストを生成する必要が無いという利点を提供する。
【００１７】
付加的又は代替的に、本方法を車両の走行中に繰り返し実施することもできる。本方法の先行の実施サイクルの終了後の、本方法の後続の実施サイクルにおける読み込みのステップにおいて、車両の走行中に、車両の目下の位置を表す少なくとも一つの新たなルート点が読み込まれ、本方法の反復的な実施によって車両の走行ルートが更新される。本発明のその種の実施の形態は、事前に規定された走行ルートに対してのみ最適化を実施できるのではなく、走行中にも目下走行している走行ルートを記録することもできるという利点を提供する。走行ルートの記録を、メモリスペースを節約するやり方でルート点のリストに格納することができ、このリストを上記と同様のやり方で最適化することができる。
【００１８】
また、ディジタル道路マップのこれまで走行したことのない部分区間への走行ルートも効率的に記憶できるようにするために、本発明の別の実施の形態においては、本方法は更に、車両の目下の位置を検出するステップを備えることができる。更に本方法は、検出された車両の目下の位置を、ルート点によって表される走行ルートの部分区間を用いて調整することができる。リストの変更のステップにおいては、走行ルートの目下走行している部分区間を表すルート点がリストに記憶されていない場合には、走行ルートの目下走行している部分区間を表すルート点がリストに追加される。
【００１９】
以下では、添付の図面に基づいて本発明を例示的により詳細に説明する。
【図面の簡単な説明】
【００２０】
【図１】出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図２】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図３】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図４】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図５】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図６】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図７】本発明の別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図８】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図９】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図１０】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図１１】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図１２】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図１３】本発明の更に別の実施例が複数のルート点又はそれらルート点の相応のリストに適用された、出発地から目的地までの走行ルートが複数のルート点によってマーキングされているディジタルマップを示す。
【図１４】方法としての本発明の実施例のフローチャートを示す。
【図１５】方法としての本発明の別の実施例のフローチャートを示す。
【図１６】ナビゲーション装置を使用する本発明の実施例のブロック回路図を示す。
【発明を実施するための形態】
【００２１】
図中、同一又は同様の構成要素には同一又は同様の参照番号を付してあるので、反復的な説明は省略する。更には、図面における各図、それら図面の説明並びに請求項は、多数の特徴の組み合わせを含んでいる。それらの特徴を個別に考察できること、また、それらの特徴をここでは明示的に示さない別の組み合わせに統合できることも当業者には明らかである。更に以下の説明においては、種々の尺度及び寸法を使用して本発明を説明するが、本発明はそれらの尺度及び寸法に限定されるべきものではない。更に、本発明による方法のステップを繰り返し実施することができ、また上記の順序とは異なる順序で実施することもできる。第１の特徴／ステップと第２の特徴／ステップとの間に「及び／又は」の接続詞を含む実施例の場合、この実施例は、第１の実施の形態によれば第１の特徴／第１のステップも、第２の特徴／第２のステップも有するものであり、また別の実施の形態によれば、第１の特徴／第１のステップのみを有するか、第２の特徴／第２のステップのみを有するものと解される。
【００２２】
本発明の重要な目標は、ドライバの自然なルート選択によって生じ、従って通常の場合は関連性がある、道路グラフの（特に所望の走行ルートに関する）部分グラフを参照するための方式を発展させることである。この場合には特に、部分グラフを次第に許容可能な時間内でデコーディングすることができ、それによって、ここで提案される方式が用途に適したものとなるようにするために、走行区間又は走行ルートの参照すべき区間への分割に関する問題が解決されるべきである。
【００２３】
従って、以下において提案するアプローチは、例えばドライバの走行した区間から次第に生じる、道路グラフの部分グラフの参照に関係する。参照すべき区間への分割は、例えば出発すべき区間に平行に行われる。ここで提案されるアプローチの重要な態様は、道路網内の固定の複数の位置、いわゆるルーティングポイント又はルート点を決定することであり、この決定に関して親子関係が考慮される。続いて、これらのルート点をリストに記憶することができるので、親子関係も一緒に記憶される。連続するルート点は参照すべき区間を限定する。連続する二つのルート点の位置及びそれらルート点間の距離の選択には、第２のマップにおける同定を実現する（実現すべき）所定の条件が課される。この同定ではルート点のペアから出発して、全体の部分グラフが次第に、幅優先探索のような相応のアルゴリズムを用いてデコーディングされる。
【００２４】
以下では、参照方式のコーディング及びデコーディングを詳細に説明する。連続するルート点の選択及びその距離の選択には、第２のマップにおける同定を実現すべき所定の条件が課される。例えば、ここでは、標準ＡＧＯＲＡ−Ｃからのいわゆる「ルーティング・ポイント・ルール」を使用することができる。
【００２５】
先ず、ルート点への走行ルートのコーディングを本発明の種々の実施例に基づき詳細に説明する。コーディングに関連する本発明の重要な態様は、ルート点の選択及び位置決めである。どの属性又は方式でもってこのルート点が記述されるかは第２のステップである。以下では、走行した区間に沿ったルート点を選択するための二つの異なるアプローチを説明する。
【００２６】
第１のヴァリエーションの説明は図１から出発する。この図１においては、出発地Ａから目的地Ｂまでの走行ルート１００が複数のルート点によってマーキングされているディジタルマップが示されている。ドライバは位置Ａから出発して、方向Ｂに向かって走行することを想定する。各リンク１０２、即ち、ドライバが走行する、二つの限定的な点によって表されている各道路部分には、黒い点によって表されているルート点１０４が一つセットされる。リンク１０２上の位置決めは、ＭＥＩ−ＬＩＮ方式において使用されるような特別な品質判定基準によって行われるか、常にリンクの中心にあるような固定的な規則に従い行われる。所定の区間を走行した後に、又は、ドライバが未知のリンクから既知のリンクに進入すると、冗長的なルート点１０４は以下のように除去される。先ず例えば、図２において線を引いて消されているルート点のような、「短い」リンク上の全てのルート点１０２が消去され、これは連続するルート点に関して上述の条件がその都度満たされている限り継続される。属性「短い」をメートル単位の長さ（例えば実際の区間に関して、郊外の道路では１００ｍよりも短い走行ルート、又は市街地の道路では５０ｍよりも短い走行ルート）に依存させることができるか、又は、複雑な交差点への所属に依存させることもできる。
【００２７】
第２のステップにおいては、図３から見て取れるように、別のルート点１０２が除去される。この除去は例えば、各２番目の点１０４’を反復的に除去するような、所定のやり方で行われる。他方では、ルート点１０４に関する品質判定基準を適用することも考えられ、この品質判定基準は、第２のマップにおいてより良好に再び発見することができる点１０４を高く評価する。それらの点としては例えば、道路の交差点の非常に近傍に位置しており、その結果、第２のマップにおいても相応の位置を容易に求めることができる点１０４が考えられる。この場合には、走行ルートの再構成にとって「高位」又は「重要」と見なされるそれらの点が除去されることを回避することができる。続いて、「高位」と評価されず、従って「重要」と見なされなかったルート点の少なくとも一部の除去がこの品質判定基準に従い行われ、これは、上述の条件が満たされる限り継続される。図４は、出発地Ａから目的地Ｂまでに残存する、従って必要なルート点（番号２から５が付されている）の例を示す。
【００２８】
更には各リンクについて、そのリンクが既に走行されたか否かが記憶されることが望ましい。ドライバが部分的に既知であり且つ部分的に既知でないルートを選択すると、例えば、「新しい」リンク（即ち走行ルートの部分区間）にのみルート点１０８がセットされれば良い。これは同様のやり方で図５に示されたように行われ、既にセットされたルート点１０４に対する新たなルート点１０８の相応の親子関係のみが、そのような場合に更新される。新たなルート点１０８の個々のルート点が例えば前述のステップの内の一つに応じて除去された後には、図６に例示的に示されているように、二つの新たなルート点（参照番号６及び７が付されている）が存在する。全体として、図７に示されているようなシナリオが生じる。残存するルート点はリストにエントリされて記憶される。このリストには、個々のルート点の関係、それらルート点の親及び子もマークされている。
【００２９】
本発明により提案されるアプローチの第２の考えられるヴァリエーションにおいては、ルート点がリンク１０２を実際に走行した直後に規定される。従って、このヴァリエーションは「as-you-go」選択と称することもできる。ドライバが例えば、図８に示されているような地点Ａから出発すると（この際、目的地Ｂはまだ既知である必要はなく、従って図８においては示されていない）、先ず、「短くない」各リンク上にルート点１０４がセットされる。例えば上記において挙げた判定基準を満たしている、（所望の）走行ルートのリンク１０２又は部分区間を「短い」と見なすことができる。ドライバがそれぞれのリンク１０２を通過し、新たなリンク１０２に進入すると、連続するルート点１０４の除去に関する条件が検査されることによって、事前にセットされたルート点１０４を除去することができるか否かが検査される。即ち、図８以降において示されている例においては、図９に示されているように、事前にセットされたルート点１１０を除去することができる。図１０は例えば最初に必要とされるルート点１を示す。何故ならば、他方では、地点Ａとルート点１に続くルート点１１２との間に、ほぼ等しい長さであり、従って考えられるデコーディング規則を損なわせる虞がある二つの異なる経路が存在するからである。このアプローチを広範に継続することができるので、図１１に示されているような必要なルート点を有している、出発地Ａと目的地Ｂとの間の走行ルートを構築することができる。従って、走行ルートの未知の部分区画又は部分区間に関する構成は走行ルートが完全に既知である場合の構成と全く同様に機能し、また、親子関係は、前述の第１のヴァリエーションと同様に機能すると考えられる。
【００３０】
所望の走行ルートを表し、例えば前述の構成に応じて作成された複数のルート点のリストが取得されると、より大きな手間を必要とすることなく、この走行ルートを第２のディジタル道路マップにも転用（即ちデコーディング）することができる。デコーディングはルート点の識別に合わせられており、これによって、二つのルート点間の参照すべき部分区画を次第に識別することができる。先ず、例えば、車両に関して地理的な座標から求められた実際の位置の近傍における、ルート点のリストに由来するルート点の親子のペアから出発する。親及び子に関して、それらを記述する属性又はメソッドに応じて、図１２に示されているような複数の考えられる位置が存在する。この例における点６及び点７はそれぞれ二つの代替点を有しており、それらは図１２において参照番号６’及び６’’又は７’及び７’’が付されている。続いて、全ての代替点間のルート（即ち６’と７’との間のルート、６’’と７’との間のルート、６’’との間のルート又は６’’と７’’との間のルート）が算出される。ルート点の一つのペアの間にのみ、（ルート点ペア間の親子関係に関する属性として長さが記憶された場合には）例えば転用された長さに近似する長さを有しているルート（即ち経路長）が存在する場合には、適切なルート点が識別されている。
【００３１】
その他の場合には、一つのペアが一義的に識別できるまで、子の子を用いて走行するか、又は、選択された子についての別の親を用いて走行する。この場合、この開始ペアは他の関連するルート点の識別を容易にする。図１３の例においては、６’’及び７’’を除去できるようにするために、例えば点２’と点８’との間のルート、又は６’と８’との間のルートを算出することも考えられる。何故ならば、それら二つの点に関しては、それぞれ一つの考えられる位置しか存在しないからである。
【００３２】
代替点の除去に関する手間を低減するために、ＭＥＩ−ＬＩＮのような方式を使用し、ルート点を参照し、代替点を早期に排除することも考えられる。即ち、開始ペアが識別されている場合には、別の点が所定のアルゴリズム、例えば幅優先探索に従い次第に除去され、全体の部分グラフを許容可能な時間内にデコーディングすることができる。更に、ルーティングアルゴリズムは道路クラスに相対的な重みを考慮すべきであり、これによってより重要な道路が優先される。
【００３３】
図１４に示した実施例によれば、本発明は、複数のルート点のリストによって表されている走行ルートの記述を簡略化するための方法２００を提供し、この方法は、複数のルート点によって表されているルート点のリストによってマッピングされる走行ルートを読み込むステップ２１０を備えている。各ルート点はディジタル道路マップに由来する走行ルートの異なる部分セグメントを表す。更に方法２００は、走行ルートを表す、ルート点の変更されたリストを取得するために、所定のアルゴリズムに応じてルート点のリストを変更するステップ２２０を備えている。最後に方法は、走行ルートの記述の簡略化を達成するために、ルート点の変更されたリストを記憶するステップ２３０を備えている。
【００３４】
図１５に示した別の実施例によれば、本発明は、複数のルート点のリストに由来する車両の走行ルートをデコーディングするための方法３００を提供し、この方法は、ルート点のリストを読み込むステップ３１０を備えている。各ルート点はディジタル道路マップに由来するデコーディングすべき走行ルートの別個の部分区間を表す。更に方法は、ディジタル道路マップを受信するステップ３２０と、複数のルート点の内の少なくとも二つのルート点を選択し、選択されたルート点をディジタル道路マップ内の種々の第１の区間にマッピングするステップ３３０とを備えている。種々の第１の区間は、車両によって選択すべき走行ルートの考えられる部分区間を表す。更に方法３００は、全体の第１の経路長を決定するステップ３４０を備えている。全体の第１の経路長は、ディジタルマップに由来する個々の第１の区間の長さに基づき求められる。また、方法３００の別のステップにおいては、選択されたルート点をディジタル道路マップの種々の第２の区間にマッピングするステップ３５０が実施される。種々の第２の区間は、車両によって選択すべき走行ルートの考えられる部分区間を表す。方法３００の別のステップ３６０においては、全体の第２の経路長の決定が実施される。全体の第２の経路長は、ディジタルマップに由来する個々の第２の区間の長さに基づき求められる。最後に、方法３００のステップ３７０においては、所定の第１の経路長が所定の第２の経路長よりも短い場合には、複数のルート点の第１の区間への対応付けが実施される。
【００３５】
更に本発明を、図１６に示されているように、車両４００のナビゲーション装置４１０において実施することができる。ナビゲーション４１０は衛星ナビゲーション信号用の受信器４２０によってデータを受信し、それらのデータを、例えばディジタルマップのためのメモリ４３０からナビゲーション装置４１０にロードされるディジタルマップと結合することができる。続いて、ナビゲーション装置４１０においては、複数のルート点のリストを記憶することができるので、メモリ４３０におけるディジタル道路網の更新の際には、所望の走行ルートをナビゲーション装置４１０に記憶されている複数のルート点のリストに基づき実現することができる。
【特許請求の範囲】
【請求項１】
複数のルート点（１−９，１０４）のリストによって表されている走行ルート（１００）の記述を簡略化するための方法（２００）において、
該方法（２００）は、
各ルート点（１０４）がディジタル道路マップに由来する走行ルート（１００）の異なる部分セグメント（１０２）を表す、複数のルート点（１０４）によって表されているルート点（１０４）のリストによってマッピングされる走行ルート（１００）を読み込むステップ（２１０）と、
前記走行ルート（１００）を表す、複数のルート点（１−９）の変更されたリストを取得するために、所定のアルゴリズムに応じて前記複数のルート点（１０４）のリストを変更するステップ（２２０）と、
前記走行ルート（１００）の記述の簡略化を達成するために、前記複数のルート点（１−９）の変更されたリストを記憶するステップ（２３０）と、
を備えていることを特徴とする、走行ルート（１００）の記述を簡略化するための方法（２００）。
【請求項２】
前記走行ルート（１００）を読み込むステップ（２１０）において、地理的な座標を表す複数のルート点（１０４）を読み込む、請求項１に記載の方法（２００）。
【請求項３】
前記変更のステップ（２２０）においてアルゴリズムを使用し、該アルゴリズムの適用時に、所定の経路長よりも短い経路区間をマッピングする、前記走行ルート（１００）の部分セグメント（１０２）を表す複数のルート点（１０４）をリストから除去する、請求項１又は２に記載の方法（２００）。
【請求項４】
前記変更のステップ（２２０）においてアルゴリズムを使用し、該アルゴリズムの適用時に各ｎ（但し変数ｎは自然数である）番目のルート点（１０４）を前記リストから除去する、請求項１乃至３のいずれか一項に記載の方法（２００）。
【請求項５】
前記方法（２００）は更に、複数の別のルート点（１０８）を受信するステップを備えており、
前記別のルート点（１０８）は前記走行ルート（１００）のある区間の代替区間の部分セグメント（１０４）を表し、
前記変更のステップ（２２０）において、前記別のルート点（１０８）の内の少なくとも一つを前記ルート点（１−９）のリストに記録する、請求項１乃至４のいずれか一項に記載の方法（２００）。
【請求項６】
前記変更のステップ（２２０）において、複数の付加的なルート点（１０８）を前記走行ルート（１００）に関する前記ルート点（１−９）の前記リストに記録し、
前記付加的なルート点（１０８）は前記走行ルート（１００）のある区間の代替区間の部分セグメント（１０２）を表す、請求項１乃至５のいずれか一項に記載の方法（２００）。
【請求項７】
前記方法（２００）を車両（４００）の走行中に繰り返し実施し、
前記方法（２００）の先行の実施サイクルの終了後の、前記方法（２００）の後続の実施サイクルにおける前記読み込みのステップ（２１０）において、前記車両（４００）の走行中に、前記車両（４００）の目下の位置を表す少なくとも一つの新たなルート点（１１０）を読み込み、
前記方法（２００）の反復的な実施によって前記車両（４００）の前記走行ルートを更新する、請求項１乃至６のいずれか一項に記載の方法。
【請求項８】
前記方法（２００）は更に前記車両（４００）の目下の位置を検出するステップを備えており、
前記方法（２００）は更に、検出された前記車両（４００）の目下の位置を、ルート点（１１０）によって表される前記走行ルート（１００）の部分区間（１０２）を用いて調整するステップを備えており、
前記リストを変更するステップ（２２０）において、前記走行ルート（１００）の目下走行している部分区間（１０２）を表すルート点（１１０）が前記リストに記憶されていない場合には、前記走行ルート（１００）の目下走行している部分区間（１０２）を表すルート点（１１０）を前記リストに追加する、請求項１乃至７のいずれか一項に記載の方法。
【請求項９】
複数のルート点（１−９）のリストに由来する車両の走行ルート（１００）をデコーディングするための方法（３００）において、
該方法（３００）は、
各ルート点がディジタル道路マップに由来するデコーディングすべき走行ルートの別個の部分区間を表す、複数のルート点を読み込むステップ（３１０）と、
ディジタル道路マップを受信するステップ（３２０）と、
複数のルート点の中から少なくとも二つのルート点を選択し、選択されたルート点をディジタル道路マップ内の、前記車両によって選択すべき走行ルートの考えられる部分区間を表す種々の第１の区間にマッピングするステップ（３３０）と、
前記ディジタル道路マップに由来する個々の第１の区間の長さに基づき求められる第１の総経路長を決定するステップ（３４０）と、
前記選択されたルート点を、前記車両によって選択すべき前記走行ルートの考えられる部分区間を表す、前記ディジタル道路マップの種々の第２の区間にマッピングするステップ（３５０）と、
前記ディジタル道路マップに由来する個々の第２の区間の長さに基づき求められる第２の総経路長を決定するステップ（３６０）と、
決定された第１の経路長が決定された第２の経路長よりも短い場合には、前記ルート点を前記第１の区間に対応付けるステップ（３７０）と、
を備えていることを特徴とする、車両の走行ルート（１００）をデコーディングするための方法（３００）。
【請求項１０】
請求項１乃至９のいずれか一項に記載の方法（２００，３００）のステップを実施するために構成されているナビゲーション装置（４１０）。
【請求項１１】
プログラムがナビゲーション装置（４１０）において実行される場合に、請求項１乃至９のいずれか一項に記載の方法（２００，３００）を実施する、機械読み取り可能な媒体に記憶されているプログラムコードを備えているコンピュータプログラム製品。
【請求項１】
複数のルート点（１−９，１０４）のリストによって表されている走行ルート（１００）の記述を簡略化するための方法（２００）において、
該方法（２００）は、
各ルート点（１０４）がディジタル道路マップに由来する走行ルート（１００）の異なる部分セグメント（１０２）を表す、複数のルート点（１０４）によって表されているルート点（１０４）のリストによってマッピングされる走行ルート（１００）を読み込むステップ（２１０）と、
前記走行ルート（１００）を表す、複数のルート点（１−９）の変更されたリストを取得するために、所定のアルゴリズムに応じて前記複数のルート点（１０４）のリストを変更するステップ（２２０）と、
前記走行ルート（１００）の記述の簡略化を達成するために、前記複数のルート点（１−９）の変更されたリストを記憶するステップ（２３０）と、
を備えていることを特徴とする、走行ルート（１００）の記述を簡略化するための方法（２００）。
【請求項２】
前記走行ルート（１００）を読み込むステップ（２１０）において、地理的な座標を表す複数のルート点（１０４）を読み込む、請求項１に記載の方法（２００）。
【請求項３】
前記変更のステップ（２２０）においてアルゴリズムを使用し、該アルゴリズムの適用時に、所定の経路長よりも短い経路区間をマッピングする、前記走行ルート（１００）の部分セグメント（１０２）を表す複数のルート点（１０４）をリストから除去する、請求項１又は２に記載の方法（２００）。
【請求項４】
前記変更のステップ（２２０）においてアルゴリズムを使用し、該アルゴリズムの適用時に各ｎ（但し変数ｎは自然数である）番目のルート点（１０４）を前記リストから除去する、請求項１乃至３のいずれか一項に記載の方法（２００）。
【請求項５】
前記方法（２００）は更に、複数の別のルート点（１０８）を受信するステップを備えており、
前記別のルート点（１０８）は前記走行ルート（１００）のある区間の代替区間の部分セグメント（１０４）を表し、
前記変更のステップ（２２０）において、前記別のルート点（１０８）の内の少なくとも一つを前記ルート点（１−９）のリストに記録する、請求項１乃至４のいずれか一項に記載の方法（２００）。
【請求項６】
前記変更のステップ（２２０）において、複数の付加的なルート点（１０８）を前記走行ルート（１００）に関する前記ルート点（１−９）の前記リストに記録し、
前記付加的なルート点（１０８）は前記走行ルート（１００）のある区間の代替区間の部分セグメント（１０２）を表す、請求項１乃至５のいずれか一項に記載の方法（２００）。
【請求項７】
前記方法（２００）を車両（４００）の走行中に繰り返し実施し、
前記方法（２００）の先行の実施サイクルの終了後の、前記方法（２００）の後続の実施サイクルにおける前記読み込みのステップ（２１０）において、前記車両（４００）の走行中に、前記車両（４００）の目下の位置を表す少なくとも一つの新たなルート点（１１０）を読み込み、
前記方法（２００）の反復的な実施によって前記車両（４００）の前記走行ルートを更新する、請求項１乃至６のいずれか一項に記載の方法。
【請求項８】
前記方法（２００）は更に前記車両（４００）の目下の位置を検出するステップを備えており、
前記方法（２００）は更に、検出された前記車両（４００）の目下の位置を、ルート点（１１０）によって表される前記走行ルート（１００）の部分区間（１０２）を用いて調整するステップを備えており、
前記リストを変更するステップ（２２０）において、前記走行ルート（１００）の目下走行している部分区間（１０２）を表すルート点（１１０）が前記リストに記憶されていない場合には、前記走行ルート（１００）の目下走行している部分区間（１０２）を表すルート点（１１０）を前記リストに追加する、請求項１乃至７のいずれか一項に記載の方法。
【請求項９】
複数のルート点（１−９）のリストに由来する車両の走行ルート（１００）をデコーディングするための方法（３００）において、
該方法（３００）は、
各ルート点がディジタル道路マップに由来するデコーディングすべき走行ルートの別個の部分区間を表す、複数のルート点を読み込むステップ（３１０）と、
ディジタル道路マップを受信するステップ（３２０）と、
複数のルート点の中から少なくとも二つのルート点を選択し、選択されたルート点をディジタル道路マップ内の、前記車両によって選択すべき走行ルートの考えられる部分区間を表す種々の第１の区間にマッピングするステップ（３３０）と、
前記ディジタル道路マップに由来する個々の第１の区間の長さに基づき求められる第１の総経路長を決定するステップ（３４０）と、
前記選択されたルート点を、前記車両によって選択すべき前記走行ルートの考えられる部分区間を表す、前記ディジタル道路マップの種々の第２の区間にマッピングするステップ（３５０）と、
前記ディジタル道路マップに由来する個々の第２の区間の長さに基づき求められる第２の総経路長を決定するステップ（３６０）と、
決定された第１の経路長が決定された第２の経路長よりも短い場合には、前記ルート点を前記第１の区間に対応付けるステップ（３７０）と、
を備えていることを特徴とする、車両の走行ルート（１００）をデコーディングするための方法（３００）。
【請求項１０】
請求項１乃至９のいずれか一項に記載の方法（２００，３００）のステップを実施するために構成されているナビゲーション装置（４１０）。
【請求項１１】
プログラムがナビゲーション装置（４１０）において実行される場合に、請求項１乃至９のいずれか一項に記載の方法（２００，３００）を実施する、機械読み取り可能な媒体に記憶されているプログラムコードを備えているコンピュータプログラム製品。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公表番号】特表２０１３−５１３０９６（Ｐ２０１３−５１３０９６Ａ）
【公表日】平成２５年４月１８日（２０１３．４．１８）
【国際特許分類】
【出願番号】特願２０１２−５４１４１７（Ｐ２０１２−５４１４１７）
【出願日】平成２２年１１月２６日（２０１０．１１．２６）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０６８２６８
【国際公開番号】ＷＯ２０１１／０６７１６９
【国際公開日】平成２３年６月９日（２０１１．６．９）
【出願人】（３９００２３７１１）ローベルト ボツシユ ゲゼルシヤフト ミツト ベシユレンクテル ハフツング (2,908)
【氏名又は名称原語表記】ＲＯＢＥＲＴ ＢＯＳＣＨ ＧＭＢＨ
【住所又は居所原語表記】Ｓｔｕｔｔｇａｒｔ， Ｇｅｒｍａｎｙ
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
【公表日】平成２５年４月１８日（２０１３．４．１８）
【国際特許分類】
【出願日】平成２２年１１月２６日（２０１０．１１．２６）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０６８２６８
【国際公開番号】ＷＯ２０１１／０６７１６９
【国際公開日】平成２３年６月９日（２０１１．６．９）
【出願人】（３９００２３７１１）ローベルト ボツシユ ゲゼルシヤフト ミツト ベシユレンクテル ハフツング (2,908)
【氏名又は名称原語表記】ＲＯＢＥＲＴ ＢＯＳＣＨ ＧＭＢＨ
【住所又は居所原語表記】Ｓｔｕｔｔｇａｒｔ， Ｇｅｒｍａｎｙ
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
[ Back to top ]