Provably good approximation algorithms for optimal kinodynamic planning for Cartesian robots and open-chain manipulators

Inoptimal kinodynamic planning, given a robot system, we must find 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-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-close to optimal in time polynomial in both (1/) and the geometric complexity.We extend [1] and [2] tod-link three-dimensional robots with full rigid-body dynamics amidst obstacles. Specifically, we describe polynomial-time approximation algorithms for Cartesian robots obeyingL₂ 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.This paper describes research done at the Computer Science Robotics Laboratory at Cornell University. Support for our robotics research there is provided in part by the National Science Foundation under Grant Nos. IRI-8802390 and IRI-9000532, by a Presidential Young Investigator award, and in part by the Mathematical Sciences Institute, Intel Corporation, and AT&T Bell Laboratories.