Efficient parallel proximity queries and an application to highly complex motion planning problems with many narrow passages
Mainz: Univ. 2013 124 S.
Erscheinungsjahr: 2013
Publikationstyp: Buch (Dissertation)
Doi/URN: urn:nbn:de:hebis:77-34388
Geprüft | Bibliothek |
Inhaltszusammenfassung
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 sam...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.» weiterlesen» einklappen
Autoren
Klassifikation
DDC Sachgruppe:
Informatik