基于改進(jìn)人工勢(shì)場(chǎng)法的多機(jī)改航路徑規(guī)劃

王興隆, 徐肖豪, 馮江然

(中國(guó)民航大學(xué) 空中交通管理研究基地, 天津 300300)

基于改進(jìn)人工勢(shì)場(chǎng)法的多機(jī)改航路徑規(guī)劃

王興隆, 徐肖豪, 馮江然

(中國(guó)民航大學(xué) 空中交通管理研究基地, 天津 300300)

惡劣天氣是航空運(yùn)輸中造成航班延誤的主要因素,實(shí)施改航策略是減少延誤的一種有效方法,多航空器路徑規(guī)劃是改航策略的關(guān)鍵環(huán)節(jié)。針對(duì)惡劣天氣造成大量航班延誤情況,提出了采用人工勢(shì)場(chǎng)法進(jìn)行多機(jī)改航路徑規(guī)劃。根據(jù)航空器所受引力和斥力建立了傳統(tǒng)人工勢(shì)場(chǎng)模型,為解決在改航期間航空器受力出現(xiàn)局部最小值的問(wèn)題,在航空器之間、航空器與惡劣天氣之間引入不同的旋轉(zhuǎn)控制力。仿真結(jié)果表明,改進(jìn)的人工勢(shì)場(chǎng)法規(guī)劃的路徑更短、更平滑,沒(méi)有大角度轉(zhuǎn)彎和反復(fù)振蕩的情況,且計(jì)算效率提高了33%。

航空運(yùn)輸; 改航路徑規(guī)劃; 人工勢(shì)場(chǎng)法; 多航空器

0 引言

導(dǎo)致航班延誤的因素有很多,其中不利于飛行的天氣,如大霧、雷暴、積冰等是造成航班延誤的主要原因。根據(jù)民航局公布的資料統(tǒng)計(jì),由于天氣原因造成的機(jī)場(chǎng)或空域容量急劇下降而直接或間接導(dǎo)致航班延誤的比例約占不正常航班的三分之一。

當(dāng)出現(xiàn)惡劣天氣時(shí),實(shí)施改航策略是減少航班延誤的一種有效途徑,改航策略是航班臨時(shí)選擇一條不受影響的航線繞過(guò)飛行受限區(qū)域,航班改航路徑規(guī)劃是改航策略的一個(gè)關(guān)鍵問(wèn)題。國(guó)外對(duì)該領(lǐng)域的研究已有十幾年的時(shí)間,具有代表性的算法主要有:基于網(wǎng)格的改航路徑規(guī)劃法[1];基于多邊形的改航路徑規(guī)劃法[2];基于標(biāo)準(zhǔn)進(jìn)離場(chǎng)程序的改航路徑規(guī)劃法[3];基于自由飛行的改航路徑規(guī)劃法[4]。我國(guó)對(duì)于改航問(wèn)題的研究開始于2000年,目前仍處于研究的初級(jí)階段。我國(guó)學(xué)者從2001年開始對(duì)航班改航路徑規(guī)劃問(wèn)題進(jìn)行研究,提出了基于已有航路點(diǎn)的A*搜索算法[5];文獻(xiàn)[6]提出了基于幾何算法的改航路徑規(guī)劃方法,該方法考慮了最短航段距離、轉(zhuǎn)彎角度和轉(zhuǎn)彎點(diǎn)數(shù)量等因素對(duì)改航路徑的影響;文獻(xiàn)[7]考慮了多個(gè)限制因素,建立了基于人工勢(shì)場(chǎng)算法的動(dòng)態(tài)改航路徑規(guī)劃模型,實(shí)現(xiàn)了改航路徑的快速實(shí)時(shí)規(guī)劃。這些研究只考慮了單航空器(也稱單機(jī))改航路徑的規(guī)劃,在實(shí)際運(yùn)行中,惡劣天氣勢(shì)必影響多個(gè)航空器的正常運(yùn)行,因此,不僅要考慮航空器避讓惡劣天氣,也要分析航空器之間的飛行沖突。針對(duì)這一問(wèn)題,本文研究了惡劣天氣下的多航空器改航路徑規(guī)劃與優(yōu)化。

1傳統(tǒng)人工勢(shì)場(chǎng)法的多機(jī)改航路徑

規(guī)劃

采用傳統(tǒng)人工勢(shì)場(chǎng)法建立人工勢(shì)場(chǎng)模型時(shí),航空器被簡(jiǎn)化為一個(gè)質(zhì)點(diǎn),在二維平面空間中運(yùn)動(dòng)[8]。航空器為了到達(dá)目標(biāo)點(diǎn)需要不斷地朝著目標(biāo)點(diǎn)運(yùn)動(dòng),目標(biāo)點(diǎn)對(duì)航空器產(chǎn)生了引力。同時(shí)航空器在飛行過(guò)程中需要避開受限空域和其他航空器,受限空域和其他各航空器對(duì)航空器產(chǎn)生了斥力,在斥力的作用下航空器始終與受限區(qū)和其他航空器保持一定的間隔,最終完成規(guī)避運(yùn)動(dòng)。航空器在運(yùn)動(dòng)空間中任意位置X=[x,y]T處的引力勢(shì)場(chǎng)函數(shù)為:

(1)

則吸引力是目標(biāo)引力勢(shì)函數(shù)的負(fù)梯度:

Fatt(X) =-grad[UA(X)]=λ(XA-X)

(2)

式中,λ為引力位置增益系數(shù);X為航空器當(dāng)前位置;XA=[xA,yA]T為目標(biāo)位置矢量;‖XA-X‖為航空器與目標(biāo)點(diǎn)間的歐氏距離。

將受限空域和其他航空器看作障礙物,其斥力勢(shì)函數(shù)定義為:

Urei(X)=

(3)

相應(yīng)的斥力為:

Frei(X) =-grad[Urei]

(4)

航空器在空域中所受合力為:

(5)

2改進(jìn)人工勢(shì)場(chǎng)法的多機(jī)改航路徑

規(guī)劃

傳統(tǒng)人工勢(shì)場(chǎng)法存在一些問(wèn)題:航空器所受的斥力和引力在一條直線上,航空器在改航期間出現(xiàn)合力為零,航空器無(wú)法避開障礙物,只能在一個(gè)范圍內(nèi)來(lái)回振動(dòng),即陷入局部最小值點(diǎn)。為解決該問(wèn)題,采用附加一個(gè)變化的控制力。在航空器之間避讓沖突的情形中,在目標(biāo)航空器周圍構(gòu)筑逆時(shí)針?lè)较虻男D(zhuǎn)力代替斥力,航空器在避讓危險(xiǎn)天氣的過(guò)程中通常是保持在危險(xiǎn)天氣的一定距離之外繞飛,在受限區(qū)域周圍構(gòu)造旋轉(zhuǎn)力場(chǎng)和斥力場(chǎng),航空器在旋轉(zhuǎn)力場(chǎng)和斥力場(chǎng)共同作用形成的復(fù)合人工勢(shì)場(chǎng)中尋找從初始位置到達(dá)目標(biāo)位置的無(wú)碰撞路徑。

2.1 改進(jìn)人工勢(shì)場(chǎng)法

本文對(duì)航空器的受力情況進(jìn)行調(diào)整,在目標(biāo)航空器周圍構(gòu)筑逆時(shí)針?lè)较虻男D(zhuǎn)力代替斥力。

航空器i與j的避讓過(guò)程中,航空器i所受的旋轉(zhuǎn)力Frot為:

(6)

式中,krot為旋轉(zhuǎn)力增益系數(shù);rij=[(xi-xj)2+(yi-yj)2]1/2是航空器i和j之間的距離;rj為航空器j的保護(hù)區(qū)半徑;ρroj為航空器j的旋轉(zhuǎn)力勢(shì)場(chǎng)半徑;ρrot為航空器的旋轉(zhuǎn)力場(chǎng)影響的最大范圍。

假設(shè)惡劣天氣的受限區(qū)為橢圓形,其斥力勢(shì)函數(shù)定義為:

Ureo(qi,X)=

(7)

相應(yīng)的斥力為:

Freo(qi,X)=

(8)

式中,kreo為受限區(qū)斥力的增益系數(shù);XR(x0,y0)為橢圓形危險(xiǎn)天氣區(qū)域的中心;ρ(qi,X)為航空器i到橢圓的距離;rreo為橢圓圓心與航空器i的連線上,圓心到橢圓邊界的長(zhǎng)度;ρreo為受限區(qū)斥力場(chǎng)影響的最大距離范圍。

受限區(qū)的旋轉(zhuǎn)力為:

(9)

式中,ρro為受限區(qū)旋轉(zhuǎn)力場(chǎng)半徑;kro為受限區(qū)的旋轉(zhuǎn)力增益系數(shù)。這樣,在多航空器系統(tǒng)中,航空器i所受的合力為:

Frot(qi,qj)+Fro(qi,X)]

(j=1,…,m;i≠j)

(10)

以上建立了多航空器避讓危險(xiǎn)天氣時(shí)的模型,需要注意的是:在計(jì)算勢(shì)場(chǎng)力Fatt,Freo,Frot,Fro時(shí),增益系數(shù)katt,kreo,krot,kro的值決定了勢(shì)場(chǎng)力的大小,進(jìn)而決定了航空器運(yùn)動(dòng)的方向。

2.2 改進(jìn)人工勢(shì)場(chǎng)法的改航路徑規(guī)劃步驟

步驟1:為規(guī)劃選定模型參數(shù),包括航空器數(shù)量I、航空器i的起始點(diǎn)Oi(x0,y0)、終點(diǎn)Ti(xt,yt)、受限區(qū)中心位置Obs(x0,y0)、受限區(qū)的橢圓方程參數(shù)a,b以及ρreo,ρro,ρrot,katt,kreo,krot,kro,還有移動(dòng)步長(zhǎng)l和最大運(yùn)行步數(shù)J,按運(yùn)動(dòng)空間的信息建立人工勢(shì)場(chǎng)模型;

步驟2:確定運(yùn)行步數(shù)j(初始步數(shù)為1),將第j步航空器i的當(dāng)前位置坐標(biāo)Xi(xj,yj)存入二維數(shù)組Currenti(xj,yj);

步驟3:分析航空器、受限區(qū)以及目標(biāo)點(diǎn)的相對(duì)位置,分別計(jì)算每一架航空器所受的引力Fatt,斥力Freo,旋轉(zhuǎn)力Frot,Fro,并表示為分別沿x軸和y軸方向的分量;

步驟4:計(jì)算每一架航空器所受的勢(shì)場(chǎng)力的合力F(x,y),航空器從點(diǎn)Xi(xj,yj)沿合力方向以固定步長(zhǎng)l移動(dòng)到下一航路點(diǎn)next(xj+1,yj+1),點(diǎn)的計(jì)算如下:

next(xj+1,yj+1)=Xi(xj,yj)+lF

(11)

步驟5:移動(dòng)航空器到點(diǎn)next(xj+1,yj+1),置j+1點(diǎn)為當(dāng)前點(diǎn),j=j+1,xj=xj+1,yj=yj+1;

步驟6:判斷航空器是否到達(dá)目標(biāo)區(qū)域,如果距離目標(biāo)區(qū)域的距離小于預(yù)設(shè)的閾值(通常為移動(dòng)步長(zhǎng)的整數(shù)倍),航空器到達(dá)目標(biāo)區(qū)域,結(jié)束改航路徑規(guī)劃,輸出數(shù)組Currenti從而生成完整的改航路徑,任務(wù)完成;否則轉(zhuǎn)步驟2繼續(xù)計(jì)算,或者直到步數(shù)j大于設(shè)定的最大步數(shù)J,無(wú)法找到完整路徑,說(shuō)明模型參數(shù)選擇不合適,需要改變參數(shù)重新規(guī)劃。

3 仿真計(jì)算

算例為8架航空器,四對(duì)同高度迎頭飛行,航空器的初始狀態(tài)為表1,航空器預(yù)計(jì)飛行航路和狀態(tài)如圖1所示。航空器在飛行中不僅要繞飛天氣,同時(shí)還必須避讓對(duì)向的航空器,且由于改航過(guò)程中需要占用側(cè)向間隔,相鄰兩架航空器的飛行沖突問(wèn)題也要加入考慮之中。

表1 航空器初始狀態(tài)Table 1 Initial state of the aircraft

圖1 航空器預(yù)計(jì)飛行航路和狀態(tài)Fig.1 Estimated flight path and state of the aircraft

首先通過(guò)傳統(tǒng)人工勢(shì)場(chǎng)法作改航路徑的規(guī)劃,各參數(shù)的設(shè)置如下:勢(shì)場(chǎng)范圍ρreo=20 km,ρro=50 km,ρrea=20 km;勢(shì)場(chǎng)力增益系數(shù)katt=15,kreo=150,krea=170,kro=15。經(jīng)MATLAB計(jì)算得到的改航路徑如圖2所示。

傳統(tǒng)人工勢(shì)場(chǎng)法可以規(guī)劃出符合間隔標(biāo)準(zhǔn)的改航路徑,其中航空器與危險(xiǎn)天氣的間隔保持在10 km以上;航空器之間的最小間隔為7.863 km,大于最低間隔標(biāo)準(zhǔn)的6 km。但是由于多航空器復(fù)雜沖突的存在,傳統(tǒng)人工勢(shì)場(chǎng)法生成的改航路徑非常曲折,包括多處180°以上的大轉(zhuǎn)彎;航空器飛行相當(dāng)長(zhǎng)一段距離后方能到達(dá)目標(biāo)地點(diǎn),特別是迎頭飛行的航空器遭遇之后經(jīng)過(guò)長(zhǎng)時(shí)間的振動(dòng)方得解脫;改航路徑在實(shí)際工作中是不可接受的。此外,整個(gè)仿真的迭代步數(shù)達(dá)到了300步以上,主要原因就是迎頭遭遇的航空器在振動(dòng)過(guò)程中消耗了大量步數(shù),造成計(jì)算資源的浪費(fèi),降低了仿真計(jì)算的效率。

圖2 傳統(tǒng)人工勢(shì)場(chǎng)法規(guī)劃的改航路徑 Fig.2 Rerouting path of traditional artificial potential field

采用前面提出的改進(jìn)人工勢(shì)場(chǎng)法解決上述問(wèn)題。由于航空器之間用旋轉(zhuǎn)力代替排斥力,所以將航空器斥力勢(shì)場(chǎng)ρrea變?yōu)樾D(zhuǎn)力勢(shì)場(chǎng)ρrot=20 km,航空器斥力增益系數(shù)krea變?yōu)樾D(zhuǎn)力增益系數(shù)krot=20,其他參數(shù)不變,通過(guò)仿真計(jì)算得到的改航路徑如圖3所示。

圖3 改進(jìn)人工勢(shì)場(chǎng)法規(guī)劃的改航路徑Fig.3 Rerouting path planned by improved artificial potential field

改進(jìn)人工勢(shì)場(chǎng)法規(guī)劃出的改航路徑較傳統(tǒng)方法規(guī)劃出的路徑更短,各航空器的航跡也更為平滑,沒(méi)有出現(xiàn)大角度轉(zhuǎn)彎的情況;迎頭相遇的各航空器都能很好地進(jìn)行避讓,沒(méi)有出現(xiàn)反復(fù)振蕩的情況,航空器之間的嚴(yán)重沖突得以避免。航空器與危險(xiǎn)天氣的距離均大于10 km,航空器之間最小間隔為6.729 km,符合最低間隔標(biāo)準(zhǔn)。此外,采用改進(jìn)人工勢(shì)場(chǎng)法的迭代步數(shù)均小于200,說(shuō)明對(duì)人工勢(shì)場(chǎng)法的改進(jìn)節(jié)約了計(jì)算時(shí)間,計(jì)算效率提高了33%,可見本文提出的改進(jìn)人工勢(shì)場(chǎng)法能夠克服傳統(tǒng)方法的一些不足之處,適用于多航空器改航的路徑規(guī)劃問(wèn)題。

4 結(jié)束語(yǔ)

本文采用改進(jìn)人工勢(shì)場(chǎng)法對(duì)多航空器改航路徑進(jìn)行了規(guī)劃,解決了傳統(tǒng)方法中航空器受力局部最小值的問(wèn)題,仿真了航空器迎頭沖突的情景。結(jié)果表明,改進(jìn)人工勢(shì)場(chǎng)法規(guī)劃的路徑更短、更平滑,沒(méi)有大角度轉(zhuǎn)彎和反復(fù)振蕩的情況。在此基礎(chǔ)上,利用空管運(yùn)行中的氣象和空域數(shù)據(jù)驗(yàn)證理論方法的實(shí)用性,是下一步研究的主要內(nèi)容。

[1] Dixon M,Weiner G.Automated aircraft routing through weather-impacted airspace[C]//5th International Conference on Aviation Weather Systems.Vienna,VA,1993:295-298.

[2] Sridhar B,Chatterji G B,Grabbe S,et al.Integration of traffic flow management decisions[C]//AIAA Guidance,Navigation,and Control Conference.Monterey,Cal,2002:1-9.

[3] Krozel J,Penny S,Prete J,et al.Automated route generation for avoiding deterministic weather in transition airspace[J].Journal of Guidance,Control,and Dynamics,2007,30(1):144-153.

[4] Balen C H,Bil C.Optimal re-routing of aircraft around closed airspace in free flight[C]//AIAA Modeling and Simulation Technologies Conference.Honolulu,HI,2008:1-10.

[5] 宋柯.空中交通流量管理改航策略初步研究[D].南京:南京航空航天大學(xué),2002.

[6] 李雄,徐肖豪,朱承元,等.基于幾何算法的空中交通改航路徑規(guī)劃研究[J].系統(tǒng)工程,2008,26(8):37-40.

[7] 徐肖豪,李成功,趙嶷飛,等.基于人工勢(shì)場(chǎng)算法的改航路徑規(guī)劃[J].交通運(yùn)輸工程學(xué)報(bào),2009,9(6):64-68.

[8] 況菲,王耀南,張輝.動(dòng)態(tài)環(huán)境下基于改進(jìn)人工勢(shì)場(chǎng)的機(jī)器人實(shí)時(shí)路徑規(guī)劃仿真研究[J].計(jì)算機(jī)應(yīng)用,2005,25(10):2415-2417.

(編輯：方春玲)

Multi-aircraftreroutingpathplanningbasedonimprovedartificialpotentialfieldalgorithm

WANG Xing-long, XU Xiao-hao, FENG Jiang-ran

(Research Base of Air Traffic Management, Civil Aviation University of China, Tianjin 300300, China)

Severe weather is the main cause for the delay of transport aircraft, rerouting strategy is an effective way to reduce delays, multi-aircraft path planning is the key point for rerouting. For many flights delay caused by severe weather, this paper presents artificial potential field method for multi-aircraft rerouting path planning. Traditional artificial potential field model is established according to the aircraft by gravity force and repulsion force, and different rotation control force between aircraft and aircraft, aircraft and severe weather is introduced to avoid local minimum value during rerouting. Simulation result shows that the path planned by improved artificial potential field method is shorter and smoother, and no large angle turning and repeated shocks, and the computational efficiency is improved by 33%.

air transportation; rerouting path planning; artificial potential field; multi-aircraft

V355

A

1002-0853(2013)04-0381-04

2013-01-15;

2013-04-01; < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間:2013-06-06 12:25

國(guó)家自然科學(xué)基金資助(61039001，60972006)；中央高?？蒲谢鹳Y助(ZXH2011D010)

王興隆(1979-)，男，黑龍江北安人，助理研究員，研究方向?yàn)榭罩薪煌ü芾怼?/p>