# Research on Complex Multiconstraint Path Planning Based on ACA Hybrid Algorithm

Authors: Hongyun Wang; Min Gao; Weiwei Gao; Wenzhao Li
Journal: International Journal of Aerospace Engineering
 (2022)

---

## Abstract

Aiming at the multiconstraint complex problem of path planning, a hybrid algorithm with fast convergence and fast obstacle avoidance is proposed. According to the actual aircraft, a multiconstrained path cost model with seven components is constructed and defined the parameters and penalty factors of each part. To improve the sensitivity of each part of the trace planning cost function, according to the inconsistency of the cost index unit and measurement range, the expert scoring method is used to configure and normalize the index with weight. Make full advantage of the ACO algorithm and the artificial potential field algorithm to form the ACA hybrid algorithm, a pheromone heuristic function improvement method is proposed, and a control factor is introduced. The proposed model and planning algorithm are simulated based on the MATLAB platform environment, and it is shown by simulations that the hybrid algorithm has obvious advantages in terms of motion trajectory smoothness, number of iterations, and minimum path cost .It well solved the practical application problem of fast path planning convergence and fast avoiding obstacles in the complex environment.


---

## Body

## 1. Introduction

In recent years, the development of advanced technologies such as unmanned platform, autonomous control, network, and artificial intelligence has effectively promoted the development of unmanned system equipment. Since 2007, the U.S. military has successively launched five versions of unmanned road map. Miniaturized unmanned aerial vehicle and cluster combat technology have become one of the key technologies of its third offset strategy. There are many key technologies of cluster operations [1–5], such as cooperative task allocation, cooperative path planning, cooperative formation flight and control, and cooperative attack; among them, path planning is the premise and foundation of mission execution. Under the condition of meeting multiple constraints, path planning plans a flightable path from the initial point to the target point for each UAV. Path planning technology includes global path planning and local dynamic online path planning.Path planning generally consists of the following six parts [6, 7]: describe the planning space, path representation, analyze constraints, determine the cost function, select path search algorithm, and path smoothing. Spatial description [8] is as follows: the main purpose is to establish an environmental model, that is, to transform the actual physical space into the space that can be processed by the algorithm. The planning space directly affects the efficiency and advantages of path planning. There are generally two forms of path representation [7]. One is represented by path points. The adjacent path points are connected by straight lines to form a geometric broken line path. The required accuracy can be achieved by adjusting the number of path points. Generally, it needs to be smoothed; the second is to use the kinematics and dynamics equations of the aircraft to describe the path. This path is relatively smooth, and the smoothing link is omitted. Analysis constraints [8–11] are as follows: the constraints to be considered in path planning include environmental constraints, mission constraints, and UAV performance constraints. Environmental constraints include threat constraints (such as the probability of being found by enemy radar, the probability of enemy missile antiaircraft gun shooting down, and collision probability), no fly zone constraints, and complex meteorological zone constraints. Mission constraints include mission completion time, starting point, target point, fixed heading angle, and low altitude/ultralow altitude penetration. The performance constraints of UAV include maximum/minimum level flight speed, maximum range, maximum/minimum flight altitude, minimum horizontal turning radius, maximum climb angle/dive angle, maximum longitudinal curvature, and maximum normal overload; determining the cost function, for path planning, the cost function is the standard for evaluating the advantages and disadvantages of the planned path. The cost function is composed of many of the above constraints. However, since the range and units of various constraints are different, it needs to be quantified and normalized. The smaller the generation value of the normalized cost function obtained on this basis, the better the path. On the contrary, it indicates that the path is getting worse. Selection of algorithm is as follows: selecting an appropriate algorithm according to the task requirements to plan the path that meets the constraints avoids obstacles and obtains the optimal value of the cost function that is the core part of the path planning problem. Path smoothing is as follows: when the planned path has many inflection points, it actually does not meet the actual flight situation of the aircraft. The aircraft cannot turn frequently during actual flight. At this time, the path needs to be smoothed.The advantages and disadvantages of the path are evaluated by the path cost. The main constraints are path cost, flight turning cost, threat cost, obstacle cost, restricted area cost, flight altitude cost, etc., which constitute the cost function. For the multiconstraint problem of path planning, the selection of the planning algorithm is the foundation of successful solution and also affects the quality of planning results to a great extent [12–14]. For path planning, there are generally two evaluation criteria for judging the advantages and disadvantages of planning algorithms: the selected algorithm can minimize the total cost of flight. The algorithm has fast convergence speed and fast calculation speed. At present, the algorithms of path planning are mainly divided into four categories: first, the path planning algorithm based on mathematics. The advantage of this kind of algorithm is the preciseness of mathematical theory, but the disadvantage is that the calculation time will increase exponentially with the increase of planning problem. When the number of aircraft is not one, but a bee colony with a large number (such as 20 nodes and 48 nodes), the calculation time is bound to increase greatly, which is not suitable for solving large-scale path planning problem [15]. Second, the path planning algorithm is based on artificial potential field [16, 17]. In this kind of algorithm, the target can produce gravitation, while the obstacle can produce repulsion. That is to say, the aircraft is not only subject to gravity, engine thrust, and aerodynamic force but also subject to target gravitation and obstacle repulsion. Its biggest advantage is that the search speed is relatively fast, but it also has limitations. When the obstacle is close to the target, the repulsion may be much greater than the gravity, resulting in the aircraft cannot reach the target at all. In this way, there is the problem of local optimal solution and the failure of search path. Third, path planning is based on graph theory [18–21]. This kind of algorithm usually divides the planned space first and then selects an algorithm to find the optimal or suboptimal path in the planned space. However, this algorithm is highly dependent on the planning space, especially when the environment is complex, and the planning space time is relatively long, which may lead to the failure of path search. Fourth, path planning is based on artificial intelligence [22, 23]. There are many such algorithms, such as bee colony algorithm, ant colony algorithm, genetic algorithm, fish swarm algorithm, and water drop algorithm; due to the characteristics of population, the outstanding advantage of these algorithms is that they can handle parallel computing and plan a path that meets the requirements in possible time. In this study, we should not only consider the path planning of a single aircraft but also lay a foundation for cluster collaborative path planning. The collaboration of the cluster system has high requirements for real-time; so, it is obviously appropriate to choose the artificial intelligence algorithm. Ant colony optimization (ACO) and particle swarm optimization (PSO) are two main swarm intelligence algorithms. Ant colony algorithm is a distributed multiagent system [24–26], which can search the solution independently in the problem space, which is consistent with the distributed structure of the cluster. The ant colony algorithm has the ability of self-organization, and the organizational power and organizational instructions come from the interior of the system, which is also the same as the self-organization structure of decentralized cluster. It has strong robustness, few parameters, and simple setting and is a positive feedback algorithm, which is different from other bionic algorithms, so that the evolution process of the algorithm can be carried out.The outstanding points of this study compared with previous studies are mainly reflected in the following three aspects: first, path planning involves many constraints, its objective function is complex, and the establishment of mathematical model is difficult. In order to reduce the complexity of the problem, this study adopts the idea of hierarchical planning and divides the idea of path planning into two steps. Firstly, according to the known external environment information, flight mission, and its own flight conditions, a globally optimized reference path that meets the constraints is planned before takeoff. If unknown or dynamic external threat information appears in the process of flying according to this path, local path dynamic optimization shall be carried out. In the literature [26–28], the composition of the path cost function mostly only includes the range cost and obstacle cost, without considering the cost caused by the factors such as turning, flight altitude, threat, and attack angle in the actual flight, resulting in a large gap between the actual flight results and the simulation results due to incomplete theoretical research; Second, no relevant literature has been found to normalize different cost function indicators. However, due to the complexity of the composition of the cost function, different index units, and different orders of magnitude, there may be problems that are not sensitive to the impact of some costs in the same function. When considering the multiconstraint path problem, normalization is necessary and extremely important. Thirdly, aiming at the realization of path planning, documents [17–19, 22–29] have studied the path planning algorithm. At present, the development trend of path planning is to organically combine multiple methods, but the main problems are as follows: first, the effect of the algorithm on single missile path planning is acceptable, but if it is transplanted to cluster collaborative path planning, its applicability is not strong, and other cooperative path planning algorithms need to be selected. Second, there is a contradiction between the accuracy and computational efficiency of the algorithm, or the algorithm itself has defects in principle. Third, this topic has a certain continuity, and the research and control of cooperative path planning should be carried out in the later stage. In order to avoid repetitive work, the selected algorithm should not only be well adapted to the path planning of single aircraft but also have good portability under the condition of cooperative constraints. Based on the above considerations, this paper proposes an ACA hybrid path planning algorithm. ACA is a hybrid algorithm combining intelligent ant colony and artificial potential field. In path planning, the ant colony algorithm adopts the intelligent ant colony algorithm with self-organizing and distributed global path planning and gives full play to the positive feedback search mechanism of ant colony by adjusting the information heuristic function. The local path planning adopts the artificial potential field method with good obstacle avoidance effect. This algorithm has the outstanding advantages of good portability, high calculation efficiency, and fast obstacle avoidance.For the above analysis, the main work of this study is divided into four parts: first, according to the constraints of path planning, the path cost model is constructed. Secondly, according to the importance, the expert scoring method is used to normalize the coefficient index of the path cost model. Thirdly, the hybrid algorithm of ant colony and artificial potential field is selected to obtain the heuristic information model of pheromone. Fourthly, the algorithm is verified and analyzed by MATLAB simulation platform.


## 2. Path Planning Problem Description

### 2.1. Path Cost Function

Path planning is a multiconstraint optimization problem. The constraints can be transformed into sub objectives, thus turning the multiconstraint problem into a multiobjective optimization problem [19, 20]. The cost function of path planning with multiple constraints is expressed as follows:
(1)minJ=ω1Jl+ω2Jangle+ω3Jh+ω4Jthreat+ω5Jobstacle+ω6Jnofly+ω7Jlast_angle.Jis the total cost of the path, and Jl is the cost of the path length; Jangle is the cost of the turning, and Jh is the cost of the flight altitude; Jthreat is the cost of threat, and Jobstacle is the cost of the obstacle; Jnofly is the cost of the flight restricted area, and Jlast_angle is the cost of the specified terminal attack angle; ωi is the weight coefficient, and the value is in the range of [0, 1].


### 2.2. Determination of Cost Functions

#### 2.2.1.Jl Determination of Length Cost

The total length of the path can be expressed as follows:(2)Jl=∑i=0npi+1−pi.pi is the first node from the starting point i, and pi+1 is the next node.


#### 2.2.2.Jangle Determination of Turning Cost

For the fixed wing UAV, the maximum turning angle limits its generated path to be less than or equal to the predetermined maximum turning angle. Assuming that a turning angleαmax is formed by three points (pi−1,pi,pi+1), the constraint formula can be expressed as follows:
(3)Jangle=fαmaxarccospi−pi−1pi+1−pipi−pi−1pi+1−pi−αmax,0.fα is called the turning penalty coefficient.


#### 2.2.3.Jh Confirmation of Flight Altitude Cost

The fixed wing UAV fly below 2000 meters, and the main patrol altitude is about 200 meters.(4)Jh=fhmaxh,0.fh is called altitude the penalty coefficient.


#### 2.2.4.Jthreat Determination of Threat Cost

Threat cost refers to the extent to which the fixed wing UAV is exposed to the threat of enemy detection radar, electromagnetic interference, and antiaircraft weapons during the flight process. The closer the fixed wing UAV to these targets, the more likely it is to be spotted and destroyed. For brief description, it is assumed that the cost of a threat at some point along the path is inversely proportional to the distance of the threat. Thus, threat cost function can be expressed as follows:(5)Jthreat=∑i=13∑k=0n−1fti,jkl/n.i=1, i=2, and i=3 represent the threat brought by enemy detection, electromagnetic interference, and antiaircraft weapons (antiaircraft missiles, antiaircraft guns, etc.), respectively. fti,jkl/n is the function of the distance between the path point and the threat point. It means that the path length from the beginning point to the end point is evenly divided into segments according to the number of path points set.


#### 2.2.5.Jobstacle Determination the Cost of Obstacles

In the process of path planning, obstacles in two-dimensional space are generally treated as circular or elliptical objects, and obstacles in three-dimensional space are generally treated as spherical, ellipsoidal, or vertebral objects. This method can be easily described by the mathematical expression in terms of the real-time distance from the center of mass of the aircraft to the ball center of the obstacle and the radius of the spherical obstacle. Base on this, whether the aircraft collides with obstacles at the current time can be judged. The cost function of obstacles can be simply expressed as follows:(6)Jobstacle=fomaxd−R,0d=minpn−q.R is the radius of the obstacle, pn is any point on the surface of the obstacle, and q is the closest point between the surface of the obstacle and the position of the patrol bullet at the current time; fo is called obstacles penalty coefficient.


#### 2.2.6.Jnofly Determination of Flight Forbidden Area Cost

The expression of cost function corresponding to the flight restricted area is similar to that of obstacle, which can be expressed simply by the following formula:(7)Jnofly=fnmaxd−r,0.fn is called forbidden penalty coefficient.


#### 2.2.7.Jlast_angle Determination of the End Attack Angle Cost

When the fixed wing UAV fly to the target, if the scheme of fixed-direction attack is adopted, the probability of the target being destroyed is the largest, and the information obtained is the most. Besides, when the cooperative flight is in cooperation, the direction of attack can be set for each patrol bullet to achieve saturation attack in many aspects and improve the penetration probability.(8)Jlast_angle=flastmaxactanylast−ylast‐1xlast−xlast‐1−αmax−Δα,0.flast is the penalty coefficient corresponding to the deviation of the attack from the specified angle, and Δα is the size of the deviation of the attack direction angle.


### 2.3. Normalization of Performance Indicators

The performance indicators of the above seven cost functions differentiate in unit and orders of magnitude, even if the same unit may differentiate in large orders of magnitude, such as path length and altitude. This difference inevitably causes the result of flight path planning to be insensitive to the value of weight. Thus, it is critical to carry out 0-1 normalization for the performance indicators of the cost function.The key of 0-1 normalization is to find the maximum and minimum value of the corresponding index. The performance indicators of the above seven cost functions can be divided into two categories according to their units: one is distance-related indicators (range, height, threat, obstacle, and restricted area); the other is angle-related indicators (turning and terminal angle of attack). According to the constraint relation, these performance indicators can be divided into three categories: linear increasing form (maximum constraint), linear decreasing form (minimum constraint), and trapezoidal change form.The range, altitude, and turn belong to the category of linear increasing form, which can be represented as Figure1.
(9)y=0x≤a,M−Lx−ab−a+L,a<x<b,1x≥b.Figure 1
Linear increment.The obstacle and restricted flight area belong to the category of linear decreasing form, which is expressed as Figure2 follows:
(10)y=1x≤a,M−Lb−xb−a+L,a<x<b0x≥b.,Figure 2
Linear decline.The terminal attack angle belongs to the category of trapezoid change form, which can be expressed as Figure3 follows:
(11)y=0x≤aorx≥d,M−Lb−xb−a+La<x<b,1b≤x≤c,M−Ld−xd−c+Lc<x<d.Figure 3
Trapezoidal.


### 2.4. Selection of Weights

The weight of path planning is usually determined according to the experience or intentions of experts. The path planning contains seven attributes: range, turn, altitude, threat, obstacle, restricted area, and angle of terminal attack. Thus, the weight of path planning is expressed as follows:(12)ω1+ω2+ω3+ω4+ω5+ω6+ω7=1.


#### 2.4.1. Build the Index Importance Judgment Matrix

Build the index importance judgment matrix and use “1-9 scale” to represent the importance of the index, as listed in Table1. Judgment criterion is as follows: set u1, u2.un for n teams. Every two teams play a match, and the total score of each match is 1 point. For ui and uj (i≠j), the scores of the two teams are, respectively, denoted as uij and uji, and the two scores should satisfyuij≥0, uij+uji=0 (i≠j).Table 1
Importance.
ValuesMeaning1Element A is as important as element B3Element A is slightly more important than element B5Element A is significantly more important than element B7Element A is more important than element B9Element A is extremely important than element B2, 4, 6, 8The median of the above importance


#### 2.4.2. Score by Experts to Get the Judgment Matrix of Pairwise Importance Degree

The data in Table2 is converted according to the following formula, and the data listed in Table 3 was obtained.
(13)uij=kk+1aij=k,1k+1aij=1k,1aij=1,i≠j,0aij=1,i=j.Table 2
Comprehensive list of weight values.
ω1ω2ω3ω4ω5ω7ω1129546ω21/216324ω31/91/611/31/41/2ω41/51/3311/22ω51/41/24213ω71/61/421/21/31Table 3
Weight list after conversion.
ω1ω2ω3ω4ω5ω7ω102/39/105/64/56/7ω21/306/73/42/34/5ω31/101/701/41/51/3ω41/61/43/401/32/3ω51/51/34/52/303/4ω71/71/52/31/31/40Setω5=ω6. The reason for such values in Table 3 is that the influence of range, turn, obstacle, and forbidden area is first considered in the path planning of this study. Then, the influence of threat and terminal angle of attack is considered in the dynamic path planning.Obtain the normalized weight coefficient:(14)ωc=ωc1,ωc2,ωc3,ωc4,ωc5,ωc6,ωc7,ωci=2nn−1∑j=17uij,i=1,2,3,4,5,6,7,∑i7ωci=1.


## 2.1. Path Cost Function

Path planning is a multiconstraint optimization problem. The constraints can be transformed into sub objectives, thus turning the multiconstraint problem into a multiobjective optimization problem [19, 20]. The cost function of path planning with multiple constraints is expressed as follows:
(1)minJ=ω1Jl+ω2Jangle+ω3Jh+ω4Jthreat+ω5Jobstacle+ω6Jnofly+ω7Jlast_angle.Jis the total cost of the path, and Jl is the cost of the path length; Jangle is the cost of the turning, and Jh is the cost of the flight altitude; Jthreat is the cost of threat, and Jobstacle is the cost of the obstacle; Jnofly is the cost of the flight restricted area, and Jlast_angle is the cost of the specified terminal attack angle; ωi is the weight coefficient, and the value is in the range of [0, 1].


## 2.2. Determination of Cost Functions

### 2.2.1.Jl Determination of Length Cost

The total length of the path can be expressed as follows:(2)Jl=∑i=0npi+1−pi.pi is the first node from the starting point i, and pi+1 is the next node.


### 2.2.2.Jangle Determination of Turning Cost

For the fixed wing UAV, the maximum turning angle limits its generated path to be less than or equal to the predetermined maximum turning angle. Assuming that a turning angleαmax is formed by three points (pi−1,pi,pi+1), the constraint formula can be expressed as follows:
(3)Jangle=fαmaxarccospi−pi−1pi+1−pipi−pi−1pi+1−pi−αmax,0.fα is called the turning penalty coefficient.


### 2.2.3.Jh Confirmation of Flight Altitude Cost

The fixed wing UAV fly below 2000 meters, and the main patrol altitude is about 200 meters.(4)Jh=fhmaxh,0.fh is called altitude the penalty coefficient.


### 2.2.4.Jthreat Determination of Threat Cost

Threat cost refers to the extent to which the fixed wing UAV is exposed to the threat of enemy detection radar, electromagnetic interference, and antiaircraft weapons during the flight process. The closer the fixed wing UAV to these targets, the more likely it is to be spotted and destroyed. For brief description, it is assumed that the cost of a threat at some point along the path is inversely proportional to the distance of the threat. Thus, threat cost function can be expressed as follows:(5)Jthreat=∑i=13∑k=0n−1fti,jkl/n.i=1, i=2, and i=3 represent the threat brought by enemy detection, electromagnetic interference, and antiaircraft weapons (antiaircraft missiles, antiaircraft guns, etc.), respectively. fti,jkl/n is the function of the distance between the path point and the threat point. It means that the path length from the beginning point to the end point is evenly divided into segments according to the number of path points set.


### 2.2.5.Jobstacle Determination the Cost of Obstacles

In the process of path planning, obstacles in two-dimensional space are generally treated as circular or elliptical objects, and obstacles in three-dimensional space are generally treated as spherical, ellipsoidal, or vertebral objects. This method can be easily described by the mathematical expression in terms of the real-time distance from the center of mass of the aircraft to the ball center of the obstacle and the radius of the spherical obstacle. Base on this, whether the aircraft collides with obstacles at the current time can be judged. The cost function of obstacles can be simply expressed as follows:(6)Jobstacle=fomaxd−R,0d=minpn−q.R is the radius of the obstacle, pn is any point on the surface of the obstacle, and q is the closest point between the surface of the obstacle and the position of the patrol bullet at the current time; fo is called obstacles penalty coefficient.


### 2.2.6.Jnofly Determination of Flight Forbidden Area Cost

The expression of cost function corresponding to the flight restricted area is similar to that of obstacle, which can be expressed simply by the following formula:(7)Jnofly=fnmaxd−r,0.fn is called forbidden penalty coefficient.


### 2.2.7.Jlast_angle Determination of the End Attack Angle Cost

When the fixed wing UAV fly to the target, if the scheme of fixed-direction attack is adopted, the probability of the target being destroyed is the largest, and the information obtained is the most. Besides, when the cooperative flight is in cooperation, the direction of attack can be set for each patrol bullet to achieve saturation attack in many aspects and improve the penetration probability.(8)Jlast_angle=flastmaxactanylast−ylast‐1xlast−xlast‐1−αmax−Δα,0.flast is the penalty coefficient corresponding to the deviation of the attack from the specified angle, and Δα is the size of the deviation of the attack direction angle.


## 2.2.1.Jl Determination of Length Cost

The total length of the path can be expressed as follows:(2)Jl=∑i=0npi+1−pi.pi is the first node from the starting point i, and pi+1 is the next node.


## 2.2.2.Jangle Determination of Turning Cost

For the fixed wing UAV, the maximum turning angle limits its generated path to be less than or equal to the predetermined maximum turning angle. Assuming that a turning angleαmax is formed by three points (pi−1,pi,pi+1), the constraint formula can be expressed as follows:
(3)Jangle=fαmaxarccospi−pi−1pi+1−pipi−pi−1pi+1−pi−αmax,0.fα is called the turning penalty coefficient.


## 2.2.3.Jh Confirmation of Flight Altitude Cost

The fixed wing UAV fly below 2000 meters, and the main patrol altitude is about 200 meters.(4)Jh=fhmaxh,0.fh is called altitude the penalty coefficient.


## 2.2.4.Jthreat Determination of Threat Cost

Threat cost refers to the extent to which the fixed wing UAV is exposed to the threat of enemy detection radar, electromagnetic interference, and antiaircraft weapons during the flight process. The closer the fixed wing UAV to these targets, the more likely it is to be spotted and destroyed. For brief description, it is assumed that the cost of a threat at some point along the path is inversely proportional to the distance of the threat. Thus, threat cost function can be expressed as follows:(5)Jthreat=∑i=13∑k=0n−1fti,jkl/n.i=1, i=2, and i=3 represent the threat brought by enemy detection, electromagnetic interference, and antiaircraft weapons (antiaircraft missiles, antiaircraft guns, etc.), respectively. fti,jkl/n is the function of the distance between the path point and the threat point. It means that the path length from the beginning point to the end point is evenly divided into segments according to the number of path points set.


## 2.2.5.Jobstacle Determination the Cost of Obstacles

In the process of path planning, obstacles in two-dimensional space are generally treated as circular or elliptical objects, and obstacles in three-dimensional space are generally treated as spherical, ellipsoidal, or vertebral objects. This method can be easily described by the mathematical expression in terms of the real-time distance from the center of mass of the aircraft to the ball center of the obstacle and the radius of the spherical obstacle. Base on this, whether the aircraft collides with obstacles at the current time can be judged. The cost function of obstacles can be simply expressed as follows:(6)Jobstacle=fomaxd−R,0d=minpn−q.R is the radius of the obstacle, pn is any point on the surface of the obstacle, and q is the closest point between the surface of the obstacle and the position of the patrol bullet at the current time; fo is called obstacles penalty coefficient.


## 2.2.6.Jnofly Determination of Flight Forbidden Area Cost

The expression of cost function corresponding to the flight restricted area is similar to that of obstacle, which can be expressed simply by the following formula:(7)Jnofly=fnmaxd−r,0.fn is called forbidden penalty coefficient.


## 2.2.7.Jlast_angle Determination of the End Attack Angle Cost

When the fixed wing UAV fly to the target, if the scheme of fixed-direction attack is adopted, the probability of the target being destroyed is the largest, and the information obtained is the most. Besides, when the cooperative flight is in cooperation, the direction of attack can be set for each patrol bullet to achieve saturation attack in many aspects and improve the penetration probability.(8)Jlast_angle=flastmaxactanylast−ylast‐1xlast−xlast‐1−αmax−Δα,0.flast is the penalty coefficient corresponding to the deviation of the attack from the specified angle, and Δα is the size of the deviation of the attack direction angle.


## 2.3. Normalization of Performance Indicators

The performance indicators of the above seven cost functions differentiate in unit and orders of magnitude, even if the same unit may differentiate in large orders of magnitude, such as path length and altitude. This difference inevitably causes the result of flight path planning to be insensitive to the value of weight. Thus, it is critical to carry out 0-1 normalization for the performance indicators of the cost function.The key of 0-1 normalization is to find the maximum and minimum value of the corresponding index. The performance indicators of the above seven cost functions can be divided into two categories according to their units: one is distance-related indicators (range, height, threat, obstacle, and restricted area); the other is angle-related indicators (turning and terminal angle of attack). According to the constraint relation, these performance indicators can be divided into three categories: linear increasing form (maximum constraint), linear decreasing form (minimum constraint), and trapezoidal change form.The range, altitude, and turn belong to the category of linear increasing form, which can be represented as Figure1.
(9)y=0x≤a,M−Lx−ab−a+L,a<x<b,1x≥b.Figure 1
Linear increment.The obstacle and restricted flight area belong to the category of linear decreasing form, which is expressed as Figure2 follows:
(10)y=1x≤a,M−Lb−xb−a+L,a<x<b0x≥b.,Figure 2
Linear decline.The terminal attack angle belongs to the category of trapezoid change form, which can be expressed as Figure3 follows:
(11)y=0x≤aorx≥d,M−Lb−xb−a+La<x<b,1b≤x≤c,M−Ld−xd−c+Lc<x<d.Figure 3
Trapezoidal.


## 2.4. Selection of Weights

The weight of path planning is usually determined according to the experience or intentions of experts. The path planning contains seven attributes: range, turn, altitude, threat, obstacle, restricted area, and angle of terminal attack. Thus, the weight of path planning is expressed as follows:(12)ω1+ω2+ω3+ω4+ω5+ω6+ω7=1.


### 2.4.1. Build the Index Importance Judgment Matrix

Build the index importance judgment matrix and use “1-9 scale” to represent the importance of the index, as listed in Table1. Judgment criterion is as follows: set u1, u2.un for n teams. Every two teams play a match, and the total score of each match is 1 point. For ui and uj (i≠j), the scores of the two teams are, respectively, denoted as uij and uji, and the two scores should satisfyuij≥0, uij+uji=0 (i≠j).Table 1
Importance.
ValuesMeaning1Element A is as important as element B3Element A is slightly more important than element B5Element A is significantly more important than element B7Element A is more important than element B9Element A is extremely important than element B2, 4, 6, 8The median of the above importance


### 2.4.2. Score by Experts to Get the Judgment Matrix of Pairwise Importance Degree

The data in Table2 is converted according to the following formula, and the data listed in Table 3 was obtained.
(13)uij=kk+1aij=k,1k+1aij=1k,1aij=1,i≠j,0aij=1,i=j.Table 2
Comprehensive list of weight values.
ω1ω2ω3ω4ω5ω7ω1129546ω21/216324ω31/91/611/31/41/2ω41/51/3311/22ω51/41/24213ω71/61/421/21/31Table 3
Weight list after conversion.
ω1ω2ω3ω4ω5ω7ω102/39/105/64/56/7ω21/306/73/42/34/5ω31/101/701/41/51/3ω41/61/43/401/32/3ω51/51/34/52/303/4ω71/71/52/31/31/40Setω5=ω6. The reason for such values in Table 3 is that the influence of range, turn, obstacle, and forbidden area is first considered in the path planning of this study. Then, the influence of threat and terminal angle of attack is considered in the dynamic path planning.Obtain the normalized weight coefficient:(14)ωc=ωc1,ωc2,ωc3,ωc4,ωc5,ωc6,ωc7,ωci=2nn−1∑j=17uij,i=1,2,3,4,5,6,7,∑i7ωci=1.


## 2.4.1. Build the Index Importance Judgment Matrix

Build the index importance judgment matrix and use “1-9 scale” to represent the importance of the index, as listed in Table1. Judgment criterion is as follows: set u1, u2.un for n teams. Every two teams play a match, and the total score of each match is 1 point. For ui and uj (i≠j), the scores of the two teams are, respectively, denoted as uij and uji, and the two scores should satisfyuij≥0, uij+uji=0 (i≠j).Table 1
Importance.
ValuesMeaning1Element A is as important as element B3Element A is slightly more important than element B5Element A is significantly more important than element B7Element A is more important than element B9Element A is extremely important than element B2, 4, 6, 8The median of the above importance


## 2.4.2. Score by Experts to Get the Judgment Matrix of Pairwise Importance Degree

The data in Table2 is converted according to the following formula, and the data listed in Table 3 was obtained.
(13)uij=kk+1aij=k,1k+1aij=1k,1aij=1,i≠j,0aij=1,i=j.Table 2
Comprehensive list of weight values.
ω1ω2ω3ω4ω5ω7ω1129546ω21/216324ω31/91/611/31/41/2ω41/51/3311/22ω51/41/24213ω71/61/421/21/31Table 3
Weight list after conversion.
ω1ω2ω3ω4ω5ω7ω102/39/105/64/56/7ω21/306/73/42/34/5ω31/101/701/41/51/3ω41/61/43/401/32/3ω51/51/34/52/303/4ω71/71/52/31/31/40Setω5=ω6. The reason for such values in Table 3 is that the influence of range, turn, obstacle, and forbidden area is first considered in the path planning of this study. Then, the influence of threat and terminal angle of attack is considered in the dynamic path planning.Obtain the normalized weight coefficient:(14)ωc=ωc1,ωc2,ωc3,ωc4,ωc5,ωc6,ωc7,ωci=2nn−1∑j=17uij,i=1,2,3,4,5,6,7,∑i7ωci=1.


## 3. ACA Hybrid Algorithm

### 3.1. Ant Colony Algorithm Model

Ant colony algorithm, also known as ant algorithm, is a probability optimization simulated evolutionary algorithm [24]. With the development of many years, a variety of improved algorithms have been derived from the basic algorithm. For example, the transition probability formula of ant colony optimization algorithm can be expressed as follows:
(15)Pabnt=τabαηabβ∑b∈Sanτabαηabβb∈San0others.Among them,Pabnt represents the probability of ant n transferring from node a to node b at time t, τab is the pheromone concentration on the node b, ηab is the heuristic function between the current position a of the aircraft and the target position b, αβ is the weight of relative importance of τab and ηab, and San is the set of all adjacent nodes of node a. Among them, because pheromones are volatile, the local pheromone information update model in the study is as follows:
(16)τabt+1=ξτabt.ξ is a pheromone reduction factor, which is used to control the size of pheromone reduction. The global pheromone update model is as follows:
(17)τabt+m=1−ρτabt+ρΔτab,(18)Δτab=Q/J,whereρ is the pheromone volatilization factor, J is the performance index of this path, and Q is the proportion coefficient of performance index to pheromone update. For the heuristic functionηab, the potential field ant colony fusion algorithm is used to generate a new heuristic function ηab.
(19)ηabt=1/da,b.It can be seen from formula (18) that this heuristic function is only related to the distance between a and B. its disadvantage is that when there are obstacles in the environment, it cannot quickly find the best path.


### 3.2. Improvement of Artificial Potential Field Algorithm

The artificial potential field method is a typical path planning algorithm. The basic idea is that the environment around the patrol bullet has a mixed force field of gravity and repulsion to make the aircraft move towards the target. When the aircraft approaches the obstacle, it will generate strong repulsion, so as to effectively avoid the obstacle [30–32]. At any time, the gravitational field function and repulsive potential field function are, respectively, expressed as follows:
(20)Fatt=12kadab2,(21)Frepia=12krepi1dao−1d02dabndao<d00others.ka is the gravitational coefficient, krep is the repulsion coefficient, i is the number of obstacles near the aircraft in the environment, dao is the distance from the obstacle, and d0 is the influence range of the repulsion field of the obstacle.Then at any time, the resultant force on the aircraft is expressed as follows:(22)Fa=gradUa=kadab+n2krep1dao−1d0ndabn−1dao<d0,kadabdao≥d0.However, the basic artificial potential field method has the following defects [33–35].As the aircraft gets closer and closer to the target, and the aircraft, obstacles, and targets form three points and one line, or multiple obstacles are scattered around targets of different shapes, the repulsive force generated by obstacles gradually tends to the attraction generated by the target, and the attraction generated by the target becomes smaller and smaller, gradually reaching a balanced state. At this time, the equilibrium potential field point is the minimum value of the potential field. When the aircraft falls into a local minimum, the bullet will stay at a certain point or vibrate back and forth in a small range, unable to search the path normally, resulting in failure [36–39].At this time, the basic artificial potential field method needs to be improved: a weight adjustment escape method is designed.(23)Fa=ς1Fatta+ς2Freqia.The basic idea is to set the distance thresholdl between the aircraft and the target. When dao=xb−xo≥l is detected, make ς1=1, ς2=1; when dao=xb−xo≤l, in order to prevent from falling into the minimum value and keep ς2=1 constant, ς1 gradually increases with the decrease of the distance between the aircraft and the target and minimizes the total potential energy when the bullet reaches the target point. In order to speed up the escape speed, ς2 can also be reduced and ς1 increased at dao=xb−xo≤l .


### 3.3. ACA Hybrid Algorithm

A new heuristic coefficient under the action of improved potential field is introduced(24)ηFt=pFcosθP is a positive number, F is the resultant force received by the aircraft at any time, and θ is the angle between the resultant force direction of the potential field and the direction to reach the position at the next time. When the value of θ is smaller, the larger ηF is, the easier it is for the aircraft to fly in this direction.When the aircraft is far away from the target, the heuristic pheromone concentration of ant colony algorithm is relatively small. It can be seen from formula (18) that the information heuristic effect is also weak. According to the principle of ant colony algorithm, it will lead to the failure of path planning. At this time, it is necessary to play the role of potential field information. When the distance between the aircraft and the target is relatively close, the pheromone concentration increases, and the heuristic effect is also significantly enhanced. At this time, it is necessary to reduce the effect of potential field information accordingly. At this time, the control factor can be introduced by adjusting the resultant force of the potential field λ:
(25)λ=d−dabd.d is a fixed value larger than dab, and λ will gradually decrease as the aircraft moves towards the target.
(26)besidesλ=Nmax−NmNmax.Then, the heuristic function of the mixed pheromone is defined as follows:(27)η′abt=ηFtηabt=pFcosθdab⋅Nmax−NmNmax,whereNmax is the maximum number of iterations, and Nm is the current number of iterations. With the increase of the number of iterations, λ gradually decreases. However, if λ is small to a certain extent, the adjusted information heuristic function will be reduced, and the effect of positive feedback will not be obvious again. Therefore, the control factor must be limited, and the minimum value of a must be set to 0.2. Therefore, in the global information update model, the improved transfer probability formula can be expressed as follows:
(28)Pabnt=1−ρτab+ρω/Jαηab⋅ηFβ∑b∈San1−ρτab+ρω/Jαηab⋅ηFβb∈San0others.The outstanding advantages of the hybrid algorithm ACA of intelligent ant colony and artificial potential field method are shown in the following aspects:(1)
In the artificial potential field method, set the obstacle as repulsive force and the target as attractive force, add the force vectors, and finally calculate the direction of the resultant force. The range of gravitational potential field is relatively large, while the action range of repulsive force is only local. When the distance between aircraft and obstacles exceeds the influence range of obstacles, it will not be affected by the repulsive potential field. Therefore, the potential field method can only solve the obstacle avoidance problem in local space. It lacks global information and is easy to fall into the local minimum. Moreover, when there are obstacles near the target, the repulsion force will be very large, which makes it difficult for the aircraft to fly the target and cause the problem of local oscillation(2)
Ant colony algorithm transmits information by releasing a hormone called pheromone in the environment. In theory, it can finally make all ants choose the same path. It is a self-organizing and parallel computing positive feedback distributed intelligent algorithm. Positive feedback can quickly find better solutions, but the heuristic information is relatively small at a long distance. It may lead to a certain blindness in the path selection of aircraft. After a certain number of iterations, it is easy to stop the search and fall into local optimization(3)
The hybrid algorithm of ant colony and artificial potential field is adopted to guide the aircraft in two aspects: one is the pheromone guidance in the ant colony algorithm, and the other is the guidance of gravity and repulsion of artificial potential field. Through the adjustment factor introduced above, when the distance from the target is far and the heuristic information is not obvious, the potential field effect is appropriately increased. At a close distance, the heuristic information is increased, and the positive feedback effect is obvious. The potential field effect is appropriately reduced, which avoids the problem that the aircraft cannot reach the target because the repulsion force may be much greater than the gravity when the obstacle is close to the target. Therefore, the ACA hybrid algorithm not only gives full play to the path search mechanism of ant colony algorithm but also gives full play to the advantage that artificial potential field can effectively avoid obstacles. It overcomes the problem that the information inspiration of the ant colony algorithm is not strong, and the target cannot be reached at close distance. The strong and strong combine to find a path from the starting point and target point


## 3.1. Ant Colony Algorithm Model

Ant colony algorithm, also known as ant algorithm, is a probability optimization simulated evolutionary algorithm [24]. With the development of many years, a variety of improved algorithms have been derived from the basic algorithm. For example, the transition probability formula of ant colony optimization algorithm can be expressed as follows:
(15)Pabnt=τabαηabβ∑b∈Sanτabαηabβb∈San0others.Among them,Pabnt represents the probability of ant n transferring from node a to node b at time t, τab is the pheromone concentration on the node b, ηab is the heuristic function between the current position a of the aircraft and the target position b, αβ is the weight of relative importance of τab and ηab, and San is the set of all adjacent nodes of node a. Among them, because pheromones are volatile, the local pheromone information update model in the study is as follows:
(16)τabt+1=ξτabt.ξ is a pheromone reduction factor, which is used to control the size of pheromone reduction. The global pheromone update model is as follows:
(17)τabt+m=1−ρτabt+ρΔτab,(18)Δτab=Q/J,whereρ is the pheromone volatilization factor, J is the performance index of this path, and Q is the proportion coefficient of performance index to pheromone update. For the heuristic functionηab, the potential field ant colony fusion algorithm is used to generate a new heuristic function ηab.
(19)ηabt=1/da,b.It can be seen from formula (18) that this heuristic function is only related to the distance between a and B. its disadvantage is that when there are obstacles in the environment, it cannot quickly find the best path.


## 3.2. Improvement of Artificial Potential Field Algorithm

The artificial potential field method is a typical path planning algorithm. The basic idea is that the environment around the patrol bullet has a mixed force field of gravity and repulsion to make the aircraft move towards the target. When the aircraft approaches the obstacle, it will generate strong repulsion, so as to effectively avoid the obstacle [30–32]. At any time, the gravitational field function and repulsive potential field function are, respectively, expressed as follows:
(20)Fatt=12kadab2,(21)Frepia=12krepi1dao−1d02dabndao<d00others.ka is the gravitational coefficient, krep is the repulsion coefficient, i is the number of obstacles near the aircraft in the environment, dao is the distance from the obstacle, and d0 is the influence range of the repulsion field of the obstacle.Then at any time, the resultant force on the aircraft is expressed as follows:(22)Fa=gradUa=kadab+n2krep1dao−1d0ndabn−1dao<d0,kadabdao≥d0.However, the basic artificial potential field method has the following defects [33–35].As the aircraft gets closer and closer to the target, and the aircraft, obstacles, and targets form three points and one line, or multiple obstacles are scattered around targets of different shapes, the repulsive force generated by obstacles gradually tends to the attraction generated by the target, and the attraction generated by the target becomes smaller and smaller, gradually reaching a balanced state. At this time, the equilibrium potential field point is the minimum value of the potential field. When the aircraft falls into a local minimum, the bullet will stay at a certain point or vibrate back and forth in a small range, unable to search the path normally, resulting in failure [36–39].At this time, the basic artificial potential field method needs to be improved: a weight adjustment escape method is designed.(23)Fa=ς1Fatta+ς2Freqia.The basic idea is to set the distance thresholdl between the aircraft and the target. When dao=xb−xo≥l is detected, make ς1=1, ς2=1; when dao=xb−xo≤l, in order to prevent from falling into the minimum value and keep ς2=1 constant, ς1 gradually increases with the decrease of the distance between the aircraft and the target and minimizes the total potential energy when the bullet reaches the target point. In order to speed up the escape speed, ς2 can also be reduced and ς1 increased at dao=xb−xo≤l .


## 3.3. ACA Hybrid Algorithm

A new heuristic coefficient under the action of improved potential field is introduced(24)ηFt=pFcosθP is a positive number, F is the resultant force received by the aircraft at any time, and θ is the angle between the resultant force direction of the potential field and the direction to reach the position at the next time. When the value of θ is smaller, the larger ηF is, the easier it is for the aircraft to fly in this direction.When the aircraft is far away from the target, the heuristic pheromone concentration of ant colony algorithm is relatively small. It can be seen from formula (18) that the information heuristic effect is also weak. According to the principle of ant colony algorithm, it will lead to the failure of path planning. At this time, it is necessary to play the role of potential field information. When the distance between the aircraft and the target is relatively close, the pheromone concentration increases, and the heuristic effect is also significantly enhanced. At this time, it is necessary to reduce the effect of potential field information accordingly. At this time, the control factor can be introduced by adjusting the resultant force of the potential field λ:
(25)λ=d−dabd.d is a fixed value larger than dab, and λ will gradually decrease as the aircraft moves towards the target.
(26)besidesλ=Nmax−NmNmax.Then, the heuristic function of the mixed pheromone is defined as follows:(27)η′abt=ηFtηabt=pFcosθdab⋅Nmax−NmNmax,whereNmax is the maximum number of iterations, and Nm is the current number of iterations. With the increase of the number of iterations, λ gradually decreases. However, if λ is small to a certain extent, the adjusted information heuristic function will be reduced, and the effect of positive feedback will not be obvious again. Therefore, the control factor must be limited, and the minimum value of a must be set to 0.2. Therefore, in the global information update model, the improved transfer probability formula can be expressed as follows:
(28)Pabnt=1−ρτab+ρω/Jαηab⋅ηFβ∑b∈San1−ρτab+ρω/Jαηab⋅ηFβb∈San0others.The outstanding advantages of the hybrid algorithm ACA of intelligent ant colony and artificial potential field method are shown in the following aspects:(1)
In the artificial potential field method, set the obstacle as repulsive force and the target as attractive force, add the force vectors, and finally calculate the direction of the resultant force. The range of gravitational potential field is relatively large, while the action range of repulsive force is only local. When the distance between aircraft and obstacles exceeds the influence range of obstacles, it will not be affected by the repulsive potential field. Therefore, the potential field method can only solve the obstacle avoidance problem in local space. It lacks global information and is easy to fall into the local minimum. Moreover, when there are obstacles near the target, the repulsion force will be very large, which makes it difficult for the aircraft to fly the target and cause the problem of local oscillation(2)
Ant colony algorithm transmits information by releasing a hormone called pheromone in the environment. In theory, it can finally make all ants choose the same path. It is a self-organizing and parallel computing positive feedback distributed intelligent algorithm. Positive feedback can quickly find better solutions, but the heuristic information is relatively small at a long distance. It may lead to a certain blindness in the path selection of aircraft. After a certain number of iterations, it is easy to stop the search and fall into local optimization(3)
The hybrid algorithm of ant colony and artificial potential field is adopted to guide the aircraft in two aspects: one is the pheromone guidance in the ant colony algorithm, and the other is the guidance of gravity and repulsion of artificial potential field. Through the adjustment factor introduced above, when the distance from the target is far and the heuristic information is not obvious, the potential field effect is appropriately increased. At a close distance, the heuristic information is increased, and the positive feedback effect is obvious. The potential field effect is appropriately reduced, which avoids the problem that the aircraft cannot reach the target because the repulsion force may be much greater than the gravity when the obstacle is close to the target. Therefore, the ACA hybrid algorithm not only gives full play to the path search mechanism of ant colony algorithm but also gives full play to the advantage that artificial potential field can effectively avoid obstacles. It overcomes the problem that the information inspiration of the ant colony algorithm is not strong, and the target cannot be reached at close distance. The strong and strong combine to find a path from the starting point and target point


## 4. Simulation and Analysis of the Hybrid Algorithm

### 4.1. Environment Set in 2D

Within the 20∗ 20 operational airspace, the rectangle represents the obstacle, the loop represents the forbidden area, the U-shape represents the threat near the target, the starting point is set at (0, 20), and the target point is (20, 0). The maximum number of iterationsNmax=100, information concentration weight α=1, heuristic function weight β=2, pheromone volatilization factor ρ=0.2, gravity coefficient ka=10, repulsion coefficient krep=10, repulsion field influence range d0=2 of obstacles, and penalty coefficient in path cost shall be set according to the actual situation, and normalization index shall be set according to the results in Table 4.Table 4
Weight normalization coefficient.
ω1ω2ω3ω4ω5ω6ω7Normalization coefficient0.240.200.060.130.140.140.09


### 4.2. Simulation Analysis

By comparing the (a) diagram of ant colony algorithm and hybrid algorithm in Figures4 and 5, the hybrid algorithm not only gives full play to the search mechanism of ant colony algorithm but also realizes the effective obstacle avoidance of various obstacles in the flight process. Moreover, under the same obstacle setting conditions, the number of inflection points is 11 and 9, respectively, and the smoothness of the hybrid algorithm is relatively good. Through the comparison of Figure 6, it can be seen that the number of iterations and minimum path cost of the hybrid algorithm are significantly reduced. Although the iteration times and minimum path cost of the hybrid algorithm are significantly improved, it is impossible to have a large turning angle in the actual flight process of the aircraft; so, the path needs to be further optimized. The optimized results are shown in the red line in Figure 5(a), which significantly improves the smoothness of the generated path. Therefore, it can be proved that the ant colony potential field hybrid algorithm used in this study is feasible.Figure 4
Simulation results of the ant colony algorithm.
(a)
Ant group algorithm(b)
Minimum path cost and number of iterations of the ant colony algorithmFigure 5
Ant potential field mixing algorithm.
(a)
The ACA motion trajectories(b)
Minimum path cost and number of iterations of the ACA algorithmFigure 6
Comparison of minimum path cost and number of iterations.


### 4.3. Environment Set in 3D

In the 3D space, the obstacles adopt a cone. In the operational airspace with area of20km×20km, the following assumptions are made: the target point coordinates fall within the range (5 km, -5 km), and the starting point coordinates is (0, 0); the flight range is 30 km, and the flight speed is 35 m/s; the maximum flight altitude is less than 2000 m, and the flight altitude is 200 m (from the ground); the maximum horizontal turning angle is 30°, and the maximum climbing angle is 45°.


### 4.4. Simulation Analysis

When the start position remains unchanged and the end position changes, the best generation value and path planning curve are shown in Figures7–9.Figure 7
End one: the best generation value and path planning curve.
(a)
The best generation value(b)
Variation curve of the best individual fitnessFigure 8
End two: the best generation value and path planning curve.
(a)
The best generation value(b)
Variation curve of the best individual fitnessFigure 9
End three: the best generation value and path planning curve.
(a)
The best generation value(b)
Variation curve of the best individual fitnessIt can be seen from the simulation results in Figures7–9 that the number of iterations of the hybrid algorithm is below 40, and most of them are around 20. This indicates that the ACA hybrid algorithm can quickly converge. When the UAV encounters an obstacle (forbidden area), it can quickly avoid the obstacle and fly to the target based on the potential field repulsion in the algorithm. Tables 5–7 are designed to make the simulation data more general. Specifically, to obtain the average maximum and best cost values, ten groups of maximum and optimal generation values at different times are randomly selected for statistics. In the same case, compared with Figures 10 and 11, the number of iterations is set to 20 to ensure real-time. At this point, the cost of using the ACA hybrid algorithm is obviously less than that of using the ant colony algorithm only. And the convergence speed of the ACA hybrid algorithm is obviously better than that of the ant colony algorithm only.Table 5
Statistics of cost and optimal cost at different times.
Cost220.65398.6974128.938114.295153.915115.3311143.602105.381141.896152.288Optimal cost85.865382.415688.861983.825278.492890.801489.720887.549587.616493.1170Average cost137.4998Best average cost86.82659Table 6
Statistics of cost and optimal cost at different times.
Cost100.5781176.443100.129123.690139.552235.435115.641185.556209.204194.886Optimal cost82.887994.1285123.242393.303492.962987.036792.982289.621184.555385.9058Average cost158.1119Best average cost92.66261Table 7
Statistics of cost and optimal cost at different times.
Cost160.1367123.558136.408168.111114.335153.308129.717137.771241.905114.695Optimal cost85.616488.155786.704884.264783.823384.121587.456689.972082.557884.4142Average cost147.9948Best average cost85.7087Figure 10
The relationship between the optimal fitness function and the number of iterations in the ACA hybrid algorithm.Figure 11
The relationship between the optimal fitness function and the number of iterations in only ant colony algorithm.


## 4.1. Environment Set in 2D

Within the 20∗ 20 operational airspace, the rectangle represents the obstacle, the loop represents the forbidden area, the U-shape represents the threat near the target, the starting point is set at (0, 20), and the target point is (20, 0). The maximum number of iterationsNmax=100, information concentration weight α=1, heuristic function weight β=2, pheromone volatilization factor ρ=0.2, gravity coefficient ka=10, repulsion coefficient krep=10, repulsion field influence range d0=2 of obstacles, and penalty coefficient in path cost shall be set according to the actual situation, and normalization index shall be set according to the results in Table 4.Table 4
Weight normalization coefficient.
ω1ω2ω3ω4ω5ω6ω7Normalization coefficient0.240.200.060.130.140.140.09


## 4.2. Simulation Analysis

By comparing the (a) diagram of ant colony algorithm and hybrid algorithm in Figures4 and 5, the hybrid algorithm not only gives full play to the search mechanism of ant colony algorithm but also realizes the effective obstacle avoidance of various obstacles in the flight process. Moreover, under the same obstacle setting conditions, the number of inflection points is 11 and 9, respectively, and the smoothness of the hybrid algorithm is relatively good. Through the comparison of Figure 6, it can be seen that the number of iterations and minimum path cost of the hybrid algorithm are significantly reduced. Although the iteration times and minimum path cost of the hybrid algorithm are significantly improved, it is impossible to have a large turning angle in the actual flight process of the aircraft; so, the path needs to be further optimized. The optimized results are shown in the red line in Figure 5(a), which significantly improves the smoothness of the generated path. Therefore, it can be proved that the ant colony potential field hybrid algorithm used in this study is feasible.Figure 4
Simulation results of the ant colony algorithm.
(a)
Ant group algorithm(b)
Minimum path cost and number of iterations of the ant colony algorithmFigure 5
Ant potential field mixing algorithm.
(a)
The ACA motion trajectories(b)
Minimum path cost and number of iterations of the ACA algorithmFigure 6
Comparison of minimum path cost and number of iterations.


## 4.3. Environment Set in 3D

In the 3D space, the obstacles adopt a cone. In the operational airspace with area of20km×20km, the following assumptions are made: the target point coordinates fall within the range (5 km, -5 km), and the starting point coordinates is (0, 0); the flight range is 30 km, and the flight speed is 35 m/s; the maximum flight altitude is less than 2000 m, and the flight altitude is 200 m (from the ground); the maximum horizontal turning angle is 30°, and the maximum climbing angle is 45°.


## 4.4. Simulation Analysis

When the start position remains unchanged and the end position changes, the best generation value and path planning curve are shown in Figures7–9.Figure 7
End one: the best generation value and path planning curve.
(a)
The best generation value(b)
Variation curve of the best individual fitnessFigure 8
End two: the best generation value and path planning curve.
(a)
The best generation value(b)
Variation curve of the best individual fitnessFigure 9
End three: the best generation value and path planning curve.
(a)
The best generation value(b)
Variation curve of the best individual fitnessIt can be seen from the simulation results in Figures7–9 that the number of iterations of the hybrid algorithm is below 40, and most of them are around 20. This indicates that the ACA hybrid algorithm can quickly converge. When the UAV encounters an obstacle (forbidden area), it can quickly avoid the obstacle and fly to the target based on the potential field repulsion in the algorithm. Tables 5–7 are designed to make the simulation data more general. Specifically, to obtain the average maximum and best cost values, ten groups of maximum and optimal generation values at different times are randomly selected for statistics. In the same case, compared with Figures 10 and 11, the number of iterations is set to 20 to ensure real-time. At this point, the cost of using the ACA hybrid algorithm is obviously less than that of using the ant colony algorithm only. And the convergence speed of the ACA hybrid algorithm is obviously better than that of the ant colony algorithm only.Table 5
Statistics of cost and optimal cost at different times.
Cost220.65398.6974128.938114.295153.915115.3311143.602105.381141.896152.288Optimal cost85.865382.415688.861983.825278.492890.801489.720887.549587.616493.1170Average cost137.4998Best average cost86.82659Table 6
Statistics of cost and optimal cost at different times.
Cost100.5781176.443100.129123.690139.552235.435115.641185.556209.204194.886Optimal cost82.887994.1285123.242393.303492.962987.036792.982289.621184.555385.9058Average cost158.1119Best average cost92.66261Table 7
Statistics of cost and optimal cost at different times.
Cost160.1367123.558136.408168.111114.335153.308129.717137.771241.905114.695Optimal cost85.616488.155786.704884.264783.823384.121587.456689.972082.557884.4142Average cost147.9948Best average cost85.7087Figure 10
The relationship between the optimal fitness function and the number of iterations in the ACA hybrid algorithm.Figure 11
The relationship between the optimal fitness function and the number of iterations in only ant colony algorithm.


## 5. Conclusion

Aiming at the complex problem of multiple constraints in path planning, based on the analysis of the research status, three problems are mainly solved: first, combined with the reality of this research, comprehensively refine the path cost function, construct a cost model containing seven cost indexes, and give the expression of each cost index. Second, in view of the inconsistency of cost index units and measures, the expert scoring method is used to configure the weight importance of each cost function to obtain the normalized weight coefficient. Third, based on the ant colony optimization algorithm, a new heuristic function is constructed by using the hybrid algorithm ACA, and the control factor is introduced to make the algorithm give full play to the global search mechanism of ant colony algorithm and the local obstacle avoidance advantage of artificial potential field method in the whole process. Finally, the hybrid algorithm is simulated in a 2D and 3D area including obstacles, restricted areas, and threats. Through the comparison between ant colony algorithm and hybrid algorithm in terms of trajectory, iteration times, and minimum path cost, the hybrid algorithm has smooth path, low path cost, and fast convergence speed, which solves the rapid convergence of path planning in complex environment and practical application of fast obstacle avoidance.



---

*Source: 8406307-2022-06-08.xml*