We present a method for manipulation planning derived from a systematic approach to constrained motion planning. We call it a method of progressive constraints. It replaces an original problem by a series of progressively constrained ones, and makes a solution of the current problem converge toward a solution of the original problem. The manipulation constraints are analyzed and it is shown how they can be introduced progressively. The progressive constraints framework can thus be used for solving manipulation planning problems. The general algorithm proposed for constrained motion planning can be derived from a standard geometric path planner. We use the variational dynamic programming path planner, in which at every iteration a current path is used to generate a submanifold that is searched for a better path.

Presents a general approach to motion planning with uncertainty based upon the Bellman principle of stochastic dynamic programming. The authors introduce the information space, whose elements represent accumulated information about a system. To each of these elements corresponds a certain knowledge of the system, that takes the form of a probability distribution. By applying stochastic dynamic programming (DP), the authors generate optimal or suboptimal motion strategies, i.e. motion commands corresponding to current knowledge, whose execution gives the system the greatest probability of reaching a goal configuration.

Establishes necessary and sufficient conditions under which manipulation constraints are holonomic. Then the authors present a systematic approach to motion planning in the presence of manipulation constraints deriving from this theory. Its principle is to replace a constrained problem by a convergent series of less constrained subproblems increasingly penalizing motions that do not satisfy the constraints. Each subproblem is solved using a standard path planner. The authors use the method of variational dynamic programming for solving the subproblems. The implemented planner has solved manipulation planning problems of unprecedented complexity.>

This paper presents a novel approach to path planning. It is a variational technique, consisting of iteratively improving an initial path possibly colliding with obstacles. At each iteration, the path is improved by performing a dynamic programming search in a sub-manifold of the configuration space containing the current path. We call this method variational dynamic programming (VDP). The method can solve difficult high-dimensional path planning problems without using any problem-specific heuristics. More importantly, an extension of VDP can solve manipulator planning problems of unprecedented complexity.>

An approach to robot path planning that consists of incrementally building a graph connecting the local minima of a potential field defined in the robot's configuration space and concurrently searching this graph until a goal configuration is attained is proposed. Unlike the so-called global path planning methods, this approach does not require an expensive computation step before the search for a path can actually start, and it searches a graph that is usually much smaller than the graph searched by the so-called local methods. A collection of effective techniques to implement this approach is described. They are based on the use of multiscale pyramids of bitmap arrays for representing both the robot's workspace and configuration space. This distributed representation makes it possible to construct potential fields numerically, rather than analytically. A path planner based on these techniques has been implemented. Experiments with this planner show that it is both very fast and capable of handling many degrees of freedom.>

It is shown that the well-known controllability rank condition theorem is applicable to nonholonomic multibody robots, even when there are inequality constraints on the velocity. This makes it possible to subsume and generalize several controllability results published in the robotics literature concerning nonholonomic mobile robots, and to infer new results. Also described is an implemented planner based on these results. Experimental results obtained with this planar are given.>

A stochastic technique is described for planning collision-free paths of robots with many degrees of freedom (DOFs). The algorithm incrementally builds a graph connecting the local minima of a potential function defined in the robot's configuration space and concurrently searches the graph until a goal configuration is attained. A local minimum is connected to another one by executing a random motion that escapes the well of the first minimum, succeeded by a gradient motion that follows the negated gradient of the potential function. All the motions are executed in a grid shown through the robot's configuration space. The random motions are implemented as random walks which are known to converge toward Brownian motions when the steps of the walks tend toward zero. The local minima graph is searched using a depth-first strategy with random backtracking. In the technique, the planner does not explicitly represent the local-minima graph. The path-planning algorithm has been fully implemented and has run successfully on a variety of problems involving robots with many degrees of freedom.>