## 3 Warehouse Delivery Problem
### Formalization
#### 3.1.2 Solution Formulation
Both are traversed three times by robot \(r_{1}\), namely, at time points \(175\), \(215\), and \(225\), and four times by \(r_{2}\) at \(120\), \(160\), \(253\), and \(263\), respectively. We have to ensure that none of the twelve putative encounters leads to a collision. As an example, consider route point \((w_{5},215,215)\) of robot \(r_{1}\) along with the putatively colliding route point \((w_{6},120,120)\) of \(r_{2}\), and let \(r_{1},r_{2}\) slip in the roles of \(r\) and \(r^{\prime}\) in (12). Here, we apply Condition 12b since \(r_{2}\) arrives earlier at \(w_{6}\) than \(r_{1}\) at \(w_{5}\). Now, we have to make sure that \(r_{2}\) has already reached its next (non-crucial) waypoint before \(r_{1}\) enters \(w_{5}\). The next route point of \(r_{2}\) is \((s_{2},135,145)\) and thus \(r_{2}\) is already passed \(s_{2}\) before \(r_{1}\) even arrives at \(w_{5}\). Hence, there is no collision at stake. Having specified criteria to ensure that all tasks are assigned, that robots always return to their home base, and that robots do not collide, we still need to ensure that the tasks assigned to these robots can actually be completed. For simplicity, we assume that the time to perform the pickup and putdown actions is fixed. We fix this value to \(10\) s and refer to it with the symbol \(\kappa\). This could be extended to a more complex setting, such as where the action time is dependent on the weight of the load, etc. In order to do this, we first introduce a supporting definition that maps assigned tasks to the timed walk of a robot. _Projection_. Given a warehouse (\(V\),\(E\),\(f_{E}\),\(C\),\(R\),\(f_{H}\),\(f_{S}\)), a task execution graph (\(T\),\(D\),\(f_{D}\),\(f_{V}\)), a timed walk \(\vec{w}\in\mathcal{W}_{W}\), and a task sequence \(\vec{t}=\langle t_{0},\dots,t_{n}\rangle\), we define a sequence \(\vec{v}=\langle(v_{0},a_{0},e_{0}),\dots,(v_{n},a_{n},e_{n})\rangle\) as a _projection_ of \(\vec{w}\) onto \(\vec{t}\) iff 1. \(\vec{v}\sqsubseteq\vec{w}\), that is, \(\vec{v}\) is a subsequence of \(\vec{w}\); and for every \(i\in\{0,\dots,n\}\) 2. \(v_{i}=f_{V}(t_{i})\); and 1. \(a_{i}+\kappa\leq e_{i}\). A non-timed projection of a (non-timed) walk onto a task sequence is a sequence of vertices satisfying the above definition but dropping arrival and exit times along with Condition 1. The essential idea behind a projection is to provide a mechanism to ensure that a robot is in fact capable of executing the tasks that it has been assigned. It must visit each task's \(t_{i}\) action execution vertex, viz. \(f_{V}(t_{i})\), in the correct order and for long enough in order to execute the required action. For a projection \(\vec{p}\) onto task sequence \(\vec{t}\), each route point \((v_{i},a_{i},e_{i})\in\vec{p}\) is referred to as the _projection point_ of the corresponding task \(t_{i}\in\vec{t}\). We call \(\mathcal{P}_{\mathcal{W}_{W}}\) the set of all possible projections onto all possible timed walks. For illustration, we give in Table 3 the projections of the timed walks of robot \(r_{1}\) and \(r_{2}\) in Table 2 onto their tasks sequences in Table 1.  
To see this, we observe that both are subsequences of the entire walks and also maintain the original order among the projection points. Furthermore, the locations in the projection points correspond to the tasks' action execution vertices given in (1) and (2). For instance, \(f_{V}(t_{1})=l_{1}\) and \(f_{V}(t_{8})=l_{2}\). Finally, the layover time of each robot at each location respects the time to perform the pickup and putdown actions. The concept of a projection and projection points can be applied to defining criteria for ensuring that the set of robots execute all their required tasks in an order that satisfies the task execution graph. **Executable Assignment**. Given a warehouse (\(V\),\(E\),\(f_{E}\),\(C\),\(R\),\(f_{H}\),\(f_{S}\)) and a task execution graph (\(T\),\(D\),\(f_{D}\),\(f_{V}\)), we define a robot assignment \((f_{T},f_{W})\) as _executable_ wrt. a set of projections \(P\) iff:  
1.