SEARCH
MENU

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

登尾 啓史大阪大学
福田 尚三大阪大学
有本 卓大阪大学

この論文は、ロボット研究開発アーカイブ「日本のロボット研究開発の歩み」掲載論文です。

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

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

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

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

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

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

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

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

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

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

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

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

動画


対応論文


登尾,福田,有本:オクトツリーを用いた高速干渉チェック法

日本ロボット学会誌,Vol.5,No.3,pp.189-198,June 1987

H.Noborio, S.Fukuda, and S.Arimoto:Fast Interference Check Method Using Octree Representation

Advanced Robotics, Vol. 3, No. 3, pp. 193-212, 1989.

H.Noborio, S.Fukuda, and S.Arimoto:A New Interference Check Algorithm Using Octree

Proceedings of the 1987 IEEE International Conference on Robotics and Automation, p.1480, March 1987.
Note: This paper may not be sold, recopied, or redistributed and is for personal use only. Any recopying, redistribution or resale of this paper is prohibited without a license from the IEEE (rights holder) to do so.

関連論文


[1] 登尾,福田,有本: BRepからオクトツリーへの変換アルゴリズムとその評価,情報処理学会論文誌,Vol.28,No.10,pp.1003-1012,October 1987

[2] 登尾,福田,有本: 複数枚の画像を用いて3次元物体を近似したオクトツリーを生成する一手法,情報処理学会論文誌,Vol.29,No.2,pp.178-189,Feb. 1988
[3] H.Noborio,S.Fukuda,S.Arimoto: Construction ofthe Octree Approximating Three-Dimensional Objects by Using Multiple Views, IEEE Trans. on Pattern Analysis and Machine Intelligence,Vol.PAMI-10,No.6,pp.769-782,Nov. 1988
[4] 登尾,畑,有本: オクトツリーを利用した3次元物体の最近点探索アルゴリズム,情報処理学会論文誌,Vol.30,No.3,pp.311-320,March 1989
[5] 登尾,有本: オクトツリーを利用したロボットと障害物の近接2点決定アルゴリズム,日本ロボット学会誌,Vol.7,No.3,pp.151-160,June 1989