Winter Term 2020/21


March 31, 2021, 2:00 pm (video conference)

Achieving global dispersion with a swarm of mobile robots is difficult if these robots only have local information and execute a distributed algorithm. In the final presentation of the project group LOCOMOTION we present several algorithms designed to disperse robots inside different regions to uniformly cover the given area, and evaluate the algorithms theoretically and empirically with the simulation environment developed during the project group. We consider robots with limited viewing range operating synchronously in Look-Compute-Move cycles and mostly focus on the two-dimensional plane but also present one algorithm dispersing robots in three dimensions.

(Final Presentation)

Jan-Luca Hansel

March 26, 2021, 2:00 pm (video conference)

3D Motion Planning in Virtual Environments

Motion Planning describes the automated computation of collision-free paths for an agent in a given environment. Such algorithms can have a manifold of different applications and can be used wherever manual path creation is infeasible. The thesis proposes such an algorithm for arbitrary scenes in 3D space and a selection of four different agents that vary in their climbing capabilities. To solve the problem, input scenes are transformed into graphs. This involves the computation of mesh intersections and the merging of graphs based on these intersections. Searching for paths can then be done by classical graph searching techniques. In this case, Iterative Deepening A* was used. In my talk, I'll present the main ideas behind the proposed algorithm. Additionally, the evaluation of the implementation and a selection of possible extensions and improvements is presented.

(Final Presentation Bachelor's Thesis)

Jonas Harbig

January 13, 2021, 2:00 pm (video conference)

Dispersion -- A Swarm Formation Problem

Swarm formation problems describe a set of final configurations which must be reached by a swarm of robots starting in an arbitrary initial configuration. Usually the robots are assumed to have very low capabilities and act locally, i.e. without global control. There are two large classes of such problems that we are interested in: Contraction and Expansion. The former minimizes a given structure, e.g., for efficiency. Among others, the Gathering Problem is well known, where all robots are tasked to meet at the same point. In contrast, Expansion problems have the goal to maximize the structure, e.g., to reach a good coverage. A notable subclass of Expansion deals with the goal to spread all robots evenly over a large area, it is sometimes referred with Deployment or Dispersion. This is a very broad description which opens a lot of questions. How do we define Dispersion? What is the target function? Under which model is the problem interesting to consider? In my talk I will discuss these questions and point out open problems in this field.

Sascha Brandt

December 9, 2020, 2:00 pm (video conference)

Hybrid point-based and Clustered Rendering

In this talk I will discuss our current research progress on a hybrid point/triangle rendering algorithm for complex scenes.

The main idea is to use our progressive farthest-point sampling algorithm to cluster a 3D-polygonal-object into a set of small triangle clusters that are each associated to one sample point. During a virtual walk-through, we then render surfels for distant objects and switch to triangle clusters as we move closer. We use a similar idea to build a wide hierarchy of clusters for large complex scenes, where each surfel in a progressive surfel list represents an entire sub-cluster of scene objects which are again approximated in the same way.

Till Knollmann

November, 04, 2020, 2:00 pm (video conference)

Multi-Commodity Online Resource Allocation

We study extended versions of well-known online resource allocation problems (e.g., Online Page Migration, Online Facility Location) by extending them with multiple commodities. Online resource allocation problems have a wide area of applications in network settings since they capture the difficulty of determining the location of resources to ensure low access and management cost under unknown request sequences.

In our research, we notice that many well-known online resource allocation models implicitly assume only a single commodity that is involved. The real world suggests that in many applications truly there are multiple commodities. Multiple commodities model the existence of multiple different resources, e.g., different services, in the same network. Combining several commodities together usually comes with a lower cost compared to considering the commodities separately. For example, instantiating a virtual machine embedding two services is probably less costly than instantiating virtual machines for each of them. Thus, trivial solutions that use single-commodity online algorithms for each commodity miss out on saving overall cost, i.e.; in general a non-trivial competitive ratio is achievable in such extended models.

In this talk, we present how multiple commodities can be introduced in established models in online resource allocation. We present two example problems – the Online Page Migration Problem and the Online Facility Location – for which we already introduced multi-commodity models along with results regarding the competitive ratio. Additionally, we outline our future research directions mainly involving further generalizations of the Multi-Commodity Online Facility Location Problem.

Jannik Castenow

November, 04, 2020, 3:00 pm (video conference)

Local Strategies for Contraction & Dispersion Problems of Mobile Robots

In this talk, I present the current state of my PhD project settled in the research area of distributed computing by mobile robots.

Robots are modeled as points in a Euclidean space (mostly the Euclidean plane) and the robot capabilities are rather restricted: The robots do not communicate, have no agreement on their local coordinate systems and can only see up to a constant distance around themselves. The goal ist that all robots together achieve a common task which is typically a formation task: the robots have to move such that their positions represent a certain formation.

My talk is divided into two parts. In the first part, I present current and future work about robot dispersion problems. Such problems demand that the robots spread out and build a formation of maximal size according to some constraints.Specifically, I present the Max-Chain-Formation problem in which a chain of robots has to be transformed into a chain of maximal length without losing the connectivity of the chain.

In the second part, I consider robot contraction problems demanding the robots to build a formation of minimal size. The most popular example is the Gathering problem in which all robots have to gather at a single, not predefined point. I introduce several research questions around the Gathering problem, for instance „Is it possible to gather the robots in a subquadratic number of synchronous rounds?“ Up to now the best known algorithms have a quadratic lower bound. Further questions involve a more profound understanding of gathering strategies: Is it possible to find a class of robot gathering strategies having a (conjectured) optimal runtime? Beyond that, I consider robots in higher dimensional spaces.

For all these problems, I present the results that are already achieved, current research and possible future directions.

Yulia Dziuba

October, 13, 2020, 2:00 pm, Room: F0.225 (video conference)

Die exponentielle Zeit Hypothese

Alle bekannten und nichttrivialen Algorithmen für das NP–vollständige Problem haben eine exponentielle Laufzeit. Daher wird vermutet, dass dieses Problem nicht in subexponentieller Zeit $poly(n)\cdot 2^{o(n)}$ entscheidbar ist, wobei $n$ die Anzahl der Variablen in der booleschen Formel ist. Diese Vermutung wird **die exponentielle Zeit Hypothese (EZH)** genannt. In dieser Arbeit wird diese Hypothese und ihre Auswirkung auf andere NP–vollständige Probleme untersucht. Ein Beispiel eines exponentiellen Algorithmus für $k$–SAT ist der Algorithmus von Monien und Speckenmeyer, welcher in dieser Arbeit ebenfalls im Detail betrachtet wird. Der Algorithmus hat Laufzeit , wobei $\alpha_k$ die größte Zahl ist, so dass $\alpha_k=2-\frac{1}{(\alpha_k)^{k-1}}$ gilt. Für $k=3$ ist $\alpha_3=1,6181$ und die Laufzeit ist $\mathcal{O}(poly(n)\cdot 1,6181^n)$.

Ein wichtiges Ergebnis, das wir beweisen, ist das Sparsification Lemma. Das Lemma zeigt die Existenz eines Algorithmus, der für beliebige $\varepsilon > 0$ eine beliebige boolesche Formel in Form in eine Disjunktion von $2^{\varepsilon n }$ $k$–KNF Formeln modifiziert, so dass jede dieser Formeln nur $\mathcal{O}(n)$ Klauseln hat. Wir zeigen, dass aus diesem Lemma eine größere untere Schranke für $k$–SAT unter der EZH folgt: $k$–SAT hat keinen Algorithmus mit Zeit$\mathcal{O}(poly(n+m)\cdot 2^{\varepsilon (n+m)})$, wobei $n+m$ die Anzahl der Variablen und Klauseln in der booleschen Formel ist. Mit Hilfe dieses Ergebnisses werden untere Schranken für einige NP-vollständige Probleme bestimmt.

Es werden folgende NP-vollständige Probleme betrachtet: Das Knotenüberdeckungs-, das gerichtete Hamiltonkreis-, das 3-Färbbarkeits- und das unabhängige Menge-Problem. Es wird gezeigt, dass diese Probleme unter der EZH keinen subexponentiellen Algorithmus, also keinen Algorithmus mit Zeit $poly(n+m)\cdot 2^{o(n+m)}$, haben, wobei $n+m$ die Anzahl der Knoten und der Kanten im Graphen ist.

Außerdem werden NP–vollständige Probleme in planaren Graphen betrachtet: Das planare , das planare Knotenüberdeckungs-, das planare unabhängige Menge- und das planare Hamiltonkreisproblem in gerichteten und ungerichteten Graphen. Für diese Probleme wird eine kleinere untere Schranke bestimmt: Es wird gezeigt, dass diese Probleme unter der EZH keinen Algorithmus mit Zeit $poly(n+m)\cdot 2^{o(\sqrt{n+m})}$ besitzen, wobei $n+m$ die Anzahl der Knoten und Kanten ist.

Abschließend wird ein subexponentieller Algorithmus mit Zeit $2^{\mathcal{O}(\sqrt{n})}$ für das NP–vollständige Problem unabhängige Menge in planaren Graphen entwickelt.