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 epsilon; (2) to bound the computational complexity of our algorithm polynomially; 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 epsilon, the algorithm returns a solution that is epsilon-close to optimal and requires only a polynomial (in (1/epsilon)) amount of time. We extend the results of [1] in two ways. First, we modify it to halve the exponent in the polynomial bounds from 6d to 3d, so that the new algorithm is O(c(d)N(1/epsilon)(3d)), where N is the geometric complexity of the obstacles and c is a robot-dependent constant. Second, the new algorithm finds a trajectory that matches the optimal in time with an epsilon factor sacrificed in the obstacle-avoidance safety margin. Similar results hold for polyhedral Cartesian manipulators in polyhedral environments. The new results indicate that an implementation of the algorithm could be reasonable, and a preliminary implementation has been done for the planar case.