摘 要: 针对未知复杂环境下的多无人机路径规划问题，提出了一种基于优先经验回放的并行深度确定性策略梯度（PER-PDDPG）算法。首先，该算法在传统深度强化学习算法和匈牙利算法的基础上，结合了优先经验回放机制与多智能体经验共享的特点，提高了经验的获取效率，并使高价值经验能够被更加充分的多次利用。其次，算法将针对单无人机的PER-DDPG 算法并行拓展到多无人机中，使得算法的网络结构相对于传统多智能体强化学习算法更加简洁高效。仿真结果表明，该方法可以灵活应用于不同数量的无人机群中，并且相较于传统的多智能体强化学习算法拥有更快的收敛速度以及更高的收敛奖励均值，有效提升了在未知复杂环境下的多无人机路径规划效果。
1 引 言
由于现代战争的作战环境日益复杂，无人机作为一种新兴飞行器，研究其相关技术对掌握作战主动权、提高作战性能有着明显的作用。其中，路径规划技术是无人机领域重要的研究方向之一。
路径规划本质上是一个最优路径搜索问题，需要找到一条从起点出发的、连续无碰撞的、能够到达终点的路线。传统路径规划算法如A*算法[1]、Dijkstra 算法[2]、协同粒子群算法[3]、遗传算法[4]等更适合解决静态路径规划问题。针对动态环境，传统控制方法与模糊控制方法需要涉及很多专家知识，而基于神经网络的方法则需要外界提供大量样本经验。作为机器学习方法之一的强化学习能够弥补上述算法的不足，其几乎不需要专家知识，且不需要外界提供的大量样本。同时，在动态环境下，也具有优秀的自适应性能与学习能力。
La 等[5]提出协作Q-learning 算法，将经典一致性控制算法、人工势场法与Q-learning 结合，使得机器人在连续空间中能够躲避静态障碍与捕食者，但文中强化学习网络的输入是一致性控制算法的相关状态，而不是从环境中得到的真实状态。香港中文大学的潘佳教授团队[6]提出了一种基于传感器的避碰策略，将原始传感器测量值直接映射到智能体的运动指令上。智能体可以根据环境信息对场景进行建模、分类，从而采取不同的运动策略，但文中未考虑对动态障碍物的避碰。王延祥等[7]将流体扰动算法与深度神经网络相结合，解决了现有的无人机路径规划方法难以兼顾路径质量和计算效率的问题，但此算法仅聚焦于单智能体，没有考虑环境中有多个智能体存在的情况。Ryan 等提出了MADDPG 算法[8]，为多无人机的航迹规划问题提供了新的方向[9]。2019 年，Qie 等[10]通过采用MADDPG 算法实现了多无人机在二维平面的目标分配与路径规划，但此时MADDPG 算法训练所需时间较长。上述文献均利用强化学习算法对单智能体和多智能体路径规划问题进行研究，但并未对复杂环境中的路径规划考虑周全。
通过上述分析，本文将基于深度强化学习，使用优先经验回放机制改进DDPG 网络并设计单无人机基于优先经验回放的DDPG 算法（Deep Deterministic Policy Gradient based Prioritized Experience Replay，PER-DDPG），随后引入经验共享机制将PER-DDPG 并行拓展到多无人机中，设计基于优先经验回放的并行 DDPG 算法（Parallel Deep Deterministic Policy Gradient based on Prioritized Experience Replay，PERPDDPG），让所有无人机使用共享的经验池和网络进行学习，实现多无人机在未知复杂环境中的路径规划。
2 问题描述与分析
2.1 未知复杂环境下的多无人机路径规划问题
本文描述的未知复杂环境是封闭的有边界的空域范围。在这个环境中，有静态障碍，如山丘、建筑等；也有动态障碍，如鸟禽等。无人机在未知复杂环境中的路径规划任务场景如图1 所示。
图1 多无人机路径规划场景
Fig. 1 Scenario of multiple UAVs path planning
由于战场环境的多样性和不可预测性，无人机执行实际任务时无法获取所有环境信息，因此无人机在运动时除目标点信息已知外，只能通过机载雷达检测到其他物体相对于本机的位置信息，并不知道环境中其他物体的运动意图和决策策略，其观测获得的信息仅是全局信息的一部分。
2.2 无人机运动学模型
由于多无人机任务决策问题本身就具有高维度、高复杂性的特点，为简化研究问题，本文假设多无人机为同构机型，具有相同的物理特性，并且在研究过程中不考虑无人机的形状大小等物理特性，将无人机简化为质点运动。无人机二维运动学模型如图2 所示，无人机位置为（ x ,y ），速度为v，航向角为ψ，雷达探测距离为R，雷达探测范围为60°。
图2 无人机二维运动学模型
Fig. 2 2D Kinematics model of UAV
无人机质点在二维空间的简化运动模型定义为
模型简化后，控制向量简化为加速度a、角速度ω 两个动作向量。无人机的运动控制变量约束为
式中， amax 是无人机的最大加速度， vmax是无人机的最大速度， ωmax 是无人机的最大角速度，其计算方程为
式中， TΔ 为仿真的时间步长，r 为转弯半径，rmin为最小转弯半径， ψΔ 为 TΔ 时间内的航向角最大转弯角， nmax 为无人机的最大侧向过载，g 为重力加速度。因此，最大角速度为
无人机初始状态为
2.3 匈牙利算法
经典匈牙利算法是Kuhn 利用匈牙利数学家Koning 针对矩阵中独立零元素定理提出的用于解决指派问题的优化方法。本文使用该方法从初始的多个目标中为每个无人机分配其对应的目标点。
该方法的理论基础是：在代价矩阵的任意行或列加上或者减去一个常数不会改变最优分配方案。其基本思想是通过每行或每列加减同一个常数来修改代价矩阵，直到代价矩阵不同行不同列至少有一个零元素。此时，零元素就对应了一个总效益最小的最优分配方案。
经典匈牙利算法的基本步骤如下：
步骤 1：建立资源分配问题的代价矩阵M 0(m ×n)；
步骤2：从效益矩阵M 0每行中减去该行最小的元素，使得每行都有一个零元素，得到 M1 ；
步骤3：从M 1每列中减去该列最小的元素，使得每列都有一个零元素，得到M 2；
步骤4：用最少的直线覆盖M 2（仅包含横线和竖线，不包含斜线）中的零元素得到M 3，如果最少直线的数量等于m，转入步骤6，否则转入步骤5；
步骤5：矩阵M 3中所有末被直线覆盖的元素减去末被覆盖元素中最小的元素，同时在直线相交点加上该最小元素得到M 4，令 M 2= M 4，转步骤4；
步骤6：从零元素最少的行或列开始指派，直到所有任务都指派完毕，得到最优指派方案P。
上述步骤是按照假定m = n 进行的，即认为效益矩阵M 0是一个方阵。但在实际问题中，任务数与人数不一定完全相等。针对任务数与人数不相等的情况，一般的处理方式是增加虚拟人或虚拟任务，即对效益矩阵进行加零补边处理，然后再按照上述步骤进行任务指派。
在本文中，目标点的数量等于无人机的数量，即m=n。在路径规划前，会使用经典匈牙利算法先根据无人机在目标点执行任务的代价矩阵，对多个目标点预先分配给不同的无人机。
2.4 单无人机PER-DDPG 算法
Lillicrap 等[11]在Actor-Critic 框架上，引入DQN 的经验回放机制，对确定策略性梯度算法（Deterministic Policy Gradient，DPG）进行改进，提出了深度确定性策略梯度算法（Deep Deterministic Policy Gradient，DDPG）。由于无人机控制量为连续值，因此选择动作空间为连续的DDPG 算法，设计单无人机路径规划算法。
对于本文任务场景而言，由于动作空间、状态空间的连续性，任务场景构成的样本数量非常巨大，但是训练初期无人机成功避开障碍到达目标点的数据很少，更多的是无人机与障碍物发生碰撞或毫无头绪徘徊的数据。如果只使用随机抽样来选择参加训练的数据样本，会使无人机倾向于更多地学习如何避障，而关于飞往目标点的学习则相对较慢。为了更加有效地利用数据样本，本文引入优先经验回放机制对DDPG 算法进行改进，设计单无人机基于优先经验回放的DDPG 算法（Deep Deterministic Policy Gradient based on Prioritized Experience Replay，PER-DDPG）。
基于优先级的经验抽取方法最早由 Schaul等[12]提出，该方法提出的Prioritized Experience Replay 思想解决了如何从经验池抽取高质量经验的问题。强化学习中，TD-error 表示当前的Q 值与目标Q 值的差距值。因此，可以将TD-error 定义为一个可以衡量样本是否重要的指标。D-error，即 tδ 的具体计算为
式中，如果 tδ 较大，则说明这个样本预测的准确性有待提高，需要提高这个样本的优先级，从而有更多的机会去学习它；如果 tδ 较小，则说明这个样本的优先级会被降低。
设定经验样本的采样概率为
式中， jP 是以TD-error 为标准的优先级指标，α为优先度调节参数，确保每一个经验都有机会被选择、被至少放入网络中参与一次训练。当α=1时，说明网络使用原始TD-error 计算优先级；当α= 0时，使用随机采样的方式对样本进行抽样，此时每个样本的优先级变为
式中，rank ( j )为第j 个样本在全体样本中所在位次，按照每个样本的
由大到小排序。
智能体倾向于更新高TD-error 的经验样本改变了原本的概率分布，模型引入了误差，可能导致神经网络训练时无法收敛。因此在计算权重变化时使用重要性采样来修正误差
式中，M 为经验回放池数量，参数β 为修正误差的程度。将与环境交互的数据根据上述排序就能区分经验样本的重要程度，大幅提高经验样本的学习效率。
