# UCAV Path Planning by Fitness-Scaling Adaptive Chaotic Particle Swarm Optimization

Authors: Yudong Zhang; Lenan Wu; Shuihua Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Path planning plays an extremely important role in the design of UCAVs to accomplish the air combat task fleetly and reliably. The planned path should ensure that UCAVs reach the destination along the optimal path with minimum probability of being found and minimal consumed fuel. Traditional methods tend to find local best solutions due to the large search space. In this paper, a Fitness-scaling Adaptive Chaotic Particle Swarm Optimization (FAC-PSO) approach was proposed as a fast and robust approach for the task of path planning of UCAVs. The FAC-PSO employed the fitness-scaling method, the adaptive parameter mechanism, and the chaotic theory. Experiments show that the FAC-PSO is more robust and costs less time than elite genetic algorithm with migration, simulated annealing, and chaotic artificial bee colony. Moreover, the FAC-PSO performs well on the application of dynamic path planning when the threats cruise randomly and on the application of 3D path planning.


---

## Body

## 1. Introduction

Unmanned combat air vehicle (UCAV) is an experimental class of the unmanned aerial vehicle (UAV). UCAVs differ from ordinary UAVs because they are designed to deliver weapons to attach enemy targets. The elimination of the need for an onboard human crew in a UCAV that may be shot down over enemy territory has obvious advantages for personnel safety. In addition, much equipment necessary for a human pilot (such as the cockpit, flight controls, oxygen, and seat/ejection seat) can be omitted from an unmanned vehicle, resulting in a decrease in weight possibly allowing greater payloads, range, and maneuverability.The path planning of UCAV is to generate a space path between an initial safe location and the desired dangerous destination that has an optimal or near-optimal performance under specific constraint conditions. It is always a complex research subject, so it is an imperative technology required in the design of UCAV. Series of algorithms have been proposed to solve this complicated multiconstrained optimization problem. Allaire used a genetic algorithm (GA) to realize the FPGA implementation for UAV real-time path planning [1]. Duan et al. proposed an improved particle swarm optimization to optimize the formation reconfiguration control of multiple UCAVs [2], proposed a hybrid metaheuristic ant colony optimization (ACO) and differential evolution (DE) to solve the UCAV three-dimension path-planning problem [3], and proposed a max-min adaptive ant colony algorithm for multi-UCAVs coordinated trajectory replanning [4]. Mou et al. proposed a modified ant colony algorithm as a fast and efficient approach for path planning of UCAV [5]. Zhang et al. proposed an improved artificial bee colony algorithm for UCAV path-planning problem [6]. However, these methods can easily be trapped into local minima and cannot solve the contradiction between the goal optimization and excessive information.PSO is well known for its lower computational costs, and its most attractive feature is that it requires less computational bookkeeping and only a few lines of implementation codes. In order to improve the performance of a traditional PSO, three improvements are proposed: (I) a new power-rank fitness-scaling method, by which the scaled values are suitable for following selection; (II) adaptively varied parameters to search an expansive area at the prophase stage and a restricted area at the anaphase stage; and (III) introduction of chaos to improve the robustness of the basic PSO algorithm considering its outstanding performance of jumping out of stagnation.The remainder of this paper is organized as follows. Section2 introduces the encoding strategy for path planning. Section 3 discusses the performance evaluation function containing both the threat cost and the fuel cost. Section 4 introduces the basic principles of canonical PSO. Section 5 gives detailed description of our proposed method—Fitness-scaling Adaptive Chaotic PSO (FAC-PSO). Experiments in Section 6 compared our proposed method with elite genetic algorithm with migration, simulated annealing, and chaotic artificial bee colony. The statistical results on 100 different runs demonstrate that the FAC-PSO is superior to other algorithms with respect to success rate and computation time. Besides, we also applied our approach in the field of dynamic UCAV path planning. Final Section 7 is devoted to the conclusions.


## 2. Path Encoding

In this model, the starting point and the target point are defined asPS and PT, respectively. There are threatening areas in the task region, such as artillery, radar, and missile, which all are presented in the form of a circle. Inside of the threatening areas, the UCAV should be vulnerable to the threat with a certain probability proportional to the distance away from the threat center, while outside of the threatening areas, the UCAV should be safe without being attacked. The task of path planning is to design an optimal path between start point and target point considering all these threatening areas as shown in Figure 1.Figure 1
Typical 2D UCAV battlefield model.We connect the starting point and target point and then divide the straight linePSPT into (D+1) equal portions. At each segment point, draw the vertical line of PSPT, which can be labeled with L1,L2,…,Li,…,LD. Select discrete points Pi at each Li. In this way, the path from the starting node to the target node can be described as follows:
(1)path={PS,P1,P2,…,Pi,…,PD,PT}.
The location of PS and PT is known for UCAV, and the location of line Li(i=1,2,…,D) can be easily calculated. Therefore, each point Pi(i=1,2,…,D) can be expressed using only 1 parameter, namely, its distance to the straight line PSPT. In a word, there are total D parameters in (1), so our task is a D-dimensional optimization problem. In the following section, we let P0=PS and PD+1=PT in order to simplify the expression.


## 3. Performance Function

The performance indicators of the planned path mainly consist of the threat costJT and the fuel cost JF. Their calculation formulas are expressed as follows:(2)JT=∑i=0DJT(i),JF=∑i=0DJF(i).
Here, JT(i) and JF(i) denote the threat cost and fuel cost at the ith subpath from Pi to Pi+1, respectively. The threat cost of subpath is calculated by an approximation based on five discrete points along the subpath as shown in Figure 2. If the ith subpath (Pi,Pi+1) is within the effect range, the threat cost is given as [7](3)JT(i)=Li5∑k=1NTTk(1d0.1,i,k4+1d0.3,i,k4+1d0.5,i,k4+1d0.7,i,k4+1d0.9,i,k4).Here, NT denotes the number of threatening areas, Li denotes the length of ith subpath, Tk denotes the degree of threatening, and d0.1,i,k denotes the distance from the 1/10 point on the ith subpath to the kth threat area.Figure 2
Computation of threat cost.Suppose that the velocity of UCAV is constant, the fuel cost of theith subpath JF(i) can be considered proportional to Li. Therefore, the total cost of the path is proportional to the total length of the path L.The total cost for traveling along the trajectory comes from a weighted sum of the threat and fuel costs, as defined in the following formula(4)J=ωJT+(1-ω)JF,
where ω is a variable between 0 and 1, giving the designer certain flexibility to dispose relations between the threat exposition degree and the fuel consumption. If ω approaches 1, a safer path is needed and less attention is paid to the fuel. Alternatively, if ω approaches 0, a shorter path is needed even on the cost of sacrifice the safety. In this study, we determine it as 0.5 by the suggestion from [8], indicating that the threat is as important as the fuel.


## 4. Particle Swarm Optimization

PSO is a population-based stochastic optimization technique, which simulates the social behavior of a swarm of birds, flocking bees, and fish schooling [9]. By randomly initializing the algorithm with candidate solutions, the PSO successfully leads to a global optimum. This is achieved by an iterative procedure based on the processes of movement and intelligence in an evolutionary system. Figure 3 shows the flow chart of a PSO algorithm.Figure 3
Flow chart of the PSO algorithm.In PSO, each potential solution is represented as a particle. Two properties (positionx and velocity v) are associated with each particle. Suppose x and v of the ith particle are given as
(5)x=(xi1,xi2,…,xiN),v=(vi1,vi2,…,viN),
where N stands for the dimensions of the problem. In each iteration, a fitness function is evaluated for all the particles in the swarm. The velocity of each particle is updated by keeping track of the two best positions. One is the best position a particle has traversed so far and called “pBest”. The other is the best position that any neighbor of a particle has traversed so far. It is a neighborhood best called “nBest”. When a particle takes the whole population as its neighborhood, the neighborhood best becomes the global best and is accordingly called “gBest”. Hence, a particle’s velocity and position are updated as follows:
(6)v=ω·v+c1r1(pBest-x)+c2r2(nBest-x),x=x+vΔt,
where ω is called the “inertia weight” that controls the impact of the previous velocity of the particle on its current one. The parameters c1 and c2 are positive constants called “acceleration coefficients”. The parameters r1 and r2 are random numbers uniformly distributed in the interval [0,1]. These random numbers are updated every time they occur. The parameter Δt stands for the given time step.The population of particles is then moved according to (6) and tends to cluster together from different directions. However, a maximum velocity vmax should not be exceeded by any particle to keep the search within a meaningful solution space. The PSO algorithm runs through these processes iteratively until the termination criterion is satisfied [10].


## 5. Principle of FAC-PSO

The PSO has proven to perform better than GA, DE, and ACO [11]. However, we can make further improvements from the following three aspects.


### 5.1. Fitness Scaling

Fitness scaling converts the raw fitness scores that are returned by the fitness function to values in a range that is suitable for the selection function [12]. The selection function uses the scaled fitness values to select the particles of the next generation. Then, the selection function assigns a higher probability of selection to particles with higher scaled values.There exist bundles of fitness-scaling methods. One of the most common scaling techniques is traditional linear scaling, which remaps the fitness values of each particle using the following equation:(7)flinear=a+b×fraw,
where a and b are constants defined by users. Another option is the rank scaling, which is obtained by sorting all the bees by their raw fitness values
(8)frank=r,
where r denotes the rank of the individual particle. The third option is the power scaling method which is instead computed with
(9)fpower=frawk,
where k is a problem-dependent exponent that might require change during a run to stretch or shrink the range as needed. Top scaling is the 4th option and probably the simplest scaling method. Using this approach, several of the top individuals have their fitness set to the same value, with all remaining individuals having their fitness values set to zero. This simple concept yields
(10)ftop={sfraw≥c0fraw<c,
where s is the user-defined constant, c is the threshold.Among those fitness-scaling methods, the power scaling finds a solution nearly the most quickly due to improvement of diversity but it suffers from instability [13]; meanwhile, the rank scaling shows stability on different types of tests [14]. Therefore, a new power-rank scaling method was proposed combing both power and rank strategies as follows:
(11)fiti=rik∑i=1Nrik,
where ri is the rank of ith individual bee, N is the number of population. Our strategy contains a three-step process. First, all bees are sorted to obtain the corresponding ranks. Second, powers are computed for exponential values k. Third, the scaled values are normalized by dividing the sum of the scaled values over the entire population.


### 5.2. Adaptive Parameters

Another improvement lies in changing the parameters(ω,c1,c2) adaptively. In the search process of PSO, the search space will gradually reduce as the generation increases. Therefore, we hope to search an expansive area with low precision at the prophase stage while searching a restricted area with high precision at the anaphase stage as listed in Table 1. The detailed formulas of those adaptive parameters are as follows:
(12)ω=ωi-ωi-ωfMaxGeneration*Generation(ωi>ωf),c1=c1i-c1i-c1fMaxGeneration*Generation(c1i>c1f),c2=c2i-c2i-c2fMaxGeneration*Generation(c2i<c2f).
Here, the indexes i and f denote “initial” and “final”, respectively.Table 1
Parameters variation.
Ω
c
1
c
2
Performance
Prophase
Larger
Larger
Smaller
PSO searches for global optima in an expansive area with low precision
Anaphase
Smaller
Smaller
Larger
PSO searches for local optima in a limited area with high precision


### 5.3. Chaotic Random Number

The parameters(r1,r2) were generated by a pseudorandom number generator (RNG) in classical PSO. The RNG cannot ensure the optimization’s ergodicity in solution space because it is absolutely random; therefore, a chaotic operator was employed to generate parameters (r1,r2) by the following formula:
(13)ri(t+1)=4.0*ri(t)*[1-ri(t)],i=1,2,
where r0∈(0,1) and r0∉{0.25,0.5,0.75}. A very small difference in the initial value of x would give rise to a large difference in its long-time behavior as shown in Figure 4. The track of chaotic variable xn can travel ergodically over the whole space of interest.Chaotic Property of logistic equation: (a)x0=0.12345678; (b) x0=0.12345679.
(a)
(b)Figure5 shows that the series is in the cycle (0.75) when initial points are 0.25 or 0.75 since 4*0.25*(1-0.25)=0.75 and 4*0.75*(1-0.75)=0.75. The series is in cycle (0) when initial point is 0.5 since 4*0.5*(1-0.5)=1 and 4*1*(1-1)=0. Therefore, those three points (0.25, 0.5, and 0.75) will make the series lose chaotic property.Loss of chaotic property at specific initial values: (a)x0=0.25; (b) x0=0.5; and (c) x0=0.75.
(a)
(b)
(c)


## 5.1. Fitness Scaling

Fitness scaling converts the raw fitness scores that are returned by the fitness function to values in a range that is suitable for the selection function [12]. The selection function uses the scaled fitness values to select the particles of the next generation. Then, the selection function assigns a higher probability of selection to particles with higher scaled values.There exist bundles of fitness-scaling methods. One of the most common scaling techniques is traditional linear scaling, which remaps the fitness values of each particle using the following equation:(7)flinear=a+b×fraw,
where a and b are constants defined by users. Another option is the rank scaling, which is obtained by sorting all the bees by their raw fitness values
(8)frank=r,
where r denotes the rank of the individual particle. The third option is the power scaling method which is instead computed with
(9)fpower=frawk,
where k is a problem-dependent exponent that might require change during a run to stretch or shrink the range as needed. Top scaling is the 4th option and probably the simplest scaling method. Using this approach, several of the top individuals have their fitness set to the same value, with all remaining individuals having their fitness values set to zero. This simple concept yields
(10)ftop={sfraw≥c0fraw<c,
where s is the user-defined constant, c is the threshold.Among those fitness-scaling methods, the power scaling finds a solution nearly the most quickly due to improvement of diversity but it suffers from instability [13]; meanwhile, the rank scaling shows stability on different types of tests [14]. Therefore, a new power-rank scaling method was proposed combing both power and rank strategies as follows:
(11)fiti=rik∑i=1Nrik,
where ri is the rank of ith individual bee, N is the number of population. Our strategy contains a three-step process. First, all bees are sorted to obtain the corresponding ranks. Second, powers are computed for exponential values k. Third, the scaled values are normalized by dividing the sum of the scaled values over the entire population.


## 5.2. Adaptive Parameters

Another improvement lies in changing the parameters(ω,c1,c2) adaptively. In the search process of PSO, the search space will gradually reduce as the generation increases. Therefore, we hope to search an expansive area with low precision at the prophase stage while searching a restricted area with high precision at the anaphase stage as listed in Table 1. The detailed formulas of those adaptive parameters are as follows:
(12)ω=ωi-ωi-ωfMaxGeneration*Generation(ωi>ωf),c1=c1i-c1i-c1fMaxGeneration*Generation(c1i>c1f),c2=c2i-c2i-c2fMaxGeneration*Generation(c2i<c2f).
Here, the indexes i and f denote “initial” and “final”, respectively.Table 1
Parameters variation.
Ω
c
1
c
2
Performance
Prophase
Larger
Larger
Smaller
PSO searches for global optima in an expansive area with low precision
Anaphase
Smaller
Smaller
Larger
PSO searches for local optima in a limited area with high precision


## 5.3. Chaotic Random Number

The parameters(r1,r2) were generated by a pseudorandom number generator (RNG) in classical PSO. The RNG cannot ensure the optimization’s ergodicity in solution space because it is absolutely random; therefore, a chaotic operator was employed to generate parameters (r1,r2) by the following formula:
(13)ri(t+1)=4.0*ri(t)*[1-ri(t)],i=1,2,
where r0∈(0,1) and r0∉{0.25,0.5,0.75}. A very small difference in the initial value of x would give rise to a large difference in its long-time behavior as shown in Figure 4. The track of chaotic variable xn can travel ergodically over the whole space of interest.Chaotic Property of logistic equation: (a)x0=0.12345678; (b) x0=0.12345679.
(a)
(b)Figure5 shows that the series is in the cycle (0.75) when initial points are 0.25 or 0.75 since 4*0.25*(1-0.25)=0.75 and 4*0.75*(1-0.75)=0.75. The series is in cycle (0) when initial point is 0.5 since 4*0.5*(1-0.5)=1 and 4*1*(1-1)=0. Therefore, those three points (0.25, 0.5, and 0.75) will make the series lose chaotic property.Loss of chaotic property at specific initial values: (a)x0=0.25; (b) x0=0.5; and (c) x0=0.75.
(a)
(b)
(c)


## 6. Experiments

The experiments were carried out on the platform of P4 IBM with 3 GHz main frequency and 2 GB memory, running under Windows XP operating system. The algorithm was developed via the global optimization toolbox of MatLab 2011a.


### 6.1. Threat Setting

Set the coordinates of the starting point as (5, 5) and the target point as (100, 100). In the flight course, there exist eight threat areas listed in Table2. Suppose that the codes of initial path are all zeros, which corresponds to a straight line from starting point directly to the target point as shown in Figure 6. Traditional gradient-based methods will guide the 12th–20th nodes of the path to search the upper-left area, and they will finally be misled into the local minima. However, the evolutionary algorithms including GA, PSO, and our proposed FAC-PSO are able to jump from the local minima and search the bottom-right area, where the global minimal point locates in.Table 2
Information of 2D threatening objects.
Index
Position
Radius
1
(10, 30)
14
2
(10, 50)
10
3
(20, 80)
20
4
(40, 15)
12
5
(40, 50)
15
6
(50, 70)
12
7
(75, 70)
14
8
(80, 40)
12Figure 6
Local minima and global minima.


### 6.2. Algorithm Comparison

We compared the proposed FAC-PSO method with elite genetic algorithms with migration (EGAM) [15], simulated annealing (SA) [16], chaotic artificial bee colony (CABC) [8], and standard PSO. The parameters are obtained through trial-and-error method and shown in Table 3. Here, NP means the number of populations/bees/particles corresponding to different algorithms, and MaxEpoch means the maximum iterative epochs. PC, Pm, and Pe of EGAM stand for the crossover probability, mutation probability, and elite probability, respectively. TDF, TI, and TF of SA denote the temperature decrease function, initial temperature, and final temperature, respectively. NF in CABC represents the number of foods.Table 3
Parameters of algorithms.
Algorithm
Parameter setting
EGAM
N
P
=
20; MaxEpoch = 100; PC=0.8; Pm=0.1; Pe=0.1; and migration interval = 20.
SA
N
P
=
20; MaxEpoch = 100; TDF = “exponential”; TI=100, and TF=0.
CABC
N
P
=
20; MaxEpoch = 100; and NF=10.
PSO
N
P
=
20; MaxEpoch = 100; vmax=1; ω=0.6; c1=1; and c2=1.
FAC-PSO
N
P
=
20; MaxEpoch = 100; vmax=1; ωi=0.9; ωf=0.4; c1i=2.5; c1f=0.5, c2i=0.5; and c2f=2.5.Each algorithm ran 100 times, and the success rate was calculated and shown in Table4. It indicates that the proposed FAC-PSO show slight superiority to other algorithms when D=10. As the D increases, the FAC-PSO shows more robustness compared to other algorithms. It should be noted that a larger D makes the search space larger, which leads to the success rate of all the algorithms decreasing.Table 4
Success rates of different algorithms for 2D UCAV.
D
EGAM
SA
CABC
PSO
FAC-PSO
10
78%
22%
80%
75%
87%
15
66%
12%
67%
71%
85%
20
53%
3%
59%
56%
80%We takeD=20 as an example, choose a typical run and show the convergence plot in Figure 7. It indicates that the proposed FAC-PSO was trapped into local minima at about 42 epochs but it jump out at about 45th epoch. Conversely, the EGAM, SA, CABC, and PSO were stagnated in the local minima over all 100 epochs.Figure 7
A typical convergence plot of different algorithms.The final searched paths of the four algorithms are shown in Figure8. It indicates that our proposed FAC-PSO found the global best path of the algorithm, while the other four algorithms failed at this run.Planned path of (a) EGAM; (b) SA; (c) CABC; (d) PSO; and (e) FAC-PSO.
(a)
(b)
(c)
(d)
(e)


### 6.3. Time Comparison

Computation time is another important factor used to evaluate the algorithm. Since a failed run usually takes little time due to early stagnation, we only consider the success runs. The average computation times of each algorithm of different sizes ofD are shown in Table 5. It indicates that the proposed algorithm takes the least time in spite of the size of D; moreover, the SA takes the second least time for calculation. The most time-consuming algorithm is the CABC.Table 5
Average computation time (s).
D
EGAM
SA
CABC
PSO
FAC-PSO
10
12.3
11.6
14.6
13.0
10.2
15
12.9
13.8
15.3
14.7
11.3
20
14.5
13.6
16.8
14.9
13.7


### 6.4. Dynamic Path Planning

The aforementioned paths are static ones which are determined by a beforehand-known map and threat information, but the UCAV usually meets unforeseen threats in actual flight course, so they must possess dynamic path-planning ability. When UCAV detects instantaneous or moving threat, it must replan the path so as to avoid the new arisen threat by revising the former path.Suppose that all the threatening areas can move randomly, then, the flight path of UCAV should change after each move according to the current threat positions. The UCAV paths by the proposed FAC-PSO at steps 0, 5, 10, and 15 are shown in Figure9, which imply the feasibility of FAC-PSO under moving threatening conditions.All threatening obstacles are moving for dynamic path planning: (a) step 0; (b) step 5; (c) step 10; and (d) step 15.
(a)
(b)
(c)
(d)


### 6.5. 3D Path Planning

We applied our method to 3D UCAV path planning. First, we generate a cube (100 × 100 × 100). Second, we generated 10 threats, and their coordinates and radii are listed in Table6.Table 6
Information of 3D threatening objects.
Index
Position
Radius
1
(10, 30, 30)
14
2
(10, 50, 20)
10
3
(20, 80, 40)
20
4
(40, 15, 70)
12
5
(40, 50, 50)
15
6
(50, 70, 40)
12
7
(75, 70, 35)
14
8
(80, 40, 50)
12
9
(40, 55, 30)
10
10
(30, 40, 40)
15We set the coordinates of the starting point as (5, 5, and 5) and the target point as (100, 100, and 100). We compared the proposed FAC-PSO method with EGAM, SA, CABC, and PSO. All parameters are the same as Table3 except that the maximal epoch is changed to 1000. Each algorithm ran 100 times, and the success rate was calculated and shown in Table 7. We found that the FAC-PSO performs best among all algorithms for 3D UCAV path planning.Table 7
Success rates of different algorithms for 3D UCAV.
D
EGAM
SA
CABC
PSO
FAC-PSO
15
65%
9%
64%
65%
74%
20
41%
2%
43%
42%
68%
25
16%
0%
21%
20%
53%


## 6.1. Threat Setting

Set the coordinates of the starting point as (5, 5) and the target point as (100, 100). In the flight course, there exist eight threat areas listed in Table2. Suppose that the codes of initial path are all zeros, which corresponds to a straight line from starting point directly to the target point as shown in Figure 6. Traditional gradient-based methods will guide the 12th–20th nodes of the path to search the upper-left area, and they will finally be misled into the local minima. However, the evolutionary algorithms including GA, PSO, and our proposed FAC-PSO are able to jump from the local minima and search the bottom-right area, where the global minimal point locates in.Table 2
Information of 2D threatening objects.
Index
Position
Radius
1
(10, 30)
14
2
(10, 50)
10
3
(20, 80)
20
4
(40, 15)
12
5
(40, 50)
15
6
(50, 70)
12
7
(75, 70)
14
8
(80, 40)
12Figure 6
Local minima and global minima.


## 6.2. Algorithm Comparison

We compared the proposed FAC-PSO method with elite genetic algorithms with migration (EGAM) [15], simulated annealing (SA) [16], chaotic artificial bee colony (CABC) [8], and standard PSO. The parameters are obtained through trial-and-error method and shown in Table 3. Here, NP means the number of populations/bees/particles corresponding to different algorithms, and MaxEpoch means the maximum iterative epochs. PC, Pm, and Pe of EGAM stand for the crossover probability, mutation probability, and elite probability, respectively. TDF, TI, and TF of SA denote the temperature decrease function, initial temperature, and final temperature, respectively. NF in CABC represents the number of foods.Table 3
Parameters of algorithms.
Algorithm
Parameter setting
EGAM
N
P
=
20; MaxEpoch = 100; PC=0.8; Pm=0.1; Pe=0.1; and migration interval = 20.
SA
N
P
=
20; MaxEpoch = 100; TDF = “exponential”; TI=100, and TF=0.
CABC
N
P
=
20; MaxEpoch = 100; and NF=10.
PSO
N
P
=
20; MaxEpoch = 100; vmax=1; ω=0.6; c1=1; and c2=1.
FAC-PSO
N
P
=
20; MaxEpoch = 100; vmax=1; ωi=0.9; ωf=0.4; c1i=2.5; c1f=0.5, c2i=0.5; and c2f=2.5.Each algorithm ran 100 times, and the success rate was calculated and shown in Table4. It indicates that the proposed FAC-PSO show slight superiority to other algorithms when D=10. As the D increases, the FAC-PSO shows more robustness compared to other algorithms. It should be noted that a larger D makes the search space larger, which leads to the success rate of all the algorithms decreasing.Table 4
Success rates of different algorithms for 2D UCAV.
D
EGAM
SA
CABC
PSO
FAC-PSO
10
78%
22%
80%
75%
87%
15
66%
12%
67%
71%
85%
20
53%
3%
59%
56%
80%We takeD=20 as an example, choose a typical run and show the convergence plot in Figure 7. It indicates that the proposed FAC-PSO was trapped into local minima at about 42 epochs but it jump out at about 45th epoch. Conversely, the EGAM, SA, CABC, and PSO were stagnated in the local minima over all 100 epochs.Figure 7
A typical convergence plot of different algorithms.The final searched paths of the four algorithms are shown in Figure8. It indicates that our proposed FAC-PSO found the global best path of the algorithm, while the other four algorithms failed at this run.Planned path of (a) EGAM; (b) SA; (c) CABC; (d) PSO; and (e) FAC-PSO.
(a)
(b)
(c)
(d)
(e)


## 6.3. Time Comparison

Computation time is another important factor used to evaluate the algorithm. Since a failed run usually takes little time due to early stagnation, we only consider the success runs. The average computation times of each algorithm of different sizes ofD are shown in Table 5. It indicates that the proposed algorithm takes the least time in spite of the size of D; moreover, the SA takes the second least time for calculation. The most time-consuming algorithm is the CABC.Table 5
Average computation time (s).
D
EGAM
SA
CABC
PSO
FAC-PSO
10
12.3
11.6
14.6
13.0
10.2
15
12.9
13.8
15.3
14.7
11.3
20
14.5
13.6
16.8
14.9
13.7


## 6.4. Dynamic Path Planning

The aforementioned paths are static ones which are determined by a beforehand-known map and threat information, but the UCAV usually meets unforeseen threats in actual flight course, so they must possess dynamic path-planning ability. When UCAV detects instantaneous or moving threat, it must replan the path so as to avoid the new arisen threat by revising the former path.Suppose that all the threatening areas can move randomly, then, the flight path of UCAV should change after each move according to the current threat positions. The UCAV paths by the proposed FAC-PSO at steps 0, 5, 10, and 15 are shown in Figure9, which imply the feasibility of FAC-PSO under moving threatening conditions.All threatening obstacles are moving for dynamic path planning: (a) step 0; (b) step 5; (c) step 10; and (d) step 15.
(a)
(b)
(c)
(d)


## 6.5. 3D Path Planning

We applied our method to 3D UCAV path planning. First, we generate a cube (100 × 100 × 100). Second, we generated 10 threats, and their coordinates and radii are listed in Table6.Table 6
Information of 3D threatening objects.
Index
Position
Radius
1
(10, 30, 30)
14
2
(10, 50, 20)
10
3
(20, 80, 40)
20
4
(40, 15, 70)
12
5
(40, 50, 50)
15
6
(50, 70, 40)
12
7
(75, 70, 35)
14
8
(80, 40, 50)
12
9
(40, 55, 30)
10
10
(30, 40, 40)
15We set the coordinates of the starting point as (5, 5, and 5) and the target point as (100, 100, and 100). We compared the proposed FAC-PSO method with EGAM, SA, CABC, and PSO. All parameters are the same as Table3 except that the maximal epoch is changed to 1000. Each algorithm ran 100 times, and the success rate was calculated and shown in Table 7. We found that the FAC-PSO performs best among all algorithms for 3D UCAV path planning.Table 7
Success rates of different algorithms for 3D UCAV.
D
EGAM
SA
CABC
PSO
FAC-PSO
15
65%
9%
64%
65%
74%
20
41%
2%
43%
42%
68%
25
16%
0%
21%
20%
53%


## 7. Conclusions

In this study, a novel FAC-PSO approach for UCAV path planning was proposed. We first investigate the path encoding strategy and then construct the cost function which combines the threat cost and fuel cost simultaneously. The FAC-PSO algorithm was proposed utilizing the fitness-scaling, the adaptive mechanism, and the ergodicity and irregularity of the chaos. Compared to standard PSO, the FAC-PSO is more powerful at jumping out of local minima as well as speeding up the procedures of finding the global optimal minima.The simulation results show that the proposed FAC-PSO excels EGAM, SA, CABC, and PSO algorithms with respect to success rate and computation time. We extended our experiment to 2D dynamic path planning and 3D path planning. All prove the superiority of FAC-PSO. Therefore, it is a feasible and effective way for UCAV path planning.



---

*Source: 705238-2013-07-25.xml*