Mobility Matters
Home›Mobile agents on graphs›Exploration›Graph exploration by a single agent›Collision-free exploration

Collision-free exploration

Agents start at distinct nodes of a graph and must explore it so that no two agents are ever at the same node; how long does it take, and what must the agents sense of each other?

Problem statement and measurescollapse
12312round 0nodes visited: agent 1: 1 of 6, agent 2: 1 of 6, agent 3: 1 of 6round 1, colour 1nodes visited: agent 1: 2 of 6, agent 2: 2 of 6, agent 3: 2 of 6round 2, colour 2nodes visited: agent 1: 3 of 6, agent 2: 2 of 6, agent 3: 3 of 6round 3, colour 3nodes visited: agent 1: 3 of 6, agent 2: 2 of 6, agent 3: 3 of 6round 4, colour 1nodes visited: agent 1: 3 of 6, agent 2: 2 of 6, agent 3: 3 of 6round 5, colour 2nodes visited: agent 1: 3 of 6, agent 2: 3 of 6, agent 3: 3 of 6round 6, colour 3nodes visited: agent 1: 4 of 6, agent 2: 3 of 6, agent 3: 4 of 6round 7, colour 1nodes visited: agent 1: 5 of 6, agent 2: 3 of 6, agent 3: 5 of 6round 8, colour 2nodes visited: agent 1: 5 of 6, agent 2: 3 of 6, agent 3: 5 of 6round 9, colour 3nodes visited: agent 1: 5 of 6, agent 2: 4 of 6, agent 3: 5 of 6round 10, colour 1nodes visited: agent 1: 5 of 6, agent 2: 5 of 6, agent 3: 5 of 6round 11, colour 2nodes visited: agent 1: 6 of 6, agent 2: 5 of 6, agent 3: 6 of 6round 12, colour 3nodes visited: agent 1: 6 of 6, agent 2: 5 of 6, agent 3: 6 of 6round 13, colour 1nodes visited: agent 1: 6 of 6, agent 2: 5 of 6, agent 3: 6 of 6round 14, colour 2nodes visited: agent 1: 6 of 6, agent 2: 6 of 6, agent 3: 6 of 6round 15, colour 3nodes visited: agent 1: 6 of 6, agent 2: 6 of 6, agent 3: 6 of 6round 16, colour 1nodes visited: agent 1: 6 of 6, agent 2: 6 of 6, agent 3: 6 of 6round 17, colour 2nodes visited: agent 1: 6 of 6, agent 2: 6 of 6, agent 3: 6 of 6round 18, colour 3nodes visited: agent 1: 6 of 6, agent 2: 6 of 6, agent 3: 6 of 6112233Start: a map with a 3-colouring of the edges; agents on three nodesRound 1, colour 1: agents 2 and 3 cross the same edge; no collisionRound 2, colour 2: an agent with no edge of that colour waitsFinal, round nΔ = 18: every agent visited all 6 nodes and is back home
Collision-free exploration of a tree with a map, Algorithm Tree-Exploration of Czyzowicz et al. 2017a: every agent computes the same colouring of the edges with \(\Delta = 3\) colours (no two edges at a node share a colour). In round \(r\) the colour is \(1 + (r-1) \bmod \Delta\) (thick edges), and every agent crosses the edge of that colour at its node if there is one, otherwise it waits. The edges of one colour share no node, so two agents can only swap across an edge, which is not a collision. After \(n\Delta = 18\) rounds every agent has visited every node and is back at its start node, and no algorithm is faster on this tree.

\(k \ge 2\) agents start at distinct nodes of a connected undirected graph \(G\) with \(n\) nodes and move in synchronous rounds: in each round an agent stays or crosses one edge. A collision is two agents at the same node in the same round; two agents that cross one edge in opposite directions do not collide and do not notice it. Exploration is collision-free if no collision ever happens, also with an agent that an adversary has not yet woken up. Unless a setting says otherwise, every agent must visit every node and then stop. The agents run the same deterministic algorithm, cannot mark nodes and send no messages; what they perceive of each other (their vision) and what they know of \(G\) are fixed by the setting, and in some settings an oracle places coloured pebbles on nodes before the start. Time is the number of rounds from the wake-up of the later agent until every agent has stopped. \(X(n)\) is the time of a single-agent exploration procedure for graphs with at most \(n\) nodes, used as a building block (polynomial in \(n\), for instance with a universal exploration sequence).

Measures: Time, rounds from the wake-up of the later agent until all agents have stopped; Colours, number of pebble colours the oracle needs, when pebbles are used.

A first look

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

Picture night guards in a museum who must each check every room, where no two guards may ever stand in the same room at the same moment. The museum is a graph: its rooms are nodes and the doorways between them are edges; it has \(n\) nodes. The guards are agents. They start on distinct nodes and move in synchronous rounds: in each round an agent stays where it is or crosses one edge. A collision is two agents on the same node in the same round. Two agents that cross the same edge in opposite directions pass each other unnoticed, and that is not a collision. Every agent must visit every node and then stop, without any collision. An adversary, an opponent who knows the algorithm, chooses where the agents start and the round in which each one wakes up. The agents run the same deterministic algorithm, cannot mark nodes and send no messages. What they perceive of each other is their vision. In the standard version there are two identical agents that see everything within two edges of their node, and that know an upper bound on \(n\). In other versions the nodes carry labels and the agents may have a map, or an oracle places coloured pebbles on some nodes before the start. We measure time: the number of rounds until all agents have stopped.

1AlgorithmOne colour per round Labelled trees, with a map, any number of agents → Czyzowicz et al. 2017a

Suppose the graph is a tree (a graph without cycles), its nodes carry labels, and every agent has a map but does not know where the others are. Let \(\Delta\) be the largest number of edges at a node.

  1. Every agent computes the same colouring of the edges with \(\Delta\) colours in which no two edges at a node share a colour; a tree always has one.
  2. In round \(r\) the colour is \(1 + (r-1) \bmod \Delta\), so the rounds run through the colours \(1, 2, \dots, \Delta\) and start again.
  3. In each round every agent crosses the edge of that round's colour at its node, if there is one, and otherwise waits.
  4. After \(n\Delta\) rounds every agent stops.
Why it works and what it costs. Suppose two agents ended a round on the same node \(w\). An agent that moved came along the only edge of that colour at \(w\), and two agents cannot both have come along it, since they started on different nodes. An agent cannot have waited at \(w\) either, since \(w\) has an edge of that colour. So no collision ever happens (Lemma 3.1). Each agent's walk goes into every branch of the tree and back. After exactly \(n\Delta\) rounds it has visited every node and is back at its start node (Lemma 3.2) Czyzowicz et al. 2017a. On any graph with labelled nodes and a map, the agents run the same procedure on a spanning tree whose largest degree \(\Delta^*\) is as small as possible, in \(O(n\Delta^*)\) rounds. That is optimal up to a constant factor. Finding that tree is NP-hard, but one of largest degree \(\Delta^* + 1\) can be found in polynomial time.

Why it matters. Colouring the edges turns a coordination problem into a timetable that every agent can follow alone, and it is exactly optimal on trees.

2Lower boundCongestion: \(n\Delta\) rounds on every tree Labelled trees, with a map, any number of agents → Czyzowicz et al. 2017a

Put an agent on every node of a tree and look at a node \(u\) with \(\Delta\) edges.

  1. In each round at most one agent enters \(u\), otherwise two would collide there.
  2. Every agent must visit all \(\Delta\) branches at \(u\) and come back to its start node. In a tree each branch is reached only through \(u\), so every agent enters \(u\) at least \(\Delta\) times.
  3. Together the \(n\) agents enter \(u\) at least \(n\Delta\) times, at most once per round.
Why it holds. So some agent is still moving in round \(n\Delta\), and the colouring algorithm is exactly optimal on every tree (Theorem 3.2) Czyzowicz et al. 2017a. An agent does not know how many others there are, so its walk must also work when every node is occupied, and the bound applies to any number of agents. On a star, one node joined to \(n-1\) others, it is \(n(n-1)\) rounds. So agents that explore a tree with labelled nodes without a map in \(O(n^2)\) rounds are optimal in the worst case.

Why it matters. The bottleneck is a single busy node, the same congestion argument that bounds routing in networks.

3ImpossibilityWith vision of radius 1, two agents collide on a star Two agents, anonymous graphs, vision of radius 1 → Bhagat & Pelc 2025

Take a star: a centre node joined by edges to leaves, nodes with a single edge. Two identical agents start on two leaves and see only their own node, its neighbours and any agent there (vision of radius 1).

  1. From a leaf an agent sees only the centre, so it cannot see the other agent.
  2. The only way out of a leaf is the centre. The algorithm must tell each agent to wait some number of rounds after waking up and then step onto the centre; the number may depend on what the agent sees.
  3. The adversary wakes the agent with the shorter wait later, by the difference between the two waits.
Why it holds. Both agents then step onto the centre in the same round and collide, whatever the algorithm Bhagat & Pelc 2025. With vision of radius 2, an agent on a leaf also sees the other leaves and any agent on them. Bhagat and Pelc show that two identical agents that know an upper bound on \(n\) then explore every graph with more than two nodes without collisions, at most a factor \(\log n\) slower than a single agent. A later preprint reports a flaw in their stopping procedure and gives a faster corrected algorithm Papin 2026. Neither claim is checked here, so the standard setting remains a draft.

Why it matters. It shows what vision buys: one more edge of sight separates impossible from possible for two agents.

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
Time
Colours
Two agents sensing presence, no pebbles
Two identical agents that only sense each other's presence cannot explore even a path of three nodes without help.
impossible — vs \(\text{impossible}\) symmetry breaking
impossible — vs —
Two agents sensing presence, with coloured pebbles
With pebbles placed by an oracle, two agents that only sense each other's presence explore any graph without collisions using three colours; one colour does not suffice.
unknown \(O(\Delta^D)\) vs —
tight \(3\) vs \(2\) symmetry breaking
Two agents sensing presence, with coloured pebbles, bipartite graphs
On bipartite graphs two colours of pebbles suffice, in polynomial time, and then each agent even visits every node.
unknown \(\mathrm{poly}(n)\) vs —
tight \(2\) vs \(1\) symmetry breaking
Two agents, anonymous graphs, vision of radius 2 standard
Two identical agents that see two edges around them and know a bound on \(n\) explore any graph with more than two nodes without collisions, at most a factor \(\log n\) slower than one agent.
unknown \(O(X(n))\) vs —
tight — vs —
Two agents, anonymous graphs, vision of radius 1
With vision of radius 1, two identical agents cannot explore a star without colliding.
impossible — vs \(\text{impossible}\) symmetry breaking
impossible — vs —
Anonymous graphs, nothing known
In anonymous graphs, agents that know no bound on \(n\) cannot explore and stop, whatever their number and their vision.
impossible — vs \(\text{impossible}\) symmetry breaking
impossible — vs —
Labelled graphs, with a map, any number of agents
With a map, collision-free exploration of a graph takes \(\Theta(n\Delta^*)\) rounds, where \(\Delta^*\) is the smallest maximum degree of a spanning tree; computing the exact optimum is NP-hard.
tight \(O(n\Delta^*)\) vs \(\Omega(n\Delta^*)\) congestion at a node
tight — vs —
Labelled trees, with a map, any number of agents
Agents that know the tree and their position explore it without collisions in exactly \(n\Delta\) rounds, using a colouring of the edges with \(\Delta\) colours.
tight \(n\Delta\) vs \(n\Delta\) congestion at a node
tight — vs —
Labelled graphs, no knowledge, any number of agents
Without a map or a bound on \(n\), agents on a graph with labelled nodes explore without collisions in \(O(n^5\log n)\) rounds, against \(\Omega(n^2)\).
polynomial gap \(O(n^5\log n)\) vs \(\Omega(n^2)\) congestion at a node
tight — vs —
Labelled trees, no knowledge, any number of agents
Without a map or a bound on \(n\), agents on a tree with labelled nodes explore without collisions in \(O(n^2)\) rounds, which is optimal in the worst case.
tight \(O(n^2)\) vs \(\Omega(n^2)\) congestion at a node
tight — vs —

Open questions 5

Two agents sensing presence, with coloured pebbles

  1. Do two colours suffice on every graph Das et al. 2025a?
  2. How fast can two agents explore with three colours Das et al. 2025a?

Two agents, anonymous graphs, vision of radius 2

  1. Can two agents explore without collisions as fast as one agent explores alone? Asked by Bhagat & Pelc 2025; Papin 2026 claims a constant factor.
  2. For which number of agents below \(n\) is collision-free exploration of anonymous graphs feasible, and with which vision radius Bhagat & Pelc 2025?

Labelled graphs, no knowledge, any number of agents

  1. Close \(O(n^5\log n)\) against \(\Omega(n^2)\) for agents without a map on graphs with labelled nodes.

What the community started looking at

Czyzowicz, Dereniowski, Gąsieniec, Klasing, Kosowski and Pająk asked how long any number of agents need to explore a graph with labelled nodes without ever sharing a node, every agent returning to its start node; with a map the answer is \(n\) times the smallest maximum degree of a spanning tree, up to a constant factor Czyzowicz et al. 2017a. Bhagat and Pelc took the problem to anonymous graphs with two identical agents, where vision of radius 2 is necessary and sufficient Bhagat & Pelc 2025. Das, Dhar, Gorain and Mahawar replaced most of that vision by coloured pebbles placed by an oracle Das et al. 2025a, and Papin claims to remove the logarithmic slowdown of Bhagat and Pelc and to correct their algorithm Papin 2026.

Variant of Graph exploration by a single agent

Every agent explores the graph as in exploration, and no two agents may ever be at the same node. A single-agent exploration procedure is the building block: with vision of radius 2, two agents run any such procedure with a slowdown of at most a factor \(\log n\) Bhagat & Pelc 2025 (a constant factor is claimed by Papin 2026). Lower bounds for exploring by one agent hold here whenever every agent must visit every node.

Related problems

Collaborative exploration: When it suffices that every node is visited by some agent, the task is collaborative exploration with the added rule that agents never share a node Das et al. 2025a.

All settings

The assumption tree (10 settings, 5 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 (Time, Colours); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Node identifiers › Timing › Number of agents › What must be visited › Knowledge of the graph › Vision of the other agents › Help from an oracle › Start › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Number of agents

0any number of agents1two agents

Czyzowicz et al. allow any number of agents, unknown to them Czyzowicz et al. 2017a. Bhagat and Pelc restrict to two agents and ask how to handle larger teams, for which symmetry breaking and synchronisation by observing moves become hard Bhagat & Pelc 2025.

Formal definitions
0any \(k\)
Any number \(k\) of agents, \(2 \le k \le n\), which they do not know.
1two agents
Exactly two agents.

What must be visited

0every agent visits every node1every node is visited by some agent

Czyzowicz et al. and Bhagat and Pelc require every agent to explore Czyzowicz et al. 2017a Bhagat & Pelc 2025; Bhagat and Pelc ask whether it helps that each node is visited by one agent only. Das et al. require only that the team visits every node Das et al. 2025a.

Formal definitions
0every agent
Every agent must visit every node and stop (in Czyzowicz et al. 2017a also return to its start node).
1the team
Every node must be visited by at least one agent, and all agents stop.

Knowledge of the graph

0nothing known1an upper bound on \(n\)2a map with their own position

Czyzowicz et al. compare agents with a map with agents that see only the identifiers of the current node and its neighbours Czyzowicz et al. 2017a. In anonymous graphs an upper bound on \(n\) is necessary: without it no team of agents can explore and stop, whatever their vision Bhagat & Pelc 2025.

Formal definitions
0nothing known
The agents know nothing about \(G\), not even \(n\).
1bound on \(n\)
The agents know an upper bound on \(n\) (Das et al. 2025a give them \(n\) itself).
2map
Every agent knows \(G\) and its own start node in it, but not the number or the start nodes of the other agents.

Vision of the other agents

0none: agents never perceive each other1presence one edge away2radius 13radius 2

With labelled nodes and a map, agents can precompute routes that never meet, so they need not see each other Czyzowicz et al. 2017a. In anonymous graphs, Bhagat and Pelc give vision of radius 2 and prove that radius 1 does not suffice; agents then also communicate by watching each other move Bhagat & Pelc 2025. Das et al. weaken vision to the presence of the other agent one edge away and compensate with pebbles Das et al. 2025a.

Formal definitions
0no vision
An agent never perceives another agent.
1presence
An agent notices that the other agent is on a neighbouring node, but not on which one Das et al. 2025a.
2radius 1
An agent sees the subgraph induced by the nodes at distance at most 1, with its port numbers and the agents on these nodes.
3radius 2
An agent sees the subgraph induced by the nodes at distance at most 2, with its port numbers and the agents on these nodes Bhagat & Pelc 2025.

Help from an oracle

0no help1coloured pebbles placed by an oracle

Das, Dhar, Gorain and Mahawar let an oracle place coloured pebbles, as in advice-based models of mobile agents, and ask for the fewest colours Das et al. 2025a.

Formal definitions
0no help
Nothing is placed on the nodes.
1pebbles
Before the start an oracle that knows \(G\), the start nodes and the wake-up rounds places at most one pebble on each node; pebbles have colours, and an agent sees the pebble of the node it is at Das et al. 2025a.

Start

0the adversary wakes the agents1simultaneous start

Czyzowicz et al. start all agents together Czyzowicz et al. 2017a. Bhagat and Pelc let the adversary wake the agents; on the graph with two nodes this alone makes the task impossible Bhagat & Pelc 2025.

Formal definitions
0adversarial wake-up
Each agent starts in a round chosen by the adversary; until then it stays at its start node, where no other agent may enter.
1simultaneous start
All agents start in the same round.

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