Gathering
Robots must meet at a single point that is not fixed in advance, and stay there.
Problem statement and measuresexpand
\(n\) robots start at distinct points and must all reach the same point in finite time and remain there. For \(n = 2\) the problem is called rendezvous. Time is counted in rounds (FSYNC, SSYNC) or in epochs (ASYNC: intervals in which every robot completes at least one full Look–Compute–Move cycle); colours count light 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).
FSYNC, no multiplicity detection
verifiedUnder FSYNC, oblivious disoriented robots gather from any start of distinct points without detecting multiplicities, even with non-rigid moves.
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: FSYNC
- FSYNC: every robot executes one atomic cycle in every round.
- 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: 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.
- Number of robots: any \(n\)
- Any number \(n\ge 2\) of robots.
- Initial configurations: any start
- The algorithm must gather from every initial configuration from which gathering is possible at all in the setting; configurations proved unsolvable there (for example bivalent ones, or several multiplicities with weak detection and crashes) are excluded by the problem, not by the algorithm.
What is known
Results, in order of publication
Introductory and current best: a variant of the centre-of-gravity algorithm of Cohen and Peleg, which needed multiplicity detection because non-rigid moves can make robots meet early; the proof follows theirs and is certified in the Coq proof assistant (Pactole library). The question was open before.
Open questions
None recorded for this variant.
Notes
Without multiplicity detection gathering is impossible under SSYNC and ASYNC (setting no-multiplicity), so FSYNC is the only scheduler of the model in which it is solvable without extra assumptions Balabonski et al. 2018b. Flocchini et al. 2026 also state that under FSYNC no multiplicity detection is needed. Checked against the HAL version of Balabonski et al. 2018b.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.