Self-organizing Particle Systems

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.

People

Senior Researchers

(Arizona State University)
(University of Paderborn)

PhD Students

Zahra Derakhshandeh
(Arizona State University)
(University of Paderborn)
(University of Paderborn)

Undergraduate Students

Joshua Daymude
(Arizona State University)
Miles Laff
(Arizona State University)
Alexandra Porter
(Arizona State University)

Collaborators

(Arizona State University)
(Ben-Gurion University)
Shimrit Tzur-David
(Ben-Gurion University)

Funding

Publications

[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)

Simulations

Leader Election

The following video shows a system of particles electing a leader according to the algorithm presented in [DGS15a].

Coating

This video shows a system of particles coating a surface. The algorithm is based on concepts presented in [DGR14].

Line Formation

Hexagon Formation

Triangle Formation