## 4 Prediction Horizon Length and Convergence
### Prediction horizon length with an occupancy grid
If_  
\[-\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}\]6  
_holds, then robot \(p\) is able to obtain a feasible control, which allows to decrease the costs according to Definition 2 and therefore is able to circumvent robot \(q\)._  
Proof. : Based on Assumption 2 and Theorem 2, each robot \(p\) is equipped with a feasible (intermediate) initial condition and (intermediate) target, i.e., these are feasible and not occupied by other robots for the given time interval \(k\in[n:K]\). By Theorem 2 a feasible trajectory exists between \(z_{p}(n)\) and \(z_{p}(n+N)\) for \(N\rightarrow\infty\) and bounded costs as the maximum ratio of necessary detour and direct path is bounded. As robot \(p\) is steered to \(z_{p}(N)=z_{p}(K)\) with \(K<\infty\) for a large horizon \(N\), most of the open-loop cost values of the prediction converge to \(\ell_{p}(z_{p}(N),0)\to 0\). With the constrained control in Equation (3), the state \(z_{p}(K)\) is reachable by incorporating the impact of the control with  
\[N_{p}^{*}\ell_{p}\left(z_{p}\left(0;z_{p}^{0}\right),0\right)\leq 1+\sum_  
The sufficient horizon length is illustrated in the following two examples depicting holonomic and non-holonomic robots, whereas we follow the definition that a robot is holonomic if the total degrees of freedom are equal to the controllable degrees of freedom. Here, we apply cost functions based on Reference [10], and for comparison reasons, the maximum norm constraint definition is used for both systems in Equation (13). The considered cellsize is \(c=2.0\), and the sampling size is \(T=1.0\). **Example 1** (Holonomic example). : _Let be two robots defined by_  
\[z^{+}=f(z,u)=z+u\text{ with }z_{p}(0)= \begin{pmatrix}0\\ 0\end{pmatrix} \text{, }z_{p}^{*}= \begin{pmatrix}-4\\ 0\end{pmatrix} \text{ and }z_{q}(0)= \begin{pmatrix}-2\\ 0\end{pmatrix} \]  
_satisfying the constraints in Equations (2) and (3) and the control bounded by \(u\in[-1,1]^{2}\) with \(u= \begin{pmatrix}u_{1}\\ u_{2}\end{pmatrix} \), \(\|u\|\leq\sqrt{2}\) and stage costs_  
\[\ell_{p}\left(z_{p},u_{p}\right):=\left\| \begin{pmatrix}\left(x_{p}-x_{p}^{*} \right)^{2}\\ 5\left(y_{p}-y_{p}^{*}\right)\end{pmatrix} \right\|_{2}+0.2\left\|u_{p}^{2} \right\|_{2}. \tag{27}\]  
_The costs of the open-loop prediction are presented in Table 1, illustrating the sufficient prediction horizon length to circumvent robot \(q\) with \(N=7\). The two columns at first show the costs for the open-loop prediction including the control impact with \(\lambda\ =0.2\) and \(\lambda\ =0\), respectively. The last column represents the stage costs without imposing any control. For an insufficient horizon length, i.e., \(N=6\), the solution of the optimiser reveals \(\mathbf{u}_{p}=0\). However, to calculate the costs for taking the detour, the optimal control sequence is calculated with the sufficient horizon length \(N=7\) and stripped by the last value._  
_Therefore, if the control is included in the cost function, the prediction horizon has to be at least \(N\geq 7\) to recognise the decrease of costs in spite of the necessary detour. For an illustration, see Figure 5a._  
**Example 2** (Non-holonomic example). : _Based on Reference [33] an example of a non-holonomic robot defined in the 2D plane via_  
\[z^{+}=f(z,u)= \begin{pmatrix}x\\ y\\ \theta\end{pmatrix} + \begin{pmatrix}\cos(\theta)\\ \sin(\theta)\\ 0\end{pmatrix} \
u+ \begin{pmatrix}0\\ 0\\ 1\end{pmatrix} \omega,\qquad z_{p}(0)= \begin{pmatrix}0\\ 0\\ \frac{\pi}{4}\end{pmatrix} \text{, }z_{p}^{*}= \begin{pmatrix}-4\\ 0\\ 0\end{pmatrix} \text{ and }z_{q}(0)= \begin{pmatrix}-2\\ 0\\ 0\end{pmatrix} \]  
_with \(\theta\) representing its orientation. Moreover, we suppose the given stage costs_  
\[\ell_{p}\left(z_{p},u_{p}\right):=\left\| \begin{pmatrix}\left(x_{p}-x_{p}^{*} \right)^{2}\\ 5(y_{p}-y_{p}^{*})\\ \left(\theta_{p}-\theta_{p}^{*}\right)^{2}\end{pmatrix}