水質(zhì)監(jiān)測(cè)無(wú)人船路徑規(guī)劃方法研究

呂揚(yáng)民， 陸康麗， 王 梓

(浙江農(nóng)林大學(xué) 信息工程學(xué)院， 浙江 臨安 311300)

0 引 言

水質(zhì)監(jiān)測(cè)是水質(zhì)評(píng)價(jià)和預(yù)防水污染的主要方法。隨著工業(yè)廢水的增多，水體污染的問(wèn)題則引發(fā)高度關(guān)注，水污染動(dòng)態(tài)監(jiān)測(cè)的研究已然刻不容緩。但是因?yàn)閭鹘y(tǒng)的水質(zhì)監(jiān)測(cè)方法步驟繁多、并耗時(shí)不菲，而且獲取到的數(shù)據(jù)多樣性、準(zhǔn)確性也遠(yuǎn)遠(yuǎn)未能滿足決策的需求[1]。基于上述問(wèn)題，多種水質(zhì)監(jiān)測(cè)方法已陸續(xù)進(jìn)入學(xué)界視野。如曹立杰等人[2]提出通過(guò)建立傳感器網(wǎng)絡(luò)，得到較為精準(zhǔn)的水質(zhì)反演模型。田野等人[3]提出通過(guò)水質(zhì)模型對(duì)衛(wèi)星數(shù)據(jù)進(jìn)行反演，得到監(jiān)測(cè)水域的水質(zhì)參數(shù)分布圖。但是以上方法卻無(wú)法靈活地更換監(jiān)測(cè)水域，工程量大、且時(shí)效性欠佳，相較而言水質(zhì)監(jiān)測(cè)無(wú)人船體積小便于攜帶、監(jiān)測(cè)領(lǐng)域不受地形影響，能連續(xù)性原位進(jìn)行多項(xiàng)水質(zhì)參數(shù)監(jiān)測(cè)，使監(jiān)測(cè)結(jié)果更具有多樣性和準(zhǔn)確性。

無(wú)人駕駛船(Unmanned Surface Vehicle，USV)是一種能夠在未知水域環(huán)境下自主航行，并完成各種任務(wù)的水面運(yùn)動(dòng)平臺(tái)[4]，其研究?jī)?nèi)容主要涉及了自動(dòng)駕駛、自主避障、航行規(guī)劃和模式識(shí)別等熱門(mén)方向[5]。故而，目前已廣泛應(yīng)用于軍事領(lǐng)域的掃雷、偵察和反潛作戰(zhàn)等方面，同時(shí)還可以用于民用領(lǐng)域的水文氣象探測(cè)、環(huán)境監(jiān)測(cè)和水上搜救等專項(xiàng)服務(wù)中[6-8]。但由于水質(zhì)的流動(dòng)性，可以流經(jīng)多種復(fù)雜地形，如流經(jīng)洞穴時(shí)等，工作人員將無(wú)法探測(cè)；或又由于天氣的多變，如水域長(zhǎng)期處于多霧天氣，致使工作人員視線受阻，因而無(wú)法實(shí)時(shí)準(zhǔn)確地掌控操作USV。綜合上述分析后可知，就可以利用USV的自主航行到達(dá)目標(biāo)水位進(jìn)行檢測(cè)，而自主航行功能的實(shí)現(xiàn)即需用到本文下面擬將系統(tǒng)展開(kāi)研究的路徑規(guī)劃技術(shù)。

USV路徑規(guī)劃技術(shù)是指USV在作業(yè)水域內(nèi)，按照一定性能指標(biāo)(如路程最短、時(shí)間最短等)搜索得到一條從起點(diǎn)到目標(biāo)點(diǎn)的無(wú)碰路徑[9]，是USV導(dǎo)航技術(shù)中核心組成部分，同時(shí)也代表著USV智能化水準(zhǔn)。目前常用的規(guī)劃方法主要有粒子群算法[10]、A*算法[11]、可視圖法[12]、人工勢(shì)場(chǎng)法[13]、蟻群算法[14]等，但其方法多用于已知環(huán)境條件下。

當(dāng)前對(duì)于已知環(huán)境下的航跡規(guī)劃問(wèn)題已經(jīng)得到了較好的解決，但USV在未知水域作業(yè)執(zhí)行任務(wù)之前卻無(wú)法得到將要監(jiān)測(cè)水域的環(huán)境信息，無(wú)法通過(guò)基于已知環(huán)境信息的路徑規(guī)劃方法去求出USV航行路線[15]。此外，由于監(jiān)測(cè)水域環(huán)境復(fù)雜，傳感器信息眾多，系統(tǒng)的計(jì)算工作量大，致使USV存在實(shí)時(shí)性差、障礙物前振蕩等缺點(diǎn)。因此USV路徑規(guī)劃亟需研究算法簡(jiǎn)單、實(shí)時(shí)性強(qiáng)、且能控制系統(tǒng)中的不確定現(xiàn)象的路徑規(guī)劃算法，所以有必要引入具有自主學(xué)習(xí)能力的方法，其中基于Q學(xué)習(xí)算法的路徑規(guī)劃適合于在未知環(huán)境中的路徑規(guī)劃?，F(xiàn)階段研究中，郭娜[16]即在傳統(tǒng)Q學(xué)習(xí)算法基礎(chǔ)上，采用模擬退火方法進(jìn)行動(dòng)作選擇，解決探索與利用的平衡問(wèn)題。陳自立等人[17]提出采用遺傳算法建立新的Q值表以進(jìn)行靜態(tài)全局路徑規(guī)劃。董培方等人[18]把人工勢(shì)場(chǎng)法加入Q學(xué)習(xí)算法中，以引力勢(shì)場(chǎng)作為初始環(huán)境先驗(yàn)信息，再對(duì)環(huán)境逐層搜索，加快Q值迭代。

在此基礎(chǔ)上，本文提出了一種基于BP神經(jīng)網(wǎng)絡(luò)的Q學(xué)習(xí)強(qiáng)化學(xué)習(xí)路徑規(guī)劃算法，以神經(jīng)網(wǎng)絡(luò)擬合Q學(xué)習(xí)方法中的Q函數(shù)，使其能夠以連續(xù)的系統(tǒng)狀態(tài)作為輸入，并通過(guò)經(jīng)驗(yàn)回放和設(shè)置目標(biāo)網(wǎng)絡(luò)方法顯著提高網(wǎng)絡(luò)在訓(xùn)練過(guò)程中的收斂速度。經(jīng)過(guò)實(shí)驗(yàn)仿真，驗(yàn)證了本文所提出改進(jìn)路徑規(guī)劃方法的可行性。

1 問(wèn)題描述

USV路徑規(guī)劃的實(shí)質(zhì)是在一定標(biāo)準(zhǔn)下找出從初始位置到最終位置的最佳無(wú)碰撞安全路線。

USV路徑規(guī)劃研究中，首先需要建立一個(gè)可航行的環(huán)境模型。假設(shè)USV的航行環(huán)境為存在著一定數(shù)量的靜態(tài)障礙物的二維空間，采用柵格法對(duì)此區(qū)域進(jìn)行分割。將柵格區(qū)域的左下角設(shè)為空間坐標(biāo)系原點(diǎn)，水平向右為X軸，垂直向上為Y軸，劃分為n*n柵格坐標(biāo)系。如此一來(lái)，該問(wèn)題就簡(jiǎn)化為在靜態(tài)環(huán)境中尋找從開(kāi)始點(diǎn)到終點(diǎn)的無(wú)碰撞的最優(yōu)路徑。

設(shè)計(jì)中運(yùn)用神經(jīng)網(wǎng)絡(luò)擬合函數(shù)，輸入為USV的當(dāng)前狀態(tài)，USV的狀態(tài)是以當(dāng)前位置來(lái)表示，即空間坐標(biāo)s；USV路徑規(guī)劃的輸出是下一時(shí)刻的轉(zhuǎn)角，即動(dòng)作a。環(huán)境狀態(tài)信息則是以障礙物的位置和大小及目標(biāo)點(diǎn)的位置來(lái)表示，不同環(huán)境下障礙物出現(xiàn)的位置不同，目標(biāo)點(diǎn)的設(shè)定位置也不同。網(wǎng)絡(luò)的輸出個(gè)數(shù)為動(dòng)作空間的數(shù)量，每個(gè)輸出表示在當(dāng)前狀態(tài)下，采取對(duì)應(yīng)動(dòng)作后的期望獎(jiǎng)勵(lì)大小R(s)。對(duì)此內(nèi)容可研究詳述如下。

2 基于改進(jìn)Q學(xué)習(xí)的無(wú)人船路徑規(guī)劃方法

2.1 基于傳統(tǒng)Q學(xué)習(xí)的路徑規(guī)劃方法

Q學(xué)習(xí)是基于馬爾科夫決策過(guò)程 (Markov Decision Process) 來(lái)描述問(wèn)題，通過(guò)USV與環(huán)境的互動(dòng)積累經(jīng)驗(yàn)，同時(shí)不斷更新USV的策略，使其做出的決策能夠獲得更高的獎(jiǎng)勵(lì)。常用的強(qiáng)化學(xué)習(xí)方法包括模仿學(xué)習(xí)、Q學(xué)習(xí)及策略梯度法等。而且進(jìn)一步研究可知，Q學(xué)習(xí)方法不需要收集訓(xùn)練數(shù)據(jù)，且能夠生成決定性策略，因而適用于USV在未知水域進(jìn)行路徑規(guī)劃問(wèn)題。

馬爾科夫決策過(guò)程包含4個(gè)元素，分別是：S,A,Ps,a,R。其中，S表示USV所處的系統(tǒng)狀態(tài)集合，即USV在當(dāng)前的狀態(tài)及當(dāng)前環(huán)境的狀態(tài)，如障礙物的大小和位置；A表示USV所能采取的動(dòng)作集合，即USV轉(zhuǎn)動(dòng)的方向；Ps,a表示系統(tǒng)模型，即系統(tǒng)狀態(tài)轉(zhuǎn)移概率，P(s'|s,a)描述了在當(dāng)前狀態(tài)s下，執(zhí)行動(dòng)作a后，系統(tǒng)到達(dá)狀態(tài)s'的概率；R表示獎(jiǎng)勵(lì)函數(shù)，由當(dāng)前的狀態(tài)和所采取的動(dòng)作決定。把Q學(xué)習(xí)看成找到策略使綜合評(píng)價(jià)最大的增量式規(guī)劃，Q學(xué)習(xí)的設(shè)計(jì)思想是不考慮環(huán)境因素，而是直接優(yōu)化一個(gè)可迭代計(jì)算的Q函數(shù)，定義函數(shù)為在狀態(tài)st時(shí)執(zhí)行動(dòng)作at，且此后最優(yōu)動(dòng)作序列執(zhí)行時(shí)的折扣累計(jì)強(qiáng)化值，即：

(1)

其中，γ為折扣因子，其值0≤γ≤1；R(st)為獎(jiǎng)勵(lì)函數(shù)，其值為正數(shù)或者負(fù)數(shù)。

在初始階段學(xué)習(xí)中，Q值可能是不正確地反映了其所定義的策略，初始Q0(s,a)對(duì)于所有的狀態(tài)和動(dòng)作假定是給出的。這里，若設(shè)給定環(huán)境的狀態(tài)集合為s，USV可能的動(dòng)作集合A選擇性較多，數(shù)據(jù)量大，需要用到可觀的系統(tǒng)內(nèi)存空間，且無(wú)法被泛化。為了克服上述不足，對(duì)傳統(tǒng)Q學(xué)習(xí)進(jìn)行改進(jìn)，采用BP神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)Q值迭代，網(wǎng)絡(luò)的輸入對(duì)應(yīng)描述環(huán)境的狀態(tài)，網(wǎng)絡(luò)的輸出對(duì)應(yīng)每個(gè)動(dòng)作的Q值。

2.2 改進(jìn)的Q學(xué)習(xí)路徑規(guī)劃算法

Q(λ)算法借鑒了TD(λ)算法，通過(guò)回溯技術(shù)讓數(shù)據(jù)不斷地進(jìn)行傳遞，使得某一狀態(tài)的動(dòng)作決策也會(huì)受到其后續(xù)狀態(tài)的影響。如果未來(lái)某一決策π是失敗的，那么當(dāng)前的決策也要承擔(dān)相應(yīng)的懲罰，會(huì)把這種影響追加到當(dāng)前決策；如果未來(lái)某一決策π是正確的，那么當(dāng)前的決策也會(huì)得到相應(yīng)的獎(jiǎng)勵(lì)，同樣也會(huì)影響當(dāng)前決策。結(jié)合改進(jìn)后能夠提高算法的收斂速度，滿足學(xué)習(xí)的實(shí)用性。改進(jìn)的Q(λ)算法更新規(guī)則為：

(2)

(3)

另外，也可以把TD(0)誤差定義為：

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

(4)

在這一過(guò)程中，也應(yīng)用了折扣因子λ∈[0,1]，并以此對(duì)將來(lái)步驟中的TD誤差進(jìn)行折扣，其數(shù)學(xué)公式可表示為：

(5)

(6)

只要將來(lái)的TD誤差未知，前述的更新就無(wú)法進(jìn)行。但是，通過(guò)使用跟蹤跡就可以逐步求得其值。下面將ηt(s,a)定義為特征函數(shù)：在t時(shí)刻(s,a)發(fā)生，則返回1，否則返回0。為了簡(jiǎn)化，忽略學(xué)習(xí)效率，對(duì)每個(gè)(s,a)定義一個(gè)跟蹤跡et(s,a)，如式(7)所示：

(7)

那么在時(shí)刻t在線更新為：

δtet(s,a)]

(8)

強(qiáng)化學(xué)習(xí)希望使系統(tǒng)運(yùn)行時(shí)收獲的總體收益期望最大，即E(R(s0)+γR(s1)+γ2R(s2)+…)最大。為此需要找到一個(gè)最優(yōu)策略π，使得當(dāng)USV依照π進(jìn)行決策和運(yùn)動(dòng)時(shí)，獲得的總收益最大。通常，強(qiáng)化學(xué)習(xí)的目標(biāo)函數(shù)為以下其中之一：

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函數(shù)可以被迭代求出。

傳統(tǒng)Q學(xué)習(xí)算法中，Q函數(shù)是以表格的形式保存并更新，但在USV避障路徑規(guī)劃中，遭遇的障礙物可能出現(xiàn)在空間中任意位置，若以表格的形式Q函數(shù)將難以描述在連續(xù)空間中出現(xiàn)的障礙物。針對(duì)這一狀況，本文在Q學(xué)習(xí)基礎(chǔ)上，將展開(kāi)深度Q學(xué)習(xí)以BP神經(jīng)網(wǎng)絡(luò)來(lái)擬合Q函數(shù)，其輸入狀態(tài)s是連續(xù)變量。通常，以非線性函數(shù)擬合Q函數(shù)時(shí)學(xué)習(xí)過(guò)程難以收斂，對(duì)此研究就采用了經(jīng)驗(yàn)回放和目標(biāo)網(wǎng)絡(luò)的方法改善學(xué)習(xí)穩(wěn)定性。

2.3 BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)與獎(jiǎng)勵(lì)函數(shù)設(shè)定

在強(qiáng)化學(xué)習(xí)中，獎(jiǎng)勵(lì)函數(shù)的設(shè)計(jì)將直接影響學(xué)習(xí)效果的好壞。通常，獎(jiǎng)勵(lì)函數(shù)對(duì)應(yīng)著人對(duì)某項(xiàng)任務(wù)的描述，通過(guò)獎(jiǎng)勵(lì)函數(shù)的設(shè)計(jì)即可將任務(wù)的先驗(yàn)知識(shí)成功融入學(xué)習(xí)中。在USV路徑規(guī)劃中，本次研究在致力于使USV盡快到達(dá)目標(biāo)位置的同時(shí)，還期望在航行過(guò)程中能夠保證安全，并避免與障礙物相撞。為此本文將獎(jiǎng)勵(lì)函數(shù)分為3種，具體就是：USV與目標(biāo)位置的距離進(jìn)行獎(jiǎng)勵(lì)、USV到達(dá)目標(biāo)位置進(jìn)行獎(jiǎng)勵(lì)、USV與障礙物相撞進(jìn)行懲罰。文中，可將獎(jiǎng)勵(lì)函數(shù)寫(xiě)為如下數(shù)學(xué)形式：

(13)

從量級(jí)上看，第一、二種的獎(jiǎng)勵(lì)值比第三的獎(jiǎng)勵(lì)值大。因?yàn)閷?duì)于USV避障任務(wù)來(lái)說(shuō)，其主要目標(biāo)就是避開(kāi)障礙物且達(dá)到目標(biāo)位置，而不是僅僅縮短USV與目標(biāo)位置的距離。加入此項(xiàng)的原因在于，如果僅僅對(duì)USV達(dá)到目標(biāo)位置和USV撞上障礙物進(jìn)行獎(jiǎng)勵(lì)和懲罰，那么在運(yùn)動(dòng)過(guò)程中將會(huì)有大量的步驟所得獎(jiǎng)勵(lì)皆會(huì)為0，這會(huì)使得USV在大部分情況下不會(huì)啟用改進(jìn)策略，學(xué)習(xí)效率偏低。而加入該項(xiàng)獎(jiǎng)勵(lì)相當(dāng)于加入了人對(duì)此項(xiàng)任務(wù)的先驗(yàn)知識(shí)，使得USV在學(xué)習(xí)和探索時(shí)更有效率。綜上可得，本文研發(fā)算法的整體設(shè)計(jì)流程如圖1所示。

圖1 整體流程圖

由圖1可見(jiàn)，對(duì)流程中各步驟可做闡釋解析如下。

Step1初始化經(jīng)驗(yàn)回放存儲(chǔ)區(qū)D。

Step2初始化Q網(wǎng)絡(luò)，狀態(tài)、動(dòng)作賦初始值。

Step3隨機(jī)選擇動(dòng)作at，得到當(dāng)前獎(jiǎng)勵(lì)rt，下一時(shí)刻狀態(tài)st+1，將(st,at,rt,st+1)存入D。

Step4從存儲(chǔ)區(qū)D中隨機(jī)采樣一批數(shù)據(jù)(st,at,rt,st+1)進(jìn)行訓(xùn)練。當(dāng)USV達(dá)到目標(biāo)位置，或超過(guò)每輪最大時(shí)間時(shí)的狀態(tài)都認(rèn)為是最終狀態(tài)。

Step5如果st+1不是最終狀態(tài)，則返回Step3；若st+1是最終狀態(tài)，則更新Q網(wǎng)絡(luò)參數(shù)，并返回Step3。重復(fù)一定輪數(shù)后，算法結(jié)束。

D為經(jīng)驗(yàn)回放存儲(chǔ)區(qū)，用來(lái)存儲(chǔ)USV航行過(guò)程，并采集訓(xùn)練樣本。經(jīng)驗(yàn)回放的存在使得每次訓(xùn)練時(shí)的多個(gè)樣本在時(shí)間上不是連續(xù)的，從而最小化樣本之間的相關(guān)性，而且也增強(qiáng)了樣本的穩(wěn)定性和準(zhǔn)確性。

3 實(shí)驗(yàn)仿真

為了檢驗(yàn)本文研發(fā)設(shè)計(jì)的路徑規(guī)劃算法性能，本文在Matlab2014a軟件上進(jìn)行仿真實(shí)驗(yàn)。在實(shí)驗(yàn)中，仿真環(huán)境為20*20的區(qū)域，折扣因子γ取值為0.9，存儲(chǔ)區(qū)D大小設(shè)為40 000，循環(huán)次數(shù)1 000，神經(jīng)網(wǎng)絡(luò)第一層有64個(gè)神經(jīng)元，第二層有32個(gè)神經(jīng)元。在訓(xùn)練的每一輪中，每當(dāng)USV撞到障礙物或USV到達(dá)目標(biāo)位置時(shí)，該輪都立即結(jié)束，并返回一個(gè)獎(jiǎng)勵(lì)。

為驗(yàn)證本文方法的準(zhǔn)確性，將采用文獻(xiàn)[16]中的迷宮地形來(lái)構(gòu)建實(shí)驗(yàn)，但是由于文獻(xiàn)[16]中的迷宮地形偏于簡(jiǎn)單，本文將設(shè)計(jì)3種不同地形來(lái)進(jìn)行算法的比較，圖2為復(fù)雜水域地形，圖3為簡(jiǎn)易同心圓迷宮地形，圖4為復(fù)雜迷宮地形。對(duì)本文改進(jìn)算法與傳統(tǒng)Q學(xué)習(xí)算法在以上地形進(jìn)行仿真，由路徑圖可以看出，藍(lán)色代表的改進(jìn)算法路線相比傳統(tǒng)Q學(xué)習(xí)算法仿真的路線，路徑長(zhǎng)度更短，更加簡(jiǎn)捷。由標(biāo)準(zhǔn)誤差圖可以看出，改進(jìn)算法比傳統(tǒng)Q學(xué)習(xí)算法提前三分之一進(jìn)入收斂穩(wěn)定狀態(tài)。

(a)路徑仿真圖

(b)誤差分析圖

圖2復(fù)雜水域地形仿真

Fig.2Mapofcomplexwaterterrainsimulation

(a)路徑仿真圖

(b)誤差分析圖

(a)路徑仿真圖

(b)誤差分析圖

在前述基礎(chǔ)上，再以臨安東湖水域?qū)嶋H環(huán)境背景為例進(jìn)行實(shí)驗(yàn)仿真。從圖5(a)中看出，USV在仿真過(guò)程中并未出現(xiàn)與障礙物相撞且路徑規(guī)劃過(guò)程簡(jiǎn)單、且快捷。圖5(b)為標(biāo)準(zhǔn)誤差曲線。由圖5可以看出，在訓(xùn)練次數(shù)達(dá)到56次時(shí)，曲線趨于平穩(wěn)，說(shuō)明已經(jīng)大致規(guī)劃出一條安全快捷的整體路線，此時(shí)在多數(shù)情況下USV都能避開(kāi)障礙物到達(dá)目標(biāo)位置。由此可以推出如下結(jié)論，基于BP神經(jīng)網(wǎng)絡(luò)的改進(jìn)Q學(xué)習(xí)算法比傳統(tǒng)Q學(xué)習(xí)算法，學(xué)習(xí)收斂速度更快，路徑更優(yōu)化。

(a)路徑仿真圖

(b)誤差分析圖

4 結(jié)束語(yǔ)

本文用強(qiáng)化學(xué)習(xí)的方法解決水質(zhì)監(jiān)測(cè)無(wú)人船在未知水域進(jìn)行水質(zhì)監(jiān)測(cè)時(shí)自主導(dǎo)航路徑規(guī)劃問(wèn)題，通過(guò)BP神經(jīng)網(wǎng)絡(luò)擬合Q函數(shù)，在訓(xùn)練后即能根據(jù)當(dāng)前環(huán)境中障礙物的實(shí)時(shí)信息做出正確決策。仿真結(jié)果表明，該方法能夠使水質(zhì)監(jiān)測(cè)無(wú)人船在未知環(huán)境根據(jù)不同的狀態(tài)規(guī)劃出可行路徑，決策時(shí)間短、路線更優(yōu)化，而且能夠滿足在線規(guī)劃的實(shí)時(shí)性要求，從而克服傳統(tǒng)Q學(xué)習(xí)路徑規(guī)劃方法計(jì)算量大、收斂速度慢的缺點(diǎn)，能在第一時(shí)間實(shí)現(xiàn)問(wèn)題水域的有效監(jiān)測(cè)。