An exact algorithm for kinodynamic planning in the plane


Journal Article

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 the L ∞ 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. © 1991 Springer-Verlag New York Inc.

Full Text

Duke Authors

Cited Authors

  • Canny, J; Rege, A; Reif, J

Published Date

  • December 1, 1991

Published In

Volume / Issue

  • 6 / 1

Start / End Page

  • 461 - 484

Electronic International Standard Serial Number (EISSN)

  • 1432-0444

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/BF02574702

Citation Source

  • Scopus