Sample-based motion planning in high-dimensional and differentially-constrained systems

State of the art sample-based path planning algorithms, such as the Rapidly-exploring Random Tree (RRT), have proven to be effective in path planning for systems subject to complex kinematic and geometric constraints. The performance of these algorithms, however, degrade as the dimension of the system increases. Furthermore, sample-based planners rely on distance metrics which do not work well when the system has differential constraints. Such constraints are particularly challenging in systems with non-holonomic and underactuated dynamics. This thesis develops two intelligent sampling strategies to help guide the search process. To reduce sensitivity to dimension, sampling can be done in a low-dimensional task space rather than in the high-dimensional state space. Altering the sampling strategy in this way creates a Voronoi Bias in task space, which helps to guide the search, while the RRT continues to verify trajectory feasibility in the full state space. Fast path planning is demonstrated using this approach on a 1500-link manipulator. To enable task-space biasing for underactuated systems, a hierarchical task space controller is developed by utilizing partial feedback linearization. Another sampling strategy is also presented, where the local reachability of the tree is approximated, and used to bias the search, for systems subject to differential constraints. Reachability guidance is shown to improve search performance of the RRT by an order of magnitude when planning on a pendulum and non-holonomic car. The ideas of task-space biasing and reachability guidance are then combined for demonstration of a motion planning algorithm implemented on LittleDog, a quadruped robot. The motion planning algorithm successfully planned bounding trajectories over extremely rough terrain.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2010

Author dc:creator

• Shkolnik, Alexander C

Advisor dc:contributor.advisor

• Russ Tedrake.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/57537

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/57537