## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
The artefacts that can lead to poor solutions, such as narrow corridors with no room for passing or over-taking, do not typically occur in well designed real-world warehouses. Secondly, where necessary it is also possible to consider different corridor definitions. Here, we have only considered the case of expanding the corridor with vertices that are directly connected to some shortest path vertex, optionally only if they do not increase the distance to the final destination. However, this expansion could be generalized to some arbitrary distance from the shortest path. We did not consider this generalization since our corridor definition worked well for our application setting and our warehouse configurations. However, alternative corridor definitions could certainly be considered for different application and warehouse settings. ### Encoding Solution Quality

We accommodate both quality measures presented in Section 3.2. For measuring the makespan, we utilize the variable bound, as mentioned in Section 4.4.6. This allows us to either restrict the solution quality via a constraint of the form kdiff(bound) <= \(q\), where \(q\in\mathbb{N}\) is the desired solution quality, or we can use _clingo_[dl]'s built-in branch-and-bound optimization by adding to the command line the option --minimize-variable=bound. Note that the latter method is computationally expensive and lacks _clingo_'s sophisticated optimization algorithms. This is the case because the scheduled values are not known to the solver and are stored in the background propagator handling difference constraints. As for the task-pair distance, we assume an instance structure as in our running example. That is, every wait dependency expresses that something has to be retrieved from a loading bay before an empty pallet can be placed. Then, we only have to consider all tasks involved in such dependencies as our task pairs to accomplish that the task-pair distance expresses the maximum replacement time. Currently, we have no means of minimizing this measure, but we can restrict it to a certain value to enforce a desired solution quality. Listing 21 adds difference constraints to enforce the desired task-pair distance. ```
1#constreplacement_bound=3*60*1000. 3&diff{arrive(T',V')-arrive(T,V)}<=replacement_bound:-
4 depends(wait,T,T'),task(T,V),task(T',V'). ```

Listing 21: Add difference constraint representing an upper bound on the pallet replacement times. ```
1#constreplacement_bound=3*60*1000. 3&diff{arrive(T',V')-arrive(T,V)}<=replacement_bound:-
4 depends(wait,T,T'),task(T,V),task(T',V'). ```

Listing 22: Add difference constraint representing an upper bound on the pallet replacement times. This pallet replacement bound provides a solution quality guarantee without resorting to computationally expensive optimization, as with makespan minimization. The constant replacement_bound should be overridden based on domain specific factors, such as the graph size and the expected ratio of tasks to robots. Figure 4: A simple example showing the limitation of the corridor-based routing; robot \(r_{1}\) located at vertex \(h_{1}\) needs to travel to \(l_{1}\), while robot \(r_{2}\) at \(h_{2}\) needs to travel to \(l_{2}\). For a uniform edge weight of 10 s the corridor-free encoding (**left**) can achieve the optimal makespan of 70 s by sending \(r_{2}\) along a non-shortest path route, while the corridor-based encoding (**right**) rules out vertices \(w_{4},\ldots,w_{7}\) from the corridor and requires 80 s.

## 5 Experiments

We evaluated our approach to the warehouse delivery problem using the Hybrid ASP system _clingo[dl]_ v1.3.0, which is built on _clingo_ v5.5.1. Given the industry focus of this work, the primary goal of these experiments is to understand the potential viability of our approach for solving real-world warehouse delivery problems. In particular, we evaluate the performance of the step-based and path-based encoding variants under different warehouse graph configurations and task loads.