一種陌生環(huán)境的無人機(jī)在線Laguerre航路規(guī)劃方法

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

(1.西北工業(yè)大學(xué) 航天學(xué)院, 陜西 西安 710072;2.空軍工程大學(xué) 航空航天工程學(xué)院, 陜西 西安 710038;3.西北工業(yè)大學(xué) 無人機(jī)特種技術(shù)國家重點(diǎn)實(shí)驗(yàn)室, 陜西 西安 710065)

一種陌生環(huán)境的無人機(jī)在線Laguerre航路規(guī)劃方法

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

(1.西北工業(yè)大學(xué) 航天學(xué)院, 陜西 西安 710072;2.空軍工程大學(xué) 航空航天工程學(xué)院, 陜西 西安 710038;3.西北工業(yè)大學(xué) 無人機(jī)特種技術(shù)國家重點(diǎn)實(shí)驗(yàn)室, 陜西 西安 710065)

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

多旋翼無人飛行器; 航路規(guī)劃; Laguerre圖; 城市環(huán)境

0 引言

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

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

1 城市環(huán)境航路規(guī)劃及Laguerre圖方法

1.1 陌生城市環(huán)境的航路規(guī)劃問題

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

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

1.2 基于Laguerre圖的航路規(guī)劃

根據(jù)文獻(xiàn)[6,10],Laguerre圖是對于一組圓的加權(quán)Voronoi圖。通常意義上的Voronoi圖考慮的是平面中一組點(diǎn)的集合。對于集合中的每一個(gè)點(diǎn),平面中到該點(diǎn)距離小于到其他點(diǎn)的距離的點(diǎn)構(gòu)成的多邊形區(qū)域即稱為Voronoi圖,這里的距離度量就是點(diǎn)到點(diǎn)的歐式距離。如果把點(diǎn)的集合換成圓的集合,把距離度量換成Laguerre距離,即點(diǎn)到圓的切點(diǎn)的距離,那么,所得到的圖形就被稱之為Laguerre圖。其數(shù)學(xué)定義闡述如下:

(1)

為了更方便地構(gòu)造Laguerre圖,文獻(xiàn)[7]建立了一種能夠有效降低計(jì)算規(guī)模的構(gòu)造算法,將Laguerre圖用于航路規(guī)劃,是考慮到Laguerre圖用圓替換了點(diǎn),更加接近于對威脅區(qū)的表達(dá),所以可以得到更好的安全航路。仿真研究也表明,基于Laguerre圖的航路規(guī)劃相較于Voronoi圖方法,對于航路安全有著突出優(yōu)勢。

2 基于Laguerre圖在線滾動(dòng)航路規(guī)劃方法

傳統(tǒng)的Laguerre圖航路規(guī)劃是在已知任務(wù)區(qū)域全局信息的情況下,首先構(gòu)建出任務(wù)區(qū)域的全局Laguerre圖,再通過對所有可能航路的代價(jià)評估,一次性得到全局規(guī)劃航路?？紤]到陌生城市環(huán)境的特點(diǎn),將全程航路分解為若干個(gè)航段,首先考察單個(gè)航段的最佳避撞安全航路,然后再完成全航程的航路規(guī)劃。

2.1 基于Laguerre圖的單航段航路規(guī)劃

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

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

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

(2)

(3)

結(jié)合GH=GQ可得:

(4)

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

LB×OE)+(PF2-OE2)

(5)

(6)

2(L-LA)×OE

(7)

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

=2LA×b-2L×OE

(8)

進(jìn)一步可導(dǎo)出C1C2與建筑物外邊界的距離為:

(9)

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

(10)

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

(11)

(12)

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

2.2 在線Laguerre航路規(guī)劃

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

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

3 仿真試驗(yàn)分析

以小型旋翼無人機(jī)在城市低空環(huán)境中運(yùn)送貨物為背景,使無人機(jī)模擬穿越建筑物密集的城市環(huán)境。按照某城市小區(qū)建筑物的實(shí)際分布情況,設(shè)計(jì)仿真試驗(yàn)的模擬飛行場景如圖3所示。

圖3 仿真試驗(yàn)?zāi)M飛行場景圖Fig.3 Simulated testing scenario in emulation test

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

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

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

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

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

4 結(jié)束語

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

[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] 魏瑞軒,李學(xué)仁.無人機(jī)系統(tǒng)與作戰(zhàn)運(yùn)用[M].北京:國防工業(yè)出版社, 2014.

[3] 董世友,龍國慶,祝小平.無人機(jī)航路規(guī)劃的研究[J].飛行力學(xué),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任務(wù)的改進(jìn)型Voronoi圖[J].國防科技大學(xué)學(xué)報(bào),2010,32(3): 121-126.

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

[7] 李春濤,易小芹,胡木.基于速度矢量場的無人機(jī)實(shí)時(shí)動(dòng)態(tài)航路規(guī)劃[J].南京航空航天大學(xué)學(xué)報(bào),2012,44(3):340-346.

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

[9] 魏瑞軒,許卓凡,王樹磊,等,基于Laguerre圖的自優(yōu)化A*無人飛行器航路規(guī)劃算法[J].系統(tǒng)工程與電子技術(shù),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] 張啟瑞,魏瑞軒,茹常劍,等.城市密集不規(guī)則障礙空間無人飛行器航路規(guī)劃[J].控制理論與應(yīng)用,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;

時(shí)間:2016-09-22 14:55

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

魏鉑淞(1995-)，男，陜西岐山人，本科生，研究方向?yàn)樘綔y制導(dǎo)與控制工程。

V279

A

1002-0853(2017)01-0057-04