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›fat, + unlimited visibility›opaque, + no faults›+ chirality, + \(n \ge 3\)

Fat robots, chirality, any number

verified
Time: unknownColours: tight

With chirality and known \(n\), any number of opaque fat robots gather in ASYNC with non-rigid moves.

Assumed (added on the last edge are outlined)

+Visibilityunlimited+Faultsno faults+Agreement on coordinatescommon chirality (same clockwise orientation)+Number of robots\(n \ge 3\)

Not assumed

Bodyfat robots (unit discs)Opacityopaque: collinear robots hide each otherSchedulerasynchronous (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 identical
Formal definitions of this setting
Body: fat
Each robot is a closed disc of radius 1 (unit disc). Discs may not overlap, so robots cannot share a point and must avoid collisions; a disc hides what lies behind it from other robots. Gathering then asks for a configuration whose union of discs is connected and in which every robot sees all others Czyzowicz et al. 2009.
Visibility: unlimited visibility
A robot sees all robots (subject to opacity).
Opacity: opaque
Robots are points that obstruct sight: \(r\) sees \(s\) iff no third robot lies on the open segment \(\overline{rs}\).
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: chirality
All local coordinate systems have the same handedness (clockwise orientation): no reflection. Also called handedness. Prencipe uses chirality for agreement on North and East, i.e. a compass Prencipe 2007.
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.

Statement for this variant

Gathering is Definition 1 of Agathangelou et al. 2013: a connected configuration (every disc tangent to another), fully visible (every robot sees all others) and terminal, with all centres on the convex hull.

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.
lower boundnone known
introductory—
current best
\(\text{finite}\)
\(n\) knownthe radius is the common unit of distancerobots that become tangent stop
Colours · colours of the light per robot (0 for oblivious robots)
tight
No colours.
lower boundnone known
introductory—
current best
\(0\)
\(n\) knownthe radius is the common unit of distancerobots that become tangent stop

Results, in order of publication

Agathangelou et al. 2013 current best
Time \(\text{finite}\)Colours \(0\)
\(n\) knownthe radius is the common unit of distancerobots that become tangent stop

Introductory for any \(n\) and current best (Theorem 26).

Open questions

  1. Remove the chirality assumption Agathangelou et al. 2013.

Notes

Checked against the full text (arXiv 1209.3904).

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

Fat robots, few robots, no common orientation
Time \(\text{finite}\)Colours \(0\)

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