{"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":1767664459171},"reference-count":26,"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\/bf01586637","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T16:51:15Z","timestamp":1114707075000},"page":"480-530","source":"Crossref","is-referenced-by-count":28,"title":["Provably good approximation algorithms for optimal kinodynamic planning for Cartesian robots and open-chain manipulators"],"prefix":"10.1007","volume":"14","author":[{"given":"B. R.","family":"Donald","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P. G.","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"},{"issue":"5","key":"CR2","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":"CR3","doi-asserted-by":"crossref","unstructured":"B. Donald and P. Xavier. Provably good approximation algorithms for optimal kinodynamic planning: robots with decoupled dynamics bounds.Algorithmica, this issue, pp. 443\u2013479.","DOI":"10.1007\/BF01586636"},{"key":"CR4","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":"CR5","doi-asserted-by":"crossref","unstructured":"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\u2013963.","DOI":"10.1109\/ROBOT.1989.100104"},{"key":"CR6","volume-title":"Technical Report ESRC 89-20\/RAMP 89-15","author":"P. Jacobs","year":"1989","unstructured":"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."},{"key":"CR7","unstructured":"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."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"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\u2013155.","DOI":"10.1109\/ROBOT.1990.125963"},{"key":"CR9","volume-title":"Robot Analysis and Control","author":"H. Asada","year":"1986","unstructured":"H. Asada and J. J. Slotine.Robot Analysis and Control. Wiley, New York, 1986."},{"key":"CR10","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."},{"issue":"2","key":"CR11","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):108\u2013120, 1983. Also A.I. Memo 605, Massachusetts Institute of Technology, Cambridge, Massachusetts, December 1982.","journal-title":"IEEE Transactions on Computers"},{"issue":"2","key":"CR12","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):200\u2013209, 1986.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"3","key":"CR13","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0004-3702(87)90069-5","volume":"31","author":"B. Donald","year":"1987","unstructured":"B. Donald. A search algorithm for motion planning with six degrees of freedom.Artificial Intelligence,31(3):295\u2013353, 1987.","journal-title":"Artificial Intelligence"},{"issue":"3","key":"CR14","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):219\u2013236, 1988.","journal-title":"Discrete and Computational Geometry"},{"key":"CR15","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.Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, California, June 1990, pp. 290\u2013300.","DOI":"10.1145\/98524.98594"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"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\u2013359.","DOI":"10.1109\/ISIC.1989.238674"},{"key":"CR17","series-title":"Supersedes 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. Supersedes TR-971."},{"key":"CR18","volume-title":"Technical Report CS-1990-13","author":"J. Reif","year":"1990","unstructured":"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."},{"key":"CR19","volume-title":"An Introduction to Optimal Control","author":"Leitman","year":"1966","unstructured":"Leitman.An Introduction to Optimal Control. McGraw-Hill, New York, 1966."},{"issue":"1","key":"CR20","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):113\u2013116, 1987.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"CR21","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":"CR22","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":"CR23","doi-asserted-by":"crossref","unstructured":"G. Heinzinger and B. Paden. Bounds on robot dynamics.Proceedings 1989IEEE International Conference on Robotics and Automation. Scottsdale, Arizona, 1989, pp. 1227\u20131232.","DOI":"10.1109\/ROBOT.1989.100148"},{"key":"CR24","volume-title":"Book version of Canny's 1986 Ph.D. thesis","author":"J. Canny","year":"1988","unstructured":"J. Canny.The Complexity of Robot Motion Planning. MIT Press, Cambridge, Massachusetts, 1988. Book version of Canny's 1986 Ph.D. thesis."},{"key":"CR25","volume-title":"Numerical Recipes in C","author":"W. Press","year":"1988","unstructured":"W. Press, B. Flannery, S. Teukolsky, and W. Vetterling.Numerical Recipes in C. Cambridge University Press, New York, 1988."},{"key":"CR26","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 1991IEEE International Conference on Robotics and Automation, Sacramento, California, 1991, pp. 552\u2013557.","DOI":"10.1109\/ROBOT.1991.131638"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01586637.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01586637\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01586637","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T04:13:59Z","timestamp":1586232839000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01586637"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["BF01586637"],"URL":"https:\/\/doi.org\/10.1007\/bf01586637","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}