，

School of Air Traffic Management，Civil Aviation University of China，Tianjin 300300，P.R.China

Abstract: With the rapid growth of the number and flight time of unmanned aerial vehicles（UAVs），safety accidents caused by UAVs flight risk is increasing gradually. Safe air route planning is an effective means to reduce the operational risk of UAVs at the strategic level. The optimal air route planning model based on ground risk assessment is presented by considering the safety cost of UAV air route. Through the rasterization of the ground surface under the air route，the safety factor of each grid is defined with the probability of fatality on the ground per flight hour as the quantitative index. The air route safety cost function is constructed based on the safety factor of each grid. Then，the total cost function considering both air route safety and flight distance is established. The expected function of the ant colony algorithm is rebuilt and used as the algorithm to plan the air routes. The effectiveness of the new air route planning model is verified through the logistical distribution scenario on urban airspace. The results indicate that the new air route planning model considering safety factor can greatly improve the overall safety of air route under small increase of the total flight time.

Key words：air transportation；unmanned aerial vehicle（UAV）；air route planning；safety cost；ground risk assessment；improved ant colony algorithm

0 Introduction

Unmanned aerial vehicles（UAVs）have been widely used in urban logistical and distribution in re?cent years. By June 2019，337 000 industrial UAVs had been registered in China alone，with a total of more than one million flight hours［1］. However，the safety accidents caused by UAV flight risks are in?creasing gradually. These accidents have had seri?ous consequences for people and property on the ground. Before the explosive growth of UAVs，it is of great significance to study their flight safety.

According to the investigation and analysis of the previous UAV safety accidents，the characteris?tics of unmanned aircraft determine that the safety risk of UAV flight shifts from the impact on board to the ground. Joint authorities for rulemaking on un?manned systems（JARUS）issued the licensed oper?ation risk assessment guidance material（SORA）for UAV operation scenarios and provided a general framework for UAV system operation risk assess?ment［2］. SORA divided the potential damages of UAV operation into three categories，including the damages to the third party in the air，to the third par?ty on the ground and to the critical infrastructure on the ground. The latter two were clearly defined as the main risks of UAV operations. In other words，the safety of ground people and property under the UAV air route became the key to the safety of UAV operations. Therefore，ground risk assess?ment should be considered in advance in the process of air route planning to make sure the mitigation of UAV flight risk.

In order to minimize the damage of UAV crash?es to people on the ground at the level of strategic planning，safety risk assessment results should be added to air route planning in advance. Scholars and scientific institutions have conducted lots of studies in ground risk assessment affected by UAV opera?tions. Ground risk was described as the uncertainty of UAV system failure under specific system config?uration，operating environment conditions and mis?sions［3-6］. Ground impact area of UAV crashes［7-10］was described as the probability distribution of the impact area after the crash. Ground object exposure distribution［7，11-12］was described as the probability of the presence of damaged objects（people and proper?ty）at a specific location and time. The exposed ob?ject distribution model can be divided into unified model and comprehensive model. Injury model caused by UAV crashes［13-14］was described as the se?verity of the drone’s damage to humans or property at the specific time and place.

From the forward flow，these models have been widely used in the evaluation of UAV flight safety. However，from the perspective of reverse flow，ground risk assessment is rarely used in air route planning. A new air route planning method based on ground risk assessment and its calculation method are proposed in this paper which focuses on an air route planning method based on ground risk assessment and its algorithm.

1 Air Route Planning Model

1.1 Analysis of air route planning

At present，studies on air route planning meth?ods［15-18］fall into two catagories. One is based on in?telligent algorithms，such as intelligent bionics and particle swarm optimization，and the other is based on graphical algorithms，such as Voronoi diagrams and Laguerre diagrams. Through the analysis of the existing literature，we found that most studies on path planning focused on the optimization of the dis?tance cost and smoothness of the air route. Howev?er，due to the important role of air route in safety，ground risk assessment［19-21］should be considered in air route planning.

In order to ensure the safe and convenient flight of UAVs，two objectives should be considered in the process of air route planning：Safety cost and distance cost. As shown in Fig.1，the safety cost in route planning focuses on the impact of UAV flight on the ground casualties below the route，and the optimization function should be built based on the safety index of risk assessment. The distance cost mainly considers the obstacle avoidance，flight dis?tance and non-linear coefficient.

Fig.1 Cost model of UAV air route planning

1.2 Ground risk assessment

As shown in Fig.2，the UAV system and ground characteristics are two major considerations in ground risk assessment. Reliability and failure probability are related to the probability of UAV crashes. The impact area of a crash is calculated ac?cording to the dynamics and kinematics characteris?tics. From the perspective of the ground people，the protective ability of ground cover and the population density have a great influence on the accident severity.

Fig.2 Influence factors of ground risk assessment

1.2.1 Grid division of the ground surface

In order to evaluate the safety costs on the ground，the ground surface below the air route should be rasterized first.In order to ensure the integ?rity of safety accident analysis within the grid，it is as?sumed that when the UAV falls in the center of the grid，the impact area of the accident falls completely within the grid. Therefore，it is necessary to analyze the area affected by an UAV crash in order to select the appropriate grid edge length. Fig.3 shows the ar?ea affected by an UAV crash accident，which is de?fined as the maximum range of human body cylinder invaded by the UAV cylinder. When only the verti?cal movement of the UAV is considered，the area af?fected by the accident can be expressed as

Fig.3 Area affected by UAV crashes

whererUAVrepresents the equivalent wingspan radi?us of the UAV andrpthe radius of human body.

Further，the horizontal displacement still needs to be considered after the collision between the UAV and the human body. The horizontal displace?ment could be calculated by

wherehprepresents the height of human body and the parameterγthe contact angle of the collision be?tween the UAV and the human body. The area af?fected by the accident can be expressed as

According to the above analysis，the grid edge length can be calculated by

1.2.2 Grid safety factor

In order to quantify the flight safety attributes of UAVs in the barrier-free grid，the risk of casual?ties caused by UAV collision accidents to ground people is analyzed. The safety factor of each grid is defined as the number of casualties caused by UAV collision accidents per flight hour. The safety factor could be expressed in terms of the probability of UAV collision accidents，the probability of casual?ties after accidents and the total population affected by accidents，namely

where the parametersrepresents the safety factor of the grid defined by the number of ground casualties per flight hour.PgsandNexprepresent the probability of UAV collision accidents and the total population on the ground affected by accidents，respectively.

1.2.3 Probability of fatality

The probability of fatality［14］affected by UAV collision accidents in each grid is related to a few fac?tors，including the UAV characteristics and grid properties. The UAV characteristic factors are relat?ed to the operating altitude and velocity. The grid properties are in connection with the protection capa?bility that can be provided by the shelter in the grid and the population density. The probability of fatali?ty is shown as follows

where the parameterαis the impact energy required for a fatality probability of 50% whenPS=6，which can be valued as 100 kJ normally. The param?eterβrepresents the impact energy threshold whenPSgoes to 0，which can be considered to be a con?stant with 34 J based on fatality limit. The parame?terEimpis the kinetic energy when the ground impact accident occurs. The speed used when calculatingEimpis higher than the vertical falling speed and 1.4 times of the maximum design speed［22］.PSrepre?sents the total protection factor of the grid which re?lated to the category and area of the shelters onto the surface. The protection factor of different shel?ters is listed in Table 1. The total protection factor can be calculated according to the percentage of each shelter area as follows

where the parameterhrepresents the category of shelters andPhSthe protection factor of shelterh.MhandMjrepresent the area of shelterhand total area of the grid，respectively.

Table 1 Ground shelter classification and protection fac?tor

1.3 Air route cost

The purpose of the route planning method pro?posed in this paper is to find a safe and short air route from the origin to destination under the premise of avoiding obstacles.Therefore，the total air route cost function under the dual constraints of safety cost and distance cost is constructed as follows

2 Algorithm of Air Route Planning

The ant colony algorithm is selected as the method of solving the route planning problem.In order to satisfy the cost function as mentioned above，it is necessary to improve the expected function of ant colony algorithm first.The total cost function of air route in section 1.3 is taken as the expected function of air route planning.

Fig.4 Flow chart of improved ant colony algorithm

2.1 Calculation flow

The calculation flow of the improved ant colo?ny algorithm is shown in Fig.4. The ant colony starts from the original grid and searches the barrierfree adjacent grids. The selection probability of each adjacent grid is based on the expected cost function.The determination of the next grid is according to the results of the roulette method. The whole pro?cess is over until the ants get to the destination or trap in a local optimal solution. After the iteration of appropriate generations，the expected air route opti?mized by both safety and distance costs is finally ob?tained.

Fig.5 Search space range and variable search radius of im?proved ant colony algorithm

2.2 Algorithm improvement

The traditional ant colony algorithm has limita?tions for wide-range route search. The problems en?countered in the study mainly include three as?pects［15］. First，the search space is too large，which leads to low efficiency and slow convergence speed.Second，search step size is small which is not suit?able for long distance search. Third，there is no di?rection to inspire the search strategies which may produce path circuitous redundancy. To solve these problems，search space range and variable search ra?dius are adopted to improve the traditional ant colo?ny algorithm. Specifically，the problem of search ef?ficiency can be solved by reasonably controlling the size of search space. The line between the starting and stopping points is used as the buffer of variable distance to form the search space（Fig.5）. The buf?fer distance increases gradually from the initial value until there is an optimal route solution in the search space. At the same time，in order to improve the ef?ficiency of path search，variable length search is ad?opted in the search process，that is，the search step size is determined according to the safety factors in the local search space. For example，when the safe?ty factors in the search space are less than 10-7，the step size adopts two grid units，as shown in Fig.5.

2.3 Probability calculation of optional adjacen?cy grid and pheromone update

The selection probability of each adjacent grid for next step is calculated by

whereis the probability of thekth ant moving from pointito pointj，the parameter allowedkthe nodelist that the ant is allowed to access in the next step，τijthe concentration of pheromone from pointito pointj，ηijthe expectation from pointito pointjwhich is calculated by the total cost function estab?lished in Eq.（8），ξthe pheromone heuristic coeffi?cient which represents the importance of phero?mone，andψthe expectation heuristic coefficient which represents the importance of expectation.Pheromone concentration is updated after the preset iterations，and the update rule is shown in

In order to avoid falling into the local optimum in the path search process，in the transfer probabili?ty calculation of the track point transfer process，the connection between the current node and the termi?nation node is introduced into the heuristic function according to the evaluation function in the A*algo?rithm. It can solve the local optimum problem and improve the efficiency of the algorithm. The heuris?tic function is as follows

whered'represents the cost andthe cost after normalization. The subscript in the formula repre?sents the node code，O the original point，and E the ending point.iandjrepresent the node number in the path.represents the weight of the cost between next node and the end point；ρrepresents the path cost threshold that starts to introduce direc?tion information，in order to prevent ants from being affected by direction information and falling into lo?cal optimality in the process of moving.Candρare constant which determined in practical application.

3 Application to Logistical Distri?bution Scenario in Urban Air?space

3.1 Description of task scenario

UAV logistical distribution has the advantage of reducing human contact. It has strong practicabili?ty in urban emergency supplies and medicine distri?bution during the period of COVID-19. UAV logis?tical distribution in Jianghan district of Wuhan is se?lected as a typical case. In this case，the UAVs are used to carry out the express delivery and catering services on this area.

3.2 Parameters of UAVs

The Maxi Joker 2 is selected as the delivery drone，and the main design parameters are shown in Table 2. The small design mass and moderate speed are suitable for small-batch and high-frequency flight activities in urban airspace. It is assumed that the probability of safety accidents caused by UAV sys?tem failure is 10-5per flight hour. The influence of environment on the reliability of UAV is not consid?ered in the model.

Table 2 Parameters of Maxi Joker 2

3.3 Ground surface rasterization

The distribution of the surface coverage on the ground is mapped as shown in Fig.6，where differ?ent grayscale represents different land use classifica?tion. Hankou railway station is selected as cargo storage place and three hospitals are selected as the shipping address. Two different kinds of air route planning methods are used to show the roles of safe?ty factors. The first method takes safety factors and distance into considerations，as shown in Eq.（9），while the second method only takes distance as the constraint. The flight distance，flight time，average route safety factor and casualty population of the dif?ferent planned air routes，considering the safety cost or not，are compared.

Fig.6 Distribution of surface coverage over the ground in flight area

According to the parameters in Table 2 and the grid size calculation method in Section 2.2，the grid size is set as 100 m×100 m，and a 73×103 grid ar?ray is constructed to cover the area completely.Based on the distribution of surface coverage and the protection factor provided by different kinds of shelters on the ground in Table 1，the protection factor of ground grids in the flight area is calculated by Eq.（8）.

The ground population density corresponding to the flight area is an important variable for evaluat?ing the risk severity of UAV collision accidents.The population data on this area is collected by mo?bile carrier data. The population distribution data collected at 15：00 is used，and the population distri?bution density map is shown in Fig.7.

Fig.7 Grayscale map of population distribution density map in each ground grid

The safety factor of the grids is calculated by the protection factor and population density.

Table 3 Comparison of main technical indexes of each planned air route

3.4 Comparisons of planned air routes

The calculation results of the main indicators for the planned air routes from origin EP to each des?tination SP are shown in Table 3. Taking the planned air route from SP3 to EP as an example，the flight distance of the planned route with safety constraint is 6 777 m，which is 580 m longer than that of the planned air route without safety con?straint，with an increase rate of about 9.4%. How?ever，the average safety factor of the route through the grid is decreased from 5.7×10-5to 2.3×10-5，with a safety improvement of 59.7%. The total ca?sualty population on the route had been reduced from 2.9×10-7to 1.3×10-7.

Therefore，the overall route safety has been greatly improved on the premise of a small increase in total length and flight time when taking safety fac?tors into consideration. As shown in Fig.8，the air route changes locally when the safety constraints are considered. The flight distance and flight time in?crease slightly compared with the planned air route without safety constraints. But the average safety factors of planned air route decrease to a great ex?tent. At the same time，the casualty population in the whole air route decrease as well.

Fig.8 Comparison of planned air routes with or without safety

4 Conclusions

A new kind of air route planning model consid?ering the dual optimization conditions of safety and distance is established. The safety constraints in the model are based on the ground risk assessment under the air route. The effectiveness of the new air route planning model is verified through the logistical dis?tribution scenario in urban airspace. By comparing the main technical indexes of planned air routes with or without safety constraints，the results show that the safety of the planned air routes is significantly im?proved after considering the safety factors，while the total length and flight time of the planned air routes are slightly increased. The new air route planning model with safety factors improves the overall safety of the planned air route greatly when the distance cost increases to an acceptable level.