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.