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).
Limited visibility, one common axis, rigid, ASYNC
verifiedWith one common axis and rigid moves, asynchronous robots with limited visibility reach a horizontal segment of length 1 in time linear in the initial diameter; gathering at a point is not shown.
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: one axis
- All robots agree on the direction and orientation of one axis (e.g. North), but not necessarily on handedness: two robots may disagree on which side is East. This is how the papers use one axis agreement (e.g. robots "agree on only 'left' and 'right'" Bose et al. 2021a; robots "do not necessarily have the same handedness" Pagli et al. 2015). One axis and chirality are alternatives on this axis; together they amount to a common compass.
- 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: 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
- \(\Delta_0\) = Euclidean diameter of the initial configuration
Results, in order of publication
Introductory and current best (Theorem 1): a relaxed gathering, all robots on a horizontal segment of length 1 not fixed in advance, in \(O(\Delta_0)\) epochs; robots that occupy one point are not merged. FSYNC \(O(g)\), \(g\) the diameter (in hops) of the initial visibility graph, was known before.
Open questions
Can asynchronous robots with one common axis and limited visibility gather at a point, and in \(O(\Delta_0)\) epochs? Poudel & Sharma 2021 reach only a horizontal segment of length 1, because two robots on a horizontal line, disagreeing on east and west, may swap places forever.
Notes
Checked against the full text of Poudel & Sharma 2021 (Information 2021). The variant was previously recorded without rigid moves and as gathering at a point; the paper assumes rigid moves and proves only relaxed gathering for one common axis (Definition 3, Theorem 1). With a common compass the same algorithm gathers at a point in \(O(\Delta_0)\) epochs (Theorem 3), (setting Limited visibility with a compass, rigid, ASYNC).
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
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.