中国科技核心期刊      中国指挥与控制学会会刊     军事装备类重点期刊
Command Control and Simulation

Command Control and Simulation >

2025 , Vol. 47 >Issue 6: 39 - 45

DOI: https://doi.org/10.3969/j.issn.1673-3819.2025.06.006

Command & Control

Static task allocation algorithm for multi-heterogeneous UAVs based on improved genetic operators

  • WANG Chengfei
Expand
  • No.91977 Troops of PLA, Beijing 100036, China

Received date: 2025-07-28

  Revised date: 2025-09-19

  Online published: 2025-11-22

Fold

Abstract

To address the issues of insufficient global optimality and robustness in traditional mission planning for unmanned aerial vehicles (UAVs) in urban disaster relief scenarios, this paper proposes a multi-heterogeneous UAV static task allocation algorithm based on improved genetic operators. By enhancing genetic operators, designing a functionally coupled chromosome encoding strategy, introducing adaptive crossover and mutation mechanisms, and embedding a path planning module into the task allocation algorithm, the accuracy of the task allocation cost function calculation is improved. This effectively overcomes the drawbacks of traditional methods, such as inaccurate allocation results due to path cost estimation deviations, as well as poor global optimization and robustness.

Key words： path planning; heterogeneous UAV constraint; genetic algorithm; task allocation

Cite this article

WANG Chengfei . Static task allocation algorithm for multi-heterogeneous UAVs based on improved genetic operators[J]. Command Control and Simulation, 2025 , 47(6) : 39 -45 . DOI: 10.3969/j.issn.1673-3819.2025.06.006

随着无人机(Unmanned Aerial Vehicle, UAV)技术的快速发展,其在灾害救援[1]、物流配送[2]、环境监测[3]等城市复杂场景中的应用日益广泛。不同类型的任务通常需要不同功能的无人机协同执行。传统的多异构无人机任务分配方法通常采用“先分配后规划”的串行处理模式,由于未充分考虑实际飞行中的障碍物约束与路径代价,出现总体代价偏高、负载不均衡等问题[4]。
为此,本文针对城市救灾背景下多异构无人机的静态任务分配问题,提出一种基于改进遗传算子的多异构无人机静态任务分配算法,实现了静态任务分配与路径规划的协同优化。仿真结果表明,本文算法在收敛速度、全局优化能力与解的质量方面均优于传统遗传算法,有效验证了其有效性与优越性。

1 多异构无人机静态分配建模

本文提出一种多异构无人机静态任务分配算法,通过合理调度实现无人机和任务的最优匹配。多异构无人机静态任务分配问题可以用E、U、T、C 4个变量描述:其中,E是含障碍物的救灾环境;U= U 1 , U 2 , … , U N u是无人机(UAV)的合集,包括无人机的位置和状态信息等;Nu是无人机的总数量;T= T 1 , T 2 , … , T N t是目标集合,包含目标的位置、任务需求、任务数量等信息;Nt是目标点的总数量;C是所有约束集合,包含每架无人机的航程约束、城市环境的障碍物约束等多重约束。

1.1 异构无人机约束

本文将无人机的异构性分为3类:搜索无人机、运输无人机和综合无人机[5]。搜索无人机仅可执行搜索需求的任务;运输无人机仅可执行运输需求的任务;综合无人机可执行两种任务,3类无人机的总数为Nu。异构无人机的约束体现在以下3个方面:
(1)搜索任务只能由搜索无人机或综合无人机执行,运输任务只能由运输无人机或综合无人机执行;
(2)无人机Ni最多能执行 L t a s k i个任务;
(3)每架无人机根据任务序列完成全部所分配的任务所需飞行距离应小于最大航程距离lenmax。

1.2 异构目标任务约束

定义T= T 1 , T 2 , … , T N t表示目标集合,每个目标随机包含搜索任务和运输任务。对于目标Tj,其任务属性合集表示为Taskj= T a s k j s , T a s k j t,其中Tas k j s∈ 0,1为目标的搜索任务需求,Tas k j t∈ 0,1为目标的运输任务需求,二者不能同时为0。目标点的任务总数如公式(1)所示:
NTask= ∑ j = 1 N t mj
mj∈ 1,2表示目标Tj的任务数。
针对异构多任务场景的约束体现在以下3个方面:
(1)所有目标的所有任务均被分配;
(2)每个目标可能由多个无人机协同执行,但该目标的具体搜索/运输任务只能由一架具备相应功能的无人机单独完成;
(3)目标的每个任务仅能被执行一次。

1.3 地图障碍物约束

本文模拟城市救灾环境,设置无人机飞行的地形障碍物。在计算无人机到目标点的真实飞行路径时,需考虑避障约束。定义每架无人机航迹集合为 T r a i,环境中障碍区域集合为Eobs。

1.4 目标函数

定义分配矩阵X=[xij]∈ R N u × 2 N t,xij∈ 0,1。j为奇数时, x i j + 1 2=1表示无人机i执行目标 j + 1 2的搜索任务;当j为偶数时, x i j + 1 2=1表示无人机i执行目标 j 2的运输任务。定义Xi为矩阵X第i行向量,代表无人机i所分配的任务集合。
本文选择两个标准来量化异构多无人机多任务分配问题的目标函数:一是所有无人机执行任务的累计航程距离,二是所有无人机航程距离的均衡程度。
基于分配矩阵Xi,结合地图中障碍物信息,利用变步长稀疏A*算法求解无人机i在最优的任务执行序列pi下的飞行总航程C X i , p i。任务的总航程如公式(2)所示:
Csum= ∑ i = 1 N u C X i , p i
无人机航程的均衡度如公式(3)所示:
Bl= C m a x - C m i n C m a x×100%
Cmax=Max C X 1 , p 1 , C X 2 , p 2 , … , C X l , p l
Cmin=Min C X 1 , p 1 , C X 2 , p 2 , … , C X l , p l
其中,Bl取值的范围为(0,1),Bl的值越小,表明各无人机的航程代价差值越小,分配结果更均匀。根据以上分析和假设,定义目标函数为
min J=Csum· 1 + ω · B l
其中,ω为均衡度权重,可根据实际应用需求设置不同的权重对结果进行控制。
该问题的约束条件如下:
∑ j = 1 2 N t xij≤ L t a s k i, ∀i=1,2,…,N u,
∑ i = 1 N a xij≤1, ∀j=1,2,…,2Nt,
∑ i = 1 N u ∑ j = 1 2 N t xij=Ntask
C(Xi,pi)≤1enmax, ∀i=1,2,…,Nu
∑ i = 1 N u Trai∩Eobs=ϕ
其中,约束1表示每架无人机最多可执行 L t a s k i任务;约束2表示每个目标下的每个任务只能由一架无人机执行;约束3表示所有目标下的所有任务都被分配;约束4表示每架无人机执行完所有所分配的任务所飞行的航程距离小于无人机最大航程距离;约束5表示所有无人机的航迹集合与地图中障碍物集合无交集。

2 嵌入路径规划的改进遗传算法

2.1 算法整体框架

嵌入路径规划的多层级改进遗传算法描述如下:外层的遗传算法针对异构无人机和异构的目标点任务进行分配,种群中每个个体表示一种无人机-目标任务的分配方案[6];内层的遗传算法得到每种分配方案下每架无人机的最短路径代价。在对当前分配方案下的不同任务序列的不同路径代价进行求解时,内层遗传算法的适应度计算步骤中应嵌入变步长稀疏A*算法以实现避障功能,算法的整体框架如图1所示。
图1 算法整体框架图

Fig.1 Algorithm System Framework Diagram

2.2 染色体编码策略

针对无人机和任务的功能对应性,本文提出一种耦合无人机功能和任务需求的多主体染色体编码策略。本文用每个可行解代表一个任务分配,并将其编码为一个染色体。每个染色体由目标、任务、无人机和无人机功能4个特征组成,每列表示一个指定基因。每条染色体的总基因数应为Ntask。一条耦合无人机功能和任务需求的多主体染色体实例如图2所示。
图2 多主体染色体实例图

Fig.2 Multi-agent chromosome idiogram

场景中共有4个目标点和3架无人机,其中1号和2号目标点存在搜索和运输两种任务,3号目标点仅存在运输任务,4号目标仅存在搜索任务。图2所示的染色体表示的分配方案如下:1号无人机负责执行2号目标和3号目标的运输任务,2号无人机负责执行1号目标和4号目标的搜索任务,3号无人机负责执行1号目标的运输任务和4号目标的搜索任务。
基于无人机和目标两个主体,本文将染色体以不同主体划分为基于无人机的子染色体组和基于目标的子染色体组。基于无人机的子染色体组以无人机的编号序列进行划分,染色体中对应无人机编号相同的基因划分为一个子染色体,并按照1到Nu的顺序对这些子染色体进行排序。同理,基于目标任务的子染色体组以目标的编号序列进行划分,对应相同目标序号的基因划分为一个子染色体,并按照1到Nt的顺序进行排序。示意图如图3和图4所示。
图3 基于无人机的子染色体组示意图

Fig.3 Drone-based sub-chromosomal group schematic diagram

图4 基于目标的子染色体组示意图

Fig.4 Target-based sub-chromosomal group idiogram

由图3和图4可见,基于无人机的子染色体组和基于目标的子染色体组本质上是一条多主体染色体的不同组合排列形式,二者可以相互转换。

2.3 种群初始化与适应度计算

(1)种群初始化
传统遗传算法解决同构无人机任务分配问题时种群初始化是随机进行的[7],但在异构无人机任务分配问题中需针对每个任务的需求和无人机的功能进行对应分配并完成种群初始化。由于初始种群染色体是按照任务需求匹配进行随机生成,因此初始种群染色体是以基于目标的子染色体组的形式呈现。
(2)适应度计算
将染色体种群转换为基于无人机的子染色体组形式。基于本文方法,改进遗传算法中的每条染色体的适应度取决于每架无人机按最优任务序列执行完所有分配任务的最短航程,即路径代价。因此作者要单独针对每一架无人机内部的最优任务序列以及最优路径规划进行分析,并在计算每种任务执行顺序下的最短路径代价时,嵌入变步长稀疏A*算法来实现避障功能,再由公式(6)得到每条染色体的适应度。具体流程如图5所示。
图5 内层遗传算法流程图

Fig.5 Inner layer genetic algorithm flowchart

2.4 改进的遗传算子

(1)选择算子
本文基于精英保留策略的分层差异化选择策略,针对不同适应度层次的染色体采用差异化的策略进行选择,实现全局最优和收敛能力的平衡。具体实现流程如下:
步骤1:将种群中所有染色体按照适应度高低进行排序后,将每代种群中适应度排序前30%的个体划分为上层,并直接保留进入下一代种群中。
步骤2:中间30%~70%的个体划分为中层种群,采用动态锦标赛选择法针对这部分种群个体进行选择操作。定义当前种群染色体的平均适应度值为f,与上一代种群的平均适应度差值为Δf。如果Δf较大,则减少锦标赛规模k以保持种群多样性;如果Δf较小则增大锦标赛规模k以增强选择压力加速收敛。锦标赛选择规模k的动态调整公式如下:
k=kmin+(kmax-kmin)· Δ f Δ f m a x
其中,kmin和kmax分别为锦标赛选择规模的下限和上限,Δfmax为最大适应度变化率。
步骤3:其余的30%个体划分为底层种群,采用轮盘赌的方式,按照与适应度值成反比的概率选择部分个体进入下一代种群。假定底层种群的数量为Na,fi为个体的适应度,则每个染色体个体被选中的概率公式如下:
pi= f i ∑ i = 1 N a f i.
(2)交叉算子
本文设计的交叉算子步骤如下:
步骤1:将种群中所有染色体转换为基于目标的子染色体组形式,并将种群中的每个染色体划分为基于目标的子染色体组合形式,保证不同染色体的相同位置处的基因对应的目标以及任务是唯一且一致的,且都在被分配的约束内;
步骤2:选择基于位置的多点交叉的方式,对染色体中多个位置的基因进行互换;
步骤3:将完成交叉操作的种群中染色体转换回基于无人机的子染色体组形式,验证是否满足无人机最大任务量约束。图6展示了交叉操作的一个实例。
图6 交叉操作示意图

Fig.6 Interlace operation schematic diagram

假设每架无人机最多能执行4个任务。算法选择父代染色体的第三列和第五列进行基于位置的多点交叉,互换父代染色体1和父代染色体2上的第三、五列基因,从而得到两个新的后代染色体。算法将两个子代染色体转换为基于无人机的子染色体组形式,验证子代染色体的每架无人机所分配到的任务数不大于4,若满足,则得到符合模型约束的两条后代染色体。
(3)变异算子
针对异构无人机的任务分配问题[9],算法选择针对基因上的无人机元素进行变异,具体实例如图7所示。
图7 变异操作示意图

Fig.7 Mutation operation schematic diagram

假设每架无人机最多能执行4个任务。算法对父代染色体选择染色体上的第五列基因进行变异操作[10],保留基因的第1、2行,仅改变第3、4行。按照初始化的配对流程,算法从具有运输能力的无人机集合中随机选中3号无人机来执行3号目标点的运输任务,得到变异后的子代染色体。算法将两个子代染色体转换为基于无人机的子染色体组形式,验证子代染色体的每架无人机所分配到的任务数不大于4,若满足,则得到符合模型约束的后代染色体。
(4)数量-概率双自适应性调整
本文提出一种基于种群进化程度的数量-概率双自适应性调整策略。算法根据选择和交叉操作选中的基因数量,采用Sigmoid函数进行动态调整。算法计算每代种群染色体的平均适应度值favg,通过比较每个个体的适应度值fi与favg,得到Δfi。根据Δfi的正负值,算法将种群分为高适应度种群和低适应度种群。交叉操作的基因数量Nc和变异操作的基因数量Nm的动态调整公式如下:
Nc= N c l · 1 - 1 1 + e - α Δ f i , Δ f i ≥ 0 N c 2 · 1 1 + e - α Δ f i , Δ f i < 0
Nm= N m l · 1 - 1 1 + e - α Δ f i , Δ f i ≥ 0 N m 2 · 1 1 + e - α Δ f i , Δ f i < 0
其中,Nc1和Nc2分别为高适应度种群的交叉基因数量下限和低适应度种群的交叉基因数量上限;Nm1和Nm2分别为高适应度种群的变异基因数量下限和低适应度种群的变异基因数量上限;α为Sigmoid函数的斜率参数。通过公式(15)和公式(16)可以根据种群的进化状态动态调整交叉和变异操作的基因数量。针对交叉概率pc和变异概率pm,本文采用自适应调整策略,交叉概率pc和变异概率pm的动态调整公式如下:
pc= p c 1 - ( p c 1 - p c 2 ) × ( f i - f a v g ) f m a x - f a v g , f i ≥ f a v g p c 1 , f i < f a v g
pm= p m 1 - ( p m 1 - p m 2 ) × ( f i - f a v g ) f m a x - f a v g , f i ≥ f a v g p m 1 , f i < f a v g
其中,pc1和pc2分别为最大、最小的交叉概率;pm1和pm2分别为最大、最小的变异概率;fmax和fmin为种群最大、最小适应度值。

2.5 算法整体流程图

本文所提出的嵌入路径规划的改进遗传算法整体流程如图8所示。
图8 改进的遗传算法流程图

Fig.8 Improved genetic algorithm flowchart

3 案例分析

为验证本文改进遗传算法的有效性,在Matlab平台中进行仿真验证。针对城市救灾场景,算法设计一个大小为100 m×100 m×50 m包含若干障碍物的三维空间,随机生成6架异构无人机和11个多类型任务点(包含搜索任务和运输任务),无人机集合和任务点集合的信息如表1和表2所示。
表1 无人机信息

Tab.1 UAV Information

编号 类型 位置 任务数
U1 搜索 (10, 2, 18) 4
U2 运输 (25, 2, 18) 4
U3 综合 (40, 2, 18) 4
U4 运输 (55, 2, 18) 4
U5 搜索 (70, 2, 18) 4
U6 综合 (85, 2, 18) 4
表2 任务点信息

Tab.2 Task point information

编号 数量 种类 位置
T1 2 搜索 T 1 1、运输 T 1 2 (21, 18, 20)
T2 2 搜索 T 2 1、运输 T 2 2 (53, 20, 20)
T3 1 运输 T 3 2 (83, 25, 20)
T4 1 运输 T 4 2 (10, 45, 20)
T5 1 搜索 T 5 1 (62, 35, 20)
T6 2 搜索 T 6 1、运输 T 6 2 (30, 60, 27)
T7 1 搜索 T 7 1 (90, 60, 20)
T8 1 搜索 T 8 1 (15, 80, 30)
T9 2 搜索 T 9 1、运输 T 9 2 (62, 75, 30)
T10 2 搜索 T 10 1、运输 T 10 2 (79, 82, 35)
T11 2 搜索 T 11 1、运输 T 11 2 (45, 92, 25)
无人机和任务点的位置分布如图9和图10所示。无人机用三角形表示,蓝色三角形代表搜索无人机;绿色三角形代表运输无人机;红色三角形代表综合无人机。任务点用黑色五角星表示,随机分布于地图中。灰色长方体代表城市环境中的楼宇障碍物,4个楼宇障碍物的中心点分别为(33,40,14)、(35,75,15)、(70,41,20)和(90,44,15),尺寸分别为34 m×30 m×26 m、30 m×22 m×24 m、10 m×50 m×40 m和20 m×16 m×30 m。
图9 多异构无人机静态分布场景图

Fig.9 Multi-heterogeneous UAV static allocation scenario diagram

图10 多异构无人机任务点位置场景图

Fig.10 Multi-Heterogeneous UAV static allocation scenario diagram

针对上述场景,分别采用传统遗传算法和本文所提嵌入变步长稀疏A*算法的改进遗传算法进行任务分配。算法参数设置如下:种群数量为100,最大和最小交叉概率分别为0.9和0.5,最大和最小变异概率分别为0.1和0.001,迭代次数为200次。两种算法的目标函数迭代图如图11所示[8]。
图11 两种算法目标函数迭代图

Fig.11 Objective function iteration diagram of two algorithms

由图11可知,传统遗传算法迭代至第64次;陷入局部最优值879.572 1直至结束,整体收敛速度较慢且波动较大,在陷入局部最优后未能继续进化;本文提出的改进遗传算法在第84次迭代中达到全局最优值811.623 9,自适应交叉和变异的设计使得改进的遗传算法比传统遗传算法具有更好的收敛效果以及全局寻优能力。
嵌入变步长稀疏A*算法的双层遗传算法所得最优分配方案如表3所示。
表3 任务分配方案

Tab.3 Task allocation scheme

编号 任务序列 总路径代价/m
U1 T 1 1→ T 6 1→ T 8 1 94.180 7
U2 T 1 2→ T 4 2→ T 6 2 73.798 1
U3 T 11 1→ T 11 2 97.978 1
U4 T 2 2→ T 9 2→ T 10 2 94.498 7
U5 T 2 1→ T 5 1→ T 9 1 86.672 5
U6 T 3 2→ T 7 1→ T 10 1 91.888 7
整体分配结果示意图,如图12和图13所示:其中,绿色线代表搜索无人机的轨迹,蓝色线代表运输无人机的轨迹,红色线代表综合无人机的轨迹;实线代表同时执行搜索任务和运输任务,虚线代表执行搜索任务,点虚线代表执行运输任务。
图12 任务分配示意图

Fig.12 Task distribution diagram

图13 分配结果示意图

Fig.13 Allocation result schematic diagram

由表3和图12、图13可见,本文提出的静态任务分配算法针对多异构无人机多任务点的分配场景得到了可行的分配结果,在满足避障约束的情况下实现了每架无人机的路径代价均衡程度与无人机编队整体的路径代价值综合最优,保证多无人机系统能在短时间内均衡地完成场景中所有任务。

4 结束语

本文针对异构无人机任务分配问题,建立了综合总路径代价值和路径代价平衡度的数学模型,并基于该模型提出了一种耦合路径规划的双层改进遗传算法。通过双层遗传算法分别寻找最优无人机-任务的配对方案以及每架无人机的最优任务序列,突破了传统“先分配后规划”的串行处理方式,创新性地构建了任务分配与路径规划紧密耦合的系统架构。通过在任务分配算法中嵌入路径规划模块,能够提高任务分配成本函数计算的准确性,从而有效克服传统方法因路径代价估计偏差导致的分配结果失准问题。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
ZHU L, WEN G, LIANG Y, LUO D, JIAN H. Multi-target enumeration and localization in distributed MIMO radar based on energy modeling and compressive sensing[J]. IEEE Transactions on Aerospace and Electronic Systems, 2023, 59(4): 4 493-4 510.

DOI

[2]
SUN X, CHAI R, CHAI S, ZHANG B, TSOURDOS A. Flexible final-time stochastic differential dynamic programming for autonomous vehicle trajectory optimization[J]. IEEE Transactions on Aerospace and Electronic Systems, 2023, 59(5): 6 658-6 669.

[3]
HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.

[4]
CONG R, QI J, WU C, WANG M, GUO J. Multi-UAVs cooperative detection based on improved NSGA-Ⅱ algorithm[C]// 2020 39th Chinese Control Conference (CCC). Shenyang, 2020: 1 524-1 529.

[5]
JING D, JIAN C, MIN S. Cooperative task assignment for heterogeneous multi-UAVs based on differential evolution algorithm[C]// IEEE International Conference on Intelligent Computing and Intelligent Systems. Shanghai, 2009: 163-167.

[6]
LUO Q, WANG H, ZHENG Y, HE J. Research on path planning of mobile robot based on improved ant colony algorithm[J]. Neural Computing and Applications, 2020, 32(3): 1 555-1 566.

DOI

[7]
ROBERT Z, ANTHONY S. Market-based multi-robot coordination for complex tasks[J]. The International Journal of Robotics Research, 2006, 25(1): 73-101.

DOI

[8]
GAO H, FENG J, XIAO Y, ZHANG B, WANG W. A UAV-assisted multi-task allocation method for mobile crowd sensing[J]. IEEE Transactions on Mobile Computing, 2023, 22(7): 3 790-3 804.

DOI

[9]
VERMA D, MESSON D, RASTOGI M, SINGH A. Comparative study of various approaches of Dijkstra algorithm[C]// 2021 International Conference on Computing, Communication, and Intelligent Systems (ICCCIS). Greater Noida, 2021: 328-336.

[10]
KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots[J]. The International Journal of Robotics Research, 1986, 5(1): 90-98.

Options
Outlines

/

〈 〉