JPH08122089A

JPH08122089A - 経路探索装置

Info

Publication number: JPH08122089A
Application number: JP26406194A
Authority: JP
Inventors: Takahiro Hashimoto; 孝博橋本
Original assignee: Toyota Motor Corp
Current assignee: Toyota Motor Corp
Priority date: 1994-10-27
Filing date: 1994-10-27
Publication date: 1996-05-17

Abstract

(57)【要約】【目的】領域分割された階層構造の地図データを用い
た経路探索装置において、不要な領域での経路探索を行
わず処理の効率化を図る。【構成】データ記憶装置２０は所定のエリアに領域分
割され、かつ、粗から密に順次階層構造をなす地図デー
タが格納され、制御コンピュータ１６はこの地図データ
を用いて現在地から目的地までの最適経路を算出し、出
力装置２２に出力する。制御コンピュータ１６は地図デ
ータのうち隣接する４つの領域を基本探索単位とし、現
在地側及び目的地側の基本探索単位が連続した位置関係
を示す最も粗の階層を上限階層として順次探索を行う。
また、基本探索単位内での到達した境界の位置関係に応
じて基本探索単位以外の領域での探索範囲を決定し、最
適経路が存在すると思われる領域のみで探索を行う。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は経路探索装置、特に領域
分割され、粗から密に階層構造をなす地図データを用い
て経路探索を行う装置に関する。

【０００２】

【従来の技術】従来より、メモリ容量の低減を図るため
に単位エリアごとに分割され、階層構造をなす地図デー
タを用いて出発地から目的地に至る経路を探索する経路
探索装置が知られている。粗い地図データ（下位階層デ
ータ）を用いて探索を行うと、探索のスピードアップを
図ることができるが、出発地から目的地に至る経路を探
索できない場合も生じ得る。一方、密（上位階層デー
タ）を用いれば出発地から目的地に至る経路を確実に探
索することは可能であるが、探索すべき経路が多く、最
終結果を得るまでに時間を要してしまう問題がある。従
って、短時間にかつ確実に出発地から目的地に至る経路
を探索するためにどの範囲の地図データを用いて探索を
行うかが重要な課題である。

【０００３】例えば、特開平５−１６５４０８号公報に
開示された車両走行案内装置では、領域分割された地図
上に設定された出発地と目的地を結ぶ直線が存在する１
又は２以上のエリアをもって探索領域を決定すると共
に、その領域内で経路探索が不能の時に探索領域を相似
的に拡大させ、あるいは予め探索領域を再設定する回数
又は大きさを制限し、その制限を越えた場合には経路探
索を行わない構成が提案されている。また、上記公報に
は、ある階層において経路探索が不能となった時に、道
路密度が高くなる次の階層に切り替えて経路探索を再実
行する構成も提案されている。

【０００４】

【発明が解決しようとする課題】しかしながら、一定領
域で経路探索が不能のときに探索領域を先の領域と相似
となるように拡大させるのでは、本来探索する必要のな
い無駄な領域までも探索領域として指定することにな
り、探索時間が大幅に増大してしまう問題がある。ま
た、単に粗から密に地図データを切り替えて探索する構
成においても、必要以上に密な地図データを用いて探索
を行うと、不必要に探索経路が増大してしまう問題が生
じる。

【０００５】本発明は上記従来技術の有する課題に鑑み
なされたものであり、その目的は必要最小限の階層の地
図データを用い、かつ不必要に探索領域を拡大すること
なく効率的に探索領域を決定でき、短時間で確実な探索
を行うことができる経路探索装置を提供することにあ
る。

【０００６】

【課題を解決するための手段】上記目的を達成するため
に、請求項１記載の経路探索装置は、領域分割され、粗
から密に階層構造をなす地図データを用いて出発地から
目的地に至る経路を探索する経路探索装置において、出
発地及び目的地を入力する地点入力手段と、前記地図デ
ータを格納する記憶手段と、前記地図データの内、前記
出発地を含む隣接４領域の地図データと前記目的地を含
む隣接４領域の地図データを抽出し、両地図データが連
続した位置関係を示す最も粗い階層を上限として順次粗
から密の階層で探索処理を行う処理手段と、を有するこ
とを特徴とする。

【０００７】また、上記目的を達成するために、請求項
２記載の経路探索装置は、請求項１記載の経路探索装置
において、前記処理手段は、前記隣接４領域の地図デー
タを用いて探索して得られた経路の領域境界の位置関係
に基づいて上限階層での前記隣接４領域以外の探索範囲
を決定する範囲決定部を有することを特徴とする。

【０００８】

【作用】請求項１記載の経路探索装置では、領域分割さ
れた階層構造の地図データの内、出発地を含む隣接４領
域の地図データ及び目的地を含む隣接４領域の地図デー
タを探索の基本領域として抽出する。そして、これら探
索の基本領域が連続した位置関係、すなわち両探索領域
が接するか又は重なる最も粗い階層を探索の上限として
粗から密の階層で探索を行う。

【０００９】これにより、不必要に密な階層で探索処理
を行うことがなく、効率的な探索を行うことができる。

【００１０】請求項２記載の経路探索装置では、出発地
を含む基本探索領域と目的地を含む基本探索領域が連続
した位置関係を示す上限階層での探索範囲を領域境界の
位置関係に基づいて決定する。すなわち、出発地を含む
基本探索領域での探索の結果、その領域での経路の境界
地が定まり、一方、目的地を含む基本探索領域において
も探索の結果経路の領域境界が決定される。これらの領
域境界に近接した領域のみを探索範囲として選択するこ
とにより，基本探索範囲以外の探索領域を不必要に拡大
させることなく、効率的な経路探索を行うことができ
る。

【００１１】

【実施例】以下、図面に基づき本発明の実施例について
説明する。

【００１２】図１には本実施例の構成ブロック図が示さ
れている。車両には位置センサ１０及びＧＰＳ１２が設
けられる。位置センサ１０としては、例えば車速センサ
やジャイロ等の方位センサが用いられ、位置センサ１０
及びＧＰＳ１２により車両の現在走行位置が検出され
る。位置センサ１０及びＧＰＳ１２からの検出信号は制
御コンピュータ１６に出力される。一方、車両運転席近
傍にはキーボードやＣＲＴ等の表示装置に表示されたタ
ッチスイッチなどからなる入力装置１４が設けられ、車
両運転者が入力したデータが制御コンピュータ１６に出
力される。また、ＲＯＭ等のデータ記憶装置２０には地
図データが格納されており、制御コンピュータ１６はデ
ータ記憶装置２０から地図データを読み出して検出され
た現在位置とともに出力装置（表示装置）２２に重畳し
て表示すると共に、地図データをメモリ１８に格納し、
入力された目的地に至るまでの経路を後述する処理に従
って算出し、出力装置２２に表示する。

【００１３】図２にはデータ記憶装置２０に格納されて
いる地図データの概念説明図が示されている。図２
（Ａ）、（Ｂ）に示されるように、地図データは所定の
エリア毎に領域分割され、かつ階層構造をなして格納さ
れている。図２（Ａ）が密な上位階層であり、図２
（Ｂ）が粗な下位階層である。このような構造を繰り返
すことにより、任意の階層数で地図データを階層化する
ことができる。

【００１４】なお、データ記憶装置２０の容量は車載と
いう観点から制約されるため、地図データでの経路の探
索範囲は任意に拡大することはできない。そこで、本実
施例においては、図２（Ａ）、（Ｂ）の斜線で示すよう
に隣接する４つの矩形領域を探索単位とし、各階層での
経路探索はこれら隣接する４つの領域内で行われる。

【００１５】図３にはある階層における出発地（現在
地）Ｏと目的地Ｄを含む隣接する４つの領域が示されて
おり、上述したように本実施例においてはこれら出発地
及び目的地を含む隣接４領域が基本探索単位となる。そ
して、これら基本探索単位はある領域内における出発地
や目的地の位置に応じて決定される。図３（Ｂ）にはあ
る領域を〜の４つの小領域にさらに分割した説明図
が示されており、出発地Ｏ、目的地Ｄがこれら〜の
いずれの小領域に属するかによって基本探索単位が決定
される。例えば、出発地Ｏが図３（Ｂ）の小領域に属
する場合には、基本探索単位は図３（Ｃ）に示すような
ものとなる。また、出発地Ｏが図３（Ｂ）の小領域に
属する場合には、基本探索単位は（Ｄ）に示すものとな
る。また、出発地Ｏが小領域に属する場合には、図３
（Ｅ）のような基本探索単位となり、小領域に属する
場合には、図３（Ｆ）に示すような基本探索単位とな
る。このように、ある領域内における出発地あるいは目
的地の位置に応じて基本探索単位を決定することによ
り、無駄な領域を探索することを防ぎ、かつ経路の存在
する可能性の高い領域を基本探索単位として含むことに
より確実な経路探索が可能となる。

【００１６】以上のようにして基本探索単位が決定され
ると、次にこれら基本探索単位内で周知の経路探索法
（例えばダイキストラ法）を用いて探索を行い、ある階
層にて経路探索が不能の場合には順次道路が密な上の階
層で経路探索処理が行われるが、必要以上に上位の階層
で経路探索を行っても、探索処理に要する時間が増大す
る。

【００１７】そこで、本実施例においては、出発地及び
目的地基本探索単位の位置関係により探索に使用する階
層の上限を決定している。

【００１８】図４には本実施例において上限となり得る
階層の基本探索単位の位置関係のパターンが示されてい
る。図４（Ａ）は出発地Ｏ側の基本探索単位と目的地Ｄ
側の基本探索単位が完全に一致する場合、同図（Ｂ）は
出発地Ｏ側の基本探索単位と目的地Ｄ側の基本探索単位
が２つの領域で重複する場合、同図（Ｃ）は出発地Ｏ側
の基本探索単位と目的地Ｄ側の基本探索単位が１つの領
域において重複する場合、同図（Ｄ）は出発地Ｏ側の基
本探索単位と目的地Ｄ側の基本探索単位が２つの領域で
接する場合、同図（Ｅ）は出発地Ｏ側の基本探索単位と
目的地Ｄ側の基本探索単位が１つの領域において接する
場合である。これら図４（Ａ）〜（Ｅ）に共通する性質
は、いずれも出発地Ｏ側の基本探索単位と目的地Ｄ側の
基本探索単位が連続した位置関係を示すことであり、こ
れらパターンのうちいずれかの位置関係を示す最も下位
の階層が探索の上限階層として決定される。このように
探索階層の上限を決定することにより、必要以上に上の
階層での無駄な探索を省くことができ、探索の効率化を
図ることが可能となる。

【００１９】図５には本実施例における経路探索の概念
図が示されている。上限の階層より下の階層の地図デー
タを用いた探索では、基本探索単位内のみを周知の経路
探索法（例えばダイキストラ法）で探索し、上の階層と
データ的に繋がりのあるノードがすべて展開されたとき
に上位の階層へ移行して探索を続行する。そして、上限
の階層においては、出発地Ｏ側の基本探索単位を移動さ
せながら探索範囲を決定してダイキストラ法等で経路探
索し、探索された経路と目的地Ｄ側ですでに探索された
経路が接続した場合に、接続した経路の総コスト＜出発地Ｏ側の未確定ノードの最小ラベルコスト＋目的地Ｄ側の未確定ノードの最小ラベルコスト（１）の条件（最適条件）を満たすか否かを判断する。上記の
条件を満たすときには得られた経路を案内経路として出
力装置２２に表示し、上記の条件を満たさなければ経路
探索処理を続行する。

【００２０】ここで、上述したように上限の階層におい
ては基本探索単位を移動して探索範囲を決定し、経路探
索処理を行うが、上限における基本探索単位の位置関係
が例えば図４（Ｃ）に示すようなものであった場合、探
索単位を移動する方法として図６（Ａ）、（Ｂ）に示さ
れるような２通りの方法が考えられる。すなわち、図６
（Ａ）のように基本探索単位を右方向に移動した後目的
地Ｄ側の基本探索単位に一致させる方法であり、もう一
つは図６（Ｂ）のように基本探索単位を下方に移動させ
た後、目的地Ｄ側の基本探索単位に一致させる方法であ
る。もちろん、これら２通りの方法で得られた経路のコ
ストを各々算出して比較し、よりコストの小さいほうを
案内経路とすることも可能である。しかしながら、常に
２通りの経路を計算するのは効率が悪く、最終的に案内
経路を得るのに時間がかかる問題がある。そこで、本実
施例においては、案内経路が存在しないと思われる領域
を探索しないような処理を行って一層の効率化を図って
いる。

【００２１】以下、案内経路が存在しないと推測される
領域の探索を行わない処理の方法を順次説明する。

【００２２】第１処理方法図７には本方法における探索範囲決定の概念図が示され
ている。なお、図７において示したのは、上限階層のパ
ターンが図４（Ｃ）の場合である。図７（Ａ）に示され
るように、現在地（出発地）Ｏ側の基本探索単位内で探
索された経路が最初に基本探索単位の境界に到達した点
が図中Ａであり、このＡを含む境界がａであったとす
る。一方、目的地Ｏ側の基本探索単位内で探索された経
路が最初に基本探索単位の境界に到達した点が図中Ｃで
あり、このＣを含む境界がｃであったとする。この場
合、探索すべき領域は境界ａ及び境界ｃを含む領域であ
り、図６（Ａ）、（Ｂ）に示された２通りの探索領域の
うち、最適経路は図６（Ａ）に示される探索領域にある
と推定され、図６（Ｂ）の探索領域には最適経路はない
と推定されて探索は行われない。

【００２３】また、図７（Ｂ）に示されるように、現在
地Ｏ側の基本探索単位内で探索された経路が最初に基本
探索単位の境界に到達した点が図中Ｂであり、このＢを
含む境界がｂであったとする。一方、目的地Ｄ側の基本
探索単位内で探索された経路が最初に基本探索単位の境
界に到達した点が図中Ｄであり、このＤを含む境界がｄ
である場合、探索すべき領域は境界ｂ及び境界ｄを含む
領域であり、この場合には図６（Ｂ）に示される範囲が
探索範囲として選択される。

【００２４】また、図７（Ｃ）に示されるように現在地
Ｏ側の基本探索単位内で探索された経路が最初に境界に
到達する点がＥであり、目的地Ｄ側の基本探索単位内で
探索された経路が最初に境界に到達した点が図中Ｆであ
るような、それぞれの地点を含む境界が連続した位置に
ない場合には、図６（Ａ）、（Ｂ）のいずれで探索され
る経路が最適か判断できないので、いずれの探索範囲も
探索し、両経路コストを比較して最終的な案内経路を決
定する。

【００２５】このように、本第１処理方法では現在地Ｏ
側及び目的地Ｄ側それぞれの探索経路の領域境界の位置
関係に基づいて最適な経路が存在するであろう領域を推
定することにより、無駄な探索を省略して効率化を図る
ものである。

【００２６】以下、上述した探索処理を図８乃至図１２
のフローチャートを用いてより詳細に説明する。

【００２７】図８は本第１処理方法の全体処理フローチ
ャートである。まず、地図データの最下位において目的
地Ｄ側の基本探索単位内をダイキストラ法等を用いて経
路探索を行う（Ｓ１０１）。この時、展開ノードが図７
に示すような境界ｃあるいは境界ｄに到達するまで探索
を行う。境界ｃ又は境界ｄに到達して探索を終了した場
合には（Ｓ１０２）、次に現在地Ｏ側の基本探索単位を
同様にして探索する（Ｓ１０３）。一方、目的地Ｄ側の
基本探索単位を探索しても境界ｃ又は境界ｄに到達せず
に終了した場合には、現階層においては最適経路が存在
しないと判定し、階層を１つ上にあげて探索をやり直す
（Ｓ１１９）。

【００２８】現在地Ｏ側の基本探索単位を探索した結
果、経路Ｒ（０）（経路Ｒ（０）については後述する）
が確定した場合には、その経路を案内経路として出力装
置２２に出力する（Ｓ１１４）。一方、経路Ｒ（ｉ）が
確定せず、かつ、ｉ＝０、すなわちどの境界に到達する
こともなく探索が終了した場合には、現階層において経
路は存在しないと判定し、１階層上の地図データ上で探
索をやり直す（Ｓ１１９）。ｉが０でない場合、すなわ
ちいずれかの境界に達した場合には、図６（Ａ）、
（Ｂ）に示すように探索単位を移動させながら１本目の
経路Ｒ（１）を探索する（Ｓ１０６）。この時、Ｓ１０
３にて最初に到達した境界が境界ａの場合には図６
（Ａ）の探索範囲を選択し、最初に到達した境界がｂの
場合には図６（Ｂ）に示される探索範囲を選択して探索
を行う（Ｓ１０６）。なお、到達境界数ｉ＝１の場合、
これはＳ１０３の探索処理で探索が終了するまでに境界
ａ又は境界ｂのいずれか一方の境界に到達したことを意
味する。この時、Ｓ１０６の探索結果Ｒ（１）があれば
他の方向には経路が存在しないこととなり、従ってこの
経路Ｒ（１）を案内経路とする（Ｓ１０７、Ｓ１１３、
Ｓ１１５）。一方、探索経路Ｒ（１）が存在しない場合
には、他の方向にも経路が存在しないので、地図データ
を１階層上にあげて探索をやり直す（Ｓ１１９）。

【００２９】ｉが１でない場合も、Ｓ１０６の探索結果
Ｒ（１）の有無によって処理が分かれ（Ｓ１０８）、探
索結果Ｒ（１）が存在しない場合には、２本目の経路Ｒ
（２）の探索を行う（Ｓ１１６）。この時、Ｓ１０６で
の１本目の探索処理において図６（Ａ）に示す探索範囲
を選択した場合にはＳ１１６の探索処理では図６（Ｂ）
に示す探索範囲を選択し、Ｓ１０６での１本目の探索処
理において図６（Ｂ）に示す探索範囲を選択した場合に
はＳ１１６では図６（Ａ）に示す探索範囲を選択して探
索を行う。２本目の経路Ｒ（２）を探索した結果、経路
Ｒ（２）が存在する場合にはこの経路を案内経路として
出力し（Ｓ１１８）、経路Ｒ（２）が存在しない場合に
は、地図データを１階層上にあげて探索をやり直す（Ｓ
１１９）。

【００３０】一方、Ｓ１０８にて経路Ｒ（１）が存在す
る場合には、次に目的地Ｄ側の領域境界Ｘが境界ｃに属
し、かつ現在地Ｏ側の領域境界Ｙが境界ａに属すか、あ
るいはＸが境界ａに属し、かつ領域境界Ｙが境界ｂに属
すか否かを判定する（Ｓ１０９）。領域境界Ｘ、Ｙがこ
れらの条件を満たす、すなわち図７（Ａ）、（Ｂ）のい
ずれかである場合には、経路Ｒ（１）を案内経路として
出力する（Ｓ１１５）。また、領域境界がこれらの条件
を満たさない場合、すなわち図７（Ｃ）のような場合に
は、２本目の経路Ｒ（２）を探索する（Ｓ１１０）。経
路Ｒ（２）が存在しない場合には、先に求められた経路
Ｒ（１）を案内経路とし（Ｓ１１５）、経路Ｒ（２）が
存在する場合には、経路Ｒ（１）のコストと経路Ｒ
（２）を大小比較し、コストの小さい経路を案内経路と
して出力する（Ｓ１１１、Ｓ１１２、Ｓ１１５、Ｓ１１
８）。

【００３１】図９には図８におけるＳ１０１の詳細な処
理フローチャートが示されている。まず、目的地Ｄ側の
基本探索単位を探索範囲として設定し（Ｓ２０１）、ノ
ード展開を順次繰り返して探索を行っていく（Ｓ２０
２、Ｓ２０３）。そして、展開するノードが境界ｃ又は
境界ｄに到達したか否かを判定し（Ｓ２０４、Ｓ２０
５）、境界に到達した場合にはそのノードが属する境界
をＸとする（Ｓ２０６）。一方、展開するノードが境界
ｃ又は境界ｄに到達する前に探索が終了した場合には、
そのまま処理を終了する。

【００３２】図１０には図８におけるＳ１０３の詳細な
処理フローチャートが示されている。まず、未到達の境
界Ｂをａ、ｂとし、また到達した境界の数ｉに０を入れ
て初期化する（Ｓ３０１）。そして、現在地Ｏ側の基本
探索単位を探索範囲として（Ｓ３０２）ノード展開を繰
り返し探索を行う（Ｓ３０３〜Ｓ３０４）。そして、次
に展開するノードが基本探索単位の境界であるか否かを
判定し（Ｓ３０５）、探索範囲の境界である場合にはそ
の境界をｙとして（Ｓ３０６）、ｙがＢの要素であるか
否か、すなわちｙが未到達境界か否かを判定する（Ｓ３
０７）。ｙが未到達境界、すなわち初めて到達した境界
である場合には、未到達境界データＢから境界ｙを削除
すると共に、到達した境界数ｉを１だけインクリメント
する（Ｓ３０８）。そして、現時点での探索状況をＭ
（ｉ）としてメモリ１８に記憶する（Ｓ３０９）。この
時、ｉのカウントにより一番目の境界に到達したときは
Ｍ（１）、２番目の境界に到達したときはＭ（２）とな
る。次に、到達した境界数ｉが１であるか否かを判定し
（Ｓ３１０）、ｉ＝１の時、すなわち始めて境界に到達
したときはその境界ｙをＹと置き換える（Ｓ３１１）。

【００３３】一方、Ｓ３０５にて次に展開するノードが
探索範囲の境界でない場合にはさらにノードを展開し
（Ｓ３１２）、目的地Ｄ側から探索している経路と接続
したか否か、すなわち展開したノードが目的地側から探
索して得られた経路のノードと一致するか否かを判定す
る（Ｓ３１３）。展開したノードが目的地Ｄ側から探索
して得られた経路と接続している場合には、最適経路の
条件（１）を満たしているか否かを判定し（Ｓ３１
４）、満たしている場合には求められた経路を案内経路
として処理を終了する（Ｓ３１５）。

【００３４】図１１及び図１２には図８におけるＳ１０
６の詳細な処理フローチャートが示されている。Ｓ１０
６ではＳ１０３の途中結果を引き継いで探索を続行する
ことになる。すなわち、まず途中結果Ｍ（１）をメモリ
１８から読み込み、その状態から探索を開始する（Ｓ４
０１）。なお、途中結果Ｍ（１）はＳ１０３での現在地
Ｏ側の基本探索単位を探索して最初に境界に到達したと
きの状況である。次に、最初の探索範囲を決定する。こ
の時、Ｓ１０３の処理で最初に到達した境界Ｙがａの場
合には探索範囲は図６（Ａ）に示される範囲（便宜上探
索範囲とする）となり、最初に到達した境界Ｙがｂの
場合には図６（Ｂ）に示す探索範囲（探索範囲とす
る）となる（Ｓ４０２）。以下、このようにして決定さ
れた探索範囲での経路探索を行い（Ｓ４０３、Ｓ４０
４）、次に展開するノードが探索範囲の境界であるか否
かを判定する（Ｓ４０５）。探索範囲の境界である場合
には、さらに最初に到達した境界Ｙがａであるか否かが
判定され（Ｓ４０６）、Ｙ＝ａの場合には次に展開する
ノードが境界ｅかどうかを判定し（Ｓ４０８）、Ｙ＝ａ
でない、すなわちＹ＝ｂの場合には、さらに次に展開す
るノードが境界ｆであるか否かが判定される（Ｓ４０
７）。Ｙ＝ａであり、かつその境界がｅである場合、及
びＹ＝ｂであり、かつその境界がｆである場合には、連
続した経路で目的地側の基本探索単位内に到達したこと
を意味するから新たな探索範囲を目的地側の基本探索単
位とする（図１２のＳ５０１）。

【００３５】一方、Ｓ４０５にて次に展開するノードが
探索範囲の境界でないと判定された場合には、ノードを
展開し（Ｓ４０９）、目的地側から探索している経路と
接続したか否かを判定する（Ｓ４１０）。目的地側から
探索している経路と接続しており、かつ最適経路の条件
（１）を満たしている場合には（Ｓ４１１）、求められ
た経路を１本目の経路Ｒ（１）とする（Ｓ５０７）。境
界に到達せず、また経路も求められずに探索を終了した
場合には、そのまま処理を終了する。

【００３６】Ｓ５０１にて探索範囲を目的地側の基本探
索単位とした場合、この基本探索単位内で経路探索処理
が行われる（Ｓ５０２、Ｓ５０３）。そして、目的地側
から探索している経路と接続したか否かを判定し（Ｓ５
０５）、接続した経路が最適経路の条件（１）を満たし
ている場合には、求められた経路を探索結果Ｒ（１）と
する（Ｓ５０６、Ｓ５０７）。

【００３７】図８のＳ１１６での２本目の経路Ｒ（２）
の探索処理は、上述した１本目の経路Ｒ（１）を探索す
る処理（Ｓ１０６）のフローチャートとほぼ同様であ
り、Ｓ４０１における途中結果Ｍ（１）をＭ（２）と
し、Ｓ４０２における探索範囲をＹ＝ａの時、Ｙ＝ｂ
の時に設定し、Ｓ４０６での判断処理をＹ＝ｂか否か
とし、さらにＳ５０７における算出経路を探索結果Ｒ
（２）と設定すればよい。

【００３８】以上のように、本第１処理方法において
は、目的地側の基本探索単位及び現在地側の基本探索単
位内でそれぞれ経路探索処理を行い、それぞれの到達境
界の位置関係に応じて基本探索単位以外の領域の探索領
域を決定して最終的な経路を得るため、経路が存在しな
いであろうと推定される不要な領域まで探索処理を行う
ことがなく、短時間で効率的な経路探索処理を行うこと
が可能となる。

【００３９】第２処理方法上述した第１処理方法では現在地Ｏ側及び目的地Ｄ側そ
れぞれの探索状況に基づき最適な経路が存在する領域を
推測したが、本第２処理方法では現在地Ｏ側又は目的地
Ｄ側いずれか一方の探索状況に基づき最適経路が存在す
る領域を推測する。

【００４０】図１３には本第２処理方法の概念図が示さ
れている。図１３（Ａ）に示されるように、現在地Ｏ側
から展開されている経路が基本探索単位の境界ｂに到達
する前に境界ａにｋ回到達した場合を想定する。図にお
いては、ｋ＝３とし、到達点をＡ１、Ａ２、Ａ３として
いる。この時、探索される領域は図６（Ａ）に示される
領域であり、図６（Ｂ）に示される領域は最適経路が含
まれないと推測して探索を行わない。同様に、図１３
（Ｂ）に示されるように現在地Ｏ側から展開されている
経路が境界ａに到達する前に境界ｂにＢ１、Ｂ２、Ｂ３
と到達した場合には、最適な経路は図６（Ｂ）に示され
る領域に含まれていると推測し、図６（Ａ）に示される
探索は行わない。一方、図１３（Ｃ）に示されるよう
に、境界ａ、ｂにそれぞれ１回ずつ到達（Ａ、Ｂ）した
場合には、図６（Ａ）、（Ｂ）のいずれの探索範囲が最
適か判断できないので、いずれの領域をも探索してコス
トを比較して決定する。

【００４１】このように、本第２処理方法では、境界に
到達する頻度に応じて探索領域を決定するため、現在地
側あるいは目的地側いずれか一方の探索状況のみで最適
経路が存在する領域を決定することができ、効率的な探
索を行うことができる。

【００４２】以下、図１４乃至図１６の処理フローチャ
ートを用いて本第２処理方法を詳細に説明する。

【００４３】図１４には全体処理フローチャートが示さ
れている。まず、第１処理方法と同様に目的地側の基本
探索単位を探索する（Ｓ６０１，Ｓ６０２）。次に、現
在地Ｏ側の基本探索単位を探索し（Ｓ６０３）、探索結
果Ｒ（０）が求められた場合には、経路Ｒ（０）を案内
経路として出力する（Ｓ６０４、Ｓ６１６）。探索結果
Ｒ（０）が存在しない場合、境界に到達せずに終了した
とき、すなわちｉ＝０のときは一階層上で探索をやり直
す（Ｓ６２０）。さらに到達した境界の数ｉが所定値ｋ
であるか否かを判定し（Ｓ６０６）、Ｒ（０）が求めら
れる前に図１３（Ａ）あるいは図１３（Ｂ）のいずれか
の状況となった場合には、１本目の経路Ｒ（１）を探索
し、求められた場合には１本目の経路Ｒ（１）を案内経
路として出力する（Ｓ６１２、Ｓ６１３、Ｓ６１８）。
１本目の経路Ｒ（１）が求められなかった場合には、Ｓ
６１０における１本目の経路探索とは異なる方向の経路
を探索し、２本目の経路Ｒ（２）が求められた場合には
その経路Ｒ（２）を案内経路とする（Ｓ６１４、Ｓ６１
５、Ｓ６１９）。１本目の経路Ｒ（１）及び２本目の経
路Ｒ（２）いずれも求められない場合には、地図データ
を１階層上にあげて探索を再びやり直す（Ｓ６２０）。

【００４４】なお、Ｓ６１２での探索処理は、到達点が
境界ａ又は境界ｂのいずれに属するかによって決定さ
れ、図１３（Ａ）に示すような場合には図６（Ａ）の領
域で経路探索が行われ、図１３（Ｂ）に示されるような
状況では図６（Ｂ）に示される領域で探索が行われる。

【００４５】一方、Ｓ６０６にて連続して到達した境界
の数ｉが所定値ｋでない場合、例えば図１３（Ｃ）に示
されるように最初の到達点がＡであり、次の到達点がＢ
であるような場合には、１本目の経路Ｒ（１）及び２本
目の経路Ｒ（２）を探索し、両経路のコストを比較して
コストの小さいほうを案内経路として出力する（Ｓ６０
７〜Ｓ６１１、Ｓ６１８、Ｓ６１９）。経路Ｒ（１）、
Ｒ（２）ともに存在しない場合には、地図データを１階
層上にあげて探索をやり直す（Ｓ６２０）。

【００４６】図１５にはＳ６０３での現在地側の基本探
索単位を探索する処理の詳細なフローチャートが示され
ている。まず、未到達の境界Ｂをａ、ｂとし、一方の境
界に連続して到達した回数ｉを０として初期化する（Ｓ
７０１）。次に、現在地側の基本探索単位を探索範囲と
してノード展開を繰り返し探索を実行する（Ｓ７０２〜
Ｓ７０４）。そして、次に展開するノードが探索範囲内
の境界である場合には、境界をｙとして（Ｓ７０５、Ｓ
７０６）、ｉが０か否かを判定する（Ｓ７０７）。ｉが
０、すなわち最初に境界に達した場合には、さらにその
境界がＢに属すか否か、すなわち境界がａ又はｂである
か否かを判定する（Ｓ７１１）。最初に到達した境界が
ａ又はｂである場合には、現在の探索状況をＭ（１）と
してメモリに記憶する（Ｓ７１２）。そして、そのとき
の境界をＹとし、到達した境界をＢから削除するととも
に、到達回数ｉを１だけインクリメントする（Ｓ７１
３）。一方、Ｓ７０７にてｉが０でない、すなわち既に
ａかｂの境界に到達している場合には、Ｙとｙが一致す
るか否か、すなわち到達した境界が最初に到達した境界
と同一か否かを判定し（Ｓ７０８）、同一である場合に
は到達回数ｉを１だけインクリメントし（Ｓ７１１）、
所定値ｋと等しくなるまでこれらの処理を繰り返す（Ｓ
７１８、Ｓ７１９）。そして、到達回数ｉがｋ（例えば
ｋ＝３）に達した場合には、そのときの探索状況をＭ
（３）とおいてメモリに記憶し探索を終了する（Ｓ７２
０）。一方、Ｓ７０８にて到達した境界ｙが最初に到達
した境界Ｙと同一でない場合には、到達した境界ｙがＢ
に属するか否か、すなわち最初に到達した境界と異なる
境界であるか否かを判定し（Ｓ７０９）、もう一方の異
なる境界である場合には、そのときの探索状況をＭ
（２）とおいてメモリに記憶し探索を終了する（Ｓ７１
０）。

【００４７】なお、Ｓ７０５にて次に展開するノードが
探索範囲内の境界でない場合には、さらにノードを展開
し（Ｓ７１４）、目的地側から探索している経路と接続
したか否かを判定する（Ｓ７１５）。そして、目的地側
から探索している経路と接続した場合には、最適経路の
条件（１）を満たしているか否かを判定し（Ｓ７１
６）、満たしている場合には求められた経路を探索結果
Ｒ（０）として出力する（Ｓ７１７）。

【００４８】図１６には図１４におけるＳ６１２の探索
処理の詳細フローチャートが示されている。このＳ６１
２ではＳ６１０にて行われた１本目の経路Ｒ（１）探索
とは別方向の経路Ｒ（２）を探索する必要があり、図１
５に示されたＳ７２０にてメモリに記憶された途中の探
索状況Ｍ（３）から現在地側の基本探索領域の探索を行
う（Ｓ８０１、Ｓ８０２）。現在地側の基本探索単位を
探索単位としてノード展開を繰り返して探索を続行し
（Ｓ８０３、Ｓ８０４）、次に展開するノードが探索範
囲の境界である場合には（Ｓ８０５）、境界をｙとし
（Ｓ８０６）、到達境界ｙが未到達のノードＢに属して
いるか否かを判定する（Ｓ８０７）。そして、到達境界
ｙが境界ａである場合には図６（Ａ）に示された領域を
探索範囲とし、一方到達境界ｙが境界ｂの場合には図６
（Ｂ）に示された探索範囲として選択し（Ｓ８０８）、
探索を続行する（Ｓ８０９）。一方、Ｓ８０５にて次に
展開するノードが探索範囲の境界でない場合には、さら
にノードを展開し（Ｓ８１０）、目的地側から探索して
いる経路と接続したか否かを判定する（Ｓ８１１）。目
的地側から探索している経路と接続した場合には最適経
路の条件（１）を満たしているか否かを判定し（Ｓ８１
２）、満たしている場合には求められた経路を探索結果
Ｒ（２）としてその経路を案内経路とする（Ｓ８１
３）。

【００４９】このように、本第２処理方法においては現
在地側あるいは目的地側の基本探索単位の探索において
到達境界が一方の境界に頻繁に生じる場合には、最適経
路の存在する可能性が高いと推測して他の方向の探索は
行わないようにするため、不要な領域の探索を行うこと
なく効率的な経路探索を行うことができる。

【００５０】なお、本実施例においては上述した第１処
理方法及び第２処理方法を説明するに際し、上限の地図
データが図４（Ｃ）に示されるパターンの場合を例に取
り説明したが、他のパターンの場合も同様に処理するこ
とができることはいうまでもない。例えば、上限のパタ
ーンが図４（Ｅ）に示されるものであった場合には、探
索範囲は図１７（Ａ）、（Ｂ）の２通りを考えることが
でき、これらはそれぞれ図６（Ａ）、（Ｂ）に対応する
ものである。そして、第１処理方法、第２処理方法にお
いて到達境界の位置関係に応じて図１７（Ａ）、（Ｂ）
のいずれかを選択して探索範囲を移動させることによ
り、同様に効率的な経路探索を行うことができる。

【００５１】また、上限パターンが図４（Ａ）、
（Ｂ）、（Ｄ）のいずれかの場合には、２本目の経路Ｒ
（２）を計算する必要がないので、第１処理方法、第２
処理方法において２本目の経路を算出する処理を省略す
れば同様に最適経路を求めることが可能である。

【００５２】以上本発明の実施例について説明したが、
本実施例には特許請求の範囲に記載された技術事項以外
に以下のような実施態様が含まれることを付記してお
く。

【００５３】（１）請求項２記載の経路探索装置におい
て、前記範囲決定部は、出発地側の領域境界と目的地側
の領域境界をともに含む領域を探索範囲として決定する
ことを特徴とする経路探索装置。

【００５４】（２）請求項２記載の経路探索装置におい
て、前記範囲決定部は、出発地側の領域境界あるいは目
的地側の領域境界の出現頻度の高い領域を探索範囲とし
て決定することを特徴とする経路探索装置。

【００５５】

【発明の効果】以上説明したように、請求項１乃至請求
項２記載の経路探索装置によれば、必要以上に密な地図
データを用いて経路探索を行うことがなく、また、最適
経路が存在しないと考えられる不要な領域まで探索範囲
を拡大して探索処理を行うことがないので、極めて効率
的な経路探索を行い最適経路を車両運転者などに報知す
ることができる。

【図面の簡単な説明】

【図１】本発明の実施例の構成ブロック図である。

【図２】同実施例における地図データの階層構造を示す
説明図である。

【図３】同実施例における地図データ上の探索単位説明
図である。

【図４】同実施例における上限地図データのパターンを
示す説明図である。

【図５】同実施例における探索処理の概念説明図であ
る。

【図６】同実施例における探索範囲の移動説明図であ
る。

【図７】同実施例における第１方法の概念説明図であ
る。

【図８】同実施例における第１方法の処理フローチャー
トである。

【図９】同実施例における第１方法の処理フローチャー
トである。

【図１０】同実施例における第１方法の処理フローチャ
ートである。

【図１１】同実施例における第１方法の処理フローチャ
ートである。

【図１２】同実施例における第１方法の処理フローチャ
ートである。

【図１３】同実施例における第２方法の概念説明図であ
る。

【図１４】同実施例における第２方法の処理フローチャ
ートである。

【図１５】同実施例における第２方法の処理フローチャ
ートである。

【図１６】同実施例における第２方法の処理フローチャ
ートである。

【図１７】同実施例における他の探索範囲移動説明図で
ある。

【符号の説明】

１０位置センサ１２ＧＰＳ１４入力装置１６制御コンピュータ１８メモリ２０データ記憶装置２２出力装置

Claims

【特許請求の範囲】

【請求項１】領域分割され、粗から密に階層構造をな
す地図データを用いて出発地から目的地に至る経路を探
索する経路探索装置において、出発地及び目的地を入力する地点入力手段と、前記地図データを格納する記憶手段と、前記地図データの内、前記出発地を含む隣接４領域の地
図データと前記目的地を含む隣接４領域の地図データを
抽出し、両地図データが連続した位置関係を示す最も粗
い階層を上限として順次粗から密の階層で探索処理を行
う処理手段と、を有することを特徴とする経路探索装置。
【請求項２】請求項１記載の経路探索装置において、前記処理手段は、前記隣接４領域の地図データを用いて
探索して得られた経路の領域境界の位置関係に基づいて
上限階層での前記隣接４領域以外の探索範囲を決定する
範囲決定部を有することを特徴とする経路探索装置。