JPH0786769B2 - 自立無人車システムにおける最適経路探索方法 - Google Patents

Description

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

「従来の技術」 現在、自立無人車の開発が盛んに行なわれており、自立
無人車自体の性能はいうにおよばず、自立無人車システ
ム全体としての性能向上が重要な課題となっている。

この種の自立無人車システムとしては、複数の自立無人
車と、これらの自立無人車を統括制御する１つの中央局
とからなるものが代表的である。

このようなシステムにおいて各自立無人車は、中央局の
指示に従って作業点まで走行して所定の作業を行う。一
方、中央局は自立無人車の移動領域の地図情報を管理す
るとともに、すべての自立無人車の現在位置や作業中か
否かなどの状態を監視し、無線または有線などの通信手
段により自立無人車と交信しながら作業指示を行う。

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

「発明が解決しようとする問題点」 ところで、上述した従来の選択方法では、中央局が各自
立無人車のそれぞれについて移動経路を求める処理を行
う必要があるから、中央局において処理すべきデータが
膨大なものとなって、中央局の処理能力に大きなものが
要求され、あるいは、中央局がデータを処理して最適な
ロボットを選択するのに要する時間が長くなるという問
題がある。

また、自立無人車をＡ地点〜Ｂ地点〜Ｃ地点…………と
順次移動させながら作業を行なおうとする場合のよう
に、移動経路が長くなると、各自立無人車の経路の計算
にさらに多くの時間が必要になる。

本発明は上記事情に鑑みて提案されたもので、複数の自
立無人車の中から最適なものを最短時間で選択させるこ
とを目的とするものである。

「問題点を解決するための手段」 上記問題点を解決するためにこの発明は、中央局と、該
中央局によって指定された第１番目から第Ｎ番目の各作
業点に移動して所定の作業を行う複数の自立無人車とか
らなる自立無人車システムにおいて、前記各自立無人車
は、前記中央局から指令があったときに、現在位置から
第１番目の作業点への経路探索をそれぞれ行なうととも
にその評価値を前記中央局に送り、前記中央局は、前記
各自立無人車が第１番目の作業点への経路探索および評
価を行っている間に、第１番目の作業点から最終の作業
点までの経路探索を行い、前記中央局は、最も良い評価
値を送ってきた自立無人車に第１番目の作業点への移動
を指令し、また、該自立無人車に、前記中央局において
探索しておいた第１番目の作業点から最終の作業点まで
の経路に沿って移動すべき移動命令を送ることを特徴と
する。

「作用」 上記構成によれば、各自立無人車毎に異なっている第１
番目の作業点までの経路探索が並列処理の形で行なわれ
るので、短時間で探索が終了する。また、複数の作業点
を経由する全経路について経路探索を行う必要がないか
ら、探査処理を極めて短時間に行うことができる。さら
に、探索処理中は、中央局の処理負荷が従来に比べて著
しく減少するため、中央局は、第１番目の作業点以降の
経路探査を行うことができる。

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

第１図はこの発明の一実施例の構成を示すブロック図で
ある。

図において１は中央局、２−ｋ（ｋ＝1,2……ｎ）はｎ
個の自立無人車であり、中央局１と各自立無人車２−ｋ
とは無線または有線の通信回線３−ｋによって結ばれて
いる。

中央局１は、CPUとメモリ（ともに図示略）とを有し、
各自立無人車２−ｋの現在位置や作業中か否かなどの状
態を把握している。また、第３図に示すような各作業点
４−Ｋ（＝1,2,……Ｎ）と結ばれ、作業点からの作業要
求を受け入れ、この情報を各自立無人車２−ｋに伝送す
る。

一方、自立無人車２−ｋは第２図に示す構成となってい
る。図において、５は自立無人車２−ｋの走行装置であ
り、走行装置５には、その走行制御を行うCPU6が接続さ
れている。また、CPU6には、メモリ７が接続され、この
メモリ７には各作業点の座標と、作業点の接続関係を示
す地図データが格納されている。

CPU6は現在の作業点から目的の作業点に至る経路を探索
し、次のような演算によって評価値Hsを算出する。

Hs＝ΣＨ（Vi,Vj）……（１） Ｈ（Vi,Vj） ＝Wa・Ａ（Vj,G）＋Wb・Ｂ（Vi,Vj）……（２） ただし、Ａ（Vj,G）＝ｌ（Vj,G）/L……（３） Ｂ（Vi,Vj）＝ｌ（Vi,Vj）/L……（４） ここで、Vi,Vjは地図上の連続する通過点（ノード）で
あり、上記（１）式の和Σは、出発作業点Ｓから目手作
業点Ｇに至るすべてのノードについてとられる。また、
ｌ（Vj,G）はノードVjと目的ノード（目的作業点）Ｇと
の距離、ｌ（Vi,Vj）は連続するノードViとノードVjと
の距離であり、Ｌはノード間の最大距離である。従っ
て、上記（３）、（４）式の値Ａ（Vj,G）、Ｂ（Vi,V
j）は距離Ｌによって正規化されたもので、０〜１の値
をとり、目的作業点Ｇに近付くほど、また連続するノー
ドVi,Vj間の距離が短いほど、小さな値となる。

従って、（１）式の評価値Hsは小さいほど評価が良くな
るようになっている。なお、Wa、Wbは上記各変数Ａ（V
j,G）およびＢ（Vi,Vj）の重みづけをする係数であり、
適宜の値に設定される。

このような構成において、ある作業点4Aから4Bを経由し
て4Nに経路に沿って順次作業を行うべく要求が発生する
と、これが中央局１に伝達され、中央局１は待機中の全
自立無人車２−ｋ、またはシステム中の全自立無人車２
−ｋに最適経路の探索を指示する。

探索を指示された自立無人車２−ｋのCPU6は、公知の縦
型探索法あるいは横型探索法によって出発作業点（すな
わち自分の現在位置）Ｓから目印作業点Ｇ（すなわち第
１番目に作業を行うべき地点４−Ａ）までの経路を探索
し、上記（１）〜（４）式によって評価値Hsを算出す
る。そして、最良の評価値Hsを与える経路を記憶すると
ともに、この最良の評価値Hsを中央局１へ伝達する。

このような各自立無人車2kの経路探索と並行して、中央
局は、作業点4A以降の経路、すなわち4Aから4B、さらに
は、それ以降の最終作業点4Nに至るまでの経路を探索す
る。

そして、中央局１は各自立無人車２−ｋから送られてき
た評価値Hsを比較して、この中から最良の評価値Hsを選
択し、最良の評価値Hsを送ってきた自立無人車２−ｋ
（図示例では２−３が該当する）に移動命令を送るとと
もに、この自立無人車２−ｋに、中央局１において探査
しておいた作業点4A以降の4Nに至る経路に沿って移動す
べく移動命令を送る。なお、4A以降の経路についての作
業命令は、選択された自立無人車２−ｋが１番目の作業
点4Aにおける作業を終了するまでの期間に出されればよ
い。

なお、上記実施例においては、各自立無人車に地図デー
タを内蔵させたが、必要に応じて中央局からもらうよう
に構成してもよい。

「発明の効果」 以上説明したように、この発明によれば、自立無人車を
移動させるべき経路の内、各無人車毎に異なっている第
１番目の作業点までの最適経路探索が各自立無人車にお
いて並列処理の形で行なわれるので、極めて短時間で探
索を終了することができる。

また、各自立無人車の探索処理中に、中央局が第１番目
の作業点から最終の作業点までの経路探索を行うので、
経路探索の重複をなくすとともに、並列処理によって中
央局及び各自立無人車の処理能力を十分に利用し、資源
としての中央局及び自立無人車を有効に活用するととも
に、システム全体としての応答性を向上できる。

【図面の簡単な説明】

第１図はこの発明の一実施例による自立無人車システム
の構成を示すブロック図、第２図は自立無人車２−ｋの
構成を示すブロック図、第３図は作業点と自立無人車の
位置関係を説明するための平面図である。 １……中央局、２−ｋ……自立無人車、4K……作業点。

Claims (1)

【特許請求の範囲】
1. 【請求項１】中央局と、該中央局によって指定された第
   １番目から第Ｎ番目の各作業点に移動して所定の作業を
   行う複数の自立無人車とからなる自立無人車システムに
   おいて、 前記各自立無人車は、前記中央局から指令があったとき
   に、現在位置から第１番目の作業点への経路探索をそれ
   ぞれ行なうとともにその評価値を前記中央局に送り、 前記中央局は、前記各自立無人車が第１番目の作業点へ
   の経路探索および評価を行っている間に、第１番目の作
   業点から最終の作業点までの経路探索を行い、 前記中央局は、最も良い評価値を送ってきた自立無人車
   に第１番目の作業点への移動を指令し、また、該自立無
   人車に、前記中央局において探索しておいた第１番目の
   作業点から最終の作業点までの経路に沿って移動すべき
   移動命令を送る ことを特徴とする自立無人車システムにおける最適経路
   探索方法。