2. 西北工业大学 自动化学院, 陕西 西安 710072;
3. 长安大学 地质工程与测绘学院, 陕西 西安 710054
在现代、信息化作战系统中，传感器(雷达)和武器(导弹、火炮)的合理高效利用对作战任务效果具有重要影响。如何快速、有效地分配RUAVs和UCAVs实现对大规模目标进行监测以及攻击是目前作战规划中一项极具挑战性的热点问题[1-4]。通常可将此类分配问题分为侦查无人机-目标(RUAVs-Target, RUAVs-T)分配问题以及攻击无人机-目标(UCAVs-Target, UCAVs-T)分配问题。RUAVs-T与UCAVs-T分配问题同属任务分配，多目标协同侦查、监测和追踪任务为典型的RUAVs-T分配问题[5-6]；火力打击任务分配即为UCAVs-T分配问题[2-3]。本文针对RUAVs和UCAVs对敌作战的任务分配问题进行研究，将侦查无人机、目标、攻击无人机结合起来统一考虑，采用协同分配模型，实现RUAVs、UCAVs以及目标的协同高效、快速分配。
目前，求解任务分配的算法大致可分为数学规划方法[7-8]、基于合同网的任务分配方法[4, 9]以及启发式智能优化算法[3, 10]三大类。
数学规划方法作为一种确定性算法，可以给出任务分配问题的最优解。然而，求解大规模分配问题时，由于求解难度剧增会导致耗时增加，在有限时间内该方法无法保证给出满意的规划结果[1]。
基于合同网的方法将任务分配视为一个协商过程，买卖双方以出价的形式竞争获得任务的执行权。但基于合同网的任务分配方法需任务执行主体间多次协商，在问题规模较大时势必造成通信量增大以及耗时增加的问题。
以遗传算法、蚁群算法等为代表的智能优化算法，由于其不要求目标函数的连续性以及可导性，在任务分配方面引起了许多学者的研究兴趣[10-11]。智能优化算法在优化过程中，整个种群中的所有个体同时向全局最优逐渐收敛。但由于智能优化算法存有大量随机性搜索尝试，致使在求解任务分配问题时会出现效率和精度不高的现象[1]。
任务分配过程中不确定性事件是不可避免的，追求全局最优的方法势必很难满足任务分配实时性的要求[12]。因此，次优、快速的任务分配方法在解决大规模任务规划问题时的实时性优势会更加明显。文献[12]提出了一种高效的基于边缘收益构造的启发式方法(an efficient marginal-return-based constructive heuristic, MRBCH)用于解决传感器-武器任务分配问题，该算法可快速解决任务分配问题。然而任务分配问题，除实时性要求外，分配结果的合理性也至关重要。本文侧重提高任务分配结果。在以作战收益最大化的目标函数中，加入调节因子与期望摧毁概率的约束条件[13]，使任务分配结果既满足作战效能又注重经济效能。
综上所述，本文提出了一种考虑目标期望摧毁概率的RUAVs/UCAVs快速、次优任务分配方法。该方法通过改进设计分配模型的目标函数以及约束条件，保证资源的均衡分配以及避免过度分配，提高分配结果质量。改进设计了基于边缘受益最大化的贪婪算法(greedy algorithm based on maximum marginal-return, GA-MMR)对提出的分配模型进行求解。仿真结果表明，所提算法可快速高效地进行任务分配，并且明显改善了资源分配不均与资源过度分配的情形。
1 RUAV、UCAV任务分配模型 1.1 问题描述本文考虑如下作战场景。在T时刻监测到有Nt个具有不同威胁程度的目标来袭，防御者拥有RUAVs和UCAVs拦截目标。Ns个RUAVs用来捕获跟踪目标，从而引导Nw个UCAVs对其进行摧毁。不同RUAV、UCAV对不同目标的捕获跟踪、摧毁能力不同。如何将这些RUAVs和UCAVs协同高效进行分配，达到有效抵御的目的是本文研究的关键问题。
假设每个RUAV与UCAV同时只能侦查和攻击一个目标, 且UAVs具有单一的侦查或者攻击功能。用Y=[yik]Ns×Nt和Z=[zjk]Nw×Nt分别表示RUAV和UCAV与目标之间的分配集合(RUAV-T, UCAV-T), 当yik/zjk为1时表示第i(i=1, 2, 3, …, Ns)个RUAV或第j(j=1, 2, 3, …, Nw)个UCAV分配给第k(k=1, 2, 3, …, Nt)个目标, 为0则相反。
Ps(k)表示目标k被RUAV捕获及追踪的概率, Pdes(k)表示目标k被摧毁的概率, Pw(k)表示目标k在RUAV引导下被UCAV摧毁的条件概率。则三者满足以下公式
|
(1) |
假设不同RUAV和UCAV对目标的成功捕获和摧毁事件是相互独立的事件。则目标k被成功捕获追踪的概率可通过(2)式计算
|
(2) |
式中，pik为目标k被第i个RUAV成功捕获追踪的概率。同样目标k被成功摧毁的概率计算公式为
|
(3) |
式中，qjk为目标k被第j个UCAV摧毁的概率[13]。于是可得目标k被RUAV成功捕获追踪, 且在指导下被UCAV成功摧毁的概率为
|
(4) |
本文设计了一种高效的RUAVs/UCAVs、目标任务分配模型, 目标函数为最大化摧毁敌方目标的价值(或最大化减少敌对目标威胁值)。
|
(5) |
式中：R为分配方案对应收益值; vk表示目标k的威胁值(目标价值); α(k)为目标k的资源分配调节因子, 其用于指导分配过程, 确保资源分配的均衡性。
1.3 约束条件该分配模型中单一RUAV只能用于捕获追踪一个敌方目标; 同样单一UCAV只能用于攻击一个敌方目标。
|
(6) |
|
(7) |
为提高分配结果的经济效能, 引入目标期望摧毁概率约束。若某一目标已分配资源(RUAVs、UCAVs)满足摧毁该目标的概率不低于其摧毁期望值(expected probability of destruction, Pd), 则停止对该目标分配资源, 避免造成资源的浪费; 否则根据分配规则继续参与分配过程, 直到分配结束。
|
(8) |
式中：a(i, j, k)为任务所包含分配方案集合, 表示将第i个RUAV和第j个UCAV分配给目标k; Pd(k)为第k个目标期望摧毁概率; remove(a(*, *, k))表示将分配方案a(*, *, k)从集合A中删除。
2 RUAV、UCAV任务分配方法 2.1 辅助决策矩阵本文研究RUAVs/UCAVs的目标分配问题, 对作战任务而言, RUAVs与UCAVs分配相互依赖。RUAVs提供目标的位置信息, UCAVs对目标进行攻击, 消除威胁。本文采用三维矩阵X=[xijk]Ns×Nw×Nt表示任务分配方案集合[12], xijk为1时表示RUAV(i)与UCAV(j)分配给目标k, xijk为0则相反。在三维矩阵的辅助下, 可以更清楚描述RUAVs和UCAVs与目标三者之间的关系。
2.2 约束处理方法为保证分配方案满足约束条件(6)、(7)式, 分别用变量NUs、NUw表示每个RUAV以及UCAV的使用次数。在任务分配过程中, 若出现RUAV(i)/UCAV(j)的使用次数NUs(i)/NUw(j)大于1时, 则停止对RUAV(i)/UCAV(j)进行分配, 将涉及RUAV(i)/UCAV(j)的分配集合从集合A中删除。既满足约束条件又可加快分配进程, 减少时间消耗。
同样在分配过程中, 当目标k的摧毁概率满足期望摧毁概率Pd(k)时, 将涉及目标k的分配方案从分配集合中删除, 加快分配进程实现高效任务分配。
2.3 任务分配规则本文在建立目标函数基础上, 采用边缘收益最大的贪心原则进行任务分配。同时为保证资源分配的均衡性, 在目标函数中增加了调节因子α。
1) 边缘受益最大原则
在计算边缘收益之前, 需定义概率更新规则。对于目标k而言, 若无RUAVs分配则该目标未被成功捕获追踪的概率就为1;若分配的RUAVs越多, 则该目标未被捕获追踪的概率就应越小, 定义如下Pmis(k)更新规则[12]。
|
(9) |
同理, 定义如下Qmis(k)更新规则
|
(10) |
式中：Pmis(k)表示目标k未被其已分配RUAVs成功捕获的概率；Qmis(k)表示目标k未被其已分配UCAVs成功摧毁的概率。{Sk}, {Wk}分别为分配给目标k的RUAVs和UCAVs集合。
在任务分配开始阶段, 任务分配的受益为0。当新增加任务分配方案xijk时, 由于增加的xijk所带来的收益增加ΔRijk计算方法如下所示
|
(11) |
|
(12) |
|
(13) |
式中：R1为xijk增加之前分配方案的收益值；R2为增加xijk之后的收益值；ΔRijk为前后分配方案的收益差值。按照边缘受益最大原则, 优先选择给分配方案带来最大收益max{ΔRijk}的分配组合xijk, 直到任务分配结束。
2) 调节因子α
|
(14) |
式中：sum(NUs+NUw)为已参与分配任务的RUAVs、UCAVs数量总和; min(Ns, Nw, Nt)为三者中的最小值; NUw(ε)和NUw(k)为目标ε和k已分配的武器个数, ε=1, 2, …, k-1, k+1, …, Nt。当所有目标均未被分配武器或分配达到最小轮次时, 调节因子全为1;当某一目标k已被分配RUAV/UCAV, 且存有仍未被分配RUAV/UCAV的目标时, 将k所对应的调节因子α(k)赋值为0。通过调节因子修正, 可避免出现资源分配不均匀的情形, 达到资源均衡分配。
2.4 任务分配流程本文提出一种改进的基于边缘受益最大的贪婪算法(GA-MMR)用于解决RUAVs/UCAVs、目标分配问题, 具体步骤如下所示:
Input: 
Output: X, Y, Z, R;
1. Initialization: X←0, Y←0, Z←0, α←1, Pmis(k)←1, Qmis(k)←1;
2. Set up 
3. while(~ is empty(A))
3.1 for k=1 to Nt
Calculate R1(k)
end
3.2. if a(i, j, k) violates (6)(7)
Delete a(i, j, k);
end
3.3. if Pdes(k)>Pd
Delete a(*, *, k);
end
3.4. for k=1 to Nt
Calculate R2(k) and ΔRi, j, k;
end
3.5. 
3.6. 
End while
3 仿真算例与分析 3.1 仿真数据产生本文中所有算例数据均在允许范围内随机产生, 目标威胁程度(价值)产生方法如(15)式所示
|
(15) |
式中，vl与vu分别为目标价值的上下限值。RUAVs成功捕获追踪目标的概率和UCAVs成功摧毁目标的概率均采用上述方法产生, 其范围如表 1所示。
1) 对比算法
为验证所提模型以及算法的有效性, 本文选择、设计了以下对比算法。文献[12]中的MRBCH算法、加入目标期望摧毁概率的MRBCH-Pd算法以及加入调节因子(revision factor, RF)α的MRBCH-RF算法。
2) 仿真算例
根据RUAV/UCAV的数量和目标数量, 本文设计了3种情况的仿真算例。情形一: RUAV/UCAV组合数量小于目标数量; 情形二: RUAV/UCAV组合数量与目标数量相同; 情形三: RUAV/UCAV组合数量大于目标数量。为了验证目标期望概率对分配结果的影响, 特在情形三中额外设置了一组对比实验。仿真算例采用的数据如表 2所示。
| 情形 | 编号 | Ns | Nw | Nt | Pd |
| 一 | 1 | 6 | 5 | 8 | 0.85 |
| 2 | 30 | 40 | 45 | 0.85 | |
| 二 | 3 | 10 | 10 | 10 | 0.85 |
| 4 | 60 | 60 | 60 | 0.85 | |
| 三 | 5 | 80 | 90 | 70 | 0.85 |
| 6 | 200 | 160 | 80 | 0.85 | |
| 7 | 200 | 160 | 80 | 0.90 | |
| 8 | 200 | 160 | 80 | 0.95 |
为验证所提模型方法的有效性, 从算例运行时间、分配结果以及影响因素三方面对结果进行统计分析。
1) 算例仿真时间与结果
不同情形下仿真算例的运行时间如表 3所示, 目标期望摧毁概率设置为0.85。每种算法独立运行11次, 算法运行时间取11次平均值, 单位为s。从表 3可以看出, 文中4种算法所用时间在一定程度内均可满足任务实时性的要求。
| 算例 | MRBCH | MRBCH-Pd | MRBCH-RF | GA-MMR |
| 1 | 0.003 7 | 0.010 0 | 0.004 3 | 0.010 3 |
| 2 | 0.191 5 | 0.175 2 | 0.1942 | 0.166 0 |
| 3 | 0.004 8 | 0.009 9 | 0.005 3 | 0.009 9 |
| 4 | 1.386 0 | 1.112 6 | 1.408 4 | 1.060 3 |
| 5 | 4.598 0 | 3.507 3 | 4.669 6 | 3.333 5 |
| 6 | 46.93 8 | 26.46 9 | 47.74 2 | 24.96 2 |
| 7 | 46.93 8 | 36.79 2 | 47.74 2 | 34.33 2 |
| 8 | 46.93 8 | 46.20 1 | 47.74 2 | 44.20 3 |
在求解算例1, 3时，本文所提算法GA-MMR与MRBCH-Pd算法在运行时间上表现相近，且在求解算例2, 4, 5~8时GA-MMR算法比MRBCH、MRBCH-Pd及MRBCH-RF算法所需运行时间少; 在算例5、6中, 当RUAV/UCAV数量大于100时, 所提算法相比改进前算法, 运行时间分别减少27.5%和46.80%。
从表 4可以看出, MRBCH算法求出分配方案的收益值最高。MRBCH-Pd、MRBCH-RF与GA-MMR 3种算法在求解算例2, 4, 5~8时, 由于调节因子或目标期望概率约束条件的原因, 未能得到收益值最大的分配方案。
| 算例 | MRBCH | MRBCH-Pd | MRBCH-RF | GA-MMR |
| 1 | 2 801.7 | 2 801.7 | 2 801.7 | 2 801.7 |
| 2 | 21 162 | 21 070 | 21 162 | 21 070 |
| 3 | 5 972.2 | 5 972.2 | 5 972.2 | 5 972.2 |
| 4 | 37 230 | 37 230 | 37 193 | 37 193 |
| 5 | 46 455 | 45 723 | 46 455 | 45 723 |
| 6 | 59 979 | 54 104 | 59 979 | 54 104 |
| 7 | 59 979 | 57 292 | 59 979 | 57 292 |
| 8 | 59 979 | 59 949 | 59 979 | 59 947 |
图 1为算例2分配方案中中各目标摧毁概率的箱线图。算例2中MRBCH-Pd与GA-MMR算法得到的RUAVs/UCAVs分配方案与其它算法相比, 目标摧毁概率值更均匀。
|
| 图 1 算例2不同算法分配方案中各目标摧毁概率的箱线图 |
由于算例2中的目标期望摧毁概率设置为0.85, 当目标1, 5, 6, 39, 41, 45的摧毁概率大于0.85后, 其不再参与分配过程。因此, MRBCH-Pd与GA-MMR算法未能选择收益较大的方法, 将资源分给目标2, 3, 7, 13, 15以及目标23, 避免了资源的过度分配, 其各目标的摧毁概率如图 2所示。
|
| 图 2 算例2不同算法分配方案部分目标摧毁概率值 |
以MRBCH和MRBCH-Pd算法为参考基准, 图 3为算例4各算法获得分配方案的摧毁概率差异图。MRBCH和MRBCH-Pd算法求解的分配方案中目标10和30所分配资源为0, 加入分配调节因子的MRBCH-RF与GA-MMR算法放弃高收益的分配方案将6和11的资源分配给目标10和30, 加强了资源分配的均匀性。针对算例5~8, RUAV/UCAV数量远大于目标数。此时, MRBCH算法将所有资源全部分配给目标, 因此该算法所得分配方案具有高收益值; 而GA-MMR算法引入了目标期望摧毁概率的约束, 当目标摧毁概率满足设置期望摧毁概率时就会停止任务分配, 避免了资源的过度分配。
|
| 图 3 算例4不同算法分配方案中各目标摧毁概率的差异图 |
2) 目标期望摧毁概率对任务分配结果的影响
任务分配方案经济性指标与方案总收益、资源消耗成本以及作战效能均有关。为了定量对分配方案进行衡量, 本文设计、提出了一种资源分配方案经济性指标用来衡量分配结果的质量。计算方式如公式(16)~(19)所示
|
(16) |
|
(17) |
|
(18) |
|
(19) |
式中: R为整个任务分配方案收益值; max(R)为参与对比算例中收益最大值; 
| 算法 | min(Pdes) | R | E | 运行时间 | |||||||||||
| 算例6 | 算例7 | 算例8 | 算例6 | 算例7 | 算例8 | 算例6 | 算例7 | 算例8 | 算例6 | 算例7 | 算例8 | ||||
| GA-MMR | 0.864 8 | 0.902 5 | 0.980 1 | 54 104 | 57 292 | 59 949 | 1.671 5 | 1.248 2 | 1.025 8 | 24.962 | 34.332 | 44.203 | |||
| MRBCH | 0.980 1 | 59 979 | 0.992 6 | 46.938 | |||||||||||
其中min(Pdes)为分配结果中各目标摧毁概率的最小值。据表 5可知, 随着目标期望摧毁概率的增大, 参与任务的RUAV/UCAV数量以及仿真运行时间也不断增加。另外, 分配结果中所有目标摧毁概率最小值均满足设置的目标期望摧毁概率, 验证了分配模型的有效性。当目标期望摧毁概率设置为0.85, 0.9以及0.95时, GA-MMR算法所得分配方案的经济指标分别比MRBCH高68.4%, 25.75%以及3.34%。由于任务分配初期等量RUAV/UCAV给总方案带来的收益比后期等量资源带来的收益高, 因此当期望摧毁概率为0.85时, 经济效能最高。通过本文所提模型与算法, 任务规划者通过设置不同的目标期望摧毁概率, 可以为任务决策者提供更多可供选择的任务分配方案, 在满足作战效能的基础上提高了经济效能。
4 结论1) 本文提出了一种考虑目标期望摧毁概率的多无人机任务分配方法, 可为解决实时任务分配问题提供参考。
2) 通过在模型目标函数中加入分配调节因子, 弥补了原有方法出现资源分配不均的不足; 引入目标期望摧毁概率作为约束条件, 避免了出现资源过度分配的情形。
3) 当任务可用RUAVs/UCAVs数量远大于任务需求时, 本文所提模型算法, 能够给出满足决策者不同目标期望摧毁概率的分配方案, 在满足作战效能的基础上又提高了经济效能, 改善了任务分配质量。
下一步, 将更加注重任务分配的质量和效率, 加入多功能UAV执行任务的情形, 进一步增加所提方法的适用性。
| [1] |
苏菲, 陈岩, 沈林成. 基于蚁群算法的无人机协同多任务分配[J]. 航空学报, 2008, 29(B05): 184-191.
SU Fei, CHEN Yan, SHEN Lingchen. UAV cooperative multi-task assignment based on ant colony algorithm[J]. Acta Aeronautica et Astronautica Sinica, 2008, 29(B05): 184-191. (in Chinese) |
| [2] |
赵明, 苏小红, 马培军, 等. 复杂多约束UAVs协同目标分配的一种统一建模方法[J]. 自动化学报, 2012, 38(12): 2038-2048.
ZHAO Ming, SU Xiaohong, MA Peijun, et al. A unified modeling method of UAVs cooperative target assignment by complex multi-constraint conditions[J]. Acta Automatica Sinica, 2012, 38(12): 2038-2048. (in Chinese) |
| [3] |
严飞, 祝小平, 周洲, 等. 考虑同时攻击约束的多异构无人机实时任务分配[J]. 中国科学(信息科学), 2019, 49: 555-569.
YAN Fei, ZHU Xiaoping, ZHOU Zhou, et al. Real-time task allocation for a heterogeneous multi-UAV simultaneous attack[J]. Science in China(Information Sciences), 2019, 49: 555-569. (in Chinese) |
| [4] |
王然然, 魏文领, 杨铭超, 等. 考虑协同航路规划的多无人机任务分配[J]. 航空学报, 2020, 41(增刊2): 724234.
WANG Ranran, WEI Wenling, YANG Mingchao, et al. Task allocation of multiple UAVs considering cooperative route planning[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(suppl 2): 724234. (in Chinese) |
| [5] | FARMANI N, SUN L, PACK D J. A scalable multi-target tracking system for cooperative unmanned aerial vehicles[J]. IEEE Trans on Aerospace and Electronic Systems, 2017, 53(4): 1947-1961. DOI:10.1109/TAES.2017.2677746 |
| [6] | MORAES R S D, FREITAS E P D. Multi-UAV based crowd monitoring system[J]. IEEE Trans on Aerospace and Electronic Systems, 2020, 56(2): 1332-1345. DOI:10.1109/TAES.2019.2952420 |
| [7] | ALIDAEE B, WANG H, LANDRAM F. A note on integer programming formulations of the real-time optimal scheduling and flight path selection of UAVs[J]. IEEE Trans on Control Systems Technology, 2009, 17(4): 839-843. DOI:10.1109/TCST.2008.2002265 |
| [8] | BELLINGHAM J, TILLERSON M, RICHARDS A, et al. Multi-task allocation and path planning for cooperating UAVs[C]//Cooperative Control: Models, Applications and Algorithms, 2003: 23-39 |
| [9] | BOGDANOWICZ Z R. A new efficient algorithm for optimal assignment of smart weapons to targets[J]. Computers & Mathematics with Applications, 2009, 58(10): 1965-1969. |
| [10] | ROBERGE V, TARBOUCHI M, LABONTE G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time uav path planning[J]. IEEE Trans on Industrial Informatics, 2013, 9(1): 132-141. DOI:10.1109/TII.2012.2198665 |
| [11] | JIAO Z Q, YAO P Y, ZHANG J Y, et al. MAV/UAV task coalition phased-formation method[J]. Journal of Systems Engineering and Electronics, 2019, 30(2): 402-414. DOI:10.21629/JSEE.2019.02.18 |
| [12] | XIN B, WANG Y, CHEN J. An Efficient marginal-return-based constructive heuristic to solve the sensor-weapon-target assignment problem[J]. IEEE Trans on Systems, Man, and Cybernetics: Systems, 2019, 49(12): 2536-2547. DOI:10.1109/TSMC.2017.2784187 |
| [13] | BOGDANOWICZ Z R, TOLANO A, PATEL K, et al. Optimization of weapon-target pairings based on kill probabilities[J]. IEEE Trans on Cybernetics, 2013, 43(6): 1835-1844. DOI:10.1109/TSMCB.2012.2231673 |
2. School of Automation, Northwestern Polytechnical University, Xi'an 710072, China;
3. School of Geological Engineering and Geomatics, Chang'an University, Xi'an 710054, China
