Navigation Among Movable Obstacles

Michael Stilman
doctoral dissertation, tech. report CMU-RI-TR-07-37, Robotics Institute, Carnegie Mellon University, October, 2007

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

Robots would be much more useful if they could move obstacles out of the way. Traditional motion planning searches for collision free paths from a start to a goal. However, real world search and rescue, construction, home and nursing home domains contain debris, materials clutter, doors and ob jects that need to be moved by the robot. Theoretically, one can represent all possible interactions between the robot and movable ob jects as a huge search. We present methods that simplify the problem and make Navigation Among Movable Obstacles (NAMO) a practical challenge that can be addressed with current computers.

This thesis gives a full development cycle from motion planning to implementation on a humanoid robot. First, we devise a state space decomposition strategy that reasons about free space connectivity to select ob jects and identify helpful displacements. Second, we present controls for balance and manipulation that allow the robot to move ob jects with previously unknown dynamics. Finally, we combine these results in a complete system that recognizes environment ob jects and executes Navigation Among Movable Obstacles.

Our continued work in NAMO planning has focused on three topics: reasoning about ob ject interaction, three dimensional manipulation and interaction with constrained ob- jects. This thesis presents the computational and theoretical challenges that arise from these elaborations of the NAMO domain. In each case we introduce extensions to our algorithms that respond to the challenge and evaluate their performance in simulation. All the methods presented in this thesis not only solve previously unsolved problems but also operate efficiently, giving real-time results that can be used during online operation.

Associated Center(s) / Consortia: Center for the Foundations of Robotics
Associated Lab(s) / Group(s): Planning and Autonomy Lab
Associated Project(s): Navigation Among Movable Obstacles
Number of pages: 144

Text Reference
Michael Stilman, "Navigation Among Movable Obstacles," doctoral dissertation, tech. report CMU-RI-TR-07-37, Robotics Institute, Carnegie Mellon University, October, 2007

BibTeX Reference
   author = "Michael Stilman",
   title = "Navigation Among Movable Obstacles",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   month = "October",
   year = "2007",
   number= "CMU-RI-TR-07-37",
   address= "Pittsburgh, PA",