Compression in Self-Organizing Particle Systems


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.

April 6, 2016 11:00 AM
Barrett, the Honors College Undergraduate Honors Thesis Defense
Arizona State University
Tempe, AZ, USA
Joshua J. Daymude
Joshua J. Daymude
Assistant Professor, Computer Science

I am a Christian and assistant professor in computer science studying collective emergent behavior and programmable matter through the lens of distributed computing, stochastic processes, and bio-inspired algorithms. I also love gaming and playing music.