Footstep planning among obstacles for biped robots

Abstract

We present an algorithm for planning safe navi- gation strategies for biped robots moving in obstacle- cluttered environments. From a discrete set of plau- sible 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 prelim- inary results of an experimental implementation of the algorithm using a model of the H6 humanoid navigat- ing on an oc e o or littered with obstacles.