基于Q-Learning的無人駕駛船舶路徑規(guī)劃

，*，，

(大連海事大學(xué) a.航海動(dòng)態(tài)仿真與控制交通行業(yè)重點(diǎn)實(shí)驗(yàn)室；b.交通信息工程實(shí)驗(yàn)室，116026)

目前，在移動(dòng)機(jī)器人、無人機(jī)與無人艇領(lǐng)域中，有效的路徑規(guī)劃方法有人工勢(shì)場(chǎng)法[1]、粒子群算法[2]、神經(jīng)網(wǎng)絡(luò)法[3]與遺傳算法[4]等方法。這些方法通常需要假設(shè)完備的環(huán)境信息，然而在未知環(huán)境中無人駕駛系統(tǒng)很少有環(huán)境的先驗(yàn)知識(shí)，在大量的實(shí)際應(yīng)用中需要系統(tǒng)具有較強(qiáng)的自適應(yīng)不確定環(huán)境的能力，借助傳感器實(shí)時(shí)感知障礙物信息進(jìn)行在線規(guī)劃。目前，國(guó)內(nèi)外基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃方法分別在移動(dòng)機(jī)器人[5-6]、無人機(jī)[7]、無人車[8]和多智能體[9]等領(lǐng)域取得較好的成果，但在無人駕駛貨船智能航行與路徑規(guī)劃方面還處于初步研究階段。為實(shí)現(xiàn)未知環(huán)境先驗(yàn)知識(shí)情況下無人駕駛貨船自適應(yīng)路徑規(guī)劃，考慮將強(qiáng)化學(xué)習(xí)創(chuàng)新遷移應(yīng)用至無人駕駛貨船的路徑規(guī)劃領(lǐng)域，利用強(qiáng)化學(xué)習(xí)選擇策略完成無人駕駛貨船的避障并抵達(dá)目的地。

1 強(qiáng)化學(xué)習(xí)原理及模型基本要素

1.1 強(qiáng)化學(xué)習(xí)原理

強(qiáng)化學(xué)習(xí)又稱增強(qiáng)學(xué)習(xí)、再勵(lì)學(xué)習(xí)[10]。無人駕駛船舶在強(qiáng)化學(xué)習(xí)系統(tǒng)中通過與環(huán)境交互進(jìn)行在線學(xué)習(xí)，強(qiáng)化學(xué)習(xí)原理見圖1。

在強(qiáng)化學(xué)習(xí)中，無人能駕駛船舶根據(jù)當(dāng)前的狀態(tài)St選擇一個(gè)動(dòng)作At對(duì)環(huán)境造成影響，并接受到環(huán)境的反饋Rt(獎(jiǎng)或懲)，無人駕駛船舶再根據(jù)當(dāng)前的反饋信號(hào)和環(huán)境選擇下一個(gè)動(dòng)作，選擇的原則是使環(huán)境的正反饋概率最大。

在離散時(shí)間內(nèi)強(qiáng)化學(xué)習(xí)本質(zhì)上可以被視為馬爾科夫決策過程(Markov decision process，MDP),一個(gè)適用于無人駕駛船舶的馬爾科夫決策過程由下面的五元組定義：(S,A,Pa，Ra，γ)；S為無人駕駛船舶所處的有限狀態(tài)空間；A為無人駕駛船舶的動(dòng)作空間，即無人駕駛船舶在任何狀態(tài)下的所有行為空間的集合，例如左舵、右舵、加速、減速、跟船和停船等；Pa(s,s′)=P(s′|s,a)為一個(gè)條件概率，代表無人駕駛船舶在狀態(tài)s和動(dòng)作a下，到達(dá)下一個(gè)狀態(tài)s′的概率；Ra(s,s′)為一個(gè)激勵(lì)函數(shù)，代表了無人駕駛船舶在動(dòng)作a下，從狀態(tài)s到狀態(tài)s′所得到的激勵(lì)。γ∈(0,1)為激勵(lì)的衰減因子，下一個(gè)時(shí)刻的激勵(lì)便按照這個(gè)因子進(jìn)行衰減[11-12]。

目前常用的強(qiáng)化學(xué)習(xí)算法有Q-Learning、SARSA-Learning、TD-Learning和自適應(yīng)動(dòng)態(tài)規(guī)劃等[13]。這里采用Q-Learning在線學(xué)習(xí)算法，Q-Learning被視為一個(gè)增量式動(dòng)態(tài)規(guī)劃，通過優(yōu)化動(dòng)作函數(shù)Q(s,a)尋找最優(yōu)策略使得累計(jì)回報(bào)的期望最大。Q-Learning算法既可滿足系統(tǒng)在環(huán)境中的自適應(yīng)性，又可確保算法在學(xué)習(xí)過程中收斂[14]。

1.2 強(qiáng)化學(xué)習(xí)模型基本要素

在無人駕駛貨船的強(qiáng)化學(xué)習(xí)系統(tǒng)中，除了船舶自身，還有以下4大要素[15]。

1)環(huán)境模型。無人駕駛船舶環(huán)境模型包括無人駕駛船舶、障礙物、起始點(diǎn)、目標(biāo)點(diǎn)及傳感器。在環(huán)境模型中，無人駕駛船舶通過傳感器獲取障礙物與目標(biāo)點(diǎn)的信息，執(zhí)行搜索策略后模型會(huì)做出反饋以判斷動(dòng)作策略的獎(jiǎng)懲。

2)激勵(lì)函數(shù)R。激勵(lì)函數(shù)是在無人駕駛船舶做出動(dòng)作策略與環(huán)境進(jìn)行交互后由環(huán)境反饋的強(qiáng)化信號(hào)，用來評(píng)價(jià)該動(dòng)作策略的好壞，如果有助于實(shí)現(xiàn)目標(biāo)則會(huì)獎(jiǎng)勵(lì)，反之懲罰。

3)值函數(shù)Q(s)。值函數(shù)是指無人駕駛船舶在動(dòng)作搜索策略下，從當(dāng)前狀態(tài)轉(zhuǎn)移至目標(biāo)狀態(tài)過程中累積回報(bào)的數(shù)學(xué)期望。值函數(shù)Qπ(s,a)在實(shí)數(shù)范圍內(nèi)取值，并將決定無人駕駛系統(tǒng)的動(dòng)作搜索策略。

Qπ(s,a)=Epπ(t)[G(t)|s1=s,a1=a]

(1)

4)策略π。無人駕駛船舶的路徑規(guī)劃需要解決的問題就是為尋找一個(gè)最優(yōu)“策略”，使得回報(bào)最大，本質(zhì)上，策略就是無人駕駛船舶狀態(tài)S到無人駕駛船舶行為動(dòng)作A的映射，記為π:S→A。

2 模型建立

2.1 環(huán)境模型

基于python和pygame構(gòu)建二維仿真環(huán)境。在二維坐標(biāo)系中，每一個(gè)坐標(biāo)點(diǎn)對(duì)應(yīng)無人駕駛船舶的一個(gè)狀態(tài)，每個(gè)狀態(tài)均可映射到環(huán)境狀態(tài)集S中的每一個(gè)元素。仿真環(huán)境模型中，每個(gè)坐標(biāo)點(diǎn)存在兩種狀態(tài)值，分別是1和0。其中1代表的是可航行區(qū)域，在環(huán)境模型中顯示為白色區(qū)域；0代表著障礙物區(qū)域，在環(huán)境模型中顯示為黑色區(qū)域。仿真環(huán)境模型見圖2，仿真環(huán)境狀態(tài)大小為800×500的二維地圖，環(huán)境模型中仿真了靜態(tài)船舶、防波堤和港池岸基等障礙物。對(duì)于無人駕駛船舶來說，這些障礙物的位置信息未知。

2.2 動(dòng)作空間的表示

設(shè)定無人駕駛船舶的初始點(diǎn)和目標(biāo)點(diǎn)之后，在仿真過程中將無人駕駛船舶視為一個(gè)質(zhì)點(diǎn)。在真實(shí)的航行過程中無人駕駛船舶自主航行是連續(xù)的狀態(tài)，進(jìn)而需要將無人駕駛船舶的觀測(cè)行為O泛化為離散動(dòng)作A=Generalization(A′,O)。一般情況下，無人駕駛船舶的搜索動(dòng)作為上、下、左、右4個(gè)離散動(dòng)作，當(dāng)環(huán)境出現(xiàn)拐角時(shí)則增加對(duì)角線方向的搜索行為。

以無人駕駛船舶質(zhì)點(diǎn)為中心，定義無人駕駛船舶的實(shí)際動(dòng)作空間模型A為上、下、左、右、上左45°、上右45°、下左45°、下右45°8個(gè)離散動(dòng)作，矩陣為

A=[-1,1 0,1 1,1 -1,0 1,0

-1,-1 0，-1 1，-1]

(2)

2.3 激勵(lì)函數(shù)的設(shè)計(jì)

在無人駕駛船舶強(qiáng)化學(xué)習(xí)系統(tǒng)中，激勵(lì)函數(shù)扮演著重要的角色，可評(píng)價(jià)無人駕駛船舶行為決策的有效性及避障的安全性等，具有搜索導(dǎo)向性作用。對(duì)于無人駕駛船舶來說，激勵(lì)函數(shù)由安全性、舒適性及抵達(dá)目標(biāo)點(diǎn)組成。在設(shè)計(jì)激勵(lì)函數(shù)時(shí)，應(yīng)盡可能考慮以下要素[16]。

1) 接近目標(biāo)點(diǎn)。強(qiáng)化系統(tǒng)在未知環(huán)境情況下做出的搜索行為應(yīng)使無人駕駛船舶更加接近目標(biāo)點(diǎn)。更加接近激勵(lì)函數(shù)會(huì)選擇獎(jiǎng)賞，否則將懲罰：

(3)

2)安全性。在Q-Learning算法模型中，將無人駕駛船舶所處的未知環(huán)境劃分為N個(gè)狀態(tài)空間，其中分為安全狀態(tài)區(qū)域和障礙物區(qū)域，無人駕駛船舶強(qiáng)化學(xué)習(xí)系統(tǒng)應(yīng)在障礙物局部區(qū)域選取滿足船舶安全性的動(dòng)作搜索策略，并“早、清、大”地避開障礙物。因此，在激勵(lì)函數(shù)中，對(duì)接近障礙物的行為增加懲罰值，反之增加獎(jiǎng)勵(lì)值。

(4)

式中：No為無人駕駛船舶當(dāng)前狀態(tài)下需要考慮的障礙物數(shù)量；∨為符號(hào)“或”；(xo,yo)為障礙物位置；Z0為船舶航行安全會(huì)遇距離，和船舶尺度(船長(zhǎng)L)有關(guān)，船越長(zhǎng)或船型越大，所需要的安全會(huì)遇距離就越大。

由于Q-Learning算法中的環(huán)境狀態(tài)集和無人駕駛船舶動(dòng)作狀態(tài)均是有限的，而實(shí)際的無人駕駛船舶運(yùn)輸過程均是連續(xù)系統(tǒng)性事件，因此，將激勵(lì)函數(shù)泛化處理為非線性分段函數(shù)。

(5)

式中：s=0表示無人駕駛船舶與障礙物發(fā)生碰撞；s=1表示無人駕駛船舶在安全區(qū)域航行；dg(t)為t時(shí)刻無人駕駛船舶距離目標(biāo)點(diǎn)的距離；dg(t-1)為t-1時(shí)刻無人駕駛船舶距離目標(biāo)點(diǎn)的距離；do(t)為t時(shí)刻無人駕駛船舶距離障礙物距離；do(t-1)為t-1時(shí)刻無人駕駛船舶距離障礙物距離。

2.4 動(dòng)作選擇策略

(6)

3 仿真實(shí)驗(yàn)及結(jié)果分析

設(shè)定無人駕駛船舶的初始位置(128,416)和目標(biāo)點(diǎn)(685,36)，在實(shí)驗(yàn)迭代前期無人駕駛船舶分別在不同的時(shí)間步與障礙物發(fā)生碰撞，實(shí)驗(yàn)中發(fā)生碰撞后無人駕駛船舶將返回上一步并重新選擇動(dòng)作策略。

如圖3所示，初始迭代中，無人駕駛船舶在仿真環(huán)境中無法判斷誘惑區(qū)域以至于陷入仿真港池中的“陷阱”海域；在迭代100次之后系統(tǒng)逐漸規(guī)劃出有效路徑，但過程中多次出現(xiàn)碰撞障礙物現(xiàn)象且規(guī)劃路徑波動(dòng)較大；迭代200次～500次，碰撞現(xiàn)象逐漸減少且規(guī)劃路徑波動(dòng)減緩；在迭代1 000次有效地避讓所有的障礙物且規(guī)劃的路徑波動(dòng)較弱并逐漸穩(wěn)定；直到迭代第1 600次，隨機(jī)搜索的概率最小，強(qiáng)化學(xué)習(xí)系統(tǒng)規(guī)劃出最終的固定路徑，到達(dá)目標(biāo)點(diǎn)。

4 結(jié)論

無人駕駛船舶在與環(huán)境交互初期，對(duì)環(huán)境狀態(tài)信息了解過少，會(huì)發(fā)生碰撞及路徑規(guī)劃波動(dòng)較大等現(xiàn)象。隨著迭代次數(shù)的增加，無人駕駛船舶系統(tǒng)累計(jì)學(xué)習(xí)經(jīng)驗(yàn)，完成對(duì)環(huán)境的自適應(yīng)，最終成功規(guī)劃路徑并抵達(dá)目標(biāo)點(diǎn)。但是，如果需要強(qiáng)化學(xué)習(xí)真正能夠在無人駕駛的場(chǎng)景下應(yīng)用，強(qiáng)化學(xué)習(xí)算法還需要很多改進(jìn)。

1)基于馬爾科夫決策過程的Q-Learning算法能通過試錯(cuò)算法取得最優(yōu)路徑，但其收斂速度較慢，迭代次數(shù)較多。第一個(gè)改進(jìn)方向就是提高強(qiáng)化學(xué)習(xí)的自適應(yīng)能力，以達(dá)到只用少量的樣本進(jìn)行少量的迭代就能學(xué)習(xí)到正確的行為。

2)強(qiáng)化學(xué)習(xí)中的策略函數(shù)和值函數(shù)都是由深度神經(jīng)網(wǎng)絡(luò)表示的，而深度神經(jīng)網(wǎng)絡(luò)的可解釋性比較差，這一安全問題在無人駕駛貨船運(yùn)輸中不能被接受。第二個(gè)改進(jìn)方向就是提高模型的可解釋性。

3)在實(shí)際航行過程中，無人駕駛貨船的行為具有復(fù)雜的連續(xù)性，在本次仿真實(shí)驗(yàn)中僅做了簡(jiǎn)單的泛化處理，將無人駕駛船舶的駕駛行為劃分為上、下、左、右等8個(gè)動(dòng)作，第三個(gè)改進(jìn)的方向是增加模型的預(yù)測(cè)和“想象”的能力。