## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
It starts at \(r_{2}\)'s home location \(h_{2}\), successively traveling to the target locations for \(t_{5}\), \(t_{6}\), \(t_{7}\), and \(t_{8}\), and finishing back at \(h_{2}\). #### 4.4.5 Conflict Detection and Resolution

Having routed the paths that the robots must follow, we can now turn to dealing with conflict detection and resolution. Similar to the step-based approach in Section 4.3.2, we refrain from explicitly ruling out conflicting situations, and rather rely on the binary predicate before/2 for expressing precedences. In contrast to Section 4.3.2, however, these precedences are now established among paths rather than robots. The encoding in Listing 14 derives either the fact before((\(p\),\(v\)),(\(p^{\prime}\),\(v^{\prime}\))) or the fact before((\(p^{\prime}\),\(v^{\prime}\)),(\(p\),\(v\))). This represents that vertex \(v\) is visited on path \(p\) before vertex \(v^{\prime}\) is visited on path \(p^{\prime}\) or vice versa, whenever paths \(p\) and \(p^{\prime}\) contain conflicting vertices \(v\) and \(v^{\prime}\) and are assigned to different robots. ```
1 visit(P,V):-path(P,V). 2 visit(P,V):-move(P,V,_). 3 same_robot(R,T):-assign(R,T). 5{before((P,V),(P',V'))}:-visit(P,V),visit(P',V'),
6 conflict(V,V'),P<P',
7 notsame_robot(P,P'),
8 notsame_robot(P',P). 9 before((P',V'),(P,V)):-visit(P,V),visit(P',V'),
10 conflict(V,V),P<P',
11 notsame_robot(P,P'),
12 notsame_robot(P',P'),
13 notbefore((P,V),(P',V')). 15:-start(R,V),notpath(R,_),{move(_,_,V)}1. 16:-start(R,V),path(R,_),notassign(R,_),before((_,_),(R,V)). 17:-start(R,V),path_assign(R,P),
18 path_sequence(P,_),notpath_sequence(_,P),before((_,_),(P,V)). 19:-before((P,V),(P',V')),path(P,V),path_sequence(P,P'),
20 notbefore((P',V),(P',V')). 21:-robot(R),path(R,V),before((R,V),(_,_)). 22
24:-move(P,V1,V2),move(P',V1',V2'),
25 conflict(V1,V1'),conflict(V2,V2'),before((P,V1),(P',V1')),
26 notbefore((P,V2),(P',V2')). 27:-move(P,V1,V2),move(P',V1',V2'),
28 conflict(V1,V2'),conflict(V2,V1'),before((P,V1),(P',V2')),
29 notbefore((P,V2),(P',V1')). ```

**Listing 14**Resolve conflicts for paths visiting conflicting vertices and edges. To this end, Lines 1 to 2 provide predicate visit/2 to capture which vertices are visited on each path; the first argument is the name of the path and the second argument is a vertex belonging to the path. Note that the rule in Line 1 uses static information since the endpoint of each path is known beforehand. Then, Line 2 only needs to collect the first vertex from each path's moves, which is dynamic information. Predicate same_robot/2 is already defined in Listing 2 to indicate which tasks are executed by the same robot. Line 3 extends this to paths by stating that for every robot \(r\) that is assigned a task \(t\), the path named \(r\) and the path named \(t\) is executed by the same robot. This extends to paths since path names are task names. With these auxiliary predicates, lines 5 to 13 use visit and path assignments to detect and resolve conflicts as indicated above. Note that we are only allowed to choose before((\(p\),\(v\)),(\(p^{\prime}\),\(v^{\prime}\))) whenever path \(p\) is alphanumerically smaller than path \(p^{\prime}\). If this atom is not chosen, we derive the opposite ordering before((\(p^{\prime}\),\(v^{\prime}\)),(\(p\),\(v\))). This enhances propagation because we only need half the choices and reduces the problem size since the additional constraint that only one ordering can be chosen becomes unnecessary. Integrity constraints in Lines 15 to 21 avoid invalid moves and address the part of conflict resolution discernible without precise scheduling. Line 15 states that no move is possible through a robot's starting location if it has no path assigned and thus never leaves this location. Both Lines 16 and 17 focus on the first path assigned to a robot. The former addresses paths to home nodes where no further tasks are assigned; the latter deals with the first task in the path sequence.