6.5. Planning for Autonomous Driving.#
Motion primitives provide a computationally efficient tool for fast, local motion planning.
In previous chapters, we have mainly considered two kinds of planning problems. For the trash sorting robot, vacuum cleaning robot, and warehouse robot, we focused on the problem of making the best decisions in the presence of uncertainty. In these problems, we used probability theory to quantify uncertainty, and developed policies to maximize the expected benefit (or to minimize the expected cost) of executing actions in a given state. In contrast, for the differential drive robot (DDR), we considered the purely geometric problem of planning collision-free paths. Even though this problem did not consider uncertainty, the computational complexity of the problem precludes exact, complete solutions for all but the simplest problems, leading to the introduction of sampling-based methods.
A common characteristic of all planning methods described to this point is that each addresses a global problem. For MDPs, we used value or policy iteration to establish a policy over the entire state space. For DDRs, we searched the entire configuration space for a collision-free path. Furthermore, the methods we developed for both problems were completely general. Our probabilistic approaches work for arbitrary probability distributions, reward functions, and system dynamics. Our geometric approaches to path planning work for arbitrary environments, and can easily be extended to robots with complex dynamics (e.g., we will extend RRTs to the case of drones in the next chapter).
However, methods that address global problems in broad generality often require significant computational resources (both processing power and computation time). This can render such methods ineffective for situations in which real-time adaptivity is required over short time horizons. These conditions are exactly those confronted by self-driving cars, and for this reason, in this chapter we introduce a new approach, one that exploits motion primitives for motion planning.
6.5.1. Motion Primitives#
Consider a car traveling in reverse that wishes to suddenly change its orientation by completing a rapid 180-degree turn (a favorite maneuver for drivers like James Bond and Steve McQueen). How would we go about implementing this type of maneuver in an autonomous vehicle?
This two approaches we have considered before can be very inefficient for planning trajectories that have such well-defined characteristics. For all of our probabilistic methods, we used a discrete time formulation and considered the effects of executing an action (e.g., move forward, move left) for a small duration of time, \(\Delta t\). To plan collision-free paths, we considered artificial potential fields and RRTs, both of which use short straight-line paths in the configuration space to connect configurations (small gradient descent steps for potential fields, and steering toward \(q_\mathrm{rand}\) for RRTs). In each case, the language of path segments is very simple, and in each case, a full plan will consist of many sequential steps.
Instead, the U-turn maneuver could be achieved by a predefined sequence of steps: after achieving a reasonable speed, remove your foot from the gas pedal; turn left sharply and hit the breaks; at the perfect moment, release the breaks and straighten the wheel. When stunt drivers execute this maneuver, they do not plan step-by-step what to do. Rather, they have pre-compiled this sequence of steps into a basic action that can be executed with little reasoning. This is the basic idea of motion primitives.
This idea is illustrated in the figure below, which shows four motion primitives for a car. The primitive \(P_1\) corresponds to driving forward, while motion primitives \(P_2\), \(P_3\), and \(P_4\) correspond to veering to the left at increasingly sharp angles.
Motion primitives can be defined in numerous ways. The figure above illustrates four fixed motion primitives, but it would not be difficult to generalize each of these to a class of motions by using parametric descriptions. We could specify a geometric curve without consideration of time or dynamics. For example, for a parallel parking robot, we might define an initial curve to move the car from the street into an empty parking spot. In cases where dynamics are significant (e.g., in drone flight), we might additionally specify a feedback control law to be executed from an initial state until some final state is achieved. We can parameterize these primitives by duration, by geometric properties (e.g., angle, distance), or by state feedback conditions. Below, we will see how to do this by using polynomial trajectories, which generalize to splines.
6.5.2. Planning using Motion Primitives#
The use of motion primitives can greatly reduce the cost of planning, since the set of actions available at any moment in time is small and easily computed. For the car example above, if we assume a symmetric set of motion primitives for veering to the right, motion planning can be reduced to choosing from this set of seven possible actions at each moment in time. If, for example, there is a slow-moving car just ahead, it might be advantageous to change lanes using one of \(P_2\), \(P_3\), or \(P_4\). If there is a rapidly approaching oncoming car, it might be best to use \(P_2\), to delay changing lanes until that car has passed by.
More generally, a motion primitive typically includes a set of conditions that define when the primitive is applicable, and a set of possible transitions to other motion primitives. For example, it would be reasonable to veer left slightly and then drive straight, but it would not be reasonable to transition from forward motion to reverse motion without some intermediate maneuvering.
Under these conditions, planning can be effected by a generate-and-test approach. At each moment in time, the planner considers the current situation, enumerates the valid motion primitives (using preconditions for execution and set of valid transitions), and evaluates the benefit of each admissible candidate motion primitive. This approach can be effective for problems such as highway driving, where local context is all that is necessary for making decisions. For example, the traffic in rural Georgia is irrelevant when leaving downtown Atlanta on a trip to Boston. In this case, immediate driving decisions depend on the car just ahead, and the nearby cars in adjacent lanes.
6.5.3. Polynomial Trajectories#
Let’s begin with the simple problem of changing lanes along a straight stretch of highway. The situation is illustrated in the figure below.
Here, we have taken the \(s\)-axis to be longitudinal direction (parallel to the highway), and the \(d\)-axis is along the lateral direction (perpendicular to the highway). This choice of coordinates will be convenient below, when we generalize trajectories to arbitrary curves. In addition, for now let us assume that the car speed satisfies \(s=t\). Below, we will generalize further by defining \(s\) to be the distance along the path (instead of a linear distance along a straight lane), and \(s(t)\) to be the time parameterization of the path.
For now, let us assume that the lane change maneuver begins at \(s=0\), \(d=0\), and that the desired ending configuration is \( s = s_\mathrm{g}, d= d_\mathrm{g}\), i.e., at the end of the maneuver (at \( s = s_\mathrm{g}\)), the car will have reached the center of the left lane (i.e., \( d = d_\mathrm{g}\)).
At first glance, it might seem that this could be accomplished by a simple linear trajectory of the form
At the start of the maneuver, \(s=0\), which matches the initial condition \(d(0)=0\), and at \( s = s_\mathrm{g}\) we match the end condition \(d(s_\mathrm{g}) = d_\mathrm{g}\). This trajectory is illustrated in the figure below.
Note that this trajectory requires an instantaneous change in the car’s heading, from 0 at \(s = 0^-\) to \(\frac{ d_\mathrm{g}}{s_\mathrm{g} }\) at \(s=0^+\). Cars, of course, are not capable of executing maneuvers with velocity discontinuities (under normal driving conditions), so this trajectory could not be executed by a normal car. However, it is not difficult to generalize this approach to solve this problem.
Consider the \(m^{th}\) order polynomial
For \(m=1\), we obtain the linear trajectory above by setting \(\alpha_0 = 0, \alpha_1 = \frac{ d_\mathrm{g}}{s_\mathrm{g} }\). In other words, if we begin with the general linear trajectory \(d(s) = \alpha_0 + \alpha_1 x\), we can solve for \(\alpha_0\) and \(\alpha_1\) to match the initial and final values for the lateral position \(d\). This shouldn’t be surprising; the linear polynomial has two free parameters (\(\alpha_0\) and \(\alpha_1\)), so it makes sense that we could satisfy two independent constraints (initial and final values for \(d\)) by an appropriate choice for these parameters.
In general, the parameters of an \(m^{th}\) order polynomial can be chosen to satisfy \(m+1\) independent constraints. So, if we wish to match initial and final conditions on heading (which is defined by the first derivative of \(d\)), we would require a cubic polynomial, and if we wished to also satisfy lateral acceleration constraints, we would need a fifth order polynomial. The lateral velocity and acceleration for the trajectory are given by the first and second derivatives of \(d\), which we denote by \(d'\) and \(d''\), respectively. For a fifth order polynomial, we have
For a simple lane change, it is typically desirable to have zero lateral velocity and zero lateral acceleration at the initial and final positions. This leads to the following system of equations:
Note that these six equations are all linear in the parameters \(\alpha_i\), so it is a simple matter to solve these.
6.5.4. Splines#
While the derivation above produced a single polynomial trajectory, it is a simple matter to extend this formalism to construct trajectories that are composed of multiple consecutive polynomial segments. Such trajectores belong to the more general class of splines. In general, a spline is a continuous, piecewise polynomial curve, and we are not necessarily given the specific values for the transition points between adjacent segments.
In fact, we have actually done exactly this in the above derviation, if we consider that for \(s < 0\) and for \(s > s_\mathrm{g}\) the trajectory \(d(s)\) is linear and pararallel to the \(s\)-axis, i.e., we have solved for a special case of three polynomial segments with two of those segments being linear and one quintic.
Suppose that we wish to construct a piecewise polynomial trajectory that exactly reaches certain via points, \((s_i, d_i)\), i.e., we are given the sequence of couples \((s_0,d_0) \dots (s_n, d_n)\), and we want to ensure that the lateral position of the car is given by \(d_i\) at longitudinal position \(s_i\). We can build the trajectory \(d\) from a sequence of polynomials \(P_k\) as follows
The coefficients \(\alpha_{ki}\) are chosen to ensure the desired continuity and smoothness properties. For example, if we want to ensure that position, velocity, and accelerations are continuous throughout the trajectory, we must enforce
Note that the first set of constraints also ensure that \(d(s_k) = d_k\) for each transition point. In order to satisfy the boundary conditions for the start and end of the trajectory, we must enforce
where \(v_k\) and \(a_k\) denote the velocity and acceleration, respectively, at position \(s_k\).
Note that in this formulation, the accelerations and velocities at the junctions of two adjacent splines are not specified; the velocity and acceleration must match for the two polynomial segments, but the specific values of velocity and acceleration are not specified. Because of this, we have fewer constraints, and therefore require fewer parameters \(\alpha_{ki}\). In particular, if we merely want to ensure continuity of position, velocity, and acceleration at the junctions, cubic polynomials are sufficient. This is different from the situation above, in which we used a quintic polynomial to achieve specific values of velocity and acceleration (all of which were set to zero) at the junctions of the two linear segments with the lane-changing trajectory. You should count the constraints, and convince yourself that this is true.
6.5.5. Following Nonlinear Trajectories#
All of the above can be generalized to the case of nonlinear trajectories, such as a car driving on a curvy road, or making a turn at an intersection. In these situations, the desired trajectory is often determined by a desired behavior. Possible behaviors might include lane following, merging, changing lanes, coming to a stop at an intersection, or making a turn at an intersection. In these cases, following the desired trajectory, rather than computing the desired trajectory, becomes an important problem. In this section, we address the problem of following such a trajectory.
The figure below illustrates the situation. We denote by \(\gamma(s)\) the desired trjactory of the car, where \(s\), an arc length parameter, is a function of time, and therefore the instantaneous desired speed of the car is \(\dot{s}(t)\). Since the goal is to keep the car on the deisred trajectory, it is convenient to represent the state of the car in a coordinate frame that is local to the trajectory. To do so, for each point along \(\gamma\), we define a frame with origin \(\gamma(s)\), with axes \(t_\gamma(s)\) and \(n_\gamma(s)\), the tangent and normal vectors to \(\gamma\) at \(s\), respectively. This is essentially a Frenet frame for planar curves (the binormal being orthogonal to the plane).
Using this convention, at time \(t\) we can denote the position of the car as
A simple way to bring the car into coincidence with the desired trajectory is to choose a target point along the desired trajectory and plan a local trajectory for the car to reach this target point at some desired time, \(T\), traveling at the desired velocity. We can do so by specifying the time \(T\) at which the car should reach the target point, and planning a trajectory, \(x(t)\) for the car such that \(x(T) = \gamma(s(T))\).
For the lateral motion, this amounts to planning a trajectory for \(d(t)\) with appropriate boundary conditions. Because human passengers are particularly sensitive to sudden motions in the lateral direction, we choose \(d(0), \dot{d}(0)\), and \(\ddot{d}(0)\) to match the state of the car at time \(t = 0\). When the car reaches the point \(\gamma(s(T))\) on the desired trajectory, it is desirable that the lateral velocity and acceleration both be zero, so that the car moves along the desired direction of motion (i.e., no lateral motion relative to the desired trajectory). Thus, at time \(T\), we need to satisfy \(d(T) = \dot{d}(T) = \ddot{d}(T) = 0\). As we have seen above, these six constraints uniquely determine a quintic polynomial trajectory for \(d\).
Given \(d(t)\), the trajectory for the car is simply given by
which brings the car onto the desired trajectory, with desired velocity, at time \(t = T\).
Obviously, the termination time \(T\) plays a significant role in determining the quality of the solution. For example, if we choose \(T\) to be too small, the car might need to accelerate quickly to an unsafe velocity to reach the target point at \(t = T\). How, then, should we choose the value of \(T\)? A typical approach is to formulate the choice of \(T\) as an optimization problem, with a cost functional that takes into account both the duration of the maneuver (we don’t want the maneuver to take too long), and the comfort of the human passenger. As mentioned above, humans are sensitive to acceleration changes in the lateral direction, therefore, we might wish to minimize the overall effect of such changes. Mathematically, the instantaneous change in lateral cceleration is given by the third derivative of \(d\), which is known as the jerk. For a given trajectory \(d(t)\), defined on the interval \([0,T]\), the following cost functional penalizes aggregate jerk and total exectution time
In general, it may not be possible to solve this optimization problem in real time. In such cases, rather than using \(J\) to solve find the optimal \(d\), we can use a generate-and-test approach. With such an approach, several values of \(T\) are proposed, and the corresponding quintic trajectories are computed for each of these. It is then a simple matter to evaluate the cost of each of these proposed trajectories, ultimately choosing the value of \(T\) with the smallest such cost.