## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
The basic path-based encoding grounded a majority of these instances, even though it subsequently failed to solve them within the time limit. #### 5.3.2 Comparison of Path-Based Encoding Variants

Table 5 compares variants of the path-based encoding with a view to identifying the variant with the best overall performance. We only consider variants with some form of move corridor restriction, since Table 4 shows that variants without a move corridor had many problem instances that failed to ground. As these configurations were able to ground all problem instances, therefore, on top of the runtime results, we only report the number of problem instances that were solved versus the number that timed out. \begin{table}
\begin{tabular}{l l l l l l} \hline \hline \multirow{2}{*}{**Configuration**} & \multirow{2}{*}{**Benchmark**} & \multicolumn{2}{c}{**SAT/**} & \multirow{2}{*}{**Time**} & \multirow{2}{*}{**Mem**} & \multirow{2}{*}{**Mean/Geo.Mean**} \\  & & & **UNSKINWAN** & & & **(Excl. Mem Out)** \\ \hline Step Basic & Crafted & 10/2/38 & 4 & 34 & 43.46/472.92 \\  & Industry & 0/0/215 & 0 & 215 & -/- \\  & Total & 10/2/253 & 4 & 249 & 43.46/472.92 \\ \hline Step TskAcyc(W) & Crafted & 10/2/38 & 4 & 34 & 45.36/474.61 \\  & Industry & 0/0/215 & 0 & 215 & -/- \\  & Total & 10/2/253 & 4 & 249 & 45.36/474.61 \\ \hline Path Basic & Crafted & 35/2/13 & 13 & 0 & 20.48/527.56 \\  & Industry & 0/0/215 & 169 & 46 & 1800.00/1800.00 \\  & Total & 35/2/228 & 182 & 46 & 647.81/1509.49 \\ \hline Path + LB + Corr(NS) & Crafted & 37/2/11 & 11 & 0 & 6.88/400.84 \\  & Industry & 100/0/115 & 115 & 0 & 338.08/1069.35 \\  & Total & 137/2/126 & 126 & 0 & 162.12/943.22 \\ \hline Path + LB + Corr(S) & Crafted & 48/2/0 & 0 & 0 & 1.07/5.13 \\ + TskAcyc(W) & Industry & 209/0/6 & 6 & 0 & 22.41/124.47 \\ + MvA + MvR + MvH & Total & 257/2/6 & 6 & 0 & 12.63/101.95 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparison of the step encoding and path encodings, from basic to most performant variants. Note, means and geometric means of runtimes apply to grounded instances only. \begin{table}
\begin{tabular}{l l l l l} \hline \hline \multirow{2}{*}{**Configuration**} & \multirow{2}{*}{**Benchmark**} & \multirow{2}{*}{**Solved**} & \multicolumn{2}{c}{**Time**} & \multicolumn{2}{c}{**Runtime**} \\  & & & **Out** & **Mean/Geo.Mean** \\ \hline Path + LB + Corr(NS) & Crafted & 39 & 11 & 6.88/400.84 \\  & Industry & 100 & 115 & 338.08/1069.35 \\  & Total & 139 & 126 & 162.12/943.22 \\ \hline Path + LB + Corr(S) & Crafted & 43 & 7 & 3.20/265.02 \\  & Industry & 138 & 77 & 79.12/704.28 \\  & Total & 181 & 84 & 43.20/621.40 \\ \hline Path + LB + Corr(NS) & Crafted & 50 & 0 & 1.37/5.34 \\ + MvH & Industry & 209 & 6 & 32.43/171.51 \\  & Total & 259 & 6 & 17.86/140.16 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Comparison of path encoding variants with/without basic move heuristic and differing in move corridor types and task/move acyclicity checks. Note, all problem instances grounded successfully so we only report on whether the problem was solvable or whether it timed out. There are a number of interesting behaviors that can be observed from these results. Firstly, the most dramatic improvement in performance comes from the use of the basic move heuristic, where the move heuristic sets move/3 facts that are not on the shortest path to false. Without the move heuristic the number of timeouts was 126 and 84 for the non-strict and strict move corridors, respectively. This dropped dramatically to 6 and 9, respectively, with the addition of the move heuristic. The second interesting behavior comes from the difference between the strict and non-strict move corridors. Using the strict corridor over the non-strict corridor typically improves solver performance for most cases, but results in timeouts for a few cases. Adding task acyclicity detection and move acyclicity detection with a reachability encoding was able to solve more cases.