Online footstep planning for humanoid robots

We present an online algorithm for planning sequences of footstep locations that encode goal-directed navigation strategies for humanoid robots. Planning footsteps is more general than most existing navigation methods designed for wheeled robots, since the options of stepping over or upon obstacles in a cluttered terrain are available. Given a discrete set of plausible footstep locations, a forward dynamic programming approach is used to compute a footstep sequence to a specified goal location in the environment. Heuristics designed to minimize the number and complexity of the step motions are used to encode cost functions used for searching a footstep transition graph. If successful, the planner returns an optimal sequence of footstep locations according to the cost functions and plausible sets of footstep locations defined. We show results from an experimental implementation of the algorithm running on the H7 humanoid robot. Using a stereo vision system to sense obstacles in the immediate environment and identify a target goal location, the robot updates the current optimal footstep sequence to the goal from its present location.