Abstract
Inoptimal kinodynamic planning, given a robot system, we must find a minimal-time trajectory that goes from a start state to a goal state while avoiding obstacles by a speed-dependent safety margin and respecting dynamics bounds. With Canny and Reif [1], we approached this problem from anɛ-approximation standpoint and introduced a provably good approximation algorithm for optimal kinodynamic planning for a robot obeying particle dynamics. If a solution exists, this algorithm returns a trajectoryɛ-close to optimal in time polynomial in both (1/ɛ) and the geometric complexity.
We extend [1] and [2] tod-link three-dimensional robots with full rigid-body dynamics amidst obstacles. Specifically, we describe polynomial-time approximation algorithms for Cartesian robots obeyingL 2 dynamic bounds and for open-kinematic-chain manipulators with revolute and prismatic joints. The latter class includes many industrial manipulators. The correctness and complexity of these algorithms rely on new trajectory tracking lemmas for robots with coupled dynamics bounds.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Canny, B. Donald, J. Reif, and P. Xavier. On the complexity of kinodynamic planning.Proceedings of the 29th Annual Symposium on the Foundations of Computer Science, White Plains, New York, 1988, pp. 306–316.
B. Donald, P. Xavier, J. Canny, and J. Reif. Kinodynamic motion planning.Journal of the ACM,40(5), 1993, 1048–1066. Journal version of [1].
B. Donald and P. Xavier. Provably good approximation algorithms for optimal kinodynamic planning: robots with decoupled dynamics bounds.Algorithmica, this issue, pp. 443–479.
P. Xavier. Provably good approximation algorithms for optimal kinodynamic robot motion plans. Technical Report CUCS-TR92-1279, Computer Science Department, Cornell University, Ithaca, New York, April 1992. Ph.D. thesis.
B. Donald and P. Xavier. A provably good approximation algorithm for optimal-time trajectory planning.Proceedings of the 1989IEEE International Conference on Robotics and Automation, Scottsdale, Arizona, 1989, pp. 958–963.
P. Jacobs, G. Heinzinger, J. Canny, and B. Paden. Planning guaranteed near-time-optimal planning in a cluttered workspace. Technical Report ESRC 89-20/RAMP 89-15, Engineering Systems Research Center, University of California, Berkeley, California, October 1989.
P. Jacobs, G. Heinzinger, J. Canny, and B. Paden. Planning guaranteed near-time-optimal planning in a cluttered workspace.Proceedings of the International Workshop on Sensorial Integration for Industrial Robots: Architectures & Applications, Zaragoza, Spain, 1989.
G. Heinzinger, P. Jacobs, J. Canny, and B. Paden. Time-optimal trajectories for a robot manipulator: a provably good approximation algorithm.Proceedings of the 1990IEEE International Conference on Robotics and Automation, Cincinnati, Ohio, May 1990, pp. 150–155.
H. Asada and J. J. Slotine.Robot Analysis and Control. Wiley, New York, 1986.
J. M. Hollerbach. Dynamic scaling of manipulator trajectories. A.I. Memo 700, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1983.
T. Lozano-Pérez. Spatial planning: a configuration space approach.IEEE Transactions on Computers,32(2):108–120, 1983. Also A.I. Memo 605, Massachusetts Institute of Technology, Cambridge, Massachusetts, December 1982.
J. Canny. Collision detection for moving polyhedra.IEEE Transactions on Pattern Analysis and Machine Intelligence,8(2):200–209, 1986.
B. Donald. A search algorithm for motion planning with six degrees of freedom.Artificial Intelligence,31(3):295–353, 1987.
J. Canny and B. Donald. Simplified Voronoi diagrams.Discrete and Computational Geometry,3(3):219–236, 1988.
B. Donald and P. Xavier. Provably good approximation algorithms for optimal kinodynamic planning for cartesian robots and open chain manipulators.Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, California, June 1990, pp. 290–300.
B. Donald and P. Xavier. Near-optimal kinodynamic planning for robots with coupled dynamics bounds. In A. C. Sanderson, A. A. Derochers, and K. Valvanis, editors,Proceedings of the Fourth IEEE International Symposium on Intelligent Control, Albany, New York, 1989, pp. 354–359.
B. Donald and P. Xavier. Provably good approximation algorithms for optimal kinodynamic planning for cartesian robots and open chain manipulators. Technical Report TR-1095, Department of Computer Science, Cornell University, Ithaca, New York, February 1990. Supersedes TR-971.
J. Reif and S. Tate. Approximate kinodynamic planning usingl 2-norm dynamics bounds. Technical Report CS-1990-13, Department of Computer Science, Duke University, Durham, North Carolina, 1990.
Leitman.An Introduction to Optimal Control. McGraw-Hill, New York, 1966.
H. M. Schaettler. On the optimality of bang-bang trajectories in ℝ3.Bulletin of the American Mathematical Society,16(1):113–116, 1987.
E. Sontag and H. Sussmann. Remarks on the time-optimal control of two-link manipulators.Proceedings of the 24th Conference on Decision and Control, Ft. Lauderdale, Florida, 1985, pp. 1646–1652.
E. Sontag and H. Sussmann. Time-optimal control of manipulators. Technical Report, Department of Mathematics, Rutgers University, New Brunswick, New Jersey, 1986.
G. Heinzinger and B. Paden. Bounds on robot dynamics.Proceedings 1989IEEE International Conference on Robotics and Automation. Scottsdale, Arizona, 1989, pp. 1227–1232.
J. Canny.The Complexity of Robot Motion Planning. MIT Press, Cambridge, Massachusetts, 1988. Book version of Canny's 1986 Ph.D. thesis.
W. Press, B. Flannery, S. Teukolsky, and W. Vetterling.Numerical Recipes in C. Cambridge University Press, New York, 1988.
B. Donald and P. Xavier. Time-safety trade-offs and a bang-bang algorithm for kinodynamic planning.Proceedings of the 1991IEEE International Conference on Robotics and Automation, Sacramento, California, 1991, pp. 552–557.
Author information
Authors and Affiliations
Additional information
Communicated by J.-D. Boissonnat.
This paper describes research done at the Computer Science Robotics Laboratory at Cornell University. Support for our robotics research there is provided in part by the National Science Foundation under Grant Nos. IRI-8802390 and IRI-9000532, by a Presidential Young Investigator award, and in part by the Mathematical Sciences Institute, Intel Corporation, and AT&T Bell Laboratories.
Rights and permissions
About this article
Cite this article
Donald, B.R., Xavier, P.G. Provably good approximation algorithms for optimal kinodynamic planning for Cartesian robots and open-chain manipulators. Algorithmica 14, 480–530 (1995). https://doi.org/10.1007/BF01586637
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01586637