Collision-free exploration

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