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›limited visibility, + transparent, + no faults›ASYNC, + compass

Limited visibility with a compass, ASYNC

verified

Time: unknownColours: tight

With a common compass, asynchronous robots with limited visibility gather in finite time.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Opacitytransparent: every robot sees every robot within range+Faultsno faults+Agreement on coordinatesagreement on both axes (common compass)

Not assumed

Visibilitylimited: robots see only within a fixed radiusSchedulerasynchronous (ASYNC)Lights (persistent memory)oblivious, no light (OBLOT)Movementnon-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 identicalNumber of robotsany \(n\)

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: compass: All robots agree on the directions and orientations of both axes (a common compass); they may still disagree on origin and unit. Called full compass by Efrima and Peleg, who also use half compass (both axis directions, the positive sense of one axis, no chirality), direction-only and axes-only Efrima & Peleg 2009. Agreement on one axis together with common chirality is equivalent: the orientation of the second axis then follows from handedness.
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: any \(n\): Any number \(n\ge 2\) of robots.

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 bound

\(\text{impossible}\) Flocchini et al. 2005

bottlenecksymmetry

holds when

if the initial distance graph is disconnected (Lemma 4.7)
two robots at distance more than \(V\) under a fully synchronous scheduler see the same empty view and keep their distance
holds for any deterministic algorithm, with a compass

Not a bound on the variant itself: it shows that connectivity of the initial distance graph is necessary.

introductory—

current best

\(\text{finite}\)

Flocchini et al. 2005

initial distance graph (edges between robots at distance at most \(V\)) connectedno multiplicity detectionagreement on the directions and orientations of both axes, not on unit or origin

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

tight

No colours.

lower boundnone known

introductory—

current best

\(0\)

Flocchini et al. 2005

initial distance graph (edges between robots at distance at most \(V\)) connectedno multiplicity detectionagreement on the directions and orientations of both axes, not on unit or origin

Results, in order of publication

Flocchini et al. 2005 current best

Time \(\text{finite}\)Colours \(0\)

initial distance graph (edges between robots at distance at most \(V\)) connectedno multiplicity detectionagreement on the directions and orientations of both axes, not on unit or origin

Introductory and current best (Theorem 4.2): all robots gather at a point on the rightmost initial vertical axis. Non-rigid moves with a minimum distance \(\delta\).

Open questions

None recorded for this variant.

Notes

Checked against the full text of Flocchini et al. 2005 (TCS 2005; preliminary version STACS 2001): robots are oblivious, anonymous, fully asynchronous (ASYNC), with non-rigid moves that cover at least a distance \(\delta_r > 0\), no multiplicity detection, and "orientation": agreement on the directions and orientations of both axes, but not on the unit distance or the origin. The authors conclude that "with respect to gathering, orientation is at least as powerful as instantaneous movements".

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

Limited visibility, one common axis, ASYNC

Time \(O(\Delta_0)\)Colours \(0\)

Lower bounds from stronger settings hold here

No catalogued stronger setting.

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