## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
Interestingly for the crafted benchmark adding the move acyclicity reachability encoding allowed the one problematic instance to be solved. This is a particularly interesting case, because, unlike the industry benchmark problems which are large in size, the crafted problems are relatively small. Consequently it is useful to examine this problematic instance (Figure 7) in more detail to understand the difference between the strict and non-strict corridor versions. The densely connected grid structure, meant that the strict corridor definition, which requires that corridor vertices be no further from the goal vertex than a shortest path vertex, failed to define an adequate corridor beyond the shortest paths themselves. Furthermore, \begin{table}
\begin{tabular}{l l c c c} \hline \hline
**Configuration** & **Benchmark** & **Solved** & \
\begin{tabular}{c} **Time** \\ **Out** \\ \end{tabular} &
\begin{tabular}{c} **Runtime** \\ **Mean/Geo.Mean** \\ \end{tabular} \\ \hline Path + LB + Corr(S) & Crafted & 49 & 1 & 1.21/39.59 \\ + MvH & Industry & 207 & 8 & 24.79/148.78 \\  & Total & 256 & 9 & 14.03/128.18 \\ \hline Path + LB + Corr(NS) & Crafted & 50 & 0 & 1.30/13.94 \\ + MvH + TsKacyC(W) & Industry & 210 & 5 & 30.67/154.98 \\  & Total & 260 & 5 & 16.90/128.37 \\ \hline Path + LB + Corr(S) & Crafted & 49 & 1 & 1.16/38.85 \\ + MvH + TsKacyC(W) & Industry & 210 & 5 & 22.05/116.99 \\  & Total & 259 & 6 & 12.65/102.25 \\ \hline Path + LB + Corr(S) & Crafted & 49 & 1 & 1.17/38.75 \\ + MvH + TsKacyC(W) & Industry & 210 & 5 & 21.58/114.00 \\ + MvA & Total & 259 & 6 & 12.44/99.80 \\ \hline Path + LB + Corr(S) & Crafted & 50 & 0 & 1.10/26.06 \\ + MvH + TsKacyC(W) & Industry & 210 & 5 & 22.50/128.37 \\ + MvR & Total & 260 & 5 & 12.74/109.07 \\ \hline Path + LB + Corr(NS) & Crafted & 50 & 0 & 1.40/6.40 \\ + MvH + TsKacyC(W) & Industry & 210 & 5 & 30.93/141.50 \\ + MvA + MvR & Total & 260 & 5 & 17.25/116.01 \\ \hline Path + LB + Corr(S) & Crafted & 50 & 0 & 1.07/5.13 \\ + MvH + TsKacyC(W) & Industry & 209 & 6 & 22.41/124.47 \\ + MvA + MvR & Total & 259 & 6 & 12.63/101.95 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: _Cont._

Figure 7: The crafted problem instance that is difficult for the strict move corridor definition. there was significant clustering for the task source vertices and task destination vertices. The combination of this clustering and the pure shortest path corridors resulted in the search for a conflict free route for each task's path being dominated by the potential vertex conflicts. Without the explicit task and move acyclicity checking, this resulted in a heavy burden on the difference logic solver to resolve the very fine grained timing required to avoid conflicts. In contrast the non-strict corridor allows all vertices connected to a shortest path vertex to be part of the corridor, so in this case a wider corridor could be generated. This in turn provides greater flexibility in the allowable moves of the robots in order to avoid conflicts, and less heavy lifting is required by the difference logic solver. The final observation from Table 5 is that there is no clear winner between the top path-based encoding variants with #edge-based task acyclicity checking and both #edge-based and reachability based move acyclicity detection. Using a non-strict corridor definition does allow more instances to be solved, in this case a single instance, but increases the solver runtime. The best choice of performance enhancements for a given scenario will therefore depend on the specific warehouse graph. For the sake of this paper, we have chosen the strict corridor version as our candidate winner. It had marginally, but also consistently, better runtimes than the best non-strict corridor based encoding for both the crafted and industry benchmarks. #### 5.3.3 Comparison of Move Heuristics

As discussed in Section \"Domain Heuristics for Moves\" we consider two variants of the move heuristic. The first move heuristic we consider preferences setting moves that are not on the shortest-path to false.