Carnegie Mellon University
Online Footstep Planning for Humanoid Robots

James Kuffner, K. Nishiwaki, Satoshi Kagami, Y. Kuniyoshi, M. Inaba, and H. Inoue
IEEE Int'l Conf. on Robotics and Automation (ICRA'2003), September, 2003.

  • Adobe portable document format (pdf) (3MB)
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.

motion planning, biped robots, online walking control, humanoids

Associated Center(s) / Consortia: Center for the Foundations of Robotics
Associated Lab(s) / Group(s): Planning and Autonomy Lab
Associated Project(s): Footstep Planning for Biped Robots
Number of pages: 6

Text Reference
James Kuffner, K. Nishiwaki, Satoshi Kagami, Y. Kuniyoshi, M. Inaba, and H. Inoue, "Online Footstep Planning for Humanoid Robots," IEEE Int'l Conf. on Robotics and Automation (ICRA'2003), September, 2003.

BibTeX Reference
   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)",
   publisher = "IEEE",
   month = "September",
   year = "2003",