Multi-Fidelity Receding Horizon Planning for Multi-Contact Locomotion

When traversing uneven terrain, humans consider their future steps for choosing the best location and timing of their current step. Likewise, when planning multi-contact motions for legged robots (e.g. humanoids), a ‘prediction horizon’ has to be considered. However, planning several steps ahead increases the dimensionality and non-linearity of an already challenging problem, which makes online planning intractable. We propose to reduce the problem complexity by using convex relaxations in the prediction horizon. We realize this idea within a Receding Horizon Planning (RHP) framework to plan dynamically consistent centroidal trajectories of humanoid walking on uneven terrain. This results in a novel formulation that combines an accurate non-convex model with a relaxed convex model, which we call RHP with multiple levels of model fidelity. We evaluate three candidate multi-fidelity RHPs with convex relaxations of the centroidal dynamics in the prediction horizon. The best candidate is 1.4x-3.0x (average 2.4x) faster than the traditional RHP that employs a single dynamics model over the entire look-ahead horizon. We also validate the resultant centroidal trajectories by tracking them with a whole-body inverse dynamics controller in simulation. Lastly, we find that incorporating angular dynamics in the prediction horizon is important to the success of multi-fidelity RHP.