水质监测无人船路径规划方法研究

吕扬民， 陆康丽， 王 梓

(浙江农林大学 信息工程学院， 浙江 临安 311300)

0 引 言

水质监测是水质评价和预防水污染的主要方法。随着工业废水的增多，水体污染的问题则引发高度关注，水污染动态监测的研究已然刻不容缓。但是因为传统的水质监测方法步骤繁多、并耗时不菲，而且获取到的数据多样性、准确性也远远未能满足决策的需求[1]。基于上述问题，多种水质监测方法已陆续进入学界视野。如曹立杰等人[2]提出通过建立传感器网络，得到较为精准的水质反演模型。田野等人[3]提出通过水质模型对卫星数据进行反演，得到监测水域的水质参数分布图。但是以上方法却无法灵活地更换监测水域，工程量大、且时效性欠佳，相较而言水质监测无人船体积小便于携带、监测领域不受地形影响，能连续性原位进行多项水质参数监测，使监测结果更具有多样性和准确性。

无人驾驶船(Unmanned Surface Vehicle，USV)是一种能够在未知水域环境下自主航行，并完成各种任务的水面运动平台[4]，其研究内容主要涉及了自动驾驶、自主避障、航行规划和模式识别等热门方向[5]。故而，目前已广泛应用于军事领域的扫雷、侦察和反潜作战等方面，同时还可以用于民用领域的水文气象探测、环境监测和水上搜救等专项服务中[6-8]。但由于水质的流动性，可以流经多种复杂地形，如流经洞穴时等，工作人员将无法探测；或又由于天气的多变，如水域长期处于多雾天气，致使工作人员视线受阻，因而无法实时准确地掌控操作USV。综合上述分析后可知，就可以利用USV的自主航行到达目标水位进行检测，而自主航行功能的实现即需用到本文下面拟将系统展开研究的路径规划技术。

USV路径规划技术是指USV在作业水域内，按照一定性能指标(如路程最短、时间最短等)搜索得到一条从起点到目标点的无碰路径[9]，是USV导航技术中核心组成部分，同时也代表着USV智能化水准。目前常用的规划方法主要有粒子群算法[10]、A*算法[11]、可视图法[12]、人工势场法[13]、蚁群算法[14]等，但其方法多用于已知环境条件下。

当前对于已知环境下的航迹规划问题已经得到了较好的解决，但USV在未知水域作业执行任务之前却无法得到将要监测水域的环境信息，无法通过基于已知环境信息的路径规划方法去求出USV航行路线[15]。此外，由于监测水域环境复杂，传感器信息众多，系统的计算工作量大，致使USV存在实时性差、障碍物前振荡等缺点。因此USV路径规划亟需研究算法简单、实时性强、且能控制系统中的不确定现象的路径规划算法，所以有必要引入具有自主学习能力的方法，其中基于Q学习算法的路径规划适合于在未知环境中的路径规划。现阶段研究中，郭娜[16]即在传统Q学习算法基础上，采用模拟退火方法进行动作选择，解决探索与利用的平衡问题。陈自立等人[17]提出采用遗传算法建立新的Q值表以进行静态全局路径规划。董培方等人[18]把人工势场法加入Q学习算法中，以引力势场作为初始环境先验信息，再对环境逐层搜索，加快Q值迭代。

在此基础上，本文提出了一种基于BP神经网络的Q学习强化学习路径规划算法，以神经网络拟合Q学习方法中的Q函数，使其能够以连续的系统状态作为输入，并通过经验回放和设置目标网络方法显著提高网络在训练过程中的收敛速度。经过实验仿真，验证了本文所提出改进路径规划方法的可行性。

1 问题描述

USV路径规划的实质是在一定标准下找出从初始位置到最终位置的最佳无碰撞安全路线。

USV路径规划研究中，首先需要建立一个可航行的环境模型。假设USV的航行环境为存在着一定数量的静态障碍物的二维空间，采用栅格法对此区域进行分割。将栅格区域的左下角设为空间坐标系原点，水平向右为X轴，垂直向上为Y轴，划分为n*n栅格坐标系。如此一来，该问题就简化为在静态环境中寻找从开始点到终点的无碰撞的最优路径。

设计中运用神经网络拟合函数，输入为USV的当前状态，USV的状态是以当前位置来表示，即空间坐标s；USV路径规划的输出是下一时刻的转角，即动作a。环境状态信息则是以障碍物的位置和大小及目标点的位置来表示，不同环境下障碍物出现的位置不同，目标点的设定位置也不同。网络的输出个数为动作空间的数量，每个输出表示在当前状态下，采取对应动作后的期望奖励大小R(s)。对此内容可研究详述如下。

2 基于改进Q学习的无人船路径规划方法

2.1 基于传统Q学习的路径规划方法

Q学习是基于马尔科夫决策过程 (Markov Decision Process) 来描述问题，通过USV与环境的互动积累经验，同时不断更新USV的策略，使其做出的决策能够获得更高的奖励。常用的强化学习方法包括模仿学习、Q学习及策略梯度法等。而且进一步研究可知，Q学习方法不需要收集训练数据，且能够生成决定性策略，因而适用于USV在未知水域进行路径规划问题。

马尔科夫决策过程包含4个元素，分别是：S,A,Ps,a,R。其中，S表示USV所处的系统状态集合，即USV在当前的状态及当前环境的状态，如障碍物的大小和位置；A表示USV所能采取的动作集合，即USV转动的方向；Ps,a表示系统模型，即系统状态转移概率，P(s'|s,a)描述了在当前状态s下，执行动作a后，系统到达状态s'的概率；R表示奖励函数，由当前的状态和所采取的动作决定。把Q学习看成找到策略使综合评价最大的增量式规划，Q学习的设计思想是不考虑环境因素，而是直接优化一个可迭代计算的Q函数，定义函数为在状态st时执行动作at，且此后最优动作序列执行时的折扣累计强化值，即：

(1)

其中，γ为折扣因子，其值0≤γ≤1；R(st)为奖励函数，其值为正数或者负数。

在初始阶段学习中，Q值可能是不正确地反映了其所定义的策略，初始Q0(s,a)对于所有的状态和动作假定是给出的。这里，若设给定环境的状态集合为s，USV可能的动作集合A选择性较多，数据量大，需要用到可观的系统内存空间，且无法被泛化。为了克服上述不足，对传统Q学习进行改进，采用BP神经网络实现Q值迭代，网络的输入对应描述环境的状态，网络的输出对应每个动作的Q值。

2.2 改进的Q学习路径规划算法

Q(λ)算法借鉴了TD(λ)算法，通过回溯技术让数据不断地进行传递，使得某一状态的动作决策也会受到其后续状态的影响。如果未来某一决策π是失败的，那么当前的决策也要承担相应的惩罚，会把这种影响追加到当前决策；如果未来某一决策π是正确的，那么当前的决策也会得到相应的奖励，同样也会影响当前决策。结合改进后能够提高算法的收敛速度，满足学习的实用性。改进的Q(λ)算法更新规则为：

(2)

(3)

另外，也可以把TD(0)误差定义为：

δt+1=R(st+1)+γV(st+2)-V(st+1)

(4)

在这一过程中，也应用了折扣因子λ∈[0,1]，并以此对将来步骤中的TD误差进行折扣，其数学公式可表示为：

(5)

(6)

只要将来的TD误差未知，前述的更新就无法进行。但是，通过使用跟踪迹就可以逐步求得其值。下面将ηt(s,a)定义为特征函数：在t时刻(s,a)发生，则返回1，否则返回0。为了简化，忽略学习效率，对每个(s,a)定义一个跟踪迹et(s,a)，如式(7)所示：

(7)

那么在时刻t在线更新为：

δtet(s,a)]

(8)

强化学习希望使系统运行时收获的总体收益期望最大，即E(R(s0)+γR(s1)+γ2R(s2)+…)最大。为此需要找到一个最优策略π，使得当USV依照π进行决策和运动时，获得的总收益最大。通常，强化学习的目标函数为以下其中之一：

Vπ(s)=E(R(s0)+γR(s1)+γ2R(s2)+…|s0=s,π)

Qπ(s,a)=E(R(s0)+γR(s1)+γ2R(s2)+…|s0=s,a0=a,π)

(9)

Q*(s,a)=R(s0)+γE(R(s1)+

γR(s2)+…|s1,a1)

(10)

且a1由π*决定，则：

(11)

那么，可得出：

(12)

式(12)称为贝文曼方程。该方程是以递归的形式定义了Q*(s,a)，从而使得Q函数可以被迭代求出。

传统Q学习算法中，Q函数是以表格的形式保存并更新，但在USV避障路径规划中，遭遇的障碍物可能出现在空间中任意位置，若以表格的形式Q函数将难以描述在连续空间中出现的障碍物。针对这一状况，本文在Q学习基础上，将展开深度Q学习以BP神经网络来拟合Q函数，其输入状态s是连续变量。通常，以非线性函数拟合Q函数时学习过程难以收敛，对此研究就采用了经验回放和目标网络的方法改善学习稳定性。

2.3 BP神经网络结构与奖励函数设定

在强化学习中，奖励函数的设计将直接影响学习效果的好坏。通常，奖励函数对应着人对某项任务的描述，通过奖励函数的设计即可将任务的先验知识成功融入学习中。在USV路径规划中，本次研究在致力于使USV尽快到达目标位置的同时，还期望在航行过程中能够保证安全，并避免与障碍物相撞。为此本文将奖励函数分为3种，具体就是：USV与目标位置的距离进行奖励、USV到达目标位置进行奖励、USV与障碍物相撞进行惩罚。文中，可将奖励函数写为如下数学形式：

(13)

从量级上看，第一、二种的奖励值比第三的奖励值大。因为对于USV避障任务来说，其主要目标就是避开障碍物且达到目标位置，而不是仅仅缩短USV与目标位置的距离。加入此项的原因在于，如果仅仅对USV达到目标位置和USV撞上障碍物进行奖励和惩罚，那么在运动过程中将会有大量的步骤所得奖励皆会为0，这会使得USV在大部分情况下不会启用改进策略，学习效率偏低。而加入该项奖励相当于加入了人对此项任务的先验知识，使得USV在学习和探索时更有效率。综上可得，本文研发算法的整体设计流程如图1所示。

图1 整体流程图

由图1可见，对流程中各步骤可做阐释解析如下。

Step1初始化经验回放存储区D。

Step2初始化Q网络，状态、动作赋初始值。

Step3随机选择动作at，得到当前奖励rt，下一时刻状态st+1，将(st,at,rt,st+1)存入D。

Step4从存储区D中随机采样一批数据(st,at,rt,st+1)进行训练。当USV达到目标位置，或超过每轮最大时间时的状态都认为是最终状态。

Step5如果st+1不是最终状态，则返回Step3；若st+1是最终状态，则更新Q网络参数，并返回Step3。重复一定轮数后，算法结束。

D为经验回放存储区，用来存储USV航行过程，并采集训练样本。经验回放的存在使得每次训练时的多个样本在时间上不是连续的，从而最小化样本之间的相关性，而且也增强了样本的稳定性和准确性。

3 实验仿真

为了检验本文研发设计的路径规划算法性能，本文在Matlab2014a软件上进行仿真实验。在实验中，仿真环境为20*20的区域，折扣因子γ取值为0.9，存储区D大小设为40 000，循环次数1 000，神经网络第一层有64个神经元，第二层有32个神经元。在训练的每一轮中，每当USV撞到障碍物或USV到达目标位置时，该轮都立即结束，并返回一个奖励。

为验证本文方法的准确性，将采用文献[16]中的迷宫地形来构建实验，但是由于文献[16]中的迷宫地形偏于简单，本文将设计3种不同地形来进行算法的比较，图2为复杂水域地形，图3为简易同心圆迷宫地形，图4为复杂迷宫地形。对本文改进算法与传统Q学习算法在以上地形进行仿真，由路径图可以看出，蓝色代表的改进算法路线相比传统Q学习算法仿真的路线，路径长度更短，更加简捷。由标准误差图可以看出，改进算法比传统Q学习算法提前三分之一进入收敛稳定状态。

(a)路径仿真图

(b)误差分析图

图2复杂水域地形仿真

Fig.2Mapofcomplexwaterterrainsimulation

(a)路径仿真图

(b)误差分析图

(a)路径仿真图

(b)误差分析图

在前述基础上，再以临安东湖水域实际环境背景为例进行实验仿真。从图5(a)中看出，USV在仿真过程中并未出现与障碍物相撞且路径规划过程简单、且快捷。图5(b)为标准误差曲线。由图5可以看出，在训练次数达到56次时，曲线趋于平稳，说明已经大致规划出一条安全快捷的整体路线，此时在多数情况下USV都能避开障碍物到达目标位置。由此可以推出如下结论，基于BP神经网络的改进Q学习算法比传统Q学习算法，学习收敛速度更快，路径更优化。

(a)路径仿真图

(b)误差分析图

4 结束语

本文用强化学习的方法解决水质监测无人船在未知水域进行水质监测时自主导航路径规划问题，通过BP神经网络拟合Q函数，在训练后即能根据当前环境中障碍物的实时信息做出正确决策。仿真结果表明，该方法能够使水质监测无人船在未知环境根据不同的状态规划出可行路径，决策时间短、路线更优化，而且能够满足在线规划的实时性要求，从而克服传统Q学习路径规划方法计算量大、收敛速度慢的缺点，能在第一时间实现问题水域的有效监测。