## 4 Data Foraging-Oriented Reconnaissance
### Proposed Algorithm  
At the beginning of the mission, there is no information about the sampling area. After Hextille \(H\) with radius \(h_{ex}\) is selected, we construct a DFG \(G_{h}\) of the sampling area and explore it. Once the MDF has visited a region in \(G_{h}\), the MDF stamps the region. The objective of reconnaissance is to expand the knowledge of the sampling area while visiting nodes based on their priority. In order to explore new nodes getting to farthest and less stamped nodes is preferred. It is necessary to satisfy Restrictions 2, 3 and 4 (see Section 4.4). The following rules are:  
**Rule 1**. : _Given the remaining energy \(e_{u}\) of an MDF, the set of potential nodes \(L_{r}\), the minimum number of steps \(e_{h}\) to traverse the DFG \(G_{h}\), a region \(r\), its neighbors \(V_{r}\), the next potential node \(r^{\prime}\) to be visited by an MDF is a \(r^{\prime}\in L_{r}\subseteq V_{r}\). The set \(L_{r}\) is determined by:_  
* _(a) if_ \(e_{u}>e_{h}\)_,_ \(L_{r}\leftarrow\{r^{\prime}\in V_{r}:d(r^{\prime},\zeta)\geq d(r^{\prime\prime },\zeta)\forall r^{\prime\prime}\in V_{r}\}\)_,_
* _(b) otherwise,_ \(L_{r}\leftarrow\{r^{\prime}\in V_{r}:d(r^{\prime},\zeta)\leq d(r^{\prime\prime },\zeta)\forall r^{\prime\prime}\in V_{r}\}\)_._  
**Rule 2**. : _Given a region \(r\) and its neighbors \(L_{r}\), an MDF can only move if \(\exists r^{\prime}\in L_{r}\) such that the estimated remaining energy between \(r\) and \(r^{\prime}\), \(\Pi\geq 0\) (see Property 5)._  
The rules are implemented in the algorithm. The main function of the algorithm is shown in Algorithm 1. The detailed description of the DFORE algorithm is presented in Appendix D.  
```
1:function[List<Cell>,int]exploration(int \(e_{u}\), List<Cell>area)
2:int \(time\gets 0\)
3:Cell \(r\gets 0\)
4:while\(e_{u}\geq 0\)do
5:if\((e_{u}-2)-e_{base^{-}}\geq 0\)then
6: Cell \(r^{\prime}\leftarrow\) choose(neighbors(\(r\))) /* See Appendix D */
7:else
8: Cell \(r^{\prime}\leftarrow\) traceback(neighbors(\(r\)), \(e_{u}\)) /* See Appendix D */
9:endif
10:\(e_{u}^{\prime}\leftarrow e_{u}-1\)
11:\(r^{\prime}.stamp\gets r^{\prime}.stamp+1\)
12:\(time^{\prime}\leftarrow time+1\)
13:\(r\gets r^{\prime}\)
14:endwhile
15:\(List<Cell>foodCells\leftarrow\) getFoodCells(\(area\)) /* See Appendix D */
16:return\([foodCells,time]\)
17:endfunction
```  
**Algorithm 1** Exploration algorithm. Next, the DFORE algorithm is described. If the environment has not been visited completely, the reconnaissance continues its execution while the MDF has enough number of steps to continueexploring the DFG. In order to choose the next node to be visited, it is necessary to verify whether the MDF has enough remaining steps to proceed (function EXPLORATION line 4, Rule 2) or needs to return (function EXPLORATION line 6). If the MDF can proceed, the following heuristics are applied. First, the MDF selects the adjacent nodes with the largest distance to the base station \(\zeta\) (see Rule 1a). Second, the MDF chooses the nodes with fewer stamps (function choose see Appendix D line 6). Third, if all conditions hold, i.e., every node has the same distance to the base station and the nodes have the same number of stamps, then the MDF chooses a node at random with a uniform distribution (function choose see Appendix D line 7). After moving to the last node, the MDF must return to recharge energy. Thus, when the MDF cannot proceed, then it will begin to choose nodes which are nearer to the base station (see Rule 1b); therefore, the MDF will return to the base station satisfying Restriction 4 (see Section 4.4). See Figure 5 for the following example. All red nodes are stamped, the number of stamps is represented by the intensity of the color. The MDF is currently on node 0. At step 0, the MDF chooses node 1 since it has only one choice. At step 1, the MDF chooses node 13, which is not stamped. Node 19 with less stamps is chosen at step 2. The MDF chooses randomly node 15 at step 3. In step 4, the MDF chooses node at random.