JPS63200207A - 移動経路探索方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔目次〕 概要 産業上の利用分野 従来の技術（第１１図） 発明が解決しようとする問題点 問題点を解決するための手段（第１図）作用 実施例 （ａ）経路探索方法の説明 （第２図、第３図、第４図、第５図） （ｂ）経路探索処理の説明 （第６図、第７図、第８図、第９図、第１０図）（Ｃ）
他の実施例の説明 発明の効果 〔概要〕 移動環境を記述した地図を用いて、障害物を回避した出
発点から目標点に到る移動経路を探索する方法において
、メツシュ分割し、格子点座標で障害物を記述した地図
を用い、格子点座標で探索点を生成しながら、障害物を
回避し且つ移動コストが最小となる連続する候補点群を
移動経路として選定することによって、最短経路を確実
に探索するものである。

〔産業上の利用分野〕

本発明は、自走車等の移動体の移動経路を障害物等の移
動環境を記述した地図を参照して探索する移動経路探索
方法に関する。

オフィスや工場などにおいて、自走車が搬送の自動化の
ため広く利用されている。

このような自走車の移動経路は、−Ｃに経路をテープや
マークで設定し、自走車がこのテープやマークを検出し
て経路を走行する形式が採られている。

しかしながら、テープ等で経路を設定するものでは、経
路が固定化され、オフィス等のレイアウトの変更が頻繁
に行われる場合には、テープ等の移設というやっかいな
手間を要す。

このため、オフィス等で障害物を避けて任意の経路を走
行する自立型自走車が求められており、特にその移動経
路の探索技術の開発が要求されている。

〔従来の技術〕

係る経路の探索は、障害物の位置と形をデータベース化
して地図として保持し、自走車の位置と状態を参照する
ことによって実行されるものである。

この地図から移動経路を探索する方法として、従来第１
１図に示すものが知られている（例えば、情報処理学会
筒３２回全国大会論文番号５Ｎ−６参照）。

即ち、第１１図（Ａ）に示す如く、２つの障害物ＯＢＩ
、ＯＢ２をデータとして有する地図１に対し、出発点が
Ｐｓ、目標点がＰｆと与えられた場合には、先づ地図１
から第１１図（Ｂ）の如く地図１の領域の障害物ＯＢＩ
、ＯＢ２を除いた領域を長方形の領域Ａ、Ｂ、Ｃ，Ｄ、
Ｅ、Ｆに分割し、領域Ａ−Ｆ間を接続するネットワーク
を作る。

次に、領域Ａ−Ｆのネットワークを探索し、複数の領域
経路を求める。この場合、ＰｓからＰｆへ向かう領域経
路は、（ＡＣＦ）、（Ａ　ＣＤ　ＥＦ）、（ＡＢＤＣＦ
）、（ＡＢＤＥＦ）の４つである。

更にそれぞれの領域経路から走行経路ｒ１〜ｒ４を第１
１図（Ｃ）の如く生成し、各々に対し距離等によるコス
ト評価を行い、第１１図（Ｄ＞の如く経路ｒ４を決定す
る。

〔発明が解決しようとする問題点〕

しかしながら、従来の方法は、障害物を除いた長方形領
域Ａ−Ｆのネットワークで移動経路の探索を行っている
ため、長方形領域内では壁などに平行にする経路しかと
れず、例えば斜め方向の経路がとれない等必ずしも探索
された経路が最短経路にならないという問題があった。

本発明は、与えられた出発点と目標点に対し、障害物を
回避した最短な移動経路を得ることができる移動経路探
索方法を提供することを目的とする。

〔問題点を解決するための手段〕

第１図は本発明の原理説明図である。

第１図（Ａ）に示す如く、本発明では、地図１として領
域をメツシュで分割し、格子点座標で障害物ＯＢＩ〜Ｏ
Ｂ７を記述したものを用い、地図１上の格子点座標で経
路探索を行うようにしている。

この経路探索には、第１図（Ｂ）に示す如く、地図１上
の格子点座標で探索点を生成し、地図１上の障害物ＯＢ
Ｉ〜ＯＢ７を参照して探索点から移動可能な候補点を求
め、出発点Ｐｓから目標点Ｐｆまでの移動コストが最小
となる連続する候補点群（図の「×」印）を移動経路と
して選択するようにしている。

〔作用〕

本発明では、障害物を記述し且つメソシュ分割した地図
上の格子点座標で経路探索を行っているから、障害物領
域外では任意の経路がとれ、移動経路を最適に且つ最短
にすることができる。

又、地図上に通路でなく、障害物を記述するようにして
いるので、レイアウトの変更に応じた地図の書替えが容
易であり、特にビルの如き、複雑な場所の経路探索に有
効である。

〔実施例〕

（ａ）経路探索方法の説明 第２図は本発明方法のための一実施例システム構成図で
ある。

図中、１ａは地図メモリであり、格子点座標で障害物を
記述した地図１がデータとして格納されているもの、２
はプロセッサ（ＣＰ　Ｕ）であり、地図メモリ１ａの地
図１の書替えや選択経路の自走車との送受信の外に後述
する経路生成処理（第４図〜第６図）及び経路選択処理
（第７図）をプログラムの実行によって行うもの、３は
データ入力部であり、ディスプレイ、キーボードを有し
、目標点ｐｒや地図１の書替えのための障害物座標、及
び各種コマンドの入力を行うもの、４はデータメモリで
あり、探索点座標、候補点座標、探索進行方向、コスト
等の経路探索に必要なデータを格納しておくもの、５は
無線インターフェイス部であり、ＣＰＵ２と自走車との
間で無線により選択経路データ等のやりとりを行うもの
、６は自走車であり、四輪操舵により任意の方向へ移動
できる移動ロボットで構成され、ＣＰＵ２の経路データ
に従って移動するものである。

尚、ＭＡは移動領域であり、例えばオフィス内の部屋の
エリアであり、ＯＢは障害物であり、移動領域ＭＡに設
けられた机、棚、植物等である。

第３図は本発明による一実施例地図の説明図である。

地図１は、第３図に示す如く、領域がＸ、Ｙ方向とも１
０分割されたメツシュで分割され、メソシュの二次元格
子点座標（Ｘ、Ｙ）で障害物の位置及び範囲が記述され
る。

例えば、障害物の１行目のデータは、Ｘ座標が１のライ
ン上では、Ｙ座標１〜２と８〜９の位置に障害物が存在
するとして、（１、〔１，２〕、〔８，９〕）と記述さ
れ、以下同様である。

又、出発点（現在点）Ｐｓは第３図では、Ｘ＝１、Ｙ＝
３、目標点はＸ＝７、Ｙ＝７で表現される。

地図メモリ１ａには、上述の障害物の位置、範囲がデー
タとして格納されている。

第４図及び第５図は経路探索動作の説明図である。この
ような地図を利用した経路の探索は、経路生成と経路選
択から成り、経路生成は、基本的に格子点を利用した横
形探索法を用いている。横形探索は全ての可能性を並行
に処理するので、最適解を求めることが可能である。

又、経路選択における最適な経路を選択するためのコス
トとしては、距離や曲がる回数、通過の容易さなどが考
えられるが、距離だけを考えることにした。

地図１上での自走車の移動方向は、第４図（Ａ）に示す
如く、８方向のみを考え、メツシュの交点以外を通る経
路は除外しである。

そして、隣接する各点への移動に対し、メツシュの縦横
方向は「２」、対角線方向は「３」のコストを与えてい
る。

経路探索を行うには、出発点Ｐｓから探索エリアを外側
に拡大して、探索点を生成する。第４図（Ａ）及び第５
図（Ａ）に示す如く、出発点Ｐｓから先づ第１ステツプ
として黒丸の探索点を生成し、次のステップでその外側
のバラ印の探索点を生成する。

各ステップで生成した探索点は障害物領域内かを地図１
上の障害物データでチェックされ、障害物領域内でない
移動可能領域にある探索点が候補点として残される。そ
して次のステップでこの残された探索点である候補点に
対しその周囲の探索点が生成される。

この探索点の生成において、探索開始点（出発点）Ｐｓ
では、第４図（Ａ）に示す如く、その廻りの８ケの点Ｐ
ｓｉ−Ｐｓ８の生成が必要であるが、それ以外の点で８
ケの探索点を生成するのは冗長である。即ち、回りの点
の１ケはこの点に来る前の点であるし、それ以外にも、
即に他の点で探索点として生成し、チェックされてきた
ものがあるからである。

そこで、各点について探索が波及してきた方向を記憶し
ておき、できるだけ探索する点の減らすようにしている
。

探索方向はメツシュと同じ水平、垂直方向と対角線方向
の場合の２つを考え、第４図（Ｂ）の如く、１つの前の
ステップ（の候補点Ｐａ）から対角線方向に探索された
候補点ｐｂでは、まず探索方向の延長上にある点Ｐ２と
、それに隣接する２つの点Ｐ１、Ｐ３を探索点とする。

又、第４図（Ｃ）の如く、１つの前のステップの候補点
Ｐａから水平（又は垂直）方向に探索された候補点ｐｂ
では、同様、に探索方向の点Ｐ３とそれに隣接する２つ
の点Ｐ２、Ｐ４を探索点とする。つまり、探索途中では
、１つの点から次のステップに行くには３つの点を探索
点として調べればよい。

一方、候補点とされたものについては、出発点からの前
述のコストが計算される。こうして最終的に候補点中に
目標点が見付かった時点では、最適な経路が探索された
ことになる。なぜなら、このように順次外側に探索エリ
アを拡大して行く方法では、既に求まった候補点のコス
トより小さなコストが後から与えられる可能性は存在し
ないからである。即ち、目標点が見付かった場合のコス
トが最小コストである。

この段階では、第５図（Ｂ）に示す如く、第３図の地図
６格子点の中の候補点上に、出発点Ｐｓからのコストが
書き込まれているだけである。

従って、移動すべき経路は一義的に決定されていない。

そこで、経路を決定するため、これまでとは逆に目標点
Ｐｆから出発点Ｐｓに向かい、求められた候補点から隣
接する候補点の中でコストの最小のものを選んでいく。

このようにして第５図（Ｂ）の候補点とそのコストから
決定される経路は第１図（Ａ）のものとなり、バラ印が
通過点である。

（ｂ）経路探索処理の説明 次に、第２図の構成における経路探索処理について説明
する。

第６図は経路生成処理フロー図、第７図は第６図におけ
る通行不能判定処理フロー図、第８図は第６図における
探索点生成処理フロー図、第９図は経路データ説明図で
ある。

■　ＣＰＵ２は、第４図（Ａ）に示す出発点Ｐｓの回り
の８つの探索点Ｐｓｉ（ｉ＝１〜８）の座標を生成する
。

即ち、Ｘ方向の変位をδ（δ＝−ｉ、０．１）、Ｙ方向
の変位をε　（ε＝−１，０、ｌ）とし、Ｐｓｉの座標
を次式で求める。

Ｐｓｉ＝（Ｘ、＋δ、Ｙ０＋ε） 但し、Ｘｏ　、Ｙｏは出発点ＰｓのＸＳＹ座標であり、 δ−ξ＝０は除く。

■　次に、各探索点Ｐｓｉを地図メモリ１ａの障害物デ
ータと比較し、探索点ｐ　ｓ　ｉが通行（移動）不能領
域内かを調べる。

この通行不能判定処理は第７図に示す如く、探索点Ｐｓ
ｉのＸ座標Ｘｐが障害物データのＸ座標に含まれるかを
調べ、含まれなければ、移動可能な探索点とする。

一方、探索点ＰｓｉのＸ座標Ｘｐが障害物データのＸ座
標に含まれれば、今度はＹ座標を調べる。

即ち、障害物データの当該含まれるＸ座標におけるＹ座
標の範囲（ＹＬ、ＹＨ）をとり出し、探索点ＰｓｉのＹ
座標Ｙｐと比較する。

ＹＬ５Ｙｐ≦ＹＨであれば、探索点Ｐｓｉは障害物領域
（通行不能領域）内であるから、通行不能領域内として
削除する。逆にＹＬ５ＹｐＳＹＨでなければ、Ｙ座標で
障害物領域外であるから、この障害物データのＸ座標に
対し他にＹ座標があるを調べ、有れば前述のＹ座標のチ
ェックを行う。

一方、なければ、この探索点Ｐｓｉは移動可能と判断す
る。

このようにして全ての探索点について、移動可能（通行
不能領域内）かを調べ、全ての探索点が移動不能領域内
であれば、目標点に移動不能として、探索を終了する。

■　一方、移動可能な探索点があれば、これの出発点か
らのコスｌ−Ｃを第４図（Ａ）の原理で計算し、第１ス
テツプ（ｎ＝１）候補点として、第９図の如く、データ
メモリｌｂのｎ＝１の位置に各候補点のＸ、Ｙ座標、Ｘ
、Ｙ方向変位、コストを格納する。尚、データメモリ１
ｂのｎ＝０の位置には出発点ＰｓのＸ座標、Ｙ座標等が
格納される。

そして、ＣＰＵ２はステップｎ＝１とする。

■　次に、ＣＰＵ２は、前のｎステップの候補点から第
４図（Ｂ）、（Ｃ）の如（（ｎ＋１）ステップの探索点
を生成する。

このため、ＣＰＵ２はデータメモリ１ｂのｎステップの
候補点のデータからＸ、Ｙ方向の変位δ、ξをとりだし
、進行方向を判定し、探索点を第８図により生成する。

Ｘ方向の変位δ−０なら、垂直の進行方向のため、生成
する３つの探索点Ｐ１〜Ｐ３は、 Ｐ１＝　（Ｘｐ、Ｙｐ＋ε）、 Ｐ２＝　（Ｘｐ＋１．Ｙｐ＋ε）、 Ｐ３＝　（Ｘｐ−１、Ｙｐ＋ε） となる。

逆にＸ方向の変位δ≠０で、Ｙ方向の変位をε≠０なら
、第４図（Ｂ）の対角線又は逆対角線方向の進行のため
、生成する３つの探索点Ｐ１〜Ｐ３は、 Ｐ１＝（Ｘｐ＋δ、Ｙｐ＋ε）、 Ｐ２＝（Ｘｐ＋δ、Ｙｐ）、 Ｐ３＝　（Ｘｐ、Ｙｐ＋ε） となる。

更に、Ｘ方向の変位δ≠０で、Ｙ方向の変位ε＝０であ
るなら、第４図（Ｃ）の水平方向又は逆水平方向の進行
のため、生成する３つの探索点Ｐｌ〜Ｐ３は、 Ｐ１＝（Ｘｐ＋δ、Ｙｐ）、 Ｐ２＝（Ｘｐ＋δ、Ｙｐ＋１）、 Ｐ３＝（Ｘｐ＋δ、ｙｐ−１） となる。

このようにしてｎステップの候補点に対する（ｎ＋１）
ステップの探索点を生成する。

■　次に、ＣＰＵ２は（ｎ＋１）ステップの探索点に対
し、第７図及びステップ■で説明した方法で各探索点が
通行不能領域内かを判定する。

ステップ■と同様全ての探索点が通行不能領域内であれ
ば、目標点に移動不能として探索を終了する。

次に、ＣＰＵ２は、移動可能な探索点が既にチェックし
た候補点と一致するかを判定する。

移動可能な探索点が既チェックの候補点で一致すれば、
経路がループしてしまうことから、目標点に到達しない
。

従って、全ての移動可能な探索点が既チェックの候補点
と一致すれば、探索を終了する。

■　一方、移動可能な探索点の全部又は一部が既チェッ
クの候補点と一致しなければ、既チェックの候補点と一
致しない探索点について、第８図で用いたＸ、Ｙ方向の
変位δ、εから、第４図（Ａ）に従ってコストＣを計算
する。

そして、この探索点のＸ、Ｙ座標と、Ｘ、Ｙ方向の変位
δ、εコストを候補点としてデータメモリｌｂの（ｎ＋
１）ステップに相当する位置に書込む。

■　次に、ＣＰＵ２は、この（ｎ＋１）ステップの候補
点と目標点Ｐｆとを比較し、（ｎ＋１）ステップの候補
点中に目標点Ｐｆがなければ、ｎを一歩進し、ステップ
■に戻る。

逆に（ｎ＋１）ステップの候補点中に目標点Ｐｆがある
と、目標点Ｐｆに到達したので、探索を終了し、次の経
路選択処理に移行する。

このような候補点の探索結果は、第９図で示す如く、ｎ
＝０の出発点Ｐｓから順次ｎを「１」づつ歩進させて、
探索エリアを拡大して得た各ステップの候補点データが
データメモリ１ｂに格納された形となり、これを地図１
上で図示すると、第５図（Ｂ）の如く、候補点の位置と
コストとの関係となる。

この例では、ｎ＝８ステツプで、コスト１８で目標点Ｐ
ｆに到達したものを示しており、データメモリｌｂ上に
各ステップの候補点座標とコストが格納されている。

このように、候補点とコストが得られると、これらから
最短経路を第１０図の経路座標選択処理フロー図によっ
て選択する。

■　先づ、ＣＰＵ２は前述のステップ■で（Ｈ＋１）ス
テップの候補点中に目標点Ｐｆを見つけると、目標点Ｐ
ｆの座標（Ｘｅ、Ｙｅ）をＴｎとし、その候補点のコス
トＣｃをＣｎとセットする。

■　次に、現ステップｎ（ここでは、ｎ＋１）に「１」
を減じ、ｎが「０」かを調べる。

ｎが「０」でなければ、ステップ［相］へ進み、ｎがｒ
ＯＪならば、第９図の経路データを目標点から出発点Ｐ
ｓにたどり終わったことになり、ステップ０へ進む。

＠ｌ　ｎ≠０ならば、ｎステップの経路データの中から
座標Ｔｎの隣接点を選ぶ。第５図（Ｂ）の例では、目標
点Ｐｆの座標はＸｅ＝７、Ｙｅ＝７であるから、１つ前
のｎステップの経路データ中の隣接点はＸ＝６、Ｙ＝７
の候補点であり、同様に、点Ｘ＝６、Ｙ＝７の１つの前
のステップの隣接点はＸ＝５、Ｙ＝６の点である。

このように隣接点が１つならよいが、２つ以上存在する
時は、選択された点の中でそのコストＣｎが最小のもの
を選ぶ。

そして、これらの座標をＴｎ、コストをＣｎに置き代え
、ステップ■に戻る。

■　このようにして、ｎ−Ｇまで経路データをたどり、
コスト最小の隣接点を選択していき、これらより出発点
から目標点までの座標列を経路として作成する。

即ち、第１図（Ａ）に示す直線で結ばれた各点の座標が
経路である。

以上の様にして、メツシュ状の地図を用いて、障害物を
避けた最適で且つ最短の経路が求められる。

又、探索点の生成を第４図（Ｂ）、（Ｃ）に示す如く、
最小限度にすることができるから、地図上の格子点を探
索する方法を用いても、探索点の数が増えてしまうこと
もなく。短時間で探索ができる。

（Ｃ）他の実施例の説明 上述の実施例では、各ステップの候補点間に対応関係を
持たせることなく、経路の選択は第１θ図の如く目標点
からコストを利用してたどっていく方法を用いているが
、各ステップの候補点間に対応関係を持たせることによ
り、経路の選択処理を不要とするようにしてもよい。

以上本発明を実施例により説明したが、本発明は本発明
の主旨に従い種々の変形が可能であり、本発明からこれ
らを排除するものではない。

〔発明の効果〕

以上説明した様に、本発明によれば、メツシュ分割した
地図上の格子点座標で経路探索を行っているので、最適
且つ最短の移動経路を探索できるという効果を奏する。

又、地図上に障害物領域を記述するようにしているので
、オフィス等のレイアウトの変更の多い場合でも地図の
書替えが容易であるという効果を奏し、特に自立形自走
車の経路探索に有効である。

【図面の簡単な説明】

第１図は本発明の原理説明図、 第２図は本発明のための一実施例システム構成図、 第３図は本発明に用いる地図の説明図、第４図及び第５
図は経路探索動作説明図、第６図は経路生成処理フロー
図、 第７図は第６図における通行不能判定処理フロー図、 第８図は第６図における探索点生成処理フロー図、 第９図は経路データ説明図、 第１Ｏ図は経路座標選択処理フロー図、第１１図は従来
技術の説明図である。 図中、１−・−地図、 １ａ・・−地図メモリ、 ２−・プロセッサ、 ４−・データメモリ、 ６−・−自走車（移動体）。 窓 ＜＜＜＜＜＜＜ ＜ｘｘｘｘｘ＜ １×・・・ｘく ＜ｘｘｘｘｘ＜ ＜＜＜＜＜＜＜ 第７図 、探索＾生ｌ芝Ｒす！フロー図 第１０図

Claims (1)

1. 【特許請求の範囲】 移動環境を記述した地図（１）を用いて、与えられた出
   発点から目標点に到る移動体の移動経路を探索する移動
   経路探索方法において、 領域をメッシュで分割し、格子点座標で障害物を記述し
   た地図（１）を用い、 該地図（１）上の格子点座標で探索点を生成し、該地図
   （１）上の障害物を参照し、該生成した探索点から移動
   可能な候補点を求め、 該出発点から目標点までの移動コストが最小となる連続
   する候補点群を移動経路として選択することを 特徴とする移動経路探索方法。