This paper presents a motion planner that enables a humanoid robot to push an object on a flat surface. The robot's motion is divided into distinct walking, reaching, and pushing modes. A discrete change of mode can be achieved with a continuous single-mode motion that satisfies mode-specific constraints (e.g. dynamics, kinematic limits, avoid obstacles). Existing techniques can plan well in single modes, but choosing the right mode transitions is difficult. Search-based methods are vastly inefficient due to over-exploration of similar modes. Our new method, Random-MMP, randomly samples mode transitions to distribute a sparse number of modes across configuration space. Results are presented in simulation and on the Honda ASIMO robot. © 2010 Springer-Verlag Berlin Heidelberg.