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. 2020e (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. 2020e

The universal algorithm of Di Luna et al. 2020e 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. 2020e

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. 2020e. 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. 2020e

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. 2020e (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. 2020e.

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 2023b?

SILBOT, full orientation

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

What the community started looking at

The first shapes were lines, triangles and hexagons, built after electing a leader Derakhshandeh et al. 2015b; 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. 2020e. Later work formed arbitrary connected shapes with a constant number of particles acting as a mobile RAM Di Luna et al. 2020d, 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 2023b. 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. 2020e.

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.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Artmann et al. 2025 On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. Shape containment, a stationary relative of shape formation: given a shape, the particles must find the largest scale \(\sigma\) (their \(k_{max}\)) at which a copy of it, in one of six rotations, fits inside the configuration, and every particle must learn whether it is a valid placement at that scale; with self-disassembly a solution yields shape formation. The particles share a compass and chirality, have constant memory, act in synchronous rounds and use reconfigurable circuits (pins of neighbouring particles linked into circuits on which a beep reaches the whole circuit in one round). Some shapes need \(\Omega(\sqrt n)\) rounds even when \(\sigma\) is known (Theorem 3.1); deterministic algorithms solve star-convex shapes in \(O(\log^2\sigma)\) rounds and the larger class of snowflake shapes in \(O(\sqrt n\log n)\) rounds (Theorem 6.2), and binary search over the scale works exactly for star-convex shapes (Theorem 5.5). Not placed: the atlas has no shape-formation setting with circuits. Read (arXiv v1).
  • Feldmann et al. 2022 Coordinating Amoebots via Reconfigurable Circuits. The paper that introduced reconfigurable circuits (its leader election is placed under leader election). With circuits, stationary particles reach consensus in \(O(1)\) rounds (Theorem 3.1), align their compasses and agree on a chirality in \(O(\log n)\) rounds with high probability (Theorem 3.4, Corollary 3.6; chirality needs two pins per bond), and recognise a shape composed of a constant number of triangles in \(O(1)\) rounds with a common chirality, \(O(\log n)\) otherwise (Theorem 3.8); parallelograms with linear or polynomial side ratio take \(\Theta(\log n)\) rounds (Appendix D). Read (arXiv v1).
  • Padalkin et al. 2024 The structural power of reconfigurable circuits in the amoebot model. Structural problems with reconfigurable circuits, for particles that share a compass and chirality: the particles on an axis through a given particle in \(O(\log n)\) rounds (Theorem 9), global maxima in \(O(\log^2 n)\) rounds (Theorem 10), a canonical skeleton and a spanning tree in \(O(\log^2 n)\) rounds (Theorems 14 and 16) and symmetry detection in \(O(\log^5 n)\) rounds (Theorem 18), all with high probability. Read (arXiv v1).
  • Padalkin & Scheideler 2026 Polylogarithmic time algorithms for shortest path forests in programmable matter. Shortest path forests with reconfigurable circuits: in a hole-free structure of stationary particles that share a compass and chirality and have a leader, a shortest path tree from one source to \(\ell\) destinations takes \(O(\log\ell)\) rounds (Theorem 39) and a forest for \(a\) sources \(O(\log n\log^2 a)\) rounds (Theorem 56), deterministically (their \(k\) is \(a\) here); Kostitsyna et al. use such trees to transform shapes. Read (arXiv v1).
  • Di Luna et al. 2018 Line Recovery by Programmable Particles. Line recovery: \(n\) particles form a line and \(f\) of them crash; the \(n - f \ge 5\) others, without chirality and under a semi-synchronous scheduler, form one line, or two lines of equal length when the configuration is symmetric (Theorem 4). Read (arXiv v1).
  • Derakhshandeh et al. 2015a An Algorithmic Framework for Shape Formation Problems in Self-Organizing Particle Systems. A framework for shape formation by particles with constant memory, applied to hexagons and triangles, asymptotically optimal in moves. Abstract read.
  • Kostitsyna et al. 2022b Fault-Tolerant Shape Formation in the Amoebot Model. Shape formation by particles whose crashes reset their memory and which detect that they crashed and recover. Abstract read.
  • Kostitsyna et al. 2022a Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter. Feather trees: shortest-path trees for amoebot structures that remain usable when several of them overlap. A brief announcement; abstract read.
  • Porter & Richa 2018 Collaborative Computation in Self-organizing Particle Systems. Computation beyond a particle's constant memory, such as counting, distributed over a particle system. Abstract read.

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 › Communication › 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.