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.
Grids, exploration with stop
verifiedThree robots explore any grid with at least three nodes (four for \(2\times2\), five for \(3\times3\)), which is optimal.
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: grid
- \(G\) is a \(\sqrt n\times\sqrt n\) grid graph; whether ports are globally consistent (oriented) is stated per result.
What is known
- grids with at least 3 nodes, deterministic or probabilistic
Results, in order of publication
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.