基于飞蛾信息素寻偶机制的无人机集群协同搜索

刘云昊，邓亦敏，段海滨，魏 晨

(北京航空航天大学 自动化科学与电气工程学院， 北京 100083)

无人化、智能化和集群化是无人机(unmanned aerial vehicle, UAV)发展的必然趋势[1]。目前，无人机集群越来越多地用于协同搜索中。无人机集群协同搜索，指的是在未知环境或者有先验信息条件下，多无人机系统通过去中心化自组网信息共享、分布式决策和协调运动控制，实现快速区域覆盖或者锁定目标位置[2]。在未知环境条件下，协同搜索策略主要是规划路径以实现区域覆盖，常见的方法有Voronoi区域覆盖、精确单元覆盖、多边形覆盖和不相交区域覆盖四类[3]；在有目标先验信息条件下，通常通过在线规划的方式进行协同目标搜索，常见的方法有概率图法[4-5]、信息素图法[6-8]、收益图法[9-10]等。然而这些研究大多以区域覆盖率作为搜索任务的评价指标，针对移动目标的研究较少。

自然界中的生物个体利用简单的规则，形成了鲁棒性高、自适应程度高、可扩展性高的自组织行为[1]。飞蛾，昆虫纲鳞翅目昆虫，在其寻偶过程中，成年雌性飞蛾分泌释放性信息素，引诱雄虫前来交配[11]。针对飞蛾通过性信息素感知视距之外的异性并自发飞行至异性位置的寻偶行为的研究已经取得了一定进展。Groot等[12]发现由于环境的影响，飞蛾的性信息素存在着数量和质量的种间差异。Justus等[13-14]研究表明当处于低浓度均匀信息素环境时雄性粉斑螟蛾更倾向于逆风飞行，而高浓度均匀信息素环境中则会更倾向于选择侧风飞行；当粉斑螟蛾处于非均匀的信息素羽流中时，则会选择与风向成一定角度飞行。Zweerus等[15]证明了雌性绿角翅夜蛾会根据性信号来评估雄性个体，并且通过远离的方式来拒绝交配。Hosseini等[16]发现雄性的绿角翅夜蛾会释放雄性信息素来排斥同性个体。Nakano等[17]研究表明雄性亚洲玉米螟会在接近雌性个体后依据信息素浓度对雌性进行定向。飞蛾依靠信息素的寻偶行为与无人机的搜索任务类似，因此这种飞蛾信息素寻偶机制对于无人机集群协同目标搜索有一定的借鉴意义。

本文面向无人机集群对移动目标的协同搜索，提出了一种基于飞蛾信息素寻偶机制的分布式集群协同搜索方法，并在无人机平台上进行了外场飞行试验。

1 问题描述

假设N架无人机对固定区域内的某一移动目标进行搜索，目标位置和目标的移动策略未知，无人机集群网络拓扑为全连通。当某一无人机满足对移动目标位置锁定条件时，认为协同搜索任务完成。

1.1 搜索区域建模

假设搜索区域为长和宽分别为L和W的矩形。对搜索区域用边长为l的方形进行网格化，如图1所示。定义Ex=W/l为x轴方向网格数，Ey=L/l为y轴方向网格数。以i行、j列网格的编号(i,j)代表网格中心点坐标(xi,yj)，其映射关系如式(1)所示。网格化后的搜索区域映射到信息素图，初始轮次信息素任意网格的信息素数值ρi,j为0。

(1)

图1 搜索区域示意Fig.1 Search area diagram

1.2 无人机和目标建模

忽略无人机和目标的高度变化，将无人机和目标简化为二维场景区域内的质点[5]，并认为无人机和目标移动完成后位于所在网格的中心点上。以第n(1≤n≤N)架无人机所在网格的编号表示无人机n的位置Pn；以目标t所在网格的编号表示目标的位置Pt。考虑无人机和目标的运动速率限制，每一轮次无人机和目标只能从当前网格移动到相邻的网格，如图2所示。

图2 无人机可移动范围示意Fig.2 UAV reachable range diagram

以(δn(x)(k),δn(y)(k))表示无人机n第k轮次的运动策略，考虑搜索区域的边界限制，其满足约束：

(2)

则无人机n第k+1轮的位置可以用式(3)计算：

(3)

设定无人机n锁定目标t的位置的条件为Pt在无人机n的单轮次可移动范围内，即：

(4)

1.3 搜索设备建模

假设目标搜索设备的最大搜索距离为Dr，在Dr范围内，可以得到目标t相对无人机n的距离dn,t和角度θn,t。dn,t和θn,t的计算公式如下：

(5)

其中，d(n,t)r和θ(n,t)r表示目标t相对无人机n的真实距离和角度；δd∈(0,1)为距离误差限比例；δθ∈(0,π]为角度误差限；Nr～N(0,0.5)为随机数。通过式(5)，目标搜索设备得到的距离dn,t在d(n,t)r±d(n,t)rδd范围内和得到的角度θn,t在θ(n,t)r±δθ范围的概率为95%。

2 仿飞蛾信息素寻偶机制的集群搜索建模

模仿飞蛾的信息素寻偶机制，建立飞蛾信息素寻偶行为模型，并映射到无人机的集群协同搜索中。将雌性飞蛾映射为目标t，雄性飞蛾映射为无人机n。数字信息素数值ρi,j的正负分别对应飞蛾雌性信息素的吸引作用[11]和雄性信息素的排斥作用[16]。信息素图按照飞蛾信息素的挥发、传播、分泌机制进行更新，无人机基于雄性飞蛾基于信息素的寻偶行为机制进行运动策略的选择。

2.1 仿飞蛾信息素挥发机制建模

自然环境中，飞蛾释放的信息素会随着时间不断挥发，从而浓度不断降低。模仿这一现象，定义吸引信息素挥发因子v+(v+>0)和排斥信息素挥发因子v-(v-<0)[6]。仿飞蛾信息素的挥发机制，对于全局信息素图中的任意网格，其信息素数值按照式(6)实现更新：

(6)

v+和v-的数值与信息素图的累计效应负相关，类似于PID控制中积分控制项，可以消除搜索过程的稳态误差、提高搜索精度。合理设置v+和v-的数值，可以实现无人机在快速跟踪和精准搜索间的平衡。

2.2 仿飞蛾雌性信息素传播机制建模

雌性飞蛾分泌释放雌性信息素，雌性信息素随风在一定范围内传播，引诱雄性飞蛾前往交配[11]。模仿飞蛾雌性信息素传播机制，定义目标t释放吸引信息素ρt(ρt>0)。考虑目标搜索设备的性能限制，定义以无人机n所在位置Pn为圆心、以dn,t+dn,tδd为半径Rn、角度范围在[θn,t-δθ,θn,t+δθ]的扇形区域为吸引信息素传播区域ROPn。ρt沿着ROPn的弧线向圆心方向传播，如图3所示。

图3 吸引信息素传播区域Fig.3 Attract pheromone propagation range

将ROPn映射到信息素图中，当网格中心坐标(xi,yj)位于ROPn内时，认为该网格受到吸引信息素传播的影响[7]，按照式(7)所示的飞蛾信息素传播机制对网格的信息素数值ρi,j进行更新：

(7)

其中，d(i,j),n为网格(i,j)的中心位置相对无人机n所在网格的中心位置的距离。

2.3 仿飞蛾雄性信息素分泌机制建模

在雄性飞蛾的寻偶过程中，雄性飞蛾分泌的雄性信息素会抑制其他雄性的飞行，从而在求偶过程中起到排斥竞争雄性的作用[16]。模仿飞蛾雄性信息素分泌机制，无人机释放排斥信息素ρu(ρu<0)标记访问过的网格点，排斥其他无人机，提高搜索效率。以无人机n所在网格及其邻近网格作为排斥信息素ρu的可影响区域。可影响区域内的网格的信息素数值按式(8)更新：

ρi,j=ρi,j+ρu

(8)

2.4 信息素图的风向建模

(9)

逆风方向θn(u)和侧风方向θn(c)的计算公式如下：

(10)

逆风方向θn(u)和侧风方向θn(c)的合成方向θn(u+c)的计算公式如下：

(11)

2.5 仿飞蛾信息素寻偶行为机制建模

模仿飞蛾信息素的寻偶行为机制[13-14]，当无人机n处于均匀信息素场时，说明目标t的吸引信息素稳定地传播到无人机n所在位置。此时若局部信息素浓度低，说明目标t与无人机n距离较远，则无人机n选择逆风飞行，接近目标t所在区域；若局部信息浓度高，说明目标t与无人机n距离较近，则无人机n选择侧风飞行，跟随目标运动方向。当处于非均匀信息素场时，说明在当前区域，目标t的吸引信息素的传播并不稳定。此时无人机n选择与风成一定角度飞行，在接近目标位置的同时，离开不稳定区域。在无人机n的可移动范围内，如果信息素数值最大值maxρn所在网格为无人机n所在网格，或者maxρn与ρPn接近时，认定无人机n处于均匀浓度信息素场中；否则认为无人机n处于非均匀浓度信息素场中。定义信息素浓度常数ρf，如果maxρn低于ρf，认为无人机n处于低浓度信息素场中；否则认为无人机n处于高浓度信息素场中。无人机n按照算法1选择飞行方向θn。

算法1 无人机飞行方向选择

无人机n选择的飞行方向θn与运动策略(δn(x),δn(y))的映射关系可由表1得到。

表1 飞行方向与运动策略的映射Tab.1 Mapping of flight direction and motion strategy

2.6 无人机集群避撞策略

无人机集群协同搜索过程中所有可能的碰撞情况，如图4所示,可以归为三类：规划位置重合(见图4 (a))；规划至另一无人机的当前位置(见图4 (b)～(c))；规划路线交叉(见图4 (d))。

(a)规划位置重合 (b)规划至另一无人位置(a)Planning location coincidence (b)Plan to the locattion of another UAV

(c)规划至双方位置 (d)规划路线交叉(c)Plan to bot lacations (d)Planning route crossing图4 无人机机间碰撞情况Fig.4 Collision between UAVs

需要说明的是，由于分布式集群中机间通信的异步特性，即使无人机n规划离开当前位置，另一架无人机规划至无人机n当前位置(见图4 (b))仍被认为是有碰撞风险的情况。

定义cn(f)为碰撞标志常数，通过算法2，无人机n判断本机的运动策略是否会与其他无人机发生碰撞。

算法2 无人机碰撞判断

当cn(f)≥3时，认为无人机n的运动策略(δn(x),δn(y))会引发碰撞，因此将其运动策略修改为(0,0)，即

(12)

在同步通信的无人机集群中，当无人机集群内所有个体完成碰撞判断和运动策略修改后，便可以避免集群内无人机的碰撞。而在分布式无人机集群中，无人机的机间通信往往是异步的，因此设计了如图5所示的无人机集群避撞策略。

图5 无人机集群避撞策略Fig.5 Collision avoidance strategy of UAV swarm

当无人机得到本轮的运动决策后，并不立即执行，而是先将自己的运动策略广播到集群中；T为无人机的等待时间，T大于无人机接收消息的周期，在此期间无人机仍在接收其他无人机的消息。因此，如果由于无人机集群异步通信导致本轮次第一次碰撞判断时未发现碰撞情况，可通过等待T时间后的第二次碰撞判断来避免。

2.7 目标逃逸策略

假设目标搭载和我方无人机相同性能的搜索设备，在Dr范围内，可得到无人机n相对目标t的距离dt,n和角度θt,n，其数值按式(5)计算。考虑目标的逃逸行为，给出如算法3所示的目标移动策略。计算出目标的逃逸方向θt(e)，然后通过表1的映射关系可以得到目标的移动策略(δt(x),δt(y))。

算法3 目标移动策略

根据社会力模型，认为目标受到无人机和区域边界的斥力ft,uav和ft,b，目标根据受到的斥力和选择运动方向。为避免斥力抵消引起“陷阱”和ft,uav与ft,b反向导致目标t向无人机方向飞行等不合理情况的发生，引入侧向力ft(c)进行修正。

3 仿飞蛾信息素寻偶机制的集群搜索实现流程

图6 仿飞蛾信息素寻偶机制的搜索实现流程Fig.6 Search process based on moth pheromone courtship

4 仿真实验

4.1 仿真实验设计

仿真实验参数如表2所示。为说明本文所提方法的有效性，将基于飞蛾信息素机制的协同目标搜索方法和基于蚂蚁信息素机制[18]的方法进行对比。针对动态目标搜索场景，在蚂蚁信息素方法的仿真流程中，增大吸引信息素挥发因子v+至1.5，作为一种改进蚂蚁信息素方法，以验证2.1节的结论。

表2 仿真实验参数Tab.2 Simulation experiment parameters

分别使用基于蚂蚁信息素机制的基本蚂蚁信息素方法、增大v+之后的改进蚂蚁信息素方法和基于飞蛾信息素寻偶行为机制的飞蛾信息素方法在相同场景下进行100次仿真实验，并记录仿真数据结果进行分析。当仿真轮次k≥300时，认为无人机集群没有搜索到目标，本次仿真搜索失败。

4.2 仿真结果分析

100次仿真实验的数据对比如图7所示。基本蚂蚁信息素方法的仿真实验，搜索成功率只有44%，在成功搜索到目标的实验里，平均搜索轮次为132.41，搜索轮次的标准差为74.99。增大v+的改进蚂蚁信息素协同搜索方法平均搜索轮次为83.41，有效搜索轮次的标准差为25.77；而基于飞蛾信息素寻偶机制的协同搜索方法平均搜索轮次为53.87，标准差为1.889 1。基于飞蛾信息素寻偶机制方法的搜索所用的平均轮次最少，且拥有最小的标准差，体现出更高的搜索效率和稳定性。

图7 仿真实验结果对比Fig.7 Comparison of simulation results

取三种方法的最后一次仿真实验，仿真路径对比如图8所示，最终形成的信息素图归一化之后如图9所示。从图中可以看出：基本蚂蚁信息素方法，无人机集群最终形成的信息素图中高数值区域与无人机整体移动路径基本重合，说明其信息素图能很好地反映出目标的整体移动态势，但也增大了过去目标位置信息在无人机运动决策时的影响，因此在对移动目标搜索时的效率较差。增大v+的改进蚂蚁信息素方法，信息素图的高数值区域较小，说明其更多反映了目标的实时态势；但是高数值区域与目标最终位置区域存在较大误差，说明该方法很难抑制传感器误差给运动决策带来的影响。而飞蛾信息素方法得到的信息素图，高数值区域与无人机整体移动路径基本重合，说明其信息素图能很好地反映出目标的整体移动态势，而且该方法基于飞蛾信息素寻偶机制，结合实时信息进行运动策略选择，因此具有更高的效率和稳定性。

(a) 基本蚂蚁信息素方法(a) Basic ant pheromone method

(b) 改进蚂蚁信息素方法(b) Improved ant pheromone method

(c) 飞蛾信息素寻偶方法(c) Moth pheromone courtship method图8 蚂蚁和飞蛾信息素方法搜索路径对比Fig.8 Contrast of path in ant and moth pheromone methods

(a) 基本蚂蚁信息素方法(a) Basic ant pheromone method

(b) 改进蚂蚁信息素方法(b) Improved ant pheromone method

(c) 飞蛾信息素寻偶方法(c) Moth pheromone courtship method图9 蚂蚁和飞蛾信息素方法信息素图对比Fig.9 Contrast of pheromone map in ant and moth pheromone methods

仿真结果表明，在移动目标的搜索问题上，通过适当提高吸引信息素挥发因子v+，可以增强蚂蚁信息素方法对移动目标搜索场景的适应性；而本文的基于飞蛾信息素寻偶机制的集群协同搜索方法具有更高的效率和稳定性。

5 外场飞行试验

以四旋翼无人机作为基于飞蛾信息素寻偶机制的集群搜索方法的飞行验证平台，如图10所示。

图10 四旋翼无人机框架结构Fig.10 Quadrotor UAV frame structure

四旋翼无人机上搭载自组网无线通信设备(数传)，通过自定义通信协议实现集群间的信息交互。在自驾仪的Ardupilot源码基础上编写基于飞蛾信息素寻偶机制的无人机集群目标搜索程序。

5.1 外场飞行试验场景设计

飞行试验场景与第4节中的仿真场景一致。使用3架无人机作为我方无人机，1架无人机作为目标，在固定区域内对所提基于飞蛾信息素寻偶机制的集群搜索方法进行试验。因为搭建的四旋翼无人机平台上没有可以感知目标的搜索设备，所以在搜索过程中敌我双方也要进行通信，以获取对方的位置信息，并分别根据式(5)和式(9)计算出含误差的对方距离和角度。

考虑到无人机本身的定位误差，为保证飞行试验安全，对无人机进行分层处理。分别设置我方3架无人机和1架目标无人机的飞行高度为14 m、12 m、10 m和8 m，在计算距离时，不考虑高度差带来的影响。取等待时间T为1 s，线程1和线程2的运行周期为0.25 s，进行飞行试验。

5.2 外场飞行试验结果分析

基于飞蛾信息素寻偶机制的无人机集群搜索飞行试验的数据结果如图11所示；无人机和目标的飞行路径如图12所示。我方3架无人机起飞之后，通过本文所提的方法对敌方1架无人机进行搜索，目标无人机按照本文提出的目标移动策略进行逃逸。从经纬度数据和路径图可以看出，目标虽然有逃脱我方无人机搜索范围的趋势，但是最终仍被无人机3锁定位置。飞行试验最后形成的信息素图如图13所示，可以反映出目标的整体移动过程。被锁定时无人机和目标的外场实拍如图14所示。

(a) 外场飞行试验纬度数据(a) Latitude data in outdoor flight verification

(b) 外场飞行试验经度数据(b) Longitude data in outdoor flight verification图11 无人机和目标的经纬度数据Fig.11 Longitude and latitude data of UAV and target

图12 外场飞行试验中无人机和目标的移动路径Fig.12 Path of UAV and target in outdoor flight verification

图13 外场飞行试验的信息素图Fig.13 Pheromone map in outdoor flight verification

图14 无人机集群协同搜索外场飞行试验Fig.14 Outdoor flight verification of UAV swarm search

外场飞行试验结果表明，在实际应用场景中，本文提出的基于飞蛾信息素寻偶机制的无人机集群搜索方法可以在目标搜索设备具有一定误差的情况下快速锁定目标的具体位置，具有一定的实用意义。

6 结论

针对可移动目标搜索问题，本文受自然界中飞蛾启发，提出了一种基于飞蛾信息素寻偶机制的无人机集群协同搜索方法。该方法模仿雄性飞蛾在不同信息素场中的行为特点，使无人机在逆风飞行、侧风飞行和与风向成一定角度飞行三种方案中进行选择；考虑无人机集群的避撞约束，设计了异步通信条件下的分布式避撞策略。仿真实验的结果表明了本文所提方法在对单个可移动目标搜索时的有效性和稳定性。飞行试验的结果验证了本文所提方法的实用性。

下一步将继续深入研究飞蛾信息素寻偶机制，开展针对更大规模无人机集群的多移动目标搜索研究和飞行试验。