General Algorithms for the Time-Optimal Trajectory Generation Problem
Stephen D. Butler · Rice Research Repository (Rice University) · 2017
As we ask robots to perform ever more sophisticated tasks, we must develop new algorithms capable of planning motions for these robots to follow. Current state-of-the-art humanoids and mobile manipulators generally operate under quasi-static assumptions. Ignoring dynamics during motion planning leads to highly sub-optimal trajectories. In turn, sub-optimal motion leads to higher requirements on robotic hardware such as increased weight, power consumption, and cost. Kinodynamic motion planning, which couples path planning with the dynamics of the robot, can create dynamically optimal trajectories. Unfortunately, kinodynamic motion planning is still intractable in the general case for high degree of freedom systems since including dynamics greatly increases the complexity of the motion planning search problem. This thesis presents two new algorithms which represent important steps toward closing the gap in general and efficient kinodynamic motion planning. The first algorithm solves the time-optimal path parameterization problem. The second algorithm can, given some range of starting velocities, generate all possible time-optimal trajectories for a given path by computing admissible velocity intervals (AVI). Solving the AVI problem generally and robustly is the first step toward a new generation of efficient kinodynamic motion planners which utilize the admissible velocity propagation (AVP) method. The algorithms presented improve on previous approaches by generically handling dynamics constraints. Through an exhaustive but efficient search, these new algorithms also eliminate the need for expert heuristics, which in prior methods were required to create the trajectory segments which form the final solution trajectory. The new algorithms presented in this thesis are simulated on a WAM arm with a Barret hand subject to dynamics constraints on joint torque, joint velocity, momentum, and end-effector velocity. Both algorithms are compared with a state-of-the-art alternative approach which they outperform in run-time and success rate.