(57)【要約】【課題】  複数の作業箇所が存在する作業において、移動ロボットの最適な停止箇所を、コストを評価基準として計算により求めることを可能にする。【解決手段】  本発明のロボットの停止箇所決定方法は、複数の作業についてロボットアームの可動作業空間内の領域を作業判定領域とすると共に、各作業判定領域内に格子点を配置するステップと、各格子点において移動ロボットによる作業が遂行可能であるか否かを判断して複数の作業に対応する作業可能領域を設定するステップと、複数の作業可能領域の重なりが最適となるように組み合わせるステップと、組み合わせた作業可能領域の重なった領域においてコストが最小となる作業箇所を求めて、最少停止箇所を決定するステップとを備えたものである。この停止箇所決定方法によれば、移動ロボットの停止箇所を最適化できる。【選択図】  図１
2005088164.tif 000002
【特許請求の範囲】
【請求項１】
複数の作業について、ロボットのロボットアームの可動作業空間内の領域を作業判定領域とすると共に、各作業判定領域内に設定間隔の格子点を配置するステップと、
前記各格子点において前記移動ロボットによる作業が遂行可能であるか否かを判断して前記複数の作業に対応する作業可能領域を設定するステップと、
前記複数の作業可能領域の重なりが最適となるように組み合わせるステップと、
前記組み合わせた作業可能領域の重なった領域において、コストが最小となる作業箇所を求めることにより、最少停止箇所を決定するステップとを備えたことを特徴とするロボットの停止箇所決定方法。
【請求項２】
前記各停止箇所において、前記ロボットのロボットアームの作業順序を最適化するステップを備えたことを特徴とする請求項１記載のロボットの停止箇所決定方法。
【請求項３】
前記各停止箇所の間の走行経路を、コストが最小となるように決定するステップを備えたことを特徴とする請求項１または２記載のロボットの停止箇所決定方法。
【請求項４】
複数の作業について、ロボットのロボットアームの可動作業空間内の領域を作業判定領域とすると共に、各作業判定領域内に設定間隔の格子点を配置する手段と、
前記各格子点において前記ロボットによる作業が遂行可能であるか否かを判断して前記複数の作業に対応する作業可能領域を設定する手段と、
前記複数の作業可能領域の重なりが最適となるように組み合わせる手段と、
前記組み合わせた作業可能領域の重なった領域において、コストが最小となる作業箇所を求めることにより、最小停止箇所を決定する手段とを備えたことを特徴とするロボットの停止箇所決定装置。
【請求項５】
前記各停止箇所において、前記ロボットのロボットアームの作業順序を最適化する手段を備えたことを特徴とする請求項４記載のロボットの停止箇所決定装置。
【請求項６】
前記各停止箇所の間の走行経路を、コストが最小となるように決定する手段を備えたことを特徴とする請求項４または５記載のロボットの停止箇所決定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の作業箇所が存在する作業を例えば移動ロボットによって実行させる場合において、移動ロボットのコストが最小となるような作業計画を作成する際に役立てることができるロボットの停止箇所決定方法及びロボットの停止箇所決定装置に関する。
【背景技術】
【０００２】
複数の作業箇所が存在する作業において、移動ロボットを停止させる位置（即ち、停止箇所）は、従来は、作業計画作成者（即ち、作業者）がそれまでの経験に従って適当に決めていた。また、停止箇所で移動ロボットを作業させる場合も、移動ロボットに対してロボットアームの教示を経験的に行うようにしていた。
これに対して、近年、移動ロボットの走行経路（停止箇所を含む）を計算によって求める研究がなされており、その一例として、非特許文献１が知られている。この研究では、移動ロボットのアームの可操作性の評価基準に注目して走行経路を計算し、経路計画（作業計画）を実現するようにしている。尚、本願発明と直接関係するものではないが、関連する分野の技術として、特許文献１、２が知られている。
【非特許文献１】永谷圭司、平山智信、五福明夫、田中豊著、「操作性を保つ移動マニピュレータの作業場所計画（第7回ロボティクスシンポジア予稿集  pp.329-334（2002-03））」
【特許文献１】特開平５−１０４４６５号公報
【特許文献２】特開平６−３３７７０９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、作業者が移動ロボットの停止位置を経験的に決める構成の場合には、最適化が行われていないので、コストを最小にすることができないという問題点があった。また、上記非特許文献１の研究においては、各種のコスト評価に関する考慮が全くなされていないし、また、移動ロボットを移動させながら実行する作業については考察しているが、移動ロボットを所定の箇所に停止させて実行する作業（即ち、高い精度が要求される作業）についての考慮は全くなされていない。
【０００４】
そこで、本発明の目的は、複数の作業箇所が存在する作業において、移動ロボットの最適な停止箇所を、コストを評価基準として計算により求めることができるロボットの停止箇所決定方法及びロボットの停止箇所決定装置を提供するにある。
【課題を解決するための手段】
【０００５】
本発明のロボットの停止箇所決定方法は、複数の作業について、ロボットのロボットアームの可動作業空間内の領域を作業判定領域とすると共に、各作業判定領域内に設定間隔の格子点を配置するステップと、前記各格子点において前記ロボットによる作業が遂行可能であるか否かを判断して前記複数の作業に対応する作業可能領域を設定するステップと、前記複数の作業可能領域の重なりが最適となるように組み合わせるステップと、前記組み合わせた作業可能領域の重なった領域において、コストが最小となる作業箇所を求めることにより、最少停止箇所を決定するステップとを備えたものである。この停止箇所決定方法によれば、複数の作業箇所が存在する作業において、ロボットの停止箇所が最適化される。
【０００６】
また、上記方法の場合、前記各停止箇所において、前記ロボットのロボットアームの作業順序を最適化するステップを備えることが好ましい。更に、前記各停止箇所の間の走行経路を、コストが最小となるように決定するステップを備えることもより一層好ましい。
一方、本発明のロボットの停止箇所決定装置は、複数の作業について、ロボットのロボットアームの可動作業空間内の領域を作業判定領域とすると共に、各作業判定領域内に設定間隔の格子点を配置する手段と、前記各格子点において前記ロボットによる作業が遂行可能であるか否かを判断して前記複数の作業に対応する作業可能領域を設定する手段と、前記複数の作業可能領域の重なりが最適となるように組み合わせる手段と、前記組み合わせた作業可能領域の重なった領域において、コストが最小となる作業箇所を求めることにより、最少停止箇所を決定する手段とを備えなるところに特徴を有するものである。
【０００７】
この構成の場合、前記各停止箇所において、前記ロボットのロボットアームの作業順序を最適化する手段を備えることが好ましい。また、前記各停止箇所の間の走行経路を、コストが最小となるように決定する手段を備えることがより一層好ましい構成である。
【発明を実施するための最良の形態】
【０００８】
以下、本発明を「複数作業を遂行する移動ロボット（移動マニピュレータ）の最適動作を計画する方法」に適用した一実施例について、図面を参照しながら説明する。まず、図２は、本実施例で用いる移動ロボット１の電気的構成を示すブロック図である。
この図２に示すように、移動ロボット１は、ロボットコントローラ２と、ロボットアーム３と、走行台車４と、電源システム５とを備えて構成されており、周知構成の移動ロボットである（例えば特願２０００−２６２８７６に記載された移動ロボットを利用しても良い）。上記ロボットコントローラ２は、メモリ６と、ＣＰＵ７と、制御ドライバ８とを備えて構成されている。
【０００９】
このロボットコントローラ２は、教示ペンダント９から与えられた教示データや、パソコン（ＰＣ）１０から与えられた教示データに基づいて、ロボットアーム３及び走行台車４を制御するように構成されている。教示ペンダント９は、ロボットコントローラ２にケーブルを介して着脱可能に接続されている。また、ＰＣ１０は、ロボットコントローラ２にケーブルを介して着脱可能に接続されている、または、無線ＬＡＮを介して接続されている。
【００１０】
上記ＰＣ１０は、本実施例の「複数作業を遂行する移動ロボット１の最適動作計画法」を実際に計算するコンピュータであり、その計算を実行するためのシミュレーションプログラムを備えている。この場合、ＰＣ１０は、オフラインシミュレータである。そして、ＰＣ１０は、移動ロボットの停止箇所決定装置を構成している。
また、ＰＣ１０は、複数の作業について、移動ロボット１のロボットアーム３の可動作業空間内の領域を作業判定領域とすると共に、各作業判定領域内に設定間隔の格子点を配置する手段としての機能と、前記各格子点において前記移動ロボット１による作業が遂行可能であるか否かを判断して前記複数の作業に対応する作業可能領域を設定する手段としての機能と、前記複数の作業可能領域の重なりが最適となるように組み合わせる手段としての機能と、前記組み合わせた作業可能領域の重なった領域において、コストが最小となる作業箇所を求めることにより、最少停止箇所を決定する手段としての機能と、前記各停止箇所において、前記移動ロボット１のロボットアーム３の作業順序を最適化する手段としての機能と、前記各停止箇所の間の走行経路を、コストが最小となるように決定する手段としての機能とを備えている。
【００１１】
次に、本実施例の「複数作業を遂行する移動ロボット１の最適動作計画法」のシステム（即ち、シミュレーションプログラム）について、図１、図３ないし図９も参照しながら具体的に説明する。
まず、本実施例のシステムの設定条件について述べる。
ここで、「作業」とは、作業環境内に散在する複数の物体を移動ロボット１のマニピュレータ（ロボットアーム３）で把持して搬送することである。
【００１２】
「作業情報」とは、その作業を遂行する際のマニピュレータ（ロボットアーム３）手先の初期コンフィグレーションと目標コンフィグレーションの組である。
また、障害物配置などの環境情報は、既知とする。作業は、任意の順序で遂行可能とする。システムの入力値は、各作業の作業情報である。システムの出力は、複数の作業箇所と、各作業箇所での作業順序と、作業箇所間の移動経路（走行経路）とである。
【００１３】
走行台車４は、ある位置姿勢において特定の方向のみに進行できるノンホロノミック特性を有する。
また、安定性、精度の問題から、移動しながらの作業は行わない。走行台車４の走行距離、移動回数は少ないほど良いとする。これは、走行時間だけでなく、移動後の走行台車４の位置補正にも時間を要し、また、位置決めにより誤差が生じ易いためである。
【００１４】
さて、本実施例においては、システムが解決すべき問題を次の３つにわけている。
第１の問題は、複数ある作業を複数の作業箇所にどう割り当てるかという問題、即ち、割当問題である。
第２の問題は、複数の作業をどの順序で遂行するか、また、複数作業箇所をどの順序で巡るか、という巡回問題である。
【００１５】
第３の問題は、ロボットアーム３（マニピュレータ）手先や走行台車４の、初期コンフィグレーションから目標コンフィグレーションまでの軌道をどう生成するか、という動作計画問題である。
これらの問題を解くために、本実施例における最優先の評価指標を、「走行台車４の移動回数を最少化すること、即ち、作業箇所数を最少化すること」としている。そして、この評価指標を満たした上で、「複数得られる最少数の作業箇所の組み合わせのうちどれが良いか、複数作業箇所をどの順序で巡れば良いか、各作業箇所においてどの手順で作業を遂行すれば良いか」という問題については、統合して最適解を導出するように構成している。
【００１６】
以下、図１のフローチャートに従って、本実施例のシステムの作業フローについて具体的に説明する。まず、ステップＳ１において、作業判定領域に格子点を配置する。ここで、作業判定領域とは、移動ロボット１のロボットアーム３の可動作業空間内の領域（３次元空間）のことであり、判定対象領域と呼んでもよい。この作業判定領域に格子点を配置する処理を、以下、説明する。
【００１７】
図７（ａ）に示すように、作業が例えば６つあり、それぞれ作業情報が与えられているとする。尚、図では、２次元平面で表現しているが、実際は位置姿勢の３次元である。また、図中では簡単にするために、作業情報を、２つの丸とそれを結ぶ矢印で表現した。これは、ロボットアーム３手先が１つ目の丸（初期コンフィグレーション）から矢印の先の丸（目標コンフィグレーション）へ動くという作業情報を意味する。
【００１８】
この場合、図７（ａ）に示す６つの作業Ｔ１〜Ｔ６を遂行可能か否かの判断を、作業環境内の全域で行うと、計算量が膨大なってしまうため、手先の初期コンフィグレーションから一定距離Ｒ以内、且つ、目標コンフィグレーションから同じく一定距離Ｒ以内に含まれる領域を、判定対象領域（作業判定領域）として抽出する。例えば、図７（ｂ）に示す斜線領域が、Ｔ１の判定対象領域である。尚、上記距離Ｒは、ロボットアーム３の腕を最大限に伸ばして届く距離に基づいて適宜決めればよい。そして、上記判定対象領域（作業判定領域）に設定間隔の格子点を配置する（図７（ｃ）参照）。
【００１９】
次に、ステップＳ２へ進み、上記判定対象領域に配置した各格子点に対応するコンフィグレーションを走行台車４がとったときに、ロボットアーム３が作業遂行可能であるか否かを判定する。このときの判定条件は、手先の初期・目標コンフィグレーションを達成可能か（第１条件）、障害物に干渉することなく作業を達成する手先軌道が実現可能か（第２条件）、手先がある一定値以上の可操作性を持ち得るか（第３条件）、という３つの条件である。
【００２０】
この場合、第３条件は、走行台車４の位置姿勢誤差もしくは作業対象の位置姿勢誤差により作業が達成不可能になることを防ぐためである。また、第２条件は、ロボットアーム３の動作計画問題を解くことで判定する。更に、第３条件の可操作性については、ここでは、第１条件及び第２条件を満たした格子点のうち、（ｘ、ｙ、θ）について６近傍も全て条件を満たしているもののみを選択することで対処する。
【００２１】
具体的には、図３のフローチャートに示すサブルーチンを実行する。まず、ステップＳ２０１で、１番目の格子点について、第１条件（手先の初期・目標コンフィグレーションが達成可能か）を調べる。ここで、第１条件を満たせば、「ＹＥＳ」へ進み、第２条件（作業を達成する手先軌道が実現可能か）を調べる（ステップＳ２０２）。ここで、第２条件を満たせば、「ＹＥＳ」へ進み、第３条件（手先がある一定値以上の可操作性を持ち得るか）を調べる（ステップＳ２０３）。そして、第３条件をみたせば、その格子点を、作業可能点とする（ステップＳ２０４）。
【００２２】
一方、上記各ステップＳ２０１、Ｓ２０２、Ｓ２０３において、各条件を満たさない場合には、それぞれ「ＮＯ」へ進み、その格子点を、作業不可能点とする（ステップＳ２０５）。
そして、ステップＳ２０６へ進み、各作業判定領域（判定対象領域）内の全ての格子点について、作業可能であるか否かの判定を完了したか否かを判断する。ここで、判定完了の場合は、「ＹＥＳ」へ進み、判定処理を終える。判定が未完了の場合は、「ＮＯ」へ進み、ステップＳ２０１へ戻り、次の格子点の判定を続行するように構成されている。
【００２３】
これにより、各格子点でどの作業が遂行可能であるかという判定結果が得られる。この判定結果に基づいて、同一作業が遂行可能な格子点をまとめることにより、各作業Ｔ１〜Ｔ６はどの領域で遂行可能かという情報、即ち、作業可能領域（作業箇所領域）Ａ１〜Ａ６を得る（図７（ｄ）参照）。この場合、作業可能領域とは、移動ロボット１の走行台車４がどの位置姿勢をとって停止しても作業遂行が可能な作業箇所を含む領域（３次元空間）のことであり、作業箇所領域と呼んでもよい。
【００２４】
次に、図１のステップＳ３へ進み、全作業を遂行可能な最少数の作業可能領域を判定する。具体的には、図４のフローチャートで示すサブルーチンを実行する。まず、ステップＳ３０１へ進み、作業可能領域で重複する領域を再定義する。この場合、上記したようにして求めた作業可能領域Ａ１〜Ａ６は、図８に示すように、重複する（重なる部分がある）ことから、各重複領域をＡ７〜Ａ１２と定義する。そして、各領域が遂行可能作業を要素として持つとしたとき、その領域は、その要素に任意の要素が付加した領域をも含むものとして再定義する。例えば、作業可能領域Ａ１はＡ７、Ａ８、Ａ９を含み、Ａ７はＡ９を含む、とする。
【００２５】
上記図８に示す例の場合、１２個の領域が構成されたことになるが、一般的には、作業数をｎとしたとき、領域数は最大で、
【００２６】
【数１】
2005088164.tif 000003
である。
次に、図４のステップＳ３０２へ進み、それらの領域の中からどれを選択すれば、最少数の領域で全作業を遂行することができるかを調べる。この問題は、集合被服問題（Set Covering Problem）として解く。
【００２７】
ここで、集合被服問題とは、各列にコストの付与されたｍ行ｎ列の０−１行列ａijの行を、列の部分集合の組合せによって最小コストで被覆する問題である。
ｘj＝１：列ｊ（コストｃj＞０）が解の中にあるとき、
ｘj＝０：それ以外
と定義すると、集合被服問題は次のように表現される。
【００２８】
【数２】
2005088164.tif 000004
そこで、行を作業番号、列を各作業可能領域の番号とすれば、上記ステップＳ３０２の問題は、作業可能領域の組合せによって全作業を被覆する問題となり、集合被服問題の一種と捉えられる。ただし、以下の特徴を有する。
【００２９】
・コストが存在せず（もしくは）一律であり、コストではなく、被覆に要する部分集合を最少化する。
・解を列挙する必要がある。
この問題を、本実施例では、最少集合被服問題（Least Set Covering Problem）と呼ぶ。
【００３０】
さて、図８で構成した領域から生成される行列ａijを下記の式（１）に示す。尚、見易くするため、要素は１のみ記した。
【００３１】
【数３】
2005088164.tif 000005
この問題を集合被服問題として解いた場合、以下の３つの解が得られる。
【００３２】
【数４】
2005088164.tif 000006
ここで、３つ目の解に着目する。この領域の組合せでは、Ａ９，Ａ１１のどちらでも作業Ｔ４を遂行可能である。Ｔ４をＡ９で遂行する場合は、Ａ１１ではＴ３のみを遂行することになる。このとき、Ａ３がＡ１１を含んでいるため、この解は１つ目の解に吸収される。逆に、Ｔ４をＡ１１で遂行する場合は、この解は２つ目の解に吸収される。つまり、解は２つに集約されることになる。よって、本問題において得られるべき解は、１つ目と２つ目のみである。
【００３３】
これは、最少集合被服問題を集合分割問題（Set Partitioning Problem）と捉えることに帰着する。集合分割問題とは、集合被服問題の制約条件の不等号≧が等号＝になったものであり、各行が解の部分集合のただ１つによって被覆されることを意味する。集合分割問題として扱えることで、作業可能領域の組合せが減り、計算量の削減になる。
この特徴は、前述したステップＳ３０１で再定義した領域の構成法に起因する。仮に、この再定義を行わず、Ａ１を、Ａ７〜Ａ８を除去した領域、即ち、作業Ｔ１のみを遂行可能な領域として定義し、同様にしてＡ７を、Ａ９を除去した領域、即ち、作業Ｔ１とＴ５のみ遂行可能でＡ４は遂行不可能な領域、のように定義すると、３つ目の解は他の解に吸収され得ず、解の領域に重複して含まれるＴ４のような作業をどちらで遂行するか、という問題を生む。従って、上記ステップＳ３０１の再定義は有効である。
【００３４】
さて、集合分割問題は、一般にＮＰ−困難の問題であり、様々な近似解導出法が提案されている。これに対し、本問題は、規模が小さい上に前記特徴を持つので、以下に説明する簡単な分枝限定操作によって現実的時間内で最適解を導出することが可能である。
（１）被覆行数が最大である列を親とする。親を解の一部として採用する。
（２）親が被覆した行を削除する。これは、親が被覆した行はもう被覆する必要がないからである。
【００３５】
（３）親と同じ行を被覆する列を採用すると集合分割にならないため、被覆行が１つ以上削除された列を、削除する。
（４）全行が被覆されるまで、上記操作を繰り返す。
（５）親の列を削除した上で、新たに親を選択し、操作を繰り返す。既に得られている被覆に要する列数と同数で被覆できるものが解となる。親の被覆行数が小さくなっていくため、最少列数での被覆ができるか否かの判定は可能である。できなくなった時点で終了する。
【００３６】
これにより、最少数の作業可能領域の集合を得ることができる（図４のステップＳ３０３参照）。
次に、図１のステップＳ４へ進み、各領域内の各格子点上での最短時間で実行可能なロボットアーム３の作業順序を判定し、作業遂行時間を算出する。具体的には、各領域内の各格子点のコンフィグレーションを走行台車４がとったときに、複数の作業情報として与えられた手先コンフィグレーションをどの順序で達成すれば最短時間で作業が遂行可能かを(即ち、作業順序を）、スタッカ・クレーン問題（Stacker Crane Problem）を解くことで導出する。この場合、コストは作業遂行時間である。解となる順序での総コストが、その領域で遂行すべき作業を全て実現するのに要するコストである。
【００３７】
続いて、ステップＳ５へ進み、領域内の格子点を繋ぐグラフを生成し、コスト最小（即ち、作業遂行時間最短）の格子点の集合を判定する。この場合、まず、作業箇所を巡る順序を列挙する。前記ステップＳ３で得られた２つの解より、作業箇所を巡る順序は、
Ａ３−Ａ９−Ａ１２，Ａ３−Ａ１２−Ａ９，Ａ９−Ａ３−Ａ１２，
Ａ７−Ａ１１−Ａ１２，Ａ７−Ａ１２−Ａ１１，Ａ１１−Ａ７−Ａ１２
の６種類である。一般に、ｎ箇所の組の解がｍ個あれば、ｍ＊ｎ！／２個の順列の種類がある。
【００３８】
そして、上記したようにして得られた順序で領域を繋ぐ。そのとき、領域内の各格子点を次の領域内の各格子点と繋ぐ。これにより、各格子点をノードとしたグラフが構成される（図９参照）。グラフは、順列の個数だけ生成されるが、図４には、２つだけ示した。図４（ａ）はＡ９−Ａ３−Ａ１２の場合であり、図４（ｂ）はＡ７−Ａ１１−Ａ１２の場合である。また、各領域内の格子点の数は、見易くするために３点とした。
【００３９】
次に、格子点の組合せを判定するのであるが、これは、図５に示すフローチャートのサブルーチンに従って実行する。まず、ステップＳ５０１にて、各作業領域内で格子点を１点選択する。そして、ステップＳ５０２へ進み、作業可能領域の集合毎に、他の領域の選択された格子点間を繋ぐアークを作成する。続いて、ステップＳ５０３へ進み、各格子点で閉ループのアークを生成する。
【００４０】
更に、ステップＳ５０４へ進み、全アークにコストを割り付ける。この場合、閉ループのアークには、作業遂行コスト（その格子点での作業遂行時間、即ち、前記したように求めた総コスト）を割り付ける（図９中のｔｙｐｅ−１参照）。また、格子点間のアークには、走行台車４の移動コスト（走行台車４が移動するのに要する移動距離（経路長））を割り付ける（図９中のｔｙｐｅ−２参照）。
【００４１】
ここで、上記経路の導出方法としては、例えば、公知の文献
（T.Kito,J.Ota,R.Katsuki,T.Mizuta,T.Arai,T.Ueyama,T.Nishiyama:Smooth Path Planning by Using Visibility Graph-like Methode,Proc.of IEEE Int.Conf.on Robotics and Automation,to appear,(2003)）
に記載された方法を用いれば良い。
【００４２】
そして、ステップＳ５０５へ進み、走行台車４の巡回順序も考慮しながら、例えばグラフ探索のDijkstra法によりコスト最小のアーク、即ち、構成されたグラフのコスト最小解を算出する。これにより、最適な作業箇所、その作業箇所での作業順序、作業箇所間を繋ぐ移動経路の組合せが導出される。この場合、グラフが複数の場合には、各々の最小コストを比較し、コスト最小のものを最終的な解とする。
【００４３】
続いて、図１のステップＳ６へ進み、上述した計算により導出された解、即ち、最少停止箇所（最適な作業箇所）、各停止箇所（作業箇所）での作業順序、各停止箇所（作業箇所）間の走行経路（移動経路）を、出力するように構成されている。これら出力データは、ＰＣ１０から移動ロボット１のロボットコントローラ２へ与えられるようになっている。そして、ロボットコントローラ２は、上記与えられたデータに基づいてロボットアーム３及び走行台車４をそれぞれ制御するように構成されている。
【００４４】
次に、上述した格子点の組合せを判定する計算（ステップＳ５０１〜Ｓ５０５）の計算量を削減する制御（サブルーチン）について、図６に示すフローチャートを参照して説明する。まず、計算量削減の条件について説明する。前述したように、探索グラフは、順列の数だけ生成される。
そこで、計算量削減のため、「作業可能領域（作業箇所領域）同士は十分離れている」という条件を仮定する。「十分離れている」とは、「各領域内のどの位置姿勢を走行台車４が選択しようとも、それによる作業遂行時間・移動時間の差に、作業箇所を繋ぐ順序が影響されない程度」という意味である。この仮定により、作業箇所巡回順序を先に決定することが可能になる。
【００４５】
具体的には、図６のステップＳ６０１において、各作業領域内で代表格子点を１点算出する。例えば、作業領域内の重心近傍の格子点を代表格子点とする（この場合、走行台車４の停止箇所を代表格子点とすることから、解は準最適解となる）。続いて、ステップＳ６０２へ進み、作業可能領域の集合毎に、代表格子点間をアークで繋ぎ、アークの直線長をコストとして割り付け、これを巡回セールス問題（Traveling Salesman Problem）として解くことにより、走行台車４の移動コスト最小となる巡回順序を算出する。この場合、探索グラフは、各解から１つずつ、前述した例では、２つだけ生成すれば良いことになる。尚、巡回セールス問題の解法としては、周知の解法を適宜使用すれば良い。
【００４６】
そして、ステップＳ６０３へ進み、各作業領域の集合毎に巡回順序を決定する。続いて、ステップＳ６０４へ進み、作業領域の集合間での最小コストとなる作業領域の集合を算出する。尚、上記した仮定は、実際の工場環境においては多くは成立することから、従って、有効な計算量削減手法となる。
このような構成の本実施例においては、複数の作業について、移動ロボット１のロボットアーム３の可動作業空間内の領域を作業判定領域とすると共に、各作業判定領域内に設定間隔の格子点を配置するステップ（図１のステップＳ１参照）を備え、前記各格子点において前記移動ロボット１による作業が遂行可能であるか否かを判断して前記複数の作業に対応する作業可能領域を設定するステップ（図１のステップＳ２参照）を備え、前記複数の作業可能領域の重なりが最適となるように組み合わせるステップ（図１のステップＳ３参照）を備え、前記組み合わせた作業可能領域の重なった領域において、作業コストが最小となる作業箇所を求めることにより、最小停止箇所を決定するステップ（図１のステップＳ４、Ｓ５参照）を備えるように構成した。
【００４７】
この停止箇所決定方法によれば、複数の作業箇所が存在する作業を移動ロボット１に遂行させる場合において、作業者が各作業の作業情報をＰＣ１０に与えるだけで、コストを評価基準として最適化された移動ロボット１の最少停止箇所をＰＣ１０から得ることができる。従って、作業者が移動ロボットの停止位置を経験的に決める場合に比べて、コスト（即ち、作業遂行時間）を小さくすることができる。
【００４８】
また、上記実施例においては、移動ロボット１の各停止箇所において、移動ロボット１のロボットアーム３の作業順序を最適化するステップ（図１のステップＳ４参照）を備えるように構成した。この構成によれば、ロボットアーム３の作業順序を最適化することができるので、コスト（即ち、作業遂行時間）をより一層小さくすることができる。
更に、上記実施例では、移動ロボット１の各停止箇所の間の走行経路（移動経路）を、コストが最小となるように決定するステップ（図１のステップＳ５参照）を備えるように構成した。この構成によれば、移動ロボット１の走行経路（移動経路）がコスト最小の経路となるので、コスト（即ち、作業遂行時間）をより一層小さくすることができる。
【００４９】
尚、上記実施例においては、移動ロボット１の停止位置を決定するシステムに適用したが、これに限られるものではなく、本発明を固定式ロボットのベース位置を最適化するように決定するシステムに適用（即ち、ベース位置の最適化手法として応用）するように構成しても良い。
【図面の簡単な説明】
【００５０】
【図１】本発明の一実施例を示す作業フローのフローチャート
【図２】移動ロボットのブロック図
【図３】格子点で作業可能であるか否かを判定するサブルーチンのフローチャート
【図４】作業可能領域の組合せを判定するサブルーチンのフローチャート
【図５】格子点の組合せを判定するサブルーチンのフローチャート
【図６】格子点の組合せを判定する他のサブルーチン（計算量を削減したもの）のフローチャート
【図７】（ａ）は複数の作業を示す図、（ｂ）は作業判定領域を示す図、（ｃ）は作業判定領域に格子点を配置した様子を示す図、（ｄ）は作業可能領域を示す図
【図８】作業可能領域の重複を示す図
【図９】探索グラフの構造を示す図
【符号の説明】
【００５１】
図面中、１は移動ロボット、２はロボットコントローラ、３はロボットアーム、４は走行台車、７はＣＰＵ、９は教示ペンダント、１０はＰＣ（移動ロボットの停止箇所決定装置）を示す。
【図１】
2005088164.tif 000007
【図２】
2005088164.tif 000008
【図３】
2005088164.tif 000009
【図４】
2005088164.tif 000010
【図５】
2005088164.tif 000011
【図６】
2005088164.tif 000012
【図７】
2005088164.tif 000013
【図８】
2005088164.tif 000014
【図９】
2005088164.tif 000015