Planning Biped Navigation Strategies in Complex Environments

Abstract

We present an algorithm for planning goal-directed footstep navigation strategies for biped robots through obstacle-filled environments and uneven ground. Planning footsteps is more general than most existing navigation methods designed for wheeled robots, since the options of stepping over or upon obstacles are available. Given a height map of the terrain and a discrete set of possible footstep motions, the planner uses an A* search to generate a sequence of footstep locations to reach a given goal state. The planner evaluates footstep locations for viability using a collection of heuristic metrics designed to encode the relative safety, effort required, and overall motion complexity. We show preliminary results of the planner over several simulated terrains, as well as a simplified, online version of the algorithm running on the H7 humanoid robot. In the latter case, a stereo vision system is used to sense obstacles in the immediate environment and identify a target goal location, which is used to update the current optimal footstep sequence to the goal from the robot's present location.