一種陌生環境的無人機在線Laguerre航路規劃方法

魏鉑淞, 張啟瑞, 許卓凡, 王亮

(1.西北工業大學 航天學院, 陜西 西安 710072;2.空軍工程大學 航空航天工程學院, 陜西 西安 710038;3.西北工業大學 無人機特種技術國家重點實驗室, 陜西 西安 710065)

一種陌生環境的無人機在線Laguerre航路規劃方法

魏鉑淞1, 張啟瑞2, 許卓凡2, 王亮3

(1.西北工業大學 航天學院, 陜西 西安 710072;2.空軍工程大學 航空航天工程學院, 陜西 西安 710038;3.西北工業大學 無人機特種技術國家重點實驗室, 陜西 西安 710065)

針對多旋翼無人機在陌生城市低空安全飛行的需要,研究了適合于陌生環境應用的在線航路規劃方法。在分析傳統Laguerre圖航路規劃原理及其航路安全性優勢的基礎上,首先導出了面向單個擬飛通道的Laguerre規劃航路的特性。進而,通過最小化航路安全誤差,建立了單個航段的最佳安全航路。在上述研究的基礎上,提出了面向陌生環境的在線滾動式Laguerre航路規劃方法。設計了模擬城市建筑物分布的仿真飛行場景,并通過對比分析不同規劃方法對于仿真場景的航路規劃結果,顯示了本文算法在航路規劃問題中避撞安全性方面的優勢。

多旋翼無人飛行器; 航路規劃; Laguerre圖; 城市環境

0 引言

近年來,由于操控方便、價格低廉、用途廣泛等原因,小型商業多旋翼無人機發展迅速,正在受到越來越多的重視和喜愛。在技術和市場的共同推動下,未來城市商業無人機的發展和運用空間極為廣闊。據有關機構預測,未來十年商業無人機的市場產值可能達到千億美元。但無人機發展和運用的一路高歌猛進,也正在給無人機在城市的低空飛行安全帶來巨大的挑戰,無人機撞擊建筑物的事件時有發生。最近兩年連續發生過無人機撞擊建筑物而墜毀的事件[1]。如何保證無人機在城市低空飛行的安全,已成為一個亟待研究和解決的問題。

航路規劃是保證無人機飛行安全的重要技術[2-3]。傳統的航路規劃方法包括基于遍歷搜索原理的A*類航路規劃方法[4]、基于Voronoi圖的方法[5]、基于Laguerre圖的方法[6]、基于速度場等的航路規劃方法[7-8]。大多數傳統航路規劃方法是預先完成型方法,需要事先知道飛行區域的環境信息。這種要求難以適用于陌生的城市環境。為此,本文將對面向陌生城市環境的基于Laguerre圖的在線安全航路規劃方法進行研究。

1 城市環境航路規劃及Laguerre圖方法

1.1 陌生城市環境的航路規劃問題

低空城市環境中的航路規劃有其特殊性,首先應考慮安全問題。文獻[9]將城市建筑物看作各種不規則的威脅區,首次將基于Laguerre圖的規劃方法擴展到對于非圓形不規則威脅區的航路規劃,建立了基于Laguerre圖的自優化A*航路規劃算法。但這一方法需要為所有的非圓形威脅區建立外接圓,需要提前預知所有的建筑物及其分布,且規劃必須提前完成。對于障礙物分布密集的情形,其執行效率也會降低。該方法的這些運行需求,對于無法提前掌握詳細環境信息的陌生任務區域來說,是難以適應的。

求解陌生城市環境中的航路規劃問題,是要在預先缺少任務區域詳細地理和環境信息的情況下,為無人機確定出可飛的安全航路。這一要求極大地限制了各種需要預先完成的規劃方法的運用?？紤]到無人機可以利用自身攜帶的CCD相機等光電探測設備和圖像處理系統實時感知前方的環境,因此,如果能在此基礎上實現實時航路規劃,就可以較好地解決這一難題。為此,本文將建立一種基于Laguerre圖的在線安全航路規劃方法。

1.2 基于Laguerre圖的航路規劃

根據文獻[6,10],Laguerre圖是對于一組圓的加權Voronoi圖。通常意義上的Voronoi圖考慮的是平面中一組點的集合。對于集合中的每一個點,平面中到該點距離小于到其他點的距離的點構成的多邊形區域即稱為Voronoi圖,這里的距離度量就是點到點的歐式距離。如果把點的集合換成圓的集合,把距離度量換成Laguerre距離,即點到圓的切點的距離,那么,所得到的圖形就被稱之為Laguerre圖。其數學定義闡述如下:

(1)

為了更方便地構造Laguerre圖,文獻[7]建立了一種能夠有效降低計算規模的構造算法,將Laguerre圖用于航路規劃,是考慮到Laguerre圖用圓替換了點,更加接近于對威脅區的表達,所以可以得到更好的安全航路。仿真研究也表明,基于Laguerre圖的航路規劃相較于Voronoi圖方法,對于航路安全有著突出優勢。

2 基于Laguerre圖在線滾動航路規劃方法

傳統的Laguerre圖航路規劃是在已知任務區域全局信息的情況下,首先構建出任務區域的全局Laguerre圖,再通過對所有可能航路的代價評估,一次性得到全局規劃航路?？紤]到陌生城市環境的特點,將全程航路分解為若干個航段,首先考察單個航段的最佳避撞安全航路,然后再完成全航程的航路規劃。

2.1 基于Laguerre圖的單航段航路規劃

設建筑物A和建筑物B的陰影矩形如圖1所示。其邊界A1A2與邊界B1B2之間的通道為擬飛通道。為簡化分析,假設兩個建筑物具有等長的邊,即A1A2=B1B2=2a。將每個擬飛通道設定為一個獨立航段。為完成基于Laguerre圖的航路規劃,分別以A1A2和B1B2為弦做外接圓,圓心分別位于各自垂直平分線上的P點和O點,兩個外接圓的半徑分別為rA和rB。記邊界A1A2與B1B2的中點分別為F和E點,圓心距OP=b。

圖1 單個擬飛通道的Laguerre航路分析圖Fig.1 Diagram for analysis of Laguerre route of an aisle

按照Laguerre圖定義,由圓O和圓P生成的Laguerre邊是位于兩個外接圓之間的直線,記為C1C2,設其與建筑物A的邊界的垂直距離為LA,則直線C1C2就是對應這兩個外接圓的Laguerre航路。為進一步分析該航路的安全特性,取C1C2上的任意一點G,從該點向兩個圓分別作切線,切點為Q和H。則由Laguerre邊的定義可知GH=GQ。在圖1中,存在兩組直角三角形關系,從而可得兩組幾何方程:

(2)

(3)

結合GH=GQ可得:

(4)

同時,由圖中幾何關系可知PG=PF+LA,OG=OE+LB,且L=LA+LB。將這些等式關系帶入式(4),可以進一步導出:

LB×OE)+(PF2-OE2)

(5)

(6)

2(L-LA)×OE

(7)

L2=2LA(PF+OE+L)-2L×OE

=2LA×b-2L×OE

(8)

進一步可導出C1C2與建筑物外邊界的距離為:

(9)

根據式(9),對位于兩個建筑物之間的單個航段,基于Laguerre圖得到的規劃航路是沿著該通道縱向、與建筑物A的外邊界距離為LA=(L2+2L×OE)/2b的直線。定義該航路與兩側建筑物外邊界的距離的平方和為避撞安全誤差ES,即:

(10)

對應于最安全的防碰撞航路,必然使下式成立:

(11)

(12)

由此得出結論,根據Laguerre圖的航路規劃原理,位于兩個建筑物之間的單個擬飛通道的最佳防碰撞安全航路位于該通道的中位航路上。依據該結論,可以很方便地為每個航段獲得最安全的Laguerre規劃航路。

2.2 在線Laguerre航路規劃

基于上述分析和結論,對在城市環境中飛行的小型旋翼無人機,可以通過單航段的滾動Laguerre規劃實現全程實時航路規劃。首先,無人機可利用機載圖像處理系統實時感知當前擬飛通道的邊界信息。依據這些信息建立通道的Laguerre航路,并以中位航路作為安全飛行航路，將航路指令注入飛行控制計算機,控制無人機按照該航路完成本航段飛行。當該航段完成后,再按上述流程滾動進行下一航段的規劃和飛行,直至完成最后一個航段。這樣,通過對每一個航段均滾動執行相同的規劃算法,即可使無人機在線完成基于Laguerre圖的全程安全航路規劃。該方法運行流程如圖2所示。

圖2 在線Laguerre航路規劃方法流程圖Fig.2 Flowchart of the online Laguerre route planning method

3 仿真試驗分析

以小型旋翼無人機在城市低空環境中運送貨物為背景,使無人機模擬穿越建筑物密集的城市環境。按照某城市小區建筑物的實際分布情況,設計仿真試驗的模擬飛行場景如圖3所示。

圖3 仿真試驗模擬飛行場景圖Fig.3 Simulated testing scenario in emulation test

分別使用3種不同方法為無人機完成從起點STA到終點END的航路規劃。3種方法得到的規劃航路如圖4所示。其中,方法1為文獻[9]提出的基于Laguerre圖的自優化A*航路規劃算法(LA-STAR);方法2為文獻[11]提出的基于局部回溯與廣度優先思想相結合的綜合航路規劃方法(LBT);方法3為本文建立的在線Laguerre安全航路規劃方法(LRP)。需要說明的是,在LA-STAR方法中,需要為擬飛區域中的每個建筑物都建立一定的外接圓,然后才能進行基于Laguerre圖的航路規劃。而LBT方法在運用時同樣需要提前知道擬飛區域的建筑物分布信息。另外,本文航路規劃算法得到的是初始航路,在轉彎處通常是折線。為了適應實際的飛行,需要對這些折線進行平滑處理,圖中在折線處顯示的小內切圓,就是用于平滑處理的。

圖4 3種方法規劃出的航路Fig.4 Routes planned with three methods

為進一步考察仿真試驗得到的規劃航路的防碰撞安全性,根據式(10)定義的航路避撞安全誤差,3種方法得到的航路避撞安全誤差曲線如圖5所示。

圖5 仿真規劃航路的避撞安全誤差曲線Fig.5 Curves of route collision avoidance safe errors

為保證不同航路上對比航點選擇的一致性,沿飛行方向任意選取了N個參考點P1到PN,按照這些參考點在每個航路上對應選擇N個航點,其中Pk表示1～N的任意位置?？疾烀總€航點處的避撞安全誤差值。在這里,主要考察的并不是每條航路對應的誤差值的大小,因為每條航路所經歷的通道不一樣,通道寬度也不同,所以無法按統一標準來比較誤差的大小。針對航路防碰撞的特點,主要考察誤差曲線在通道內的起伏情況。從3條航路對應的避撞安全誤差曲線可以看出,本文方法規劃出的航路防撞誤差曲線在飛行通道內起伏平穩,顯示了本文方法所得到的航路對于防碰撞具有更大的優勢。

4 結束語

本文以陌生城市的低空飛行任務為背景,在已有研究的基礎上,探索了將Laguerre圖方法應用于陌生城市環境的實時在線規劃方法。盡管仿真試驗結果表明本文方法在實時航路安全方面取得了較好的效果,但還需進行更加深入的研究，特別是目前的研究只是考慮了較簡單的建筑物位置關系。在現代化大城市中,各種高層建筑物不僅形狀多樣,而且位置關系復雜。對于在這些復雜情況下的方法研究和實踐,將是今后研究的一個重點。

[1] Liam Stack.New Jersey man is arrested after drone hits Empire State building[EB/OL].(2016.02.05)[2016.5].http://www.nytimes.com/2016/02/05/nyregion/new-jersey-man-is-arrested-after-drone-hits-empire-state-building.html.

[2] 魏瑞軒,李學仁.無人機系統與作戰運用[M].北京:國防工業出版社, 2014.

[3] 董世友,龍國慶,祝小平.無人機航路規劃的研究[J].飛行力學,2004 22(3):21-24.

[4] Yao J F,Lin C,Xie X B,et al.Path planning for virtual human motion using improved A*star algorithm[C]//Proc. of the 7th International Conference on Information Technology:New Generations.Las Vegas,NV:IEEE,2010:1154-1158.

[5] 張雷,王道波,段海濱,等.一種用于SEAD任務的改進型Voronoi圖[J].國防科技大學學報,2010,32(3): 121-126.

[6] 王樹磊,魏瑞軒,沈東,等.面向航路規劃的Laguerre圖構造算法[J].系統工程與電子技術,2013,35(3):552-556.

[7] 李春濤,易小芹,胡木.基于速度矢量場的無人機實時動態航路規劃[J].南京航空航天大學學報,2012,44(3):340-346.

[8] 肖秦琨,高曉光.一種無人機局部航路重規劃算法研究[J].飛行力學,2006,24(1):85-88.

[9] 魏瑞軒,許卓凡,王樹磊,等,基于Laguerre圖的自優化A*無人飛行器航路規劃算法[J].系統工程與電子技術,2015,37(3):577-582.

[10] Marina Gavrilova,Jon Rokne.On sweep-plane analysis of Laguerre Verona diagram[C]//Proc.of the 4th International Symposium on Voronoi Diagram in Science and Engineering (ISVD 2007).Washington,DC,USA:IEEE,2007:260-264.

[11] 張啟瑞,魏瑞軒,茹常劍,等.城市密集不規則障礙空間無人飛行器航路規劃[J].控制理論與應用,2015,32(10):1407-1413.

(編輯：方春玲)

A method of online Laguerre route planning for UAVs flying in an unknown regions

WEI Bo-song1, ZHANG Qi-rui2, XU Zhuo-fan2, WANG Liang3

(1.School of Astronautics, NWPU, Xi’an 710072, China;2.Aeronautics and Astronautics Engineering College, AFEU, Xi’an 710038, China;3.National Key Laboratory of Special Technology on UAV, NWPU, Xi’an 710065, China)

Aiming at the safe flying requirement for multi-rotor UAV in urban lower aerial regions, a method of online route planning for unknown urban areas are studied in this paper. By demonstrating the route planning principle of the traditional Laguerre diagram method and advantages on route safety, the characteristic of Laguerre route planning for an independent flight aisle is firstly studied. And then by minimizing the route’s collision avoidance safe error, the safest route is built for a single flying-phrase channel. Based on above researches, an online rolling Laguerre method for route planning is presented for unknown urban lower flying areas. A simulation flight testing scenario is designed by referring a real buildings distribution on an urban community. By comparing the route planning results of various planning methods for the same simulation flight scenes, the advantages on route collision avoidance and online route planning have been shown for the method mentioned in this paper.

multi-rotor UAV; route planning; Laguerre diagram; urban area

2016-03-22;

2016-09-05;

時間:2016-09-22 14:55

國家自然科學基金資助(61573373)

魏鉑淞(1995-)，男，陜西岐山人，本科生，研究方向為探測制導與控制工程。

V279

A

1002-0853(2017)01-0057-04