基于强化学习的无人机集群动态任务规划算法.pdf

2023 年 8 月第 19 卷 第 3 期系统仿真技术System Simulation TechnologyAug.，2023Vol.19，No.3基于强化学习的无人机集群动态任务规划算法李明哲1，马琼敏2，3*，伍国华1（1.中南大学 交通运输工程学院，湖南 长沙 410075；2.军事科学院 系统工程研究院，北京 100101；3.复杂系统仿真总体重点实验室，北京，100101）摘要：针对无人机集群动态任务规划问题，本研究提出一种基于强化学习的无人机集群动态任务规划方法。该方法将无人机集群动态任务规划划分为任务分配和路径规划2层进行求解，首先通过任务分配得到各个无人机所负责的任务集合，然后在各个任务集合内通过路径规划得到无人机的飞行路径。在任务分配层面，根据大规模无人机集群任务分配存在的规模性和动态性特点，设计基于注意力机制的强化学习算法对其进行求解，该算法在深度强化学习算法的基础上引入注意力机制网络，使得算法能够高效处理无人机数目和任务数动态变化。在路径规划层面，采用基于Gurobi的最优化算法求解最优飞行路径，保证强化学习训练效果与求解结果质量。实验结果表明，在多种规模的动态任务规划中，本研究所提出的算法任务完成度较对比算法提升26.9%59.9%，方案变化量较对比算法减少12.8%19.8%，且求解时间在1 s以内。关键词:无人机集群；动态任务规划；强化学习；注意力机制Dynamic Task Planning Algorithm for UAV Swarm Based on Reinforcement LearningLI Mingzhe1，MA Qiongmin2，3*，WU Guohua1（1.School of Transportation Engineering，Central South University，Changsha 410075，China；2.Institute of Systems Engineering，Military Academy of Sciences，Beijing 100101，China；3.National Key Laboratory for Complex Systems Simulation，Beijing 100101，China）Abstract：Aiming at the problem of UAV swarm dynamic task planning，this paper proposes a method of UAV swarm dynamic task planning based on reinforcement learning.In this method，the UAV swarm dynamic task planning problem is divided into two layers：task assignment and path planning.First，the task set of each UAV is obtained through task assignment，and then the flight path of the UAV is obtained through path planning within each task set.At the task assignment level，according to the scale and dynamic characteristics of task assignment in large-scale UAV swarms，a reinforcement learning algorithm based on attention mechanism is designed to solve it.This algorithm introduces an attention mechanism network on the basis of deep reinforcement learning algorithm，so that the algorithm can efficiently deal with the dynamic changes of the number of drones and the number of tasks.At the level of path planning，the optimization algorithm based on Gurobi is used to solve the optimal flight path to ensure the training effect of reinforcement learning and the quality of solution results.The experimental results show that in solving multi-scale dynamic task planning problems，the task completion degree of the proposed algorithm is improved by 26.9%59.9%，the scheme variation is reduced by 12.8%19.8%，and the solution time is less than 1s.Key words：UAV swarm；dynamic task planning；reinforcement learning；attention mechanism基金项目：自然科学基金项目（62373380）通信作者：马琼敏，E-mail:DOI:10.16812/31-1945.2023.03.014系统仿真技术第 19 卷 第 3 期近年来，随着视觉感知技术、空间定位技术、路径规划算法、智能控制技术等机器人自动化技术不断发展和成熟，各类无人机器设备如工业机器人、无人机、四足机器人得到广泛研究，并应用在物流、交通等各个领域中。其中无人机因其具有操作灵活、智能化程度高以及可以越过地形障碍等特性，被应用在工业制造、交通运输等各个领域1。在物流运输方面，多无人机逐渐被应用在物流配送任务上，不仅降低了时间与人力成本，还能在新冠疫情背景下减少面对面接触、满足防控疫情的需要2。从2010年以来，亚马逊3、DHL4、谷歌等企业就纷纷布局无人机配送，美团也自2016年开始研究无人机在外卖业务中的应用，目前在深圳坪山、龙岗等8个社区、1个商圈为8 000多户居民提供无人机即时配送服务。由于单无人机受到续航时间、负载能力、运动速度等的约束，在某些复杂任务上无人机集群拥有更高的任务执行效率和容错性5，能够有效降低运输成本。目前，无人机集群相关技术得到广泛研究，无人机集群也常被应用于集群配送、集群作战、集群侦察等各种现实任务当中6-7。无人机集群协作性能依赖于高效的无人机集群任务规划算法。目前，无人机集群任务规划算法的研究方向主要分为分层规划和联合规划。分层规划的研究思路是将原问题拆分为任务分配和路径规划。而联合规划的研究思路是直接对原问题进行求解，如通过智能算法，逐步优化任务执行方案，或通过多智能体每次输出无人机下一步行动方式，逐步得到完整的任务执行方案。联合规划的研究思路已有不少研究，如刘希阳5、于盛8都采用多智能体强化学习的方法解决无人机集群任务规划问题；涂铮铮9采用进化算法和强化学习结合的方法解决无人机集群任务规划问题。然而，LONG等10采用进化课程学习解决多智能体强化学习任务规划中的规模性问题，但最多也只能支持24个智能体的协同。下面分别介绍任务分配和路径规划的研究现状。（1）任务分配问题研究现状对于静态场景的任务分配，Luan等12将联盟编队博弈模型应用于无人机任务分配场景，提出了一种基于合作规划的联盟形成算法。田震等13、邓可等14和许可等15主要根据已知的任务信息提前进行分配，实现任务收益最大化。Ghamry等16采用粒子群算法来计算多无人机灭火路径规划，根据相对火点距离来进行任务分配，实现了灭火任务完成总时间的最小化。上述研究主要解决静态任务分配问题，还有众多学 者 在 动 态 任 务 分 配17方 面 进 行 了 大 量 研 究。韩攀18采用合同网的方法完成多无人机协同任务分配与重分配；Zhu等19和竺殊荣20采用自组织神经网络解决多无人机动态任务分配问题。强化学习方法能够动态地与环境交互，并给出实时的、可学习的决策结果。近几年，已经有一些研究将强化学习应用到动态场景的任务分配上。代琪等1、唐峯竹等21和 Sun等22采用深度强化学习（Deep Q-Network，DQN）解决无人机集群动态任务规划问题，采用基础的DQN，让智能体在与动态环境交互中不断优化任务分配策略。Kool等23提出一种基于注意力机制的强化学习方法，并将其用于求解传统的组合优化问题，取得了出色的成果。Hu等11在Kool等23基础上，结合注意力机制、图神经网络与REINFORCE强化学习算法求解静态任务分配问题，其算法采用图神经网络进行特征提取，并使用注意力机制进行特征匹配，最后在实验中优于设置时限的OR-tools运算性能。但Hu等11提出的强化学习算法最多只能支持10架无人机执行任务，并没有考虑动态因素对任务分配的影响，难以应对动态场景下大规模无人机集群任务规划问题。（2）路径规划研究现状针对无人机路径规划的算法研究主要分为精确算法和近似算法。精确算法主要包括动态规划24、分支定界25、Dijkstra 算法26等方法，该类方法能够求得问题的最优解，但其运算代价随规模呈指数级增长，因此适合规模较小的情况。近似算法则主要采用启发式算法求解近似最优解，如模拟退火算法27、遗传算法28等，该类方法在路径规划中经常被用到，其优势在于能够短时间内求得大规模路径规划的近似最优解，但是其不能保证质量，且在小规模问题上性能并不突出。本研究针对无人机集群动态任务规划研究中存在的规模性和动态性问题，将无人机集群动态任务规划划分为任务分配和路径规划进行求解，首先通过任务分配得到各个无人机所负责的任务集合，然后在各任务集合内通过路径规划得到无人机的飞行路径。在任务分配层面，根据大规模无人机集群任务分配存在的规模性和动态性特点，设计基于注意力机制的强化学习算法对其进行求解。在路径规划层面，采用基于Gurobi的最优化算法求解最优飞行路径，保证强化学习训练效果与求解结果的质量。194李明哲，等：基于强化学习的无人机集群动态任务规划算法1 无人机集群动态任务规划问题与模型 1.1问题描述各类无人机集群任务如目标搜索、物资运送、打击突防等，都可以转换为无人机集群任务规划问题，其本质都是给各无人机分配任务并规划任务执行路径。不考虑动态因素的情况下，无人机集群静态任务规划只考虑无人机集群从一个或多个起点出发，在时间约束内遍历各任务点即可，如图1所示。考虑动态因素的情况下，则转变为无人机集群动态任务规划：无人机集群在执行原任务规划方案过程中，会遭遇多种动态扰动因素，如无人机损毁、任务新增等，此时原任务规划方案失效，需要对原任务规划方案进行调整，以保证任务完成率。1.2无人机集群动态任务规划基本要素在无人机集群任务规划场景中，有Nu架无人机和Nv个任务目标，定义t代表时间步，t 0，tmax，假设任务开始于t=0，任务区域范围为Area(x轴坐标xarea0，xmax；y轴坐标yarea 0，ymax)，无人机飞行速度为V，无人机最大航程为Lmax。定义t时刻环境状态St=Uavst，Targetst，无人机信息Uavst主要包括无人机位置Puti Area(i=1，Nu)、无人机剩余航程Lti(Lti Lmax；i=1，Nu)，而任务目标信息Targetst则包含任务目标位置Pvtj Area(j=1，Nv)。定义任务分配模型的输出结果为各无人机所负责的任务集Tasksti(i=1，Nu)，Tasksti即表示时间t时无人机i所负责的所有任务序号组成的集合；路径规划模型的输出结果为各无人机的行动路线Routeti(i=1，Nu)，Routeti即时间t时无人机i所负责的所有任务的序号组成的序列，其顺序为执行任务的顺序。1.3动态任务分配模型动态任务分配模型根据初始状态信息（各无人机位置Pu、各任务目标位置Pv、各无人机最大航程L）进行多次任务规划决策，并考虑发生动态事件对决策的影响：以无人机最大航程为约束条件，以最大化无人机任务总完成量为目标，给出各无人机的任务分配方案Taskst=Tasksti|i=1，Nu及其对应的各无人机的路径规划方案Routet=Routeti|i=1，Nu。定义0-1变量aij 0，1代表第j个任务目标是否被分配给第i个无人机，0-1变量yij 0，1代表第j个任务是否在第i架无人机的任务执行路径当中，即第j个任务是否被第i架无人机执行完成。任务分配完成后，需要对各无人机进行路径规划，在本模型内用Path Plan()函数代表这一功能，Path Plan()函数输入任务分配方案Tasks与无人机最大航程L，输出各无人机规划的满足航程约束的任务执行路径。maxa t=0tmaxj=1Ntvi=1Ntuytij-t=0tmaxj=1Taskstctj（1）yti=PathPlan(Tasksti，min(zti，V)，（2）t=0，tmaxctj=1，j Taskti0，j Taskti，（3）j(Taskt-1i/Solvedt)；t=0，tmaxTasksti=j|atij=1，（4）i=1，Ntu；t=0，tmaxi=0Ntuatij=1，（5）j=1，Ntv；t=0，tmax&Svdtj=0i=0Ntuatij=0，（6）j=1，Ntv；t=0，tmax&Svdtj=1j=0Ntvatij=0，（7）j=1，Ntv；t=0，tmax&Dmgti=1ytij atij，（8）i=1，Ntu；j=1，Ntv；t=0，tmax其中，式（1）表示以任务完成量最大化和方案变化量最小化为目标函数；式（2）表示根据任务分配方案和航程得到各个任务的完成情况，其中航程为单位时间航程与无人机当前剩余航程中的最小值；式（3）定义ctj为方案变化量，其中，Solvedt代表到t时已经完成的任务编号集合；集合运算“A/B”表示集合A去除与集合B的交集部分，即A B。Taskt-1i-Solvedt即代表上一时间段分配给无人机i的任务集中尚未完成的部分；式（4）图1无人机集群动态任务规划Fig.1UAV swarm dynamic mission planning195系统仿真技术第 19 卷 第 3 期表示Tasksti变量是由任务序号j组成的集合，而j为分配给无人机i的任务序号；式（5）表示t时刻尚未完成的目标都有且仅有一个无人机负责执行；式（6）表示t时刻已完成的目标不再被分配；式（7）表示t时刻已损毁的无人机不再被分配任务；式（8）表示任务仅能被分配的无人机执行。1.4路径规划模型给 定 当 前 无 人 机 任 务 集 合Tasks=0，n(0为无人机当前位置)和剩余航程L，且所有无人机均从基地出发并完成各个任务；xij为0-1变量，其值为 1表示无人机从任务点i出发前往j点执行任务；yi同样为0-1变量，其值为1表示无人机执行过任务i；zi为无人机到达任务点i时所剩余的航程大小。本研究针对多无人机任务路径规划问题，考虑无人机在执行任务过程中不能超过其原剩余航程L，在此基础上使得所有无人机执行的任务数量最大，由此得到多无人机任务路径规划数学模型如下所示。maxi=1n-1yi（9）j=0nxij=j=0nxji=yi(i=1，2，n)（10）i=0nj=0ndijxij L（11）xij=0(i=j&i，j=0，1，2，n)（12）zi-zj+L xij L-dij （13）(i j&i，j=0，1，n)zi L-di0 (i=1，2，n)（14）其中，式（9）为目标函数，即最大化任务完成数；式（10）表示每个任务最多只能被执行一次；式（11）表示无人机总航程不能超过其航程限制；式（12）-（14）则表示避免自环和子圈的产生。2 基于强化学习的无人机动态任务规划算法 本研究所提出的基于注意力机制的无人机集群任务动态规划算法主要包含任务分配和路径规划2个部分，其中任务分配主要采用基于注意力机制的神经网络及基于 REINFORCE 的改进强化学习算法进行求解，而路径规划主要采用启发式和最优化方法进行求解。采用任务分配、路径规划2个阶段框架求解无人机集群动态任务规划问题，能够缩减强化学习中的状态空间，降低策略的学习难度，进而使得智能体能够学习到更优的策略。算法基本框架如图2所示。其中，无人机/任务目标特征信息加工即是采用基于多头注意力机制的编码器对位置信息、航程信息进行特征提取，为特征匹配做准备，而特征匹配过程则是对无人机、任务目标的特征信息进行注意力机制运算，以得到各无人机对各任务目标的匹配度，并根据匹配度将任务目标分配给合适的无人机，特征匹配结果即是各个任务被分配到的无人机编号。根据任务分配的结果，可以得到各个无人机及其所负责任务目标组成的无人机任务集合，而路径规划所完成的内容即是在任务集合内为无人机规划路径。本研究采用启发式算法与最优化算法求解路径规划问题，得到总的成本消耗、约束冲突与效能，用于评估任务分配结果，得到强化学习算法所需的奖励值，以此引导强化学习算法不断训练得到更好的任务分配策略。2.1强化学习基本框架强化学习基本框架包括状态空间、动作空间、状态转移过程、奖励函数。对于初始有M个任务目标和N架最大航程为lmax的无人机任务分配问题，其状态空间、动作空间及状态转移方程如下所示。2.1.1 状态空间无人机集群任务分配在t时刻的状态向量主要包含各无人机位置Ptuav=(xtuav，ytuav)、各无人机剩余航程ltuav、各任务目标位置Pttarget=(xttarget，yttarget)3个部分。任务 在 t 时 刻 的 状 态 可 以 表 示 为（xtuav，ytuav，ltuav，xttarget，yttarget）。其中各无人机位置Ptuav及各任务目标位置Pttarget限制在任务区域Area范围内，各无人机剩余航程则限制在 0，lmax 范围内。图 2算法结构Fig.2Structure of algorithm196李明哲，等：基于强化学习的无人机集群动态任务规划算法2.1.2 动作空间无人机集群任务分配在t时刻的动作向量即各任务目标的分配结果a，可以转换为各无人机所负责的任务集Taskt。其中各任务目标的分配结果a由M N的0-1矩阵表示，其中aij表示任务i是否分配给无人机j，其取值范围为 0，1 。而Tasktj则是无人机j所负责的所有任务编号组成的列表，其取值范围为0到M-1的整数。2.1.3 状态转移过程无人机集群任务分配的状态转移过程较为复杂，难以用一个数学方程表达，其过程主要包括分配任务、路径规划、任务执行、动态事件4个部分。其中分配任务即是根据动作向量将任务目标分配到对应的无人机，得到各无人机所负责的任务集Taskti。路径规划则是针对各个无人机及其任务集，规划无人机的任务执行路径Routeti。任务执行则是各无人机按照其规划路径Routeti前进固定步长，任务尚未全部完成时，发生动态事件。动态事件即包括无人机损毁、任务目标新增、任务目标消失等影响无人机集群任务执行的动态因素，在发生动态事件后，会重新将新的环境状态输入至智能体，进行下一阶段的决策与任务执行。2.1.4 奖励函数设置无人机集群任务规划目标包括任务完成率最大化和方案变化量最小化，因此在奖励设置方面主要设置这2个方面，即任务完成奖励和方案变化惩罚，如表1所示。其中任务完成奖励即某一任务在当前阶段被完成，则增加10个奖励值。任务完成量越多，总奖励值也对应越大。而方案变化惩罚，即任务规划方案的变化带来的惩罚，保证任务完成率的前提下，应尽可能减少对原任务规划方案的调整。在上一次决策后已被分配的任务，若在本次动态事件发生后尚未被完成，则此次动态决策应尽可能让这些任务仍然由之前的无人机去执行，若决策将任务的负责无人机更改，则给予1的惩罚。除了与问题的目标函数直接关联之外，本研究所设计的无人机集群任务规划模型不包含其他引导性的奖励。2.2基于注意力机制的任务分配网络设计基于强化学习的任务分配网络主要包含编码器和解码器2个部分，其中编码器负责提取任务目标点及无人机的分布特征，而解码器则负责根据任务目标点和无人机的特征匹配得到所有任务目标点的分配去向。2.2.1 编码器编码器主要负责对2个部分数据进行特征提取，分别是任务目标点信息（坐标Ptarget）和无人机信息（包括坐标Puav和剩余航程luav），如图3所示。编码器对这2个部分数据的处理流程一致，只是具体的网络结构与网络参数不同，因此下面将输入数据（M个任务目标点信息或M个无人机信息）表示为x=x0，x1，xM，介绍其具体计算过程。输入数据x首先会经过一层线性层Linear，将信息维度从dx维映射到dh，得到第一层特征向量h(0)i。通过将低维特征映射到高维，编码器能够从更高维度解析输入数据，得到具有丰富特征的结果。该线性层的参数包括权重Wx和偏置bx，计算过程如（15）式所示。h(0)i=Wxxi+bx（15）然后特征向量h(0)i将经过n层的注意力层计算，得到最终的编码结果。在下面的推导中，将用h(l)i代表经过第l层计算得到的特征向量(l 1，n)。该注意力层主要包含2个子层：多头注意力机制层和全连接前馈神经网络层，且每个子层都加入了残差连接和批标准化。各个子层之间不共享网络参数，处理无人机信息的网络与处理任务目标点信息的网络也不共享网络参数。具体计算过程如下所示。h(l)i=BNl h()l-1i+MHAli(h()l-11h(l-1)n)（16）h(l)i=BNl h(l)i+FFl(h(l)i)（17）其中，BNl代表第l层的批标准化处理，MHAli代表第l层对第i个特征向量的多头注意力机制运算。经过N层注意力层（本研究中采用N=4）计算后，特征向量h(n)i不仅嵌入了个体i自身的信息，还嵌入了其他所有个体信息。对无人机信息而言，每个无人机对应的特征向量h(n)i都嵌入了其他所有无人机的信息，因此进行决策时能够考虑与其他无人机的协同配合；对于任务点信息而言，输入向量xi接近的多个任务点经过注意力机制处理后，得到的特征向量h(n)i也会相互趋近，使得特征类似的任务目标点尽可能被同一无人机执行，提高任务执行效率。经过上述一层线性层、N层注意力层的计算，编码器输出得到各无人机和各任务目标点的特征信息，用于后续的特征匹配。表 1奖励设置Tab.1Setting of reward奖励/惩罚任务完成奖励方案变化惩罚分值+10-1触发条件在当前时间步内任务被完成某一任务目标被重新分配197系统仿真技术第 19 卷 第 3 期2.2.2 解码器解码器部分，则以从编码器得到的特征向量为基础，为每一个待分配任务目标点匹配最合适的无人机。主要计算方法就是对任务目标点特征向量（表示为ftargets）和无人机特征向量（表示为fuavs）做注意力匹配度运算，得到各任务目标点与各无人机的匹配度Cmp，最后根据匹配度按概率pi选择每个任务目标的分配去向，如图4所示。具体计算过程如下所示。u=fTuavs ftargetsduav（18）Cmp=C tanh(u)（19）pi=ecmpiiecmpi(i=1，2，n)（20）其中，duav为无人机特征向量fuavs的维度。经过以上特征匹配网络的计算，并按照分配概率分配好各个任务目标，即可得到分配方案，即各个任务目标的分配去向，由此可以得到各个无人机所负责的任务目标集合Tasks，并用于之后的路径规划和解的评估。基于以上网络结构能够完成对当前情况下无人机/任务目标的特征加工与特征匹配，将任务目标分配给合适的无人机。但是仅仅将位置等静态信息输入模型，还无法学习到使方案变化量尽量小的策略，因为智能体无法获知原任务分配方案。为了进一步降低动态决策过程中的方案变化量，在每次决策之后，智能体会保存本次决策结果，在下一次决策时，将上一次决策结果编码到已分配未完成的任务目标特征向量中，使智能体获知上一次决策中各任务目标的分配情况，进而让智能体尽可能保持原本的分配情况不变，以降低方案变化量。具体编码方式如图5所示，采用无人机特征编码，即将负责任务j的无人机特征Uavi加入到任务j的特征Targetj中，在进行特征加工及匹配时，该任务点也有更大概率匹配给上次分配的无人机，以此减少受动态干扰因素影响而改变决策结果的情况，即减少方案变化量。2.3基于滚动基线的REINFORCE算法根据基础 REINFORCE 算法，在给定实例s情况下，上述网络模型可以表示一个行动策略|s，为了使训练模型行动策略不断优化，定义损失函数L(|s)=Ep(|s)L()，即成本函数L()的期望值，并应用REINFORCE 算法（Williams，1992）对其做梯度下降，以优化行动策略。梯度公式如（21）式所示，其中b(s)为baseline。L(|s)=Ep(|s)(L()-b(s)logp(|s)（21）一个好的baseline能够有效地降低梯度的方差，进而加速网络的收敛。一个简单的baseline设计方法是采用指数平滑的平均结果b(s)=M，其中M在初始情况下等于成本函数L()，并随迭代次数不断更新：M M+(1-)L()。一个常见的baseline设计方法是采用一个学习得到的价值函数（Critic）v(s，)，其中参数经过观察数据 s，L()训练得到。然而，并不是所有情况都适合应用这样的Actor-Critic算法，特别在复杂的场景下，要构建并训练出一个高效的Critic模型相当困难。因此，本研究采用滚动基线的方式来达到近似自监督训练的效果：b(s)为一个固定网络输出结果的成本。该固定网络与策略网络的结构一致，其参数周期性地（一个回合）与策略网络同步，且仅在行动策略|s的结果比固定网络更好的情况下更新参数。为了使基线更加稳定，在固定网络计算结果时，采用贪婪的方式生成结果，而非按概率采样。最后的优化算法采用高效的Adam算法。具体算法流程如算法1所示。图 5动态编码过程Fig.5Dynamic encoding process图 3编码器结构Fig.3Structure of encoder图 4解码器结构图Fig.4Structure of decoder198李明哲，等：基于强化学习的无人机集群动态任务规划算法2.4基于启发式与最优化方法的路径规划算法经过上述网络得到各任务目标的分配结果后，还需对每个无人机任务集合做路径规划，使得路程尽量短，以便在时限内完成尽量多的任务。该场景的路径规 划 与 经 典 的 旅 行 商 问 题（traveling salesman prublem，TSP）模型类似，唯一的区别在于TSP模型考虑整个环路的总距离，而该场景的路径规划不考虑回程距离。因此在TSP模型基础上，需令各点到起点（无人机坐标）的距离为0。本研究主要基于最优化算法与启发式算法对该场景的路径规划进行求解。2.4.1 基于Gurobi的最优化路径规划算法最优化算法求解路径规划问题，通常采用先建模再调用求解器求解模型的方式。下面首先根据前文所述问题模型，以无人机最大航程为约束，以任务完成量最大化为目标，确定路径规划数学模型。所有无人机均从基地出发并完成各个任务；xij为0-1变量，其值为1表示无人机从任务点i出发前往j点执行任务；yi同样为0-1变量，其值为1表示无人机执行过任务i；zi为无人机到达任务点i时所剩余的航程大小。本研究针对多无人机任务路径规划问题，考虑无人机在执行任务过程中不能超过其最大航程L，在此基础上使得所有无人机执行的任务数量最大。基于以上描述与前文所述路径规划模型，采用Gurobi求解器来求解该模型，即可得到该问题的最优解，即航程约束内完成任务数最多的路径。2.4.2 基于贪婪策略的启发式路径规划算法贪婪算法的主要思想是，每次选择都选成本最小、效能最高的那个点。在该路径规划问题中，就是从起点出发，每次选择下个去往的点时，都选择离当前最近的点，以此构成一条遍历的路径。其具体计算流程如算法2所示。算法 2：基于贪婪策略的路径规划算法1.输入：无人机坐标start，各任务目标点集合P，任务目标点个数n2.初始化当前点p0 start3.循环4.初始化最小距离dmin5.循环：(针对未分配点p P)6.计算与当前点的距离d=distance(p0,p)7.如果d dmin，更新最优点pmin=p8.更新当前点p0=pmin9.添加pmin到路径Route10.直到路径Route包含所有任务目标点11.输出：任务执行路径Route3 仿真实验 3.1无人机路径规划实验无人机路径规划问题即给定一个无人机位置、其所负责的任务目标点位置及其最大航程，求解无人机能够执行最多任务的路径。针对这一问题，设置3种规模的实验：5个任务目标点，10个任务目标点，30个任务目标点，并根据不同规模设定对应的无人机航程约束。具体规模设置如表2所示。在上述实验设置之下，随机生成地图并分别对基于启发式方法（贪婪策略）和最优化方法的路径规划算法（Gurobi）进行实验测试，实验进行100次，每一次都更新无人机和任务目标位置，取平均的任务完成度和运算时间，得到如表3所示的实验结果。算法 1：基于滚动基线的REINFORCE算法1.随机初始化策略、基线BL2.循环：（对于每个回合）3.循环：（对于回合内每个时间步）4.获取环境状态st5.根据策略选择动作at（st）6.环境反馈奖励值R（st，at）7.环境状态更新stst+18.直到终止状态9.计算策略总奖励R（）=t=0tmaxR()st，at10.每过N个回合：11.采样基线总奖励b（）=t=0tmaxR()st，at12.计算梯度：J()1N Nt=0tmaxlog()at，st()R()b()13.更新网络参数：Adam（，J（）表 2路径规划实验设置Tab.2Experiment setting of path planning类别规模1规模2规模3任务目标点数51030无人机航程约束100120170表 3路径规划实验结果Tab.3Experiment result of path planning类别规模1规模2规模3算法贪婪策略Gurobi贪婪策略Gurobi贪婪策略Gurobi任务完成度4.8/54.91/58.8/109.35/1017.84/2019.16/20运算时间/s0.000 220.001 000.000 740.079 320.002 471.027 49199系统仿真技术第 19 卷 第 3 期从实验数据可知，Gurobi最优化算法由于其能够计算得到问题的最优解，在各个规模的无人机路径规划问题上都取得更优的结果。任务完成度方面，基于最优化方法的路径规划算法计算结果比基于贪婪策略的路径规划算法计算结果高2.3%7.4%。但是随着规模的增长，最优化算法运算时间长的劣势逐渐显露，在规模3（30个任务目标点）的场景下，运算时间的差异已经超过1s。3.2静态任务规划实验静态任务规划实验中，不考虑无人机中途损毁及新增任务目标的动态情况，设置3种规模的实验：5架无人机-20个任务目标点，10架无人机-40个任务目标点，30架无人机-100个任务目标点，并根据不同规模实际情况设定对应的无人机航程约束和模型学习率。具体规模设置如表4所示。根据以上实验设置，开展多算法的对比实验。采用各个算法进行100次测试实验，强化学习方法的学习时间按照从开始学习到收敛为止计算，并取100次测试实验的平均值作为该算法的实验结果。其中对比算法或策略有基于注意力机制的强化学习、基于前馈神经网络的强化学习以及最近邻规则策略和纯随机策略。对比实验结果如表5所示。从实验结果可以看出，在任务完成度方面，本研究所运用的基于注意力机制的强化学习算法在各个规模的测试实验当中取得最好的结果；而在收敛时间方面，本研究所提出的基于注意力机制的强化学习算法由于其网络规模与任务规模无关，训练时间随任务规模变化幅度不大，而基于前馈神经网络的强化学习方法收敛时间更早且结果较差，说明其能够学习的能力有限；在决策时间方面，本研究所提出的基于注意力机制的强化学习算法在保证决策质量的同时，决策时间与其他方法基本一致，能够满足实时决策要求。其中算法中分别对应本研究提出的基于注意力机制 的 REINFORCE 算 法、基 于 前 馈 神 经 网 络 的REINFORCE算法和随机分配策略。在规模1和规模2的结果中可以看出，本研究提出的算法基本能够找到最优解和任务的最大完成量，而最近邻策略方法虽然分配结果也比较合理，各任务都分配给了最近的无人机，但是由于缺乏多无人机的协同任务规划，其结果与最优解仍相差甚远，而随机策略效果更差，其表现效果主要体现在特定规模问题的求解难度上，由此可见，由规模1到规模3，问题求解难度呈指数级上升，但本研究算法仍能够继续保持求解性能与求解时间。3.3动态任务规划实验动态任务规划实验下，考虑无人机中途概率出现损毁情况和出现新任务目标情况。设置3种规模的实验：5架无人机-20个任务目标点（增至40个任务目标点），10 架无人机-40 个任务目标点（增至 60 个任务目标点），30架无人机-100个任务目标点（增至150个任务目标点），并根据不同规模实际情况设定对应的无人机航程约束和模型学习率。具体规模设置如表6所示。根据以上实验设置，同样采用各个对比算法进行100次测试实验，强化学习方法的学习时间按照从开始学习到收敛为止计算，并取100次测试实验的平均值作为该算法的实验结果。其中对比算法或策略有基于注意力机制的强化学习、基于前馈神经网络的强化学习、纯随机策略，最近邻策略由于无法考虑动态情况不参与对比试验。对比实验结果如表 7所示。从上述实验结果可以看出，本研究提出的算法对于动态场景的问题求解同样能够保持很高的求解性能与求解速度，在各个规模的问题求解中都获得最好的结果，求解时间也都满足实时要求。在动态场景下，优化目标不表 6动态任务规划实验设置Tab.6Dynamic task planning experiment setup类别规模1规模2规模3无人机数/架51030初始目标点数/个2040100最终目标点数/个4060150航程约束1005020学习率/%110-5510-6110-6表 4静态任务规划实验设置Tab.4Experiment setting of static mission planning类别规模1规模2规模3无人机架数51030任务目标点数2040100无人机航程约束1005020学习率/%110-5510-6110-6表 5静态任务规划实验结果Tab.5Experimental results of static task planning类别规模1规模2规模3算法REINFORCE with AMREINFORCE with FFRandom StrategyREINFORCE with AMREINFORCE with FFRandom StrategyREINFORCE with AMREINFORCE with FFRandom Strategy任务完成度19.97/2015.74/2013.11/2036.77/4023.00/4013.20/4063.82/10037.00/1009.27/100决策时间/s0.0710.0580.0490.0770.0690.0490.0920.1250.055学习时间/s14445-239160-18241406-200李明哲，等：基于强化学习的无人机集群动态任务规划算法只是任务完成量，还有动态情况下的方案变化量指标。在这一指标的对比中，