Informatica 21 (1997) 651-655 651 
Steepest Descent Optimisation in th e Secondary Space of Redundan t Manipulators 
Jadran Lenarčič and Bojan Nemec Jožef Štefan Institute, Jamova 39, 1111 Ljubljana, Slovenia Phone: +386 61 1773 563, Fax: +386 61 1258 058 
jadran.lenarcicSij s.s i 
Keywords: redundant manipulators, steepest descent optimisation, optimum step size 
Edited by: Rudi Murn Received: April 15, 1997 Revised: September 9, 1997 Accepted: September 30, 1997 
To minimise a cost function in the secondary level of control of redundant manipulators, the gradient of the cost function is projected on the nuU space of the primary task. This projection, however, does not guarantee the maximum decrement of the cost function. In the present paper we rotate the null space of the primary task in order to find the niaximum optimisation step. By this improvement, the optimisation procedure can provide the desired solution in much less iterations. 


 Introductio n 
One of the emerging issues of the new generation of manipulators, in particular service robots, is the kine­matical redundancy. The mechanism of a redundant manipulator possesses superfluous degrees of freedom with respect to the motion constraints posed by the assigned primary task. Hence, as a secondary task, it can operate by simultaneously optimising a set of performance criteria or can avoid obstacles and ill-conditioned configurations. Assume that the primary task is to plače the hand in a given spatial position and orientation. The rest of the mechanism will stili be able to move (see Fig 1). This is the so-called self or secondary motion of the mechanism and is a typi­cal property of kinematically redundant manipulators. Prom this viewpoint also the human arm contains a de­gree of redundancy. By rotating the elbow in a fixed pose of the hand, the human arm mechanism accom­modate its static and dynamic characteristics. 
A majority of efforts in treating redundancy have been concentrated at the kinematic level of control with respect to different type of criteria with robots moving in complex environments avoiding obstacles, as reported in [1], and undesired or ill-conditioned con­figurations, as reported in [2, 3]. Many authors based their approach on the utilisation of the pseudoinverse of the Jacobian matrix associated with the primary task, such as [4], which is a purely numeric approach. It has intrinsic inaccuracies and accumulates errors that become larger as the velocity increases. To over­come these difficulties, some authors developed sym­bolic Solutions to this problem, such as [5]. It must be pointed out, hovvever, that no symbohc solution can be developed for a general-type redundant manipulator uhless certain conditions are met by the mechanism. 
Figure 1: A 6-degree-of-freedom manipulator that po­sitions end effector in x,y plane is kinematically redun­dant 
The calculation schemes based on the pseudoin­verse are procedures of local optimisation [6]. They imphcitly minimise a norm of joint velocities. Vet, the central point and a distinctive property of various pseudoinverse-based methods is in the determination of the null space projection operator associated with the secondary task [7]. A proper selection of the null space projection operator in combination with the null space vector provides a secondary motion of the ma­nipulator that respects different types of criteria, such as joint torque minimisation, obstacle avoidance, sin­gular pose avoidance, etc.[8, 9]. [10, 11] reported some results obtaining global optima with integral type of criteria. [12] optimised the weighted null space pro­

652 Informatica 21 (1997) 651-655 
jection operator in order to avoid instabilities. An al­ternative to the pseudoinverse-based methods is the extended Jacobian method introduced by [13]. [14] described a new formulation of this algorithm that is well suited for more general choices of the secondary criterion. Characteristics of different optimum solu­tions were studied in [15]. 
In a vast variety of applications, the secondary task of a redundant manipulator, formulated in terms of an optimisation, is based on a gradient-type proce­dure. Usually, not to disturb the primary task execu­tion, this gradient is mapped in the null space of the Jacobian matrix pertinent to the primary task. Unfor­tunately, the projection in this null space may distort the gradient vector, so that in a final consequence it may not provide a decrease of the cost function and the optimisation procedure may become inefRcient. In the present work, to overcome the difficulty, we rotate the null space operator in order to achieve the best di­rection and amplitude of the optimisation step in the domain of the secondary task. By this improvement, the optimisation procedure becomes more effective. 

2 Mathematical background 
Let the primary task of a redundant manipulator be to achieve some desired poses p (such as position and orientation of the hand) that are given as a function of joint coordinates q (angles or linear displacements in joints), where vector p is of dimension m and q of di­mension n. Typically, vector p is a set of non-linear in­dependent algebraic equations where q are arguments of trigonometric functions. It is expressed in the well know differential form [16] by 
dp — Jpd q = O, (1) 

\vhere J p is a m x n Jacobian matrix that incorpo­rates the derivatives dp/dq\. We assume that n > m and 
Jpd p — dq = 0. (2) 

If J p J p of dimension m xn isn't singular, the fol­lowing 
Jp = Jp (JpJp ) (3) 

is the so-called unweighted pseudoinverse of J p whose dimension is mxn. The utilisation of the pseu­doinverse in solving the task to move a redundant ma­nipulator in a given p implicitly leads to a minimisa­tion of joint velocities [16]. To satisfy other criteria, one can introduce additional optimisations that must J. Lenarčič et al. 
not interfere with the primary task. Let the secondary task be expressed similarly to the primary task 
ds — Jsd q = O, (4) 

where the objective is to achieve a q that corre­sponds to given values of secondary task coordinates s (for instance joint torques), and J s is the Jacobian that includes derivatives ds/dq\ . If s is of dimension /, J s is of dimension I x n. If n > Z , we can take advantage of the n x I pseudoinverse 
Jg ds — dq = 0. (5) 

Arrange now the increment of joint coordinates into the primary dqp and the secondary dqN (subordi­nated) part, so that dqN does not produce any change of primary coordinates p 
dq = dqp + dqN • (6) 

By multiplying with J p we get 
dp = Jpdqp -I- JpdqN. (7) 

Since JpdqN = O, (8) 
we have 
dp = Jpdq p => dqp = Jpd p (9) 

Let dqN = Ni3dqs (10) 
where dqs is an arbitrary ?i-dimensional vector of joint increments associated with the secondary task, while 'Np is of dimension n x n 
JpN p = 0. (11) 

According to [17] 
N p = I - J+J p (12) 

lies in the null space of J p so that dqN and dqp are orthogonal. The null space projection operator N p is Hermitian and idempotent, N p ' = Np,NpN p = Np . 
The kinematic redundancy, in our opinion, must be understood as an instantaneous property associated 
STEEPEST DESCENT OPTIMISATION 
with the dimension of the null space of the primarytask. We thus define the degree of redundancy as therank of the null space projection operator

D = rank {Np} — TI — ranfc {Jp} . (13)
D is the achievable order of the secondary motion that can change throughout the workspace of the ma­nipulator mechanism in dependence on q. We assume in this work that I > D. 
By substituting (10) into (6) and by multiplying with J S we have 
ds = Jsdq p + JsNpdq s (14) dqs = (JsNp)+(d s - Jsdqp) . 
The secondary task coordinates depend on (iqN and dqp . We denote 
dsp = JsdciP, dsN -3sdqN => ds = dsp + dsN-(15) 
If we take into account (6,10,14), a complete incre­ment in joint coordinates can be written as 
dq_ = Jp+d p + Np(JsNp)+(d s - JsJjdp) , (16) 
which is the know task priority approach where the first part of the joint increment is the particular so­lution associated with the primary task. It is of a higher priority in comparison with the second part which is the homogeneous solution associated with the secondary task [1, 4]. 
 Secondary domain 
In this work, an increment in joint coordinates is re­ferred to as the secondary motion (self-motion) of a redundant manipulator when it does not produce any increment in the primary task coordinates. In connec­tion with the definition of the manipulability ellipsoids [18], a sphere dqldqs = 1 produces an ellipsoid in /­dimensional space of ds whose principal axes are the eigenvectors of J s Jg ^^'^ their lengths are the related singular values. It is clear, however, that only a part of elements ds in this elhpsoid can be accomplished by the secondary motion of the redundant manipulator. Note that there is some controversy in the definition and utilisation of manipulability when different types of task coordinates are treated simultaneously, such as hnear and angular velocities. [19, 8] dealt with this problem. 
Informatica 21 (1997) 651-655 653 

 The secondary motion can only be assembled in the  null space of the Jacobian matrix J p where a vec­ tor dqs is projected through Np into dqN. Thus, an element of a sphere (iqg (iqs = 1 is transformed in the sphere dq^dqt<! < 1. The null space of J p 
 is spaned by the n-dimensional orthonormal eigen­vectors of matrix NpN p = Np , denoted by Ep = (ei,e2, ,ep) . Thus, any (iqN as a function of pa­rameters 7 = (71, ,7L))'^ 
dqN = Ep 7 (17) 
is an element of a sphere if 
dqTdqN=7l+7 l + -- + 7l) = l- (18) 

The values of dsN (15) that are functions of dqN constrained by (18) form that part of the vector space of ds that can be accomplished by the secondary mo­tion of the manipulator. Vectors dsN produce an ellipsoid whose principal axes are the /-dimensional eigenvectors of matrix JsNp(JsNp)' ^ (denoted by uj , U2, , UD) , while the corresponding singular val­ues of JsN p are the lengths of these principal axes. The secondary manipulabilitv ellipsoid characterises the domain of the secondary task bounded by (18). It describes the potential of a redundant manipulator to solve the secondary task with no interference with the primary task in a given location determined by the joint coordinates q [20]. 

4 Best optimisation step 
Assume that the secondary task of a redundant manip­ulator is to minimise a quadratic cost function (which is a very reasonable assumption for a vast variety of practical implementations, e.g. joint torque minimisa­tion) 
C = s W s —^ mini (19) 
where W is a diagonal / x I full-rank matrix of pos­itive weights Wi, while dqN is constrained by the pri­mary task. An iterative procedure is to provide a se­ries of dqM that step by step minimise c and do not interfere with the primary task. In a commonly used gradient projection technique to minimise a scalar cost function [17, 8], the joint displacement is 
dq = fcpJ+dp - A;sNpJ+ 11 ^ I • (20) 
where ks and kp are selected in order to assure the convergence of the numerical procedure. The trouble 654 Informatica 21 (1997) 651-655 

with such an approach is that in general the projec­tion of the gradient in the null space of J p may not provide the maximum decrease of the cost function. Hence, the iterative procedure may not be able to lo­cate the desired minimum in an acceptable number of iterations. There are two remedies for it. One is to adapt the projection vector directly in the domain of the secondary task. This can be done by searching the optimum projection vector produced by joint in­crements that lie the secondary domain. The other way is to adequately rotate the null space of Jp . In the present paper we show only the second possibility. 
It is well known [16] that a vveighted pseudoinverse 
T + A-^jJ(JpA-ij?) -(21) 
•'PA 

minimises a performance criterion of joint velocities in the form of q^A q vvhere A is a positive definite weighting matrix. The weighted null space projection operator for the weighted pseudoinverse Jp^^^ is given by 
NpA =I-JiAJp -(22) 

This null space projection operator is idempotent but in general is not Hermitian. It rotates the null space of the Jacobian in what was termed the ef­fective null space by [12]. It is the central point of many attempts to resolve redundancy with solutions possessing different characteristics that assist to avoid obstacles and singularities or minimise a given crite­rion. In [7] one can find a variety of possibilities later implemented and improved by other authors. For in­stance, [10, 11] used this approach in order to incor­porate some global properties in the optimisation of dynamic joint torques. [21] showed the limitations of these methods when they are implemented indepen­dently on a real mechanism without considering its ki­netic behaviour. Lately, [12] reported a vveighted null space projection operator suitable for a vveighted joint torque optimisation vvith the aim to avoid instabilities that arise from unrealisable joint velocities. 
We show here that it is possible to determine a vveighted null space projection operator that provides a steepest descent minimisation of a given cost func­tion. For this purpose we search for an optimum ds that minimises a quadratic form c = c(s + ds) (vvhere C is given in (19)) vvith respect to the primary task (1). 
The associated Lagrangian, in vvhich we substitute ds by Jsd q , is as follows 
(23) 
+ 
+rfq'^Ji'WJsdq + X^{dp -Jpdq) 

Here,A is the vector of Lagrangian multipliers. The derivative of L vvith respect to dq must vanish 
J. Lenarčič et al. 

I —I 2JJ (1 ^ }. + 2j|WJsdq - JjA = o, 

I ds\ 
(24) 

as well as its derivative with respect to A so that (1) holds. As a result, 
dq=lA-ij?A-A-ij|{g| (25) 

where we introduced the following notation 
A = j|WJs. (26) 

Since A is singular when / > m and cannot directly be inverted, one can utilise either the damped least square solution 
,-1 (j|WJ s -I- al) -1 (27) 

or the formulation 
A-i=J+W-i(J+)T . (28) 

Multiplying (25) by J p gives 
;A = (JpA-ij5)""i(d p + JpA--^J '11'} (29) 
Then by substituting A again in (25), by taking into account (21,22), as vvell as A^^Jg" = Jg'W"^ , and by introducing scalar constantsfcp,ks to control the iteration step we get 
dc_
dq = fcpJjt^dp -fcsNpAJg" \ (30) 

vvhich is analogous to the standard formula (20) vvith a vveighted pseudoinverse and the corresponding null space projection operator, vvhile the vveighting matrix is given by (26) and its inverse by (27) or (28). 
The approach (30) turns out to be numerically very effective if compared to (20). The necessary number of iterations to solve the primary and the secondary task can drastically be decreased. While in some cases the formulation (20) fails to carry out the imposed optimi­sation in the secondary le vel, the approach formulated in (30) guarantees the best solution to the primary and to the secondary task simultaneously. 
STEEPEST DESCENT OPTIMISATION 
 Conclusions 

The paper deals with a steepest descent local minimi­sation in the level of the secondary task of a redundant manipulator. In previously reported pseudoinverse­based optimisation techniques, the gradient of a given cost function is directly mapped in the null space of the primary task. The projection in the null space may distort the gradient and the optimisation proce­dure may be troubled. In our work, we overcome the problem by utilising an optimum weighted pseudoin­verse. By this improvement, the optimisation proce­dure becomes more efFective and numerically robust. It finds a solution in less iterations and its potential to locate the optimum solution is greater. 
References 

[1] Maciejewski,	 A.A., Klein, CA . (1985) Obsta­cle avoidance for kinematically redundant manip­ulators in dynamically varying environments, Int. J.Robotics Res. Vol. 4, No. 4, pp.109-117. 
[2] Baker,	 D.R., Wampler, C.W. (1988) On the in­verse kinematics of redundant manipulators, Int. J.Robotics Res., Vol. 7, No. 2, pp. 3-21. 
[3] Chang,	 K.-S., Khatib, O. (1994) A dynamically consistent strategy for manipulator control at sin­gularities, Advances in Robot Kinematics, Kluvier Academic Publ, Dordrecht, pp. 221-228. 
[4] Nakamura, Y., Hanafusa, H., Yoshikawa, T. (1987) Task-priority based redundancy control of robot ma­nipulators, Int. J.Robotics Res., Vol. 6, No. 2, pp. 3-15. 
[5] Ghosal,	 A., Roth, B. (1988) A new approach for kinematic resolution of redundancy, Int. J.Robotics Res., Vol. 7, No. 2, pp. 22-35. 
[6] Nenchev,	 D.N. (1989) Redundancy resolution through local optimisation: A review, Int. J. Robotic Systs., Vol. 6, No. 6, pp. 769-798. 
[7] Hollerbach,	 J.M., Suh, K.C. (1987) Redundancy resolution of manipulators through torque optimiza­tion, IEEE J. Robotics and Automat., Vol. 3, No. 4, pp. 308-316. 
[8] Yoshil{awa, T.(1996) Basic optimization	 methods of redundant manipulators, Laboratorij Robotics and Automat., Vol. 8, No. 1, pp. 49-60. 
[9] Khatib,	 O. (1996) The impact of redundancy on the dynamic performance of robots, Laboratory Robotics and Automat, Vol. 8, No. 1, pp. 37-48. 
[10] Nedungadi,	 A. Kazerounian, K. A (1989) local solution with global characteristics for joint torque Informatica 21 (1997) 651-655 655 
optimisation of a redundant manipulator, J.Robotic Systs., Vol.6, No. 5., pp. 631-654. 
[11] Kazerounian,	 K., Wang, Z. (1988) Global ver­sus local optimization in redundancy resolution of robotic manipulators, J. Robotics Res., Vol. 7, No. 5, pp. 3-13. 
[12] Hu,	 B., Teo, C.L., Lee, H.P. (1995) Local opti­mization of vveighted joint torques for redundant robotic manipulators, IEEE Trans, on Robotics and Automat, Vol. 11, No. 3, pp. 422-425. 
[13] Baillieul, (1986) J. Avoiding obstacles and resolv­ing kinematic redundancy, IEEE Int. Conf. Robotics and Automat., pp. 1698-1704. 
[14] Klein,	 C.A., Chu-Jenq, C., Ahmed, S. (1995) A new forraulation of the extended Jacobian method and its use in mapping algorithmic singularities for kinematically redundant manipulators, IEEE Trans, on Robotics and Automat., Vol. 11, No. 1, pp. 50-55. 
[15] Park, J.,	 Chung, W.-K., Youm, Y. (1996) Char­acteristics of optimal solutions in kinematic resolu­tions of redundancy, IEEE Trans, on Robotics and Automat, Vol. 12, No. 3, pp. 471-478. 
[16] Whitney, D.E.	 (1969) Resolved motion rate con­trol of robot manipulators and human prostheses, IEEE Trans. Man-Mach. Sys., Vol. 10, No. 2, pp. 47-53. 
[17] Liegois, A. (1977) Automatic supervisory control of the configuration and behaviour of multibody mechanisms, IEEE Trans. Sys., Man, Crjbern., Vol. 7, No. 12, pp. 868-871. 
[18] Yoshikawa,	 (1985) T. Manipulability of robotic systems, Int. J. Robotics Res., Vol. 4, No. 2, pp. 3-9. 
[19] Doty,	 K.L., Melchiorri, C., Schwartz, E.M., Bonivento, C. (1995) Robot Manipulabihty, IEEE Trans, on Robotics and Automat., Vol. 11, No. 3, pp. 462-468. 
[20] Nenchev, D.N.	 (1992) Restricted Jacobian matri­ces of redundant manipulators in constrained mo­tion tasks, Int. J. Robotics Res., Vol. 11, No. 6, pp. 584-597. 
[21] Maciejewski,	 A.A. (1991) Kinetic limitations on the use of redundancy in robotic manipulators, IEEE Trans, on Robotics and Automat., Vol. 7, No. 2, pp. 205-210.