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›oblivious, disoriented, anonymous, + \(n \ge 3\)

No multiplicity detection, SSYNC

verified

Time: impossibleColours: impossible

Without multiplicity detection, deterministic oblivious robots cannot gather, for any \(n \ge 2\), in SSYNC or ASYNC.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Visibilityunlimited+Opacitytransparent: every robot sees every robot within range+Faultsno faults+Schedulersemi-synchronous (SSYNC)+Number of robots\(n \ge 3\)

Not assumed

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\)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): 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 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 \ge 3\): \(n\ge 3\) robots.

What is known

Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known

impossible

Impossible in general.

lower bound

\(\text{impossible}\) Prencipe 2007

bottleneckindistinguishable multiplicities

holds when

Theorem 2: deterministic oblivious robots, no multiplicity detection
\(n \ge 2\): Prencipe proves \(n \ge 3\) (Lemmas 5 and 6) and takes \(n = 2\) from Suzuki and Yamashita
SSYNC (Atom) and ASYNC (Corda)
non-rigid moves, unlimited visibility, no common coordinate system

introductory—

current best—

Colours · colours of the light per robot (0 for oblivious robots)

impossible

Impossible for oblivious robots.

lower boundnone known

introductory—

current best—

Results, in order of publication

No result recorded yet.

Open questions

None recorded for this variant.

Notes

Prencipe uses chirality to mean agreement on North and East (a compass), not handedness. Agmon & Peleg 2006 attribute the necessity of multiplicity detection in SSYNC and ASYNC to Prencipe's thesis (2002). Checked against the SIROCCO 2005 version; the TCS 2007 version was not read.

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.