Skip to main content

On the complexity of kinodynamic planning

Publication ,  Journal Article
Canny, J; Reif, J; Donald, B; Xavier, P
Published in: Annual Symposium on Foundations of Computer Science (Proceedings)
January 1, 1988

The following problem, is considered: 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. The simplified case of a point mass under Newtonian mechanics together with velocity and acceleration bounds is considered. The point must be flown from a start to a goal, amid 2-D or 3-D polyhedral obstacles. While exact solutions to this problem are not known, the first provably good approximation algorithm is given and shown to run in polynomial time.

Duke Scholars

Published In

Annual Symposium on Foundations of Computer Science (Proceedings)

DOI

ISSN

0272-5428

Publication Date

January 1, 1988

Start / End Page

306 / 316
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Canny, J., Reif, J., Donald, B., & Xavier, P. (1988). On the complexity of kinodynamic planning. Annual Symposium on Foundations of Computer Science (Proceedings), 306–316. https://doi.org/10.1109/sfcs.1988.21947
Canny, J., J. Reif, B. Donald, and P. Xavier. “On the complexity of kinodynamic planning.” Annual Symposium on Foundations of Computer Science (Proceedings), January 1, 1988, 306–16. https://doi.org/10.1109/sfcs.1988.21947.
Canny J, Reif J, Donald B, Xavier P. On the complexity of kinodynamic planning. Annual Symposium on Foundations of Computer Science (Proceedings). 1988 Jan 1;306–16.
Canny, J., et al. “On the complexity of kinodynamic planning.” Annual Symposium on Foundations of Computer Science (Proceedings), Jan. 1988, pp. 306–16. Scopus, doi:10.1109/sfcs.1988.21947.
Canny J, Reif J, Donald B, Xavier P. On the complexity of kinodynamic planning. Annual Symposium on Foundations of Computer Science (Proceedings). 1988 Jan 1;306–316.

Published In

Annual Symposium on Foundations of Computer Science (Proceedings)

DOI

ISSN

0272-5428

Publication Date

January 1, 1988

Start / End Page

306 / 316