provably good approximation algorithms for optimal kinodynamic planning for cartesian robots and open chain manipulators
We consider the following problem: given a robot system, find a minimal-time trajectory from a start state to a goal state, while avoiding obstacles by a speed-dependent safety margin and respecting dynamics bounds. In [CDRX] we developed a provably good approximation algorithm for the minimum-time trajectory problem for a robot system with decoupled dynamics bounds. This algorithm differed from previous work in three ways: it is possible (1) to bound the goodness of the approximation by an error term &egr; (2) to polynomially bound the running time (complexity) of our algorithm; and (3) to express the complexity as a polynomial function of the error term. We extend these results to d -link, revolute-joint 3D robots will full rigid body dynamics. Specifically, we first prove a generalized trajectory-tracking lemma for robots with coupled dynamics bounds. Using this result we describe polynomial-time approximation algorithms for Cartesian robots obeying L 2 dynamics bounds and open kinematic chain manipulators with revolute and prismatic joints; the latter class includes most industrial manipulators. We obtain a general &Ogr; ( n 2 (log n )(1/&egr; 6 d -1 ) algorithm, where n is the geometric complexity. The algorithm is simple, but the new game-theoretic proof techniques we introduce are subtle, and employ tools from disparate parts of computational geometry, robotics, and dynamical systems.
approximation algorithms approximation algorithm optimality dynamic plan robotics manipulation systems trajectories errors polynomial timing complexity functional 3d general class industrial log tools computational geometry dynamic system game time complexity linking minimal dependencies tracking