基于帶電粒子搜索的無人潛航器航路規劃方法

趙云欽，蔡 超，王厚軍，李東武

(1.多譜信息處理技術國家級重點實驗室(華中科技大學 自動化學院)，武漢 430074；2.國家海洋技術中心，天津 300112； 3.天津航天中為數據系統科技有限公司，天津 300450)(*通信作者電子郵箱caichao@hust.edu.cn)

0 引言

無人潛航器(Unmanned Underwater Vehicle, UUV)是一種能在水下自主遠程航行的智能化裝置，它能夠完成水下搜尋、偵察，甚至是軍事上的進攻防守等任務[1-2]。如今海洋開發日益加快，無人潛航器得到了各個國家的重視，不管是在軍事領域還是在民用領域都發揮著越來越重要的作用。航路規劃是UUV研究領域中的熱點問題之一，它是指在綜合考慮航行器自身性能、能量損耗、威脅以及航行區域限制的情況下，在起始點和目標點之間規劃出一條最優或可行的航路[3]。

UUV航路規劃具有規劃區域廣闊、環境復雜、約束條件多等特點，這就對航路規劃算法的收斂速度、內存空間需求都有比較高的要求。國內外學者在航路規劃算法方面作了許多研究工作，也提出了多種航路規劃算法。Kanehara等[4]通過采用地圖格網化的方法將航路規劃問題離散化，然后采用A*算法找到最短路徑；但是A*算法作為一種確定性算法，它的計算復雜度和規劃時間將隨著規劃區域的增大也將大幅上升。也有學者采用隨機性算法進行航路規劃，如Khelchandra等[5]提出一種基于隨機采樣的航路規劃方法，該方法雖然能夠以比較高的概率在短時間內規劃出一條路徑，但是也有可能規劃出一條不可行的路徑；Tarokh等[6]采用的遺傳算法，但是由于各種約束的存在，該方法會出現早熟而導致得不到最優解；Englot等[7]也提出了基于蟻群算法的航路規劃方法，但對于連續的規劃空間，算法收斂速度慢，規劃用時長；而粒子群優化(Particle Swarm Optimization, PSO)算法[8]參數設置比較復雜，局部搜索能力不佳，收斂速度慢。

帶電粒子搜索算法最早在2010年由Kaveh等[9]提出，它源于物理學中庫倫定律和牛頓定律的啟發，通過搜索空間中帶電粒子的相互作用，進而達到尋優的目的。該算法對于優化問題在保證解質量的同時可以得到更快的收斂速度。自帶電粒子搜索(Charged System Search, CSS)算法提出以來，已經在多個領域得到了應用。Kaveh等[10]將CSS算法離散化并將其用于框架結構優化問題的求解；?zy?n等[11]將該算法用于電力調度問題，以減少傳輸消耗和NOx等有毒化學物質的釋放；Precup等[12]將該算法用于模糊控制器的優化。

本文將帶電粒子搜索算法與航路規劃問題相結合，提出一種基于帶電粒子搜索的航路規劃方法。本文對航行器航路規劃問題進行建模，采用標準矢量電子海圖作為搜索空間，使用實數編碼的帶電粒子來表示航路，通過建立代價函數將多約束、復雜海洋環境下航路規劃的多目標優化問題轉換為單目標優化問題，并用該方法對最終的單目標問題進行優化求解。實驗分析表明該方法在保證規劃出的航路質量的同時，收斂速度快、規劃耗時短。

1 UUV航路規劃問題及模型建立

1.1 UUV航路規劃問題

UUV航行在復雜的海洋環境中，為了保證航行器的安全航行不僅要考慮到海洋自然環境約束(如：洋流、風浪、海底地形等)，還需考慮導航區域約束、戰場環境約束等。航路規劃要在綜合考慮多種因素的條件下，為航行器規劃出一條安全的，能夠順利完成目標任務的航路，因此航路規劃問題實質上是一個帶約束的多目標優化問題：

目標函數 minfit(X)=[f1(X),f2(X),…,fn(X)]T

約 束gi(X)≤0;i=1,2,…,p

hj(X)=0;i=1,2,…,q

Xl

決策變量X={X1,X2,…,Xm}

其中：Xl、Xu分別為決策變量X的下界和上界，決策變量的邊界值就構成了目標問題的決策空；fi(X)(i=1,2,…,n)表示n個需要被同時優化的目標函數；gi(X)≤0(i=1,2,…,p)表示p個不等式約束函數；而hj(X)=0(i=1,2,…,q)表示q個等式約束函數。

多目標優化問題往往包含了多個相互耦合的目標函數，它可能沒有唯一的最優解，而是一個包含無窮多個解的解集。最后，決策者需要對Pareto解集中的解作比較并進行選擇，因此，UUV航路規劃中的模型建立和代價函數設計就是其中尤為關鍵的兩個部分。

1.2 模型建立

UUV在海洋環境中航行時，會受到自身物理性能限制[13]，主要有以下幾個方面：

1)航行器轉彎約束：UUV轉彎時，最大轉彎角度不能超過θmax，最小轉彎半徑不能小于Rmin：

2)安全航行深度約束：為了保證UUV的航行安全，其航行深度h應該小于當前位置海洋深度hsea，0

3)最大航程約束：UUV由于機載能耗有限，所以航路距離l不能超過其最大航程lmax，l

4)上浮約束：UUV在沒有海洋浮標的海域中，為了能夠及時校正航路偏差，可以采用讓UUV上浮與衛星進行通信的方法，因此，航路需要在除風浪區以外的位置每隔一定時間設置一個上浮點使UUV完成衛星通信。

海洋環境復雜且范圍廣，合適的地圖環境描述與存儲方式對規劃精度和速度都有重要的影響。本文采用的是標準的矢量電子海圖來描述環境信息，它將海域中的每個要素都以點、線、面等幾何元素的形式存儲下來，相比柵格電子海圖具有存儲量小、精度高等優點，并且當環境發生改變時，用戶可以方便地在基礎數據上進行修改更新。

由于海洋環境復雜，而環境因素對UUV航路規劃影響很大。為了便于算法的模擬計算，本文將海洋環境表達為以下幾種約束區域模型。

1)限制區：島嶼、禁飛區、暗礁等航行器不可達的區域，在本文中用凸多邊形來描述限制區。

2)威脅區：在某些區域，敵方在一些區域會部署雷達、防御武器等，這對航行器的安全性產生威脅，在航路規劃時應盡量避開這些區域。本文用橢圓來描述威脅區，當航行器進入這類區域時，航行器有一定可能被攔截摧毀。穿過的威脅區的威脅等級越高，航行器被攔截的概率越大。

3)海流區：在海洋中的不同區域、不同深度海流的大小和方向是不同的，這對航行器的速度矢量產生影響，因此，在航路規劃時必須考慮到海流因素的影響，航行器在海流區中的航行速度是正常巡航速度與海流速度的矢量疊加。

4)風浪區：在某些海域表面，由于風的作用會引起海水的波動。航行器在這類區域上浮將會對自身安全性造成影響，因此在風浪區航行器不能進行上浮以及與衛星進行通信操作。由于在此區域無法進行通信進而對當前航線進行誤差矯正，這就會使航行器偏離既定航路。為了保證航行器的安全準確航行，需要繞過風浪區航行。

1.3 航路表示與代價計算

根據不同的實際要求、不同抽象層次，航行器的航路可以表達成多種形式。Capozzi[14]提出幾種典型的航路表達形式：

1)航行器空間位置點序列；

2)航行器速度和方向的時間序列；

3)航行器機動動作的時間序列；

4)任務級的抽象航路。

這四種航路表達方式抽象程度依次增加。無論采用什么表達形式，都應以有利于航路規劃計算與航路的準確表達為首要目標。本文采用空間位置點序列表示航行器航路，例如：S表示起始點位置，T表示目標點位置，X1,X2,…,Xm為中間航路點位置，航路就可以表示為：

{S,X1,X2,…,Xm,T}

因此航路規劃問題實質上是在規劃空間中找到一個滿足要求的m維的解向量。

本文綜合考慮了UUV的航程、海流、威脅等因素，將代價評估函數設置如下：

(1)

其中,f(xi)表示航路段xi的代價，它由時間代價ft和威脅代價fs組成。

2 基于帶電粒子搜索的航路規劃方法

2.1 CSS算法描述

帶電粒子搜索算法受到庫倫定律和牛頓定律的啟發，利用帶電粒子之間的相互作用來進行尋優，是一種具有全局搜索能力的智能算法。與蟻群算法、粒子群算法等智能算法相比，該算法中每個帶電粒子之間有更多的信息交流，它具有較強的全局搜索能力和更快的收斂速度等特點。

該算法首先會在規劃空間中隨機初始化一組初始解(稱為初始帶電粒子群)P={p1,p2,…,pn}，每個帶電粒子pi都被看成為一個半徑為a的帶電球體，其所帶電荷量qi由代價函數值確定，它將會在其周圍區域產生一定強度的電場，如圖1所示。在電磁場中帶電粒子的電荷量越大，該帶電粒子對其他帶電粒子的吸引力就越大，通過電場力的影響，每個帶電粒子在規劃空間中進行尋優。在本方法中，利用代價值來間接表征帶電粒子的電荷量大小，電荷量越大則對其他帶電粒子的吸引力就越強，其他帶電粒子從該粒子繼承信息的繼承度就越高。

圖1 電場強度示意圖

根據庫倫定律，帶電粒子在電場中會受到電場力的作用，如下式所示：

其中：Eij表示電場強度；qj表示帶電粒子j的電荷量；ri和rj分別表示帶電粒子i，j的空間位置，因此在搜索空間中，帶電粒子會受到其他粒子產生的電場的影響，進而在空間中進行移動尋優。在每次迭代時，帶電粒子根據如下式進行位置、速度更新：

Xj,old

Vj,new=(Xj,new-Xj,old)/Δt

其中:ka是加速度系數，kv是速度系數；Fj是帶電粒子j所受電場力合力;Δt是時間步長;Xj,new、Vj,new分別為位置和速度矢量；randj1和randj2都是均勻分布在(0，1)上的隨機數。該方法通過計算其他帶電粒子施加給當前粒子的合力來確定該帶電粒子更新后的位置、速度等。重復迭代過程，直至滿足定義的算法終止條件后，停止迭代并得到優化問題的解。

2.2 基于CSS的航路規劃方法

由1.3節的分析，航路規劃問題最終目標是要在規劃空間中得到滿足要求的一個m維的解向量；因此在本文方法中，每個帶電粒子都被視為規劃空間中的一個解，并且解代表的航路的優劣程度由上文航路代價部分描述方法來進行度量。通過代價值再對每個帶電粒子自適應更新其所帶電荷量，提高算法的收斂速度和自適應能力。記帶電粒子集合為P，它由n個帶電粒子組成：P={p1,p2,…,pn}，帶電粒子pi代表規劃空間中的一條航路。對于任意帶電粒子pi，可以由式(1)計算得到該帶電粒子所代表航路的代價函數值fiti，故帶電粒子集合的代價為：

fit=[fit1,fit2,…,fitn]

因而可以根據代價函數值得到該帶電粒子群中的最優帶電粒子pbest和最差帶電粒子pworst，以及它們分別的代價函數fitbest和fitworst：

pbest=min(fit1,fit2,…,fitn)

pworst=max(fit1,fit2,…,fitn)

較優的帶電粒子相比較差的粒子應該在搜索尋優過程中發揮更重要的作用，因此，帶電粒子電荷量大小可以和代價函數值關聯起來。

在迭代過程中每個帶電粒子的電荷量、電場力以及位置速度計算方法定義如下：

1)電荷量。對于帶電粒子pi，將其電荷量qi通過上文定義的代價函數值，采用歸一化的方法來進行定義：

(2)

可以看出越優的帶電粒子其代價函數值越小，而所帶電荷量越大。這使得該帶電粒子對其他的粒子產生更大的電場力，進而使較差的粒子朝著較優的粒子運動。

2)帶電粒子間距離。本文所考慮優化問題的解空間是一個m維空間，其中任意兩個帶電粒子pi、pj的距離采用如式(3)進行計算：

(3)

其中：Xi、Xj分別是帶電粒子pi和pj的位置，都是一個m維的向量；Xbest是當前最優粒子pbest的位置;ε是個極小正數，防止分母為0。

3)電場力。帶電粒子所受電場力合力的計算可將當前帶電粒子所獲得的局部和全局信息有效地結合起來，為航路規劃算法優化搜索提供依據。帶電粒子pj在維度k上所受電場力合力：

(4)

其中i1、i2為：

pij表示帶電粒子pj受到粒子pi電場力的概率：

其中rand是在(0，1)范圍內均勻分布的隨機數。根據矢量疊加，最終可以得到帶電粒子pj所受到的電場力合力Fj：

Fj=[Fj1,Fj2,…,Fjm]

在最初的迭代搜索過程中，帶電粒子彼此之間離得都比較遠，而此時庫侖力反比于帶電粒子距離的平方。在這種情況下，早期的迭代過程中帶電粒子會進行更多的全局搜索，因此算法具有較強的探索能力。對于隨機性算法而言，在算法開始的時候增強全局搜索能力，隨著迭代的進行減小這種全局搜索是必要的。經過一系列的迭代搜索過后，帶電粒子聚集在一個小的區域，故而帶電粒子間的距離變小，此時帶電粒子所受到的電場力合力正比于帶電粒子距離，開始進行精細的局部搜索，并且，這個階段帶電粒子所受電場力合力始終正比于其電荷量。較優的帶電粒子具有較小的代價函數值，故而帶有較高的電荷量，在它的周圍將會有較大的電場強度；也就相對于較差的帶電粒子而言，它對其他的粒子將會產生較大的吸引力，所以帶電粒子朝著好的粒子運動的趨勢將會大于朝著差的粒子運動的趨勢。

4)位置、速度更新。根據庫倫定律和牛頓運動定律，每次迭代規劃空間中的帶電粒子pj的每個維度k的位置速度分量將按如下公式進行更新：

(5)

vjk(t+1)=xjk(t+1)-xjk(t)

(6)

其中：ka是加速度系數，用來調控其他帶電粒子對位置更新的影響；kv是速度系數，用來調控先前帶電粒子速度的影響；randj1和randj2都是均勻分布在(0，1)上的隨機數。ka與帶電粒子的電場力合力相關聯，較大的取值將會導致過快的收斂；較小的取值將會使收斂速度變慢，增加計算時間。而kv則平衡著全局搜索能力與局部搜索能力，kv較大則全局搜索能力強局部搜索能力弱，反之則全局搜索能力弱、局部搜索能力強。在算法開始階段，全局搜索能力較強，隨著迭代搜索的進行，全局搜索能力減弱、局部搜索能力增強，這樣才能達到好的尋優效果，因此，本文將ka和kv設置如下：

(7)

(8)

其中：iter是當前迭代次數；itermax是算法最大迭代次數。由式(3)和(4)可知，kv從初始值1開始，隨著迭代次數iter的增加，非線性遞減；ka則隨著迭代次數增加，非線性單調遞增。隨著搜索算法進入迭代后期局部搜索階段kv減小，ka增大速度變快，這避免了帶電粒子因速度過快而使算法無法在當前最優區域進行更加精細的搜索。通過這種方法來平衡全局搜索與收斂速度，可以有效地避免算法的早熟收斂。

2.3 方法流程

基于CSS的航路規劃算法的流程如圖2所示，方法的具體步驟描述如下：

1)根據實際問題設置合適的帶電粒子個數m，最大迭代次數itermax，算法終止條件；

2)根據航路規劃任務的要求，設置每個帶電粒子的維數；

3)初始化整個帶電粒子群，每個帶電粒子代表規劃空間中的一條航路，初始化每個帶電粒子的位置、速度；

4)根據設定的代價函數，計算出每個帶電粒子的電荷量；

5)計算帶電粒子所受電場力合力，更新帶電粒子的位置及速度；

6)更新每個帶電粒子的代價函數值；

7)確定是否達到終止條件，如果沒有，返回到步驟4)，否則算法結束；

8)輸出全局最優代價函數值的帶電粒子所代表的航路。

圖2 基于CSS的航路規劃方法流程

3 實驗結果及分析

本文在Intel Core i5- 3230M CPU、2.60 GHz、4 GB內存的PC上進行仿真實驗，運行環境為Windows 7，編程環境為VS2005。

相關實驗參數設置為：帶電粒子群規模m為30。約束條件設置為：航行器最大轉彎角度60°，最小轉彎半徑200 m，上浮時間間隔為4 h。算法終止條件為：連續兩次迭代最優代價值相差小于0.01，則算法終止。

本實驗采用的是矢量電子海圖，地圖范圍為116.2°E～132.5°E，21.5°N～41.2°N，約為1 793 km×2 167 km的矩形區域。記號“”表示航行器的起始點，“▲”表示目標點，其中限制區標注為“A”，海流區標注為“B”,風浪區標注為“C”，威脅區標注為“D”。

實驗中對本文方法與A*算法、粒子群算法和蟻群算法進行多組對比實驗，每次對比實驗以上四種方法均在同樣的起始點、目標點以及相同海域環境下進行實驗，記錄每種方法每次實驗規劃得到的航路代價、實驗耗時和占用內存。其中：蟻群算法設置為迭代5次終止，信息素揮發因子為0.3，螞蟻數為20；粒子群算法種群數目設置為30，終止條件設置為連續兩次迭代最優代價值相差小于0.01，則算法終止。在不同海域環境下得到的航路規劃實驗結果如圖3、圖4所示。

從表1、表2實驗數據可以看出，航路規劃算法用時上從小到大依次為：基于帶電粒子搜索的航路規劃方法、粒子群算法、A*算法、蟻群航路規劃算法。為了對本文方法與粒子群航路規劃方法作進一步比較，本文對每組實驗記錄了這兩種方法最優航路代價的收斂曲線，如圖5、圖6所示。在相同的實驗條件下，本文方法得到的航路的代價值與粒子群算法航路代價值相差不大；但收斂速度比粒子群算法收斂速度快。這是因為在粒子群算法中，粒子的運動僅由局部最優和全局最優來決定，這樣大部分其他粒子所攜帶的信息都被忽略。這也是本文方法與粒子群算法的一個本質不同，在本方法中，每個帶電粒子的運動是由其他帶電粒子對其電場力合力來確定的，每次迭代尋優是綜合了其他帶電粒子影響的結果，帶電粒子之間有更多的信息交流。這一特點就使得帶電粒子能夠以一定概率更新到遠離當前局部最優的位置，而這個位置可能比當前全局最優粒具有更好的適應度，因此該算法相比粒子群算法具有更強的全局搜索能力；并且本文提出的非線性調整速度和加速度系數的方法平衡了全局搜索與局部搜索，在提高了算法收斂速度的同時，避免了算法的早熟。

圖3 繞島嶼航路規劃實驗

圖4 復雜環境航路規劃實驗

方法算法耗時/s航路長度/km航路代價內存占用/KB基于CSS航路規劃算法1.786292.8869632.82670234A?算法6.314291.5927332.681645646蟻群算法213.804313.2360134.3441802361粒子群算法3.598294.3106432.89878133

表2 復雜環境航路規劃實驗結果比較

從以上兩組實驗結果看，本文方法與確定性算法A*算法相比，A*算法最終規劃出的航路代價略優；但是本文方法規劃用時間明顯少于A*算法。在規劃空間環境比較復雜的情況下，A*算法會占用大量內存。從表1、表2實驗結果可以看出，當規劃空間變得相對復雜時A*算法在第二組實驗中內存消耗比第一組實驗提高了28.3%，而本文方法內存消耗沒有太大變化，并且A*算法在復雜環境下尋優過程中可能會產生回退，這會使算法耗時增大，而本文方法則不存在該問題。

圖5 繞島嶼航路規劃實驗CSS與PSO最優航路代價收斂曲線

圖6 復雜環境航路規劃實驗CSS與PSO最優航路代價收斂曲線

蟻群算法也是一種隨機性算法，它基于螞蟻信息素這種間接交流方式，是一種離散的優化方法。該算法本質上是一種正反饋機制，最優路徑上的螞蟻增多，留下的信息素強度變大，導致后面的螞蟻通過輪盤賭更大的概率會選擇到該路徑，最優路徑上的螞蟻數量更多，最后收斂到這條路徑上。對于離散的搜索空間(如Voronoi圖等)，蟻群算法耗時和優化結果都有較好的效果；但是對于連續的搜索空間，信息素的擴散等操作將會使得算法耗費的時間大幅度增加，信息素圖也會占用大量內存，而本文提出的方法對于連續問題的求解則沒有這一問題。從表1、表2也可以看出，本文方法與蟻群算法解的質量相差無幾，但是該方法所用時間以及占用內存都遠小于蟻群算法。

4 結語

本文提出了基于帶電粒子搜索的航路規劃方法，并成功地將該方法運用于無人潛航器的航路規劃，有效地解決了多約束復雜海洋環境下的航路規劃問題。通過實驗表明，該方法能夠快速為航行器規劃出可行航路，并通過對比實驗表明，該方法與A*算法、蟻群算法、粒子群航路規劃算法相比，在保證解的質量的同時，算法耗時較少，收斂速度更快。本文航路規劃方法對于特定的任務帶電粒子的維數是固定的，因此下一步可以將本方法中的帶電粒子的維數引入模糊性，而不是設置為固定的維數，這會使得本方法在適應高維問題的同時，優化效果進一步提高。