We investigate the capabilities and properties of distributed systems that consist of myriads of simple computational particles. These particle systems are supposed to be able to self-organize in order to solve their designated tasks without any central control. Self-organizing particle systems have many interesting applications like coating objects for monitoring and repair purposes and the formation of nano-scale devices for surgery and molecular-scale electronic structures. Tightly interwoven with the term self-organizing particle systems is the notion of programmable matter, which has the ability to change its physical properties (shape, density, moduli, conductivity, optical properties, etc.) in a programmable fashion.
We aim at building a theoretical foundation for self-organizing particles systems that allows rigorous algorithmic research. In doing so, we attempt to provide a universal model that is able to capture many underlying assumptions and physical properties of particle systems in general. In our preliminary work we propose the Amoebot model which we use to investigate shape formation and coating problems in a simple setting.
Project Summary
The goal of this project is to lay the foundations for algorithmic research on self-organizing particle systems. Particle systems are physical systems of simple computational particles that can bond to other particles and that can use these bonds in order to communicate with neighboring particles and to move from one spot to another (non-occupied) spot. These particle systems are supposed to be able to self-organize in order to adapt to a desired shape without any central control. Self-organizing particle systems have many interesting applications like coating objects for monitoring and repair purposes and the formation of nano-scale devices for surgery and molecular-scale electronic structures. While there has been quite a lot of systems work in this area, especially in the context of modular self-reconfigurable robotic systems, only very little theoretical work has been done in this area so far.
This project will prepare the ground for rigorous algorithmic research on self-organizing particle systems by proposing some basic models and solving some basic algorithmic problems in this area. More specifically, the main objectives of this three-year project are (i) to refine an amoeba-inpired model for particle systems in 2D, and to develop appropriate models for particle systems in 3D; and (ii) to develop self-organizing algorithms for the smart paint problem, covering and bridging problems, shape formation problems, and the macrophage problem in 2D and 3D. A transformative, novel thinking approach will be needed if one indeed wants to capture the essential nature of these systems, in some ways mimicking those that already exist in nature.
This project is a natural continuation of the PI's seed one-year NSF EAGER award, and is a necessary component of the work that is needed to lay the grounds for theoretical research on particle systems comprised of computational particles such as nano-sensor nodes.
Intellectual Merit
This three-year project will bridge the gap between applied and theoretical research in self-organizing particle systems both in terms of models and algorithmic research: It will significantly advance the field of self-organizing particle systems from an algorithmic/computational point-of-view.
Broader Impact
The proposed research will have an impact in several respects, such as: (i) bridging the gap between theory and practice in the area of self-organizing particle systems, with impact on many application areas such as microfabrication and cellular engineering; (ii) international collaboration, since we will further foster the successful collaboration with Prof. Scheideler and the U. of Paderborn, Germany; (iii) multidisciplinary activities, since the topics in this proposal will foster collaboration with researchers in transdisciplinary areas such as nano-scale microfabrication, cellular engineering, nano-scale medical applications, biochemistry, etc.; (iv) advancing education at ASU; and (v) enhancing diversity at ASU and at the CS Theory\Algorithms at large.
Project Summary
The goal of this project is to lay the foundations for algorithmic research on self-organizing particle systems. Particle systems are physical systems of simple computational particles that can bond to other particles and that can use these bonds in order to communicate with neighboring particles and to move from one spot to another (non-occupied) spot. These particle systems are supposed to be able to self-organize in order to adapt to a desired shape without any central control. Self-organizing particle systems have many interesting applications like coating objects for monitoring and repair purposes and the formation of nano-scale devices for surgery and molecular-scale electronic structures. While there has been quite a lot of systems work in this area, especially in the context of modular self-reconfigurable robotic systems, only very little theoretical work has been done in this area so far. This project will prepare the ground for rigorous algorithmic research on self-organizing particle systems by proposing some basic models and solving some basic algorithmic problems in this area.
A transformative, novel thinking approach will be needed if one indeed wants to capture the essential nature of these systems, in some ways mimicking those that already exist in nature. Also, there needs to be a better understanding by the broader theoretical community on how research in self-organizing particle systems is conducted, in particular leveraging on research from different communities, in order to achieve a broader advance on theoretical research in this area: The workshop on self-organizing particle systems component of this project aims at exactly that.
More specifically, the main objectives of this one-year project are (i) to develop appropriate models for particle systems; (ii) to develop self-organizing algorithms for smart paint problems; and (iii) to better educate the Computer Science Theory/Algorithms community on self-organizing particle systems.
The pioneering and transformative nature of this project and of theoretical research on particle systems make it a good fit for the scope of the NSF EAGER program.
Intellectual Merit
This one-year project is a first step towards bridging the gap between applied and theoretical research in self-organizing particle systems both in terms of models and algorithmic research: It will significantly advance the field of self-organizing particle systems from an algorithmic/computational point-of-view.
Broader Impact
The proposed research will have an impact in several respects, such as: (i) bridging the large gap between theory and practice in the area of self-organizing particle systems, with impact on many application areas such as microfabrication and cellular engineering; (ii) better educating CS Theory/Algorithms researchers in the field of self-organizing particle systems through the proposed NSF sponsored workshop, which will result in a faster advance of theoretical research in this field; (iii) international collaboration, since we will further foster the successful collaboration with Prof. Scheideler and the U. of Paderborn, Germany; (iv) multidisciplinary activities, since the topics in this proposal will foster collaboration with researchers in transdisciplinary areas such as nano-scale microfabrication, cellular engineering, nano-scale medical applications, biochemistry, etc.; (v) advancing education at ASU; and (vi) enhancing diversity at ASU and at the CS Theory/Algorithms at large.
[DGR15] | Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, Thim Strothmann. An Algorithmic Framework for Shape Formation Problems in Self-Organizing Particle Systems. To appear in 2nd ACM International Conference on Nanoscale Computing and Communication (ACM NANOCOM 2015), 2015. |
[DGS15a] | Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida A. Bazzi, Andréa W. Richa, Christian Scheideler. Leader election and shape formation with self-organizing programmable matter. In DNA Computing and Molecular Programming - 21st International Conference (DNA 21), 2015. |
[DGS15] | Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida A. Bazzi, Andréa W. Richa, Christian Scheideler. Brief announcement: On the feasibility of leader election and shape formation with self-organizing programmable matter. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC 2015), 2015. |
[DGR14] | Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, Thim Strothmann, Shimrit Tzur-David. Infinite Object Coating in the Amoebot Model. CoRR abs/1411.2356, 2014. |
[DDG14] | Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Brief announcement: Amoebot—a new model for programmable matter. 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2014), pp. 220-222. |
[DGR13] | Shlomi Dolev, Robert Gmyr, Andréa W. Richa, and Christian Scheideler. Ameba-inspired self-organizing particle systems. CoRR, abs/1307.4259, 2013. (workshop paper at BDA'13) |
The following video shows a system of particles electing a leader according to the algorithm presented in [DGS15a].
This video shows a system of particles coating a surface. The algorithm is based on concepts presented in [DGR14].