Handling Non-Convex Constraints in MPC-Based Humanoid Gait Generation

In most MPC-based schemes used for humanoid gait generation, simple Quadratic Programming (QP) problems are considered for real-time implementation. Since these only allow for convex constraints, the generated gait may be conservative. In this paper we focus on the non-convex reachable region of the swinging foot, also known as Kinematic Admissible Region (KAR), and the corresponding constraint. We represent an approximation of such non-convex region as the union of multiple non-overlapping convex sub-regions. By leveraging the concept of feasibility region, i.e., the subset of the state space for which a QP problem is feasible, and introducing a proper selection criterion, we are able to maintain linearity of the constraints and thus use our Intrinsically Stable Model Predictive Control (IS-MPC) scheme with a negligible additional computational load. This approach allows for a wider range of possible generated motions and is very effective when reacting to a push or avoiding an obstacle, as illustrated in dynamically simulated scenarios.