Compression
Particles following a local stochastic rule must gather into a configuration with small perimeter.
Problem statement and measurescollapse
Starting connected, the \(n\) particles perform a Markov chain (at each step one particle, chosen at random, proposes a move and accepts it with a probability that depends only on its neighbourhood) with bias \(\lambda\) towards having more neighbours. The system is \(\alpha\)-compressed if its perimeter is at most \(\alpha\) times the minimum possible.
Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).
A first look
the basic problem, a simple algorithm and why some things cannot be done, for a newcomer
Picture a crowd of penguins huddling together for warmth, each one just shuffling towards places with more neighbours. The floor is the triangular lattice: the endless graph whose nodes are the corners of a tiling of the plane by equal triangles; each node is joined by an edge to six others, its neighbours. A particle occupies one node and moves in two actions: an expansion into an empty neighbouring node, after which it occupies both, then a contraction into one of the two; so one expansion and one contraction move it by one node. The system of \(n\) particles starts connected. One particle at a time, chosen at random, is activated (an activation) and makes a random move; particles have no names, a few bits of memory, and no compass. The goal is to become compressed: the perimeter (the length of the walk around the outside of the system) should be at most \(\alpha\) times the smallest possible perimeter for \(n\) particles, for a constant \(\alpha > 1\). The question is not how fast this happens, but whether, after running long enough, the system is compressed with very high probability.
Fix a number \(\lambda > 0\), the bias. A randomly chosen particle does the following.
- Pick one of its six directions at random. If that node is empty, expand into it.
- Count \(e\), its neighbours at the old node, and \(e'\), the neighbours it would have at the new node.
- Check, by looking only at nearby nodes, that the move would neither split the system nor enclose a hole (a region of empty nodes surrounded by particles). If it would, contract back.
- Otherwise contract into the new node with probability \(\lambda^{e'-e}\) (or with certainty if this number exceeds 1); else contract back.
So moves that gain neighbours are always accepted when \(\lambda > 1\), and moves that lose neighbours are accepted only sometimes.
Why it matters. This 'local random rule with a bias' recipe became the template for separation, alignment and bridging.
Two forces compete. The bias favours each single compact configuration over each single stretched one: a configuration with perimeter \(p\) gets weight roughly \(\lambda^{-p}\). But stretched configurations are far more numerous. The number of configurations with perimeter \(p\) grows roughly like \((2+\sqrt2)^p\), because the walk around the outside never crosses itself on the honeycomb lattice (the hexagonal lattice of the triangles' centres), and such walks grow at exactly that rate. Multiply: all configurations of perimeter \(p\) together weigh about \(\left((2+\sqrt2)/\lambda\right)^p\).
Why it matters. It explains why 'prefer neighbours' is not enough on its own and how strong the preference must be.
What is known
The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.
Open questions 1
Markov chain, sequential
- Behaviour for \(2.17 \le \lambda \le 2+\sqrt2\), and bounds on the convergence time.
What the community started looking at
Compression introduced the stochastic approach to programmable matter, where the question is which bias produces which emergent behaviour Cannon et al. 2016.
Derived problems
Separation of coloured particles: Separation adds two colours to compression; the same local chain compresses and, depending on a second bias, separates or integrates the colours Cannon et al. 2019.
Alignment: Alignment adds an orientation to each particle; the same chains also give compression and expansion Kedia et al. 2022.
Bridging: Bridging adds terrain: the compression chain is biased to stay on land and to shorten a path across a gap Arroyo et al. 2018.
Perspectives
- From robots to particles Programmable matter re-asks the questions of robots in the plane on a lattice, with particles that touch, remember a little and stay connected; SILBOT takes memory and messages away again, and the stochastic approach replaces algorithms by a biased local rule.
- The most consequential open problems Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.
All settings
The assumption tree (1 settings, 1 branch points)
The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Moves); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Memory › Scheduler › Orientation › Randomness › Initial shape › Connectivity during execution.
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.