Page 451 - Automotive Engineering Powertrain Chassis System and Vehicle Body

CHAP TER 1 4. 2 Decisional architecture

moving obstacles and dynamic constraints, in a unified way. It has been decided to focus herein on the case of a car-
It seems from two concepts which have been used before in like vehicle with full dynamics and moving along a given
order to deal respectively with moving obstacles and dy- path. The main reason for this choice is that, in this par-
namic constraints, namely the concepts of configuration- ticular case, the state-time space is three-dimensional
time space (Erdmann and Lozano-Perez, 1987), and state thus permitting a clear presentation of the concept of
space, i.e. the space of the configuration parameters and state-time space. Besides, although one-dimensional only,
their derivatives. Merging these two concepts leads natu- this motion planning problem does feature all the key
rally to state-time space, i.e. the state space augmented of characteristics of trajectory planning in dynamic work-
the time dimension. In this framework, the constraints spaces, i.e. full dynamics and moving obstacles, and the
imposed by both the moving obstacles and the dynamic concepts presented hereafter can easily be extended to
constraints can be represented by static forbidden regions problems of higher dimension (see for instance Fraichard
of state-time space. In addition, a trajectory maps to a curve and Scheuer (1994)). Accordingly the method presented
in state-time space hence trajectory planning in dynamic here could readily be used within a path-velocity de-
workspaces simply consists in finding a curve in state-time composition scheme (Kant and Zucker, 1986) to plan
space, i.e. a continuous sequence of state-times between motions along a given path taking into account the vehicle
the current state of the robot and a goal state. Such a curve dynamics (as in Shin and McKay (1985)) or moving
must obviously respect additional constraints due to the obstacles (as in Kyriakopoulos and Saridis (1991) or
´
fact that time is irreversible and that velocity and acceler- O’Du ´nlaing (1987)).
ation constraints translate to geometric constraints on the In summary, this section addresses trajectory planning
slope and the curvature along the time dimension. However for a car-like vehicle A which moves along a given path S
it is possible to extend previous methods for path planning on a planar workspace W cluttered up with stationary
in configuration space in order to solve the problem at hand. and moving obstacles. It is assumed that S is collision-free
In particular, a method to solve trajectory planning in with the stationary obstacles of W and that it is feasible,
dynamic workspaces problems when cast in the state- i.e. that it respects the kinematic constraints that re-
time space framework is presented (Section 14.2.5.5). It stricts the motion capabilities of A. The problem then is
is derived from a method originally presented in Canny to compute a trajectory for A that follows S, is collision-
et al. (1988), and extended to take into account the time free with the moving obstacles of W and satisfies the
dimension of the state-time space. It follows the para- dynamic constraints of A.
digm of near-time-optimization: the search for the solu-
tion trajectory is performed over a restricted set of 14.2.5.4.1 Model of the path S
canonical trajectories hence the near-time-optimality of As mentioned earlier, the car-like vehicle A moves along
the solution. These canonical trajectories are defined as a given path S which is collision-free with the stationary
having piecewise constant acceleration that changes its obstacles of W and which is feasible, i.e. it respects the
value at given times. Moreover, the acceleration is kinematic constraints of A. Those kinematic constraints
selected so as to be either minimum, null or maximum are studied in more detail in Section 14.2.5.6. It appears
(bang controls). Under these assumptions, it is possible there that good feasible paths for a car-like vehicle
to transform the problem of finding the time-optimal should be planar curve made up of straight segments and
canonical trajectory to finding the shortest path in a di- circular arcs of radius 1=k max connected with clothoid
rected graph embedded in the state-time space. arcs. S is defined accordingly. Our main concern is that in
planning ‘high’ speed and forward motions only. S should
2
2
also be of class C . The C property ensures that the
14.2.5.4 Case study path is manoeuvre-free and that A can follow it without
having to stop to change its direction. Assuming that A
State-time space was first introduced in Fraichard and moves along S, it is possible to reduce a configuration of
Laugier (1992) to plan the motion of a point robot sub- A to the single variable s which represents the distance
ject to simple velocity and acceleration bounds and travelled along S.
moving along a given path amidst moving obstacles. Later,
a mobile robot subject to full dynamic constraints was
14.2.5.4.2 Model of the vehicle A
considered; first, in the case of a one-dimensional motion
along a given path Fraichard (1993), and then, in the In this section, we start by presenting the dynamic model
5
case of a two-dimensional motion on a planar surface of A that is used. Then we describe the dynamic con-
(Fraichard and Scheuer, 1994). straints that are taken into account.

5
This model is the two-dimensional instance of the model presented in Shiller and Chen (1990).

458