Footstep planning among obstacles for biped robots

We present an algorithm for planning safe navigation strategies for biped robots moving in obstacle-cluttered environments. From a discrete set of plausible statically-stable, single-step motions, a forward dynamic programming approach is used to compute a sequence of feasible footstep locations. In contrast to existing navigation strategies for mobile robots, our method is a global method that takes into account the unique ability of legged robots such as bipedal humanoids to traverse obstacles by stepping over them. 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. We show preliminary results of an experimental implementation of the algorithm using a model of the H6 humanoid navigating on an office floor littered with obstacles