/A Multi-Heuristic framework for Humanoid Planning

A Multi-Heuristic framework for Humanoid Planning

Karthik Vijayakumar
Master's Thesis, Tech. Report, CMU-RI-TR-17-57, Robotics Institute, Carnegie Mellon University, August, 2017

Download Publication (PDF)

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.


Humanoid robots have been the subject of active research for several years, with the aim of developing systems that can potentially replace humans in performing dangerous tasks with similar agility and versatility. Motion planning for humanoid robots is a particularly challenging problem because of the high dimensionality of the planning space, kinematic constraints and stability. The general approach to planning for humanoid mobility in complex environments, such as industries, with potentially multiple state-space abstractions, for e.g. bipedal, ladder, crawling etc., is to plan separately for each of these representations and combine the solution. A recently developed technique of planning with adaptive dimensionality can be used to develop a single planner to handle such multiple state-space abstractions. To this end, we develop a Multi-heuristic framework, as a generalization of MHA*, that can simultaneously plan across multiple state-space representations to produce a single solution. We test our planner in challenging environments containing several abstractions such as staircases, ladders, etc.

A heuristic based planner for high-dimensional state-space planning has a potential drawback of the user having to define good heuristic functions that guide the search. This can become a very tedious task for a system as complex as the humanoid. In this thesis, we address the issue of automatically deriving heuristic functions by learning macro-actions from a database of previous plans. By extracting spatio-temporal bases of repeatedly seen motions in prior plans, we generate new macro-actions as a planning pre-computation, subject to various constraints. We also show how these macro-actions can be used as heuristics and provide preliminary results on full-body planning for humanoids.

BibTeX Reference
author = {Karthik Vijayakumar},
title = {A Multi-Heuristic framework for Humanoid Planning},
year = {2017},
month = {August},
school = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-17-57},