Page 134 - Innovations in Intelligent Machines

Evolution-based Dynamic Path Planning for Autonomous Vehicles 125
4 Planning Algorithm

In this section, we describe an evolutionary algorithm for solving the dynamic
path planning problem presented in Section 2. This problem basically is iter-
atively finding a path represented by the variable Q(s p ) that maximizes the
objective function given in Equation 16.
The algorithm presented here can be used to compute both the static and
dynamic path planning problems. Static or off-line path planning is a process
used to compute an optimal path connecting the initial position of the vehicle
to the goal location prior to the start of a mission. Dynamic path planning
is an iterative process. This planning problem is dynamic because it changes
as the vehicle moves along the last updated path. In a dynamic environment,
the locations of objects in the environment may also change. We will first
describe the algorithm for static path planning. Then we extend the static
path planning algorithm to be used for dynamic path planning.

4.1 Algorithm for Static Planning

The path planning algorithm presented here is based on the algorithm
described in Rathbun et al. [21]. An evolutionary algorithm is used to solve
the underlying optimization problem. The general concept of the planning
algorithm is illustrated in Figure 5. The algorithm runs in a loop which has
three phases. It starts by randomly generating a population of encoded plans.
Then it evaluates the fitness value of each plan. The next step is to select the
best plan to be the candidate solution for this generation. Using a selection
scheme, a portion of the plans in the population are selected to be the parents
of the next generation based on their fitness values. The last step is to pro-
duce offspring from the parents selected in the previous phase. An offspring
is generated by cloning a parent and applying a mutation mechanism to it or
by crossover of two parents. This loop is run continuously to update the plan
as the optimization process proceeds.

Environment
Produce Vehicle
Offspring Capabilities
(mutation)

Plan Encoding Population Evaluate Best Decode Plan
(fitness)

Selection Constraints
Goals
Fig. 5. Overview of evolutionary planning algorithms