打开文本图片集

摘要：本文在标准狼群算法的基础上，根据狼群的不同分工，对游走行为和围攻行为进行了改进，并与拍卖算法相结合，提出了改进狼群融合拍卖算法，以解决所无人机的多任务分配问题，并基于Markov链对算法的收敛性进行了证明。最后通过MATLAB进行仿真，并与蜂群算法进行比较，仿真结果表明该算法具有较好的全局搜索能力，收敛速度快。

关键词：无人机；任务分配；狼群算法；拍卖算法

0 引言

无人机（Unmanned Aerial Vehicle，UAV）和载人飞机相比较，有着价格低廉、应用领域广泛、可避免人员伤亡等优点，被大量应用在军事侦察领域[1]。随着无人机应用领域的不断多样化，如何高效的实现无人机的任务分配成为当前研究的重点[2]。任务分配是指根据无人机自身情况、实际环境以及任务要求，将任务有序指派给相应无人机，对无人机所需完成的具体任务进行预先设定与统筹管理，使无人机在航线距离、任务代价、目标收益等约束条件下的整体效能达到最优。

智能仿生算法因易于实现，鲁棒性较高等优点在无人机任务分配问题上具有明显的应用优势。薛凯[3]在数学规划模型的基础上，将匈牙利算法和蚁群算法相结合，提出了缩减总任务时间和使最大任务时间最小化的精确算法。许可[4]等人采用分布式拍卖算法解决异构多无人机的任务分配问题，通过实现单个无人机的收益最大化来实现整个无人机系统的收益最大化，而且算法实现了完全分布式。张梦颖[5]等人采用改进合同网算法，通过在算法中引入并发机制一次进行多个任务的拍卖，减少了拍卖次数，提高了算法效率。Heba Kurdi[6]等人基于细菌觅食算法对无人机的任务分配问题进行研究，该算法求解速度较快，运行时间短。Almasri[7]针对求解无人机飞行时间有限制和有功耗约束的问题采用了多目标进化算法，该算法与单目标方法相比有效缩短了计算时间。Martin[8]利用分支定界和遗传算法对多个非线性准则的多级任务分配问题进行了处理求解。

狼群算法因其求解速度快，计算精度高也逐渐得到广泛应用。Radmanseh[9]等人基于狼群算法提出了一种优化策略对无人机轨迹进行优化处理，将贝叶斯模型和距离值函数单元加权概念相结合对求解过程进行优化，并通过仿真实验对方法的可行性进行了验证。Xu[10]等人将狼群算法与烟火算法相结合，利用烟火算法的爆炸规则改善了狼群算法搜索半径固定这一弊端，从而提高了算法的局部寻优效果。赵煜民[11]等人针对狼群算法指向性向目标靠拢的现象，采用聚类算法改进任务分配优先级，改进后算法的任务分配效率得到了有效的改善，并且大大节省了无人机的飞行距离。

1 模型建立

1.1 初始定义

在进行初始参数定义前首先假设各无人机飞行速度相等且全程保持不变，最后都预留有足够能量支持无人机安全返航。为了实现多无人机整体任务分配结果最优，需要在合理规划航迹的条件下将各个任务按照代价最小的原则分配给满足要求的无人机。

建立三维空间环境模型。环境中存在的威胁主要为山体威胁，定义无人机集合为U={Ux，Uy，Uz}，并规定各无人机的载荷信息ZaiHe，Nt表示无人机数量。定义任务集合为R={Rx，Ry，Rz}，任务属性包括执行该任务的价值Value、威胁Risk以及执行该任务所需耗费的无人机载荷信息HaoFei，N表示任务数量。

1.2 无人机航程

无人机飞行总航程即所有航迹节点距离之和。无人机航程由n个节点组成，两节点间的距离用表示，其计算公式如公式（1-1）所示。

其中，表示无人机当前节点位置坐标，表示无人机下一节点位置坐标。

总航程用表示。

1.3 任务空间约束

本文中无人机在三维空间中执行相应任务。假设任务环境空间X轴坐标范围为，Y轴坐标范围为，Z轴坐标范围为，则任务分配问题中环境空间中某一点需满足以下约束条件，如公式（1-3）所示。

1.4 协同任务约束

任务分配问题中任务集合里每个任务只需执行一次即可，因此需要满足以下任务约束，如公式（1-4）所示。

其中，表示无人机数量，表示任务数量，表示无人机是否执行任务，无人机的总数量为，无人机执行的任务总数为。

综上所述，任务分配问题收益函数可表示为公式（1-5）。

其中，为权重系数，且满足，为各项代价或收益，具体计算方式见公式（1-6）～（1-9）。

其中，为对应的惩罚系数。

2 算法原理

2.1 狼群算法

严酷恶劣的自然环境以及生物的进化规律使狼群生成了属于自己的一套具有组织性完整、协作完善的狩猎活动系统。整个狼群分为头狼、探狼、猛狼。对整个狼群的捕猎活动进行研究，主要可抽象为三种行为和两种规则，即游走、召唤和围攻三种行为，头狼产生、狼群更新两种规则。

游走行为

解空间中除头狼外适应度最优的匹狼属于探狼，负责环境中猎物的搜寻，探狼数量是属于的随机数，表示探狼在整体狼群中所占比例。在搜寻过程当探狼所处位置的猎物气味浓度大于头狼时，则该探狼将取代头狼成为新的首领，同时重新发起召唤行为；当前探狼所处位置猎物气味浓度未超过头狼时，探狼将朝着个方向以游走步长继续游走搜索，此时探狼位置更新公式如（2-1）所示。

其中，表示当前第只探狼在维空间上的位置，表示某个方向，表示方向的总个数，就表示某一个方向，表示在维空间中的游走步长。

召唤行为

头狼可发动召唤行为。狼群中由头狼和探狼以外的狼担任猛狼，假设狼群总数为，则猛狼数量。猛狼接收到头狼的召唤后，将以较大步长向头狼奔袭，奔袭过程中猛狼位置由公式（2-2）进行更新。

其中，表示在维空间中猛狼的位置，表示维空间中猛狼的奔袭步长，表示在维空间中迭代次后头狼的位置。

猛狼朝着猎物位置奔袭，当两者间的距离小于距离阈值时，则狼群转入围攻行为。距离阈值计算公式如公式（2-3）所示。

其中，表示空间维数，为距离判断因子，的不同取值将对算法的收敛速度产生不同影响。相同条件下，越大算法就收敛的越快，但随着过大狼群转入围攻行为的难度也会增加。和表示维空间中待寻优变量的最大值和最小值。

围攻行为

围攻阶段，用距离猎物最近的头狼位置表示猎物位置，围攻行为中狼群的位置可由公式（2-4）表示。

其中，为均匀分布在之间的随机数，表示维空间中狼群的围攻步长，表示在维空间中猎物的位置。

在维空间中狼群的三种步长间存在一定关系，如公式（2-5）所示。

其中，表示步长因子，影响狼群对猎物搜索是否全面仔细。

2.2 改进狼群算法

2.2.1 改进游走行为

在基本狼群算法中，根据游走行为探狼的位置更新公式可得，探狼的位置只和当前位置和游走步长相关，这将在一定程度上限制狼群搜索的随机性，易陷入局部最优。为此提出一种自适应游走方式，改进后探狼位置更新如公式（2-6）所示。

其中，为自适应调节系数，取值范围为，为当前迭代次数，为算法最大迭代次数。引入自适应游走步长后，探狼前期将以较大的步长进行游走，提高全局搜索能力，有利于搜索速度的提升；后期探狼进行搜索时步长较小，极大改善了算法的搜索精度，加快了算法的收敛速度。

2.2.2 改进围攻行为

围攻行为中狼群一直以固定补偿进行围攻前进，大大降低了算法的局部寻优能力，可能会导致算法陷入局部最优。而围攻步长过小将会大大增加搜索时间，导致对计算机资源的过分占用。针对此种弊端，对围攻行为进行改进，结合自适应调节因子使围攻步长可以随迭代次数进行改变。改进后的围攻行为位置更新公式可表示为公式（2-7）。

其中，为调节系数，取值范围为，为当前迭代次数，为算法最大迭代次数。

2.3 改进狼群算法的收敛性证明

Markov链是一种无后效性的随机过程，经常被人们用于收敛性问题的分析[12]。狼群算法中的三种行为都只和狼群当前状态相关，和以前的状态没有关系。因此，狼群算法的种群序列很显然是Markov链。而改进狼群算法中狼群行为亦然，显然改进狼群算法的种群系列同样是Markov链。

由Markov链的收敛性以及文献[13]中的证明可得改进狼群算法以概率1收敛于待优化问题的全局最优解。

改进狼群算法流程图如图2-1所示。

3 仿真结果分析

本文通过MATLAB软件进行仿真，对所提出的算法及其改进进行验证。假设无人机起始点位置为，目标点位置为。环境为山地环境，首先验证改进狼群算法在航迹规划中的效果，并与狼群算法[14]和蜂群算法进行对比，然后利用改进狼群融合拍卖算法对多无人机进行任务分配并仿真验证。

人工蜂群算法和改进狼群算法的初始参数如表3-1所示。

利用MATLAB分别对狼群算法、改进狼群算法和人工群算法进行三维环境空间下的无人机航迹规划仿真实验，仿真中将无人机与目标点之间的直线距离信息作为适应度评价的标准指标。在两组不同地形环境下进行仿真，以无人机的飞行总航迹作为评价航迹优劣的标准，进行仿真实验。

根据仿真结果三种算法都可以有效对山峰等地形障碍物进行躲避，最终到达要求目标点。三种算法的适应度曲线图如图3-1所示，其中虚线表示无人机的理论最优适应度，其大小为无人机位置和目标点位置的直线距离，红色为人工蜂群算法的适应度曲线，绿色为狼群算法的适应度曲线，紫色为改进狼群算法的适应度曲线。根据图3-1可得，狼群算法和改进后的狼群算法优化精度和收敛速度十分接近，但都明显优于人工蜂群算法，人工蜂群算法最优航迹总长度为1664.23，狼群算法最优航迹总长度为1628.37，改进狼群算法最优航迹总长度为1629.08，而理论最优值为1623.08；狼群算法和改进狼群算法迭代到15次时的适应度值已明显接近最优值，其收敛速度快于人工蜂群算法。但改进狼群算法首次迭代时最优值明显低于狼群算法首次迭代值，其更接近理论最优值，说明改进后的狼群算法全局寻优能力得到了显著提高。

将改进狼群算法与拍卖算法相结合形成改进狼群融合拍卖算法，进行多无人机的任务分配。以3架无人机执行5项任务进行仿真。有关任务信息，如下表3-2所示。

无人机位置和载荷信息（执行任务的能力）如表3-3所示。

利用拍卖算法对其进行分配，最终分配方案见表3-4。任务分配及执行效果如图3-5所示。

由图3-2可得，无人机根据改进狼群算法规划的航迹，在三维复杂地形环境下可安全到达任务点。该分配方案充分统筹全局资源，使整体系统以最小代价完成任务。

改进狼群融合拍卖算法可以有效进行整体决策，得到科学的分配方案，同时保证无人机航迹的安全性，最终达到安全高效执行任务的目的。

4 结束语

随着环境对的复杂以及任务的多样化，无人机正在从单机执行任务向多机协同的方式进行转变，狼群算法作为一种生物集群算法，通过模拟狼群的组织结构和狩猎方式，能很好地协调种群内个体间的关系，有利于任务的分配与执行。本文对游走步长和奔袭步长进行改进，并与拍卖算法结合形成改进狼群融合拍卖算法，在安全飞行的前提下有效缩短了无人机的飞行航迹，实现了对任务的科学分配。

参考文献

[1]MAHMUD I， CHO Y Z. Detection Avoidance and Priority-Aware Target Tracking for UAV Group Reconnaissance Operations. Journal of intelligent & robotic systems： Theory & applications， 2018， 92： 381-392

[2]MOON S， OH E， SHIM D H. An integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamnic environments. Journal of Intelligent & Robotic Systems， 2013， 70（1）： 303-313

[3]XUE KAI， HUANG ZHIQIN， WANG PING， et al. An Exact Algorithm for Task Allocation of Multiple Unmanned Surface Vehicles with Minimum Task Time. Journal of Marine Science and Engineering， 2021， 9（8）

[4]许可，宫华，秦新立，张博渊.基于分布式拍卖算法的多无人机分组任务分配[J].信息与控制，2018，47（03）：341-346.DOI：10.13976/j.cnki.xk.2018.8013.

[5]张梦颖，王蒙一，王晓东，宋勋.基于改进合同网的无人机群协同实时任务分配问题研究[J].航空兵器，2019，26（04）：38-46.

[6]H. KURDI， M. F. AIDAOOD， S. Al. MEGREN， et al. Adaptive Task Allocation for Multi-UAV Systems Based on Bacteria Foraging Behaviour. Applied Soft Computing， 2019， 83： 105643-105661

[7]ALMASRI， SANAA， JARAH， et al. Multi-objective optimization of task assignment in distributed mobile edge computing. Journal of Reliable Intelligent Environments， 2021

[8]MARTIN J. G. ， FREJO J. R. D. ， GARCIA R. A. ， et al. Multi-robot task allocation problem with multiple nonlinear criteria using branch and bound and genetic algorithms. Intelligent Service Robotics， 2021， 14（5）

[9]M. RADMANESH， M. KUMAR， M. SARIM. Grey Wolf Optimization--based Sense and Avoid Algorithm in a Bayesian Framework for Multiple UAV Path Planning in an Uncertain Environment. Aerospace Science and Technology， 2018， 77： 168-179

[10]CHEN XU， ZHANG YI， LI KUUI， et al. Path Planing of Mobile Robot Based on Improved Wolf Swarm Algorithms， 2019 IEEE 8th Joint Intemnational Information Technology and Artificial Intelligence Conference （ITAIC）， 2019， pp. 359-364

[11]赵煜民，张建磊.基于聚类的无人机狼群任务分配算法[J].人工智能，2021（04）：31-39+47.DOI：10.16453/j.cnki.ISSN2096-5036.2021.04.004.

[12]宋延红，毛永华.强遍历Markov链的扰动估计及收敛速度[J/OL].数学学报（中文版）：1-19[2023-05-12].http：//kns.cnki.net/kcms/detail/11.2038.O1.20220411.0915.010.html

[13]BACK T. Evolutionary algorithms in theory and practice. New York： Oxford Uversity Press， 1996： 21-28

[14]吴虎胜，张凤鸣，吴庐山.一种新的群体智能算法——狼群算法[J].系统工程与电子技术，2013，35（11）：2430-2438.

课题来源：2024年度河北省高等学校科学研究青年基金项目“基于多源数据融合技术的数字城市三维建模技术的研究”，课题编号：QN2024124，依托平台：邢台市无人机应用技术创新中心