Feasibility-Based Convexification of MPC Footstep Constraints for Humanoid Gait Generation

Model Predictive Control is an effective tool for robust humanoid gait generation in complex 3D environments. This challenging operating condition typically results in non-convex footstep constraints which, if directly included in the optimization problem, would introduce significant computation overhead. We present a feasibility-driven method to convexify such constraints so as to retain an efficient QP formulation. At each control cycle, the non-convex steppable region is decomposed into convex subregions, one of which is selected to set up the MPC problem, based on a criterion which balances QP feasibility and conformity to the original plan. Dynamic simulations on the HRP-4 humanoid demonstrate robust push recovery with leg crossing and reactive navigation in cluttered 3D environments, including stepping onto obstacles when beneficial. A comparison against a mixed-integer variant of the method confirms that the proposed selection strategy preserves feasibility and responsiveness with a limited computational load.