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 measuresexpand

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

no assumptions

Rotation only

standard settingverified
Moves: unknownTime: unknown

With rotations alone, deciding whether one shape can be transformed into another is in P; with connectivity preserved it is in PSPACE.

Assumed (added on the last edge are outlined)

nothing

Not assumed

Mechanismrotation only
Formal definitions of this setting
Mechanism: rotation
A module may rotate \(90°\) around an adjacent module, if the cells it sweeps are empty.

What is known

Moves · sequential moves
unknown
—
lower boundnone known
introductory—
current best
\(\text{decidable in P}\)
Time · parallel time
unknown
—
lower boundnone known
introductory—
current best—

Results, in order of publication

Michail et al. 2019 current best
Moves \(\text{decidable in P}\)

Introductory and current best: transformability with rotations, allowing disconnection, is decidable in polynomial time (Theorem 9); preserving connectivity it is in PSPACE (Theorem 10).

Open questions

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

Notes

Checked against the full text.

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

No catalogued weaker setting.

Lower bounds from stronger settings hold here

Rotation and sliding
Moves \(\Omega(n^2)\)Time \(\Omega(n)\)

Branches from here

Rotation and sliding

+rotation + sliding
Rotation and sliding are universal for connected shapes: \(\Theta(n^2)\) moves sequentially and \(O(n)\) parallel time, both optimal.

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