https://www.dagstuhl.de/18331

12. – 17. August 2018, Dagstuhl-Seminar 18331

Algorithmic Foundations of Programmable Matter

Organisatoren

Spring Berman (Arizona State University – Tempe, US)
Sándor Fekete (TU Braunschweig, DE)
Matthew J. Patitz (University of Arkansas – Fayetteville, US)
Christian Scheideler (Universität Paderborn, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 8, Issue 8 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente

Summary

The term "programmable matter" refers to any substance that can change its physical properties (shape, density, moduli, conductivity, optical properties, etc.) in a programmable fashion. The role of algorithmic foundations of programmable matter continues to grow in importance due to ongoing progress in a wide range of applications. Examples of cutting-edge application areas with a strong algorithmic flavor include self-assembling systems, in which chemical and biological substances such as DNA are designed to form predetermined shapes or carry out massively parallel computations; and swarm robotics, in which complex tasks are achieved through the local interactions of robots with highly limited individual capabilities, including micro- and nano-robots. Progress in these application areas has been achieved through close collaboration with algorithmic theoreticians, enabling the investigation of fundamental problems related to system geometry using methods from the field of computational geometry, and yielding techniques for decentralized computation from the field of distributed computing.

A previous Dagstuhl seminar (16271, Algorithmic Foundations of Programmable Matter) had laid the foundations for further progress by bringing together experts from different fields and focusing on expert surveys and breakout groups. We built on the success of that seminar by expanding its focus on particular challenges that arise from the application areas of programmable matter. For this purpose, we brought together a combination of established experts from DNA computing, swarm robotics, computational geometry, and distributed computing. On the senior level, particants included a number of leading authorities who are established in more than one of the mentioned topics; on the junior level, we had a good selection of highly talented scientists who are able to advance the field by specific contributions.

The seminar started with a plenary introduction of all participants, their research areas and their specific challenges and expectations for the seminar. This was followed by a number of plenary sessions, in which experts gave overviews of broad developments and specific open problems.

  • Erik Demaine gave an overview of challenges for geometric algorithms in the settings of reconfigurable robots (both modular and folding robots that can become any possible shape), robot swarms (which may be so small and simple that they have no identity), and self-assembly (building computers and replicators out of DNA tiles).
  • Dave Doty and Chris Thachuk gave a survey of the basics of experimental and theoretical DNA tile self-assembly, concluding with suggestions for theoretical problems related to programmable control of the nucleation of assemblies. A second part consisted of a survey of DNA strand displacement, including the problem of orienting molecules on a surface with the use of DNA origami and some clever shapes that can "align" themselves into target placements.
  • Andréa Richa presented an overview of self-organizing particle systems, describing programmable matter as an abstract collection of simple computational elements (particles) with limited memory that each execute fully distributed, local, asynchronous algorithms to self-organize and solve system-wide problems such as movement, (re)configuration, and coordination.
  • Aaron Becker discussed the connection between robot swarms and programmable matter, in particular in a setting with a global input to a whole particle swarm, as well as open questions arising from the use of mobile robots to fold 2D planar stock into 3D bricks and to connect the bricks together.

Spread throughout the week, further presentations were given by Spring Berman (applications and open challenges in swarm robotics and a control-theoretic framework for robotic swarms and programmable matter), Julien Bourgeois (realizing programmable matter with modular robots), Luca Cardelli (sequenceable DNA algorithms), Kenneth Cheung (programmable modular periodic metamaterials), Sándor Fekete (coordinated motion planning), Roderich Groß (capabilities of individual units in distributed robotic systems and making programmable matter self-propel efficiently), Dan Halperin (hard vs. easy tasks in multi-robot motion planning), Heiko Hamann (self-assembly and collective construction based on minimal surprise), Lila Kari (DNA smart-tile self-assembly and computational CRISPR), MinJun Kim (engineering particles for robot swarms and modular microrobotics), Alcherio Martinoli (fluid-mediated stochastic self-assembly), Friedhelm Meyer auf der Heide (continuous strategies for swarm robotics), Nils Napp (autonomous construction in unstructured environments), Pekka Orponen (algorithmic design of RNA nanostructures) and Christian Scheideler (a survey on hybrid programmable matter).

A key feature of the seminar was exceptionally intensive, interdisciplinary collaboration throughout the week, based on the use of the new interactive electronic tool coauthor. This tool, specifically developed for use in a workshop-like environment, is an excellent platform that provides a versatile medium for collaborative research discussions, and maintains easily accessible structured records for future reference. We have found that exttt{coauthor} greatly facilitated the work done during the seminar, enabling not just identification of, but also dynamic research work on a number of new topics. These include (A) specific problems in the context of hybrid models for programmable matter, in which there is a set of active micro-robots that can move a large set of simple material tiles that cannot move themselves; (B) aspects of distributed boundary detection for self-organizing swarms; (C) fundamental issues related to the computational equivalence of completely different self-assembly systems and robotic models; and (D) questions of self-aligning geometric shapes that would allow more robust methods for DNA origami and self-assembly. For some aspects, we were able to resolve long-standing open problems; for others, we made significant progress that will undoubtedly lead to future publications. As a consequence, the seminar has triggered a number of new collaborations and a variety of followup projects that will undoubtedly contribute to further collaborative research activities.

License
  Creative Commons BY 3.0 Unported license
  Spring Berman, Sándor Fekete, Matthew J. Patitz, and Christian Scheideler

Related Dagstuhl-Seminar

Classification

  • Artificial Intelligence / Robotics
  • Data Structures / Algorithms / Complexity

Keywords

  • Distributed algorithms
  • Computational geometry
  • Swarm robotics
  • DNA computing
  • Programmable matter

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.