Efficient parallel proximity queries and an application to highly complex motion planning problems with many narrow passages

Abstract

In vielen Bereichen der industriellen Fertigung, wie zum Beispiel in der Automobilindustrie, wer- den digitale Versuchsmodelle (sog. digital mock-ups) eingesetzt, um die Entwicklung komplexer Maschinen m Ì oglichst gut durch Computersysteme unterstu Ì tzen zu k Ì onnen. Hierbei spielen Be- wegungsplanungsalgorithmen eine wichtige Rolle, um zu gew Ì ahrleisten, dass diese digitalen Pro- totypen auch kollisionsfrei zusammengesetzt werden k Ì onnen. In den letzten Jahrzehnten haben sich hier sampling-basierte Verfahren besonders bew Ì ahrt. Diese erzeugen eine große Anzahl von zuf Ì alligen Lagen fu Ì r das ein-/auszubauende Objekt und verwenden einen Kollisionserken- nungsmechanismus, um die einzelnen Lagen auf Gu Ì ltigkeit zu u Ì berpru Ì fen. Daher spielt die Kollisionserkennung eine wesentliche Rolle beim Design effizienter Bewegungsplanungsalgorith- men. Eine Schwierigkeit fu Ì r diese Klasse von Planern stellen sogenannte â narrow passagesâ dar, schmale Passagen also, die immer dort auftreten, wo die Bewegungsfreiheit der zu planenden Objekte stark eingeschr Ì ankt ist. An solchen Stellen kann es schwierig sein, eine ausreichende Anzahl von kollisionsfreien Samples zu finden. Es ist dann m Ì oglicherweise n Ì otig, ausgeklu Ì geltere Techniken einzusetzen, um eine gute Performance der Algorithmen zu erreichen.rnDie vorliegende Arbeit gliedert sich in zwei Teile: Im ersten Teil untersuchen wir parallele Kollisionserkennungsalgorithmen. Da wir auf eine Anwendung bei sampling-basierten Bewe- gungsplanern abzielen, w Ì ahlen wir hier eine Problemstellung, bei der wir stets die selben zwei Objekte, aber in einer großen Anzahl von unterschiedlichen Lagen auf Kollision testen. Wir im- plementieren und vergleichen verschiedene Verfahren, die auf Hu Ì llk Ì operhierarchien (BVHs) und hierarchische Grids als Beschleunigungsstrukturen zuru Ì ckgreifen. Alle beschriebenen Verfahren wurden auf mehreren CPU-Kernen parallelisiert. Daru Ì ber hinaus vergleichen wir verschiedene CUDA Kernels zur Durchfu Ì hrung BVH-basierter Kollisionstests auf der GPU. Neben einer un- terschiedlichen Verteilung der Arbeit auf die parallelen GPU Threads untersuchen wir hier die Auswirkung verschiedener Speicherzugriffsmuster auf die Performance der resultierenden Algo- rithmen. Weiter stellen wir eine Reihe von approximativen Kollisionstests vor, die auf den beschriebenen Verfahren basieren. Wenn eine geringere Genauigkeit der Tests tolerierbar ist, kann so eine weitere Verbesserung der Performance erzielt werden.rnIm zweiten Teil der Arbeit beschreiben wir einen von uns entworfenen parallelen, sampling- basierten Bewegungsplaner zur Behandlung hochkomplexer Probleme mit mehreren â narrow passagesâ . Das Verfahren arbeitet in zwei Phasen. Die grundlegende Idee ist hierbei, in der er- sten Planungsphase konzeptionell kleinere Fehler zuzulassen, um die Planungseffizienz zu erh Ì ohen und den resultierenden Pfad dann in einer zweiten Phase zu reparieren. Der hierzu in Phase I eingesetzte Planer basiert auf sogenannten Expansive Space Trees. Zus Ì atzlich haben wir den Planer mit einer Freidru Ì ckoperation ausgestattet, die es erlaubt, kleinere Kollisionen aufzul Ì osen und so die Effizienz in Bereichen mit eingeschr Ì ankter Bewegungsfreiheit zu erh Ì ohen. Optional erlaubt unsere Implementierung den Einsatz von approximativen Kollisionstests. Dies setzt die Genauigkeit der ersten Planungsphase weiter herab, fu Ì hrt aber auch zu einer weiteren Perfor- mancesteigerung. Die aus Phase I resultierenden Bewegungspfade sind dann unter Umst Ì anden nicht komplett kollisionsfrei. Um diese Pfade zu reparieren, haben wir einen neuartigen Pla- nungsalgorithmus entworfen, der lokal beschr Ì ankt auf eine kleine Umgebung um den bestehenden Pfad einen neuen, kollisionsfreien Bewegungspfad plant.rnWir haben den beschriebenen Algorithmus mit einer Klasse von neuen, schwierigen Metall- Puzzlen getestet, die zum Teil mehrere â narrow passagesâ aufweisen. Unseres Wissens nach ist eine Sammlung vergleichbar komplexer Benchmarks nicht Ì offentlich zug Ì anglich und wir fan- den auch keine Beschreibung von vergleichbar komplexen Benchmarks in der Motion-Planning Literatur.

In industrial manufacturing, like the automotive industry, digital mock-ups are used to design complex machinery with the help of computer systems. In this field, motion planning algorithms play an important role to ensure the (de-)composability of the digital prototypes. In the last decades, sampling-based motion planning algorithms have shown themselves to be practical in this application. In order to construct a (dis-)assembly path for a virtual 3D object, these algorithms generate a high number of different placements for the object and validate these positions by utilizing a collision detection routine. Hence, collision detection is a very important sub-task in sampling-based motion planning and an efficient collision detection routine is essential to every sampling-based planner. One of the main difficulties for these planners results from â narrow passagesâ that appear whenever the movements of the assembled component are highly restricted. It can then be difficult to find a sufficient number of collision free samples and more sophisticated techniques might be required to enhance the performance of the algorithm.rnThe present work is organized in two parts: In the first part, we analyze parallel collision detection algorithms. Focusing on the application to sampling-based motion planning, we formulate the a basic collision query as testing the same two rigid body objects in a number of different relative placements. We implement and compare different approaches based on bounding volume hierarchies and hierarchical grids that are executed in parallel on multiple CPU cores. Besides, we describe the design of different parallel CUDA kernels that perform collision tests based on bounding volume hierarchies. In addition to different distributions of the work amongst the available GPU threads, we analyze the effect of different memory access patterns on the performance of our CUDA kernels. Furthermore, we propose to improve the performance of the algorithms at the expense of their accuracy and analyze a family of different approximate collision tests.rnIn the second part, we describe a novel parallel, sampling-based motion planner that is especially suited for complex motion planning problems with many narrow passages. The algorithm works in two phases. The basic idea is to conceptually allow small object interpenetrations and not to enforce a high accuracy in the first planning phase. We describe a non-conservative motion planner that is based on an Expansive Space Tree. The approach uses an iterative sample retraction mechanism to actively improve the performance in highly restricted environments. To further improve the performance, we optionally allow to apply approximate collision tests in the first planning phase. This results in a disassembly path that is not completely collision free. In the second phase, we repair this path with a new type of sampling-based motion planner that locally re-plans a valid path in close proximity to the non-conservative solution.rnTo benchmark our new algorithm and show its strength for highly complex motion planning problems with many narrow passages, we have modeled and solved a new family of very complex metal puzzles in addition to the well known alpha puzzle. To the best of our knowledge, there is no comparably complex benchmark set of rigid body motion planning problems publicly available, neither have comparable benchmarks been described in the motion planning literature.