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).
Sequential schedulers
standard settingverifiedUnder any sequential scheduler, oblivious robots can form every pattern from every starting configuration, except a single point, which needs weak multiplicity detection.
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): oblivious
- OBLOT: a robot's computation depends only on the current snapshot; nothing persists across cycles.
- 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: no multiplicity detection
- A snapshot is a set of points: a point occupied by several robots looks like a single robot.
- 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
- under FSYNC, even with strong extra capabilities
Results, in order of publication
Introductory and current best; no additional assumptions except for point formation.
Open questions
None recorded for this variant.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.