  We present a sampling-based kinodynamic planning framework for a bipedal
robot in complex environments. Unlike other footstep planner which typically
plan footstep locations and the biped dynamics in separate steps, we handle
both simultaneously. Three advantages of this approach are (1) the ability to
differentiate alternate routes while selecting footstep locations based on the
temporal duration of the route as determined by the Linear Inverted Pendulum
Model dynamics, (2) the ability to perform collision checking through time so
that collisions with moving obstacles are prevented without avoiding their
entire trajectory, and (3) the ability to specify a minimum forward velocity
for the biped. To generate a dynamically consistent description of the walking
behavior, we exploit the Phase Space Planner. To plan a collision free route
toward the goal, we adapt planning strategies from non-holonomic wheeled robots
to gather a sequence of inputs for the PSP. This allows us to efficiently
approximate dynamic and kinematic constraints on bipedal motion, to apply a
sampling based planning algorithms, and to use the Dubin's path as the steering
method to connect two points in the configuration space. The results of the
algorithm are sent to a Whole Body Controller to generate full body dynamic
walking behavior.
