Page 450 - Automotive Engineering Powertrain Chassis System and Vehicle Body

Decisional architecture C HAPTER 14.2

the configuration space. However there is much more to dynamics and moving along a given path (Shiller and
motion planning than that, especially when the robot Dubowsky, 1985; Shiller and Lu, 1990). Using these
considered is a car-like vehicle. For a start, such a vehicle results, some authors have described methods that com-
cannot move freely: it is subject to nonholonomic con- pute a local time-optimal trajectory (Shiller and
straints that restrict its motion capabilities (a car cannot Dubowsky, 1989; Shiller and Chen, 1990). The key idea of
make sidewise motions for instance). Then it usually these works is to formulate the problem as a two-stage
moves in a workspace that contains moving obstacles optimization process: optimal motion time along a given
(they should be avoided too!). In addition to that, it may path is used as a cost function for a local path optimization
also be necessary to take into account dynamic con- (hence local time-optimality). However the difficulty of
straints, e.g. bounded accelerations, that further affect the general problem and the need for practical algorithms
the vehicle’s motion capabilities (they cannot be ignored led some authors to develop approximate methods. Their
when the vehicle is moving fast). basic principle is to define a grid which is searched in order
In summary, physical and temporal constraints as well to find a near-time-optimal solution. Such grids are defin-
as geometrical ones must be considered when planning the ed either in the workspace (Shiller and Dubowsky, 1988),
motions of a car-like vehicle. Such additional constraint the configuration space (Sahar and Hollerbach, 1985), or
yields extensions to the basic motion planning problem the state space of the robot (Canny et al., 1988; Donald
that raise new problems and further complicate motion and Xavier, 1990; Jacobs et al.,1989).
planning. In this case, the output of motion planning is
a trajectory, i.e. a path parameterized by time. Trajectory 14.2.5.2.3 Moving obstacles
planning with its time dimension permits to take into A general approach that deals with moving obstacles is the
account time-dependent constraints such as moving ob- configuration-time space approach which consists of
stacles and the dynamic constraints of the vehicle. adding the time dimension to the robot’s configuration
The rest of this section explores how to deal with these space (Erdmann and Lozano-Perez, 1987). The robot maps
kinds of constraints. It reviews the main approaches that in this configuration-time space to a point moving among
have been developed in order to deal with all or part of the stationary obstacles. Accordingly the different approaches
constraints considered (Section 14.2.5.2). Then it in- developed in order to solve the path planning problem in
troduces a method that, unlike most of the methods
the configurationspace can beadaptedinorder to deal with
developed before, attempts to take into account all the
the specificity of the time dimension and used (see
aforementioned constraints simultaneously; it is based
Latombe (1991)). Among the existing works are those
upon the concept of state-time space (Section 14.2.5.3). basedupon extensions ofthe visibility graph (Erdmann and
For the sake of clarity, this general method is presented in Lozano-Perez, 1987; Fujimura and Samet, 1990; Reif and
the case of a car-like vehicle moving along a given path Sharir, 1985) and those based upon cell decomposition
(Sections 14.2.5.4 and 14.2.5.5). Such a path is collision- (Fujimura and Samet, 1989; Shih et al.,1990).
free and respects the vehicle’s nonholonomic constraints. Few research works take into account moving obsta-
The particular problem of planning a nonholonomic path cles and dynamic constraints simultaneously, and they
is explored afterwards (Section 14.2.5.6). usually do so with far too simplifying assumptions e.g.
´
Fujimura and Samet (1989) and O’Du ´nlaing (1987).
More recently (Fiorini and Shiller, 1996), has presented
14.2.5.2 Main approaches to trajectory a two-stage algorithm that computes a local time-optimal
planning trajectory for a manipulator arm with full dynamics and
moving in a dynamic workspace: the solution is com-
14.2.5.2.1 Nonholonomic constraints puted by first generating a collision-free path using the
Path planning with nonholonomic constraints is a re- concept of velocity obstacle, and then by optimizing it
search field in itself and has motivated a large number of thanks to dynamic optimization.
research works in the past 15 years. The review of the
relevant literature is made in Section 14.2.5.6, which is 14.2.5.3 Trajectory planning and
dedicated to this topic.
state-time space
14.2.5.2.2 Dynamic constraints State-time space is a tool to formulate problems of trajec-
There are several results for time-optimal trajectory tory planning in dynamic workspaces. In this respect, it is
planning for Cartesian robots subject to bounds on similar to the concept of configuration space (Lozano-Perez
their velocity and acceleration (Canny et al.,1990; and Wesley, 1979b) which is a tool to formulate path
´
O’Du ´nlaing, 1987). Besides optimal control theory pro- planning problems. State-time space permits to study the
vides some exact results in the case of robots with full different aspects of dynamic trajectory planning, i.e.

457