Single Leg Dynamic Motion Planning with Mixed-Integer Convex Optimization

Abstract

This paper proposes a mixed-integer convex programming formulation for dynamic motion planning. Many dynamic constraints such as the actuator torque constraint are nonlinear and non-convex due to the trigonometrical terms from the Jacobian matrix. This often causes the optimization problem to converge to local optima or even infeasible set. In this paper, we convexify the torque constraint by formulating a mixed-integer quadratically-constrained program (MIQCP). More specifically, the workspace is discretized into a union of disjoint polytopes and torque constraint is enforced upon a convex outer approximation of the torque ellipsoid, obtained by solving a semidefinite program (SDP). Bilinear terms are approximated by McCormick envelope convex relaxation. The proposed MIQCP framework could be solved efficiently to global optimum and the generated trajectories could exploit the rich features of the rough terrain without any initial guess from the designer. The demonstrated experiment results prove that this approach is currently capable of planning consecutive jumps that navigates a single-legged robot through challenging terrains.