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 measuresexpand
\(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.
Graphs that are not vertex-transitive, round robin
verifiedUnder 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.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Faults: no faults
- All agents follow the algorithm forever.
- Network: not 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.
- Multiplicity detection: no multiplicity detection
- A snapshot shows which nodes are occupied, not how many robots each holds.
- Initial configuration: any start
- Agents start at arbitrary nodes; \(\ell\le k\) nodes are initially occupied, possibly with several agents each.
- Scheduler: sequential
- 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).
- Activation order: round 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.
Statement for this variant
An orbit \(O\) is terminal if every node of \(O\) can be reached from every node outside \(O\) by a path that meets \(O\) only at its end. \(\ell\) is the number of initially occupied nodes and \(d\) the largest distance between two of them. Robots compute the orbits from their snapshot by canonical labelling of the graph.
What is known
- the two robots at distance \(d\) must meet, and each moves at most one edge per epoch (Lemma 1)
- for a worst-case start, \(d = D\)
Results, in order of publication
Introductory and current best (Theorem 5, graphs without a terminal orbit). With a terminal orbit, a simple algorithm gathers in \(O(D)\) epochs (Theorem 1): robots leave the smallest terminal orbit until one of its nodes is occupied, then all walk to that node without entering the orbit elsewhere. Graphs with a universal node, a cut node or an orbit of twins have a terminal orbit (Theorem 3); butterflies and a family of circular graphs have none (Theorem 4). The algorithms also work if the adversary changes the order in every epoch. Read in the arXiv version (v1).
Open questions
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.
Notes
There are no unsolvable starts: the orbits of the graph, which every robot computes, break the symmetry that defeats robots on rings. Checked against the full text of Cicerone et al. 2025d (arXiv v1).
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.