Name
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 λ, where λ > 1 corresponds to particles favoring inducing more lattice triangles within the particle system. We show that for all λ > 5, there is a constant α > 1 such that at stationarity with all but exponentially small probability the particles are α-compressed, meaning the perimeter of the system configuration is at most α ⋅ pmin, where pmin 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 λ in particular, for all 0 pmax, where pmax is the maximum possible perimeter. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2933057.2933107 | PODC |
Keywords | DocType | Volume |
Self-organizing Particles, Compression, Markov Chains | Conference | abs/1603.07991 |
Citations | PageRank | References |
6 | 0.50 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sarah Cannon | 1 | 29 | 6.36 |
| Joshua J. Daymude | 2 | 21 | 4.52 |
| Dana Randall | 3 | 29 | 8.15 |
| Andréa W. Richa | 4 | 968 | 164.82 |