JP6895082B2 - 干渉判定方法、干渉判定システム及びコンピュータプログラム - Google Patents

Description

本発明は、干渉判定方法、干渉判定システム及びコンピュータプログラムに関する。

産業用ロボットに所定の作業を行わせる際、作業を実行するロボットアームの動作経路を、プログラミングや、実機を実際に動作させる教示により決定する場合、多くの時間と労力を要する。

これに対し、動作開始点（始点）及び動作終了点（終点）を入力すると、始点と終点間の経路を自動的に生成するアルゴリズムを用いることができれば、産業用ロボットを教示する時間を大幅に短縮することが期待できる。

産業用ロボットのロボットアームの動作を制御する際に周辺物との干渉の有無をチェックする方法として、特許文献１がある。この文献には、始点と終点との間を結ぶロボットの経路について、ロボットがその経路を通過する離散時間毎に区分して、ロボットの占有領域を計算し、隣り合う離散時間同士の占有領域を組み合わせて複数の凸包を計算し、これら凸包と、周辺の障害物を多面体で近似した凸多面体とが共有領域を有するか否かを計算し、共有領域がある場合は干渉が生じている、とする干渉予測方法が開示されている。

このようなアルゴリズムを用いて経路を生成する際に、産業用ロボットが配置される周辺環境、たとえば、ベルトコンベア等の障害物を考慮した経路生成が可能になれば、より実際の環境に適合した経路が生成されることとなり好ましい。

特開２０１２−２２３８４５号公報

そして、このような経路の自動生成に求められる性能の１つとして、経路演算処理の高速化がある。たとえば、ベルトコンベア上を不規則に流れてくる複数の把持対象物をロボットアームでそれぞれ把持しなければならない場合は、把持対象物ごとに経路を演算しなければならないため、演算処理の高速化を図る必要がある。演算時間の長短は、ベルトコンベアの可動速度、ひいては、生産効率に直結するからである。

特許文献１に記載の干渉判定方法では、隣接する離散時間におけるロボットの占有領域を組み合わせた凸包の全てと、ロボット周辺の障害物を近似した凸多面体について共有領域の有無を判定しているため、干渉有無の判定時間が長いという課題があった。

そこで本発明は、動作経路に従って動作するロボットと周辺物との干渉の有無を高速に演算することを可能とする干渉判定方法、干渉判定システム及びコンピュータプログラムを提供することを目的とする。

本開示の一側面に係る干渉判定方法は、取得部、記憶部及び演算部を備える演算装置を用いて、複数の可動軸を有するロボットが初期姿勢から目標姿勢に移動する動作経路上でロボットの周辺に存在する周辺物と干渉する可能性を判定する方法である。そして、演算部は、記憶部にロボットの形状を所定の着目部位について多面体で近似したロボットデータを記憶させるステップと、記憶部に周辺物の形状を近似した周辺物近似体のデータを記憶させるステップと、取得部を用いて初期姿勢及び目標姿勢を取得するステップと、初期姿勢から目標姿勢へと移動する動作経路上におけるロボットの第１の姿勢と、第１の姿勢よりも、相対的に目標姿勢側の動作経路上におけるロボットの第２の姿勢と、第１の姿勢と第２の姿勢との間の中間姿勢と、を設定するステップと、ロボットデータに基づいて、第１の姿勢、第２の姿勢及び中間姿勢におけるロボットの形状を、少なくとも一つの着目部位について多面体で近似した複数のロボット近似体を生成するステップと、このステップで生成されたロボット近似体を組み合わせて構成される第１の組み合わせ近似体を生成するステップと、第１の組み合わせ近似体と、周辺物近似体とが干渉するか判定するステップと、このステップにおいて干渉すると判定された場合は、第１の組み合わせ近似体を構成する複数のロボット近似体のうち、隣接する二つのロボット近似体の間隔を示す量を算出し、所定値と比較するステップと、間隔を示す量と所定値との比較結果に基づいて、第１の組み合わせ近似体よりも小さい組み合わせ近似体を生成するか否かを判断するステップと、を実行する。

この態様によれば、第１の組み合わせ近似体を構成する隣接する二つのロボット近似体の間隔を示す量を算出し、所定値と比較するから、十分に間隔が狭い場合の干渉判定か、そうでない場合か判断することが可能になり、比較結果に応じて後の処理を変更することが可能になる。すなわち、隣接する二つのロボット近似体の間の間隔が相対的に広い場合には、ロボット近似体の間に障害物が存在する可能性があるため、間隔が所定値以上であるか、所定値未満であるか否かに応じて後の処理を変更することで、必要のない干渉判定の処理を省略して高速性を保ちつつ、精度の高い干渉判定が可能になる。

また、演算部は、間隔を示す量が所定値以上と判断された場合は、着目部位について、第１の姿勢、第２の姿勢及び中間姿勢に相当する複数の前記ロボット近似体の少なくとも二つを組み合わせて構成され、第１の組み合わせ近似体よりも小さい第２の組み合わせ近似体を生成するステップと、第２の組み合わせ近似体と、周辺物近似体とが干渉するか判定するステップと、を更に実行することができる。

この態様によれば、第１の組み合わせ近似体よりも小さい第２の組み合わせ近似体を生成し、第２の組み合わせ近似体と、周辺物近似体とが干渉するか判定し、干渉しないと判定された場合はその領域内の干渉判定処理を省略することが可能になるため、干渉判定処理を高速に実現することが可能になる。

また、演算部は、第２の組み合わせ近似体と、周辺物近似体とが干渉するか判定するステップにおいて干渉すると判定され、かつ、第２の組み合わせ近似体を構成する複数の前記ロボット近似体のうち、隣接する二つのロボット近似体の間隔を示す量が所定値以上の場合に、第１の姿勢、第２の姿勢及び中間姿勢に相当する複数のロボット近似体の少なくとも二つを組み合わせて構成され、第（ｎ−１）の組み合わせ近似体よりも小さい第ｎの組み合わせ近似体を生成するステップと（ただし、ｎは３以上の整数）、第ｎの組み合わせ近似体と、周辺物近似体が干渉するか判定するステップを、更に実行してもよい。

この態様によれば、隣接する二つのロボット近似体の間隔を示す量が所定値以上の場合に、第ｎの組み合わせ近似体よりも小さい第（ｎ＋１）の組み合わせ近似体を生成するので、間隔が十分に狭くない場合には、更に小さい第（ｎ＋１）の組み合わせ近似体を用いてより詳細な干渉判定が可能になる一方で、間隔が十分に狭い場合には、以降の干渉判定処理を省略することも可能になるので、高速な干渉判定処理を実現することが可能になる。

また、演算部は、第ｎの組み合わせ近似体を構成する複数のロボット近似体のうち、隣接する二つのロボット近似体の間隔を示す量が、所定値未満となるまで、ｎを１ずつ増加させながら、第ｎの組み合わせ近似体を生成するステップと、第ｎの組み合わせ近似体と周辺物近似体とが干渉するか判定するステップを、繰り返してもよい。

この態様によれば、間隔を示す量が所定値未満となるまで、ｎを１ずつ増加させながら、第ｎの組み合わせ近似体を生成するステップと、第ｎの組み合わせ近似体と周辺物近似体とが干渉するか判定するステップを、繰り返すので、必要に応じて詳細な干渉判定をするとともに、不要な干渉判定処理を省略することが可能になる。

また、演算部は、第ｎの組み合わせ近似体を構成する隣接する二つのロボット近似体の間隔を示す量が、所定値未満の場合は、第ｎの組み合わせ近似体を構成する隣接する二つのロボット近似体間の動作経路上で干渉する可能性があると出力することができる。

この態様によれば、間隔が十分に狭く、かつ、干渉可能性がある場合は、同様の干渉判定処理を終了することが可能になる。したがって、必要のない干渉判定の処理を省略して高速性を保ちつつ、干渉判定の精度を向上させることができる。

また、第ｎの組み合わせ近似体を生成するステップは、第（ｎ−１）の組み合わせ近似体を構成する複数の前記ロボット近似体のうち、隣接する二つのロボット近似体間の動作経路上の中間姿勢と、隣接する二つのロボット近似体を組み合わせて第ｎの組み合わせ近似体を生成するステップと、を含むことができる。

この態様によれば、隣接する二つのロボット近似体間の動作経路上の中間姿勢と、隣接する二つのロボット近似体を組み合わせて第ｎの組み合わせ近似体を生成するから、隣接する二つのロボット近似体の動作経路上の中間姿勢を用いた詳細な干渉判定が可能になる。

また、第ｋの組み合わせ近似体（ｋは１以上の整数）と、周辺物近似体とが干渉するか判定するステップは、周辺物近似体と、第ｋの組み合わせ近似体の距離を算出するステップと、距離と第２の所定値とを比較するステップと、を含むことができる。

この態様によれば、周辺物近似体と、第ｋの組み合わせ近似体の距離に基づいて干渉可能性を判断することができるので、駆動軸の回転運動のために、第ｋの組み合わせ近似体からはみ出る中間姿勢を取る場合であっても、そのような中間姿勢を加味した干渉判定が可能になる。

また、本開示の他の側面に係る干渉判定方法は、演算部を備える演算装置を用いて、複数の可動軸を有するロボットが初期姿勢から目標姿勢に移動する動作経路上で、ロボットの周辺に存在する周辺物と干渉する可能性を判定する。そして、演算部は、初期姿勢から目標姿勢へと移動する動作経路上におけるロボットの第１の姿勢を特定するための複数の可動軸の回転角度を設定するステップと、第１の姿勢よりも目標姿勢側の動作経路上におけるロボットの第２の姿勢を特定するための複数の可動軸の回転角度であって、第１の姿勢から第２の姿勢に変化する間の回転角度は、可動軸ごとに、単調増加又は単調減少する回転角度を、設定するステップと、第１の姿勢と第２の姿勢との間の少なくとも一つの中間姿勢を特定するために複数の可動軸の回転角度を示す情報を設定するステップと、ロボットの少なくとも一つの着目部位を多面体で近似したロボット近似体であって、第１の姿勢、第２の姿勢及び中間姿勢のそれぞれに対応した複数のロボット近似体を生成するステップと、このステップで生成された複数のロボット近似体を組み合わせて構成される第１の組み合わせ近似体が、周辺物と干渉するか判断するステップと、このステップで干渉すると判断された場合は、複数のロボット近似体を組み合わせて構成され、第１の組み合わせ近似体よりも小さい第２の組み合わせ近似体を生成するステップと、第２の組み合わせ近似体と、周辺物近似体とが干渉するか判定するステップと、を実行する。

この態様によれば、第１の姿勢から第２の姿勢にわたり、可動軸の回転角度は、単調増加又は単調減少に変化するから、所定の可動軸の回転角度が増加及び減少の双方を伴うことがなくなり、より正確な干渉判定が可能になる。また、第１の組み合わせ近似体が、周辺物と干渉すると判断された場合は、第１の組み合わせ近似体よりも小さい第２の組み合わせ近似体を生成して干渉判定するから、必要が無い場合は、第２の組み合わせ近似体を生成することなく、高速な干渉判定を実現することができる。

また、本開示の他の側面に係る干渉判定方法は、演算部を備える演算装置を用いて、複数の可動軸を有するロボットが第１の姿勢から第２の姿勢に移動する動作経路上で、ロボットの周辺に存在する周辺物と干渉する可能性を判定する。

そして、動作経路上におけるロボットの第１の姿勢を取得するステップと、動作経路上におけるロボットの第２の姿勢を取得するステップと、第１の姿勢から第２の姿勢に至る動作経路について、ロボットの所定部位が周辺物と干渉するか第１の分解能で判断するステップと、このステップの結果に基づいて選択される動作経路の一部である第２の動作経路のみについて、ロボットの所定部位が周辺物と干渉するか第１の分解能より高い第２の分解能で判断するステップと、このステップの結果に基づいて選択される第２の動作経路の一部である第３の動作経路のみについて、ロボットの所定部位が周辺物と干渉するか第２の分解能より高い第３の分解能で判断するステップと、を実行する。

この態様によれば、第１の姿勢から第２の姿勢に至る動作経路について、ロボットの所定部位が周辺物と干渉するか第１の分解能で判断し、その結果に基づいて選択される第２の動作経路のみについて、ロボットの所定部位が周辺物と干渉するか第２の分解能で判断し、更に、その結果に基づいて選択される第３の動作経路のみについて、ロボットの所定部位が周辺物と干渉するか第３の分解能で判断するから、少なくとも３つの分解能で干渉判定する際に、低い分解能で干渉判定された結果に基づいて動的に選択される動作経路の一部について高分解能で干渉判定をすることが可能となり、高速な干渉判定処理を実現することが可能になる。

また、本開示の他の側面に係る干渉判定システムは、取得部、記憶部及び演算部を備える演算装置を用いて、複数の可動軸を有するロボットが初期姿勢から目標姿勢に移動する動作経路上で、ロボットの周辺に存在する周辺物と干渉する可能性を判定する。そして、演算部は、記憶部に、ロボットの形状を、所定の着目部位について多面体で近似したロボットデータを記憶させるステップと、記憶部に、周辺物の形状を近似した周辺物近似体のデータを記憶させるステップと、取得部を用いて、初期姿勢及び目標姿勢を取得するステップと、初期姿勢から目標姿勢へと移動する動作経路上におけるロボットの第１の姿勢と、第１の姿勢よりも、相対的に目標姿勢側の動作経路上におけるロボットの第２の姿勢と、第１の姿勢と第２の姿勢との間の中間姿勢と、を設定するステップと、ロボットデータに基づいて、第１の姿勢、第２の姿勢及び中間姿勢におけるロボットの形状を、少なくとも一つの着目部位について多面体で近似した複数のロボット近似体を生成するステップと、このステップで生成された複数のロボット近似体を組み合わせて構成される第１の組み合わせ近似体を生成するステップと、第１の組み合わせ近似体と、周辺物近似体とが干渉するか判定するステップと、このステップにおいて干渉すると判定された場合は、第１の組み合わせ近似体を構成する複数のロボット近似体のうち、隣接する二つのロボット近似体の間隔を示す量を算出し、所定値と比較するステップと、間隔を示す量と所定値との比較結果に基づいて、第１の組み合わせ近似体よりも小さい組み合わせ近似体を生成するか否かを判断するステップを実行する。

この態様によれば、第１の組み合わせ近似体を構成する隣接する二つのロボット近似体の間隔を示す量を算出し、所定値と比較するから、十分に間隔が狭い場合の干渉判定か、そうでない場合か判断することが可能になり、比較結果に応じて後の処理を変更することが可能になる。すなわち、隣接する二つのロボット近似体の間の間隔が相対的に広い場合には、ロボット近似体の間に障害物が存在する可能性があるため、間隔が所定値以上であるか、所定値未満であるか否かに応じて後の処理を変更することで、必要のない干渉判定の処理を省略して高速性を保ちつつ、精度の高い干渉判定が可能になる。

また、本開示の他の側面に係るプログラムは、取得部、記憶部及び演算部を備える演算装置を用いて、複数の可動軸を有するロボットが初期姿勢から目標姿勢に移動する動作経路上で、ロボットの周辺に存在する周辺物と干渉する可能性を判定する干渉判定を演算装置に実行させる。そして、演算部に、記憶部に、ロボットの形状を、所定の着目部位について、多面体で近似したロボットデータを記憶させるステップと、記憶部に、周辺物の形状を近似した周辺物近似体のデータを記憶させるステップと、取得部を用いて、初期姿勢及び目標姿勢を取得するステップと、初期姿勢から目標姿勢へと移動する動作経路上におけるロボットの第１の姿勢と、第１の姿勢よりも、相対的に目標姿勢側の動作経路上におけるロボットの第２の姿勢と、第１の姿勢と第２の姿勢との間の中間姿勢と、を設定するステップと、ロボットデータに基づいて、第１の姿勢、第２の姿勢及び中間姿勢におけるロボットの形状を、少なくとも一つの着目部位について多面体で近似した複数のロボット近似体を生成するステップと、このステップで生成された複数のロボット近似体を組み合わせて構成される第１の組み合わせ近似体を生成するステップと、第１の組み合わせ近似体と、周辺物近似体とが干渉するか判定するステップと、このステップにおいて干渉すると判定された場合は、第１の組み合わせ近似体を構成する複数のロボット近似体のうち、隣接する二つのロボット近似体の間隔を示す量を算出し、所定値と比較するステップと、間隔を示す量と所定値との比較結果に基づいて、第１の組み合わせ近似体よりも小さい組み合わせ近似体を生成するか否かを判断するステップを実行させる。

この態様によれば、第１の組み合わせ近似体を構成する隣接する二つのロボット近似体の間隔を示す量を算出し、所定値と比較するから、十分に間隔が狭い場合の干渉判定か、そうでない場合か判断することが可能になり、比較結果に応じて後の処理を変更することが可能になる。すなわち、隣接する二つのロボット近似体の間の間隔が相対的に広い場合には、ロボット近似体の間に障害物が存在する可能性があるため、間隔が所定値以上であるか、所定値未満であるか否かに応じて後の処理を変更することで、必要のない干渉判定の処理を省略して高速性を保ちつつ、精度の高い干渉判定が可能になる。

なお、「初期姿勢」とは、ロボットの動作開始時における姿勢を含み、たとえば、ロボットの動作経路を演算するときの始点においてロボットがとっている姿勢を含む。

また、「目標姿勢」とは、ロボットの動作終了時における姿勢を含み、たとえば、ロボットの動作経路を演算するときの終点においてロボットがとっている姿勢を含む。

また、「着目部位」とは、メッシュなどにより表現されたロボットの形状のモデルデータの一部または全部であって、ＯＢＢ（Oriented Bounding Box）等の近似手法によって近似される形状を含む。たとえば、産業用ロボットの各リンク、または、リンクの一部を着目部位として取り扱う場合がある。

また、「ロボットデータ」とは、メッシュなどにより表現されたロボットの形状のモデルデータを所定の近似手法により近似したロボットの形状を示すデータを含む。

また、「周辺物近似体」とは、障害物などの周辺物をメッシュや、ＡＡＢＢ（Axis-Aligned Bounding Box）等の近似手法により近似した形状モデルを含む。

また、「第１の姿勢」とは、初期姿勢と目標姿勢とを結ぶ動作経路上の姿勢であって、ロボット近似体を生成する対象となる姿勢を含む。初期姿勢と同一姿勢であってもよい。

また、「第２の姿勢」とは、初期姿勢と目標姿勢とを結ぶ動作経路上の姿勢であって、ロボット近似体を生成する対象となる姿勢を含む。目標姿勢と同一姿勢であってもよい。

また、「中間姿勢」とは、第１の姿勢と第２の姿勢との間の動作経路上の姿勢であって、ロボット近似体を生成する対象となる姿勢を含む。中間姿勢は、第１の姿勢と第２の姿勢との間の動作経路上の中間地点における姿勢に限られない。

また、「ロボット近似体」とは、ロボットデータに基づいて算出される、第１の姿勢、第２の姿勢、中間姿勢のそれぞれに対応したロボットの姿勢（各軸の関節が所定値に定まったロボットの体勢）をＯＢＢ等の近似手法によって近似した近似体を含む。

また、「組み合わせ近似体」とは、少なくとも二つのロボット近似体を組み合わせた近似体を含む。少なくとも二つのロボット近似体の大半または全てを包含するようにＡＡＢＢ等の近似手法によって近似した近似体を含む。

本発明によれば、動作経路に従って動作するロボットと周辺物との干渉の有無を高速に演算することを可能とする干渉判定方法、干渉判定システム及びコンピュータプログラムを提供することができる。

第１実施形態及び第２実施形態に係る干渉判定システム１０のハードウェアブロック図 ロボットアーム１６とそのロボットデータ 第２実施形態に係る干渉判定方法の事前処理のフローチャート コンフィギュレーション空間の概念図 第２実施形態に係る干渉判定方法のフローチャート チェックデータリストＤＬの変化を示す概念図 ロボットアーム１６が姿勢を変化させる様子の模式図 link_a、link_b及びlink_cのロボット近似体データ 第１の組み合わせ近似体と周辺物近似体 高分解能な干渉判定の必要性を判断するための条件を示す模式図 第２の組み合わせ近似体と周辺物近似体 異なる第２の組み合わせ近似体と周辺物近似体 第３の組み合わせ近似体と周辺物近似体 第４の組み合わせ近似体と周辺物近似体 第５の組み合わせ近似体と周辺物近似体 異なる第５の組み合わせ近似体と周辺物近似体 第６の組み合わせ近似体と周辺物近似体 異なる第６の組み合わせ近似体と周辺物近似体 最終的に生成された組み合わせ近似体 第３実施形態に係る干渉判定方法のフローチャート

[第１実施形態]
まず、図１を用いて、本発明が適用される実施形態の一例について説明する。

図１は、本発明の第１実施形態に係る干渉判定システム１０（「干渉判定システム」の一例）のハードウェアブロック図である。この図に示されるように、この干渉判定システム１０は、情報を入力するための入力部１２と、情報を処理するための演算装置１４（「演算装置」の一例）と、演算結果に基づいて制御されるロボットアーム１６（「ロボット」の一例）ならびに結果を表示するためのモニタ１８を備える出力部２０を有する。

入力部１２は、演算装置１４に情報を入力するためのインタフェースとして機能し、入力データであるロボットアーム１６の初期姿勢、目標姿勢、障害物情報及びロボットアーム１６に関するロボット情報等を入力するための手段を備える。

演算装置１４は、典型的には計算機２２を用いて実現することが可能であり、入力部１２等から入力される情報を取得するためのインタフェース２８（「取得部」の一例）と、各実施形態に示される種々の演算処理を実施するためのＣＰＵ２４（「演算部」の一例）と、各実施形態に示される干渉判定等の各処理を規定するプログラム等を不揮発的に記憶する記憶装置２６（「記憶部」の一例）を備える。

本実施形態に係る干渉判定システム１０を用いて、ロボットアーム１６が障害物などの周辺物と干渉する可能性を判定するための干渉判定方法は、以下のようなステップにより実現される。

まず、インタフェース２８は、入力部１２から入力される初期姿勢及び目標姿勢を取得する。具体的には、ロボットアーム１６の姿勢を特定する各駆動軸の回転角度を取得する。なお、初期姿勢及び目標姿勢は、ロボットアーム１６の先端の位置の情報を含む初期位置及び目標位置として与えられてもよい。このとき、各駆動軸の回転角度は、演算装置１４のＣＰＵ２４（演算部）を含む所定の演算装置が、先端の位置に基づいてインバースキネマティクス（逆運動学）計算を実行することにより算出される。なお、初期姿勢は、例えば、ロボットアーム１６の各駆動軸の現在の回転角度でもよい。また、目標姿勢または目標位置は、例えば、ロボットアーム１６の作業対象物の位置示す画像に基づいて算出されてよい。

次いで、ＣＰＵ２４は、初期姿勢から目標姿勢に至る動作経路上における第１の姿勢と、第２の姿勢を設定する。具体的には、ロボットアーム１６の姿勢を特定する各駆動軸の回転角度を設定する。

ここで、第１の姿勢から第２の姿勢に変化する間の回転角度は、各可動軸について、単調増加又は単調減少するように第１の姿勢及び第２の姿勢は設定される。たとえば、ある可動軸は、第１の姿勢における回転角度から第２の姿勢における回転角度に至るまで単調に増加する。別の可動軸は、第１の姿勢における回転角度から、第２の姿勢における回転角度に至るまで単調に減少する。このように第１の姿勢及び第２の姿勢を設定し、第１の姿勢と第２の姿勢を包含するような第１直方体（後述）と、周辺物との干渉可能性を判定することにより、第１の姿勢から第２の姿勢に移動する際に、周辺物との干渉可能性の有無を高速に判断することが可能になる。すなわち、所定の可動軸の回転角度が増減を繰り返す場合には、ロボットアーム１６の動きが折り返し軌道を描く。一方で、所定の可動軸の回転角度が担当増加または単調に減少する場合には、ロボットアーム１６の動きは略円弧軌道で動作するから、当該所定の軌道について干渉有無の判定を実行すればよく干渉可能性の有無を高速に判断することが可能になる。一方で、所定の可動軸について、第１の姿勢における回転角度から、第２の姿勢における回転角度に至るまでに、回転角度が増減する場合は、この二つの姿勢を包含するような第１直方体から中間姿勢が大きくはみでる可能性があるため、周辺物との干渉可能性が無いことを担保することができず、好ましくない。

次いで、中間姿勢が設定される。中間姿勢は、第１の姿勢と第２の姿勢との間の動作経路上の姿勢であり、たとえば、第１の姿勢に相当する各駆動軸の各回転角度と、第２の姿勢に相当する各駆動軸の各回転角度のそれぞれ平均値を算出し、これにフォワードキネマティクス（順運動学）をあてはめることにより設定することができる。

その後、第１の姿勢、第２の姿勢及び中間姿勢の各リンク（「着目部位」の一例）について、第２直方体（後述）で近似したロボット近似体（「ロボット近似体」の一例）が、生成される。

そして、これら第１の姿勢、中間姿勢及び第２の姿勢のロボット近似体を組み合わせ第１直方体で近似した第１の組み合わせ近似体（「第１の組み合わせ近似体」の一例）が生成される。このとき、第１の組み合わせ近似体は、第１の姿勢、中間姿勢及び第２の姿勢のそれぞれのロボット近似体を包含する直方体であることが好ましい。

次いで、第１の組み合わせ近似体と、周辺物を第１直方体で近似した周辺物近似体（「周辺物近似体」の一例）との干渉可能性が判定される。

この判定の結果、両者の干渉可能性がない場合は、第１の姿勢から第２の姿勢に移動する際に、ロボットアーム１６は、周辺物と干渉しないと判断することができるため、この間の動作経路について詳細な干渉判定をする必要がないと判断することができる。そのため、ＣＰＵ２４は、第２の姿勢を新たな第１の姿勢として設定し、新たに第２の姿勢を設定し、同様の処理を繰り返すことにより初期姿勢から目標姿勢に至る動作経路の全般について、ロボットアーム１６と周辺物との干渉を判定することが可能になる。

一方で、両者の干渉可能性がある場合は、次いで詳細な干渉判定の必要性を判定する。

すなわち、第１の姿勢と第２の姿勢が十分に近接し、十分な分解能をもっている場合に、両者の干渉可能性があると判定された場合は、現実にロボットアーム１６と周辺物とが干渉する可能性が高いと考えられるため、それ以上のロボット近似体を新たに生成して、さらに詳細な干渉判定を継続する必要性はないと判断することができる。ＣＰＵ２４は、第１の姿勢から第２の姿勢に移動する際に、ロボットアーム１６は周辺物と干渉する可能性が高いと決定し、本実施形態に係る干渉判定方法を終了する。そして、必要に応じて計算量を要する別の方法を用いて精密に干渉有無を判断してもよいし、異なる経路を探索してもよい。

他方で、分解能が十分ではなく、第１の姿勢と第２の姿勢の粗密の度合いが疎な場合、すなわち、第１の姿勢と第２の姿勢との間隔が所定値以上である場合には、第１の姿勢と中間姿勢を第１直方体で近似した第２の組み合わせ近似体（「第２の組み合わせ近似体」の一例）と、中間姿勢と第２の姿勢を第１直方体で近似した第２の組み合わせ近似体（「第２の組み合わせ近似体」の一例）と、を生成し、それぞれ周辺物近似体との干渉可能性が同様に判定される。すなわち、第１の組み合わせ近似体よりも小さい第２の組み合わせ近似体を生成し、第２の組み合わせ近似体のそれぞれと、周辺物近似体との干渉可能性が判定される。以下、中間姿勢と第２の姿勢を包含する第２の組み合わせ近似体に着目して説明する。

この判定の結果、中間姿勢と第２の姿勢を包含する第２の組み合わせ近似体と周辺物近似体の干渉可能性がない場合は、中間姿勢から第２の姿勢に移動する際に、ロボットアーム１６は、周辺物と干渉しないと判断することができるため、この間の動作経路について詳細な干渉判定をする必要がないと判断することができる。

一方で、両者の干渉可能性がある場合は、詳細な干渉判定の必要性を判定する。

中間姿勢と第２の姿勢が十分に近接し、十分な分解能をもっている場合は、現実にロボットアーム１６と周辺物とが干渉する可能性が高いと考えられるため、それ以上の詳細な干渉判定の必要性はないと判断することができる。したがって、中間姿勢と第２の姿勢を包含する第２の組み合わせ近似体が周辺物と干渉する可能性がある旨を出力する。

他方で、分解能が十分ではなく、中間姿勢と第２の姿勢の粗密の度合いが疎な場合には、中間姿勢と第２の姿勢の間に、さらに新たな中間姿勢を設定し、元の中間姿勢と新たな中間姿勢とを組み合わせて第１直方体で近似した第３の組み合わせ近似体、及び、この新たな中間姿勢と第２の姿勢とを組み合わせて第１直方体で近似した第３の組み合わせ近似体を生成し、それぞれ周辺物近似体との干渉判定が行われる。同様に、干渉可能性があると判定された際の分解能が十分ではない場合は、第４及びそれ以降の組み合わせ近似体の生成ならびにそれを用いた干渉可能性の判定が、所定の分解能に到達するまで繰り返し実行される。

以上のような干渉判定方法によれば、周辺物との干渉可能性がないと判定された動作経路については、以降の詳細な干渉判定を省略する一方で、干渉可能性があると判定された動作経路については、所定の分解能になるまで中間姿勢を生成しながら詳細な干渉判定を繰り返すので、高速な干渉判定処理と干渉可能性のある動作経路の詳細な特定を両立することが可能になる。

なお、第１直方体とは、所定の基準座標系（例えば、水平方向をＸ軸とＹ軸、鉛直方向をＺ軸、として定義した、互いに直交するＸＹＺ軸を有する絶対座標系）の各軸に平行な線分により構成され、近似する対象となるオブジェクトを包含する直方体のことをいう。所定の基準座標系は、例えば、その原点を、後述するベースリンクＢＬの接地面に設けることができる。

また、第２直方体とは、所定の基準座標系から所定の角度傾斜した第２の直交座標系に平行な線分により構成され、近似する対象となるオブジェクトを包含する直方体のことをいう。

なお、本実施形態では、各リンクを着目部位として、各リンクについてロボット近似体を生成し、干渉判定を実施することとしたが、これに限られるものではなく、一部のリンクのみ（例えば、干渉可能性が高い手先のリンク又はエンドエフェクタ）についてロボット近似体を生成し、干渉判定を実施することにしてもよい。

また、リンク以外の着目部位（たとえば、エンドエフェクタによって把持される対象物そのものや、エンドエフェクタとこれにより把持される対象物を含む部位）やリンクの一部についてロボット近似体を生成し、干渉判定を実施してもよい。

また、当業者の通常の創作能力の発揮として、発明の要旨を変更しない範囲で、本開示の各実施形態における各ステップの順番を変更することもできる。たとえば、第１の姿勢及び第２の姿勢と同時に複数の中間姿勢を設定してもよい。ただし、必要な場合（すなわち、干渉可能性がある場合）にのみその動作経路間に中間姿勢を設定することにより、一層の高速化を実現することができる。

また、近似の方法は、様々であり、第１直方体や第２直方体などの方法で、対象となるオブジェクトを包含するようなバウンディングボリューム（Bounding Volume）によりオブジェクトを近似してもよいし、いわゆる凸包のようにオブジェクトを包含しない多面体によりオブジェクトを近似してもよい。ただし、バウンディングボリュームを用いて、オブジェクトを包含するように近似することにより、本来は干渉するのに干渉しないと判断される誤判定をなくすことが可能になる。

［第２実施形態］
以下、図面を参照して本発明の第２実施形態について説明する。なお、同一の要素には同一の符号を付し、重複する説明を省略又は簡略化する。

図１は、第２実施形態に係る干渉判定システム１０（「干渉判定システム」の一例）のハードウェアブロック図である。

ここで、演算装置１４（「演算装置」の一例）のＣＰＵ２４は、記憶装置２６（「記憶部」の一例）に記憶されているプログラム（本開示の各フローチャート等で示される演算処理を規定するプログラムを含む）を読み出し、又は、インタフェース２８（「取得部」の一例）を用いて外部からプログラムを取得し、実行する。演算装置１４が備える一時記憶装置（不図示）は、ＳＲＡＭ（Static Random Access Memory）等から構成されており、プログラムの一部や、演算データ等を一時的に記憶する。

記憶装置２６は、コンピュータを用いて読み取り可能な状態で、プログラム等の情報を、電気的、磁気的、光学的、機械的、化学的又はそれらの組み合わせによって記憶する媒体であり、例えば、ＣＤ、ＤＶＤ、磁気ディスク、ＭＯ、半導体メモリ（ＮＯＲフラッシュメモリ、ＮＡＮＤフラッシュメモリ、ＭＲＡＭ等）を含む。

インタフェース２８は、例えば、外部との情報の授受をするための有線又は無線の通信インタフェースである。

また、入力部１２は、例えば、マウス、キーボード、タッチパッド、キーパッド、マイク等の情報を入力するための装置である。

図２（ａ）は、制御対象であるロボットアーム１６（「ロボット」の一例）を示している。また、図２（ｂ）は、後述するステップＳ１２に基づいて、ロボットアーム１６を構成する複数のリンクＬであるリンクＢＬ〜Ｌ５（「着目部位」の一例）を第２直方体で近似したロボットデータを示している。

このロボットアーム１６は、６軸の垂直多関節型のロボットアーム１６であり、各リンクＬは、サーボモータ（不図示）により回転駆動される。また、先端のリンクＬ５には、エンドエフェクタが接続される。

このような干渉判定システム１０を用いた干渉判定方法について以下に説明する。

図３は、判定処理に必要なデータを生成するための事前処理のフローチャートである。この事前処理は、障害物等の周辺物や、ロボットアーム１６が変更されるたびに実施される。

まず、演算装置１４のインタフェース２８は、入力部１２から障害物情報として、メッシュ等により表現された周辺物等を仮想空間上に表現した障害物モデルを取得する。そして、ＣＰＵ２４は、メッシュにより表現された障害物モデルを、第１直方体、第２直方体またはその他の公知の手法を用いて、周辺物の形状を近似した周辺物近似体（「周辺物近似体」の一例）を生成し、記憶装置２６に記憶させる（ステップＳ１１）。本実施形態では、複数の周辺物をそれぞれ第１直方体で近似した周辺物近似体データＯｂｓ_i（ただし、ｉは、１以上で周辺物の数以下の整数）が、記憶装置２６に記憶される。

また、インタフェース２８は、入力部１２からロボット情報として、ロボットアーム１６をメッシュ等により表現したロボットモデルを取得する。そして、ＣＰＵ２４は、メッシュにより表現された障害物モデルをロボットアーム１６の各リンクＬに区分し、各リンクＬを第２直方体で近似したロボットデータを生成し、記憶装置２６に記憶させる（ステップＳ１２）。なお、ステップＳ１１とステップＳ１２とは異なる順序で、または、同時に行われてもよい。

次いで、ロボットアーム１６の初期姿勢Ｓ及び目標姿勢Ｇが入力部１２から入力される。初期姿勢Ｓは、たとえば、コンテナに置かれている把持対象物であるワークＷをロボットアーム１６が把持するときの姿勢であり、目標姿勢Ｇは、ロボットアーム１６がコンテナからワークＷを取り出し、目的地に載置するときの姿勢である。初期姿勢Ｓ及び目標姿勢Ｇは、それぞれ、ロボットアーム１６の各駆動軸の回転角度を指定する６次元の情報であり、ティーチングペンダント等を用いて入力部１２から入力することもできる。演算装置１４のＣＰＵ２４は、インタフェース２８に初期姿勢Ｓ及び目標姿勢Ｇを特定する各６次元の角度情報を取得させ、記憶装置２６に記憶させる。なお、初期姿勢Ｓ及び目標姿勢Ｇは、それぞれ、ロボットアーム１６の先端初期位置Ｓ’、先端目標位置Ｇ’として与えられ、先端初期位置Ｓ’、先端目標位置Ｇ’に基づいて、インバースキネマティクス（逆運動学）計算を実行することにより算出されてもよい。先端初期位置Ｓ’、及び、先端目標位置Ｇ’は、例えば、図示しないティーチングペンダントを用いて、作業者が設定することができる。

その後、経路探索を実行し、初期姿勢Ｓから目標姿勢Ｇに至る動作経路を探索する。

具体的には、動作経路上におけるある地点におけるロボットアーム１６の姿勢ｑ_i（「第１の姿勢」の一例）と、その姿勢よりも相対的に目標姿勢Ｇ側の動作経路上の地点における姿勢ｑ_i+1（「第２の姿勢」の一例）を特定する各駆動軸の角度情報を入力とし、姿勢ｑ_iから姿勢ｑ_i+1に移動するまでに周辺物と干渉するか否かを出力とする干渉判定方法を、初期姿勢Ｓから目標姿勢Ｇに至るまで繰り返して実行することにより、周辺物と干渉しないような動作経路を特定する各姿勢ｑ_iのリストを生成する。

ここで、姿勢ｑ_iから姿勢ｑ_i+1に変化する間の各駆動軸の回転角度は、駆動軸ごとに単調増加、または、単調減少するように姿勢ｑ_i+1は設定される。

図４（ａ）は、たとえば、二つの駆動軸を有するロボットアーム１６が、初期姿勢Ｓから目標姿勢Ｇに至る動作経路を探索する様子を、各駆動軸の回転角度を座標軸（Joint1及びJoint2）とするコンフィギュレーション空間で示した模式図である。このロボットアーム１６の姿勢は、各駆動軸の回転角度に対応する座標で示すことができる。また、周辺の障害物Ｄ１及びＤ２は、ロボットアーム１６が衝突する各駆動軸の範囲として、所定の領域を有する空間として示すことができる。

従って、障害物Ｄ１及びＤ２の領域に侵入しないように、初期姿勢Ｓに相当する座標から目標姿勢Ｇに相当する座標に至る動作経路を生成することにより、干渉しない動作経路を導くことができる。

図４（ｂ）は、姿勢ｑ_iから姿勢ｑ_i+1に変化する間の各駆動軸の回転角度を示しており、横軸は、姿勢ｑ_iから姿勢ｑ_i+1への進捗を示し、縦軸は各駆動軸（Joint1及びJoint2）の回転角度（degree）を示している。両駆動軸とも、等速で単調増加していることが示される。

このように、各駆動軸が単調増加、または、単調減少する範囲内の姿勢を姿勢ｑ_i+1として設定し、この間の干渉判定をすることにより干渉判定の精度が向上するとともに干渉判定の演算を高速に実行することができる。なお、姿勢ｑ_iから姿勢ｑ_i+1に変化する間に回転角度が増減する場合、すなわち、図４（ａ）に示されるコンフィギュレーション空間で、Joint1軸方向に増加した（右側に進行した）後に、減少する（左側に進行する）姿勢間で干渉判定をすると、干渉判定の精度が低下し、実際には干渉するにもかかわらず干渉しないと判定してしまう可能性が高まるため、本実施形態では採用しない。

図４（ｃ）は、参考として、実空間においてロボットアーム１６が姿勢ｑ_iから姿勢ｑ_i+1に変化する様子を示している。

なお、経路の探索は種々の手法により行うことができる。例えば、ランダムサンプリング法の一つであるＲＲＴ（Rapidly-Exploring Random Tree）、ロードマップ法の一つである確率的ロードマップ（Probabilistic Road Map：ＰＲＭ）、ポテンシャル法（Artificial Potential Method）、軌道最適化（Trajectory Optimization）等を用いることができる。

ランダムサンプリング法の一つであるＲＲＴは、コンフィギュレーション空間内に姿勢ｑ_i+1に対応する点を一つ配置し、当該点と、既にコンフィギュレーシ ョン空間内に配置されている姿勢ｑ_iに対応する点と、を結ぶ処理を繰り返すことにより経路を生成する手法である。

確率的ロードマップ（Probabilistic Road Map：ＰＲＭ）は、姿勢ｑ_i及び姿勢ｑ_i+1に対応する複数の点をコンフィギュレーション空間内にランダムに配置し、これらの点の中から周辺物と干渉が生じない点を抽出し、これらの点を結ぶことにより経路を生成する手法である。

ポテンシャル法（Artificial Potential Method）は、ロボットアーム１６及び周辺物が位置し得る領域内のポテンシャルを算出し、ポテンシャルに基づいて経路を生成する手法である。例えば、評価関数を使用することにより、ロボットアーム１６及び周辺物が位置し得る領域内のポテンシャルを算出する。

軌道最適化（Trajectory Optimization）は、コンフィギュレーション空間内における姿勢ｑ_nに対応する点の配置に関するコスト関数の最適化問題を解くことにより、経路を生成する。コスト関数とは、例えば、ロボットアーム１６と対象物と周辺物（障害物）との距離、コンフィギュレーション空間内における経路の滑らかさ、ロボットアーム１６が有する複数の駆動軸が発生させるべきトルクの最大値、等に基づいて設定される関数である。

図５は、姿勢ｑ_iから姿勢ｑ_i+1に移動する動作経路におけるロボットアーム１６の所定のリンクＬと周辺物との干渉判定方法を示すフローチャートである。図６は、この干渉判定方法で用いられるチェックデータリストＤＬの変化を示している。ここで、チェックデータリストＤＬとは、複数のチェックデータＤを記憶するスタック型のデータ構造をいい、チェックデータＤの後入れ先出し（ＬＩＦＯ）が可能となるように構成されている。また、チェックデータＤは、干渉判定の対象となる始点と終点の二つの姿勢を特定するデータである。本実施形態では、このチェックデータＤに基づいて、２つの姿勢を結ぶ経路上の中間姿勢が演算され、チェックデータＤに含まれるこれら２つの姿勢、及び、中間姿勢の少なくとも３姿勢に相当するロボット近似体データを包含した第１（または第２以降の）組み合わせ近似体が生成される。

まず、演算装置１４は、記憶装置２６の所定領域に設けられたチェックデータリストＤＬの末尾に、チェックデータＤとして、[link_i, link_i+1］を記録する（ステップＳ５１、図６（ａ））。[link_i, link_i+1］というチェックデータＤは、ロボットアーム１６の姿勢ｑ_i及び姿勢ｑ_i+1に対応する所定のリンクＬ（「着目部位」の一例）の姿勢を特定する。

図７（ａ）は、ロボットアーム１６が姿勢ｑ_i及び姿勢ｑ_i+1に移動する様子と周囲の障害物を模式的に示しており、図７（ｂ）は、姿勢ｑ_i及び姿勢ｑ_i+1の際のロボットアーム１６の先端のリンクＬをそれぞれ第２直方体で近似したロボット近似体と、二つの周辺物に相当する周辺物近似体データＯｂｓ₁とＯｂｓ₂を示している。

次いで、演算装置１４は、チェックデータリストＤＬの末尾のチェックデータＤを、[link_a, link_b］として取り出す（ステップＳ５２）。ここでは、チェックデータリストＤＬの末尾のチェックデータＤとしてステップＳ５１で記録された[link_i, link_i+1］が[link_a, link_b］として取り出され、チェックデータリストＤＬから、取り出されたチェックデータＤである[link_i, link_i+1］は削除される。link_aは、粗密探索状態における「着目部位」の「第１の姿勢」の一例であり、link_bは、粗密探索状態における「着目部位」の「第２の姿勢」の一例である。

次いで、演算装置１４により、link_aとlink_bの中間リンクを特定するlink_cが生成される（ステップＳ５３）。

図８は、link_aとlink_bの中間リンクであるlink_cが設定される様子を示している。

link_aの際の各駆動軸の回転角度を示すジョイント値（「回転角度」の一例）と、link_bの際の各駆動軸の回転角度を示すジョイント値の平均値に基づいてフォワードキネマティクス（順運動学）を解くことで、中間リンクであるlink_cを設定することができる。この場合、コンフィギュレーション空間上におけるlink_aに対応する座標とlink_bに対応する座標の中点がlink_cに対応する座標となる。すなわち、コンフィギュレーション空間上におけるlink_aに対応する座標Ｐは、Ｐlink_a＝（ｊ_a1, ｊ_a2,・・・ｊ_a6）であり（ｊ_a1, ｊ_a2,・・・ｊ_a6は各回転軸の回転角度を示す）、link_bに対応する座標Ｐは、Ｐlink_b＝（ｊ_b1, ｊ_b2,・・・ｊ_b6）である。これら、Ｐlink_aの各座標とＰlink_bの各座標の中点がlink_cに対応する座標となる。

中間リンクは、別の方法で設定することもできる。たとえば、ロボットアーム１６の各リンクＬの回転速度は等速ではなく増減するため、各リンクＬの回転速度の変化を考慮して、link_aからlink_bへ移動する中間の時点における各駆動軸の回転角度を求め、求められた各回転角度に基づいてフォワードキネマティクスを解くことによっても、中間リンクであるlink_cをより正確に設定できる。すなわち、link_aからlink_bへ移動する期間において、各駆動軸はすべて一様に動作するわけでは無く、動作の前半の一部分や、動作の後半の一部分にのみ動作する駆動軸も存在する。したがって、link_aからlink_bへ移動する中間の時点における各駆動軸の回転角度を求め、求められた各回転角度に基づいてフォワードキネマティクスを解くことによって中間リンクであるlink_cをより正確に設定できる
次いで、演算装置１４により、link_a、link_b及びlink_cを近似する近似体と、周辺物の干渉可能性が判定される（ステップＳ５４）。具体的には、link_a、link_b及びlink_cに対応するリンクＬの形状を第２直方体で近似したロボット近似体（「ロボット近似体」の一例）を生成し、これらを包含する第１直方体で近似した第１の組み合わせ近似体（「第１の組み合わせ近似体」の一例）を生成し、周辺物近似体データＯｂｓ₁及びＯｂｓ₂との干渉可能性を判定する。

link_aに相当するロボット近似体は、姿勢ｑ_iの各駆動軸のジョイント値と、各リンクＬの長さ、ならびに、ステップＳ１２で記憶されたリンクＬのロボットデータに基づいて計算することができ、第２直方体を特定する各頂点の値として算出することができる。なお、第２の直方体は、有効境界ボックス（OBB: Oriented Bounding Box）により生成されてよい。

同様に、link_b及びlink_cについてもロボット近似体が算出される。

次いで、これら３つのロボット近似体の各頂点の座標の最大値及び最小値を座標軸ごとに抽出することにより、これら３つのロボット近似体を組み合わせて構成される第１の組み合わせ近似体が算出される。ここで、ロボット近似体の各頂点に内接するように第１の組み合わせ近似体を生成してもよいし、所定の距離だけロボット近似体と離間するように、これらロボット近似体を包含する第１の組み合わせ近似体を生成してもよい。

そして、第１の組み合わせ近似体と周辺物近似体データＯｂｓ₁及びＯｂｓ₂との干渉可能性が判定される。まず、第１の組み合わせ近似体と周辺物近似体データＯｂｓ_iとの最短距離ｍがそれぞれ算出される。これは、第１組み合わせ近似体と各周辺物近似体の各座標を比較することにより算出することができる。

次いで、最短距離ｍを、干渉可能性があるか否かを判定するための閾値と比較する。閾値は、予め設定された値を用いてもよく、また、その他の値を用いることが可能であるが、本実施の形態では以下のように、（Ｌ２＋Ｌ３−Ｌ１）を閾値として用いる。すなわち、link_a及びlink_cのリンク間距離Ｌ２、link_b及びlink_cのリンク間距離Ｌ３及びlink_a及びlink_cのリンク間距離Ｌ１を、各姿勢におけるリンクＬの特定位置の座標に基づいて算出し、（Ｌ２＋Ｌ３−Ｌ１）を算出する。Ｌ１は、現状態のリンク間距離を示し、（Ｌ２＋Ｌ３）は、次状態のリンク間距離を示しているため、仮にリンクＬが円弧運動をすると仮定すると、「（Ｌ２＋Ｌ３）＞Ｌ１」である。このとき、第１の組み合わせ近似体から初期姿勢と目標姿勢とを結ぶ実際の軌道上のある点におけるロボットアーム１６のリンクＬがはみ出るとしても、多くとも（Ｌ２＋Ｌ３−Ｌ１）であると合理的に見積もることができる。従って、（Ｌ２＋Ｌ３−Ｌ１）とｍを比較し、「（Ｌ２＋Ｌ３−Ｌ１）＞ｍ」ならば、その周辺物近似体データＯｂｓ_iとリンクＬは、link_aからlink_cで干渉可能性があると判定される。

図９は、第１の組み合わせ近似体と周辺物近似体データＯｂｓ₁及びＯｂｓ₂が、それぞれ干渉可能性があると判定された様子を示している。

ステップＳ５４で干渉可能性がある周辺物近似体データＯｂｓ_iがある場合（「ＹＥＳ」）は、続くステップＳ５５において、演算装置１４により、link_a、link_b及びlink_cを更に細かく（分解能を高めて）干渉判定する必要がある（「ＹＥＳ」）か、あるいは、各姿勢が十分に近接し、十分な分解能をもっているから、それ以上の詳細な分解能で本実施に係る干渉判定の必要性はない（「ＮＯ」）か、判定される。

具体的には、以下の２つの条件の双方が満足されない場合は、更に分解能を高めて干渉判定する。

第１の条件は、link_aからlink_cを介してlink_bに至るリンクＬの移動軌跡が、実際の移動軌跡を十分に再現できているかを示す。十分に再現されている場合は、それ以上詳細に本実施形態に係る高速な干渉判定の必要性はない（「ＮＯ」）と判断される。

図１０（ａ）は、第１の条件を示す模式図である。この図に示されるように、link_a、link_b及びlink_cのロボット近似体データに基づいて、各姿勢におけるリンクＬの所定頂点Ａの次状態のリンク間距離（Ｌ２＋Ｌ３）に対する現状態のリンク間距離Ｌ１の比率である「Ｌ１／（Ｌ２＋Ｌ３）」を移動軌跡の再現率として計算する。ここで、Ｌ１／（Ｌ２＋Ｌ３）≦１であるから、リンク間距離Ｌ１と、リンク間距離（Ｌ２＋Ｌ３）の値が近く、再現率が１に近いほど、link_aからlink_cを介してlink_bに至るリンクＬの移動軌跡が、実際の移動軌跡を十分に再現できていると考えることができる。

次いで、頂点Ａの対角に位置する頂点に相当する頂点Ｂについても、同様に再現率を計算する。すなわち、第２の直方体を用いて近似された各ロボット近似体のぞれぞれに設定された頂点Ａに対し、頂点Ａの対角の位置に存在する第２の直方体の各頂点についても、同様に再現率を計算する。

そして、両者のうち大きい方の再現率を所定値と比較して、１つ目の条件が満足されているかどうか決定する。なお、所定値としては、例えば、０．８以上、１．０未満の値を用いることができる
このように対角頂点に相当する２点について再現率をそれぞれ計算することにより、リンクＬが一端を基点として動作する場合に、基点付近のほとんど移動しない頂点に対する再現率が異常値を示しても、対角頂点に対する再現率を用いることで正確な判定が可能になる。

第２の条件は、link_aとlink_bとの間隔（「間隔を示す量」の一例）が十分に狭いか否かを示す。link_aとlink_bの間隔が十分に狭いといえる場合は、それ以上詳細に本実施形態に係る高速な干渉判定の必要性はない（「ＮＯ」）と判断される。

図１０（ｂ）は、リンク間の間隔が十分に狭いか否か判断する様子を示している。具体的には、link_a及びlink_bのロボット近似体データを、分離軸ＡＸ（たとえば、ｘ軸、ｙ軸及びｚ軸の各軸のいずれか）に射影し、link_a及びlink_bの各中心点ならびに各頂点の座標を取得する。そして、分離軸ＡＸ上で、互いに最も近接する頂点同士の距離をＬｂとし、その頂点と中心点との距離をそれぞれＬａ及びＬｃとして、「Ｌｂ／（Ｌａ＋Ｌｃ）」を所定値と比較する。たとえば、いずれかの軸において「Ｌｂ／（Ｌａ＋Ｌｃ）＞３」であれば、その軸については、間隔が十分に狭いといえないため、第２の条件は不満足である。全ての軸において「Ｌｂ／（Ｌａ＋Ｌｃ）≦３」であれば、第２の条件を満足する。

両条件を共に満足しない場合は、分解能が低い状態で干渉可能性が示されたに過ぎないから、更に分解能を高めて干渉判定するために（「ＹＥＳ」）、ステップＳ５６以降に進む。

ステップＳ５６に進んだときのチェックデータリストＤＬは、図６（ｂ）の右側に示される。チェックデータリストＤＬの末尾に記録されていた［link_i, link_i+1］は、[link_a, link_b］として取り出されたため既に削除済みだが、替りにステップＳ５５において詳細にチェックされる可能性がある姿勢である[link_a、link_c]（ステップＳ５６）及び[link_c、link_b]（ステップＳ５７）が順番に記録される（図６（ｂ））。

そして、ステップＳ５２に戻り、チェックデータリストＤＬの末尾に記録されている［link_c, link_b］が［link_a, link_b］として取り出される。次いで、ステップＳ５３において、中間リンクであるlink_cが設定され、ステップＳ５４において、新たに設定されたlink_a、link_b及びlink_cに相当する３つのロボット近似体を組み合わせて構成される第２の組み合わせ近似体（「第２の組み合わせ近似体」の一例）が生成される。

図１１は、第２の組み合わせ近似体を示している。この図に示されるとおり、第１の組み合わせ近似体よりも第２の組み合わせ近似体は小さい。ここで、小さいとは、組み合わせ近似体の面積または体積の値が相対的に小さいことをいう。そして、上述したとおり、リンク間距離Ｌ２、Ｌ３及びＬ１に基づいて計算される（Ｌ２＋Ｌ３−Ｌ１）の値と、第２の組み合わせ近似体と周辺物近似体データＯｂｓ_iとの距離を示すｍの値を比較し、両者の干渉判定をする。図１１では、「ｍ≧（Ｌ２＋Ｌ３−Ｌ１）」のため、干渉可能性がない（「ＮＯ」）と判定された様子を示している。

ステップＳ５４において「ＮＯ」の場合、演算装置１４により、ステップＳ５９においてチェックデータリストＤＬにチェックデータＤが残っているか調べられる。（ステップＳ５９）。チェックデータＤが残っておらず、チェックデータリストＤＬが空の場合（「ＹＥＳ」）は、フローチャートが終了する。空でない場合（「ＮＯ」）は、ステップＳ５２に戻る。ここでは、図６（ｃ）に示されるように、ステップＳ５７においてチェックデータリストＤＬに記録された［link_c, link_b］は取り出されて削除されたが、ステップＳ５６においてチェックデータリストＤＬに記録された[link_a、link_c]が残っているため、ステップＳ５２に戻る。

その後、ステップＳ５２において、[link_a、link_c]を、[link_a、link_b]として取り出し、中間リンクに相当するlink_cを生成する（ステップＳ５３）。

図１２は、新たに設定されたlink_a、link_b及びlink_cと、これらに相当する３つのロボット近似体を組み合わせて構成される第２の組み合わせ近似体（「第２の組み合わせ近似体」の一例）を示している。この図に示されるように「ｍ＜（Ｌ２＋Ｌ３−Ｌ１）」の場合、ステップＳ５５に進む。

ステップＳ５５において、干渉判定の分解能が低い場合は、ステップＳ５６及びＳ５７を経てステップＳ５２に戻る。このときのチェックデータリストＤＬは、図６（ｄ）に示される。

図１３は、ステップＳ５２に戻り、図１２におけるlink_cをlink_aとし、link_bをlink_bとして中間リンクに相当するlink_cを生成し、これらに相当する３つのロボット近似体を組み合わせて構成される第３の組み合わせ近似体を示している。この図に示されるように、第３の組み合わせ近似体は、第２の組み合わせ近似体よりも小さい。この図に示されるように「ｍ＜（Ｌ２＋Ｌ３−Ｌ１）」の場合、再度ステップＳ５５に進む。

ステップＳ５５において、干渉判定の分解能が低い場合は、ステップＳ５６及びＳ５７を経てステップＳ５２に戻る。このときのチェックデータリストＤＬは、図６（ｅ）に示される。

図１４は、ステップＳ５２に戻り、図１３におけるlink_cをlink_aとし、link_bをlink_bとして中間リンクに相当するlink_cを生成し、これらに相当する３つのロボット近似体を組み合わせて構成される第４の組み合わせ近似体を示している。この図に示されるように、第４の組み合わせ近似体は、第３の組み合わせ近似体よりも小さい。この図に示されるように「ｍ＜（Ｌ２＋Ｌ３−Ｌ１）」の場合、再度ステップＳ５５に進む。

ステップＳ５５において、干渉判定の分解能が低い場合は、ステップＳ５６及びＳ５７を経てステップＳ５２に戻る。このときのチェックデータリストＤＬは、図６（ｆ）に示される。

図１５は、ステップＳ５２に戻り、図１４におけるlink_cをlink_aとし、link_bをlink_bとして中間リンクに相当するlink_cを生成し、これらに相当する３つのロボット近似体を組み合わせて構成される第５の組み合わせ近似体を示している。この図に示されるように、第５の組み合わせ近似体は、第４の組み合わせ近似体よりも小さい。この図に示されるように「ｍ＞（Ｌ２＋Ｌ３−Ｌ１）」の場合、ステップＳ５９に進む。

ステップＳ５９において、チェックデータリストＤＬは空ではない（「ＮＯ」）ので、ステップＳ５２に戻り、末尾のチェックデータＤが取り出される。

図１６は、図１４におけるlink_aをlink_aとし、link_cをlink_bとして中間リンクに相当するlink_cを生成し、これらに相当する３つのロボット近似体を組み合わせて構成される第５の組み合わせ近似体を示している。この図に示されるように「ｍ＜（Ｌ２＋Ｌ３−Ｌ１）」の場合、再度ステップＳ５５に進む。

ステップＳ５５において、干渉判定の分解能が低い場合は、ステップＳ５６及びＳ５７を経てステップＳ５２に戻る。

図１７は、図１６におけるlink_cをlink_aとし、link_bをlink_bとして中間リンクに相当するlink_cを生成し、これらに相当する３つのロボット近似体を組み合わせて構成される第６の組み合わせ近似体を示している。この図に示されるように「ｍ＜（Ｌ２＋Ｌ３−Ｌ１）」の場合、再度ステップＳ５５に進む。

そして、ステップＳ５５において、第１の条件または第２の条件を満足する場合は、ステップＳ５８に進む。

ステップＳ５８において、その時のlink_a、link_b、link_cならびに周辺物近似体データＯｂｓ_iに相当する周辺物を判定結果Ｒに記録し、ステップＳ５９に進み、チェックデータリストＤＬに残っているチェックデータＤについて同様の処理を繰り返す。

図１８は、図１６におけるlink_aをlink_aとし、link_cをlink_bとして中間リンクに相当するlink_cを生成し、これらに相当する３つのロボット近似体を組み合わせて構成される第６の組み合わせ近似体を示している。この図に示されるように「ｍ＜（Ｌ２＋Ｌ３−Ｌ１）」の場合、再度ステップＳ５５に進み、同様に、第１の条件または第２の条件を満足する場合は、ステップＳ５８に進み、その時のlink_a、link_b、link_cならびに周辺物近似体データＯｂｓ_iに相当する周辺物を判定結果Ｒに記録し、ステップＳ５９に進む。

図１９は、図５に示されるフローチャートに従って同様の処理を実行した実行結果を示している。この図に示されるように、link_iからlink_i+1に至る経路において、第２の組み合わせ近似体による干渉判定処理で終わっている部分、第４の組み合わせ近似体による干渉判定処理で終わっている部分、第５の組み合わせ近似体による干渉判定処理で終わっている部分、第６の組み合わせ近似体による干渉判定処理で終わっている部分がある。

その後、ロボットアーム１６の異なるリンクＬについて、図５に示されるフローチャートを順次実行する。なお、図５に示されるフローチャートに示す干渉判定処理は、ロボットアーム１６の少なくとも１つの着目部位に対して行われればよい。

なお、図５に示すフローチャートに示す干渉判定処理を実行した後、干渉可能性が有と判定された判定結果Ｒで示される姿勢間において、より精密に干渉判定をすることができる異なる干渉判定方法を用いて、実際に干渉するか否かを決定する演算処理や、あるいは、干渉する位置を特定するための演算処理などを実行してもよい。

以上のような干渉判定方法によれば、周辺物の干渉可能性がないと判定された部分については、以降の詳細な干渉判定を省略する一方で、干渉可能性があると判定された部分については、所定の分解能に達するまで干渉判定を繰り返すので、高速な干渉判定処理と干渉可能性のある動作経路の詳細な特定を両立することが可能になる。

なお、ステップＳ５４において生成された第１の組み合わせ近似体、または、他の組み合わせ近似体と、周辺物近似体データＯｂｓ_iが重複するか接触する場合は、干渉が確実であることから、その時点で図５に示されるフローチャートを終了し、その旨を出力するようにしてもよい。

また、近似する方法は、本実施形態に限られず、例えば、凸包のような多面体で近似してもよい。また、周辺物については、事前処理において取得された障害物モデルそのものを用いて干渉判定をしてもよい。

また、組み合わせ近似体を所定の距離だけロボット近似体と離間するように、これらロボット近似体を包含する第１の（または第２以降の）組み合わせ近似体を生成し、周辺物近似体と干渉判定してもよい。たとえば、組み合わせ近似体の大きさに応じた距離だけロボット近似体と離間するように、これらロボット近似体を包含する第１（または第２以降）の組み合わせ近似体を生成してもよい。

ステップＳ５５における判断手法は、異なる指標を用いて様々な方法を適用してもよいし、省略することもできる。たとえば、隣接する姿勢間の距離に基づいて、以降の高分解能での干渉判定処理の要否を判断してもよい。

本実施形態に示される干渉判定方法は、様々なロボットに適用可能であり、たとえば、水平多関節型のロボットアームに用いることもできる。

また、ステップＳ５４において、所定の場合は、異なる方法で干渉判定をしてもよい。たとえば、各リンクＬのジョイント値の組み合わせによっては、円弧運動ではなく波運動になる場合があるため、例えば、先端のリンクＬのジョイント値が大きく変動する場合は、干渉可能性があると判断することにしてもよい。

なお、本明細書において、「部」や「手段」、「手順」とは、単に物理的構成を意味するものではなく、その「部」等が行う処理をソフトウェアによって実現する場合も含む。また、１つの「部」等や、装置が行う処理が２つ以上の物理的構成や装置により実行されても、２つ以上の「部」等や、装置が行う処理が１つの物理的手段や装置により実行されてもよい。また、以上の実施の形態は、本発明を説明するための例示であり、本発明をその実施形態のみに限定する趣旨ではない。

また、本発明は、その要旨を逸脱しない限り、さまざまな変形が可能である。たとえば、当業者の通常の創作能力の範囲内で、ある実施形態における一部の構成要素を、他の実施形態に組み合わせることもできる。また、要旨を逸脱しない範囲で、各フローチャートに示される各ステップの順番を変更することもできる。

［第３実施形態］
以下、図面を参照して本発明の第３実施形態について説明する。なお、同一の要素には同一の符号を付し、重複する説明を省略又は簡略化する。

図２０は、第３実施形態に係る干渉判定方法のフローチャートである。第２実施形態に係る干渉判定方法と異なる点は、ステップＳ５５において「ＮＯ」と判断された後に、新たなステップＳ６０として対象の姿勢間で詳細な干渉判定を実行し、干渉する場合は、フローチャートを終了する点である。

より具体的には、ステップＳ５４において、link_a、link_c及びlink_bからなる組み合わせ近似体が、周辺物近似体データＯｂｓ_iと干渉可能性があると判定され、かつ、ステップＳ５５において、既に十分な分解能に達していると判断された（「ＮＯ」）場合は、高精度の干渉判定が可能となる別の干渉判定方法を用いて、link_a、link_c 及びlink_bで規定される所定リンクＬの姿勢間の動作経路において、周辺物近似体データＯｂｓ_iとの干渉判定を実行する（ステップＳ６０）。例えば、link_a、からlink_bの間で、隣接するロボット近似体同士が接触する、すなわち、隣接するロボット近似体の間に隙間が生じない程度の離散幅で、複数の中間姿勢のロボット近似体を生成し、生成された各ロボット近似体と周辺物近似体との干渉の有無を判定することで、詳細な干渉判定を実行する。

その結果、干渉すると判定（「ＹＥＳ」）された場合は、フローチャートを終了する。出力結果としては、干渉することを示す出力でもよいし、干渉すると判定されたリンクＬ及び姿勢を特定する出力形態でもよい。

干渉しないと判定（「ＮＯ」）された場合はステップＳ５８以降に進み、第２実施形態と同様の処理が行われる。

このように、第２実施形態に係る高速な干渉判定処理とは別に、低速で高精度の干渉判定処理アルゴリズムを準備しておき、高速な干渉判定処理で絞り込まれた所定の動作経路の一部についてのみ、高精度の干渉判定処理アルゴリズムを適用するようにしたから、高速で高精度の干渉判定を実現することが可能になる。

なお、第１の姿勢と第２の姿勢の間の姿勢のうち、目標姿勢に近い方から順番に干渉判定をするようにしたが、初期姿勢に近い姿勢から干渉判定を実行して、所定の分解能に達しても、ステップＳ６０の結果、干渉すると判定された時点でその姿勢を出力するとともに以降の干渉判定処理を中止するようにしてもよい。その際に、処理を中止せず、干渉しないと判定されたそれまでの経路に続く新たな経路を探索するように構成してもよい。

上記の実施形態の一部又は全部は、以下の付記のようにも記載され得るが、以下には限られない。

（付記１）
インタフェース２８、記憶装置２６及び演算部２４を備える演算装置１４を用いて、複数の可動軸を有するロボットアーム１６が初期姿勢から目標姿勢に移動する動作経路上で、前記ロボットアーム１６の周辺に存在する周辺物と干渉する可能性を判定する方法であって、
前記演算部２４は、
前記記憶装置２６に、前記ロボットアーム１６の形状を、所定の着目部位について多面体で近似したロボットデータを記憶させるステップと、
前記記憶装置２６に、前記周辺物の形状を近似した周辺物近似体のデータを記憶させるステップと、
前記インタフェース２８を用いて、前記初期姿勢及び前記目標姿勢を取得するステップと、
前記初期姿勢から前記目標姿勢へと移動する前記動作経路上における前記ロボットアーム１６の第１の姿勢と、前記第１の姿勢よりも、相対的に前記目標姿勢側の前記動作経路上における前記ロボットアーム１６の第２の姿勢と、前記第１の姿勢と前記第２の姿勢との間の中間姿勢と、を設定するステップと、
前記ロボットデータに基づいて、前記第１の姿勢、前記第２の姿勢及び前記中間姿勢における前記ロボットアーム１６の形状を、少なくとも一つの前記着目部位について前記多面体で近似した複数のロボット近似体を生成するステップと、
このステップで生成された複数の前記ロボット近似体を組み合わせて構成される第１の組み合わせ近似体を生成するステップと、
前記第１の組み合わせ近似体と、前記周辺物近似体とが干渉するか判定するステップと、
このステップにおいて干渉すると判定された場合は、
前記第１の組み合わせ近似体を構成する複数の前記ロボット近似体のうち、隣接する二つの前記ロボット近似体の間隔を示す量を算出し、所定値と比較するステップと、
前記間隔を示す量と前記所定値との比較結果に基づいて、前記第１の組み合わせ近似体よりも小さい組み合わせ近似体を生成するか否かを判断するステップと、
を実行する干渉判定方法。

（付記２）
演算部２４を備える演算装置１４を用いて、複数の可動軸を有するロボットアーム１６が初期姿勢から目標姿勢に移動する動作経路上で、前記ロボットアーム１６の周辺に存在する周辺物と干渉する可能性を判定する方法であって、
前記演算部２４は、
前記初期姿勢から前記目標姿勢へと移動する前記動作経路上における前記ロボットアーム１６の第１の姿勢を特定するための複数の前記可動軸の回転角度を設定するステップと、
前記第１の姿勢よりも前記目標姿勢側の前記動作経路上における前記ロボットアーム１６の第２の姿勢を特定するための複数の前記可動軸の回転角度であって、前記第１の姿勢から前記第２の姿勢に変化する間の回転角度は、前記可動軸ごとに、単調増加又は単調減少する回転角度を、設定するステップと、
前記第１の姿勢と前記第２の姿勢との間の少なくとも一つの中間姿勢を特定するために複数の前記可動軸の回転角度を示す情報を設定するステップと、
前記ロボットアーム１６の少なくとも一つの着目部位について、前記第１の姿勢、前記第２の姿勢及び前記中間姿勢を多面体で近似した複数のロボット近似体を生成するステップと、
このステップで生成された複数の前記ロボット近似体を組み合わせて構成される第１の組み合わせ近似体が、前記周辺物と干渉するか判断するステップと、
このステップで干渉すると判断された場合は、複数の前記ロボット近似体を組み合わせて構成され、前記第１の組み合わせ近似体よりも小さい第２の組み合わせ近似体を生成するステップと、
前記第２の組み合わせ近似体と、前記周辺物近似体とが干渉するか判定するステップと、
を実行する干渉判定方法。

（付記３）
インタフェース２８、記憶装置２６及び演算部２４を備える演算装置１４を用いて、複数の可動軸を有するロボットアーム１６が初期姿勢から目標姿勢に移動する動作経路上で、前記ロボットアーム１６の周辺に存在する周辺物と干渉する可能性を判定する干渉判定システム１０であって、
前記演算部２４は、
前記記憶装置２６に、前記ロボットアーム１６の形状を、所定の着目部位について多面体で近似したロボットデータを記憶させるステップと、
前記記憶装置２６に、前記周辺物の形状を近似した周辺物近似体のデータを記憶させるステップと、
前記インタフェース２８を用いて、前記初期姿勢及び前記目標姿勢を取得するステップと、
前記初期姿勢から前記目標姿勢へと移動する前記動作経路上における前記ロボットアーム１６の第１の姿勢と、前記第１の姿勢よりも、相対的に前記目標姿勢側の前記動作経路上における前記ロボットアーム１６の第２の姿勢と、前記第１の姿勢と前記第２の姿勢との間の中間姿勢と、を設定するステップと、
前記ロボットデータに基づいて、前記第１の姿勢、前記第２の姿勢及び前記中間姿勢における前記ロボットアーム１６の形状を、少なくとも一つの前記着目部位について前記多面体で近似した複数のロボット近似体を生成するステップと、
このステップで生成された複数の前記ロボット近似体を組み合わせて構成される第１の組み合わせ近似体を生成するステップと、
前記第１の組み合わせ近似体と、前記周辺物近似体とが干渉するか判定するステップと、
このステップにおいて干渉すると判定された場合は、
前記第１の組み合わせ近似体を構成する複数の前記ロボット近似体のうち、隣接する二つの前記ロボット近似体の間隔を示す量を算出し、所定値と比較するステップと、
前記間隔を示す量と前記所定値との比較結果に基づいて、前記第１の組み合わせ近似体よりも小さい組み合わせ近似体を生成するか否かを判断するステップと、
を実行する干渉判定システム。

（付記４）
インタフェース２８、記憶装置２６及び演算部２４を備える演算装置１４を用いて、複数の可動軸を有するロボットアーム１６が初期姿勢から目標姿勢に移動する動作経路上で、前記ロボットアーム１６の周辺に存在する周辺物と干渉する可能性を判定する干渉判定を前記演算装置１４に実行させるためのプログラムであって、
前記演算部２４に、
前記記憶装置２６に、前記ロボットアーム１６の形状を、所定の着目部位について多面体で近似したロボットデータを記憶させるステップと、
前記記憶装置２６に、前記周辺物の形状を近似した周辺物近似体のデータを記憶させるステップと、
前記インタフェース２８を用いて、前記初期姿勢及び前記目標姿勢を取得するステップと、
前記初期姿勢から前記目標姿勢へと移動する前記動作経路上における前記ロボットアーム１６の第１の姿勢と、前記第１の姿勢よりも、相対的に前記目標姿勢側の前記動作経路上における前記ロボットの第２の姿勢と、前記第１の姿勢と前記第２の姿勢との間の中間姿勢と、を設定するステップと、
前記ロボットデータに基づいて、前記第１の姿勢、前記第２の姿勢及び前記中間姿勢における前記ロボットの形状を、少なくとも一つの前記着目部位について前記多面体で近似した複数のロボット近似体を生成するステップと、
このステップで生成された複数の前記ロボット近似体を組み合わせて構成される第１の組み合わせ近似体を生成するステップと、
前記第１の組み合わせ近似体と、前記周辺物近似体とが干渉するか判定するステップと、
このステップにおいて干渉すると判定された場合は、
前記第１の組み合わせ近似体を構成する複数の前記ロボット近似体のうち、隣接する二つの前記ロボット近似体の間隔を示す量を算出し、所定値と比較するステップと、
前記間隔を示す量と前記所定値との比較結果に基づいて、前記第１の組み合わせ近似体よりも小さい組み合わせ近似体を生成するか否かを判断するステップと、
を実行させるプログラム。

１０…干渉判定システム、１２…入力部、１４…演算装置、１６…ロボットアーム、１８…モニタ、２０…出力部、２２…計算機、２４…演算部、２６…記憶装置、２８…インタフェース、ＢＬ-Ｌ５、Ｌ…リンク、ＤＬ…チェックデータリスト、Ｌ…リンク

Claims (9)

1. 取得部、記憶部及び演算部を備える演算装置を用いて、複数の可動軸を有するロボットが、初期姿勢から目標姿勢に移動する動作経路上で、前記ロボットの周辺に存在する周辺物と干渉する可能性を判定する方法であって、
   前記演算部は、
   前記記憶部に、前記ロボットの形状を、所定の着目部位について多面体で近似したロボットデータを記憶させるステップと、
   前記記憶部に、前記周辺物の形状を近似した周辺物近似体のデータを記憶させるステップと、
   前記取得部を用いて、前記初期姿勢及び前記目標姿勢を取得するステップと、
   前記初期姿勢から前記目標姿勢へと移動する前記動作経路上における前記ロボットの第１の姿勢と、前記第１の姿勢よりも、相対的に前記目標姿勢側の前記動作経路上における前記ロボットの第２の姿勢と、前記第１の姿勢と前記第２の姿勢との間の中間姿勢と、を設定するステップと、
   前記ロボットデータに基づいて、前記第１の姿勢、前記第２の姿勢及び前記中間姿勢における前記ロボットの形状を、前記着目部位について前記多面体で近似したロボット近似体を生成するステップと、
   このステップで生成された前記ロボット近似体を組み合わせて構成される第１の組み合わせ近似体を生成するステップと、
   前記第１の組み合わせ近似体と、前記周辺物近似体とが干渉するか判定するステップと、
   このステップにおいて干渉すると判定された場合は、
   前記第１の組み合わせ近似体を構成する複数の前記ロボット近似体のうち、隣接する二つの前記ロボット近似体の間隔を示す量を算出し、第１の所定値と比較するステップと、
   前記間隔を示す量と前記第１の所定値との比較結果に基づいて、前記第１の組み合わせ近似体よりも小さい組み合わせ近似体を生成するか否かを判断するステップと、
   を実行する干渉判定方法。
2. 前記演算部は、
   前記間隔を示す量が前記第１の所定値以上と判断された場合は、
   前記着目部位について、前記第１の姿勢、前記第２の姿勢及び前記中間姿勢に相当する複数の前記ロボット近似体の少なくとも二つを組み合わせて構成され、前記第１の組み合わせ近似体よりも小さい第２の組み合わせ近似体を生成するステップと、
   前記第２の組み合わせ近似体と、前記周辺物近似体とが干渉するか判定するステップと、
   を更に実行する請求項１に記載の干渉判定方法。
3. 前記演算部は、
   前記第２の組み合わせ近似体と、前記周辺物近似体とが干渉するか判定するステップにおいて干渉すると判定され、かつ、前記第２の組み合わせ近似体を構成する複数の前記ロボット近似体のうち、隣接する二つの前記ロボット近似体の間隔を示す量が前記第１の所定値以上の場合に、
   前記第１の姿勢、前記第２の姿勢及び前記中間姿勢に相当する複数の前記ロボット近似体の少なくとも二つを組み合わせて構成され、前記第（ｎ−１）の組み合わせ近似体よりも小さい第ｎの組み合わせ近似体を生成するステップと（ただし、ｎは３以上の整数）、
   前記第ｎの組み合わせ近似体と、前記周辺物近似体とが干渉するか判定するステップを、
   更に実行する請求項２に記載の干渉判定方法。
4. 前記演算部は、
   前記第ｎの組み合わせ近似体を構成する複数の前記ロボット近似体のうち、隣接する二つの前記ロボット近似体の間隔を示す量が、前記第１の所定値未満となるまで、ｎを１ずつ増加させながら、
   前記第ｎの組み合わせ近似体を生成するステップと、前記第ｎの組み合わせ近似体と前記周辺物近似体とが干渉するか判定するステップとを、 繰り返す請求項３に記載の干渉判定方法。
5. 前記第ｎの組み合わせ近似体を生成するステップは、
   前記第（ｎ−１）の組み合わせ近似体を構成する複数の前記ロボット近似体のうち、隣接する二つの前記ロボット近似体を選択するステップと、
   前記隣接する二つの前記ロボット近似体間の動作経路上の中間姿勢を新たに設定するステップと、
   新たに設定された前記中間姿勢に相当する前記ロボット近似体を生成するステップと、
   前記隣接する二つの前記ロボット近似体と、新たに設定された前記中間姿勢に相当する前記ロボット近似体と、を組み合わせて第ｎの組み合わせ近似体を生成するステップと、
   を含む請求項４に記載の干渉判定方法。
6. 前記第ｋの組み合わせ近似体（ｋは１以上の整数）と、前記周辺物近似体とが干渉するか判定するステップは、
   前記第ｋの組み合わせ近似体と前記周辺物近似体との距離を算出するステップと、
   前記距離と第２の所定値とを比較するステップと、
   を含む請求項１から５のいずれか一項に記載の干渉判定方法。
7. 演算部を備える演算装置を用いて、複数の可動軸を有するロボットが初期姿勢から目標姿勢に移動する動作経路上で、前記ロボットの周辺に存在する周辺物と干渉する可能性を判定する方法であって、
   前記演算部は、
   前記初期姿勢から前記目標姿勢へと移動する前記動作経路上における前記ロボットの第１の姿勢を特定するための複数の前記可動軸の回転角度を設定するステップと、
   前記第１の姿勢よりも前記目標姿勢側の前記動作経路上における前記ロボットの第２の姿勢を特定するための複数の前記可動軸の回転角度であって、前記第１の姿勢から前記第２の姿勢に変化する間の回転角度は、前記可動軸ごとに、単調増加又は単調減少する回転角度を、設定するステップと、
   前記第１の姿勢と前記第２の姿勢との間の少なくとも一つの中間姿勢を特定するために複数の前記可動軸の回転角度を示す情報を設定するステップと、
   前記ロボットの少なくとも一つの着目部位を多面体で近似したロボット近似体であって、前記第１の姿勢、前記第２の姿勢及び前記中間姿勢のそれぞれに対応した複数のロボット近似体を生成するステップと、
   このステップで生成された複数の前記ロボット近似体を組み合わせて構成される第１の組み合わせ近似体が、前記周辺物と干渉するか判断するステップと、
   このステップで干渉すると判断された場合は、複数の前記ロボット近似体を組み合わせて構成され、前記第１の組み合わせ近似体よりも小さい第２の組み合わせ近似体を生成するステップと、
   前記第２の組み合わせ近似体と、周辺物近似体とが干渉するか判定するステップと、
   を実行する干渉判定方法。
   
8. 取得部、記憶部及び演算部を備える演算装置を用いて、複数の可動軸を有するロボットが初期姿勢から目標姿勢に移動する動作経路上で、前記ロボットの周辺に存在する周辺物と干渉する可能性を判定する干渉判定システムであって、
   前記演算部は、
   前記記憶部に、前記ロボットの形状を、所定の着目部位について多面体で近似したロボットデータを記憶させるステップと、
   前記記憶部に、前記周辺物の形状を近似した周辺物近似体のデータを記憶させるステップと、
   前記取得部を用いて、前記初期姿勢及び前記目標姿勢を取得するステップと、
   前記初期姿勢から前記目標姿勢へと移動する前記動作経路上における前記ロボットの第１の姿勢と、前記第１の姿勢よりも、相対的に前記目標姿勢側の前記動作経路上における前記ロボットの第２の姿勢と、前記第１の姿勢と前記第２の姿勢との間の中間姿勢と、を設定するステップと、
   前記ロボットデータに基づいて、前記第１の姿勢、前記第２の姿勢及び前記中間姿勢における前記ロボットの形状を、少なくとも一つの前記着目部位について前記多面体で近似した複数のロボット近似体を生成するステップと、
   このステップで生成された前記ロボット近似体を組み合わせて構成される第１の組み合わせ近似体を生成するステップと、
   前記第１の組み合わせ近似体と、前記周辺物近似体とが干渉するか判定するステップと、
   このステップにおいて干渉すると判定された場合は、
   前記第１の組み合わせ近似体を構成する複数の前記ロボット近似体のうち、隣接する二つの前記ロボット近似体の間隔を示す量を算出し、第１の所定値と比較するステップと、
   前記間隔を示す量と前記第１の所定値との比較結果に基づいて、前記第１の組み合わせ近似体よりも小さい組み合わせ近似体を生成するか否かを判断するステップと、
   を実行する干渉判定システム。
9. 取得部、記憶部及び演算部を備える演算装置を用いて、複数の可動軸を有するロボットが初期姿勢から目標姿勢に移動する動作経路上で、前記ロボットの周辺に存在する周辺物と干渉する可能性を判定する干渉判定を前記演算装置に実行させるためのプログラムであって、
   前記演算部に、
   前記記憶部に、前記ロボットの形状を、所定の着目部位について、多面体で近似したロボットデータを記憶させるステップと、
   前記記憶部に、前記周辺物の形状を近似した周辺物近似体のデータを記憶させるステップと、
   前記取得部を用いて、前記初期姿勢及び前記目標姿勢を取得するステップと、
   前記初期姿勢から前記目標姿勢へと移動する前記動作経路上における前記ロボットの第１の姿勢と、前記第１の姿勢よりも、相対的に前記目標姿勢側の前記動作経路上における前記ロボットの第２の姿勢と、前記第１の姿勢と前記第２の姿勢との間の中間姿勢と、を設定するステップと、
   前記ロボットデータに基づいて、前記第１の姿勢、前記第２の姿勢及び前記中間姿勢における前記ロボットの形状を、少なくとも一つの前記着目部位について前記多面体で近似した複数のロボット近似体を生成するステップと、
   このステップで生成された前記ロボット近似体を組み合わせて構成される第１の組み合わせ近似体を生成するステップと、
   前記第１の組み合わせ近似体と、前記周辺物近似体とが干渉するか判定するステップと、
   このステップにおいて干渉すると判定された場合は、
   前記第１の組み合わせ近似体を構成する複数の前記ロボット近似体のうち、隣接する二つの前記ロボット近似体の間隔を示す量を算出し、第１の所定値と比較するステップと、
   前記間隔を示す量と前記第１の所定値との比較結果に基づいて、前記第１の組み合わせ近似体よりも小さい組み合わせ近似体を生成するか否かを判断するステップと、
   を実行させるプログラム。

Images