Mobility Matters
Home›Programmable matter›Self-organising particle systems›Centralised transformations of modular robots

Centralised transformations of modular robots

A centralised algorithm must transform one connected shape of \(n\) modules on the square grid into another using local moves.

Problem statement and measurescollapse
Start: a connected shape of 5 modulesRotation: a quarter turn around a neighbourSliding: one cell along two neighboursFinal: the modules form a line
Centralised transformation with rotations and slidings, the universal strategy of Michail et al. 2019: repeatedly pick a module on the outside whose removal keeps the rest connected and walk it around the outside, rotating at corners (a quarter turn around a neighbour, the swept cells being empty) and sliding along straight stretches (one cell along two neighbours), to the end of a line growing to the right along the bottom row (dashed); a target shape is reached by also playing its own plan to the line backwards (not shown). One frame per move; a rotation is drawn along its arc.

\(n\) modules (unit squares, the particles of this model) occupy cells of the square grid and form a connected shape; modules in cells that share a side are neighbours, and the shape is connected when every module can be reached from every other through neighbours. A centralised algorithm must transform it into a given target shape with the same number of modules, using only the allowed local moves, keeping the shape connected where required. Moves counts sequential moves; time is parallel time when several moves may happen at once.

Measures: Moves, sequential moves; Time, parallel time.

A first look

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

Picture a set of square magnets on a chessboard, all touching one another, that you are allowed to rearrange only by small local moves, and ask: can one arrangement be turned into another, and how many moves does it take? Here the magnets are \(n\) square modules and the squares of the board are cells of the infinite square grid. Modules in cells that share a side are neighbours, and the modules form a connected shape: every module can be reached from every other through neighbours. A centralised algorithm sees everything and decides the moves. Unlike amoebot particles, which move by expanding and contracting, a module moves by rotation (turning a quarter circle around a neighbour, ending on a diagonal cell) or by sliding (moving one cell along two neighbouring modules); a move is allowed only if the cells it sweeps through are empty. The goal: transform the shape into a given target shape with the same number of modules, and count moves (one at a time) or parallel time (the number of steps when several moves may happen at once).

1AlgorithmEverything turns into a line, and moves can be undone Rotation and sliding → Michail et al. 2019

With rotations and slidings both allowed:

  1. Find a module on the outside of the shape whose removal keeps the rest connected; every connected shape with at least two modules has at least two.
  2. That module can walk around the outside of the rest, rotating at corners and sliding along straight stretches, always staying a neighbour of some module.
  3. Walk it to the end of a horizontal line (modules in consecutive cells of one row) growing from the shape's lowest right-most module; repeat until all \(n\) modules form the line.
  4. To reach a target shape \(B\), also plan \(B \to\) line, then play that plan backwards: every rotation and sliding can be undone by the opposite move.
Why it works and what it costs. So any two connected shapes with the same number of modules can be transformed into each other without ever disconnecting Michail et al. 2019. Each module walks at most about the perimeter of the shape, so the plan uses \(O(n^2)\) moves, and that is the best possible in the worst case (the third idea). Allowing many moves at once, the same paper reaches \(O(n)\) parallel time, also best possible.

Why it matters. Going through a canonical shape and using reversibility is the standard way to prove that a set of moves is universal.

2ImpossibilityRotations never change a module's chessboard colour Rotation only → Michail et al. 2019

Colour the grid like a chessboard. A rotation moves a module to a cell diagonal to its old one, which has the same colour. So with rotations alone, the number of modules on black cells never changes, and neither does the number on white cells. Example: a horizontal line of 3 modules on black, white, black cells has two on black; a shape of 3 modules with two on white cells can never be reached from it.

Why it holds. Two shapes with different colour counts can never be transformed into each other by rotations Michail et al. 2019. Equal colour counts are not enough either: some shapes have no rotation available at all and are stuck. If disconnecting is allowed, the paper shows that deciding whether a transformation exists takes polynomial time; if connectivity must be kept, the decision is in PSPACE.

Why it matters. An invariant, a quantity that no move changes, is the simplest tool for proving that a transformation is impossible.

3Lower boundA staircase is far from a line Rotation and sliding → Michail et al. 2019

Take a ladder: a diagonal staircase two modules wide, climbing one row every two modules. Ask for a horizontal line. Wherever the line is placed, at least half of the ladder's modules lie on one side of it, at heights \(1, 1, 2, 2, \dots\) up to about \(n/4\) from it. Each must cover at least that height, so the total distance is at least \(2(1+2+\dots+n/4)\), which is about \(n^2/16\).

Why it holds. One rotation or sliding moves one module by a constant distance, so it reduces this total by at most a constant. Hence \(\Omega(n^2)\) moves are needed, even if the shape may disconnect Michail et al. 2019 (Theorem 18), and the line-based plan is optimal. The same measure, total distance under the best matching of modules to target cells, can be computed in polynomial time, so such lower bounds are easy to evaluate.

Why it matters. The total-distance argument gives quadratic lower bounds for every model where one entity moves one step at a time.

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
Moves
Time
Rotation only standard
With rotations alone, deciding whether one shape can be transformed into another is in P; with connectivity preserved it is in PSPACE.
unknown \(\text{decidable in P}\) vs —
unknown — vs —
Rotation and sliding
Rotation and sliding are universal for connected shapes: \(\Theta(n^2)\) moves sequentially and \(O(n)\) parallel time, both optimal.
tight \(O(n^2)\) vs \(\Omega(n^2)\) distance
tight \(O(n)\) vs \(\Omega(n)\) distance

Open questions 3

Rotation only

  1. What is the complexity of connectivity-preserving transformability with rotations alone? The paper leaves it open (Section 7) Michail et al. 2019.

Rotation and sliding

  1. Prove the suspected \(\Omega(n\log n)\) lower bound for universal transformations with line pushing Almethen et al. 2020.
  2. Distributed universal transformations with line pushing Almethen et al. 2020.

What the community started looking at

The first question was which mechanisms are universal and how hard it is to decide transformability Michail et al. 2019; then how far stronger mechanisms reduce the number of moves Almethen et al. 2020 Akitaya et al. 2021.

Related problems

Shape formation in programmable matter: A central controller plans the moves, so the question is which mechanisms are universal and how many moves they need, not how particles coordinate.

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 (Moves, Time); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Mechanism.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Mechanism

0rotation only1rotation and sliding

Michail, Skretas and Spirakis chose two movements that are "easily implementable by existing technology": a module may rotate \(90°\) around a neighbour, or slide one cell over two neighbours Michail et al. 2019. Rotation and sliding together had been studied before for metamorphic robotic systems Dumitrescu et al. 2004 (as cited by Michail et al. 2019). Rotation alone is the weaker mechanism. Michail et al. showed that deciding transformability with rotations alone is in P, and in PSPACE when connectivity must be kept; adding sliding makes any two connected shapes of the same size transformable into each other with \(\Theta(n^2)\) moves Michail et al. 2019. Almethen, Michail and Potapov later added a line-pushing mechanism that contains both as special cases and is faster Almethen et al. 2020.

Formal definitions
0rotation
A module may rotate \(90°\) around an adjacent module, if the cells it sweeps are empty.
1rotation + sliding
In addition, a module may slide one cell along a line of modules.

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