## 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 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.

### Duke Scholars

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 0802 Computation Theory and Mathematics
- 0103 Numerical and Computational Mathematics
- 0101 Pure Mathematics

### Citation

*Discrete & Computational Geometry*,

*6*(1), 461–484. https://doi.org/10.1007/BF02574702

*Discrete & Computational Geometry*6, no. 1 (December 1, 1991): 461–84. https://doi.org/10.1007/BF02574702.

*Discrete & Computational Geometry*, vol. 6, no. 1, Dec. 1991, pp. 461–84.

*Scopus*, doi:10.1007/BF02574702.

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 0802 Computation Theory and Mathematics
- 0103 Numerical and Computational Mathematics
- 0101 Pure Mathematics