An exact algorithm for kinodynamic planning in the plane

Planning time-optimal motions has been a major focus of research in robotics. In this paper we consider the following problem: given an object in two-dimensional physical space, an initial point, and a final point, plan a time-optimal obstacle-avoiding motion for this object subject to bounds on the velocity and acceleration of the object. We give the first algorithm which solves the problem exactly in the case where the velocity and acceleration bounds are given in theL _∞ norm. We further prove the following important results: a tracking lemma and a loop-elimination theorem, both of which are applicable to the case of arbitrary norms. The latter result implies that, with or without obstacles, a path which intersects itself can be replaced by one which does not do so and which takes time less than or equal to that taken by the original path. The work of J. Canny and A. Rege was supported by NSF Grants IRI-89-58577 and IRI-90-14490 and by a David and Lucile Packard Fellowship. J. Reif's work was supported in part by DARPA/ARO Contract DAAL03-88-K-0185, Air Force Contract AFSOR-87-0386, ONR Contract N00014-K-0310, and DARPA/ISTO Contract N00014-88-K-0458.