## 4 Prediction Horizon Length and Convergence
### Prediction horizon length with an occupancy grid  
In Model Predictive Control (MPC), an appropriate prediction horizon length is crucial for convergence. Here, as the constraints utilising the maximum norm and the intermediate safety margin have to be obeyed (Proposition 2), the indifferentiability of the occupied cells has to be taken into account, which requires a suitable horizon length to enable the optimiser to recognise a decrease of costs by taking a detour. The following assumption is stated to ensure disjunct, feasible initial conditions, and targets of the robots:  
**Assumption 3** (Disjunct initial conditions/targets). : _Consider a set of robots \([1:P]\) with the underlying model in Equation (1), the state in Equation (2), and the control constraints in Equation (3). For each robot \(p\in[1:P]\), let \(z_{p}^{0},z_{p}^{*}\in Z\), and for all \(p,q\in[1:P]\) with \(p\
eq q\) and \(\hat{z}_{j}\in\{z_{j}^{0},z_{j}^{*}\}\) with \(j\in\{p,q\}\), we have_\[g_{q,0}^{p}(\hat{z}_{p},q(\hat{z}_{q}))\geq 2\overline{\Psi}+c, \tag{20}\]  
_and for \(z_{p}=\big{(}x_{p},y_{p}\big{)}^{\top}\)_  
\[-\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}\]  
_shall hold._  
This assumption ensures the existence of a connected feasible path between all initialization points and to all targets, i.e., between any two of these points, there is one grid cell available for a third robot such that all constraints are satisfied. Additionally, to allow that other robots could pass at the bounds of \(Z\), this is ensured by Equation (21). For an illustration, see Figure 2. Here, \(\Psi\) is included in the figure, so the overall distance for Equation (20) leads to \(2\overline{\Psi}+c\) to ensure that a robot can still move between the initial conditions or targets of the other robots. We like to point out that Assumption 3 is stricter as the target positions are included in the feasibility assumption and therefore directly induces Assumption 2 to hold. In order to obtain a sufficient prediction horizon length, which depends on the formulated cost function, a class of stage costs has to be defined:  
**Definition 2** (Stage cost function). : _: Let \(\ell_{p}\colon Z\times U\to\mathbb{R}_{\geq 0}\) be a positive definite, continuous differentiable function with_  
\[\ell_{p}(z_{p},u_{p}):=\left\|d_{z}(z_{p},z_{p}^{*})\right\|_{2}+\lambda\; \;\left\|d_{u}(u_{p},u_{p}^{*})\right\|_{2} \tag{22}\]  
_where \(d_{z}\colon Z\times Z\to\mathbb{R}_{\geq 0}\) and \(d_{u}\colon U\times U\to\mathbb{R}_{\geq 0}\) describe metrics with \(\ell_{p}(z_{p}^{*},0)=0\), \(\ell_{p}(z_{p},u_{p})>0\) for \(z_{p}\in Z\) and \(u_{p}\in U\) and where \(0\leq\lambda\;\leq\;1\), \(\lambda\;\in\mathbb{R}_{\geq 0}\) describes the fraction of the included penalty of the control._  
Figure 2: Example of a given initial \(z_{i}(0)\), \(i\in\{1,2\}\) and intermediate positions (here, \(z_{2}\left(n\right)\)) with initial constraints (green) and constraints for intermediate states (\(n>0\), purple and orange) in a grid \(\mathcal{G}\) with \(a_{\max}=b_{\max}=3\). For stage cost functions based on a normed distance, we have to evaluate the worst case of a necessary feasible detour caused by circumventing another robot's cell in comparison to the direct path to ensure a sufficient prediction horizon length. Therefore, we consider the trajectory points (start and end point of the detour) of a robot at a cell to be circumvented. Then, as most pairs of start and end points of this detour are on the opposite sides of the cell, which has to be circumvented, these pairs can be classified as shown in Figure 3 by either taking the middle of a side length for start and (intermediate) targets or the diagonal length of an asymmetric pair.