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

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

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

0 引 言

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

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

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

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

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

1.1 水平航跡控制變量

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

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

其中,ri為第i個(gè)有向線段的長度;θi為第i個(gè)有向線段前進(jìn)方向相對于第i-1個(gè)有向線段前進(jìn)方向的夾角,定義θi方位角逆時(shí)針為正,順時(shí)針為負(fù),取第1個(gè)有向線段的前進(jìn)方向變化量θ1以起點(diǎn)的正東方向?yàn)榛鶞?zhǔn)。

1.2 水平航跡變化規(guī)律

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

圖1 航跡轉(zhuǎn)彎段示意圖Fig.1 Sketch map of route curve section

(1)

(2)

(3)

1.3 飛行環(huán)境分析

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

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

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

1.4 水平航跡約束條件分析

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

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

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

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

2 水平航跡可行時(shí)縱向航跡優(yōu)化模型

2.1 縱向航跡控制變量

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

2.2 縱向航跡約束條件分析

2.2.1 水平轉(zhuǎn)彎段的平飛高度取值范圍

其中,Hmax為UAV最大升限。

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

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

3 基于AICS的航跡規(guī)劃模型

3.1 基于AICS的航跡規(guī)劃流程

基于上述分析,在給定水平航跡的基礎(chǔ)上,可以確定一條滿足約束的最優(yōu)縱向航跡,航跡規(guī)劃問題轉(zhuǎn)換成了尋找一條水平航跡的過程。

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

(1) 編碼方式

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

(2) 群體規(guī)模

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

初始種群采用隨機(jī)的方式產(chǎn)生,因?yàn)殡S機(jī)選取可保證初始解分布的均勻性?？贵w[(r1,θ1),(r2,θ2),…,(rd,θd)]中ri、θi按式(4)產(chǎn)生。

i=1,2,…,d

(4)

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

(3) 適應(yīng)度計(jì)算

仿真中適應(yīng)度取UAV平均飛行高度。

(4) 克隆操作

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

(5) 免疫基因操作

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

(5)

(6) 克隆選擇操作

在實(shí)施克隆操作之前,根據(jù)抗體適應(yīng)度進(jìn)行選擇操作。

3.2 仿真計(jì)算及結(jié)果分析

3.2.1 仿真條件

仿真地形有多種典型生成方法,本文采用經(jīng)典的中點(diǎn)位移法生成地形[20],具有4個(gè)地形匹配區(qū),其頂點(diǎn)坐標(biāo)如表1所示。

表1 地形匹配區(qū)數(shù)據(jù)

發(fā)射點(diǎn)坐標(biāo)(0,0,0.02),目標(biāo)點(diǎn)坐標(biāo)(600,600,0.75),單位為km。

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

3.2.2 仿真結(jié)果

基于上述條件進(jìn)行仿真,仿真流程如圖2所示,仿真結(jié)果如圖3～圖8所示,穿越匹配區(qū)結(jié)果如表2所示。

圖2 航跡規(guī)劃流程圖Fig.2 Flow diagram of route planning

圖3 航跡規(guī)劃結(jié)果Fig.3 Result of route planning

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

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

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

圖7 指標(biāo)優(yōu)化曲線Fig.7 Index optimization curve

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

3.2.3 仿真結(jié)果分析

從仿真結(jié)果中可以看出,在給定相關(guān)參數(shù),以高度為優(yōu)化指標(biāo),得到了一條靠近山谷的飛行航跡,符合預(yù)期,驗(yàn)證了模型的可靠性。因此,在水平航跡變化規(guī)律、狀態(tài)特征計(jì)算、可行性判定及縱向航跡優(yōu)化的基礎(chǔ)上,采用AICS算法可以實(shí)現(xiàn)UAV航跡規(guī)劃。同時(shí),AICS算法表現(xiàn)了較好的收斂性。

4 結(jié) 論

本文提出了一種基于AICS的UAV航跡規(guī)劃方法,克服了傳統(tǒng)方法工程化過程中假設(shè)條件較多的缺點(diǎn),優(yōu)點(diǎn)如下:

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

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

(3) 設(shè)計(jì)了基于AICS的UAV航跡規(guī)劃方法,仿真結(jié)果驗(yàn)證了方法的可行性和有效性,同時(shí)該方法能充分發(fā)揮計(jì)算機(jī)容量大、速度快的優(yōu)點(diǎn),對傳統(tǒng)的人工航跡規(guī)劃方法進(jìn)行一定程度上的改進(jìn)。

[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] 符小衛(wèi), 高曉光. 基于貝葉斯優(yōu)化的三維飛行航跡規(guī)劃[J]. 兵工學(xué)報(bào), 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] 倪天權(quán), 王建東, 劉以安. 交叉粒群算法在無人機(jī)航路規(guī)劃中的應(yīng)用[J]. 系統(tǒng)工程與電子技術(shù), 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] 蘇菲,彭輝,沈林成.基于協(xié)進(jìn)化多子群蟻群算法的多無人作戰(zhàn)飛機(jī)協(xié)同航跡規(guī)劃研究[J].兵工學(xué)報(bào),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] 傅陽光, 周成平, 胡漢平. 無人飛行器海上航跡規(guī)劃差分進(jìn)化算法研究[J]. 兵工學(xué)報(bào), 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] 齊乃明, 孫小雷, 董程, 等. 航跡預(yù)測的多無人機(jī)任務(wù)規(guī)劃方法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 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ìn)蟻群算法的多批次協(xié)同三維航跡規(guī)劃[J]. 西北工業(yè)大學(xué)學(xué)報(bào), 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] 向明思, 劉新學(xué), 郝輝. 相鄰特定平飛段之間縱向航跡的快速規(guī)劃算法研究[J]. 四川兵工學(xué)報(bào), 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ī)中點(diǎn)位移法的三維地形模擬[J].計(jì)算機(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.