基于ADS-B IN 的多機沖突解脫及路徑規(guī)劃*

姚 飛，王 軍，謝凱承，李廣春，單 嫻

（1.鄭州航空工業(yè)管理學院民航學院，鄭州 450046；2.鄭州航空工業(yè)管理學院大數(shù)據(jù)科學研究院，鄭州 450046；3.中國民用航空中南地區(qū)空中交通管理局河南分局流量管理室，鄭州 450000）

0 引言

隨著空中交通流量不斷增加，空域越來越擁擠，對航空器的防撞系統(tǒng)要求越來越高?，F(xiàn)今航空器的空中避撞主要通過空中交通防撞系統(tǒng)（Traffic Collision Avoidance System，TCAS）來實現(xiàn)。文獻［1］指出TCAS 雖然可以有效地進行沖突探測和提供解脫策略，但目前的TCAS 仍存在很多不足，例如探測范圍較近、探測目標有限、誤警率較高、僅提供垂直方向解脫策略，對于飛行流量較大的終端區(qū)或飛行航跡比較靈活的通航飛機，無法給出有效的沖突探測和路徑規(guī)劃。

由于采用大量先進的通信、導航與監(jiān)視設(shè)備，受空中復雜情況及氣象等要素約束，不僅需要飛行員與管制員協(xié)同配合，還需要航空器具備有效的沖突預測與解脫的能力。文獻［2-3］指出廣播式自動相關(guān)監(jiān)視（Automatic Dependent Surveillance-Broadcast，ADS-B）技術(shù)的不斷發(fā)展，尤其是空空監(jiān)視ADS-B IN 技術(shù)的發(fā)展，該技術(shù)能夠提供高精度、高更新率的信息，飛行駕駛員能及時掌握本機周圍大范圍多目標的交通態(tài)勢，可以在飛行規(guī)則允許范圍內(nèi)自主選擇飛行高度、路線和速度，減輕管制員的工作負荷，提高飛行效率和安全性。

根據(jù)民航局最新規(guī)劃，預計我國2025 年實現(xiàn)ADS-B IN 初始運行［4］。文獻［5］以位置誤差的概率統(tǒng)計特性，評估了當前ADS-B 運行間隔下的目標沖突和危險接近等碰撞風險。文獻［6］提出了基于ADS-B 技術(shù)的沖突探測系統(tǒng)的組成，但文章沒有闡述多機沖突解脫的具體方法。文獻［7］將ADS-B IN監(jiān)視范圍內(nèi)的區(qū)域劃分為26 個區(qū)域，每個區(qū)域由專門判別目標是否與本機相關(guān)的規(guī)則，計算和處理工作量較大。文獻［8］建立了幾何型沖突預測模型，并設(shè)計算法進行仿真計算，這種方法雖然比較簡單，但有一定的局限性，與傳統(tǒng)的TCAS 方法一樣。

目前沖突解脫模型主要集中在碰撞風險研究，未能進行航跡規(guī)劃和提供管制策略。文獻［9］以概率統(tǒng)計學為基礎(chǔ)研究航空器的碰撞風險。文獻［10］針對空中交通管制中的沖突探測與解脫問題，提出了一種幾何最優(yōu)的沖突探測與解脫方法。文獻［11］采用最優(yōu)控制理論和微分方程研究了固定航路條件下的多機沖突解脫問題，提出了改變航向的飛行策略。同時，針對上述問題國內(nèi)外學者提出了大量的算法，例如人工智能算法［12］、改進量子遺傳算法［13］、Swarm 方法和Steer 算法［14］、遺傳算法［15］、改進蟻群算法［16］、狼群算法［17］等。

針對沖突解脫模型研究主要分為幾何型和概率型兩大類，幾何型沖突探測算法是基于兩架飛機最近一段時間的位置與速度矢量進行航跡外推，再根據(jù)設(shè)定的保護區(qū)模型預測未來是否發(fā)生沖突，這種方法比較簡單但有一定的局限性，與傳統(tǒng)的TCAS 方法相同。本文通過深入分析機載TCAS 和ADS-B IN 技術(shù)的特點，借鑒國內(nèi)外自由飛行下利用隨機微分方程建立沖突模型的方法，假設(shè)飛行中不確定因素導致的誤差服從正態(tài)分布［18］，根據(jù)自由飛行下的碰撞風險設(shè)計適合機載設(shè)備和空管設(shè)備的沖突解脫與恢復算法，也為人工飛行解脫與恢復提供借鑒。

1 飛行沖突預測模型建立

通過空空監(jiān)視ADS-B IN 技術(shù)，機載計算機可以預測范圍更遠的航空器，并提前規(guī)劃出與周圍所有飛機都保持安全間隔的最優(yōu)飛行路徑，從而實現(xiàn)整個空域安全高效的自由飛行。航空器在空中飛行受到多種不確定因素的影響，無論是航跡規(guī)劃，還是碰撞風險的研究，都必須知道飛機確切的位置、速度、航向、高度等因素。若忽略飛行動力學、氣象、人為因素等多種不確定因素，對于實際飛行中會造成很大的誤差。因此，飛機在“可視”狀態(tài)下，對于碰撞風險的研究才更有意義。根據(jù)相關(guān)文獻［18］，大部分學者都將不確定因素引起的飛機定位誤差假設(shè)為服從正態(tài)分布，且得到的結(jié)論也符合實際情況。因此，本文假設(shè)由不確定因素引起的飛機定位誤差服從正態(tài)分布，利用相對運動原理，基于平面直角坐標系建立2 架飛機在水平投影面和垂直投影面上的隨機運動模型，當2 架飛機相對運動距離小于最小安全間隔時認為碰撞發(fā)生。

據(jù)此建立基于相對運動原理和平面直角坐標系的水平方向沖突預測模型和垂直方向沖突預測模型。在時間段［t，T］內(nèi)，飛機在水平方向和垂直方向定位誤差服從N1（0，δ12）、N2（0，δ22）正態(tài)分布，其概率密度函數(shù)為：

自由飛行環(huán)境下兩飛機發(fā)生碰撞的概率為P=P1×P2。P1和P2分別表示在水平方向和垂直方向上發(fā)生碰撞的概率。

1.1 模型的基本假設(shè)

為建立自由飛行環(huán)境下飛行沖突預測模型，進行如下假設(shè)：

1）多架飛機之間的運行狀態(tài)相互獨立；

2）飛機水平運動和垂直運動相互獨立；

3）飛機自由飛行是在高空區(qū)域飛行；

4）飛機隨機因素導致誤差服從正態(tài)分布；

5）相對速度與兩飛機之間連線的夾角簡稱為角度；

6）建立x-y-z 坐標系，x-y 所在平面的運動為水平方向上的運動，z 軸方向上的運動為垂直方向上的運動，采用的速度均為相對速度。

1.2 水平方向沖突預測模型的建立

兩架飛機在水平投影面上相對運動示意圖1所示，為了表述方便，假設(shè)飛機A 的起始位置為坐標原點（0，0），可分解計算沿坐標軸投影到水平投影面的速度分量，定位誤差服從正態(tài)分布。飛機B 的位置為（x，y），同樣可分解計算沿坐標軸投影到水平投影面的速度分量，定位誤差服從正態(tài)分布。根據(jù)相對運動原理，假設(shè)飛機A 在此平面無實際運動的速度，轉(zhuǎn)化為在原點做標準的布朗運動B1（t）服從分布N1（0，δ12），概率密度函數(shù)如式（2），飛機B 以水平相對速度v1飛行，兩架飛機水平相對距離為R，角度為θ［23］。因此，兩架飛機的飛行狀態(tài)可轉(zhuǎn)化為飛機A 以原點做標準的布朗運動，飛機B 以水平相對速度v1飛行、水平相對距離為R 的相對運動。

圖1 水平投影面上飛機相對運動示意圖

按以上假設(shè)建立飛機沿相對速度方向運動的微分方程模型，S（t）為飛機B 在速度v1方向上運動的距離。

由幾何關(guān)系可知飛機A 和飛機B 在任意時刻的水平方向上的距離滿足如下方程式：

式中，X（t）為在時刻兩飛機之間的水平方向上的距離，由式（2）可知，B1（t）的均值為0，方差為δ1。

飛機在水平面上發(fā)生碰撞定義為X（t）＜D1，其中X（t）為t 時刻兩飛機的水平相對距離，D1為規(guī)定的水平方向上最小安全間隔。則飛機在水平面的碰撞概率為P（X（t）＜D1）。

1.3 垂直方向沖突預測模型的建立

根據(jù)兩架飛機在水平方向上飛行狀態(tài)分析，利用相對運動原理轉(zhuǎn)化為飛機A 在原點做標準的布朗運動B2（t）服從分布N2（0，δ22），其概率密度函數(shù)為如式（6），飛機B 以垂直相對速度v2飛行，初始時刻兩飛機的相對高度差H。

式中，Y（t）為在時刻t 兩飛機之間的垂直方向上的距離，由式（6）可知，B2（t）的均值為0，方差為δ2。

飛機在水平面上發(fā)生碰撞定義為Y（t）＜D2，其中Y（t）為t 時刻兩飛機的垂直相對距離，D2為規(guī)定的垂直方向上最小安全間隔。則飛機在垂直方向上的碰撞概率為P（Y（t）＜D2）。

飛機發(fā)生碰撞一定是兩飛機的水平相對距離和垂直相對距離同時小于規(guī)定的最小安全距離，用式子表達為：

式中，NP 為飛機架次，架/h。

每架飛機的危險系數(shù)都是相對于某一個本機的，多機航跡規(guī)劃作為一種整體規(guī)劃，具有協(xié)同性，即所有飛機遵循同樣的規(guī)劃原則，因此，每架飛機應(yīng)具有唯一的危險系數(shù)。以ADS-B IN 監(jiān)視范圍內(nèi)的每一架飛機為本機，計算周圍所有飛機的危險系數(shù)，其中危險系數(shù)最大的目標機定義為本機的危險系數(shù)。根據(jù)每架飛機的危險數(shù)調(diào)整規(guī)劃優(yōu)先級，保證最危險的兩架沖突飛機獲得最遠的安全間隔和最早的航跡改變，危險系數(shù)是路徑規(guī)劃過程中規(guī)劃順序、規(guī)劃方向、沖突判定、快速求解和最優(yōu)解等項目的重要依據(jù)。

2 飛行沖突解脫與路徑規(guī)劃模型的建立

根據(jù)ADS-B IN 數(shù)據(jù)，可以預測和發(fā)現(xiàn)沖突，消除所有潛在的碰撞威脅，并始終保持足夠的安全間隔和最短路徑，計算出最優(yōu)的沖突解脫路線和回歸路線，提高飛行的安全和效率。傳統(tǒng)的垂直解脫策略通常不適用于多機沖突場景。此外，改變高度對飛機燃油消耗比較大。因此，本文采用水平解脫策略，主要分為改變航向和改變航速兩種，然而飛機改變速度存在一定的延時，且速度會受氣象、氣流、飛行高度等影響，無法進行精確的計算，因此，本文采用的是以保速調(diào)向方式為主，調(diào)速方案只作為對調(diào)向方式的改進和補充。

2.1 模型的基本假設(shè)

根據(jù)中國空中交通管理安全規(guī)定以及實際運行情況，為盡快尋找出安全有效的沖突解脫方案，簡化如下：

1）航空器在巡航階段采用定高飛行，可簡化為二維平面的沖突解脫問題；

2）按照中國空中交通管理安全規(guī)定：兩架航空器之間的安全間隔為20 km，若兩架航空器距離小于20 km 時，則發(fā)生飛行沖突；

3）為提高計算的精確度，計算移動的步長采用最小安全距離的一半即10 km；

4）在改變航向時，本文假設(shè)航向角可在-45°～45°中任意選取，在調(diào)整速度時假設(shè)民用航空器的速度可在預計速度的30%～130%范圍內(nèi)變化；

5）研究區(qū)域為200 km 的正方形區(qū)域，每隔10 km 設(shè)置一個計算點，飛機沿網(wǎng)格節(jié)點飛行；

6）在研究區(qū)間內(nèi)飛機做直線飛行沒有飛行方向的變化。

2.2 沖突解脫的目標函數(shù)

2.2.1 位置點更新函數(shù)

2.2.2 航向調(diào)整策略的目標函數(shù)

采取航向調(diào)整的策略防止沖突時，為節(jié)省沖突解脫時間，同時減少燃料消耗，民用航空器在能夠規(guī)避沖突的前提下，使每個節(jié)點距離原航跡的和最小，則公式為：式中，Li為第i 架航空器的每個節(jié)點與原航跡距離總和。

為滿足最小安全距離的約束，要求兩機之間滿足：

式中，δ=20 km。（xi，yi），（xj，yj）分別為i 機和j 機在該水平面內(nèi)的坐標。

2.2.3 速度調(diào)整策略的目標函數(shù)

單獨使用速度調(diào)整可能使速度調(diào)整幅度較大，且速度變化較大，航空器在高空中飛行較難保持所必需的升力，在上文假設(shè)中只假設(shè)了30%的速度調(diào)整量。本文中不單獨使用速度調(diào)整策略來解決航跡沖突規(guī)劃問題，只用來做航向調(diào)整策略的補充，在航向調(diào)整策略中航空器會在預計碰撞點之前作出航向改變以增加飛行路徑來避免飛行沖突，本質(zhì)上與減小速度來避免飛行沖突是一樣的。因此，速度調(diào)整策略目標函數(shù)的形式與航向調(diào)整策略的目標函數(shù)一致，則公式為：

式中，Vi為第i 架航空器的每個節(jié)點與原航跡距離總和。

3 飛行沖突解脫與路徑規(guī)劃算法設(shè)計

3.1 遺傳算法原理

遺傳算法是一種隨機搜索算法，新一代是由前一代可行解通過交叉或變異運算形成的。經(jīng)過多次迭代運算，算法趨于收斂，進而得到問題的最優(yōu)解或次優(yōu)解。

3.2 適應(yīng)度函數(shù)的改進

根據(jù)遺傳算法的原理，第i 個個體被選取的概率可由式（16）計算得到。由于群體的差異性降低，算法可能出現(xiàn)早期收斂。因此，改進算法的適應(yīng)度函數(shù)降低適應(yīng)度之間的差異程度，以維護群體的多樣性，避免算法出現(xiàn)早期收斂。

當子代的適應(yīng)度小于父代且滿足最小安全間隔時，就用子代染色體代替父代來進行下一輪的迭代，當子代的適應(yīng)度大于父代或最小安全距離小于20 km 時用父代染色體來開始下一輪迭代，這樣，就可以保持種群個數(shù)不變且個體都是符合約束的，迭代方程如式（17）。

式中，n 為種群的個體數(shù)，N 為迭代次數(shù)，y為通過變異突變得到的個體，f 為適應(yīng)度，D 為每個節(jié)點飛機之間的相對距離。

3.3 采用改進遺傳算法的飛行沖突解脫

3.3.1 問題簡化

根據(jù)遺傳算法的原理，需要對每一條航跡的坐標進行編碼。在邊長為200 km 的正方形區(qū)域內(nèi)，每隔10 km 設(shè)置一個計算點，這樣共有21 個點。按照兩架飛機進行計算的變量數(shù)有126 個，編碼工作較大。為此，對問題進行簡化如下：

1）三維立體問題簡化為二維平面問題，多機避免沖突時只在水平面內(nèi)改變方向；

2）飛機的飛行速度不變；

3）飛機可選航向：原航向，左偏45°，右偏45°。

經(jīng)過上述3 步簡化就可以避免直接對飛機的3個空間坐標進行編碼，對每架飛機的每步飛行方向進行編碼，飛機只有3 個飛行方向，采用二進制編碼，兩位就可表示出所有情況，00（0）和01（1）表示按原方向飛行，10（2）表示向原航向左側(cè)飛行，11（3）表示向原航向右側(cè)飛行，一個染色體就是84 個bit。

3.3.2 算法步驟

針對多機解脫策略，設(shè)計改進遺傳算法，其計算步驟如下：

步驟1：初始化參數(shù)。確定解脫所需步數(shù)、航向改變角度、最小安全間隔、飛機初始位置點、飛機飛行方向、最大迭代次數(shù)、初始種群個數(shù)、變異概率、交配概率。

步驟2：產(chǎn)生初始可行解。將產(chǎn)生的初始種群解碼，再轉(zhuǎn)換成相應(yīng)的偏轉(zhuǎn)方向和角度，通過式（10）可以得到飛機在每個飛行節(jié)點的坐標，看兩架飛機是否滿足式（13），若滿足則作為一個可行解保留下來。篩選足夠多的滿足最小安全距離的個體組成初始種群。

步驟3：計算初始種群中每個個體的適應(yīng)度。由式（11）、式（12）可計算得到每個個體的適應(yīng)度。

步驟4：進行染色體突變和交配。

步驟5：檢查新得到的個體是否滿足式（13）要求，用式（11）和式（12）計算每個個體的適應(yīng)度。

步驟6：由式（7）進行更新迭代，若子代的適應(yīng)度小于父代且滿足最小安全間隔時，就用子代染色體代替父代來進行下一輪的迭代，當子代的適應(yīng)度大于父代或最小安全距離小于20 km 時，用父代染色體來開始下一輪迭代，始終用每個個體迭代中出現(xiàn)的最優(yōu)的個體去進行下一次迭代。

步驟7：由式（11）和式（12）計算每個個體的適應(yīng)度，記錄最優(yōu)值和最優(yōu)個體。

步驟8：若迭代次數(shù)沒有超過最大限制或最優(yōu)值出現(xiàn)次數(shù)沒有超過限制，則返還步驟4。

4 仿真驗證結(jié)果及分析

本文假設(shè)水平方向和垂直方向上的運動相互獨立，水平相對速度、角度、垂直相對速度都為變量，在模型中不易求解。先研究垂直方向相對速度為定值，水平相對速度和角度在一定的范圍區(qū)間變化對碰撞風險的影響。在垂直相對速度確定情況下，可以給出改變水平方向速度或改變角度來降低碰撞風險的措施。

本文以ICAO 規(guī)定的安全等級4.5 次事故/108飛行小時為目標［22］，若高于此標準則對應(yīng)的角度和速度為可行方案，低于此標準則為不可行方案。

4.1 不定步長航向調(diào)整策略的仿真計算

按照10 km 的間隔將沖突區(qū)域劃分為20×20個方格，飛機沿網(wǎng)格線飛行的距離和沿網(wǎng)格對角線飛行的距離是不同的。假設(shè)飛機沿網(wǎng)格線飛行到下一節(jié)點和沿對角線飛行到下一節(jié)點所用時間相同。因此，飛機飛行每步都在網(wǎng)格節(jié)點上，有利于初始研究，并對后續(xù)改進提供一定參考。

表1 不同角度和速度下的危險系數(shù)

設(shè)初始種群有150 個個體，最大迭代次數(shù)100，兩飛機沖突解脫情況如圖2，最優(yōu)值的迭代情況如圖3，用沖突預測模型得到的每個節(jié)點的危險系數(shù)值如圖4。從圖3 中可以看出最優(yōu)值呈現(xiàn)出階梯式下降，從45 代之后始終處于恒定值，即認為得到了最優(yōu)解，由于對適應(yīng)度函數(shù)進行了改進，可以清晰地從圖3 看出最優(yōu)值的迭代情況呈現(xiàn)階梯式下降且都是確定的值。從圖4 可以看出在第10 個飛行節(jié)點碰撞危險系數(shù)最大，且小于指定的安全目標等級（4.5 次事故/108飛行小時），在其他節(jié)點碰撞危險系數(shù)都是0，沒有碰撞風險。若在第9 個飛行節(jié)點和第11 個飛行節(jié)點進行精細的劃分可以得到更精確的結(jié)果。

圖2 不定步長2 機航跡規(guī)劃

圖3 最優(yōu)值迭代情況

圖4 每個節(jié)點的碰撞風險系數(shù)

4.2 定步長航向調(diào)整策略的仿真計算

設(shè)定每架飛機預計航線方向步長均為10 km，最小安全距離為20 km。若有航向的調(diào)整必定會造成有的飛行節(jié)點不在網(wǎng)格節(jié)點上，實現(xiàn)起來要比不定步長航向調(diào)整策略復雜一些，仿真模擬效果更接近于實際情況。

多機飛行沖突可分為兩機連續(xù)沖突和多機匯聚沖突，如圖5 和圖6 所示。對于這兩種典型的多機飛行沖突，通過本文提出的無沖突航跡規(guī)劃方法可以快速地找出一條最優(yōu)的無沖突航跡，如圖7 和圖8 所示。仿真計算后的航跡點完全錯開，并且相互之間的水平間隔始終滿足航路最小間隔20 km 的要求。

圖5 連續(xù)兩機沖突

圖6 多機匯聚沖突

圖7 采用航向調(diào)整策略的兩機航跡規(guī)劃

圖8 采用航向調(diào)整策略的四機航跡規(guī)劃

4.3 加入速度調(diào)整策略兩機航跡規(guī)劃優(yōu)化仿真計算

從圖7 中可以看出飛機調(diào)向次數(shù)較多，這是由于設(shè)置的目標函數(shù)造成的，飛機為避免沖突不得不在碰撞點之前進行多轉(zhuǎn)向來在航路上消耗時間以達到避免沖突的目的，但轉(zhuǎn)向次數(shù)過多在實際飛行中并不現(xiàn)實，轉(zhuǎn)向次數(shù)過多實際上就是在航路上消耗時間，用速度調(diào)整策略可以達到相同的目的，加入減速策略的兩飛機沖突解脫情況如圖9。未加入減速策略的定步長航向調(diào)整策略的最優(yōu)值為56.569，加入速度調(diào)整策略的定步長航向調(diào)整策略的最優(yōu)值為28.284，減少了近50%，可見加入減速策略不僅可以減少轉(zhuǎn)向次數(shù)也可以極大地減少最優(yōu)值。

圖9 采用航向和速度調(diào)整策略的兩機沖突解脫

5 結(jié)論

本文結(jié)合ADS-B IN 技術(shù)特點，建立了多因素的概率型飛行沖突預測和解脫模型，并設(shè)計了基于改進遺傳算法的飛行沖突解脫與路徑規(guī)劃算法。該算法不僅保持了傳統(tǒng)遺傳算法全局搜索和跳出局部最優(yōu)的能力，且能夠?qū)σ恍┻m應(yīng)度較高的個體進行控制，維護群體的多樣性，進而提高了尋優(yōu)的能力，避免了遺傳算法易出現(xiàn)早期收斂現(xiàn)象?；诎踩繕说燃?.5 次事故/108飛行小時（h）為限制條件，通過多機航向調(diào)整、速度調(diào)整2 種策略沖突解脫的仿真，保證了飛機之間的安全間隔，實現(xiàn)了解脫后自動回歸到原航跡上，驗證了該算法在多機飛行沖突解脫問題中的可行性、高效性和優(yōu)越性。