Page 94 - Innovations in Intelligent Machines

84 I.K. Nikolos et al.
advantage to this approach is that it yields the optimal solution for the given
problem. The primary disadvantage is the high computational time required.
In [16] the motion-planning problem was decomposed into a waypoint path
planner and a dynamic trajectory generator. The path-planning problem was
solved via a Voronoi diagram and Eppstein’s k-best paths algorithm. The
trajectory generator problem was solved via a real-time nonlinear filter that
explicitly accounts for the dynamic constraints of the vehicle and modifies
the initial path. This decomposition of the motion-planning problem has the
advantage of decomposing a non-polynomial optimization problem into two
sub-problems that can be computed in near-real time, with the disadvantage
of providing a suboptimal solution [16].
Computational intelligence methods, such as Neural Networks [28], Fuzzy
Logic [29] and Evolutionary Algorithms (EAs) [15, 23] (or, in some cases, a
combination of them) have been successfully used in the development of algo-
rithms that produce trajectories for guiding mobile robots in known, unknown
or partially known environments.
During the past few years, it has been shown by many researchers that
EAs are a viable candidate to solve path planning problems effectively and
provide feasible solutions within a short time without demanding excessive
computer power. The reasons behind choosing EAs as an optimization tool
for the path-planning problem are their high robustness compared to other
existing directed search methods, their ease of implementation in problems
with a relatively high number of constraints, and their high adaptability to
the special characteristics of the problem under consideration [23].
Traditionally, EAs have been used for the solution of the path-finding
problem in ground based or sea surface navigation [30]. Commonly, the gen-
erated trajectory composed of straight line segments, connecting successive
way points, that guided a mobile robot or a vehicle along a 2-D path on the
earth’s or sea’s surface. The design variables used represented the coordinates
of the way points, where the vehicle changes its direction. Other approaches
took into account the time dimension by using design variables that also
described the vehicle steady speed as it traversed a part of its path. When the
vehicle’s operational environment was partially known or dynamic, a feasible
and safe trajectory was planned off-line by the EA, and the algorithm was
used on-line whenever unexpected obstacles were sensed [31, 32]. EAs have
been also used for solving the path-finding problem in a 3-D environment for
underwater vehicles, assuming that the path is a sequence of cells in a 3-D
grid [33, 34].
In [23] an EA based framework was utilized to design an off-line/on-line
path planner for UAVs autonomous navigation. The path planner calculates
a curved path line, represented using B-Spline curves in a 3-D rough terrain
environment; the coordinates of B-Spline control points serve as design vari-
ables. The off-line planner produces a single B-Spline curve that connects
the starting and target points with a predefined initial direction. The on-line
planner gradually produces a smooth 3-D trajectory aiming at reaching a