Matthias Dürksen

February 15, 2023, 2:00 pm, Raum: F0.530

Uniform Circle Formation of Mobile Robots with Limited Visibility

The world of distributed computing is becoming increasingly relevant. This is also true for mobile robots. For this topic, the formation of a circle formation is investigated, where the robots have a limited field of view. One possibility for the problem is to gather the robots first and thus have an effective global view, but we consider a direct approach. In this talk, I will present my circle formation strategy, explain the limitations of particular robot models, and show the obtained results.


Tobias Terfort

February 15, 2023, 2:45 pm, Raum: F0.530

Scheduling under shared Resources

In the industry, many scheduling problems with shared resources occur. In this thesis, we consider scheduling jobs on identical machines under makespan minimization. Furthermore, jobs are allowed to request resources.

We introduce a new structure called inclusion graphs to the scheduling problem notation, to develop approximation algorithms for special scheduling problems in between the single resource request scheduling problem and the arbitrary resource combination request scheduling problem. The inclusion graph will show, which resource sets an instance requests and how a requested set interferes with other requested sets.

In the first algorithmic part, we review the single resource request per job problem and extend the algorithmic ideas of Pukrop et al. to derive an easier than currently known approximation algorithm with an approximation ratio of 1.5.

In the second algorithmic part, we derive a simple 2 approximation algorithm and a 1.9 approximation for the scheduling problem, in which each job can request arbitrary resource sets, except, that the inclusion graph of the instance must have depth 2 and indegree 1.

In the last part, we generalize the 2 approximation to the case, that the inclusion graph can have arbitrary depth.


Steffen Braun

February 01, 2023, 2:00 pm, Raum: F0.530

Restricted Assignment and Parallel Batch Scheduling

Wir betrachten die Erweiterung von Unrelated Scheduling, Scheduling with compatible assignment restricitons und Scheduling with treehierarchical assignment restrictions durch das Batch-Konzept. Für eine gegebene Job- und Maschinenmenge wird eine Job-Maschinen-Zuweisung gesucht. Die Jobzuweisungen unterliegen Restriktionen, die sich in den verschiedenen Problemen unterscheiden. Jobs haben Lasten, aus denen sich die Last der Maschinen bildet. Ohne das Batch-Konzept ist die Last einer Maschine die Summe der Lasten der ihr zugewiesenen Jobs. Mit dem Batch-Konzept werden Jobs nicht mehr Maschinen, sondern Batches zugewiesen. Batches lassen sich auf Maschinen erzeugen und können maximal Jobs in Höhe der maschinenspezifischen Batch-Kapazität enthalten. Die Last einer Maschine im Batch-Konzept ergibt sich aus der Summe der Batchlasten. Die Last eines Batch ist gleich der maximalen Last der in ihm enthaltenen Jobs. Ziel ist es, die maximale Last auf einer Maschine zu minimieren.

Diese Arbeit untersucht die für die einzelnen Probleme bereits entwickeltem Algorithmen hinsichtlich der Möglichkeit, diese auf das Batch-Konzept zu adaptieren. Der Ausgangspunkt ist die Problemstellung der Job-Batch-Zuweisung. Für eine gegebene Jobmenge wird eine Job-Batch-Zuweisung gesucht, in der die Gesamtlast der erzeugten Batches minimal ist. Eine solche lässt sich konstruieren, indem die Jobs in absteigender Reihenfolge ihrer Lasten Batches zugeordnet werden. Dabei wird ein Batch mit der maximal möglichen Anzahl von Jobs befüllt, bevor ein neuer Batch konstruiert wird.

Die betrachteten Algorithmen werden hinsichtlich ihrer Erweiterung um diese Job-Batch-Zuweisung überprüft. Dabei wird für Unrelated Scheduling der Algorithmus aus An approximation algorithm for the generalized assignment problem (1993) von Shmoys und Tardos auf das Batch-Konzept adaptiert. Dieser hat eine Approximationsgüte von 2. Die Adaption erfordert eine Anpassung der LP Bedingung, die die maximal mögliche Maschinenlast beschränkt. Diese muss die veränderte Berechnung der Maschinenlast im Batch-Konzept berücksichtigen. Weiterhin werden in den Beweisen Anpassungen auf das Batch-Konzept vorgenommen, die die Beweisstruktur jedoch nicht verändern. Für Scheduling with compatible assignment restrictions wird das PTAS aus Approximation algorithms for scheduling and two-dimensional packing problems (2010) von Schwarz auf das Batch-Konzept adaptiert. Hier ist es notwendig, die Zielfunktion mit der Schedules bewertet werden anzupassen, sodass sie der veränderten Berechnung der Maschinenlast im Batch-Konzept entspricht. Des Weiteren wird für die Reduktion der verschiedenen Jobgrößen auf eine konstante Anzahl ein anderes Verfahren verwendet. Hierfür wird das Konzept aus Structural Parameters for Scheduling with Assignment Restrictions von Jansen, Maack und Solis Oba genutzt. Ebenfalls werden die Beweise auf das Batch-Konzept angepasst. Dies verändert die Beweisstruktur jedoch nicht. Für Scheduling with treehierarchical assignment restrictions wird der optimale Algorithmus für den Fall mit konstant vielen verschiedenen Jobgrößen aus Scheduling with processing set restrictions: PTAS results for several variants (2011) von Epstein und Levin auf das Batch-Konzept transformiert. Dies erfordert die Anpassung der Zielfunktion, mit der die Schedules bewertet werden und der Anpassung der Beweise auf das Batch-Konzept.


Piu Roy

February 01, 2023, 2:45 pm, Raum: F0.530

3D Modeling Using Model Synthesis

3D modeling is used to create digital content such as computer games, movies, graphics, or even a virtual world. This thesis focuses on the model synthesis and its different approaches to 3D modeling. Model Synthesis generates a complex 3D model that resembles a user-provided input model. The fact that this method does not require a predetermined set of rules is one of the primary reasons why this method was chosen. Another advantage is that the input model does not need to be drawn by hand, which is a significant time-saver. We went over different techniques for model synthesis and their respective drawbacks and chose the continuous model synthesis approach because it requires maintaining only one constraint, i.e., adjacency constraints, between its boundary features. As the current approach works only for polyhedral objects; the purpose of this thesis is to improve the current approach so that it can be used on curved-shaped objects or objects with a huge number of distinct face normals. The idea proposed was to use bounding boxes for such input models. We have used four different models to test the proposed idea; a cylinder made up of 48 triangles, a pig with 2352 triangles, a bench with 4280 triangles and a tree with 8844 triangles. The outcomes are unique and different across all four scenarios. They do, however, offer certain benefits and drawbacks. As a result, we can draw the conclusion that it is possible to build an output model using a bounding box for objects with curved shapes or objects with a large number of distinct face normals. However, we still need to do more research to determine its limit on the type or shape of models that cannot give proper results.


André Graute

February 01, 2023, 3:30 pm, Raum: F0.530

Various techniques to accelerate the rendering of Neural Radiance Fields

Neural Rendering using Neural Radiance Fields (NeRFs) is a technique that uses deep learning algorithms to create photorealistic images and videos. It is widely used in computer graphics and animation to create more realistic and lifelike images. One of the main challenges in rendering NeRFs is the high computational cost, which can make it difficult to achieve real-time performance. In this talk, several techniques and solutions will be presented that aim to make the rendering process more efficient, as well as accelerate it while keeping the image quality as close to the original as possible. These techniques usually augment the neural network with spatial data structures, simplify the computations of individual MLPs, or trade computation time for memory by storing more data.


Jonas Harbig

December 07, 2022, 2:00 pm, F0.530

A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility

We consider a swarm of n robots in a d-dimensional Euclidean space. The robots are oblivious (no persistent memory), disoriented (no common coordinate system/compass), and have limited visibility (observe other robots up to a constant distance). The basic formation task Gathering requires that all robots reach the same, not predefined position. In the related Near-Gathering task, they must reach distinct positions in close proximity such that every robot sees the entire swarm. In the considered setting, Gathering can be solved in O(n + ∆2 ) synchronous rounds both in two and three dimensions, where ∆ denotes the initial maximal distance of two robots.

In this work, we formalize a key property of efficient Gathering protocols and use it to define λ-contracting protocols. Any such protocol gathers n robots in the d-dimensional space in O(∆2 ) synchronous rounds, for d ≥ 2. For d = 1, any λ-contracting protocol gathers in optimal time O(∆). Moreover, we prove a corresponding lower bound stating that any protocol in which robots move to target points inside the local convex hulls of their neighborhoods – λ-contracting protocols have this property – requires Ω(∆2 ) rounds to gather all robots (d > 1). Among others, we prove that the d-dimensional generalization of the GtC-protocol is λ-contracting. Remarkably, our improved and generalized runtime bound is independent of n and d.

We also introduce an approach to make any λ-contracting protocol collision-free (robots never occupy the same position) to solve Near-Gathering. The resulting protocols maintain the runtime of Θ(∆2 ) and work even in the semi-synchronous model. This yields the first Near-Gathering protocols for disoriented robots and the first proven runtime bound. In particular, combined with results from [32] for robots with global visibility, we obtain the first protocol to solve Uniform Circle Formation (arrange the robots on the vertices of a regular n-gon) for oblivious, disoriented robots with limited visibility.


Tim Ölker

December 07, 2022, 3:00 pm, F0.530

Laufzeitoptimierung der Berechnungsphase bei Near-Gathering Strategien

Wir betrachten das Near-Gathering Problem auf Basis von Castenow et al. Dabei untersuchen wir einen Schwarm von n Robotern im 2-dimensionalen euklidischen Raum, in dem die Roboter die Eigenschaften anonym, homogen, identisch, autonom, deterministisch besitzen und über eine eingeschränkte Sichtweite verfügen. Die Roboter bewegen sich in Look, Compute und Move Zyklen nach dem Fsync Modell. Bei dem Near-Gathering Problem geht es darum, dass sich alle Roboter in einem vorher nicht definierten Bereich sammeln, ohne mit anderen Robotern zu kollidieren. Dies konnte mit dem Protokoll P^cl in O(Δ^2) Runden erreicht werden, indem ein Roboter in jedem Schritt nur eine maximale Distanz einer Konstanten t/2 zurücklegen darf und dieser für Nachbarn, die im Abstand ≤ t sich befinden, deren Zielpunkte berechnet, um Kollisionen auszuschließen. ∆ ist die maximale Distanz zwischen zwei Robotern in der initialen Formation. Dabei gibt die Laufzeit eine Anzahl an Schritten (LCM-Zyklen) bis zur Terminierung an. In dieser Arbeit analysieren wir die Laufzeit eines einzelnen Berechnungsschritts eines Roboters und die damit verbundene Laufzeitverzögerung durch die Berechnung von Zielpunkten der Nachbarn.

Der Fokus dieser Arbeit liegt auf der Verwendung von P^cl mit dem GoToCenter (GtC) Protokoll, mithilfe dessen Zielpunkte berechnet werden. Bei GtC wird das Gathering mithilfe von Smallest Enclosing Circles (SEC) erreicht, wobei die Berechnung von einem SEC O(n) benötigt. Somit konnte in dieser Arbeit gezeigt werden, dass für einen Roboter mit vielen Nachbarn in einem Schritt t polynomielle Laufzeiten entstehen, durch die Berechnung von Zielpunkten der Nachbarn und die damit verbundenen Berechnungen von SEC. Mithilfe von Verbesserungen für P^cl konnte die Laufzeit verkürzt werden. Hierbei wurde P^cl angepasst, um Kollisionen bereits vorher auszuschließen und mithilfe einer Hashtabelle bereits berechnete Zielpunkte wiederzuverwenden, sollten zwei Nachbarn dieselben Nachbarn haben und somit auch denselben Zielpunkt. Durch eine Simulation konnte gezeigt werden, dass durch diese Verbesserungen, für konkrete Startformationen unter Verwendung von GtC, weniger SEC berechnet werden müssen und somit eine Laufzeitverbesserung erzielt wurde. Bei quadratischen Gittern wurden um den Faktor ≤ 0,453 weniger SEC berechnet und bei konzentrischen Kreisen um den Faktor ≤ 0,49.


Barbara Kempkes und Andreas Cord-Landwehr und Miroslaw Dynia

Dezember 2, 2022, 17:00 Uhr, F0.530

Alljährliches Kooperationskolloquium

Die drei Vortragenden unseres diesjährigen Kolloquiums sind Absolventen unserer Arbeitsgruppe. Sie berichten über ihre aktuellen Tätigkeitsfelder in der industriellen und wissenschaftlichen Praxis.

Barbara Kempkes promovierte im Jahr 2012 in unserer Arbeitsgruppe mit einer Arbeit über "Local strategies for robot formation problems". Sie ist heute bei der dSPACE GmbH in Paderborn tätig.

Andreas Cord-Landwehr promovierte im Jahr 2016 in unserer Arbeitsgruppe mit einer Arbeit über "Selfish Network Creation - On Variants of Network Creation Games". Er ist heute bei der CLAAS KGaA mbH in Harsewinkel tätig.

Miroslaw Dynia promovierte im Jahr 2007 in unserer Arbeitsgruppe mit einer Arbeit über "Collective Graph Exploration". Er ist heute bei der GMS Development als Director Product Management in Paderborn tätig.


Daniel Neib

November 23, 2022, 11:00 am, room: F1.310

Max-Line-Formation for oblivious mobile robots with limited visibility

We investigate a recently studied formation problem called the Max-LineFormation problem. It considers N ∈ N robots with limited visibility, implying each robot can observe robots only up to a constant distance denoted as the viewing range. The robots operate in fully synchronous (Fsync) discrete rounds. Motivated by the impossibility result proving that robots, which agree on both axes of their local coordinate system in Fsync are unable to solve the Max-Line-Formation problem with a constant-sized circular viewing range under the OBLOT model, we examine the circular viewing range issue under modified models. Therefore, we assume simplifications to the model evaluating if two robots differing in appearance are sufficient to solve the formation problem under the circumstances it was proven impossible. We derive three algorithms solving the Max-Line-Formation problem with a constant-sized circular viewing range under different additions to the original model. The first algorithm uses an extended circular viewing range enabling an approaching step mechanism helping to solve the formation problem. The second algorithm uses an extended circular viewing range, memory, and two visibly differing robots. The third algorithm removes the memory property and uses an extended circular viewing range and two visibly differing robots. We show that the worst-case runtime of all algorithms is identical. Finally, we elaborate on observations we made, motivating why we assume that two visibly differing robots as the only addition to the OBLOT model, where the impossibility was proven, seems insufficient to solve the original problem.


Florian Bürger

November 16, 2022, 3:00 pm, room: F1.110

Accelerating Real-Time Rendering of Complex Scenes Using Deep Learning-Based Super-Resolution

Virtual scenes are becoming more complex and to render them in high quality and real-time, increasingly advanced hardware is required. In this work, we present a prototypical alternative in which we render a virtual scene in a smaller resolution using an approximation algorithm and upscale this image using a neural network. In doing so, we attempt to reduce rendering time by using the Progressive Blue Surfels algorithm. Then, we upscale the output image by using super-resolution with a convolutional neural network to receive a high-quality image. For this purpose, we present the neural network training in detail. We describe which parameters and images should be used to train such a convolutional neural network to achieve a high training quality. Thereby, we compare the image qualities of the outputs from different training runs. Finally, we look at the performance of our approach in PADrend and compare it to rendering only with the Progressive Blue Surfels algorithm in a higher resolution.