A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems

Abstract

We consider programmable matter as a collection of simple computational elements (or particles) with limited (constant-size) memory that self-organize to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, in which the particle system gathers as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. More specifically, we seek fully distributed, local, and asynchronous algorithms that lead the system to converge to a configuration with small perimeter. We present a Markov chain based algorithm that solves the compression problem under the geometric amoebot model, for particle systems that begin in a connected configuration with no holes. The algorithm takes as input a bias parameter $\lambda$, where $\lambda > 1$ corresponds to particles favoring inducing more lattice triangles within the particle system. We show that for all $\lambda > 5$, there is a constant $\alpha > 1$ such that at stationarity with all but exponentially small probability the particles are $\alpha$-compressed, meaning the perimeter of the system configuration is at most $\alpha \cdot p_{min}$, where $p_{min}$ is the minimum possible perimeter of the particle system. We additionally prove that the same algorithm can be used for expansion for small values of $\lambda$. In particular, for all $0 < \lambda < \sqrt{2}$, there is a constant $\beta < 1$ such that at stationarity, with all but an exponentially small probability, the perimeter will be at least $\beta \cdot p_{max}$, where $p_{max}$ is the maximum possible perimeter.