多运动目标的多无人机协同搜索追踪策略

王洪民,田家强,韦凌云,庄育锋

(北京邮电大学现代邮政学院,北京 100876)

1 引言

无人机(unmanned aerial vehicle,UAV)在民用领域、科研领域和现代战争中都发挥着至关重要的作用,是辅助人类探索自然、抢险救灾的重要工具[1].但是由于无人机的探测能力、机器载荷、续航时间等因素限制,单架无人机难以完成复杂环境中的搜索、追踪、探测等任务,越来越多的应用场景要求多无人机系统协同合作[2].

在无人机协同的研究领域中,区域内多无人机对多运动目标的协同搜索追踪问题具有较高的实际应用价值,受到了国内外学者的热切关注和广泛研究[3–6].由于实际的问题场景复杂多变,解决该问题的方法也各式各样.从无人机的搜索航迹特征来看,可以分为直线搜索任务规划[7–8]与非直线搜索任务规划[9].

在直线搜索任务规划中,为保证搜索效果,通常采用区域全覆盖的搜索方式.文献[10]以减小搜索盲区、提高无人机对区域的有效覆盖率为目的,提出了运动目标垂线搜索算法与运动目标斜线搜索算法.文献[11]研究了传统的垂线搜索算法的不足,提出了并排回寻式搜索算法.文献[12–13]针对不规则凸多边形区域的搜索问题,使用了“Z型”航线完成了对区域的全覆盖搜索.

非直线搜索任务规划与直线搜索任务规划相比,更加注重搜索质量,多采用分布式架构[9]、概率图[14]、滚动时域[15]、区域回访[16]等方法来提高无人机的搜索质量.文献[17]提出了一种智能自组织算法来解决多无人机协同搜索问题,算法采用分布式结构,将全局最优化问题分解为多个局部优化问题,在保证高覆盖率的同时算法具有较好收敛性.文献[18]提出了一种信息融合与协同控制的分布式算法,建立了概率搜索图的更新模型,对目标函数进行优化求解.文献[19]设计了一种将路径图信息和概率图信息相结合的搜索算法,结合基于几何的追踪方法确定无人机的最优路径.

直线搜索任务规划多以任务区域的全覆盖为目标,具有算法简单、适用性强、可实时在线规划等优点.但由于其无法做到对搜索资源的灵活分配,容易对目标存在概率较低的区域投入过多的搜索资源,造成搜索资源的浪费.所以,在面对初始位置未知且随机运动的目标时,直线搜索任务规划的搜索效果较差.非直线搜索任务规划通过建立复杂的目标函数,从全局视角做规划,多采用概率图、滚动时域等方法规划航迹,对于随机运动目标的搜索效果较好.但是面对较大规模的协同搜索规划问题时,场景复杂度的提升会导致航迹规划的计算量大幅增加,进一步导致计算耗时增加,难以满足实时在线规划的需求.

在协同搜索追踪的问题场景下,无人机群需要实时在线完成任务分配和航迹规划等决策工作,对算法的计算效率和运行效果都有较高要求.当任务区域较大、无人机和目标的数量较多时,基于概率图和滚动时域算法的计算效率较低,而传统的直线规划又面临搜索效果不佳的问题.为了解决上述问题,本文提出了以垂线搜索为基础的多无人机协同搜索追踪策略(cooperative search planning strategy based on vertical line search,CSP–BVL),并通过数值仿真对所提策略的有效性进行验证.

2 问题描述及模型构建

2.1 问题描述

图1所示为典型的区域内多无人机协同搜索追踪任务场景.一个n架无人机的无人机编队在任务区域S内搜索并追踪k个运动目标(k可变但k≤n,即运动目标可以进出区域,但是区域内目标数量小于无人机数量).目标在任务区域内初始位置未知,以速度vt随机运动.在执行任务时,无人机首先在区域内搜索,发现目标后进行追踪.故无人机有搜索与追踪两种状态:处于搜索状态的无人机即为搜索无人机,速度为vd;处于追踪状态的无人机即为追踪无人机,速度为vc(vc≥vt).其中,单架无人机只能追踪单个目标,且追踪无人机不再进行其他目标的搜索.

图1 多无人机协同搜索追踪任务示意图Fig.1 Illustration of multi-UAV cooperative search and tracking mission

设计搜索追踪策略,在保证无人机安全的前提下,在规定时间内,搜索并追踪到尽可能多的运动目标.

2.2 传感器模型

传感器的性能决定了无人机的探测范围,无人机的探测范围越大,搜索和侦查的能力就越强.

无人机在高度h处执行搜索任务时,到探测范围中心的距离为e,传感器的探测范围为R,是一个横向为l纵深为w的矩形,如图2所示.传感器的探测频率为f.

图2 无人机传感器探测范围Fig.2 Detection range of UAV sensor

3 多无人机协同搜索追踪策略

本文的策略基于以下几点假设:

1) 无人机性能完全相同;

2) 无人机追踪到目标后不会跟丢;

3) 传感器不会误判和虚警;

4) 无人机之间通信良好.

CSP–BVL策略的结构图如图3所示.该策略包含了上层的任务分配和下层的航迹规划两部分.在任务分配部分,首先设计了航道均分垂线搜索算法(equally-divided course vertical line search pattern,ECVL)来进行搜索无人机的搜索任务分配;然后使用最邻近原则,来对追踪任务进行任务指派;最后根据被追踪的运动目标来进行追踪无人机的追踪任务分配.在航迹规划部分,设计了改进人工势场算法(improved artificial potential field method,IAPF)来规划无人机的航迹.

图3 CSP–BVL策略结构图Fig.3 Strategy structure diagram of CSP–BVL

CSP–BVL 策略创新性地提出了ECVL 算法和IAPF算法,来解决任务分配和航迹规划的问题.除此之外,该策略还创新性地设计了集中式与分布式混合的控制架构,在机群中指定一架飞机作为主机,其他飞机为从机.每架飞机独立调用ECVL算法和IAPF算法来规划自身的搜索任务和飞行航迹.除此之外主机还需要进行任务指派的决策.该架构既不会使主机承受巨量的计算任务以至于影响任务分配效率,又可以实现追踪任务的有序执行.

本章首先介绍了CSP–BVL策略的运行流程,其次介绍了ECVL算法的设计思想和算法流程,最后介绍了使用IAPF算法来规划航迹的必要性与算法设计思想.

3.1 CSP–BVL流程

CSP–BVL策略的伪代码如表1所示.

表1 CSP–BVL伪代码Table 1 Pseudocode of CSP–BVL

具体步骤描述如下:

步骤1(第1行) 初始化.

设置无人机数量n、运动目标数量k、无人机传感器参数F、避撞参数d、无人机飞行参数G、总任务时间T.

步骤2(第2行) 判断任务是否结束.

此步骤由主机进行判断,从机接收主机的任务结束指令.结束标志为:达到总任务时间或所有运动目标都被无人机追踪.其中nt为追踪无人机的数量.若是,结束任务;否则,转步骤3.

步骤3(第3–6行) 任务指派.

该步骤由主机根据最邻近原则进行任务指派.假设所有搜索无人机携带的传感器探测到了kn个新发现的目标,根据最邻近原则,使距离被发现目标最近的搜索无人机转换为追踪状态,指派其去追踪,并更新搜索无人机和追踪无人机的数量.其中ns为搜索无人机的数量,nt为追踪无人机的数量.使用最邻近原则的目的是最小化搜索无人机转追踪后追上目标的时间,最大限度地保障被搜索到的目标不会被跟丢.

步骤4(第7行) 搜索任务分配.

该步骤中,每架搜索无人机独立调用ECVL算法来分配自身的搜索任务.

步骤5(第8行) 追踪任务分配.

该步骤中,每架追踪无人机根据主机的指令和当前被追踪的运动目标的位置来分配自身的追踪任务.

步骤6(第9行) 航迹规划.

通过步骤4和步骤5,每架无人机都已经得到了自身的任务,根据自身的任务与所有无人机的实时位置,每架无人机独立调用IAPF算法来规划自身的飞行航迹.

3.2 ECVL算法

考虑无人机飞行性能与传感器探测性能等约束,结合目标在区域内初始位置未知且随机运动等特征,设计了ECVL算法,来解决多无人机协同搜索的任务分配问题.目标的随机运动使传感器探测得到的区域信息具有时效性,探测信息会在一定时间后失效.探测信息失效后,对应区域内的目标信息再次变为未知,需要对该区域进行重新探测.当目标运动速度较快时,所探测区域信息的有效性会快速消失,进一步加大了搜索的难度.传统的任务分配算法往往存在资源分配失衡、任务收益低等问题.本算法在传统垂线搜索方法的基础上,考虑探测信息时效性的问题,设计了基于平均原则的任务分配机制,为每架无人机分配相同任务量的任务区域,充分利用传感器的探测能力,均匀分散搜索资源.同时设计了基于效能的搜索机制,在任务区域内为每架无人机分配搜索效能最高的垂线搜索航道.

本算法的创新点在于针对初始位置未知且随机运动目标的搜索场景,结合了整体任务平均分配的原则和单机搜索效能的评价,以较少的计算量,快速地进行无人机搜索任务的分配,可满足实时在线规划的要求,具有工程实用性.

算法的伪代码如表2所示.

表2 ECVL伪代码Table 2 Pseudocode of ECVL

ECVL算法的具体步骤描述如下:

算法输入:任务区域位置信息S,搜索无人机的数量ns,所有搜索无人机的位置信息Cs,调用ECVL算法的无人机i.

算法输出:无人机被分配的搜索任务Pi.

步骤1(第1行) 判断无人机i是否在搜索.

判断调用ECVL算法的无人机是否为搜索无人机,若是,则转步骤2,否则,结束算法.

步骤2(第2行) 均分任务区域.

当前共有ns架无人机执行搜索任务,根据平均原则,将任务区域按照搜索任务量平均分成ns部分,每一部分为一个子任务区域.

步骤3(第3行) 指派任务区域.

根据所有搜索无人机的位置信息Cs和步骤2分配好的子任务区域,计算出每架搜索无人机执行每个子任务区域搜索任务的效率矩阵.效率矩阵如下:

其中dij表示第i架无人机搜索第j个子任务区域的价值系数.

依据效率矩阵,通过指派算法求解出最优或较优的任务指派方案.假设无人机i被分配的子任务区域为part-i.

步骤4(第4–6行) 重分配搜素任务.

若无人机i完成了被分配的搜索任务或从未被分配过搜索任务,则需要为其重分配搜索任务.

首先,以搜索效能最大为原则,计算出子任务区域part-i中搜索效能最高的航道course-i.

航道的效能公式如下:

随后根据无人机i的位置Ci和航道course-i,求解出无人机i的搜索任务Pi.引导无人机i进入航道并由航道的起点向终点进行搜索.

步骤5(第7–9行) 继承搜索任务.

如果无人机i暂未完成被分配的搜索任务,此时,继承无人机i未完成的搜索任务.

步骤6(第10行) 输出分配结果.

计算完成后得到无人机i的搜索任务,用于本机航迹规划的计算.

3.3 IAPF算法

考虑任务场景中无人机的避撞约束和实时规划的需求,设计了IAPF算法来规划无人机的飞行航迹,避免无人机之间发生碰撞,保障编队的飞行安全.

无人机在执行任务过程中主要有两方面碰撞风险:一方面,场景中的目标是随机运动的,无人机在追踪目标时需要跟随目标运动,即追踪无人机的运动也是随机的,此时搜索无人机和追踪无人机存在碰撞风险;另一方面,由于无人机的飞行控制会有误差,当两个运动目标非常接近时,有可能导致其对应的追踪无人机之间的碰撞.

APF算法假设无人机在虚拟的力场中飞行,虚拟力场包括产生引力的引力场和产生斥力的斥力场.引力的方向指向无人机的目标航迹点,吸引无人机向其飞行.斥力由障碍物产生,排斥无人机靠近.当引力与斥力共线时APF算法就会出现目标航迹点不可达或受迫性碰撞等问题.

本文提出的IAPF算法的创新点在于设计了方向调整力,使其在面临极端情况时不会因为受力平衡而无法完成预期的航迹规划.在IAPF算法中无人机所受的合力F由引力、斥力和方向调整力3个力合成,无人机由合力驱动,使其在执行自身任务的同时与其他无人机保持距离,避免机间碰撞,保障无人机编队的安全.

IAPF算法的参数如表3所示.其中,Ctt是由任务分配算法分配给该无人机的目标航迹点,Cobs是该无人机面临障碍物的坐标,在多无人机协同搜索追踪区域内多运动目标的任务场景中障碍物为机群中除本机外的其他无人机.

表3 IAPF算法参数定义Table 3 Definition of parameters of IAPF

IAPF算法中合力的计算公式为

其中:F(x)为F(C)在x方向上的分力,F(y)为F(C)在y方向上的分力,Fatt为无人机所受引力,Frep为无人机所受斥力,Fadj为无人机所受方向调整力.

将引力场定义为

无人机所受引力为引力势能的负梯度

其中a为引力增益系数.

将斥力场定义为

无人机所受斥力为斥力势能的负梯度

其中:b为方向调整力增益系数,方向调整力的方向与引力方向的夹角为θ.

4 仿真分析

本节面向典型的多无人机协同搜索追踪区域内多运动目标场景,开展数值仿真研究.首先展示了CSP–BVL策略规划的结果,其次对IAPF算法的参数进行了灵敏度分析,最后进行了对比仿真实验,分析了ECVL算法和运动目标垂线搜索(moving target with vertical line search pattern,MTVL)算法[10]的规划结果,进一步验证了所提算法的有效性.仿真硬件环境为Inter Core i7–8565U 1.8 GHz PC机,编程环境为Python 3.7.

4.1 场景设置与算法参数设置

任务区域为20 km×20 km的矩形,在区域内存在6个运动目标,其初始坐标在区域内随机生成,并以60 m/s的速度随机运动.与之对应有6架无人机执行搜索追踪任务,为了保证无人机能够追踪到目标,设置无人机的追踪速度比运动目标的速度大10 m/s.无人机初始位置和搜索速度如表4所示,传感器的参数如表5所示,IAPF算法的仿真参数设置如表6所示.在本实例中假设无人机之间的临界撞击距离为1 m.

表4 无人机初始状态与速度信息Table 4 Initial state and speed of multi-UAV

表6 IAPF算法参数Table 6 Parameters of IAPF

设定每次仿真时间为1200 s,将仿真时间离散为12000个规划步,规划时间间隔为0.1 s.若在仿真时间内所有的运动目标都被追踪到则判定此次协同搜索追踪任务成功.

4.2 协同搜索追踪规划结果

针对多无人机协同搜索追踪区域内多运动目标的仿真,采用第4.1节的参数设置,使用CSP–BVL策略的一次仿真结果如图4所示.

图4 搜索规划结果Fig.4 Results of searching planning

图4(a)展示了在此次仿真中时间为930.1 s的态势图,在当前时刻所有无人机都已经追踪到了目标,本次多无人机协同搜索追踪多运动目标任务完成.图4(b)展示的是无人机在搜索时飞行的航迹,每架无人机在自己被分配的任务区域内,沿规划好的航道进行垂线搜索,直到发现目标为止.仿真结果表明,CSP–BVL策略可以有效地引导多架无人机对任务区域内的多运动目标进行搜索追踪.在规划过程中,每一个规划步的平均计算时间为0.000996 s,约为1 ms,能够满足协同搜索任务的实时性要求.

4.3 IAPF算法的改进效果和参数影响

在第4.2节的仿真场景中,由于任务区域较大,无人机之间很少发生飞行冲突,为了检验IAPF算法的避撞效果,设计了经典对飞场景,如图5所示.4架无人机初始分布在正方形的4个顶点,以相同的速度向中心O匀速飞行,若不进行航迹优化,无人机会在O点发生撞击.

图5 经典对飞场景Fig.5 Classic face to face flying scene

在该场景下,APF算法会因受力共线,导致目标点不可达的情况产生,如图6(a)所示.而本文提出的IAPF算法,因方向调整力的存在可以有效地应对这种极端情况,如图6(b)所示.

图6 APF算法与IAPF算法无人机航迹对比Fig.6 Comparison of UAV track by APF and IAPF

为了研究IAPF算法的引力系数、斥力系数和方向调整力系数对避撞效果的影响,利用控制变量法来设计实验.设计的3组实验如表7所示.无人机的速度设置同第4.1节.

表7 IAPF算法实验参数设置Table 7 Experimental parameters of IAPF

经典对飞场景下,无人机在成功完成飞行任务的同时,机间的最近距离越大说明算法的避撞效果越好,故本次实验使用无人机间的最近距离作为衡量算法避撞效果的指标.实验结果如图7所示,可以看出在其他参数不变的情况下,随着引力系数的增大,机间的最近距离会逐渐减小,而随着斥力系数和方向调整力系数的增大,机间最近距离会逐渐增大.在本实例的仿真中IAPF算法的设置如表6所示,该参数组合在经典对飞场景中得到的机间最近距离为1.55 m,大于要求的1 m,不会有撞击风险,满足无人机在执行任务时的避撞约束.

图7 无人机之间的最近距离与IAPF算法参数关系Fig.7 Relationship between the closest distance between UAVs and the parameters of IAPF

4.4 算法性能对比

本节通过对比分析ECVL算法和MTVL算法的规划结果,来进一步验证本文算法的有效性.场景和参数设定同第4.1节,针对不同的无人机搜索速度,进行对比实验,每次实验仿真1000次.统计在不同速度条件下两种算法的任务成功率和平均发现目标数量.

ECVL算法和MTVL算法规划结果的对比如图8所示.

图8 规划结果对比Fig.8 Comparison of planning results

由图8(a)可知,在相同的任务场景下,ECVL算法和MTVL算法发现的目标数量均与无人机速度成正相关,即无人机速度越大,发现目标数量越多.无人机速度相同时,ECVL算法发现的目标数量更多;由图8(b)可知,在相同的任务场景下,ECVL算法和MTVL算法的任务成功率均与无人机速度成正相关,无人机速度相同时,ECVL算法的成功率更高.

由于运动目标在任务区域内随机运动且速度较快,所以无人机探测信息的有效性消失得也较快.MTVL算法是对任务区域的全覆盖式搜索,会导致其对局部地区投入过多搜索资源,而且搜索航迹固定,不能灵活变通.对比之下,ECVL算法利用基于平均原则的任务分配机制,均匀分散搜索资源,避免过多的重叠搜索区域,充分发挥每架无人机的作用.同时利用基于效能的搜索机制,引导无人机在最有可能发现目标的航道上执行搜索任务,有效提升了多无人机协同搜索追踪的效果,具有更好的鲁棒性与工程实用性.

5 结论

本文针对区域内多无人机对多运动目标的协同搜索追踪问题,考虑无人机的传感器与避撞等约束和目标随机运动等特征,提出了CSP–BVL策略,并进行了数值仿真实验,得到如下结论:

1) 考虑区域没有先验信息且目标完全随机运动的特征,设计的基于平均原则的任务分配机制与基于效能的搜索机制,可以充分利用无人机传感器的探测能力,均匀分散搜索资源,能够引导无人机在搜索效能最高的航道上执行搜索任务,有效提升了多无人机协同搜索追踪的效果;

2) 考虑无人机的避撞约束,使用了IAPF算法,通过引力、斥力以及方向调整力的共同作用,引导无人机保持安全距离,优化飞行航迹.该算法可以有效避免无人机之间发生碰撞,保障编队的飞行安全;

3) 相比于传统垂线搜索策略,本文策略能够更充分地发挥每架无人机的作用,合理分配搜索资源,引导无人机进行高质量搜索.即使在目标完全随机运动且无任何先验信息的情况下,本文所提出的策略仍然能够以更少的搜索时间,追踪到更多的运动目标.

本文假设无人机探测性能和机间通信良好,暂未考虑传感器探测概率与虚警概率对多无人机协同搜索的影响.后续研究中可以考虑加入传感器的探测概率、虚警概率以及通信的不确定性,进一步完善多无人机协同搜索追踪策略.