In this paper, we address the problem of automatically generating motions for nonholonomic systems consisting of tractors with trailers. The presented method generalizes an existing dynamic programming exploration technique using a progressive constraints approach. It has performed well in experiments with multibody vehicles moving with few reversals in cluttered environments.

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 method for nonholonomic motion planning (NMP), that is able to solve problems for systems with high-dimensional configuration spaces. The original NMP problem is replaced by a series of progressively constrained ones that are solved successively, and whose solution path converges towards a solution of the original problem. The nonholonomic constraints are introduced progressively in an iterative algorithm. Each iteration consists of exploring a neighborhood of the path obtained from the previous iteration, searching for a path that satisfies more accurate constraints. The explorations proceed according to a dynamic programming procedure able to deal with optimization criteria.

Considers the motions of objects moved by manipulators that can only perform some specific actions. These motions are fundamentally nonholonomic. They consist of a sequence of maneuvers, each one being a permitted action of a manipulator. We present a general method for planning such motions while minimizing the number of maneuvers. The object's state space is searched by performing step motions corresponding to the permitted manipulator actions. We distinguish between low-dimensional cases in which the system's state space is explored extensively, and high-dimensional cases. In the latter we introduce the motion constraints progressively. Successive explorations are performed in a neighborhood of a current path that converges toward a solution.

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.>