TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 23091

Algorithmic Foundations of Programmable Matter

( Feb 26 – Mar 03, 2023 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/23091

Organizers

Contact

Shared Documents


Schedule

Summary

Algorithmic Foundations of Programmable Matter is an area that aims at designing models and algorithms for materials that can change their physical properties in a programmable fashion or based on external stimuli.

This was the third successful Dagstuhl Seminar on this topic, following seminar 16271, which brought together a number of algorithmic core topics, and seminar 18331, which helped to identify a number of particular challenges. In this third seminar 23091, we continued and extended these first steps, in particular, by considering systems with many small components (such as in physics), very large structures (such as in space), and very complex structures (such as in biology).

Despite having to deal with a number of pandemic and post-pandemic issues (which led to the cancellation of the originally planned seminar 21091 in March 2021), we were able to benefit from a broader range of interaction, including digital preparation: We ran an online event over two half days (accounting for time zones from Japan to the US), bringing together the originally planned group of attendees with additional interested and motivated colleagues. This not only helped to maintain the community spirit and keep in touch about ongoing developments, but it also helped to identify the most motivated members of the community. This preparatory event was successful in the following ways.

  • Participants worked out a refined format for preparing joint work on new research problems.
  • Participants of the digital meeting demonstrated their great commitment to attend: At the end of the second day (i.e., after 8h of online interaction spanning 11h of time difference), the number of live participants was still at 43, i.e., basically undiminished.

This turned out to be extremely helpful for the organization of the renewed seminar 23091, in particular with respect to participation: Despite the inevitable late cancellations due to illness or other unforeseeable emergencies, there was a total of 38 in-person participants.

Another key feature of the seminar was to again make use of the interactive electronic tool coauthor, which allowed exceptionally intensive and interdisciplinary collaboration throughout the week, allowing dynamic formulation and development of research problems, ideas, progress and formulation of results. Thus, 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.

On the content side, a number of research areas were brought together, with theoretical connections to the areas of Distributed Computing, Computational Geometry, and Self-Assembly. In addition, a number of application areas provided further directions, including Swarm Robotics with their methods for dealing with systems composed of many individual components that together form complex and reconfigurable structures; Engineering and Physics, with a variety of technologies and applications for developing flexible and innovative materials and constructions; and Biomolecular applications with a spectrum of real-life scenarios.

Overall, we brought together a combination of established experts from the mentioned areas. On the senior level, participants 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 will continue to advance the field by specific contributions.

Making use of the excellent experiences during the previous seminar, 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 over broad developments and specific open problems.

  • Amira Abdel-Rahman gave an excellent survey over the challenges and perspectives of using self-replicating hierarchical robotic swarms in application areas such as space missions.
  • Dan Halperin gave an overview of geometry at the service of robotics, ranging from snapping fixtures to multi-robot coordination.
  • Damien Woods gave an introduction to practice and theory of self-assembly using synthetic DNA, and then went on to give an overview of work going on in the wet lab, covering a range of different practical topics.
  • Kay Römer described scalable real-time localization for robotic ensembles, providing insights into practical hardware considerations.
  • Benoît Piranda gave an overview of ongoing work on both the development of real-world Catoms (as a powerful model for producing programmable matter platforms), as well as their simulation and visualization.
  • Tom Peters (with support by both Irina Konstitsyna and Christian Scheideler) described the state of the art and ongoing challenges in the amoebot model.

Further presentations were given by Jo Ellis-Monaghan (on DNA self-assembly), Sándor Fekete (describing work on coordinating large ensembles of particles at extreme dimensions, from space to targeted drug delivery), Timothy Gomez (on two-handed self-assembly), Christian Scheideler (on reconfigurable circuit extension), and Giovanni Viglietta (describing programmable matter from fractal formation to genetic programming).

Extending precedent, we put particular emphasis on sessions and presentations that were focused not only on previous and ongoing work, but also on coming challenges, by running a considerable number of open problem sessions. A variety of open problem sessions were headed by Amira Abdel-Rahman (path planning for assembly and reconfiguration), Yuval Emek (self-stabilizing chemical reaction networks), Dan Halperin (minimum number of control alterations), Tanja Kaiser (open-ended evolution), Maria Kokkou (leader election with faults), Irene Parada (fast parallel reconfiguration), Nicolas Schabanel (DNA origami and experiments), Cynthia Sung (self-folding structures), and Ryuhei Uehara (slide-and-pack puzzles).

Copyright Aaron Becker, Sándor Fekete, Irina Kostitsyna, Matthew J. Patitz, and Damien Woods

Motivation

“Algorithmic Foundations of Programmable Matter” is an area that designs models and algorithms for materials that can change their physical properties in a programmable fashion or based on external stimuli. Many research areas have already been brought together, with connections to distributed computing, computational geometry, self-assembly, and swarm robotics, but the number of problems that have been identified so far is limited.

In this Dagstuhl Seminar, we will significantly broaden the range of problems by seeking inspiration from researchers in areas where programmable matter promises to have a major impact in the future: engineering, physics and biological systems. Each of these areas also has its specific characteristics and challenges, making them particularly interesting for this seminar: physics with its very small components, space technologies and engineering with their extremely large structures, and biology with its extremely complex structures. As a second objective, we will intensify interactions between communities towards concrete outcomes, which was successfully initiated during the previous Dagstuhl Seminar "Algorithmic Foundations of Programmable Matter" (18331).

Copyright Aaron Becker, Sándor Fekete, Irina Kostitsyna, Matthew J. Patitz, and Damien Woods

Participants

Related Seminars
  • Dagstuhl Seminar 16271: Algorithmic Foundations of Programmable Matter (2016-07-03 - 2016-07-08) (Details)
  • Dagstuhl Seminar 18331: Algorithmic Foundations of Programmable Matter (2018-08-12 - 2018-08-17) (Details)

Classification
  • Computational Geometry
  • Data Structures and Algorithms
  • Robotics

Keywords
  • Distributed algorithms
  • computational geometry
  • robotics
  • DNA computing
  • programmable matter