Page 91 - Innovations in Intelligent Machines

UAV Path Planning Using Evolutionary Algorithms 81
• Stealth, in order to minimize the probability of detection by hostile radar,
by flying along a route which keeps away from possible threats and/or has
a lower altitude to avoid radar detection.
• Physical feasibility, which refers to the physical (or technology) limitations
from the use of UAVs, such as limited range, minimum turning angle,
minimum and maximum speed etc.
• Performance of mission, which imposes special requirements, including
maximum turning angle, maximum climbing/diving angle, minimum and/
or maximum flying altitude and specific approaching angle to the target
point.
• Cooperation between UAVs in order to maximize the possibility of mission
accomplishment.
• Real-time implementation, which asks for computationally efficient
algorithms.
The characteristics above imply special issues that have to be consi-
dered for an efficient modeling of the (single or multiple) UAV path planning
problems.

Path modeling:
The simpler way to model an UAV path is by using straight-line segments
that connect a number of way points, either in 2D or 3D space [12, 15]. This
approach takes into account the fact that in typical UAV missions the shortest
paths tend to resemble straight lines that connect way points with starting
and target points and the vertices of obstacle polygons. Although way points
can be efficiently used for navigating a flying vehicle, straight-line segments
connecting the corresponding way points cannot efficiently represent the real
path that will be followed by the vehicle. As a result, these simplified paths
cannot be used for an accurate simulation of the movement of the UAV in
an optimization procedure, unless a large number of way points is adopted.
In that case the number of design variables in the optimization procedure
explodes, along with the computation time. The problem becomes even more
difficult in the case of cooperating flying vehicles.
In [16], paths from the initial vehicle location to the target location
are derived from a graph search of a Voronoi diagram that is constructed
from the known threat locations. The resulting paths consist of line segments.
These paths are subsequently smoothed around each way point, in order to
provide feasible trajectories within the dynamic constraints of the vehicle. A
great advantage of the Voronoi diagram approach is that it reduces the path
planning problem from an infinite dimensional search, to a finite-dimensional
graph search. This important abstraction makes the path planning problem
feasible in near-real time, even for a large number of way points [16].
Vandapel et al. [17] used a network of free space bubbles to model the
path of small scale UAVs, in order to solve the path planning problem of
autonomous unmanned aerial navigation below the forest canopy. Using a