JPS6232517A - 移動ロボツトの最適経路探索方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ この発明は、自立無人車等の移動ロボットに適用して好
適な移動ロボットの最適経路探索方法に関する。

［従来の技術］ 移動ロボットにおいて、ある地点から目的地まで、どう
いう経路を通れば最適であるかという問題について、種
々の研究がなされ、いろいろな方法が提案されている。

例えば、移動ロボットに内蔵されたメモリに、地図に対
応するデータを格納しておき、このデータによって最適
経路を決定する。すなわち、地図上の特殊点（ノード）
間の直線距離やノードの接続関係を予めメモリに格納し
ておき、現在位置しているノードＶｉから次に進むべき
ノード■ｊを次のようにして決定する。

（１）縦型探索、横型探索などの公知の手法によって、
出発ノードＳから目的ノードＧまでの経路を探索する。

そして、中間ノードＶｉに接続されたノードの中から次
に通過ずべきノードＶｊの候補ノードＶｊｘを選択する
。

（２）次候補ノードＶｊｘの中から、現在ノードＶｉに
最も近いノードＶｊを選ぶ。

（３）この操作を操り返して、出発ノートＳから１］的
ノードＧまでの経路を決定する。

この場合、上記経路は、総経路長が最小となり、最適経
路と考えられる。しかしながら、上述した従来の経路探
索方法では、本当の最適経路が得られないことがあった
。これは、次候補ノードＶｊｘの中から次のノードｖｊ
を選ぶ場合、現在ノード■ｉに最も近いノードを選択し
ているため、目的ノードＧから遠ざかるような進路を取
ってしまうケースが生じるからである。

また、縦型探索においては、いつになってし目的ノード
Ｇに到達しない場合がある一方、横型探索においては、
目的ノードＧを探索するのに長時間を要するといった問
題があった。これは、各ノード間の距離が等しい場合、
探索すべき枝が幾何級数的に増加してしまうからである
（第３図参照）。

そこで、本出願人は先に、中間ノードＶｉから次のノー
ドＶｊを選択するにあたり、次のような評価関数Ｈ（Ｖ
　ｉ、Ｖ　ｊｘ）を用いて、経路探索を行う方法を提案
した。

Ｈ（Ｖｉ、Ｖｊｘ） ＝Ｗａ−Ａ（Ｖｊｘ、Ｇ）＋Ｗｂ−Ｂ（Ｖ　ｉ、Ｖｊｘ
’）・−・（１）ただし、Ａ　（Ｖ　ｊｘ、Ｇ）＝１２
（Ｖ　ｊｘ、Ｇ　）／　Ｌ−＝＝−Ｃ２）Ｂ　（Ｖ　ｉ
、Ｖ　ｊｘ）＝１２（Ｖ　ｉ、Ｖ　ｊｘ）／　Ｌ−（３
）°ここで、Ｑ（Ｖ　ｊｘ、Ｇ　）は次候補ノードＶｊ
ｘと目的ノードＧとの距離、（２（Ｖ　ｉ、Ｖ　ｊｘ）
は現在ノードＶｉと次候補ノードＶｊｘとの距離であり
、しは最も離れたノード間の距離、すなわち、ノード間
の最大距離である。従って、上記変数Ａ（Ｖｊｘ、Ｇ）
お上びＢ　（Ｖ　ｉ、Ｖ　ｊｙ：）は距離しに上って正
規化されたもので、０〜ｌの値をとり、小さいほど評価
が良く、０が最良で、ｌが最悪である。また、Ｗａ、Ｗ
ｂは上記各変数Ａ（Ｖｊｘ、Ｇ）、およびＢ　（Ｖ　ｉ
、Ｖ　ｊｘ）の重みづけをする係数である。

［発明が解決しようとする問題点］ 王妃゛評価関数Ｈ（Ｖ　ｉ、Ｖ　ｊｘ）を用いることに
より、隣接するノード間の距離だけでなく、次候補ノー
ドＶｊｘが目的ノードＧにいかに近付いているかを考慮
に入れた経路決定が行なわれるため、探索枝を減少させ
、探索時間を短くすることができる。

また、評価関数Ｈ（Ｖｉ、Ｖｊｘ）の各項を正規化する
ことにより、各項の重みづけが容易となり、最適経路を
迅速に探索することができる。

しかしながら、ノード間の経路に円弧状の経路が含まれ
る場合（第５図参照）、上述した評価関数Ｈ（Ｖ　ｉ、
Ｖ　ｊｘ）ノ第２項であるＢ　（Ｖ　ｉ、Ｖ　ｊｘ）が
１を超える場合があり、正規化できないという不都合が
生じた。

この発明は、このような背景の下になされたもので、円
弧状の経路を含む場合も最適経路を迅速に探索できる移
動ロボットの最適経路探索方法を提供することを目的と
する。

［問題点を解決するための手段］ 上記問題点を解決するためにこの発明は、予め記憶され
たノード情報に基づいて次に進むべきノードを順次探索
し、探索された経路に沿って走行する移動ロボットにお
いて、経路探索時の評価関数を、次候補ノードから目的
ノードまでの距離を前記移動ロボットの移動領域に外接
する長方形の対角線の長さで正規化した項と、現在ノー
ドがら次候補ノードまでの距離を前記対角線の長さに円
周率を掛けた値で正規化した項とから構成したことを特
徴とする。

［作用］ 上記方法によれば、ノードの経路長だけでなく、いかに
目的ノードに近付きつつあるかを考慮に入れているため
、探索枝が非常に少なくなり、短時間で探索することが
できる。また、経路に円弧状の経路が含まれる場合でも
、評価関数の各項を正規化できるため、各項の重みづけ
が考えやすく、これを適宜に変化させることにより、最
適な経路探索が可能となる。更に、この方法を縦型探索
に適用すれば、探索失敗の確率が非常に小さ−くなる。

し実施例コ 以下、図面を参照して、本発明の詳細な説明する。

第１図は、この発明の一実施例の構成を示すブロック図
である。図において、２１は移動ロボットの走行装置で
あり、走行装置２１には、その走行制御を行うＣＰＵ２
２が接続されている。また、ＣＰｔＪ２２には、メモリ
２３が接続され、このメモリ２３には第２図に示すよう
な地図に関するデータが格納され°ている。すなわち、
地図を含む平面上の１点を原点としたときの各ノードｌ
〜１６の座標、ノート１〜１６の接続関係がメモリ２３
に格納されている。

ここで、出発ノードを８１目的ノードを０１連続する中
間ノードをＶ　ｉ、Ｖ　ｊとし、ノードＶｉからノード
■ｊを選択するための評価関数Ｈ（Ｖ　ｉ、Ｖ　ｊｘ）
次の式によって定義する。

Ｈ（Ｖ　　ｉ、Ｖ　　ｊｘ） ＝Ｗａ−Ａ（Ｖｊｘ、Ｇ）＋Ｗｂ−Ｂ（Ｖ　ｉ、Ｖｊｘ
）−−（４）ノこ　だ　し　、　　Ａ（Ｖｊｘ、Ｇ）＝
Ｃ（Ｖｊｘ、Ｇ）／　　Ｌ　−・　−・・　（５）Ｂ　
（Ｖ　ｉ、Ｖ　ｊｘ）＝（！（Ｖ　ｉ、Ｖ　ｊｘ）／　
ｒｒ　Ｌ−−（６）ここで、Ｑ（Ｖ　ｊｘ、　Ｇ　）は
次候補ノードＶｊｘと目的ノードＧとの距離、Ｑ（Ｖ　
ｉ、Ｖ　ｊｘ）は現在ノードＶｉと次候補ノードＶｊｘ
との距離であり、Ｌは地図（すなわち、移動ロボットの
移動領域）に外接する長方形の対角線の距離である。従
って、第２図の例ては、Ｌはノード１と１６との距離、
あるいはノード４と１３との距離となる。なお、距離り
をこのように定めたのは、例えば第５図のような場合を
考慮してである。すなわち、この場合、ノードＡ、Ｈ間
の直線距離は極めて短いにもかかわらず、これらの間の
円弧状経路３０は極めて長いものとなり、このような経
路３０を正規化するためには、円弧状経路３０やノード
Ｄ、Ｅに外接する長方形３１の対角線の長さしに円周率
πを乗じた値で正規化しなければならないからである。

こうして、値Ａ（Ｖｊｘ、Ｇ）は距離りによって正規化
され、値Ｂ　（Ｖ　ｉ、Ｖ　ｊｘ）は距離Ｉ、に円周率
πを乗じた値によって正規化されたものとなる。そして
、これらの値Ａ　（Ｖ　ｊｘ、Ｇ　）とＢ　（Ｖ　ｉ、
Ｖ　ｊｘ）とは０〜ｌの値をとり、小さいほど評価が良
く、０が最良で、ｌが最悪である。また、Ｗａ、Ｗｂは
変数Ａ（Ｖｊｘ、Ｇ）およびＢ　（Ｖ　ｉ、Ｖ　ｊｘ）
の重みづけをする係数である。　このような構成におい
て、出発ノードＳがＩＯ１目的目的ノードラード４であ
るとする。この場合、第２図、第３図に示すように、出
発ノード１０の次候補ノードＶｊｘとして、ノード６．
９．１１および１４が選ばれる。これらの次候補ノード
６．９．１１および１４に（４，）式を適用すると、評
価関数Ｈ（Ｖｉ、Ｖ・ｊｘ）を最小にする次候補ノード
Ｖｊｘとして、第４図に示すようにノード６．１１が選
択される。

次に、ノード６の次候補ノードＶｊｘとして、ノード２
，５．７が選択され、評価関数Ｈ（Ｖｉ、Ｖｊｘ）を最
小にするものとして、ノード７が選ばれる。

また、ノード１１の次候補ノードＶｊｘとしてノード７
．１２．１５があげられ、この中から、ノード７が評価
関数Ｈ（Ｖ　ｉ、　Ｖ　ｊｘ）を最小にするものとして
選択される。以下、同様にして、ノード７の次候補ノー
ドＶｊｘとしてノード３と８が選ばれるが、ノード７．
８間が直線であるのに対して、ノード７．３間は円弧で
あるから、評価関数Ｈ（Ｖｉ、Ｖｊｘ）を最小にするも
のとしてノード８が選ばれ、このノード８の次に目的ノ
ード４が選択される。

こうして、最適経路として、第４図に示すように、１０
→６−７→８→４あるいは１０→１１→７−８→４が選
択される。

こうして、本実施例によれば、探索すべき技が第３図に
比べて激減し、探索時間を短縮することができる。

なお、上記実施例では、評価関数の値が、最良のときに
０、最悪のときに１となるようにしたが、Ａ（Ｖｊｘ、
Ｇ）＝（Ｌ−ｆ２（Ｖｊｘ、Ｇ））／ＬＢ（Ｖ　ｉ、Ｖ
　ｊｘ）＝　（ｒｃ　Ｌ−Ｑ（Ｖ　ｉ、Ｖ　ｊｘ））／
　ｘ　Ｌとすれば、最良が１、最悪が０となることは明
らかである。また、第１図のＣＰＵ２２とメモリ２３と
は、走行装置２１と別体としてもよい。

［発明の効果］ 以上説明したように、この発明は、ノード間の経路長だ
けでなく、次候補ノードと目的ノードとの距離をも考慮
に入れて経路探索を行うようにしたので、探索枝が非常
に少なくなり、短時間で探索することができる。また、
経路に円弧状の経路が含まれる場合でも、評ｉ関数の各
項を正規化できるので、各項の重みづけ係数を適宜変化
させることにより、最適の経路探索が可能となる。更に
、縦型探索において、探索失敗の確率を非常に小さくで
きる。

【図面の簡単な説明】

第１図はこの発明の一実施例の構成を示すブロック図、
第２図は同実施例における地図の一例を示す概念図、第
３図は次候補ノードの探索枝の一例を示すトリー図、第
４図は本実施例における経路探索の一例を示すトリー図
、第５図は同実施例における円弧状経路３０と、長方形
３１の対角線の長さしとの関係を説明するための図であ
る。 １−１６・・・・・・ノード、２１・・・・・・走行装
置、２２・・・・・・ＣＰＵ、２３・・・・・メモリ、
３０・・・・・・円弧状経路、３Ｉ・・・・・・移動領
域に外接する長方形。 第１図 第２図

Claims (1)

【特許請求の範囲】
1. 予め記憶されたノード情報に基づいて次に進むべきノー
   ドを順次探索し、探索された経路に沿って走行する移動
   ロボットにおいて、経路探索時の評価関数を、次候補ノ
   ードから目的ノードまでの距離を前記移動ロボットの移
   動領域に外接する長方形の対角線の長さで正規化した項
   と、現在ノードから次候補ノードまでの距離を前記対角
   線の長さに円周率を掛けた値で正規化した項とから構成
   したことを特徴とする移動ロボットの最適経路探索方法
   。