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).
Luminous robots, sequential scheduler (universal dancing)
verifiedUnder a sequential scheduler, disoriented luminous robots form every sequence of patterns up to a length fixed by the number of colours.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Body: point
- Each robot is a point of the plane: several robots may share a point (multiplicity), and a robot hides only what lies exactly behind it on a line of sight.
- Visibility: unlimited visibility
- A robot sees all robots (subject to opacity).
- Opacity: transparent
- Robots do not obstruct each other's view.
- Faults: no faults
- All robots follow the algorithm forever.
- Scheduler: sequential
- Sequential: an SSYNC scheduler that activates exactly one robot per round (fairly). Also called a centralized scheduler Terai et al. 2023; a round-robin scheduler is a fair special case.
- Lights (persistent memory): lights (LUMI)
- LUMI: each robot has a light with \(c\) colours, set at the end of Compute, visible to all robots including itself; it is both memory and communication. Also called luminous robots, or a full light.
- Agreement on coordinates: disoriented
- Each robot \(r\) observes in its own coordinate system, obtained from the global one by an unknown similarity (translation, rotation, uniform scaling, and possibly reflection); systems may differ between robots and, in some models, between cycles. Papers that call robots disoriented do not always mean this: Défago and Souissi use the word while assuming chirality Défago & Souissi 2008. Some papers also let the adversary change a robot's rotation, reflection and unit at every Look (variable disorientation) Flocchini et al. 2023 Masuzawa et al. 2026.
- Movement: non-rigid
- In a Move phase the adversary may stop a robot before its destination, but only after it has travelled at least \(\delta>0\) (a constant unknown to the robots) or reached the destination.
- Multiplicity detection: strong multiplicity
- A snapshot is a multiset: each occupied point comes with the exact number of robots on it.
- Randomness: deterministic
- The destination computed in a cycle is a function of the snapshot (and the light, if any).
- Identifiers: anonymous
- Robots are indistinguishable and run the same algorithm.
What is known
- longer sequences cannot be formed with \(c\) colours
Results, in order of publication
Introductory and current best: with \(c \ge 4\) colours every sequence of length up to \(\tbinom{n+c-7}{c-4}\) is formed; non-rigid moves, disoriented robots.
Open questions
None recorded for this variant.
Notes
Checked against the full text.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.