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 + sliding

Rotation and sliding

verified
Moves: tightTime: tight

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

Assumed (added on the last edge are outlined)

+Mechanismrotation and sliding

Not assumed

Formal definitions of this setting
Mechanism: rotation + sliding
In addition, a module may slide one cell along a line of modules.

What is known

Moves · sequential moves
tight
\(\Theta(n^2)\) moves.
lower bound
\(\Omega(n^2)\) Michail et al. 2019
bottleneckdistance
holds when
  • Theorem 18: transforming a ladder into a line
  • holds even without preserving connectivity
introductory—
current best
\(O(n^2)\)
Time · parallel time
tight
\(\Theta(n)\) parallel time.
lower bound
\(\Omega(n)\) Michail et al. 2019
bottleneckdistance
holds when
  • Proposition 15 (arXiv version)
  • connectivity is preserved
introductory—
current best
\(O(n)\)

Results, in order of publication

Michail et al. 2019 current best
Moves \(O(n^2)\)Time \(O(n)\)

Introductory and current best; connectivity preserved.

Almethen et al. 2020 also
Moves \(O(n\log n)\)
line-pushing mechanism: one move shifts a whole line of modulesthe shape may disconnect

A stronger mechanism; a suspected \(\Omega(n\log n)\) lower bound is left open.

Open questions

  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.

Notes

With pivoting square modules (facet-connected), universal reconfiguration between any two configurations needs only five extra helper modules and \(O(n^2)\) pivot moves, worst-case optimal Akitaya et al. 2021. Checked against the full texts.

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

Rotation only
Moves \(\text{decidable in P}\)

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.