## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
corridor(r1,t1,h1)corridor(r1,t1,w3)corridor(r1,t1,w2)corridor(r1,t1,w7)corridor(r1,t1,w1)corridor(r1,t1,w6)corridor(r1,t1,l1)corridor(r1,t1,w5)

Here the corridor includes the shortest path vertices h1, w3, w2, and l1, as well as the vertices w7, w1, w6, and w5, that are directly connected to one of these shortest path vertices. If we consider the case of vertex w7, it is directly connected to w3 and from w7 the minimum travel time to the target l1 is 63 s, which is less than the 65 s from w3 to l1. In contrast w4 is also directly connected to w3, but has a minimum travel time of 85 s to w7 and hence fails the N'<=N restriction. To integrate the corridor information, we need to replace the choice rules in Lines 1 to 6 in Listing 11 by the ones in Lines 1 to 10 in Listing 20. ```
10{move(P,V,V'):edge(V,V',_),corridor(P,V')}1:-
2 corridor(P,V),edge(V,_,_). 30{move(P,V,V'):edge(V,V',_),corridor(P,V)}1:-
4 corridor(P,V'),edge(_,V',_). 60{move(P,V,V'):edge(V,V',_),corridor(_,P,V')}1:-
7 corridor(_,P,V),edge(V,_,_). 80{move(P,V,V'):edge(V,V',_),corridor(_,P,V)}1:-
9 corridor(_,P,V'),edge(_,V',_). 10:-robot(R),notpath(R,_),move(R,_,_). 12:-move(P',V,V'),path_sequence(P,P'),
13 notcorridor(P,P',V),notcorridor(P,P',V'). 15:-move(R,V,V'),robot(R),notassign(R,_),
16 notcorridor(R,R,V),notcorridor(R,R,V'). ```

Listing 20: Only allow moves along corridors. This only allows moves along corridors. Furthermore, recall that corridors are decided at grounding time, so we keep the desired property that the choices do not depend on any non-domain atom. Finally, the integrity constraints in Lines 12 and 15 ensure that only moves are made on corridors applicable to the path sequencing and task assignments. Although corridor-based routing restricts the set of possible solutions, its advantages are twofold. Firstly, the problem size is reduced, and secondly, the first solution found by the solver is likely to have a relatively high quality with respect to the set of all possible solutions. What we mean by this is that the pool of solutions without a corridor-based restriction will include circuitous paths that can range over the entire warehouse graph. If the solver is simply trying to find a single satisfying solution then it is difficult to guarantee that it will not fix on one of these poor quality solutions. In contrast the solutions returned by the corridor-based restriction will all have the basic level of route quality guaranteed by the corridor definition. In this section, we have described the details of corridor-based routing and highlighted its many advantages. Nevertheless this approach also has some important limitations that need to be considered. As was mentioned earlier, applying corridor-based routing introduces a source of incompleteness to the encoding. It is relatively easy to construct an example where the use of corridor-based routes can rule out an optimal solution or even fail to admit any solution. In Figure 4, corridor-free routing allows robot \(r_{2}\) to take a longer path that avoids conflicts with the path of robot \(r_{1}\). In so doing it is able to find an optimal makespan of 70 s. In contrast, with corridor-based routing the longer path is no longer an option, which makes the problem highly sensitive to timing so that robot \(r_{2}\) has to reach its destination before \(r_{1}\) can even start its journey. This results in a non-optimal makespan of 80 s. Furthermore, as with the scenario in Figure 3 it is also possible to create an alternative scenario with robot \(r_{1}\) starting at \(w_{1}\) and \(r_{2}\) starting at \(w_{3}\) that makes the corridor-based routing fail to admit a solution. Nevertheless, as with the discussion of the trade-offs between the step and path-based encodings, there are measures that can be taken to minimize any potential negative effects of employing corridor-based routing. Firstly, and most importantly, as we have already outlined in Section 4.4.1, good warehouse design is crucial.