Publications [#237069] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Canny, J; Reif, J; Donald, B; Xavier, P, On the complexity of kinodynamic planning, Annual Symposium on Foundations of Computer Science Proceedings (January, 1988), pp. 306-316 [doi]
   (last updated on 2026/01/14)

   Abstract:
   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.