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.
Progress map
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.