0 引　言

随着自主水下航行器（AUV）技术的发展和应用场景的不断扩大，人们对AUV的自主性和稳定性提出了更高要求。路径规划为智能水下机器人技术的主要研究方向和研究热点之一，同时是AUV实现自主决策的重要前提条件，贯穿AUV水下作业的全过程。在执行航行任务中，利用先验的电子海图信息进行全局路径规划可有效辅助机器人水下航行。当前常用的路径规划算法有人工势场法^[1]、A*算法^[2-3]、蚁群算法^[4-5]、遗传算法、Q学习算法^[6]等，近年来随着机器学习技术的快速发展，强化学习算法已成为解决路径规划问题的热门方案。

Q学习算法是路径规划问题中较为常用的强化学习方法，在无人车、无人机、机械臂、无人航行器等领域使用广泛。Q学习算法可为路径规划问题提供良好的解决办法，但在训练过程中，算法根据环境直接给出动作执行的评价而忽略其余动作所含信息，算法存在收敛困难、探索不平衡、参数敏感等问题^[7]。在强化学习技术高速发展背景下，针对Q学习算法的改进研究也取得了部分进展，Mnih等^[8]使用深度强化学习来实现路径规划的方法，结合Q学习算法与深度神经网络，实现了在Atari游戏中超越人类水平的控制能力。Bonny等^[9]使用蜜蜂算法和 Q 学习算法以更少的迭代次数找到最佳路径。Zhu等^[10]采用缩小轨迹的规约规则，从而有效减少了冗余的探索空间，同时保证最优的导航路径仍在缩减的空间中。Maoudj等^[11]提出一个新的奖励函数来初始化Q表，并向机器人提供环境的先验知识改善计算时间和机器人安全性。Li等^[12]在Q学习的探索机制中增加了动态探索因子，以解决无人机在Q学习局部动态路径规划中利用与探索难题。这些研究在一定程度上解决了机器人在线路径规划中的维数灾难和收敛过慢问题，但对硬件计算能力和智能体的机动性有一定要求。为解决水下无人航行器离线全局路径规划问题，本文提出一种轻量级AUV路径规划算法，通过设计距离奖励函数使Q学习算法探索时加快学习效率，引入ε贪婪策略和Softmax策略相结合的机制提供一种平衡探索与利用的方法，同时考虑AUV运动约束简化动作集合的元素数量减少算法复杂度。

1 Q-learning算法理论

在Q学习中，智能体与环境进行交互，从当前状态开始，采取不同动作，并观察到下一个状态和获得的奖励。智能体的目标是学习一个策略，使得在每个状态下选择动作时能最大化累积奖励。AUV和环境一次交互过程轨迹所收到的累计奖励为总回报如下：

$ G\left(\tau \right)= \sum _{t=0}^{T-1}{r}_{t+1}=\sum _{t=0}^{T-1}{r}_{t+1}({s}_{t},{a}_{t},{s}_{t+1}) 。$

(1)

当目前环境中存在一个以上的终止状态，即达到此状态时交互过程结束，这一轮的交互过程称之为一个回合或实验。如果环境中没有终止状态，其总回报可能为无穷大，所以引入一个折扣率$ \gamma $来降低远期回报的权重。折扣回报定义为：

$ G\left(\tau \right)=\sum _{t=0}^{T-1}{\gamma }^{t}{r}_{t+1} 。$

(2)

式中：$ \gamma \in \left[\mathrm{0,1}\right] $为折扣率，$ \gamma $取值接近1时使智能体偏向于长期回报，$ \gamma $取值接近0时则偏向于短期回报, Q函数表示了在给定状态和动作下，累积折扣奖励的期望值。它可以用一个Q表来表示。Q学习算法通过不断更新Q函数的估计值来学习最优策略。Q学习的更新规则如下：

$ {Q （{s}_{t},{a}_{t}） \leftarrow {Q}\left({s}_{t},{a}_{t}\right)+\mathrm{\alpha }\left({r}+\mathrm{\gamma }\cdot{\max}_{a'}Q\left({s}_{t+1},{a'}\right)-Q\left({s}_{t},{a}_{t}\right)\right) 。}$

(3)

式中：$ {Q}\left({s}_{t},{a}_{t}\right) $为状态S下选择动作$ {a}_{t} $的Q值；$ \mathrm{\alpha } $为学习率，用于控制更新幅度；r为获得的奖励；γ为折扣因子；用于平衡当前奖励和未来奖励的重要性；$ {s}_{t+1} $是下一个状态；$ a' $是在状态$ {s}_{t+1} $选择的最佳动作。

2 AUV路径规划改进方法

传统Q学习简单易实现、无模型依赖性，不需要对环境的任何先验知识或模型做出假设，但存在采样效率低、收敛速度慢、参数调整敏感等问题。针对欠驱动AUV路径规划需求，本文提出一种改进Q算法提高算法性能和稳定性。

2.1 奖励函数设计

Q学习算法通过最大化奖励值来获得最优策略，针对路径规划复杂的应用环境，选择合理的奖励函数会得到更合理的策略，根据AUV专业知识设计奖惩函数，可提高AUV航向时安全，同时提加快强化学习的探索效率。水中环境复杂，目前大型AUV多数为欠驱动其运动约束明显。为了更有效地将Q学习算法应用于AUV路径规划，本文引入避碰奖惩机制和距离奖惩机制，同时结合启发性思想，加入启发性函数。AUV在当前状态S，在经过选择策略后执行a动作获得的总奖励由避碰奖惩和距离奖惩组成：

$ R=rewar{d}_{1}+rewar{d}_{2}。$

(4)

$ rewar{d}_{1} $为碰撞奖励函数，避免路径产生碰撞是保证AUV安全航行的前提，通常的Q学习选择固定值的奖励函数，动作到达终点奖励值为100，动作未产生碰撞奖励值为−1，动作产生碰撞奖励值为−50。

$ reward=\left\{\begin{array}{l}\text{−1,}\quad\ \mathrm{未}\mathrm{发}\mathrm{生}\mathrm{碰}\mathrm{撞}，\\ \text{100}\text{\text{，}}\ \mathrm{到}\mathrm{达}\mathrm{终}\mathrm{点}，\\ \text{−50}\text{\text{，}}\ \mathrm{发}\mathrm{生}\mathrm{碰}\mathrm{撞}。\end{array}\right. $

(5)

固定大小的奖励函数在特定情况下能够满足AUV路径规划的要求，AUV实际应用中不同任务航行距离相差大，使用固定的奖励值会使算法稳定性大幅度下降。在进行短距离任务时，探索步数较短便到达终点，容易陷入局部最优解。在进行长距离航行任务时，由于步数较多，会使到达终点的路线与其他路线累计奖励数值接近，导致算法不收敛。为解决以上问题，本文以任务距离为参数来设计奖励函数能提高算法适用范围和稳定性，选用奖励函数如下：

$ {reward}_{1}=\left\{\begin{array}{l}\text{−1}\text{，} \mathrm{未}\mathrm{发}\mathrm{生}\mathrm{碰}\mathrm{撞}，\\ \lambda \sqrt{({x}_{{s}_{t}}-X)({y}_{{s}_{t}}-Y)}\text{，}\mathrm{到}\mathrm{达}\mathrm{终}\mathrm{点}，\\ -\beta \text{，} \mathrm{发}\mathrm{生}\mathrm{碰}\mathrm{撞}。\end{array}\right. $

(6)

式中：$ \lambda $为终点参数，取值范围为[3,5]；$ \beta $为碰撞系数，取值范围为[20,50]；$ X $、$ Y $为目标点横纵坐标；$ {x_{{{{s}}_{{t}}}}} $、$ {{{y}}_{{{{s}}_{{t}}}}} $为当前状态$ {S_t} $位置所对应的横纵坐标。设计以任务距离相关的奖励函数，能有效解决固定奖励函数导致的问题，提高了该算法的适用范围与稳定性。

$ rewar{d}_{2} $为距离奖励函数，AUV进行长距离路径规划，Q学习算法探索初期缺乏方向性，迭代次数多，导致模型计算要求高。为加快算法的收敛速度，减少迭代计算次数，结合了启发性思想，引入距离奖惩机制改进 Q 学习算法的奖励函数。设计距离奖惩函数如下式：

$ {{reward}_{2} = \varphi \frac{( \sqrt{({x}_{{s}_{t}} - X{)}^{2} + ({y}_{{s}_{t}} - Y{)}^{2}} - \sqrt{({x}_{{s}_{\text{t+1}}} - X{)}^{2} + ({y}_{{s}_{\text{t+1}}} - Y{)}^{2}})}{D} 。}$

(7)

式中：$ \varphi $为奖励系数，D为目标起点和终点之间的欧氏距离，距离奖励能使Q学习算法减少计算时间，在AUV初期探索时更趋向于选择靠近目标点的动作。

2.2 探索因子的改进

在AUV学习过程中，合理地处理利用与探索的决策可显著提高算法性能。探索和利用代表了在选择动作时的2种不同策略，在不同阶段的学习中发挥着重要作用。参数初始化完成后，算法训练不足，需通过不断的探索来获取更多的环境信息。AUV随机选择动作，能更好地探索环境，并避免陷入局部最优解。此时的探索过程有助于建立对环境的模型和获取更多的奖励信息。当算法深入了解当下环境时，AUV应更加倾向于最优秀的信息来做出决策，选择更有效的动作，以最大化累积奖励。传统ε−贪婪策略通过设置一个小的ε值，智能体在能够利用已有信息的基础上进行一定程度的探索。近年来的研究^[13]表明若采用传统ε−贪婪值策略其误差会随着学习次数呈线性增长，为了能使算法在学习的过程中逐渐依赖于利用，更好地利用已有知识提高算法的训练效率。本文提出一种结合ε−贪婪策略和Softmax策略的选择机制。时变ε探索因子兼顾算法学习过程中的探索与利用，在初期尽可能多的进行“探索”，以求准确估计，在后期尽可能多的“利用”，以求最大化平均回报。贪婪策略从环境中直接给出最优动作执行，而忽略其余动作所含信息，容易使算法丢失最优解。Softmax策略用于从多个选择中进行概率性的随机选择，概率与选择的价值相关。Softmax策略对每个选择的价值进行归一化处理，根据归一化后的价值分布，按照概率进行随机选择，保留了所有动作所含的价值信息。

$ {a}_{\mathrm{S}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{x}}\to {p}_{\mathrm{S}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{x}}\left({a}_{i}\right)=\frac{{e}^{ \frac{Q\left({a}_{i}\right)}{\tau }}}{\displaystyle {\sum }_{k=j}^{k}{e}^{ \frac{Q\left({a}_{j}\right)}{\tau }}}。$

(8)

式中：$ {p}_{\mathrm{S}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{x}}\left({a}_{i}\right) $为执行动作$ {a_i} $的概率，$ Q\left({a}_{i}\right) $为选择动作$ {a}_{i} $对应的Q值，k为动作集合A的元素个数，$ \tau $为温度系数，用于调节选择情况，在高温下，模型更倾向于探索不同的动作，对于尚未学习到的情况有更多的探索性；而在低温下，模型更加倾向于选择已学到的最优动作，对于已知情况有更高的确定性。当温度参数$ \tau $趋近于无穷大时，Softmax函数的概率分布趋近于均匀分布；当温度参数$ \tau $趋近于0时，Softmax函数的概率分布趋近于一个单位脉冲函数，即只有最大价值的动作被选择的概率为1，其余动作的概率为0，通常温度取值范围在0.1～1。AUV动作策略应选择在初期偏向于探索，并随着学习次数增加逐渐偏向于利用的策略方法。在算法运行初期，探索获得的回报较大，Q值未收敛，选择并保持较大探索概率，以避免陷入局部最优。随着学习次数增加，算法在全局上已找到较优路径，处于局部范围优化阶段，此时应减小当前选择探索的概率。选择合适的探索因子$ \mathit{\varepsilon} $或$ \tau $均可平衡探索与利用的关系，考虑计算复杂度，选择固定$ \tau $和随迭代次数增加而减小的时变$ \mathit{\varepsilon} $，公式如下：

$ \mathit{\varepsilon} =\mathit{\varepsilon} /(1+{e}^{-\frac{N}{n}}) 。$

(9)

式中：$ \mathit{\varepsilon} $为探索概率；N为学习的总轮次；n为当前学习轮次。

改进Q学习算法使用的策略机制，首先生成一个小于1的随机正数p，若p＜1−$ \mathit{\varepsilon} $时，选择贪婪动作，若p≥$ \mathit{\varepsilon} $则由Softmax策略选择动作。

$ p\left({a}_{i}\right)=\left\{\begin{array}{l}{\rm{arg}\rm{max}}_{a\in A}{Q}_{t}\left(a\right),\; p > \mathit{\varepsilon}，\\ {a}_{\rm Softmax},\; p < \mathit{\varepsilon} 。\end{array}\right. $

(10)

2.3 简化动作集合A

AUV相比较陆地机器人和无人机其机动性较差，在动作集合上使用减枝策略，可使Q学习算法得出的路径更加平滑。通过当前状态$ {S}_{t} $与上一轮状态$ {S}_{t+1} $可得出当前速度方向，根据速度方向删除部分不满足欠驱动运动约束的动作缩小动作集合A。如图1所示，当速度方向为右上时，理论上航行器可选择向上、向下、向右、向左、右上、右下、左上、左下的8个动作，在AUV实际航行中，由于自身欠驱动和水中环境，在当前速度方向为右上方状态$ {S}_{t} $时，执行向左下、向下、向左运动的动作对于AUV是难以完成的。因此在动作选择时将左下、向下、向左运动的运动动作删除、使路径更加平滑减少计算时间。如图1中执行动作集合A更新为动作集合A'。

3 AUV路径规划仿真 3.1 仿真环境与参数设置

AUV的所处环境为海洋，航行时海洋中的障碍物多为岛屿，使用如图2中的栅格法设置障碍物。设置栅格方法操作简单，要求计算量低，为AUV与障碍物之间的距离增加余量，保证了AUV航行安全。

AUV执行短距离任务时，通常环境为距离海岸线不远的位置，珊瑚、岛屿浅水区均可视为障碍物，分布相对密集且零散，在AUV长距离航行任务，所处环境通常为深水海洋岛屿分布离散无规律。对2种不同的情况进行对比仿真验证，模拟不同使用环境，同时验证算法的适用范围，改进Q学习算法的参数设置如表1所示。

3.2 AUV路径规划仿真

选择24×24的仿真环境，模拟AUV执行短距离任务所处的复杂环境，对其进行仿真实验对比改进算法与传统Q学习算法的收敛速度和最优路径。传统Q学习算法选用ε贪婪算法，奖励函数选择式(5)。其仿真结果如图3～图4所示。

图3表明在复杂环境下改进算法减少路径长度7.85%，减少转向次数14.29%，避免陷入局部最优解。通常研究使用奖励值来评估强化学习算法的性能，是因为强化学习算法的核心是通过智能体与环境的交互，不断获取奖励或惩罚来训练其行为策略。图4表明，改进后的Q学习算法可更快获得奖励值，其迭代300次左右即可使AUV获得收敛路径，而传统算法需迭代近1300次使AUV的路径收敛，改进后的Q学习算法能获得的奖励值更高。

选择50×50的仿真环境，模拟AUV执行长距离任务所处环境，改进Q学习算法所用的参数如表1所示，传统Q学习算法在使用式(5)的固定奖励值进行仿真时无法收敛，将(5)中到达目标点的奖励值更改为250，与当前环境下式(6)到达终点奖励值相同，进行仿真实验，其结果如图5所示。

仿真结果表明，改进算法具有更高的适用范围，有效果缓解了传统Q学习算法的参数敏感性问题，同时改进Q学习算法最终收敛的最优路径长度减少6.10%，转向次数减32.14%。如图6(b)改进Q学习算法在学习约1300次时获得最大奖励，传统Q学习算法迭代约4000次获得AUV收敛路径，改进后学习的收敛速度更快。

4 结　语

针对传统Q学习算法存在的问题，本文以欠驱动AUV为对象，提出一种变参数的Q学习路径规划算法。在传统Q学习算法基础上设计避碰奖惩和距离奖惩函，优化动作集合，提高算法收敛速度、降低参数敏感性、扩大适用范围。同时引入时变贪婪策略和Softmax策略结合的机制，平衡利用与探索，使Q学习算法避免局部最优解。仿真对比实验表明：1）改进算法可在离线电子海图中为AUV提供无碰撞的路径，路径曲折及长度对比传统算法有明显提升；2）相比于传统Q学习算法解决路径规划问题，改进Q学习算法适用范围更广，具有更快的收敛速度和更好的鲁棒性。