基于有向元胞自动机的空中导航和冲突解脱算法

董兵，杜文，刘晓明

(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.