基于有向元胞自動機的空中導航和沖突解脫算法

董兵，杜文，劉曉明

(1.西南交通大學 交通運輸與物流學院，四川 成都610031;2.中國民用航空飛行學院 研究生處，四川 廣漢618307)

0 引言

隨著國家通用航空的快速發展和低空空域開放帶來大發展的機遇，通用航空飛行安全問題凸顯出來。據統計，2009年和2010年，通用航空事故和事故征候率均是運輸航空的3倍，安全形勢比較嚴峻［1］。部分通用航空公司存在著規模小、底子薄、安全基礎差等客觀因素，特別是在一些邊遠和海洋地區，地面導航設備缺乏，需要一種精度高、使用方便的導航設備和導航系統。

隨著國際民航組織(ICAO)等研究機構的重視［2］，許多新技術不斷被提出，其目的是將地面管制員的負擔向空中轉移。新系統中提出了廣播式自動相關監視(Automatic Dependent Surveillance Broadcast，ADS-B)系統，其特點是:主動發布和接收飛行狀態信息，機載設備與地面設備相互協同，監視范圍擴展為飛行的全過程［3-4］。

目前基于ADS-B的研究主要體現在基于ADSB 數據飛行沖突的避免［5］、飛行安全間隔評估［6］、誤差評估分析及完好性［7］等方面。在導航和沖突檢測方面，少有人涉及。在已有的文獻中，文獻［8-11］利用元胞自動機模型，對機器人路徑規劃進行了研究。本文將元胞自動機概念引入到飛機自主導航和飛行沖突解脫問題的研究中。

1 模型的建立

1.1 有向元胞自動機的引入

元胞自動機(Cellular Automaton，CA)是一種時間、空間、狀態都離散的動力學模型，它適合于復雜系統時空演化過程的動態模擬研究［12］。當每一個元胞能夠向8個基本方向運動時，該元胞被定義為有向元胞自動機(Directional Cellular Automata)。

一個元胞的上、下、左、右、左上、左下、右上、右下相鄰8個元胞為該元胞的鄰居。本文采用二維的Moore型元胞自動機來定義其鄰居［13］。鄰居的邊長為1，如圖1所示(圖中，“●”表示飛機，“→”表示飛機的飛行方向)，其鄰居定義如下:

式中:(xix，yiy)∈Z2，Z為整數集合。

圖1 元胞的基本運動方向Fig.1 Basic moving direction of CA

元胞自動機每個變量只取有限多個狀態［13］，而且其狀態改變的規則在時間和空間上都是局部的。散布在規則網格(Lattice Grid)中的每一個元胞遵循同樣的作用規則，依據確定的規則作同步更新。大量元胞通過簡單的相互作用從而構成動態系統的演化。

不同于一般的動力學模型，元胞自動機不是由嚴格定義的物理方程或函數確定，而是由一系列模型構造的規則構成。

1.2 空域的建模

基于上述的有向元胞自動機模型，對空域進行仿真建模。首先，將飛行區域進行適當的分割，分別記為A1，A2，…，分割的大小可按照ADS-B系統信號的發射和接受能力來確定［14］。

飛機在某一空域Ai飛行時，可視該飛行區域為一個平面。將某空域Ai劃分成M×N網格，每一個網格代表一個元胞，網格的大小應當根據其所在空域飛行的最小安全間隔、速度、限制區域的大小以及飛機的性能等因素來確定。一般情況下，鄰居的邊長為2r，r的大小取決于飛機的性能、轉彎的坡度等因素。

根據飛行原理知識［15］，有:

式中:v為飛行速度;g為重力加速度;γ為盤旋坡度。飛行速度和盤旋坡度的取值參考飛機性能參數。

以出發點為坐標原點，目標位置可能出現的位置為右上(包括正北方、正東方)、右下、左上(包括正西方、正南方)、左下。以右上方為例建立空域模型，如圖2所示。

圖2 基于元胞的空域模型Fig.2 Airspace model based CA

1.3 元胞更新時間的定義

在考慮綜合性能的情況下，將時間t離散化處理，以t0表示一個時間段，每過t0時長，元胞的狀態將更新一次。ti表示經i個時間段。時間段的長短應考慮飛行速度等因素。

2 導航和沖突解脫算法的建立

2.1 問題假設

(1)在該元胞自動機系統中，每一個元胞狀態用布爾代數來表示。當該元胞被占用時，狀態為1，沒有被占用時，狀態為0，在該系統中的限制區以及惡劣天氣所占的空間狀態為1。

(2)裝配有ADS-B系統的飛機將自動發布自己和接收所在空域內飛機的經緯度、飛行高度及速度，以便確定其在空域中的位置。

(3)對每架進入飛行區域Ai的飛機進行編號，Flight 1，Flight 2，…，將離開飛行區域Ai的飛機編號從小到大依次分配給新進入的飛機。

2.2 有向元胞自動機的演化規則

2.2.1 元胞移動規則的建立

由于每個分割后的飛行區域較小，可視飛行區域為平面的。以導航飛機本身為中心，正東方向為x軸，正北方向為y軸建立直角坐標系。

水平軸x:xo表示現在飛行器所處的狀態，xd表示飛行器將前行的鄰居的狀態。

垂直軸y:yo表示現在飛行器所處的狀態，yd表示飛行器將前行的鄰居的狀態。

當所在的元胞狀態為 1 時，xo，xd，yo，yd其值為1;元胞狀態所處的狀態為0時，其值為0。如果:xd－xo＞0，元胞向右移動;yd－yo＞0，元胞向上移動;xd－xo＜0，元胞向左移動;yd－yo＜0，元胞向下移動;xd－xo=0，元胞無水平移動;yd－yo=0，元胞無垂直移動。

2.2.2 系統移動方向搜索順序的確立

在圖3表示的空域環境中，a是系統第一搜索方向;b，c是第二搜索方向;d，e是第三搜索方向。以上條件的組合，可確定出在下一離散時間點上元胞將要移動的方向，比如:xd－xo＞0，yd－yo＞0，元胞將向右上鄰居移動。

圖3 元胞自動機模型移動方向搜索順序Fig.3 Hierarchical searches in CA model

2.2.3 元胞移動方向的確定

出發點指向終點的連線方向是元胞的移動方向，如圖3所示。按上述規則，元胞的移動方向為水平、垂直和對角線方向。

3 仿真結果及分析

以某型機為例進行仿真。選取v=80 m/s，g=9.8 m/s2，γ =25°，經計算 r=1 401 m，以2r為邊長，將空域Ai進行網格化處理，其中每一個網格定義為一個元胞。每過t0=15 s，元胞的狀態更新一次。根據元胞運動規則，飛機將向鄰居方向移動一次。

3.1 飛機的自主導航

飛機將從cell(1，1)飛行到目的地cell(5，5)。在此空域中，由于沒有限制區和飛行沖突，飛機將會選擇a方向飛行，因此cell(1，1)→cell(2，2)→cell(3，3)→cell(4，4)就構成了該架飛機的飛行路徑，如圖4所示。

圖4 無沖突環境中飛機自動導航路徑Fig.4 Automatic navigation path in no conflict situation

3.2 避開限制區

在圖5(圖中，陰影區表示飛行限制區域)所示空域中，cell(3，4)，cell(3，3)，cell(3，2)，cell(4，2)構成的區域為飛行限制區，飛機從cell(1，1)飛到cell(5，5)。當飛機出發時，a方向是飛行方向。經過一個時間段，飛到 cell(2，2)時，b，d，e 是可選擇的飛行方向。按照規則，b方向是選擇的飛行方向。依次進行，經過6個時間段，飛機將飛到cell(5，5)。這樣 cell(1，1)→cell(2，2)→cell(2，3)→cell(2，4)→ cell(3，5)→cell(4，5)→cell(5，5)就構成了該架飛機的飛行路徑。

圖5 避開限制區后的飛行路徑Fig.5 Flight path after restricted zone

3.3 沖突解脫

空域中有3架飛機，Flight 1將從cell(1，15)飛到 cell(15，1)，Flight 2 將從 cell(15，8)飛到 cell(1，8)，Flight 3 將從 cell(1，15)飛到 cell(15，1)。飛機進入空域的編號順序為:Flight 1，Flight 2，Flight 3。開始時，每架飛機按照各自最佳的飛行路徑進行飛行。當飛行到第7個飛行時間段t7時，3架飛機將在cell(8，8)發生沖突。此時，編號最小的飛機最先進行選擇。當Flight 1在t7時段選擇正左方向飛行時(情況a)，依次地，Flight 2在t7時段選擇正右方向飛行，Flight 3在t7時段選擇正上方向飛行，具體的沖突解脫細節如圖6所示。圖7中顯示的飛行軌跡是依據圖6飛行時，3架飛機的最終飛行軌跡。

圖6 3架飛機的沖突解脫細節(a)Fig.6 Self-spacing maneuvering detail of three aircrafts(a)

圖7 3架飛機的仿真軌跡(a)Fig.7 Simulated trajectories of three aircrafts(a)

當Flight 2選擇了正下方作為t7時段的飛行方向時(情況b)，該算法依然能夠給出各飛機的飛行軌跡。具體的沖突解脫細節如圖8所示。

圖8 3架飛機的沖突解脫細節(b)Fig.8 Self-spacing maneuvering detail of three aircrafts(b)

圖9中顯示的飛行軌跡是依據圖8飛行時，3架飛機的最終飛行軌跡。

圖9 3架飛機的仿真軌跡(b)Fig.9 Simulated trajectories of three aircrafts(b)

從以上仿真實例可以看出，利用機載ADS-B系統發出和接收的信息，結合有向元胞機模擬空域，能夠實現飛機的自動導航及沖突解脫。沖突解脫的計算量較小，能夠通過機載計算機給出沖突解脫的實時路徑。

4 結論

通過本文的研究，可以得出以下結論:

(1)基于有向元胞自動機模型建立的運行規則，能夠實現飛機自主導航和飛行沖突解脫。在本文研究的基礎上，完善相關數據系統后，能夠為飛行機組提供導航決策。

(2)本文討論的方法是針對二維空域，對于三維空域，可采用分別向水平面和垂直面投影的方法，將三維空域分解為兩個二維空域，所提出的方法同樣適用。

(3)本文所列舉的例子較簡單，空域范圍也比較小，隨著空域范圍的擴大，元胞數目將會增多，飛機數目和危險點也會增加。按照本文提供的規則，在飛機數目足夠多和限制區非常特殊的情況下，將可能出現無解的情況，此時，飛機可選擇在此空域盤旋。但在實際運行過程中，由于有航空情報服務，極端天氣和嚴重超出空域容量的情況是不會出現的。

［1］ 中國民用航空局航空安全辦公室.中國民航不安全事件統計分析報告［R］.北京:中國民用航空局航空安全辦公室，2011.

［2］ JPDO.Concept of operations for the next generation air transportation system version 2.0［R］.Washington:JPDO，2007.

［3］ 張軍.空域監視技術的新進展及應用［J］.航空學報，2011，32(1):1-14.

［4］ 高揚，雷昱，雒旭峰.基于ADS-B的多雷達民航空管安全監視體系［J］.交通信息與安全，2009，27(3):89-92.

［5］ Thompson S D，Sinclair K A.Automatic dependent surveillance broadcast in the gulf of mexico［J］.Lincoln Lab.，2007，1(17):55-69.

［6］ 吳振亞，王明輝，張瑞平，等.一種基于ADS-B的雷達誤差實時融合校正算法［J］.西南交通大學學報，2013，48(1):102-106.

［7］ Robert Holdsworth.Autonomous in flight path planning to replace pure collision avoidance for free flight aircraft using automatic dependent surveillance broadcast［D］.Melbourne:Swinburne University，2003.

［8］ Fabio M Marchese.A directional diffusion algorithm on cellular automata for robot path-planning［J］.Future Generation Computer Systems，2002，18(7):983-994.

［9］ Fu Marchese F.Cellular automata in robot path planning［C］//Advanced Mobile Robot，Proceedings of the First Euromicro Workshop on.Kaiserslautern:IEEE，1996:116-125.

［10］曾明如，王從慶，劉公法，等.基于元胞自動機的移動機器人路徑規劃［J］.南昌大學學報:工科版，2012，34(3):287-290.

［11］張建英，劉暾.基于人工勢場法的移動機器人最優路徑規劃［J］.航空學報，2007，28(S1):183-188.

［12］ Burzynski M，Kosinski W.From traffic flow simulations to collision avoidance module for mobile robot-cellular automata with fuzzy rules approach［C］//Third International Workshop on Robot Motion and Control.Bukowy Dworek:IEEE，2002:303-308.

［13］賈斌，高自友，李克平，等.基于元胞自動機的交通系統建模與模擬［M］.北京:科學出版社，2007:25-29.

［14］張青竹，張軍，劉偉，等.民航空管應用ADS-B的關鍵問題分析［J］.電子技術應用，2007，35(9):72-74.

［15］王大海，楊俊，余江.飛行原理［M］.成都:西南交通大學出版社，2010:95-98.