A desirable property of path planning for robotic manipulation is the ability to identify solutions in a sufficiently short amount of time to be usable. This is particularly challenging for the manipulation problem due to the need to plan over high-dimensional configuration spaces and to perform computationally expensive collision checking procedures. Consequently, existing planners take steps to achieve desired solution times at the cost of low quality solutions. This paper presents a planning algorithm that overcomes these difficulties by augmenting the asymptotically-optimal RRT* with a sparse sampling procedure. With the addition of a collision checking procedure that leverages memoization, this approach has the benefit that it quickly identifies low-cost feasible trajectories and takes advantage of subsequent computation time to refine the solution towards an optimal one. We evaluate the algorithm through a series of Monte Carlo simulations of seven, twelve, and fourteen degree of freedom manipulation planning problems in a realistic simulation environment. The results indicate that the proposed approach provides significant improvements in the quality of both the initial solution and the final path, while incurring almost no computational overhead compared to the RRT algorithm. We conclude with a demonstration of our algorithm for single-arm and dual-arm planning on Willow Garage's PR2 robot.

The reduction of the kinematics and/or dynamics of a high-DOF robotic manipulator to a low-dimension ldquotask spacerdquo has proven to be an invaluable tool for designing feedback controllers. When obstacles or other kinodynamic constraints complicate the feedback design process, motion planning techniques can often still find feasible paths, but these techniques are typically implemented in the high-dimensional configuration (or state) space. Here we argue that providing a Voronoi bias in the task space can dramatically improve the performance of randomized motion planners, while still avoiding non-trivial constraints in the configuration (or state) space. We demonstrate the potential of task-space search by planning collision-free trajectories for a 1500 link arm through obstacles to reach a desired end-effector position.

Rapidly-exploring random trees (RRTs) are widely used to solve large planning problems where the scope prohibits the feasibility of deterministic solvers, but the efficiency of these algorithms can be severely compromised in the presence of certain kinodynamics constraints. Obstacle fields with tunnels, or tubes are notoriously difficult, as are systems with differential constraints, because the tree grows inefficiently at the boundaries. Here we present a new sampling strategy for the RRT algorithm, based on an estimated feasibility set, which affords a dramatic improvement in performance in these severely constrained systems. We demonstrate the algorithm with a detailed look at the expansion of an RRT in a swing up task, and on path planning for a nonholonomic car.

Kinodynamic planning algorithms have the potential to find feasible control trajectories which accomplish a task even in very nonlinear or constrained dynamical systems. Underactuation represents a particular form of a dynamic constraint, inherently present in many machines of interest (e.g., walking robots), and necessitates planning for long-term control solutions. A major limitation in motion planning techniques, especially for real-time implementation, is that they are only practical for relatively low degree-of-freedom problems. Here we present a model-based dimensionality reduction technique based on an extension of partial feedback linearization control into a task-space framework. This allows one to plan motions for a complex underactuated robot directly in a low-dimensional task-space, and to resolve redundancy with lower-priority tasks. We illustrate the potential of this approach with an extremely simple motion planning system which solves the swing-up problem for multi-link underactuated pendula, and discuss extensions to the control of walking.

In this work we examine the control of center of mass and swing leg trajectories in LittleDog, a point-foot quadruped robot. It is not clear how to formulate a function to compute forward kinematics of the center of mass of the robot as a function of actuated joint angles because point-foot walkers have no direct actuation between the feet and the ground. Nevertheless, we show that a whole-body Jacobian exists and is well defined when at least three of the feet are on the ground. Also, the typical approach of work-space centering for redundancy resolution causes destabilizing motions when executing fast motions. An alternative redundancy resolution optimization is proposed which projects single-leg inverse kinematic solutions into the nullspace. This hybrid approach seems to minimize 1) unnecessary rotation of the body, 2) twisting of the stance legs, and 3) whole-body involvement in achieving a step leg trajectory. In simulation, this control allows the robot to perform significantly more dynamic behaviors while maintaining stability.

We propose a fast approach for detecting collision- free swing-foot trajectories for legged locomotion over extreme terrains. Instead of simulating the swing trajectories and checking for collisions along them, our approach uses machine learning techniques to predict whether a swing trajectory is collision-free. Using a set of local terrain features, we apply supervised learning to train a classifier to predict collisions. Both in simulation and on a real quadruped platform, our results show that our classifiers can improve the accuracy of collision detection compared to a real-time geometric approach without significantly increasing the computation time.