荊 緯， 李 浩， 咸琳濤， 劉 源， 郭忠文

(中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院， 山東 青島 266100)

自動(dòng)水面航行器(Autonomous surface vehicles)也稱為無(wú)人水面航行器(Unmanned surface vehicles)[1-2]，已迅速發(fā)展成為海洋科學(xué)技術(shù)的一個(gè)重要研究領(lǐng)域，對(duì)海洋工業(yè)具有重要意義。與傳統(tǒng)的船舶相比，ASV具有體型小、造價(jià)低以及多用途的特點(diǎn)[3]，這些特點(diǎn)使它可以獨(dú)立完成一些特殊任務(wù)。尤其是在一些長(zhǎng)期任務(wù)中，ASV低能耗的特點(diǎn)使它在燃料補(bǔ)給不方便的環(huán)境中仍能繼續(xù)工作。ASV的應(yīng)用十分廣泛[4-5]，不僅包括民用領(lǐng)域，還包括科學(xué)研究和國(guó)防安全。

根據(jù)為船提供的動(dòng)力來(lái)源，我們將ASV劃分為自動(dòng)航行船艇和自動(dòng)航行帆船[6]，船艇的動(dòng)力來(lái)源于發(fā)動(dòng)機(jī)，而帆船的動(dòng)力來(lái)源于自然的風(fēng)。在這兩者中，自動(dòng)航行船艇得到了更多研究者的關(guān)注，主要是因?yàn)榇Ь哂邪l(fā)動(dòng)機(jī)，所獲得的速度更快更穩(wěn)定；其次自動(dòng)航行船艇技術(shù)的實(shí)際應(yīng)用范圍更加廣泛，如小型的游艇、大型的客船甚至戰(zhàn)艦。

雖然自動(dòng)航行船艇具有很多的優(yōu)勢(shì)，但是卻不適合去完成一些長(zhǎng)期遠(yuǎn)海任務(wù)，因?yàn)楹叫兴枰哪茉囱a(bǔ)給是一個(gè)很大問(wèn)題。在遠(yuǎn)海補(bǔ)給困難的情況下，使用自動(dòng)航行帆船是一個(gè)很好的選擇。自動(dòng)航行帆船的動(dòng)力來(lái)源于風(fēng)，并且不消耗任何化石燃料更加環(huán)保。它可長(zhǎng)期處于工作狀態(tài)，隨時(shí)接受命令執(zhí)行航行或靜止，獨(dú)立完成一些長(zhǎng)期性的遠(yuǎn)海特殊任務(wù)。但是，對(duì)帆船的研究相較于船艇來(lái)說(shuō)更加復(fù)雜，因?yàn)闆Q定帆船航行的因素很多，海上的風(fēng)為船提供了動(dòng)力，風(fēng)的大小和方向決定了船在靜水中的速度。而在海面上，海流的速度和方向又會(huì)影響著船速。所以最終的帆船速度是由海面環(huán)境條件共同決定的。

在帆船的自動(dòng)導(dǎo)航領(lǐng)域，絕大部分的研究者都只考慮風(fēng)對(duì)自動(dòng)導(dǎo)航帆船路徑規(guī)劃的影響。其中，圖搜索算法應(yīng)用比較廣泛[7-8]，該算法將航行地圖分成網(wǎng)狀格，將地圖離散化。圖中的每個(gè)點(diǎn)都是帆船航行過(guò)程的潛在位置，并且每個(gè)點(diǎn)都有風(fēng)速和風(fēng)向的屬性，船在任意點(diǎn)都可以根據(jù)帆船的VPP模型[9]獲得帆船在此點(diǎn)的速度。當(dāng)船在兩點(diǎn)之間航行時(shí)，兩點(diǎn)的距離與兩點(diǎn)速度的平均值得到時(shí)間，最后利用傳統(tǒng)尋路算法(如A*和Dijkstra)獲得一條所用總時(shí)間最小的路徑。另一種是基于勢(shì)能的方法[10-11]，研究者將其分為全局勢(shì)能和局部勢(shì)能兩部分。全局勢(shì)能是在整張地圖上進(jìn)行分配，將目標(biāo)點(diǎn)設(shè)置為地圖中勢(shì)能最小的位置，而障礙物則具有很大的勢(shì)能；局部勢(shì)能是對(duì)帆船自身進(jìn)行分配，根據(jù)風(fēng)向在船周圍劃分了順風(fēng)禁行區(qū)、逆風(fēng)禁行區(qū)以及滯后區(qū)，其中滯后區(qū)是防止帆船頻繁的變換方向而導(dǎo)致傾覆。將勢(shì)能分配完畢后，帆船將朝向勢(shì)能最小的方向運(yùn)動(dòng)。除此之外，還有以模糊理論控制算法[12]為基礎(chǔ)，以先進(jìn)的高清相機(jī)探測(cè)[13]為基礎(chǔ)的方法來(lái)實(shí)現(xiàn)自動(dòng)航行帆船的路徑規(guī)劃。

而在自動(dòng)船艇的路徑規(guī)劃方面，往往忽略風(fēng)的作用，更關(guān)注海流及障礙物[14]對(duì)航行安全的影響。研究者使用了與帆船類似的圖搜索法[15]以及基于模糊理論[16]的方法。還有同樣強(qiáng)化學(xué)習(xí)[17-18]、AIS數(shù)據(jù)[19]、航向移動(dòng)窗[20]和遺傳進(jìn)化算法[21]。

總的來(lái)說(shuō)，在考慮各種因素下為自動(dòng)航行帆船找到最優(yōu)路徑是實(shí)現(xiàn)帆船自動(dòng)航行的關(guān)鍵問(wèn)題。本文提出了基于強(qiáng)化學(xué)習(xí)的帆船路徑規(guī)劃算法，綜合考慮了帆船內(nèi)在的模型因素以及外在海風(fēng)、海流以及障礙物的環(huán)境影響，為其規(guī)劃出一條合理的路徑。在眾多的機(jī)器學(xué)習(xí)方法中，我們將強(qiáng)化學(xué)習(xí)[22]用在了為帆船規(guī)劃路徑當(dāng)中。相較于傳統(tǒng)的尋路算法，本文算法不需要提前獲取全圖的路徑信息，它通過(guò)學(xué)習(xí)過(guò)程中自身輸入與環(huán)境的相互作用得到反饋，進(jìn)而確定下一步行動(dòng)，這更符合實(shí)際駕駛帆船航行的情況。

1 自動(dòng)航行帆船模型

眾所周知，帆船在海面航行的動(dòng)力來(lái)源于海風(fēng)和海流，這使得帆船成為蒸汽機(jī)之前傳統(tǒng)的水上最主要運(yùn)輸工具之一。與其它現(xiàn)代水上交通工具相比，帆船最大的優(yōu)勢(shì)正是其航行無(wú)需消耗化石燃料，這使得自動(dòng)航行帆船成為完成長(zhǎng)期無(wú)間斷工作的最佳選擇。對(duì)于帆船來(lái)說(shuō)，應(yīng)該優(yōu)先考慮的主要特征是風(fēng)和流，因?yàn)轱L(fēng)和流會(huì)代替了在船艇的螺旋槳，成為給帆船提供推進(jìn)力的主要?jiǎng)恿?。本章主要?duì)帆船的航行原理，以及本文使用的帆船運(yùn)動(dòng)模型進(jìn)行介紹，以獲得一種真實(shí)有效的帆船數(shù)值模擬方法

1.1 帆船的受力分析

帆船主要由船體、桅桿、帆、船舵和中央板五部分組成。如圖1所示，船體是帆船的主要部件，根據(jù)帆船型號(hào)的不同，船體的大小也不一樣；桅桿的作用是用來(lái)固定船帆；船帆用來(lái)接收海上的風(fēng)，正是因?yàn)榇氖芰?，才推?dòng)帆船前進(jìn)；舵的作用相當(dāng)于汽車的方向盤，用于控制帆船的航行方向；中央板用于維持帆船的姿態(tài)，防止帆船側(cè)翻。

圖1 帆船結(jié)構(gòu)圖

當(dāng)風(fēng)以非垂直方向吹過(guò)船帆時(shí)，由于船帆產(chǎn)生了一個(gè)弧形，船帆兩邊的氣體流動(dòng)速度出現(xiàn)差異。根據(jù)伯努利效應(yīng)[23]，這個(gè)風(fēng)速的差異會(huì)在船帆的兩側(cè)產(chǎn)生一個(gè)壓力差，這個(gè)壓力差產(chǎn)生了對(duì)船帆的推力。我們可以把風(fēng)分為三種，真實(shí)風(fēng)、航行風(fēng)和相對(duì)風(fēng)。真實(shí)風(fēng)是在陸地測(cè)試得到的風(fēng)速；航行風(fēng)的方向與帆船航行方向相反，等于船的航行速度；相對(duì)風(fēng)是真實(shí)風(fēng)和航行

風(fēng)的矢量合成。帆船受力分析如圖2所示。相對(duì)風(fēng)和航行方向之間的夾角是β。相對(duì)風(fēng)作用于船帆產(chǎn)生了氣動(dòng)升力FL和氣動(dòng)阻力FD兩部分，氣動(dòng)阻力FD與相對(duì)風(fēng)的方向相同，而氣動(dòng)升力FL垂直于FD。它們的大小取決于升力系數(shù)Cl和阻力系數(shù)Cd決定。Cl與船帆周圍動(dòng)態(tài)的風(fēng)壓所產(chǎn)生的升力有關(guān)；Cd量化了船帆通過(guò)風(fēng)的阻力。氣動(dòng)升力和氣動(dòng)阻力可以由式(1)求得：

圖2 帆船的受力分析

(1)

式中：ρ是空氣密度;S是船帆面積;Vr是相對(duì)風(fēng)的速度。進(jìn)一步，由氣動(dòng)升力和氣動(dòng)阻力的在船前進(jìn)方向上的分力得到帆船的推進(jìn)力：

F=FLsinβ-FDcosβ。

(2)

氣動(dòng)升力和氣動(dòng)阻力在垂直于帆船前進(jìn)方向的分量的合力構(gòu)成了側(cè)向力：

FS=FLcosβ+FDsinβ。

(3)

在逆風(fēng)行駛時(shí)，航行方向與船頭的指向是不同的，這個(gè)夾角γ稱為漂角。同時(shí)，由于帆船在水中行駛，水對(duì)帆船產(chǎn)生了相對(duì)運(yùn)動(dòng)方向的力FR和FS。

綜上所述，帆船的速度取決于真實(shí)風(fēng)速的大小和方向，當(dāng)帆船需要沿逆風(fēng)方向航行時(shí)，β趨近于0，推進(jìn)力F為負(fù)值，不能在逆風(fēng)時(shí)直線行駛，所以為了能夠順利地到達(dá)目的地，帆船必須要選擇“Z”字型路線。

1.2 帆船的運(yùn)動(dòng)模型

嚴(yán)格來(lái)說(shuō)，一艘在海上運(yùn)動(dòng)的船舶在空間當(dāng)中有6個(gè)自由度，其中平移運(yùn)動(dòng)3個(gè)：縱蕩、橫蕩、垂蕩，轉(zhuǎn)動(dòng)運(yùn)動(dòng)3個(gè)：橫搖、縱搖、艏搖(見(jiàn)圖3)。所以想要完整的表達(dá)運(yùn)動(dòng)狀態(tài)下船的狀態(tài)向量要包括以上6個(gè)維度以及船的位置等信息，復(fù)雜程度可想而知。

圖3 船的6個(gè)維度

在自動(dòng)航行船舶的路徑規(guī)劃問(wèn)題當(dāng)中，我們更關(guān)注的是在船體水平面上發(fā)生的運(yùn)動(dòng)情況，而船在垂直面上發(fā)生的位移變化或搖擺角度變化通常不考慮在內(nèi)，這主要是為了簡(jiǎn)化問(wèn)題，提高算法的效率。所以在研究船舶路徑規(guī)劃問(wèn)題時(shí)，平面運(yùn)動(dòng)模型更多的被用到。這樣也可以減少船舶的狀態(tài)向量維數(shù)，維數(shù)的增加會(huì)增加計(jì)算復(fù)雜度，所以為了再次提高算法效率，式(4)展示了本文在考慮海流影響下的帆船運(yùn)動(dòng)公式，在這樣的二維平面中研究路徑規(guī)劃問(wèn)題既有合理性又提高了算法效率。

(4)

式中：x和y是船舶在水平面上的位置坐標(biāo);V是船舶的航行速度;φ是帆船航向與水平x軸的夾角。Vcx(x,y)和Vcy(x,y)分別是海流在座標(biāo)點(diǎn)(x，y)處沿著x軸和y軸方向的速度。φ是船舶在海面上的角速度，代表了船舶航向變化的速率。由于帆船機(jī)構(gòu)中的中央版具有穩(wěn)定船體抵消橫向力的作用，并且在平穩(wěn)海面中海流速度不大的條件下，與帆船速度方向相垂直的海流速度將被忽略。

帆船不像普通的船舶有發(fā)動(dòng)機(jī)提供穩(wěn)定的速度，其速度來(lái)源于海風(fēng)。在將上述的船舶平面運(yùn)動(dòng)模型運(yùn)用到帆船之前，還需要考慮帆船的運(yùn)動(dòng)模型以得到帆船航行速度V。在帆船的運(yùn)動(dòng)模型研究中，速度預(yù)測(cè)程序(Velocity prediction programs,VPP)[9]是主要方式之一。這個(gè)程序方式是將帆船進(jìn)行水池實(shí)驗(yàn)，再通過(guò)風(fēng)洞測(cè)量將帆船的動(dòng)力特點(diǎn)參數(shù)化，最終可以輸出一個(gè)極坐標(biāo)圖，用來(lái)展示連續(xù)變化的真實(shí)風(fēng)速Vw、船速V和航行角度的關(guān)系。由于船體模型以及船帆大小的不同，型號(hào)不同的帆船具有不同的極坐標(biāo)。圖4是通過(guò)對(duì)J24帆船的測(cè)試數(shù)據(jù)所繪制的極坐標(biāo)圖，圖中顯示了在給定不同的真實(shí)風(fēng)速和風(fēng)向條件下，船在穩(wěn)定狀態(tài)所能達(dá)到的最大速度。兩側(cè)的淺藍(lán)色區(qū)域分別是逆風(fēng)禁行區(qū)和順風(fēng)禁行區(qū)，在順風(fēng)禁行區(qū)中理論上是可以航行的，但是出于安全考慮，帆船的航行通常會(huì)避開(kāi)完全順風(fēng)的方向。

圖4 帆船極坐標(biāo)圖

根據(jù)帆船的極坐標(biāo)圖，船體360°的范圍可以分成4個(gè)區(qū)域(見(jiàn)圖5)： (1)有效行駛區(qū)；(2)逆風(fēng)禁行區(qū)；(3)滯后區(qū)；(4)順風(fēng)禁行區(qū)。其中滯后區(qū)與有效行駛區(qū)的極坐標(biāo)速度曲線是對(duì)稱的，當(dāng)船航向位于逆風(fēng)和順風(fēng)區(qū)域時(shí)，兩側(cè)都是有效行駛區(qū)。設(shè)置滯后區(qū)的原因是當(dāng)需要進(jìn)行下一步路徑選擇時(shí)，應(yīng)盡量避免選擇這個(gè)區(qū)域以防止帆船因劇烈的轉(zhuǎn)向而導(dǎo)致發(fā)生傾覆等危險(xiǎn)情況。

圖5 帆船航行區(qū)域

2 基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃算法

強(qiáng)化學(xué)習(xí)(Reinforcement learning，也稱為增強(qiáng)學(xué)習(xí))是機(jī)器學(xué)習(xí)三大分支之一，它與另外兩類監(jiān)督學(xué)習(xí)、無(wú)監(jiān)督學(xué)習(xí)的主要區(qū)別在于強(qiáng)化學(xué)習(xí)是系統(tǒng)與環(huán)境進(jìn)行交互，以使選擇的行動(dòng)獲得的獎(jiǎng)勵(lì)最大。強(qiáng)化學(xué)習(xí)在路徑規(guī)劃領(lǐng)域主要應(yīng)用在室內(nèi)機(jī)器人[24]。

2.1 強(qiáng)化學(xué)習(xí)概況

強(qiáng)化學(xué)習(xí)算法主要由智能體(Agent)、狀態(tài)(State)、環(huán)境(Environment)、行動(dòng)(Action)以及獎(jiǎng)勵(lì)(Reward)組成。智能體也就是實(shí)施行動(dòng)的主體，所決定的行動(dòng)與環(huán)境進(jìn)行交互。環(huán)境是一個(gè)與智能體相互獨(dú)立的系統(tǒng)，它為智能體所實(shí)施的行動(dòng)提供反饋。狀態(tài)是智能體的內(nèi)在表達(dá)，使智能體可以用參數(shù)進(jìn)行表示。獎(jiǎng)勵(lì)是一個(gè)數(shù)值，用來(lái)表示所選擇的行動(dòng)在環(huán)境條件下是利還是弊。圖6展示了強(qiáng)化學(xué)習(xí)算法的流程圖。主體在狀態(tài)st下選擇了行動(dòng)at，經(jīng)過(guò)環(huán)境之后，反饋了獎(jiǎng)勵(lì)值rt+1，同時(shí)主體的狀態(tài)更新為st+1。

圖6 強(qiáng)化學(xué)習(xí)算法流程圖

所以在路徑規(guī)劃問(wèn)題里，強(qiáng)化學(xué)習(xí)可以用來(lái)找出一條最優(yōu)路徑。當(dāng)主體選擇了一個(gè)行動(dòng)獲得了環(huán)境反饋的獎(jiǎng)勵(lì)，重復(fù)這個(gè)過(guò)程使得主體選擇可以獲得最大獎(jiǎng)勵(lì)的行動(dòng)。強(qiáng)化學(xué)習(xí)也有很多的分支，本文使用的Q-learning算法屬于Off-Policy，其表達(dá)式為：

Q(S,A)←Q(S,A)+α[R+γmaxaQ(S′,a)-Q(S,A)]。

(5)

式中：行動(dòng)A表示在狀態(tài)S的所有行動(dòng)集合;a則表示

其中的一個(gè)具體動(dòng)作，它們之間的關(guān)系是：a∈A。α為學(xué)習(xí)率(Learning rate)；γ為折扣因子(Discount factor)；R是在狀態(tài)S時(shí)實(shí)施行動(dòng)a的獎(jiǎng)勵(lì)值；Q(S,A)是Q-learning的動(dòng)作價(jià)值函數(shù)，它是一個(gè)矩陣，代表了每個(gè)狀態(tài)下所有行動(dòng)所對(duì)應(yīng)的邏輯值，本文使用了python編程，其數(shù)值是通過(guò)Pandas庫(kù)中的”.loc”計(jì)算得到。根據(jù)式(5)可以看出，學(xué)習(xí)速率α越大，保留之前訓(xùn)練的效果就越少。折扣因子γ越大，maxaQ(S′,a)所起到的作用就越大。maxaQ(S′,a)可以看作是智能體記憶中的利益，它是智能體在狀態(tài)S時(shí)選擇能獲得最大Q值的動(dòng)作，同時(shí)使?fàn)顟B(tài)更新到S′。這樣智能體再次處于狀態(tài)S時(shí)會(huì)選擇正確的動(dòng)作繼續(xù)進(jìn)入這個(gè)S′。

相較于On-Policy的算法(如Sarsa算法)，Q-learning將優(yōu)化與探索分開(kāi)考慮。在優(yōu)化部分，Q-learning在每步選擇最大值Q的動(dòng)作本質(zhì)來(lái)說(shuō)是一種貪心行為。雖然每步都是得到最優(yōu)的結(jié)果，但是智能體在學(xué)習(xí)階段還是需要去探索其他動(dòng)作，因?yàn)槿绻悄荏w每次只選擇最貪心的動(dòng)作，那些一開(kāi)始沒(méi)有產(chǎn)生最優(yōu)Q值的動(dòng)作是永遠(yuǎn)無(wú)法被探索的。所以在探索部分，使用了ε-greedy策略，在概率為ε時(shí)隨機(jī)選擇一個(gè)非最優(yōu)的動(dòng)作而在概率1-ε時(shí)選擇最優(yōu)的動(dòng)作。所以Q-learning可以在保證探索的同時(shí)獲得最優(yōu)解。

2.2 問(wèn)題公式化

采用強(qiáng)化學(xué)習(xí)來(lái)解決自動(dòng)航行帆船的路徑規(guī)劃問(wèn)題，用帆船的平面運(yùn)動(dòng)模型來(lái)考慮環(huán)境對(duì)帆船的影響，需要對(duì)問(wèn)題里的各部分進(jìn)行公式化。

其次，結(jié)合Q-learning與路徑規(guī)劃問(wèn)題。根據(jù)上一節(jié)介紹的概況，“智能體”代表了帆船，而“環(huán)境”就是海洋上的海風(fēng)速度Vw和海流速度Vc。結(jié)合帆船的平面運(yùn)動(dòng)模型，帆船的狀態(tài)由帆船的位置和航向組成，其表達(dá)式s為：

s=[px,py,Dheading]。

(6)

式中：px和py是帆船在x和y坐標(biāo)軸上的坐標(biāo);Dheading是帆船此時(shí)的朝向。根據(jù)1.2節(jié)內(nèi)容，帆船為了在航行時(shí)為了保證安全會(huì)設(shè)置逆風(fēng)和順風(fēng)禁行區(qū)以及避免頻繁選擇滯后區(qū)。所以在規(guī)劃路徑時(shí)，大部分情況下帆船的行動(dòng)a會(huì)從以下5個(gè)之中選擇：沿航向直行、左偏45°、右偏45°、左偏90°和右偏90°。

對(duì)于帆船路徑規(guī)劃問(wèn)題，理想的結(jié)果是獲得一條所用時(shí)間最少的路徑。所以這里的獎(jiǎng)勵(lì)是一個(gè)負(fù)面獎(jiǎng)勵(lì)，也就是說(shuō)這個(gè)獎(jiǎng)勵(lì)值越小越好。為了獲得時(shí)間最少的路徑，我們將獎(jiǎng)勵(lì)r定義為帆船通過(guò)兩個(gè)節(jié)點(diǎn)間距離所用的時(shí)間倒數(shù)，其表達(dá)式t為：

t=2dij/(vi+vj);

(7)

r=1/t。

(8)

式中：i與j是地圖中相鄰的兩點(diǎn);dij是它們之間的歐式距離;vi和vj分別是帆船在i點(diǎn)與j點(diǎn)的速度;其大小是由該點(diǎn)的Vw和Vc決定的:

vi=vi(Vw,Vc);

(9)

vj=vj(Vw,Vc)。

(10)

當(dāng)帆船能夠完成從起始點(diǎn)到目標(biāo)點(diǎn)的航行，將此次航行中每段距離所需要的時(shí)間和定義為總獎(jiǎng)勵(lì)，于是要獲得所用時(shí)間最少的路徑即是獲得最大的總獎(jiǎng)勵(lì)。

在規(guī)劃最優(yōu)路徑的同時(shí)，要考慮對(duì)于障礙物的規(guī)避。海面上的障礙物主要包括海島以及礁石，如果船駛?cè)胝系K物的范圍有發(fā)生危險(xiǎn)的可能。對(duì)于已知位置的障礙物，如果帆船距離障礙物的距離dobstacle滿足一定條件，則給予帆船一個(gè)負(fù)的獎(jiǎng)勵(lì)N作為懲罰。與其相反若dgoal滿足一定條件，則給予一個(gè)正的獎(jiǎng)勵(lì)M，表示已經(jīng)到達(dá)了目標(biāo)點(diǎn)。

綜上，該算法的獎(jiǎng)勵(lì)表達(dá)式為：

(11)

在這里，將N的值設(shè)為-100，代表經(jīng)過(guò)障礙物所給予的懲罰；M值設(shè)為+100，代表此處就是目標(biāo)點(diǎn)。d1和d2是帆船到障礙物和目標(biāo)點(diǎn)的安全距離。使用Q-learning算法，在考慮海風(fēng)、海浪以及障礙物的條件下獲得一組行動(dòng)序列，這一組行動(dòng)可以實(shí)現(xiàn)帆船從起始點(diǎn)航行至目標(biāo)點(diǎn)用時(shí)最短，并且滿足了對(duì)未知路線探索的需要，防止陷入局部最優(yōu)解。帆船若到達(dá)障礙物或者跑出地圖邊界，路徑規(guī)劃都將停止并重新開(kāi)始規(guī)劃。本文設(shè)計(jì)的帆船的路徑規(guī)劃算法如算法1所示。

算法1 基于強(qiáng)化學(xué)習(xí)的帆船路徑規(guī)劃算法

輸入：網(wǎng)狀圖，包括起始點(diǎn)、目標(biāo)點(diǎn)以及障礙物位置，各區(qū)域Vw及Vc。

輸出：路徑圖。

1. 設(shè)置α、γ、ε值;

2. 反復(fù)初始化Q(S,A)，直到抵達(dá)目標(biāo)點(diǎn);

3. 對(duì)于每一次規(guī)劃路線執(zhí)行以下循環(huán)：

4. 初始化s；

5. 對(duì)于每一次的每一步執(zhí)行以下循環(huán)：

6. 用ε-greedy策略從狀態(tài)S中選則A；

7. 執(zhí)行A，利用船速極坐標(biāo)圖，使用式(7)至(11)得到獎(jiǎng)勵(lì)R(s,a)；

8. 執(zhí)行式(5)；

9.S←S’；

10. 直到dgoal

11. 直到路徑所用時(shí)間曲線收斂;

12. 從中找出最優(yōu)路徑。

3 仿真實(shí)驗(yàn)設(shè)計(jì)與分析

為了驗(yàn)證該算法，本文創(chuàng)建了一個(gè)海面環(huán)境離散網(wǎng)狀圖，對(duì)海面環(huán)境因素就行了仿真，并針對(duì)不同海風(fēng)、海流條件規(guī)劃J24帆船的航行路線。文獻(xiàn)[25]驗(yàn)證了在不同學(xué)習(xí)率與折扣因子的條件下對(duì)路徑規(guī)劃的影響，結(jié)果顯示學(xué)習(xí)率和折扣因子的數(shù)值較大時(shí)，可更快更穩(wěn)定的找到最佳路徑。于是通過(guò)對(duì)不同參數(shù)組合的實(shí)驗(yàn)結(jié)果進(jìn)行比較，本次實(shí)驗(yàn)將學(xué)習(xí)率和折扣因子設(shè)置為0.6和0.9，ε設(shè)置為0.2。本文同時(shí)對(duì)不同迭代次數(shù)的路徑規(guī)劃實(shí)驗(yàn)結(jié)果進(jìn)行了比較，由于使用了ε-greedy策略，其路徑所用時(shí)間與迭代次數(shù)的收斂是相對(duì)的，智能體總會(huì)有ε概率去選擇非最優(yōu)路線。最終發(fā)現(xiàn)在本文設(shè)置的參數(shù)條件下，迭代3 000次之內(nèi)都能夠找到時(shí)間最短的路線。

仿真實(shí)驗(yàn)地圖設(shè)置為10×10的網(wǎng)格圖，如圖7所示，帆船從左上角出發(fā)，黑色方塊代表障礙物，黃色圓形代表目標(biāo)點(diǎn)。圖中每一格的寬度L假定為10 n mile，路徑節(jié)點(diǎn)為每一個(gè)網(wǎng)格的中心點(diǎn)，在每一個(gè)網(wǎng)格中都包含著海風(fēng)和海流的矢量速度，考慮到真實(shí)情況下風(fēng)向時(shí)刻變化，在船速極坐標(biāo)圖中，風(fēng)向的范圍在±5°之內(nèi)。

圖7 仿真實(shí)驗(yàn)地圖

在考慮環(huán)境的影響情況下，首先當(dāng)風(fēng)向?yàn)闁|北風(fēng)時(shí)，以地圖中間為分界線，1≤y≤5的上半部分風(fēng)速為8 kn，Vcx=Vcy=-1.5；6≤y≤10的下半部分風(fēng)速為16 kn，Vcx=Vcy=2(見(jiàn)圖7)。使用本文算法所得路線結(jié)果見(jiàn)圖8，圖中4個(gè)結(jié)果分別為循環(huán)40、1 200、2 400和3 000次所得到的路徑，通過(guò)這些路徑所需要的時(shí)間(即分圖的標(biāo)題，下文同)分別為33.74、16.58、14.34和14.30 h ?？梢钥吹酵ㄟ^(guò)連續(xù)學(xué)習(xí)，帆船在不斷的尋找時(shí)間最短的最優(yōu)路線。由于考慮了風(fēng)向的變化，帆船所獲得的速度也在變化，這就造成了結(jié)果中在相同路徑條件下，時(shí)間不同的情況。

圖8 仿真實(shí)驗(yàn)結(jié)果

為了證明所獲得路線為最優(yōu)，這里與Dijkstra算法進(jìn)行比較。但是這類路徑規(guī)劃方法有個(gè)弊端，它需要提前獲取全圖所有路徑的權(quán)值，再?gòu)倪@些權(quán)值中找到權(quán)值累加最小的路線，在這里路徑的權(quán)值即為時(shí)間。但是這個(gè)權(quán)值用在對(duì)帆船路徑選擇時(shí)便出現(xiàn)了問(wèn)題，由于帆船得到的速度與當(dāng)前航向及風(fēng)向有關(guān)，所以對(duì)于圖中除起始點(diǎn)外的任意相鄰兩點(diǎn)xt和xt+1來(lái)說(shuō)，xt+1處的速度可以獲得，但是由于無(wú)法確定xt-1的位置也就無(wú)法知道當(dāng)時(shí)帆船的航向等信息，所以無(wú)法確定xt處的速度。為了解決這一問(wèn)題，在實(shí)驗(yàn)中將xt處的速度設(shè)置為從所有可到達(dá)xt位置方向速度的平均值，以此便可以提前得到仿真地圖中所有路線所需的權(quán)值。為了與之前實(shí)驗(yàn)中條件一致，速度的計(jì)算都考慮了海流的影響，風(fēng)向也同樣具有小范圍的變化性。最后使用Dijkstra算法找到的路線如圖9所示。起始點(diǎn)為序列“0”點(diǎn)，以此橫向計(jì)數(shù)，目標(biāo)點(diǎn)序列為“88”。則路線如圖10所示，可以發(fā)現(xiàn)與圖8用本文算法找出的路線是一樣的，但是由于時(shí)間的計(jì)算方法有一定的差別，所以總體時(shí)間不同。

圖9 Dijkstra算法路徑

圖10 Dijkstra算法路徑展示

總體上來(lái)說(shuō)，本文的路徑規(guī)劃算法可以為帆船找到最優(yōu)路線。并且考慮到實(shí)際航行情況，特別是帆船的航行更依賴于外界環(huán)境，而想要提前得到整個(gè)航行海域的環(huán)境狀態(tài)，再使用像Dijkstra這類傳統(tǒng)尋路算法進(jìn)行路徑規(guī)劃是極為困難的。相反，本文提出的基于強(qiáng)化學(xué)習(xí)的帆船路徑規(guī)劃算法不需要提前獲取全地圖的信息，通過(guò)逐漸學(xué)習(xí)選擇出最佳路線，更符合實(shí)際帆船航行情況。

在其它環(huán)境條件不變的條件下，改變海流的方向，即上半部分Vcx=Vcy=1.5，下半部分Vcx=Vcy=-2，所規(guī)劃路徑結(jié)果如圖11所示，循環(huán)次數(shù)分別為600、1 200、2 400和3 000次以及時(shí)間16.07、15.92、15.12和14.35 h。

圖11 逆向海流仿真實(shí)驗(yàn)結(jié)果

為了測(cè)試在逆風(fēng)(東南風(fēng))情況下的路徑情況，在浪速為0、風(fēng)向?yàn)槟骘L(fēng)的情況下在6×6的地圖中路徑結(jié)果見(jiàn)圖12所示，2張結(jié)果圖的次數(shù)分別為50和3 000次，時(shí)間為12.66和10.04 h。在逆風(fēng)條件下，帆船無(wú)法直接朝向目標(biāo)，所以需要選擇折線的方式移動(dòng)。

圖12 純逆風(fēng)情況下實(shí)驗(yàn)結(jié)果

最后，在逆風(fēng)(東南風(fēng))并且海流大小方向與第一個(gè)實(shí)驗(yàn)相同情況下，對(duì)路徑進(jìn)行規(guī)劃，結(jié)果見(jiàn)圖13，循環(huán)次數(shù)為600和3 000次，時(shí)間為20.18和18.16 h。

圖13 逆風(fēng)仿真實(shí)驗(yàn)結(jié)果

從所有實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，隨著循環(huán)次數(shù)的增加，所需要的航行時(shí)間都在減小，其航行路線也更加合理。并且根據(jù)不同的環(huán)境條件，所選擇的路線不同，符合帆船運(yùn)動(dòng)規(guī)律，可以證明本文算法對(duì)自動(dòng)帆船在復(fù)雜海面環(huán)境中的路徑規(guī)劃是有效的。

4 結(jié)語(yǔ)

本文針對(duì)帆船的自動(dòng)航行問(wèn)題進(jìn)行研究，分析了復(fù)雜海面環(huán)境與其航行的關(guān)系，綜合考慮了海風(fēng)、海流以及海面障礙物對(duì)自動(dòng)帆船路線的影響，同時(shí)考慮了帆船的運(yùn)動(dòng)模型，最后基于強(qiáng)化學(xué)習(xí)的方法，對(duì)學(xué)習(xí)過(guò)程進(jìn)行重新定義，通過(guò)學(xué)習(xí)使帆船面對(duì)不同環(huán)境條件做出最優(yōu)的選擇。最后的仿真結(jié)果和對(duì)比實(shí)驗(yàn)結(jié)果也表明該算法可以綜合考慮環(huán)境因素，為自動(dòng)航行帆船找到最優(yōu)路線。綜上所述，本文的創(chuàng)新點(diǎn)可歸納為：

(1)本文將強(qiáng)化學(xué)習(xí)引入了自動(dòng)帆船路徑規(guī)劃中，與傳統(tǒng)的帆船路徑規(guī)劃算法不同，不需要提前獲得全圖的信息，而是根據(jù)當(dāng)前狀態(tài)以及之后狀態(tài)確定路線，更符合實(shí)際情況。

(2)與基于強(qiáng)化學(xué)習(xí)自動(dòng)船艇路徑規(guī)劃不同，帆船所涉及的影響因素更多更復(fù)雜，航行速度是由自身模型和環(huán)境條件共同決定的，于是本文算法綜合參考了帆船運(yùn)動(dòng)模型以及船體平面運(yùn)動(dòng)模型，更符合帆船海面航行狀態(tài)。

(3)相較于其它路徑規(guī)劃方法對(duì)于海風(fēng)、海流、障礙物以及船體模型出現(xiàn)的“顧此失彼”問(wèn)題，本文算法全面考慮了上述海面環(huán)境因素以及帆船自身因素對(duì)路徑規(guī)劃的影響。