## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
Furthermore, since \(p\) identifies a task, and not just a path, and \(v^{\prime}\) is its target location, we can add the projection of task \(p\) on step \(\pi_{X}(p,v^{\prime})\). Note that the step count is the same for paths \(p\) and \(p^{\prime}\) on vertex \(v^{\prime}\). Finally, we deal with conflict resolution in 7. If vertex \(v\) on path \(p\) precedes vertex \(v^{\prime}\) on path \(p^{\prime}\), then the robot, \(r\), assigned to path \(p\) also precedes the robot, \(r^{\prime}\), assigned to path \(p^{\prime}\) on these vertices. Recall that conflict resolution in the step-based encoding is expressed via the step and not the vertex. It is mapped to the correct vertices via atoms \(\mathtt{walk}(r,\pi_{X}(p,v),v)\) and \(\mathtt{walk}(r^{\prime},\pi_{X}(p^{\prime},v^{\prime}),v^{\prime})\). ### Performance Enhancement via Shortest Path Information

To this point, we have provided two different encodings that generate solutions to the warehouse delivery problem. The step-based encoding closely matches the formalization of the warehouse delivery problem, so the mapping from a stable model of the step-based encoding to a solution of the problem was relatively straightforward. In contrast, the link from the path-based encoding to the problem formalization was less immediate. So instead, we showed how a path-based solution maps directly to a step-based solution (but not vice versa), and hence, by implication, the stable models of a path-based encoding also correspond to solutions of the warehouse delivery problem. We now go beyond the basic encodings to develop enhancements that can be added to improve solver performance, and also solution quality, when searching for solutions to the warehouse delivery problem. The enhancements that we introduce are based around pre-computing shortest path information for a given warehouse graph. This type of pre-processing is tractable and needs only be done once for a graph at hand. The shortest path information is used in three key ways: to calculate timing lower-bounds to improve solver propagation, to implement domain heuristics to prefer routes along shortest paths, and finally to define corridors for limiting the choice of robot moves. It is worth pointing out that we do not consider performance enhancements for the step-based encoding. There are two reasons for this. Firstly, the need to apply a step horizon means that grounding problem instances for the step-based encoding is highly dependent on the size of the warehouse graph. As will be clear from our experimental results (Section 5), this issue alone negatively impacts the viability of the step-based encoding for many realistic warehouse graphs. The second reason is that it is significantly more challenging to apply shortest path techniques to the step-based encoding. This encoding deals with the entire walk of a robot as a single unit, from its starting vertex to its final arrival at its home vertex. In order to apply shortest path information in such a setting it would be necessary to first segment a robot's walk into sub-parts for which shortest path information would be relevant. In contrast, this is something that comes for free with the path-based encoding, shortest path information can be applied directly to the paths of the path-based encoding. The underlying shortest path information is provided at the outset by pre-computing all shortest paths from every vertex on the graph to every _endpoint_ vertex. By endpoint vertex we simply mean all possible task target vertices as well as the robot home vertices. For a warehouse (\(V\),\(E\),\(f_{E}\),\(C\),\(R\),\(f_{H}\),\(f_{S}\)), this results in facts of the form

\(\mathtt{shortest\_path}(v,v^{\prime},l,v^{\prime\prime})\). for every \(\{v,v^{\prime}\}\subseteq V\), \((v,v^{\prime\prime})\in E\), and \(l\in\mathbb{N}\). Such a fact represents that there is a shortest path from \(v\) to \(v^{\prime}\) of length \(l\) that follows edge \((v,v^{\prime\prime})\in E\). Note that there might be several such shortest paths.