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, terminating
standard settingverifiedFive asynchronous robots explore and stop from any configuration without towers when \(n\) is not a multiple of 5; three never suffice, four never suffice for even \(n\), and \(k\) never suffices when \(k\) divides \(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: 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: 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
The algorithm must work from every initial configuration in which each node holds at most one robot; the robots know neither \(n\) nor any orientation of the ring. Each Look shows the whole ring and, for each node, whether it holds no robot, one robot or several (global weak multiplicity detection). When a robot whose snapshot is symmetric chooses to move, the adversary chooses the direction Flocchini et al. 2013.
What is known
- \(k \le 3\) and every \(n > k\) (Corollary 2 of the 2009 report)
- holds for probabilistic algorithms too
- proved under SSYNC, so it holds under ASYNC; a sequential scheduler suffices except for \(k = 3\), \(n = 4\), settled by enumerating all protocols (Theorem 2)
- an execution must pass through at least \(n - k + 1\) pairwise distinguishable configurations that contain a tower of fewer than \(k\) robots (Corollary 1); three robots have only \(\lfloor n/2 \rfloor\) such configurations (Lemma 5)
- \(k = 4\) and even \(n\), deterministic (Lemma 1)
- initial configuration: four robots with two axes of symmetry
- proved under SSYNC: robots with the same snapshot are activated together, so the four robots act as two
- for odd \(n\) the bound is 4
- \(k\) divides \(n\), \(k < n\) (Lemma 2.1)
- initial configuration: the \(k\) robots evenly spaced
- holds even under FSYNC: the adversary activates all robots and sends them the same way, so every configuration is evenly spaced and none is terminal
- deterministic
- for infinitely many \(n\): \(n = \mathrm{lcm}(1, \dots, m)\), which every \(k \le m\) divides (Theorem 4.1)
- consequence of the \(k \mid n\) impossibility; deterministic; holds even under FSYNC
- each of the \(n - k\) initially empty nodes must be entered by some robot; stated as trivial in Lamani et al. 2010
Results, in order of publication
Theorem 4.1: taking the least \(k \ge 17\) co-prime with \(n\) gives \(O(\log n)\) robots for every \(n\); for prime \(n > 17\), 17 robots suffice. Moves are not analysed.
Introductory and current best for five robots; \(O(n)\) moves, which is optimal. Read in the arXiv version (October 2009); the SIROCCO 2010 version was not read.
Open questions
Can four robots explore and stop on every ring of odd size \(n\) under ASYNC? Four suffice under SSYNC for odd \(n > 7\); the question is posed in Lamani et al. 2010.
For which pairs \((n, k)\) can \(k\) robots explore an \(n\)-node ring Flocchini et al. 2013? In particular, is exploration impossible whenever \(\gcd(n, k) > 1\) and \(k < n\), as conjectured in Lamani et al. 2010? Impossibility is proved only when \(k\) divides \(n\) Flocchini et al. 2013, and for \(k = 4\) with even \(n\) Lamani et al. 2010.
What is the minimum number of robots when \(n\) is a multiple of 5? From model checking on rings of fewer than 18 nodes, Bérard et al. conjecture that the algorithm of Flocchini et al. 2013 is correct for every odd \(k\) with \(5 \le k < 17\) from initial configurations with at most one axis of symmetry Bérard et al. 2016; the lower bounds use more symmetric starts.
Notes
Flocchini, Ilcinkas, Pelc and Santoro posed the problem and showed that robots without memory or communication can still explore a ring: the configuration itself records the phase (set-up, tower creation, exploration) Flocchini et al. 2013. Lamani, Potop-Butucaru and Tixeuil reduced the team to five robots with the same three-phase idea (a block of five, one tower, one walker) Lamani et al. 2010. The lower bounds are proved under SSYNC (fewer than five robots) or FSYNC (\(k \mid n\)), so they hold here; all of them use a symmetric or evenly spaced start, which the problem allows. The four-robot probabilistic algorithm sometimes attributed to Lamani et al. 2010 is due to Devismes, Petit and Tixeuil and needs atomic cycles (see the probabilistic SSYNC setting) Devismes et al. 2013. Ilcinkas reports that the lower bounds hold even with global strong multiplicity detection, while the algorithms use only weak detection Ilcinkas 2019. As reported by Ilcinkas 2019, the \(\Omega(\log n)\) bound remains true for probabilistic algorithms under ASYNC, citing the journal version of Devismes et al. 2013; this is unverified here (the journal version was not read, and the 2009 report read does not contain it). Bérard et al. model-checked the set-up phase of the \(k \ge 17\) algorithm for \(17 \le k \le 21\), \(n \le 22\) and found it correct Bérard et al. 2016.
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
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.