Online Footstep Planning for Humanoid Robots

James Kuffner, K. Nishiwaki, Satoshi Kagami, Y. Kuniyoshi, M. Inaba and H. Inoue
Conference Paper, IEEE Int'l Conf. on Robotics and Automation (ICRA'2003), September, 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 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.

author = {James Kuffner and K. Nishiwaki and Satoshi Kagami and Y. Kuniyoshi and M. Inaba and H. Inoue},
title = {Online Footstep Planning for Humanoid Robots},
booktitle = {IEEE Int'l Conf. on Robotics and Automation (ICRA'2003)},
year = {2003},
month = {September},
publisher = {IEEE},
keywords = {motion planning, biped robots, online walking control, humanoids},
} 2017-09-13T10:44:30-04:00