# An Improved Heuristic Algorithm for UCAV Path Planning

Authors: Kun Zhang; Peipei Liu; Weiren Kong; Jie Zou; Min Liu
Journal: Journal of Optimization
 (2017)

---

## Abstract

The study of unmanned combat aerial vehicle (UCAV) path planning is increasingly important in military and civil field. This paper presents a new mathematical model and an improved heuristic algorithm based on SparseA⁎ Search (SAS) for UCAV path planning problem. In this paper, flight constrained conditions will be considered to meet the flight restrictions and task demands. With three simulations, the impacts of the model on the algorithms will be investigated, and the effectiveness and the advantages of the model and algorithm will be validated.


---

## Body

## 1. Introduction

Nowadays, unmanned combat aerial vehicle (UCAV) has long been a challenging area for researchers in military and civil field. Path planning is defined as looking for the optimal path of moving objects from the start point to the target point under specific constraints (including environmental constraint and movement constraint) [1]. The path planning aims to find the path with the highest survival rate, lower loss, and shorter period of time. Currently, the path planning problem has been widely used in different areas such as cruise missile, helicopter, and UCAV. In modern warfare, with the development of various air defense technologies, there is no doubt that the path planning problem is more and more being paid attention to in military field. Numerous scholars study the path planning problem constantly. The represented techniques of UCAV path planning are like PSO [1, 2], dynamic planning [3], A∗ algorithm [4, 5], ant colony algorithm [6], genetic algorithm [7, 8], and so on [9–13]. Reference [14] discussed sparse algorithm, another effective way, which greatly improves the efficiency of the search, but it is easy to fall into a death cycle under the conditions of lacking maneuver ability. Reference [5] adopted sparse algorithm, but angle heuristic function is not taken into consideration and the number of constraint conditions is small; the simulation result is not scientific. Reference [7, 15] proposed the algorithms with large amount of calculation, making the algorithms unsuitable to seek optimization solution. To address these problems, an improved heuristic algorithm [16] is studied which takes angle information into account in a certain range, two methods of trajectory smooth straightening processing are adopted and compared, and the corresponding simulations are given in this paper.


## 2. Related Works

### 2.1. Basic Mathematical Model

The path planning problem of UCAV can be modeled as a constrained optimization problem. Before searching track, flight condition and elements (like terrain, threats, climate, etc.) of relevant path planning are represented as symbol information.Let(xL,yL,zL) be longitude, latitude, and height of a certain point in state space. The path planning space can be represented as a set: {xL,yL,zL∣0⩽xL⩽max⁡XL,  0⩽yL⩽max⁡YL,0⩽zL⩽max⁡ZL}, which represents a space district. In practical planning, the planning space is divided into two-dimensional grids or three-dimensional grids; a series of nodes are acquired and built into a network graph, as shown in Figure 1. The path planning problem can be simply attributed to a combinational optimization problem for getting the shortest path of the network graph. That is to say, when UCAV is flying along the path formed by some nodes of the network graph, a certain kind of path takes minimum cost.Figure 1
Network graph.Supposing the nodes of network graph form a setS(1)S=s1,s2,s3,…,sm.Define a set that includes all paths from the start point to the end point asE:(2)E=e1,e2,e3,…,en.Letsi and sj be two adjacent nodes on the path ek, the connecting line between two nodes can be expressed by V(si,sj), the cost value of the connecting line between two nodes can be expressed by uij, and the path planning problems of UCAV are defined as follows:(3)minfek=∑si,sj∈ekuijs.t.ek∈E,si∈S,sj∈S.As can be seen from the above content, the performance constraint of UCAV is not reflected in the planning. If the nodes in the network graph are feasible points which take performance constraint of UCAV into account, the path with the performance constraint of UCAV can be reflected from solving the above optimization problems. This is a new mathematical model. Compared with [5], our new mathematical model takes more constraints into account. And simulation result shows that it is highly useful for the approximate optimal solution. Besides, it is also good at processing path planning in complicated conditions.


### 2.2. Basic Constraint Conditions of Path Planning

There are many factors that influence the result of path planning. These factors, which include terrain features, threat locations, and mission requirements, are basic constraints in mathematical modeling. Path planning should meet basic constraints, and they mainly include the following constraints [4].Minimum Route Length. Aircraft generally does not want to weave and turn constantly, because this adds to fuel cost and increases navigational errors.Maximum Turning Angle. The turning angle of the aircraft does not exceed maximum turning angle. For instance, the aircraft cannot make severe turns without a greater risk of collision in formation fight.Route Distance Constraint. The length of the route does not exceed maximum distance because of fuel restriction.Specific Approaching Angle to Target Point. This constrains UCAV to approach the hostile aircraft from a predetermined angle to ensure UCAV defend the weak part.


### 2.3. Path Planning Cost

On the premise that some constraints are met, the UCAV path planning aims to generate trajectory with the highest survival rate. Therefore, threat locations in battle field should be fully taken into account. Threat factors and fuel restriction are mainly taken into account when calculating trajectory cost.


#### 2.3.1. Models of Threats

Threat Model of Radar. The factors that influence the probability of radar detection mainly include earth curvature, atmospheric refraction and absorption, ground clutter interference, distance between aircraft and radar, radar cross-section, radar performance, and ground multipath effect. For the sake of simplification, here we mainly take the distance from aircraft to radar and radar performance into account. Supposing the flying height is h, the horizontal distance from aircraft to radar is R, radar maximal horizontal range is Rmax, radar performance coefficient is k, the probabilistic model of radar detection can be presented as follows:(4)PR=e-kR2/h-R4/Rmax4. If a>0, the approximation expression e-a can be equivalent as follows:(5)e-a≈1a+1.If R<Rmax, aircraft is in the detection range of radar, and threat model can be simplified as follows:(6)PR=e-R4/Rmax4. Use formula (5) to get the approximation expression(7)PR≈Rmax4R4+Rmax4.If aircraft is out of the radar maximal horizontal range, threat for radar to aircraft is zero. Threat model of radar can be represented as follows:(8)PR=Rmax4R4+Rmax4R⩽Rmax0R>Rmax.Threat Model of Surface-to-Air Missile. Supposing probability distribution of missile to target obeys Poisson distribution concerning horizontal distance Rm, killing probability of maximum attack radius RMmax is e-1, and if Rm<RMmax, threat model for missile to aircraft can be presented as follows:(9)PM=e-Rm/RMmax.According to formula (5), the approximation expression can be equivalent as follows:(10)PM=RMmaxRm+RMmax.If aircraft is out of the maximum attack radius range, the threat for missile to aircraft is zero. Threat model of missile can be presented as follows:(11)PR=RMmaxRm+RMmaxRm⩽RMmax0Rm>RMmax.Threat Model of Terrain. The main danger caused by terrain is peaks, which may be an obstacle of flight when aircraft is flying at the fixed height. And peaks can be expressed as cones. Supposing the horizontal cross-section of the peak is a circumference at the flight height and the radius of circumference is Rd, the central position of the peak is (x,y), and the current position of aircraft is (xA,yA), the horizontal distance RAT from aircraft to the central of the peak can be expressed as follows:(12)RAT=xA-x2+yA-y2.Unlike several kinds of threats above, the collisions between the aircraft and peak are fatal risk for aircraft. Therefore, enough space and time must be maintained when the aircraft is bypassing the peak. Threat model of peaks can be presented as follows:(13)PT=0RAT>10Km+Rd1RAT⩽2Km+Rd1RAT2Km+Rd<RAT<10Km+Rd.Threat Model of Atrocious Weather. Similar to the threat of peak to aircraft, supposing that the radius of atrocious weather on the cross-section is Rc and horizontal distance from aircraft to the center of atrocious weather is RAW, mathematical model of atrocious weather can be presented as follows:(14)PW=0RAW>5Km+Rc1RAWRAW⩽5Km+Rc.


#### 2.3.2. Path Planning Cost Calculation Function

In this paper, the cost calculation function relates to threat cost and fuel cost. Because fuel cost is proportional to the voyage, the cost calculation function can be given as(15)J=∑i=1nwsli+wtfTAi,Ji=wsli+wtfTAi,where J is the total cost of the route, Ji is the ith route cost, li is the ith route length, it can decrease flight time of aircraft in enemy air defenses area by cutting down the total length of route, fTAi is the threat index of the ith route, it ensures the aircraft can fly along the safe area, and ws and wt are the weight coefficients of distance factors and threat factors, and ws+wt=1. Besides, they can be determined according to the specific requirements of route performance. For example, sometimes we need the minimum route, and sometimes the highest survival rate is required.The calculation of the threat index on theith route needs to be integrated along the ith route, for the sake of simplification, calculate average value of the threat index of certain points on the route, and then multiply the length of the influenced part. Divide route into m equal parts, select m break points on the route, and their positions can be expressed as(16)12mli,32mli,…,2n+12mlin=0,1,2,…,n<m.The threat index on the ith route is given by the expression(17)fTAi=1mli∑j=1NtfTAj12mli+fTAj32mli+⋯+fTAj2n+12mli,where Nt is the number of the known threat sources, li is the ith route length, fTAj is the threat value of the break points, the value of m can be adjusted according to the computational accuracy and the route length. According to different threat classifications, it can be calculated by formulas (8); (11); (13); (14).


### 2.4. SparseA∗ Algorithm

Heuristic search [17] aims to use heuristic information to find the optimal path with the minimum cost. The main difference between heuristic search and other methods is that the cost information is related to heuristic information. The cost calculation function of heuristic search is given as(18)fx=Jx+hx,where x is the extended node, J(x) is the actual cost from the start node to the extended node, and h(x) is the estimate cost from the extended node to the target node. According to different task demands, heuristic information may involve many factors such as ground threat sources, artificial obstacles, flight time, and fuel quantity. An appropriate heuristic function can greatly increase search speed and acquire the solution easily.The primary problem to be solved is how to acquire the candidate node set in the search process. The expression of nodes in state space can be divided into two general types: nodes of graphic expression and nodes of grid expression. The former extends nodes out in the form of ray; the latter divides state space into grids with a certain size and then extends the adjacent grid points out. For example, basicA∗ is based on grid search. Nodes can be divided into three states in heuristic search:(1)
Nodes have been extended.(2)
Nodes have been generated but has not been extended.(3)
Nodes have not been generated.The first kind of nodes is called closed nodes, and we can construct a table namedCLOSED to store this kind of nodes; the second kind of nodes is called open nodes because the nodes has been generated but has not been extended, such nodes can be stored in a table namedOPEN. The start nodes are stored inOPEN table in the initial search. New nodes can be generated according to different extensible rules, and then these new nodes are inserted intoOPEN table according to the increment of the cost value f, the node with the smallest value can be preferentially extended, and it can be stored inCLOSED table.


## 2.1. Basic Mathematical Model

The path planning problem of UCAV can be modeled as a constrained optimization problem. Before searching track, flight condition and elements (like terrain, threats, climate, etc.) of relevant path planning are represented as symbol information.Let(xL,yL,zL) be longitude, latitude, and height of a certain point in state space. The path planning space can be represented as a set: {xL,yL,zL∣0⩽xL⩽max⁡XL,  0⩽yL⩽max⁡YL,0⩽zL⩽max⁡ZL}, which represents a space district. In practical planning, the planning space is divided into two-dimensional grids or three-dimensional grids; a series of nodes are acquired and built into a network graph, as shown in Figure 1. The path planning problem can be simply attributed to a combinational optimization problem for getting the shortest path of the network graph. That is to say, when UCAV is flying along the path formed by some nodes of the network graph, a certain kind of path takes minimum cost.Figure 1
Network graph.Supposing the nodes of network graph form a setS(1)S=s1,s2,s3,…,sm.Define a set that includes all paths from the start point to the end point asE:(2)E=e1,e2,e3,…,en.Letsi and sj be two adjacent nodes on the path ek, the connecting line between two nodes can be expressed by V(si,sj), the cost value of the connecting line between two nodes can be expressed by uij, and the path planning problems of UCAV are defined as follows:(3)minfek=∑si,sj∈ekuijs.t.ek∈E,si∈S,sj∈S.As can be seen from the above content, the performance constraint of UCAV is not reflected in the planning. If the nodes in the network graph are feasible points which take performance constraint of UCAV into account, the path with the performance constraint of UCAV can be reflected from solving the above optimization problems. This is a new mathematical model. Compared with [5], our new mathematical model takes more constraints into account. And simulation result shows that it is highly useful for the approximate optimal solution. Besides, it is also good at processing path planning in complicated conditions.


## 2.2. Basic Constraint Conditions of Path Planning

There are many factors that influence the result of path planning. These factors, which include terrain features, threat locations, and mission requirements, are basic constraints in mathematical modeling. Path planning should meet basic constraints, and they mainly include the following constraints [4].Minimum Route Length. Aircraft generally does not want to weave and turn constantly, because this adds to fuel cost and increases navigational errors.Maximum Turning Angle. The turning angle of the aircraft does not exceed maximum turning angle. For instance, the aircraft cannot make severe turns without a greater risk of collision in formation fight.Route Distance Constraint. The length of the route does not exceed maximum distance because of fuel restriction.Specific Approaching Angle to Target Point. This constrains UCAV to approach the hostile aircraft from a predetermined angle to ensure UCAV defend the weak part.


## 2.3. Path Planning Cost

On the premise that some constraints are met, the UCAV path planning aims to generate trajectory with the highest survival rate. Therefore, threat locations in battle field should be fully taken into account. Threat factors and fuel restriction are mainly taken into account when calculating trajectory cost.


### 2.3.1. Models of Threats

Threat Model of Radar. The factors that influence the probability of radar detection mainly include earth curvature, atmospheric refraction and absorption, ground clutter interference, distance between aircraft and radar, radar cross-section, radar performance, and ground multipath effect. For the sake of simplification, here we mainly take the distance from aircraft to radar and radar performance into account. Supposing the flying height is h, the horizontal distance from aircraft to radar is R, radar maximal horizontal range is Rmax, radar performance coefficient is k, the probabilistic model of radar detection can be presented as follows:(4)PR=e-kR2/h-R4/Rmax4. If a>0, the approximation expression e-a can be equivalent as follows:(5)e-a≈1a+1.If R<Rmax, aircraft is in the detection range of radar, and threat model can be simplified as follows:(6)PR=e-R4/Rmax4. Use formula (5) to get the approximation expression(7)PR≈Rmax4R4+Rmax4.If aircraft is out of the radar maximal horizontal range, threat for radar to aircraft is zero. Threat model of radar can be represented as follows:(8)PR=Rmax4R4+Rmax4R⩽Rmax0R>Rmax.Threat Model of Surface-to-Air Missile. Supposing probability distribution of missile to target obeys Poisson distribution concerning horizontal distance Rm, killing probability of maximum attack radius RMmax is e-1, and if Rm<RMmax, threat model for missile to aircraft can be presented as follows:(9)PM=e-Rm/RMmax.According to formula (5), the approximation expression can be equivalent as follows:(10)PM=RMmaxRm+RMmax.If aircraft is out of the maximum attack radius range, the threat for missile to aircraft is zero. Threat model of missile can be presented as follows:(11)PR=RMmaxRm+RMmaxRm⩽RMmax0Rm>RMmax.Threat Model of Terrain. The main danger caused by terrain is peaks, which may be an obstacle of flight when aircraft is flying at the fixed height. And peaks can be expressed as cones. Supposing the horizontal cross-section of the peak is a circumference at the flight height and the radius of circumference is Rd, the central position of the peak is (x,y), and the current position of aircraft is (xA,yA), the horizontal distance RAT from aircraft to the central of the peak can be expressed as follows:(12)RAT=xA-x2+yA-y2.Unlike several kinds of threats above, the collisions between the aircraft and peak are fatal risk for aircraft. Therefore, enough space and time must be maintained when the aircraft is bypassing the peak. Threat model of peaks can be presented as follows:(13)PT=0RAT>10Km+Rd1RAT⩽2Km+Rd1RAT2Km+Rd<RAT<10Km+Rd.Threat Model of Atrocious Weather. Similar to the threat of peak to aircraft, supposing that the radius of atrocious weather on the cross-section is Rc and horizontal distance from aircraft to the center of atrocious weather is RAW, mathematical model of atrocious weather can be presented as follows:(14)PW=0RAW>5Km+Rc1RAWRAW⩽5Km+Rc.


### 2.3.2. Path Planning Cost Calculation Function

In this paper, the cost calculation function relates to threat cost and fuel cost. Because fuel cost is proportional to the voyage, the cost calculation function can be given as(15)J=∑i=1nwsli+wtfTAi,Ji=wsli+wtfTAi,where J is the total cost of the route, Ji is the ith route cost, li is the ith route length, it can decrease flight time of aircraft in enemy air defenses area by cutting down the total length of route, fTAi is the threat index of the ith route, it ensures the aircraft can fly along the safe area, and ws and wt are the weight coefficients of distance factors and threat factors, and ws+wt=1. Besides, they can be determined according to the specific requirements of route performance. For example, sometimes we need the minimum route, and sometimes the highest survival rate is required.The calculation of the threat index on theith route needs to be integrated along the ith route, for the sake of simplification, calculate average value of the threat index of certain points on the route, and then multiply the length of the influenced part. Divide route into m equal parts, select m break points on the route, and their positions can be expressed as(16)12mli,32mli,…,2n+12mlin=0,1,2,…,n<m.The threat index on the ith route is given by the expression(17)fTAi=1mli∑j=1NtfTAj12mli+fTAj32mli+⋯+fTAj2n+12mli,where Nt is the number of the known threat sources, li is the ith route length, fTAj is the threat value of the break points, the value of m can be adjusted according to the computational accuracy and the route length. According to different threat classifications, it can be calculated by formulas (8); (11); (13); (14).


## 2.3.1. Models of Threats

Threat Model of Radar. The factors that influence the probability of radar detection mainly include earth curvature, atmospheric refraction and absorption, ground clutter interference, distance between aircraft and radar, radar cross-section, radar performance, and ground multipath effect. For the sake of simplification, here we mainly take the distance from aircraft to radar and radar performance into account. Supposing the flying height is h, the horizontal distance from aircraft to radar is R, radar maximal horizontal range is Rmax, radar performance coefficient is k, the probabilistic model of radar detection can be presented as follows:(4)PR=e-kR2/h-R4/Rmax4. If a>0, the approximation expression e-a can be equivalent as follows:(5)e-a≈1a+1.If R<Rmax, aircraft is in the detection range of radar, and threat model can be simplified as follows:(6)PR=e-R4/Rmax4. Use formula (5) to get the approximation expression(7)PR≈Rmax4R4+Rmax4.If aircraft is out of the radar maximal horizontal range, threat for radar to aircraft is zero. Threat model of radar can be represented as follows:(8)PR=Rmax4R4+Rmax4R⩽Rmax0R>Rmax.Threat Model of Surface-to-Air Missile. Supposing probability distribution of missile to target obeys Poisson distribution concerning horizontal distance Rm, killing probability of maximum attack radius RMmax is e-1, and if Rm<RMmax, threat model for missile to aircraft can be presented as follows:(9)PM=e-Rm/RMmax.According to formula (5), the approximation expression can be equivalent as follows:(10)PM=RMmaxRm+RMmax.If aircraft is out of the maximum attack radius range, the threat for missile to aircraft is zero. Threat model of missile can be presented as follows:(11)PR=RMmaxRm+RMmaxRm⩽RMmax0Rm>RMmax.Threat Model of Terrain. The main danger caused by terrain is peaks, which may be an obstacle of flight when aircraft is flying at the fixed height. And peaks can be expressed as cones. Supposing the horizontal cross-section of the peak is a circumference at the flight height and the radius of circumference is Rd, the central position of the peak is (x,y), and the current position of aircraft is (xA,yA), the horizontal distance RAT from aircraft to the central of the peak can be expressed as follows:(12)RAT=xA-x2+yA-y2.Unlike several kinds of threats above, the collisions between the aircraft and peak are fatal risk for aircraft. Therefore, enough space and time must be maintained when the aircraft is bypassing the peak. Threat model of peaks can be presented as follows:(13)PT=0RAT>10Km+Rd1RAT⩽2Km+Rd1RAT2Km+Rd<RAT<10Km+Rd.Threat Model of Atrocious Weather. Similar to the threat of peak to aircraft, supposing that the radius of atrocious weather on the cross-section is Rc and horizontal distance from aircraft to the center of atrocious weather is RAW, mathematical model of atrocious weather can be presented as follows:(14)PW=0RAW>5Km+Rc1RAWRAW⩽5Km+Rc.


## 2.3.2. Path Planning Cost Calculation Function

In this paper, the cost calculation function relates to threat cost and fuel cost. Because fuel cost is proportional to the voyage, the cost calculation function can be given as(15)J=∑i=1nwsli+wtfTAi,Ji=wsli+wtfTAi,where J is the total cost of the route, Ji is the ith route cost, li is the ith route length, it can decrease flight time of aircraft in enemy air defenses area by cutting down the total length of route, fTAi is the threat index of the ith route, it ensures the aircraft can fly along the safe area, and ws and wt are the weight coefficients of distance factors and threat factors, and ws+wt=1. Besides, they can be determined according to the specific requirements of route performance. For example, sometimes we need the minimum route, and sometimes the highest survival rate is required.The calculation of the threat index on theith route needs to be integrated along the ith route, for the sake of simplification, calculate average value of the threat index of certain points on the route, and then multiply the length of the influenced part. Divide route into m equal parts, select m break points on the route, and their positions can be expressed as(16)12mli,32mli,…,2n+12mlin=0,1,2,…,n<m.The threat index on the ith route is given by the expression(17)fTAi=1mli∑j=1NtfTAj12mli+fTAj32mli+⋯+fTAj2n+12mli,where Nt is the number of the known threat sources, li is the ith route length, fTAj is the threat value of the break points, the value of m can be adjusted according to the computational accuracy and the route length. According to different threat classifications, it can be calculated by formulas (8); (11); (13); (14).


## 2.4. SparseA∗ Algorithm

Heuristic search [17] aims to use heuristic information to find the optimal path with the minimum cost. The main difference between heuristic search and other methods is that the cost information is related to heuristic information. The cost calculation function of heuristic search is given as(18)fx=Jx+hx,where x is the extended node, J(x) is the actual cost from the start node to the extended node, and h(x) is the estimate cost from the extended node to the target node. According to different task demands, heuristic information may involve many factors such as ground threat sources, artificial obstacles, flight time, and fuel quantity. An appropriate heuristic function can greatly increase search speed and acquire the solution easily.The primary problem to be solved is how to acquire the candidate node set in the search process. The expression of nodes in state space can be divided into two general types: nodes of graphic expression and nodes of grid expression. The former extends nodes out in the form of ray; the latter divides state space into grids with a certain size and then extends the adjacent grid points out. For example, basicA∗ is based on grid search. Nodes can be divided into three states in heuristic search:(1)
Nodes have been extended.(2)
Nodes have been generated but has not been extended.(3)
Nodes have not been generated.The first kind of nodes is called closed nodes, and we can construct a table namedCLOSED to store this kind of nodes; the second kind of nodes is called open nodes because the nodes has been generated but has not been extended, such nodes can be stored in a table namedOPEN. The start nodes are stored inOPEN table in the initial search. New nodes can be generated according to different extensible rules, and then these new nodes are inserted intoOPEN table according to the increment of the cost value f, the node with the smallest value can be preferentially extended, and it can be stored inCLOSED table.


## 3. Path Planning Methods Based on SparseA∗ Searching Algorithm

### 3.1. SparseA∗ Algorithm Based on Constrains of Path Planning

Szczerba et al. provided an advanced version of the basicA∗ searching algorithm in 2000 which is called SAS (Sparse A∗ Search). Traditional A∗ algorithm is designed on the basis of grid search. For example, in Figure 2, define xc as the current node and xe as the extended node. Eight neighborhood subnodes are taken into account when extending nodes. In addition, we can also take more neighborhood nodes into account when extending nodes. But, generally speaking, larger neighborhood corresponds to the more elaborate route, larger memory space, and longer period of convergence time. Since the nodes can only be extended to eight fixed directions, the generated path may not meet constraints of path planning introduced in Section 2.2.Figure 2
The basic extension ofA∗ nodes.SAS [5] could combine constraints such as minimum step, maximum turning angle, and maximum route into search algorithm, which condenses search space effectively. SAS not only improves the search efficiency but also meets the flight constrained conditions. In the following section, we will introduce how to combine flight constrained conditions into the process of the extension of nodes. We will also discuss how to set a reasonable cost function.


### 3.2. Extensible Rules of Nodes

LetL be the minimum step and θ be the maximum turning angle. Based on the known direction of current nodes, the search of the current nodes is limited to the fan-shaped region with a range of 2θ. The medial axis of the fan-shaped region is the direction of the current nodes. Then, the fan-shaped region is divided into m equal parts, and the cost of knot vector whose distance is between each subpart and the current nodes is calculated. To save space and speed up convergence rate, only the node with the minimum cost of each sector is reserved. As shown in Figure 3, the fan-shaped region is divided into three equal parts: A, B, and C representing the nodes with the minimum cost of each fan-shaped region, respectively. Set m according to different accuracy requirements and convergence rate, and the number of nodes should be smaller than m. This process is repeated when extending nodes. Remove the node with minimum cost fromOPEN table, and then define this node as the current node and insert the current node intoCLOSED table. Extend the current node, and then insert all subnodes intoOPEN table according to the increment of cost value.Figure 3
SAS extension of nodes.The constraint of route distance is the allowable maximum length of the route which represents the payload of fuel and arrival time constraint in a specific task. The route whose length is longer than maximum distance (dmax) is termed as the invalid route. On the basis of the above discussion, before inserting the nodes with the minimum cost intoOPEN table, define xc as the current node, and we need to make a judgment of another condition as follows:(19)Dxc+SLxc⩽dmax,where D(xc) is the actual distance between the start point and the current point, SL(xc) is the straight-line distance between current node and the target point, dmax is generally several times the value of the straight-line distance between the start point to the target point. If the current node meets the above requirements, it can be extended; otherwise it will be discarded. This method can not only meet flight restrictions but also generate direct route effectively.


### 3.3. Trajectory Cost Function

On the basis of the above discussion, the cost function of heuristic search can be represented asf(x)=J(x)+h(x). The actual cost function J(x) can be calculated by formula (15), and here we discuss the calculation of h(x).The basicA∗ heuristic function adopts the Manhattan distance to show the distance from the current node to the target node:(20)h1=xb-xm+yb-ym,where xb,yb is the coordinate of the current node and xm,ym is the coordinate of the target node. Considering the constraints of target approaching angle, aircraft is set to reach the target in a fixed direction. Angle information is taken into account when designing the cost function. The deviation between current course and target course is used to guide search process within the predetermined direction. The cost function [1] which adds the angle information can be expressed as follows:(21)h2=wdh1+wθhθ,(22)hθ=Δθ2,where h1 is distance heuristic function which can be calculated by formula (20), h(θ) is angle heuristic function which can be calculated by formula (22), wd and wθ are the weight coefficients of distance heuristic and angle heuristic, respectively, and wd+wθ=1. In formula (22), Δθ=θx-θm, θx is the direction of the line which connects current nodes and target nodes and θm is the predetermined target approaching angle. Supposing θx∈-π,+π, θm∈-π,+π, and Δθ∈-2π,+2π, Δθ is regulated as follows:(23)Δθ=-2π-Δθπ<Δθ⩽2πΔθ+2π-2π<Δθ⩽-π.In traditional search method, the path may prematurely tend to the predetermined target direction so that the resulting path may not be the shortest path. Only when the aircraft nears the target can the aircraft turn to the predetermined target direction in the long distance flight, it is not necessary to have been proceeding angle heuristic throughout the whole search process. In the proposed method, heuristic functionh2 takes angle information into consideration. Let radius be a∗d, d be the simulation step size, and a be range coefficient. The size of the radius can be adjusted according to the maneuver ability and the simulation step size. The aircraft should be able to turn the predetermined direction timely within this range. If the nodes are within this range, heuristic function h2 is used to calculate the cost; otherwise heuristic function h1 is used. The proposed method can not only make the aircraft close to the target in the predetermined direction but also get an approximate optimal solution. In SAS algorithm, the calculation of route cost can be expressed as follows:(24)fx=Jx+h1DLx>a∗dJx+h2DLx⩽a∗d,where DL(x) is the distance between x and target node and J(x) is the actual cost value. The cost value generated by the distance and threat can be calculated by formula (15).On the basis of the above discussion, it is very important to find a reasonable heuristic function for getting an approximate optimal solution without reducing search speed. It is also important to design corresponding appropriate heuristic function for different stages of track search.


### 3.4. Trajectory Smooth Straightening Processing

#### 3.4.1. Method  1

From the above description, the ultimate goal of path planning system is to generate a set of track point data and then provide these data to flight task manager. Therefore, the initial route obtained by search algorithm needs to be processed so as to get the smaller number of track points. Track points located between start point and target point are stored in path table. Set start point as current point, and traverse other nodes in path table according to the order of the current point to next point. Check whether the connection line of current node and a certain visiting node will encounter threat. If the connection line of current node and a certain visiting node encounters threat, go back to the previous node, set the previous node as current node, delete all nodes between current node and the last current node, update information of current note, and retraverse from this current node until reaching the target node. Otherwise it continues to traverse and repeat above steps.


#### 3.4.2. Method  2

The following method is optimized in the search process. As shown in Figure4, let A be current node, B be father node of current node, C be ancestral node, and their cost values are fa, fb, and fc, respectively. In the planning of extending current node fromOPEN table toCLOSED table, calculate the route cost from current node A to ancestral node C, and the route cost is Δf3=fa-fc; the route cost from node A to its father node B is Δf1=fa-fb; the route cost from father node B to ancestral node C is Δf2=fb-fc. Judge their relationship, if Δf3<Δf1+Δf2, which indicated that the connection cost from current node to its ancestral node is superior to that from current node to its father node. Therefore, set ancestral node of current node as its father node and adjust its cost value.Figure 4
Track smooth straightening processing map.The route obtained from the above methods can not only reduce route cost but also constrain the number of turns. Besides, valid information of track points can be generated which is in favor of the future navigation.


## 3.1. SparseA∗ Algorithm Based on Constrains of Path Planning

Szczerba et al. provided an advanced version of the basicA∗ searching algorithm in 2000 which is called SAS (Sparse A∗ Search). Traditional A∗ algorithm is designed on the basis of grid search. For example, in Figure 2, define xc as the current node and xe as the extended node. Eight neighborhood subnodes are taken into account when extending nodes. In addition, we can also take more neighborhood nodes into account when extending nodes. But, generally speaking, larger neighborhood corresponds to the more elaborate route, larger memory space, and longer period of convergence time. Since the nodes can only be extended to eight fixed directions, the generated path may not meet constraints of path planning introduced in Section 2.2.Figure 2
The basic extension ofA∗ nodes.SAS [5] could combine constraints such as minimum step, maximum turning angle, and maximum route into search algorithm, which condenses search space effectively. SAS not only improves the search efficiency but also meets the flight constrained conditions. In the following section, we will introduce how to combine flight constrained conditions into the process of the extension of nodes. We will also discuss how to set a reasonable cost function.


## 3.2. Extensible Rules of Nodes

LetL be the minimum step and θ be the maximum turning angle. Based on the known direction of current nodes, the search of the current nodes is limited to the fan-shaped region with a range of 2θ. The medial axis of the fan-shaped region is the direction of the current nodes. Then, the fan-shaped region is divided into m equal parts, and the cost of knot vector whose distance is between each subpart and the current nodes is calculated. To save space and speed up convergence rate, only the node with the minimum cost of each sector is reserved. As shown in Figure 3, the fan-shaped region is divided into three equal parts: A, B, and C representing the nodes with the minimum cost of each fan-shaped region, respectively. Set m according to different accuracy requirements and convergence rate, and the number of nodes should be smaller than m. This process is repeated when extending nodes. Remove the node with minimum cost fromOPEN table, and then define this node as the current node and insert the current node intoCLOSED table. Extend the current node, and then insert all subnodes intoOPEN table according to the increment of cost value.Figure 3
SAS extension of nodes.The constraint of route distance is the allowable maximum length of the route which represents the payload of fuel and arrival time constraint in a specific task. The route whose length is longer than maximum distance (dmax) is termed as the invalid route. On the basis of the above discussion, before inserting the nodes with the minimum cost intoOPEN table, define xc as the current node, and we need to make a judgment of another condition as follows:(19)Dxc+SLxc⩽dmax,where D(xc) is the actual distance between the start point and the current point, SL(xc) is the straight-line distance between current node and the target point, dmax is generally several times the value of the straight-line distance between the start point to the target point. If the current node meets the above requirements, it can be extended; otherwise it will be discarded. This method can not only meet flight restrictions but also generate direct route effectively.


## 3.3. Trajectory Cost Function

On the basis of the above discussion, the cost function of heuristic search can be represented asf(x)=J(x)+h(x). The actual cost function J(x) can be calculated by formula (15), and here we discuss the calculation of h(x).The basicA∗ heuristic function adopts the Manhattan distance to show the distance from the current node to the target node:(20)h1=xb-xm+yb-ym,where xb,yb is the coordinate of the current node and xm,ym is the coordinate of the target node. Considering the constraints of target approaching angle, aircraft is set to reach the target in a fixed direction. Angle information is taken into account when designing the cost function. The deviation between current course and target course is used to guide search process within the predetermined direction. The cost function [1] which adds the angle information can be expressed as follows:(21)h2=wdh1+wθhθ,(22)hθ=Δθ2,where h1 is distance heuristic function which can be calculated by formula (20), h(θ) is angle heuristic function which can be calculated by formula (22), wd and wθ are the weight coefficients of distance heuristic and angle heuristic, respectively, and wd+wθ=1. In formula (22), Δθ=θx-θm, θx is the direction of the line which connects current nodes and target nodes and θm is the predetermined target approaching angle. Supposing θx∈-π,+π, θm∈-π,+π, and Δθ∈-2π,+2π, Δθ is regulated as follows:(23)Δθ=-2π-Δθπ<Δθ⩽2πΔθ+2π-2π<Δθ⩽-π.In traditional search method, the path may prematurely tend to the predetermined target direction so that the resulting path may not be the shortest path. Only when the aircraft nears the target can the aircraft turn to the predetermined target direction in the long distance flight, it is not necessary to have been proceeding angle heuristic throughout the whole search process. In the proposed method, heuristic functionh2 takes angle information into consideration. Let radius be a∗d, d be the simulation step size, and a be range coefficient. The size of the radius can be adjusted according to the maneuver ability and the simulation step size. The aircraft should be able to turn the predetermined direction timely within this range. If the nodes are within this range, heuristic function h2 is used to calculate the cost; otherwise heuristic function h1 is used. The proposed method can not only make the aircraft close to the target in the predetermined direction but also get an approximate optimal solution. In SAS algorithm, the calculation of route cost can be expressed as follows:(24)fx=Jx+h1DLx>a∗dJx+h2DLx⩽a∗d,where DL(x) is the distance between x and target node and J(x) is the actual cost value. The cost value generated by the distance and threat can be calculated by formula (15).On the basis of the above discussion, it is very important to find a reasonable heuristic function for getting an approximate optimal solution without reducing search speed. It is also important to design corresponding appropriate heuristic function for different stages of track search.


## 3.4. Trajectory Smooth Straightening Processing

### 3.4.1. Method  1

From the above description, the ultimate goal of path planning system is to generate a set of track point data and then provide these data to flight task manager. Therefore, the initial route obtained by search algorithm needs to be processed so as to get the smaller number of track points. Track points located between start point and target point are stored in path table. Set start point as current point, and traverse other nodes in path table according to the order of the current point to next point. Check whether the connection line of current node and a certain visiting node will encounter threat. If the connection line of current node and a certain visiting node encounters threat, go back to the previous node, set the previous node as current node, delete all nodes between current node and the last current node, update information of current note, and retraverse from this current node until reaching the target node. Otherwise it continues to traverse and repeat above steps.


### 3.4.2. Method  2

The following method is optimized in the search process. As shown in Figure4, let A be current node, B be father node of current node, C be ancestral node, and their cost values are fa, fb, and fc, respectively. In the planning of extending current node fromOPEN table toCLOSED table, calculate the route cost from current node A to ancestral node C, and the route cost is Δf3=fa-fc; the route cost from node A to its father node B is Δf1=fa-fb; the route cost from father node B to ancestral node C is Δf2=fb-fc. Judge their relationship, if Δf3<Δf1+Δf2, which indicated that the connection cost from current node to its ancestral node is superior to that from current node to its father node. Therefore, set ancestral node of current node as its father node and adjust its cost value.Figure 4
Track smooth straightening processing map.The route obtained from the above methods can not only reduce route cost but also constrain the number of turns. Besides, valid information of track points can be generated which is in favor of the future navigation.


## 3.4.1. Method  1

From the above description, the ultimate goal of path planning system is to generate a set of track point data and then provide these data to flight task manager. Therefore, the initial route obtained by search algorithm needs to be processed so as to get the smaller number of track points. Track points located between start point and target point are stored in path table. Set start point as current point, and traverse other nodes in path table according to the order of the current point to next point. Check whether the connection line of current node and a certain visiting node will encounter threat. If the connection line of current node and a certain visiting node encounters threat, go back to the previous node, set the previous node as current node, delete all nodes between current node and the last current node, update information of current note, and retraverse from this current node until reaching the target node. Otherwise it continues to traverse and repeat above steps.


## 3.4.2. Method  2

The following method is optimized in the search process. As shown in Figure4, let A be current node, B be father node of current node, C be ancestral node, and their cost values are fa, fb, and fc, respectively. In the planning of extending current node fromOPEN table toCLOSED table, calculate the route cost from current node A to ancestral node C, and the route cost is Δf3=fa-fc; the route cost from node A to its father node B is Δf1=fa-fb; the route cost from father node B to ancestral node C is Δf2=fb-fc. Judge their relationship, if Δf3<Δf1+Δf2, which indicated that the connection cost from current node to its ancestral node is superior to that from current node to its father node. Therefore, set ancestral node of current node as its father node and adjust its cost value.Figure 4
Track smooth straightening processing map.The route obtained from the above methods can not only reduce route cost but also constrain the number of turns. Besides, valid information of track points can be generated which is in favor of the future navigation.


## 4. Experimental Study

Define the range of path planning as500Km×500Km and the simulation step size and minimum route length d as 5 Km. Define distance coefficient and threat coefficient as ws=0.5 and wt=0.5, respectively, when calculating the actual cost; define distance coefficient and angle coefficient as wd=0.5 and wθ=0.5, respectively, when calculating heuristic function which takes the angle information into account. The maximum route distance constraint is 1.5 times the straight distance between the start point and target point. Let angle heuristic range coefficient a be 5, maximum turning angle be 60, m be 3 when extending nodes.(1)
Supposing the coordinate of start point is(0,0), the coordinate of target point is (450,500). The threat distribution is given as Figure 5, and the result of path planning is presented in Figure 5.(2)
Supposing the coordinate of start point is100,100, the coordinate of target point is 400,400. The threat distribution and the result of path planning are shown in Figure 6. The second method (see Section 3.4.2) is taken when considering route processing, and the result of path planning can be shown as Figure 7.(3)
Supposing the coordinate of start point is(40,30), the coordinate of target point is (100,100). The threat distribution is given as Figure 8, and the result of path planning can be shown as Figure 8. The first method (see Section  3.4.1) is taken when considering route processing, and the result of path planning can be shown as Figure 8.Figure 5
The first result.Figure 6
The second result.Figure 7
The third result.Figure 8
The fourth result.


## 5. Conclusion

This paper presents an improved heuristic algorithm which is an improved version of SAS algorithm for UCAV path planning. Our algorithm considers not only traditional constraints of path planning but also various flight constrained conditions, like angle information, track smooth straightening processing, and so on. Compared with [5], the simulation results show that angle information and trajectory smooth straightening processing are advisable, effective, and feasible. In addition, the algorithm can not only make the aircraft close to the target in the predetermined direction but also get an approximate optimal solution. And our improved algorithm has less extended nodes in complex conditions and the running efficiency is much better. Besides, some simulations have shown that our proposed new model and algorithm can meet the flight restrictions and task demands of UCAV path planning.



---

*Source: 8936164-2017-04-10.xml*