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

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, ASYNC, terminating → 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. Three robots never suffice, even if robots may flip coins Devismes et al. 2013. For even \(n\), four robots cannot explore without coins Lamani et al. 2010 (the proof uses an adversary that activates robots with the same snapshot at the same moment), so five is optimal for those rings; for odd \(n\) it is open whether four robots suffice when the adversary may also interleave the three phases of different robots. 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, ASYNC, terminating → Devismes et al. 2021

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. 2021 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, ASYNC, terminating → 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. Whether exploration is also impossible when \(n\) and \(k\) share a smaller common factor is open: it was conjectured Lamani et al. 2010, and a computer check found the algorithm of Flocchini et al. 2013 correct for five robots on rings of 10 and 15 nodes from starts with at most one axis of symmetry Bérard et al. 2016. When \(n\) and \(k\) share no factor and \(k \ge 17\), exploration is solvable Flocchini et al. 2013; 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, ASYNC, terminating standard
Five asynchronous robots explore and stop from any configuration without towers when \(n\) is not a multiple of 5; three never suffice, four never suffice for even \(n\), and \(k\) never suffices when \(k\) divides \(n\).
tight \(5\) vs \(4\) memory
tight \(O(n)\) vs \(\Omega(n)\) every node visited
Grids, ASYNC, terminating
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 —
Rings, SSYNC, terminating
With atomic cycles, four robots explore every ring of odd size \(n > 7\) and stop; fewer than four never suffice, and four do not suffice for even \(n\).
tight \(4\) vs \(4\) memory
unknown — vs —
Rings, probabilistic, SSYNC, terminating
Four robots that flip coins explore any ring of more than four nodes and stop with probability 1; three never suffice, whatever \(n\).
tight \(4\) vs \(4\) memory
unknown — vs —
Rings, ASYNC, exclusive perpetual
Three asynchronous robots explore a ring of \(n \ge 10\) nodes perpetually without collisions when \(3 \nmid n\); one or two robots never can, and three cannot when \(n < 10\).
tight \(3\) vs \(3\) symmetry breaking
unknown — vs —

Open questions 8

Rings, ASYNC, terminating

  1. Can four robots explore and stop on every ring of odd size \(n\) under ASYNC? Four suffice under SSYNC for odd \(n > 7\); the question is posed in Lamani et al. 2010.
  2. For which pairs \((n, k)\) can \(k\) robots explore an \(n\)-node ring Flocchini et al. 2013? In particular, is exploration impossible whenever \(\gcd(n, k) > 1\) and \(k < n\), as conjectured in Lamani et al. 2010? Impossibility is proved only when \(k\) divides \(n\) Flocchini et al. 2013, and for \(k = 4\) with even \(n\) Lamani et al. 2010.
  3. What is the minimum number of robots when \(n\) is a multiple of 5? From model checking on rings of fewer than 18 nodes, Bérard et al. conjecture that the algorithm of Flocchini et al. 2013 is correct for every odd \(k\) with \(5 \le k < 17\) from initial configurations with at most one axis of symmetry Bérard et al. 2016; the lower bounds use more symmetric starts.

Rings, SSYNC, terminating

  1. What is the minimum number of robots under SSYNC when \(n\) is a multiple of 10 (four and five robots are impossible)? This is the SSYNC case of the characterisation of solvable pairs \((n, k)\) asked for in Flocchini et al. 2013.

Rings, probabilistic, SSYNC, terminating

  1. How many moves (or rounds) do four probabilistic robots need to explore a ring of \(n\) nodes and stop, and how does the time decrease when more robots are used? Posed in Devismes et al. 2013, where termination is only shown to be finite.

Rings, ASYNC, exclusive perpetual

  1. What is the minimum number of robots for exclusive perpetual exploration of a ring whose size is a multiple of 3, from every configuration without towers?
  2. Would coin flips help in the cases where deterministic exclusive perpetual exploration is impossible? Posed in Blin et al. 2010.
  3. What is the largest team that can explore exclusively and perpetually from every configuration without towers? Blin et al. 2010 claim \(n - 5\) robots for odd \(k \ge 7\) with \(k \nmid n\), but an SMT check found collisions in their algorithm for 7 and 9 robots on rings of \(k + 5\) nodes under FSYNC Sangnier et al. 2020.

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. On rings, \(k\) robots cannot explore when \(k\) divides \(n\), which forces \(\Omega(\log n)\) robots for infinitely many \(n\), and \(O(\log n)\) robots always suffice Flocchini et al. 2013. Three robots never suffice, even with coin flips; four robots that flip coins suffice under SSYNC Devismes et al. 2013. Without coins, five robots suffice whenever \(n\) is not a multiple of 5, four do not when \(n\) is even, and four suffice for odd \(n > 7\) under SSYNC Lamani et al. 2010; the exact minimum for every \(n\) is still open. On grids three robots suffice and are optimal Devismes et al. 2021. Exclusive perpetual exploration of rings needs three robots when \(n \ge 10\) and \(3 \nmid n\) Blin et al. 2010 Bérard et al. 2016.

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.

Related problems

Gathering by oblivious robots on graphs: The same robots and schedulers on graphs, with exploration as the task.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Ilcinkas 2019 Oblivious robots on graphs: exploration. Survey of terminating and exclusive perpetual exploration by oblivious robots on rings, trees, lines, grids and tori, with the schedulers and multiplicity detection each bound needs. Read.
  • Flocchini et al. 2010 Remembering without memory: tree exploration by asynchronous oblivious robots. Trees: \(\Omega(n)\) robots are needed on some trees; \(O(\log n / \log\log n)\) suffice and are needed when the maximum degree is 3. As reported by Ilcinkas 2019; not read.
  • Flocchini et al. 2011 How many oblivious robots can explore a line. Lines: \(k < n\) robots explore an \(n\)-node line if and only if \(k = 3\), \(k \ge 5\), or \(k = 4\) with \(n\) odd. As reported by Ilcinkas 2019; not read.
  • Devismes et al. 2019 Optimal torus exploration by oblivious robots. Tori: at least 5 deterministic robots; 4 probabilistic robots for large tori. As reported by Ilcinkas 2019; not read.
  • Bonnet et al. 2011 Asynchronous exclusive perpetual grid exploration without sense of direction. Exclusive perpetual exploration of grids without sense of direction under ASYNC: 3 robots, except the \(2 \times 2\) and \(2 \times 3\) grids. As reported by Ilcinkas 2019; not read.
  • Chalopin et al. 2010b Network exploration by silent and oblivious robots. Terminating exploration of arbitrary graphs with port numbers under ASYNC from rigid configurations: impossible with fewer than 3 robots, a characterisation of the graphs explorable by 3 robots, and every graph explorable by 4 robots and by any odd \(k > 3\). As reported by Ilcinkas 2019; not read.
  • Bonnet et al. 2014 Discovering and assessing fine-grained metrics in robot networks protocols. Enumerates all protocols for exclusive perpetual ring exploration; five robots on a 10-node ring are impossible under SSYNC from rigid starts. Abstract read; result as reported by Ilcinkas 2019.
  • Doan et al. 2016 Model checking of a mobile robots perpetual exploration algorithm. Model checking of the three-robot exclusive perpetual algorithm of Blin et al. 2010; finds a collision, like Bérard et al. 2016. As reported by Ilcinkas 2019; not read.
  • Sangnier et al. 2020 Parameterized verification of algorithms for oblivious robots on a ring. Parameterized verification of ring algorithms for oblivious robots: the three-robot exclusive perpetual algorithm of Blin et al. 2010 is collision-free under FSYNC for \(n > 10\), and its \(n - 5\) algorithm has collisions for 7 and 9 robots. Section 4.5 of the 2017 report read.
  • Balabonski et al. 2018a A foundational framework for certified impossibility results with mobile robots on graphs. Coq framework that certifies impossibility results for robots on graphs, such as the \(k \mid n\) argument for ring exploration. Abstract read.
  • Sardar et al. 2022 Grid exploration by a swarm of autonomous robots with minimum repetitions. Terminating exploration of a finite grid by \(k\) oblivious ASYNC robots with unlimited visibility and one pebble each, minimising nodes visited twice: no repeated visit on grids with an even side, at most one on grids with both sides odd, and at most \(n/(k+1) - 1\) on a \(1 \times n\) grid, following Hamiltonian cycles or paths of the grid. Read (model, algorithms and bounds).

All settings

The assumption tree (5 settings, 3 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 › Randomness › Scheduler › Exploration goal › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Scheduler

0asynchronous (ASYNC)1semi-synchronous (SSYNC)2fully synchronous (FSYNC)

Ring exploration by oblivious robots on graphs began under ASYNC with instantaneous moves Flocchini et al. 2013. Devismes, Petit and Tixeuil proved their bounds for probabilistic robots with atomic cycles (SSYNC) Devismes et al. 2013, and Lamani, Potop-Butucaru and Tixeuil wrote their four-robot lower bound for SSYNC (it carries over to ASYNC) and gave a four-robot algorithm for odd \(n\) only under SSYNC Lamani et al. 2010. The scheduler changes the answer: with coin flips, a constant number of robots suffices under SSYNC, while \(\Omega(\log n)\) robots are needed under ASYNC for infinitely many \(n\), as reported by the survey of Ilcinkas, which compares the three schedulers for this problem Ilcinkas 2019.

Formal definitions
0ASYNC
ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may Look while others are between phases, so it may move on an outdated snapshot. A robot is always seen on a node (moves are instantaneous). The scheduler is fair: every robot is activated infinitely often. Called CORDA (with instantaneous moves) in Lamani et al. 2010 and Blin et al. 2010.
1SSYNC
SSYNC: time is divided into rounds; in each round a fair adversary chooses a non-empty subset of robots, which execute one atomic Look–Compute–Move cycle together. Called ATOM in Lamani et al. 2010.
2FSYNC
FSYNC: in every round every robot executes one atomic Look–Compute–Move cycle.

Exploration goal

0both goals: terminating and exclusive perpetual1terminating exploration (explore, then stop)1exclusive perpetual exploration

Terminating exploration of rings by oblivious robots was posed by Flocchini, Ilcinkas, Pelc and Santoro Flocchini et al. 2013. Exclusive perpetual exploration was posed for robots with memory on partial grids by Baldoni, Bonnet, Milani and Raynal (as reported by Blin et al. 2010) and for oblivious robots on rings without chirality by Blin, Milani, Potop-Butucaru and Tixeuil Blin et al. 2010; it models patrolling by physical robots that must not collide. The two goals do not imply each other: a terminating algorithm stops, and an exclusive perpetual one never stops but must avoid towers, which terminating algorithms use to mark the end. The survey of Ilcinkas treats the two goals side by side Ilcinkas 2019.

Formal definitions
0both goals
Solve both terminating and exclusive perpetual exploration with the stated resources (possibly with two algorithms). A lower bound for either goal holds here, and a result here gives both. No variant is catalogued here; the value exists because the two goals do not imply each other.
1terminating
From every allowed initial configuration, every node is visited by at least one robot and the robots reach a configuration in which no robot ever moves again. With coin flips, this must happen with probability 1.
1exclusive perpetual
Every robot visits every node infinitely often, no two robots are ever on the same node, and no two robots ever cross the same edge in opposite directions.

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