## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
The idea is now to use this information to calculate shortest paths that are relevant for a given set of tasks. This is done in Listing 16. ```
1 static_shortest_path(T',V):-depends(deliver,T,T'),task(T,V). 2 static_shortest_path(T,V'):-static_shortest_path(T,V),task(T,V'),
3 shortest_path(V,V',_,V'). 5 possible_shortest_path(R,R,V):-start(R,V). 6 possible_shortest_path(T,R,V):-robot(R),notdepends(deliver,T_),
7 task(T,V). 8 possible_shortest_path(P,R,V'):-possible_shortest_path(P,R,V),home(R,V'),
10 shortest_path(V,V',_,V'). 11 possible_shortest_path(R,T,V):-start(R,V),task(T),
12 notdepends(deliver,_,T). 13 possible_shortest_path(T,T',V'):-task(T,_),task(T',V'),T!=T',
14 notdepends(deliver,T,T'). 15 possible_shortest_path(P,T,V'):-possible_shortest_path(P,T,V),
16 task(T,V'),shortest_path(V,V',_,V'). 17 shortest_path(R,V):-possible_shortest_path(R,R,V),
20 notassign(R,_),path(R,_). 21 dynamic_shortest_path(R,V):-possible_shortest_path(T,R,V),
22 path_sequence(T,R),notpath_sequence(R,_). 23 dynamic_shortest_path(T,V):-possible_shortest_path(R,T,V),assign(R,T),
24 task_sequence(T,_),nottask_sequence(_,T). 25 dynamic_shortest_path(T',V):-possible_shortest_path(T,T',V),
26 task_sequence(T,T'),task(T',_). ```

**Listing 16**. Calculate static and dynamic shortest path information for relevant vertices. To begin with, in Lines 1 to 3 we capture the shortest paths that are relevant irrespective of the task assignment or the sequencing. To this end, atoms of the form static_shortest_path(\(t,v\)) collect vertices, \(v\), belonging to shortest paths among the start and end node of task of \(t\). In fact, whenever two tasks \(t\) and \(t^{\prime}\) are in a delivery dependency with their respective target vertices \(v\) and \(v^{\prime}\), then \(v\) must be the start of the path to \(v^{\prime}\) for the path of \(t^{\prime}\), since both \(t\) and \(t^{\prime}\) have to be executed by the same robot and one immediately after the other. We then use the pre-computed shortest path information to complete the shortest paths from \(v\) to \(v^{\prime}\) for the path of \(t^{\prime}\). For instance, in our running example, we get

```
static_shortest_path(t2,11)static_shortest_path(t2,w1)static_shortest_path(t2,w5)static_shortest_path(t2,s1)
```

because path t2 must begin at vertex 11 and end at s1. From Lines 5 to 17, we define all possible relevant shortest paths depending on what paths and robots are present. An atom possible_shortest_path(\(x,p,v\)) states that vertex \(v\) belongs to the shortest path \(p\) if \(x\) is a path and precedes \(p\) in the path sequence or \(x\) is a robot and \(p\) is its first path. Then, Lines 19 to 26 check the actual task assignment and path sequencing and determine the shortest paths for each path. The multitude of rules in both cases stems from case discrimination. For instance, if we consider the path for task t1 in our example, we have the following possibilities among others:possible_shortest_path(r1,t1,h1)possible_shortest_path(r1,t1,w3)possible_shortest_path(r1,t1,w2)possible_shortest_path(r1,t1,w1)possible_shortest_path(r1,t1,l1)

possible_shortest_path(r2,t1,h2)possible_shortest_path(r2,t1,w4)possible_shortest_path(r2,t1,w3)possible_shortest_path(r2,t1,w2)possible_shortest_path(r2,t1,w1)possible_shortest_path(r2,t1,l1)

possible_shortest_path(t6,t1,s2)possible_shortest_path(t6,t1,w6)possible_shortest_path(t6,t1,w5)possible_shortest_path(t6,t1,w1)possible_shortest_path(t6,t1,l1)

The three blocks of atoms tell us what vertices belong to path t1 depending on whether task tl is assigned first to robot r1, first to robot r2, or is preceded by task t6 in the path sequence. For the solution in Table 2, we then get the following atoms for path t1 that determine the vertices on its shortest path

dynamic_shortest_path(t1,h1)dynamic_shortest_path(t1,w3)dynamic_shortest_path(t1,w2)dynamic_shortest_path(t1,w1) dynamic_shortest_path(t1,l1)

They correspond to the first block of atoms since task tl is the first task assigned to robot r1.