中国指挥与控制学会会刊 
近年来,随着人工智能、大数据、云计算和物联网等先进技术的发展, 无人机平台已广泛应用于工业、农业、军事等多个领域,尤其在智能自主方面展现出强劲的增长势头。在灾害救援和军事任务等高风险场景中,无人机系统具有零人员伤亡、机动灵活、隐蔽性强、响应迅速、性价比高等显著优势,预计在未来的灾害应急或复杂战场监测任务中将发挥不可替代的作用。
例如,在森林火灾监视与决策支持中,基于分布式架构的无人机集群能够提供实时数据,协助指挥控制,提升灭火效率[1]。2022年,俄乌冲突中,无人机被广泛应用于隐蔽渗透、战术侦察和火力打击,取得了显著战果,对局部冲突的战术平衡产生了深远影响[2]。全球军事大国对无人机集群自主任务规划能力的重视日益增加,给未来战争形态和制胜机理带来了革命性挑战。美国国防部在《无人系统综合路线图2017—2042》中提出了4大主题:“互操作性、自主性、网络安全和人机协作”[3], 而中国电子技术标准化研究院发布的《智能无人集群系统发展白皮书》则对无人机集群在智能化、鲁棒性等方面提出了更高要求[4]。
然而,当前无人机集群系统的自主性应用仍处于初级阶段,尤其在协同感知、决策和控制方面存在诸多不足,表现为适应性差、计算效率低、环境识别能力不足以及任务执行效率不高[5]。在传统的探测任务框架下,受限于无人机的态势感知、载荷能力和通信限制,其集群协同探测的高效性、抗损毁性和快速响应能力尚未得到充分展现。
多无人机的探测任务分配问题多属于多约束下的NP-hard类型[6],目前建模方式主要有旅行商模型、扩展定向模型及其他拓展模型[7]。现有的多传感器无人机集群任务分配优化算法,按拓扑结构划分主要有集中式、分散式和混合式[7],其中常见的多目标启发式优化算法包括基于分解的多目标进化算法[8](multi-objective evolutionary algorithm based on decomposition, MOEA/D)、快速非支配排序遗传算法II(nondominated sorting genetic algorithm II,NSGA-II[9])、多目标粒子群算法(multi-objective particle swarm optimization, MOPSO)等。上述启发式算法在小规模任务分配中表现良好,但在大规模集群探测任务场景中,算法的求解时间显著增加,甚至可能无法达到预期效果。此外,在集群出现规模化损毁时任务重分配的能力不足,采用拍卖[10]方法进行再优化时,随着节点规模的增多,通信负载急剧上升,难以满足任务调优的快速性需求。为适应快速变化的任务环境,研究人员亟须提升任务分配算法的求解效率及损毁情况下的任务重分配能力。
针对上述问题,本文提出了一种基于改进NSGA-II算法的多传感器无人机集群任务分配优化算法,旨在降低总任务执行时长、减少无人机占用成本并最大化探测信息收益。该算法不仅能有效优化不同传感器无人机的任务分配,还能在集群出现规模化损毁的情况下基于原分配方案快速进行任务重构优化。
1 问题描述与建模
假设集群由N架无人机组成,每架无人机可以搭载一个有效载荷,常见载荷包括红外光电传感器、激光雷达传感器。任务区域内的目标点集合记为T= ,其中,每个目标点Tj的属性包含坐标位置 和侦察收益信息,且每个目标点需要至少被一架无人机覆盖。无人机集合记为U={U1,U2,…,UN},每架无人机Ui的属性包括坐标位置 、最大飞行时长Lmax、传感器类型Si,即Ui={[ , ],Lmax,Si},其中,Si∈{1,2},编码1表示红外光电传感器,编码2表示激光雷达传感器。
任务分配问题抽象为求T到U之间的映射关系,目标是确保每个任务均被探测到,且满足无人机集群系统的自身性能约束。
1.1 探测代价
集群总体飞行时长是反应分配方案性能的关键指标之一,假设无人机从起飞点到任务点均采用直飞模式,则第i架无人机的飞行时长 表示如下:
$f_{t}^{i}=\frac{\sqrt{\left(U_{i}^{x}-T_{A_{i}}^{w}\right)^{2}+\left(U_{i}^{y}-T_{A_{i}}^{y}\right)^{2}}}{v}$
其中, 表示第i架无人机的起飞点坐标,Ai表示分配给无人机i的任务编号, 表示分配给无人机i的任务点坐标。
为方便统一计算,本文去掉时间量纲,进行归一化处理,构造代价函数如下:
$f_{1}=\frac{\sum_{i=1}^{N} f_{t}^{i}}{N L_{\max }}$
其中,N为无人机的数量,v是无人机的平均航速,Lmax是无人机的最大滞空时长。
此时,f1表征的是无人机集群平均飞行时长占最大飞行时长的比例,比例越低,则留给无人机执行探测任务的时间越多。
1.2 探测收益
$f_{j}^{k}=\min \left(1, \frac{\sum_{i=1}^{N} x_{i j}}{I_{\max }^{k}}\right)$
其中,xij表示将第i个无人机分配至j号任务。
目标点j的探测总收益则表示为
$f_{r}^{j}=\sum_{k=1}^{2} \omega f_{j}^{k}$
其中,ω表示两类信息的重要性权重,本文中将其设定为[0.6,0.4]。
为将收益函数改成最小化函数,本文采用最大收益1减去实际收益的方式进行处理,构造探测收益函数如下:
$f_{2}=1-\frac{1}{M} \sum_{j=1}^{M} f_{r}^{j}$
1.3 优化模型
在点目标任务探测场景下的无人机集群任务分配中,探测代价和收益存在一定的冲突。假设无人机集群的任务分配方案为X,则X与每架无人机的任务变量xij的关系矩阵如下:
$\boldsymbol{X}=\left[\begin{array}{cccc}x_{11} & x_{12} & \cdots & x_{1 M} \\x_{21} & x_{22} & \cdots & x_{2 M} \\\vdots & \vdots & \ddots & \vdots \\x_{N 1} & x_{N 2} & \cdots & x_{N M}\end{array}\right]$
本文将探测代价和收益作为目标函数,构建多目标优化模型如下:
$\begin{array}{ll}\min & F(X)=\left(f_{1}(\boldsymbol{X}), f_{2}(\boldsymbol{X})\right)^{\mathrm{T}} \\\text { s. t. } & \sum_{i=1}^{N} x_{i j} \geqslant 1, j \in\{1,2, \cdots, M\} \\& x_{i j} \in\{0,1\} \\& f_{t}^{i}+m_{t} \leqslant L_{\max }\end{array}$
其中,约束1表示每个目标点至少分配一架无人机,约束2表示无人机只能同一时间探测一个目标,约束3表示无人机航行和任务探测时间要小于可用滞空时长Lmax。
该问题是一个非凸的非线性优化问题,使用传统方法难以快速进行优化。
2 优化算法求解
本文采用基于NSGA-II的算法进行求解,该算法是一种多目标遗传算法,可用于解决具有多个冲突目标的优化问题。通过改进,其可适用于本文的整数优化问题,即将无人机集群的任务分配方案X看成由基因片段xij组成的遗传基因编码,通过交叉和变异产生新的种群,并从中筛选保留优秀的基因,完成任务分配方案的进化寻优。为更快地进行寻优,可设置基于维诺划分的种群初始化策略和带限制的遗传算子缩小寻优范围。
由于单一无人机只能覆盖一个目标点的探测任务,所以种群个体的编码方式采用整数编码提高算法搜索效率,具体编码如图1所示。
该编码方式将原分配方案X的N×M矩阵简化为向量X=(x1,x2,…,xN),xi∈{0,1,2,…,M}表示无人机i分配的任务编号。例如x5=8,则表示由5号无人机执行8号任务。
通过上述编码方式可知,本文需要优化的决策变量个数就是无人机的数量N,决策变量随着集群规模的扩大而增加,NSGA-II算法的计算复杂度为O(MN2),大规模集群场景下,算法需要压缩寻优空间来降低计算复杂度。
2.1 基于维诺划分的种群初始化
一般情况下,不同起飞点的无人机携带的两类传感器比例大致相当,采用基于维诺划分的方式将起飞点内无人机按比例分配至最近的任务点。在相邻单元之间进行任务-无人机分配数量的均衡,将均衡后的单元放入禁忌表,直至所有单元的任务分配达到均衡,生成具有较大收益且总航时较小的初始种群。
以无人机集群的起飞点为维诺划分生成点A={A1,A2,…,Ak|i=1,2,…,k},其中,每个点Ai∈R2是对应起飞点的二维坐标。采用平分线的方法将任务区划分成k个维诺单元,对于每个维诺单元{Vi,i=1,2,…,k},维诺单元内起飞点和任务点满足式(8),维诺单元内部的任务点T与起飞点的距离总是最近的[13]。
$V_{i}=\left\{A_{i} \in R^{2} \mid \forall j \neq i,\left\|T, A_{i}\right\|_{2} \leqslant\left\|T, A_{j}\right\|_{2}\right\}$
假设任务区为60 km×60 km的区域,分布了10个起飞点,任务区内有随机分布的80个目标,则维诺划分如图2所示。
本文假设红外光电传感器的配置比例为ps,激光雷达传感器比例为1-ps,采用式(9)计算每个任务点分配的每一类无人机的数量 、 ,直至单元内任务或无人机分配完。
$\left\{\begin{array}{l}n_{S_{1}}=\left\lfloor\operatorname{rand}+\frac{N_{S_{1}}}{M} p_{s}\right\rfloor \\n_{S_{2}}=\left\lfloor\operatorname{rand}+\frac{N_{S_{2}}}{M}\left(1-p_{s}\right)\right\rfloor\end{array}\right.$
其中,rand为在区间(0,1)上的随机数,表示向下取整, 为携带红外光电无人机数量, 为携带激光雷达无人机数量。
各维诺单元起飞点配置的无人机数量与任务需求存在差异,故各单元之间存在任务负载的不均衡,导致探测收益下降。各单元无人机盈余数量按下式计算。
$n_{V_{r}}^{\prime}=\left\{\begin{array}{l}0, n_{V_{r}} \leqslant T_{V_{r}} \frac{N}{M} \\n_{V_{r}}-T_{V_{r}} \frac{N}{M}, \text { else }\end{array}\right.$
其中,n' 是单元Vr无人机的盈余数量, 是单元Vr无人机的配置数量, 是Vr单元的任务数量。
为提高初始解的收益且不显著增加航时成本,系统将无人机盈余单元Vr的n' 架无人机按临近单元内目标数的比例流转出去,流转方式见式(11),根据式(9)将流转至临近单元Vl的 架无人机再次分配,此时,Vr内的无人机资源与任务数匹配最佳,将均衡后的Vr放入禁忌表Ct。通过逐次流转,使各单元的负载趋于平衡,如图3所示。
$\left\{\begin{array}{l}n_{V_{l}}=\left\lfloor\left(1-\frac{T_{V_{l}}}{\sum T_{V_{l}}}\right) n_{V_{r}}^{\prime}\right\rfloor, l \in\left(\cup V_{l}-C_{t}\right) \\C_{t}=C_{t} \cup V_{r}\end{array}\right.$
其中,Vl是Vr的各临近单元, 是流转至Vl的无人机数量, 是Vr各临近单元的任务数量,n' 是当前单元盈余无人机数,l是Vr相邻单元的序号。
上述过程按照维诺划分、最佳配比随机分配、流转均衡、再分配的方式进行,每次分配均存在随机性,多次执行后生成初始种群。这种方式保证了初始种群的高收益,且成本不会显著增加。
2.2 带限制的遗传算子
在无人机集群任务放飞时对各无人机进行编号,每个集群任务分配方案X视作染色体,各基因点位对应的传感器和可用滞空时长是确定的。针对上述的基因编码方式,本文设计如下带限制的交叉和变异操作。
2.2.1 交叉操作
交叉操作是指在原分配方案的基础上,随机选择一部分无人机进行任务的交换。由于解X的编码特性,对于任一解,原算法的染色体间的单点交叉或者多点交叉方式会较大概率打破各任务点传感器分配比例,并不能将收益与成本很好地解耦。
本文设置自交叉算子和互交叉算子,自交叉操作限制任务交换在相同传感器无人机之间,此时收益f2不变,对成本优化。互交叉是不同传感器的无人机任务进行交换,用于微调各点传感器配比,同时增加种群的多样性。本文采用轮盘赌的方法,从两组父本X1、X2中以比例pc随机选择交叉基因点,按图4进行基因交换,生成新的子代。
2.2.2 变异操作
2.3 改进NSGA-II算法流程
3 仿真测试
本节共设置2组仿真试验,3.1节是小规模无人机集群场景中,最佳传感器配比下非支配解的详细分配方案,验证了任务分配算法的有效性和性能。3.2节设置大规模无人机集群场景下的算法测试与对比。实验测试基于MATLAB R2021a、Intel 12400 CPU进行。
3.1 小规模集群任务分配实验
为验证算法在资源短缺或损毁场景下的优化分配能力,本文进一步缩减无人机数量,模拟损毁或者资源短缺。从上述30架无人机场景中,本文随机去除3、9、15架无人机,生成新的任务场景,测试算法在资源短缺时的性能。实验结果如图8所示,无人机数量的减少使非支配解的数量明显减少,最大收益明显降低,成本上升。但改进的NSGA-II算法仍然能够对资源短缺场景下的任务分配进行优化。
3.2 大规模集群任务分配实验
表3 大规模集群探测场景参数Tab.3 Large scale cluster detection scenario |
| 区域 | 任务数 | 无人机数 | 传感器配比 | 起飞点 |
|---|---|---|---|---|
| 60×60 | 80个 | 200架 | 3∶2 | 10个 |
| 备注:各起飞点部署20架(12红外光电+8激光雷达) | ||||
表4 算法相关参数2Tab.4 Algorithm related parameters 2 |
| 参数 | 数值 |
|---|---|
| 种群数 | 30 |
| 最大迭代次数 | 500 |
| 交叉概率 | 0.2, 0.2 |
| 变异概率 | 0.03, 0.02 |
| 任务邻域dm | 15 |
| 滞空时长L | 40 |
对比原始NSGA-II算法,求解的PF如图9所示。探测成本f1随着收益f2的减少而增加,表明本文所提的两个优化目标是相互对立的,应当使用多目标优化的方式求解,决策者可以根据自身偏好选取收益最优、成本最低或平衡的任务分配方案。得益于种群初始策略和对搜索空间的压缩设计,本文通过对比不同迭代次数下的PF值,改进后的算法能够在相对较小的成本代价下达到理论最大收益,同时,改进后的算法相比原算法求解速度更快。
4 集群的损毁模拟
集群探测任务中,无人机的损毁主要来自3个方面:一是自身故障随机损毁,二是复杂地理环境坠毁,三是对抗性损毁[16]。前两种损毁可以近似为全局的小概率随机损毁,对抗性损毁则具有聚集性和高概率的特点。本节模拟任务执行过程中的损毁时,综合损毁率设定为20%~30%,对抗性损毁概率如下:
$ P_{d}=1-\mathrm{e}^{-\eta \frac{\varepsilon}{D^{2}}}$
其中,Pd是损毁概率,η是环境影响因子表征环境复杂度,ε是对抗手段影响因子表征干扰或对抗的强度,D是无人机到对抗中心的距离。
本文设定环境影响因子η为0.6,对抗影响因子ε为3,距离对抗中心5 km处影响衰减至7%,超出范围认为对抗手段失效。自然因素和对抗因素导致的损毁热力图如图10所示,小斑块为自然损毁,大斑块为对抗性损毁,综合损毁比例为27%。
5 任务的重分配
突发的规模化损毁会导致局部出现严重探测能力漏洞,失去对部分任务点的侦察探测,对集群完成区域的整体探测使命具有重大影响,必须进行任务的重分配。由于损毁点周围存在相对较多的无人机,在原优化分配方案基础上,算法采用局部任务流转的方式将释放的任务分配至邻近无人机,生成初始种群进行迭代优化。与前述无人机选择任务点的初始分配模式不同的是,重分配以任务点为中心选择无人机。
损毁无人机漏洞区的任务无法保证最小收益,释放的任务集合Tc满足下式:
无人机的流转不应造成新的探测漏洞,无人机释放的任务点集合To满足下式:
任务点之间的无人机流转应兼顾距离成本,设计任务流转规则如下:
其中,Xc为任务点流转分配方案,dc是可接受的任务流转距离,公式(14)、公式(15)表示任务流转满足公式(7)中所有任务都被分配的原则。
任务流转能够解决任务失败问题,但并不能确保全局负载的平衡,为进一步提高收益,降低成本,再次使用改进NSGA-II算法进行优化。设定损毁54架无人机的情况下,优化结果见图11。
可以看出,由于规模化的损毁,收益出现整体降低,任务之间部分无人机的流转导致航程成本f1>0,但小于初始分配成本。任务整体探测收益和成本均未出现大于1的情况,说明未出现任务失败或超航程的惩罚情况。
6 结束语
本文针对大规模无人机集群侦察探测场景下的任务分配问题,基于航路成本和探测收益建立多目标优化模型,解决了传统单目标优化不能兼顾航程和探测收益的问题。本文通过改进NSGA-II算法对模型进行求解,改进算法引入基于维诺划分的种群初始化和带限制的遗传策略,显著压缩了寻优空间,计算复杂度介于O(MN)~O(MN2)量级,相比原算法,在求解速度上存在明显优势。最后,通过构建规模化损毁模型模拟突发损毁场景,仿真实验验证了本文算法在处理资源短缺或无人机规模化损毁问题上的可行性与快速性。