2025-4-3- Friday
HomeIntroductionEditorial boardContact usChinese
Home > Archive>Volume 45, Issue 08, 2017 >1150-1159. DOI:10.11908/j.issn.0253-374x.2017.08.008
PDF HTML XML Export Cite reminder
A Review of the Motion Planning Problem of Autonomous Vehicle
CSTR:
[cstr]
Author:
Clc Number:

TP242.6

  • Article
    • | |
  • Metrics
    • |
  • Reference [118]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    The motion planning problem of unmanned autonomous vehicle (UAV) is reviewed. UAV operates in both structured road and unstructured field with differential constraints. The problem of trajectory generation can be simplified with the differential flatness of Ackerman steering vehicle. Compared to direct trajectory generation method, pathvelocity decomposition method is more popular. Clothoids, splines and polynomial spirals are used for path generation. The two major planning algorithms of great practical significance are rapidly random tree(RRT) in the name of samplingbased and A* in the name of searchbased methods.

    Reference
    LaValle S M. Planning algorithms[M]. Cambridge university press, 2006.
    Laumond J P. Robot Motion Planning and Control[M]. Springer Berlin Heidelberg, 1998.
    Kavraki L E, Svestka P, Latombe J C, et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. IEEE transactions on Robotics and Automation, 1996, 12(4): 566-580.
    Siméon T, Laumond J P, Nissoux C. Visibility-based probabilistic roadmaps for motion planning[J]. Advanced Robotics, 2000, 14(6): 477-493.
    Brooks R A, Lozano-Perez T. A Subdivision Algorithm in Configuration Space for Findpath with Rotation[R]. MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB, 1982.
    Khatib O. Real-time obstacle avoidance for manipulators and mobile robots[J]. The international journal of robotics research, 1986, 5(1): 90-98.
    LaValle S M. Rapidly-exploring random trees: A new tool for path planning[J]. 1998.
    LaValle S M, Kuffner Jr J J. Rapidly-exploring random trees: Progress and prospects[J]. 2000.
    LaValle S M, Kuffner J J. Randomized kinodynamic planning[J]. The International Journal of Robotics Research, 2001, 20(5): 378-400.
    Pivtoraiko M, Kelly A. Efficient constrained path planning via search in state lattices[C]//International Symposium on Artificial Intelligence, Robotics, and Automation in Space. 2005: 1-7.
    Pivtoraiko M, Kelly A. Generating near minimal spanning control sets for constrained motion planning in discrete state spaces[C]//2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2005: 3231-3237.
    Ferguson D, Howard T M, Likhachev M. Motion planning in urban environments [J]. Journal of Field Robotics, 2008, 25(11‐12): 939-960.
    Leonard J, How J, Teller S, et al. A perception‐driven autonomous urban vehicle[J]. Journal of Field Robotics, 2008, 25(10): 727-774.
    Reif J H. Complexity of the mover’s problem and generalizations extended abstract[C]//Proceedings of the 20th Annual IEEE Conference on Foundations of Computer Science. 1979: 421-427.
    Sastry S S. Nonlinear systems: analysis, stability, and control[M]. Springer Science Business Media, 2013.
    Betts J T. Survey of numerical methods for trajectory optimization[J]. Journal of guidance, control, and dynamics, 1998, 21(2): 193-207.
    Lafferriere G, Sussmann H J. A differential geometric approach to motion planning[M]. Nonholonomic motion planning. Springer US, 1993: 235-270.
    Murray R M, Sastry S S. Nonholonomic motion planning: Steering using sinusoids[J]. Automatic Control, IEEE Transactions on, 1993, 38(5): 700-716.
    Rouchon P, Fliess M, Lévine J, et al. Flatness, motion planning and trailer systems[C]. Decision and Control, 1993., Proceedings of the 32nd IEEE Conference on. IEEE, 1993: 2700-2705.
    Fliess M, Lévine J, Martin P, et al. Flatness and defect of non-linear systems: introductory theory and examples[J]. International journal of control, 1995, 61(6): 1327-1361.
    Murray R M, Rathinam M, Sluis W. Differential flatness of mechanical control systems: A catalog of prototype systems[C]. ASME International Mechanical Engineering Congress and Exposition. 1995.
    Rouchon P, Martin P, Murray R M. Flat systems, equivalence and trajectory generation[R]. Tech. Rep. CDS 2003-008, California Institute of Technology, Pasadena, Calif, USA, 2003.
    Takahashi A, Hongo T, Ninomiya Y, et al. Local path planning and motion control for AGV in positioning[C]//Intelligent Robots and Systems' 89. The Autonomous Mobile Robots and Its Applications. IROS'89. Proceedings., IEEE/RSJ International Workshop on. IEEE, 1989: 392-397.
    Werling M, Ziegler J, Kammel S, et al. Optimal trajectory generation for dynamic street scenarios in a frenet frame[C]. Robotics and Automation (ICRA), 2010 IEEE International Conference on. IEEE, 2010: 987-993.
    Kant K, Zucker S W. Toward efficient trajectory planning: The path-velocity decomposition[J]. The International Journal of Robotics Research, 1986, 5(3): 72-89.
    Fraichard T, Laugier C. Path-velocity decomposition revisited and applied to dynamic trajectory planning[C]. Robotics and Automation, 1993. Proceedings., 1993 IEEE International Conference on. IEEE, 1993: 40-45.
    Pham Q C, Caron S, Lertkultanon P, et al. Planning Truly Dynamic Motions: Path-Velocity Decomposition Revisited [J]. arXiv preprint arXiv:1411.4045, 2014.
    Dubins L E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents[J]. American Journal of mathematics, 1957: 497-516.
    Reeds J, Shepp L. Optimal paths for a car that goes both forwards and backwards[J]. Pacific journal of mathematics, 1990, 145(2): 367-393.
    Soueres P, Laumond J P. Shortest paths synthesis for a car-like robot[J]. Automatic Control, IEEE Transactions on, 1996, 41(5): 672-688.
    Scheuer A, Fraichard T. Continuous-curvature path planning for car-like vehicles[C]. Intelligent Robots and Systems, 1997. IROS'97., Proceedings of the 1997 IEEE/RSJ International Conference on. IEEE, 1997, 2: 997-1003.
    Meek D S, Walton D J. A note on finding clothoids[J]. Journal of Computational and Applied Mathematics, 2004, 170(2): 433-453.
    Fraichard T, Scheuer A. From Reeds and Shepp's to continuous-curvature paths [J]. Robotics, IEEE Transactions on, 2004, 20(6): 1025-1035.
    Bakolas E, Tsiotras P. On the generation of nearly optimal, planar paths of bounded curvature and bounded curvature gradient[C]. American Control Conference, 2009. ACC'09. IEEE, 2009: 385-390.
    Wilde D K. Computing clothoid segments for trajectory generation[C]. Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on. IEEE, 2009: 2440-2445.
    Vorobieva H, Minoiu-Enache N, Glaser S, et al. Geometric continuous-curvature path planning for automatic parallel parking[J]. Networking, Sensing and Control (ICNSC), 2013 10th IEEE International Conference on, 2013:418 - 423.
    Vorobieva H, Glaser S, Minoiu-Enache N, et al. Automatic parallel parking with geometric continuous-curvature path planning[C]. Intelligent Vehicles Symposium Proceedings, 2014 IEEE. IEEE, 2014:465 - 471.
    Komoriya K, Tanie K. Trajectory Design and Control of a Wheel-type Mobile Robot Using B-spline Curve[J]. Proceedings of the ‘89 IEEE/RSJ Intl. Workshop on Intelligent Robots and Systems, 1989:398 - 405.
    Yang K, Sukkarieh S. 3D smooth path planning for a UAV in cluttered natural environments[C]. //Intelligent Robots and Systems, Iros, IEEE/RSJ International Conference on. IEEE, 2008:794 - 800.
    Yang K, Sukkarieh S. Planning continuous curvature paths for UAVs amongst obstacles[C]//Australasian Conference on Robotics Automation, Canberra, Australia. 2008.
    Yang K, Sukkarieh S. An Analytical Continuous-Curvature Path-Smoothing Algorithm[J]. Robotics, IEEE Transactions on, 2010, 26(3):561 - 568.
    Yang K, Moon S, Yoo S, et al. Spline-Based RRT Path Planner for Non-Holonomic Robots[J]. Journal of intelligent robotic systems: Theory applications, 2014, 73(14):págs. 763-782.
    Piazzi A, Guarino Lo Bianco C, Romano M. eta3-Splines for the Smooth Path Generation of Wheeled Mobile Robots[J]. eta3-Splines for the Smooth Path Generation of Wheeled Mobile Robots - ResearchGate, 2007, 23(5):1089-1095.
    Piazzi A, Bianco C G L, Romano M. Smooth path generation for wheeled mobile robots using η3-splines[J]. Motion Control, 2010: 75-96.
    Chang H, Liu J. High-quality path planning for autonomous mobile robots with η3-splines and parallel genetic algorithms[J]. Robotics and Biomimetics, 2008. ROBIO 2008. IEEE International Conference on, 2009:1671 - 1677.
    Nagy B, Kelly A. Trajectory generation for car-like robots using cubic curvature polynomials[J]. Field and Service Robots, 2001, 11.
    Kelly A. Reactive Nonholonomic Trajectory Generation via Parametric Optimal Control[J]. The International Journal of Robotics Research, 2003, 22(7-8):583-601.
    Mishchenko A S, Fomenko A T. A course of differential geometry and topology[M]. Mir Publishers, 1988.
    McNaughton M. Parallel algorithms for real-time motion planning[J]. 2011.
    Mcnaughton M, Urmson C, Dolan J M, et al. Motion planning for autonomous driving with a conformal spatiotemporal lattice[J]. Robotics and Automation (ICRA), 2011 IEEE International Conference on, 2011, 19(6):4889 - 4895.
    Bianco C G L, Piazzi A, Romano M. Velocity Planning For Autonomous Vehicles[J]. Intelligent Vehicles Symposium, 2004 IEEE, 2004:413 - 418.
    Guarino Lo Bianco C, Romano M. Bounded velocity planning for autonomous vehicles[C]. //Intelligent Robots and Systems, 2005. (IROS 2005). 2005 IEEE/RSJ International Conference on. IEEE, 2005:685 - 690.
    Solea R, Nunes U. Trajectory Planning with Velocity Planner for Fully-Automated Passenger Vehicles[C]. //Intelligent Transportation Systems Conference, 2006. ITSC '06. IEEE. IEEE, 2006:474 - 480.
    Bianco C G L. Kinematically constrained smooth real-time velocity planning for robotics applications[C]. //Control and Automation, 2009. ICCA 2009. IEEE International Conference on. IEEE, 2009:373 - 378.
    Guarino Lo Bianco C. Minimum-Jerk Velocity Planning for Mobile Robot Applications[J]. Robo Ranaon on, 2013, 29(5):1317 - 1326.
    Xu W, Wei J, Dolan J M, et al. A real-time motion planner with trajectory optimization for autonomous vehicles[J]. In IEEE ICRA - International Conference on Robotics and Automation, 2012, 162(4):2061 - 2067.
    Kavraki L, Kolountzakis M N, Latombe J. Analysis Of Probabilistic Roadmaps For Path Planning[J]. Robotics and Automation, 1996. Proceedings., 1996 IEEE International Conference on, 1996, 4(1):3020 - 3025.
    Kuwata Y, Teo J, Karaman S, et al. Motion planning in complex environments using closed-loop prediction[J]. Proc. AIAA Guidance, Navigation, and Control Conf. and Exhibit, 2008.
    Jr. J J K, Lavalle S M. RRT-connect: An efficient approach to single-query path planning[C]. //Robotics and Automation, 2000. Proceedings. ICRA '00. IEEE International Conference on. IEEE, 2000:995 - 1001.
    LaValle S M. Motion planning[J]. IEEE Robotics Automation Magazine, 2011, 18(1): 79-89.
    Lamiraux F. Kinodynamic Motion Planning: Connecting Exploration Trees Using Trajectory Optimization Methods[J]. In IEEE Int. Conf. Robot. Autom, 2004:3987 - 3992 Vol.4.
    Urmson C, Simmons R. Approaches for heuristically biasing RRT growth[C]. //Intelligent Robots and Systems, 2003. (IROS 2003). Proceedings. 2003 IEEE/RSJ International Conference on. IEEE, 2003:1178 - 1183.
    Kiesel S, Burns E, Ruml W. Abstraction-Guided Sampling for Motion Planning[C]//SOCS. 2012.
    Shkolnik A, Walter M, Tedrake R. Reachability-guided sampling for planning under differential constraints[C]//Robotics and Automation, 2009. ICRA'09. IEEE International Conference on. IEEE, 2009: 2859-2865.
    Shkolnik A C. Sample-based motion planning in high-dimensional and differentially-constrained systems[D]. Massachusetts Institute of Technology, 2010.
    Jaillet L, Cortés J, Siméon T. Sampling-based path planning on configuration-space costmaps[J]. IEEE Transactions on Robotics, 2010, 26(4): 635-646.
    Bohlin R, Kavraki L E. Path planning using lazy PRM[C]//Robotics and Automation, 2000. Proceedings. ICRA'00. IEEE International Conference on. IEEE, 2000, 1: 521-528.
    Cheng P, LaValle S M. Reducing metric sensitivity in randomized trajectory design[C]//Intelligent Robots and Systems, 2001. Proceedings. 2001 IEEE/RSJ International Conference on. IEEE, 2001, 1: 43-48.
    Cheng P. Sampling-based motion planning with differential constraints[D]. University of Illinois at Urbana-Champaign, 2005.
    Jaillet L, Hoffman J, Berg J V D, et al. EG-RRT: Environment-guided random trees for kinodynamic motion planning with uncertainty and obstacles[C]. //Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on. IEEE, 2011:2646 - 2652.
    Yershova A, Jaillet L, Siméon T, et al. Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain[C]. //Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on. IEEE, 2005:3856 - 3861.
    Jaillet L, Yershova A, LaValle S M, et al. Adaptive Tuning of the Sampling Domain for Dynamic-Domain RRTs[J]. Intelligent Robots and Systems, IEEE/RSJ International Conference on, 2005:2851 - 2856.
    Ferguson D, Stentz A. Anytime RRTs[C]. //Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on. IEEE, 2006:5369 - 5375.
    Tsianos K I, Kavraki L E. Replanning: A powerful planning strategy for hard kinodynamic problems[C]. //Intelligent Robots and Systems, 2008. IROS 2008. IEEE/RSJ International Conference on. IEEE, 2008:1667 - 1672.
    Cheng P, LaValle S M. Reducing metric sensitivity in randomized trajectory design[C]. //Intelligent Robots and Systems, 2001. Proceedings. 2001 IEEE/RSJ International Conference on. IEEE, 2001:43 - 48.
    Kuffner J J. Effective Sampling and Distance Metrics for 3D Rigid Body Path Planning[J]. In IEEE International Conference on Robotics and Automation, 2004:3993--3998.
    Jeon J H, Karaman S, Frazzoli E. Anytime computation of time-optimal off-road vehicle maneuvers using the RRT[J]. Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on, 2011, 413(1):3276 - 3282.
    Karaman S, Frazzoli E. Incremental sampling-based algorithms for optimal motion planning[J]. Robotics Science and Systems VI, 2010, 104.
    Karaman S, Frazzoli E. Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.
    Karaman S. Sampling-based algorithms for optimal path planning problems[D]. Massachusetts Institute of Technology, 2012.
    Salzman O, Halperin D. Asymptotically near-optimal RRT for fast, high-quality, motion planning[C]//2014 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2014: 4680-4685.
    Janson L, Schmerling E, Clark A, et al. Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions[J]. The International journal of robotics research, 2015: 0278364915577958.
    Li Y, Littlefield Z, Bekris K E. Asymptotically Optimal Sampling-based Kinodynamic Planning[J]. eprint arXiv:1407.2896, 2014.
    Gammell J D, Srinivasa S S, Barfoot T D. Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic[J]. Eprint Arxiv：1404, 2014:2997 - 3004.
    Gammell J D, Srinivasa S S, Barfoot T D. Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs[J]. Eprint Arxiv：1405, 2014.
    Xie C, van den Berg J, Patil S, et al. Toward asymptotically optimal motion planning for kinodynamic systems using a two-point boundary value problem solver[C]//2015 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2015: 4187-4194.
    Qureshi A H, Mumtaz S, Iqbal K F, et al. Triangular geometry based optimal motion planning using RRT*-motion planner[C]//Advanced Motion Control (AMC), 2014 IEEE 13th International Workshop on. IEEE, 2014: 380-385.
    Devaurs D, Siméon T, Cortés J. Optimal Path Planning in Complex Cost Spaces With Sampling-Based Algorithms[J]. IEEE Transactions on Automation Science and Engineering, 2016, 13(2): 415-424.
    Karaman S, Frazzoli E. Optimal Kinodynamic Motion Planning using Incremental Sampling-Based Methods[J]. Decision and Control (CDC), 2010 49th IEEE Conference on, 2010, 5(10):7681 - 7687.
    Jeon J H, Cowlagi R V, Peters S C, et al. Optimal motion planning with the half-car dynamical model for autonomous high-speed driving[C]. //American Control Conference. IEEE, 2013:188 - 193.
    Karaman S, Frazzoli E. Sampling-based optimal motion planning for non-holonomic dynamical systems[J]. Robotics and Automation (ICRA), 2013 IEEE International Conference on, 2013:5041 - 5047.
    Krogh B H, Thorpe C E. Integrated Path Planning and Dynamic Steering Control for Autonomous Vehicles[J]. Robotics and Automation. Proceedings. 1986 IEEE International Conference on, 1986:1664 - 1669.
    Pivtoraiko M, Kelly A. Efficient constrained path planning via search in state lattices[J]. in 8th International Symposium on Artificial Intelligence, Robotics and Automation in Space, 2005.
    Authors U. Generating near minimal spanning control sets for constrained motion planning in discrete state spaces[C]. //Intelligent Robots and Systems, 2005. (IROS 2005). 2005 IEEE/RSJ International Conference on. IEEE, 2005:3231 - 3237.
    Knepper R A, Kelly A. High Performance State Lattice Planning Using Heuristic Look-Up Tables[C]. //Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on. IEEE, 2006:3375 - 3380.
    Pivtoraiko M, Kelly A. Differentially Constrained Mobile Robot Motion Planning in State Lattices[J]. Journal of Field Robotics, 2008, 26(3):308–333.
    Rufli M, Siegwart R. On the design of deformable input-/state-lattice graphs[J]. In Proceedings of ICRA, 2010, 58(8):3071 - 3077.
    Ziegler J, Stiller C. Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios[C]. //Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on. IEEE, 2009:1879 - 1884.
    Kushleyev A, Likhachev M. Time-bounded lattice for efficient planning in dynamic environments[C]. //Robotics and Automation, 2009. ICRA '09. IEEE International Conference on. IEEE, 2009:1662 - 1668.
    Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische mathematik, 1959, 1(1): 269-271.
    Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2):100 - 107.
    Furcy D A. Speeding up the convergence of online heuristic search and scaling up offline heuristic search[J]. 2004.
    Likhachev M, Gordon G J, Thrun S. ARA*: Anytime A* with provable bounds on sub-optimality[C]//Advances in Neural Information Processing Systems. 2003: None.
    Aine S, Swaminathan S, Narayanan V, et al. Multi-heuristic A*[J]. The International Journal of Robotics Research, 2016, 35(1-3): 224-243.
    Narayanan V, Aine S, Likhachev M. Improved multi-heuristic a* for searching with uncalibrated heuristics[C]//Eighth Annual Symposium on Combinatorial Search. 2015.
    Islam F, Narayanan V, Likhachev M. Dynamic multi-heuristic A*[C]//Robotics and Automation (ICRA), 2015 IEEE International Conference on. IEEE, 2015: 2376-2382.
    Islam F, Narayanan V, Likhachev M. A*-Connect: Bounded suboptimal bidirectional heuristic search[C]// IEEE International Conference on Robotics and Automation. 2016.
    Koenig S, Likhachev M. Incremental A[J]. In Proceedings of the Neural Information Processing Systems, 2002.
    Koenig S, Likhachev M, Furcy D. Lifelong planning A*[J]. ARTIFICIAL INTELLIGENCE, 2004, 155(1):93–146.
    Stentz A, A S, Stentz A, et al. Optimal and efficient path planning for partially-known environments[C]. //Robotics and Automation, 1994. Proceedings., 1994 IEEE International Conference on. IEEE, 1994:3310 - 3317.
    Koenig S, Member S, Likhachev M. Fast replanning for navigation in unknown terrain[J]. IEEE TRANSACTIONS ON ROBOTICS, 2005, 21(3):354 - 363.
    Wagner G, Choset H. M*: A complete multirobot path planning algorithm with performance bounds.[J]. Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on, 2011, 10(1):3260 - 3267.
    Likhachev M, Stentz A. R* search[J]. Lab Papers (GRASP), 2008: 23.
    Ferguson D, Stentz A. Field D*: An Interpolation-Based Path Planner and Replanner[J]. Proceedings of the International Symposium on Robotics Research (ISRR, 2005:1926--1931.
    Nash A, Daniel K, Koenig S, et al. Theta*: Any-Angle Path Planning on Grids[J]. eprint arXiv:1401.3843, 2014, 39(1):533-579.
    Sucan I A, Moll M, Kavraki E E. The Open Motion Planning Library[J]. Robotics Automation Magazine, IEEE, 2012, 19(4):72 - 82.
    Search-based Planning Laboratory.[DB/OL]. http://www.sbpl.net/
    Pan J, Chitta S, Manocha D. FCL: A general purpose library for collision and proximity queries[C]. //Robotics and Automation (ICRA), 2012 IEEE International Conference on. IEEE, 2012:3859 - 3866.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

YU Zhuoping, LI Yishan, XIONG Lu. A Review of the Motion Planning Problem of Autonomous Vehicle[J].同济大学学报(自然科学版),2017,45(08):1150~1159

Copy
Share
Article Metrics
  • Abstract:5778
  • PDF: 2717
  • HTML: 1409
  • Cited by: 0
History
  • Received:July 27,2016
  • Revised:June 19,2017
  • Adopted:May 15,2017
  • Online: September 07,2017
Article QR Code

Youare the 26290 visitor to this site

Copyright:JOURNAL OF TONGJI UNIVERSITY     Director:The Ministry of Education    The host:Tongji university.

Address:上海市四平路1239号同济大学内    Postcode:200092    TEL:86-21-65982344     E-mail:zrxb@tongji.edu.cn

Supported byBeijing E-Tiller Technology Development Co.,Ltd.