## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
* If \(\{\mathtt{proj}(t,s),\mathtt{assign}(r,t),\mathtt{walk}(r,s,v),\mathtt{dl}( \mathtt{arrive}(r,s),\mathtt{d}),\mathtt{dl}(\mathtt{exit}(r,s),e)\}\subseteq X\), \(\{\mathtt{proj}(t^{\prime},s^{\prime}),\mathtt{assign}(r,t^{\prime}),\mathtt{ walk}(r,s^{\prime},v^{\prime})\}\subseteq X\) and \(\{\mathtt{dl}(\mathtt{arrive}(r,s^{\prime}),a^{\prime}),\mathtt{dl}(\mathtt{exit} (r,s^{\prime}),e^{\prime})\}\subseteq X\)such that \(s<s^{\prime}\), and there exists no \(\{\texttt{proj}(t^{\prime\prime},s^{\prime\prime})\,,\texttt{assign}(r,t^{\prime \prime}),\texttt{walk}(r,s^{\prime\prime},v^{\prime\prime})\}\subseteq X\) such that \(s<s^{\prime\prime}<s^{\prime}\) and \(v=f_{V}(t)\), \(v^{\prime}=f_{V}(t^{\prime})\), \(v^{\prime\prime}=f_{V}(t^{\prime\prime})\), then \(\vec{p}=\langle\ldots,(v,a,e),(v^{\prime},a^{\prime},e^{\prime}),\ldots\rangle\) for some \(\vec{p}\in P^{X}\). * If \(\{\texttt{proj}(t,s),\texttt{assign}(r,t),\texttt{walk}(r,s,v),\texttt{dl}( \texttt{arrive}(r,s),a),\texttt{dl}(\texttt{exit}(r,s),e)\}\subseteq X\), and there exists no \(\{\texttt{proj}(t^{\prime},s^{\prime}),\texttt{assign}(r,t^{\prime}), \texttt{walk}(r,s^{\prime},v^{\prime})\}\subseteq X\) such that \(s^{\prime}<s\) and \(v=f_{V}(t)\), \(v^{\prime}=f_{V}(t^{\prime})\), then \(\vec{p}=\langle(v,a,e),\ldots\rangle\) for some \(\vec{p}\in P^{X}\). * If \(\{\texttt{proj}(t,s),\texttt{assign}(r,t),\texttt{walk}(r,s,v),\texttt{dl}( \texttt{arrive}(r,s),a),\texttt{dl}(\texttt{exit}(r,s),e)\}\subseteq X\), and there exists no \(\{\texttt{proj}(t^{\prime},s^{\prime}),\texttt{assign}(r,t^{\prime}), \texttt{walk}(r,s^{\prime},v^{\prime})\}\subseteq X\) such that \(s<s^{\prime}\) and \(v=f_{V}(t)\), \(v^{\prime}=f_{V}(t^{\prime})\), then \(\vec{p}=\langle\ldots,(v,a,e)\rangle\) for some \(\vec{p}\in P^{X}\). We start with Condition 13. First, Line 5 of Listing 8 ensures a non-timed candidate projection on the robots' walks. That is, for each robot \(r\) and (timed) walk \(\vec{w}\in f_{W}^{X}(r)\), we have a projection \(\vec{p}\) in \(P^{X}\) such that \((v,a,e)\in\vec{p}\) only if \((v,a,e)\in\vec{w}\) for any \(v=f_{V}(t)\) and task \(t\in f_{T}^{X}(r)\). Then, Line 6 of Listing 8 accounts for the correct order within the projections in view of the task sequences. In detail, for any robot \(r\) with task sequence \(f_{T}^{X}(r)=\langle\ldots,t,t^{\prime},\ldots\rangle\), we have a corresponding projection \(\langle\ldots,(v,a,e),(v^{\prime},a^{\prime},e^{\prime}),\ldots\rangle\) in \(P^{X}\) with \(v=f_{V}(t)\) and \(v^{\prime}=f_{V}(t^{\prime})\). Finally, Line 18 of Listing 9 ensures that a robot stays on the projection point of a given task for at least its execution time \(\kappa\). Specifically, for every robot \(r\), task \(t\in f_{T}^{X}(r)\) and corresponding projection \(\vec{p}\in P^{X}\), we have a projection point \((v,a,e)\in\vec{p}\) satisfying \(a+\kappa\leq e\). Condition 14 is addressed in Line 20 of Listing 9 by ensuring that the task execution time is respected for tasks in a dependency. Note that we only need to pose a timing constraint if interdependable tasks are assigned to different robots. If we have two distinct tasks \(t,t^{\prime}\) with \((t,t^{\prime})\in f_{D}\) and \(t,t^{\prime}\in f_{T}^{X}(r)\) for some robot \(r\), then there is a projection \(\vec{p}\) in \(P^{X}\) of form \(\vec{p}=\langle\ldots,(v,a,e),\ldots,(v^{\prime},a^{\prime},e^{\prime}),\ldots\rangle\), comprising the projection points \((v,a,e)\) and \((v^{\prime},a^{\prime},e^{\prime})\) of \(t\) and \(t^{\prime}\) in the given order, respectively. This is the case, first, because \(f_{T}^{X}(r)\) respects dependencies by construction, and second, as established above, there has to be a projection on the walk of \(r\) in \(P^{X}\). Then, by the properties of projections, we have that \(a+\kappa\leq e\leq a^{\prime}\), and thus \(a\leq a^{\prime}-\kappa\).