邱福生，楊建平，邵緒威

(沈陽(yáng)航空航天大學(xué) 航空航天工程學(xué)部(院)，沈陽(yáng) 110136)

基于遺傳模擬退火算法的無(wú)人機(jī)航跡規(guī)劃

邱福生，楊建平，邵緒威

(沈陽(yáng)航空航天大學(xué) 航空航天工程學(xué)部(院)，沈陽(yáng) 110136)

航跡規(guī)劃技術(shù)是無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng)中重要的核心技術(shù)之一，無(wú)人機(jī)飛行空間廣闊，需要一種快速搜索最佳路徑的方法。首先在飛行區(qū)域中建立數(shù)字地圖模型和防空威脅區(qū)模型，在滿(mǎn)足無(wú)人機(jī)飛行約束條件的情況下，為無(wú)人機(jī)航跡規(guī)劃提供一種遺傳模擬退火算法，充分利用模擬退化算法的概率突跳特性和遺傳算法強(qiáng)大的快速搜索能力。仿真結(jié)果表明，使用該算法無(wú)人機(jī)能夠自動(dòng)避開(kāi)模擬數(shù)字地圖的威脅區(qū)，搜索出一條安全有效航跡，并保證航線(xiàn)的完整性和最優(yōu)性。

無(wú)人機(jī)；航跡規(guī)劃；遺傳模擬退火算法；威脅區(qū)

無(wú)人機(jī)航跡規(guī)劃就是在根據(jù)無(wú)人機(jī)自身性、戰(zhàn)場(chǎng)環(huán)境和任務(wù)要求，為其選擇一條安全有效的飛行路線(xiàn)，在現(xiàn)代日新月異的高科技空戰(zhàn)中，航跡規(guī)劃是確保飛行器對(duì)敵區(qū)進(jìn)行遠(yuǎn)程偵察和精確打擊必要途徑之一。航跡規(guī)劃技術(shù)主要是研究在航跡規(guī)劃中的算法，程國(guó)采研究的最優(yōu)控制方法由于在航跡規(guī)劃中執(zhí)行時(shí)間較慢，此算法在地形復(fù)雜、新增威脅較多的戰(zhàn)場(chǎng)環(huán)境下規(guī)劃出的航線(xiàn)不是很理想[1]。2000年Robert J Szcaerba提出的A*算法經(jīng)常應(yīng)用在機(jī)器人二維路徑規(guī)劃中，在三維的航跡規(guī)劃中常常出現(xiàn)組合爆炸的問(wèn)題[2]。Kenneny J.Eberhart研究的粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)在約束優(yōu)化過(guò)程中，罰函數(shù)的設(shè)計(jì)過(guò)于復(fù)雜，不利于求解，若約束處理的不好，其優(yōu)化的結(jié)果往往會(huì)出現(xiàn)不能夠收斂和結(jié)果是空集的狀況[3]。遺傳算法是一種全局最優(yōu)搜索算法，但容易得到局部最優(yōu)極值[4]。本文采用的遺傳模擬退火算法利用基本遺傳算法的編碼技術(shù)和概率搜索技術(shù)，在交叉和變異過(guò)程中結(jié)合模擬退火算法常用的Metropolis接受準(zhǔn)則對(duì)遺傳算法求解過(guò)程進(jìn)行擾動(dòng)[5]，跳出局部最優(yōu)解，從而得到目標(biāo)函數(shù)的全局最優(yōu)解，在航跡規(guī)劃中使用模擬退火遺傳算法能夠減少迭代次數(shù)和求解時(shí)間，并且能夠得到最優(yōu)航跡，因此在求解要求越來(lái)越高的航跡規(guī)劃領(lǐng)域，遺傳模擬退火算法在求解過(guò)程中得到了廣泛的應(yīng)用。

1 飛行區(qū)域

1.1 地形的構(gòu)建

無(wú)人機(jī)航跡規(guī)劃的首要條件就是建立數(shù)字地圖模型，其它航跡規(guī)劃元素模型的建立都是在建好的數(shù)字地圖模型上展開(kāi)，地圖模型的復(fù)雜程度直接影響著航線(xiàn)的優(yōu)越性。隨著計(jì)算機(jī)仿真技術(shù)的越來(lái)越成熟，數(shù)字地圖的仿真模擬方法也越來(lái)越多。為了使數(shù)字地圖模型在仿真過(guò)程中趨于真實(shí)，本文根據(jù)文獻(xiàn)[6]給出了一種函數(shù)模擬方法加以改進(jìn)，在文獻(xiàn)[6]提出的模型中的橫縱坐標(biāo)前添加一個(gè)調(diào)節(jié)系數(shù)，改進(jìn)后的數(shù)字地圖模型如下：

(1)

其中，x，y表示水平投影面上的點(diǎn)坐標(biāo)，Z1表示對(duì)應(yīng)水平面坐標(biāo)點(diǎn)的地形高度。a，b，c，d，e，f，g，ξ是常系數(shù)，可以通過(guò)調(diào)節(jié)a，b，c，d，e，f，g，ξ的大小來(lái)模擬各種數(shù)字地形。為了能模擬出高度、寬度和坡度各不相同的山峰，采用高斯造型法通過(guò)公式(2)來(lái)對(duì)山峰進(jìn)行構(gòu)造模擬：

(2)

其中，x，y表示水平投影面上的點(diǎn)坐標(biāo)，Z2表示對(duì)應(yīng)水平面坐標(biāo)點(diǎn)的地形高度。h(i)和xi(i)，yi(i)是山峰的輪廓參數(shù)，i表示第i座山峰的山體，通過(guò)公式(3)：

Z(x,y)=max(Z1(x,y),Z2(x,y))

(3)

可以將山峰和起伏的地貌通過(guò)取兩者較大高程值的方法疊加融合到一起，形成一個(gè)完整的地形[7]，如圖1所示。

1.2 防空武器威脅區(qū)模型

雷達(dá)是軍事上低空突防時(shí)具有較大威脅的探測(cè)設(shè)備，其探測(cè)能力易受周邊環(huán)境的影響，如果考慮各種影響因素，精確的描述雷達(dá)的探測(cè)能力非常復(fù)雜，一般用雷達(dá)的探測(cè)空域來(lái)考察其威脅性能，雷達(dá)主要依靠短電磁波沿直線(xiàn)傳播，電磁波傳播的距離越遠(yuǎn)，電磁波的能量越弱，則威脅代價(jià)也越小。地空導(dǎo)彈是防空火力最重要的火力部分，一般配置在主要目標(biāo)附近，對(duì)射程內(nèi)的無(wú)人機(jī)有較高的殺傷概率，在無(wú)人機(jī)進(jìn)行航跡規(guī)劃時(shí)應(yīng)當(dāng)避免飛入導(dǎo)彈的威脅區(qū)域。在導(dǎo)彈威脅區(qū)域內(nèi)，無(wú)人機(jī)距離導(dǎo)彈位置越遠(yuǎn)，威脅代價(jià)越小[8]。雷達(dá)和地空導(dǎo)彈的威脅代價(jià)都是隨著無(wú)人機(jī)距離雷達(dá)和地空導(dǎo)彈越遠(yuǎn)而越小，將雷達(dá)和地空導(dǎo)彈的威脅空域映射到定高的二維平面上組成防空武器威脅區(qū)域，防空武器威脅模型合并為如下數(shù)學(xué)模型：

圖1 模擬地形圖

(4)

其中，fLDi表示第i段航跡被雷達(dá)和導(dǎo)彈威脅的代價(jià)，β為參數(shù)，表示無(wú)人機(jī)在第i段航跡距離雷達(dá)和導(dǎo)彈中心最近點(diǎn)受雷達(dá)和導(dǎo)彈的威脅的強(qiáng)度，它與威脅概率和威脅密度有關(guān)，di表示第雷達(dá)和導(dǎo)彈威脅中心點(diǎn)第i段航跡的距離，R表示雷達(dá)和導(dǎo)彈的威脅半徑。

圖2 威脅區(qū)模擬圖

2 含約束條件的最優(yōu)航跡規(guī)劃問(wèn)題

2.1 航跡約束條件

在對(duì)無(wú)人機(jī)航跡規(guī)劃時(shí)要充分考慮其性能限制，一般要考慮以下5個(gè)方面的約束條件：

(1)航跡最小步長(zhǎng):無(wú)人機(jī)在飛行過(guò)程中，在改變飛行姿態(tài)機(jī)動(dòng)前和機(jī)動(dòng)后，無(wú)人機(jī)應(yīng)保持一段距離的直飛狀態(tài)，這個(gè)距離稱(chēng)為最小步長(zhǎng)。多次改變飛行姿勢(shì)容易增大導(dǎo)航誤差，設(shè)li表示第i段航跡長(zhǎng)度，lmin表示最小航跡段長(zhǎng)度，該約束表示為：

li≥lmin(i=1，2，3…，n)

(5)

(2)最大轉(zhuǎn)彎角：無(wú)人機(jī)的機(jī)動(dòng)性能受到轉(zhuǎn)彎角α的限制，該限制取決于飛行器的過(guò)載能力和飛行任務(wù)。新生成的航跡段只能在最大轉(zhuǎn)彎角的范圍內(nèi)轉(zhuǎn)彎。

圖3 最大轉(zhuǎn)彎角約束

(6)

(7)

(4)最小離地高度：無(wú)人機(jī)在飛行過(guò)程中，為了不被雷達(dá)或地空導(dǎo)彈威脅，應(yīng)盡量貼地飛行，但如果離地面高度太小易發(fā)生撞地事件，因此要設(shè)定一個(gè)合適的最小離地高度[9]。設(shè)第i個(gè)航跡點(diǎn)[xi,yi,h(xi,yi)]，h(xi,yi)為第i個(gè)航跡點(diǎn)的飛行高度，Z(xi,yi)為地理模型的海拔高度，hmin為離地最小飛行高度，所以該約束可以表示為:

h(xi,yi)-Z(xi,yi)≥hmin

(8)

(5)航跡總長(zhǎng)約束：無(wú)人機(jī)在飛行過(guò)程中受到耗油率和載油量的限制，必須要求飛行的總航程越小越好[10]，設(shè)dmax為最大航跡長(zhǎng)度，等于1.5倍出發(fā)點(diǎn)到目標(biāo)點(diǎn)的直線(xiàn)距離，所以航跡總長(zhǎng)約束可以表示為：

(9)

(6)機(jī)動(dòng)點(diǎn)數(shù)量:機(jī)動(dòng)點(diǎn)的數(shù)量直接影響著航跡規(guī)劃的精度，當(dāng)精度要求較高時(shí)，可以增加機(jī)動(dòng)點(diǎn)的數(shù)量，反之可以減少機(jī)動(dòng)點(diǎn)的數(shù)量。機(jī)動(dòng)點(diǎn)的數(shù)量增加較多時(shí)，會(huì)導(dǎo)致導(dǎo)航誤差增大和計(jì)算時(shí)間延長(zhǎng)。所以，需要根據(jù)具體的飛行任務(wù)要求來(lái)決定機(jī)動(dòng)點(diǎn)的數(shù)量。

2.2 威脅代價(jià)函數(shù)

當(dāng)無(wú)人機(jī)進(jìn)行三維航跡規(guī)劃時(shí)，實(shí)質(zhì)上是一個(gè)多約束優(yōu)化問(wèn)題，本文對(duì)航跡規(guī)劃威脅代價(jià)函數(shù)采用線(xiàn)性加權(quán)的指標(biāo)方法[11]。

(10)

其中l(wèi)i表示第i段航跡的長(zhǎng)度，hi表示第i段航跡的海拔高度，fLDi表示第i段航跡被雷達(dá)和導(dǎo)彈威脅代價(jià)，w1，w2，w3為權(quán)系數(shù)，w1+w2+w3=1，由w2/w1的大小來(lái)選擇飛機(jī)是從上方飛越還是從障礙側(cè)邊繞過(guò)，w3/w1的大小決定讓飛機(jī)直接穿越雷達(dá)威脅區(qū)還是繞過(guò)威脅區(qū)。

3 遺傳模擬退火算法求解流程

遺傳算法在航跡規(guī)劃中得到了廣泛的應(yīng)用，遺傳算法的選擇、交叉和變異算子在搜索最佳的航跡路線(xiàn)時(shí)，能夠以隨機(jī)的方式得到尋求最優(yōu)解，新一代的子群體主要是通過(guò)上一代父群體之間進(jìn)行交叉重組產(chǎn)生的，容易得到全局最優(yōu)解附近的局部最優(yōu)解，所以，單純的使用遺傳算法容易導(dǎo)致早熟和陷入局部最優(yōu)解，而模擬退火算法能夠?qū)z傳算法尋優(yōu)過(guò)程進(jìn)行擾動(dòng)，具有擺脫局部最優(yōu)解的能力，在交叉和變異過(guò)程中用Metropolis準(zhǔn)則判斷新解是否可以被接受，使用兩者結(jié)合的遺傳模擬退火算法能夠有效的解決陷入局部最優(yōu)解問(wèn)題，從而得到全局最優(yōu)解[4]。

設(shè)定種群規(guī)模M,最大遺傳操作代數(shù)N，交叉概率pc，變異概率pm，初始溫度T=T0,溫度更新次數(shù)j=0，設(shè)定退火溫度變化規(guī)律為T(mén)j+1=0.9Tj，終止溫度為T(mén)e。遺傳模擬退火算法流程如圖4所示：

4 仿真實(shí)驗(yàn)

為了驗(yàn)證模擬遺傳退火算法的可靠性，對(duì)算法進(jìn)行仿真實(shí)驗(yàn)，結(jié)合模擬地形圖和威脅區(qū)模擬圖，取最小步長(zhǎng)lmin=2 km，最大轉(zhuǎn)彎角α=450，最大俯仰角θ=300，最小離地高度hmin=0.05 km，取各權(quán)重系數(shù)w1=0.4，w2=0.4，w3=0.2，種群規(guī)模M=20，最大迭代操作代數(shù)N=80，交叉概率pc=0.4，變異概率pm=0.1，初始溫度T=T0=100，終止溫度Te=60，航線(xiàn)起始點(diǎn)坐標(biāo)為(0，20)，目標(biāo)點(diǎn)坐標(biāo)(200，200)，仿真結(jié)果如圖5-圖7所示。

圖4 遺傳模擬退火算法流程圖

圖5 適應(yīng)度曲線(xiàn)

迭代次數(shù)為51次，航跡總長(zhǎng)3.372 6×105m，通過(guò)圖6和圖7可以看出，通過(guò)本文提出的遺傳模擬退火算法，無(wú)人機(jī)能夠有效的避開(kāi)山體障礙和威脅區(qū)，并根據(jù)地形和適應(yīng)度函數(shù)有效的選擇最佳路徑，最后能夠得到滿(mǎn)足無(wú)人機(jī)約束性能的航跡。

圖6 航跡規(guī)劃三維示意圖

圖7 航跡規(guī)劃等高示意圖

5 結(jié)論

本文首先建立數(shù)字地形和防空武器威脅區(qū)模型，給出代價(jià)函數(shù)，并對(duì)無(wú)人機(jī)飛行性能進(jìn)行約束，本文提出的遺傳模擬退火算法是將模擬退火算法中常用的Metropolis接受準(zhǔn)則引入到遺傳算法的交叉和變異過(guò)程中，這使得算法可以避免基本遺傳算法陷入局部最優(yōu)解，通過(guò)擾動(dòng)跳出局部最優(yōu)解，從而得到全局最優(yōu)解，減少迭代次數(shù)并保證了算法的收斂性,在三維航跡規(guī)劃快速搜索最佳路徑領(lǐng)域有較好的應(yīng)用前景。本文使用的算法在山峰和防空威脅區(qū)數(shù)量較少的情況下較適用，對(duì)于戰(zhàn)場(chǎng)地形環(huán)境特別復(fù)雜和實(shí)時(shí)規(guī)避動(dòng)態(tài)防空威脅區(qū)域的問(wèn)題還需要進(jìn)一步的研究。

[1]楊軍，朱學(xué)平，朱蘇朋，等.飛行器最優(yōu)控制[M].北京：國(guó)防工業(yè)出版社，2011.

[2]Robert J Szcaerba J.Robust algorithm for real-time router planning[J].IEEE Transactions 0n Aerospace and Electronic System,2000，36(3):869-875.

[3]Kenneny J,Eberhart R C.Particle swarm optimization[C].IEEE International Conference on Neural Networks,Perth,Western Australia,1995.

[4]鞏敦衛(wèi)，郝國(guó)生，周勇,等.交互式遺傳算法原理及其應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2007.

[5]Krikpatrick S,Gelett C,Veechi M.Optimization by simulated annealing[J].Science,1983,200(8):671-680.

[6]Ioannis K Nikolos,Kimon P.Valavanis,Nikos C.Sourveloudis.Evolutionary algorithm based offline/online path panner for UAV nvigation[J].EE Transactions on Systems Man and Cybernetics,2003,33(6):898-912.

[7]劉娟.小型無(wú)人機(jī)地面站電子地圖子系統(tǒng)研究與設(shè)計(jì)[D].呼和浩特：內(nèi)蒙古工業(yè)大學(xué)，2009.

[8]張延松.基于遺傳算法的無(wú)人機(jī)航跡規(guī)劃研究[D].長(zhǎng)沙：中南大學(xué)，2010.

[9]巴海濤.無(wú)人機(jī)航跡規(guī)劃方法研究[D].西安：西北工業(yè)大學(xué)，2006.

[10]柳長(zhǎng)安.無(wú)人機(jī)航路規(guī)劃方法研究[D].西安：西北工業(yè)大學(xué)，2003.

[11]鄭昌文，嚴(yán)平，丁明躍,等.飛行器航跡規(guī)劃[M].北京：國(guó)防工業(yè)出版社,2008.

(責(zé)任編輯：宋麗萍 英文審校：劉敬鈺)

UAVrouteplanningbasedonthegeneticsimulatedannealingalgorithm

QIU Fu-sheng，YANG Jian-ping，SHAO Xu-wei

Faculty of Aerospace Engineering，Shenyang Aerospace University，Shenyang 110136)

Path planning technology is one of the core technologies of UAV mission planning system.UAV flight space is large,which needs a method to quickly find out the best path.This paper sets up a digital map model and a model for air defense threat area in the airfield domain.Under the condition of meeting the UAV flight constraints,the paper provides a genetic simulated annealing algorithm for UAV track planning,and makes full use of the probability kick features of simulation degradation algorithm and powerful ability of fast searching genetic algorithm.Simulation results show that with this algorithm,UAV can automatically avoid the threatened field of simulated digital map area,search out a safe and effective path,and ensure the integrity and optimality of their routes.

UAV;route planning;genetic simulated annealing algorithm;threatened area

2013-11-05

邱福生(1977-)，男，江西于都人，副教授，主要研究方向：飛機(jī)系統(tǒng)設(shè)計(jì)與試驗(yàn)技術(shù)、飛行器設(shè)計(jì)與制造一體化(CAX集成技術(shù)/DFX)，E-mail:shenhangsau2011@sina.com。

2095-1248(2014)01-0016-04

V249.12

A

10.3969/j.issn.2095-1248.2014.01.004