## 3 Warehouse Delivery Problem
### Formalization
#### 3.1.1 Problem Formulation  
**Warehouse**. We define a _warehouse_ as a tuple (\(V\),\(F_{E}\),\(C\),\(R\),\(f_{H}\),\(f_{S}\)) such that:  
Figure 1: A graph representing a simple warehouse with loading bay vertices \(l_{1}\) and \(l_{2}\), an empty pallet area \(p_{1}\), storage vertices \(s_{1},s_{2}\), waypoint vertices \(w_{1},\ldots,w_{8}\), and home vertices \(h_{1},h_{2}\) for robots \(r_{1},r_{2}\), respectively. Edge labels represent the minimal travel times between vertices (in seconds). * \((V,E)\) is a connected directed graph, fixing the warehouse layout;
* \(f_{E}:E\rightarrow\mathbb{N}\) assigns the minimum travel time along an edge;
* \(C\subseteq V\times V\) is a reflexive and symmetric conflict relation over vertices \(V\);
* \(R\) is a set of robots;
* \(f_{H}:R\to V\) assigns a home docking vertex to each robot; and
* \(f_{S}:R\to V\) assigns a starting vertex to each robot. The warehouse formalization simply provides for the physical layout of the environment, in terms of a weighted graph \((V,E,f_{E})\), as well as parameters for the robots. Vertices represent locations and weighted edges capture their connectivity. To avoid robots colliding while traveling through the warehouse, we keep track of locations that can hold only a single robot at a time. We formalize this in terms of a _conflict relation_ over the vertices of the graph (for simplicity, we assume a planar warehouse graph and refrain from adding conflicts among edges). It is worth noting that while our examples only consider robots starting at their respective docking stations, the formalization itself allows for the separation of these locations. This generalizes the formalism, making it applicable to an online setting that potentially requires re-planning and pre-existing partial assignments. We can now consider the example scenario in light of this formalism. The set of vertices and edges in the graph are specified by Figure 1, for example \(s_{1}\in V\) and \((w_{1},l_{1})\in E\). The travel times between connected vertices, encoded in function \(f_{E}\), are similarly taken directly from the figure, for example \(f_{E}((w_{1},w_{2}))=20\) and \(f_{E}((w_{7},w_{8}))=30\). Finally, the robot home docking stations and starting locations are determined by the functions \(f_{H}\) and \(f_{S}\), respectively, and are assigned based on the figure:  
\[f_{H}(r_{1})=f_{S}(r_{1})=h_{1},\qquad f_{H}(r_{2})=f_{S}(r_{2})=h_{2}\]  
Next, the conflict relation ensures that only a single robot at a time can access a vertex or a group of vertices that are physically close together. This relation is reflexive (and symmetric), so all vertices form a conflict with themselves, but we also need to add the storage locations and their connected vertices:  
\[\{(s_{1},s_{2}),(s_{2},s_{1}),(w_{5},w_{6}),(w_{6},w_{5})\}\subseteq C\]  
The above warehouse formalization and examples encodes the static information for a given configuration. We now consider the dynamic information, in particular, the set of tasks that the robots must perform and the relationship between these tasks. We model tasks at a fine-grained level, where a task is associated with an action that needs to be executed at a specific vertex. Because we are dealing with a delivery problem, each task is either a _pickup_ or a _putdown_ action. Hence, a robot that needs to transport an item from one location to another is performing two distinct tasks, a pickup at the first location followed by a putdown at the second. In order to capture the relationship between tasks, we adopt the notion of a _task execution graph_, restricting the order in which tasks can be executed as well as capturing the dependency relation between tasks. For our example scenario, we need the task graph to capture two key pieces of information. Firstly, it needs to encode the pairs of pickup-putdown tasks that are part of the same delivery, and secondly, it needs to specify when a replacement empty pallet is to be delivered to a loading bay. **Task Execution Graph**.