## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
#### 4.5.1 Lower-Bound Propagation

The first application of the shortest path information is to impose lower bounds on travel times for all paths. Although these lower bound constraints are redundant, their addition may improve propagation and therefore decrease solving time. The lower bound information can quickly prune invalid variable assignments that could never be part of a satisfiable solution. This can be especially performant for detecting unsatisfiable problem instances. We express this by means of difference constraints in Listing 17. ```
1&&diff{exit(R,V)-arrive(R,V')}<-N:-
2 start(R,V),home(R,V'),V!=V',
3 notassign(R,_),shortest_path(V,V',N,_). 4&&diff{exit(T,V)-arrive(T,V')}<-N:-
5 start(R,V),nottask_sequence(_,T),task(T,V'),
6 assign(R,T),shortest_path(V,V',N,_). 7&&diff{exit(P',V)-arrive(P',V')}<-N:-
8 path_sequence(P,P'),path(P,V),path(P',V'),
9 shortest_path(V,V',N,_). ```

**Listing 17**. Add difference constraint representing lower bound on travel time. Whenever we have a path \(p\) with start vertex \(v\) and end vertex \(v^{\prime}\), and a shortest path among them of length \(n\), we add a difference constraint requiring that the arrival time at \(v^{\prime}\) on \(p\) is at least \(n\) time units after the exit of \(v\) on \(p\). For instance, in our running example, we would add the difference constraint &&diff{ exit(t2,l1)-arrive(t2,s1)}<=-48 for the path for t2. As above, case discrimination results in the three different rules for identifying the respective start and end vertex of each path. Line 1 captures the situation where a robot has no work assigned but is not at its home vertex; the start of the path is thus the start of the robot and the end is its home vertex. Line 4 identifies the first task in a task sequence. The start of the path is the start of its associated robot, and the end is the target vertex of the task. Furthermore, finally, Line 7 handles two subsequent paths in a path sequence. The target vertex of the first path is the start and the target vertex of the second path the end. #### 4.5.2 Domain-Specific Heuristics

The second application of shortest path information is to use it to encode domain-specific heuristics to prefer moves on shortest paths as well as to avoid moves that are off the shortest paths. We use the two heuristic modifiers [1,sign] and [1,false] to specify these preferences; where the modifier [1,false] is a shorthand for the combination of [-1,sign] and [1,level]. The heuristic directives in Line 1 and Line 4 in Listing 18 prefer atoms over move/3 to be assigned true, at the default assignment level of 0, whenever they are on statically and dynamically determined shortest paths, respectively. Note that Line 1 is determined before solving, while Line 4 is evaluated during solving, since it depends on task assignments and sequencing. ```
1#heuristicmove(P,V,V'):static_shortest_path(P,V),path(P,V'),shortest_path(V,V',...,V'),V!=V'. 2[1,sign]
4#heuristicmove(P,V,V'):dynamic_shortest_path(P,V),path(P,V'),shortest_path(V,V',...,V'),V!=V'. 5[1,sign]
7#heuristicmove(P,V,V'):edge(V,V',...),path(P,V'),notshortest_path(V,V',...,V'). 8[1,false]
```

Finally, the statement in Line 7 prefers choosing and falsifying atoms, at the higher assignment level of 1, for moves that are not on a shortest path. While all three directives express preferences on the assigned truth values, the latter is assigned first and is therefore the stronger preference. In this way, we use a weaker form of heuristics for moves on the shortest path. This is because there might be several shortest paths spread over different vertices, and so heuristically modifying all of them has no focusing effect. On the other hand, if a move is not on any shortest path, it is clearly preferable to avoid it. We verify these hypotheses empirically in Section 5. For instance, in our running example, we would add the directives (after grounding):

```
#heuristicmove(t1,w1,w5). [1,sign]
#heuristicmove(t1,w1,w2).