Algorithms for self-organizing particle systems
Final Report Abstract
Ziel des beantragten Projekts war es, die Grundlagen für die algorithmische Forschung im Bereich selbstorganisierender Partikelsysteme zu legen. In unserem Kontext sind Partikelsysteme physikalische Systeme, die aus einfachen intelligenten Partikeln bestehen, die sich an andere Partikel binden können und welche diese Verbindungen nutzen können, um Informationen auszutauschen und um sich entlang der Oberfläche der Partikelstruktur zu bewegen. Diese Partikelsysteme sollen in der Lage sein, sich selbst zu organisieren, um z.B. eine gewünschte Form einzunehmen oder ein Objekt zu ummanteln. Selbstorganisierende Partikelsysteme haben viele interessante Anwendungen wie z.B. im Bereich intelligenter, adaptiver Materialien, der Konstruktion, Überwachung und Reparatur komplexer mikroskopischer Objekte und der minimal invasiven Chirurgie. Obwohl es bereits umfangreiche praktische Arbeiten in diesem Bereich gibt, speziell im Bereich modularer selbstkonfigurierender Robotersysteme, gibt es bisher nur sehr wenige theoretische Arbeiten in diesem Gebiet. Unser Ziel war es, die Grundlagen für eine rigorose algorithmische Forschung im Bereich selbstorganisierender Partikelsysteme zu legen, indem wir grundlegende Modelle und grundlegende algorithmische Probleme in diesem Bereich angehen. Ausgangspunkt unserer Forschungen war die Entwicklung eines neuen Modells für selbstorganisierende Partikelsysteme, das wir Amoebot Modell genannt haben. Wir nehmen in diesem Modell an, dass das Partikelsystem aus homogenen, intelligenten Einheiten (bzw. Partikeln) besteht, die wir Amoebots nennen. Die Amoebots konnen eine beliebige 2-dimensionale Struktur einnehmen, sofern diese auf das trianguläre Gitter G∆ abbildbar ist, d.h. jedem Amoebot ein eindeutiger Knoten im triangulären Gitter zugeordnet werden kann. Die Struktur ist dabei zusammenhängend, wenn die Teilmenge der Knoten in G∆, auf die die Amoebots abgebildet sind, zusammenhängend ist. Amoebots konnen sich über Expansionen und Kontraktionen fortbewegen. Dabei muss allerdings im Algorithmus beachtet werden, dass dadurch der Zusammenhang des Systems nicht gefährdet wird. Die Motivation hinter dieser Forderung ist, dass ansonsten die getrennten Partikelstrukturen auseinanderdriften konnten. Aufbauend auf dem Amoebot Modell konnten wir, wie im Antrag vorgesehen, verschiedene Algorithmen für die Ummantelung von Objekten und die Bildung einer vorgegebenen Form vorstellen. Hauptergebnisse sind dabei universelle Verfahren fir die Ummantelung von Objekten und universelle Verfahren für die Bildung einer vorgegebenen Form. Unsere Ergebnisse haben bereits einige Aufmerksamkeit in der Wissenschaft auf sich gezogen. So sind Artikel dazu im MIT Technology Review (Januar 2016) und in den ACM TechNews (Marz 2017) erschienen. Weiterhin haben wir bereits unter anderem ein Dagstuhl Seminar zu den Grundlagen programmierbarer Materie im Juli 2016 organisiert, und ein weiteres Dagstuhl Seminar zu diesem Thema im August 2018. Fortführende Arbeiten sind bereits in verschiedenen Richtungen unterwegs. So arbeiten wir zurzeit auch an hybriden Systemen, in denen aktive Einheiten auf passiven Einheiten agieren.
Publications
- An Algorithmic Framework for Shape Formation Problems in Self-Organizing Particle Systems. In Proc. of the 2nd International Conference on Nanoscale Computing and Communication (NANOCOM 2015), pp. 21:1–21:2, 2015
Zahra Derakhshandeh, Robert Gmyr, Andrea W. Richa, Christian Scheideler, and Thim Strothmann
(See online at https://doi.org/10.1145/2800795.2800829) - Leader Election and Shape Formation with Self-organizing Programmable Matter. In Proc. of the 21st International Conference on DNA Computing and Molecular Programming (DNA 2015), pp. 117–132, 2015
Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida A. Bazzi, Andrea W. Richa, and Christian Scheideler
(See online at https://doi.org/10.1007/978-3-319-21999-8_8) - On the Runtime of Universal Coating for Programmable Matter. In Proc. of the 22nd International Conference on DNA Computing and Molecular Programming (DNA 2016), pp. 148–164, 2016
Zahra Derakhshandeh, Robert Gmyr, Alexandra Porter, Andrea W. Richa, Christian Scheideler, and Thim Strothmann
(See online at https://doi.org/10.1007/978-3-319-43994-5_10) - Universal Shape Formation for Programmable Matter. In Proc. of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), pp. 289–299, 2016
Zahra Derakhshandeh, Robert Gmyr, Andrea W. Richa, Christian Scheideler, and Thim Strothmann
(See online at https://doi.org/10.1145/2935764.2935784) - Improved Leader Election for Self-organizing Programmable Matter. In Proc. of the 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2017), pp. 127–140, 2017
Joshua J. Daymude, Robert Gmyr, Andrea W. Richa, Christian Scheideler, and Thim Strothmann
(See online at https://doi.org/10.1007/978-3-319-72751-6_10) - Universal coating for programmable matter. Theoretical Computer Science 671: 56–68 (2017)
Zahra Derakhshandeh, Robert Gmyr, Andrea W. Richa, Christian Scheideler, and Thim Strothmann
(See online at https://doi.org/10.1016/j.tcs.2016.02.039)
