# Consensus Algorithms Based Multi-Robot Formation Control under Noise and Time Delay Conditions
## 2 Pre-Preparation and Problem Description
### Problem Description  
Suppose the system consists of n omnidirectional robots. The dynamic characteristics of the omnidirectional robot in the x direction are:  
\[\left\{ \begin{array}{l}\dot{x}_{i}(t)=v_{i}(t)\\ \dot{v}_{i}(t)=u_{i}(t)\end{array} \right. \tag{1}\]  
where \(x_{i}(t)\) is position, \(v_{i}(t)\) is velocity and \(u_{i}(t)\) is input control. If any \(i\) robot and \(j\) robot in the multi-robot system satisfy the identities as follows:  
\[\lim_{t\rightarrow+\infty}[x_{i}(t)-x_{j}(t)]=0 \tag{2}\]  
\[\lim_{t\rightarrow+\infty}[v_{i}(t)-v_{j}(t)]=0 \tag{3}\]  
then the multi-robot system (1) has achieved consensus under the control protocol \(u_{i}(t)\) Let the state vector of the \(i\) robot be \(\delta_{i}(t)=[x_{i}(t),v_{i}(t)]^{T}\), then the multi-robot system state vector is \(\mathbf{S}(t)=[\delta_{1}(t),\delta_{2}(t),\delta_{3}(t),\ldots,\delta_{n}(t)]\). Rewrite system (1) as:  
\[\dot{\mathbf{S}}(t)=\mathbf{\
abla}\mathbf{S}(t) \tag{4}\]  
where \(\mathbf{\
abla}=\mathbf{I}\otimes\mathbf{A}-\mathbf{L}\otimes\mathbf{B}\), \(\mathbf{A}=\left[ \begin{array}{cc}0&1\\ 0&0\end{array} \right]\), \(\mathbf{B}=\left[ \begin{array}{cc}0&0\\ k_{1}&k_{2}\end{array} \right]\), \(\otimes\) is Kronecker. When ideally without noise and delay, the control protocol designed in [13] is as follows:  
\[u_{i}(t)=\sum_{j\in N_{i}}a_{ij}\big{\{}k_{1}[x_{i}(t)-x_{j}(t)]+k_{2}[v_{i}(t )-v_{j}(t)]\big{\}} \tag{5}\]  
where \(a_{ij}>0\) is the topology weight of the communication between robot \(i\) and robot \(j\), \(k_{1}\) is the position scale factor that needs to be designed, \(k_{2}\) is the velocity scale factor that needs to be designed. Lemmas 1 and 2 give the conditions that the coefficient matrix \(\mathbf{\
abla}\) of control protocol (5) must satisfy when the communication topology of system (4) is undirected graph and directed graph, respectively. **Lemma 1**. : _When the communication topology of multi-robot system (4) is connected graph, the coefficient matrix \(\mathbf{\Psi}\) has a double zero root, and the real part of other eigenvalues is negative._  
**Proof. ** Let there be an orthogonal matrix \(\mathbf{Q}\), such that:  
\[\mathbf{Q}^{T}\mathbf{L}\mathbf{Q}=diag\{0,\lambda_{2},\lambda_{3},\ldots, \lambda_{n}\} \tag{6}\]  
where \(0,\lambda_{2},\lambda_{3},\ldots,\lambda_{n}\) is the eigenvalue of the Laplacian matrix \(\mathbf{L}\), and \(\lambda_{i}>0\) (\(i=2\), \(3\),..., n). Formula (7) is obtained from Formula (6):  
\[(\mathbf{Q}\otimes\mathbf{I}_{2})^{T}\mathbf{\Psi}(\mathbf{Q}\otimes\mathbf{ I}_{2})=diag\{\mathbf{A},\mathbf{A}-\lambda_{2}\mathbf{B},\mathbf{A}-\lambda_{3} \mathbf{B},\ldots,\mathbf{A}-\lambda_{n}\mathbf{B}\} \tag{7}\]  
The determinant of Formula (7) is obtained:  
\[|diag\{\mathbf{A},\mathbf{A}-\lambda_{2}\mathbf{B},\mathbf{A}-\lambda_{3} \mathbf{B},\ldots,\mathbf{A}-\lambda_{n}\mathbf{B}\}|=s^{2}\prod_{2}^{n}s^{2} +\lambda_{i}k_{2}s+\lambda_{i}k_{1}=0 \tag{8}\]  
Because there is \(s^{2}\) in Formula (8), there must be a double zero root in the eigenvalue. By solving polynomial equation \(s^{2}+\lambda_{i}k_{2}s+\lambda_{i}k_{1}=0\), we can get:  
\[s_{1}=\frac{-\lambda_{i}k_{2}+\sqrt{(\lambda_{i}k_{2})^{2}-4\lambda_{i}k_{1}} }{2}\]  
\[s_{2}=\frac{-\lambda_{i}k_{2}-\sqrt{(\lambda_{i}k_{2})^{2}-4\lambda_{i}k_{1}} }{2}\]  
Based on this analysis, when \((\lambda_{i}k_{2})^{2}>4\lambda_{i}k_{1}\), obviously \(-\lambda_{i}k_{2}\pm\sqrt{(\lambda_{i}k_{2})^{2}-4\lambda_{i}k_{1}}<0\), so the eigenvalues \(s_{1}\) and \(s_{2}\) are negative. When \((\lambda_{i}k_{2})^{2}<4\lambda_{i}k_{1}\), because \(\lambda_{i}k_{2}>0\), so \(-\lambda_{i}k_{2}<0\), the eigenvalues \(s_{1}\) and \(s_{2}\) have negative real parts. Lemma 1 is proved. \(\square\)  
**Lemma 2**. : _When the communication topology of multi-robot system (4) is directed graph and contains spanning tree, \(k_{1}\in(0,k_{0}k_{2}^{2})\) the coefficient matrix \(\mathbf{\Psi}\) has a double zero root, and the real part of other eigenvalues is negative.