Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents

Chalopin et al. [5] study mobile agents with limited energy that must collaboratively deliver data from network sources to a central repository. It turns out that the decision problem is NP-hard for a single source, and they present a 2-approximation algorithm to find the minimum energy assignable to each agent to deliver data. In a follow-up paper, Chalopin et al. [6] study $n$ mobile agents with limited energy on a straight line that must collectively deliver data from source point $s$ to target point $t$, and show that deciding if agents can deliver data is (weakly) NP-complete. Bärtschi et al. [3] study delivering $m$ messages between source-target pairs in an undirected graph using $k$ mobile agents initially at distinct nodes. Anaya et al. [1] study the problem of broadcast and convergecast with energy aware mobile agents. In the centralized setting, they give a linear-time algorithm to compute optimal battery power and strategy for convergecast and broadcast on a line. Finding the optimal battery power for trees is NP-hard. They also give a polynomial algorithm for 2-approximation for convergecast and 4-approximation for broadcast in arbitrary graphs. Czyzowicz et al. [9] studied broadcast and exploration in trees, and give an $O(n\log n)$ time algorithm to solve the problem in a $n$-nodes tree $T$. If the number of agents is at least equal to the number of leaves of $T$, their approach results in an $O(n)$ time algorithm. Bärtschi et al. [2] consider the possibility of gathering $k$ energy-constrained mobile agents in an undirected edge-weighted graph. The authors study three variants of near-gathering to minimize: (i) the radius of a ball containing all agents, (ii) the maximum distance between any two agents, or (iii) the average distance between agents. They prove that (i) is polynomial-time solvable, (ii) has a polynomial-time 2-approximation with matching NP-hardness lower bound, and (iii) admits a polynomial-time $2(1-\frac{1}{k})$-approximation but no FPTAS unless P=NP. Czyzowicz et al. [11] studied the exit search problem for two robots on an infinite line, starting at the origin. Time-energy trade-offs for this evacuation problem are studied. Contrary to all aforementioned works, the energy consumption of a robot traveling a distance $x$ at speed $s$ is measured as $x{s}^2$.

Energy transfer by mobile agents was previously considered by Czyzowicz et al. [8]. Agents travel and spend energy proportional to distance traversed. Some nodes have information acquired by visiting agents. Meeting agents may exchange information and energy. They consider communication problems where information held by some nodes must be communicated to other nodes or agents. They deal with data delivery and convergecast problems for a centralized scheduler with full knowledge of the instance. With energy exchange, both problems have linear-time solutions on trees. For general undirected and directed graphs, these problems are NP-complete. Then, Czyzowicz et al. [7] consider the gossiping problem in tree networks. In an edge-weighted tree network, agents spend energy while traveling and collect copies of data packets from visited nodes. They deposit copies of possessed data packets and collect copies of data packets present at the node. Czyzowicz et al. [7] prove that gossiping can be solved in $O(k^2{n}^2)$ time for an $n$-node tree network with $k$ agents.

Most related to our paper are the works by Czyzowicz et al. [10], Sun et al. [12], and Bramas et al. [4]. On the one hand, Czyzowicz et al. [10] study the collective exploration of a known $n$-node edge-weighted graph by $k$ mobile agents with limited energy and energy transfer capability. The goal is for every edge to be traversed by at least one agent. For an $n$-node path, they give an $O(n+k)$ time algorithm to find an exploration strategy or report that none exists. For an $n$-node tree with $\mathrm{\ell }$ leaves, they provide an $O(n+\mathrm{\ell }{k}^2)$ algorithm to find an exploration strategy if one exists. For general graphs, deciding if exploration is possible by energy-sharing agents is NP-hard, even for 3-regular graphs. However, it’s always possible to find an exploration strategy if the total energy of agents is at least twice the total weight of edges; this is asymptotically optimal. Next, Sun et al. [12] examines circulating graph exploration by energy-sharing agents on an arbitrary graph. They present the necessary and sufficient energy condition for exploration and an algorithm to find an exploration strategy if one exists. The exploration requires each node to have the same number of agents before and after. Finally, Bramas et al. [4] considered the problem of exploring every weighted edge of a given ring-shaped graph using a team of two mobile energy-sharing agents. They introduce the possibility for one of the two agents to fail unpredictably and cease functioning permanently (i.e., crashing). In this context, Bramas et al. [4] considered two scenarios: asynchronous (where no limit on the relative speed of the agents is known), and synchronous (where the two agents have synchronized clocks and operate at the same speed).

We consider the problem of graph exploration by energy-sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and the considered topology is that of connected acyclic graphs (i.e. trees). We assume that agents initially know the entire topology, as well as their starting locations. Under these strong assumptions, the lower-bounds we provide are interesting, as they also apply to more general case settings. The algorithms we present for the same setting demonstrate that the lower bounds are tight for path graphs, and almost tight for general trees. In the following, $e{n}_0$ and $e{n}_1$ denote the initial energy of the first and second agents, respectively. Also, $x$ denotes the initial distance between the agents.

On the positive side, we show that, two asynchronous agents can explore a weighted tree $T$ with diameter $d$ and total weight $W$ if (Theorem 7):

On the negative side, we provide a lower bound (Theorem 1) on the total energy for weighted star graphs (each edge has a weight $d/2$, $d\in \mathbb{N}$): $e{n}_0+e{n}_1$ cannot be in $2W+d\log (o(|E|))$.

In the synchronous case, a sufficient condition (Theorem 9) is:

On the other hand (Theorem 2), we show that there exists an infinite family of trees such that the required total energy is at least $2W+\frac{d}{2}-3$.

We also provide tight bounds for the case of path graphs, regardless of the initial locations of agents. The algorithms we provide when agents are not initially collocated assume that the agents may initially exchange information, and we discuss the trade-off between the amount of information exchanged and the solvability of the problem in this case. Due to space constraints, some proofs are omitted from the conference version of this paper.

For asynchronous stars, we first show a lower bound of the total energy consumption.

We now present a lower bound on the total energy for exploring a weighted tree with the total weight $W$ and a diameter $d$.

We now consider the case of two asynchronous agents in trees. Let $T=(V,E)$ be a weighted tree of $n$ nodes, and let $d$ be the weighted diameter of $T$. First, we construct a family of $k$ connected non-empty subtrees of $T$ named $T_1,T_2,\mathrm{\dots },T_k$, where $T_i=(V_i,E_i)$ and ${(E_i)}_{1\le i\le k}$ forms a partition of $E$. At the beginning, the agents meet to share energy. Then the agents repeat a procedure $explore(T_i)$ for all $i\in \{1,\mathrm{\dots },k\}$ from 1 to $k$. The procedure assumes that the agents are initially at the same location (possibly on an edge), and ensure that after execution the agents are at the same location (not necessarily the same as the initial one) if (when $i=k$ the agents can terminate anywhere on completion of the exploration).

Agent $r_0$ (resp. $r_1$) executing $explore(T_i)$ first moves to the closest node $v_i$ of $T_i$, executes $\mathrm{𝐸𝑢𝑙𝑒𝑟𝑖𝑎𝑛𝐸𝑥𝑝𝑙𝑜𝑟𝑒}(T_i)$ (resp. $\mathrm{𝑅𝑒𝑣𝑒𝑟𝑠𝑒𝐸𝑢𝑙𝑒𝑟𝑖𝑎𝑛𝐸𝑥𝑝𝑙𝑜𝑟𝑒}(T_i)$), and moves back to its initial location, until it meets the other agent, and $T_i$ is explored. If the agents meet before ending this sequence of moves and $E_i$ is explored, then the procedure terminates. This occurs during the exploration of the Eulerian tour from $v_i$, or when one of the agents $r$ comes back from $v_i$ to its initial location after completing its Eulerian tour while the other has not started it (it is still moving towards $v_i$ from the location where it started executing $explore(T_i)$).

Since the length of the Eulerian tour is $2w(T_i)$ (where $w(T_i)$ denotes the weight of $T_i$) and the distance to $v_i$ from their initial location is $d$ in the worst case, each agent must have, at the beginning of the procedure, the energy of at least $2d+2w(T_i)$ if (to terminate even when the other agent remains at the initial location), at least $d+2w(T_i)$ if $i=k$. When the procedure terminates the total energy consumed during the procedure is at most $2d+2w(T_i)$ (because every edge traversed in the procedure is traversed exactly twice if , and at most twice if $i=k$).

Consequently, to complete all $explore(T_i)$, for every $i$, sequentially, our algorithm requires that the total remaining energy $E{N}_i$ at the beginning of the procedure $explore(T_i)$ is as follows, where $x$ is the initial distance between the agents:

• $\mathrm{■}$

  $E{N}_k\ge 2d+4w(T_k)$

• $\mathrm{■}$

  $E{N}_i\ge \max (2d+2w(T_i)+E{N}_{i+1},4d+4w(T_i))(2\le i\le k-1)$

• $\mathrm{■}$

  $E{N}_1\ge x+\max (2d+2w(T_1)+E{N}_2,4d+4w(T_1))$ where $x$ is the initial weighted distance between the agents.

Moreover, the total energy consumption for exploring $T$ is at most $x+{\sum }_{i=1..k}(2d+2w(T_i))=2W+2kd+x$.

We now have to construct the partition $T_1,T_2,\mathrm{\dots },T_k$ of $T$ so that $k$ should be small to reduce the number of calls to $explore()$, but each $w(T_i)$ should not be too large to avoid increasing the energy required at the beginning of $explore(T_i)$. A good partition could be to have $w(T_k)=1$ and $w(T_i)=2w(T_{i+1})$, which results in $k=\lceil \log W\rceil$. In general trees, such a partition does not exist, but we can obtain a similar result using the centroid-based partition recursively.

Let $T=(V,E)$ be a weighted tree with total weight $W$. The centroid of $T$ is defined as follows. In the following, for a tree $T$ and a node $u$ of $T$, $T$ can be regarded as a rooted tree, denoted by $T^u$, rooted at $u$. For the root $u$ and its neighbor $v$, let $T_v^u$ be the subtree of $T^u$ rooted at $v$.

1. 1.

   When there exists an edge $(u,v)\in E$ satisfying and , the centroid of $T$ is the point $p$ on edge $(u,v)$ such that $w(T_v^u)+w(v,p)=w(T_u^v)+w(u,p)=W/2$. We call $p$ the edge centroid.

2. 2.

   When there exists a node $u\in V$ satisfying $w(T_v^u)+w(u,v)\le W/2$ for each neighbor $v$ of $u$, the centroid of $T$ is node $u$. We call $u$ the node centroid.

We now construct a new tree $T^{\prime }=(V^{\prime },E^{\prime })$ from $T$ by inserting nodes onto edges when necessary to simplify the construction of the partition. Observe that exploring the edges of $T^{\prime }$ is equivalent to exploring the edges of $T$, as exploring the two edges obtained after adding a node is equivalent to exploring the initial edge.

To construct $T^{\prime }=(V^{\prime },E^{\prime })$ and obtain $T_1,T_2,\mathrm{\dots },T_k$ of subgraphs of $T^{\prime }$, we recursively use the centroid-based partition of a tree. Let $T^{\prime }=T$ temporally and $c$ be the centroid of $T^{\prime }$. If $c$ is an edge centroid on an edge $e$, $T^{\prime }$ is updated by inserting a node at $c$ to partition $e$ into two edges. We denote the inserted node as $c$. So now, $c$ is the node centroid of $T^{\prime }$. Consider the subtrees $T_u^{\prime c}$ for each neighbor $u$ of $c$.

We can show that there exists a subset $N^{\prime }(c)\subset N(c)$ of neighbors of $c$ such that $W/3\le {\sum }_{u\in N^{\prime }(c)}(w(T_u^c)+w(c,u))\le W/2$. Let $T_1$ be the connected subtree of $T^{\prime }$ consisting of nodes ${\cup }_{u\in N^{\prime }(c)}V(T_u^c)\cup \{c\}$ and edges among them, where $V(T_u^c)$ denotes the set of nodes in $T_u^c$. Hence $T_1$ satisfies

Temporary tree $T^{\prime }$ is further updated (if necessary) and $T_2$ is obtained by applying the same method to the remaining tree consisting of the node set $V^{\prime }\setminus {\cup }_{u\in N^{\prime }(c)}V(T_u^c)$. Trees $T_3,T_4,\mathrm{\dots }$ are obtained by recursively applying the same method until the weight of the remaining tree becomes one or smaller, where the last subtree $T_k$ is the remaining tree. Each time the method is applied, the weight of the remaining tree is reduced by at least $2/3$, which implies the method is applied at most $k=\lceil {\log }_{3/2}W\rceil$ times. Thus, the initial amount of the total energy should be at least $2W+2d\lceil {\log }_{3/2}W\rceil +x$. Actually, we can derive the following sufficient condition on the initial amount of the energy.

$c{t}_1$

: $(e{n}_0\ge x)\wedge (e{n}_1\ge x)\wedge (e{n}_0+e{n}_1\ge 2W+2d\lceil {\log }_{3/2}W\rceil +x)$

The following shows the actions of the agents. It is assumed that subtrees $T_1,T_2,\mathrm{\dots }{T}_k$ $(k\le \lceil {\log }_{3/2}W\rceil )$ are a priori determined by the recursive centroid-based partitions.

Step 0:

The agents meet on the shortest path between their initial locations. (This is executed only once at the beginning of the execution.) Set $i=1$.

Step 1:

When they meet at a point, say $p$ (possibly on an edge), they evenly share the remaining energy.

Step 2

Agent $r_0$ (resp. $r_1$) performs the following sequence of moves: move to the nearest node $v_i$ of $T_i$; traverse $T_i$ along a Eulerian tour of $T_i$ in the clockwise direction (resp. the counter-clockwise direction) until the agent (i) meets the other, or (ii) completes the Eulerian tour traversal without meeting the other; move toward $p$ until the agent meets the other in case of ii) if ; If , set $p$ be the meeting point, set $i=i+1$, and continue from Step 1.

Notice that in unweighted stars of degree $\mathrm{\Delta }$, hence with $W=\mathrm{\Delta }$, we have $k=\lceil \log \mathrm{\Delta }\rceil$ holds for the number of the subtrees $T_1,T_2,\mathrm{\dots },T_k$ and the closest node $v_i$ of $T_i$ is the center node of the star graph for each $i(1\le i\le k)$. Consequently, the sufficient condition is refined and becomes tight.

We now present an upper bound for synchronous tree exploration. Our proof is constructive, as we present an algorithm to solve the problem. Our strategy for exploring $T$ is as follows. First, the two agents meet at the initial location $v_0$ of agent $r_0$, then they execute $SyncTreeExplore(T)$ that orders one agent to explore all the subtrees $T_1,\mathrm{\dots },T_{k-1}$, rooted at the children of $v_0$, except $T_k$ with the largest weight. When only $T_k$ is unexplored, the agents both move towards its root and execute recursively $SyncTreeExplore(T_k)$. If the exploring agent crashes, the other one can reach it to retrieve the remaining energy and explore the remaining edges on its own. The pseudo-code of $SyncTreeExplore$ is given in Algorithm 1 and is illustrated by Figure 2.

We now give a more formal description of the algorithm. First, the two agents meet at the node $v_0$ where agent $r_0$ is initially located. If $x$ is the initial distance between the two agents, $r_0$ waits for $r_1$ until the time $x$, the time $r_1$ should take to reach $v_0$ without crashing. If $r_1$ does not reach $v_0$ by the time, $r_0$ moves toward the initial location of $r_1$ until it meets $r_1$. When the agents are collocated, a total of $x$ energy is consumed. If $r_1$ is crashed, $r_0$ retrieves all the energy from $r_1$ and explores the entire tree using at most $2W$ energy.

If both agents are in $v_0$, then the agents execute $SyncTreeExplore$ as follows. Consider $T$ as a tree rooted at $v_0$ and let $T_i(1\le i\le k)$ be the subtree rooted at a child $v_i$ of $v_0$, and let $w_i=w(T_i)+w(v_0,v_i)$ . Without loss of generality, assume that $w_k$ is the largest among all $w_i(1\le i\le k)$. Then, we explain how to explore $T_1,T_2,\mathrm{\dots },T_{k-1}$ (subtrees except for $T_k$) one by one, followed by the exploration of $T_k$ in a recursive way.

To explore $T_i(1\le i\le k-1)$, the agents first evenly share energy so that each has the energy of at least $2w_i$, which is sufficient to solely complete the exploration of $T_i$ and come back to $v_0$. Agent $r_0$ moves to the root of $T_i$, traverses $T_i$ along an Eulerian tour, and then comes back to $v_0$. While $r_0$ explores $T_i$, $r_1$ is waiting at $v_0$. If $r_0$ does not come back to $v_0$ in time $2w_i$ after leaving $v_0$ for $T_i$ (which implies $r_0$ crashes during the traversal), $r_1$ explores $T_i$ along the same Eulerian tour of $T_i$ but in the opposite direction until it meets $r_0$ and $T_i$ is completely explored. When $r_1$ meets $r_0$, it gets all the remaining energy from $r_0$, comes back at $v_0$ and explores all the remaining part $T_{i+1},T_{i+2},\mathrm{\dots },T_k$ by itself. The energy consumption for exploring $T_i$ is $2w_i$ with additionally at most $d$ (the diameter) if $r_0$ crashes during the exploration (but this can occur at most once). If $r_0$ does not crash and completes the exploration of $T_i$, then the agents share their energy and $r_0$ explores $T_{i+1}$ in a similar way. If agent $r_0$ explores $T_1,T_2,\mathrm{\dots },T_{k-1}$, then the agents evenly share the remaining energy, move to the root of $T_k$, and explore $T_k$ using the same algorithm $SyncTreeExplore(T_k)$.

The remarkable point is that the edge between $v_0$ and the root of $T_k$ is traversed by the two agents together but is never traversed afterward. Hence each edge is traversed exactly twice if no crash occurs. If a crash occurs, each edge is traversed at most twice, except for a path of length at most $d$ that is traversed three times. Thus, the total energy consumption for exploring $T$ is at most $2W+d+x$; $x$ moving to $v_0$ and $2W+d$ for exploring the tree.

The condition for the above method is as follows.

$c{t}_2$

: $(e{n}_0\ge x)\wedge (e{n}_1\ge x)\wedge (e{n}_0+e{n}_1\ge 2W+d+x)$

Let $G=(V,E)$ be a path graph (called line thereafter) such that $V=\{v_0,v_1,\mathrm{\dots },v_{n-1}\}$ and . We consider that $v_i$ is on the left of $v_{i+1}$ and says, for example, “an agent moves left”. Let $w_i$ be the weight of edge $e_i$. For each node $v_i$, let $\mathrm{𝑑𝑖𝑠}(v_i)$ be the weighted distance from $v_0$ to $v_i$, that is, $\mathrm{𝑑𝑖𝑠}(v_i)={\sum }_{j=0..i-1}{w}_j$, and let $\mathrm{\ell }$ be the total weight of $G$, that is, $\mathrm{\ell }=\mathrm{𝑑𝑖𝑠}(v_{n-1})$. Consider that agents $r_0$ and $r_1$ are initially located at nodes $s_0$ and $s_1$ respectively. For convenience, we assign $x=\mathrm{𝑑𝑖𝑠}(s_0)$ and $y=\mathrm{𝑑𝑖𝑠}(s_1)$, and assume without loss of generality that $x\le y$ and $x\le \mathrm{\ell }-y$ ²²2If $x>\mathrm{\ell }-y$, one can reverse the order of the nodes on the line, exchange the positions of $r_0$ and $r_1$, and the condition is satisfied in the new graph.. Figure 3 illustrates these notations.

Let $e{n}_0$ and $e{n}_1$ be the initial energy of agents $r_0$ and $r_1$ respectively. The four conditions for the rules are:

$c_1$

: $(e{n}_0\ge x+y)\wedge (e{n}_1\ge y)\wedge (e{n}_0+e{n}_1\ge 2\mathrm{\ell }+x+y)$

$c_2$

: $(e{n}_0\ge \mathrm{\ell }-x)\wedge (e{n}_1\ge 2\mathrm{\ell }-(x+y))\wedge (e{n}_0+e{n}_1\ge 4\mathrm{\ell }-(x+y))$

$c_3$

: $(e{n}_0\ge \mathrm{\ell }+x)\wedge (e{n}_1\ge 2\mathrm{\ell }-y)$

$c_4$

: $(e{n}_0\ge y-x)\wedge (e{n}_1\ge y-x)\wedge (e{n}_0+e{n}_1\ge min(3\mathrm{\ell }+y-x,2\mathrm{\ell }-x+3y))$

The corresponding actions are denoted by $a_i$, $i\in \{1,\mathrm{\dots },4\}$.

$a_1$

:

$r_0$

: $(v_0)\leftarrow$; $\to (v_{n-1})$

$r_1$

:

$(r_0)\leftarrow$ ; if $\overleftarrow{r_0}$ then  $(v_0)\leftarrow$ ; $\to (v_{n-1})$ else  $\to (v_{n-1})$

$a_2$

:

$r_0$

:

$\to (r_1)$ ; if $\overrightarrow{r_1}$ then  $\to (v_{n-1})$ ; $(v_0)\leftarrow$ else  $(v_0)\leftarrow$

$r_1$

: $\to (v_{n-1})$; $(v_0)\leftarrow$

$a_3$

:

$r_0$

: $(v_0)\leftarrow$; $\to (v_{n-1})$;

$r_1$

: $\to (v_{n-1})$; $(v_0)\leftarrow$

$a_4$

:

$r_0$

:

$\to (r_1)$ ; if $v_0\prec v_{n-1}$ then  $(v_0)\leftarrow$ ; $\to (v_{n-1})$ else  $\to (v_{n-1})$ ; $(v_0)\leftarrow$

$r_1$

:

$(r_0)\leftarrow$ ; if $v_0\prec v_{n-1}$ then  $(v_0)\leftarrow$ ; $\to (v_{n-1})$ else  $\to (v_{n-1})$ ; $(v_0)\leftarrow$

In the above algorithms, when two agents meet, they share energy equally. In more detail, if the energy levels when meeting are $e{n}_i^{\prime }$ and $e{n}_j^{\prime }$ with , then $r_i$ takes an amount of energy $(e{n}_j^{\prime }-e{n}_i^{\prime })/2$ from $r_j$. After the transfer, their energy levels are both $(e{n}_i^{\prime }+e{n}_j^{\prime })/2$.

In the following, we show that satisfying at least one of the conditions $c_1,c_2,c_3$ or $c_4$ is necessary for two asynchronous agents to complete exploration of lines. We first state some general facts about asynchronous line exploration in the following Lemma.

For two agents without energy sharing, the following lemma shows the amounts of the initial energy of the agents necessary and sufficient for exploration of lines.

In this subsection, we consider synchronous lines. We assume that two agents start execution at the same time, and it takes time $d$ for each agent to travel distance $d$. A remarkable feature of synchronous lines is that an agent can detect the crash of the other when it does not show up as scheduled. This feature enables energy saving with respect to the asynchronous case. We consider four possible conditions that enable exploration:

$c_1$

: $(e{n}_0\ge x+y)\wedge (e{n}_1\ge y)\wedge (e{n}_0+e{n}_1\ge max(\mathrm{\ell }+x+y,2\mathrm{\ell }+x-y))$

$c_2$

: $(e{n}_0\ge \mathrm{\ell }-x)\wedge (e{n}_1\ge 2\mathrm{\ell }-(x+y))\wedge (e{n}_0+e{n}_1\ge 3\mathrm{\ell }-x-y)$

$c_3$

: $(e{n}_0\ge \mathrm{\ell }+x)\wedge (e{n}_1\ge 2\mathrm{\ell }-y)$

$c_4$

: $(e{n}_0\ge y-x)\wedge (e{n}_1\ge y-x)\wedge (e{n}_0+e{n}_1\ge 2\mathrm{\ell }-x+y)$