## 4 Prediction Horizon Length and Convergence
### Prediction horizon length with an occupancy grid
Theorem 2 states the worst-case ratio, which has to be covered by a necessary detour in favour to the direct path, which also determines the ratio for the cost function to let the optimiser recognise a decrease of costs by circumventing a robot. This is illustrated in Figure 4 for two robots, where the quantised position of robot \(1\) is given as an occupied cell. The sufficient horizon length \(N_{p}^{*}\), necessary for the optimiser to recognise the decrease of costs, additionally depends on the position of the given target \(z_{p}^{*}\), illustrated in Figure 4 for robot 2. Examples  
\[-\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}\]3 Illustration of the sufficient prediction horizon length \(N_{2}^{*}\) to recognise a decrease of costs by taking the detour (**a**) and feasible trajectories for robot 2 (**b**), with \(x_{i}(0)\) as the initial position, \(q(\cdot)\) as the quantised state, and \(x_{i}^{*}\) as the (intermediate) target for \(i\in[1:2]\). for up to 4 robots (\(P\leq 4\)) are presented in the Appendix. Based on this, we can derive a lower bound for the sufficient horizon length assuming the worst-case positioning from Theorem 2, where the ratio of necessary detour to shortest way is at maximum. An example of feasible trajectories is presented in Figure 4b, illustrating the trajectories depending on the target used for the maximum ratio by Theorem 2. Note that, although the ratio is bounded, an additional difficulty to determine a lower bound on the prediction horizon length occurs as this depends also on the formulation of the cost function: The costs do not depend solely on the difference of current \(z_{p}(n)\) and target \(z_{p}^{*}\). A positive definite cost function \(\ell_{p}\) defined by Definition 2 may include a penalty on the control with \(0<\lambda\ \leq 1\) to avoid large control values or large differences in the control values as many cost functions aiming for a set point are defined for the euclidean space according to Reference [32] [\[-\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}\]43]. The open-loop costs for a robot retaining its position over the prediction horizon \(N\) are given by \(\left(N-1\right)\ell_{p}\left(z_{p}(n;z_{p}^{0}),0\right)\). Then, if such a robot holds this position, the costs to circumvent the occupied cell have to be lower, i.e.,  
\[-\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}\]5  
holds. Here, a prediction horizon length, which is long enough that a decrease of state costs (\(\lambda\ =0\)) is recognised by choosing a detour, is not necessarily long enough if control effort is also penalised (\(\lambda\ >0\)). Hence, a sufficient prediction horizon length has to incorporate the control effort, and therefore, the whole cost function has to be considered. Using Definition 2 and the assumption that a minimiser for the OCP in Equation (16) exists, the sufficient horizon length to recognise a decrease of the open-loop costs is stated in the following theorem:  
**Theorem 3** (Sufficient prediction horizon length). : _Suppose that two robots \(p,q\) are given with feasible initial conditions \(z_{p,q}^{0}\equiv z_{p,q}(n)\) and disjunct (intermediate) targets \(z_{p}(K)\in Z\) with \(K\in\mathbb{N}_{0}\), \(K<\infty\) satisfying Equations (2) and (3), minimising a cost function defined by Definition 2 with Assumptions 1 and 2 to hold and a feasible trajectory between \(z_{p}^{0}\) and \(z_{p}(K)\) exists bounded by Theorem 2.