復雜海戰場環境下AUV全局路徑規劃方法*

趙 苗，高永琪，吳笛霄，王 鵬，張洪剛

(1.海軍工程大學 兵器工程學院，湖北 武漢 430033；2.火箭軍工程大學 導彈工程學院,陜西 西安 710025)

自主水下航行器(Autonomous Underwater Vehicle,AUV)路徑規劃是保證其在水下安全隱蔽航行和可靠高效完成作戰任務的關鍵技術，AUV在執行水下作戰任務的路徑規劃中，需要充分考慮水下環境的不確定性和動態特性以及復雜海戰場下的戰場地形、自身性能、任務要求、外部威脅、水文信息等多種約束條件限制，近些年逐漸成了國內外學者研究的熱點。Li等[1]和Wang等[2]提出了一種基于可視性幾何理論的AUV水下路徑規劃算法，通過模擬典型的水下地理三維實體海洋模型，應用該算法仿真水下三維海洋環境，并進行水下路徑規劃。Gal[3]提出了一種改進的無人水下航行器(Unmanned Underwater Vehicle,UUV)通視圖空間搜索算法，它主要通過減少路徑節點的數量來提高算法的計算效率，并融入內部螺旋算法，成功實現水下避障。Arinaga等[4]將Dijkstra算法應用于水下環境中UUV的全局路徑搜索，結果表明，該算法可以避免一系列障礙并順利達到目的，但該試驗僅進行了模擬仿真，并未考慮海洋環境對路徑搜索的影響。A*算法是全局最短路徑搜索最有效的直接搜索解決方法，Li等[5]考慮了海洋環境因素的影響，并用A*算法實現了最優路徑的搜索。快速步進算法路徑節點間距離的更新采用非線性Eikonal方程簡化后的近似偏微分方程，具有較好的可靠性和收斂性。于暉等[6]考慮了UUV的機動約束，將快速步進算法應用于UUV在大范圍復雜戰場環境中，解決了UUV因導航安全和能耗問題而丟失的搜索路徑問題。趙云欽等[7]提出了基于帶電粒子模型的航路規劃方法，并成功地將該方法運用于UUV的航路規劃，有效地解決了多約束復雜海洋環境下的航路規劃問題。通過實驗表明，該方法能夠快速地為航行器規劃出可行航路。上述方法的共同缺點是，需要建立復雜的環境模型和未考慮海流等情況，更難以應用于復雜三維動態環境下的在線實時路徑規劃，搜索效率較低。

基于生物智能算法的航路規劃方法不必建立復雜的環境模型，在穩定收斂的同時，可以在自由空間進行隨機搜索。Jung等[8]將粒子群優化(Particle Swarm Optimization,PSO)算法的應用推廣到三維路徑規劃中，初始運動由當前位置與目標點的直線代替，通過最小化敵方威脅和燃料消耗獲得路徑最優解，最后利用B樣條曲線得到一條光滑的最優路徑。Moreno和Castro[9]提出一種增長的彈性神經網絡，用于計算路徑規劃解。該方法用自組織、網絡互連的神經元集合表示路徑，各處理單元用Kohonen網絡進行局部采樣與學習，采用簡單的強化規則進化避碰路徑，最終得到一條完整的路徑。基于生物智能算法的方法可以解決異常復雜的非結構化約束和各種難以近似處理的動力學約束等難題[10]，對于大范圍復雜環境下的AUV路徑規劃問題，生物智能算法仍是解決非確定性多項式(Non-deterministic Polynomial,NP)路徑規劃問題的有效方法。

1 AUV路徑描述和模型建立

1.1 AUV路徑的問題描述

(1)

式中：pi為S=(p1,p2,…,pn)中的路徑節點；J表示路徑的代價函數；Obstacle表示障礙物約束；Risk表示水下的敵方武器威脅。

1.2 AUV路徑規劃策略

AUV路徑規劃首先通過建立空間環境數學模型來表達路徑的搜索空間，并給出合適的代價評估函數，然后利用某種算法來尋求這種代價下的最佳路徑。減小搜索空間是快速高效地規劃出滿足AUV機動性能以及作戰要求路徑的重要手段，眾多文獻中往往只考慮二維平面內的路徑搜索，或是將水平面和垂直面分開路徑搜索，但這樣很難應用于AUV執行近海底突防、地形跟隨以及威脅回避任務。因此，借鑒文獻[12]中提出的無人機突防過程中最小威脅曲面的概念，將最小威脅曲面等效為AUV航行的最佳航行曲面。

假設水下地形可以用函數f(x,y)來表示，AUV避免撞底的最佳離底高度用Hc來表示，三維最佳航行曲面可表示為：

F(x,y)=f(x,y)+Hc

(2)

由于實際中獲取的水下地形數據是離散的，因此必須通過擬合或者插值的方法得到最佳航行曲面。此外，真實的海底地形復雜，在AUV水下航行中，考慮到AUV的自身機動性能限制，當突遇一個起伏較大的海槽或島礁時，由于近海底航行離地高度的限制，往往難以避開而發生碰撞。因此，構建的三維最佳航行曲面必須是一個光滑的曲面，Kriging插值算法是一種光滑的插值算法，采用該算法來構建三維最佳航行曲面。

給定起點和終點后，最佳航行曲面上的任意一條曲線都可以看作是一條規劃路徑，而每一條路徑在水平面內的投影也是一條曲線，只要找到水平面內的路徑投影曲線，即可在最佳航行曲面上找到相應的最佳路徑。文獻[13]采用B樣條曲線插值方法，在路徑規劃中只需給出幾個控制點就可以得到一條復雜的光滑曲線，然后通過對得到的B樣條曲線節點向量的非遞減參數等步長的均勻劃分，就可以得到一系列的路徑節點，這種方法把路徑規劃問題轉化為搜索幾個控制點的簡單問題，可以大大降低問題求解的維度。本文同樣采用B樣條曲線方法來描述投影路徑，通過確定N個路徑控制點來規劃一條路徑，則每個路徑控制點可由極坐標的方式來表示：

(3)

式中：Lst表示起點和終點在水平面內投影的距離；Xi、Yi分別表示第i個路徑控制點的橫、縱坐標；θi表示水平面內控制點到起點連線與起點到終點連線之間的夾角，其中θi∈[0,2π)。通過搜索N-2個角度值，便可得到N個路徑控制點，再通過B樣條曲線均勻劃分得到一系列的路徑投影節點序列(p′1,p′2,…,p′n)，最后通過投影的一一對應關系，即可在最佳航行曲面上找到相應的三維路徑節點序列(p1,p2,…,pn)，這樣就得到了AUV的近海底航行路徑。

1.3 路徑的約束條件和代價函數

1.3.1 路徑的約束條件

針對AUV大范圍海洋環境下的作戰背景，主要考慮以下幾方面的約束：

1)戰場地形約束。戰場地形約束主要指對海島、暗礁以及鉆井平臺、水下漂浮物等動靜態障礙物的避碰。本文所規劃的路徑均在水下地形數據構建的AUV三維最佳航行曲面上，在最佳航行曲面的構建中已融合了AUV避免碰撞的最佳離地高度，因此戰場地形約束只需考慮障礙物的避碰。將障礙物膨化為規則的圓柱體，障礙物的水平面圓心坐標(x0,y0)，深度上、下限坐標分別為zmax、zmin，障礙物的影響半徑為Or,則任一路徑節點pi(xi,yi,zi)必須滿足：

(4)

2)自身性能約束。為了提高所規劃路徑的可達性，需要考慮AUV的可操控性，包括最小轉彎半徑等方面的自身性能約束。因此，所規劃路徑曲率半徑的下確界必須大于AUV的最小轉彎半徑。采用本文所提方法規劃的路徑非常平滑，一般可以滿足AUV對轉彎半徑的要求。

3)任務要求約束。路徑規劃需要考慮完成作戰任務要求約束。任務約束要求包括航行時間和燃料消耗。假設AUV等功率勻速航行，則AUV單位時間的能耗是常數，也就是能量消耗正比于航行時間，則能量消耗和航行時間兩個目標等價。假設AUV實際航行時間為T，AUV完成作戰任務要求的最長時間為Tm max，AUV耗盡燃料的最長航行時間為Tmax，則必須滿足：

(5)

4)水文信息約束。水文信息約束主要是指海洋中溫度、鹽度、海流等對AUV航行的影響，本文主要考慮海流對AUV的影響。在海流環境中，不利的海流會直接降低AUV的航行速度，增加AUV完成任務的航行時間和能源損耗，甚至威脅AUV的航向安全；相反，有利的海流可以提高AUV的航向速度，實現快速節能。因此，海流對AUV的航行約束可以轉化為規劃路徑代價函數中的航行時間，以此來滿足海流的約束。

5)武器威脅約束。武器威脅約束主要是指敵方聲吶、海底水聽器的探測威脅和敵方水雷陣、反AUV等火力威脅。敵方武器威脅包括被敵方探測類武器偵察威脅和敵方火力殺傷威脅[14]。被敵方探測類武器偵察的時間和概率直接影響著AUV的航行安全，因此將敵方探測類武器偵察的有效時間作為規劃路徑代價函數的一部分。敵方火力殺傷威脅：一種是敵方布放水雷等殺傷性武器密集區域形成的禁航區，本文按照水下障礙物模型進行等效處理來滿足約束；另一種是敵方武器平臺攜載殺傷性武器的威脅，同樣轉化為代價函數的一部分作為優化目標進行約束。

1.3.2 路徑的代價函數

在對AUV進行路徑規劃之前，必須確定路徑規劃的性能指標。在AUV執行作戰任務過程中，希望AUV航行的路徑具有以下性質：規劃路徑航行時間盡量短，滿足作戰任務要求；規劃路徑被敵方有效偵察時間盡量少；規劃路徑被敵方有效殺傷的時間盡量少，滿足AUV自身航行的安全性。

1)航行時間代價：由上一節在AUV的路徑描述中，路徑中的節點坐標pi是采用B樣條曲線方法并通過一系列控制點生成的。研究使用的三維空間海流是由一組基于多重渦流和Navier-Stokes方程來模擬的[15-16]。假定在靜態海洋中AUV的速度是恒定的，海流的速度為VC，AUV的航行速度Va運動方向為從節點pi指向節點pi+1，則三個速度矢量的空間關系可由圖1具體描述。

圖1 AUV速度合成示意圖Fig.1 Schematic diagram of AUV speed synthesis

由圖1可知，海流速度VC的三個方向矢量(uC,vC,wC)可以表示為：

(6)

其中,θC、ψC分別表示海流速度在水平和垂直方向上的夾角。將AUV航行速度在水平和垂直方向上的夾角分別記作θ、ψ，AUV航行速度與海流速度的夾角為Φ，則AUV航行速度在三個方向上的速度矢量(u,v,w)和夾角Φ可以表示為：

(7)

由式(6)和式(7)可推導出：

(8)

則AUV的航行時間代價為：

(9)

2)敵方有效偵察時間代價：AUV的隱蔽性是其在海戰場中執行作戰任務最重要的戰技術指標之一，因為被敵方聲吶探測偵察很可能會導致作戰任務失敗，甚至對作戰造成不可估量的損失。因此，在路徑規劃中必須考慮在執行任務時被敵方聲吶有效偵察時間，具體可以表示為：

(10)

3)敵方有效殺傷時間代價：在AUV執行任務時，敵方殺傷性武器裝備的部署直接對AUV造成威脅，因此敵方殺傷性武器對AUV的有效殺傷時間是路徑評價指標的重要組成部分。敵方有效殺傷時間代價可以表示為：

(11)

在AUV路徑規劃時，需要滿足并且最優化上述提到的所有性能指標，但是要使所有性能指標都達到最優是不可能的，因為某些目標就是矛盾的，比如安全性和航行時間。通常的做法是使用加權求和法。因此，本文選擇的代價函數J為：

(12)

其中，w1、w2、w3分別表示AUV航行時間、被敵方有效偵察時間和有效殺傷時間的權重系數，權重系數一般通過多次試驗給定。在這里需要特別說明的是，本文假定在兩個連續路徑節點pi和pi+1之間的任意路徑點的海流速度、被敵方偵察的概率、殺傷概率與路徑節點pi+1處完全相同。

2 基于振蕩型IWO算法的全局路徑規劃

本文中AUV的航行路徑是一條在水平面內投影為一組控制點定義的B樣條曲線構成的三維路徑。在給定起點和終點后，路徑規劃問題的本質轉化為通過優化算法來尋找一組最優控制點的問題。在路徑規劃中遇到密集的障礙物、起伏較大的地形區域等情況時，將導致可行路徑解的空間范圍變小，使得算法在搜索路徑時很容易陷入局部最優解，導致規劃路徑的質量降低或無效路徑的產生。IWO算法是Mehrabian和Lucas于2006年提出的一種從自然界野草進化原理演化而來的隨機搜索算法[17]。2010年，Basak等提出了一種改進型的振蕩型IWO算法[18]，在計算標準方差(Standard Deviation,SD)的過程中引入一個振蕩因子|cose|，使得算法得在全局搜索和局部搜索并行展開，相比IWO算法，全局尋優能力和快速收斂性都得到了極大的提升。因此，本文采用振蕩型IWO算法作為路徑規劃的搜索算法。

2.1 基于振蕩型IWO算法的路徑規劃基本原理

路徑規劃問題的最終目標是要在規劃空間中得到滿足要求的一個解向量。因此在振蕩型IWO算法中，每株野草的位置都被視為規劃空間中的一個解，并且解代表的路徑優劣程度由上文的路徑代價函數來進行度量。通過代價函數值計算每株野草產生的子代數量，每株子代野草的位置由父代野草的位置和當前代的標準方差值決定，通過不斷淘汰適應度值差的野草，更新標準方差值，提高算法的收斂速度和自適應能力。記野草的初始種群數量為A，它由n株野草組成：{a1,a2,…,an}，每株野草aj=(θ1j,θ2j,…,θnj)代表規劃空間中的一條航路。對于任意一株野草aj，可以計算得到該野草所代表航路的代價函數fj。同樣對于整個野草種群，其中每株野草位置的代價都可以根據式(13)計算得到：

f=[f1,f2,…,fn]

(13)

故而可以根據代價函數值得到該野草種群中適應度最好的野草abest和最差的野草aworst，以及它們的代價函數fbest和fworst：

(14)

適應度較好的野草相比于適應度較差的野草應該在搜索尋優過程中發揮更重要的作用。因此，每株野草產生后代的數量可以和代價函數值關聯起來。在迭代過程中，每株野草產生的子代數量、子代野草的位置以及當前代的標準方差更新計算方法如下。

1)種子產生的數量。對于野草aj產生種子依據本身以及野草種群中適應度最好的野草abest和最差的野草aworst計算每株野草繁殖種子的數量：

(15)

式中，[·]表示取整。

可以看出，適應度值越好的野草其代價函數值越小，所產生的種子數量越多。這使得種群中適應度越好的野草越來越多，進而使適應度較差的野草被淘汰。

(16)

其中，normrnd(aj,σe)是以aj為均值，σe為方差的正態分布隨機數。

(17)

2.2 基于振蕩型IWO算法的路徑規劃步驟

基于振蕩型IWO算法的路徑規劃方法具體步驟描述如下。

步驟1：根據實際問題設置選擇合適算法參數需要確定種群的初始數量Pinitial、種群的最大數量Pmax，最大迭代次數emax、最大和最小種子數量Smax和Smin、非線性指數n、標準方差的初始值σinitial和最終值σfinal以及算法終止條件。

步驟2：根據路徑規劃任務的要求設置算法問題維數D，野草種群初始化，初始化每株野草位置。

步驟3：根據設定的代價函數，按規則計算出每株野草的適應度值，并計算出種群中適應度最好的野草的代價函數值fbest和最差代價函數值fworst。

步驟5：當種群數量達到上限時，對種群中所有的野草按代價函數值大小排序進行淘汰，保留適應度值最好的Pmax株野草。

步驟7：判斷是否到達最大迭代次數emax，如果沒有，返回到步驟4，否則算法結束。

步驟8：輸出全局最優代價函數值的野草所代表的航路。

3 仿真結果與分析

將式(12)采取的代價函數作為優化目標為AUV搜索全局最優路徑；每種算法運行100次，通過蒙特卡洛模擬實驗，對IWO算法、振蕩型IWO算法、全振蕩型IWO算法以及粒子群算法四種路徑規劃算法計算所得的路徑平均代價值和標準方差進行比較。

計算機仿真平臺為MATLAB 2016a，處理器為酷睿i7-3630QM，@2.40 GHz，RAM8 GB，操作系統為Windows7-64位。標準IWO算法、振蕩型IWO算法、全振蕩型IWO算法以及粒子群算法四種算法的種群規模統一設置為N=30，最大迭代次數emax=500，控制點的個數統一設為12，則問題的維數D=10，算法的參數設置如表1所示。

表1 算法的參數設置Tab.1 Parameter settings of the algorithm

仿真試驗選取116.8°E～117°E，23°N～23.2°N區域為路徑規劃區域，水下地形的原始數據采用美國Scripps海洋研究所公布的分辨率為1海里的數據。首先利用移動Kriging插值算法獲得分辨率為100 m的水下高程地形數據，利用Kriging插值算法構建AUV最佳航行曲面。這里需要特別說明的是，考慮到獲得的水下地形數據分辨率較高，本文將任務區域的經緯度坐標轉換后縮小為原來的1/100形成實驗的水下地形，這樣可以更加直觀真實地反映水下威脅的探測范圍，便于仿真試驗的開展和研究；AUV的航行速度設置為9.252 m/s；海流采用20個渦流疊加而成，敵方武器威脅由水雷等密集布放的武器平臺構建的禁航區、敵方水面艦艇和潛艇來模擬；障礙物由水中漂浮物來模擬。具體水下威脅模型參數設置如表2所示。

表2 水下威脅空間的參數設置Tab.2 Parameter settings for underwater threat space

設置任務的起點為(132 800 m,25 360 m,-80 m)，終點為(133 300 m,25 500 m,-80 m)，分別設置算法的種群初始數量為10、20，仿真得到的AUV規劃路徑如圖2、圖3所示，不同算法的代價函數值收斂曲線和各路徑性能指標分別如圖4和表3所示，不同算法參數下的最優路徑、路徑的平均代價函數值和標準方差如表4所示。需要特別說明的是，仿真圖中藍色線條構成類半球狀圖形表示武器平臺的最大探測范圍，紅色線條構成的類半球狀圖形表示武器平臺殺傷性武器的殺傷范圍，黃色圓柱體表示禁航區的范圍，青藍色圓柱體表示障礙物的影響范圍。

圖2 不同算法規劃的最優路徑三維立體圖Fig.2 Three-dimensional perspective of the optimal planning path of different algorithms

圖3 不同算法規劃的最優路徑三維俯視圖Fig.3 Three-dimensional top view of the optimal planning path of different algorithms

圖4 不同算法的代價函數值收斂曲線Fig.4 Cost function value convergence curve of different algorithms

表3 不同算法最優規劃路徑的性能指標值Tab.3 Performance index values of optimal paths of different algorithms

表4 運行100次不同規劃算法的路徑代價比較Tab.4 Path cost comparison of different planning algorithms running 100 times

通過圖2、圖3可以看出，采用四種算法為AUV規劃出的最優路徑均能繞過敵方探測、火力威脅以及禁航區，并成功躲避水下障礙物后安全抵達任務終點。在不同算法規劃路徑的代價函數值差別不大時，振蕩型IWO算法比標準IWO算法規劃的路徑長度長7.665 m，航行時間少了0.108 s，這說明振蕩型IWO規劃的路徑較好地利用了海流來引導AUV航行，增大了航行速度，從而減小了航行時間。通過表4可以看出，選取標準IWO算法、振蕩型IWO算法、全振蕩型IWO算法的初始種群數量為10、20，粒子群算法的初始種群數量為20，分別運行100次，發現標準IWO算法存在陷入局部最優的現象，而振蕩型IWO算法規劃最優路徑優于其他三種算法，平均路徑代價振蕩型IWO算法最優。從標準方差來看，振蕩型IWO算法的穩定性也更好，這是由于振蕩型IWO算法的標準方差隨著迭代次數的增加呈振蕩衰減的趨勢，當在迭代初期，如果野草靠近一個可疑的最優解，引入一個振蕩因子后就會使標準方差處于相對較小值，從而實現快速的局部搜索，而不是等到迭代后期標準偏差降低到一個合理的值再進行，這樣有很大的概率可快速地發現較優解，使得算法在迭代初期也可以進行局部搜索，提高了IWO算法的尋優能力，因此基于振蕩型IWO算法路徑規劃方法的規劃效果最好。

4 結論

本文介紹了基于振蕩型IWO算法的AUV路徑規劃方法的基本原理，結合復雜海戰場環境，提出了一種以構建最佳航行曲面為條件，基于振蕩型IWO算法的三維路徑規劃方法。仿真實驗表明，該方法可以高效、準確地為AUV水下作戰任務規劃出一條滿足性能要求的最佳路徑。該方法未來可以廣泛應用于AUV執行各種水下近海底突防、地形跟隨以及威脅回避等不同作戰樣式下的全局路徑規劃任務。