程传斌 倪艾辰 房翔宇 张亮
DOI：10.19850/j.cnki.2096-4706.2021.09.001
摘 要：Q-Learning算法是一种基于价值函数的强化学习方法。传统的Q-Learning算法迭代效率低且容易陷入局部收敛，针对该劣势改进了算法，引入A*算法和动态搜索因子ε。将改进后的动态A*-Q-Learning算法应用于三维复杂环境下无人机的航迹规划，分析无人机航迹规划结果的回报函数、探索步数和运行效率。结果表明，改进后的算法可使无人机在复杂环境下具有很强的自适应性;同时，动态搜索因子ε能有效地避免智能体在搜寻过程中陷入局部最优的状况，在复杂地形中能寻找到更优的路径。
关键词：无人机;航迹规划;A*改进;动态搜索因子ε;动态A*-Q-Learning
中图分类号：TP181;V279 文献标识码：A 文章编号：2096-4706（2021）09-0001-06
Improved Dynamic A*-Q-Learning Algorithm and Its Application in UAV Route Planning
CHENG Chuanbin1，NI Aichen2，FANG Xiangyu1，ZHANG Liang1
（1.School of Science，Wuhan University of Technology，Wuhan 430070，China;
2.School of Economics，Wuhan University of Technology，Wuhan 430070，China）
Abstract：The Q-Learning algorithm is a reinforcement learning method based on value functions. The traditional Q-Learning algorithm lacks efficiency in iteration and is easy to fall into local convergence. To solve the disadvantage，the algorithm is improved：introducing A* algorithm and dynamic search factor ε. The improved dynamic A*-Q-Learning algorithm is applied to the route planning of UAV in 3D complex environment，and the return function，exploration steps and operation efficiency of UAV route planning results are analyzed. The results demonstrate that the improved algorithm can enable UAV to have strong adaptability in the face of complex environment;meanwhile，dynamic search factors ε can effectively avoid the agent falling into the local optimal condition in the search process，and find a better path in complex terrain.
Keywords：UAV;route planning;A* improvement;dynamic search factor ε;dynamic A*-Q-Learning
0 引 言
强化学习是机器学习的范式和方法论之一，用于描述和解决智能体（Agent）在与环境的交互过程中通过学习策略以达成回报最大化或实现特定目标的问题[1]。它具有良好的适应性，能够在未知环境中不断试错从而寻找最优策略[2]。
目前，强化学习可广泛应用于机器人二维平面的路径规划过程中[3]，采用的算法多为Q-Learning算法[4]。传统的Q-Learning算法由于受大规模动作值过估计而出现不稳定和效果不佳等情况[5]。因此，许多学者对Q-Learning算法进行了改进。Wen等[6]基于模糊规则初始化Q值，加快了算法的收敛速度;朱志斌等人[7]利用系统数据迭代求解出可使给定目标函数最小化的控制律，实现了多智能体系统的一致性;蒋国飞[8]等将BP神经网络和Q-Learning有效结合，解决了确定和随机倒立摆模型的平衡控制。
近年来，随着信息技术的快速发展，无人机的应用由广阔空旷地域中的常规应用逐渐转变为复杂地理环境中的军事应用，这对无人机的机动性和远程通信水平提出了更高的要求[9]。在复杂环境下合理规划路线，能够提高无人机执行任务的效率和安全性，为无人机的安全航行保驾护航[10]。
无人机的航迹规划可以根据无人机的任务分配情况进行界定[11]，实验是在不考虑无人机任务分配及任务关系的条件下进行的。目前大量航迹规划的研究中，主要的方法可以分为基于图论的方法、智能优化算法、基于势场的方法、随机规划算法以及启发性搜索算法[12-16]。其中，启发性搜索算法包含A*算法[17]和D*Lite算法[18]等。此外，已经有部分研究着眼于Q-Learning在三维航迹中的应用。郝钏钏等[19]通过设置三维环境中的航迹约束条件，合理引导和规划空间的离散化过程;封硕等[20]将深度学习嵌套入Q-Learning框架，对三维救灾环境中的机器人路径进行规划。无人机的航迹规划受限于传统算法，没有表现出优秀的自我探索能力，期望通过强化学习赋予无人机自主学习能力，使其能够灵活应对更加复杂的环境。
本文在引入马尔科夫决策过程[21]五个重要组成部分（环境与动力、策略、回报函数、价值函数、Bellman期望方程）的基础上，结合A*算法改进传统的Q-Learning算法[22]，同时引入动态搜索因子ε。基于实验数据，分别对Q-Learning算法和动态A*-Q-Learning算法的回报函数、探索步数和运行效率这三方面的数据进行了分析：改进的动态A*-Q-Learning算法总回报值高，探索步数较少，运行效率高。这表明在无人机飞行过程中，改进后的算法能够以更小的代价求得更优的解。此外，动态A*-Q-Learning算法还赋予了无人机较强的自适应性，在风力变化不定的情况下，无人机依旧可以迅速采取相应策略实现航迹的适当调整。
1 Q-Learning算法分析及改进
1.1 基本原理
强化学习模型由智能体和环境组成，其主要内容是智能体通过与环境交互，对当前状态下不同动作策略的价值函数进行估计，执行高回报动作，避免执行低回报或惩罚的动作，从而达到不断改进策略，逼近最优决策的效果。强化学习模型的机理图如图1所示。
无人机通过Agent与环境交互，获得航迹过程的本质是马尔可夫决策过程（Markov decision process，MDP），无人机的下一个空间状态只与当前的状态信息有关，与之前的信息状态无关，即无人机航迹规划的过程具有马尔可夫性。
MDP由五个元素构成：
1.2 基于A*的策略舒适化改进
A*算法是无人机航迹规划中较为成熟的解决方法。该算法不仅具有最佳优先搜索、高效率搜索的特点，同时具有结合Dijkstra算法能够找寻最佳路径的优势。具体流程为：
Agent探索的过程是不断寻找最优策略的过程，其运行效率会随着探索过程的减少而提高。结合A*算法，利用算法得到的路径结果对Q-Learning的价值函数Q（s，a）进行初始化，不仅能有效缩短算法迭代时间，同时还能令航迹规划的结果比A*算法更精确。
具体是实现步骤为：
Step 1：调用A*算法得到一条起点至终点的最短路径;
Step 2：记录路径中上一个状态s迁移至下一个状态s所采用的动作a;
Step 3：令Q（s，a）=C，C>0。对于状态s的其余动作a，令Q（s，a）=0，完成对价值函数的初始化。
1.3 动态搜索因子ε的改进
在强化学习算法中，需要设计出合理的策略依次为繁多的状态确定最优的动作选择。在Q-Learning算法中，采用ε-贪心策略来平衡对环境的探索和利用。其基本思想是确定一个探索因子ε，在确定动作时，Agent通过ε的概率选择当前回报最高的动作，或者以1-ε的概率随机选择一个动作策略。在Q-Learning中，ε通常取一个定值，这样可能会导致Agent在迭代计算的初期，对环境的探索程度不够，寻找不到最优路径，而在迭代的后期又迟迟没办法收敛。
为解决上述问题，引入动态搜索因子ε，根据迭代计算的进度动态调整ε的大小。设ε=f（x），f（x）表示ε与迭代次数x之间的函数关系。具体函数表达式为：
式中，x为当前迭代次数，N为最大迭代次数。
当Agent处于第x代，由f（x）得到ε的值，通过比较rand（）与ε的大小关系，进一步确定是进行贪心选择还是进行随机选择。
动态搜索因子ε的引入能够有效解决以A*算法结果初始化价值函数Q（s，a）后容易陷入局部最优的问题，同时加速迭代后期算法的收敛速度。下面给出基于上述改进的伪代码：
Algorithm 1
Input： Starting point coordinates， End point coordinates
Output： UAV track
Call the algorithm A*
find the static environment route
Initialize the Q-table，
Repeat （for each episode）
Initialize s， a for all s∈S， a∈A
Repeat （for each step of episode）
Calculate ε
2 无人机三维航迹规划建模
2.1 仿真环境设置
2.1.1 风力对航迹的影响
考虑到实际环境中无人机的航迹会受到天气的影响，导致规划航迹与实际航迹存在偏差，因此设置有风区域模拟无人机受天气影响的场景。设置该区域为任意立体空间，进入该空间内的无人机可能会受到风力的影响并沿风力方向强制移动至下一离散空间点上。风力的影响将持续到无人机离开该区域为止。同时考虑到风力可能会出现不连续吹风的情况，即无人机处于有风区域时并不会持续受到风力对航迹的影响，设置风力对无人机造成航迹偏移影响的概率为p=0.9。
2.1.2 山体环境设置
在现代军事领域中，无人机需能够在复杂的地形环境中执行任务，其中以山脉丘陵地区为主。因此，规划其航迹以避免与山体发生碰撞是必然要求。通过构造三维函数来刻画山体的轮廓，描述仿真环境中的山体信息。山体的轮廓函数设置为：
式中，z表示山体表面上某点的垂直高度，（x，y）表示该点在xOy平面上的投影坐标，（ai，bi）表示山体中心在xOy平面上的投影坐标，ki表示地形坡度参数。参数取不同数值时会得到不同的山峰。实验山体相关参数设置如表1所示。
无人机在实际航行过程中应避免与山体发生碰撞，即无人机应与障碍物保持一定的安全距离。同时山体表面丰富的植被让环境信息变得更为复杂，为简化山体表面植被的环境信息，对山体进行“膨胀”处理，使得仿真环境中的山体体积扩大为实际山体体积的（1+β）倍，在满足完全躲避山体要求的同时与山体保持安全距离。实验仿真环境如图2所示。
仿真环境空间大小设置为7×7×4，以0.25为间隔对仿真环境进行离散化处理。在Agent与环境交互的过程中以Δt的间隔更新环境信息，以适应环境变化。
2.2 空间状态设置
在仿真实验中，为了能够将改进后的算法应用于三维无人机航迹规划，首先将无人机放置于一个三维空间当中;接着，分别对无人机的空间状态和动作策略机制进行设置，定义无人机的空间状态为无人机在空间中的坐标位置，例如，无人机在（x0，y0，z0）时，经过动作决策移动到（x1，y1，z1），即无人机从空间状态（x0，y0，z0）转移到空间状态（x1，y1，z1）。
2.3 动作策略设置
式中，D为当前点到终点的欧氏距离，a=5，b=-100，c=-1。
执行回报指无人机每执行一次动作决策所得到的奖励;目标回报指无人机到达终点时所获得的奖励;山体回报指无人机撞击山体的损失;越界回报指无人机离开构建的仿真环境所受到的损失。
执行回报设置的作用是在能够完成无人机躲避障碍到达目的地的同时，使得航迹最短。对每一步施加惩罚，使Agent能够得到步数尽可能少的路径。
3 实验结果及分析
3.1 实验参数
实验在7×7×4的三维仿真环境中进行，对Agent的运动进行了模拟和检测。此外，对改进后的动态A*-Q-Learning算法和传统的Q-Learning算法进行比较，以验证改进后的A*和动态搜索因子ε对无人机航迹规划的积极作用。
实验中使用的主要参数如表2所示。
其中，学习率α为算法中的参数，决定收敛速度的快慢;折扣因子γ表示对未来奖励的看重程度;山体膨胀系数指的是为防止无人机飞行时与山体距离过于接近而发生事故，将山体放大的倍数。
3.2 仿真环境飞行结果
设定起点为（0，0，0），终点为（3.5，4.0，1.5），图3给出了仿真环境中无人机从起点到终点的飞行轨迹。
从图3中可以看出，无人机从起点开始出发，穿过仿真环境中的山脉和风力区域到达终点。使用Q-Learning算法时，无人机航迹与直线距离偏差较大，且航迹受风力影响较大;而使用动态A*-Q-Learning算法时，无人机航迹与直线距离偏差较小，并且在经过风力区域时也保持着较高的稳定性。
3.3 回报函数分析
回报函数通过将任务目标具体化和数值化，实现了目标与算法之间的沟通。在具体的运用之中，随着迭代的推进，回报函数的大小及变化趋势能够有效地反映出算法的优良程度。
图4中，Q-Learning算法与动态A*-Q-Learning算法在起始时刻的回报值表现出差异。Q-Learning算法的回报值约为-60，根据回报函数的设置，其航迹表现为无目的性地徘徊;动态A*-Q-Learning算法起始时刻的回报值约为-100，其在初始化策略的过程中没有考虑到风力的作用，在风力的作用下与山体发生碰撞，得到负回报-100，即在不考虑风力的作用下，航迹的起始初始值远大于传统算法。其航迹结果表明动态A*-Q-Learning算法比Q-Learning算法更具方向性，有效加快了Agent探索过程。
从整体看，Q-Learning算法的回报值增长趋势较缓，在迭代次数为50 000左右时就收敛于-20左右;动态A*-Q-Learning算法的回报值增长趋势明显，最后收敛于0左右，表明其在探索最优路径的过程中花费了较多的时间，但是最后的总回报却更优。
因此，从回报函数值的变化趋势可以推断出：在迭代初期，动态A*-Q-Learning算法与Q-Learning算法相比，前者的航迹表现出更强的方向性，同时所得到的结果具有更优的回报。
3.4 探索步数分析
一个成熟算法在寻优过程中所付出的代价可以表现为收敛时所需的步数。探索步数的峰值和增长速度能反映出算法的寻优能力及算法的稳定性能。
图5中，Q-Learning算法与动态A*-Q-Learning算法在探索步数的峰值方面表现出较大的差异。动态A*-Q-Learning算法探索步数的峰值为55，小于Q-Learning算法探索步数的峰值65，且最终收敛后的步数更少。在环境信息相同的情况下，动态A*-Q-Learning算法只需较少的探索步数就可学习到更多的信息，可帮助Agent获取更多环境反馈的信息，从而做出更加合理的动作策略。
从整体上看，动态搜索因子ε增强了动态A*-Q-Learning算法在迭代初期的探索能力，在获取更多环境反馈信息的情况下，帮助算法提高了最终的收敛程度，同时在迭代末期加快了收敛的速度，动态A*-Q-Learning算法相较于Q-Learning算法，表现出更强的稳定性能和探索能力。
3.5 运行效率分析
运行效率是判断算法优劣的重要指标。主要对算法的空间效率和时间效率进行分析，目前空间效率不作为关注的重点。实验在相同设备上进行，两种算法时间上的表现如图6所示。
图6中，展示了Q-Learning算法与动态A*-Q-Learning算法迭代次数与时间的关系曲线。对比曲线的总体水平和斜率，可知动态A*-Q-Learning算法的总体时间水平低于传统算法;同时曲线的斜率低于传统算法的斜率，表明改进后的算法在每代的迭代时间上少于传统算法。在迭代次数为55 000次之后，斜率保持不变，陷入局部最优的状况，因此，无法探索出更优的路径。
对比Q-Learning算法与动态A*-Q-Learning算法，在对回报函数、探索步数及运行效率进行分析之后，验证了动态A*-Q-Learning算法在结合A*以及引入动态搜索因子ε后，表现为探索能力增强，算法运行效率提高，得到的结果更优的特点。
4 结 论
本文通过结合A*算法以及引入动态搜索因子ε对传统的Q-Learing算法进行了改进，克服了算法迭代效率低以及易陷入局部收敛的缺点，以更低的成本得到更高的回报。此外，将动态A*-Q-Learning算法应用于无人机的航迹规划中，在仿真环境下通过实时更新Q值表，使得无人机具备良好的自适应性，能够根据外界环境的变化采取最合适的动作策略。最后，无人机通过强化学习获得了较强的自我探索能力，可在具有更多试错机会的情况下探索出最优飞行路径。
参考文献：
[1] 秦智慧，李宁，刘晓彤，等。无模型强化学习研究综述 [J].计算机科学，2021，48（3）：180-187.
[2] 韩忻辰，俞胜平，袁志明，等.基于Q-Learning的高速铁路列车动态调度方法 [C]//第31届中国过程控制会议（CPCC 2020）.徐州：中国自动化学会和中国自动化学会过程控制专业委员会，2020：1.
[3] 张汝波，顾国昌，刘照德，等.强化学习理论、算法及应用 [J].控制理论与应用，2000（5）：637-642.
[4] 高阳，陈世福，陆鑫.强化学习研究综述 [J].自动化学报，2004（1）：86-100.
[5] MATHEW A，JOLLY M J，MATHEW J. Improved Residential Energy Management System Using Priority Double Deep Q-Learning [J].Sustainable Cities and Society，2021，69：102812.
[6] WEN S H，CHEN J H，LI Z，et al. Fuzzy Q-Learning obstacle avoidance algorithm of humanoid robot in unknown environment [C]//第37届中国控制会议.武汉：中国自动化学会控制理论专业委员会，2018：5.
[7] 朱志斌，王付永，尹艳辉，等.基于Q-Learning的离散时间多智能体系统一致性 [J].控制理论与应用，2021，38（7）：997-1005.
[8] 蒋国飞，吴沧浦.基于Q学习算法和BP神经网络的倒立摆控制 [J].自动化学报，1998（5）：88-92.
[9] 胡嘉悦，李广文，章卫国，等.面向有人/无人机协同远程作战的IVMS架构 [J/OL].航空学报：1-12[2021-04-30].http：//kns.cnki.net/kcms/detail/11.1929.V.20210326.1703.022.html.
[10] 王科银，石振，杨正才，等.改进强化学习算法应用于移动机器人路径规划 [J/OL].计算机工程与应用：1-7[2021-04-28].http：//kns.cnki.net/kcms/detail/11.2127.TP.20210331.1016. 006.html.
[11] 吴蔚楠.多无人飞行器分布式任务规划技术研究 [D].哈尔滨：哈尔滨工业大学，2018.
[12] 张栋，李如飞，闫晓东，等.基于智能优化算法的集群协同航迹规划方法研究 [J].战术导弹技术，2020（6）：17-29+ 103.
[13] 阎昊，樊兴，夏学知.图结构与Dijkstra算法在无人机航迹规划中的应用 [J].火力与指挥控制，2010，35（4）：155-157+160.
[14] 王宁，代冀阳，应进.基于改进势场的无人机编队恢复与一致性仿真 [J/OL].系统仿真学报：1-16[2021-04-12].https：//doi.org/10.16182/j.issn1004731x.joss.20-0980.
[15] 陈诚，林秋婷，邱荣祖.基于随机规划模型的弹性木材供应链网络优化 [J].森林与环境学报，2021，41（1）：88-95.
[16] 郑书朋，郑淑涛，朱思滨，等.基于启发搜索策略的飞行仿真系统实时调度算法 [J].沈阳工业大学学报，2011，33（1）：86-92.
[17] 张志文，张鹏，毛虎平，等.改进A*算法的机器人路径规划研究 [J].电光与控制，2021，28（4）：21-25.
[18] 程志，张志安，乐伟扬，等.基于D* Lite算法的三维路径规划研究 [J].传感器与微系统，2020，39（12）：71-73+77.
[19] 郝钏钏，方舟，李平.基于Q学习的无人机三维航迹规划算法 [J].上海交通大学学报，2012，46（12）：1931-1935.
[20] 封硕，舒红，谢步庆.基于改进深度强化学习的三维环境路径规划 [J].计算机应用与软件，2021，38（1）：250-255.
[21] 张思齐.基于部分可观测马尔科夫决策过程的干扰决策研究 [D].西安：西安电子科技大学，2019.
[22] 秦旋，陈舒铃，乔任.复杂性视角下基于Agent智能体的复杂工程社会风险演化研究 [J].软科学，2021，35（6）：125-131.
作者简介：程传斌（1998.01—），男，汉族，江西上饶人，本科在读，研究方向：强化学习;倪艾辰（2000.06—），男，汉族，江苏镇江人，本科在读，研究方向：数字经济;房翔宇（1999.12—），男，汉族，河南永城人，本科在读，研究方向：人工智能和大数据;通讯作者：张亮（1977.02—），男，汉族，湖北随州人，教授，博士，研究方向：分布参数的控制理论。
收稿日期：2021-04-06
基金项目：国家自然科学基金（61573012）
