Page 125 - Innovations in Intelligent Machines

116 A. Pongpunwattana and R. Rysdyk
locations. These optimal paths must also satisfy all the given constraints such
as avoiding obstacles in the environment. The cost information of this set of
local paths is then used during the evaluation of candidate overall paths. This
process is performed by the mission planner which determines the optimal
sequence of target locations for the vehicle to visit during the mission. The
planning at this level is a combinatorial optimization problem. This approach
is shown to be effective in a static environment. However, it may not be
suitable in dynamic environments where the targets and obstacles may move
during the mission. The changes in the environment force the planning sys-
tem to frequently update the local paths prior to the optimization process for
task sequencing. The process of updating the local paths is computationally
extensive because it often needs to update most if not all of the local paths
joining all target locations.
In this paper, we present an evolution-based dynamic path planning algo-
rithm to compute paths for a vehicle to reach a set of targets while avoiding
obstacles in the environment. The planning algorithm searches for the opti-
mal path that maximizes an objective function and satisfies all the constraints
imposed on the problem. The planner must be able to compute an effective
path off-line prior to the start of the mission and dynamically adapt the path
in response to changes in the environment during the mission.
The remaining sections are organized as follows. Section 2 describes the
concept of dynamic path planning and a stochastic model of the system used
to formulate the planning problem. In Section 3, we present a technique to
approximate the probability of intersection of a vehicle and a site in the envi-
ronment. This technique addresses the collision avoidance problem, either with
static or moving objects such as other vehicles. The planning algorithm is pre-
sented in Section 4. Example problems of static and dynamic path planning
are also given. Section 5 and 6 show the ability of the planning algorithm
to handle timing constraints and a changing environment. Finally Section 7
provides a summary and conclusion of the work presented here.

2 Dynamic Path Planning

Dynamic path planning is a continual process which generates a new path
by adapting previously computed paths for future motion. This concept is
illustrated in Figure 3. We define a spawn point as a time where the planner
updates the output trajectory. During the course of the mission, the planner
continually computes an updated path which starts at the next closest spawn
which is the
point. In the figure, the closest spawn point is located at time t s p
execution time horizon of the vehicle controller. This spawn point separates
the committed section and the adapting section of the planned trajectory
. The committed section, which will not be
previously computed at time t s p−1
. The adapt-
altered, is a portion of the path for the time period t k <t<t s p
ing section of the trajectory remains free to be further refined by the planner.