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

Shape formation by hybrid programmable matter

One finite-automaton agent rearranges passive tiles into a target shape.

Problem statement and measurescollapse
Start: connected tiles, agent on a tileWalk south while there is a tileSearch for a top-left tileLift it, move SE, walk SPlace it at the first empty nodeFinal: the tiles form a line
Shape formation by hybrid programmable matter, the line algorithm of Gmyr et al. 2020: a single agent (blue ring), a finite automaton, walks on passive hexagonal tiles and carries at most one tile (amber). It first walks south as far as there are tiles; then it repeatedly searches, walking N, NW or SW (in that order) while there is a tile there, until it stands on a top-left tile (no tile to its N, NW or SW); it lifts that tile, moves once SE, walks S to the first empty node and places the tile there. One frame per round (move, lift or place); the tiles, with the carried tile counted at the agent, stay connected. It stops when the tiles form a single north-south line.

\(n\) passive hexagonal tiles (rhombic dodecahedra in 3D) occupy nodes of a lattice and form a connected structure. A single active agent, a deterministic finite automaton, starts on a tile, must always stand on or next to a tile, sees its node and the adjacent nodes, and in each round lifts a tile, places the tile it carries, or moves to an adjacent node; it carries at most one tile, and the tiles (with the carried tile counted at the agent's node) must stay connected. It must rearrange the tiles into a target shape (a line, a triangle, or an intermediate structure such as a block or a tree). Time counts the agent's rounds.

Measures: Time, rounds; in each round the agent performs one Look-Compute-Move step.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine a single small machine on a beach of hexagonal tiles, which can pick up one tile at a time, carry it, and put it down elsewhere, and must rebuild the whole pile into a given shape. Here the machine is an agent and the beach is the triangular lattice: the infinite tiling of the plane by equilateral triangles, whose corners are its nodes. \(n\) passive hexagonal tiles sit on nodes, one tile per node; together they form a structure, which must be connected: from every tile one can reach every other tile by moving between tiles on adjacent nodes. The agent has only a fixed finite memory (it is a finite automaton) and starts on a tile. Unlike in the amoebot model, the tiles cannot expand or contract; only the agent moves. In each round it does one thing: it moves to an adjacent node, always staying on or next to a tile, or it lifts the tile under it, or it places the tile it carries. The tiles (counting the carried one) must stay connected. The goal is a target shape such as a straight line of tiles (tiles on consecutive nodes in one direction) or a triangle; time is the number of rounds, and \(D\) is the diameter of the initial structure, the largest distance between two of its tiles, counted in moves between adjacent nodes.

1AlgorithmBuild a line by moving top-left tiles down Planar → Gmyr et al. 2020

Here the line runs north-south.

  1. The agent walks south (down) as long as there is a tile below it.
  2. Search. It walks north, north-west or south-west (in that order of preference) as long as one of these has a tile. It stops on a top-left tile: a tile with no tile to its north, north-west or south-west.
  3. Move. It lifts that tile, moves once to the south-east, walks south until it reaches an empty node, and places the tile there.
  4. It repeats the search. When a search finds no tile to the east or west, the structure is a line and the agent stops.
Why it works and what it costs. The tile it moves is never needed to hold the structure together, because it is placed back where it reconnects any tiles it might have separated. Tiles only move south-east and south, and each tile is carried across at most about \(2n\) nodes, so there are \(O(n^2)\) rounds in which the agent carries a tile; a bookkeeping argument bounds the searching rounds by the same amount. Total: \(O(n^2)\) rounds Gmyr et al. 2020. The same paper builds a more compact intermediate shape (a block) in \(O(nD)\) rounds, and from it a triangle in \(O(nD)\) rounds, which is \(O(n^{3/2})\) when \(D\) is about \(\sqrt n\).

Why it matters. It shows an agent with constant memory can reshape a large structure, using simple intermediate shapes it can navigate.

2Lower boundCarrying one tile at a time is slow Planar → Gmyr et al. 2020

Start from a compact structure of \(n\) tiles, of diameter about \(\sqrt n\), and ask for a line. As in shape formation, a constant fraction of the tiles must end at distance proportional to \(n\) from where they started. The agent carries one tile at a time and moves to one adjacent node per round, so each such tile costs it about \(n\) rounds of carrying.

Why it holds. So a constant fraction of \(n\) tiles times about \(n\) rounds each gives \(\Omega(n^2)\) rounds Gmyr et al. 2020, and the line algorithm above is optimal. A similar argument gives \(\Omega(nD)\) for the block, so the block algorithm is optimal as well.

Why it matters. With a single agent, the total distance tiles must travel directly bounds the time.

3ImpossibilityAn agent with finite memory cannot find a safely removable tile Planar → Gmyr et al. 2020

The naive approach would be: find a tile whose removal keeps the structure connected (a safely removable tile), carry it to its place in the target shape, repeat. Consider a large hollow hexagon of tiles, a closed ring. An agent with \(s\) memory states walking along a long side of the ring sees the same thing in every round, so after at most \(s\) rounds it repeats its behaviour; it cannot count the length of a side. So it cannot tell this ring apart from a structure that looks the same nearby but is not closed far away, where the same tile is no longer safely removable. Gmyr et al. 2020 (Theorem 1) make this precise with hollow hexagons and spirals; the full proof is longer.

Why it holds. No finite automaton can, without lifting tiles, always stop on a safely removable tile. With a single pebble, a marker it can drop and pick up, it can find one in \(O(n^2)\) rounds Gmyr et al. 2020 (Theorem 2). This is why the algorithms above move tiles only in ways that are always locally safe.

Why it matters. It shows how far a finite memory falls short of seeing the whole picture, and why a single marker helps so much.

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
Three-dimensional
In 3D, one agent turns any connected tile structure into a low-diameter icicle in \(O(n^3)\) rounds.
unknown \(O(n^3)\) vs —
Planar standard
One agent builds a line or a tree in \(O(n^2)\) rounds and a block in \(O(nD)\) rounds, which is asymptotically optimal, and then a triangle in \(O(nD)\) rounds.
tight \(O(n^2)\) vs \(\Omega(n^2)\) one active agent

What the community started looking at

The hybrid model asked what one weak active agent can build from passive material; the first answer was that it cannot always find a tile that is safe to remove, so it builds intermediate structures by local moves instead Gmyr et al. 2020, and then whether the same holds in 3D Hinnenthal et al. 2024.

Related problems

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

All settings

The assumption tree (2 settings, 0 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); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Space.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Space

0three-dimensional lattice1the triangular lattice (planar)

The hybrid model has a few active agents with the power of finite automata and many passive tiles that the agents pick up, carry and place Hinnenthal et al. 2024. It is motivated by the observation that "while fabricating computing DNA robots remains challenging, producing simple passive tiles from folded DNA strands is efficient and scalable", and an agent can be reused after a task Hinnenthal et al. 2024. The earliest paper of the model in this atlas, by Gmyr et al. (DNA 24, 2018), works in the plane Gmyr et al. 2020. Hinnenthal, Liedtke and Scheideler moved to three dimensions, with rhombic-dodecahedral tiles on the face-centred cubic lattice. There "complexity increases significantly, with instances where any tile movement can locally disconnect the structure" Hinnenthal et al. 2024. Coating in 3D followed Kostitsyna et al. 2024.

Formal definitions
03D
Tiles occupy nodes of the face-centred cubic lattice; planar structures are a special case.
12D
Tiles occupy nodes of the triangular lattice.

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