(57)【特許請求の範囲】
【請求項１】
探索開始点から順次探索枝を延ばして目的点までの経路を探索する経路探索装置において、
着目交差点を介してそれに隣接する交差点までの経路のうちコストが最小の経路及び該コストを該隣接交差点に対応させて保存する記憶部、
探索開始点から目的点あるいはその近傍点までの直線距離をＡ、探索開始点から着目交差点を介してそれに隣接する交差点までの累計距離をＤ、探索開始点から該隣接交差点までの直線距離をＢとするとき、隣接交差点までのコストＣを次式
Ｃ＝Ｄ＋ｋ（Ａ−Ｂ） （ｋは係数）
により算出し、該隣接交差点までの経路のうちコストが最小の経路及び該コストを前記記憶部に該隣接交差点に対応させて保存し、同様に着目交差点に隣接する他の交差点に対応させて経路及びコストを前記記憶部に保存し、以後保存した各隣接交差点を着目交差点とし探索枝を延ばして目的点までの経路を探索する経路探索部、
を備えたことを特徴とする経路探索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は経路探索装置に係わり、特に、探索開始点から順次探索枝を延ばして目的地までの経路を探索する経路探索装置に関する。
【０００２】
【従来の技術】
車載用ナビゲーション装置は、出発地点から目的地点までのコスト最小の経路、例えば最短距離を辿るような経路を探索し、画面に該経路を表示して運転者の走行案内をする（経路誘導機能）。この経路誘導機能によれば、実際の運転に際して、誘導経路を特定の色で太く表示するなど他の道路と識別可能に表示して、運転者が目的地まで容易に到着できるようになっている。車両が走行する経路を道路地図データから検索する方法として、ダイクストラ法が知られている。ダイクストラ法は出発地と目的地を結ぶ直線を半径とする領域、あるいは該領域より大きめの領域内に存在する全交差点を考慮して出発地から目的地迄の最短経路を探索するものである。
【０００３】
図７はダイクストラ法の概略説明図で、道路を直線、交差点を直線の交点としてグラフ化したものであり、各交差点間の距離は既知で、Ｐsは出発点(自車位置)、Ｐdは目的地である。ダイクストラ法では、出発地Ｐsに隣接する１次交差点Ａ1〜Ａ4を求め、各１次交差点Ａ1〜Ａ4に対応させて０次の交差点（出発点）及び出発点からの距離を記憶する。ついで、各１次交差点Ａ1〜Ａ4について２次交差点Ｂijを求め、各２次交差点に対応させて１次交差点及び出発点からの距離を求める。例えば、１次交差点Ａ2については３つの２次交差点Ｂ11，Ｂ12，Ｂ13が求まり、各２次交差点Ｂ11，Ｂ12，Ｂ13に対応させて、
Ｂ11：１次交差点Ａ2と出発点からの距離ｄ11 Ｂ12：１次交差点Ａ2と出発点からの距離ｄ12 Ｂ13：１次交差点Ａ2と出発点からの距離ｄ13  ・・(a)
を記憶する。
【０００４】
又、1次交差点Ａ3について３つの２次交差点Ｂ21，Ｂ22，Ｂ23が求まり、各２次交差点Ｂ21，Ｂ22，Ｂ23に対応させて、
Ｂ21：１次交差点Ａ3と出発点からの距離ｄ21  ・・(b)
Ｂ22：１次交差点Ａ3と出発点からの距離ｄ22 Ｂ23：１次交差点Ａ3と出発点からの距離ｄ23を記憶し、他の１次交差点Ａ1，Ａ4についても同様に２次交差点を求めて所定のデータを記憶する。ところで、交差点Ｂ13とＢ21は同一の交差点である。このように、デ−タを記憶すべき交差点が重複すると、出発点からの距離ｄ13とｄ21の大小を比較し、小さい方のデータのみを記憶する。たとえば、ｄ13＞ｄ21であれば、交差点Ｂ13（＝Ｂ21)のデータとして(b)のデータが最終的に記憶される。
以後、同様に、各２次交差点について３次交差点Ｃijを求め、各３次交差点に対応させて２次交差点及び出発点からの距離を求めて記憶し、一般に各第ｉ次交差点について第(i+1)次交差点を求め、各第(i+1)次交差点に対応させて第ｉ次交差点と出発点からの累計距離を求めて記憶してゆけば、最終的に目的点Ｐｄに到達する。尚、出発点及び目的点の双方からダイクストラ法により検索し、双方からの検索経路が互いにリンクした時点で検索を停止し、双方の検索経路を接続して出発点から目的点までの経路とすることもできる。
【０００５】
以上では、ダイクストラ法により、階層構造を有しない地図データを用いて経路探索する場合であるが、階層構造を有する地図データを用いて経路探索することもできる。図８を参照して説明すると、まず、▲１▼下層の交差点ネットリストを用いて、出発点Ｐsから上層起点Ｐs′までを結ぶ最適な第１経路PT1及び目的点Ｐdから上層終点Ｐd′までを結ぶ最適な第２経路PT2をそれぞれダイクストラ法により求め、しかる後、▲２▼上層の交差点ネットリストを用いて、上層起点Ｐs′から上層終点Ｐd′までを結ぶ最適な第３経路PT3をダイクストラ法により求め、▲３▼これら第１経路→第３経路→第２経路を順に結合して出発点から目的点までの最適経路とする。
【０００６】
【発明が解決しようとする課題】
以上のように階層構造の道路ネットワークを用いてルート探索を行う場合、まず両地点Ｐs,Ｐdから伸ばされる探索枝が連結し合う上層レベルを決定し、両地点が含まれる最下層から上層の交差点まで探索枝を伸ばし、ついで、上層で探索枝を両方から伸ばしあい、接触した探索枝から両地点までのリンクの並びを最適ルートとする。かかる経路探索において、(1) 最下層から上層までの探索では、いかに少ない計算量で広範囲に探索枝を伸ばして有効な上層への交差点を探すかが重要なポイントであり、又、(2) 上層での探索では、同様に少ない計算量で両地点からの探索枝を接触させるかが重要なポイントとなる。
しかし、従来のダイクストラ法で探索枝を伸ばしていくと、アルゴリズムの性質上、探索開始地点に近いエリアほど密（びっしり）に、離れるほど疎（ぱらぱら）に計算され、探索される範囲は探索開始点を中心にグラデーション状にじわじわとゆっくり広がっていく。つまり従来の純粋なダイクストラ法によるルート探索では上記のポイントが解決されない問題がある。
以上から本発明の目的は、経路探索に要する計算量を減らし、探索時間を短縮することができる経路探索装置を提供することである。
【０００７】
【課題を解決するための手段】
本発明では、(1) 探索開始点から目的点あるいはその近傍点までの直線距離をＡ、探索開始点から着目交差点を介してそれに隣接する交差点までの累計距離をＤ、探索開始点から該隣接交差点までの直線距離をＢとするとき、隣接交差点までのコストＣを次式
Ｃ＝Ｄ＋ｋ（Ａ−Ｂ）
により求め（ｋは係数）、(2) 隣接交差点までの経路のうちコストが最小の経路及び該コストを隣接交差点に対応させて保存し、同様に着目交差点に隣接する他の交差点に対応させて経路及びコストを保存し、(3) 以後保存した各隣接交差点を着目交差点とし探索枝を延ばして目的点までの経路を探索する。
【０００８】
【発明の実施の形態】
（Ａ）本発明の原理
図１は本発明の原理説明図である。探索開始点Ｐsから目的点Ｐdあるいはその近傍点までの直線距離をＡ、探索開始点Ｐsから着目交差点Ｐiを介してそれに隣接する交差点Ｐn1までの累計距離をＤ、探索開始点Ｐsから該隣接交差点Ｐn1までの直線距離をＢとするとき、隣接交差点Ｐn1までのコストＣを次式
Ｃ＝Ｄ＋ｋ（Ａ−Ｂ）
により求める（ｋは係数）。ついで、隣接交差点Ｐn1までの経路のうちコストが最小の経路及び該コストを隣接交差点Ｐn1に対応させて保存し、同様に他の隣接交差点Ｐn2,..に対応させて経路及びコストを保存する。以後、保存した各隣接交差点Ｐn1,Ｐn2,,..を着目交差点とし探索枝を延ばして目的点までの経路を探索する。
以上のようにすれば、着目交差点が探索開始地点から離れて探索範囲円の円周に近づくほどｋ（Ａ−Ｂ）が小さくなる為、探索枝が円周方向へぐいぐい伸びるようになり、経路探索速度が向上する。
【０００９】
（Ｂ）ナビゲーション装置の構成
図２は本発明を実現するナビゲーション装置の構成図であり、１１は道路地図を記憶するDVD（地図データ記憶部）である。地図データは、(1) ノ−ドテーブルNDTB、道路リストRDLT、交差点構成ノ−ドリストCRLT、交差点ネットリストCRNLからなる道路レイヤと、(2) 地図上のオブジェクトを表示するための背景レイヤと、(3) 市町村名や国道名などを表示するための文字レイヤなどから構成されている。地図データに含まれる道路レイヤは図３に示すデータ構造を有している。このうち、道路リストRDLTは該当道路リンクの属性情報を与えるもので、リンク上の全ノ−ド数、リンクを構成する各ノ−ド、道路の種別（国道、高速道路、幅員、その他の別）等のデータより構成されている。交差点ノ−ド構成リストCRLTは地図上の各交差点毎に、該交差点に連結する各リンクの他端ノ−ド（交差点構成ノ−ドという）の集合を示すものである。ノ−ドテ−ブルNDTBは地図上の全ノ−ドのリストであり、ノ−ド毎に▲１▼位置情報（経度、緯度）、▲２▼該ノ−ドが交差点であるか否かの交差点識別フラグ、▲３▼交差点であれば交差点データを指し、交差点でなければ該ノ−ドが属する道路リンクを指すポインタ、▲４▼該交差点が含まれる地図の図葉番号/ユニットコ−ド/ユニットにおける交差点シ−ケンシャル番号等で構成されている。▲４▼の情報が交差点ネットリストCRNLに対するポインタとなる。
【００１０】
交差点ネットリストCRNLは図４に示すように、交差点毎に
(1) 該交差点が含まれる地図の図葉番号
(2) ユニットコ−ド
(3) ユニットにおける交差点シ−ケンシャル番号以上、交差点ＩＤ
(4) 交差点構成ノ−ド数
(5) 上層ノード存在フラグ/上層交差点シーケンス番号、
(6) 各隣接交差点のシ−ケンシャル番号
(7) 各隣接交差点までの距離
(8) 各隣接交差点までの道路の属性（道路種別、幅員）
等を有し、経路探索処理において用いられる。尚、交差点ネットリストには上層用と下層用がある。
【００１１】
交差点ネットリストCRNLにおける(5) の上層ノード存在フラグは、図５に示すように下層での交差点CPB1の存在する道路RDが上層でも道路データで表現されており、かつ、交差点CPB1が上層で交差点CPAとして登録されている場合に「１」が立てられ、その他の場合は「０」とされる（図5のＣＰB2、ＣＰB3の場合）。又、上層交差点シーケンシャル番号は、下層での交差点と同一の交差点について、上層で交差点ネットリストが作成されている場合に、該上層での交差点シーケンシャル番号を示すものである。
【００１２】
図２の戻り、１２は自動車の現在地に応じた地図や自動車位置マ−ク、誘導経路等を描画するディスプレイ装置（CRT）、１３は走行中の自動車の走行距離と方位に基づいて現在地を算出する現在地検出部である。現在地検出部１３は、図示しないが、自動車の進行方位を検出する方位センサや走行距離を検出する車速センサ、方位や走行距離に基づいて自動車の現在地（経度、緯度）を算出する位置計算用CPUを有している。
１４は地図検索キー、地図スクロ−ルキー、経路探索キー、メニューキー等を備えたリモコンなどの操作部、１５はナビゲーション制御装置であり、地図データに基づき車両現在地周辺の地図画像を発生すると共に、誘導経路を探索し、誘導経路画像や自動車位置マ−クを発生する。
ナビゲーション制御装置１５において、１５ａは現在地データに基づき、現在地周辺で画面表示範囲より広い範囲の地図データ（例えば９画面分の地図データ）をDVD １１から読出し、該地図データに基づいてドットイメ−ジの地図画像を発生する地図画像描画部である。
【００１３】
１５ｂは誘導経路探索処理により得られた出発地から目的地までの誘導経路データに基づいて誘導経路画像を発生する誘導経路描画部、１５ｃは地図画像及び誘導経路画像を記憶するビデオRAMである。地図画像描画部１５ａはディスプレイ画面の表示範囲がビデオRAM １５ｃの画像範囲を越えないように、自動車の走行に従って、随時、ビデオRAM １５ｃを書き替え、また誘導経路描画部１５ｂも自動車の走行に応じて誘導経路画像を発生してビデオRAM １５ｃに記憶するようになっている。
【００１４】
１５ｄは車両現在地がディスプレイ画面の固定点に位置するようにビデオRAM １５ｃから１画面分の地図画像を読み出す読出制御部であり、読出し位置は地図画像描画部１５ａから指示される。１５ｅはディスプレイ画面の固定点に自動車位置マ−クを表示するための自動車位置マ−ク発生部、１５ｆは経路探索部であり、経路探索時に出発地と目的地が入力されると地図データに含まれる道路レイヤ情報に基づいて、出発地から目的地迄の最短経路を誘導経路として算出する。１５ｇは出発地から目的地迄の誘導経路を構成するノ−ドを順次記憶する誘導経路記憶部である。１５ｈは合成部であり、ビデオＲＡＭ１５ｃ、自動車位置マ−ク発生部１５ｅからそれぞれ読出された地図画像及び誘導経路画像、自動車位置マ−ク画像、その他メニュー画像を適宜合成してＣＲＴ１２に出力して表示する。
【００１５】
（Ｃ）経路探索処理
図６は本発明の経路探索処理のフローである。本発明はダイクストラ法の探索手順を変形した亜流であり、ダイクストラ法の確実な最短経路を求める機能を弱め（放棄し）、広範囲に探索枝を広げる事に主眼を置いている。予め探索開始点を中心にした円（探索範囲円）を設定する（ステップ１００）。ただし、探索範囲円の半径Ａは探索開始点Ｐs(図１参照）と目的点Ｐdあるいはその近傍点を結ぶ直線距離とする。目的点は例えば下層と上層を連結する交差点である。
【００１６】
ついで、経路探索部１５ｆは、検索次数ｉを０にし（０→ｉ、ステップ１０１）、第ｉ次交差点に隣接する交差点が存在するかを下層交差点ネットリストCRNL（図４）を参照して調べる（ステップ１０２）。０次交差点は出発点Ｐsである。
第ｉ次交差点Ｐiに隣接する交差点が存在すれば、出発点Ｐsから第ｉ次交差点Ｐiを経由して隣接交差点Ｐn1までの累計距離Ｄを計算する（ステップ１０３）。出発点から第ｉ次交差点までの距離ｄ1は後述するように、該第ｉ次交差点に対応させて記憶部15f-1に記憶してあり、また第ｉ次交差点Ｐiから隣接交差点  Ｐn1までの距離ｄ2は交差点ネットリストに記憶してあるから、次式
ｄ1＋ｄ2→Ｄ
により出発点Ｐsから隣接交差点Ｐn1までの累計距離Ｄが求まる。
【００１７】
ついで、出発点Ｐsから隣接交差点Ｐn1までの直線距離Ｂを計算し（ステップ１０４）、次式
Ｃ＝Ｄ＋ｋ（Ａ−Ｂ）
（ｋは係数）によりコストＣを演算する（ステップ１０５）。ｋは（Ａ−Ｂ）のコストに対する影響
（効果）を調整する係数であり、ｋの大小により（Ａ−Ｂ）の効果に強弱を与えることができ、計算された探索経路の品質と探索時間のバランスを調節することができる。
ついで、隣接交差点Ｐn1の検索次数が(i+1)かチェックし（ステップ１０６）、(i+1)でなければ、隣接交差点に対応させて、以下のデータ
(1) 現在着目している第ｉ次交差点のシ−ケンシャル番号、
(2) 出発点から当該隣接交差点までのトータルコストＣ、
(3) 出発点から当該隣接交差点までの累計距離Ｄ、
(4) 当該隣接交差点の検索次数としての(i+1)
を記憶部15f-1に記憶し（ステップ１０７）、以後、ステップ１０２に戻り、着目している第ｉ次交差点に隣接する交差点が、なお残存するか調べて以降の処理を繰り返す。
【００１８】
一方、ステップ１０６において、隣接交差点の次数が(i+1)の場合には、換言すれば、該隣接交差点が別の第ｉ次交差点に隣接する交差点として参照されていれば（ステップ１０７で既に上記(1)〜(4) のデータが記憶されていれば）、該隣接交差点に対応して記憶してある出発点からのトータルコストＣ′とステップ１０５で求めたコストＣの大小を比較する（ステップ１０８）。
Ｃ＜Ｃ′であれば、当該隣接交差点Ｐn1に対応して記憶部15f-1に記憶してある、第ｉ次交差点のシ−ケンシャル番号を現在着目している第ｉ次交差点のシ−ケンシャル番号で置き換えると共に、コストＣ′及び累計距離Ｄ′をＣ，Ｄで書き替え（Ｃ→Ｃ′，Ｄ→Ｄ′，ステップ１０９）、以後、ステップ１０２に戻り、着目している第ｉ次交差点に隣接する交差点が、なお残存するか調べて以降の処理を繰り返す。又、Ｃ≧Ｃ′の場合には、当該隣接交差点に対応して記憶部15f-1に記憶してある内容を変更せずステップ１０２に戻る。
【００１９】
ステップ１０２において、着目している第ｉ次交差点に隣接する交差点が存在しなくなれば、別の第ｉ次交差点が存在するか調べ（ステップ１１０）、存在すれば、該別の第ｉ次交差点を新たに第ｉ次交差点として（ステップ１１１）、ステップ１０２以降の処理を繰り返す。
ステップ１１０において、別の第ｉ次交差点が存在しなければ、目的点Ｐdに到達したかチェックし、換言すれば第(i+1)次の交差点に目的点が含まれているかチェックし（ステップ１１２）、含まれていなければ検索次数を１つ歩進し（ｉ＋１→ｉ，ステップ１１３）、ステップ１０２以降の処理を繰り返す。しかし、目的点に到達すれば、▲１▼目的点Ｐd→目的点（ｍ次の交差点とする）に対応させて記憶してある（ｍ−１）次の交差点→▲３▼該（ｍ−１）次の交差点に対応させて記憶してある（ｍ−２）次の交差点→・・・→▲４▼２次の交差点に対応させて記憶してある１次交差点→▲５▼該１次交差点に対応させて記憶してある０次の交差点（出発点）を順次接続してコストの小さい経路を決定し（ステップ１１４）、経路処理を終了する。
【００２０】
本発明によれば、着目交差点が探索開始地点から離れて探索範囲円の円周に近づくほどｋ（Ａ−Ｂ）が小さくなる為、探索枝が円周方向へぐいぐい伸びるようになり、経路探索速度が向上する。
以上、本発明を実施例により説明したが、本発明は請求の範囲に記載した本発明の主旨に従い種々の変形が可能であり、本発明はこれらを排除するものではない。
【００２１】
【発明の効果】
以上本発明によれば、ｋ（Ａ−Ｂ）をコストに含めたから、着目交差点が探索開始地点から離れて探索範囲円の円周に近づくほどｋ（Ａ−Ｂ）が小さくなり、この結果、探索枝が円周方向へぐいぐい伸びるようになり、経路探索に要する計算量が減り、経路探索時間が短縮する。
【図面の簡単な説明】
【図１】本発明の経路探索の原理説明図である。
【図２】本発明を実現するナビゲーション装置の構成図である。
【図３】道路レイヤ説明図である。
【図４】交差点ネットリスト説明図である。
【図５】上層ノード存在フラグ、上層道路識別データの説明図である。
【図６】本発明の経路探索処理である。
【図７】ダイクストラ法の説明図である。
【図８】階層構造を有する地図データを用いた経路探索法の説明図である。
【符号の説明】
Ｐs・・探索開始点
Ｐd・・目的点
Ｐi・・着目交差点
Ｐn1,Ｐn2・・隣接交差点
【図１】
0003860392.tif 000002
【図２】
0003860392.tif 000003
【図３】
0003860392.tif 000004
【図４】
0003860392.tif 000005
【図５】
0003860392.tif 000006
【図６】
0003860392.tif 000007
【図７】
0003860392.tif 000008
【図８】
0003860392.tif 000009