【手続補正書】
【提出日】平成23年4月28日(2011.4.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
目的地（２２；８２；１３２）までのルートを決定するための方法であって、
第１のステップにおいて、第１のグラフ（２０）に基づいて、複数の頂点（２３、２４、２５、２７、２８、３２、３３）に対する評価関数の値を決定することであって、頂点（２１〜３３）に対する評価関数の値は、該頂点（２１〜３３）から該目的地（２２；８２；１３２）までのルートに関連するコストの下限を表現している、ことと、
第２のステップにおいて、該第１のステップにおいて決定された該評価関数の値に基づいて、第２のグラフ（２０；２０’）上で、出発点（２１；８１；１３１）から該目的地（２２；８２；１３２）までのルート（６１）を検索することと
を包含し、
該第２のグラフの頂点（２１〜３３；１７１〜１７４；１７７、１７８）は、該第１のグラフの頂点（２１〜３３）またはエッジ（４１〜５５）に対応し、
該第２のステップにおいて該ルート（６１）を検索することは、該第１のステップにおいて所与の頂点（２９）に対する評価関数の値が決定されたかどうかを決定することを含み、該第１のステップにおいて評価関数の値が決定されていない場合には、該所与の頂点（２９）に対する評価関数の値を決定することを含む、方法。
【請求項２】
前記第１のステップにおいて、頂点（２１〜３３）に対する評価関数の値を決定することは、前記第１のグラフ（２０）上で該頂点（２１〜３３）から前記目的地（２２；８２；１３２）までのルートを検索することを含む、請求項１に記載の方法。
【請求項３】
前記頂点（２１〜３３）から前記目的地（２２）までの前記ルートを検索することは、前記第１のグラフ（２０）上でＤｉｊｋｓｔｒａアルゴリズムまたはＡ＊−アルゴリズムを用いて実行される、請求項２に記載の方法。
【請求項４】
前記第１のステップにおいて頂点（２１〜３３）に対する評価関数の値を決定することは、前記第１のグラフ上で、前記目的地（２２；８２；１３２）から出発して前記出発点（２１；８１；１３１）まで延長するルート検索を実行することを含む、請求項１〜請求項３のいずれか一項に記載の方法。
【請求項５】
前記第２のステップにおいて、前記評価関数の値に基づいて、前記目的地（２２；８２；１３２）までのルート（６１）とは異なる少なくとも１つのさらなるルート（１２１；１５１）を検索すること
を含む、請求項１〜請求項４のいずれか一項に記載の方法。
【請求項６】
前記少なくとも１つのさらなるルート（１２１；１５１）は、前記出発点（２１）から前記目的地（２２）までの代替ルート（１２１；１５１）、または別の出発点（１３５）から前記目的地（１３２）までのルートのうちの少なくとも１つを含む、請求項５に記載の方法。
【請求項７】
前記出発点（２１；１３１）から前記目的地（２２；１３２）までの前記ルート（６１）に対する現在の位置（１３５）をモニタリングすることであって、前記少なくとも１つのさらなるルートの前記検索は、該現在の位置（１３５）の該モニタリングの結果に基づいて自動的に開始される、こと
を含む、請求項５または請求項６に記載の方法。
【請求項８】
前記第２のグラフ（２０；２０’）の頂点（２１〜３３；１７１〜１７８）および／またはエッジ（４１〜４５；１８１〜１８５）に関連するコストの変化をモニタリングすることであって、前記少なくとも１つのさらなるルート（１２１；１５１）の前記検索は、該変化をモニタリングした結果に基づいて自動的に開始される、こと
を含む、請求項５〜請求項７のいずれか一項に記載の方法。
【請求項９】
前記第１のステップにおいて決定された前記評価関数の値の少なくともサブセット（５）を格納することと、
前記第２のステップにおいて該サブセット（５）の少なくとも１つの評価関数の値を抽出することと
を含む、請求項１〜請求項８のいずれか一項に記載の方法。
【請求項１０】
前記第１のステップにおける前記評価関数の値の前記決定は、第１のコストモデルに基づいており、前記第２のステップにおける前記出発点（２１；８１；１３１）から前記目的地（２２；８２；１３２）までの前記ルート（６１）の検索は、第２のコストモデルに基づいている、請求項１〜請求項９のいずれか一項に記載の方法。
【請求項１１】
前記第１のコストモデルにしたがう、前記第１のグラフ（２０）の前記頂点（２１〜３３）および／またはエッジ（４１〜５５）に関連するコストは、時間に関係しない、請求項１０に記載の方法。
【請求項１２】
前記第２のコストモデルにしたがう、前記第２のグラフ（２０；２０’）の頂点（２１〜３３；１７１〜１７８）および／またはエッジ（４１〜５５；１８１〜１８５）に関連するコストは可変である、請求項１０または請求項１１に記載の方法。
【請求項１３】
ユーザの選好度、交通情報信号、時刻または日付のうちの少なくとも１つに基づいて、前記第２のコストモデルにしたがう前記コストを調整すること
を含む、請求項１２に記載の方法。
【請求項１４】
前記調整することは、少なくとも１つの頂点（２１〜３３；１７１〜１７８）および／またはエッジ（４１〜５５；１８１〜１８５）に対し、前記第１のコストモデルに対して前記第２のコストモデルにしたがうコストを増加させることを含む、請求項１３に記載の方法。
【請求項１５】
前記第１のコストモデルにしたがう前記第１のグラフ（２０）の頂点（２１〜３３）および／またはエッジ（４１〜５５）に関連するコストは、前記第２のコストモデルにしたがう対応する頂点（２１〜３３；１７１〜１７８）および／またはエッジ（４１〜５５；１８１〜１８５）に関連するコストの下限を表現する、請求項１２〜請求項１４のいずれか一項に記載の方法。
【請求項１６】
前記第１のグラフ（２０）は、該第１のグラフ（２０）上のルート検索が、平均で、該第２のグラフ（２０’）上のルート検索よりも速くなるように定義される、請求項１〜請求項１５のいずれか一項に記載の方法。
【請求項１７】
前記第１のグラフ（２０）は、前記第２のグラフ（２０’）よりも少ない頂点（２１〜３３）を有している、請求項１〜請求項１６のいずれか一項に記載の方法。
【請求項１８】
前記第１のグラフの頂点は、前記道路網の道路セグメントを表現しており、前記第１のステップにおいて、該道路網上のターン制限は無視される、請求項１〜請求項１７のいずれか一項に記載の方法。
【請求項１９】
前記第１のステップにおいて、一方通行制限が考慮される、請求項１８に記載の方法。
【請求項２０】
前記第１のグラフ（２０）のエッジ（４１〜５５）は、道路網の道路セグメントを表現しており、前記第２のグラフ（２０’）の頂点（１７１〜１７８）は、該道路網の道路セグメントを表現している、請求項１〜請求項１７のいずれか一項に記載の方法。
【請求項２１】
前記第１のグラフ（２０）は、前記第２のグラフ（２０’）の双対グラフによって構成される、請求項２０に記載の方法。
【請求項２２】
前記第１のグラフ（２０）は、前記第２のグラフ（２０）と同じものである、請求項１〜請求項１５のいずれか一項に記載の方法。
【請求項２３】
前記第１のステップは、第３のグラフ（２０”）を定義すること、該第３のグラフ（２０”）上でルート検索を実行すること、および該第３のグラフ（２０”）上での該ルート検索の結果を利用して、前記複数の頂点（２３、２４、２５、２７、２８、３２、３３）に対する評価関数を決定することを含む、請求項１〜請求項２２のいずれか一項に記載の方法。
【請求項２４】
前記第１のステップにおいて頂点（２３、２４、２５、２７、２８、３２、３３）に対する評価関数の値を決定することは、前記第１のグラフ（２０）上で予め計算された情報に基づいて、該第１のグラフ（２０）上で該頂点（２３、２４、２５、２７、２８、３２、３３）から前記目的地（２２）までのルートを検索することを含む、請求項１〜請求項２３のいずれか一項に記載の方法。
【請求項２５】
前記第１のグラフ（２０）および前記第２のグラフ（２０；２０’）は、道路網、コンピュータネットワーク、またはインフラストラクチャネットワークのうちの１つを表現する、請求項１〜請求項２４のいずれか一項に記載の方法。
【請求項２６】
前記方法は、車両上のナビゲーションシステム（１）によって実行される、請求項１〜請求項２５のいずれか一項に記載の方法。
【請求項２７】
目的地（２２；８２；１３２）までのルートを決定するためのデバイスであって、
グラフデータ（４）を格納する格納ユニット（３）であって、該グラフデータ（４）は、第１のグラフ（２０）および第２のグラフ（２０；２０’）のうちの少なくとも１つの頂点（２１〜３３）およびエッジ（４１〜５５）を定義する、格納ユニット（３）と、
該格納ユニット（３）に接続されたプロセッサ（２）であって、該プロセッサ（２）は、該グラフデータ（４）を抽出し、該プロセッサは、第１のステップにおいて、該第１のグラフ（２０）に基づいて、複数の頂点（２３、２４、２５，２７、２８，３２、３３）に対する評価関数の値を決定し、頂点（２１〜３３）に対する評価関数の値は、該頂点（２１〜３３）から該目的地（２２；８２；１３２）までのルートに関連するコストの下限を表現しており、該プロセッサは、第２のステップにおいて、該第１のステップにおいて決定された該評価関数の値に基づいて、第２のグラフ（２０；２０’）上で、出発点（２１；８１；１３１）から該目的地（２２；８２；１３２）までのルート検索を実行する、プロセッサ（２）と
を備え、
該第２のグラフの頂点（２１〜３３；１７１〜１７４；１７７、１７８）は、該第１のグラフの頂点（２１〜３３）またはエッジ（４１〜５５）に対応し、
該プロセッサは、該第２のステップにおいて該ルート検索を行うときに、該第１のステップにおいて所与の頂点（２９）に対する評価関数の値が決定されたかどうかを決定し、該第１のステップにおいて評価関数の値が決定されていない場合には、該所与の頂点（２９）に対する評価関数の値を決定する、デバイス。
【請求項２８】
前記プロセッサ（２）は、前記第１のグラフ（２０）上でルート検索を実行し、前記評価関数の値を決定する、請求項２７に記載のデバイス。
【請求項２９】
前記プロセッサ（２）は、前記目的地（２２；８２；１３２）から出発して前記出発点（２１；８１；１３１）まで延長するルート検索を実行し、前記評価関数の値を決定する、請求項２７または請求項２８に記載のデバイス。
【請求項３０】
前記第２のステップにおいて、前記プロセッサ（２）は、前記第１のステップにおいて決定された前記評価関数の値に基づいて、前記目的地（２２；８２；１３２）までの少なくとも１つのさらなるルート検索を実行する、請求項２７〜請求項２９のいずれか一項に記載のデバイス。
【請求項３１】
さらなる格納ユニット（３）を含み、前記プロセッサ（２）は、該さらなる格納ユニット（３）に接続されており、前記第１のステップにおいて決定された前記評価関数の値（５）を該さらなる格納ユニット（３）に格納し、前記第２のステップを実行するために該さらなる格納ユニット（３）から該評価関数の値（５）を抽出する、請求項２７〜請求項３０のいずれか一項に記載のデバイス。
【請求項３２】
前記プロセッサ（２）は、第１のコストモデルに基づいて、前記第１のステップにおいて前記評価関数の値を決定し、第２のコストモデルに基づいて、前記第２のステップにおいて前記出発点（２１；８１；１３１）から前記目的地（２２；８２；１３２）までのルート検索を実行する、請求項２７〜請求項３１のいずれか一項に記載のデバイス。
【請求項３３】
前記第１のコストモデルにしたがう、前記第１のグラフ（２０）の前記頂点（２１〜３３）および／またはエッジ（４１〜５５）に関連するコストは時間に関係せず、前記第２のコストモデルにしたがう、前記第２のグラフ（２０；２０’）の頂点（２１〜３３；１７１〜１７８）および／またはエッジ（４１〜５５；１８１〜１８５）に関連するコストは可変である、請求項３２に記載のデバイス。
【請求項３４】
前記第１のコストモデルにしたがう、前記第１のグラフ（２０）の前記頂点（２１〜３３）および／またはエッジ（４１〜５５）に関連するコストは、前記第２のコストモデルにしたがう、前記第２のグラフ（２０；２０’）の対応する頂点（２１〜３３；１７１〜１７８）および／またはエッジ（４１〜５５；１８１〜１８５）に関連するコストの下限を表現する、請求項３２または請求項３３に記載のデバイス。
【請求項３５】
ユーザ入力を受信する入力ユニット（６）を含み、前記プロセッサ（２）は、該入力ユニット（６）に接続されており、該ユーザ入力に基づいて、前記第２のコストモデルのコストを調整する、請求項３２〜請求項３４のいずれか一項に記載のデバイス。
【請求項３６】
時刻および／または日付を決定するクロックユニット（１０）を含み、前記プロセッサ（２）は、該クロックユニット（１０）に接続されており、該時刻および／または日付に基づいて、前記第２のコストモデルのコストを調整する、請求項３２〜請求項３５のいずれか一項に記載のデバイス。
【請求項３７】
交通情報信号を受信する交通メッセージ受信器（９）を含み、前記プロセッサ（２）は、該交通メッセージ受信器（９）に接続されており、該交通情報信号に基づいて、前記第２のコストモデルのコストを調整する、請求項３２〜請求項３６のいずれか一項に記載のデバイス。
【請求項３８】
前記プロセッサ（２）は、少なくとも１つの頂点（２１〜３３；１７１〜１７８）および／またはエッジ（４１〜５５；１８１〜１８５）に対し、前記第１のコストモデルに対して前記第２のコストモデルのコストを増加させ、該第２のコストモデルのコストを調整する、請求項３５〜請求項３７のいずれか一項に記載のデバイス。
【請求項３９】
現在の車両の位置（１３５）を決定する位置決定手段（８）を含み、前記プロセッサ（２）は、該位置決定手段（８）に接続されており、該現在の車両の位置（１３５）を前記出発点（２１；８１；１３１）から前記目的地（２２；８２；１３２）までの前記ルート（６１）と比較し、該比較の結果に基づいて、前記第２のグラフ（２０；２０’）上での該現在の車両の位置（１３５）から該目的地（１３２）までのさらなるルート検索を実行する、請求項２７〜請求項３８のいずれか一項に記載のデバイス。
【請求項４０】
前記第１のグラフ（２０）は、該第１のグラフ（２０）上のルート検索が、平均で、該第２のグラフ（２０’）上のルート検索よりも速くなるように定義される、請求項２７〜請求項３９のいずれか一項に記載のデバイス。
【請求項４１】
前記決定されたルートは道路網上にある、請求項１〜２６のいずれか一項に記載の方法。
【請求項４２】
前記決定されたルートは道路網上にある、請求項２７〜４０のいずれか一項に記載のデバイス。
【請求項４３】
前記プロセッサ（２）は、請求項１〜請求項２６のいずれか一項に記載の方法を実行するように構成されている、請求項２７〜請求項４０および４２のいずれか一項に記載のデバイス。
【請求項４４】
ルートを決定する請求項２７〜請求項４０および４２のいずれか一項に記載のデバイスと、
該ルート上の情報を出力する出力ユニット（７）と
を含む、ナビゲーションシステム。
【請求項４５】
データ格納媒体であって、該データ格納媒体上に命令を有しており、該命令は、ナビゲーションシステム（１）のプロセッサ（２）によって実行されたときに、該ナビゲーションシステム（１）に、請求項１〜請求項２６のいずれか一項に記載の方法を実行するように命令する、データ格納媒体。