=Paper=
{{Paper
|id=Vol-3101/Paper24
|storemode=property
|title=Risk of mid-air collision estimation using minimum spanning tree of air traffic graph
|pdfUrl=https://ceur-ws.org/Vol-3101/Paper24.pdf
|volume=Vol-3101
|authors=Ivan Ostroumov,Oleg Ivashchuk,Sergii Babichev
|dblpUrl=https://dblp.org/rec/conf/citrisk/OstroumovIB21
}}
==Risk of mid-air collision estimation using minimum spanning tree of air traffic graph==
https://ceur-ws.org/Vol-3101/Paper24.pdf
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