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 measuresexpand
\(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.
Anonymous graphs, nothing known
verifiedIn anonymous graphs, agents that know no bound on \(n\) cannot explore and stop, whatever their number and their vision.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Node identifiers: anonymous nodes
- Nodes have no identifiers; an agent at \(v\) sees only \(\deg(v)\) and the port numbers \(1,\dots,\deg(v)\), which are assigned locally and independently at each endpoint of an edge.
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- Number of agents: two agents
- Exactly two agents.
- What must be visited: every agent
- Every agent must visit every node and stop (in Czyzowicz et al. 2017a also return to its start node).
- Knowledge of the graph: nothing known
- The agents know nothing about \(G\), not even \(n\).
- Vision of the other agents: radius 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: no help
- Nothing is placed on the nodes.
- Start: simultaneous start
- All agents start in the same round.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
- a ring whose ports are numbered \(0, 1, 0, 1, \dots\) clockwise, with the agents started together, each one more than the vision radius away from the next: in every round all agents see the same thing and none sees another, so an algorithm that stops after a fixed number of rounds leaves nodes of large enough rings unvisited (Section 4)
- holds for any number of agents and any vision radius
Results, in order of publication
No result recorded yet.
Open questions
None recorded for this variant.
Notes
With labelled nodes the task is solvable without knowing \(n\) Czyzowicz et al. 2017a. Checked against the full text of Bhagat & Pelc 2025 (arXiv v1).
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.