# A Pathfinding Problem for Fork-Join Directed Acyclic Graphs with Unknown Edge Length
## 3 Estimate and Characteristic Vector  
For conservative strategies, the current knowledge about the graph is represented by a pair \(F=(F_{K},F_{U})\), where \(F_{K}\) is the set of all pairs \(\langle(v_{i},v_{j}),w(v_{i},v_{j})\rangle\) with \((v_{i},v_{j})\in E_{K}\), and \(F_{U}\) is the set of all pairs \(\langle(v_{i},v_{j}),\tilde{w}(v_{i},v_{j})\rangle\) with \((v_{i},v_{j})\in E_{U}\). We call such \(F\) an estimate of \(G\). Let \(\mathcal{F}\) denote the set of all estimates. A strategy for PFJUEL is formally defined as a mapping \(\mathcal{S}\) from \(\mathcal{F}\) to \(E_{U}\times\mathbb{N}\) (this definition of strategies means that strategies are deterministic; i.e., any strategy gives the same response to the same estimate). Based on the previous results on oracle calls, strategy \(\mathcal{S}\) gives the next edge in \(E_{U}\) and nonnegative integer \(c\) for which the oracle is called. The current lower bound of the path length is given by the sum of \(\tilde{w}(v_{i},v_{j})\) for all edges \((v_{i},v_{j})\) on the path. We call this the estimated length of the path. When a shortest goal path is found, the estimate has to satisfy the following requirements in order to guarantee the correctness of the result. **Definition 3**. : _An estimate is called terminal if the following two conditions hold:_  
1. _All the edges on a shortest goal path_ \(\pi^{*}\) _are in_ \(E_{K}\)_;_
2. _For any goal path other than_ \(\pi^{*}\)_, its estimated length is no less than the length of_ \(\pi^{*}\)_._  
In what follows, oracle calls that return \"no\" are called fail calls and oracle calls that return \"yes\" are called success calls. Given an estimate \(F\), we define a vector \(\#_{F}=[a_{0},a_{1},\cdots,a_{s}]\) called the characteristic vector of \(F\), where each \(a_{k}\) is the number of edges with \(\hat{v}_{F}(v_{i},v_{j})=k+1\), and \(s\) is the largest integer such that \(a_{s}\
eq 0\). In conservative strategies, the number of fail calls \(\text{search}_{c}(\cdot,\cdot)\) is given by \(\sum_{i=c}^{s}a_{i}\), because if \(\text{search}_{c}(v_{i},v_{j})\) fails, then \(\text{search}_{c}(v_{i},v_{j})\) fails for all \(0\leq c^{\prime}<c\). To define the optimality of strategies, we introduce a lexicographical order \(\preceq\) on the set of characteristic vectors. For two characteristic vectors \(\#_{F_{1}}=[a_{0},a_{1},\cdots,a_{s}]\) and \(\#_{F_{2}}=[b_{0},b_{1},\cdots,b_{1}]\), we write \(\#_{F_{1}}\prec\#_{F_{2}}\) if (i) \(s<t\) or (ii) \(s=t\) and \(a_{j}<b_{j}\) holds for \(j=\max\{i\in\{0,1,\cdots,s\}\,|\,\,a_{i}\
eq b_{i}\}\), and define \(\#_{F_{1}}\preceq\#_{F_{2}}\) to be \(\#_{F_{1}}\prec\#_{F_{2}}\) or \(\#_{F_{1}}=\#_{F_{2}}\). **Definition 4**. : _A terminal estimate \(F\) is called optimal if for any other terminal estimate \(F^{\prime}\), \(\#_{F}\preceq\#_{F^{\prime}}\) holds._  
Figure 2: A tree and the constructed FJ-DAG. The characteristic vectors do not reflect the number of success calls, since the lower bound is not updated for any success call. In the conservative strategies, however, every success call \(\mathit{search}_{c}(v_{i},v_{j})\) for \(c=w(v_{i},v_{j})\) is preceded by a fail call \(\mathit{search}_{c-1}(v_{i},v_{j})\). This means that the number of success calls \(\mathit{search}_{c}(\cdot,\cdot)\) is no greater than the number of fail calls \(\mathit{search}_{c-1}(\cdot,\cdot)\). For this reason, the optimality defined above can be a measure of the total computational cost. We have assumed that the cost of calling oracles is dominant in the total computation time and it becomes exponentially larger as the length \(c\) increases. Since we give no exact computational cost of oracle calls, the optimality of a strategy should be defined by the number of oracle calls. Under the assumption of the computational cost of oracle calls, the above definition is reasonable. In our previous paper, we initially intended to use the same evaluation measure as that used in this paper.