輻射掃描算法在無人船航跡規劃中的應用

路春暉, 尹美琳, 付振楷, 李興盛, 張嘉琪

(天津理工大學 環境科學與安全工程學院，天津 300380)

0 引 言

目前，人們對海上無人船的研究越來越感興趣。通過派遣無人船執行危險任務會大大降低人員受傷的風險[1]。在無人船應用中，一個部署是環境監控，在高度污染的湖泊中，可以通過無人船來有效地收集水樣采集數據，而不會將人類暴露于有害元素之中;另一個潛在的應用是災后場景中的搜救任務。在多次實驗中已經證明，無人船可以有效縮短響應時間，增加救援任務的成功率[2]。而簡單、有效、快速的航跡規劃算法成為提高任務成功率的重要保障。目前，常用的航跡規劃算法主要有A*算法[3-5]、人工勢場算法[6-7]、粒子群算法[8-10]和蟻群算法[11-12]等。

本文針對傳統路徑算法的思路和現有缺陷進行研究，尋求一種新型路徑規劃方法。在起點和終點之間存在障礙物的情況下，向兩側掃描獲取周圍障礙物信息，用以獲取最短路徑。通過使用LabVIEW2017平臺編寫了算法仿真軟件，進行仿真實驗，最終確定路徑規劃算法的可靠性。

1 環境模型的建立

在規劃無人船全局路徑時，首先針對已知信息進行環境空間建模[13]，根據建模結果獲得包含環境的搜索空間。本文采用柵格法作為建模方法表示障礙物，將規劃路徑的區域劃分成大小相同的柵格，原本有障礙物的柵格標記為不可行區域；剩下的柵格就是正常情況下的可行區域。

1.1 柵格粒度的確定

在利用柵格法進行空間環境建模過程中，柵格粒度的確定影響著路徑規劃的準確性[14]。柵格粒度的取值如果過小，將會造成環境空間的信息量過大，使系統負擔過大；柵格粒度的取值如果過大，當障礙物較多時，將導致無法找到有效路徑。

將柵格粒度的確定與環境中障礙物的疏密程度相結合，粒度的大小可以通過計算各障礙物面積的總和與計算整體環境的面積來獲得。計算障礙物的面積時，對于不是矩形的障礙區域，對障礙物邊緣進行擴充，以構成矩形區域，并將擴充部分一并算為障礙物進行考慮。

確定柵格粒度的具體方法：通過將各個障礙物矩形化，確定各個障礙物的面積，利用Sz=∑Sn計算障礙物總面積,其中：Sn為第n個障礙物的面積；Sz為障礙物總面積。確定柵格粒度：

式中：S總為需規劃二維空間的面積；lmax為柵格坐標系的長度；lmin為人為限定的柵格最小邊長；l為經計算所得的柵格邊長(柵格粒度)。

1.2 柵格空間布局

在二維路徑規劃空間中，將水平右方向設置為正x軸方向，水平向上方向設置為正y軸方向。以這種方式構造了二維空間直角坐標系。柵格分為兩種類型，第1種類型在其覆蓋范圍內不含任何障礙物；第2種類型在其覆蓋范圍內含有障礙物。將第1種柵格稱之為自由柵格，用白色表示；第2種柵格稱為障礙柵格，用黑色表示(見圖1、2)。

圖1 未處理前柵格障礙物形狀

圖2 處理后柵格障礙物形狀

2 輻射掃描算法原理、模型及優化

2.1 輻射掃描路徑規劃原理

在起點與終點之間存在障礙物的情況下，起點沿障礙物向兩側進行掃描，得出子節點。再由子節點向終點方向進行掃描，若存在障礙物，則繼續沿起點之前的掃描方向掃描，得出下一代的子節點。子節點再掃描下一代子節點時，已經被掃描過的子節點將不會再被定義為子節點。掃描到終點為最后一代節點，掃描過程終止，每代子節點依次反選，最后反選回起點，得出最短路徑。

2.2 算法實現

Step1建立環境模型，確定柵格粒度，設置障礙柵格、可行柵格、起始柵格、目標柵格。

Step2從起點向終點方向發射射線，掃描路上有沒有障礙(注意：射線真實寬度不是1，而是單個柵格的邊長)。

Step3碰到障礙物后，生成兩條射線向兩側掃點，以原向量角度沿障礙物邊界前進，為起點到該點的新向量。

Step5比較該方向掃描新向量的長度與舊向量長度，當差值超過單位柵格粒度時，則判斷當前位置存在可走空間。

Step6此時，在判斷有可走空間的位置，被阻擋的可行柵格向射線方向下一個柵格建立子節點。

Step7子節點只需向外發射一條射線，新掃描的柵格需要不斷判斷是否超過了上級起點的掃描范圍。如果超過，則上級起點也需要繼續掃描(防止出現迷宮里的死胡同問題，同時防止所走路線并非最短路徑)。

Step8如果沿障礙物前進所更新向量位置坐標的柵格不是障礙柵格的話，則需要該點到起點方向的向量的下一個柵格建立子節點。

Step9當沿障礙物掃描方向又出現不可行柵格時，則判斷遇到內拐點，此時由原向量向邏輯掃描方向(一條射線為順時針；另一條為逆時針)轉動90°，繼續掃描。

Step10重復當前所有步驟進行掃描。

Step11到達終點后，從終點開始反向連接父節點，直至回到起點，尋路完成。

2.3 輻射掃描算法模型

建立環境柵格，在環境模型中，設點(13,17)為要規劃路徑的起點，目標為(13,4)點。從起點(13,17)出發，向終點(13,4)發射射線，發現中間有障礙物(見圖3)。由于起點(13,17)到終點(13,4)中發現障礙物，那么程序將生成兩條射線向兩側掃描(見圖4)。

掃描過程中發現在點(15,11)處，掃描射線的新向量與舊向量長度差超過1柵格寬度，判斷此處有缺口。點(15,11)為射線中心遇到障礙物前的最后一個柵格。這時在點(15,11)向射線方向下一個柵格點(15,10)建立子起點(見圖5)。

圖5 建立一級子節點圖

點(15,10)只向外發射1條射線，首先判斷此點與終點之間是否存在障礙物，若存在則按上級點(這里的上級點是起點)掃描方向繼續掃描，并且不斷判斷是否超過了上級起點范圍，如果超過則上級起點也需要掃描。點(15,10)掃描到障礙物點(17,9)時，開始超過起點(13,17)的掃描范圍，那么起點也繼續掃描(見圖6)。

起點(13,17)掃描過程中至點(21,12)處由不可行柵格變為可行柵格，判斷該點到起點方向的向量的下一個柵格(21,13)建立子節點(見圖7)。而點(15,10)由于掃描角度變化一周后無子節點而被舍棄。重復上述步驟，依次在點(21,13)、(23,11)、(23,8)、(21,6)、(18,4)、(16,2)、(13,2)建立子節點，點(13,2)向終點(13,4)發射射線，發現無障礙物?？芍苯拥竭_終點，則掃描過程結束(見圖8)。

圖6 起點與一級子節點同時掃描圖

圖7 建立二級子節點圖

圖8 掃描終止后路線圖

最終程序尋找出的路徑為：起點(13,17)至(21,13)至(23,11)至(23,8)至(21,6)至(18,4)至(16,2)至(13,2)至 終點(13,4)(見圖9)。

圖9 掃描算法所尋路線圖

2.4 輻射掃描算法的優化

通過實例分析不難看出，障礙物分布與子節點的位置關系為左上、左下、右上、右下4種位置關系。當尋找的路徑通過了子節點和其周邊障礙物方格所夾方格時，則可忽略子節點，直接將兩個所夾方格相連。如圖10所示，點(21,13)為黃色子節點柵格，點(20,12)為其周邊障礙物柵格，并在其右上位置。點(21,13)與點(20,12)相夾柵格為(21,12)和(20,13)，通過圖10不難看出所規劃路線需經過(21,12)和(20,13)兩點。那么當尋路完畢后，從起點沿著所尋路徑發射信號，當到達點(20,13)時，跳過子節點(21,13)直接走到點(21,12)。最終規劃路徑(見圖10)。

圖10 射線掃描算法最終規劃路線圖

3 仿真實驗

為了驗證輻射掃描算法的正確性，用C++實現了算法，并將其封裝到動態鏈接庫中，在LabVIEW 2017開發環境下做程序主界面并調用C++庫。仿真軟件主界面如圖11所示，左側用來顯示無人船工作環境，圖中顯示的是天津于橋水庫。路徑規劃的結果會直接繪制在地圖上，并且在右側顯示規劃的路徑中包含的GPS坐標和算法耗時。為了方便使用，軟件在內部對GPS坐標和柵格模型的序號之間做轉換，所以軟件的輸入和輸出均是GPS坐標，不需要用戶手動輸入起點和目標所在柵格的序號。

圖11 仿真軟件界面

使用明理湖和于橋水庫的GPS坐標生成的柵格模型做了大量仿真實驗。明理湖的每個柵格的邊長是10 m，柵格模型共75行70列；于橋水庫的每個柵格邊長40 m，柵格模型共198行428列。仿真結果如圖12、13所示。

圖12、13中的紅色圓點是路徑規劃的起點和目標。可以看出：在明理湖中測試，規劃的路徑繞開了湖中的湖心島，是一條近似最優的路徑。在于橋水庫中的測試規劃的路徑也避開了水庫的邊緣，也是一條近似最優的路徑?？梢钥闯觯诓煌沫h境、起點和目標的情況下，算法均能正確地規劃出一條避開障礙物的路徑。

圖12 明理湖仿真實驗

圖13 于橋水庫仿真實驗

實際情況下，無人船的航程常常會達到數km至幾十km。為了比較在長距離情況下輻射掃描算法的性能和魯棒性，將柵格蟻群算法和離散蟻群算法進行對比，并在于橋水庫做了長距離路徑規劃的仿真。仿真實驗中算法的起點和目標相同，仿真結果如圖14所示。

(a)柵格-蟻群算法

(b)離散-蟻群算法

(c)輻射掃描算法

從圖14可以看出：柵格-蟻群算法在長距離下雖然可以工作，但輸出的路徑曲折迂回，沒有實際使用價值。離散-蟻群算法由于步長可以自適應調節，所以在長距離下仍然可以正常工作。輻射掃描路徑規劃算法規劃的路徑最短，表現最優。

4 結 論

針對海上無人船執行任務的特點及存在的問題，通過仿真程序對幾十種不同地形圖進行仿真實驗，實驗結果表明。

(1)在環境模擬場所利用改進后的掃描算法規劃路徑是安全可行的，該算法既能保證避開障礙物，也可以實時動態避開危險區域。

(2)相較蟻群算法能夠規劃出更短的路線。

(3)在較為復雜的近海領域，有待進行深一步研究。

航跡規劃為無人船提供航線，具體如何航行需要導航避障系統和控制器協作配合完成。不僅如此，無人船在水面航行還會受到自身狀態、傳感器噪聲、風浪和天氣等因素的影響[15]。對無人船航跡規劃還有很大的研究空間。