Humanoids' abilities to navigate uneven terrain make them well-suited for disaster response efforts, but humanoid motion planning in unstructured environments remains a challenging problem. In this thesis we focus on planning contact sequences for a humanoid robot navigating in large unstructured environments using multi-contact motion, including both foot and palm contacts. In particular, we address the two following questions: (1) How do we efficiently generate a feasible contact sequence? and (2) How do we generate contact sequences which lead to dynamically-robust motions?

For the first question, we propose a library-based method that retrieves motion plans from a library constructed offline, and adapts them with local trajectory optimization to generate the full motion plan from the start to the goal. This approach outperforms a conventional graph search contact planner when it is difficult to decide which contact is preferable with a simplified robot model and local environment information. We also propose a learning approach to estimate the difficulty to traverse a certain region based on the environment features. By integrating the two approaches, we propose a planning framework that uses graph search planner to find contact sequences around easy regions. When it is necessary to go through a difficult region, the framework switches to use the library-based method around the region to find a feasible contact sequence faster.

For the second question, we consider dynamic motions in contact planning. Most humanoid motion generators do not optimize the dynamic robustness of a contact sequence. By querying a learned model to predict the dynamic feasibility and robustness of each contact transition from a centroidal dynamics optimizer, the proposed planner efficiently finds contact sequences which lead to dynamically-robust motions. We also propose a learning-based footstep planner which takes external disturbances into account. The planner considers not only the poses of the planned contact sequence, but also alternative contacts near the planned contact sequence that can be used to recover from external disturbances. Neural networks are trained to efficiently predict multi-contact zero-step and one-step capturability, which allows the planner to generate contact sequences robust to external disturbances efficiently.