## 3 Materials and Methods
### Validation Methodology for a Main Instance of the Generic Planning Problem (IGPP)
#### 3.3.1 Scene Initial States for a Main Instance of the Generic Planning Problem (IGPP)
A sub-set \(\tilde{f}_{ips,i}\) with \(n_{ps}\) process steps to be carried out need not necessarily be determined with respect to the original start-process-steps set \(st_{ps}\). Such a sub-set can also be defined relative  
Figure 8: Dependency graph (DG) for a simple IGPP. to other start-process-steps sets \(\tilde{st}_{ps,i}\). The sets \(\tilde{st}_{ps,i}\) are obtained, for example, when an error occurs during execution and a new plan from a new initial state is required. Figure 8 presents an example of start-process-steps and finish-process-steps sets. For the original initial state \(s_{0}\), \(\tilde{st}_{ps,1}=st_{ps}\) holds, while for the original goals set \(g\), \(fi_{ps}\) holds as in Equation (4). We assume that our planner cannot find a plan in the given timeout period if the corresponding planning problem has more than three process steps goals. Therefore, \(n_{ps}=3\), and the new set of finish process steps can be defined as \(\tilde{f}_{ip_{ps},1}=\{item1\_step1,item1\_step2,item3\_step1\}\). We also assume that during the execution of _item1_step2_, an error occurs and a new plan must be generated. The new initial state \(s_{0,2}\) is different from the original initial state \(s_{0}\) because the first step has already been executed. In this case, \(\tilde{st}_{ps,2}=\{item1\_step2\}\) holds. The set of finish process steps \(\tilde{f}_{ip_{ps},2}=fi_{ps}\) relative to the new start-process-steps set then contains all process steps, while the first process step is already executed. The planner should find a plan that does not modify the status of the first process step and guarantees that the other \(n_{ps}=3\) will also be reached. This is a simplified example, but it shows that a complete validation method must consider all possible initial states and sets of goals for the given main IGPP corresponding to further situational IGPPs. Thus, all start-process-steps sets \(\tilde{st}_{ps,i}\) and finish-process-steps sets \(\tilde{f}_{ip_{s},i}\), where the latter sets have \(n_{ps}\) elements more than the former, must be considered in the validation method. The technicalities of determining the sets \(\tilde{st}_{ps,i}\) and \(\tilde{f}_{ps,j}\), and their formulation in PDDL are presented in the following. Many initial states can be derived for a main IGPP. However, not all such initial states are allowed. To determine the set of start-process-steps sets \(ST_{ps}=\{\tilde{st}_{ps,i}\}\) for the allowed initial states, the information contained in the DG is used. An allowed start-process-steps set \(\tilde{st}_{ps,i}\) represents the information encoded in the leaves of a special dependency sub-graph DsG of the DG. **Definition 5**. : _A dependency sub-graph \(DsG=(\tilde{V},\tilde{E},\tilde{\phi})\) is a sub-graph of a DG \(=(\tilde{V},\tilde{E},\tilde{\phi})\) that contain all vertices \(v\in\tilde{V}\) of all direct paths \(dp\) between the start \(\in\tilde{V}\) vertex and its leaves. More formally, \(\tilde{V}=\{x\in\tilde{V}|x\in\{dp\},dp=(start,\ldots,y)\) for \(y\in\tilde{V}\wedge\text{children}(y)=\emptyset\}\); \(\tilde{E}=\{(x,y)|(x,y)\in\tilde{E}\wedge x,y\in\tilde{V}\}\); \(\tilde{\phi}:\tilde{E}\rightarrow\{(x,y)|(x,y)\in\tilde{V}^{2},x\
eq y\}\)._  
This condition ensures that all process steps prior to those from the leaves of a DsG are already finished. For the example from Figure 8, if _item1_step2_ should be part of an initial state, the vertices _item1_step1_ and _item1_step2_ must be vertices in the corresponding DsG. Algorithm 1 presents the steps for computing the DsGs of the DG that correspond to the given main IGPP. In a first step, the set of dependency sub-graphs is initialized with the first DsG containing only one element: the _start_ vertex (line 1). In addition, the vertices of the input DG are ordered according to the breadth-first search (bfs) approach (line 2). The main _for_ loop (lines 3-16) iterates over all bfs-ordered vertices.