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

Abstract

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

Description

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

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

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

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

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

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

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

この場合、上記経路は、総経路長が最小となり、最適経
路と考えられる。

［発明が解決しようとする問題点コ ところで、上述した従来の経路探索方法では、本当の最
適経路が得られないことがあった。これは、次候補ノー
ドＶｊｘの中から次のノードＶｊを選ぶ場合、現在ノー
ドＶｉに最も近いノードを選択しているため、目的ノー
ドＧから遠ざかるような進路を取ってしまうケースが生
じるからである。

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

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

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

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

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

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

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

Ｈ（Ｖｉ、Ｖｊｘ） ＝Ｗａ−Ａ（Ｖｊｘ、Ｇ）＋Ｗｂ−Ｂ（Ｖｉ、Ｖｊｘ）
−・”（１）ただし、Ａ（Ｖ　ｊｘ、Ｇ）＝１２（Ｖ　
ｊｘ、Ｇ）／　Ｌ−−（２）Ｂ　（Ｖ　ｉ、Ｖ　ｊｘ）
＝Ｉ２（Ｖ　ｉ、Ｖ　ｊｘ）／　Ｌ−−（３）ここで、
Ｑ（ｖ　ｊ）＋、ｃ　）は次候補ノードＶｊｘと目的と
次候補ノードＶｊｘとの距離であり、Ｌはノード間の最
大距離、すなわち、ノードｌと１６との距離、あるいは
ノード４と１３との距離である。従って、値Ａ（Ｖｊｘ
、Ｇ）、Ｂ　（Ｖ　ｉ、Ｖ　ｊｘ）ハ距離りによって正
規化されｊこもので、０〜１の値をとり、小さいほど評
価が良く、０が最良で、ｌが最悪である。

また、Ｗａ％Ｗｂは上記各変数Ａ（Ｖｊｘ、Ｇ）、およ
びＢ　（Ｖ　ｉ、Ｖ　ｊｘ）の重みづけをする係数であ
る。

このような構成において、各ノード１−１６の隣どうし
のノード間距離は等距離であり、上記の値Ｂ　（Ｖ　ｉ
、Ｖ　ｊｘ）はすべて等しいとする。また、出発ノード
Ｓが１０．目的ノードＧがノード４であるとする。

この場合、第２図、第３図に示すように、出発ノードｌ
Ｏの次候補ノードＶｊｘは、ノード６．９゜ｉｔ、１４
となる。これらの次候補ノード６．９゜１１．１４に（
１）式を適用すると、値Ａ（Ｖｊｘ、Ｇ）を最小にする
次候補ノードＶｊｘとして、第４図に示すようにノード
６．１１が選択される。

ｋｐ＋−ＪＬごｃ、ｆｒＹｋ・−・Ａａｋｌ＋ノーＬ’
ＩＦニー１−１−ｒ−＋ノード２．５．７が選択され、
値Ａ（Ｖｊｘ、Ｇ）を最小にするものとして、ノート７
が選ばれる。また、ノード１１の次候ｈｌｔノードＶｊ
ｘとしては、ノード７．１２．１５があげられ、値Ａ　
（Ｖ　ｊｘ、Ｇ　）を最小にするものとして、ノード７
が選択される。以下、同様にして、ノード７の次はノー
ド３と８が選ばれ、これらの次に目的ノード４が選択さ
れる。

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

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

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

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

【図面の簡単な説明】

第１図はこの発明の一実施例の構成を示すプロ・ツク図
、第２図は同実施例における地図の一例を示す概念図、
第３図は次侯ｈｌｉノードの探索枝の一例を示すトリー
図、第４図は本実施例における経路探索の一例を示すト
リー図である。 １−１６・・・・・ノード、２１・・・・・走行装置、
２２・・・・・ＣＰＵ、２３　・・・・メモリ。

Claims (1)

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