Mobility Matters
Home›Programmable matter›Self-organising particle systems›Shape formation in programmable matter

Shape formation in programmable matter

Particles must rearrange into a target shape (a line, a triangle, any shape built from triangles).

Problem statement and measurescollapse
LLLStart: a connected configurationErosion: corners drop outThree candidates remain: all three leadEach leader picks a rayStraighten: pull onto the rayFold into the triangleFinal: the target triangle is formed
Shape formation by the universal algorithm of Di Luna et al. 2020 (the problem as in Derakhshandeh et al. 2016), here on a configuration with three-fold symmetry and a triangle as target shape. Erosion (no movement) leaves three candidates, neighbours of each other (green), that cannot break the symmetry, so all three lead. Each leader picks a ray (dashed; the three rays are rotations of each other) and pulls its part into a straight segment along it; then each segment folds into its third of the triangle. A particle moves by one node with an expansion followed by a contraction.

From a connected initial configuration (the set of nodes occupied by particles) of \(n\) particles, the particles must reach a configuration forming a given target shape (at a scale depending on \(n\)). Time is in rounds; moves counts expansions and contractions.

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

Think of a pile of clay made of tiny identical machines that should mould itself into a triangle, a hexagon or a line. Each machine is a particle. It occupies one node of the triangular lattice, the infinite tiling of the plane by equilateral triangles whose corners are the nodes; particles on adjacent nodes are neighbours. There are \(n\) particles, and their nodes form a connected configuration with no holes (empty regions enclosed by particles); each particle has a few bits of memory and talks only to its neighbours. A particle moves in two steps: an expansion into an empty adjacent node, after which it briefly occupies both nodes, then a contraction into one of the two; so one expansion and one contraction move it by one node. In the standard version the particles do not agree on clockwise (they have no chirality) or on north, and an adversarial scheduler decides when each particle acts; each time a particle acts is an activation. They all know a small description of the target shape, and must end up forming it, scaled up so that it uses all \(n\) particles. We count rounds (stretches of time in which every particle is activated at least once) and moves (expansions and contractions).

1AlgorithmElect, straighten into a line, rebuild Deterministic, simply connected start, no chirality → Di Luna et al. 2020

The universal algorithm of Di Luna et al. 2020 has seven phases; in plain words:

  1. Erosion: particles on corners of the configuration drop out one by one (no movement) until 1, 2 or 3 candidates remain, each a neighbour of the others; a candidate may become a leader, a particle that directs the others.
  2. Each candidate becomes the root of a tree that spans part of the configuration (every particle remembers a parent).
  3. The particles agree on chirality, copying it from the candidates.
  4. The candidates try to break ties; if they cannot, the starting configuration was symmetric and several leaders carry on together.
  5. Each leader pulls its tree into a straight line; all lines get the same length.
  6. Walking along its line, each leader works out the scale of the target shape and tells every particle its future role.
  7. Each line, guided by its leader, folds into its share of the target shape.
Why it works and what it costs. A line is easy to control: a leader at one end can count along it and send instructions particle by particle. The whole process takes \(O(n^2)\) rounds and \(O(n^2)\) moves, and the moves are optimal by the next idea. With coin flips, chirality and one particle activated at a time, shapes made of a constant number of triangles are built in \(\Theta(\sqrt n)\) rounds from a well-prepared configuration Derakhshandeh et al. 2016.

Why it matters. Using a line as a universal halfway shape is the standard trick for shape formation, reused for tiles and modular robots too.

2Lower boundA compact configuration must travel far to become a line Deterministic, simply connected start, no chirality → Di Luna et al. 2020

Start with the \(n\) particles packed into a hexagon; it fits inside a circle of radius about \(\sqrt n\) around its centre \(c\). Ask for a straight line. A line has at most \(2r+1\) of its particles within distance \(r\) of \(c\). Take \(r = n/4\): at most about \(n/2\) particles of the final line are within distance \(n/4\) of \(c\), so at least about \(n/2\) particles end farther than \(n/4\) from \(c\). Each of them started within about \(\sqrt n\) of \(c\), so it must travel at least \(n/4 - \sqrt n\) nodes, one node per expansion and contraction.

Why it holds. Adding up gives at least about \((n/2)(n/4) = n^2/8\) expansion-and-contraction pairs, so \(\Omega(n^2)\) moves for any algorithm Di Luna et al. 2020. The algorithm above uses \(O(n^2)\) moves, so it is optimal in moves. The argument says nothing about rounds, because many particles can move in the same round.

Why it matters. The same distance-counting argument gives the quadratic lower bounds for line formation, coating and centralised transformations.

3ImpossibilitySymmetry that cannot be broken Deterministic, simply connected start, no chirality → Di Luna et al. 2020

Take three particles in a small triangle and ask them to form a straight line of three. The triangle looks the same after a turn by a third of a circle, and its centre is the middle of a triangular face, not a node. Each particle numbers the six directions around it; these local numbers are its ports. Let the scheduler always activate the three rotated copies of a particle together, and give them rotated ports. Then they see rotated copies of the same view and make rotated copies of the same move. Because the centre is not a node, two of them never try to enter the same node, so nothing breaks the tie: the configuration stays three-fold symmetric forever. A line of three is not three-fold symmetric, so it is never formed.

Why it holds. In general, a configuration that is symmetric under a turn of a half or a third of a circle around a point that is not a node can only reach configurations with the same symmetry Di Luna et al. 2020 (Theorem 1). The paper also proves the converse for hole-free configurations: every other target shape can be formed, so this is the only obstacle. With coin flips the obstacle disappears and any shape can be formed once \(n\) is large Di Luna et al. 2020.

Why it matters. It shows exactly which shapes are out of reach and why, and it explains why many algorithms elect up to three leaders instead of one.

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
Deterministic, simply connected start, no chirality standard
Which shapes are deterministically formable from a simply connected start is characterised; \(O(n^2)\) rounds and moves, and the moves are optimal.
unknown \(O(n^2)\) vs —
tight \(O(n^2)\) vs \(\Omega(n^2)\) distance
Universal shapes, sequential, randomized
Any shape made of a constant number of triangles, from a well-initialised start, in \(\Theta(\sqrt n)\) rounds.
tight \(O(\sqrt n)\) vs \(\Omega(\sqrt n)\) distance
unknown — vs —
SILBOT, chirality
Silent oblivious particles cannot form a line if they share only chirality.
impossible — vs \(\text{impossible}\) symmetry breaking
impossible — vs —
SILBOT, full orientation
With a common compass, silent oblivious particles form a line with \(O(n^2)\) moves, which is optimal.
unknown — vs —
tight \(O(n^2)\) vs \(\Omega(n^2)\) distance

Open questions 3

SILBOT, chirality

  1. Is line formation solvable in SILBOT when particles share just one direction instead of the full orientation Navarra & Piselli 2023?

SILBOT, full orientation

  1. Does 1-hop visibility suffice for line formation in SILBOT Navarra & Piselli 2023?
  2. Which other shapes can SILBOT particles form Navarra & Piselli 2023?

What the community started looking at

The first shapes were lines, triangles and hexagons, built after electing a leader Derakhshandeh et al. 2015; then any shape made of triangles Derakhshandeh et al. 2016. The deterministic question, which shapes are formable from which starts, mirrors pattern formation for robots Di Luna et al. 2020. Later work formed arbitrary connected shapes with a constant number of particles acting as a mobile RAM Di Luna et al. 2020, reconfigured between arbitrary shapes in a linear number of rounds without a canonical intermediate shape Kostitsyna et al. 2023, and asked which shapes silent, oblivious particles can form, starting with the line Navarra & Piselli 2023. Most tasks have a natural \(\Omega(D)\) lower bound because particles and information move one node at a time; joint movements and reconfigurable circuits are extensions proposed to break it Padalkin et al. 2025.

Related problems

Pattern formation: "Shape formation is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter" Di Luna et al. 2020.

Shape formation by hybrid programmable matter: In the hybrid model the tiles are passive and one active agent moves them; in the amoebot model every particle is active.

Centralised transformations of modular robots: A central controller plans the moves, so the question is which mechanisms are universal and how many moves they need, not how particles coordinate.

Perspectives

  • Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
  • 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.
  • What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.

All settings

The assumption tree (4 settings, 2 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.