Navigation Among Movable Obstacles: Real-Time Reasoning in Complex Environments
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.
BibTeX
@article{Stilman-2005-9363,author = {Michael Stilman and James Kuffner},
title = {Navigation Among Movable Obstacles: Real-Time Reasoning in Complex Environments},
journal = {International Journal of Humanoid Robotics},
year = {2005},
month = {December},
volume = {2},
number = {4},
pages = {479 - 504},
keywords = {NAMO, movable obstacle, motion planning, navigation, manipulation, planning},
}