Near-optimal kinodynamic planning for robots with coupled dynamics bounds

The authors 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 safety margin and respecting bounds on velocity and generalized forces. A provably good polynomial-time approximation algorithm for this problem is one for which it is possible to (1) bound the goodness of the approximate solution it produces by an error term epsilon ; (2) polynomially bound the running time (complexity) of the algorithm; and (3) express the complexity as a polynomial function of 1/ epsilon . Using a new trajectory tracking lemma for robots with coupled dynamics bounds and a generalization of the basic algorithm of J. Canny et al. (1988), the authors describe provably good polynomial-time approximation algorithms for nonrotating robots obeying L/sub 2/ dynamics bounds and for open-chain manipulators. These algorithms only consider near-extremal accelerations, thus the out-degree complexity of the search is lower than that of the earlier provably good polynomial-time approximation algorithm of P. Jacobs et al. (1989) for open-chain manipulators.<>