基于ADS-B的无人机感知与规避蚁群算法模型

袁梦婷, 时宏伟

(四川大学 计算机学院, 四川 成都 610065)

随着近年无人机的迅猛发展，对无人机监视指挥和安全保障的需求也愈加强烈和紧迫。为了避免无人机与有人机的冲突，业界一直采用划分隔离空域的方法；而对于无人机与其他障碍物之间的冲突与碰撞，小、微型民用无人机仍主要采用视距内飞行的方式[1]。但在国家空域资源有限背景下，伴随无人机技术的愈发进步，混合共享空域与低空开放必将成为发展趋势。当无人机所处空域环境愈发复杂，碰撞规避问题将成为严峻的挑战。因此，无人机感知与规避(sense and avoid,S&A)系统的研究与落地，将助力无人机突破隔离空域限制，推动无人机更为广泛的实际应用。

近年来，国际民航组织大力推动广播式自动相关监视(automatic dependent surveillance-broadcast,ADS-B)技术的应用，将其作为全球航空运输系统中新一代监视技术的主要方向。美国、欧洲、中国也都在逐步完成ADS-B的相关落地计划，未来将实现ADS-B技术更广泛的应用。而将ADS-B技术应用在无人机上或也将成为发展的趋势。

目前，国内外学者围绕飞行器的避撞问题展开了大量卓有成效的研究，为无人机S&A系统的研究提供了极有价值的参考。

在冲突的探测上，主要有几何法和概率法两类方法。几何法多通过划分安全区，并基于当前飞行状态对未来航迹进行线性预测，判定安全区是否存在重叠，而民航飞机所用的空中防撞系统(traffic collision avoidance system,TCAS)就是采用几何法[2]。概率法则考虑了如风扰动、导航误差等随机因素，能计算出冲突发生的可能性，更精确但也更复杂。但在实际应用中，降低并消除碰撞风险才是空中安全技术的关键[2]。并且，考虑到ADS-B技术能提供精确全面的实时飞行状态和意图信息，且具有较高更新率，本文采用基于几何法的确定型冲突探测模型。

在冲突的解脱上，较多采用的方法是航路规划，包括人工势场法、以遗传算法为代表的启发式算法、A*算法等[1-3]。不同算法各有优缺点，因此也有学者将算法进行融合。但航路规划多是基于几何学进行搜索，不考虑飞行器动力学约束，且搜索效率取决于规划空间大小[4]。而不少学者对算法的改进集中在算法本身的缺陷和求解速度上，优质航路的判定仅参考延误距离这一条标准。对此，本文提出引入综合启发函数的蚁群解脱模型，从航路的平滑度和延误两方面进行了考虑。

1 无人机感知与规避S&A系统

1.1 基本需求

无人机的冲突规避不同于有人机。一方面，无人机缺少飞行员执行“看见-规避”；另一方面，民航飞机可以采用空中交通管制(air traffic control,ATC)服务、TCAS的避撞建议，而满足飞行高度门槛的无人机却大多囿于性能难以达到TCAS运行要求。因此，无人机需要特定的S&A系统，代替飞行员“看见-规避”以克服潜在威胁，包括其他飞行器(如飞机、滑翔伞等)以及有碰撞危险的物体(如建筑物等)。

为了保障飞行安全，S&A系统需要满足2层功能需求：首先，该系统需通过确保飞行器之间保持适当的距离来降低碰撞的可能性，以避免更危险的状态，此为自主间隔保持；其次，当自主间隔保持操作也无法改变两者相撞的趋势，飞行器处于更危险的状态，就需要在即将产生实际碰撞时，进行碰撞规避。自主间隔保持与碰撞规避原理相似，不过前者的机动开始得更早，并且在机动措施的选择上，前者可选取轻缓的机动操作，后者的紧急度更高[5]。

自主间隔保持和碰撞规避的实现大致可分为3个部分[6]：①感知，即利用机载传感器监视周围空域环境；②探测，即判定是否存在潜在冲突，并评估威胁程度；③规避，即通过生成规避策略与决策指令，由飞控装置执行机动，以降低威胁程度或消除威胁。

1.2 功能实现

为了实现无人机进入国家空域后的自主间隔保持和碰撞规避，本文提出一种基于ADS-B监视技术的蚁群算法模型。

本文研究的模型功能逻辑架构如图1所示。该模型在感知部分采用ADS-B技术，基于ADS-B信息进行冲突的探测与规避；冲突探测部分包括水平初选、水平探测、垂直探测3个步骤，通过三维空间内的距离判定来确定冲突目标；规避策略来自于冲突解脱模型，该模型基于蚁群算法进行航路重规划，并对蚁群算法的2个关键步骤(状态转移和信息素更新)进行改进，引入综合启发函数、排序机制，以获得优质解脱路径及策略。

图1 S&A系统功能模型架构实现

2 ADS-B原理特点

为了实现环境感知，无人机需要配备传感设备。其传感设备包括合作式和非合作式2种[7]。ADS-B属于一种合作式传感器，依靠全球导航卫星系统(global navigation satellite system,GNSS)和先进的空-空、空-地数据链通信技术实现多种信息的生成和远距离交换。

依照信息传输的方向，ADS-B应用功能分为IN和OUT，其中OUT是基本功能。ADS-B的工作原理可概述为：配备了ADS-B OUT的飞行器通过机载发射器以一定周期主动向外广播飞行器的各种信息，这些信息来自于GNSS和其他机载设备，主要包括飞行器识别信息、四维位置及速度信息、其他附加信息(航向、飞行员输入信息、航迹改变关键点等)[8]。地面站和其他配备了ADS-B IN的飞行器最终会接收这些ADS-B OUT信息，以实现对空监视与相互感知。此外，地面站也可以发送空中交通情报服务广播(traffic information service-broadcast,TIS-B)和飞行情报服务广播(flight information service-broadcast,FIS-B)给配备了ADS-B IN的飞行器。

作为一种新型对空监视技术，与传统二次监视雷达(secondary surveillance radar,SSR)相比，ADS-B具有提供信息内容更全面、定位更精确、更新率更高等优势[9]。因此，ADS-B被有效应用在空中交通管制、空对空协同、机场场面监视等方面，有助于提高飞行的安全性和空管的高效性。在全球范围内，ADS-B的部署都在积极推进当中。目前，我国在民用航空中正全面启动ADS-B的管制运行，也已基本完成ADS-B地面设施布局，未来还将持续推进、拓展其建设及应用。

3 冲突探测方法分析

保护区和安全间隔的明确是冲突探测的基础。探测和解脱算法采用圆柱体保护区模型作为飞行器实体的抽象，当目标飞行器进入该区域，则表示发生了碰撞，其大小主要取决于飞行器性能；而间隔要求是在保护区的基础上，将区域进一步扩展，其大小是根据所处空域、遭遇场景等多种因素确定的[4]。碰撞规避、自主间隔保持等功能的实现基础是制定不同的间隔要求。综合考虑飞行安全和算法的易实现性，在冲突探测与解脱算法模型分析中不再区分碰撞规避和自主间隔保持，而基于混合飞行场景，参考RTCA标准及文献[8]，将安全间隔标准统一设定为R=9.26 km,H=0.609 6 km。

而对于混合飞行场景中的飞行器，ADS-B提供的关键信息包括WGS-84(world geodetic system-1984)坐标系下的三维位置信息、水平速度及航向角、垂直速度及升降标识符，为了方便模型建立，需要将其转换为空间直角坐标系下的信息。在此基础上，冲突探测功能的完成包括水平初选、水平探测和垂直探测3个部分。

3.1 水平初选

水平初选的主要思想是排除明显不可能冲突的目标,在此指逐渐远离的飞行器。在X-Y二维水平面上,本机A的位置坐标为(x1,y1),入侵机B的位置坐标为(x2,y2),A的航速矢量为VAhori=(v1horicosφ1,v1horisinφ1),B的航速矢量为VBhori=(v2horicosφ2,v2horisinφ2)。

相对于本机A,入侵机B的相对位置与相对航速分别为

水平初选的判断依据即为[8,10]

S0=Pr·Vrhori

(3)

若S0≥0则表示两机正在逐渐远离或持续保持间隔,而S0<0则表示两机需要进一步判断。

3.2 水平探测

经过初步探测,快速过滤掉部分飞行器。而对于逐渐靠近的飞行器,还需要进行距离计算,主要思路为计算最接近点(closet point of approach,CPA)处对应的水平错开距离(horizontal miss distance,HMD)[9],将其与水平最小安全间隔R进行比较,如图2所示。

图2 水平冲突探测图

根据几何知识,有

(4)

(5)

3.3 垂直探测

在垂直方向上,考虑X-Z二维平面上,飞行器A的位置坐标为(x1,z1),B的位置坐标为(x2,z2),A的航速矢量为VAvert=(v1horicosφ1,v1vert),B的航速矢量为VBvert=(v2horicosφ2,v2vert)。

相对于本机A,入侵机B的相对航速为

Vrvert=(v2horicosφ2-v1horicosφ1,v2vert-v1vert)

(6)

入侵机B的相对飞行情景如图3所示,图中的矩形NMFE为在X-Z面上的安全间隔。

图3 垂直冲突探测图

B的相对航迹线对应斜率为

(7)

根据几何知识,可通过以下公式进行垂直冲突判定[8]

若S1≥0且S2≥0,则表明在垂直面上,A和B之间将无冲突产生;反之,则需要进行冲突解脱。

4 冲突解脱方法分析

4.1 问题描述

解脱算法是一种离散化航路规划方法,按照等时长将解脱区域内的各航路段划分为K步,每一步可选择的策略有27种,包括速度调整(减速20%、保持初始速度、加速20%)、航向角调整(左转30°、保持初始航向角、右转30°)、俯仰角调整(增加3°、保持初始俯仰角、减少3°)以及同时调整,记为C1～C27。

经过航路划分后,n机冲突解脱问题可以进一步描述为:n架飞行器为一批次,对应n条冲突航路。其中,每架飞行器在每一步选择一种策略,经过K步后到达最终位置,要求其最终到达点与原计划目标点的延误距离尽可能小,并且此过程不能存在与其他飞行器的冲突。

则经过K步后,飞行器i的最终位置与目的地之间的延误距离为

(10)

目标函数即为

(11)

约束条件为无冲突产生,即在任意步k(1≤k≤K)后,飞行器i(1≤i≤n)与飞行器j(1≤j≤n,且j≠i)之间的距离满足下式

(12)

(13)

式中：R为水平最小安全间隔；H/2为垂直最小安全间隔。

4.2 蚁群算法模型

为了寻找无冲突的优质航路,模型采用蚁群算法进行分析。蚁群算法是一种用来寻找优化路径的概率型算法,这种算法具有分布计算、信息正反馈和启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法。蚁群算法是经过迭代来寻找最优解,迭代过程中的状态转移和信息素更新是蚁群算法的关键步骤。

首先,状态转移需要按照信息素浓度计算路段的被选概率,在此基础上采用轮盘赌方式进行随机选择;其中,概率的计算是状态转移的关键。假设每一次迭代过程中,均有M批次飞行器依次飞行。在第t次迭代中,第m(1≤m≤M)批次的某架飞行器正进行下一步选择时,选择策略Ci的概率为[11]

(14)

式中，τCi(t)为策略Ci对应路段的信息素值。该信息素值在经过此次迭代后将进行更新,更新过程按照(15)式进行

(15)

(16)

4.3 模型改进

目前,已有文献对蚁群算法的优化,主要围绕算法的核心步骤来进行[12-13]:①对初始信息素分布进行优化,例如引入人工势场法、遗传算法等方法对解空间进行初步分析,进而差异化分布初始信息素,可以降低初期搜索的盲目性,加快收敛速度;②对状态转移方式与启发规则进行优化,例如引入参数的自适应机制,让前期搜索中启发信息占主导,后期搜索中信息素浓度占主导,可以改善蚁群算法易陷入局部最优的缺点,并权衡算法效率[9];③对信息素更新规则进行优化,例如引入最大最小蚁群、精英策略、排序机制等,可以避免陷入局部最优、加快算法收敛速度。

已有的优化方法多围绕蚁群算法自身缺点,强调提升全局寻优能力、避免陷入局部最优、加快收敛速度[12]。而在实际航路规划应用中,除环境因素外,无人机最大转弯角度、航程、最小航线段长度等限制都会成为规划的约束条件[14],也有部分文献基于启发式算法,将目标改为最小化路径综合代价,考虑飞行高度、路径长度、平滑度、障碍物威胁等[15-16],进而提高了特定威胁情景下的规划效果,但改进主要面向静态障碍物的避撞。

而本文围绕基于ADS-B的协同解脱,对模型状态转移方式、信息素更新方式进行改进,以优化算法本身缺点,并提高模型的适应性。

4.3.1 状态转移方式改进

基本解脱模型以信息素为路段选择的唯一标准,由于解空间较大又缺少启发部分,极易陷入局部最优。在飞行器冲突解脱情景中,优质航路的判定标准是综合性的。并且,在实际飞行中,最大转弯角度、最小航线段长度等限制使得平滑的航路更具可操作性,而最大航程限制等因素要求规划航路尽可能接近原航路。因此,引入综合启发部分,通过增强搜索随机性以避免局部最优问题,同时综合考虑无人机性能等约束条件以减少无效的随机搜索。

第一项因素为每步延误距离,若每步的延误距离较小,则航路会尽量接近原航路,最终延误距离也会较小。第二项因素为角度变化[11,17],作为第一项因素的补充,加强与原航路的接近度。第三项因素为每步航向转变度,旨在让航路平滑,减少大幅度变向的出现。类似的,第四项因素为每步速度转变度,旨在让速度的变化更加平缓。综合四项因素的启发函数即为

ηCi(t)=

(17)

经过以上改进,下一步策略Ci的选择概率为

(18)

式中,α和β表示各部分的相对重要程度。

4.3.2 信息素更新方式改进

基本蚁群解脱模型中,信息素更新方式采用的是蚁周模型,最终延误采用的是n架飞行器的总延误,但若存在其中一架飞行器最终延误较大,而其他飞行器最终延误较小的情况,这些被连累的较优质路径可能会因此被漏选。而另一种较为常用的蚁量模型则是考虑每一步延误,过于局部化而忽略了全局情况。因此,在原信息素更新方式上改进为采用每一架飞行器的最终延误。

并且,为了加快收敛,在改进中引入排序机制[11-12],让优质路径的信息素增加,而较差的路径信息素增量为0。因此,最终的信息素更新方式变为

(19)

5 仿真分析

为了充分检验模型的有效性,对冲突探测和冲突解脱分别设定情景进行仿真实验。实验的硬件运行环境主要为2.8 GHz的Intel Core i5处理器,4 GB内存;软件运行平台为MATLAB 9.1。

5.1 冲突探测仿真

模拟场景为多机(无人机与有人机混合)冲突探测。仿真实验中假设本机位于坐标原点,速度与航向随机生成,其周围40 km范围内存在100架目标飞行器,关键飞行状态数据按如下条件随机生成:

1) 目标飞行器速度值:vhori∈[180,360],vvert∈[-30,30],单位为km/h;

2) 目标飞行器水平航向：与X轴夹角φ∈[0,2π];

3) 目标飞行器坐标:x∈(9.26cosθ,40cosθ),y∈(9.26sinθ,40sinθ),θ∈(0,2π],z∈[-1.5,1.5],单位为km。

图4 冲突探测结果

图5 冲突概率分布

基于MATLAB进行100 000次蒙特卡洛实验,每次模拟探测域内均有100架目标飞行器。图4为单次实验结果,图5为蒙特卡洛统计结果。实验结果显示,在100架目标飞行器中,最终的平均冲突数量为7.185 5架,表明探测模型的过滤效果显著。

5.2 冲突解脱仿真

经过探测,能明显过滤出潜在冲突目标,随即进行解脱操作。一般情况下,面对探测出的多架冲突目标,可以在探测部分追加计算冲突的潜在发生时间,从而排列出先后顺序,赋予目标不同的优先级,依次实现双机或多机冲突解脱。

为了验证模型的可行性,分别对迎面遭遇、追尾遭遇、正侧向遭遇3种典型情况进行验证。迎面遭遇和正侧向遭遇场景中假设两机均以360 km/h的速度飞行,追尾遭遇场景中则分别以360 km/h和270 km/h的速度飞行。

相关参数设定为α=1,β=2,衰减系数ρ=0.3,信息素量Q=100,批次数M=20,总步数K=20,迭代次数为200次。

经过仿真,改进模型给出了图6的解脱策略。在3种场景中,最终总延误距离分别为1.490 2 km，0.833 2 km，1.408 8 km。

图6 两机冲突解脱

除简单的两机冲突场景外,还存在多机同时产生冲突的复杂情况。重新设定场景,假设存在4架飞行器同时进入解脱区域,表1为飞行器的初始飞行状态。

表1 飞行器初始状态

为了更好地体现模型优化的效果,对该冲突场景,分别采用遗传算法、基本蚁群算法、改进蚁群算法模型进行解脱,解脱结果与最优总延误距离的收敛过程如图7～8所示。

图7 四机冲突解脱

图8 收敛过程对比

并且,就无人机物理性能、航路质量和算法性能方面[18],选取航路长度、航路平滑度、最终延误距离和收敛性作为指标,对路径质量进行综合判断,得到表2的算法对比结果。

表2 四机冲突解脱效果对比

实验结果显示，在无人机物理性能方面，要求航路尽可能平滑，具有可操作性，改进模型与遗传算法、基本蚁群模型相比，在航向转变次数上略有优化，航路更加平滑；在航路质量方面，要求能耗尽可能小，即航路总长度较小，并且对原航路的偏离尽量小，改进模型优势相对明显；在算法性能上，蚁群算法收敛较遗传算法快，但也更易陷入局部最优，改进模型中，启发部分增强了搜索的随机性，求解速度受到影响，但排序机制的引入则加快了收敛，使得模型能快速找到较优解脱路径。

6 结 论

本文针对无人机感知与规避系统，充分利用ADS-B提供的实时动态航行信息，提出了确定型冲突探测模型和基于蚁群算法的冲突解脱模型；前者能有效过滤出无人机周围的冲突目标以待进行解脱，而后者能为无人机及冲突对象重新规划较优质的解脱路径。经仿真实验验证，探测模型的过滤效果良好，而解脱模型不仅能解决双机冲突，在复杂的多机冲突情景下也能提供较好的解脱路径。但基于条件有限，本文考虑的是较为理想情况下的感知与规避，天气因素影响、应用场景差别等诸多问题并未进行考虑。在未来的研究中，模型还需结合现实场景需求进行适应性改进，针对特殊应用场景进行更深入的探讨，并在算法性能与效果上实现进一步完善与优化。