## 2 Problem
### Construction of the Constraints  
The mobile robots share a collective operation space defined by \(Z\). As their trajectories may cross each other, we have to ensure collision avoidance regarding two aspects: The first aspect is a minimum cell size of the occupancy grid to prevent robots from skipping cells or swapping cells with another robot. As the dynamics of the robots is discretised with a fixed sampling step, an overlapping of two trajectories may occur within two time instants, leading to an unnoticed crossing of robots. Hence, a minimum cell size to prevent this is imperative. The second aspect stems from a necessary physical distance among the robots and the adherence of the constraints in the discrete time instants and in between two successive time instants. **Cell size**: In Reference [10], we proposed a minimum cell size \(\underline{c}\) based on the maximum control value which can be imposed on the robot. This minimum cell size has to cover all possible moves of the robot in \(Z\); therefore, it is lower bounded for each vector field \(f_{0}\) and \(f_{i}\) with \(i\in\{1,\ldots,m\}\)  
\[\underline{c}:=\max_{u_{p}\in U}\left\{c_{f_{0}}+\sum_{i=1}^{m}c_{f_{i}}|u_{p, i}|\right\} \tag{8}\]where each \(c_{i}\) with \(i\in\{0,\ldots,m\}\) covers the dimensions with  
\[c_{f_{0}}:=\max_{z_{p}\in Z}\left\{\max_{j\in\{1,2\}}\left|\left(f_{0}(z_{p})-z_{ p}\right)_{j}\right.\right|\right\}\text{ and }c_{f_{i}}:=\max_{z_{p}\in Z}\left\{\max_{j\in\{1,2\}}\left|f_{i,j}(z_{p}) \right|\right\}.\]  
Here, obeying the kinematic model of the robot, this is sufficient to avoid skipping cells. **Safety margin in discrete time instants**: Considering the safety margin, we have to ensure that each robot keeps a physical minimum distance to other robots, which is given by \(d_{min}\). As the minimum cell size can be smaller or larger then the necessary physical distance among the robots, we define the safety margin as follows:  
**Definition 1** (Safety Margin). : _The safety margin among any two robots \(p,q\in P,p\
eq q\) is given by the necessary physical minimum distance \(d_{min}\) and the given minimum cell size \(\underline{c}\) such that_  
\[\left\| \begin{pmatrix}x_{p}\\ y_{p}\end{pmatrix} - \begin{pmatrix}x_{q}\\ y_{q}\end{pmatrix} \right\|_{\infty}\geq\max\{d_{min},\underline{c}\} \tag{9}\]  
_holds. Here, \(\left(x_{i},y_{i}\right)^{\top}=z_{i}\), \(i\in\{p,q\}\) denote the planar positions of the robots._  
Furthermore, we have to ensure that this safety margin holds over all predicted states \(z_{p}^{u}\left(k;z_{p}^{0}\right)\) with \(k\in[1:N]\) of one robot \(p\) to any other robot \(q\). As the information of the states of robot \(q\) is given via the quantised occupancy tuples \(\mathcal{I}_{q}\left(n\right)\left(k\right):=q\left(z_{q}^{u}(n+k;z_{q}^{0})\right)\) for \(k\in[1:N]\); for a given cell size \(c\geq\underline{c}\), a robot may be in the centre of the communicated cell or on the boundary. Therefore, we obtain the maximal deviation of the quantised state to the continuous state of the robot by  
\[\left\| \begin{pmatrix}x_{q}\\ y_{q}\end{pmatrix} -h\left(q\left(z_{q}\right)\right)\right\|_{\infty}\leq\frac {c}{2}.\]  
This leads to the definition of the safety margin \(\Psi\) regarding the quantised error:  
**Proposition 1** (Quantised Prediction Safety Margin). : _For a given cell size \(c\geq\underline{c}\), minimum distance among robots \(d_{min}\), and discrete time instants \(k\) with \(k\in[1:N]\), the safety margin between two robots \(p,q\in P,p\
eq q\) based on the received quantised state \(\mathcal{I}_{q}\left(n\right)\left(k\right)\) from robot \(q\) is_  
\[\left\| \begin{pmatrix}x_{p}\left(k\right)\\ y_{p}\left(k\right)\end{pmatrix} -h\left(\mathcal{I}_{q}\left(n\right)\left(k \right)\right)\right\|_{\infty}\geq\max\left\{d_{min},\underline{c}\right\}+ \frac{c}{2}=:\Psi. \tag{10}\]  
_If this holds, then Definition 1 is satisfied with_  
\[ \begin{pmatrix}x_{p}\\ y_{p}\end{pmatrix} = \begin{pmatrix}x_{p}\left(k\right)\\ y_{p}\left(k\right)\end{pmatrix} ,\quad\forall k\in[1:N].