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.
Finite grids, ASYNC, no multiplicity detection
verifiedOn 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.
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: finite 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.
- Multiplicity detection: no multiplicity detection
- A snapshot shows which nodes are occupied, not how many robots each holds.
- Initial configuration: dispersed start
- Every initially occupied node holds exactly one agent (\(\ell=k\)). Also called a scattered start, notably in black hole search.
- Scheduler: ASYNC
- 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.
- Activation order: any order
- The adversary chooses which robots to activate, subject only to the scheduler's fairness.
What is known
- starts invariant under a rotation by 90 or 180 degrees about the centre of the grid, or symmetric about an axis that passes through edges (Theorem 2); on a grid with both sides odd the centre is a node and every start is solvable (Theorem 1)
- every start with two or more occupied nodes on the \(2 \times 2\) grid, which behaves as a ring of four nodes (Theorem 4)
- the adversary activates symmetric robots together, so every move keeps the symmetry
Results, in order of publication
Introductory and current best (Theorems 1, 3 and 5): on a grid with both sides odd every robot moves to the central node; otherwise the robots read the configuration as strings from the corners and agree on a gathering node, which stays the same while robots move toward it, and towers formed on the way do no harm. Time is not analysed.
Open questions
How many epochs does gathering on finite grids without multiplicity detection take?
Notes
D'Angelo, Di Stefano, Klasing and Navarra show that the unsolvable starts are exactly those listed here: a start is unsolvable if and only if it is invariant under a rotation on a grid with at least one even side, symmetric about an axis through edges, or on the \(2 \times 2\) grid (Section 5). With local multiplicity detection the \(2 \times 2\) grid can be gathered exactly from the starts with three occupied nodes (Theorem 4). On rings no robots gather without multiplicity detection Klasing et al. 2008; on grids and trees they do. Checked against the full text of D'Angelo et al. 2016.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.