CN112462804A - Unmanned aerial vehicle perception and avoidance strategy based on ADS-B and ant colony algorithm - Google Patents

Abstract

The invention discloses an unmanned aerial vehicle sensing and avoiding strategy based on ADS-B and an ant colony algorithm, and belongs to the technical field of unmanned aerial vehicle safety. The invention mainly provides a cooperative sensing and avoiding strategy for the collision avoidance problem of an unmanned aerial vehicle under an airspace fusion background, which mainly comprises the following steps: firstly, acquiring flight state data of a target aircraft based on an ADS-B technology; secondly, performing deterministic collision detection, and determining a collision target by fully utilizing ADS-B information to perform geometric distance judgment from a horizontal plane and a vertical plane; and finally, performing route re-planning by adopting an ant colony algorithm based on an introduced comprehensive factor heuristic function and a sequencing mechanism to realize collision avoidance. The method can effectively identify the possible threat targets around the unmanned aerial vehicle, and provides a high-quality release strategy with high adaptability.

Description

Translated fromChinese

基于ADS-B和蚁群算法的无人机感知与规避策略UAV perception and avoidance strategy based on ADS-B and ant colony algorithm

技术领域technical field

本发明属于无人机安全技术领域，涉及一种基于ADS-B技术和蚁群算法的无人机感知与规避策略，尤其涉及一种基于改进蚁群算法的冲突解脱方法。The invention belongs to the technical field of UAV safety, relates to a UAV perception and avoidance strategy based on ADS-B technology and ant colony algorithm, and in particular relates to a conflict resolution method based on improved ant colony algorithm.

背景技术Background technique

无人机感知与规避是指无人机能自主识别障碍物、保持安全间隔并避免碰撞，大致包含环境感知、冲突探测、冲突解脱三个功能模块。UAV perception and avoidance means that UAVs can autonomously identify obstacles, maintain safe distances and avoid collisions. It roughly includes three functional modules: environment perception, conflict detection, and conflict resolution.

环境感知主要依靠传感器，包括雷达、红外系统、广播式自动相关监视(AutomaticDependent Surveillance-Broadcast,ADS-B)技术等方式。其中，ADS-B技术是全球航空运输系统中新一代监视技术的主要方向，其依靠全球导航卫星系统(GlobalNavigationSatellite System,GNSS)和先进的空-空、空-地数据链通信技术实现多种信息的生成和远距离交换。目前，美国、欧洲、中国也都在逐步完成ADS-B的相关落地计划，未来将实现ADS-B技术更广泛的应用。但在无人机领域，ADS-B的应用还有待进一步探索。Environmental perception mainly relies on sensors, including radar, infrared systems, and Automatic Dependent Surveillance-Broadcast (ADS-B) technology. Among them, ADS-B technology is the main direction of the new generation of surveillance technology in the global air transportation system. It relies on the Global Navigation Satellite System (GNSS) and advanced air-air and air-ground data link communication technologies to realize a variety of information generation and long-distance exchange. At present, the United States, Europe, and China are also gradually completing the relevant implementation plans of ADS-B, and in the future, ADS-B technology will be more widely used. However, in the field of UAVs, the application of ADS-B remains to be further explored.

冲突探测方法主要分为几何法和概率法两类。几何法多通过划分安全区，并基于当前飞行状态对未来航迹进行线性预测，判定安全区是否存在重叠，例如民航飞机所用的空中防撞系统(TrafficCollisionAvoidance System,TCAS)就是采用的几何法。概率法则考虑了如风扰动、导航误差等随机因素，能计算出冲突发生的可能性，更精确但也更复杂。Conflict detection methods are mainly divided into two categories: geometric method and probabilistic method. The geometric method mostly divides the safety zone and predicts the future track linearly based on the current flight state to determine whether the safety zone overlaps. Probabilistic laws take into account random factors such as wind disturbances, navigation errors, etc., and can calculate the probability of conflict, which is more accurate but also more complex.

冲突解脱的实现较多采用航路规划方法，包括人工势场法、以遗传算法为代表的启发式算法、A*算法等。其中，蚁群算法是启发式全局优化算法的一种，是用于寻找优化路径的概率型算法，具有分布计算、信息正反馈和启发式搜索的特征，其优势在于有较强的鲁棒性和搜索性，但也存在对计算性能要求较高、易陷入局部最优的缺点。目前，航路规划方法多是基于几何学进行搜索，不考虑飞行器动力学约束，且搜索效率取决于规划空间大小，而不少学者对算法的改进集中在算法本身的缺陷和求解速度上，优质航路的判定仅参考延误距离这一条标准，因此，算法的适应性存在较大改进空间。The realization of conflict resolution mostly adopts route planning methods, including artificial potential field method, heuristic algorithm represented by genetic algorithm, A* algorithm, etc. Among them, ant colony algorithm is a kind of heuristic global optimization algorithm. It is a probabilistic algorithm for finding optimization paths. It has the characteristics of distributed calculation, positive information feedback and heuristic search, and its advantage lies in its strong robustness. and searchability, but it also has the disadvantages of high requirements on computing performance and easy to fall into local optimum. At present, most of the route planning methods are based on geometry search, without considering the constraints of aircraft dynamics, and the search efficiency depends on the size of the planning space, and many scholars have focused on the algorithm's shortcomings and solution speed. The determination of , only refers to the standard of delay distance, so there is a large room for improvement in the adaptability of the algorithm.

发明内容SUMMARY OF THE INVENTION

为了解决现有技术中存在的问题，本发明提供了一种基于ADS-B和蚁群算法的无人机感知与规避策略。本发明采用的技术方案如下：In order to solve the problems existing in the prior art, the present invention provides a UAV perception and avoidance strategy based on ADS-B and ant colony algorithm. The technical scheme adopted in the present invention is as follows:

一种基于ADS-B和蚁群算法的无人机感知与规避策略，包括如下步骤：A UAV perception and avoidance strategy based on ADS-B and ant colony algorithm, including the following steps:

步骤1，对初始环境进行建模。以柱形保护区模型对飞行器进行抽象，设置冲突探测区域大小、最小水平安全间隔R和最小垂直安全间隔H。Step 1. Model the initial environment. The aircraft is abstracted with a cylindrical protection zone model, and the size of the conflict detection area, the minimum horizontal safety interval R and the minimum vertical safety interval H are set.

步骤2，对探测域中的飞行器ADS-B报文数据进行处理，得到三维笛卡尔坐标系下的飞行器位置坐标、水平速度值、航向、垂直速度。Step 2: Process the ADS-B message data of the aircraft in the detection domain to obtain the position coordinates, horizontal velocity value, heading, and vertical velocity of the aircraft in the three-dimensional Cartesian coordinate system.

步骤3，对目标机进行水平初选，根据公式(1)判断目标机是否逐渐靠近。Step 3, perform a horizontal primary selection on the target machine, and judge whether the target machine is gradually approaching according to formula (1).

S₀＝AB·V_{r_hori} (1)S₀ =AB·V_{r_hori} (1)

其中，AB表示X-Y二维水平面上目标机的相对位置向量，V_{r_hori}表示X-Y二维水平面上目标机的相对速度向量。若S₀≥0表示无冲突产生，跳转步骤6；否则，继续步骤4。Among them, AB represents the relative position vector of the target machine on the XY two-dimensional horizontal plane, and V_{r_hori} represents the relative velocity vector of the target machine on the XY two-dimensional horizontal plane. If S₀ ≥ 0, it means that no conflict occurs, go to step 6; otherwise, continue to step 4.

步骤4，对经过水平初选的目标机进行水平距离计算，根据公式(2)进行判断。Step 4: Calculate the horizontal distance of the target machine that has undergone the horizontal primary selection, and judge according to formula (2).

其中，HMD表示X-Y二维水平面上目标机相对航迹最接近点处的水平错开距离。若S₁≥0表示无冲突产生，跳转步骤6；否则，继续步骤5。Among them, HMD represents the horizontal offset distance of the target aircraft relative to the closest point of the track on the XY two-dimensional horizontal plane. If S₁ ≥ 0, it means that no conflict occurs, go to step 6; otherwise, continue to step 5.

步骤5，对经过水平探测的目标机进行垂直探测，根据公式(3)、(4)进行判断。Step 5: Perform vertical detection on the target machine that has been detected horizontally, and judge according to formulas (3) and (4).

S₂＝[k·(x_M-x_B)+z_B-z_M]·[k·(x_E-x_B)+z_B-z_E] (3)S₂ =[k·(x_M -x_B )+z_B -z_M ]·[k·(x_E -x_B )+z_B -z_E ] (3)

S₃＝[k·(x_N-x_B)+z_B-z_N]·[k·(x_F-x_B)+z_B-z_F] (4)S₃ =[k·(x_N −x_B )+z_B −z_N ]·[k·(x_F −x_B )+z_B −z_F ] (4)

其中，k表示目标机相对轨迹在X-Z平面上的斜率，点E、F、M、N为安全域垂直矩形切面顶点。若S₁≥0且S₂≥0表示无冲突产生；否则，标记目标机为入侵机。Among them, k represents the slope of the relative trajectory of the target machine on the XZ plane, and points E, F, M, and N are the vertices of the vertical rectangular section of the safety domain. If S₁ ≥ 0 and S₂ ≥ 0, there is no conflict; otherwise, the target machine is marked as an intruder.

步骤6，判断探测域内所有目标机是否完成冲突探测。若未完成，则跳转步骤3；否则，基于具体的冲突场景，对解脱环境进行建模，包括设置冲突解脱扇区大小，将解脱扇区中的n架飞行器未来航路进行离散化。Step 6: Determine whether all target machines in the detection area have completed conflict detection. If it is not completed, go to step 3; otherwise, based on the specific conflict scenario, model the relief environment, including setting the conflict relief sector size, and discretize the future routes of n aircraft in the relief sector.

步骤7，将n架飞行器分别放置在n个出发点上，记为一批次，n架飞行器同时开始各自进行路径选择。对每一步，按照信息素浓度计算每种策略的被选概率，具体计算式为公式(5)，并采用轮盘赌方式进行随机选择。Step 7: Place the n aircrafts on the n departure points respectively, which is recorded as a batch, and the n aircrafts start their own path selection at the same time. For each step, the probability of being selected for each strategy is calculated according to the pheromone concentration. The specific calculation formula is formula (5), and the roulette method is used for random selection.

其中，τ_ci(t)为信息素值；α和β表示各部分的相对重要程度；综合因素启发部分η_ci(t)由公式(6)确定。Among them, τ_ci (t) is the pheromone value; α and β represent the relative importance of each part; the comprehensive factor inspiration part η_ci (t) is determined by formula (6).

其中，

表示经指数处理的偏离原航迹点的距离，angle表示与出发点连线对应角度与冲突路径对应角度的差，共同表征路径偏离因素；direction和speed表示与前一步选择策略在方向、速度上存在的差别大小，表征平滑度因素。in,

Represents the exponentially processed distance from the original track point, angle represents the difference between the angle corresponding to the line connecting the starting point and the corresponding angle of the conflicting path, which together represent the path deviation factor; direction and speed represent the existence of the direction and speed with the previous selection strategy The size of the difference represents the smoothness factor.

步骤8，对规划路径进行冲突判定，根据公式(7)计算每一步飞行器之间的距离d。若d≥R，则表示无冲突产生；否则，跳转步骤7进行重新规划。Step 8: Conflict determination is performed on the planned path, and the distance d between the aircrafts at each step is calculated according to formula (7). If d≥R, it means that no conflict occurs; otherwise, skip to step 7 for re-planning.

步骤9，重复步骤7-8，直到完成M批次，记M批次为一次迭代。按照该次迭代中每一批次飞行器最终延误距离之和进行排序，并按照公式(8)更新信息素浓度。Step 9, repeat steps 7-8 until M batches are completed, and record M batches as one iteration. Sort according to the sum of the final delay distances of each batch of aircraft in this iteration, and update the pheromone concentration according to formula (8).

其中，0＜ρ＜1，ρ为信息素衰减系数，表征信息素随着时间逐渐挥发；

表示新增信息素量，其分布方式引入了排序机制，按照公式(9)确定。Among them, 0<ρ<1, ρ is the pheromone attenuation coefficient, which indicates that the pheromone gradually volatilizes with time;

Represents the amount of newly added pheromone, and its distribution method introduces a sorting mechanism, which is determined according to formula (9).

其中，Q为每架飞行器信息素释放量，

为飞行器最终延误距离。Among them, Q is the amount of pheromone released by each aircraft,

It is the final delay distance of the aircraft.

步骤10，重复步骤7-9，直到完成T次迭代。输出当前最优策略及其最终平均延误距离。Step 10, repeat steps 7-9 until T iterations are completed. Output the current optimal policy and its final average delay distance.

本发明的有益效果如下：The beneficial effects of the present invention are as follows:

(1)以基本蚁群算法进行航路规划，多围绕目标函数设计启发部分，即仅考虑延误距离，或者在解空间较大的情况下省略启发部分，以降低随机性并加快收敛速度。本发明在基本蚁群算法的基础上，引入了综合因素启发部分，考虑了延误距离、航迹和速度的平滑度因素，提升了规划航路的适应性。(1) The basic ant colony algorithm is used for route planning, and the heuristic part is designed around the objective function, that is, only the delay distance is considered, or the heuristic part is omitted when the solution space is large, so as to reduce the randomness and speed up the convergence speed. On the basis of the basic ant colony algorithm, the present invention introduces the heuristic part of comprehensive factors, and considers the smoothness factors of delay distance, track and speed, and improves the adaptability of planning routes.

(2)本发明提出了一种引入了排序机制的信息素更新方式。一方面，传统的蚁周模型以n架飞行器的最终总延误为标准，全局性过强，不能体现每架飞行器的差异性，而另一种蚁量模型则是考虑每架飞行器每一步的延误，过于局部化。本发明提出的信息素更新模型则以每架飞行器的最终延误为标准，兼顾了全局和局部。另一方面，排序机制的引入，能加快算法的收敛，平衡因引入综合启发因素而带来的随机性提高、收敛速度降低问题。(2) The present invention proposes a pheromone update method that introduces a sorting mechanism. On the one hand, the traditional ant-week model takes the final total delay of n aircraft as the standard, which is too global and cannot reflect the differences of each aircraft, while the other ant-quantity model considers the delay of each aircraft at each step. , is too localized. The pheromone update model proposed by the present invention takes the final delay of each aircraft as the standard, and takes into account both the global and the local. On the other hand, the introduction of the sorting mechanism can speed up the convergence of the algorithm, and balance the increase of randomness and the decrease of convergence speed caused by the introduction of comprehensive heuristic factors.

附图说明Description of drawings

图1是本发明的基于ADS-B和蚁群算法的无人机感知与规避策略的模型架构图；Fig. 1 is the model framework diagram of the UAV perception and evasion strategy based on ADS-B and ant colony algorithm of the present invention;

图2是本发明的基于ADS-B数据信息的水平探测示意图；Fig. 2 is the horizontal detection schematic diagram based on ADS-B data information of the present invention;

图3是本发明的基于ADS-B数据信息的垂直探测示意图；Fig. 3 is the vertical detection schematic diagram based on ADS-B data information of the present invention;

图4是本发明的基于ADS-B数据信息的冲突探测仿真结果图；Fig. 4 is the conflict detection simulation result diagram based on ADS-B data information of the present invention;

图5是本发明的基于基本蚁群算法的冲突解脱仿真对照结果图；Fig. 5 is the conflict resolution simulation comparison result diagram based on basic ant colony algorithm of the present invention;

图6是本发明的基于引入排序机制与综合因素启发部分的蚁群算法的冲突解脱仿真结果图。FIG. 6 is a simulation result diagram of conflict resolution of the ant colony algorithm based on the introduction of the sorting mechanism and the heuristic part of the comprehensive factor of the present invention.

具体实施方式Detailed ways

为使本发明的目的、技术方案和优点更加清楚，下面结合附图和具体实施例进行更为完整的描述。In order to make the objectives, technical solutions and advantages of the present invention clearer, a more complete description is given below with reference to the accompanying drawings and specific embodiments.

如图1所示，基于ADS-B和蚁群算法的无人机感知与规避策略在充分利用ADS-B数据的基础上，算法模型主要包括冲突探测、冲突解脱两部分，具体包括以下步骤：As shown in Figure 1, the UAV perception and avoidance strategy based on ADS-B and ant colony algorithm is based on the full use of ADS-B data. The algorithm model mainly includes two parts: conflict detection and conflict resolution, including the following steps:

步骤1，对初始环境进行建模。以柱形保护区模型对飞行器进行抽象，设置冲突探测区域大小、最小水平安全间隔R和最小垂直安全间隔H。Step 1. Model the initial environment. The aircraft is abstracted with a cylindrical protection zone model, and the size of the conflict detection area, the minimum horizontal safety interval R and the minimum vertical safety interval H are set.

步骤2，对探测域中的飞行器ADS-B报文数据进行处理，得到三维笛卡尔坐标系下的飞行器位置坐标、水平速度值、航向、垂直速度。Step 2: Process the ADS-B message data of the aircraft in the detection domain to obtain the position coordinates, horizontal velocity value, heading, and vertical velocity of the aircraft in the three-dimensional Cartesian coordinate system.

记本机为A，记目标机为B。在X-Y-Z坐标系中，本机A的位置坐标为(x₁,y₁,z₁)，目标机B的位置坐标为(x₂,y₂,z₂)。在X-Y二维水平面上，A的航速矢量为

B的航速矢量为

在X-Z二维平面上，A的航速矢量为

B的航速矢量为

Note that the machine is A, and the target machine is B. In the XYZ coordinate system, the position coordinates of local machine A are (x₁ , y₁ , z₁ ), and the position coordinates of target machine B are (x₂ , y₂ , z₂ ). On the XY two-dimensional plane, the speed vector of A is

The speed vector of B is

On the XZ two-dimensional plane, the speed vector of A is

The speed vector of B is

步骤3，对目标机进行水平初选，根据公式(1)判断目标机是否逐渐靠近。Step 3, perform a horizontal primary selection on the target machine, and judge whether the target machine is gradually approaching according to formula (1).

S₀＝AB·V_{r_hori} (1)S₀ =AB·V_{r_hori} (1)

其中，AB表示X-Y二维水平面上目标机的相对位置向量，V_{r_hori}表示X-Y二维水平面上目标机的相对速度向量。若S₀≥0表示无冲突产生，跳转步骤6；否则，继续步骤4。Among them, AB represents the relative position vector of the target machine on the XY two-dimensional horizontal plane, and V_{r_hori} represents the relative velocity vector of the target machine on the XY two-dimensional horizontal plane. If S₀ ≥ 0, it means that no conflict occurs, go to step 6; otherwise, continue to step 4.

步骤4，对经过水平初选的目标机进行水平距离计算，如图2，根据公式(2)进行判断。Step 4: Calculate the horizontal distance of the target machine that has undergone the horizontal primary selection, as shown in Figure 2, and judge according to formula (2).

其中，HMD表示X-Y二维水平面上目标机相对航迹最接近点处的水平错开距离。若S₁≥0表示无冲突产生，跳转步骤6；否则，继续步骤5。Among them, HMD represents the horizontal offset distance of the target aircraft relative to the closest point of the track on the XY two-dimensional horizontal plane. If S₁ ≥ 0, it means that no conflict occurs, go to step 6; otherwise, continue to step 5.

步骤5，对经过水平探测的目标机进行垂直探测，如图3，根据公式(3)、(4)进行判断。Step 5: Perform vertical detection on the target machine that has been detected horizontally, as shown in Figure 3, and judge according to formulas (3) and (4).

S₂＝[k·(x_M-x_B)+z_B-z_M]·[k·(x_E-x_B)+z_B-z_E] (3)S₂ =[k·(x_M -x_B )+z_B -z_M ]·[k·(x_E -x_B )+z_B -z_E ] (3)

S₃＝[k·(x_N-x_B)+z_B-z_N]·[k·(x_F-x_B)+z_B-z_F] (4)S₃ =[k·(x_N −x_B )+z_B −z_N ]·[k·(x_F −x_B )+z_B −z_F ] (4)

其中，k表示目标机相对轨迹在X-Z平面上的斜率，点E、F、M、N为安全域垂直矩形切面顶点。若S₁≥0且S₂≥0表示无冲突产生；否则，标记目标机为入侵机。Among them, k represents the slope of the relative trajectory of the target machine on the XZ plane, and points E, F, M, and N are the vertices of the vertical rectangular section of the safety domain. If S₁ ≥ 0 and S₂ ≥ 0, there is no conflict; otherwise, the target machine is marked as an intruder.

步骤6，判断探测域内所有目标机是否完成冲突探测。若未完成，则跳转步骤3；否则，基于具体的冲突场景，对解脱环境进行建模。设置冲突解脱扇区大小，将解脱扇区中的n架飞行器未来航路进行离散化，按照等时长将解脱扇区内的各原定航路段划分为K步。Step 6: Determine whether all target machines in the detection area have completed conflict detection. If not completed, go to step 3; otherwise, model the release environment based on the specific conflict scenario. Set the size of the conflict relief sector, discretize the future routes of n aircraft in the relief sector, and divide each original route segment in the relief sector into K steps according to the same duration.

其中，各条航路被分为K段，对应K+1个节点，第1个节点记为出发点，第K+1个节点记为目标点；每一步可选择的策略有9种，包括速度调整(减速20％、保持初始速度、加速20％)、航向调整(左转30°、保持初始航向、右转30°)以及同时调整速度与航向，记为C₁-C₉。Among them, each route is divided into K sections, corresponding to K+1 nodes, the first node is recorded as the starting point, and the K+1th node is recorded as the target point; there are 9 strategies for each step, including speed adjustment. (Decelerate 20%, keep initial speed, accelerate 20%), course adjustment (turn left 30°, keep initial course, turn right 30°) and adjust speed and heading at the same time, denoted as C₁ -C₉ .

步骤7，将n架飞行器分别放置在n个出发点上，记为一批次，n架飞行器同时开始各自进行路径选择。对每一步，按照信息素浓度计算每种策略的被选概率，并采用轮盘赌方式进行随机选择。记当前飞行器为第i(1≤i≤n)架，当前步为第k(1≤k≤K)步，策略C_i被选概率计算公式为公式(5)。Step 7: Place the n aircrafts on the n departure points respectively, which is recorded as a batch, and the n aircrafts start their own path selection at the same time. For each step, the probability of being selected for each strategy is calculated according to the pheromone concentration, and the random selection is made by roulette. Denote the current aircraft as the i-th (1≤i≤n) aircraft, the current step as the k-th (1≤k≤K) step, and the formula for calculating the probability of strategy C_i being selected is formula (5).

其中，τ_ci(t)为策略C_i对应路段的信息素值；α和β表示各部分的相对重要程度；综合因素启发部分η_ci(t)由公式(6)确定。Among them, τ_ci (t) is the pheromone value of the road section corresponding to the strategy C_i ; α and β represent the relative importance of each part; the comprehensive factor inspiration part η_ci (t) is determined by formula (6).

其中，

表示第i(1≤i≤n)架飞行器在第k(1≤k≤K)步偏离原航迹点的距离，

表示经指数处理的偏离原航迹点的距离，angle表示与出发点连线对应角度与冲突路径对应角度的差，共同表征路径偏离因素；direction和speed表示与前一步选择策略在方向、速度上存在的差别大小，表征平滑度因素。in,

represents the distance that the i-th (1≤i≤n) aircraft deviates from the original track point at the k-th (1≤k≤K) step,

Represents the exponentially processed distance from the original track point, angle represents the difference between the angle corresponding to the line connecting the starting point and the corresponding angle of the conflicting path, which together represent the path deviation factor; direction and speed represent the existence of the direction and speed with the previous selection strategy The size of the difference represents the smoothness factor.

步骤8，对规划路径进行冲突判定，根据公式(7)计算每一步飞行器之间的距离d。若d≥R，则表示无冲突产生；否则，跳转步骤7进行重新规划。Step 8: Conflict determination is performed on the planned path, and the distance d between the aircrafts at each step is calculated according to formula (7). If d≥R, it means that no conflict occurs; otherwise, skip to step 7 for re-planning.

其中，

表示飞行器i(1≤i≤n)从出发点开始运行k步后对应的二维水平面坐标。in,

Indicates the two-dimensional horizontal plane coordinates corresponding to the aircraft i (1≤i≤n) after k steps from the starting point.

步骤9，重复步骤7-8，直到完成M批次，记M批次为一次迭代。记当前已经完成第t(1≤t≤T)次迭代，以该次迭代中每一批次飞行器最终延误距离大小之和进行排序，并按照公式(8)更新信息素浓度。Step 9, repeat steps 7-8 until M batches are completed, and record M batches as one iteration. Note that the t (1≤t≤T) iteration has been completed currently, sort by the sum of the final delay distances of each batch of aircraft in this iteration, and update the pheromone concentration according to formula (8).

其中，0＜ρ＜1，ρ为信息素衰减系数，表征信息素随着时间逐渐挥发；

则为该次迭代的第m(1≤m≤M)批次中，飞行器i(1≤i≤n)在该步选择了策略C_i，于是在该路段上留下的新增信息素量，其分布方式引入了排序机制，按照公式(9)确定。Among them, 0<ρ<1, ρ is the pheromone attenuation coefficient, which indicates that the pheromone gradually volatilizes with time;

Then, in the mth (1≤m≤M) batch of this iteration, the aircraft i (1≤i≤n) selects the strategy C_i in this step, so the amount of newly added pheromone left on this road section , and its distribution method introduces a sorting mechanism, which is determined according to formula (9).

其中，Q为每架飞行器信息素释放量，

为该飞行器i(1≤i≤n)最终延误距离。Among them, Q is the amount of pheromone released by each aircraft,

is the final delay distance of the aircraft i (1≤i≤n).

步骤10，重复步骤7-9，直到完成T次迭代。输出当前最优策略及其最终延误。Step 10, repeat steps 7-9 until T iterations are completed. Output the current optimal policy and its final delay.

为了验证基于ADS-B和蚁群算法的无人机感知与规避策略的可行性和有效性，下面通过仿真实验对本发明效果作进一步描述。In order to verify the feasibility and effectiveness of the UAV perception and avoidance strategy based on ADS-B and ant colony algorithm, the effect of the present invention is further described below through simulation experiments.

实验的硬件运行环境主要为2.8GHz的Intel Core i5处理器，4GB内存；软件运行平台为MATLAB 9.1。The hardware running environment of the experiment is mainly 2.8GHz Intel Core i5 processor, 4GB memory; the software running platform is MATLAB 9.1.

为了验证冲突探测方法的有效性，仿真模拟处于坐标原点的本机周围40km范围内存在100架目标飞行器，其关键飞行状态数据按如下条件随机生成：In order to verify the effectiveness of the collision detection method, 100 target aircraft are simulated within a 40km range around the aircraft at the origin of the coordinates, and the key flight status data are randomly generated according to the following conditions:

(1)目标飞行器速度值：v_hori∈[180,360]，v_vert∈[-30,30]，单位为km/h；(1) The speed value of the target aircraft: v_hori ∈ [180,360], v_vert ∈ [-30,30], the unit is km/h;

(2)目标飞行器航向：水平航向与X轴夹角

(2) Target aircraft heading: the angle between the horizontal heading and the X-axis

(3)目标飞行器坐标：x∈(9.26cosθ，40cosθ)，y∈(9.26sinθ，40sinθ)，θ∈(0,2π]，z∈[1,3]，单位为km。(3) Target aircraft coordinates: x∈(9.26cosθ, 40cosθ), y∈(9.26sinθ, 40sinθ), θ∈(0, 2π], z∈[1,3], the unit is km.

安全间隔标准采用R＝5nmile，H＝2000ft。经过100000次蒙特卡洛实验，得到图4的概率分布结果，在100架冲突目标飞行器中，最终平均冲突数量为7.4597架，过滤效果明显。The safety interval standard adopts R=5nmile, H=2000ft. After 100,000 Monte Carlo experiments, the probability distribution results in Figure 4 are obtained. Among the 100 conflicting target aircraft, the final average number of conflicts is 7.4597, and the filtering effect is obvious.

为了验证冲突解脱方法的有效性，仿真模拟一个四机冲突场景，假设存在4架飞行器以360km/h的相同速度同时进入半径为50km的扇区，初始飞行状态设定如表1。In order to verify the effectiveness of the conflict resolution method, a four-aircraft conflict scenario is simulated, assuming that there are four aircraft entering a sector with a radius of 50km at the same speed of 360km/h, and the initial flight state is set as shown in Table 1.

表1初始飞行状态设定Table 1 Initial flight state settings

其他相关参数设定为α＝1，β＝2，衰减系数ρ＝0.3，信息素量Q＝100，批次数M＝20，总步数K＝20，迭代次数T＝200次，综合因素启发部分中C＝R＝5nmile。Other related parameters are set as α=1, β=2, attenuation coefficient ρ=0.3, pheromone quantity Q=100, batch number M=20, total number of steps K=20, iteration number T=200 times, inspired by comprehensive factors C=R=5nmile in part.

采用不引入启发部分的基本蚁群算法得到的解脱策略如图5，对应最终平均延误距离为7.8941km。采用本发明提出的引入了排序机制和综合因素启发部分的蚁群算法得到的解脱策略如图6，对应最终平均延误距离为0.8562km。The escape strategy obtained by using the basic ant colony algorithm without the introduction of the heuristic part is shown in Figure 5, and the corresponding final average delay distance is 7.8941km. The escape strategy obtained by adopting the ant colony algorithm that introduces the sorting mechanism and the heuristic part of comprehensive factors proposed by the present invention is shown in Figure 6, and the corresponding final average delay distance is 0.8562km.

综上所述，仿真实验验证了本发明的有效性。以上内容是结合具体实施例对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。In conclusion, the simulation experiment verifies the effectiveness of the present invention. The above content is a further detailed description of the present invention in conjunction with specific embodiments, and it cannot be considered that the specific implementation of the present invention is limited to these descriptions.

Claims (4)

Translated fromChinese

1.一种基于ADS-B和蚁群算法的无人机感知与规避策略，其特征在于，其包括如下步骤：1. a drone perception and evasion strategy based on ADS-B and ant colony algorithm, is characterized in that, it comprises the steps:步骤1，对初始环境进行建模；Step 1, model the initial environment;步骤2，对探测域中的飞行器ADS-B报文数据进行处理；Step 2, processing the ADS-B message data of the aircraft in the detection domain;步骤3，对目标机进行水平初选；Step 3, perform a horizontal primary selection on the target machine;步骤4，对经过水平初选的目标机进行水平探测；Step 4, perform horizontal detection on the target machine that has undergone the horizontal primary selection;步骤5，对经过水平探测的目标机进行垂直探测；Step 5, perform vertical detection on the target machine that has been detected horizontally;步骤6，判断探测域内所有目标机是否完成冲突探测，若未完成，则跳转步骤3；否则，基于具体的冲突场景，对解脱环境进行建模；Step 6, judge whether all target machines in the detection domain have completed the conflict detection, if not, then jump to Step 3; otherwise, based on the specific conflict scenario, model the relief environment;步骤7，对飞行器进行基于信息素浓度的路径选择；Step 7, carrying out path selection based on pheromone concentration for the aircraft;步骤8，对规划路径进行冲突判定，若存在冲突，则跳转步骤7进行重新规划；Step 8, carry out conflict determination on the planned path, if there is a conflict, skip to step 7 to re-plan;步骤9，重复步骤7-8，直到完成一次迭代，对飞行器最终延误距离之和进行排序，并更新信息素浓度；Step 9, repeat steps 7-8 until one iteration is completed, sort the sum of the final delay distances of the aircraft, and update the pheromone concentration;步骤10，重复步骤7-9，直到完成全部迭代，输出当前最优策略及其最终平均延误距离。Step 10: Repeat steps 7-9 until all iterations are completed, and output the current optimal strategy and its final average delay distance.2.根据权利要求1所述基于ADS-B和蚁群算法的无人机感知与规避策略，其特征在于，对目标机的确定型探测包括水平初选、水平探测、垂直探测：2. the UAV perception and evasion strategy based on ADS-B and ant colony algorithm according to claim 1, it is characterized in that, to the deterministic detection of target aircraft, comprises horizontal primary selection, horizontal detection, vertical detection:水平初选判定指标为目标机的飞行趋向，具体判定指标为公式(1)：The horizontal primary selection judgment index is the flight trend of the target aircraft, and the specific judgment index is formula (1):S₀＝AB·V_{r_hori} (1)S₀ =AB·V_{r_hori} (1)其中，AB表示X-Y二维水平面上目标机的相对位置向量，V_{r_hori}表示X-Y二维水平面上目标机的相对速度向量，若S₀≥0表示目标机逐渐远离或保持距离，无冲突产生；否则，需要进一步判断；Among them, AB represents the relative position vector of the target machine on the XY two-dimensional horizontal plane, and V_{r_hori} represents the relative velocity vector of the target machine on the XY two-dimensional horizontal plane. If S₀ ≥ 0, it means that the target machine gradually moves away or maintains a distance, and no conflict occurs; otherwise , requires further judgment;水平探测为计算水平面最接近点的错开距离，从而判断目标机是否突破水平最小安全间隔R，具体判定指标为公式(2)：The horizontal detection is to calculate the staggered distance of the closest point on the horizontal plane, so as to judge whether the target machine breaks through the minimum horizontal safety interval R. The specific judgment index is formula (2):

其中，HMD表示目标机相对航迹最接近点处的水平错开距离，若S₁≥0表示不会突破水平最小安全间隔，无冲突产生；否则，需要进一步判断；Among them, HMD represents the horizontal staggered distance of the target aircraft relative to the closest point of the track. If S₁ ≥ 0, it means that the horizontal minimum safety interval will not be broken, and no conflict will occur; otherwise, further judgment is required;垂直探测为基于几何知识判断目标机是否进入安全域垂直切面，具体判定指标为公式(3)、(4)：Vertical detection is to judge whether the target machine enters the vertical section of the safety domain based on geometric knowledge. The specific judgment indicators are formulas (3) and (4):S₂＝[k·(x_M-x_B)+z_B-z_M]·[k·(x_E-x_B)+z_B-z_E] (3)S₂ =[k·(x_M -x_B )+z_B -z_M ]·[k·(x_E -x_B )+z_B -z_E ] (3)S₃＝[k·(x_N-x_B)+z_B-z_N]·[k·(x_F-x_B)+z_B-z_F] (4)S₃ =[k·(x_N −x_B )+z_B −z_N ]·[k·(x_F −x_B )+z_B −z_F ] (4)其中，k表示目标机相对轨迹在X-Z平面上的斜率，点E、F、M、N为安全域垂直矩形切面顶点，若S₁≥0且S₂≥0表示不会进入安全域，无冲突产生；否则，会产生冲突。Among them, k represents the slope of the relative trajectory of the target machine on the XZ plane, and points E, F, M, and N are the vertices of the vertical rectangular section of the safety zone. If S₁ ≥ 0 and S₂ ≥ 0, it means that it will not enter the safety zone and there is no conflict. produces; otherwise, a conflict is produced.3.根据权利要求1所述基于ADS-B和蚁群算法的无人机感知与规避策略，其特征在于，基于蚁群算法的冲突解脱中，飞行器基于信息素浓度进行路径选择，具体计算公式为公式(5)：3. the UAV perception and evasion strategy based on ADS-B and ant colony algorithm according to claim 1, it is characterized in that, in the conflict resolution based on ant colony algorithm, aircraft carries out path selection based on pheromone concentration, and concrete calculation formula is formula (5):

其中，τ_ci(t)为信息素值；α和β表示各部分的相对重要程度；引入的综合因素启发部分η_ci(t)，具体计算公式为公式(6)：Among them, τ_ci (t) is the pheromone value; α and β represent the relative importance of each part; the introduced comprehensive factor inspires the part η_ci (t), and the specific calculation formula is formula (6):

其中，

表示经指数处理的偏离原航迹点的距离，angle表示与出发点连线对应角度与冲突路径对应角度的差，共同表征路径偏离因素；direction和speed表示与前一步选择策略在方向、速度上存在的差别大小，表征平滑度因素。in,

Represents the exponentially processed distance from the original track point, angle represents the difference between the angle corresponding to the line connecting the starting point and the corresponding angle of the conflicting path, which together represent the path deviation factor; direction and speed represent the existence of the direction and speed with the previous selection strategy The size of the difference represents the smoothness factor.4.根据权利要求1所述基于ADS-B和蚁群算法的无人机感知与规避策略，其特征在于，基于蚁群算法的冲突解脱中，信息素浓度在一次迭代后进行更新，具体计算公式为公式(7)：4. the UAV perception and evasion strategy based on ADS-B and ant colony algorithm according to claim 1, it is characterized in that, in the conflict resolution based on ant colony algorithm, the pheromone concentration is updated after one iteration, and the concrete calculation The formula is formula (7):

其中，0＜ρ＜1，ρ为信息素衰减系数，表征信息素随着时间逐渐挥发；

表示新增信息素量，其分布方式引入了排序机制，具体计算公式为公式(8)：Among them, 0<ρ<1, ρ is the pheromone attenuation coefficient, which indicates that the pheromone gradually volatilizes with time;

Represents the amount of newly added pheromone, and its distribution method introduces a sorting mechanism. The specific calculation formula is formula (8):

其中，Q为每架飞行器信息素释放量，

为飞行器最终延误距离。Among them, Q is the amount of pheromone released by each aircraft,

It is the final delay distance of the aircraft.

Images