Date of Award

Spring 1-1-2017

Document Type


Degree Name

Doctor of Philosophy (PhD)

First Advisor

Nikolaus Correll

Second Advisor

Sriram Sankaranarayanan

Third Advisor

Christoffer Heckman

Fourth Advisor

Mark Moll

Fifth Advisor

Gabe Sibley


This thesis introduces new approaches to improve robotic motion planning by learning from past experiences especially suited for high-dimensional c-space with many invariant constraints. This experience-based motion planning (EBMP) paradigm reduces query resolution time, improves the quality of paths, and results in more predictable motions than typical probabilistic methods. Most previous approaches to motion planning have discarded past solution results and planned from scratch new solutions for every problem. A robot that is in operation for years will never get any better at its routine tasks. This thesis is novel in its focus on efficiently recalling previous motions the robot has performed and generalizing them to arbitrary new solutions even in the midst of changing obstacle environments.

Several key difficulties present themselves in the reuse of previous experiences: efficient storage given memory constraints, quick recall for new queries, verification given changing environments, and adaptation/repair. These challenges are largely addressed by the use of sparse roadmaps that provide theoretical guarantees for asymptotic-near optimality, and lazy collision checking which allows iterative search through a large roadmap of motions. Improved sparse roadmap data structures for experience storage are presented that are optimized for the L1-norm metric and large c-spaces. The trade-offs of full preprocessing of an experience roadmap for invariant constraints is studied.

These new approaches are applied to the high-dimensional problems of humanoid whole body manipulation, dual-arm shelf picking, and multi-modal underconstrained Cartesian planning. Experiments are implemented in the MoveIt! Motion Planning framework and takeaways from developing robot-agnostic motion planning software are presented. Experimental results show two orders of magnitude speedups for solving difficult motion planning problems.

Included in

Robotics Commons