Home›Mobile agents on graphs›Exploration›Graph exploration by a single agent›Rendezvous›Gathering in graphs›Gathering by oblivious robots on graphs

Gathering by oblivious robots on graphs

Oblivious Look–Compute–Move robots must all reach one node of a graph and stay there; which starts can be gathered depends on the symmetries of the graph, on multiplicity detection and on the scheduler.

Problem statement and measurescollapse

Gathering on a tree by asynchronous oblivious robots that cannot see towers, the algorithm of D'Angelo et al. 2016: this tree has two centres, \(c_1\) and \(c_2\), and removing the edge between them (dashed) leaves two halves. The robots of the half with fewer occupied nodes walk towards the other centre while the others wait; when that half is empty, every robot walks to \(c_2\). A tower looks like a single robot, which only lowers the count of the half that is emptying, so the robots never change their choice. One Move per frame, in an order chosen by the scheduler.

\(k \ge 2\) anonymous, oblivious robots stand on the nodes of a connected anonymous graph \(G\) with \(n\) nodes, which every robot sees whole. A robot runs Look–Compute–Move cycles: in a Look it takes a snapshot of the graph with its occupied nodes, it computes from that snapshot only, and it stays or moves to a neighbour; moves are instantaneous, so robots are always seen on nodes. A node with two or more robots is a tower. With multiplicity detection a snapshot shows which nodes are towers (weak) or how many robots each node holds (strong); without it a tower looks like one robot. The robots must reach a configuration in which all of them are on one node and none moves again. A setting fixes the scheduler, the multiplicity detection, whether towers may exist at the start, and the graph class; an algorithm must gather from every start of the setting except the starts listed as unsolvable. Under round robin the scheduler activates one robot at a time in a fixed cyclic order. Time is counted in epochs: an epoch is an interval in which every robot completes at least one cycle (under round robin, \(k\) consecutive activations).

Measures: Time, epochs until all robots are on one node and no robot moves again.

A first look

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

Imagine identical toy trains on a rail network that must all meet at one station, although none of them remembers anything and none can tell how many trains already stand at a station. The network is a graph: stations are nodes, and two nodes joined by an edge are neighbours. The \(k \ge 2\) trains are robots. They are anonymous (the robots are identical and the nodes carry no names) and oblivious (a robot keeps nothing from one activation to the next). Each activation is a Look–Compute–Move cycle. The robot takes a snapshot of the whole graph showing which nodes are occupied, computes from that snapshot alone, and then stays or moves to a neighbour. A node with two or more robots is a tower. With multiplicity detection a snapshot shows the towers; without it a tower looks like a single robot. The scheduler, an adversary, decides when each robot runs its cycle. The robots must reach a configuration (the positions of all of them) in which they all stand on one node, and then never move again. In the standard version the graph is a ring and the robots cannot see towers. Towers may already exist at the start, and the scheduler is round robin: it activates one robot at a time, in a cyclic order that it fixes once and for all. Time is counted in epochs, intervals in which every robot completes at least one cycle.

1AlgorithmOn a tree, walk to the centre Trees, ASYNC, no multiplicity detection → D'Angelo et al. 2016

A tree is a graph without cycles. A centre of a tree is a node whose largest distance to the other nodes is as small as possible; a tree has one centre or two neighbouring centres. The scheduler is asynchronous: Look, Compute and Move take finite but unpredictable times, so a robot may move on the basis of an old snapshot. The robots start on distinct nodes and cannot see towers.

If the tree has one centre, every robot walks to it, one edge per cycle.
If it has two centres, remove the edge between them. This splits the tree into two halves, each holding one centre.
If one half has fewer occupied nodes, its robots walk to the centre of the other half, and the robots of the other half wait.
When that half is empty, every robot walks to the remaining centre.
If the halves have equal numbers of occupied nodes, a fixed way of writing each half as a string, occupied nodes included, picks the half that moves first.

Why it works and what it costs. Each rule depends only on the tree and on which nodes are occupied, so towers that look like single robots do no harm D'Angelo et al. 2016. While a half empties, its number of occupied nodes can only fall and the other half's can only rise, so the robots never change their choice, even when they act on an old snapshot. The robots gather from every start except those in which the two halves are mirror images of each other, robots included (Theorem 6). There the scheduler can activate two mirror-image robots together forever, and the configuration stays symmetric. The paper does not analyse the time.

Why it matters. It shows the method of this problem in its simplest form: the robots agree on a node that the snapshot determines, and the only obstacle is a symmetry that the scheduler can preserve.

2ImpossibilityTwo robots at odd distance never meet Rings, SSYNC, no multiplicity detection → Klasing et al. 2008

Put two robots on a ring (a cycle of nodes) at odd distance, and let the scheduler activate both of them in every round.

Two robots on a ring see the same snapshot, up to a reflection, so they make the same decision: both stay or both move.
Fix one of the two arcs of the ring between them and count its edges. A move of one robot changes that count by one, so when both move it changes by two or not at all.
The count starts odd, so it stays odd and never reaches 0.

Why it holds. So two robots never gather on a ring, whatever the algorithm Klasing et al. 2008. Without multiplicity detection the same holds for any number of robots. Let a single robot create the first tower alone. From then on every snapshot looks like one with fewer robots, and by induction they never gather. This is why Klasing, Markou and Pelc assume multiplicity detection.

Why it matters. It is the basic obstacle on rings: what the robots cannot see or tell apart, the scheduler can keep symmetric.

3ImpossibilityOne robot at a time is not enough unless the order is fixed Rings, sequential scheduler, no multiplicity detection → Navarra & Piselli 2025

Let the scheduler activate one robot at a time but choose the order freely, on a ring with robots that cannot see towers. Just before gathering, all robots stand on two neighbouring nodes. A snapshot shows only two occupied neighbours, so the only useful move is onto the other occupied node (Lemma III.1).

Take robots \(r_1\) and \(r_2\) on node \(u\) and \(r_3\) on node \(v\).
The scheduler activates \(r_1\), which moves to \(v\).
It activates \(r_3\), which moves back to \(u\); then \(r_2\), which moves to \(v\).
It goes on like this, always taking a robot from the node that holds more, so neither node ever empties, and every robot is activated again and again.

Why it holds. So with such a scheduler \(k \ge 3\) robots that cannot see towers never gather on a ring (Theorem III.1) Navarra & Piselli 2025. Round robin removes the scheduler's freedom: the order is fixed once and for all. Navarra and Piselli first make the robots choose an empty gathering node between two groups of robots, then move both groups next to it and finally onto it. Every robot is activated once before any robot is activated again, so the last step works. Their algorithm gathers from every start except a few listed ones, in at most \(n-3\) epochs, which is optimal up to a constant factor.

Why it matters. It shows how much the scheduler matters for robots that cannot count: a fixed order of activations replaces multiplicity detection.

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

Rings, sequential scheduler, no multiplicity detection

If the scheduler may activate the robots one at a time in any fair order, \(k \ge 3\) robots that cannot see towers never gather on a ring.

impossible — vs \(\text{impossible}\) adversarial activation

Rings, round robin, no multiplicity detection standard

Under round robin, robots that cannot see towers gather on a ring from every start except a few listed ones, in at most \(n-3\) epochs, which is optimal up to a constant factor.

tight \(O(n)\) vs \(\text{impossible}\) indistinguishable multiplicities

Rings, round robin, one robot per node at the start

With one robot per node at the start, only three robots on three consecutive nodes and the full 4-node and 5-node rings cannot be gathered; every other start is gathered in at most \(n-3\) epochs.

tight \(O(n)\) vs \(\text{impossible}\) indistinguishable multiplicities

Rings, SSYNC, no multiplicity detection

Without multiplicity detection, \(k \ge 2\) robots cannot gather on any ring when the scheduler may activate several robots in the same round.

impossible — vs \(\text{impossible}\) indistinguishable multiplicities

Rings, ASYNC, weak multiplicity detection

With weak multiplicity detection, an odd number of asynchronous robots gathers on a ring exactly from the starts that are not periodic; two robots never gather.

unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry breaking

Complete graphs, round robin

On a complete graph, robots that cannot see towers never gather under round robin once two nodes are occupied.

impossible — vs \(\text{impossible}\) indistinguishable multiplicities

Complete graphs, FSYNC, strong multiplicity detection

On a complete graph, FSYNC robots that start on distinct nodes and see how many robots each node holds gather exactly when the least prime factor of \(k\) exceeds the number \(n-k\) of empty nodes, in \(O(\log k)\) epochs.

near-optimal \(O(\log k)\) vs \(\text{impossible}\) symmetry breaking

Graphs that are not vertex-transitive, round robin

Under round robin, robots that cannot see towers gather from every start on a finite graph that is not vertex-transitive; time is optimal when the graph has a terminal orbit.

polynomial gap \(O(\ell\,d + n)\) vs \(\Omega(d)\) distance

Hypercubes, round robin

On hypercubes of dimension at least 3, robots that cannot see towers gather under round robin in \(O(\log n)\) epochs from every start except two adjacent occupied nodes, three occupied nodes forming a path, and every node occupied.

tight \(O(\log n)\) vs \(\text{impossible}\) indistinguishable multiplicities

Infinite grid, round robin

On the infinite grid, robots that cannot see towers gather under round robin in a number of epochs linear in their largest distance, from every start except two adjacent occupied nodes and one kind of three-node path.

tight \(O(d)\) vs \(\text{impossible}\) indistinguishable multiplicities

Finite grids, ASYNC, no multiplicity detection

On a finite grid, ASYNC robots that cannot see towers gather from every start except those invariant under a rotation of a grid with an even side, those symmetric about an axis through edges, and every start on the \(2 \times 2\) grid.

unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry breaking

Trees, ASYNC, no multiplicity detection

On a tree, ASYNC robots that cannot see towers gather from every start except those in which removing the edge between the two centres leaves two isomorphic halves, robots included.

unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry breaking

Open questions 5

Rings, round robin, no multiplicity detection

Which sequential schedulers between round robin and an arbitrary sequential scheduler still allow gathering on rings without multiplicity detection? Navarra & Piselli 2025 ask about other sequential schedulers; on graphs that are not vertex-transitive, a new order in every epoch suffices Cicerone et al. 2025d.

Rings, ASYNC, weak multiplicity detection

Even \(k\): which symmetric starts whose axis passes through a node can be gathered? Left open by Klasing et al. 2008; four robots on rings of seven and nine nodes cannot gather from some of them D'Emidio et al. 2018, and the proofs do not extend to other ring sizes. Later ring papers listed in Cicerone et al. 2025d were not read here.

Complete graphs, FSYNC, strong multiplicity detection

Does every algorithm need \(\Omega(\log k)\) epochs on complete graphs for infinitely many \(k\), without assuming infinitely many Fibonacci primes? The lower bound of Cicerone et al. 2021b uses \(k = F_\ell\) robots and \(F_{\ell-1}\) empty nodes, solvable only when \(F_\ell\) is prime.

Graphs that are not vertex-transitive, round robin

Can robots gather in \(O(d)\) epochs on every graph that is not vertex-transitive and has no terminal orbit? Asked in Cicerone et al. 2025d.

Finite grids, ASYNC, no multiplicity detection

How many epochs does gathering on finite grids without multiplicity detection take?

What the community started looking at

Klasing, Markou and Pelc posed the problem on rings for asynchronous robots and showed that it needs multiplicity detection: without it, \(k \ge 2\) robots cannot gather on any ring; with weak detection an odd number of robots gathers exactly from the starts that are not periodic Klasing et al. 2008. Later work kept these assumptions (no towers at the start, multiplicity detection) and solved one graph class at a time, as listed in Cicerone et al. 2025d. A recent series drops multiplicity detection and allows towers at the start, and makes up for it with round robin: rings Navarra & Piselli 2025, graphs that are not vertex-transitive Cicerone et al. 2025d, and hypercubes and infinite grids Cicerone et al. 2025b.

Variant of Gathering in graphs

The task is that of gathering in graphs, all entities on one node, but the entities are oblivious Look–Compute–Move robots, as in exploration by oblivious robots: they see the positions of all robots, remember nothing, carry no labels and send no messages. Whether a start can be gathered then depends on the symmetries of the configuration, on what a robot sees of robots sharing a node, and on the scheduler. Results do not transfer directly in either direction.

All settings

The assumption tree (12 settings, 5 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); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Faults › Network › Multiplicity detection › Initial configuration › Scheduler › Activation order.

tight near-optimal polynomial gap unknown impossible no variant

No assumptions · 1 branches by graph dynamics Nothing is assumed on any axis.
- +static graph+undirected+no faults
  Network · 7 branches

Assumptions specific to this problem

Scheduler

0asynchronous (ASYNC)1semi-synchronous (SSYNC)2sequential: exactly one robot is activated per round2fully synchronous (FSYNC)

The schedulers come from robots in the plane (see the plane model). On graphs gathering was posed under ASYNC Klasing et al. 2008. A sequential scheduler activates one robot at a time, so no two robots with the same snapshot move together; it was used for universal pattern formation in the plane, as reported by Navarra & Piselli 2025, and on rings, where a general sequential scheduler still defeats every algorithm for \(k \ge 3\) robots without multiplicity detection, while round robin does not Navarra & Piselli 2025.

Formal definitions

0ASYNC: ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may Look while others are between phases, so it may move on an outdated snapshot. A robot is always seen on a node (moves are instantaneous). The scheduler is fair: every robot is activated infinitely often.
1SSYNC: SSYNC: time is divided into rounds; in each round a fair adversary chooses a non-empty subset of robots, which execute one atomic Look–Compute–Move cycle together.
2sequential: Sequential: an SSYNC scheduler that activates exactly one robot per round, fairly; which robot is the adversary's choice unless the activation order is fixed (see the order axis).
2FSYNC: FSYNC: in every round every robot executes one atomic Look–Compute–Move cycle.

Activation order

0any order the scheduler chooses1round robin: one robot per round in a fixed cyclic order

Navarra and Piselli took round robin from work on distinct gathering in the plane (as they report) to rings, where it separates the solvable from the unsolvable: under a general sequential scheduler gathering is impossible for \(k \ge 3\) robots without multiplicity detection, under round robin it is characterised Navarra & Piselli 2025. Cicerone, Di Fonso, Di Stefano and Navarra call it favourable, since it breaks every symmetry by activating a single robot, and use it to compensate for the loss of multiplicity detection Cicerone et al. 2025b; their algorithms for graphs that are not vertex-transitive also work if the order changes in every epoch Cicerone et al. 2025d. The order is a separate axis because round robin is a special case of the sequential scheduler only, and says nothing about FSYNC.

Formal definitions

0any order: The adversary chooses which robots to activate, subject only to the scheduler's fairness.
1round robin: With the sequential scheduler: the robots are activated one per round in a cyclic order that the adversary fixes at the start, that the robots do not know, and that repeats forever; an epoch is \(k\) consecutive rounds, one activation per robot.

Multiplicity detection

0none: a tower looks like one robot1global weak: a robot sees which nodes are towers2global strong: a robot sees how many robots each node holds

Klasing, Markou and Pelc proved that without multiplicity detection \(k \ge 2\) robots cannot gather on any ring, and assumed the weak form Klasing et al. 2008. Cicerone, Di Fonso, Di Stefano and Navarra note that most work assumes some multiplicity detection and starts without towers, and drop both under round robin Cicerone et al. 2025b Cicerone et al. 2025d. Strong detection is used where robots must count, as in gathering at a meeting node that minimises the total distance despite crashes Maiti et al. 2026e. Local forms, in which a robot sees only the multiplicity of its own node, are stated per result.

Formal definitions

0no multiplicity detection: A snapshot shows which nodes are occupied, not how many robots each holds.
1weak detection: A snapshot marks every occupied node as holding one robot or more than one.
2strong detection: A snapshot gives the number of robots on every node.

Network

0any connected graph1ring1complete graph1hypercube1infinite square grid1finite grid1tree1finite graphs that are not vertex-transitive

Gathering was solved graph class by graph class: rings first Klasing et al. 2008, then trees, finite and infinite grids, tori, hypercubes, complete and complete bipartite graphs and butterflies, as listed in Cicerone et al. 2025d. On finite grids and trees no multiplicity detection is needed: in ASYNC every start can be gathered unless a symmetry of the graph and the robots forbids it D'Angelo et al. 2016. Classes matter through their symmetries: the more automorphisms a graph has, the fewer nodes robots can tell apart. Under round robin without multiplicity detection, every start on a graph that is not vertex-transitive can be gathered Cicerone et al. 2025d, vertex- and edge-transitive graphs need algorithms specific to the class, and complete graphs cannot be gathered at all Cicerone et al. 2025b. This axis replaces the model's topology axis because the infinite grid and the graphs that are not vertex-transitive are not among the model's values.

Formal definitions

0any graph: Any connected anonymous graph, finite unless stated; robots see it whole but share no orientation.
1ring: An anonymous, unoriented ring of \(n\) nodes.
1complete graph: \(K_n\): every two nodes are neighbours.
1hypercube: The hypercube of dimension \(\log n\): nodes are the \(n\) binary strings of length \(\log n\), neighbours when they differ in one bit. Its diameter is \(D = \log n\).
1infinite grid: The infinite square grid: nodes are the points of \(\mathbb Z^2\), neighbours at Manhattan distance one; finitely many robots.
1finite grid: An anonymous \(a \times b\) grid without orientation: nodes are the points \((i, j)\) with \(1 \le i \le a\) and \(1 \le j \le b\), neighbours at distance one.
1tree: An anonymous tree of \(n\) nodes without orientation.
1not vertex-transitive: A finite connected graph whose nodes fall into at least two orbits, an orbit being a class of nodes that automorphisms of \(G\) map onto each other.

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

Gathering by oblivious robots on graphs

A first look

What is known

Open questions 5

Rings, round robin, no multiplicity detection

Rings, ASYNC, weak multiplicity detection

Complete graphs, FSYNC, strong multiplicity detection

Graphs that are not vertex-transitive, round robin

Finite grids, ASYNC, no multiplicity detection

What the community started looking at

Variant of Gathering in graphs

Related problems

Further reading

All settings

Assumptions specific to this problem

Scheduler

Activation order

Multiplicity detection

Network