Planning Among Movable Obstacles with

Artificial Constraints In this paper we present artificial constraints as a method for guiding heuristic search in the computationally challenging domain of motion planning among movable obstacles. The robot is permitted to manip-ulate unspecified obstacles in order to create space for a path. A plan is an ordered sequence of paths for robot motion and object manip-ulation. We show that under monotone assumptions, anticipating fu-ture manipulation paths results in constraints on both the choice of objects and their placements at earlier stages in the plan. We present an algorithm that uses this observation to incrementally reduce the search space and quickly find solutions to previously unsolved classes of movable obstacle problems. Our planner is developed for arbitrary robot geometry and kinematics. It is presented with an implementa-tion for the domain of navigation among movable obstacles. KEY WORDS—Key Words 1