## 3 Warehouse Delivery Problem
### Formalization
#### 3.1.2 Solution Formulation
For each robot \(r\in R\), there is exactly one projection \(\vec{p}\in P\) of the timed walk \(f_{W}(r)\) onto the task sequence \(f_{T}(r)\);
2. For any distinct tasks \(t,t^{\prime}\in T\) such that \((t,t^{\prime})\in D\) and corresponding projection points \((v,a,e)\) in some \(\vec{p}\in P\) and \((v^{\prime},a^{\prime},e^{\prime})\) in some \(\vec{p^{\prime}}\in P\), we have \(a+\kappa\leq a^{\prime}\);
3. For any distinct tasks \(t,t^{\prime}\in T\) such that \((t,t^{\prime})\in D\) and \(f_{D}((t,t^{\prime}))=\textit{deliver}\), there is some projection \(\vec{p}\in P\) with \(\vec{p}=\langle p_{0}\ldots,p_{i},p_{i+1},\ldots,p_{m}\rangle\) such that \(p_{i}\) is the projection point of \(t\) in \(\vec{p}\) and \(p_{i+1}\) is the projection point of \(t^{\prime}\) in \(\vec{p}\) for \(0\leq i\leq m\). The first item in this definition ensures that every robot is able to execute the tasks that it was assigned, and in the assigned order. The second and third items ensure that the dependencies of these assigned tasks are met. In particular, no task can begin to be executed before its dependencies have finished executing, and matching pickup and putdown tasks are executed by the same robot one immediately after the other. Note that Condition (14) implicitly assumes that a task is executed as soon as its assigned robot arrives at the vertex of the corresponding projection point. The rationale for this assumption is simple: When a task's dependencies have been satisfied then the assigned robot should execute that task as soon as it is able to do so. To see that the robot assignment given in Tables 1 and 2 is executable, we start with noting that the sequences in Table 3 are indeed projections of the two timed walks in Table 2 on the corresponding task assignments in Table 1. For (14), we observe that each putdown task follows several seconds after its preceding pickup task; the same applies to the two wait dependencies, namely \((t_{1},t_{4})\) and \((t_{5},t_{8})\). Furthermore, finally, all deliver dependencies are mapped onto consecutive projection points in Table 3, namely, \(t_{1}\) directly precedes \(t_{2}\), \(t_{3}\) precedes \(t_{4}\), etc., establishing (15). **Solutions**. A pair \(((f_{T},f_{W}),P)\) of a robot assignment \((f_{T},f_{W})\) and a set of projections \(P\subseteq 2^{\mathcal{P}_{W}}\) is a _solution_ to a warehouse delivery problem with warehouse \(W=(V,E,f_{E},C,R,f_{H},f_{S})\) and a task execution graph (\(T\),\(D\),\(f_{D}\),\(f_{V}\)) iff it is complete, non-overlap-ping, starting, homing, collision-free, and executable wrt. \(P\). \begin{table}
\begin{tabular}{r c c c c c} \hline \hline \(r_{1}\) & \((l_{1},80,90)\) & \(t_{1}\) & \((\text{pickup})\) & \(r_{2}\) & \((l_{2},45,55)\) & \(t_{5}\) & \((\text{pickup})\) \\  & \((s_{1},190,200)\) & \(t_{2}\) & \((\text{putdown})\) & \((s_{2},135,145)\) & \(t_{6}\) & \((\text{putdown})\) \\  & \((p_{1},255,265)\) & \(t_{3}\) & \((\text{pickup})\) & \((p_{1},190,200)\) & \(t_{7}\) & \((\text{pickup})\) \\  & \((l_{1},315,325)\) & \(t_{4}\) & \((\text{putdown})\) & \((l_{2},328,338)\) & \(t_{8}\) & \((\text{putdown})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Projections of timed walks of robot \(r_{1}\) and \(r_{2}\) in Table 2 onto their tasks sequences in Table 1.  
Note that there might be several sets of projections for which a robot assignment is executable. For instance, a robot might move several times over a target vertex and remain there long enough to execute the assigned task. The projections clarify at which specific visit the task is executed. In our running example, the robot assignment given in Tables 1 and 2, together with the projections in Table 3, constitute a solution to the warehouse delivery problem, consisting of the warehouse in Figure 1 and the task execution graph in Figure 2.  
**Observations**. In order to complete the description of our approach we now list some observations that are a direct result of our formalization.