{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T01:54:19Z","timestamp":1767664459347,"version":"3.32.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1995,12,1]],"date-time":"1995-12-01T00:00:00Z","timestamp":817776000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,12]]},"DOI":"10.1007\/bf01586636","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T16:51:15Z","timestamp":1114707075000},"page":"443-479","source":"Crossref","is-referenced-by-count":35,"title":["Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds"],"prefix":"10.1007","volume":"14","author":[{"given":"B. R.","family":"Donald","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Xavier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"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\u2013316.","DOI":"10.1109\/SFCS.1988.21947"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"J. Canny, A. Rege, and J. Reif, An exact algorithm for kinodynamic planning in the plane,Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, California, 1990, pp. 271\u2013280.","DOI":"10.1145\/98524.98584"},{"key":"CR3","series-title":"Technical Report CUCS-TR92-1279","volume-title":"Ph.D. thesis","author":"P. Xavier","year":"1992","unstructured":"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."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"J. Canny and J. Reif, New lower bound techniques for robot motion planning,Proceedings of the 28th Annual Symposium on the Foundations of Computer Science, Los Angeles, California, 1987.","DOI":"10.1109\/SFCS.1987.42"},{"issue":"5","key":"CR5","doi-asserted-by":"crossref","first-page":"1048","DOI":"10.1145\/174147.174150","volume":"40","author":"B. Donald","year":"1993","unstructured":"B. Donald, P. Xavier, J. Canny, and J. Reif, Kinodynamic motion planning,Journal of the ACM,40(5), 1993, 1048\u20131066. Journal version of [1].","journal-title":"Journal of the ACM"},{"key":"CR6","series-title":"Supercedes TR-971","volume-title":"Technical Report TR-1095","author":"B. Donald","year":"1990","unstructured":"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. Supercedes TR-971."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"B. Donald and P. Xavier, Provably good approximation algorithms for optimal kinodynamic planning for Cartesian robots and open-chain manipulators,Algorithmica, this issue, pp. 480\u2013530.","DOI":"10.1007\/BF01586637"},{"key":"CR8","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C. H. Papadimitriou","year":"1982","unstructured":"C. H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, New Jersey, 1982."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0020-0190(85)90029-8","volume":"20","author":"C. H. Papadimitriou","year":"1985","unstructured":"C. H. Papadimitriou, An algorithm for shortest path motion in three dimensions,Information Processing Letters,20, 1985, 259\u2013263.","journal-title":"Information Processing Letters"},{"volume-title":"Robot Motion: Planning and Control","year":"1982","key":"CR10","unstructured":"M. Brady, J. Hollerbach, T. Johnson, T. Lozano-P\u00e9rez, and M. Mason, editors,Robot Motion: Planning and Control. MIT Press, Cambridge, Massachusetts, 1982."},{"key":"CR11","volume-title":"Advances in Robotics, Volume 1","author":"C. Yap","year":"1986","unstructured":"C. Yap, Algorithmic motion planning. In J. Schwartz and C. Yap, editors,Advances in Robotics, Volume 1. Erlbaum, Hillsdale, New Jersey, 1986."},{"key":"CR12","volume-title":"A.I. Memo 700","author":"J. M. Hollerbach","year":"1983","unstructured":"J. M. Hollerbach, Dynamic scaling of manipulator trajectories. A.I. Memo 700, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1983."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"J. Bobrow, S. Dubowsky, and J. Gibson, Time-optimal control of robot manipulators along specified paths,International Journal of Robotics Research,4(3), 1985.","DOI":"10.1177\/027836498500400301"},{"issue":"1","key":"CR14","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1090\/S0273-0979-1987-15479-6","volume":"16","author":"H. M. Schaettler","year":"1987","unstructured":"H. M. Schaettler, On the optimality of bang-bang trajectories in \u211d3,Bulletin of the American Mathematical Society,16(1), 1987, 113\u2013116.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"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\u20131652.","DOI":"10.1109\/CDC.1985.268795"},{"key":"CR16","volume-title":"Technical Report","author":"E. Sontag","year":"1986","unstructured":"E. Sontag and H. Sussmann, Time-optimal control of manipulators. Technical Report, Department of Mathematics, Rutgers University, New Brunswick, New Jersey, 1986."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"G. Sahar and J. Hollerbach, Planning of minimum-time trajectories for robot arms,Proceedings of the 1985 IEEE International Conference on Robotics and Automation, St. Louis, Missouri, 1985, pp. 751\u2013758.","DOI":"10.1109\/ROBOT.1985.1087233"},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"Z. Shiller and S. Dubowsky, Global time-optimal motions of robotic manipulators in the presence of obstacles,Proceedings of the 1988 IEEE International Conference on Robotics and Automation, Philadelphia, Pennsylvania, 1988, pp. 370\u2013375.","DOI":"10.1109\/ROBOT.1988.12076"},{"issue":"4","key":"CR19","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/BF01840370","volume":"2","author":"C. \u00d3'D\u00fanlaing","year":"1987","unstructured":"C. \u00d3'D\u00fanlaing, Motion planning with inertial constraints,Algorithmica,2(4), 1987, 431\u2013475.","journal-title":"Algorithmica"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"S. Fortune and G. Wilfong, Planning constrained motion,Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, Chicago, Illinois, 1988, pp. 445\u2013459.","DOI":"10.1145\/62212.62256"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"G. Wilfong, Motion planning for an autonomous vehicle,Proceedings of the 1988 IEEE International Conference on Robotics and Automation, Philadelphia, Pennsylvania, 1988, pp. 529\u2013533.","DOI":"10.1109\/ROBOT.1988.12106"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"P. Jacobs and J. Canny, Planning smooth paths for mobile robots,Proceedings of the 1989 IEEE International Conference on Robotics and Automation, Scottsdale, Arizona, 1989, pp. 2\u20137.","DOI":"10.1109\/ROBOT.1989.99959"},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"B. Donald and P. Xavier, Time-safety trade-offs and a bang-bang algorithm for kinodynamic planning,Proceedings of the 1991 IEEE International Conference on Robotics and Automation, Sacramento, California, 1991, pp. 552\u2013557.","DOI":"10.1109\/ROBOT.1991.131638"},{"issue":"2","key":"CR24","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1109\/TC.1983.1676196","volume":"32","author":"T. Lozano-P\u00e9rez","year":"1983","unstructured":"T. Lozano-P\u00e9rez, Spatial planning: a configuration space approach,IEEE Transactions on Computers,32(2), 1983, 108\u2013120. Also A.I. Memo 605, Massachusetts Institute of Technology, Cambridge, Massachusetts, December 1982.","journal-title":"IEEE Transactions on Computers"},{"key":"CR25","volume-title":"EATCS 10","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner,Algorithms in Combinatorial Geometry. EATCS 10. Springer-Verlag, Berlin, 1987."},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"L. Guibas and R. Seidel, Computing convolutions by reciprocal search,Proceedings of the 4th ACM Symposium on Computational Geometry, Urbana, Illinois, 1988, pp. 90\u201399.","DOI":"10.1145\/10515.10525"},{"issue":"2","key":"CR27","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1109\/TPAMI.1986.4767773","volume":"8","author":"J. Canny","year":"1986","unstructured":"J. Canny, Collision detection for moving polyhedra,IEEE Transactions on Pattern Analysis and Machine Intelligence,8(2), 1986, 200\u2013209.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"3","key":"CR28","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF02187909","volume":"3","author":"J. Canny","year":"1988","unstructured":"J. Canny and B. Donald, Simplified Voronoi diagrams,Discrete and Computational Geometry,3(3), 1988, 219\u2013236.","journal-title":"Discrete and Computational Geometry"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01586636.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01586636\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01586636","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,31]],"date-time":"2024-12-31T23:48:11Z","timestamp":1735688891000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01586636"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["BF01586636"],"URL":"https:\/\/doi.org\/10.1007\/bf01586636","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}