基于海洋遙感圖像的無人艇路徑覆蓋規(guī)劃算法

曹 毅，程向紅，李丹若，劉豐宇

（1.微慣性儀表與先進導航技術(shù)教育部重點實驗室，南京 210096;2.東南大學 儀器科學與工程學院，南京 210096）

無人艇（Unmanned Surface Vehicle,USV）具有低風險、高速度、自主操作和智能化水平高的特點，越來越多地被應(yīng)用于海洋搜救、資源勘探、反水雷等覆蓋任務(wù)中[1]。路徑覆蓋規(guī)劃（Coverage Path Planning,CPP）是實現(xiàn)這些覆蓋任務(wù)的關(guān)鍵。USV 的CPP 技術(shù)通常需要解決2 個核心問題：（1）建立精細化的地圖模型；（2）設(shè)計高效、合理的覆蓋路徑[2-3]。

在地圖建模部分，傳統(tǒng)柵格法在路徑覆蓋的地圖建模方面應(yīng)用最為廣泛[4-6]。但是考慮到USV 在海洋環(huán)境邊界條件多、障礙物復(fù)雜且具有方向任意性等多方面挑戰(zhàn)，傳統(tǒng)柵格法無法保證海岸線與障礙物的精細化提取。在覆蓋路徑規(guī)劃方面，當前，常用的路徑覆蓋算法有A*算法[7]，神經(jīng)元激勵算法[8]，蟻群算法[9]，遺傳算法[10]，貪心算法[11]等。但這些算法應(yīng)用到海洋環(huán)境中，仍然存在一些問題，如A*算法在面對大規(guī)模海洋區(qū)域時，其規(guī)劃的轉(zhuǎn)彎路徑多且計算量過大；而神經(jīng)元激勵算法在進行復(fù)雜環(huán)境下路徑覆蓋時，該方法隨機性大，且重復(fù)率較高。蟻群算法與粒子群算法均是啟發(fā)于生物界行為而設(shè)計的啟發(fā)式算法，這類算法可以在規(guī)劃時忽略機器人本身的運動約束，但在算法初期搜索速度慢，需要較高的迭代次數(shù)才能收斂，因此算法的實時性不高，且算法程序設(shè)計較為復(fù)雜，只有在處理小范圍環(huán)境時耗時較少。貪心算法計算量小且算法簡單，但是其在處理全局路徑覆蓋規(guī)劃時，易陷入局部最優(yōu)。

針對上述研究現(xiàn)狀存在的不足，提出了一種基于海洋遙感圖像的無人艇路徑覆蓋規(guī)劃算法。首先，提出了一種基于改進YOLO V3 的目標檢測與圖像處理融合的地圖建模算法。該算法將海洋遙感圖像作為USV 路徑覆蓋的輸入，并將遙感圖像中障礙物的角度信息引入到地圖模型中，最終建立精細化的二值地圖模型。該模型與柵格地圖相比，考慮了障礙物的角度信息，地圖模型更精細。其次，提出了一種基于旋轉(zhuǎn)光束與貪心算法的路徑覆蓋算法，該算法將完整的覆蓋路徑分為直行路與轉(zhuǎn)彎路徑。并分別基于路徑長度、轉(zhuǎn)彎拐點數(shù)目優(yōu)化兩類路徑。在規(guī)劃轉(zhuǎn)彎路徑時，還將已獲得的直行路徑作為約束，引入貪心算法，將貪心算法的全局優(yōu)化問題轉(zhuǎn)化為局部優(yōu)化問題，解決了貪心算法易陷入局部最優(yōu)的缺陷。總的來說，本文將覆蓋路徑規(guī)劃與目標檢測、圖像處理融合，構(gòu)建了直接基于遙感圖像的USV 路徑覆蓋框架，提高了無人艇執(zhí)行覆蓋任務(wù)的作業(yè)效率。

1 地圖建模

1.1 地圖模型信息描述

復(fù)雜海洋環(huán)境遙感圖像包含許多不可覆蓋區(qū)域，這些區(qū)域包含信息的類型各不相同。如圖1 所示，淺綠色的區(qū)域為港口等基礎(chǔ)設(shè)施(RN)的位置，該區(qū)域可通過測繪技術(shù)得到，視為已知信息。深綠色的區(qū)域為海面上的船舶障礙物(RO)，RO是未知的信息且具有不同的尺寸和方向，這些特點給精確地圖模型的建立帶來困難；黑色曲線框住的區(qū)域(RT)是待覆蓋區(qū)域，定義為一個閉合多邊形。假設(shè)本文算法的應(yīng)用背景為無人艇小范圍的巡邏與測繪。應(yīng)用場景包含：包含多種密集障礙物的小范圍遠海區(qū)域，包含復(fù)雜海岸線與障礙物的小范圍近岸區(qū)域。

圖1 遙感地圖信息示意圖Fig.1 Schematic diagram of remote sensing map information

1.2 地圖建模算法

地圖建模的重點是精準獲取RO障礙物的位置信息，為此，提出了一種基于改進YOLO V3 的旋轉(zhuǎn)目標檢測算法。傳統(tǒng)YOLO V3[12]的模型輸出(x,y,w,h)四維信息，即中心點的坐標和外接矩形的長、寬。該坐標只能預(yù)測目標的外接矩形框，而不能輸出目標最小面積的外接矩形框。如圖2 所示，在海洋遙感圖像中，船舶障礙物的方向是任意且排列緊密的。如果使用傳統(tǒng)YOLO V3 檢測船舶障礙物，則相鄰兩艘船舶的交并比過大，會出現(xiàn)目標檢測召回率降低且目標框與船體不擬合的問題，最終導致地圖建模不精細。

圖2 不同輸出矩形框的檢測結(jié)果Fig.2 The detection results of different output boxes

為了解決上述問題，在保證傳統(tǒng)YOLO V3 模型預(yù)測速度情況下，本文重新定義了最小面積的外接矩形框：（tx,ty,tw,th,tθ）。其中，（tx,ty）為矩形框中心點的坐標，tw和th為矩形框長邊或短邊的長度，當x軸向上正方向旋轉(zhuǎn)時，遇到的第一個邊即為tw，則另一側(cè)為th所在的邊，旋轉(zhuǎn)角度為tθ，取值范圍為[-90 °,0 °]。具體定義如圖3 所示，粗紅線為tw，另一側(cè)為th。定義的角tθ是tw與x軸正方向之間的夾角，其取值范圍為[-90 °，0 °]。

圖3 最小面積的外接矩形框示意圖Fig.3 Schematic diagram of external rectangular with minimum area

對于改進后的YOLO V3 網(wǎng)絡(luò)的新輸出矩形框，需要設(shè)計網(wǎng)絡(luò)的角度損失函數(shù)。為了縮小學習區(qū)間，讓原始的tθ從-45°開始預(yù)測，取值范圍設(shè)置為(0 °,-45°]和[0 °,45°），將原始學習區(qū)間縮小一倍，降低學習難度，重新定義后的角度損失函數(shù)為：

模型總損失函數(shù)包含定位損失、角度損失、置信度損失和類別損失：

其中，λcoord為訓練權(quán)重，設(shè)為0.5,S為網(wǎng)格單元格數(shù)，B為錨框數(shù)，表示第i個網(wǎng)格的第j個錨框是否負責預(yù)測該目標，如果是，則=1，否則=0,Ci表示目標分類，Pi表示分類概率。

如圖4(a)所示，當通過改進的YOLO V3 獲取RO障礙物的信息及通過測繪手段獲取RN等其他區(qū)域信息后，需要利用歸一化色差原理對處理后的圖像進行二值化，并建立如圖4(b)所示的地圖模型。歸一化色差原理是根據(jù)顏色特征對圖像進行二值化，提取圖4(a)中的綠色區(qū)域。其中，RO與RN區(qū)域定義為1，待覆蓋的海洋區(qū)域定義為0。如式(3)(4)所示：

圖4 遙感地圖建模過程Fig.4 The remote sensing map modeling process

其中R，G和B分別表示彩色遙感圖像的紅、綠和藍3 個通道，τ為歸一化色差，Mapij表示處理后的地圖模型信息，0(白色部分)表示待覆蓋區(qū)域，1(黑色部分)表示不可覆蓋區(qū)域。固定閾值為160，其值通過對遙感圖像的像素分析后得到。

2 路徑覆蓋規(guī)劃算法

基于已建立的海洋地圖模型，提出了一種基于旋轉(zhuǎn)光束和貪心算法的CPP 算法。在有障礙物的不規(guī)則多邊形區(qū)域中，USV 的覆蓋路徑會被障礙物或凹凸部分打斷。因此，本文將覆蓋路徑分為兩部分：直行路徑和轉(zhuǎn)彎路徑。由于USV 在轉(zhuǎn)彎時必須先減速后加速，轉(zhuǎn)彎耗時比直行要多，所以有必要限制轉(zhuǎn)彎次數(shù)，基于此本文采用旋轉(zhuǎn)光束算法，以最短路徑長度和最小轉(zhuǎn)彎次數(shù)為目標優(yōu)化直行路徑。然后利用貪心算法以最短長度為目標將直行路徑形成的節(jié)點進行連接，最終得到完整的覆蓋路徑。

2.1 基于旋轉(zhuǎn)光束的直行覆蓋路徑規(guī)劃

如圖5 所示，采用前后折返運動作為USV 的覆蓋模式。該種覆蓋模式使得前一直行路徑總是平行于下一直行路徑，因此初始直行路徑平行于最終直行路徑。本文將這些平行直行路徑定義為一系列平行光束。通過改變平行光束的斜率和截距參數(shù)，使光束組旋轉(zhuǎn)。最終得到一組以轉(zhuǎn)彎次數(shù)與路徑長度為約束的避障直線路徑。圖5 中黑色網(wǎng)格代表障礙物，白色網(wǎng)格代表待覆蓋區(qū)域。紅色虛線表示直行路徑，藍色虛線表示轉(zhuǎn)彎路徑，兩者共同構(gòu)成完整覆蓋路徑。

圖5 不同斜率的直行光束組Fig.5 The group of straight paths with different slopes

如圖5 所示，一組紅色平行直線路徑定義如下：

其中，φ為直線的斜率，或，θ1=1...m，θ2=1...n，定義?1和?2為直行路徑的水平軸和垂直軸的截距，n為垂直軸的網(wǎng)格總數(shù)，m為水平軸的網(wǎng)格總數(shù)。j為二值地圖中劃分窗口的總列數(shù)，i為二值地圖中劃分窗口的總行數(shù)，網(wǎng)格地圖由式(4)求得。

其中，w為USV 的作業(yè)寬度，在圖5 中，n=7，m=6。

定義好直行路徑方程后，通過調(diào)整φ與?值，使得直行路徑被障礙物打斷最少，從而減少整體的路徑耗時。因為當直行路徑障礙物打斷時，轉(zhuǎn)彎點的數(shù)量會增加，耗時也隨之增加。限制轉(zhuǎn)彎次數(shù)的代價函數(shù)定義由以下公式給出:

其中，Mapij為式(4)得到的地圖模型，L∩Mapij=1，=1為若直行路徑L通過地圖中的障礙物，則其通過第i行，第j列的窗口格數(shù)目記為1，l'為通過障礙物的總窗口數(shù)目。

此外，限制路徑長度的代價函數(shù)定義如下：

其中，L∩Mapij=0，lij=1為若直行路徑L通過地圖中的待覆蓋區(qū)域，則其通過第i行，第j列的窗口數(shù)目lij記為1，l為通過覆蓋區(qū)域的總窗口數(shù)目，δmin為長度代價函數(shù)，μ∈{μ1，μ2}為長度參數(shù)。

2.2 基于貪心算法的轉(zhuǎn)彎覆蓋路徑規(guī)劃

得到規(guī)劃直線路徑后，由式(5)定義的每條直行路徑的截距決定直行路徑的順序。如圖6 所示，采用“從左到右，從上到下”的規(guī)則，生成平行線段的排列順序列表。該規(guī)則定義每條直行路徑有兩個鄰域：一個是屬于相鄰直行路徑列表的線段，另一個是不屬于同一列表的線段。不屬于同一列表的直線路徑段是那些被障礙物打斷的，如：線段(11-12)與(13-14)。轉(zhuǎn)彎路徑是在相鄰節(jié)點之間產(chǎn)生的。圖6 是貪婪算法的原理圖。基于最短長度原則，利用貪心算法來生成轉(zhuǎn)彎路徑。傳統(tǒng)的貪心算法不考慮路徑的全局最優(yōu)性，只考慮局部路徑[13]的最優(yōu)解。但本文在前一節(jié)中，通過旋轉(zhuǎn)光束算法得到了直行路徑，以得到的直線路徑為約束，可連接得到轉(zhuǎn)彎路徑。通過已獲取的直行路徑本文將貪心算法的全局最優(yōu)覆蓋路徑問題轉(zhuǎn)化為直行路徑節(jié)點連接的局部最優(yōu)問題。此外，本文引入長度代價函數(shù)對貪心算法進行進一步約束，來限制貪心算法的節(jié)點搜索長度，長度代價函數(shù)如下:

其中，D為貪心算法的搜索距離，其值小于節(jié)點a與節(jié)點b之間的最小歐幾里得距離。

在圖6(a)中，不加直行路徑約束時，貪心算法規(guī)劃的轉(zhuǎn)彎路徑復(fù)雜、效率低下，且轉(zhuǎn)彎次數(shù)較多。在圖6(b)中，增加直行路徑約束時，貪心算法規(guī)劃的轉(zhuǎn)彎路徑簡單，可以實現(xiàn)局部優(yōu)化。

圖6 貪心算法原理Fig.6 The principle of greedy algorithm

3 仿真實驗與結(jié)果

在本節(jié)中，仿真分為兩部分。首先進行地圖建模仿真。該部分的仿真結(jié)果可以為后續(xù)CPP 算法的仿真提供精細的輸入；其次，對CPP 算法進行仿真。為了驗證兩個算法在小范圍復(fù)雜海洋環(huán)境下的可行性和高效性，本文選擇了兩種典型的復(fù)雜海洋環(huán)境作為仿真對象。第一類是包含多種密集障礙物的遠海區(qū)域的遙感圖像(圖7(a))；第二類是包含復(fù)雜海岸線與障礙物的近岸區(qū)域的遙感圖像(圖7(b))。

圖7 目標檢測結(jié)果對比Fig.7 The comparison results of target detection

3.1 基于YOLO V3 的地圖建模算法仿真

仿真的硬件環(huán)境為Intel 系列CPU i7，GPU:GeForce GTX3080Ti。系統(tǒng)環(huán)境為Ubuntu 18.04。為了公平起見，本文算法與比較算法的訓練的參數(shù)如表1所示。

表1 訓練參數(shù)設(shè)置Tab.1 training parameters setting

算法的評價指標為平均精度、輸出框面積比、檢測時間和召回率。輸出框面積比用來衡量地圖建模精準度，其公式如下所示：

其中，Sv為船舶輸出框的面積（即地圖模型中的黑色區(qū)域），S為遙感圖像的總面積，o為輸出框的面積例。o值越小，地圖模型的精度越高。

目標檢測仿真結(jié)果如圖7 所示。圖7(a)和圖7(c)為改進后YOLO V3 的檢測結(jié)果，圖7(b)和圖7(d)為改進前YOLO V3 的檢測結(jié)果。表2 為在包含200 張圖片的驗證集上計算得到的平均精度與召回率結(jié)果。

從表2 可以看出，改進后的YOLO V3 的平均精度比改進前的YOLO V3 提高了12.1%，召回率提高了18.6%。從圖7 中可以看出，圖7(a)中有9 個船舶障礙，圖7(b)中有4 個船舶障礙物都被準確檢測到。這證明了YOLO V3 的改進策略在海洋遙感圖像船舶檢測上是有效的。

表2 與改進前YOLO V3 結(jié)果對比Tab.2 results compared with the original YOLO V3

此外，需要將檢測完成后的圖像利用歸一化色差原理處理為二值圖，建立可輸入CPP 算法中的地圖模型。二值化地圖模型結(jié)果分析如表3 所示。

表3 o 值對比結(jié)果Tab.3 comparison results of o

從表3 可以看出，在2 個仿真場景中，利用改進的YOLO V3 的檢測結(jié)果建立的地圖模型，其o值都小于改進前的YOLO V3。在2 個仿真環(huán)境中，o最多下降了4.91%。綜上所述，改進的YOLO V3 能夠更準確地提取海洋遙感圖像中的船舶障礙物且可為CPP算法提供更精細的地圖模型。

3.2 路徑覆蓋算法仿真

路徑覆蓋算法的輸入地圖模型為圖7(a)與圖7(c)的二值圖像，其大小為800 像素×800 像素；路徑覆蓋應(yīng)用場景為：USV 資源探測，其傳感器掃描寬度為：10 像素。

算法的評價指標為覆蓋率、重復(fù)率、路徑長度、計算時間和轉(zhuǎn)彎拐點數(shù)。由于USV 在轉(zhuǎn)彎時必須減速和加速，所以轉(zhuǎn)彎時的平均速度要低于直線行駛時的平均速度。因此，拐點越少，USV 的路徑覆蓋效率越高。具體公式如下所示：

其中，Cr為覆蓋率，Rr為重復(fù)率，S為目標海域總面積，Sn為覆蓋面積，Sr為重復(fù)覆蓋面積。

為了驗證旋轉(zhuǎn)光束+貪心算法（本文算法）融合的優(yōu)越性，選取了“旋轉(zhuǎn)光束+概率路線圖[14]”算法，“旋轉(zhuǎn)光束+A*”算法作為對比，3 種算法依次記為：M1，M2，M3。其可視化結(jié)果如圖8 所示，在圖8 中選取了兩個場景進行對比，圖8(a)與圖8(b)為M1 的仿真結(jié)果，圖8(c)與圖8(d)為M2 的仿真結(jié)果，圖8(e)與圖8(f)為M3 的仿真結(jié)果，其中彩色線條為規(guī)劃的路徑，黃色虛線框為重復(fù)率較高的區(qū)域，橫坐標和縱坐標單位為像素。

圖8 所提算法與其他算法對比結(jié)果Fig.8 The comparison results between the proposed algorithm and other algorithms

從圖8(a)到圖8(f)中可以看出，由于概率路線圖與A*算法的隨機性較大，M2 與M3 算法規(guī)劃的路徑具有更多的重復(fù)率較高的區(qū)域?？陀^分析結(jié)果如表4所示，表格中的數(shù)據(jù)為取2 個地圖模型路徑覆蓋仿真結(jié)果的平均值。從表4 中可以看出，在覆蓋率方面，M1，M2，M3 算法規(guī)劃的路徑覆蓋率均達到100%。在重復(fù)率方面，本文算法的平均重復(fù)率為2.05%。與M2，M3 算法相比，平均降低了2.95%。驗證了本文所提的CPP算法在復(fù)雜海洋環(huán)境中具有較高的覆蓋率和較低的重復(fù)率，具有較好的可行性。在路徑長度方面，本文算法比M2，M3 算法的路徑長度要少，平均減少30%，驗證了本文算法具有更高的效率。綜上所述，在2 個不同仿真場景中，本文提出的算法模型在平均覆蓋率，平均重復(fù)率，平均長度，平均轉(zhuǎn)彎拐點與平均計算耗時上均更具優(yōu)勢。

表4 不同模型的結(jié)果對比Tab.4 comparison results of different models

此外，為了證明所提算法的優(yōu)越性，本文選取了文獻[9]基于柵格地圖的神經(jīng)元激勵算法作為對比，圖8(g)與圖8(h)為基于神經(jīng)元激勵的CPP 算法的仿真結(jié)果，其輸入地圖模型為柵格圖，網(wǎng)格大小為10×10。仿真圖中，紅線為規(guī)劃路徑，黃色區(qū)域為重復(fù)覆蓋路徑。仿真結(jié)果的評價指標對比如表5 所示。

從表5 中可以看出，在覆蓋率方面，本文算法和基于神經(jīng)元激勵的CPP算法規(guī)劃的路徑覆蓋率均達到100%。在重復(fù)率方面，本文算法的平均重復(fù)率為2.05%。與基于柵格地圖的神經(jīng)元激勵算法相比，降低了1.75%。本文提出的CPP 算法在復(fù)雜海洋環(huán)境中具有較高的覆蓋率和較低的重復(fù)率，具有較好的可行性。在路徑長度方面，本文算法基于柵格地圖的神經(jīng)元激勵算法的路徑長度要小，平均減少9.3%。在轉(zhuǎn)折點數(shù)量上，該算法的轉(zhuǎn)折點數(shù)量比基于柵格地圖的神經(jīng)元激勵算法少，平均減少71%。綜上所述，本文提出的CPP算法在復(fù)雜的海洋環(huán)境中具有較短的長度和較少的轉(zhuǎn)彎拐點，與基于柵格地圖的神經(jīng)元激勵算法相比，該算法效率更高。在計算耗時方面，該算法在2 種復(fù)雜海洋環(huán)境下的計算時間均小于基于柵格地圖的神經(jīng)元激勵算法，本文算法計算效率更高。

表5 與基于柵格地圖的神經(jīng)元激勵算法結(jié)果對比Tab.5 results compared with the neuron excitation algorithm based on grid map

4 結(jié)論與展望

本文提出了一種基于海洋遙感圖像的無人艇路徑覆蓋規(guī)劃方法。該算法將CPP 技術(shù)與遙感圖像目標檢測技術(shù)和圖像處理技術(shù)相結(jié)合，構(gòu)建了適用于小范圍復(fù)雜海洋環(huán)境遙感圖像的USV 路徑覆蓋系統(tǒng)。針對精細化環(huán)境建模問題，提出了一種改進的YOLO V3 算法，通過增加角度信息來增加目標框輸出維數(shù)，從而幫助CPP 建立更精確的地圖模型。此外，CPP 算法將全覆蓋路徑分為直行路徑和轉(zhuǎn)彎路徑，并根據(jù)路徑長度約束和轉(zhuǎn)彎次數(shù)約束進行計算。該算法規(guī)劃的路徑在時間、適用性、可行性和計算效率方面具有一定的優(yōu)勢。CPP 算法在處理大規(guī)模海域作業(yè)時尚有局限性。未來針對大規(guī)模海域高效作業(yè)可考慮多USV 協(xié)同技術(shù)。