Mobility Matters
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 measurescollapse
towertowertowertowerStart: 5 robots on distinct nodes, n = 8Block: one robot at a time closes a gapTower: the middle robot moves onto a neighbourWalk: the end robot far from the tower walks away from itWalker reaches the group from the other side: every node visited, all stop
Exploration of a ring by five oblivious robots Lamani et al. 2010 (the problem: Flocchini et al. 2013): anonymous robots without memory, on distinct nodes of an anonymous ring with \(n = 8\) nodes (co-prime with 5), run Look–Compute–Move cycles, one robot activated per frame here. They first close the gaps into a block of five, then the middle robot forms a tower, which fixes a direction; one end robot, the walker, moves away from the tower round the ring, and when it is back beside the group the configuration means that every node (shaded) has been visited, and no robot moves again. The rules are simplified from Lamani et al. 2010.

\(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.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine a few identical toy robots on a circular track of \(n\) squares. The track is a ring: its squares are its \(n\) nodes, and two squares side by side are neighbours. The robots cannot talk, they have no memory at all, and they cannot tell clockwise from counterclockwise, yet together they must visit every node and then stop forever. Each robot works in Look–Compute–Move cycles: Look (take a snapshot showing where all robots are), Compute (decide, from that snapshot only, whether to move and where) and Move (move to a neighbour). Robots are oblivious: they forget everything after each cycle. The nodes are anonymous (they have no names), and an adversary (an imagined opponent) decides when each robot is activated. A robot can tell whether several robots stand on one node (such a node is called a tower). The positions of all robots form the configuration. In the basic version \(k\) robots start on distinct nodes of a ring of \(n\) nodes; they must visit every node and then all stop. We count the robots needed.

1AlgorithmGather in a block, build a tower, send one walker Rings, exploration with stop → Lamani et al. 2010

Five robots, on a ring whose size \(n\) is not a multiple of \(5\) Lamani et al. 2010. The rule a robot follows depends only on its current snapshot, so each stage must leave a configuration that announces which stage it is.

  1. Block: while the robots are not on five consecutive nodes (a block), robots move closer together, carefully so that no two land on the same node.
  2. Tower: when the five robots form one block, the middle robot moves onto a neighbour. Now there is exactly one tower, and the configuration is no longer symmetric: it shows a direction.
  3. Walk: one robot, the walker, singled out by its position relative to the tower, moves node by node around the ring, away from the tower.
  4. When the walker reaches the other side of the group, the robots form a special pattern (a tower-chain); this configuration means the ring has been explored, and nobody moves again.
Why it works and what it costs. The condition that \(n\) and \(5\) share no common factor is what lets the robots break symmetry in the first stage (see the third idea for what goes wrong otherwise). Each stage costs \(O(n)\) moves, so the total is \(O(n)\), which is optimal, since the walker must cover the ring. For even \(n\), four robots cannot explore deterministically Lamani et al. 2010, so five is optimal for those rings. The earlier algorithm of Flocchini et al. 2013 needed \(17\) or more robots.

Why it matters. It shows the main technique of the area: memoryless robots store their progress in the shape of their own configuration.

2ImpossibilityThe final configuration must contain a tower Grids, exploration with stop → Devismes et al. 2012

An oblivious robot decides only from its current snapshot. Suppose that the robots stop in a configuration in which every robot is on its own node. That configuration could also be a starting configuration, since robots start on distinct nodes. Started from it, the robots would see snapshots in which they stop, so they would stop at once, after visiting only their own \(k\) nodes, fewer than the \(n\) nodes of the graph. So every final configuration must contain a tower.

Why it holds. A single robot can never make a tower, so one robot can never explore and stop, on any graph with at least two nodes. With more care Devismes et al. 2012 show that two robots are not enough on a grid with at least three nodes, and they give an algorithm with three robots, which is optimal (four for the \(2\times2\) grid, five for the \(3\times3\) grid).

Why it matters. This one-line remark is the starting point of most lower bounds for oblivious robots: termination itself must be written in the configuration.

3ImpossibilityEvenly spaced robots stay evenly spaced Rings, exploration with stop → Flocchini et al. 2013

Let \(k\) divide \(n\), with \(k < n\), for example \(3\) robots on a ring of \(6\) nodes, one on every second node. Every robot takes exactly the same snapshot, the same in both directions. The adversary activates all robots together and, whenever a robot wants to move but cannot tell its two directions apart, sends every robot clockwise. Then all robots do the same thing: either nobody moves, or every robot moves clockwise and the configuration is again evenly spaced. The robots will take this same snapshot forever, so they either stop where they are, having visited only \(k\) nodes, or never stop.

Why it holds. So \(k\) robots cannot explore a ring whose size is a multiple of \(k\). Flocchini et al. 2013 show that exploration is impossible in general whenever \(n\) and \(k\) share a common factor (the full argument is longer), and solvable when they share none and \(k \ge 17\); the five-robot algorithm above later lowered the team size.

Why it matters. Symmetry that robots cannot break is the obstacle behind the number-theoretic conditions that appear throughout the oblivious-robot literature.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Robots
Moves
Rings, exploration with stop standard
Five robots explore any ring whose size is co-prime with 5; fewer than five cannot for even \(n\).
tight \(5\) vs \(5\) symmetry
tight \(O(n)\) vs —
Grids, exploration with stop
Three robots explore any grid with at least three nodes (four for \(2\times2\), five for \(3\times3\)), which is optimal.
tight \(3\) vs \(3\) symmetry
unknown — vs —

What the community started looking at

Robots with no memory must encode progress in their positions, so the first question was the minimum number of robots Flocchini et al. 2013, answered exactly for rings Lamani et al. 2010 and grids Devismes et al. 2012.

Variant of Graph exploration by a single agent

The robots follow the Look–Compute–Move model of the plane, moved to graphs: they see the positions of all robots but remember nothing, so the configuration itself must encode the progress of the exploration.

Derived problems

Exploration by luminous robots: The same Look–Compute–Move robots, but each carries a light with a constant number \(c\) of colours that acts both as persistent memory (the robot sees its own colour in the next cycle) and as a message (every robot within range reads it); in exchange, robots usually see only within a fixed distance \(\varphi\). An oblivious algorithm is a luminous one with \(c = 1\), so algorithms of the parent problem with myopic vision carry over, and lower bounds proved here for any number of colours hold for oblivious robots too Ooshita & Tixeuil 2022.

All settings

The assumption tree (2 settings, 2 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Robots, Moves); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Identifiers › Timing › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.