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›+ no faults›+ SSYNC›+ internal light (FSTA)›disoriented, non-rigid, + \(n = 2\)

Rendezvous, internal light (FSTA), SSYNC, non-rigid

verified
Time: unknownColours: tight

A light only its owner sees, that is constant memory, lets two robots meet in SSYNC with 3 colours if they know \(\delta\); 2 colours are impossible.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Visibilityunlimited+Opacitytransparent: every robot sees every robot within range+Faultsno faults+Schedulersemi-synchronous (SSYNC)+Lights (persistent memory)internal light only (FSTA): a robot sees its own light, not the others'+Number of robots\(n = 2\) (rendezvous)

Not assumed

Agreement on coordinatesno agreement on local coordinate systemsMovementnon-rigid: the adversary may stop a move after some minimum distance \(\delta\)Multiplicity detectionnone: a point with several robots looks like one robotRandomnessdeterministicIdentifiersanonymous: 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: 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): internal light (FSTA)
FSTA: each robot has a light with \(c\) colours that only it can see; it persists between cycles (constant persistent memory, no communication). Also called an internal light.
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 Masuzawa 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: \(n = 2\)
Exactly two robots (rendezvous).

What is known

Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known
unknown
Time is not analysed; only solvability.
lower boundnone known
introductory—
current best
\(\text{finite}\)
the robots know the minimum move length \(\delta\)
Colours · colours of the light per robot (0 for oblivious robots)
tight
Exactly 3 colours when \(\delta\) is known.
lower bound
\(3\) Otaka et al. 2026
bottleneckmemory
holds when
  • Theorem 1: 2 colours are impossible, for every \(n \ge 2\)
  • holds even with rigid moves, chirality and a common unit
introductory—
current best
\(3\)
the robots know the minimum move length \(\delta\)

Results, in order of publication

Flocchini et al. 2016 current best
Time \(\text{finite}\)Colours \(3\)
the robots know the minimum move length \(\delta\)

Introductory and current best (Theorem 18).

Open questions

  1. Rendezvous with internal lights in non-rigid SSYNC when \(\delta\) is unknown.

Notes

No self-stabilizing algorithm with internal lights exists, for any number of colours Otaka et al. 2026. No colour-only (class L) algorithm works with internal lights, whatever the memory (Theorem 1 of Flocchini et al. 2016). If the adversary may rescale a robot's frame at every Look, rendezvous with internal lights is impossible for any number of colours (Theorem 1(i) of Masuzawa et al. 2026). 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

Two robots, SSYNC
Rendezvous, internal light (FSTA), ASYNC

Lower bounds from stronger settings hold here

Rendezvous, internal light (FSTA), SSYNC, rigid
Colours \(3\)

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