Page 460 - Automotive Engineering Powertrain Chassis System and Vehicle Body

Decisional architecture C HAPTER 14.2

path planning approach. It incrementally builds
a tree rooted at the start configuration. At each
step, a new configuration is added to the tree; it is
the farthest configuration reachable from the tree
by the steering method considered (optimization
tools such as genetic algorithms are used). In par-
allel, the steering method is used to determine
whether the goal configuration is reachable from
the new configuration.
Holonomic path approximation: the controllability
Fig. 14.2-30 Optimal paths for the Reeds and Shepp car.
result on the existence of an admissible collision-
free path is at the origin of a two-step nonholonomic
constraints and the obstacles of the environment. Al- path planning scheme that was introduced in
though the results on the controllability and the optimal Laumond et al. (1994):
paths presented above did not consider the obstacles of Step 1: compute a holonomic 10 collision-free
the environment, it will be seen further down that they path.
proved useful in the design of path planners for the RS Step 2: approximate the holonomic path by
car. a sequence of admissible collision-free paths.
In the past 15 years, several solutions have been pro- Step 2 recursively subdivides the holonomic path and
posed to solve the full path planning problem for both tries to connect the endpoints by using a steering method
the RS car (e.g. Barraquand and Latombe, 1989; along with a collision checker.
Laumond et al., 1989; Pommier, 1991), and the RS car
that can move forward only (e.g. Jacobs and Canny, 1989;
Fraichard, 1991; Laumond, 1987; Wilfong, 1988). This 14.2.5.6.2 Continuous-curvature car
paragraph focuses on three of them that all share
common features. For a start, they are generic, i.e. they As mentioned earlier, most path planning techniques for
can be applied to other types of robotics systems (the the RS car compute paths made up of line segments
first two are completely general, they can deal with connected with tangential circular arcs of minimum
holonomic and nonholonomic systems). Then, all of radius. Reeds and Shepp’s (1990) result concerning the
them make use of a steering method such as Steer RS . shortest path for the RS car is a reason that explains this
Steer RS computes the optimal path between two config- situation. No doubt that another reason for this situation
urations for the RS car but other steering methods could is that they are easy to deal with from a computational
be used instead (see the review made in Laumond et al. point of view. However the curvature of this type of path
(1998)). is discontinuous: discontinuities occur at the transitions
between segments and arcs. The curvature is directly
Prohahilistic path planning: this generic path planning related to the orientation of the front wheels of the car.
scheme was developed by Svestka and Overmars Accordingly, if a car were to track precisely such a type of
(1998) and Kavraki et al. (1996). It operates in two path, it would have to stop at each curvature disconti-
phases: nuity so as to reorient its front wheels. It is therefore
– Learning phase: build a roadmap reflecting the desirable to plan continuous-curvature paths. 11 To
connectivity of the collision-free configuration space. address this issue, a new model for the car-like vehicle is
The roadmap is a graph whose nodes are randomly introduced: the Continuous-curvature car, or CC car.
selected configurations and whose edges are admis- This model is presented in the next paragraph. Unlike
sible collision-free paths computed with a steering the RS car, the CC car has been little studied; several
method and a collision checker. results have been obtained however, they are presented
– Query phase: given a start and a goal configura- afterwards.
tions, use Steer RS to connect them to the roadmap. Model of the CC car Let A now represent a CC
Search the roadmap for a solution path. car-like robot. As per Boissonnat et al. (1994), a confi-
Ariadne’s Clew algorithm: this generic path plan- guration of A is now defined by the quadruple
1
2
ning scheme developed by Ahuactzin-Larios q ¼ðx; y; q; kÞ ˛R S R. k is introduced to charac-
(1994) is slightly different from the probabilistic terize the orientation of the front wheels of A.

10 It does not satisfy the nonholonomic constraints.
11 As a matter of fact, it is emphasized in De Luca et al. (1998) that feedback controllers for car-like robots require this property in order to
guarantee the exact reproducibility of a path.

467