In the previous video we learned a graphical interpretation of the time-optimal time scaling problem. Basically, we try to keep the speed s-dot as high as possible while remaining within the motion cone dictated by the robot's actuators. In some cases, the time-optimal solution is given by a bang-bang trajectory, where the robot maximally accelerates then maximally decelerates.

In other cases, though, the velocity limit curve prevents a simple solution like this. In this final video of Chapter 9, we develop an algorithm to handle this case.

The first step of the algorithm is initialization, which you can find in the book. In step 2, we integrate the minimum acceleration L backward from the end state until either we reach s equal to zero or the motion cone disappears at the velocity limit curve. In the figure shown here, we reach the velocity limit curve. In step 3, we integrate the maximum acceleration forward from the initial state until we intersect either the final segment or the velocity limit curve. If we intersect the final segment, then we're finished: we've found the optimal time scaling. In the figure, we intersect the velocity limit curve at (s_lim, s_lim-dot). We know we have to slow down at some point before this intersection, to keep from running into the velocity limit curve. Since time-optimal trajectories consist of only maximum acceleration U and minimum acceleration L, we need to find a point where we switch from U to L.

One way to find the switch point is to decrease the velocity s-dot from the point where we hit the velocity limit curve, and to integrate forward the minimum acceleration L. Depending on how much we decrease s-dot, the forward integration will either hit the s-axis, as it does with our first two guesses; or it will intersect the velocity limit curve again, as with our third guess; or it will just touch the velocity limit curve tangentially. It is this tangential point we are looking for, and we'll call this point (s_tan, s_tan-dot).

In step 5, we integrate the minimum acceleration L backward from the tangent point until it intersects the previous U segment. This is the switch point s_1, from maximum acceleration to minimum acceleration. States in the region shaded red would eventually collide with the velocity limit curve, so they have to be avoided.

In step 6, we mark the tangent point as the switch point s_2, where we switch again from minimum acceleration L to maximum acceleration U. We then go back to step 3, where we integrate U forward again. This segment will either intersect the velocity limit curve again, in which case we repeat the process just described, or it will intersect the final L segment, and the algorithm is complete. In the figure shown, the algorithm completes with three switching points, and the time-optimal time scaling consists of maximum acceleration until s_1, followed by minimum acceleration until s_2, followed by maximum acceleration until s_3, followed by minimum acceleration to bring the robot to rest. This time scaling keeps the velocity as high as possible at all points on the path while assuring the trajectory is feasible for the actuators.

A key step in this algorithm is step 4, finding the next tangent point on the velocity limit curve. Instead of using a binary search guess-and-check approach, a more computationally efficient approach is to numerically construct the velocity limit curve and search for the next point where the motion ray is tangent to the curve. Clearly, at the point of intersection the motion ray is into the region of inadmissible states. As we search along the velocity limit curve, we eventually find a point on the curve where the motion ray is tangent to the limit curve. We can now proceed with the algorithm as before.

There are some other technical details, special cases, and improvements to the algorithm, some described in the book, but the description I've given covers the most important points. Because the time-optimal time scaling requires one or more actuators to operate at maximum capacity at all times, and because the dynamic model is never exactly known, this algorithm is rarely directly used in trajectory generation. Nonetheless, it provides a deep theoretical understanding of the maximum capability of a robot.

So this concludes Chapter 9. You now understand the basics of how to generate trajectories for robots, and how the dynamic equations of Chapter 8 can be used to find time-optimal trajectories along specified paths. In Chapter 10 we will study the problem of planning motions among obstacles.