Page 101 - Innovations in Intelligent Machines

UAV Path Planning Using Evolutionary Algorithms 91
points located inside the solid boundary; consequently, non-feasible curves
with fewer points inside the solid boundary show better fitness than curves
with more points inside the solid boundary. Term f 2 is the length of the
curve (non-dimensional with the distance between the starting and destina-
tion points) used to provide shorter paths.
Term f 3 is designed to provide flight paths with a safety distance from
solid boundaries
nline nground
2
f 3 = 1/ (d i,j /d safe ) , (9)
i=1 j=1
where nline is the number of discrete curve points, nground is the number of
discrete mesh points of the solid boundary, d i,j is the distance between the
corresponding nodes and curve points, while d safe is a safety distance from the
solid boundary. Term f 4 is designed to provide curves with a prescribed mini-
mum curvature radius [23]. Weights w i are experimentally determined, using
as criterion the almost uniform effect of the last three terms in the objective
function. Term w 1 f 1 has a dominant role in Eq. 8 providing feasible curves in
few generations, since path feasibility is the main concern. The minimization
of Eq. 8, through the EA procedure, results in a set of B-Spline control points,
which actually represent the desired path.
Initially, the starting and ending path-line points are determined, along
with the direction of flight. The limits of the physical space, where the vehicle
is allowed to fly (upper and lower limits of their Cartesian coordinates), are
also determined, along with the ground surface. The determined initial flight
direction is used to compute the third fixed point close to the starting one;
its position is along the flight direction and at a pre-fixed distance from the
starting point.
The EA randomly produces a number of chromosomes to form the initial
population. Each chromosome contains the physical coordinates of the free-
to-move B-Spline control points. Using Eqs. 1 to 6, with a constant step of
parameter u, a B-Spline curve is calculated for each chromosome of the popu-
lation in the form of a sequence of discrete points. Subsequently, each B-Spline
is evaluated, using the aforementioned criteria, and its objective function is
calculated. Using the EA procedure, the population of candidate solutions
evolves during the generations; at the last generation the population member
with the smallest value of objective function is the solution to the problem
and corresponds to the path line with the best characteristics according to
the aforementioned criteria.
The simulation runs have been designed in order to search for path lines
between “mountains”. For this reason, an upper ceiling for flight height has
been enforced, which is represented in the graphical environment by the hor-
izontal section of the terrain. A typical simulation result is demonstrated
in Fig. 2.