Pattern formation
Robots start at distinct points and must form a given geometric pattern, up to similarity; which patterns are formable, and from which initial configurations?
Problem statement and measuresexpand
\(n\) robots start at distinct points of the plane. Each is given the same pattern \(P\), a set (or multiset) of \(n\) points in its own local coordinate system. The robots must reach a configuration similar to \(P\) (equal up to translation, rotation, uniform scaling and, without chirality (a common clockwise direction), reflection) and stay there. The question is for which pairs (initial configuration, pattern) this is possible under the given assumptions, and at what cost in time and colours.
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).
Fat robots with lights, FSYNC, randomized, no agreement
verifiedRandomized fat robots with lights and no common orientation form any pattern in FSYNC in \(O(n)+O(\kappa\log n)\) rounds with probability at least \(1-n^{-\kappa}\), with 7 colours.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Body: fat
- Each robot is a closed disc of radius 1 (unit disc). Discs may not overlap, so robots cannot share a point and must avoid collisions; a disc hides what lies behind it from other robots. Gathering then asks for a configuration whose union of discs is connected and in which every robot sees all others Czyzowicz et al. 2009.
- Visibility: unlimited visibility
- A robot sees all robots (subject to opacity).
- Opacity: opaque
- Robots are points that obstruct sight: \(r\) sees \(s\) iff no third robot lies on the open segment \(\overline{rs}\).
- Faults: no faults
- All robots follow the algorithm forever.
- Scheduler: FSYNC
- FSYNC: every robot executes one atomic cycle in every round.
- 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: rigid
- Every Move phase ends at the computed 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: randomized
- Robots may use random bits in Compute; guarantees hold with probability 1 or in expectation, as stated per result.
- Identifiers: anonymous
- Robots are indistinguishable and run the same algorithm.
What is known
Results, in order of publication
Introductory and current best (Theorems 11, 16, 20, 21); with probability at least \(1-n^{-\kappa}\). Earlier versions used 10 and 11 colours.
Open questions
None recorded for this variant.
Notes
With \(O(1)\) words of \(O(\log n)\) bits of persistent memory instead of lights, the same bound holds (Alsaedi, Gudmundsson and van Renssen, Computational Geometry 2025). Checked against the full text of Alsaedi et al. 2025.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.