Risk Assessment of Unmanned Aerial Vehicle Flight Based on K-means Clustering Algorithm

，，，

College of Civil Aviation，Nanjing University of Aeronautics&Astronautics，Nanjing 211106，P.R.China

Abstract:To quantify unmanned aerial vehicle（UAV）flight risks in low-altitude airspace，we analyze the factors of UAV flight risks from three aspects:flight conflict，flight environment，and traffic characteristics.The aerial risk index and ground risk index of the UAV are constructed，the index screening model and the UAV flight risk assessment model are established，and a UAV flight risk assessment model based on K-means clustering has been proposed.Meanwhile，numerical simulations show the proposed method can not only evaluate the UAV flight risks effectively，but also provide technical support for UAV risk management and control.

Key words:unmanned aerial vehicle（UAV）；risk factor；risk index；assessment model；K-means clustering

0 Introduction

In recent years，Chinese civilian unmanned aerial vehicle（UAV）has developed rapidly. UAV continues to highlight advantages in practice，such as aerial photography，aerial mapping，search and rescue，logistics and express delivery. However，due to the lack of safety management standards，UAV flight accidents occur frequently，which directly restrict the development of UAV.It is urgent to implement an assessment method of UAV flight risk and to provide theoretical basis and technical support for effective control of UAV.

In 2005，Weibel et al.［1］developed a model of midair collisions between a UAV（the“threat”aircraft）and other（“threatened”）aircraft based on the threatened aircraft parameters，including the area of exposure，distance，airspace volume and flight hour，and they also created an event-based UAV ground risk model according to the UAV system failure rate，the lethal debris area，the population density of the area，the penetration factor and fall mitigation measures.In 2007，Clothier et al.［2］established a UAV flight risk assessment model based on conditional probability.In 2010，F(xiàn)ord et al.［3］used satellite images to refine the regional population density distribution and make security risk assessment more accurate. In 2014，Melnyk et al.［4］compared the existing UAV ground impact risk assessment models，and introduced research data from other fields into their assessment models，which alleviating the issue of missing data in UAV safety risk assessment field.In 2015，Aalmoes et al.［5］considered the increased system failure rate during the take-off and landing stages of the UAV，and expressed the total safety risk as the sum of the three stages of take-off，cruise and landing.In 2016，Haartsen et al.［6］proposed a simulation-based method to explore the probability distribution of landing position for fixed-wing UAV and rotorcraft UAV.In 2017，Ancel et al.［7］proposed a real-time risk assessment framework for UAVs，combining UAV system monitoring data with dynamic environmental information，and realized realtime assessment of UAV safety risk through probability graph model based on Bayesian network and UAV ground impact model.In 2019，Primatestaa et al.［8］came up with a mapping method for UAV safety risk based on the existing results，and initially set up a UAV safety risk visualization framework. Mcfadyen et al.［9］proposed a quantitative computation method of collision risk based on datadriven modeling and non-parametric estimation.They used real radar data to extract the spatial and temporal traffic distribution of manned aircraft.Through statistical analysis to estimate spatial overlap probability of manned and unmanned aircraft.Then Mcfadyen et al.assessed UAV spatial and temporal collision risk，and confirmed the practicability and effectiveness of UAV collision risk assessment model. La Cour-Harbo et al.［10］established a collision risk model for UAV and general aviation in low-altitude non-controlled airspaces，and the computations showed that the risk of collision between UAV and general aviation in Danish airspace， without mitigation measures， was about 10-6per hour，and this model was more suitable for beyond visual line-of-sight flight.Zhang et al.［11］established a UAV ground impact risk assessment model and a UAV aerial collision risk assessment model based on Refs.［3，12］.They also analyzed the safety risks caused by UAV crashes in different environments and predicted frequency of collision accidents between UAV and civil aircraft.

We consider the aerial risks and ground risks during UAV operation，sort out main factors affecting the safety of UAV flight from three aspects:Flight conflict，flight environment，and traffic characteristics.We establish a multi-dimensional UAV flight risk assessment index system，propose a comprehensive evaluation method of UAV flight risk based onK-means clustering algorithm，and assesse UAV airspace risks and individual UAV risks.

1 Risk Factor Analysis

Low-altitude airspace is a complex system composed of multiple factors such as people，aircraft，operating environment，and management. The flighting of UAV will be affected by various risk factors in low-altitude airspace，which can be summarized into three aspects:Flight conflict，flight environment and traffic characteristics.

1.1 Flight conflict

Flight conflict refers to the situation where the distance between the UAVs and other aircraft in the horizontal or vertical directions is less than or about to be less than the specified separation standard.Flight conflicts mainly include three factors:Conflict number，conflict category，and conflict location.These three elements basically cover all the main characteristics of flight conflict events，which can more comprehensively and objectively reflect the category of UAV flight conflicts and the degree of conflicts.

1.2 Flight environment

The UAV flight environment mainly includes dynamic environment elements and static environment elements.Dynamic environmental elements refer to dynamic information such as complex and changing meteorological conditions，birds，and other flighting activities.Static environmental elements refer to the established structure of low-altitude airspace，such as the position and range of controlled airspace，reported airspace and monitored airspace，the limitations and the requirements of isolated airspace and no-fly airspace，UAV route network planning，take-off and landing position，terrain obstacles and other static information.

1.3 Traffic characteristics

Traffic characteristics describe the context of the current airspace in which an unsafe event may occur such as traffic flow density，traffic flow speed，traffic flow volume，traffic complexity，congestion level，airspace load，UAV activity missions，UAV models，etc.

2 Risk Assessment Index

2.1 Air risk index

Based on the analysis of the UAV risk factors，considering the simplicity and practicability of the index，six airborne risk assessment indexes of the UAV flight volume，average speed，average separation，UAV mixing ratio，convergence approach rate，and collision risk intensity，are established.

Flight volume，average speed，average separation，and UAV mixing ratio are basic statistical indexes，which are obtained by comprehensively considering factors such as flight conflict，flight environment，and traffic characteristics.The convergence approach rate and collision risk intensity are mainly derived from flight conflict factors.

（1）Flight volume

Flight volume refers to the number of UAV flights in a specific airspace at a time（or time period）.The computation formula is

wherentis the UAV flight volume at timet（or time period）and unit is sortie；Mthe whole monitored UAV samples；anda 0-1 variable，indicating whether theith monitored UAV sample falls at timet（or time period）of the monitored data.

Flight volume reflects the degree of crowdedness in the airspace at a time.Flight volume is the most basic statistical index，simple and intuitive，and convenient to be required.The variation trend of other indexes can be analyzed according to the changes of flight volume.Then the flight volume also reflects the holistic airspace operation situation，and lays a great foundation for the UAV flight risk assessment.

（2）Average speed

Average speed means the average flight speed of all UAVs in a specific airspace at a time（or time period）.The computation formula is

whereis the average speed of the UAVs at timet（or time period）andvithe flight speed of theith UAV.

The average speed index is used to reflect the speed of the UAV in the currently monitored airspace.When the most UAVs belong to transportation UAV，the average speed index also reflects the overall efficiency of the monitored airspace.When the relative flight speed of the encountering aircraft is larger，the protection area of the aircraft is correspondingly larger.Under the same distance condition，the greater the average flighting speed of the UAV，the higher the risk of aerial collision.

（3）Average separation

Average separation means the average space separation of UAV in a specific airspace at a time（or time period）.The computation formula is

whereis the average separation of UAVs at timet（or time period）（unit:m），Sijthe Euclidean distance between UAVsiandj.

The average separation index considers from the interaction relationship of the UAV distance，and reflects the dispersion degree in the space and the degree of crowdedness in the currently monitored airspace.The smaller the average separation，the smaller the maneuverable space.At this moment，if the UAV deviates from the planned route because of low-altitude wind shear and navigation errors，the risk of aerial collision will significantly increase. The average separation index measures the current operating situation of the monitored airspace，which is relatively intuitive and convenient to be computed.

（4）UAV mixing ratio

UAV mixing ratio refers to the degree of mixing UAV categories in a specific airspace at a time（or time period）.The computation formula is

whereφ(t)is the UAV mixing ratio，dimensionless；mthe number of UAV models；andthe number of categoryiUAV at timet（or time period）.

There are many categories of UAVs.According to aerodynamic characteristics，UAVs can be divided into fixed-wing UAVs，unmanned helicopters，multi-rotor UAVs，tilt-rotor UAVs，and so on.Different categories of UAVs also have large differences in flight performance and escape avoidance capabilities.When the UAV mixing ratio is larger，low-altitude airspace operation becomes more complicated，and UAV flight will be in the risks.

（5）Convergence approach rate

Convergence approach rate refers to the convergent tendency between UAVs in a specific airspace at a time.The computation formula is

whereηij(Sij，vij)is the convergence approach index（unit:s）.The schematic computation of UAV convergence approach index is shown in Fig.1.

Fig.1 Schematic computation of UAV convergence approach index

The convergence approach index is derived from the traffic collision avoidance system（TCAS）and used to compute the estimated encounter time between aircraft.We take the reciprocal of the UAV encounter time to reflect the degree of convergence.Considering the monitored data of the existing system usually cannot reflect the UAV flight courses accurately，and the UAV is more flexible than traditional aircraft.To consider the worst-case scenario，computing the convergence approach rate assumes that all UAVs are in head-on meet condition.This processing method lowers the sights of parameters in computation，and the index is more simplified to be understood.

（6）Collision risk intensity

Collision risk intensity refers to the degree of danger closeness between UAVs in a specific airspace at a time，which is used to measure the UAV collision risk.The computation formula is

whereμij(Sij)is the collision risk intensity，dimensionless；λthe proportional position gain factor；anddthe minimum UAV safety separation.The schematic computation of UAV collision risk intensity index is shown in Fig.2.

Fig.2 Schematic diagram for calculating the UAV collision risk intensity index

The index of collision risk intensity is derived from the artificial potential field method.The basic idea is to consider the airspace where UAVs fly as a potential field.The flight of a UAV is regarded as the motion in the gravitational field，thus other UAVs in the gravitational field have a repulsive effect on this one.When other UAVs are outside the safety separation of the UAV，it can be considered that the repulsive force of the other UAVs on this UAV is zero.When the UAV is within the safety separation，the repulsive force between the UAVs will present the third power growth.This mutual repulsion between UAVs can be converted into a collision risk intensity index.When a UAV crosses a safe separation boundary，it can be considered as a UAV flight conflict.Meanwhile，when the distance of the UAV approaches again，the intensity of the UAV collision increases gradually，and the collision risk is correspondingly higher.

2.2 Ground risk index

Ground risk index includes landing coverage area and ground impact kinetic energy.Considering the environmental factors including terrain obstacles，we propose a landing coverage area index.Moreover，ground impact kinetic energy is constructed based on three major risk factors and the UAV characteristics.The more flight conflicts，the worse flight environment，and the more complicated traffic，the greater ground impact kinetic energy which brings the greater risk.

（1）Landing coverage area

Landing coverage area refers to the coverage area when a UAV crashes and hits the ground due to system failure，midair collision，etc.The computation formula is

whereAexpis the UAV landing coverage area（unit:mm2），wUAVthe wingspan or lateral dimension of the UAV，LUAVthe length or vertical dimension of the UAV，adnRpthe adult average width.

This index mainly depends on the size of the UAV.If the UAV size is larger，the landing area of the UAV will also be larger，and the impact on the ground will also be greater.In the specific operational risk assessment（SORA）of joint authorities for rule making of unmanned systems（JARUS），the maximum feature size of a UAV is one of the important indexes to measure the UAV ground risk level，the basic reason is the UAV size directly affects the UAV landing area，and affects the UAV ground risk.

（2）Ground impact kinetic energy

Ground impact kinetic energy refers to the amount of kinetic energy when a UAV crashes and hits the ground due to system failure，midair collision，etc.The computation formula is

whereEimpactis the ground impact kinetic energy（unit:J），mUAVthe UAV flight quality，mpthe mass of adults，vimpactthe UAV impact speed，vUAVthe UAV flight speed，hUAVthe UAV flight altitude，andgthe gravitational acceleration.

Ground impact kinetic energy index reflects the risk of UAV to ground personnel from energy perspective. When the impact kinetic energy of the crash UAV is greater，the accident hazard which caused by the UAV is also greater，and the secondary disasters such as fire，explosion，and collapse are liable to occur.When the UAV impact kinetic energy is large enough，it can destroy the building，which brings tremendous potential risk to ground personnel.Therefore，from the perspective of impact kinetic energy，considering the momentum conservation law and the energy conservation law，combining the real-time monitoring data with the UAV performance data，the UAV ground impact kinetic energy can be computed approximate，and assessing the UAV ground risks could be simple and effective.

3 UAV Flight Risk Assessment Model Based on K-means Clustering

wherexikrepresents theith index value of thekth assessment object（k=1，2，3，…，n），the mean of theith index，andyiktheith index normalized value of thekth assessment object.

Step 2Scoring the importance of the index

“What do you mean?” Debbie inquired, more than a little puzzled. Looking at her with love-filled eyes, Tommy said, “Just think of all those years we didn’t know each other.

Invite experts to score the importance of indexes.Experts have chosen from“5，4，3，2，1”corresponding to“very important，important，general，less important，unimportant”.Then remove the highest score and the lowest score，and select the mean as the final importance score of each index.

Step 3Coefficient of variation-importance screening

The coefficient of variation is usually used to

3.1 UAV assessment index screening model

Based on the popularization and application of Delphi method in the screening model［13］，a new index screening model is established in this paper.And the steps of the UAV assessment index screening model are as follows.

Step 1Data acquisition and processing

Design some different simulation scenarios and conduct multiple experiments to obtain the original data，and compute each index value through MATLAB.For eliminating the impact that different indexes have different dimensions and orders of magnitude while retaining the original variation information，and ensuring the comparability of the data，the data has been normalized by the averaging method as estimate the difference of index value.The greater the difference，the more significant the differential information，and the greater the impact on the evaluation result.In order to prevent some important indexes from being deleted because of extremely large coefficient of variation，and to avoid neglecting the meaning of the indexes in quantitative analysis，it is necessary to make a qualitative analysis and judgment based on the importance of the indexes.

Compute the coefficient of variation of the index by Eq.（10）.There are some extreme data in the data set，but they generally do not affect the median value.Therefore，consider the mean of the coefficient of variation and the median of importance as guides，and delete the low coefficient of variationlow importance index.

wherec.v.iis the coefficient of variation of theith index，nthe sample size，andthe mean value of theith index after normalization.

Step 4Correlation screening

whererijindicates the correlation coefficient between theith index and thejth index andyikthe normalized value of theith index of thekth assessment object（k=1，2，3，…，n）.

Step 5Universality analysis

The indexes are obtained through horizontal comparison which experiments screened，and the indexes with higher stability are retained as the key indexes to evaluate the UAV flight risk.

Step 6Rationality determination

SupposeSas the indexes covariance matrix.Stris the trace of covariance matrix which means the sum of the variance of indexes on the main diagonal in the covariance matrix.is the number of indexes after screening andthe number of original indexes.Iis the information contribution of the selected indexes to the original indexes，which means the information of theindexes can reflect theoriginal indexes.The computation formula is

3.2 Risk assessment model for UAV airspace

（1）Initial data matrixX

Assumemis the number of time series samples andnis the number of UAV risk indexes，and establish the initial data matrix as

（2）Normalized data matrixY

First，outlier processing is performed，and the index value above the 95%quantile of each column of the matrixXis replaced by the 95%quantile.Then，we normalize the matrixXto obtain the normalized data matrixY.

For the positive（Bigger is better）indexes

For the negative（Smaller is better）indexes

whereyij(0 ≤yij≤1)is the normalized value of thejth index on theith time series sample.

（3）K-means clustering

①Randomly selectksamples in the data setP={y1，…，yi，…，ym}as the initial cluster centers.

②Compute Euclidean distance from each data pointyitokcluster centersC={C1，C2，…，C k}.

③Set each data pointyiinto the nearest cluster.

④Compute the mean value of the data in each cluster to update the cluster centersC′=，and compute the sum of squared error（SSE）.

⑤Determine whether the change of the SSE is less than the thresholdε.If it is not less，return to step ②.If it is less，output

3.3 Risk assessment model for individual UAV

AssumingMis the sample size of monitored UAV data andnis the number of UAV risk indexes，we establish the initial assessment data matrix as

wherezijis thejth index value of theith sample and these values are calculated by experimental data according to the index formula.

Similarly，the data matrix is normalized by Eqs.（14）and（15），and the risk assessment of the individual UAV is performed by usingK-means clustering algorithm.Then flight risk classification of the individual UAV in different times and spaces is realized.We givekrisk levels tokgradient colors from green（safe）to red（dangerous），and use orange，red，and other colors to warn the UAV flight risks regionally，and finally realize spatial visualization of UAV flight risks.

4 Simulation Analysis and Assessment

The experimental process figure can be given in Fig.3.

Fig.3 Process of experiment

4.1 Indexes analysis

（1）Time-series analysis of indexes

Based on the UAV cloud statistical data from Civil Aviation Administration of China（CAAC）and the complex low-altitude flight situation simulation system from Nanjing University of Aeronautics and Astronautics（NUAA）and fast time simulation method，we simulate the current spatiotemporal density of UAV flight in China，and obtain about 28 h of UAV flight simulation data in a specific airspace.Assuming 5 s as a time period，the time range can be divided into about 20 000 time series samples.Then set 5 s as the basic unit of time series.It can be seen from Fig.4 that when the simulation time reaches the sixth，nineth，24th，and 28th hour，the UAV flight volume reaches a peak.At the moment，the UAV flight activity of simulation airspace is intensive，and accordingly，the average speed of UAVs is at a low level，while the change trend of the UAV mixing ratio is the same as that of the flight volume.The values of convergence approach rate index and collision risk intensity index change more rapidly，because the UAV collision probability significantly increases when the safe separation boundary of the UAV is invaded.In order to highlight the UAV flight risks，these two indexes consider dangerous situations where the UAVs are too close to each other as an abnormal state，which is reflected in the index value showing a sudden curve of“outliers”.It can be summarized from Fig.4 that there is a large convergence trend and collision risk of the UAV in the simulation airspace at about the 28th hour.Therefore，through the UAV risk assessment index screening model，six key indexes of UAV flight risk can be obtained，such as flight volume，average speed，average separation，average collision risk intensity，average landing coverage area，and average ground impact kinetic energy.

（2）Characteristic analysis of indexes

Fig.4 Change curves of UAV flight risk assessment index with time series

Fig.5 Correlation between UAV flight risk indexes and flight volume

In order to lucubrate the characteristics of UAV flight risk indexes，the figure of correlation between UAV flight risk indexes and flight volume is drawn.It can be intuitively seen from Fig.5 that the average speed of the UAV gradually decreases with the increase of the flight volume.For the average separation，when the flight volume is less than ten，the average separation of UAV will be about 20 000 m.When the flight volume is more than ten and less than 15，the average separation of UAV instead rises to over 30 000 m，because the number of monitored UAV samples with a flight volume more than ten is too small，leading to conclusions derived from a flight volume more than ten that are not universal.The convergence approach rate index and the collision risk intensity index have no direct relationship with the flight volume.Since the current UAV flight volume is far from reaching the saturation of the airspace，and the collision risk intensity depends more on the random encounter process between the two UAVs.If the UAV flight volume in China increases in the future，there may be an inflection point，causing the collision risk intensity to increase rapidly.

4.2 Assessment results

Fig.6 UAV flight risk classification

Excluding the time samples with zero flight volume，the UAV flight risk assessment model based onK-means clustering algorithm is used to cluster the above UAV flight risk assessment index data to obtain the UAV flight risk classification in Fig.6.It can be seen from Fig.6 that when the simulation time is around the sixth，nineth，24th，and 28th hour，the flight risk level of the UAV airspace is relatively high，which is more consistent with the time-series curve of the UAV flight volume index.It verifies the rationality of the assessment model to a certain extent. However，conducting flight risk assessment for UAV airspace，can only analyze the safety situation of UAV airspace at a macro level，and cannot be refined to the individual UAV flight risk. It can only provide certain warnings to controllers or managers，but cannot provide scientific guidance for UAV management and control. Therefore，based on the assessment of the UAV flight risk level，we make a preliminary attempt and exploration on the classification of the individual UAV flight risk level.As a result，based on C# language，a UAV flight risk visualization system is established.The black mark indicates the normal state，the orange mark indicates the alarm state，and the red mark indicates the dangerous state.It can be seen from Fig.7 that the two red-marked UAVs are very close to each other. Without conflict resolution，the two UAVs are likely to collide with each other in the air，causing damage to property and ground personnel.

Fig.7 UAV flight risk demonstration system

5 Conclusions

This paper extracts and constructs six assessment indexes from two aspects:Aerial risk and ground risk，including flight volume，average speed，average separation，average collision risk intensity，average landing coverage area，and average ground impact kinetic energy. Based on theKmeans clustering algorithm，a UAV flight risk assessment model is established，and the UAV flight risk classification is realized.Through the analysis of simulation data，the spatiotemporal characteristics of the UAV flight risk index are extracted，and the rationality of the UAV flight risk assessment model is verified.As a result，a visualized system of UAV flight risk based on C#language is provided，which provides certain technical and system support for the future scientific management and efficient management of UAV.