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).
Gathering, external light (FCOM), SSYNC, rigid
verifiedWith external lights, \(n \ge 3\) robots gather in rigid SSYNC with 3 colours, which is optimal; 2 suffice if a robot sees who shares its point.
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: SSYNC
- SSYNC: time is divided into rounds; in each round a non-empty subset of robots, chosen by a fair adversary, executes one atomic Look–Compute–Move cycle. Called Atom by Prencipe Prencipe 2007.
- Lights (persistent memory): external light (FCOM)
- FCOM: each robot has a light with \(c\) colours that only the others can see (constant communication, no persistent memory of its own). Also called an external light.
- Agreement on coordinates: chirality
- All local coordinate systems have the same handedness (clockwise orientation): no reflection. Also called handedness. Prencipe uses chirality for agreement on North and East, i.e. a compass Prencipe 2007.
- 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: 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: \(n \ge 3\)
- \(n\ge 3\) robots.
What is known
- Theorem 2(1)
- without seeing the robots at its own point
Results, in order of publication
Introductory and current best (Theorem 6). With local awareness 2 colours suffice (Theorem 7), and local awareness cannot be dropped (Theorem 2(2) of Otaka et al. 2026).
Open questions
Gathering with external lights in ASYNC Otaka et al. 2026.
Notes
Checked against the full texts.
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.