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 measurescollapse
24545452455Start: symmetric, no multiplicity: all aim at the centreA multiplicity forms; all walk to itFinal: all robots on one point
Gathering: anonymous oblivious robots at distinct points of the plane must meet at one point, not fixed in advance, and stay there. Shown: the strategy of Cieliebak et al. 2012 with weak multiplicity detection, in SSYNC rounds (ringed robots are activated; a move may stop early). In a symmetric configuration every robot computes the same centre; once a single multiplicity exists, every robot walks to it.

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

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine robots scattered over a field that must all meet at one spot, although nobody has said where. There are \(n\) robots, points in the plane at distinct places; their positions form the configuration. Each robot repeats a Look–Compute–Move cycle: it takes a snapshot of where the other robots are (Look), decides on a destination point (Compute) and moves towards it (Move). They are identical, silent and oblivious (they remember nothing from one cycle to the next), and each uses its own local coordinate system (origin, axes, unit of length and handedness), so they agree on no direction. An adversary, the scheduler, decides the activation of robots, that is, when each performs a cycle: in SSYNC time runs in rounds and in each round it activates some of the robots; in ASYNC every phase may take any finite time. The robots must all reach the same point in finite time and stay there (for \(n = 2\) this is called rendezvous). In the standard version \(n \ge 3\), the scheduler is ASYNC, and robots have weak multiplicity detection: they can tell whether a point holds one robot or several (a multiplicity), but not how many.

1AlgorithmCreate one multiplicity, then every robot walks to it ASYNC with weak multiplicity detection → Cieliebak et al. 2012
  1. If exactly one point is a multiplicity, walk straight to it.
  2. Otherwise, look at the shape of the configuration and choose a point that every robot identifies in the same way despite their different local coordinate systems (for example the centre of a symmetric configuration), and move so that exactly one multiplicity appears.
  3. From then on every robot follows rule 1, along paths that never create a second multiplicity.
Why it works and what it costs. A multiplicity is a landmark that no local coordinate system can hide: it looks special to every robot. Step 2 is the hard part, because the robots agree on no direction and the scheduler may stop a robot partway; Cieliebak, Flocchini, Prencipe and Santoro solve it with a case analysis of configuration types and gather \(n \ge 3\) robots in ASYNC from every initial configuration Cieliebak et al. 2012, the catalogue's introductory and current best result for this setting. Time is not analysed. The outline above is the idea of the approach and was not checked against the paper's full text.

Why it matters. It shows how a tiny sensing ability, telling one robot from several, makes an unsolvable problem solvable.

2ImpossibilityTwo oblivious robots cannot meet in SSYNC Two robots, SSYNC → Suzuki & Yamashita 1999

Take two robots, \(A\) and \(B\), and look at the round in which they would finally meet.

(a) If both moved in that round, the scheduler could have activated only one: it lands where the other was heading, not where the other is, so they miss.

(b) If only \(A\) moved and landed on \(B\), the scheduler could have activated both; unless \(B\)'s rule tells it to stay put, \(B\) moves away and they miss again.

So meeting needs a situation in which, when both are activated, one robot jumps onto the other while the other stays. (c) But the robots are identical and agree on no direction, so the adversary can give them local coordinate systems in which each sees the other at the same spot, say one unit to its east. Identical robots with identical snapshots make the same choice: both stay or both move. The lopsided situation never occurs, and they never meet.

Why it holds. Suzuki and Yamashita proved this as Theorem 3.1 of Suzuki & Yamashita 1999, even for robots with common handedness whose moves always reach their destination, so it also holds without these advantages. Natural rules fail in instructive ways: "move to the midpoint" brings the robots closer forever, but the scheduler activates one robot at a time so they never coincide; "move to the other robot" makes them swap places forever when both are activated. Extra power fixes this: with lights that both robots see, two colours suffice even in ASYNC Heriban et al. 2018.

Why it matters. It is the founding impossibility of the field: the scheduler keeps identical robots symmetric, and most later assumptions (multiplicity detection, lights, compasses) are ways to break that symmetry.

3ImpossibilityWithout multiplicity detection, a multiplicity looks like one robot No multiplicity detection, SSYNC → Prencipe 2007

Suppose the robots stand on only two points, say \(n-1\) robots on \(p\) and one robot on \(q\). A robot that cannot detect multiplicities sees just two occupied points, exactly what it would see if there were only two robots. The robots are thrown back into the two-robot situation above, and the scheduler, by activating only some of the robots on a point, can move groups around so that they never all stand together. Prencipe shows that against any algorithm the scheduler can first drive the robots into such special configurations and then keep them from ever gathering; the full proof is a longer case analysis.

Why it holds. The result holds for deterministic oblivious robots without multiplicity detection, for every \(n \ge 2\), in SSYNC and ASYNC Prencipe 2007. In the fully synchronous model, by contrast, gathering needs no multiplicity detection Flocchini et al. 2026, and in ASYNC weak multiplicity detection is enough Cieliebak et al. 2012.

Why it matters. It explains why weak multiplicity detection became the standard assumption for gathering.

4AlgorithmShort sight but a common compass: drift right, then down Limited visibility with a compass, ASYNC → Flocchini et al. 2005

Now each robot sees only the robots within distance \(V\) (its visibility radius), but all robots agree on north and east (a common compass).

  1. If you see a robot to your left, or above you on your own vertical line, do nothing.
  2. If you see robots only below you on your vertical line, move down towards the nearest one.
  3. If you see robots only to your right, move horizontally to the vertical line of the nearest one.
  4. If you see robots both below you and to your right, make a diagonal move right and down, chosen so that you lose sight of nobody.
Why it works and what it costs. Robots only move right or down and never beyond the rightmost vertical line that holds a robot in the initial configuration, so they collect on that line and then at its lowest occupied point; the delicate part of the proof is that nobody is left behind out of sight. Flocchini, Prencipe, Santoro and Widmayer prove that this gathers ASYNC robots with non-rigid moves (Theorem 4.2 of Flocchini et al. 2005), provided the initial configuration is connected (robots joined when at most \(V\) apart); a disconnected initial configuration cannot be gathered at all. With agreement on one axis only, time linear in the initial diameter is achievable and optimal Poudel & Sharma 2021.

Why it matters. It shows how a shared direction can replace global vision: robots that see little can still agree where to go.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Colours
Rendezvous, internal light (FSTA), SSYNC, non-rigid
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.
unknown \(\text{finite}\) vs —
tight \(3\) vs \(3\) memory
Rendezvous, internal light (FSTA), SSYNC, rigid
With rigid moves, robots with internal lights meet in SSYNC with exactly 3 colours.
unknown \(\text{finite}\) vs —
tight \(3\) vs \(3\) memory
Gathering, internal light (FSTA), SSYNC, non-rigid
With internal lights, 2 colours gather \(n \ge 3\) robots in SSYNC only from restricted starts; 2 colours do not suffice in general, and whether more do is open.
unknown \(\text{finite}\) vs —
unknown \(2\) vs \(3\) memory
Rendezvous, external light (FCOM), SSYNC
With a light only the other robot sees, two robots meet in SSYNC with 3 colours, and 2 colours are impossible.
unknown \(\text{finite}\) vs —
tight \(3\) vs \(3\) memory
Gathering, external light (FCOM), SSYNC, rigid
With external lights, \(n \ge 3\) robots gather in rigid SSYNC with 3 colours, which is optimal; 2 suffice if a robot sees who shares its point.
unknown \(\text{finite}\) vs —
tight \(3\) vs \(3\) memory
No multiplicity detection, SSYNC
Without multiplicity detection, deterministic oblivious robots cannot gather, for any \(n \ge 2\), in SSYNC or ASYNC.
impossible — vs \(\text{impossible}\) indistinguishable multiplicities
impossible — vs —
Two robots, SSYNC
Two oblivious robots without a common orientation cannot meet in SSYNC: rendezvous needs extra power.
impossible — vs \(\text{impossible}\) symmetry
impossible — vs —
Homonymous robots, SSYNC
Two distinct identifiers (two different algorithms) are necessary and sufficient for gathering in SSYNC.
unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry
tight \(0\) vs —
Gathering, full lights, SSYNC, no multiplicity detection
With lights and chirality, \(n \ge 3\) robots that cannot detect multiplicities gather in SSYNC with 2 colours, which is optimal.
unknown \(\text{finite}\) vs —
tight \(2\) vs \(2\) indistinguishable multiplicities
Rendezvous, full lights (LUMI), ASYNC, non-rigid
Two robots whose lights both can see meet in ASYNC with non-rigid moves using 2 colours, which is optimal, from any initial colours.
unknown \(\text{finite}\) vs —
tight \(2\) vs \(2\) symmetry breaking
Gathering, full lights, ASYNC, no multiplicity detection
With lights and chirality, \(n \ge 3\) robots gather in ASYNC with non-rigid moves and no multiplicity detection using 3 colours; whether 2 suffice is open.
unknown \(\text{finite}\) vs —
tight \(3\) vs \(2\) indistinguishable multiplicities
Rendezvous, external light (FCOM), ASYNC, non-rigid
In ASYNC with non-rigid moves, robots with external lights meet with 3 colours if they know the minimum move \(\delta\); without \(\delta\) the question is open, and colour-only algorithms cannot work.
unknown \(\text{finite}\) vs —
tight \(3\) vs \(3\) memory
Rendezvous, external light (FCOM), ASYNC, rigid
With rigid moves, robots with external lights meet in ASYNC; the best count is 6 colours against a lower bound of 3.
unknown \(\text{finite}\) vs —
tight \(6\) vs \(3\) memory
ASYNC with weak multiplicity detection standard
With weak multiplicity detection, \(n \ge 3\) oblivious, disoriented, asynchronous robots gather from any initial configuration.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Rendezvous, internal light (FSTA), ASYNC
Whether robots with internal lights can meet in ASYNC is open.
unknown — vs —
unknown — vs \(3\) memory
Gathering, external light, sequential scheduler
If one robot moves per round, 2 external colours gather \(n \ge 3\) robots, self-stabilizing, without chirality; oblivious robots cannot.
unknown \(\text{finite}\) vs —
tight \(2\) vs \(2\) memory
Crash faults, SSYNC
With weak multiplicity detection and no common orientation, the correct robots gather despite up to \(n-1\) crashes.
unknown \(\text{finite}\) vs \(\text{impossible}\) indistinguishable multiplicities
tight \(0\) vs —
Rendezvous, full lights, a crash, SSYNC
If the correct robot must reach a crashed one, two robots cannot meet in SSYNC, even with unboundedly many colours, rigid moves and a common coordinate system.
impossible — vs \(\text{impossible}\) indistinguishable crashes
impossible — vs —
Byzantine faults, SSYNC
Three robots with one Byzantine robot can neither gather nor converge in SSYNC.
impossible — vs \(\text{impossible}\) indistinguishable Byzantine agents
impossible — vs —
Byzantine faults, FSYNC
In FSYNC, gathering tolerates \(f\) Byzantine robots when \(n \ge 3f+1\).
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Limited visibility with a compass, ASYNC
With a common compass, asynchronous robots with limited visibility gather in finite time.
unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry
tight \(0\) vs —
Limited visibility, one common axis, ASYNC
With one common axis, asynchronous robots with limited visibility gather in time linear in the initial diameter, which is optimal.
tight \(O(\Delta_0)\) vs \(\Omega(\Delta_0)\) distance
tight \(0\) vs —
Limited visibility, FSYNC, disoriented
Disoriented robots with limited visibility gather in \(O(\Delta_0^2)\) synchronous rounds, \(\Delta_0\) the initial diameter.
tight \(O(\Delta_0^2)\) vs \(\Omega(\Delta_0^2)\) locality
tight \(0\) vs —
Fat robots, few robots, no common orientation
Three and four oblivious fat robots, which block each other's view and motion, gather in ASYNC without any common orientation.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Fat robots, chirality, any number
With chirality and known \(n\), any number of opaque fat robots gather in ASYNC with non-rigid moves.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Transparent fat robots, no chirality
Transparent fat robots without chirality gather into a layered pattern from every start whose robots can be ordered, which is exactly the asymmetric starts.
unknown \(\text{finite}\) vs —
tight \(0\) vs —

Open questions 16

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

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

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

  1. Gathering with internal lights in SSYNC from every start, with more than 2 colours, and in ASYNC Otaka et al. 2026.

Gathering, external light (FCOM), SSYNC, rigid

  1. Gathering with external lights in ASYNC Otaka et al. 2026.

Homonymous robots, SSYNC

  1. What is the minimum number of identifiers for Byzantine-tolerant gathering? Asahiro & Yamashita 2025

Gathering, full lights, SSYNC, no multiplicity detection

  1. Gathering with lights without chirality Terai et al. 2023.

Gathering, full lights, ASYNC, no multiplicity detection

  1. Is 3 the minimum number of colours for ASYNC gathering with lights, and can chirality be dropped Nakai et al. 2021?
  2. Self-stabilizing gathering of \(n\) robots with lights Heriban et al. 2018.

Rendezvous, external light (FCOM), ASYNC, non-rigid

  1. Rendezvous with external lights in non-rigid ASYNC when \(\delta\) is unknown Flocchini et al. 2016 Masuzawa et al. 2026.

Rendezvous, external light (FCOM), ASYNC, rigid

  1. Close the gap between 3 and 6 colours Masuzawa et al. 2026.

ASYNC with weak multiplicity detection

  1. How many epochs does oblivious ASYNC gathering with weak multiplicity detection need?

Rendezvous, internal light (FSTA), ASYNC

  1. Can robots with internal lights solve rendezvous in ASYNC Flocchini et al. 2016 Masuzawa et al. 2026?

Crash faults, SSYNC

  1. "The maximum number of faults under which a solution is still feasible, for gathering and other tasks, has yet to be established" Agmon & Peleg 2006, in particular in ASYNC.

Limited visibility, FSYNC, disoriented

  1. Is \(\Omega(\Delta_0^2)\) necessary for every protocol, not only local convex-hull ones?

Fat robots, few robots, no common orientation

  1. Gathering any number of fat robots without chirality Agathangelou et al. 2013.

Fat robots, chirality, any number

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

Transparent fat robots, no chirality

  1. Gathering transparent fat robots from symmetric starts; the paper proves no general impossibility Chaudhuri & Mukhopadhyaya 2015.

What the community started looking at

Gathering started with an impossibility: two oblivious robots cannot meet in SSYNC Suzuki & Yamashita 1999. The community's main question became the weakest set of capabilities that makes gathering solvable: multiplicity detection Cieliebak et al. 2012, a compass under limited visibility Flocchini et al. 2005, lights for two robots Das et al. 2016 Flocchini et al. 2016 Heriban et al. 2018, and how many faulty robots can be tolerated Agmon & Peleg 2006 Pattanayak et al. 2019. Running time (rounds, epochs) became a measure mainly for limited visibility Degener et al. 2011 Castenow et al. 2022.

Special case of k-grouping

Gathering is \(k\)-grouping with \(k = 1\), a single group of all \(n\) robots, that is, point formation: the pattern consisting of one point of multiplicity \(n\) Flocchini et al. 2017 Flocchini et al. 2026. General pattern formation algorithms usually exclude it, because multiplicity points need detection Bramas & Tixeuil 2016.

Derived problems

Near-gathering: Gathering requires a common point; near-gathering only requires being close, but forbids collisions. It is used as a first phase before forming patterns.

Related problems

Convergence: Every gathering algorithm solves convergence, but not conversely: two oblivious robots in SSYNC cannot gather, while "two oblivious robots can converge to a point with a naive algorithm" Izumi et al. 2012. In ASYNC the centre-of-gravity algorithm converges for any \(n\) Cohen & Peleg 2005, whereas gathering needs extra assumptions such as multiplicity detection.

Scattering: Scattering is the opposite task: gathering creates a multiplicity point, scattering removes all of them. Pattern formation from configurations with multiplicities needs scattering first Bramas & Tixeuil 2016.

Perspectives

  • Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
  • Symmetry is the adversary Identical agents running the same deterministic program can be kept in lockstep forever. Across graphs, the plane and programmable matter, the papers break this symmetry with identifiers, with randomness, with asymmetric starts, or with the scheduler, and leader election keeps reappearing as the common core.
  • Meeting at one place Rendezvous and gathering on graphs, gathering and convergence in the plane, and evacuation through an unknown exit all ask entities to end at one point. The papers give the same reasons for meeting, but each model makes a different part of it hard: symmetry and exploration on graphs, capability in the plane, information in continuous search.
  • Weak robots in the plane Why the theory of robots in the plane starts from oblivious, anonymous, disoriented points; how formation problems became its testbed and the scheduler its adversary; and how a light with a few colours turned into memory, communication and a measure.
  • When agents fail A node that destroys visitors, a robot that stops, an agent that lies, a searcher that misses the target: the papers motivate each fault by the hardware or the network, and each kind of fault changes a different measure, from team size to feasibility to an exact constant.
  • What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.
  • The most consequential open problems Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.

All settings

The assumption tree (26 settings, 13 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Colours); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Body › Visibility › Opacity › Faults › Scheduler › Lights (persistent memory) › Agreement on coordinates › Movement › Multiplicity detection › Randomness › Identifiers › Number of robots.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Number of robots

0any \(n\)1\(n = 2\) (rendezvous)1\(n \ge 3\)

Suzuki and Yamashita Suzuki & Yamashita 1999 showed that two oblivious robots cannot gather deterministically in SSYNC, although the task is trivial in FSYNC; rendezvous thus became the first separator between the two schedulers Flocchini et al. 2023 Heriban et al. 2018. For \(n \ge 3\) robots the situation differs: with multiplicity detection, oblivious disoriented robots gather from any configuration even in ASYNC Cieliebak et al. 2012, because a multiplicity point, once formed, can be kept unique and serve as the target Bandettini et al. 2011. As Flocchini, Santoro, Viglietta and Yamashita put it, "Rendezvous is very different from the Gathering problem of having \(k \geqslant 3\) robots meet" Flocchini et al. 2016 (their \(k\) is \(n\) here). Two robots cannot create such an asymmetry, so the two-robot case became the test bed for each new capability: unreliable compasses Izumi et al. 2012, persistent memory Suzuki & Yamashita 1999, lights Viglietta 2013 Heriban et al. 2018 Okumura et al. 2023, and finite-state or finite-communication robots Flocchini et al. 2016. The catalogue therefore splits gathering by team size: any \(n \ge 2\), exactly two (rendezvous), and \(n \ge 3\).

Formal definitions
0any \(n\)
Any number \(n\ge 2\) of robots.
1\(n = 2\)
Exactly two robots (rendezvous).
1\(n \ge 3\)
\(n\ge 3\) robots.

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