1 Introduction

Overview

Graph exploration is a well studied problem in computer science with a wide range of applications from searching the internet to navigation of robots in unknown environments. The objective is to discover an initially unknown graph by visiting all nodes starting from a given node of the graph. The problem has been well studied for a single agent exploring a graph [22] or a digraph [1] with the aim of minimizing the exploration time or equivalently the number of edges traversed. Others have studied the problem from the perspective of minimizing the memory needed by the agents for exploration [13, 19]. When the nodes of the graph do not have identifiers, the agent may need to mark nodes with a pebble to recognize them and thus, another research direction is to minimize the number of pebbles used for exploration [6].

When the exploration is performed by physical robots, one of the major issues is the energy consumed during the exploration, since each robot may have alimited amount of energy for movement. Surprisingly, most previous studies on exploration have not considered this limitation. Betke et al. [7] and later Awerbuch et al. [2] have studied the problem of exploration with an energy constrained agent. Their solution requires afuelling station at the starting node and the agent periodically returns there to refuel. Between two visits to the starting node, the agent can make at most B edge traversals. Thus the diameter of graphs that can be explored is restricted to B/2. When refuelling is not allowed, multiple agents may be needed to explore even graphs of restricted diameter. Given agraph G, determining whether ateam of k agents, each having an energy constraint of B can explore G is known to be an NP-hard problem, even when the graph G is atree [18]. When the graph (or the tree) is unknown, there are two possible approaches for online exploration. One approach is to fix the number k of agents and try to optimize the amount of energy B required by each agent as studied by Dynia et al. [15, 17]. In this paper, we take the other approach of fixing the available energy B for each agent and bounding the number of agents used for exploration. In fact, the limitation of energy is ahard constraint and it is often not possible in practice to add additional batteries to aphysical robot. Moreover, it is preferable to use alarge number of small robots rather than afew bulky ones, as advocated by robotics researchers [8]. The line of research in this paper goes in this direction. In our model, each agent has alimited energy resource without the ability to recharge, thus allowing the agent to traverse at most B edges, and our objective is to minimize the total number of such agents used for exploration. The cost of an algorithm is the number of agents used for exploration. An online exploration algorithm has no knowledge of the graph G, while an offline algorithm knows the graph in advance. We measure the efficiency of the solution in terms of the competitive ratio which is defined as the worst case ratio of the cost of the online algorithm for some graph G over the cost of the optimal offline algorithm for the same graph. In this paper, we restrict ourselves to exploration of trees, which are easier to explore than general graphs. The agents start at the designated root of an unknown tree T and they must collectively visit every node of T, i.e., each node of the tree must be visited by at least one agent. The agents are not required to return to the root after the exploration.

If the height of T, i.e., the longest path between the root and aleaf, is greater than B, then T cannot be fully explored, even by an unbounded number of agents.

On the other hand, if the height of the tree is exactly B then each leaf at depth B must be visited by a separate agent. Once the tree is completely explored and known up to depth B − 1 then we can send one additional agent to explore each leaf at depth B. Observe that any optimal offline algorithm would also need to send one agent per leaf at depth B. Thus, we can safely ignore these agents, as this would not increase the cost of the algorithm by more than a factor of 2. So, in this paper we consider algorithms for exploring trees of height at most B − 1. Note that the previous results [2, 7, 14, 15] for energy-constrained agents were restricted to exploring trees of height at most B/2 or graphs of diameter at most B/2.

Related Work

The graph exploration problem has been previously studied with the objective of minimizing the time for exploration. Studies on exploration of general graphs usually assume that the nodes of the graph are labeled such that agents can identify an already visited node, while the exploration of trees does not require this assumption. For exploration of undirected graphs by a single agent, the algorithm given by Panaite and Pelc [22] requires m + O(n) time for exploring a graph of m edges and n nodes. For exploration of an unknown tree, exploration in the optimal time of 2(n − 1) can be achieved by the depth-first search algorithm. Using multiple agents can speedup the exploration and Fraigniaud et al. [18] have presented an algorithm for a team of k mobile agents that explores a tree of height D in O(D + n/log k) time. They also showed that any algorithm for k-agent exploration of a tree has at least a (2 − 1/k) overhead over the optimal offline algorithm. While the above results are for small team of agents (where \(k\leq \sqrt {n}\)), Dereniowski et al. [12] used a large team of agents to reduce the exploration time to O(D) and their solution also works for general graphs where all nodes are within distance D from the starting node. The competitive ratio of the time cost to explore an unknown tree by k agents has been studied by Dynia et al. [16] where the agents have limited range communication capabilities. Ortolf et al. [21] gave bounds on the competitive ratio for multiple agent exploration of grid graphs with obstacles. For general graphs, Megow et al. [20] presented a single-agent exploration algorithm having a constant competitive ratio.

The above results do not consider any energy limitation for the agent. For a single, energy constrained agent, the problem of exploration with refuelling, has been studied for grid graphs [7] and also for general graphs [2]. The optimal time algorithm for exploration with refuelling was given by Duncan et al. [14], who also studied exploration under a different type of constraint where the agent is tied to the starting node with a string of fixed length of l = B/2. Note that this algorithm can only explore graphs of diameter much less than B/2.

Results on exploration usually assume that agents can identify an already visited vertex, while the exploration of trees does not require this assumption.

For a team of k agents, the problem of exploring a tree using limited energy resources was investigated by Dynia et al. [15] who presented an algorithm that is 8-competitive in terms of the energy consumed by each agent. This was later improved to a competitive ratio of (4 − 2/k) by Dynia et al. [17]. Other problems that have been considered for energy constrained agents (that may not start at the same node) include broadcast and convergecast [3] as well as delivery from a source node to a target node in the graph [4, 5, 9]. Czyzowicz et al. [10] in a recent work studied the delivery and convergecast problems under the assumption that the agents can exchange energy when they meet. These are mainly offline solutions where the graph and the starting locations are given as input.

Our Results

We consider the problem of exploration of an unknown tree by a team of mobile agents initially located at the root of the tree. Each agent is equipped with a battery of size B which bounds the total number of edges the agent can traverse during its lifetime. We assume the height of the tree to be at most B − 1, and our objective is to find an exploration strategy where every node of the tree is visited by at least one agent, and we wish to minimize the total number of agents used. We study this problem first assuming a global communication model (where agents communicate to each other instantaneously) and provide an algorithm for online exploration, that has a competitive ratio of O(log B). We then show how to remove the assumption of global communication and achieve the same result in the local communication model, with a constant overhead. Finally we provide a lower bound of Ω(log B) on the competitive ratio of any online exploration algorithm for energy-constrained agents in the local communication model, showing that our result is tight. We conclude with some open questions for future research.

2 The Model

The environment to be explored is a rooted tree T. The root r 0 contains an infinite supply of mobile agents, each of which has a limited energy B, allowing it to traverse at most B edges during its lifetime. There is a total order among the agents (i.e., they have distinct identities). The nodes of the tree may be assumed to be anonymous (i.e., we do not require unique identifiers for the nodes of T). Each agent has unlimited memory. When two agents are at the same node, they can freely exchange information. However the agents may not write any information on the nodes of the tree.Footnote 1 We call this the local communication model. In contrast, in a global communication model an agent can communicate instantaneously with any other agent irrespective of their location in the tree.

All agents start at the same time, in the same state. The agents move synchronously. At each time unit, any agent can move to an adjacent node or stay at its current node. Each move costs one unit of time and one unit of energy, while computation and communication between agents are instantaneous and do not consume any energy. The agents cannot exchange their energy resources or recharge their batteries.

The height of the tree (i.e., the distance to the furthest leaf from the designated root r 0) is at most B − 1 and this information is known to the agents. However, the size (number of nodes in the tree) and the structure of the tree are initially unknown to the agents. The edges incident at each node are locally ordered with port numbers, allowing the agents to choose edges to visit in a deterministic manner. An exploration strategy for the team of agents is successful if each node of the tree visited by at least one agent. The cost of the exploration strategy is the number of agents which made any non-null moves during the exploration. We denote by OPT the cost of the optimal offline strategy that has complete knowledge of the tree.

For any node r ∈ T we denote by T r the subtree of T, rooted at r. Further for any node v ∈ T r , we define the depth of node v as the length of the path from r to v. We denote by \(T^{\delta }_{r}\) the subtree rooted at r truncated to depth δ from r. We denote by |T|, the number of edges in T.

3 Exploration with Global Communication

In this section we describe and analyze a recursive algorithm for tree exploration under the global communication model. The algorithm is called Global Communication Tree Exploration (GCTE). The main idea of the algorithm is to explore the tree up until a certain depth and afterwards take advantage of the already known part of the tree to continue the exploration. More specifically, this algorithm proceeds by levels. Each level of the algorithm is a set of nodes which are located at a certain depth of the tree. The first level consists of the root r 0. At each level i, agents having energy b i , expand the explored part of the tree further by increasing its depth by ⌈ε ⋅ b i ⌉ where ε is a parameter of the algorithm such that \(0< \varepsilon < \frac {1}{4}\). The new frontier of the explored part defines the next level of the algorithm. The algorithm GCTE ε is then recursively called at each node r of the newly created level i. Whenever an agent is needed at a node r, one agent from the global root r 0 arrives at r to execute GCTE ε

Definition 1

For i = 1, level i of algorithm GCTE ε consists of the root node r 0; the depth d i of the level i is d 1 = 0, the energy b i at this level is b 1 = B. For i > 1, level i of GCTE ε consists of all nodes at depth d i = d i− 1 + ⌈ε ⋅ b i− 1⌉, and b i = B − d i .

For any two nodes u and v at the same level, we would like the exploration of the trees T u and T v to proceed independently, using disjoint sets of agents. To this end, we allow some overlap between successive levels of the algorithm. More precisely, at each level i, the exploration is extended to depth of \(\left \lfloor {(\frac {1}{2} +\varepsilon ) \cdot b_{i}}\right \rfloor \), although the next level still starts at depth ⌈ε ⋅ b i ⌉ from the current level. This additional extension at each level i allows the algorithm to look ahead at the start of the next level (i + 1). Thus, at the start of a recursive call to Algorithm GCTE ε at a node r at level i + 1, the subtree T r has been already partially explored to some depth. We show below (c.f. Lemma 1) that the exploration of this partially explored subtree T r can be done independently to any other subtree at the same level.

Definition 2

Two partially explored subtrees T u and T v , rooted at nodes u and v located at the same depth from r 0, are said to be independent if no single agent can visit nodes in the unexplored part of both subtrees.

Informally, this independence means that disjoint teams of agents can be used for exploring such subtrees during the algorithm. See Fig. 1, which illustrates the ‘overlaps’ of explored parts of the subtrees for two consecutive calls to GCTE ε .

Fig. 1
figure 1

The explored subtrees for two consecutive calls to GCTE ε : the first for node r at level i and the next recursive call for r ′ at level i + 1. The first shaded region is the explored part of T r and the second shaded region is the part explored during level i

Full size image

We now formally describe our Algorithm GCTE ε .

figure a

For an execution of GCTE ε with parameters r and b, we define \(x(\varepsilon ) = \frac {1}{2}(\frac {1}{2} - \varepsilon ) b\). Each agent saves ⌈x(ε)⌉ units of energy which is never used during GCTE ε . This energy will be used later as explained in the next section.

Procedure Uncover (r,δ) with input node r and an integer δ works as follows. During this procedure, the agents explore the unexplored part of subtree T r rooted at r, using a Depth First Search (DFS) traversal restricted to a depth of δ from r. This DFS traversal is defined as the walk followed by an agent of infinite energy starting at node r and performing DFS on the tree T ′ that is obtained from T r δ by pruning all subtrees that have been already explored (before the call to Uncover). An agent initially located at the root r 0 arrives at the current root r, having b units of energy and begins to explore the subtree \(T^{\delta }_{r}\). First, this agent goes to the unexplored node that is supposed to be visited next in the DFS traversal. From this node, the agent follows the DFS traversal. Finally, when the agent has ⌈x(ε)⌉ units of energy left, it interrupts the exploration. Note that in the global communication model, at any point of the exploration, each agent possesses the full knowledge of the part of the tree explored to date and the current locations of all agents. Hence, another agent will arrive at r and continue the exploration by visiting the unexplored node that is supposed to be visited next according to the DFS traversal. This procedure ends when all nodes at depth δ or less have been visited.

Lemma 1

The subtrees that are created in step 2 of GCTE ε are pairwise independent. Moreover, for any such subtree T r rooted at a node r any agent that explores any edge in the unexplored part of T r cannot return to node r.

Proof

Consider the subtree T r rooted at r at the start of procedure Uncover(r,δ) at some level i > 1 of the algorithm. Let \(E_{r}^{\prime }\) denote the set of unexplored edges of T r . By construction, we have that subtree T r is already explored until depth \(d \geq \left \lfloor \frac {1}{2} \cdot b_{i-1} \right \rfloor \) from r and thus any edge in \(E_{r}^{\prime }\) is at distance at least d from r. Any agent located at r has at most b i units of energy and \(d \geq \left \lfloor \frac {1}{2} \cdot b_{i-1} \right \rfloor \geq \left \lfloor \frac {1}{2} \cdot b_{i} \right \rfloor \). As a result, the agent will use at least d + 1 units of its available energy to explore any edge in \(E_{r}^{\prime }\), where \(d + 1 > \frac {1}{2} \cdot b_{i}\), thus, such an agent would not have sufficient energy to return to the root r and subsequently to reach any other subtree rooted at the same level. □

Theorem 1

For any \(\varepsilon , \ 0 < \varepsilon < \frac {1}{4}\) , Algorithm GCTE ε called with parameters r 0 and B correctly explores the tree.

Proof

To prove the correctness of GCTE ε , we will first show that procedure Uncover(r,δ) called for a subtree T r rooted at r at some level i ≥ 1 with \(\delta =\left \lfloor {(\frac {1}{2} + \varepsilon ) b_{i}}\right \rfloor \) correctly explores the subtree T r up to depth δ. In order to prove this, we will show that each agent has enough energy to reach an unexplored edge. Note that by a simple induction on the distance of r from r 0, any agent that arrives at node r, to execute Uncover(r,δ), has exactly b i units of energy. Further any such agent A has complete knowledge of the part of subtree T r already explored by previous agents and thus agent A knows the path from r to the next unexplored node v in the DFS traversal of \(T^{\delta }_{r}\). This node v is at distance at most δ from r. According to the algorithm, agent A has

$$l:=b_{i} - \left\lceil x(\varepsilon) \right\rceil = \left\lfloor b_{i} - x(\varepsilon) \right\rfloor \geq \delta + \left\lfloor x(\varepsilon) \right\rfloor $$

units of energy available for the DFS traversal. Since l ≥ δ the agent does succeed in reaching the node v. Hence, each agent used in Uncover visits at least one previously unexplored node in \(T^{\delta }_{r}\). As long as there are unexplored edges we keep sending agents, where this implies that eventually all nodes within depth δ in T r are visited during the DFS exploration. This proves the correctness of procedure Uncover.

In order to complete the proof of the correctness of GCTE ε , we note that the algorithm makes progress at each level i, that is, level i + 1 is at strictly greater depth than level i. Indeed, this follows from ε b i > 0 for ε > 0, which gives ⌈ε b i ⌉ ≥ 1. □

Lemma 2

The number of levels in Algorithm GCTE ε is at most \(\log _{(\frac {1}{1-\varepsilon })} B\) .

Proof

For the purpose of this proof introduce two variables \(d_{i}^{\prime }\) and \(b_{i}^{\prime }\) as follows: \(d_{1}^{\prime }= 0\) and \(d_{i}^{\prime }=d_{i-1}^{\prime }+\varepsilon \cdot b_{i-1}^{\prime }\) for i > 1, where \(b_{i}^{\prime }=B-d_{i}^{\prime }\) for i ≥ 1.

We first argue by induction on i that \(d_{i}^{\prime } = B-(1-\varepsilon )^{i-1}B\) for i ≥ 1. This claim trivially holds for i = 1 so take now some i ≥ 1 and assume that \(d_{i}^{\prime } = B-(1-\varepsilon )^{i-1}B\). We obtain

$$\begin{array}{@{}rcl@{}} d_{i + 1}^{\prime} = d_{i}^{\prime} + \varepsilon b_{i}^{\prime} = d_{i}^{\prime} + \varepsilon(B-d_{i}^{\prime}) = (1-\varepsilon)d_{i}^{\prime} + \varepsilon B \\ = (1-\varepsilon)\left( B-(1-\varepsilon)^{i-1}B \right) + \varepsilon B = B-(1-\varepsilon)^{i}B, \end{array} $$

as required.

Since \(d_{i}\geq d_{i}^{\prime }\) for each i ≥ 1, we have proved that d i+ 1 ≥ B − (1 − ε)i B for each i ≥ 1. Observe now, that if (1 − ε)i ⋅ B ≤ 1, then the i-th call is the last recursive call to GCTE ε , i.e., the subtrees rooted at level i + 1 have no unexplored edges. This holds due to the fact that the height of the tree is no more than B − 1. Therefore, the inequality (1 − ε)i ⋅ B ≤ 1, gives us an upper bound on the maximum level number i, which gives at most \(\log _{(\frac {1}{1- \varepsilon })} B \) levels. □

Before proceeding to calculating the cost of Algorithm GCTE ε , let us make the following useful remark. During the procedure Uncover, each participating agent uses at most δ − 1 energy to reach the starting node for its DFS exploration and uses at least \(b -(\delta - 1) - \left \lceil {x(\varepsilon )}\right \rceil \geq \left \lceil {\frac {1}{2}(\frac {1}{2} - \varepsilon ) b}\right \rceil \) units of energy to contribute to the DFS exploration of unexplored nodes.

Lemma 3

Procedure Uncover ( r,δ ) for r = r 0 and δ = ⌊(1/2 + ε)B⌋uses S O L r agents where S O L r ≤\(\frac {4}{(\frac {1}{2} - \varepsilon )} \cdot OPT\) .

Proof

In this case, \(T^{\delta }_{r}\) is completely unexplored at the start of the procedure. By the properties of DFS exploration, the DFS walk of a tree \(T^{\delta }_{r}\) is of length \(2\cdot |T^{\delta }_{r}|\). Each agent (except possibly the last one) uses at least \(\left \lceil \frac {1}{2}(\frac {1}{2} - \varepsilon ) \cdot B \right \rceil \) of its available energy to traverse a part of this walk. Thus, we get the following inequality:

$$\left\lceil \frac{1}{2}\left( \frac{1}{2} - \varepsilon\right) \cdot B \right\rceil \cdot {SOL_{r}} \leq 2 \cdot |T^{\delta}_{r}| \leq 2 \cdot |T|. $$

In addition, we have that |T|≤ O P T⋅ B, since the optimal algorithm must visit all the edges of the tree T. Hence, we get

$$\left\lceil \frac{1}{2}\left( \frac{1}{2} - \varepsilon\right) \cdot B \right\rceil \cdot {SOL_{r}} \leq 2 \cdot {OPT_{}} \cdot B,$$

Finally, we have that \(\frac {1}{2}\left (\frac {1}{2} - \varepsilon \right ) \cdot B \leq \left \lceil {\frac {1}{2}\left (\frac {1}{2} - \varepsilon \right ) \cdot B}\right \rceil \), therefore

$${SOL_{r}} \leq \frac{4}{\frac{1}{2} - \varepsilon} \cdot {OPT_{}} .$$

□

Theorem 2

Algorithm GCTE ε has a competitive ratio of at most \( \frac {4}{(\frac {1}{2} - \varepsilon )} \cdot \log _{(\frac {1}{1-\varepsilon })} B\) .

Proof

Consider a call to GCTE ε (r,b i ) at some level i > 1, where r is at depth d i > 0 from the global root. Let S O L r denote the number of agents used by the algorithm to explore edges of the subtree T r during level i. A DFS exploration walk of T r that starts and ends at r has length 2 ⋅|T r |. As explained before each of the S O L r agents (except the last one) use at least \(\left \lceil \frac {1}{2}(\frac {1}{2} - \varepsilon ) b_{i} \right \rceil \) of their available energy to contribute to the DFS exploration. The last agent may have some available energy after visiting the last unexplored edge in T r but it does not have enough energy to return to node r (by Lemma 1). Therefore, if we assume that the last agent attempts to reach the root r with its remaining energy, we can say that the path traversed in total by the agents is less than 2 ⋅|T r |. Thus,

$$\frac{1}{2}(\frac{1}{2} - \varepsilon) b_{i} \cdot {SOL_{r}} \leq \left\lceil \frac{1}{2}(\frac{1}{2} - \varepsilon) b_{i} \cdot {SOL_{r}} \right\rceil \leq 2 \cdot |T_{r}| $$
$$\implies {SOL_{r}} \leq \frac{4}{b_{i}(\frac{1}{2} - \varepsilon)} |T_{r}|$$

Furthermore, due to Lemma 1, we know the subtrees at the same level are independent so we can sum up over all subtrees at level i:

$${\sum}_{r \in r_{1}, r_{2}, \ldots}{SOL_{r}} \leq \frac{4}{b_{i}(\frac{1}{2} - \varepsilon)} {\sum}_{r \in r_{1}, r_{2}, \ldots} |T_{r}| $$
$${SOL_{}} (i) \leq \frac{4}{b_{i}(\frac{1}{2} - \varepsilon)} |T \setminus T_{r_{0}}^{d_{i}}|$$

where S O L(i) denotes the number of agents used by the algorithm at level i. The optimal algorithm uses OPT agents to explore the tree. Any agent that reaches to depth d i of T has b i units of energy remaining. Thus, each agent can traverse at most b i edges below this depth. Hence

$$b_{i} \cdot {OPT_{}} \geq | T \setminus T_{r_{0}}^{d_{i}} | $$

Combining the above two equations, we have

$${SOL_{}} (i) \leq \frac{4}{\frac{1}{2} - \varepsilon} {OPT_{}} $$

The above bound holds for any level i > 1. Moreover, due to Lemma 3, we have exactly the same bound for level i = 1 of the algorithm. Since there are at most \(\log _{(\frac {1}{1-\varepsilon })} B\) levels in the algorithm (due to Lemma 2), we obtain the total cost SOL of the algorithm,

$${SOL_{}} \leq \frac{4}{\frac{1}{2} - \varepsilon} \cdot \log_{(\frac{1}{1-\varepsilon})} B \cdot {OPT_{}} $$

□

Note that on the termination of Algorithm GCTE ε , each agent that participated in the exploration at level i has at least \(x_{i}(\varepsilon )=\frac {1}{2}(\frac {1}{2} - \varepsilon ) \cdot b_{i}\) units of unused energy. This remaining energy would be used by the algorithm presented in the next section.

4 Exploration with Local Communication

This section is devoted to adaptation of GCTE ε for the model with local communication between agents. This is done in two steps. In the first step we introduce an intermediate stage between two models of global and local communication. We call this a semi-local communication model and we define it as follows: two agents performing the DFS exploration in Step 1 of an instance of GCTE ε can communicate only locally, that is, they can communicate only when present at the same node; on the other hand, whenever an agent is needed at a node r, one agent arrives from the global root at r to execute the instance of GCTE ε . Thus, in our semi-local communication model this mechanism of calling for agents uses the global communication model. In Section 4.1 we adopt GCTE ε so that it operates in the semi-local communication model and we calculate the cost of this modification in terms of the number of agents used. In particular, we prove that with respect to the original algorithm, the total number of agents increases by a constant factor (depending only on ε). Then, in Section 4.2, we add to our algorithm a mechanism for calling for new agents at local roots so that this part is also done via local communication.

4.1 Semi-local Communication Model

We start this section by providing some intuition. We consider an arbitrary execution of GCTE ε (r,b) for an input node r and energy level b. Recall Step 1 of GCTE ε , where the agents, one by one, perform the DFS traversal up to a certain depth of the subtree T r . Suppose that the agents that perform this traversal are \(\if !! A_{1} \else A_{1}^{}\fi ,\ldots ,\if !! A_{k} \else A_{k}^{}\fi \) and that they are ordered according to the precedence of their movements, i.e., \(\if !! A_{i} \else A_{i}^{}\fi \) traverses its path prior to A i+ 1 for each i ∈{1,…,k − 1}. For each agent \(\if !! A_{i} \else A_{i}^{}\fi \) we will add 5 additional agents denoted \(\if !1! A_{i} \else A_{i}^{1}\fi ,\ldots ,\if !5! A_{i} \else A_{i}^{5}\fi \). To simplify some statements we sometimes write \(\if !0! A_{i} \else A_{i}^{0}\fi \) in place of \(\if !! A_{i} \else A_{i}^{}\fi \). The agents \(\if !! A_{i} \else A_{i}^{}\fi ,\if !1! A_{i} \else A_{i}^{1}\fi ,\ldots ,\if !5! A_{i} \else A_{i}^{5}\fi \) are called the i-th team for each i ∈{1,…,k}. For the purposes of the analysis we introduce some additional notation that allows us to describe the behavior of agents during this DFS traversal in more details. As mentioned earlier, we denote

$$ x(\varepsilon)=\frac{1}{2}\left( \frac{1}{2}-\varepsilon\right) b. $$
(1)

We also say that an agent heads towards a node v if in each of the following consecutive time units the agent makes a move that gets it closer to v until either v is reached or the agent runs out of energy. It is said that the i-th team is successful if: (i) the agent \(\if !! A_{i} \else A_{i}^{}\fi \) visited a superset of nodes with respect to its original behavior in Step 1 of GCTE ε , and (ii) the agent \(\if !1! A_{i} \else A_{i}^{1}\fi \) reaches the root r and possesses the information about all moves performed by agents \(\if !! A_{1} \else A_{1}^{}\fi ,\ldots ,\if !! A_{i} \else A_{i}^{}\fi \).

We now describe the modification of the DFS traversal from Step 1 of GCTE ε by describing how \(\if !! A_{i} \else A_{i}^{}\fi \) and \(A_{i}^{1},\ldots ,A_{i}^{5}\) operate for each i ∈{1,…,k}.

Behavior of A i5

Recall that in Step 1 of GCTE ε , each agent \(\if !! A_{i} \else A_{i}^{}\fi \), i ∈{1,…,k}, finishes its part of DFS traversal having at least ⌈x(ε)⌉ energy left. We now use this energy as follows: the agent heads towards the root r in the next ⌈x(ε)⌉ time units.

Behavior of A i j’s

For each i ∈{1,…,k} and j ∈{1,…,5}, the agent \(\if !j! A_{i} \else A_{i}^{j}\fi \) follows the movements of \(\if !! A_{i} \else A_{i}^{}\fi \) up to depth

$$d_{j}(\varepsilon)= \left\lfloor j \cdot x(\varepsilon) \right\rfloor$$

until the completion of the movement of \(\if !! A_{i} \else A_{i}^{}\fi \). More precisely, the agent \(A_{i}^{j}\) mimics each move of A i from node u to node v if both u and v are within depth (from r) at most d j (ε). If, on the other hand, either u or v is at depth greater than d j (ε), then \(A_{i}^{j}\) stays idle during any such move of agent A i . Finally, the agent \(A_{i}^{j}\) heads towards the root r; we will describe below in which time step this action is triggered.

Order of Movements

Having described the movements of A i j and \(\if !j! A_{i} \else A_{i}^{j}\fi \) for each i ∈{1,…,k} and j ∈{1,…,5}, we specify the order of their actions. The agent \(\if !! A_{1} \else A_{1}^{}\fi \) starts its movement once all agents of the 1-st team are at r. For each i ∈{2,…,k}, the agent \(\if !! A_{i} \else A_{i}^{}\fi \) starts its movement once \(\if !1! A_{i-1} \else A_{i-1}^{1}\fi \) completed its movement by arriving at r and once all agents of the i-th team are at r. (We will argue later that A i− 11 indeed returns to the root r.) In other words, once \(\if !1! A_{i-1} \else A_{i-1}^{1}\fi \) completes its movement, all agents of the i-th team are called to appear at r. For each j ∈{1,…,5}, we only need to describe how they operate once \(\if !! A_{i} \else A_{i}^{}\fi \) runs out of energy, as their preceding movements are specified above. The agent \(\if !j! A_{i} \else A_{i}^{j}\fi \) heads towards the root r in time unit in which he occupies the same node as \(\if !j + 1! A_{i} \else A_{i}^{j + 1}\fi \) and the latter agent is heading towards r. (Thus, it may happen that for some units of time both agents will head towards r together.)

In the following we prove that the above actions of agents are valid under the assumption that they have to communicate locally. Considering the order of movements of agents it suffices to argue that each team is successful. We refer to all movements of the agents \(\if !j! A_{i} \else A_{i}^{j}\fi \), i ∈{1,…,k}, j ∈{1,…,5}, as the extended DFS traversal of T.

Lemma 4

For each i ∈{1,…,k}, the i-th team is successful.

Proof

We prove the lemma by induction on i. The argument is identical for i = 1 and i > 1 so take an arbitrary i ∈{1,…,k} and inductively assume that the (i − 1)-th team is successful whenever i > 1. If i = 1, then clearly the 1-st team needs no additional information about the subtree. By assumption, when i > 1, \(\if !1! A_{i-1} \else A_{i-1}^{1}\fi \) completes its movement reaching the root r and this agent knows the entire subtree explored by \(\if !! A_{1} \else A_{1}^{}\fi ,\ldots ,\if !! A_{i-1} \else A_{i-1}^{}\fi \). Thus, once \(\if !! A_{i} \else A_{i}^{}\fi \) is about to start its actions at r, it learns the subtree explored to date: for i > 1 this information comes from \(\if !1! A_{i-1} \else A_{i-1}^{1}\fi \) and for i = 1 it is known that the DFS traversal will be initiated by \(\if !! A_{i} \else A_{i}^{}\fi \). Thus, \(\if !! A_{i} \else A_{i}^{}\fi \) can indeed correctly resume in Step 1 of GCTE ε the DFS traversal and can correctly complete all its following actions as they do not depend on any extra knowledge. Hence, it remains to analyze the behavior of the remaining agents of the i-th team. Note that, by algorithm definition, all agents of the i-th team are present at the root r once \(\if !! A_{i} \else A_{i}^{}\fi \) is about to start its movements. Thus, each agent \(\if !j! A_{i} \else A_{i}^{j}\fi \) can correctly mimic the movements of \(\if !! A_{i} \else A_{i}^{}\fi \) till the depth predefined for \(\if !j! A_{i} \else A_{i}^{j}\fi \).

Suppose that \(\if !! A_{i} \else A_{i}^{}\fi \) reaches a node v at depth l with its last move; the move that ends the stage when it is heading towards r. According to the algorithm of the extended DFS traversal, \(\if !! A_{i} \else A_{i}^{}\fi \) was heading towards r and the duration of this stage was ⌈x(ε)⌉. Thus, these movements of \(\if !! A_{i} \else A_{i}^{}\fi \) of heading towards r started at a node v ′ at depth l + ⌈x(ε)⌉, at time unit t ′, ended at depth l and node v, and there exists a node u at depth d j (ε) on the path traversed during these movements of heading towards r. By construction, agent \(\if !j! A_{i} \else A_{i}^{j}\fi \) is at node u at time unit t ′.

At time step t ′, each agent \(\if !j^{\prime }! A_{i} \else A_{i}^{j^{\prime }}\fi \), j ′∈{1,…,5}, has at least ⌈x(ε)⌉ units of energy available. Indeed, this follows from two observations: first, the available energy of \(\if !! A_{i} \else A_{i}^{}\fi =\if !0! A_{i} \else A_{i}^{0}\fi \) is at least ⌈x(ε)⌉ at time step t ′; second: the length of the path traversed by \(\if !j^{\prime }-1! A_{i} \else A_{i}^{j^{\prime }-1}\fi \) till time step t ′ is not greater than the length of the path traversed by \(\if !j^{\prime }! A_{i} \else A_{i}^{j^{\prime }}\fi \) till time step t ′, for each j ′∈{1,…,5}. Furthermore, at time step t ′, the distance between any two consecutive agents \(\if !j^{\prime }! A_{i} \else A_{i}^{j^{\prime }}\fi , \if !j^{\prime }+ 1! A_{i} \else A_{i}^{j^{\prime }+ 1}\fi \) for j ∈{1,…,4} is not greater than ⌈x(ε)⌉ since ⌊(j + 1) ⋅ x(ε)⌋ −⌊j ⋅ x(ε)⌋ ≤ ⌊(j + 1) ⋅ x(ε) − j ⋅ x(ε)⌋ + α = ⌊x(ε)⌋ + α, where α < 1. Thus, in particular, each agent \(\if !j^{\prime }! A_{i} \else A_{i}^{j^{\prime }}\fi \) has enough energy to reach the node occupied by \(\if !j^{\prime }-1! A_{i} \else A_{i}^{j^{\prime }-1}\fi \) for each j ′∈{2,…,5}. Hence, by a simple induction on j ′ = j − 1,…,1 we obtain that \(\if !j^{\prime }+ 1! A_{i} \else A_{i}^{j^{\prime }+ 1}\fi \) meets \(\if !j^{\prime }! A_{i} \else A_{i}^{j^{\prime }}\fi \) at some time step and in this step \(\if !j^{\prime }! A_{i} \else A_{i}^{j^{\prime }}\fi \) has at least ⌈x(ε)⌉ units of energy and is present at depth ⌊j ′⋅ x(ε)⌋ in T. Thus, we obtain that \(\if !1! A_{i} \else A_{i}^{1}\fi \) is able to reach r (at depth 0 of T r ) carrying the required information. □

As a consequence of the above, we obtain the following.

Lemma 5

The extended DFS traversal correctly explores T r to a depth of \((\frac {1}{2}+\varepsilon )B\) using 6k agents that communicate locally, where k is the number of agents used in the DFS traversal performed in Step 1 of Algorithm GCTE ε .

Proof

The fact that the k teams, each of size 6, explore the tree to the required depth follows directly from Lemma 4. □

4.2 Local Communication Between Levels

We start this section with an informal description, also pointing out the obstacles we need to overcome. The mechanism of communication between two consecutive levels will be handled by special agents that we call managing agents (see below for a formal definition). A managing agent arrives at a root r for which a call to GCTE ε is performed. This agent is not used for the extended DFS traversal of T r but will play a crucial role while conducting recursive calls for descendants r 1,r 2,…. More precisely, this agent will keep track of which subtrees have been already explored and for which one the recursive call is ‘in progress’. By a recursive call, made say for r i , being in progress we mean that the exploration of \(T_{r_{i}}\) is in progress. Thus, until the exploration of that subtree is completed, the managing agent for T r is responsible for redirecting all agents arriving at r to this subtree, \(T_{r_{i}}\). Once the exploration of \(T_{r_{i}}\) is completed, the managing agent for \(T_{r_{i}}\) will report this fact to the managing agent for T r and the latter one may initiate the process of exploration of the next subtree \(T_{r_{i + 1}}\). Once all subtrees \(T_{r_{1}},T_{r_{2}},\ldots \) are explored the managing agent for T r returns ‘one level up’ to report this event to appropriate managing agent.

Observe that the above scheme should be performed in such a way that each subtree T r ‘receives’ just enough agents needed for its exploration and not more. This includes one managing agent for the subtree itself, the agents performing the extended DFS traversal of T r and the agents needed for recursive calls, if any. This is regulated by introducing the agents slowly at the global root so that, within predefined time intervals new agents appear at the global root and are directed gradually by managing agents precisely to the subtree for which the current extended DFS traversal is performed. The time intervals are set up in such a way that if an exploration of a particular subtree is completed then this information has enough time to be carried by the managing agent to the one residing one level up. In this way the flow of agents to a particular subtree is stopped and redirected to the next one supplying the exact amount of agents needed for each of the subtrees. Intuitively, the measurement of time is used indirectly as a communication tool: if a managing agent does not receive for a given amount of time a signal that a recursive call to a subtree is completed, then this means that the exploration of that subtree is not completed and more agents are needed to finish it — hence another agent will be sent to that subtree.

Now we give a detailed description of the modifications to the exploration strategy described in Section 4.1 so that it is valid for agents communicating locally. At the beginning of exploration (i.e., when GCTE ε is called for a tree T), one distinguished agent is selected to be constantly present at the root r 0 of the entire tree T. This agent is called the managing agent for T. Similarly, whenever a recursive call of GCTE ε is made for any input node r, the first agent that arrives at r is the managing agent for T r and it stays at r until the entire subtree T r is explored.

Extension of Step 1 of GCTE ε

Once all 6 members of the i-th team are present at the root r of a subtree for which the extended DFS traversal is performed, the i-th team operates exactly as described in Section 4.1. Recall that the i-th team finishes its work with one of its agents being at the root. The beginning of the operation of the (i + 1)-th team is postponed until exactly 6 new agents, each with energy b, appear at r. Then, the (i + 1)-th team resumes the extended DFS traversal. We note that the agents forming each team will arrive at r directly from the global root of the tree and this will become clear after description of the extension of Step 3 of GCTE ε .

Extension of Step 3 of GCTE ε

For this part we need to describe how a recursive call is performed by an instance of GCTE ε . This includes two actions: initiating the call and receiving information that a recursive call is completed, i.e., that the exploration of the subtree for which the call was conducted is finished. Suppose that an instance of GCTE ε with input r and b performs a call for a subtree rooted at a node r i (see Fig. 1). Recall that the managing agent for T r , denoted by A(r) is present at r during exploration of T r . First, A(r) waits until a new agent, denoted by A(r i ), appears at r and after it arrives, agent A(r i ) is sent to r i and it becomes the managing agent for \(T_{r_{i}}\). Then, the algorithm sends each agent arriving at r to the node r i until the agent A(r i ) returns to r. This completes the recursive call for r i and A(r i ) stays idle at r indefinitely (and will not play any role in the remaining part of the exploration). Then, the next recursive call, if any, that needs to be done is performed. The information about the current status of each recursive call made by the instance of GCTE ε (r,b), is maintained by A(r), the managing agent for T r , and once all recursive calls are completed this managing agent returns to the node that is the ancestor of r from which the instance of GCTE ε (r,b) was called.

Distribution of Agents at the Global Root

Note that the above description defines the operation of agents for each instance of GCTE ε except for the managing agent at the global root r 0 for the first call to GCTE ε . The managing agent at the global root has all agents at its disposal from the first step and does not need to wait for the arrival of an agent. Therefore we introduce an artificial delay denoted by d(ε) as defined below. The d(ε) is an integer and it will be understood that the agents will appear at the global root r in time intervals of length d(ε). This time interval is defined as

$$ d(\varepsilon)= 8B. $$
(2)

We will prove later that this delay is sufficient for our strategy.

The exploration strategy modified as above is called LCTE ε (Local Communication Tree Exploration). We now prove that LCTE ε works correctly in the local communication model.

Lemma 6

For 0 < ε < 1/4, Algorithm LCTE ε correctly explores any tree T using local communication between agents.

Proof

The correctness of the extension of Step 1 follows from Lemma 5. To ensure that the extension of Step 3 is correct we need to argue that if an instance of GCTE ε called for a node r performs a recursive call for a descendant v, then the information that the subtree T v is explored (and hence that the corresponding call for v is completed) eventually arrives at r. Let b be the available energy that is part of the input for the call to LCTE ε at r. By definition, B − b is the distance of r from the global root and

$$b=b_{i}=\left\lfloor (1-\varepsilon)^{i-1}B \right\rfloor$$

for some i ≥ 1. We calculate the total distance that the managing agent for T v , denoted by A(v), needs to traverse. The agent A(v) traverses the path from the global root to v at distance B −⌊(1 − ε)i B⌋ and the path from v to the root r. The latter path is of length

$$\left( B-\left\lfloor (1-\varepsilon)^{i}B \right\rfloor\right)-\left( B-\left\lfloor (1-\varepsilon)^{i-1}B \right\rfloor\right) = \left\lfloor{(1-\varepsilon)^{i-1}B}\right\rfloor-\left\lfloor{(1-\varepsilon)^{i}B}\right\rfloor.$$

Thus, the total distance traversed by A(v) is

$$B - \left\lfloor (1-\varepsilon)^{i-1}B \right\rfloor +\left\lfloor (1-\varepsilon)^{i-1}B \right\rfloor- \left\lfloor (1-\varepsilon)^{i}B \right\rfloor \leq B $$

□

Theorem 3

Algorithm LCTE ε explores T using at most O(log B) ⋅ O P T agents.

Proof

By Lemma 6, the tree is correctly explored by LCTE ε and hence it is enough to count the number of agents used in this exploration strategy. Denote by m(ε) the overall number of managing agents used by the procedure and denote by e(ε) the overall number of agents used to perform all extended DFS traversals. Also, denote by a(ε) the number of remaining agents used by the algorithm.

As shown in Lemma 5, the algorithm uses 6 times the number of agents used by algorithm GCTE ε (see Theorem 2) for all extended DFS traversals. Therefore we have

$$ e(\varepsilon)\leq \frac{24}{\left( \frac{1}{2} - \varepsilon\right)} \cdot \log_{\left( \frac{1}{1-\varepsilon}\right)} B \cdot{OPT_{}} . $$
(3)

We now bound m(ε). Note that there exists exactly one managing agent for each node for which LCTE ε is called. Whenever two recursive calls to LCTE ε are performed for two nodes r i and r j at the same level, the subtrees \(T_{r_{i}}\) and \(T_{r_{j}}\) are independent due to Lemma 1. Thus any exploration strategy (offline or not) would use at least two distinct agents for exploring \(T_{r_{i}}\) and \(T_{r_{j}}\). This proves, that if an instance of LCTE ε performs recursive calls for nodes r 1,…,r p , then at least p agents need to be used in any exploration strategy for the subtrees \(T_{r_{1}},\ldots ,T_{r_{p}}\). Thus, the overall number of managing agents for subtrees rooted at the same level is at most O P T. Therefore, by Lemma 2,

$$ m(\varepsilon)\leq \log_{\left( \frac{1}{1-\varepsilon}\right)} B\cdot {OPT_{}} . $$
(4)

We finally prove that

$$ a(\varepsilon)= 0. $$
(5)

To that end take two agents A and A ′ that arrive at the global root of the tree separated by time interval d(ε), i.e, A and A ′ are two consecutive agents ‘deployed’ at the global root. We will show that A∉a(ε) ⇒ A ′∉a(ε). Suppose that A becomes the managing agent for some subtree T r or \(A=\if !j! A_{i} \else A_{i}^{j}\fi \), where j < 5 or the i-th team is not the last one used for the extended DFS traversal of T r . In any of these cases, each managing agent visited by A ′ is present at the same node as when visited by A, and hence A ′ arrives at r and becomes a member of some team performing the extended DFS traversal of T r . Now let us consider the remaining case when \(A=\if !5! A_{k} \else A_{k}^{5}\fi \) and k-th team is the last one used for the extended DFS traversal of T r . We need to consider two sub-cases depending on whether the subtree T r is big (requiring more than one level of recursion) or small (only a single level).

In the first sub-case, when T r is big, a recursive call is performed for some node r 1 ∈ T r during the execution of LCTE ε (r,b) at the node r that we consider. Then, A ′ arrives at r and is directed to r 1 and becomes the managing agent for \(T_{r_{1}}\).

In the second sub-case, no recursive call is performed by the instance of LCTE ε called for r. Thus, there exists a sequence of nodes v 0 = r,v 1,…,v p such that an instance of LCTE ε was called for v i by an instance of LCTE ε called for v i+ 1, i ∈{0,…,p − 1}, and the subtree \(T_{v_{p-1}}\) is explored, or equivalently, none of the instances of LCTE ε called for v 0,…,v p− 1 is going to perform another recursive call. By the formulation of the algorithm, the managing agent for v i returns to v i+ 1 once the managing agent for v i− 1 returned to v i for each i ∈{1,…,p − 1}. Moreover, the exploration of \(T_{r}=T_{v_{0}}\) is completed and the managing agent for T r recognizes this fact and goes to v 1. Thus, the information about completion of the extended DFS traversal of \(T_{v_{p-1}}\) arrives at v p after a number of time units at most the depth of \(T_{v_{p}}\), which is bounded by B. We bound the number of time units that elapsed since A has been deployed at the global root till the time it reported completion of the extended DFS traversal of T r . This is at most B, which accounts the time needed to reach r from the global root, plus the time of operation of the k-th team of the extended DFS traversal, to which A belongs, which is at most

$$6 b \leq 6B.$$

Therefore, by (2), the managing agent for \(T_{v_{p}}\) learns about the completion of the exploration of \(T_{v_{p-1}}\) prior to the event when A ′ is deployed at the global root and hence prior to the arrival of A ′ at v p . In particular, if v p is the global root and the exploration of the entire tree is completed, then this fact is known before A ′ is deployed at the global root. This proves (5).

Since the overall number of agents used by LCTE ε is e(ε) + m(ε) + a(ε), the theorem follows from (3), (4) and (5). □

5 Competitive Ratio of Online Exploration

We now show a lower bound on the competitive ratio of any online exploration algorithm in the local communication model. The following result implies that the competitive ratio of algorithm LCTE ε is asymptotically optimal.

Theorem 4

Any online exploration algorithm for exploring a tree of depth D = B − 1has a worst case competitive ratio of at least Ω(log B).

Proof

We consider the family of trees which consist of a line of length D − 1, where one endpoint of the line is the root and the other endpoint is connected to the center of a star with p leaves. Thus all the p leaves of the tree are at distance D = B − 1 from the root and there is only one node at distance D − 1. An offline algorithm would use exactly p agents for exploring this tree. An online algorithm for exploring this tree can be of two types: We say an algorithm is type-1 if during the algorithm there is no transfer of information from the node at depth D − 1 to the root; All other algorithms are of type-2. First notice that if an algorithm of type-1, uses k agents for exploration then k is independent of p, since p remains unknown to the root. Thus, by taking p > k, we can make the algorithm fail. So we need to consider only type-2 algorithms where information from the node at depth D − 1 is transferred to the root. Any agent visiting this node has at most B − (D − 1) = 2 units of energy remaining, so it can return back to depth D − 3 = B − 4. Similarly, any agent visiting the node at depth B − 4 can return back to depth B − 8, and so on. Thus, at least Ω(log B) agents are needed to carry the information from the node at depth D − 1 back to the root. So any type-2 algorithm would use at least Ω(log B) agents. By taking p = 1, we get a competitive ratio of Ω(log B) for any such algorithm. □

6 Conclusions

We studied the problem of exploring a tree with a team of agents, each of which can traverse at most B edges. We gave matching lower and upper bound of Θ(log B) on the competitive ratio of the cost of tree exploration. Unlike previous algorithms for energy constrained agents, the agents in our algorithm do not necessarily return to the root after exploration. This fact allows us to explore trees of larger depth (at least twice more compared to [2, 7]). However our algorithm can be still used e.g. to collect information from the leaves of a tree, or to search for a resource and bring it back to the root, since there is always a transfer of information from the leaves to the root. On the other hand if all agents were required to return to root, then it may be possible to have more competitive algorithms. Note that the lower bound of Ω(log B) on the competitive ratio of exploration holds only in the local communication model. An interesting question is whether more efficient algorithms are possible for tree exploration in the global communication model. Another open question is the cost of exploring general graphs or other specific classes of graphs.