Detailseite
Projekt Druckansicht

Algorithmen für selbstorganisierende Partikelsysteme

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2014 bis 2020
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 240633587
 
Erstellungsjahr 2018

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung