Constraint Graphs: Unifying task and motion planning for Navigation and Manipulation Among Movable Obstacles

摘要

We consider a class of advanced motion planning problems including object manipulation, navigation among movable obtacles and legged locomotion. Our approach uses rearrangement rules, encoded in a Constraint Graph, a formulation unifying high-level task planning and motion planning. Our method can compute manipulation paths for complex robots and movable-articulated-objects in a static environment, allowing for instance to generate continuous grasps and object placements. A new planning algorithm, Manipulation RRT, makes use of the Constraint Graph to solve Rearrangement problems and to produce rich feedbacks to higher level planners. Simulation results, for problems where movable objects must be manipulated simultaneously or several times, involving humanoid robots, are presented.