## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
Similarly to the step-based encoding, difference constraints over integer variables are used to derive the arrival and exit times at vertices. More specifically, variables arrive(\(p\),\(v\)) and exit(\(p\),\(v\)) represent the arrival and exit times, respectively, at a vertex \(v\) for path \(p\). Note that, in contrast to the step-based encoding, we no longer have a step associated with variable names. This has the advantage that variables describing arrival and exit times on target vertices for tasks are known apriori, and the number of possible variables scales with the number of paths and vertices instead of the number of robots and chosen horizon. The drawback, as already discussed, is that there is no mechanism to distinguish multiple visits to a vertex, and therefore, there cannot be cyclic movement within a single path. The structure of the scheduling for the path-based encoding is very similar to the scheduling for the step-based encoding, detailed in Listing 4.3.4. We first create a valid schedule for the individual paths, then handle conflict resolution between paths, and finally address task executions and dependencies. Line 1 reuses predicate visit/2, described in Section 4.4.5, to derive difference constraints stating that the exit time at each vertex on a path is greater than or equal to the arrival time. Line 2 ensures that the schedule of each path respects durations stemming from the warehouse layout. That is, whenever there is a move from \(v\) to \(v^{\prime}\) on path \(p\), then a difference constraint enforces that exit(\(p\),\(v\)) + \(f_{E}(v,v^{\prime})\leq\texttt{arrive}(p,v^{\prime})\). The two rules in Lines 4 to 7 deal with the first vertex on the first path in a path sequence and set the corresponding arrival time to zero. Line 8 deals with scheduling of the transition between paths. This is, for a path \(p^{\prime}\) that immediately follows path \(p\) in a path sequence, such that the target vertex of \(p\) is \(v\), then we stipulate that exit(\(p\),\(v\)) \(\leq\texttt{arrive}(p^{\prime},v)\). Note that here the exit time of path \(p\) at vertex \(v\) should be understood as the end of the assigned robot's execution of \(p\). It does not indicate that the robot itself has left the vertex, only that \(p\) is finished and that any corresponding task has been executed. Similarly, the arrival time of path \(p^{\prime}\) at vertex \(v\) marks the beginning of the execution of path \(p\) by the assigned robot, and not the robot's physical arrival at vertex \(v\). Analogously to the step-based encoding, Lines 10-12 add difference constraints to set the variable bound to the makespan, and align it with the final paths' exit times. Notethat this is made possible by selecting the home vertex of each robot, because the last path in a path sequence is always identified by the name of a robot, and the last vertex of this path is the home vertex of that robot. Naming the homing path with the identifier of the corresponding robot has the added advantage that home/2 is known statically so these atoms is dissolved during grounding. Line 14 deals with conflict resolution. Whenever we have before((\(p\),\(v\)),(\(p^{\prime}\),\(v^{\prime}\))), we add a difference constraint expressing the condition that arrive(\(p\),\(v^{\prime\prime}\)) \(\leq\) arrive(\(p^{\prime}\),\(v^{\prime}\)), where \(v^{\prime\prime}\) is the vertex immediately following vertex \(v\) along path \(p\). Intuitively, this constraint ensures that the robot following path \(p\) has moved on to the vertex past the conflict before the robot tasked with \(p^{\prime}\) may arrive at the vertex in conflict. This removes any possibility of a collision. There are a number of points worth noting here. Firstly, if vertex \(v^{\prime\prime}\) is also in conflict with \(v^{\prime}\), then the fact before((\(p\),\(v^{\prime\prime}\)),(\(p^{\prime}\),\(v^{\prime}\))) would also be derived.