## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
We developed two base encodings, a step-based encoding and a path-based encoding, that both rely on the scheduling of robot movements using difference constraints. While the step-based encoding is able to capture the generality of the formalization, it fails to scale to the level required for solving the problem in an industrial setting. In contrast, the path-based encoding gains efficiency by restricting robot motion to sequences of acyclic paths. We showed that despite lacking the generality of the step-based encoding, the restriction of the path-based encoding was not a limitation in practice. Furthermore, the encoding of paths provides a number of important advantages. Firstly, it obviates the need to specify a horizon value for each problem instance, a problem shared by many ASP-based planning approaches. Secondly, the introduction of paths as a primitive to the encoding opens a number of avenues for developing performance enhancing variants and restrictions. We evaluated the path-based encoding and its variants on a range of problem instances, from small semi-randomly generated warehouses through to large warehouses that were hand-designed by domain experts at Dorabot. While all variants were able to provide some performance benefits, we can identify two key improvements, one for memory usage and the other for timing, that were crucial to the success of our approach. Both these improvements were built on the use of pre-computed shortest-path information, which is rendered practical as a result of the static nature of warehouse graphs. Firstly, the restriction of robot motion to corridors, defined around the shortest-path information, is a necessary step to allowing the memory usage of _clingo[DL]_'s grounder to scale to robots operating over large graphs with many tasks. Secondly, the use of domain heuristics for robot routing is crucial to reaching the near real-time performance required by the application setting. Beyond the task of simply finding a solution to a given problem instance, we also evaluated the performance of our approach with respect to solution quality. We can highlight three important findings from this evaluation. Firstly, we showed that traditional makespan minimization is not a realistic expectation for large scale warehouse delivery problems. Despite allowing for an extended timeout there was not a single case where the solver was able to provably find the solution with the minimal makespan for any of our industry benchmark problems. Secondly, the first solutions found by the basic search were already of a high quality, typically less than twice the makespan of the best solution found. This is not particularly surprising since the combination of the shortest-path domain heuristic and the algorithm for the difference constraints solver ensured both near optimal routes and minimal timing for individual tasks. Consequently, improvements in solution quality can, largely, only come from changes to the robot-task assignment and sequencing. Finally, we showed that significant improvements in solution quality can often come relatively cheaply through the use of application specific constraints. While our evaluation shows the applicability of an ASP-based approach to warehouse delivery problems, there are still a number of important avenues for further work. Firstly, our developments and evaluation did not cover all possible variants that could be applied to the path-based encoding. In particular, different corridor definitions could be developed, and a variety of domain heuristics could be considered for both the routing as well as task assignment and sequencing. Secondly, the evaluation does highlight some areas for greater study and refinement. One aspect in particular can be seen in the breakdown comparison for the individual maps; both as the number of tasks increase but also as the size of the robots increase. Adding more tasks increases the runtime and number of timeouts.