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.

15.05.2024, 14:00 Uhr
Vortragender: Vincent Griebel (Bachelor)