無(wú)人船全覆蓋路徑規(guī)劃算法研究

邢博聞，楊 柳，胡慶松，王五桂

(1.上海海洋大學(xué) 工程學(xué)院， 上海 201306； 2.中國(guó)艦船研究設(shè)計(jì)中心， 武漢 430064)

1 引言

近年來(lái)，隨著我國(guó)在渤海綜合治理、長(zhǎng)江保護(hù)修復(fù)、水源地保護(hù)等水生態(tài)事業(yè)的持續(xù)推進(jìn)，搭載相關(guān)傳感器裝置的無(wú)人船已經(jīng)被越來(lái)越多的使用在水域監(jiān)測(cè)領(lǐng)域。在這個(gè)過(guò)程中，針對(duì)指定水域的無(wú)人船監(jiān)測(cè)路徑規(guī)劃的有效性與科學(xué)性已經(jīng)成為了提升監(jiān)測(cè)質(zhì)量、降低監(jiān)測(cè)成本的核心問(wèn)題。為了實(shí)現(xiàn)對(duì)水域環(huán)境的完整監(jiān)測(cè)，無(wú)人船往往需要執(zhí)行經(jīng)典搜索模式(平行線(xiàn)、蠕變線(xiàn)、方形、扇區(qū)和障礙巡邏等搜索模式)，即全覆蓋路徑規(guī)劃(CCPP)任務(wù)。但其監(jiān)測(cè)效率、數(shù)據(jù)實(shí)時(shí)性、可檢測(cè)范圍等方面都受到路徑距離的限制與制約，如何在有限的時(shí)間內(nèi)完成對(duì)相關(guān)水域的完整覆蓋，已經(jīng)成為了無(wú)人船CCPP任務(wù)策略設(shè)計(jì)的核心指標(biāo)。

目前已經(jīng)有很多基于全覆蓋路徑規(guī)劃(CCPP)的研究。其中Howie Choset提出了精確的細(xì)胞分解方法用于覆蓋目標(biāo)地圖。算法的主要工作是將整個(gè)工作空間按照障礙物的邊界分割成一個(gè)個(gè)小的待覆蓋區(qū)域，然后在整個(gè)工作空間中使用深度優(yōu)先搜索的方法來(lái)遍歷這些區(qū)域。Vatana等提出了一種為圓形移動(dòng)機(jī)器人進(jìn)行本地全覆蓋路徑規(guī)劃的方法。該方法首先將目標(biāo)區(qū)域劃分為多個(gè)正三角形，然后根據(jù)多個(gè)正三角形的大小和感應(yīng)范圍，確定路徑。Hassan等提出了一種新穎的自適應(yīng)全覆蓋路徑規(guī)劃算法，該方法設(shè)計(jì)了一個(gè)包含3個(gè)獎(jiǎng)勵(lì)的總獎(jiǎng)勵(lì)函數(shù)，其中第一個(gè)獎(jiǎng)勵(lì)受到捕食者與獵物關(guān)系的啟發(fā)，第二個(gè)獎(jiǎng)勵(lì)與沿著直線(xiàn)方向的持續(xù)運(yùn)動(dòng)有關(guān)，第三個(gè)獎(jiǎng)勵(lì)則與覆蓋的范圍大小有關(guān)。

無(wú)人船在航行過(guò)程中時(shí)刻受到浪流影響需要不斷改變速度、航行，這也降低了傳統(tǒng)全覆蓋路徑規(guī)劃算法無(wú)法在復(fù)雜環(huán)境中的有效性與可行性。為此，Koppaka Ganesh Sai Apuroop 和 Anh Vu Le以卷積神經(jīng)網(wǎng)絡(luò)(CNN)為基礎(chǔ)，提出了可以使機(jī)器人最大化區(qū)域覆蓋，同時(shí)最小化耗能的基于深度強(qiáng)化學(xué)習(xí)的框架，并使用演員-評(píng)論家經(jīng)驗(yàn)回放算法(actor-critic experience replay)來(lái)訓(xùn)練神經(jīng)網(wǎng)絡(luò)的長(zhǎng)期記憶庫(kù)(LSTM)。然而基于傳統(tǒng)神經(jīng)網(wǎng)絡(luò)方法，其全覆蓋路徑規(guī)劃算法面臨環(huán)境信息未知、缺乏先驗(yàn)知識(shí)和神經(jīng)網(wǎng)絡(luò)沒(méi)有解搜索空間等等問(wèn)題。

為此本文中提出了一種新的神經(jīng)網(wǎng)絡(luò)算法，通過(guò)改進(jìn)后人工蜂群法進(jìn)行無(wú)監(jiān)督訓(xùn)練和學(xué)習(xí)完成無(wú)人船的全覆蓋路徑規(guī)劃。該算法根據(jù)無(wú)人船是否滿(mǎn)足障礙物約束、新區(qū)域探索效率等條件來(lái)構(gòu)建了評(píng)價(jià)函數(shù)，利用改進(jìn)后的人工蜂群法優(yōu)化神經(jīng)網(wǎng)絡(luò)的參數(shù)，提高訓(xùn)練效率、提升訓(xùn)練效果，從而實(shí)現(xiàn)無(wú)人船在復(fù)雜環(huán)境下的自主探索的全覆蓋路徑規(guī)劃。

2 環(huán)境建模與仿真平臺(tái)

2.1 柵格地圖模型

由于計(jì)算機(jī)不能直接處理環(huán)境信息，所以需要首先對(duì)環(huán)境進(jìn)行建模，將現(xiàn)實(shí)的環(huán)境和路徑規(guī)劃問(wèn)題轉(zhuǎn)化為計(jì)算機(jī)可以理解的表達(dá)形式。

在柵格地圖模型中，空白(白色)柵格代表可以通行的區(qū)域，黑色柵格代表障礙物所在區(qū)域。如果柵格中既有白色又有黑色，通過(guò)判斷黑色部分的占比來(lái)判斷該區(qū)域是否可以通行，如果黑色占整個(gè)柵格的10%以上則判定為此柵格不可通行，否則該區(qū)域可以正常通行。

2.2 仿真平臺(tái)搭建

本文中根據(jù)柵格地圖模型，基于Tkinter搭建了無(wú)人船全覆蓋路徑規(guī)劃仿真環(huán)境平臺(tái)，其效果如圖1所示。圖1中地圖中的黑色區(qū)域?yàn)檎系K物所在的區(qū)域，無(wú)人船只能在白色柵格中移動(dòng)，如果無(wú)人船移動(dòng)到黑色柵格中，則任務(wù)失敗。紅色方塊代表無(wú)人船，規(guī)定無(wú)人船每一步移動(dòng)都只能從當(dāng)前柵格移動(dòng)到相鄰的白色柵格區(qū)域。無(wú)人船每覆蓋一個(gè)柵格，柵格就會(huì)由白色變?yōu)樯钌硎酒湟呀?jīng)被覆蓋過(guò)。若無(wú)人船移動(dòng)到地圖邊界以外或者移動(dòng)到黑色柵格內(nèi)，則任務(wù)失敗。若除黑色柵格區(qū)域以外的柵格都變?yōu)樯钌瑒t代表所有非障礙物柵格都已經(jīng)被覆蓋，任務(wù)完成。

圖1 仿真環(huán)境平臺(tái)效果示意圖Fig.1 Schematic diagram of simulation environment

2.3 評(píng)價(jià)函數(shù)

無(wú)人船需要使用盡量少的步長(zhǎng)遍歷整個(gè)環(huán)境同時(shí)自主躲避地圖中的障礙物。為了分析算法的性能，本文中定義了以下評(píng)價(jià)函數(shù)。該評(píng)價(jià)函數(shù)分為3部分：

1) 覆蓋率

2) 路徑重復(fù)率

3) 事故懲罰

本文中設(shè)定當(dāng)無(wú)人船進(jìn)入障礙物所在的柵格或者地圖邊界以外則代表任務(wù)失敗，從而在評(píng)價(jià)函數(shù)中減去固定的值作為懲罰，并且結(jié)束此次任務(wù)。然后開(kāi)始新一輪的嘗試。如果無(wú)人船順利完成全覆蓋路徑規(guī)劃任務(wù)，即覆蓋了工作環(huán)境中所有未被障礙物覆蓋的柵格并且過(guò)程中未碰撞到障礙物和地圖邊界，則加上固定的分?jǐn)?shù)作為獎(jiǎng)勵(lì)。獎(jiǎng)勵(lì)記為。

3 人工蜂群法結(jié)合神經(jīng)網(wǎng)絡(luò)的全覆蓋路徑規(guī)劃算法

3.1 人工蜂群法

人工蜂群法是2005年Karaboga小組為優(yōu)化代數(shù)問(wèn)題所提出的群智能算法，其模仿蜜蜂尋找蜜源和采集蜂蜜的過(guò)程。相較于常見(jiàn)的啟發(fā)式算法，它的優(yōu)勢(shì)在于使用了比較少的控制參數(shù)，在每次迭代中都會(huì)搜索全局和局部的最優(yōu)解方案，因此可以大大增加其尋找到最優(yōu)解的概率，并且人工蜂群法具有很強(qiáng)的魯棒性。

人工蜂群算法就是基于蜜蜂采蜜的過(guò)程而提出的新型智能優(yōu)化算法，它由蜜源、雇傭蜂和非雇傭蜂3個(gè)部分組成。蜜源就是待優(yōu)化問(wèn)題的可行解，是人工蜂群算法需要處理的基本對(duì)象。蜜源的好壞由評(píng)價(jià)函數(shù)所決定。雇傭蜂與蜜源的位置是一一對(duì)應(yīng)的，在人工蜂群算法中，蜜源的個(gè)數(shù)與雇傭蜂的個(gè)數(shù)是相等的。雇傭蜂的任務(wù)是發(fā)現(xiàn)蜜源并且以一定的概率與跟隨蜂相分享，概率一般是以評(píng)價(jià)函數(shù)的值和輪盤(pán)賭法則來(lái)綜合計(jì)算。非雇傭蜂則分為跟隨蜂與偵察蜂。跟隨蜂根據(jù)雇傭蜂發(fā)布的蜜源信息來(lái)選擇探索的范圍并且進(jìn)行貪心選擇搜索新的蜜源。如果一個(gè)蜜源在經(jīng)過(guò)多次更新后仍未被更新，則此雇傭蜂變?yōu)閭刹旆洹刹旆涞淖饔檬窃诜涑哺浇鼘ふ倚碌氖澄镌矗簿褪翘鼍植孔顑?yōu)解，尋找全局最優(yōu)解。

人工蜂群法的算法原理如下。假設(shè)需要解決的問(wèn)題的解空間的維數(shù)為，跟隨蜂與偵察蜂的個(gè)數(shù)都為，蜜源的濃度相當(dāng)于相應(yīng)的解通過(guò)評(píng)價(jià)函數(shù)得到的值，也稱(chēng)為適應(yīng)度。跟隨蜂與蜜源是一一對(duì)應(yīng)的，所以與第個(gè)蜜源相對(duì)應(yīng)的第個(gè)跟隨蜂尋找蜜源的公式如下：

(1)

其中，=1,2,3,…,，=1,2,3,…,,為[-1,1]區(qū)間上的隨機(jī)數(shù)，并且≠。然后將新生成的解與原本的解比較并且采用貪婪策略選擇保留較好的解。每一個(gè)觀察蜂根據(jù)概率選擇一個(gè)蜜源，概率為：

(2)

其中為解所對(duì)應(yīng)評(píng)價(jià)函數(shù)的值。觀察蜂根據(jù)概率公式搜尋新的可能解。當(dāng)在給定的步驟內(nèi)蜜源對(duì)應(yīng)的評(píng)價(jià)函數(shù)值沒(méi)有提高，則放棄該蜜源。而與該蜜源對(duì)應(yīng)的雇傭蜂變?yōu)閭刹旆鋵ふ倚碌拿墼矗旅墼礊?

(3)

3.2 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

無(wú)人船應(yīng)該做到可以根據(jù)周?chē)沫h(huán)境和自身的狀態(tài)來(lái)不斷自動(dòng)調(diào)節(jié)下一時(shí)刻的動(dòng)作。在這一應(yīng)用場(chǎng)景下，神經(jīng)網(wǎng)絡(luò)展現(xiàn)出了良好的效果。神經(jīng)網(wǎng)絡(luò)不僅可以通過(guò)周?chē)h(huán)境的信息輸入來(lái)決定下一時(shí)刻的控制指令，而且可以通過(guò)不斷地學(xué)習(xí)提高自己的表現(xiàn)效果。但是由于在全覆蓋路徑規(guī)劃中很難利用類(lèi)似于梯度下降等的規(guī)律來(lái)優(yōu)化神經(jīng)網(wǎng)絡(luò)參數(shù)進(jìn)行學(xué)習(xí)，所以本文中只構(gòu)建一個(gè)前向神經(jīng)網(wǎng)絡(luò)，優(yōu)化參數(shù)時(shí)使用人工蜂群法代替神經(jīng)網(wǎng)絡(luò)的反向傳播過(guò)程。

圖2 激光雷達(dá)的輸入示意圖Fig.2 Schematic diagram of Lidar input

除了障礙物信息，無(wú)人船為了更好地執(zhí)行全覆蓋路徑規(guī)劃任務(wù)，還需要了解已經(jīng)覆蓋完成的區(qū)域信息，所以神經(jīng)網(wǎng)絡(luò)地輸入還要包含無(wú)人船5個(gè)方向的區(qū)域覆蓋程度信息：

(4)

其中，為在第個(gè)方向上的輸入，為無(wú)人船覆蓋過(guò)第個(gè)方向上第個(gè)柵格的次數(shù)，為激光雷達(dá)的量程，為最大覆蓋次數(shù)，本文中設(shè)定=15。當(dāng)無(wú)人船覆蓋該方向上柵格的平均次數(shù)大于15次，則該方向上的區(qū)域覆蓋率恒為1。

因此，神經(jīng)網(wǎng)絡(luò)的輸入應(yīng)為{,,,,,,,,,}，其中為激光雷達(dá)輸出的障礙物信息，為從地圖獲取的5個(gè)方向上的覆蓋率信息。

神經(jīng)網(wǎng)絡(luò)的輸出為無(wú)人船所做出的動(dòng)作，即向上、向下、向左和向右4個(gè)動(dòng)作。本文中的神經(jīng)網(wǎng)絡(luò)的隱藏層激活函數(shù)選擇ReLU 函數(shù)，輸出層的激活函數(shù)選取softmax函數(shù)，ReLU函數(shù)的表達(dá)式為()=max(0,)。

經(jīng)大量實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)隱藏層的層數(shù)為1，隱藏層的神經(jīng)元個(gè)數(shù)為6時(shí)神經(jīng)網(wǎng)絡(luò)的性能最優(yōu)。

3.3 人工蜂群法作為神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化方法的全覆蓋路徑規(guī)劃算法

神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)模式大致可以分為有監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)，有監(jiān)督學(xué)習(xí)需要提供大量的標(biāo)注后的樣本，通過(guò)輸入樣本之后輸出的信息來(lái)調(diào)整神經(jīng)網(wǎng)絡(luò)的參數(shù)，從而擬合出樣本與輸出的關(guān)系。由于在無(wú)人船的全覆蓋路徑規(guī)劃算法中，很難根據(jù)任務(wù)去設(shè)定每一種情況對(duì)應(yīng)的最優(yōu)動(dòng)作的值，從而很難確定實(shí)際輸出與理想輸出之間的誤差，即無(wú)法判斷在某一環(huán)境下某一個(gè)動(dòng)作是否為正確、高效的對(duì)全覆蓋有利的動(dòng)作，需要根據(jù)回合結(jié)束后的信息才能判斷，所以無(wú)法確定該動(dòng)作樣本為正樣本還是負(fù)樣本，也無(wú)法利用損失值來(lái)進(jìn)行梯度下降等方法來(lái)更新神經(jīng)網(wǎng)絡(luò)的參數(shù)。

本文中將神經(jīng)網(wǎng)絡(luò)的參數(shù)值作為待優(yōu)化的部分，可以通過(guò)啟發(fā)式算法來(lái)對(duì)其進(jìn)行優(yōu)化更新。由于人工蜂群法不需要了解問(wèn)題的特殊信息，只需對(duì)生成的路徑進(jìn)行優(yōu)劣比較，通過(guò)各人工蜂個(gè)體的局部尋優(yōu)行為，最終在群體中使全局最優(yōu)值凸顯出來(lái)，有著較快的收斂速度，所以本文中采用無(wú)監(jiān)督學(xué)習(xí)結(jié)合人工蜂群法來(lái)優(yōu)化神經(jīng)網(wǎng)絡(luò)參數(shù)。

一般來(lái)說(shuō)，神經(jīng)網(wǎng)絡(luò)單步更新的效率更高，即無(wú)人船每走一步，神經(jīng)網(wǎng)絡(luò)的參數(shù)更新一次。但是由于無(wú)法根據(jù)無(wú)人船單步運(yùn)動(dòng)信息準(zhǔn)確地判斷這一步對(duì)于整體全覆蓋路徑規(guī)劃的收益，所以本文中選擇在無(wú)人船完成任務(wù)之后或者碰撞到障礙物和地圖邊界之后再整體評(píng)價(jià)神經(jīng)網(wǎng)絡(luò)所最終形成的路徑，根據(jù)評(píng)價(jià)再進(jìn)一步優(yōu)化神經(jīng)網(wǎng)絡(luò)的參數(shù)，即按照回合制更新。

人工蜂群法可以基于任務(wù)來(lái)靈活地設(shè)計(jì)評(píng)價(jià)函數(shù)，從而評(píng)價(jià)和選擇神經(jīng)網(wǎng)絡(luò)的參數(shù)，并且通過(guò)多次迭代得出全局近似最優(yōu)解。由于人工蜂群法算法設(shè)計(jì)過(guò)程簡(jiǎn)單、參數(shù)少、能夠跳出局部最優(yōu)解、魯棒性強(qiáng)等特點(diǎn)，所以本文中采取人工蜂群法來(lái)代替梯度下降法優(yōu)化神經(jīng)網(wǎng)絡(luò)的參數(shù)。

初始情況下神經(jīng)網(wǎng)絡(luò)的參數(shù)是在極值區(qū)間中隨機(jī)生成的，所以初始情況下神經(jīng)網(wǎng)絡(luò)所規(guī)劃出的路徑得分會(huì)較低。然后人工蜂群法一次生成多組神經(jīng)網(wǎng)絡(luò)參數(shù)，神經(jīng)網(wǎng)絡(luò)參數(shù)的組數(shù)即蜜源的個(gè)數(shù)，人工蜂群法求解空間的維數(shù)即神經(jīng)網(wǎng)絡(luò)參數(shù)的個(gè)數(shù)。然后在每一組神經(jīng)網(wǎng)絡(luò)的控制下無(wú)人船會(huì)在地圖中生成各自的軌跡，軌跡可以通過(guò)速度的積分求出，也可以在地圖中實(shí)時(shí)記錄無(wú)人船每一步的位置信息。當(dāng)軌跡碰撞到障礙物和地圖邊界或者覆蓋率達(dá)到指定要求時(shí)，無(wú)人船停止運(yùn)動(dòng)并評(píng)估軌跡的得分。神經(jīng)網(wǎng)絡(luò)在初始學(xué)習(xí)階段很容易出現(xiàn)無(wú)人船在相同的路徑上轉(zhuǎn)圈，此路徑既不會(huì)碰撞到障礙物或者地圖邊界，也不會(huì)達(dá)到覆蓋率大于預(yù)設(shè)值，此時(shí)程序陷入死循環(huán)，所以設(shè)定當(dāng)無(wú)人船運(yùn)動(dòng)步長(zhǎng)大于待覆蓋柵格的3倍以上，則任務(wù)失敗。無(wú)人船停止運(yùn)動(dòng)并且評(píng)估該軌跡得分。如果最高分滿(mǎn)足要求，則算法結(jié)束。如果最高分不符合要求，則將該分值和參數(shù)值保存在列表中，供人工蜂群法之后的迭代使用。通過(guò)評(píng)價(jià)函數(shù)評(píng)價(jià)各個(gè)軌跡，挑選優(yōu)秀的軌跡，并且偵察蜂會(huì)在整個(gè)解空間隨機(jī)搜索新的蜜源，不斷優(yōu)化蜜源即神經(jīng)網(wǎng)絡(luò)參數(shù)的質(zhì)量。

全覆蓋路徑規(guī)劃算法需要無(wú)人船能夠在未知區(qū)域中進(jìn)行全覆蓋路徑規(guī)劃并且自主避障，所以路徑的評(píng)價(jià)函數(shù)必須包含地圖的覆蓋率、路徑的重復(fù)率和路徑的事故率，所以評(píng)價(jià)函數(shù)應(yīng)該取：

(5)

由于在仿真地圖中可以很輕易地實(shí)時(shí)獲得無(wú)人船的動(dòng)作信息，所以在仿真中取：

(6)

本文中選取的蜜源數(shù)為8，雇傭蜂個(gè)數(shù)與蜜源相等。首先隨機(jī)生成蜜源，根據(jù)各個(gè)蜜源生成對(duì)應(yīng)的神經(jīng)網(wǎng)絡(luò)，通過(guò)評(píng)價(jià)函數(shù)來(lái)評(píng)估依據(jù)神經(jīng)網(wǎng)絡(luò)輸出生成的路徑。之后通過(guò)雇傭蜂和跟隨蜂的搜尋尋找更優(yōu)的蜜源，不斷迭代，迭代終止條件為迭代次數(shù)達(dá)到設(shè)定的最大值或者評(píng)價(jià)函數(shù)的值高于預(yù)設(shè)值。同時(shí)偵察蜂在整個(gè)解空間搜尋蜜源，實(shí)現(xiàn)跳出局部最優(yōu)解，達(dá)到全局最優(yōu)解。算法流程如圖3所示。

圖3 算法流程框圖Fig.3 Algorithm flowchart

4 仿真分析

本次仿真實(shí)驗(yàn)環(huán)境為一張10*10的柵格地圖，其中有一些隨機(jī)障礙物，網(wǎng)格邊長(zhǎng)為1 m。仿真系統(tǒng)通過(guò)離線(xiàn)學(xué)習(xí)功能實(shí)現(xiàn)自主避障和全覆蓋路徑規(guī)劃任務(wù)的神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化。當(dāng)一代無(wú)人船完成全覆蓋路徑規(guī)劃任務(wù)或與障礙物碰撞時(shí)，它們會(huì)根據(jù)路徑覆蓋、重復(fù)率和事故率進(jìn)行評(píng)分。人工蜂群算法選擇得分較高的路徑進(jìn)行迭代，優(yōu)化神經(jīng)網(wǎng)絡(luò)參數(shù)進(jìn)行全覆蓋路徑規(guī)劃。優(yōu)化結(jié)果如圖4所示。縱坐標(biāo)cost采取路徑分?jǐn)?shù)的倒數(shù)，橫坐標(biāo)代表迭代次數(shù)。隨著迭代次數(shù)的不斷增加，前200次的cost迅速降低，說(shuō)明之前的訓(xùn)練可以非常有效。快速提升神經(jīng)網(wǎng)絡(luò)的效果，后面的分?jǐn)?shù)趨于收斂，此時(shí)得到的路徑接近最優(yōu)路徑。圖5為使用神經(jīng)網(wǎng)絡(luò)結(jié)合遺傳算法進(jìn)行全覆蓋路徑規(guī)劃的訓(xùn)練得分曲線(xiàn)。通過(guò)大量的實(shí)驗(yàn)表明，在地圖大小小于7*7時(shí)遺傳算法可以很快收斂到最優(yōu)路徑，但是當(dāng)?shù)貓D大小大于9*9之后，遺傳算法的收斂速度變得非常緩慢。圖5為遺傳算法在10*10的柵格地圖中進(jìn)行全覆蓋路徑規(guī)劃的訓(xùn)練得分曲線(xiàn)。圖6表示采用傳統(tǒng)的牛耕法全覆蓋路徑規(guī)劃，此時(shí)的覆蓋率為100%，重復(fù)率為20%。圖7表示全覆蓋路徑規(guī)劃神經(jīng)網(wǎng)絡(luò)訓(xùn)練之后生成的路徑。此路徑的覆蓋率為100%，重復(fù)率為2%。如表1所示，本文中所提出的算法的路徑重復(fù)率大大小于傳統(tǒng)的牛耕法，雖然算法耗時(shí)要大于牛耕法的時(shí)間，但是也在接受范圍之內(nèi)。而且其算法可以積累之前的經(jīng)驗(yàn)，在新的地圖中可以吸取之前地圖的全覆蓋路徑規(guī)劃經(jīng)驗(yàn)，從而更加迅速地收斂于最優(yōu)路徑。理論上，使用足夠多的地圖對(duì)其算法進(jìn)行訓(xùn)練，訓(xùn)練完成之后，此算法可以直接在任意陌生地圖中使用而不需要再次訓(xùn)練。此時(shí)只需要相應(yīng)的傳感器提供數(shù)據(jù)，從而滿(mǎn)足路徑規(guī)劃過(guò)程中實(shí)時(shí)性的需求。

圖4 神經(jīng)網(wǎng)絡(luò)訓(xùn)練優(yōu)化曲線(xiàn)Fig.4 Neural network training optimization diagram

圖5 遺傳算法訓(xùn)練得分曲線(xiàn)Fig.5 Genetic algorithm training score graph

圖6 牛耕法全覆蓋路徑規(guī)劃示意圖Fig.6 The full coverage path planning diagram of cattle farming method

圖7 全覆蓋路徑規(guī)劃路徑示意圖Fig.7 The map of full coverage path planning path

表1 算法結(jié)果Table 1 The result of the algorithm

由上文可得本文中設(shè)計(jì)的神經(jīng)網(wǎng)絡(luò)結(jié)合人工蜂群的全覆蓋路徑規(guī)劃算法經(jīng)過(guò)較少的迭代次數(shù)就能收斂，得到較高的評(píng)價(jià)即較優(yōu)的全覆蓋路徑，且路徑不會(huì)與障礙物和地圖邊界相撞。同時(shí)通過(guò)降低迭代結(jié)束標(biāo)準(zhǔn)，程序迭代的時(shí)間也會(huì)大大縮短，即犧牲一部分區(qū)域的探索可以換得更短的步長(zhǎng)覆蓋盡量多的區(qū)域，當(dāng)全覆蓋路徑規(guī)劃的路徑重復(fù)率的要求比較低時(shí)時(shí)可以通過(guò)適當(dāng)調(diào)低覆蓋率來(lái)實(shí)現(xiàn)快速收斂，使得算法執(zhí)行效率更高。

5 結(jié)論

1) 基于神經(jīng)網(wǎng)絡(luò)前向傳播結(jié)合人工蜂群的全覆蓋路徑規(guī)劃算法，可非監(jiān)督學(xué)習(xí)，在離線(xiàn)環(huán)境下學(xué)習(xí)規(guī)避障礙物和地圖邊界，有效地進(jìn)行全覆蓋路徑規(guī)劃，降低路徑重復(fù)率；使用人工蜂群方法改進(jìn)了神經(jīng)網(wǎng)絡(luò)梯度下降的收斂方法，使神經(jīng)網(wǎng)絡(luò)更快地訓(xùn)練完成，提高算法的可實(shí)現(xiàn)性與移植性。

2) 一般全覆蓋路徑規(guī)劃算法全覆蓋路徑重復(fù)率過(guò)高、無(wú)法應(yīng)對(duì)動(dòng)態(tài)環(huán)境。人工蜂群法結(jié)合神經(jīng)網(wǎng)絡(luò)的全覆蓋路徑規(guī)劃算法可以有效控制無(wú)人船進(jìn)行高質(zhì)量的全覆蓋路徑規(guī)劃，并且可以移值到不同的環(huán)境下，具有較強(qiáng)的魯棒性。