基于空間映射的異構(gòu)無(wú)人機(jī)在線沖突消解算法

楊健 鐘紫凡 楊少博

隨著與無(wú)人機(jī)相關(guān)的技術(shù)不斷成熟,人們看到了將其用于各種場(chǎng)景和領(lǐng)域的巨大潛力.例如應(yīng)用無(wú)人機(jī)進(jìn)行交通情況監(jiān)視、貨物運(yùn)輸、災(zāi)難現(xiàn)場(chǎng)的搜索救援等等[1?2].我們可以暢想,在不遠(yuǎn)的未來(lái),無(wú)人機(jī)會(huì)成為空中交通的重要一員.未來(lái)無(wú)人機(jī)將大量應(yīng)用在大城市及其周邊區(qū)域的上空,在那里無(wú)人機(jī)將與其他有人航空器(例如私人飛機(jī))共享空域.無(wú)人機(jī)之間以及無(wú)人機(jī)與有人機(jī)之間的碰撞會(huì)對(duì)其他有人航空器或者地面的人和財(cái)產(chǎn)造成威脅.因此,政府在考慮發(fā)展無(wú)人機(jī)產(chǎn)業(yè)的同時(shí)由于擔(dān)憂無(wú)人機(jī)產(chǎn)生的空域安全問(wèn)題而有所顧慮.

如何讓無(wú)人機(jī)在空中安全而高效地飛行？這個(gè)問(wèn)題越來(lái)越成為人們關(guān)注的熱點(diǎn).我們知道有人機(jī)的安全飛行大多依賴細(xì)致的預(yù)先調(diào)度和周密的飛行計(jì)劃[3].在周密細(xì)致的事前工作保證下,空中交通管理部門(mén)不需面臨太大的實(shí)時(shí)處置壓力.這種模式對(duì)無(wú)人機(jī)并不適用.首先,無(wú)人機(jī)的起飛場(chǎng)地要求比較低,一個(gè)城市內(nèi)有很多場(chǎng)地都可供無(wú)人機(jī)起飛,難以對(duì)飛機(jī)進(jìn)行全面監(jiān)管;另外,未來(lái)無(wú)人機(jī)飛行應(yīng)用靈活,可能會(huì)在一個(gè)局部空域中大量聚集,無(wú)人機(jī)為了完成既定的任務(wù),其航跡可能由很多不規(guī)則的折線組成而不像有人飛機(jī)那樣一般是起點(diǎn)到終點(diǎn)間的連線.因此,有人機(jī)的管控方法難以直接應(yīng)用于無(wú)人機(jī)空中交通管理.為了滿足將無(wú)人機(jī)納入空中交通管理系統(tǒng)的需求,需要增強(qiáng)空中交通管理系統(tǒng)實(shí)時(shí)協(xié)調(diào)處理空中交通用戶的能力.

無(wú)人機(jī)的種類(lèi)多樣,未來(lái)在空中飛行的無(wú)人機(jī)的類(lèi)型各異,載荷和平臺(tái)性能不同.針對(duì)異構(gòu)無(wú)人機(jī)沖突消解問(wèn)題的研究存在現(xiàn)實(shí)需求.當(dāng)前學(xué)術(shù)界已經(jīng)提出了很多處理沖突消解的方法,例如航線規(guī)劃方法[4]、智能優(yōu)化算法[5]、半正定規(guī)劃方法[6]、幾何導(dǎo)航算法[7].其中基于幾何導(dǎo)航的方法不依靠需要大量計(jì)算的復(fù)雜預(yù)測(cè)和分析,在實(shí)時(shí)處理大量無(wú)人機(jī)沖突上具有較好的應(yīng)用前景[8].

本文基于幾何導(dǎo)航方法的研究分析無(wú)人機(jī)間的沖突.由于在天空中運(yùn)行的無(wú)人機(jī)用處不同,因此,其載荷和平臺(tái)性能有很大的差異.未來(lái)天空中飛行的無(wú)人機(jī)大部分是異構(gòu)無(wú)人機(jī).當(dāng)兩個(gè)無(wú)人機(jī)的速度不同時(shí),它們的安全間隔約束條件是非線性的.非線性問(wèn)題比線性問(wèn)題的求解難度大.為提升計(jì)算效率,很多研究人員研究了多種方法歸納出線性的安全間隔約束條件[9?11].我們研究提出了一個(gè)兩層次求解機(jī)制尋找局部最優(yōu)解[12],該算法具有較好的計(jì)算效果.但這些已有方法的計(jì)算效率仍然難以滿足實(shí)時(shí)沖突消解的需求.

本文研究異構(gòu)無(wú)人機(jī)的沖突消解方法[13].應(yīng)用空間映射方法將每個(gè)一對(duì)一的沖突約束條件推導(dǎo)為基于周期的線性約束不等式,并將問(wèn)題建模為混合整數(shù)線性規(guī)劃問(wèn)題加以求解.

1 問(wèn)題提出

假設(shè)無(wú)人機(jī)在空中執(zhí)行具體任務(wù)的過(guò)程中其飛行高度不發(fā)生變化,因此,本文研究二維空間無(wú)人機(jī)的沖突消解問(wèn)題.假設(shè)在局部區(qū)域中有N個(gè)無(wú)人機(jī)陷入空間沖突中,在二維空間,無(wú)人機(jī)Ai,i∈N的位置定義為Pi(t)=(xi(t),yi(t)),速度vi(t),運(yùn)動(dòng)方向φi(t).無(wú)人機(jī)的運(yùn)動(dòng)學(xué)模型描述為式(1):

加速度ai(t)與角速度wi(t)是控制無(wú)人機(jī)運(yùn)動(dòng)的兩個(gè)變量.假設(shè)空域沖突時(shí)無(wú)人機(jī)速度保持不變,依靠調(diào)整運(yùn)動(dòng)方向保證飛行安全.空中交通管理系統(tǒng)動(dòng)態(tài)監(jiān)控空域中無(wú)人機(jī)的基本信息,如位置、速度、運(yùn)動(dòng)方向及既定的航路點(diǎn).為了保證無(wú)人機(jī)飛行安全,需為每個(gè)無(wú)人機(jī)設(shè)定獨(dú)立的安全空域.這個(gè)安全區(qū)域隨著無(wú)人機(jī)的位置動(dòng)態(tài)移動(dòng),其他的航空器進(jìn)入這個(gè)區(qū)域會(huì)對(duì)本無(wú)人機(jī)產(chǎn)生較大的安全威脅.安全空域可被定義為球狀區(qū)域,也可定義為圓柱狀區(qū)域.研究同一平面內(nèi)的無(wú)人機(jī)沖突問(wèn)題時(shí)這兩種區(qū)域在水平面上都是一個(gè)具有安全半徑ri的圓形投影,被定義為Di(Pi(t),ri).由于無(wú)人機(jī)平臺(tái)比有人機(jī)平臺(tái)小很多,根據(jù)無(wú)人機(jī)的平臺(tái)和飛行速度,將無(wú)人機(jī)的安全空域半徑設(shè)定為數(shù)百米[14].無(wú)人機(jī)Ai和Aj的距離小于時(shí)定義為失距,是復(fù)合安全半徑=max(ri,rj).將Ai與Aj間的安全約束定義為式(2):

其中k.k是二維空間中的歐氏范數(shù).

沖突消解的目標(biāo)是為每個(gè)無(wú)人機(jī)找到在時(shí)間段[0,τ]內(nèi)合適的調(diào)整方向?i以保證局部空域的無(wú)人機(jī)在τ時(shí)刻前不會(huì)發(fā)生失距.無(wú)人機(jī)的動(dòng)力學(xué)性能約束其不可能在瞬時(shí)完成規(guī)劃的機(jī)動(dòng)角度的調(diào)整.我們假設(shè)無(wú)人機(jī)的跟蹤系統(tǒng)能夠在其性能范圍內(nèi)跟蹤?i.本文考慮應(yīng)用dubins曲線近似無(wú)人機(jī)調(diào)整方向的過(guò)程,如圖1所示.假設(shè)無(wú)人機(jī)將通過(guò)兩次方向調(diào)整θ1和θ2達(dá)到角度調(diào)整的目標(biāo)[15].

為了確保為Ai規(guī)劃的機(jī)動(dòng)角度?i滿足其動(dòng)力學(xué)約束,應(yīng)確定Ai在時(shí)間段[0,τ]內(nèi)的最大可跟蹤角度(τ).可應(yīng)用τ與最大角速度估計(jì)(τ)的取值[15].?i應(yīng)滿足約束:

實(shí)時(shí)規(guī)劃中為了提高計(jì)算效率假設(shè)無(wú)人機(jī)的飛行線路為直線,如圖1所示的點(diǎn)劃線.點(diǎn)劃線的距離與飛機(jī)實(shí)際飛行的距離有誤差,這些誤差在無(wú)人機(jī)跟蹤路徑過(guò)程中消除[16].

首選分析兩個(gè)無(wú)人機(jī)的安全間隔約束.在局部坐標(biāo)系中討論無(wú)人機(jī)間的關(guān)系.如圖2所示,Ai和Aj存在空域沖突,以Aj當(dāng)前位置為局部坐標(biāo)系原點(diǎn),在t=0時(shí)刻Ai在局部坐標(biāo)系中位置如式(4):

Ai與Aj間存在空域沖突.這類(lèi)空域沖突被定義為既有沖突,意為如不調(diào)整運(yùn)動(dòng)方向,兩無(wú)人機(jī)將發(fā)生失距[16].假設(shè)它們分別調(diào)整?i與?j.經(jīng)過(guò)調(diào)整后兩機(jī)速度為式(5):

Aj相對(duì)Ai的速度為:

為保證Ai與Aj的安全間隔,v v vj j ji應(yīng)在圖2中灰色區(qū)域以外,安全間隔約束條件式(2)轉(zhuǎn)換為:

其中kji是v v vj j ji的斜率.為了討論式(7)的可行解,定義等式:

其判別式:

假設(shè)兩個(gè)無(wú)人機(jī)在t=0時(shí)保持著安全間隔,故有?>0.式(8)的兩個(gè)實(shí)數(shù)根:

式(7)的可行域由和確定.通過(guò)坐標(biāo)系旋轉(zhuǎn)將可行域歸納為[15]:

將kji展開(kāi)為式(12):

kji是周期為 [?π/2+kπ,π/2+kπ],k∈Z的周期函數(shù).整理式(12)為式(13):

如圖3所示,完整的可行解區(qū)域被劃分為區(qū)域1和區(qū)域2.雖然這兩個(gè)區(qū)域是聯(lián)通的,但因?yàn)檫@兩個(gè)區(qū)域?qū)儆趉ji不同的周期而難以將其描述為一個(gè)整體區(qū)域并求解沖突消解策略.本文研究在kji的不同周期分別求解沖突消解策略.定義kji的分母函數(shù)式14):

為了方便討論,設(shè)定v v vji在4個(gè)象限的方位角為[?π/2,3π/2].(?i,?j)確定了kji的周期性.應(yīng)用函數(shù)(?i,?j)取值正負(fù)判斷kji的周期[15].定義布爾變量dsij判斷函數(shù)(?i,?j)在區(qū)域1與區(qū)域2上的正負(fù)值.定義v v vji的朝向?yàn)棣誮i,dsij的取值定義:

a)若(0,0)6=0,如果φji∈[π/2,π?3/2]且0,0)<0,或φji∈[?π/2,π/2]且(0,0)>0,dsij=1否則dsij=0.

b)若(0,0)=0,給無(wú)人機(jī)的飛行方向增加一個(gè)微小的擾動(dòng)(使得=0.將會(huì)得到新的值.可以根據(jù))的正負(fù)確定dsij的取值.

由此可確定能保證安全間隔的(?i?j)應(yīng)滿足:

1)若dsij=1可行解區(qū)域滿足

或

2)當(dāng)dsij=0可行解區(qū)間滿足約束:

或

當(dāng)涉及沖突的無(wú)人機(jī)多于兩個(gè)時(shí),需考慮飛機(jī)間的潛在沖突[12],定義變量cij:

2 空間映射方法

Ai與Aj速度相同時(shí),kji與(?i?j)的關(guān)系是線性的[7].但大多數(shù)情況下無(wú)人機(jī)速度不相同,此時(shí)基于方向調(diào)整的沖突消解問(wèn)題是一個(gè)混合整數(shù)非線性優(yōu)化問(wèn)題,其計(jì)算復(fù)雜度比線性優(yōu)化問(wèn)題復(fù)雜[9,16].當(dāng)無(wú)人機(jī)的速度不同時(shí)為了建立kji與(?i,?j)的線性關(guān)系,對(duì)式(13)進(jìn)行進(jìn)一步討論.

兩個(gè)無(wú)人機(jī)的安全間隔約束為式(15)、式(16)與式(17)、式(18).根據(jù)約束條件特點(diǎn),定義映射關(guān)系如式(20):

與的值域?yàn)閇?1,1].式(20)將角度值關(guān)系映射為正弦值關(guān)系.式(13)轉(zhuǎn)換為xis,b與ysj,b的關(guān)系:

由此,安全間隔約束被轉(zhuǎn)換為正弦值空間的線性關(guān)系.對(duì)式(21)進(jìn)行進(jìn)一步討論以得到每個(gè)無(wú)人機(jī)的機(jī)動(dòng)約束.以不等式約束的可行解為例,如圖4所示.深灰色區(qū)域?yàn)榭尚薪庠M()對(duì)應(yīng)的可行解區(qū)域,將其定義為,b∈1,2.?()對(duì)應(yīng)在角度空間能保證Ai與Aj安全間隔的機(jī)動(dòng)策略對(duì)(φi,φj).深黑線是可行解邊界,其表達(dá)式如式(21).與坐標(biāo)軸的夾角為

坐標(biāo)系中,當(dāng)Ai與Aj的運(yùn)動(dòng)方向不變時(shí)初始點(diǎn)為=xis,,bo=sin(φi(0)?δ(),=sin(φj(0)? δ().當(dāng)Ai與Aj存在既有沖突時(shí).此時(shí)需Ai和Aj調(diào)整(?i,?j)以使(φi(0)+?i,?j(0)+?j)的映射在區(qū)域內(nèi).定義向量如式(23):

uhh的范數(shù)為從到可行域的最小距離.根據(jù)可計(jì)算得Ai應(yīng)負(fù)擔(dān)的調(diào)整量在映射空間中的取值和Aj應(yīng)負(fù)擔(dān)的調(diào)整量在映射空間中的取值(φi(0)+?i,φj(0)+?j)經(jīng)過(guò)映射后在坐標(biāo)系上的坐標(biāo)為=.從到映射的向量被定義為,如圖4(a)所示.為了保證Ai與Aj的安全間隔,需滿足約束:

無(wú)人機(jī)間存在潛在沖突時(shí),其機(jī)動(dòng)角度約束也可被描述為式(15),式(16)或式(17),式(18).由于安全區(qū)域邊界的影響,由潛在沖突會(huì)得到兩個(gè)不同的約束,一個(gè)與既有沖突的相同,另一個(gè)約束定義了Ai與Aj在當(dāng)前狀態(tài)下可機(jī)動(dòng)角度而不是須機(jī)動(dòng)角度.如圖4(b)所示,深灰色區(qū)域?yàn)榭尚薪鈪^(qū)域,定義為1or2,且.定義一個(gè)向量

為保證無(wú)人機(jī)間安全間隔,應(yīng)滿足約束:

Ai與Aj的機(jī)動(dòng)角度在正弦值空間的映射需分別滿足或在各坐標(biāo)系上映射分量的約束.

基于這個(gè)規(guī)則,涉及既有沖突的Ai與Aj應(yīng)滿足如下約束.

無(wú)人機(jī)之間存在潛在約束時(shí)應(yīng)當(dāng)滿足下面的不等式:

由此由非線性沖突約束推導(dǎo)出線性約束條件.在計(jì)算獲得正弦值空間內(nèi)的線性約束條件后經(jīng)過(guò)反三角函數(shù)運(yùn)算即可得到Ai在與Aj的沖突中的機(jī)動(dòng)角度約束條件,如同樣也可以得到Ai的機(jī)動(dòng)角度約束條件進(jìn)一步可分別得到由與分別確定的Ai和Aj的可機(jī)動(dòng)區(qū)域.最終可建立Ai與Aj一對(duì)一沖突中的可行域集合Sij.由于篇幅限制本文不再贅述.

3 沖突消解問(wèn)題建模

3.1 沖突消解目標(biāo)函數(shù)

沖突消解的目的是找到能使無(wú)人機(jī)消耗降低的安全機(jī)動(dòng)解,需要設(shè)計(jì)合理的目標(biāo)函數(shù).由于無(wú)人機(jī)速度不變,認(rèn)為無(wú)人機(jī)機(jī)動(dòng)消耗與當(dāng)前飛行方向和期望飛行方向的角度差正相關(guān)[17].由于無(wú)人機(jī)可能在處理當(dāng)前面臨的沖突前由于風(fēng)力或者其他因素的影響而偏離原定的航線,設(shè)當(dāng)前Ai原本偏離期望航線的角度為,經(jīng)過(guò)機(jī)動(dòng)過(guò)后偏離期望航向的角度變?yōu)閒i=|?i+.無(wú)人機(jī)采用機(jī)動(dòng)角度造成的損失定義為:

為消去絕對(duì)值帶來(lái)的非線性特性,將目標(biāo)函數(shù)定義為式(32)[18]:

其中0,且0.它們滿足約束:

3.2 混合整數(shù)線性規(guī)劃模型

應(yīng)用在正弦值空間定義的向量可將非線性約束轉(zhuǎn)化為解耦的線性約束.由于兩個(gè)無(wú)人機(jī)的沖突可行解區(qū)域分布在kji的兩個(gè)周期中,每個(gè)周期內(nèi)有?i與?j的一到兩個(gè)可行解區(qū)間.最優(yōu)方向調(diào)整解需在多個(gè)獨(dú)立可行解區(qū)間中搜索.

在多無(wú)人機(jī)發(fā)生沖突時(shí),對(duì)每個(gè)一對(duì)一沖突Ai與Aj可行解區(qū)間的選擇會(huì)影響它們與其他無(wú)人機(jī)構(gòu)成沖突對(duì)的優(yōu)化解的搜索.因此,多無(wú)人機(jī)沖突可以看作是多個(gè)相互耦合的一對(duì)一沖突,本文應(yīng)用混合整數(shù)線性規(guī)劃方法求解多無(wú)人機(jī)沖突消解問(wèn)題.

將多無(wú)人機(jī)集中協(xié)作式方向調(diào)整問(wèn)題建模為混合整數(shù)線性規(guī)劃問(wèn)題.目標(biāo)函數(shù)為降低所有無(wú)人機(jī)的機(jī)動(dòng)角度之和:

M是一個(gè)較大的數(shù)值.是布爾變量以建模安全約束的或條件.它可以被用來(lái)標(biāo)示優(yōu)化時(shí)選擇了哪個(gè)約束,也就是在集合Sij的哪個(gè)子區(qū)間中搜索最優(yōu)解.由于目標(biāo)函數(shù)和安全約束都是選定的參數(shù)的線性約束,因此,整個(gè)問(wèn)題就是一個(gè)標(biāo)準(zhǔn)化的混合整數(shù)線性規(guī)劃模型,可應(yīng)用高效的求解器求解.

4 仿真驗(yàn)證

本文設(shè)置了兩個(gè)場(chǎng)景展示算法對(duì)復(fù)雜沖突場(chǎng)景的處置效果.仿真計(jì)算的平臺(tái)條件是Intel Core i5 2.8GHz,4GB RAM.軟件平臺(tái)為Microsoft Windows 7 Professional系統(tǒng),采用 MATLAB 2014編程求解.求解混合整數(shù)線性規(guī)劃的求解器為CPLEX.空中交通管理要素持續(xù)監(jiān)視無(wú)人機(jī)的狀態(tài),過(guò)程中不存在時(shí)延或丟包現(xiàn)象.仿真二維環(huán)境中消解無(wú)人機(jī)的沖突.無(wú)人機(jī)的速度范圍為[40m/s～60m/s].考慮到無(wú)人機(jī)的速度,空中交通管理系統(tǒng)對(duì)無(wú)人機(jī)的監(jiān)視距離為2.5km.τ取值為35s.無(wú)人機(jī)Aii∈N的安全空域半徑為.在仿真中設(shè)定為5deg/s.在實(shí)際場(chǎng)景中每個(gè)無(wú)人機(jī)的方向調(diào)整可能不同.

4.1 聚集場(chǎng)景

圖5展示大量異構(gòu)無(wú)人機(jī)匯聚的場(chǎng)景.多無(wú)人機(jī)匯聚場(chǎng)景經(jīng)常被用于在檢驗(yàn)一個(gè)算法的有效性[11].因?yàn)樵趨R聚場(chǎng)景中每個(gè)無(wú)人機(jī)都與其他無(wú)人機(jī)存在沖突,一對(duì)一的沖突個(gè)數(shù)為N(N?1)/2,此時(shí)的沖突場(chǎng)景可以建模為一個(gè)無(wú)向全聯(lián)通圖[12].很多研究人員展示了他們的算法在處理同構(gòu)無(wú)人機(jī)匯聚場(chǎng)景中的表現(xiàn),實(shí)際上這種條件下的安全間隔約束是線性約束,計(jì)算容易.本文展示當(dāng)無(wú)人機(jī)的速度不同時(shí)采用方向調(diào)整策略解決沖突的場(chǎng)景.無(wú)人機(jī)的初始狀態(tài)如表1.

應(yīng)用本算法消解無(wú)人機(jī)沖突結(jié)果如圖5所示.

沖突消解結(jié)果如圖5所示,無(wú)人機(jī)采用右轉(zhuǎn)以擺脫失距風(fēng)險(xiǎn).完成消解沖突后無(wú)人機(jī)將返回原定航線.表1記錄了每個(gè)無(wú)人機(jī)的安全區(qū)域半徑和它在飛行過(guò)程中與其他無(wú)人機(jī)的最小距離.針對(duì)12個(gè)異構(gòu)無(wú)人機(jī)匯聚沖突,CPLEX求解器計(jì)算時(shí)間為0.2s左右.該計(jì)算效率能夠滿足在線實(shí)時(shí)的沖突消解規(guī)劃需求.規(guī)劃結(jié)果說(shuō)明應(yīng)用本算法能夠使無(wú)人機(jī)通過(guò)合適的角度調(diào)整保持安全間隔.

4.2 方格場(chǎng)景沖突消解

圖6展示了異構(gòu)多無(wú)人機(jī)在方格場(chǎng)景中的沖突消解問(wèn)題.本場(chǎng)景中,12個(gè)無(wú)人機(jī)被分為4組.無(wú)人機(jī)初始狀態(tài)如表2所示.無(wú)人機(jī)會(huì)在十字交叉區(qū)域處發(fā)生沖突.方格場(chǎng)景中由于無(wú)人機(jī)不向同一個(gè)方向匯聚,其沖突的復(fù)雜性較匯聚場(chǎng)景簡(jiǎn)單,處置每組沖突的計(jì)算時(shí)間為0.05s左右.應(yīng)用本文算法解決無(wú)人機(jī)沖突得到能夠保證無(wú)人機(jī)飛行安全的航線如圖6所示.無(wú)人機(jī)在飛行過(guò)程中與其他飛機(jī)間的最小距離如表2所示.數(shù)據(jù)說(shuō)明應(yīng)用本文的算法能保證無(wú)人機(jī)飛行過(guò)程中的安全間隔.

表1 多異構(gòu)無(wú)人機(jī)沖突消解信息

表2 多異構(gòu)無(wú)人機(jī)沖突消解信息

這兩個(gè)沖突消解的場(chǎng)景證明了本文提出的算法解決復(fù)雜沖突的有效性.應(yīng)用本文的算法無(wú)人機(jī)在規(guī)避沖突時(shí)不會(huì)進(jìn)行多余方向調(diào)整.由于在優(yōu)化計(jì)算時(shí)會(huì)考慮事先規(guī)劃的路徑,因此,產(chǎn)生的偏移量較小,造成的機(jī)動(dòng)消耗也較小.

5 結(jié)論

本文提出了解決異構(gòu)無(wú)人機(jī)間沖突的局部集中式優(yōu)化方法.該方法應(yīng)用空間映射方法由非線性安全間隔約束推導(dǎo)得到線性約束.從而問(wèn)題可被建模為混合整數(shù)線性規(guī)劃模型.算法具有實(shí)時(shí)消解多無(wú)人機(jī)復(fù)雜沖突的能力,可以用于解決通信帶寬較大條件下的多無(wú)人機(jī)沖突消解問(wèn)題.算法可以集成到空域管理系統(tǒng)中用于處置航空器的非預(yù)期過(guò)度接近問(wèn)題.