0 引　言

智能体Agent多指无人自主装备，本文主要特指无人船、艇、舟等USV装备，研究的算法同样适用其他无人装备。Agent 路径规划是指Agent 对环境进行感知并自主规划出能够躲避障碍的从起点到达终点的运动轨迹。显然，Agent 路径规划能力对Agent 执行特定任务非常重要。Agent 路径规划的传统解决方法主要有粒子群算法、A^* 算法、遗传算法、模拟退火算法、蚁群算法、人工势场法等^[1-2]。随着技术发展以及Agent 面对环境快速、准确的路径规划训练需求，人们提出了利用强化学习方法，通过Agent 与环境之间的交互，不断试错积累经验，使Agent 从环境中获得的累积奖励值最大，从而使Agent 获得行为最优决策能力^[1]。深度强化学习（DRL）将深度学习与强化学习进行融合^[2]，其中深度学习利用神经网络实现状态动作值函数的逼近，强化学习根据神经网络的状态动作值函数的输出以及一定的探索策略完成决策，从而实现状态到动作的映射，能较好地满足Agent 的路径规划需求^[2]。为了Agent 能够快速优化路径，本文将强化学习中的Q-learning与神经网络方法相结合，针对Agent 训练初期动作选择随机性较强从而导致算法训练时间过长问题，采用以目标位置为导向的动作选择策略^[3]及动作回报函数的动态计算方法^[4]，对算法进行优化，提高其实用性，最后验证了算法的有效性，加快了训练收敛速度，缩短了路径长度，算法具备一定的泛化能力。

1 Q-learning 基础算法

强化学习通过Agent 与环境之间的交互进行决策，Agent观察当前t时刻状态s_t，采取某种行为a_t作用于环境 ，然后获得奖励r_t，并进入状态s_t+1，如此循环。Agent根据奖励值随时调整行为，以获得最大回报，其基本原理如图1所示^[5]。

回报定义为即时奖励值的加权累积，一般用状态s_t处的状态值函数来描述回报。

${v}_{\text π}\left({s}_{t}\right)={E}_{\text π}\left[\sum _{k=0}^{\mathrm{\infty }}{\gamma }^{k}{r}_{t+k+1}|s={s}_{t}\right]。$

(1)

式中：${\mathit{\gamma }}^{\mathit{k}}$为折扣权系数；${\mathit{r}}_{\mathit{t}+\mathit{k}+1}$为即时奖励。t状态动作值函数为：

${q}_{\text π}\left({s}_{t},{a}_{t}\right)={E}_{\text π}\left[\sum _{k=0}^{\mathrm{\infty }}{\gamma }^{k}{r}_{t+k+1}|s={s}_{t},a={a}_{t}\right]。$

(2)

Agent在每次动作完成以后，都要更新值函数，针对不同的更新策略，产生了不同的学习算法，其中Q-learning是一种通过离策略找到最优策略的时间差分（TD） 控制方法。当通过Q-learning学习动作时，利用从环境中得到的即时奖励值$\mathit{r}$来进行算法更新，当$\mathit{r}$值较大时，这个动作将被加强；当$\mathit{r}$较小时，这个动作将被减弱。Q-learning更新规则采用Bellman方程式：

$Q\left(s,a\right) = Q\left(s,a\right) + \alpha\left[r+\gamma {\rm {max}}_{a^{\mathrm{'}}} Q\left(s',a'\right)- Q\left(s,a\right)\right]。$

(3)

式中：$\mathit{Q}\left(\mathit{s},\mathit{a}\right)$ 为Agent 的状态动作值函数；$\mathbf{\alpha }$为学习率；$\left(\mathit{s},\mathit{a}\right)$ 分别为Agent 当前状态和动作；$(s',a')$分别为下一个状态和动作；$\mathit{\gamma }$为折扣因子。Q-learning 通过$\varepsilon -greedy$贪婪策略选取最优的动作^[6]。

当Agent状态、动作较少时，可建立Q值表，存储$\mathit{Q}\left(\mathit{s},\mathit{a}\right)$值，通过足够多的训练次数，Q值表内的Q值最终将收敛，Agent 将在Q值表中找到最优策略进行执行^[7]。当环境非常复杂，状态空间的Q值表数据量巨大，产生计算维数灾难，很难找到最优策略，此时可利用神经网络进行Q值逼近^[4]。

2 避碰及路径规划建模 2.1 环境及状态建模

本文讨论的路径规划主要针对二维环境。为简化描述，对环境采用网格地图建模，无人船Agent 在二维网格中运动，其t时刻状态s_t可用当时的无人船Agent 位置来表达。如图2所示，将环境分为$\mathit{n}\times \mathit{m}$个等边长网格，在网格内设置起点、终点及障碍，整个网格可以用环境矩阵EM表示^[7]，0为网格无障碍物；1为Agent 当前位置；2为终点位置；3为网格中的障碍物，坐标为(x,0)、（0,y）、(x_m,y)、(x,y_n)为环境的边界，Agent 为不可驻留及跨越。

根据不同的策略学习算法，可将(x_t, y_t)或实时EM矩阵或当前实时网格图像作为智能体Agent 状态${\mathit{s}}_{\mathit{t}}$，输入神经网络进行训练。Agent初始对环境未知，没有任何先验知识，具备一定的环境感知能力，能够发现邻近障碍物，Agent路径规划的目的是避开环境中的障碍物，能够到达目的地，尽可能保证路径最短。环境中的障碍以静态为主。

2.2 动作空间与探索策略

Q-learningt动作选择随机性强，在策略探索前期，无人船Agent有很大概率碰撞到障碍物，这些大量的碰撞经验降低算法的收敛速度，本文将$\varepsilon -greedy$策略与启发式策略相结合进行动作选取，当Agent每次选择动作时，尽可能选择朝着目标方向的动作^{[3, 8]}，克服Agent无先验知识而导致的学习速度慢的缺陷，缩短值函数收敛时间。

设t时刻Agent 状态s_t=(x_t, y_t)，目标状态为s_g=(x_g, y_g)，Agent朝着目标的方向动作，能够确保最短路径，方向角可定义为^[3]：

$\mathrm{\varnothing }={\rm arctan}\frac{{y}_{g}-{y}_{t}}{{x}_{g}-{x}_{t}}\text{，}\mathrm{\varnothing }\in \left(-{\text π} , \right.\left.{\text π} \right]。$

(4)

规定Agent在每个状态下可以采取8个动作，分别从当前网格状态移动到8个相邻的网格状态^[3]，用动作方向角表示8个动作：

$A\left[i\right]=\left\{0,\frac{\text π}{4},\frac{\text π}{2},\frac{3\text π}{4},\text π,-\frac{3\text π}{4},-\frac{\text π}{2},-\frac{\text π}{4}\right\}\text{，}i=\mathrm{0,1}\dots 7 。$

(5)

计算目标方向角与8个动作方向角之间的夹角，取最小的夹角所对应的动作方向，为目标导向的动作a_t。

${\text π} \left({s}_{t}\right)={a}_{\mathrm{t}}=A\left[{\rm arg{min}}_{i}\left(\mathrm{\varnothing }\mathrm{与}A\left[i\right]\mathrm{之}\mathrm{间}\mathrm{夹}\mathrm{角}\right)\right] 。$

(6)

为了Agent的策略探索，利用$\varepsilon -greedy$策略，以$1-\varepsilon$概率选择目标导向的动作a_t，否则以$\varepsilon$概率选取最大Q值对应的动作。

${\text π} \left({a}_{t}|{s}_{t}\right)= \left\{\begin{array}{l}1-\varepsilon，{\rm if} \quad{a}_{t}=A\left[i\right]目标导向，\\ \varepsilon，{\rm if} \quad{a}_{t}={\rm arg{max}}_{a}Q\left({s}_{t},a\right)\text{，} a\in A\left(s\right)。\end{array}\right.$

(7)

障碍物避碰动作，如果Agent执行动作a_t遇到障碍物，避碰则保持原状态不变，获得奖励后，进行避碰动作选择，继续训练，避碰动作依次如下：

$a_{\mathrm{t}} = A\left[i\right]\text{，} i = [i + k + 8]\mathrm{mod}8,k\epsilon[-\mathrm{1,1},-\mathrm{2,2},-\mathrm{3,3},-4]_{ }。$

(8)

2.3 奖励函数模型

无人船Agent在状态s_t执行a_t动作后，环境反馈奖励r_t进行动作评价，Agent试图获得最大总报酬，奖励函数指导Agent实现其目标，r_t值越高，其动作越值得选择，奖励函数能决定算法的收敛速度。一般奖励函数设置为静态固定值，本文为了奖励Agent快速接近终点，利用人工势场法动态设置奖励函数^[4]，Agent越接近目标，r_t越高。

$r_t=\left\{ \begin{array}{l}15\text{，}\qquad\qquad\quad\ \ 如果\mathrm{Agent}移动到终点，\\ 10-kD\left(s_{t+1},s_g\right),\ 如果\mathrm{Agent}移动到新状态，\\ -kD\left(s_{t+1},s_g\right),\quad\ \ 如果\mathrm{Agent}碰到障碍物。\end{array}\right.$

(9)

式中：k为灵敏系数控制奖励的范围；${D}\left({\boldsymbol{s}}_{{t}+1},{\boldsymbol{s}}_{{g}}\right)$为Agent与目标之间的距离。当Agent移动到终点时即时奖励最大，移动到正常网格状态时，根据与终点距离大小计算奖励；当遇到障碍物时取值较低，不同的障碍物根据位置的不同，其奖励函数也有区别。

3 路径规划的Q神经网络训练框架

Q神经网络是神经网络和Q-learning相结合的无监督学习方法。强化学习为神经网络提供训练的样本，神经网络对输入的无人船Agent 状态进行逼近计算，得出Agent所有状态动作值$\boldsymbol{Q}\left({\boldsymbol{s}}^{},{\boldsymbol{a}}^{}\right)$。Q神经网络利用梯度下降法对网络权重$\boldsymbol{w}$进行更新^[4]。

$Q\left({s}^{},{a}^{};w\right)\approx Q\left({s}^{},{a}^{}\right)，$

(10)

$\begin{split}w_{t+1}= & w_t+\alpha\left[r+ {\gamma \max}_{a^{'}}Q\left(s',a';w\right)-Q\left(s^{ },a^{ };w\right)\right]. \\ & \nabla Q\left(s^{ },a^{ };w\right)。\end{split}$

(11)

式中：$\boldsymbol{w}$为神经网络的权值；$\nabla \boldsymbol{Q}\left({\boldsymbol{s}}^{},{\boldsymbol{a}}^{};\boldsymbol{w}\right)$为$\boldsymbol{Q}\left({\boldsymbol{s}}^{},{\boldsymbol{a}}^{}\right)$关于$\boldsymbol{w}$权值向量的梯度，为了避免训练样本的关联性，可设置独立的目标网络计算时序差分（TD）目标，深度Q神经网络算法（DQN），促进神经网络训练的收敛。

$\begin{aligned}w_{t+1}= & w_t+\alpha\left[r+\gamma\mathrm{max}_{a^{\mathrm{’}}}Q\left(s^{\mathrm{'}},a^{\mathrm{'}};w^{\mathrm{'}}\right)-Q\left(s^{ },a^{ };w\right)\right]。\\ & \nabla Q\left(s^{ },a^{ };w\right)。\end{aligned}$

(12)

式中：$\mathit{w}$权重为估值网络，w'权重为目标网络；${\mathit{w}}_{\mathit{t}}$为t时刻估值网络权重；估值网络持续训练，目标网络不训练，只用来计算训练过程的TD目标，以一定的周期同步估值网络的权重参数，通过该TD目标网络可以降低训练数据的独立性，提高网络的稳定性。定义损失函数^[6]：

$L\left(w\right)=E\left(r+\gamma\mathrm{max}_{a^{\mathrm{'}}}Q\left(s^{\mathrm{'}} ,a^{\mathrm{'}} ;w^{\mathrm{'}}\right)-Q\left(s^{ },a^{ };w\right)\right)^2。$

(13)

由于Q-learning选取动作值函数采用max操作，存在过估计问题，DQN 神经网络算法利用 Q-learning 提供有标签的样本，所以DQN同样存在过估计问题，可能导致策略逐渐变成次优解，对DQN进行优化，产生优化网络DoubleDQN，神经网络结构相同^[4,6,9]，只是TD目标函数不同，TD目标及损失函数为：

$\begin{aligned} L\left(w\right)=&E\left(r+\gamma Q\left({s}^{\mathrm{'}},{\rm arg{max}}_{{a}^{\mathrm{'}}}\right.\right.\\& \left.\left.Q\left({s}^{\mathrm{'}},{a}^{\mathrm{'}};w\right);{w}^{\mathrm{'}}\right)-Q\left({s}^{},{a}^{};w\right)\right)^{2}，\end{aligned}$

(14)

$\begin{aligned} {w}_{t+1}=&{w}_{t}+\alpha \left[r+\gamma Q\left({s}^{\mathrm{'}} ,{\rm arg{max}}_{{a}^{\mathrm{'}}}\right.\right.\\ &\left.\left.Q\left({s}^{\mathrm{'}},{a}^{\mathrm{'}};w\right);{w}^{\mathrm{'}}\right)-Q\left({s}^{},{a}^{};w\right)\right]\nabla Q\left({s}^{},{a}^{};w\right)。\end{aligned}$

(15)

Q神经训练结合目标导向的动作策略以及经验回放，构建算法训练框架如图3所示。

神经网络训练时是有监督的学习模型，训练数据满足独立同分布的假设，利用Q-learning获取的样本关联性较大，不利于神经网络的稳定收敛，利用经验回放，将Agent每次执行结果$\left(\mathit{s},\mathit{a},\mathit{r},{\mathit{s}}^{\mathit{'}}\right)$存储于经验池，定期均匀随机提取经验池中小批量样本进行训练，降低数据之间的相关性，避免权重参数的振荡或发散^[4]。使用Q神经网络代替Q表，解决“维数灾难”问题，同时增强模型的泛化性^[8]。DQN方法动作选择随机性强，训练时间过长，结合目标导向的动作选择及奖励函数动态计算，构造网络训练框架^[6,10]，加快算法收敛速度。

4 路径规划的算法流程设计

以神经网络训练框架为基础，结合避碰知识、目标导向策略、动态奖励计算方法，构建无人船Agent避碰导航算法流程，有效避免无效探索，加快算法的收敛速度，缩短Agent的路径长度。神经网络训练及路径算法流程如图4所示。

算法中的Agent状态可以是实时EM矩阵或当前实时网格图像。算法首先初始化各种参数，随机设置估值网络、目标网络的权重，对于每个回合的每一步，首先根据目标的位置，以$1-{\varepsilon}$概率利用目标导向的动作策略，但为了保持一定的探索能力，以${\varepsilon}$概率利用目标网路提供的最大Q值对应的策略，并将状态与回报存于回放经验池中；Agent判断策略将导向障碍物时，选择避碰策略执行；对估值网络进行周期训练及同步估值网络与目标网络。

5 实验仿真与分析

为验证算法的有效性，以无人船作为Agent实例，设置了一个虚拟的20×20网格环境，如图5所示，初始设置了终点及静态障碍点，Agent的起点在训练过程中随机产生。在任意时刻Agent都有8个动作，Agent状态s_t为20×20矩阵。表1中为算法参数。

t时刻无人船Agent位置s_t=(x_t, y_t)，目标位置为s_g=(x_g, y_g)动作的即时奖励函数r_t具体设置如下：

$r_t=\left\{\begin{array}{l}15,\\ 如果\mathrm{Agent}到达终点；\\ 10-\dfrac{1}{3}\sqrt{(x_{t+1}-x_g)^2+(y_{t+1}-y_g)^2},\\ 如果\mathrm{Agent}移动到新位置状态；\\ -\dfrac{1}{3}\sqrt{(x_{t+1}-x_g)^2+(y_{t+1}-y_g)^2},\\ 如果\mathrm{Agent}碰到障碍物。\end{array}\right.$

(16)

如图5所示，无人船Agent 从S₁出发，经过训练找到了最终的避碰优化路径，路径从起点到终点共24步，长度较短，无效及绕行路径很少，由于采用了ε-greed策略选取目标导向的动作，整个路线从开始就一直趋向目标点方向，减少试错次数，缩短路径的总步数。算法是有效的，在收敛方面效果比较好。当改变Agent的起点为S₂或S₃时，Agent分别用了18、19步到达目标终点，都是基于目标导向的最短路径，这说明算法对起点选择具有泛化能力。

如图6所示，障碍物的数量和位置发生了一定的变化，无人船Agent 同样可以顺利从起点S₁避碰到达目标终点S_g，共28步。Agent避障时产生了曲折的路径，这是因为障碍物位置变化后，按照以前的训练结果选择动作，与最优方向有偏差。Agent的感知能力，神经网络在Agent运动过程中不断训练，都可适应障碍物变化，保证算法一定的泛化能力。

如图7和图8所示，无人船Agent经过190多回合迭代训练，平均奖励值及每回合步数开始趋于稳定，260次左右完全收敛，训练总步数为12524步，平均每回合的步数为48步。在训练初期，Agent需要很多步才能到达终点，有时碰撞障碍物，平均奖励不稳定，振幅较大，以目标导向作为动作策略，促使了算法平均奖励值收敛加快。

6 结　语

强化学习在线决策与神经网络函数逼近相结合，是解决以无人船、艇、舟等USV设备为代表的自主Agent避碰及路径规划的有效方法。本文参考人类行为，利用目标导向作为动作策略，避免大量无效动作路径，设置动态奖励方法，期望越接近目标收敛越快，将Q-learning与神经网络相结合，构建了有效的算法，既可适应静态障碍的避碰与导航，同时对随机点出发及障碍变化的环境，算法具有一定的泛化性。算法也有缺陷，面对马蹄形障碍，容易训练失败，算法存在一定的过拟合现象，如果障碍物位置与数量动态持续变化，算法不适应，待以后重点研究。