Convex strategies for trajectory optimisation: application to the Polytope Traversal Problem
This work addresses the challenge of reliable trajectory initialization for unstable dynamical systems, such as robotics, though it is incremental as it builds on existing optimization methods.
The paper tackles the problem of generating feasible initial guesses for non-linear trajectory optimization in unstable systems like humanoid robots, proposing a convex optimization method that simultaneously computes a feasible path and time allocation, achieving success rates above 80% in scenarios where quasi-static solutions fail, with computation times under 10ms for up to 5 polytopes and under 1s for 20 polytopes.
Non-linear Trajectory Optimisation (TO) methods require good initial guesses to converge to a locally optimal solution. A feasible guess can often be obtained by allocating a large amount of time for the trajectory to complete. However for unstable dynamical systems such as humanoid robots, this quasi-static assumption does not always hold. We propose a conservative formulation of the TO problem that simultaneously computes a feasible path and its time allocation. The problem is solved as an efficient convex optimisation problem guaranteed to converge to a locally optimal solution. The interest of the approach is illustrated with the computation of feasible trajectories that traverse sequentially a sequence of polytopes. We demonstrate that on instances of the problem where the quasi static solutions are not admissible, our approach is able to find a feasible solution with a success rate above $80 \%$ in all the scenarios considered, in less than 10ms for problems involving traversing less than 5 polytopes and less than 1s for problems involving 20 polytopes, thus demonstrating its ability to reliably provide initial guesses to advanced non linear solvers.