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.
 We present an approach to path planning for humanoid robots that computes dynamically-stable, collision-free trajectories from full-body posture goals. Given a geometric model of the environment and a statically-stable desired posture, we search the configuration space of the robot for a collision-free path that simultaneously satisfies dynamic balance constraints. We adapt existing randomized path planning techniques by imposing balance constraints on incremental search motions in order to maintain the overall dynamic stability of the final path. A dynamics filtering function that constrains the ZMP (zero moment point) trajectory is used as a post-processing step to transform statically-stable, collision-free paths into dynamically-stable, collision-free trajectories for the entire body. Although we have focused our experiments on biped robots with a humanoid shape, the method generally applies to any robot subject to balance constraints (legged or not). The algorithm is presented along with computed examples using both simulated and real humanoid robots. Humanoid robots have abilities of stepping over or onto obstacles, which is different from wheeled robots. However it may be difficult to apply the ordinary motion planning methods such as Rapidly-exploring Random Trees (RRT) to humanoid robots directly. Because these kinds of methods only consider to circumvent obstacles and ignore the constraint of balance. Aiming at dealing with these problems in one frame, a novel approach based on hierarchical RRT is used to plan the footstep for humanoid robots. It is designed according to three basic constraints: a transition model based gait generator, an inverted pendulum based balance controller and a collision detection based path planner. First, a set of layered transition model is utilized to revise the footstep according to the terrain condition, which is able to take full use of the motion ability as well as improve the efficiency. Then, a hierarchical strategy is exploited to select the feasible foot location to be added in the random tree based on the results of collision checking and balance control. Finally, a dynamic RRT method is introduced in our work to revise paths in changing environments. Different experiments are given to verify the feasibility and performance of the proposed approach in complicated environments with both dynamic and static obstacles.