Mobility Matters
Home›Mobile robots in the plane›Formation problems›Pattern formation›k-grouping›Gathering

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).

no assumptions›+ point›+ unlimited visibility›+ transparent›+ crash faults›ASYNC, + weak multiplicity, + \(n \ge 3\), + restricted start

Crash faults, ASYNC, restricted start

verified
Time: unknownColours: tight

In ASYNC with instantaneous computation, up to \(\lfloor n/2\rfloor - 2\) crashes are tolerated for \(n \ge 7\), from initial configurations that exclude some symmetric families.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Visibilityunlimited+Opacitytransparent: every robot sees every robot within range+Faultsup to \(f\) robots may crash+Multiplicity detectionweak: a robot sees whether a point holds more than one robot+Number of robots\(n \ge 3\)+Initial configurationsa restricted family of initial configurations

Not assumed

Schedulerasynchronous (ASYNC)Lights (persistent memory)oblivious, no light (OBLOT)Agreement on coordinatesno agreement on local coordinate systemsMovementnon-rigid: the adversary may stop a move after some minimum distance \(\delta\)RandomnessdeterministicIdentifiersanonymous: all robots are identical
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: crash faults
Up to \(f\) robots stop forever at adversarial times and remain visible at their last position.
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: 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: weak multiplicity
A snapshot marks each occupied point as holding one robot or more than one.
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.
Initial configurations: restricted start
The algorithm gathers only from a stated family of initial configurations that leaves out some solvable ones, typically symmetric configurations; the family is named on each result.

What is known

Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known
unknown
Time not analysed.
lower boundnone known
introductory—
current best
\(\text{finite}\)
ASYNC with instantaneous computation (Look and Compute happen at one instant)\(f \le \lfloor n/2\rfloor - 2\) crashes and \(n \ge 7\)initial configurations with at most one multiplicity, excluding the symmetric families \(C(0)\), \(C(1/k)\), \(C(1/2)\) and \(C(1/2+1/k)\) of the paper (Table 1)
Colours · colours of the light per robot (0 for oblivious robots)
tight
No colours.
lower boundnone known
introductory—
current best
\(0\)
ASYNC with instantaneous computation (Look and Compute happen at one instant)\(f \le \lfloor n/2\rfloor - 2\) crashes and \(n \ge 7\)initial configurations with at most one multiplicity, excluding the symmetric families \(C(0)\), \(C(1/k)\), \(C(1/2)\) and \(C(1/2+1/k)\) of the paper (Table 1)

Results, in order of publication

Pattanayak et al. 2019b current best
Time \(\text{finite}\)Colours \(0\)
ASYNC with instantaneous computation (Look and Compute happen at one instant)\(f \le \lfloor n/2\rfloor - 2\) crashes and \(n \ge 7\)initial configurations with at most one multiplicity, excluding the symmetric families \(C(0)\), \(C(1/k)\), \(C(1/2)\) and \(C(1/2+1/k)\) of the paper (Table 1)

Introductory and current best (Theorem 3), without agreement on coordinates. Cicerone, Di Stefano and Navarra state that the discussion after this theorem does not consider configurations with more than one axis of symmetry, and that it lets configurations with a robot at the centre of the smallest enclosing circle elect a leader only when \(n\) is even Cicerone et al. 2021a (arXiv version).

Open questions

  1. Gather despite crashes in ASYNC from every solvable initial configuration, symmetric ones included, with weak multiplicity detection.

Notes

Checked against the full text of Pattanayak et al. 2019b (Problem 2, Table 1 and Theorem 3).

Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.