基于總體沖突概率和三維布朗運動的沖突探測算法

石 磊吳仁彪黃曉曉

①(中國民航大學智能信號與圖像處理天津市重點實驗室 天津 300300)

②(天津大學電子信息工程學院 天津 300072)

基于總體沖突概率和三維布朗運動的沖突探測算法

石 磊①②吳仁彪*①黃曉曉①

①(中國民航大學智能信號與圖像處理天津市重點實驗室 天津 300300)

②(天津大學電子信息工程學院 天津 300072)

隨著空中交通流量的增加，沖突探測在空中交通管理系統中的作用越來越重要。該文提出了一種概率型沖突探測算法，計算向前看時間內的總體沖突概率?；陲w機3維布朗運動模型，飛機的預測航跡可以表示為確定航跡外加布朗運動擾動。對于兩飛機速度為常值的運動情況，沖突概率可以表示為做布朗運動的飛機進入運動的飛機保護區的概率，使用坐標變換和Bachelier-Levy定理進行估計；對于兩飛機運動為非勻速運動情況，預測航跡則可以使用足夠多速度為分段常值的片段來近似，計算出每一片段內的沖突概率，并給出了向前看時間內總體沖突概率的上下界。與蒙特卡羅仿真結果比較，算法滿足沖突探測精度要求，對及時發現沖突和沖突解決具有重要意義。

空中交通管理系統；總體沖突概率；3維布朗運動；坐標變換；Bachelier-Levy定理

1 引言

空中交通管理的基本要求是保證飛行的安全?？沼蛑酗w行的安全是以飛機之間發生沖突的次數來衡量的。當飛機之間的距離小于等于最小安全間隔時則認為發生飛行沖突[1]。最小安全間隔分為最小水平間隔和最小垂直間隔，它們構成了一個以飛機為中心的圓柱形保護區。航路區的最小水平間隔為9.3 km，終端區的最小水平間隔為5.6 km。在未實行縮小最小垂直間隔(RVSM)之前，飛機飛行高度在8.8 km以上時，最小垂直間隔為610 m，飛機飛行高度在8.8 km以下時，最小垂直間隔為305 m[2]；實行RVSM之后，最小垂直間隔標準均為305 m。

隨著民用和通用航空運輸業的快速發展，空域中飛行密度大大增加，如何高效地利用有限空域并保證飛行安全成了空中交通管理系統的一個巨大挑戰。飛行沖突探測成為了空中交通管理系統保障飛行安全高效的一個重要工具。飛行沖突探測的基本思路就是利用雷達數據、ADS-B數據以及交通管制信息等，提前探測出可能的飛行沖突，并給予管制員提示，讓管制員有足夠的時間通知飛行員來避免飛行沖突的發生。

飛行沖突探測包括確定型沖突探測和概率型沖突探測[3]。確定型沖突探測根據飛機當前位置和速度不考慮其它因素的影響預測飛機未來航跡并進行沖突判斷，而概率型沖突探測則考慮飛機受到導航、跟蹤控制精度以及風等因素影響，預測航跡具有不確定性，從而導致沖突結果為概率。關于概率型沖突探測，國內外研究者進行了一系列的研究。Prandini等人[4,5]提出了計算飛行沖突概率的隨機化方法；劉小龍等人[6]提出了一種改進的Prandini概率型沖突探測算法，提高了運算效率；梁海軍等人[7]提出了3維坐標系下的沖突探測算法，使用蒙特卡羅方法計算沖突概率并分析了一系列參數對沖突概率的影響；文獻[8]提出了基于位置空間離散化思想的快速算法來計算沖突概率；文獻[9]提出了基于航跡預測的位置預測模型，使用概率分布函數估計法估計沖突概率。以上方法基于瞬時沖突概率，瞬時沖突概率反映了在某一時刻兩飛機沖突的可能性，并不能直接代表一段時間內兩飛機沖突的可能性，并且瞬時沖突概率對于兩飛機預測航跡誤差較為敏感，當預測航跡誤差協方差很大時，沖突概率會變小，有可能導致漏警。而總體沖突概率則是向前看時間內兩飛機沖突的概率，更能反映兩飛機在向前看時間內沖突的可能性。文獻[10]提出了自由飛行情況下飛機航跡預測模型，使用不同的概率密度描述飛機動態參數，并使用蒙特卡羅方法求解沖突概率；文獻[11]使用多級分解以及序貫蒙特卡羅的方法計算沖突概率，來減小計算量。不過蒙特卡羅方法計算量依然較大，不太適合于工程應用。文獻[2,12]提出了飛機位置預測誤差模型以及一種估計方法求沖突概率，適用于航路上勻速飛行的飛機，但并不適合飛機飛行狀態改變的情況。文獻[5,13]提出了基于布朗運動的沖突探測算法，求向前看時間內的沖突概率；李丹等人[14]對基于布朗運動的方法進行改進用于減小誤警率，不過文獻[5,13,14]提出的沖突探測算法僅僅適用于2維空間兩飛機勻速直線運動的情況，對于3維空間中飛機改變飛行方向等情況則不適用。

針對上述問題，本文提出了一種基于總體沖突概率思想的沖突探測算法，適用于3維空間中飛機運動不僅僅為勻速直線運動的情況，并提出了一種沖突概率的估計方法。飛機運動模型基于3維布朗運動，飛機沖突概率可以表示為做布朗運動的飛機進入運動的飛機保護區的概率。對于兩飛機相對運動為勻速直線運動情況(相對速度為常值)，使用坐標變換和Bachelier-Levy定理來估算沖突概率。對于相對運動為非勻速直線運動的情況，則可以使用足夠多相對速度為分段常值的片段來近似，求出每一片段的沖突概率，則向前看時間內總體沖突概率上下界可以由每個片段的沖突概率給出。

2 飛行沖突概率模型

2.1 飛機運動模型

本節建立飛機運動模型，預測在[0,T]時間段內的飛機航跡，其中T為向前看時間。建立以xyz為坐標軸的慣性坐標系，其中xy為水平面坐標軸，z為垂直方向坐標軸。

飛機在飛行中會受到風等一系列不確定因素的影響。這些因素對飛機地面速度dX(t)/dt 的擾動可以認為呈高斯分布[5,13]，即

其中()tX和()tu為t時刻飛機的位置和空速，()tω為高斯分布的隨機變量?？紤]飛機在3維空間中飛行，t時刻飛行方向在水平面的投影與慣性坐標系x軸正向夾角為()tθ，則飛機位置()tX可以用隨機微分方程表示。

其中B(t)為標準布朗運動；Σ=diag(σa,σc,σv)，其中,,分別是飛機水平航向、水平側向和垂直方向速度擾動的功率譜密度。R(θ(t))為t時刻的旋轉矩陣，由于風對飛機水平速度和垂直速度影響可以認為是獨立的，因此R(θ(t))為[12]

2.2 飛機速度為常值時的沖突概率

不妨考慮飛機A和B，其中飛機A在0t=時刻位于慣性坐標系原點，飛機B在=0t時刻位于0Δx。飛機A速度為Au，速度矢量在水平面投影平行于x軸正向；飛機B速度為Bu，速度矢量在水平面投影與x軸正向夾角為θ，則兩飛機位置()AtX和()BtX可以表示為

其中()AtB和()BtB分別為標準布朗運動，2Σ為飛機速度擾動的功率譜密度，()θR為飛機B的旋轉矩陣。

兩飛機相對位置()tΔX可以由式(4)可得

其中ΔX(t)=XB(t)-XA(t), Δu=uB-uA, n(t )=R(θ)ΣBB(t)-ΣBA(t )。

假設兩飛機在向前看時間[0,]T內發生沖突的事件為(0,)TC，則

其中A

D是由最小安全間隔構成的以飛機A為中心的圓柱形保護區，保護區半徑為r，高度為h。

兩飛機沖突概率CP為事件(0,)TC發生的概率，即

2.3 飛機速度為分段常值函數時的沖突概率

對于飛機進行轉彎等非勻速直線運動，可以使用足夠數量的勻速直線運動片段來近似，即速度為分段常值函數。假設飛機A和B速度矢量為uA(t)和uB(t)，兩飛機位置XA(t)和XB(t)可以使用隨機微分方程來表示。

兩飛機相對位置ΔX(t )可以由式(8)得到。

其中ΔX(t)=XB(t)-XA(t ),Δu(t)=uB(t)-uA(t )。

由于飛機A和B的速度為分段常值函數，因此將兩飛機各段速度的起始和終點時刻TiA和TjB按照從小到大進行排序可得Tk，其中0≤k≤l,l為合并后速度片段的個數。則

其中T0=0并且Tl=T,Δuk為[Tk,Tk+1)時間段的相對速度矢量，為常值矢量。

假設在t∈[Tk,Tk+1)時間段內，兩飛機發生沖突的事件為C(Tk,Tk+1)，則

假設兩飛機在向前看時間[0,]T內發生沖突的事件為(0,)TC，則

因此，兩飛機沖突概率CP可以定義為

為了表述方便，令Ck=C(Tk,Tk+1)。由概率論基本知識可得

對于兩飛機相對飛行路線分為多個片段的情況，一般在兩飛機飛行路線交叉的時間片段內沖突概率最大，并且其它時間片段內飛行沖突概率很小，因此可以使用兩飛機飛行路線交叉的時間片段內的總體沖突概率來衡量兩飛機在向前看時間內的沖突可能性，即PC≈max(P(Ci))。

3 沖突概率估計算法

3.1 飛機速度為常值時沖突概率的估計

由式(5)可知飛機A在原點做隨機運動n(t)，飛機B以Δx0為起點做速度為Δu的運動。兩飛機沖突概率則可以看作在原點做隨機運動的飛機A進入運動的飛機B保護區的概率，假設飛機B運動著的保護區為，則兩飛機沖突概率為

對于式(15)可以使用蒙特卡羅方法進行計算，但計算量很大，這里給出一種方法估計PC的值[15]。

(1)非正交變換 由于n(t)=R(θ)ΣBB(t) -ΣBA(t)，并且假定BA(t)和BB(t)是不相關的，隨機運動n(t)的協方差為

隨機運動n(t)可以通過非正交變換矩陣L-1變為標準的布朗運動(t)，即

由式(16)和式(17)可得

矩陣L的具體計算見文獻[15]。

式(5)兩邊乘以矩陣1-L得

將隨機運動n(t)變換為標準布朗運動n(t)后，進行正交變換使得相對速度v的方向與坐標系某一個坐標軸平行。

(2)正交變換 建立以z1z2z3為坐標軸的慣性坐標系，其中z1z2軸組成水平面，z3軸垂直于水平面向上。為了便于計算沖突概率，需要正交變換將相對速度矢量v=[v,v,v]T旋轉到與z坐標軸平行。

1231其中正交變換包括水平旋轉和垂直旋轉，具體計算見文獻[15]。

假設水平旋轉和垂直旋轉的矩陣分別為R1和 R2，則經過兩次旋轉變換，式(19)變為

其中z(t)=R2R1ΔZ(t ), a=R2R1Δz0,ω=R2R1v ，標準布朗運動(t)對于旋轉變換R2R1是不變的。

(3)沖突概率的估計 令Mt為飛機B經過非正交和正交變換后的保護區。由式(20)可知，變換后的保護區是以a為起點，速度為ω進行勻速運動的一個橢圓柱體，如圖1所示。

圖1 經過非正交和正交變換后的保護區

此時兩飛機沖突概率CP表達式變為

沖突概率PC可以看作一個在原點開始的標準布朗運動(t)進入一個初始位置在a速度為ω的運動橢圓柱保護區的概率。

在圖1中，pt是經過保護區Mt的中心且垂直于相對速度ω的平面。是保護區Mt在pt平面的投影，為不規則的形狀，St是邊長分別平行于z2和z3軸的包含的最小矩形，如圖2所示。其中Δz2和Δz3分別是St兩邊邊長的一半。

圖2 非正交和正交變換后的保護區在tp平面的投影

針對式(21)中PC的計算，本文提出了一種估計方法。當標準布朗運動n(t)首次擊中運動著的平面pt，其落在矩形St內的概率是對PC很好的估計。

令初始位置a的坐標值為(a1,a2,a3)T，速度ω大小為ω，則基于Bachelier-Levy定理，n(t)首次擊中運動著的平面pt的概率密度函數為

那么沖突概率CP的估計表達式為

其中P(z(τ)∈St|τ=t )是t時刻布朗運動n(t)擊中平面pt時候在矩形St內的概率。當τ=t時刻，標準布朗運動(t)在平面pt內呈2維高斯分布，其均值是0，方差為tI2。則P(z(τ)∈St|τ=t)可以表示為

其中

有關2zΔ和3zΔ的計算見文獻[15]。

首中時間τ的均值為

由于首中時間τ的概率密度集中于t0:=E[τ]附近，因此對P(z(τ)∈St|τ=t)在t0處進行0階泰勒展開，即可獲得很高的估計精度[16]，則得

其中()Qx見式(25)。

由式(27)和式(28)可得

3.2 兩飛機速度為分段常值函數情況下沖突概率的估計

計算兩飛機在速度為分段常值情況下的沖突概率，需要計算沖突事件C(Tk,Tk+1)的概率。由式(11)可知，事件C(Tk,Tk+1)表示在t∈[Tk,Tk+1)時間段內，兩飛機相對位置在飛機A保護區DA內的事件。

由式(2)可知，在Tk時刻兩飛機相對位置服從高斯分布，假設均值為Δxk，協方差為ΣTk，如圖3所示。我們將相對位置Δxk以t∈[Tk,Tk+1)時間段內的速度Δuk按照時間向前線性逆推到0時刻得Δ。起始位置為Δ的布朗運動在T時刻的位置k服從均值為Δx協方差為的高斯分布。相對速

圖3 相對飛行速度為兩段情況下兩飛機相遇幾何

k度Δuk與前一段的相對速度Δuk-1速度方向改變不大時，協方差和相差不大，并且對于求t∈[Tk,Tk+1)一段時間內的沖突概率來說，Tk時刻相對位置協方差對求[Tk,Tk+1)時間段內總體沖突概率影響并不大，影響其概率的是兩飛機在[Tk,Tk+1)時間段內的最小距離以及到達最小距離的時刻。

因此求P(C(Tk,Tk+1))可以使用式(23)，不過對時間的積分上下限需要變為Tk+1和Tk，即

由式(27)和式(29)得

由式(31)和式(14)可以求出向前看時間段[0,]T內沖突概率CP的上限值和下限值。

4 仿真與分析

4.1 飛機速度為常值情況下的仿真

設置向前看時間為10 min，圓柱形保護區半徑為5.6 km，高度為610 m。考慮兩架飛機A和B，其中飛機A初始位置為坐標系原點，速度A=u (123.5,0,0)Tm/s，飛機B的初始位置為Δ，速度為uB，其水平速度大小為154.3 m/s，垂直速度為7.6 m/s，飛機B水平速度方向與坐標系x軸正向夾角為θ。如圖4所示。

圖4 兩飛機相遇幾何

改變0Δx和θ值，使得兩飛機最小距離、到達最小距離時刻以及水平面上相遇角度不同，在這些情況下，本文算法求出的沖突概率與蒙特卡羅仿真結果的誤差如表1所示。

其中使用蒙特卡羅仿真次數105次。本文計算結果平均絕對誤差小于0.01，最大絕對誤差為0.042，滿足沖突探測對精度的要求[2]。最大絕對誤差出現在兩飛機水平速度夾角較小并且兩飛機最小距離是保護區半徑5.6 km時，原因是飛行速度夾角較小時，兩飛機位置的布朗運動相關性大，而本文忽略兩飛機位置布朗運動的相關性。

4.2 飛機速度為分段常值情況下的仿真

設置向前看時間為10 min，圓柱形保護區半徑為5.6 km，高度為610 m?？紤]兩架飛機A和B在同一水平面內飛行，其中飛機A初始位置為坐標系原點，速度Au大小為123.5 m/s，速度方向與x軸正向夾角為60°，預計飛行3 min后，速度大小不變，但速度方向與x軸正向夾角變為30°。飛機B的初始位置為(35.7,0,T0)km，飛行速度Bu大小為123.5 m/s，速度方向與x軸正向夾角為132°，預計兩飛機在第4 min到達最小距離且最小距離為0。這里設置飛機B在第2 min進行水平協調轉彎改變飛行速度方向，轉彎率為2.5/s°，其中可以進行右轉彎或者左轉彎，轉過一定角度后繼續直線飛行，如圖5所示。

表1 本文結果與蒙特卡羅仿真結果的誤差

圖5 兩飛機相遇幾何

本文分別仿真飛機B向左或者向右轉彎角度為5°至50°的情況。本文中將轉彎分為兩個直線片段來近似，則這種情況下兩飛機相對飛行路線可以分為5段，分別是0時刻至飛機B開始轉彎的時間片段([0,2] min)，轉彎2個時間片段，轉彎后至飛機A改變飛行速度方向的時間片段以及飛機A改變飛行速度方向后至向前看時間的片段([3,10] min)。

前4個時間片段，兩飛機最近距離遠大于5.6 km，求出的兩飛機沖突概率為0。在[3,10] min片段內，也即兩飛機飛行路線交叉片段，兩飛機最近距離隨著轉彎角度的變大而從0變大。兩飛機飛行路線交叉時間段[3,10] min內的沖突概率本文算法和蒙特卡羅仿真結果如圖6所示。

其中使用蒙特卡羅仿真次數為510次，本文結果與蒙特卡羅仿真結果最大絕對誤差為0.034。平均絕對誤差小于0.01。當飛機B向左或者向右轉彎40°時，兩飛機預計最小距離為7.6 km和8.5 km，兩飛機沖突概率均小于0.05，則一定程度上可以認為沒有沖突。

圖6 飛行路線交叉片段的沖突概率

5 結論

本文根據飛機布朗運動模型和總體沖突概率思想提出了一種適用于3維空間中飛機運動不僅僅為勻速直線運動情況下的沖突探測算法。對于飛機速度為常值情況，使用坐標變換和Bachelier-Levy定理來估算沖突概率。對于飛機速度是分段常值情況，求出了每個時間片段內的沖突概率并給出了向前看時間內沖突概率的上下限。仿真結果驗證了本文算法的精度滿足沖突探測精度的要求，對空中交通管理系統發現沖突以及進行沖突解決有重要意義。

[1] Federal Aviation Administration. Aeronautical information manual-official guide to basic flight information and ATC procedures[R]. Washington, D.C., 2012.

[2] Paielli R A and Erzberger H. Conflict probability estimation for free flight[J]. Journal of Guidance, Control and Dynamics, 1997, 20(3): 588-596.

[3] Kuchar J and Yang L. A review of conflict detection and resolution modeling methods[J]. IEEE Transactions on Intelligent Transportation Systems, 2000, 1(4): 179-189.

[4] Prandini M, Lygeros J, Nilim A, et al.. Randomized algorithms for probabilistic aircraft conflict detection[C]. Proceedings of the 38th IEEE Conference on Decision and Control, Berkeley, CA, USA, 1999, 3: 2444-2449.

[5] Prandini M, Hu J, Lygeros J, et al.. A probabilistic approach to aircraft conflict detection[J]. IEEE Transactions on Intelligent Transportation Systems, 2000, 1(4): 199-220.

[6] 劉小龍, 羅以寧, 趙喜求, 等. 一種改進的Prandini概率型中期沖突探測方法[J]. 計算機技術與發展, 2013, 23(1): 214-216. Liu Xiao-long, Luo Yi-ning, Zhao Xi-qiu, et al.. An improved medium-term conflict detection methods of Prandini probability type[J]. Computer Technology and Development, 2013, 23(1): 214-216.

[7] 梁海軍, 楊紅雨, 肖朝, 等. 3維坐標系下的飛行沖突探測算法[J]. 四川大學學報(工程科學版), 2013, 45(2): 88-93. Liang Hai-jun, Yang Hong-yu, Xiao Chao, et al.. Flight conflict detection algorithm based on the three dimensional coordinate system[J]. Journal of Sichuan University (Engineering Science Edition), 2013, 45(2): 88-93.

[8] 石磊, 吳仁彪. 預測位置空間離散化的多航路中期沖突探測算法[J]. 信號處理, 2012, 28(11): 1521-1528. Shi Lei and Wu Ren-biao. Multi-route mid-term conflict detection algorithm based on discretization of predicted position space[J]. Signal Processing, 2012, 28(11): 1521-1528.

[9] Liu W and Hwang I. Probabilistic trajectory prediction andconflict detection for air traffic control[J]. Journal of Guidance, Control, and Dynamics, 2011, 34(6): 1779-1789.

[10] Yang L and Kuchar J. Prototype conflict alerting system for free flight[J]. Journal of Guidance, Control, and Dynamics, 1997, 20(4): 768-773.

[11] Prandini M and Watkins O. Probabilistic Aircraft Conflict Detection[R]. Distributed Control and Stochastic Analysis of Hybrid Systems Supporting Safety Critical Real-Time Systems Design (HYBRIDGE), 2005.

[12] Paielli R and Erzberger H. Conflict probability estimation generalized to non-level flight[J]. Air Traffic Control Quarterly, 1999, 7(3): 1-12.

[13] Hu J, Lygeros J, Prandini M, et al.. Aircraft conflict prediction and resolution using Brownian motion[C]. Proceedings of the 38th International Conference on Decision and Control, Berkeley, CA, USA, 1999: 2438-2443.

[14] 李丹, 崔德光. 基于布朗運動的空中交通短期沖突探測[J]. 清華大學學報(自然科學版), 2008, 48(4): 477-481. Li Dan and Cui De-guang. Air traffic control conflict detection algorithm based on Brownian motion[J]. Journal of Tsinghua University (Science & Technology), 2008, 48(4): 477-481.

[15] Shi Lei and Wu Ren-biao. A probabilistic conflict detection algorithm in terminal area based on three-dimensional Brownian motion[C]. Proceedings of the 11th International Conference on Signal Processing, Beijing, 2012: 2287-2291.

[16] Hu J. A study of conflict detection and resolution in free flight[D]. [Master dissertation], Berkeley: University of California, 1999.

石 磊： 男，1985年生，博士生，研究方向為飛行沖突探測等.

吳仁彪： 男，1966年生，教授，研究方向為自適應信號處理及其應用等.

黃曉曉： 女，1989年生，碩士生，研究方向為飛行沖突探測等.

Conflict Detection Algorithm Based on Overall Conflict Probability and Three Dimensional Brownian Motion

Shi Lei①②Wu Ren-biao①Huang Xiao-xiao①

①(Tianjin Key Laboratory for Advanced Signal Processing, Civil Aviation University of China, Tianjin 300300, China)
②(School of Electronic Information Engineering, Tianjin University, Tianjin 300072, China)

With the increasing of the air traffic flow, conflict detection plays an increasingly important role in air traffic management system. A probabilistic conflict detection algorithm is proposed. Overall conflict probability in look-ahead time is calculated. The aircraft predicted trajectory is expressed as deterministic trajectory plus a Brownian motion perturbation. For the case of constant aircraft speed, conflict probability is expressed as the probability of an aircraft with Brownian motion perturbation entering a time-varying moving protection zone, the probability is approximated using coordinate transformation and Bachelier-Levy theorem. For the case of aircraft with non-constant speed, predicted trajectory can be approximated by a large enough number of constant speed segments. Conflict probability of each segment is calculated and the overall conflict probability bounds in look-ahead time are given. Compared with Monte Carlo simulations, the proposed algorithm is accurate for conflict detection and it is useful to detect and avoid conflicts in air traffic management system.

Air traffic management system; Overall conflict probability; Three dimensional Brownian motion; Coordinate transformation; Bachelier-Levy theorem

TP391

A

1009-5896(2015)02-0360-07

10.11999/JEIT140363

2014-03-19收到，2014-09-17改回

國家科技支撐計劃(2011BAH24B12)和國家自然科學基金委員會與中國民航局聯合資助項目(U1233109)資助課題

*通信作者：吳仁彪 rbwu@cauc.edu.cn