# UAV Path Planning in Dynamical Environment: A Novel ICACO-IDWA Algorithm

Authors: Jiayang Yu; Jiansheng Guo; Xiaofeng Zhang; Chuhan Zhou; Tao Xie
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

In this paper, a novel UAV path planning algorithm based on improved cellular ant colony algorithm and dynamic window algorithm (ICACO-IDWA) is proposed to solve the problem of dynamically changing threat during actual flight. The main innovations of this paper are as follows. (a) The hexagon grid method is proposed to model the UAV flight space, which solves the problem of inconsistent simulation time step. (b) A novel ICACO-IDWA algorithm is proposed. In the first stage, the optimal path is obtained by the improved cellular ant colony algorithm (ICACO). In the second stage, the improved dynamic window algorithm (IDWA) is used to optimize the optimal path considering dynamic threat. Through the algorithm, the UAV path planning with dynamic threat change is realized. Finally, simulation results verify the effectiveness of the proposed model and algorithm.


---

## Body

## 1. Introduction

Recently, unmanned aerial vehicle (UAV) has been widely used in the military field due to its characteristics of high speed, all-weather, non-contact, and zero casualties, which has had a revolutionary impact on the air combat model [1–4]. Relative scholars have carried out extensive studies on the UAV real-time path planning problem in the decade [5–8]. How to avoid the dynamic potential threats in the complex environment and plan a safe shortest flight path have become a hot point in the UAV application field.Cellular ant colony algorithm (CACO) has been widely used in path planning problems because of its short-planned path and good global optimization performance [9, 10]. Wang et al. [9] optimized the heuristic function and pheromone update mode of CACO algorithm, increasing the solution space and improving the global search ability of the algorithm. Wen et al. [11] combined CACO algorithm with multi-objective optimization theory to solve the multi-objective path planning problem with multiple constraints. Ye et al. [12] constructed comprehensive heuristic information to guide CACO algorithm search based on node potential field direction and distance between node and target, which effectively improved algorithm’s convergence performance and solution accuracy. Akbarimajd and Hassanzadeh [13] proposed a new CACO algorithm with hierarchical architecture, which realized path planning in an environment with convex and concave obstacles. The above studies have achieved good results in path planning problem. However, in the dynamic and complex environment where threats change in real time, CACO algorithm cannot avoid obstacles and threats in real time, leading to the inability to ensure the safety of the planned global optimal path. In addition, although CACO algorithm has good convergence and global optimization ability, the search efficiency of the algorithm is low and needs to be further improved.Dynamic window algorithm (DWA) has the advantage of simple model, smooth planning path, and good local obstacle avoidance ability [14]. Han et al. [15] dynamically selected parent nodes as search targets of DWA algorithm, which effectively avoided the algorithm falling into local optimum. Lin and Fu [16] used DWA algorithm to carry out path planning for three environments with different obstacle types and verified the effectiveness of DWA algorithm by experiments. Hossain et al. [17] were able to find a robust and safe path. It was not affected by global convergence and local minimum by integrating the following gap method into the dynamic programming method. Kobayashi and Motoi [18] proposed a local path planning method named VMDWA algorithm, in which variable speed values were used for path prediction to find the best path. The above studies have better solved the real-time obstacle avoidance problem of the path, and the obtained path is smooth and more consistent with the motion characteristics of UAV. However, because DWA algorithm only considers the environment information in the window area and does not consider the global information in the search process, the global optimality of the path cannot be guaranteed, and the algorithm is easy to fall into local optimality.In addition, the following disadvantages still exist in real-time path planning problem. First, most of the path planning models only take path length as the objective function. They do not consider the threat to UAV caused by radar, electromagnetic interference, and other factors, which affects the authenticity of the model [19–22]. Furthermore, rectangle grid is widely used to divide the UAV flight space. It owns the problem of inconsistent simulation time step [23–26].In view of the above problems, this paper proposes a real-time path planning method. It gives consideration to both the global optimal path and local dynamic threat avoidance and designs a real-time path planning algorithm named ICACO-IDWA that integrates improved cellular ant colony algorithm and dynamic window algorithm. The main contributions of this paper are as follows:(1)
Taking path length and threat degree of UAV as objective function, the path planning model is improved to make it closer to battlefield reality.(2)
The hexagon grid is used to model the UAV flight space, which effectively solves the problem of inconsistent simulation time step.(3)
A novel real-time path planning algorithm named ICACO-IDWA is designed. In the first stage, based on traditional CACO algorithm, the potential field concept is introduced to modify the heuristic function, and the differential search strategy is adopted to guide the ant colony to search the target quickly. An adaptive pheromone updating method is designed to select the high-quality route, and the efficiency of the algorithm is effectively improved to quickly plan the global optimal path. In the second stage, dynamic threats are considered. The improved DWA algorithm named IDWA is used to carry out local planning between adjacent nodes of the optimal path, so that the UAV can bypass threats and return to the global optimal path when it encounters threats in the global path. It not only ensures the global optimality of the local real-time planning path but also realizes threat avoidance. In addition, the smoothness of the obtained path is ensured, so that it can better meet the UAV flight characteristics.The organizational structure of this paper is as follows. Section2 establishes the mathematical model of UAV path planning problem. ICACO algorithm for global path planning and IDWA algorithm for local real-time path planning are introduced in Sections 3 and 4, respectively, and the details of the fusion of the two algorithms are given in Section 5. In Section 6, a large number of simulation examples of UAV path planning are given. Section 7 summarizes the work of this paper.


## 2. UAV Path Planning Problem Modeling

The UAV path planning problem is to plan the flight path that meets the constraints of UAV maneuvering performance and minimizes the comprehensive cost on the premise of considering terrain threat, electromagnetic interference, and radar threat. In this paper, the UAV is seen as flying at a constant altitude. Besides, compared with maneuvering flight, UAV flying at constant speed consumes less power. Therefore, when there is no threat, UAV is flying with a constant speed. When UAV encounters threats such as terrain threat in the process of flight, it will adopt strategies such as turning to avoid threats, and the speed of UAV will change at this time. The kinematic model of UAV, the environment model of flight area, and the objective function of path planning are described as follows.


### 2.1. The Kinematic Model

In order to simplify the model, UAV is regarded as a particle, and its take-offs, landings, and altitude changes are ignored. The process of its task execution is regarded as a two-dimensional plane flight at a specific height. This model not only retains the dynamic characteristics of the system but also reduces the amount of input and state. The kinematic model of UAV is shown in Figure1.Figure 1
Kinematic model of UAV.In Figure1, vx and vy are the horizontal and vertical velocities of UAV; ω is the angular velocity of UAV; and θt is the heading angle of UAV. Assuming that UAV keeps a constant speed in time Δt, the trajectory of UAV from time t to time t+Δt can be approximated as a straight line. Therefore, the posture increment of UAV in time Δt is(1)Δx=vxΔtcosθt−vyΔtsinθt,Δy=vxΔtsinθt+vyΔtcosθt,Δt=ωΔt.Then, the posture at momentt+Δt is expressed as(2)xt+Δt=xt+vxΔtcosθt−vyΔtsinθt,yt+Δt=yt+vxΔtsinθt+vyΔtcosθt,θt+Δt=θt+ωΔt.


### 2.2. The Environment Model

In solving traditional path planning problems, rectangular grid map is generally used to model the flight space, and “Moore” neighborhood is used to describe the transition state of UAV, namely,M=C1,C2,⋯,C8, with Ci∈0,1. Ci=1 represents that the neighborhood cellular is selected. Black cellular is unreachable cellular, indicating the boundary, threat, or obstacle. White cellular is free cellular, indicating that UAV can pass normally, as shown in Figure 2(a).Figure 2
The grid diagram. (a) “Moore” neighborhood. (b) Rectangular grid map. (c) Hexagonal grid map.
(a)(b)(c)Rectangular grid map reduces the complexity of environment modeling, but there are some problems such as inconsistent time step in the transformation of adjacent cellular, which affect the authenticity of the model. Assuming that the grid length ish, when the next cellular is selected according to the “Moore” neighborhood, the cellular moves h, h, and 2h in transverse, longitudinal, and oblique directions, respectively, as shown in Figure 2(b). When the cellular moves at a constant speed v, the time of the cellular in a movement may be h/v or 2h/v, resulting in inconsistent time step and affecting the authenticity of the model. Therefore, a hexagonal grid map is proposed in this paper (see Figure 2(c)). When the grid length is h, the cellular moving distance is 3h and moving time is 3h/v, which effectively solves the problem of inconsistent time step.The hexagonal grid map is constructed as follows. The cartesian coordinate system is established with the lower left corner of the map as the origin, the center of the grid tangent circle is taken as the center point, and the corresponding relation between the coordinatex,y of the center point and the grid number is(3)x=2.5h+3hj−1,modi,2=0,h+3hj−1,modi,2=1,y=0.53h×i,where i and j are the row and column numbers of the grid, respectively.Before solving the UAV path planning problem, it is necessary to determine the performance index of the optimization problem. In this paper, the penalty function method is adopted to transform the constraint equation into the objective cost function, and the result is as follows:(4)F=k1f+k2C,where C is the UAV path length and f is the threat cost function, including radar threat and electromagnetic interference threat, and so on. Threat cost ε in per unit flight path obeys uncertain distribution Φα. k1 and k2 are the corresponding penalty coefficients, respectively.Obviously, the optimization objective in formula (4) includes uncertain variables. Since the values of uncertain variables cannot be compared, it is necessary to transform them into a deterministic model. Expected value is an important statistical feature of uncertain variables. Liu[27] constructed an expected value model to solve uncertain programming problems by taking the expected value of the minimized objective function as the criterion. Therefore, the objective function can be converted to(5)EF=k1∫01Φ−1αdα+k2C,where Φ−1α is the inverse distribution function of threat cost ε.Theorem 1 (see [28]).
Letξ be an uncertain variable with the uncertain distribution ψα. If the expected value exists, then(6)Eξ=∫01ψ−1αdα,where ψ−1α is the inverse distribution function of uncertain variable ξ.


## 2.1. The Kinematic Model

In order to simplify the model, UAV is regarded as a particle, and its take-offs, landings, and altitude changes are ignored. The process of its task execution is regarded as a two-dimensional plane flight at a specific height. This model not only retains the dynamic characteristics of the system but also reduces the amount of input and state. The kinematic model of UAV is shown in Figure1.Figure 1
Kinematic model of UAV.In Figure1, vx and vy are the horizontal and vertical velocities of UAV; ω is the angular velocity of UAV; and θt is the heading angle of UAV. Assuming that UAV keeps a constant speed in time Δt, the trajectory of UAV from time t to time t+Δt can be approximated as a straight line. Therefore, the posture increment of UAV in time Δt is(1)Δx=vxΔtcosθt−vyΔtsinθt,Δy=vxΔtsinθt+vyΔtcosθt,Δt=ωΔt.Then, the posture at momentt+Δt is expressed as(2)xt+Δt=xt+vxΔtcosθt−vyΔtsinθt,yt+Δt=yt+vxΔtsinθt+vyΔtcosθt,θt+Δt=θt+ωΔt.


## 2.2. The Environment Model

In solving traditional path planning problems, rectangular grid map is generally used to model the flight space, and “Moore” neighborhood is used to describe the transition state of UAV, namely,M=C1,C2,⋯,C8, with Ci∈0,1. Ci=1 represents that the neighborhood cellular is selected. Black cellular is unreachable cellular, indicating the boundary, threat, or obstacle. White cellular is free cellular, indicating that UAV can pass normally, as shown in Figure 2(a).Figure 2
The grid diagram. (a) “Moore” neighborhood. (b) Rectangular grid map. (c) Hexagonal grid map.
(a)(b)(c)Rectangular grid map reduces the complexity of environment modeling, but there are some problems such as inconsistent time step in the transformation of adjacent cellular, which affect the authenticity of the model. Assuming that the grid length ish, when the next cellular is selected according to the “Moore” neighborhood, the cellular moves h, h, and 2h in transverse, longitudinal, and oblique directions, respectively, as shown in Figure 2(b). When the cellular moves at a constant speed v, the time of the cellular in a movement may be h/v or 2h/v, resulting in inconsistent time step and affecting the authenticity of the model. Therefore, a hexagonal grid map is proposed in this paper (see Figure 2(c)). When the grid length is h, the cellular moving distance is 3h and moving time is 3h/v, which effectively solves the problem of inconsistent time step.The hexagonal grid map is constructed as follows. The cartesian coordinate system is established with the lower left corner of the map as the origin, the center of the grid tangent circle is taken as the center point, and the corresponding relation between the coordinatex,y of the center point and the grid number is(3)x=2.5h+3hj−1,modi,2=0,h+3hj−1,modi,2=1,y=0.53h×i,where i and j are the row and column numbers of the grid, respectively.Before solving the UAV path planning problem, it is necessary to determine the performance index of the optimization problem. In this paper, the penalty function method is adopted to transform the constraint equation into the objective cost function, and the result is as follows:(4)F=k1f+k2C,where C is the UAV path length and f is the threat cost function, including radar threat and electromagnetic interference threat, and so on. Threat cost ε in per unit flight path obeys uncertain distribution Φα. k1 and k2 are the corresponding penalty coefficients, respectively.Obviously, the optimization objective in formula (4) includes uncertain variables. Since the values of uncertain variables cannot be compared, it is necessary to transform them into a deterministic model. Expected value is an important statistical feature of uncertain variables. Liu[27] constructed an expected value model to solve uncertain programming problems by taking the expected value of the minimized objective function as the criterion. Therefore, the objective function can be converted to(5)EF=k1∫01Φ−1αdα+k2C,where Φ−1α is the inverse distribution function of threat cost ε.Theorem 1 (see [28]).
Letξ be an uncertain variable with the uncertain distribution ψα. If the expected value exists, then(6)Eξ=∫01ψ−1αdα,where ψ−1α is the inverse distribution function of uncertain variable ξ.


## 3. Improved Cellular Ant Colony Algorithm (ICACO)

### 3.1. Traditional Cellular Ant Colony Algorithm

Traditional cellular ant colony algorithm (CACO) can be represented byTm×n,Im×n,Cw,C,CN,CR,O. Among them, Tm×n is the information matrix of grid map; Im×n is the pheromone matrix; Cw is the cellular space, where w is the cellular space dimension, with w=2; C=0,1 is the cellular state, which indicates whether the current cellular is occupied. C=1 indicates that the cellular is occupied; CN is the cellular neighborhood, generally using “Moore” type; CR is the cellular transfer rule, which is the constraint condition of ant colony movement. It includes the following three points. First, the selected cellular should not be a boundary, obstacle, and threat. Besides, the selected cellular should be conducive to finding the target cellular. At last, the transfer probability of cellular depends on the probability transfer formula pijkt:(7)pijkt=τijαtηijβt∑r∈Ckτirαtηirβt,j∈Ck,0,other,where Ck is a collection of “Moore” neighborhood cellular; τijt and ηijt=1/dij are pheromone value and heuristic value, respectively, between cellular i and j, which reflect cellular attraction to ants, in which dij is the Euclidean distance between cellular; α and β are pheromone elicitation factor and expectation elicitation factor, reflecting the importance of τijt and ηijt, respectively; and O is the pheromone update policy and adopts the global update policy.(8)τijt+1=1−ρτijt+Δτijt,Δτijt=Q/Lk,ifantgoesthroughthispath,0,other,where ρ is the pheromone volatile factor; Δτijt is the pheromone increment between cellular i and j in this iteration; Q is pheromone intensity coefficient; and Lk is the length of the ant’s path.Compared with traditional ant colony algorithm, CACO algorithm has some advantages. However, there are still the following problems. First, the algorithm’s efficiency needs to be improved. Second, the algorithm is easy to fall into local optimal and occur “deadlock” phenomenon (see Figure3), resulting in the inability to obtain feasible solutions. Therefore, heuristic function and pheromone update methods are optimized and differential search strategy is introduced to solve the above problems in this paper.Figure 3
Schematic diagram of “deadlock” phenomenon. (a) Traps are created by obstacles. (b) Traps are created by its own actions.
(a)(b)


### 3.2. Algorithm Improvement

#### 3.2.1. Heuristic Function Based on Potential Field

In traditional CACO algorithm, reciprocal of the distance between two cellular is used as heuristic function to reflect the expectation degree of neighborhood cellular selection. However, the equal distance between any two cellular in the hexagonal grid results in the failure of the original heuristic function, which cannot effectively guide the algorithm to optimize. The concept of potential field is introduced in this paper. The potential field value reflects the distance between neighborhood cellular and target cellular. The smaller the distance is, the larger the potential field value is, which meets the requirement of algorithm’s heuristic function. In addition, the drastic turning behaviour of UAV in flight will increase safety risks, so the turning cost is added into the heuristic function to reduce the number of turning times and turning angle of UAV. The formula of heuristic function is as follows:(9)costbend=φ×turn+ψ×θ,ηij=1djE3+costbend,where φ and ψ are the cost coefficients of turning times and turning angle, respectively, and djE represents the distance from neighborhood cellular to target cellular. By introducing potential field, CACO algorithm can effectively enhance the search efficiency, reduce the number of UAV sharp turns, and improve the global optimization ability and UAV flight safety.


#### 3.2.2. Differential Search Strategy

The center line is the connection between the starting point and the ending point. In general, the closer a path is to the center line, the more likely it is to be the shortest. Therefore, the weight of the path can be determined according to the distance between the current path and the center line. After introducing differential search strategy, the transition probability is(10)pijkt=τijαtηijβtϕijt∑r∈Ckτirαtηirβt,j∈Ck,0,other.In formula (10), ϕijt takes different values according to the distance d between the path and the center line at the moment t. It follows the normal distribution under N0,1. The efficiency of ant colony search can be improved by introducing differential search.


#### 3.2.3. Adaptive Pheromone Update Strategy

The method of pheromone update mainly includes global update method and real-time update method. Some studies show that the global update method has higher search efficiency, but it is easy to fall into local optimum. Also, the real-time update method is easy to find high-quality solutions, but the algorithm’s search efficiency is low [29]. Therefore, this paper integrates the two methods and proposes an adaptive update strategy, and the formula is as follows:(11)τijt+1=1−ρτijt+ω1Qfspbset+ω2Qfsgbset,where spbset is the current optimal path, sgbset is the global optimal path, ρ is the pheromone volatilization coefficient, and Q is the pheromone intensity coefficient. In the early search stage, ω1 is larger, making pheromone update more dependent on the current iterative optimal path. It is conducive to finding more high-quality solutions and avoiding the algorithm falling into local optimal. In the later search stage, ω2 is large, making pheromone update more dependent on the global optimal path. It is conducive to making the algorithm converge quickly.The ICACO algorithm is shown in Algorithm 1.Algorithm 1: ICACO algorithm.
(1)
Construct cellular space of hexagonal grid(2)
Parameter initialization(3)
fori = 1∼itermax (maximum iteration)(4)
if (the ant did not find the target cellular)(5)
The ant decides the next cellular according to transfer rule which introduces differential search strategy(6)
end(7)
Updating the pheromone value between cellular according to the adaptive strategy(8)
end


## 3.1. Traditional Cellular Ant Colony Algorithm

Traditional cellular ant colony algorithm (CACO) can be represented byTm×n,Im×n,Cw,C,CN,CR,O. Among them, Tm×n is the information matrix of grid map; Im×n is the pheromone matrix; Cw is the cellular space, where w is the cellular space dimension, with w=2; C=0,1 is the cellular state, which indicates whether the current cellular is occupied. C=1 indicates that the cellular is occupied; CN is the cellular neighborhood, generally using “Moore” type; CR is the cellular transfer rule, which is the constraint condition of ant colony movement. It includes the following three points. First, the selected cellular should not be a boundary, obstacle, and threat. Besides, the selected cellular should be conducive to finding the target cellular. At last, the transfer probability of cellular depends on the probability transfer formula pijkt:(7)pijkt=τijαtηijβt∑r∈Ckτirαtηirβt,j∈Ck,0,other,where Ck is a collection of “Moore” neighborhood cellular; τijt and ηijt=1/dij are pheromone value and heuristic value, respectively, between cellular i and j, which reflect cellular attraction to ants, in which dij is the Euclidean distance between cellular; α and β are pheromone elicitation factor and expectation elicitation factor, reflecting the importance of τijt and ηijt, respectively; and O is the pheromone update policy and adopts the global update policy.(8)τijt+1=1−ρτijt+Δτijt,Δτijt=Q/Lk,ifantgoesthroughthispath,0,other,where ρ is the pheromone volatile factor; Δτijt is the pheromone increment between cellular i and j in this iteration; Q is pheromone intensity coefficient; and Lk is the length of the ant’s path.Compared with traditional ant colony algorithm, CACO algorithm has some advantages. However, there are still the following problems. First, the algorithm’s efficiency needs to be improved. Second, the algorithm is easy to fall into local optimal and occur “deadlock” phenomenon (see Figure3), resulting in the inability to obtain feasible solutions. Therefore, heuristic function and pheromone update methods are optimized and differential search strategy is introduced to solve the above problems in this paper.Figure 3
Schematic diagram of “deadlock” phenomenon. (a) Traps are created by obstacles. (b) Traps are created by its own actions.
(a)(b)


## 3.2. Algorithm Improvement

### 3.2.1. Heuristic Function Based on Potential Field

In traditional CACO algorithm, reciprocal of the distance between two cellular is used as heuristic function to reflect the expectation degree of neighborhood cellular selection. However, the equal distance between any two cellular in the hexagonal grid results in the failure of the original heuristic function, which cannot effectively guide the algorithm to optimize. The concept of potential field is introduced in this paper. The potential field value reflects the distance between neighborhood cellular and target cellular. The smaller the distance is, the larger the potential field value is, which meets the requirement of algorithm’s heuristic function. In addition, the drastic turning behaviour of UAV in flight will increase safety risks, so the turning cost is added into the heuristic function to reduce the number of turning times and turning angle of UAV. The formula of heuristic function is as follows:(9)costbend=φ×turn+ψ×θ,ηij=1djE3+costbend,where φ and ψ are the cost coefficients of turning times and turning angle, respectively, and djE represents the distance from neighborhood cellular to target cellular. By introducing potential field, CACO algorithm can effectively enhance the search efficiency, reduce the number of UAV sharp turns, and improve the global optimization ability and UAV flight safety.


### 3.2.2. Differential Search Strategy

The center line is the connection between the starting point and the ending point. In general, the closer a path is to the center line, the more likely it is to be the shortest. Therefore, the weight of the path can be determined according to the distance between the current path and the center line. After introducing differential search strategy, the transition probability is(10)pijkt=τijαtηijβtϕijt∑r∈Ckτirαtηirβt,j∈Ck,0,other.In formula (10), ϕijt takes different values according to the distance d between the path and the center line at the moment t. It follows the normal distribution under N0,1. The efficiency of ant colony search can be improved by introducing differential search.


### 3.2.3. Adaptive Pheromone Update Strategy

The method of pheromone update mainly includes global update method and real-time update method. Some studies show that the global update method has higher search efficiency, but it is easy to fall into local optimum. Also, the real-time update method is easy to find high-quality solutions, but the algorithm’s search efficiency is low [29]. Therefore, this paper integrates the two methods and proposes an adaptive update strategy, and the formula is as follows:(11)τijt+1=1−ρτijt+ω1Qfspbset+ω2Qfsgbset,where spbset is the current optimal path, sgbset is the global optimal path, ρ is the pheromone volatilization coefficient, and Q is the pheromone intensity coefficient. In the early search stage, ω1 is larger, making pheromone update more dependent on the current iterative optimal path. It is conducive to finding more high-quality solutions and avoiding the algorithm falling into local optimal. In the later search stage, ω2 is large, making pheromone update more dependent on the global optimal path. It is conducive to making the algorithm converge quickly.The ICACO algorithm is shown in Algorithm 1.Algorithm 1: ICACO algorithm.
(1)
Construct cellular space of hexagonal grid(2)
Parameter initialization(3)
fori = 1∼itermax (maximum iteration)(4)
if (the ant did not find the target cellular)(5)
The ant decides the next cellular according to transfer rule which introduces differential search strategy(6)
end(7)
Updating the pheromone value between cellular according to the adaptive strategy(8)
end


## 3.2.1. Heuristic Function Based on Potential Field

In traditional CACO algorithm, reciprocal of the distance between two cellular is used as heuristic function to reflect the expectation degree of neighborhood cellular selection. However, the equal distance between any two cellular in the hexagonal grid results in the failure of the original heuristic function, which cannot effectively guide the algorithm to optimize. The concept of potential field is introduced in this paper. The potential field value reflects the distance between neighborhood cellular and target cellular. The smaller the distance is, the larger the potential field value is, which meets the requirement of algorithm’s heuristic function. In addition, the drastic turning behaviour of UAV in flight will increase safety risks, so the turning cost is added into the heuristic function to reduce the number of turning times and turning angle of UAV. The formula of heuristic function is as follows:(9)costbend=φ×turn+ψ×θ,ηij=1djE3+costbend,where φ and ψ are the cost coefficients of turning times and turning angle, respectively, and djE represents the distance from neighborhood cellular to target cellular. By introducing potential field, CACO algorithm can effectively enhance the search efficiency, reduce the number of UAV sharp turns, and improve the global optimization ability and UAV flight safety.


## 3.2.2. Differential Search Strategy

The center line is the connection between the starting point and the ending point. In general, the closer a path is to the center line, the more likely it is to be the shortest. Therefore, the weight of the path can be determined according to the distance between the current path and the center line. After introducing differential search strategy, the transition probability is(10)pijkt=τijαtηijβtϕijt∑r∈Ckτirαtηirβt,j∈Ck,0,other.In formula (10), ϕijt takes different values according to the distance d between the path and the center line at the moment t. It follows the normal distribution under N0,1. The efficiency of ant colony search can be improved by introducing differential search.


## 3.2.3. Adaptive Pheromone Update Strategy

The method of pheromone update mainly includes global update method and real-time update method. Some studies show that the global update method has higher search efficiency, but it is easy to fall into local optimum. Also, the real-time update method is easy to find high-quality solutions, but the algorithm’s search efficiency is low [29]. Therefore, this paper integrates the two methods and proposes an adaptive update strategy, and the formula is as follows:(11)τijt+1=1−ρτijt+ω1Qfspbset+ω2Qfsgbset,where spbset is the current optimal path, sgbset is the global optimal path, ρ is the pheromone volatilization coefficient, and Q is the pheromone intensity coefficient. In the early search stage, ω1 is larger, making pheromone update more dependent on the current iterative optimal path. It is conducive to finding more high-quality solutions and avoiding the algorithm falling into local optimal. In the later search stage, ω2 is large, making pheromone update more dependent on the global optimal path. It is conducive to making the algorithm converge quickly.The ICACO algorithm is shown in Algorithm 1.Algorithm 1: ICACO algorithm.
(1)
Construct cellular space of hexagonal grid(2)
Parameter initialization(3)
fori = 1∼itermax (maximum iteration)(4)
if (the ant did not find the target cellular)(5)
The ant decides the next cellular according to transfer rule which introduces differential search strategy(6)
end(7)
Updating the pheromone value between cellular according to the adaptive strategy(8)
end


## 4. Improved Dynamic Window Algorithm (IDWA)

Due to the lack of global programming guidance, traditional DWA algorithm is prone to fall into local optimality. Therefore, this paper introduces the angle difference between the path end point and the target direction into the evaluation function of DWA algorithm to guide the algorithm search to solve this problem. The main idea of DWA algorithm is to predict the next path of UAV to determine the speed and direction of the next moment.Firstly, the next speed range of UAV is determined, and the path simulation is carried out based on the UAV kinematic model. Furthermore, these paths are scored by evaluation function, and the path with the highest score is taken as the current optimal path, in which the corresponding speed is the UAV optimal speed. The specific process of the algorithm is as follows (see Algorithm2).Algorithm 2: IDWA algorithm.
(1)
Parameter initialization(2)
while (the current position is not the ending point)(3)
Determining the next UAV speed range(4)
Performing path prediction based on UAV velocity range and motion model(5)
Determining the optimal path according to the evaluation function which introduces global information(6)
Determining the optimal speed and searching forward(7)
end


### 4.1. UAV Path Prediction

The kinematic model of UAV has been introduced in Section2.1 and will not be repeated here. In fact, according to formula (2), based on the current pose of UAV, the trajectory can be predicted as long as the velocity vector is determined at this time. In this paper, we set the predicted time step Δt to be 0.1 s, and the number of the predicted time step is 50. In other words, predicting the next 5 seconds of the UAV's path planning. This is the result of considering UAV flight safety and algorithm efficiency. On the one hand, UAV may not be able to respond to an emerging threat in time if the predicted path is too short; on the other hand, the efficiency of the algorithm will be greatly reduced if the predicted path is too long.


### 4.2. Velocity Vector Sampling

We mentioned in Section4.1 that the velocity vector is one of the keys to predicting paths. In the DWA algorithm, UAV samples many times in the velocity vector space at time t to obtain the velocity vector. The velocity vector of UAV is restricted within a certain range by its own maximum and minimum speed, overload bearing capacity, and braking distance.(1)
Maximum and minimum speed limitation:(12)v1=v,ω|v∈vmin,vmax,ω∈ωmin,ωmax.(2)
Overload bearing capacity limitation:(13)v2=v,ω|v∈va−vb·Δt,va+vc·Δt,ω∈ωa−ωb·Δt,ωa+ωc·Δt,whereva is the current linear velocity, vb· is the maximum linear deceleration, vc· is the maximum linear acceleration, ωa is the current angular velocity, ωb· is the maximum angular deceleration, and ωc· is the maximum angular acceleration.(3)
Braking distance limitation: when new terrain obstacles or threats are found, UAV must avoid hitting obstacles or threats by maximum deceleration speed in order to ensure flight safety.(14)v3=v,ω|v≤2Dvb·0.5,ω≤2Dωb·0.5,whereD is the distance between the current position of UAV and obstacles.In summary, the speed range of UAV can be expressed as(15)vUAV=v1∩v2∩v3.


### 4.3. Evaluation Function Based on Global Information

In order to solve the problem that the traditional DWA algorithm is prone to fall into local optimal, this paper introduces the angle difference between the path ending point and the target direction into the evaluation function to guide the algorithm to screen out the optimal path, ensuring the local path search based on the global optimal path. The improved evaluation function is as follows:(16)Gv,ω=α1Headv,ω+α2distv,ω+α3velv,ω,where Headv,ω is the angle difference between the path ending direction and the current target point. The smaller the angle, the better the path; distv,ω is the distance between the path and the nearest obstacle or threat. The larger the distance, the better the path; velv,ω is the evaluation function of the current speed. The faster the speed, the better the path; α1, α2, and α3 are the weight coefficients of the above three, respectively.To avoid the influence of different dimensional and extreme values on the path evaluation results, normalization of each item in the evaluation function is also required.(17)Headi′=Headi∑i=1nHeadi,disti′=disti∑i=1ndisti,veli′=veli∑i=1nveli,where n is the total number of paths to be predicted.By using the above evaluation function, UAV can avoid obstacles and threats and obtain local path conforming to global optimum, which avoids algorithm falling into local optimum.


## 4.1. UAV Path Prediction

The kinematic model of UAV has been introduced in Section2.1 and will not be repeated here. In fact, according to formula (2), based on the current pose of UAV, the trajectory can be predicted as long as the velocity vector is determined at this time. In this paper, we set the predicted time step Δt to be 0.1 s, and the number of the predicted time step is 50. In other words, predicting the next 5 seconds of the UAV's path planning. This is the result of considering UAV flight safety and algorithm efficiency. On the one hand, UAV may not be able to respond to an emerging threat in time if the predicted path is too short; on the other hand, the efficiency of the algorithm will be greatly reduced if the predicted path is too long.


## 4.2. Velocity Vector Sampling

We mentioned in Section4.1 that the velocity vector is one of the keys to predicting paths. In the DWA algorithm, UAV samples many times in the velocity vector space at time t to obtain the velocity vector. The velocity vector of UAV is restricted within a certain range by its own maximum and minimum speed, overload bearing capacity, and braking distance.(1)
Maximum and minimum speed limitation:(12)v1=v,ω|v∈vmin,vmax,ω∈ωmin,ωmax.(2)
Overload bearing capacity limitation:(13)v2=v,ω|v∈va−vb·Δt,va+vc·Δt,ω∈ωa−ωb·Δt,ωa+ωc·Δt,whereva is the current linear velocity, vb· is the maximum linear deceleration, vc· is the maximum linear acceleration, ωa is the current angular velocity, ωb· is the maximum angular deceleration, and ωc· is the maximum angular acceleration.(3)
Braking distance limitation: when new terrain obstacles or threats are found, UAV must avoid hitting obstacles or threats by maximum deceleration speed in order to ensure flight safety.(14)v3=v,ω|v≤2Dvb·0.5,ω≤2Dωb·0.5,whereD is the distance between the current position of UAV and obstacles.In summary, the speed range of UAV can be expressed as(15)vUAV=v1∩v2∩v3.


## 4.3. Evaluation Function Based on Global Information

In order to solve the problem that the traditional DWA algorithm is prone to fall into local optimal, this paper introduces the angle difference between the path ending point and the target direction into the evaluation function to guide the algorithm to screen out the optimal path, ensuring the local path search based on the global optimal path. The improved evaluation function is as follows:(16)Gv,ω=α1Headv,ω+α2distv,ω+α3velv,ω,where Headv,ω is the angle difference between the path ending direction and the current target point. The smaller the angle, the better the path; distv,ω is the distance between the path and the nearest obstacle or threat. The larger the distance, the better the path; velv,ω is the evaluation function of the current speed. The faster the speed, the better the path; α1, α2, and α3 are the weight coefficients of the above three, respectively.To avoid the influence of different dimensional and extreme values on the path evaluation results, normalization of each item in the evaluation function is also required.(17)Headi′=Headi∑i=1nHeadi,disti′=disti∑i=1ndisti,veli′=veli∑i=1nveli,where n is the total number of paths to be predicted.By using the above evaluation function, UAV can avoid obstacles and threats and obtain local path conforming to global optimum, which avoids algorithm falling into local optimum.


## 5. A Novel UAV Real-Time Path Planning Method Based on Improved Cellular Ant Colony Algorithm and Dynamic Window Algorithm

A real-time path planning method named ICACO-IDWA algorithm is proposed in this paper, which combines ICACO algorithm and IDWA algorithm, so that it can meet the global planning and have real-time threat avoidance capability. Specifically, firstly, ICACO algorithm is used for offline planning to calculate the global optimal path. The turning points, start point, and end point on the global optimal path are defined as the key nodes, and the paths between adjacent key nodes are defined as subpaths. Then, IDWA algorithm is used to avoid dynamic threats on the subpaths with an online approach. When the ending point of subpath is the ending point of global optimal path, the algorithm ends. In Figure4, the ending condition of the algorithm is that the local end point is the global optimal path end point.Figure 4
The flowchart of ICACO-IDWA algorithm.The flowchart of ICACO-IDWA algorithm is as follows.Step 1. Initializing the hexagonal grid map.Step 2. ICACO algorithm is used for path planning, and the global optimal path is obtained.Step 3. Using IDWA algorithm to carry out local path planning between adjacent nodes in the global optimal path.The flowchart of ICACO-IDWA algorithm is shown in Figure4.


## 6. Experimental Analysis

To prove the effectiveness of the proposed hexagonal grid model and ICACO-IDWA algorithm in solving the path planning problem, this paper carries out example simulation verification on the path planning problem, and the experiment is divided into three parts. Experiment 1: a 20 × 20 scale path planning problem is modeled using rectangular grid and hexagonal grid, respectively, and CACO algorithm is used to illustrate the advantages of the proposed new gird model, compared with rectangular grid. Experiment 2: firstly, verify the influence of related parameter on the performance of ICACO algorithm on the 20 × 20 scale problem. Then, ICACO algorithm and traditional CACO algorithm are used to different scale problems to illustrate the advantage of ICACO algorithm. Experiment 3: a number of threats are randomly set in different scale path planning problems to verify the threat avoidance ability of ICACO-IDWA algorithm. In these three experiments, the side length of rectangular grid is1km, the side length of hexagonal grid is 1/3km, and the objective functions are in formula (4). The software platform used in the experiment is MATLAB R2019a.


### 6.1. Analysis of Different Grid Path Planning Results

To illustrate the effectiveness of the hexagon grid model in solving the path planning problem, a 20 × 20 scale path planning problem is modeled by using rectangular grids and hexagonal grids, respectively, and CACO algorithm is used to solve this problem. The parameters of CACO algorithm are set as follows. The pheromone elicitation factorα is 1, the expectation elicitation factor β is 7, the pheromone volatilization coefficient ρ is 0.3, the pheromone intensity coefficient Q is 1, the number of ants is 50, and the number of iterations is 100. The experimental results are shown in Figure 5.Figure 5
Simulation results of different grid maps. (a) Simulation results of rectangular grid map. (b) Simulation results of hexagonal grid map.
(a)(b)Figure5 shows that both rectangular grid and hexagonal grid can realize path planning. In the face of “U-trap,” the path planned by the former cannot be effectively avoided, while the path planned by the latter can be effectively avoided. In addition, there are 10 turns in the path planned by the former, and 6 turns in the path planned by the latter, which reduces the number of turns, indicating the effectiveness of hexagonal grid in solving the path planning problem.


### 6.2. Global Path Planning Result Analysis

#### 6.2.1. ICACO Algorithm Parameter Analysis

In order to verify the influence of pheromone heuristic factorα, expected heuristic factor β, and pheromone volatilization factor ρ on the algorithm performance, we used the control variable method to calculate the influence of another parameter on algorithm performance in solving the 20 × 20 scale path planning problem. Parameter settings of the algorithm in Figure 6 are shown in Table 1. The experimental results are shown in Figure 6.Figure 6
Different parameters affect the performance of the algorithm. (a) Number of iterations and minimum cost curve under differentα. (b) Number of iterations and minimum cost curve under different β. (c) Number of iterations and minimum cost curve under different ρ.
(a)(b)(c)Table 1
Parameter settings of the algorithm in Figure6.
αβρQψφAnt numberIteration numberFigure6(a)—70.3Figure6(b)1—0.310.50.555100Figure6(c)17—It can be seen from Figure6 that when α∈1,2, β∈5,8, and ρ∈0.3,0.6, ICACO algorithm can find the optimal path and its convergence speed is fast, which has good performance. Besides, literature [30] indicates that ICACO algorithm performs well when the ant colony number is one-sixth of the number of free cellular. Based on the above analysis, ICACO algorithm parameters are shown in Table 2.Table 2
Algorithm parameter setting.
ParameterScaleNumberα—1.5β—7ρ—0.3Q—1φ—0.5Ant number20553011550355Iteration number—100ψ—0.5


#### 6.2.2. Path Planning Result Analysis

ICACO algorithm is compared with CACO algorithm on 20 × 20 (small scale) and 30 × 30 (large scale) path planning problems, respectively, to verify the algorithm performance.Figure7 shows the path planning results of ICACO algorithm and CACO algorithm under different scale problems. The red solid line is the path obtained by ICACO algorithm, and the blue dotted line is the path obtained by CACO algorithm. As shown in Figure 7(a), in the small-scale problem, there is little difference in the path cost between the two algorithms, but the path obtained by ICACO algorithm is slightly better than that obtained by CACO algorithm. As shown in Figure 7(b), with the increase of the problem scale and the appearance of complex terrain, the path obtained by ICACO algorithm is significantly better than that obtained by CACO algorithm. The CACO algorithm fails to plan feasible paths,, as shown in Figure 8 (parameter settings of CACO are the same as those in Table 1).Figure 7
Path planning results of algorithms in different scale maps. (a) Path planning result in the 20 × 20 scale map. (b) Path planning result in the 30 × 30 scale map.
(a)(b)Figure 8
The purple line is the trap which is created by obstacles. The red line is the trap which is created by its own actions.According to the simulation results, the difference between the two algorithms is not obvious when the environment is relatively simple. With the complexity of the environment and the increase of the problem scale, the performance of ICACO algorithm is obviously better than that of CACO algorithm. On the one hand, ICACO algorithm makes use of the new pheromone updating mechanism, which considers the current path and the historical optimal path comprehensively; meanwhile, it effectively improves the algorithm’s optimization accuracy. On the other hand, ICACO algorithm introduces the differential search strategy and the concept of potential field to improve the search speed of the algorithm. In addition, the heuristic function of the algorithm also considers the turning cost to ensure the safety of UAV during flight. In order to further illustrate the advantages of ICACO algorithm, the stability and convergence of the algorithm are analyzed as follows.


#### 6.2.3. Stability Analysis

To verify the stability of the algorithm, CACO algorithm and ICACO algorithm are used to solve the path planning problems of different scales. Each algorithm is independently run for 30 times, and the maximum number of iterations is 100. The experimental results are shown in Table3.Table 3
The path planning results of each algorithm in different scale problems.
ScaleAlgorithmMeanVarianceNumber of optimum pathsNumber of turns20 × 20CACO algorithm46.7131.0786ICACO algorithm42.54030430 × 30CACO algorithm88.27129.37112ICACO algorithm76.210.84266It can be seen from Table3 that the mean and variance of path cost obtained by ICACO algorithm are both smaller than those obtained by CACO algorithm. Besides, ICACO algorithm can jump out of the local optimum and find the optimal path, while CACO algorithm basically falls into the local optimum. Taking the 20 × 20 scale path planning problem as an example, the mean path cost of ICACO algorithm is 8.93% lower than that of CACO algorithm, and all of them find the optimal path, while CACO algorithm basically falls into the local optimal. In addition, the number of path turning points obtained by ICACO algorithm is less than that obtained by CACO algorithm, which effectively improves the safety of UAV during flight.


#### 6.2.4. Convergence Analysis

To verify the convergence performance of ICACO algorithm, ICACO algorithm and CACO algorithm are iterated for 100 times, respectively, under different scale problems. Parameter settings are the same as those in Table1, and the convergence curve is shown in Figure 9. The blue solid line is the convergence curve of ICACO algorithm, and the black dotted line is the convergence curve of CACO algorithm. The ordinate is the path cost, and the abscissa is the number of iterations.Figure 9
Convergence curves of each algorithm in different scale maps. (a) Convergence curves in the 20 × 20 scale map. (b) Convergence curves in the 30 × 30 scale map.
(a)(b)It can be seen from Figure9 that the two algorithms show a trend of oscillation in the early stage of iteration, but generally a downward trend, and the path cost can converge to a stable value. On the one hand, compared with CACO algorithm, ICACO algorithm has fewer iterations and can converge at a faster speed. This is because the differential search strategy is introduced to make the ant colony have a higher pheromone level at a better location, accelerating the algorithm search. On the other hand, the convergence value of ICACO algorithm is smaller than that of CACO algorithm. The cost of the optimal path obtained by ICACO algorithm for the 20 × 20 and 30 × 30 scale problems is 44.53 and 73.98, respectively, while the cost of the path obtained by CACO algorithm is 48.53 and 85.95, respectively, indicating that the quality of the solution obtained by ICACO algorithm is improved.


### 6.3. Path Planning Effect Analysis Based on ICACO-IDWA Algorithm

In this part, four groups of simulation experiments are set. Threats are randomly added to the hexagonal grid map of the 20 × 20 and 30 × 30 scale path planning problem (the number of threats in the four groups is 0, 1, 2, and 3, respectively, as shown in Figure10), and ICACO algorithm and ICACO-IDWA algorithm are, respectively, used to solve the problem to verify the real-time path planning capability of the ICACO-IDWA algorithm. The parameters of the IDWA algorithm are set as follows: the maximum speed is 50 m/s, the maximum angular speed is 20°/s, the speed resolution is 0.5 m/s, the acceleration is 10 m/s2, and the angular acceleration is 50°/s2. The weight coefficients of each item in the evaluation function are α1=0.3, α2=0.2, and α3=0.5. The parameters of the ICACO algorithm are the same as those in Table 2. The path planning results of each group experiment are shown in Figure 10 and Table 3. Among them, the solid green line is the optimal path obtained by the ICACO algorithm, the solid red line is the optimal path obtained by ICACO-IDWA algorithm, the blue grid is the random threat, the black grid indicates the fixed terrain obstacles and threats, and the white grid is the passable area.Figure 10
Real-time path planning results. (a) Path planning results without random threat (20 × 20 scale map). (b) Path planning results without random threat (30 × 30 scale map). (c) Path planning results for 1 random threat (20 × 20 scale map). (d) Path planning results for 1 random threat (30 × 30 scale map). (e) Path planning results for 2 random threats (20 × 20 scale map). (f) Path planning results for 2 random threats (30 × 30 scale map). (g) Path planning results for 3 random threats (20 × 20 scale map). (h) Path planning results for 3 random threats (30 × 30 scale map).
(a)(b)(c)(d)(e)(f)(g)(h)As can be seen from Figure10, when there is no random threat in the map (see Figures 10(a) and 10(b)), both ICACO algorithm and ICACO-IDWA algorithm can plan the optimal path. However, the velocity direction of the path obtained by the former changes at the turning point, which is not conducive to UAV flight. The velocity direction of the path obtained by the latter changes continuously (see Figure11), which is more suitable for UAV flight. After a threat appears suddenly (see Figures 10(c) and 10(d)), ICACO algorithm cannot avoid the newly emerging threat, while ICACO-IDWA algorithm can realize real-time threat avoidance and maintain the smoothness and optimality of the path. When the number of threats continues to increase (see Figures 10(e)–10(h)), ICACO-IDWA algorithm can still effectively avoid threats and find the optimal path.Figure 11
UAV angular velocity curves. (a) 20 × 20 scale map. (b) 30 × 30 scale map.
(a)(b)In general, due to sudden threats in the path, UAV takes the “circling” strategy to avoid, and this will lead to an increase in the path cost. However, Table4 shows that the path cost with one random threat is less than the path without random threat in the 20 × 20 scale map. This is because IDWA algorithm requires UAV to keep a certain distance from terrain obstacles and threats on the map to ensure flight safety (see Figure 10(a)). However, after random threat appears, UAV can only approach the threat actively to avoid it (see Figure 10(c)), so that the planned path length happens to be smaller than the former, but the speed advantage of the UAV is sacrificed. Figure 12 shows part of the velocity curve in the process of UAV threat avoidance. As shown in Figure 12(a), when UAV detects the first random threat (the number of posture node is about 200), UAV appears obvious deceleration process to execute the “circling” strategy, resulting in longer path planning time and increasing algorithm time.Table 4
The path planning result of ICACO-IDWA algorithm.
ScaleRandom threat numberCostTotal time (s)Local path time (s)123456720 × 20044.17139.5621.7324.092.3169.6821.75——143.75153.5421.7339.962.246722.61——243.88167.9121.7339.962.2480.7423.24——345.07175.6321.7339.962.2488.3523.35——30 × 30076.70235.6240.5136.222326.036.958715.91177.35240.1640.5139.0322.5326.516.9687.7316.89278.26266.5840.5155.5425.9625.47.1695.8216.19379.07279.0840.5155.5425.9625.47.16107.3817.13Figure 12
UAV velocity curves. (a) 20 × 20 scale map. (b) 30 × 30 scale map.
(a)(b)Remark 1.
Local path 1 refers to the path between the start of the global path and the first turning point. Local path 2 refers to the path between the first turning point of the global path and the second turning point, and so on; all seven local paths are defined this way.
In conclusion, ICACO-IDWA algorithm proposed in this paper can realize the real-time threat avoidance of UAV without significantly increasing the path planning time, and the obtained path is smooth, which effectively realizes the real-time path planning of UAV.


## 6.1. Analysis of Different Grid Path Planning Results

To illustrate the effectiveness of the hexagon grid model in solving the path planning problem, a 20 × 20 scale path planning problem is modeled by using rectangular grids and hexagonal grids, respectively, and CACO algorithm is used to solve this problem. The parameters of CACO algorithm are set as follows. The pheromone elicitation factorα is 1, the expectation elicitation factor β is 7, the pheromone volatilization coefficient ρ is 0.3, the pheromone intensity coefficient Q is 1, the number of ants is 50, and the number of iterations is 100. The experimental results are shown in Figure 5.Figure 5
Simulation results of different grid maps. (a) Simulation results of rectangular grid map. (b) Simulation results of hexagonal grid map.
(a)(b)Figure5 shows that both rectangular grid and hexagonal grid can realize path planning. In the face of “U-trap,” the path planned by the former cannot be effectively avoided, while the path planned by the latter can be effectively avoided. In addition, there are 10 turns in the path planned by the former, and 6 turns in the path planned by the latter, which reduces the number of turns, indicating the effectiveness of hexagonal grid in solving the path planning problem.


## 6.2. Global Path Planning Result Analysis

### 6.2.1. ICACO Algorithm Parameter Analysis

In order to verify the influence of pheromone heuristic factorα, expected heuristic factor β, and pheromone volatilization factor ρ on the algorithm performance, we used the control variable method to calculate the influence of another parameter on algorithm performance in solving the 20 × 20 scale path planning problem. Parameter settings of the algorithm in Figure 6 are shown in Table 1. The experimental results are shown in Figure 6.Figure 6
Different parameters affect the performance of the algorithm. (a) Number of iterations and minimum cost curve under differentα. (b) Number of iterations and minimum cost curve under different β. (c) Number of iterations and minimum cost curve under different ρ.
(a)(b)(c)Table 1
Parameter settings of the algorithm in Figure6.
αβρQψφAnt numberIteration numberFigure6(a)—70.3Figure6(b)1—0.310.50.555100Figure6(c)17—It can be seen from Figure6 that when α∈1,2, β∈5,8, and ρ∈0.3,0.6, ICACO algorithm can find the optimal path and its convergence speed is fast, which has good performance. Besides, literature [30] indicates that ICACO algorithm performs well when the ant colony number is one-sixth of the number of free cellular. Based on the above analysis, ICACO algorithm parameters are shown in Table 2.Table 2
Algorithm parameter setting.
ParameterScaleNumberα—1.5β—7ρ—0.3Q—1φ—0.5Ant number20553011550355Iteration number—100ψ—0.5


### 6.2.2. Path Planning Result Analysis

ICACO algorithm is compared with CACO algorithm on 20 × 20 (small scale) and 30 × 30 (large scale) path planning problems, respectively, to verify the algorithm performance.Figure7 shows the path planning results of ICACO algorithm and CACO algorithm under different scale problems. The red solid line is the path obtained by ICACO algorithm, and the blue dotted line is the path obtained by CACO algorithm. As shown in Figure 7(a), in the small-scale problem, there is little difference in the path cost between the two algorithms, but the path obtained by ICACO algorithm is slightly better than that obtained by CACO algorithm. As shown in Figure 7(b), with the increase of the problem scale and the appearance of complex terrain, the path obtained by ICACO algorithm is significantly better than that obtained by CACO algorithm. The CACO algorithm fails to plan feasible paths,, as shown in Figure 8 (parameter settings of CACO are the same as those in Table 1).Figure 7
Path planning results of algorithms in different scale maps. (a) Path planning result in the 20 × 20 scale map. (b) Path planning result in the 30 × 30 scale map.
(a)(b)Figure 8
The purple line is the trap which is created by obstacles. The red line is the trap which is created by its own actions.According to the simulation results, the difference between the two algorithms is not obvious when the environment is relatively simple. With the complexity of the environment and the increase of the problem scale, the performance of ICACO algorithm is obviously better than that of CACO algorithm. On the one hand, ICACO algorithm makes use of the new pheromone updating mechanism, which considers the current path and the historical optimal path comprehensively; meanwhile, it effectively improves the algorithm’s optimization accuracy. On the other hand, ICACO algorithm introduces the differential search strategy and the concept of potential field to improve the search speed of the algorithm. In addition, the heuristic function of the algorithm also considers the turning cost to ensure the safety of UAV during flight. In order to further illustrate the advantages of ICACO algorithm, the stability and convergence of the algorithm are analyzed as follows.


### 6.2.3. Stability Analysis

To verify the stability of the algorithm, CACO algorithm and ICACO algorithm are used to solve the path planning problems of different scales. Each algorithm is independently run for 30 times, and the maximum number of iterations is 100. The experimental results are shown in Table3.Table 3
The path planning results of each algorithm in different scale problems.
ScaleAlgorithmMeanVarianceNumber of optimum pathsNumber of turns20 × 20CACO algorithm46.7131.0786ICACO algorithm42.54030430 × 30CACO algorithm88.27129.37112ICACO algorithm76.210.84266It can be seen from Table3 that the mean and variance of path cost obtained by ICACO algorithm are both smaller than those obtained by CACO algorithm. Besides, ICACO algorithm can jump out of the local optimum and find the optimal path, while CACO algorithm basically falls into the local optimum. Taking the 20 × 20 scale path planning problem as an example, the mean path cost of ICACO algorithm is 8.93% lower than that of CACO algorithm, and all of them find the optimal path, while CACO algorithm basically falls into the local optimal. In addition, the number of path turning points obtained by ICACO algorithm is less than that obtained by CACO algorithm, which effectively improves the safety of UAV during flight.


### 6.2.4. Convergence Analysis

To verify the convergence performance of ICACO algorithm, ICACO algorithm and CACO algorithm are iterated for 100 times, respectively, under different scale problems. Parameter settings are the same as those in Table1, and the convergence curve is shown in Figure 9. The blue solid line is the convergence curve of ICACO algorithm, and the black dotted line is the convergence curve of CACO algorithm. The ordinate is the path cost, and the abscissa is the number of iterations.Figure 9
Convergence curves of each algorithm in different scale maps. (a) Convergence curves in the 20 × 20 scale map. (b) Convergence curves in the 30 × 30 scale map.
(a)(b)It can be seen from Figure9 that the two algorithms show a trend of oscillation in the early stage of iteration, but generally a downward trend, and the path cost can converge to a stable value. On the one hand, compared with CACO algorithm, ICACO algorithm has fewer iterations and can converge at a faster speed. This is because the differential search strategy is introduced to make the ant colony have a higher pheromone level at a better location, accelerating the algorithm search. On the other hand, the convergence value of ICACO algorithm is smaller than that of CACO algorithm. The cost of the optimal path obtained by ICACO algorithm for the 20 × 20 and 30 × 30 scale problems is 44.53 and 73.98, respectively, while the cost of the path obtained by CACO algorithm is 48.53 and 85.95, respectively, indicating that the quality of the solution obtained by ICACO algorithm is improved.


## 6.2.1. ICACO Algorithm Parameter Analysis

In order to verify the influence of pheromone heuristic factorα, expected heuristic factor β, and pheromone volatilization factor ρ on the algorithm performance, we used the control variable method to calculate the influence of another parameter on algorithm performance in solving the 20 × 20 scale path planning problem. Parameter settings of the algorithm in Figure 6 are shown in Table 1. The experimental results are shown in Figure 6.Figure 6
Different parameters affect the performance of the algorithm. (a) Number of iterations and minimum cost curve under differentα. (b) Number of iterations and minimum cost curve under different β. (c) Number of iterations and minimum cost curve under different ρ.
(a)(b)(c)Table 1
Parameter settings of the algorithm in Figure6.
αβρQψφAnt numberIteration numberFigure6(a)—70.3Figure6(b)1—0.310.50.555100Figure6(c)17—It can be seen from Figure6 that when α∈1,2, β∈5,8, and ρ∈0.3,0.6, ICACO algorithm can find the optimal path and its convergence speed is fast, which has good performance. Besides, literature [30] indicates that ICACO algorithm performs well when the ant colony number is one-sixth of the number of free cellular. Based on the above analysis, ICACO algorithm parameters are shown in Table 2.Table 2
Algorithm parameter setting.
ParameterScaleNumberα—1.5β—7ρ—0.3Q—1φ—0.5Ant number20553011550355Iteration number—100ψ—0.5


## 6.2.2. Path Planning Result Analysis

ICACO algorithm is compared with CACO algorithm on 20 × 20 (small scale) and 30 × 30 (large scale) path planning problems, respectively, to verify the algorithm performance.Figure7 shows the path planning results of ICACO algorithm and CACO algorithm under different scale problems. The red solid line is the path obtained by ICACO algorithm, and the blue dotted line is the path obtained by CACO algorithm. As shown in Figure 7(a), in the small-scale problem, there is little difference in the path cost between the two algorithms, but the path obtained by ICACO algorithm is slightly better than that obtained by CACO algorithm. As shown in Figure 7(b), with the increase of the problem scale and the appearance of complex terrain, the path obtained by ICACO algorithm is significantly better than that obtained by CACO algorithm. The CACO algorithm fails to plan feasible paths,, as shown in Figure 8 (parameter settings of CACO are the same as those in Table 1).Figure 7
Path planning results of algorithms in different scale maps. (a) Path planning result in the 20 × 20 scale map. (b) Path planning result in the 30 × 30 scale map.
(a)(b)Figure 8
The purple line is the trap which is created by obstacles. The red line is the trap which is created by its own actions.According to the simulation results, the difference between the two algorithms is not obvious when the environment is relatively simple. With the complexity of the environment and the increase of the problem scale, the performance of ICACO algorithm is obviously better than that of CACO algorithm. On the one hand, ICACO algorithm makes use of the new pheromone updating mechanism, which considers the current path and the historical optimal path comprehensively; meanwhile, it effectively improves the algorithm’s optimization accuracy. On the other hand, ICACO algorithm introduces the differential search strategy and the concept of potential field to improve the search speed of the algorithm. In addition, the heuristic function of the algorithm also considers the turning cost to ensure the safety of UAV during flight. In order to further illustrate the advantages of ICACO algorithm, the stability and convergence of the algorithm are analyzed as follows.


## 6.2.3. Stability Analysis

To verify the stability of the algorithm, CACO algorithm and ICACO algorithm are used to solve the path planning problems of different scales. Each algorithm is independently run for 30 times, and the maximum number of iterations is 100. The experimental results are shown in Table3.Table 3
The path planning results of each algorithm in different scale problems.
ScaleAlgorithmMeanVarianceNumber of optimum pathsNumber of turns20 × 20CACO algorithm46.7131.0786ICACO algorithm42.54030430 × 30CACO algorithm88.27129.37112ICACO algorithm76.210.84266It can be seen from Table3 that the mean and variance of path cost obtained by ICACO algorithm are both smaller than those obtained by CACO algorithm. Besides, ICACO algorithm can jump out of the local optimum and find the optimal path, while CACO algorithm basically falls into the local optimum. Taking the 20 × 20 scale path planning problem as an example, the mean path cost of ICACO algorithm is 8.93% lower than that of CACO algorithm, and all of them find the optimal path, while CACO algorithm basically falls into the local optimal. In addition, the number of path turning points obtained by ICACO algorithm is less than that obtained by CACO algorithm, which effectively improves the safety of UAV during flight.


## 6.2.4. Convergence Analysis

To verify the convergence performance of ICACO algorithm, ICACO algorithm and CACO algorithm are iterated for 100 times, respectively, under different scale problems. Parameter settings are the same as those in Table1, and the convergence curve is shown in Figure 9. The blue solid line is the convergence curve of ICACO algorithm, and the black dotted line is the convergence curve of CACO algorithm. The ordinate is the path cost, and the abscissa is the number of iterations.Figure 9
Convergence curves of each algorithm in different scale maps. (a) Convergence curves in the 20 × 20 scale map. (b) Convergence curves in the 30 × 30 scale map.
(a)(b)It can be seen from Figure9 that the two algorithms show a trend of oscillation in the early stage of iteration, but generally a downward trend, and the path cost can converge to a stable value. On the one hand, compared with CACO algorithm, ICACO algorithm has fewer iterations and can converge at a faster speed. This is because the differential search strategy is introduced to make the ant colony have a higher pheromone level at a better location, accelerating the algorithm search. On the other hand, the convergence value of ICACO algorithm is smaller than that of CACO algorithm. The cost of the optimal path obtained by ICACO algorithm for the 20 × 20 and 30 × 30 scale problems is 44.53 and 73.98, respectively, while the cost of the path obtained by CACO algorithm is 48.53 and 85.95, respectively, indicating that the quality of the solution obtained by ICACO algorithm is improved.


## 6.3. Path Planning Effect Analysis Based on ICACO-IDWA Algorithm

In this part, four groups of simulation experiments are set. Threats are randomly added to the hexagonal grid map of the 20 × 20 and 30 × 30 scale path planning problem (the number of threats in the four groups is 0, 1, 2, and 3, respectively, as shown in Figure10), and ICACO algorithm and ICACO-IDWA algorithm are, respectively, used to solve the problem to verify the real-time path planning capability of the ICACO-IDWA algorithm. The parameters of the IDWA algorithm are set as follows: the maximum speed is 50 m/s, the maximum angular speed is 20°/s, the speed resolution is 0.5 m/s, the acceleration is 10 m/s2, and the angular acceleration is 50°/s2. The weight coefficients of each item in the evaluation function are α1=0.3, α2=0.2, and α3=0.5. The parameters of the ICACO algorithm are the same as those in Table 2. The path planning results of each group experiment are shown in Figure 10 and Table 3. Among them, the solid green line is the optimal path obtained by the ICACO algorithm, the solid red line is the optimal path obtained by ICACO-IDWA algorithm, the blue grid is the random threat, the black grid indicates the fixed terrain obstacles and threats, and the white grid is the passable area.Figure 10
Real-time path planning results. (a) Path planning results without random threat (20 × 20 scale map). (b) Path planning results without random threat (30 × 30 scale map). (c) Path planning results for 1 random threat (20 × 20 scale map). (d) Path planning results for 1 random threat (30 × 30 scale map). (e) Path planning results for 2 random threats (20 × 20 scale map). (f) Path planning results for 2 random threats (30 × 30 scale map). (g) Path planning results for 3 random threats (20 × 20 scale map). (h) Path planning results for 3 random threats (30 × 30 scale map).
(a)(b)(c)(d)(e)(f)(g)(h)As can be seen from Figure10, when there is no random threat in the map (see Figures 10(a) and 10(b)), both ICACO algorithm and ICACO-IDWA algorithm can plan the optimal path. However, the velocity direction of the path obtained by the former changes at the turning point, which is not conducive to UAV flight. The velocity direction of the path obtained by the latter changes continuously (see Figure11), which is more suitable for UAV flight. After a threat appears suddenly (see Figures 10(c) and 10(d)), ICACO algorithm cannot avoid the newly emerging threat, while ICACO-IDWA algorithm can realize real-time threat avoidance and maintain the smoothness and optimality of the path. When the number of threats continues to increase (see Figures 10(e)–10(h)), ICACO-IDWA algorithm can still effectively avoid threats and find the optimal path.Figure 11
UAV angular velocity curves. (a) 20 × 20 scale map. (b) 30 × 30 scale map.
(a)(b)In general, due to sudden threats in the path, UAV takes the “circling” strategy to avoid, and this will lead to an increase in the path cost. However, Table4 shows that the path cost with one random threat is less than the path without random threat in the 20 × 20 scale map. This is because IDWA algorithm requires UAV to keep a certain distance from terrain obstacles and threats on the map to ensure flight safety (see Figure 10(a)). However, after random threat appears, UAV can only approach the threat actively to avoid it (see Figure 10(c)), so that the planned path length happens to be smaller than the former, but the speed advantage of the UAV is sacrificed. Figure 12 shows part of the velocity curve in the process of UAV threat avoidance. As shown in Figure 12(a), when UAV detects the first random threat (the number of posture node is about 200), UAV appears obvious deceleration process to execute the “circling” strategy, resulting in longer path planning time and increasing algorithm time.Table 4
The path planning result of ICACO-IDWA algorithm.
ScaleRandom threat numberCostTotal time (s)Local path time (s)123456720 × 20044.17139.5621.7324.092.3169.6821.75——143.75153.5421.7339.962.246722.61——243.88167.9121.7339.962.2480.7423.24——345.07175.6321.7339.962.2488.3523.35——30 × 30076.70235.6240.5136.222326.036.958715.91177.35240.1640.5139.0322.5326.516.9687.7316.89278.26266.5840.5155.5425.9625.47.1695.8216.19379.07279.0840.5155.5425.9625.47.16107.3817.13Figure 12
UAV velocity curves. (a) 20 × 20 scale map. (b) 30 × 30 scale map.
(a)(b)Remark 1.
Local path 1 refers to the path between the start of the global path and the first turning point. Local path 2 refers to the path between the first turning point of the global path and the second turning point, and so on; all seven local paths are defined this way.
In conclusion, ICACO-IDWA algorithm proposed in this paper can realize the real-time threat avoidance of UAV without significantly increasing the path planning time, and the obtained path is smooth, which effectively realizes the real-time path planning of UAV.


## 7. Conclusions

In this paper, hexagonal grids are used to model the UAV flight space, and a novel ICACO-IDWA algorithm is proposed to solve the real-time path planning problems considering dynamic threats. Specifically, based on traditional CACO algorithm, the potential field concept is introduced to modify the heuristic function, the differential search strategy is adopted to guide the ant colony to search the target quickly, and an adaptive pheromone updating method is designed to select the high-quality path, which effectively improves the efficiency of the algorithm to quickly plan the global optimal path. IDWA algorithm is used to avoid real-time dynamic threat and realize local real-time path planning. The experimental results show that the hexagonal grid can solve the problem of inconsistent simulation time of rectangular grid, and ICACO-IDWA algorithm can satisfy the UAV real-time path planning considering dynamic threat environment, and the obtained path is smooth and conforms to the UAV motion characteristics. In the future research, the following two aspects can be considered. From the model perspective, considering the UAV path planning in three-dimensional space, the model is closer to reality. From the algorithm perspective, consider designing a more efficient optimization mechanism to improve the efficiency of the algorithm, so as to better solve the path planning problem.



---

*Source: 6802360-2022-12-17.xml*