基于人工免疫克隆選擇算法的無人機三維航跡規劃

武 健, 舒健生, 李亞雄, 蘇國華, 何艷萍

(1. 火箭軍工程大學作戰規劃教研室, 陜西 西安 710025; 2. 火箭軍裝備研究院三所, 北京 100094)

0 引 言

無人機(unmanned aerial vehicle,UAV)在軍事戰略中起著越來越重要的作用,作為任務規劃系統的核心之一,航跡規劃技術大大提高了UAV的作戰效能。如何為UAV規劃出一條參考飛行航跡是一項重要而又復雜的工作。

UAV航跡規劃屬于非確定性多項式(non-deterministic polynomial, NP)問題,國內外學者圍繞該問題展開了大量的研究,航跡規劃算法大致包括:①動態規劃法、A*算法、Voronoi算法等確定型算法[1-5];②模擬退火、神經網絡算法、遺傳算法、蟻群算法和粒子群優化算法及其改進算法等隨機型航跡規劃[6-18]。目前的算法研究一般基于一定的假設條件,使得算法在工程應用有一定的局限性。

工程中UAV航跡規劃分兩步完成:第一,平時進行預處理工作,并儲存預處理結果;第二,基于預處理結果,采用人工方法進行航跡規劃。工程中的航跡分步規劃方法能夠借助人較強的跳躍性思維能力快速地處理多要素、多約束、時變性的優化問題,但該方法在規劃時間和規劃精度上都有很大的改進空間。

本文將工程中的航跡分步規劃方法與人工免疫克隆選擇(artificial immune clone selection, AICS)算法相結合,提出了基于AICS的航跡自動規劃方法。由于UAV的水平航跡和縱向航跡有一定的獨立性,在航跡規劃中分兩步進行:第一,對于給定的可行水平航跡,尋找與其對應的最優縱向航跡;第二,利用AICS尋找一條水平航跡,以確保與其相對應的飛行航跡為最優。本文方法能夠充分發揮計算機速度快的特點,進一步提高航跡規劃結果的精度,更好地滿足UAV控制要求;同時,能進一步降低航跡規劃的工作時間,更好地滿足實際工作時間要求。

1 水平航跡描述及約束條件分析

1.1 水平航跡控制變量

UAV水平航跡是其飛行航跡在水平面內的投影,水平航跡的運動形式分為水平直飛和水平轉彎。在水平轉彎半徑Rsp給定的情況下,水平航跡由一組有序排列的線段連接而成,航跡可以用各折點的直角坐標(xi,yi)描述,給定折點坐標,則航跡確定,也可以采用極坐標(ri,θi)的形式,取一組有序連接有向線段的各個有向線段的起點、長度和方向所構成的集合。

由于起點(x0,y0)、終點(xn,yn)已知,因此水平航跡控制變量可以取為一組有序連接的n-1個局部極坐標:(ri,θi),i=1,2,…,n。

其中,ri為第i個有向線段的長度;θi為第i個有向線段前進方向相對于第i-1個有向線段前進方向的夾角,定義θi方位角逆時針為正,順時針為負,取第1個有向線段的前進方向變化量θ1以起點的正東方向為基準。

1.2 水平航跡變化規律

對于直飛段,只要確定出直飛段的起點和終點即可;對于轉彎段,除了確定出轉彎段的起點和終點,還必須給出起點到終點的轉動方向,由兩個相鄰直飛方向的方向變化θi+1和水平轉彎半徑Rsp確定,如圖1所示。

圖1 航跡轉彎段示意圖Fig.1 Sketch map of route curve section

(1)

(2)

(3)

1.3 飛行環境分析

UAV一般采用組合導航方案,其主要特點表現為慣性導航為主,地形匹配、景象匹配、GPS制導、氣壓高度修正等為輔。以地形匹配區為例,開展UAV飛行環境分析,航跡約束條件分析及航跡規劃研究。

地形匹配系統是利用UAV飛行航跡地面投影點的地形高程起伏特性對其實時定位的一種非連續定位系統。UAV在飛越地形匹配區時,彈上的高度系統(氣壓高度表、雷達高度表)測量出UAV下方地形剖面的起伏變化,然后與預先存儲在計算機存儲器中的基準地形匹配區進行相關計算,找出最佳匹配的基準地形剖面,并計算出UAV位置,從而修正由于慣性導航所帶來的實際偏差。

地形匹配的時機和地形匹配區面積是根據慣性導航的誤差散布及可匹配的地形決定的。原則上,當慣性導航的位置誤差積累達到一定值時,應根據地形的具體情況安排一次地形匹配定位,從而及時修正慣性導航的位置誤差和速度誤差。如果在飛行中,有一段航程內沒有合適的地形匹配區,可以再增加航程并根據慣導誤差散布的實際情況,安排較大面積的地形匹配搜索區,即UAV飛行一定距離后就需要一個具備一定長度跟寬度的地形匹配區。

1.4 水平航跡約束條件分析

在UAV航跡規劃中,除考慮自身技術性能的約束外,還必須充分考慮地形匹配約束,因此影響水平航跡的約束條件主要有:

(1) 水平轉彎角度θi的約束:θi≤θmax;

(2) 各水平直飛段航程ri的約束:ri≥rmax;

(3) 水平航跡總航程S的約束:S≤Smax;

2 水平航跡可行時縱向航跡優化模型

2.1 縱向航跡控制變量

UAV縱向航跡是其飛行航跡在縱平面的投影,其控制變量就是一組能夠確定縱向航跡的變量,縱向航跡控制變量可以取為各個水平轉彎、地形匹配等特定平飛段的飛行高度Hi(i=1,2,…)。

2.2 縱向航跡約束條件分析

2.2.1 水平轉彎段的平飛高度取值范圍

其中,Hmax為UAV最大升限。

2.2.2 地形匹配段的平飛高度取值范圍

在給定地形及UAV爬坡、下滑等相關參數,水平航跡的條件下,可以根據約束快速確定縱向航跡[19]。

3 基于AICS的航跡規劃模型

3.1 基于AICS的航跡規劃流程

基于上述分析,在給定水平航跡的基礎上,可以確定一條滿足約束的最優縱向航跡,航跡規劃問題轉換成了尋找一條水平航跡的過程。

取水平航跡控制變量(ri,θi)為優化變量,其維數是可變的,AICS不涉及交叉問題,比較適合于該問題的求解,同時AICS在收斂速度和多樣性保持方面也取得了較好的效果。本文在確定編碼方式、克隆操作、免疫基因操作及克隆選擇操作的基礎上,建立了基于AICS的航跡規劃模型。

(1) 編碼方式

在本文中,參考航跡優化是取水平航跡控制變量為優化變量的,因此構建抗體為d(可變)維向量[(r1,θ1),(r2,θ2),…,(rd,θd)],采用實數編碼的方式。

(2) 群體規模

人工免疫算法中常將群體規模設定為個體編碼長度最大值的一個線性倍數,如取為N2和2N2之間的確定數,而N=max(dk)。群體規模按m=int[1.5N2]確定,其中m為群體規模;int[]為取整函數。

初始種群采用隨機的方式產生,因為隨機選取可保證初始解分布的均勻性。抗體[(r1,θ1),(r2,θ2),…,(rd,θd)]中ri、θi按式(4)產生。

i=1,2,…,d

(4)

式中,(ri_min,ri_max)、(θi_min,θi_max)為UAV水平直飛距離的最小值/最大值邊界、水平轉彎角度的最小值/最大值邊界;rand()為0～1的隨機數。

(3) 適應度計算

仿真中適應度取UAV平均飛行高度。

(4) 克隆操作

采用整體克隆的方式,即對任意一個抗體采用相同的克隆比例R。

(5) 免疫基因操作

免疫基因操作主要包括克隆重組操作和克隆變異操作,免疫學認為親和度成熟和抗體多樣性的產生主要是依靠抗體的高頻變異,而非交叉或重組,因此采取均勻變異的克隆變異操作,即對抗體[(r1,θ1),(r2,θ2),…,(rd,θd)]的隨機位i選擇變異,變異后的取值如式(5)所示。

(5)

(6) 克隆選擇操作

在實施克隆操作之前,根據抗體適應度進行選擇操作。

3.2 仿真計算及結果分析

3.2.1 仿真條件

仿真地形有多種典型生成方法,本文采用經典的中點位移法生成地形[20],具有4個地形匹配區,其頂點坐標如表1所示。

表1 地形匹配區數據

發射點坐標(0,0,0.02),目標點坐標(600,600,0.75),單位為km。

人工免疫算法參數:群體規模m=20,克隆比例R=1.5,變異概率pm=0.4,最大迭代次數Imax=50。

3.2.2 仿真結果

基于上述條件進行仿真,仿真流程如圖2所示,仿真結果如圖3～圖8所示,穿越匹配區結果如表2所示。

圖2 航跡規劃流程圖Fig.2 Flow diagram of route planning

圖3 航跡規劃結果Fig.3 Result of route planning

圖4 三維航跡Fig.4 Three-dimensional route planning

圖5 航跡水平投影圖Fig.5 Horizontal projection of route

圖6 穿越地形匹配區示意圖Fig.6 Sketch map of passing the terrain matching area

圖7 指標優化曲線Fig.7 Index optimization curve

圖8 縱向航跡示意圖Fig.8 Sketch map of vertical route

3.2.3 仿真結果分析

從仿真結果中可以看出,在給定相關參數,以高度為優化指標,得到了一條靠近山谷的飛行航跡,符合預期,驗證了模型的可靠性。因此,在水平航跡變化規律、狀態特征計算、可行性判定及縱向航跡優化的基礎上,采用AICS算法可以實現UAV航跡規劃。同時,AICS算法表現了較好的收斂性。

4 結 論

本文提出了一種基于AICS的UAV航跡規劃方法,克服了傳統方法工程化過程中假設條件較多的缺點,優點如下:

(1) 采用了分步規劃策略,將復雜的航跡規劃問題分解為水平航跡規劃規劃和縱向航跡規劃;

(2) 提出了易于計算機描述的水平航跡控制變量(ri,θi)和縱向航跡控制變量Hi;

(3) 設計了基于AICS的UAV航跡規劃方法,仿真結果驗證了方法的可行性和有效性,同時該方法能充分發揮計算機容量大、速度快的優點,對傳統的人工航跡規劃方法進行一定程度上的改進。

[1] PEHLIVANOGLU Y V. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J].Aerospace Science and Technology,2012,16(1):47-55.

[2] CHEN X, CHEN X M. The UAV dynamic path planning algorithm research based on Voronoi diagram[C]∥Proc.of the 26th Chinese Control and Decision Conference, 2014: 1069-1071.

[3] WANG Z, LIU L, LONG T. Enhanced sparseA*search for UAV path planning using Dubins path estimation[C]∥Proc.of the 33rd Chinese Control Conference, 2014:738-742.

[4] JENNINGS A L, ORDONEZ R, CECCARELLI N. Dynamic programming applied to UAV way point path planning in wind[C]∥Proc.of the IEEE International Symposium on Computer-aided Control System Design, 2008: 215-220.

[5] 符小衛, 高曉光. 基于貝葉斯優化的三維飛行航跡規劃[J]. 兵工學報, 2007, 28(11): 1340-1346.

FU X W, GAO X G. 3D flight path planning based on Bayesian optimization algorithm[J]. Acta Armamentarii, 2007, 28(11): 1340-1346.

[6] 倪天權, 王建東, 劉以安. 交叉粒群算法在無人機航路規劃中的應用[J]. 系統工程與電子技術, 2011, 33(4): 806-810.

NI T Q, WANG J D, LIU Y A. Application of particle swarm algorithm in route planning of UAV[J]. Systems Engineering and Electronics, 2011, 33(4): 806-810.

[7] 蘇菲,彭輝,沈林成.基于協進化多子群蟻群算法的多無人作戰飛機協同航跡規劃研究[J].兵工學報,2009,30(11):1562-1567.

SU F, PENG H, SHEN L C. Research on multi-UCAV cooperative route planning based on coevolutionary multi-ant-colony algorithm[J]. Acta Armamentarii, 2009, 30(11): 1562-1567.

[8] 傅陽光, 周成平, 胡漢平. 無人飛行器海上航跡規劃差分進化算法研究[J]. 兵工學報, 2012, 33(3): 295-301.

FU Y G, ZHOU C P, HU H P. Research on differential evolution algorithm for path planning for unmanned aerial vehicle in ocean environment[J]. Acta Armamentarii, 2012, 33(3): 295-301.

[9] AL-SABBAN W H, GONZALEZ L F, SMITH R N. Wind-energy based path planning for electric unmanned aerial vehicles using markov decision processes[C]∥Proc.of the IEEE International Conference on Robotics and Automation, 2013: 784-789.

[10] BAEK S S, KWON H, YODER J A, et al. Optimal path planning of a target following fixed-wing UAV using sequential decision processes[C]∥Proc.of the IEEE/RSJ International Conference on Intelligent Robots and System, 2013: 2955-2962.

[11] DONG Z N, ZHANG R L, CHEN Z J, et al. Study on UAV path planning approach based on fuzzy virtual force[J]. Chinese Journal of Aeronautics, 2010, 23(3): 341-350.

[12] WANG Q, CHANG A, SUN H Y. MPC and SADE for UAV real-time path planning in 3D environment[C]∥Proc.of the IEEE International Conference on Security, 2014: 130-133.

[13] 齊乃明, 孫小雷, 董程, 等. 航跡預測的多無人機任務規劃方法[J]. 哈爾濱工業大學學報, 2016, 48(4): 32-35.

QI N M, SUN X L, DONG C, et al. Mission planning based on path prediction for multiple UAVs[J]. Journal of Harbin Institute of Technology, 2016, 48(4): 32-35.

[14] 高穎, 陳旭, 周士軍, 等. 基于改進蟻群算法的多批次協同三維航跡規劃[J]. 西北工業大學學報, 2016, 34(1): 41-45.

GAO Y, CHEN X, ZHOU S J, et al. Planning based on improved ant colony algorithm multiple batches collaborative three-dimensional track[J]. Journal of Northwestern Polytechnical University, 2016, 34(1): 41-45.

[15] BELLINI A C, LU W, NALDI R, et al. Information driven path planning and control for collaborative aerial robotic sensors using artificial potential functions[C]∥Proc.of the American Control Conference, 2014:590-597.

[16] OZALP N, SAHINGOZ O K. Optimal UAV path planning in a 3D threat environment by using parallel evolutionary algorithms[C]∥Proc.of the IEEE International Conference on Unmanned Aircraft Systems, 2013: 308-317.

[17] FU Y G, DING M Y, ZHOU C P. Routing planning for unmanned aerial vehicle (UAV) on the sea using hybrid differential evolution and quantum-behaved particle swarm optimization[J]. IEEE Trans.on Systems,Man,and Cybernetic: System,2013,43(6):1451-1465.

[18] ZAZA T, RICHARDS A. Ant colony optimization for routing and tasking problems for teams of UAVs[C]∥Proc.of the UKACC International Conference on Control, 2014: 652-655.

[19] 向明思, 劉新學, 郝輝. 相鄰特定平飛段之間縱向航跡的快速規劃算法研究[J]. 四川兵工學報, 2013, 34(1): 97-100.

XIANG M S, LIU X X, HAO H. Fast planning algorithm of vertical track between adjacent specific level flight segments[J]. Acta Armamentarii of Sichuan, 2013, 34(1): 97-100.

[20] 梁俊,王琪,劉坤良,等.基于隨機中點位移法的三維地形模擬[J].計算機仿真,2005,22(1):213-215.

LIANG J, WANG Q, LIU K L, et al. 3D terrain simulation based on the method of random mid-point displacement[J]. Computer Simulation, 2005, 22(1): 213-215.