## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
```
#edge(T,T'):depends(D,T,T'),D!=deliver. ```
Our example yields 120 (acyclic) task sequence assignments, among them the one in Table 1, represented by
```

assign(r1,t1)assign(r2,t5)assign(r1,t2)assign(r2,t6)assign(r1,t3)assign(r2,t7)assign(r1,t4)assign(r2,t8)task_sequence(t1,t2)task_sequence(t5,t6)task_sequence(t2,t3)task_sequence(t6,t7)task_sequence(t3,t4)task_sequence(t7,t8)

### Step-Based Encoding

In this section, we address routing and scheduling aspects of our application via an encoding closely following our formalization. In doing so, we separately describe the parts of the encoding capturing walk assignments, conflict detection and resolution, projections, and scheduling. Finally, we discuss the correspondence of the resulting stable models to the solutions of warehouse delivery problems. #### 4.3.1 Walk Assignment

We start by providing an encoding capturing (non-timed) walks satisfying starting and homing conditions in Listing 6; timing constraints addressing arrival and exit times are addressed in Section 4.3.4. ```
1 step(0..maxstep). 3 vertex(V'):-edge(V,_,_). 4 vertex(V'):-edge(_,V',_). 50{walk(R,S,V):vertex(V)}1:-robot(R),step(S). 7:-walk(R,S,_),notwalk(R,S-1,_),S>0. 8:-walk(R,S,V),walk(R,S+1,V'),notedge(V,V',_). 10:-walk(R,0,V),notstart(R,V). 11:-walk(R,S,V),notwalk(R,S+1,_),nothome(R,V). 12:-start(R,V),home(R,V'),V!=V',notwalk(R,_,_). ```

To begin with, we introduce a horizon limiting the maximum length of any walk. The corresponding parameter is introduced in Line 1 and controls how many instances of predicate step/1 are introduced. A robot's walk is a sequence of vertices; it is represented via the ternary predicate walk/3. The walk in Table 2 is captured by the following atoms. ```
walk(r1,0,h1)walk(r2,0,h2)walk(r1,1,w3)walk(r2,1,w4)walk(r1,2,w2)walk(r2,2,w8)walk(r1,3,w1)walk(r2,3,12)walk(r1,4,11)walk(r2,4,w8)walk(r1,5,w1)walk(r2,5,w7)walk(r1,6,w5)walk(r2,6,w6)walk(r1,7,s1)walk(r2,7,s2)walk(r1,8,w5)walk(r2,8,w6)walk(r1,9,w6) walk(r2,9,w2) walk(r1,10,w2) walk(r2,10,p1) walk(r1,11,p1) walk(r2,11,w2) walk(r1,12,w2) walk(r2,12,w1) walk(r1,13,w1) walk(r2,13,w5) walk(r1,14,11) walk(r2,14,w6) walk(r1,15,w1) walk(r2,15,w7) walk(r1,16,w2) walk(r2,16,w8) walk(r1,17,w3) walk(r2,17,12) walk(r1,18,h1) walk(r2,18,w8) walk(r2,19,w4) walk(r2,20,h2)  
Each instance walk(\(r,s,v\)) expresses that robot \(r\) is at step \(s+1\) at vertex \(v\). Accordingly, Line 5 allows every robot in every step to be at any vertex, while the remaining integrity constraints make sure that walks are feasible (except for timing constraints) and respect the starting and homing conditions. Firstly, the integrity constraint at Line 7 excludes walks with gaps. This ensures a canonical representation making sure that subsequently visited vertices also have subsequent step numbers. Next, since walks have to respect the warehouse's structure, vertices with successive step numbers must be connected via an edge in the warehouse graph. This is enforced by the integrity constraint in Line 8. Up to this point, the encoding produces (non-timed) feasible walks with up to maxstep\(+1\) vertices for each robot in the warehouse at hand. Next, we add additional constraints to ensure Conditions 8 and 9, warranting a starting and homing walk. Line 10 ensures that the walk of each robot begins at its starting location. Then, Line 11 requires each walk to end at the robot's home location. Furthermore, finally, Line 12 enforces that the walk is non-empty if the robot does not start at its home location. This is necessary to deal with the special case of a robot that does not start at its home location but also has no assigned tasks. Without this constraint it would be possible for there to be no walk/3 instances generated for this robot, which in turn would mean that the homing constraint at Line 11 would not ensure that the robot finished its walk at its home location.