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.
Trees, ASYNC, no multiplicity detection
verifiedOn 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.
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: tree
- An anonymous tree of \(n\) nodes without orientation.
- 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
- a tree with two centres such that removing the edge between them leaves two subtrees that are isomorphic, occupied nodes mapped to occupied nodes (Theorem 6)
- every move of a robot in one subtree may be mirrored by the adversary in the other, so the robots never pick one node
Results, in order of publication
Introductory and current best (Section 4): if the tree has one centre, every robot moves to it. With two centres, removing the edge between them splits the tree into two subtrees; the robots of the subtree with fewer occupied nodes move to the other centre, and once their subtree is empty all robots move there. When both subtrees hold as many occupied nodes, a string encoding of the subtrees with their robots picks the side whose robots move first, which breaks the tie. Time is not analysed.
Open questions
None recorded for this variant.
Notes
The unsolvable starts of Theorem 6 are the only ones: every other start on a tree is gathered without multiplicity detection (Section 5 of D'Angelo et al. 2016). 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.