A provably good approximation algorithm for optimal-time trajectory planning

Abstract

The authors describe the first implementation of a good polynomial-time approximation algorithm for kinodynamic planning. Attention is given to the following problem: given a robot system, find a minimal-time trajectory from a start position and velocity to a goal position and velocity, while avoiding obstacles and respecting dynamic constraints on velocity and acceleration. From the class of approximate minimal-time trajectories for a given problem instance that the theoretical algorithm would find, the proposed implementation will find a trajectory with minimal useless chattering. In addition, the authors present an improved analysis of the accuracy of the approximation strength of this approach. This analysis reveals that the algorithm produces approximations good to a small additive error in state space and exact in time while only sacrificing the epsilon -approximation factor in safety, where epsilon is an error term. In addition, the analysis halves the polynomial complexity of the algorithm in (1/ epsilon ), and it provides a simple characterization of when the algorithm will find a trajectory that is exact at the start and goal.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>