Local Stochastic Algorithms for Compression and Shortcut Bridging in Programmable Matter

Abstract

Many programmable matter systems have been developed, including modular and swarm robotics, synthetic biology, DNA tiling, and smart materials, with each tailored toward a specific task or physical setting. In our work on self-organizing particle systems, we abstract away specific settings and instead describe programmable matter as a collection of simple computational elements (particles) with limited memory that each execute fully distributed, local, asynchronous algorithms to solve system-wide problems such as movement, configuration, and coordination. Recent work taking a stochastic approach has yielded surprisingly fruitful results, producing local algorithms that are robust, nearly-oblivious, and truly decentralized. For the compression problem, in which a particle system is tasked with gathering as tightly as possible, we gave a Markov chain based solution that minimizes the overall perimeter of the system via individual particles making decisions based only on information about their local neighborhoods. Variants of this algorithm produced a variety of other useful behaviors, including expansion over as wide an area as possible, coating an arbitrarily shaped surface, and spanning fixed sites. Subsequently we presenting a distributed stochastic algorithm for particle systems forming shortcut bridges, a behavior also observed in army ants, where balancing between two competing global objectives is observed. For all of these problems, tools from Markov chain analysis and distributed algorithms allow us to relate local and globally optimal behavior.