Page 126 - Innovations in Intelligent Machines

Evolution-based Dynamic Path Planning for Autonomous Vehicles 117
Planning
horizon Path computed
at time t s
p−1

Committed section
t < t < t s p Spawn point t s
k
Vehicle p
at time t k
Previous
spawn point t s
p−1
Adapting section
t < t < t N
s p
Execution Planning
time horizon time horizon

time
t s p−1 t k t s p t N

}
Time-available-to-plan
Fig. 3. Illustration of the concept of dynamic path planning. A vehicle (at time t k)
which is shown as
is moving along a trajectory previously computed at time t s p−1
a gray line. The next closest spawn point at time t s p is shown as a black diamond

The time t N at the end point of this trajectory segment is the planning time
horizon. It can either be fixed or a variable whose value is specified by the
planner. An update trajectory is sent to the vehicle’s controller for execution
every time the vehicle reaches a spawn point. The planner will start comput-
ing a new trajectory starting at the next spawn point. The time difference
)) specifies the maxi-
between two adjacent spawn points (∆T s =(t s p − t s p−1
mum time available to plan for the planner to update its path. In this manner,
the planner can incorporate any new information about the environment that
becomes available during the mission. The trade-off between time available to
plan and adaptability is important. One would want the non-adapting commit-
ted sections of the planned path to be short in a highly dynamic environment.
However, that shortens the time available to plan. The shorter time available
to plan requires faster planning algorithms. Hence, dynamic planning algo-
rithms must be fast enough to compute new plans within the specified time
limit.
The concept of this dynamic planning process is very similar to that of the
Model-based Predictive Control [4]. Figure 4 illustrates the block diagram of a