Self-Organizing Particle Systems: an Algorithmic Approach to Programmable Matter

Abstract

In order for programmable matter to live up to the dream of being an all-purpose “bucket of stuff” deployable for any task at any scale, we need a rich toolbox of algorithmic primitives upon which we can program more complex behaviors. Although the eventual vision is to control a whole mass of programmable matter as a single entity, our toolbox of primitives should be defined at the level of individual “atoms” of programmable matter to enable arbitrary scalability. Thus, we must take a distributed computing approach to defining micro-scale behaviors that collectively induce macro-scale phenomena. Towards this goal, self-organizing particle systems abstractly envision programmable matter as an ensemble of tiny computational units called particles. These particles are assumed to be very simple: they have very limited memory, no sense of orientation or direction, and only local movement and communication capabilities. Our formal model for these particle systems is the amoebot model. In this talk, I will review the amoebot model before describing the behaviors and primitives developed so far including leader election, shape formation, object coating/enclosure, compression, and separation. Time permitting, I will conclude with a preview of current work-in-progress and open problems.