基于勢場啟發(fā)蟻群算法的遠程水中兵器航路規(guī)劃

劉海光，孫明太，王桂芹

（1.海軍航空工程學院青島分院，山東青島 266045；2.海軍潛艇學院，山東青島 266199）

基于勢場啟發(fā)蟻群算法的遠程水中兵器航路規(guī)劃

劉海光1，2，孫明太1，王桂芹2

（1.海軍航空工程學院青島分院，山東青島 266045；2.海軍潛艇學院，山東青島 266199）

針對航行誤差較大的遠程水中兵器航路規(guī)劃問題，采用柵格化方法建立海洋環(huán)境模型，為使兵器在航行過程中能有效規(guī)避障礙并導向目標，提出一種人工勢場力為啟發(fā)因子的改進蟻群算法，利用該方法搜索遠程水中兵器從起始點至目標點的最佳路徑，算法解決了經典蟻群算法容易陷入局部最優(yōu)及收斂速度慢的問題。仿真結果表明該規(guī)劃算法雖有少量的路徑損失，但可以有效避免由于誤差引起的航行安全問題，是一種有效的遠程水中兵器航路規(guī)劃方法。

蟻群算法；遠程水中兵器；航路規(guī)劃；人工勢場；柵格法

遠程水中兵器是一種水下遠距離航渡到作戰(zhàn)海域，自主執(zhí)行作戰(zhàn)任務的水中兵器，其航渡時間長、航程遠，航途障礙多、敵情復雜。因此為其規(guī)劃安全航路以便順利到達作戰(zhàn)海域是其作戰(zhàn)任務順利完成的前提。相對于短程水下航行器的航路由人工控制，遠程水下航行器航路一般自主控制。隨著遠程水下航行器不斷出現(xiàn)，其航路規(guī)劃逐漸成為研究的熱點，形成了幾何模型搜索、虛擬勢場及導航函數(shù)、典型生物智能和數(shù)學優(yōu)化四種方法［1］。幾何模型法通過建立障礙物模型，采用一定優(yōu)化算法進行搜索尋找最優(yōu)解，方法簡單，但較難考慮約束性條件影響，可用來進行無約束條件的航路規(guī)劃。虛擬勢場法算法簡單，執(zhí)行效率高，多使用于局部路徑規(guī)劃，文獻［2］在考慮了海流影響下使用虛擬勢場法進行水下航行器航路規(guī)劃。生物智能法較多，典型的有遺傳算法、蟻群算法、粒子群算法及各智能算法的組合等，這些算法多考慮約束條件的影響，適合于全局路徑規(guī)劃，文獻［3?4］分別利用遺傳算法及蟻群算法對水下航器進行了路徑規(guī)劃。文獻［5］將各種約束轉換為數(shù)學多項式，并利用數(shù)學優(yōu)化方法求最優(yōu)解，數(shù)學優(yōu)化法較容易考慮動力學約束條件，計算速度快，但構建合適的數(shù)學模型較為困難。

遠程水中兵器航渡階段速度低，航向受水下環(huán)境及慣導控制精度影響大，需定時上浮校準位置，當由于敵情等原因無法正常上浮時，其航向累積誤差較大。為提高環(huán)境適應性、隱蔽性及航行安全性，同時需將敵情敏感區(qū)域也作為障礙考慮到環(huán)境中。航路規(guī)劃應綜合各種因素規(guī)劃一條從發(fā)射點到目的地，隱蔽性高、同時兼顧航行安全性和航程指標的全局最優(yōu)路徑。蟻群算法作為智能路徑規(guī)劃算法的一種，具有良好的通用性、魯棒性和開放性，本文選擇它為基本算法規(guī)劃遠程水中兵器航路。但標準蟻群算法也存在著容易陷入局部最優(yōu)及收斂速度慢等缺點，因此在具體使用時應根據具體任務進行算法改進。為使遠程水中兵器在發(fā)生較大航行誤差的情況下能有效規(guī)避水中障礙，同時加快算法運算速度，本文提出一種人工勢場為啟發(fā)信息因子的改進蟻群算法進行遠程水中兵器航路規(guī)劃，算例表明該方法考慮了在較大航行誤差下能夠避開威脅，實現(xiàn)了遠程水中兵器航路選擇與優(yōu)化的目的。

1 環(huán)境表達

柵格化方法是處理大型地圖建模的經典方法［6?7］，本文采用柵格化方法將整個航渡海域海圖劃分為二維網格，進行編碼，并利用海圖給出的數(shù)據和敵情信息，判斷海域水深、障礙物、封鎖區(qū)域、適航區(qū)域等信息。用網格編碼代表遠程水中兵器在海域中的位置，將編碼統(tǒng)一映射為網格的左下角坐標，并用相對位置來表示網格間的位置關系。用邏輯變量來表示網格的狀態(tài)，1表示障礙，0表示自由海域，如圖1所示，黑色表示障礙，白色表示自由區(qū)域，整個網格可以形成一個二維矩陣。圖中網格中箭頭表示每個自由海域網絡可以移動路徑的方向。根據蟻群算法搜索路徑原理，螞蟻可以從起始節(jié)點出發(fā)，沿箭頭方向移動到下一網格并最終到達目標點，可選路徑有很多種，經過反復選擇搜索到一條路徑最短且滿足條件的最佳路徑。路徑長度計算方法為：設網格邊長為a0，則任意相鄰兩個網格（x1，y1）、（x2，y2）間的距離J為

圖1 網格劃分及其相互關系圖

2 航路規(guī)劃算法設計

2.1 改進蟻群算法

蟻群算法利用螞蟻在所經路徑上留下的信息激素作為后續(xù)螞蟻選擇路徑的依據，并通過蟻群協(xié)同來完成路徑選擇。總數(shù)為N的螞蟻在路徑的網格間可選擇的網格范圍內，根據路徑選擇的規(guī)則選擇下一個網格，在第t次搜索中，從網格i選擇網格j的概率pi，j（t）定義為

式中，τi，j（t）為第t次循環(huán)搜索時網格i到網格j路徑上的信息素濃度，ηi，j為該路徑上的啟發(fā)信息，α為信息素濃度的權值，β為啟發(fā)信息的權值，allowedk表示約束條件下節(jié)點i的可移動節(jié)點集合。螞蟻從初始節(jié)點出發(fā)，根據節(jié)點轉移概率不停地在節(jié)點間進行選擇，最后到達目的地，完成一次路徑搜索。到達目的節(jié)點后，需要對路徑上的信息素進行更新，為加快算法的收斂速度，設置更新規(guī)則如下：算法的目的是為了尋找滿足條件的最短路徑，因此可以根據路徑長度來確定解的優(yōu)劣，在完成一次搜索后，必然產生最優(yōu)解Jmin和最差解Jmax。為加快算法運算速度，只對接近最優(yōu)解的路徑信息素進行更新。更新條件為，待更新信息素的路徑長度Jx滿足：

更新規(guī)則為

式中，ρ為信息消散指數(shù)。Δτi，j為新增加的信息素濃度。其與該次搜索途徑路徑長度成反比，路徑較短的被附加更多的信息素。

式中，C為常數(shù)，為螞蟻釋放的信息素總量。

2.2 人工勢場法

人工勢場法是一種利用虛擬勢場力來進行路徑規(guī)劃的方法，它假定工作區(qū)域內的目標點產生吸引力場，同時障礙點產生排斥力場，利用引力場和排斥力場的綜合作用進行航路規(guī)劃［8］。目標位置為G，在水中兵器位置P處引力場可表示為

式中，ζ為引力系數(shù)，d（P，G）為兵器與目標的距離?？梢钥吹奖髋c目標的距離越大吸引力越大，引力梯度函數(shù)為

式中，nG為兵器指向目標點的單位矢量。在位置Po處有障礙物，其對兵器產生斥力，斥力場函數(shù)為：

式中，d0為一常數(shù)，λ為斥力場常數(shù)，表示斥力場的作用范圍。兵器所受到的斥力可以表示為：

式中，nO為兵器指向障礙物的單位矢量，由此兵器在海域中所受的引力與斥力的合力為：

2.3 啟發(fā)信息

由標準蟻群算法可知，當不同路徑上的啟發(fā)信息差別比較大時，蟻群算法的搜索能力就會變弱，容易陷入局部最優(yōu)?？蛇x網格到目標網格的距離，一定程度上反應了路徑的優(yōu)越程度，應該讓較優(yōu)的路徑有相對較大的概率被選擇；本文定義待選網格到目標網絡距離的倒數(shù)為啟發(fā)式信息的因子Δηij（t）。待選網格到目標網格的距離差別不大，這樣可以適當增加較差路徑被選擇的概率，既保證了路徑選擇的隨機性又能避免算法過早地出現(xiàn)局部最優(yōu)。

當出現(xiàn)較大航向誤差時，引入人工勢場法可實現(xiàn)遠程水中兵器快速規(guī)避障礙。因此當兵力與障礙距離較遠，啟發(fā)式信息應主要由式（12）決定，而當兵器與障礙間的距離較小，螞蟻在選擇路徑時應受到信息素和勢場力的雙重作用。兵器所處位置的Ft大小一定程度上能夠表征該節(jié)點與障礙或目標的距離，如果Ft較大，說明該網格靠近障礙或目標，應在勢場力的啟發(fā)下盡快遠離或接近該區(qū)域，則有助于保證兵器航行安全。為發(fā)揮蟻群算法與人工勢場算法的優(yōu)勢，將兩部分的因素綜合考慮，共同決定螞蟻狀態(tài)轉移的啟發(fā)信息ηij（t）。

式中，θ表示可選擇路徑方向與合力Ft方向的夾角。這種情況下，當Ft較大或可選路徑方向與Ft角度接近時，被選中的概率會較大，主要由勢場力來決定兵器移動的方向，便于兵器遠離障礙及導向目標。

3 算法實現(xiàn)步驟

結合改進的蟻群算法和人工勢場法進行遠程水中兵器的航路規(guī)劃，具體實現(xiàn)步驟及詳細流程如圖3所示。

圖2 算法流程圖

4 算例分析

為驗證算法有效性，將兵器航渡區(qū)域離散化成40× 40的網格。螞蟻起始點坐標為（0，0），目標點G坐標為（40，40）。蟻群算法參數(shù)初始化為：信息素權值α為1，啟發(fā)信息權值β為3，信息素總量參數(shù)C為3，信息消散系數(shù)ρ為0.7，螞蟻總數(shù)量M為20只，最大迭代次數(shù)為100。引力場參數(shù)設置為：引力系數(shù)ζ為2，斥力系數(shù)η為2，斥力作用距離d0＝3個單位長度。利用Matlab進行計算，最終輸出的最優(yōu)路徑如圖3所示，路徑長度為72.385個單位長度，最優(yōu)解的迭代過程如圖4所示。

為驗證本文算法的先進性，使用相同的參數(shù)設置方式，利用標準蟻群算法對相同的環(huán)境進行航路規(guī)劃，輸出結果如圖5所示，最優(yōu)路徑長度為68.798個單位長度。迭代過程如圖6所示。通過比較可以看到，相對于標準蟻群算法，勢場啟發(fā)的蟻群算法具有相對較快的收斂速度，為消除航行誤差對航行安全的影響，在臨近障礙時采取了一定的“平滑”過渡，兵器航行路徑與障礙間距離加大，更容易規(guī)避航路中的障礙，航行安全性更高。其最優(yōu)路徑長度比標準蟻群算法約有5%的航程損失，但為保證航行安全，少量的航程損失也是有必要的。

圖3 勢場啟發(fā)蟻群算法路徑規(guī)劃

圖4 勢場啟發(fā)的蟻群算法迭代過程

圖5 標準蟻群算法路徑規(guī)劃

圖6 標準蟻群算法迭代過程

5 結束語

蟻群算法開放性較好，方便與其它算法結合使用，以充分利用各種算法的優(yōu)勢。本文針對遠程水中兵器航渡階段速度低，航行誤差較大等問題，在改進蟻群算法的基礎上，通過將人工勢場力作為改進蟻群算法的啟發(fā)因子，實現(xiàn)了遠程水中兵器的航路規(guī)劃。仿真結果表明改造后的算法比標準蟻群算法收斂速度快，在面對水中障礙時能夠以相對平滑的方式規(guī)避，在犧牲小部分航程為代價的基礎上，可有效避免航行誤差對航行安全性的影響。表明該方法為一種可行的遠程水中兵器航路規(guī)劃方法。

［1］ 王奎民.水下潛器的航路規(guī)劃技術綜述［J］.智能系統(tǒng)學報，2014，9（6）：563?658.

［2］ 吳正平，等.基于改進人工勢場法的AUV路徑規(guī)劃［J］.化工自動化及儀表，2014，41（12）：1421?1423.

［3］ 張京娟.基于遺傳算法的水下潛器自主導航規(guī)劃技術研究［D］.哈爾濱：哈爾濱工程大學，2003：29?35.

［4］ 劉利強.蟻群優(yōu)化方法研究及其在潛艇導航規(guī)劃中的應用［D］.哈爾濱：哈爾濱工程大學，2007：35.

［5］ Singhr.Path planning using Shi and Karl level sets［S］. Proceedings of the 1st International Conference on Robot Communication and Coordination.Piscataway.USA，2007：2829?2832.

［6］ 曲鏡圓.基于聲納的AUV環(huán)境感知與地形建模方法研究［D］.哈爾濱：哈爾濱工程大學，2009：12?22.

［7］ Duan Hai?bin，Yu Ya?xiang，Zhang Xiang?yin.Three di?mension path planning for UCAV using hybrid meta?heu?ristic ACO?DE algorithm［J］.Modeling Practice and Theo?ry，2010，18（8）：1104?1115.

［8］ 羅德林，吳順祥.基于勢場蟻群算法的機器人路徑規(guī)劃［J］.系統(tǒng)工程與電子技術，2010，32（6）：1277?1280.

Remote Underwater Weapon Path Planning Based on Ant Colony Optimization Inspired by Field Heuristic

LIU Hai?guang1，2，SUN Ming?tai1，WANG Gui?qin2
（1.Qingdao Branch of Naval University of Aeronautics＆Astronautics，Qingdao 266045；2.Navy Submarine Academy，Qingdao 266199，China）

Aimming at the problems of path planning for the remote underwater weapon with large navigation error，a grid method is used to establish the model of marine environment，in order to enable the weapon to be able to move effectively a?way from the barrier in the navigation，an improved ant colony optimization algorithm is proposed，and the artificial potential field is a heuristic factor of it.This algorithm is used to search for the best path of the remote underwater weapon from the starting point to the target point，and solves the problems that the standard ant colony algorithm is easy to fall into local opti?mum and has slow convergence speed.Simulation results show that the path planning algorithm brings a small amount of path loss，but it can avoid the problem of navigation safety due to the error.This algorithm is an effective path planning method for the remote underwater weapon.

ant colony algorithm；remote underwater weapon；path planning；artificial potential field；grid method

TJ630；E917

A

10.3969／j.issn.1673?3819.2016.06.009

1673?3819（2016）06?0042?04

2016?07?21

2016?08?18

劉海光（1975?），男，山東濟寧人，博士研究生，講師，研究方向為水中兵器保障與應用。

孫明太（1961?），男，教授，博士生導師。

王桂芹（1977?），女，副教授。