JPH067366B2 - 移動ロボツトシステムにおける最適経路探索方法 - Google Patents

Description

【発明の詳細な説明】 ［産業上の利用分野］ この発明は、作業要求の発生した作業点に、自立無人車
等の移動ロボットを迅速に行かせることのできる、移動
ロボットシステムにおける最適経路探索方法に関する。

［従来の技術］ 現在、移動ロボットの開発が盛んに行なわれており、移
動ロボット自体の性能はいうにおよばず、移動ロボット
システム全体としての性能向上が重要な課題となってい
る。

この種の移動ロボットシステムとしては、複数の移動ロ
ボットと、これらの移動ロボットを統括制御する１つの
中央局とからなるものが代表的である。そして、各移動
ロボットは中央局の指示に従い、作業点まで走行して所
定の作業を行う。中央局は移動ロボットの移動領域の地
図情報を管理するとともに、すべての移動ロボットの現
在位置や作業中か否かなどの状態を監視し、無線または
有線などの通信手段により移動ロボットと交信しながら
作業指示を行う。

すなわち、いずれかの作業点で作業要求が発生すると、
中央局は作業を行っていない移動ロボットの中から、作
業点に行くのに最適な移動ロボットを選択して指令を与
える。ここで、移動ロボットの選択方法としては、作業
点への直線距離が最も短い移動ロボットを選ぶ単純なも
のや、各移動ロボットが上記作業点に行くための最適経
路を中央局が計算し、その中で今回の作業に最も適した
移動ロボットを選択する方法がある。

［発明が解決しようとする問題点］ ところで、上述した従来の選択方法のうち、作業点に最
も近い移動ロボットを選ぶ方法では、直線距離が最短で
も経路が大回りしていることもあり、最適の移動ロボッ
トが選択されないケースも生じる。例えば第３図に示す
ように、移動ロボット１の現在位置と作業点２とが極め
て接近しているにもかかわらず、経路３が大回りしてい
るため、最適の移動ロボットは移動ロボット４になるよ
うな場合である。

一方、現在作業をしていない全部の移動ロボットについ
て、作業点まで行く最適経路を中央局が探索し、その中
から最適の移動ロボットを選択する方法では、中央局が
統括する移動ロボットの数に比例して探索時間が長引い
てしまい、迅速な処理ができなくなるという問題があっ
た。

この発明は、このような背景の下になされたもので、作
業点に移動すべき移動ロボットを迅速に決めることので
きる、移動ロボットシステムにおける最適経路探索方法
を提供することを目的とする。

［問題点を解決するための手段］ 上記問題点を解決するためにこの発明は、中央局と、前
記中央局によって指定された作業点に移動して所定の作
業を行う複数の移動ロボットとからなるロボットシステ
ムにおいて、 前記中央局が各移動ロボットへ経路探索およびその評価
をするよう指令する第１のステップと、 前記各移動ロボットのうち待機状態にある移動ロボット
が、前記指令に応じて並行してそれぞれの現在位置から
前記作業点に至る最適経路を探索する第２のステップ
と、 前記待機状態にある移動ロボットが、前記探索した最適
経路の長さに対応した評価値を算出し、 これを前記中央局へ送る第３のステップと、 前記中央局が、前記待機状態にある移動ロボットから送
られた評価値を比較し、最良の評価値を送ってきた移動
ロボットを選択する第４のステップと、 前記中央局が、前記選択された移動ロボットに前記作業
点へ移動するよう指令する第５のステップとを有するこ
とを特徴とする。

［作用］ 上記構成によれば、最適経路探索のための処理が待機状
態にある複数の移動ロボットに分散され、並列処理の形
で行われるので、処理効率が向上し、極めて短時間で探
索が終了する。また、探索処理中は、中央局の処理負荷
が従来に比べて著しく減少するため、中央局は他の処理
を行うことができる。

各移動ロボットが中央局へ返すのは探索経路ではなく評
価値であるため、中央局は最適位置にいる移動ロボット
を迅速に判断することができる。また、中央局がこの判
断をしている間に、各移動ロボットは自分が選択された
ときのために、探索した経路に基づいて移動の準備をし
ておくことができる。

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

第１図はこの発明の一実施例の構成を示すブロック図で
ある。図において１１は中央局、１２−k(k＝1,2……n)
はｎ個の移動ロボットであり、中央局１１と各移動ロボ
ット１２-kとは無線または有線の通信改選１３-kによっ
て結ばれている。

中央局１１は、ＣＰＵとメモリとを有し、各移動ロボッ
ト１２-kの現在位置や作業中か否かなどの状態を把握し
ている。また、各作業点と結ばれ、作業点からの作業要
求を受け入れ、この情報を各移動ロボット１２-kに伝送
する。

一方、移動ロボット１２-kは第２図に示す構成となって
いる。図において、２１は移動ロボット１２-kの走行装
置であり、走行装置２１には、その走行制御を行うＣＰ
Ｕ２２が接続されている。また、ＣＰＵ２２には、メモ
リ２３が接続され、このメモリ２３には各作業点の座標
と、作業点の接続関係を示す地図データが格納されてい
る。

ＣＰＵ２２は現在の作業点から目的の作業点に至る経路
を探索する。この探索に当たっては、以下のような演算
によってノードを選択し、評価値Ｈｓを算出する。

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

Ｈ（Ｖｉ，Ｖjx） ＝Ｗａ・Ａ（Ｖjx，Ｇ） ＋Ｗｂ・Ｂ（Ｖｉ，Ｖjx）……（１） ただし、 Ａ（Ｖjx，Ｇ）＝１（Ｖjx，Ｇ）／Ｌ……（２） Ｂ（Ｖｉ，Ｖjx）＝１（Ｖｉ，Ｖjx）／Ｌ……（３） ここで１（Ｖjx，Ｇ）は次候補ノードＶjxと目的ノード
Ｇとの距離、１（Ｖｉ，Ｖjx）は現在ノードＶｉと次候
補ノードＶjxとの距離であり、Ｌはノード間の最大距
離、すなわち例えば図４に示すような地図モデルの場
合、ノード１とノード１６との距離あるいはノード４と
ノード１３との距離である。従って、値Ａ（Ｖjx，
Ｇ）、Ｂ（Ｖｉ，Ｖjx）は距離Ｌによって正規化された
もので、０〜１の値をとり、小さい値ほど評価が良く、
０が最良で、１が最悪である。また、Ｗａ、Ｗｂは上記
各変数Ａ（Ｖjx，Ｇ）およびＢ（Ｖｉ，Ｖjx）の重み付
けをする係数である。

このとき、図４に示す地図モデルにおいて、各ノード１
〜１６の隣どうしのノード間距離は等距離であり、上記
の値Ｂ（Ｖｉ，Ｖjx）は、全て等しいとする。また、出
発ノードＳがノード１０、目的ノードＧがノード４であ
るとする。

この場合、出発ノード１０の次候補ノードＶjxは、ノー
ド６，９，１１，１４となる。これらの次候補ノード
６，９，１１，１４に（１）式を適用すると、Ａ（Ｖj
x，Ｇ）を最小にする次候補ノードＶjxとして、ノード
６，１１が選択される。

次に、ノード６の次候補ノードＶjxとしては、ノード
２，５，７のうち、Ａ（Ｖjx，Ｇ）を最小にするものと
して、ノード７が選択される。また、ノード１１の次候
補ノードＶjxとしては、ノード７，１２，１５のうち、
Ａ（Ｖjx，Ｇ）を最小にするものとして、ノード７が選
択される。以下同様にして、ノード７の次はノード３と
８が選ばれ、これらの次に目的ノード４が選択される。

こうして、最適経路として、１０→６→７→３→４、１
０→６→７→８→４、１０→１１→７→３→４あるいは
１０→１１→７→８→４が探索される。

そして、このようにして得られた最適経路について、次
式（４）によって出発ノード１０から目的ノード４まで
評価関数Ｈ（Ｖｉ，Ｖjx）の値の総和、すなわち評価値
Ｈｓを算出する。

Ｈｓ＝ΣＨ（Ｖｉ，Ｖjx）……（４） この評価値Ｈｓは、値が小さいほど探索された最適経路
としての評価が良いことになる。なお、この例で探索さ
れた上記４つの最適経路の評価値Ｈｓは全て等しくな
る。

こうして、それぞれ異なる出発ノードＳに位置する移動
ロボットにおいて、最適経路の評価値Ｈｓが算出され
る。

このような構成において、ある作業点に作業要求が発生
すると、これが中央局１１に伝達され、中央局１１は待
機中の全移動ロボット１２-kに最適経路の探索を指示す
る。探索を指示された移動ロボット１２-kのＣＰＵ２２
は、上記（１）〜（４）式によって、出発作業点（すな
わち自分の現在位置）Ｓから目的作業点Ｇまでの経路を
探索し、評価値Ｈｓを算出する。そして、最良の評価値
Ｈｓを与える経路を記録するとともに、この最良の評価
値Ｈｓを中央局１１へ伝達する。

中央局１１は各移動ロボット１２-kから送られてきた評
価値Ｈｓを比較して、この中から最良の評価値Ｈｓを選
択し、最良の評価値Ｈｓを送ってきた移動ロボット１２
-kに移動命令を送る。移動命令をうけた移動ロボット１
２-kは探索ずみの経路に従って、目的作業点Ｇまで移動
する。

なお、上記実施例においては、各移動ロボットに地図デ
ータを内蔵させたが、必要に応じて中央局からもらうよ
うに構成してもよい。

［発明の効果］ 以上説明したように、この発明によれば、最適経路探索
が各移動ロボットにおいて並列処理の形で行なわれるの
で、極めて短時間で探索を終了することができる。ま
た、探索処理中は、中央局の処理負荷が従来に比べて著
しく減少するため、中央局は他の処理を行うことができ
る。

各移動ロボットが中央局へ返すのは探索経路ではなく評
価値であるため、中央局き最適位置にいる移動ロボット
を迅速に判断することができる。また、中央局がこの判
断をしている間に、各移動ロボットは自分が選択された
ときのために、探索した経路に基づいて移動の準備をし
ておくことができる。

こうして、資源としての移動ロボットを有効に活用する
とともに、中央局の負荷を低減でき、システム全体とし
ての応答性を向上できる。また、移動ロボットが探索結
果を返してくるか否かによって、中央局は各移動ロボッ
トの異常を検知できる。

【図面の簡単な説明】

第１図はこの発明の一実施例による移動ロボットシステ
ムの構成を示すブロック図、第２図は移動ロボット１２
-kの構成を示すブロック図、第３図は作業点と移動ロボ
ットの位置関係を説明するための平面図、第４図は地図
モデルの一例を示す概念図である。 １１……中央局、１２-k……移動ロボット。

Claims (1)

【特許請求の範囲】
1. 【請求項１】中央局と、前記中央局によって指定された
   作業点に移動して所定の作業を行う複数の移動ロボット
   とからなるロボットシステムにおいて、 前記中央局が、各移動ロボットへ経路探索およびその評
   価をするよう指令する第１のステップと、 前記各移動ロボットのうち待機状態にある移動ロボット
   が、前記指令に応じて並行してそれぞれの現在位置から
   前記作業点に至る最適経路を探索する第２のステップ
   と、 前記待機状態にある移動ロボットが、前記探索した最適
   経路の長さに対応した評価値を算出し、これを前記中央
   局へ送る第３のステップと、 前記中央局が、前記待機状態にある移動ロボットから送
   られた評価値を比較し、最良の評価値を送ってきた移動
   ロボットを選択する第４のステップと、 前記中央局が、前記選択された移動ロボットに前記作業
   点へ移動するよう指令する第５のステップと を有することを特徴とする移動ロボットシステムにおけ
   る最適経路探索方法。