文章目录
 
写在前面
预备基础
分层拉普拉斯矩阵
有向图下的仿射队形
  
有向图下的仿射可操控条件
leader和follower分层控制律

 
写在前面
 
原论文标题：Layered Affine Formation Control of Networked Uncertain Systems: A Fully Distributed Approach Over Directed Graphs
 
本文为近期阅读的论文(Dong 2020)的笔记。该论文研究欧拉-拉格朗日系统(以下称EL系统)有向图拓扑下的分布式仿射编队控制。论文重点集中于两处：其一，有向图下的仿射可操控条件；其二，leader和follower分层控制律。
 
预备基础
 
这里默认读者都看过Lin 2016和Zhao 2018，这两篇论文是以下内容的基础，证明不再给出，请自行参阅原论文。由于不同论文所用标志符号不同，本文所用标志符号统一与前文(仿射队形控制原理与stress matrix的构建)一致。
 
分层拉普拉斯矩阵
 
 
 
定义1：nominal formation $(\mathcal{G},r)$称为仿射可操控(affine maneuverable)，当且仅当对任意$q=[q_l^T,q_f^T{]}^T\in \mathcal{A}(r)\in {\mathbb{R}}^{Nd}$，$q_f$可以被$q_l$唯一表示，即
 $$q_f=-((L_{f1}^s{)}^{-1}{L}_{f2}^s\otimes I_d)q_l。$$
 
 
注意：这里的“仿射可操控”其实就是Zhao 2018的“仿射可定位”，整合了Zhao的一部分相关结论。
 
上面定义中用到的拉普拉斯矩阵在论文中也有重新定义，为分层拉普拉斯矩阵(Layered Laplacian matrix)，即
 $$L^{†}=\left[\begin{array}{ccc}0& 0_{N_l}^T& 0_{N_f}^T\\ L_{l2}& L_{l1}& 0_{N_l\times N_f}\\ 0_{N_f}& L_{f2}^s& L_{f1}^s\end{array}\right]，$$
 其中$L_{l1}\in {\mathbb{R}}^{N_l\times N_l}$表示leader之间的拓扑，$L_{l2}\in {\mathbb{R}}^{N_l\times 1}$，表示leader与虚拟agent的拓扑，$L_{f1}^s\in {\mathbb{R}}^{N_f\times N_f}$表示follower之间的拓扑，$L_{f2}^s\in {\mathbb{R}}^{N_f\times N_l}$表示leader和follower之间的拓扑。
 
综上所述，分层拉普拉斯矩阵表示分层的拓扑结构，第一层是普通拉普拉斯矩阵
 $$L=\left[\begin{array}{cc}0& 0_{N_l}\\ L_{l2}& L_{l1}\end{array}\right]\in {\mathbb{R}}^{(N_l+1)\times (N_l+1)}，$$
 第二层是带符号拉普拉斯矩阵
 $$L^s=\left[\begin{array}{cc}{0}^{N_l\times N_l}& 0^{N_l\times N_f}\\ L_{f2}^s& L_{f1}^s\end{array}\right]\in {\mathbb{R}}^{(N_l+N_f)\times (N_l+N_f)}。$$
 整个控制过程的逻辑结构是，一个虚拟agent 0(如：人的输入)控制多个leader，再由leader控制follower。为了完成这个控制过程，需要以下假设和引理。
 
令所有agent的label为$0,1,\cdots ,N_l,\cdots ,N_l+N_f$。前$N_l+1$个组成图${\mathcal{G}}_l$。
 
 
 
假设4：对于第一层的$N_l(N_l\ge d+1)$个leader，图${\mathcal{G}}_l$中存在一个有向生成树，其中root为agent 0。
 
 
 
 
引理1：对于第一层，如果图${\mathcal{G}}_l$中存在一个有向生成树，那么下列声明成立：
 
 
$L_{l1}$非奇异；
所有$L_{l1}$的特征根有正实部；
$-L_{l1}^{-1}{L}_{l2}$的每一个元素非负，每一行和为1。
 
 
证明：前两条证明见Meng 2013的Lemma 2.1，第三条证明见Meng 2010的Lemma 4。$L_{l1}$是一个non-singular M-matrix，满足inverse-positive，即$L_{l1}^{-1}$ exists and $L_{l1}^{-1}\ge 0$ element-wisely。而$L_{l2}$的每一个元素非正，因为agent 0只可能是leader的in-neighbor。因此$-L_{l1}^{-1}{L}_{l2}$的每一个元素非负。注意到$\left[\begin{array}{cc}{L}_{l2}& L_{l1}\end{array}\right]\left[\begin{array}{c}1\\ 1_{N_l}\end{array}\right]=0$。因此，$L_{l2}=-L_{l1}{1}_{N_l}$，即$-L_{l1}^{-1}{L}_{l2}=1_{N_l}$行和为1(全1列向量)。
 
有向图下的仿射队形
 
以下定义和假设出自Zhao 2018，详见前文(仿射队形控制原理与stress matrix的构建)。
 
定义configuration matrix $P(q)$和augmented matrix $\bar{P}(q)$。
 
 
 
假设5：nominal configuration $r$ is generic.
 
 
以下定义和引理出自Lin 2016：
 
若有向图$\mathcal{G}=(\mathcal{V},\mathcal{E})$中存在边$(j,i)\in \mathcal{E}$，方向为$j\to i$，那么$j$是$i$的in-neighbor，$i$是$j$的out-neighbor。
 
 
 
定义2.1：对于有向图$\mathcal{G}$，如果去掉除节点$v\in \mathcal{V}$外的任意$k-1$个节点，仍然存在一条路径(path)从某一节点$u\in \mathcal{U}$到节点$v$，那么节点$v$被称为$k$-reachable from 非单元素(non-singleton)集合$\mathcal{U}$。
 
 
从上面的定义中，我们可以得知：
 
$\mathcal{U}$的元素必定大于等于$k$个，才能保证去掉$k-1$个节点后$\mathcal{U}\ne \varnothing$；
从集合$\mathcal{U}$到节点$v$至少有$k$条互不相交(disjoint)的路径。
 
 
 
定义2.2：有向图$\mathcal{G}$是$k$-rooted，如果存在包含$k$个节点的子集，称为根(root)集，从根集出发所有其他节点都$k$-reachable。
 
 
 
 
定义2.3：对于有向图$\mathcal{G}=(\mathcal{V},\mathcal{E})$，一个根集为
     
      
       
        
         R
        
        
         =
        
        
         {
        
        
         
          r
         
         
          1
         
        
        
         ,
        
        
         ⋯
         
        
         ,
        
        
         
          r
         
         
          k
         
        
        
         }
        
        
         ⊂
        
        
         V
        
       
       
        \mathcal R=\{r_1,\cdots,r_k\}\subset \mathcal V
       
      
     R={r1​,⋯,rk​}⊂V的$k$-生成树(spanning $k$-tree)是一个生成子图(spanning subgraph)$\mathcal{T}=(\mathcal{V},\bar{\mathcal{E}})$，其满足：
 
 
每一个节点$r\in \mathcal{R}$都没有in-neighbor；
每一个节点$v\notin \mathcal{R}$都有$k$个in-neighbor；
每一个节点$v\notin \mathcal{R}$都$k$-reachable from $\mathcal{R}$。
 
 
从上面的定义中，我们可以得知：
 
有向图$\mathcal{G}$如果有$k$-生成树，那么一定$k$-rooted；
如果节点$k$-reachable，那么必然有$k$个in-neighbor。
 
 
 
引理2 (Lemma 2.1, Lin 2016)：图$\mathcal{G}$有一个$k$-生成树，当且仅当图$\mathcal{G}$是$k$-rooted。
 
 
只需证明必要性。令根集为$\mathcal{R}$，并移除所有incoming edge，其他节点仍然$k$-reachable。再移除其他节点的多余incoming edge，只留下$k$个保证$k$-reachable。通过上述两步得到$k$-生成树，利用了$k$-路径的互不相交性。
 
 
 
引理3 (Lemma 4.1, Lin 2016)：对于有向图$\mathcal{G}$，如果它是$k$-rooted，那么相关的$L^s$满足：
 
 
去掉与根节点相关的$k$行和$k$列所得子矩阵的主子式(principal minor)不为0；
去掉与根节点相关的$k$行和任意的$k$列所得子矩阵是非奇异的。
 
 
回顾一下，余子式(minor)$[A{]}_{i,j}$是原矩阵$A$去掉第$i$行和第$j$列后的子矩阵的行列式，如果$i=j$，则为主子式。
 
参考Lin 2016，定义仿射队形可实现(realizable)为：$(L^s\otimes I_d)q=0$当且仅当$q\in \mathcal{A}(r)$。
 
 
 
引理4 (Theorem 4.1, Lin 2016)：假如有向图$\mathcal{G}$有$N\ge d+2$个节点，且$r$是generic。那么仿射队形可实现当且仅当$\mathcal{G}$是$(d+1)$-rooted。
 
 
有向图下的仿射可操控条件
 
 
 
定理1：在假设5条件下，nominal formation $(\mathcal{G},r)$仿射可操控，当且仅当leader集合${\mathcal{V}}_l$有至少$d+1$个节点，同时集合$V_f$中的每一个follower都$(d+1)$-reachable from集合$V_l$。
 
 
证明：(充分性) 满足条件的$\mathcal{G}$是$(d+1)$-rooted，所以有$k$-生成树，仿射队形可实现。再加上$L_{f1}^s$的非奇异性，队形可被唯一确定，即仿射可操控。(必要性) 如果仿射可操控，必然存在$L^s$使得仿射队形可实现，故$\mathcal{G}$是$(d+1)$-rooted满足条件。
 
 
 
假设6：集合$V_f$中的每一个follower都$(d+1)$-reachable from集合$V_l$。
 
 
leader和follower分层控制律
 
 
 
问题1：给定初始队形$\mathcal{G}(q(0))$和nominal configuration matrix $P(r)$，为每一个agent设计基于邻居相对位置和速度的控制律${\tau }_i(t)$，使得$q_l\to -(L_{l1}^{-1}{L}_{l2}\otimes I_d)q_0+p$，且$q_f\to -((L_{f1}^s{)}^{-1}{L}_{f2}^s\otimes I_d)q_l$误差有界，其中$p=[p_1^T,\cdots ,p_{N_l}^T{]}^T$，$p_i$为相对于nominal formation的位移。
 
 
可以看出，$-(L_{l1}^{-1}{L}_{l2}\otimes I_d)q_0$实现consensus，即所有leader收敛于$q_0$，再加上$p$即为相对$q_0$的位移。
 
论文对两层都用了自适应NN控制律(adaptive NN-based control law)，误差有限时间收敛到原点的一个邻域，即practical finite-time stability。
 
注意：这里的practical是针对EL系统的模型不确定性来说的，如果模型完全确定，那么是可以有限时间收敛到原点的。
 
至于自适应NN控制律如何设计，我在这里挖个坑，之后的文章里结合Wang 2009讲。
 
 
 
 
Li, D., Ma, G., Xu, Y., He, W., & Ge, S. S. (2020). Layered Affine Formation Control of Networked Uncertain Systems: A Fully Distributed Approach Over Directed Graphs. IEEE Transactions on Cybernetics, 1–12. https://doi.org/10.1109/tcyb.2020.2965657 ↩︎
 
Lin, Z., Wang, L., Chen, Z., Fu, M., & Han, Z. (2016). Necessary and sufficient graphical conditions for affine formation control. IEEE Transactions on Automatic Control, 61(10), 2877–2891. https://doi.org/10.1109/TAC.2015.2504265 ↩︎
 
Zhao, S. (2018). Affine Formation Maneuver Control of Multiagent Systems. IEEE Transactions on Automatic Control, 63(12), 4140–4155. https://doi.org/10.1109/TAC.2018.2798805 ↩︎
 
Meng, Z., Lin, Z., & Ren, W. (2013). Robust cooperative tracking for multiple non-identical second-order nonlinear systems. In Automatica (Vol. 49, pp. 2363–2372). Elsevier Ltd. https://doi.org/10.1016/j.automatica.2013.04.040 ↩︎
 
Meng, Z., Ren, W., & You, Z. (2010). Distributed finite-time attitude containment control for multiple rigid bodies. Automatica, 46(12), 2092–2099. https://doi.org/10.1016/j.automatica.2010.09.005 ↩︎
 
Wikipedia contributors. (2020, August 29). M-matrix. In Wikipedia, The Free Encyclopedia. Retrieved 08:23, October 8, 2020, from https://en.wikipedia.org/w/index.php?title=M-matrix&oldid=975609653 ↩︎
 
Wikipedia contributors. (2020, May 20). Minor (linear algebra). In Wikipedia, The Free Encyclopedia. Retrieved 02:22, October 8, 2020, from https://en.wikipedia.org/w/index.php?title=Minor_(linear_algebra)&oldid=957799839 ↩︎
 
Zhu, Z., Xia, Y., & Fu, M. (2011). Attitude stabilization of rigid spacecraft with finite-time convergence. International Journal of Robust and Nonlinear Control, 21(6), 686–702. https://doi.org/10.1002/rnc.1624 ↩︎
 
Wang, L., Chai, T., & Zhai, L. (2009). Neural-network-based terminal sliding-mode control of robotic manipulators including actuator dynamics. IEEE Transactions on Industrial Electronics, 56(9), 3296–3304. https://doi.org/10.1109/TIE.2008.2011350 ↩︎
 
 

仿射变换含义
 
 
 
仿射变换是指在几何中，一个向量空间（vector space）进行一次线性变换（linear transformation）并拼上一个平移（Translation ）。所以，本质上仿射变换针对的是某一向量空间（当然该空间中的任一向量）。
 
 
 
 其矩阵表达形式（matrix formal）为： 
 
 
A控制旋转与缩放，b控制平移：
 
 
 我们使用Python语言对之进行演示：
 
import numpy as np
x = np.array((1, 2, 3))
b = np.ones(2)
A = np.random.rand(2, 3)
y1 = np.dot(A, x) + b
                #  array([ 4.17327185,  4.0755495 ])

A_aug = np.hstack((A, b.reshape((-1, 1))))
A_aug = np.vstack((A_aug, np.hstack(np.zeros(3), 1).reshape((1, -1))))
y2 = np.dot(A_aug, np.hstack((x, 1)).reshape((-1, 1)))
                    # array([[ 4.17327185],
                    # [ 4.0755495 ],
                    # [ 1.        ]])


# 上述构造的方式仍稍显繁琐，这里再提供一种方式
A_aug = np.zeros((A.shape[0]+1, A.shape[1]+1))
A_aug[-1, -1] = 1
A_aug[:-1, :-1] = A
A_aug[:-1, -1] = b
np.dot(A_aug, np.hstack((x, 1)).reshape((-1, 1)))

 
文章目录
 
写在前面
预备基础
线性相关和仿射相关
Stress Matrix
Distance Rigidity
  
Affine Formation Control的实现
Affine Image和Stress Matrix的关系
什么条件下Stress Matrix可行
如何构建Stress Matrix
奇异值分解的原理和应用
特征值和特征向量
奇异值分解
常见应用
  
 

 
写在前面
 
原论文标题：Affine Formation Maneuver Control of Multiagent Systems.
 
本文为近期阅读的论文(Zhao 2018)的笔记。该论文研究基于仿射变换的编队控制，重点集中于如何通过控制leader实现maneuver。
 
预备基础
 
column stack(记作vec)的性质：
 $$\begin{array}{rl}\mathrm{vec}(ABC)& =(C^T\otimes A)\mathrm{vec}(B)\\ x\otimes y& =\mathrm{vec}(y{x}^T)\end{array}$$
 configuration matrix定义为:
 $$P(p)=\left[\begin{array}{c}{p}_1^T\\ ⋮\\ p_n^T\end{array}\right]，\bar{P}(p)=\left[\begin{array}{cc}P(p)& 1_n\end{array}\right]，$$
 其中$p_i\in {\mathbb{R}}^d$的column stack叫做configuration $p=[p_1^T,\cdots ,p_n^T{]}^T$。
 
结合上面两个，得到一个多智能体控制中常用的性质：
 $$\mathrm{vec}((LP(p){)}^T)=(L\otimes I_d)\mathrm{vec}(P^T(p))。(1)$$
 该性质在matlab编程中可以简化代码。
 
线性相关和仿射相关
 
线性相关(linearly dependant)要求${\sum }_{i=1}^n{a}_i{p}_i=0$，而仿射相关(affinely dependant)额外要求${\sum }_{i=1}^n{a}_i=0$。这个区别直接反映在configuration matrix上，故
    
     
      
       
        {
       
       
        
         p
        
        
         i
        
       
       
        
         }
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         n
        
       
      
      
       \{p_i\}_{i=1}^n
      
     
    {pi​}i=1n​仿射相关当且仅当$\bar{P}(p)$行线性相关，即${\bar{P}}^T(p)a=0$。
 
仿射相关肯定线性相关，反之不一定。线性无关肯定仿射无关，反之不一定。
 
由于$\bar{P}(p)$有$d+1$列，所以${\mathbb{R}}^d$空间最多有$d+1$个点仿射无关(affinely independant)。相对应的，${\mathbb{R}}^d$空间最多有$d$个点线性无关(linearly dependant)。
 
当
    
     
      
       
        {
       
       
        
         p
        
        
         i
        
       
       
        
         }
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         n
        
       
      
      
       \{p_i\}_{i=1}^n
      
     
    {pi​}i=1n​中存在$d+1$个点仿射无关时，${\mathbb{R}}^d$可以被
    
     
      
       
        {
       
       
        
         p
        
        
         i
        
       
       
        
         }
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         n
        
       
      
      
       \{p_i\}_{i=1}^n
      
     
    {pi​}i=1n​仿射展开(affine span)，此时$\bar{P}(p)$行线性无关，$\mathrm{rank}(\bar{P}(p))=d+1$。
 
 
 
引理1：
     
      
       
        
         {
        
        
         
          p
         
         
          i
         
        
        
         
          }
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
       
       
        \{p_i\}_{i=1}^n
       
      
     {pi​}i=1n​仿射展开${\mathbb{R}}^d$，当且仅当$n\ge d+1$和$\mathrm{rank}(\bar{P}(p))=d+1$。
 
 
Stress Matrix
 
对基于图论定义的formation$(\mathcal{G},p)$，stress是每条边上的标量权重，
    
     
      
       
        {
       
       
        
         ω
        
        
         
          i
         
         
          j
         
        
       
       
        
         }
        
        
         
          (
         
         
          i
         
         
          ,
         
         
          j
         
         
          )
         
         
          ∈
         
         
          E
         
        
       
      
      
       \{\omega_{ij}\}_{(i,j)\in\mathcal E}
      
     
    {ωij​}(i,j)∈E​ ，其中${\omega }_{ij}={\omega }_{ji}\in \mathbb{R}$。
 
equilibrium stress满足
 $$\sum _{j\in {\mathcal{N}}_i}{\omega }_{ij}(p_i-p_j)=0，i\in \mathcal{V}。(2)$$
 可知，如果$\omega$是equilibrium stress，则$k\omega$也是($k\ne 0$)。
 
Distance Rigidity
 
对于一组formation，满足等价和全等的条件为：
 
 
等价(equivalent)：图相同的情况下，任意一条边对应的两个节点，在不同的formation中距离相等。
 
 
全等(congruent)：图相同的情况下，任意两个节点，在不同的formation中距离相等。
 
 
globally rigid：对于一个formation，等价和全等同时成立。
 
universally rigid：对于一个formation，在任意${\mathbb{R}}^{d_1}$空间满足globally rigid，其中$d_1\ge d$。
 
应用式(1)，定义对称的equilibrium stress matrix $\Omega$，我们将平衡条件式(2)重写为
 $$(\Omega \otimes I_d)p=\mathrm{vec}((\Omega P(p){)}^T)=0。(3)$$
 由于$\mathrm{rank}(P(p))=d+1$，故$\mathrm{rank}(\Omega )=n-d-1$。
 
 
 
引理2：给定无向图$\mathcal{G}$和generic configuration $p$，formation $(\mathcal{G},p)$是universally rigid当且仅当存在半正定stress matrix $\Omega$满足$\mathrm{rank}(\Omega )=n-d-1$。
 
 
注意：线性代数里正定性的前提是实对称矩阵。
 
 
 
Consider all of the coordinates of $p=[p_1^T,\cdots ,p_n^T{]}^T$ as a set of numbers $x_1,x_2,\cdots ,x_{dn}$, and consider any non-zero polynomial equation $f(x_1,x_2,\cdots ,x_{dn})$ with integer coeffcients and the numbers (the coordinates) substituted for the variables $x_1,x_2,\cdots ,x_{dn}$. If $f(p)\ne 0$ for every such $f$, we say that the configuration is generic.
 
 
论文(Zhao 2018)中对generic的定义是：the coordinates of all the nodes do not satisfy any nontrivial equations with rational coefficients. 由于有理数可以通过乘以最小公倍数得到整数，该定义与上述定义一致。
 
Affine Formation Control的实现
 
给定nominal configuration $r=[r_1^T,\cdots ,r_n^T{]}^T$和nominal formation $(\mathcal{G},r)$，target formation中的configuration为
 $$p^{\ast }(t)=[I_n\otimes A(t)]r+1_n\otimes b(t)，A(t)\in {\mathbb{R}}^{d\times d}，b(t)\in {\mathbb{R}}^d，$$
 即$p^{\ast }(t)\in \mathcal{A}(r)$，其中$\mathcal{A}(r)$为$r$的affine image。
 
 
 
引理3：$\mathcal{A}(r)$的维度为$d^2+d$当且仅当
     
      
       
        
         {
        
        
         
          r
         
         
          i
         
        
        
         
          }
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
       
       
        \{r_i\}_{i=1}^n
       
      
     {ri​}i=1n​仿射展开${\mathbb{R}}^d$。
 
 
假设1：
    
     
      
       
        {
       
       
        
         r
        
        
         i
        
       
       
        
         }
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         n
        
       
      
      
       \{r_i\}_{i=1}^n
      
     
    {ri​}i=1n​仿射展开${\mathbb{R}}^d$。我们不讨论控制算法的设计和稳定性证明，主要研究下面几个问题。
 
Affine Image和Stress Matrix的关系
 
 
 
引理4：对任意nominal configuration $r$，以下条件始终成立：
 $$\begin{array}{rl}\mathcal{A}(r)& \subseteq \mathrm{Null}(\Omega \otimes I_d)，\\ \mathrm{Col}(\bar{P}(r))& \subseteq \mathrm{Null}(\Omega )。\end{array}$$
 
 
因为
    
     
      
       
        {
       
       
        
         r
        
        
         i
        
       
       
        
         }
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         n
        
       
      
      
       \{r_i\}_{i=1}^n
      
     
    {ri​}i=1n​满足(2)，所以
    
     
      
       
        {
       
       
        A
       
       
        
         r
        
        
         i
        
       
       
        +
       
       
        b
       
       
        
         }
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         n
        
       
      
      
       \{Ar_i+b\}_{i=1}^n
      
     
    {Ari​+b}i=1n​满足(2)，第一个条件成立。由式(3)知，第二个条件成立。
 
假设2：nominal formation $(\mathcal{G},r)$存在满足引理2的$\Omega$。
 
 
 
引理5：满足假设2的条件下，下列条件等价。
 
 

      
       
        
         
          {
         
         
          
           r
          
          
           i
          
         
         
          
           }
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
        
        
         \{r_i\}_{i=1}^n
        
       
      {ri​}i=1n​仿射展开${\mathbb{R}}^d$。
$\mathrm{Null}(\Omega \otimes I_d)=\mathcal{A}(r)$。
$\mathrm{Null}(\Omega )=\mathrm{Col}(\bar{P}(r))$。
 
 
在引理4的基础上，证明引理5只需要证明维度相等。由假设2和引理2，知$\dim (\mathrm{Null}(\Omega \times I_d))=d(d+1)$，再由引理3，知两者维度相等。同理可证第3条。
 
什么条件下Stress Matrix可行
 
 
 
定理1：满足假设1的条件下，nominal formation $(\mathcal{G},r)$仿射可定位(affinely localizable)当且仅当leader节点，即
     
      
       
        
         {
        
        
         
          r
         
         
          i
         
        
        
         
          }
         
         
          
           i
          
          
           ∈
          
          
           
            V
           
           
            l
           
          
         
        
       
       
        \{r_i\}_{i\in\mathcal V_l}
       
      
     {ri​}i∈Vl​​，仿射展开${\mathbb{R}}^d$。
 
 
仿射可定位：已知$(\mathcal{G},r)$，给定leader节点$p_l$可以唯一确定target configuration $p=[p_l^T,p_f^T{]}^T$。也就是说，$A$和$b$被唯一确定。
 
 
 
推论1：如果
     
      
       
        
         {
        
        
         
          r
         
         
          i
         
        
        
         
          }
         
         
          
           i
          
          
           ∈
          
          
           
            V
           
           
            l
           
          
         
        
       
       
        \{r_i\}_{i\in\mathcal V_l}
       
      
     {ri​}i∈Vl​​仿射展开${\mathbb{R}}^d$，那么对任意$p\in \mathcal{A}(r)$，相对应的$A$和$b$被唯一确定为
 $$\begin{array}{rl}A& =\left(\sum _{i\in {\mathcal{V}}_l}{p}_i{\tilde{r}}_i^T\right){\left(\sum _{i\in {\mathcal{V}}_l}{\tilde{r}}_i{\tilde{r}}_i^T\right)}^{-1}，\\ b& =\frac{1}{n_l}\sum _{i\in {\mathcal{V}}_l}{p}_i-A\bar{r}，\end{array}$$
 其中$\bar{r}={\sum }_{i\in {\mathcal{V}}_l}{r}_i/n_l$和${\tilde{r}}_i=r_i-\bar{r}$。
 
 
由推论1可知，
    
     
      
       
        {
       
       
        
         r
        
        
         i
        
       
       
        
         }
        
        
         
          i
         
         
          ∈
         
         
          
           V
          
          
           l
          
         
        
       
      
      
       \{r_i\}_{i\in\mathcal V_l}
      
     
    {ri​}i∈Vl​​仿射展开${\mathbb{R}}^d$当且仅当${\sum }_{i\in {\mathcal{V}}_l}{\tilde{r}}_i{\tilde{r}}_i^T$非奇异。
 
下面研究什么样的$\Omega$满足仿射可定位。定义$\bar{\Omega }=\Omega \otimes I_d=\left[\begin{array}{cc}{\bar{\Omega }}_{ll}& {\bar{\Omega }}_{lf}\\ {\bar{\Omega }}_{fl}& {\bar{\Omega }}_{ff}\end{array}\right]$。
 
 
 
定理2：满足假设1、2的情况下，nominal formation $(\mathcal{G},r)$仿射可定位当且仅当${\bar{\Omega }}_{ff}$非奇异。此时，$p_f$被唯一确定，即$p_f=-{\bar{\Omega }}_{ff}^{-1}{\bar{\Omega }}_{fl}{p}_l$。
 
 
假设3：nominal formation $(\mathcal{G},r)$仿射可定位。
 
假设1、2保证$\Omega$的零空间正好是affine image。假设3保证${\bar{\Omega }}_{ff}$是正定的(因为$\bar{\Omega }$半正定，且${\bar{\Omega }}_{ff}$非奇异)。
 
参考schur complement condition，对于$X=[A,B;B^T,C]$，有：
 
$X>0$ $\iff A>0,C-B^T{A}^{-1}B>0$；
$X>0$ $\iff C>0,A-B{C}^{-1}{B}^T>0$；
如果$A>0$，那么 $X\ge 0$ $\iff$ $C-B^T{A}^{-1}B\ge 0$；
如果$C>0$，那么 $X\ge 0$ $\iff$ $A-B{C}^{-1}{B}^T\ge 0$。
 
如何构建Stress Matrix
 
令$H\in {\mathbb{R}}^{|\mathcal{E}|\times n}$为incidence matrix。已知formation $(\mathcal{G},r)$如何求取$\Omega$满足平衡条件？
 
首先，由$\Omega =H^T\mathrm{diag}(\omega )H$和$\Omega \bar{P}(r)=0$，知${\bar{P}}^T(r)H^T\mathrm{diag}(\omega )H={\bar{P}}^T(r)H^T\mathrm{diag}(\omega )[h_1,\cdots ,h_n]=0$。
 
由$\mathrm{diag}(\omega )h_i=\mathrm{diag}(h_i)\omega$，两者位置互换，得到${\bar{P}}^T(r)H^T\mathrm{diag}(h_i)w=0$。
 
定义$E=\left[\begin{array}{c}{\bar{P}}^T(r)H^T\mathrm{diag}(h_1)\\ ⋮\\ {\bar{P}}^T(r)H^T\mathrm{diag}(h_n)\end{array}\right]$。则$E\omega =0$，因此$\omega$在$E$的零空间里。
 
定义$z_1,\cdots ,z_q\in {\mathbb{R}}^{|\mathcal{E}|}$为$E$的零空间上的一组基。则$\omega ={\sum }_{i=1}^q{c}_i{z}_i$，其中$c_1,\cdots ,c_n\in \mathbb{R}$是一组待定系数。
 
对于宽(fat)矩阵$A\in {\mathbb{R}}^{m\times n}$，其零空间可以写为$I_n-A^{†}A$，然而$E\in {\mathbb{R}}^{n(d+1)\times |\mathcal{E}|}$也可能是长(slim)矩阵。
 
对于长矩阵$A\in {\mathbb{R}}^{m\times n}$，可以通过奇异值分解求$A$的零空间。
 
然后，我们继续确定系数$c_1,\cdots ,c_n\in \mathbb{R}$。令$\bar{P}(r)=U\Sigma V^T$。令$U=[U_1,U_2]$，其中$U_1$包含$U$的前$d+1$列。因为$\bar{P}(r)$的秩为$d+1$，所以$U_1$是非零奇异值对应的左奇异向量，即$\bar{P}(r)$的列空间。同理$U_2$是${\bar{P}}^T(r)$的零空间。
 
根据假设2和引理2，我们要求$\Omega$是半正定，且秩为$n-d-1$。
 
因为$\Omega \bar{P}(r)=0$，故$\Omega U_1=0$，所以$\Omega$在前$d+1$维秩为0，于是剩下的$n-d-1$维需要满秩，即$\Omega$在${\bar{P}}^T(r)$的零空间上正定，对任意$x\in \mathrm{Null}({\bar{P}}^T(r))$，有$x^T\Omega x>0$。换句话说，对任意$y\in {\mathbb{R}}^n$，$y^T(U_2^T\Omega U_2)y>0$。
 
 
 
命题：$\mathrm{rank}(\Omega )=n-d-1$当且仅当$U_2^T\Omega U_2=U_2^T{H}^T\mathrm{diag}(\omega )H{U}_2>0$。
 
 
将$\omega ={\sum }_{i=1}^q{c}_i{z}_i$代入$U_2^T{H}^T\mathrm{diag}(\omega )H{U}_2$，得到${\sum }_{i=1}^n{c}_i{U}_2^T{H}^T\mathrm{diag}(z_i)H{U}_2>0$。
 
定义$M_i=U_2^T{H}^T\mathrm{diag}(z_i)H{U}_2$。可知系数$c_1,\cdots ,c_n\in \mathbb{R}$需要满足条件${\sum }_{i=1}^n{c}_i{M}_i>0$。
 
奇异值分解的原理和应用
 
我们回顾一下奇异值分解(singular value decomposition)。
 
特征值和特征向量
 
如果$A\in {\mathbb{R}}^{n\times n}$是实矩阵，其特征值和特征向量定义为$Aq=\lambda q$，那么$A=QD{Q}^T$是它的特征分解(谱分解)，其中$Q=[q_1,\cdots ,q_n]$是它的特征向量，
    
     
      
       
        D
       
       
        =
       
       
        diag
       
       
        ⁡
       
       
        {
       
       
        
         λ
        
        
         i
        
       
       
        
         }
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         n
        
       
      
      
       D=\operatorname{diag}\{\lambda_i\}_{i=1}^n
      
     
    D=diag{λi​}i=1n​是它的特征根。
 
一般我们会将特征向量转化为标准正交基，使得$Q$是标准正交矩阵。
 
# Eigenvalues and eigenvectors in MATLAB
# such that e are eigenvalues and D = diag(e)
e = eig(A)
# such that A*V=V*D (right) and W'*A=D*W' (left)
[V,D,W] = eig(A)
 
奇异值分解
 
如果$A\in {\mathbb{R}}^{m\times n}$不是方阵，可以进行奇异值分解，即$A=U\Sigma V^T$，其中$U\in {\mathbb{R}}^{m\times m}$和$V\in {\mathbb{R}}^{n\times n}$是正交矩阵，$\Sigma \in {\mathbb{R}}^{m\times n}$是(矩形)对角阵。
 
$U$和$V$分别是对$A$正交输出和输入的基向量，也是$A{A}^T$和$A^{T}A$的特征向量，即
 $$\begin{gathered} (A{A}^T)U=U{D}_u， \\ (A^{T}A)V=V{D}_v。 \end{gathered}$$
 证明：$A=U\Sigma V^T\Rightarrow A^T=V{\Sigma }^T{U}^T\Rightarrow A^{T}A=V{\Sigma }^T{U}^{T}U\Sigma V^T=V({\Sigma }^T\Sigma )V^T$。
 
# Singular value decomposition
# such that s are non-zero sigular values
s = svd(A)
# such that A = U*S*V'
[U,S,V] = svd(A)
 
常见应用
 
求伪逆
 
如果$A=U\Sigma V^T$，那么$A^{†}=V{\Sigma }^{†}{U}^T$，其中${\Sigma }^{†}$是将$\Sigma$非零主对角元求倒数，再转置得到。
 
列空间、零空间和秩
 
对角矩阵$\Sigma$的非零对角元素的个数对应于矩阵$A$的秩。
 
与零奇异值对应的右奇异向量生成矩阵$A$的零空间，与非零奇异值对应的左奇异向量则生成矩阵$A$的列空间。
 
 
 
 
Zhao, S. (2018). Affine Formation Maneuver Control of Multiagent Systems. IEEE Transactions on Automatic Control, 63(12), 4140–4155. https://doi.org/10.1109/TAC.2018.2798805 ↩︎
 
Wikipedia contributors. (2020, September 5). Rank–nullity theorem. In Wikipedia, The Free Encyclopedia. Retrieved 13:55, September 24, 2020, from https://en.wikipedia.org/w/index.php?title=Rank%E2%80%93nullity_theorem&oldid=976828687 ↩︎
 
Connelly, R., & Guest, S. D. (2015). Frameworks, Tensegrities and Symmetry: Understanding Stable Structures. Section 7.2. ↩︎
 
Wikipedia contributors. (2020, August 12). Schur complement. In Wikipedia, The Free Encyclopedia. Retrieved 13:06, September 25, 2020, from https://en.wikipedia.org/w/index.php?title=Schur_complement&oldid=972571695 ↩︎