  We present an algorithm for receding-horizon motion planning using a finite
family of motion primitives for underactuated dynamic walking over uneven
terrain. The motion primitives are defined as virtual holonomic constraints,
and the special structure of underactuated mechanical systems operating subject
to virtual constraints is used to construct closed-form solutions and a special
binary search tree that dramatically speed up motion planning. We propose a
greedy depth-first search and discuss improvement using energy-based
heuristics. The resulting algorithm can plan several footsteps ahead in a
fraction of a second for both the compass-gait walker and a planar
7-Degree-of-freedom/five-link walker.
