無人水下航行器勢場航路規劃方法研究

賈下跖, 劉可述, 張 孟, 鄧 超

(1.山東核電有限公司，山東 煙臺 264000；2.北京航天控制儀器研究所，北京 100854；3.東方電子股份有限公司，山東 煙臺 264000)

無人水下航行器勢場航路規劃方法研究

賈下跖1, 劉可述2, 張 孟1, 鄧 超3

(1.山東核電有限公司，山東 煙臺 264000；2.北京航天控制儀器研究所，北京 100854；3.東方電子股份有限公司，山東 煙臺 264000)

對運動障礙威脅環境下無人水下航行器(UUV)航路規劃問題進行了研究;首先分別對規劃過程中固定障礙、運動障礙建立了排斥勢場，對目標點建立了吸引勢場，將航路規劃問題轉變為尋找最優勢場點問題；然后提出一種改進的粒子群算法(NPSO)，在UUV航路規劃過程中，尋找距離當前路徑點固定步長范圍內的最優勢場點，將其作為下一路徑點，最終實現UUV在運動障礙威脅環境中的航路規劃；最后對所提方法進行了仿真驗證，UUV可以有效躲避固定障礙與運動障礙威脅，尋找到較優航路，取得了較好的仿真效果。

UUV；航路規劃；勢場；粒子群

0 引言

隨著海洋經濟的迅猛發展，無人水下航行器 (Unmanned underwater vehicle, UUV)也逐漸成為眾多學者的研究熱點，尤其是其在深海探測與開發、軍事偵察與干擾等方面的應用越來越受到人們重視。在有海底山脈、沉船、礁巖等固定障礙物和艦艇等運動威脅的復雜海洋環境下，尋找一條能有效避開深海中各種固定障礙和運動威脅、順利到達指定地完成勘測和偵察任務，無疑對無人水下航行器的航路規劃技術提出了更高的要求[1]。

國內外眾多學者通過對UUV航路規劃問題的大量深入研究，提出了許多行之有效的航路規劃算法[2-4]，諸如人工勢場法、A-Star算法及其改進的D-Star算法、蟻群優化算法、神經網絡算法等獲得了廣泛的研究與應用。但是，這些算法也具有其應用場合的局限性、算法的復雜性和搜索效率較低等問題。本文構建了一種UUV航路規劃勢場，并提出一種改進的粒子群算法，以提高粒子群算法的搜索性能，利用改進的粒子群算法尋找最優勢場點，以實現復雜環境下UUV航路規劃。

1 勢場建立

本文針對固定障礙、運動障礙環境下的UUV航路規劃問題進行研究。UUV規劃起始點坐標為P0(x0,y0)，航路點坐標為Pi(xi,yi)，其中i=1,2,…n，終點坐標為Pg(xg,yg)。為簡化問題，規劃過程中，以固定步長S進行搜索。這樣每一步搜索只需要尋找最優的前進角度ψ即可。

(1) 固定障礙勢場。

如圖1所示，為UUV躲避固定障礙航路規劃示意圖。

圖1 UUV航路規劃示意圖

(1)

其中:S為UUV路徑規劃單步航行距離，UUV前行過程中始終尋找F1小的點，從而實現對固定障礙物的規避。

(2) 運動障礙勢場。

UUV作業過程中會遇到艦艇等運動障礙。

如圖2所示，當前點Pi在候選點Pi+1方向延長線與運動障礙方向延長線的交點為M，UUV從Pi點運動到M點的時間為t1，運動障礙運動到M點的時間為t2。如果t2>t1則說明UUV先于運動障礙到達，t2-t1越大，UUV越安全，這里取函數e-β(t2 -t1 )2為運動障礙勢場函數，當UUV距離交點越近時避碰行為越強，UUV距離交點越遠時避碰行為越弱，因此運動障礙勢場函數調整為：e-αt12*e-β(t2 -t1 )2。如果t2

圖2 UUV運動障礙規劃示意圖

(2)

如果交點M不存在，則說明UUV與運動障礙運動航線不相交，此時同樣有F2=0。

(3) 吸引勢場。

為實現UUV朝向目標運動，需要建立吸引勢場。如圖3所示。

圖3 吸引勢場示意圖

(3)

(4)UUV航路規劃總勢場函數。

UUV航路規劃總勢場函數為各勢場函數的疊加。從而有：

F=k1F1+k2F2-k3F3

(4)

其中:ki為權重系數(ki>0)。

基于上述分析，建立了當前航跡點的UUV航路規劃勢場函數后，利用粒子群算法搜索使勢場函數獲得最小值的航跡點，將該搜索到的航跡點作為UUV航行路徑中下一時刻的航跡點，依次原理逐步獲得一系列的航跡點，最終得到優化航行路徑，實現航路規劃。

2 改進粒子群算法

粒子群算法(particle swarm optimization)也稱粒子群優化算法，具有參數調節簡單，易于實現，精度高、尋優能力強等優點[5-7]。因此該算法一經提出便引起許多專家學者的重視，演化出諸多改進策略，提高算法性能[8-11]。自身歷史最優位置、自身慣性速度、群體歷史最優位置是粒子群優化算法中影響其搜索性能的3個主要因素。本文針對這三大主要因素，提出了一種有利于提高算法性能的改進粒子群優化算法(novel particle swarm optimization, NPSO)。在粒子群優化算法搜索過程中，每一個粒子分別朝下列3個不同方向進行進化：自身最優位置、種群最優位置、自身最優與種群最優的加權位置，繼而產生3個同源的子粒子，然后比較這3個同源子粒子適應度，根據優勝劣汰的原則，保留適應度最優的子粒子。即有粒子進化方程：

(5)

從而：

(6)

變量定義：

rt,t=1,2,3：取值介于[0,1]之間的隨機數；

ω：粒子進化產生子粒子的速度方向慣性權重；

ci(i=1,2)：學習因子；

pgd(k)：第k次迭代后種群最優粒子第d維坐標。

3 算法性能分析

3.1 算法收斂性分析

對于進化方程：

(7)

(8)

當c1r2=0、c2r3=0、ωr1=0時分別對應NPSO的3個不同進化方向，顯然NPSO是進化方程(7)、(8)的特殊進化方式，如果進化方程(7)、(8)收斂則NPSO收斂。

(9)

(10)

其中：φ1=c1r2，φ2=c2r3，φ=φ1+φ2，φp=φ1pid(k)+φ2pgd(k)。

定義：

從而有：

(11)

當矩陣的特征根具有負實部時，方程(11)收斂，有特征方程：

(12)

解得特征根為：

(13)

從而只需ωr1-φ-1<0，即可保證進化方程(7)、(8)收斂，進而保證NPSO收斂。

3.2 算法搜索性能分析

為衡量算法的搜索性能，采用不同的測試函數對算法進行測試，并將NPSO與(Basicparticleswarmoptimization)BPSO、(Linearlyvaryinginertiaweight)LWPSO、(Exponentialinertiaweightstrategies)EPSO、(Time-varyingaccelerationco-efficient)TVAC性能進行比較[8-11]。

采用的測試函數為：

(1)sphere函數：

(2)Rotatedhyper-ellipsoid函數：

(3)Rosenbrock函數：

-100

(4)Rastrigin函數：

(5)Griewank函數：

Kennedy研究認為c1、之和取4.0時，可以獲得較好的搜索效果[12]，一般把它們均設為2。

為了獲得較好的搜索效果，通常取慣性權重ω為0.7、種群數量為30[12-13]。在仿真中，對BPSO、LWPSO、EPSO、TVAC優化算法，種群粒子個數選為n=30，而對于NPSO，因為其在進化過程中產生3個子粒子，所以選取n=10。在對比各算法搜索性能測試的仿真實驗中，各相關參數的取值如表1所示。

如果粒子位置為搜索過程中超出搜索空間，則將粒子位置坐標設為此時的邊界坐標、粒子速度設為零；同理，如果粒子速度超出速度邊界，則將此時粒子速度設為速度邊界值。為了讓仿真實驗結果更加準確可靠，對每個測試函數的優化過程都重復100次，并對這100次測試結果求取平均值和標準差。仿真實驗結果如表2所示。

表1 不同優化算法相關參數取值

表2 BPSO、LWPSO、EPSO、TVAC和NPSO對比結果

注：表中數據為均值±標準差

圖4 平均適應度變化曲線圖

由表2可以看出，對于單模態測試函數，上述各種搜索算法的搜索精度和穩定性由高到低依次為NPSO、TVAC、EPSO、LWPSO、BPSO；但是NPSO唯獨對高度多模態Rastrigin函數搜索效果不太理想。

圖4所示為不同搜索算法在Rosenbrock函數f3和Griewank函數f5進化過程中的平均適應度變化曲線。從該圖中可以清晰的看出，各算法的收斂速度由快到慢依次為NPSO、TVAC、BPSO、EPSO、LWPSO。

本文驗證了各算法在不同自變量維數D下的搜索性能：自變量維數D從10增加到100的過程中，求取不同算法下測試結果的平均值和標準差。表3所示為Rosenbrock函數f3在自變量維數D由10增加到100的部分實驗數據。由表3可以得知，各算法的搜索精度和穩定性均會隨著測試函數維數的增加而出現不同程度的降低，但TVAC和NPSO算法的搜索精度和穩定性要優于其他算法。

表3 Rosenbrock函數不同維數下BPSO、LWPSO、EPSO、

注：表中數據為均值±標準差

4 UUV航路規劃仿真

利用所提算法對UUV在動態障礙環境中的航路規劃進行仿真，由UUV當前點出發，以固定步長前行，在UUV最大轉角約束范圍內，利用改進的粒子群算法尋找具有最優勢場點的候選點，作為UUV前進的下一路徑點，逐步完成UUV航路規劃。仿真環境為1 km×1 km的區域，UUV起始點為A(50,50)，目標點為G(950,950)。ki=1,i=1,2,…,4，σ=2。仿真步長為20m，為簡化問題，仿真時UUV以4m/s的速度勻速前進，分別遭遇橫坐標為200m平行于y軸的運動障礙B，與縱坐標為800 m，平行于x軸的運動障礙C。

圖5 運動障礙環境下UUV航路規劃效果圖

從仿真圖5上可以看出，UUV遭遇運動障礙B時，選擇從運動障礙B之前繞行，遭遇運動障礙C時，選擇從運動障礙C之后繞行，本文所提方法能有效的避開威脅域。仿真結果表明本文所提方法可以有效實現UUV運動障礙環境下的航路規劃，獲得了較好的規劃效果。

為進一步檢驗本文所提算法性能，對復雜環境下的UUV航路規劃進行了仿真驗證，并與傳統人工勢場算法進行比較，仿真結果如圖6所示。

圖6 復雜環境下UUV航路規劃

圖6中實線為本文所提算法規劃的UUV航路，黑色點劃線為傳統人工勢場算法規劃的UUV航路。為對比復雜環境下算法有效性，仿真時UUV起始點設為A(50,50),目標點設為B(950,950)，從圖6可以看出，本文所提算法在復雜的環境中可獲得較優的UUV規劃航路，而傳統人工勢場算法容易陷入障礙區域無法實現航路規劃。為對比本文所提算法與傳統人工勢場算法所搜索路徑的優化性，UUV起始點設為C(50,950)，目標點設為D(950,50)，仿真結果顯示，本文所提算法規劃路徑長度為1 308 m，傳統人工勢場算法規劃路徑長度為1 504 m。由仿真圖6可以看出，傳統人工勢場算法在障礙物前容易震蕩，陷入不穩定運動狀態，本文所提算法可以獲得較優的平滑路徑，明顯優于傳統人工勢場算法。

5 結論

本文首先分別對固定障礙和運動障礙威脅環境建立了排斥勢場，對目標點建立了吸引勢場，將航路規劃問題轉變為尋找最優勢場點問題；然后提出了NPSO算法，并應用典型評價的函數對算法性能進行了分析；最后將所提出的NPSO算法應用到運動障礙威脅環境下UUV航路規劃問題中，通過分析仿真結果可得出以下結論：

(1) NPSO算法通過在每次粒子進化過程中，向3個不同方向搜索，使得搜索更充分，并對子粒子優勝劣汰得到最終的搜索結果，有利于尋找到較快的收斂方向。對典型評價函數的仿真結果表明，對于單模態函數，NPSO在搜索精度和收斂速度上均優于BPSO、LWPSO、EPSO以及TVAC。但是，對高度多模態函數NPSO搜索效果并不十分理想，這是由于NPSO算法相對于其它算法每次迭代更容易找到收斂較快的搜索方向，使得NPSO算法過快收斂而多樣性有所降低。

(2) 本文所設計的航路規劃方法通過建立運動障礙遭遇時間模型，得到躲避運動障礙勢場函數，利用粒子群算法尋找勢場值最小點，從而在運動障礙威脅環境中，能有效的避開障礙物，獲得較優的規劃航路，效果良好。

(3) 對復雜環境下UUV航路規劃的仿真顯示，相對于傳統人工勢場，本文所提算法可以得到較優的規劃航路，且不容易陷入局部極小點，可實現復雜環境下的航路規劃，然而要實現徹底避免陷入局部極小點，或U型障礙，還需要進行UUV狀態判斷與逃逸規則的設計，這是后續工作需要加強和完善的地方。

[1] Liu Liqiang, Dai Yuntao. 3D Space Path Planning of Complex Environmental Underwater Vehicle[A].2009 International Joint Conference on Computational Sciences and Optimization[C]. 2009: 204-209.

[2] Zhang J J. Research on Autonomous Navigation Planning of Underwater Vehicle Based on Genetic Algorithm[D]. Harbin: Harbin Engineering University, 2003.

[3] Nathan E B. Three-Dimensional Route Planner Using A* Algorithm Application to Autonomous Underwater Vehicles[R]. Louisiana State University Report, 2008.

[4] 朱 毅，張 濤，宋靖雁.非完整移動機器人的人工勢場法路徑規劃[J].控制理論與應用，2010, 24(2): 154-161.

[5] Mondal D，Chakrabarti A, Sengupta A. Optimal placement and parameter setting of SVC and TCSC using PSO to mitigate small signal stability problem[J]. Electrical Power & Energy Systems, 2012,42(1): 334-340.

[6] Ishaque K，Salam Z, Amjad M, et al.An Improved Particle Swarm Optimization (PSO)-Based MPPT for PV With Reduced Steady-State Oscillation[J]. Power Electronics, IEEE Transactions on, 2012,27(8): 3627-3638.

[7] Mohammadi-Ivatloo B, Rabiee A, Soroudi A, et al.Iteration PSO with time varying acceleration coefficients for solving non-convex economic dispatch problems[J]. Electrical Power & Energy Systems, 2012, 42(1): 508-516.

[8] 張頂學,關治洪,劉新芝.一種動態改變慣性權重的自適應粒子群算法[J].控制與決策，2008,23(11):1253-1257.

[9] Sdsngs, Ratnaweera, Saman K. Halgamuge, Harry C. Watson. Self-Organizing Hierarchical Particle Swarm Optimizer with Time-Varying Acceleration Coefficients[J]. IEEE Transaction on evolutionary computation 3(8):240-255.

[10] Shi Y, Eberhart R. A modified particle swarm optimizer[A].IEEE World Conf on Computational Intelligence[C]. Piscataway: IEEE Press,1998: 69-73.

[11] Chen G M, Huang X B, Jia J Y, et al. Natural exponential inertia weight strategy in particle swarm optimization[A]. Proc of 6th Congress on Intelligent Control and Automation[C]. Dalian: IEEE Press, 2006:3672-3675.

[12] Kennedy, J. (1998). The behavior of particles[A]. 7thAnnual Conference on evolutionary programming[C]. San Diego, USA.

[13] Shi Y, Eberhart R C. Empirical Study of particle swarm optimization[A]. 1999 congress on evolutionary computing[C]. Vol. III, pp 1945-1950.

[14] Carlisle A, Dozier G. An Off-The-Shelf PSO[A]. Proceeding of the 2001 Workshop on Particle Swarm Optimization[C].1-6.

Potential Field Method for Unmanned Underwater Vehicle Path-planning

Jia Xiazhi1, Liu Keshu2, Zhang Meng1, Deng Chao3

(1.ShanDong Nuclear Power Company LTD, Yantai 264000, China; 2.Beijing Aerospace Control Instrument Research Institute, Beijing 100854, China; 3.Dong Fang Electronics Co.,Ltd., Yantai 264000, China)

The problem of UUV path-planning under the environment of movement disorders has been addressed. Firstly, potential field method is proposed to build rejection potential field for fixed obstacles and movement disorders, and attractive potential for objective point. Then, a novel particle swarm optimization (NPSO) is proposed and applied to find the optimal potential field point as the next path point, which point of fixed step length distance from the current point, so as to realize UUV path-planning under movement disorders threat. Finally, simulation is presented, demonstrating that UUV can dodge obstacles and threat, and search for the better sea-lane.

UUV; path-planning; field; PSO

2016-07-15；

2016-09-13。

賈下跖(1988-)，女，湖北天門人，主要從事核電站儀控儀表方向的研究。

1671-4598(2017)01-0144-05

10.16526/j.cnki.11-4762/tp.2017.01.041

TP301.6；TP18

A