## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
In both cases, the integrity constraints ensure that no other path is given priority over the robots' starting positions, which constitutes the first vertex of the respective initial paths. Since each robot can be viewed as \"arriving\" at its starting location at time point zero, therefore, no path assigned to a different robot containing this starting location, or a vertex in conflict with it, could arrive there first. Line 19 aligns conflict resolution at the transition between two adjacent paths in a sequence. This transition is reflected in the target vertex \(v\) of a path \(p\), expressed by path(\(p\),\(v\)). If path \(p\) is followed immediately by path \(p^{\prime\prime}\) then \(v\) is both the final vertex for \(p\) and the starting vertex for \(p^{\prime\prime}\). Since the robot remains on \(v\) during this path transition, therefore, the same conflict resolution that applied between \(p\) and \(p^{\prime}\) must also apply between \(p^{\prime\prime}\) and \(p^{\prime}\). That is, since \(p\) had precedence over \(p^{\prime}\) in accessing \(v\) therefore \(p^{\prime\prime}\) must also precede \(p^{\prime}\) in accessing \(v\). Finally, integrity constraints in Lines 24 and 27 align conflict resolution whenever paths follow or cross each other with respect to adjacent pairs of conflicting vertices. In essence, if path \(p\) contains a move from vertex \(v_{1}\) to vertex \(v_{2}\), path \(p^{\prime}\) contains a move from vertex \(v_{1}^{\prime}\) to vertex \(v_{2}^{\prime}\), and we have that \((v_{1},v_{1}^{\prime})\in C\) and \((v_{2},v_{2}^{\prime})\in C\), then whatever conflict resolution is applied to \(v_{1}\) and \(v_{1}^{\prime}\) must also carry over to \(v_{2}\) and \(v_{2}^{\prime}\). Intuitively, in this situation, two robots would follow each other through narrow terrain, so overtaking would not be possible, whoever starts going first, continues doing so. Similarly, if instead \((v_{1},v_{2}^{\prime})\in C\) and \((v_{2},v_{1}^{\prime})\in C\), that is, distinct robots traveling along paths \(p\) and \(p^{\prime}\) that cross in a tight corridor, the robot to enter the corridor first must also exit the corridor before the second robot can enter, resulting in the same conflict resolution for \(v_{1}\) and \(v_{2}^{\prime}\) and for \(v_{2}\) and \(v_{1}^{\prime}\). Our running example in Table 2 exhibits the following conflict resolution. ```
before((t1,w2),(t7,w2))before((t7,w2),(t3,w2))before((t1,w2),(t8,w2))before((t8,w2),(t3,w2))before((t1,w1),(t8,w1))before((t7,p1),(t3,p1))before((t2,w1),(t8,w1))before((t7,w2),(t4,w2))before((t2,w5),(t8,w5))before((t8,w2),(t4,w2))before((t3,w5),(t8,w5))before((t8,w1),(t4,w1))before((t6,w6),(t3,w6))before((t8,w1),(r1,w1))before((t3,w6),(t8,w6))before((t7,w2),(r1,w2))before((t8,w2),(r1,w2))
```

#### 4.4.6 Scheduling

Once the paths have been routed and the potential conflicts have been resolved, the next step is deal with scheduling. Listing 15 handles scheduling for the path-based encoding. ```
1&diff{ arrive(P,V) - exit(P,V) } <= 0 :- visit(P,V). 2&diff{ exit(P,V) - arrive(P,V') } <= -W :- move(P,V,V'), edge(V,V',W). 4&diff{ 0 - arrive(P,V) } <= 0 :- path(P,_), not path_sequence(_,P),
5 path_assign(R,P), start(R,V). 6&diff{ arrive(P,V) - 0 } <= 0 :- path(P,_), not path_sequence(_,P),
7 path_assign(R,P), start(R,V). 8&diff{ exit(P,V) - arrive(P',V) } <= 0 :- path_sequence(P,P'),
9 path(P,V). 10&diff{ arrive(R,V) - bound } <= 0 :- home(R,V). 11&diff{ exit(R,V) - bound } <= 0 :- home(R,V). 12&diff{ bound - exit(R,V) } <= 0 :- home(R,V). 14&diff{ arrive(P,V') - arrive(P',V') } <= 0 :-
15 before((P,V),(P',V')), move(P,V,V'). 17#constkappa=10. 18&diff{ arrive(T,V) - exit(T,V) } <= -kappa :- task(T,V). 19&diff{ exit(T,V) - exit(T',V')} <= -kappa :- depends(D,T,'),
20 D!= deliver,
21 task(T,V), task(T',V'),
22 not same_robot(T,T'),
23 not same_robot(T',T). ```

**Listing 15**. Derive timing constraints to obtain a valid schedule.