Planning Biped Navigation Strategies in Complex Environments

Joel Chestnutt, James Kuffner, Koichi Nishiwaki and Satoshi Kagami
Conference Paper, Proceedings of the 2003 International Conference on Humanoid Robots, October, 2003

View Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


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.

author = {Joel Chestnutt and James Kuffner and Koichi Nishiwaki and Satoshi Kagami},
title = {Planning Biped Navigation Strategies in Complex Environments},
booktitle = {Proceedings of the 2003 International Conference on Humanoid Robots},
year = {2003},
month = {October},
keywords = {bipeds, planning, navigation},
} 2017-09-13T10:44:25-04:00