Page 135 - Innovations in Intelligent Machines

126 A. Pongpunwattana and R. Rysdyk
The planning algorithm used in the Evolution-based Cooperative Plan-
ning System (ECoPS) is based on both Genetic Algorithms (GA) [11] and
Evolutionary Programming (EP) [8]. Work by Capozzi [5] suggests that the
algorithm combining features of both paradigms can improve the performance
of the optimization process for path planning problems. The design of evolu-
tionary path planning algorithms involves the following issues: path encoding,
fitness evaluation, mutation mechanisms, and selection scheme. The follow-
ing subsections describes these issues of path planning problems for a single
autonomous vehicle. Extensions to multiple cooperating UAVs are given in [1].

Path Encoding
One of the key issues of applying evolutionary computation to a given problem
is finding a good representation of each individual in the population which
adequately represents a candidate solution to the problem. In path planning
problems, the search space Ω which consists of the parameters of the chosen
path representation must be defined. These parameters must be sufficient to
specify a candidate path in spatial and/or temporal space. Examples of path
representations are:

– Sequence of waypoints: A sequence of waypoints including the initial and
goal locations are used to represent a path. A path represented by these
waypoints is the linked straight-line segments connecting the initial loca-
tion, all the waypoints in the sequence, and the goal location.
– Sequence of velocity vectors: A path is presented by a time sequence of
velocity vectors whose elements are speed, heading and climb angle. Using
a fixed time interval, this representation allows the planning algorithm to
constrain the candidate solution to lie within the acceleration capabilities
of the vehicle.
– Sequence of maneuvers: A path is represented by a time sequence of prim-
itive maneuvers which are achievable by the vehicle. Examples of maneu-
vers are speed-up, slow-down, turn-left, turn-right, and so on. The time
duration of each maneuver can be varied.
– Sequence of motion primitives: In this representation, a path is a chain of
motion primitives linked together end to end. Examples of motion prim-
itives are a straight line segment, constant radius curve, constant climb
angle line segment.

In ECoPS, a path is encoded as a sequence of simple segments chained
end-to-end, shown in Figure 6. The locations of the vehicle and the goal are
shown as a blue triangle and a green circle respectively. In this approach, for 2-
dimension problems, there are two elemental types of segments, straight lines
and constant radius curves, shown in Figure 7. The segment parameters are
limited to keep motion within the vehicle capabilities. Continuity is enforced
between the joining end of a segment and the starting point, heading, and
speed of another joining segment. We also enforce every path to end at the