Navigation Among Movable Obstacles in unknown environments

This paper explores the Navigation Among Movable Obstacles (NAMO) problem in an unknown environment. We consider the realistic scenario in which the robot has to navigate to a goal position in an unknown environment consisting of static and movable objects. The robot may move objects if the goal can not be reached otherwise or if moving the object may significantly shorten the path to the goal. We consider real situations in which the robot only has limited sensing information and where the action selection can therefore only be based on partial knowledge learned from the environment at that point. This paper introduces an algorithm that significantly reduces the necessary calculations to accomplish this task compared to a direct approach. We present an efficient implementation for the case of planar, axis-aligned environments and report experimental results on challenging scenarios with more than 50 objects.

Authors

• Hai-Ning Wu
• Martin Levihn
• Mike Stilman

Keywords

• Heuristic algorithms
• Optimization
• Planning
• Navigation
• Robot sensing systems
• Robot kinematics
• Unknown Environment
• Movable Obstacles
• Object Motion
• Partial Knowledge
• Static Objects
• Goal Position
• Dynamics Simulations
• Local Information
• Number Of Steps
• Multiple Activities
• Partial Information
• Multiple Objects
• Object Size
• Path Planning
• Uncertain Environment
• Robot Motion
• Laser Ranging
• Baseline Algorithms
• List Of Elements