## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
Recall that the walk assignment \(f_{W}(r)\) of a robot \(r\) is a sequence of route points being feasible in the underlying warehouse. Each route point represents the arrival and exit time at a vertex. We represent a route point \((v,a,e)\) at position \(s+1\) of the timed walk \(f_{W}(r)\) of a robot \(r\) by means of an atom walk(\(r,s,v\)) along with two terms \(a\) and \(e\) acting as integer variables. The actual timing constraints are expressed as difference constraints among these integer variables. Listing 9 poses timing constraints based on the robots' walks, resolved conflicts, and projections. These constraints are encoded using integer variables that correspond to the arrival and exit times of specific robots at specific steps of their walks. These variables are represented by the terms arrive(\(r,s\)) and exit(\(r,s\)) for any robot \(r\) at step \(s+1\) of walk assignment \(f_{W}(r)\). Note, the arrival and exit of a robot at a specific step maps directly to specific vertices, so we can think of the constraints as determining the arrival and exit times of robots at vertices. The purpose of the difference constraints in Listing 9 is then to check whether an integer assignment to these variables exists that warrants a feasible timed walk in view of the constraints posed by the other parts of the encoding. ```
1&&diff{ arrive(R,S)-exit(R,S)}<=0:-walk(R,S,_). 3&&diff{ exit(R,S)-arrive(R,S+1)}<=-W:-walk(R,S,V),walk(R,S+1,V'), edge(V,V',W). 6&&diff{ arrive(R,0)-0}<=0:-walk(R,0,_). 7&&diff{ 0-arrive(R,0)}<=0:-walk(R,0,_). 9&&diff{ arrive(R,S)-bound}<=0:-walk(R,S,_),notwalk(R,S+1,_). 10&&diff{ exit(R,S)-bound}<=0:-walk(R,S,_),notwalk(R,S+1,_). 11&&diff{ bound-exit(R,S)}<=0:-walk(R,S,_),notwalk(R,S+1,_). 14&&diff{ arrive(R,S+1)-arrive(R',S')}<=0:-before((R,S),(R',S')). 16#constkappa=10. 18&&diff{ arrive(R,S)-exit(R,S)}<=-kappa:-
19 proj(T,S),assign(R,T). 20&&diff{ arrive(R,S)-arrive(R',S')}<=-kappa:-
21 proj(T,S),assign(R,T),
22 proj(T',S'),assign(R',T'),
23 depends(D,T,T'),D!=deliver, R!=R'. ```

Listing 9: Derive timing constraints to obtain a valid schedule. Line 1 ensures that the exit time of a robot at a vertex, as represented by the robot's step count, does not precede its arrival at that vertex, while Line 3 ensures that the travel time between vertices is respected. Together, this corresponds to the feasibility requirements (2) and (3) on timed walks. Next, Lines 6 and 7 force each robot's arrival time at its starting vertex, represented by the step count 0, to a time of 0 as stipulated in 10. Lines 9 to 11 impose constraints on each robot at its terminal vertex. In particular, the constraints ensure that for any robot \(r\) at its terminating step \(s\), we have that arrive(\(r,s\)) \(\leq\) bound and exit(\(r,s\)) \(=\) bound. Note, bound here is an integer variable, so the value of bound is an upper bound on all robots' arrival times at their last steps. In fact, _clingo[DL]_ yields the least upper bound, which corresponds to the last of these arrival times, because the assignment returned by _clingo[DL]_ contains the lowest possible positive integer values that satisfy all difference constraints. Furthermore, the exit times of all last steps are set to this value. Hence, the exit times of all robots at their corresponding home vertices are equal, which also constitutes the makespan of the solution to the warehouse delivery problem. The advantage of this technique is two-fold. First, if a home vertex of a robot can be in the walk of another robot, we ensure that finished robots remain in place until the entire execution is completed. Second, the variable bound gives us an easy access to the makespan of the solution. This can be utilized to either minimize or restrict the execution time. Note, that we use the variable bound for the exit times at terminal vertices rather than the constant \(\infty\), as stipulated by the homing Condition 11. However, since bound is the common exit time of all terminal vertices it is easy to see the direct mapping between the two.