部分具有引导信息的多领导者蜂拥控制算法∗

丛 凯 张金春 卢 翰

（海军航空大学 烟台 264001）

1 引言

蜂拥行为是指大量的个体利用有限的环境信息和简单的几条规则，组织形成的群体运动。自然界中就有很多蜂拥行为，比如蜂群、鸟群和鱼群［1～2］等。几十年以来，蜂拥行为已经引起生物、物理和计算机等各领域学者的研究兴趣［3～9］，其中代表性的是 Reynolds和 Olfati-Saber［10～11］。他们提出的模型得到了广泛的认可。

现有的研究中［12～16］，大部分蜂拥控制算法都是基于跟踪单个领导者。Reynolds［10］提出的蜂拥控制算法就是基于跟踪的单一的领导者，并且假设所有智能体都具有领导者的位置信息和速度信息，通过理论分析证明了最终能够形成稳定的蜂拥行为。在实际生活中很多情况下同时具有多个领导者，比如蜂群在寻找花粉的过程中根据目的地不同形成多个小蜂群，蚁群为了寻找食物分成不同的行进路线等，所以具有多个领导者的蜂拥控制算法具有很强的实际意义。苏厚胜［17］提出了一种基于多个领导者的蜂拥控制算法，在假设所有智能体都拥有自己需要追踪的领导者的位置信息和速度信息的条件下，通过理论证明了能形成结构稳定的蜂拥行为，并且通过仿真实验验证了算法的准确性。在自然界中，很多情况下只有少数个体具有领导者信息，比如最典型的“毛毛虫效应”，以及大雁迁徙中的“人字形”（群体末尾的大雁是根据其最近邻前方的大雁行动而不是最前方大雁）。在人类生产生活中，每个智能体都有领导者信息就意味着智能体具有很大的探测范围，这对生产成本和技术提出了很高的要求。因此设计一种在多个领导者情况下只需要少数个体具有领导者信息就能形成稳定蜂拥行为的算法具有很强的实际意义。在已有的研究中，文献［18］设计了一种改进的蜂拥控制算法，并将其应用到无线传感器网络中，能够保证在少数智能体具有领导者信息的情况下仍然具有良好的跟踪效果。但是为了保持蜂拥网络的连通性设计了无界的势能函数，难以应用到实际生活中。文献［19～20］在蜂拥控制算法中加入了导航项和阻尼项，以实现领导者、具有引导信息的智能体和自由智能体之间的平衡，但是并没有对算法进行稳定性分析和仿真验证。文献［21］提出了内聚项，即自由智能体能够通过感知其探测范围内的其他智能体的位置和速度，并求得平均位置和平均速度作为内聚项，加强自由智能体对网络的追踪能力。

针对现有工作的不足，总结上述问题的原因，本文在不改变势能函数的条件下，提出了一种改进的部分具有引导信息的多领导者蜂拥控制算法，并且通过理论分析证明了算法的稳定性，最后通过仿真实验验证了算法的有效性。

2 问题描述

2.1 预备知识

在n维平面上，假设存在N个智能体，全部视为质点。将具有领导者信息的智能体称为信息智能体，将不具有领导者信息的智能体称为自由智能体。第i个智能体的运动方程为

其中，qi∈Rn为第i个智能体的位置，pi∈Rn为速度，ui∈Rn为加速度，也就是控制输入。假设存在M个领导者，其运动方程为

对于智能体i，在任意时刻t，将它感知半径内的所有智能体的集合记为其中，‖⋅‖ 为欧几里得范数，r为感知半径。把智能体i视为节点，将它与其他能感知到的节点用无向边连接，则由系统内所有节点和无向边组成的网络构成了一个无向图G(t)。其邻接矩阵为A(G(t))=[aij(t)]，其中

图G(t)的Laplacian矩阵为

其中，Δ(A(G(t))称为度矩阵，对角元素为此节点的度，其余为0。由此定义可知L(G(t))是一个半正定矩阵。

拉萨尔不变性原理［22］：对于一个动态连续系统ẋ=f(x)，若连续函数V(x)存在一阶连续偏导数，且满足：1）∃l∈R+，使集合有界 ；2） ∀x∈Ωc，有V(·x)≤0；定义集合M是S中的最大不变集，则∀x0∈Ωc，当t→∞ 时，x(t)→M。

为了描述智能体在跟踪领导者的过程中速度的一致性，引入极化程度［23］H，定义为

当系统内所有的智能体的速度均匀的指向不同的方向，H=0；H越大，表明速度情况越相同；当所有智能体的速度方向相同时，H=1。

2.2 Reynolds多智能体蜂拥控制模型

1986 年，Reynolds［10］提出了一种蜂拥控制模型，并提出了三条规则：分离、聚合、速度匹配。根据 Reynolds提出的模型，Olfati-Saber［11］提出了如下控制输入算法：

的具体形式为的具体形式为其中，的具体形式为

控制输入ui的具体形式为

这里，hi可以用来描述智能体i是否拥有领导者的引导信息。当hi=1时，智能体i为信息智能体，当hi=0时，智能体为自由智能体。

对第i个智能体来说，通过人工势函数，可以得到它的总势能为

人工势函数ψα(z)满足：1）当时，ψα为最大值；2）当趋近于某一期望值时，ψα为最小值；3）当时，ψα恒为很小的正常数。人工势函数ψα如图1所示。

图1 人工势函数

所有智能体总能量分为两部分，一是所有智能体间的总势能，包括智能体间的势能和智能体与领导者间的势能，二是智能体与领导者间的相对动能，具体形式为

2.3 少数信息智能体的蜂拥控制模型

苏厚胜［17］提出了当所有智能体都为信息智能体时的蜂拥控制算法，并且通过理论分析证明当所有智能体都具有领导者的信息时，最终所有智能体都能跟踪到领导者并且形成稳定的蜂拥行为。但是当智能体群体中存在自由智能体时，由于自由智能体在运动过程中没有领导者的指引信息，并且同时受到不同的信息智能体以及其他自由智能体的作用，所以对于自由智能体来说最终能否跟踪到领导者以及跟踪到哪个领导者很难确定下来。

Couzin［24］的研究指出，在只有少数个体具有领导者信息的蜂拥算法中，蜂拥结果的好坏取决于信息智能体对其他智能体的影响，即信息智能体与领导者的作用以及信息智能体与自由智能体的作用的平衡，如图2。因为具有领导者信息的智能体最终肯定能够跟踪到领导者，所以可以通过加强信息智能体与自由智能体的作用或者减弱信息智能体与领导者的作用这两种方法使自由智能体能够更好地跟踪目标。

本文提出的蜂拥控制算法中，首先对自由智能体进行分类，使自由智能体有明确的跟踪目标；然后加入基于连通分支的内聚项，通过加强信息智能体与自由智能体的作用达到更好的跟踪效果。

图2 智能体相互作用关系图

本文研究具有两个领导者的多智能体系统，即M=2，两个领导者记为α和β。假设N个智能体中各有m个智能体分别跟踪两个领导者，都为信息智能体，其余智能体为自由智能体跟踪领导者α，称为第一类信息智能体跟踪领导者β，称为第二类信息智能体为自由智能体。为了对智能体进行分类，本文采取优先准则，自由智能体根据运动过程中首先遇到的信息智能体的类型确定跟踪目标，具体实现方法为：对于自由智能体j，当智能体没有跟踪目标时，邻接矩阵A中a(i，j)=0，i=1，2，…，m，m+1，m+2，…，2m；当自由智能体j感知范围内出现其他信息智能体时，a(i，j)≠0。因为感知范围内同时出现两类信息智能体的概率可以忽略不计，所以当邻接矩阵中元素1出现在前m列时，可以判断自由智能体j首先遇到第一类信息智能体，确定j跟踪领导者α，将自由智能体j称为第一类自由智能体；当邻接矩阵中元素1出现在后m列时，可以判断自由智能体j首先遇到第二类信息智能体，确定j跟踪领导者β，将自由智能体j称为第二类自由智能体。这样就对自由智能体进行了分类，明确了自由智能体的跟踪目标。

图3 连通分支图

接下来考虑如何加强自由智能体与信息智能体的相互作用。首先建立无向图G(t)的连通分支。目前对图的遍历搜索算法中比较成熟的算法有广度优先搜索算法（BFS算法）和深度优先搜索算法（DFS算法），本文使用BFS算法建立无向图的连通分支。假设在某时刻t自由智能体O在运动过程中跟踪到某第一类信息智能体A，如图3所示。图3表示的是无向图G(t)中的一个连通分支，图中智能体之间的连线表示智能体之间的距离小于智能体的感知范围，即智能体能够相互感知到。在这种情况下，智能体之间能够相互通信，智能体i能将自己的位置信息和速度信息(pi，qi) 或者自己接收到的其他智能体的位置信息和速度信息(pj，qj)传递到与之相邻的其他智能体。基于连通分支的网络连通性，任意智能体都能接收到其他智能体的位置信息和速度信息。因为自由智能体O优先遇到第一类信息智能体A，所以忽略掉第二类信息智能体和第二类自由智能体的影响，其运动受到连通分支中其他第一类信息智能体和第一类自由智能体的作用。连通分支中第一类信息智能体的集合为Niα(t)，第一类自由智能体的集合为Ni(t)，则位置质心和速度质心为

将qˉi和pˉi作为加强自由智能体O与信息智能体相互作用的内聚项就可以得到作为自由智能体的控制输入：

其中，c3，c4为系数。

3 理论证明

对于有2m个信息智能体的多智能体系统，它们的控制输入满足式（9）和式（13），假设系统的初始能量为有限值Q0，那么就有如下结论：

1）从t=0开始，任意一个信息智能体与领导者的距离小于

2）所有信息智能体的速度都会趋近于自身所追踪的领导者的速度

这两条结论就可以保证Rerynolds提出的分离、聚合和速度匹配三条规则。下面对结论进行证明：

首先证明结论（1），它是关于分离和聚合规则的结论。记信息智能体i与它所追踪的领导者的位置和速度差值为 Δqi=qi-qγi和 Δpi=pi-pγi，则

所以

同理，pij-pγij=Δpij。

因此，控制输入ui，势能函数V(q)和能量函数Q(q，p)都可以改写为

对于能量函数Q(q，p)，其中V(qi)对时间t的导数为

其余两项对时间t的导数为

将式（15）中的u和式（16）、（17）代入能量函

i数Q(q，p)得：

4 仿真结果与分析

本文模仿了15个智能体在二维平面中的运动情况。其中，10个智能体为信息智能体，分成5个一组分别跟踪两个领导者，其余5个为自由智能体。参数分别设置为：智能体初始速度为[-1，1]和[-1，1]，初始分布范围为 [0，50]和 [0，50]，智能体感知半径r=6，智能体间期望距离d=5，σ范数的参 数ε=0.1，式（8）中 参 数h=0.9，ϕ(z)中a=1，b=2 ，控 制 输 入 中c1=0.1，c2=0.9，c3=c4=1，程序运行步数loop=500。

首先对传统的蜂拥控制算法进行仿真。图4表示的是传统算法的几种运动状况，图中智能体之间的连线表示智能体之间能够相互感知。从图4中可以看出基本形成了蜂拥状态，大多数的智能体能够跟踪到目标并且形成稳定的蜂拥运动，但是仍有少数智能体没有跟踪到目标。随着时间增加，这些智能体和目标的距离会越来越大，最终无法跟踪目标。这些智能体丢失目标的原因有两个：一是这些智能体在运动过程中没有被其他智能体感知到，没有进入其他智能体形成的连通分支网络；二是这些智能体在运动过程中进入了其他智能体形成的连通分支网络，但是由于受到不同类型智能体的共同作用，导致运动受到多种影响导致最终没有跟踪到目标。

接下来对本文提出的算法进行仿真。图5（a）表示的是智能体的初始分布情况，其初始分布采用随机分布。图5（b）表示的是程序运行500步之后的智能体分布情况，图5（c）和（d）用来表示一般智能体与领导者的速度跟随情况，曲线的数值为智能体的在x和y方向上的分速度与速度大小的比值。从图5（b）中可以看出所有智能体都能跟踪到目标，没有出现智能体丢失目标的情况，图5（c）和（d）的速度情况也可以反映出所有智能体的速度情况都和各自追踪的领导者的速度一致。通过图5与图4的比较可以看出，相比传统算法，加入基于连通分支的内聚项之后，自由智能体与信息智能体的相互作用明显得到了加强，有利于自由智能体更好的明确跟踪目标，其跟踪能力也得到了提升。

图4 传统算法运行结果

为了对本文提出算法的有效性进行进一步验证，本文分别对传统算法和改进算法进行了15次数值仿真。根据上面的理论分析可知，所有信息智能体最终肯定能够跟踪到目标。由于智能体初始分布的随机性，所以即使对于改进算法，仍然难以保证每次所有自由智能体都能跟踪到目标。所以在每次仿真中，不考虑是否所有智能体都跟踪到目标，只记录能够跟踪到领导者与无法跟踪到领导者的智能体的数量，得到统计数据如图6。通过数据可知，使用改进算法后，能够跟踪到目标的自由智能体的数目明显上升，跟踪效率得到了显著提升。

图5 改进算法智能体分布和速度跟随情况

为了对智能体的速度跟随情况做进一步分析，本文选取了程序运行300步后的速度数据做极化程度对比，如图7，改进算法的极化程度稳定值H1=0.997，传统算法的稳定值H2=0.853。从图中可以看出，改进算法的极化程度增长速度较快，并且很快趋近于比较高的稳定值。相比而言，传统算法增长速度较慢，并且稳定值也比较低。

图6 15次仿真统计对比图

图7 极化程度对比图

5 结语

针对多领导者蜂拥控制算法中不具有目标引导信息的智能体在跟踪过程中出现的目标丢失的问题，本文提出了基于连通分支的多领导者蜂拥控制算法，在控制输入中加入内聚项提高智能体的跟踪能力。通过理论分析证明了智能体在速度和距离上能够保持一致，并且通过数值仿真对算法进行了验证，本文算法能够使智能体明确跟踪目标，并且提高智能体的跟踪能力。通过仿真验证可知：基于连通分支的多领导者蜂拥控制算法能够更好地实现多智能体系统的蜂拥控制和目标跟踪。