基于深度強(qiáng)化學(xué)習(xí)的無(wú)人船全覆蓋路徑規(guī)劃

宋大雷，呂昆嶺，陳小平，干文浩，曹江麗

（1.中國(guó)海洋大學(xué) 工程學(xué)院，山東 青島 266100；2.中國(guó)海洋大學(xué) 海洋高等研究院，山東 青島 266100；3.中國(guó)海洋大學(xué) 基礎(chǔ)教學(xué)中心，山東 青島 266100；4.中國(guó)船舶重工集團(tuán)公司第七〇九研究所，湖北 武漢 430205）

0 引言

因無(wú)人船具有智能化、效率高、適應(yīng)性強(qiáng)[1]等優(yōu)勢(shì)，故多采用無(wú)人船執(zhí)行任務(wù)。關(guān)于無(wú)人船島嶼區(qū)域全覆蓋路徑規(guī)劃任務(wù)的研究較少，海上區(qū)域廣闊且其中散布的島嶼通常較小、形狀不規(guī)則。在全覆蓋路徑規(guī)劃過(guò)程中，對(duì)大范圍無(wú)障礙區(qū)域可采用“之”字形搜索算法，效率高且算法簡(jiǎn)單，而針對(duì)不規(guī)則的島嶼區(qū)域，目前尚無(wú)有效算法解決全覆蓋路徑規(guī)劃問(wèn)題。

無(wú)人船全覆蓋路徑規(guī)劃算法的研究分為兩個(gè)步驟：一是對(duì)海域環(huán)境進(jìn)行建模，生成環(huán)境地圖；二是在已知環(huán)境地圖上進(jìn)行全覆蓋路徑規(guī)劃[2]。目前海域建模分析方法有很多，如可視圖法、沙盤模型法和柵格法等。柵格法直觀性強(qiáng)且建模簡(jiǎn)單、運(yùn)算量小，故任務(wù)海域建模采用柵格化方法[3]。

傳統(tǒng)的全覆蓋路徑規(guī)劃算法，如“之”字形規(guī)劃算法、啟發(fā)式算法、蟻群算法[4]、遺傳算法[5]、生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法等無(wú)法處理復(fù)雜環(huán)境信息，易陷入局部最優(yōu)[6]。深度強(qiáng)化學(xué)習(xí)算法既具備強(qiáng)化學(xué)習(xí)的決策性又具備深度學(xué)習(xí)的感知性[7]，有利于在復(fù)雜環(huán)境下進(jìn)行路徑規(guī)劃。Yuan等人使用GRU RNN網(wǎng)絡(luò)在基于網(wǎng)格的環(huán)境中規(guī)劃從A點(diǎn)到B點(diǎn)的路徑，同時(shí)避開障礙物[8]。Chen G等人提出雙深度Q網(wǎng)絡(luò)（DDQN）方法，將包含目標(biāo)位置和機(jī)器人速度的網(wǎng)格地圖直接映射到智能體的轉(zhuǎn)向命令中，從而規(guī)劃?rùn)C(jī)器人的運(yùn)動(dòng)路徑[9]。這些工作都集中在從A點(diǎn)到B點(diǎn)的簡(jiǎn)單任務(wù)上，也有學(xué)者應(yīng)用深度強(qiáng)化學(xué)習(xí)算法解決全覆蓋路徑規(guī)劃問(wèn)題。M.Theile等人提出DDQN方法，結(jié)合來(lái)自無(wú)人機(jī)地圖和相機(jī)的信息規(guī)劃一條從起點(diǎn)到目標(biāo)點(diǎn)的全覆蓋路徑，但這種方法側(cè)重對(duì)功率進(jìn)行限制且使用視覺(jué)觀測(cè)值作為輸入，訓(xùn)練速度慢[10]。S.Y.Luis等人使用DQN與DDQN方法訓(xùn)練智能體對(duì)湖泊進(jìn)行全覆蓋，但DDQN算法受參數(shù)影響較大，不穩(wěn)定[11]。Apuroop等人提出一種基于深度強(qiáng)化學(xué)習(xí)技術(shù)，利用Actor-Critic Experience Reply對(duì)具有長(zhǎng)短時(shí)記憶（LSTM）的卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，使蜂窩型鋪磚機(jī)器人對(duì)清潔區(qū)域進(jìn)行全覆蓋路徑規(guī)劃。該方法是對(duì)機(jī)器人形態(tài)進(jìn)行鏈?zhǔn)街貥?gòu)，從而達(dá)到目的[12]。

現(xiàn)階段使用的深度強(qiáng)化學(xué)習(xí)算法多側(cè)重于對(duì)無(wú)人船進(jìn)行端到端的路徑規(guī)劃或簡(jiǎn)單場(chǎng)景的全覆蓋路徑規(guī)劃，在復(fù)雜島嶼區(qū)域進(jìn)行全覆蓋路徑規(guī)劃的研究較少，故本文提出一種將“之”字形算法和基于深度強(qiáng)化學(xué)習(xí)的無(wú)人船島嶼區(qū)域全覆蓋路徑規(guī)劃算法框架相結(jié)合的混合算法。該算法框架通過(guò)調(diào)整無(wú)人船狀態(tài)和行為之間的映射關(guān)系，利用智能體與環(huán)境交互獲得的獎(jiǎng)勵(lì)來(lái)指導(dǎo)行為；用矢量觀測(cè)值代替視覺(jué)觀測(cè)值進(jìn)行地圖信息輸入，并加入內(nèi)在好奇心模塊解決訓(xùn)練速度慢、探索效率低、收斂速度慢的問(wèn)題，使智能體有效地探索環(huán)境以獲得最大獎(jiǎng)勵(lì)，從而規(guī)劃出滿足任務(wù)要求的最短路徑。

1 環(huán)境建模與任務(wù)分析

1.1 海域環(huán)境建模

環(huán)境建模是通過(guò)數(shù)學(xué)方法對(duì)海上環(huán)境進(jìn)行描述，文中將任務(wù)區(qū)域等分為大小相同的柵格，并對(duì)覆蓋區(qū)域、未覆蓋區(qū)域以及障礙物區(qū)域標(biāo)注不同的值加以區(qū)分，用于對(duì)環(huán)境進(jìn)行表示和規(guī)劃。

海上任務(wù)海域的柵格化劃分實(shí)例如圖1所示。柵格化過(guò)程如圖2所示。

定義無(wú)人船探測(cè)器開角長(zhǎng)度為柵格邊長(zhǎng)D，并且定義無(wú)人船任務(wù)區(qū)域?yàn)椋?/p>

無(wú)人船可達(dá)任務(wù)區(qū)域?yàn)椋?/p>

無(wú)人船不可達(dá)區(qū)域?yàn)椋?/p>

f(x,y)定義如下：

1.2 問(wèn)題求解輸入輸出空間

解決無(wú)人船全覆蓋路徑規(guī)劃問(wèn)題，需通過(guò)柵格化方法將任務(wù)區(qū)域劃分為二維柵格與地理坐標(biāo)點(diǎn)(x,y)一一對(duì)應(yīng)，由此任務(wù)地圖被轉(zhuǎn)化為二維數(shù)組G(x,y)，并將該數(shù)組作為智能體的矢量觀察值。定義G(x,y)為：

文獻(xiàn)[10]通過(guò)卷積網(wǎng)絡(luò)層將地圖式的空間信息傳遞給智能體，智能體可使用視覺(jué)觀察值進(jìn)行訓(xùn)練，可捕獲任意復(fù)雜的狀態(tài)，但相比矢量觀察訓(xùn)練，其效率低、速度慢，而且有時(shí)不能完全成功。故本文不直接將圖像作為輸入，而是將二維數(shù)據(jù)作為矢量觀測(cè)值進(jìn)行輸入，訓(xùn)練成功率高、速度快。

無(wú)人船的動(dòng)作輸出分別為前進(jìn)、后退、左移、右移。無(wú)人船在全覆蓋路徑規(guī)劃問(wèn)題求解過(guò)程中對(duì)不同外部事件的獎(jiǎng)勵(lì)規(guī)則如表1所示。

表1 無(wú)人船獎(jiǎng)勵(lì)規(guī)則

2 深度強(qiáng)化學(xué)習(xí)

深度強(qiáng)化學(xué)習(xí)算法是在Agent與Environment交互過(guò)程中，通過(guò)Reward的反饋不斷更新迭代從而獲得最優(yōu)Policy。

2.1 策略訓(xùn)練

文中設(shè)計(jì)的深度強(qiáng)化學(xué)習(xí)算法框架選用主流深度強(qiáng)化學(xué)習(xí)算法，即PPO、SAC算法。PPO算法穩(wěn)定性強(qiáng)、準(zhǔn)確性好，對(duì)大規(guī)模復(fù)雜問(wèn)題處理效果好，且對(duì)小批量信息數(shù)據(jù)進(jìn)行實(shí)時(shí)更新的同時(shí)，可以提高數(shù)據(jù)的利用率[13]；SAC算法的探索性能極佳，極易在各種情況下尋找最優(yōu)模式，且魯棒性強(qiáng)，故面對(duì)干擾時(shí)能夠更容易做出調(diào)整[14]。在全覆蓋路徑規(guī)劃過(guò)程中實(shí)現(xiàn)穩(wěn)定和快速的訓(xùn)練性能，主要依賴以下三個(gè)關(guān)鍵要素：

1）并行采樣策略。通過(guò)在30個(gè)環(huán)境中并行執(zhí)行策略部署模擬訓(xùn)練智能體，顯著加快數(shù)據(jù)收集過(guò)程，并可以利用并行化來(lái)增加收集的環(huán)境交互的多樣性。

2）泛化策略。為了使智能體能在不同的環(huán)境中具有魯棒性和可泛化性，設(shè)置了一組可隨時(shí)間改變的參數(shù)，通過(guò)對(duì)每個(gè)參數(shù)分配一個(gè)采樣器進(jìn)行泛化。

3）內(nèi)在好奇心模塊。旨在激勵(lì)智能體采取一定的行動(dòng)降低智能體，預(yù)測(cè)自身運(yùn)動(dòng)未來(lái)的不確定性，可提高探索效率，且對(duì)智能體未遇到的場(chǎng)景具有高度泛化能力。

2.2 PPO算法

傳統(tǒng)主流的深度強(qiáng)化學(xué)習(xí)算法是PPO算法，該算法可同時(shí)面向離散控制和連續(xù)控制[15]。PPO的核心思想是根據(jù)當(dāng)前策略和舊策略的概率比決定是否做clip，如果該比率超過(guò)ε就做clip[16]，此時(shí)神經(jīng)網(wǎng)絡(luò)就不再更新參數(shù)，通過(guò)該方法對(duì)目標(biāo)函數(shù)進(jìn)行約束。目標(biāo)函數(shù)公式如下[17]：

式中rt(θ)為新策略與舊策略的概率比例。式（6）可確保新策略與舊策略的偏差程度不會(huì)太大。

2.3 SAC算法

SAC算法具有很強(qiáng)的功能性和目的性，通過(guò)探索學(xué)習(xí)一個(gè)最優(yōu)路徑可使得累積獎(jiǎng)勵(lì)期望值最大；其次是熵最大化，SAC算法會(huì)使輸出的動(dòng)作盡可能最分散，使之不集中于一處。這樣可實(shí)現(xiàn)策略隨機(jī)化的結(jié)果[18]，公式如下：

式中：H(π( ·|st))為熵，表示當(dāng)前策略的隨機(jī)化程度；α為熵系數(shù)控制熵項(xiàng)相對(duì)回報(bào)的重要程度，從而對(duì)最優(yōu)策略的隨機(jī)程度起到?jīng)Q定作用；st為當(dāng)前環(huán)境的狀態(tài)信息；at為當(dāng)前狀態(tài)下做出的行為選擇。

2.4 內(nèi)在好奇心模塊

內(nèi)在好奇心模塊（Intrinsic Curiosity Module，ICM）是一種內(nèi)部獎(jiǎng)勵(lì)機(jī)制，即將智能體此時(shí)的狀態(tài)和執(zhí)行的動(dòng)作作為輸入，進(jìn)而預(yù)測(cè)未來(lái)的狀態(tài)，根據(jù)智能體對(duì)外界的好奇程度給予獎(jiǎng)勵(lì)，從而鼓勵(lì)智能體自身不斷探索，提高探索效率[18]。

ICM模塊如圖3所示。

ICM模塊共包含兩個(gè)模型：反向模型（Inverse Model）是通過(guò)特征提取層Φ提取出狀態(tài)st和st+1與動(dòng)作相關(guān)的特征向量Φ(st),Φ(st+1)，從而預(yù)測(cè)動(dòng)作值，預(yù)測(cè)出的動(dòng)作值與實(shí)際的動(dòng)作值越接近越好；正向模型（Forward Model）則將Φ(st)和at作為輸入，用以預(yù)測(cè)st+1的特征[19]，表示為Φ(st+1)，預(yù)測(cè)值與真實(shí)值相差越大，獲取的獎(jiǎng)勵(lì)越大，通過(guò)這種方式激勵(lì)智能體進(jìn)行冒險(xiǎn)，探索未知區(qū)域。

在外部獎(jiǎng)勵(lì)的基礎(chǔ)上，加入內(nèi)在好奇心獎(jiǎng)勵(lì)機(jī)制提高學(xué)習(xí)效率，優(yōu)化算法性能，故需重塑獎(jiǎng)勵(lì)公式。重塑前獎(jiǎng)勵(lì)公式為：R=Rb。Rb為Agent在探索環(huán)境的過(guò)程中所獲得的外部獎(jiǎng)勵(lì)，重塑后獎(jiǎng)勵(lì)公式為：R=λrti+Rb。引入ICM后的獎(jiǎng)勵(lì)架構(gòu)如圖4所示。

增加ICM模塊后，隨之增加一個(gè)好奇心獎(jiǎng)勵(lì)，即狀態(tài)s和動(dòng)作a進(jìn)入網(wǎng)絡(luò)后得到兩個(gè)獎(jiǎng)勵(lì)，分別為外界環(huán)境給的rb和ICM給的rti，使兩個(gè)獎(jiǎng)勵(lì)之和達(dá)到最大。

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

3.1 仿真試驗(yàn)

基于Unity3D平臺(tái)對(duì)無(wú)人船全覆蓋路徑規(guī)劃任務(wù)環(huán)境進(jìn)行三維仿真，并使用Unity3D中ML-Agents插件對(duì)無(wú)人船進(jìn)行訓(xùn)練。該插件包含Learning Environment、Python API和External Communicator[20]。訓(xùn)練過(guò)程中將觀測(cè)到的地圖信息以平鋪的形式傳給Agents，Agents將觀測(cè)值傳送給Brain后，Brain給出獎(jiǎng)勵(lì)并返回動(dòng)作，Agents則執(zhí)行該動(dòng)作；Brain將觀測(cè)信息和獎(jiǎng)勵(lì)通過(guò)Academy包含的External Communicator轉(zhuǎn)發(fā)給Python API進(jìn)行模型訓(xùn)練，獲得訓(xùn)練好的策略網(wǎng)絡(luò)。ML-Agents結(jié)構(gòu)如圖5所示。

學(xué)習(xí)環(huán)境包含Agents、Brain和Academy，Agents負(fù)責(zé)收集觀測(cè)結(jié)果并執(zhí)行操作[21]。選擇三個(gè)不同場(chǎng)景驗(yàn)證該算法框架的有效性。首先選取一個(gè)簡(jiǎn)單場(chǎng)景，分別使用PPO算法、SAC算法以及PPO+ICM算法進(jìn)行訓(xùn)練。圖6為通過(guò)訓(xùn)練獲得的訓(xùn)練曲線，即為使用上述算法得到的累積獎(jiǎng)勵(lì)值的變化趨勢(shì)。圖中，實(shí)線表示累積獎(jiǎng)勵(lì)平均值，陰影區(qū)域表示累積獎(jiǎng)勵(lì)的標(biāo)準(zhǔn)差。

圖6結(jié)果表明，三種算法的平均累積獎(jiǎng)勵(lì)逐漸遞增直至收斂。傳統(tǒng)PPO算法較穩(wěn)定，在3 500 000步時(shí)達(dá)到收斂且收斂效果好，而加入ICM的PPO算法在2 000 000步時(shí)率先達(dá)到收斂，則說(shuō)明加入ICM模塊后算法的收斂速度變快且穩(wěn)定性更好。三種算法的相關(guān)參數(shù)如表2～表4所示。

表2 PPO算法訓(xùn)練參數(shù)

表4 ICM模塊訓(xùn)練參數(shù)

隨著訓(xùn)練過(guò)程的進(jìn)行，搜索結(jié)束后覆蓋區(qū)域逐漸變多，規(guī)劃路徑逐漸變短，為了解不同策略在不同訓(xùn)練階段的表現(xiàn)，選擇PPO+ICM四個(gè)不同的訓(xùn)練階段進(jìn)行分析，如圖7所示。

圖7中，無(wú)人船從初始位置（左下角）起，避開島嶼（黑色方塊）到達(dá)目標(biāo)點(diǎn)（右上角）遍歷所有可達(dá)區(qū)域后結(jié)束。在每組策略下，設(shè)置步長(zhǎng)為250步，隨著訓(xùn)練從策略A進(jìn)行到策略D，無(wú)人船規(guī)劃路線趨于最優(yōu)。訓(xùn)練初始階段（策略A）覆蓋率小，無(wú)法完全覆蓋；再訓(xùn)練40回合后（策略B）覆蓋率增大，但無(wú)法完全覆蓋；再訓(xùn)練80回合后（策略C）可完全覆蓋，但重復(fù)率高；訓(xùn)練到策略D，無(wú)人船可規(guī)劃一條完全覆蓋可達(dá)區(qū)域的路徑且路徑長(zhǎng)度最優(yōu)。

表3 SAC算法訓(xùn)練參數(shù)

上述四個(gè)不同學(xué)習(xí)階段的結(jié)果可驗(yàn)證所提出的深度強(qiáng)化學(xué)習(xí)框架的可行性。對(duì)比SAC、PPO、PPO+ICM的訓(xùn)練結(jié)果可看出，PPO+ICM算法訓(xùn)練的神經(jīng)網(wǎng)絡(luò)效果更好。為分析最終策略的實(shí)際性能，在復(fù)雜環(huán)境中選取不同大小的區(qū)域，分別使用深度強(qiáng)化學(xué)習(xí)算法框架進(jìn)行對(duì)比試驗(yàn)，來(lái)判定選取多大的區(qū)域時(shí)，使用深度強(qiáng)化學(xué)習(xí)算法規(guī)劃效果最優(yōu)。

第2，3個(gè)試驗(yàn)選取復(fù)雜場(chǎng)景，在所提算法框架下進(jìn)行試驗(yàn)，選取大小不同的區(qū)域，分別使用深度強(qiáng)化學(xué)習(xí)算法框架進(jìn)行對(duì)比，選取使用深度強(qiáng)化學(xué)習(xí)算法框架的最優(yōu)區(qū)域大小。

3.2 試驗(yàn)結(jié)果

上述試驗(yàn)結(jié)果證明了所提出的“之”字形算法與基于深度強(qiáng)化學(xué)習(xí)相結(jié)合的混合算法的有效性。試驗(yàn)在27×27的地圖上進(jìn)行，選取不同大小的、使用深度強(qiáng)化學(xué)習(xí)框架的區(qū)域比較算法框架的性能。在任務(wù)區(qū)域包含不同島嶼情況下，使用深度強(qiáng)化學(xué)習(xí)算法框架分別在大小為15×15和13×13的區(qū)域下進(jìn)行比較，來(lái)判定選取多大的區(qū)域時(shí)，使用深度強(qiáng)化學(xué)習(xí)算法最優(yōu)。性能指標(biāo)對(duì)比情況如表5所示。

表5 性能指標(biāo)對(duì)比

使用深度強(qiáng)化學(xué)習(xí)算法框架規(guī)劃結(jié)果圖如圖8所示。

根據(jù)表5可知，文中所提出的“之”字形算法與深度強(qiáng)化學(xué)習(xí)算法相結(jié)合的混合算法實(shí)現(xiàn)了任務(wù)區(qū)域包含島嶼情況下的全覆蓋，并且覆蓋路徑較短。選擇使用深度強(qiáng)化學(xué)習(xí)算法框架的區(qū)域大小最好為距離障礙物周邊兩格左右，重復(fù)率較低，具有較好的效果。

4 結(jié) 語(yǔ)

針對(duì)無(wú)人船全覆蓋路徑規(guī)劃中存在的問(wèn)題，本文提出了一種將“之”字形算法與深度強(qiáng)化學(xué)習(xí)相結(jié)合的混合算法，同時(shí)加入內(nèi)在好奇心模塊，加快該混合算法的收斂速度，搭建環(huán)境模型和仿真平臺(tái)驗(yàn)證該算法的可行性。智能體在可視化平臺(tái)Unity3D中通過(guò)深度強(qiáng)化學(xué)習(xí)學(xué)會(huì)了在任務(wù)區(qū)域避障并實(shí)現(xiàn)了可達(dá)區(qū)域的全覆蓋，在不斷訓(xùn)練的過(guò)程中無(wú)人船可找到最優(yōu)（近最優(yōu)）路徑，并且提高避障能力。在無(wú)障礙物的區(qū)域覆蓋搜索使用“之”字形規(guī)劃算法，解算速度快；在含障礙物區(qū)域使用深度強(qiáng)化學(xué)習(xí)算法框架，兩者相結(jié)合實(shí)現(xiàn)了任務(wù)區(qū)域的完全覆蓋，且覆蓋路徑較短。