【手続補正書】
【提出日】平成22年5月10日(2010.5.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
道路網の出発点から目的地までのルートを決定する方法であって、
該方法は、該道路網の複数の頂点のための推定関数を使用し、
該推定関数は、該道路網の頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該方法は、
該道路網の少なくとも一部分が含まれる地域をカバーするタイリング（Ｔ）を定義するステップと、
該タイリングの各タイルの抵抗値を提供するステップと、
該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点（２３）に対して推定関数値を決定するステップと
を包含し、
所定のタイルの抵抗値は、該所定のタイルの境界に位置する該道路網の頂点を接続するルートに関連するコストを表し、該所定のタイルの境界に位置する頂点を接続するルートに関連するコストの下限が、該所定のタイルの抵抗値を使用して導出される、方法。
【請求項２】
前記所定のタイル（Ｔ０）の抵抗値が、該所定のタイルにおける前記道路網の幾何学的特性に関連して、該所定のタイルの境界に位置する頂点（ｔｂｖ１〜ｔｂｖ４）を接続するルート（１１、１３）に関連するコストを表す、ことを特徴とする、請求項１に記載の方法。
【請求項３】
前記所定のタイル（Ｔ０）の抵抗値が、該所定のタイルの境界に位置する一対の頂点（ｔｂｖ１〜ｔｂｖ４）を、一対の頂点のエアライン距離（１２、１４）に関連して接続する最適ルート（１１、１３）に関連する前記コストの下限であり、該ルートが該所定のタイルを横断する、ことを特徴とする、請求項１または２に記載の方法。
【請求項４】
前記所定のタイルの抵抗値と、該所定のタイル（Ｔ０）の境界に位置する任意の一対のテスト頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離（１２、１４）との積が、該所定のタイルの範囲内の該一対のテスト頂点を接続する最適ルート（１１、１３）に関連するコストの下限であるように、該所定のタイルの抵抗値が、該一対の頂点のエアライン距離によって分割される該所定のタイルの境界に位置する任意の一対の頂点を接続する該最適ルートに関連するコストの最小値である、ことを特徴とする、請求項３に記載の方法。
【請求項５】
前記タイル境界頂点（２３）に対して前記推定関数値を決定するステップが、
前記目的地（２２）を含む目的地タイル（Ｔ３）を決定するステップと、
該目的地タイル（Ｔ３）の境界に位置する少なくとも一つの目的地タイル境界頂点（２４、２５）と、該タイル境界頂点（２３）と、を接続する最適ルートに関連するコストの第１の下限を決定するステップと
をさらに包含する、ことを特徴とする、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
前記第１の下限が、前記タイルの前記抵抗値に応じて、または前記タイリングの複数のタイルの前記抵抗値に応じて、決定される、ことを特徴とする、請求項５に記載の方法。
【請求項７】
前記第１の下限が、タイル境界のみに位置する頂点（２３〜２５）を含む前記道路網のサブグラフに対して、ダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムまたはＡ＊−アルゴリズムを使用して決定される、ことを特徴とする、請求項６に記載の方法。
【請求項８】
任意のタイル（Ｔ２）の境界に位置する第１および第２の頂点（２３、２４）を接続するサブグラフのエッジ（２６ａ）に関連するコストが、該任意のタイルの抵抗値と、該第１および第２の頂点（２３、２４）のエアライン距離とから決定される、ことを特徴とする、請求項７に記載の方法。
【請求項９】
前記サブグラフのエッジ（２６ａ）に関連する前記コストが、前記第１および第２の頂点（２３、２４）のエアライン距離が乗算された前記任意のタイル（Ｔ２）の抵抗値に等しく設定される、ことを特徴とする、請求項８に記載の方法。
【請求項１０】
前記タイル境界頂点（２３）に対して前記推定関数を決定する前記ステップが、
前記目的地（２２）と、前記少なくとも一つの目的地タイル境界頂点（２４、２５）と、を接続する最適ルートに関連するコストの第２の下限を決定するステップと、
前記第１の下限と前記第２の下限とを加算するステップと
をさらに含む、ことを特徴とする、請求項５〜９のいずれか１項に記載の方法。
【請求項１１】
前記タイル境界頂点（２３）に対して前記推定関数値を決定する前記ステップが、
すべての目的地タイル境界頂点（２４、２５）にわたる前記第１の下限と前記第２の下限との合計の最小値を決定するステップをさらに含む、ことを特徴とする、請求項１０に記載の方法。
【請求項１２】
前記タイル（Ｔ２）の前記境界に位置するタイル境界頂点（２３、２４）のための推定関数値からの該タイル（Ｔ２）の内側に位置する内側頂点（２９）のための推定関数値と、該内側頂点（２９）と該タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの下限と、を決定する、ステップによって特徴付けられる、請求項１〜１１のいずれか１項に記載の方法。
【請求項１３】
前記内側頂点（２９）と前記タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの前記下限が、該内側頂点（２９）と該タイル境界頂点（２３、２４）とのエアライン距離から決定される、ことを特徴とする、請求項１２に記載の方法。
【請求項１４】
前記内側頂点（２９）と前記タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの前記下限が、該タイル境界頂点（２３、２４）が位置する前記タイルのエッジからの前記内側頂点の最小エアライン距離（２７’、２８’）から決定される、ことを特徴とする、請求項１２に記載の方法。
【請求項１５】
前記道路網の道路セグメントのコスト要因における増加を検出するステップと、
該コスト要因における検出された増加に応じて、該道路セグメントを含むタイルの抵抗値を増加させる、ステップとによって特徴づけられる、請求項１〜１４のいずれか１項に記載の方法。
【請求項１６】
前記道路セグメントを含む前記タイルの抵抗値を増加させることが、乗法による、ことを特徴とする、請求項１５に記載の方法。
【請求項１７】
前記道路セグメントの前記コスト要因が、ユーザ入力に依存して増加する、ことを特徴とする、請求項１５または１６に記載の方法。
【請求項１８】
交通メッセージ信号を自動的に受信し、前記道路セグメントの前記コスト要因が該受信された交通メッセージ信号に依存して増加する、ステップによって特徴づけられる、請求項１５〜１７のいずれか１項に記載の方法。
【請求項１９】
前記タイリング（Ｔ）のタイル（Ｔ１’、Ｔ２’、Ｔ１’’〜Ｔ６’’）のタイルサイズが、前記出発点と前記目的地からの増加する距離とともに増加する、ことを特徴とする、請求項１〜１８のいずれか１項に記載の方法。
【請求項２０】
第１の抵抗値が、第１の規則的なタイリング（Ｔ’）の各タイルに対して提供され、
第２の抵抗値が、第２の規則的なタイリング（Ｔ’’）の各タイルに対して提供され、
前記地域をカバーする前記タイリング（Ｔ）が、該第１の規則的なタイリング（Ｔ’）のタイル（Ｔ１’、Ｔ２’）と、第２の規則的なタイリング（Ｔ’’）のタイル（Ｔ１’’〜Ｔ６’’）とを含み、該タイリングのタイルの抵抗値が、対応する該第１および該第２の抵抗値とそれぞれ等しい、ことを特徴とする、請求項１９に記載の方法。
【請求項２１】
前記タイリング（Ｔ）の各タイルに対して、第１の基礎抵抗値および第２の基礎抵抗値が提供され、これらの抵抗値が第１および第２の基礎コストモデルをそれぞれ表し、該第１および第２の基礎コストモデルの線形な組み合わせとして形成されるコストモデルに対して、該抵抗値の下限が、該第１および第２の基礎抵抗値の線形な組み合わせによって決定される、ことを特徴とする、請求項１〜２０のいずれか１項に記載の方法。
【請求項２２】
前記出発点から前記目的地までの最適ルートが、前記タイリングのタイルの抵抗値に応じて決定される推定関数を使用するＡ＊−アルゴリズムを使用して決定される、ことを特徴とする、請求項１〜２１のいずれか１項に記載の方法。
【請求項２３】
グラフ上の出発点から目的地までのルートを決定する方法であって、
該方法は、該グラフの複数の頂点のための推定関数を使用し、
該推定関数は、該グラフの頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該方法は、
地域をカバーするタイリング（Ｔ）を定義するステップであって、該グラフの少なくとも一部分が含まれる、ステップと、
該タイリングの各タイルに対して抵抗値を提供するステップと、
該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点（２３）に対して推定関数を決定するステップと
を含み、
所定のタイルの抵抗値は、該所定のタイルの境界に位置する該グラフの頂点を接続するルートに関連するコストを表し、該所定のタイルの該境界に位置する頂点を接続するルートに関連するコストの下限が該所定のタイルの抵抗値に基づいて導出される、方法。
【請求項２４】
道路網データを前処理する方法であって、
地域をカバーするタイリング（Ｔ）を定義するステップであって、該道路網の少なくとも一部分が含まれる、ステップと、
該タイリングのタイル（Ｔ０）に対して、該タイルの境界に位置する頂点（ｔｂｖ１〜ｔｂｖ４）を決定するステップと、
任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離によって分割される該タイルの境界に位置する該一対の頂点を接続する最適ルート（１１、１３）に関連するコストの下限を決定するステップと、
該決定された下限を出力するステップと
を含む、方法。
【請求項２５】
前記下限が、任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）の前記エアライン距離によって分割される前記タイルの境界に位置する該一対の頂点を接続するルートに関連する前記コストの最小値から決定される、ことを特徴とする、請求項２４に記載の方法。
【請求項２６】
前記決定された下限が、出力の前に離散化される、ことを特徴とする、請求項２４または２５に記載の方法。
【請求項２７】
道路網の出発点から目的地までのルートを決定するシステムであって、
該システムは、該道路網の複数の頂点のための推定関数を使用し、
該推定関数は、該道路網の頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該システムは、
道路網データを含む第１の格納ユニット（３）と、
タイリングを定義するタイリング定義データと、各タイルの抵抗値と、を含む第２の格納ユニット（４）と、
該タイリングの該タイルの該抵抗値に応じて、タイル境界に位置するタイル境界頂点のための推定関数を決定するように適合される処理ユニット（２）と
を備え、
該第２の格納ユニット（４）に含まれる、所定のタイルの該抵抗値は、該所定のタイルの境界に位置する該道路網の頂点を接続するルートに関連するコストを表し、該処理ユニット（２）は、該所定のタイルの該境界に位置する頂点を接続する該ルートに関連するコストの下限を、該所定のタイルの該抵抗値を使用して導出するように適合される、システム。
【請求項２８】
前記第２の格納ユニット（４）に含まれる、前記所定のタイル（Ｔ０）の前記抵抗値が、該所定のタイルの前記境界に位置する任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）を、一対の頂点のエアライン距離（１２、１４）に関連して接続する最適ルート（１１、１３）に関連する前記コストの下限であり、該ルートが該所定のタイルを横断する、ことを特徴とする、請求項２７に記載のシステム。
【請求項２９】
前記第２の格納ユニット（４）に含まれる、前記所定のタイルの抵抗値と、該所定のタイル（Ｔ０）の境界に位置する任意の一対のテスト頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離（１２、１４）との積が、該所定のタイルの範囲内の該一対のテスト頂点を接続する最適ルート（１１、１３）に関連するコストの下限であるように、該所定のタイルの抵抗値が、該一対の頂点のエアライン距離によって分割される該所定のタイルの境界に位置する任意の一対の頂点を接続する該最適ルートに関連する前記コストの最小値である、ことを特徴とする、請求項２７または２８に記載のシステム。
【請求項３０】
前記処理ユニット（２）が、前記目的地（２２）を含む目的地タイル（Ｔ３）の境界に位置する少なくとも一つの目的地タイル境界頂点（２４、２５）を決定し、前記タイル境界頂点（２３）と該少なくとも一つの目的地タイル境界頂点（２４、２５）とを接続する最適ルートに関連するコストの下限を計算し、該下限が前記タイリングのタイルの抵抗値に応じて決定される、ことを特徴とする、請求項２７〜２９のいずれか１項に記載のシステム。
【請求項３１】
前記下限が、前記目的地タイル境界頂点（２４、２５）を原点として有するダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムまたはＡ＊−アルゴリズムを使用して計算される、ことを特徴とする、請求項３０に記載のシステム。
【請求項３２】
前記タイル境界頂点（２３）の座標と、前記処理ユニット（２）によって決定される該タイル境界頂点（２３）のための前記推定関数値と、を格納するメモリユニット（５）、によって特徴づけられる、請求項２７〜３１のいずれか１項に記載のシステム。
【請求項３３】
前記メモリユニット（５）が、前記タイルの境界によって規定される線に沿った前記タイル境界頂点（２３）の位置を指定する一次元的座標の形式において、該タイル境界頂点の該座標を格納する、ことを特徴とする、請求項３２に記載のシステム。
【請求項３４】
前記処理ユニット（２）が、前記道路網の道路セグメントのための交通メッセージ信号を受信し、該受信された交通メッセージ信号に応じて、該道路セグメントを含むタイルの抵抗値を変更する、ことを特徴とする、請求項２７〜３３のいずれか１項に記載のシステム。
【請求項３５】
前記処理ユニット（２）が、前記タイリングのタイルの前記抵抗値に応じて決定されて前記メモリユニット（５）に格納された推定関数値を使用するＡ＊−アルゴリズムを使用して、前記出発点から前記目的地までの最適ルートを決定する、ことを特徴とする、請求項２７〜３４のいずれか１項に記載のシステム。
【請求項３６】
前記システムが、請求項１〜２３のいずれか１項に記載の方法を実行する、ことを特徴とする、請求項２７〜３５のいずれか１項に記載のシステム。
【請求項３７】
ナビゲーションシステムであって、
目的地を入力する入力手段（６）と、
決定されたルートを出力する出力手段（７）と、
請求項２７〜３６のいずれか１項に記載のルートを決定するシステム（２〜５）とを備え、
該システムは、そこから該目的地を受信する該入力手段（６）と、そこへ決定されたルートを出力する出力手段（７）とに結合されている、ナビゲーションシステム。
【請求項３８】
現在の車両位置を決定する位置決定手段（８）を備え、該位置決定手段（８）は、前記ルートを決定するシステム（２〜５）に結合され、該現在の車両位置を前記出発点として提供する、請求項３７に記載のナビゲーションシステム。
【請求項３９】
前記位置決定手段（８）が、ＧＰＳ受信機を備える、ことを特徴とする、請求項３８に記載のナビゲーションシステム。
【請求項４０】
交通メッセージ信号を提供する前記処理ユニット（２）に結合されたＴＭＣ受信機（９）、ことを特徴とする、請求項３７〜３９のいずれか１項に記載のナビゲーションシステム。