binary-counter

In this dissertation defense, I treat three questions on emergent behavior in programmable matter: What are the minimum individual capabilities necessary to achieve a collective behavior? How can existing algorithms be enhanced to capture realistic assumptions? How can digital algorithms be translated for simple, analog systems?

The world is filled with systems of entities that collaborate in motion, both natural and engineered, that are capable of sophisticated emergent behavior arising from simple interactions of their members. This PhD dissertation collects my work on the amoebot model, stateful and stochastic distributed algorithms for programmable matter, and translations to active granular matter.

We give an algorithm under the amoebot model for forming the convex hull of an object, enclosing it with the minimum number of particles. Ours is the first distributed algorithm for convex hull formation restricted to local sensing, constant-size memory, and no shared orientation or coordinates.

In this book chapter, we recap the first five years of work on the amoebot model and its variant, hybrid programmable matter. This includes distributed algorithms for shape formation and recognition, object coating, compression, shortcut bridging, separation, and some underlying primitives.