基于改進A*算法的無人機航跡規劃

張帥, 李學仁, 張鵬, 李博

(1.空軍工程大學 航空航天工程學院, 陜西 西安 710038;2.航空電子系統綜合技術重點實驗室, 上海 200233)

基于改進A*算法的無人機航跡規劃

張帥1,2, 李學仁1, 張鵬1, 李博1

(1.空軍工程大學 航空航天工程學院, 陜西 西安 710038;2.航空電子系統綜合技術重點實驗室, 上海 200233)

摘要:借鑒A*算法思想,提出了一種改進A*算法的無人機航跡規劃方法。針對在傳統A*算法中將規劃區域柵格化、只能在特定方向按照特定步長擴展節點的不足,采用圓形節點擴展方法,可以實現變方向和變步長擴展節點。通過仿真進行了驗證,結果表明改進的航跡規劃方法可以繞過威脅,安全到達目標點。

關鍵詞:無人機; 航跡規劃; 節點擴展

0引言

目前,國內外對無人機的航跡規劃已進行了大量的研究,關于航跡規劃的方法也有很多,特別是大量的智能算法,如:蟻群算法、神經網絡法、粒子群算法、遺傳算法、模擬退火算法等。文獻[1]運用粒子群算法和遺傳算法對無人機進行了航跡規劃,對比了這兩種方法,遺傳算法存在費時、遺傳因子不好選擇的缺點,在接近最優解時,收斂速度會很慢;而粒子群算法在復雜問題上有早熟收斂和收斂性能差的缺點。文獻[2]將蟻群算法運用到無人機航路規劃中,其缺點是容易陷入局部最優的陷阱，并且收斂速度較慢。文獻[3]采用模擬退火算法進行無人機航跡規劃,該算法對初始解有較強的依賴性,可能陷于局部最小,雖然理論上可以跳出來,但需要經過很長的時間。

本文在借鑒了A*算法思想的基礎上,提出了一種新的、易實現的改進型A*無人機航跡規劃方法。傳統的A*算法將規劃區域柵格化,節點擴展只限于柵格線的交叉點,擴展方向和步長都受到了限制。本文采用圓形節點擴展法,從起始位置出發,先確定最佳擴展方向,然后根據設定的步長,得到下一擴展點,再以下一擴展點為初始位置,繼續搜尋最佳擴展方向,按照步長得到下一擴展點,如此循環,直至到達目標點。最后,通過仿真驗證了算法的可行性。

1問題描述

無人機航跡規劃是根據任務需要,在給定的規劃空間里,在滿足地形限制、敵方雷達、防空火力威脅、氣象分布、自身機動特性等一系列約束條件下,找到一條從起始點到目標點的最滿意或最優的路徑,使得所花代價最小,安全系數最高,并保證任務能圓滿完成[4]。航跡規劃涉及的學科和知識較廣,是一項比較復雜的工程。

無人機實際飛行過程包括起飛、爬升、巡航、下降、著陸等階段。本文主要針對無人機在巡航階段的航跡規劃進行研究,假設無人機在飛行過程中高度和速度保持不變,則航跡規劃就變為一個在二維平面的規劃問題。

2威脅模型

在無人機飛行過程中,會遇到各種各樣的威脅,主要包括:(1)地形威脅:防止飛行過程中與山峰碰撞或低于安全高度而墜地;(2)雷達和火力威脅:防止被探測到而擊落;(3)氣象威脅:防止誤入氣象條件復雜的空間;(4)敵方設置的禁飛區等。無人機需要及時地規避各種威脅,所以在進行航跡規劃時,需要對威脅信息有充分的考慮。而在這些威脅中,最主要的來源是地形威脅和敵方雷達的探測威脅,因此,本文重點考慮這兩種威脅。

2.1地形威脅

很多情況下,無人機在執行任務時,由于山峰等對雷達形成探測盲區,需要借助地形的掩護,實行低空突防[5]。但進行低空突防時,由于飛行高度比較低,容易發生碰撞,致使無人機墜毀。所以,在飛行過程中,山峰地形是一個很大的威脅。本文采用如下函數建立山峰威脅概率模型:

(1)

式中:(xpi,ypi)為第i個山峰中心點在平面上的位置坐標;λ為一個參數,可以通過λ來調節山峰在二維規劃平面上威脅作用距離;(x,y)為二維規劃平面上的一點;fp(x,y)為關于點(x,y)到山峰中心點坐標(xpi,ypi)的距離函數,表示發生碰撞的概率。假設某山峰中心點坐標是(15,15) km,λ=0.1。通過仿真,模擬得到的山峰威脅如圖1所示。

圖1　山峰威脅模擬Fig.1　Simulation of mountain peak

從圖1中可以看出,距離山峰中心點越近,受威脅概率越大。因為距離越近時,留給無人機通過改變航跡繞過山峰的時間將越短,無人機采取機動規避的難度將加大,發生碰撞的可能性增大。

2.2雷達威脅

隨著導彈技術的快速發展,防空導彈變得越來越先進,突破敵方防空區的難度增大,風險系數增高。現代戰爭中,發現即意味著摧毀,當無人機在執行任務時,如果被敵方的雷達探測到并跟蹤鎖定,摧毀的概率幾乎為1,所以在此只考慮被雷達探測到的威脅而不考慮防空火力的威脅,雷達威脅是航跡規劃中一個絕對不能忽視的因素[6]。雷達威脅與山峰威脅有相似之處,比如距離越近,被探測概率越大,對無人機威脅越大,在此,采用山峰威脅模型來近似模擬雷達威脅。采用這種模型可以簡化航跡規劃過程中威脅的表達,以便占用較少的時間和系統資源。雷達威脅概率模型為:

(2)

3約束條件

為保證規劃的航跡是可飛的,符合無人機的氣動特性和機動性能,需要考慮其自身的性能約束條件。無人機在巡航飛行過程中主要受最大航程、最小步長、最小轉彎半徑等條件約束[7]。

(1)最大航程

最大航程表示無人機總航跡不能超過一個特定的值,因為無人機所攜帶的燃料是有限的,飛行時間有限。從起始點到目標點的所有可行航跡都受最大航程的約束,在航跡規劃的尋優過程中,航跡是由很多個小段的航跡連接而成,假設第i段航跡長度為li,最大航程為Lmax,則必須滿足:

(3)

(2)最小步長

最小步長lmin是指無人機由于慣性作用,在改變飛行姿態前需要直飛的最短距離,即在單位時間內,以最小速度飛行的距離。必須滿足以下關系:

(4)

(3)最小轉彎半徑

最小轉彎半徑指無人機改變航向,在水平面內做圓周運動時,圓周的最小半徑。無人機由于受性能影響而不能轉彎過急,最小轉彎半徑受最大轉彎角φ限制,轉彎角越大,則轉彎半徑越小。轉彎半徑如圖2所示。

圖2　最小轉彎半徑Fig.2　Minimum turning radius

無人機做圓周運動時,向心力是由無人機傾斜時的側向力提供,根據文獻[8-9],最小轉彎半徑滿足如下關系式:

(5)

式中:v為無人機飛行速度;γmax為最大傾斜角。通過控制傾斜角,就可以使無人機滿足最小轉彎半徑的約束。

4算法思想

4.1算法描述

本文在A*算法的基礎上,提出了一種新的改進方法。其基本思想是:

(1)初始化參數,確定規劃區域,并對規劃區域的地形和雷達威脅進行建模,得到威脅概率模型;

(2)從當前位置出發,根據圓形節點擴展方法確定最佳擴展方向,選擇步長,得到最佳待擴展節點,作為下一個飛行位置,然后無人機從當前節點位置飛到規劃的下一位置;

(3)判斷此時的待擴展節點是否為目標點。如果不是目標點,則將此時的擴展節點作為當前節點,重復步驟(2)和(3);如果是目標點,則規劃結束,無人機到達目的地。

4.2節點擴展

傳統的A*算法采用柵格化的方法,將規劃區域劃分成無數小柵格,節點擴展主要限定在柵格線的交叉點上,如圖3所示。

圖3　柵格法節點擴展Fig.3　Grid node expansion

針對這種局限性,本文提出了一種可變方向和步長的節點擴展法,并將之命名為“圓形節點擴展法”。即以當前節點P為圓心,無人機的雷達探測距離r為半徑,得到一個圓,然后在圓弧上等距離地選取N個點,限定待擴展方向為在當前節點與這N個點的連線上。這樣從當前節點P出發,總共有N個待擴展的方向,然后,通過計算這N個點的代價值,選取其中代價值最小的那個點Pi(i=1，…，N),則PPi連線所在方向就是最佳擴展方向。通常由于無人機受體積和結構限制,所攜帶的雷達探測距離相對于地面敵方雷達的探測距離要小很多,所以如果Pi落在敵方雷達的探測范圍內時,其威脅代價值較高,當Pi代價值最小時,則PPi連線必定不在雷達探測區域內,其所在方向必為最佳擴展方向,PPi連線上所取的節點要優于其他方向的節點。

確定了擴展方向后,考慮到無人機的實際飛行速度和雷達探測距離,步長取0.1r～r之間,沿最佳擴展方向取設定步長,就可以得到下一個待擴展節點。以N=16為例,如圖4所示,假設第三個點P3代價值最小,則PP3為最佳擴展方向,再以0.2r為步長就得到下一個最佳擴展節點Pnext。

圖4　圓形節點擴展Fig.4　Circular node expansion

采用這種節點擴展方法,可以保證無人機搜索到的節點盡可能接近最優路徑。通過改變N的值,可以在多個方向上搜索,而不是像柵格化的方法只能在特定方向搜索。 圓弧上取的點越多,搜索的方向則越多,更易找到最優航路。但存在一個矛盾,取的點越多時,計算量增大,航跡規劃的速度降低。所以,需要調節步長,搜索步長越大時,總路徑的節點將越少,規劃量減少,有效降低規劃時間。但搜索步長過大時,又會降低航跡尋優能力,增加威脅性,所以,需要綜合考慮待擴展節點的數量和搜索步長的關系,使航跡盡可能接近最優。

4.3節點代價

在4.1節中已經提到,要確定最佳擴展方向,需要計算圓弧上各點的代價值。規劃的無人機航跡應使無人機在比較安全的區域飛行,保證其安全系數較高,受威脅較小,并且考慮到燃油消耗,應使航程盡可能短,所以,定義圓弧上節點Pi(i=1,2,…)的代價函數為:

(6)

5仿真分析

5.1規劃區域

設定規劃區域為30 km×30 km,起始位置為(0,0) km,目標位置為(30,30) km。假設無人機的雷達探測半徑r=1 km,雷達和山峰威脅的參數如表1所示。在Pentium 4(2.93 GHz),1.21 GB內存的PC機進行仿真實驗,運行環境為Windows XP,通過MATLAB仿真得到的規劃區域如圖5所示。

表1　威脅參數

圖5　規劃區域二維圖Fig.5　2D planning area

5.2步長對航跡的影響

為研究步長對航跡規劃的影響,分別取不同的步長進行仿真。設定權系數w1=1,w2=1×10-3,N=16,步長分別取0.1r,0.4r,0.7r和1.0r,得到在不同步長下無人機的規劃航跡如圖6所示。規劃時間、規劃步數、航程代價對比結果如表2所示。

圖6　不同步長下的航跡Fig.6　Flight path with different steps

步長/km規劃步數規劃時間/s總航程/km0.1r4572.638645.74310.4r1142.281145.99830.7r652.198346.05781.0r462.071646.5452

由圖6可知,不同步長下規劃的無人機航跡都能繞過威脅區域,安全到達目標點,并且不同步長下的航跡幾乎重合。可見,步長的選擇對無人機路徑的影響并不大,分析其原因主要是因為在節點擴展時,最佳擴展方向已經確定,并且所取的步長在雷達有效探測范圍之內,都是比較安全的。

由表2可知,步長越大,從起點到目標點總共需要規劃的步數則越少,規劃時間越短,但總的航程變大,代價更高。因為步長越短,規劃越精細,更接近于最優航跡。可見,采用小步長進行規劃時,航跡更優,但實時性有所降低;而采用大步長進行規劃時,實時性更好,但航程代價更高。

5.3方向對航跡的影響

為研究取不同N值時,即在不同方向搜尋擴展節點對航跡規劃的影響,分別取N=8,12,16,20。其中,N=8時,與柵格法的節點擴展方向相同。統一取步長為0.4r,w1=1,w2=1×10-3,得到不同方向節點擴展時無人機的規劃航跡如圖7所示。

由圖7可知,取不同的N值時,規劃的航跡都能繞過威脅區域,安全到達目標點。但N=8時,即與傳統A*算法節點擴展方向一致時,航跡是由很多段折線組成,不夠平滑,存在個別航向角變化較大的拐點,并且在末段時,航跡呈鋸齒狀,這樣的航跡不符合無人機實際飛行的要求。

圖7　不同方向下的航跡Fig.7　Planning path in different directions

規劃時間、規劃步數、航程代價對比結果如表3所示。由表中可以看出,N越大,總規劃步數越少,總航程越短,總代價越小,但規劃時間會越長。說明隨著N的增大,規劃出來的航跡會越來越精細,越來越接近最優值,但相應的處理速度會降低。并且,雖然航跡代價會隨著N增大而變小,但變化并不是很大,說明取不同的N時,都可以有效規避威脅,其主要受影響的是航程。通過結果的對比可以得出結論,當N取16或20時,可以獲得較優的航跡。

表3　不同擴展方向結果

6結束語

本文針對無人機巡航階段,采用新的方法進行了航跡規劃，提出了一種可變方向和變步長的節點擴展方法,突破了柵格化擴展節點特定方向、特定步長的約束。并通過取不同方向和步長擴展節點進行了仿真驗證,對所得到的不同航跡進行了對比,結果表明所采用的航跡規劃方法是可行的。

參考文獻：

[1]Vincent R,Mohammed T,Gilles L.Comparison of parellel genetic algorithm and particle swarm optimization for real-time UAV path planning[J].IEEE Transactions on Industrial Informatics,2013,9(1):132-141.

[2]白俊強,柳長安.基于蟻群算法的無人機航路規劃[J].飛行力學,2005,23(2):35-38.

[3]范林玉.航跡規劃遺傳模擬退火算法研究[D].重慶:重慶大學,2010.

[4]胡中華.基于智能優化算法的無人機航跡規劃若干關鍵技術研究[D].南京:南京航空航天大學,2011.

[5]占偉偉,王偉,陳能成,等.一種利用改進A*算法的無人機航跡規劃[J].武漢大學學報(信息科學版),2015,40(3):315-320.

[6]Karimi J,Pourtakdoust S H.A real-time algorithm for variable-objective motion planning over terrain and threats[J].Journal of Aerospace Engineering,2015,229(6):1043-1056.

[7]鄭昌文,嚴平,丁明躍,等.飛行器航跡規劃研究現狀與趨勢[J].宇航學報,2007,28(6):1442-1446.

[8]張洛兵,徐流沙,吳梅.基于改進人工蜂群算法的無人機實時航跡規劃[J].飛行力學,2015,33(1):38-42.

[9]常波,王瑞.基于幾何法的無人機航跡規劃[J]. 計算機系統應用,2015,24(1):109-113.

(編輯：方春玲)

UAV path planning based on improved A*algorithm

ZHANG Shuai1,2, LI Xue-ren1, ZHANG Peng1, LI Bo1

(1.Aeronautics and Astronautics Engineering College, Air Force Engineering University,Xi’an 710038, China;2.Key Laboratory of Science and Technology on Avionics Integration Technologies,Shanghai 200233,China)

Abstract:An improved UAV path planning method was put forward considering A*algorithm. Since gridding on planning area in traditional A* algorithm could only expand nodes in a specific direction with given step, this paper adopted circular nodes expanding method, which could realize expand nodes in alterable direction and step. This method was verified by a large number of simulations. The result shows that the improved path planning method can bypass the threat and reach the target safely.

Key words:UAV; path planning; nodes expansion

收稿日期:2015-06-23;

修訂日期:2015-12-08; 網絡出版時間:2016-01-10 14:09

基金項目:航空科學基金資助(20145596024)； 陜西省基礎研究項目(2014JQ8331)

作者簡介:張帥(1992-)，男，湖南湘潭人，碩士研究生，研究方向為無人機航跡規劃。

中圖分類號：V279

文獻標識碼：A

文章編號：1002-0853(2016)03-0039-05