## 4 Prediction Horizon Length and Convergence
### Prediction horizon length with an occupancy grid
We state the following theorem to obtain the worst-case positioning of the robots, i.e., we derive a maxima of the ratio of direct path to the necessary detour that a robot has to take:  
**Theorem 2** (Worst-case positioning of robots). : _Suppose a group of robots with the time discrete model in Equation (1) restricted by the state in Equation (3) and the control constraints in Equation (17) with feasible initial conditions and disjunct (intermediate) targets \(z_{p}(n),z_{q}(n),z_{p}(n+N),z_{q}(n+N)\in Z\) satisfying Assumption 3 with \(z_{p}(n+N)\
eq z_{q}(n+N)\) and a minimum cell size \(\xi\) obtained by Equation (9). For two robots \(p,q\in[1:P]\), \(q\) keeps its position \(z_{q}(k)\equiv z_{q}\) with \(k\in[n:n+N]\). Then, the worst-case of positioning of two robots is bounded by the maximum of the ratio of a necessary feasible detour (\(3\left(\xi+\xi\right)\) for moving along the sides of the cell and \(\sqrt{\left(\frac{\xi}{2}+\xi\right)^{2}+\delta\ \left(\frac{\xi}{2}+\xi \right)^{2}}\) for the hypotenuse to the target) to the direct path \(\left\|z_{p}(n)-z_{p}(n+N)\right\|_{2}\) (c.f. \(z_{2}\) (blue) in Figure 4b) by_  
\[\frac{3\left(\frac{\xi}{2}+\xi\right)+\sqrt{\left(\frac{\xi}{2}+\xi\right)^{2} +\delta\ \left(\frac{\xi}{2}+\xi\right)^{2}}}{2\left(\frac{\xi}{2}+\xi\right)+\delta\ \left(\frac{\xi}{2}+\xi\right)}=\frac{3\overline{ \Psi}+\sqrt{\overline{\Psi}^{2}+\delta\ \overline{\Psi}^{2}}}{2\overline{\Psi}+\delta\ \overline{\Psi}}=\frac{3 \overline{\Psi}+\overline{\Psi}\sqrt{\left(1+\delta\right)^{2}}}{\left(2+ \delta\right)\overline{\Psi}}\]  
_with \(\delta\ \to 0\) leading to the maximum ratio_  
\[\lim_{\delta\to 0}\frac{3\overline{\Psi}+\overline{\Psi}\sqrt{\left(1+\delta \right)^{2}}}{\left(2+\delta\right)\overline{\Psi}}=\frac{4\overline{\Psi}}{2 \overline{\Psi}}=2.\]  
_This coincides with the shortest feasible target distance (opposite of both sides of the cell of \(z_{p}\), c.f. \(z_{2}\) (red) in Figure 4b) with_  
\[\frac{4\left(\frac{\xi}{2}+\xi\right)}{\left\|z_{p}(n)-z_{p}(n+N)\right\|_{2}} =\frac{4\left(\frac{\xi}{2}+\xi\right)}{2\left(\frac{\xi}{2}+\xi\right)}\equiv \frac{4\overline{\Psi}}{2\overline{\Psi}}=2, \tag{23}\]  
Figure 3: Classification of start and end combinations of robot 2 to circumvent robot 1 to obtain the ratios of detour/direct way: middle of side length (red), diagonal (blue), and asymmetric (green). _and therefore, the ratio of shortest feasible detour to direct path is bounded by_  
\[1\leq\frac{3\overline{\Psi}+\overline{\Psi}\sqrt{\left(1+\delta\right)^{2}}}{ \left(2+\delta\right)\overline{\Psi}}\leq\frac{4\overline{\Psi}}{2\overline{ \Psi}}\leq 2.\]  
Proof. : Suppose, a larger ratio of detour to direct path exists. Then, we have to select a combination of start and end points on the side length of the cell. In total, four combinations can be classified, which are depicted in \[-\bar{x}+2\overline{\Psi}+c\leq x_{p}\leq\bar{x}-\big{(}2\overline{\Psi}+c \big{)}\;,\quad-\bar{y}+2\overline{\Psi}+c\leq y_{p}\leq\bar{y}-\big{(}2 \overline{\Psi}+c\big{)} \tag{21}\]0 Setting the diagonal opposite edges (Figure 3, blue pair) would lead to a ratio of detour to direct way of  
\[-\bar{x}+2\overline{\Psi}+c\leq x_{p}\leq\bar{x}-\big{(}2\overline{\Psi}+c \big{)}\;,\quad-\bar{y}+2\overline{\Psi}+c\leq y_{p}\leq\bar{y}-\big{(}2 \overline{\Psi}+c\big{)} \tag{21}\]1  
and therefore, this is a contradiction to the hypothesis. If a nonsymmetric pair is chosen (Figure 3, green pair) with \(0\leq\delta\ \leq 1\), this lead to a ratio with  
\[-\bar{x}+2\overline{\Psi}+c\leq x_{p}\leq\bar{x}-\big{(}2\overline{\Psi}+c \big{)}\;,\quad-\bar{y}+2\overline{\Psi}+c\leq y_{p}\leq\bar{y}-\big{(}2 \overline{\Psi}+c\big{)} \tag{21}\]2  
and therefore, all these combinations lead to a ratio of detour to direct tour of less then 2 and, therefore, a larger ratio then in Equation (23) does not exists, which completes the proof.