一種無人機實時航跡規劃策略研究

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

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

0 引言

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

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

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

1 滾動規劃搜索策略

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

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

(2)規劃區域:在滾動區域內部進行有限步數的航跡規劃所能到達的最大區域;

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

2 滾動規劃的時空約束

機載雷達等探測設備具有一定的探測范圍,對雷達探測數據的處理也需要消耗一定的時間,因此對于動態不確定環境,無法對探測范圍之外的區域進行航跡規劃。機載雷達的探測范圍決定了滾動規劃的搜索范圍,因此,滾動規劃應該滿足一定的空間和時間約束。

2.1 滾動規劃搜索的空間約束

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

(1)

搜索過程采取“邊規劃、邊執行”的策略。在沿規劃區域Si-1的航跡段Pi-1Pi飛行的同時,對當前規劃區域Si進行規劃,生成從Pi到Pi+1的飛行航跡;之后沿航跡段PiPi+1飛行,并在飛行的同時對下一規劃區域Si+1的航跡進行規劃。如此循環往復,直到無人機到達目標位置。此過程必須保證在飛行過程中,下一規劃區域處在機載雷達探測范圍內。

(2)

無人機在沿航跡段Pi-1Pi飛行過程中,保證下一規劃區域Si+1在當前滾動區域SL內的必要條件為:

L≥2R0(3)

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

N≤L/(2l0) (4)

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

2.2 滾動規劃搜索的時間約束

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

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

Ti=l0N/V0(5)

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

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

S=πL2-SACBD(6)

根據對稱性和相互間的幾何關系,可以得到:

(7)

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

(8)

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

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

Ti1=S/υ(9)

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

(10)

3 同步滾動機制分析

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

4 滾動規劃的搜索流程

本文采用A*算法在當前規劃區域進行航跡搜索,代價函數為:

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

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

在執行任務的過程中,如果作戰任務臨時改變,目標點由T變為T′,假設此時數據鏈暢通,無人機可以及時接收到任務改變的命令,則在下一滾動區域進行航跡規劃時,將規劃算法的目標點由T設置為T′,即可以保證滾動區域不斷收斂于新的目標T′。

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

5 仿真算例

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

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

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

由圖5仿真結果可知,滾動搜索策略能夠實時探測戰場態勢并進行航跡規劃,有效躲避多種威脅并順利到達目標點。

圖6為在執行任務過程中任務突然發生改變時的情形。從圖中可知,滾動搜索策略可以較好地應對任務突然發生變化的情況,向新的目標點規劃航跡直至到達新目標點。

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

6 結束語

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

參考文獻：

[1] 鄭昌文,嚴平,丁越明,等.飛行器航跡規劃研究現狀與趨勢[J].宇航學報,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圖和量子遺傳算法的飛行器航跡規劃方法[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] 劉希,朱凡,蔡滿意,等.一種改進的快速航路規劃方法[J].飛行力學,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] 王新增,慈林林,李俊山,等.基于改進粒子群優化算法的無人機實時航跡規劃[J].微電子學與計算機,2011,28(4):87-90.

[8] 何平川,戴樹齡.一種改進的UAV三維航跡實時規劃算法[J].北京航空航天大學學報,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] 李士波,孫秀霞,王棟,等.無人機動態環境實時航跡規劃[J].系統工程與電子技術,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.