Pattern sequences
Robots must form a given sequence of patterns, one after the other, forever.
Problem statement and measuresexpand
Robots are given a sequence of patterns \(P_1, P_2, \dots, P_m\) (sets of points in the plane) and must form them in order, repeatedly, with all robots taking part in each.
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
unknown
\(\text{finite}\) vs —
tight
\(0\) vs —
unknown
\(\text{finite}\) vs \(\text{impossible}\)
symmetry breaking
polynomial gap
\(\alpha(S)+\mu(S)+O(1)\) vs \(\max\{\alpha(S)/\min_i\alpha(S_i),\ \mu(S)^{1/\alpha(S)}\}\)
memory
Luminous robots, sequential scheduler (universal dancing) + sequential, + lights (LUMI), + strong multiplicity
0 open · 1 results
unknown
\(\text{finite}\) vs —
near-optimal
\(c \ge 4\) vs \(\text{with } c \text{ colours, length} \le \tbinom{n+c-1}{c-1}\)
memory
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.