We utilize tools from statistical physics and Markov chain analysis to investigate how macro-scale behaviors in distributed systems of programmable matter can naturally emerge from local micro-behaviors by individual computational units. When this stochastic approach is combined with the amoebot model from the SOPS project, we translate Markov chains defined at a system level into local, distributed algorithms for self-organizing particle systems that are inherently robust — tolerant of particle faults — and oblivious, using very little memory and communication when compared to the stateful SOPS algorithms.
We can then translate distributed, stochastic algorithms for desirable macroscopic behaviors such as clustering, flocking, exploration, or desegregation into the physical mechanics of simple, analog robots. Ultimately, this project will provide a better end-to-end understanding of how microscopic rules can induce macroscopic behaviors, providing a more systematic approach to building and analyzing swarm robotic systems.
