Wintersemester 2011/12

Daniel Jung, University of Bonn

March 14, 2012, 2:00 p.m., F1.110

Multi-Agenten Exploration von Bäumen

Die Aufgabe ist die online Exploration graphentheoretischer Bäume unter Verwendung von k Robotern (Agenten). Wobei Exploration hier bedeutet, daß jeder Baumknoten von einem Roboter besucht werden muß. Es existiere hierbei keine globale Steuerung. D.h., die Roboter führen den Explorationsalgorithmus autonom aus. Die Roboter unterliegen einer Kommunikationsform (hier: globale und lokale Kommunikation) die angibt, ob sie über beliebige Abstände hinweg oder beispielsweise nur während des Besuchs desselben Knotens miteinander kommunizieren können. Als Kostenmodell soll hier das Zeitmodell herangezogen werden: Für jeden Kantenbesuch wird eine Zeiteinheit berechnet. Da hier mehrere Agenten gleichzeitig explorieren, werden deren simultane Bewegungen jedoch nur einfach angerechnet!

Die Diplomarbeit beschäftigt sich nun mit oberen und unteren Schranken des kompetitiven Faktors bei dieser online Multi-Agenten Exploration von Bäumen. Zur Berechnung kompetitiver Faktoren wird die Komplexität einer optimalen Offlinelösung für das betrachtete Problem benötigt. Hiermit beginnt die Diplomarbeit: Nach der Präsentation eines Beweises der NP-Schwere des Problems, wird ein 4-Approximationsalgorithmus der optimalen Offlinelösung vorgestellt.

Die für das Onlineproblem bisher besten bekannten und nur von k abhängigen allgemeinen unteren und oberen Schranken Omega(log(k)/loglog(k)) bzw. O(k/log(k)) des kompetitiven Faktors, liegen weit auseinander und bieten daher noch einiges Optimierungspotential. Nach der Ausarbeitung des Papers zur unteren dieser Schranken wird daher zunächst versucht, diese untere Schranke weiter zu optimieren.

Bei den oberen Schranken folgt nach der Vorstellung obiger allgemeiner Schranke die Analyse diverser Spezialfälle von Bäumen: Diese sind der vollständige Binär-, der AVL- und der Fibonaccibaum, sowie der im Beweis zur allgemeinen unteren Schranke verwandte Jellyfish tree. Hier werden diverse Explorationsalgorithmen entwickelt. Insb. für den Jellyfish tree wird ein universelles Algorithmenkonzept hergeleitet, mit Hilfe dessen sich neben dem ursprünglichen Jellyfish tree auch teils exotische Abarten, von denen einige hier ebenfalls betrachtet werden, effizient explorieren lassen. Dies läßt insb. auch Aussagen darüber zu, inwieweit sich die allgemeine untere Schranke mit Hilfe des Ansatzes aus dem betreffenden Paper weiter optimieren läßt.

Neben den in dieser Diplomarbeit speziell entwickelten Algorithmen, wird das Konzept der sog. Sparse Trees auf die betrachteten Baumtypen angewandt, bei dem kompetitive Faktoren mit Hilfe eines definierten Dichtemaßes der zu explorierenden Bäume angegeben werden können.

Einige der in dieser Diplomarbeit verwandten Paper wurden teils intensiv fehlerkorrigiert, was im Falle des obigen Approximationsalgorithmus der optimalen Offlinelösung zu einer Verdopplung dessen Approximationsgüte geführt hat.

Yinan Li, University of Paderborn

March 9, 2012, 11:00 a.m., F1.110

Parallelbearbeitung von Schweißprozessdaten

In der Automobilindustrie gehört das Schweißen zu den wichtigsten Fügeverfahren für Metalle. Schweißfehler können die Homogenität der Schweißnaht stören und sich somit negativ auf die Festigkeit der Schweißnaht auswirken. Die Qualitätssicherung erfordert, dass die Schweißnähte aller Werkstücke zu prüfen sind und alle Schweißfehler entdeckt werden. Eine in-situ Prüfung ist sinnvoll für die Produktionseffizienz, weil sie parallel zur Produktion erfolgt.

Die Firma Benteler Automobiltechnik GmbH entwickelt ein neuartiges, automatisiertes Schweißnahtprüfungssystem. Mit diesen werden die Schweißprozesse in-situ verfolgt und bewertet. Die typischen Schweißfehler wie Risse, Hohlräume und Bindefehler können durch das neu entwickelte System entdeckt werden.

Im Rahmen der Arbeit werden das bereits vorhandene Schweißnahtprüfungsprogramm und seine Algorithmen unter Berücksichtigung der architektonischen Eigenschaften von CPU und Grafikkarten (GPU) parallelisiert. Aufgrund herausgearbeiteter Optimierungsmöglichkeiten der Algorithmen mit CUDA-Implementierung (Compute Unified Device Architecture) kann der Algorithmus-Teil maximal 4,5 fach beschleunigt werden. Durch OpenMP-Implementierung (Open Multi-Processing) kann auf der CPU der Nicht-Algorithmus-Teil im Programm maximal 1,3 fach beschleunigt werden. Insgesamt erzeugt die Ausführung der Kombination von OpenMP und CUDA eine gesamte Beschleunigung von Faktor 3.3 im Gegensatz zu einem CPU-Kern.

(Abschlussvortrag Masterarbeit)

Benjamin Koch, University of Paderborn

February 22, 2012, 4:30 p.m., F1.110

Kombination algorithmischer und regelungstechnischer Methoden zur Optimierung von Kommunikationsketten aus Robotern

Man kann zwei Roboter durch eine Kette von beweglichen Relaisstationen verbinden. Diese Kommunikationskette soll so kurz wie möglich sein. In anderen Arbeiten wurden mehrere Strategien vorgeschlagen und untersucht, um eine solche Kette zu verkürzen. Die meisten davon nutzen ein diskretes Zeitmodell.

In dieser Bachelorarbeit habe ich einige dieser Strategien auf einem echten Roboter implementiert, um sie in der Praxis zu auszuprobieren. Auf einem echten Roboter würden diskrete Zeitschritte nur dann Sinn ergeben, wenn durch Einschränkungen des Roboters ohnehin keine kontinuierliche Messung oder Bewegung möglich ist. Deshalb nutze ich (quasi-)kontinuierliche Strategien.

Für diese Arbeit habe ich eine Methode entwickelt, mit der man diskrete Strategien in kontinuierliche umwandeln kann. Dazu wird zu der Strategie eine Positionsregelung hinzugefügt. Die transformierten Strategien können nicht mit den bisher genutzten Techniken untersucht werden, aber mit Hilfe von Methoden aus der Mechatronik und Regelungstechnik kann man sie analysieren und die Parameter einstellen, die sich durch die Transformation ergeben.

Bei echten Robotern muss man einige praktische Aspekte berücksichtigen: Zum einen dürfen die Roboter nicht kollidieren, sondern sie müssen einander ausweichen. Darüber hinaus sollen überflüssige Roboter entfernt werden. Einige Strategien haben dafür bereits Mechanismen integriert, die aber leider durch die Transformation in kontinuierliche Zeit verloren gehen. I habe deshalb einen Algorithmus implementiert, der unabhängig vom Zeitmodell für alle Strategien funktioniert.

(Abschlussvortrag Bachelorarbeit)

Sven Kurras, University of Paderborn

January 25, 2012, 2:00 p.m., F1.110

Distributed Sampling of Regular Graphs

Generating random graphs, called graph sampling, is used as a tool in various applications as well as of its own theoretical interest. In the context of peer-to-peer networks, one is interested in sampling d-regular graphs that provide high connectivity and low diameter while being robust against node failures and adversarial attacks. Distributed strategies are preferred, because any central server is a potential bottleneck and makes such a network vulnerable. Since random graphs do provide the above properties with high probability, a promising distributed strategy is to frequently randomize the connections between the nodes by a simple local graph perturbation, aiming to achieve an unknown global structure that is sufficiently close to random. An example for such an operation is the k-Flip, where the outer edges of a random (k + 2)-walk are flipped. The most challenging part of the analysis is to quantify the speed of convergence towards the long-term probability distribution, denoted as the mixing time of the underlying Markov chain on all connected d-regular graphs towards its stationary distribution. For that purpose, some advanced proof techniques were evolved in the last decades that are able to deal with such highly combinatorial structures, but which still need further refinements.

This thesis focuses on working out the present state of the art of this research field, as well as on contributing some new insights and theoretical results. After an introduction into the theoretical background of distributed sampling strategies, the first main focus lies on an extensive report on the most powerful proof techniques from this field, especially on the latest refinements that are not covered by any standard literature. The second main focus lies on three independent results of my own:

  1. an extension to the k-Flip to make it applicable whenever its flip edges do not induce a triangle
  2. a generalization of an existing convergence rate proof for the 1-Flip to the k-Flip
  3. lower bounds that allow to analyze principle limitations of the prominent canonical path technique

In my talk, I provide insights into this research field and some of my results, with focus on the canonical path technique.

(Final Presentation Master Thesis)

Tobias Bertel, University of Paderborn

January 11, 2012, 2:00 p.m., F1.110

Entwicklung einer Datenstruktur für Echtzeitrendering mit Vermeidung überflüssiger Zustandswechsel

Mit OpenGL 1.5 (2003) wurden sogenannte Buffer Objects (Batches) eingeführt, welche es einem Programmierer erlauben Primitivgruppen, wie etwa Vertex Arrays, direkt im VRAM der GPU abzulegen. Dies reduziert die notwendige Kommunikation für Datenübertragungen zwischen CPU RAM und GPU VRAM beim Darstellen einer Szene erheblich.

In dieser Arbeit untersuche ich texturierte und statische 3-D-Szenen mit einer Komplexität von 100.000 bis 2,3 Millionen Dreiecken mit unterschiedlichen Renderingansätzen, die Batches verwenden. Das Hauptziel ist es die Renderingansätze auf ihre Fähigkeit hin zu überprüfen, interaktive Bildraten zu liefern. Dabei wird insbesondere untersucht wie sich die Anzahl notwendiger Zustandswechsel von OpenGL zum Zeichnen einer Szene auf die Bildrate auswirkt.

Im wesentlichen vergleiche ich zwei Renderingansätze: Zum Einen werden alle Grafikprimitiven nach Texturverwendung sortiert (State Sorting) und in jedem Darstellungsschritt gezeichnet. Dieser Ansatz liefert für jede verwendete Textur in der Szene genau einen Batch. Zum Anderen werden die Grafikprimitiven in einen Octree verteilt und in den Knoten des Octrees Batches gebildet. Die Darstellung des Octrees geschieht über eine Tiefensuche beginnend bei der Wurzel des Octrees standardmäßig mit deaktiviertem View-Frustum-Culling. Dies erlaubt es die Änderung der Bildrate zu untersuchen, wenn anstatt der optimalen Batches aus dem State Sorting Ansatz nicht optimale Batches, herbeigeführt durch die hierarchische Verteilung der Szene innerhalb eines Octrees, verwendet werden.

Die Evaluation zeigt unter anderem, dass der Renderingansatz, der nur auf State Sorting beruht, stets höhere durchschnittliche Bildraten erzeugt als der Ansatz mit einem Octree, der Batches als innere Knoten und View-Frustum-Culling verwendet. Dies ist sehr bemerkenswert, da in den gewählten Testpfaden teilweise sehr viel Geometrie verworfen werden konnte.

(Abschlussvortrag Bachelorarbeit)

Kathrin Bujna, University of Paderborn

December 21, 2011, 2:00 p.m., F1.110

Parallel Real-Time Rendering using Heterogeneous PC Clusters

We are given an arbitrarily formed chain of mobile relay robots that connects two base stations. Each relay does only know its two neighbours in the chain, which have to be within its viewing range. The goal is to shorten this chain as far as possible. The problem is that each relay can base its decision where to move only on the relative position of its neighbours. There already exist different local strategies for this short-chain-problem, such as the Hopper, the Go-to-the-Middle, and the Move-on-Bisector strategy.

In my master's thesis I have elaborated on the question whether the existing strategies can be improved. To this end, I have generalised and parametrised the existing strategies and made use of optimisation techniques known from machine learning to find out which of the parameter combinations (i.e., concrete strategies) works best regarding certain experiments. To be more precise, I have shown how the strategies can (or cannot) be improved with respect to different classes of initial chains and different performance measures (i.e., the runtime, the travelled distance, and a measure that combines both). For example, it can be shown that the so-called shorten operation of the Hopper strategy is not necessarily needed. In our experiments the respective strategy achieves a performance similar to the classical Hopper, and it can be proven that a relative chain length of 2 is always reached. Another example concerns the Go-to-the-Middle strategy. In the experiments it has turned out that, regarding the runtime as well as the travelled distance, it seems to be better to let the relays move to the middle between their neighbours in a sequential order, rather than moving all relays in parallel.

(Final Presentation Master Thesis)

Tim Süß, University of Paderborn

December 14, 2011, 2:00 p.m., F1.110

Parallel Real-Time Rendering using Heterogeneous PC Clusters

3-D-Szenen aus CAD-Systemen besitzen zumeist eine hohe geometrische Komplexität. Es gibt eine Reihe von Konzepten, welche sich mit der Schwierigkeit auseinandersetzen, solche Szenen in Echtzeit zu rendern; beispielsweise daten- und rechenparallele Techniken oder Outof- Core Rendering Mechanismen. Diese Arbeit behandelt die Nutzung von heterogenen PC-Clustern zur parallelen Bildberechnung von hochkomplexen Szenen. Für drei unterschiedliche Szenarien wurden jeweils verschiedene Verfahren entwickelt, bei deren Berechnungen wenige Highend-Rechner von vielen schwachen Rechnern unterstützt werden. Zunächst sind dies statische Szenen, die vollständig in den Hauptspeicher eines Rechners geladen werden können. Im zweiten Szenario werden statische Szenen betrachtet, deren Komplexität den Speicher eines einzelnen Rechners übersteigt. Zuletzt werden Szenen betrachtet, die neben statischen Objekten auch dynamische Objekte beinhalten.

Ralf Petring, University of Paderborn

December 7, 2011, 2:00 p.m., F1.110

Multi Algorithm Rendering

There are many rendering algorithmsknown in computer graphics. Each of them performs well for a specific type of scene but they may perform poorly on other types of scenes. The problem we consider in this talk are scenes which consist of different scene types combined in a single scene. For such scenes there is no single optimal algorithm. We present an idea how to use many algorithms in a single frame to display different parts of the scene. At this we consider sampled observer positions to find the best out of a given set of algorithms for the different scene parts. We consider culling algorithms as well as approximation algorithms. In this talk, we focus on the final decision which algorithms to use at a specific position during runtime. This is an optimization problem whose conditions can change from frame to frame.

Alexander Maecker, University of Paderborn

November 30, 2011, 2:00 p.m., F1.110

Analyse einer kontinuierlichen, lokalen Strategie für Roboter zur Erzeugung einer kurzen Kommunikationskette

Das Optimieren einer Kommunikationskette, bestehend aus einer Gruppe in ihren Fähigkeiten stark eingeschränkter mobiler Roboter, zwischen zwei Basisstationen ist ein bekanntes Problem. Mit Move-On-Bisector wurde in [1] eine effiziente kontinuierliche, lokale Strategie vorgestellt, die es ermöglicht die Roboter innerhalb einer Zeit von O(n) auf der direkten Geraden zwischen diesen Basisstationen anzuordnen. Dabei legen die Roboter lediglich basierend auf den Positionen ihrer Nachbarn ihre eigene Bewegung fest.

Ziel ist es nun Move-On-Bisector in einem abgewandelten, weniger idealisierten, Modell zu untersuchen. Dabei wird im Gegensatz zum Modell in [1] davon ausgegangen, dass es bei der Erfassung der Positionen der Nachbarn eines Roboters zu einer konstanten Verzögerung kommt. In Hinblick darauf wurde die Strategie zum einen in einigen Konfigurationen theoretisch betrachtet. Zum anderen wurden mit Hilfe von Simulationen weitere Erkenntnisse zu einigen Eigenschaften der Strategie gewonnen.

[1] Degener, Bastian; Kempkes, Barbara; Kling, Peter; Meyer auf der Heide, Friedhelm. A continuous, local strategy for constructing a short chain of mobile robots. In: Sirocco '10: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity Bd. 6058, Springer, 7 - 11 Juni 2010, S. 168-182.

(Abschlussvortrag Bachelorarbeit)

Benjamin Eikel, University of Paderborn

November 23, 2011, 2:00 p.m., F1.110

Spherical Visibility Sampling for a new Data Structure

I am developing a new data structure for rendering of complex 3D scenes. The idea for this new data structure is based on the Randomized Sample Tree [1] and its shortcoming of not taking visibility information into account. The new data structure shall store visibility information for different viewing directions onto an object.

This information can be used during walking through the virtual scene. When the object is to be displayed, the current viewing direction can be determined and only parts that were found visible before have to be displayed. Because the visibility information can neither be collected nor stored for the infinitely many viewing directions, a sampling approach is used. Sampling positions are created on the surface of the bounding sphere of the object, and visibility information is collected for these positions. I will present my current ideas, results, and problems concerning the ongoing work on the spherical visibility sampling.

[1] Jan Klein, Jens Krokowski, Matthias Fischer, Michael Wand, Rolf Wanka, and Friedhelm Meyer auf der Heide. The Randomized Sample Tree: A Data Structure for Interactive Walkthroughs in Externally Stored Virtual Environments. In Proceedings of the ACM symposium on Virtual reality software and technology (VRST '02)

Yinan Li, University of Paderborn

October 26, 2011, 2:00 p.m., F1.110

Parallelbearbeitung von Schweißprozessdaten

In der Automobilindustrie gehört das Schweißen zu den wichtigsten Fügeverfahren für Metalle. Schweißfehler können die Homogenität der Schweißnaht stören und sich somit negativ auf die Festigkeit der Schweißnaht auswirken. Die Qualitätssicherung erfordert, dass die Schweißnähte aller Werkstücke zu prüfen sind und alle Schweißfehler entdeckt werden. Eine in-situ Prüfung ist sinnvoll für die Produktionseffizienz, weil sie parallel zur Produktion erfolgt.

Die Firma Benteler Automobiltechnik GmbH entwickelt ein neuartiges, automatisiertes Schweißnahtprüfungssystem. Mit diesen werden die Schweißprozesse in-situ verfolgt und bewertet. Die typischen Schweißfehler wie Risse, Hohlräume und Bindefehler können durch das neu entwickelte System entdeckt werden.

Im Rahmen der Arbeit sollen bereits vorhandene Algorithmen aus dem Schweißnahtprüfungssystem, unter Berücksichtigung der architektonischen Eigenschaften von Grafikkarten (GPU) und CPUs parallelisiert werden. Das Laufzeitverhalten wird ebenso untersucht, wie weitere Optimierungsmöglichkeiten der betrachteten Algorithmen. Die Ergebnisse gilt es in Form eines lauffähigen Prototypen zu bestätigen.

(Antrittsvortrag Masterarbeit)

David Maicher, University of Paderborn

October 19, 2011, 2:00 p.m., F1.110

Sichtbarkeitsveränderungen durch Benutzerverhalten in virtuellen 3-D-Szenen

Das Ziel dieser Masterarbeit sind Erkenntnisse über Auswirkungen von Benutzerverhalten bei der Bewegung durch eine 3-D-Szene auf Änderungen der Menge sichtbarer Objekte. Dazu wird zunächst das Benutzerverhalten durch Parameter wie z.B. Bewegungsgeschwindigkeit oder Rotationsgeschwindigkeit beschrieben. Aufbauend auf dieser Parametrisierung werden anschließend innerhalb einer Evaluierung die Auswirkungen von einzelnen Parametern auf die Sichtbarkeit von Objekten untersucht. Hierfür werden entsprechende Tests für zwei feste Szenen implementiert, bei denen zufällige Pfade betrachtet werden, die bestimmten Belegungen einzelner Parameter genügen. Aus den gemessenen Änderungen der sichtbaren Objekte bei einer Bewegung entlang dieser Pfade lassen sich Informationen zur Relevanz der einzelnen Parameter bezüglich Sichtbarkeitsveränderungen gewinnen. Auf Basis dieser Ergebnisse wird abschließend eine Heuristik vorgestellt, die für gegebene Pfade eine Schätzung der verursachten Sichtbarkeitsveränderung ermöglicht.

(Abschlusspräsentation Masterarbeit)

Project Group: NODES - Offering Dynamics to Emerging Structures, University of Paderborn

October 12, 2011, 2:00 p.m., F1.110

Our project group focuses on the research area of local strategies in dynamic networks. Changes that lie outside of the control of the network are referred to as external dynamics. Modifications initiated by the system itself are referred to as controlled dynamics. We want to investigate how controlled dynamics can be used to counteract external dynamics. By using local strategies we aim at ensuring scalability and robustness.

We will consider self-stabilizing small-world networks and networks in which the positions of the nodes are adapted based on their communication behavior. Furthermore, we will look at networks in which nodes exhibit certain roles. In particular, we will look at a certain coloring and facility location problem.

To study the behaviors of our algorithms and gain new insights, we developed a simulator. We will give a short demonstration of the simulator.

(interim report)

Kamil Swierkot, University of Paderborn

October 12, 2011, 2:30 p.m., F1.110

Complexity Classes for Local Computation

Just recently Korman, Peleg and Fraigniaud have introduced a complexity theory for the local distributed setting. They have defined three complexity classes: LD(Local Decision), NLD(Nondeterministic Local Decision) and NLD#n whereby it is required that the algorithms use at most a constant number of communication rounds. In order to define the classes NLD and NLD#n they defined nondeterminism for the distributed setting by the use of certificates and verifiers.

In my master's thesis, I have studied different aspects of this complexity theory. On the one hand, I give a comprehensive classification of languages whose computational tasks are of interest in the research of distributed algorithms. On the other hand, I have found two hierarchies within the complexity classes LD and NLD. The hierarchy for LD states that one additional communication round is sufficient to decide more languages. The hierarchy within NLD is based on the size of the certificates that are needed to verify a language.

In my talk, I will briefly introduce the needed concepts of this complexity theory. Moreover, I will give some additional definitions and an overview of the main results.

(Final Presentation Master Thesis)