Kinodynamic motion planning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Kinodynamic motion planning

Full text

Pdf (1.18 MB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 5 (November 1993) table of contents

Pages: 1048 - 1066

Year of Publication: 1993

ISSN:0004-5411

Authors

Bruce Donald	Cornell University, Ithaca, New York
Patrick Xavier	Cornell University, Ithaca, New York
John Canny	University of California at Berkeley, Berkeley, California
John Reif	Duke University, Durham, North Carolina

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 81, Citation Count: 9

Additional Information:

references cited by index terms reviews collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/174147.174150 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	~BOBROW, J., DUBOWSKY, S., AND GIBSON, J. Time-optimal control of robot manipulators. Int. ~J. Robotics Res. 4, 3 (1985).
	2	Michale Brady , John M. Hollerbach , Timothy L. Johnson , Matthew T. Mason , Tomas Lozano-Perez, Robot Motion: Planning and Control, MIT Press, Cambridge, MA, 1983
	3	J Canny, Collision detection vkr moving polyhedra, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.2, p.200-209, March 1986 [doi>10.1109/TPAMI.1986.4767773]
	4	~CANNY, J., DONALD, B., REIF, J., AND XAVIER, P. On the complexity of kinodynamic ~planning. In Proceedings of the 29th Symposium on the Foundations of Computer Science ~(White Plains, N.Y.). 1EEE, New York, 1988.
	5	John Canny , Ashutosh Rege , John Reif, An exact algorithm for kinodynamic planning in the plane, Proceedings of the sixth annual symposium on Computational geometry, p.271-280, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98584]
	6	~CANNY, J., AND REIF, J. New lower bound techniques for robot motion planning. In ~Proceedings of the 28th $?mposlurn on the Foundations of Computer Science (Los Angeles, ~Calif.). IEEE, New York, 1987.
	7	~DONALD, B., AND XAVIER, P. A provably good approximation algorithm for optimal-time ~trajectory planning. In 1EEE International Conference on Robotics and Automatton (Scottsdale, ~Az.). IEEE, New York, 1989, pp. 958-964.
	8	~DONALD, B., AND XAVIER, P. Near-optimal kinodynamlc planning for robots with coupled ~dynamics bounds. In Proceedings of the 4th IEEE International Symposium on Intelligent ~Control (Albany, N.Y.). IEEE, New York, 1989, 354-359.
	9	Bruce R. Donald , Patrick G. 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, p.290-300, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98594]
	10	~DONALD, B., AND XAVIER, P. Provably good approximation algorithms for optimal kino- ~dynamic planning: Robots with decoupled dynamics bounds. Algorithmica, in press.
	11	~DONALD, B., AND XAVIER, P. Provably good approximation algorithms for optimal kino- ~dynamic planning for Cartesian robots and open chain manipulators. Algorithmwa, in press.
	12	Steven Fortune , Gordon Wilfong, Planning constrained motion, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.445-459, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62256]
	13	~HOLLERBACH, J.M. Dynamic scaling of manipulator trajectories. MIT A.I. Lab Memo 700. ~MIT, Cambridge, Mass., 1983.
	14	~JACOBS, P., HE1NZINGER, G., CANNY, J., AND PADEN, B. Planning guaranteed near-time-opti- ~mal planning in a cluttered workspace. In Proceedings of the hlternational Workshop on ~Sensorzal Integration for hldustrial Robots: Archttectures& Apphcatlons (Zaragoza, Spain). 1989.
	15	~LOZANO-PI2REZ, T. Spatial planning: A configuration space approach. IEEE Trans. Compztt. ~C-32 (1983), 108-120.
	16	~6'DI~INLAING, C. Motion planning with inertial constraints. NYU Robotics Laboratory, TR ~230. New York Univ., New York, 1986.
	17	~PAPADIMITRIOU, C. An algorithm for shortest path motion in three dimensions. Inf. Proc. ~Lett. 20 (1985), 259-263.
	18	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	19	John Reif , Stephen Tate, Approximate Kinodynamic Planning Using L2-norm Dynamic Bounds, Duke University, Durham, NC, 1990
	20	~SAHAR, G.~ AND HOLLERBACH, J. Planning of minimum-time trajectories for robot arms. In ~IEEE International Collference on Robotics and Automation (St. Louis, Mo.). IEEE, New York, ~1985.
	21	~SCI-IAETTLER, H. M. On the optimality of bang-bang trajectories in !~i~. Bull AMS 16, 1 ~(1987), 113-116.
	22	~SmLLER, Z., AND DUBOWSKY, S. Global time-optimal motions of robotic manipulators in the ~presence of obstacles. In Proceedings of the {EEE International Conference on Robotzcs and ~Automation (Philadelphia, Pa.). IEEE, New York, 1988.
	23	~SONTAG, E., AND SUSSMANN, H. Remarks on the time-optimal control of two-hnk manipula- ~tors. In Proceedings of the 24th Conference of~ Deciszon and Control (Ft. Lauderdale, Fla.). ~1985.
	24	~SONTAG, E., AND SUSSMANN, H. Time-optimal control of manipulators. Tech. Rep. Dept. ~Mathematics. Rutgers Univ., New Brunswick. N.J., 1986.
	25	~WILFONG, G. Motion planning for an autonomous vehicle. In Proceedings of the 1EEE ~bzternatzonal Conference on Robotics and A,tomatton (Philadelphia, PaD. IEEE, New York, ~1988.
	26	Patrick Gordon Xavier, Provably-good approximation algorithms for optimal kinodynamic robot motion plans, Cornell University, Ithaca, NY, 1992
	27	~YAP, C. Algorithmic motion planning. In AdL,ances tn Robottcs: Vol. 1, J. Schwartz and ~C. Yap, eds. Lawrence Erlbaum Associates, Hillsdale, N.J., 1986.

CITED BY 9

	P. S. A. Reitsma , N. S. Pollard, Evaluating motion graphs for character navigation, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France
	Michael S. Gudaitis , Gary B. Lamont , Andrew J. Terzuoli, Multicriteria vehicle route-planning using parallel A * search, Proceedings of the 1995 ACM symposium on Applied computing, p.171-176, February 26-28, 1995, Nashville, Tennessee, United States
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	Jovan Popović , Steven M. Seitz , Michael Erdmann , Zoran Popović , Andrew Witkin, Interactive manipulation of rigid body simulations, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.209-217, July 2000
	Jufeng Peng , Srinivas Akella, Coordinating Multiple Robots with Kinodynamic Constraints Along Specified Paths, International Journal of Robotics Research, v.24 n.4, p.295-310, April 2005
	Paul S. A. Reitsma , Nancy S. Pollard, Evaluating motion graphs for character animation, ACM Transactions on Graphics (TOG), v.26 n.4, p.18-es, October 2007
	Jongwoo Kim , Joel M. Esposito , Vijay Kumar, Sampling-based Algorithm for Testing and Validating Robot Controllers, International Journal of Robotics Research, v.25 n.12, p.1257-1272, December 2006
	Kostas E. Bekris , Konstantinos I. Tsianos , Lydia E. Kavraki, A distributed protocol for safe real-time planning of communicating vehicles with second-order dynamics, Proceedings of the 1st international conference on Robot communication and coordination, October 15-17, 2007, Athens, Greece
	David C. Conner , Howie Choset , Alfred A. Rizzi, Flow-through policies for hybrid controller synthesis applied to fully actuated systems, IEEE Transactions on Robotics, v.25 n.1, p.136-146, February 2009

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
G. Mathematics of Computing
G.1 NUMERICAL ANALYSIS
G.2 DISCRETE MATHEMATICS

I. Computing Methodologies
I.2 ARTIFICIAL INTELLIGENCE
I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Performance, Reliability

Keywords:
approximation, computational geometry, dynamics, optimal control, robotics, shortest path

REVIEWS

"Franz Winkler : Reviewer"

The paper clearly deals with an important problem in robot motion planning, in which both kinematic (joint limitations and obstacles) and dynamic (velocity and acceleration) constraints have to be obeyed by a robot moving from a starting posit more...

"Bruce Randall Donald : Reviewer"

Our paper develops a polynomial-time approximation scheme (PTAS). A PTAS produces a solution that is e -close to the optimal solution T , and runs i more...

Collaborative Colleagues:

Bruce Donald: colleagues

Patrick Xavier: colleagues

John Canny: colleagues

John Reif: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player