This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Citation Map Services Email this article to a friend Similar articles in this journal Similar articles in ISI Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via HighWire Citing Articles via ISI Web of Science (31) Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by LaValle, S. M. Articles by Kuffner, J. J. Search for Related Content Social Bookmarking                   What's this?

Randomized Kinodynamic Planning

Department of Computer Science, Iowa State University, Ames, IA 50011lavalle{at}cs.iastate.edu

James J. Kuffner, Jr.

Department of Mechano-Informatics, University of Tokyo, Bunkyo-ku, Tokyo, Japankuffner{at}jsk.t.u-tokyo.ac.jp

This paper presents the first randomized approach to kinodynamic planning (also known as trajectory planning or trajectory design). The task is to determine control inputs to drive a robot from an ini ial configuration and velocity to a goal configuration and velocity while obeying physically based dynamical models and avoiding obstacles in the robot’s environment. The authors consider generic systems that express the nonlinear dynamics of a robot in terms of the robot’s high-dimensional configuration space. Kinodynamic planning is treated as a motion-planning problem in a higher dimensional state space that has both first-order differential constraints and obstacle-based global constraints. The state space serves the same role as the configuration space for basic path planning; however, standard randomized path-planning techniques do not directly apply to planning trajectories in the state space. The authors have developed a randomized planning approach that is particularly tailored to trajectory planning problems in high-dimensional state spaces. The basis for this approach is the construction of rapidly exploring random trees, which offer benefits that are similar to those obtained by successful randomized holonomic planning methods but apply to a much broader class of problems. Theoretical analysis of the algorithm is given. Experimental results are presented for an implementation that computes trajectories for hovercrafts and satellites in cluttered environments, resulting in state spaces of up to 12 dimensions.

Key Words: motion planning • trajectory planning • nonholonomic planning • algorithms • collision avoidance

The International Journal of Robotics Research, Vol. 20, No. 5, 378-400 (2001)
DOI: 10.1177/02783640122067453


CiteULike    Connotea    Del.icio.us    Digg    Reddit    Technorati    What's this?

This article has been cited by other articles:

				S. R. Lindemann and S. M. LaValle Simple and Efficient Algorithms for Computing Smooth, Collision-free Feedback Laws Over Given Cell Decompositions The International Journal of Robotics Research, May 1, 2009; 28(5): 600 - 621. [Abstract] [PDF]

				J. Kim, J. M. Esposito, and V. Kumar Sampling-based Algorithm for Testing and Validating Robot Controllers The International Journal of Robotics Research, December 1, 2006; 25(12): 1257 - 1272. [Abstract] [PDF]

				J. Peng and S. Akella Coordinating Multiple Robots with Kinodynamic Constraints Along Specified Paths The International Journal of Robotics Research, April 1, 2005; 24(4): 295 - 310. [Abstract] [PDF]

				C. Belta, J. M. Esposito, J. Kim, and V. Kumar Computational Techniques for Analysis of Genetic Network Dynamics The International Journal of Robotics Research, February 1, 2005; 24(2-3): 219 - 235. [Abstract] [PDF]

				A. M. Ladd and L. E. Kavraki Using Motion Planning for Knot Untangling The International Journal of Robotics Research, August 1, 2004; 23(7-8): 797 - 808. [Abstract] [PDF]

				J.C. Trinkle and R. J. Milgram Complete Path Planning for Closed Kinematic Chains with Spherical Joints The International Journal of Robotics Research, September 1, 2002; 21(9): 773 - 789. [Abstract] [PDF]