## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
While the focus is principally on the performant variants of the path-based encoding, the step-based encoding is also important to the evaluation. In particular, the step-base encoding provides a direct correspondence to the underlying problem formalization. In contrast, because the path-based encoding is restricted to acyclic paths, there are problem instances for which the step-based encoding admits a solution but the path-based encoding does not. Therefore the step-based encoding provides a baseline for our evaluation; both in terms of the solver performance but also to see whether the lack of completeness of the path-based encoding is an issue in practice. We consider two sets of benchmarks. The first set of benchmarks consist of synthetically generated graphs, varying in size and graph density. The second set of benchmarks consist of real warehouse graphs, where we consider variations in the number of tasks and robots. The synthesized benchmarks have graphs with fewer vertices. On the other hand these benchmarks are grid-based in their construction, and in some cases are denser than the real warehouse graphs. Consequently, the differences in the two sets of benchmarks serve to highlight different performance features for a range of graph types and problem sizes. For the real warehouse graphs we also consider a number of further variations to the problem instances. Firstly, we compare the performance when the size of each robot is treated as a single point versus when the robots are assigned non-point diameters of one and two meters. Importantly, depending on the graph vertex density, allowing for larger robots can result in an increase in the number of vertex conflict constraints. Secondly, we also consider how the addition of application specific constraints, in this case pallet replacement time constraints, affect solver performance. The pallet replacement constraints provide a mechanism to ensure good-enough plans without having to consider makespan minimization; which is computationally more expensive, and, as we shall see, ultimately impractical. All benchmarks ran on a Linux computer with an Intel(R) Xeon(R) CPU E3-1260L v5 @ 2.90 GHz and 32 GB of RAM. Runs were given a memory limit of 30 GB of RAM. For the experiments to find a single solution a time limit of 1800 s (30 min) was imposed. For the optimization runs with makespan minimization a longer time limit of 7200 s (2 h) was allowed. _clingo[dl]_ was run in single-threaded mode, which ensures deterministic behavior and makes the experimental results repeatable. Finally, while we experimented with different solver configurations, _clingo[dl]_'s default _tweety_ configuration provided good overall performance. In order to keep the presentation of the results manageable we only show the results for this default configuration. ### Benchmarks

As mentioned earlier we consider two sets of benchmark problems to understand the performance limits of the different encodings and variants. #### 5.1.1 Crafted Benchmark

We generated a set of 50 problem instances of varying sizes and graph density. Graphs were generated from a number of grid configurations ranging in size from \(20\times 4\) to \(40\times 20\). For each size of grid the graphs were generated by varying the density of the vertices over the grid points and the connectedness between adjacent vertices. Each graph was also assigned a task execution graph consisting of between 2 and 20 robots and between 3 and 15 \"jobs\". Note, we loosely use the term \"job\" here to describe two pairs of dependenttasks; so a single job consists of 4 distinct tasks. Each pair of tasks consists of a pickup and a putdown task; and the putdown of the second task pair has a wait dependency on the pickup of the first task pair. This corresponds to the industry scenario of a full pallet pickup-putdown from a loading bay to a storage location, as well as the corresponding pickup-putdown of a replacement empty pallet from the empty pallet storage to the newly vacated loading bay.