日本のロボット研究の歩みHistory of Robotics Research and Development of Japan1987Integration, Intelligence, etc.〈インテグレーション・知能ほか〉階層型ソリッドモデルを用いて物体間の衝突を高速にチェックするアルゴリズム

コンピュータグラフィックスの技術を利用すると，現実の世界をシミュレートしたり，仮想の世界を新しく創り出したりできる．このため，ロボット工学でも初期のころから，この技術を用いてロボットの動作を可視化してきたが，最近では動力学を含んだダイナミックアニメーション，および奥行きを感じるためのヘッドマウンティッドディスプレイ(HMD)，そしてハップティックスを介しての触覚や力覚のバーチャルリアリティ技術などとも融合し，よりリアルに３次元世界を表現できるようになってきた．

これらの分野では，ロボットのような動物体どうし，および動物体と障害物のような静物体との接触や衝突を早く検出することが不可欠である．そして，この高速化手法の一つに｢Bounding Box｣と呼ばれるラフチェック法がある．これは，個々の物体を立方体や直方体，または球といったプリミティブで取り囲む．そして，物体どうしの干渉を取り囲むプリミティブどうしの干渉で調べる．そして，プリミティブどうしが干渉するときのみ実際の物体どうしの干渉を調べる．この｢Bounding Box｣というラフチェックを３次元空間のすべての静物体と任意の動物体に対して統一的に施せるのが，著者らが提案した｢オクトツリーを用いた高速干渉チェック法｣であり，世界的にも初期の提案である．

このアルゴリズムの振る舞いを，｢オクトツリーを用いた干渉チェック法(動画)｣に示す.この動画では，障害物環境は黄色，ロボット・マニピュレータは緑色で表示されている．そして，ロボットが障害物に接近したら，それらが共に存在するキューブが橙色で表示され，衝突してしまったらその面が青色で表示される．

このあと，これに類する研究は多数発表され，あるものは商用のソリッドモデラに採用されたり，別のものは物体を幾何学的に階層化するモデルHierarchy of Oriented Bounding Boxes (OBB Trees)などへと発展していった．これらの階層モデルを用いた干渉チェックの要点は，干渉が無いほとんどの領域をラフチェックで見逃し，本当に干渉が起こっている領域を絞り込んで集中的に調べることにある．

最後に，｢オクトツリーを用いた高速干渉チェック法｣と関連する研究について紹介する．まず，３次元空間のオクトツリーを生成するため，以下の２種類の方法を開発した．

●コンピュータグラフィックスにおいて最も一般的なソリッドモデルであるB-Reps.(Boundary Representation)をオクトツリーに変換するアルゴリズム[1]．

このアルゴリズムの振る舞いは，｢オクトツリーの作成方法(動画)｣に示しています．この動画では，まず直方体のB-Reps.で障害物環境を定義します.次に，構築するオクトツリーの最大レベルとして３を入力します．さらに，最大レベルのノード属性のうち，“SURFACE”(B-Reps.の面を含むノード)，“EDGE”(B-Reps.の辺を含むノード)，“VERTEX”(B-Reps.の頂点を含むノード)のうちから描画したいものを選択します．ここでは，すべてを表示したいので“ALL”を入力しました(aviファイルに圧縮したため部分的に“EDGE”を選んでいるように見える場面があります).これにより，おのおのの属性のノードは，緑色，青色，白色のキューブとして描写されました．同様に，オクトツリーの最大レベルを５とし，すべてのノードを表示させました．最後に，多数のB-Reps.で複雑な環境を定義します.そして，オクトツリーの最大レベルを５として，すべてのノードを表示させました．このように，障害物環境をB-Reps．の集合で与え，オクトツリーの最大レベルを入力すると，全体環境を表現するオクトツリーが柔軟に作成されます．

●錐体相貫法を利用して複数枚の画像からオクトツリーを作成するアルゴリズム[2],[3]．

また，オクトツリーを用いてロボットの経路を計画する基礎としては，

○３次元のコンフィギュレーション空間を考えたとき，点ロボットから最も近いコンフィギュレーション空間障害物の最近点を決定するアルゴリズム[4]．

○作業座標系としての３次元空間を考えたとき，ロボットと障害物の近接２点を高速に決定するアルゴリズム[5]．

がある．これらとポテンシャル法を融合すると，ロボットが障害物を回避する動作を自動的に作り出せる．