11. Chapter 10: Finding Near Optimal Robot Motions
As was described earlier, it is only necessary to find a few points during the motion and the Bezier spline will be fitted to model the motion. The next consideration is determining the motion between two end points and extracting some points for the spline model of the motion.
The motion will be described with a preset number of points and the motion may evolve between the points in many ways. Once this arbitrary path has been determined, the time between points may be adjusted in a simple manner to reduce path time to a short duration.
The path should be generated so as to create a table of values for the motion. This motion will be made over a very long time to ensure that the robot moves very slowly, and therefore the motion will not violate any joint torque constraints. The table will therefore contain ‘n’ points on the path, and ‘n-1’ control points on the path. The ‘n-1’ time durations on the path will be given large values (the definition of large is dependant upon the manipulator). A total time for the path was made to be more than 30 seconds for the manipulator used here.
The actual shape of the path is important. The path has to be described within a specified number of steps. These steps are based upon the number of Bezier spline segments specified. Here, 3 spline segments were chosen for simplicity, thus a total of seven points are used (four knot points and three control points). The start and stop velocities of the manipulator have to be zero (as do the accelerations). The velocity should generally have the highest value at the center of the path. These particular requirements could be met with a scaled cosine function, as applied to joint interpolated motion.
Figure 11.1 Figure 10.1: A Motion Plan With A Bezier Spline
The scaled cosine function was chosen for a few of its obvious benefits. It can guarantee zero velocity at the path end conditions. The function also provides a smooth transition from start to finish, without having to find a complex mathematical solution (like fitting coefficients to a polynomial). Considering that this path is only providing an initial guess for the path, the actual function is not an important issue.
Figure 11.2 Figure 10.2: The Use of Cosine Functions for Path Planning
This method accounts for finding points during motion, and preparing a list of points to construct a Bezier spline for both joints. The reader may notice the functions ‘f1’ and ‘f2’. Their purpose is to precalculate the fraction of displacement, from time. ‘f1’ will estimate the normalized displacement for the start of a spline segment. ‘f2’ will estimate the displacement for segment control points. This is 2/3 of the way along the segment, because the other control point 1/3 along the segment is used for matching velocities between spline segments. The algorithm also makes it obvious that the manipulator moves with joint interpolated motion, with the joints stopping in unison. The values of motion positions and times are thus used to build a table, which may be used to determine the Bezier spline segments.
The cosine function may not provide a shape that can be used to represent optimal paths. It was suggested by Rajan  that the most optimal paths will have some curvature in joint space. This means that joint motions may reverse, or have irregular shapes when following an optimal path.
As mentioned in the last section, it is desirable to have paths that have curvature in joint space. This will allow joint reversals, which will allow joints to move into positions of lower inertia, and thus will reduce the time needed for a path. Joint space representations of such paths are shown below. The method presented above will have a straight line motion in joint space. This is because the joint position functions are both based on the same cosine function.
Figure 11.3 Figure 10.3: Robot Motions in Joint Space
The curvature shows some interaction of the joints. This curvature may result in faster motion times. Rajan  cites one case in which a straight path in joint space took 7.38 seconds, and a curved path in joint space took 4.37 seconds. Thus, a more optimal path may be found by accounting for some curvature in joint space. The curvature can be described as the result of compensation for interaction between joint motions. Thus, to help generate a better suggestion for an initial path, a motion ‘coupling’ term will be introduced.
To be more precise, if each joint could ‘respond’ when other joints are undergoing motion, then this could create a curvature in the joint space path. This may be accomplished by adding some factor of coupling, in which some of the motion from one joint is transferred to the other. A result could be, a large motion in one joint would result in a relaxation of the other joint.
This method is not meant to be empirically correct, but merely to generate some path guesses which are good start points for optimization. Without coupling, the joints will be very close to a local minima which is the straight line in joint space (this will be discussed more in the next chapter).
An algorithm is shown for calculating a motion path based upon the ‘coupling’ term.
The formulation above is almost the same as for the straight line case, except that some curvature in joint space is induced. It can also be seen that this coupling has the most effect at the midpoint of the motion. The reader should be aware that the definition of coupling is very loose. In the above function, coupling is based on a ‘sin()’ function. This is going to give a small curve in joint space, which can guide the optimization routines to a solution that is not straight in joint space. This method will not provide the sort of loop that is optimal.
Figure 11.4 Figure 10.4: Joint Space Effect of Coupling Factors
The value of the coupling term has the most effect. If the term is negative and one joint is in an accelerating motion, the other joint will relax in the opposite direction. The effect will be that the coupling will reduce joint torques and allow the manipulator to move faster.
Coupling will create a curved shape in joint space, which may give sub-optimal paths and lead to a good start for optimization. By choosing the best coupling value, a good guess may be found in a short period of time without using very sophisticated mathematical techniques.
Before using the powerful optimization routines, it is best to spend some time improving the initial guess. This method focuses on two techniques used together. The first technique to be described is a time scaling routine which will reduce the path time to its minimum. This is done by reducing the time steps in the motion as much as possible. The second technique involves trying to alter the coupling term to produce the motion with the least time.
The path shape will be determined by the algorithm with the coupling term. And, this path will have very long time steps, which should be reduced.
The preferred technique is to move along the path and reduce the time steps by a small amount. The change is kept if it does not cause a violation of the joint torque constraints. This procedure is repeated until none of the time steps may be reduced any further.
More specifically the time steps in the path will be reduced by some small fraction. As long as the path is valid, to begin with, this method will always produce an answer in a finite time. The choice of a reduction limit allows the search to be limited to a reasonable degree of accuracy and time. The typical run time for this routine was less than five seconds on a Sun 4.
Another method that could have been tried, is to reduce one time step, as much as possible. Then reduce the next time step as much as possible and so on until all time steps are reduced. This method would still require many repetitions for the path and thus would probably not make much difference in the convergence time. Other methods could have been used, but were deemed excessive for this thesis.
This method is able to take a path pre-described with a certain coupling factor, and determine the time the motion requires. This only leaves the problem of determining the optimal coupling term.
Some examples of a path are shown below. The time for the path has been determined, using a few different values for the coupling coefficient. These paths have also had their time steps reduces by the methods described above, thus the original shape may be slightly deformed.
Figure 11.5 Figure 10.5: Sample Paths for Varied Coupling Values: Paths with Coupled Joint Motion (after time reduction routines)
Figure 11.6 Figure 10.5: Sample Paths for Varies Coupling Values (continued)
Careful observation of the graphs will reveal the coupling effects. The reader should also note the path times are not symmetrical about the path shape with the coupling factor equal to zero. This suggests that a non-zero coupling term could be found that provides improved results.
The coupling term is very easy to adjust, and test. Therefore, this leads to a very simple method for attempting to reduce the path time. To find the best coupling factor, it should not be varied more than between -1 to 1, and even more realistically the bounds of 0.5 to -0.5 were found to be practical.
The coupling verses time function has a few minima, as illustrated below. This eliminates the possibility of using a simple reduction technique like Newton-Raphson. Thus it was determined to be better to perform a pattern search for the best coupling term.
Figure 11.7 Figure 10.6: Approximate Graph of Effect of Coupling Factor on Motion Time (Not derived experimentally, only given for illustrative purposes)
The pattern search simply evaluated the path times at eleven points bounded by -0.5 and 0.5 at intervals of 0.1. The best point was then used as the basis for an equivalent search that was bounded by an interval of ±0.1 about the previous best value. After the next success was found, the same process was repeated around the new value. After completion, this search tended to produce what could be said to be a motion with a good time. The typical calculation time for this algorithm is a period of about one minute.
The motion which was explored in the previous pages was run through this stage of optimization, and produced the results seen below. This set of results testifies to the value of using a coupling term. It will be shown later that the path in figure 10.7 has an optimum time of about 3.1 seconds. Thus the path shown is a good guess, and a much better guess than that with a coupling factor of 0.0, which required a motion time of 5.4 seconds.
Figure 11.8 Figure 10.7: Final Path Produced by Coupling, and Iterative Reduction (couple = -0.0608, tpath = 3.9 seconds)
Even though the path time is good, it may be easily identified as non-optimal.
The results presented here allow a good first approximation for a robot motion. A good second optimization phase may now follow. If further research using this technique was to continue, the researcher would be well advised to use a more complex curvature in joint space (for the coupling term).