## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
The individual moves along a path are represented by atoms over predicate move/3, where the first argument is the path's name, and the second and third are vertices belonging to an edge on the path. Note that there is no time step associated with a move. This abolishes the need for a horizon and yields, a priori, a smaller problem representation. The drawback is, however, that each path needs to be acyclic since there is no way to distinguish between multiple visits to a vertex. In contrast, with a step-based encoding, distinct time steps allow for multiple visits of vertices. Having said that, the combination of the distinct paths that form the overall walk of any given robot may itself contain cycles, it is only the paths themselves that must be acyclic. ```
10{move(T,V,V'):edge(V,V',_)}1:-task(T,_),edge(V,_,_). 20{move(T,V,V'):edge(V,V',_)}1:-task(T,_),edge(_,V',_). 40{move(R,V,V'):edge(V,V',_)}1:-robot(R),edge(V,_,_). 50{move(R,V,V'):edge(V,V',_)}1:-robot(R),edge(_,V',_). 6:-robot(R),notpath(R,_),move(R,_,_). 8 first_visit(P,V):-move(P,V,_),notmove(P,_,V). 9 last_visit(P,V):-move(P,_,V),notmove(P,V,_). 10:-#count{V:last_visit(P,V)}>1,path(P,_). 12 first_visit(P,V):-path(P,V),notmove(P,_,_). 13 last_visit(P,V):-path(P,V),notmove(P,_,_). 15:-start(R,V),path(R,_),notassign(R,_),notfirst_visit(R,V). 16:-start(R,V),path_assign(R,P),
17 path_sequence(P,_),notpath_sequence(_,P),notfirst_visit(P,V). 18:-path_sequence(P,P'),path(P,V),notfirst_visit(P',V). 19:-path(P,V),notlast_visit(P,V). ```

Lines 1-6 allow for traversing every vertex on each path in at most one way, namely, along an incoming and an outgoing edge. The definition of predicate move/3 is separated into four choice rules, two for each task and two for homing each robot. In each case, the first rule handles moves over outgoing edges while the second handles moves over incoming edges. The encoding of the move choices in this way introduces two forms of redundancy. Firstly, rather than explicitly dealing with paths, we encode separate choice rules for tasks and robots. This allows rule bodies to be dissolved during grounding, since task/2 and robot/1 are input predicates, while path/2 is not. For the solver, this eliminates the need to first derive instances of path/2 before making the respective move choices. Secondly, while the duplication of choice rules for incoming and outgoing moves allows the same move to be selected by each rule, it also allows for solver propagation along both directions along a path. In particular, since there is at most one incoming and one outgoing move to any vertex, the solver can generate a chain of moves, propagating either from a vertex back to some source for forward to some destination. Consequently, while these choice rules encode some redundancy, this redundancy allows for improved propagation during solving. Finally, note that the constraint in Line 6 simply ensures that homing moves are created only when a robot needs it; a robot that starts at its home location and has no assigned tasks has no need to be homed. While the choice rules in Lines 1-6 ensure that each vertex along a path has at most one incoming and one outgoing edge, nevertheless, moves may still be disconnected and may not match a task's or robot's location. Ensuring these restrictions is addressed through the addition of integrity constraints. The rules in Lines 8-10 identify the first and last vertex in each path via atoms over first_visit/2 and last_visit/2, respectively. Such atoms are used to ensure that paths form connected sequences of moves. Specifically, Line 10 expresses that there cannot be paths with more than one end vertex. Additionally, Lines 12 and 13 define the first and last vertex of a path without movement. This is the case if the robot starts on a vertex where it also executes a task. Then, the path only consists of the single vertex, the target vertex of the task. Finally, the integrity constraints in Lines 15-19 align paths with robot and task locations.