Page 124 - Innovations in Intelligent Machines

Evolution-based Dynamic Path Planning for Autonomous Vehicles 115
in which the vehicle operates is discretized and represented by a graph com-
posed of a number of nodes linked together with arcs. Each node corresponds
to a location in the environment and an arc links two adjacent nodes. There
is a cost associated with each arc. A path in this graph consists of a series
of connected arcs. One advantage of this approach is the compactness of the
topological map of the environment represented by the graph. The path plan-
ning problem is to find the optimal path from one node to another in the
graph. The planning algorithm minimizes the total cost which is the sum of
the cost of each arc in the path. A graph search algorithm such as Dijkstra’s
algorithm or the A algorithm [17] can be used to find the optimal path. Thrun
∗
[25], Mata and Mitchell [15], Mandow [14], and Bander [2] have all worked on
this graph-based planning concept and applied it to many scenarios.
Another approach to path planning is probabilistic roadmap planning
(PRM). It is an efficient method to compute collision-free paths for vehi-
cles with many degrees of freedom [12]. This method consists of two phases, a
building phase and a query phase. The building phase is the construction of a
graph called roadmap. The nodes in the roadmap are collision-free configura-
tions and the edges linking the nodes are collision-free paths which enable a
robot to move from one configuration to another. The query phase is finding
a path between an initial and goal configurations by connecting these config-
uration nodes to the road map and searching the roadmap for a sequence of
edges linking the two nodes. This method was originally developed for holo-
nomic robots in a static environment. Overmars [18] applied this technique to
simple holonomic robots and non-holonomic robots having constrained kine-
matics and high degrees of freedom. LaValle and Kuffner [13] proposed a
randomized path planning technique similar to PRM for robots having high
degree-of-freedom with both kinematic and dynamic constraints. Song et al.
[24] proposed a new method of building and querying probabilistic roadmaps
to improve the performance of the planning process.
The common drawback of the above approaches is the requirement to
repeatedly update the graph representing the environment if it is changing
rapidly. Evolution-based approach is suitable in this situation. It does not
require a graph-based representation of the environment. Furthermore, evolu-
tionary algorithms are continual adaptation techniques favorable for dynamic
path planning. They can run continuously during the execution of the plans
and handle changes in the operating environment and the vehicle capabili-
ties. Evolution-based techniques respond to the changing environment quickly
because they do not have to recompute the entire plans. The current plan is
adapted in response to the changes. Works in this approach have been investi-
gated by several researchers [9], [26], [6], [10], and [20].
Dynamic path planning is typically solved using a hierarchical approach
such as Brumitt [3] and Chien et al. [7]. In such approach, the planning sys-
tem is divided into two levels, task sequencing and local path planning. The
path planner provides optimal local paths for traveling between each pair
of target locations and between the current vehicle location and all target