Provably Good Approximation Algorithms for Optimal Kinodynamic Planning: Robots with Decoupled Dynamics Bounds

: We consider the following problem: given a robot system, 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. In [1] we developed a provably good approximation algorithm for the minimum-time trajectory problem for a robot system with decoupled dynamics bounds (e.g., a point robot in R 3 ). This algorithm differs from previous work in three ways. It is possible (1) to bound the goodness of the approximation by an error term ffl; (2) to polynomially bound the computational complexity of our algorithm; and (3) to express the complexity as a polynomial function of the error term. Hence, given the geometric obstacles, dynamics bounds, and the error term ffl, the algorithm returns a solution that is ffl-close to optimal and requires only a polynomial (in ( 1 ffl )) amount of time. We extend the results of [1] in two ways. First, we modify it to halve the exponent in the p..