Algorithmen für programmierbare Materie in einem physiologischen Medium
Zusammenfassung der Projektergebnisse
Das Ziel des Projekts war es, Algorithmen für programmierbare Materie in einem physiologischen Medium zu studieren. Als Grundlage für unsere Forschungen diente das Amoebot Model, welches von uns 2014 vorgeschlagen worden ist und sich seitdem als sehr nützlich für die algorithmische Forschung im Bereich der programmierbaren Materie erwiesen hat. Neben einigen überfälligen Grundlagenarbeiten am Amoebot Modell konnten wir den Stand der Forschung in mehreren Richtungen erweitern. So konnten wir eine neue Variante des Amoebot Modells entwerfen, in der die Amoebots in der Lage sind, Schaltkreise aufzubauen, und konnten darauf aufbauend Algorithmen entwerfen, die die Laufzeit für verschiedene fundamentale Probleme wie Leader Election, Kompassübereinstimmung und die Bildung grundlegender Formen deutlich verbessert haben. Darüber hinaus haben wir eine Erweiterung zum Studium der Fehlertoleranz entworfen und darauf aufbauend einen ersten Algorithmus für die Bildung einer grundlegenden Form entwickelt, der eine beliebige Anzahl an temporären Ausfällen von Amoebots verkraften kann. Schließlich haben wir auch eine Erweiterung des Amoebot Modells, welches ursprünglich für den 2D-Fall entwickelt worden ist, für den 3D-Fall entworfen und die Machbarkeit des Entwurfs von Algorithmen für dieses Modell demonstriert, indem wir eine Lösung für die Ummantelung eines beliebigen 3D-Objects ohne enge Passagen vorgestellt haben.
Projektbezogene Publikationen (Auswahl)
-
Computing by Programmable Particles. Lecture Notes in Computer Science, 615-681. Springer International Publishing.
Daymude, Joshua J.; Hinnenthal, Kristian; Richa, Andréa W. & Scheideler, Christian
-
Design of nanorobots for exposing cancer cells. Nanotechnology, 30(31), 315501.
Dolev, Shlomi; Narayanan, Ram Prasadh & Rosenblit, Michael
-
Forming tile shapes with simple robots. Natural Computing, 19(2), 375-390.
Gmyr, Robert; Hinnenthal, Kristian; Kostitsyna, Irina; Kuhn, Fabian; Rudolph, Dorian; Scheideler, Christian & Strothmann, Thim
-
Convex Hull Formation for Programmable Matter. Proceedings of the 21st International Conference on Distributed Computing and Networking, 1-10. ACM.
Daymude, Joshua J.; Gmyr, Robert; Hinnenthal, Kristian; Kostitsyna, Irina; Scheideler, Christian & Richa, Andréa W.
-
Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model. Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 223-233. ACM.
Feldmann, Michael; Khazraei, Ardalan & Scheideler, Christian
-
Towards synchronizing radio communication of In-Vivo nanorobots. Nano Futures, 4(3), 035008.
Dolev, Shlomi; Narayanan, Ram Prasadh & Scheideler, Christian
-
Coordinating Amoebots via Reconfigurable Circuits. Lecture Notes in Computer Science, 484-488. Springer International Publishing.
Feldmann, Michael; Padalkin, Andreas; Scheideler, Christian & Dolev, Shlomi
-
Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization. Proceedings of the Eight Annual ACM International Conference on Nanoscale Computing and Communication, 1-2. ACM.
Dolev, Shlomi; Narayanan, Ram Prasadh; Scheideler, Christian & Schindelhauer, Christian
-
The Canonical Amoebot Model: Algorithms and Concurrency Control. DISC 2021: 20:1-20:19.
Joshua J. Daymude, Andréa W. Richa & Christian Scheideler
-
Coordinating Amoebots via Reconfigurable Circuits. Journal of Computational Biology, 29(4), 317-343.
Feldmann, Michael; Padalkin, Andreas; Scheideler, Christian & Dolev, Shlomi
-
Fault-Tolerant Shape Formation in the Amoebot Model. DNA 2022: 9:1-9:22.
Irina Kostitsyna, Christian Scheideler & Daniel Warner
-
Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems. SAND 2022: 12:1-12:19.
Joshua J. Daymude, Andréa W. Richa & Christian Scheideler
-
The Structural Power of Reconfigurable Circuits in the Amoebot Model. DNA 2022: 8:1-8:22.
Andreas Padalkin, Christian Scheideler & Daniel Warner
