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.
Two agents sensing presence, with coloured pebbles
verifiedWith 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.
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: the team
- Every node must be visited by at least one agent, and all agents stop.
- Knowledge of the graph: bound on \(n\)
- The agents know an upper bound on \(n\) (Das et al. 2025a give them \(n\) itself).
- Vision of the other agents: presence
- An agent notices that the other agent is on a neighbouring node, but not on which one Das et al. 2025a.
- Help from an oracle: pebbles
- 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: adversarial 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.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
Statement for this variant
The agents know \(n\).
What is known
- three graphs, each a 4-cycle with a chord between the two start nodes and differently numbered ports, which the agents cannot tell apart at the start: with pebbles of one colour, every algorithm collides or leaves a node unvisited in one of them (Lemma 2.1 for pebbles on both start nodes or on neither, Theorem 2.1)
Results, in order of publication
Introductory and current best (Theorem 2.2): the pebbles break the symmetry between the start nodes and mark safe routes; the time is exponential in the diameter (Section 2.3).
Open questions
Do two colours suffice on every graph Das et al. 2025a?
How fast can two agents explore with three colours Das et al. 2025a?
Notes
Read in arXiv v1 (2024); theorem numbers refer to it.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
Branches from here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.