Page 92 - Innovations in Intelligent Machines

82 I.K. Nikolos et al.
priori aerial data scans of forest environments, they compute a network of
free space bubbles, which form safe paths within the forest environment.
Their approach is tailored to the problem of small scale UAVs and can be
decomposed into two steps: 1) the scene made of 3-D points is segmented
into three classes (ground, vegetation and tree trunk-branches). 2) A path
planning algorithm explores the segmented environment and computes con-
nected obstacle-free areas, which will subsequently form a network of tunnels
intersecting at some locations.
An alternative approach is to model the UAV dynamics using the Dubins
car formulation [18]. The UAV is assumed to fly with constant altitude,
constant flight speed and to have continuous time kinematics [19]. This
approach cannot efficiently model real world scenarios, which may include
3D terrain avoidance or following of stealthy routes. However, this approach
seems to be sufficient enough for task assignment purposes to cooperating
UAVs flying at safe altitudes [19, 8, 20].
B-Spline curves have been used for trajectory representation in 2-D
environments (simulated annealing based path line optimization, combined
with fuzzy logic controller for path tracking) [21], and in 3-D environments
(Evolutionary Algorithm based path line optimization for a UAV over rough
terrain) [22, 23]. B-Spline curves need a few variables (the coordinates of
their control points) in order to define complicated 2D or 3D curved paths,
providing at least first order derivative continuity. Each control point has a
very local effect on the curve’s shape and small perturbations in its position
produce changes in the curve only in the neighborhood of the repositioned
control point.

Cooperation Scenarios:

Path planning algorithms were initially developed for the solution of the prob-
lem of a single UAV. The increasing interest for missions involving cooperating
UAVs resulted in the development of algorithms that take into account the
special characteristics and constraints of such missions. The related works
present various scenarios, formulations and approaches connected to cooper-
ating UAV path planning problems. Some of the most representative scenarios
are presented below.
Beard et al. [16] considered the scenario where a group of UAVs is required
to transition through a number of known target locations, with a number
of threats in the region of interest. Some threats are known a priori, some
others “pop up” or become known only when a UAV flies near them. It is
desirable to have multiple UAVs arrive on the boundary of each target’s radar
detection region simultaneously. Collision avoidance is ensured by supposing
that individual UAVs fly at different pre-assigned altitudes. In this work the
problem is decomposed in several sub-problems: a) The assignment problem
of a number of UAVs to a number of targets in a way that each target has
multiple UAVs assigned to it, with a high preference to specific targets. b) The