SEAD场景异构无人机配置与任务规划联合优化方法

王建峰; 贾高伟; 辛宏博; 郭正; 侯中喜; WANG Jianfeng; JIA Gaowei; XIN Hongbo; GUO Zheng; HOU Zhongxi

doi: 10.11887/j.cn.202401004

王建峰，贾高伟，辛宏博，郭正，侯中喜

国防科技大学空天科学学院, 湖南长沙 410073

基金项目: 国家自然科学基金资助项目（61801495）

详细信息

作者简介

王建峰（1995—），男，河北衡水人，博士研究生，E-mail: jianfeng129@foxmail.com

通讯作者

贾高伟（1989—），男，河南周口人，副教授，博士，E-mail: ji_as@126.com

中图分类号: V279

文献标识码: A

文章编号: 1001-2486(2024)01-032-10

Joint optimization for heterogeneous multi-UAV configuration and mission planning within SEAD scenarios

WANG Jianfeng ， JIA Gaowei ， XIN Hongbo ， GUO Zheng ， HOU Zhongxi

College of Aerospace Science and Engineering, National University of Defense Technology, Changsha 410073 , China

摘要

对敌防空压制（suppression of enemy air defenses, SEAD）场景是多无人机协同的典型应用，针对该场景特点，在任务规划问题基础上将各类型无人机数量也作为决策变量，充分表征目标、任务和无人机的多种约束，建立异构无人机编队路径问题模型。设计了双层联合优化方法求解该模型：上层设计了任务衔接参数指标，精确评估各类型无人机需求，指导无人机配置调整；下层设计了改进遗传算法，高效处理多类型约束并能结合无人机数量变化对任务方案进行精细调整；双层相互协调获得满足需求的无人机配置和执行方案。仿真结果表明，该方法可以在避免遍历无人机配置组合的前提下获得合理的无人机配置方案和高效可行的执行方案。

关键词

SEAD场景 / 异构无人机 / 无人机配置 / 任务规划 / 任务衔接参数

Abstract

SEAD(suppression of enemy air defenses) is a typical application scenario of multi-UAV cooperation. Based on the characteristics of this scenario, the number of different types of UAV was also used as a decision variable in the task planning problem, fully characterizing the various constraints of the target, mission, and UAV, and establishing a heterogeneous UAV formation path problem model. A two-layer joint optimization method was designed to solve the model: the upper layer was designed with the task connection impact indicator to accurately assess the quantitative requirements of various types of UAVs and guide UAVs configuration adjustments; the lower layer improved the genetic algorithm, which can efficiently handle multiple coupling constraints and can accurately adjust the mission plan in conjunction with UAV quantity changes. The two layers coordinate with each other to obtain a UAV configuration and mission execution plan that meet the requirements. Simulation results show that the method can obtain a reasonable UAV configuration plan without traversing various UAV configurations, while obtaining an efficient and feasible mission execution plan.

Keywords

SEAD scenarios / heterogeneous UAV / UAV configuration / mission planning / mission connection parameters

1 联合优化问题建模 1.1 SEAD任务场景想定 1.2 基础模型构建 1.2.1 目标与任务模型 1.2.2 任务耦合关系 1.2.3 无人机模型 1.3 问题求解模型 2 双层联合优化方法 2.1 联合优化问题求解分析 2.2 上层：无人机配置计算 2.2.1 任务衔接参数 2.2.2 无人机配置调整流程 2.3 下层：任务规划计算 2.3.1 任务编码与调整 2.3.2 任务时间表计算 2.3.3 局部搜索算子 3 场景仿真验证 3.1 场景及参数配置 3.2 无人机配置方法仿真验证 3.2.1 无人机配置过程分析 3.2.2 多场景下无人机配置方法验证 3.3 多无人机SEAD任务规划仿真验证 3.3.1 任务规划方法可行性分析 3.3.2 任务规划方法求解效率分析 4 结论

无人机作为无人系统的“集大成者”，被广泛应用于不同任务场景。大型全能型无人机平台存在任务效费比低、系统容错性差和升级周期长等缺陷^[1-2]，异构无人机系统旨在将大型平台功能分散到空间分布的低成本单元，通过合理调度实现不同单元的动态组合和密切协作，在兼具经济性的基础上达到甚至超过大型平台能力水平。

对敌防空压制（suppression of enemy air defenses，SEAD）场景是当前异构无人机协同应用的典型场景，受到了广泛关注^[3]。当前该场景的研究多在给定无人机配置下进行，并集中于完善场景建模^[3-4]与提升求解效率^[5]。无人机配置是确定参与任务的无人机类型及数量^[6]，任务规划是协调各单元以获得执行方案，二者存在递阶关联性，合理的无人机配置可以提升机间协同效率，在满足任务需求的同时避免无人机资源浪费^[6]。

SEAD场景中无人机配置和任务规划联合优化问题属于异构车队车辆路径问题（heterogeneous fleet vehicle routing problem， HFVRP）范畴，即寻找最佳异构车队组成和任务路线^[7-8]。HFVRP是在车辆路径问题（vehicle routing problem，VRP）的基础上将车队组成也作为变量，较VRP这一NP-hard问题计算复杂度更高。HFVRP包含多种扩展^[9-10]——多次访问、站点依赖、时间窗口、资源限制、非对称路径等，本文问题包含类似限制^[3，11]：对同一目标顺序执行多种任务；存在时间窗口约束和资源需求；航程和资源载荷有限，且有返航需求；任务执行要求和动力学约束使得任务路径不对称。这些限制极大增加了问题求解难度。

考虑无人机配置对任务执行的影响：文献^[12]针对协同搜索与攻击场景，选择不同数量的无人机组合进行仿真，发现增加无人机可以降低任务时间但也增加任务协调成本，数量过多反而降低整体效能；文献^[13]针对协同对地打击场景，对比了不同机型组合及数量配置的体系贡献率，发现高速与高隐身无人机体系贡献率较高，无人机数量增加会提高贡献率，但存在饱和。考虑无人机配置与任务规划的递阶关联性，确定合理的无人机配置：文献^[14]利用分层策略处理无人机配置与任务分配问题，对比了基于进化算法的同时求解和分层求解的效果，证明了分层策略的有效性；文献^[15]针对广域侦察场景，利用聚类方法将目标划分成簇，根据簇群数量确定无人机数量并进行任务指派；文献^[16]针对无人机武器配置和打击路径优化问题，设计了基于局部搜索策略的启发式算法，在确定各个目标的毁伤需求的基础上优化无人机任务路径，验证了启发式算法的计算优势。

本文针对SEAD场景特点，建立了异构无人机编队路径问题（heterogeneous UAV fleet vehicle routing problem， HUFVRP）模型，在任务规划问题基础上将各类型无人机数量也作为决策变量，充分表征目标、任务和无人机的多种约束，优化无人机使用数量与任务执行时间指标。建立了双层联合优化方法求解模型：上层调整无人机配置，设计了任务衔接参数引导无人机数量调整；下层求解任务规划，改进遗传算法能够有效处理多种约束，并根据无人机数量变化针对性调整执行方案；双层相互协调以获得无人机配置和执行方案。

1 联合优化问题建模

本节首先介绍SEAD场景想定，然后建立目标、任务和无人机模型，最后给出HUFVRP模型相关数学描述。

1.1 SEAD任务场景想定

场景目标为位置已知的雷达站，毁伤要求和时间窗口已经明确，为简化计算做出如下想定：

1）任务场景为二维区域，不考虑地形障碍、禁飞区、突发威胁等干扰因素，目标和无人机均视为点目标。

2）目标包含多个任务，每个任务由一架无人机执行，不能忽略任务执行时间。

3）无人机存在资源和航程限制，不能无限执行任务，任务完成后需返回起飞点。

1.2 基础模型构建

1.2.1 目标与任务模型

T = \{T_{1} ， \dots ， T_{i} ， \dots ， T_{N^{Target}}\}

为目标集合，数量为N^Target。

M^{T_{i}}

表示目标T_i所属任务集合，包含侦察C、攻击A和评估V三类任务，c∈{1，2，3}为对应类型序号。

M^{T_{i}} \subseteq {C, A, V}

(1)

M^{T_{i}} = \{M_{i}^{1} ， \dots ， M_{i}^{m} ， \dots ， M_{i}^{N_{i}^{M}}\}

表示T_i任务数量为

N_{i}^{M}

，可在式（1）基础上调整任务数量应对不同需求。设

M_{i}^{m}

表示目标T_i的第m个任务，d^m_i为任务资源需求，[e^m_i，l^m_i]为任务时间窗口，s^m_i为执行时长。

全部任务按照目标序号排列形成任务总集合

M^{All} = \{M^{T_{1}} ， \dots ， M^{T_{i}} ， \dots ， M^{T_{N} T_{argel}}\}

，任务总数量为：

N_{A l l}^{M} = \overset{N^{Target}}{\underset{i = 1}{Σ}} N_{i}^{M}

(2)

为完善整体模型，定义T₀为起飞点，其评估任务为无人机返航，即

M^{T_{0}} = \{M_{0}^{1}\} = {V}

。

1.2.2 任务耦合关系

为描述任务间的时序关系，在任务总集合M^All基础上建立关联矩阵A^C和时间间隔矩阵A^T，矩阵大小均为

N_{A l l}^{M} \times N_{A l l}^{M}

。关联矩阵定性描述任务的耦合关系，时间矩阵定量描述任务的时间间隔。

a_{a ， b}^{C} \in {0，1}

表示关联矩阵A^C的a行b列元素，

a_{a ， b}^{C} = a_{\begin{matrix} m ， n \\ i ， j \end{matrix}}^{C} = 1

表示M^All中第a个任务M^m_i影响第b个任务Mⁿ_j执行，任务Mⁿ_j依赖于任务M^m_i；

a_{a ， b}^{C} = a_{b ， a}^{C} = a_{\begin{matrix} m ， n \\ i ， j \end{matrix}}^{C} = a_{\begin{matrix} n ， m \\ j ， i \end{matrix}}^{C} = 1

表示两个任务需同时执行。

a_{a ， b}^{T}

≥0为时间间隔矩阵A^T元素，

a_{\begin{matrix} m ， n \\ i ， j \end{matrix}}^{T} > 0

表示第b个任务Mⁿ_j需在第a个任务M^m_i完成后间隔

a_{a ， b}^{T}

时间才开始。

对于某一任务，关联矩阵中对应列的非零项为其依赖的任务，称为前序任务，前序任务全部完成后该任务方可执行；关联矩阵中对应行的非零项为受其影响的任务，称为后续任务，该任务完成后后续任务方可执行。式（3）为侦察、攻击和评估任务的关联矩阵，第3列表示评估任务的前序任务为侦察和攻击任务。

(3)

1.2.3 无人机模型

U^u（u∈{1，2，3}）表示各类型无人机集合：U¹为侦察型无人机，U²为攻击型无人机，U³为评估型无人机，N_U^AVMaxu为U^u型无人机最大数量。U^u型无人机参数如下：D^u为机载资源数量，V^u为巡航速度，B^u为最大留空时间，R^u_min为最小转弯半径。P^u={p^u₁，p^u₂，p^u₃}为无人机能力参数，其中p^u_c∈{0，1}，p^u_c=1表示无人机可以执行对应任务。

U={U₁，···，U_k，···，

U_{N^{UAV}}

}为参与任务的无人机集合，U_k表示其中第k架无人机。定义N_U^AVu为U^u型无人机使用数量，N^UAV为无人机使用总数量：

N^{U A V} = N_{1}^{U A V} + N_{2}^{U A V} + N_{3}^{U A V}

(4)

1.3 问题求解模型

在上述模型的基础上，借鉴异构车队车辆路径问题^[7，10]与无人机任务规划^[3-4]的部分研究建立HUFVRP模型。定义图模型G（V，A），其中

V = \{T_{0} ， T_{1} ， \dots ， T_{i} ， \dots ， T_{N^{Target}}\}

为起飞点和目标点的集合；A={（i，j）0≤i，j≤N^Target，i≠j}为无人机目标间转移顺序的集合，（i，j）表示无人机从目标T_i转移至目标T_j。模型相关变量如下：

1）[N^UAV₁，N^UAV₂，N^UAV₃]为无人机使用数量。

2）X^k^，^m_（_i_，_j_）∈{0，1}为任务分配关系，表示无人机U_k将按照（i，j）前往目标T_j执行任务M^m_j。

3）dis^k^，^m_（_i_，_j_）为无人机U_k按照（i，j）前往目标T_j执行任务M^m_j的路径长度，t^k^，^m_（_i_，_j_）为转移时间。

4）t^m_j为任务M^m_j的开始时间，t¹_0，_k表示无人机U_k返航到达起飞点的时间。

该问题需要寻找合理的无人机配置方案和对应执行方案，因此针对性设置无人机数量F₁和任务平均完成时间F₂两个优化目标，具体如下：

F_{1} = N^{U A V}

(5)

F_{2} = \frac{\overset{N^{Target}}{\underset{i = 0}{Σ}} \overset{N^{Target}}{\underset{j = 1}{Σ}} \overset{N_{j}^{M}}{\underset{m = 1}{Σ}} \overset{N^{U A V}}{\underset{k = 1}{Σ}} X_{(i, j)}^{k, m} (t_{j}^{m} + s_{j}^{m}) λ_{j}^{m}}{\overset{N^{Target}}{\underset{i = 0}{Σ}} \overset{N^{Target}}{\underset{j = 1}{Σ}} \overset{N_{j}^{M}}{\underset{m = 1}{Σ}} \overset{N^{U A V}}{\underset{k = 1}{Σ}} X_{(i, j)}^{k, m}}

(6)

其中，λ^m_j≥1为未完成任务惩罚系数。

模型约束包含任务执行要求、任务时序耦合约束和无人机能力限制三类，建模如下：

(7)

(8)

(9)

\begin{matrix} \overset{N_{}^{Target}}{\underset{i = 0}{Σ}} \overset{N_{t}^{M}}{\underset{m = 1}{Σ}} X_{(i, t)}^{k, m} - \overset{N^{Target}}{\underset{j = 1}{Σ}} \overset{N_{j}^{M}}{\underset{n = 1}{Σ}} X_{(t, j)}^{k, n} = 0 \\ \forall U_{k} \in U, T_{t} \in T \end{matrix}

(10)

\begin{matrix} t_{i}^{m} - t_{j}^{n} + X_{(i, j)}^{k, n} (s_{i}^{m} + t_{(i, j)}^{k, n} + l_{i}^{m} - e_{j}^{n}) ⩽ l_{i}^{m} - e_{j}^{n} \\ \forall T_{i}, T_{j} \in T; M_{i}^{m} \in M^{T_{i}}; M_{j}^{n} \in M^{T_{j}}; U_{k} \in U \end{matrix}

(11)

(12)

\begin{matrix} t_{i}^{m} + s_{i}^{m} + a_{\begin{matrix} m, n \\ i, j \end{matrix}}^{C} a_{\begin{matrix} m, n \\ i, j \end{matrix}}^{T} ⩽ t_{j}^{n} + (1 - a_{\begin{matrix} m, n \\ i, j \end{matrix}}^{C}) Y \\ \forall T_{i}, T_{j} \in T; M_{i}^{m} \in M^{T_{i}}; M_{j}^{n} \in M^{T_{j}} \end{matrix}

(13)

(14)

(15)

\begin{matrix} X_{(0, i)}^{k, m} [t_{0, k}^{1} - (t_{i}^{m} - t_{(0, i)}^{k, m})] ⩽ B^{u} \\ \forall T_{i} \in T, M_{i}^{m} \in M^{T_{i}}, U_{k} \in U^{u} \end{matrix}

(16)

(17)

其中：式（7）约束目标包含的任务均分配给无人机执行；式（8）~（9）约束无人机从起飞点出发，执行完任务后返回出发点；式（10）约束无人机按方案顺序执行任务；式（11）确保无人机在任务开始前到达目标位置；式（12）确保任务时间满足时间窗约束；式（13）确保任务时间满足时序耦合约束，其中Y为无穷大值；式（14）确保无人机有能力执行所分配的任务；式（15）确保无人机所执行任务的资源需求不超过其机载资源限制；式（16）确保无人机不超过航程限制；式（17）确保各类无人机使用数量不超过最大数量。

2 双层联合优化方法

2.1 联合优化问题求解分析

无人机配置与任务规划联合优化问题包含多种类型的变量，且变量之间存在递阶关联性，求解十分困难^[14]。因此，本文设计了双层联合优化方法，上层进行无人机配置计算，下层进行多无人机任务规划计算，具体见图1。

图1双层联合优化方法结构

Fig.1Structural diagram of the two-level joint optimization method

在上层中，根据任务时间表和无人机使用率设计了任务衔接参数，精确评估各类型无人机需求，指导无人机配置方案调整。在下层中，使用改进遗传算法在给定无人机配置下进行任务规划计算，能结合无人机数量变化精确调整执行方案，在有限时间内能够以更高概率获得高质量执行方案，提升对无人机配置方案的评估准确性。

双层联合优化方法可以通过有限次数的迭代获得满足要求的无人机配置及任务执行方案，避免了无人机配置与任务规划同时求解造成的问题空间非线性扩展，在有限的计算时间内可以获得更高质量结果。

2.2 上层：无人机配置计算

2.2.1 任务衔接参数

任务衔接参数旨在通过任务开始时间评估各类型无人机需求情况。任务开始时间受到无人机到达时间、前序任务完成时间和时间窗口的影响。其中无人机到达时间受到无人机数量和任务执行顺序影响。为评估无人机到达时间，设想一个理想情况，即无人机从起飞点直接前往目标，实际到达时间不会早于该时间。定义

t_{i ， m}^{ideal}

为任务M^m_i的最早允许开始时间，计算见下式：

t_{i, m}^{ideal} = m a x \{t_{i, m}^{C}, e_{i}^{m}, t_{(0, i)}^{k, m}\}

(18)

t_{i, m}^{C} = m a x \{a_{\begin{matrix} n, m \\ j, i \end{matrix}}^{C} (t_{j}^{n} + s_{j}^{n} + a_{\begin{matrix} n, m \\ j, i \end{matrix}}^{C} a_{\begin{matrix} n, m \\ j, i \end{matrix}}^{T})\} \forall T_{j} \in T, M_{j}^{n} \in M^{T_{j}}

(19)

其中，

t_{i ， m}^{C}

为M^m_i前序任务的完成时间与时间间隔之和的最大值。

在实际执行过程中，任务开始时间会与最早允许开始时间存在差值：若无人机数量不足，无人机需要承担多项任务，到达目标的时间较晚，此时差值较大；若无人机数量充足，无人机承担任务较少，到达目标的时间较早，此时差值较小。将该差值定义为任务等待时间

W_{i ， m}^{C I}

：

W_{i, m}^{C I} = t_{i}^{m} - t_{i, m}^{ideal}

(20)

未执行的任务将根据未执行原因设置不同的等待时间值。未执行原因包含航程不足、资源不足、前序任务未执行和违反时间窗约束四类。前两类可以通过增加无人机处理，因此设置较大的等待时间（本文设为等待时间最大值

W_{M a x}^{C I}

）。后两类存在前序任务影响，无法判断增加无人机是否有效，因此将等待时间设置为0，等待进一步观察；待前序任务完成后，若无人机数量仍不足，此时未执行原因会变为前两类。

W^{C I} = \{\begin{matrix} W_{M a x}^{C I} & \{\begin{matrix} 无 人 机 航 程 不 足 \\ 无 人 机 资 源 不 足 \end{matrix} \\ 0 & \{\begin{matrix} 前 序 任 务 未 执 行 \\ 违 反 时 间 窗 约 束 \end{matrix} \end{matrix}

(21)

本文在任务等待时间的基础上设计了任务衔接参数指标δ^CI，以评估各类型无人机需求情况。某类任务的衔接参数高，说明对应的无人机数量不足，计算如下：

δ^{C I} = \bar{χ} {({\bar{W}}^{C I} + 1)}^{λ^{C l}} + α^{C l} {\bar{N}}_{U A V}^{T a s k}

(22)

式中：

\bar{χ}

为无人机使用率，当无人机未全部使用时降低参数；

{\bar{W}}^{C I}

为该类任务的等待时间均值；λ^CI∈（0，1）为等待时间调节参数，避免各类型任务衔接参数差距过大；

{\bar{N}}_{U A V}^{T a s k}

为无人机平均任务数量，α^CI∈（0，0.1]为其系数，平均任务数量可以反映不同类型无人机的任务负载是否平衡，但无人机能力存在差异，因此将其作为辅助项，设置较小的控制系数。

可以根据任务衔接参数的变化判断无人机数量是否饱和：无人机增加会影响对应任务完成时间，进而影响其后续任务的最早允许开始时间。若后续任务对应无人机数量不足，参数将上升；若无人机数量充足，参数将不变，此时不需增加该类无人机。

2.2.2 无人机配置调整流程

无人机配置将在给定的初始配置方案基础上进行调整，每次增加1架无人机，如图2所示，具体流程如下：

步骤1：输入初始无人机配置方案。

步骤2：调用下层任务规划，计算当前无人机配置方案下的最优执行方案。

步骤3：根据式（18）~（22）计算任务衔接参数，根据参数对各类型无人机进行倒序排列，形成无人机增加列表。

步骤4：判断各类型无人机是否达到其最大数量限制，若达到则从列表中删除该类无人机。

步骤5：若上次无人机配置迭代时，任务的前序任务对应无人机增加后，该任务衔接参数没有变化，则将对应无人机从列表中删除。

步骤6：选择列表中排在首位的无人机，在当前无人机配置方案的基础上增加1架该类无人机，然后更新无人机配置方案。

步骤7：判断是否满足迭代终止条件，若满足则停止迭代，否则返回步骤2进行计算。

图2无人机配置调整流程

Fig.2Flow chart of UAV configuration adjustment

2.3 下层：任务规划计算

下层改进遗传算法主要包含任务编码与调整、任务时间表计算、局部搜索算子三部分，计算流程见图3。

图3任务规划计算流程

Fig.3Flow chart of mission planning calculation

2.3.1 任务编码与调整

任务编码包含目标序列、任务序列和无人机序列三部分，编码长度与任务总数量相同，按照编码顺序从左至右计算。多层编码情况如图4所示，第一列表示目标T₂的攻击任务A由无人机U₁执行。

图4多层编码示意图

Fig.4Multi-layer coding schematic

由于存在时序耦合约束，若某一任务先于其前序任务执行，可能出现“死锁”情况，导致无人机陷入无休止的等待^[11]。如图4所示，第1列和第4列分别为目标T₂的攻击和侦察任务，任务执行顺序与任务时序耦合约束矛盾，导致前四个任务陷入“死锁”。对此，本文设计了基于任务关联矩阵的“死锁”调整流程，具体如下：

步骤1：在原编码基础上生成空白的新编码。

步骤2：根据编码顺序对原始编码中的任务逐一进行判断——其关联矩阵对应列是否全部为0。

步骤3：若出现任务满足上述条件，则立即停止判断。将该任务从原始编码中删除并将其关联矩阵对应行设为0。

步骤4：将该任务插入新编码的当前第一空位，若编码为空则放置于首位，无人机映射关系不变。

步骤5：判断原始编码是否为空，若是则输出新编码，否则返回步骤2。

该方法只对存在时序耦合约束的任务进行调整，其他任务的对应顺序不变。

2.3.2 任务时间表计算

任务时间表将根据调整后的编码顺序进行计算，每个任务的计算过程包含无人机选择、任务执行路径和任务时间协调三部分。

1）无人机选择：为避免编码对应无人机无法执行任务，定义选择概率PS_k为无人机U_k执行任务M^m_i的概率。如式（23）所示，

{\hat{a}}_{k}^{i ， m}

为无人机从上一位置到达任务处的时间，D^u_k为无人机剩余资源数量。将选择概率大于0的无人机按照概率值倒序排列形成无人机列表，若编码中对应无人机的选择概率大于0，则将其排在该列表首位。

P S_{k} = e^{- {\hat{a}}_{k}^{i, m}} p_{c}^{u} (m i n \{\frac{D_{k}^{u}}{d_{i}^{m}}, 1\}) U_{k} \in U^{u}

(23)

2）任务执行路径：采用末端航向松弛的Dubins方法^[17]计算任务路径，在满足无人机动力学约束和任务执行需求的基础上，将任务规划寻优和任务路径计算部分解耦，降低整体计算复杂度。计算过程如图5所示，侦察无人机（A点）和攻击无人机（B点）对目标T₁和T₂执行侦察和攻击任务。蓝色实线为侦察路径：无人机需绕目标盘旋（红色区域）搜集信息，其转移路径为当前位置进入盘旋航线的最短路径，可以使用几何切线方法计算其转移路径，评估任务与侦察任务计算相同。攻击无人机路径为红色实线：无人机需要到达目标上方进行攻击，目标位置将作为无人机转移路径的终点进行计算。

图5无人机任务路径计算示意图

Fig.5UAV path calculation schematic

3）任务时间协调：根据上述路径可以获得无人机到达时间，然后根据式（18）与前序任务时间和时间窗口进行协调计算任务开始时间。计算完成后需要判断是否满足无人机航程约束，若不满足就选择无人机列表中下一架无人机进行计算，若满足则按照编码顺序计算下一项任务。

2.3.3 局部搜索算子

局部搜索算子将根据无人机配置变化对前序无人机配置下的完成时间较短的方案进行调整。主要将原方案中的部分未完成任务和等待时间较大任务添加至新增无人机执行列表，流程如下：

步骤1：选择一个完成时间较短的任务方案，将其作为基础方案进行调整。

步骤2：选择新增无人机可执行的全部任务，将其中未完成任务和等待时间大于0的任务加入待调整任务列表。

步骤3：为新增无人机增加一个任务——按照待调整任务列表顺序，分别将任务列表中的任务调整至基础方案中新增无人机的执行列表末尾，形成多种新执行方案。

步骤4：计算生成的全部执行方案，选择最优方案。

步骤5：判断最优方案是否优于基础方案，若占优则执行步骤6，否则执行步骤7。

步骤6：将此时最优方案作为基础方案，并从待调整任务列表删除最优方案中已调整的任务，返回步骤3。

步骤7：输出此时的基础方案。

3 场景仿真验证

本节对无人机配置和任务规划联合优化方法进行仿真。分析了无人机配置过程和不同场景下的普适性；验证了任务规划方案的可行性与规划方法的求解效率。

3.1 场景及参数配置

仿真场景区域范围为150 km×150 km，起飞点为[0，0]，目标随机分布在[10，140] km×[10，140] km的区域。考虑到任务背景，目标会远离起飞点，因此限制目标与起飞点的最小距离为60 km，目标间最小距离为20 km。目标所属任务集合包含侦察、攻击和评估三个任务。攻击任务存在时间窗口，资源消耗数量为1；评估任务与攻击任务需间隔一定时间以避免烟尘干扰。表1为无人机的性能数据^[4]。任务衔接参数中等待时间调节参数为1/3，平均任务数控制系数为0.01。

表1无人机性能数据

Tab.1 UAV performance data

3.2 无人机配置方法仿真验证

3.2.1 无人机配置过程分析

场景包含8个目标，初始无人机配置为5架无人机（1侦察、3攻击、1评估），上层无人机配置迭代次数为10。攻击任务时间窗前端分布在[10，30] min，后端分布在[150，180] min，评估任务与攻击任务间隔为1 min。

为验证本文无人机配置方法的有效性，设计了一种对比方法：在迭代时增加衔接参数最小任务所对应无人机，生成一组对比方案。结果如下：

1）无人机配置与任务衔接参数：图6为两种方法的无人机配置方案对比，两种方法的无人机总数量相同，不同类型的无人机数量存在差异。图7表示本文方法的任务衔接参数变化。如图6和图7所示，随着无人机数量增加，任务衔接参数呈下降趋势，第2次迭代时增加了侦察无人机，对应衔接参数下降，其后续的攻击和评估任务的参数上升且变化较大，说明两类无人机数量不足，同样情况也在第4、6、8和9次迭代时出现，但后续任务的衔接参数波动持续减小，说明无人机数量已经较为充足。这表明无人机配置过程中观察无人机增加对任务衔接参数的影响是有意义的。

图6无人机配置方案对比（左侧为本文方法，右侧为对比方法）

Fig.6Comparison of UAV configuration plans (left is the method in this article, right is the comparison method)

图7任务衔接参数变化图

Fig.7Chart of connection impact indicator

2）无人机配置与无人机使用率：图8为攻击无人机使用率的变化（其余无人机均全部使用）：除初始配置外，本文方法中无人机均全部使用；而对比方法在第2~4次迭代时攻击无人机未全部使用，这是由于无人机比例不合理，侦察无人机数量过少影响侦察任务执行，使得后续攻击任务错过时间窗口，造成攻击无人机资源浪费。在本文方法生成的无人机配置方案中，侦察型多于评估型，攻击型最少。侦察型和评估型无人机性能相同，但侦察任务影响整体任务的执行，故数量较多；攻击无人机速度最快，可以承担更多任务，故数量较少；配置方案与无人机性能参数相符。

图8攻击无人机使用率对比

Fig.8Comparison of attack UAV usage rates

3）无人机配置与任务平均完成时间：图9为任务平均完成时间对比，随无人机数量增加，任务平均完成时间持续减小，前期下降快，后期平缓，说明无人机数量增加呈现边际效应。本文方法始终占优，第2次迭代时本文方法中任务已全部完成，但对比方法中存在未完成任务，因此差距较小；迭代后期，两种方法调整基础相同，增加无人机的影响降低，使得差距逐渐减小。

4）无人机配置与未完成任务：表2为未完成任务情况，图10为未完成数量对比图。在第1次迭代时存在部分攻击和评估任务未完成，本文方法在第2次迭代时增加了侦察无人机，调整后任务全部完成；对比方法增加了攻击无人机，但任务依旧未完成，说明本文方法中分类处理未完成任务的策略是有效的。

3.2.2 多场景下无人机配置方法验证

为验证本文方法在不同场景的有效性，进行如下仿真：在目标和任务数量不变的情况下，随机生成100组目标位置和对应时间窗口，在无人机总数量为7~16这十种情况下随机生成无人机配置方案（这一范围内变化明显），运行本文方法和对比方法，对比任务平均完成时间变化。

图9任务平均完成时间对比

Fig.9Comparison of average mission completion time

表2未完成任务情况

Tab.2 Table of uncompleted missions

图10未完成任务数量对比

Fig.10Comparative chart of uncompleted missions

图11为不同场景下调整后与原方案时间比值的平均值，图中数字为调整前无人机总数量。可以看出本文方法较对比方法始终占优，说明本文方法不同场景中均能够实现对无人机配置的高效调整。在无人机数量为7~9之间时，对比方法的数据存在波动，这是由于此时无人机数量较少且配置方案随机生成，存在部分未完成任务。随着无人机数量增多，增加无人机的积极效果逐渐降低，这与图9中任务平均完成时间的变化趋势相似。

图11任务时间比值对比

Fig.11Comparative chart of the task time ratio

3.3 多无人机SEAD任务规划仿真验证

3.3.1 任务规划方法可行性分析

选择3.2.1节第5次迭代时生成的任务执行方案进行分析，包含9架无人机（3侦察、3攻击、3评估）。图12为任务执行甘特图，图中序号6-1中6为目标编号，1为任务类型。相同颜色的色块为同一目标任务，粉色色块代表任务执行时间，红色三角表示任务时间窗口。可以看出同一目标的多个任务按顺序执行，满足时序耦合约束；任务均在时间窗口内完成，满足时间窗约束；无人机在留空时间限制内返回出发点，满足航程约束。

3.3.2 任务规划方法求解效率分析

为验证本文任务规划方法的求解效率，设置了多种算法进行对比。首先在给定无人机配置方案下分析了算法收敛性能，然后对比不同场景下的算法求解性能。相关算法参数见表3，算法种群数量为100，迭代次数为100。

图13为四种算法在9架无人机（3侦察、3攻击、3评估）时的任务平均完成时间变化，其横坐标为任务规划算法的迭代次数。可以看出，相较于算法1和算法2，本文算法通过增加局部搜索算子，加速了算法收敛并提升了求解质量。本文变异操作主要调整等待时间较长的任务，相较于算法3，本文算法寻优速度更快。

图12任务执行甘特图

Fig.12Mission execution Gantt chart

表3算法参数设置

Tab.3 Parameters of algorithms

图13算法收敛性能对比

Fig.13Comparison of the algorithms convergence

图14为100组场景下的无人机配置调整和任务规划计算：横坐标为上层无人机配置迭代次数，纵坐标为算法最终解与初始最优解的比值，算法使用相同初始种群，比值越小解性能越好。由于第1次迭代时无前序执行方案，无法使用局部搜索算子，故不进行对比。相较于算法1和算法2，由于存在局部搜索算子，本文算法始终占优。计算后期单架无人机承担任务数量较少，局部搜索算子可调整任务数量下降，因此算法之间差异下降。相较于对比算法3，本文算法整体占优但相差很小，与图13中两种算法收敛至相同解的情况相符合，为确保任务规划的求解效果，本文使用了较大的变异概率。

图14多场景下算法效果对比

Fig.14Comparison of the algorithms in multiple scenarios

4 结论

本文针对SEAD场景中无人机配置和任务规划联合优化问题进行研究，在任务规划问题基础上将各类型无人机数量也作为决策变量，充分表征目标、任务和无人机的多种约束，建立无人机编队路径问题模型。设计了双层联合优化方法，将无人机配置与任务规划进行分层处理：上层通过分析无人机数量对任务时间的影响设计了任务衔接参数，评估各类型无人机需求并指导无人机配置调整；下层利用改进遗传算法进行任务规划求解，能够满足多类型约束获得任务执行方案；并设计了局部搜索算子，能够结合无人机数量变化调整执行方案以提升算法寻优效率。

仿真结果表明，无人机数量增加呈现边际效应，合理的无人机配置能够充分发挥各类无人机能力。本文方法能够通过有限次数的迭代获得满足要求的无人机配置及任务执行方案，可以避免无人机配置与任务规划同时求解造成的问题空间非线性扩展，在同等无人机规模下执行方案效果持续占优。该方法为SEAD场景中无人机资源配置与任务规划提供了一套完整的解决方法，可以提高多无人机协同的指控效率。

图1双层联合优化方法结构

Fig.1Structural diagram of the two-level joint optimization method

下载: 全尺寸图片

图2无人机配置调整流程

Fig.2Flow chart of UAV configuration adjustment

下载: 全尺寸图片

图3任务规划计算流程

Fig.3Flow chart of mission planning calculation

下载: 全尺寸图片

图4多层编码示意图

Fig.4Multi-layer coding schematic

下载: 全尺寸图片

图5无人机任务路径计算示意图

Fig.5UAV path calculation schematic

下载: 全尺寸图片

图6无人机配置方案对比（左侧为本文方法，右侧为对比方法）

Fig.6Comparison of UAV configuration plans (left is the method in this article, right is the comparison method)

下载: 全尺寸图片

图7任务衔接参数变化图

Fig.7Chart of connection impact indicator

下载: 全尺寸图片

图8攻击无人机使用率对比

Fig.8Comparison of attack UAV usage rates

下载: 全尺寸图片

图9任务平均完成时间对比

Fig.9Comparison of average mission completion time

下载: 全尺寸图片

图10未完成任务数量对比

Fig.10Comparative chart of uncompleted missions

下载: 全尺寸图片

图11任务时间比值对比

Fig.11Comparative chart of the task time ratio

下载: 全尺寸图片

图12任务执行甘特图

Fig.12Mission execution Gantt chart

下载: 全尺寸图片

图13算法收敛性能对比

Fig.13Comparison of the algorithms convergence

下载: 全尺寸图片

图14多场景下算法效果对比

Fig.14Comparison of the algorithms in multiple scenarios

下载: 全尺寸图片

表1无人机性能数据

下载: 全尺寸图片

表2未完成任务情况

下载: 全尺寸图片

表3算法参数设置

下载: 全尺寸图片

图1双层联合优化方法结构

Fig.1Structural diagram of the two-level joint optimization method

图2无人机配置调整流程

Fig.2Flow chart of UAV configuration adjustment

图3任务规划计算流程

Fig.3Flow chart of mission planning calculation

图4多层编码示意图

Fig.4Multi-layer coding schematic

图5无人机任务路径计算示意图

Fig.5UAV path calculation schematic

图6无人机配置方案对比（左侧为本文方法，右侧为对比方法）

Fig.6Comparison of UAV configuration plans (left is the method in this article, right is the comparison method)

图7任务衔接参数变化图

Fig.7Chart of connection impact indicator

图8攻击无人机使用率对比

Fig.8Comparison of attack UAV usage rates

图9任务平均完成时间对比

Fig.9Comparison of average mission completion time

图10未完成任务数量对比

Fig.10Comparative chart of uncompleted missions

图11任务时间比值对比

Fig.11Comparative chart of the task time ratio

图12任务执行甘特图

Fig.12Mission execution Gantt chart

图13算法收敛性能对比

Fig.13Comparison of the algorithms convergence

图14多场景下算法效果对比

Fig.14Comparison of the algorithms in multiple scenarios

表1无人机性能数据

表2未完成任务情况

表3算法参数设置

图1双层联合优化方法结构

Fig.1Structural diagram of the two-level joint optimization method

图2无人机配置调整流程

Fig.2Flow chart of UAV configuration adjustment

图3任务规划计算流程

Fig.3Flow chart of mission planning calculation

图4多层编码示意图

Fig.4Multi-layer coding schematic

图5无人机任务路径计算示意图

Fig.5UAV path calculation schematic

图6无人机配置方案对比（左侧为本文方法，右侧为对比方法）

Fig.6Comparison of UAV configuration plans (left is the method in this article, right is the comparison method)

图7任务衔接参数变化图

Fig.7Chart of connection impact indicator

图8攻击无人机使用率对比

Fig.8Comparison of attack UAV usage rates

图9任务平均完成时间对比

Fig.9Comparison of average mission completion time

图10未完成任务数量对比

Fig.10Comparative chart of uncompleted missions

图11任务时间比值对比

Fig.11Comparative chart of the task time ratio

图12任务执行甘特图

Fig.12Mission execution Gantt chart

图13算法收敛性能对比

Fig.13Comparison of the algorithms convergence

图14多场景下算法效果对比

Fig.14Comparison of the algorithms in multiple scenarios

表1无人机性能数据

表2未完成任务情况

表3算法参数设置

王祥科, 刘志宏, 丛一睿, 等. 小型固定翼无人机集群综述和未来发展[J]. 航空学报,2020,41(4):20-45. WANG X K, LIU Z H, CONG Y R,et al. Miniature fixed-wing UAV swarms:review and outlook[J]. Acta Aeronautica et Astronautica Sinica,2020,41(4):20-45.(in Chinese)

ZHANG J, XING J H. Cooperative task assignment of multi-UAV system[J]. Chinese Journal of Aeronautics,2020,33(11):2825-2827.

JIA Z Y, YU J Q, AI X L,et al. Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm[J]. Aerospace Science and Technology,2018,76:112-125.

WU W N, WANG X G, CUI N G. Fast and coupled solution for cooperative mission planning of multiple heterogeneous unmanned aerial vehicles[J]. Aerospace Science and Technology,2018,79:131-144.

WANG Z, LIU L, LONG T,et al. Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double-chromosome encoding[J]. Chinese Journal of Aeronautics,2018,31(2):339-350.

OTTO A, AGATZ N, CAMPBELL J,et al. Optimization approaches for civil applications of unmanned aerial vehicles(UAVs)or aerial drones:a survey[J]. Networks,2018,72(4):411-458.

BELLOSO J, JUAN A A, FAULIN J. An iterative biased-randomized heuristic for the fleet size and mix vehicle-routing problem with backhauls[J]. International Transactions in Operational Research,2019,26(1):289-301.

KOĢ Ģ, BEKTAŞ T, JABALI O,et al. The fleet size and mix pollution-routing problem[J]. Transportation Research Part B: Methodological,2014,70:239-254.

JIANG J, NG K M, POH K L,et al. Vehicle routing problem with a heterogeneous fleet and time windows[J]. Expert Systems with Applications,2014,41(8):3748-3760.

PENNA P H V, SUBRAMANIAN A, OCHI L S,et al. A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet[J]. Annals of Operations Research,2019,273(1):5-74.

DENG Q B, YU J Q, MEI Y S. Deadlock-free consecutive task assignment of multiple heterogeneous unmanned aerial vehicles[J]. Journal of Aircraft,2014,51(2):596-605.

严飞, 祝小平, 周洲, 等. 考虑同时攻击约束的多异构无人机实时任务分配[J]. 中国科学: 信息科学,2019,49(5):555-569. YAN F, ZHU X P, ZHOU Z,et al. Real-time task allocation for a heterogeneous multi-UAV simultaneous attack[J]. Scientia Sinica(Informationis),2019,49(5):555-569.(in Chinese)

刘文金, 裴扬, 葛玉雪, 等. 基于ABMS的对地攻击型无人机体系贡献率评估[J]. 航空学报,2022,43(9):436-449. LIU W J, PEI Y, GE Y X,et al. System-of-systems contribution evaluation of ground-attack UCAV based on ABMS[J]. Acta Aeronautica et Astronautica Sinica,2022,43(9):436-449.(in Chinese)

WANG Y, RU Z Y, WANG K Z,et al. Joint deployment and task scheduling optimization for large-scale mobile users in multi-UAV-enabled mobile edge computing[J]. IEEE Transactions on Cybernetics,2020,50(9):3984-3997.

MANDAL S, GAO T S, BHATTACHARYA S. Planning for aerial robot teams for wide-area biometric and phenotypic data collection[C]//Proceedings of 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS),2021:2586-2591.

ZHANG J M, LIU Z, SHI J M,et al. Weapon configuration,allocation and route planning with time windows for multiple unmanned combat air vehicles[J]. Journal of Systems Engineering and Electronics,2018,29(5):953-968.

WANG J F, JIA G W, LIN J C,et al. Cooperative task allocation for heterogeneous multi-UAV using multi-objective optimization algorithm[J]. Journal of Central South University,2020,27(2):432-448.

首页

期刊介绍

投稿指南

编委会

出版声明

开放获取声明

联系我们

期刊订阅

Rss

English

1 联合优化问题建模

2 双层联合优化方法

3 场景仿真验证

4 结论