Exploration by oblivious robots
Oblivious Look–Compute–Move robots with vision must visit every node of a ring or grid and stop; how many robots are needed?
Problem statement and measuresexpand
\(k\) anonymous, oblivious robots run Look–Compute–Move cycles on an anonymous graph: they see where all robots are, compute, and move to a neighbour. They must visit every node and then stop (or, for perpetual exploration, keep visiting). The primary measure is the number of robots.
Measures: Robots, number of robots needed; Moves, total moves.
Rings, exploration with stop
standard settingverifiedFive robots explore any ring whose size is co-prime with 5; fewer than five cannot 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\).
- Timing: asynchronous
- Each agent's Communicate–Compute–Move steps take finite but unbounded, adversarially chosen time. Time is measured in epochs. An epoch is an interval of time in which every agent completes at least one full Communicate–Compute–Move step; it need not be the shortest such interval. Time is counted by dividing the execution into consecutive epochs, and a bound of \(X\) epochs holds for every such division.
- Topology: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
What is known
- for infinitely many \(n\), when the algorithm must work from every configuration
Results, in order of publication
Solvable for co-prime \(n\) and \(k \ge 17\); unsolvable in general if \(n\) and \(k\) are not co-prime.
Optimal moves; 4 robots suffice probabilistically.
Open questions
None recorded for this variant.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.