基于分离轴算法的机场场面飞行器冲突告警研究

吴寿英 李 炜

1(四川大学视觉合成图形图像技术国防重点学科实验室 四川 成都 610065) 2(四川大学空天科学与工程学院 四川 成都 610065)

0 引 言

由于目前机场场面缺少完备的冲突事件检测和告警系统,导致机坪航空器之间的擦碰事件时有发生,造成大量人员航班延误。因为机坪人手不足,地勤和航空器操作员存在视线盲区,导致机坪繁忙阶段特别容易发生航空器之间的擦碰问题。为有效监控与管理场面飞机的安全运行,减少机场地面交通擦碰事件的发生,国内外航空界对此做了较多的研究,提出了一些理论与方法[1-2]。但总体上都是从硬件设备以及策略方面降低机场飞机之间的碰撞问题。减少航空器间的冲突及碰撞是机场安全运行的重要保证,由于航空器后机会受到前机尾流的影响,所以在地面滑行时保证航空器间的安全距离是有效避免冲突及碰撞的手段,叶右军[3]研究了基于航空器间安全距离的碰撞模型,以降低航空器之间的碰撞风险。另外,潘卫军等[4]分析了机场冲突热点的时空分布特征,通过对机场建模构建航空器的滑行和避让机制,提出基于机场冲突热点时空分布特征的航空器地面滑行路径优化模型,从而降低场面飞机的冲突或碰撞事件。葛亚威等[5]利用A-SMGC系统监视模块与路由规划模块的结合,构建冲突探测系统框架来减少冲突碰撞事件以及提升机场运行安全,类似的研究还有许多[6-8]。

上述这些理论方法虽然在一定程度上对场面航空器冲突预警,但是其虚警率高。牟奇锋等[9]通过航空器外形及关键尺寸设计类碰撞盒的可变多边形还原航空器,且考虑航空器在运动过程中对地面空间占用的影响,将其机头保护层沿运动方向前推至一个制动距离,从而降低虚警率。杜金峰等[10]使用基于北斗二代定位数据的机场场面短期冲突探测算法,可以根据飞机不同运动状态设定最小安全距离且判定冲突类型从而减少虚警率。

机场场面目标危险接近与告警实质上是其在告警区域内的碰撞检测问题。根据监控飞机的地理位置坐标和型号可重建飞机模型,进而获得该飞机模型在2D场面下的区域坐标范围,从而可以转化为二维场景下的多边形碰撞检测问题。本文设计基于最近点的分离轴碰撞检测算法,重建飞机目标模型,并对模型顶点进行弧形检测,构建模型监控告警区。通过计算机模拟仿真场面飞机危险接近场景,仿真实验结果表明,本文算法可有效降低程序时间复杂度加快冲突检测速度,同时弧形处理可降低虚警率。

1 重建飞机模型

由于飞机是多边形,且常见的载人客机模型轮廓都差不多,所以围绕航空器的外围轮廓,根据其外部形状特征,通过模型关键尺寸即可构建飞机模型基层区域。飞机模型可以用17条边包围,如图1所示,假设已知的坐标点为飞机头顶点A0(x0,y0),则沿顺时针分别将各个顶点坐标标记为A1,A2,…,A16。

图1 飞机模型编号

过顶点A0作一条中线平分模型,直线与x轴夹角为飞机的朝向θ。设飞机关键尺寸为hi、wi,当i<7时,分别为Ai到A0顶点的θ-π/2方向和θ方向的两个分量,如图2所示。当i≥7时,分别为θ+π/2方向和θ方向的两个分量,如图3所示。

图2 飞机模型顶点坐标计算(i<7)

图3 飞机模型顶点坐标计算 (i≥7)

当i<7情况下,飞机朝向和关键尺寸已知,由图2可知Ai(xi,yi)顶点的坐标为:

式中:m与n分别为Ai到A0顶点之间x轴和y轴投影的距离,根据几何原理可得:

则有:

同理,当i≥7时,则有:

机场场面冲突检测就是防止碰撞,所以要制定安全距离,进行危险接近触发告警机制。危险接近告警就是模拟告警区,对于特定的安全距离阈值可以构造飞机告警区,从而构造飞机之间的安全距离。飞机模型是一个非凸多边形,如果直接计算航空器之间的碰撞关系则会非常复杂,所以把非凸多边形划分为多个凸多边形是自然会想到的解决方法。如图1所示,飞机模型被划分为6个凸多边形,其中有效多边形为5个(a-e)。接下来是飞机模型安全区域的碰撞检测,本文把检测过程分为粗略检测阶段和精细检测阶段,其中精细检测即直接对飞机凸多边形进行两两检测。

由于场面飞机较多,直接进行精细检测会消耗较多检测时间,所以使用检测速度较快的方法先进行粗略检测可以提高检测速度。如图4所示,B区为粗略检测区,使用类包围球方法,原点为恰好能够把A区围住的圆的圆心。A区为精细检测区,用一个多边形把飞机模型围起来,多边形形状即飞机模型向外制动一个安全距离所得,在顶点部分进行圆滑处理,即以飞机模型顶点为圆心画弧。由于飞机实体较大,若顶点不进行圆滑处理,则会出现机翼顶点区域向外制动的安全距离过长,会导致虚警。设飞机安全距离告警阈值为SPTP,飞机机头到机尾距离为d,则有飞机模型对应B区的半径为rB=2×SPTP+d。

图4 飞机安全区域及阈值设置

具体实现中,目标的冲突检测需先检测B区是否碰撞,如果没有则进行下一个目标模型检测,否则再进行A区碰撞检测。由于飞机A区检测比较复杂,所以用B区包起来先进行一次快速粗略检测,这样可以降低检测A区的次数,从而很大程度减少程序时间复杂度,增快检测速度。

2 检测算法描述

凸多边形碰撞检测算法使用分离轴定理,若令K和L为两个不相交的非空封闭凸集,其中一个是有界闭集,则存在一个非零向量v和实数r1

〈x1,v〉>r2(x1∈K),〈x2,v〉

(5)

若K、L集合都是开放的,则存在一个非零向量v′和实数r使得:

〈x1,v′〉>r(x1∈K),〈x2,v′〉

(6)

如图5所示,取飞机模型的两个凸多边形a与e为例,把多边形的顶点都投影至一条轴线上。只要找到一条或多条轴(分离轴),使凸多边在该轴的投影不相交,那就可以说明这两个或多个物体没有发生碰撞。为了方便观察,垂直于分离轴且可以把目标分为左右两边的向量称为分离线。

图5 分离轴定理示图

分离轴定理所选择的潜在分离轴通常都是凸多边形的边所在的轴线,随着边数的增多,检测的次数会不断增加(如一直未找到潜在分离轴),只要找到一条不相交的分离轴,程序就会立马停止检测,所以基于分离轴定理的碰撞检测算法属于高效的算法,不过弊端也非常明显,当找不到分离轴的时候,算法复杂度会增加。所以需要一个改进的方案,降低程序寻找分离轴的次数,从而提高计算效率。

由于应用场景是场面飞机,而对于精细检测阶段,把A区分解成5个有效凸边形(此处凸边形是指没有进行顶点圆弧处理的多边形),则两个飞机A区碰撞检测算法最多会被调用25次,若飞机数量增加,碰撞算法时间复杂度也会增大,所以碰撞算法的选取显得尤为重要,本文使用基于分离轴定理的碰撞检测算法。

多架飞机之间碰撞如果用传统的分离轴定理效率不够高,由于每架飞机有5个凸边形17条边,逐个查找分离轴最多需要17×2次,两架飞机总的查找次数为5!×17×2即4 080次,若有n架飞机,则查找次数变为n!×4 080次。所以传统基于分离轴的碰撞检测算法不适合边数较多的凸多边形。由于两个目标碰撞一定是点和点、点和线、线和线的其中一种情况,即一定包含一个顶点,所以找到这个可能的顶点可以减少碰撞检测次数。首先找到碰撞点序列,再利用折半搜索技术求取最初碰撞的顶点和边。本文利用改进的分离轴碰撞检测算法即基于最近点的碰撞检测。设ai(xi,yi)(i=0,1,…,16)为飞机的顶点,Tj(j=a,b,c,d,e)为飞机模型里的5个凸多边形,则有:

连接两架飞机中线中点形成直线M,飞机中线中点坐标dz(xz,yz)为:

两架飞机的中点坐标分别为dz1(xz1,yz1)、dz2(xz2,yz2)则直线M函数为:

其斜率和截距为:

把飞机顶点ai(xi,yi)(i=0,1,…,16)投影到直线M上,设投影点为aMi(xMi,yMi)(i=0,1,…,16),则有:

首先找到最近的两个投影点,记录最近顶点所在凸边形号,若可以找到一条垂直直线把两个凸边形的投影点分隔开,即证明两个凸边形无重叠。否则查找两个凸边形的分离轴,具体地,只需要查找最近顶点对及其所在边的法向量,若能找到分离向量把最近顶点对分隔开,则两个凸边形没有碰撞即飞机没有发生碰撞(无危险接近)。否则继续判断最近点所在的四条潜在分离轴,只要找到一条分离轴,则说明飞机无危险接近,若找不到则说明两架飞机危险接近需要告警。图6所示为机翼碰撞情况的示例,其投影在直线M的两个最近点都在Tb凸边形里,即只需要检测一次碰撞检测算法即可,两个Tb凸边形则使用分离轴算法进行检测。

图6 基于最近点的A区碰撞检测示图

3 仿真实验及分析

为研究不同算法对于最终效率的影响,本文分别对传统的包围盒算法、传统分离轴算法、基于最近点的检测算法进行对比实验,观测不同算法在整个飞机碰撞检测实验中所使用的时间。并且通过对比不使用弧形检测以及使用弧形检测的算法误警次数来研究顶点弧形检测对降低虚警率的有效性。

本文使用Qt框架来模拟50架飞机危险接近的仿真实验。首先生成飞机的关键尺寸如表1所示,关键尺寸根据普通客机轮廓模拟所得。设定初始位置与方向角度,设置危险接近阈值SPTP为50 m。然后用定时器模拟飞机的运动状态和轨迹,从而模拟飞机之间的危险接近情形。实验模拟了机场场面几个重要区域,包括跑道、多个滑行道、若干停机坪等。

表1 飞机关键尺寸

图7表示使用不同算法时,算法运行时间随着场面飞机数量增加而变化的过程。其中圆形标注折线表示传统包围盒算法,三角形标注折线表示传统分离轴算法,方形折线表示基于最近点的检测算法。飞机数量从10架逐渐增长至50架。由图7可知,传统包围盒算法随着检测目标的增加运行时间增长速度最快,表明此算法运行效率最低。传统分离轴算法检测时间虽然低于包围盒算法,但是波动幅度最大,这是由于在有n个目标情况下,B区碰撞前时间复杂度为((n2+n)/2)即O(n2),传统分离轴算法由于最多要检测8条分离轴,其时间复杂度增高为8×O(n2),A区需要检测飞机模型的5个凸边形即要查找17×5次分离轴,时间复杂度则增加到85×O(n2)。本文改进的基于最近点的检测算法相对最平稳,运行时间也最低,而且随着飞机数量的增加,运行时间有趋近于稳定的趋势,说明基于最近点分离轴的算法可有效提高检测速度。

图7 不同算法的运行时间对比

仿真实验部分截图如图8所示,分别代表机场场面飞机机翼、机头、机尾之间可能的危险接近情形。图8(a)为两飞机机翼危险接近,一般会发生在停机坪飞机需要推出或者进入停机位时产生的擦碰行为。图8(b)也是可能会发生的擦碰事件,由于牵引车牵引飞机时很可能由于视线盲区等因素,没注意到正在移动的飞机而造成机身擦碰。若加入了冲突告警系统,程序可以监控飞机之间的安全距离,当B区碰撞时发出B区危险接近告警,紧接着进入A区告警检测程序,如继续接近,则A区检测到碰撞或者重合,则持续发出A区危险接近告警。

图8 飞机二级碰撞检测告警

在进行顶点检测时,对顶点进行了弧形处理。为研究弧形检测对虚警率的影响,模拟了30架飞机危险接近的场景,对误警进行研究。通过计算误警次数与总的告警次数比值得到误警率如表2所示。可以看出,进行了弧形检测的碰撞算法误警率更低,证明了本文算法的有效性。

表2 算法误警率对比表

这种层层递进的检测方法可以大大简化算法时间复杂度,但每次都对场面的所有飞机进行B区碰撞检测依然不够优化,所以实验当中需要对场面再进行区域的划分,分为跑道、滑行道、停机坪等区域。每次得到目标物体的新坐标和运动方向时,则还原出物体模型,然后记录下其坐标点当前所在区域,并判断其属于运动目标或是静止目标,这里通过对比当前坐标与上一次坐标可以判断飞机是否有移动,当前场面区域所有目标更新完成后可依次对各区域进行运动目标扫描,所以每个运动目标只需要和其所在区域的其他运动目标做碰撞检测,避免进行远距离检测,可更进一步减少程序算法的时间复杂度。如果飞机坐标恰好处在区域分界线上也不用进行额外处理,因为每个区域检测都会把其边界处的目标一起检测,所以边界处的飞机会被检测两次。算法流程如图9所示。

图9 仿真实验算法流程

图9中,系统的所有飞机信息原则上应该接入类似ADS-B、GPS技术、雷达等给出的机场场面上运动目标的坐标和航向信息,实现对机场场面上运动目标的可靠和高精度监视,并获取目标的其他属性信息。

4 结 语

机场场面危险接近主要包括航空器与航空器、航空器与机动车、机动车与机动车和两者与建筑物固定物的危险接近。机动车模型相对简单,所以,本文没有对机动车进行模拟仿真,然而,由于航空器本身外观形状比较复杂,直接对其进行冲突碰撞检测实现难度较大。因此,本文使用QT框架构建与还原航空器模型,建立告警区,演示了飞机之间危险接近情形。实验结果显示,使用基于最近点分离轴的碰撞检测算法可以有效减少检测速度,降低程序时间复杂度。本文提出的最近点危险接近算法可应用集成于实时获取飞机坐标位置和其他信息的机场场面监视系统中,为其进行场面预警和告警提供理论支持。