A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and Maximum Constraints

S. D. Butler, M. Moll, and L. E. Kavraki, “A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and Maximum Constraints,” in Proceedings of Algorithmic Foundations of Robotics XII, 2020, vol. 13, pp. 368–383.

Abstract

This paper presents a new algorithm which generates time-optimal trajectories given a path as input. The algorithm improves on previous approaches by generically handling a broader class of constraints on the dynamics. It eliminates the need for heuristics to select trajectory segments that are part of the optimal trajectory through an exhaustive, but efficient search. We also present an algorithm for computing all achievable velocities at the end of a path given an initial range of velocities. This algorithm effectively computes bundles of feasible trajectories for a given path and is a first step toward a new generation of more efficient kinodynamic motion planning algorithms. We present results for both algorithms using a simulated WAM arm with a Barrett hand subject to dynamics constraints on joint torque, joint velocity, momentum, and end effector velocity. The new algorithms are compared with a state-of-the-art alternative approach.

Publisher: http://dx.doi.org/10.1007/978-3-030-43089-4_24

PDF preprint: http://kavrakilab.org/publications/butler2020.pdf