PROVABLY GOOD APPROXIMATION ALGORITHMS FOR OPTIMAL KINODYNAMIC PLANNING FOR CARTESIAN ROBOTS AND OPEN-CHAIN MANIPULATORS

In optimal kinodynamic planning, given a robot system, we must fmd a minimal-time trajectory that goes from a start state to a goal state while avoiding obstacles by a speed-dependent safety margin and respecting dynamics bounds. With Canny and Reif [1], we approached this problem from an E-approximation standpoint and introduced a provably good approximation algorithm for optimal kinodynamic planning for a robot obeying particle dynamics. If a solution exists, this algorithm returns a trajectory E-close to optimal in time polynomial in both (1/epsilon) and the geometric complexity. We extend [1] and [2] to d-link three-dimensional robots with full rigid-body dynamics amidst obstacles. Specifically, we describe polynomial-time approximation algorithms for Cartesian robots obeying L(2) dynamic bounds and for open-kinematic-chain manipulators with revolute and prismatic joints. The latter class includes many industrial manipulators. The correctness and complexity of these algorithms rely on new trajectory tracking lemmas for robots with coupled dynamics bounds.