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, SSYNC, terminating
verifiedWith atomic cycles, four robots explore every ring of odd size \(n > 7\) and stop; fewer than four never suffice, and four do not suffice for even \(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: 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 ASYNC setting, from every initial configuration without towers and with global weak multiplicity detection, but each activated robot executes its whole Look–Compute–Move cycle atomically.
What is known
- \(k \le 3\), every \(n > k\), even for probabilistic algorithms (Corollary 2 of the 2009 report)
- even \(n\), \(k = 4\) (Lemma 1)
- initial configuration with two axes of symmetry
- \(k\) divides \(n\), \(k < n\) (Lemma 2.1)
- initial configuration: the \(k\) robots evenly spaced
- holds even under FSYNC
- for infinitely many \(n\) (Theorem 4.1); consequence of the \(k \mid n\) impossibility, which holds even under FSYNC
Results, in order of publication
Algorithm Exploration-odd, in the appendix of the arXiv version (Lemma 14); Ilcinkas 2019 also cites it from there. Introductory and current best. Whether the appendix is in the SIROCCO 2010 version is not known (not read).
Open questions
What is the minimum number of robots under SSYNC when \(n\) is a multiple of 10 (four and five robots are impossible)? This is the SSYNC case of the characterisation of solvable pairs \((n, k)\) asked for in Flocchini et al. 2013.
Notes
The appendix algorithm of Lamani et al. 2010 forms one tower from a symmetric or asymmetric configuration and lets one or two robots walk until a terminal pattern appears. Moves of this algorithm are not analysed. Under FSYNC, Ilcinkas reports that only three robots are a clear lower bound for every \(n\), in particular for odd \(n\) Ilcinkas 2019.
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
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.