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.

Informationsstrukturen der protokollbasierten Medizin

Die protokollbasierte Medizin stellt einen interdisziplin��ren Brennpunkt der Informatik dar. Als besonderer Ausschnitt der medizinischen Teilgebiete erlaubt sie die relativ formale Spezifikation von Prozessen in den drei Bereichen der Pr��vention, Diagnose und Therapie.Letzterer wurde immer besonders fokussiert und gilt seit jeher im Rahmen klinischer Studien als Projektionsfl��che f��r informationstechnologische Konzepte. Die Euphorie der fr��hen Jahre ern��chtert sich jedoch bei jeder Bilanz. Nur sehr wenige der unz��hlbaren Projekte haben ihre Routine in der allt��glichen Praxis gefunden. Die meisten Vorhaben sind an der Illusion der vollst��ndigen Berechenbarkeit medizinischer Arbeitsabl��ufe gescheitert. Die traditionelle Sichtweise der klinischen Praxis beruht auf einer blockorientierten Vorstellung des Therapieausf��hrungsprozesses. Sie entsteht durch seine Zerlegung in einzelne Therapiezweige, welche aus vordefinierten Bl��cken zusammengesetzt sind. Diese k��nnen sequentiell oder parallel ausgef��hrt werden und sind selbst zusammengesetzt aus jeweils einer Menge von Elementen,welche die Aktivit��ten der untersten Ebene darstellen. Das blockorientierte Aufbaumodell wird erg��nzt durch ein regelorientiertes Ablaufmodell. Ein komplexes Regelwerk bestimmt Bedingungen f��r die zeitlichen und logischen Abh��ngigkeiten der Bl��cke, deren Anordnung durch den Ausf��hrungsproze�� gebildet wird. Die Modellierung der Therapieausf��hrung steht zun��chst vor der grunds��tzlichen Frage, inwieweit die traditionelle Sichtweise f��r eine interne Repr��sentation geeignet ist. Das ��bergeordnete Ziel besteht in der Integration der unterschiedlichen Ebenen der Therapiespezifikation. Dazu geh��rt nicht nur die strukturelle Komponente, sondern vorallem die Ablaufkomponente. Ein geeignetes Regelmodell ist erforderlich, welches den spezifischen Bed��rfnissen der Therapie��berwachung gerecht wird. Die zentrale Aufgabe besteht darin, diese unterschiedlichen Ebenen zusammenzuf��hren. Eine sinnvolle Alternative zur traditionellen Sichtweise liefert das zustandsorientierte Modell des Therapieausf��hrungsprozesses. Das zustandsorientierte Modell beruht auf der Sichtweise, da�� der gesamte Therapieausf��hrungsproze�� letztendlich eine lineare Folge von Zust��nden beschreibt, wobei jeder Zustands��bergang durch ein Ereignis eingeleitet wird, an bestimmte Bedingungen gekn��pft ist und bestimmte Aktionen ausl��sen kann. Die Parallelit��t des blockorientierten Modells tritt in den Hintergrund, denn die Menge der durchzuf��hrenden Ma��nahmen sind lediglich Eigenschaften der Zust��nde und keine strukturellen Elemente der Ablaufspezifikation. Zu jedem Zeitpunkt ist genau ein Zustand aktiv, und er repr��sentiert eine von endlich vielen klinischen Situationen, mit all ihren spezifischen Aktivit��ten und Ausf��hrungsregeln. Die Vorteile des zustandsorientierten Modells liegen in der Integration. Die Grundstruktur verbindet die statische Darstellung der m��glichen Phasenanordnungen mit der dynamischen Ausf��hrung aktiver Regeln. Die urspr��nglichen Inhalte des blockorientierten Modells werden als gew��hnliche Eigenschaften der Zust��nde reproduziert und stellen damit nur einen Spezialfall der zustandsbezogenen Sicht dar.Weitere M��glichkeiten f��r die Anreicherung der Zust��nde mit zus��tzlichen Details sind denkbar wie sinnvoll. Die Grundstruktur bleibt bei jeder Erweiterung jedoch die gleiche. Es ergibt sich ein wiederverwendbares Grundger��st,ein gemeinsamer Nenner f��r die Erf��llung der ��berwachungsaufgabe.

COBAMOS: Endnutzerprogrammierung auf Basis nachrichtenbasierter Komponentenvernetzung

Die Aufgabenstellung, welche dieser Dissertation zugrunde liegt, l��sst sich kurz als die Untersuchung von komponentenbasierten Konzepten zum Einsatz in der Softwareentwicklung durch Endanwender beschreiben. In den letzten 20 bis 30 Jahren hat sich das technische Umfeld, in dem ein Gro��teil der Arbeitnehmer seine t��glichen Aufgaben verrichtet, grundlegend ver��ndert. Der Computer, fr��her in Form eines Gro��rechners ausschlie��lich die Dom��ne von Spezialisten, ist nun ein selbstverst��ndlicher Bestandteil der t��glichen Arbeit. Der Umgang mit Anwendungsprogrammen, die dem Nutzer erlauben in einem gewissen Rahmen neue, eigene Funktionalit��t zu definieren, ist in vielen Bereichen so selbstverst��ndlich, dass viele dieser T��tigkeiten nicht bewusst als Programmieren wahrgenommen werden. Da diese Nutzer nicht notwendigerweise in der Entwicklung von Software ausgebildet sind, ben��tigen sie entsprechende Unterst��tzung bei diesen T��tigkeiten. Dies macht deutlich, welche praktische Relevanz die Untersuchungen in diesem Bereich haben. Zur Erstellung eines Programmiersystems f��r Endanwender wird zun��chst ein flexibler Anwendungsrahmen entwickelt, welcher sich als Basis zur Erstellung solcher Systeme eignet. In Softwareprojekten sind sich ��ndernde Anforderungen und daraus resultierende Notwendigkeiten ein wichtiger Aspekt. Dies wird im Entwurf des Frameworks durch Konzepte zur Bereitstellung von wieder verwendbarer Funktionalit��t durch das Framework und M��glichkeiten zur Anpassung und Erweiterung der vorhandenen Funktionalit��t ber��cksichtigt. Hier ist zum einen der Einsatz einer serviceorientierten Architektur innerhalb der Anwendung und zum anderen eine komponentenorientierte Variante des Kommando-Musters zu nennen. Zum anderen wird ein Konzept zur Kapselung von Endnutzerprogrammiermodellen in Komponenten erarbeitet. Dieser Ansatz erm��glicht es, unterschiedliche Modelle als Grundlage der entworfenen Entwicklungsumgebung zu verwenden. Im weiteren Verlauf der Arbeit wird ein Programmiermodell entworfen und unter Verwendung des zuvor genannten Frameworks implementiert. Damit dieses zur Nutzung durch Endanwender geeignet ist, ist eine Anhebung der zur Beschreibung eines Softwaresystems verwendeten Abstraktionsebene notwendig. Dies wird durch die Verwendung von Komponenten und einem nachrichtenbasierten Kompositionsmechanismus erreicht. Die vorgenommene Realisierung ist dabei noch nicht auf konkrete Anwendungsfamilien bezogen, diese Anpassungen erfolgen in einem weiteren Schritt f��r zwei unterschiedliche Anwendungsbereiche.

Exact computation of the adjacency graph of an arrangement of quadrics

Pr��sentiert wird ein vollst��ndiger, exakter und effizienter Algorithmus zur Berechnung des Nachbarschaftsgraphen eines Arrangements von Quadriken (Algebraische Fl��chen vom Grad 2). Dies ist ein wichtiger Schritt auf dem Weg zur Berechnung des vollen 3D Arrangements. Dabei greifen wir auf eine bereits existierende Implementierung zur Berechnung der exakten Parametrisierung der Schnittkurve von zwei Quadriken zur��ck. Somit ist es m��glich, die exakten Parameterwerte der Schnittpunkte zu bestimmen, diese entlang der Kurven zu sortieren und den Nachbarschaftsgraphen zu berechnen. Wir bezeichnen unsere Implementierung als vollst��ndig, da sie auch die Behandlung aller Sonderf��lle wie singul��rer oder tangentialer Schnittpunkte einschlie��t. Sie ist exakt, da immer das mathematisch korrekte Ergebnis berechnet wird. Und schlie��lich bezeichnen wir unsere Implementierung als effizient, da sie im Vergleich mit dem einzigen bisher implementierten Ansatz gut abschneidet. Implementiert wurde unser Ansatz im Rahmen des Projektes EXACUS. Das zentrale Ziel von EXACUS ist es, einen Prototypen eines zuverl��ssigen und leistungsf��higen CAD Geometriekerns zu entwickeln. Obwohl wir das Design unserer Bibliothek als prototypisch bezeichnen, legen wir dennoch gr����ten Wert auf Vollst��ndigkeit, Exaktheit, Effizienz, Dokumentation und Wiederverwendbarkeit. ��ber den eigentlich Beitrag zu EXACUS hinaus, hatte der hier vorgestellte Ansatz durch seine besonderen Anforderungen auch wesentlichen Einfluss auf grundlegende Teile von EXACUS. Im Besonderen hat diese Arbeit zur generischen Unterst��tzung der Zahlentypen und der Verwendung modularer Methoden innerhalb von EXACUS beigetragen. Im Rahmen der derzeitigen Integration von EXACUS in CGAL wurden diese Teile bereits erfolgreich in ausgereifte CGAL Pakete weiterentwickelt.

Lernen mit einer Hybride aus Lernendem Klassifizierendem System und Selbstorganisierender Karte

Im Forschungsgebiet der K��nstlichen Intelligenz, insbesondere im Bereich des maschinellen Lernens, hat sich eine ganze Reihe von Verfahren etabliert, die von biologischen Vorbildern inspiriert sind. Die prominentesten Vertreter derartiger Verfahren sind zum einen Evolution��re Algorithmen, zum anderen K��nstliche Neuronale Netze. Die vorliegende Arbeit befasst sich mit der Entwicklung eines Systems zum maschinellen Lernen, das Charakteristika beider Paradigmen in sich vereint: Das Hybride Lernende Klassifizierende System (HCS) wird basierend auf dem reellwertig kodierten eXtended Learning Classifier System (XCS), das als Lernmechanismus einen Genetischen Algorithmus enth��lt, und dem Wachsenden Neuralen Gas (GNG) entwickelt. Wie das XCS evolviert auch das HCS mit Hilfe eines Genetischen Algorithmus eine Population von Klassifizierern - das sind Regeln der Form [WENN Bedingung DANN Aktion], wobei die Bedingung angibt, in welchem Bereich des Zustandsraumes eines Lernproblems ein Klassifizierer anwendbar ist. Beim XCS spezifiziert die Bedingung in der Regel einen achsenparallelen Hyperquader, was oftmals keine angemessene Unterteilung des Zustandsraumes erlaubt. Beim HCS hingegen werden die Bedingungen der Klassifizierer durch Gewichtsvektoren beschrieben, wie die Neuronen des GNG sie besitzen. Jeder Klassifizierer ist anwendbar in seiner Zelle der durch die Population des HCS induzierten Voronoizerlegung des Zustandsraumes, dieser kann also flexibler unterteilt werden als beim XCS. Die Verwendung von Gewichtsvektoren erm��glicht ferner, einen vom Neuronenadaptationsverfahren des GNG abgeleiteten Mechanismus als zweites Lernverfahren neben dem Genetischen Algorithmus einzusetzen. W��hrend das Lernen beim XCS rein evolution��r erfolgt, also nur durch Erzeugen neuer Klassifizierer, erm��glicht dies dem HCS, bereits vorhandene Klassifizierer anzupassen und zu verbessern. Zur Evaluation des HCS werden mit diesem verschiedene Lern-Experimente durchgef��hrt. Die Leistungsf��higkeit des Ansatzes wird in einer Reihe von Lernproblemen aus den Bereichen der Klassifikation, der Funktionsapproximation und des Lernens von Aktionen in einer interaktiven Lernumgebung unter Beweis gestellt.

Efficient certification of feasibility and objective value of linear programs and its applications

The use of linear programming in various areas has increased with the significant improvement of specialized solvers. Linear programs are used as such to model practical problems, or as subroutines in algorithms such as formal proofs or branch-and-cut frameworks. In many situations a certified answer is needed, for example the guarantee that the linear program is feasible or infeasible, or a provably safe bound on its objective value. Most of the available solvers work with floating-point arithmetic and are thus subject to its shortcomings such as rounding errors or underflow, therefore they can deliver incorrect answers. While adequate for some applications, this is unacceptable for critical applications like flight controlling or nuclear plant management due to the potential catastrophic consequences. We propose a method that gives a certified answer whether a linear program is feasible or infeasible, or returns unknown'. The advantage of our method is that it is reasonably fast and rarely answers unknown'. It works by computing a safe solution that is in some way the best possible in the relative interior of the feasible set. To certify the relative interior, we employ exact arithmetic, whose use is nevertheless limited in general to critical places, allowing us to rnremain computationally efficient. Moreover, when certain conditions are fulfilled, our method is able to deliver a provable bound on the objective value of the linear program. We test our algorithm on typical benchmark sets and obtain higher rates of success compared to previous approaches for this problem, while keeping the running times acceptably small. The computed objective value bounds are in most of the cases very close to the known exact objective values. We prove the usability of the method we developed by additionally employing a variant of it in a different scenario, namely to improve the results of a Satisfiability Modulo Theories solver. Our method is used as a black box in the nodes of a branch-and-bound tree to implement conflict learning based on the certificate of infeasibility for linear programs consisting of subsets of linear constraints. The generated conflict clauses are in general small and give good rnprospects for reducing the search space. Compared to other methods we obtain significant improvements in the running time, especially on the large instances.

Optimized scheduling in real-time environments with column generation

Im Bereich sicherheitsrelevanter eingebetteter Systeme stellt sich der Designprozess von Anwendungen als sehr komplex dar. Entsprechend einer gegebenen Hardwarearchitektur lassen sich Steuerger��te aufr��sten, um alle bestehenden Prozesse und Signale p��nktlich auszuf��hren. Die zeitlichen Anforderungen sind strikt und m��ssen in jeder periodischen Wiederkehr der Prozesse erf��llt sein, da die Sicherstellung der parallelen Ausf��hrung von gr����ter Bedeutung ist. Existierende Ans��tze k��nnen schnell Designalternativen berechnen, aber sie gew��hrleisten nicht, dass die Kosten f��r die n��tigen Hardware��nderungen minimal sind. Wir stellen einen Ansatz vor, der kostenminimale L��sungen f��r das Problem berechnet, die alle zeitlichen Bedingungen erf��llen. Unser Algorithmus verwendet Lineare Programmierung mit Spaltengenerierung, eingebettet in eine Baumstruktur, um untere und obere Schranken w��hrend des Optimierungsprozesses bereitzustellen. Die komplexen Randbedingungen zur Gew��hrleistung der periodischen Ausf��hrung verlagern sich durch eine Zerlegung des Hauptproblems in unabh��ngige Unterprobleme, die als ganzzahlige lineare Programme formuliert sind. Sowohl die Analysen zur Prozessausf��hrung als auch die Methoden zur Signal��bertragung werden untersucht und linearisierte Darstellungen angegeben. Des Weiteren pr��sentieren wir eine neue Formulierung f��r die Ausf��hrung mit fixierten Priorit��ten, die zus��tzlich Prozessantwortzeiten im schlimmsten anzunehmenden Fall berechnet, welche f��r Szenarien n��tig sind, in denen zeitliche Bedingungen an Teilmengen von Prozessen und Signalen gegeben sind. Wir weisen die Anwendbarkeit unserer Methoden durch die Analyse von Instanzen nach, welche Prozessstrukturen aus realen Anwendungen enthalten. Unsere Ergebnisse zeigen, dass untere Schranken schnell berechnet werden k��nnen, um die Optimalit��t von heuristischen L��sungen zu beweisen. Wenn wir optimale L��sungen mit Antwortzeiten liefern, stellt sich unsere neue Formulierung in der Laufzeitanalyse vorteilhaft gegen��ber anderen Ans��tzen dar. Die besten Resultate werden mit einem hybriden Ansatz erzielt, der heuristische Startl��sungen, eine Vorverarbeitung und eine heuristische mit einer kurzen nachfolgenden exakten Berechnungsphase verbindet.

Efficient subsequence alignment of time series

Zeitreihen sind allgegenw��rtig. Die Erfassung und Verarbeitung kontinuierlich gemessener Daten ist in allen Bereichen der Naturwissenschaften, Medizin und Finanzwelt vertreten. Das enorme Anwachsen aufgezeichneter Datenmengen, sei es durch automatisierte Monitoring-Systeme oder integrierte Sensoren, bedarf au��erordentlich schneller Algorithmen in Theorie und Praxis. Infolgedessen besch��ftigt sich diese Arbeit mit der effizienten Berechnung von Teilsequenzalignments. Komplexe Algorithmen wie z.B. Anomaliedetektion, Motivfabfrage oder die un��berwachte Extraktion von prototypischen Bausteinen in Zeitreihen machen exzessiven Gebrauch von diesen Alignments. Darin begr��ndet sich der Bedarf nach schnellen Implementierungen. Diese Arbeit untergliedert sich in drei Ans��tze, die sich dieser Herausforderung widmen. Das umfasst vier Alignierungsalgorithmen und ihre Parallelisierung auf CUDA-f��higer Hardware, einen Algorithmus zur Segmentierung von Datenstr��men und eine einheitliche Behandlung von Liegruppen-wertigen Zeitreihen.rnrnDer erste Beitrag ist eine vollst��ndige CUDA-Portierung der UCR-Suite, die weltf��hrende Implementierung von Teilsequenzalignierung. Das umfasst ein neues Berechnungsschema zur Ermittlung lokaler Alignierungsg��ten unter Verwendung z-normierten euklidischen Abstands, welches auf jeder parallelen Hardware mit Unterst��tzung f��r schnelle Fouriertransformation einsetzbar ist. Des Weiteren geben wir eine SIMT-vertr��gliche Umsetzung der Lower-Bound-Kaskade der UCR-Suite zur effizienten Berechnung lokaler Alignierungsg��ten unter Dynamic Time Warping an. Beide CUDA-Implementierungen erm��glichen eine um ein bis zwei Gr����enordnungen schnellere Berechnung als etablierte Methoden.rnrnAls zweites untersuchen wir zwei Linearzeit-Approximierungen f��r das elastische Alignment von Teilsequenzen. Auf der einen Seite behandeln wir ein SIMT-vertr��gliches Relaxierungschema f��r Greedy DTW und seine effiziente CUDA-Parallelisierung. Auf der anderen Seite f��hren wir ein neues lokales Abstandsma�� ein, den Gliding Elastic Match (GEM), welches mit der gleichen asymptotischen Zeitkomplexit��t wie Greedy DTW berechnet werden kann, jedoch eine vollst��ndige Relaxierung der Penalty-Matrix bietet. Weitere Verbesserungen umfassen Invarianz gegen Trends auf der Messachse und uniforme Skalierung auf der Zeitachse. Des Weiteren wird eine Erweiterung von GEM zur Multi-Shape-Segmentierung diskutiert und auf Bewegungsdaten evaluiert. Beide CUDA-Parallelisierung verzeichnen Laufzeitverbesserungen um bis zu zwei Gr����enordnungen.rnrnDie Behandlung von Zeitreihen beschr��nkt sich in der Literatur in der Regel auf reellwertige Messdaten. Der dritte Beitrag umfasst eine einheitliche Methode zur Behandlung von Liegruppen-wertigen Zeitreihen. Darauf aufbauend werden Distanzma��e auf der Rotationsgruppe SO(3) und auf der euklidischen Gruppe SE(3) behandelt. Des Weiteren werden speichereffiziente Darstellungen und gruppenkompatible Erweiterungen elastischer Ma��e diskutiert.