## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
Line 15 ensures that a robot without any assigned tasks begins its homing path at its start location. The integrity constraint in Line 16 enforces a similar arrangement for the opposite case of robots that have assigned tasks. It requires that a path addressing the first task assigned to a robot needs to begin at the robot's starting location. Next, Line 18 connects paths being adjacent in a path sequence. In detail, the target vertex of the preceding path needs to be the first vertex of the following path. Finally, Line 19 enforces that the last vertex of a path is indeed its target vertex. This is either a task's destination or a robot's home location. Up to this point, the path routing has ensured that there is a connected sequence of moves for each path that is aligned with the relevant task and robot locations. However, similar to the sequencing of tasks detailed in Section 4.2, this does not exclude the possibility of disconnected cyclic moves. As with task sequencing, we may employ three alternative techniques to ensure acyclicity: scheduling via difference constraints, a reachability encoding, and an edge directive. Since we detail the former approach in Section 4.4.6, we focus below on the two latter; also because they allow for routing valid paths independently. The encoding of reachability is given in Listing 12. ```
1 vertex_reachable(P,V):-path(P,V). 2 vertex_reachable(P,V):-vertex_reachable(P,V'),move(P,V,V'). 3:-move(P_,V),notvertex_reachable(P,V). ```

**Listing 12**. Path reachability. In contrast to the reachability encoding for task sequencing, we establish reachability for move sequencing from a path's destination vertex, because this target vertex is known statically. First, Line 1 declares that target vertices of each path are reachable, then, Line 2 propagates that vertices are reachable by a path, if they are connected with a reachable vertex via an outgoing move, and, finally, Line 3 checks that all moves along a path end in a reachable vertex. As an easy alternative, we may also use an edge directive to enforce acyclicity, as shown in Listing 13. ```
#edge((P,V),(P,V')):move(P,V,V'). ```

Concluding the routing of paths, Listing 11, combined with cyclic move detection, ensures a sequence of moves for each path that satisfies all tasks and homes all robots. The moves of the example timed walk in Table 2 is captured by the following atoms. ```
move(t1,h1,w3)move(t1,w3,w2)move(t1,w2,w1)move(t1,w1,l1)move(t2,l1,w1)move(t2,w1,w5)move(t2,w5,s1)move(t3,s1,w5)move(t3,w5,w6)move(t3,w6,w2)move(t3,w2,p1)move(t4,p1,w2)move(t4,w2,l1)move(r1,w1,w2)move(r1,w2,w3)move(r1,w3,h1)move(t5,h2,w4)move(t5,w4,w8)move(t5,w8,l2)move(t6,l2,w8)move(t6,w8,w7)move(t6,w7,w6)move(t6,w6,s2)move(t7,s2,w6)move(t7,w6,w2)move(t7,w2,p1)move(t8,p1,w2)move(t8,w2,w1)move(t8,w1,w5)move(t8,w5,w6)move(t8,w7,w8)move(t8,w8,l2)move(r2,l2,w8)move(r2,w8,w4)move(r2,w4,h2)
```

The first block of moves corresponds to the walk for robot \(r_{1}\). Task \(t_{1}\) is the first task assigned to \(r_{1}\) so the path for \(t_{1}\) begins at \(r_{1}\)'s starting location, \(h_{1}\), and ends at \(t_{1}\)'s target location \(l_{1}\). Task \(t_{2}\) is the second task assigned to \(r_{1}\), so the path for \(t_{2}\) begins at \(l_{1}\) and ends at its target location \(s_{1}\). The astute reader may note that these moves correspond to robot \(r_{1}\) first moving to the pallet pickup location \(l_{1}\) and then delivering the pallet to the storage location \(s_{1}\). This pattern is then repeated for the subsequent tasks \(t_{3}\) and \(t_{4}\), where the final task \(t_{4}\) corresponds to the delivery of the replacement (empty) pallet to \(l_{1}\). Finally, the homing path for \(r_{1}\) begins at \(t_{4}\)'s target location \(l_{1}\) and ends back at \(r_{1}\)'s home location \(h_{1}\). An identical pattern of moves applies to the second block, corresponding to the walk for robot \(r_{2}\).