Dagstuhl Seminar 18331
Algorithmic Foundations of Programmable Matter
( Aug 12 – Aug 17, 2018 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/18331
Organizers
- 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)
Contact
- Michael Gerke (for scientific matters)
- Jutka Gasiorowski (for administrative matters)
Impacts
- Deadlock and Noise in Self-Organized Aggregation Without Computation : article - Daymude, Joshua J.; Harasha. Noble C.; Richa, Andrea W.; Yiu, Ryan - Cornell University : arXiv.org, 2021. - 17 pp..
- Exploiting Nonslip Wall Contacts to Position Two Particles Using the Same Control Input : article : pp. 577 - 588 - Shahrokhi, Shiva; Shi, Jingang; Isichei, Benedict; Becker, Aaron T. - Los Alamitos : IEEE, 2019.
- Motion-planning Using RRTs for a Swarm of Robots Controlled by Global Inputs : article in 2019 IEEE 15th International Conference on Automation Science and Engineering (CASE) : pp. 1163 - 1168 - Joshi, Parth; Leclerc, Julien; Bao, Daniel; Becker, Aaron T. - Los Alamitos : IEEE, 2019.
- Planar Orientation Control and Torque Maximization Using a Swarm With Global Inputs : article : pp. 1980-1987 - Shahrokhi, Shiva; Lin, Lillian; Becker, Aaron T. - Los Alamitos : IEEE, 2019..
- Reshaping Particle Configurations by Collisions with Rigid Objects : article in 2019 International Conference on Robotics and Automation (ICRA) : pp. 4436 - 4443 - Shahrokhi, Shiva; Zhao, Haoran; Becker, Aaron T. - Los Alamitos : IEEE, 2019.
- Robotic Harvesting of a Moving Swarm Represented by a Markov Process : article in 2019 IEEE 15th International Conference on Automation Science and Engineering (CASE) : pp. 1157-1162 - Bhatnagar, Shriya; Soto, Steban; Garcia, Javier; Becker, Aaron T. - Los Alamitos : IEEE, 2019.
- Simulation of Programmable Matter Systems : Using Active Tile-Based Self-Assembly - Alumbaugh, John Calvin; Daymude, Joshua J.; Demaine, Erik D.; Patitz, Matthew J.; Richa, Andrea W. - Cornell University : arXiv.org, 2019. - 33 pp..
- Simulation of Programmable Matter Systems Using Active Tile-Based Self-Assembly : article in DNA 2019: DNA Computing and Molecular Programming : pp. 140 - 158 - Alumbaugh, John Calvin; Daymude, Joshua J.; Demaine, Erik D.; Patitz, Matthew J.; Richa, Andrea W. - Berlin : Springer, 2019 - (Lecture notes in computer science ; 11648 : article).
Generally speaking, 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) has laid the foundations for further progress by bringing together experts from different fields and focusing on expert surveys and breakout groups. In this Dagstuhl Seminar, we plan to build on the success of the previous seminar by expanding its focus on particular challenges that arise from the application areas of programmable matter. This will be achieved by supplying participants with detailed briefing material, and by providing more space for smaller group sessions in which specific problems will be addressed. For this purpose, we intend to bring together a combination of established experts from DNA computing, swarm robotics, computational geometry, and distributed computing. On the senior level, we are inviting leading authorities who are established in more than one of the mentioned topics; on the junior level, we have identified a good selection of highly talented scientists who will be able to advance the field by specific contributions.
Creative Commons BY 3.0 DE
Spring Berman, Sándor Fekete, Matthew J. Patitz, and Christian Scheideler
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 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.
Spring Berman, Sándor Fekete, Matthew J. Patitz, and Christian Scheideler
- Aaron Becker (University of Houston, US) [dblp]
- Spring Berman (Arizona State University - Tempe, US) [dblp]
- Julien Bourgeois (FEMTO-ST Institute - Montbéliard, FR) [dblp]
- Luca Cardelli (Microsoft Research UK - Cambridge, GB) [dblp]
- Kenneth Cheung (NASA - Moffett Field, US) [dblp]
- Joshua J. Daymude (Arizona State University - Tempe, US) [dblp]
- Erik D. Demaine (MIT - Cambridge, US) [dblp]
- David Doty (University of California - Davis, US) [dblp]
- Sándor Fekete (TU Braunschweig, DE) [dblp]
- Roderich Gross (University of Sheffield, GB) [dblp]
- Dan Halperin (Tel Aviv University, IL) [dblp]
- Heiko Hamann (Universität Lübeck, DE) [dblp]
- Kristian Hinnenthal (Universität Paderborn, DE) [dblp]
- Lila Kari (University of Waterloo, CA) [dblp]
- MinJun Kim (SMU - Dallas, US) [dblp]
- Irina Kostitsyna (TU Eindhoven, NL) [dblp]
- Dominik Krupke (TU Braunschweig, DE) [dblp]
- Alcherio Martinoli (EPFL - Lausanne, CH) [dblp]
- Friedhelm Meyer auf der Heide (Universität Paderborn, DE) [dblp]
- Othon Michail (University of Liverpool, GB) [dblp]
- Joseph S. B. Mitchell (Stony Brook University, US) [dblp]
- Nils Napp (Buffalo State - The State University of New York , US) [dblp]
- Ram Prasadh Narayanan (Ben Gurion University - Beer Sheva, IL) [dblp]
- Pekka Orponen (Aalto University, FI) [dblp]
- Matthew J. Patitz (University of Arkansas - Fayetteville, US) [dblp]
- Andréa Richa (Arizona State University - Tempe, US) [dblp]
- Marcel J. M. Roeloffzen (TU Eindhoven, NL) [dblp]
- Trent Rogers (University of Arkansas - Fayetteville, US) [dblp]
- Kay Römer (TU Graz, AT) [dblp]
- Dorian Rudolph (Universität Paderborn, DE) [dblp]
- Christian Scheideler (Universität Paderborn, DE) [dblp]
- Stefan Schmid (Universität Wien, AT) [dblp]
- Arne Schmidt (TU Braunschweig, DE) [dblp]
- Chris Thachuk (California Institute of Technology - Pasadena, US) [dblp]
- Pierre Thalamy (FEMTO-ST Institute - Montbéliard, FR)
- André van Renssen (The University of Sydney, AU) [dblp]
- Jennifer L. Welch (Texas A&M University - College Station, US) [dblp]
Related Seminars
Classification
- artificial intelligence / robotics
- data structures / algorithms / complexity
Keywords
- Distributed algorithms
- computational geometry
- swarm robotics
- DNA computing
- programmable matter
