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 measuresexpand

\(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.

no assumptions›+ 2D

Planar

standard settingverified
Time: tight

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.

Assumed (added on the last edge are outlined)

+Spacethe triangular lattice (planar)

Not assumed

Formal definitions of this setting
Space: 2D
Tiles occupy nodes of the triangular lattice.

What is known

Time · rounds; in each round the agent performs one Look-Compute-Move step
tight
\(\Theta(n^2)\) for the line and \(\Theta(nD)\) for the block in the worst case; the lower bounds are sketched.
lower bounds
\(\Omega(n^2)\) Gmyr et al. 2020
bottleneckone active agent
holds when
  • line formation from an initial configuration of diameter \(O(\sqrt n)\): a constant fraction of the tiles must move a distance linear in \(n\)
  • a single agent carrying one tile at a time
Stated after Theorem 3 with a one-line argument ("not hard to see"); a similar argument gives \(\Omega(nD)\) for a block.
\(\text{impossible}\) Gmyr et al. 2020
bottleneckmemory
holds when
  • the agent must stop on a safely removable tile (one whose removal keeps the structure connected) without lifting any tile
  • no pebble
  • instances: hollow hexagons and a spiral of long segments
Theorem 1: no finite automaton finds a safely removable tile in general; with one pebble it takes \(O(n^2)\) rounds (Theorem 2). This rules out the naive approach, not shape formation.
introductory—
current best
\(O(n^2)\)
no compass needed: the agent keeps its orientation relative to its initial one

Results, in order of publication

Gmyr et al. 2020 current best
Time \(O(n^2)\)
no compass needed: the agent keeps its orientation relative to its initial one

Introductory and current best: line in \(O(n^2)\) (Theorem 3), block of diameter \(O(D)\) in \(O(nD)\) (Theorem 4), tree inside the initial convex hull in \(O(n^2)\) (Theorem 5), triangle in \(O(nD)\) (Theorem 6), hence \(O(n^{3/2})\) when \(D = O(\sqrt n)\). With several agents, line formation was sped up almost linearly for a small number of agents in simulations only.

Open questions

None recorded for this variant.

Notes

\(D\) is the diameter of the initial tile set. Checked against the full text of Gmyr et al. 2020 (Natural Computing version).

What carries over from neighbouring settings

Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.

Algorithms from weaker settings work here

Three-dimensional
Time \(O(n^3)\)

Lower bounds from stronger settings hold here

No catalogued stronger setting.

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