基于增強(qiáng)拓?fù)渖窠?jīng)演化強(qiáng)化學(xué)習(xí)的水面無人艇局部路徑規(guī)劃

王寶仁, 韓婷婷, 王 凱

(山東科技大學(xué)機(jī)械電子工程學(xué)院，青島 266510)

水面無人艇(unmanned surface vessel, USV)是一種能在水面上獨(dú)立航行的小型化、無人智能平臺(tái)，其在軍事科技和智能交通領(lǐng)域都發(fā)揮著重要的作用[1-2]。USV的局部路徑規(guī)劃問題是當(dāng)前研究的熱點(diǎn)，中外學(xué)者針對(duì)船舶自主避碰與局部路徑規(guī)劃問題提出了很多觀點(diǎn)和解決方案。目前，前人多采用模糊邏輯算法或人工勢場算法進(jìn)行局部路徑規(guī)劃。王敏捷等[3]將模糊算法與近域圖(ND)法相結(jié)合，提高了USV角度和速度控制的平滑性，進(jìn)而提高了USV在復(fù)雜環(huán)境下的適應(yīng)性；徐小強(qiáng)等[4]改進(jìn)了經(jīng)典人工勢場法，優(yōu)化了距離及時(shí)間，并利用YimaEnc電子海圖仿真平臺(tái)進(jìn)行了仿真驗(yàn)證；Wu等[5]利用人工勢場-蟻群優(yōu)化(APF-ACO)算法及基于激光雷達(dá)的多層避障框架，改善了傳統(tǒng)方法在USV導(dǎo)航時(shí)對(duì)障礙物檢測的精度。 模糊邏輯算法可以便捷地通過模糊規(guī)則對(duì)USV進(jìn)行操控且魯棒性較高，但模糊邏輯算法存在模糊規(guī)則和隸屬度函數(shù)均由經(jīng)驗(yàn)給出、控制精較低的問題[6]，因此往往不能滿足控制精度要求。對(duì)于人工勢場算法，雖其結(jié)構(gòu)簡單、路徑平滑，但其存在局部極小點(diǎn)問題，導(dǎo)致路徑規(guī)劃失敗[7]。

增強(qiáng)拓?fù)渖窠?jīng)演化(neuroevolution of augmenting topologies, NEAT)是一種人工神經(jīng)網(wǎng)絡(luò)進(jìn)化算法，具體來說是結(jié)合神經(jīng)網(wǎng)絡(luò)算法和遺傳算法的一種強(qiáng)化學(xué)習(xí)方法[8]?；诖?，對(duì)USV路徑規(guī)劃問題進(jìn)行了數(shù)學(xué)建模，并提出了基于NEAT算法的USV局部路徑規(guī)劃方法，仿真對(duì)比本文方法與傳統(tǒng)的模糊邏輯算法、人工勢場算法，在路徑點(diǎn)數(shù)目和魯棒性方面。

1 USV局部路徑規(guī)劃數(shù)學(xué)模型

USV的局部路徑規(guī)劃如圖1所示，USV需要從起始點(diǎn)(x0,y0)到達(dá)指定目標(biāo)點(diǎn)(xq,yq)，并根據(jù)附近的未知障礙物信息實(shí)時(shí)地對(duì)USV進(jìn)行操控。將USV質(zhì)點(diǎn)化，(xi,yi)表示第i個(gè)路徑點(diǎn)的坐標(biāo)值。

圖1 USV的局部路徑規(guī)劃Fig.1 Schematic diagram of partial path planning of the USV

USV從此時(shí)的路徑點(diǎn)(xi,yi)到下一個(gè)路徑點(diǎn)(xi+1,yi+1)的遞推關(guān)系為

(1)

圖2 USV環(huán)境探測示意圖Fig.2 Schematic diagram of the USV environment detection

式(1)中:

ψi=ψi-1+Δψi

(2)

式(2)中:ψ為USV在第i個(gè)路徑點(diǎn)的航向角;vi為USV在第i個(gè)路徑點(diǎn)的速度;Δψi為航向角變化量;T為每個(gè)路徑點(diǎn)間隔的時(shí)間周期。航向角變化量Δψi和速度vi共同作為系統(tǒng)的輸出，由此可計(jì)算得出下一個(gè)路徑點(diǎn)。

USV環(huán)境探測示意圖如圖2所示，USV五個(gè)方向上的聲吶傳感器獲得的距離信息D={dl2,dl1,dc,dr1,dr2}。設(shè)定探測的極限距離為dmax。若某方向上的聲吶傳感器未探測到障礙物，則該方向上距離信息值為dmax。

對(duì)于路徑的優(yōu)化問題，目的在于減少USV成功到達(dá)目標(biāo)點(diǎn)時(shí)路徑點(diǎn)的總數(shù)p，故設(shè)定目標(biāo)函數(shù)為

minf=p

(3)

約束條件為

0≤vi≤vmax,i=0,1,…,p

(4)

|Δψi|≤Δψlim,i=0,1,…,p-1

(5)

式中:vmax為速度上限；Δψlim為航向角變化量極限值。

2 基于NEAT強(qiáng)化學(xué)習(xí)的USV局部路徑規(guī)劃算法設(shè)計(jì)

2.1 NEAT強(qiáng)化學(xué)習(xí)算法概述及實(shí)現(xiàn)

NEAT是一種利用遺傳算法(GA)的思想進(jìn)化人工神經(jīng)網(wǎng)絡(luò)的算法[9-10]。傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)演化算法在網(wǎng)絡(luò)演化開始前，必須確定網(wǎng)絡(luò)的結(jié)構(gòu)，通過訓(xùn)練優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)的權(quán)重。NEAT對(duì)比傳統(tǒng)神經(jīng)網(wǎng)絡(luò)演化算法不僅對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的權(quán)重進(jìn)行優(yōu)化，同時(shí)也對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行優(yōu)化，這樣就保證了演化得到的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)最簡。NEAT算法借助于GA，所以算法結(jié)構(gòu)也與GA類似。首先需要對(duì)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行基因的編碼操作，之后再經(jīng)過基因的變異與交叉，得到新一代個(gè)體，最后利用適應(yīng)度函數(shù)計(jì)算適應(yīng)度并淘汰部分種群。

為了便于神經(jīng)網(wǎng)絡(luò)間基因的雜交，基因編碼采用網(wǎng)絡(luò)連接的線性化表示，每個(gè)基因編碼都有與之一一對(duì)應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)?；蚓幋a包含節(jié)點(diǎn)信息和連接信息，節(jié)點(diǎn)信息主要包括節(jié)點(diǎn)編號(hào)及類型，連接信息主要包括連接編號(hào)、連接的起始節(jié)點(diǎn)、連接的終止節(jié)點(diǎn)、連接的權(quán)重、標(biāo)志位，其中標(biāo)志位表示此連接是否有效，EN表示有效，DIC表示無效。圖3為基因編碼實(shí)現(xiàn)的示例。

圖3 基因編碼的實(shí)現(xiàn)Fig.3 The implementation of gene coding

基因的變異包括節(jié)點(diǎn)的增加或移除、連接的增加或移除兩種形式。對(duì)于增加節(jié)點(diǎn)或連接，首先對(duì)新生成的節(jié)點(diǎn)或連接進(jìn)行編號(hào)，同時(shí)賦值連接權(quán)重為符合給定正態(tài)分布的隨機(jī)數(shù)。移除操作是利用標(biāo)志位來實(shí)現(xiàn)的，當(dāng)標(biāo)志位以一定概率由有效變?yōu)闊o效時(shí)，對(duì)應(yīng)連接被移除。圖4為基因突變實(shí)現(xiàn)的示例。

圖4 基因變異的實(shí)現(xiàn)Fig.4 The realization of genetic variation

基因的交叉是通過父代基因編碼的組合產(chǎn)生新的基因編碼的過程。由于連接編號(hào)對(duì)應(yīng)唯一的連接情況，所以后代只需繼承父代的連接編號(hào)，就可以實(shí)現(xiàn)基因的交叉操作。圖5為基因交叉實(shí)現(xiàn)的示例。

圖5 基因交叉的實(shí)現(xiàn)Fig.5 The realization of gene crossover

新形成的個(gè)體會(huì)根據(jù)基因差別的大小區(qū)分為各個(gè)種群，競爭只存在于各個(gè)種群內(nèi)部，而不是整體進(jìn)行競爭。隨著進(jìn)化代數(shù)的增加種群數(shù)目會(huì)逐漸增多，NEAT規(guī)定一個(gè)種群進(jìn)化多代后，適應(yīng)度沒有提高則淘汰掉這個(gè)種群，除非這個(gè)種群包含適應(yīng)度最高的個(gè)體。

2.2 USV局部路徑規(guī)劃算法

應(yīng)用NEAT強(qiáng)化學(xué)習(xí)算法進(jìn)行USV局部路徑規(guī)劃，需要通過對(duì)多種情況下的地圖進(jìn)行訓(xùn)練，才能使神經(jīng)網(wǎng)絡(luò)得到進(jìn)化，以演化出能夠滿足路徑規(guī)劃要求的最優(yōu)神經(jīng)網(wǎng)絡(luò)。神經(jīng)網(wǎng)絡(luò)訓(xùn)練流程如圖6所示。具體步驟如下。

k表示地圖編號(hào);q表示訓(xùn)練集地圖總數(shù);u表示個(gè)體編號(hào);pop_size表示個(gè)體總數(shù);gen為進(jìn)化代數(shù)。圖6 神經(jīng)網(wǎng)絡(luò)訓(xùn)練流程圖Fig.6 Neural network training flow chart

(1)初始化參數(shù)并隨機(jī)生成神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。

(2)判斷是否為最后一個(gè)個(gè)體，若否進(jìn)行步驟(3)，若是則計(jì)算第gen代種群的最大適應(yīng)度及平均適應(yīng)度，然后再判斷是否滿足終止條件。終止條件包括適應(yīng)度達(dá)到設(shè)定閾值或進(jìn)化代數(shù)達(dá)到最大進(jìn)化代數(shù)，若是則結(jié)束并輸出最優(yōu)個(gè)體的信息，若否則通過遺傳算子生成新的神經(jīng)網(wǎng)絡(luò)和種群并淘汰某些個(gè)體，然后跳轉(zhuǎn)至步驟(2)，進(jìn)行下一代種群的訓(xùn)練，如此循環(huán)。

(3)判斷是否為最后一幅地圖，若否進(jìn)行步驟(4)，若是計(jì)算第u個(gè)個(gè)體的適應(yīng)度，然后跳轉(zhuǎn)至步驟(3)，進(jìn)行下一個(gè)個(gè)體的訓(xùn)練，如此循環(huán)。

(4)判斷是否達(dá)到目標(biāo)點(diǎn)或到達(dá)最大步數(shù)或發(fā)生碰撞，若否則進(jìn)行步驟(5)，若是則計(jì)算個(gè)體在單個(gè)地圖的獎(jiǎng)勵(lì)值并初始化位置信息，跳轉(zhuǎn)至步驟(4)，進(jìn)行下一幅地圖的訓(xùn)練，如此循環(huán)。

(5)判斷是否有障礙物，若否,則以最大速度沿直線向目標(biāo)點(diǎn)移動(dòng)并計(jì)算下一個(gè)路徑點(diǎn);若是,則由生成的神經(jīng)網(wǎng)絡(luò)計(jì)算速度量和角度變換量并計(jì)算下一個(gè)路徑點(diǎn)。然后跳轉(zhuǎn)至步驟(4)，如此循環(huán)。

2.3 適應(yīng)度函數(shù)的設(shè)定

適應(yīng)度的計(jì)算分兩步來進(jìn)行，首先計(jì)算個(gè)體在單個(gè)地圖的獎(jiǎng)勵(lì)值，當(dāng)個(gè)體在每個(gè)地圖都完成訓(xùn)練后，進(jìn)行個(gè)體的適應(yīng)度計(jì)算。個(gè)體在單個(gè)地圖k的獎(jiǎng)勵(lì)值Rk在個(gè)體結(jié)束單個(gè)地圖訓(xùn)練時(shí)進(jìn)行計(jì)算。結(jié)束條件分別為USV成功到達(dá)目標(biāo)點(diǎn)即(xp,yp)=(xq,yq)、發(fā)生碰撞即USV所有距離信息的最小值min{dl2,dl1,dc,dr1,dr2}小于安全距離dlim、達(dá)到最大步數(shù)pmax。Rk計(jì)算公式為

(6)

式(6)中:d為單個(gè)地圖訓(xùn)練結(jié)束時(shí)的位置(xp,yp)與目標(biāo)點(diǎn)(xq,yq)之間的距離；Cd為距離常數(shù)；Cp為步數(shù)常數(shù)。式(6)將獎(jiǎng)勵(lì)計(jì)算分為兩種情況并保證到達(dá)目標(biāo)點(diǎn)時(shí)的獎(jiǎng)勵(lì)高于未達(dá)到，當(dāng)未到達(dá)目標(biāo)點(diǎn)時(shí)獎(jiǎng)勵(lì)通過距目標(biāo)點(diǎn)的距離計(jì)算，距離越近獎(jiǎng)勵(lì)越高；當(dāng)達(dá)目標(biāo)點(diǎn)時(shí)獎(jiǎng)勵(lì)通過步數(shù)計(jì)算，步數(shù)越少獎(jiǎng)勵(lì)越高，這與給出的目標(biāo)函數(shù)[式(3)]相符。

對(duì)于個(gè)體的適應(yīng)度計(jì)算，設(shè)定適應(yīng)函數(shù)為個(gè)體在各個(gè)地圖獎(jiǎng)勵(lì)值的平均數(shù)除以2。根據(jù)地圖選擇合適的Cd與Cp可以將適應(yīng)度的值限定在0～1，適應(yīng)度函數(shù)計(jì)算公式為

(7)

2.4 神經(jīng)網(wǎng)絡(luò)參數(shù)設(shè)定

根據(jù)NEAT算法的設(shè)定，需要給出初始的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)開始進(jìn)化。初始神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖7所示，設(shè)定初始網(wǎng)絡(luò)結(jié)構(gòu)為無隱藏層節(jié)點(diǎn)的全連接結(jié)構(gòu)，神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的輸入量包括距離信息D={dl2,dl1,dc,dr1,dr2}和USV運(yùn)動(dòng)方向和目標(biāo)方向的夾角θ。為了到達(dá)更好的訓(xùn)練效果，對(duì)輸入量進(jìn)行歸一化處理，使得輸入值在[0,1]。轉(zhuǎn)換公式為

(8)

(9)

圖7 初始神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)Fig.7 Initial neural network structure

神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的輸出層包括速度值信號(hào)Svi與航向角變換量量信號(hào)SΔψi兩個(gè)節(jié)點(diǎn)。激勵(lì)函數(shù)采用sigmoid函數(shù)，通過激勵(lì)函數(shù)，輸出層節(jié)點(diǎn)的值被限定在[0,1]，再通過區(qū)間變換公式得到最終的速度vi與航向角變換量Δψi。區(qū)間變換公式為

vi=vmaxSvi

(10)

Δψi=Δψlim(2SΔψi-1)

(11)

通過變換，vi的范圍為[0,vmax]，Δψi的范圍為[-Δψlim,Δψlim]，與約束條件中的式(4)和式(5)相符。

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

3.1 仿真參數(shù)設(shè)定及NEAT強(qiáng)化學(xué)習(xí)訓(xùn)練

為驗(yàn)證所提出的局部路徑規(guī)劃方法的有效性和可行性，在PyCharm編譯環(huán)境中，利用Python3編程語言對(duì)問題的數(shù)學(xué)模型進(jìn)行模擬，借助sklearn機(jī)器學(xué)習(xí)庫實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)的搭建及訓(xùn)練過程，從而對(duì)提出的局部路徑規(guī)劃方法進(jìn)行計(jì)算機(jī)仿真實(shí)驗(yàn)。與其他機(jī)器學(xué)習(xí)算法相同，神經(jīng)網(wǎng)絡(luò)的演化需要一定數(shù)量的訓(xùn)練集樣本，研究設(shè)計(jì)了6幅地圖作為訓(xùn)練樣本，即訓(xùn)練集地圖總數(shù)q為6。設(shè)定起始點(diǎn)坐標(biāo)為(0,0)，目標(biāo)點(diǎn)坐標(biāo)為(10,10)。設(shè)定速度上限vmax為每周期0.25個(gè)單位長度，航向角變化量極限值Δψlim為0.3 rad，探測的極限距離dmax為1.5個(gè)單位長度。取安全距離dlim為0.2個(gè)單位長度，最大步數(shù)pmax為120，距離常數(shù)Cd為15，步數(shù)常數(shù)Cp為70。NEAT神經(jīng)網(wǎng)絡(luò)演化的主要參數(shù)如表1所示。

表1 NEAT主要演化參數(shù)Table 1 NEAT main evolution parameters

圖8為USV訓(xùn)練過程中最佳適應(yīng)度值與平均適應(yīng)度值的變化曲線。由圖8可以看出，初始種群的最佳適應(yīng)度僅為0.434，經(jīng)過50代的進(jìn)化最佳適應(yīng)度提高為0.926，平均適應(yīng)度也有很大提高。圖9為訓(xùn)練樣本地圖及最終演化結(jié)果。由圖9可以看出，最終演化出的最優(yōu)個(gè)體可以完成6幅地圖的路徑規(guī)劃任務(wù)，且路徑軌跡較為平滑。

3.2 測試及仿真結(jié)果分析

為了驗(yàn)證算法的魯棒性及路徑優(yōu)化的有效性，利用新地圖對(duì)訓(xùn)練得到的最優(yōu)個(gè)體進(jìn)行測試，并與USV路徑規(guī)劃中常用的模糊規(guī)則算法與人工勢場算法進(jìn)行對(duì)比實(shí)驗(yàn)，其中模糊規(guī)則算法參考文獻(xiàn)[3]提出的模糊ND算法、人工勢場算法使用文獻(xiàn)[4]提出的引力場函數(shù)和斥力場函數(shù)。仿真結(jié)果如圖10所示。圖10中人工勢場算法在復(fù)雜的環(huán)境中因陷入局部最小值區(qū)域而發(fā)生碰撞，導(dǎo)致路徑規(guī)劃失敗。NEAT算法和模糊規(guī)則算法均完成了路徑規(guī)劃，路徑點(diǎn)的個(gè)數(shù)分別為95和114。由圖10可以看出，對(duì)于這幅測試地圖NEAT算法路徑規(guī)劃的路徑點(diǎn)數(shù)較少，路徑軌跡較為平滑。為進(jìn)一步驗(yàn)證算法的有效性，使用其他的8幅地圖對(duì)上述3種算法進(jìn)行對(duì)比測試，測試結(jié)果如表2所示。由表2中數(shù)據(jù)可知，人工勢場算法的路徑點(diǎn)數(shù)較少但其魯棒性差，測試的8幅地圖中只完成了6幅地圖的路徑規(guī)劃任務(wù)。模糊規(guī)則算法的魯棒性較高，完成了所有地圖的路徑規(guī)劃任務(wù)，但其路徑點(diǎn)數(shù)較多。NEAT算法完成了所有測試地圖的路徑規(guī)劃任務(wù)且路徑點(diǎn)數(shù)優(yōu)于模糊規(guī)則算法、接近于人工勢場算法。通過對(duì)比驗(yàn)證了NEAT算法的魯棒性和路徑優(yōu)化的有效性。

圖8 適應(yīng)度變化曲線Fig.8 Fitness curve

圖9 訓(xùn)練樣本地圖及最終演化結(jié)果Fig.9 Training sample map and final evolution results

圖10 對(duì)比仿真結(jié)果Fig.10 Comparison of simulation results

表2 對(duì)比測試結(jié)果Table 2 Comparison test results

4 結(jié)論

對(duì)USV路徑規(guī)劃問題進(jìn)行了數(shù)學(xué)建模，設(shè)計(jì)了基于NEAT算法的USV局部路徑規(guī)劃方法，通過強(qiáng)化學(xué)習(xí)訓(xùn)練演化出能夠完成USV局部路徑規(guī)劃任務(wù)的最優(yōu)神經(jīng)網(wǎng)絡(luò)，通過仿真對(duì)比，驗(yàn)證了本文方法在路徑點(diǎn)數(shù)目和魯棒性方面，優(yōu)于傳統(tǒng)的模糊邏輯算法與人工勢場算法。

由于NEAT強(qiáng)化學(xué)習(xí)算法具有較強(qiáng)的可拓展性，可將風(fēng)浪或其他環(huán)境因素作為神經(jīng)網(wǎng)絡(luò)的輸入修改模型后重新對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，在今后的研究中將考慮這些因素使得仿真更接近于實(shí)際情況。