A Generalized Mixed-Integer Convex Program for Multilegged Footstep Planning on Uneven Terrain

Robot footstep planning strategies can be divided in two main approaches: discrete searches and continuous optimizations. While discrete searches have been broadly applied, continuous optimizations approaches have been restricted for humanoid platforms. This article introduces a generalized continuous-optimization approach for multilegged footstep planning which can be adapted to different platforms, regardless the number and geometry of legs. This approach leverages Mixed-Integer Convex Programming to account for the non-convex constraints that represent footstep rotation and obstacle avoidance. The planning problem is formulated as an optimization problem which considers robot geometry and reachability with linear constraints, and can be efficiently solved using optimization software. To demonstrate the functionality and adaptability of the planner, a set of tests are performed on a BH3R hexapod and a LittleDog quadruped on scenarios which can't be easily handled with discrete searches, such tests are solved efficiently in fractions of a second. This work represents, to the knowledge of the authors, the first successful implementation of a continuous optimization-based multilegged footstep planner.