## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
The combination of the constraints from Lines 1 to 11 ensures that the obtained robot arrival and exit times result in a timed walk that is feasible in the given warehouse. We now turn to the remaining constraints that address the timing of conflict resolution and task execution. Condition 12 requires the robot assignment to be collision-free. Line 14 addresses this condition by imposing a difference constraint to ensure that two robots visiting conflicting vertices at certain steps do not collide. That is, whenever a robot \(r\) has been granted precedence over another robot \(r^{\prime}\) by virtue of before(\((r,s)\,,(r^{\prime},s^{\prime})\)), then the relationship arrive(\(r,s+1\))\(\leq\) arrive(\(r^{\prime},s^{\prime}\)) must hold. This relationship ensures that \(r^{\prime}\) enters the conflict zone only once \(r\) has already moved outside the conflict zone to its next vertex (this vertex is guaranteed to exist due to Line 9 in Listing 7). To further elaborate on how the difference constraint satisfies the collision-free condition, we start by noting that the above robot-step pairs, \((r,s)\) and \((r^{\prime},s^{\prime})\), are associated with vertices \(v,v^{\prime}\), and \(v^{\prime\prime}\) by atoms ( see Listing 7). walk(\(r,s,v\)), walk(\(r^{\prime},s^{\prime},v^{\prime}\)), as well as walk(\(r,s+1,v^{\prime\prime}\)). The actual conflict concerns route points \((v,a,e)\in f_{W}(r)\) and \((v^{\prime},a^{\prime},e^{\prime})\in f_{W}(r^{\prime})\) with \((v,v^{\prime})\in\mathbb{C}\). Given walk \(f_{W}(r)=\langle\ldots,(v,a,e),(v^{\prime\prime},a^{\prime\prime},e^{\prime \prime}),\ldots\rangle\), the difference constraint in Line 14 requires \(a^{\prime\prime}\leq a^{\prime}\). Furthermore, the non-zero travel time of \(r\) between \(v\) and \(v^{\prime\prime}\) implies that \(a<a^{\prime}\), namely that \(r\) arrives at \(s\) before \(r^{\prime}\) arrives at \(s^{\prime}\). Note that if we also have conflict \((v^{\prime},v^{\prime\prime})\in C\), the integrity constraints in Lines 11 and 14 in Listing 7 ensure that before(\((r,s+1)\,,(r^{\prime},s^{\prime})\)) also holds. This then further delays the entry of \(r^{\prime}\) to vertex \(v^{\prime}\) in the same manner as above. Moving on to task timing, the rule at Line 18 enforces that when a robot arrives at a vertex to execute a given task, it must remain at that vertex long enough for it to actually complete the task's execution. To this end, the constraint arrive(\(r,s\))\(+\kappa\leq\) exit(\(r,s\)) is imposed whenever assign(\(r,t\)) and proj(\(t,s\)) hold. However, note, by virtue of Line 5 in Listing 8, whenever assign(\(r,t\)) and proj(\(t,s\)) hold, then we also conclude walk(\(r,s,v\)) for vertex \(v=f_{V}(t)\). So we know that robot \(r\) is at the correct location \(v\), and time step \(s\), required to execute the task \(t\) to which it has been assigned. So the difference constraint at Line 18 simply ensures that the duration of \(r\)'s stay at \(v\) does indeed satisfy the minimum timing requirement given by the definition of a projection (i.e., Condition 1). Together with the earlier result in Section 4.3.3 that Listing 8 satisfies the qualitative aspect of Condition 13, the result of this timing constraint is to satisfy the quantitative aspect of this same condition. Finally, Line 20 establishes the satisfaction of Condition 14 by enforcing the timing constraint that arrive(\(r,s\))\(+\kappa\leq\) arrive(\(r^{\prime},s^{\prime}\)) for any two robots \(r,r^{\prime}\) that are assigned, respectively, to the two tasks \(t\) and \(t^{\prime}\) in a pair of dependent tasks, where \(s\) and \(s^{\prime}\) are the projections points corresponding to these two tasks. Similarly to the explanation for Line 14, the rule's precondition implies the existence of the two route points \((v,a,e)\in f_{W}(r)\) and \((v^{\prime},a^{\prime},e^{\prime})\in f_{W}(r^{\prime})\) that serve as the projection points \(s\) and \(s^{\prime}\) of the tasks \(t\) and \(t^{\prime}\).