## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution  
Having assigned robots to walks, we now turn to detecting and resolving any potential conflicts between these walks. Rather than explicitly ruling out conflicting situations, Listing 7 relies on the predicate before/2 to indicate which robot is to proceed first whenever two robots travel over conflicting vertices. ```
1{before((R,S),(R',S'))}:-walk(R,S,V),walk(R',S',V'),
2 conflict(V,V'),R<R'. 3 before((R',S'),(R,S)):-walk(R,S,V),walk(R',S',V'),
4 conflict(V,V'),R<R',
5 notbefore((R,S),(R',S')). 7:-start(R,V),notwalk(R,_,_),walk(_,_,V). 8:-walk(R,0,_),before((_,_),(R,0)). 9:-walk(R,S,_),notwalk(R,S+1,_),before((R,S),(_,_)). 11:-walk(R,S,V1),walk(R,S+1,V2),walk(R',S',V1'),walk(R',S'+1,V2'),
12 conflict(V1,V1'),conflict(V2,V2'),before((R,S),(R',S')),
13 notbefore((R,S+1),(R',S'+1)). 14:-walk(R,S,V1),walk(R,S+1,V2),walk(R',S',V1'),walk(R,S'+1,V2'),
15 conflict(V1,V2'),conflict(V2,V1'),before((R,S),(R',S'+1)),
16 notbefore((R,S+1),(R',S')). More specifically, an atom of the form before((r,s),(r',s')) indicates that robot \(r\) in its step \(s\) precedes robot \(r^{\prime}\) in its steps \(s^{\prime}\). The underlying conflicting vertices remain implicit. The actual detection and resolution of conflicts is done in Lines 1-5. To reduce grounding, we only make a choice whenever the robots' names are strictly smaller. We derive the opposite ordering, if the robot with the smaller name was not chosen to advance first. The rest of the encoding adds constraints for a conflict-free routing that are expressible without the need of timing constraints. In the initial situation, robots are located at their starting positions, and therefore, no other robot could pass through there first. Line 7 forbids any robot to pass through the starting point of another robot that never moves. A similar constraint is expressed in Line 8, denying robots precedence over other robots at the starting step no matter where this step takes place. Finally, Line 9 imposes a constraint for the end of each robot's walk. In particular, for the final vertex of a given robot's walk, all other robots need to have passed through any conflicting vertices first, before the given robot is allowed to arrive at its destination. Note, since our solutions are restricted to homing walks, this constraint covers the corner-case where a robot visits another robot's home vertex. This would only happen if the robot's home vertex happened to also be a waypoint to some other vertex, or if a robot needed to detour to this vertex to allow some other robot to pass, such as along a narrow corridor. However, both these situations are potential indicators of a poorly designed warehouse, and are therefore unlikely to occur in practice. Finally, the integrity constraints in Lines 11 and 14 handle robots following or facing each other in a group of conflicting vertices. The idea is that in both situations, whatever decision was made to order a pair of robots with respect to a pair of conflicting vertices, that same decision has to be maintained throughout the rest of the group of conflicting vertices. As a consequence, overtaking or colliding head-on is impossible since the robots remain in the same order or let the other robot pass completely before entering the critical part of the warehouse. Continuing our example, the following facts capture part of the conflict resolution for the walks of robots r1 and r2. To help illustrate this scenario ASP comments also show the underlying warehouse conflict atoms. before((r2,6),(r1,6)) before((r2,6),(r1,9)) before((r2,8),(r1,6)) before((r2,8),(r1,9)) before((r1,6),(r2,14)) before((r1,8),(r2,13)) before((r1,9),(r2,13)) before((r1,9),(r2,14))

These atoms address the conflicts on the two pairs of conflict vertices (w5,w6), and (s1,s2), discussed in Section 3 and shown in Figure 1. Robot r2 passes through these conflict vertices twice; once on its way to dropping off a full pallet at s2 and a second time on its way to dropping off an empty pallet at l2.