Fast Interpolation and Time-Optimization on Implicit Contact Submanifolds

Kris Hauser, Robotics: Science and Systems, 2013

Abstract. This paper presents a method for generating smooth, efficiently-executable trajectories for robots under contact constraints, such as those encountered in legged locomotion and object manipulation. It consists of two parts. The first is an efficient, robust method for constructing C1 interpolating paths between configuration/velocity states on implicit manifolds. The second is a robust time-scaling method that solves for a minimum-time parameterization using a novel convex programming formulation. Simulation experiments demonstrate that the method is fast, scalable to high-dimensional robots, and numerically stable on humanoid robot locomotion and object manipulation examples.

Download PDF pdf


Manifold Interpolation and Time-Optimal Smoothing (Mintos) library

The Mintos library implements the algorithm in the above paper. It supports 1) generating smooth interpolating paths on implicit manifolds and 2) optimizing time-scaling of such paths under velocity, acceleration, torque, and frictional force bounds. It is lightweight, fast, written in C++, and has only one external dependency (GLPK).


  • Computes a smooth, time optimized interpolating trajectory that lies on the manifold up to the user-defined threshold.
  • Also applicable to time-scaling of free-space Bezier curves.
  • Supports smooth interpolation through multiple configurations.
  • Supports constraint submanifolds in non-Cartesian spaces, e.g. SO(3).
  • Very fast: interpolation and time-optimization typically takes only fractions of a second even with dozens of DOFs.
  • Numerically stable: time scaling achieved via provably convergent convex optimization.
  • Variety of constraints: velocity, acceleration, torque, point contact with Coulomb friction constraints.
  • Distributed under the LGPL license.