Abstract
By taking advantage of the well-behaved nature of singular values and vectors, the computational expense of determining the SVD of the Jacobian matrix can be reduced to such an extent that on-line calculation becomes feasible. This permits more intelligent use of the extra degrees of freedom present with redundant m a n i p ulators, particularly with respect to the optimization of various secondary criteria, including obstacle avoidance, under the constraint of a specified end effector trajectory.
I. Introduction
In recent years the singular value decomposition (SVD) has become a popular tool for analyzing the kinematic and dynamic properties of robotic manipulators. It plays a particularly prominent role with regard to redundant manipulators, both in term of analyzing the significance of the extra degrees of freedom 121 and in specifying a side criterion which can be optimized using these redundant degrees of freedom. In many cases, these side criteria are some quantitative measure of the qualitative concept of dexterity. Most of the dexterity measures proposed are some function of the singular values of the Jacobian matrix. The most common of these is perhaps the manipulability measure proposed by Yoshikawa [12] which is defined as the square root of the determinant of the matrix JJ* which is simply the product of the singular values of J . Other proposed measures include the trace of the above matrix, the minimum singular value of the Jacobian, the compatibility index, and isotropy (all equal singular values).
I. Introduction
While all of the above measures have a physical significance and justification for their use, the key point here is that they are all closely linked to the SVD. Yet in spite of this fact, the full decomposition is usually limited to the analysis of manipulator configurations and is not considered for implementation in on-line control. This work demonstrates that, with the right formulation, the SVD is computationally feasible for use in real-time control. Traditionally, the computation of the SVD of an arbitrary matrix is an iterative procedure so that the exact number of computations cannot be known a priori.
I. Introduction
However, the control of robotic systems is not based on the solution of arbitrary matrix equations but quite frequently involves the solution of equations based on the Jacobian matrix. The current Jacobian for a system can be regarded as a perturbation of a previously known matrix for which perturbation bounds on the singular values and singular vectors can be established. Knowledge of the previous state can be exploited during the current calculation of the SVD in order to reduce the overall computational burden. This results in a computational scheme capable of calculating the SVD of the Jacobian for use in real-time control of manipulators.
Perturbation Bounds on the SVD
All SVD algorithms possess an iterative component designed to orthogonalize the columns (or rows) of the matrix being decomposed. Clearly, the more orthogonal these columns are to begin with, the fewer the number of calculations are required to reach convergence. Thus, if one considers the current manipulator Jacobian, denoted by J ( t + At), to be a perturbation of the previous Jacobian J ( t + At) = J ( t ) + A J ( t )
Perturbation Bounds on the SVD
(1) the SVD of which is known and given by
Perturbation Bounds on the SVD
then the matrix J ( t + A t ) V ( t ) will have nearly orthogonal columns provided the perturbation A J ( t ) is small relative to J ( t ) . The foundation of the above lies in the fundamentally well-behaved nature of the SVD of a matrix. The perturbation bounds on singular values, denoted by U;, are very well-known and it is easy to show that
(3)
The perturbation bounds on the rotation of subspaces defined by singular vectors are not as widely known but are also well-behaved (111. In particular, consider a partitioning of the Jacobian into two singular subspaces of the form where U; and v; are the columns of U and V , respectively, and the integer k denotes the partitioning between the large and the small singular values. The angle between the subspace Jo(t) and its perturbation Jo(t + Ai!) can be defined as where PJ, denotes the orthogonal projection onto the subspace Jo. With the above definition, an upper bound on q5 will guarantee that the subspaces defined by the singular vectors will change in a well-defined manner.
(3)
The bounds for rotations of subspaces are closely related to the spacing of the kth and the k + Ith singular values.
(3)
In particular, if the gap between Ok of J ( t + A t ) and ~k +~ of J ( t ) is denoted by 6 then it can be shown [I11 that the bound on subspace rotation is given by
(3)
The above bound guarantees continuity of the singular vectors as long as 6 does not approach zero. Geometrically, what occurs when 6 -+ 0 is that there are multiple equal singular values. When this occurs the singular vectors are ill-defined since the subspace associated with the corresponding singular values is no longer one dimensional and any orthogonal set of vectors which spans this subspace is a valid set of singular vectors.
III. Calculation of the SVD
The Golub-Reinsch algorithm is generally regarded as the most efficient and numerically stable technique for computing the SVD of an arbitrary matrix. However, an algorithm based exclusively on Givens rotations is more suited t o take advantage of the incremental perturbations of the Jacobian matrix. The basis of this algorithm is the ability of a single Givens rotation to orthogonalize any two columns on which it operates. In particular, if ai and a j are denoted as the ith and j t h columns of the matrix A , then multiplication by a Givens rotation results in the new columns, a: and a;. given by a: = ai cos(O) + a j sin(0)
III. Calculation of the SVD
It can be easily shown that one can choose the rotation angle 0 such that a; and a, are orthogonal. To orthogonalize all of the columns, Givens rotations are applied to all combinations of pairs of columns, a process referred to as a sweep. Unfortunately, a single sweep will not, in general, orthogonalize all of the columns of a matrix since subsequent rotations can destroy the orthogonality produced by previous ones, however, the procedure can be shown to converge.
III. Calculation of the SVD
While the number of sweeps required to orthogonalize the columns of the Jacobian cannot, in general, be determined a priori it should be clear that the more orthogonal the columns are to begin with, the fewer the number of sweeps required. Simulation results show that by using the knowledge of the previous SVD as discussed in section I1 above, the number of sweeps can be cut by a factor of three. In addition, it can be shown that in many cases a single sweep is sufficient so that convergence tests can be removed from the computation. A further reduction in the computational complexity of the equations for computing the SVD can be gained by noting that the majority of the rotations are very small in magnitude. As an example, consider a typical trajectory for a PUMA robot, presented in Fig. 1, which illustrates the singular values of the Jacobian for each configuration of the trajectory along with the maximum rotation angle required for orthogonalization. Note that for the majority of the trajectory the maximum rotation angle is very small, however, there exist three peaks, two of which are very sharp. of subspaces in section 11. Since the maximum plane rotations required during the algorithm are very small in magnitude outside of a few isolated peaks, a small angle approximation is useful in reducing the computational effort required in computing the SVD. For small 8 the approximations cos(8) M 1 and sin(8) M 8 can be used so that the number of multiplications required in calculating the rotation of (7) and (8) is cut in half. Those configurations for which the small angle approximation is not valid are easily identified by examining the spacing of the singular values. In terms of actual CPU time, an algorithm using the previous estimate of the SVD as well as the small angle approximations was implemented in PASCAL and executed on a VAX785. The time required to calculate the SVD of the Jacobian for the PUMA manipulator used in Fig. 1 was 5 
IV. Control of R e d u n d a n t Manipulators
Real-time computation of the SVD can improve the utilization of redundancy in robotic systems both in terms of implementation of the control equations as well as in the evaluation of various measures of dexterity. The kinematics of manipulators is frequently presented in the form
IV. Control of R e d u n d a n t Manipulators
where i is an rn dimensional vector specifying the end effector velocity, 8 is an n dimensional vector denoting the joint velocities, and J is the m by n Jacobian matrix.
IV. Control of R e d u n d a n t Manipulators
For redundant manipulators n > m so that the general solution to (9) is typically presented in the form where + denotes the pseudoinverse, ( I -J + J ) is a projection operator onto the null space of J , and 4 is an arbitrary vector in space. The second term in (10) is the homogeneous solution to (9) since it results in no end effector velocity. This homogeneous solution is frequently used to optimize some secondary criterion under the constraint of the specified end effector velocity by choosing q5 to be the gradient of some function of 8 (31. Some of the secondary criteria that have been applied include joint range availability, singularity avoidance, various measures of dexterity, and obstacle avoidance. With the complete SVD available the projection operation becomes trivial since the singular vectors v i for t > i > n specify an orthonormal basis for the null space. Thus the relative advantages of using the homogeneous solution for alternate secondary criteria can be easily evaluated. The homogeneous solution can also be used to optimize secondary criteria defined in Cartesian space, either to impose a priority to the manipulation variables 19) or to avoid obstacles [ 5 ] , by using
IV. Control of R e d u n d a n t Manipulators
where the subscript 2 refers to the secondary criterion. The overall solution is then given by substituting (11) into ( 
V. Dealing with Singularities
Singular configurations can be identified by a mathematical change of rank in J which physically represents the inability of the manipulator to achieve an arbitrary end effector velocity. A general approach to resolving the discontinuity at singular configurations and maintaining a well-conditioned formulation which results in physically meaningful joint velocities is to use the damped least-squares formulation independently proposed in 18) and [lo] and extended in 16). The damped least squares solution of (Q), denoted by &'), is the solution which minimizes the sum 1 1 2 -Jd(( + Alle((. Unfortunately, the norm of the solution is a nonlinear function of the d a m p ing factor, A, so that iterative techniques such as Newton's method must be applied to determined the optimal damping factor for a given constraint on the physically achievable joint velocity norm.
V. Dealing with Singularities
While the damped least-squares solution is optimal in the sense described above, it may be undesirable to implement due to the iterative nature of calculating the appropriate damping factor A. It can be shown that the characteristics of the damped least-squares solution are very similar to those obtained using a continuous version of the truncated SVD solution. This type of solution will be denoted dC) and is defined by advantages of using this form of a solution are that, when the SVD is available, it is extremely easy t o compute.
V. Dealing with Singularities
By performing a worst case analysis, it can be shown 141 that the error in the continuous truncated SVD solution can be as much as 40% greater than the damped least-squares solution. While a 40% discrepancy may at first seem as cause for concern, it can be shown that this case will occur only under very special circumstances. In particular, analysis shows that it will occur only if the manipulator is in a configuration which results in two or more very small and equal singular values. That is, the manipulator must b e going into a multiple singularity. In addition, the commanded end effector velocity must be restricted to these two or more directions which represent the lost degrees of freedom. Finally, the magnitude of this commanded end effector velocity must be on the order of magnitude of the very small singular values. An example of this condition illustrating the plane defined by the singular vectors associated with the two equal and very small singular values is presented in Fig. 2 . Since these conditions are very restrictive and easily identified when the SVD is available, the more accurate damped least-squares solution can be employed if desired. In these cases, the value of c provides a good starting point for the Newton iteration scheme.
VI. Conclusions
It has been shown that the incremental manner in which the Jacobian changes, along with the perturbation bounds on singular values and vectors, allows one to reduce the computational expense of calculating the SVD in three ways. First, the singular vectors from the previous calculation can be used to pre-orthogonalize the current Jacobian. Second, by virtue of nearly orthogonal columns, the iterative nature of the calculations can be prevented thus avoiding convergence tests. Finally, since the few rotations required for orthogonalization are small in magnitude, approximations can be used. The advantages of having the SVD available in redundant manipulator control include the optimization of secondary criteria for dexterous operation, obstacle avoidance, and torque minimization as well as the identification of physical limitations corresponding t o singular or near-singular configurations.

{'paper_id': '27751766', 'title': 'Real-time SVD for the control of redundant robotic manipulators', 's2_url': 'https://api.semanticscholar.org/CorpusID:27751766', 'source': 'S2ORC'}