# A Pathfinding Problem for Fork-Join Directed Acyclic Graphs with Unknown Edge Length
## 1 Introduction  
In a previous paper by the author [1], a pathfinding problem for directed trees is studied under the following situation: each edge has a nonnegative integer length, but the length is unknown in advance and should be found by a procedure whose computational cost becomes exponentially larger as the length increases. Such a situation arises in an operation synthesis problem for reconfigurable cloud computing systems [2; 3]. This problem is described as follows. A typical reconfigurable cloud computing system consists of multiple physical servers interconnected via network switches. Servers may have different computing resources such as CPU, memory, and hard disk drives. Multiple virtual machines are running under the virtual machine monitor in each server, and application software runs on each virtual machine. Such an arrangement of virtual machines, operating systems, and application software on physical servers is called a configuration. Then, the problem is to find a sequence of operations that leads the system from the initial configuration to a given goal configuration. Since the problem becomes harder as the length of the operation sequence becomes longer, implementing subgoals is proposed to shorten the total computation time. The number of necessary operations between two subgoals is not known in advance and can be known by applying some search procedure. This situation is formulated as the above graph problem. In this paper, the same problem is studied for a more general class of graphs called fork-join directed acyclic graphs. We call this problem PFJUEL (Pathfinding in an FJ-DAG with Unknown Edge Length). There is a remaining problem in the previous paper, which is the optimality criterion used for evaluating the solution method. The optimality criterion used in this paper is stronger than that in the previous paper and is more appropriate for real applications. Moreover, the argument to derive the optimality becomes clearer for this generalized class of graphs. Solution methods to the problem involve a procedure whereby the next action to be taken is determined by the current knowledge of the target. We call this type of procedure a strategy. Such a problem has been studied as the planning problem in artificial intelligence, and there are a variety of algorithms in this area. Typical algorithms are the \(A^{*}\) algorithm [4] and its variants such as [5; 6; 7]. In the research field of graph algorithms, many algorithms have been proposed for solving shortest path problem in varieties of situations. Well-knownalgorithms for finding a shortest path, such as [PERSON]'s algorithm and the Bellman-Ford algorithm, cannot be applied because the length of each edge is unknown in advance. There exist studies on graphs with uncertainty. Algorithms to solve such problems with uncertainty include online algorithms [8]. The Canadian traveler problem [9; 10] is one of these algorithms. In the Canadian traveler problem, whether each edge \((v_{i},v_{j})\) is available or not is known only when the vertex \(v_{i}\) is visited. Solution methods to this problem are strategies, and the cost of a strategy is defined as the sum of the lengths of all edges traversed. Online shortest path problems for graphs with uncertainty are also studied [11], and there are many applications such as route finding in transit networks [12]. In these problems, the weight of each edge can change in an arbitrary way. Such a situation occurs in real transit networks because of traffic jams. There are several differences between PFJUEL and the existing online graph problems with uncertainty. Although most of the graph problems with uncertainty are defined in stochastic domain [8; 13; 14; 15], PFJUEL is defined in a fully deterministic way. Moreover, the edge length does not change (but is not known in advance). In some online shortest path problems, the existence of an agent that traverses the network is assumed. The agent makes decisions based on the information around the agent and its history.