Hi everyone, and welcome to the final module of course four. In this module, we'll discuss the lowest level of our hierarchical motion planner, which is the local planner. As a reminder, the local planner is the portion of the hierarchical planner that executes the maneuver requested by the behavior planner in a collision-free, efficient, and comfortable manner. This results in either a trajectory, which is a sequence of points in space at given times or a path and velocity profile, which is a sequence of points in space with the required velocities at each point. This plan can then be given as the reference input to the controllers that you developed in course one. In this module, we'll build upon the introductory reactive planner we developed back in module four, such that it is able to handle some of the nuances presence in the autonomous driving motion planning problem. In particular, we'll move from the discrete time to continuous time in order to produce smooth parameterized paths that are easy to track with our controllers. In this video, we'll introduce the path planning problem and its associated constraints and boundary conditions. As well, we'll discuss parametric curves and how they are useful for representing paths for this problem. In particular, you should understand the difference between splines and spirals in the context of motion planning, and the advantages and drawbacks of each. So let's get started. The first step in understanding the path planning problem is to first understand its most fundamental requirements. For the path planning problem, this is given a starting position, heading, and curvature, find a path to an ending position heading and curvature that satisfies our kinematic constraints. In the context of an optimization, the starting and end values can be formulated as the boundary conditions of the problem, and the kinematic motion of the vehicle can be formulated as continuous time constraints on the optimization variables. In this context, the boundary conditions are the conditions that must hold on either end point of the path for a given optimization solution to be considered feasible. If these boundary conditions are violated, no matter how great the path is, we haven't achieved our core objective of actually getting to the point we want to get to. So the path is not useful to us. These boundary conditions will influence how we decide to set up the underlying structure of the optimization problem. Let's look at why this is. For our path planner, our only kinematic constraint is going to be restricting the maximum curvature along the path. In general, this is not easy to satisfy since there are infinitely many points along a continuous path. Instead, we will often take samples of the curvature at different points along the path, and constrain the curvature of each of these points. Assuming the path is relatively well-behaved, this will likely correspond to the curvature of the entire path satisfying the constraint. To simplify the representation of our optimization problem, we're going to define a path as a parametric curve. What is a parametric curve? A parametric curve is a curve that can be described as a set of equations with specific parameters. These parameters often denote path traversal, whether it will be through arc length or just varying from zero to one. For example, here we have a cubic spline set of parametric equations for the x and y positions of a path. The parameter of the equations u varies from zero to one, as we traveled from the start of the path to the end of the path. The vector valued function r contains the x and y position at each point corresponding to a given u value. For autonomous driving, we often but not always require the path to be a parametric curve. Why is this? We often focus on planning methods that optimize a given path according to boundary conditions shown here by Beta naught and Beta f, kinematic constraints shown here by Alpha, and an objective functional shown here by f. Having a parametric representation of the path make setting up the optimization problem simpler, as we have a function we can directly give to our objective functional f. Note that the term functional refers to mappings that takes a function as their argument and return a real value, so it can be used to define a cost over a space of functions or parametrized curves. We can contrast this parametric curve approach with the reactive planner in module four, where we represented the trajectory and the path with a sequence of points in space. This is known as a non-parametric path since the curve we followed did not have a parametric representation. In the field of autonomous driving, there are two common types of path parameterizations. The first are quintic splines which are fifth order polynomial functions of the x and y position of the car. The second type is the polynomial spiral, given by a polynomial curvature function with respect to arc length. Pictured here is a third order polynomial spiral, a cubic spiral, both of these parameterized curves give us the means to satisfy the boundary conditions we just discussed, and also offer us parameters to use in objective functions to craft the paths according to our requirements. Selecting either of these has associated tradeoffs. So let's explore each more deeply. First, let's discuss the quintic spline. The quintic spline is given by two equations, one for the progression of x along the spline and one for y. Here we can see that the quintic spline has 12 parameters, six for the x equation and six for the y equation. These parameters correspond to the polynomial coefficients that form the shape of the curve. The traversal parameter u is fairly arbitrary here. For simplicity, we take it to be in the range of zero to one. What this means is that u equals zero corresponds to the start of the path, and u equals one corresponds to the end. A nice property of the quintic spline is that for given position heading and curvature boundary conditions, there is an immediate closed form solution for the spline coefficients that satisfy them. The solution is quite long so we won't listed here, but it is still cheaper to evaluate than generating a path using an iterative optimization method. See the supplemental materials for a full listing. There are also additional degrees of freedom which can be further optimize depending on this application. This is desirable because it allows us to generate a feasible solution to the boundary conditions immediately, which can be further refined in anytime fashion. The downside with quintic splines is that it is often hard to constrain curvature within a certain set of bounds as is often required in autonomous driving. If we look at the curvature equation for a parametric curve, we can see that for our quintic splines, the curvature as a function of arc length will not in general be a polynomial. This has the potential to introduce cusps or even discontinuities of the curvature in the spline, which makes it difficult to approximately satisfy curvature constraints across the entire domain of the spline. We will discuss these curvature constraints in more detail in our next lesson, where we set up the optimization problem for path planning. As an alternative approach, we can also employ polynomial spirals to represent our path. These curves offer a closed form equation for the curvature of the curve along each point of its arc length. For autonomous driving, it is common to select a cubic polynomial as our curvature function of arc length. However, higher-order functions are also acceptable. The main positive of using polynomial spirals is that their structure is highly conducive to satisfying the approximate curvature constraints that are often required by the path planning problem. Since a spiral is a polynomial function of curvature, the curvature value will not change extremely quickly like it can in the case of quintic splines. This means we can constrain the curvature of only a few points in the spiral and the spiral will very likely satisfy the curvature constraints across the entire curve. This is highly useful when performing path optimization, as the number of constraints greatly increases the computational effort of each optimization step. The downside of using polynomial spirals is that there is no closed form solution of the position and heading of the spiral, unlike the case in the quintic spline. Therefore, we must perform an iterative optimization in order to generate a spiral that satisfies our boundary conditions. As can be seen here, the position equations results in Fresnel integrals, which have no closed form solution. We therefore need to use numerical approximation techniques to compute the final end points of the spiral. In this module, we will approximate these Fresnel integrals using Simpson's rule shown here on the third line. Simpson's rule is more accurate with fewer points than other approximation methods, which will be useful when we setup our optimization problem. When it comes to the strengths and weaknesses of the spiral, we almost have a duality when compared to the spline, each has a weak point where the other is strong. The spline provides closed form solutions based on start and end points alone, whereas the spiral does not. The spiral ensures smooth curvature variation along the path, while the spline does not. You will therefore need to determine which method is appropriate depending on your specific application. As a brief shorthand, the spline leads to computational efficiency, while the spiral leads to easier implementation of curvature constraints. For this module, we will focus on the polynomial spirals as we develop our path planner, as we have a strong interest in ensuring the paths generated by our local planner can be executed smoothly and safely by the vehicle. However, many of the techniques described going forward can also be applied to quintic splines. Let's summarize this lesson. We gave you an overview of the boundary conditions and parametric curves used in autonomous driving path planning, and we introduced splines and spirals as alternative path representations, and discuss their differences in the path planning context. In our next lesson, we'll be discussing how to set up the path planning optimization problem using the cubic spiral parametrization we discussed in this lesson, as well as the constraints and objective functions we defined earlier in this course. We will see you there.
