Home›Mobile agents on graphs›Exploration›Graph exploration by a single agent›Exploration by oblivious robots
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.
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Robots
Moves
tight
\(5\) vs \(5\)
symmetry
tight
\(O(n)\) vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.