text: This paper presents an equivalence between feasible kinodynamic planning and optimal kinodynamic planning, in that any optimal planning problem can be transformed into a series of feasible planning problems in a state-cost space whose solutions approach the optimum. This transformation gives rise to a meta-algorithm that produces an asymptotically optimal planner, given any feasible kinodynamic planner as a subroutine. The meta-algorithm is proven to be asymptotically optimal, and a formula is derived relating expected running time and solution suboptimality. It is directly applicable to a wide range of optimal planning problems because it does not resort to the use of steering functions or numerical boundary-value problem solvers. On a set of benchmark problems, it is demonstrated to perform, using the EST and RRT algorithms as subroutines, at a superior or comparable level to related planners.
  @cite_18: This paper presents a systematic benchmarking comparison between optimal motion planners. Six planners representing the categories of sampling-based, grid-based, and trajectory optimization methods are compared on synthetic problems of varying dimensionality, number of homotopy classes, and width and length of narrow passages. Performance statistics are gathered on success and convergence rates, and performance variations with respect to geometric characteristics are analyzed. Based on this analysis, we recommend planners that are likely to perform well for certain problem classes, and draw recommendations for future planning research.
  @cite_14: 
  @cite_4: Recent work in sampling-based motion planning has yielded several different approaches for computing good quality paths in high degree of freedom systems: path shortcutting methods that attempt to shorten a single solution path by connecting non-consecutive configurations, a path hybridization technique that combines portions of two or more solutions to form a shorter path, and asymptotically optimal algorithms that converge to the shortest path over time. This paper presents an extensible meta-algorithm that incorporates a traditional sampling-based planning algorithm with offline path shortening techniques to form an anytime algorithm which exhibits competitive solution lengths to the best known methods and optimizers. A series of experiments involving rigid motion and complex manipulation are performed as well as a comparison with asymptotically optimal methods which show the efficacy of the proposed scheme, particularly in high-dimensional spaces.
  @cite_22: This paper presents a randomized motion planner for kinodynamic asteroid avoidance problems, in which a robot must avoid collision with moving obstacles under kinematic, dynamic constraints and reach a specified goal state. Inspired by probabilistic-roadmap (PRM) techniques, the planner samples the state x time space of a robot by picking control inputs at random in order to compute a roadmap that captures the connectivity of the space. However, the planner does not precompute a roadmap as most PRM planners do. Instead, for each planning query, it generates, on the fly, a small roadmap that connects the given initial and goal state. In contrast to PRM planners, the roadmap computed by our algorithm is a directed graph oriented along the time axis of the space. To verify the planner's effectiveness in practice, we tested it both in simulated environments containing many moving obstacles and on a real robot under strict dynamic constraints. The efficiency of the planner makes it possible for a robot to respond to a changing environment without knowing the motion of moving obstacles well in advance.
  @cite_9: Abstract A fast marching level set method is presented for monotonically advancing fronts, which leads to an extremely fast scheme for solving the Eikonal equation. Level set methods are numerical techniques for computing the position of propagating fronts. They rely on an initial value partial differential equation for a propagating level set function and use techniques borrowed from hyperbolic conservation laws. Topological changes, corner and cusp development, and accurate determination of geometric properties such as curvature and normal direction are naturally obtained in this setting. This paper describes a particular case of such methods for interfaces whose speed depends only on local position. The technique works by coupling work on entropy conditions for interface motion, the theory of viscosity solutions for Hamilton-Jacobi equations, and fast adaptive narrow band level set methods. The technique is applicable to a variety of problems, including shape-from-shading problems, lithographic development calculations in microchip manufacturing, and arrival time problems in control theory.
  @cite_1: During the last decade, sampling-based path planning algorithms, such as probabilistic roadmaps (PRM) and rapidly exploring random trees (RRT), have been shown to work well in practice and possess theoretical guarantees such as probabilistic completeness. However, little effort has been devoted to the formal analysis of the quality of the solution returned by such algorithms, e.g. as a function of the number of samples. The purpose of this paper is to fill this gap, by rigorously analyzing the asymptotic behavior of the cost of the solution returned by stochastic sampling-based algorithms as the number of samples increases. A number of negative results are provided, characterizing existing algorithms, e.g. showing that, under mild technical conditions, the cost of the solution returned by broadly used sampling-based algorithms converges almost surely to a non-optimal value. The main contribution of the paper is the introduction of new algorithms, namely, PRM* and RRT*, which are provably asymptotically optimal, i.e. such that the cost of the returned solution converges almost surely to the optimum. Moreover, it is shown that the computational complexity of the new algorithms is within a constant factor of that of their probabilistically complete (but not asymptotically optimal) counterparts. The analysis in this paper hinges on novel connections between stochastic sampling-based path planning algorithms and the theory of random geometric graphs.
  @cite_3: This paper presents an optimization-based framework for emulating the low-level capabilities of human motor coordination and learning. Our approach rests on the observation that in most biological motor learning scenarios some form of optimization with respect to a physical criterion is taking place. By appealing to techniques from the theory of Lie groups, we are able to formulate the equations of motion of complex multibody systems in such a way that the resulting optimization problems can be solved reliably and efficiently—the key lies in the ability to compute exact analytic gradients of the objective function without resorting to numerical approximations. The methodology is illustrated via a wide range of optimized, “natural” motions for robots performing various human-like tasks—for example, power lifting, diving, and gymnastics. © 2001 John Wiley & Sons, Inc.
  @cite_6: 
  @cite_0: Randomized path planners have been successfully used to compute feasible paths for difficult planning problems. Such paths are typically computed without taking into account any optimality criteria and may contain many “jagged” segments because of the randomness involved in their generation. This paper presents a two-phase path planning algorithm, which uses a randomized planner to compute low-cost paths, and gradient descent to locally optimize these paths by minimizing a Hamiltonian function. The algorithm is tested on motion planning for a non-holonomic car-like robot. The results indicate that the two-phase approach is practical; however, gradient descent seems to be inefficient for the optimization of long paths.
  @cite_5: 
  @cite_13: The planning problem is considered for a mobile manipulator system which must perform a sequence of tasks defined by position, orientation, force, and moment vectors at the end effector. Each task can be performed in multiple configurations due to the redundancy introduced by mobility. The planning problem is formulated as an optimization problem in which the decision variables for mobility (base position) are separated from the manipulator joint angles in the cost function. The resulting numerical problem is nonlinear with nonconvex, unconnected feasible regions in the decision space. Simulated annealing is proposed as a general solution method for obtaining near-optimal results. The problem formulation and numerical solution by simulated annealing are illustrated for a positioning system with five degrees of freedom. These results are compared with results obtained by conventional nonlinear programming techniques customized for the particular example system. >
  @cite_25: This paper presents the first randomized approach to kinodynamic planning (also known as trajectory planning or trajectory design). The task is to determine control inputs to drive a robot from an ini ial configuration and velocity to a goal configuration and velocity while obeying physically based dynamical models and avoiding obstacles in the robot’s environment. The authors consider generic systems that express the nonlinear dynamics of a robot in terms of the robot’s high-dimensional configuration space. Kinodynamic planning is treated as a motion-planning problem in a higher dimensional state space that has both first-order differential constraints and obstacle-based global constraints. The state space serves the same role as the configuration space for basic path planning; however, standard randomized path-planning techniques do not directly apply to planning trajectories in the state space. The authors have developed a randomized planning approach that is particularly tailored to trajectory plannin...
  @cite_20: 
  @cite_17: A new motion planning method for robots in static workspaces is presented. This method proceeds in two phases: a learning phase and a query phase. In the learning phase, a probabilistic roadmap is constructed and stored as a graph whose nodes correspond to collision-free configurations and whose edges correspond to feasible paths between these configurations. These paths are computed using a simple and fast local planner. In the query phase, any given start and goal configurations of the robot are connected to two nodes of the roadmap; the roadmap is then searched for a path joining these two nodes. The method is general and easy to implement. It can be applied to virtually any type of holonomic robot. It requires selecting certain parameters (e.g., the duration of the learning phase) whose values depend on the scene, that is the robot and its workspace. But these values turn out to be relatively easy to choose, Increased efficiency can also be achieved by tailoring some components of the method (e.g., the local planner) to the considered robots. In this paper the method is applied to planar articulated robots with many degrees of freedom. Experimental results show that path planning can be done in a fraction of a second on a contemporary workstation ( spl ap 150 MIPS), after learning for relatively short periods of time (a few dozen seconds).
summary: Optimal motion planning has been a topic of renewed activity in robotics largely due to the advent of sampling-based motion planners that are proven to be asymptotically optimal @cite_1 . But the community has had a long history of interest in optimal motions. Numerical trajectory optimization techniques @cite_20 @cite_13 @cite_3 @cite_14 have been long studied, but have several drawbacks. First, they are prone to falling into local minima, and second they typically require differentiable constraint and cost representations, which are often hard to produce for complex obstacles. Grid-based planners @cite_6 @cite_5 @cite_9 are often fast in low dimensional spaces but suffer from the curse of dimensionality,'' with performance degrading rapidly in spaces of higher dimension @cite_18 . Sampling-based planners were originally developed to overcome many of these challenges, and have been shown to have excellent empirical performance in finding feasible paths in high-dimensional spaces, both without @cite_17 and with dynamic constraints @cite_22 @cite_25 . However, they tend to produce jerky paths that are far from optimal. Some hybrid approaches have combined sampling-based planning with local optimization to produce better paths @cite_4 @cite_0 .