RRT-based trajectory design for autonomous automobiles and spacecraft

• Autorzy: Cheng P. , Shen Z. , LaValle S.
• Języki publikacji: EN

Abstrakty

EN

This paper considers the design of open loop control laws for nonlinear systems that are subject to nonconvex state space constraints. The focus is on finding feasible trajectories for two challenging sets of nonlinear systems: 1) the determination of automobile trajectories through obstacle courses; 2) the design of re-entry trajectories for a reusable launch vehicle model based on the NASA X33 prototype. Our algorithms are based on rapidly-exploring random trees (RRTs) that incrementally explore the state space while satisfying both the global constraints imposed by obstacles and velocity bounds and differential constraints imposed by the equations of motion. The method is particularly suited for high-dimensional problems in which classical numerical approaches such as dynamic programming cannot be applied in practice. Our algorithms for trajectory design have been implemented and evaluated on several challenging examples, which are presented in the paper.

Słowa kluczowe

EN

trajectory planning; motion planning; nonlinear systems; robotics; algorithms

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2001
• Tom: Vol. 11, no. 3/4
• Strony: 167--194
• Opis fizyczny: Bibliogr. 51 poz., rys., wzory

Twórcy

autor

Cheng P.

• Dept. of Computer Science, 1304 W. Springfield Ave., University of Illinois, Urbana, IL, 61801, USA

autor

Shen Z.

• Dept. of Aerospace Engineering and Engineering Mechanics, 2271 Howe Hall, Iowa State University, Ames, IA 50011, USA

autor

LaValle S.

• Dept. of Computer Science, 1304 W. Springfield Ave., University of Illinois, Urbana, IL, 61801, USA

Bibliografia

• [1] N. M. Amato and Y. Wu: A randomized roadmap method for path and manipulation planning. Proc. IEEE Int. Conf. on Robotics and Automation, (1996), 113-120.
• [2] S. Arya and D. M. Mount: Approximate nearest neihgbor queries in fixed dimensions. Proc. ACM-SIAM Symp. on Discrete Algorithms, (1993), 271-280.
• [3] S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu: An optimal algorithm for approximate nearest neighbor searching. J. of the ACM, 45 (1998), 891-923.
• [4] J. Barraquand, B. Langlois, and J. C. Latombe: Numerical potential field techniques for robot path planning. IEEE Trans. on Systems, Man and Cybernetics, 22(2), (1992), 224-241.
• [5] J. Barraquand and J.-C. Latombe: Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles. Algorithmica, 10 (1993), 121-155.
• [6] J. Bernard, J. Shannan, and M. Vanderploeg: Vehicle rollover on smooth surfaces. Proc. SAE Passenger Car Meeting and Exposition, Dearborn, Michigan, (1989).
• [7] J. T. Betts: Survey of numerical methods for trajectory optimization. J. of Guidance, Control, and Dynamics, 21(2), (1998), 193-207.
• [8] V. Boor, N. H. Overmars, and A. F. Van Der Stappen: The gaussian sampling strategy for probabilistic roadmap planners. Proc. IEEE Int. Conf. on Robotics and Automation, (1999), 1018-1023.
• [9] A. E. Bryson and Y.-C. Ho: Applied Optimal Control. Hemisphere Publishing Corp., New York, NY, 1975.
• [10] J. Canny, A. Rege, and J. Reif: An exact algorithm for kinodynamic planning in the plane. Discrete and Computational Geometry, 6 (1991), 461-484.
• [11] J. F. Canny: The Complexity of Robot Motion Planning. MIT Press, Cambridge, MA, 1988.
• [12] P. Cheng and S. M. Lavalle: Resolution complete rapidly-exploring random trees. Submitted to IEEE Int. Conf. on Robotics and Automation, (2002).
• [13] M. Cherif: Kinodynamic motion planning for all-terrain wheeled vehicles. Proc. IEEE Int. Conf. on Robotics and Automation, (1999).
• [14] C. Connolly, R. Grupen, and K. Souccar: A Hamiltonian framework for kinodynamic planning. Proc. IEEE Int. Conf. on Robotics and Automation, (1995).
• [15] B. Donald and P. Xavier: Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds. Algorithmica, 14(6), (1995), 443-479.
• [16] B. R. Donald, P. G. Xavier, J. Canny, and J. Reif: Kinodynamic planning. J. of the ACM, 40 (1993), 1048-1066.
• [17] L. E. Dubins: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American J. of Mathematics, 79 (1957), 497-516.
• [18] TH. Fraichard and C. Laugier: Kinodynamic planning in a structured and time-varying 2d workspace. Proc. IEEE Int. Conf. on Robotics and Automation, (1992), 1500-1505.
• [19] E. Frazzoli, M. A. Dahleh, and E. Feron: Robust hybrid control for autonomous vehicles motion planning. Technical Report LIDS-P-2468, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 1999.
• [20] J. H. Friedman, J. L. Bentley, and R.A. Finkel: An algorithm for finding best matches in logarithmic expected time. ACM Trans. on Mathematical Software, 3(3), (1977), 209-226.
• [21] L. J. Guibas, D. Hsu, and L. Zhang: H-Walk: Hierarchical distance computation for moving convex bodies. Proc. ACM Symp. on Computational Geometry, (1999), 265-273.
• [22] D. Hsu, L. E. Kavraki, J.-C. Latombe, R. Motwani, and S. Sorkin: On finding narrow passages with probabilistic roadmap planners. In: Robotics: The Algorithmic Perspective, P. Agarwal (Ed), A.K. Peters, Wellesley, MA, 1998, 141- 154.
• [23] D. Hsu, J.-C. Latombe, and R. Motwani: Path planning in expansive configuration spaces. Int. J. of Computational Geometry and Applications, 4 (1999), 495-512.
• [24] P. Indyk and R. Motwani: Approximate nearest neighbors: Towards removing the curse of dimensionality. Proc. 30th Annual ACM Symposium on Theory of Computing, (1998), 604-613.
• [25] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. on Robotics and Automation, 12(4), (1996), 566-580.
• [26] R. Kindel, D. Hsu, J.-C. Latombe, and S. Rock: Kinodynamic motion planning amidst moving obstacles. Proc. IEEE Int. Conf. on Robotics and Automation, (2000).
• [27] J. M. Kleinberg: Two algorithms for nearest-neighbor search in high dimensions. ACM Symp. on Theory of Computing, (1997), 599-608.
• [28] J. J. Kuffner and S. M. Lavalle: RRT-connect: An efficient approach to single-query path planning. Proc. IEEE Int. Conf. on Robotics and Automation, (2000).
• [29] J.-C. Latombe: A fast path planner for a car-like indoor mobile robot. Proc. Am. Assoc. Artif. Intell., (1991), 659-665.
• [30] J.-C. Latombe: Robot Motion Planning. Kluwer Academic Publishers, Boston, MA, 1991.
• [31] J.-P. Laumond: Finding collision-free smooth trajectories for a non-holonomic mobile robot. Proc. Int. Joint Conf. on Artificial Intelligence, (1987), 1120-1123.
• [32] J. P. Laumond, S. Sekhavat, and F. Lamiraux: Guidelines in nonholonomic motion planning for mobile robots. In: Robot Motion Plannning and Control, J.-P. Laumond, (Ed), Springer-Verlag, Berlin, (1998), 1-53.
• [33] S. M. Lavalle: Rapidly-exploring random trees: A new tool for path planning. TR 98-11, Computer Science Dept., Iowa State University, 1998.
• [34] S. M. Lavalle and J. J. Kuffner: Randomized kinodynamic planning. Proc. IEEE Int. Conf. on Robotics and Automation, (1999), 473-479.
• [35] S. M. Lavalle and J. J. Kuffner: Rapidly-exploring random trees: Progress and prospects. In: Algorithmic and computational robotics: New directions. B.R. Donalds, K.M. Lynch and D. Rus (Eds), A.K. Peters, (2001), 293-308.
• [36] S. M. Lavalle and J. J. Kuffner: Randomized kinodynamic planning. Int. J. of Robotics Research, 20(5), (2001), 378-400.
• [37] M. C. Lin and J. F. Canny: Efficient algorithms for incremental distance computation. Proc. IEEE Int. Conf. on Robotics and Automation, (1991).
• [38] P. Lu and J. M. Hanson: Entry guidance for the X-33 vehicle. J. Spacecraft and Rockets, 35(3), (1998), 342-349.
• [39] E. Mazer, G. Talbi, J. M. Ahuactzin, and P. Bessière: The Ariadne’s clew algorithm. Proc. Int. Conf. on Society of Adaptive Behavior, Honolulu, (1992).
• [40] G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis: Separators for sphere-packings and nearest neighbor graphs. J. of the ACM, 44(1), (1997), 1-29.
• [41] B. Mirtich: V-Clip: Fast and robust polyhedral collision detection. Technical Report TR97-05, Mitsubishi Electronics Research Laboratory, 1997.
• [42] R. M. Murray and S. Sastry: Nonholonomic motion planning: Steering using sinusoids. IEEE Trans. on Automatic Control, 38(5), (1993), 700-716.
• [43] C. O’dunlaing and C. K. Yap: A retraction method for planning the motion of a disc. J. of Algorithms, 6 (1982), 104-111.
• [44] M. H. Overmars and J. Van Leeuwen: Dynamic multidimensional data structures based on Quad- and K-D trees. Acta Informatica, 17 (1982), 267-285.
• [45] I. Pohl: Bi-directional and heuristic search in path problems. Technical report, Stanford Linear Accelerator Center, 1969.
• [46] J. A. Reeds and L. A. Shepp: Optimal paths for a car that goes both forwards and backwards. Pacific J. Math., 145(2), (1990), 367-393.
• [47] J. H. Reif: Complexity of the mover’s problem and generalizations. Proc. IEEE Symp. on Foundations of Computer Science, (1979), 421-427.
• [48] R. L Sproull: Refinements to nearest-neighbor searching in k-dimensional trees. Algorithmica, 6 (1991), 579-589.
• [49] G. J. Toussaint, T. Basar, and F. Bullo; Motion planning for nonlinear underactuated vehicles using hinfinity techniques. Coordinated Science Lab, University of Illinois, 2000.
• [50] D. Vallejo, C. Jones, and N. Amato: An adaptive framework for "single shot" motion planning. Texas A&M, 1999.
• [51] P. N. Yianilos: Data structures and algorithms for nearest neighbor search in general metric spaces. ACM-SIAM Symp. on Discrete Algorithms, (1993), 311-321.