基于改进人工蜂群算法的多无人机灭火任务规划

2020-12-14张小孟胡永江李文广庞强伟袁国刚

中国惯性技术学报 2020年4期

张小孟，胡永江，李文广，庞强伟，袁国刚

（1.陆军工程大学无人机工程系，石家庄 050003；2.31700 部队，辽阳 111000）

随着无人机技术的快速发展，其在情报搜集、电子侦察、指控通信、战损评估等军事领域，以及灾情预警、事故救援、消防灭火等民用领域都发挥着越来越重要的作用。无人机运用模式也逐渐由单机向多机协同方向发展[1]，其中灭火救援是多无人机应用的一个重要方面[2]。受到用火习俗以及气候等多种因素的影响，山火灾害特别容易在短时间内集中爆发。当一个区域同时爆发多处山火时，需要迅速地根据各个火点的火情及位置情况，对其进行灭火救援，而使用无人机投放灭火弹对山火火点进行灭火是一种快速高效的灭火方法。

在火情高发期，通过使用多个无人机共同对多个火点目标投放灭火弹，可以快速实现对多个火点火情的控制。无人机投放灭火弹需要针对具体的任务需求，为各无人机合理分配火点目标，使各无人机以较小的代价完成灭火救援任务，该过程即为多无人机对多火点火场灭火救援任务规划过程。

目前在多无人机任务规划过程中,关于无人机航路的可行性以及避险问题规划的研究已相对成熟[3-7]。但对于高效救援多个不同价值目标时的任务规划问题，还有一定的研究空间。针对多无人机对多目标任务规划问题，文献[8]建立了混合整数线性规划模型，文献[9]建立了多目标优化问题模型，文献[10]建立了多旅行商问题模型。根据这些模型，文献[11]提出了一种改进量子粒子群算法，文献[12]通过引入Metropolis 准则的方式提出改进人工蜂群算法，文献[13]设计了一种蝗虫仿生算法，但是这些算法局限于传统单一约束问题，无法求解多约束的实际问题，算法的普适性很差。文献[14]提出了一种基于整数编码的多种群混合遗传算法(Multi-Population Hybrid Genetic Algorithm,MPHGA)，该算法的收敛性较强，且任务规划效果较好，但该算法仅适用于目标价值固定的情况，对于目标价值变化的情况普适性较差。

上述方法在一定程度上能够解决多无人机对多目标的任务规划问题，但在解决多无人机对多火点火场灭火救援任务规划问题时仍存在以下几点不足：1）忽略了火点目标救援价值的时变性对任务规划效果的影响[15]。在实际应用中，不同的目标对救援效果有着不同的影响，甚至在救援过程的不同时期，同一个目标产生的影响也是不同的，即目标对整体救援态势的影响是随时间变化的。在任务规划的过程中必须考虑目标价值的时变性，进而增强任务规划的可靠性。2）没有考虑救援资源的有限性[16]。在实际灭火救援过程中，可用的无人机数量和挂载灭火弹的数量有限，可能无法保证对所有目标实施救援，指挥者需要根据目标实际价值和位置情况进行综合决策。因此在救援资源有限的条件下，任务规划必须考虑指挥者的综合决策，以保证用有限的救援资源，收到尽可能大的救援效益。3）未考虑实际情况对任务规划算法的约束性[14]。在多无人机对多火点火场灭火救援任务规划过程中，由于无人机挂载灭火弹数量和任务无人机的航程有限，寻优过程中的所有可行解都需要满足载弹量和无人机航程限制，才能保证算法收敛的准确性和快速性，防止无用解占用规划资源。

针对以上问题，本文提出了一种多无人机对多火点火场灭火救援任务规划方法。首先，在考虑火点目标价值时变性的基础上，建立了目标价值随时间变化的多无人机任务规划模型，可实现根据指挥者的决策意图来进行合理救援。然后，在标准人工蜂群算法的基础上引入了整数编码以及三种算子操作，用来解决有约束的任务规划问题。最后，进行了仿真实验。结果表明该任务规划算法具有寻优能力强、寻优效率高的优点，不仅可以有效解决目标价值随时间变化的任务规划问题，而且可以在无人机数量不能满足对所有火点目标进行饱和救援的情况下，根据指挥者的决策意图进行有效的任务规划。

1 多目标救援模型

1.1 问题描述

假设在进行灭火任务之前，通过前期对区域火情的分析，已确定各个火点目标的位置信息、目标价值以及价值随时间变化情况等。在实施灭火任务过程中，各无人机均从地面站起飞，根据任务规划结果有序完成对指定火点目标的救援任务，并在任务结束后回到地面站。

多无人机对多火点火场灭火救援任务规划问题可描述为：给定待救援的火点目标集合target = {T1,T2…TNt}和Nu架灭火无人机UAVi(i=1,2…Nu)，所有待救援目标的价值集合为Value = {V1,V2…VNt}，各个目标价值随时间改变情况的集合为Change = {C1,C2…CNt}。

在选定地面站位置的条件下，设计一种可通过调节整体任务价值和路径代价的权重系数来实现指挥员决策意图的任务规划方法。同时在救援资源有限的情况下实现救援目标价值的最大化，增强规划方法的普适性。

1.2 目标函数

多无人机执行对多火点火场灭火救援任务需要在获取尽可能大的救援总收益同时，尽可能地减小无人机的滞空时间，降低任务执行过程中的能量损耗，即需要在目标总收益与无人机总滞空时间之间进行综合优化。

在无人机实施目标救援的过程中，设Xi j为决策变量，其取值为1 时表示无人机UAVi对救援目标Tj实施救援，0 表示不实施救援。

（1）救援目标的总收益。假设目标价值随时间的改变情况为目标价值关于时间的负指数函数，则总价值收益为：

其中C j=e-d jt为目标价值随时间变化的函数，dj为目标Tj随时间的衰减的系数；ti为无人机UAVi从离开基地到救援目标Tj时所经历的时间。

（2）总滞空时间。随着无人机在执行灭火任务过程中滞空时间的增长，火情引起的强上升气流及强热辐射对无人机造成损伤的概率增加，能量损耗增多，因此要求无人机总滞空时间要尽可能的短，即：

其中pathi为第i架无人机UAVi执行灭火任务所分配到的目标序列时所需的路径代价，vi为UAVi的巡航速度。

（3）目标函数。考虑到指挥员需要根据救援目标总收益与总滞空时间进行综合决策，目标函数通过分配不同的权重将多目标寻优问题转换为单目标寻优问题。

其中p，q为权重系数，β为补偿系数（使两个目标函数处于同一数量级）。

1.3 约束条件

（1）单架无人机执行任务的能力约束：

其中Bi为第i架无人机UAVi的最大挂载灭火弹数量。

（2）无人机的航程约束。受无人机机载能源的限制，无人机的航程不能超过自身最大航程Di，则

（3）目标价值约束。无人机执行任务的最大价值之和不能超过所有目标的总价值：

2 预先路径规划

由于在任务区域内可能存在障碍物、火情引起的强上升气流及强热辐射等因素产生的禁飞区影响无人机飞行，为了确保无人机在任务区域内有可飞路径，在进行任务规划之前，需要对无人机的可飞路径进行预先规划，以增强任务规划的可行性及准确性。

可飞路径的预先规划首先需要用栅格法在任务区域内建立包含目标位置和禁飞区的路径规划空间模型，然后利用A 星算法求得初始较优路径，最后在上述求得的较优路径的基础上，利用遗传算法求得最优路径。通过以上算法获取无人机基地到每个目标点和任意两目标点之间的可飞路径，并准确计算得到所有路径代价矩阵，为任务规划提供有效依据。预先路径规划流程如图1所示。

图1 预先路径规划流程图Fig.1 Flow chart of advance path planning

3 改进的人工蜂群算法

3.1 标准人工蜂群算法

标准人工蜂群算法（Artificial Bee Colony，ABC）包括三个组成部分，即蜜源位置、花蜜量和三种蜜蜂（雇佣蜂、跟随蜂和侦察蜂）[17]。每个蜜源位置代表了需要优化问题的一个可行的解决方案，其花蜜量对应于解决方案的质量即适应度值。每一种蜜蜂都会执行一个特定的操作来产生新的候选蜜源位置。雇佣蜂也称为引领蜂，其存储有某一蜜源的相关信息，并且可以在蜜源周围搜寻新的蜜源；跟随蜂在蜂巢中通过雇佣蜂分享的信息寻找相关蜜源，侦察蜂是在雇佣蜂和跟随蜂都找不到更好的邻近蜜源时，进行随机搜索以寻找新的蜜源位置。因此，标准ABC 算法将雇佣蜂和跟随蜂视为执行局部搜索，而侦察蜂则执行全局搜索。

3.2 改进的ABC 算法

标准ABC 算法只能用于求解无约束连续问题，针对有约束的无人机任务规划问题，本章采取一种基于整数编码的改进人工蜂群算法，用以解决有约束的任务规划问题，其核心包括种群初始化、改进雇佣蜂阶段、改进跟随蜂阶段以及改进侦察蜂阶段。

3.2.1 种群初始化

根据无人机以及任务目标的序列信息，借鉴遗传算法的编码形式，随机生成一个m=Nt+Nu-1 位的整数序列（M1,M2…Mm），代表一个蜜源位置。其中编码值小于或等于Nt的为目标编码；大于Nt的为无人机编码，假设为Hj，则无人机真实序列号为：j=Hj-Nt+1。从左边开始到第一个无人机编码之前的编码序列为UAV1救援序列，之后的两个相邻无人机编码之间所对应目标编码组成的序列为UAVj救援序列，UAVj为对应序列最左侧编码对应无人机序列，以此类推。

假设待救援目标数Nt=10，无人机数Nu=3，无人机的载弹量B=4，则m=12。如图2所示，该编码对应的UAV1救援序列为T2-T5-T9-T3-T10，UAV2救援序列为T4-T8-T7，UAV3救援序列为T1-T6。

图2 初始蜜源编码Fig.2 Initial honey source coding

因无人机载弹量有限，则两个无人机编码之间的目标编码个数不能超过无人机最大载弹量，当判断目标个数超出载弹量时，对当前的蜜源位置重新初始化，直至满足条件，因图2中，UAV1救援目标为5 个，超过载弹量B=4，不满足条件，则重新生成蜜源序列，如图3所示，新序列中各个无人机救援序列分别为：UAV1救援序列为T2-T5-T9-T3，UAV2救援序列为T1-T6，UAV3救援序列为T10-T4-T8-T7,均满足载弹量要求。

图3 载弹量约束编码Fig.3 Payload constraint coding

考虑到无人机存在航程约束，当无人机从基地起飞经过救援目标序列再回到基地时出现路径代价之和超过最大航程约束时，当前蜜源位置也需要重新初始化。

用以上编码方式生成SN个整数序列作为改进ABC 算法初始化种群，其中SN是蜜源数量。

3.2.2 改进雇佣蜂阶段

雇佣蜂通常在蜜源附近进行邻域搜索。为了表示邻域搜索的行为，引入逆向算子操作，其过程如图4根据以下步骤进行：

图4 逆向算子操作Fig.4 Reverse operator operation

步骤1 从1 到m（位置总数）之间随机生成两个整数r1和r2；

步骤2 将r1到r2之间的编码序列反转，得到新序列；

步骤3 检验新序列是否满足载弹量和航程约束要求，若满足则使用新序列码作为新的蜜源，若不满足则转至步骤1。

为进一步提高邻域搜索能力，雇佣蜂阶段再引入交叉算子操作，用选择的蜜源和现有最优蜜源做为双亲，创造出更好的后代，其操作过程如图5按以下步骤进行。

图5 交叉算子操作Fig.5 Crossover operator operation

步骤1 从1 到m之间随机生成两个整数r1和r2；

步骤2 选择r1和r2作为两个交叉点；

步骤3 从步骤2 交换的数据中通过映射关系替换子代中的重复数，得到新序列；

步骤4 检验新序列是否满足载弹量和航程约束要求，若满足则使用新编码序列作为新的蜜源，若不满足则转至步骤1。

使用逆向算子操作和交叉算子操作对雇佣蜂进行邻域搜索，并在当前蜜源和新的邻近蜜源之间进行贪婪选择，以保证更好的蜜源被保留下来供进一步进化。贪婪选择是基于蜜源的适应度值，计算公式为：

其中fi是模型的目标函数，fiti为适应度函数。

3.2.3 改进跟随蜂阶段

跟随蜂是按轮盘赌方式在雇佣蜂种群中选择的较优的种群，计算公式为：

跟随蜂阶段同样根据收益率大小来选择蜜源位置，使用逆向算子操作和交叉算子操作来进行邻域搜索产生新的蜜源，收益率通过适应度值来表示。同雇佣蜂阶段一样，使用贪婪选择保留更优蜜源。

3.2.4 改进侦察蜂阶段

如果在有限的迭代次数内，雇佣蜂和跟随蜂邻域搜索没有找到更优蜜源时，则将其作为侦察蜂。

通过在现有的最优蜜源的基础上应用变异算子操作，使侦察蜂可以在全局范围内发现新的蜜源，其操作过程如图6按以下步骤进行。

图6 变异算子操作Fig.6 Mutation operator operation

步骤1 从1 到m之间随机生成一个整数r1；

步骤2 将所选序列码中的r1位置的编码随机变异为另一位置的编码，假设为r2位置，交换r1位置和r2位置，得到新序列；

步骤3 检验新序列是否满足载弹量和航程约束要求，若满足则使用新序列码作为新的蜜源，若不满足则转至步骤1。

通过逆向算子操作，雇佣蜂可以生成新的邻近蜜源，跟随蜂可以通过邻域搜索生成更多的蜜源，用来提高其局部搜索能力。通过交叉算子操作，可以进一步提高蜂群的局部搜索能力。通过变异算子操作，侦察蜂可以根据当前最优解生成新的蜜源，防止搜索陷入局部最优。

为了提高收敛速度和解的多样性，逆向算子操作和交叉算子操作是在满足逆向概率Pr和交叉概率Pc（0 ＜Pr，Pc＜ 1）的情况下进行的，而变异算子操作是在侦察蜂阶段进行的，只有当雇佣蜂和跟随蜂在有限次迭代内都无法找到更优的蜜源时，变异算子操作才被激活。

3.3 算法步骤

改进ABC 算法步骤如图7所示。

图7 改进ABC 算法流程图Fig.7 Improved ABC algorithm flowchart

步骤1：种群初始化。设置初始化参数，对初始蜜源编码，生成初始种群；

步骤2：改进雇佣蜂阶段。使用带概率的逆向算子、交叉算子操作对每个雇佣蜂进行邻域搜索，使用贪婪选择保留更好的解；

步骤3：选择产生跟随蜂。按轮盘赌方式选择较优种群作为跟随蜂种群；

步骤4：改进跟随蜂阶段。同雇佣蜂一样，使用带概率的逆向算子、交叉算子操作对每个跟随蜂进行邻域搜索，使用贪婪选择保留更好的解；

步骤5：判断是否产生侦察蜂。如果产生，对当前最佳蜜源实施变异算子操作进行全局搜索；

步骤6：判断是否满足终止条件。若满足则输出最优解，否则转至步骤2。

3.4 收敛性分析

假设人工蜂群中蜂群个体的更新概率为P，由改进人工蜂群算法中蜂群个体的逆向算子操作和交叉算子操作概率（0 ＜Pr，Pc＜ 1）,可知P∈(0,1)，因此，蜂群个体的每一步更新概率都小于1，且更新过程中构成 Markov 链，即任意解间依概率可达，并对其它蜂群个体的更新不产生影响（独立同分布）。同时，蜂群的种群序列是单调的。由上述理论分析及依概率收敛定理可知，该算法满足依概率1 收敛到全局最优解的充要条件。

4 仿真实验

仿真实验平台为Inter Core i5-7300HQ CPU,8GB,64 位Win10 操作系统惠普笔记本。编程工具为Matlab R2017b（64 位）。

4.1 参数设置

假设某基地机场有3 架无人机，现有30 个待救援的火点目标，每架无人机的最大载弹量为6，无人机参数如表1，目标位置参数如表2，目标的价值及衰减参数情况如表3。为直观反映任务规划效果，在仿真实验中将无人机基地到每个火点目标和任意两个火点目标之间的直线路径作为可飞路径，距离作为路径代价。

由表1、2、3 可得出目标和无人机位置参数如图8所示，其中初始价值大于0.5 的为重要目标，其余为一般目标。

表1 无人机参数Tab.1 UAV parameters

表2 目标位置参数Tab.2 Target position parameters

表3 目标的价值及衰减参数Tab.3 Target value and attenuation parameters

图8 无人机和目标位置Fig.8 UAVs and target location

4.2 实验结果及分析

实验一：在目标价值不存在时变的情况下，对提出的改进ABC 算法有效性进行验证。

如表2所示，重要目标有15 个，每架无人机的载弹量为6 发，需要3 架无人机完成任务。用改进ABC算法和文献[11]提出的多种群遗传算法（MPHGA）进行对比实验。实验次数为100 次，种群规模为100，最大迭代次数为100，改进ABC 算法中蜜源最大搜索次数limit为10，逆向概率Pc和交叉概率Pr均为0.85；MPHGA 算法中子种群数为4。仿真结果如图9、图10、图11 所示，代价结果如表4所示。

图9 改进ABC 算法救援路径Fig.9 Rescue path of improved ABC algorithm

图10 MPHGA 算法救援路径Fig.10 Rescue path of MPHGA algorithm

图11 两种算法对比Fig.11 Comparison of two algorithms

表4 两种算法对比Tab.4 Comparison of two algorithms

结果分析如下：

（1）由图9，图10 可得，两种算法均能有效完成对所有重要目标的救援，验证了所提算法的可行性。

（2）由表4两种算法对比可得，在目标价值不存在时间衰减的情况下，所有被救援目标的总价值不变，主要影响因素为完成所有救援任务的时间代价，其中100 次仿真中MPHGA 算法的3 架无人机对15 个重点目标有效救援的总滞空时间平均为43 min，改进ABC算法则为42 min，滞空时间即完成任务时间降低了2.3%，说明改进ABC 算法的寻优能力优于MPHGA算法。

（3）由图11 两种算法有限次迭代的收敛状况对比可得，改进ABC 算法平均在迭代12 次就达到了全局最优解；而MPHGA 算法在迭代79 次后最终陷入局部最优，得出次优解。改进算法的寻优时间仅为MPHGA 算法的15.2%，说明改进ABC 算法的寻优效率优于MPHGA 算法。

实验二：在考虑目标价值时变的情况下，通过调整权重系数来反映决策者意图，从而来验证所提算法的普适性。

当无人机数量不能满足救援所有目标的情况时，决策者就必须有取舍的去选择救援一些更有价值的目标。因此，针对决策者对目标价值和滞空时间的权重要求，分别对权重系数分配不同时无人机救援任务规划情况进行仿真，能够更加体现算法在应对各种情况时的适用性，同时通过对比其仿真结果，也能够为决策者提供最佳决策。

图12 p = 1,q = 0 时改进ABC 算法救援路径Fig.12 p = 1,q = 0 improved ABC algorithm rescue path

图13 p = 1,q = 0 时MPHGA 算法救援路径Fig.13 p = 1,q = 0 MPHGA algorithm rescue path

假设无人机的数量为3，改进ABC 算法中种群规模为100，最大迭代次数为200，蜜源最大搜索次数limit为10，逆向概率Pc和交叉概率Pr均为0.85，MPHGA 算法中子种群数为4。在权重系数为p= 1,q= 0；p=q= 0.5；p= 0,q= 1 时两种算法的仿真结果如图12、图13、图14、图15、图16、图17 及表5。

图14 p = q = 0.5 时改进ABC 算法救援路径Fig.14 p = q = 0.5 improved ABC algorithm rescue path

图15 p = q = 0.5 时MPHGA 算法救援路径Fig.15 p = q = 0.5 MPHGA algorithm rescue path

图16 p = 0,q = 1 时改进ABC 算法救援路径Fig.16 p = 0,q = 1 improved ABC algorithm rescue path

图17 p = 0,q = 1 时MPHGA 算法救援路径Fig.17 p = 0,q = 1 MPHGA algorithm rescue path

表5 三种不同权重情况对比Tab.5 Comparison of three different weights

结果分析如下：

（1）分析图12 及表5在p= 1，q= 0 时可以得出，决策者在不考虑滞空时间代价，只关注目标价值的情况下，无人机救援序列中没有重点目标T8，因为其初始价值参数为0.6 较小，衰减参数为较大的0.9，并且离基地的距离较远，其价值衰减严重，当无人机数量不足时，相对于其他重要目标救援的价值较小，进一步验证了目标价值随时间变化是决策者在进行任务规划时必须要考虑的因素，图14、图15 中较远的重要目标没有被救援也间接说明了所提因素。

（2）分析图16、图17 及表5在p= 0，q= 1 时可以得出，决策者在不考虑目标价值大小，只关注滞空时间的情况下，算法按照无人机最大载弹就近救援任务目标，滞空时间最短，符合决策者意图，验证了算法的有效性。

（3）对比图12、图14、图16 及图13、图15、图17 和表5可得出，因目标函数中目标价值收益取负相关（即“-p”），则当目标价值收益权重系数p变小，而滞空时间权重系数q变大时，无人机对重点目标的救援数量呈现递减趋势，无人机救援目标总价值减小，又滞空时间权重系数q决定的总路径代价在减小，使得无人机的飞行安全价值增加。说明两种算法都可以有效根据决策者的意图通过调整权重系数对救援任务进行规划。

（4）分别对比图12 和图13、图16 和图17、图14 和图15 以及表5中两种算法在权重系数相同情况下的相关数据可得，在只关注目标价值时所提算法目标总价值高于现有算法1.4%；只关注滞空时间时所提算法的滞空时间短于现有算法4.9%；当滞空时间和目标价值的权重系数都为0.5 时所提算法的滞空时间短于现有算法6.5%，同时目标总价值高于现有算法3.2%。说明所提改进ABC 算法的寻优能力高于现有的MPHGA 算法。