Convex geometric motion planning of multi-body systems on Lie groups via variational integrators and sparse moment relaxation

Abstract

This paper reports a novel result: with proper robot models based on geometric mechanics, one can formulate the kinodynamic motion planning problems for rigid body systems as exact polynomial optimization problems. Due to the nonlinear rigid body dynamics, the motion planning problem for rigid body systems is nonconvex. Existing global optimization-based methods do not parameterize 3D rigid body motion efficiently; thus, they do not scale well to long-horizon planning problems. We use Lie groups as the configuration space and apply the variational integrator to formulate the forced rigid body dynamics as quadratic polynomials. Then, we leverage Lasserre’s hierarchy of moment relaxation to obtain the globally optimal solution via semidefinite programming. By leveraging the sparsity of the motion planning problem, the proposed algorithm has linear complexity with respect to the planning horizon. This paper demonstrates that the proposed method can provide globally optimal solutions or certificates of infeasibility at the second-order relaxation for 3D drone landing using full dynamics and inverse kinematics for serial manipulators. Moreover, we extend the algorithms to multi-body systems via the constrained variational integrators. The testing cases on cart-pole and drone with cable-suspended load suggest that the proposed algorithms can provide rank-one optimal solutions or nontrivial initial guesses. Finally, we propose strategies to speed up the computation, including an alternative formulation using quaternion, which provides empirically tight relaxations for the drone landing problem at the first-order relaxation.