Time-Optimal Path Parameterization by Reachability Analysis (TOPP-RA)

TOPP-RA repo on Github.

TOPP-RA is the latest theoretical development for solving the Time-Optimal Path Parameterization (TOPP) problem. TOPP-RA achieves 100% success rate while being faster than the state-of-the-art implementation of the classic Bobrow algorithm. The current implementation of TOPP-RA supports the following constraints :

  • joint velocity and acceleration bounds;
  • torque bounds (including redundantly-actuated manipulators);
  • contact stability for legged robots.

Reference

  • A new approach to Time-Optimal Path Parameterization based on Reachability Analysis, IEEE Transactions on Robotics, 2018 [pdf]

Time-Optimal Path Parameterization (TOPP) à la Bobrow

TOPP repo on Github.

We implemented in C++ the classic algorithm to find the time-optimal parameterization of a given path under kinodynamic constraints. Currently, the standalone version supports :

  • pure kinematic (velocity and acceleration) bounds;
  • general quadratic bounds;
  • kinematic and dynamic bounds in SE(3).

The OpenRAVE-enabled version supports moreover :

  • torque bounds;
  • contact stability bounds;
  • torque bounds for redundantly-actuated robots.

References

  • A general, fast, and robust implementation of the time-optimal path parameterization algorithm, IEEE Transactions on Robotics, 2014 [pdf]
  • Time-optimal path parameterization for redundantly-actuated robots: a numerical integration approach, IEEE/ASME Transactions on Mechatronics, 2015 [pdf]
  • Time-optimal path parameterization of rigid-body motions: applications to spacecraft reorientation, Journal of Guidance, Control, and Dynamics, 2016 [pdf]
  • Admissible Velocity Propagation: beyond quasi-static path planning for high-dimensional robots, International Journal of Robotics Research, 2017 [pdf]

Time-Optimal Parabolic Interpolation (Parabint)

Parabint repo on Github.

We implemented, in standalone Python files, the algorithm to find the time-optimal multi-dof parabolic interpolation subject to velocity, acceleration and minimum-switch-time constraints.

Reference

  • Time-optimal parabolic interpolation with velocity, acceleration, and minimum-switch-time constraints, Advanced Robotics, 2016 [pdf]

Converting cone representations [deprecated]

Every Polyhedral Convex Cone (PCC) P has two different representations, the face representation and the positive span representation :

  • P = face{a1,...,am} = {x : a1Tx ≤ 0,...,amTx ≤ 0}
  • P = span{u1,...,uk} = {c1u1 + ... + ckuk : c1 ≥ 0 ... ck ≥ 0}

In his thesis (1991), S. Hirai described an algorithm to convert one representation into the other and gave an implementation in LISP. Here we re-implemented that algorithm in the more modern Python language :

  • PCC.txt (the main algorithm in Python, rename to .py to use)
  • test-PCC.txt (an example of computation that makes use of the conversion, rename to .py to use)