Scattering
Robots that may start at shared points must move to pairwise distinct points.
Problem statement and measuresexpand
\(n\) robots start at points of the plane, several possibly at the same point (a multiplicity). They must reach a configuration in which all positions are distinct, and stay there.
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).
Randomized, ASYNC, rigid, weak multiplicity detection, no vision needed
verifiedWith rigid moves, robots that see nothing but whether their own point is shared scatter in ASYNC in expected \(O(2^{2n^2})\) rounds.
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: limited visibility
- A robot sees exactly the robots within Euclidean distance \(V\) of its position, for a fixed radius \(V>0\).
- Opacity: transparent
- Robots do not obstruct each other's view.
- Faults: no faults
- All robots follow the algorithm forever.
- Scheduler: ASYNC
- ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may look while others move, and compute on an outdated snapshot. Time is counted in epochs: an epoch is an interval of time in which every robot completes at least one full Look–Compute–Move cycle; it need not be the shortest such interval. The execution is divided into consecutive epochs, and a bound of \(X\) epochs holds for every such division. In FSYNC and SSYNC time is counted in rounds. Called Corda by Prencipe Prencipe 2007. Intermediate variants restrict interleavings: LC-atomic (no Look by another robot between a robot's Look and its Compute), Move-atomic (no Look during another robot's Move) and CM-atomic Flocchini et al. 2023.
- 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 Wada et al. 2026.
- Movement: rigid
- Every Move phase ends at the computed destination.
- Multiplicity detection: weak multiplicity
- A snapshot marks each occupied point as holding one robot or more than one.
- 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 (Algorithm 1, Theorems 2 and 5): a robot that shares its point moves to the \(i\)-th point of a fixed sequence on a circle, with probability \(2^{-i}\); the bound is on the expected number of rounds. Since the robots ignore the others, the algorithm works under any visibility.
Open questions
Is there a polynomial bound on the expected time of blind rigid ASYNC scattering in the plane?
Notes
On the line, blind robots cannot scatter even with rigid moves and weak multiplicity detection (Theorem 8 of Léchine & Tixeuil 2019). Checked against the full text of Léchine & Tixeuil 2019 (arXiv v1, a preprint).
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.