Oberseminar WS 2024/2025
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.
04.12.2024, 14.00 Uhr
Vortragender: Oliver Oster, Bachelor
Title: AWS-Based Implementation of Supervised Distributed Computations
Abstract: In this thesis we define a supervised distributed peer-to-peer system and implement it using services offered by the cloud service provider AWS. After laying out the foundations of the proposed system and the concepts used for its implementation, every component is deployed in AWS for simulations of two presented algorithm executed within the supervised distributed peer-to-peer system. The results are evaluated and a conclusion is drawn founded on the results of the simulations and the insights gathered during the development and writing process of this thesis.