Ph.D Dissertation Defense: Tobias Kunz

Title: Time-Optimal Sampling-Based Motion Planning for Manipulators with
Acceleration Limits

Date: Monday, March 9, 2015
Time: 11:15 am - 1:15 pm
Location: College of Computing Building, Room 345

Dr. Henrik Christensen (Advisor), School of Interactive Computing, Georgia
Dr. Andrea Thomaz, School of Interactive Computing, Georgia Tech
Dr. Karen Liu, School of Interactive Computing, Georgia Tech
Dr. Magnus Egerstedt, School of Electrical and Computer Engineering, Georgia
Dr. Steven LaValle, Department of Computer Science, University of Illinois
at Urbana-Champaign

Robot actuators have physical limitations in how fast they can change their
velocity. The more accurately planning algorithms consider these
limitations, the better the robot is able to perform.

Sampling-based algorithms have been successful in geometric domains, which
ignore actuator limitations. They are simple, parameter-free,
probabilistically complete and fast. Even though some algorithms like RRTs
were specifically designed for kinodynamic problems, which take actuator
limitations into account, they are less efficient in these domains or are,
as we show, not probabilistically complete.

A common approach to this problem is to decompose it, first planning a
geometric path and then time-parameterizing it such that actuator
constraints are satisfied. We improve the reliability of the latter step.
However, the decomposition approach can neither deal with non-zero start or
goal velocities nor provides an optimal solution.

We demonstrate that sampling-based algorithms can be extended to consider
actuator limitations in the form of acceleration limits while retaining the
same advantageous properties as in geometric domains. We present an
asymptotically optimal planner by combining a steering method with the RRT*
algorithm. In addition, we present hierarchical rejection sampling to
improve the efficiency of informed kinodynamic planning in high-dimensional