Risk of Mid-Air Collision Estimation Using Minimum Spanning Tree of Air Traffic Graph Ivan Ostroumov1, Oleg Ivashchuk1 and Sergii Babichev2,3 1National Aviation University, Lubomira Huzara ave., 1, Kyiv, 03680, Ukraine1 2Jan Evangelista Purkyne University in Usti nad Labem, Ceske mladeze, 8, Usti nad Labem, 40096, Czech Republic 3Kherson State University, Universytetska st. 27, Kherson,73003, Ukraine Abstract The safety of air transportation is based on different risk estimations and control. A mid-air collision is one of the dangerous events in aviation due to both air-planes involved in the catastrophe. Risk of a mid-air collision is considered as a probability of airplane deviation to the safety area of another airspace user in horizontal and vertical planes. A double exponential function is used as a probability density function to estimate probability of airplane deviation from a preplanned position. A theory of Graph has been used to detect the closest pairs of airplanes. Thus, air traffic has been represented as an undirected, connected graph. The probability density function is fixed at nodes of the air traffic graph along of optimal minimum spanning tree path. A minimum of separation is used to build a safety area around each airspace user. In numerical application, live air traffic data within Ukrainian airspace has been used under Automatic-Dependent Surveillance-Broadcast technology. Keywords aviation, mid-air collision, risk, minimum spanning tree, graph, probability density function. 1. Introduction Nowadays, aviation can be referred to as one of the safest types of transport. A number of aviation events have been constantly decreasing since the early 2000s, while passenger traffic has been rising. In the period from 2009 to 2019, there were only seven crashes involving commercial airplanes [1]. This is mainly due to the development of technology and improvement of procedural instructions used for air traffic management. Detailed analysis of each aviation event helps to identify causes, and if necessary, amendments are made to the current rules to prevent the recurrence of this event. However, the number of serious incidents and non-fatal accidents remains quite high, not to mention the situation with non-commercial aviation. This is primarily due to the fact that the volume of airspace is constant at a time when the number of aircraft is growing every year [2, 3]. One of the most dangerous events which still appear in a statistic of aviation events is a mid-air collision An importance of this event makes due to involving two or more aircraft that are flying at the time of the event, respectively, the chances of survival of passengers are much lower. The main cause of such situations is the loss of CITRisk’2021: 2nd International Workshop on Computational & Information Technologies for Risk-Informed Systems, September 16–17, 2021, Kherson, Ukraine EMAIL: vany@nau.edu.ua (I.Ostroumov); iva.oleg2000@gmail.com (O.Ivashchuk); sergii.babichev@ujep.cz (S.Babichev) ORCID: 0000-0003-2510-9312 (I.Ostroumov); 0000-0001-5637-0332 O.Ivashchuk); 0000-0001-6797-1467 (S.Babichev) © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) separation between airspace users, which can be the cause of both human [4] and technical error [5, 6]. Very often action of several unfavorable factors simultaneously may lead to dangerous situation or catastrophe [7, 8]. These factors include bad weather conditions, on-board or ground equipment malfunction, or human factors. Nowadays special systems are used by pilots and air traffic controllers (ATC) for early detection and avoidance of mid-air collision [9]. All of these systems are additional instruments for ATC which play the role of a final step in safety control [10]. Most safety control systems use criteria based on range or time to particular event. Also, there are several approaches to estimate the risk of a mid-air collision, based on air traffic data [11]. A Reich model is one of the most useful in a mid-air collision analysis. Reich's model uses relative motion and velocities of both involved airplanes to estimate probabilities of safety boundaries overlap [11, 12]. This model is useful mostly in air traffic with approximately the same dynamic properties. However, implementation of Unmanned aerial vehicles into controlled airspace will increase the number of airspace users with very different dynamic properties [13, 14], which makes currently used models not adequate. In the current study, we would like to propose to consider air traffic in terms of graph theory to analyze traffic configuration and detects risky pairs of airspace users, which can be considered as potential candidates for a mid-air collision analysis. Risk of a mid-air collision between specified pairs of airspace users can be estimated as probability of safety areas overlap in horizontal and vertical plans. Estimated risk of a mid-air collision is used in a safety control system to inform ATC and pilots or initiate collision avoidance scenarios. 2. Performance-based navigation To control the air situation and improve the process of organizing traffic, the entire airspace is divided into several classes. There are seven classes marked by alphabetical letters from A to G. These classes can be divided into controlled and uncontrolled. In controlled classes (A – E) air traffic services provide aircraft operators with ATC services. Airspace classes F and G are referred to uncontrolled. As an example Ukrainian airspace is divided into three classes [15]: - G – from the ground to 1500 m; - D – from 1500 m to 2900 m; - C – from 2900 m to FL 660. However, in addition to airspace classes, there are established areas and zones for which a separate airspace class may be assigned regardless of their vertical boundaries. To ensure air traffic safety, it was decided to conduct a separation procedure between aircraft and flight levels. Separation can be done by time and distance. In the first case, the use of a time interval between aircraft is envisaged. Separation based on distance is of three types: lateral, vertical, and longitudinal. Although the International Civil Aviation Organization has set out in its documents the conditions for the application of specific minimums, it also states that each state has the right to regulate these criteria [15]. The main factors influencing the size of separation interval are the speed of aircraft, availability, and quality of ground navigation equipment, and the trajectory of aircraft. Performance-Based Navigation (PBN) of airspace users specify requirements for performance of on-board positioning sensor, based on airspace type and availability of particular positioning system [18]. In our study, we will mainly use lateral separation, which is based on the use of navigation aids so that the distance between aircraft is always maintained at least the value of navigation errors and protective reserve [16, 17]. The more accurately you can determine the location of the aircraft on the route, the less value of separation is required. As progress has not stood still since the advent of aviation, navigation equipment has taken a huge step forward. Therefore, today aircraft should no longer move blindly from one navigational aid to another. With the availability of navigation equipment of the required level of precision, pilots can easily maintain their route and fly on it, if there are no obstacles or conflicts with other air traffic participants. Today, most countries around the world use the concept of area navigation (RNP/RNAV), which helps to direct the route between the point of departure and destination. Also, navigation equipment used today can support trajectory maintaining with a defined deviation from the center of the route during 95% of the flight [17]. The navigation specifications of PBN include RNAV and RNP [18]. The difference between them is that in the technical characteristics of RNP there is a requirement for on-board equipment for efficiency monitoring and warning. Navigation error mainly depends on the equipment used. Thus RNAV / RNP specifies requirements for a navigation system that can be used in a particular airspace. The following levels of navigation requirements were used [15]: 1. For oceanic or remote continental routes – RNAV 10 (50 NM) or RNP 4 (23 NM); 2. For conventional continental routes – RNAV 5 (10 NM) or RNP 2 (7 or 15 NM); 3. For the aerodrome zone – RNAV 1 (7 NM) or RNP 1 (5 NM). Another important safety factor is compliance with the Target Level of Safety (TLS) which indicates the required level of safety must be guaranteed in the airspace. TLS is expressed in the value of the collision per hour. The ICAO specifies the acceptable level of TLS in 5×10-9 accidents per flight hour [19]. Estimated risk of mid-air collision can be compared with a TLS. Pairs of airplanes with a higher risk of mid-air collision than TLS may be classified as dangerous. 3. Model of mid-air collision Risk The safety of aviation is grounded on wide usage a risk value. In common risk is a probability of something bad happening. Risk values can be estimated as the frequency of some dangerous event that can take place within a defined time interval. Different frequencies are used for different tasks of safety. Thus, the risk of catastrophe or incident can be estimated by frequency of event related to the number of flight or the total amount of flight times [3]. Risk estimated by statistics usually is used to indicate TLS value [12]. However, in the tasks of risk control, a statistical analysis of particular sensor data is used to estimate components of risk values [20]. A risk tree method is used to segregate the impact of a particular event into total aviation safety. A mid-air collision is one of the most dangerous events in aviation which can lead to a catastrophe of both involved airplanes. In a model of a mid-air collision, we consider two components of risk separately in horizontal and vertical planes. Consideration of risks in two components is a result of application of different separation minimums. Probabilities of overlap in both planes can be estimated based on known probability density functions (PDF) of airplane deviations and separation minimum for investigated airspace. Thus, the risk of a mid-air collision is a probability of one airplane deviation to the safety area of another airspace user (see Figure 1). Safety areas are defined by normative documents under the performance-based navigation criteria. Safety A B Safety limits of limits of airplane A airplane B ρA(x) ρB(x) R(B/A) R(A/B) x Figure 1: Probability of mid-air collision A probability of an airplane getting at a particular region can be represented as an area under PDF which is limited by separation minimums. Risk of two airplanes overlap can be estimated as the maximal probability of particular pair as follows: 𝑅𝑅 = max �∫𝜆𝜆 𝜌𝜌𝑖𝑖 (𝑥𝑥)�, (1) 𝑖𝑖=1,𝑛𝑛−1 𝑖𝑖 where λi is the safety limit of ith airplane; n is the number of airspace users currently located at the same airspace. Safety intervals are defined by a particular airspace type based on separation minimums and calculated from known airplane coordinates. PDF of airplane deviation from a defined point of airspace can be obtained based on known advisable level of separation minimums. In this case assumption of Normal Probability Density Function can be used with zero mean value and mean-standard deviation estimated from "Two sigmas" rule by separation minima to get 95 % of confidence band. In the case of available data of airplane deviations from a particular trajectory, PDF can be estimated statistically. In this case, the following PDF can be used: ─ Normal Probability Density Function 1 −(𝑥𝑥−𝜇𝜇)2 𝜌𝜌𝑁𝑁 (𝑥𝑥) = 𝑒𝑒𝑒𝑒𝑒𝑒 � �, (2) √2𝜋𝜋𝜎𝜎 2𝜎𝜎 2 ─ Double Exponential Density Function [21, 22] −1 −1 1−𝛼𝛼 𝑥𝑥−𝜇𝜇 𝑏𝑏1 𝛼𝛼 𝑥𝑥−𝜇𝜇 𝑏𝑏2 𝜌𝜌𝐷𝐷 (𝑥𝑥) = 𝑒𝑒𝑒𝑒𝑒𝑒 �− � � � + 𝑒𝑒𝑒𝑒𝑒𝑒 �− � � �, (3) 2𝑎𝑎1 𝑏𝑏1 𝛤𝛤(𝑏𝑏1 ) 𝑎𝑎1 2𝑎𝑎2 𝑏𝑏2 𝛤𝛤(𝑏𝑏2 ) 𝑎𝑎2 ─ Triple Univariate Generalized Error Density function [23] 1 1 𝛼𝛼 𝑥𝑥 − 𝜇𝜇 𝑏𝑏1 𝛽𝛽 𝑥𝑥 − 𝜇𝜇 𝑏𝑏2 𝜌𝜌𝑇𝑇 (𝑥𝑥) = 𝑒𝑒𝑒𝑒𝑒𝑒 �− � � �+ 𝑒𝑒𝑒𝑒𝑒𝑒 �− � � �+ 2𝑎𝑎1 𝑏𝑏1 𝛤𝛤(𝑏𝑏1 ) 𝑎𝑎1 2𝑎𝑎2 𝑏𝑏2 𝛤𝛤(𝑏𝑏2 ) 𝑎𝑎2 1 (4) 1 − 𝛼𝛼 − 𝛽𝛽 𝑥𝑥 − 𝜇𝜇 𝑏𝑏3 + 𝑒𝑒𝑒𝑒𝑒𝑒 �− � � �, 2𝑎𝑎3 𝑏𝑏3 𝛤𝛤(𝑏𝑏3 ) 𝑎𝑎3 ∞ 𝛤𝛤(𝑥𝑥) = ∫0 𝑒𝑒 −𝑡𝑡 𝑡𝑡 𝑥𝑥-1 𝑑𝑑𝑑𝑑, where μ is a mean value; σ is mean-standard deviation; ai is a scale variable; bi is a shape parameter; Γ(x) is an Euler-gamma function; α and β are weight parameters. Parameters of PDF can be easily estimated by Least Squares or Maximum Likelihood Methods for input statistical dataset of air traffic deviations from preplanned trajectories [22, 23]. Also, it should be noted that PDF for horizontal and vertical planes are estimated separately due to different sensors usage. Airplane position in a horizontal plane is estimated by Global Navigation Satellite System. However, a barometrical altimeter or accurate radar can be used for estimation of airplane deviations in vertical side. The accuracy of preplanned trajectory maintenance depends on a variety of factors, which include airplane performance and flight technical errors. Thus, it makes sense to provide statistical data processing by particular airplanes, airlines, pilots, particular airspace areas. Estimated parameters of PDF and current air traffic data are used in (1) to process a particular risk value. In order to use equation (1) efficiently at the ATC side within a wide airspace area, the closest airplanes can be considered only. A graph theory can be helpful to identify the most dangerous airplane pairs. In this case, air traffic can be represented as an undirected graph with airspace user location at nodes and relative distances as edges. This graph is dynamically changing in time. A graph can be set up with a help of an adjacency matrix [24, 25]. Nodes we associate with a unique airplane identification number. A pair of the closest airplanes can be obtained by applying one of the methods of searching the minimum spanning tree of a graph [26, 27, 28]. A minimum spanning tree is a set of edges that is selected by criteria of closest nodes or minimal weighted by distance centrality of a graph. Any available method can be used to identify a minimum spanning tree. Surveillance data of current air traffic can be obtained from different sensors. On-board of airplane a receiver of Automatic-Dependent Surveillance-Broadcast (ADS-B) messages, surveillance data of Traffic collision an avoidance system, or passive positioning by navigational aids can be used. Surveillance data processing system at ATC side uses the following sensors: secondary surveillance radar, multilateration, wide area of multilateration, or network of software defined radios for receiving ADS-B data. In our research, we consider ADS-B as the main source of data for all air space users and ATC. ADS-B technology supports free sharing of actual airplane position with other airspace users. Nowadays several systems support ADS-B. However, the usage of modified airplane transponder of Mode 1090ES is one of the most useful worldwide. Airplane position measured by on-board receiver of global navigation satellite system is used by ADS-B. An airplane transponder of mode 1090ES periodically transmits digital messages which include current aircraft coordinate with information about the aircraft type, vertical and horizontal velocities, heading, and aircraft identification. Data messages are transmitted in “open” format and can be received and decoded at the ATC ground facility side or by any airspace user for air traffic situation awareness. Unfortunately, data transmitted by mode 1090ES are not synchronized. Each transponder is configurated for a particular rate of data transmission. Also, many packets may be broken due to interference or overlap with other messages present on 1090 MHz data channel. Therefore, received data includes airplane positions present for unsynchronized periods. Simple linear interpolation or sequential operations can be used for air traffic data synchronization at the time of data processing. Location sharing of each airspace user is a key technology for Free Routs Airspace concept, which is integrated globally now. Free route flight can be supported only by a particular navigation sensor which ensures RNP/RNAV requirements. The structure scheme of mid-air risk estimation is represented in Figure 2. ADS-B messages are received by local and network of software-defined radios. Decoded data are archived in ADS-B database. User-based software may interact with data-base server to obtain data within investigated airspace volume. Data messages are grouped by airplane based on a unique identification code in order to get a separate airplane trajectory. Previous trajectory data are used for interpolation by spline functions to get the actual airplane position. Local software- Data-base of Network of Software defined radio ADS-B messages defined radios radio Interpolation of Selection of air Parameters air traffic data traffic data of PDF Data Adjacency matrix Minimum transformation calculation and setting spanning tree Fix PDFs up graph model estimation Risk Risk of mid-air value estimation Figure 2: Structure scheme of mid-air collision risk estimation in a horizontal plane Actual aircraft positions are transformed from latitude-longitude-altitude to Earth-Centered, Earth-Fixed (ECEF) reference frame. Graph model is setting up by unique airplane identification codes as node vector and adjacency matrix. Adjacency matrix includes ranges between airspace users estimated by the following equation: 2 2 2 2 𝑤𝑤𝑖𝑖 = ��𝑥𝑥𝑖𝑖 − 𝑥𝑥𝑗𝑗 � + �𝑦𝑦𝑖𝑖 − 𝑦𝑦𝑗𝑗 � + �𝑧𝑧𝑖𝑖 − 𝑧𝑧𝑗𝑗 � (5) where x,y,z is airplane location in ECEF reference frame. Then a minimum spanning tree estimation algorithm is initiated for defined air traffic graph. Finally, a PDFs are fixed at nodes of minimum spanning tree and the risk of a mid-air collision is estimated by (1). Obtained risk values will improve situation awareness of ATC and can be indicated by color scale at air traffic screen. 4. Simulation of a mid-air collision risk In numerical demonstration, we estimate the risk of a mid-air collision in a horizontal plane within Ukrainian airspace. Input data of air traffic has been obtained from a national network of Ukrainian ADS-B receivers located across the territory. Software defined radios receive and decode all correct messages transmitted on 1090 MHz frequency. This dataset includes location of airspace users at a particular not synchronize time on June 12, 2021. Coordinates are represented in angles of geodetic latitude and longitude by WGS84 accompanied by barometric altitude measured in feet from the standard pressure at mean sea level. Due to usage of not synchronize measurements an air traffic data should be interpolated for a particular time. Polynomial or spline functions can be used for fast data interpolation at a specified time. We use linear regression with B-spline functions for data synchronization. Results of interpolated air traffic data for 14:21 UTC time in conical equidistance cartographic projection are represented in Figure 3. Also, Table 1 includes detailed information on investigated air traffic. 52.5 N 471F7B C25B 50.0 ° N 50841C 471F813946EB 06A08C 48AE85 5081EC 5082C8 48C130 48C131 4B8E8E 508429 50822C GLF4 508207 508446 5082EA 407B55 48ADA5 47.5 ° N 508370 504E64 45.0 ° N 5082CB ° ° 22.5 E ° ° 40.0 E 25.0 E ° ° ° ° 37.5 E 27.5 E 30.0 E 32.5 E 35.0 E Figure 3: Input extrapolated air traffic data Table 1 Input air traffic data Unique airplane Latitude, Longitude, Altitude, Departure Destination # identification Airplane deg deg ft Airport Airport code 1. 471F7B 51,0603 25,2526 37000 Airbus A320 EPGD UKKK 2. C25B 50,8445 25,2154 40000 Cessna 525 UKKK EVRA 3. 48C130 49,6281 23,0998 36000 Boeing 737-800 LGAV EPMO 4. 5082EA 48,4893 22,8359 37000 Embraer ERJ-190 LEBL UKBB 5. 48AE85 49,8975 24,1680 8400 Boeing 737-86N EPWA UKLL 6. 48C131 49,8217 24,9584 39000 Boeing 737-8AS EPKK UKBB 7. 508429 49,5304 23,3760 29925 Boeing 737-8Z0 UKLL UGTB 8. 407B55 48,4387 25,0783 34975 Airbus A321-271NX EGGW LUKK 9. 4B8E8E 49,7999 25,6993 20625 Dassault Falcon 2000 UKHH UKLL 10. 50822C 49,4872 26,8810 39025 Airbus A321-231 LDPL UKBB 11. 48ADA5 48,5034 26,6598 35000 Embraer E195LR EPWA LUKK 12. 504E64 47,7278 29,3592 31600 Airbus A320-232 LUKK UUWW 13. 471F81 50,2287 29,7509 19050 Airbus A320-232 UKKK EPKK 14. GLF4 49,4292 30,2585 25600 Gulfstream IV UKKK LTBJ 15. 508207 49,3097 30,5995 21750 Boeing 737-8HX LTAI UKKK 16. 508446 49,2948 30,6955 31875 Boeing 737-96N(ER) UKBB LATI 17. 3946EB 50,2259 30,7764 9050 Airbus A319-111 LFPG UKBB 18. 5081EC 50,1022 30,8579 3825 Boeing 767-322(ER) UKBB MDLR 19. 5082C8 50,0290 31,0941 6025 Boeing 737-85R LGRP UKBB 20. 50841C 50,3698 31,1716 8325 Boeing 737-75C UKBB LTFE 21. 06A08C 50,2089 31,1841 13900 Airbus A321-231 UKBB OTHH 22. 508370 48,0696 31,2708 38000 Boeing 737-8Q8 LTAI UKBB 23. 5082CB 44,4093 31,4533 37000 Boeing 737-83N UKDE LTAI The data in Table 1 are used to create an undirected graph of live air traffic. Nodes of a graph can be set up by a unique airplane identification code. The distances between users are used as weighted edges. The undirected graph of live air traffic created by data represented in Table 1 is shown in Figure 4. 4 10 52 1.4 51 471F7B C25B 50841C 471F81 3946EB 06A08C 1.3 5081EC 5082C8 50 48AE85 48C131 4B8E8E 48C130 508429 50822C GLF4 508207 508446 1.2 49 5082EA 407B55 48ADA5 1.1 48 508370 Weighted Centrality, [km] Latitude, [deg] 504E64 1 47 0.9 46 0.8 45 5082CB 0.7 44 0.6 43 20 22 24 26 28 30 32 34 Longitude, [deg] Figure 4: Undirected graph of live air traffic data Weighted centrality of the graph [29, 30] can be used as a safety marker too. Accumulated distances to all other nodes indicate the apartness of a particular air space user. Weighted centrality represents a sum of edges from each node: 𝑛𝑛 𝐶𝐶 = � 𝑟𝑟𝑖𝑖 (6) 𝑖𝑖=1 where rj is a range between pair of airspace users, n is a number of airspace users withing investigated airspace volume. The results of weighted centrality estimation are represented in Figure 4 by color marks of nodes. The biggest value indicates about far location from other air traffic and a low chance to be involved in a mid-air collision. Based on data used a '5082CB' airplane has the lowest risk of a mid-air collision. We use an optimal method to find the minimum spanning tree of the air traffic Graph. A minimum spanning tree is represented in Figure 5 by red lines. Minimum spanning tree connects the closes nodes in a line and indicates pairs of airplanes that can be involved in further detailed estimation for mid-air collision between them. A PDF is fixed at each node position and aligned at the side of edges connected to this node. A PDFs geometry for part of a tree is represented in Figure 6. We use a ρD(x) as PDF with the same shape for each airspace user. Parameters of ρD(x) are the following m1=m2=0; α=0.37; a1=1; a2=9.5; b1=0.96; b2=0.79. Also, requirements of RNP/RNAV for free-routes airspace specify the safety perils for airplane location within confidence band in 95%. We use requirements of RNP 2 for a continental side in 7 NM, which specify a safety radius around each airspace user. Results of risk estimation for pairs of airspace users are represented in Table 2 in decreasing order. 471F7B C25B 50841C 471F81 3946EB 06A08C 5081EC 5082C8 48AE85 48C131 4B8E8E 48C130 508429 50822C GLF4 508207 508446 5082EA 407B55 48ADA5 508370 504E64 5082CB Figure 5: Minimum spanning tree of air traffic graph -4 10 1.2 1 0.8 0.6 PDF 0.4 0.2 3946EB 50841C 50.4 5081EC 06A08C 0 50.2 30.75 30.8 5082C8 30.85 30.9 30.95 31 31.05 31.1 50 31.15 31.2 Latitude, [Deg] Longitude, [Deg] Figure 6: The geometry of PDFs Table 2 Risk of a mid-air collision in the horizontal plane Risk of a mid-air collision in the # Start Node End node horizontal plane 1. '508207' '508446' 0,666 2. '3946EB' '5081EC' 0,327 3. '50841C' '06A08C' 0,217 4. '5081EC' '5082C8' 0,188 5. '5082C8' '06A08C' 0,140 6. '48C130' '508429' 0,103 7. '471F7B' 'C25B' 0,088 8. 'GLF4' '508207' 0,046 9. '48C131' '4B8E8E' 3.667×10-4 10. '48AE85' '48C131' 1.609×10-4 11. '48AE85' '508429' 9,881×10-6 12. '471F81' '3946EB' 6,340×10-6 13. 'GLF4' '5081EC' 2,582×10-7 14. '4B8E8E' '50822C' 7,926×10-8 15. '50822C' '48ADA5' 7,568×10-10 16. 'C25B' '48C131' 2,757×10-10 17. '407B55' '48ADA5' 1,657×10-10 18. '5082EA' '508429' 3,551×10-11 19. '508446' '508370' 1,797×10-13 20. '504E64' '508370' 4,635×10-14 21. '48ADA5' '504E64' 5,774×10-23 22. '504E64' '5082CB' 1,352×10-49 Obtained results highlight a pair '508207-508446' with the highest value of mid-air collision risk. Also, pairs 1 – 14 has risk of a mid-air collision in a horizontal plane more than TLS. However, results in Table 2 represent a horizontal component of a mid-air collision of airplanes only. 5. Conclusion Aviation is a quite speedy developing type of transportation, with a continuously increasing number of airspace operations. Further development of airlines is faced with an operation inside of congested air traffic and increased risk of a mid-air collision. Representation of air traffic as an undirected, connected graph helps to identify the riskiest pairs of airplanes based on closest distances and weighted centrality. Obtained set of risky pairs of airspace users estimated by minimum spanning tree of a graph. Estimation of risk of mid-air collision only for a highlighted set of pairs helps to save computation performance of ATC equipment. Numerical verification with real air traffic data indicates that for 23 airspace users we get 22 pairs connected in a minimum spanning tree of a graph. Results of risk estimation represented in tab.2. highly depends on probability density function. Usage of normal probability density function or triple univariate generalized error density function will result in different risk values. However, the order of risky pairs represented in Table 2 still constant. Proposed approach may be useful for development of a future automatic ATC data processing system that will operate within free routes airspace with integrated unmanned areal vehicles in controlled airspace. References [1] Annual safety review 2020, European Aviation Safety Agency, 2021. URL: https://www.easa.europa.eu/document-library/general-publications/annual-safety-review- 2020 [2] Annual Report 2020, ICAO, 2021. URL: https://www.icao.int/annual-report- 2020/Pages/progress-on-icaos-strategic-objectives-safety-safety-priorities.aspx [3] Safety Report 2020, International Air Transport Association, Geneva, 2021 [4] P.V.Carvalho, J.O.Gomes, G.J.Huber, M.C.Vidal, Normal people working in normal organizations with normal equipment: system safety and cognition in a mid-air collision, Applied ergonomics, 40(3), 2009, pp. 325–340. doi: 10.1016/j.apergo.2008.11.013 [5] O.Solomentsev, M.Zaliskyi, Correlated failures analysis in navigation system, in: Proceedings of the 5th International Conference on Methods and Systems of Navigation and Motion Control, MSNMC 2018, Kyiv, Ukraine, 2018, pp. 123–126. doi:10.1109/MSNMC.2018.8576306 [6] O.Solomentsev, M.Zaliskyi, O.Zuiev, Estimation of quality parameters in the radio flight support operational system, Aviation, 20(3), 2016, pp. 123–128. doi:10.3846/16487788.2016.1227541. [7] P.V.Carvalho, The use of Functional Resonance Analysis Method (FRAM) in a mid-air collision to understand some characteristics of the air traffic management system resilience, Reliability Engineering & System Safety, 96(11), 2011, pp. 1482–1498. doi: 10.1016/j.ress.2011.05.009 [8] J.A.Castan, A.R.Sanz, Risk Assessment in Air Traffic Management, IntechOpen, London, United Kingdom, 2020 [9] Global Air Traffic Management Operational Concept, Doc. 9854, ICAO, 2005. URL: https://www.icao.int/Meetings/anconf12/Document%20Archive/9854_cons_en[1].pdf [10] J.Hannah, R.Mills, R.Dill, D.Hodson, Traffic collision avoidance system: false injection viability. The journal of supercomputing, 2021, pp.1–24. doi: 10.1007/s11227-021-03766-9. [11] A Unified Framework for Collision Risk Modelling in Support of the Manual on Airspace Planning Methodology for the Determination of Separation Minima, Doc. 9689, ICAO, 2009 [12] I. Ostroumov, O.Ivashchuk, T.Shmelova, Risk of mid-air collision in a lateral plane, CEUR Workshop Proceedings, 2805, 2020, pp. 297–307 [13] T.Kille, P.R.Bates, S.Y.Lee, Unmanned aerial vehicles in civilian logistics and supply chain management, IGI global, 2019 [14] R.B.Ferreira, D.M.Baum, E.C.Neto, M.R.Martins, J.R.Almeida, P.S.Cugnasca, J.B.Camargo, A risk analysis of unmanned aircraft systems (UAS) integration into non- segregate airspace, in: Proceedings of the International Conference on Unmanned Aircraft Systems, ICUAS, IEEE, 2018, pp. 42–51 [15] Air traffic management, Procedures for Air Navigation Services, Doc. 4444, ICAO, 2016 [16] I.Ostroumov, N.Kuzmenko, O.Sushchenko, Yu.Averyanova, O.Shcherbyna, O.Solomentsev, F.Yanovsky, M.Zaliskyi, Ukrainian Navigational Aids Network Configuration Estimation, in: Proceedings of the 16th International Conference on the Experience of Designing and Application of CAD Systems, CADSM, IEEE, Lviv, Ukraine, 2021, pp. 5–9. doi: 10.1109/CADSM52681.2021.9385226 [17] I.V.Ostroumov, V.P.Kharchenko, N.S.Kuzmenko, An airspace analysis according to area navigation requirements, Aviation, 23(2), 2019, pp. 36–42. doi: 10.3846/aviation.2019.10302 [18] Performance-Based Navigation (PBN) Manual, Doc 9613, ICAO, 2008. URL: https://www.icao.int/sam/documents/2009/samig3/pbn%20manual%20- %20doc%209613%20final%205%2010%2008%20with%20bookmarks1.pdf [19] Manual on a 300 m (1 000 ft) Vertical Separation Minimum Between FL 290 and FL 410 Inclusive, Doc 9574, AN/934, ICAO, 2012 [20] I.Tsymbaliuk, O.Ivashchuk, I.Ostroumov, Estimation the Risk of Airplane Separation Lost by Statistical Data Processing of Lateral Deviations, in: Proceedings of the 10th International Conference on Advanced Computer Information Technologies, ACIT, IEEE, Deggendorf, Germany, 2020, pp. 269–272. doi: 10.1109/ACIT49673.2020.9208935 [21] S.Nagaoka, A model for estimating the lateral overlap probability of aircraft with RNP alerting capability in parallel RNAV routes. ICAS Secretariat – 26th Congress of International Council of the Aeronautical Sciences, ICAS 2008, Anchorage, AK, United States, 2008, 1, pp. 3590–3597 [22] R.Mori, Identifying the ratio of aircraft applying SLOP by statistical modeling of lateral deviation, Transactions of the Japan Society for Aeronautical and Space Sciences, 54(183), 2011, pp. 30–36. doi:10.2322/tjsass.54.30 [23] I.V.Ostroumov, K.Marais, N.S.Kuzmenko, N.Fala, Triple Probability Density Distribution model in the task of Aviation Risk Assessment, Aviation, 24(2), 2020, pp. 57–65. doi: 10.3846/aviation.2020.12544 [24] W.D.Brent, Introduction to graph theory, Upper Saddle River, NJ: Prentice hall, 2002 [25] B.Bela, Modern graph theory, Springer Science & Business Media, 2002 [26] F.Neumann, I.Wegener, Randomized local search, evolutionary algorithms, and the minimum spanning tree problem, Theoretical Computer Science, 378(1), 2007, pp.32–40. doi: 10.1016/j.tcs.2006.11.002 [27] J.Knowles, D.Corne, A new evolutionary approach to the degree-constrained minimum spanning tree problem, IEEE Transactions on Evolutionary computation, 4(2), 2000, pp.125–134. doi: 10.1109/4235.850653 [28] S.Pettie, V.Ramachandran, An optimal minimum spanning tree algorithm, Journal of the ACM (JACM), 49(1), 2002, pp. 16–34. doi: 10.1145/505241.505243 [29] J.L.Gross, J.Yellen, M.Anderson, Graph theory and its applications, CRC press, 2018 [30] O.Ivashchuk, I.Ostroumov, N.Kuzmenko, O.Sushchenko, Yu.Averyanova, O.Solomentsev, M.Zaliskyi, F.Yanovsky, O.Shcherbyna, A Configuration Analysis of Ukrainian Flight Routes Network, in: Proceedings of the 16th International Conference on the Experience of Designing and Application of CAD Systems, CADSM, IEEE, Lviv, Ukraine, 2021, pp. 6– 10. doi: 10.1109/CADSM52681.2021.9385263