基于蒙特卡洛法的无人机飞行冲突解脱安全评估*

谷志鸣，高文明，魏潇龙，姚登凯

（1.解放军91899部队，辽宁葫芦岛125001；2.空军工程大学空管领航学院，西安710051）

基于蒙特卡洛法的无人机飞行冲突解脱安全评估*

谷志鸣1，高文明2，魏潇龙2，姚登凯2

（1.解放军91899部队，辽宁葫芦岛125001；2.空军工程大学空管领航学院，西安710051）

冲突解脱技术是无人机与有人机共域飞行的前提保障。针对目前缺少对冲突解脱技术安全评估的方法，提出运用蒙特卡洛法对飞行冲突进行仿真模拟，得出冲突解脱算法的安全效率。提出基于改进蚁群算法的冲突解脱技术，实现无人机的飞行冲突解脱；利用蒙特卡洛法，对飞行冲突过程进行大规模仿真，计算冲突解脱效率，与基本蚁群算法进行对比，并从安全角度对结果进行分析。提出的思路可为未来无人机空域运行安全评估体系的构建提供一种理论参考。

无人机，蚁群算法，蒙特卡洛，冲突解脱

0 引言

无人驾驶航空器即无人机，因其体积小、使用风险小，成本低、对环境要求低等诸多优点，在军事和民用领域受到青睐［1］。随着无人机技术的发展，无人机早已具备了全空域飞行的能力，但由于“感知-避让”功能的不完善，国内外无人机的管制一般都采用划设隔离空域的方式运行［2］，限制了无人机在各领域的应用，为使无人机能充分发挥它的作用，找到一种可靠的飞行冲突解脱技术成为目前无人机系统设计的关键技术之一［3］。

目前，国内外对无人机冲突解脱技术的研究有很多，但是绝大多数研究都集中在冲突解脱算法的有效性上，从算法的可靠性以及无人机空域飞行安全的角度检验冲突解脱算法性能的研究很少。在国外，M.Garcia［4］，Eva Crück［5］在冲突解脱算法上都提出了自己的观点，但研究中并未对算法的可靠性上未加证明，很大程度上降低了算法应用于实际工程的可能性。Jose Asmat［6］设计了一种利用TCAS（Traffic Alert Collision Avoidance System）技术来进行无人机协同方式下的冲突解脱技术，并用Monte Carlo的仿真验证了冲突解脱方案的安全性能；在国内方面对无人机评估主要集中于任务执行效率方面，王渊［7］、崔莉薇［8］等分别应用不同的智能算法，实现了飞行冲突解脱，但仅仅比较了解脱航迹的长度和算法运算速度，未对算法的可靠性进行说明；也有使用风险评价指数矩阵法［9］、层次分析法［10］、多级模糊综合评判法［11］等方法进行无人机安全评估，但相对数量较少。

鉴于此，本文基于蚁群算法提出了一种无人机飞行冲突解脱技术，再利用蒙特卡洛法（MC，Monte Carlo）对改进的算法进行可靠性分析，从安全的角度对算法的性能进行比较。

1 蒙特卡洛方法简介

随着现代计算机技术的飞速发展，蒙特卡洛法已经成为人们解决复杂统计模型和随机事件模拟的主要工具。蒙特卡洛法又称为随机模拟法或统计模拟法，属于计算数学的一个分支，其实质是按一定概率分布产生随机数的方法来模拟实际中可能出现的随机现象，通过利用计算机软件进行大规模仿真实验，得到模拟的实验数据，在此实验的基础上进行分析判断，得到实际问题中可能出现的规律或求解方法。在现实生活中进行工程实验时，试验有可能高风险，耗费高，耗时长甚至具有破坏性，不可能通过反复试验进行实验数据的采集，此时蒙特卡洛法不失为最简单、经济、实用的方法。

本文研究的是无人机飞行冲突解脱问题，不可能在安全性未达标的情况下在现实中进行冲突解脱效率测试，因而采取应用计算机软件进行仿真模拟。飞机在飞行时由于设备精度，飞行员操作误差，环境影响等因素，飞行轨迹具有随机性，具有蒙特卡洛方法的特征，故而应用蒙特卡洛法进行仿真，因涉及安全的因素十分复杂，本文将所有因素，在综合作用下可以假定为高斯分布［13］。进行大规模的仿真，得出无人机冲突解脱算法成功避险的概率，并对结果进行分析。

2 改进蚁群算法的冲突解脱技术

蚁群算法作为一种最新提出的仿生进化算法具有:鲁棒性强、并行计算能力、全局搜索能力、正反馈机制、易于与其他算法混合等优点［14］。目前为止，蚁群算法已经成功解决了旅行商问题、指派问题、调度问题、车辆路由问题、网络路由问题等组合优化问题，且与旅行商问题具有一定的相似性，但由于蚁群算法具有搜索时间长、易陷入局部解两大缺点，必须要加以改善才能适应无人机冲突解脱的复杂性与对时效性的要求。

在传统蚁群算法中，一般将节点和节点之间的距离的倒数作为启发因子，如式（1）:

式中:dij为节点i到节点j的距离。蚂蚁k由状态i向j转移的概率选择公式为:

式中:Pij（kt）为t时刻蚂蚁k从节点i转移至j的概率为t时刻节点i到j路径上的信息素浓度；为节点j的启发函数；allowedk为蚂蚁k下一步可能到达的路径点集；α，β分别表示的作用程度。

在所有蚂蚁进行完一次路径规划后，则需要进行信息素的更新，信息素更新公式为:

在无人机路径规划问题中，有时候最优解与次优解之间会相差较大距离，甚至不在同一方向上。最大最小蚂蚁系统中只有最优蚂蚁才释放信息素，将所有蚂蚁趋向最优蚂蚁附近，当最优蚂蚁附近的解与真实的最优解之间差距较大时，最优解就有可能被错过，对此，引入基于排序的蚂蚁系统。每次迭代完成，对所有蚂蚁进行排序，除最优蚂蚁释放信息素外，适应度为前γ的蚂蚁都进行信息素的释放，信息素更新公式为:

在完成一次信息素更新之后，一次循环结束，对形成的路径进行适应性评价，适应性函数为:

其中:w1，w2，w3为权重；J为综合代价；Js为矩形空域威胁代价；Jr为圆形空域威胁代价；Ja为动态航空器的综合威胁代价；Jl为无人机的航程约束代价。

无人机的飞行冲突解脱运用了动态路径规划的原理，在每完成一次路径规划之后，进行一次状态转移，并对空域态势进行再次探测与更新，基于最新的态势信息，无人机进行航路的重规划，不断滚动前进，直至到达终点。

本文构建的冲突场景为航线交叉相遇下的飞行冲突，结合我国当前航空器运行安全间隔的划分标准［15］，根据无人机每次飞行与其他航空器的最小间隔距离，对无人机运行的安全状况进行分类。当无人机与有人机之间的飞行间隔小于1.76 km，则认为无人机存在极高的相撞风险，记为一次严重事故。当航空器间的距离在10 km～15 km之间时，则认为无人机存在发生飞行冲突的潜在风险。在10 km～15 km的间隔范围内虽然不算一次事故，但对其进行统计有利于无人机冲突解脱反应距离的设置。具体的事故风险等级划分如表1所示。

表1 事故风险等级划分

改进算法的飞行冲突避让流程如图1所示。

3 仿真结果

本文利用Matlab2008进行仿真，在100km×100km的空域范围内分别构造了单机冲突场景和双机冲突场景，单机冲突分为45°交叉角和90°交叉角两种情况，双机冲突为两种角度的综合。有人机驾驶的航空器按照飞行计划飞行。无人机在空域运行过程中需要避开空域中运行的航空器及各类不可进入的空域，T代表训练空域，D代表空中危险区，F代表空中禁区，Start为无人机某一航段起始点，Goal为该航段终点。无人机冲突解脱安全性评估的运行环境及飞行路径如图2所示。

无人机冲突解脱过程中各类航空器的综合轨迹如图3所示。

图1 基于改进算法的飞行冲突避让流程图

图2 无人机空域运行环境

图3 无人机冲突解脱示意图

本文评估对象为无人机自主冲突解脱技术，重点是评估其安全性水平，因此，管制员与无人机操作员的影响因素被去除。而有人机飞行员并不与无人机进行飞行冲突解脱的协同，将会驾驶飞机按计划飞行，航空器在运行过程中可能会受到风、人为因素影响、设备运行误差的扰动，在综合作用下可假定为高斯分布。

本文分别对基本蚁群算法和改进蚁群算法的冲突解脱技术进行模拟，分为单机冲突和双机冲突，以检验各算法对空域复杂度增加的情况下的冲突解脱安全性水平，其中单机冲突按交叉角分为45°交叉角和90°交叉角两种情况，针对每一种情况分别进行10万次的蒙特卡洛仿真实验，测试冲突解脱算法的安全性水平，得出的数据如下页表2、表3。

对比表2与表3可以发现，基本蚁群算法与改进蚁群算法在90°交叉角上很好地防止了严重事故和危险接近的发生，但是改进算法在飞行冲突和存在风险两个危险等级上改善不明显。在单机45°交叉角和双机冲突上，改进蚁群算法对比基本算法在事故率上有了很明显的减少，但按照美军提出的无人机运行安全目标水平105 h内20次事故的标准还有较大的差距［15］。对比ICAO提出的10-7次事故/h的标准则可判定无人机的安全水平无法达到有人机的运行标准。说明改进的算法还需针对这一情况进行进一步的改善，来降低无人机冲突解脱过程中的风险。

表2 基于基本蚁群算法事故率

表3 改进算法下的事故率

4 结论

当前国内有关无人机冲突解脱技术的文献较多，但大部分研究都集中在冲突解脱技术的有效性上，很少有针对冲突解脱安全性方面的验证，并且目前国内针对无人机空域运行安全评估体系还很缺乏。因此，利用蒙特卡洛方法针对无人机飞行冲突解脱技术的安全性进行了模拟仿真，仿真结果有较大改善，但安全性仍然无法满足空域运行的要求。得出无人机对45°交叉相遇下的冲突解脱能力存在严重的不足，应当作为安全瓶颈加以重点研究。本文在构建无人机空域运行环境的过程中作了很多简化，与实际环境具有较大差异，但重点在于引入蒙特卡洛法针对无人机飞行冲突解脱技术的安全性进行模拟，从安全的角度考虑冲突解脱算法的性能，可以为未来无人机空域运行安全评估体系的构建提供一种理论参考。

［1］陈金良，高文明，史际刚.无人机飞行管理［M］.西安:西北工业大学出版社，2014:1-2.

［2］李春锦，文泾.无人机系统的运行管理［M］.北京:北京航空航天大学出版社，2011.5.

［3］SHIN H S，ANTONIOS T，WHITE B A，et al.UAV Conflict Detection and Resolution forStatic and Dynamic Obstacles［C］//Guidance，Navigation and Control Conference and Exhibit.Honolulu，Hawaii:American Institute of Aeronautics and Astronautics，2008.

［4］GARCIA M，VIGURIA A，OLLERO A.Dynamic graph-search algorithm for global path planning in presence of hazardous weather［J］.J Intell Robot Syst，2013，69:285-295.

［5］Eva Crück，JOHN L.Sense and avoid system for a MALE UAV［C］//Guidance，Navigation and Control Conference and Exhibit.Hilton Head，South Carolina:American Institute of Aeronautics and Astronautics，2007.

［6］JOSE A，BRETT R，JESICA U，et al.Unmanned aerial collision avoidance system［R］.George Mason University:Department of Systems Engineering and Operations Research，2006.

［7］王渊，孙秀霞，刘树光，等.基于改进人工蜂群算法的多机飞行冲突解脱策略［J］.空军工程大学学报（自然科学版），2014，15（3）:10-14.

［8］崔莉薇，石为人，刘祥明，等.基于遗传粒子群算法的飞行冲突解脱［J］.计算机工程与应用，2013，49（7），263-266.

［9］阳再清，刘志强.舰载无人机飞行安全性评估方法研究［J］.宇航计测技术，2014，34（6）:84-89.

［10］魏法杰，卢珊，张羽.某实际型号无人机试飞风险评估案例［J］.中国管理科学，2014，22（11）:199-204.

［11］吴忠杰，张耀中，王强.无人机复杂气象威胁建模及评估方法［J］.计算机应用，2013，33（4）:1179-1182.

［12］魏潇龙，姚登凯，戴喆，等.基于路径规划的无人机飞行冲突解脱技术［J］.火力与指挥控制，2016，41（10）: 48-54.

［13］闫丽萍，夏元清，杨毅.随机过程理论及其在自动控制中的应用［M］.北京:国防工业出版社，2012.4

［14］宋锦娟.一种改进的蚁群算法及其在最短路径问题中的应用［D］.太原:中北大学，2013.

［15］张兆宁，王莉莉，李冬宾.飞行间隔安全评估引论［M］.北京:科学出版社，2009.

UAV Flight Conflict Resolution Safety Assessment Technique Based on Monte Carlo Method

GU Zhi-ming1，GAO Wen-ming2，WEI Xiao-long2，YAO Deng-kai2
（1.Unit 91899 of PLA，Huludao 125001，China；2.School of Air Traffic Control and Navigation，Air Force Engineering University，Xi’an 710051，China）

Conflict resolution technology is a prerequisite for UAV.Aiming at the lack of the safety assessment method of conflict resolution technology，this paper uses Monte Carlo method to simulate the flight conflict and reached the efficiency of conflict resolution algorithm.In this paper，an improved ant colony algorithm is proposed to achieve the flight conflict resolution；using the Monte Carlo method to simulate the flight conflict process and then compare the efficiency with basic ant colony algorithm.The ideas presented in this paper can provide a theoretical reference for the construction of safety assessment system in the UAV airspace operation in the future.

UAV，ant colony algorithm，Monte Carlo，conflict resolution

V271.4

A

1002-0640（2017）04-0158-04

2016-03-16

2016-04-27

省部级自然科学基金资助项目（2015JM7364）

谷志鸣（1988-），男，河北无极人，硕士研究生。研究方向：空域规划与空中交通流量管理。