Near-gathering
Robots must get within a small distance of each other without ever colliding.
Problem statement and measuresexpand
Robots with limited visibility, each seeing only the robots within its visibility radius \(V\), start at distinct points whose visibility graph (two robots joined by an edge when they are within distance \(V\)) is connected. They must reach a configuration in which every robot sees all others, without a collision (two robots at the same point) ever happening.
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).
ASYNC, limited visibility, one common axis
standard settingverifiedRobots get close together without ever colliding, from a connected start, if they agree on one axis.
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. 2021; 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: 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.
What is known
Results, in order of publication
Introductory and current best; collision-free with termination.
Open questions
Pagli, Prencipe and Viglietta conjecture that near-gathering is impossible without agreement on one axis.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.