Compression in Self-Organizing Particle Systems

Abstract

Many programmable matter systems have been proposed and realized recently, each often tailored toward a particular task or physical setting. In our work on self-organizing particle systems, we describe programmable matter as a collection of simple particles with limited computational power that each perform distributed, local, asynchronous algorithms to solve system-wide problems of movement, configuration, and coordination. In this thesis defense, I focus on the compression problem, in which the particle system gathers as tightly together as possible. I address three different notions of compression: (1) local compression, in which each individual particle utilizes local rules to create an overall convex structure containing no holes, (2) hole elimination, in which the particle system seeks to detect and eliminate any holes it contains, and (3) $\alpha$-compression, in which the particle system seeks to shrink its perimeter to be within a constant factor of the minimum possible value. Lastly, I briefly overview my contributions to the problem of leader election in which a particle system elects a single leader.