李世曉, 朱凡, 張健, 劉杰, 隋曉奎

(1.空軍工程大學(xué) 航空航天工程學(xué)院, 陜西 西安 710038;2.哈爾濱飛行學(xué)院 理論訓(xùn)練系, 黑龍江 哈爾濱 150001)

0 引言

在空防技術(shù)日趨完善的現(xiàn)代戰(zhàn)爭中,無人機所處的戰(zhàn)場環(huán)境通常是動態(tài)的,執(zhí)行的任務(wù)具有不確定性,無法預(yù)先規(guī)劃滿足要求的航跡[1]。而現(xiàn)代戰(zhàn)爭要求無人機具有較高的自主性、智能性,其核心是無人機必須具備一定的在線實時航跡規(guī)劃能力。

航跡規(guī)劃可以分為參考航跡規(guī)劃、航跡重規(guī)劃以及動態(tài)航跡規(guī)劃。目前關(guān)于航跡規(guī)劃的研究多集中于離線航跡規(guī)劃。國內(nèi)外學(xué)者采用遺傳算法[2]、粒子群算法[3]、A*算法[4-5]、Voronoi圖法[3,6]等對無人機離線航跡規(guī)劃進行了研究,并取得了大量的成果。改進粒子群算法[7]和基于共享的小生境遺傳算法[8]在一定程度上增強了算法的實時性,但本質(zhì)上屬于航跡重規(guī)劃。文獻[9-10]提出一種分區(qū)段規(guī)劃的規(guī)劃方法可以實現(xiàn)航跡的實時規(guī)劃,但是沒有具體分析分段的原則和方法。

本文借鑒工業(yè)滾動時域控制(Receding Horizon Control, RHC)[11]的滾動優(yōu)化思想,將全局范圍內(nèi)的實時航跡規(guī)劃問題轉(zhuǎn)化為一系列彼此連接的局部區(qū)域航跡規(guī)劃子問題。提出了一種滾動規(guī)劃的搜索策略,定量分析了滾動規(guī)劃的空間和時間約束,提出了同步滾動的機制,設(shè)計了滾動搜索的搜索流程。最后對搜索策略的可行性進行了仿真,驗證了該方法的可行性和有效性。

1 滾動規(guī)劃搜索策略

滾動規(guī)劃搜索策略是將全局范圍內(nèi)的航跡規(guī)劃問題根據(jù)一定的要求劃分為一系列彼此連接的局部區(qū)域的航跡規(guī)劃子問題。滾動規(guī)劃采取“邊規(guī)劃、邊執(zhí)行”的策略,“執(zhí)行”是指無人機沿規(guī)劃的航跡段飛行。在局部區(qū)域內(nèi)利用A*算法進行航跡搜索,規(guī)劃一段航跡,無人機沿此航跡段飛行的同時規(guī)劃下一局部區(qū)域的航跡段,直至到達目標(biāo)點。這樣生成的航跡在全局范圍內(nèi)一般不是最優(yōu)的,但是可以滿足在線實時應(yīng)用的要求,并保證無人機最終到達目標(biāo)位置。滾動規(guī)劃搜索策略是局部區(qū)域的劃分和更新策略。這里先給出關(guān)于滾動規(guī)劃的兩個定義:

(1)滾動區(qū)域:劃分的彼此連接的局部搜索區(qū)域稱為滾動規(guī)劃搜索區(qū)域,簡稱滾動區(qū)域,與機載雷達的探測范圍直接相關(guān),又稱為探測區(qū)域。

(2)規(guī)劃區(qū)域:在滾動區(qū)域內(nèi)部進行有限步數(shù)的航跡規(guī)劃所能到達的最大區(qū)域;

根據(jù)規(guī)劃步數(shù)N和執(zhí)行步數(shù)M是否相同,滾動規(guī)劃分為同步滾動規(guī)劃(N=M)和異步滾動規(guī)劃(N≠M)。多步尋優(yōu)搜索算法[9]本質(zhì)上是一種多步規(guī)劃、一步執(zhí)行的滾動機制,屬于異步滾動規(guī)劃。這種機制每次執(zhí)行一步,無法對無人機執(zhí)行的航跡進行優(yōu)化,且表征航跡段的航跡點較多,存在頻繁轉(zhuǎn)彎的問題。同步滾動規(guī)劃的執(zhí)行步數(shù)與規(guī)劃步數(shù)相同,當(dāng)規(guī)劃步數(shù)N>1時,在航跡規(guī)劃后對局部區(qū)域的航跡段進行優(yōu)化,進而執(zhí)行優(yōu)化后的全部航跡段,即可以在一定程度上解決上述問題。故本文采用同步滾動規(guī)劃機制。

2 滾動規(guī)劃的時空約束

機載雷達等探測設(shè)備具有一定的探測范圍,對雷達探測數(shù)據(jù)的處理也需要消耗一定的時間,因此對于動態(tài)不確定環(huán)境,無法對探測范圍之外的區(qū)域進行航跡規(guī)劃。機載雷達的探測范圍決定了滾動規(guī)劃的搜索范圍,因此,滾動規(guī)劃應(yīng)該滿足一定的空間和時間約束。

2.1 滾動規(guī)劃搜索的空間約束

滾動規(guī)劃搜索的空間約束表現(xiàn)在滾動區(qū)域和規(guī)劃區(qū)域的相互關(guān)系上。定義機載雷達探測半徑為L,規(guī)劃步長為l0,每片滾動區(qū)域中當(dāng)前規(guī)劃區(qū)域的規(guī)劃步數(shù)和執(zhí)行步數(shù)均為N。圖1以N=3為例描述了滾動區(qū)域與規(guī)劃區(qū)域相互關(guān)系。定義當(dāng)前規(guī)劃區(qū)域的規(guī)劃起點為Pi,則Pi亦是前一規(guī)劃區(qū)域的規(guī)劃航跡的終點;當(dāng)前規(guī)劃區(qū)域的范圍是以Pi為圓心,以R0=l0×N為半徑的圓。從Pi點連續(xù)進行N步規(guī)劃得到的航跡段必然包含在規(guī)劃區(qū)域內(nèi)。

(1)

搜索過程采取“邊規(guī)劃、邊執(zhí)行”的策略。在沿規(guī)劃區(qū)域Si-1的航跡段Pi-1Pi飛行的同時,對當(dāng)前規(guī)劃區(qū)域Si進行規(guī)劃,生成從Pi到Pi+1的飛行航跡;之后沿航跡段PiPi+1飛行,并在飛行的同時對下一規(guī)劃區(qū)域Si+1的航跡進行規(guī)劃。如此循環(huán)往復(fù),直到無人機到達目標(biāo)位置。此過程必須保證在飛行過程中,下一規(guī)劃區(qū)域處在機載雷達探測范圍內(nèi)。

(2)

無人機在沿航跡段Pi-1Pi飛行過程中,保證下一規(guī)劃區(qū)域Si+1在當(dāng)前滾動區(qū)域SL內(nèi)的必要條件為:

L≥2R0(3)

將式(1)帶入式(3)得:

N≤L/(2l0) (4)

式(4)稱為滾動規(guī)劃搜索的空間約束。

2.2 滾動規(guī)劃搜索的時間約束

無人機實時航跡規(guī)劃是利用機載設(shè)備實時獲取戰(zhàn)場信息,通過高效的規(guī)劃算法規(guī)劃出可行航跡,“邊規(guī)劃、邊執(zhí)行”直至到達目標(biāo)點。從時間上看,滾動規(guī)劃搜索是一個連續(xù)的周期重復(fù)的過程。航跡段的執(zhí)行時間為循環(huán)周期,在一個周期中,滾動規(guī)劃搜索可以分為三個時間段:戰(zhàn)況信息處理時間、航跡規(guī)劃時間和冗余時間。

設(shè)Si-1的航跡段的執(zhí)行時間為Ti,無人機到達Pi-1點時,開始規(guī)劃Si內(nèi)的航跡段;戰(zhàn)況信息處理時間為Ti1,航跡規(guī)劃時間為Ti2,冗余時間為Tiε。假設(shè)無人機以速度V0作等速直飛跟蹤航跡,規(guī)劃區(qū)域Si-1內(nèi)航跡段長度為l0N,則航跡段執(zhí)行時間為:

Ti=l0N/V0(5)

戰(zhàn)況信息處理時間與需要處理的戰(zhàn)場信息區(qū)域大小相關(guān),而戰(zhàn)場信息區(qū)域大小與前一片規(guī)劃區(qū)域航跡段的形狀相關(guān),如圖2所示。圖中,Li和Ri分別表示當(dāng)前滾動區(qū)域和規(guī)劃區(qū)域邊界;Li-1和Ri-1分別表示上一片滾動區(qū)域和規(guī)劃區(qū)域的邊界;Pi-2Pi-1和Pi-1Pi為已經(jīng)規(guī)劃好的航跡。此時無人機剛好到達點Pi-1,沿航跡段Pi-1Pi飛行,PiPi+1為將要規(guī)劃的航跡段。圖2(a)中的網(wǎng)格陰影區(qū)域即為此段航跡規(guī)劃需要處理的戰(zhàn)況信息區(qū)域;圖2(b)給出了需要戰(zhàn)況信息處理的區(qū)域在面積最大時的情形。

從圖2可知,當(dāng)航跡段Pi-2Pi為直線時,戰(zhàn)況信息處理區(qū)域面積最大。圖3為處理區(qū)域最大面積計算示意圖,圖中,兩個滾動區(qū)域圓的半徑為雷達探測區(qū)域L,‖Pi-2Pi-1‖=R0。設(shè)網(wǎng)格區(qū)域面積為S,則有式(6)幾何關(guān)系成立:

S=πL2-SACBD(6)

根據(jù)對稱性和相互間的幾何關(guān)系,可以得到:

(7)

將式(7)帶入式(6)整理可得:

(8)

圖3 處理區(qū)域最大面積計算示意圖Fig.3 The calculation diagram of largest processing area

若信息處理的速率為υ,則處理信息所需的最大時間為:

Ti1=S/υ(9)

為了實現(xiàn)航跡段的有效銜接和保證飛行安全,滾動規(guī)劃搜索時需要滿足以下時間約束條件:

(10)

3 同步滾動機制分析

設(shè)每片規(guī)劃區(qū)域的規(guī)劃步數(shù)和執(zhí)行步數(shù)為N。根據(jù)N是否為1,同步滾動機制又可以分為單步規(guī)劃單步執(zhí)行(N=1)和多步規(guī)劃多步執(zhí)行(N>1)。單步規(guī)劃單步執(zhí)行滾動機制簡單,但每次只進行一步航跡搜索,對當(dāng)前節(jié)點的后繼搜索范圍以外的環(huán)境信息沒有加以考慮,生成的節(jié)點只是一步優(yōu)化的結(jié)果,并且沒有機會進行航跡段的局部優(yōu)化。多步規(guī)劃多步執(zhí)行的滾動機制每次進行多步搜索優(yōu)化,利用更多的環(huán)境信息,尋找一定范圍內(nèi)的最優(yōu)航跡節(jié)點,并且可以進行局部航跡優(yōu)化,得到更優(yōu)的航跡。同時N越大,每次規(guī)劃時需的內(nèi)存也越大,規(guī)劃時間越長,且N的選取需滿足滾動規(guī)劃的空間約束和時間約束。

4 滾動規(guī)劃的搜索流程

本文采用A*算法在當(dāng)前規(guī)劃區(qū)域進行航跡搜索,代價函數(shù)為:

f(n)=g(n)+h(n) (11)

式中,g(n)為從起始點到節(jié)點n已經(jīng)付出的代價;h(n)為節(jié)點n到目標(biāo)節(jié)點的代價估計值,稱為啟發(fā)函數(shù)。g(n)取初始點到節(jié)點n實際付出的威脅代價和航程代價的加權(quán);h(n)取節(jié)點n到目標(biāo)節(jié)點的歐氏距離。算法的搜索起點為上一規(guī)劃區(qū)域的航跡段的終點,搜索終點不固定。A*算法主要解決起點和終點都固定的全局航跡規(guī)劃問題,這里采用限定算法擴展層數(shù)的策略,解決終點不固定的問題。在當(dāng)前規(guī)劃區(qū)域,首先根據(jù)機載雷達探測到的動態(tài)戰(zhàn)況信息進行動態(tài)戰(zhàn)況信息更新;然后將上一規(guī)劃區(qū)域的航跡段終點作為此次規(guī)劃的起點,將全局的目標(biāo)點作為規(guī)劃的終點;根據(jù)選取的規(guī)劃步數(shù)N,進行N層節(jié)點擴展,將搜索得到的最優(yōu)的N個航跡節(jié)點和起點順次連接便得到當(dāng)前規(guī)劃區(qū)域內(nèi)的航跡段。如此反復(fù),直至到達目標(biāo)點。滾動搜索流程如圖4所示,圖中,i為滾動區(qū)域和規(guī)劃區(qū)域的標(biāo)號。

在執(zhí)行任務(wù)的過程中,如果作戰(zhàn)任務(wù)臨時改變,目標(biāo)點由T變?yōu)門′,假設(shè)此時數(shù)據(jù)鏈暢通,無人機可以及時接收到任務(wù)改變的命令,則在下一滾動區(qū)域進行航跡規(guī)劃時,將規(guī)劃算法的目標(biāo)點由T設(shè)置為T′,即可以保證滾動區(qū)域不斷收斂于新的目標(biāo)T′。

圖4 滾動規(guī)劃的搜索流程圖Fig.4 Flow chart of the rolling planning

5 仿真算例

仿真計算機使用Intel(R) Core(TM) i3處理器,主頻為2.93 GHz,內(nèi)存為2 GB;規(guī)劃策略和算法采用Microsoft Visual C++6.0編程技術(shù)實現(xiàn);使用范圍為E117°～E118°,N23°～N24°的真實數(shù)字地圖和模擬生成的威脅信息;起始點為(E117.14°, N23.18°),目標(biāo)點為(E117.85°, N23.83°);最小轉(zhuǎn)彎半徑為1 000 m,信息處理速度15 km2/s,規(guī)劃步長1 800 m,防空威脅作用范圍8～10 km,機載設(shè)備探測距離18 km,無人機飛行速度150 m/s。

設(shè)無人機在未知的威脅環(huán)境下執(zhí)行飛行任務(wù),當(dāng)無人機與威脅中心的距離小于機載設(shè)備探測距離時,威脅才被處理,進而在以后的航跡搜索時加以規(guī)避。根據(jù)式(4)計算得到規(guī)劃步數(shù)N≤5,為兼顧航跡的優(yōu)化程度和計算效率,本文選取N=3。由式(5)和式(9)得執(zhí)行時間Ti=12.00 s,最大信息處理時間Ti1=4.12 s,每片航跡規(guī)劃區(qū)域內(nèi)航跡搜索時間不超過Ti2max=Ti-Ti1=7.88 s,即可以滿足式(10)所示的時間約束。仿真時設(shè)定每片規(guī)劃區(qū)域航跡規(guī)劃的時間限制為Ti2max。規(guī)劃時間不超過Ti2max時仿真轉(zhuǎn)入下一片規(guī)劃區(qū)域進行規(guī)劃,否則停止規(guī)劃。由于實時航跡規(guī)劃是一個動態(tài)過程,本文采用圖5所示的仿真截圖展示實時規(guī)劃的動態(tài)過程。

圖5 實時規(guī)劃仿真截圖Fig.5 Real-time path planning simulation diagram

由圖5仿真結(jié)果可知,滾動搜索策略能夠?qū)崟r探測戰(zhàn)場態(tài)勢并進行航跡規(guī)劃,有效躲避多種威脅并順利到達目標(biāo)點。

圖6為在執(zhí)行任務(wù)過程中任務(wù)突然發(fā)生改變時的情形。從圖中可知,滾動搜索策略可以較好地應(yīng)對任務(wù)突然發(fā)生變化的情況,向新的目標(biāo)點規(guī)劃航跡直至到達新目標(biāo)點。

圖6 任務(wù)突然變化時的情形Fig.6 The sudden change situation of planning task

6 結(jié)束語

本文提出了一種滾動規(guī)劃的搜索策略,采用“邊規(guī)劃、邊執(zhí)行”的策略和同步滾動機制實現(xiàn)了全局范圍的實時航跡規(guī)劃。仿真結(jié)果表明,該策略可行有效,可以通過實時探測戰(zhàn)場態(tài)勢分區(qū)域滾動規(guī)劃,有效地規(guī)避各種威脅,較好地應(yīng)對任務(wù)突變的情形。進一步提升無人機的自主性和智能性,有較高的研究價值。

參考文獻：

[1] 鄭昌文,嚴平,丁越明,等.飛行器航跡規(guī)劃研究現(xiàn)狀與趨勢[J].宇航學(xué)報,2007,28(6):1141-1146.

[2] Eun Y,Bang H.Cooperative task assignment/path planning of multiple unmanned aerial vehicles using genetic algorithms[J].Journal of Aircraft,2009,46(1):338-343.

[3] 何兵,劉剛,閆建諍,等.基于Voronoi圖和量子遺傳算法的飛行器航跡規(guī)劃方法[J].電光與控制,2013,20(1):5-8.

[4] Rapajic P B,Vucetic B S.Adaptive receiver structures for asynchronous CDMA systems[J].IEEE J Sel Areas Commun,1994,12(5):685-697.

[5] 劉希,朱凡,蔡滿意,等.一種改進的快速航路規(guī)劃方法[J].飛行力學(xué),2011,29(1):89-92.

[6] McLain T W,Beard R W.Trajectory planning for coordinated rendezvous of unmanned air vehicles[R].AIAA-2000-4369,2000.

[7] 王新增,慈林林,李俊山,等.基于改進粒子群優(yōu)化算法的無人機實時航跡規(guī)劃[J].微電子學(xué)與計算機,2011,28(4):87-90.

[8] 何平川,戴樹齡.一種改進的UAV三維航跡實時規(guī)劃算法[J].北京航空航天大學(xué)學(xué)報,2010,36(10):1249-1251.

[9] Weiss B,Naderhim M,del Re L.Global real-time path planning for UAVs in uncertain environment[C]//IEEE International Symposium on Intelligent Control.Munich,Germany: IEEE,2006:2725-2730.

[10] 李士波,孫秀霞,王棟,等.無人機動態(tài)環(huán)境實時航跡規(guī)劃[J].系統(tǒng)工程與電子技術(shù),2007,29(3):399-401.

[11] Kirk Wesselowski.Receding horizon methods in cooperative control for stochastic transportation application on graphs [D].Boston:PhD Dissertation of Boston University,2007.