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

Abstract

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 ε (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.