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, ASYNC, exclusive perpetual
verifiedThree asynchronous robots explore a ring of \(n \ge 10\) nodes perpetually without collisions when \(3 \nmid n\); one or two robots never can, and three cannot when \(n < 10\).
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: deterministic
- The next state and move of an agent are a function of its current state and what it observes.
- 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. Called CORDA (with instantaneous moves) in Lamani et al. 2010 and Blin et al. 2010.
- Exploration goal: exclusive perpetual
- Every robot visits every node infinitely often, no two robots are ever on the same node, and no two robots ever cross the same edge in opposite directions.
- Topology: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
Statement for this variant
From every initial configuration without towers, every robot must visit every node infinitely often, no two robots may ever be on one node, and no two robots may ever cross one edge in opposite directions. Robots have no common chirality (no common sense of clockwise) Blin et al. 2010.
What is known
- \(k \le 2\), \(n \ge 3\): one robot (Lemma 12) and two robots (Corollary 1) in the 2010 report
- a single robot always has a symmetric snapshot, so the adversary moves it back and forth between two nodes
- \(k = 3\) and \(n < 10\) (Theorem 1); in the 2010 report the proof is given for \(n = 4, 5\), the cases \(n = 7, 8\) are omitted, and \(n = 3, 6, 9\) are referred to the \(k \mid n\) case
- \((n - k) \mid n\) with \(n - k > 2\) (evenly spaced empty nodes, Lemma 5), and \(k \in \{n - 4, n - 3, n - 2\}\) from specific symmetric starts (Lemmas 4, 6, 7)
- \(k\) divides \(n\) and \(k < n/2\), \(n \ge 3\) (Lemma 1 of the survey, inspired by Lemma 2.1 of Flocchini et al. 2013)
- initial configuration: the \(k\) robots evenly spaced
- holds even under FSYNC, with global strong multiplicity detection and for robots with memory; deterministic
Results, in order of publication
Not correct as published: model checking found a collision under ASYNC for \(n = 10\) Bérard et al. 2016, also found by Doan, Bonnet and Ogata Doan et al. 2016 (as reported by Ilcinkas 2019); under FSYNC the algorithm was verified collision-free for \(n > 10\) Sangnier et al. 2020. Read in the 2010 research report; the DISC 2010 version was not read.
Corrects rule RC5 of Blin et al. 2010; model-checked under ASYNC for \(n \in \{10, 11, 13, 14, 16\}\) and proved for every such \(n\) (Theorems 2 and 3: from a legitimate configuration the ring is explored perpetually, and a legitimate configuration is always reached). The inductive proof was read for its statements only.
Theorems 6 and 7: the same algorithm also clears the ring perpetually (graph searching). Large teams are possible from rigid starts, so the impossibilities for \(k \ge n - 4\) in Blin et al. 2010 come from symmetric starts.
Open questions
What is the minimum number of robots for exclusive perpetual exploration of a ring whose size is a multiple of 3, from every configuration without towers?
Would coin flips help in the cases where deterministic exclusive perpetual exploration is impossible? Posed in Blin et al. 2010.
What is the largest team that can explore exclusively and perpetually from every configuration without towers? Blin et al. 2010 claim \(n - 5\) robots for odd \(k \ge 7\) with \(k \nmid n\), but an SMT check found collisions in their algorithm for 7 and 9 robots on rings of \(k + 5\) nodes under FSYNC Sangnier et al. 2020.
Notes
Blin, Milani, Potop-Butucaru and Tixeuil posed the problem for oblivious robots without chirality; their three robots cycle through three legitimate configurations, each round shifting all robots one node Blin et al. 2010. Bérard et al. found a collision in that algorithm by model checking under ASYNC: a move computed from an outdated snapshot meets a later move Bérard et al. 2016. Ilcinkas reports, from the DISC version of Blin et al. 2010, that the problem cannot be solved with an even number of robots, even under FSYNC Ilcinkas 2019; this claim was not found in the 2010 report and is unverified. From rigid starts, D'Angelo et al. handle every \(5 \le k \le n - 3\) for \(n \ge 10\) except \((k, n) = (5, 10)\) D'Angelo et al. 2015; Bonnet et al. enumerated all SSYNC protocols for five robots on a ring of 10 nodes and found none (as reported by Ilcinkas 2019; abstract of Bonnet et al. 2014 read). In the text extraction of D'Angelo et al. 2015 the relation symbol in the range of \(n\) in Theorem 6 is lost; \(n \ge 10\) is taken from its contribution paragraph and Theorem 7.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.