## 3 Warehouse Delivery Problem
### Formalization
#### 3.1.2 Solution Formulation
\begin{table}
\begin{tabular}{c c c c} \hline \hline \(f_{W}(r_{1})\) & \((h_{1},0,0)\) & \(f_{W}(r_{2})\) & \((h_{2},0,0)\) \\  & \((w_{3},15,15)\) & & \((w_{4},15,15)\) \\  & \((w_{2},45,45)\) & & \((w_{8},30,30)\) \\  & \((w_{1},65,65)\) & & \((l_{2},45,55)\) & \(t_{5}\) \\  & \((l_{1},80,90)\) & \(t_{1}\) & \((w_{8},70,70)\) \\  & \((w_{1},105,105)\) & & \((w_{7},100,100)\) \\  & \((w_{5},175,175)\) & & \((w_{6},120,120)\) \\  & \((s_{1},190,200)\) & \(t_{2}\) & \((s_{2},135,145)\) & \(t_{6}\) \\  & \((w_{5},215,215)\) & & \((w_{6},160,160)\) \\  & \((w_{6},225,225)\) & & \((w_{2},175,175)\) \\  & \((w_{2},240,240)\) & & \((p_{1},190,200)\) & \(t_{7}\) \\  & \((p_{1},255,265)\) & \(t_{3}\) & \((w_{2},215,215)\) \\  & \((w_{2},280,280)\) & & \((w_{1},235,235)\) \\  & \((w_{1},300,300)\) & & \((w_{5},253,253)\) \\  & \((l_{1},135,325)\) & \(t_{4}\) & \((w_{6},263,263)\) \\  & \((w_{1},340,340)\) & & \((w_{7},283,283)\) \\  & \((w_{2},360,360)\) & & \((w_{8},313,313)\) \\  & \((w_{3},390,390)\) & & \((l_{2},328,338)\) & \(t_{8}\) \\  & \((h_{1},405,\infty)\) & & \((w_{8},353,353)\) \\  & & \((w_{4},368,368)\) \\  & & \((h_{2},383,\infty)\) & \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Timed walks of robot \(r_{1}\) and \(r_{2}\) taking 18 and 20 steps, respectively. our example scenario, both robots start and end their walks in (4) at their home docking stations; hence both walks in (4) are starting and homing. Next, we consider restrictions over the movements of the robots to ensure that the robots do not collide with each other. Essentially, we must make sure that the timed walk for a robot cannot conflict with that of any other robot. To this end, we take a rather conservative approach and require that the robot passing first through a crucial zone must already have reached its next waypoint before another robot can enter the zone. This is similar to the follow constraint in MAPF (cf. [12]). This condition could be refined by instead introducing a safety period after a robot leaves a conflict zone rather than waiting until it arrives at the next node. For simplicity, we opt for this conservative formalization. **Collision-free Assignment**. Given a warehouse (\(V\),\(E\),\(f_{E}\),\(C\),\(R\),\(f_{H}\),\(f_{S}\)), we define a robot assignment \((f_{T},f_{W})\) as _collision-free_ iff:  
12. For any distinct robots \(r,r^{\prime}\in R\) and route points \((v,a,e)\in f_{W}(r)\) and \((v^{\prime},a^{\prime},e^{\prime})\in f_{W}(r^{\prime})\) with \((v,v^{\prime})\in C\), either 1. \(a<a^{\prime}\) and \(f_{W}(r)=\langle\dots,(v,a,e),(v^{\prime\prime},a^{\prime\prime},e^{\prime \prime}),\dots\rangle\) such that \(a^{\prime\prime}\leq a^{\prime}\); or 2. \(a^{\prime}<a\) and \(f_{W}(r^{\prime})=\langle\dots,(v^{\prime},a^{\prime},e^{\prime}),(v^{\prime \prime},a^{\prime\prime\prime},e^{\prime\prime\prime}),\dots\rangle\) such that \(a^{\prime\prime\prime}\leq a\). In both cases, we require that either of the conflict parties arrives strictly first at the vertices in question. Then, if robot \(r\) arrives first, as in Condition 12a, there must be a subsequent route point \((v^{\prime\prime},a^{\prime\prime},e^{\prime\prime})\) such that robot \(r^{\prime}\) is only allowed to arrive at \(v^{\prime}\) once \(r\) has arrived at its next destination \(v^{\prime\prime}\), and has thus moved out of the way so that \(r^{\prime}\) may pass. The converse situation where \(r^{\prime}\) proceeds first is expressed in Condition 12b, such that robot \(r\) is only allowed to arrive at \(v\) once \(r^{\prime}\) has arrived at its next destination \(v^{\prime\prime\prime}\). Clearly, most conflict zones are singleton. However, in case of a larger conflict zone, Condition 12a and 12b would in turn by applied to all corresponding pairs in the conflict relation to warrant that the first robot has left the zone before another one may enter. For illustration, let us consider the connected vertices \(w_{5}\) and \(w_{6}\).