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.

Progress map

tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Moves

Time

Rotation only

1 open · 1 results

unknown \(\text{decidable in P}\) vs —

unknown — vs —

Rotation and sliding + rotation + sliding

2 open · 2 results

tight \(O(n^2)\) vs \(\Omega(n^2)\) distance

tight \(O(n)\) vs \(\Omega(n)\) distance

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