CHAPTER 05: SPECIAL TOPICS: Interpolating a Short and Smooth Path for a Robot


In this demonstration, we're going to show that how to find a smooth and the shortest path for a robot.  Let's go ahead and look at the example.  So here you are given six data points, and a robot has to go through consecutive points.  So it cannot take any path it wants to, what I'm trying to say is that it has to go from this point, to this point, to this point, to this, and this, and this here, and what you want to do is you want to find the shortest path going through those consecutive data points, and the points are given to you. And the reason why you want to do that is because you want to be able to minimize the amount of time it's taking for the robot to go from the first data point to the last data point.  Now, it may look like that connecting the dots as we do in some restaurants, the children do, might be the best approach to solve this problem, because you're simply drawing straight lines from one data point to another.  However, what we want to do is we also want to find a smooth path, that means that we cannot have sudden changes in the first derivative, or the slope of the function.  So what we want to be able to do is we want to be able to have a smooth path going through the data points.  So it means that maybe we need to do some kind of interpolation, which is higher than the first-order one, like in the . . . like what we have shown here is a linear spline interpolant, so we need to do something different than that. So since we are given six data points, what I might want to do is to maybe interpolate it to a fifth-order polynomial, and see what kind of a curve do I get. So let's go to the next step here.  So what you are finding out here is that you have six data points, so since you have six data points, you are taking a fifth-order polynomial which is going through those six data points, and this is the path which I get if I use a fifth-order polynomial going through those six data points.  Now, if I use spline interpolants, so this is a cubic spline interpolant which has been used through the six data points, so it seems that almost like that the curve which you are getting is very similar to the fifth-order polynomial which I had previously, so may this path is not any shorter than what I had before, but once you start putting them on top of each other, you will find that what you find out here is that the blue line is your spline interpolant. So this is your spline interpolant, and the other one which you have is the polynomial interpolant, and just by observing, you are able to see that the spline interpolant path length is going to be much shorter than what you find out from the polynomial interpolant.  So this is just an illustration to show you that spline interpolation will help you to develop a path which is shorter than what you would have gotten otherwise by using the polynomial interpolant, and also the concept of . . . it reinforces the concept that higher order interpolation is a bad idea.  If I add more points on this robot path, most probably I'll get a much more wigglier curve, much more oscillatory curve for the polynomial interpolant.  So what we have done is that we have taken . . . what we did was we found out the length of the polynomial interpolant, and it turns out that the length of the polynomial interpolant is 14.9, as opposed to the spline interpolant is 12.9, so it is shorter than what you get from the polynomial interpolant.  Now, how do you find the length of the interpolant?  The length of the interpolant is used by the formula that the length of a curve is given by this particular formula here, 1 plus, then you have to take the derivative of the function, you square it, you add 1 to it, then you take the square root of that, and that's what you have to integrate to be able to find out what the length of the curve is.  So be sure that when you are trying to find the length of this path that you don't start doing some kind of an integration under the curve, because that will give you the area under the curve, that's not what we're interested in, we're interested in finding the length of the curve, and the formula for that is given here. And that's the end of this segment.