## 3 Warehouse Delivery Problem
### Formalization
#### 3.1.1 Problem Formulation
We define a _task execution graph_ as a tuple \((T,D,f_{D},f_{V})\) such that:  
* \((T,D)\) is a directed acyclic graph, specifying dependencies among tasks \(T\);
* \(f_{D}:D\rightarrow\{\mathit{deliver},\mathit{wait}\}\) specifies a type for each dependency; and
* \(f_{V}:T\to V\) assigns to each task a location for the task's action execution. Applying this formalism to the example scenario, we consider four delivery tasks; where items are delivered from the loading bays \(l_{1}\) and \(l_{2}\) to the storage locations \(s_{1}\) and \(s_{2}\), respectively, and replacement pallets are delivered from the empty pallet area to the loading bays (cf. Figure 2). Note that in the formalization, tasks are simply abstract entities, and the property of one task being a pickup task while another being a putdown task is not an attribute of the task entity itself. Rather, this property is encoded in the tasks' dependencies. For example, because there is a _deliver_ relation from task \(t_{1}\) to task \(t_{2}\), \(t_{1}\) must be a pickup task and \(t_{2}\) must be its corresponding putdown task. Functionally, tasks in a _deliver_ dependency have to be executed by the same robot, while tasks in a _wait_ dependency do not. However, both comprise the idea that one task must be executed before another. So the _wait_ relation from task \(t_{1}\) to task \(t_{4}\) tells us that \(t_{1}\)'s full pallet pickup task must be executed before \(t_{4}\)'s replacement empty pallet putdown task, but it does not prescribe which robots execute these tasks. These tasks could be executed by the same robot or by different robots. The graphical representation of Figure 2 corresponds to the following formal representation of the task execution graph consisting of tasks \(T=\{t_{1},\dots,t_{8}\}\) with the task dependencies establishing the executability relationship between the different tasks:  
\[D=\{(t_{1},t_{2}),(t_{3},t_{4}),(t_{1},t_{4}),(t_{5},t_{6}),(t_{7},t_{8}),(t_ {5},t_{8})\}\]  
The dependency type mapping \(f_{D}\) establishes that two tasks are part of the same delivery and that one task must wait for another to finish:  
\[f_{D}=\{(t_{1},t_{2}) \mapsto\textit{deliver},(t_{3},t_{4})\mapsto\textit{deliver},(t_ {1},t_{4})\mapsto\textit{wait},\] \[(t_{5},t_{6}) \mapsto\textit{deliver},(t_{7},t_{8})\mapsto\textit{deliver},(t_ {5},t_{8})\mapsto\textit{wait}\}\]  
The _deliver_ label associated with the edge \((t_{1},t_{2})\) establishes that \(t_{1}\) is a pickup task and \(t_{2}\) is its corresponding putdown task. In contrast, the _wait_ label associated with \((t_{1},t_{4})\) establishes that the action of \(t_{1}\) must be executed before the action of \(t_{4}\). Finally, the assignment of a vertex to each task establishes the task's _action execution vertex_; that is, the location where the pickup or putdown action occurs:  
\[f_{V}=\{t_{1} \mapsto l_{1},t_{2}\mapsto s_{1},t_{3}\mapsto p_{1},t_{4}\mapsto l _{1}, \tag{1}\] \[t_{5} \mapsto l_{2},t_{6}\mapsto s_{2},t_{7}\mapsto p_{1},t_{8}\mapsto l _{2}\} \tag{2}\]  
**Warehouse delivery problem**. We can now combine the two concepts, of a warehouse and a task execution graph, into a single problem description. We define a _warehouse delivery problem_ as the pairing of a warehouse and a task execution graph.