近年来,随着无人飞行平台科技水平的快速发展,其应用场景已经广泛融入社会生产生活的各个方面。目前,无人飞行平台已经被广泛应用于通信中继、农业植保、搜查救援等多个重要领域[1-3],极大地减轻了相关工作量,产生了巨大的经济与社会效益。但是由于单无人飞行平台的工作能力有限,多无人飞行平台合作执行任务成为目前主流的研究与应用趋势,解决双平台任务协作调度问题是推广到多平台应用的基础,因此本文选择以双无人飞行平台入手解决传感器规划调度问题。
无人飞行平台具有行动便捷、造价低廉等优势,因此现阶段对于地面目标的捕获、探测都是依靠无人飞行平台来进行。在无人飞行平台执行任务之前,需要根据飞行航线、搭载设备、目标情况等对任务进行规划。随着飞行平台集成化程度的提高与所需捕获目标数目的增多,人工制定调度方案已经不能满足实际需求。目前,双无人飞行平台的传感器调度规划主要面临着以下问题。
(1)由于两个无人飞行平台对于同一目标群体进行捕获,因此两个平台的任务之间存在复杂的耦合关系,并且需要考虑平台间的协同问题[4-5]。需要根据无人飞行平台所携带的探测设备与航线对任务进行合理的分配。
(2)在执行任务的过程中,需要考虑多方面的因素。首先,需要保证在规划调度中获得尽可能高的任务收益[6]。其次,在任务中需要最大程度上顾及所有的目标,同时也需要考虑捕获设备的空闲情况。
(3)由于无人飞行平台数据处理能力的限制,平台所搭载的传感器在同一时刻只能捕获一定数目的目标[7]。因此,传感器的分配与捕获目标的取舍都会对任务结果产生巨大的影响。
本文以无人飞行平台航程占比作为任务初步分配指标,采用多传感器共同捕获与任务迁移方法来提高任务收益,针对双无人飞行平台的传感器调度问题提出有效的解决方案,并通过仿真实验验证了算法的有效性。
1 相关工作
无人飞行平台已经被广泛应用到了目标的跟踪捕获领域,如何通过飞行平台所接收的信息规划跟踪方案是一个巨大挑战,根据无人飞行平台目标跟踪算法所应用的方向,可将其分为3类。第1类是基于相关滤波的目标跟踪算法,如Li等[8]提出基于增强记忆的相关滤波算法,通过学习记忆存档等方法使得滤波器可以有效地跟踪目标,但跟踪精度不高。第2类是基于深度学习的目标跟踪算法,如Danelljan等[9]提出通过卷积层将输出映射为响应图确定目标跟踪位置,但需要相关硬件的帮助才能满足任务的实时性需求。第3类是基于相关滤波与深度学习相结合的目标跟踪算法,如Ma等[10]提出先利用卷积层特征调整分辨率,再训练相关滤波器,结合了两者的特征,实现了对目标的有效跟踪,但相关技术还不成熟。
相较于单无人飞行平台,多无人飞行平台协作在时间效率、容错性以及工作范围等方面都明显优于前者,但也面临着调度复杂、碰撞安全等问题。为解决上述存在的问题,越来越多的研究者开始从事多无人平台协作的研究。针对多无人飞行平台的任务规划系统,主要根据自主性分为3类:在低自主性系统中,飞行平台自身无自主行动能力,并按照提前规划的路径执行任务,任务的收益与规划效果密切相关;在一般自主性系统中,无人飞行平台具有一定的自主性,操作人员只需要选定任务区域,无人机即可自主规划任务;在高自主性系统中,无须操作人员干预,系统即可根据外部环境状态的变化自行规划任务。对于多无人飞行平台任务协作,Skorobogatov等[11]对于目前多无人飞行系统的分类、应用及一些技术细节都进行了详细叙述。
在单无人飞行平台的多传感器调度领域,目前已经有部分学者提出了一些可行方案。如赵坤等[12]使用遗传算法,提出一种结合目标价值,解决复杂约束条件的传感器调度方案。张龙龙等[13]使用几何精度稀疏因子作为衡量适应度函数的指标,利用遗传算法实现对于传感器调度的自动规划。刘睿等[14]在文献[12-13]的基础上,根据目标的捕获情况,提出一种目标的拆分合并机制,减轻了目标任务之间的耦合,可以搜索到较为优秀的传感器资源配置方案。在多无人飞行平台的多传感器调度领域,Emami等[15]提出一种使用无人机群收集地面信息的研究方法,通过联合控制无人机速度与采集数据计划尽可能多地减少数据包的丢失,但缺点是任务覆盖的范围较小。Khodaparast等[16]设计了一种基于多无人机系统的数据传输网络,通过控制调度相关传感器的使用,扩大任务的覆盖范围。Zheng等[17]提出了一种基于多无人机多传感器调度的两级自适应变量领域搜索算法,提升了算法的规划效率。Fei等[18]设计了一种使用机器学习方法对多传感器数据进行数据融合的方法,有效提升了多无人机系统执行任务时的精度与收益。由于上述工作解决调度问题的计算时间较长,不能满足对于调度任务实时性的要求[19]。此外,上述工作在进行传感器调度时,并未考虑传感器资源冲突区域的分配,因此浪费了大量的任务收益。为解决在双无人飞行平台背景下,传感器调度中存在的算法耗时与传感器资源冲突区域调度问题,本文设计了结合多传感器共同捕获与任务迁移方法的双无人飞行平台的传感器调度算法。
2 算法原理
2.1 算法框架
本文所设计的算法主要包含4个步骤,算法流程图如图1所示。首先,根据平台航线与目标的位置关系,给每个飞行平台分配预定的任务。其次,通过目标、传感器与飞行平台的适配情况进行预分配,对于稀缺的传感器资源与独立的目标进行标记。再次,以任务收益为依据,对每个平台进行上的传感器与目标的分配进行匹配。最后,对于未完成既定捕获任务的目标进行任务迁移,将未完成的任务迁移到有空闲捕获资源的航段。
图1 算法流程图
Figure 1 Algorithm flowchart
2.2 平台任务分配及评价指标
由于双无人飞行平台的目标种群相同,大部分目标都处于可以被两个平台捕获的位置,因此两个平台的任务之间存在较强的耦合关系。为了简化求解难度,本文算法以每个平台的探测范围与目标的相交距离为依据,利用可探测范围的比例初步分配两个平台之间的任务。对平台任务进行分配后,则将双平台协作的捕获任务简化为了两个单平台的目标捕获任务。无人飞行平台的目标捕获任务可以表示为
(1)
式中:Ci,j为目标j在平台i上分配的捕获任务次数;Li,j为平台i所途径目标j的航程长度;Sj为目标j可以被两平台所捕获的总航程长度;
为目标j所需的最大有效捕获次数。
为了直观地比较算法的结果,本文采用与文献[14]相同的评价机制。任务收益P的定义如下:
(2)
(3)
式中:Ci为目标i所捕获的总次数;
为目标i的最大有效捕获次数;
为目标的最小有效捕获次数;Threat为目标的威胁程度。
由式(2)可知,当目标i满足最大有效捕获次数以后,目标i任务收益不会增加,因此,当捕获次数
后,将停止对于目标i的捕获。
2.3 目标及传感器的预处理
由于传感器资源是有限的,目标之间存在竞争关系,为了减少目标争夺传感器资源的情况,需要在分配之前对于目标与传感器进行预处理操作。目标的预处理如图2所示。
图2 目标的预处理
Figure 2 Preprocessing of the target
图2中,F1与F2为双无人飞行平台的预定航线,虚线代表所属目标可被捕获的空间范围。目标T1、T2、T5均可被两个无人飞行平台捕获,目标T3仅可被平台F2所在的航线捕获,T4仅可被F1所在航线捕获,因此,由于T3与T4的独立归属性将其标记为独立目标,在对相应的平台进行规划调度时,提高相对应目标的调度优先级。
在进行调度任务规划之前,对于目标进行逐个的判断,记录可以用来对目标Ti进行捕获的所有传感器Sj。如图3所示,目标T2可以被传感器S2、S5、S6与S9捕获,因此目标T2在传感器调度中的选择较多,而目标T4、T5、T7与T8仅可以被传感器S2捕获。如果目标T2分配到了传感器S2,那么在后续的调度中,上述只有1个可用传感器的目标就有很大的概率没有可用的传感器。将传感器S2标记为稀缺传感器后,在进行传感器调度时,目标T2、T6就会优先选择其他非稀缺传感器,可以有效地降低对于稀缺传感器资源的竞争。
图3 传感器的预处理
Figure 3 Preprocessing of the sensor
2.4 传感器的调度分配
传感器调度中最重要的工作就是分配合适的传感器、目标与平台组合,为了解决传感器调度中调度规模大以及目标较多不易处理等问题,本文设计了航段拆分与多传感器协同捕获的策略。由于飞行平台的航线由多个连续航段组成,因此每一航段上都存在着若干个需要捕获的目标。如果从整个航线的角度对传感器进行规划调度,那么调度的规模相较于每一航段来说是倍数式增长的;从航段角度入手逐段解决调度问题,需要考虑的规划调度的规模就会有大幅度的减少,拆分操作的定义如下:
Fi=[Fi-1,Fi-2,…,Fi-n];
(4)
(5)
式中:Fi代表第i条航线;Fi-j代表i航线上的j航段同时由Fi-j组成1个捕获状态列表;OT1,1代表航段Fi-j在第1个捕获位置上目标T1的状态,当状态为1时表示对此位置进行捕获操作,为0时表示不进行捕获。
多传感器协同捕获可以有效地解决目标较多时,某一目标对传感器资源长时间占用的问题。如图4所示,假设无人飞行平台上共搭载了4个捕获传感器,对5个等距且捕获次数相等的目标都可以进行捕获,箭头表示飞行平台的航向,点线表示目标可捕获的范围,由于篇幅原因部分目标的可捕获航段进行了省略。在使用单一传感器捕获目标的情况下,飞行到T5时前4个目标已经占据了所有可用传感器。当采用多传感器协同捕获的策略后,在目标T1进入捕获范围之后,4个可用传感器对T1进行协同捕获,捕获效率将提升4倍;当目标T2进入捕获范围以后,对于目标T1只保留主捕获传感器,将剩余3个传感器全部释放给目标T2。采取多传感器协同捕获目标后,目标T1的捕获距离缩短了3/5,T2的距离缩短了2/5,当目标T5进入捕获范围之后,存在2个可用传感器,解决了单传感器捕获中目标占据传感器资源时间较长的问题,减轻了传感器的调度压力。
图4 多传感器协同捕获
Figure 4 Multi-sensor collaborative capture
对于传感器的调度,本文采取的规划方法是按捕获顺序逐个进行的,以任务收益为基础对传感器进行规划调度。具体操作如下。
步骤1 将航线按航段拆分,将航段所对应目标的捕获任务按航段所占航程的比例进行分配,初始化每一航段的传感器状态集合Aa,i并读取在传感器预处理中得到的可用传感器列表Ij。(其中,a表示传感器标号,i表示航段编号,j为目标编号)。
步骤2 对于第i航段的目标j根据其可用传感器列表Ii,检查在目标捕获起始位置传感器的空闲情况。
步骤3 如果存在空闲的传感器a,则将目标j加入到Aa,i中,对于处于占用状态的传感器,检查占用传感器资源的目标中是否存在本传感器非此目标主捕获传感器的情况,如果存在则释放相关资源,释放的目标中未完成捕获任务的部分转移到释放目标的主捕获传感器的任务中。将目标的捕获任务均分给当前所有对于目标j的可用空闲传感器。如果不存在可用传感器,则执行步骤4。
步骤4 根据当前目标j的可用传感器列表Ij,读取列表中占用传感器的目标编号,并计算目前占用Ij传感器中所有目标与目标j重叠的捕获航程,选择重叠捕获航程距离Lmin的最小的目标Tmin。目标j仅需完成本航段所预定捕获任务即可,如本航段的可捕获航程大于预定捕获任务,那么两者之间存在差值Lj。若满足Lj≥Lmin,那么当前目标j的捕获任务的起点则移动到目标Tmin的终点处,同时当前目标j的捕获任务的终点后移距离Lmin;如果Lj<Lmin,则执行步骤5。
步骤5 将当前目标j的捕获起点与终点向后移动Lj后,计算目前占用Ij传感器中所有目标与目标j重叠的捕获航程与威胁程度的乘积,若目标为独立目标则将目标威胁程度加1进行计算,此结果为重叠航程的捕获价值。选取具有最小重叠价值Pmin的目标TPmin对比目标j的重叠价值Pj。若满足Pj≥Pmin,则将TPmin的终点截断到目标j的起点;若满足Pj<Pmin,则将j的起点移动到TPmin的终点之后。
在传感器状态集Aa,i中,对于实施目标捕获的航段位置使用1进行标记;对于可进行目标捕获的航段,若未进行捕获的位置使用-1进行标记。图5表述了所采用方法的步骤。对目标T2进行任务调度时与目标T1发生资源竞争,此时T2处于未安排捕获任务的航段长度满足T1与T2冲突航段移动条件,因此T2的调度任务的起点与终点后移即可解决传感器资源竞争问题。
图5 重叠捕获航段的移动
Figure 5 Movement of overlapping capture flight segments
2.5 任务迁移
在传感器调度过程中,由于资源冲突问题,会导致部分目标的预定捕获任务不能完成,因此设计任务迁移机制将未完成的任务通过迁移到本目标的其他航段,或者迁移到本传感器下其他有空闲资源目标的航段来对未完成的任务进行补分配。具体流程如下。
步骤1 对于未完成既定捕获任务的目标j,检测此目标是否在多个航段上被捕获,如果可以则执行步骤2,否则执行步骤3。
步骤2 统计目标j在所有航段上未进行捕获任务的航段的传感器状态列表的空闲情况,若上述传感器资源占用未超出上限,则可将此位置作为任务迁移的选择。若执行此操作后目标j仍有任务未完成,则执行步骤3。
步骤3 检测所有航段上与目标j存在资源竞争关系的目标,监测竞争目标是否存在未进行捕获任务航段的传感器资源占用未超出上限的情况,若存在则可将竞争目标目前占用的传感器资源迁移给目标j。在任务迁移之后,迁移目标的捕获次数会发生如下变化:
(6)
ETx=CTx+MTx。
(7)
式中:CTx表示目标Tx的捕获总次数;n为航线数;m为航线上的航段数;MTx为迁移的捕获次数。
为了便于理解任务迁移的具体流程,图6展示了步骤2中同目标之间任务迁移的示意图。在航段1、2上对同一目标都可对其进行捕获,但是由于传感器资源的竞争关系,致使在航段1上有部分任务未完成。经过搜索发现同一目标在航段2上存在部分空闲资源,那么即可将在航段1上未完成的任务迁移到航段2的任务上。
图6 同目标之间任务迁移
Figure 6 Task transfer between the same target
3 仿真实验
为了验证双无人飞行平台的多传感器调度算法(multi-sensor scheduling algorithm for dual unmanned flight platforms,DUFP-MSS)在双无人平台任务环境下的性能,本文选取文献[14]中的GA-TSP作为对比算法,从调度规划时间与调度任务收益两方面对算法的性能进行评估。本文选取10个不同目标个数的测试问题进行比较。出于数据安全和保密性考虑,测试问题的航线以及目标相关的参数依据实际航线的数据特征和规律重新生成,其中目标所处高度及目标威胁程度等参数与航线的固有属性相关,一旦航线确定这些参数也成为固定值。算法在每个测试问题上独立运行30次,表1分别记录了10个测试问题中捕获目标的个数。测试问题的详细信息可在https:∥github.com/cilabsxd/DUFP-MSS-Test-Data下载。
表1 测试问题的目标个数
Table 1 Target number of test questions
测试问题目标个数测试问题目标个数问题1301问题6361问题2300问题7310问题3314问题8322问题4275问题9289问题5292问题10261
表2记录了DUFP-MSS与GA-TSP在10个测试问题上独立运行30次的平均时间与方差。由结果可知,GA-TSP的运行速度相较于DUFP-MSS更慢,并且30次运行时间的方差较大。这是因为GA-TSP采取进化算法来解决规划问题,由于传感器规划调度问题属于有较强约束的问题,因此GA-TSP生成子代的过程中不易生成可行解,浪费了大量的运行时间,而DUFP-MSS在进行调度安排时采取逐段求解的方法,减少了大量的约束条件,运行速度更快。
表2 算法的运行时间
Table 2 Algorithm running time
测试问题运行时间/sGA-TSPDUFP-MSS问题12.65e02±1.595.16e-01±1.02e-01问题22.36e02±1.634.63e-01±1.96e-02问题32.55e02±1.194.62e-01±1.23e-02问题42.59e02±2.723.88e-01±1.52e-02问题52.84e02±1.874.61e-01±9.54e-03问题64.40e02±1.56e016.80e-01±1.99e-02问题73.40e02±3.48e014.96e-01±4.80e-03问题85.47e02±6.40e015.59e-01±2.21e-02问题93.06e02±8.444.31e-01±1.06e-02问题102.98e02±1.353.47e-01±7.06e-03
表3记录了DUFP-MSS与GA-TSP在10个测试问题上独立运行30次的平均任务收益。DUFP-MSS在10个测试问题上的结果都明显优于GA-TSP,这是由于DUFP-MSS采取了逐段调度的方法使得传感器资源的竞争减小,并且采用了任务迁移的补分配机制。而GA-TSP在进行调度规划任务时,不能解决传感器资源竞争的问题,且没有考虑传感器中存在稀缺资源的问题。通过比较可知,DUFP-MSS无论是在运行速度还是任务收益上都优于GA-TSP。DUFP-MSS在计算任务收益时,使用目标威胁程度作为主要参考依据,在对同一任务进行重复多次调度时,由于任务中所有目标的威胁程度不变,因此所有目标的优先调度顺序也是不变的。DUFP-MSS多次调度的任务收益为定值,所以方差为0;而GA-TSP在进行任务调度时,任务收益与其随机初始化种群有一定联系,此外在进化过程中突变是随机的,因此多次调度的任务收益会有波动,其任务收益具有一定的方差。
表3 算法的任务收益
Table 3 Algorithm task benefits
测试问题任务收益GA-TSPDUFP-MSS问题12.09e04±1.52e023.00e04±0问题21.74e04±9.57e012.53e04±0问题31.79e04±1.05e022.15e04±0问题41.96e04±1.34e022.45e04±0问题51.82e04±1.07e022.34e04±0问题62.82e04±1.76e023.57e04±0问题71.84e04±1.44e022.43e04±0问题82.49e04±1.99e023.23e04±0问题91.80e04±9.18e012.07e04±0问题101.63e04±1.08e021.90e04±0
4 结论
本文通过将无人飞行平台任务分配、目标及传感器预处理、传感器调度分配与任务迁移相结合,提出了一种解决双无人飞行平台的多传感器调度问题的高效算法,可以在极短时间内给出一个较为合理的传感器调度方案。通过比较现有算法,验证了DUFP-MSS的有效性。DUFP-MSS相较于GA-TSP可以取得较高的任务收益,同时运行时间减少了3个数量级,在算法稳定性方面也具有较大的优势。
在双无人飞行平台的多传感器调度问题领域仍有一些问题没有得到充分的研究。首先,目前解决传感器资源冲突问题是从局部考虑的,下一步需要研究如何从全局去协调传感器解决资源冲突问题。其次,多无人飞行器协同工作已成为发展与应用的主要趋势,如何协同多个飞行器共同执行任务并进行合理分配仍需要进一步的研究。
[1] JI B F, LI Y Q, CAO D, et al. Secrecy performance analysis of UAV assisted relay transmission for cognitive network with energy harvesting[J]. IEEE Transactions on Vehicular Technology, 2020, 69(7): 7404-7415.
[2] TSOUROS D C, BIBI S, SARIGIANNIDIS P G. A review on UAV-based applications for precision agriculture[J]. Information, 2019, 10(11): 349.
[3] PANDA K G, DAS S, SEN D, et al. Design and deployment of UAV-aided post-disaster emergency network[J]. IEEE Access, 2019, 7: 102985-102999.
[4] 张方方, 张文丽, 王婷婷. 基于速度补偿算法的多机器人编队控制研究[J]. 郑州大学学报(工学版), 2022, 43(2): 1-6, 14.
ZHANG F F, ZHANG W L, WANG T T. Research on multi-robot formation control based on speed compensation algorithm[J]. Journal of Zhengzhou University (Engineering Science), 2022, 43(2): 1-6, 14.
[5] 高岳林, 杨钦文, 王晓峰, 等. 新型群体智能优化算法综述[J]. 郑州大学学报(工学版), 2022, 43(3): 21-30.
GAO Y L, YANG Q W, WANG X F, et al. Overview of new swarm intelligent optimization algorithms[J]. Journal of Zhengzhou University (Engineering Science), 2022, 43(3): 21-30.
[6] 樊娇, 雷涛, 韩伟, 等. 无人机航迹规划技术研究综述[J]. 郑州大学学报(工学版), 2021, 42(3): 39-46.
FAN J, LEI T, HAN W, et al. A survey of UAV path planning[J]. Journal of Zhengzhou University (Enginee-ring Science), 2021, 42(3): 39-46.
[7] 史殿习, 洪臣, 康颖, 等. 面向多无人机协同飞行控制的云系统架构[J]. 计算机学报, 2020, 43(12): 2352-2371.
SHI D X, HONG C, KANG Y, et al. Cloud-based control system architecture for multi-UAVs cooperative flight[J]. Chinese Journal of Computers, 2020, 43(12): 2352-2371.
[8] LI Y M, FU C H, DING F Q, et al. Augmented memory for correlation filters in real-time UAV tracking[C]∥2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Piscataway: IEEE, 2020: 1559-1566.
[9] DANELLJAN M, BHAT G, KHAN F S, et al. ATOM: accurate tracking by overlap maximization[C]∥2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). Piscataway: IEEE, 2019: 4655-4664.
[10] MA C, HUANG J B, YANG X K, et al. Hierarchical convolutional features for visual tracking[C]∥2015 IEEE International Conference on Computer Vision. Piscataway: IEEE, 2015: 3074-3082.
[11] SKOROBOGATOV G, BARRADO C, SALAM
E. Multiple UAV systems: a survey[J]. Unmanned Systems, 2020, 8(2): 149-169.
[12] 赵坤, 刘睿, 张龙龙, 等. 无人侦察机多传感器任务规划技术研究[J]. 电子技术与软件工程, 2018(7): 125-126.
ZHAO K, LIU R, ZHANG L L, et al. Research on multisensor mission planning technology for unmanned reconnaissance aircraft[J]. Electronic Technology &Software Engineering, 2018(7): 125-126.
[13] 张龙龙, 刘睿, 赵坤, 等. 基于遗传算法的多传感器规划技术[J]. 电子技术与软件工程, 2019(6): 70-72.
ZHANG L L, LIU R, ZHAO K, et al. Multi-sensor planning technology based on genetic algorithm[J]. Electronic Technology &Software Engineering, 2019(6): 70-72.
[14] 刘睿, 赵坤. 基于优化算法的多传感器自动规划技术[J]. 电子技术与软件工程, 2021(18): 90-93.
LIU R, ZHAO K. Multi-sensor automatic planning technology based on optimization algorithm[J]. Electronic Technology &Software Engineering, 2021(18): 90-93.
[15] EMAMI Y, WEI B, LI K, et al. Joint communication scheduling and velocity control in multi-UAV-assisted sensor networks: a deep reinforcement learning approach[J]. IEEE Transactions on Vehicular Technology, 2021, 70(10): 10986-10998.
[16] KHODAPARAST S S, LU X, WANG P, et al. Deep reinforcement learning based energy efficient multi-UAV data collection for IoT networks[J]. IEEE Open Journal of Vehicular Technology, 2021, 2: 249-260.
[17] ZHENG H X, YUAN J P. An integrated mission planning framework for sensor allocation and path planning of heterogeneous multi-UAV systems[J]. Sensors (Basel, Switzerland), 2021, 21(10): 3557.
[18] FEI S, HASSAN M A, XIAO Y, et al. UAV-based multi-sensor data fusion and machine learning algorithm for yield prediction in wheat[J]. Precision Agriculture, 2022,8:1-26.
[19] 汪慎文, 张佳星, 褚晓凯, 等. 两阶段搜索的多模态多目标差分进化算法[J]. 郑州大学学报(工学版), 2021, 42(1): 9-14, 110.
WANG S W, ZHANG J X, CHU X K, et al. Multimodal multi-objective differential evolution algorithm based on two-stage search[J]. Journal of Zhengzhou University (Engineering Science), 2021, 42(1): 9-14, 110.