Mobility Matters
Home›Programmable matter›Self-organising particle systems›Compression›Bridging

Bridging

Particles moving between two sites must build a bridge across a gap that balances path length against bridge cost.

Problem statement and measurescollapse
Start: particles follow the landParticles shift towards a shortcutFinal: a shortcut bridge over the gap
Shortcut bridging by the Markov chain of Arroyo et al. 2018: particles join two fixed sites (black squares) along the land (shaded); the nodes under the land are over the gap (red outline). One particle at a time (outlined) expands into a free neighbouring node and contracts forward with a probability that rewards a short perimeter (\(\lambda\)) and penalises perimeter over the gap (\(\gamma\)), otherwise it contracts back; moves that would disconnect the particles from the sites, or create a hole, are refused. Shown is a run of accepted moves: the bridge shortcuts the corner but keeps few particles over the gap.

Particles occupy a path between two fixed sites across a gap in the terrain. They run a local Markov chain that rewards neighbours and penalises particles over the gap. The system should form a shortcut bridge whose length and cost are balanced, with high probability in the stationary distribution.

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

Army ants build living bridges out of their own bodies to cut a corner across a gap: a longer bridge saves walking but takes more ants out of work. 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 particles form a connected system joining two fixed sites (fixed locations at the two ends of the path); some nodes are marked as gap (over empty space) and the others as land, and a particle can tell which kind of node it is on. One randomly chosen particle acts at a time, with constant memory and no compass. The system should settle into a bridge that balances a short path between the two sites against few particles hanging over the gap, measured by a weighted perimeter: the length of the walk around the outside of the system, in which each edge of the walk over the gap costs more than one over land.

1AlgorithmThe compression rule, with the gap made expensive Markov chain, sequential → Arroyo et al. 2018

There are two biases: \(\lambda > 1\) rewards a short perimeter (many neighbours), and a second bias, written \(\gamma\) in Arroyo et al. 2018, rewards a short perimeter over the gap.

  1. A randomly chosen particle picks a random empty neighbouring node.
  2. It checks locally that the move neither splits the system nor encloses a hole (a region of empty nodes surrounded by particles).
  3. It works out, from its neighbourhood, how the move changes the perimeter and the part of the perimeter that lies over the gap.
  4. It moves with a probability that is larger when both get shorter (certainly, when the move improves both).
Why it works and what it costs. For \(\lambda > 2+\sqrt2 \approx 3.41\) and \(\gamma > 1\), the weighted perimeter is within a constant factor of its minimum with all but exponentially small probability Arroyo et al. 2018. For a V-shaped gap the bridge settles at a position that depends on the angle of the V, as observed in real ant bridges. The threshold \(2+\sqrt2\) is the same as for compression, and for the same counting reason; for small biases the paper gives no guarantee.

Why it matters. It showed that the compression rule is a flexible tool: changing the weights of the edges of the perimeter changes the shape the system settles into.

2AlgorithmWhy only one bridge forms Markov chain, sequential → Oh et al. 2024

Fire ants searching for food across water start several bridges but end with only one. Oh et al. 2024 model this with particles that prefer to move in one direction (towards the food) and prefer having neighbours, with one bias for each preference.

  1. Particles move at random, but a step towards the food is more likely than a step away.
  2. A step that gains neighbours is more likely than one that loses them.
  3. Nothing else: no particle knows how many bridges exist.
Why it works and what it costs. When both biases are large, a single bridge forms almost certainly Oh et al. 2024. Intuitively, two bridges have a longer perimeter than one bridge made of the same particles, and the neighbour bias makes long perimeters unlikely. The proof follows which nodes are occupied rather than which particle is where, which simplifies the analysis.

Why it matters. It shows that a striking collective decision, choosing one bridge, can arise from two simple preferences without coordination.

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
A local stochastic rule builds near-optimal shortcut bridges; for large biases a single bridge forms.
unknown \(\text{eventually}\) vs —
unknown — vs —

What the community started looking at

Bridging was inspired by army ants, whose bridges depend on the gap angle Arroyo et al. 2018; the later question was whether a single bridge forms Oh et al. 2024.

Generalisation of Compression

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.

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

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