## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
[1,false]
```

#### 4.5.3 Corridor-Based Routing

Last but not least, the final application of shortest path information is to define corridors and to restrict robot moves accordingly. Unlike the previous applications of shortest path information, restricting robot moves to defined corridors actually restricts the solution space of the problem. While the path-based encoding has already been shown to be incomplete with respect to the formalization (Section 4.4.1), the introduction of corridor-based routing adds a second source of incompleteness. Candidate models that deviate from the corridors will no longer be acceptable as solutions. On the other hand, the corridor restriction decreases the problem size, and therefore the overall size of the ground instance, which is an important consideration when dealing with large warehouse graphs. This is borne out in Section 5 where the experimental results show that a significant number problem instances simply fail to ground without the addition of corridor-based routing. Furthermore, with some caveats that we discuss at the end of this section, the set of solutions often have shorter makespans, even in the absence or other performance enhancements, such as domain heuristics, since detours are avoided. In the same way that there can be multiple shortest paths between any two vertices, there can also be multiple corridor between any two vertices. To define the corridors between two vertices we first ensure that the shortest paths between these vertices are part of some corridor. We then expand each corridor to include vertices that are directly connected to a shortest path vertex that is already on that corridor. Optionally this expansion can be restricted only to cases where the new vertex does not increase the distance to the target goal vertex. Listing 19 shows the creation of corridors from the shortest paths. ```
1 corridor(T,V):-static_shortest_path(T,V). 2 corridor(T,V'):-static_shortest_path(T,V),
3 edge(V,V',_),task(T,V'),
4 shortest_path(V,V'',N,_),
5 shortest_path(V',V'',N',_),N'<=N. 7 corridor(P,P',V'):-possible_shortest_path(P,P',V). 8 corridor(P,T,V'):-corridor(P,T,V),
9 edge(V,V',_),task(T,V'),
10 shortest_path(V,V'',N,_),
11 shortest_path(V',V'',N',_),N'<=N. 12 corridor(P,R,V'):-corridor(P,R,V),
13 edge(V,V',_),home(R,V')',
14 shortest_path(V,V'',N,_),
15 shortest_path(V',V'',N',_),N'<=N. ```

Lines 1 and 7 make the shortest paths part of the corridors. The rules in Lines 2, 8 and 12 extend the corridor with vertices if the aforementioned conditions are fulfilled. The three different cases are necessary because of different sources of shortest path information. We have to differentiate whether a path is associated with a task or a robot to know its target location. Note that all corridors are established after grounding. Listing 19 only shows the case where the expansion is restricted to vertices where the distance to the target vertex is not increased. However in the experimental results (Section 5) we also consider the case where the expansion is not restricted by this requirement, essentially removing the N'<=N restriction from each rule and requiring only that a vertex in a corridor either is a vertex on the shortest path or is directly connected to such a vertex. We ensure in the adapted routing encoding in Listing 20 that the correct corridors are traversed depending on task assignment and sequencing. As an example, we have the following corridor for path t2 in our example. corridor(t2,11)corridor(t2,w1)corridor(t2,w5)corridor(t2,s1)

This corridor is identical to the only shortest path because all alternative routes would increase the distance to the target vertex s1. On the other hand, a corridor that is unequal to a shortest path in our running example is the following one.