## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
#### 4.4.3 Path Creation

Knowing task assignment and sequences provides us with the necessary information about paths to be routed and their order. That is, there needs to be a path addressing each task, whereby the set of paths are ordered so as to match the task sequences, and an additional path has to be routed to return each robot to its home station. The latter applies to robots having been assigned a task or not having started from their home station. Looking at the warehouse delivery problem in terms of necessary paths has the advantage that a lot of relevant information is static, since the tasks' target vertices are known in advance. Hence, the routing problem is no longer being solved in a somewhat indirect manner, by shaping the meandering timed walks of individual robots to fit their assigned tasks. Instead routing becomes focused on the individual paths themselves, where only the starting location of each path can be subject to change based on the assigned robot. Listing 10 identifies how the necessary paths are constructed. ```
1 path(T,V):-task(T,V). 2 path(R,V):-assign(R,_),home(R,V). 3 path(R,V):-notstart(R,V),home(R,V). 5 path_assign(R,T):-assign(R,T). 6 path_assign(R,R):-assign(R,_). 7 path_assign(R,R):-notstart(R,V),home(R,V). 9 path_sequence(T,T'):-task_sequence(T,T'). 10 path_sequence(T,R):-assign(R,T),nottask_sequence(T,_). ```

Lines 1-3 define atoms over predicate path/2, where the first argument can be seen as the name of a path and the second as its destination. More precisely, we have path(\(t,v\)for every task \(t\) and \(f_{V}(t)=v\), and path(\(r,v\)) for every robot \(r\) that needs to return to its home station, either because it has assigned tasks or because it did not start at its home station, viz. \(f_{S}(r)\
eq f_{H}(r)\). Analogously, we assign paths to robots in Lines 5-7. We have path_assign(\(r,t\)) whenever assign(\(r,t\)) and path_assign(\(r,r\)) for any robot \(r\) having a task assignment or not having started at its home station. Here the first argument identifies the robot while the second identifies the path. Lines 9 and 10 build path sequences from task sequences. Line 9 aligns path sequences with task sequences. That is, we have path_sequence(\(t,t^{\prime}\)) whenever task_sequence(\(t,t^{\prime}\)) for all tasks \(t,t^{\prime}\). Furthermore, we have to route a way home once a robot has executed its final assigned task. For this, we add path_sequence(\(t,r\)) in Line 10, where \(t\) is the final task assigned to robot \(r\). Here, \(t\) is identifiable as a final task as it has no successor task in any task sequence. Note, that Line 10 covers two cases: one where there exists a fact task_sequence(\(t^{\prime},t\)) for some \(t^{\prime}\), and one where there is no such fact. The latter is a corner-case that does not occur in our specific application setting, since every delivery job consists of both a pickup and a putdown task, guaranteeing that any robot having a task assignment is assigned more than one task. We get the following atoms in our example in Table 1.

```
path(t1,11)path(t2,s1)path(t3,p1)path(t4,11) path(t5,l2)path(t6,s2)path(t7,p1)path(t8,l2)path(r1,h1)path(r2,h2) path_assign(r1,t1)path_assign(r2,t5)path_assign(r1,t2)path_assign(r2,t6)path_assign(r1,t3)path_assign(r2,t7)path_assign(r1,t4)path_assign(r2,t8)path_assign(r1,r1)path_assign(r2,r2)path_sequence(t1,t2)path_sequence(t5,t6)path_sequence(t2,t3)path_sequence(t6,t7)path_sequence(t3,t4)path_sequence(t7,t8)path_sequence(t4,r1)path_sequence(t8,r2)
```

The first eight atoms over path/2 identify paths associated with specific tasks, while the last two care about the return of both robots to their home station. In turn, robot \(r_{1}\) is assigned \(t_{1},\ldots,t_{4}\) plus its return home; analogously, \(r_{2}\) is assigned \(t_{5},\ldots,t_{8}\) and its return. The given list of tasks also corresponds to the order of the paths to be executed by each robot. #### 4.4.4 Routing

Listing 11 determines routes for the paths created in Listing 10.