経路探索加速データとともに地図データを用いるナビゲーション装置
それぞれが電子地図によってカバーされるエリアにおいてナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む電子地図にわたり経路を計画する際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、ａ）ナビゲート可能セグメントのコアネットワークを形成するナビゲート可能セグメントを除去することにより探索加速データの作成時に考慮されるナビゲート可能セグメントの数を減少するステップと、ｂ）各ナビゲート可能セグメントが階層の各レベルの少なくとも１つの領域に分類されるように電子地図を階層領域の集合に分割するステップと、ｃ）ナビゲート可能セグメントが少なくとも１つの領域までの最小コストの経路の一部であるかを判定するためにコアネットワークの少なくともいくつかのナビゲート可能セグメント、一般には各ナビゲート可能セグメントと関連付けられた時変関数を使用し且つ当該判定を探索加速データに記録するステップとを含む方法。
Notice: Undefined index: DEJ in /mnt/www/gzt_disp.php on line 298
【特許請求の範囲】
【請求項１】
それぞれが電子地図によってカバーされるエリアにおいてナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む前記電子地図にわたり経路を計画する際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
ａ）ナビゲート可能セグメントのコアネットワークを形成するナビゲート可能セグメントを除去することにより探索加速データの作成時に考慮されるナビゲート可能セグメントの数を減少するステップと、
ｂ）各ナビゲート可能セグメントが階層の各レベルの少なくとも１つの領域に分類されるように電子地図を複数の階層領域の集合に分割するステップと、
ｃ）ナビゲート可能セグメントが複数の領域の少なくとも１つまでの最小コストの経路の一部であるかを判定するために前記コアネットワークの少なくともいくつかのナビゲート可能セグメント、一般には各ナビゲート可能セグメントと関連付けられた時変関数を使用し且つ当該判定を探索加速データに記録するステップと、
ｄ）地図データを生成するステップと、
を含むことを特徴とする方法。
【請求項２】
前記時変関数は、実質的に前記地図データの各ナビゲート可能セグメントに対して提供されることを特徴とする請求項１に記載の方法。
【請求項３】
前記コアネットワークは、前記探索加速データが後に回復されるナビゲート可能セグメントを除去することによって生成されることを特徴とする請求項１又は２に記載の方法。
【請求項４】
前記コアネットワークの外部の前記ナビゲート可能セグメントに対する探索加速データを生成するステップをさらに含むことを特徴とする請求項１乃至３の何れか１項に記載の方法。
【請求項５】
・道路プロパティに関連する所定の基準を満たすナビゲート可能セグメントを除去することと、
・ある所定の基準に従って十分に小さく、且つ、更なる所定の基準を満たすナビゲート可能セグメントの集合を除去することによってネットワークの残りの部分から切断される、前記ネットワークの部分を形成するナビゲート可能セグメントをネットワークから除去することと、
・所定の状況においてナビゲート可能セグメントの間の分岐点に存在するノードを他方のノードにまとめることと、
・ノードが２つ以下のナビゲート可能セグメントを接続させる場合に当該ノードを他方のノードにまとめることと
の少なくとも１つの基準に従って、前記探索加速データの作成前に前記電子地図からナビゲート可能セグメントを除去することを特徴とする請求項１乃至４の何れか１項に記載の方法。
【請求項６】
・前記探索加速データ中のビット対の相関性を計算するステップと、
・可逆的に符号化するビット数を減少するために前記探索加速データ中の実質的に相関されたビットを結合させるステップと、
・不可逆的圧縮を実行するために前記探索加速データ中の相関されたビットを結合させるステップと、
・相関性に従って結合された前記探索加速データ中のビットを再順序付けするステップと、
・前記探索加速データをハフマン符号化するステップと
の少なくとも１つのステップに従って、探索加速データが作成された後に探索加速データを圧縮することを特徴とする請求項１乃至５の何れか１項に記載の方法。
【請求項７】
電子地図によってカバーされるエリアにおけるナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
前記処理装置が、
ａ．ナビゲート可能セグメントが最小コストの経路の一部であるかどうかを示す前記電子地図の前記ナビゲート可能セグメントの少なくともいくつか、一般的にはナビゲート可能セグメントのそれぞれに対する探索加速データを生成するために当該ナビゲート可能セグメントを処理し、
ｂ．以下のステップ、
・前記探索加速データ中のビット対の相関性を計算するステップと、
・可逆的に符号化するビット数を減少するために前記探索加速データ中の実質的に相関されたビットを結合させるステップと、
・不可逆的圧縮を実行するために前記探索加速データ中の相関されたビットを結合させるステップと、
・相関性に従って結合された前記探索加速データ中のビットを再順序付けするステップと、
・前記探索加速データをハフマン符号化するステップと
の少なくとも１つのステップを含む圧縮によって当該データを圧縮するために前記生成された探索加速データを処理する
ことを特徴とする方法。
【請求項８】
電子地図によってカバーされるエリアにおけるナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
前記処理装置は、
ａ．ナビゲート可能セグメントのコアネットワークを形成するナビゲート可能セグメントを除去することによって、前記探索加速データの作成時に考慮されるナビゲート可能セグメントの数を減少させるためにナビゲート可能セグメントを処理するステップと、
ｂ．当該ナビゲート可能セグメントが最小コストの経路の一部であるかどうかを示す前記コアネットワークのナビゲート可能セグメントの少なくとも一部に対して、一般には各ナビゲート可能セグメントに対して前記探索加速データを生成するステップと、
を実行し、
前記ステップａ．は、
・道路プロパティに関連した所定の基準を満たすナビゲート可能セグメントを除去するステップと、
・ある所定の基準に従って十分に小さく、且つ、更なる所定の基準を満たすナビゲート可能セグメントの集合を除去することによってネットワークの残りの部分から切断される、ネットワークの部分を形成するナビゲート可能セグメントをネットワークから除去するステップと、
・所定の状況においてナビゲート可能セグメントの間の分岐点に存在するノードを他方のノードにまとめるステップと、
・ノードが２つ以下のナビゲート可能セグメントを接続させる場合に当該ノードを他方のノードにまとめるステップと
を含むことを特徴とする方法。
【請求項９】
それぞれが電子地図によってカバーされるエリアにおいてナビゲート可能な経路のセグメントを表し且つナビゲート可能な経路のパラメータを表す関連付けられた少なくとも１つの属性を有する複数の関連付けられたノードを有する複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
ａ）少なくとも１つの属性を評価するステップと、
ｂ）ナビゲート可能セグメントと関連付けられたノードが前記電子地図の領域にわたり均衡されることを保証するためにステップａ）の評価を使用して各ナビゲート可能セグメントを階層の各レベルの少なくとも１つの領域に分類するように、前記電子地図を階層領域の集合に分割するステップと、
ｃ）前記地図データを生成するステップと、
を含むことを特徴とする方法。
【請求項１０】
前記ステップａ）及びｂ）は、領域にわたるノードの均衡を測定する所定の基準が満たされるまで繰り返し実行されることを特徴とする請求項９に記載の方法。
【請求項１１】
前記属性は、
・ナビゲート可能セグメントの種類と、
・ナビゲート可能セグメントに沿う平均速度と、
・ナビゲート可能セグメントの長さと、
・他のナビゲート可能セグメントに対する当該ナビゲート可能セグメントの接続性と
の何れかを含むことを特徴とする請求項９又は１０に記載の方法。
【請求項１２】
移動時間が所定の閾値より遅くなる前記電子地図の領域を判定し、判定された当該領域内のナビゲート可能セグメントを、前記電子地図の他の領域から分離することを特徴とする請求項９乃至１１の何れか１項に記載の方法。
【請求項１３】
ナビゲート可能セグメントに対する属性がフェリー路線であると判定することにより、島の一部であるナビゲート可能セグメントを前記電子地図の他の領域から分離することを特徴とする請求項９乃至１２の何れか１項に記載の方法。
【請求項１４】
電子地図によってカバーされるエリアにおけるナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
ａ）より粗なレベルのいずれか１つの領域がより精細なレベルの複数の領域を含み、各ナビゲート可能セグメントがより粗なレベル及びより精細なレベルの各々の少なくとも１つの領域に分類されるように、前記電子地図を少なくともより粗なレベル及び近傍のより精細なレベルに属する複数の階層領域に分割するステップと、
ｂ）行先領域を含むより粗なレベルの領域に近接する領域が可視エリアに追加されるべきかを評価し且つ当該評価が肯定的である場合に当該領域を追加することにより、行先領域を含むより粗なレベルの領域を少なくとも含む可視エリアの範囲を所定の行先領域に対して判定するステップと、
ｃ）少なくともいくつかのナビゲート可能セグメントに対して前記行先領域までの少なくとも１つの最小コストの経路に関する情報を算出するステップと、
ｄ）ナビゲート可能セグメントの処理が前記行先領域から該ナビゲート可能セグメントへ戻る逆探索の実行を含み、実質的に前記行先領域の前記可視エリアのナビゲート可能セグメントのみを含むステップと、
ｅ）前記地図データを生成するステップと
を含むことを特徴とする方法。
【請求項１５】
電子地図によってカバーされるエリアにおけるナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
ａ）より粗なレベルのいずれか１つの領域がより精細なレベルの複数の領域を含む場合に、各ナビゲート可能セグメントがより粗なレベル及びより精細なレベルの各々の少なくとも１つの領域に分類されるように、前記電子地図を少なくともより粗なレベル及び近傍のより精細なレベルに属する複数の階層領域に分割するステップと、
ｂ）行先領域を含むより粗なレベルの領域に近接する領域が可視エリアに追加されるべきかを評価し且つ当該評価が肯定的である場合に当該領域を追加することにより、行先領域を含むより粗なレベルの領域を少なくとも含む可視エリアの範囲を所定の行先領域に対して判定するステップと、
ｃ）少なくともいくつかのナビゲート可能セグメントに対して前記行先領域までの少なくとも１つの最小コストの経路に関する情報を算出するステップと、
ｄ）前記可視エリアの少なくともいくつかのナビゲート可能セグメントに対して、一般には各ナビゲート可能セグメントに対して、前記行先領域までの少なくとも１つの最小コストの経路に関する情報を含むように前記探索加速データを構成するステップと、
ｅ）前記地図データを生成するステップと
を含むことを特徴とする方法。
【請求項１６】
前記ステップｂ）における、領域が前記行先領域を含むより粗なレベルの領域に近接するかに関する評価は、所定の基準に基づき、
前記所定の基準は、グラフ理論距離、地理的距離、移動時間、燃料消費及びＣＯ２排出のうちのいずれか１つ又はそれらの組み合わせであることを特徴とする請求項１４又は１５に記載の方法。
【請求項１７】
前記ステップｂ）において、前記行先領域を含むより粗なレベルの領域に隣接する領域がより近接すると判定されることを特徴とする請求項１４乃至１６の何れか１項に記載の方法。
【請求項１８】
前記可視エリアに追加された領域は、より粗なレベルの１つ以上の領域と、より粗なレベルの１つ以上の領域の一部と、のうちの少なくとも一方を含むことを特徴とする請求項１４乃至１７の何れか１項に記載の方法。
【請求項１９】
前記探索加速データは、最小コストの経路に加えて少なくとも１つの追加の経路を含み、
前記追加の経路は、
・所定の出発地と目的地との間の異なる時間における種々の最小コストの経路と、
・種々の交通状況に対する所定の出発地と目的地との間の種々の最小コストの経路と、
・種々のコスト関数に従う所定の出発地と目的地との間の種々の最小コストの経路と、
・所定の道路ネットワークのあらゆる動的変化に対する所定の出発地と目的地との間の種々の最小コストの経路と、
・同一のコスト関数に従う所定の出発地と目的地との間の別の経路と、
・互いに類似する方向の種々の目的地と
のいずれか１つ以上を反映することを特徴とする請求項１乃至１８の何れか１項に記載の方法。
【請求項２０】
電子地図によってカバーされるエリアにおけるナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
ａ）地図を階層の１つ以上のレベルの複数の階層領域に分割するステップと、
ｂ）レベル階層の順序で階層の特定のレベルに属する領域の少なくとも一部を処理し、最も精細なレベルから最も粗なレベルに向かって動作し、それら領域の少なくとも一部に対してその領域に入るナビゲート可能セグメント及び／又はその領域から出るナビゲート可能セグメントを判定するステップと、
ｃ）地図内のナビゲート可能セグメントの少なくとも一部を処理してそのナビゲート可能セグメントから行先領域までの少なくとも１つの最小コストの経路を決定するステップと、
ｄ）ナビゲート可能セグメントの処理が行先領域からナビゲート可能セグメントに戻る逆探索の実行を含むステップと、
ｅ）結果として得られた探索グラフにおいて、次に精細なレベルの少なくとも１つの領域に対して、所定の領域からの最小コストの各パスが次に精細なレベルの領域の集合の少なくとも１つの領域を通過するようにその集合を特定し、結果として相関行列を得るステップと、
ｆ）結果として得られた探索グラフにおいて、自身とは異なる領域から更なる行先領域までのいずれのパスにも含まれず且つ従って「非通過セグメント」と考えられるナビゲート可能セグメントを特定し、後続ステップにおいて考慮されるナビゲート可能セグメントの数を減少するために後続ステップのためにそれら非通過セグメントを除去するステップと、
ｇ）探索加速データの作成が前の全てのステップにおいて除去された非通過セグメントに探索加速データを割り当てるために相関行列を使用することを含むステップと、
ｈ）地図データを生成するステップと、
を含むことを特徴とする方法。
【請求項２１】
請求項１乃至６の何れか１項に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２２】
請求項７に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２３】
請求項８に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２４】
請求項９乃至１３の何れか１項に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２５】
請求項１４に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２６】
請求項１５乃至１９の何れか１項に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２７】
請求項２０に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２８】
コンピュータが、請求項１乃至６の何れか１項に記載の方法を実行するように、又は、請求項２１に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項２９】
コンピュータが、請求項７に記載の方法を実行するように、又は、請求項２２に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３０】
コンピュータが、請求項８に記載の方法を実行するように、又は、請求項２３に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３１】
コンピュータが、請求項９乃至１３の何れか１項に記載の方法を実行するように、又は、請求項２４に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３２】
コンピュータが、請求項１４に記載の方法を実行するように、又は、請求項２５に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３３】
コンピュータが、請求項１５乃至１９の何れか１項に記載の方法を実行するように、又は、請求項２６に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３４】
コンピュータが、請求項２０に記載の方法を実行するように、又は、請求項２７に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３５】
プロセッサを使用して電子地図にわたり経路を生成するように構成されたナビゲーション装置であって、
前記プロセッサは、
前記電子地図にわたり経路探索を実行し、
前記電子地図のナビゲート可能セグメントを表す、探索中に処理されたノードにおけるコストの算出において、当該ノードに接続されたナビゲート可能セグメントが最小コストの経路の一部として印をつけられるか否かの評価を実行し、
そのようなナビゲート可能セグメントが存在する場合に当該ナビゲート可能セグメントのみを探索するように構成されることを特徴とするナビゲーション装置。
【請求項３６】
請求項３５に記載のナビゲーション装置によって提供される経路計画を提供する方法。
【請求項３７】
コンピュータが、請求項３５に記載のナビゲーション装置として動作するように、又は、請求項３６に記載の方法を提供するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３８】
請求項１乃至２０の何れか１項に記載の方法によって生成される探索加速データ。
【請求項３９】
請求項３８に記載の探索加速データを含むコンピュータで読み取り可能な記憶媒体。
【請求項４０】
地図データを解析するためにプロセッサを使用して目的地までの電子地図にわたる経路を生成するように構成されたナビゲーション装置であって、
前記プロセッサは、
・前記地図データに保持された情報を使用して前記電子地図にわたり経路探索を実行し、
・前記電子地図のナビゲート可能セグメントを表す、探索中に処理されたノードにおけるコストの算出において、当該ノードに接続されたナビゲート可能セグメントが探索加速データ内で最小コストの経路の一部として印をつけられるか否かの評価を実行し、
・最小コストの経路に関する更なる情報を提供する追加の探索加速データがノードから目的地までに存在するかに関する指標を前記地図データが含み、
・そのような追加の探索加速データが利用可能である場合に、該追加の探索加速データにおける最小コストの経路の一部として印をつけられたそれらのナビゲート可能セグメントのみを探索するように構成されることを特徴とするナビゲーション装置。
【請求項１】
それぞれが電子地図によってカバーされるエリアにおいてナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む前記電子地図にわたり経路を計画する際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
ａ）ナビゲート可能セグメントのコアネットワークを形成するナビゲート可能セグメントを除去することにより探索加速データの作成時に考慮されるナビゲート可能セグメントの数を減少するステップと、
ｂ）各ナビゲート可能セグメントが階層の各レベルの少なくとも１つの領域に分類されるように電子地図を複数の階層領域の集合に分割するステップと、
ｃ）ナビゲート可能セグメントが複数の領域の少なくとも１つまでの最小コストの経路の一部であるかを判定するために前記コアネットワークの少なくともいくつかのナビゲート可能セグメント、一般には各ナビゲート可能セグメントと関連付けられた時変関数を使用し且つ当該判定を探索加速データに記録するステップと、
ｄ）地図データを生成するステップと、
を含むことを特徴とする方法。
【請求項２】
前記時変関数は、実質的に前記地図データの各ナビゲート可能セグメントに対して提供されることを特徴とする請求項１に記載の方法。
【請求項３】
前記コアネットワークは、前記探索加速データが後に回復されるナビゲート可能セグメントを除去することによって生成されることを特徴とする請求項１又は２に記載の方法。
【請求項４】
前記コアネットワークの外部の前記ナビゲート可能セグメントに対する探索加速データを生成するステップをさらに含むことを特徴とする請求項１乃至３の何れか１項に記載の方法。
【請求項５】
・道路プロパティに関連する所定の基準を満たすナビゲート可能セグメントを除去することと、
・ある所定の基準に従って十分に小さく、且つ、更なる所定の基準を満たすナビゲート可能セグメントの集合を除去することによってネットワークの残りの部分から切断される、前記ネットワークの部分を形成するナビゲート可能セグメントをネットワークから除去することと、
・所定の状況においてナビゲート可能セグメントの間の分岐点に存在するノードを他方のノードにまとめることと、
・ノードが２つ以下のナビゲート可能セグメントを接続させる場合に当該ノードを他方のノードにまとめることと
の少なくとも１つの基準に従って、前記探索加速データの作成前に前記電子地図からナビゲート可能セグメントを除去することを特徴とする請求項１乃至４の何れか１項に記載の方法。
【請求項６】
・前記探索加速データ中のビット対の相関性を計算するステップと、
・可逆的に符号化するビット数を減少するために前記探索加速データ中の実質的に相関されたビットを結合させるステップと、
・不可逆的圧縮を実行するために前記探索加速データ中の相関されたビットを結合させるステップと、
・相関性に従って結合された前記探索加速データ中のビットを再順序付けするステップと、
・前記探索加速データをハフマン符号化するステップと
の少なくとも１つのステップに従って、探索加速データが作成された後に探索加速データを圧縮することを特徴とする請求項１乃至５の何れか１項に記載の方法。
【請求項７】
電子地図によってカバーされるエリアにおけるナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
前記処理装置が、
ａ．ナビゲート可能セグメントが最小コストの経路の一部であるかどうかを示す前記電子地図の前記ナビゲート可能セグメントの少なくともいくつか、一般的にはナビゲート可能セグメントのそれぞれに対する探索加速データを生成するために当該ナビゲート可能セグメントを処理し、
ｂ．以下のステップ、
・前記探索加速データ中のビット対の相関性を計算するステップと、
・可逆的に符号化するビット数を減少するために前記探索加速データ中の実質的に相関されたビットを結合させるステップと、
・不可逆的圧縮を実行するために前記探索加速データ中の相関されたビットを結合させるステップと、
・相関性に従って結合された前記探索加速データ中のビットを再順序付けするステップと、
・前記探索加速データをハフマン符号化するステップと
の少なくとも１つのステップを含む圧縮によって当該データを圧縮するために前記生成された探索加速データを処理する
ことを特徴とする方法。
【請求項８】
電子地図によってカバーされるエリアにおけるナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
前記処理装置は、
ａ．ナビゲート可能セグメントのコアネットワークを形成するナビゲート可能セグメントを除去することによって、前記探索加速データの作成時に考慮されるナビゲート可能セグメントの数を減少させるためにナビゲート可能セグメントを処理するステップと、
ｂ．当該ナビゲート可能セグメントが最小コストの経路の一部であるかどうかを示す前記コアネットワークのナビゲート可能セグメントの少なくとも一部に対して、一般には各ナビゲート可能セグメントに対して前記探索加速データを生成するステップと、
を実行し、
前記ステップａ．は、
・道路プロパティに関連した所定の基準を満たすナビゲート可能セグメントを除去するステップと、
・ある所定の基準に従って十分に小さく、且つ、更なる所定の基準を満たすナビゲート可能セグメントの集合を除去することによってネットワークの残りの部分から切断される、ネットワークの部分を形成するナビゲート可能セグメントをネットワークから除去するステップと、
・所定の状況においてナビゲート可能セグメントの間の分岐点に存在するノードを他方のノードにまとめるステップと、
・ノードが２つ以下のナビゲート可能セグメントを接続させる場合に当該ノードを他方のノードにまとめるステップと
を含むことを特徴とする方法。
【請求項９】
それぞれが電子地図によってカバーされるエリアにおいてナビゲート可能な経路のセグメントを表し且つナビゲート可能な経路のパラメータを表す関連付けられた少なくとも１つの属性を有する複数の関連付けられたノードを有する複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
ａ）少なくとも１つの属性を評価するステップと、
ｂ）ナビゲート可能セグメントと関連付けられたノードが前記電子地図の領域にわたり均衡されることを保証するためにステップａ）の評価を使用して各ナビゲート可能セグメントを階層の各レベルの少なくとも１つの領域に分類するように、前記電子地図を階層領域の集合に分割するステップと、
ｃ）前記地図データを生成するステップと、
を含むことを特徴とする方法。
【請求項１０】
前記ステップａ）及びｂ）は、領域にわたるノードの均衡を測定する所定の基準が満たされるまで繰り返し実行されることを特徴とする請求項９に記載の方法。
【請求項１１】
前記属性は、
・ナビゲート可能セグメントの種類と、
・ナビゲート可能セグメントに沿う平均速度と、
・ナビゲート可能セグメントの長さと、
・他のナビゲート可能セグメントに対する当該ナビゲート可能セグメントの接続性と
の何れかを含むことを特徴とする請求項９又は１０に記載の方法。
【請求項１２】
移動時間が所定の閾値より遅くなる前記電子地図の領域を判定し、判定された当該領域内のナビゲート可能セグメントを、前記電子地図の他の領域から分離することを特徴とする請求項９乃至１１の何れか１項に記載の方法。
【請求項１３】
ナビゲート可能セグメントに対する属性がフェリー路線であると判定することにより、島の一部であるナビゲート可能セグメントを前記電子地図の他の領域から分離することを特徴とする請求項９乃至１２の何れか１項に記載の方法。
【請求項１４】
電子地図によってカバーされるエリアにおけるナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
ａ）より粗なレベルのいずれか１つの領域がより精細なレベルの複数の領域を含み、各ナビゲート可能セグメントがより粗なレベル及びより精細なレベルの各々の少なくとも１つの領域に分類されるように、前記電子地図を少なくともより粗なレベル及び近傍のより精細なレベルに属する複数の階層領域に分割するステップと、
ｂ）行先領域を含むより粗なレベルの領域に近接する領域が可視エリアに追加されるべきかを評価し且つ当該評価が肯定的である場合に当該領域を追加することにより、行先領域を含むより粗なレベルの領域を少なくとも含む可視エリアの範囲を所定の行先領域に対して判定するステップと、
ｃ）少なくともいくつかのナビゲート可能セグメントに対して前記行先領域までの少なくとも１つの最小コストの経路に関する情報を算出するステップと、
ｄ）ナビゲート可能セグメントの処理が前記行先領域から該ナビゲート可能セグメントへ戻る逆探索の実行を含み、実質的に前記行先領域の前記可視エリアのナビゲート可能セグメントのみを含むステップと、
ｅ）前記地図データを生成するステップと
を含むことを特徴とする方法。
【請求項１５】
電子地図によってカバーされるエリアにおけるナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
ａ）より粗なレベルのいずれか１つの領域がより精細なレベルの複数の領域を含む場合に、各ナビゲート可能セグメントがより粗なレベル及びより精細なレベルの各々の少なくとも１つの領域に分類されるように、前記電子地図を少なくともより粗なレベル及び近傍のより精細なレベルに属する複数の階層領域に分割するステップと、
ｂ）行先領域を含むより粗なレベルの領域に近接する領域が可視エリアに追加されるべきかを評価し且つ当該評価が肯定的である場合に当該領域を追加することにより、行先領域を含むより粗なレベルの領域を少なくとも含む可視エリアの範囲を所定の行先領域に対して判定するステップと、
ｃ）少なくともいくつかのナビゲート可能セグメントに対して前記行先領域までの少なくとも１つの最小コストの経路に関する情報を算出するステップと、
ｄ）前記可視エリアの少なくともいくつかのナビゲート可能セグメントに対して、一般には各ナビゲート可能セグメントに対して、前記行先領域までの少なくとも１つの最小コストの経路に関する情報を含むように前記探索加速データを構成するステップと、
ｅ）前記地図データを生成するステップと
を含むことを特徴とする方法。
【請求項１６】
前記ステップｂ）における、領域が前記行先領域を含むより粗なレベルの領域に近接するかに関する評価は、所定の基準に基づき、
前記所定の基準は、グラフ理論距離、地理的距離、移動時間、燃料消費及びＣＯ２排出のうちのいずれか１つ又はそれらの組み合わせであることを特徴とする請求項１４又は１５に記載の方法。
【請求項１７】
前記ステップｂ）において、前記行先領域を含むより粗なレベルの領域に隣接する領域がより近接すると判定されることを特徴とする請求項１４乃至１６の何れか１項に記載の方法。
【請求項１８】
前記可視エリアに追加された領域は、より粗なレベルの１つ以上の領域と、より粗なレベルの１つ以上の領域の一部と、のうちの少なくとも一方を含むことを特徴とする請求項１４乃至１７の何れか１項に記載の方法。
【請求項１９】
前記探索加速データは、最小コストの経路に加えて少なくとも１つの追加の経路を含み、
前記追加の経路は、
・所定の出発地と目的地との間の異なる時間における種々の最小コストの経路と、
・種々の交通状況に対する所定の出発地と目的地との間の種々の最小コストの経路と、
・種々のコスト関数に従う所定の出発地と目的地との間の種々の最小コストの経路と、
・所定の道路ネットワークのあらゆる動的変化に対する所定の出発地と目的地との間の種々の最小コストの経路と、
・同一のコスト関数に従う所定の出発地と目的地との間の別の経路と、
・互いに類似する方向の種々の目的地と
のいずれか１つ以上を反映することを特徴とする請求項１乃至１８の何れか１項に記載の方法。
【請求項２０】
電子地図によってカバーされるエリアにおけるナビゲート可能な経路のセグメントを表す複数のナビゲート可能セグメントを含む電子地図を処理するために少なくとも１つの処理装置を使用する、電子地図にわたり経路が計画される際の速度を向上するように構成された探索加速データを含む地図データを作成する方法であって、
ａ）地図を階層の１つ以上のレベルの複数の階層領域に分割するステップと、
ｂ）レベル階層の順序で階層の特定のレベルに属する領域の少なくとも一部を処理し、最も精細なレベルから最も粗なレベルに向かって動作し、それら領域の少なくとも一部に対してその領域に入るナビゲート可能セグメント及び／又はその領域から出るナビゲート可能セグメントを判定するステップと、
ｃ）地図内のナビゲート可能セグメントの少なくとも一部を処理してそのナビゲート可能セグメントから行先領域までの少なくとも１つの最小コストの経路を決定するステップと、
ｄ）ナビゲート可能セグメントの処理が行先領域からナビゲート可能セグメントに戻る逆探索の実行を含むステップと、
ｅ）結果として得られた探索グラフにおいて、次に精細なレベルの少なくとも１つの領域に対して、所定の領域からの最小コストの各パスが次に精細なレベルの領域の集合の少なくとも１つの領域を通過するようにその集合を特定し、結果として相関行列を得るステップと、
ｆ）結果として得られた探索グラフにおいて、自身とは異なる領域から更なる行先領域までのいずれのパスにも含まれず且つ従って「非通過セグメント」と考えられるナビゲート可能セグメントを特定し、後続ステップにおいて考慮されるナビゲート可能セグメントの数を減少するために後続ステップのためにそれら非通過セグメントを除去するステップと、
ｇ）探索加速データの作成が前の全てのステップにおいて除去された非通過セグメントに探索加速データを割り当てるために相関行列を使用することを含むステップと、
ｈ）地図データを生成するステップと、
を含むことを特徴とする方法。
【請求項２１】
請求項１乃至６の何れか１項に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２２】
請求項７に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２３】
請求項８に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２４】
請求項９乃至１３の何れか１項に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２５】
請求項１４に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２６】
請求項１５乃至１９の何れか１項に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２７】
請求項２０に記載の方法を実行するように構成されたコンピュータデバイス。
【請求項２８】
コンピュータが、請求項１乃至６の何れか１項に記載の方法を実行するように、又は、請求項２１に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項２９】
コンピュータが、請求項７に記載の方法を実行するように、又は、請求項２２に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３０】
コンピュータが、請求項８に記載の方法を実行するように、又は、請求項２３に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３１】
コンピュータが、請求項９乃至１３の何れか１項に記載の方法を実行するように、又は、請求項２４に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３２】
コンピュータが、請求項１４に記載の方法を実行するように、又は、請求項２５に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３３】
コンピュータが、請求項１５乃至１９の何れか１項に記載の方法を実行するように、又は、請求項２６に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３４】
コンピュータが、請求項２０に記載の方法を実行するように、又は、請求項２７に記載のコンピュータデバイスとして動作するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３５】
プロセッサを使用して電子地図にわたり経路を生成するように構成されたナビゲーション装置であって、
前記プロセッサは、
前記電子地図にわたり経路探索を実行し、
前記電子地図のナビゲート可能セグメントを表す、探索中に処理されたノードにおけるコストの算出において、当該ノードに接続されたナビゲート可能セグメントが最小コストの経路の一部として印をつけられるか否かの評価を実行し、
そのようなナビゲート可能セグメントが存在する場合に当該ナビゲート可能セグメントのみを探索するように構成されることを特徴とするナビゲーション装置。
【請求項３６】
請求項３５に記載のナビゲーション装置によって提供される経路計画を提供する方法。
【請求項３７】
コンピュータが、請求項３５に記載のナビゲーション装置として動作するように、又は、請求項３６に記載の方法を提供するように、コンピュータで読み込んで実行される命令を含むコンピュータで読み取り可能な記憶媒体。
【請求項３８】
請求項１乃至２０の何れか１項に記載の方法によって生成される探索加速データ。
【請求項３９】
請求項３８に記載の探索加速データを含むコンピュータで読み取り可能な記憶媒体。
【請求項４０】
地図データを解析するためにプロセッサを使用して目的地までの電子地図にわたる経路を生成するように構成されたナビゲーション装置であって、
前記プロセッサは、
・前記地図データに保持された情報を使用して前記電子地図にわたり経路探索を実行し、
・前記電子地図のナビゲート可能セグメントを表す、探索中に処理されたノードにおけるコストの算出において、当該ノードに接続されたナビゲート可能セグメントが探索加速データ内で最小コストの経路の一部として印をつけられるか否かの評価を実行し、
・最小コストの経路に関する更なる情報を提供する追加の探索加速データがノードから目的地までに存在するかに関する指標を前記地図データが含み、
・そのような追加の探索加速データが利用可能である場合に、該追加の探索加速データにおける最小コストの経路の一部として印をつけられたそれらのナビゲート可能セグメントのみを探索するように構成されることを特徴とするナビゲーション装置。
【図１】
【図１ａ】
【図１ｂ】
【図１ｃ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図６ａ】
【図７】
【図７ａ】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３ａ】
【図１３ｂ】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図１ａ】
【図１ｂ】
【図１ｃ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図６ａ】
【図７】
【図７ａ】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３ａ】
【図１３ｂ】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【公表番号】特表２０１２−５３３０５６（Ｐ２０１２−５３３０５６Ａ）
【公表日】平成２４年１２月２０日（２０１２．１２．２０）
【国際特許分類】
【出願番号】特願２０１２−５１９０２２（Ｐ２０１２−５１９０２２）
【出願日】平成２２年７月９日（２０１０．７．９）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０５９９４７
【国際公開番号】ＷＯ２０１１／００４０２９
【国際公開日】平成２３年１月１３日（２０１１．１．１３）
【出願人】（３０７０４３２２３）トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【出願人】（５１２００６４５７）トムトム デベロップメント ジャーマニー ゲーエムベーハー (2)
【氏名又は名称原語表記】ＴｏｍＴｏｍ Ｄｅｖｅｌｏｐｍｅｎｔ Ｇｅｒｍａｎｙ ＧｍｂＨ
【住所又は居所原語表記】Ｍａｘｉｍｉｌｉａｎａｌｌｅｅ ４， ０４１２９ Ｌｅｉｐｚｉｇ Ｇｅｒｍａｎｙ
【Ｆターム（参考）】
【公表日】平成２４年１２月２０日（２０１２．１２．２０）
【国際特許分類】
【出願日】平成２２年７月９日（２０１０．７．９）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０５９９４７
【国際公開番号】ＷＯ２０１１／００４０２９
【国際公開日】平成２３年１月１３日（２０１１．１．１３）
【出願人】（３０７０４３２２３）トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【出願人】（５１２００６４５７）トムトム デベロップメント ジャーマニー ゲーエムベーハー (2)
【氏名又は名称原語表記】ＴｏｍＴｏｍ Ｄｅｖｅｌｏｐｍｅｎｔ Ｇｅｒｍａｎｙ ＧｍｂＨ
【住所又は居所原語表記】Ｍａｘｉｍｉｌｉａｎａｌｌｅｅ ４， ０４１２９ Ｌｅｉｐｚｉｇ Ｇｅｒｍａｎｙ
【Ｆターム（参考）】
[ Back to top ]