Universal pattern formation
Robots must be able to form any pattern from any initial configuration, not only the ones symmetry allows.
Problem statement and measuresexpand
From every initial configuration of \(n\) robots (several robots may start on the same point, forming a multiplicity Flocchini et al. 2026), the robots must form every given pattern of \(n\) points (a multiset of points given to every robot; multiplicities allowed). With lights, universal dancing asks for any sequence of patterns.
Measures: Time, rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known; Colours, colours of the light per robot (0 for oblivious robots).
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
Time
Colours
Sequential schedulers + point, + unlimited visibility, + transparent, + no faults, + sequential
0 open · 1 results
unknown
\(\text{finite}\) vs \(\text{impossible}\)
symmetry
tight
\(0\) vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.