(57)【特許請求の範囲】
【請求項１】
共通の作業空間を有する１対のロボットのデッドロックを防止する方法であって、前記ロボットの各々は、関連のプログラムによって制御され、通常プログラム動作を生成するためにプログラムが同時に実行されるとき、前記ロボットの各々が、前記関連のプログラムの実行の一部の間に前記共通の作業空間の少なくとも一部を占有し、
前記通常プログラム動作の前に、前記共通の作業空間の占有された部分をボクセルモデルで表すことを含む前記プログラムに従うロックダウンモードの開始動作又はオフライン実行によって、前記ロボットによって占有される前記共通の作業空間の部分を決定するステップと、
前記ロボットによって占有される前記共通の作業空間の部分と重なる少なくとも一つの干渉領域を決定するために前記ボクセルモデルを比較することによって、前記少なくとも一つの干渉領域を決定するステップと、
前記少なくとも一つの干渉領域を分析するとともに二つのロボットのうちの少なくとも一つのデッドロック状態が生じうる場所を決定するステップと、
前記通常プログラム動作の前記プログラムの実行前に前記少なくとも一つのデッドロック状態を回避するための機構を自動的に決定するとともに前記機構を前記プログラムの少なくとも一つに関連させることによって、前記通常プログラム動作の前記プログラムの実行中に前記少なくとも一つのデッドロック状態を回避するステップと、
を備えることを特徴とする方法。
【請求項２】
前記機構は、少なくとも一つのデッドロックフリー動作ステートメントを含む請求項１に記載の方法。
【請求項３】
前記少なくとも一つのデッドロックフリー動作ステートメントを、前記プログラムの少なくとも一つに追加することによって関連させる請求項２に記載の方法。
【請求項４】
前記少なくとも一つのデッドロックフリー動作ステートメントを、前記プログラムの少なくとも一つにある少なくとも一つの命令を変更することによって関連させる請求項２に記載の方法。
【請求項５】
前記少なくとも一つのデッドロックフリー動作ステートメントを、前記プログラムの少なくとも一つにある命令を並べ直すことによって関連させる請求項２に記載の方法。
【請求項６】
前記少なくとも一つのデッドロックフリー動作ステートメントを、待機コマンドを前記プログラムの少なくとも一つに追加することによって関連させる請求項２に記載の方法。
【請求項７】
共通の作業空間を有する１対のロボットのデッドロックを防止する方法を実行するためにコンピュータによって実行可能な命令を有するコンピュータ読出し可能媒体であって、前記ロボットの各々は、関連のプログラムによって制御され、通常プログラム動作を生成するためにプログラムが同時に実行されるとき、前記ロボットの各々が、前記関連のプログラムの実行の一部の間に前記共通の作業空間の少なくとも一部を占有し、前記コンピュータ読出し可能媒体は、
前記通常プログラム動作の前に、前記共通の作業空間の占有された部分をボクセルモデルで表すことを含む前記プログラムに従うロックダウンモードの開始動作又はオフライン実行によって、前記ロボットによって占有される前記共通の作業空間の部分を決定する命令と、
前記共通の作業空間の部分と重なる少なくとも一つの干渉領域を決定するために前記ボクセルモデルを比較することによって、前記少なくとも一つの干渉領域を決定する命令と、
前記少なくとも一つの干渉領域を分析するとともに二つのロボットのうちの少なくとも一つのデッドロック状態が生じうる場所を決定する命令と、
前記通常プログラム動作の前記プログラムの実行前に前記少なくとも一つのデッドロック状態を回避するための機構を自動的に決定するとともに前記機構を前記プログラムの少なくとも一つに関連させることによって、前記通常プログラム動作の前記プログラムの実行中に前記少なくとも一つのデッドロック状態を回避する命令と、
を備えることを特徴とするコンピュータ読出し可能媒体。
【請求項８】
前記機構は、少なくとも一つのデッドロックフリー動作ステートメントを含む請求項７に記載のコンピュータ読出し可能媒体。
【請求項９】
前記少なくとも一つのデッドロックフリー動作ステートメントを、前記プログラムの少なくとも一つに追加することによって関連させる請求項８に記載のコンピュータ読出し可能媒体。
【請求項１０】
前記少なくとも一つのデッドロックフリー動作ステートメントを、前記プログラムの少なくとも一つにある少なくとも一つの命令を変更することによって関連させる請求項８に記載のコンピュータ読出し可能媒体。
【請求項１１】
前記少なくとも一つのデッドロックフリー動作ステートメントを、前記プログラムの少なくとも一つにある命令を並べ直すことによって関連させる請求項８に記載のコンピュータ読出し可能媒体。
【請求項１２】
前記少なくとも一つのデッドロックフリー動作ステートメントを、待機コマンドを前記プログラムの少なくとも一つに追加することによって関連させる請求項８に記載のコンピュータ読出し可能媒体。
【請求項１３】
共通の作業空間を有する複数のロボットのデッドロックを防止する方法であって、前記ロボットの各々は、関連のプログラムによって制御され、通常プログラム動作を生成するためにプログラムが同時に実行されるとき、前記ロボットの各々が、前記関連のプログラムの実行の一部の間に前記共通の作業空間の少なくとも一部を占有し、
前記通常プログラム動作の前に、前記共通の作業空間の占有された部分をボクセルモデルで表すことを含む前記プログラムに従うロックダウンモードの開始動作又はオフライン実行によって、前記ロボットによって占有される前記共通の作業空間の部分を決定するステップと、
前記ロボットの少なくとも二つのロボットについて前記共通の作業空間の部分と重なる少なくとも一つの干渉領域を決定するために前記ボクセルモデルを比較することによって、前記少なくとも一つの干渉領域を決定するステップと、
前記少なくとも一つの干渉領域を分析するとともに前記少なくとも二つのロボットのうちの少なくとも一つのデッドロック状態が生じうる場所を決定するステップと、
前記通常プログラム動作の前記プログラムの実行前に前記少なくとも一つのデッドロック状態を回避するための機構を自動的に決定するとともに前記機構を前記プログラムの少なくとも一つに関連させることによって、前記通常プログラム動作の前記プログラムの実行中に前記少なくとも一つのデッドロック状態を回避するステップと、
を備えることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
この出願は、２００８年５月２１日に出願された同時係属中の米国特許出願第１２／１２４，４３０号の一部継続出願である。
【０００２】
この出願は、２０１１年５月５日に出願された米国特許仮出願第６１／４８２，８０８号の利益を主張する。
【０００３】
本発明は、一般的には複数のロボットを制御するシステム及び複数のロボットの動作干渉回避を制御する方法に関する。
【背景技術】
【０００４】
空間中の物体の動作は、典型的な製造環境における必要なタスクである。必要な動作を行うためにロボット工学がますます用いられるようになってきている。しかしながら、複数の物体を動作させるときに、物体間に干渉が生じることがある。物体が同一の座標系に対して同一の座標を有するときのように少なくとも二つの物体が同一の空間を同時に共有する場合、干渉がある。
【０００５】
最近の産業用ロボットは相当な速度で動作するので、ロボット間の干渉によって衝突が生じ、ロボット及びロボットによって操作されるワークピースに不所望な損傷が加えられることがある。衝突により製造工程中に犠牲の大きい故障時間が生じることがある。したがって、そのような衝突を回避することが望ましい。
【０００６】
従来のシステム及び方法は、干渉及び衝突を最小にするために用いられてきた。しかしながら、従来のシステム及び方法の複数の欠点が存在する。典型的には、工具中心点（ＴＣＰ）は、予め決定された干渉エリアすなわち「静的空間」(static space)に対してのみ確認される。複数のロボットに対して、これらの衝突又は干渉を直ちに又は有効に防止するのは困難である。さらに、複数の動作するロボットの静止座標系に関する干渉空間を特定するのは困難である。任意の干渉空間はロボットの動作経路の関数であるだけでなく動作速度の関数でもある。二つ以上のロボットが共用空間で同時に動作することを要求するときのデッドロック状態を処理することを試みる際の困難もある。
【０００７】
従来のシステムは、世界座標系に対する固定空間でロボットのＴＣＰが衝突するのを防止する試みも行っている。（複数のコントローラを有する）複数のロボットがタスク実行中に共通空間すなわち「干渉」空間を共有するとき、各コントローラは、ロボットが共通空間に存在しなくなるまで待機する必要がある。この場合、コントローラは、ロボットに動作を許容するために動作制御コマンドを発することができる。この工程は、「待機及び動作」工程とも称され、一般的には作業サイクル時間を増大する。しかしながら、干渉空間はロボットの動作経路の関数であるだけでなく動作速度の関数でもあるので、固定座標系に対する干渉空間を有効に特定するのは困難である。一つを超えるロボットが共通空間で同時に動作することを要求するとき、ロボットは、ロボットが互いに待機するためにいずれのロボットも動作することができないデッドロック状態を作り出す。
【０００８】
従来のシステムは、球及び円柱によってロボットのモデルを作る試みも行っている。従来のシステムは、リアルタイムでの動作中にロボットの将来の位置を予測する。従来のシステムは所定の時間に亘ってロボットによって占有される累積空間(accumulated space)を決定しないので、従来のシステムは、ロボットの動作中に頻繁に比較を行う必要がある。従来のシステムは、作業セルの全てのロボットのモデルを構成要素ごとに比較する。この比較は、計算コストが非常に高くなり、コストは、ロボット並びにロボット及び工具のモデルを作るのに用いられる構成要素の個数が増大するに従って飛躍的に高くなる。差し迫った衝突が検出されるときに比較がリアルタイムで行われるので、従来のシステムは、一般的には差し迫った衝突に伴う全てのロボットを停止させる必要があり、自動プログラム動作を中断する必要がある。従来のシステムは、ロボットが異なるコントローラに属するときに更に困難になる。その理由は、従来のシステムがコントローラ間でリアルタイムの通信を行うために多量の情報を必要とするからである。従来のシステムは、干渉を回避するためにＩ／Ｏハンドシェイク機構を利用する試みも行っている。本発明において、Ｉ／Ｏ  ＰＬＣの必要はない。
【０００９】
既知のシステム及び方法の一つは、譲受人による同時係属中の国際出願番号ＰＣＴ／ＵＳ２００７／０６６６３８に開示されており、参照すにより全体がここに組み込まれる。かかるシステム及び方法は、ロボットの動作の効率を最大にするとともに複数のロボットの干渉又は衝突の可能性を最小にする「動的空間確認」(dynamic space check)システムを有する。各コントローラによって制御されるロボットは、ユーザによって定義された動的空間(user-defined dynamic space)でのみ動作し、これにより衝突を回避する。しかしながら、動的空間確認システムは、一般的にはユーザによって定義された直線で囲まれた空間(user-defined rectilinear space)に対してのみＴＣＰを保護する。
【００１０】
ロボットの衝突を回避する他の既知の方法は、Pollack等による米国特許第５，１５０，４５２号明細書で報告されている。この方法は、所望のロボットの動作を含む衝突マップを作成することを含む。排他的論理和演算においてロボットマップと「ワールド」マップとを組み合わせ、その後、排他的論理和演算において衝突マップと「ワールド」マップとを組み合わせるのに続いて包含的論理和演算において衝突マップと「ワールド」マップとを組み合わせることをバイト単位で行うことによって、所望のロボットの元の位置が「ワールド」マップから取り除かれる。衝突は、包含的論理和の組合せ及び排他的論理和の組合せの任意のビット位置の差によって表される。この方法は、衝突を検出するために２次元的なｘ−ｙ投影(x-y projection)及び１次元的な高さを与えるが、３次元的なリアルタイムの衝突検出を行うことができない。
【００１１】
ロボットと一つ以上の障害との間の衝突を衝突が生じる前に検出する更に別の既知の方法は、Greenspan等による米国特許第５，３４７，４５９号明細書に記載されている。ロボットは、ボクセル作業空間(voxelized workspace)において球によってモデルが作られる。作業空間中の各ボクセルには、最も近い障害からの距離に対応する値が割り当てられる。球の中心のボクセル値がボクセル中の他の球の半径より小さい場合には、衝突間近であると決定される。しかしながら、この方法は、単一のロボットアームを保護するだけである。ロボットは、球のみによってモデルが作られ、したがって、ロボットの重要な工程経路の保護には不十分である。
【００１２】
複数のロボットの動作干渉回避を制御するシステム及び方法が引き続き必要となっている。望ましくは、システム及び方法は、３次元的なリアルタイムの衝突の検出を行い、ロボットシステムにロボットの動作を予め提供し、衝突のないプログラムされた軌跡を保存し、かつ、重要な工程経路を保護する。
【００１３】
プログラム又はタスクが、プログラム又はタスクのいずれかの継続するシーケンシャル実行(continued sequential execution)の結果としてプログラム又はタスクに関連した一つ以上のロボット間に干渉が生じ、かつ、干渉なく順次に進行することができるプログラム又はタスクが存在しない状態になったとき、デッドロック状態が生じる。
【００１４】
Chaffee等による米国特許第７，１１４，１５７号は、設定命令(set order)においてリソースを取得することによってデッドロックを回避する方法を記載している。この方法はデッドロックを回避することができるが、この方法は、設定デッドロックフリー命令(set deadlock-free order)が決定されなかった場合には動作を許可する能力がない。さらに、この方法は、要求された命令が規定のデッドロックフリー命令とは別である場合にはデッドロックフリーとすることができる動作を許可しない。
【００１５】
Chang等による米国特許出願第２００９／０３２６７１１号明細書は、自動的に又は手動でデッドロックを回避するために自動区分(automatic zone)を利用する方法を記載する。Changは、デッドロックを防止するために優先値(priority value)を使用する方法を示唆している。Changは、優先値を使用しない場合にデッドロックを防止する方法を示唆していない。
【発明の概要】
【発明が解決しようとする課題】
【００１６】
本開示によれば、複数のロボットの動作干渉回避を制御するシステム及び方法であって、３次元的なリアルタイムの衝突の検出を行い、ロボットシステムにロボットの動作を予め提供し、衝突のないプログラムされた軌跡を保存し、かつ、Ｉ／Ｏハンドシェイク機構を利用することなく重要な工程経路を保護するシステム及び方法は、驚くべき発見である。
【課題を解決するための手段】
【００１７】
一実施の形態において、共通の作業空間を有する１対のロボットのデッドロックを防止する方法であって、ロボットの各々は、関連のプログラムによって制御され、プログラムが同時に実行されるとき、ロボットの各々が、関連のプログラムの実行の一部の間に共通の作業空間の少なくとも一部を占有し、プログラムの同時実行中に、ロボットによって占有される共通の作業空間の部分を識別するステップと、共通の作業空間の部分と重なる少なくとも一つの干渉領域を識別するステップと、少なくとも一つの干渉領域を分析するとともに二つのロボットのうちの少なくとも一つのデッドロック状態が生じうる場所を識別するステップと、少なくとも一つのデッドロック状態となるロボットの任意の動作の実行前に少なくとも一つのデッドロックフリー動作ステートメントを自動的に決定及び実行することによって、プログラムの実行中に少なくとも一つのデッドロック状態を回避するステップと、を備える。
【００１８】
他の実施の形態において、共通の作業空間を有する１対のロボットのデッドロックを防止する方法を実行するためにコンピュータによって実行可能な命令を有するコンピュータ読出し可能媒体であって、ロボットの各々は、関連のプログラムによって制御され、プログラムが同時実行されるとき、ロボットの各々が、関連のプログラムの実行の一部の間に共通の作業空間の少なくとも一部を占有し、方法は、プログラムの同時実行中に、ロボットによって占有される共通の作業空間の部分を識別する命令と、共通の作業空間の部分と重なる少なくとも一つの干渉領域を識別する命令と、少なくとも一つの干渉領域を分析するとともに二つのロボットのうちの少なくとも一つのデッドロック状態が生じうる場所を識別する命令と、少なくとも一つのデッドロック状態となるロボットの任意の動作の実行前に少なくとも一つのデッドロックフリー動作ステートメントを自動的に決定及び実行することによって、プログラムの実行中に少なくとも一つのデッドロック状態を回避する命令と、を備える。
【００１９】
他の実施の形態において、共通の作業空間を有する複数のロボットのデッドロックを防止する方法であって、ロボットの各々は、関連のプログラムによって制御され、プログラムが同時実行されるとき、ロボットの各々が、関連のプログラムの実行の一部の間に共通の作業空間の少なくとも一部を占有し、プログラムの同時実行中に、ロボットによって占有される共通の作業空間の部分を識別するステップと、ロボットの少なくとも二つのロボットについて共通の作業空間の部分と重なる少なくとも一つの干渉領域を識別するステップと、少なくとも一つの干渉領域を分析するとともに少なくとも二つのロボットのうちの少なくとも一つのデッドロック状態が生じうる場所を識別するステップと、少なくとも一つのデッドロック状態となる少なくとも二つのロボットの任意の動作の実行前に少なくとも一つのデッドロックフリー動作ステートメントを自動的に決定及び実行することによって、プログラムの実行中に少なくとも一つのデッドロック状態を回避するステップと、を備える。
【００２０】
本発明によるシステム及び方法は、既知のデッドロックフリーシーケンスを必要としない。本発明によるシステム及び方法は、あり得るデッドロック状態を自動的に決定し、あり得るデッドロック状態を回避する方法を確定する。本発明によるシステム及び方法は、デッドロックを防止するための優先値を必要としない。本発明によるシステム及び方法は、干渉状態を防止するのと同時に、存在しうるデットロック状態を防止する。
【００２１】
本発明の上記利点及び他の利点は、添付図面を考慮するときに好適な実施の形態の詳細の説明から当業者に明らかになる。
【図面の簡単な説明】
【００２２】
【図１】ワークセル内で動作する第１のロボット及び第２のロボットを有する本開示による典型的なロボットシステムを示す。
【図２】本開示による干渉確認自動区分法を示す工程図である。
【図３】図１に示す第１のロボットと第２のロボットのうちの一方のボクセル化モデルを示す。
【図４】図３に示すボクセル化モデルの等角図である。
【図５】第１のロボットと第２のロボットのうちの一方を覆うボクセル化した球及び円柱によって形成されたボクセル化モデルを有する図１に示す第１のロボットと第２のロボットのうちの一方の拡大図を示す。
【図６】複数のボクセルから形成した図５に示すボクセル化球およびボクセル化円柱を示す。
【図７Ａ】本発明によるデッドロックフリー行列及び関連のプログラムリストを示す。
【図７Ｂ】本発明によるデッドロックフリー行列及び関連のプログラムリストを示す。
【図７Ｃ】本発明によるデッドロックフリー行列及び関連のプログラムリストを示す。
【図８Ａ】本発明による干渉行列及び関連のプログラムリストを示す。
【図８Ｂ】本発明による干渉行列及び関連のプログラムリストを示す。
【図８Ｃ】本発明による干渉行列及び関連のプログラムリストを示す。
【図８Ｄ】本発明による干渉行列及び関連のプログラムリストを示す。
【図９】複数のデッドロック領域を組み合わせて単一のデッドロックフリー領域にする経路及び関連の表を示す。
【図１０】本発明によるデッドロック防止を行わない複数のロボットプログラム実行シーケンス及び本発明によるデッドロック防止を行う複数のロボットプログラム実行シーケンスを示す。
【図１１】本発明によるデッドロック回避シーケンスの流れ図である。
【図１２】本発明によるあり得るデッドロック領域を決定するための流れ図である。
【発明を実施するための形態】
【００２３】
以下の説明は、本質的には単なる例示であり、この開示、この出願又は使用を制限することを意図しない。図面中、対応する参照番号が同様な又は対応する部分及び特徴を表すことを理解すべきである。開示した方法に関して、示したステップは、本質的には例示であり、したがって、必須でも重要でない。
【００２４】
図１は、複数のロボット間の衝突回避を制御するロボットシステム２を示す線形図である。限定されない例として、ロボットシステム２を、少なくとも二つのロボットを有するボディーショップロボットシステム(body shop robot system)、ウォータジェット切断ロボットシステム(waterjet cutting robot system)、レーザ溶接ロボットシステム、アーク溶接ロボットシステム及び塗装ロボットシステムのうちの一つとすることができる。所望に応じて、複数のロボットを有する他のロボットシステム２を用いることもできる。
【００２５】
ロボットシステム２は、第１のロボット６及び第２のロボット８が動作するように構成されるエンベロープ(envelope)を規定するワークセル４を有する。第１のロボット６及び第２のロボット８は、ワークセル４内に配置された少なくとも一つの共通空間１０を選択的に占有するように構成される。第１のロボット６及び第２のロボット８のみを示すが、当然のことながら、ロボットシステム２は、開示の範囲及び精神から逸脱することなく２を超える数のロボットを有することができる。
【００２６】
第１のロボット６は、第１のプログラム経路(programmed path)に沿った第１のロボット６の動作中に共通空間１０の第１の部分１２を占有することができる。第２のロボット８は、第２のプログラム経路に沿った第２のロボット８の動作中に共通空間１０の第２の部分１４を占有することができる。第１の部分１２及び第２の部分１４は、「自動区分」(automatic zone)又は「自動ゾーン」(autozone)としても知られている。各プログラム経路は、一つ以上の自動区分を備え、各自動区分は、予め処理され、一つ以上の動作ステートメントから取得される。第１のプログラム経路及び第２のプログラム経路を、例えば、複数の動作ステートメントを有する一連の命令中の一つ以上の動作ステートメントによって制御することができる。当業者は、第１のロボット６及び第２のロボット８の動作を制御する干渉回避方法を用いない場合には第１の部分１２及び第２の部分１４が重なることがあるためにロボットの干渉の可能性があることを理解すべきである。
【００２７】
第１のロボット６及び第２のロボット８は、少なくとも一つのコントローラ１６，１８によって制御される。図１に示す実施の形態において、第１のロボット６は、第１のコントローラ１６によって制御され、第２のロボット８は、第２のコントローラ１８によって制御される。少なくとも一つのコントローラ１６，１８は、電源（図示せず）と電気的なやり取りを行うように適合される。コントローラ１６，１８は、コントローラ１６，１８内にあるコンピュータプログラムのような一連の命令を実行することができる。他の実施の形態において、一連の命令は、コントローラ１６，１８とやり取りを行うコンピュータ読出し可能媒体又はメモリに存在することができる。
【００２８】
ロボットシステム２は、種々のシステム構成要素に接続するように構成されたネットワーク媒体（図示せず）、プログラマブル論理装置（図示せず）及び少なくとも一つのコントローラ１６，１８と電気的なやり取りを行う教示装置(teaching device)２０のうちの少なくとも一つのような従来既知の他の構成要素を更に有することができる。特定の実施の形態において、教示装置２０は、モニタを有することができ、所望に応じてロボットシステム２のオペレータが観察するために、第１のロボット６、第２のロボット８、共通空間１０の第１の部分１２及び共通空間１０の第２の部分１４を映像によって表すように構成される。教示装置２０は、ロボットのジョグ操作を行うための一連の命令を行う(initiate)手段を有することもできる。
【００２９】
本開示による典型的な一連の命令を図２に示す。一連の命令は、干渉確認自動区分法(interference check automatic zone method)２００を有する。干渉確認自動区分法２００は、先ず、ワークセル４内に少なくとも一つの共通空間１０を設ける開始ステップ２０２を有する。開始ステップ２０２の後に第１の決定ステップ２０４及び第２の決定ステップ２０６が続く。第１の決定ステップ２０４は、第１のプログラム経路に沿った第１のロボット６の動作中に占有される共通空間１０の第１の部分１２の決定を含む。第２の決定ステップ２０６は、第２のプログラム経路に沿った第２のロボット８の動作中に占有される共通空間１０の第２の部分１４の決定を含む。当然のことながら、第１の部分１２及び第２の部分１４を、自動的に、すなわち、従来知られているような各ロボットの動作のユーザ指定区分を必要とすることなく決定することができる。その後、第１の部分１２及び第２の部分１４は、これらの間に重なり２１０が存在するか否かを決定するために比較ステップ２０８で比較される。
【００３０】
限定されない例として、第１の決定ステップ及び第２の決定ステップを、第１のロボット６及び第２のロボット８を有するロボットシステム２の開始動作中に実質的にリアルタイムで行うことができる。開始動作を、第１のロボット６と第２のロボット８との任意のあり得る衝突を回避するためにロックダウンモード(lockdown mode)において第１のロボット６及び第２のロボット８によって行うことができる。他の例において、第１の決定ステップ２０４及び第２の決定ステップ２０６を、例えば、リアルタイム動作中にロボット６，８によって占有することができる共通空間１０の第１の部分１２及び第２の部分１４を識別するために第１のプログラム経路及び第２のプログラム経路のオフライン実行(offline run)により行うことができる。第１の決定ステップ２０４及び第２の決定ステップ２０６中に識別された第１の部分１２及び第２の部分１４を、例えば、メモリに保持し、第１のロボット６及び第２のロボット８の次の動作中に再利用することができる。その結果、第１のロボット６及び第２のロボット８の衝突に影響を及ぼすために第１のロボット６及び第２のロボット８の動作のプログラム経路すなわち軌道が予め処理されるとともに保持されることを理解すべきである。
【００３１】
第１のロボット６及び第２のロボット８の第１の移動ステップ２１２及び第２の移動ステップ２１４は、重なり２１０の存在に応じて選択される。第１の部分１２と第２の部分１４との間に重なり２１０が存在する場合、ロボット６，８の衝突の可能性があり、第１の移動ステップ２１２が選択される。第１の移動ステップ２１２は、第１のプログラム経路に沿う第１のロボット６と第２のプログラム経路に沿う第２のロボット８のうちの一方のみの移動を含む。第１の部分１２と第２の部分１４との間に重なり２１０が存在しない場合、ロボット６，８の衝突の可能性がなく、第２の移動ステップ２１４が選択される。第２の移動ステップ２１４は、第１のプログラム経路に沿う第１のロボット６の移動及び第２のプログラム経路に沿う第２のロボット８の移動を含む。
【００３２】
第１の決定ステップ２０４及び第２の決定ステップ２０６を、従来既知の任意の手段によって行うことができる。本開示による一つの特定の実施の形態において、第１の決定ステップ２０４及び第２の決定ステップ２０６は、図３〜６に実例で示すような少なくとも一つのボクセル３０２を有する少なくとも一つのボクセルモデル３００を有する共通空間１０、第１の部分１２及び第２の部分１４のうちの少なくとも一つを表すステップを有することができる。ボクセル３０２は、３次元空間において規則的なグリッド上に値を表すボリュームエレメント(volume element)である。比較ステップ２０８は、例えば、第１の部分１２を表す第１のボクセルモデル３００と第２の部分１４を表す第２のボクセルモデル３００との間に重なり２１０が存在するか否かを決定するステップを有することができる。ボクセル３００は、一般的には第１のロボット６及び第２のロボット８の基部、アーム及び工具のような種々の構成要素の形状を近似する複数のボクセル３０２によって表される。
【００３３】
図３及び図４を参照すると、実例のボクセルモデル３００は、Ｘ軸、Ｙ軸及びＺ軸に沿った座標に配置された複数のボクセルを有することができる。ボクセルモデル３００は、第１のロボット６と第２のロボット８の少なくとも一方によって占有される共通空間１０の３次元ボリュームを表現するよう構成される。ボクセルモデル３００を、生成されるデータファイルの形態にすることができ、例えば、コントローラ１６，１８、他のコンピュータ読取可能媒体又は他のメモリに保存することができる。所定の実施の形態において、ボクセルモデル３００は、動的であり、ロボットの一連の動作に関連した複数のモデル３００を有する。動的なボクセルモデル３００を、第１のロボット６と第２のロボット８の少なくとも一方の動作中に占有される共通空間１０の３次元ボリュームを表現するために用いることができる。各自動区分を、ボクセルモデル３００の複数のスナップショット(snapshot)の累積／重ね合わせ(accumulation/superimposition)から取得し、各スナップショットは、一つ以上のＩＴＰ間隔から取り出される。
【００３４】
図５及び図６を参照すると、第１のロボット６及び第２のロボット８のボクセルモデル３００は、第１のロボット６及び第２のロボット８によって占有された３次元ボリュームを表すためにボクセル化された球５００及びボクセル化された円柱５０２のうちの少なくとも一方を有することができる。ここで更に説明するように、ボクセル化された球５００及びボクセル化された円柱５０２は、第１のロボット６及び第２のロボット８の基部、アーム及び工具のような種々の構成要素を表すことができる。ボクセル化された球５００及びボクセル化された円柱５０２は、一般的には第１のロボット６及び第２のロボット８の一般的な形状及び境界を近似するために相互配置された複数のボクセル３０２を有する。
【００３５】
当業者は、ボクセル化された球５００及びボクセル化された円柱５０２を任意の適切な手段によって生成することができることを理解すべきである。例えば、ボクセル化された球５００を、ロボット６，８の構成要素を表す典型的な球をＸ−Ｙ平面に投影することによって近似することができる。この場合、球を包囲する最も小さい円柱Ａが識別される。その後、同一の球をＹ−Ｚ平面に投影し、球を包囲する最も小さい円柱Ｂを識別する。その後、同一の球をＺ−Ｘ平面に投射し、球を包囲する最も小さい円柱Ｃを識別する。その後、ボクセル化された球５００は、円柱Ａ、円柱Ｂ及び円柱Ｃの交差を識別することによって近似される。
【００３６】
他の実施の形態において、ボクセル化された球５００を、ロボット６の構成要素及びロボット８の構成要素を表す球を包囲する最小のボックスを最初に見つけることによって近似することができる。ボックスは、ボリューム占有Ａを有する。ボックスＡの内側にあるとともに球の外側にあるボクセルボリューム占有Ｂが識別される。その後、ボクセル球５００は、値Ａから値Ｂを減算することによって近似される。
【００３７】
ボクセル化された球５００を、典型的な球とＸ−Ｙ平面との交差を識別することによって近似することもできる。交差は、Ｚ軸沿いに球の中心を有し、交差した円形プレートＡ１を形成する。円形面Ａ１には任意の高さが割り当てられ、その後、交差した円形プレートＡ１のボクセルの占有が識別される。さらに、円形プレートＡ２，Ａ３，．．．，Ａ（ｎ）を、典型的な球とＸ−Ｙ平面の交差をＺ軸に沿ってシフトすることによって決定し、これらのボリューム占有が同様に識別される。その後、ボクセル化された球５００は、典型的な球の円形プレートに対して識別されたボクセル占有の各々を統合することによって近似される。
【００３８】
ボクセル化された円柱５０２を、左半球／全球のボクセル占有Ａを識別し、右半球／全球のボクセル占有Ｂを識別し、左半球と右半球との間の複数の円形プレートのボクセル占有Ｃを識別することによって近似することができる。この場合、基線に垂直な円形基板が形成される。基線は、円柱の両端で二つの半球を接続する。次に、円形面を、円形基板をＺ軸に沿ってシフトすることによって取得することができる。基線のボクセル占有を計算し、次に、二つの半球間の全領域を満たすために基線をシフトすることもできる。次に、ボクセル化された円柱５０２を、ボクセル占有Ａ、ボクセル占有Ｂ及びボクセル占有Ｃの各々を統合することによって近似する。
【００３９】
ボクセル化された円柱５０２を近似する他の方法は、ロボットの構成要素を表す典型的な円柱を包囲することができる最小のボックスを最初に識別することを含む。ボックスはボリューム占有Ａを有する。その後、ボックスの内側にあるとともに円柱の外側にあるボクセルボリューム占有Ｂが識別される。次に、ボクセル化されたシリンダ５０２を、ボクセルボリューム占有Ａからボクセル占有Ｂを減算することによって近似する。当業者は、ロボット６，８の構成要素を表すボクセル化された球５００及び円柱５０２を近似するのに適切な他の手段を所望に応じて用いることができることを理解すべきである。
【００４０】
ボクセル化(voxelization)を、ロボット、アームドレスアウト(arm dressout)及びツーリング(tooling)を表すことができる任意のＣＡＤ表面又はボリューム(CAD surface or volume)から同様にして決定することもできる。
【００４１】
ボクセル化は、ロボットの動作セグメント(motion segment)によって占有される空間を表すのに非常に有効な方法である。ボクセル化工程は、ボクセル化された空間を形成するためにある程度の計算オーバーヘッド(computational overhead)を有するが、ランタイムコンポーネント(run-time component)は非常に有用である。一度空間がボクセル化されると、動作経路中にロボットによって占有される共通空間の複雑さの程度又は量に関係なくボクセル化された空間に要求される最大の記憶容量は固定される。ボクセル化された空間の間の干渉のランタイム確認は非常に有効である。好適な実施の形態は、ボクセル化された領域によって表すために干渉確認自動区分を提供するが、動作経路中にロボットによって占有される空間のボリューム又は表面を表す任意の方法を用いることができる。
【００４２】
他の実施の形態は、プログラムされた動作中、ジョグ操作によって開始される動作中又は他の手段によって開始される動作中の衝突を回避する。他の実施の形態は、動作中のロボットを、ワークセル中の静止しているロボット、他の固定された物体又は他の規定された領域への衝突から保護する。プログラムされた動作に対して、ボクセル化工程又は他の干渉確認自動区分モデル化工程を、オフライン中又はテストラン中に行うことができ、ボクセル化されたデータは、後の探索のために効率的に格納される。この工程を、新たな動作経路が新たなプログラム、ロボットのジョグ操作又は他の手段によって開始される動作から決定されるときにリアルタイムで行うこともできる。これらの場合に対して、一連の命令を、教示装置の使用又は動作を開始する他の手段によって決定することができる。実際の動作は、工程が完了するとともにこの干渉確認自動区分及び他の占有された干渉確認自動区分による干渉がなくなるまで開始するのを許可されない。
【００４３】
他の実施の形態において、共通空間１０の第１の部分１２及び第２の部分１４の少なくとも一方は、第１のロボット６及び第２のロボット８の少なくとも一方に取り付けられたツーリングによって占有されるツーリング空間(tooling space)及びドレスアウトアッセンブリ(dressout assembly)（例えば、アークツールワイヤフィーダ(ArcTool wire feeder)）を有することができる。重なり２１０を決定するステップは、第１の部分１２及び第２の部分１４の少なくとも一方とロボット以外の障害(non-robot obstacle)（図示せず）によって占有される共通空間１０の第３の部分との比較を含むこともできる。障害を、所望に応じて共通空間１０の寸法、形状及び位置を規定するのに用いられるパラメータのセットによって手動で特定することができる。他の例において、方法２００は、障害によって占有される共通空間１０の第３の部分を決定するステップを更に有することができる。ロボット以外の障害によって占有される共通空間の第３の部分を所望に応じて同様なボクセルモデル３００のボクセル３０２によって表すこともできることを理解すべきである。
【００４４】
本開示の方法２００は、第１のプログラム経路に沿った第１のロボット６の動作及び第２のプログラム経路に沿った第２のロボット８の動作の少なくとも一方の後に共通空間１０の非占有部分を決定するステップを更に有することもできる。この場合、共通空間１０の非占有部分を、所望に応じて他のプログラム経路すなわち軌道に従う他のロボットによって使用できるようにする。他の実施の形態において、方法２００は、本開示の方法２００による他の使用のために共通空間１０の第１の部分１２及び第２の部分１４の座標を少なくとも一つのコントローラ１６，１８に移すステップを有することができる。この場合、コントローラ１６，１８は、ここで説明した第１の決定ステップ２０４及び第２の決定ステップ２０６の少なくとも一方を行うとともに座標を第１の部分１２及び第２の部分１４を表すボクセルモデル３００に変換するために用いることができる。
【００４５】
当業者は、共通空間１０の第１の部分１２と第２の部分１４との間に重なりが存在するか否かを決定する際に第１のロボット６の動作と第２のロボット８の動作のそれぞれを優先値によって決定できることを理解すべきである。限定されない例として、第１のロボット６及び第２のロボット８の優先値は、先入れ先出しシステムに基づくことができる。他の例において、第１のロボット６及び第２のロボット８の一方は、常に第１のロボット６及び第２のロボット８の他方よりも高い優先値を有することができる。高い優先値は、ロボットシステム２のロボット６，８の優先度に対する予め決定されたユーザ設定に基づくことができる。他の例において、優先値を、共通空間１０内の非占有部分の利用可能性に基づいて選択することができる。当業者は、所望に応じて第１のロボット６及び第２のロボット８に対して所望の優先値を割り当てることができる。
【００４６】
他の実施の形態において、方法２００は、デッドロック状態となり得る重なり２１０の存在に対する複数のプログラム経路を分析するステップを更に有することができる。次に、デッドロック状態の発生に影響を及ぼすために複数のプログラム経路の動作シーケンスを所望に応じて調整することができる。動作シーケンスを、例えば、所望に応じて優先値に基づいて手動で又は自動的に調整することができる。
【００４７】
当然のことながら、本開示の干渉確認自動区分システム２及び方法２００は、従来のマルチアームロボットシステムよりも優れた利点を提供することができる。システム２及び方法２００は、３次元的なリアルタイムの衝突回避を行う。システム２は、最小のプログラミングしか必要としない。その理由は、システム２が干渉区域の特定又は教示の必要に影響を及ぼすからである。これによって、生産休止時間も減少する。
【００４８】
当業者は、ボクセル化された球５００及び円柱５０２を使用することによって典型的にはロボットモデルの生成に関連した処理要求を最小にすることも理解すべきである。第１のロボット６及び第２のロボット８の動作は、例えば、ボクセルモデル３００のオフライン生成によってシステム２に予め伝達される。同様に、第１のロボット６及び第２のロボット８のプログラム経路すなわち軌道は、衝突なく保持される。工程経路は、切断、溶接、研削、ルーティング(routing)、塗装、分配(dispensing)等のアプリケーション工程(application process)又は他の同様な工程を行う間の一連の動作である。一度工程が開始されると全体の工程経路を中断なく完了することは、一般的には重要である。当然のことながら、第１のロボット６及び第２のロボット８の重要な工程経路も本方法２００によって同様に保護される。
【００４９】
システム２は、所望に応じて同一のコントローラ１６，１８内及び複数のコントローラ１６，１８間の複数のロボットアームの衝突の回避をサポートする。さらに、システム２及び方法２００は、簡単なロボット形態を提供し、所定の従来のシステム及び方法で行われるようなＩ／Ｏハンドシェイクプロトコルの必要に影響を及ぼす。干渉確認自動区分システム２及び方法２００は、複数のアーム干渉確認の形態を簡単化し、複数のロボットアームのデッドロックに影響を及ぼす。
【００５０】
干渉防止及びデッドロック防止は密接な関係がある。干渉は、二つのロボットが同一の物理的な空間を占有することを試みるときに生じる。干渉を防止する一つの方法は、現在の動作コマンドにおいて全てのロボットによって占有されている又は将来占有される空間の確認及び干渉が生じる前の一つ以上のロボットの停止を伴う。このタイプの干渉防止は、停止しているロボットの一つ以上が他のロボットによって必要である又は将来必要とされる空間を現在占有しているとともに他のロボットにより妨害され続けているために停止しているロボットが始動できないときにデッドロックが生じる傾向が非常に高いという重大な不都合を有する。
【００５１】
干渉を防止する他の方法は、ロボットプログラムに開始区分コマンド及び終了区分コマンド(enter and exit zone commands)をプログラム的に(programmatically)挿入することによって設定することである。これらのコマンドは、一つのロボットだけが一度に特定区分を占有できるようにすることを容易にするためにＰＬＣ又は他のロボットとやり取りを行う。単一の区分に対して、ほとんど影響がない。主要な問題は、利用可能となっているときに複数のロボットが待機中である場合に誰が区分を取得するかという優先度の一つである。しかしながら、複数の区分に対して、デッドロックが非常に生じやすくなっている。例えば、隣接する区分に対して、各ロボットが現在一つの区分を占有するとともに次の動作が他のロボットに占有されている区分内で行われるか否かを知ることは容易である。この場合、各ロボットは、他のロボットが所望の区分をあきらめるのを永久に待つ。デッドロック状態が生じる。
【００５２】
本発明によるシステム及び方法は、起こりうるデッドロック状態を有する動作を実行する前にデッドロックフリー動作ステートメントを決定することによって上述した場合におけるデッドロック状態を除外する。デッドロックフリー動作ステートメントの決定を、オフラインで、通常の実行とは別に又は通常の製造の実行中に行うことができる。十分なＣＰＵ処理時間を利用できる場合、通常の製造の実行中の決定は、Ｉ／Ｏタイミングの変化又は外部イベント若しくはシーケンスのタイミングの変化のような動的な条件に応答するのに最大の適応性を与える。最小のＣＰＵの影響に対して、決定はオフラインで行われ、この場合、プログラムシーケンス(programming sequence)の多数の順列(permutation)を分析することができ、最適化された実行のシーケンスを見つけることができる。
【００５３】
本発明によるシステム及び方法は、既知のデッドロックフリーシーケンス(deadlock-free sequence)を必要としない。システム及び方法は、起こりうるデッドロック状態を自動的に決定し、起こりうるデッドロック状態を回避する方法を特定することができる。システム及び方法は、デッドロックを回避するために優先値を必要としない。システム及び方法は、干渉状態を防止し、同時に、デッドロック状態の可能性が存在しないようにする。
【００５４】
第１のロボットによって実行される「元のプログラムＡ」のリスト４０１の行番号及び第２のロボットによって実行される「元のプログラムＢ」のリスト４０３の行番号の「デッドロックフリー行列」４００を、図７に示す。行列４００の網掛けセルは、デッドロックフリー領域を規定する上方向の凸包(ascending convex hull)を表す。網掛けセルの大部分は、一方のプログラムの行ｉ−１から行ｉまでの経路及び他方のプログラムの行ｊ−１から行ｊまでの経路の進行中に干渉を有するプログラム行の対を表す。残りのセルは、上方向の凸包を完成することが要求される。行列４００のセルを、（ｉ，ｊ）の形式で指定することができ、この場合、ｉは、プログラムＡの行番号であり、ｊは、プログラムＢの行番号である。したがって、干渉セルは、（３，６；３，７；４，５；４，６；４，７；５，４；５，５；５，６；５，７）であり、残りのセルは、（３，４；３，５；４，４）である。
【００５５】
例えば、プログラムＡが行３にあり、プログラムＢが行５にある場合、デッドロック状態が存在する。その理由は、Ａが行４に移動することを試みる場合、行５でＢとの干渉があり、Ｂが行６に移動することを試みる場合、行３でＡとの干渉があるからである。したがって、いずれのロボットも進行することができない。Ａの行３から行５まで及びＢの行４から行７までのデッドロック区分を完成することによって、一方のプログラムＡ又はＢのみが一度にこの区分を占有することができる。これは、「新たなプログラムＡ」のリスト４０２及び「新たなプログラムＢ」のリスト４０４に示すようなプログラムの例においてＺＯＮＥ［１］として識別される。
【００５６】
図８は、「干渉行列」４０５を三つのデッドロックフリー区分：ＺＯＮＥ［１］，ＺＯＮＥ［２］，ＺＯＮＥ［３］に細分することができる例を示す。干渉セルは、（３，３；３，４；３，５；３，６；３，７；４，５；４，６；４，７；５，４；５，５；５，６；５，７：６，６；６，７）である。ＺＯＮＥ［１］は、セル（３，３；３，４；３，５；３，６；３，７）を有する。ＺＯＮＥ［２］は、セル（４，５；４，６；４，７；５，４；５，５；５，６；５，７）を有する。ＺＯＮＥ［３］は、（６，６；６，７）を有する。上方向の凸包は、三つの凸包を形成できるようにするとともに全領域が上に凸となるように、仮想的な干渉であるセル（４，４）を通じて形成される。三つの区分は、「新たなプログラムＡ」リスト４０６及び「新たなプログラムＢ」リスト４０７に組み込まれる。任意の干渉のない行の対の組合せにおいて少なくとも一つのプログラムが干渉なく次の行に進むことができる場合はない。
【００５７】
図９は、デッドロックが存在しうる複数の干渉領域及び二つのデッドロック領域を有するプログラムの対の例を示す。「プログラムＡ」は、行３から行１５までの経路４０９を進む。「プログラムＢ」は、行９から行２１までの経路４１０を進む。プログラムは、経路及び表４１３に示すような第１のデッドロック領域４１２及び第２のデッドロック領域４１１を有する。単一のデッドロック領域を形成する簡単な方法は、全ての干渉領域及び介在する非干渉領域を組み合わせて表４１４に示すような単一の領域にすることであり、この領域は、もともとデッドロックがない。
【００５８】
図１０は、「プログラムＡ」及び「プログラムＢ」をそれぞれ実行するロボット６，８の五つのシーケンスを示す。最も左にある第１のシーケンスにおいて、ロボット６は、ロボット８が動作することなく「プログラムＡ」を実行する。右側の次のシーケンスにおいて、ロボット８は、ロボット６が動作することなく「プログラムＢ」を実行する。真ん中のシーケンスにおいて、ロボット６，８は、各プログラムを同時に実行し、衝突が生じる。右側の次のシーケンスは、デッドロックが生じる従来の干渉回避を行いながら各プログラムを同時に実行するロボット６，８を示す。最も右側のシーケンスは、本発明によるデッドロック防止を行いながら各プログラムを同時に実行するロボット６，８を示し、両プログラムは、干渉なく完了する。
【００５９】
上述したシステム及び方法は、衝突の防止とあり得るデッドロックの処理の両方を行うためにプログラムステートメントを自動的に追加及び／又は修正する。一部のケースにおいて、発される自動待機コマンドによって、全体のサイクル時間を所定のジョブのために増大させる。サイクル時間の増大が許容されない場合、本発明によるシステム及び方法は、ロボットが停止することなくプログラムを実行することができる再設定経路(re-sequenced path)を推奨又は自動的に形成する。すなわち、二つのロボットが一度に同一空間を占有する予定である経路の部分が存在する場合、システム及び方法は、この状態を除去するために新たな経路シーケンス（溶接を想定した場合には、異なる順序のスポット）を自動的に推奨する。このようにプログラム命令を再設定する特徴は、塗装屋の塗布に用いることができる。
【００６０】
条件実行ステートメントがプログラム中に生じる場合、分析は、シーケンシャル実行の全ての組合せを含むことができる。又は、簡単のために、条件分岐領域に含まれるプログラムセグメントを、独立したものとして扱うことができる。典型的には、ロボットプログラマは、そのような条件領域を教示し、領域に対する入力経路及び領域に対する出力経路が他のロボットとの干渉を有さなくするとともに独立した扱いを実用的にできるようにする。しかしながら、条件領域に対する入力経路及び条件領域に対する出力経路が他のロボットとの干渉を有する場合、干渉のないこと及びデッドロックのないことを保証するために条件領域及び非条件領域の複数の組合せを分析する。
【００６１】
この方法の利点の一つは、デッドロック状態を除去することができる機構と同一の機構が通常のプログラム動作中に干渉も除去できることである。したがって、ロボット間の干渉のリアルタイムの確認を、通常プログラム動作中に除去することができる。これは、処理時間を更に高い補間速度すなわち更に短い補間時間のような他の目的のために用いることができる著しいＣＰＵ利用を確保することができる。エラー状態中すなわちプログラムが実行されないとき、「３次元自動区分によるマルチアームロボットシステム干渉確認」(Multi-Arm Robot System Interference Check Via Three Dimensional Automatic Zones)の表題の同時係属中の米国特許出願第１２／１２４，４３０号で提案されているようなＣＰＵの使用が少ない干渉確認を、干渉を防止するために用いることができる。
【００６２】
プログラムによって占有される空間を、物理的な空間、時間、プログラムシーケンス、行番号、プルグラム若しくは行の完了の割合又はロボット、プログラム若しくはシステムに関連した状態変化の関数とすることができる。干渉領域及びデッドロック領域は、占有空間を規定する関数と同一の関数によって関連付けられる。
【００６３】
デッドロックを回避する方法をさまざまな形で実行することができる。最も簡単な方法は、図９に示すようにデッドロック及び干渉を防止するよう干渉領域を展開する(expand)ことである。全プログラムに対して一つの干渉領域のみが存在するように干渉領域を展開することは、システムがデッドロックフリーになることを保証するが、サイクル時間が重要である場合、シーケンス制御の一部のソート及び／又は複数の干渉領域を用いることができる。他の方法は、デッドロックを防止するために干渉領域外に実行シーケンスを設けることである。これを、第１のロボットが進行する前にデッドロック状態が存在しうるプログラム実行の一部を完了するために第１のロボットが第２のロボットを待機することによって簡単に行うことができる。
【００６４】
占有空間を決定することができる複数の方法がある。最も簡単な方法は、占有面積を純粋にプログラム実行中にロボットによって占有される累積空間(cumulative space)とすることである。複数のロボットがこのように決定された占有空間を有するとき、干渉領域は、各ロボットの累積占有空間の交差である単なる空間となる。一つのロボットのみが一度にこの空間に入ることを許容することによって、干渉とデッドロックの両方を防止する。
【００６５】
他の方法は、占有空間を時間の関数として決定することである。各時点において、各ロボットによって占有される空間が存在する。占有空間を特定の期間にわたる時間の積分として表すことによって、占有空間を、時間に関連した一連の離散空間として表すことができる。干渉領域は、同一時間又は時間間隔におけるロボットの交差となる。干渉を、一度に一つのロボットだけが干渉領域に存在できるようにすることによって回避することができる。相対的時間(relative time)がシーケンス制御により変化するので、時間基準を、シーケンス制御が行われた後に新たな時間に関連するように調整する必要がある。
【００６６】
上述した時間に基づく方法に対して、時間を時間間隔数(time interval number)として表すことができる。この方法では、全経過時間は重要でなくなり、干渉領域を時間間隔数の行列として表すことができる。特定の時間間隔状態で干渉が存在する場合、当該時間間隔状態の発生を許容しないようにする必要がある。その理由は、当該時間間隔状態で衝突が生じうるからである。
【００６７】
同様に、プログラムシーケンスを、行番号、完了の割合、プログラム状態等によって表すことができる。そのような任意のシーケンシャル表示に対して、選択されたパラメータの関数として規定された干渉を表示することができる。干渉を回避する目的は、干渉が存在する関数の集合の状態を回避することである。シーケンシャル離散間隔すなわちシーケンシャル状態として表すことができる関数に対して、これを、図８に示すような干渉行列として表すことができる。干渉行列は干渉領域を有する。当然、行列は、データを表す一つの方法にすぎないが、行列を、更に視覚的な表現にすることができる。一般的に、行列はスパースであり、任意のスパース行列技術を表示に適用することができる。
【００６８】
Ｉ／Ｏ状態若しくは工程又は他の状態のような状態規定を、領域を規定するために用いることができる。状態がシーケンシャルな意味を有し又はロボット位置及び占有空間に関連したシーケンシャル動作を表すために規定できる限り、状態を干渉領域及びデッドロック領域のパラメータ表示に用いることができる。
【００６９】
一度干渉行列が決定されると、デッドロックを防止する一つの方法は、干渉が順方向シーケンシング(forward sequencing)を妨害するシーケンス番号の単調増加の任意の「トラップ」を回避することである。干渉行列を上に凸(ascendingly convex)にすることによって、デッドロックと干渉の両方を回避することができる。このように上に凸である干渉行列を、デッドロック行列と称することができる。デッドロック行列は、図７に示すようなデッドロック領域を有する。干渉と同様に、デッドロック行列は、データを表す一つの方法にすぎない。
【００７０】
一度デッドロック行列を決定するとデッドロック及び干渉を回避する多数の手段がある。最も簡単な手段は、デッドロック行列のデッドロック領域を回避するよう実行タイミングを調整するためにプログラムに命令を挿入することである。プログラムに命令を追加することは、実行タイミングの正確な性質を単なるプログラム観察だけによって決定できることである。他の手段は、実際のプログラム変更とは別にタイミングを決定することができる。
【００７１】
干渉領域及びデッドロック領域のパラメータ規定は、干渉及びデッドロックを回避するための一般的な方法を提供する。このような領域の表示によって、種々の係数(factor)による種々のプログラム制御を可能にする。
【００７２】
また、ＣＰＵの利用を減らすために、実際のプログラムを、デッドロック状態を回避するために必要な全ての情報がプログラムに含まれるように区分及びシーケンシャル情報を含むために更新することができる。これによって、プログラムシーケンス、干渉及びあり得るデッドロック状態をリアルタイムで確認する必要がなくなる。
【００７３】
図１１は、本発明のシステム及び方法によるデッドロック回避シーケンスの流れ図である。ステップ４２０において、プログラムをロボットコントローラ１６，１８に教示する。ステップ４２１において、占有空間を決定する。その後、ステップ４２２において、干渉領域を決定する。ステップ４２３において、あり得るデッドロック領域を決定する。ステップ４２４において、デッドロックを回避するためのプログラム実行要求を決定する。最後に、上述したように、デッドロックを回避するための機構をステップ４２５で決定する。
【００７４】
ステップ４２３を、図１２において更に詳細に示す。ステップ４２６において、占有空間及び全ての干渉領域を識別する。ステップ４２７において、各干渉領域の組合せを調べる。「デッドロック状態が存在するか」についての確認を、決定ステップ４２８で行う。結果がＮＯである場合、ステップ４２９において、ステップ４２３を終了する。結果がＹＥＳである場合、ステップ４３０は、デッドロックの発生を防止する手段を提供し、ステップ４２７に戻る。
【００７５】
発明を説明するために所定の代表的な実施の形態及び説明を示したが、当業者は、以下で添付した請求の範囲で更に説明した開示の範囲から逸脱することなく種々の変更を行うことができることを理解する。
【図１】
0005981215.tif 000002
【図２】
0005981215.tif 000003
【図３】
0005981215.tif 000004
【図４】
0005981215.tif 000005
【図５】
0005981215.tif 000006
【図６】
0005981215.tif 000007
【図７Ａ】
0005981215.tif 000008
【図７Ｂ】
0005981215.tif 000009
【図７Ｃ】
0005981215.tif 000010
【図８Ａ】
0005981215.tif 000011
【図８Ｂ】
0005981215.tif 000012
【図８Ｃ】
0005981215.tif 000013
【図８Ｄ】
0005981215.tif 000014
【図９】
0005981215.tif 000015
【図１０】
0005981215.tif 000016
【図１１】
0005981215.tif 000017
【図１２】
0005981215.tif 000018