Navigation Among Movable Obstacles: Real-Time Reasoning in Complex Environments

Michael Stilman and James Kuffner
International Journal of Humanoid Robotics, Vol. 2, No. 4, December, 2005, pp. 479-504.


Download
  • 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.

Abstract
In this paper, we address the problem of Navigation Among Movable Obstacles (NAMO): a practical extension to navigation for humanoids and other dexterous mobile robots. The robot is permitted to reconfigure the environment by moving obstacles and clearing free space for a path. This paper presents a resolution complete planner for a subclass of NAMO problems. Our planner takes advantage of the navigational structure through state-space decomposition and heuristic search. The planning complexity is reduced to the difficulty of the specific navigation task, rather than the dimensionality of the multiobject domain. We demonstrate real-time results for spaces that contain large numbers of movable obstacles. We also present a practical framework for single-agent search that can be used in algorithmic reasoning about this domain.

Keywords
NAMO, movable obstacle, motion planning, navigation, manipulation, planning

Notes
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: 24

Text Reference
Michael Stilman and James Kuffner, "Navigation Among Movable Obstacles: Real-Time Reasoning in Complex Environments," International Journal of Humanoid Robotics, Vol. 2, No. 4, December, 2005, pp. 479-504.

BibTeX Reference
@article{Stilman_2005_5374,
   author = "Michael Stilman and James Kuffner",
   editor = "G. Cheng",
   title = "Navigation Among Movable Obstacles: Real-Time Reasoning in Complex Environments",
   journal = "International Journal of Humanoid Robotics",
   pages = "479-504",
   publisher = "World Scientific",
   month = "December",
   year = "2005",
   volume = "2",
   number = "4",
}