Despite the performance advantages of modern sampling-based motion planners, solving high dimensional planning problems in near real-time remains a challenge. Applications include hyper-redundant manipulators, snake-like and humanoid robots. Based on the intuition that many of these problem instances do not require the robots to exercise every degree of freedom independently, we introduce an enhancement to popular sampling-based planning algorithms aimed at circumventing the exponential dependence on dimensionality. We propose beginning the search in a lower dimensional subspace of the configuration space in the hopes that a simple solution will be found quickly. After a certain number of samples are generated, if no solution is found, we increase the dimension of the search subspace by one and continue sampling in the higher dimensional subspace. In the worst case, the search subspace expands to include the full configuration space - making the completeness properties identical to the underlying sampling-based planer. Our experiments comparing the enhanced and traditional version of RRT, RRT-Connect, and BidirectionalT-RRT on both a planar hyper-redundant manipulator and the Baxter humanoid robot indicate that a solution is typically found much faster using this approach and the run time appears to be less sensitive to the dimension of the full configuration space. We explore important implementation issues in the sampling process and discuss its limitations.
Furthermore, motion planning for humanoid robots with sampling-based algorithms has been explored; Kuffner presented algorithms for motion planning on humanoid robots with both the use of PRMs @cite_10 and RRTs @cite_34 . Other studies, such as the work of Liu @cite_7 , use RRTs for solving the stepping problem for humanoid robots.
@cite_34 @cite_10 @cite_7
1485487406 2000194319 2026941035 2054585537
Asymptotically-optimal sampling-based motion planners, like RRT*, perform vast amounts of collision checking, and are hence rather slow to converge in complex problems where collision checking is relatively expensive. This paper presents two novel motion planners, Lazy-PRM* and Lazy-RRG*, that eliminate the majority of collision checks using a lazy strategy. They are sampling-based, any-time, and asymptotically complete algorithms that grow a network of feasible vertices connected by edges. Edges are not immediately checked for collision, but rather are checked only when a better path to the goal is found. This strategy avoids checking the vast majority of edges that have no chance of being on an optimal path. Experiments show that the new methods converge toward the optimum substantially faster than existing planners on rigid body path planning and robot manipulation problems. Sampling-based motion planning algorithms, such as the Probabilistic RoadMap (PRM) and the Rapidly-exploring Random Tree (RRT), have received a large and growing amount of attention during the past decade. Most recently, sampling-based algorithms, such as the PRM* and RRT*, that guarantee asymptotic optimality, i.e., almost-sure convergence towards optimal solutions, have been proposed. Despite the experimental success of asymptotically-optimal sampling-based algorithms, their extensions to handle complex non-holonomic dynamical systems remains largely an open problem. In this paper, with the help of results from differential geometry, we extend the RRT* algorithm to handle a large class of non-holonomic dynamical systems. We demonstrate the performance of the algorithm in computational experiments involving the Dubins' car dynamics. This paper presents a technique for improving the efficiency of automated motion planners. Motion planning has application in many areas such as robotics, virtual reality systems, computer-aided design, and even computational biology. Although there have been steady advances in motion planning algorithms, especially in randomized approaches such as probabilistic roadmap methods (PRMs) or rapidly-exploring random trees (RRTs), there are still some classes of problems that cannot be solved efficiently using these state-of-the-art motion planners. In this paper, we suggest an iterative strategy addressing this problem where we first simplify the problem by relaxing some feasibility constraints, solve the easier version of the problem, and then use that solution to help us find a solution for the harder problem. We show how this strategy can be applied to rigid bodies and to linkages with high degrees of freedom, including both open and closed chain systems. Experimental results are presented for linkages composed of 9-98 links. Although we use PRMs as the automated planner, the framework is general and can be applied with other motion planning techniques as well. We present Kinodynamic RRT*, an incremental sampling-based approach for asymptotically optimal motion planning for robots with linear dynamics. Our approach extends RRT*, which was introduced for holonomic robots [10], by using a fixed-final-state-free-final-time controller that optimally connects any pair of states, where the cost function is expressed as a trade-off between the duration of a trajectory and the expended control effort. Our approach generalizes earlier work on RRT* for kinodynamic systems, as it guarantees asymptotic optimality for any system with controllable linear dynamics, in state spaces of any dimension. In addition, we show that for the rich subclass of systems with a nilpotent dynamics matrix, closed-form solutions for optimal trajectories can be derived, which keeps the computational overhead of our algorithm compared to traditional RRT* at a minimum. We demonstrate the potential of our approach by computing asymptotically optimal trajectories in three challenging motion planning scenarios: (i) a planar robot with a 4-D state space and double integrator dynamics, (ii) an aerial vehicle with a 10-D state space and linearized quadrotor dynamics, and (iii) a car-like robot with a 5-D state space and non-linear dynamics.