ルート決定方法およびデバイス
【課題】評価関数に基づいてルートを決定するための手段を提供すること。
【解決手段】目的地、特に道路網上の目的地(22;82;132)までのルートを決定するための方法であって、第1のステップにおいて、第1のグラフ(20)に基づいて、複数の頂点(23、24、25、27、28、32、33)に対する評価関数の値を決定することであって、頂点(21〜33)に対する評価関数の値は、頂点(21〜33)から目的地(22;82;132)までのルートに関連するコストの下限を表現している、ことと、第2のステップにおいて、第1のステップにおいて決定された評価関数の値に基づいて、第2のグラフ(20;20’)上で、出発点(21;81;131)から目的地(22;82;132)までのルート(61)を検索することと、を包含する、方法。
【解決手段】目的地、特に道路網上の目的地(22;82;132)までのルートを決定するための方法であって、第1のステップにおいて、第1のグラフ(20)に基づいて、複数の頂点(23、24、25、27、28、32、33)に対する評価関数の値を決定することであって、頂点(21〜33)に対する評価関数の値は、頂点(21〜33)から目的地(22;82;132)までのルートに関連するコストの下限を表現している、ことと、第2のステップにおいて、第1のステップにおいて決定された評価関数の値に基づいて、第2のグラフ(20;20’)上で、出発点(21;81;131)から目的地(22;82;132)までのルート(61)を検索することと、を包含する、方法。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ルート決定に関し、より具体的には、評価関数に基づいて、例えば、道路網上のルートを決定するための方法に関する。有利にも、本発明の方法およびシステムは、ルート検索に利用され得、特に道路網におけるルートを(例えば、車両上で)検索するために利用され得る。
【背景技術】
【0002】
所与の出発点から所与の目的地までの良いルート(好適には最適なルート)を見つけることは、カーナビゲーションシステムまたはルーティング情報を提供するその他のシステムの鍵となる特徴のうちの1つである。本明細書の全体にわたって、用語「最適なルート(optimum route)」は、最小のコストのルートに対して用いられ、ルートのコストは、ルートによって通過(traverse)されるグラフのエッジおよび頂点のコストの和によって決定される。例えば、道路網においてルートが決定されるとき、ルートのコストは、通過される道路のセグメントのコスト、および道路のセグメントの接合部に関連するコストに対応する。使用されるコストモデルに依存して、コストは、距離、移動時間、および/またはユーザの選好度を反映し得る。同様に、例えば用語「良いルート(good route)」は、少ないコストに関連するルートを意味する(すなわち、ルートの移動に対して生じるコストに関して、ルートの品質が測定される)。一連のエッジおよび一連の頂点(グラフのエッジが相互接続している)によって定義される所与のグラフに対し、様々なコストモデルが定義され得る。例えば、ナビゲーションシステムにおいて、様々なコストモデルは、様々な最適化の基準(例えば、最速ルート、最短ルート、トンネルの回避、ハイウェイの回避、フェリーの回避、有料道路の回避、等)、ならびにこれらのオプションおよび選好度の組み合わせに対応し得る。
【0003】
(関連技術)
グラフ上で最適なルートまたは良いルートを見つけるためのいくつかの標準的なアルゴリズムが、当該技術分野において公知であり、それらのうちで最も有名なものは、DijkstraアルゴリズムおよびA*−アルゴリズムである。
【0004】
Dijkstraアルゴリズムにおいては、道路網(または、より一般的にはグラフ)は、エッジの伸縮(relaxation)または延長(expansion)によって、ルートの出発点から出発して探索される。道路網の様々な頂点は、頂点と出発点とを結ぶルートに関連する順序にしたがって訪問される。グラフのエッジの延長において、目的地に到達したとき、出発点から目的地までの最適なルートが見つけられ、Dijkstraアルゴリズムが終了する。
【0005】
A*−アルゴリズムは、Dijkstraアルゴリズムの改変であり、このA*−アルゴリズムは、グラフの頂点に対する評価関数を利用する。所与の頂点に対する評価関数は、所与の頂点と目的地とを結ぶ最適なルートに関連するコストに対する評価を提供する。ルート検索においては、様々な経路が、出発点からそれまでの頂点までに生じたコストの和および頂点に対する評価関数の値によって与えられる優先順位にしたがって、ランク付けされる。評価関数が、頂点と目的地とを結ぶ最適なルートのコストを決して過大評価することがない場合、A*−アルゴリズムが最適経路問題に対する正しい解を見つけることが公知である。従来、評価関数は、単純な幾何学的基準(例えば、直線距離(air distance))に基づいて、決定される。
【0006】
カーナビゲーションのためのルート検索は、しばしば、ターン制限に適応するために、道路網の双対グラフ(双対グラフの頂点は、道路網の道路セグメントを表現している)に対して実行される。多くの用途において、ルート検索は、今日では、追加的な便利な特徴(例えば、いくつかの代替ルートを決定すること、ユーザの選好度に適応すること、動的なルーティング、等)を提供することが期待されている。ルート検索を実行するための双対グラフと上述の追加的な特徴との両方は、格納空間および計算時間の要件の観点から見てコストが高い。
【発明の開示】
【発明が解決しようとする課題】
【0007】
したがって、当該技術分野においては、ルート検索の複雑さを減少させることを可能にするルートを決定するための改良された方法およびデバイスに対する必要性が存在する。特に、当該技術分野においては、適度な格納空間および/または計算時間の要件を有するルートを決定するための改良された方法およびデバイスに対する必要性が存在する。
【課題を解決するための手段】
【0008】
本発明にしたがうと、この必要性は、独立請求項によって定義される方法およびデバイスによって対処される。従属請求項は、好適または有利な実施形態を定義する。
【0009】
本発明の一局面にしたがうと、ルートを決定するための方法が提供される。この方法は、第1のステップにおいて、第1のグラフに基づいて評価関数の値を決定することであって、頂点に対する評価関数の値は、その頂点から目的地までのルートに関連するコストの下限を表現している、ことと、第2のステップにおいて、第1のステップにおいて決定された評価関数の値に基づいて、第2のグラフ上で出発点から目的地までのルートを検索することとを含む。評価関数の値は、直線距離ベースの評価だけに基づいて決定されるのではなく、第1のグラフに基づいて決定されるので、評価関数は、この評価関数が頂点から目的地までの最短のルートに対する実際のコストを良く近似するように決定され得る。そのような近似関数は、以下では「良い(good)」近似関数として称される。そして、良い評価関数は、第2のステップにおけるその後のルート検索の複雑さを低減するために利用され得る。
【0010】
第1のステップにおいて評価関数の値を決定することは、第1のグラフ上で頂点から目的地までのルートを検索することを含み得、この検索は、第1のグラフ上でDijkstraアルゴリズムまたはA*−アルゴリズムを用いることによって実行され得る。第1のグラフ上でのルート検索は、目的地から出発して検索を出発点に向けて延長することによって実行され得る。言い換えると、第1のステップにおいて、検索方向は逆転され得る。第1のグラフ上でルート検索の間に探索される頂点に対し、第1のグラフ上でルート検索を実行することによって、評価関数の値が決定されるとき、良い評価関数が提供され得、この良い評価関数は、それぞれの頂点から目的地までの任意のルートに関連する真の最小のコストを表現し得るか、または少なくとも真の最小のコストに対する良い近似を提供し得る。この評価関数の値に基づいて、第2の検索におけるその後の検索の検索ツリーのサイズが低減され得る。
【0011】
第2のステップにおいて、評価関数の値に基づいて、前記ルートとは異なる目的地までの少なくとも1つのさらなるルートが検索または決定され得る。少なくとも1つのさらなるルートは、出発点から目的地までの代替ルート、または別の出発点から目的地までのルートのうちの少なくとも1つを含み得る。別のルートに対する検索は、例えば、車両が所定のルートから逸れたとき、または第2のグラフのエッジまたは頂点に対するコストが変化したときに開始され得、これは例えば、ユーザによって指定された回避オプション、交通情報信号、または動的なルーティングによってもたらされ得る。複数のルート検索に対する第1のステップの結果(すなわち、評価関数の値)を利用することによって、所与のルート検索に必要な平均の計算時間が、低減され得る。なぜならば、中間の結果(すなわち、評価関数の値)が繰り返し用いられ得るからである。
【0012】
第1のステップにおいて決定された評価関数の値のうちの少なくともサブセットが格納され得、第2のステップにおいて抽出され得る。
【0013】
第1のステップにおいて評価関数の値を決定することは、第1のコストモデルに基づき得、第2のステップにおいて出発点から目的地までのルートを検索することは、第2のコストモデルに基づき得る。第1および第2のコストモデルは異なり得るので、第1のモデルの適切な選択によって、第1のステップにおいて決定された評価関数の値は、いくつかの異なる第2のコストモデルに対して再利用され得る。特に、第1のコストモデルにしたがう、第1のグラフの頂点および/またはエッジに関連するコストは、第2のコストモデルにしたがう、第2のグラフの対応する頂点および/またはエッジに関連するコストの下限を表現し得る。このようにして、第1のモデルに基づいて決定された評価関数の値は、第2のコストモデルに基づくルート検索に対してでさえも、目的地までのルート上で生じるコストの有効な下からの評価を提供する。
【0014】
第1のコストモデルにしたがう第1のグラフの頂点および/またはエッジに関連するコストは、時間に関係しないものであり得る。第2のコストモデルにしたがう第2のグラフの頂点および/またはエッジは、可変であり得る。第2のコストモデルにしたがうコストは、ユーザの選好度、交通情報信号、時刻または日付のうちの少なくとも1つに基づいて変化し得る。第2のコストモデルにしたがうコストの変化は、第1のコストモデルに対して少なくとも1つの頂点および/またはエッジに対するコストを増加させることによって実施され得る。同様に、可変のコストの寄与を考慮しない第1のコストモデルが、評価関数の値を決定するために利用され得る。
【0015】
第1のグラフは、第1のグラフ上のルート検索が、例えば第1のグラフが第2のグラフよりも少ない頂点を有するように第1のグラフを定義することによって、平均で、第2のグラフ上のルート検索よりも速くなるように定義され得る。第1のグラフのそのような適切な定義によって、評価関数の値を決定する際の計算の複雑さおよび/または格納空間の要件が、低減され得る。例えば、第1のグラフの頂点は、道路網の道路セグメントを表現し得、第1のステップにおいて、道路網におけるターン制限が無視され得る。第1および第2のグラフはまた、第1のグラフのエッジが道路網の道路セグメントを表現し、第2のグラフの頂点が道路網の道路セグメントを表現するように定義され得る。すなわち、第1および第2のグラフは、互いに対する双対グラフであり得る。別の実施形態において、第1のグラフは、第2のグラフと同じものであり得る。
【0016】
方法はまた、2つ以上のステップまたは段階で実行され得る。例えば、第1のステップは、第3のグラフを定義することと、第3のグラフ上でルート検索を実行することと、第3のグラフ上でのルート検索の結果を利用し、複数の頂点に対する評価関数の値を決定することとを含み得る。先の段階の結果をその後の段階に繰り返し利用することによって、ルート検索の計算の複雑さが、さらに低減され得る。
【0017】
グラフは、道路網、コンピュータネットワーク、またはインフラストラクチャネットワークのうちの1つを表現し得る。特に、様々な実施形態にしたがう方法は、道路網上のルーティングに利用され得、車両上のナビゲーションシステムによって実行され得る。
【0018】
本発明の別の局面にしたがうと、目的地(特に、道路網上の目的地)までのルートを決定するためのデバイスが提供される。デバイスは、第1のグラフおよび第2のグラフのうちの少なくとも1つのグラフの頂点およびエッジを定義するグラフデータを格納する格納ユニット、および格納ユニットに接続され、グラフデータを抽出するプロセッサを含んでいる。プロセッサは、第1のステップにおいて、第1のグラフに基づいて、複数の頂点に対する評価関数の値を決定し、頂点に対する評価関数の値は、頂点から目的地までのルートに関連するコストの下限を表現しており、第2のステップにおいて、第1のステップにおいて決定された評価関数の値に基づいて、第2のグラフ上で出発点から目的地までのルート検索を実行する。プロセッサは、直線距離ベースの評価だけを利用するのではなく、第1のグラフに基づいて評価関数の値を決定するので、良い評価関数が決定され得、有利にも第2のステップにおいて、その後のルート検索のために装備され得る。
【0019】
プロセッサは、第1のグラフ上でルート検索を実行し、評価関数の値を決定し得る(例えば、目的地から出発し、出発点に向けて延長することによって、評価関数の値を決定し得る)。
【0020】
第2のステップにおいて、プロセッサは、第1のステップにおいて決定された評価関数の値に基づいて、目的地までの少なくとも1つのさらなるルート検索を実行することによって、第1のステップにおいて得られた結果を第2のステップにおける複数のルート検索に利用し得る。いくつかのルート検索に対して中間の結果(すなわち、評価関数の値)を再利用することによって、各ルート検索に必要な平均の計算時間は、低減され得る。
【0021】
プロセッサは、第1のステップにおいて、第1のコストモデルに基づいて、評価関数の値を決定し得、第2のステップにおいて、第2のコストモデルに基づいて、出発点から目的地までのルート検索を実行し得る。第1および第2のコストモデルは、異なり得る。特に、第1のコストモデルにしたがう第1のグラフの頂点および/またはエッジに関連するコストは、時間に関係しないものであり得、第2のコストモデルにしたがう第2のグラフの頂点および/またはエッジに関連するコストは、可変であり得る。このように、第1のコストモデルのコストが、特定の用途に対して考慮される第2のコストモデルの対応するコストの下限を表現するように、第1のコストモデルを適切に選択することによって、時間に関係しない第1のコストモデルに基づいて決定される評価関数の値は、第2のコストモデルが変化するコストを含んでいるときでさえも、異なる第2のコストモデルに対して再利用され得る。
【0022】
デバイスは、ユーザ入力を受信する入力ユニットを含み得、プロセッサは、この入力ユニットに接続され、ユーザ入力に基づいて、第2のコストモデルのコストを調整し得る。加えてまたはあるいは、デバイスは、時刻および/または日付を決定するクロックユニットを含み得、プロセッサは、このクロックユニットに接続され、時刻および/または日付に基づいて、第2のコストモデルのコストを調整し得る。加えてまたはあるいは、デバイスは、交通情報信号を受信する交通メッセージ受信器を含み得、プロセッサは、交通メッセージ受信器に接続され、交通情報信号に基づいて、第2のコストモデルのコストを調整し得る。したがって、デバイスは、ユーザの選好度に基づいて、動的なルーティングにおける時刻または日付に基づいて、または交通情報に基づいて、第2のコストモデルのコストを調整するように構成され得る。
【0023】
デバイスはまた、現在の車両の位置を決定する位置決定手段を含み得、プロセッサは、位置決定手段に接続され、現在の車両の位置を出発点から目的地までのルートと比較する。プロセッサは、比較の結果に基づいて、第2のグラフ上での現在の車両の位置から目的地までのさらなるルート検索を自動的に実行し得る。
【0024】
様々な実施形態にしたがうデバイスは、プロセッサが、本発明の局面または実施形態のうちの任意のものにしたがう方法を実行し得るように、構成され得る。
【0025】
別の局面にしたがうと、ナビゲーションシステムが提供され、このナビゲーションシステムは、目的地を指定する入力を受信する入力ユニットと、ルートに関する情報を出力する出力ユニットと、本発明の任意の一実施形態にしたがってルートを決定するデバイスとを含む。ナビゲーションシステム(このナビゲーションシステムは、携帯型のナビゲーションシステムであったり、または車両上に据え付けられたりし得る)は、車両上でルート検索が実行されることを可能にする。
【0026】
別の局面にしたがうと、データ格納媒体(このデータ格納媒体上には命令が格納されている)が提供され、この命令は、ナビゲーションシステムのプロセッサによって実行されたときに、プロセッサに、本発明の局面または実施形態のうちの任意のものにしたがう方法を実行するように命令し得る。
【0027】
本発明を説明するために、以下では本発明のいくつかの実施形態が「道路網(road network)」に関連して記載されるが、本発明の用途は、物理的な道路網に限定されない。むしろ、本発明は、ルート検索が実行され得る任意のネットワークまたはグラフに応用され得る。実施例は、フェリー接続、コンピュータネットワークにおけるデータ接続、電線、または航空機のルートを含む。
【0028】
さらに、本発明は2次元空間に埋め込まれ得るグラフに関連して記載されるが、本発明はそのようなグラフに限定されないことに留意されたい。むしろ、本発明の原理は、高次元の対象(例えば、3次元のグラフ)にも等しく応用可能である。
【0029】
本発明の応用分野のうちの1つは、道路網におけるルートの決定、特に、車両上のナビゲーションシステムの道路網におけるルートの決定であることが企図されている。
【0030】
本発明は、さらに以下の手段を提供する。
【0031】
(項目1)
目的地、特に道路網上の目的地(22;82;132)までのルートを決定するための方法であって、
第1のステップにおいて、第1のグラフ(20)に基づいて、複数の頂点(23、24、25、27、28、32、33)に対する評価関数の値を決定することであって、頂点(21〜33)に対する評価関数の値は、該頂点(21〜33)から該目的地(22;82;132)までのルートに関連するコストの下限を表現している、ことと、
第2のステップにおいて、該第1のステップにおいて決定された該評価関数の値に基づいて、第2のグラフ(20;20’)上で、出発点(21;81;131)から該目的地(22;82;132)までのルート(61)を検索することと
を包含する、方法。
【0032】
(項目2)
上記第1のステップにおいて、頂点(21〜33)に対する評価関数の値を決定することは、上記第1のグラフ(20)上で該頂点(21〜33)から上記目的地(22;82;132)までのルートを検索することを含む、項目1に記載の方法。
【0033】
(項目3)
上記頂点(21〜33)から上記目的地(22)までの上記ルートを検索することは、上記第1のグラフ(20)上でDijkstraアルゴリズムまたはA*−アルゴリズムを用いて実行される、項目2に記載の方法。
【0034】
(項目4)
上記第1のステップにおいて頂点(21〜33)に対する評価関数の値を決定することは、上記第1のグラフ上で、上記目的地(22;82;132)から出発して上記出発点(21;81;131)まで延長するルート検索を実行することを含む、項目1〜項目3のいずれか一項に記載の方法。
【0035】
(項目5)
上記第2のステップにおいて、上記評価関数の値に基づいて、上記目的地(22;82;132)までのルート(61)とは異なる少なくとも1つのさらなるルート(121;151)を検索すること
を含む、項目1〜項目4のいずれか一項に記載の方法。
【0036】
(項目6)
上記少なくとも1つのさらなるルート(121;151)は、上記出発点(21)から上記目的地(22)までの代替ルート(121;151)、または別の出発点(135)から上記目的地(132)までのルートのうちの少なくとも1つを含む、項目5に記載の方法。
【0037】
(項目7)
上記出発点(21;131)から上記目的地(22;132)までの上記ルート(61)に対する現在の位置(135)をモニタリングすることであって、上記少なくとも1つのさらなるルートの上記検索は、該現在の位置(135)の該モニタリングの結果に基づいて自動的に開始される、こと
を含む、項目5または項目6に記載の方法。
【0038】
(項目8)
上記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜45;181〜185)に関連するコストの変化をモニタリングすることであって、上記少なくとも1つのさらなるルート(121;151)の上記検索は、該変化をモニタリングした結果に基づいて自動的に開始される、こと
を含む、項目5〜項目7のいずれか一項に記載の方法。
【0039】
(項目9)
上記第1のステップにおいて決定された上記評価関数の値の少なくともサブセット(5)を格納することと、
上記第2のステップにおいて該サブセット(5)の少なくとも1つの評価関数の値を抽出することと
を含む、項目1〜項目8のいずれか一項に記載の方法。
【0040】
(項目10)
上記第1のステップにおける上記評価関数の値の上記決定は、第1のコストモデルに基づいており、上記第2のステップにおける上記出発点(21;81;131)から上記目的地(22;82;132)までの上記ルート(61)の検索は、第2のコストモデルに基づいている、項目1〜項目9のいずれか一項に記載の方法。
【0041】
(項目11)
上記第1のコストモデルにしたがう、上記第1のグラフ(20)の上記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、時間に関係しない、項目10に記載の方法。
【0042】
(項目12)
上記第2のコストモデルにしたがう、上記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストは可変である、項目10または項目11に記載の方法。
【0043】
(項目13)
ユーザの選好度、交通情報信号、時刻または日付のうちの少なくとも1つに基づいて、上記第2のコストモデルにしたがう上記コストを調整すること
を含む、項目12に記載の方法。
【0044】
(項目14)
上記調整することは、少なくとも1つの頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に対し、上記第1のコストモデルに対して
上記第2のコストモデルにしたがうコストを増加させることを含む、項目13に記載の方法。
【0045】
(項目15)
上記第1のコストモデルにしたがう上記第1のグラフ(20)の頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、上記第2のコストモデルにしたがう対応する頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストの下限を表現する、項目12〜項目14のいずれか一項に記載の方法。
【0046】
(項目16)
上記第1のグラフ(20)は、該第1のグラフ(20)上のルート検索が、平均で、該第2のグラフ(20’)上のルート検索よりも速くなるように定義される、項目1〜項目15のいずれか一項に記載の方法。
【0047】
(項目17)
上記第1のグラフ(20)は、上記第2のグラフ(20’)よりも少ない頂点(21〜33)を有している、項目1〜項目16のいずれか一項に記載の方法。
【0048】
(項目18)
上記第1のグラフの頂点は、上記道路網の道路セグメントを表現しており、上記第1のステップにおいて、該道路網上のターン制限は無視される、項目1〜項目17のいずれか一項に記載の方法。
【0049】
(項目19)
上記第1のステップにおいて、一方通行制限が考慮される、項目18に記載の方法。
【0050】
(項目20)
上記第1のグラフ(20)のエッジ(41〜55)は、道路網の道路セグメントを表現しており、上記第2のグラフ(20’)の頂点(171〜178)は、該道路網の道路セグメントを表現している、項目1〜項目17のいずれか一項に記載の方法。
【0051】
(項目21)
上記第1のグラフ(20)は、上記第2のグラフ(20’)の双対グラフによって構成される、項目20に記載の方法。
【0052】
(項目22)
上記第1のグラフ(20)は、上記第2のグラフ(20)と同じものである、項目1〜項目15のいずれか一項に記載の方法。
【0053】
(項目23)
上記第1のステップは、第3のグラフ(20”)を定義すること、該第3のグラフ(20”)上でルート検索を実行すること、および該第3のグラフ(20”)上での該ルート検索の結果を利用して、上記複数の頂点(23、24、25、27、28、32、33)に対する評価関数を決定することを含む、項目1〜項目22のいずれか一項に記載の方法。
【0054】
(項目24)
上記第1のステップにおいて頂点(23、24、25、27、28、32、33)に対する評価関数の値を決定することは、上記第1のグラフ(20)上で予め計算された情報に基づいて、該第1のグラフ(20)上で該頂点(23、24、25、27、28、32、33)から上記目的地(22)までのルートを検索することを含む、項目1〜項目23のいずれか一項に記載の方法。
【0055】
(項目25)
上記第2のステップにおいて上記ルート(61)を検索することは、上記第1のステップにおいて所与の頂点(29)に対する評価関数の値が決定されたかどうかを決定することを含み、該第1のステップにおいて評価関数の値が決定されていない場合には、該所与の頂点(29)に対する評価関数の値を決定することを含む、項目1〜項目24のいずれか一項に記載の方法。
【0056】
(項目26)
上記第1のグラフ(20)および上記第2のグラフ(20;20’)は、道路網、コンピュータネットワーク、またはインフラストラクチャネットワークのうちの1つを表現する、項目1〜項目25のいずれか一項に記載の方法。
【0057】
(項目27)
上記方法は、車両上のナビゲーションシステム(1)によって実行される、項目1〜項目26のいずれか一項に記載の方法。
【0058】
(項目28)
目的地、特に道路網上の目的地(22;82;132)までのルートを決定するためのデバイスであって、
グラフデータ(4)を格納する格納ユニット(3)であって、該グラフデータ(4)は、第1のグラフ(20)および第2のグラフ(20;20’)のうちの少なくとも1つの頂点(21〜33)およびエッジ(41〜55)を定義する、格納ユニット(3)と、
該格納ユニット(3)に接続されたプロセッサ(2)であって、該プロセッサ(2)は、該グラフデータ(4)を抽出し、該プロセッサは、第1のステップにおいて、該第1のグラフ(20)に基づいて、複数の頂点(23、24、25,27、28,32、33)に対する評価関数の値を決定し、頂点(21〜33)に対する評価関数の値は、該頂点(21〜33)から該目的地(22;82;132)までのルートに関連するコストの下限を表現しており、該プロセッサは、第2のステップにおいて、該第1のステップにおいて決定された該評価関数の値に基づいて、第2のグラフ(20;20’)上で、出発点(21;81;131)から該目的地(22;82;132)までのルート検索を実行する、プロセッサ(2)と
を備えている、デバイス。
【0059】
(項目29)
上記プロセッサ(2)は、上記第1のグラフ(20)上でルート検索を実行し、上記評価関数の値を決定する、項目28に記載のデバイス。
【0060】
(項目30)
上記プロセッサ(2)は、上記目的地(22;82;132)から出発して上記出発点(21;81;131)まで延長するルート検索を実行し、上記評価関数の値を決定する、項目28または項目29に記載のデバイス。
【0061】
(項目31)
上記第2のステップにおいて、上記プロセッサ(2)は、上記第1のステップにおいて決定された上記評価関数の値に基づいて、上記目的地(22;82;132)までの少なくとも1つのさらなるルート検索を実行する、項目28〜項目30のいずれか一項に記載のデバイス。
【0062】
(項目32)
さらなる格納ユニット(3)を含み、上記プロセッサ(2)は、該さらなる格納ユニット(3)に接続されており、上記第1のステップにおいて決定された上記評価関数の値(5)を該さらなる格納ユニット(3)に格納し、上記第2のステップを実行するために該さらなる格納ユニット(3)から該評価関数の値(5)を抽出する、項目28〜項目31のいずれか一項に記載のデバイス。
【0063】
(項目33)
上記プロセッサ(2)は、第1のコストモデルに基づいて、上記第1のステップにおいて上記評価関数の値を決定し、第2のコストモデルに基づいて、上記第2のステップにおいて上記出発点(21;81;131)から上記目的地(22;82;132)までのルート検索を実行する、項目28〜項目32のいずれか一項に記載のデバイス。
【0064】
(項目34)
上記第1のコストモデルにしたがう、上記第1のグラフ(20)の上記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは時間に関係せず、上記第2のコストモデルにしたがう、上記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストは可変である、項目33に記載のデバイス。
【0065】
(項目35)
上記第1のコストモデルにしたがう、上記第1のグラフ(20)の上記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、上記第2のコストモデルにしたがう、上記第2のグラフ(20;20’)の対応する頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストの下限を表現する、項目33または項目34に記載のデバイス。
【0066】
(項目36)
ユーザ入力を受信する入力ユニット(6)を含み、上記プロセッサ(2)は、該入力ユニット(6)に接続されており、該ユーザ入力に基づいて、上記第2のコストモデルのコストを調整する、項目33〜項目35のいずれか一項に記載のデバイス。
【0067】
(項目37)
時刻および/または日付を決定するクロックユニット(10)を含み、上記プロセッサ(2)は、該クロックユニット(10)に接続されており、該時刻および/または日付に基づいて、上記第2のコストモデルのコストを調整する、項目33〜項目36のいずれか一項に記載の方法。
【0068】
(項目38)
交通情報信号を受信する交通メッセージ受信器(9)を含み、上記プロセッサ(2)は、該交通メッセージ受信器(9)に接続されており、該交通情報信号に基づいて、上記第2のコストモデルのコストを調整する、項目33〜項目37のいずれか一項に記載の方法。
【0069】
(項目39)
上記プロセッサ(2)は、少なくとも1つの頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に対し、上記第1のコストモデルに対して上記第2のコストモデルのコストを増加させ、該第2のコストモデルのコストを調整する、項目36〜項目38のいずれか一項に記載のデバイス。
【0070】
(項目40)
現在の車両の位置(135)を決定する位置決定手段(8)を含み、上記プロセッサ(2)は、該位置決定手段(8)に接続されており、該現在の車両の位置(135)を上記出発点(21;81;131)から上記目的地(22;82;132)までの上記ルート(61)と比較し、該比較の結果に基づいて、上記第2のグラフ(20;20’)上での該現在の車両の位置(135)から該目的地(132)までのさらなるルート検索を実行する、項目28〜項目39のいずれか一項に記載のデバイス。
【0071】
(項目41)
上記第1のグラフ(20)は、該第1のグラフ(20)上のルート検索が、平均で、該第2のグラフ(20’)上のルート検索よりも速くなるように定義される、項目28〜項目40のいずれか一項に記載のデバイス。
【0072】
(項目42)
上記プロセッサ(2)は、項目1〜項目27のいずれか一項に記載の方法を実行するように構成されている、項目28〜項目41のいずれか一項に記載のデバイス。
【0073】
(項目43)
ルートを決定する項目28〜項目42のいずれか一項に記載のデバイスと、
該ルート上の情報を出力する出力ユニット(7)と
を含む、ナビゲーションシステム。
【0074】
(項目44)
データ格納媒体であって、該データ格納媒体上に命令を有しており、該命令は、ナビゲーションシステム(1)のプロセッサ(2)によって実行されたときに、該ナビゲーションシステム(1)に、項目1〜項目27のいずれか一項に記載の方法を実行するように命令する、データ格納媒体。
【0075】
(摘要)
目的地(特に、道路網上の目的地)までのルートを決定するための方法およびデバイスが提供される。この方法は、ステップ(72)において、第1のグラフに基づいて複数の頂点に対する評価関数の値を決定し、頂点から目的地までのルートに関連するコストの下限を表現する頂点に対する評価関数の値を決定することと、第2のステップ(73)において、第1のステップ(72)において決定された評価関数の値に基づいて、第2のグラフ上で出発点から目的地までのルートを検索することとを含む。
【発明を実施するための最良の形態】
【0076】
本発明の追加的な特徴および利点は、添付の図面を参照すると、好適または有利な実施形態に関する以下の詳細な記載から、より容易に理解される。
【0077】
(好適な実施形態の記載)
本明細書において以後、本発明の実施形態が、図面を参照して説明される。以下の記載は、本発明をより良く説明する目的のためにのみ与えられ、限定的な意味で解釈されるべきではないことが理解されるべきである。特に断りがない限り、以下に記載される様々な実施形態の特徴は、互いに組み合わされ得るということもまた、理解されるべきである。
【0078】
以下、本発明は、道路網を表現するグラフ上のルート検索に関連して記載されるが、本発明は、この用途に限定されず、任意のグラフまたはネットワークにおけるルートを決定するために容易に用いられ得ることに留意されたい。例えば、本発明は、電源ネットワークにおけるルート検索、信号伝送のための光学ネットワークまたは電気ネットワークにおけるルート検索、コンピュータネットワークまたはその他任意のインフラストラクチャまたはその他のネットワークにおけるルート検索に適用され得る。
【0079】
図1を参照し、本発明の一実施形態にしたがう、ナビゲーションシステム1が記載される。このナビゲーションシステム1は、本発明の一実施形態にしたがう、ルートを決定するためのデバイスを含んでいる。システムは、プロセッサ2、グラフデータ4を含む格納ユニット3、入力ユニット6、出力ユニット7、位置決定手段8(例えば、GPS受信器)、交通情報信号を受信するための交通メッセージ受信器9、ならびに時刻および/または日付を提供するクロックユニット10を含んでいる。
【0080】
プロセッサ2は、格納ユニット3に格納されたグラフデータ4によって表現されるグラフ上でルート検索を実行するように構成されている。特に、プロセッサ2は、評価関数に基づく検索方法または検索アルゴリズム(例えば、A*−アルゴリズムまたはそのバリエーション)を利用するルート検索を実行するように構成されている。格納ユニット3は、任意の適切な格納媒体(例えば、CD−ROM、CD−RW、DVD、メモリカード、または内部ハードディスク)によって構成されている。グラフデータ4は、道路網の頂点および/またはエッジに関する情報を含んでいる。例えば、グラフデータ4は、道路セグメントの端点の地理的位置に関する情報、およびこれら端点におけるその他の道路セグメントに対する接続(例えば、道路の接合部または交差部)に関する情報を含み得る。グラフデータはさらに、道路セグメントまたは道路セグメントの頂点に関連するコストに関する情報を含み得る。グラフの道路セグメントまたは道路セグメントの頂点に関連する一連のコストは、本明細書において以後、「コストモデル(cost model)」と称される。コストモデルに応じて、これらのコストは、最短ルートコストモデルに対しては道路セグメントの長さを表現し得る。あるいは、これらのコストは、最速ルートコストモデルに対しては、道路セグメントの移動時間、および接合部または交差部における、1つの道路セグメントから別の道路セグメントへと曲がるための時間を表現し得る。その他の様々なコストモデルに対応するコスト(例えば、ユーザの選好度に依存して、道路セグメントまたは道路セグメントの頂点のコスト値の増分または絶対値を表現するコスト)もまた、格納ユニット3に格納され得る。さらに、格納ユニット3はまた、複数の道路セグメントまたは道路セグメントの頂点に対する評価関数のデータ5、道路セグメントの頂点から目的地までのルートに関連するコストの下限を表現する道路セグメントの頂点に対する評価の値をも格納し得る。以下でより詳細に説明されるように、ユーザによる目的地の入力後、プロセッサ2は、評価関数のデータ5を決定し、データ5を格納ユニット3に格納する。その他の例示的な実施形態において、評価関数のデータ5はまた、グラフデータを格納する格納ユニット3とは別のさらなる格納ユニットに格納されたり、またはワーキングメモリに保持されたりし得る。一実施形態において、プロセッサ2は、ルート検索の目的地と出発点との両方に基づいて、評価関数のデータ5を決定し得る。一実施形態において、プロセッサ2は、ルート検索の出発点を、GPS受信器8によって決定された現在の車両の位置と同じ位置に設定したり、または現在の車両の位置に基づいて決定された位置と同じ位置に設定したりし得る。
【0081】
目的地に関する情報およびユーザの選好度は、入力ユニット6を介して、システム1に入力され得、この入力ユニット6は、例えば、タッチスクリーン、キーパッド、またはマイクロフォンおよび音声認識デバイスとして構成され得る。プロセッサ2は、入力ユニット6を介して入力された情報を評価し、ルートの検索を実行したり、またはユーザの選好度に基づいてコストモデルのコストを調整したりし得る。出発点から目的地までのルートに関する情報は、出力ユニット6を介してユーザに出力される。この出力ユニット6は、例えば、ディスプレイスクリーンおよび/またはラウドスピーカを含み得る。
【0082】
位置決定手段8によって決定された現在の車両の位置、および交通メッセージ受信器9において受信された交通情報は、プロセッサ2に提供される。このプロセッサ2は、以下で図5〜図8を参照してより完全に記載されるように、格納ユニット3に格納された評価関数のデータ5を利用することによって、位置決定手段8および/または交通メッセージ受信器9によって提供される情報に基づいて、新しいルート検索を開始する。同様に、クロックユニット10は、プロセッサ2に現在時刻を提供し、このプロセッサ2は、例えば動的なルーティングにおいては、交通状況の変化に起因する道路セグメントおよび/または道路セグメントの頂点に関連するコストの時間変化を考慮することによって、現在時刻に基づいてルート検索が実行されるグラフに対するコストモデルを調整し得る。
【0083】
図2および図3を参照し、一実施形態にしたがう、道路網上のルートを決定するための方法が記載される。この方法は、ナビゲーションシステム1の格納ユニット3に接続されたプロセッサ2によって実行され得る。
【0084】
図2Aおよび図2Bは、例示的な道路網20を示しており、これを参照して、ルートを決定するための方法が説明される。道路網は、図2においては箱(box)として示されている複数の道路セグメントの頂点21〜33を含んでおり(この例においては、13個が示されている)、複数の道路セグメント41〜56(この例においては、16個が示されている)によって、相互接続されている。道路セグメント41〜56は、図2の道路ネットワーク20を表現するグラフのエッジを形成している。
【0085】
図3は、実施形態にしたがう、ルートを決定するための方法70の流れ図である。この方法にしたがい、道路網20上のルート検索が、2つのステップまたは段階で実行される。すなわち、第1のステップまたは段階においては、道路網20に基づいて、道路網20の複数の頂点21〜33に対して、評価関数の値が決定される。第2のステップまたは段階においては、出発点(図2においては21として示されている)から目的地(図2においては22として示されている)までのルートを検索するために、評価関数の値が利用される。
【0086】
対応して、方法70では、71において、少なくとも所望の目的地を示すユーザ入力が受信される。72においては、道路網を表現する第1のグラフに基づいて、複数の頂点に対し、評価関数の値が決定される。72において決定された頂点に対する評価関数の値は、頂点から目的地までのルートに関連するコストに関する下限を提供する。73においては、72において決定された評価関数の値に基づいて、目的地までのルートに対する検索が実行される。本明細書においては、72における評価関数の値の決定に関連して用いられているように、用語「第1のグラフに基づいて(based on the first graph)」は、第1のグラフの個々の頂点の幾何学的配置に基づくだけではなく、グラフのエッジによる第1のグラフの少なくとも2つの頂点の相対的な配置および/または相互接続にも基づく動作を意味する。
【0087】
以下でより詳細に説明されるように、評価関数の値を決定するために72において利用される第1のグラフは、第2のグラフと同じまたは異なるものであり得、この第2のグラフに対して、第2のステップのルート検索が73において実行される。1つの例示的な実施形態においては、72において利用される第1のグラフと73において利用される第2のグラフとの両方は、ルート検索が実行される道路網を表現しており、第1のグラフおよび第2のグラフのエッジは、道路セグメントに対応する。すなわち、図2の例示的な道路網20に対して、道路セグメント41〜56は、第1のグラフと第2のグラフとの両方のエッジに対応し得、道路セグメントの頂点21〜33は、第1のグラフと第2のグラフとの両方の頂点に対応し得る。
【0088】
方法70の多くの改変が、実施され得ることが理解されるべきである。例えば、73におけるルート検索および72における評価関数の値の決定は、例えば、図5〜図8を参照して以下でより詳細に説明されるように、様々なコストモデルに基づき得る。73におけるルート検索はまた、例えば、図9および図10を参照して以下でより詳細に説明されるように、72において決定されなかった評価関数の値にも基づき得る。72において評価関数の値を決定するために利用される第1のグラフ、および73においてルート検索が実行される第2のグラフは、図11および図12を参照して以下でより詳細に記載されるように、異なり得る。また、ルートを決定するための方法は、図13および図14を参照して以下でより詳細に説明されるように、3つ以上の異なる段階またはステップ(例えば、3つの段階)を含み得る。
【0089】
図2および図3を参照して、方法70の1つの実装が、図2の道路網20に関連して記載される。例示的な目的のみのために、72における評価関数の値の決定のためのコストモデルと73におけるルート検索のためのコストモデルとは同じものであるということ、72における評価関数の決定と73におけるルート検索との両方は同じグラフ上で(すなわち、道路セグメント41〜55がグラフのエッジに対応する主グラフ(primary graph)上で)実行されるということが、仮定される。
【0090】
評価関数の値を決定するために、目的地22から出発して出発点21に向けて延長するルート検索が実行される。一実施形態において、目的地22から出発するルート検索は、Dijkstraアルゴリズムを用いて実行される。別の実施形態において、目的地22から出発して出発点21に向けて導かれるルート検索は、A*−アルゴリズムを利用して実行される。後者の場合、図2Aにおいて破線34および37によって概略的に示されているように、任意の適切な評価関数(例えば、直線距離ベースの評価関数)が利用され得る。
【0091】
第1の段階において、目的地22から出発するルート検索が実行されるが、道路網41〜55または頂点21〜33を通過すると加算されるコストは、出発点21から目的地22に向けた移動に関連するコストである。例えば、道路セグメント55が頂点33から頂点22までの移動のみが可能な一方通行の道路である場合でさえも(この場合、頂点22から頂点33に向けた道路セグメント55の移動のためのコストは無限である)、頂点33から頂点22までの道路セグメント55の移動を反映する少ない方のコストのみが、目的地22から出発する検索において考慮される。言い換えると、評価関数の値を決定するときには、検索方向のみが逆転され、その一方でルートは、出発点21から目的地22までの移動に課される交通規則を遵守しながら見つけられ、このようにして、目的地22までの有効なルートを表現する。
【0092】
目的地22から出発するルート検索は、このルート検索がDijlstraアルゴリズム、A*−アルゴリズム、または別の適切なアルゴリズムのどれを用いて実行されるかに関わらず、道路網20の頂点を含む検索ツリーをもたらし、これらの頂点の各々に対し、コストは、それぞれの頂点から目的地22までの移動と関連付けられる。目的地22から出発する検索は、出発点21に到達したときに終了するが、その他の実施形態においては、この検索はまた、さらに継続され得る。単なる例示として、検索は、例えば、コストが所定の閾値に到達するまで、またはアルゴリズムにおけるエッジの延長ステップのステップ数が所与の閾値に到達するまで、継続され得る。別の実施形態において、目的地22から出発する検索は、出発点21に到達する前であっても、終了され得る。目的地22から出発するルート検索においては、終了の基準に依存して、道路網20の全ての頂点21〜33が、探索されなければならないわけではないことに留意されたい。対応して、それぞれの頂点から目的地22までの移動に関連するコストは、道路ネットワーク20の頂点21〜33のサブセットに対してのみ決定され得る。図2の例示的な道路網20において、目的地22から出発するルート検索は、図2における黒い四角(full squre)によって概略的に示されているように、頂点33、32、28、27、24、23、21、および25をそれぞれ訪問する。これらの頂点のうちの任意の頂点vに対し、目的地22から出発するルート検索は、第1のステップにおいて利用されるコストモデルに基づいて、頂点vから目的地までのルートに対する正確なコストcosts(v,d)を提供する。これらのコストは、その後73で、出発点21から目的地22までのルート検索において用いられる。
【0093】
図2Bを参照して、73におけるルート検索が、より詳細に説明される。図2Bは、道路網20の概略的表現60であり、ここでは、出発点21および目的地22を結ぶ最適なルート61が示されている。例示的な道路網において、最適なルート61は、道路セグメント41、45、46、52、54、および55、ならびに頂点23、24、28、32、および33をそれぞれ通過する。出発点21から目的地22までのルート検索は、評価関数を利用して、A*−アルゴリズムまたは別の検索アルゴリズムを用いて実行され、ここでは、頂点vへと進む検索ツリーの次の「枝(branch)」は、
【0094】
【化1】
が最小になるように選択され、ここで、
【0095】
【化2】
は、出発点sから頂点vまでのルートに沿って生じるコストを表現しており、
【0096】
【化3】
は、頂点vに対する評価関数の値であり、これは、頂点vから目的地dまでのコストの下限を表現している。72での目的地から出発する検索においてcosts(v,d)が決定された任意の頂点に対し、評価関数の値は、costs(v,d)に等しく設定され得、すなわち、
【0097】
【化4】
である。しかしながら、図9および図10を参照して以下でより詳細に記載されるように、72におけるルート検索において訪問されていない任意の頂点に対しては、必要に応じて、式(3)を満たす別の適切な評価関数の値が用いられ得る。
【0098】
72におけるルート検索に対するコストモデルと73におけるルート検索に対するコストモデルとが同じであると仮定すると、道路網20に基づいて決定された評価関数の値h(v)は、目的地までの残りの経路に対する正確なコストを表現し、ひいては、最も優れた可能な評価関数の値を表現することに留意されたい。したがって、第2のステップ73において実行されるA*−アルゴリズムが、第1のステップ72において見つけられた評価関数の値h(v)=costs(v,d)を利用するとき、検索ツリーは、単一の枝へと崩壊し、この枝は、最適なルート61に沿って(すなわち、出発点21から、頂点23、24、28、32、および33を介して)直接的に目的地22に進む。出発点21から目的地22までの検索ツリーは、例えば図2Bに示されているように、単一の枝のみしか含んでいないので、ステップ73における図3の方法70にしたがう、72において決定された評価関数の値に基づくルート検索は、少ない計算リソース、特に、直線距離ベースの評価関数の値だけを用いるA*−アルゴリズムと比較して、短い計算時間を必要とし得る。
【0099】
方法70の効果は、図4において概略的に示されており、図4は、それぞれ、本発明の実施形態にしたがうルート検索の間に探索される地図の一部分(図4A、図4B)、および従来のルート検索の間に探索される地図の一部分(図4C)を描いている。図4は、道路セグメント(図示されず)を含む地図部分80を示している。出発点81から目的地82までのルートの検索が実行されることが仮定される。図4Aに示されているように、方法70にしたがって、ステップ72において、地図80の領域83は、この領域83の内部に配置された頂点に対する評価関数の値を決定するために、目的地82から出発して出発点81に向けて延長するように検索される。図4Bに示されているように、ステップ73において実行される出発点81から目的地82までの次のルート検索においては、地図80の遥かに小さな領域84のみが、検索される必要がある。なぜならば、ステップ72において既に確立された良い評価関数の値が、ステップ73において利用されるからである。
【0100】
対照的に、従来のA*−アルゴリズムが実行され、出発点81から出発して検索ツリーを延長することによって、出発点81から目的地82までのルートを決定するときには、領域84と比べて通常大きい領域85(図4Cにおいて概略的に示されている)が、検索される必要がある。
【0101】
評価関数の値が第1のステップ72におけるグラフに基づいて決定されるときでさえも、第2のステップ73において探索される検索ツリーは、図2Bの説明例に示されているように、必ずしも常に単一の検索ツリーの枝に崩壊するとは限らない。例えば、図5〜図10を参照して以下でより完全に説明されるように、第2のステップ73において利用されるコストモデルが、例えば回避オプション、交通情報、動的なルーティング等が理由で、第1のステップ72において逆の検索に用いられるコストモデルとは異なる場合、ステップ72において決定されたコストcosts(v,d)(以下では、これらのコストが第1のステップにおいて用いられる第1のコストモデルに基づいて決定されたことを反映するように、costs1(v,d)によって示される)は、一般的には、第2のステップにおいて用いられる新しい第2のコストモデルに基づいて決定される頂点vから目的地dまでのルートの最小のコストとは、同じものではない。以下では、第2のコストモデルに対応する後者のコストは、costs2(v,d)によって示される。次に説明されるように、第1および第2のコストモデルが異なる場合でさえも、第1のステップにおいて決定された評価関数の値は、有利にも、第2のステップにおける評価関数として利用され得る。
【0102】
図5は、別の実施形態にしたがう、ルートを決定するための方法90の流れ図である。この方法は、例えば、ナビゲーションシステム1のプロセッサ2によって実行され得る。方法90では、91において、所望の目的地を指定するユーザ入力が受信される。92においては、複数の頂点に対する評価関数の値が、第1のグラフに基づいて、かつ第1のコストモデルを利用することにより、決定される。92における評価関数の値の決定は、図3を参照して上述された方法のうちの任意の方法で実施され得る。特に、複数の頂点に対する評価関数の値は、目的地から出発して出発点に向けて延長する第1のグラフ上でルート検索を実行することによって、決定され得る。複数の頂点のうちの頂点vに対し、92において決定される評価関数の値は、第1のコストモデルにしたがって、頂点vから目的地dまでのルートに関連するコストであるcosts1(v,d)に等しく設定される。ステップ93においては、92において決定された評価関数の値costs1(v,d)が、その後の使用のためにさらなる格納ユニットに格納される。図1に示されている例示的な実施形態1において、評価関数の値はまた、データ5として格納ユニット3に格納される(すなわち、グラフデータを格納する格納ユニットおよび評価関数の値を格納するさらなる格納ユニットは、一体的に形成される)。しかしながら、評価関数の値が格納されるさらなる格納ユニットは、グラフデータ4を格納する格納ユニット3とは異なることもあり得る。例えば、さらなる格納ユニットは、評価関数の値がその後の使用のために格納されるワーキングメモリ(例えば、RAM)であり得る。
【0103】
94においては、第2のグラフ上で、出発点から目的地までのルートの検索が実行される。図3の方法におけるステップ73と同様に、94におけるルート検索は、A*−アルゴリズムまたは評価関数を利用する別のアルゴリズムを用いて、実行される。しかしながら、ステップ94において利用される第2のコストモデルは、必ずしも第1のコストモデルと同じであるとは限らない。図5の実施形態においては、第1のコストモデルは、この第1のコストモデルが、ステップ94におけるルート検索に利用される第2のコストモデルに関する下限を表現するように、選択されることが仮定され得る。すなわち、第1のグラフの任意の頂点またはエッジに対し、第1のコストモデルにしたがうこの頂点またはエッジに関連するコストは、第2のコストモデルにしたがう第2のグラフの頂点またはエッジに関連するコスト未満であるか、それと等しい。92において決定された評価関数の値は、94におけるルート検索における評価関数の値としての役割を担う。すなわち、検索ツリーの次の枝は、
【0104】
【化5】
が最小になるように選択され、ここで、
【0105】
【化6】
は、出発点sから頂点vまでのルートに沿って生じる第2のコストモデルにしたがうコストを表現しており、頂点vにおける評価関数の値は、
【0106】
【化7】
であり、すなわち、この値は、costs1(v,d)が既に決定されているときには、第1のコストモデルにしたがう、92において決定されたコストである。94において決定されたルートは、例えば、ユーザに出力される。
【0107】
出発点から目的地までのルートを決定した後、95において、第2のグラフの頂点またはエッジのコストの変化をもたらすイベントが発生したかどうかがモニタリングされる。コストの変化をもたらすイベントが95において検出されなかった場合、95におけるモニタリングは、待機状態96の後に繰り返される。95において、第2のコストモデルにしたがう頂点またはエッジのコストが変化したことが決定された場合、97において、コストの変化に適応するために、第2のコストモデルが更新される。上述のように、ステップ92において用いられる第1のコストモデルは、第2のコストモデルが97において更新されるときでさえも、第1のコストモデルが第2のコストモデルにしたがうコストに関する下限を提供するように、選択される。言い換えると、第1のコストモデルは、第1のステップの結果が用いられることが予想される任意の第2のコストモデルに関する下限を表現するように、選択される。98において、格納された評価関数の値が抽出される。方法は次に94に戻り、ここでもまた、更新された第2のコストモデルおよび格納された評価関数の値に基づいて、ルートが決定される。
【0108】
図5の実施形態の方法90にしたがうと、92において決定された評価関数の値が、第2のコストモデルにしたがって決定される頂点vから目的地dまでのルートに関連する実際のコストを低く評価している場合には、92において第1のコストモデルに基づいて決定された評価関数の値は、第2のコストモデルにおけるコストが変化するときでさえも、評価関数の再計算を要求することなしに、94における以後のルート決定のために何回か用いられ得るということに、留意されたい。これは、第1のコストモデルを適切に選択することによって達成される。一実施形態において、第1のコストモデルは、任意の予想される第2のコストモデルに対して選択され得、第1のコストモデルにしたがう頂点またはエッジの通過に関連するコストは、予想される第2のコストモデルにしたがう対応する頂点またはエッジの通過に関連するコスト未満であるか、またはそれと等しい。
【0109】
コストにおける変化は、様々な機構によってもたらされ得、95におけるコストの変化をもたらすイベントのモニタリングおよび第1のコストモデルの適切な選択は、特定の機構に基づいて実施され得る。次に説明されるように、コストの変化に対する可能性のある原因は、回避オプションなどのユーザの選好度、動的なルーティングにおける時刻および/または日付の関数としてのコストにおける変化、出発点から目的地までの代替ルートの計算、または交通情報信号を含む。
【0110】
一実施形態において、95においてモニタリングされるコストの変化は、ユーザの選好度における変化によって、例えば、ユーザによって選択される回避オプションによって、もたらされ得る。そのような回避オプションは、コストペナルティを課す(すなわち、特定の基準を満たす回避されるべき道路セグメントに関連するコストを増加させる)ことによって、ルート決定において考慮され得る。例えば、トンネルまたはフェリー接続が回避されるべき場合には、トンネルまたはフェリー接続を表現するグラフのエッジの全てのコストが増加され得る。そして、評価関数の値を決定するために92において第1のグラフ上のルート検索に利用される第1のコストモデルが、任意のコストの増加または回避オプションによって課されるペナルティを考慮しないコストモデルとして選択され得、例えば、このコストモデルは、最速ルートまたは最短ルートのコストモデルを表現し得る。94におけるルート検索に利用される第2のコストモデルは、基本的に、ユーザによって回避オプションが選択されていない場合には、第1のコストモデルと同じである。95におけるコストの変化をもたらすイベントのモニタリングは、入力ユニット6におけるユーザの選好度を示すユーザ入力をモニタリングすることによって、実施され得る。そして、97において、第2のコストモデルが、選択された回避オプションにしたがってコストを増加させることによって、更新される。上述のように選択された第1のコストモデルにしたがう任意の頂点またはエッジのコストは、第2のコストモデルにしたがう対応する頂点またはエッジのコストに関する下限を表現しているので、92において決定された評価関数の値は、なおも頂点から目的地までのルートに関連するコストを低く評価している。それ故、この評価関数の値は、94においてA*−アルゴリズムが再び実行される場合に、なおも利用される。ここで、
【0111】
【化8】
の値は、ユーザの選好度が理由で変化し得る更新された第2のコストモデルに基づいて決定される。
【0112】
一実施形態においては、代替ルートを決定するために、コストの変化は、プロセッサ2によって内的にもたらされ得る。評価関数の値は、92において、第1のコストモデル(ユーザの回避オプションを考慮するものであったり、または考慮しないものであったりし得る)に基づいて、第1のグラフ上でルート検索を実行することによって決定される。出発点から目的地までの第1のルートは、94において、第2のコストモデル(最初は第1のコストモデルに等しく設定されている)に基づいて決定される。第1のルートが見つけられた後、第1のルートによって通過されるエッジおよび/または頂点に対するコストは、97において増加される。そして、94におけるルート検索が、更新された第2のコストモデル(第1のルートは、好ましくないものとされる)に基づいて、かつ92において第1のコストモデルに基づいて決定された評価関数の値を利用することによって、繰り返される。このようにして、第1のルートの代わりに、出発点から目的地までの第2のルートが見つけられ得る。続いて、ステップ97、98、および94が、繰り返され得る。例えば、第2のルートに沿ったコストもまた増加され得、第1のルートおよび第2のルート等に対する別の代替物である第3のルートが決定され得る。プロセッサ2が、外部のトリガイベントを要求することなしに第2のコストモデルを自動的に更新する場合、モニタリングステップ95および待機ステップ96もまた省略され得、ステップ97、98、および94が、第2のコストモデルが更新されるときはいつでも、自動的に繰り返され得る。
【0113】
一実施形態において、コストの変化は、交通情報信号(例えば、交通渋滞またはその他の悪い交通状況を示す)によって引き起こされ得る。評価関数の値は、92において、第1のコストモデル(これは、ユーザの回避オプションを考慮するものであったり、または考慮しないものであったりし得るが、悪い交通状況によってもたらされるコストの増加を考慮しない)に基づいて、第1のグラフ上でルート検索を実行することによって決定される。このようにして決定された評価関数の値は、93において、格納される。悪い交通状況に関する情報が最初に利用可能でない場合、94におけるルート検索は、第2のコストモデル(最初は第1のコストモデルに等しく設定されている)に基づいて決定され得る。95におけるコストの変化をもたらすイベントのモニタリングは、ナビゲーションシステム1のプロセッサ2が、交通メッセージ受信器9(例えば、TMC受信器として構成され得る)によって受信された交通情報信号を評価することによって、もたらされ得る。プロセッサ2が、受信した交通情報信号が94において既に決定されたルートによって通過される頂点またはエッジのコストに影響を与え得るということを決定すると、このプロセッサ2は、97において、受信した交通情報信号に基づいて、それぞれの頂点またはエッジのコストを増加させることによって、第2のコストモデルを更新する。別の実施形態において、第2のコストモデルの更新は、グラフの任意の頂点またはエッジに関連する交通状況信号が受信されたときに、実行され得る。そしてルートは、g(v)を決定するための更新された第2のコストモデルに基づいて、かつ92において決定された評価関数h(v)に基づいて、再び決定される。第1のコストモデルのコストは、第2のコストモデルのコストの下限を表現しているので、第2のコストモデルのコストはなおも、有効な評価関数を提供する。ステップ97、98、および94は、さらなる交通情報信号が受信されるときはいつでも、繰り返され得る。
【0114】
一実施形態において、コストの変化は、時刻または日付の関数としての、コストの所定の時間変化によってもたらされ得る。そのような時間変化するコストは、例えば、時刻および/または日付の関数として交通状況の変化が考慮される動的なルート検索において利用される。そして、92において、評価関数の値を決定する際に利用される第1のコストモデルは、任意の頂点またはエッジに対し、第1のコストモデルが、任意の時刻および/または日付において、この頂点またはエッジに関連する最小のコストに対応するように、選択される。そして、94におけるルート決定において、第2のコストモデルが、クロックユニット10によって時間変化するコストを反映するように決定された時刻および/または日付に応じて、選択され得る。言い換えると、頂点またはエッジのコストに対する時間変化する寄与は、94におけるルート決定においてのみ考慮され、92における評価関数の値の決定に対しては考慮されない。第1のコストモデルのコストは、第2のコストモデルのコストに関する下限を表現しているので、第2のコストモデルはなおも、有効な評価関数を提供し、94におけるルート検索に利用され得る。コストに対する時間変化する寄与が(例えば、ルートの通過の間になされる一時停止が原因で)変化する場合、97において、時間変化するコストを考慮する第2のコストモデルが更新され得、94において、ルートが再び決定され得る。
【0115】
ユーザの選好度、代替ルートの決定、交通情報信号、および動的なルート決定は、コストモデルが変化し得る例示的なシナリオを表現し得るが、図5の実施形態はこれらのシナリオに限定されないということに、留意されたい。
【0116】
図7を参照すると、この図は、図2の例示的な道路網20を示しており、図5の実施形態にしたがう方法90が説明される。上述で図2を参照して説明されたように、第1および第2のグラフは、同じものであって、グラフのエッジが道路網20の道路セグメントを表現している主グラフを表現していることが仮定されている。92において、評価関数の値が、図7における黒い四角によって示されている頂点21、23、25、24、27、28、32、および33に対して決定されることが仮定される。最初に、出発点21から目的地22までの最適なルート61が、道路セグメント41、45、46、52、54、および55を通過することが決定される。例えばユーザの選好度、代替ルートの決定、交通情報信号、および動的なルート決定が理由で、道路セグメント45に対するコストが増加すると、94におけるルート検索はなおも、頂点21、23、25、24、27、28、32、および33に対して最初に決定された評価関数の値h(v)=costs1(v,d)を用いて実行され得るが、道路セグメント45に対して増加されたコストを有する更新された第2のコストモデルを利用することによって、g(v)=costs2(s,d)を決定する。図7において概略的に示されているように、道路セグメント45に対して増加されたコストが理由で、新しい最適なルート121は、道路セグメント41、44、51、54、および55を通過する。第1のステップにおいて、グラフ20に基づいて評価関数の値h(v)=costs1(v,d)が決定されるので、これらの評価関数の値は、頂点vから目的地dまでのコストの下からの評価(第2のコストモデルにしたがう実際のコストに近いものであり得る)を提供し、これによって、ルートを見つけるために検索されなければならないグラフ20の部分のサイズを減らす。第1および第2のコストモデルが異なるとき、94におけるルート検索はまた、92において評価関数の値が決定されていないさらなる頂点に対して(例えば、図7における頂点26に対して)評価関数の値が決定されることを要求し得るが、要求される追加的な評価関数の値は、図9および図10を参照して以下でより詳細に説明されるように、容易に確立され得る。
【0117】
次に、図6を参照して、本発明の別の例示的な実施形態にしたがう方法100が記載される。方法100にしたがい、第1のグラフに基づいて決定された評価関数の値が、出発点から目的地までのルートを決定するために、また、ルートの逸脱(deviation)が検出されたときには、別の出発点から(例えば、現在の車両の位置から)目的地までのルートを決定するために利用される。
【0118】
方法100では、101において、所望の目的地を指定するユーザ入力が受信される。102においては、複数の頂点に対する評価関数の値が、第1のグラフに基づいて、かつ第1のコストモデルを利用することにより、決定される。102における評価関数の値の決定は、図2および図3を参照して上述された方法のうちの任意の方法でもたらされ得る。特に、複数の頂点に対する評価関数の値は、目的地から出発して出発点に向けて延長する第1のグラフ上でのルート検索を実行することによって、決定され得る。複数の頂点のうちの頂点vに対し、102において決定される評価関数の値は、第1のコストモデルにおける頂点vから目的地dまでのルートに関連するコストであるcosts1(v,d)に等しく設定される。ステップ103においては、102において決定された評価関数の値costs1(v,d)は、その後の使用のためにさらなる格納ユニットに格納される。104においては、第2のグラフ上で、かつ第2のコストモデルに基づいて、出発点から目的地までのルートの検索が実行される。第2のコストモデルは、第1のコストモデルと同じものであったり、または異なるものであったりし得る。しかしながら、一実施形態においては、102において利用される第1のコストモデルは、第1のグラフの任意の頂点またはエッジに対し、第1のコストモデルにしたがうコストが、第2のコストモデルにしたがう第2のグラフの対応する頂点またはエッジに関する下限を表現するように、選択される。図3の方法におけるステップ73と同様に、104におけるルート検索は、A*−アルゴリズムまたは別のアルゴリズム(評価関数として、102において決定された評価関数の値を利用する)を用いて実行される。
【0119】
105において、現在の車両の位置が決定される。現在の車両の位置は、ナビゲーションシステム1において、GPS受信器8によって出力された信号に基づいて決定され得る。100において、車両がルートを逸れたかどうかを決定するために、現在の車両の位置が、ルートに沿った位置と比較される。106において、最初のルートからの逸脱が決定されなかった場合には、105における現在の位置の決定が、107における所定の待機期間の後に繰り返される。
【0120】
しかしながら、106において最初のルートからの逸脱が検出された場合には、108において、現在の車両の位置または現在の車両の位置に近い別の位置が、新しい出発点として選択される。109において、格納された評価関数の値が抽出される。110において、新しい出発点から目的地までのルートの検索が、第2のグラフ上で、かつ第2のコストモデルに基づいて、実行される。ルート検索110において、102において決定された評価関数の値は、ここでもまた、(例えば、A*−アルゴリズムにおいて)評価関数として利用される。そして方法は、105におけるアクティブなルートに対する現在の車両の位置のモニタリングに戻る。102において第1のコストモデルを適切に選択することによって、第1および第2のコストモデルが異なる場合でさえも、102において決定された評価関数の値はなおも、110におけるルート検索に有効な評価関数を表現するということに留意されたい。さらに、以下でより詳細に記載されるように、102において評価関数の値が決定される第1のグラフ、および104および110においてルート検索が実行される第2のグラフは、同じものであったり、または異なるものであったりし得るということに留意されたい。
【0121】
図5および図6の方法は、組み合わされ得るということに留意されたい。例えば、一実施形態において、第1のグラフに基づいて評価関数の値が決定される第1のステップの結果は、例えば代替ルートの検索において、1つの出発点から目的地までのいくつかの異なるルートを決定するためと、例えば最初のルートからの逸脱が検出されたときに、異なる出発点から目的地までの異なるルートを決定するためとの両方に、利用され得る。
【0122】
図7を参照して、図6の実施形態の方法100が、道路網20に関連して例示的に説明される。ルート61の道路セグメント41を通過した後、ユーザは頂点23において道路セグメント45ではなく道路セグメント44に曲がると仮定し、最初のルート61からの逸脱が検出されると仮定する。これに応答して、第1のステップにおいて既に決定された評価関数の値を利用することにより、道路セグメント44上の現在の車両の位置または到達されるべき次の頂点27から目的地22までの新しいルートが決定される。
【0123】
図6の方法100をさらに説明するために、図8に対する参照がなされる。この図は、道路網(図示されず)を含む地図130を示しており、図6の方法100の様々なステップにおいて訪問される地図130の一部分を概略的に表現している。例示を目的として、102において評価関数の値を決定する際に利用されるコストモデル、ならびに104および110においてルート検索の際に利用されるコストモデルは、同じものであったり、または僅かに異なるものであったりし得るということに留意されたい。ルート検索の出発点は131に示されており、目的地は132に示されている。図8Aは、目的地132から出発して出発点131に向かって延長するルート検索を実行することによって評価関数の値が決定されるときに、ステップ102において訪問される領域133を概略的に示している。102におけるルート検索において、評価関数の値は、領域133に配置される頂点に対して決定される。図8Bにおいて、領域134は、104において出発点131から目的地132までのルート検索において探索される地図130の一部分を概略的に示している。図4Bを参照して上述されたように、グラフに基づいて決定される評価関数の値は、正確な最小のコストに対する良い近似を表現し得るので、領域134は小さな領域であり得る。車両が最初に決定されたルートを逸脱し、例えば位置135に位置するときには、位置135から目的地132までのさらなるルート検索がトリガされる。領域136は、このさらなるルート検索において探索される地図130の一部分を概略的に示している。さらなるルート検索もまた、グラフに基づいて決定された評価関数の値を利用するので、探索されなければならない領域136もまた、小さな領域であり得る。単に例示を目的として、102において評価関数の値を決定する際に利用されるコストモデル、および104および110におけるルート検索に利用されるコストモデルは、同じものであると仮定すると、102および104における検索での検索ツリーは、1つの枝に崩壊し得る。
【0124】
図1〜図8を参照して上述されたように、2つのステップまたは段階においてルート検索が実行されるとき、第2のステップまたは段階において実行される出発点から目的地までのルート検索は、第1のステップまたは段階において評価関数の値が決定されなかった頂点に対する評価関数の値を必要とし得る。この状況は例えば、第1のステップおよび第2のステップにおいて利用される第1のコストモデルおよび第2のコストモデルのそれぞれが異なるとき、または車両が最初のルートから逸脱しているときに、第1のステップ利用される終了の基準が理由で、第1のステップにおいて、全ての頂点のうちの僅かな部分に対してのみ、評価関数の値が決定されたときに生じ得る。次に説明されるように、追加的な頂点に対する評価関数の値は、必要に応じて、ルート決定の第2のステップの間に容易に決定され得る。
【0125】
図9は、第2のステップ(図3の方法70における73、図5の方法90における94、図6の方法100における104および110)における出発点から目的地までのルート検索に利用され得る方法140の流れ図である。限定ではなく例示のために、出発点から目的地までのルート検索は、A*−アルゴリズムを用いて実行される。
【0126】
141において、延長ステップは、検索ツリーの「逸脱(leave)」から(すなわち、出発点から延びる検索ツリーにおける最後の頂点のうちの1つから)実行される。142において、延長ステップが実行される新しい頂点に対して、評価関数の値が既にルート検索の第1のステップにおいて決定されているかどうかが、決定される。評価関数の値が既に決定されている場合、143において、第1のステップにおいて決定された新しい頂点に対する格納された評価関数の値costs1(v,d)が、新しい頂点に対する評価関数h(v)として用いられる。評価関数の値が決定されていない場合には、144において決定される。
【0127】
144における新しい頂点に対する評価関数の値の決定は、様々な方法で実行される。一実施形態において、新しい頂点に対する評価関数の値は、第1のステップ(すなわち、図3における72)に戻り、かつ新しい頂点に対しても評価関数の値が求まるまで第1のステップを継続することによって、決定される。例えば、第1のステップが目的地から出発して出発点まで延長するルート検索を含む場合、このルート検索は、新しい頂点に到達されるまで継続され得る。
【0128】
図10を参照すると、この図は、図2の道路網20を示しており、新しい頂点に対して評価関数を決定するための方法が例示的に説明される。道路セグメント41のコストは、(例えば、回避オプションが理由で)増加されており、出発点21から目的地22までの最適なルートはもはや、道路セグメント41を通過しないことが仮定される。出発点21から頂点25までの第1の延長ステップの後、それ続いて、白い四角(open squre)によって示されている頂点29(この頂点に対しては、第1のステップにおいて、評価関数の値が決定されていない)まで延長する。しかしながら、頂点28から目的地22までのルートに対するcosts1(頂点28,d)、頂点25から目的地22までのルートに対するcosts1(頂点25,d)の両方が、第1のステップにおいて決定されているので、頂点29に対する評価関数の値は、頂点25および28から頂点29までの検索を延長し、かつcosts1(頂点28,d)と頂点29から頂点28までのルートに関連するコストとの和、そしてcosts1(頂点25,d)と頂点29から頂点25までのルートに関連するコストとの和のうちの小さいほうを決定することによって、決定され得る。
【0129】
別の実施形態において、144における新しい頂点に対する評価関数の値は、第1のステップのルート検索を継続することを要求することなしに、第1のステップにおいて決定された情報に基づいて、決定され得る。限定ではなく例示のために、新しい頂点に対する評価関数の値は、第1のステップにおいて決定された評価関数の最大値、および第1のステップにおける、目的地から出発して出発点まで延長するルート検索において利用される評価関数に基づいて決定され得る。すなわち、
【0130】
【化9】
が第1のステップにおいて決定された任意の頂点vに対する最大のコストを示し、かつh1(v)(出発点sから頂点vまでのルートに関連するコストに関する下限を表現する)がルート検索の第1のステップにおいて利用される評価関数を示す場合、ルート検索の第2のステップにおいて利用される任意の頂点vに対する評価関数の値h(v)は、
【0131】
【化10】
に等しく設定され得る。図2Aを参照して上述されたように、第1のステップにおいて利用される評価関数h1(v)は、直線距離ベース(例えば、最短ルートのコストモデルに対する直線距離、または直線距離を最速ルートのコストモデルにおける固有の移動速度で割ったもの)であり得る。
【0132】
新しい頂点に対する評価関数を決定するための本方法をさらに説明するために、再び図10を参照すると、ここでもまた、出発点21から目的地22までの検索は、第1のステップにおいて評価関数の値が決定されていない頂点29まで延長することが仮定される。しかしながら、max1=costs(頂点25,d)が、第1のステップにおいて決定されている。さらに、第1のステップにおいて、直線(air−line)ベースの評価関数h1が利用されると仮定すると、153に概略的に示されているように、h1(頂点29)は、頂点29と出発点21との間の直線距離から容易に決定され得る。max1およびh1(頂点29)から、h(頂点29)が式(9b)にしたがって決定され得る。
【0133】
別の実施形態において、新しい頂点に対する評価関数の値は、新しい頂点から目的地までの直線距離に基づいて決定され得る。
【0134】
新しい頂点に対する評価関数を決定するための本方法をさらに説明するために、再び図10を参照すると、頂点29に対する評価関数の値は、152に概略的に示されている頂点29と目的地22との間の直線距離に基づいて決定され得る。
【0135】
図1〜図10を参照して上述された例示的な実施形態において、評価関数の値が決定される第1のグラフ、および出発点から目的地までのルート検索が実行される第2のグラフは同じであると仮定されているが、次に説明されるように、第1および第2のグラフはまた、その他の実施形態においては異なるものであり得る。
【0136】
図11は、本発明の一実施形態にしたがう、方法160の流れ図である。方法160では、161において、所望の目的地を指定するユーザ入力が受信される。162において、第1のグラフの複数の頂点および/またはエッジに対する評価関数の値が、第1のグラフに基づいて決定される。162における評価関数の値の決定は、図2および図3を参照して上述された方法のうちの任意の方法でもたらされ得る。特に、評価関数の値は、目的地から出発して出発点に向けて延長する第1のグラフ上でルート検索を実行することによって決定され得る。第1のグラフの頂点に対し、162において決定される評価関数の値は、第1のグラフ上の評価関数の頂点から目的地までのルートに関連するコストに等しく設定され得る。加えてまたはあるいは、評価関数の値はまた、第1のグラフのエッジ上の特徴点に対して決定され得る。163においては、第1のグラフの要素(すなわち、頂点またはエッジ)に対して決定される評価関数の値が、第2のグラフの対応する要素に対する評価関数の値にマッピングされる。164においては、162において確立された評価関数の値を利用することにより、ルート検索が第2のグラフ上で実行され、163における第2のグラフにマッピングされる。
【0137】
例えば、図11の方法160は、図12に関連してさらに示される。図12は、第1のグラフを表現している図2の道路網20を示しており、これに基づいて、評価関数の値が決定される。すなわち、第1のグラフのエッジは、道路セグメントを表現しており、第1のグラフの頂点は、道路セグメントの端点を表現している。図12においては、第1のグラフの頂点は、中実の四角(solid squre)で示されており、第1のグラフのエッジは、実線で示されている。第2のグラフ20’は、道路網の双対グラフである。すなわち、第2のグラフ20’の頂点171〜178は、道路網の道路セグメントを表現している。例えば、頂点171は道路セグメント41を表現しており、頂点172は道路セグメント42を表現している、等。第2のグラフ20’のエッジ181〜185は、道路セグメントの端点を表現しており、これらは、1つの道路セグメントから別の道路セグメントへの移行を可能にしている。たとえば、頂点171および172を結ぶエッジ181は、出発点21において、道路セグメント41と道路セグメント42との間の移行が可能であることを示している。同様に、頂点174および175を結ぶエッジが存在しないという事実は、接合部23における道路セグメント45と道路セグメント44との間の移行が可能ではないということを示している。したがって、双対グラフにおいて、ターン制限は容易に考慮され得る。なぜならば、ターン制限は、双対グラフのエッジによる双対グラフの頂点の相互接続によって反映されるからである。図12においては、第2のグラフの頂点は、空白の四角(open squre)によって示されており、第2のグラフのエッジは、破線によって示されている。
【0138】
図12に見られるように、第1のグラフ20および第2のグラフ20’は、互いに異なるものであり得る(すなわち、一方は他方の双対グラフであり得る)。そして、評価関数の値が決定されるルート検索の第1のステップは、(例えば、目的地22から出発して出発点21に向けて延長する第1のグラフ20上でルート検索を実行することによって)第1のグラフ20上で実行され得る。これによって、結果として得られる検索ツリーの任意の枝における第1のグラフ20の任意の頂点に対し、第1のグラフ上の頂点から目的地22までのルートに関連するコストが決定される。そして、第2のステップ(すなわち、出発点21から目的地22までのルート検索)が、第1のステップにおけるルート検索において決定されたコストに基づくようにするために、第1のステップにおいて探索された全ての頂点に対して第1のステップにおいて決定されたコストは、第2のグラフ20’の対応するセグメントにマッピングされる。例えば、図12においては、第2のグラフ20’の頂点171〜178は、第1のグラフ20のエッジの中点に配置されて示されているが、第2のグラフ20’の頂点171〜178のうちの任意の頂点に対し、評価関数の値は、第2のグラフ20’のそれぞれの頂点によって表現されている道路セグメントの端点に対するコストに基づいて決定され得る。例えば、頂点21から目的地22までのルート、および頂点23から目的地22までのルートに対するコストが、第1のステップにおいて決定されたと仮定すると、第2のグラフ20’の頂点171に対する評価関数の値は、costs1(頂点23,d)と頂点23から頂点21までの道路セグメント41の通過に関連するコストとの和、およびcosts1(頂点21,d)と頂点21から頂点23までの道路セグメント41の通過に関連するコストの半分との和のうちの最小値に等しく決定され得る。ここで、costs1は、第1のステップにおいて第1のグラフに基づいて決定されたコストを表現している。第1のグラフ20の要素(すなわち、頂点および/またはエッジ)から第2のグラフ20’の対応する要素への評価関数のマッピングの後、第2のグラフ20’でのルート検索が、図1〜図10の上述の実施形態のうちの任意の実施形態に対して記載されたように実行され得る。
【0139】
第1のステップおよび第2のステップにおいて利用されるコストモデルは同じものであり得るが、第1のグラフおよび第2のグラフが異なるときには、互いに異なり得ることに留意されたい。特に、第1のグラフに基づいて評価関数の値を決定するために利用される第1のコストモデルは、ユーザの選好度によって生じる追加的なコスト、交通情報信号、時間変化するコストの寄与、等とは無関係であり得るが、これらは、第2のコストモデルにおいて考慮され得る。
【0140】
図12における第1および第2のグラフの概略図は、単に例示的なものであり、限定的な意味で解釈されるべきではないことに留意されたい。特に、第1および第2のグラフは、一方通行制限、反対の移動方向における異なる移動速度、移動方向に関係するターン制限、等を考慮するために、より複雑な方法で定義され得る。例えば、道路セグメントの各移動方向は、一方通行ではない通りの道路セグメントが、第1のグラフの2つのエッジおよび第2のグラフの2つの頂点のそれぞれによって表現され得るように、第1のグラフにおけるエッジによって、および第2のグラフにおける頂点によって表現され得る。
【0141】
図11に戻ると、161および164において利用される第1および第2のグラフは互いに異なるものであり得るので、第1のグラフは、第1のグラフ上のルート検索が、平均で第2のグラフ上のルート検索よりも速くなるように、選択され得る。例えば、第1のグラフは、これが第2のグラフよりも少ない頂点を有するように選択され得る。
【0142】
一実施形態において、第1のステップ(すなわち、評価関数の値を決定すること)は、道路セグメントの到達される方向に関する情報を無視し、1つの道路セグメントから別の道路セグメントへのターンに関連するコストを無視することによって、道路セグメントの中点の間のルート検索を実行することにより、実施され得る。言い換えると、第1のステップは、グラフによって表現される道路網においてターン制限が無視されるグラフ上で実行され得る。一方通行制限は依然として、考慮され得る。別の実施形態においては、一方通行制限はまた、無視され得る。そして、第2のステップは、図11および図12を参照して上述されたように、エッジが道路セグメントを表現する主グラフ上、または頂点が道路セグメントを表現する双対グラフ上のいずれかの上で、実行され得る。
【0143】
別の実施形態においては、第1のグラフ(第1のステップにおいて、この第1のグラフに基づいて評価関数が決定される)が主グラフであり得るが、第2のステップにおけるルート検索は、第2グラフ上で実行される。第1のステップにおいて、ターン制限は無視され得る。
【0144】
本発明の様々な実施形態にしたがう方法は、図1〜図12を参照して2つのステップのプロセスとして上述されてきたが、この方法はまた、2つ以上のステップを含み得る。上述の1つまたはいくつかのステップの結果は、その後のステップにおいて利用され得る。
【0145】
例えば、評価関数の値が決定される第1のステップは、いくつかのサブステップを含み得る。すなわち、第1のグラフの複数の頂点に対する評価関数の値の決定は、1つの段階の結果が別の段階において利用される複数の段階のプロセスであり得る。
【0146】
図13は、本発明の別の実施形態にしたがう方法190の流れ図であり、この方法にしたがって、評価関数の値の決定が、複数の段階のプロセスにおいて実行される。191において、目的地がユーザ入力によって指定される。192および193において、評価関数の値が、まず192において第3のグラフ上でルート検索を実行し、193においてこのルート検索の結果を第1のグラフ上のルート検索に利用することによって、決定される。第1のグラフ上でのルート検索の結果、複数の頂点に対する評価関数の値が得られる。194において、評価関数の値は、出発点から目的地までのルート検索において利用される。
【0147】
一実施形態においては、第3のグラフは、192および193における2段階のプロセスが、複数の頂点に対して評価関数の値をより容易に決定することを可能にするように、定義される。一実施形態では、193において、ルート検索は、目的地から出発して出発地に向かってA*−アルゴリズムを用いることによって実行される。192におけるルート検索は、第3のグラフ上で実行され、192において実行されたA*−アルゴリズムに対し、より正確な評価関数を提供する。
【0148】
2段階のプロセス192、193の例示的な実装が、図2の道路網20を示す図14Aおよび図14Bを参照して示される。例示的な実装において、第3のグラフ20”は、例えば欧州特許出願第06 012 160.5号に記載されているように、タイリング(tiling)に基づいて、かつタイリングのタイルに関する所定の情報(例えば、タイルの抵抗(resistance)を定量化する抵抗値)を利用して、定義される。
【0149】
図14Aに見られるように、タイリング201は、道路網20が含まれる領域をカバーし、複数のタイル202〜205を含むように定義される。タイリング201の任意のタイルに対し、グラフの幾何学的配置に関連して、タイルを通過するルートに関連するコストを定量化する所定の抵抗値が提供される。例えば、タイリングのタイル202〜205に対する抵抗値は、
【0150】
【化11】
に等しく定義され得、viおよびvjは、それぞれのタイルの境界上に配置される頂点を示しており、costs(vi,vj)は、グラフ上のviからvjまでのルートに関連する最小のコストを示しており、distance(vi,vj)は、viとvjとの間の直線距離を示している。
【0151】
図14Aおよび図14Bに示されているように、タイル202〜205に対する局所的な抵抗値に基づいて、単純化された第3のグラフ20”が定義され得、このグラフは、出発点21および目的地22を含むタイル以外のその他の全てのタイルにおいて、タイルの境界上に配置された頂点のみを含む。言い換えると、出発点21も目的地22も含まない任意のタイルに対しては、道路網20の頂点28および30に対する場合のように、タイル内に配置された頂点は省略される。タイル内部における頂点が省略されているタイルにおいては(例えば、図14におけるタイル205においては)、タイルの境界上に配置された頂点24、27、29、32を結ぶ新しいグラフのエッジ211〜214が定義され、これらのエッジはタイルの頂点の幾何学的配置およびタイルの抵抗値に基づくコストに関連する。より具体的には、頂点viおよびvjを結ぶ第3のグラフの新しく導入されるエッジに対するコストは、
【0152】
【化12】
に等しく設定され得る。例えば、エッジ214に対するコストは、タイル205の抵抗Rと、頂点29と頂点32との直線距離との積に等しく設定され得る。式(10)における抵抗値の定義から、第3のグラフの新しいエッジに対するコストは、実際のコストの下限を表現する。
【0153】
そして、図13の192において、上記で概説されたように構成される第3のグラフ20”に基づいて、直線距離ベースの評価関数を利用するDijkstraアルゴリズムまたはA*−アルゴリズムが、出発点21から出発して目的地22に向かって延長するように実行される。第3のグラフ20”の構成が理由で、第3のグラフ20”の出発点から任意の頂点までのルートに対するコストは、第1のグラフ20の出発点21から対応する頂点までのルートに関連するコストの下限を表現するので、193において第1のグラフ20上でA*−アルゴリズムが利用されるときに、評価関数の値として利用され得る。第1のグラフ20に含まれるが第3のグラフ20”には含まれない任意の頂点に対し(すなわち、内部に配置された頂点に対し)、193において利用される評価関数の値は、それぞれのタイルの境界に配置された頂点に対する評価関数の値から決定され得る。例えば、頂点28に対する評価関数の値は、頂点27、28、29、または32のうちの任意の頂点に対して決定されるコストの最小値に等しく設定され得る。上述の実施形態のうちの任意の実施形態に関連して記載されているように、第1のグラフ20の複数の頂点に対する評価関数の値の決定の後、方法は、第2のグラフ上の出発点から目的地までのルート検索へと進む。
【0154】
評価関数の値の決定が2段階のプロセスとして実装される場合のみが、図13および図14を参照して上述されてきたが、その他の実施形態においては、出発点からも目的地までの(すなわち、第2のステップの)ルート検索はまた、複数の段階のプロセスとしても実装され得る。さらに、本発明の様々な実施形態にしたがう方法は、2段階または3段階のプロセスに限定されず、任意の適切な複数のステップまたは段階、先のステップまたは段階から得られた結果を利用するその後のステップまたは段階を含み得る。
【0155】
概説すると、本発明にしたがって、ルートを決定するための方法およびデバイスが提供され、ルートは複数のステップのプロセスで決定される。好適または有利な実施形態の上記の記載から明らかなように、本発明の実施形態にしたがうと、第1のステップにおいて正確な評価関数が決定され得、これは、第2のステップにおいてルート検索の複雑さを低減させるために利用され得る。第1のステップにおいて決定される評価関数の値は、いくつかのルート検索に対して利用され得る。
【0156】
本発明は、有利にも任意の最適なルート検索に利用され得、特に、道路網上でルートを決定することに利用され得るが、道路網上でのルート決定には限定されない。
【図面の簡単な説明】
【0157】
【図1】図1は、本発明の一実施形態にしたがう、ルートを決定するためのデバイスを含むナビゲーションシステムの概略ブロック図を示している。
【図2A】図2Aおよび図2Bは、例示的な道路網を概略的に示している。
【図2B】図2Aおよび図2Bは、例示的な道路網を概略的に示している。
【図3】図3は、一実施形態にしたがう、ルートを決定するための方法の流れ図である。
【図4A】図4は、ルート検索において探索される地図の一部分を示しており、図4Aおよび図4Bは、本発明の一実施形態にしたがう、ルート検索の第1および第2のステップを表現しており、図4Cは、従来のルート検索を表現している。
【図4B】図4は、ルート検索において探索される地図の一部分を示しており、図4Aおよび図4Bは、本発明の一実施形態にしたがう、ルート検索の第1および第2のステップを表現しており、図4Cは、従来のルート検索を表現している。
【図4C】図4は、ルート検索において探索される地図の一部分を示しており、図4Aおよび図4Bは、本発明の一実施形態にしたがう、ルート検索の第1および第2のステップを表現しており、図4Cは、従来のルート検索を表現している。
【図5】図5は、別の実施形態にしたがう、ルートを決定するためお方法の流れ図である。
【図6】図6は、別の実施形態にしたがう、ルートを決定するための方法の流れ図である。
【図7】図7は、図2の例示的な道路網に対する図5および図6の方法にしたがう、ルート検索を概略的に示している。
【図8A】図8は、図6の方法にしたがう、ルート検索において探索される地図の一部分を示している。
【図8B】図8は、図6の方法にしたがう、ルート検索において探索される地図の一部分を示している。
【図9】図9は、ルート決定において、格納された評価関数の値を利用するためのステップを表現する流れ図である。
【図10】図10は、図2の例示的な道路網に対する図9のステップを概略的に示している。
【図11】図11は、別の実施形態にしたがう、ルートを決定するための方法の流れ図である。
【図12】図12は、図2の例示的な道路網を表現する第1のグラフおよび第2のグラフを概略的に示している。
【図13】図13は、別の実施形態にしたがう、ルートを決定するための方法の流れ図である。
【図14A】図14Aは、図2の例示的な道路網に対する図13の方法にしたがうルート検索を示しており、図14Bは、ルート検索において利用される第3のグラフを表現している。
【図14B】図14Aは、図2の例示的な道路網に対する図13の方法にしたがうルート検索を示しており、図14Bは、ルート検索において利用される第3のグラフを表現している。
【符号の説明】
【0158】
2 プロセッサ
3 格納ユニット
4 グラフデータ
5 データ
6 入力ユニット
7 出力ユニット
8 位置決定手段
9 交通メッセージ受信器
10 クロックユニット
20 第1のグラフ
20,20’ 第2のグラフ
22、82、132 目的地
21、81、131 出発点
61 ルート
【技術分野】
【0001】
本発明は、ルート決定に関し、より具体的には、評価関数に基づいて、例えば、道路網上のルートを決定するための方法に関する。有利にも、本発明の方法およびシステムは、ルート検索に利用され得、特に道路網におけるルートを(例えば、車両上で)検索するために利用され得る。
【背景技術】
【0002】
所与の出発点から所与の目的地までの良いルート(好適には最適なルート)を見つけることは、カーナビゲーションシステムまたはルーティング情報を提供するその他のシステムの鍵となる特徴のうちの1つである。本明細書の全体にわたって、用語「最適なルート(optimum route)」は、最小のコストのルートに対して用いられ、ルートのコストは、ルートによって通過(traverse)されるグラフのエッジおよび頂点のコストの和によって決定される。例えば、道路網においてルートが決定されるとき、ルートのコストは、通過される道路のセグメントのコスト、および道路のセグメントの接合部に関連するコストに対応する。使用されるコストモデルに依存して、コストは、距離、移動時間、および/またはユーザの選好度を反映し得る。同様に、例えば用語「良いルート(good route)」は、少ないコストに関連するルートを意味する(すなわち、ルートの移動に対して生じるコストに関して、ルートの品質が測定される)。一連のエッジおよび一連の頂点(グラフのエッジが相互接続している)によって定義される所与のグラフに対し、様々なコストモデルが定義され得る。例えば、ナビゲーションシステムにおいて、様々なコストモデルは、様々な最適化の基準(例えば、最速ルート、最短ルート、トンネルの回避、ハイウェイの回避、フェリーの回避、有料道路の回避、等)、ならびにこれらのオプションおよび選好度の組み合わせに対応し得る。
【0003】
(関連技術)
グラフ上で最適なルートまたは良いルートを見つけるためのいくつかの標準的なアルゴリズムが、当該技術分野において公知であり、それらのうちで最も有名なものは、DijkstraアルゴリズムおよびA*−アルゴリズムである。
【0004】
Dijkstraアルゴリズムにおいては、道路網(または、より一般的にはグラフ)は、エッジの伸縮(relaxation)または延長(expansion)によって、ルートの出発点から出発して探索される。道路網の様々な頂点は、頂点と出発点とを結ぶルートに関連する順序にしたがって訪問される。グラフのエッジの延長において、目的地に到達したとき、出発点から目的地までの最適なルートが見つけられ、Dijkstraアルゴリズムが終了する。
【0005】
A*−アルゴリズムは、Dijkstraアルゴリズムの改変であり、このA*−アルゴリズムは、グラフの頂点に対する評価関数を利用する。所与の頂点に対する評価関数は、所与の頂点と目的地とを結ぶ最適なルートに関連するコストに対する評価を提供する。ルート検索においては、様々な経路が、出発点からそれまでの頂点までに生じたコストの和および頂点に対する評価関数の値によって与えられる優先順位にしたがって、ランク付けされる。評価関数が、頂点と目的地とを結ぶ最適なルートのコストを決して過大評価することがない場合、A*−アルゴリズムが最適経路問題に対する正しい解を見つけることが公知である。従来、評価関数は、単純な幾何学的基準(例えば、直線距離(air distance))に基づいて、決定される。
【0006】
カーナビゲーションのためのルート検索は、しばしば、ターン制限に適応するために、道路網の双対グラフ(双対グラフの頂点は、道路網の道路セグメントを表現している)に対して実行される。多くの用途において、ルート検索は、今日では、追加的な便利な特徴(例えば、いくつかの代替ルートを決定すること、ユーザの選好度に適応すること、動的なルーティング、等)を提供することが期待されている。ルート検索を実行するための双対グラフと上述の追加的な特徴との両方は、格納空間および計算時間の要件の観点から見てコストが高い。
【発明の開示】
【発明が解決しようとする課題】
【0007】
したがって、当該技術分野においては、ルート検索の複雑さを減少させることを可能にするルートを決定するための改良された方法およびデバイスに対する必要性が存在する。特に、当該技術分野においては、適度な格納空間および/または計算時間の要件を有するルートを決定するための改良された方法およびデバイスに対する必要性が存在する。
【課題を解決するための手段】
【0008】
本発明にしたがうと、この必要性は、独立請求項によって定義される方法およびデバイスによって対処される。従属請求項は、好適または有利な実施形態を定義する。
【0009】
本発明の一局面にしたがうと、ルートを決定するための方法が提供される。この方法は、第1のステップにおいて、第1のグラフに基づいて評価関数の値を決定することであって、頂点に対する評価関数の値は、その頂点から目的地までのルートに関連するコストの下限を表現している、ことと、第2のステップにおいて、第1のステップにおいて決定された評価関数の値に基づいて、第2のグラフ上で出発点から目的地までのルートを検索することとを含む。評価関数の値は、直線距離ベースの評価だけに基づいて決定されるのではなく、第1のグラフに基づいて決定されるので、評価関数は、この評価関数が頂点から目的地までの最短のルートに対する実際のコストを良く近似するように決定され得る。そのような近似関数は、以下では「良い(good)」近似関数として称される。そして、良い評価関数は、第2のステップにおけるその後のルート検索の複雑さを低減するために利用され得る。
【0010】
第1のステップにおいて評価関数の値を決定することは、第1のグラフ上で頂点から目的地までのルートを検索することを含み得、この検索は、第1のグラフ上でDijkstraアルゴリズムまたはA*−アルゴリズムを用いることによって実行され得る。第1のグラフ上でのルート検索は、目的地から出発して検索を出発点に向けて延長することによって実行され得る。言い換えると、第1のステップにおいて、検索方向は逆転され得る。第1のグラフ上でルート検索の間に探索される頂点に対し、第1のグラフ上でルート検索を実行することによって、評価関数の値が決定されるとき、良い評価関数が提供され得、この良い評価関数は、それぞれの頂点から目的地までの任意のルートに関連する真の最小のコストを表現し得るか、または少なくとも真の最小のコストに対する良い近似を提供し得る。この評価関数の値に基づいて、第2の検索におけるその後の検索の検索ツリーのサイズが低減され得る。
【0011】
第2のステップにおいて、評価関数の値に基づいて、前記ルートとは異なる目的地までの少なくとも1つのさらなるルートが検索または決定され得る。少なくとも1つのさらなるルートは、出発点から目的地までの代替ルート、または別の出発点から目的地までのルートのうちの少なくとも1つを含み得る。別のルートに対する検索は、例えば、車両が所定のルートから逸れたとき、または第2のグラフのエッジまたは頂点に対するコストが変化したときに開始され得、これは例えば、ユーザによって指定された回避オプション、交通情報信号、または動的なルーティングによってもたらされ得る。複数のルート検索に対する第1のステップの結果(すなわち、評価関数の値)を利用することによって、所与のルート検索に必要な平均の計算時間が、低減され得る。なぜならば、中間の結果(すなわち、評価関数の値)が繰り返し用いられ得るからである。
【0012】
第1のステップにおいて決定された評価関数の値のうちの少なくともサブセットが格納され得、第2のステップにおいて抽出され得る。
【0013】
第1のステップにおいて評価関数の値を決定することは、第1のコストモデルに基づき得、第2のステップにおいて出発点から目的地までのルートを検索することは、第2のコストモデルに基づき得る。第1および第2のコストモデルは異なり得るので、第1のモデルの適切な選択によって、第1のステップにおいて決定された評価関数の値は、いくつかの異なる第2のコストモデルに対して再利用され得る。特に、第1のコストモデルにしたがう、第1のグラフの頂点および/またはエッジに関連するコストは、第2のコストモデルにしたがう、第2のグラフの対応する頂点および/またはエッジに関連するコストの下限を表現し得る。このようにして、第1のモデルに基づいて決定された評価関数の値は、第2のコストモデルに基づくルート検索に対してでさえも、目的地までのルート上で生じるコストの有効な下からの評価を提供する。
【0014】
第1のコストモデルにしたがう第1のグラフの頂点および/またはエッジに関連するコストは、時間に関係しないものであり得る。第2のコストモデルにしたがう第2のグラフの頂点および/またはエッジは、可変であり得る。第2のコストモデルにしたがうコストは、ユーザの選好度、交通情報信号、時刻または日付のうちの少なくとも1つに基づいて変化し得る。第2のコストモデルにしたがうコストの変化は、第1のコストモデルに対して少なくとも1つの頂点および/またはエッジに対するコストを増加させることによって実施され得る。同様に、可変のコストの寄与を考慮しない第1のコストモデルが、評価関数の値を決定するために利用され得る。
【0015】
第1のグラフは、第1のグラフ上のルート検索が、例えば第1のグラフが第2のグラフよりも少ない頂点を有するように第1のグラフを定義することによって、平均で、第2のグラフ上のルート検索よりも速くなるように定義され得る。第1のグラフのそのような適切な定義によって、評価関数の値を決定する際の計算の複雑さおよび/または格納空間の要件が、低減され得る。例えば、第1のグラフの頂点は、道路網の道路セグメントを表現し得、第1のステップにおいて、道路網におけるターン制限が無視され得る。第1および第2のグラフはまた、第1のグラフのエッジが道路網の道路セグメントを表現し、第2のグラフの頂点が道路網の道路セグメントを表現するように定義され得る。すなわち、第1および第2のグラフは、互いに対する双対グラフであり得る。別の実施形態において、第1のグラフは、第2のグラフと同じものであり得る。
【0016】
方法はまた、2つ以上のステップまたは段階で実行され得る。例えば、第1のステップは、第3のグラフを定義することと、第3のグラフ上でルート検索を実行することと、第3のグラフ上でのルート検索の結果を利用し、複数の頂点に対する評価関数の値を決定することとを含み得る。先の段階の結果をその後の段階に繰り返し利用することによって、ルート検索の計算の複雑さが、さらに低減され得る。
【0017】
グラフは、道路網、コンピュータネットワーク、またはインフラストラクチャネットワークのうちの1つを表現し得る。特に、様々な実施形態にしたがう方法は、道路網上のルーティングに利用され得、車両上のナビゲーションシステムによって実行され得る。
【0018】
本発明の別の局面にしたがうと、目的地(特に、道路網上の目的地)までのルートを決定するためのデバイスが提供される。デバイスは、第1のグラフおよび第2のグラフのうちの少なくとも1つのグラフの頂点およびエッジを定義するグラフデータを格納する格納ユニット、および格納ユニットに接続され、グラフデータを抽出するプロセッサを含んでいる。プロセッサは、第1のステップにおいて、第1のグラフに基づいて、複数の頂点に対する評価関数の値を決定し、頂点に対する評価関数の値は、頂点から目的地までのルートに関連するコストの下限を表現しており、第2のステップにおいて、第1のステップにおいて決定された評価関数の値に基づいて、第2のグラフ上で出発点から目的地までのルート検索を実行する。プロセッサは、直線距離ベースの評価だけを利用するのではなく、第1のグラフに基づいて評価関数の値を決定するので、良い評価関数が決定され得、有利にも第2のステップにおいて、その後のルート検索のために装備され得る。
【0019】
プロセッサは、第1のグラフ上でルート検索を実行し、評価関数の値を決定し得る(例えば、目的地から出発し、出発点に向けて延長することによって、評価関数の値を決定し得る)。
【0020】
第2のステップにおいて、プロセッサは、第1のステップにおいて決定された評価関数の値に基づいて、目的地までの少なくとも1つのさらなるルート検索を実行することによって、第1のステップにおいて得られた結果を第2のステップにおける複数のルート検索に利用し得る。いくつかのルート検索に対して中間の結果(すなわち、評価関数の値)を再利用することによって、各ルート検索に必要な平均の計算時間は、低減され得る。
【0021】
プロセッサは、第1のステップにおいて、第1のコストモデルに基づいて、評価関数の値を決定し得、第2のステップにおいて、第2のコストモデルに基づいて、出発点から目的地までのルート検索を実行し得る。第1および第2のコストモデルは、異なり得る。特に、第1のコストモデルにしたがう第1のグラフの頂点および/またはエッジに関連するコストは、時間に関係しないものであり得、第2のコストモデルにしたがう第2のグラフの頂点および/またはエッジに関連するコストは、可変であり得る。このように、第1のコストモデルのコストが、特定の用途に対して考慮される第2のコストモデルの対応するコストの下限を表現するように、第1のコストモデルを適切に選択することによって、時間に関係しない第1のコストモデルに基づいて決定される評価関数の値は、第2のコストモデルが変化するコストを含んでいるときでさえも、異なる第2のコストモデルに対して再利用され得る。
【0022】
デバイスは、ユーザ入力を受信する入力ユニットを含み得、プロセッサは、この入力ユニットに接続され、ユーザ入力に基づいて、第2のコストモデルのコストを調整し得る。加えてまたはあるいは、デバイスは、時刻および/または日付を決定するクロックユニットを含み得、プロセッサは、このクロックユニットに接続され、時刻および/または日付に基づいて、第2のコストモデルのコストを調整し得る。加えてまたはあるいは、デバイスは、交通情報信号を受信する交通メッセージ受信器を含み得、プロセッサは、交通メッセージ受信器に接続され、交通情報信号に基づいて、第2のコストモデルのコストを調整し得る。したがって、デバイスは、ユーザの選好度に基づいて、動的なルーティングにおける時刻または日付に基づいて、または交通情報に基づいて、第2のコストモデルのコストを調整するように構成され得る。
【0023】
デバイスはまた、現在の車両の位置を決定する位置決定手段を含み得、プロセッサは、位置決定手段に接続され、現在の車両の位置を出発点から目的地までのルートと比較する。プロセッサは、比較の結果に基づいて、第2のグラフ上での現在の車両の位置から目的地までのさらなるルート検索を自動的に実行し得る。
【0024】
様々な実施形態にしたがうデバイスは、プロセッサが、本発明の局面または実施形態のうちの任意のものにしたがう方法を実行し得るように、構成され得る。
【0025】
別の局面にしたがうと、ナビゲーションシステムが提供され、このナビゲーションシステムは、目的地を指定する入力を受信する入力ユニットと、ルートに関する情報を出力する出力ユニットと、本発明の任意の一実施形態にしたがってルートを決定するデバイスとを含む。ナビゲーションシステム(このナビゲーションシステムは、携帯型のナビゲーションシステムであったり、または車両上に据え付けられたりし得る)は、車両上でルート検索が実行されることを可能にする。
【0026】
別の局面にしたがうと、データ格納媒体(このデータ格納媒体上には命令が格納されている)が提供され、この命令は、ナビゲーションシステムのプロセッサによって実行されたときに、プロセッサに、本発明の局面または実施形態のうちの任意のものにしたがう方法を実行するように命令し得る。
【0027】
本発明を説明するために、以下では本発明のいくつかの実施形態が「道路網(road network)」に関連して記載されるが、本発明の用途は、物理的な道路網に限定されない。むしろ、本発明は、ルート検索が実行され得る任意のネットワークまたはグラフに応用され得る。実施例は、フェリー接続、コンピュータネットワークにおけるデータ接続、電線、または航空機のルートを含む。
【0028】
さらに、本発明は2次元空間に埋め込まれ得るグラフに関連して記載されるが、本発明はそのようなグラフに限定されないことに留意されたい。むしろ、本発明の原理は、高次元の対象(例えば、3次元のグラフ)にも等しく応用可能である。
【0029】
本発明の応用分野のうちの1つは、道路網におけるルートの決定、特に、車両上のナビゲーションシステムの道路網におけるルートの決定であることが企図されている。
【0030】
本発明は、さらに以下の手段を提供する。
【0031】
(項目1)
目的地、特に道路網上の目的地(22;82;132)までのルートを決定するための方法であって、
第1のステップにおいて、第1のグラフ(20)に基づいて、複数の頂点(23、24、25、27、28、32、33)に対する評価関数の値を決定することであって、頂点(21〜33)に対する評価関数の値は、該頂点(21〜33)から該目的地(22;82;132)までのルートに関連するコストの下限を表現している、ことと、
第2のステップにおいて、該第1のステップにおいて決定された該評価関数の値に基づいて、第2のグラフ(20;20’)上で、出発点(21;81;131)から該目的地(22;82;132)までのルート(61)を検索することと
を包含する、方法。
【0032】
(項目2)
上記第1のステップにおいて、頂点(21〜33)に対する評価関数の値を決定することは、上記第1のグラフ(20)上で該頂点(21〜33)から上記目的地(22;82;132)までのルートを検索することを含む、項目1に記載の方法。
【0033】
(項目3)
上記頂点(21〜33)から上記目的地(22)までの上記ルートを検索することは、上記第1のグラフ(20)上でDijkstraアルゴリズムまたはA*−アルゴリズムを用いて実行される、項目2に記載の方法。
【0034】
(項目4)
上記第1のステップにおいて頂点(21〜33)に対する評価関数の値を決定することは、上記第1のグラフ上で、上記目的地(22;82;132)から出発して上記出発点(21;81;131)まで延長するルート検索を実行することを含む、項目1〜項目3のいずれか一項に記載の方法。
【0035】
(項目5)
上記第2のステップにおいて、上記評価関数の値に基づいて、上記目的地(22;82;132)までのルート(61)とは異なる少なくとも1つのさらなるルート(121;151)を検索すること
を含む、項目1〜項目4のいずれか一項に記載の方法。
【0036】
(項目6)
上記少なくとも1つのさらなるルート(121;151)は、上記出発点(21)から上記目的地(22)までの代替ルート(121;151)、または別の出発点(135)から上記目的地(132)までのルートのうちの少なくとも1つを含む、項目5に記載の方法。
【0037】
(項目7)
上記出発点(21;131)から上記目的地(22;132)までの上記ルート(61)に対する現在の位置(135)をモニタリングすることであって、上記少なくとも1つのさらなるルートの上記検索は、該現在の位置(135)の該モニタリングの結果に基づいて自動的に開始される、こと
を含む、項目5または項目6に記載の方法。
【0038】
(項目8)
上記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜45;181〜185)に関連するコストの変化をモニタリングすることであって、上記少なくとも1つのさらなるルート(121;151)の上記検索は、該変化をモニタリングした結果に基づいて自動的に開始される、こと
を含む、項目5〜項目7のいずれか一項に記載の方法。
【0039】
(項目9)
上記第1のステップにおいて決定された上記評価関数の値の少なくともサブセット(5)を格納することと、
上記第2のステップにおいて該サブセット(5)の少なくとも1つの評価関数の値を抽出することと
を含む、項目1〜項目8のいずれか一項に記載の方法。
【0040】
(項目10)
上記第1のステップにおける上記評価関数の値の上記決定は、第1のコストモデルに基づいており、上記第2のステップにおける上記出発点(21;81;131)から上記目的地(22;82;132)までの上記ルート(61)の検索は、第2のコストモデルに基づいている、項目1〜項目9のいずれか一項に記載の方法。
【0041】
(項目11)
上記第1のコストモデルにしたがう、上記第1のグラフ(20)の上記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、時間に関係しない、項目10に記載の方法。
【0042】
(項目12)
上記第2のコストモデルにしたがう、上記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストは可変である、項目10または項目11に記載の方法。
【0043】
(項目13)
ユーザの選好度、交通情報信号、時刻または日付のうちの少なくとも1つに基づいて、上記第2のコストモデルにしたがう上記コストを調整すること
を含む、項目12に記載の方法。
【0044】
(項目14)
上記調整することは、少なくとも1つの頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に対し、上記第1のコストモデルに対して
上記第2のコストモデルにしたがうコストを増加させることを含む、項目13に記載の方法。
【0045】
(項目15)
上記第1のコストモデルにしたがう上記第1のグラフ(20)の頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、上記第2のコストモデルにしたがう対応する頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストの下限を表現する、項目12〜項目14のいずれか一項に記載の方法。
【0046】
(項目16)
上記第1のグラフ(20)は、該第1のグラフ(20)上のルート検索が、平均で、該第2のグラフ(20’)上のルート検索よりも速くなるように定義される、項目1〜項目15のいずれか一項に記載の方法。
【0047】
(項目17)
上記第1のグラフ(20)は、上記第2のグラフ(20’)よりも少ない頂点(21〜33)を有している、項目1〜項目16のいずれか一項に記載の方法。
【0048】
(項目18)
上記第1のグラフの頂点は、上記道路網の道路セグメントを表現しており、上記第1のステップにおいて、該道路網上のターン制限は無視される、項目1〜項目17のいずれか一項に記載の方法。
【0049】
(項目19)
上記第1のステップにおいて、一方通行制限が考慮される、項目18に記載の方法。
【0050】
(項目20)
上記第1のグラフ(20)のエッジ(41〜55)は、道路網の道路セグメントを表現しており、上記第2のグラフ(20’)の頂点(171〜178)は、該道路網の道路セグメントを表現している、項目1〜項目17のいずれか一項に記載の方法。
【0051】
(項目21)
上記第1のグラフ(20)は、上記第2のグラフ(20’)の双対グラフによって構成される、項目20に記載の方法。
【0052】
(項目22)
上記第1のグラフ(20)は、上記第2のグラフ(20)と同じものである、項目1〜項目15のいずれか一項に記載の方法。
【0053】
(項目23)
上記第1のステップは、第3のグラフ(20”)を定義すること、該第3のグラフ(20”)上でルート検索を実行すること、および該第3のグラフ(20”)上での該ルート検索の結果を利用して、上記複数の頂点(23、24、25、27、28、32、33)に対する評価関数を決定することを含む、項目1〜項目22のいずれか一項に記載の方法。
【0054】
(項目24)
上記第1のステップにおいて頂点(23、24、25、27、28、32、33)に対する評価関数の値を決定することは、上記第1のグラフ(20)上で予め計算された情報に基づいて、該第1のグラフ(20)上で該頂点(23、24、25、27、28、32、33)から上記目的地(22)までのルートを検索することを含む、項目1〜項目23のいずれか一項に記載の方法。
【0055】
(項目25)
上記第2のステップにおいて上記ルート(61)を検索することは、上記第1のステップにおいて所与の頂点(29)に対する評価関数の値が決定されたかどうかを決定することを含み、該第1のステップにおいて評価関数の値が決定されていない場合には、該所与の頂点(29)に対する評価関数の値を決定することを含む、項目1〜項目24のいずれか一項に記載の方法。
【0056】
(項目26)
上記第1のグラフ(20)および上記第2のグラフ(20;20’)は、道路網、コンピュータネットワーク、またはインフラストラクチャネットワークのうちの1つを表現する、項目1〜項目25のいずれか一項に記載の方法。
【0057】
(項目27)
上記方法は、車両上のナビゲーションシステム(1)によって実行される、項目1〜項目26のいずれか一項に記載の方法。
【0058】
(項目28)
目的地、特に道路網上の目的地(22;82;132)までのルートを決定するためのデバイスであって、
グラフデータ(4)を格納する格納ユニット(3)であって、該グラフデータ(4)は、第1のグラフ(20)および第2のグラフ(20;20’)のうちの少なくとも1つの頂点(21〜33)およびエッジ(41〜55)を定義する、格納ユニット(3)と、
該格納ユニット(3)に接続されたプロセッサ(2)であって、該プロセッサ(2)は、該グラフデータ(4)を抽出し、該プロセッサは、第1のステップにおいて、該第1のグラフ(20)に基づいて、複数の頂点(23、24、25,27、28,32、33)に対する評価関数の値を決定し、頂点(21〜33)に対する評価関数の値は、該頂点(21〜33)から該目的地(22;82;132)までのルートに関連するコストの下限を表現しており、該プロセッサは、第2のステップにおいて、該第1のステップにおいて決定された該評価関数の値に基づいて、第2のグラフ(20;20’)上で、出発点(21;81;131)から該目的地(22;82;132)までのルート検索を実行する、プロセッサ(2)と
を備えている、デバイス。
【0059】
(項目29)
上記プロセッサ(2)は、上記第1のグラフ(20)上でルート検索を実行し、上記評価関数の値を決定する、項目28に記載のデバイス。
【0060】
(項目30)
上記プロセッサ(2)は、上記目的地(22;82;132)から出発して上記出発点(21;81;131)まで延長するルート検索を実行し、上記評価関数の値を決定する、項目28または項目29に記載のデバイス。
【0061】
(項目31)
上記第2のステップにおいて、上記プロセッサ(2)は、上記第1のステップにおいて決定された上記評価関数の値に基づいて、上記目的地(22;82;132)までの少なくとも1つのさらなるルート検索を実行する、項目28〜項目30のいずれか一項に記載のデバイス。
【0062】
(項目32)
さらなる格納ユニット(3)を含み、上記プロセッサ(2)は、該さらなる格納ユニット(3)に接続されており、上記第1のステップにおいて決定された上記評価関数の値(5)を該さらなる格納ユニット(3)に格納し、上記第2のステップを実行するために該さらなる格納ユニット(3)から該評価関数の値(5)を抽出する、項目28〜項目31のいずれか一項に記載のデバイス。
【0063】
(項目33)
上記プロセッサ(2)は、第1のコストモデルに基づいて、上記第1のステップにおいて上記評価関数の値を決定し、第2のコストモデルに基づいて、上記第2のステップにおいて上記出発点(21;81;131)から上記目的地(22;82;132)までのルート検索を実行する、項目28〜項目32のいずれか一項に記載のデバイス。
【0064】
(項目34)
上記第1のコストモデルにしたがう、上記第1のグラフ(20)の上記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは時間に関係せず、上記第2のコストモデルにしたがう、上記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストは可変である、項目33に記載のデバイス。
【0065】
(項目35)
上記第1のコストモデルにしたがう、上記第1のグラフ(20)の上記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、上記第2のコストモデルにしたがう、上記第2のグラフ(20;20’)の対応する頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストの下限を表現する、項目33または項目34に記載のデバイス。
【0066】
(項目36)
ユーザ入力を受信する入力ユニット(6)を含み、上記プロセッサ(2)は、該入力ユニット(6)に接続されており、該ユーザ入力に基づいて、上記第2のコストモデルのコストを調整する、項目33〜項目35のいずれか一項に記載のデバイス。
【0067】
(項目37)
時刻および/または日付を決定するクロックユニット(10)を含み、上記プロセッサ(2)は、該クロックユニット(10)に接続されており、該時刻および/または日付に基づいて、上記第2のコストモデルのコストを調整する、項目33〜項目36のいずれか一項に記載の方法。
【0068】
(項目38)
交通情報信号を受信する交通メッセージ受信器(9)を含み、上記プロセッサ(2)は、該交通メッセージ受信器(9)に接続されており、該交通情報信号に基づいて、上記第2のコストモデルのコストを調整する、項目33〜項目37のいずれか一項に記載の方法。
【0069】
(項目39)
上記プロセッサ(2)は、少なくとも1つの頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に対し、上記第1のコストモデルに対して上記第2のコストモデルのコストを増加させ、該第2のコストモデルのコストを調整する、項目36〜項目38のいずれか一項に記載のデバイス。
【0070】
(項目40)
現在の車両の位置(135)を決定する位置決定手段(8)を含み、上記プロセッサ(2)は、該位置決定手段(8)に接続されており、該現在の車両の位置(135)を上記出発点(21;81;131)から上記目的地(22;82;132)までの上記ルート(61)と比較し、該比較の結果に基づいて、上記第2のグラフ(20;20’)上での該現在の車両の位置(135)から該目的地(132)までのさらなるルート検索を実行する、項目28〜項目39のいずれか一項に記載のデバイス。
【0071】
(項目41)
上記第1のグラフ(20)は、該第1のグラフ(20)上のルート検索が、平均で、該第2のグラフ(20’)上のルート検索よりも速くなるように定義される、項目28〜項目40のいずれか一項に記載のデバイス。
【0072】
(項目42)
上記プロセッサ(2)は、項目1〜項目27のいずれか一項に記載の方法を実行するように構成されている、項目28〜項目41のいずれか一項に記載のデバイス。
【0073】
(項目43)
ルートを決定する項目28〜項目42のいずれか一項に記載のデバイスと、
該ルート上の情報を出力する出力ユニット(7)と
を含む、ナビゲーションシステム。
【0074】
(項目44)
データ格納媒体であって、該データ格納媒体上に命令を有しており、該命令は、ナビゲーションシステム(1)のプロセッサ(2)によって実行されたときに、該ナビゲーションシステム(1)に、項目1〜項目27のいずれか一項に記載の方法を実行するように命令する、データ格納媒体。
【0075】
(摘要)
目的地(特に、道路網上の目的地)までのルートを決定するための方法およびデバイスが提供される。この方法は、ステップ(72)において、第1のグラフに基づいて複数の頂点に対する評価関数の値を決定し、頂点から目的地までのルートに関連するコストの下限を表現する頂点に対する評価関数の値を決定することと、第2のステップ(73)において、第1のステップ(72)において決定された評価関数の値に基づいて、第2のグラフ上で出発点から目的地までのルートを検索することとを含む。
【発明を実施するための最良の形態】
【0076】
本発明の追加的な特徴および利点は、添付の図面を参照すると、好適または有利な実施形態に関する以下の詳細な記載から、より容易に理解される。
【0077】
(好適な実施形態の記載)
本明細書において以後、本発明の実施形態が、図面を参照して説明される。以下の記載は、本発明をより良く説明する目的のためにのみ与えられ、限定的な意味で解釈されるべきではないことが理解されるべきである。特に断りがない限り、以下に記載される様々な実施形態の特徴は、互いに組み合わされ得るということもまた、理解されるべきである。
【0078】
以下、本発明は、道路網を表現するグラフ上のルート検索に関連して記載されるが、本発明は、この用途に限定されず、任意のグラフまたはネットワークにおけるルートを決定するために容易に用いられ得ることに留意されたい。例えば、本発明は、電源ネットワークにおけるルート検索、信号伝送のための光学ネットワークまたは電気ネットワークにおけるルート検索、コンピュータネットワークまたはその他任意のインフラストラクチャまたはその他のネットワークにおけるルート検索に適用され得る。
【0079】
図1を参照し、本発明の一実施形態にしたがう、ナビゲーションシステム1が記載される。このナビゲーションシステム1は、本発明の一実施形態にしたがう、ルートを決定するためのデバイスを含んでいる。システムは、プロセッサ2、グラフデータ4を含む格納ユニット3、入力ユニット6、出力ユニット7、位置決定手段8(例えば、GPS受信器)、交通情報信号を受信するための交通メッセージ受信器9、ならびに時刻および/または日付を提供するクロックユニット10を含んでいる。
【0080】
プロセッサ2は、格納ユニット3に格納されたグラフデータ4によって表現されるグラフ上でルート検索を実行するように構成されている。特に、プロセッサ2は、評価関数に基づく検索方法または検索アルゴリズム(例えば、A*−アルゴリズムまたはそのバリエーション)を利用するルート検索を実行するように構成されている。格納ユニット3は、任意の適切な格納媒体(例えば、CD−ROM、CD−RW、DVD、メモリカード、または内部ハードディスク)によって構成されている。グラフデータ4は、道路網の頂点および/またはエッジに関する情報を含んでいる。例えば、グラフデータ4は、道路セグメントの端点の地理的位置に関する情報、およびこれら端点におけるその他の道路セグメントに対する接続(例えば、道路の接合部または交差部)に関する情報を含み得る。グラフデータはさらに、道路セグメントまたは道路セグメントの頂点に関連するコストに関する情報を含み得る。グラフの道路セグメントまたは道路セグメントの頂点に関連する一連のコストは、本明細書において以後、「コストモデル(cost model)」と称される。コストモデルに応じて、これらのコストは、最短ルートコストモデルに対しては道路セグメントの長さを表現し得る。あるいは、これらのコストは、最速ルートコストモデルに対しては、道路セグメントの移動時間、および接合部または交差部における、1つの道路セグメントから別の道路セグメントへと曲がるための時間を表現し得る。その他の様々なコストモデルに対応するコスト(例えば、ユーザの選好度に依存して、道路セグメントまたは道路セグメントの頂点のコスト値の増分または絶対値を表現するコスト)もまた、格納ユニット3に格納され得る。さらに、格納ユニット3はまた、複数の道路セグメントまたは道路セグメントの頂点に対する評価関数のデータ5、道路セグメントの頂点から目的地までのルートに関連するコストの下限を表現する道路セグメントの頂点に対する評価の値をも格納し得る。以下でより詳細に説明されるように、ユーザによる目的地の入力後、プロセッサ2は、評価関数のデータ5を決定し、データ5を格納ユニット3に格納する。その他の例示的な実施形態において、評価関数のデータ5はまた、グラフデータを格納する格納ユニット3とは別のさらなる格納ユニットに格納されたり、またはワーキングメモリに保持されたりし得る。一実施形態において、プロセッサ2は、ルート検索の目的地と出発点との両方に基づいて、評価関数のデータ5を決定し得る。一実施形態において、プロセッサ2は、ルート検索の出発点を、GPS受信器8によって決定された現在の車両の位置と同じ位置に設定したり、または現在の車両の位置に基づいて決定された位置と同じ位置に設定したりし得る。
【0081】
目的地に関する情報およびユーザの選好度は、入力ユニット6を介して、システム1に入力され得、この入力ユニット6は、例えば、タッチスクリーン、キーパッド、またはマイクロフォンおよび音声認識デバイスとして構成され得る。プロセッサ2は、入力ユニット6を介して入力された情報を評価し、ルートの検索を実行したり、またはユーザの選好度に基づいてコストモデルのコストを調整したりし得る。出発点から目的地までのルートに関する情報は、出力ユニット6を介してユーザに出力される。この出力ユニット6は、例えば、ディスプレイスクリーンおよび/またはラウドスピーカを含み得る。
【0082】
位置決定手段8によって決定された現在の車両の位置、および交通メッセージ受信器9において受信された交通情報は、プロセッサ2に提供される。このプロセッサ2は、以下で図5〜図8を参照してより完全に記載されるように、格納ユニット3に格納された評価関数のデータ5を利用することによって、位置決定手段8および/または交通メッセージ受信器9によって提供される情報に基づいて、新しいルート検索を開始する。同様に、クロックユニット10は、プロセッサ2に現在時刻を提供し、このプロセッサ2は、例えば動的なルーティングにおいては、交通状況の変化に起因する道路セグメントおよび/または道路セグメントの頂点に関連するコストの時間変化を考慮することによって、現在時刻に基づいてルート検索が実行されるグラフに対するコストモデルを調整し得る。
【0083】
図2および図3を参照し、一実施形態にしたがう、道路網上のルートを決定するための方法が記載される。この方法は、ナビゲーションシステム1の格納ユニット3に接続されたプロセッサ2によって実行され得る。
【0084】
図2Aおよび図2Bは、例示的な道路網20を示しており、これを参照して、ルートを決定するための方法が説明される。道路網は、図2においては箱(box)として示されている複数の道路セグメントの頂点21〜33を含んでおり(この例においては、13個が示されている)、複数の道路セグメント41〜56(この例においては、16個が示されている)によって、相互接続されている。道路セグメント41〜56は、図2の道路ネットワーク20を表現するグラフのエッジを形成している。
【0085】
図3は、実施形態にしたがう、ルートを決定するための方法70の流れ図である。この方法にしたがい、道路網20上のルート検索が、2つのステップまたは段階で実行される。すなわち、第1のステップまたは段階においては、道路網20に基づいて、道路網20の複数の頂点21〜33に対して、評価関数の値が決定される。第2のステップまたは段階においては、出発点(図2においては21として示されている)から目的地(図2においては22として示されている)までのルートを検索するために、評価関数の値が利用される。
【0086】
対応して、方法70では、71において、少なくとも所望の目的地を示すユーザ入力が受信される。72においては、道路網を表現する第1のグラフに基づいて、複数の頂点に対し、評価関数の値が決定される。72において決定された頂点に対する評価関数の値は、頂点から目的地までのルートに関連するコストに関する下限を提供する。73においては、72において決定された評価関数の値に基づいて、目的地までのルートに対する検索が実行される。本明細書においては、72における評価関数の値の決定に関連して用いられているように、用語「第1のグラフに基づいて(based on the first graph)」は、第1のグラフの個々の頂点の幾何学的配置に基づくだけではなく、グラフのエッジによる第1のグラフの少なくとも2つの頂点の相対的な配置および/または相互接続にも基づく動作を意味する。
【0087】
以下でより詳細に説明されるように、評価関数の値を決定するために72において利用される第1のグラフは、第2のグラフと同じまたは異なるものであり得、この第2のグラフに対して、第2のステップのルート検索が73において実行される。1つの例示的な実施形態においては、72において利用される第1のグラフと73において利用される第2のグラフとの両方は、ルート検索が実行される道路網を表現しており、第1のグラフおよび第2のグラフのエッジは、道路セグメントに対応する。すなわち、図2の例示的な道路網20に対して、道路セグメント41〜56は、第1のグラフと第2のグラフとの両方のエッジに対応し得、道路セグメントの頂点21〜33は、第1のグラフと第2のグラフとの両方の頂点に対応し得る。
【0088】
方法70の多くの改変が、実施され得ることが理解されるべきである。例えば、73におけるルート検索および72における評価関数の値の決定は、例えば、図5〜図8を参照して以下でより詳細に説明されるように、様々なコストモデルに基づき得る。73におけるルート検索はまた、例えば、図9および図10を参照して以下でより詳細に説明されるように、72において決定されなかった評価関数の値にも基づき得る。72において評価関数の値を決定するために利用される第1のグラフ、および73においてルート検索が実行される第2のグラフは、図11および図12を参照して以下でより詳細に記載されるように、異なり得る。また、ルートを決定するための方法は、図13および図14を参照して以下でより詳細に説明されるように、3つ以上の異なる段階またはステップ(例えば、3つの段階)を含み得る。
【0089】
図2および図3を参照して、方法70の1つの実装が、図2の道路網20に関連して記載される。例示的な目的のみのために、72における評価関数の値の決定のためのコストモデルと73におけるルート検索のためのコストモデルとは同じものであるということ、72における評価関数の決定と73におけるルート検索との両方は同じグラフ上で(すなわち、道路セグメント41〜55がグラフのエッジに対応する主グラフ(primary graph)上で)実行されるということが、仮定される。
【0090】
評価関数の値を決定するために、目的地22から出発して出発点21に向けて延長するルート検索が実行される。一実施形態において、目的地22から出発するルート検索は、Dijkstraアルゴリズムを用いて実行される。別の実施形態において、目的地22から出発して出発点21に向けて導かれるルート検索は、A*−アルゴリズムを利用して実行される。後者の場合、図2Aにおいて破線34および37によって概略的に示されているように、任意の適切な評価関数(例えば、直線距離ベースの評価関数)が利用され得る。
【0091】
第1の段階において、目的地22から出発するルート検索が実行されるが、道路網41〜55または頂点21〜33を通過すると加算されるコストは、出発点21から目的地22に向けた移動に関連するコストである。例えば、道路セグメント55が頂点33から頂点22までの移動のみが可能な一方通行の道路である場合でさえも(この場合、頂点22から頂点33に向けた道路セグメント55の移動のためのコストは無限である)、頂点33から頂点22までの道路セグメント55の移動を反映する少ない方のコストのみが、目的地22から出発する検索において考慮される。言い換えると、評価関数の値を決定するときには、検索方向のみが逆転され、その一方でルートは、出発点21から目的地22までの移動に課される交通規則を遵守しながら見つけられ、このようにして、目的地22までの有効なルートを表現する。
【0092】
目的地22から出発するルート検索は、このルート検索がDijlstraアルゴリズム、A*−アルゴリズム、または別の適切なアルゴリズムのどれを用いて実行されるかに関わらず、道路網20の頂点を含む検索ツリーをもたらし、これらの頂点の各々に対し、コストは、それぞれの頂点から目的地22までの移動と関連付けられる。目的地22から出発する検索は、出発点21に到達したときに終了するが、その他の実施形態においては、この検索はまた、さらに継続され得る。単なる例示として、検索は、例えば、コストが所定の閾値に到達するまで、またはアルゴリズムにおけるエッジの延長ステップのステップ数が所与の閾値に到達するまで、継続され得る。別の実施形態において、目的地22から出発する検索は、出発点21に到達する前であっても、終了され得る。目的地22から出発するルート検索においては、終了の基準に依存して、道路網20の全ての頂点21〜33が、探索されなければならないわけではないことに留意されたい。対応して、それぞれの頂点から目的地22までの移動に関連するコストは、道路ネットワーク20の頂点21〜33のサブセットに対してのみ決定され得る。図2の例示的な道路網20において、目的地22から出発するルート検索は、図2における黒い四角(full squre)によって概略的に示されているように、頂点33、32、28、27、24、23、21、および25をそれぞれ訪問する。これらの頂点のうちの任意の頂点vに対し、目的地22から出発するルート検索は、第1のステップにおいて利用されるコストモデルに基づいて、頂点vから目的地までのルートに対する正確なコストcosts(v,d)を提供する。これらのコストは、その後73で、出発点21から目的地22までのルート検索において用いられる。
【0093】
図2Bを参照して、73におけるルート検索が、より詳細に説明される。図2Bは、道路網20の概略的表現60であり、ここでは、出発点21および目的地22を結ぶ最適なルート61が示されている。例示的な道路網において、最適なルート61は、道路セグメント41、45、46、52、54、および55、ならびに頂点23、24、28、32、および33をそれぞれ通過する。出発点21から目的地22までのルート検索は、評価関数を利用して、A*−アルゴリズムまたは別の検索アルゴリズムを用いて実行され、ここでは、頂点vへと進む検索ツリーの次の「枝(branch)」は、
【0094】
【化1】
が最小になるように選択され、ここで、
【0095】
【化2】
は、出発点sから頂点vまでのルートに沿って生じるコストを表現しており、
【0096】
【化3】
は、頂点vに対する評価関数の値であり、これは、頂点vから目的地dまでのコストの下限を表現している。72での目的地から出発する検索においてcosts(v,d)が決定された任意の頂点に対し、評価関数の値は、costs(v,d)に等しく設定され得、すなわち、
【0097】
【化4】
である。しかしながら、図9および図10を参照して以下でより詳細に記載されるように、72におけるルート検索において訪問されていない任意の頂点に対しては、必要に応じて、式(3)を満たす別の適切な評価関数の値が用いられ得る。
【0098】
72におけるルート検索に対するコストモデルと73におけるルート検索に対するコストモデルとが同じであると仮定すると、道路網20に基づいて決定された評価関数の値h(v)は、目的地までの残りの経路に対する正確なコストを表現し、ひいては、最も優れた可能な評価関数の値を表現することに留意されたい。したがって、第2のステップ73において実行されるA*−アルゴリズムが、第1のステップ72において見つけられた評価関数の値h(v)=costs(v,d)を利用するとき、検索ツリーは、単一の枝へと崩壊し、この枝は、最適なルート61に沿って(すなわち、出発点21から、頂点23、24、28、32、および33を介して)直接的に目的地22に進む。出発点21から目的地22までの検索ツリーは、例えば図2Bに示されているように、単一の枝のみしか含んでいないので、ステップ73における図3の方法70にしたがう、72において決定された評価関数の値に基づくルート検索は、少ない計算リソース、特に、直線距離ベースの評価関数の値だけを用いるA*−アルゴリズムと比較して、短い計算時間を必要とし得る。
【0099】
方法70の効果は、図4において概略的に示されており、図4は、それぞれ、本発明の実施形態にしたがうルート検索の間に探索される地図の一部分(図4A、図4B)、および従来のルート検索の間に探索される地図の一部分(図4C)を描いている。図4は、道路セグメント(図示されず)を含む地図部分80を示している。出発点81から目的地82までのルートの検索が実行されることが仮定される。図4Aに示されているように、方法70にしたがって、ステップ72において、地図80の領域83は、この領域83の内部に配置された頂点に対する評価関数の値を決定するために、目的地82から出発して出発点81に向けて延長するように検索される。図4Bに示されているように、ステップ73において実行される出発点81から目的地82までの次のルート検索においては、地図80の遥かに小さな領域84のみが、検索される必要がある。なぜならば、ステップ72において既に確立された良い評価関数の値が、ステップ73において利用されるからである。
【0100】
対照的に、従来のA*−アルゴリズムが実行され、出発点81から出発して検索ツリーを延長することによって、出発点81から目的地82までのルートを決定するときには、領域84と比べて通常大きい領域85(図4Cにおいて概略的に示されている)が、検索される必要がある。
【0101】
評価関数の値が第1のステップ72におけるグラフに基づいて決定されるときでさえも、第2のステップ73において探索される検索ツリーは、図2Bの説明例に示されているように、必ずしも常に単一の検索ツリーの枝に崩壊するとは限らない。例えば、図5〜図10を参照して以下でより完全に説明されるように、第2のステップ73において利用されるコストモデルが、例えば回避オプション、交通情報、動的なルーティング等が理由で、第1のステップ72において逆の検索に用いられるコストモデルとは異なる場合、ステップ72において決定されたコストcosts(v,d)(以下では、これらのコストが第1のステップにおいて用いられる第1のコストモデルに基づいて決定されたことを反映するように、costs1(v,d)によって示される)は、一般的には、第2のステップにおいて用いられる新しい第2のコストモデルに基づいて決定される頂点vから目的地dまでのルートの最小のコストとは、同じものではない。以下では、第2のコストモデルに対応する後者のコストは、costs2(v,d)によって示される。次に説明されるように、第1および第2のコストモデルが異なる場合でさえも、第1のステップにおいて決定された評価関数の値は、有利にも、第2のステップにおける評価関数として利用され得る。
【0102】
図5は、別の実施形態にしたがう、ルートを決定するための方法90の流れ図である。この方法は、例えば、ナビゲーションシステム1のプロセッサ2によって実行され得る。方法90では、91において、所望の目的地を指定するユーザ入力が受信される。92においては、複数の頂点に対する評価関数の値が、第1のグラフに基づいて、かつ第1のコストモデルを利用することにより、決定される。92における評価関数の値の決定は、図3を参照して上述された方法のうちの任意の方法で実施され得る。特に、複数の頂点に対する評価関数の値は、目的地から出発して出発点に向けて延長する第1のグラフ上でルート検索を実行することによって、決定され得る。複数の頂点のうちの頂点vに対し、92において決定される評価関数の値は、第1のコストモデルにしたがって、頂点vから目的地dまでのルートに関連するコストであるcosts1(v,d)に等しく設定される。ステップ93においては、92において決定された評価関数の値costs1(v,d)が、その後の使用のためにさらなる格納ユニットに格納される。図1に示されている例示的な実施形態1において、評価関数の値はまた、データ5として格納ユニット3に格納される(すなわち、グラフデータを格納する格納ユニットおよび評価関数の値を格納するさらなる格納ユニットは、一体的に形成される)。しかしながら、評価関数の値が格納されるさらなる格納ユニットは、グラフデータ4を格納する格納ユニット3とは異なることもあり得る。例えば、さらなる格納ユニットは、評価関数の値がその後の使用のために格納されるワーキングメモリ(例えば、RAM)であり得る。
【0103】
94においては、第2のグラフ上で、出発点から目的地までのルートの検索が実行される。図3の方法におけるステップ73と同様に、94におけるルート検索は、A*−アルゴリズムまたは評価関数を利用する別のアルゴリズムを用いて、実行される。しかしながら、ステップ94において利用される第2のコストモデルは、必ずしも第1のコストモデルと同じであるとは限らない。図5の実施形態においては、第1のコストモデルは、この第1のコストモデルが、ステップ94におけるルート検索に利用される第2のコストモデルに関する下限を表現するように、選択されることが仮定され得る。すなわち、第1のグラフの任意の頂点またはエッジに対し、第1のコストモデルにしたがうこの頂点またはエッジに関連するコストは、第2のコストモデルにしたがう第2のグラフの頂点またはエッジに関連するコスト未満であるか、それと等しい。92において決定された評価関数の値は、94におけるルート検索における評価関数の値としての役割を担う。すなわち、検索ツリーの次の枝は、
【0104】
【化5】
が最小になるように選択され、ここで、
【0105】
【化6】
は、出発点sから頂点vまでのルートに沿って生じる第2のコストモデルにしたがうコストを表現しており、頂点vにおける評価関数の値は、
【0106】
【化7】
であり、すなわち、この値は、costs1(v,d)が既に決定されているときには、第1のコストモデルにしたがう、92において決定されたコストである。94において決定されたルートは、例えば、ユーザに出力される。
【0107】
出発点から目的地までのルートを決定した後、95において、第2のグラフの頂点またはエッジのコストの変化をもたらすイベントが発生したかどうかがモニタリングされる。コストの変化をもたらすイベントが95において検出されなかった場合、95におけるモニタリングは、待機状態96の後に繰り返される。95において、第2のコストモデルにしたがう頂点またはエッジのコストが変化したことが決定された場合、97において、コストの変化に適応するために、第2のコストモデルが更新される。上述のように、ステップ92において用いられる第1のコストモデルは、第2のコストモデルが97において更新されるときでさえも、第1のコストモデルが第2のコストモデルにしたがうコストに関する下限を提供するように、選択される。言い換えると、第1のコストモデルは、第1のステップの結果が用いられることが予想される任意の第2のコストモデルに関する下限を表現するように、選択される。98において、格納された評価関数の値が抽出される。方法は次に94に戻り、ここでもまた、更新された第2のコストモデルおよび格納された評価関数の値に基づいて、ルートが決定される。
【0108】
図5の実施形態の方法90にしたがうと、92において決定された評価関数の値が、第2のコストモデルにしたがって決定される頂点vから目的地dまでのルートに関連する実際のコストを低く評価している場合には、92において第1のコストモデルに基づいて決定された評価関数の値は、第2のコストモデルにおけるコストが変化するときでさえも、評価関数の再計算を要求することなしに、94における以後のルート決定のために何回か用いられ得るということに、留意されたい。これは、第1のコストモデルを適切に選択することによって達成される。一実施形態において、第1のコストモデルは、任意の予想される第2のコストモデルに対して選択され得、第1のコストモデルにしたがう頂点またはエッジの通過に関連するコストは、予想される第2のコストモデルにしたがう対応する頂点またはエッジの通過に関連するコスト未満であるか、またはそれと等しい。
【0109】
コストにおける変化は、様々な機構によってもたらされ得、95におけるコストの変化をもたらすイベントのモニタリングおよび第1のコストモデルの適切な選択は、特定の機構に基づいて実施され得る。次に説明されるように、コストの変化に対する可能性のある原因は、回避オプションなどのユーザの選好度、動的なルーティングにおける時刻および/または日付の関数としてのコストにおける変化、出発点から目的地までの代替ルートの計算、または交通情報信号を含む。
【0110】
一実施形態において、95においてモニタリングされるコストの変化は、ユーザの選好度における変化によって、例えば、ユーザによって選択される回避オプションによって、もたらされ得る。そのような回避オプションは、コストペナルティを課す(すなわち、特定の基準を満たす回避されるべき道路セグメントに関連するコストを増加させる)ことによって、ルート決定において考慮され得る。例えば、トンネルまたはフェリー接続が回避されるべき場合には、トンネルまたはフェリー接続を表現するグラフのエッジの全てのコストが増加され得る。そして、評価関数の値を決定するために92において第1のグラフ上のルート検索に利用される第1のコストモデルが、任意のコストの増加または回避オプションによって課されるペナルティを考慮しないコストモデルとして選択され得、例えば、このコストモデルは、最速ルートまたは最短ルートのコストモデルを表現し得る。94におけるルート検索に利用される第2のコストモデルは、基本的に、ユーザによって回避オプションが選択されていない場合には、第1のコストモデルと同じである。95におけるコストの変化をもたらすイベントのモニタリングは、入力ユニット6におけるユーザの選好度を示すユーザ入力をモニタリングすることによって、実施され得る。そして、97において、第2のコストモデルが、選択された回避オプションにしたがってコストを増加させることによって、更新される。上述のように選択された第1のコストモデルにしたがう任意の頂点またはエッジのコストは、第2のコストモデルにしたがう対応する頂点またはエッジのコストに関する下限を表現しているので、92において決定された評価関数の値は、なおも頂点から目的地までのルートに関連するコストを低く評価している。それ故、この評価関数の値は、94においてA*−アルゴリズムが再び実行される場合に、なおも利用される。ここで、
【0111】
【化8】
の値は、ユーザの選好度が理由で変化し得る更新された第2のコストモデルに基づいて決定される。
【0112】
一実施形態においては、代替ルートを決定するために、コストの変化は、プロセッサ2によって内的にもたらされ得る。評価関数の値は、92において、第1のコストモデル(ユーザの回避オプションを考慮するものであったり、または考慮しないものであったりし得る)に基づいて、第1のグラフ上でルート検索を実行することによって決定される。出発点から目的地までの第1のルートは、94において、第2のコストモデル(最初は第1のコストモデルに等しく設定されている)に基づいて決定される。第1のルートが見つけられた後、第1のルートによって通過されるエッジおよび/または頂点に対するコストは、97において増加される。そして、94におけるルート検索が、更新された第2のコストモデル(第1のルートは、好ましくないものとされる)に基づいて、かつ92において第1のコストモデルに基づいて決定された評価関数の値を利用することによって、繰り返される。このようにして、第1のルートの代わりに、出発点から目的地までの第2のルートが見つけられ得る。続いて、ステップ97、98、および94が、繰り返され得る。例えば、第2のルートに沿ったコストもまた増加され得、第1のルートおよび第2のルート等に対する別の代替物である第3のルートが決定され得る。プロセッサ2が、外部のトリガイベントを要求することなしに第2のコストモデルを自動的に更新する場合、モニタリングステップ95および待機ステップ96もまた省略され得、ステップ97、98、および94が、第2のコストモデルが更新されるときはいつでも、自動的に繰り返され得る。
【0113】
一実施形態において、コストの変化は、交通情報信号(例えば、交通渋滞またはその他の悪い交通状況を示す)によって引き起こされ得る。評価関数の値は、92において、第1のコストモデル(これは、ユーザの回避オプションを考慮するものであったり、または考慮しないものであったりし得るが、悪い交通状況によってもたらされるコストの増加を考慮しない)に基づいて、第1のグラフ上でルート検索を実行することによって決定される。このようにして決定された評価関数の値は、93において、格納される。悪い交通状況に関する情報が最初に利用可能でない場合、94におけるルート検索は、第2のコストモデル(最初は第1のコストモデルに等しく設定されている)に基づいて決定され得る。95におけるコストの変化をもたらすイベントのモニタリングは、ナビゲーションシステム1のプロセッサ2が、交通メッセージ受信器9(例えば、TMC受信器として構成され得る)によって受信された交通情報信号を評価することによって、もたらされ得る。プロセッサ2が、受信した交通情報信号が94において既に決定されたルートによって通過される頂点またはエッジのコストに影響を与え得るということを決定すると、このプロセッサ2は、97において、受信した交通情報信号に基づいて、それぞれの頂点またはエッジのコストを増加させることによって、第2のコストモデルを更新する。別の実施形態において、第2のコストモデルの更新は、グラフの任意の頂点またはエッジに関連する交通状況信号が受信されたときに、実行され得る。そしてルートは、g(v)を決定するための更新された第2のコストモデルに基づいて、かつ92において決定された評価関数h(v)に基づいて、再び決定される。第1のコストモデルのコストは、第2のコストモデルのコストの下限を表現しているので、第2のコストモデルのコストはなおも、有効な評価関数を提供する。ステップ97、98、および94は、さらなる交通情報信号が受信されるときはいつでも、繰り返され得る。
【0114】
一実施形態において、コストの変化は、時刻または日付の関数としての、コストの所定の時間変化によってもたらされ得る。そのような時間変化するコストは、例えば、時刻および/または日付の関数として交通状況の変化が考慮される動的なルート検索において利用される。そして、92において、評価関数の値を決定する際に利用される第1のコストモデルは、任意の頂点またはエッジに対し、第1のコストモデルが、任意の時刻および/または日付において、この頂点またはエッジに関連する最小のコストに対応するように、選択される。そして、94におけるルート決定において、第2のコストモデルが、クロックユニット10によって時間変化するコストを反映するように決定された時刻および/または日付に応じて、選択され得る。言い換えると、頂点またはエッジのコストに対する時間変化する寄与は、94におけるルート決定においてのみ考慮され、92における評価関数の値の決定に対しては考慮されない。第1のコストモデルのコストは、第2のコストモデルのコストに関する下限を表現しているので、第2のコストモデルはなおも、有効な評価関数を提供し、94におけるルート検索に利用され得る。コストに対する時間変化する寄与が(例えば、ルートの通過の間になされる一時停止が原因で)変化する場合、97において、時間変化するコストを考慮する第2のコストモデルが更新され得、94において、ルートが再び決定され得る。
【0115】
ユーザの選好度、代替ルートの決定、交通情報信号、および動的なルート決定は、コストモデルが変化し得る例示的なシナリオを表現し得るが、図5の実施形態はこれらのシナリオに限定されないということに、留意されたい。
【0116】
図7を参照すると、この図は、図2の例示的な道路網20を示しており、図5の実施形態にしたがう方法90が説明される。上述で図2を参照して説明されたように、第1および第2のグラフは、同じものであって、グラフのエッジが道路網20の道路セグメントを表現している主グラフを表現していることが仮定されている。92において、評価関数の値が、図7における黒い四角によって示されている頂点21、23、25、24、27、28、32、および33に対して決定されることが仮定される。最初に、出発点21から目的地22までの最適なルート61が、道路セグメント41、45、46、52、54、および55を通過することが決定される。例えばユーザの選好度、代替ルートの決定、交通情報信号、および動的なルート決定が理由で、道路セグメント45に対するコストが増加すると、94におけるルート検索はなおも、頂点21、23、25、24、27、28、32、および33に対して最初に決定された評価関数の値h(v)=costs1(v,d)を用いて実行され得るが、道路セグメント45に対して増加されたコストを有する更新された第2のコストモデルを利用することによって、g(v)=costs2(s,d)を決定する。図7において概略的に示されているように、道路セグメント45に対して増加されたコストが理由で、新しい最適なルート121は、道路セグメント41、44、51、54、および55を通過する。第1のステップにおいて、グラフ20に基づいて評価関数の値h(v)=costs1(v,d)が決定されるので、これらの評価関数の値は、頂点vから目的地dまでのコストの下からの評価(第2のコストモデルにしたがう実際のコストに近いものであり得る)を提供し、これによって、ルートを見つけるために検索されなければならないグラフ20の部分のサイズを減らす。第1および第2のコストモデルが異なるとき、94におけるルート検索はまた、92において評価関数の値が決定されていないさらなる頂点に対して(例えば、図7における頂点26に対して)評価関数の値が決定されることを要求し得るが、要求される追加的な評価関数の値は、図9および図10を参照して以下でより詳細に説明されるように、容易に確立され得る。
【0117】
次に、図6を参照して、本発明の別の例示的な実施形態にしたがう方法100が記載される。方法100にしたがい、第1のグラフに基づいて決定された評価関数の値が、出発点から目的地までのルートを決定するために、また、ルートの逸脱(deviation)が検出されたときには、別の出発点から(例えば、現在の車両の位置から)目的地までのルートを決定するために利用される。
【0118】
方法100では、101において、所望の目的地を指定するユーザ入力が受信される。102においては、複数の頂点に対する評価関数の値が、第1のグラフに基づいて、かつ第1のコストモデルを利用することにより、決定される。102における評価関数の値の決定は、図2および図3を参照して上述された方法のうちの任意の方法でもたらされ得る。特に、複数の頂点に対する評価関数の値は、目的地から出発して出発点に向けて延長する第1のグラフ上でのルート検索を実行することによって、決定され得る。複数の頂点のうちの頂点vに対し、102において決定される評価関数の値は、第1のコストモデルにおける頂点vから目的地dまでのルートに関連するコストであるcosts1(v,d)に等しく設定される。ステップ103においては、102において決定された評価関数の値costs1(v,d)は、その後の使用のためにさらなる格納ユニットに格納される。104においては、第2のグラフ上で、かつ第2のコストモデルに基づいて、出発点から目的地までのルートの検索が実行される。第2のコストモデルは、第1のコストモデルと同じものであったり、または異なるものであったりし得る。しかしながら、一実施形態においては、102において利用される第1のコストモデルは、第1のグラフの任意の頂点またはエッジに対し、第1のコストモデルにしたがうコストが、第2のコストモデルにしたがう第2のグラフの対応する頂点またはエッジに関する下限を表現するように、選択される。図3の方法におけるステップ73と同様に、104におけるルート検索は、A*−アルゴリズムまたは別のアルゴリズム(評価関数として、102において決定された評価関数の値を利用する)を用いて実行される。
【0119】
105において、現在の車両の位置が決定される。現在の車両の位置は、ナビゲーションシステム1において、GPS受信器8によって出力された信号に基づいて決定され得る。100において、車両がルートを逸れたかどうかを決定するために、現在の車両の位置が、ルートに沿った位置と比較される。106において、最初のルートからの逸脱が決定されなかった場合には、105における現在の位置の決定が、107における所定の待機期間の後に繰り返される。
【0120】
しかしながら、106において最初のルートからの逸脱が検出された場合には、108において、現在の車両の位置または現在の車両の位置に近い別の位置が、新しい出発点として選択される。109において、格納された評価関数の値が抽出される。110において、新しい出発点から目的地までのルートの検索が、第2のグラフ上で、かつ第2のコストモデルに基づいて、実行される。ルート検索110において、102において決定された評価関数の値は、ここでもまた、(例えば、A*−アルゴリズムにおいて)評価関数として利用される。そして方法は、105におけるアクティブなルートに対する現在の車両の位置のモニタリングに戻る。102において第1のコストモデルを適切に選択することによって、第1および第2のコストモデルが異なる場合でさえも、102において決定された評価関数の値はなおも、110におけるルート検索に有効な評価関数を表現するということに留意されたい。さらに、以下でより詳細に記載されるように、102において評価関数の値が決定される第1のグラフ、および104および110においてルート検索が実行される第2のグラフは、同じものであったり、または異なるものであったりし得るということに留意されたい。
【0121】
図5および図6の方法は、組み合わされ得るということに留意されたい。例えば、一実施形態において、第1のグラフに基づいて評価関数の値が決定される第1のステップの結果は、例えば代替ルートの検索において、1つの出発点から目的地までのいくつかの異なるルートを決定するためと、例えば最初のルートからの逸脱が検出されたときに、異なる出発点から目的地までの異なるルートを決定するためとの両方に、利用され得る。
【0122】
図7を参照して、図6の実施形態の方法100が、道路網20に関連して例示的に説明される。ルート61の道路セグメント41を通過した後、ユーザは頂点23において道路セグメント45ではなく道路セグメント44に曲がると仮定し、最初のルート61からの逸脱が検出されると仮定する。これに応答して、第1のステップにおいて既に決定された評価関数の値を利用することにより、道路セグメント44上の現在の車両の位置または到達されるべき次の頂点27から目的地22までの新しいルートが決定される。
【0123】
図6の方法100をさらに説明するために、図8に対する参照がなされる。この図は、道路網(図示されず)を含む地図130を示しており、図6の方法100の様々なステップにおいて訪問される地図130の一部分を概略的に表現している。例示を目的として、102において評価関数の値を決定する際に利用されるコストモデル、ならびに104および110においてルート検索の際に利用されるコストモデルは、同じものであったり、または僅かに異なるものであったりし得るということに留意されたい。ルート検索の出発点は131に示されており、目的地は132に示されている。図8Aは、目的地132から出発して出発点131に向かって延長するルート検索を実行することによって評価関数の値が決定されるときに、ステップ102において訪問される領域133を概略的に示している。102におけるルート検索において、評価関数の値は、領域133に配置される頂点に対して決定される。図8Bにおいて、領域134は、104において出発点131から目的地132までのルート検索において探索される地図130の一部分を概略的に示している。図4Bを参照して上述されたように、グラフに基づいて決定される評価関数の値は、正確な最小のコストに対する良い近似を表現し得るので、領域134は小さな領域であり得る。車両が最初に決定されたルートを逸脱し、例えば位置135に位置するときには、位置135から目的地132までのさらなるルート検索がトリガされる。領域136は、このさらなるルート検索において探索される地図130の一部分を概略的に示している。さらなるルート検索もまた、グラフに基づいて決定された評価関数の値を利用するので、探索されなければならない領域136もまた、小さな領域であり得る。単に例示を目的として、102において評価関数の値を決定する際に利用されるコストモデル、および104および110におけるルート検索に利用されるコストモデルは、同じものであると仮定すると、102および104における検索での検索ツリーは、1つの枝に崩壊し得る。
【0124】
図1〜図8を参照して上述されたように、2つのステップまたは段階においてルート検索が実行されるとき、第2のステップまたは段階において実行される出発点から目的地までのルート検索は、第1のステップまたは段階において評価関数の値が決定されなかった頂点に対する評価関数の値を必要とし得る。この状況は例えば、第1のステップおよび第2のステップにおいて利用される第1のコストモデルおよび第2のコストモデルのそれぞれが異なるとき、または車両が最初のルートから逸脱しているときに、第1のステップ利用される終了の基準が理由で、第1のステップにおいて、全ての頂点のうちの僅かな部分に対してのみ、評価関数の値が決定されたときに生じ得る。次に説明されるように、追加的な頂点に対する評価関数の値は、必要に応じて、ルート決定の第2のステップの間に容易に決定され得る。
【0125】
図9は、第2のステップ(図3の方法70における73、図5の方法90における94、図6の方法100における104および110)における出発点から目的地までのルート検索に利用され得る方法140の流れ図である。限定ではなく例示のために、出発点から目的地までのルート検索は、A*−アルゴリズムを用いて実行される。
【0126】
141において、延長ステップは、検索ツリーの「逸脱(leave)」から(すなわち、出発点から延びる検索ツリーにおける最後の頂点のうちの1つから)実行される。142において、延長ステップが実行される新しい頂点に対して、評価関数の値が既にルート検索の第1のステップにおいて決定されているかどうかが、決定される。評価関数の値が既に決定されている場合、143において、第1のステップにおいて決定された新しい頂点に対する格納された評価関数の値costs1(v,d)が、新しい頂点に対する評価関数h(v)として用いられる。評価関数の値が決定されていない場合には、144において決定される。
【0127】
144における新しい頂点に対する評価関数の値の決定は、様々な方法で実行される。一実施形態において、新しい頂点に対する評価関数の値は、第1のステップ(すなわち、図3における72)に戻り、かつ新しい頂点に対しても評価関数の値が求まるまで第1のステップを継続することによって、決定される。例えば、第1のステップが目的地から出発して出発点まで延長するルート検索を含む場合、このルート検索は、新しい頂点に到達されるまで継続され得る。
【0128】
図10を参照すると、この図は、図2の道路網20を示しており、新しい頂点に対して評価関数を決定するための方法が例示的に説明される。道路セグメント41のコストは、(例えば、回避オプションが理由で)増加されており、出発点21から目的地22までの最適なルートはもはや、道路セグメント41を通過しないことが仮定される。出発点21から頂点25までの第1の延長ステップの後、それ続いて、白い四角(open squre)によって示されている頂点29(この頂点に対しては、第1のステップにおいて、評価関数の値が決定されていない)まで延長する。しかしながら、頂点28から目的地22までのルートに対するcosts1(頂点28,d)、頂点25から目的地22までのルートに対するcosts1(頂点25,d)の両方が、第1のステップにおいて決定されているので、頂点29に対する評価関数の値は、頂点25および28から頂点29までの検索を延長し、かつcosts1(頂点28,d)と頂点29から頂点28までのルートに関連するコストとの和、そしてcosts1(頂点25,d)と頂点29から頂点25までのルートに関連するコストとの和のうちの小さいほうを決定することによって、決定され得る。
【0129】
別の実施形態において、144における新しい頂点に対する評価関数の値は、第1のステップのルート検索を継続することを要求することなしに、第1のステップにおいて決定された情報に基づいて、決定され得る。限定ではなく例示のために、新しい頂点に対する評価関数の値は、第1のステップにおいて決定された評価関数の最大値、および第1のステップにおける、目的地から出発して出発点まで延長するルート検索において利用される評価関数に基づいて決定され得る。すなわち、
【0130】
【化9】
が第1のステップにおいて決定された任意の頂点vに対する最大のコストを示し、かつh1(v)(出発点sから頂点vまでのルートに関連するコストに関する下限を表現する)がルート検索の第1のステップにおいて利用される評価関数を示す場合、ルート検索の第2のステップにおいて利用される任意の頂点vに対する評価関数の値h(v)は、
【0131】
【化10】
に等しく設定され得る。図2Aを参照して上述されたように、第1のステップにおいて利用される評価関数h1(v)は、直線距離ベース(例えば、最短ルートのコストモデルに対する直線距離、または直線距離を最速ルートのコストモデルにおける固有の移動速度で割ったもの)であり得る。
【0132】
新しい頂点に対する評価関数を決定するための本方法をさらに説明するために、再び図10を参照すると、ここでもまた、出発点21から目的地22までの検索は、第1のステップにおいて評価関数の値が決定されていない頂点29まで延長することが仮定される。しかしながら、max1=costs(頂点25,d)が、第1のステップにおいて決定されている。さらに、第1のステップにおいて、直線(air−line)ベースの評価関数h1が利用されると仮定すると、153に概略的に示されているように、h1(頂点29)は、頂点29と出発点21との間の直線距離から容易に決定され得る。max1およびh1(頂点29)から、h(頂点29)が式(9b)にしたがって決定され得る。
【0133】
別の実施形態において、新しい頂点に対する評価関数の値は、新しい頂点から目的地までの直線距離に基づいて決定され得る。
【0134】
新しい頂点に対する評価関数を決定するための本方法をさらに説明するために、再び図10を参照すると、頂点29に対する評価関数の値は、152に概略的に示されている頂点29と目的地22との間の直線距離に基づいて決定され得る。
【0135】
図1〜図10を参照して上述された例示的な実施形態において、評価関数の値が決定される第1のグラフ、および出発点から目的地までのルート検索が実行される第2のグラフは同じであると仮定されているが、次に説明されるように、第1および第2のグラフはまた、その他の実施形態においては異なるものであり得る。
【0136】
図11は、本発明の一実施形態にしたがう、方法160の流れ図である。方法160では、161において、所望の目的地を指定するユーザ入力が受信される。162において、第1のグラフの複数の頂点および/またはエッジに対する評価関数の値が、第1のグラフに基づいて決定される。162における評価関数の値の決定は、図2および図3を参照して上述された方法のうちの任意の方法でもたらされ得る。特に、評価関数の値は、目的地から出発して出発点に向けて延長する第1のグラフ上でルート検索を実行することによって決定され得る。第1のグラフの頂点に対し、162において決定される評価関数の値は、第1のグラフ上の評価関数の頂点から目的地までのルートに関連するコストに等しく設定され得る。加えてまたはあるいは、評価関数の値はまた、第1のグラフのエッジ上の特徴点に対して決定され得る。163においては、第1のグラフの要素(すなわち、頂点またはエッジ)に対して決定される評価関数の値が、第2のグラフの対応する要素に対する評価関数の値にマッピングされる。164においては、162において確立された評価関数の値を利用することにより、ルート検索が第2のグラフ上で実行され、163における第2のグラフにマッピングされる。
【0137】
例えば、図11の方法160は、図12に関連してさらに示される。図12は、第1のグラフを表現している図2の道路網20を示しており、これに基づいて、評価関数の値が決定される。すなわち、第1のグラフのエッジは、道路セグメントを表現しており、第1のグラフの頂点は、道路セグメントの端点を表現している。図12においては、第1のグラフの頂点は、中実の四角(solid squre)で示されており、第1のグラフのエッジは、実線で示されている。第2のグラフ20’は、道路網の双対グラフである。すなわち、第2のグラフ20’の頂点171〜178は、道路網の道路セグメントを表現している。例えば、頂点171は道路セグメント41を表現しており、頂点172は道路セグメント42を表現している、等。第2のグラフ20’のエッジ181〜185は、道路セグメントの端点を表現しており、これらは、1つの道路セグメントから別の道路セグメントへの移行を可能にしている。たとえば、頂点171および172を結ぶエッジ181は、出発点21において、道路セグメント41と道路セグメント42との間の移行が可能であることを示している。同様に、頂点174および175を結ぶエッジが存在しないという事実は、接合部23における道路セグメント45と道路セグメント44との間の移行が可能ではないということを示している。したがって、双対グラフにおいて、ターン制限は容易に考慮され得る。なぜならば、ターン制限は、双対グラフのエッジによる双対グラフの頂点の相互接続によって反映されるからである。図12においては、第2のグラフの頂点は、空白の四角(open squre)によって示されており、第2のグラフのエッジは、破線によって示されている。
【0138】
図12に見られるように、第1のグラフ20および第2のグラフ20’は、互いに異なるものであり得る(すなわち、一方は他方の双対グラフであり得る)。そして、評価関数の値が決定されるルート検索の第1のステップは、(例えば、目的地22から出発して出発点21に向けて延長する第1のグラフ20上でルート検索を実行することによって)第1のグラフ20上で実行され得る。これによって、結果として得られる検索ツリーの任意の枝における第1のグラフ20の任意の頂点に対し、第1のグラフ上の頂点から目的地22までのルートに関連するコストが決定される。そして、第2のステップ(すなわち、出発点21から目的地22までのルート検索)が、第1のステップにおけるルート検索において決定されたコストに基づくようにするために、第1のステップにおいて探索された全ての頂点に対して第1のステップにおいて決定されたコストは、第2のグラフ20’の対応するセグメントにマッピングされる。例えば、図12においては、第2のグラフ20’の頂点171〜178は、第1のグラフ20のエッジの中点に配置されて示されているが、第2のグラフ20’の頂点171〜178のうちの任意の頂点に対し、評価関数の値は、第2のグラフ20’のそれぞれの頂点によって表現されている道路セグメントの端点に対するコストに基づいて決定され得る。例えば、頂点21から目的地22までのルート、および頂点23から目的地22までのルートに対するコストが、第1のステップにおいて決定されたと仮定すると、第2のグラフ20’の頂点171に対する評価関数の値は、costs1(頂点23,d)と頂点23から頂点21までの道路セグメント41の通過に関連するコストとの和、およびcosts1(頂点21,d)と頂点21から頂点23までの道路セグメント41の通過に関連するコストの半分との和のうちの最小値に等しく決定され得る。ここで、costs1は、第1のステップにおいて第1のグラフに基づいて決定されたコストを表現している。第1のグラフ20の要素(すなわち、頂点および/またはエッジ)から第2のグラフ20’の対応する要素への評価関数のマッピングの後、第2のグラフ20’でのルート検索が、図1〜図10の上述の実施形態のうちの任意の実施形態に対して記載されたように実行され得る。
【0139】
第1のステップおよび第2のステップにおいて利用されるコストモデルは同じものであり得るが、第1のグラフおよび第2のグラフが異なるときには、互いに異なり得ることに留意されたい。特に、第1のグラフに基づいて評価関数の値を決定するために利用される第1のコストモデルは、ユーザの選好度によって生じる追加的なコスト、交通情報信号、時間変化するコストの寄与、等とは無関係であり得るが、これらは、第2のコストモデルにおいて考慮され得る。
【0140】
図12における第1および第2のグラフの概略図は、単に例示的なものであり、限定的な意味で解釈されるべきではないことに留意されたい。特に、第1および第2のグラフは、一方通行制限、反対の移動方向における異なる移動速度、移動方向に関係するターン制限、等を考慮するために、より複雑な方法で定義され得る。例えば、道路セグメントの各移動方向は、一方通行ではない通りの道路セグメントが、第1のグラフの2つのエッジおよび第2のグラフの2つの頂点のそれぞれによって表現され得るように、第1のグラフにおけるエッジによって、および第2のグラフにおける頂点によって表現され得る。
【0141】
図11に戻ると、161および164において利用される第1および第2のグラフは互いに異なるものであり得るので、第1のグラフは、第1のグラフ上のルート検索が、平均で第2のグラフ上のルート検索よりも速くなるように、選択され得る。例えば、第1のグラフは、これが第2のグラフよりも少ない頂点を有するように選択され得る。
【0142】
一実施形態において、第1のステップ(すなわち、評価関数の値を決定すること)は、道路セグメントの到達される方向に関する情報を無視し、1つの道路セグメントから別の道路セグメントへのターンに関連するコストを無視することによって、道路セグメントの中点の間のルート検索を実行することにより、実施され得る。言い換えると、第1のステップは、グラフによって表現される道路網においてターン制限が無視されるグラフ上で実行され得る。一方通行制限は依然として、考慮され得る。別の実施形態においては、一方通行制限はまた、無視され得る。そして、第2のステップは、図11および図12を参照して上述されたように、エッジが道路セグメントを表現する主グラフ上、または頂点が道路セグメントを表現する双対グラフ上のいずれかの上で、実行され得る。
【0143】
別の実施形態においては、第1のグラフ(第1のステップにおいて、この第1のグラフに基づいて評価関数が決定される)が主グラフであり得るが、第2のステップにおけるルート検索は、第2グラフ上で実行される。第1のステップにおいて、ターン制限は無視され得る。
【0144】
本発明の様々な実施形態にしたがう方法は、図1〜図12を参照して2つのステップのプロセスとして上述されてきたが、この方法はまた、2つ以上のステップを含み得る。上述の1つまたはいくつかのステップの結果は、その後のステップにおいて利用され得る。
【0145】
例えば、評価関数の値が決定される第1のステップは、いくつかのサブステップを含み得る。すなわち、第1のグラフの複数の頂点に対する評価関数の値の決定は、1つの段階の結果が別の段階において利用される複数の段階のプロセスであり得る。
【0146】
図13は、本発明の別の実施形態にしたがう方法190の流れ図であり、この方法にしたがって、評価関数の値の決定が、複数の段階のプロセスにおいて実行される。191において、目的地がユーザ入力によって指定される。192および193において、評価関数の値が、まず192において第3のグラフ上でルート検索を実行し、193においてこのルート検索の結果を第1のグラフ上のルート検索に利用することによって、決定される。第1のグラフ上でのルート検索の結果、複数の頂点に対する評価関数の値が得られる。194において、評価関数の値は、出発点から目的地までのルート検索において利用される。
【0147】
一実施形態においては、第3のグラフは、192および193における2段階のプロセスが、複数の頂点に対して評価関数の値をより容易に決定することを可能にするように、定義される。一実施形態では、193において、ルート検索は、目的地から出発して出発地に向かってA*−アルゴリズムを用いることによって実行される。192におけるルート検索は、第3のグラフ上で実行され、192において実行されたA*−アルゴリズムに対し、より正確な評価関数を提供する。
【0148】
2段階のプロセス192、193の例示的な実装が、図2の道路網20を示す図14Aおよび図14Bを参照して示される。例示的な実装において、第3のグラフ20”は、例えば欧州特許出願第06 012 160.5号に記載されているように、タイリング(tiling)に基づいて、かつタイリングのタイルに関する所定の情報(例えば、タイルの抵抗(resistance)を定量化する抵抗値)を利用して、定義される。
【0149】
図14Aに見られるように、タイリング201は、道路網20が含まれる領域をカバーし、複数のタイル202〜205を含むように定義される。タイリング201の任意のタイルに対し、グラフの幾何学的配置に関連して、タイルを通過するルートに関連するコストを定量化する所定の抵抗値が提供される。例えば、タイリングのタイル202〜205に対する抵抗値は、
【0150】
【化11】
に等しく定義され得、viおよびvjは、それぞれのタイルの境界上に配置される頂点を示しており、costs(vi,vj)は、グラフ上のviからvjまでのルートに関連する最小のコストを示しており、distance(vi,vj)は、viとvjとの間の直線距離を示している。
【0151】
図14Aおよび図14Bに示されているように、タイル202〜205に対する局所的な抵抗値に基づいて、単純化された第3のグラフ20”が定義され得、このグラフは、出発点21および目的地22を含むタイル以外のその他の全てのタイルにおいて、タイルの境界上に配置された頂点のみを含む。言い換えると、出発点21も目的地22も含まない任意のタイルに対しては、道路網20の頂点28および30に対する場合のように、タイル内に配置された頂点は省略される。タイル内部における頂点が省略されているタイルにおいては(例えば、図14におけるタイル205においては)、タイルの境界上に配置された頂点24、27、29、32を結ぶ新しいグラフのエッジ211〜214が定義され、これらのエッジはタイルの頂点の幾何学的配置およびタイルの抵抗値に基づくコストに関連する。より具体的には、頂点viおよびvjを結ぶ第3のグラフの新しく導入されるエッジに対するコストは、
【0152】
【化12】
に等しく設定され得る。例えば、エッジ214に対するコストは、タイル205の抵抗Rと、頂点29と頂点32との直線距離との積に等しく設定され得る。式(10)における抵抗値の定義から、第3のグラフの新しいエッジに対するコストは、実際のコストの下限を表現する。
【0153】
そして、図13の192において、上記で概説されたように構成される第3のグラフ20”に基づいて、直線距離ベースの評価関数を利用するDijkstraアルゴリズムまたはA*−アルゴリズムが、出発点21から出発して目的地22に向かって延長するように実行される。第3のグラフ20”の構成が理由で、第3のグラフ20”の出発点から任意の頂点までのルートに対するコストは、第1のグラフ20の出発点21から対応する頂点までのルートに関連するコストの下限を表現するので、193において第1のグラフ20上でA*−アルゴリズムが利用されるときに、評価関数の値として利用され得る。第1のグラフ20に含まれるが第3のグラフ20”には含まれない任意の頂点に対し(すなわち、内部に配置された頂点に対し)、193において利用される評価関数の値は、それぞれのタイルの境界に配置された頂点に対する評価関数の値から決定され得る。例えば、頂点28に対する評価関数の値は、頂点27、28、29、または32のうちの任意の頂点に対して決定されるコストの最小値に等しく設定され得る。上述の実施形態のうちの任意の実施形態に関連して記載されているように、第1のグラフ20の複数の頂点に対する評価関数の値の決定の後、方法は、第2のグラフ上の出発点から目的地までのルート検索へと進む。
【0154】
評価関数の値の決定が2段階のプロセスとして実装される場合のみが、図13および図14を参照して上述されてきたが、その他の実施形態においては、出発点からも目的地までの(すなわち、第2のステップの)ルート検索はまた、複数の段階のプロセスとしても実装され得る。さらに、本発明の様々な実施形態にしたがう方法は、2段階または3段階のプロセスに限定されず、任意の適切な複数のステップまたは段階、先のステップまたは段階から得られた結果を利用するその後のステップまたは段階を含み得る。
【0155】
概説すると、本発明にしたがって、ルートを決定するための方法およびデバイスが提供され、ルートは複数のステップのプロセスで決定される。好適または有利な実施形態の上記の記載から明らかなように、本発明の実施形態にしたがうと、第1のステップにおいて正確な評価関数が決定され得、これは、第2のステップにおいてルート検索の複雑さを低減させるために利用され得る。第1のステップにおいて決定される評価関数の値は、いくつかのルート検索に対して利用され得る。
【0156】
本発明は、有利にも任意の最適なルート検索に利用され得、特に、道路網上でルートを決定することに利用され得るが、道路網上でのルート決定には限定されない。
【図面の簡単な説明】
【0157】
【図1】図1は、本発明の一実施形態にしたがう、ルートを決定するためのデバイスを含むナビゲーションシステムの概略ブロック図を示している。
【図2A】図2Aおよび図2Bは、例示的な道路網を概略的に示している。
【図2B】図2Aおよび図2Bは、例示的な道路網を概略的に示している。
【図3】図3は、一実施形態にしたがう、ルートを決定するための方法の流れ図である。
【図4A】図4は、ルート検索において探索される地図の一部分を示しており、図4Aおよび図4Bは、本発明の一実施形態にしたがう、ルート検索の第1および第2のステップを表現しており、図4Cは、従来のルート検索を表現している。
【図4B】図4は、ルート検索において探索される地図の一部分を示しており、図4Aおよび図4Bは、本発明の一実施形態にしたがう、ルート検索の第1および第2のステップを表現しており、図4Cは、従来のルート検索を表現している。
【図4C】図4は、ルート検索において探索される地図の一部分を示しており、図4Aおよび図4Bは、本発明の一実施形態にしたがう、ルート検索の第1および第2のステップを表現しており、図4Cは、従来のルート検索を表現している。
【図5】図5は、別の実施形態にしたがう、ルートを決定するためお方法の流れ図である。
【図6】図6は、別の実施形態にしたがう、ルートを決定するための方法の流れ図である。
【図7】図7は、図2の例示的な道路網に対する図5および図6の方法にしたがう、ルート検索を概略的に示している。
【図8A】図8は、図6の方法にしたがう、ルート検索において探索される地図の一部分を示している。
【図8B】図8は、図6の方法にしたがう、ルート検索において探索される地図の一部分を示している。
【図9】図9は、ルート決定において、格納された評価関数の値を利用するためのステップを表現する流れ図である。
【図10】図10は、図2の例示的な道路網に対する図9のステップを概略的に示している。
【図11】図11は、別の実施形態にしたがう、ルートを決定するための方法の流れ図である。
【図12】図12は、図2の例示的な道路網を表現する第1のグラフおよび第2のグラフを概略的に示している。
【図13】図13は、別の実施形態にしたがう、ルートを決定するための方法の流れ図である。
【図14A】図14Aは、図2の例示的な道路網に対する図13の方法にしたがうルート検索を示しており、図14Bは、ルート検索において利用される第3のグラフを表現している。
【図14B】図14Aは、図2の例示的な道路網に対する図13の方法にしたがうルート検索を示しており、図14Bは、ルート検索において利用される第3のグラフを表現している。
【符号の説明】
【0158】
2 プロセッサ
3 格納ユニット
4 グラフデータ
5 データ
6 入力ユニット
7 出力ユニット
8 位置決定手段
9 交通メッセージ受信器
10 クロックユニット
20 第1のグラフ
20,20’ 第2のグラフ
22、82、132 目的地
21、81、131 出発点
61 ルート
【特許請求の範囲】
【請求項1】
目的地、特に道路網上の目的地(22;82;132)までのルートを決定するための方法であって、
第1のステップにおいて、第1のグラフ(20)に基づいて、複数の頂点(23、24、25、27、28、32、33)に対する評価関数の値を決定することであって、頂点(21〜33)に対する評価関数の値は、該頂点(21〜33)から該目的地(22;82;132)までのルートに関連するコストの下限を表現している、ことと、
第2のステップにおいて、該第1のステップにおいて決定された該評価関数の値に基づいて、第2のグラフ(20;20’)上で、出発点(21;81;131)から該目的地(22;82;132)までのルート(61)を検索することと
を包含する、方法。
【請求項2】
前記第1のステップにおいて、頂点(21〜33)に対する評価関数の値を決定することは、前記第1のグラフ(20)上で該頂点(21〜33)から前記目的地(22;82;132)までのルートを検索することを含む、請求項1に記載の方法。
【請求項3】
前記頂点(21〜33)から前記目的地(22)までの前記ルートを検索することは、前記第1のグラフ(20)上でDijkstraアルゴリズムまたはA*−アルゴリズムを用いて実行される、請求項2に記載の方法。
【請求項4】
前記第1のステップにおいて頂点(21〜33)に対する評価関数の値を決定することは、前記第1のグラフ上で、前記目的地(22;82;132)から出発して前記出発点(21;81;131)まで延長するルート検索を実行することを含む、請求項1〜請求項3のいずれか一項に記載の方法。
【請求項5】
前記第2のステップにおいて、前記評価関数の値に基づいて、前記目的地(22;82;132)までのルート(61)とは異なる少なくとも1つのさらなるルート(121;151)を検索すること
を含む、請求項1〜請求項4のいずれか一項に記載の方法。
【請求項6】
前記少なくとも1つのさらなるルート(121;151)は、前記出発点(21)から前記目的地(22)までの代替ルート(121;151)、または別の出発点(135)から前記目的地(132)までのルートのうちの少なくとも1つを含む、請求項5に記載の方法。
【請求項7】
前記出発点(21;131)から前記目的地(22;132)までの前記ルート(61)に対する現在の位置(135)をモニタリングすることであって、前記少なくとも1つのさらなるルートの前記検索は、該現在の位置(135)の該モニタリングの結果に基づいて自動的に開始される、こと
を含む、請求項5または請求項6に記載の方法。
【請求項8】
前記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜45;181〜185)に関連するコストの変化をモニタリングすることであって、前記少なくとも1つのさらなるルート(121;151)の前記検索は、該変化をモニタリングした結果に基づいて自動的に開始される、こと
を含む、請求項5〜請求項7のいずれか一項に記載の方法。
【請求項9】
前記第1のステップにおいて決定された前記評価関数の値の少なくともサブセット(5)を格納することと、
前記第2のステップにおいて該サブセット(5)の少なくとも1つの評価関数の値を抽出することと
を含む、請求項1〜請求項8のいずれか一項に記載の方法。
【請求項10】
前記第1のステップにおける前記評価関数の値の前記決定は、第1のコストモデルに基づいており、前記第2のステップにおける前記出発点(21;81;131)から前記目的地(22;82;132)までの前記ルート(61)の検索は、第2のコストモデルに基づいている、請求項1〜請求項9のいずれか一項に記載の方法。
【請求項11】
前記第1のコストモデルにしたがう、前記第1のグラフ(20)の前記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、時間に関係しない、請求項10に記載の方法。
【請求項12】
前記第2のコストモデルにしたがう、前記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストは可変である、請求項10または請求項11に記載の方法。
【請求項13】
ユーザの選好度、交通情報信号、時刻または日付のうちの少なくとも1つに基づいて、前記第2のコストモデルにしたがう前記コストを調整すること
を含む、請求項12に記載の方法。
【請求項14】
前記調整することは、少なくとも1つの頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に対し、前記第1のコストモデルに対して
前記第2のコストモデルにしたがうコストを増加させることを含む、請求項13に記載の方法。
【請求項15】
前記第1のコストモデルにしたがう前記第1のグラフ(20)の頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、前記第2のコストモデルにしたがう対応する頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストの下限を表現する、請求項12〜請求項14のいずれか一項に記載の方法。
【請求項16】
前記第1のグラフ(20)は、該第1のグラフ(20)上のルート検索が、平均で、該第2のグラフ(20’)上のルート検索よりも速くなるように定義される、請求項1〜請求項15のいずれか一項に記載の方法。
【請求項17】
前記第1のグラフ(20)は、前記第2のグラフ(20’)よりも少ない頂点(21〜33)を有している、請求項1〜請求項16のいずれか一項に記載の方法。
【請求項18】
前記第1のグラフの頂点は、前記道路網の道路セグメントを表現しており、前記第1のステップにおいて、該道路網上のターン制限は無視される、請求項1〜請求項17のいずれか一項に記載の方法。
【請求項19】
前記第1のステップにおいて、一方通行制限が考慮される、請求項18に記載の方法。
【請求項20】
前記第1のグラフ(20)のエッジ(41〜55)は、道路網の道路セグメントを表現しており、前記第2のグラフ(20’)の頂点(171〜178)は、該道路網の道路セグメントを表現している、請求項1〜請求項17のいずれか一項に記載の方法。
【請求項21】
前記第1のグラフ(20)は、前記第2のグラフ(20’)の双対グラフによって構成される、請求項20に記載の方法。
【請求項22】
前記第1のグラフ(20)は、前記第2のグラフ(20)と同じものである、請求項1〜請求項15のいずれか一項に記載の方法。
【請求項23】
前記第1のステップは、第3のグラフ(20”)を定義すること、該第3のグラフ(20”)上でルート検索を実行すること、および該第3のグラフ(20”)上での該ルート検索の結果を利用して、前記複数の頂点(23、24、25、27、28、32、33)に対する評価関数を決定することを含む、請求項1〜請求項22のいずれか一項に記載の方法。
【請求項24】
前記第1のステップにおいて頂点(23、24、25、27、28、32、33)に対する評価関数の値を決定することは、前記第1のグラフ(20)上で予め計算された情報に基づいて、該第1のグラフ(20)上で該頂点(23、24、25、27、28、32、33)から前記目的地(22)までのルートを検索することを含む、請求項1〜請求項23のいずれか一項に記載の方法。
【請求項25】
前記第2のステップにおいて前記ルート(61)を検索することは、前記第1のステップにおいて所与の頂点(29)に対する評価関数の値が決定されたかどうかを決定することを含み、該第1のステップにおいて評価関数の値が決定されていない場合には、該所与の頂点(29)に対する評価関数の値を決定することを含む、請求項1〜請求項24のいずれか一項に記載の方法。
【請求項26】
前記第1のグラフ(20)および前記第2のグラフ(20;20’)は、道路網、コンピュータネットワーク、またはインフラストラクチャネットワークのうちの1つを表現する、請求項1〜請求項25のいずれか一項に記載の方法。
【請求項27】
前記方法は、車両上のナビゲーションシステム(1)によって実行される、請求項1〜請求項26のいずれか一項に記載の方法。
【請求項28】
目的地、特に道路網上の目的地(22;82;132)までのルートを決定するためのデバイスであって、
グラフデータ(4)を格納する格納ユニット(3)であって、該グラフデータ(4)は、第1のグラフ(20)および第2のグラフ(20;20’)のうちの少なくとも1つの頂点(21〜33)およびエッジ(41〜55)を定義する、格納ユニット(3)と、
該格納ユニット(3)に接続されたプロセッサ(2)であって、該プロセッサ(2)は、該グラフデータ(4)を抽出し、該プロセッサは、第1のステップにおいて、該第1のグラフ(20)に基づいて、複数の頂点(23、24、25,27、28,32、33)に対する評価関数の値を決定し、頂点(21〜33)に対する評価関数の値は、該頂点(21〜33)から該目的地(22;82;132)までのルートに関連するコストの下限を表現しており、該プロセッサは、第2のステップにおいて、該第1のステップにおいて決定された該評価関数の値に基づいて、第2のグラフ(20;20’)上で、出発点(21;81;131)から該目的地(22;82;132)までのルート検索を実行する、プロセッサ(2)と
を備えている、デバイス。
【請求項29】
前記プロセッサ(2)は、前記第1のグラフ(20)上でルート検索を実行し、前記評価関数の値を決定する、請求項28に記載のデバイス。
【請求項30】
前記プロセッサ(2)は、前記目的地(22;82;132)から出発して前記出発点(21;81;131)まで延長するルート検索を実行し、前記評価関数の値を決定する、請求項28または請求項29に記載のデバイス。
【請求項31】
前記第2のステップにおいて、前記プロセッサ(2)は、前記第1のステップにおいて決定された前記評価関数の値に基づいて、前記目的地(22;82;132)までの少なくとも1つのさらなるルート検索を実行する、請求項28〜請求項30のいずれか一項に記載のデバイス。
【請求項32】
さらなる格納ユニット(3)を含み、前記プロセッサ(2)は、該さらなる格納ユニット(3)に接続されており、前記第1のステップにおいて決定された前記評価関数の値(5)を該さらなる格納ユニット(3)に格納し、前記第2のステップを実行するために該さらなる格納ユニット(3)から該評価関数の値(5)を抽出する、請求項28〜請求項31のいずれか一項に記載のデバイス。
【請求項33】
前記プロセッサ(2)は、第1のコストモデルに基づいて、前記第1のステップにおいて前記評価関数の値を決定し、第2のコストモデルに基づいて、前記第2のステップにおいて前記出発点(21;81;131)から前記目的地(22;82;132)までのルート検索を実行する、請求項28〜請求項32のいずれか一項に記載のデバイス。
【請求項34】
前記第1のコストモデルにしたがう、前記第1のグラフ(20)の前記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは時間に関係せず、前記第2のコストモデルにしたがう、前記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストは可変である、請求項33に記載のデバイス。
【請求項35】
前記第1のコストモデルにしたがう、前記第1のグラフ(20)の前記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、前記第2のコストモデルにしたがう、前記第2のグラフ(20;20’)の対応する頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストの下限を表現する、請求項33または請求項34に記載のデバイス。
【請求項36】
ユーザ入力を受信する入力ユニット(6)を含み、前記プロセッサ(2)は、該入力ユニット(6)に接続されており、該ユーザ入力に基づいて、前記第2のコストモデルのコストを調整する、請求項33〜請求項35のいずれか一項に記載のデバイス。
【請求項37】
時刻および/または日付を決定するクロックユニット(10)を含み、前記プロセッサ(2)は、該クロックユニット(10)に接続されており、該時刻および/または日付に基づいて、前記第2のコストモデルのコストを調整する、請求項33〜請求項36のいずれか一項に記載の方法。
【請求項38】
交通情報信号を受信する交通メッセージ受信器(9)を含み、前記プロセッサ(2)は、該交通メッセージ受信器(9)に接続されており、該交通情報信号に基づいて、前記第2のコストモデルのコストを調整する、請求項33〜請求項37のいずれか一項に記載の方法。
【請求項39】
前記プロセッサ(2)は、少なくとも1つの頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に対し、前記第1のコストモデルに対して前記第2のコストモデルのコストを増加させ、該第2のコストモデルのコストを調整する、請求項36〜請求項38のいずれか一項に記載のデバイス。
【請求項40】
現在の車両の位置(135)を決定する位置決定手段(8)を含み、前記プロセッサ(2)は、該位置決定手段(8)に接続されており、該現在の車両の位置(135)を前記出発点(21;81;131)から前記目的地(22;82;132)までの前記ルート(61)と比較し、該比較の結果に基づいて、前記第2のグラフ(20;20’)上での該現在の車両の位置(135)から該目的地(132)までのさらなるルート検索を実行する、請求項28〜請求項39のいずれか一項に記載のデバイス。
【請求項41】
前記第1のグラフ(20)は、該第1のグラフ(20)上のルート検索が、平均で、該第2のグラフ(20’)上のルート検索よりも速くなるように定義される、請求項28〜請求項40のいずれか一項に記載のデバイス。
【請求項42】
前記プロセッサ(2)は、請求項1〜請求項27のいずれか一項に記載の方法を実行するように構成されている、請求項28〜請求項41のいずれか一項に記載のデバイス。
【請求項43】
ルートを決定する請求項28〜請求項42のいずれか一項に記載のデバイスと、
該ルート上の情報を出力する出力ユニット(7)と
を含む、ナビゲーションシステム。
【請求項44】
データ格納媒体であって、該データ格納媒体上に命令を有しており、該命令は、ナビゲーションシステム(1)のプロセッサ(2)によって実行されたときに、該ナビゲーションシステム(1)に、請求項1〜請求項27のいずれか一項に記載の方法を実行するように命令する、データ格納媒体。
【請求項1】
目的地、特に道路網上の目的地(22;82;132)までのルートを決定するための方法であって、
第1のステップにおいて、第1のグラフ(20)に基づいて、複数の頂点(23、24、25、27、28、32、33)に対する評価関数の値を決定することであって、頂点(21〜33)に対する評価関数の値は、該頂点(21〜33)から該目的地(22;82;132)までのルートに関連するコストの下限を表現している、ことと、
第2のステップにおいて、該第1のステップにおいて決定された該評価関数の値に基づいて、第2のグラフ(20;20’)上で、出発点(21;81;131)から該目的地(22;82;132)までのルート(61)を検索することと
を包含する、方法。
【請求項2】
前記第1のステップにおいて、頂点(21〜33)に対する評価関数の値を決定することは、前記第1のグラフ(20)上で該頂点(21〜33)から前記目的地(22;82;132)までのルートを検索することを含む、請求項1に記載の方法。
【請求項3】
前記頂点(21〜33)から前記目的地(22)までの前記ルートを検索することは、前記第1のグラフ(20)上でDijkstraアルゴリズムまたはA*−アルゴリズムを用いて実行される、請求項2に記載の方法。
【請求項4】
前記第1のステップにおいて頂点(21〜33)に対する評価関数の値を決定することは、前記第1のグラフ上で、前記目的地(22;82;132)から出発して前記出発点(21;81;131)まで延長するルート検索を実行することを含む、請求項1〜請求項3のいずれか一項に記載の方法。
【請求項5】
前記第2のステップにおいて、前記評価関数の値に基づいて、前記目的地(22;82;132)までのルート(61)とは異なる少なくとも1つのさらなるルート(121;151)を検索すること
を含む、請求項1〜請求項4のいずれか一項に記載の方法。
【請求項6】
前記少なくとも1つのさらなるルート(121;151)は、前記出発点(21)から前記目的地(22)までの代替ルート(121;151)、または別の出発点(135)から前記目的地(132)までのルートのうちの少なくとも1つを含む、請求項5に記載の方法。
【請求項7】
前記出発点(21;131)から前記目的地(22;132)までの前記ルート(61)に対する現在の位置(135)をモニタリングすることであって、前記少なくとも1つのさらなるルートの前記検索は、該現在の位置(135)の該モニタリングの結果に基づいて自動的に開始される、こと
を含む、請求項5または請求項6に記載の方法。
【請求項8】
前記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜45;181〜185)に関連するコストの変化をモニタリングすることであって、前記少なくとも1つのさらなるルート(121;151)の前記検索は、該変化をモニタリングした結果に基づいて自動的に開始される、こと
を含む、請求項5〜請求項7のいずれか一項に記載の方法。
【請求項9】
前記第1のステップにおいて決定された前記評価関数の値の少なくともサブセット(5)を格納することと、
前記第2のステップにおいて該サブセット(5)の少なくとも1つの評価関数の値を抽出することと
を含む、請求項1〜請求項8のいずれか一項に記載の方法。
【請求項10】
前記第1のステップにおける前記評価関数の値の前記決定は、第1のコストモデルに基づいており、前記第2のステップにおける前記出発点(21;81;131)から前記目的地(22;82;132)までの前記ルート(61)の検索は、第2のコストモデルに基づいている、請求項1〜請求項9のいずれか一項に記載の方法。
【請求項11】
前記第1のコストモデルにしたがう、前記第1のグラフ(20)の前記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、時間に関係しない、請求項10に記載の方法。
【請求項12】
前記第2のコストモデルにしたがう、前記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストは可変である、請求項10または請求項11に記載の方法。
【請求項13】
ユーザの選好度、交通情報信号、時刻または日付のうちの少なくとも1つに基づいて、前記第2のコストモデルにしたがう前記コストを調整すること
を含む、請求項12に記載の方法。
【請求項14】
前記調整することは、少なくとも1つの頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に対し、前記第1のコストモデルに対して
前記第2のコストモデルにしたがうコストを増加させることを含む、請求項13に記載の方法。
【請求項15】
前記第1のコストモデルにしたがう前記第1のグラフ(20)の頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、前記第2のコストモデルにしたがう対応する頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストの下限を表現する、請求項12〜請求項14のいずれか一項に記載の方法。
【請求項16】
前記第1のグラフ(20)は、該第1のグラフ(20)上のルート検索が、平均で、該第2のグラフ(20’)上のルート検索よりも速くなるように定義される、請求項1〜請求項15のいずれか一項に記載の方法。
【請求項17】
前記第1のグラフ(20)は、前記第2のグラフ(20’)よりも少ない頂点(21〜33)を有している、請求項1〜請求項16のいずれか一項に記載の方法。
【請求項18】
前記第1のグラフの頂点は、前記道路網の道路セグメントを表現しており、前記第1のステップにおいて、該道路網上のターン制限は無視される、請求項1〜請求項17のいずれか一項に記載の方法。
【請求項19】
前記第1のステップにおいて、一方通行制限が考慮される、請求項18に記載の方法。
【請求項20】
前記第1のグラフ(20)のエッジ(41〜55)は、道路網の道路セグメントを表現しており、前記第2のグラフ(20’)の頂点(171〜178)は、該道路網の道路セグメントを表現している、請求項1〜請求項17のいずれか一項に記載の方法。
【請求項21】
前記第1のグラフ(20)は、前記第2のグラフ(20’)の双対グラフによって構成される、請求項20に記載の方法。
【請求項22】
前記第1のグラフ(20)は、前記第2のグラフ(20)と同じものである、請求項1〜請求項15のいずれか一項に記載の方法。
【請求項23】
前記第1のステップは、第3のグラフ(20”)を定義すること、該第3のグラフ(20”)上でルート検索を実行すること、および該第3のグラフ(20”)上での該ルート検索の結果を利用して、前記複数の頂点(23、24、25、27、28、32、33)に対する評価関数を決定することを含む、請求項1〜請求項22のいずれか一項に記載の方法。
【請求項24】
前記第1のステップにおいて頂点(23、24、25、27、28、32、33)に対する評価関数の値を決定することは、前記第1のグラフ(20)上で予め計算された情報に基づいて、該第1のグラフ(20)上で該頂点(23、24、25、27、28、32、33)から前記目的地(22)までのルートを検索することを含む、請求項1〜請求項23のいずれか一項に記載の方法。
【請求項25】
前記第2のステップにおいて前記ルート(61)を検索することは、前記第1のステップにおいて所与の頂点(29)に対する評価関数の値が決定されたかどうかを決定することを含み、該第1のステップにおいて評価関数の値が決定されていない場合には、該所与の頂点(29)に対する評価関数の値を決定することを含む、請求項1〜請求項24のいずれか一項に記載の方法。
【請求項26】
前記第1のグラフ(20)および前記第2のグラフ(20;20’)は、道路網、コンピュータネットワーク、またはインフラストラクチャネットワークのうちの1つを表現する、請求項1〜請求項25のいずれか一項に記載の方法。
【請求項27】
前記方法は、車両上のナビゲーションシステム(1)によって実行される、請求項1〜請求項26のいずれか一項に記載の方法。
【請求項28】
目的地、特に道路網上の目的地(22;82;132)までのルートを決定するためのデバイスであって、
グラフデータ(4)を格納する格納ユニット(3)であって、該グラフデータ(4)は、第1のグラフ(20)および第2のグラフ(20;20’)のうちの少なくとも1つの頂点(21〜33)およびエッジ(41〜55)を定義する、格納ユニット(3)と、
該格納ユニット(3)に接続されたプロセッサ(2)であって、該プロセッサ(2)は、該グラフデータ(4)を抽出し、該プロセッサは、第1のステップにおいて、該第1のグラフ(20)に基づいて、複数の頂点(23、24、25,27、28,32、33)に対する評価関数の値を決定し、頂点(21〜33)に対する評価関数の値は、該頂点(21〜33)から該目的地(22;82;132)までのルートに関連するコストの下限を表現しており、該プロセッサは、第2のステップにおいて、該第1のステップにおいて決定された該評価関数の値に基づいて、第2のグラフ(20;20’)上で、出発点(21;81;131)から該目的地(22;82;132)までのルート検索を実行する、プロセッサ(2)と
を備えている、デバイス。
【請求項29】
前記プロセッサ(2)は、前記第1のグラフ(20)上でルート検索を実行し、前記評価関数の値を決定する、請求項28に記載のデバイス。
【請求項30】
前記プロセッサ(2)は、前記目的地(22;82;132)から出発して前記出発点(21;81;131)まで延長するルート検索を実行し、前記評価関数の値を決定する、請求項28または請求項29に記載のデバイス。
【請求項31】
前記第2のステップにおいて、前記プロセッサ(2)は、前記第1のステップにおいて決定された前記評価関数の値に基づいて、前記目的地(22;82;132)までの少なくとも1つのさらなるルート検索を実行する、請求項28〜請求項30のいずれか一項に記載のデバイス。
【請求項32】
さらなる格納ユニット(3)を含み、前記プロセッサ(2)は、該さらなる格納ユニット(3)に接続されており、前記第1のステップにおいて決定された前記評価関数の値(5)を該さらなる格納ユニット(3)に格納し、前記第2のステップを実行するために該さらなる格納ユニット(3)から該評価関数の値(5)を抽出する、請求項28〜請求項31のいずれか一項に記載のデバイス。
【請求項33】
前記プロセッサ(2)は、第1のコストモデルに基づいて、前記第1のステップにおいて前記評価関数の値を決定し、第2のコストモデルに基づいて、前記第2のステップにおいて前記出発点(21;81;131)から前記目的地(22;82;132)までのルート検索を実行する、請求項28〜請求項32のいずれか一項に記載のデバイス。
【請求項34】
前記第1のコストモデルにしたがう、前記第1のグラフ(20)の前記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは時間に関係せず、前記第2のコストモデルにしたがう、前記第2のグラフ(20;20’)の頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストは可変である、請求項33に記載のデバイス。
【請求項35】
前記第1のコストモデルにしたがう、前記第1のグラフ(20)の前記頂点(21〜33)および/またはエッジ(41〜55)に関連するコストは、前記第2のコストモデルにしたがう、前記第2のグラフ(20;20’)の対応する頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に関連するコストの下限を表現する、請求項33または請求項34に記載のデバイス。
【請求項36】
ユーザ入力を受信する入力ユニット(6)を含み、前記プロセッサ(2)は、該入力ユニット(6)に接続されており、該ユーザ入力に基づいて、前記第2のコストモデルのコストを調整する、請求項33〜請求項35のいずれか一項に記載のデバイス。
【請求項37】
時刻および/または日付を決定するクロックユニット(10)を含み、前記プロセッサ(2)は、該クロックユニット(10)に接続されており、該時刻および/または日付に基づいて、前記第2のコストモデルのコストを調整する、請求項33〜請求項36のいずれか一項に記載の方法。
【請求項38】
交通情報信号を受信する交通メッセージ受信器(9)を含み、前記プロセッサ(2)は、該交通メッセージ受信器(9)に接続されており、該交通情報信号に基づいて、前記第2のコストモデルのコストを調整する、請求項33〜請求項37のいずれか一項に記載の方法。
【請求項39】
前記プロセッサ(2)は、少なくとも1つの頂点(21〜33;171〜178)および/またはエッジ(41〜55;181〜185)に対し、前記第1のコストモデルに対して前記第2のコストモデルのコストを増加させ、該第2のコストモデルのコストを調整する、請求項36〜請求項38のいずれか一項に記載のデバイス。
【請求項40】
現在の車両の位置(135)を決定する位置決定手段(8)を含み、前記プロセッサ(2)は、該位置決定手段(8)に接続されており、該現在の車両の位置(135)を前記出発点(21;81;131)から前記目的地(22;82;132)までの前記ルート(61)と比較し、該比較の結果に基づいて、前記第2のグラフ(20;20’)上での該現在の車両の位置(135)から該目的地(132)までのさらなるルート検索を実行する、請求項28〜請求項39のいずれか一項に記載のデバイス。
【請求項41】
前記第1のグラフ(20)は、該第1のグラフ(20)上のルート検索が、平均で、該第2のグラフ(20’)上のルート検索よりも速くなるように定義される、請求項28〜請求項40のいずれか一項に記載のデバイス。
【請求項42】
前記プロセッサ(2)は、請求項1〜請求項27のいずれか一項に記載の方法を実行するように構成されている、請求項28〜請求項41のいずれか一項に記載のデバイス。
【請求項43】
ルートを決定する請求項28〜請求項42のいずれか一項に記載のデバイスと、
該ルート上の情報を出力する出力ユニット(7)と
を含む、ナビゲーションシステム。
【請求項44】
データ格納媒体であって、該データ格納媒体上に命令を有しており、該命令は、ナビゲーションシステム(1)のプロセッサ(2)によって実行されたときに、該ナビゲーションシステム(1)に、請求項1〜請求項27のいずれか一項に記載の方法を実行するように命令する、データ格納媒体。
【図1】
【図2A】
【図2B】
【図3】
【図4A】
【図4B】
【図4C】
【図5】
【図6】
【図7】
【図8A】
【図8B】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14A】
【図14B】
【図2A】
【図2B】
【図3】
【図4A】
【図4B】
【図4C】
【図5】
【図6】
【図7】
【図8A】
【図8B】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14A】
【図14B】
【公開番号】特開2008−275621(P2008−275621A)
【公開日】平成20年11月13日(2008.11.13)
【国際特許分類】
【出願番号】特願2008−119334(P2008−119334)
【出願日】平成20年4月30日(2008.4.30)
【出願人】(504147933)ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【Fターム(参考)】
【公開日】平成20年11月13日(2008.11.13)
【国際特許分類】
【出願日】平成20年4月30日(2008.4.30)
【出願人】(504147933)ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【Fターム(参考)】
[ Back to top ]