## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
Line 14 forbids that a task has several predecessors and Line 15 requires that a robot's task sequence has a unique beginning. Note that the encoding in Listing 2 cannot rule out that the obtained instances of predicate task_sequence/2 form disconnected cycles. This is because it only enforces that each such task sequence has a unique start and there is no task with several pre-decessors. For instance, given the robot assignments assign(r1,t1), assign(r1,t2), assign(r1,t3), and assign(r1,t4), Lines 4-15 could potentially generate the linear sequence task_sequence(t1,t2) in combination with the circular sequence consisting of task_sequence(t3,t4) and task_sequence(t4,t3). Fortunately, while Listing 2 by itself is not ruling out such incorrect sequences, they are discarded when scheduling information is added. This is an implicit consequence of assigning time points to tasks which rule out cyclic time sequences. However, scheduling is handled differently for the step and path encodings, and we therefore differ the discussion of its application to the following subsections. Nevertheless, while the scheduling process implicitly removes any disconnected cycles, it is also possible, and potentially beneficial, to enforce this explicitly. We introduce two distinct mechanisms for doing this. The first way of removing cyclic task sequences without scheduling is via a reachability encoding. The encoding in Listing 3 ensures that all tasks on a task sequence are reachable from the start of a sequence. ```
1 task_reachable(T):-task_sequence(T,_),nottask_sequence(_,T). 2 task_reachable(T'):-task_reachable(T),task_sequence(T,T'). 3:-task_sequence(T,_),nottask_reachable(T). ```  
First, Line 1 identifies the start of a sequence and determines that it is reachable, then, Line 2 propagates that a task is also reachable if it is connected to some other reachable task on a task sequence. Finally, Line 3 ensures that a task sequence may only continue from a reachable task. This discards the cyclic example from above, as neither t3 nor t4 are reachable from the start of a task sequence. In fact, the reachability between t3 and t4 forms an unfounded set and is discarded by the unfounded set checker of _clingo_. A second, and easy, alternative to explicitly eliminating cyclic task sequences is by using _clingo_'s builtin acyclicity checker. This can be accomplished by using the #edge directive with atoms over predicate task_sequence/2 as shown in Listing 4. ```
#edge(T,T'):task_sequence(T,T'). ```  
The advantages of combining Listings 2 with either 3 or 4 are twofold. First, the stable models of both listings combined yield all correct possible task sequence assignments, and second, although redundant when scheduling is added, it may improve solving performance by immediately discarding cyclic task sequences. We empirically investigate this in Section 5. Beyond individually correct task sequences, we can also employ acyclicity detection to prematurely discard more complex sequences that are unschedulable. For instance, we may have the single acyclic sequence task_sequence(t3,t4),task_sequence(t4,t1),and task_sequence(t1,t2), where all tasks are assigned to the same robot (e.g., assign(r1,t1), assign(r1,t2), assign(r1,t3), and assign(r1,t4)). While this task sequence itself is not cyclic, nevertheless there is a cycle introduced through wait dependencies over multiple task sequences. In this example, there is a wait dependency depends(wait,t1,t4) because t1 is the full pallet pickup task at location l1 while t4 is its corresponding empty pallet putdown task (see Figure 2). Essentially t1 must be executed before t4, and so this sequence is not schedulable despite the fact that the task sequence itself is acyclic. Listing 5 eliminates such cycles by adding the wait dependencies, via the edge directive, to the acyclicity detection. However, it is important to note that this encoding has no effect individually and needs to be used in tandem with Listing 4. ```
**Listing 5**. : Acyclicity between task sequences via #edge directives.