In motion planning there must be some method for describing the shape of a path. Any method chosen must be continuous along the path of motion. The continuity must extend to the motion velocity as well. In real applications the continuity should also extend to the acceleration, because of the jerk limitations of current actuators. But, for simplicity, this effect will be regarded as insignificant, and the effects of a discontinuous acceleration may be neglected.
The continuity of the motion function in the zero, and first order derivatives suggests that a continuous mathematical function is required for modelling. This may be done by one single function for the entire motion, or by a set of functions that may do a piecewise approximation. A single function is hard to control over an entire path, and thus is not very desirable for this problem. A piecewise approximation of a manipulator motion is desirable, because of the nature of robotic motions. The motions tend to have local control stages, like acceleration, cruising, and deceleration. Since splines are well suited to piecewise approximations, they have become a method of choice for modelling robot motion. A description of the basic properties of splines is available in Cheney and Kincaid [1985].
A spline uses a set of knot points on a continuous curve to model a function passing through all these points. The spline is a piecewise approximate model, with individual curves for each of the segments constructed between points. How the spline estimates the curve varies between techniques. One fundamental measure for the curve estimation of a spline, is the degree. A first degree spline (C0) is a linear approximation of a line connecting a set of data points. It approximates using a set of straight lines between knot points. A Second degree spline (C1) approximates a line using a series of smoothly connected curves. These have the same first derivatives at the knot points, but not necessarily the same second derivatives. This type of spline is continuous for both position and velocity.
Figure 10.1 Figure 9.1: Spline Continuity
A Third degree spline uses many approximating curves that piecewise connect the set of knot points, with continuous first and second derivatives. This spline is also known as a ‘Natural Cubic Spline’. This family of splines is very dependable, but often results in unwanted ripples in the modelled function. There are more exotic variations on the simple splines which may be used.
A common alternative is ‘B-Splines’, which are similar in nature to the simple Splines. They approximate about a knot point, with respect to the previous and next knot points (see figure below). As the spline passes a knot point the function for the previous point now becomes unfelt, while the function for the current knot is at maximum value, and the function for the next point begins to have influence. The result of these overlapping functions is a smooth transition between knot points.
Figure 10.2 Figure 9.2: Some First order B-Splines are shown for Constructing An Example Spline
There are another form of splines called, Bezier Splines. They use some of the points as fixed points on the spline, and use other points as control points. The shape of a Bezier spline may be easily modified by shifting the control points.
Figure 10.3 Figure 9.3: Bezier Spline Approximation of a Curve
Some other methods do not force the spline to pass through any points on the curve. Barsky [1988] mentions a type of spline called a Beta-Spline, which may be of use in future work. A Beta-Spline is based upon the idea of curve tightness to points. And, it will in effect pull the curve tighter until the common ripples associated with cubic splines disappear. The Beta-splines are undesirable (at this stage) because they would add another degree of difficulty to the application, and introduce a new variable for tightness.
Robot Motion Planning requires the expression of robot position as a function of time. Robot positions are most commonly expressed as joint coordinates, or as an end effector positions in space coordinates. When robot positions are expressed in end effector space coordinates, they result in an ambiguity of robot configuration, due to singularities and redundancy of robot kinematics. When the expression of robot positions is done in joint coordinates there is no ambiguity, therefore, the joint positions will be used here.
The method for representing the path may be done several ways, but the two most common ways to express the motion are with i) a set of abstract parameters, or ii) with sets of positions and times in space. The use of abstract parameters can dramatically alter a path shape by changing one variable, this obviously adds a degree of difficulty. The direct use of points and time simplifies the application of any algorithm to manipulate it, by limiting the effects of all changes to local regions.
The problem of Motion planning requires a function that is continuous in position, and velocity, but discontinuous in acceleration for bang-bang control. In particular, the beta-splines are continuous in acceleration, thus are not desired. The desired function will have the ability to set the points the curve passes through, and then adjust the shape. B-Splines and normal splines may have the desired level of continuity, but it is very hard to change the shape without changing the knot points. A simple technique, with the ability to alter shape, is a Bezier Spline.
The basic theory of splines, that follows, will provide a good introduction to the concepts behind Bezier Splines.
Third Order Spline theory can be expressed quite neatly with the Hermite form. The Hermite form of a spline segment is expressed in terms of endpoints, and first derivatives at both the endpoints. The basic form may be seen below.
Figure 10.4 Figure 9.4: A Hermite Spline Segment
The spline segment parameters may be constructed, given that a set of four endpoint parameters be found for each segment of the spline. These segment parameters are subsequently used to find the value of the function, when that segment of spline is evaluated. The Hermite form guarantees that each point will be touched (i.e., every point is on the spline function).
The basic Hermite form of spline has one disadvantage, because it requires knowledge of the derivatives at the segment endpoints. It is possible to use an alternative formulation, which uses four points to determine the parameters of a segment.
Disadvantages may arise when the derivatives at segment endpoints must be determined. To overcome this problem a Bezier spline approximates four points with a single spline segment. The first and fourth points will be “passed through”, whereas the second and third points will serve to guide the spline (as ‘control points’).
Figure 10.5 Figure 9.5: A Bezier Spline Segment
The Bezier spline is similar to the Hermite form, except that the first derivatives at the endpoints are approximated with the help of the second and third points in the spline. This may be seen in the formulation given below
The resulting Bezier spline will have second order continuity along each segment, but may have a discontinuous second order derivative between segments (see next section). It may also be noted that this form is very easy to encapsulate in an algorithmic form.
An advantage of the application of Bezier splines is that their control points will have a local effect on the shape of the function, but little effect on the global shape of the function. The problem that must be dealt with when modelling motion with Bezier splines, is to ensure that the matching spline segments have equivalent endpoint values and first derivatives.
For Bezier Splines, the segment endpoints must be matched by making the joining endpoint values and first derivatives equal. To match the first derivative of the splines, one of the internal points in one of the joining segments must be adjusted to ensure the curve matching. To do this the method shown below was used.
This will mean that one of every four points (P2 here) within each segment is dedicated to matching the first derivative segment endpoints. The two endpoint values are explicitly specified (i.e., Pi4 = Pi+11), and the control point (P3) may be shifted to allow shape adjustment.
Explicit algorithms are required to use Bezier splines to model motion described with a set of points. The first algorithm will return a set of coefficients for each of the segments on the spline. The second algorithm will use these parameters to determine the value at any point in time along the spline.
The spline matching routine is provided with a set of ‘n’ points, distributed between the start and stop times of the manipulator. ‘n-1’ control points are also included between each of the ‘n’ via points. Also, ‘n-1’ time intervals are specified for the motion time between via points. The spline is required to start and stop with a first order derivative of 0.0. Using these data points and constraints, the spline is constructed in a sequential piecewise manner from the information provided.
Figure 10.6 Figure 9.6: A Bezier Spline Segment for Motion Modelling
This routine will result in ‘n-1’ path segments that are described by the four coefficients, a, b, c and d. With the spline parameters calculated for the ‘n-1’ path segments, it is easy to calculate the value of the function at any point in time.
After the spline parameters have been calculated, the point calculation may be repeated any number of times, very rapidly. Note that the derivatives of this function are easily found from the Bezier formulation, which is easily differentiated.
Figure 10.7 Figure 9.7: A Flowchart for Bezier Spline Modelling of a Motion
There are a few good reasons to use the bezier splines,
they are easy to apply to the problem,
they are easy to differentiate,
can represent a motion which has constant torque over a segment, but may be discontinuous between segments,
the curve shape may be adjusted locally, without changing the global shape of the curve,
they do not have the ripple associated with the cubic splines.
The splines have been implemented in software, as is described in the algorithms. This form is very neat and raises the next topic, “How may a set of points be selected for a motion path?”. This question is addressed in the next chapter.