Report an accessibility problem

Self-Organizing Particle Systems

Computing by Programmable Particles

Joshua J. Daymude, Kristian Hinnenthal, Andréa W. Richa, and Christian Scheideler.

[PDF] [Springer] — Book chapter in Distributed Computing by Mobile Entities, pp. 615–681, 2019.

Overview

The vision for programmable matter is to realize a physical substance that is scalable, versatile, instantly reconfigurable, safe to handle, and robust to failures. Programmable matter could be deployed in a variety of domain spaces to address a wide gamut of problems, including applications in construction, environmental science, synthetic biology, and space exploration. However, there are considerable engineering and computational challenges that must be overcome before such a system could be implemented. Towards developing efficient algorithms for novel programmable matter behaviors, the amoebot model for self-organizing particle systems and its variant, hybrid programmable matter, provide formal computational frameworks that facilitate rigorous algorithmic research.

This chapter is a recapitulation of the first four years of theoretical research on the amoebot model. We begin with a fully detailed definition of the amoebot model, differentiating between what we see as core model features versus model extensions. We then describe three algorithmic primitives:

  1. Leader election. How can anonymous, local, distributed particles elect a unique leader?
  2. Spanning forest primitive. How can a particle system organize and move along a specified path?
  3. Distributed binary counters. How can a particle system store values that are too big for any one particle’s memory?

These primitives are useful components of more complex algorithms, including shape formation, shape recognition, object coating, compression, shortcut bridging, and separation. We describe each of these algorithms in detail (including many new figures) and give the highlights of their theoretical analysis (including correctness and runtime bounds).

Resources

  • [Talk Slides] Self-Organizing Particle Systems: an Algorithmic Approach to Programmable Matter. Joshua J. Daymude. 2nd Workshop on Self-Organization in Swarm of Robots (WSSR ’18), Tokyo, Japan. November 4, 2018.

Press

None.

BibTeX

@InCollection{Daymude2019,
  Title     = {Computing by Programmable Particles},
  Author    = {Daymude, Joshua J. and Hinnenthal, Kristian and Richa, Andr\'ea W. and Scheideler, Christian},
  Booktitle = {Distributed Computing by Mobile Entities: Current Research in Moving and Computing},
  Pages     = {615--681},
  Publisher = {Springer},
  Address   = {Cham},
  Year      = {2019}
}

Related Publications

TODO.