## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
While some variants apply to both the step-based and path-based encodings, the majority of variants rely on pre-computed shortest path information and therefore only apply to the path-based encoding. Finally, we also consider the application specific variant of adding pallet replacement time constraints, which we also only apply to the path-based encoding for solving the industry benchmarks. #### 5.2.1 Basic and Task Acyclicity Variants

For the step-based and path-based encodings we tested the basic encodings as well as the variants with added task acyclicity checking. To be clear, all variants produce correct solutions but the basic variants have no enhancements to improve performance. Both the step-based and path-based encodings support the addition of task sequence acyclicity checking, using the #edge directive, shown in Listing 4. Additionally, we also added the acyclicity check of Listing 5 to enforce task wait dependencies. As outlined in Section 4.2 the task acyclicity check can also be encoded in pure ASP using a reachability encoding (Listing 3). However, in all our experiments the reachability version for detecting task acyclicity under-performed the #edge variant, so we do not report on these results here. In our results tables we use the abbreviation TskAcyc(W) to indicate the use of task acyclicity checking with wait dependencies. #### 5.2.2 Shortest-Path Enhancements

As the path-based encoding treats the notion of a _path_ as a primitive, this enables many performance enhancements based on using pre-calculated shortest path information (see Section 4.5). For each problem instance, the shortest path information was pre-calculated using the FloydWarshal algorithm [15]. For a fast Python implementation of FloydWarshal see [[https://gist.github.com/mosco/11178777](https://gist.github.com/mosco/11178777)]([https://gist.github.com/mosco/11178777](https://gist.github.com/mosco/11178777)) (accessed on 1 February 2022). Note, here we calculated the shortest path information separately for each problem instance. However, in a production environment this information would typically to be calculated only once for each warehouse graph, and then filtered based on the particular tasks that make up the problem instance. The first use of the shortest-path information that we evaluated was for propagating path length lower-bounds (Listing 17). We use the abbreviation LB to indicate the use of lower-bound propagation in a configuration. Because lower-bound propagation showed only positive performance results we used it as the basis for all subsequent configurations. Corridor Restrictions

To foreshadow the presentation of results, the path-based encoding can ground many more problem instances that are simply beyond the reach of the step-based encoding. Nevertheless grounding was still problematic for the path-based encoding when the paths were unconstrained. In order to reduce the grounding we restricted the allowable moves of the robots to a corridor constructed around the shortest-path information, as shown in Listings 19 and 20. We considered both the strict and non-strict corridor definitions, where the non-strict version simply drops the N' <= N restriction to the rules in Listing 19. For the strict corridor definition we use the abbreviation Corr(S) and for the non-strict version we use the abbreviation Corr(NS). We consider both versions because there are some few cases where the strict definition makes the problem harder to solve without additional performance enhancements. Unarguably, the most important performance enhancement we consider is the addition of the domain heuristics for selecting moves. The main move heuristic we consider is the negative heuristic of preferring to set moves that are not on a shortest path to false. This is encoded in the rule at Line 7 of Listing 18. We use the abbreviation MVH to indicate the use of this heuristic.