Exploration by oblivious robots
Oblivious Look–Compute–Move robots that see all robots must visit every node of a ring or grid and stop, or keep visiting every node forever without two robots ever meeting; how many robots are needed?
Problem statement and measuresexpand
\(k\) anonymous, oblivious robots run Look–Compute–Move cycles on an anonymous graph with \(n\) nodes: in a Look a robot takes a snapshot showing which nodes hold no robot, one robot or a tower, it computes from that snapshot only, and it stays or moves to a neighbour. The robots start on distinct nodes (no tower). Two goals are studied. In terminating exploration every node must be visited by at least one robot and the robots must reach a configuration in which no robot ever moves again. In exclusive perpetual exploration every robot must visit every node infinitely often, no two robots may ever be on the same node, and no two robots may ever cross the same edge in opposite directions. The setting fixes the goal, the scheduler (ASYNC, SSYNC or FSYNC) and whether robots may flip coins; which initial configurations an algorithm must handle (every configuration without towers, or only some) is stated with each result. The primary measure is the number of robots; the second is the total number of moves.
Measures: Robots, number of robots needed; Moves, total moves.
Rings, probabilistic, SSYNC, terminating
verifiedFour robots that flip coins explore any ring of more than four nodes and stop with probability 1; three never suffice, whatever \(n\).
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.
- Identifiers: anonymous
- All agents run the same deterministic algorithm on the same input; no agent has a label. Formally the label function is constant: \(\mathrm{id}(a)=\mathrm{id}(b)\) for all agents \(a,b\).
- Randomness: private coins
- Each agent additionally has access to independent fair coin flips; guarantees hold with probability 1, in expectation, or with high probability, as stated per result.
- Scheduler: SSYNC
- 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. Called ATOM in Lamani et al. 2010.
- Exploration goal: terminating
- From every allowed initial configuration, every node is visited by at least one robot and the robots reach a configuration in which no robot ever moves again. With coin flips, this must happen with probability 1.
- Topology: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
Statement for this variant
As the SSYNC setting, but a robot may flip coins in Compute. From every initial configuration without towers, every execution must visit every node, and the robots must reach a configuration in which no robot moves again with probability 1 Devismes et al. 2013.
What is known
- \(k \le 3\), every \(n > k\) (Corollary 2 of the 2009 report)
- proved with a sequential scheduler, except \(k = 3\), \(n = 4\) (Theorem 2)
Results, in order of publication
Introductory and current best. Read in INRIA report RR-6838 (2009), which calls the robots asynchronous but defines atomic cycles; the TCS 2013 version was not read. Rings of five to eight nodes are covered by Devismes 2010, so four probabilistic robots suffice for every \(n > 4\), as Ilcinkas also reports Ilcinkas 2019.
The same model (atomic Look–Compute–Move cycles, oblivious anonymous robots without a common orientation), with the rings that Devismes et al. 2013 leaves out; each size from 5 to 8 is checked separately. Read in the author's copy.
Open questions
How many moves (or rounds) do four probabilistic robots need to explore a ring of \(n\) nodes and stop, and how does the time decrease when more robots are used? Posed in Devismes et al. 2013, where termination is only shown to be finite.
Notes
Randomization removes the number-theoretic conditions of the deterministic setting: four robots suffice for every \(n > 4\) Devismes et al. 2013 Devismes 2010, whereas deterministic robots need \(\Omega(\log n)\) for infinitely many \(n\) even under FSYNC Flocchini et al. 2013. The robots first gather on four consecutive nodes, using coin flips to break symmetry, then build an arrow (a tower next to the block) whose tail robot walks around the ring Devismes et al. 2013. Under ASYNC, coin flips do not help in the worst case: \(\Omega(\log n)\) robots are needed for infinitely many \(n\), as reported by Ilcinkas 2019 (not verified; see the ASYNC setting).
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.