ZHANG Honghong ,GAN Xusheng,* ,LI Shuangfeng ,and CHEN Zhiyuan

1.Air Traffic Control and Navigation College,Air Force Engineering University,Xi’an 710051,China;2.National Key Laboratory of Air Traffic Collision Prevention,Xi’an 710051,China

Abstract: In order to solve the current situation that unmanned aerial vehicles (UAVs) ignore safety indicators and cannot guarantee safe operation when operating in low-altitude airspace,a UAV route planning method that considers regional risk assessment is proposed.Firstly,the low-altitude airspace is discretized based on rasterization,and then the UAV operating characteristics and environmental characteristics are combined to quantify the risk value in the low-altitude airspace to obtain a 3D risk map.The path risk value is taken as the cost,the particle swarm optimization-beetle antennae search (PSO-BAS) algorithm is used to plan the spatial 3D route,and it effectively reduces the generated path redundancy.Finally,cubic B-spline curve is used to smooth the planned discrete path.A flyable path with continuous curvature and pitch angle is generated.The simulation results show that the generated path can exchange for a path with a lower risk value at a lower path cost.At the same time,the path redundancy is low,and the curvature and pitch angle continuously change.It is a flyable path that meets the UAV performance constraints.

Keywords: unmanned aerial vehicle (UAV),low-attitude airspace,mission planning,risk assessment,particle swarm optimization,beetle antennae search (BAS),cubic B-spline.

1.Introduction

With the advance of low-altitude airspace reform,it has become a current development trend for UAVs to leave isolated airspace and enter low-altitude fusion airspace to develop diversified missions.A large number of disordered low-altitude unmanned aerial vehicles (UAVs)bring harm to ground facilities and public safety [1].Especially with the wide use of small UAVs in urban space,there will be a large number of UAVs performing aerial photography,logistics,security,search,rescue,and other tasks over cities.Meanwhile,the complex low-altitude environment formed by irregular obstacles in dense urban space brings severe challenges to the UAV safe operation [2].At the same time,when the UAVs run at low altitude in the city,it may fall and hurt people and vehicles,increasing the UAV accidents risk [3].Therefore,it is necessary to plan a safe and flyable route for UAVs in the complex urban low-altitude environment,to provide technical support for UAVs low-altitude air traffic management.

Route planning is one of key UAV autonomous flight technologies.There are many mature traditional methods.Common route planning methods include the heuristic algorithm,the mathematical optimization algorithm,the potential field method,the graph theory,etc.

(i) Heuristic optimization algorithm.It is an optimization algorithm that searches for approximate optimal solutions at an acceptable computational cost.It mainly includes ant colony algorithm,genetic algorithm,and A*algorithm.Luo et al.[4] used the ant colony algorithm with positive feedback and good robustness to separate the pheromones according to the advantages and disadvantages,strengthened the pheromones with good effects,and improved the route planning speed.Bao et al.[5] proposed an improved heuristic function and local search strategy of ant colony algorithm with angle factor,it is to solve the algorithm slow convergence speed problem in 3D UAV route planning.Xu et al.[6] presented a route planning approach for rotary UAVs（R-UAVs）in a known static rough terrain environment.Considering the length,height and tuning angle of a path,the route planning of R-UAVs is described as a tri-objective optimization problem.An improved multi-objective particle swarm optimization algorithm is developed.

(ii) Mathematical optimization method.According to the established UAV route planning model,the optimization problem can be transformed into the optimal control model,and the mathematical optimization method can be used to solve it.Zhang et al.[7] proposed a sequential mixed integer linear optimization method.It could simultaneously select speed regulation,direction,and height adjustment to generate a resolution path for the complex low-altitude multi-machine conflict problem.On the premise of route pre-planning,Sarim et al.[8] adopted the mixed integer linear programming method and then carried out fine planning to improve the route smoothness.

(iii) Potential field method.The route planning method based on the potential field constructs a virtual potential field in the airspace,generates a navigation function,and converts the aircraft motion law into the result of the force between objects.Fan et al.[9] proposed a regular hexagonal guidance method based on the artificial potential field method to improve the local minimum problem.At the same time,a relative velocity method was proposed to detect and avoid moving objects in dynamic environment.

(iv) Graph theory.The route planning method based on graph theory firstly uses the rasterization method to model the environment,and then uses the search algorithm to generate the planned path.Commonly used methods are Dijkstra algorithm,Voronoi diagram,probabilistic roadmaps,etc.Angel et al.[10] proposed a route planning of multiple trajectories for a swarm of UAVs based on 3D probabilistic road maps (PRM).In addition,machine learning [11-13],model predictive control [14,15] and game theory [16,17] were also applied in route planning,and they all had certain characteristics and advantages.

Although the current route planning method has been relatively mature,the current route planning basically takes the shortest path and the minimum threat as the performance indicators to generate the UAV flyable path.After the UAV leaves the isolated airspace and enters the national airspace,each area in the 3D space has different risk values,so it is necessary to comprehensively consider obstacle avoidance requirements and safety risk management.If the airspace itself risk is ignored,the generated path will cause hidden danger to the city safety,and the low-altitude UAV air traffic management is not used.In order to ensure the low-altitude UAVs flight safety,it is necessary to consider the urban low-altitude airspace risk assessment.The path can meet the obstacle avoidance requirements and minimizes the path risk by combining the different urban areas risk maps.In view of the above problem,this paper studies the UAV route planning in the complex low-altitude environment with regional risk assessment.According to the different city modeling area,3D airspace risk maps are established.Combined with UAV performance constraints and obstacle avoidance requirements,a path that takes into account the urban area risks is generated based on the particle swarm optimitation-beetle antennae search (PSO-BAS).Finally,cubic B-spline is used to smooth the planned path to generate continuous curvature and smooth flyable path.

2.Low-altitude airspace modeling

Environmental modeling is the work that needs to be completed in the first step of UAV route planning.The establishment of the model directly affects the effect of path planning.Urban environmental obstacles are numerous,diverse and unevenly distributed.To simplify the airspace running environment,speed up the planning,the city 3D space will be discretized by using the cross grid method.

As shown in Fig.1(a),firstly,a 3D rectangular coordinate systemO-XYZis established,and then a 3D areaABCD-EFGHis constructed in the coordinate system,where theABCDplane is on theXOZplane,and then the UAV’s low-altitude operation airspace is placed in this 3D area,ABandAEare respectively equal to the length and width of the airspace where the UAV operates.

Fig.1 Schematic diagrams of division of planning space and arbitrary plane

Once the planning space is obtained,it can be further divided.Firstly,ABCD-EFGHis divided intonequal parts along theYaxis to obtain (n+1) planes.Then,the arbitrary plane is divided intolequal parts along theZaxis andmequal parts along theXaxis,as shown in Fig.1(b).In this way,the planning space is discretized inton×m×lgrids.In practical applications,the division of the grid size should be based on the premise that the UAV can move freely in the unit grid,that is to say,nandmshould be selected accordingly,andlis the division in height.This can give a good balance between the environmental information amount storage and the path planning accuracy.

After the above processes,the low-altitude operation airspace of the UAV can be represented by a collection of discrete points.The airspace coordinates after rasterization correspond to the node number one by one.The coding rules can be used to convert the airspace coordinate information to the node number.

The parks,streets,buildings,residential areas,and other areas in the city low-altitude environment are regarded as static obstacles for the UAV operation.They are scattered in different areas in the city.For towering buildings,the UAV avoids collisions by flying around.For lower areas,it carries out overflight.In order to reduce the airspace structure complexity and facilitate the effective obstacle avoidance,various obstacles are simplified into cuboids.

3.Regional risk assessment

In the complex urban low-altitude environment,due to the differences in population density,flight height,ground cover,and other parameters of UAV operation regions,the operational risks are also greatly different.Therefore,it is necessary to conduct discrete risk assessment for each grid area and quantify risks.Each position corresponds to a risk value [18].Then×m×l3D risk assessment matrixRis constructed.The risk matrix of thek(k=1,2,···,l)level is expressed as

wherer(pi,j,k)(i=1,2,···,n;j=1,2,···,m;k=1,2,···,l)represents the risk assessment value within each grid area in 3D space,and (i,j,k) represents the coordinate value in 3D space.

In the 3D urban airspace,then×m×lUAV running path matrix can be constructed,the path matrix of thekth level can be expressed as

wherem(pi,j,k)(i=1,2,···,n;j=1,2,···,m;k=1,2,···,l)represents whether each grid area in the 3D space is flown over by the UAV,denoted as

Therefore,the cost of considering regional risk assessment is expressed as

The lower the risk assessment value,the less security threat the path poses.At present,the mortality rate is usually used as a method to evaluate the risk UAV operation[19-21].The risk assessment value calculation process in each grid area is described below.

3.1 Risk assessment of UAV impact on humans

Due to the high people density in urban space and the high value of ground property,the UAV falling accident often causes higher loss of people and property.Therefore,urban route planning considering regional risk assessment can plan a path with lower risk value for UAVs.It can reduce operational risk to a certain extent.UAVs operating in urban space pose a certain threat to ground personnel due to their reliability and the difference in operating areas.Currently,UAVs are mainly represented by accident fatality rate [22] of UAV system:

wherefGrepresents the UAV reliability index,it represents the system crash rate due to its own failure;Nexprepresents the people number exposed to the UAV ground impact accident;P(f) represents the death rate of the system impact.Nexpcan be expressed as

where ρ represents population density;Aexprepresents the killing area of ground collision when the UAV system falls down.Combined with [23],Aexpis related to the UAV itself physical properties and the sliding parameters,as shown in Fig.2.It is expressed as

whererprepresents the ground personnel radius;Ruavrepresents the UAV maximum radius.According to the geometric relationship in Fig.2,d=hp/tan θ ,whereθ

Fig.2 Schematic diagram of the killing area of falling UAV

represents the UAV sliding and falling angle,and it can be determined by the following formula:

whereVyandVmaxrespectively indicate the UAV fall vertical speed and their own maximum speed;Fdrepresents the UAV air resistance during it falls,grepresents gravitational acceleration,RIrepresents the drag correlation coefficient,it is associated with its physical properties;Arepresents the UAV area; ρArepresents air density;vrelrepresents the UAV actual airspeed when it crashes.

The UAV impact fatality rateP(f) can be expressed as

whereEimprepresents the impact kinetic energy and it is calculated withis defined as the required impact capacity when the mortality rate reaches 50% whenpsis set as 0.5;β is defined as the impact capacity critical value for the death events whenpsis set as 0.Shading parameterpsrepresents the impact degree of UAV system ground impact event on urban ground personnel,and its value is between [0,1].The larger the value is,the better the ground shelter effect is.According to the actual situation of urban ground shelter effect,the various types shelter parameter settings of areas are shown in Table 1.

Table 1 Masking parameters

3.2 Risk assessment of UAV impact on vehicle

During the UAVs operation in cities,due to the numerous towering buildings,the planned flying path is often over the road.The UAVs fall down due to a failure and collide with vehicles on the ground,causing traffic accidents and injuries.Therefore,in the urban 3D route planning process,it is necessary to consider the risk assessment of UAV impact on vehicles.

The expected death rate of a UAV hitting a ground vehicle can be defined as the deaths number per hour caused by the UAV falling,it can be expressed as

whereTrepresents the average deaths number caused by each traffic accident;Crepresents the UAV hitting the vehicle probability.Ccan be defined by the ratio of the all vehicles projected total area to the covered road total area:

whererepresents the vehicles projected area on the ground,Nrepresents the vehicles number calculated byN=KL,Krepresents the traffic density (the vehicles number on the road per unit length),Lrepresents the road length,Sroadrepresents the road area calculated bySroad=DroadL,andDroadrepresents the road width.

3.3 Three-dimensional route planning model considering regional risk assessment

If regional risks are not taken into account,the property index of urban airspace air route planning isJ0=ω1Jl+ω2Js.If regional risks are taken into account,the performance indicators of urban airspace route planning is expressed as

Small UAVs flying in urban space are limited by their own performance,and they often cause safety hazards when performing large maneuvers.Therefore,flight constraints and terrain constraints need to be considered in the planning process.

(i) The maximum horizontal turning angle.Limited by its own hardware performance,when the UAV turns in a horizontal direction,the turning angle cannot exceed the maximum horizontal turning angle Δψmax.Assume that inNpath assembly points,and thenth horizontal turning angle track segment compared to the (n-1)th track segment is Δψn.Then,the horizontal turning angle constraint is

(ii) The maximum pitch angle.Pitch angle refers to the angle when the UAV climbs up or dives down.Due to performance limitations,the high and low angle of the UAV in flight cannot exceed the maximum high and low angle θmax.Assuming that inNpath assembly points,the pitch angle between thenth track segment and the (n-1)th track segment is θk,then the maximum pitch angle constraint is

(iii) Terrain constraints.The flight altitude and terrain altitude should meet the safety threshold requirements,and the terrain constraints can be expressed as

whereHsafeis the safety threshold;Hteris the terrain height where the waypoint is located;znis the flight height of thenth track segment in the flight path.

The total flight path risk value in the urban airspace is used as the objective function,and obstacles such as nonflyable buildings in the low-altitude airspace are used as path constraints.The parameter that needs to be optimized in the UAV route is the set point of the planned path.Therefore,the 3D path model can be simplified to the following expression,and the model considers the urban low-altitude areas risk assessment:

4.3D route planning based on PSO-BAS algorithm

4.1 Standard PSO

PSO is an optimization algorithm.It simulates the birds random predatory phenomena.Each particle can be regarded as a bird,it will have individual and group information feedback in the predation process.Each bird represents a possible solution to the optimization problem.When a bird finds food,other birds in the group will move towards it.PSO algorithm is to use the birds’ information sharing characteristics to form a process from dispersion to concentration.All particles have a fitness value determined by the optimized function,and each particle has a speed to determine the direction and its flight distance.The algorithm initializes a group of random particles (random solutions),and then searches for the optimal solution through iterative updating.In the PSO algorithm,each particle has a memory to track the previous generation optimal position during iteration: one is the optimal position found by the particle itself.It is called the particle individual optimal position.The other is the optimal position found by the whole group.It is called the particle global optimal position.

It is assumed that there areNparticle in theD-dimensional search space,that is,the particle swarm population size isN,theith particle position parameter in theDdimensional can be expressed asxi(k)=(xi1(k),xi2(k),···,xiD(k)).The optimization problem cost function is used to determine whether the particle current position is better than the historical position.

Up to now,theith particle individual optimal value position parameterpbestis

Up to now,the optimal population value position parametergbestfor all particles is

Theith particle velocity and position iteration rule at thektime is

wherekis the iterations number,ω is the inertia weight;c1andc2are the acceleration factors.It mainly controls the individual information feedback and group information communication of particles.It enables particles to make judgments based on the information obtained by the individual and group optimization,adjust their own positions and approach the potential optimal position.r1andr2are random numbers from 0 to 1.They increase the fault tolerance and particles optimization ability.

4.2 BAS algorithm

The BAS algorithm was put forward in 2017 based on the beetle antennae foraging principle.It mainly detects food smell based on the beetle antennae tentacles and determines its own direction.If a higher odor concentration is detected on one side of the antenna,the beetle will rotate in the same direction.Otherwise it will turn to the other side.BAS algorithm flow is as follows:

Step 1For them-dimensional optimization problem,the centroid is expressed asx,left-whiskerxl,rightwhiskerxr,and two-whisker distanced.x,xl,andxrare allm-dimensional vectors.

Step 2Because the beetle head orientation is random,a randomm-dimensional unit vector is generated to represent the vector that the left whisker points to the right whisker

where rands(·) stands for random function.

The relation between the left and right whiskers and the mass center spatial coordinates is

wheredtrepresents the distance between the two whiskers in thetth iteration.xtrepresents the beetle centroid position in thetth iteration.

Step 3Calculate the fitness valuesf(xl) andf(xr)of the left and right whiskersxlandxr,and judge the beetle direction according to the size relationship betweenf(xl) andf(xr).

where sign (·) is the symbolic function,and δtis the step size of thetth iteration.

Step 4Calculate the fitness value after the beetle movement,and update the distance and step size between the left and right whisker

wheredtis the distance between the two whiskers in thetth iteration; eta_dand eta_δ are the two-whisker distance and the step size decay coefficient respectively.

Step 5Judge whether the iteration end condition is met.If yes,end the iteration;otherwise repeat Steps 2-4 until the condition is met.

4.3 PSO-BAS algorithm

The BAS algorithm biggest limitation is its individual singleness.When a certain iterations number is reached,the step size attenuation will lead to the beetles movements in all directions that are too small.Therefore,it is difficult to jump out after falling into the local optima.Using a fixed step or a larger initialization step may skip the best and easily lead to unstable results.With the information sharing characteristic among the PSO particles,a PSO-BAS algorithm is proposed in this paper.In this algorithm,the PSO individual optimal value comparison process is changed to BAS optimization,so as to update the individual and global optimal value [24,25].

The PSO algorithm function is to make the “beetle”distribution more dispersed.It is to make all close to the optimal value through the different particles information exchange.At the same time,changing the PSO comparison process to BAS for further optimization can better improve the convergence speed and prevent premature local optimization due to convergence.The algorithm specific process is described as follows:

Step 1Initialize the population size,speed and position of particles.

Step 2Evaluate the fitness of each particle.

Step 3Update individual and global optimality through BAS.

Step 4The PSO approaches dominant particle in (16)to the global optima.

Step 5Update the BAS parameters.

Step 6Judge whether the accuracy standard is met.If the iterations maximum number is not met,then turn to Step 2.

4.4 Cubic B-spline smoothing path

The urban space 3D route planning obtained based on PSO-BAS algorithm basically satisfies the UAV constraint conditions.However,in the actual flight process,the planned flight path often has sharp angles and discontinuous curvature,so it is necessary to conduct smoothing processing on the flight path to generate a smooth and flyable 3D path.B-spline is a special case of Bezier curve.By approximating the polygon,a smooth curve can be obtained.Since it has continuity and will not affect the global situation when changing control points position,it has been widely used in track smoothing [26].

Given (n+1) control pointsPi(i=0,1,···,n),thenntimes uniform B-spline curve can be expressed as

whereBi,n(t) is then-order (n-1) degree B-spline curve basis function.The B-spline curve is composed of curve segments,and adjacent curves have the same control points.The definition ofBi,n(t) [26] can be expressed as

In order to facilitate local curve control,cubic B-spline curve is selected to smooth the UAV track.The matrix can be expressed as

Cubic B-spline curve formula is used to generate a smooth track curve with continuous curvature.It satisfies UAV performance constraints,as shown in Fig.3.The blue line is the track obtained after cubic B-spline curve smoothing processing.

Fig.3 Cubic B-spline curve smoothing processing

5.Simulation analysis

In order to verify the effectiveness and applicability of the urban low-altitude UAV flight route planning considering regional risk assessment proposed in this paper.The Xidian University North Campus is selected as the UAV track planning background.The satellite image is shown in Fig.4,and the starting and ending positions are marked.

Fig.4 Map of Xidian University North Campus

The route planning method flow chart considering regional risk assessment is shown in Fig.5.

Fig.5 Route planning process based on PSO-BAS

Since the same area has great differences in parameters in different time periods,the parameters are selected to refer to a specific moment instantaneous value in the route planning scene during the simulation process.It can be estimated by historical data.The parameters required for risk assessment in this planning scenario are shown in Table 2.The parameters required for the PSO-BAS algorithm are shown in Table 3.

Table 2 Values of regional risk assessment parameters

Table 3 PSO-BAS algorithm required parameters

According to the planning method proposed in this paper,the risk value in the low-altitude airspace is evaluated,and then the comprehensive cost value required by the UAV route planning is comprehensively considered to generate discrete path points.Finally,cubic B-spline curve is used to smooth the path to obtain the UAV flyable path,as shown in Fig.6.

Fig.6 Schematic diagram of low-altitude airspace route planning

In order to verify whether the spatial curve satisfies the UAV maneuvering performance constraints,the smoothing spatial track is divided into horizontal and vertical directions.The UAV maximum pitch angle and turning radius are determined by calculating the curve derivative respectively.As shown in Fig.7 and Fig.8,the step size is one coding counting unit,the spatial track curvature is continuous,and the curvature value is less than 1,and the spatial track pitch angle is less than π/4.It conforms to the UAV performance constraints.Therefore,the path obtained after smoothing processing can be used for the UAV actual flight.

Fig.7 Curvature change of space track

Fig.8 Spatial track elevation angle variation

In order to verify the PSO-BAS algorithm superiority proposed in this paper,the PSO-BAS algorithm is compared with the paths planned by the PSO algorithm,ant colony optimization (ACO) algorithm,and PSO-ACO.The results are shown in Fig.9.The path risk value trend with the iterations number is shown in Fig.10.After improvement,the PSO-BAS algorithm completes the search process at 55 iterative times.It is faster than other algorithms.At the same time,the cost risk value tends to stabilize,reaching 8.75×10-7,and the optimization is also stronger than other algorithms.Therefore,it can be concluded that the PSO-BAS algorithm can quickly plan the flyable path,and at the same time can effectively reduce the redundancy,reduce the risk value,and improve the planning effect.

Fig.9 Comparison of different planning algorithm tracks

Fig.10 Search process of different solving algorithms

The path risk value and path length in the planning method considering risk assessment and the planning method without risk assessment are compared.The results are shown in Table 4,and the analysis show that the planning method considering risk assessment through additional pay 15% of the path cost,in return for 86%lower risk value of the safe path,and it is helpful for UAV in complex low safe operation environment.

Table 4 Performance comparison of route planning methods

6.Conclusions

In this paper,a relatively safe and smooth UAV flying path is planned based on the characteristics of complex urban low-altitude airspace and regional risk assessment.Aiming at many kinds of obstacles characteristics and high uncertainty in urban low-altitude airspace,a complex low-altitude environment containing dense obstacles is constructed to operate close to the actual city.In view of the threat posed by UAV crash to urban space with high density of people and property,based on regional risk assessment,the path risk value is considered in the route planning process to generate a relatively safe planning path.Aiming at the problem that the discrete path precision generated by PSO algorithm is not enough,the PSO-BAS algorithm is proposed,and the path is smoothed by cubic B-spline curve to get flyable paths that meet the UAV performance constraints.