# Research on an Obstacle Avoidance Method for UAV

Authors: Zhenqi He; Lu Yao
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

With the continuous development of UAV technology, UAV has been widely used in various industries. In the flight process of UAV, UAV often changes the given path because of obstacles (including static nonliving body and moving living body). According to the properties of obstacles and the characteristics of UAV, standard Kalman filter is used for nonmaneuvering targets, and sigma point Kalman filter is used for maneuvering targets. In the aspect of obstacle avoidance, the minimum search method is used to get the initial population of local programming. Then, the improved genetic algorithm is run. Combined with the predicted obstacle features, the local planning path can be obtained. Finally, the local planning path and global planning path are combined to generate the planning path with new obstacles. At the end of the paper, the obstacle avoidance strategies of static and moving obstacles are simulated. The simulation results show that this method has fast convergence speed and good feasibility and can flexibly deal with the obstacle avoidance and local path planning of various new obstacles.


---

## Body

## 1. Introduction

In recent years, with the continuous development of UAV and computer technology, UAV technology is widely used in power, agriculture, film, and other industries. In high temperature, cold, dangerous, and other environments [1], UAV technology can help people work. With the continuous expansion of the application field of UAV, the performance requirements of UAV are higher and higher, especially for the key technologies of UAV, such as endurance, shooting, and obstacle avoidance [1, 2].The obstacle avoidance technology of UAV is related to the safety of UAV, so it is a hot issue in the research of UAV.At present, many research studies on UAV obstacle avoidance are to obtain the two-dimensional position information of UAV height through UAV airborne radar and construct an artificial potential field model to guide UAV to quickly track targets and avoid air obstacles. Similar to this obstacle avoidance method, it is more suitable for obstacle avoidance of stationary objects and does not predict dynamic objects [1, 2]. In the subsequent path planning, the optimal path cannot be obtained. In this study, the obstacles are classified, the standard Kalman filter prediction algorithm is used for nonmaneuvering targets, and the sigma point Kalman filter method is used for maneuvering targets. Better results can be obtained in path planning.There are two common methods for obstacle avoidance planning of UAV [3]; one is to adjust the UAV flight speed to avoid obstacles according to the relative position and speed between UAV and target; the other is to change the UAV heading to avoid obstacles. Considering that the outdoor environment is mostly static obstacles, it is difficult to meet the obstacle avoidance requirements only by adjusting the UAV speed, so the second method is considered.In this paper, according to the characteristics of obstacles, obstacles are divided into nonmaneuvering targets and maneuvering targets. The standard Kalman filter is used to predict the maneuvering target, and the sigma point Kalman filter is used to predict the maneuvering target. Through the study of these two parts, we can effectively predict the characteristics and location of obstacles. Then, for the predicted obstacles, the minimum search method is used to obtain the initial population of local programming and run the improved genetic algorithm. Combined with the predicted obstacle characteristics, the local planning path can be obtained. Finally, the planning path with new obstacles is generated by combining the local planning path and the global planning path. The simulation results show that this method has fast convergence speed and good feasibility and can flexibly deal with obstacle avoidance and local path planning of various new obstacles.


## 2. Decision of Obstacle Avoidance Algorithm

The sensors used for real-time obstacle avoidance in UAV are mainly lidar, and many scholars have done a lot of research on the use of lidar [1, 4]. However, the main starting point of these research results is to avoid obstacles, which is not fully based on the attributes of obstacles and the characteristics of UAV, so as to organically combine safety obstacle avoidance and path planning. In this paper, based on the information obtained by UAV, combined with the characteristics of obstacles, UAV, and preplanned global path, local planning path is generated near the global planning path on the basis of safe obstacle avoidance, so as to achieve the unity of global and local path planning [5].The obstacle avoidance decision algorithm is shown in Figure1. Target recognition is based on the information obtained by lidar. If obstacles are found beyond the safe distance, obstacle avoidance will not be initiated. On the contrary, obstacle avoidance is based on the results of target recognition.Figure 1
Structure diagram of UAV obstacle avoidance planning.


## 3. Prediction of Nonmaneuvering Target and Maneuvering Target

### 3.1. Standard Kalman Filter Algorithm

The filtering process of the standard Kalman filter is calculated in a recursive way of “prediction-revision.” First, the prediction value is calculated, and then, the observed value is modified according to the new information and Kalman gain (weighting term). The predicted value can be obtained from the filtered value, and the filtered value can be obtained from the predicted value. The interaction between the filtering and the prediction does not require any observation data to be stored, and it can be processed in real time. The system structure block diagram is shown in Figure2.Figure 2
Standard Kalman filter system block diagram.Assume that the state equation and measurement equation of the system are, respectively,(1)Xk=Ak/k−1Xk−1+BkWk,Zk=CkXk+Vk,where Xk is the n-dimensional state vector at time k. That is to say, the estimated vector Ak/k−1 is n∗n-dimensional state transition matrix. Xk−1 is the n-dimensional state vector at time k-1. Bk is the dynamic noise matrix n∗n. Wk is n-dimensional dynamic noise. Zk is the observation vector at time K. Ck is k-time measurement matrix n∗n. The m-dimensional observation noise at time Vk is k. And, dynamic noise W and observation noise K are uncorrelated zero mean white noise sequences. That is to say, for all k and j, EWk=0,EVk=0. Then,(2)CovWk,Wj=EWkWjT=Qkδkj,(3)CovVk,Vj=EVkVjT=Rkδkj,(4)CovWk,Vj=EWkVjT=0,where δkj is Kronecker symbolic function,(5)δkj=0,k≠j,1,k=j,and Qk is the variance of dynamic noise. In the Kalman filter, it is required to be a known nonnegative fixed array. Rk is the observation noise variance matrix. In the Kalman filter, it is required to be a known nonnegative fixed array. That is to say, there is noise in each measurement component.Using the minimum variance to deduce the Kalman filter, we can obtain the following.Forecast estimateX¯k/k−1 is(6)X¯k/k−1=Ak/k−1X¯k−1.Filter estimationX¯k is(7)X¯k=X¯k/k−1+KkZk−CkX¯k/k−1,where Kk is the best gain matrix.Measured predictionZk/k−1 is(8)Zk/k−1=CkX¯k/k−1.New information predictionεk is(9)εk=Z¯k−Zk/k−1.Prediction error covariance matrixPk/k−1 is(10)Pk/k−1=Ak/k−1Pk−1Ak/k−1Τ+Bk−1Qk−1Bk−1Τ.Filtering error covariance matrixPk is(11)Pk=I−KkCkPk/k−1.Optimal gain matrixKk is(12)Kk=Pk/k−1CkΤCkPk/k−1CkΤ+Rk−1.


### 3.2. Prediction of Uniform Linear Motion with Standard Kalman

In this paper, the target mathematical modelx=ut+x0y=vt+y0 of uniform linear motion is predicted, where u and v are the velocity component of the target in x and y coordinate axes, which are constant parameters. x0 and y0 are the displacement of the target at the initial time, and they are also constant parameters:(13)Xk=AXk−1+BWk,where the state variable Xk is(14)Xk=xkx^yky^.The state transition matrixA and dynamic noise matrix B are(15)A=I2TI202I2,B=T22I2TI2.Sampling timeT = 1 s. Wk is the mean value, its value is zero, and the dynamic variance is the dynamic noise of Q. The value of dynamic variance Q is as follows:(16)Q=5005.The observation equation of the system is as follows:(17)Zk=CkXk+Vk,where C is the observation matrix,(18)C=1010,and Vk is the mean value, its value is 0, and the dynamic variance is the dynamic noise of R. The value of dynamic variance R is as follows:(19)R=5005.The initial stateX0 and the initial covariance matrix P0 are as follows:(20)X0=040020Τ,P0=5000050000500005.The prediction results of nonmotorized obstacles using the standard Kalman are shown in Figures3 and 4. The simulation results show that the prediction effect is satisfactory.Figure 3
Actual and predicted positions.Figure 4
Prediction error.The standard Kalman filter can achieve good results in predicting the state of nonmaneuvering target. For maneuvering target, its motion is unknown, so the standard Kalman filter cannot accurately describe its motion state. In this paper, the sigma point Kalman filter is used to realize the state estimation of the maneuvering target. Its core idea is unscented transformation, which propagates a finite number of sigma points by using nonlinear state and observation equations. Then, weighted sum is used to get the mean and variance of the state probability distribution.


### 3.3. Sigma Point Kalman Filtering Algorithm

UKF, the sigma point Kalman filter algorithm, is based on UT transformation and adopts the Kalman filter framework. The specific sampling form is deterministic sampling. The number of discrete points (called sigma points) sampled by UKF is small, and the specific number depends on the selected sampling strategy. The most commonly used is 2n + 1 sigma point symmetric sampling.According to the state estimatesx^k−1 and Pk−1 at time k−1, the realization process of obtaining the state estimates x^k−1 and Pk−1 at time k is given.First, according tox^k−1 and Pk−1, the sigma point χk−1i, i=1,…,2n, is constructed according to the sigma point sampling formulas (5)–(31):(21)χi=x¯,i=0,x¯+n+λPi,i=1,…,n,x¯+n+λPii=n+1,…,2n.Then, predict the sigma point and mean:(22)χk|k−1i=fkχk−1i,(23)x^=∑i=02nWimχk|k−1i,(24)Pk|k−1=∑i=02nWicχk|k−1i−x^k|k−1χk|k−1i−x^k|k−1Τ+Qw,k,Correction (measurement update):(25)Yk|k−1i=gχk−1i,(26)y^=∑i=02nWimYk|k−1i,(27)Py,k=∑i=02nWicYk|k−1i−y^k|k−1Yk|k−1i−y^k|k−1Τ+Rv,k,(28)Pxy,k=∑i=02nWicχk|k−1i−x^k|k−1Yk|k−1i−y^k|k−1Τ,(29)Kk=Pxy,kPy,k−1,(30)x^k=x^k|k−1+Kkyk−y^k|k−1,(31)Pk=Pk|k−1−KkPy,kKkT.


### 3.4. Maneuvering Target Prediction Simulation

In order to verify the prediction of the movement of obstacles with mobility by the sigma point Kalman filter method, this paper constructs the state equation and observation equation of obstacle movement:(32)x=0.2x+0.01x2+8cos1.2∗k+1+sqrt10∗randn,y=x2+0.1randn.Take the initial state ofx as x = 1, the estimated value of the initial state is x = 0.5, the process state covariance Qis Q = 10, the measurement noise covariance R is R = 0.01, and the initial estimated variance P is P = 1000. The prediction of maneuverable obstacle motion using the sigma point Kalman filter is shown in Figures 5 and 6. From the simulation results, it can be seen that the method has achieved good prediction effect on the mobility movement.Figure 5
The true value and UKF estimated value.Figure 6
UKF estimation error.


## 3.1. Standard Kalman Filter Algorithm

The filtering process of the standard Kalman filter is calculated in a recursive way of “prediction-revision.” First, the prediction value is calculated, and then, the observed value is modified according to the new information and Kalman gain (weighting term). The predicted value can be obtained from the filtered value, and the filtered value can be obtained from the predicted value. The interaction between the filtering and the prediction does not require any observation data to be stored, and it can be processed in real time. The system structure block diagram is shown in Figure2.Figure 2
Standard Kalman filter system block diagram.Assume that the state equation and measurement equation of the system are, respectively,(1)Xk=Ak/k−1Xk−1+BkWk,Zk=CkXk+Vk,where Xk is the n-dimensional state vector at time k. That is to say, the estimated vector Ak/k−1 is n∗n-dimensional state transition matrix. Xk−1 is the n-dimensional state vector at time k-1. Bk is the dynamic noise matrix n∗n. Wk is n-dimensional dynamic noise. Zk is the observation vector at time K. Ck is k-time measurement matrix n∗n. The m-dimensional observation noise at time Vk is k. And, dynamic noise W and observation noise K are uncorrelated zero mean white noise sequences. That is to say, for all k and j, EWk=0,EVk=0. Then,(2)CovWk,Wj=EWkWjT=Qkδkj,(3)CovVk,Vj=EVkVjT=Rkδkj,(4)CovWk,Vj=EWkVjT=0,where δkj is Kronecker symbolic function,(5)δkj=0,k≠j,1,k=j,and Qk is the variance of dynamic noise. In the Kalman filter, it is required to be a known nonnegative fixed array. Rk is the observation noise variance matrix. In the Kalman filter, it is required to be a known nonnegative fixed array. That is to say, there is noise in each measurement component.Using the minimum variance to deduce the Kalman filter, we can obtain the following.Forecast estimateX¯k/k−1 is(6)X¯k/k−1=Ak/k−1X¯k−1.Filter estimationX¯k is(7)X¯k=X¯k/k−1+KkZk−CkX¯k/k−1,where Kk is the best gain matrix.Measured predictionZk/k−1 is(8)Zk/k−1=CkX¯k/k−1.New information predictionεk is(9)εk=Z¯k−Zk/k−1.Prediction error covariance matrixPk/k−1 is(10)Pk/k−1=Ak/k−1Pk−1Ak/k−1Τ+Bk−1Qk−1Bk−1Τ.Filtering error covariance matrixPk is(11)Pk=I−KkCkPk/k−1.Optimal gain matrixKk is(12)Kk=Pk/k−1CkΤCkPk/k−1CkΤ+Rk−1.


## 3.2. Prediction of Uniform Linear Motion with Standard Kalman

In this paper, the target mathematical modelx=ut+x0y=vt+y0 of uniform linear motion is predicted, where u and v are the velocity component of the target in x and y coordinate axes, which are constant parameters. x0 and y0 are the displacement of the target at the initial time, and they are also constant parameters:(13)Xk=AXk−1+BWk,where the state variable Xk is(14)Xk=xkx^yky^.The state transition matrixA and dynamic noise matrix B are(15)A=I2TI202I2,B=T22I2TI2.Sampling timeT = 1 s. Wk is the mean value, its value is zero, and the dynamic variance is the dynamic noise of Q. The value of dynamic variance Q is as follows:(16)Q=5005.The observation equation of the system is as follows:(17)Zk=CkXk+Vk,where C is the observation matrix,(18)C=1010,and Vk is the mean value, its value is 0, and the dynamic variance is the dynamic noise of R. The value of dynamic variance R is as follows:(19)R=5005.The initial stateX0 and the initial covariance matrix P0 are as follows:(20)X0=040020Τ,P0=5000050000500005.The prediction results of nonmotorized obstacles using the standard Kalman are shown in Figures3 and 4. The simulation results show that the prediction effect is satisfactory.Figure 3
Actual and predicted positions.Figure 4
Prediction error.The standard Kalman filter can achieve good results in predicting the state of nonmaneuvering target. For maneuvering target, its motion is unknown, so the standard Kalman filter cannot accurately describe its motion state. In this paper, the sigma point Kalman filter is used to realize the state estimation of the maneuvering target. Its core idea is unscented transformation, which propagates a finite number of sigma points by using nonlinear state and observation equations. Then, weighted sum is used to get the mean and variance of the state probability distribution.


## 3.3. Sigma Point Kalman Filtering Algorithm

UKF, the sigma point Kalman filter algorithm, is based on UT transformation and adopts the Kalman filter framework. The specific sampling form is deterministic sampling. The number of discrete points (called sigma points) sampled by UKF is small, and the specific number depends on the selected sampling strategy. The most commonly used is 2n + 1 sigma point symmetric sampling.According to the state estimatesx^k−1 and Pk−1 at time k−1, the realization process of obtaining the state estimates x^k−1 and Pk−1 at time k is given.First, according tox^k−1 and Pk−1, the sigma point χk−1i, i=1,…,2n, is constructed according to the sigma point sampling formulas (5)–(31):(21)χi=x¯,i=0,x¯+n+λPi,i=1,…,n,x¯+n+λPii=n+1,…,2n.Then, predict the sigma point and mean:(22)χk|k−1i=fkχk−1i,(23)x^=∑i=02nWimχk|k−1i,(24)Pk|k−1=∑i=02nWicχk|k−1i−x^k|k−1χk|k−1i−x^k|k−1Τ+Qw,k,Correction (measurement update):(25)Yk|k−1i=gχk−1i,(26)y^=∑i=02nWimYk|k−1i,(27)Py,k=∑i=02nWicYk|k−1i−y^k|k−1Yk|k−1i−y^k|k−1Τ+Rv,k,(28)Pxy,k=∑i=02nWicχk|k−1i−x^k|k−1Yk|k−1i−y^k|k−1Τ,(29)Kk=Pxy,kPy,k−1,(30)x^k=x^k|k−1+Kkyk−y^k|k−1,(31)Pk=Pk|k−1−KkPy,kKkT.


## 3.4. Maneuvering Target Prediction Simulation

In order to verify the prediction of the movement of obstacles with mobility by the sigma point Kalman filter method, this paper constructs the state equation and observation equation of obstacle movement:(32)x=0.2x+0.01x2+8cos1.2∗k+1+sqrt10∗randn,y=x2+0.1randn.Take the initial state ofx as x = 1, the estimated value of the initial state is x = 0.5, the process state covariance Qis Q = 10, the measurement noise covariance R is R = 0.01, and the initial estimated variance P is P = 1000. The prediction of maneuverable obstacle motion using the sigma point Kalman filter is shown in Figures 5 and 6. From the simulation results, it can be seen that the method has achieved good prediction effect on the mobility movement.Figure 5
The true value and UKF estimated value.Figure 6
UKF estimation error.


## 4. Obstacle Avoidance Operator in Local Planning Based on the Minimal Search Method

For local path planning, fast obstacle avoidance is the primary issue under the condition of safety assurance, so it is necessary to consider how to improve the planning speed. Perform local planning between the abovementioned starting point and ending point. First of all, it is necessary to find the initial population that can be used for fast local planning, so this paper designs an obstacle avoidance operator.Obstacle avoidance operator: by performing obstacle avoidance operations on the starting point and ending point of the path through the obstacle, a new local initial path can be obtained. Then, the local path is planned through genetic algorithm and then returned to the originally planned path. If the new obstacle is a triangle ABC, extrapolate the intersection of the global planning path and the obstacle to a safe distance and get the starting and ending points of the local path asP and Q. As shown in Figure 7. The ABC three-point coordinates can be substituted into PQ line equation, and the point with one end (such as point a) can be determined by symbols, and R point is generated near point a, where r-point coordinate is one of (xa + Δx, ya + Δy), (xa − Δx, ya + Δy), (xa + Δx, ya − Δy), and (xa − Δx, ya − Δy). If neither PR line nor QR line segment intersects with triangle ABC, the r-point coordinate is accepted as a point in the path. Such a problem can be reduced to the solution of the minimum value. The most common algorithm is the steepest descent method. The steepest descent method searches according to the inverse direction of the gradient of the multivariate function. It still needs to find the partial derivative and select a step size. The convergence rate of this method is linear and becomes very slow after the first few steps.Figure 7
Diagram of the obstacle avoidance operator.In this paper, a minimum search method is proposed to find the minimum extremum ofR point. The minimum search method is a simplified model, which can solve the problem of n-dimensional space in practice. In order to illustrate the problem conveniently, take two-dimensional space as an example.In this paper, the symmetry axis of conic is used to estimate the minimum extremum value ofR point. First of all, the problem can be attributed to a function of one variable fx. We consider the minimal value problem of fxa−Δx, fxa, and fxa+Δx on a diagonal. Since these three points can determine a conic curve, the minimum value R point can be estimated by using the known fxa−Δx, fxa, and fxa+Δx.Suppose the quadratic function ishx=ax2+bx+c, and it coincides with fx at three known points; according to the undetermined coefficient method, the equations are obtained:(33)fxa+Δx=axa−Δx2+bxa−Δx+c,fxa=axa2+bxa+c,fxa+Δx=axa+Δx2+bxa+Δx+c.For the symmetric axis ofhx at −b/2a, the equation system can be solved:(34)−b2a=xa+fxa−Δx−fxa+Δx2fxa−Δx−2fxa+fxa+ΔxΔx.Because the axis of symmetry ofhx is near xa and Δx is small enough, when fx0−Δx−2fx0+fx0+Δx>0, hx is a concave function and the minimum value is taken at −b/2a.From equation (34), the estimation point R of the ultimate minimum value can be obtained. The search process of R point is shown in Figure 7.TheP and Q points are reserved as the starting and ending points, and the initial population is generated near the PRQ so that the local optimal path can be quickly searched.


## 5. Local Planning Path Simulation

As mentioned above, the global planning path is shown in Figure8(a). In the simulation, the obstacles are represented by multilateral type and segmented by triangles. The starting point of the path is (0, 0), and the target point of the path is (20, 0). If new obstacles appear on the planned path, the type of new obstacles needs to be determined through target identification. Here, we mainly discuss the case that the new obstacle is an inanimate body.Figure 8
Path planning combining local path planning with global path planning. (a) Global path planning. (b) Local path planning based on global planning.
(a)(b)Firstly, the obstacle avoidance operator subroutine is run to obtain the initial population of local planning. Then, run the improved genetic algorithm to get the local planning path. Finally, the local planning path is combined with the global planning path to generate the planning path with new obstacles. The simulation is programmed in Matlab platform, and genetic operation is realized by genetic algorithm toolbox function of Sheffield University. The initial cross rate was 0.9, the initial variation rate was 0.2, and the genetic algebra was 1000. The simulated annealing process is set to 100 times and the simulated annealing temperature is set to 1000 by using binary number coding.


### 5.1. The New Obstacles Are Inanimate Objects at Rest

If the above targets are identified, the new obstacles are inanimate objects at rest (mountains, buildings, etc.), as shown in Figure8(b). The obstacle coordinates are (11.3, −3.1), (14.2, −2), and (12.1, −0.7). The wind speed is vwindy=0.1m/s.Figure8 shows the combination of local path planning and global path planning on the basis of global path planning. As shown in Figure 8(a), if new obstacles are found on the planned path, local planning is carried out by the improved genetic algorithm mentioned above. Combining with the original optimal path, the path planning results of the combination of local path planning and global path planning are obtained. Most of the paths maintain the global path planning results. The new obstacle part is local path planning, as shown in Figure 8(b). The path points include (0, 0), (4, −1.8), (10.2, −1.4), (12.2, −0.7), (14.2, −1.2) (16.1, −1), and (20, 0). As can be seen from Figure 8(b), the UAV bypasses the obstacle in the downstream direction. Figure 9 shows the error curve of local programming. The genetic algebra converges at about 200. The simulation results show that the convergence speed of local programming is fast.Figure 9
Local path planning error curve.If there are large static inanimate obstacles on the original global planning path, as shown in Figure10(a), the coordinates of the new obstacles are (4.8, −0.7), (7.1, −3.2), and (10.2, −2), and the wind speed is vwy=0.1m/s. The simulation results are shown in Figure 10(a). The combination path of global and local planning is (0, 0), (4, −1.8) (7.2, −3.4), (16.1, −1), and (20, 0).Figure 10
Path planning combining local path planning with global path planning for large obstacles. (a) Local path planning based on global planning; (b) local path planning error curve.
(a)(b)From the simulation results, the local path part is not planned along the wind speed direction because if it is planned along the wind speed direction, the UAV will enter the obstacle dense area, so it is difficult to realize the local path planning. Figure10(b) shows the error curve of local programming. The genetic algebra converges about 600 times. The simulation results show that the convergence speed of local programming is fast.


### 5.2. The Obstacle Is a Moving Nonliving Body (Aircraft)

On the path of global path planning shown in Figure7(a), after target recognition, new obstacles of moving inanimate body appear.If the new obstacle moves at a constant speed, as shown by the dotted line in Figure11(a), the new obstacle is represented as a triangle. Among the new obstacles, vx=−0.2m/s and vy=0. The wind speed is vwindy=0.1m/s. The motion of the obstacle can be estimated by the Kalman filter.Figure 11
Path planning of uniform moving obstacles with local and global combination. (a) Local path planning based on global planning; (b) local path planning error curve.
(a)(b)In Figure11(a), due to the low speed of the obstacle and the small cross-sectional area of the obstacle, the local planning path completes the local motion planning along the short direction of the obstacle detour path and returns to the global planning path after the local path planning.Figure11(b) shows the error curve of local programming, and the genetic algebra converges around 150. The simulation results show that the local programming converges fast.If the new obstacles are uniformly accelerated, as shown by the dotted line in Figure12(a), the new obstacles are represented as triangles. Among new obstacles, vx=0, vy=0.2m/s, and ay0=0.2m/s2. The wind speed is vwindy=0.1m/s. The motion of the obstacle can be estimated by the Kalman filter.Figure 12
Path planning of local and global combination for accelerating moving obstacles. (a) Local path planning based on global planning; (b) local path planning error curve.
(a)(b)It can be seen from the simulation results in Figure12(a) (the planned path is represented by a thick line) that the local planned path is divided into two parts: bypassing obstacles and returning. Due to the acceleration of the new obstacles, the part around the obstacles and the return part are both curves. The part around the obstacles starts the obstacle avoidance planning in advance to ensure the safety. The return part quickly returns to the global planning path, achieving the unity of local planning and global planning. Figure 12(b) shows the error curve of local planning. The genetic algebra converges around 400. The simulation results show that the convergence speed of local planning is fast.


## 5.1. The New Obstacles Are Inanimate Objects at Rest

If the above targets are identified, the new obstacles are inanimate objects at rest (mountains, buildings, etc.), as shown in Figure8(b). The obstacle coordinates are (11.3, −3.1), (14.2, −2), and (12.1, −0.7). The wind speed is vwindy=0.1m/s.Figure8 shows the combination of local path planning and global path planning on the basis of global path planning. As shown in Figure 8(a), if new obstacles are found on the planned path, local planning is carried out by the improved genetic algorithm mentioned above. Combining with the original optimal path, the path planning results of the combination of local path planning and global path planning are obtained. Most of the paths maintain the global path planning results. The new obstacle part is local path planning, as shown in Figure 8(b). The path points include (0, 0), (4, −1.8), (10.2, −1.4), (12.2, −0.7), (14.2, −1.2) (16.1, −1), and (20, 0). As can be seen from Figure 8(b), the UAV bypasses the obstacle in the downstream direction. Figure 9 shows the error curve of local programming. The genetic algebra converges at about 200. The simulation results show that the convergence speed of local programming is fast.Figure 9
Local path planning error curve.If there are large static inanimate obstacles on the original global planning path, as shown in Figure10(a), the coordinates of the new obstacles are (4.8, −0.7), (7.1, −3.2), and (10.2, −2), and the wind speed is vwy=0.1m/s. The simulation results are shown in Figure 10(a). The combination path of global and local planning is (0, 0), (4, −1.8) (7.2, −3.4), (16.1, −1), and (20, 0).Figure 10
Path planning combining local path planning with global path planning for large obstacles. (a) Local path planning based on global planning; (b) local path planning error curve.
(a)(b)From the simulation results, the local path part is not planned along the wind speed direction because if it is planned along the wind speed direction, the UAV will enter the obstacle dense area, so it is difficult to realize the local path planning. Figure10(b) shows the error curve of local programming. The genetic algebra converges about 600 times. The simulation results show that the convergence speed of local programming is fast.


## 5.2. The Obstacle Is a Moving Nonliving Body (Aircraft)

On the path of global path planning shown in Figure7(a), after target recognition, new obstacles of moving inanimate body appear.If the new obstacle moves at a constant speed, as shown by the dotted line in Figure11(a), the new obstacle is represented as a triangle. Among the new obstacles, vx=−0.2m/s and vy=0. The wind speed is vwindy=0.1m/s. The motion of the obstacle can be estimated by the Kalman filter.Figure 11
Path planning of uniform moving obstacles with local and global combination. (a) Local path planning based on global planning; (b) local path planning error curve.
(a)(b)In Figure11(a), due to the low speed of the obstacle and the small cross-sectional area of the obstacle, the local planning path completes the local motion planning along the short direction of the obstacle detour path and returns to the global planning path after the local path planning.Figure11(b) shows the error curve of local programming, and the genetic algebra converges around 150. The simulation results show that the local programming converges fast.If the new obstacles are uniformly accelerated, as shown by the dotted line in Figure12(a), the new obstacles are represented as triangles. Among new obstacles, vx=0, vy=0.2m/s, and ay0=0.2m/s2. The wind speed is vwindy=0.1m/s. The motion of the obstacle can be estimated by the Kalman filter.Figure 12
Path planning of local and global combination for accelerating moving obstacles. (a) Local path planning based on global planning; (b) local path planning error curve.
(a)(b)It can be seen from the simulation results in Figure12(a) (the planned path is represented by a thick line) that the local planned path is divided into two parts: bypassing obstacles and returning. Due to the acceleration of the new obstacles, the part around the obstacles and the return part are both curves. The part around the obstacles starts the obstacle avoidance planning in advance to ensure the safety. The return part quickly returns to the global planning path, achieving the unity of local planning and global planning. Figure 12(b) shows the error curve of local planning. The genetic algebra converges around 400. The simulation results show that the convergence speed of local planning is fast.


## 6. Conclusions

When UAV flies on the planned path, new obstacles appear on the planned path. In different cases, the local path planning method will be determined according to the UAV obstacle avoidance decision. On the basis of obstacle target recognition, such as fully considering the type characteristics of obstacles, the influence of wind speed, and the influence of yaw angle change rate, the Kalman filter, prediction, and its improved algorithm are used to estimate the target motion parameters [6–8]. The local approximate obstacle avoidance path is planned by the obstacle avoidance operator of minimum search method, and the local initial population is generated. On this basis, the improved genetic algorithm is used to plan the local obstacle avoidance path. The starting point and ending point of local planning are all on the global planning path, which achieves the unity of global path planning and local path planning from the method and implementation. The simulation results show that the method has fast convergence speed and good feasibility and can flexibly deal with the obstacle avoidance and local path planning of various new obstacles.



---

*Source: 3798990-2021-09-10.xml*