In this paper we address planning problems in high-dimensional hybrid configuration spaces, with a particular focus on manipulation planning problems involving many objects. We present the hybrid backward-forward (HBF) planning algorithm that uses a backward identification of constraints to direct the sampling of the infinite action space in a forward search from the initial state towards a goal configuration. The resulting planner is probabilistically complete and can effectively construct long manipulation plans requiring both prehensile and nonprehensile actions in cluttered environments.
The class of problems that involve finding where to place or how to move a solid object in the presence of obstacles is discussed. The solution to this class of problems is essential to the automatic planning of manipulator transfer movements, i.e., the motions to grasp a part and place it at some destination. For example, planning transfer movements requires the ability to plan paths for the manipulator that avoid collisions with objects in the workspace and the ability to choose safe grasp points on objects. The approach to these problems described here is based on a method of computing an explicit representation of the manipulator configurations that would bring about a collision. This paper deals with motion planning for robots manipulating movable objects among obstacles. We propose a general manipulation planning approach capable of addressing continuous sets for modeling both the possible grasps and the stable placements of the movable object, rather than discrete sets generally assumed by the previous approaches. The proposed algorithm relies on a topological property that characterizes the existence of solutions in the subspace of configurations where the robot grasps the object placed at a stable position. It allows us to devise a manipulation planner that captures in a probabilistic roadmap the connectivity of sub-dimensional manifolds of the composite configuration space. Experiments conducted with the planner in simulated environments demonstrate its efficacy to solve complex manipulation problems. We describe a robot system capable of locating a part in an unstructured pile of objects, choose a grasp on the part, plan a motion to reach the part safely, and plan a motion to place the part at a commanded position. The system requires as input a polyhedral world model including models of the part to be manipulated, the robot arm, and any other fixed objects in the environment. In addition, the system builds a depth map, using structured light, of the area where the part is to be found initially. Any other objects present in that area do not have to be modeled. Motion planning algorithms have generally dealt with motion in a static environment, or more recently, with motion in an environment that changes in a known manner. We consider the problem of finding collision-free motions in a changeable environment. That is, we wish to find a motion for an object where the object is permitted to move some of the obstacles. In such an environment the final positions of the movable obstacles may or may not be part of the goal. In the case where the final positions of the obstacles are unspecified, the motion planning problem is shown to be NP-hard. An algorithm that runs in O ( n 2 log n ) time after O ( n 3 log 2 n ) preprocessing time is presented when the object to be moved is polygonal and there is only one movable polygonal obstacle in a polygonal environment of complexity O ( n ). In the case where the final positions of the obstacles are specified the general problem is shown to be PSPACE-hard and an algorithm is given when there is one movable obstacle with the same preprocessing time as the previous algorithm but with O ( n 2 ) query time. This paper presents a new geometrical formulation of the manipulation task planning problem in robotics. The problem is shown to be a constrained instance of the coordinated motion planning problem for multiple moving bodies. The constraints are related to the placement and the motion of objects, and can be expressed geometrically. We give a general paradigm for building Manipulation Task Planners based on the proposed formulation. A manipulation task appears as a path in the configuration space of the robot and all movable objects. A manipulation path is a sequence of constrained paths: transit-paths , where the robot moves "alone'', and transfer-paths , where the robot holds an object. The approach consists in building a Manipulation Graph that models the connectivity between certain regions in the global configuration space by transit-paths and transfer-paths. This approach is then applied to the case of a finite number of object placements and grasps. The nodes in the Manipulation Graph correspond to well identified configurations and the edges correspond to paths built from a series of configuration space slices. An implemented system is presented and discussed. 