Page 99 - Innovations in Intelligent Machines

UAV Path Planning Using Evolutionary Algorithms 89
After the evaluation of each individual’s fitness function, operators are
applied to the population, simulating the according natural processes. Applied
operators include various forms of recombination, mutation and selection,
which are used in order to provide the next generation chromosomes. The
first classic operator applied to the selected chromosomes is the one-point
crossover scheme. Two randomly selected chromosomes are divided in the
same (random) position, while the first part of the first one is connected to
the second part of the second one and vice-versa. The crossover operator is
used to provide information exchange between different potential solutions to
the problem.
The second classic operator applied to the selected chromosomes is the uni-
form mutation scheme. This asexual operator alters a randomly selected gene
of a chromosome. The new gene takes its random value from the constrained
space, determined in the beginning of the process. The mutation operator is
used in order to introduce some extra variability into the population.
The resulting intermediate population is evaluated and a fitness function is
assigned to each member of the population. Using a selection procedure (diff-
erent for each type of EA) the best individuals of the intermediate population
(or the best individuals of the intermediate and the previous population) will
form the next generation. The process of a new generation evaluation and
creation is successively repeated, providing individuals with high values of
fitness function.

2.3 The Solid Boundary Representation

In the simulation results that will be presented the terrain where UAVs fly is
represented by a meshed 3-D surface, produced using mathematical functions
of the form

2
z (x, y)=sin (y + a)+ b · sin (x)+ c · cos d · x + y 2

2
+ e · cos (y)+ f · sin f · x + y 2 + g · cos (y) , (7)
where a, b, c, d, e, f, g are constants experimentally defined, in order to
produce either a surface with mountains and valleys (as shown in Fig. 2) or a
maritime environment with islands close to each other (as shown in Fig. 6).
A graphical interface has been developed for the visualization of the terrain
surface, along with the path lines [23]. The corresponding interface deals with
different terrains produced either artificially or based on real geographical
data, providing an easy verification of the feasibility and the quality of each
solution. The path-planning algorithm considers the boundary surface as a
group of quadratic mesh nodes with known coordinates.