## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
\begin{table}
\begin{tabular}{l l l l l l} \hline \hline \multirow{2}{*}{**Map**} & \multirow{2}{*}{\begin{tabular}{c} **Num** \\ **Robots** \\ \end{tabular} } & \multicolumn{2}{c}{\begin{tabular}{c} **Num Jobs** \\ **(4 Tasks** \\ \end{tabular} } & \multicolumn{2}{c}{\begin{tabular}{c} **Time** \\ **Out** \\ \end{tabular} } & \multicolumn{2}{c}{\
\begin{tabular}{c} **Makespan** \\ **(seconds)** \\ \end{tabular} } & \multicolumn{2}{c}{
\begin{tabular}{c} **Runtime** \\ **Mean/Geo.Mean** \\ \end{tabular} } \\ \hline
**map0** & 4 & 5 & 0 & 352/363 & 1.20/1.20 \\  & & 10 & 0 & 842/855 & 6.00/6.05 \\  & & 15 & 0 & 1308/1311 & 16.24/16.42 \\ \hline
**map1** & 3 & 5 & 0 & 1184/1198 & 2.33/2.33 \\  & & 10 & 0 & 2554/2581 & 10.38/10.42 \\  & & 15 & 0 & 3331/3343 & 28.32/28.45 \\  & & 20 & 0 & 4805/4830 & 71.32/72.55 \\  & & 30 & 0 & 6779/6848 & 308.39/327.74 \\  & & 40 & 0 & 8790/8805 & 797.99/852.29 \\ \hline
**map2** & 11 & 5 & 0 & 1038/1052 & 6.52/6.53 \\  & & 10 & 0 & 2450/2463 & 25.63/26.03 \\  & & 15 & 0 & 3870/3873 & 84.45/85.26 \\  & & 20 & 0 & 4808/4814 & 232.87/424.04 \\  & & 30 & 1 & 7322/7343 & 973.34/1059.79 \\  & & 40 & 5 & -/- & 1800.00/1800.00 \\ \hline
**map3** & 7 & 5 & 0 & 301/308 & 2.12/2.13 \\  & & 10 & 0 & 573/580 & 7.90/7.92 \\  & & 15 & 0 & 1045/1050 & 23.44/23.61 \\  & & 20 & 0 & 1361/1371 & 51.77/52.46 \\  & & 30 & 0 & 2321/2342 & 222.00/227.06 \\ \hline
**map4** & 2 & 5 & 0 & 341/354 & 1.11/1.12 \\  & & 10 & 0 & 656/662 & 5.16/5.18 \\  & & 15 & 0 & 926/934 & 15.68/15.78 \\  & & 20 & 0 & 1228/1236 & 39.64/40.35 \\ \hline
**map5** & 20 & 5 & 0 & 3520/3561 & 11.25/11.26 \\  & & 10 & 0 & 8008/8079 & 30.52/32.35 \\  & & 15 & 0 & 13,467/13.517 & 121.64/138.78 \\  & & 20 & 0 & 18,469/18,537 & 617.26/734.76 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Comparison of runtimes and makespans by map and and number of tasks for the high performance path encoding variant Path + LB + Corr(S) + TskAcyc(W) + MVA + MvR + MVH. of combinatorics for the encoding. Consequently, as the size of each robot increases, the number of vertex conflicts will also increase, and will result in an increase in the number of conflict constraints. This in turn increases in the size of the ground program. One would also expect an increase in the solver runtime as these additional constraints need to be resolved. Because of the variation in the vertex densities of the different maps it is worth looking at these result separately for the individual maps. Table 8 shows that as the diameter of the robots increase we start to see problems as more and more instances fail to ground. Furthermore, as expected, the solver runtimes increase with timeouts becoming more frequent. Note, in Table 8 the runtime results only apply to problem instances that were able to be grounded. So the reason that the runtimes may not increase as much as expected can simply be a result of the harder problems failing to ground and therefore not being included in the aggregate solver runtime values. These results highlight the importance of choosing the correct level of granularity for a warehouse graph. A balance needs to be found between the need to plan high-level robot tasks and plan relatively low-level movements that might be better handled by a low-level robot motion controller. For example, while map3 (Figure 6) is relatively small in size it has a very dense set of vertices. While this allows for fine-grained path planning for the robots, it also results in large clusters of conflicting vertices that need to be resolved. Finally, while reducing the density of vertices in the graph is one possibility for dealing with an increase in conflicting vertices, a second option would be to separate the conflict handling from the path routing. In particular, it would be possible to group vertices into larger blocks where conflict handling is performed on the blocks rather than on the individual vertices. We discuss this possibility further in Section 7.