4 Control Strategy
From Definition 1, achieving an affine formation implies that \(p\) is in the column space of the matrix \(C \otimes I_D\). Based on this fact, our control strategy consists in:
- Defining, for the agents in \(\mathcal{S}_j\) \(\forall j \in \mathcal{N}_s\), motion vectors toward the column space of the matrix \(\overline{C}_j\). This produces a motion toward a partial (i.e., encompassing only \(\mathcal{S}_j\)) affine formation in the sense of Definition 1.
- Adding up these motion vectors for all sets \(\mathcal{S}_j\).
Let \(d_{j,i}(t) \in \mathbb{R}^D\) denote the vector from the current position, \(p_i(t)\), of agent \(i \in \mathcal{S}_j\) to the component corresponding to agent \(i\) of the orthogonal projection onto the column space of \(\overline{C}_j\) in (10). Note the vectors \(d_{j,i}(t)\) are only defined for agents \(i\) from \(i=j\) to \(i=j+M-1\). They are defined as \[ \tag{11} \begin{bmatrix} d_{j,j}(t) \\ \vdots \\ d_{j,j+M-1}(t) \end{bmatrix}= - (I_{D\cdot M}-\overline{C}_j \overline{C}_j^+) \begin{bmatrix} p_j(t) \\ \vdots \\ p_{j+M-1}(t) \end{bmatrix}. \] Then, according to 2), for every agent \(i \in \mathcal{N}\), the control law is the sum of the vectors for the sets that contain \(i\): \[\tag{12} u_i(t) = \dot{p}_i(t) = \sum_{j \in \mathcal{N}_s |\hspace{1pt} i \in \mathcal{S}_j} d_{j,i}(t) \hspace{10pt} \forall i \in \mathcal{N}. \] Let us now express this control law in stacked form, which will be useful for analysis. We define for every \(j \in \mathcal{N}_s\) a selector matrix \(Q_{j}=[q_{j_{m,n}}]\) \(\in \mathbb{R}^{M\times N}\) with \(q_{j_{1,j}}=1\), \(q_{j_{2,j+1}}=1\), \(\ldots\) , \(q_{j_{M,j+M-1}}=1\), and zeros in all other positions. Then, the matrix \(\overline{Q}_{j}=Q_{j}\otimes I_D\) \(\in \mathbb{R}^{(D\cdot M) \times (D\cdot N)}\) selects the elements of \(p(t)\) corresponding to the set \(\mathcal{S}_{j}\); i.e., \[\tag{13} \overline{Q}_{j} \hspace{1pt} p(t) = \begin{bmatrix} p_{j}(t) \\ \vdots \\ p_{j+M-1}(t) \end{bmatrix}. \] We can, therefore, express the control law motion vectors as \[\tag{14} \begin{bmatrix} d_{{j},{j}}(t) \\ \vdots \\ d_{{j},{j}+M-1}(t) \end{bmatrix} = -(I_{D\cdot M} - \overline{C}_{j} \overline{C}^+_{j}) \overline{Q}_{j} \hspace{1pt} p(t). \] We now define \(d_{j}(t)\) \(\in \mathbb{R}^{D\cdot N}\) which is the motion vector, for the full team, due to the set \(\mathcal{S}_{j}\). This vector simply includes the motion vectors from (14) for the agents that are in \(\mathcal{S}_{j}\), and it has zeros in all other positions. It is defined by \[\tag{15} d_{j}(t) = \overline{Q}_{j}^\intercal \begin{bmatrix} d_{{j},{j}}(t) \\ \vdots \\ d_{{j},{j}+M-1}(t) \end{bmatrix}= -\overline{Q}_{j}^\intercal (I_{D\cdot M} - \overline{C}_{j} \overline{C}^+_{j}) \overline{Q}_{j} \hspace{1pt} p(t). \] The expression of the control law in stacked form is, hence, \[\tag{16} \hspace{-4pt}\dot{p}(t) =\hspace{-1pt}\sum_{{j} \in \mathcal{N}_s} d_{j}(t) = -\hspace{-1pt}\sum_{{j} \in \mathcal{N}_s} \overline{Q}_{j}^\intercal (I_{D\cdot M} - \overline{C}_{j} \overline{C}^+_{j}) \overline{Q}_{j} \hspace{1pt} p(t). \]
Example 1.
4.1 Control Strategy Implementation
To compute (12), an agent \(i \in \mathcal{N}\) needs to know the identities, nominal configuration positions, and positions at time \(t\), of the agents that are in common sets with \(i\). It does not need any information about the agents that are not in common sets; e.g., agent \(1\) in Example 1 needs no information about agent \(7\), and vice versa. The maximum possible number of agents that a given agent has to interact with is limited to \(2\cdot(M-1)\) even if \(N\) grows indefinitely. Hence, the control strategy is distributed. \(C_j\), \(C^+_j\) are constant matrices and can be pre-stored offline. The online (i.e., at time \(t\)) information used in this approach consists of measurements of positions. Importantly, it is possible for every agent to use measurements expressed in its local reference frame; e.g., the relative positions of the other agents, measured with an onboard sensor. Let the superscript \((i)\) denote that a variable is expressed in agent \(i\)'s local frame. Assume that, instead of \(p_k\), what agent \(i\) measures is \(p^{(i)}_k=R_i p_k + w_i\), where the rotation \(R_i \in SO(D)\) and translation \(w_i \in \mathbb{R}^D\) express the transformation between frames. We omit \(t\) in this section, for compactness, but \(R_i\) and \(w_i\) can be time-varying. As mentioned, a common particular case is \(p^{(i)}_k=R_i (p_k - p_i)\), i.e., \(w_i=-R_i p_i\), which means that agent \(i\) measures relative positions in its local frame. Clearly, if \(u^{(i)}_i=R_i u_i\), the agent's motion is the same as when computed in the global frame. Next, we show that this condition is indeed satisfied.
Due to Kronecker product properties, the matrix \(I_{D\cdot M}-\overline{C}_j \overline{C}_j^+\) for any \(j \in \mathcal{N}_s\) has the form \((I_{M}-C_j C_j^+) \otimes I_D\); therefore, it consists of blocks \(\Omega_{j_{m,n}}=\alpha_{j_{m,n}} I_D\), with \(\alpha_{j_{m,n}} \in \mathbb{R}\). Expressing \(I_{D\cdot M}-\overline{C}_j \overline{C}_j^+\) in terms of these blocks, we can write from (11), for a \(j\) such that \(i \in \mathcal{S}_j\), \[ \tag{18} \hspace{-3pt} \begin{bmatrix} \hspace{-1pt} d^{(i)}_{j,j} \\ \vdots \\ d^{(i)}_{j,j+M-1} \hspace{-1pt} \end{bmatrix} \hspace{-5pt}=\hspace{-3pt}-\hspace{-3pt}\begin{bmatrix} \hspace{-1pt} \Omega_{j_{1,1}} \hspace{-3pt}&\hspace{-4pt} \cdots \hspace{-2pt}&\hspace{-2pt} \Omega_{j_{1,M}}\\ \vdots \hspace{-2pt}&\hspace{-4pt} \ddots \hspace{-2pt}&\hspace{-3pt} \vdots \\ \Omega_{j_{M,1}} \hspace{-3pt}&\hspace{-4pt} \cdots \hspace{-2pt}&\hspace{-2pt} \Omega_{j_{M,M}} \hspace{-1pt}\end{bmatrix} \hspace{-5pt}\Bigg(\hspace{-3pt} \begin{bmatrix} \hspace{-1pt} R_i p_j \\ \vdots \\ R_i p_{j+M-1} \hspace{-2pt}\end{bmatrix} \hspace{-2pt} +\hspace{-2pt}\begin{bmatrix} \hspace{-1pt} w_i \\ \vdots \\ w_i \hspace{-1pt} \end{bmatrix} \hspace{-3pt}\Bigg)\hspace{-1pt}. \] Let us define \(\widetilde{w}_i=[I_D,\ldots,I_D{]}^\intercal w_i \in \mathbb{R}^{D\cdot M}\), which is the rightmost vector of (18). Note the last \(D\) columns of \(\overline{C}_j\) are \([I_D,\ldots,I_D{]}^\intercal\); therefore, \(\widetilde{w}_i\) is in the column space of \(\overline{C}_j\), i.e., \((I_{D\cdot M}-\overline{C}_j \overline{C}_j^+)\widetilde{w}_i=0\). In addition, \(\Omega_{j_{m,n}} R_i=R_i\Omega_{j_{m,n}}\) for every block \(\Omega_{j_{m,n}}\). Comparing (11) and (18), we conclude that \(d^{(i)}_{j,i} = R_i d_{j,i}\), which holds for every addend in the control law (12) of agent \(i\). Consequently, \(u^{(i)}_i=R_i u_{i}\).
4.2 Control Law Analysis
Our formal result is presented in the following.
Theorem 1.
Proof.
As \(\widecheck{p}\) is in the nullspace of \(B\), we have \[ B \hspace{1pt} \widecheck{p} = 0. \] We can then write \[ \widecheck{p}^\intercal B \hspace{1pt} \widecheck{p} = 0 \] and, substituting the expression of \(B\), and using \(\widecheck{p}^\intercal \overline{Q}_{j}^\intercal= (\overline{Q}_{j} \hspace{1pt}\widecheck{p}{)}^\intercal\), we get \[\tag{20} \sum_{{j} \in \mathcal{N}_s} (\overline{Q}_{j} \hspace{1pt}\widecheck{p}{)}^\intercal (I_{D\cdot M} - \overline{C}_{j} \overline{C}^+_{j}) \overline{Q}_{j} \widecheck{p} = 0. \] As noted above, all matrices \(I_{D\cdot M} - \overline{C}_{j} \overline{C}^+_{j}\) are positive semidefinite. Therefore, we infer from (20) that \[ (\overline{Q}_{j} \hspace{1pt}\widecheck{p}{)}^\intercal (I_{D\cdot M} - \overline{C}_{j} \overline{C}^+_{j}) \overline{Q}_{j} \widecheck{p} = 0 \hspace{10pt}\forall {j} \in \mathcal{N}_s, \] and (see, e.g., (R. A. Horn and C. R. Johnson, 2012, Obs. 7.1.6)) that \[\tag{21} (I_{D\cdot M} - \overline{C}_{j} \overline{C}^+_{j}) \overline{Q}_{j} \widecheck{p} = 0 \hspace{10pt}\forall {j} \in \mathcal{N}_s. \] Recalling (13), let us arrange (21) as follows: \[\tag{22} \begin{bmatrix} \widecheck{p}_{j} \\ \vdots \\ \widecheck{p}_{{j}+M-1} \end{bmatrix} = \overline{C}_{j} \widecheck{v}_{j} \hspace{10pt}\forall {j} \in \mathcal{N}_s, \] where we defined \[\tag{23} \widecheck{v}_{j} = \overline{C}^+_{j} \begin{bmatrix} \widecheck{p}_{j} \\ \vdots \\ \widecheck{p}_{{j}+M-1} \end{bmatrix} \in \mathbb{R}^{D\cdot (M-1)} \hspace{10pt}\forall {j} \in \mathcal{N}_s. \] From (22), every one of the \(N_s\) systems of linear equations \[\tag{24} \begin{bmatrix} \widecheck{p}_{j} \\ \vdots \\ \widecheck{p}_{{j}+M-1} \end{bmatrix} = \overline{C}_{j} g_{j} \hspace{10pt}\forall {j} \in \mathcal{N}_s, \] where \(g_{j} \in \mathbb{R}^{D\cdot(M-1)}\) is the unknown vector, has \(g_{j}=\widecheck{v}_{j}\) as a solution. Moreover, due to Assumption 1, this solution is unique, since every \(\overline{C}_{j}\) has full column rank. In addition, if we apply Definition 1 to the set of agents in \(\mathcal{S}_{j}\) only, (22) implies that these agents are in an affine formation (which can be understood as a partial affine formation) with respect to the corresponding partial nominal configurations. Hence, we have established that every set of agents \(\mathcal{S}_{j}\) converges as \(t\rightarrow \infty\) to a partial affine formation with a parameter vector \(\widecheck{v}_{j}\) uniquely determined by the positions \(\widecheck{p}_i\) for \(i \in \mathcal{S}_{j}\). Next, we show that \(\widecheck{v}_{j}\) is the same for all the sets \(\mathcal{S}_{j}\).
Let us take an arbitrary integer \(k\) such that \(1<k\leq N_s\). For the cases \({j}=k\) and \({j}=k-1\) in (22), we have \[\tag{25} \begin{bmatrix} \widecheck{p}_{k} \\ \vdots \\ \widecheck{p}_{k+M-1} \end{bmatrix} \hspace{-3pt}= \overline{C}_{k} \widecheck{v}_{k},\hspace{3pt} \begin{bmatrix} \widecheck{p}_{k-1} \\ \vdots \\ \widecheck{p}_{k+M-2} \end{bmatrix} \hspace{-3pt}= \overline{C}_{k-1} \widecheck{v}_{k-1}. \hspace{0pt} \] From (9), we know that the matrix \(G_k\) satisfies \[\tag{26} \overline{C}_{k}=\begin{bmatrix} G_k \otimes I_D \\ row_M(C_k) \otimes I_D \end{bmatrix}\hspace{-2pt}, \hspace{2pt} \overline{C}_{k-1}= \begin{bmatrix}row_1(C_{k-1}) \otimes I_D \\ G_k \otimes I_D \end{bmatrix}\hspace{-2pt}. \] Therefore, from (25) and (26), we have \[\tag{27} \begin{bmatrix} \widecheck{p}_{k} \\ \vdots \\ \widecheck{p}_{k+M-2} \end{bmatrix} =(G_k \otimes I_D) \cdot \widecheck{v}_{k} = (G_k \otimes I_D) \cdot \widecheck{v}_{k-1}, \] i.e., \[\tag{28} (G_k \otimes I_D) \cdot (\widecheck{v}_k-\widecheck{v}_{k-1}) = 0. \] Recall that \(G_k\) is a nonsingular matrix, due to Assumption 1. Hence, \(G_k \otimes I_D\) is nonsingular too. Therefore, the only solution to (28) is \(\widecheck{v}_k-\widecheck{v}_{k-1} = 0\), and we thus have \(\widecheck{v}_k=\widecheck{v}_{k-1}\). It is direct to see that this reasoning can be extended to every set \(\mathcal{S}_{j}\) \(\forall {j} \in \mathcal{N}_s\), due to their chained structure. Hence, there exists a unique \(\widecheck{v}\) such that \(\widecheck{v}_{j}=\widecheck{v}\) \(\forall {j} \in \mathcal{N}_s\). Considering (22) and the form of the \(\overline{C}_{j}\) matrices according to (7), (8), we can then write \[\begin{aligned} \widecheck{p}_1 & = (row_1( C_1) \otimes I_D) \widecheck{v}= (row_1(C) \otimes I_D) \widecheck{v} \\ \widecheck{p}_2 & = (row_2( C_1) \otimes I_D) \widecheck{v}= (row_2(C) \otimes I_D) \widecheck{v} \\ &\vdots \\ \widecheck{p}_M & = (row_M(C_1) \otimes I_D) \widecheck{v}= (row_M(C) \otimes I_D) \widecheck{v}\\ \widecheck{p}_{M+1} & = (row_M(C_2) \otimes I_D)\widecheck{v}= (row_{M+1}(C) \otimes I_D) \widecheck{v}\\ &\vdots \\ \widecheck{p}_{N} & = (row_M(C_{N-M+1}) \otimes I_D)\widecheck{v}= (row_{N}(C) \otimes I_D) \widecheck{v}.\\ \end{aligned}\] Therefore, \(\widecheck{p}=(C\otimes I_D) \widecheck{v}\); i.e., according to Definition 1, the multiagent team converges as \(t\rightarrow \infty\) to an affine formation with respect to the nominal configurations \(c_{(1)}, c_{(2)}, \ldots, c_{(L)}\). The unique parameter vector \(\widecheck{v}\) of this formation can be computed from sets of \(M-1\) agent positions: using \(\widecheck{p}=(C\otimes I_D) \widecheck{v}\) for agents \({j}\) to \({j}+M-2\), \[\tag{29} \widecheck{v} = (G_{j} \otimes I_D)^{-1}\hspace{-1pt}\begin{bmatrix} \widecheck{p}_{{j}} \\ \vdots \\ \widecheck{p}_{{j}+M-2} \end{bmatrix}\hspace{10pt} \forall {j} \in \mathcal{N}_s, \] which concludes the proof.□