## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
A second advantage of the path-based encoding is that by introducing an explicit notion of a path it allows for specific path-based optimizations. In particular it allows for pre-computed shortest-paths that can be used to calculate timing lower-bounds, determine movement corridors, and specify domain-based move heuristics. Despite the advantages of the path-based encoding, restricting each task to a single acyclic path does limit the allowable moves that a robot can make, whereas the step-based encoding permits arbitrary movements. This limitation can be easily observed in the example outlined in Figure 3. In this scenario each robot needs to swap sides in order to execute its assigned task; \(r_{1}\) needs to travel to \(l_{1}\) while \(r_{2}\) needs to travel to \(l_{2}\). The step-based encoding is able to calculate an optimal solution of 90 s, where both robots start moving at the same time with robot \(r_{2}\) deviating to vertex \(w_{p}\) to allow the robot \(r_{1}\) to pass (Figure 3 left). In contrast with the step-based encoding robot \(r_{2}\) is not able to deviate to \(w_{p}\) as it would then have to visit vertex \(w_{3}\) twice, which would break the path acyclicity requirement. Instead, one of the robots has to wait until the other robot arrives at its destination before starting its journey (Figure 3 right); with the resulting non-optimal minimal makespan of 120 s.

The observant reader may also notice that it would be easy to generate a variant of Figure 3 where the path encoding admits no solutions at all. In particular, if robot \(r_{1}\) starts

Figure 3: A simple example showing the limitation of the path encoding against the step-based encoding; 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 walk encoding (**left**) can achieve the optimal makespan of 90 s while the best path encoding plan (**right**) requires 120 s.

at \(w_{1}\) and \(r_{2}\) starts at \(w_{5}\) then neither robot will be able to break the deadlock by moving to \(w_{p}\). While the lack of completeness of the path encoding with respect to the formalization is important to appreciate, nevertheless, in practice it is not a serious limitation. The main reason for this is that in practice warehouse graphs are designed by domain experts, and a well-designed warehouse rarely contains artefacts that would lead to these types of scenarios. This is borne out in Section 5, where this restriction has no practical impact when applied to our real-world warehouse scenarios. Finally, it should also be noted that even in cases where such a narrow corridor is unavoidable, it is possible for the path encoding to avoid such deadlocks through the careful introduction of _mirrored_ vertices and edges. In Figure 3, it would be possible to introduce an extra vertex \(w^{\prime}_{3}\), setting a conflict with \(w_{3}\), and with edges to both \(w_{2}\) and \(w_{p}\). In this modified scenario, robot \(r_{2}\) could then travel along the (acyclic) path sequence \(h_{2},w_{5},w_{4},w_{3},w_{p},w^{\prime}_{3},w_{2},w_{1},l_{2}\) allowing it to use the passing vertex \(w_{p}\) and find an optimal plan. #### 4.4.2 Outline

As in Section 4.3, we start by discussing individual encoding components, namely, path creation, routing, conflict resolution and scheduling. Finally, we relate the answer sets of the path-based encoding to the ones of the step-based encoding, and discuss the relation to the problem formalization. Recall that both the step- and path-based encoding rely upon Listing 2, optionally with Listings 3-5, for assigning and sequencing tasks. It provides task sequence assignments allotting each robot a sequence of tasks; they are represented by atoms \(\texttt{assign}(r,t)\), representing that \(t\in f_{T}(r)\) for robot \(r\) and task \(t\), and \(\texttt{task\_sequence}(t,t^{\prime})\), capturing that there is a task assignment \(f_{T}(r)\) with two consecutive tasks \(t,t^{\prime}\) for some robot \(r\).