## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
While the negative move heuristic always improved solver performance, we also considered the case where this heuristic is supplemented with the additional heuristic of weakly preferring moves that are on a shortest path. This weak preference heuristic is encoded in the rules at Lines 1 and 4 of Listing 18, and we use the abbreviation MVH(P) to indicate its use. #### 5.2.3 Move Routing Acyclicity Checking

As discussed in Section 4.4.4 the time-based path acyclicity checking of the base routing rules (Listing 11) can be supplemented by the addition of explicit acyclicity checking of the moves along a path. We considered both the pure ASP encoding using reachability (Listing 12) and using the edge/3 encoding (Listing 13). For the pure ASP reachability encoding we use the abbreviation MVR and for the edge/3 based encoding we use the abbreviation MVA. We report on the performance of these two additional move acyclicity checkers separately as well as working together. #### 5.2.4 Pallet Replacement Time Bound

Finally, we report on the use of the pallet replacement time bound as a mechanism for providing a quality guarantee that can be computed quickly while providing a good-enough solution. Because determining an appropriate pallet replacement time bound is specific to a specific warehouse and problem configuration we do not perform these experiments on the synthetically generated graphs of the crafted benchmark, and only perform these experiments for the warehouse graphs of the industry benchmark. For most of the warehouse graphs we considered a pallet replacement time bound of 300 s and 400 s, however for the largest warehouse (map5) we used a bound of 800 s because some instances were simply not satisfiable given the lower bounds. #### 5.2.5 A Note on Step Encoding Horizons

The step-based encoding requires a horizon value that fixes the maximum length of any robot walk. A balance needs to be found between a horizon that is large enough to admit solutions and a horizon that is not so large that the problem instance fails to ground. Since the size of the ground instance is directly correlated with the horizon, and we conjectured that grounding would be a major hurdle for the step-based encoding, ideally we would want to use the smallest horizon possible for each problem instance. However, determining this value for each problem instance would have been impractical, potentially needing to run each problem instance 100 s or 1000 s of times with varying horizon values to find this minimum value. As a compromise we used the results generated by the solution of the path-based encoding. While the path-based encoding does not require a walk horizon, a horizon value can be calculated from each solution, using the translation described in Section 4.4.7. To approximate the minimum horizon we used the horizon value calculated when minimizing the makespan for the path-based encoding (with a 2 h time limit). Note, there are two caveats to this approach. Firstly, most problem instances timed out after 2 h so the makespans found were not necessarily minimal. Secondly, the horizon value calculated from a minimal makespan solution does not guarantee that the horizon itself will be minimal. A solution with a minimal makespan solves the problem in the shortest amount of time, but this does not guarantee that the maximum number of steps required for all robots is also minimal. Nevertheless the two are loosely correlated so such a solution will provide a horizon that is close to the minimal. Unfortunately, as we shall see in the next section (Section 5.3), despite our best efforts most problem instances simply failed to ground. While it is conceivable that there could be some cases where our approximation of the horizon was not good enough, however, considering that even for the basic path-based encoding there where 55 instances that failed to ground, finding a better horizon for just a few more instances of the step-based encoding would always be of limited use.