Global inverse kinematics via mixed-integer convex optimization
Authors:
- 13 May 2019
- journal article
- research article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 38 (12-13) , 1420-1441
Abstract
In this paper, we present a novel formulation of the inverse kinematics (IK) problem with generic constraints as a mixed-integer convex optimization program. The proposed approach can solve the IK problem globally with generic task space constraints: a major improvement over existing approaches, which either solve the problem in only a local neighborhood of the user initial guess through nonlinear non-convex optimization, or address only a limited set of kinematics constraints. Specifically, we propose a mixed-integer convex relaxation of non-convex rotation constraints, and apply this relaxation on the IK problem. Our formulation can detect if an instance of the IK problem is globally infeasible, or produce an approximate solution when it is feasible. We show results on a seven-joint arm grasping objects in a cluttered environment, an 18-degree-of-freedom quadruped standing on stepping stones, and a parallel Stewart platform. Moreover, we show that our approach can find a collision free path for a gripper in a cluttered environment, or certify such a path does not exist. We also compare our approach against the analytical approach for a six-joint manipulator. The open-source code is available at http://drake.mit.edu.
Keywords
This publication has 33 references indexed in Scilit:
- Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxationsMathematical Programming, 2012
- Task Space RegionsThe International Journal of Robotics Research, 2011
- Inverse kinematic analysis of the general 6R serial manipulators based on double quaternionsMechanism and Machine Theory, 2010
- Modeling disjunctive constraints with a logarithmic number of binary variables and constraintsMathematical Programming, 2009
- Kinematics of an offset 3-UPU translational parallel manipulator by the homotopy continuation methodNonlinear Analysis: Real World Applications, 2009
- A new and efficient algorithm for the inverse kinematics of a general serial 6R manipulatorMechanism and Machine Theory, 2007
- Cutting planes in integer and mixed integer programmingDiscrete Applied Mathematics, 2002
- Pose estimation from corresponding point dataIEEE Transactions on Systems, Man, and Cybernetics, 1989
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problemsMathematical Programming, 1976
- A Platform with Six Degrees of FreedomProceedings of the Institution of Mechanical Engineers, 1965