米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 測定; 光学 -> アルパイン株式会社

発明の名称 経路探索方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2001−324343(P2001−324343A)
公開日 平成13年11月22日(2001.11.22)
出願番号 特願2000−144784(P2000−144784)
出願日 平成12年5月17日(2000.5.17)
代理人 【識別番号】100084711
【弁理士】
【氏名又は名称】斉藤 千幹
【テーマコード(参考)】
2C032
2F029
5H180
【Fターム(参考)】
2C032 HB11 HC27 HD21 
2F029 AA02 AB07 AB13 AC02 AC08 AC14
5H180 AA01 FF05 FF11 FF23 FF27 FF32
発明者 松崎 聡
要約 目的


構成
特許請求の範囲
【請求項1】 探索開始点から順次探索枝を延ばして目的点までの経路を探索する経路探索方法において、探索開始点から目的点あるいはその近傍点までの直線距離をA、探索開始点から着目交差点を介してそれに隣接する交差点までの累計距離をD、探索開始点から該隣接交差点までの直線距離をBとするとき、隣接交差点までのコストCを次式C=D+k(A−B)
により求め(kは係数)、隣接交差点までの経路のうちコストが最小の経路及び該コストを隣接交差点に対応させて保存し、同様に着目交差点に隣接する他の交差点に対応させて経路及びコストを保存し、以後保存した各隣接交差点を着目交差点とし探索枝を延ばして目的点までの経路を探索する、ことを特徴とする経路探索方法。
発明の詳細な説明
【0001】
【発明の属する技術分野】本発明は経路探索方法に係わり、特に、探索開始点から順次探索枝を延ばして目的地までの経路を探索する経路探索方法に関する。
【0002】
【従来の技術】車載用ナビゲーション装置は、出発地点から目的地点までのコスト最小の経路、例えば最短距離を辿るような経路を探索し、画面に該経路を表示して運転者の走行案内をする(経路誘導機能)。この経路誘導機能によれば、実際の運転に際して、誘導経路を特定の色で太く表示するなど他の道路と識別可能に表示して、運転者が目的地まで容易に到着できるようになっている。車両が走行する経路を道路地図データから検索する方法として、ダイクストラ法が知られている。ダイクストラ法は出発地と目的地を結ぶ直線を半径とする領域、あるいは該領域より大きめの領域内に存在する全交差点を考慮して出発地から目的地迄の最短経路を探索するものである。
【0003】図7はダイクストラ法の概略説明図で、道路を直線、交差点を直線の交点としてグラフ化したものであり、各交差点間の距離は既知で、Psは出発点(自車位置)、Pdは目的地である。ダイクストラ法では、出発地Psに隣接する1次交差点A1〜A4を求め、各1次交差点A1〜A4に対応させて0次の交差点(出発点)及び出発点からの距離を記憶する。ついで、各1次交差点A1〜A4について2次交差点Bijを求め、各2次交差点に対応させて1次交差点及び出発点からの距離を求める。例えば、1次交差点A2については3つの2次交差点B11,B12,B13が求まり、各2次交差点B11,B12,B13に対応させて、11:1次交差点A2と出発点からの距離d11 12:1次交差点A2と出発点からの距離d12 13:1次交差点A2と出発点からの距離d13 ・・(a)を記憶する。
【0004】又、1次交差点A3について3つの2次交差点B21,B22,B23が求まり、各2次交差点B21,B22,B23に対応させて、B21:1次交差点A3と出発点からの距離d21 ・・(b)B22:1次交差点A3と出発点からの距離d22 23:1次交差点A3と出発点からの距離d23を記憶し、他の1次交差点A1,A4についても同様に2次交差点を求めて所定のデータを記憶する。ところで、交差点B13とB21は同一の交差点である。このように、デ−タを記憶すべき交差点が重複すると、出発点からの距離d13とd21の大小を比較し、小さい方のデータのみを記憶する。たとえば、d13>d21であれば、交差点B13(=B21)のデータとして(b)のデータが最終的に記憶される。
以後、同様に、各2次交差点について3次交差点Cijを求め、各3次交差点に対応させて2次交差点及び出発点からの距離を求めて記憶し、一般に各第i次交差点について第(i+1)次交差点を求め、各第(i+1)次交差点に対応させて第i次交差点と出発点からの累計距離を求めて記憶してゆけば、最終的に目的点Pdに到達する。尚、出発点及び目的点の双方からダイクストラ法により検索し、双方からの検索経路が互いにリンクした時点で検索を停止し、双方の検索経路を接続して出発点から目的点までの経路とすることもできる。
【0005】以上では、ダイクストラ法により、階層構造を有しない地図データを用いて経路探索する場合であるが、階層構造を有する地図データを用いて経路探索することもできる。図8を参照して説明すると、まず、■下層の交差点ネットリストを用いて、出発点Psから上層起点Ps′までを結ぶ最適な第1経路PT1及び目的点Pdから上層終点Pd′までを結ぶ最適な第2経路PT2をそれぞれダイクストラ法により求め、しかる後、■上層の交差点ネットリストを用いて、上層起点Ps′から上層終点Pd′までを結ぶ最適な第3経路PT3をダイクストラ法により求め、■これら第1経路→第3経路→第2経路を順に結合して出発点から目的点までの最適経路とする。
【0006】
【発明が解決しようとする課題】以上のように階層構造の道路ネットワークを用いてルート探索を行う場合、まず両地点Ps,Pdから伸ばされる探索枝が連結し合う上層レベルを決定し、両地点が含まれる最下層から上層の交差点まで探索枝を伸ばし、ついで、上層で探索枝を両方から伸ばしあい、接触した探索枝から両地点までのリンクの並びを最適ルートとする。かかる経路探索において、(1) 最下層から上層までの探索では、いかに少ない計算量で広範囲に探索枝を伸ばして有効な上層への交差点を探すかが重要なポイントであり、又、(2) 上層での探索では、同様に少ない計算量で両地点からの探索枝を接触させるかが重要なポイントとなる。しかし、従来のダイクストラ法で探索枝を伸ばしていくと、アルゴリズムの性質上、探索開始地点に近いエリアほど密(びっしり)に、離れるほど疎(ぱらぱら)に計算され、探索される範囲は探索開始点を中心にグラデーション状にじわじわとゆっくり広がっていく。つまり従来の純粋なダイクストラ法によるルート探索では上記のポイントが解決されない問題がある。以上から本発明の目的は、経路探索に要する計算量を減らし、探索時間を短縮することができる経路探索方法を提供することである。
【0007】
【課題を解決するための手段】本発明では、(1) 探索開始点から目的点あるいはその近傍点までの直線距離をA、探索開始点から着目交差点を介してそれに隣接する交差点までの累計距離をD、探索開始点から該隣接交差点までの直線距離をBとするとき、隣接交差点までのコストCを次式C=D+k(A−B)
により求め(kは係数)、(2) 隣接交差点までの経路のうちコストが最小の経路及び該コストを隣接交差点に対応させて保存し、同様に着目交差点に隣接する他の交差点に対応させて経路及びコストを保存し、(3) 以後保存した各隣接交差点を着目交差点とし探索枝を延ばして目的点までの経路を探索する。
【0008】
【発明の実施の形態】(A)本発明の原理図1は本発明の原理説明図である。探索開始点Psから目的点Pdあるいはその近傍点までの直線距離をA、探索開始点Psから着目交差点Piを介してそれに隣接する交差点Pn1までの累計距離をD、探索開始点Psから該隣接交差点Pn1までの直線距離をBとするとき、隣接交差点Pn1までのコストCを次式C=D+k(A−B)
により求める(kは係数)。ついで、隣接交差点Pn1までの経路のうちコストが最小の経路及び該コストを隣接交差点Pn1に対応させて保存し、同様に他の隣接交差点Pn2,..に対応させて経路及びコストを保存する。以後、保存した各隣接交差点Pn1,Pn2,,..を着目交差点とし探索枝を延ばして目的点までの経路を探索する。以上のようにすれば、着目交差点が探索開始地点から離れて探索範囲円の円周に近づくほどk(A−B)が小さくなる為、探索枝が円周方向へぐいぐい伸びるようになり、経路探索速度が向上する。
【0009】(B)ナビゲーション装置の構成図2は本発明を実現するナビゲーション装置の構成図であり、11は道路地図を記憶するDVD(地図データ記憶部)である。地図データは、(1) ノ−ドテーブルNDTB、道路リストRDLT、交差点構成ノ−ドリストCRLT、交差点ネットリストCRNLからなる道路レイヤと、(2) 地図上のオブジェクトを表示するための背景レイヤと、(3) 市町村名や国道名などを表示するための文字レイヤなどから構成されている。地図データに含まれる道路レイヤは図3に示すデータ構造を有している。このうち、道路リストRDLTは該当道路リンクの属性情報を与えるもので、リンク上の全ノ−ド数、リンクを構成する各ノ−ド、道路の種別(国道、高速道路、幅員、その他の別)等のデータより構成されている。交差点ノ−ド構成リストCRLTは地図上の各交差点毎に、該交差点に連結する各リンクの他端ノ−ド(交差点構成ノ−ドという)の集合を示すものである。ノ−ドテ−ブルNDTBは地図上の全ノ−ドのリストであり、ノ−ド毎に■位置情報(経度、緯度)、■該ノ−ドが交差点であるか否かの交差点識別フラグ、■交差点であれば交差点データを指し、交差点でなければ該ノ−ドが属する道路リンクを指すポインタ、■該交差点が含まれる地図の図葉番号/ユニットコ−ド/ユニットにおける交差点シ−ケンシャル番号等で構成されている。■の情報が交差点ネットリストCRNLに対するポインタとなる。
【0010】交差点ネットリストCRNLは図4に示すように、交差点毎に(1) 該交差点が含まれる地図の図葉番号
(2) ユニットコ−ド(3) ユニットにおける交差点シ−ケンシャル番号以上、交差点ID(4) 交差点構成ノ−ド数(5) 上層ノード存在フラグ/上層交差点シーケンス番号、(6) 各隣接交差点のシ−ケンシャル番号
(7) 各隣接交差点までの距離(8) 各隣接交差点までの道路の属性(道路種別、幅員)
等を有し、経路探索処理において用いられる。尚、交差点ネットリストには上層用と下層用がある。
【0011】交差点ネットリストCRNLにおける(5) の上層ノード存在フラグは、図5に示すように下層での交差点CPB1の存在する道路RDが上層でも道路データで表現されており、かつ、交差点CPB1が上層で交差点CPAとして登録されている場合に「1」が立てられ、その他の場合は「0」とされる(図5のCPB2、CPB3の場合)。又、上層交差点シーケンシャル番号は、下層での交差点と同一の交差点について、上層で交差点ネットリストが作成されている場合に、該上層での交差点シーケンシャル番号を示すものである。
【0012】図2の戻り、12は自動車の現在地に応じた地図や自動車位置マ−ク、誘導経路等を描画するディスプレイ装置(CRT)、13は走行中の自動車の走行距離と方位に基づいて現在地を算出する現在地検出部である。現在地検出部13は、図示しないが、自動車の進行方位を検出する方位センサや走行距離を検出する車速センサ、方位や走行距離に基づいて自動車の現在地(経度、緯度)を算出する位置計算用CPUを有している。14は地図検索キー、地図スクロ−ルキー、経路探索キー、メニューキー等を備えたリモコンなどの操作部、15はナビゲーション制御装置であり、地図データに基づき車両現在地周辺の地図画像を発生すると共に、誘導経路を探索し、誘導経路画像や自動車位置マ−クを発生する。ナビゲーション制御装置15において、15aは現在地データに基づき、現在地周辺で画面表示範囲より広い範囲の地図データ(例えば9画面分の地図データ)をDVD 11から読出し、該地図データに基づいてドットイメ−ジの地図画像を発生する地図画像描画部である。
【0013】15bは誘導経路探索処理により得られた出発地から目的地までの誘導経路データに基づいて誘導経路画像を発生する誘導経路描画部、15cは地図画像及び誘導経路画像を記憶するビデオRAMである。地図画像描画部15aはディスプレイ画面の表示範囲がビデオRAM 15cの画像範囲を越えないように、自動車の走行に従って、随時、ビデオRAM 15cを書き替え、また誘導経路描画部15bも自動車の走行に応じて誘導経路画像を発生してビデオRAM 15cに記憶するようになっている。
【0014】15dは車両現在地がディスプレイ画面の固定点に位置するようにビデオRAM15cから1画面分の地図画像を読み出す読出制御部であり、読出し位置は地図画像描画部15aから指示される。15eはディスプレイ画面の固定点に自動車位置マ−クを表示するための自動車位置マ−ク発生部、15fは経路探索部であり、経路探索時に出発地と目的地が入力されると地図データに含まれる道路レイヤ情報に基づいて、出発地から目的地迄の最短経路を誘導経路として算出する。15gは出発地から目的地迄の誘導経路を構成するノ−ドを順次記憶する誘導経路記憶部である。15hは合成部であり、ビデオRAM15c、自動車位置マ−ク発生部15eからそれぞれ読出された地図画像及び誘導経路画像、自動車位置マ−ク画像、その他メニュー画像を適宜合成してCRT12に出力して表示する。
【0015】(C)経路探索処理図6は本発明の経路探索処理のフローである。本発明はダイクストラ法の探索手順を変形した亜流であり、ダイクストラ法の確実な最短経路を求める機能を弱め(放棄し)、広範囲に探索枝を広げる事に主眼を置いている。予め探索開始点を中心にした円(探索範囲円)を設定する(ステップ100)。ただし、探索範囲円の半径Aは探索開始点Ps(図1参照)と目的点Pdあるいはその近傍点を結ぶ直線距離とする。目的点は例えば下層と上層を連結する交差点である。
【0016】ついで、経路探索部15fは、検索次数iを0にし(0→i、ステップ101)、第i次交差点に隣接する交差点が存在するかを下層交差点ネットリストCRNL(図4)を参照して調べる(ステップ102)。0次交差点は出発点Psである。第i次交差点Piに隣接する交差点が存在すれば、出発点Psから第i次交差点Piを経由して隣接交差点Pn1までの累計距離Dを計算する(ステップ103)。出発点から第i次交差点までの距離d1は後述するように、該第i次交差点に対応させて記憶部15f-1に記憶してあり、また第i次交差点Piから隣接交差点Pn1までの距離d2は交差点ネットリストに記憶してあるから、次式d1+d2→Dにより出発点Psから隣接交差点Pn1までの累計距離Dが求まる。
【0017】ついで、出発点Psから隣接交差点Pn1までの直線距離Bを計算し(ステップ104)、次式C=D+k(A−B)
(kは係数)によりコストCを演算する(ステップ105)。kは(A−B)のコストに対する影響(効果)を調整する係数であり、kの大小により(A−B)の効果に強弱を与えることができ、計算された探索経路の品質と探索時間のバランスを調節することができる。ついで、隣接交差点Pn1の検索次数が(i+1)かチェックし(ステップ106)、(i+1)でなければ、隣接交差点に対応させて、以下のデータ(1) 現在着目している第i次交差点のシ−ケンシャル番号、(2) 出発点から当該隣接交差点までのトータルコストC、(3) 出発点から当該隣接交差点までの累計距離D、(4) 当該隣接交差点の検索次数としての(i+1)を記憶部15f-1に記憶し(ステップ107)、以後、ステップ102に戻り、着目している第i次交差点に隣接する交差点が、なお残存するか調べて以降の処理を繰り返す。
【0018】一方、ステップ106において、隣接交差点の次数が(i+1)の場合には、換言すれば、該隣接交差点が別の第i次交差点に隣接する交差点として参照されていれば(ステップ107で既に上記(1)〜(4) のデータが記憶されていれば)、該隣接交差点に対応して記憶してある出発点からのトータルコストC′とステップ105で求めたコストCの大小を比較する(ステップ108)。C<C′であれば、当該隣接交差点Pn1に対応して記憶部15f-1に記憶してある、第i次交差点のシ−ケンシャル番号を現在着目している第i次交差点のシ−ケンシャル番号で置き換えると共に、コストC′及び累計距離D′をC,Dで書き替え(C→C′,D→D′,ステップ109)、以後、ステップ102に戻り、着目している第i次交差点に隣接する交差点が、なお残存するか調べて以降の処理を繰り返す。又、C≧C′の場合には、当該隣接交差点に対応して記憶部15f-1に記憶してある内容を変更せずステップ102に戻る。
【0019】ステップ102において、着目している第i次交差点に隣接する交差点が存在しなくなれば、別の第i次交差点が存在するか調べ(ステップ110)、存在すれば、該別の第i次交差点を新たに第i次交差点として(ステップ111)、ステップ102以降の処理を繰り返す。ステップ110において、別の第i次交差点が存在しなければ、目的点Pdに到達したかチェックし、換言すれば第(i+1)次の交差点に目的点が含まれているかチェックし(ステップ112)、含まれていなければ検索次数を1つ歩進し(i+1→i,ステップ113)、ステップ102以降の処理を繰り返す。しかし、目的点に到達すれば、■目的点Pd→目的点(m次の交差点とする)に対応させて記憶してある(m−1)次の交差点→■該(m−1)次の交差点に対応させて記憶してある(m−2)次の交差点→・・・→■2次の交差点に対応させて記憶してある1次交差点→■該1次交差点に対応させて記憶してある0次の交差点(出発点)を順次接続してコストの小さい経路を決定し(ステップ114)、経路処理を終了する。
【0020】本発明によれば、着目交差点が探索開始地点から離れて探索範囲円の円周に近づくほどk(A−B)が小さくなる為、探索枝が円周方向へぐいぐい伸びるようになり、経路探索速度が向上する。以上、本発明を実施例により説明したが、本発明は請求の範囲に記載した本発明の主旨に従い種々の変形が可能であり、本発明はこれらを排除するものではない。
【0021】
【発明の効果】以上本発明によれば、k(A−B)をコストに含めたから、着目交差点が探索開始地点から離れて探索範囲円の円周に近づくほどk(A−B)が小さくなり、この結果、探索枝が円周方向へぐいぐい伸びるようになり、経路探索に要する計算量が減り、経路探索時間が短縮する。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013