基于最小弱刚性的编队通信拓扑生成算法

杨秀霞，严 瑄，张 毅

(海军航空大学， 山东 烟台 264001)

由于多智能体系统的广泛应用，对多智能体系统编队队形控制的研究越来越多。在编队队形控制的问题中，编队队形往往是通过对智能体位置的特定约束来实现的。这些约束取决于描述智能体之间交互关系和智能体感知能力的通信拓扑[1-3]。

近年来，基于相对位移信息的分布式编队策略以其在减轻计算量和提高可靠性方面的优势得到了广泛的应用[4-6]。文献[7-9]研究了基于距离的编队控制问题，该方法通过智能体间的距离来确定所需的编队队形，并且只需要每个智能体在其局部坐标系下感知局部相对位移。文献[10-12]中通过将队形图嵌入到指定的空间中，采用由一个特定链接拓扑和所有顶点的坐标组成的框架来描述期望的队形。上述文献为了解决队形问题，都需考虑形成怎样通信拓扑来确定队形框架，最终要求目标队形是刚性的。队形图刚性需要知道大量的距离约束(边)，然而，在实际应用中，这种要求并不容易得到满足。文献[13]中提出了弱刚性，将图中某些距离约束替换成角度约束，从而简化了编队的通信拓扑。文献[14]中给出了弱刚性相关定义，并证明了它的通用性。最小弱刚性编队是编队通信拓扑最简单的一种编队，但它们都没有研究最小弱刚性编队的生成算法。

拓扑控制是在保证网络连通性和覆盖性的前提下，充分考虑无线传感器网络特点，根据不同应用场景，通过节点发射功率调节和邻居节点选择，形成优化的网络结构，以保证完成预定任务。与拓扑控制区别在于，本研究设计编队通信拓扑目的是最大程度减少维持编队队形所需的信息交互量，并保证对应的框架能进行刚性变换。把相对位移的成对内积看作是形成所需队形的约束条件，从而引入了广义刚性的概念，即弱刚性。这种信息在基于距离的编队控制中没有得到有效利用。以相对位移内积为约束条件，利用队形图中的夹角来确定所需的队形。基于上述方法，分别导出了二维和三维空间中框架最小弱刚性的充分条件。利用这些条件，可以很容易得到最小弱刚性编队的生成算法。

1 刚性理论

有n个顶点和m条边的无向图可以表示为G(V，E)，其中V={1，2，…,n}和E⊆V×V分别表示顶点集合和边的集合。本文考虑的图均是无向图，即边(i，j) 和边(j，i)是一样的。在d维空间中，通过分配每个顶点一个坐标pi∈Rd，i∈V，图G(V，E)可以用来描述多智能体编队。刚性理论研究图G(多智能体编队)是否能进行刚性变换(平移、旋转、反射)。下面给出一些有关刚性理论的定义[15]。

(1)

式中：eij=pi-pj，||eij||表示顶点i和顶点j之间的欧式距离。

当gG(p)=gG(q)即||pi-pj||=||qi-qj||，∀(i，j)∈E时，框架(G，p)和框架(G，q)是等价的。当||pi-pj||=||qi-qj||，∀i，j∈V时，框架(G，p)和框架(G，q)是全等的。当存在p的邻域Up，对∀q∈Up，如果框架(G，p)等价于框架(G，q)能得到框架(G，p)全等于框架(G，q)，则称框架(G，p)是刚性的(任意顶点之间有恒定的距离)。当从图G删除任意一条边，刚性框架(G，p)失去刚性，则框架(G，p)是最小刚性的。

(vi-vj)Teij=0， (i，j)∈E

(2)

2 最小弱刚性编队的产生

2.1 弱刚性理论

图1 2种不同类型的框架示意图

(3)

关于弱刚性的定义如下[14]：

(4)

2.2 二维空间最小弱刚性编队

与刚性理论对比易知，修改的刚度函数rG(p)必定存在对应的刚度函数gG(p)。所以可以把判断框架是否是弱刚性的转换成判断框架是否是刚性的，由此可以得到定理2.1。

由定理2.1知所有的弱刚性框架都可以找到与之对应的刚性框架，由此可以得到定理2.2。

定理2.2框架(Gw，p)是无穷小弱刚性的，则框架(Gw，p) 是弱刚性的。

定理2.3框架(Gw，p)是最小弱刚性的，则框架是连通的。

证明：假设框架(Gw，p)是最小弱刚性的，且框架不是连接的。由定义2.1知框架(Gw，p)是弱刚性的，则与框架(Gw，p)相对应的框架(G，p)是刚性的，并且框架(G，p) 也是不连通的。这与刚性理论中刚性框架是连通的相矛盾。所以假设不成立，定理2.3成立。

由于二维空间中生成树是连通图中边最少的，只要找到一种生成树保证它是弱刚性的，这种生成树就是最小弱刚性的。具体如定理2.4。

定理2.4在二维空间中，顶点数n≥3的图是生成树并且对∀i∈Vtr，当|Ni|≥2时，存在2个顶点j，k∈Ni使得eij和eik不共线，则框架(Tr，p)是最小弱刚性的。

令集合H⊆V是由在图Tr中顶点的邻居数大于等于2的顶点组成，即∀i∈H，|Ni|≥2。在连通图Tr中有公式(5)成立：

(5)

又由于图Tr是生成树，所以n=|V|=|Etr|+1=m+1，上式可以写成：

(6)

(7)

2.3 三维空间中最小弱刚性

3 编队生成算法

3.1 二维空间中编队生成算法

由定理2.4知在二维空间中生成满足要求的生成树就得到了最小弱刚性编队，具体算法如下：

步骤3：当|Vtr|

3.2 三维空间中编队生成算法

由定理2.5知在三维空间中将最小刚性编队中的边进行替换就能得到最小弱刚性编队，具体算法如下：

步骤2：设G*=(V，E*)，其中，E*=Φ。根据输入边E的建立刚度矩阵Mc，令i=1，初始化M，作为Mc的首行。

步骤3：若i>|E|，则转入步骤7，否则计算M的秩。

步骤4：若M的秩为3n-6，则转入步骤8，否则把Mc的下一行添加到M形成新的矩阵M′。

步骤5：若M′是行满秩，则令M=M′，记录此对应的边到E*。

步骤6：令i=i+1，然后转入步骤3。

步骤7：G中不存在最小刚性图，输出G=null，直接返回。

步骤8：令E=E*，则G是最小刚性图。

步骤9：将中E删除用点积元素表示的边，得到最小弱刚性边集Ew。

步骤10：令E=Ew，则G是最小弱刚性图。

4 仿真验证

为了验证所提算法的有效性，下面给出实例仿真。在二维和三维空间中考虑16个智能体，假设每个智能体上的传感器相同，通信范围为r=30。每个智能体只能与通信范围内的智能体(邻居)进行通信。所有智能体随机分布在空间中。仿真结果如表1和图2～图7所示：图2表示二维空间中智能体与所有邻居建立通信时的刚性编队；图3表示由文献[16]得到的最优刚性编队(最小刚性编队)；图4表示本文所提算法生成的最小弱刚性编队；图5表示三维空间中智能体与所有邻居建立通信时的刚性编队；图6表示由文献[17]得到的最小刚性编队；图7表示本文所提算法生成的最小弱刚性编队。由表1可知最小弱刚性编队能很大程度的减少编队中边的数量，只有最小刚性编队的一半左右。所以本文提出的算法能极大地简化编队的通信拓扑。

表1 编队中边的数量

图2 刚性编队示意图

图3 由文献[16]得到的最优刚性编队示意图

图4 最小弱刚性编队示意图

图5 刚性编队示意图

图6 由文献[17]得到的最小刚性编队示意图

图7 最小弱刚性编队示意图

5 结论

本文采用了一种弱刚性理论，与刚性理论相比，该理论允许通过更少的边来确定任意维空间中的框架。通过约束框架内相对位移的两两内积来确定框架，这实际上利用了刚性理论中未使用的角信息。给出了最小弱刚性框架的判定条件，并导出了生成最小弱刚性框架的2个充分条件。根据这2个充分条件给出了在二维和三维空间中生成最小弱刚性编队的算法。所得编队在保持刚性的基础上能最大程度减少保持刚性所需要的距离约束的数量。