Home›Programmable matter›Self-organising particle systems›Compression›Alignment

Alignment

Oriented particles, following a local stochastic rule, must align their orientations.

Problem statement and measurescollapse

Alignment by the Markov chain of Kedia et al. 2022, connected setting: each particle carries one of \(q\) orientations (here \(q = 3\), shown as three colours). One particle at a time (outlined) either steps, expanding into a free neighbouring node and contracting forward with a probability that grows with its gain in neighbours (\(\lambda\)) and in agreeing neighbours (\(\gamma\)), or turns to a new orientation, accepted with a probability that grows with its gain in agreeing neighbours; moves that would disconnect the system or create a hole are refused. Shown is a run in which every proposed move is accepted. For large biases most particles end up sharing one orientation, with high probability; for small biases they do not.

Each particle carries one of \(q \ge 2\) orientations, a spin state, not a sense of direction. Particles run a local Markov chain; the system should be aligned (most particles share an orientation) or not, depending on the bias, with high probability in the stationary distribution, both when connectivity is kept and when particles may disconnect.

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 school of fish or a flock of birds in which every animal turns to face the same way as its 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, and each particle carries an orientation, one of \(q \ge 2\) values drawn as an arrow; the orientation is just a state, not a compass, and a particle can only compare its orientation with its neighbours' orientations. One randomly chosen particle acts at a time; it either steps (moves to a neighbouring node) or turns (changes its orientation). The system should become aligned (one orientation is held by most particles) or stay non-aligned (all orientations about equally common), depending on a bias; this is studied both when the system must stay connected and when it may fall apart.

1AlgorithmStep or turn, with a bias towards agreeing neighbours Markov chain, sequential → Kedia et al. 2022

In the connected setting there are two biases: \(\lambda\) rewards having neighbours, as in compression, and a second bias, written \(\gamma\) in Kedia et al. 2022, rewards agreeing neighbours (neighbours with the same orientation). A randomly chosen particle does one of two things, with equal chance.

Step. Pick a random empty neighbouring node; check locally that the system stays connected without holes (regions of empty nodes surrounded by particles); move with a probability that grows with the gain in neighbours and in agreeing neighbours.
Turn. Pick a new orientation; accept it with a probability that grows with the gain in agreeing neighbours (certainly, if it gains).

Why it works and what it costs. With both biases large (for instance \(\gamma > 29.3(q-1)\) and \(\lambda\gamma\) large enough), the system is compressed (its perimeter, the length of the walk around its outside, is at most a constant times the minimum) with high probability, and under further conditions on \(\gamma\) one orientation dominates Kedia et al. 2022. With \(\lambda\) large but \(\gamma\) small, the system is compressed but its orientations stay evenly split among the \(q\) values; with \(\lambda\) small, the system stays stretched out. Compactness matters: a long thin bottleneck lets two regions with different orientations coexist cheaply, so alignment is proved only for well compressed systems.

Why it matters. It brings the Potts and clock models of magnetism into programmable matter, with particles that move as well as turn.

2AlgorithmWhen particles may drift apart: one knob Markov chain, sequential → Kedia et al. 2022

If the system is allowed to disconnect, the connectivity check is dropped: a particle may step to any empty neighbouring node. A single bias then rewards, at the same time, having neighbours and having agreeing neighbours.

Pick step or turn with equal chance.
Step: move to a random empty neighbouring node, accepted with a probability that grows with the gain in (agreeing) neighbours.
Turn: as before.

Why it works and what it costs. When the single bias is large, the particles gather into compact clusters (sets of particles connected through neighbours) and align; when it is small, they disperse and the orientations stay balanced Kedia et al. 2022. The proof is harder than in the connected case because a spread-out system can contain many small clusters scattered over the lattice.

Why it matters. It shows that the stochastic approach does not need the connectivity rule, which is costly to check and not always realistic.

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.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Moves

Markov chain, sequential standard

For every \(q \ge 2\), alignment and non-alignment are both achieved by the bias.

unknown \(\text{eventually}\) vs —

unknown — vs —

What the community started looking at

Alignment brought Potts and clock models from statistical physics to programmable matter Kedia et al. 2022.

Generalisation of Compression

Alignment adds an orientation to each particle; the same chains also give compression and expansion Kedia et al. 2022.

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.

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.

tight near-optimal polynomial gap unknown impossible no variant

No assumptions · 1 branches by memory Nothing is assumed on any axis.
- +constant memory+sequential+randomized
  Markov chain, sequential standard setting For every \(q \ge 2\), alignment and non-alignment are both achieved by the bias.

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.