132 IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, VOL. 9, NO.

1, FEBRUARY 2013

Comparison of Parallel Genetic Algorithm and

Particle Swarm Optimization for
Real-Time UAV Path Planning
Vincent Roberge, Mohammed Tarbouchi, and Gilles Labonté

Abstract—The development of autonomous unmanned aerial that the complexity of the problem has grown. To cope with
vehicles (UAVs) is of high interest to many governmental and this complexity, researchers have slowly moved from using
military organizations around the world. An essential aspect of deterministic algorithms to using nondeterministic algorithms
UAV autonomy is the ability for automatic path planning. In this
paper, we use the genetic algorithm (GA) and the particle swarm
[2].
optimization algorithm (PSO) to cope with the complexity of the As an example, the authors of [3] proposed the use of a vi-
problem and compute feasible and quasi-optimal trajectories for brational genetic algorithm (GA) to improve the exploration and
fixed wing UAVs in a complex 3D environment, while considering better avoid local minima when searching for an optimal path.
the dynamic properties of the vehicle. The characteristics of the In [4], Bezier curves are used with a GA to produce trajecto-
optimal path are represented in the form of a multiobjective cost ries that respect a minimum curvature and torsion in an effort
function that we developed. The paths produced are composed
of line segments, circular arcs and vertical helices. We reduce to better consider the dynamic properties of the UAV. The au-
the execution time of our solutions by using the “single-program, thors of [5] also use a GA, but add the concept of artificial im-
multiple-data” parallel programming paradigm and we achieve mune system in order to maintain superior population diversity
real-time performance on standard commercial off-the-shelf throughout the evolution process. In [6], the authors use a PSO
multicore CPUs. After achieving a quasi-linear speedup of 7.3 to compute the shortest path between targets in the context of
on 8 cores and an execution time of 10 s for both algorithms, we surveillance UAV. In [7], a comparison of the PSO, the phase
conclude that by using a parallel implementation on standard
multicore CPUs, real-time path planning for UAVs is possible. angle-encoded PSO and the quantum-behaved PSO in the con-
Moreover, our rigorous comparison of the two algorithms shows, text of UAV path planning is presented.
with statistical significance, that the GA produces superior trajec- In this paper, we use two nondeterministic algorithms to de-
tories to the PSO. velop an operational path planning module for fixed wing UAVs.
Index Terms—Genetic algorithm (GA), path planning, particle Our research work presents three important contributions. First,
swarm optimization (PSO), parallel computing, unmanned aerial we propose a comprehensive cost function which includes both
vehicles (UAVs). the optimization and the feasibility criteria. This allows us to use
a generic optimization algorithm (without modification) as the
I. INTRODUCTION search algorithm. In our case, we use the GA and the PSO, but
these could easily be replaced by other algorithms. Second, we
T HE PATH planner is a key element of the unmanned aerial
vehicle (UAV) autonomous control module [1]. It allows
the UAV to autonomously compute the best path from a start
present a technique to parallelize both the GA and the PSO while
minimizing the communication between the processes in order
point to an end point. Whereas commercial airlines fly constant to achieve a near linear speedup and fully exploit the computing
prescribed trajectories, UAVs in operational areas have to travel power of today’s multicore CPUs. Finally, we offer a statisti-
constantly changing trajectories that depend on the particular cally significant comparison between the quality of the trajecto-
terrain and conditions prevailing at the time of their flight. ries generated by our GA-based and PSO-based path planners.
In the past, the best path has been associated with the shortest Both algorithms have recently been widely used for UAV path
path and deterministic search algorithms were used to find the planning [3]–[8] and [9]. However, to our knowledge, there ex-
very shortest path. The definition of the problem has since ists no rigorous comparison between the two algorithms when
evolved and the best path is now associated with the path applied to this particular problem. The results we present in this
that minimizes the distance travelled, the average altitude, the paper provide clear insight as to which of the two optimization
fuel consumption, the radar exposure, etc. These are a few algorithms is preferable for UAV path planning in complex 3D
examples of the factors to be considered and clearly show environments.
Nondeterministic algorithms have been used to cope with
Manuscript received October 21, 2011; revised December 07, 2011, February
the complexity of UAV path planning; however, they could po-
14, 2012; accepted April 02, 2012. Date of publication May 10, 2012; date of tentially produce, on some occasions, poor solutions. A sub-
current version December 19, 2012. Paper no. TII-11-646.R2. sequent re-execution of the algorithm would then be required.
V. Roberge and M. Tarbouchi are with the Department of Electrical and Com-
puter Engineering, Royal Military College of Canada, Kingston, ON K7K7L6,
It is important to note that the path planner is a submodule of
Canada (e-mail: [Link]@[Link]; tarbouchi-m@[Link]). an UAV autonomous control system that includes a decision-
G. Labonté is with the Department of Mathematics and Computer Science, making module to handle such situations [1]. For this reason,
Royal Military College of Canada, Kingston, ON K7K7L6, Canada (e-mail: this paper does not cover the decision making process that would
labonte-g@[Link]).
Digital Object Identifier 10.1109/TII.2012.2198665 be required in the event of a poor trial run.

1551-3203/$31.00 © 2012 British Crown Copyright

ROBERGE et al.: COMPARISON OF PARALLEL GA AND PSO FOR REAL-TIME UAV PATH PLANNING 133

Fig. 1. UAV trajectory in a 3D environment. The red dots represent the way-
points of the UAV trajectory, the blue line represents the line segments con-
necting the waypoints and the red cylinders represents the danger zones to be
avoided.

Fig. 2. 2D matrix representation of the terrain displayed on Fig. 1. The number

in each cell represents the terrain elevation at that location.
The remainder of this paper is organized into sections.
Section II provides details of the representation of the terrain row represents the coordinates of the th waypoint,
and the encoding of the trajectories. We present in Section III as shown in (2). The trajectories are flown at constant speed
the cost function we developed to evaluate the quality of can-
didate trajectories. Sections IV and V, respectively, discuss the
use of the GA and the PSO to find trajectories that optimize (2)
the cost function. Section VI briefly presents the method we
used to smooth the generated path into a feasible path with no
discontinuity in the velocity. Section VII explains the method
used to parallelize the GA and the PSO in order to allow III. COST FUNCTION
real-time path planning. Finally, we compare the quality of the
trajectories produced by the GA and the PSO in Section VIII. As previously stated, searching for the best path is often as-
sociated with searching for the shortest path. This is the case
when solving the Traveling Salesperson Problem (TSP), which
II. ENVIRONMENT AND TRAJECTORY REPRESENTATION consists of finding the shortest path that visits all the given cities
The first step of path planning is to discretize the world space only once. In the case of UAV path planning, the optimal path is
into a representation that will be meaningful to the path planning more complex and includes many different characteristics. To
algorithm. This representation is closely related to a search algo- take into account these desired characteristics, a cost function
rithm and some algorithms will only perform well when coupled is used and the path planning algorithm becomes a search for a
with a specific environment representation. An overview of the path that will minimize the cost function. The cost of a path de-
performance of different representations used with different al- creases with the degree to which the desired characteristics are
gorithms is presented in [10]. In our implementation (see Figs. 1 being fulfilled. A path that fulfills all the characteristics to a high
and 2), we use an approximate cell decomposition of the terrain degree would result in a low cost. We define our cost function
using a 2D grid where each element of the matrix represents as follows:
the elevation of the terrain. This representation allows us to use
digital elevation maps freely available from the GeoBase [11]
repository with no further processing. Our representation of the (3)
environment also allows for the definition of cylindrical danger where penalizes longer paths, penalizes paths
zones (or no-fly zones) to be kept in a separate matrix where with a higher average altitude, penalizes paths
each row represents the coordinates and the diameter going through danger zones, penalizes paths requiring
of the th cylinder as shown in (1). Complex no-fly zones can more power than the maximum available power of the UAV,
be built by partially juxtaposing multiple cylinders penalizes paths colliding with the ground, penal-
izes paths requiring more fuel than initially available in the UAV,
and finally, penalizes paths that cannot be smoothed
(1) using circular arcs. and are op-
timization criteria and are used to improve the quality of the
trajectory. Each of those three terms are defined to be in the
The trajectories generated by the optimization algorithm are range of [0, 1]. On the other hand, , and
composed of line segments and encoded in a matrix where each are feasibility criteria that must be satisfied for the
134 IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, VOL. 9, NO. 1, FEBRUARY 2013

final trajectory to be valid. Each feasibility criterion is defined The term associated with a required power higher than the
to be equal to 0, when it is respected, or in the range available power of the UAV is defined as follows:
when it is not. By choosing a greater than 3, we ensure that
unfeasible trajectories always have a cost greater than any fea-
sible ones. It is important to note that our implementation de-
fines as an optimization criterion in the sense that (10)
it is preferable to avoid danger zones but not necessarily essen-
tial to the survival of the UAV. therefore
This would simulate the scenario where the UAV should (11)
avoid enemy radars identified by the danger zones. If used in a
different scenario, our cost function could easily be modified where is the sum of the lengths of the line segments
to include as a feasibility criterion ensuring forming the trajectory which require more power than the avail-
no danger zones are violated. Moreover, although we define able power of the UAV, is the total length of the trajec-
danger zones as cylindrical regions, our approach also allows tory and is the penalty constant. This constant must be higher
the representation of complex zones by overlapping multiple than the cost of the worst feasible trajectory which would have,
cylinders. based on our cost function, a cost of 3. By adding this penalty ,
In our costs function, the term associated with the length of a we separate nonfeasible solutions from the feasible ones. The
path is defined as follows: power required and available depends on the altitude and the
current weight of the UAV and is computed using the approach
presented in [12] and based on [13].
(4) The term associated with ground collisions is defined as fol-
lows:
therefore
(5)

where is the length of the straight line connecting the

starting point and the end point and is the actual
length of the trajectory. (12)
The term associated with the altitude of the path is defined as therefore
follows: (13)

where is the total length of the subsections of the

(6) trajectory which travels below the ground level and is the
total length of the trajectory. We compare the altitude of the
therefore terrain and the altitude of the trajectory in a discreet way using
(7) the Bresenham’s line drawing algorithm [14].
The term associated with an insufficient quantity of fuel avail-
where is the upper limit of the elevation in our search able is defined as follows:
space, is the lower limit and is the average altitude
of the actual trajectory. and are respectively set to
be slightly above the highest and lowest points of the terrain.
The term associated with the violation of the danger zones is (14)
defined as follows:
therefore
(15)
(8)
where is the quantity of fuel required to fly the imaginary
with straight segment connection the starting point to the end
(9) point is the actual amount of fuel needed to fly the
trajectory, is the initial quantity of fuel onboard the UAV.
where is the total number of danger zones, is The quantity of fuel required is computed using the approach
the total length of the subsections of the trajectory which go presented in [12] and based on [13].
through danger zones and is the diameter of the danger zone Because our representation defines a path as a series of line
. This definition ensures that a trajectory passing through a segments, the trajectory generated includes discontinuity in the
single danger zone is severely penalized on a map containing velocity at the connections of those segments. As will be ex-
few danger zones and lightly penalized on a map containing plained later in Section VI, we remove those discontinuity using
many danger zones. Since it is possible for to be circular constructions in the last step of our path planning algo-
larger than (as in the case of a dog-leg path through a rithm. However, to ensure the smoothing of the optimal solution
single danger zone), we arbitrarily bound to 1. found is possible, we verify the feasibility of the smoothing in
ROBERGE et al.: COMPARISON OF PARALLEL GA AND PSO FOR REAL-TIME UAV PATH PLANNING 135

our cost function. So finally, the term associated with the im-
possible smoothing of the path is defined as follows:

(16)

therefore
(17)

where is the number of connection that cannot

be smoothed using circular constructions as explained in
Section VI and is the total number of connections in the
trajectory.
During the optimization phase of our path planner algorithm,
the search engine will be used to find a solution which mini-
mize the cost function and, therefore, find a trajectory that best
satisfies all the qualities represented by this cost function. Our
cost function represents a specific scenario where the optimal
path minimizes the distance travelled, the average altitude (to
increase the stealthiness of the UAV) and avoids danger zones,
while respecting the UAV performance characteristics. This
cost function is highly complex and demonstrates the power of
our path planning algorithm. However, this cost function could Fig. 3. Flowchart of the genetic algorithm.
easily be modified and applied to a different scenario.

IV. GENETIC ALGORITHM (GA) waypoint within the 3D neighborhood of its midpoint. Simi-
The GA is a population based nondeterministic optimization larly, we implemented the modification operator by randomly
method that was developed by John Holland in the 1960s and selecting one of the waypoints of the trajectory and moving it
first published in 1975 [15]. Based on the genetic theory of to a random location within its 3D neighborhood. The size of
Darwin evolution, the GA simulates the evolution of a popu- this neighborhood is initially set based on the size of the search
lation of solutions to optimize a problem. Similarly to living space and is linearly reduced throughout the evolution process
organisms adapting to their environment over the generations, improving the exploration at the beginning of the execution and
the solutions in the GA adapt to a fitness function over an itera- the refinement towards the end. At every generation, each chil-
tive process using biology-like operators such as the crossovers dren solution is subject to a mutation based on the mutation rate
of chromosomes, the mutations of genes and the inversions of parameter. The type of mutation is randomly selected between
genes. In recent years, the GA has been used for a wide range of the three we implemented and the mutation affects the solu-
applications such as the design of minimal phase digital filters tion in a single point. Our implementation also uses the con-
[16] and the optimization of surface grinding process [17]. In cept of elitism when replacing the old generation with the new
this work, we use the GA to simulate the evolution of a popu- one in order to improve convergence. The flowchart of the GA
lation of trajectories adapting to the cost function defined in the is shown in Fig. 3 and the different genetic operators used, in
previous section. Fig. 4. The parameter values used in our implementation of the
In our implementation, the initial trajectories are randomly GA are listed in Table I. To reflect the good design of our GA
generated within the 3D search space with no consideration of and cost function, we plot in Fig. 5 the cost of the solutions
their feasibility. The fitness of each solution is then evaluated generated by the GA against iterations. At iteration 1, the best
and the mating pool selected favoring fit parents using the sto- solution has a cost of 9.17 and therefore violates a few feasi-
chastic universal sampling method presented in [18]. Children bility constraints. The optimization process rapidly converges
solutions are created from the selected parents using single point and finds a first feasible solution at iteration 30. The refinement
crossover also based on [18]. The children solutions are then of the solutions continues until the maximum number of itera-
subject to the following mutations: addition of a new waypoint, tions is attained. The cost of the best solution at the last iteration
deletion of an existing waypoint and modification of an existing is 0.342.
waypoint. Finally, the parent generation is replaced by the chil-
dren generation and the evolution cycle continues until the ter- V. PARTICLE SWARM OPTIMIZATION (PSO)
mination criterion has been met. Our implementation allows the
user to define the termination criterion as a maximum number The PSO is a population-based nondeterministic optimization
of generations to be simulated (as used in Section VII) or a fixed method that was proposed by Kennedy and Eberhart in 1995
execution time (as used in Section VIII). [19]. Similarly to the GA, the PSO has recently been used in a
We implemented the addition operator by randomly selecting wide range of applications such as the design and optimization
one of the line segments of the trajectory and adding a random of infinite impulse response digital filters [20]. The algorithm
136 IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, VOL. 9, NO. 1, FEBRUARY 2013

TABLE I
ALGORITHM PARAMETER VALUES

Fig. 4. Genetic operators used in our GA: (a) single-point crossover and (b)
mutations: addition, deletion, modification.

Fig. 5. Cost of the solutions generated by our GA at each iteration (256 chro-
mosomes, 300 iterations, for the scenario shown in Fig. 1).

simulates the movement of a swarm of particles in a multidi-

mensional search space progressing towards an optimal solu-
tion. The position of each particle represents a candidate solu-
tion and is randomly initiated. In our implementation, the posi-
tion of a particle represents a complete trajectory using the same
encoding as with the GA. At every step of the iterative process,
the velocity of each particle is individually updated based on the
previous velocity of the particle, the best position ever occupied Fig. 6. Flowchart of the particle swarm optimization.
by the particle (personal influence) and the best position ever
occupied by any particle of the swarm (social influence). In line
with the original PSO [19], our implementation does not allow by the particle; is the best position previously occupied by any
any mutation type operations. As outlined in [21], the equations particle of the swarm; and are vectors of random values
used to compute the velocity and position of a single particle at between 0 and 1; and and are the inertia, the personal in-
iteration are as follows: fluence and the social influence parameters. When searching for
an 8-waypoint trajectory, vectors in (18) and (19) have 24 ele-
(18) ments and the particles are moving in a 24 D search space. Every
(19) element of the particles’ velocity and position are updated
independently as per the two equations. Still based on [21], the
where variables in bold are vectors is the velocity of the par- flow diagram of our implementation of the PSO is displayed in
ticle; is its position; is the best position previously occupied Fig. 6. The parameter values used in our implementation of the
ROBERGE et al.: COMPARISON OF PARALLEL GA AND PSO FOR REAL-TIME UAV PATH PLANNING 137

Fig. 7. Cost of the solutions generated by our PSO at each iteration (256 par-
ticles, 300 iterations, for the scenario shown in Fig. 1). Fig. 10. Speedup achieved by our parallel GA for different work sizes.

TABLE II
COMPUTER SYSTEM USED FOR THE EXPERIMENTAL TEST

Fig. 8. Circular constructions used to smooth the final trajectory and remove
all discontinuity in the velocity (left diagram shows a simple circular arc and
the right diagram shows a connection using two circular arcs and a circle on an
horizontal plane) (reproduced with permission from [22]).

Fig. 11. 3D visualization of the computed path [fictitious map, 25 km , altitude

ranging from 0 to 250 m above mean sea level (AMSL)].

insight of the good design of our GA and PSO, it is not suffi-

cient to compare the two algorithms. A rigorous comparison in
Fig. 9. Execution time of our parallel GA for different work sizes.
presented in Section VIII of this document.

PSO are listed in Table I. Our implementation of the PSO al- VI. PATH SMOOTHING
lows the user to define the termination criterion as a maximum Consistent with solutions proposed in the literature [22]–[24],
number of iterations to be simulated (as used in Section VII) or our solution generates a path composed of line segments. This
a fixed execution time (as used in Section VIII). As we previ- would be sufficient for multidirectional ground robots, but in-
ously did for the GA, we plot in Fig. 7 the cost of the solutions adequate for a fixed-wing UAV. To remove all discontinuities
generated by the PSO against iterations. Compared to the GA, in the velocity, we smooth the final path by connecting the line
the PSO took more iterations before finding the first feasible so- segments with simple circular arcs (when the power available
lution. We also note that the refinement of the best solution is is sufficient) or circles on a horizontal plateau (when the power
less visible than with the GA. This may be caused by a local available is not sufficient to fly a simple circular arc) based on
minimum. Although the cost versus iteration graphs give clear [22], [24], [25], and as shown in Fig. 8. Our final stage module
138 IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, VOL. 9, NO. 1, FEBRUARY 2013

Fig. 12. 3D visualization of the computed path (St-John, NL, Canada, area of Fig. 15. 3D visualization of the computed path (Columbia Icefield, AB,
100 km , altitude ranging from 0 to 246 m AMSL). Canada, area of 269 km , altitude ranging from 1 621 to 3 486 m AMSL).

Fig. 16. 3D visualization of the computed path (Banff, AB, Canada, area of 1
Fig. 13. 3D visualization of the computed path (Lake Louise, AB, Canada, area 360 km , altitude ranging from 1290 to 3079 m AMSL).
of 192 km , altitude ranging from 1 515 to 3 491 m AMSL).

Fig. 17. 3D visualization of the computed path (Jasper, AB, CA, area of 3 717
Fig. 14. 3D visualization of the computed path (Kinbasket lake, BC, Canada, km , altitude ranging from 1020 to 3308 m AMSL).
area of 348 km , altitude ranging from 750 to 2 746 m AMSL).

VII. PARALLEL IMPLEMENTATION

also replaces any line segment requiring more power than avail- We have now discussed all the elements required to build
able with a vertical helix as in [22]. Although smoothing of the a complete path planning module for UAVs. Although the
path is performed after the optimization process, the feasibility generated trajectories are feasible and nearly optimal, the
of this operation is verified in our cost function to ensure the computation time remains too long for real-time applications.
smoothing of the final trajectory is always possible. To address this problem, we developed parallel versions of
ROBERGE et al.: COMPARISON OF PARALLEL GA AND PSO FOR REAL-TIME UAV PATH PLANNING 139

Fig. 18. Flowchart of our parallel genetic algorithm.

our GA and PSO using the “Single-program, multiple-data” CPUs. The flowchart of our parallel GA is shown in Fig. 18.
parallel programming paradigm. Our implementation was Although drawn for two processes, our implementation allows
done in MATLAB™. It can be classified as a multiple-deme any number of processes. Our parallel version of the PSO is
parallel GA where sub-populations evolve independently while not shown in this paper but follows the same principle. The
allowing some level of migration between the demes [26]. In execution time and the speedup of our parallel GA were mea-
our implementation, the migrations occur synchronously, ten sured using the parameters in Table I, on the system described
times throughout the optimization process and involve all the in Table II and are plotted in Figs. 9 and 10. The execution time
solutions. Our approach maintains a good level of collaboration and the speedup of our parallel PSO are not presented here, but
between the subpopulation, minimizes the communication be- almost identical.
tween the processes, offer a better speedup than a master-slave Although we achieved a computation time of 3.63 s for 128
implementation [26] and allows full use of today’s multicore chromosomes and 100 generations, we arbitrarily configured
140 IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, VOL. 9, NO. 1, FEBRUARY 2013

TABLE III different with a 95% confidence. In that case, we can compare
AVERAGE COST OF THE 60 TRAJECTORIES GENERATED FOR EACH the two averages and identify which algorithm performed the
OF THE 40 SCENARIOS USING OUR GA-BASED AND PSO-BASED
PATH PLANNING ALGORITHM (SHOWING RESULTS FOR THE best. Base on the results presented in Table III, we conclude
FIRST 20 SCENARIOS DUE TO SPACE LIMITATION) that:
1) the GA produced trajectories significantly better than those
generated by the PSO for 25 of the 40 scenarios;
2) the PSO produced trajectories significantly better than
those generated by the GA for 3 of the 40 scenarios;
3) the GA and the PSO produced trajectory of similar quality
for 12 of the 40 scenarios.
Based on these results, we conclude that the GA is preferable
to the PSO when solving the path planning problem for UAVs
in a fixed computation time of 10 s on multicore commercial
off-the-shelf processors.

IX. CONCLUSION
This paper presents a path planning solution for UAVs which
considers the dynamic properties of the UAV and the complexity
of a real 3D environment. We used two nondeterministic algo-
rithms, the GA and the PSO, to attack this complexity and pro-
duce solutions in a relatively short computation time. We fur-
ther reduced the execution time by developing parallel versions
of our algorithms. After achieving a quasi-linear speedup of 7.3
on 8 cores and an execution time of 10 s for both algorithms,
we conclude that by using a parallel implementation on stan-
dard multicore CPUs, real-time path planning for UAVs is pos-
our path planning module for a fixed execution time of 10 s. This sible. Moreover, our rigorous comparison of the two algorithms
allows the simulation to continue for few hundreds of genera- shows, with statistical significance, that our implementation of
tions (318 for the GA and 213 for the PSO) and generate very the GA produces superior trajectories than our implementation
high-quality trajectories in a wide range of complex 3D envi- of the PSO when using the same encoding.
ronments. Ten seconds may seem too long for a real-time ap-
plication, but easily allows the UAV to compute the next path, REFERENCES
while flying the current one. As an example, the Global Hawk [1] H. Chen, X.-M. Wang, and Y. Li, “A survey of autonomous control for
(one of the fastest UAVs currently in use) has a cruising speed UAV,” in Proc. 2009 Int. Conf. Artif. Intell. Comput. Intell., 2009, vol.
of 635 km/h and travels 1 764 m in 10 s [13]. Our path planning 2, pp. 267–271.
[2] E. Masehian and D. Sedighizadeh, “Classic and heuristic approaches
module can easily generate trajectories longer than this distance in robot motion planning—A chronological review,” World Academy
and therefore allows computation while in flight. of Science, vol. 29, pp. 101–106, 2007.
[3] P. Y. Volkan, “A new vibrational genetic algorithm enhanced with a
VIII. COMPARISON OF THE GA AND THE PSO Voronoi diagram for path planning of autonomous UAV,” Aerosp. Sci.
Technol., vol. 16, no. 1, pp. 47–55, Jan. 2012.
Finally, we compare the performance of the GA and the PSO [4] D. G. Macharet, A. A. Neto, and M. F. M. Campos, “Feasible UAV
using 40 different scenarios from two fictitious terrain eleva- path planning using genetic algorithms and Bezier curves,” in Proc.
SBIA’10, Berlin, Germany, 2010, pp. 223–232.
tion maps and six real terrain elevation maps from the Canadian [5] Z. Cheng, Y. Sun, and Y. Liu, “Path planning based on immune genetic
coast, the Canadian Rockies and the Canadian ice fields. The algorithm for UAV,” in Proc. Int. Conf. Electric Inform. Control Eng.,
digital elevation maps for the six real terrains were taken from 2011, pp. 590–593.
[6] Y. Bao, X. Fu, and X. Gao, “Path planning for reconnaissance UAV
the GeoBase repository [11]. Each scenario has a unique start based on particle swarm optimization,” in Proc. 2nd Int. Conf. Comput.
and finish point and a varied number of danger zones. Six of [Link] Comput., CINC’10, Wuhan, China, 2010, vol. 2, pp.
the 40 scenarios are shown in Figs. 11–17. These scenarios are 28–32.
[7] Y. Fu, M. Ding, and C. Zhou, “Phase angle-encoded and quantum-be-
representative of the complexity and realism of all 40 scenarios haved particle swarm optimization applied to three-dimensional route
used. The average costs of 60 trajectories generated using our planning for UAV,” IEEE Trans. Syst., Man, Cybern., vol. 42, no. 2, pp.
parallel GA and parallel PSO for a fixed computation time of 511–526, 2012.
[8] D. M. Pierre, N. Zakaria, and A. J. Pal, “Master-slave parallel vector-
10 s and population size of 256 are listed in Table III. Each run evaluated genetic algorithm for unmanned aerial vehicle’s path plan-
used a different initial random population of solutions. To com- ning,” in Proc. Int. Conf. Hybrid Intell. Syst., 2011, pp. 517–521.
pare our implementations of the GA and the PSO, we used the [9] G. Wang, Q. Li, and L. Guo, “Multiple UAVs routes planning based on
particle swarm optimization algorithm,” in Proc. 2nd Int. Symp. Inform.
T-test [27] on the cost distributions of the trajectories obtained Eng. Electronic Commerce, 2010, pp. 1–5.
by each algorithm. In Table III, the p-value obtained by the [10] N. Sariff and N. Buniyamin, “An overview of autonomous mobile robot
T-test represents the probability that the difference between the path planning algorithms,” in Proc. 4th Student Conf. Res. Develop.,
Piscataway, NJ, USA, 2006, pp. 183–188.
two averages is due to chance. In other words, when the p-value [11] GeoBase—Canadian Digital Elevation Data Accessed: Apr. 3, 2012.
obtained is lower than 0.05, the two averages are significantly [Online]. Available: [Link]
ROBERGE et al.: COMPARISON OF PARALLEL GA AND PSO FOR REAL-TIME UAV PATH PLANNING 141

[12] G. Labonté, “Mathematical relations to analyze aircraft performance Vincent Roberge received the [Link]. and [Link].
for trajectory planning” Defense Research and Development, Ottawa, degrees from the Royal Military College of Canada,
ON, Canada, Contract Rep. CR 2010-249, Dec. 2010. Kingston, ON, Canada, in 2005 and 2010, respec-
[13] J. D. J. Anderson, Introduction to Flight, 6th ed. New York: McGraw- tively. Currently, he is working towards the Ph.D. de-
Hill, 2008. gree at the Department of Electrical and Computer
[14] J. Bresenham, “Algorithm for computer control of a digital plotter,” Engineering, the Royal Military College of Canada.
IBM Syst. J., vol. 4, no. 1, pp. 25–30, 1965. In July 2011, he joined the Department of Elec-
[15] J. H. Holland, Adaptation in Natural and Artificial Systems. Cam- trical and Computer Engineering, Royal Military
bridge, MA: MIT Press, 1975. College of Canada, where he is currently Lecturer .
[16] A. Slowik, “Application of evolutionary algorithm to design minimal His current research interests include parallel com-
phase digital filters with non-standard amplitude characteristics and fi- putation, optimization and real-time applications.
nite bit word length,” Bull. Polish Acad. Sci.: Tech. Sci., vol. 59, no. 2,
pp. 125–135, 2011.
[17] A. Slowik and J. Slowik, “Multi-objective optimization of surface
grinding process with the use of evolutionary algorithm with remem- Mohammed Tarbouchi received the [Link]. and
bered Pareto set,” Int. J. Adv. Manuf. Technol., vol. 37, no. 7–8, pp. Ph.D. degrees from Laval University, Laval, QC,
657–669, 2008. Canada, in 1993 and 1997, respectively.
[18] X. Yu and M. Gen, Introduction to Evolutionary Algorithms. London, In September 1997, he joined the Department of
U.K.: Springer, 2010. Electrical and Computer Engineering, Royal Military
[19] J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proc. College of Canada, Kingston, ON, where he is cur-
IEEE Int. Conf. Neural Networks, Perth, WA, Australia, 1995, vol. 4, rently an Associate Professor. His current research
pp. 1942–1948. interests include analysis and design of electrical ma-
[20] A. Slowik and M. Bialko, “Design and optimization of ir digital filters chines, variable speed drives and fault diagnosis of
with non-standard characteristics using particle swarm optimization al- electric machines.
gorithm,” in Proc. ICECS’07, Piscataway, NJ, 2007, pp. 162–165.
[21] M. Clerc, Particle Swarm Optimization. Paris, France: Lavoisier,
2005.
[22] G. Labonté, “On the construction of dynamically feasible aircraft tra-
jectories using series of line segments,” Comput. Intell. Res. Lab, RMC, Gilles Labonté received the [Link]. and [Link]. degrees
Nov. 2009. [Online]. Available: [Link] in physics from the Université de Montréal, Mon-
internal-publications/58-g treal, QC, Canada, and the Ph.D. degree in theoretical
[23] I. Hasircioglu, H. R. Topcuoglu, and M. Ermis, “3-D path planning physics from the University of Alberta, Edmonton,
for the navigation of unmanned aerial vehicles by using evolutionary AB, Canada.
algorithms,” in Proc. 10th Annu. Conf. Genetic Evol. Comput., Atlanta, He is presently a Professor with the Department of
GA, 2008, pp. 1499–1506. Mathematics and Computer Science and the Depart-
[24] E. P. Anderson, R. W. Beard, and T. W. McLain, “Real-time dynamic ment of Electrical and Computer Engineering, Royal
trajectory smoothing for unmanned air vehicles,” IEEE Trans. Control Military College of Canada. He has contributed
Syst. Technol., vol. 13, no. 3, pp. 471–477, May 2005. to relativistic quantum mechanics, symbolic alge-
[25] C. L. Bottasso, D. Leonello, and B. Savini, “Path planning for au- braic computations, artificial neural networks and
tonomous vehicles by trajectory smoothing using motion primitives,” soft-computing. He presently works on automatic target recognition, intelligent
IEEE Trans. Control Syst. Technol., vol. 16, no. 6, pp. 1152–1168, control systems for unmanned vehicles, and applications of the theory of
2008. complex systems.
[26] S. N. Sivanandam and S. N. Deepa, Introduction to Genetic Algo-
rithms. New York: Springer, 2008.
[27] MATLAB Two-Sample T-Test Accessed Apr. 3, 2012. [Online]. Avail-
able: [Link]