Oberseminar

Lars Prior

June, 21, 2023, 2:00 pm, room: F1.110

Viewing Range Analysis for Gathering Anonymous, Oblivious Robots on a Grid

Consider a set of robots in an arbitrary but connected formation on a two-dimensional grid. The robots do not have any means to store a state nor communicate with other robots. Now all of these robots have the task to gather in one cell. Since the robots have no shared logic, each robot has to make its own decisions, with only the knowledge of its current surroundings. This problem is a very central problem in swarm robotics and is called the Gathering problem. In the paper "Gathering Anonymous, Oblivious Robots on a Grid" (Castenow et al., 2020) an algorithm was presented that is able to solve this problem. However, for this algorithm each robot needs a viewing range of at least seven cells. This opens up the question of what the smallest possible viewing range is, at which this problem can be solved. Since the goal of swarm robotics is to solve tasks with small and cheap robots, simplifying robots by reducing the needed viewing range would be beneficial. This thesis uses a computer-based approach for generating and simulating algorithms and provides an overview and analysis of all potentially valid algorithms for viewing ranges one to three. Multiple algorithms are provided, which may solve the oblivious robot gathering problem on a grid. While this thesis does not provide a correctness proof for these algorithms, it is shown that all other possible algorithms with a viewing range smaller or equal to three cannot gather arbitrary swarm configurations.

AND

Ingo Gerigk

June, 21, 2023, 2:45 pm, room: F1.110

A simulator for unified scheduling problems

In this presentation we will discuss why sheduling problems are worth researching and how we developed a generic data model to represent a varaiety of sheduling problems. Additionaly we will demo the framework and graphical user application created in conjunction with this thesis to show the process of creating a model for a basic sheduling problem, generating instances of said problem, simulating sheduling heuristics on these problems and presenting the result in a graph.

 

Spoorthi Satish Madhavan

May, 31, 2023, 2:00 pm, Room: F1.110

Title: Max-Line-Formation by luminous mobile robots with limited visibility

This research aims to solve the impossibility issue of Max-Line Formation problem using mobile robots in oblot model and circular viewing range with limited visibility [CGKadH21]. The robots operate under the fsync scheduler and possess characteristics like homogeneous, autonomous, oblivious, silent, disoriented, and anonymous, as explained in detail in section 3. The fundamental challenge in solving the problem in the oblot model lies in the robots being silent and oblivious, i.e., lacking memory of their previous movements and unable to share information within their viewing range. To overcome this issue, we employ the lumi model [DFP+ 16]. Lumi model has similar properties to oblot model. However, unlike oblot model, the lumi model is not oblivious and silent because it includes a small register called lights to facilitate storage and communication among the robots.

In subsequent sections, we explore how the lumi robots attempt to solve the Max-Line Formation problem with a circular viewing range. We study three configurations, i.e., $H$, Extended-H, and square-grid refer subsequent sections. We have developed an algorithm based on these three configurations. The algorithm consists of two parts. In the first part, we utilize the fsync scheduler with the lumi model to arrange the robots in a straight line. In the second part, we stretch the line formation until $n-1$ using the approach employed in the Max-Line Formation problem with the oblot model and square viewing range [CGKadH21][DFP+ 22]. We have also done an empirical analysis with the help of a simulator. We analyze their effectiveness in different situations and configurations and provide a clear understanding.

 

Project Group VirtuChemLab

April 5, 2023, 1:00 pm, Room F1.110

Adaptive Virtual Chemistry Laboratory for Study Preparation

We present the results of the project group: “Adaptive Virtual Chemistry Laboratory for Study Preparation”. The project group aims to develop a virtual learning platform for chemical-technical education using virtual reality technology. It represents a supplementary offer for students to prepare for internships in chemical laboratories. We will give examples of how to perform chemical experiments in the virtual laboratory.

The programming team behind the VirtuChemLab project consists of 14 individuals who have spent over a year developing a virtual chemistry laboratory in VR using Unity. Through constant communication with the customers from the chemistry department, the team worked to implement a wide range of functionalities aimed at providing new chemistry students with an immersive laboratory experience and additional resources for use at the University of Paderborn to serve as an introduction to the real lab and enable wide-range collaboration.

In addition, the team placed significant emphasis on ensuring the software's extensibility, allowing for continued improvement and customization by a subsequent project group to meet more specific needs and the implementation of even more experiments or use cases in general. The resulting VirtuChemLab project promises to provide an innovative and valuable resource for students and faculty alike.

(Final Presentation)

 

Denis Korugic

March 29, 2023, 2:00 pm, Raum: F1.110

Graphentheoretische Pfadfindung im 3D-Raum

Die Pfadfindung ist für viele Aufgaben ein primäres Problem. Der A* Algorithmus ist in der Lage, effizient Lösungen zu erzeugen. Doch zur Pfadfindung im 3D-Raum eignet sich der Algorithmus nur bedingt. Durch die Bindung an die Kanten des zugrunde liegenden Graphens, werden meist nur sub-optimale Lösungen erzeugt.

Auf Grunde dessen, vergleicht diese Ausarbeitung A* mit zwei Abwandlungen des Algorithmus. Bei den Algorithmen handelt es sich um Theta* und Lazy Theta*. Beide Algorithmen sind nicht an dieselbe Einschränkung wie A* gebunden. Diese Untersuchung steht im Kontext der 3-dimensionalen Pfadfindung und nutzt verschiedene Parameter, welche starke Einflüsse auf die Laufzeit und die Pfadlänge haben. Bei den Parametern handelt es sich um die Übergewichtung der für die Algorithmen genutzten Heuristik, verschiedene Distanzen zwischen den Knoten eines sukzessiv erzeugten Graphen und dem Erlaub oder Verbot von Re-Expansion bereits besuchter Knoten.

(Abschlussvortrag Bachelorarbeit)

 

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.

AND

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.

AND

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.

AND

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.

AND

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.