Oberseminar SS 2024
17.04.2024, 14:00 Uhr, F2.419,
Vortragender: Sebastian Korzeczek (Master)
Title: Shape Formation with Passive Objects and Joint Movements in the Amoebot Model
Abstract: In the shape formation problem, the goal is to transform an initial shape into a given target shape. The scale of the formed target shape is maximal with respect to the number of passive objects in the initial shape. Such an algorithm was formalized in the Amoebot Model with joint movements and partially implemented in the AmoebotSim2.0 simulation environment. The shape formation algorithm presented here is capable of forming the target shape in O(m^2) rounds, where m is the number of passive objects in the initial shape.
24.04.2024, 14:00 Uhr, F2.419,
Vortragender: Matthias Artmann (Master)
Title: On the Shape Containment Problem within the Amoebot Model with Reconfigurable Circuits
Abstract: Programmable matter is envisioned as a material that can alter its physical properties
(shape, conductivity, appearance etc.) and react to external stimuli intelligently to
fulfill a large variety of tasks in construction, maintenance, medicine and other
application domains. Such materials are often imagined as large numbers of small
computational entities, called particles, with very limited sensing, communication and
movement abilities. By modeling programmable matter as distributed systems, we can study
its theoretical capabilities and limitations under varying assumptions and independent of
physical implementations.
The problem of shape formation, i.e., reorganizing an arbitrary initial configuration of
particles into a desired shape, has been studied extensively in various models due to its
high practical relevance. We consider the related problem of shape containment, where the
particles have to find the maximum scale at which a given shape can be represented by the
initial configuration (i.e., without movement) and identify a subset of particles
representing the maximally scaled shape. A shape containment solution could serve as a
preparation for fast shape formation algorithms or other complex procedures, but the
problem has not been studied in the context of programmable matter so far.
In this master's thesis, we present solutions to the shape containment problem in the
amoebot model, using the model's reconfigurable circuits extension to enable fast
communication over long distances. In addition to a solution of the most general problem
case, we identify several classes of shapes and initial configurations with more
efficient solutions, achieving sublinear runtimes in the number of particles. The final
presentation of this thesis gives an overview of the considered problem cases and
presents the key algorithmic ideas used to solve these cases efficiently.
08.05.2024, 14:00 Uhr
Vortragender: Dominik Delgado Steuter (Bachelor)
Title: Realizing Concurrency on Top of the Microkernel seL4 via Improved Threads
Abstract: What is the best way to make programs concurrent? How can threads be made more efficient and easier to use? In this paper, threads and the event model are compared for realizing concurrency in programs and opportunities for improvement of threads are presented. The microkernel seL4 is showcased and the threads it provides are implemented and analyzed regarding their ease of use and performance. Can they be improved? Also, a concurrency-optimal binary search tree is showcased and a partial implementation of it in the programming language C is discussed.
15.05.2024, 14:00 Uhr
Vortragender: Vincent Griebel (Bachelor)
Titel: Designing a financial system on a centralized blockchain with distributed backend
Abstract:Spätestens seit dem Bitcoin-Boom im Jahr 2020 haben Kryptowährungen die breite Öffentlichkeit erreicht. Doch obwohl einige Länder wie El Salvador Bitcoin sogar als offizielles Zahlungsmittel eingeführt haben, bleiben die Anwendungsmöglichkeiten eher limitiert. Gründe dafür lassen sich unter anderem in den Gegebenheiten des Bitcoin Protokolls finden. So ist die maximale Anzahl der Transaktionen auf zehn pro Minute beschränkt, und alle Transaktionsdaten sind öffentlich für jedermann zugänglich. Wie könnte man ein Zahlungsmittel schaffen, das einer Kryptowährung ähnelt, aber einige dieser Probleme löst?
In der Präsentation wird zuerst einmal Bitcoin analysiert, um zu verstehen, woher einige der Probleme kommen. Danach wird eine zentrale Blockchain konstruiert, welche keinen speziellen Konsensus Mechanismus benötigt. Zum Schluss wird noch betrachtet, wie die Beträge in Transaktionen so verschlüsselt werden können, sodass der Server die Transaktionen validieren, aber nichts weiteres über sie herausfinden kann.
26.06.2024, 14:00 Uhr
Vortragender: Varun Maitreya Eranki, Master
Titel: Fever: Optimal Responsive View Synchronisation
Abstract: In this thesis an exploration into the role of hardware and software combination for improving Byzantine Fault Tolerant State Machine systems with integration of novel Fever algorithm. The role of partial synchrony model in a consensus decision making, can improve the reliability and resiliency in the event of faults. Tolerance of such a system is explored practically in the presence of adversarial behaviour. An addition of cost effective precision clock overall improves the Fever algorithm.
17.07.2024, 14:00 Uhr
Vortragender: Andreas Padalkin
Titel: Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter
Abstract: In this talk, we study the computation of shortest paths within the \emph{geometric amoebot model}, a commonly used model for programmable matter. Shortest paths are essential for various tasks and therefore have been heavily investigated in many different contexts. For example, in the programmable matter context, which is the focus of this paper, Kostitsyna et al.\ have utilized shortest path trees to transform one amoebot structure into another [DISC, 2023]. We consider the \emph{reconfigurable circuit extension} of the model where this amoebot structure is able to interconnect amoebots by so-called circuits. These circuits permit the instantaneous transmission of simple signals between connected amoebots.
We propose two distributed algorithms for the \emph{shortest path forest problem} where, given a set of $k$ sources and a set of $\ell$ destinations, the amoebot structure has to compute a forest that connects each destination to its closest source on a shortest path. For hole-free structures, the first algorithm constructs a shortest path tree for a single source within $O(\log \ell)$ rounds, and the second algorithm a shortest path forest for an arbitrary number of sources within $O(\log n \log^2 k)$ rounds. The former algorithm also provides an $O(1)$ rounds solution for the \emph{single pair shortest path problem} (SPSP) and an $O(\log n)$ rounds solution for the \emph{single source shortest path problem} (SSSP) since these problems are special cases of the considered problem.
24.07.2024, 14:00 Uhr
Vortragender: Gbadamosi Damiloda, Master (bei Matthias Fischer)
Title: Implementation and Evaluation of Iterative Deepening A* Algorithm on a 3D game map.
Abstract: Path-finding algorithms are critical for developing interactive games, providing effective routes for characters to perform in virtual environments with complex scene structures. This thesis investigates the performance and suitability of three prominent path-finding algorithms: A*, Dijkstra, and Iterative Deepening A* (IDA*) which are practically applicable in a game prototype environment. This paper includes a study of six scenarios, each with difficult passages like obstacle blockages and complex terrain.
The introduction provides an in-depth explanation of the game mechanics and how the IDA* algorithm is combined with the iterative deepening procedure, demonstrating the role of the algorithm in path optimization. My strategy is to integrate the algorithms within the game layers, where significant aspects such as memory consumption, time performance, route length, and the appearance of smooth paths are considered. Visual explanation of the algorithm implementation is due to the screenshots of the coding process.
Scenario-delimited metrics from the evaluation give a detailed view of the scenarios' computational complexity. A* and Dijkstra algorithms can achieve consistently and reliably better performance as the algorithms enhance the adaptability of different gaming environments. On the other hand, IDA* demonstrates different efficiency levels when coping with scenario complexity, but there are unique improvements for the scenarios that embrace the IDA* iterative deepening strategy.
Moreover, another aspect of the analysis is the study of each algorithm's pros and cons. The advantages and disadvantages include the space and time complexity of each algorithm, heuristic function and limitations of the algorithms' optimization. The algorithm comparison reveals the usage of grid and octree in different scenes, making it easy for game developers to choose a suitable algorithm for their purpose.
The study's implications highlight the relevance of choosing algorithms according to the gaming system's environmental features. Developing an algorithm that will optimize the path-finding mechanisms and strike the right balance between computational effort and path-finding accuracy can be a task. This research is a step in the path-finding process in game development; it offers an elementary framework for further exploration and innovation in the design of interactive games.
24.07.2024, 14:45 Uhr
Vortragender: Natiq Sihab Akram, Master
Title: Anomaly Detection in N-Sensor Data for Accurate Field Mapping Using Machine Learning
Abstract: This study presents a detailed examination of anomaly detection within N-Sensor data, aiming to enhance precision agriculture by refining field boundary delineation using machine learning techniques integrated with geospatial analysis. Focusing on Yara International’s N-Sensor and Varda’s Global Field ID system, this study addresses challenges posed by redundant data through spatial joins that effectively detect farm-relevant data points and remove non-farm points, significantly improving data accuracy. Machine learning limitations were encountered, notably a high rate of false negatives due to an imbalanced dataset for non-farm points. However, applying spatial joins offers a solution for removing non-farm points, optimizing data quality, and providing better computational efficiency. Consequently, this approach supports more accurate agricultural practices.
16.08.2024, 13.00 Uhr, F2.419
Vortragender: Adarsch Manepalli, Master (bei Matthias Fischer)
Title: Optimizing Unreal Engine’s Procedural Content Generation for Accurate Visualization of Satellite-Derived Terrains: Methods, Implementation, and Applications
Abstract: Data has become increasingly important in many scientific and technical domains, necessitating good administration and use strategies. This thesis proposes an innovative pipeline for automating tree species classification while generating realistic virtual landscapes using high-resolution satellite imagery and deep learning algorithms. The landscape of geospatial analysis and procedural content development has shifted substantially as technology has advanced. This study applies these breakthroughs to improve the realism and ecological accuracy of virtual environments. The proposed pipeline incorporates the Detectree2 package for precise tree crown delineation, utilizes custom CNN models and pre-trained backbone architectures for species classification, and employs a coordinate conversion process to translate classified tree locations into Unreal Engine for procedural tree placement. Challenges such as data acquisition limitations and computational demands are addressed. The pipeline’s potential applications are vast, including ecological studies, forest management, urban planning, and immersive visualization. This work advances geospatial analysis and procedural content generation, contributing an innovative approach to creating immersive and accurate virtual urban environments. This approach supports more precise and efficient analysis and visualization of forest ecosystems, paving the way for sustainable urban tree management and conservation efforts.
21.08.2024, 14.00 Uhr
Vortragender: William Lepp, Bachelor
Title: A Survey of Cryptocurrencies
Abstract: In this talk, the three cryptocurrencies Bitcoin, Ethereum and Algorand will be compared. After an illustration of the so-called double-spending problem, a central problem for cryptocurrency, we will give a brief introduction to each of the three cryptocurrencies and show differences in how each system solves the double-spending problem.
As the double-spending problem is a consensus problem, we focus on the consensus mechanism used in each system.
Furthermore, we will compare the cryptocurrencies regarding their performance in terms of decentralization, scalability and security, also known as the blockchain trilemma. Finally, are comparison of the systems considering economic and ecological aspects will be presented.
23.09.2024, 14.00 Uhr
Vortragender: Tristan Lippold, Bachelor
Title: Maximum matching in a supervised peer-to-peer network with adversarial peers
Abstract: For a graph G a subset of edges M is called a matching if no two edges in M share a common vertex. A matching M is called a maximum matching if ∄ matching M':M'>M. In this paper a supervised peer-to-peer algorithm for finding a maximum matching in a general graph is presented. Furthermore, methods will be introduced to handle adversarial behaviour from a certain fraction of adversarial peers. Although the total work of the algorithm is in On5logn, the span of the task graph lies in Onlogn and is therefore promising. In addition, first ideas for converting the supervised peer-to-peer algorithm into a peer-to-peer algorithm will be described.
23.10.2024, 15.00 Uhr
Vortragende: Roja Raj, Master
Title: Hexagon Shape Formation in the Amoebot Model with Immobilized Particles
Abstract: We explore the amoebot model, a distributed computing framework for programmable matter, by extending the model to solve the hexagon shape formation problem in the connected system with immobilized and non-immobilized particles. We consider that immobilized particles cannot move but can communicate with neighboring particles, while non-immobilized particles can both move and communicate. The central objective is to combine all non-immobilized particles to form a hexagon while ensuring that it does not include or surround the immobilized particles. In this thesis, we propose the HEX-IM algorithm, which is structured into multiple phases that guide scattered non-immobilized particles to navigate successfully around the immobilized particles and form a hexagon while maintaining connectivity and alignment. This research provides insights into shape formation mechanisms within complex particle configurations and has potential applications in various felds such as medicine, material science, and robotics. This presentation gives an overview of the proposed algorithamic idea to solve the issues with an efficient solution.
06.11.2024, 14.00 Uhr
Vortragender: Paul Bergmann, Master
Title: Closing Holes in Dodecahedron Tiles Programmable Matter in a Bounded Environment Hybrid Model
Abstract: Programmable matter, a system of connected objects (robots) that collaboratively solve
tasks, has promising potential applications from nano-scale surgeries to shape-chaining
matter fulfilling all kinds of tasks. Currently, developing a general framework for the
shape reconstruction of programmable matter is the main challenge from an algorithmic
point of view. As an intermediate step during the shape reconstruction, it might be rea-
sonable to transform the matter into a simple (hole-free) structure since this generally
simplifies finding a tile that can be removed and placed in another spot without losing
connectivity in the configuration. We present the first algorithm for building such sim-
ple structures inside the bounding box of the start configuration for dodecahedron tile
programmable matter in the passive tile (hybrid) model of Hinnenthal et al. [HRS20].
The algorithms presented run with logarithmic memory depending on the number of
tiles and O(n^4) time or constant memory and four pebbles in O(n^5) time, respectively.
20.11.2024, 14.00 Uhr
Vortragender: Vineet Vasishta Eranki, Master, bei Matthias Fischer
Title: Improving the precision and performance of a 3D path finding algorithm for virtual environments
Abstract: This thesis improves a three-dimensional pathfinding algorithm in
virtual environments, achieving better performance and visual
clarity. The pathfinding algorithm processes scenes in 3D space into
a set of interconnected graphs and then
uses iterative deepening A* to find the shortest path between the
start node and the goal node. To improve the existing algorithm,
five key enhancements are made. The first goal ensures that there is
no path between the start and goal nodes when these nodes are placed
in different disconnected graph components. The second goal uses a
directed graph structure for traversal of a sloped terrain, which
consists of both uphill and downhill movement for different agents
like person, bicycle, car, and truck based on their movement
constraints. The third goal evaluates different heuristic functions,
including Manhattan, Chebyshev, Diagonal, and Euclidean distance, to
determine the better heuristic to improve execution time and to find
the shortest path. The fourth goal ensures that a visually appealing
straight line path is found between the start
and goal nodes. The fifth goal ensures that graphs are processed
faster by using multithreading.
27.11.2024, 14.00 Uhr
Vortragende: Anna Dröge, Bachelor
Title: Dispersion of Autonomous Robots in simple Non-Convex Polygonal Areas
Abstract: This thesis will analyse the dispersion of a swarm of N autonomous robots on areas of the form of non-convex polygons without holes.
The robots will act according to the model chosen by Schmidt [1] in his thesis:
Thus, robots will operate according to the LUMINOUS model with the FSYNC model used as a scheduler.
To cover the polygon, robots first will build a chain of stationary robots at a distance of 1 upon the boundary and second form a grid consisting of squares with side length 1 upon the bounded area. The formation of the grid will take place in parts, separately for each (ortho-)convex part of the polygon.
The thesis includes a proof of the algorithms' correctness. Moreover, ideas are presented on how the algorithm can be adapted to similar scenarios.