自然界存在着大量的群体，比如蜂群、鸟群、鱼群、蚁群，这些群体的个体拥有的智能相对简单，但通过群体协作却能让整个种群很好地适应自然界的各种复杂情况[1]，近年来，随着各种具有相对简单功能的机器面世，如无人机、无人车、仿生鱼等智能化群体在农业[2]、物流[3]、军事[4]等领域有了重要作用，因此将具有简单智能个体集合成多智能体系统，研究多智能体系统群体运动的协作方式和效能在对提高机器群体共同完成任务有重要意义。
多智能体集群运动是当前多智能体系统的研究重点之一，其中多智能体集群避障问题在多智能体集群运动中具有基础的研究意义，如：群体跟踪、群体编队、群体覆盖等，只要涉及到群体运动的问题，都要考虑到避障问题，然而在自然环境中，障碍物复杂多变，需要设计合理简洁的适应性避障算法。文献[5]提出了速度障碍法，通过个体和障碍的运动速度计算个体运动的安全区域，从而判断个体是否需要采取避障措施。文献[6]将其运用于大规模个体的情况，并体现出较好的避障效能。Tanner[7]、Olfati[8]、Murray[9]等提出了基于一致性与人工势能函数相结合的群体控制算法，并且讨论仿真了在有障碍时的集群运动情况。文献[10]提出了基于人工势场和极限环方法改进群体编队避障算法。李皎洁[11]基于Olfati-Saber等提出的人工势能框架，系统研究了部分智能体具有全局信息时群体避障的算法。文献[12]基于势能函数和行为规则设计了智能群体在满足避障能力的同时能有效追踪目标的群体控制方法。为简化群体控制，Sakai[13]提出不区分相邻智能体与障碍物的群体算法，简化了算法设计时需要用到的势能函数，仿真结果表明群体在有虚拟领导的情况下能有效避开障碍物。
上述论文的工作多数探讨的是关于凸形障碍物的避障方法，部分虽然探讨了凹形障碍物的避障方法，但这些方法都需部分智能体具有障碍物的中心点，或最大半径等障碍物的几何信息或者全局障碍信息。但在很多实际情况中，障碍物的几何信息难以得到。为简化智能体的信息需求，本文针对部分简单凹形障碍设计了备用领导者更换机制，能在智能群体陷入凹形势能陷阱的时候根据自身群体具备的信息生成只影响新的领导者智能体的虚拟障碍，通过新领导者带领群体绕过凹形障碍。
1 问题描述
在二维平面中运动的群体可用N+2个智能体描述，其中一个智能体为当前领导者，一个智能体为备用领导者，剩余N个智能体跟随当前领导者。将群体中每个个体抽象成质点，每个智能体质点的运动方程满足如下动力学方程：
(1)
式(1)中：xi(t)∈R2代表第i个智能体的二维位置向量；vi(t)∈R2代表第i个智能体的速度向量； ui(t)∈R2代表其控制量。为描述方便，令xl(t)=xn+1(t)表示领导者的位置坐标，xsl(t)=xn+2(t)表示备用领导者的位置坐标。
根据olfaite的群体算法框架[8]，定义单个智能体邻居集，从而描述每个智能体的影响源，并定义智能体的邻居集合如下：在t时刻每个智能体的探测半径为r，其探测到的其他智能体(包括领导者和备用领导者)集合为：
Ni(t)={j|‖xi(t)-xj(t)‖≤r, j≠i}
(2)
障碍物在智能体探测范围之内时，将会产生该智能体对应的β智能体，其位置为障碍物表面距离智能体最近的点，其坐标可表述为：
(3)
对应探测到的障碍智能体集合为：
(4)
式(4)中，No为障碍智能体个数。
为确保函数处处可微分，令参数ε>0，定义智能体之间的距离范数为：
(5)
为使群体运动模型更为简洁，本文根据文献[13]只考虑智能体之间排斥力的思想设计群体控制算法。定义所有种类智能体之间的排斥函数为：
φ(Z)=ρh(z/df)(σ1(z-df)-1)
(6)
式(6)中：
为智能体之间排斥力最大作用距离，且d≤r； ρh(z)表示为如下形式：
(7)
由此可定义每对智能体之间的排斥势能为：
Ψ(z)=
φ(s)ds≥0
(8)
2 控制输入设计
本文定义3种智能体，领导者能探测到运动方向信息，领导跟随者智能体朝预定方向运动。跟随者智能体具有领导者状态信息，跟随领导者运动，并且能探测到一定范围内其他智能体信息和障碍信息。备用领导者智能体与领导者智能体保持相对位置，在领导者陷入凹形障碍产生的局部势能陷阱时，成为新领导者，之前的领导者成为备用领导者，新的领导者根据之前领导者的位置产生虚拟障碍，同时根据探测到的运动方向和实际障碍带领群体离开局部势能陷阱。
令第i个跟随者智能体的控制输入为uf,i，领导者的控制输入为ul，备用领导者的控制输入为usl，分别定义其具体控制输入形式如下。
1) 跟随者智能体的控制输入
(9)
式(9)中：参数
为非负常数；
式(9)中，第一项表示第i个跟随者智能体受到在其探测范围内其他跟随者智能体、领导者及备用领导者的排斥力总合，其中
第二项表示第i个跟随者智能体受到在其探测范围内所有障碍物产生的β智能体对其排斥力的总合。第三、第四项为智能体一致性算法项，确保智能体能跟踪领导者的位置和速度，同时保持群体聚集性。
2) 领导者智能体的控制输入
ul=
(10)
式(10)中：参数
为非负常数；
式(10)中，第一项表示虚拟障碍对领导者的排斥力，其中
为虚拟障碍产生的β智能体，只有当领导者和被领导者角色互换，并且虚拟障碍产生后，Tflag的值为1，否则为零，变换领导者和虚拟障碍产生的方法将在下一部分详细讲述。第二项表示领导者受到其探测范围内实体障碍产生的β智能体对其总排斥力。第三项为智能体一致性算法项，确保领导者在避开障碍后，最终运动的方向为原方向，其中vr为预定运动方向。
3) 备用领导者智能体的控制输入
usl=
(11)
式(11)中：参数
为非负常数；
式(11)中，第一项表示备用领导者受到障碍物的排斥力。第二项表示备用领导者与领导者之间的排斥力。第三项确保备用领导者与领导者保持相对位置，其中xp为领导者和备用领导者期望相对位置向量。最后一项使备用领导者与领导者保持速度一致。
当领导者遇到障碍，并且陷入凹形障碍的局部势能陷阱时，备用领导者变换成为新的领导者，通过生成只有新的领导者能探测到的虚拟障碍填补凹形势能陷阱区域，使新领导者绕过旧领导者进入的势能陷阱区，同时其他智能体，由于探测不到虚拟障碍，它们将跟随新领导者从之前凹形势能陷阱区域撤出并绕过实际的凹形障碍。
当领导者与备用领导者互换时，以旧领导者智能体位置为中心xvo(t)=xl(t)，以领导者与备用领导者相对距离εsl||xl(t)-xsl(t)|| 为半径生成虚拟障碍，其中0<εsl<1。在备用领导者成为新的领导者后，其探测到的虚拟障碍产生的β智能体位置为
其中vo表示虚拟障碍物。
3 稳定性分析
智能体控制输入可根据势能函数求导，如下表述：
uf,i=
(12)
ul=
(13)
考虑到领导者一直以常数vr(t)作为运动参考方向，可定义一个虚拟参考点xr(t)，其中xr(t)=xl(t)，vr(t)为常数。
定义跟随者智能体和领导者相对虚拟参考点的总能量函数为：
Qf(t)=
(vi(t)-vr(t))Τ(vi(t)-vr(t))]+Ul,o+
(14)
式(14)中：
对于满足上述运动方程的智能体组成的系统，在没有遇到障碍物且系统能量有限Qf(t0)=C0的情况下，对t0时刻以后的系统可以有以下结论：
结论(1)任何跟随者智能体与领导者智能体之间的距离不会超过
结论(2)系统中跟随者智能体与领导者智能体的速度将收敛到同一速度值。
证明：
当智能体没有遇到障碍物时Ui,o=0， Ul,o=0，同时另备用智能体与群体具有相对较远的距离，此时可不考虑其对跟随者智能体的影响，即Ui,sl=0。
此时，令
(15)
且
代入上述势能函数得到：
Qf(t) =
(16)
由对称性可知
(17)
能量函数对时间求导数得到：
(18)
由式(18)得式(19)与式(20)，有：
(vl(t)-vi(t))]-
(19)
(vi(t)-vr(t))]-
(20)
式(19)、式(20)相加除以2可得：
(21)
(22)
因此智能体系统函数Qf(t)是一个随时间单调递减的系统，令初始系统能量为 Qf(t0)，则对于任意时刻t>t0，Qf(t)≤Qf(t0)成立。
由式(16)可知：
(23)
可得到：
(24)
即智能体与领导者的距离不超过
结论(1)得证。
同理得到
令：
(25)
(26)
由于任意t>t0时， Qf(t)≤Qf(t0)且
集合Ω={(x(t), v(t))|Qf(x(t), v(t))≤Qf(t0)}为正不变紧集。由于其最大不变集为：
由LaSalle不变集理论[14]，从不变集Ω开始的轨迹都将收敛到其最大不变集S。当
时，可得：v1(t)=v2(t)…vN(t)=vr(t)，因此结论(2)成立。
4 仿真实验与结果分析
下面对基于变换领导者机制的避障算法进行仿真验证。对凹形障碍情况下，22个智能体构成的系统在二维平面内运动，其中包括1个领导者智能体、1个备用领导者智能体及20个跟随者智能体。令单位长度为1 m。
初始时，领导者坐标为[0,0]，跟随者和备用领导者位于[-20,20]×[-20,20]的空间内，速度随机分布在[-5,5]×[-5,5]的区间内，令‖vr‖=10 m/s，vr=[10,0]。智能体之间探测半径和探测障碍物范围半径相等，即r=r′=6，智能体之间和智能体与β智能体之间排斥力最大作用距离为d=4，σ范数中ε=0.5，函数ρh(z)中h=0.9。生成的虚拟障碍物半径长度为εsl||xl(t)-xsl(t)||，其中εsl=0.95。考虑到系统内作用力大小跟系统整体参考速度vr有关，所以设计各智能体控制输入的参数分别为：
凹形障碍物由3个圆形障碍物组成，3个圆形障碍物中心点坐标分别为：
半径为都为13.5。
以下描述为在该状态下，仿真8 000步的结果，其中一步代表0.01 s。初始状态图如图1所示，在二维平面上，智能体由圆点表示，运动方向及大小用红色箭头表示。图2表示智能体最终状态，可明显看到其速度方向保持一致，并且能够形成统一行动的群体。两图中横纵坐标单位为米。
图1 初始智能体状态示意图
图2 最终状智能体状态示意图
图3为多智能体避障路线图，由图3可看到跟随智能体在领导者的带领下能够顺利绕过局部势能陷阱实现避障功能。图4为单独画出领导者和备用领导者智能体的避障路线，由图4可知，其互换了两次领导权，最初的备用领导者在陷入新的势能陷阱后，被再次变换领导位置，从而使群体最终顺利绕过障碍。
图3 避障路线
图4 领导者和备用领导者路线
图5、图6为智能体在X轴和Y轴方向的速度曲线，由图5、图6可知，在第2 000步到4 500步时速度变化较为剧烈，处于避障过程，之后速度收敛到同一数值，表明智能群体绕过障碍物后，智能体系统逐渐达到稳定状态。
图5 X轴方向速度曲线
图6表示智能个体之间最短距离的变化图，在2 000～5 000 步，最短距离变化最为剧烈，但最小距离都大于0.5，表明系统内部智能体之间具有较好的避碰性能，满足群体避障算法的基本要求。
图6 Y轴方向速度曲线
5 结论
本文针对凹形障碍易使智能体陷入局部最小势能陷阱和避障信息简化的问题，设计了基于领导者互换和虚拟障碍机制的多智能体避障算法，该算法不需要智能体事先知道障碍物的几何信息或全局障碍信息，就能实现对凹形障碍物的群体避障功能，通过理论分析该算法的稳定性，仿真验证该算法能够有效避开简单凹形障碍。
[1] QIU H X,WEI C,DOU R,ZHOU Z W.Fully autonomous flying:from collective motion in bird flocks to unmanned aerial vehicle autonomous swarms[J].Science China(Information Sciences),2015,58(12):211-213.
[2] 兰玉彬,王林琳,张亚莉.农用无人机避障技术的应用现状及展望[J].农业工程学报,2018,34(09):104-113.
[3] 傅正堂,胡志华,费海平.无人机危险品集装箱堆场巡查路径优化研究[J].铁道科学与工程学报,2017,14(11):2467-2472.
[4] 张策.美军探索机器人蜂群在作战中的运用[J].军事文摘,2018,417(09):19-23.
[5] FIORINI P,SHILLER Z.Motion planning in dynamic environments using the relative velocity paradigm[C]//Proc.of the IEEE International Conference on Robotics & Automation.1993:560-565.
[6] BERG J V D,LIN M,MANOCHA D.Reciprocal Velocity Obstacles for real-time multi-agent navigation[C]//Proc.of the 2008 IEEE International Conference on Robotics and Automation.IEEE,2008:1928-1935.
[7] TANNER H G,JADBABAIE A,PAPPAS G J.Flocking in Fixed and Switching Networks[J].IEEE Transactions on Automatic Control,2007,52(5):863-868.
[8] OLFATISBER R.Flocking for multi-agent dynamic systems:algorithms and theory[J].IEEE Transactions on Automatic Control,2006,51(3):401-420.03.
[9] SABER R O,MURRAY R M.Flocking with obstacle avoidance:cooperation with limited communication in mobile networks[C]//Proc.of the IEEE Conference on Decision & Control.2003:2022-2028.
[10] 曹建福,凌志浩,高冲,等.基于群集思想的多智能体编队避障算法研究[J].系统仿真学报,2014,26(03):562-566,591.
[11] 李皎洁.具有部分感知能力的多智能体协同避障控制[D].上海：上海交通大学,2015.
[12] YAN J,GUAN X P,TAN F X.Target tracking and obstacle avoidance for multi-agent systems[J].International Journal of Automation and Computing,2010,7(4):550-556.
[13] SAKAI D,FUKUSHIMA H,MATSUNO F.Flocking for multirobots without distinguishing Robots and Obstacles[J].IEEE Transactions on Control Systems Technology,2017,25(3):1019-1027.
[14] KHALILl H K.Nonliear Systems[M].New Jersey:Prentice-Hall,1996.