# Deterministic Collision-Free Exploration
of Unknown Anonymous Graphs

Subhash Bhagat 111 Department of Mathematics, Indian Institute of Technology
Jodhpur, India<EMAIL_ADDRESS>Andrzej Pelc 222 Département
d’informatique, Université du Québec en Outaouais, Gatineau, Québec, Canada.
<EMAIL_ADDRESS>333 Research supported in part by NSERC Discovery Grant 2018-03899
and by the Research Chair in Distributed Computing of the Université du Québec
en Outaouais.

###### Abstract

We consider the fundamental task of network exploration. A network is modeled
as a simple connected undirected $n$-node graph with unlabeled nodes, and all
ports at any node of degree $d$ are arbitrarily numbered $0,\dots,d-1$. Each
of two identical mobile agents, initially situated at distinct nodes, has to
visit all nodes and stop. Agents execute the same deterministic algorithm and
move in synchronous rounds: in each round an agent can either remain at the
same node or move to an adjacent node. Exploration must be collision-free: in
every round at most one agent can be at any node. We assume that agents have
vision of radius 2: an awake agent situated at a node $v$ can see the subgraph
induced by all nodes at distance at most 2 from $v$, sees all port numbers in
this subgraph and the agents located at these nodes. Agents do not know the
entire graph but they know an upper bound $n$ on its size. The time of an
exploration is the number of rounds since the wakeup of the later agent to the
termination by both agents. We show a collision-free exploration algorithm
working in time polynomial in $n$, for arbitrary graphs of size larger than 2.
Moreover we show that if agents have only vision of radius 1, then collision-
free exploration is impossible, e.g., in any tree of diameter 2.

Keywords: algorithm, graph, exploration, mobile agent, collision

##  1 Introduction

Exploration of networks by visiting all of their nodes is one of the basic
tasks performed by mobile agents in networks. Agents may model humans walking
along streets of a town with the aim of visiting it, software agents
collecting data placed at nodes of a computer network, or mobile robots
collecting samples of air or ground in a contaminated mine whose corridors
form links of a network. We consider exploration by two agents, where each
node must be visited by each of the agents, and both agents have to eventually
stop. We impose the additional requirement that exploration must be collision-
free: in every round at most one agent can be at any node. This requirement,
previously considered in [10, 20], has many applications. If agents are humans
circulating in a pharmacy or a supermarket during a pandemic, some areas (such
as cash registers or prescription counters) may be too small to preserve the
6-feet requirement of social distancing between customers. When mobile
entities model software agents, these entities may need exclusive access to
the part of a distributed data base situated at a node. Finally, mobile robots
distributing chemicals at nodes of a network may need to avoid being at a
small distance from each other.

The network is modeled as a simple connected undirected graph $G=(V,E)$,
called graph in the sequel. Nodes are unlabeled, and all ports at any node of
degree $d$ are arbitrarily numbered $0,\dots,d-1$. This is a standard
assumption in many papers on network exploration [2, 9, 18, 24]. Each of two
identical mobile agents, initially situated at distinct nodes, has to visit
all nodes and stop. Agents execute the same deterministic algorithm and move
in synchronous rounds: in each round, an agent can either remain at the same
node or move to an adjacent node by taking one of the ports. We say that an
agent is located at node $v$ in round $t$, if it is at this node after the
above action in round $t$. When agents cross each other moving simultaneously
along an edge in opposite directions, they do not even notice this fact.
Agents are woken up in possibly different rounds, chosen by an adversary. Each
agent starts the execution of the algorithm in the round following its wakeup.
In every round, at most one agent can be located at any node. For a non-
negative integer $r$, we say that agents have vision of radius $r$, if in each
round $t$, an awake agent located at a node $v$ in round $t-1$ sees the
subgraph $G(v,r)$ induced by all nodes at distance at most $r$ from $v$, sees
all port numbers in this subgraph, and sees the other agent located at any of
these nodes in round $t-1$. We call this information the input of the agent in
round $t$. We assume that agents have vision of radius 2. In each round $t$,
an awake agent located at a node $v$ in round $t-1$, uses the input in round
$t$ to determine its action in round $t$: either moving to an adjacent node
choosing one of the ports at $v$, or staying idle at $v$.

An awake agent can compare its inputs in consecutive rounds and deduce a
crucial piece of information (often used in our algorithm), namely that the
other agent has moved. We will say that agent $a$ already awake in round $t-1$
sees the agent $b$ moving in round $t$, if a node $u$ is in the input of $a$
in rounds $t-1$ and $t$, and one of the following conditions is satisfied:
either $b$ was not at $u$ in round $t-1$ but was at $u$ in round $t$, or $b$
was at $u$ in round $t-1$ but was not at $u$ in round $t$.

Agents have no a priori knowledge of the graph but they know an upper bound
$n$ on its size. Agents are computationally unbounded and cannot mark the
visited nodes. They cannot send any messages. The time of an exploration is
the number of rounds since the wakeup of the later agent to the termination by
both agents.

###  1.1 Our results

Our main result is a collision-free exploration algorithm working in time
polynomial in $n$, for arbitrary graphs of size larger than 2 (in the two-node
graph, collision-free exploration is impossible, see Section 3). We also show
that the assumption of vision of radius 2 cannot be weakened: we prove that
collision-free exploration with vision of radius 1 is impossible in any tree
of diameter 2.

An important building block of our algorithm is a procedure called $EXP(n)$,
that, given any positive integer $n$, allows an agent to visit all nodes of
any graph of size at most $n$, starting from any node of this graph, using
$R(n)$ edge traversals, where $R$ is some polynomial. We show that our
collision-free exploration algorithm works in time $O(R(n)\log n)$, and thus
has only logarithmic slowdown with respect to the time of exploration by a
single agent, without any constraints. It is important to note that, while we
use the well-known Reingold’s [24] result as the base of $EXP(n)$, any
exploration procedure working in arbitrary anonymous graphs of size at most
$n$ would do, and no changes would be necessary. (We could use, for example,
the faster but non-constructive exploration algorithm from [2]). Hence, our
result can be viewed as a generic one: given any exploration procedure for one
agent, working in arbitrary anonymous graphs of size at most $n$, we obtain a
collision-free exploration with only logarithmic slowdown. Of course, if the
collision-free restriction were removed, we could use any of the existing
exploration procedures for anonymous graphs, and each of the agents would
accomplish exploration independently.

Collision-free exploration in anonymous graphs, studied in this paper, should
be compared to the scenario considered in [10], where collision-free
exploration was studied in labeled graphs. As opposed to our assumption that
nodes of the graph are unlabeled, the authors of [10] assumed that all nodes
of the graph have distinct identifiers and that each agent can see the labels
of its current node and of all adjacent nodes. Under this assumption, they
designed a cost-efficient collision-free exploration algorithm in arbitrary
graphs by teams of agents of arbitrary size. It is important to stress the
major difference between the labeled and the anonymous scenario, in the
context of collision-free exploration. While the authors of [10] where able to
precompute collision-free routes of all agents, using distinct labels of
nodes, no such technique is possible in our anonymous case. In fact, the main
difficulty that we face in the anonymous scenario is breaking symmetry between
agents when they are near each other (at distance at most 2), and when there
is the danger of colliding at a common neighbor. The possibility of
precomputing collision-free routes in the labeled scenario avoids this major
difficulty altogether.

###  1.2 Related work

The problem of exploration of an unknown environment by mobile agents has been
extensively studied in the literature for many decades (cf. the survey [23]).
Two types of environments have been considered: either geometric terrains in
the plane, e.g., an unknown terrain with convex obstacles [8], or a room with
polygonal [11] or rectangular [4] obstacles, or as we do in this paper,
networks modeled as graphs, assuming that the agents may only move along the
edges. The graph model can be further specified in two different ways: either
the graph is directed, in which case the agent can move only from tail to head
of a directed edge [1, 5, 6], or the graph is undirected (as we assume) and
the agent can traverse edges in both directions [3, 7, 15, 21]. The efficiency
measure adopted in most papers dealing with exploration of graphs is the cost
of completing this task, measured by the number of edge traversals by the
agent, or by all agents. Some authors impose further restrictions on the moves
of the agent. It is assumed that the agent has either a restricted tank [3,
7], and thus has to periodically return to the base for refueling, or that it
is attached to the base by a rope or a cable of restricted length [15].

An important direction of research concerns exploration of anonymous graphs.
In this case it is impossible to explore arbitrary graphs and stop after
exploration, if no marking of nodes is allowed, and if nothing is known about
the graph. Hence some authors [5, 6] allow pebbles which can be dropped on
nodes to recognize already visited ones, and then removed and dropped on other
nodes. A more restrictive scenario assumes a stationary token that is fixed at
the starting node of the agent [9, 22]. Exploring anonymous graphs without the
possibility of marking nodes (and thus possibly without stopping) is
investigated, e.g., in [13, 17]. The authors concentrate attention not on the
cost of exploration but on the minimum amount of memory sufficient to carry
out this task. In the absence of marking nodes, in order to guarantee stopping
after exploration, some knowledge about the graph is required, e.g., an upper
bound on its size [9, 24]. Graph exploration using the paradigm of algorithms
with advice was investigated in [12, 14, 16, 18]. In this research, the main
issue is to find the minimum amount of information that the agent must have in
order to perform exploration in an efficient way.

##  2 Preliminaries

In our algorithm we will use the following procedure, called $EXP(n)$, based
on universal exploration sequences (UXS) [19], and derived from the result of
Reingold [24]. Given any positive integer $n$, it allows the agent to visit
all nodes of any graph of size at most $n$, starting from any node of this
graph, using $R(n)$ edge traversals, where $R$ is some polynomial. The
sequence of steps of an agent starting at any node of a graph of size at most
$n$ and applying procedure $EXP(n)$ will be called an exploration walk.

A UXS is an infinite sequence $x_{1},x_{2},\dots$ of non-negative integers.
Given this sequence, whose effective construction follows from [19, 24], the
procedure $EXP(n)$ can be described as follows. In step 1, the agent leaves
the starting node by port 0. For $i\geq 1$, the agent that entered the current
node of degree $d$ by some port $p$ in step $i$, computes the port $q$ by
which it has to exit in step $i+1$ as follows: $q=(p+x_{i})\mod d$. The result
of Reingold implies that if an agent starts at any node $v$ of an arbitrary
graph with at most $n$ nodes, and applies procedure $EXP(n)$, then it will
visit all nodes of the graph after $R(n)$ steps.

##  3 The algorithm

We start with the observation that collision-free exploration is impossible in
the two-node graph. Indeed, suppose that there is a collision-free algorithm
for this graph. This algorithm would have to instruct an agent to move $x$
rounds after waking up, for some $x\geq 0$. The adversary can wake up one
agent $x+1$ rounds before the other, thus making it move when the other agent
is still at the other node, creating a collision. It follows that we can
assume from now on that the graph has more than two nodes.

The high-level idea of the algorithm is the following. The agent executes the
exploration walk, using procedure $EXP(n)$, until it sees the other agent at
some point or until it finishes the walk. Due to the lack of node labels, such
exploration walks cannot be precomputed, and getting at distance at most 2
from the other agent, called an approach, cannot be avoided in general. An
approach is potentially dangerous: if agents blindly followed their
exploration walks, they could get to the same common neighbor in the next
round, creating a collision. Even if there is no common neighbor and the
agents are at distance 1 in an approach, following the exploration walk is not
safe either. The other agent could be not yet woken up, so if the exploration
walk prescribes moving to its current location, this could again result in a
collision. The crux of the algorithm is the behavior of the agents during an
approach.

At an approach, both agents execute the procedure Approach resolution whose
aim is to make progress. Progress is defined as at least one agent making the
next step in its exploration walk. The procedure is designed in such a way
that at each approach either both agents make the next step in their
respective exploration walks, or if at the previous approach only agent $A$
made the next step, then at the current approach agent $B$ will make the next
step and agent $A$ will end up at the same node at which it was when this
approach occurred. This guarantees that eventually both agents will execute
their entire exploration walks without collisions.

We now proceed with the description of procedure Approach resolution. The
procedure consists of two subroutines: Synchronization and Progress. The aim
of Synchronization is to bring both agents to the same position they occupied
at the beginning of this subroutine, and to make sure that they are both woken
up and agree on the same round called red. Synchronization is executed only at
the first approach, since at all subsequent approaches both agents remember
that the other agent is awake and, since they see each other in the same
round, they can consider this round to be red. Subroutine Progress begins in
the round following the red round of an approach and its aim is to make
progress, as described above. Upon completion of Progress, both agents may
stop seeing each other, in which case they continue executing their respective
exploration walks until the next approach, or they can still see each other in
which case this is considered a new approach, and they proceed to the next
execution of Progress, as Synchronization is not needed anymore.

Subroutine Synchronization
We now give a detailed description of subroutine Synchronization. It starts in
the round when at least one of the agents sees the other for the first time.
Let $X$ be the set consisting of the two agents. Consider an agent $a\in X$.
We denote by $\hat{a}$ the other agent in $X$. Let agents $a$ and $\hat{a}$ be
located at nodes $u$ and $v$ respectively at the beginning of the first
approach. We refer to $u$ and $v$ as the initial synch nodes of $a$ and
$\hat{a}$ respectively. Let $B$ be the set of common neighbors of $u$ and $v$.
Let $D=V\backslash(B\cup\\{u,v\\})$. Let $A_{u}$ and $A_{v}$ be the subsets of
nodes in $D$ which are adjacent to $u$ and to $v$ respectively. We call these
nodes the private neighbors of $u$ and of $v$ respectively. The back and forth
movement of an agent between two fixed nodes is referred to as the oscillating
movement.  During the execution of our algorithm, an agent performs three
types of waits, namely, the initial wait, the compulsory wait, and the
terminal wait. The initial wait and the compulsory wait are performed by an
agent before it makes its first move after waking up. Whenever an agent wakes
up, it waits for one round. This waiting is referred to as the initial wait of
the agent. The initial wait is essential to avoid collisions. The compulsory
wait depends on the situation. There are two reasons for the compulsory wait:
either the agent waits to see the other agent moving for the first time or it
waits for the other agent to move to a particular node. This type of wait is
also essential to avoid collisions. Finally, the terminal wait is defined as
follows: an agent $a\in X$ waits in round $t+1$ if in round $t$ agent $a$ was
moving and finds the other agent $\hat{a}$ moving for the first time, and in
round $t$, agent $a$ is at its initial synch node. This wait is referred to as
the terminal wait of agent $a$. The terminal wait is for the confirmation that
both agents are at their respective initial synch nodes at the start of the
red round. During the synchronization, the round when for the first time both
agents move simultaneously is referred as the event round.

Synchronization starts in the round when at least one of the agents sees the
other agent for the first time. Call this round $\hat{t}$. Then there are the
following two possibilities,

  * •

Case A: Both agents see each other moving in round $\hat{t}$ (figure 1).

  * •

Case B: At least one of the agents does not see the other agent moving in
round $\hat{t}$.

Now we describe the strategies followed by the agents in both of the above
cases separately.

Case A: In this case, round $\hat{t}$ is the event round. Both agents do not
move in round $\hat{t}+1$ and consider round $\hat{t}+2$ as the red round. We
make agents wait in round $\hat{t}+1$ just for convenience to prove the
correctness of our algorithm.

Figure 1: An illustration for the Case A: In round $\hat{t}-1$, agents $a$ and
$\hat{a}$ were at nodes $u_{1}$ and $v_{1}$ respectively. During the round
$\hat{t}$, both agents $a$ and $\hat{a}$ move concurrently to the nodes
$u_{2}$ and $v_{2}$ respectively.

Case B: In this case at least one of the agents wakes up in some round
$t\geq\hat{t}$. Suppose that agent $a\in X$ wakes up in round $t$. It makes
its initial wait in round $t+1$. Now there are two possibilities: in round
$t+1$, the other agent $\hat{a}$ either moves or does not move. The actions of
agent $a$ in round $t+2$ and onward depend on this and are as follows:

  * •

Case B1. Agent $\hat{a}$ does not move in round $t+1$: In this case, agent $a$
infers that the initial synch node of agent $\hat{a}$ is the node $v$ at which
$\hat{a}$ stays in round $t+1$. The actions of agent $a$ depend on the sub-
graph induced by nodes adjacent to $u$ and to $v$.

    * –

Subcase 1. Nodes $u$ and $v$ do not have any common neighbor: In this case,
$u$ and $v$ are adjacent.

      * *

Subcase 1.1. $u$ is not a leaf node: Agent $a$ selects the private neighbor
$n_{u}\in A_{u}$ which corresponds to the lowest port number at node $u$ and
starts the oscillating movement between its initial synch node $u$ and the
selected private neighbor $n_{u}$ (figure 2(A)). It keeps oscillating until it
sees the other agent moving for the first time. When $a$ sees $\hat{a}$ moving
for the first time, it stops its oscillating movement. Let $t^{*}$ be the
round when agent $a$ sees agent $\hat{a}$ moving for the first time (the event
round). If agent $a$ is at its initial synch node $u$ in round $t^{*}$, then
it does not move in round $t^{*}+1$ (the terminal wait for agent $a$).
Otherwise, agent $a$ moves back to its initial synch node $u$ in round
$t^{*}+1$. Agent $a$ decides on the round $t^{*}+2$ as the red round. The
terminal wait of agent $a$ helps the agent $\hat{a}$ to confirm the initial
synch node of $a$. This also ensures that agent $\hat{a}$ gets back to its
initial synch node before the start of the red round.

Figure 2: An illustration for: (A) Subcase 1.1 when node $u$ is not a leaf
node (B) Subcase 1.2 when node $u$ is a leaf node

      * *

Subcase 1.2. $u$ is a leaf node: The node $u$ does not have any private
neighbor in this case but $v$ does (as there are more than two nodes in the
graph). The only node where agent $a$ can move from node $u$ is $v$ (figure
2(B)). Upon wake-up, agent $a$ waits until it sees the other agent moving (a
compulsory wait). Let $t^{*}$ be the round when agent $a$ sees agent $\hat{a}$
moving for the first time. Agent $\hat{a}$ moves from its initial synch node
$v$ to one of its private neighbors $n_{v}$. In round $t^{*}$, agent $\hat{a}$
is at node $n_{v}$. In round $t^{*}+1$, agent $a$ does not move (it is a
compulsory wait to avoid collision with agent $\hat{a}$). In round $t^{*}+1$,
agent $a$ finds agent $\hat{a}$ at node $v$. In round $t^{*}+2$ (the event
round), agent $a$ moves to node $v$ (while $\hat{a}$ moves to $n_{v}$) and in
round $t^{*}+3$, $a$ moves back to its initial synch node $u$ (while $\hat{a}$
moves back to $v$). Agent $a$ decides on round $t^{*}+4$ as the red round.

    * –

Subcase 2. Nodes $u$ and $v$ have at least one common neighbor: We define two
subsets of nodes $B_{u},B_{v}\subset B$ in the following way: a node $w\in B$
is in $B_{u}$ if the port number at $w$ corresponding to the edge $\\{w,u\\}$
is larger than the port number at $w$ corresponding to the edge $\\{w,v\\}$
(figure 3). The set $B_{v}$ is defined analogously.

      * *

Subcase 2.1. $B_{u}$ is not empty: In this case, agent $a$ moves in round
$t+2$. Agent $a$ chooses the node $n_{u}\in B_{u}$ corresponding to the lowest
port number at $u$, and starts its oscillating movement between nodes $u$ and
the selected neighbor $n_{u}$. It continues its movement until it sees the
other agent moving. Suppose $t^{*}$ is the round when agent $a$ sees $\hat{a}$
moving for the first time. If in round $t^{*}$, agent $a$ is not at $u$ (its
initial synch node), it moves back to $u$ in round $t^{*}+1$. Otherwise, it
waits in round $t^{*}+1$ (the terminal wait). Agent $a$ decides on $t^{*}+2$
as the red round.

Figure 3: An illustration for Subcase 2 when nodes $u$ and $v$ have at least
one common neighbor

      * *

Subcase 2.2. $B_{u}$ is empty: In this case, agent $a$ waits until it sees
agent $\hat{a}$ moving. Let $t^{*}$ be the round when agent $a$ sees agent
$\hat{a}$ moving for the first time. In round $t^{*}$, agent $\hat{a}$ is at
node $n_{v}$. In round $t^{*}+1$ (the event round), agent $a$ moves to $n_{v}$
(while $\hat{a}$ moves back to $v$). In round $t^{*}+2$, agent $a$ moves back
to node $u$ (while $\hat{a}$ waits at $v$). Agent $a$ decides on round
$t^{*}+3$ as the red round.

Figure 4: An illustration for Case B2 when agent $\hat{a}$ moves in round
$t+1$: (A) when both nodes $x$ and $y$ are adjacent to node $u$ (B) when
exactly one of nodes $x$ and $y$ is adjacent to the node $u$.

  * •

Case B2. Agent $\hat{a}$ moves in round $t+1$: In this case, agent $a$ is not
sure which is the initial synch node of agent $\hat{a}$. Suppose that agent
$\hat{a}$ moves from node $x$ to $y$ in round $t+1$. One of $x$ and $y$ is the
initial synch node of agent $\hat{a}$. At least one of $x$ and $y$ is adjacent
to node $u$. First consider the case, when both nodes $x$ and $y$ are adjacent
to $u$ (figure 4 (A)). In round $t+2$ (the event round), agent $a$ moves to
node $y$ (while $\hat{a}$ moves back to $x$). In round $t+3$, agent $a$ moves
back to its initial synch node $u$. Agent $a$ decides on round $t+4$ as the
red round.

Next consider the case, when exactly one of nodes $x$ and $y$ is adjacent to
$u$ (figure 4 (B)). If $x$ is not adjacent to $u$ (but $y$ is adjacent to
$u$), agent $a$ moves to node $y$ in round $t+2$ (the event round) and moves
back to node $u$ in round $t+3$. In this case, agent $a$ decides on round
$t+4$ as the red round. If $x$ is adjacent to $u$ (but $y$ is not adjacent to
$u$), agent $a$ does not move in round $t+2$ (a compulsory wait), while
$\hat{a}$ moves back to $x$. In round $t+3$ (the event round), agent $a$ moves
to node $x$ (while $\hat{a}$ moves to $y$) and in round $t+4$, $a$ moves back
to node $u$. Agent $a$ decides on round $t+5$, as the red round.

###### Lemma 3.1

Upon completion of subroutine Synchronization both agents establish the same
round as red, in this round they know that they are awake and they are at the
positions they occupied at the start of the subroutine.

Proof. We show that in all possible scenarios, agents agree on round event
round+2 as the red round. Suppose that at least one of the agents sees the
other agent for the first time in round $\hat{t}$. We prove the lemma by
considering different scenarios separately.

Case A: Both agents see each other moving in round $\hat{t}$.
In this case, round $\hat{t}$ is the event round. Agents do not move in round
$\hat{t}+1$ and decide on round $\hat{t}+2$ as the red round. Since they do
not move in round $\hat{t}+1$, they remain at the same nodes that they occupy
at the start of the subroutine. Hence, the lemma is true in this case.

Case B: At least one of the agents does not see the other agent moving in
round $\hat{t}$.
In this case, at least one of the agents wakes up in round $t\geq\hat{t}$. We
have the following sub-cases in this case:

  * •

Case 1: Both agents wake up in the same round. Suppose that both agents wake
up in the same round $t$. The round $t+1$ is the initial wait round for both
agents. Since none of them moves in round $t+1$, in this round both agents
know the initial synch node of each other. This satisfies condition (iii)
above. In round $t+2$, at least one of them moves.

    * –

Case 1.1: Nodes $u$ and $v$ do not have any common neighbor. We consider two
sub-cases.

      * *

Case 1.1.1: None of $u$ and $v$ is a leaf node. In this case, both agents are
allowed to move simultaneously and they perform oscillating movements to their
respective private neighbors. Since $A_{u}\cap A_{v}=\emptyset$, during their
movements, agents do not collide with each other. In round $t+2$, for the
first time, agents see each other moving. Thus, in this case, round $t+2$ is
the event round. In round $t+2$, agent $a$ is at node $n_{u}\in A_{u}$ and
agent $\hat{a}$ is at a node $n_{v}\in A_{v}$. Since none of the agents moved
in round $t+1$, each of them knows that this is the first move of the other
agent in this subroutine, and in round $t+2$ none of them is at its initial
synch node. In round $t+3$, both of them move back to their respective initial
synch nodes. In round $t+3$, each of the agents knows that the other agent is
active and is back at its initial synch node. They both agree on round $t+4$
(event round+2) as the red round.

      * *

Case 1.1.2: One of $u$ and $v$ is a leaf node. Without loss of generality,
suppose that $v$ is a leaf node. Agent $a$ chooses a neighbor $n_{u}\in A_{u}$
and starts its oscillating movement in round $t+2$. Since $v$ is a leaf, the
only node where agent $\hat{a}$ can move, is node $u$. In round $t+1$, agent
$\hat{a}$ does not know whether agent $a$ is active or not. Thus, agent
$\hat{a}$ does not move in round $t+2$ (a compulsory wait). In round $t+2$,
agent $a$ moves for the first time and it moves to node $n_{u}$. In round
$t+2$, agent $\hat{a}$ knows that agent $a$ is active. In round $t+3$, agent
$a$ moves back to node $u$ and agent $a$ does not move in this round to avoid
collision with agent $a$ (a compulsory wait). In round $t+3$, agent $a$ is at
$u$ and agent $\hat{a}$ knows that in the next round agent $a$ will be moving
out of this node. In round $t+4$, agent $\hat{a}$ moves to node $u$ while
agent $a$ moves to node $n_{u}$. This is first time agent $a$ sees agent
$\hat{a}$ moving. Thus, $t+4$ is the event round. In round $t+5$, both agents
move back to their respective initial synch nodes. In round $t+5$, each of the
agents knows that the other agent is active and is at its initial synch node.
They agree on round $t+6$ (event round+2) as the red round.

    * –

Case 1.2: Nodes $u$ and $v$ have at least one common neighbor. There are two
sub-cases.

      * *

Case 1.2.1. None of $B_{u}$ and $B_{v}$ is empty. After the initial wait both
agents move in this case. They do oscillating movements to nodes $n_{u}\in
B_{u}$ and $n_{v}\in B_{v}$ respectively. Since $B_{u}\cap B_{v}=\emptyset$,
the agents do not collide with each other during their movements. In round
$t+2$, both agents move and see each other moving for the first time (the
event round). In round $t+2$, each of the agents knows that the other agent is
active and is currently not at its initial synch node. In round $t+3$, both
the agents move back to their respective initial synch nodes. In round $t+3$,
both agents know that the other is active and that it is at its initial synch
node. The agents agree on the round $t+4$ (event round+2) as the red round.

      * *

Case 1.2.2. One of $B_{u}$ and $B_{v}$ is empty. Without loss of generality,
suppose $B_{v}=\emptyset$. In round $t+2$, agent $a$ moves to node $n_{u}\in
B_{u}$. This is the first time agent $\hat{a}$ sees agent $a$ moving. Agent
$\hat{a}$ does not moves in this round (a compulsory wait). In round $t+2$,
agent $a$ is at $n_{u}$ and has not seen agent $\hat{a}$ moving. In round
$t+3$, agent $a$ moves back to node $u$ and agent $\hat{a}$ moves to node
$n_{u}$. This is the first time both agents move simultaneously. Thus, $t+3$
is the event round. Since agent $a$ has seen agent $\hat{a}$ moving for the
first time and it is at its initial synch node in round $t+3$, gent $a$ does
not move in round $t+4$ (the terminal wait for agent $a$). In round $t+4$,
agent $\hat{a}$ moves back to node $v$. In round $t+4$, each of the agents
knows that the other agent is active and is currently at its initial synch
node. They agree on the round $t+5$ (event round+2) as the red round.

  * •

Case 2: Agents wake up in different rounds. Without loss of generality,
suppose that agent $\hat{a}$ wakes up later and wakes up in round $t$. It
waits in round $t+1$. In round $t+1$, agent $a$ is either moving or waiting
for agent $\hat{a}$ to move first. In this case, agent $a$ knows the initial
synch node of $\hat{a}$. However, there are cases in which agent $\hat{a}$
does not know yet the initial synch node of $a$.

    * –

Case 2.1: Nodes $u$ and $v$ do not have any common neighbor.

      * *

Case 2.1.1: None of $u$ and $v$ is a leaf node. In this case, agent $\hat{a}$
sees agent $a$ moving between nodes $u$ and $n_{u}$, in round $t+1$. In round
$t+1$, agent $a$ is either at $u$ or at $n_{u}$. Agent $\hat{a}$ does not know
the initial synch node of agent $a$. Node $n_{u}$ is not adjacent to node $v$.
Agent $a$ knows the initial synch node of agent $\hat{a}$.

First suppose that agent $a$ is at node $u$ in round $t+1$. Agent $\hat{a}$
moves to node $u$ in round $t+2$ while agent $a$ moves to node $n_{u}$ in this
round. This is the first time agents see each other moving, i.e., round $t+2$
is the event round. In round $t+2$ agent $a$ is at $n_{u}$ which is not the
initial synch node of $a$. Thus, in round $t+3$, agent $a$ moves back to $u$
while agent $\hat{a}$ moves back to $v$. In round $t+3$, agents $a$ and
$\hat{a}$ are at their respective initial synch nodes and agent $\hat{a}$
knows the initial synch node of $a$ in view of the move of agent $a$ in round
$t+3$. (Agent $a$ moves even after seeing agent $\hat{a}$ moving in round
$t+2$). They agree on round $t+4$ (event round+2) as the red round.

Next suppose that agent $a$ is at node $n_{u}$ in round $t+1$. In round $t+2$
agent $a$ moves to node $u$ and agent $\hat{a}$ does not move in this round (a
compulsory wait to avoid collision). In round $t+2$, agent $a$ is at $u$ and
has not seen agent $\hat{a}$ moving yet. In round $t+3$, agent $a$ moves to
node $n_{u}$ and agent $\hat{a}$ moves to node $u$. This is the first time
both agents see each other moving, i.e., round $t+3$ is the event round. In
round $t+3$, both agents are not at their respective initial synch nodes.
Thus, in round $t+4$, agents $a$ and $\hat{a}$ move back to nodes $u$ and $v$
respectively. In round $t+4$, each of the agents knows that the other agent is
active and that it is currently at its initial synch node. They agree on round
$t+5$ (event round+2) as the red round.

      * *

Case 2.1.2: One of $u$ and $v$ is a leaf node. First consider the case when
$u$ is a leaf node. In this case, each of the agents is aware of the initial
synch node of the other. Agent $a$ does not move in round $t+1$ (a compulsory
wait). In round $t+2$, agent $\hat{a}$ moves to node $n_{v}\in A_{v}$. Nodes
$u$ and $n_{v}$ are not adjacent. In round $t+2$, agent $\hat{a}$ is at node
$n_{v}$ and has not seen agent $a$ moving yet. Thus, in round $t+3$, agent
$\hat{a}$ moves back to node $v$. In round $t+4$, agent $\hat{a}$ moves to
node $n_{v}$ and agent $a$ moves to node $v$. This is the first time when
agents see each other moving. Thus, round $t+4$ is the event round. In round
$t+4$ none of the agents is at its initial synch node. Thus, in round $t+5$
agents $\hat{a}$ and $a$ move back to nodes $v$ and $u$ respectively. In round
$t+5$, each of the agents is at its initial synch node and knows that other
agent is active. They agree on round $t+6$ (event round+2) as the red round.

Now consider the case when $v$ is a leaf node. In this case, agent $\hat{a}$
finds $a$ moving in round $t+1$ between nodes $u$ and $n_{u}\in A_{u}$ and the
only node where agent $\hat{a}$ can move is node $u$. In round $t+1$, agent
$a$ is either at $u$ or at $n_{u}$. The rest of the argument is the same as in
Case 2.1.1,

    * –

Case 2.2: Nodes $u$ and $v$ have common neighbors.

      * *

Case 2.2.1: None of $B_{u}$ and $B_{v}$ is empty. In round $t+1$, agent $a$
moves, and in this round, it is either at $u$ or at $x\in B_{u}$. Agent $a$
knows the initial synch node of $\hat{a}$. However, agent $\hat{a}$ does not
know the initial synch node of $a$. Note that nodes $v$ and $x$ are adjacent.
However, nodes $u$ and $v$ may not be adjacent.

First consider the case when nodes $u$ and $v$ are adjacent. If agent $a$ is
at node $u$ in round $t+1$, in round $t+2$ agent $\hat{a}$ moves to node $u$
while agent $a$ moves to node $x$. This is the first time when agents see each
other moving simultaneously in the same round i.e., round $t+2$ is the event
round. In round $t+2$, agent $a$ has seen agent $\hat{a}$ moving for the first
time, however agent $a$ is not at its initial synch node. Thus, in round
$t+3$, agents $a$ and $\hat{a}$ move back to nodes $u$ and $v$ respectively.
During these movements agents do not collide. In round $t+3$, agent $\hat{a}$
knows the initial synch node of $a$ (since agent $a$ has moved even after
watching agent $\hat{a}$ moving in the previous round), each of the agents
knows that the other agent is active and it is at its initial synch node. They
agree on round $t+4$ (event round+2) as the red round.

Now consider the case, when nodes $u$ and $v$ are not adjacent. If agent $a$
is at node $x$ in round $t+1$, agent $\hat{a}$ moves to node $x$ in round
$t+2$ while agent $a$ moves to node $u$ at the same time. This is the first
time when agents see each other moving, i.e., round $t+2$ is the event round.
In round $t+2$, agent $a$ is at its initial synch node and it has just seen
agent $\hat{a}$ moving for the first time. Thus, in round $t+3$, agent $a$
does not move (the terminal wait) while agent $\hat{a}$ moves back to node
$v$. In round $t+3$, agent $\hat{a}$ knows the initial synch node of agent $a$
(since agent $a$ has not moved in round $t+3$ after watching agent $\hat{a}$
moving for the first time in the previous round). During these movements
agents do not collide. Thus, in round $t+3$, both agents know that each of
them is active and they are at their respective initial synch nodes. They
agree on round $t+4$ (event round+2) as the red round.

If agent $a$ is at node $u$ in round $t+1$, agent $a$ has not seen agent
$\hat{a}$ moving yet. Thus, in round $t+2$, agent $a$ moves from node $u$ to
node $x$. Agent $\hat{a}$ does not move in this round to avoid collision. In
round $t+2$, agent $a$ has not seen agent $\hat{a}$ moving. Thus, in round
$t+3$, agents $a$ moves to node $u$ while agent $\hat{a}$ moves to node $x$ at
the same time. This is the first time when both agents see each other moving,
i.e., round $t+3$ is the event round. In round $t+3$, agent $a$ is at node $u$
which is its initial synch node and it has seen agent $\hat{a}$ moving for the
first time. Thus, in round $t+4$, agent $a$ does not move (the terminal wait
for $a$) while agent $\hat{a}$ moves back to node $v$. In round $t+4$, each of
the agents knows that the other agent is active and it is at its initial synch
node (since in round $t+4$ agent $a$ does not move after watching agent
$\hat{a}$ moving for the first time in round $t+3$, agent $\hat{a}$ knows the
initial synch node of agent $a$ in round $t+4$). They agree on round $t+5$
(event round+2) as the red round.

      * *

Case 2.2.2: One of $B_{u}$ and $B_{v}$ is empty. First consider the case when
$B_{u}=\emptyset$. In this case, agent $a$ does not move in round $t+1$. Both
agents know the initial synch node of each other. In round $t+2$, agent
$\hat{a}$ moves from $v$ to node $y\in B_{v}$. Note that nodes $u$ and $y$ are
adjacent. This is the first time agent $a$ sees agent $\hat{a}$ moving and
agent $a$ is at its initial synch node. However, agent $a$ has not moved yet
and thus round $t+3$ is not a terminal wait round for $a$. In round $t+3$,
agent $\hat{a}$ moves to node $v$ while agent $a$ moves to node $y$. This is
the first time when agents see each other moving simultaneously i.e., round
$t+3$ is the event round. In round $t+3$, agent $\hat{a}$ is at its initial
synch node and it has seen agent $a$ moving for the first time. Thus, in round
$t+4$, agent $\hat{a}$ does not move (the terminal wait for $\hat{a}$) while
agent $a$ moves back to its initial synch node $u$. In round $t+4$, each of
the agents knows that other agent is active and currently is at its initial
synch node. They agree on round $t+5$ (event round+2) as the red round.

Now consider the case when $B_{v}=\emptyset$. In this case agent $\hat{a}$
sees agent $a$ moving in round $t+1$. Agent $a$ knows the initial synch node
of agent $\hat{a}$. However, agent $\hat{a}$ does not know yet the initial
synch node of agent $a$. In round $t+1$, agent $a$ is either at $u$ or at a
node $x\in B_{u}$. Nodes $v$ and $x$ are adjacent. There are two
possibilities: either nodes $u$ and $v$ are adjacent or not.

First consider the case when nodes $u$ and $v$ are adjacent. If agent $a$ is
at node $u$ in round $t+1$, in round $t+2$ agent $a$ moves to node $x$ while
agent $\hat{a}$ moves to node $u$ in the same round. This is the first time
when agents see each other moving. Thus, round $t+2$ is the event round. In
round $t+2$, agent $a$ is at node $x$ and agent $\hat{a}$ is at node $u$.
Thus, in round $t+3$ agents $a$ and $\hat{a}$ move back to nodes $u$ and $v$,
respectively. In round $t+3$, each of the agents knows that the other agent is
active and it is at its initial synch node. They decide on round $t+4$ (event
round+2) as the red round. Next suppose that agent $a$ is at node $x$ in round
$t+1$. Since it has not seen agent $\hat{a}$ moving in round $t+1$ (agent
$\hat{a}$ does its initial wait in round $t+1$), agent $a$ moves to node $u$
in round $t+2$. In this round, agent $\hat{a}$ moves to node $x$. This is the
first time agents see each other moving, i.e., round $t+2$ is the event round.
In round $t+2$, agent $a$ is at its initial synch node and has seen agent
$\hat{a}$ moving for the first time. Thus in round $t+3$, agent $a$ does not
move (the terminal wait for $a$) while agent $\hat{a}$ moves back to node $v$
in the same round. In round $t+3$, each of the agents knows that the other
agent is active and currently is at its initial synch node. They agree on
round $t+4$ (event round+2) as the red round.

Finally consider the case when nodes $u$ and $v$ are not adjacent. In round
$t+1$, agent $a$ moves and agent $\hat{a}$ does not move due to its initial
wait. If agent $a$ is at node $x$ in round $t+1$, then in round $t+2$, agent
$a$ moves to node $u$ and agent $\hat{a}$ moves to node $x$. This is the first
time when agents see each other moving. Thus, round $t+2$ is the event round.
In round $t+2$, agent $a$ is at its initial synch node and has seen the other
agent moving for the first time. Thus, in round $t+3$ agent $a$ does not move
(the terminal wait for $a$) while agent $\hat{a}$ moves back to node $v$. In
round $t+3$, agent $\hat{a}$ is knows the initial synch node of $a$ and both
the agents are at their respective initial synch nodes. They agree on round
$t+4$ as the red round. Now, if agent $a$ is at node $u$ in round $t+1$ then,
in round $t+2$, agent $a$ moves to node $x$ while agent $\hat{a}$ does not
move in this round (compulsory wait to avoid collision). In round $t+3$,
agents $a$ and $\hat{a}$ move to nodes $u$ and $x$ respectively. This is the
first time when agents see each other moving i.e., round $t+3$ is the event
round. Since in round $t+3$, agent $a$ is at its initial synch node and it has
seen agent $\hat{a}$ moving for the first time, agent $a$ does not move in
round $t+4$ (the terminal wait for agent $a$). Agent $\hat{a}$ moves back to
node $v$ in this round. In round $t+4$, each of the agents knows the initial
synch node of the other agent and both of them are at their respective initial
synch nodes. They agree on round $t+5$ (event round+2) as the red round.

$\Box$

We now give a detailed description of subroutine Progress. The subroutine
starts in the round following the red round. The two agents are at distance at
most 2, at nodes $u$ and $v$, which are the nodes at which the current
approach started. We consider the subgraph induced by the nodes $u$, $v$ and
all their common neighbors. We call it the approach graph and we say that it
is symmetric if there exists a port preserving automorphism of this graph
interchanging $u$ and $v$. If this is not the case, it is possible to elect a
leader among the agents, based only on the approach graph. It can be done as
follows. Let $L(u)$ (resp. $L(v)$) be the lexicographically ordered list of
all edges of the approach graph incident to $u$ (resp. $v$), coded as ordered
pairs of port numbers with the port number at $u$ (resp. $v$) first. Since the
approach graph is not symmetric, these lists are not identical. Consider the
first index $i$ at which they differ. The leader is the agent for which the
$i$th edge is lexicographically smaller than the $i$th edge for the other
agent. There are four possible cases.

Case 1. Nodes $u$ and $v$ do not have a common neighbor.

Each of the agents executes the next step of their respective exploration
walks. Since they do not have a common neighbor, this does not result in a
collision.

Case 2. Nodes $u$ and $v$ have a common neighbor, are not adjacent and the
approach graph is not symmetric.

If a leader was elected at some previous approach then the other agent is
elected as leader in the current approach. Otherwise, agents elect a leader as
specified above. The leader executes the next step of its exploration walk and
the other agent stays idle for a round. Since nodes $u$ and $v$ are not
adjacent, there is no collision.

Case 3. Nodes $u$ and $v$ have a common neighbor, are adjacent and the
approach graph is not symmetric.

If a leader was elected at some previous approach then the other agent is
elected as leader in the current approach. Otherwise, agents elect a leader as
specified above. If the next step of the exploration walk of the leader is not
along the edge joining $u$ and $v$ then the leader executes this next step and
the other agent stays idle for a round. Otherwise the leader stays idle for a
round. In the next round both agents execute the next step of their respective
exploration walks. In both cases there is no collision.

Case 4. Nodes $u$ and $v$ have a common neighbor and the approach graph is
symmetric.

This case is the most delicate: agents cannot simply execute the next step of
their respective exploration walks because they risk colliding at a common
neighbor and they cannot elect a leader based only on the approach graph
because this graph is symmetric. If a leader was elected at some previous
approach then the other agent is elected as leader in the current approach.
Otherwise, agents need to mutually communicate where each of them wants to go
next. Let $d$ be the degree of nodes $u$ and $v$ in the original graph and let
$k=\lceil\log d\rceil+1$. Let $s_{u}$ (resp. $s_{v}$) be the binary string of
length $k$ that is the binary representation of the port number (padded by
zeroes in front, if necessary) that the agent at $u$ (resp. at $v$) should
take to make the next step of its exploration walk. Each agent communicates
this number by walking back and forth on the edge leading to a common neighbor
and corresponding to the smallest port number. More precisely, let
$x\in\\{u,v\\}$ and let $w_{x}$ be the common neighbor of $u$ and $v$
corresponding to this edge for $x$. Due to symmetry, we have $w_{u}\neq
w_{v}$. In the next $2k$ rounds
$r_{1},r^{\prime}_{1},\dots,r_{k},r^{\prime}_{k}$, the agent originally
located at $x$ behaves as follows. If the $i$th bit of $s_{x}$ is 1 then the
agent goes from $x$ to $w_{x}$ in round $r_{i}$ and from $w_{x}$ to $x$ in
round $r^{\prime}_{i}$. If the $i$th bit of $s_{x}$ is 0 then the agent stays
idle at $x$ in rounds $r_{i}$ and $r^{\prime}_{i}$. Since the diameter of the
approach graph is at most 2, each agent sees the moves of the other agent.
After round $r^{\prime}_{k}$, both agents learn $s_{u}$ and $s_{v}$ and behave
as follows in the next round. If $s_{u}=s_{v}$ then both agents execute the
next step of their respective exploration walks. Since, by symmetry of the
approach graph this is done either on the same edge or on non-incident edges,
no collision occurs. If $s_{u}\neq s_{v}$ then symmetry can be broken: the
leader is the agent for which $s_{x}$ is smaller. In this case agents behave
as in Case 3 or as in Case 2, depending on whether $u$ and $v$ are adjacent or
not.

We are now ready to describe our main Algorithm Explo-without-Collisions. Each
agent executes its exploration walk interrupting it when an approach occurs.
At every approach agents execute procedure Approach resolution and then
continue their respective exploration walks until the next approach. After
performing $R(n)$ steps of its exploration walk, an agent stops at some node
$v$, possibly only temporarily. At this time the agent has already visited all
nodes of the graph. This will be called provisional stop. Let $w$ be the
neighbor of $v$ corresponding to the port 0 at $v$ and let $p$ be the port
number at $w$ corresponding to the neighbor $v$. If another approach occurs
after the provisional stop of an agent (due to the fact that the other agent
has not yet completed its exploration walk) the agent resumes Algorithm Explo-
without-Collisions, as if the next two port numbers in its exploration walk
were 0 and $p$, i.e., it executes procedure Approach resolution and then tries
to make the next two steps from $v$ to $w$ and back. There is one exception to
this rule. Let $\Sigma=R(n)(4\lceil\log n\rceil+8)$. Consider any agent and
let $\sigma$ be the round of its provisional stop. If no approach occurred
between round $\sigma$ and $\sigma+\Sigma$ then we define
$\rho=\sigma+\Sigma$. Otherwise we define $\rho=\sigma+2\Sigma$. The agent
knows that no approach will ever occur after round $\rho$ (see the proof of
Theorem 3.1). It terminates in round $\rho$ and stays idle forever.

###### Theorem 3.1

Upon execution of Algorithm Explo-without-Collisions both agents have visited
all nodes of the graph, were never at the same node in the same round and
remain idle forever. The running time of Algorithm Explo-without-Collisions is
$O(R(n)\log n)$.

Proof. Subroutine Synchronization is executed once, at the first approach, and
takes constantly many rounds. Each execution of subroutine Progress takes at
most $2\lceil\log n\rceil+4$ rounds, as the degree of any node is at most $n$.
Hence each agent makes a step of its exploration walk at most every
$4\lceil\log n\rceil+8$ rounds. It follows that $\Sigma$ rounds after the
beginning of the first execution of subroutine Progress both agents have
visited all nodes and hence can terminate. On the other hand, if no approach
happens by the round $\sigma_{A}+\Sigma$, where $\sigma_{A}$ is the round of
the provisional stop of agent $A$ then this agent knows that the other agent
$B$ has already visited all nodes of the graph and provisionally stopped. This
is because agent $B$ must have woken up before the provisional stop of $A$
(otherwise there would be an approach) and hence the provisional stop of $B$
must have occurred before round $\sigma_{A}+\Sigma$. To summarize, agent $A$
can safely terminate in round $\rho$ in all cases.

The design of procedure Approach resolution is such that agents are never at
the same node in the same round. In rounds outside of approaches, agents are
at distance at least 3, hence there can be no collision in the next round.

It remains to estimate the running time of Algorithm Explo-without-Collisions.
Consider the wakeup round of the later agent as round 0 and consider any
agent. Since its provisional stop occurs in round at most $\Sigma+O(1)$, the
termination round is at most $3\Sigma+O(1)$. In view of the definition of
$\Sigma$ this concludes the proof. $\Box$

##  4 Discussion

In this section we discuss the two main assumptions of our model and show that
none of them can be removed. The first assumption is that agents know an upper
bound on the size of the graph, and the second is that agents have vision of
radius 2. In order to show the necessity of the first assumption observe that,
in the absence of any upper bound on the size of the graph, known to the
agents, it is impossible to perform exploration with stop by any team of
agents starting simultaneously in some ring in which all ports are numbered
0,1,0,1,… clockwise, regardless of the radius of vision. Indeed, consider a
team of $k$ agents with vision of radius $r$, starting simultaneously at
distances $r+1$ in rings of size larger than $k(r+1)$. For any algorithm that
stops after $j$ rounds, no agent can see any other agent, and the subgraph
seen by all agents in all rounds is the same. For any such algorithm, no agent
will visit all nodes if the size of the ring is larger than $j+1$.

As for the second assumption, we show that it cannot be weakened. Indeed,
suppose that agents have vision of radius 1, and consider 2 agents trying to
explore any tree of diameter 2, i.e., any star. Port numbers at the central
node $v$ are $0,1,\dots,d-1$, and port numbers at all leaves are 0. Call the
leaf corresponding to port $i$ at the central node, the $i$th leaf. If the
agent starts at the $i$th leaf, it sees the two-node graph with port numbers 0
and $i$ at two endpoints of the single edge. Consider any hypothetical
collision-free exploration algorithm, where two agents start at leaves 0 and
1. For any $i\in\\{0,1\\}$, this algorithm must prescribe a move to the agent
starting at the $i$th leaf, in some round. Suppose that, for the $i$th leaf,
it prescribes waiting $x_{i}\geq 0$ rounds and then moving, unless the agent
sees another agent in one of the waiting rounds. Without loss of generality,
let $x_{0}\geq x_{1}$. Then the adversary starts the agent at leaf 1
$x_{0}-x_{1}$ rounds after the agent at leaf 0. Thus both agents collide at
the central node after their first move.

##  5 Conclusion

We designed a collision-free exploration algorithm working for two agents in
arbitrary graphs of size larger than 2. The natural open problem is to
generalize our collision-free exploration to arbitrary teams of agents. This
is by no means straightforward. First, it is not even clear if the task is
feasible whenever the number of agents is smaller than the number of nodes (as
it is for two agents) and if so, what is the minimum vision radius necessary
to accomplish it. Second, our exploration strategy for two agents relies on
leader election among the agents, if this is possible, and on synchronization.
For two agents these are global properties: an order is established on all
agents, and all of them (i.e., both in our case) agree on a common round. It
is not clear how to achieve a similar feature for many agents. Finally, in our
case, agents communicate indirectly by making moves. This is possible because,
in our case, at least one agent is always adjacent to an empty node, and hence
changes of positions can be detected by the other agent. This may not be the
case for many agents, as there may be large parts of the graph completely
filled with agents, and thus this indirect communication by observing moves
may be difficult or impossible.

Another issue concerns the efficiency of collision-free exploration, even for
two agents. Since any agent can visit only one node in every round, it is
impossible to beat the complexity of the best exploration by a single agent.
As mentioned before, our solution has a generic feature: given any exploration
algorithm by a single agent, it produces a collision-free exploration by two
agents, with only logarithmic slowdown. While this slowdown is small, it is
natural to ask if it can be removed: does there exist a collision-free
exploration algorithm by two agents whose complexity is the same as that of
the best exploration by a single agent? Another variant of the problem is to
require that every node be visited by only one agent, instead of both of them.
Would this weakening help in getting the same complexity as the best
exploration by a single agent?

##  6 Acknowledgment

Funding: Supported in part by Natural Sciences and Engineering Research
Council of Canada (NSERC) discovery grant 2018-03899 and by the Research Chair
in Distributed Computing of the Université du Québec en Outaouais, Canada.

## References

  * [1] S. Albers and M. R. Henzinger, Exploring unknown environments, SIAM Journal on Computing 29 (2000), 1164-1188.
  * [2] R. Aleliunas, R. Karp, R. Lipton, L. Lovasz C. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, Proc. 20th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1979), 218-223.
  * [3] Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh: Piecemeal Graph Exploration by a Mobile Robot., Inf. Comput. 152 (1999), 155-172.
  * [4] E. Bar-Eli, P. Berman, A. Fiat and R. Yan, On-line navigation in a room, Journal of Algorithms 17 (1994), 319-341.
  * [5] Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil P. Vadhan: The Power of a Pebble: Exploring and Mapping Directed Graphs., Inf. Comput. 176 (2002), 1-21.
  * [6] M.A. Bender and D. Slonim, The power of team exploration: Two robots can learn unlabeled directed graphs, Proc. 35th Ann. Symp. on Foundations of Computer Science (FOCS 1994), 75-85.
  * [7] M. Betke, R. Rivest and M. Singh, Piecemeal learning of an unknown environment, Machine Learning 18 (1995), 231-254.
  * [8] A. Blum, P. Raghavan and B. Schieber, Navigating in unfamiliar geometric terrain, SIAM Journal on Computing 26 (1997), 110-137.
  * [9] J. Chalopin, S. Das, A. Kosowski, Constructing a map of an anonymous graph: Applications of universal sequences, Proc. 14th International Conference on Principles of Distributed Systems (OPODIS 2010), 119-134.
  * [10] J. Czyzowicz, D.Dereniowski, L. Gasieniec, R. Klasing, A. Kosowski, Dominik Pajak, Collision-free network exploration. J. Comput. Syst. Sci. 86 (2017), 70-81.
  * [11] X. Deng, T. Kameda and C. H. Papadimitriou, How to learn an unknown environment I: the rectilinear case, Journal of the ACM 45 (1998), 215-245.
  * [12] A.K. Dhar, B. Gorain, K. Mondal, S. Patra, R.R. Singh, Edge exploration of a graph by mobile agent, Proc. 13th International Conference on Combinatorial Optimization and Applications (COCOA 2019), 142-154.
  * [13] K. Diks, P. Fraigniaud, E. Kranakis, and A. Pelc, Tree exploration with little memory, Journal of Algorithms 51 (2004), 38-63.
  * [14] S. Dobrev, R. Kralovic, and E. Markou, Online graph exploration with advice, Proc. 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), 267-278.
  * [15] Christian A. Duncan, Stephen G. Kobourov, V. S. Anil Kumar: Optimal constrained graph exploration. ACM Trans. Algorithms 2 (2006), 380-402.
  * [16] P. Fraigniaud, D. Ilcinkas, A. Pelc, Tree exploration with advice, Information and Computation 206 (2008), 1276–1287.
  * [17] P. Fraigniaud and D. Ilcinkas. Directed graphs exploration with little memory, Proc. 21st Symposium on Theoretical Aspects of Computer Science (STACS 2004), 246-257.
  * [18] B. Gorain, A. Pelc, Deterministic graph exploration with advice. ACM Trans. Algorithms 15 (2019), 8:1-8:17.
  * [19] M. Koucký, Universal traversal sequences with backtracking, Journal of Computer and System Sciences 65 (2002), 717-726.
  * [20] Y. Nakaminami, T. Masuzawa, T. Herman, Self-stabilizing agent traversal on tree networks, IEICE Trans. 87-D (12) (20034), 2773-2780.
  * [21] P. Panaite and A. Pelc, Exploring unknown undirected graphs, Journal of Algorithms 33 (1999), 281-295.
  * [22] A. Pelc, A. Tiane, Efficient grid exploration with a stationary token, International Journal of Foundations of Computer Science 25 (2014), 247-262.
  * [23] N. S. V. Rao, S. Kareti, W. Shi and S.S. Iyengar, Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms, Tech. Report ORNL/TM-12410, Oak Ridge National Laboratory, July 1993.
  * [24] O. Reingold, Undirected connectivity in log-space, Journal of the ACM 55 (2008), 17:1-17:24.