甄 然，司 超，吴学礼，张建华，武晓晶

(1.河北科技大学电气工程学院，河北石家庄 050018；2.河北省生产过程自动化工程技术研究中心，河北石家庄 050018)



基于改进粒子群算法的飞行器冲突解脱方法研究

甄 然1,2，司 超1,2，吴学礼1,2，张建华1,2，武晓晶1,2

(1.河北科技大学电气工程学院，河北石家庄 050018；2.河北省生产过程自动化工程技术研究中心，河北石家庄 050018)

冲突解脱要求飞行器采用一种有效的方法来满足工作环境的限制。针对飞行器在多障碍环境下的冲突解脱问题，提出一种能够满足限制条件的改进粒子群算法(PSO)对冲突进行解脱。所提出的新算法(DARPSO)相对于经典粒子群算法有2个优点：第一，考虑了障碍对寻优过程的影响；第二，具有跳出局部极小的能力。仿真实验结果显示，所提出算法的优化效果要优于标准粒子群算法。将改进后的算法应用到飞行器冲突解脱过程中并进行仿真，结果表明，所提出的算法能够有效地指导飞行器躲避障碍，完成冲突解脱。

算法理论；飞行器；冲突探测；冲突解脱；粒子群算法

近年来，空中交通领域迅速发展，美国、日本等相继设立相关组织来适应新的空中交通发展[1]。空中交通管理中的一个安全问题就是飞机的冲突探测和解脱。由于飞机轨迹预测的准确性受到一些不确定因素的影响，比如雷达、导弹、气候等，所以，在冲突探测和解脱的过程中考虑障碍物等不确定因素的影响具有重要的意义[2-3]。

粒子群算法是基于种群优化的方法[4-7]，本文在粒子群算法的基础上，提出一种新的粒子群算法来满足冲突解脱过程中的限制条件，同时保持粒子间的多样性及跳出局部极小值的能力。

1 粒子群算法及拓展

(1)

(2)

在PSO中，随着每个粒子迭代速度的减小，会越来越接近0，这时所有的粒子会趋于一种平衡的状态，这些粒子没有足够的能力去探索和开发新的空间，极易陷入局部最优的情况[8-10]。所以，基于PSO的方法都必须具备跳出局部极小的能力。

文献[11—13]在PSO的基础上进行了改进，提出了机器人粒子群算法 (robotic particle swarm optimization, RPSO)，笔者将算法应用到机器人探测未知路径的过程中，并考虑了障碍对寻优过程的影响。RPSO类似PSO都是由一群粒子在未知空间中进行搜索[14-15]，那么，不同之处主要就是RPSO考虑了真实环境中的障碍回避。其他的不同点并不是很显著，包括对参数的初始化设置等。在RPSO中，每个粒子的速度和位置更新公式如式(3)和式(4)所示：

(3)

(4)

该算法在文献[12]中的测试结果显示，相对经典粒子群算法而言，RPSO能够跳出局部极小值，但是效果不明显。算法引入了约束条件对粒子的动作进行限制，这种方法能够基本保证算法在搜索过程中粒子的多样性，但仍存在收敛速率慢等问题。

文献[16]中提出了一种动态自适应的粒子群算法(DAPSO)，该方法将惯性权重改为具有动态特性的时变参数。DAPSO中粒子的速度和位置更新公式如式(5)和式(6)所示：

(5)

(6)

对比经典粒子群算法，DAPSO的速度更新公式(5)有2个显著的优点，随机数r1和r2的取值随着粒子数量和迭代次数随机改变，惯性权重的取值也受到粒子的数量和迭代次数的影响。并且在动态惯性权重改变的过程中引入了2个新的概念，分别是“进化速度”和“聚集度”，这2个因素在文献[17]中有介绍。通过引入这些新的概念，使算法跳出局部极小值的能力和算法收敛速度及精度有了显著的提升。

2 具有动态自适应特性的机器人粒子群算法

为了改善算法的性能，本文将第1部分中所提到的算法进行了有效的结合，在对上述算法改进策略分析的基础上提出了一种具有动态自适应特性的机器人粒子群算法(DARPSO)。在DARPSO中，每个粒子的速度和位置更新公式如式(7)和式(8)所示：

(7)

(8)

对比第1部分提到的算法，所提出的算法有2个优点，分别是考虑了在真实环境中的障碍躲避和增强了算法跳出局部极小的能力。其中惯性权重的取值与所提到的“进化速度因素”和“聚集度因素”2个因素有关。这种改进在飞行器冲突解脱领域是前所未有的。这些改变，不仅使算法没有陷入局部极值的情况，而且提高了粒子的搜索速度。这种方法非常迅速，因为在粒子工作的过程中都会对粒子群体每次迭代的状态进行检查。所提出的方法充分考虑了对粒子的限制，并针对粒子对目标进行搜索的问题提出了新的约束条件。许多学者也针对目标搜索问题介绍过一些约束[18]，本文中采用的约束条件为“粒子更新速度必须小于最大更新速度”和“考虑躲避障碍函数的计算”，这些约束条件能够帮助粒子完成指定的动作。本文在考虑躲避真实环境障碍的基础上，通过定义最大速度来解决早期的约束。事实上，这个最大值也用来作为公式(7)的最大边界。由于DARPSO在更新粒子位置时只需要进行简单的计算，所以上述2个约束条件也得到了解决。此外，在定义最大迭代次数上限的同时考虑了真实环境中飞行器的能源限制。

2.1 进化速度和聚集度

粒子的进化速度定义如式(9)所示：

(9)

全部粒子的聚集度定义如式(10)所示：

(10)

2.2 动态惯性权重的迭代策略

在粒子群算法的搜索过程中，粒子的进化速度和聚集度是2个特有的参数。所以，本文中惯性权重必须跟随进化速度和聚集度的变化而变化，计算公式如式(11)所示：

(11)

如果粒子寻找最优值的速度较慢，为了保证粒子更新速度，则需要减少粒子的数量。也就是说，如果粒子的位置彼此靠近，那么聚集度值就会变大。通过减小进化速度或者增大聚集度值就会增大惯性权重的影响并且削弱粒子当前最优和全局最优的跟踪能力。简而言之，这些影响因素保持了粒子之间的多样性，是完成搜寻任务的重要保障。

(12)

文献[20]表示，在智能搜寻的过程中，将参数设置为c2>c1，这表示粒子在搜索目标任务中，社会认知部分成为主要内容。一般来说，c2的值越大收敛速度就越快。然而，相对于c1来说，非常大的c2会导致陷入局部极值的概率变大。出于此因，提出了一种新的方法定义c2的值，定义如式(13)所示：

c2=min((NR×ρ+c1),2c1)。

(13)

式中NR是粒子数量，同时ρ=0.4。在考虑粒子数量和初值的情况下研究了c2的计算公式，将式(13)引入到DARPSO中，在后续内容中经过一些不同环境中的实验，可知此计算方法更简单并且拥有较高的效率。当式(13)取最小值时，粒子数量的增长可以有效地控制参数c2的变化。一般的，c1=2，理想情况是在每次迭代过后c1的值稍微增大而c2的值稍微减小。感应系数c3定义如式(14)所示：

c3=2s(c1+c2)。

(14)

式中s是传感器的数量。如果粒子和障碍物的距离很远，粒子检测不到障碍物，则s=0，c3=0。如果粒子和障碍物之间的距离缩短的话，那么c3的值就会增大，所以粒子会更多的考虑障碍物的因素并且尽可能与之保持距离。总之，DARPSO能够保持粒子和目标搜索约束之间的多样性，并保证计算简单容易实现。

3 冲突解脱及仿真

3.1 算法有效性的验证

一般来说，飞行器在同高度飞行时发生冲突，解脱方法一般有以下3种策略：1)调整航向的大小；2)改变航行速度；3)变化飞行高度。文献[21]提出了一种冲突探测的几何结构，并且给出了飞行冲突探测的边界条件，以及在发生冲突时的航向角所需的调整量。本文将采用调整航向角的方法来对飞行器冲突进行解脱。

为了证明所提出算法的有效性，以下对比了改进的PSO和经典PSO在不同情况下的收敛速度，最优解以及收敛成功率。适应度函数选取2个基准测试函数，测试函数的参数设置如表1所示，测试结果如表2所示，其中稳定代数表示20次试验达到最优时得到的迭代次数的平均值。2个基准测试函数分别是Sphere函数和Griewank函数。

Sphere函数：

Griewank函数：

由表1和表2中的数据可以看出，所提出的算法在跳出局部最优方面的能力有所增强，收敛精度和速度也有了显著的提升。对比经典PSO，所提出的方法在搜索成功率和解决质量上更加突出。

表1 测试函数的参数设置

表2 测试函数的测试结果

3.2 冲突解脱仿真模拟

飞行冲突解脱问题的目标是，避免冲突时生成的新航迹同原航迹偏差最小，从而实现航迹最短，燃耗最小。本文所采用的冲突解脱目标函数为

式中dik和djk为飞机i和j在第k次迭代的位置与原航迹点的距离。为了飞行安全，必须时刻保持同一冲突区内的任意2架飞机间的距离大于最小安全间隔R，所以冲突解脱问题还需要满足的约束条件为dij>R,其中R的取值[22]一般为20 km。

以2架飞机在同高度的障碍区域的冲突解脱问题进行仿真验证。首先构建一个30 km×30 km的冲突避障区域，并设置2架飞机的起点和终点，如图1所示。其中小方框代表2架飞行器的起点，五角星代表终点，小圆圈表示障碍点。在障碍点处生成高度为1 km的山峰，三维地形图如图2所示。如果2架飞行器以相同的速度飞往目标地点，那么在区域的中心点会发生相撞，如图3所示。图4是2架飞行器发生冲突时DARPSO生成的解脱航迹，从图中可以看出，所提出的改进粒子群算法能够完成对冲突的解脱，并且能够使解脱后的航迹平滑，与原航迹偏差较小。

图1 初始化飞行器起始点、障碍物坐标Fig.1 Initial positions of aircraft goals and obstacles

图2 障碍的三维地形图Fig.2 Three-dimensional terrain of the obstacles

图3 2架飞行器冲突示意图Fig.3 Conflict schematic view of two aircrafts

图4 飞行器冲突解脱航迹Fig.4 Aircrafts conflict resolution trajectory

4 结 语

本文针对飞行器冲突解脱问题，在PSO的基础上提出一种新的解脱算法DARPSO，建立了适合解决问题的粒子更新表达式。DARPSO考虑了真实环境中障碍的影响，保证了粒子在搜索过程中的多样性，仿真结果显示DARPSO跳出局部极小的能力和收敛速度有了显著提升。该算法作为一种通用的优化算法，也可以应用到机器人路径规划、无人机航迹规划等问题中，具有广泛的应用价值。本文不足之处在于只考虑了二维空域下的解脱策略，由于飞行器数量的增加以及不确定环境中的其他影响因素的存在，有待于将飞行器冲突解脱问题拓展到三维空域中进行更加深入的研究。

[1] 王利亚.提高空域使用效率确保飞行安全顺畅[J].空中交通管理，2011(6)：4-6.

WANG Liya. Improving efficiency in use of airspace to ensure flight safety and smoothness[J]. Air Traffic Management, 2011 (6):4-6.

[2] 崔德光,程朋,耿睿. 空中交通管制自动化中的冲突概率分析[J].清华大学学报(自然科学版), 2000, 40(11)：119-122.

CUI Deguang, CHENG Peng, GENG Rui. Probability analysis of collision in Automation Air Traffic Control[J]. Journal of Tsinghua University(Science and Technology),2000, 40(11):119-122.

[3] 王世锦，隋东．低空空域飞行冲突风险研究[J]．西南交通大学学报,2010, 45(1)：116-123.

WANG Shijing, SUI Dong. Risk analysis of conflict in low altitude airspace[J]. Journal of Southwest Jiaotong University, 2010, 45(1):116-123.

[4] MARINI F, WALCZAK B. Particle swarm optimization(PSO)：A tutorial[J]. Chemometrics and Intelligent Laboratory Systems, 2015, 49(1):153-165.

[5] 张万绪，张向兰，李莹．基于改进粒子群算法的智能机器人路径规划[J]．计算机应用，2014, 34(2)：510-513.

ZHANG Wanxu, ZHANG Xianglan, LI Ying. Path planning for intelligent robots based on improved particle swarm optimization algorithm[J]. Journal of Computer Applications, 2014, 34(2):510-513.

[6] 甄然，王开拓，吴学礼．基于数字地图预处理的飞行器航及规划[J]．河北科技大学学报，2015, 36(2)：195-202.

ZHEN Ran, WANG Kaituo, WU Xueli. Aircraft route planning based on digital map pre-treatment[J]. Journal of Hebei University of Science and Technology, 2015, 36(2): 195-202．

[7] 任子晖，王坚.加速收敛的粒子群优化算法[J].控制与决策，2011,26(2)：201-206.

REN Zihui, WANG Jian. Accelerate convergence particle swarm optimization algorithm[J]. Control and Decision, 2011, 26(2):201-206.

[8] KENNEDY M, EBERHART B. Particle swarm optimization[J]. Proceedings of the Conference on Neural Networks, 1995 (8):1942-1948.

[9] KLOSE C. Algorithms for solving the single-sink fixed-charge transportation problem[J]. Computers and Operations Research, 2006, 35(6):2079-2092.

[10] 吕振肃，侯志荣.自适应变异的粒子群优化算法[J] .电子学报，2004, 32(3)：416-420.

LYU Zhensu, HOU Zhirong. Particle swarm optimization with adaptive mutation[J]. Acta Electronica Sinica, 2004, 32(3):416-420.

[11] CHYAN G, PONNAM S. Obstacle avoidance control of redundant robots using variants of particle swarm optimization[J]. Robot Comput Integr Manuf, 2012, 28(2):147-153.

[12] DADGAR M, JAFARI S ,ALI H. A PSO-based multi-robot cooperation method for target searching in unknown environments[J]. Neurocomputing, 2015, 11(7):1-13.

[13] SENTHILKUMAR K. Multi-robot exploration and terrain coverage in an unknown environment[J]. Robotics and Autonomous Systems, 2012, 60(1):123-132.

[14] SCHILLING K, JUNGIUS C. Mobile robots for planetary exploration[J]. Control Engineering Practice, 1996, 4(4):513-524.

[15] ZHANG Jianhua, GONG Dunwei, ZHANG Yong. A niching PSO-based multi-robot cooperation method for localizing odor sources[J]. Neurocomputing, 2014, 123(10):308-317.

[16] YANG Xueming, YUAN Jinsha, MAO Huina. A modified particle swarm optimizer with dynamic adaptation[J]. Applied Mathematics and Computation, 2007, 189(12):1205-1213.

[17] ALFI A. PSO with adaptive mutation and inertia weight and its application in parameter estimation of dynamic systems[J]. Acta Automatica Sinica, 2011, 37(5):541-549.

[18] MATSUNO Y, TSUCHIYA T, WEI Jian, et al. Stochastic optimal control for aircraft conflict resolution under wind uncertainty[J]. Aerospace Science and Technology, 2015, 43(2):77-88.

[19] CAI Yifan. An improved PSO-based approach with dynamic parameter tuning for cooperative multi-robot target searching in complex unknown environments[J]. International Journal of Control, 2013, 86(10):1720-1732.

[20] ZHANG Yong, GONG Dunwei , ZHANG Jianhua. Robot path planning in uncertain environment using multi-objective particle swarm optimization[J]. Neurocomputing, 2013, 103(1):172-185.

[21] ANTONIO A, LAUREANO F. Multiobjective optimization for aircraft conflict resolution： A metaheuristic approach[J]. European Journal of Operational Research, 2016, 248(5):691-702.

[22] MARIA P, HU Jianghai, JOHN L, et al. A probabilistic approach to aircraft conflict detection[J]. IEEE Transactions on Intelligent Transportation Systems, 2000, 1(4):199-220.

Study of the aircraft conflict resolution method based on modified particle swarm optimization

ZHEN Ran1,2, SI Chao1,2, WU Xueli1,2, ZHANG Jianhua1,2, WU Xiaojing1,2

(1.School of Electrical Engineering, Hebei University of Science and Technology, Shijiazhuang, Hebei 050018, China; 2. Hebei Provincial Research Center for Technologies in Process Engineering Automation, Shijiazhuang, Hebei 050018, China)

Conflict resolution requires the aircraft to adopt an effective method to meet the constraints of the working space. Aiming at the problem of conflict resolution in multi obstacle environment, a novelty algorithm based on particle swarm optimization (PSO) is proposed for conflict resolution which meets the mentioned constrains. The proposed DARPSO is similar to PSO with two modifications: firstly, it takes into account the obstacle avoidance; secondly, it has a mechanism to escape from local optima. Various experimental results obtained in simulations show that the proposed DARPSO is much more superior than PSO. The DARPSO is applied to the process of conflict resolution of aircrafts, and it is simulated. The simulation results show that the proposed algorithm can avoid the obstacles and complete conflict resolution effectively.

algorithm theories; aircraft; conflict detection; conflict resolution; particle swarm optimization

1008-1542(2016)05-0491-06

10.7535/hbkd.2016yx05010

2016-05-24；

2016-09-09；责任编辑：李 穆

河北省自然科学基金(F2015208128，F2014208119)；河北省教育厅青年基金(QN20140157，BJ2016020)

甄 然(1971—)，女，河北安国人，副教授，主要从事控制科学与控制工程方面的研究。

E-mail:zhenranzr@126.com

TP273; V19

A

甄 然，司 超，吴学礼,等.基于改进粒子群算法的飞行器冲突解脱方法研究[J].河北科技大学学报,2016,37(5):491-496.

ZHEN Ran, SI Chao,WU Xueli,et.al.Study of the aircraft conflict resolution method based on modified particle swarm optimization[J].Journal of Hebei University of Science and Technology,2016,37(5):491-496.