Optimization Online


Fast Computation of Optimal Contact Forces

Stephen Boyd(boyd***at***stanford.edu)
Ben Wegbreit(wegbreit***at***ix.netcom.com)

Abstract: We consider the problem of computing the smallest contact forces, with point-contact friction model, that can hold an object in equilibrium against a known external applied force and torque. It is known that the force optimization problem (FOP) can be formulated as a semidefinite programming problem (SDP), or a second-order cone problem (SOCP), and so can be solved using several standard algorithms for these problem classes. In this paper we describe a custom interior-point algorithm for solving the FOP that exploits the specific structure of the problem, and is much faster than these standard methods. Our method has a complexity that is linear in the number of contact forces, whereas methods based on generic SDP or SOCP algorithms have complexity that is cubic in the number of forces. Our method is also much faster for smaller problems. We derive a compact dual problem for the FOP, which allows us to rapidly compute lower bounds on the minimum contact force, and to certify infeasibility of a FOP. We use this dual problem to terminate our optimization method with a guaranteed accuracy. Finally, we consider the problem of solving a family of FOPs that are related. This occurs, for example, in determining whether force closure occurs, in analyzing the worst-case contact force required over a set of external forces and torques, and in the problem of choosing contact points on an object so as to minimize the required contact force. Using dual bounds, and a warm-start version of our FOP method, we show how such families of FOPs can be solved very efficiently.

Keywords: Robotics, grasp optimization, second-order cone programming, semidefinite programming

Category 1: Applications -- Science and Engineering (Mechanical Engineering )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: To appear in IEEE Trans. Robotics, 2008.

Download: [PDF]

Entry Submitted: 10/01/2007
Entry Accepted: 10/01/2007
Entry Last Modified: 10/01/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society