具有伪领导者的多智能体系统动态牵制蜂拥控制算法

高晶英，徐 旭，何斯日古楞

(1.呼和浩特民族学院 数学与大数据学院，呼和浩特 010051；2.吉林大学 数学学院，长春 130012)

多智能体系统蜂拥控制问题来源于自然界各种生物群体的蜂拥现象，它们通过彼此之间的相互协作寻找食物或躲避天敌.蜂拥控制的目的有3个，即避免相邻个体之间碰撞；相邻个体之间尽量保持聚集；所有个体的速度尽量保持一致.目前多智能体系统蜂拥控制研究取得了丰富成果，文献[1]研究了有切换拓扑结构的多智能体蜂拥控制问题，提出一种局部自适应牵制控制算法使得当多智能体网络不时刻连通时也能达到蜂拥状态.文献[2]提出了高频反馈鲁棒控制算法，当智能体运动方程含未知参数时该算法可以保证多智能体系统有很好的收敛性和鲁棒性.文献[3]研究了具有扰动非线性系统的多智能体蜂拥控制问题，为了解决每个智能体动力系统的非线性性，引入了一些辅助变量，通过定义有限势能函数保证了多智能体系统的蜂拥控制.文献[4]在Cucker-Smale模型的基础上得到了改进模型，该算法可以实现在有限时间内使得多智能体系统达到蜂拥状态.文献[5]为了减少智能体之间的信息交流次数，采用了有限域delaunay图表示智能体之间的网路拓扑结构，同时删除与智能体网络连通性无关的边，以此提高蜂拥控制算法灵活性.文献[6]研究了含未知参数非线性系统多智能体自适应有限时间蜂拥控制算法，构造了有限势函数保证多智能体网络的连通性.

大部分蜂拥控制算法有一个虚拟领导者，该虚拟领导者可以看作给多智能体系统的指令，但由于可能的外界干扰或内部故障，无法保证多智能体系统时刻获取该指令，从而达不到蜂拥的目的.针对该情况，本文考虑了没有虚拟领导者且具有切换拓扑结构动态牵制蜂拥控制问题，每个智能体的运动方程表示为更一般的二阶系统[7-8].为了使得所有智能体能够聚集在一起，首先引入了伪领导者的概念，从整个智能体网络选择评价指标最低的节点作为群体临时领导者，其次从每个子网络中选择评价指标最低的节点作为牵制节点使其能够收到伪领导者的反馈信息，从而使所有智能体围绕在伪领导者周围.基于动态牵制策略，给出了一种新的控制协议使得具有一般二阶模型多智能体系统在无需假设智能体网络连通的情况下达到蜂拥控制目标.最后给出了一些数值模拟结果，进一步证实算法的有效性.

本文算法与已有的成果有3个方面的不同，首先大部分多智能体系统蜂拥控制算法当中每个智能体动力学方程为简单的二阶系统，而本文算法中由更一般的二阶系统表示每个智能体的运动方程，这更符合实际情况.其次，以往蜂拥控制算法都具有一个虚拟领导者，该虚拟领导者可作为整个智能体网络的运动参考目标，本文没有设置虚拟领导者，而是引入一种伪领导者的概念，伪领导者真实存在且从整个智能体网络中选出.最后，大部分蜂拥控制算法需要假设智能体网络的连通性，本文在无需假设智能体网络连通的情况下，采用动态牵制策略能够保证整个智能体网络的连通性.

1 问题阐述

考虑n个智能体在m维欧式空间上移动，每个智能体的运动方程表示为

其中qi(t),pi(t)∈Rm分别是智能体i在t时刻的位置向量和速度向量，ui(t)∈Rm为智能体i在t时刻的控制输入向量.矩阵X和Y是2×2矩阵，Im是m阶单位矩阵，⊗表示Kronecker积.此时，多智能体系统蜂拥控制问题可以转化为当ui(t)满足什么条件时n个智能体达到蜂拥状态.

2 伪领导者和牵制节点的选择

多智能体网络不连通且没有虚拟领导者时，可以从多个智能体当中选择一个智能体作为临时的领导者，称该智能体为伪领导者.本文提出的动态牵制算法的做法是在每个拓扑切换时刻，把整个网络分成若干个连通子网络，然后从每个子网络中选择一个智能体作为牵制节点，即能够收到伪领导者的反馈信息.

其中d1,d2∈(0,1].式(2)可以看作是一个智能体与其他智能体之间势能和动能的加权总和.评价指标公式的实际运算显示第1项的值远大于第2项，使得第1项具有主导地位.为了使第2项的作用变大，增加了两个参数d1、d2调整第1项和第2项的比值.式(2)的几何意义为越接近智能体网络中心位置的智能体越有可能被选作伪领导者.选完伪领导者之后，重新排列智能体的标号使得伪领导者的下标变成1，图1中的正方形代表伪领导者.

图1 动态牵制策略

伪领导者与虚拟领导者不一样，虚拟领导者可以带领整个智能群体到达某个提前给定的目的地，而伪领导者不能，因为伪领导者也是众多智能体当中的一个智能体，它会受到周围智能体的影响从而无法实现虚拟领导者的作用.但是伪领导者仍然有领导者的部分作用，它可以把自己的反馈信息传达给牵制节点，使得整个智能体网路最终能够达到连通.由于伪领导者是多个智能体当中的一员，它的运动方程依然使用公式(1)表示.根据选择伪领导者的方法，它会随着拓扑结构变化而改变.

牵制节点依然采用类似式(2)的方法选择，不同点在于牵制节点是从每个连通网络中选择而伪领导者是从整个智能体网络中选取，所以选择每个连通网络中评价指标最低的节点作为该子网络的牵制节点.对于具有切换拓扑结构的多智能体系统，由于每个智能体不断更新自己的位置，因此任意两个智能体之间的连边在某一个时刻可能会断开，有时候导致第2类非牵制节点出现.这些第2类非牵制节点由于收不到伪领导者的信息，有可能永远不会与剩下的智能体网络连通.为了第2类非牵制节点能够重新回到智能体网络当中，在每个拓扑切换时刻把整个智能体网络(除去伪领导者)分成若干个连通子网络，之后从每个子网络中选择评价指标最低的节点作为牵制节点，使得在每个时刻所有节点都能够直接或间接的收到伪领导者的反馈信息，最终整个网络能够达到连通的目的.图1(b)为智能体网络在某时刻切换之后的拓扑结构，从该拓扑结构可以看出当出现新的子网络，则根据动态牵制策略，从每个新的子网络中再选出一个节点作为牵制节点，以此来保证整个网络的连通性，图中三角形表示新的牵制节点.

3 控制输入的设计

控制的目的为使多智能体系统(1)能够达到蜂拥状态，根据前面得到的结论，伪领导者的控制输入定义如下:u1=(-ξ21q1+v1)/ζ2.

(3)

其中第1项表示伪领导者的状态反馈项，第2项v1表示伪领导者的协作控制项，v1定义如下形式:

每个智能体i的控制输入定义如下:ui=(wi+vi)/ζ2,i=2,…,n

(5)

其中第1项wi为智能体i的状态反馈项，第2项vi为智能体i的协作控制项.设计控制输入的目的是使所有智能体的速度达到一致且智能体之间不会发生碰撞.为了达到该目的，第1项wi可以考虑如下形式:

wi=-ξ21qi.

(6)

第2项vi可以考虑如下形式:

(7)

其中c1,c2>0，q1和p1分别是伪领导者的位置和速度向量，v1是伪领导者的协作控制项，由于伪领导者受到它周围智能体的影响，所以它的速度是随时间变化的，因此式(7)中加入了伪领导者的协作控制输入部分.如果第i个智能体是牵制节点，则hi(t)=1，否则hi(t)=0.势函数ψα(z)和邻接矩阵A(t)=(aij(t))n×n的表达式已在文献[10]中给出.每个智能体在t时刻的邻域定义为:Ni(t)={j∈V|‖qj(t)-qi(t)‖σ

为了使矩阵X和Y里的元素取的更广泛，在每个智能体的控制输入当中都加入了wi=-ξ21qi项，如果定义wi=0，则可以得到矩阵X中的元素必须满足ξ11=ξ21=0，这使得矩阵X中的元素取值范围变得非常小，并且该条件也包含在假设里面.总之，取wi=-ξ21qi好于wi=0.

式(3)～(7)可以写成统一形式:

其中i=1,2,…,n且如果i=1，则δi=1；否则δi=0.

假设1多智能体网络中每个智能体的动力学方程中矩阵(X,Y)满足以下条件：ζ2ξ11-ζ1ξ21=0.

基于以上假设，动力学方程(9)可以改写为以下形式:

4 算法的稳定性分析

为了给出蜂拥控制算法在控制输入(8)下的稳定性分析，定义系统的总能量函数如下:

并且得到以下结论.

定理1n个智能体的运动方程由式(1)给出，并且用式(8)控制每个智能体.假如初始能量Q0=Q(t0)有限，并且ξ12,ξ22,ζ1和ζ2取合适的值使得μ1>0，μ2≥0和μ3≤0，则所有智能体的速度逐渐达到一致并且智能体之间不会发生碰撞.

证明t1,t2,…表示一系列拓扑切换时刻，并且在每两个连续的切换时刻[ty,ty+1),y=0,1,…内网络G(t)的拓扑结构是不变的，由于拓扑结构的切换性，总能量函数Q(t)在切换时刻是不连续的，但在每个[ty,ty+1),y=0,1,…内是可微的.

且式(11)可以改写为

(14)

由势函数和邻接矩阵的对称性，总能量函数Q(t)求关于时间t的导数，可以得到：

其中Hk(t)∈Rρk(t)×ρk(t)是第k个连通子网络对应的对角矩阵，如果第i(1≤i≤ρk(t))智能体是牵制节点，则Hk(t)的第i对角元素是1，否则Hk(t)的第i对角元素是0.

下面给出每个智能体之间避免碰撞的证明.首先在第1个时间区间[t0,t1)内讨论智能体之间的碰撞问题.假设Q0=Q(t0)<ψα(0)，可以得到在t∈[t0,t1)时刻Q(t)≤Q0<ψα(0)，如果存在某个时刻ts∈[t0,t1)使得两个不同的智能体k和智能体l在时刻ts发生碰撞，即qk(ts)=ql(ts)，则有

5 数值模拟结果与讨论

本文模拟了n=30个智能体在控制输入(8)的影响下在2维平面上运动.30个智能体的初始位置和初始速度分别由区间[0,20]×[0,20]和[-1,1]×[-1,1]随机生成.每个智能体的感应半径为r=4，c1=0.3,c2=0.5，其它参数定义如文献[10]所示.在动力学方程(1)中矩阵X和Y取值为

图2给出了30智能体网络的初始拓扑结构最终拓扑结构.在图2中，实心圆点表示牵制节点，空心圆点表示非牵制节点，正方形表示伪领导者的位置，直线表示智能体之间的邻域关系，箭头表示智能体的速度方向及大小.从图2(a)可以看出初始网路有很高的不连通性.通过本文算法，所有的智能体网络连通且速度达到一致并且与伪领导者的速度一样(图2(b)).

图2 30个智能体初始和最终拓扑结构图

图3(a)给出了所有智能体的运动轨迹，可以清楚地看到每个智能体之间保持相对固定的距离并且所有智能体以相同的速度移动.图3(b)给出了本文算法前10s内的牵制节点变化及数量，很容易看到牵制节点个数随着时间的增长而下降.但是在某些时刻会出现牵制节点个数增长情况，这是因为智能体网络拓扑演化过程中有新的第2类非牵制节点出现，为了能够把第2类非牵制节点转换成第1类非牵制节点，需要重新选择牵制节点，这会导致牵制节点的增长.随着多智能体网络渐进蜂拥过程中，所有智能体逐渐调整它们的位置到期望距离并且渐渐调整它们的速度与伪领导者一样，这会减少第2类非牵制节点的出现且最终整个网络达到连通.图3(c)显示了所有智能体的平均速度与伪领导者速度的误差，很显然该误差逐渐趋于零，这说明所有智能体的速度与伪领导者的速度一样，得到的模拟结果与定理1中的理论结果一致.

图3 30个智能体的蜂拥控制模拟结果

6 结语

本文给出了一种新的动态牵制蜂拥控制算法，使一群智能体跟随伪领导者达到蜂拥，并且考虑每个智能体的动力学方程为更一般形式的二阶系统.首先从整个多智能体网络中选择评价指标最低的智能体作为多智能体网络的伪领导者，之后在每个拓扑切换时刻，把除去伪领导者以外的多智能体网络分成若干个连通子网络，每个连通子网络中选择评价指标最低的节点作为牵制节点，即能够收到伪领导者的反馈信息，从而实现蜂拥控制.同时给出了算法的稳定性分析，并得到所有智能体的速度逐渐达到一致且智能体之间不会发生碰撞.