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

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.

Design of cell adhesive and angiogenic titanium surfaces for cellular stimulation

Die Förderung der Zelladhäsion durch sogenannte biomimetische Oberflächen wird in der Medizin als vielversprechender Ansatz gesehen, um Komplikationen wie z. B. Fremdkörperreaktionen nach der Implantation entgegenzuwirken. Neben der Immobilisierung einzelner Biomoleküle wie z. B. dem RGD-Peptid, Proteinen und Wachstumsfaktoren auf verschiedenen Materialien, konzentriert man sich derzeit in der Forschung auf die Co-Immobilisierung zweier Moleküle gleichzeitig. Hierbei werden die funktionellen Gruppen z. B. von Kollagen unter Verwendung von nur einer Kopplungschemie verwendet, wodurch die Kopplungseffizienz der einzelnen Komponenten nur begrenzt kontrollierbar ist. Das Ziel der vorliegenden Arbeit war die Entwicklung eines Immobilisierungsverfahrens, welches die unabhängige Kopplung zweier Faktoren kontrolliert ermöglicht. Dabei sollten exemplarisch das adhäsionsfördernde RGD-Peptid (Arginin-Glycin-Asparaginsäure) zusammen mit dem Wachstumsfaktor VEGF (Vascular Endothelial Growth Factor) auf Titan gebunden werden. In weiteren Experimenten sollten dann die pro-adhäsiven Faktoren Fibronektin, Kollagen, Laminin und Osteopontin immobilisiert und untersucht werden. rnDie Aminofunktionalisierung von Titan durch plasma polymerisierte Allylaminschichten wurde als Grundlage für die Entwicklung des nasschemischen Co-immobilisierungsverfahren verwendet. Für eine unabhängige und getrennte Anbindung der verschiedenen Biomoleküle stand in diesem Zusammenhang die Entwicklung eines geeigneten Crosslinker Systems im Vordergrund. Die Oberflächencharakterisierung der entwickelten Oberflächen erfolgte mittels Infrarot Spektroskopie, Surface Plasmon Resonance Spektroskopie (SPR), Kontaktwinkelmessungen, Step Profiling und X-Ray Photoelectron Spektroskopie (XPS). Zur Analyse der Anbindungsprozesse in Echtzeit wurden SPR-Kinetik Messungen durchgeführt. Die biologische Funktionalität der modifizierten Oberflächen wurde in vitro an Endothelzellen (HUVECs) und Osteoblasten (HOBs) und in vivo in einem Tiermodell-System an der Tibia von Kaninchen untersucht.rnDie Ergebnisse zeigen, dass alle genannten Biomoleküle sowohl einzeln auf Titan kovalent gekoppelt als auch am Bespiel von RGD und VEGF in einem getrennten Zwei-Schritt-Verfahren co-immobilisiert werden können. Des Weiteren wurde die biologische Funktionalität der gebundenen Faktoren nachgewiesen. Im Falle der RGD modifizierten Oberflächen wurde nach 7 Tagen eine geförderte Zelladhäsion von HUVECs mit einer signifikant erhöhten Zellbesiedlungsdichte von 28,5 % (p<0,05) gezeigt, wohingegen auf reinem Titan Werte von nur 13 % beobachtet wurden. Sowohl VEGF als auch RGD/VEGF modifizierte Proben wiesen im Vergleich zu Titan schon nach 24 Stunden eine geförderte Zelladhäsion und eine signifikant erhöhte Zellbesiedlungsdichte auf. Bei einer Besiedlung von 7,4 % auf Titan, zeigten VEGF modifizierte Proben mit 32,3 % (p<0,001) eine deutlichere Wirkung auf HUVECs als RGD/VEGF modifizierte Proben mit 13,2 % (p<0,01). Die pro-adhäsiven Faktoren zeigten eine deutliche Stimulation der Zelladhäsion von HUVECs und HOBs im Vergleich zu reinem Titan. Die deutlich höchsten Besiedlungsdichten von HUVECs konnten auf Fibronektin mit 44,6 % (p<0,001) und Kollagen mit 39,9 % (p<0,001) nach 24 Stunden beobachtet werden. Laminin zeigte keine und Osteopontin nur eine sehr geringe Wirkung auf HUVECs. Bei Osteoblasten konnten signifikant erhöhte Besiedlungsdichten im Falle aller pro-adhäsiven Faktoren beobachtet werden, jedoch wurden die höchsten Werte nach 7 Tagen auf Kollagen mit 90,6 % (p<0,001) und Laminin mit 86,5 % (p<0,001) im Vergleich zu Titan mit 32,3 % beobachtet. Die Auswertung der Tierexperimente ergab, dass die VEGF modifizierten Osteosyntheseplatten, im Vergleich zu den reinen Titankontrollen, eine gesteigerte Knochenneubildung auslösten. Eine solche Wirkung konnte für RGD/VEGF modifizierte Implantate nicht beobachtet werden. rnInsgesamt konnte gezeigt werden, dass mittels plasmapolymerisierten Allylamin Schichten die genannten Biomoleküle sowohl einzeln gebunden als auch getrennt und kontrolliert co-immobilisiert werden können. Des Weiteren konnte eine biologische Funktionalität für alle Faktoren nach erfolgter Kopplung in vitro gezeigt werden. Wider Erwarten konnte jedoch kein zusätzlicher biologischer Effekt durch die Co-immobilisierung von RGD und VEGF im Vergleich zu den einzeln immobilisierten Faktoren gezeigt werden. Um zu einer klinischen Anwendung zu gelangen, ist es nun notwendig, das entwickelte Verfahren in Bezug auf die immobilisierten Mengen der verschiedenen Faktoren hin zu optimieren. rn