JP6657582B2 - 経路探索システム、方法およびプログラム - Google Patents

Description

本発明は、経路探索システム、経路探索方法およびプログラムに関する。

従来、経路探索システムにおいては、道路に階層が対応づけられた状態で地図情報が定義され、出発地と目的地付近では下位階層の道路を探索対象として詳細な経路を探索し、経路の中間地域では上位階層の道路を探索対象とし、下位階層の道路を探索対象とせずに経路を探索し、探索された経路を統合する処理が一般的に採用されている（例えば、特許文献１参照）。

特開２００９−１５６９４０号公報

上述した従来技術においては、探索された経路が地図に表示されない場合や、探索された経路のみが地図に表示され当該経路が通っている道路は表示されない場合があった。すなわち、一般的に、経路探索システムにおいては、探索された経路が地図上で示されるが、当該地図においては、地図の縮尺によって表示対象の道路が異なる。例えば、通常の縮尺の地図では細街路が表示されず、より詳細な地図を表示するように縮尺が変更された場合に細街路が表示される等のように、表示対象の道路が地図の縮尺に応じて変化する。従って、地図に表示された道路を考慮することなく経路を探索すると、表示対象ではない道路を含む経路が探索され得る。この場合、表示中の地図に経路や道路の一部が表示されない。
本発明は、前記課題にかんがみてなされたもので、視認性の高い経路を探索し表示することが可能な技術を提供することを目的とする。

上記の目的を達成するため、経路探索システムは、出発地と目的地とを取得する探索条件取得手段と、地図の縮尺毎に表示対象となる表示対象道路が決められた地図情報を記憶する記憶部と、地図情報と表示部に表示する地図の縮尺に基づいて表示対象道路を特定し、特定された表示対象道路からなる地図を表示部に表示する地図表示手段と、表示部に表示されている地図上の表示対象道路を探索対象とし、地図上の表示対象道路ではない道路を探索対象から除外して出発地から目的地までの経路を探索する経路探索手段と、探索された経路を地図上に表示する経路表示手段と、を備える。

また、上記の目的を達成するため、経路探索方法は、出発地と目的地とを取得する探索条件取得工程と、地図の縮尺毎に表示対象となる表示対象道路が決められた地図情報と表示部に表示する地図の縮尺に基づいて表示対象道路を特定し、特定された表示対象道路からなる地図を表示部に表示する地図表示工程と、表示部に表示されている地図上の表示対象道路を探索対象とし、地図上の表示対象道路ではない道路を探索対象から除外して出発地から目的地までの経路を探索する経路探索工程と、探索された経路を地図上に表示する経路表示工程と、を含むように構成される。

さらに、上記の目的を達成するため、経路探索プログラムは、出発地と目的地とを取得する探索条件取得機能と、地図の縮尺毎に表示対象となる表示対象道路が決められた地図情報と表示部に表示する地図の縮尺に基づいて表示対象道路を特定し、特定された表示対象道路からなる地図を表示部に表示する地図表示機能と、表示部に表示されている地図上の表示対象道路を探索対象とし、地図上の表示対象道路ではない道路を探索対象から除外して出発地から目的地までの経路を探索する経路探索機能と、探索された経路を地図上に表示する経路表示機能と、をコンピュータに実現させる。

以上のように、経路探索システム、方法、プログラムにおいては、地図上に表示されている表示対象道路を探索対象とし、地図上に表示されていない道路を探索対象から除外して経路を探索し、探索された経路を地図上に表示する。従って、地図上に表示されていない道路が経路となることが防止され、視認性の高い経路を探索し、表示することが可能である。

経路探索システムの構成を示すブロック図である。 通過道路を指定する経路探索処理を示すフローチャートである。 （３Ａ）（３Ｂ）は出発地、目的地および経路を模式的に示す図である。

ここでは、下記の順序に従って本発明の実施の形態について説明する。
（１）経路探索システムの構成：
（２）通過道路を指定する経路探索処理：
（３）他の実施形態：

（１）経路探索システムの構成：
図１は、本発明の一実施形態である経路探索システムとして機能するナビゲーションシステム１０の構成を示すブロック図である。ナビゲーションシステム１０は、ＣＰＵ、ＲＡＭ、ＲＯＭ等を備える制御部２０を備えており、制御部２０は、当該ＲＯＭや記録部３０に記録された種々のプログラムを実行することができる。本実施形態においては、このプログラムの一つとして経路探索プログラム２１を実行可能である。

制御部２０は、経路探索プログラム２１の処理により、現在地を出発し、目的地まで到達するための経路を探索することが可能である。また、制御部２０は、経路探索プログラムの処理により、ナビゲーションシステム１０を備えた車両を経路に沿って誘導する案内を実行することができる。

記録部３０には地図情報３０ａが予め記録されている。地図情報３０ａは、道路区間の端点に対応するノードの位置、ノード間の道路の形状を特定するための形状補間点の位置等を示す形状補間点データ、ノード同士の連結を示すリンクデータ、施設の位置および属性を示す施設データ等を含んでいる。施設の属性は種々の定義が可能であり、本実施形態においては、名称、施設の種類等が属性として定義され、対応づけられている。なお、本実施形態において、リンクデータには、道路区間毎のコストのデフォルト値を示す情報が対応づけられており、各道路区間の道路種別（例えば、高速道路、一般道、細街路等）を示す情報が対応づけられている。さらに、リンクデータには、各リンクデータが示す道路区間が表示対象道路となる地図の縮尺を示す情報が対応づけられている。

なお、地図情報３０ａにおいて、道路上のノードには階層を示す情報が対応付けられている。すなわち、地図情報３０ａにおいては、仮想的に複数の階層が設定され、各階層上でノードの位置が定義され、各階層上のノード同士のリンク情報に基づいて階層毎に道路を再現することが可能である。また、各階層においては、その順位が定義されており、上位階層であるほどノードの密度（単位面積当たりのノード数）が小さくなるように定義されている。すなわち、特定の例外を除いて一般的には、ノードの密度が大きい下位階層においては当該階層より上位の階層と比較して、道路上において短い間隔でノードが設定される。従って、上位の階層であるほどそのノードによって区切られる道路区間は長い。さらに、本実施形態においては、上位階層であるほど重要（幅が広い、交通量が多いなど）な地点（例えば、主要道路同士の交差点等）にノードが設定されている。

ナビゲーションシステム１０は、ユーザＩ／Ｆ部４０とＧＰＳ受信部４１と車速センサ４２とジャイロセンサ４３とを備えている。ユーザＩ／Ｆ部４０は、利用者の指示を入力し、また利用者に各種の情報を提供するためのインタフェース部であり、図示しないタッチパネルディスプレイからなる入力部を兼ねた表示部やスピーカー等の出力音の出力部を備えている。

ＧＰＳ受信部４１は、ＧＰＳ衛星からの電波を受信し、図示しないインタフェースを介して車両の現在地を算出するための信号を出力する。車速センサ４２は、車両が備える車輪の回転速度に対応した信号を出力する。制御部２０は、図示しないインタフェースを介してこの信号を取得し、車速を取得する。ジャイロセンサ４３は、車両の水平面内の旋回についての角加速度を検出し、車両の向きに対応した信号を出力する。制御部２０は、この信号を取得して車両の進行方向を取得する。制御部２０は、車速センサ４２およびジャイロセンサ４３等の出力信号に基づいて車両の走行軌跡を特定することで車両の現在地を取得する。ＧＰＳ受信部４１の出力信号は、車速センサ４２およびジャイロセンサ４３等から特定される車両の現在地を補正するなどのために利用される。

本実施形態における経路探索プログラム２１は、現在地から利用者が指定した目的地までの経路を探索する機能を制御部２０に実現させる。本実施形態における探索は２種類の態様で実施可能である。すなわち、制御部２０は、地図情報３０ａに定義された道路区間毎のコストに基づいて、ダイクストラ法等によって現在地から目的地までの間の経路を探索することが可能である。当該探索は、経路が未設定の場面等で主に行われる（以下この態様を第１態様と呼ぶ）。

一方、経路が設定済の状態において、制御部２０は、ユーザＩ／Ｆ部４０の表示部に地図を表示する。この状態において、利用者が表示部上の道路をタッチした場合に、制御部２０は、当該道路を通過道路として取得し、通過道路を通過する経路となるように既存の経路を修正する探索を行う（以下、この態様を第２態様と呼ぶ）。当該第２態様において、表示部に表示されていない道路が経路探索対象となり、結果として経路となると、表示されていない道路が経路となるために、利用者に対して強い違和感を与える。そこで、本実施形態においては、探索対象となる道路を表示対象道路に限定している。

このような探索を実行するため、経路探索プログラム２１は、探索条件取得部２１ａと地図表示部２１ｂと経路探索部２１ｃと経路表示部２１ｄとを備えている。探索条件取得部２１ａは、経路探索条件を取得する機能を制御部２０に実現させるプログラムモジュールである。すなわち、制御部２０は、探索条件取得部２１ａの処理により、少なくとも出発地と目的地とを取得する。具体的には、制御部２０は、ＧＰＳ受信部４１，車速センサ４２，ジャイロセンサ４３の出力信号に基づいて車両の現在地を取得し、当該現在地を出発地として取得する。また、制御部２０は、ユーザＩ／Ｆ部４０の出力信号に基づいて利用者が指定した目的地を取得する。

さらに、第２態様の探索が行われる際に、制御部２０は、探索条件取得部２１ａの処理により、通過道路を探索条件として取得することが可能である。すなわち、利用者がユーザＩ／Ｆ部４０の表示部をタッチした場合、ユーザＩ／Ｆ部４０はタッチされた位置を示す信号を出力する。制御部２０は、当該信号と、ユーザＩ／Ｆ部４０の表示部に表示した地図上の道路の座標とに基づいて、利用者がタッチした道路を特定し、当該道路を通過道路として取得する。

地図表示部２１ｂは、地図情報３０ａと表示部に表示する地図の縮尺に基づいて表示対象道路を特定し、特定された表示対象道路からなる地図を表示部に表示する機能を制御部２０に実現させるプログラムモジュールである。本実施形態においては、利用者によって目的地が設定されると、制御部２０は、地図表示部２１ｂの処理により、出発地と目的地と経路とが表示部に表示される縮尺で地図を表示部に表示する。すなわち、表示部の大きさは予め決められているため、制御部２０は、地図情報３０ａを参照し、１画面上に出発地、目的地および経路が表示される状態となるように地図を表示するための縮尺を特定する。このような縮尺の特定は、例えば、制御部２０が複数段階の縮尺で地図を表示可能であるとともに、出発地、目的地および経路の構成道路が表示部の画面（地図表示領域）に含まれる縮尺であって、出発地および目的地の直線距離が最も大きくなる縮尺を特定する処理等によって実現可能である。

表示部に表示される地図の縮尺が特定されると、制御部２０は、地図表示部２１ｂの処理により、当該縮尺の地図を表示部に表示する。すなわち、制御部２０は、地図情報３０ａを参照し、当該縮尺に対応づけられた表示対象道路を特定する。さらに、制御部２０は、地図情報３０ａに基づいて、当該表示対象道路で道路ネットワークが構成された地図を示す画像を生成し、当該画像を表示するための制御信号をユーザＩ／Ｆ部４０の表示部に出力する。この結果、ユーザＩ／Ｆ部４０の表示部には、出発地と目的地と経路が表示部に含まれる縮尺の地図が表示される。そして、表示部に表示された当該地図には、当該縮尺に対応づけられた表示対象道路が含まれているが、当該縮尺に対応づけられていない道路は含まれていない。

経路探索部２１ｃは、出発地（本実施形態においては車両の現在地）から目的地までの経路を探索する機能を制御部２０に実現させるプログラムモジュールである。すなわち、制御部２０は、経路探索部２１ｃの処理により、第１態様および第２態様で経路を探索することができる。制御部２０は、利用者がユーザＩ／Ｆ部４０によって目的地を指定すると、地図情報３０ａを参照して道路ネットワークおよび各道路区間のコストを特定し、ダイクストラ法等によって出発地から目的地までの経路を探索する。すなわち、制御部２０は、第１態様による探索を実行する。

経路表示部２１ｄは、探索された経路を表示部に表示された地図上に表示する機能を制御部２０に実現させるプログラムモジュールである。すなわち、制御部２０は、経路表示部２１ｄの処理により、ユーザＩ／Ｆ部４０の表示部に対して制御信号を出力し、経路の道路に経路を示す線の画像を表示させる。

図３Ａは、ユーザＩ／Ｆ部４０の表示部に表示される地図および経路を模式的に示す図である。図３Ａにおいては、出発地をＳ、目的地をＧとして示しており、道路を直線によって示している。本実施形態においては、上述のように出発地と目的地と経路が１画面上に表示され、図３Ａに示す例においては、出発地Ｓと目的地Ｇとが表示部の縁の近傍に配置された状態で地図が表示される。さらに、図３Ａにおいては、細い直線によって表示対象道路を示し、太い直線によって経路を示している。また、図３Ａに示す例においては破線によって表示対象ではない道路を示しており、破線で示す道路は実空間上に存在するものの、図３Ａに示す縮尺の地図上には表示されない。

このように、出発地、目的地および経路が１画面上に表示された状態において、利用者が、地図上の表示対象道路をタッチすることによって通過道路を指定した場合、制御部２０は、第２態様の探索を行う。すなわち、制御部２０は、表示部に表示されている地図上の表示対象道路を探索対象とし、地図上の表示対象道路ではない道路を探索対象から除外して出発地から目的地までの経路を探索する。さらに、この際、制御部２０は、出発地から目的地までの経路が、通過道路を通過する経路となるように経路探索を行う。

すなわち、制御部２０は、ユーザＩ／Ｆ部４０の表示部に表示中の地図の縮尺を取得し、地図情報３０ａに基づいて当該縮尺における表示対象道路を特定する。そして、制御部２０は、地図情報３０ａに基づいて当該表示対象道路のコストを特定し、表示対象道路ではない道路のコストを表示対象道路と比較して極端に大きい値のコストに設定する。当該極端に大きい値のコストは、表示対象道路ではない道路が実質的に選択されなくなる程度の大きさであれば良い。この結果、制御部２０は、表示対象道路を探索対象とし、表示対象道路ではない道路を探索対象から除外する。

そして、制御部２０は、得られたコストに基づいて出発地から通過道路までの経路を探索し、通過道路から目的地までの経路を探索し、結合することによって出発地から目的地までの経路を探索する。図３Ｂは、図３Ａに示す例において、通過道路が指定された場合の例を示す図である。図３Ｂにおいては、道路Ｒ₁が指でタッチされたことが模式的に示されており、図３Ａに示す状態において、図３Ｂに示すように道路Ｒ₁がタッチされると、当該道路Ｒ₁が通過道路に指定される。このように通過道路が指定された状態で制御部２０が経路を探索すると、道路Ｒ₁を通過する経路であって、表示対象道路から構成された経路が取得される。

経路が探索されると、制御部２０は、経路表示部２１ｄの処理により、探索された経路を表示部に表示させる。この結果、図３Ｂに示すように道路Ｒ₁を通過する経路が探索される。また、当該経路の探索の際に、表示対象道路ではない道路は探索対象から除外されているので、図３Ｂにおいて破線で示す表示されていない道路は経路とならない。従って、表示されていない道路が経路になることはなく、利用者に対して強い違和感を与えることはない。

また、利用者が存在を表示部上で確認できない道路が経路に含まれることはなく、探索された経路を利用者が表示部の地図上で確認できるように、経路を探索することができる。さらに、本実施形態によれば、一画面に出発地と目的地（および経路）とが表示されている状態において、表示されている道路を使用して探索および探索結果の表示を行うことができる。さらに、以上の構成によれば、地図上に表示されていない道路が経路となることが防止され、視認性の高い経路を探索し、表示することが可能である。

（２）通過道路を指定する経路探索処理：
次に、通過道路を指定する経路探索処理について詳細に説明する。図２は、通過道路を指定する経路探索処理のフローチャートである。制御部２０は、ユーザＩ／Ｆ部４０の入力部によって利用者が目的地を指定した後に、第１態様の経路探索を開始するとともに、図２に示す処理を開始する。図２示す経路探索処理において、制御部２０は、地図表示部２１ｂの処理により、経路が存在するか否かを判定する（ステップＳ１００）。すなわち、第１態様または第２態様によって経路の探索が完了した後、消去されていない場合（例えば、経路の目的地に到達すると経路が消去される構成において、目的地に未達である場合）、当該経路を示す情報がＲＡＭに記憶されており、この状態であれば制御部２０は、経路が存在すると見なす。

ステップＳ１００において、経路が存在すると判定された場合、制御部２０は、地図表示部２１ｂの処理により、現在地、目的地、経路を画面表示可能な地図の縮尺を取得する（ステップＳ１０５）。すなわち、制御部２０は、地図表示部２１ｂの処理により、ＧＰＳ受信部４１，車速センサ４２，ジャイロセンサ４３の出力信号に基づいて車両の現在地を取得し、当該現在地を出発地とみなす。

また、制御部２０は、利用者がユーザＩ／Ｆ部４０によって指定した目的地を取得する。さらに、制御部２０は、探索済の経路を示す情報をＲＡＭから取得する。そして、制御部２０は、出発地、目的地および経路の構成道路が表示部の画面（地図表示領域）に含まれる縮尺であって、出発地および目的地の直線距離が最も大きくなる縮尺を特定し、当該縮尺を、現在地、目的地、経路を画面表示可能な地図の縮尺として取得する。

ステップＳ１００において、経路が存在すると判定されない場合（例えば、初期段階で経路探索が完了していない場合や経路が消去されている場合等）、制御部２０は、地図表示部２１ｂの処理により、現在地、目的地を画面表示可能な地図の縮尺を取得する（ステップＳ１１０）。すなわち、制御部２０は、地図表示部２１ｂの処理により、ＧＰＳ受信部４１，車速センサ４２，ジャイロセンサ４３の出力信号に基づいて車両の現在地を取得し、当該現在地を出発地とみなす。また、制御部２０は、利用者がユーザＩ／Ｆ部４０によって指定した目的地を取得する。そして、制御部２０は、出発地、目的地が表示部の画面（地図表示領域）に含まれる縮尺であって、出発地および目的地の直線距離が最も大きくなる縮尺を特定し、当該縮尺を、現在地、目的地を画面表示可能な地図の縮尺として取得する。

次に、制御部２０は、地図表示部２１ｂの処理により、表示対象道路を特定し、地図を表示する（ステップＳ１１５）。すなわち、制御部２０は、地図情報３０ａを参照し、ステップＳ１０５またはＳ１１０で取得した縮尺の地図に対応づけられた表示対象道路を特定する。また、制御部２０は、地図情報３０ａを参照し、ステップＳ１０５またはＳ１１０で取得された縮尺の地図において、出発地および目的地が表示部上で同時に表示されるように、地図の描画範囲を設定する。さらに、制御部２０は、当該描画範囲において表示対象道路で構成される道路ネットワークと道路周辺の地物等を含む地図の画像を生成する。そして、制御部２０は、当該地図の画像を表示させるための制御信号をユーザＩ／Ｆ部４０の表示部に対して出力する。この結果、表示部には、ステップＳ１０５またはＳ１１０で取得された縮尺の地図が表示される。また、出発地および目的地が同時に地図に表示された状態となる。

なお、ステップＳ１０５が実行された場合、制御部２０は、経路表示部２１ｄの処理により、地図上に経路を表示する。すなわち、制御部２０は、地図情報３０ａに基づいて経路となった道路区間の地図上での位置を特定し、当該道路区間が経路であることを示す情報を地図に重畳するための画像を生成する。そして、制御部２０は、当該経路を示す情報を表示させるための制御信号をユーザＩ／Ｆ部４０の表示部に対して出力する。この結果、表示部には、経路を示す情報が表示された状態となる。

次に、制御部２０は、探索条件取得部２１ａの処理により、通過道路が指定されたか否かを判定する（ステップＳ１２０）。すなわち、制御部２０は、ユーザＩ／Ｆ部４０の表示部が出力する信号に基づいて、タッチパネルディスプレイとしての表示部がタッチされたか否かを監視する。表示部がタッチされた場合、制御部２０は、地図情報３０ａを参照し、タッチされた位置と表示対象道路の表示位置とを比較し、表示対象道路の表示位置がタッチされた場合に、当該表示対象道路が通過道路として指定されたと見なす。

ステップＳ１２０において、通過道路が指定されたと判定されない場合、制御部２０は、ステップＳ１００以降の処理を繰り返す。一方、ステップＳ１２０において、通過道路が指定されたと判定された場合、制御部２０は、経路探索部２１ｃの処理により、コスト設定対象リンクを特定する（ステップＳ１２５）。すなわち、ステップＳ１２５〜Ｓ１５５において、制御部２０は、探索対象となる道路区間に標準的な値のコストを設定し、探索対象とならない道路区間には極端に大きい値のコストを設定することにより、探索対象を限定するための処理を行う。このために、ステップＳ１２５においては、現在地の前方に存在する道路区間の中の１個をコスト設定対象リンクとしてコストを設定するための処理を行う。コスト設定対象リンクの決定法は、種々の手法を採用可能であり、例えば、ダイクストラ法等に従ってコスト設定対象のリンクを決定すれば良い。なお、ステップＳ１２０において、通過道路が指定されたと判定された段階において、制御部２０が並行して経路探索を実行している場合（例えば、経路探索完了待ちでステップＳ１１０が行われた場合）、制御部２０は、並行して実行されている経路探索を終了させる。

次に、制御部２０は、経路探索部２１ｃの処理により、コスト設定対象リンクが探索対象階層以上の階層に属するか否かを判定する（ステップＳ１３０）。本実施形態においては、道路の端点を構成するノードが複数の階層のいずれかに属するように定義されており、出発地および目的地の周辺領域を除く中間領域において、制御部２０が、周辺領域よりも上位階層に属する道路を探索対象の道路として経路を探索することにより、経路探索の高速化を実現している。すなわち、制御部２０は、出発地および目的地の周辺領域と中間領域と探索対象となる道路が属する階層が異なる。

具体的には、制御部２０は、中間領域においては特定の階層以上の階層に属する道路のみを探索対象とし、周辺領域においては全ての階層に属する道路を探索対象として経路を探索する。従って、コスト設定対象リンクが中間領域内に存在する場合、制御部２０は、コスト設定対象リンクが上述の特定の階層以上の階層に属していれば、コスト設定対象リンクが探索対象階層以上の階層に属すると判定する。コスト設定対象リンクが上述の特定の階層より下位の階層に属していれば、制御部２０は、コスト設定対象リンクが探索対象階層以上の階層に属すると判定しない。

コスト設定対象リンクが周辺領域内に存在する場合、制御部２０は、コスト設定対象リンクが探索対象階層以上の階層に属すると判定する。なお、周辺領域は種々の手法で定義可能であり、本実施形態においては、出発地および目的地から地図上の表示対象道路に至るまでの区間が周辺領域となる。ステップＳ１３０において、コスト設定対象リンクが探索対象階層以上の階層に属すると判定されない場合、制御部２０は、経路探索部２１ｃの処理により、コスト設定対象リンクに極端に大きい値のコストを設定する（ステップＳ１５０）。すなわち、制御部２０は、コスト設定対象リンクを探索対象から除外する。

一方、ステップＳ１３０において、コスト設定対象リンクが探索対象階層以上の階層に属すると判定された場合、制御部２０は、地図情報３０ａを参照し、コスト設定対象リンクが中間領域に属するか否かを判定する（ステップＳ１３５）。ステップＳ１３５において、コスト設定対象リンクが中間領域に属すると判定されない場合、制御部２０は、経路探索部２１ｃの処理により、コスト設定対象リンクに標準的な値（地図情報３０ａに定義された値）のコストを設定する（ステップＳ１４５）。すなわち、制御部２０は、コスト設定対象リンクを探索対象とする。

一方、ステップＳ１３５において、コスト設定対象リンクが中間領域に属すると判定された場合、制御部２０は、経路探索部２１ｃの処理により、コスト設定対象リンクが表示対象道路であるか否かを判定する（ステップＳ１４０）。すなわち、制御部２０は、地図情報３０ａを参照し、コスト設定対象リンクがステップＳ１０５またはＳ１１０で取得された縮尺における表示対象道路であるか否かを判定する。

ステップＳ１４０において、コスト設定対象リンクが表示対象道路であると判定された場合、制御部２０は、ステップＳ１４５によってコスト設定対象リンクを探索対象に設定する。一方、ステップＳ１４０において、コスト設定対象リンクが表示対象道路であると判定されない場合、制御部２０は、ステップＳ１５０によってコスト設定対象リンクを探索対象から除外する。そして、制御部２０は、コスト設定終了条件が充足されたか否かを判定し（ステップＳ１５５）、コスト設定終了条件が充足されるまでステップＳ１２５以降の処理を繰り返す。ここで、コスト設定終了条件は種々の条件を採用可能であり、例えば、目的地までの経路探索に必要なリンクについてコスト設定処理が終了した場合にコスト設定終了条件が充足したと見なされる構成等を採用可能である。

ステップＳ１５５において、コスト設定終了条件が充足されたと判定された場合、制御部２０は、経路探索部２１ｃの処理により、設定されたコストに基づいて通過道路を通過する経路を探索する（ステップＳ１６０）。すなわち、制御部２０は、ステップＳ１４５，Ｓ１５０で設定されたコストに基づいて、現在地から通過道路までの経路を探索する。さらに、制御部２０は、ステップＳ１４５，Ｓ１５０で設定されたコストに基づいて、通過道路から目的地までの経路を探索する。そして、制御部２０は、探索された経路を結合して、現在地から目的地までの、通過道路を通過する経路を取得する。以上の構成により、表示対象道路を探索対象（ただし、周辺領域内の道路区間は例外）とした第２態様での経路探索が行われる。

なお、出発地および目的地から地図上の表示対象道路に至るまでの区間である周辺領域においては、細街路等、表示対象となっていない道路を利用しないとこれらの地点に到達できない場合がある。しかし、本実施形態において周辺領域においては、表示対象道路以外の道路であっても探索対象となって経路探索が行われる。従って、出発地から目的地までの経路を途切れることなく探索することができる。

（３）他の実施形態：
以上の実施形態は本発明を実施するための一例であり、地図上に表示されていない道路を探索対象から除外して経路を探索する限りにおいて、他にも種々の実施形態を採用可能である。例えば、ナビゲーションシステム１０は、可搬型の装置であってもよい。また、車両以外の案内、例えば、歩行者の案内等にナビゲーションシステム１０が利用されてもよい。さらに、経路探索システムを構成する手段が複数の装置に分かれて存在していても良い。さらに、上述の第１態様の経路探索で表示対象道路を探索対象とした探索を行ってもよい。

探索条件取得手段は、出発地と目的地とを取得することができればよい。すなわち、探索条件取得手段は、経路を探索するための条件として経路の両端の地点を取得することができればよい。むろん、出発地と目的地以外にも他の探索条件（例えば、コストの重み付け（一般道優先等）や経由地等）が取得され、探索に反映されても良い。

記憶部は、地図の縮尺毎に表示対象となる表示対象道路が決められた地図情報を記憶することができればよい。すなわち、記憶部は、経路の探索や地図の表示のために参照される地図情報を記憶することができる。ただし、表示部に地図が表示される際には地図の縮尺を調整可能であり、当該縮尺毎に表示対象となる表示対象道路が決められており、各縮尺に表示対象道路が対応づけられて定義されている。従って、任意の縮尺の地図を表示する際に、地図情報に基づいて表示対象道路を特定することが可能である。

地図表示手段は、地図情報と表示部に表示する地図の縮尺に基づいて表示対象道路を特定し、特定された表示対象道路からなる地図を表示部に表示することができればよい。すなわち、地図表示手段は、表示対象となる地図の縮尺を特定し、当該縮尺の地図を表示部に表示する。当該地図には、少なくとも道路が含まれており、任意の縮尺の地図において表示される表示対象道路は地図情報および地図の縮尺に基づいて特定される。表示対象道路が特定されると、地図表示手段は、当該表示対象道路で道路ネットワークが構成された地図を描画し、表示部に表示させる。このとき、表示される地図の縮尺における表示対象道路でない道路は地図に表示されない。なお、表示部に表示する地図の縮尺は、種々の手法で特定されて良く、利用者が指定しても良いし、既定の縮尺（前回表示された縮尺等）であっても良いし、地図に表示すべき要素（例えば、出発地、目的地、経路等）に従って特定されても良い。

経路探索手段は、表示部に表示されている地図上の表示対象道路を探索対象とし、地図上の表示対象道路ではない道路を探索対象から除外して出発地から目的地までの経路を探索することができればよい。すなわち、利用者が、表示部に表示されている地図によって（地図を視認することによって）、その存在を確認可能な表示対象道路が探索対象とされ、利用者が、表示中の地図によって存在を確認できない道路は探索対象から除外される。このため、利用者が存在を確認できない道路が経路に含まれることはなく、探索された経路を利用者が地図上で確認できるように、経路を探索することができる。

探索対象は、経路となり得る候補としての道路である。探索対象を限定するための構成としては、種々の構成を採用可能であり、探索対象から除外された道路を探索の際に候補と見なさない構成であっても良いし、コストに基づいて探索する構成において探索対象から除外された道路に極めて大きいコストを付与する構成であっても良く、種々の構成を採用可能である。

探索は、種々の手法を採用可能であり、ダイクストラ法等の手法を採用可能である。また、探索が行われるタイミングとしても種々のタイミングを採用可能であり、出発地から目的地までの経路が存在しない（探索されていない）状態で経路が探索されても良いし、目的地までの経路が既に存在する状態で経路が探索されても良い。経路表示手段は、探索された経路を表示部に表示された地図上に表示することができればよく、種々の態様で経路を示すことが可能である。例えば、経路の道路に経路を示す線の画像を重畳する表示（近傍等に表示してもよい）を行う構成等を採用可能である。

さらに、地図情報が、道路の端点を示すノードの密度が上位階層であるほど小さくなるように階層化されて定義されている構成において、出発地および目的地の周辺領域を除く中間領域においては、周辺領域よりも上位階層に属する道路を探索対象の道路として、経路探索手段が経路を探索する構成であっても良い。すなわち、階層化されて定義された地図情報を利用し、出発地および目的地の周辺領域と中間領域とで異なる階層の道路を探索対象とする方式を採用すれば、経路探索の開始から終了までの所要時間を短縮することが可能である。

なお、周辺領域は、出発地および目的地の周囲に中間領域の経路の探索対象となる道路が属する上位階層の道路が存在しない場合に、当該上位階層より下位の階層の道路を使って探索が行えるように定義されれば良いため、当該目的に応じて適宜周辺領域の大きさが変更されても良い。例えば、出発地や目的地が上位階層に属する道路沿いに存在するのであれば、周辺領域が実質的に設けられていなくても良いし、出発地や目的地から上位階層に属する道路までの距離が長い場合、周辺領域の大きさが当該距離に応じて変化してよい。

階層は、道路の端点を示すノードの密度が異なるように定義されていればよく、この結果、上位階層であるほど道路の密度が小さく、当該密度の差異を反映して経路探索が高速に実行できるように構成されていれば良い。例えば、上位階層であるほど交通量の多い道路や広い道路に限定され、下位階層であるほど交通量が少ない道路や狭い道路が増えるような傾向となるように階層が定義されていれば良い。

さらに、出発地および目的地の周辺領域においては、経路探索手段が、地図上の表示対象道路ではない道路を探索対象に含めて経路を探索する構成であってもよい。すなわち、出発地および目的地の周辺領域においては、細街路等の狭い道路を利用しないとこれらの地点に到達できない場合がある。しかし、このような狭い道路は常に地図上に表示されるとは限らない（一般的に多用される縮尺では表示されない等）。そこで、出発地および目的地の周辺領域においては、経路探索手段が、例外的に、地図上の表示対象道路ではない道路を探索対象に含めて経路を探索する構成とすれば、出発地からの出発直後の経路や目的地に到達する直前の経路が探索不能になることを防止することができ、出発地から目的地までの経路を途切れることなく探索することができる。なお、地図上の表示対象道路ではない道路が探索対象に含められ、探索された結果としての経路に当該表示対象道路ではない道路が含まれる場合、経路表示手段が当該道路を地図上に表示しても良い。この構成によれば、出発地から目的地までの経路を途切れることなく表示することができる。

さらに、出発地および目的地から地図上の表示対象道路に至るまでの区間については、経路探索手段が、地図上の表示対象道路ではない道路を探索対象に含めて経路を探索する構成であっても良い。すなわち、出発地および目的地の周辺領域においては、細街路等、表示対象となっていない道路を利用しないとこれらの地点に到達できない場合がある。そこで、出発地および目的地から地図上の表示対象道路に至るまでの区間については、経路探索手段が、地図上の表示対象道路ではない道路を探索対象に含めて経路を探索する構成とすれば、出発地からの出発直後の経路や目的地に到達する直前の経路が探索不能になることを防止することができ、出発地から目的地までの経路を途切れることなく探索することができる。この場合も、地図上の表示対象道路ではない道路が探索対象に含められ、探索された結果としての経路に当該表示対象道路ではない道路が含まれる場合、経路表示手段が当該道路を地図上に表示しても良い。この構成によれば、出発地から目的地までの経路を途切れることなく表示することができる。

さらに、地図表示手段が、出発地と目的地とが表示部に表示される縮尺で地図を表示部に表示する構成としても良い。この構成によれば、出発地と目的地とが表示部に表示された状態において、表示対象ではない道路を探索対象から除外して経路を探索することができる。従って、一画面に出発地と目的地とが表示されている状態において、表示されている道路を使用して探索および探索結果の表示を行うことができる。

さらに、探索条件取得手段が、２個以上の目的地を取得することが可能である構成において、２個以上の目的地が取得された場合、地図表示手段が、現在地から直近の目的地が表示部に表示される縮尺で地図を表示部に表示する構成であっても良い。例えば、図３Ａの例のように目的地が１個の場合ではなく、２個以上である場合、現在地と直近の目的地が１画面に同時表示される構成としても良い。この構成によれば、現在地と直近の目的地とが表示部に表示された状態において、表示対象ではない道路を探索対象から除外して経路を探索することができる。従って、一画面に現在地と直近の目的地とが表示されている状態において、表示されている道路を使用して探索および探索結果の表示を行うことができる。

さらに、表示部がタッチパネルディスプレイであり、探索条件取得手段が、利用者がタッチパネルディスプレイに表示されている地図上の表示対象道路をタッチすることによって指定した通過道路を取得可能である構成において、利用者が地図上の表示対象道路をタッチすることによって通過道路を指定した場合に、経路探索手段が、タッチパネルディスプレイに表示されている地図上の表示対象道路を探索対象とし、地図上の表示対象道路ではない道路を探索対象から除外して、通過道路を通過する出発地から目的地までの経路を探索する構成としてもよい。

すなわち、利用者が、地図上の道路をタッチすることによって通過道路を指定する構成においては、利用者が地図上に表示されている表示対象道路から選択した道路が通過道路になる。この場合において、表示されていない道路が探索対象となり、表示されていない道路が経路となり、表示されると、通過道路を指定した利用者にとって強い違和感を与える。そこで、地図上の道路をタッチすることによって通過道路を指定する構成において、探索対象道路を表示対象道路に限定する構成を採用すれば、通過道路を指定した利用者に強い違和感を覚えさせることはない。

さらに、本発明のように、地図上に表示されていない道路を探索対象から除外して経路を探索する手法は、プログラムや方法としても適用可能である。また、以上のようなシステム、プログラム、方法は、単独の装置として実現される場合や、複数の装置によって実現される場合が想定可能であり、各種の態様を含むものである。例えば、以上のような手段を備えた経路探索システムや方法、プログラムを提供することが可能である。また、一部がソフトウェアであり一部がハードウェアであったりするなど、適宜、変更可能である。さらに、システムを制御するプログラムの記録媒体としても発明は成立する。むろん、そのソフトウェアの記録媒体は、磁気記録媒体であってもよいし光磁気記録媒体であってもよいし、今後開発されるいかなる記録媒体においても全く同様に考えることができる。

１０…ナビゲーションシステム、２０…制御部、２１…経路探索プログラム、２１ａ…探索条件取得部、２１ｂ…地図表示部、２１ｃ…経路探索部、２１ｄ…経路表示部、３０…記録部、３０ａ…地図情報、４０…ユーザＩ／Ｆ部、４１…ＧＰＳ受信部、４２…車速センサ、４３…ジャイロセンサ

Claims (9)

1. 出発地と目的地とを取得する探索条件取得手段と、
   地図の縮尺毎に表示対象となる表示対象道路が決められた地図情報を記憶する記憶部と、
   前記地図情報と表示部に表示する前記地図の縮尺に基づいて前記表示対象道路を特定し、特定された前記表示対象道路からなる前記地図を前記表示部に表示する地図表示手段と、
   前記表示部に表示されている前記地図上の前記表示対象道路を探索対象とし、前記地図上の前記表示対象道路ではない道路を前記探索対象から除外して前記出発地から前記目的地までの経路を探索する経路探索手段であって、前記出発地および前記目的地の周辺領域においては、前記地図上の前記表示対象道路ではない道路を前記探索対象に含め、前記地図情報に予め定義されたコストに基づいて前記経路を探索する前記経路探索手段と、
   探索された前記経路を前記地図上に表示する経路表示手段と、
   を備える経路探索システム。
2. 前記地図情報は、
   道路の端点を示すノードの密度が上位階層であるほど小さくなるように階層化されて定義されており、
   前記経路探索手段は、
   前記周辺領域を除く中間領域においては、前記周辺領域よりも上位階層に属する道路を前記探索対象の道路として前記経路を探索する、
   請求項１に記載の経路探索システム。
3. 前記経路表示手段は、
   前記地図上の前記表示対象道路ではない道路が前記探索対象に含められ、探索された結果としての前記経路に当該表示対象道路ではない道路が含まれる場合、当該道路を前記地図上に表示する、
   請求項１または請求項２のいずれかに記載の経路探索システム。
4. 前記経路探索手段は、
   前記出発地および前記目的地から前記地図上の前記表示対象道路に至るまでの区間については、前記地図上の前記表示対象道路ではない道路を前記探索対象に含めて前記経路を探索する、
   請求項１〜請求項３のいずれかに記載の経路探索システム。
5. 前記地図表示手段は、
   前記出発地と前記目的地とが前記表示部に表示される縮尺で前記地図を前記表示部に表示し、
   前記経路探索手段は、前記表示部に表示されている前記地図上の前記表示対象道路を前記探索対象とし、前記地図上の前記表示対象道路ではない道路を前記探索対象から除外して前記出発地から前記目的地までの前記経路を探索する、
   請求項１〜請求項４のいずれかに記載の経路探索システム。
6. 前記探索条件取得手段は、
   ２個以上の前記目的地を取得することが可能であり、
   前記地図表示手段は、
   ２個以上の前記目的地が取得された場合、現在地から直近の前記目的地が前記表示部に表示される縮尺で前記地図を前記表示部に表示し、
   前記経路探索手段は、前記表示部に表示されている前記地図上の前記表示対象道路を前記探索対象とし、前記地図上の前記表示対象道路ではない道路を前記探索対象から除外して前記出発地から前記目的地までの前記経路を探索する、
   請求項１〜請求項５のいずれかに記載の経路探索システム。
7. 前記表示部はタッチパネルディスプレイであり、
   前記探索条件取得手段は、
   利用者が前記タッチパネルディスプレイに表示されている前記地図上の前記表示対象道路をタッチすることによって指定した通過道路を取得可能であり、
   前記経路探索手段は、
   利用者が前記地図上の前記表示対象道路をタッチすることによって前記通過道路を指定した場合に前記タッチパネルディスプレイに表示されている前記地図上の前記表示対象道路を前記探索対象とし、前記地図上の前記表示対象道路ではない道路を前記探索対象から除外して、前記通過道路を通過する前記出発地から前記目的地までの前記経路を探索する、
   請求項１〜請求項６のいずれかに記載の経路探索システム。
8. 出発地と目的地とを取得する探索条件取得工程と、
   地図の縮尺毎に表示対象となる表示対象道路が決められた地図情報と表示部に表示する前記地図の縮尺に基づいて前記表示対象道路を特定し、特定された前記表示対象道路からなる前記地図を前記表示部に表示する地図表示工程と、
   前記表示部に表示されている前記地図上の前記表示対象道路を探索対象とし、前記地図上の前記表示対象道路ではない道路を前記探索対象から除外して前記出発地から前記目的地までの経路を探索する経路探索工程であって、前記出発地および前記目的地の周辺領域においては、前記地図上の前記表示対象道路ではない道路を前記探索対象に含め、前記地図情報に予め定義されたコストに基づいて前記経路を探索する前記経路探索工程と、
   探索された前記経路を前記地図上に表示する経路表示工程と、
   を含む経路探索方法。
9. 出発地と目的地とを取得する探索条件取得機能と、
   地図の縮尺毎に表示対象となる表示対象道路が決められた地図情報と表示部に表示する前記地図の縮尺に基づいて前記表示対象道路を特定し、特定された前記表示対象道路からなる前記地図を前記表示部に表示する地図表示機能と、
   前記表示部に表示されている前記地図上の前記表示対象道路を探索対象とし、前記地図上の前記表示対象道路ではない道路を前記探索対象から除外して前記出発地から前記目的地までの経路を探索する経路探索機能であって、前記出発地および前記目的地の周辺領域においては、前記地図上の前記表示対象道路ではない道路を前記探索対象に含め、前記地図情報に予め定義されたコストに基づいて前記経路を探索する前記経路探索機能と、
   探索された前記経路を前記地図上に表示する経路表示機能と、
   をコンピュータに実現させる経路探索プログラム。

Images