## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
Otherwise, if we have two distinct tasks \(t,t^{\prime}\) with \((t,t^{\prime})\in f_{D}\) and two distinct robots \(r,t^{\prime}\) with \(t\in f_{T}^{X}(r)\) and \(t^{\prime}\in f_{T}^{X}(r^{\prime})\), we pose the timing constraint \(a-a^{\prime}\leq-\kappa\) which implies \(a\leq a^{\prime}-\kappa\) on the projection points \((v,a,e)\) and \((v^{\prime},a^{\prime},e^{\prime})\) of tasks \(t\) and \(t^{\prime}\), respectively. To address Condition 15, Line 6 of Listing 2 makes sure that tasks in a delivery dependency are assigned to the same task sequence, and Line 10 in the same listing that they are assigned to the same robot. Then, Line 6 of Listing 8 demands their successive execution. Note that it is enough to require that there exists a projection such that for two adjacent tasks in a task sequence the latter one is executed at a strictly larger step number. This is because a task may have at most one successor and predecessor in a task sequence due to Lines 4 and 14 of Listing 2. That means, if such a projection exists, the tasks in a task sequence are strictly ordered by the step they are executed in. Of course, this also holds for deliver dependencies. In detail, for distinct tasks \(t,t^{\prime}\) with \(f_{D}((t,t^{\prime}))=\mathit{deliver}\), there exists a projection \(\vec{p}\) in \(P^{X}\) such that \(\vec{p}=\langle\ldots,p,p^{\prime},\ldots\rangle\) and \(p\) and \(p^{\prime}\) are the projection points of \(t\) and \(t^{\prime}\), respectively. ### Path-Based Encoding

In this section, we present an encoding to the warehouse delivery problem that solves the routing and scheduling of robots through a series of discrete acyclic paths. This approach contrasts to the step-based encoding, presented in the previous section, that explicitly assigns timed walks to individual robots. While a timed walk pertains to the entire movement of a single robot, from its starting vertex through to its final arrival at its home vertex, we use the graph theoretic notion of (acyclic) paths at a more fine-grained level of abstraction. In particular, in our encoding we generate an individual path for each task. The start of the path is the vertex of the assigned robot at the point that it starts fulfilling that task, and the path's destination is the task's execution vertex. A path is also generated for each robot that needs to return to its home location. For any robot assigned a sequence of tasks, the corresponding path sequence is constructed so that the starting and ending vertices of each path align with the task sequence. Consequently, the series of paths are generated so as to fulfill all tasks and return all robots to their home stations. For example, the walk of robot \(r_{1}\) is given by the sequence in Table 2; where the robot visits a series of vertices starting and finishing at its home location \(h_{1}\). The actual task execution for tasks \(t_{1}\) through to \(t_{4}\) is determined by Table 3 showing the projection of the walk onto \(r_{1}\)'s task sequence. In contrast, for the path-based approach we view this walk as being composed of a sequence of five distinct paths; the first path \(h_{1},w_{3},w_{2},w_{1},l_{1}\) is associated with task \(t_{1}\), the second \(l_{1},w_{1},w_{5},s_{1}\) is associated with task \(t_{2}\), and the final path \(l_{1},w_{1},w_{2},w_{3},h_{1}\) is associated with robot \(r_{1}\)'s journey back to its home vertex. Note, that while each individual path is acyclic, nevertheless \(r_{1}\) still visits some vertices multiple times, but it does so only when fulfilling different paths. #### 4.4.1 Advantages and Limitations

The path-based encoding has a number of key advantages over the step-based encoding. In the first place, it does not require a step horizon; the step horizon is instance specific and has to be determined on a case-by-case basis. The lack of a horizon also means that there is no step counter for tracking each robot's walk through the warehouse, which has important consequences for scalability and the size of the ground instances produced by the encoding.