## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
In contrast, robot r1 only passes through the vertices once on its way to dropping off a full pallet at s1. In combination, there are two sets of occasions requiring conflict resolution, and we have therefore presented these facts in two distinct blocks. Firstly, when r2 is at its step 6 it passes through vertex w6 on its way to dropping off the pallet at s2. The first fact states that r2 must do this before r1 passes through vertices w5 at its own step 6. In fact, the subsequent facts in this block show that because of the adjacency of these conflict pairs, r2 must complete the full sequence of moves from w5 to s2, back to w5 and then leave w5 before r1 is able to travel through w5 on its way to s1 and back to w5 and then to w6. The second block of facts deals with r2's second visit to w5 and w6 as it passes through these vertices on its way to dropping off an empty pallet at vertex l2. However, unlike the first case where r2 was given precedence over robot r1, in this case r1 is given precedence. Intuitively, this is the preferred scenario as the overall delay would have been much greater if r1 had to wait for r2 to pass through twice before it could finish its first delivery task. Finally, it is worthwhile observing that the before/2 facts only establish a qualitative ordering without providing any assignment of specific timings. For instance, before((r2,6),(r1,8)) only expresses that the passage of r2 in its sixth step must precede that of r1 in its eighth step. As shown in Section 3.1.2, in an ultimate solution of our example, this is refined by letting r1 pass at time point 215 and r2 at 120. #### 4.3.3 Projection

Next, we form projections for checking whether task assignments, sequences and walks are executable, still without considering timing constraints. For this, we derive in Listing 8 atoms of the form proj(t,s) to indicate that task \(t\) is executed during some walk at step \(s\). ```
11{proj(T,S):step(S)}1:-task(T,_). 33:-#count{T:proj(T,S),assign(R,T)}>1,step(S),robot(R). 55:-proj(T,S),task(T,V),assign(R,T),notwalk(R,S,V). 66:-proj(T,S),proj(T',S'),task_sequence(T,T'),S>S'. ```

Specifically, we project in Line 1 each task onto exactly one step. In contrast to Condition 13, this abstracts from the specific robot and vertex; which allows for a more compact encoding that scales independently of the number of robots and vertices. Rather, we represent the actual projection points implicitly and enforce the connection to the specific robot and vertex via the integrity constraints in Lines 3 to 5. Line 3 makes sure that at most one task per robot and step is projected, given that robots cannot execute several tasks simultaneously. The constraint in Line 5 enforces that there actually is a robot assigned with the specific task at its target vertex in the projected step. In detail, for proj(t,s), it is required that we have walk(r,s,v) with \(t\in f_{T}(r)\) and \(f_{V}(t)=v\), or assign(r,t) and task(t,v), respectively. This establishes Condition k. in the definition of projections and selects the relevant vertices from the robot's walk. Finally, Line 6 ensures that projections respect the order of the task sequences, \(f_{T}\). Together the rules in Listing 8 make sure that there is a non-timed projection of each robot's walk onto its task sequence. This establishes the qualitative aspects of Condition 13. As an example, the representation of the two projections in Table 3 is given below. ```
proj(t1,4)proj(t5,3) proj(t2,7)proj(t6,7) proj(t3,11)proj(t7,10) proj(t4,14)proj(t8,17)
```

Note that the respective step indicates the position in the timed walks in Table 2, which are in turn represented by the following instances of walk/3 (cf. end of Section 4.3.1):

```
walk(r1,4,11)walk(r2,3,12) walk(r1,7,s1)walk(r2,7,s2) walk(r1,11,p1) walk(r2,10,p1) walk(r1,14,11)walk(r2,17,12)
```

#### 4.3.4 Scheduling

Up to now, we have ignored all timing constraints. In fact, so far our encoding has only dealt with walks rather than timed walks, making up an actual walk assignment.