nexoncn.com

文档资料共享网 文档搜索专家

文档资料共享网 文档搜索专家

当前位置：首页 >> >> Grasp Analysis as Linear Matrix Inequality Problems

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 16, NO. 6, DECEMBER 2000

663

Grasp Analysis as Linear Matrix Inequality Problems

Li Han, Jeff C. Trinkle, and Zexiang X. Li, Member, IEEE

Abstract—Three fundamental problems in the study of grasping and dextrous manipulation with multifingered robotic hands are as follows. a) Given a robotic hand and a grasp characterized by a set of contact points and the associated contact models, determine if the grasp has force closure. b) Given a grasp along with robotic hand kinematic structure and joint effort limit constraints, determine if the fingers are able to apply a specified resultant wrench on the object. c) Compute “optimal” contact forces if the answer to problem b) is affirmative. In this paper, based on an early result by Buss et al., which transforms the nonlinear friction cone constraints into positive definiteness constraints imposed on certainy symmetric matrices, we further cast the friction cone constraints into linear matrix inequalities (LMIs) and formulate all three of the problems stated above as a set of convex optimization problems involving LMIs. The latter problems have been extensively studied in optimization and control communities. Currently highly efficient algorithms with polynomial time complexity have been developed and made available. We perform numerical studies to show the simplicity and efficiency of the LMI formulation to the three grasp analysis problems. Index Terms—Convex programming, grasp analysis, force closure, force optimization, friction cones, linear matrix inequalities.

I. INTRODUCTION T HAS been recognized for some time that robotic systems equipped with multifingered hands have great potential for performing useful work in various environments. This recognition is evidenced by the hundreds of research papers (see [1]–[12] and references therein for further details) on grasp analysis, synthesis, control, design, and related topics and the large number of mechanical hands built for both robotic and prosthetic research. Despite the huge effort, many unsolved theoretical and practical problems remain.

Manuscript received December 17, 1998; revised May 15, 2000. This paper was recommended for publication by Associate Editor A. Bicchi and Editor A. De Luca upon evaluation of the reviewers’ comments. This work was supported in part by the National Science Foundation under Grant IRI-9619850, the Texas Advanced Research Program under Grant 999903-078, the Texas Advanced Technology Program under Grant 999903-095, Sandia National Laboratories, and the Research Grants Council of Hong Kong under Grant HKUST6221/99E and Grant CRC98/01.EG02. Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company, for the U.S. Department of Energy under Contract DE-AC04-94AL85000. This paper was presented in part at the 1999 International Conference on Robotics and Automation, Detroit, MI, May 1999. L. Han is with Institute for Complex Engineered Systems, Department of Electrical and Computer Engineering , Carnegie Mellon University, Pittsburgh, PA 15213-3890 USA (e-mail: lihan@cs.cmu.edu). J. C. Trinkle is with Sandia National Laboratory, Albuquerque, NM 87185-1004 USA (e-mail: jctrink@sandia.gov), on leave from the Department of Computer Science, Texas A&M University, College Station, TX 77843 USA. Z. X. Li is with Department of Electrical and Electronic Engineering, HongKong University of Science and Technology, Clear Water Bay, Kowloon, HongKong (e-mail: eezxli@ee.ust.hk). Publisher Item Identifier S 1042-296X(00)11650-7.

I

Of the remaining problems, the three of interest in this paper are the force closure problem, the force feasibility problem, and the force optimization problem, which have mainly been solved (with a handful exception discussed below) after conservatively linearizing the contact friction models. Our main objective here is to develop efficient solution techniques for these fundamental nonlinear problems in a unified mathematical framework developed through the theories of linear matrix inequalities (LMIs) and convex programming. Informally, these problems can be stated as follows. 1) Force Closure Problem—Given the locations of the contact points on the object and the hand, the corresponding friction models, and the kinematic structure of the hand, can be balanced.1 determine if every object load in 2) Force Feasibility Problem—Given the locations of the contact points on the object and the hand, the corresponding friction models, the kinematic structure of the hand, the actuator limits, and known external load on the object and hand, determine if the load can be balanced. 3) Force Optimization Problem—Given a grasp force problem that has passed the feasibility test in item 2 above, determine the “optimal” actuator efforts and corresponding contact forces. These three problems will collectively be referred to as grasp analysis problems. One may note that these problems also arise in the study of foot-step planning and force distribution by multilegged robots [14]. Other applications of these problems can be found in fixturing, cell manipulation by multiple laser probes, and the control of satellites with multiple unidirectional thrusters. As for grasp synthesis problems which address how to generate grasps of certain desired properties, several approaches based on grasp force properties such as force closure and optimal forces have been proposed. Therefore, the solution techniques to grasp analysis problems discussed in this paper can also be applied to grasp synthesis and other relevant applications. A. Related Previous Work The major difficulty associated with the three grasp analysis problems has been the nonlinearity of the commonly accepted contact friction models: point contact with friction (PCWF) and soft-finger contact (SFC). The quadratic nature of both models has been experimentally verified [2], [5] for some common materials. For the force closure problem, there exist theorems [15], [8], [7] for general grasps, which consist of arbitrary numbers and types of contact points. Due to the difficulty

1There exist other definitions of force closure, e.g., the one without taking the hand structure into account [7], which was adopted in our earlier publication [13] and handled similarly as the one in this paper.

1042–296X/00$10.00 ? 2000 IEEE

664

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 16, NO. 6, DECEMBER 2000

of handling the nonlinear models, the force closure theorems [8], [11], have been specialized for the grasps characterized by the number of contact points and the associated contact models and expressed in geometric terms such as antipodal positions. Even with these specialized theorems, the analysis and synthesis of frictional force closure grasps has mainly been studied by linearizing the friction cone constraints and then applying linear programming techniques. Similar approaches [14], [3], [4] have also prevailed in the study of grasp force feasibility and optimization problems. While simplifying the three grasp analysis problems, the linearized model and linear programming approach have the following disadvantages. 1) The friction cone must be approximated conservatively, to avoid the possibility of finding solutions that satisfy the linearized model, but violate the nonlinear model (false positive). Unfortunately, a conservative linearization, may cause the linear analysis to yield false negative results, (e.g., the linear model implies no force closure, when it exists). 2) The orientations of the tangent plane directions in the contact frame affect the results of grasp analysis, which violates the usual assumption of isotropic Coulomb friction. 3) Small perturbations in the parameters describing the grasp (geometry, physics, and kinematics) can produce large variations in the solutions of the linear programs. The nonsmoothness of solutions of linear programming methods [16] poses difficulty for optimization-based grasp synthesis and real-time control applications. (4) Increasing the number of facets in the linearized friction models will increase the running time unacceptably for real-time applications. The problems just discussed, can be alleviated to a large extent by retaining the nonlinear nature of the friction models. Despite the discouraging fact that our current computing resources only allow off-line computation for most nonlinear analyses, this approach has been pursued persistently inside and outside the robotics community. To name a few here, Nakamura et al. [17] developed a nonlinear formulation of the grasp force optimization problem. Bicchi [1] formulated the force closure test as a nonlinear differential equation. Lobo et al. [18] briefly discussed the grasp force feasibility and optimization problems as an engineering application of second order cone programming. Haidacher et al.included a two-stage quadratically-constrained quadratic programming formulation for force closure in [19]. One major progress in the study of grasp force optimization was made by Buss, Hashimoto, and Moore (BHM) [20]. They made the important observation that the nonlinear friction cone constraints are equivalent to the positive definiteness of certain symmetric matrices. This observation enabled them to formulate the grasp force optimization problem on the Riemannian manifold of linearly constrained symmetric positive definite matrices and to develop efficient projected gradient flow algorithms [20]–[23] fast enough for real-time applications. However, to start their optimization algorithms, a valid initial grasp force, which satisfied the friction cone constraints and generated the specified object wrench, was needed, and there was no discussion on how to compute valid initial forces for general grasps. Therefore, the force feasibility and force closure problems remained open.

B. Our Results In this paper, based on the BHM observation and a detailed analysis of the structure of the symmetric positive definite matrices arising from the friction cone constraints, we cast the friction cone constraints into LMIs and formulate the basic grasp analysis problems as a set of convex optimization problems involving LMIs [24]. The latter problems have been extensively studied in optimization and control communities. Recently the efficient algorithms with polynomial time complexity [25], [24] have been developed and made available. We used these algorithms to perform numerical studies that showed the simplicity and efficiency of the LMI formulation to the three grasp analysis problems. II. PROBLEM REVIEW Consider an object grasped by a multifingered robotic hand with contacts between the object and the links of the fingers , transforms applied and the palm. The grasp map, finger forces expressed in local contact frames to resultant object wrenches (1) is the contact wrench of where is the independent wrench intensity the grasp, and vector of finger .2 In order for the grasp to be maintained, the resultant generalized contact force must balance the external (possibly dynamic) load experienced by the object. Thus we have (2) Since the contacts are unilateral, the wrench vector must adhere to a generalized contact friction constraint (3) defines the set of contact wrenches under the contact where model and friction law applicable at contact . For our purposes, this set will be assumed to take the following general form:3 (4) , which will also be denoted as in this paper, is the where normal component of the contact force at contact and denotes a weighted quadratic norm of the frictional components at contact . For the four common contact types, frictionless point contact (FPC), point contact with friction (PCWF), soft finger contact with elliptic approximation (SFCE), and soft finger contact with linearized elliptic approximation (SFCL) [2], the weighted norms are defined respectively as follows: (5) (6)

2The number is respectively, one, three, and four for frictionless point contacts, frictional point contacts, and for soft finger contacts which can transmit a component of moment about the contact normal. 3The condition 0 is included to explicitly show the unilateral property of friction cones, even though it is implied by the condition .

m

x

kx k x

HAN et al.: GRASP ANALYSIS AS LINEAR MATRIX INEQUALITY PROBLEMS

665

(7) (8)

constraints , a joint external load , and a generalized on the object, find an optimal contact resultant wrench wrench vector satisfying (2), (3), (10), and (12). III. FORMULATING GRASP FORCE CONSTRAINTS AS LMIS

and are friction force components in two orthogwhere is the friction onal directions in the contact tangent plane, is the moment component in the contact normal direction, and are (difusual coefficient of Coulomb friction, and ferent) torsion friction limits. A relationship analogous to (2) must be satisfied by the hand on the robot joints must subsystem. The external load be balanced by the contact wrench and the actuator efforts (9) is the transpose of the hand Jacobian. Note that the where may include Coriolis, centripetal, and inertial loads. term , when The null space of the Jacobian transpose, it exists, corresponds to the structurally dependent forces [7], which cannot be generated by robot actuators and cannot be determined for certain types of grasps without more information about the elastic properties of the mechanism [26]. In general, the admissible grasp forces [27], [1] have to be in the range when the despace of , or flection and the grasp stiffness, denoted by matrix , are taken into account. For simplicity, let be a matrix whose columns form a basis for the space of admissible grasp forces, and thus, the latter can be described as (10) The analog to the friction constraints (3) are joint effort constraints. Assume that the joint effort vector is limited by upper and and lower bound vectors

According to BHM [20], the friction cone constraints (3) imposed by the set of contacts can be written as a positive semidefinite constraint on a block diagonal matrix

(13) where denotes positive semidefiniteness. for contact takes one of the following The submatrix forms dictated by its contact type: (14) (15)

(16)

(17) , and . The correctness of this observation can be proved by the pos[20] and itive semidefiniteness of the symmetric matrices the following proposition which will also be used in this paper. Proposition 1: A block diagonal matrix is symmetric (semi) positive , is symmetric definite if and only if each block (semi) positive definite. matrices are Notice that for all the friction models, the linear and symmetric in the unknown components of the contact wrench. This fact allows us to write the friction constraints as nonstrict LMIs which have the following general form: where

(11) The corresponding constraints are written as on the contact wrench vector

(12) Equations (2), (3), (9), (10), and (11) comprise the system model for our subsequent analysis of the grasp problems discussed above. Their simultaneous satisfaction implies that a grasp is valid (i.e., will be maintained). With the model completed, the three fundamental grasp analysis problems can be formalized as follows. Problem 1: Force Closure Problem: Given a grasp and admissible contact force constraints , determine if force . closure exists, i.e., Problem 2: Force Feasibility Problem: Given a grasp , admissible contact force constraints , joint effort , and a generalized constraints , a joint external load on the object, determine if there exists a resultant wrench contact wrench vector satisfying (2), (3), (10), and (12). Problem 3: Force Optimization Problem: Given a grasp , admissible contact force constraints , joint effort

(18) serve as where the real symmetric matrices being zero for the friction the coefficients of the LMI, with cone LMIs. , the symmetric matrix of dimenDenoting by equal to 1 and all other elements zero, sion with element

666

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 16, NO. 6, DECEMBER 2000

the coefficient matrices of the matrix can be written conveniently. For example, if contact is of type SFCE, then the matrices are given as follows:

second-order cone constraint can be cast into a linear matrix inequality:

(22) (19) The coefficient matrices for other friction models have similarly simple forms. on the main diagonal, Since is block diagonal with the it can be written as an LMI (20) is simplified to where the double-indexed and , with the being symmetric. Replacing in (20) by would yield a strict LMI and would restrict the contact forces to lie in the interiors of their respective friction cones, . denoted by One key property of LMIs is that both nonstrict LMIs and strict LMIs are convex constraints on as indicated in the following proposition. , where Proposition 2: Given . The sets and are convex. In general, LMIs can be viewed as an extension of linear inequality constraints where the componentwise inequalities between vectors are replaced by matrix inequalities. It is shown in [24] that LMIs can represent a wide class of convex constrains on such as linear inequalities, (convex) quadratic inequalities or matrix norm inequalities. Consider, for instance, a secondorder cone constraint [18] (which is also called a quadratic, ice-cream, or Lorenz cone constraint) (21) , the problem where the constraint variable is the vector , and . parameters are The vector norm appearing in the constraint is the standard Eu. It is shown [18] that a clidean norm, i.e., where is the identity matrix with dimension . Note that the friction cone constraints (6), (7), (8) can all be transformed into second order cone constraints whose BHM observation (15), (16), (17) can be derived from transformation (22). Next take as another example a linear inequality constraint (23) where and . Since a vector (componentwise) if and only if the matrix (the diagonal matrix with the components of on its diagonal) is positive semidefinite, the linear inequality constraint (23) can , i.e., be cast into a nonstrict LMI with (24) As a direct application of this example, partition the joint effort constraints defined in (12) into two linear inequality constraints (25) and formulate the corresponding LMIs

Therefore, the joint effort constraints (12) can also be cast into one LMI constraint, shown in (26) at the bottom of the page, . where Utilizing proposition 1, we obtain the LMI which incorporates both friction cone and joint effort limit constraints, shown in (27) at the bottom of the page, where .

(26)

(27)

HAN et al.: GRASP ANALYSIS AS LINEAR MATRIX INEQUALITY PROBLEMS

667

In closing this section, we first note that our model for grasp analysis using LMIs is defined by (20) and (26). Second, we stress that the representational breadth of LMIs is greater than what was required by our formulation. So the LMI approach is not restricted to the friction models used in this paper. As long as the friction cone models and other system constraints can be cast into LMIs, the grasp analysis problems can be formulated in the same vein as those discussed in the next section, and thus, can be readily solved by the efficient LMI algorithms.

Substituting (28) into the LMI , we obtain an equivalent LMI in terms of for admissible strictly-internal forces (29) is indeed an LMI since LMI structure is preserved under affine transformations as indicated in the following proposition. , where Proposition 3: Given . Let , where , is the new variable. Then and has the LMI structure, i.e., , and . In summary, the force closure problem is solved by first and, if it is onto, then determining if checking the rank of such that (29) holds. The latter problem there exists a is a standard LMI feasibility problem [24]. Remark 1: If the conventional quadratic representation of the friction cones (5), (6), (7), (8) is used instead of their LMI formulations (14), (15), (16), (17), the internal force existence problem can be cast into a second-order cone feasibility problem utilizing same process described in this section. B. Force Feasibility Problem The grasp force feasibility problem is very similar to the internal force existence problem and can be solved using a similar approach: First, determine if there exists a solution for the linear equation (30) need not satisfy the grasp force constraints. Here, Thus, a simple choice is the least-square solution (31) is the generalized inverse of . The solution is where Range . Otherwise, the answer to the grasp exact if force feasibility problem is negative. For the case that , the general admissible force satisfying (30), if exists, has the form (32) helps to bring to be an where alone might not lie in admissible force satisfying (30), since . The columns of form a basis of the admissible subspace of the null space of . Thus, the answer to the grasp force feasibility problem is af, there exist firmative if and only if satisfying (32) and holding the LMI (33)

IV. GRASP FORCE ANALYSIS PROBLEMS Based on the LMI formulation of grasp force constraints, we now restate the grasp analysis problems as follows. Problem 1: Force Closure Problem and admissible contact force conGiven a grasp , such that straints , determine if for every and . Problem 2: Force Feasibility Problem , admissible contact force constraints Given a grasp , joint effort constraints , a joint external load , and an , determine if , such that object wrench and . Problem 3: Force Optimization Problem , admissible contact force constraints Given a grasp , joint effort constraints , a joint external load , and an , find an “optimal” grasp force object wrench satisfying and . In this section, we will analyze these problems and transform them into standard convex optimization problems involving LMIs, which can be efficiently solved in polynomial time using recently developed interior-point methods [25], [24]. A. Force Closure Problem It was shown that a grasp has force closure if and only if the grasp map has full row rank and there exists an admissible strictly-internal grasp force [7]. In other words, the following two conditions are simultaneously satisfied: ; 1) s.t. and . 2) While verification of the first condition is straightforward, the second condition is difficult due to the nonlinear friction needs to lie constraints. To resolve this problem, note that in the intersection of the null space of and the range space of . If such an intersection is empty, then the answer to the force closure problem is negative. Otherwise, concatenate a set of the basis vectors of the admissible subspace of the null space , where is as column vectors to form a matrix the dimension of the admissible subspace. Then an admissible internal force can be written as

(28) where is the free variable.

Again, the last problem is an LMI feasibility problem and can also be cast as a second-order cone feasibility problem as noted in Remark 1.

668

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 16, NO. 6, DECEMBER 2000

One important property on the force feasibility problem that can be derived from the convexity of the problem is: , admissible contact Proposition 4: Given a grasp force constraints , joint effort constraints , a joint external , if every object wrench in set load is feasible, then every object wrench in the convex hull of set is feasible. A similar result for frictionless contacts was proved in paper [28]. C. Force Optimization Problem , admissible contact force constraints Given a grasp , joint effort constraints , a joint external load , and an object wrench , the grasp force optimization problem amounts to finding an optimal grasp force in the feasible set (34) Here, we only consider the nontrivial case when the feasible set is nonempty. This is true if and only if the answer to the corresponding force feasibility problem is affirmative. In this case, there exists a nonempty feasible set for (35) is defined in (33). where and are convex, we would like to Noting that both to take advantage of define a convex objective function the properties of convex optimization4 and formulate the force optimization problem as (36) Substituting (32) into the objective function yields

the overall squeezing force on the object. With the linear objective function (38), the grasp force optimization problem can be cast with respect to as follows. Optimization Problem 1: Minimizing the summation of normal force components (SDP) minimize subject to

(39)

is a constant and can be where omitted from the objective function. Optimization Problem 1 is in the standard form of semidefinite programming (SDP) [31], [13]. If we use the conventional nonlinear expression of the friction cones (5), (6), (7), (8) instead of their LMI formulations (14), (15), (16), (17), then the grasp force optimization problem as defined below becomes a second-order cone programming (SOCP) problem [18], [13]. Optimization Problem 2: Minimizing the summation of normal force components (SOCP) minimize subject to (2), (3), (10), and (12).

(40)

Both semidefinite programming and second-order cone programming problems can be solved efficiently [25], [31], [18]. However, one potential problem with these formulations is that the linear objective function (38), while minimizing the total normal pressure on the object, may push the contact forces toward their friction cone boundaries. Grasping with such contact forces is not robust to the uncertainty of friction coefficients and may cause the slippage between the object and the fingers. One strategy to overcome this drawback is to add a term that will confine contact forces to the interior of their friction cones. In be defined as particular, let (41) where the vector is the same as in function (38) and is used to weight the normal components of the contact forces . The , tends to infinity as any contact second term, force approaches the boundary of its friction cone and thus yields optimal grasp forces interior to their friction cones. It is convex and can be proven that the function self-concordant [25], two properties essential for the design of polynomial time algorithms and making it a self-concordant barrier for the set of the symmetric positive definite matrices. , where Proposition 5: The function , is convex and self-concordant on the set of symmetric positive definite matrices. Proof: See Appendix A. Proposition 6: The function is strictly convex on the set . Proof: See Appendix A. This objective function (41) is very similar to the self-concordant one proposed in [23]. The weight vector balances the minimal normal (squeezing) forces (linear term) and friction cone boundary (slippage avoidance) conditions (logarithmic term). Larger will generally lead to smaller squeezing forces while smaller will push the contact forces away from their

Then the problem (36) can be transformed into a problem of (37) The latter problem is also a convex optimization problem since the convexity of a function is preserved under affine transformation [30]. Recall that an affine function is convex. Therefore, we can define (38) is used to where the vector weight the normal components of the grasp force , for a fric, for a PCWF contact tionless contact and for a SFC contact . In other words, this objective function minimizes the summation of the normal force components. The smaller the objective value, the lighter

4A convex function reaches its global minimum at its local minimum points [29].

HAN et al.: GRASP ANALYSIS AS LINEAR MATRIX INEQUALITY PROBLEMS

669

friction cone boundaries. The grasp force optimization problem under the self-concordant objective function as given below is in the form of a determinant maximization (maxdet) problem with LMI constraints [32]. Optimization Problem 3: Force optimization as a maxdet problem (maxdet1) minimize subject to (42) While the above maxdet problem can generate grasp forces robust to friction cone constraints, it does not prevent grasp forces from moving to upper or lower joint effort limits, especially for small weights. Small weights put more emphasis on , which may rethe friction cone barrier term sult in forces that are far away from friction cone boundaries but close to the joint effort limits. One way to generate optimal forces that are robust to both friction cone and joint effort conin the logarithmic term of the straints is to use the matrix maxdet objective function. In other words, formulate the force optimization problem as follows. Optimization Problem 4: Force optimization as a maxdet problem (maxdet2) minimize subject to

maximization problems with interior-point convex programming techniques, which need a valid initial grasp force to start the optimization procedure. Our solver of the grasp force feasibility problem, discussed in next section, will provide such an initial force, if the problem is determined to be feasible. Such an initial force can also be used for other optimization procedures, such as the gradient flow algorithm by BHM [20], [23]. D. Transforming LMI Feasibility Problem to Optimization Problem This section shows that an LMI feasibility problem can be transformed to an optimization problem with an easily computable starting point, and thus, can be solved utilizing corresponding optimization algorithms. First notice that for a symmetric matrix s.t. (45)

(43)

The objective function (43) restricts optimal force solution to the interior of the constraint set. It is known [25], [33] that interior solutions to convex optimization programs vary smoothly with changes in the input data. Therefore, the convex Optimization Problem 4 would lead to smooth optimal force solutions. Remark 2: There are many other ways to define convex objective functions for the force optimization problem, which can be formulated as semidefinite programming, second-order cone programming or determinant maximization problems. For example, define an objective function as , i.e., the maximum contact wrench magnitude among all contact wrenches of a grasp. Then the minimization problem for this objective function can be formulated as follows: minimize subject to (2), (3), (10), and (12) where (44)

is the identity matrix with same dimension as where . This is true since (a) is true if and only if , where is the minimal eigenvalue of . (b) Under the constraint if and only if , i.e., is positive semidefinite. (A matrix is positive semidefinite if and only if all of its eigenvalues are nonnegative.) , can be Therefore, an LMI feasibility problem, formulated as a semidefinite programming problem. Optimization Problem 5: The SDP problem equivalent to the LMI feasibility problem minimize subject to The LMI is feasible if and only if the optimal value . Second-order feasibility problem can be transformed to second order cone programming problem in a similar manner. Notice that a valid initial point for Optimization Problem 5 , where is the minimal is . Therefore, we can use this initial point to eigenvalue of start any interior-point semidefinite program algorithms to solve Optimization Problem 5. Also notice that the SDP Problem 5 can be transformed to an equivalent maxdet problem by choosing the logarithmic term , i.e., minimize subject to

is a slack variable. Since the newly-added constraint is also a second order cone constraint, the problem above can be cast into SOCP and SDP problems as discussed in this section. Remark 3: This paper formulates the force optimization problem in terms of contact forces . It should be noted that the force optimization problem can be similarly formulated and solved with respect to joint efforts or both joint efforts and grasp forces to obtain various kinds of “optimal grasp forces.” Remark 4: Current algorithms solve the semidefinite programming, second-order cone programming and determinant

(46)

Therefore, a maxdet algorithm can also solve the LMI feasibility problem. Indeed, SDP is a special case of maxdet. Finally notice that the optimal objective value of Optimization Problem 5 is the negative of the maximum minimum eigen. In particular, when the LMI is feasible, value of Optimization Problem 5 is equivalent to maximize subject to (47)

670

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 16, NO. 6, DECEMBER 2000

with the optimal values of the two problems being related by . The minimal eigenvalue of a positive definite matrix can be used as a “robustness” criterion of the matrix since it denotes how far the matrix is to the boundary of the set of the positive definite matrices [20]. Therefore, the optimal solution from Optimization Problem 5 can be interpreted as the “most robust” solution to the LMI constraint under the max-min definition (47). Optimization Problem 5, when used to solve the grasp force feasibility problem, will yield a grasp force corresponding to forces at each contact point that are farther away from the boundaries of their friction cones and the joint effort limits. It should be noted that the SDP and maxdet formulations of the grasp force optimization problems only need a valid grasp force to start the optimization procedure. So there is no need to finish the Optimization Problem 5. Instead, it can be terminated whenever becomes negative and then use the corresponding as a valid initial force. V. NUMERICAL EXAMPLES In this section, we present the numerical results obtained from applying the maxdet optimization package developed by Wu et al. [34] to grasp force feasibility and optimization problems. The results for the force closure problem are not presented here since the existence problem of an admissible internal force is essentially a force feasibility problem. The figures in the paper are chosen to highlight the convergence of contact forces and the effect of different optimization problem formulations on optimal forces. More numerical results and figures can be found in our technical report [35]. A. MaxDet The ANSI C source code of maxdet was downloaded from http://www.stanford.edu/~boyd/MAXDET.html. We further developed auxiliary C code to compute various problem data (such as grasp maps), formulate LMI constraints, transform an LMI feasibility problem to a maxdet optimization problem, and record the feasibility and optimization data. An executable file was generated by linking the standard Fortran77 math libraries blas and lapack provided on our HP/Convex computer to the object files generated by gcc. Maxdet implements a primal-dual interior-point convex optimization algorithm. Assume that the optimal objective value of . Briefly, maxdet computes a concerned maxdet problem is and a lower bound for the optimal value. an upper bound is called the duality gap [32], [34]. The proThe quality gram uses three parameters, namely, maximum number of iterations allowed, absolute tolerance abstol and relative tolerance reltol, as its termination criteria. More specifically, the program will stop if at least one of the following conditions is satisfied: ? the maximum number of iterations is exceeded; abstol; ? the absolute tolerance is reached: ? the relative tolerance is reached. If both upper and lower reltol , or both bounds are positive and reltol bounds are negative and In our numerical study, the maximum number of iterations allowed was 100, the relative tolerance was 0.005; the absolute

tolerance was set in the way that its corresponding relative tolerance was at most 0.005. Note that relaxing tolerance criteria could reduce the running times. B. Numerical Example Consider a case in which four fingertips grasp a ball of unit radius. In our numerical study, we assumed the following. a) The first two contact points were frictionless. (b) The third contact was a soft finger contact with elliptic approximation (SFCE), with 0.632 tangential friction coefficient and 0.669 torsion friction coefficient. (c) The fourth contact was a point contact with friction (PCWF) with 0.4 tangential friction coefficient. (d) The contact points on the object had spherical coordinates [7] . To simplify the presentation, we will present the numerical results without including a detailed kinematic description of a robotic hand in the problem. In our study, however, we mimicked kinematic effects on the grasping capabilities by assuming partially admissible space of the contact forces. We also assumed that (31) to the force equilibrium the minimal normal solution in our constraint (30) was admissible, and thus, the term admissible force formula (32) was set to zero. Furthermore, we assumed lower and upper bounds for the contact force components as a simplified way to incorporate joint effort constraints. In particular, all contact wrench components were assumed to and 10 as their lower and upper bounds. The task was have to solve the grasp force feasibility and optimization problems . for resultant object wrench C. Numerical Results of the four-finger grasp was rank 6 The grasp map and had a 3-D null space, whose basis vectors were

, and . When the last basis vector of the null space was assumed to be nonadmissible, the problem was determined to be infeasible in 7.81 ms. On the other hand, when the first basis vector was not admissible, the system could generate the desired object wrench. The figures in this section show the feasibility and optimization results for the latter case. The convergence of the contact forces and objective value for the feasibility phase is shown in Fig. 1. Notice the grasp force constraints were violated at the beginning. a) At step 0, reached 10.02, above its upper limit the first contact force 10.0. b) Again at step 0, the weighted tangential force at the , was larger than the normal force comfourth contact point, , violating the friction cone constraints. c) At steps ponent one through four, the normal force component of the fourth was greater than its upper limit 10.0. By the end contact of the feasibility phase, all contact wrenches satisfied friction cone constraints and torque limit constraints, which were also satisfied through the whole optimization procedure (Figs. 2–5). One point to notice here is that the feasibility condition became satisfied at step 5 (the objective value became negative), while the feasibility phase continued up to step 15. This is because maxdet implements a two-loop optimization algorithm and only

HAN et al.: GRASP ANALYSIS AS LINEAR MATRIX INEQUALITY PROBLEMS

671

Fig. 3. Force optimization phase for problem maxdet1 (d = 0:6).

Fig. 1. Force feasibility phase.

Fig. 4.

Force optimization phase for problem maxdet1 (d = 0:01).

Fig. 2. Force optimization phase for problem maxdet1 (d = 10:0).

the outer loop checks the objective value and may terminate the algorithm if at least one termination criteria is satisfied. It would be easy to let the inner loop check the objective value, which would add more computation to each step but could reduce the total time needed for the feasibility phase by reduced number of steps. Figs. 2–4 are the results of three different runs of force Optibeing set to mization Problem 3 (maxdet1) with the weights 10, 0.6 and 0.01, respectively. Recall that larger weights favor smaller normal forces, while smaller weights favor forces that are far away from the friction cone boundaries. The effect of different weights were clearly reflected in Figs. 2–4. The normal forces were smallest when the weight was 10.0 (Fig. 2), and they were the closest to the friction cone boundary. (Notice that the almost coincides with that of .) On curve of

Fig. 5.

Force optimization phase for problem maxdet2 (d = 0:01).

the other hand, the optimal forces for weight 0.01 (Fig. 4) were furtherest from the friction cone boundaries (the largest gap beand , among three different weights), tween but were closest to the upper limits of the (simulated) joint effort constraints. The weight 0.6 puts approximately equal importance on the linear term and the self-concordant term in the maxdet objective function. Fig. 3 shows that its corresponding optimization results were found to lie between those for larger weight 10 and smaller weight 0.01. Fig. 5 shows the optimization results under problem formulation 4 (maxdet2), i.e., with the actuator limits being included in being 0.01. the logarithmic barrier term, and with weights

672

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 16, NO. 6, DECEMBER 2000

Notice that the normal forces were not as close to their upper bounds 10.0 as those in Fig. 4. This was expected since the objective function (43) for Optimization Problem 4 would move to infinity as any force moves to its friction or effort boundaries and thus prohibit any force to be close to its upper or lower limits. Figs. 1 –5 observed larger contact force adjustment at some iteration steps (e.g., step 5 in Fig. 1) than at others, which happened at the start of new outer loop optimization and appeared to be caused by the two-loop optimization procedure. This kind of behavior, which is also typical for many other optimization algorithms, is not expected to cause much difficulty in manipulation experiments since not all intermediate forces computed within an optimization procedure need to be sent to the robotic systems especially when the optimal forces can be generated fast, which is the case of the maxdet algorithm. Instead, the continuity of optimal force trajectories during a manipulation task is important for a stable implementation of the task, and our next numerical example shows the maxdet performance on this regard. For the ball-in-hand system discussed above, we simulated a manipulation task where contact points moved as the ball rotated 180 relative to its -axis. The incremental change values of the contact and object configurations were taken to be (0.000 396, 0.000 840, 0.000 353, 0.000 447, 0.000 319, 0.000 886, 0.000 016, 0.000 584) and 1.8 . Fig. 6 highlights the smoothness of the solution trajectories during this simulated manipulation. Also, we observed that the tangential friction force directions varied by 129.04 for contact 3 and 305.47 for contact 4. If we were to produce the solution trajectories using linearized friction cones and an LP-based grasp analysis, we would expect the friction force directions to contain jump discontinuities. In other words, a friction direction would point toward a particular facet in the linearized friction cone until the external force changed enough to cause it to jump to a neighboring facet. This behavior is inherent in linearized approaches, but is avoided by our LMI formulation. For the results presented in Figs. 1 –5, maxdet took at most 7.81 ms to solve the feasibility problem or the optimization problem. The total computation times, including computing the problem data, preparing the LMI constraints, determining the feasibility and optimizing the objectives, ranged from 7.81 to 15.63 ms, which indicated the preprocessing times, including computing problem data and prepare the LMI constraints, were insignificant. The last example took about 0.9453 s for the 100 runs of maxdet. VI. CONCLUSION Grasp analysis is of fundamental importance in robotics, yet despite many years of research effort, efficient solutions to general formulations of some of the basic problems, such as grasp feasibility, have not previously been developed. The major stumbling block has been the nonlinear friction cone constraints imposed by the contact models. In this paper, based on the important observation by BHM, that the nonlinear friction cone constraints are equivalent to the constraint that certain symmetric matrices be positive definite, we have cast the friction cone constraints into linear matrix inequalities (LMIs) and formulated the basic grasp analysis problems as a set of

Fig. 6.

Optimal forces for problem maxdet2 (d = 0:01).

convex optimization problems involving LMIs. The resulting problems can be solved in polynomial time by highly efficient algorithms. Our simulation results showed the simplicity and efficiency of this approach. Convex optimization has found wide applications in various areas such as control and system theory, combinatorial optimization, statistics, computational geometry and pattern recognition. It can efficiently solve problems involving nonlinear and nondifferentible functions, which would be considered to be very difficult in a standard treatment of optimization. Due to

HAN et al.: GRASP ANALYSIS AS LINEAR MATRIX INEQUALITY PROBLEMS

673

its natural application to grasp analysis problems, it appears that convex optimization will play an increasingly active role in solving complicated mathematical and engineering problems in robotics. APPENDIX A PROOFS OF PROPOSITIONS This appendix only proves relatively difficult propositions, namely Propositions 5 and 6. Refer to [36] for proofs of all propositions. Definition of Self-Concordant Barrier: Assume is a closed convex subset in . A function defined over is a self-concordant barrier for if the following two properties are satisfied: constant constant (48)

The proof of self-concordance utilizes the similar strategy as above but involves more computation, and is omitted here. More details can be found in book [25]. Proof of Proposition 6: Since is convex, we know , and is still . Also note that in

Therefore

(by Proposition 5)

denote the first, second, and where third order Frechet derivatives of the function at a point in , and is a tangent vector at to the interior of . Proof of Proposition 5: Denote the set of symmetric matrices and the set of symmetric positive semidefinite matrices of and , respectively dimension by

ACKNOWLEDGMENT The authors would like to thank M. Buss and T. Schlegl of Technical University of Munich for the motivating discussions and generous offer of their grasp force optimization code for regrasping [22]. The authors are also grateful to A. Bicchi of University of Pisa for pointing out the importance of kinematicstructure-imposed force constraints, as well as S. Boyd and C. Crusius of Stanford University, S. Jiang of The Hong Kong University of Science and Technology for helpful discussions, and anonymous reviewers for helpful comments. REFERENCES

[1] A. Bicchi, “On the closure properties of robotic grasping,” International Journal of Robotics Research, vol. 14, no. 4, pp. 319–334, 1995. [2] R. Howe, I. Kao, and M. Cutkosky, “The sliding of robot fingers under combined torsion and shear loading,” presented at the Proc. IEEE Int. Conf. on Robotics and Automation, 1988. [3] J. Kerr and B. Roth, “Analysis of multifingered hands,” International Journal of Robotics Research, vol. 4, no. 4, pp. 3–17, 1986. [4] Y. H. Liu, “Qualitative test and force optimization of 3d frictional form-closure grasps using linear programming,” IEEE Transactions on Robotics and Automation, vol. 15, no. 1, pp. 163–173, 1999. [5] M. Mason and K. Salisbury, Robot Hands and the Mechanics of Manipulation. Cambridge, MA: MIT Press, 1985. [6] B. Mishra, J. T. Schwartz, and M. Sharir, “On the existence and synthesis of multifinger positive grips,” Algorithmica, vol. 2, no. 6, pp. 541–558, 1987. [7] R. Murray, Z. X. Li, and S. Sastry, A Mathematical Introduction to Robotic Manipulation. Boca Raton, FL: CRC Press, 1994. [8] V.-D. Nguyen, “Constructing force-closure grasps,” International Journal of Robotics Research, vol. 7, no. 3, pp. 3–16, 1988. [9] J. S. Pang and J. C. Trinkle, “Complementarity formulations and existence of solutions of dynamic multi-rigid-body contact problems with coulomb friction,” Methematical Programming, vol. 73, no. 2, pp. 199–226, 1996. [10] J. S. Pang, J. C. Trinkle, and G. Lo, “A complementarity approach to a quasistatic rigid body motion problem,” Journal of Computational Optimization and Applications, vol. 5, no. 2, pp. 139–154, 1996. [11] J. Ponce, S. Sullivan, A. Sudsang, J.-D. Boissonnat, and J.-P. Merlet, “On computing four-finger equilibrium and force-closure grasps of polyhedral objects,” International Journal of Robotics Research, vol. 16, no. 1, pp. 11–35, 1997. [12] E. Rimon and J. Burdick, “On force and form closure for multiple finger grasps,” presented at the Proc. IEEE Int. Conf. on Robotics and Automation, 1996.

Note that mension at point

and , is

are smooth manifolds [37] of di, and , the tangent space to . Define a function

We need to prove that the function is a strictly convex and . self-concordant barrier on the set Proof: Denote the first, second, and third order Frechet and derivatives of the function at a point as . , it can be computed that

where denotes trace. To show that is strictly convex, we only need to prove that is strictly positive definite, or equivalently, the Hessian of . This is true since

and the equality holds if and only if

.

674

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 16, NO. 6, DECEMBER 2000

[13] L. Han, J. C. Trinkle, and Z. X. Li, “Grasp analysis as linear matrix inequality problems,” in Proc. IEEE Int. Conf. on Robotics and Automation, 1999, pp. 1261–1268. [14] F. T. Cheng and D. E. Orin, “Efficient algorithm for optimal force distribution—The compact-dual LP method,” IEEE Transactions on Robotics and Automation, vol. 6, no. 2, pp. 178–187, 1990. [15] J. K. Salisbury and B. Roth, “Kinematic and force analysis of articulated hands,” ASME Journal of Mechanisms, Transmissions, and Automation in Design, vol. 104, no. 1, pp. 33–41, 1982. [16] C. A. Klein and S. Kittivatcharapong, “Optimal force distribution for the legs of a walking machine with friction cone constraints,” IEEE Transactions on Robotics and Automation, vol. 6, no. 1, pp. 73–85, 1990. [17] Y. Nakamura, K. Nagai, and T. Yoshikawa, “Dynamics and stability in coordination of multiple robotic mechanisms,” International Journal of Robotics Research, vol. 8, no. 2, pp. 44–61, 1989. [18] M. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret, “Applications of second-order cone programming,” Linear Algebra and Its Applications, Special Issue on Linear Algebra in Control, Signals and Image Processing, vol. 284, pp. 193–228, Nov. 1998. [19] S. Haidacher, T. Schlegl, and M. Buss, “Grasp evaluation based on unilateral force closure,” presented at the Proc. IEEE-RSJ Int. Conf. on Intelligent Robots and Systems, 1999. [20] M. Buss, H. Hashimoto, and J. Moore, “Dextrous hand grasping force optimization,” IEEE Transactions on Robotics and Automation, vol. 12, no. 3, pp. 406–418, 1996. [21] M. Buss and K. Kleinmann, “Multifingered grasping experiments using real-time grasping force optimization,” in Proc. IEEE Int. Conf. on Robotics and Automation, 1996, pp. 1807–1812. [22] M. Buss and T. Schlegl, “Multi-fingered regrasping using on-line grasping force optimization,” presented at the Proc. IEEE Int. Conf. on Robotics and Automation, 1997. [23] M. Buss, L. Faybusovich, and J. Moore, “Dikin-type algorithms for dextrous grasping force optimization,” International Journal of Robotics Research, vol. 17, no. 8, pp. 831–839, 1998. [24] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory. Philadelphia, PA: SIAM, 1994. [25] Y. Nesterov and A. Nemirovsky, Interior-Point Polynomial Methods in Convex Programming. Philadelphia, PA: SIAM, 1994. [26] D. Prattichizzo and A. Bicchi, “Dynamic analysis of mobility and graspability of general manipulation systems,” IEEE Transactions on Robotics and Automation, vol. 14, no. 2, pp. 241–257, Jan. 1998. [27] J. Kerr, “An Analysis of Multifingered Hand,” Ph.D. Thesis, Department of Mechanical Engineering, Stanford University, Stanford, CA, 1985. [28] J. D. Wolter and J. C. Trinkle, “Automatic selection of fixture points for frictionless assemblies,” in Proc. IEEE Int. Conf. on Robotics and Automation, 1994, pp. 528–534. [29] R. T. Rockafellar, “Lagrange multipliers and optimality,” SIAM Review, vol. 35, pp. 183–283, 1993. , Convex Analysis. Princeton, NJ: Princeton Univ. Press, 1970. [30] [31] L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM Review, vol. 38, no. 1, pp. 49–95, 1996. [32] L. Vandenberghe, S. Boyd, and S.-P. Wu, “Determinant maximization with linear matrix inequality constraints,” SIAM Journal on Matrix Analysis and Applications, vol. 19, no. 2, pp. 499–533, 1998. [33] S. Boyd and L. Vandenberghe. (1999) Introduction to Convex Optimization with Engineering Applications. Lecture Notes, Inform. Syst. Lab., Stanford Univ., Stanford, CA. [Online]. Available: http://www.stanford.edu/class/ee364

[34] S.-P. Wu, L. Vandenberghe, and S. Boyd, Maxdet: Software for Determinant Maximization Problems. User’s Guide, Alpha Version, Stanford University, Stanford, CA, Apr. 1996. [35] L. Han, J. C. Trinkle, and Z. X. Li, “Grasp Analysis as Linear Matrix Inequality Problems,” Texas A&M University, College Station, TX, Tech. Rep. CS-1998-020, 1998. [36] L. Han, “The Planning and Control of Robot Dextrous Manipulation,” Ph.D. Thesis, Dept. of Computer Science, Texas A&M University, 2000. [37] W. Boothby, An Introduction to Differentiable Manifolds and Riemannian Geometry. New York, NY: Academic Press, 1975.

Li Han received the B.S. and M.S. degrees in biomedical engineering from Xian Jiaotong University, Xian, China, in 1989 and 1992, respectively, and the Ph.D. degree in computer science from Texas A&M University, College Station, TX, in 2000. She is currently a Postdoctoral Fellow at Carnegie Mellon University. Her research interests include robotics, computer simulation, computational biology, and distributed and parallel computing.

Jeff C. Trinkle received his bachelor’s degrees in physics (1979) and engineering science and mechanics (1979) from Ursinus College and Georgia Institute of Technology, respectively. He was a member of the Fiber Composites Group at Lawrence Livermore National Laboratory for two and one half years before returning to graduate school in 1982. In 1987, he received his Ph.D. from the Department of Systems Engineering at the University of Pennsylvania. Since 1987, he has held faculty positions in the Department of Systems and Industrial Engineering at the University of Arizona, and the Department of Computer Science at Texas A&M University. He is currently a Principal Member of Technical Staff in the Intelligent Systems and Robotics Center at Sandia National Laboratories in Albuquerque, NM. Trinkle’s primary research interests lie in the areas of robotic manipulation planning, multibody dynamics, and automated fixturing.

Zexiang X. Li (M’89) received the B.S. degree in electrical engineering and economics (with honors) from Carnegie Mellon University, Pittsburgh, PA, in 1983, and the M.A. degree in mathematics and the Ph.D. degree in electrical engineering and computer science, both from the University of California at Berkeley, in 1985 and 1989, respectively. He is an Associate Professor with the Department of Electrical and Electronic Engineering, Hong Kong University of Science and Technology. His research interests include robotics, nonlinear system theory, and manufacturing.

更多相关文档:

A *Linear* *Matrix* *Inequality* Approach to Output_数学_自然科学_专业资料。Pitcha...D., 2004, “Detailed Error *Analysis* for a Fractional Adams Method,” ...

【国家自然科学基金】_*linear* *matrix* *inequality*_期刊发文

Peak-to-Peak Gain Minimization for Uncertain *Linear* Discrete Systems: A *Matrix* *Inequality* Appr_专业资料。维普资讯 http://www.cqvip.com Bre prifPae ACTA ...

On stabilization for a class of nonlinear stochastic time-delay systems: a *matrix* *inequality*_专业资料。维普资讯 http://www.cqvip.com JunlfCnrlhoyn plain...

One can obtain the *matrix* A and vector b from...*Analyze* the running time of your algorithm. 解:...to solve the *linear*-*inequality* feasibility *problem*....

In many special cases the *problem* of determining ...Katz. On a *matrix* *inequality*. *Linear* Algebra ...Topics in *Matrix* *Analysis*. Cambridge University ...

Controller Design via *Linear* *Matrix* *Inequalities*_...(13) *as* a *matrix* *inequality* instead of an ...Sugeno, \Stability *Analysis* and Design of Fuzzy ...

This is because many *analysis* and synthesis *problems* for static output feed... an iterative *linear* *matrix* *inequality* (ILMI) method to solve the *problem*....

Delay dependent exponential stability *analysis*(2002)_专业资料。Delay dependent ...*linear* *matrix* *inequality* is taken to investigate the *problems*, which provide ...

Exponential stability *analysis* of nonlinear systems using LMIs_专业资料。This ... conditions can be formulated *as* a *linear* *matrix* *inequality* (LMI) *problem*....

Fuzzy control; Time-delay; *Linear* *matrix* *inequality* (LMI); Stability 1. ... approach is applied to *analyze* the stability and stabilization *problem*. ...

It is namely shown how a recently published *linear* *matrix* *inequality* ...This approach is well suited to solve stability *analysis* *problems* formulated ...

Stability; Sampled-data system; Feedback control; *Linear* *matrix* *inequality* 1...(2001), the authors considered an *analysis* *problem* for the NCSs under ...

Flouquet Abstract This Letter is concerned with the *analysis* *problem* of ...Time-varying delays; LyapunovKrasovskii functional; *Linear* *matrix* *inequality* ...

更多相关标签:

相关文档

- Li Han y Grasp Analysis as Linear Matrix Inequality Problems
- Linear matrix inequality in Control
- A linear matrix inequality approach to H∞ control
- a linear matrix inequality approach to peak-to-peak gain minimization
- (1994)A LINEAR MATRIX INEQUALITY APPROACH TO Hinfty control
- Linear eigenvalue analysis of the disc-brake squeal problem
- Nonlinear Component Analysis as a Kernel Eigenvalue Problem,Bernhard Scholkopf,1996
- Statistical analysis of array expression data as applied to the problem of tamoxifen resist
- Nonlinear component analysis as a kernel eigenvalue problem

文档资料共享网 nexoncn.com
copyright ©right 2010-2020。

文档资料共享网内容来自网络，如有侵犯请联系客服。email:zhit325@126.com