袁夢婷, 時宏偉
(四川大學(xué) 計算機(jī)學(xué)院, 四川 成都 610065)
隨著近年無人機(jī)的迅猛發(fā)展,對無人機(jī)監(jiān)視指揮和安全保障的需求也愈加強(qiáng)烈和緊迫。為了避免無人機(jī)與有人機(jī)的沖突,業(yè)界一直采用劃分隔離空域的方法;而對于無人機(jī)與其他障礙物之間的沖突與碰撞,小、微型民用無人機(jī)仍主要采用視距內(nèi)飛行的方式[1]。但在國家空域資源有限背景下,伴隨無人機(jī)技術(shù)的愈發(fā)進(jìn)步,混合共享空域與低空開放必將成為發(fā)展趨勢。當(dāng)無人機(jī)所處空域環(huán)境愈發(fā)復(fù)雜,碰撞規(guī)避問題將成為嚴(yán)峻的挑戰(zhàn)。因此,無人機(jī)感知與規(guī)避(sense and avoid,S&A)系統(tǒng)的研究與落地,將助力無人機(jī)突破隔離空域限制,推動無人機(jī)更為廣泛的實際應(yīng)用。
近年來,國際民航組織大力推動廣播式自動相關(guān)監(jiān)視(automatic dependent surveillance-broadcast,ADS-B)技術(shù)的應(yīng)用,將其作為全球航空運輸系統(tǒng)中新一代監(jiān)視技術(shù)的主要方向。美國、歐洲、中國也都在逐步完成ADS-B的相關(guān)落地計劃,未來將實現(xiàn)ADS-B技術(shù)更廣泛的應(yīng)用。而將ADS-B技術(shù)應(yīng)用在無人機(jī)上或也將成為發(fā)展的趨勢。
目前,國內(nèi)外學(xué)者圍繞飛行器的避撞問題展開了大量卓有成效的研究,為無人機(jī)S&A系統(tǒng)的研究提供了極有價值的參考。
在沖突的探測上,主要有幾何法和概率法兩類方法。幾何法多通過劃分安全區(qū),并基于當(dāng)前飛行狀態(tài)對未來航跡進(jìn)行線性預(yù)測,判定安全區(qū)是否存在重疊,而民航飛機(jī)所用的空中防撞系統(tǒng)(traffic collision avoidance system,TCAS)就是采用幾何法[2]。概率法則考慮了如風(fēng)擾動、導(dǎo)航誤差等隨機(jī)因素,能計算出沖突發(fā)生的可能性,更精確但也更復(fù)雜。但在實際應(yīng)用中,降低并消除碰撞風(fēng)險才是空中安全技術(shù)的關(guān)鍵[2]。并且,考慮到ADS-B技術(shù)能提供精確全面的實時飛行狀態(tài)和意圖信息,且具有較高更新率,本文采用基于幾何法的確定型沖突探測模型。
在沖突的解脫上,較多采用的方法是航路規(guī)劃,包括人工勢場法、以遺傳算法為代表的啟發(fā)式算法、A*算法等[1-3]。不同算法各有優(yōu)缺點,因此也有學(xué)者將算法進(jìn)行融合。但航路規(guī)劃多是基于幾何學(xué)進(jìn)行搜索,不考慮飛行器動力學(xué)約束,且搜索效率取決于規(guī)劃空間大小[4]。而不少學(xué)者對算法的改進(jìn)集中在算法本身的缺陷和求解速度上,優(yōu)質(zhì)航路的判定僅參考延誤距離這一條標(biāo)準(zhǔn)。對此,本文提出引入綜合啟發(fā)函數(shù)的蟻群解脫模型,從航路的平滑度和延誤兩方面進(jìn)行了考慮。
無人機(jī)的沖突規(guī)避不同于有人機(jī)。一方面,無人機(jī)缺少飛行員執(zhí)行“看見-規(guī)避”;另一方面,民航飛機(jī)可以采用空中交通管制(air traffic control,ATC)服務(wù)、TCAS的避撞建議,而滿足飛行高度門檻的無人機(jī)卻大多囿于性能難以達(dá)到TCAS運行要求。因此,無人機(jī)需要特定的S&A系統(tǒng),代替飛行員“看見-規(guī)避”以克服潛在威脅,包括其他飛行器(如飛機(jī)、滑翔傘等)以及有碰撞危險的物體(如建筑物等)。
為了保障飛行安全,S&A系統(tǒng)需要滿足2層功能需求:首先,該系統(tǒng)需通過確保飛行器之間保持適當(dāng)?shù)木嚯x來降低碰撞的可能性,以避免更危險的狀態(tài),此為自主間隔保持;其次,當(dāng)自主間隔保持操作也無法改變兩者相撞的趨勢,飛行器處于更危險的狀態(tài),就需要在即將產(chǎn)生實際碰撞時,進(jìn)行碰撞規(guī)避。自主間隔保持與碰撞規(guī)避原理相似,不過前者的機(jī)動開始得更早,并且在機(jī)動措施的選擇上,前者可選取輕緩的機(jī)動操作,后者的緊急度更高[5]。
自主間隔保持和碰撞規(guī)避的實現(xiàn)大致可分為3個部分[6]:①感知,即利用機(jī)載傳感器監(jiān)視周圍空域環(huán)境;②探測,即判定是否存在潛在沖突,并評估威脅程度;③規(guī)避,即通過生成規(guī)避策略與決策指令,由飛控裝置執(zhí)行機(jī)動,以降低威脅程度或消除威脅。
為了實現(xiàn)無人機(jī)進(jìn)入國家空域后的自主間隔保持和碰撞規(guī)避,本文提出一種基于ADS-B監(jiān)視技術(shù)的蟻群算法模型。
本文研究的模型功能邏輯架構(gòu)如圖1所示。該模型在感知部分采用ADS-B技術(shù),基于ADS-B信息進(jìn)行沖突的探測與規(guī)避;沖突探測部分包括水平初選、水平探測、垂直探測3個步驟,通過三維空間內(nèi)的距離判定來確定沖突目標(biāo);規(guī)避策略來自于沖突解脫模型,該模型基于蟻群算法進(jìn)行航路重規(guī)劃,并對蟻群算法的2個關(guān)鍵步驟(狀態(tài)轉(zhuǎn)移和信息素更新)進(jìn)行改進(jìn),引入綜合啟發(fā)函數(shù)、排序機(jī)制,以獲得優(yōu)質(zhì)解脫路徑及策略。
圖1 S&A系統(tǒng)功能模型架構(gòu)實現(xiàn)
為了實現(xiàn)環(huán)境感知,無人機(jī)需要配備傳感設(shè)備。其傳感設(shè)備包括合作式和非合作式2種[7]。ADS-B屬于一種合作式傳感器,依靠全球?qū)Ш叫l(wèi)星系統(tǒng)(global navigation satellite system,GNSS)和先進(jìn)的空-空、空-地數(shù)據(jù)鏈通信技術(shù)實現(xiàn)多種信息的生成和遠(yuǎn)距離交換。
依照信息傳輸?shù)姆较?,ADS-B應(yīng)用功能分為IN和OUT,其中OUT是基本功能。ADS-B的工作原理可概述為:配備了ADS-B OUT的飛行器通過機(jī)載發(fā)射器以一定周期主動向外廣播飛行器的各種信息,這些信息來自于GNSS和其他機(jī)載設(shè)備,主要包括飛行器識別信息、四維位置及速度信息、其他附加信息(航向、飛行員輸入信息、航跡改變關(guān)鍵點等)[8]。地面站和其他配備了ADS-B IN的飛行器最終會接收這些ADS-B OUT信息,以實現(xiàn)對空監(jiān)視與相互感知。此外,地面站也可以發(fā)送空中交通情報服務(wù)廣播(traffic information service-broadcast,TIS-B)和飛行情報服務(wù)廣播(flight information service-broadcast,FIS-B)給配備了ADS-B IN的飛行器。
作為一種新型對空監(jiān)視技術(shù),與傳統(tǒng)二次監(jiān)視雷達(dá)(secondary surveillance radar,SSR)相比,ADS-B具有提供信息內(nèi)容更全面、定位更精確、更新率更高等優(yōu)勢[9]。因此,ADS-B被有效應(yīng)用在空中交通管制、空對空協(xié)同、機(jī)場場面監(jiān)視等方面,有助于提高飛行的安全性和空管的高效性。在全球范圍內(nèi),ADS-B的部署都在積極推進(jìn)當(dāng)中。目前,我國在民用航空中正全面啟動ADS-B的管制運行,也已基本完成ADS-B地面設(shè)施布局,未來還將持續(xù)推進(jìn)、拓展其建設(shè)及應(yīng)用。
保護(hù)區(qū)和安全間隔的明確是沖突探測的基礎(chǔ)。探測和解脫算法采用圓柱體保護(hù)區(qū)模型作為飛行器實體的抽象,當(dāng)目標(biāo)飛行器進(jìn)入該區(qū)域,則表示發(fā)生了碰撞,其大小主要取決于飛行器性能;而間隔要求是在保護(hù)區(qū)的基礎(chǔ)上,將區(qū)域進(jìn)一步擴(kuò)展,其大小是根據(jù)所處空域、遭遇場景等多種因素確定的[4]。碰撞規(guī)避、自主間隔保持等功能的實現(xiàn)基礎(chǔ)是制定不同的間隔要求。綜合考慮飛行安全和算法的易實現(xiàn)性,在沖突探測與解脫算法模型分析中不再區(qū)分碰撞規(guī)避和自主間隔保持,而基于混合飛行場景,參考RTCA標(biāo)準(zhǔn)及文獻(xiàn)[8],將安全間隔標(biāo)準(zhǔn)統(tǒng)一設(shè)定為R=9.26 km,H=0.609 6 km。
而對于混合飛行場景中的飛行器,ADS-B提供的關(guān)鍵信息包括WGS-84(world geodetic system-1984)坐標(biāo)系下的三維位置信息、水平速度及航向角、垂直速度及升降標(biāo)識符,為了方便模型建立,需要將其轉(zhuǎn)換為空間直角坐標(biāo)系下的信息。在此基礎(chǔ)上,沖突探測功能的完成包括水平初選、水平探測和垂直探測3個部分。
水平初選的主要思想是排除明顯不可能沖突的目標(biāo),在此指逐漸遠(yuǎn)離的飛行器。在X-Y二維水平面上,本機(jī)A的位置坐標(biāo)為(x1,y1),入侵機(jī)B的位置坐標(biāo)為(x2,y2),A的航速矢量為VAhori=(v1horicosφ1,v1horisinφ1),B的航速矢量為VBhori=(v2horicosφ2,v2horisinφ2)。
相對于本機(jī)A,入侵機(jī)B的相對位置與相對航速分別為
水平初選的判斷依據(jù)即為[8,10]
S0=Pr·Vrhori
(3)
若S0≥0則表示兩機(jī)正在逐漸遠(yuǎn)離或持續(xù)保持間隔,而S0<0則表示兩機(jī)需要進(jìn)一步判斷。
經(jīng)過初步探測,快速過濾掉部分飛行器。而對于逐漸靠近的飛行器,還需要進(jìn)行距離計算,主要思路為計算最接近點(closet point of approach,CPA)處對應(yīng)的水平錯開距離(horizontal miss distance,HMD)[9],將其與水平最小安全間隔R進(jìn)行比較,如圖2所示。
圖2 水平?jīng)_突探測圖
根據(jù)幾何知識,有
(4)
(5)
在垂直方向上,考慮X-Z二維平面上,飛行器A的位置坐標(biāo)為(x1,z1),B的位置坐標(biāo)為(x2,z2),A的航速矢量為VAvert=(v1horicosφ1,v1vert),B的航速矢量為VBvert=(v2horicosφ2,v2vert)。
相對于本機(jī)A,入侵機(jī)B的相對航速為
Vrvert=(v2horicosφ2-v1horicosφ1,v2vert-v1vert)
(6)
入侵機(jī)B的相對飛行情景如圖3所示,圖中的矩形NMFE為在X-Z面上的安全間隔。
圖3 垂直沖突探測圖
B的相對航跡線對應(yīng)斜率為
(7)
根據(jù)幾何知識,可通過以下公式進(jìn)行垂直沖突判定[8]
若S1≥0且S2≥0,則表明在垂直面上,A和B之間將無沖突產(chǎn)生;反之,則需要進(jìn)行沖突解脫。
解脫算法是一種離散化航路規(guī)劃方法,按照等時長將解脫區(qū)域內(nèi)的各航路段劃分為K步,每一步可選擇的策略有27種,包括速度調(diào)整(減速20%、保持初始速度、加速20%)、航向角調(diào)整(左轉(zhuǎn)30°、保持初始航向角、右轉(zhuǎn)30°)、俯仰角調(diào)整(增加3°、保持初始俯仰角、減少3°)以及同時調(diào)整,記為C1~C27。
經(jīng)過航路劃分后,n機(jī)沖突解脫問題可以進(jìn)一步描述為:n架飛行器為一批次,對應(yīng)n條沖突航路。其中,每架飛行器在每一步選擇一種策略,經(jīng)過K步后到達(dá)最終位置,要求其最終到達(dá)點與原計劃目標(biāo)點的延誤距離盡可能小,并且此過程不能存在與其他飛行器的沖突。
則經(jīng)過K步后,飛行器i的最終位置與目的地之間的延誤距離為
(10)
目標(biāo)函數(shù)即為
(11)
約束條件為無沖突產(chǎn)生,即在任意步k(1≤k≤K)后,飛行器i(1≤i≤n)與飛行器j(1≤j≤n,且j≠i)之間的距離滿足下式
(12)
(13)
式中:R為水平最小安全間隔;H/2為垂直最小安全間隔。
為了尋找無沖突的優(yōu)質(zhì)航路,模型采用蟻群算法進(jìn)行分析。蟻群算法是一種用來尋找優(yōu)化路徑的概率型算法,這種算法具有分布計算、信息正反饋和啟發(fā)式搜索的特征,本質(zhì)上是進(jìn)化算法中的一種啟發(fā)式全局優(yōu)化算法。蟻群算法是經(jīng)過迭代來尋找最優(yōu)解,迭代過程中的狀態(tài)轉(zhuǎn)移和信息素更新是蟻群算法的關(guān)鍵步驟。
首先,狀態(tài)轉(zhuǎn)移需要按照信息素濃度計算路段的被選概率,在此基礎(chǔ)上采用輪盤賭方式進(jìn)行隨機(jī)選擇;其中,概率的計算是狀態(tài)轉(zhuǎn)移的關(guān)鍵。假設(shè)每一次迭代過程中,均有M批次飛行器依次飛行。在第t次迭代中,第m(1≤m≤M)批次的某架飛行器正進(jìn)行下一步選擇時,選擇策略Ci的概率為[11]
(14)
式中,τCi(t)為策略Ci對應(yīng)路段的信息素值。該信息素值在經(jīng)過此次迭代后將進(jìn)行更新,更新過程按照(15)式進(jìn)行
(15)
(16)
目前,已有文獻(xiàn)對蟻群算法的優(yōu)化,主要圍繞算法的核心步驟來進(jìn)行[12-13]:①對初始信息素分布進(jìn)行優(yōu)化,例如引入人工勢場法、遺傳算法等方法對解空間進(jìn)行初步分析,進(jìn)而差異化分布初始信息素,可以降低初期搜索的盲目性,加快收斂速度;②對狀態(tài)轉(zhuǎn)移方式與啟發(fā)規(guī)則進(jìn)行優(yōu)化,例如引入?yún)?shù)的自適應(yīng)機(jī)制,讓前期搜索中啟發(fā)信息占主導(dǎo),后期搜索中信息素濃度占主導(dǎo),可以改善蟻群算法易陷入局部最優(yōu)的缺點,并權(quán)衡算法效率[9];③對信息素更新規(guī)則進(jìn)行優(yōu)化,例如引入最大最小蟻群、精英策略、排序機(jī)制等,可以避免陷入局部最優(yōu)、加快算法收斂速度。
已有的優(yōu)化方法多圍繞蟻群算法自身缺點,強(qiáng)調(diào)提升全局尋優(yōu)能力、避免陷入局部最優(yōu)、加快收斂速度[12]。而在實際航路規(guī)劃應(yīng)用中,除環(huán)境因素外,無人機(jī)最大轉(zhuǎn)彎角度、航程、最小航線段長度等限制都會成為規(guī)劃的約束條件[14],也有部分文獻(xiàn)基于啟發(fā)式算法,將目標(biāo)改為最小化路徑綜合代價,考慮飛行高度、路徑長度、平滑度、障礙物威脅等[15-16],進(jìn)而提高了特定威脅情景下的規(guī)劃效果,但改進(jìn)主要面向靜態(tài)障礙物的避撞。
而本文圍繞基于ADS-B的協(xié)同解脫,對模型狀態(tài)轉(zhuǎn)移方式、信息素更新方式進(jìn)行改進(jìn),以優(yōu)化算法本身缺點,并提高模型的適應(yīng)性。
4.3.1 狀態(tài)轉(zhuǎn)移方式改進(jìn)
基本解脫模型以信息素為路段選擇的唯一標(biāo)準(zhǔn),由于解空間較大又缺少啟發(fā)部分,極易陷入局部最優(yōu)。在飛行器沖突解脫情景中,優(yōu)質(zhì)航路的判定標(biāo)準(zhǔn)是綜合性的。并且,在實際飛行中,最大轉(zhuǎn)彎角度、最小航線段長度等限制使得平滑的航路更具可操作性,而最大航程限制等因素要求規(guī)劃航路盡可能接近原航路。因此,引入綜合啟發(fā)部分,通過增強(qiáng)搜索隨機(jī)性以避免局部最優(yōu)問題,同時綜合考慮無人機(jī)性能等約束條件以減少無效的隨機(jī)搜索。
第一項因素為每步延誤距離,若每步的延誤距離較小,則航路會盡量接近原航路,最終延誤距離也會較小。第二項因素為角度變化[11,17],作為第一項因素的補(bǔ)充,加強(qiáng)與原航路的接近度。第三項因素為每步航向轉(zhuǎn)變度,旨在讓航路平滑,減少大幅度變向的出現(xiàn)。類似的,第四項因素為每步速度轉(zhuǎn)變度,旨在讓速度的變化更加平緩。綜合四項因素的啟發(fā)函數(shù)即為
ηCi(t)=
(17)
經(jīng)過以上改進(jìn),下一步策略Ci的選擇概率為
(18)
式中,α和β表示各部分的相對重要程度。
4.3.2 信息素更新方式改進(jìn)
基本蟻群解脫模型中,信息素更新方式采用的是蟻周模型,最終延誤采用的是n架飛行器的總延誤,但若存在其中一架飛行器最終延誤較大,而其他飛行器最終延誤較小的情況,這些被連累的較優(yōu)質(zhì)路徑可能會因此被漏選。而另一種較為常用的蟻量模型則是考慮每一步延誤,過于局部化而忽略了全局情況。因此,在原信息素更新方式上改進(jìn)為采用每一架飛行器的最終延誤。
并且,為了加快收斂,在改進(jìn)中引入排序機(jī)制[11-12],讓優(yōu)質(zhì)路徑的信息素增加,而較差的路徑信息素增量為0。因此,最終的信息素更新方式變?yōu)?/p>
(19)
為了充分檢驗?zāi)P偷挠行?對沖突探測和沖突解脫分別設(shè)定情景進(jìn)行仿真實驗。實驗的硬件運行環(huán)境主要為2.8 GHz的Intel Core i5處理器,4 GB內(nèi)存;軟件運行平臺為MATLAB 9.1。
模擬場景為多機(jī)(無人機(jī)與有人機(jī)混合)沖突探測。仿真實驗中假設(shè)本機(jī)位于坐標(biāo)原點,速度與航向隨機(jī)生成,其周圍40 km范圍內(nèi)存在100架目標(biāo)飛行器,關(guān)鍵飛行狀態(tài)數(shù)據(jù)按如下條件隨機(jī)生成:
1) 目標(biāo)飛行器速度值:vhori∈[180,360],vvert∈[-30,30],單位為km/h;
2) 目標(biāo)飛行器水平航向:與X軸夾角φ∈[0,2π];
3) 目標(biāo)飛行器坐標(biāo):x∈(9.26cosθ,40cosθ),y∈(9.26sinθ,40sinθ),θ∈(0,2π],z∈[-1.5,1.5],單位為km。
圖4 沖突探測結(jié)果
圖5 沖突概率分布
基于MATLAB進(jìn)行100 000次蒙特卡洛實驗,每次模擬探測域內(nèi)均有100架目標(biāo)飛行器。圖4為單次實驗結(jié)果,圖5為蒙特卡洛統(tǒng)計結(jié)果。實驗結(jié)果顯示,在100架目標(biāo)飛行器中,最終的平均沖突數(shù)量為7.185 5架,表明探測模型的過濾效果顯著。
經(jīng)過探測,能明顯過濾出潛在沖突目標(biāo),隨即進(jìn)行解脫操作。一般情況下,面對探測出的多架沖突目標(biāo),可以在探測部分追加計算沖突的潛在發(fā)生時間,從而排列出先后順序,賦予目標(biāo)不同的優(yōu)先級,依次實現(xiàn)雙機(jī)或多機(jī)沖突解脫。
為了驗證模型的可行性,分別對迎面遭遇、追尾遭遇、正側(cè)向遭遇3種典型情況進(jìn)行驗證。迎面遭遇和正側(cè)向遭遇場景中假設(shè)兩機(jī)均以360 km/h的速度飛行,追尾遭遇場景中則分別以360 km/h和270 km/h的速度飛行。
相關(guān)參數(shù)設(shè)定為α=1,β=2,衰減系數(shù)ρ=0.3,信息素量Q=100,批次數(shù)M=20,總步數(shù)K=20,迭代次數(shù)為200次。
經(jīng)過仿真,改進(jìn)模型給出了圖6的解脫策略。在3種場景中,最終總延誤距離分別為1.490 2 km,0.833 2 km,1.408 8 km。
圖6 兩機(jī)沖突解脫
除簡單的兩機(jī)沖突場景外,還存在多機(jī)同時產(chǎn)生沖突的復(fù)雜情況。重新設(shè)定場景,假設(shè)存在4架飛行器同時進(jìn)入解脫區(qū)域,表1為飛行器的初始飛行狀態(tài)。
表1 飛行器初始狀態(tài)
為了更好地體現(xiàn)模型優(yōu)化的效果,對該沖突場景,分別采用遺傳算法、基本蟻群算法、改進(jìn)蟻群算法模型進(jìn)行解脫,解脫結(jié)果與最優(yōu)總延誤距離的收斂過程如圖7~8所示。
圖7 四機(jī)沖突解脫
圖8 收斂過程對比
并且,就無人機(jī)物理性能、航路質(zhì)量和算法性能方面[18],選取航路長度、航路平滑度、最終延誤距離和收斂性作為指標(biāo),對路徑質(zhì)量進(jìn)行綜合判斷,得到表2的算法對比結(jié)果。
表2 四機(jī)沖突解脫效果對比
實驗結(jié)果顯示,在無人機(jī)物理性能方面,要求航路盡可能平滑,具有可操作性,改進(jìn)模型與遺傳算法、基本蟻群模型相比,在航向轉(zhuǎn)變次數(shù)上略有優(yōu)化,航路更加平滑;在航路質(zhì)量方面,要求能耗盡可能小,即航路總長度較小,并且對原航路的偏離盡量小,改進(jìn)模型優(yōu)勢相對明顯;在算法性能上,蟻群算法收斂較遺傳算法快,但也更易陷入局部最優(yōu),改進(jìn)模型中,啟發(fā)部分增強(qiáng)了搜索的隨機(jī)性,求解速度受到影響,但排序機(jī)制的引入則加快了收斂,使得模型能快速找到較優(yōu)解脫路徑。
本文針對無人機(jī)感知與規(guī)避系統(tǒng),充分利用ADS-B提供的實時動態(tài)航行信息,提出了確定型沖突探測模型和基于蟻群算法的沖突解脫模型;前者能有效過濾出無人機(jī)周圍的沖突目標(biāo)以待進(jìn)行解脫,而后者能為無人機(jī)及沖突對象重新規(guī)劃較優(yōu)質(zhì)的解脫路徑。經(jīng)仿真實驗驗證,探測模型的過濾效果良好,而解脫模型不僅能解決雙機(jī)沖突,在復(fù)雜的多機(jī)沖突情景下也能提供較好的解脫路徑。但基于條件有限,本文考慮的是較為理想情況下的感知與規(guī)避,天氣因素影響、應(yīng)用場景差別等諸多問題并未進(jìn)行考慮。在未來的研究中,模型還需結(jié)合現(xiàn)實場景需求進(jìn)行適應(yīng)性改進(jìn),針對特殊應(yīng)用場景進(jìn)行更深入的探討,并在算法性能與效果上實現(xiàn)進(jìn)一步完善與優(yōu)化。