文獻(xiàn)標(biāo)識碼: A
DOI:10.16157/j.issn.0258-7998.172483
中文引用格式: 葉春,張曦煌. 一種無人機(jī)三維航跡規(guī)劃算法研究[J].電子技術(shù)應(yīng)用,,2018,,44(3):84-88.
英文引用格式: Ye Chun,Zhang Xihuang. Research for an algorithm of UAV three-dimensional path planning[J]. Application of Electronic Technique,,2018,,44(3):84-88.
0 引言
隨著航空技術(shù)的發(fā)展,無人機(jī)在軍用與民用領(lǐng)域的應(yīng)用不斷擴(kuò)大,,如:敵情偵察,、地形勘探、地理測繪,、目標(biāo)轟炸,、高壓巡線等[1-2]。無人機(jī)執(zhí)行的任務(wù)復(fù)雜多樣,,為了提高其生存能力,,必須實現(xiàn)自主飛行。航跡規(guī)劃作為無人機(jī)自主飛行的關(guān)鍵技術(shù)之一,,一直是國內(nèi)外學(xué)者們研究的熱點,。
航跡規(guī)劃可以被看作是優(yōu)化一系列未知航點集的多約束組合問題,據(jù)現(xiàn)有的報道,,很多人工智能算法可有效解決該問題,。例如,XU C等[3]提出采用人工蜂群算法(Artificial bee colony algorithm,,簡稱ABC)去解決無人機(jī)航跡規(guī)劃問題,,并在偵察蜂搜索階段加入混沌算子,,取得了不錯的效果;SZCZERBA R J等[4]在A*算法中添加自適應(yīng)搜索策略,,有效去除了規(guī)劃空間中的無用航點,,提高了算法的搜索時間。然而,,上述方法只停留在二維航跡規(guī)劃層面上,,并未考慮規(guī)劃空間中的地形信息和無人機(jī)的拐彎角、俯沖角/爬升角以及最短航跡段長度等約束,。而三維航跡規(guī)劃更符合實際需求,,需對其開展研究。近年來,,張仁鵬等[5]在建立地形數(shù)字模型的基礎(chǔ)上,,采用改進(jìn)粒子群算法來模擬無人機(jī)三維航跡規(guī)劃,獲得了安全可飛的航跡,;ROBERGE V等[6]結(jié)合遺傳算法(Genetic Algorithm,,GA)與粒子群算法兩者的優(yōu)勢,采用混合算法解決了無人機(jī)三維航跡規(guī)劃問題,。然而,,上述算法隨著搜索空間維數(shù)的增加,穩(wěn)定性和收斂性會隨之下降,,也會陷入局部最優(yōu)值,。另外,這些研究也未涉及無人機(jī)如何應(yīng)對突發(fā)威脅帶來的影響,。
本文采用ABC算法來解決無人機(jī)的三維航跡規(guī)劃和針對突發(fā)威脅時的航跡重規(guī)劃問題,。同時,為了提供傳統(tǒng)ABC算法的收斂性,、魯棒性與穩(wěn)定性,,在雇傭蜂搜索時引入自適應(yīng)搜索算子、在跟隨蜂搜索時引入新型概率選擇方式及在偵察蜂搜索時引入混沌算子,,從而得到了一種改進(jìn)的ABC算法(Probability self-Adaptive Chaotic Artificial Bee Colony algorithm,,PAC-ABC)。然后,,對無人機(jī)的規(guī)劃空間,、地形信息和航跡代價模型進(jìn)行了建模,給出了相應(yīng)的數(shù)學(xué)描述,。最后,,通過三維航跡規(guī)劃與突發(fā)威脅航跡規(guī)劃模擬,驗證了本文所提算法的有效性。
1 航跡規(guī)劃建模
1.1 規(guī)劃空間與地形模型
在三維空間內(nèi),,無人機(jī)航跡規(guī)劃問題就是利用規(guī)劃算法找出一系列適合飛行且能滿足約束條件的飛行航點集[7],。在無人機(jī)實際應(yīng)用匯總,規(guī)劃空間中隱藏著各種威脅信息,,如地形,、雷達(dá)、高炮等,,有時這些威脅還具有不確定性,,因此想預(yù)先獲取飛行空間中的威脅信息具有很大的難度。另外,,無人機(jī)的續(xù)航時間很依賴油耗大小,。為了簡化航跡規(guī)劃過程,本文提出了以下幾個假設(shè)條件:(1)所有規(guī)劃空間內(nèi)的威脅物與地形信息均一致,;(2)無人機(jī)的油耗與航程成線性關(guān)系,;(3)無人機(jī)的飛行速度保持恒值不變;(4)忽略陣風(fēng)干擾,、機(jī)械動力學(xué)及機(jī)械振動等因素,。
用點(xα,yα,,zα)來表征規(guī)劃空間的某個航點,,其中xα為經(jīng)度值,yα為緯度值,,zα為海拔高度,,故航跡規(guī)劃的規(guī)劃空間可描述為[8]:
其中,(x,,y)表示山體坐標(biāo),(ak,,bk)為山體中心對稱軸坐標(biāo),,hk為山體的最高點。
1.2 航跡代價模型
航跡代價模型由威脅代價模型和油耗代價模型組成,。其中,,威脅代價主要考慮高炮威脅和雷達(dá)威脅[9]。
(1)雷達(dá)威脅,。通常雷達(dá)的探測范圍為圓形,,故設(shè)雷達(dá)對無人機(jī)的威脅概率為:
其中,d為雷達(dá)中心到無人機(jī)的距離,,dmax為雷達(dá)探測區(qū)域的最大半徑,。
(2)高炮威脅。和雷達(dá)威脅類似,高炮威脅的范圍也為圓形,,故設(shè)高炮對無人機(jī)的威脅概率為:
(3)油耗代價,。油耗與航程有關(guān),故認(rèn)為油耗代價就是總航程,。
另外,,還應(yīng)該考慮無人機(jī)航跡規(guī)劃過程中的其他約束條件:
(1)極限拐彎角。無人機(jī)通過控制其偏航角來控制航向的改變,。因為存在慣性,,飛行過程中要改變航向需要拐彎時間與拐外半徑。記航跡段li在水平面投影為mi=(xi-xi-1,,yi-yi-1),,設(shè)無人機(jī)允許的極限拐彎角為θt,則該約束可被描述成:
(2)極限俯沖角/爬升角,。無人機(jī)在高度方向(z方向)上俯沖與爬升的角度限制于其機(jī)動性,。因此,可設(shè)定極限大俯沖角/爬升角為θp的約束方程為:
(3)最小航跡段長度,。在飛行過程中,,當(dāng)前飛行姿態(tài)的改變需要無人機(jī)持續(xù)飛行一段距離,若無人機(jī)偏航角改變頻繁或者大幅度迂回飛行,,則會擴(kuò)大導(dǎo)航誤差,,故應(yīng)盡可能減小航跡長度。設(shè)定無人機(jī)的最小飛行航跡段長度為lmin,,則該約束的數(shù)學(xué)描述為:
綜上所述,,航跡代價模型主要由上述因素構(gòu)成,故無人機(jī)三維航跡代價模型可表示為:
式中,,J1~J5分別表征飛行過程中的威脅指標(biāo),、油耗指標(biāo)、極限拐彎指標(biāo),、極限俯沖角/爬升角指標(biāo)與最小航跡長度指標(biāo),,wk為相應(yīng)的權(quán)重系數(shù)。
2 改進(jìn)的人工蜂群算法
ABC算法是由土耳其KARABOGA D教授提出的一種模擬蜂群協(xié)作覓食行為的新興元啟發(fā)式優(yōu)化算法[10],。在算法中,,蜜蜂的種類可分為雇傭蜂、跟隨蜂和偵察蜂3種,。設(shè)蜂群種群總數(shù)為N,,雇傭蜂和跟隨蜂的數(shù)量各占種群總數(shù)的一半;每個蜜源均為一個D維向量,,其中D表示需要被優(yōu)化的解個數(shù),。在無人機(jī)航跡規(guī)劃問題,,種群中的每只蜜蜂對應(yīng)一組可行解,ABC算法通過3種蜂種的搜索方式尋找搜索空間的最優(yōu)解,。同時,,在算法中添加自適應(yīng)搜索策略、新型概率選擇策略與Logistic混沌搜索算子,。具體的步驟如下所示:
(1)種群初始化,。隨機(jī)派出N只蜜蜂尋找到xij(i=1,2,,…,,N;j=1,,2,,…,D)蜜源,,即可行解,。蜜源由式(9)產(chǎn)生:
(2)蜜源收益度計算。根據(jù)式(10)來計算每只蜜蜂初始時搜索到蜜源的收益度值,,并根據(jù)蜜源大小排序,,取前N/2組解。
其中,,Si是ABC算法中的目標(biāo)函數(shù)值,。
(3)雇傭蜂搜索階段。在此搜索階段,,蜜源信息會因為雇傭蜂的過度挖掘而致使算法迭代速率降低[11],,故本文采用一個自適應(yīng)搜索策略來改進(jìn)原搜索方式,即:
(4)跟隨蜂搜索階段,。隨著算法迭代次數(shù)的增加,,種群個體雖會朝著一個方向進(jìn)化,但同時也會遺漏其他有用信息,,從而導(dǎo)致種群多樣性的降低,。ABC算法性能的提高在某種程度上依賴于種群多樣性。研究發(fā)現(xiàn),,被摒棄的解也含有有用信息[12]。所以,,為了使含有較差信息的蜜源同樣能被充分挖掘,,本文采用一個新穎的概率選擇方式,來保證種群的多樣性:
(6)記錄當(dāng)前最優(yōu)解,。當(dāng)算法遇到終止條件時,,輸出迭代過程中的最優(yōu)解,。
3 仿真實驗
在本節(jié)中,通過一個三維航跡規(guī)劃仿真算例對本文所提PAC-ABC算法的有效性進(jìn)行驗證,。另外,,也引入傳統(tǒng)ABC算法與GA算法與之進(jìn)行比較分析。規(guī)劃空間采用100 km×100 km×100 km的三維空間,??臻g中共有5座山峰,疊加的地形信息參數(shù)為:
另外,,威脅物中的雷達(dá)和高炮的分布信息如表1所示,。
無人機(jī)飛行的起始點為(0,0,,0),,目標(biāo)點為(90,80,,0),,規(guī)劃的維數(shù)D=10。采用PAC-ABC算法,、ABC算法和GA算法同時去搜索最優(yōu)航跡,。前兩種算法的初始條件設(shè)置為:N=20,limit=15,。而設(shè)置GA算法的條件為:抗體種群數(shù)M=20,,交叉因子與變異因子分別為0.8與0.2。3種算法各運行10次,,每次迭代500次,,然后記錄下其中的最優(yōu)解。航跡規(guī)劃的結(jié)果如圖1所示,。從圖中可以看出,,3種算法均能生成可飛航跡,但是ABC算法與GA算法獲得航跡均要翻越山脊,,這會導(dǎo)致無人機(jī)被發(fā)現(xiàn)的概率增加,;而PAC-ABC算法獲得航跡則沿著山谷飛行,并較其他兩種算法縮短了航程,,利于規(guī)避威脅,,實現(xiàn)低空突防。
圖2給出了3種算法的迭代曲線,,從圖中可以看出本文所提算法的收斂速度最快,,在100代左右就能收斂到極值,且航跡代價為51.231 2,,而ABC算法和GA算法的航跡代價分別為54.998 0和60.621 4,。在改進(jìn)策略的作用下,,PAC-ABC算法能夠較好地避免局部最優(yōu)值,迅速地尋找到最優(yōu)解,。
為了進(jìn)一步驗證PAC-ABC算法的魯棒性,,分別取D為20和30時,評價此算法求解無人機(jī)航跡規(guī)劃問題的效果,,仿真結(jié)果如圖3所示,。從圖中可以看出,隨著維數(shù)的增加,,PAC-ABC算法依舊能夠?qū)ふ业捷^好的航跡,。這說明本文所提算法具有較好的魯棒性。
有時,,在規(guī)劃空間中隱藏著未被發(fā)現(xiàn)的突發(fā)威脅,。當(dāng)無人機(jī)遇到這些突發(fā)威脅時,需要算法具有重規(guī)劃能力,,來規(guī)避這些威脅,。設(shè)無人機(jī)從起始點(0,0,,0)到目標(biāo)點(90,,80,0)中,,在(40,,40,13)點處突然偵察到高炮,,如圖4(a)所示,。若不改變航跡繼續(xù)飛行,無人機(jī)則有幾率被擊落,,故需要對其航跡重新規(guī)劃,。如圖4(b)所示,通過PAC-ABC算法對航跡再次規(guī)劃,,可以有效避免突發(fā)威脅,,規(guī)劃時間僅為1.24 s。這說明本文所提航跡規(guī)劃算法迭代速率高,,具有一定的實時性,。
4 結(jié)論
在處理無人機(jī)三維航跡規(guī)劃問題時,本文提出了一種改進(jìn)人工蜂群算法,。在算法中,,通過自適應(yīng)搜索策略、新穎的概率選擇方式以及混沌搜索算子,,提高了算法的穩(wěn)定性,、搜索快速性與魯棒性。三維航跡規(guī)劃實驗表明:(1)與ABC算法與GA算法相比,,PAC-ABC算法能夠更快地獲得最優(yōu)航跡,,且航跡代價分別比前兩者少7.35%和18.33%;(2)隨著解維數(shù)的增加,,PAC-ABC算法依舊能夠獲得較好的解,,具有很強的魯棒性;(3)在處理突發(fā)威脅時,,PAC-ABC算法能夠在較短的時間內(nèi)實現(xiàn)局部航跡在規(guī)劃,,保證了無人機(jī)的安全飛行。綜上所述,,本文所提算法能夠為無人機(jī)規(guī)劃出一條可飛且較優(yōu)的飛行路徑,。
參考文獻(xiàn)
[1] CHEN Y,LUO G,,MEI Y,,et al.UAV path planning using artificial potential field method updated by optimal control theory[J].International Journal of Systems Science,2016,,47(6):1407-1420.
[2] GEVAERT C M,,PERSELLO C,SLIUZAS R,,et al.Informal settlement classification using point-cloud and image-based features from UAV data[J].ISPRS Journal of Photogrammetry and Remote Sensing,,2017,125(3):225-236.
[3] XU C,,DUAN H,,LIU F.Chaotic artificial bee colony approach to uninhabited combat air vehicle(UCAV) path planning[J].Aerospace Science and Technology,2010,,14(8):535-541.
[4] SZCZERBA R J,,GALKOWSKI P,GLICKTEIN I S,,et al.Robust algorithm for real-time route planning[J].Aerospace and Electronic Systems,,IEEE Transactions on,2000,,36(3):869-878.
[5] 張仁鵬,,楊金孝,潘佳華,,等.基于改進(jìn)粒子群算法的無人機(jī)三維航跡規(guī)劃[J].計算機(jī)仿真,,2014,31(3):66-69.
[6] ROBERGE V,,TARBOUCHI M,,LABONTE G.Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J].IEEE Transactions on Industrial Informatics,,2013,9(1):132-141.
[7] BESADA-PORTAS E,,DE LA TORRE L,,MORENO A,et al.On the performance comparison of multi-objective evolutionary UAV path planners[J].Information Sciences,,2013,,238(7):111-125.
[8] 胡中華.基于智能優(yōu)化算法的無人機(jī)航跡規(guī)劃若干關(guān)鍵技術(shù)研究[D].南京:南京航空航天大學(xué),2011.
[9] DUAN H,,ZHANG X,,WU J,et al.Max-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments[J].Journal of Bionic Engineering,,2009,,6(2):161-173.
[10] KARABOGA D,BASTURK B.On the performance of artificial bee colony(ABC) algorithm[J].Applied Soft Computing,,2008,,8(1):687-697.
[11] FOO J L,KNUTZON J,,KALIVARAPU V,,et al.Path planning of unmanned aerial vehicles using B-splines and particle swarm optimization[J].Journal of aerospace computing,Information,,and Communication,,2009,6(4):271-290.
[12] 林小軍,,葉東毅.云變異人工蜂群算法[J].計算機(jī)應(yīng)用,,2012,32(9):2538-2541.
[13] CHEN G,,WU X,,ZHU X,et al.Efficient string matching with wildcards and length constraints[J].Knowledge and Information Systems,,2006,,10(4):399-419.
作者信息:
葉 春1,張曦煌2
(1.江蘇信息職業(yè)技術(shù)學(xué)院 物聯(lián)網(wǎng)工程學(xué)院,,江蘇 無錫214001,;2.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫214001)