Page 95 - Innovations in Intelligent Machines

UAV Path Planning Using Evolutionary Algorithms 85
predetermined target in an unknown environment; the produced trajectory
consists of smaller B-Spline curves smoothly connected with each other. For
both off-line and on-line planners, the problem is formulated as an optimiza-
tion one; each objective function is formed as the weighted sum of different
terms, which take into account the various objectives and constraints of the
corresponding problem. Constraints are formulated using penalty functions.
Changwen Zheng et al. [15] proposed a route planner for UAVs, based
on evolutionary computation, which can be used to plan routes for either
single or multiple vehicles. The flight route consists of straight-line segments,
connecting the way points from the starting to the goal points. A real coded
chromosome representation is used; for each way point its physical coordinates
are used as design variables, along with a state variable, which provides infor-
mation on the feasibility of the corresponding way point and the feasibility
of the route segment connecting the point to the next one. The cost func-
tion of flight route penalizes the length of the route, penalizes flight routes at
high altitudes and routes that come dangerously close to known ground threat
sites. The imposed constraints on route segments are relevant to: minimum
route leg length, maximum route distance, minimum flying height, maximum
turning angle, maximum climbing/diving angle, simultaneous arrival at tar-
get location and no collision between vehicles. The route planning problem
is formulated as the problem of minimization of the cost function under the
aforementioned constraints.
In [8] a multi-task assignment problem for cooperating UAVs is formulated
as a combinatorial optimization problem. A Genetic Algorithm is utilized for
assigning the multiple agents to perform multiple tasks on multiple targets.
The algorithm allows efficiently solving this NP-hard problem and, addition-
ally, allows taking into account requirements such as task precedence and
coordination, timing constraints, and flyable trajectories. The performance
metric for the optimization problem is defined as the cumulative distance
traveled by the vehicles to perform all of the required tasks; the objective is
to minimize this metric subject to the above requirements. Integer encoding
is used for the chromosomes, which are composed of two rows; the first row
presents the assignment of a vehicle to perform a task on the target appear-
ing on the second row. The algorithm was compared to a stochastic random
search and a deterministic branch and bound search methods and found to
provide near optimal solutions considerably faster than the other methods.

1.4 Outline of the Current Work

The following scenario was considered in this work: Assuming a number of
UAVs at different known initial locations, the issue is to produce 2-D tra-
jectories, with a desirable velocity distribution along each trajectory, reach-
ing a common target under specific coordination and route constraints. The
constraints and objectives refer to: minimum path lengths, collision avoid-
ance between the flying vehicles and the ground, predefined minimum and