融合Q 学习算法和人工势场算法的无人机航迹规划方法

刘 冬，余文泉，霍文健，李 瑞，姜伟月

（北方自动控制技术研究所，太原 030006）

0 引言

作为重要的无人装备，军用无人机已在现代战争中崭露头角。从叙利亚战争到纳卡冲突，军用无人机都表现出色，它们对地面坦克、步战车、自行火炮等装甲高价值目标形成巨大的威胁。战争形态的持续变化不断呼唤新装备新技术，自主执行任务是军用无人机发展的趋势。无人机航迹规划是在综合考虑无人机到达时间、油耗、威胁以及飞行区域等因素的前提下，为无人机规划出最优或满意的飞行航迹［1］。战场环境下无人机需要深入敌区进行侦察和对抗，因此，如何快速准确地规划出一条安全、便捷的路径，成为了无人机自主完成任务的关键。

现有航迹规划算法可分为经典算法和智能算法。其中，应用于航迹规划的经典算法主要有A*算法、人工势场法、快速搜索随机树、Voronoi 图法等；用于航迹规划的智能算法主要包括蚁群算法、粒子群算法、遗传算法等［2-9］。上述方法在一定条件下拥有各自的优势，但在环境信息无法完全获取或模型过于复杂的情况下，表现的效果并不理想［10］。

随着机器学习的迅速发展，人们试图用基于强化学习的算法来解决无人机航迹规划问题。Q 学习算法作为一种经典的强化学习方法，它能够在环境信息未完全获取的情况下，通过学习机制为无人机规划出一条避开所有危险区域的最优路径。现有基于强化学习的航迹规划方法大多基于Q 学习及其改进算法，见文献［11-13］。

基于强化学习的航迹规划算法生成的航迹，是由搜索到的航迹点直线连接而成，若无人机沿规划的航迹飞行时，可能与障碍物发生碰撞［14］。针对该问题，本文提出了一种融合Q 学习算法和人工势场算法的无人机航迹规划方法，可以有效、快速地构建出最短航线，并避免基于Q 学习算法规划的航迹中发生与障碍物碰撞的危险。

1 融合Q 学习算法和人工势场算法的航迹规划方法

1.1 基于Q 学习算法的航迹规划方法

强化学习是机器学习的范式和方法论之一，它把学习看成试探的过程，具体模型如图1 所示。每次试探时，智能体先是感知环境，获得当前在环境中所处状态St；然后依据一定的策略，从动作集中选择一个动作At作用于环境；环境在动作At的作用下，变更到了新的状态St+1，并根据动作给予智能体奖惩Rt+1；智能体通过奖惩判断执行动作的好坏反馈，并且不断地调整动作的选择策略，以期望获得最大的回报。在基于强化学习的航迹规划系统中，无人机可以看作智能体，飞行环境可以看作智能体作用的环境，位置可以看作智能体所处的状态，飞行的方向可以看作智能体能够采取的动作，如果飞到障碍区给予惩罚，或者飞到安全区给予奖励，寻求最佳路径的过程即求取最佳决策的过程。

图1 强化学习基本模型Fig.1 Basic model of reinforcement learning

下面给出基于强化学习的航迹规划方法的实现方法。

1.1.1 环境建模

本文假设无人机在相同高度飞行，并采用栅格法对飞行环境进行建模，具体如图2 所示。

图2 基于栅格法的飞行环境Fig.2 Flight environment based on grid method

在该图中，飞行区域被划分成了多个连续但不重合的网格，其中，黑色网格表示障碍物（山峰、攻击区），白色网格表示可以通行的区域，实心圆圈分别表示起始点和目标点。为了计算无人机的飞行轨迹，需要对栅格地图中网格的位置进行标记。网格的位置有两种表示方法：序列法和坐标法［15］。假设每个网格都有如图2 所示的一个序列化的编号，每个网格的中心点坐标为网格的直角坐标，则网格编号与其直角坐标的对应关系如式（1）所示。

式中：x，y 分别为网格的直角坐标；N 表示每个网格对应的编号；n 表示网格的行（列）数；Mod 表示取余函数，ceil 表示向右取整运算。

1.1.2 动作建模

在栅格地图中，无人机位于某一栅格时有8 种可能前进方向，本文用0，1…7 来表示无人机可能执行的8 种动作，即向正北、东北、正东、东南、正南，西南、正西，西北飞行，具体如图3 所示。

图3 飞行动作Fig.3 Flight movements

1.1.3 奖惩函数

在基于强化学习的规划航迹算法中，智能体每次与环境进行一次交互（即飞行器在栅格中每移动一步）就会获得一次奖惩。学习的目标就是到达终点时，得到的回报最多，因此，构建合理的奖励函数直接关系到航迹规划的好坏。本文设计的奖励函数如表1 所示。

表1 无人机飞行奖惩函数表Table 1 Flight reward and punishment function table of UAV

1.1.4 Q 学习算法

Q 学习算法是最基本的强化学习算法之一，它采用Q 值迭代方式来获取到最优策略。Q 学习算法中的迭代方程如式（2）所示：

式中，Q（st，at）表示在状态s 下采取动作a 能够获得的回报，α∈［0，1］为学习率，用于调节学习过程中的可能误差；γ 为折扣因子，r 为状态下执行动作a得到的即时奖励。

算法1 给出了Q 学习算法的伪码描述，利用该算法可以求得所需的路径。

算法1 Q 学习算法1 Initialize Q（s，a）arbitrarily 2 Repeat（for each episode）:3 Initialize s4 Repeat（for each step of episode）:5 Choose a from s using policy derived 6 from Q（e.g.ξ-greedy）7 Take action a，observe r，s'8 Q（s，a）=Q（s，a）+α［r+ymaxa'（s'，a'）-Q（s，a）］9 s=s'10 until s is terminal

1.2 人工势场算法

人工势场算法是一种对运动物体进行路径规划的常用方法。该算法将假设无人机周围存在一个虚拟的力场，并由引力场和斥力场所构成。其中，目标点会对物体产生引力场，障碍物对物体产生斥力场，无人机在这两种势场力的控制下不断朝目标点前进，最终形成要规划的轨迹。图4 展示了无人机在人工势场环境下的受力模型，其中，Fatt表示引力，Frep示排斥力，Ftotal是引力和斥力的合力。

图4 人工势场环境下的无人机受力模型Fig.4 Force model of UAV under the artificial potential field environment

下面给出传统人工势场法相关函数的定义。

假设无人机当前的位置为X=（x，y），目标的位置为Xg=（x，y），则引力势场函数表示为：

由于引力是引力场产生的负梯度，则引力函数表示为：

式（3）和式（4）中Katt表示引力增益系数，表示无人机从当前位置到目标位置的距离。

障碍物产生的斥力势场函数公式如下：

同理，由斥力场的负梯度可以得到斥力函数：

式中，Krep表示斥力增益系数，ρ 表示障碍物能够对无人机产生影响的最大半径，同时也是无人机和障碍物之间的最小安全距离，表示无人机与障碍物之间的距离。

无人机在运动空间中受到的势场和合力分别为：

1.3 基于融合算法的航迹规划方法

由上节可知，在基于Q 学习算法无人机航迹规划方法中，无人机可以沿正南、正北、正东、正西、东南、东北、西南、西北8 个方向飞行。根据奖惩函数，斜线飞行的价值大于水平飞行，所以系统在为无人机规划航线时会优先选择斜线飞行方向。沿着斜线飞行会缩短飞行距离，但这也会导致如图5 所示与障碍物碰撞的情形。

图5 飞行器沿斜线飞行时的情形Fig.5 The status of UAV flying along oblique line

为了避免该问题的发生，本文提出了融合Q 学习算法和人工势场算法的航迹规划方法。该方法首先采用Q 学习算法获得一条飞行路径，其次针对该路径每段斜线轨迹统计其范围内所包含的障碍物，再次判断每段斜线轨迹是否包含障碍物，如果包含采用改进的人工势场法对该段轨迹进行重新规划，否则仍采用原有轨迹。障碍物的统计方法如图6 所示：以p1和p2的连线为直径画圆，如果障碍物落在圆内则进行记录，否则将将其丢弃。其中，p1是无人飞行器移动的当前位置，p2是通过Q 学习算法产生的当前节点的下一位置，图中的圆是障碍物，r 是半径。

图6 局部路径规划中障碍物、目标点示意图Fig.6 Schematic diagram of obstacles and target points in local route planning

传统人工势场法的局限性在于，当目标点对无人机的吸引力和障碍物对无人机的排斥力合力为零时，无人机永远无法到达目标点。针对该问题，本文通过引入式（9）所示的斥力场函数来解决。

该函数在原有斥力场的基础上增加了目标和物体距离的影响。无人机靠近目标时，虽然斥力场会增加，但是距离却在减少，因此，在一定程度上能够起到对斥力场增大减缓的作用。

相应的斥力变成式（10）

其中，

为了进一步解决该问题，本文还对排斥力在坐标轴上的分量进行改进，具体如式（13）和式（14）所示。当无人机因受力平衡陷入僵局时，通过此法改变排斥力的方向，从而使无人机绕开障碍物继续向目标靠近。

下页算法2 给出了融合算法的伪代码描述，首先通过Q 学习算法得到全局路径点集golobpath（步骤2），接下来对全局路径的每段轨迹进行遍历（步骤3～步骤26）。每次遍历时首先判断该段轨迹p1-p2是否为斜边（步骤5～步骤25）。如果p1-p2是斜边，则需要进一步判段是否需要对斜边p1-p2进行局部航迹规划（步骤6～步骤22），否则直接将该轨迹段的起始点p1加入到最终路径path 中（步骤24）。判段是否需要对该斜边p1-p2进行局部路径规划，主要看该段轨迹内是否存在障碍物，也即判读obj2集合是否为空，如果不为空基于人工势场法求出局部路径localpath（步骤18），将其加入最终路径path（步骤19），如果为空则将该路段的起始点p1加入到最终路径path 中。其中obj2集的构建方法如下：1）求出该段轨迹范围的半径r 和圆心o（步骤6～步骤7）。2）遍历障碍物集obj1（步骤9～步骤15）。每次遍历时判段该次遍历到的障碍物obj1［i］到圆心o 的距离是否小于半径r，如果小于等于r，将其加入obj2中（步骤10～步骤11），否则加入到障碍物点集obj3中（步骤12～步骤13）。

算法2 Q-learning and artificial potential field fusion algorithm Intput:start，goal，map，obstacle Output:path 1 Initialize：obj1=obstacle，J=200 2 golobpath=Q 学习（star，goal，map，obstacle）3 for i=1：len（golobpath）-1 4 p1=golobpath［i］：p2=golobpath［i+1］5 If（‖p2［2］-p1［2］‖=‖p2［1］-p1［1］‖）6 r=1/2‖p1-p2‖7 o［1］=1/2（p2［1］-p1［1］）；o［2］=1/2（p2［2］-p1［2］）8 obj2=［］；obj3=［］9 for j=1:len(obj1)-1 10 if（‖obj1［j］-o‖≤r）then 11 obj2=obj2.append（obj1［j］）12 else 13 obj3=obj3.append（obj1［j］）14 end 15 end 16 obj1=obj3 17 If（len（obj2）>0 18 localpath=artificialpotentialfield（p1，p2，obj2）19 path.append（localpath）20 else21.path.append（p1）22 end23.else 24 path.append（p1）25 end 26 end 27 path.append（goal）

算法2 中主要用到的符号及其含义见表2。

表2 符号意义Table 2 The meaning of symbols

2 实验评价

为了验证融合算法的有效性，本文基于MATLAB2015a、在Intel（R）Core（TM）i5-10210U 主频为1.6 GHz 的计算机上进行仿真实验。选取的地图起始点设为（0.5，0.5），目标点设为（19.5，19.5），每个网格的单位长度为200 m。本文主要进行了两组实验。实验1 基于Q 学习算法，设定折扣因子，学习率，迭代次数为80 次，奖惩函数参数见表2，动作集元素如图3 所示。实验2 基于融合算法，设定引力增益系数，斥力增益系数，最小安全距离0.5*单元格长度，参数n=2。

图7 展示了实验1 的运行结果，可以看出尽管利用该方法得到的路径长度最短，但当无人机沿着该路线飞行时会与障碍物发生碰撞。下页图8 展示了实验2 的运行结果，虽然路径长度有所增加，但当无人机沿着该修正路线进行飞行时，可以避免障碍物发生碰撞。

图7 基于Q 学习算法规划出的路线Fig.7 The planned route based on Q-learning algorithm

图8 基于融合算法规划出的路线Fig.8 The planned rtoute based on fusion algorithm

下页表3 列出了两种算法的性能指标对比。从表3 可以看出，融合算法较Q 学习算法规划出的路径长度增加了3.9%，规划时间增加了19%，但碰撞点却减少了100%。

表3 两种算法性能指标对比Table 3 Performance index comparison of two kinds of algorithms

综合来看，虽然融合算法在路径长度和规划时间上略有牺牲，却避免了与障碍物碰撞的风险，这样的路径也更加适合无人机的飞行。

3 结论

针对基于Q 学习算法规划出的航线存在与障碍物发生碰撞危险的问题，本文提出了一种融合Q学习算法和人工势场算法的航迹规划方法，并与基于Q 学习算法的航迹规划算法进行了实验比较。实验结果显示，融合算法可以在给出最短轨迹航线的情况下，有效避免障碍物发生碰撞。

本文的航迹规划方法仅仅考虑了静态障碍物，而无人机的飞行环境是复杂多变的，往往会出现运动轨迹未知的随机障碍物。若要使用本文方法避开动态运行的障碍物，则需要结合飞机的飞行速度，这将作为本文下一步的研究重点。