1932
0
  1. Home
  2. A-Z Publications
  3. Annual Review of Control, Robotics, and Autonomous Systems
  4. Volume 4, 2021
  5. Article

Annual Review of Control, Robotics, and Autonomous Systems

Volume 4, 2021

Asymptotically Optimal Sampling-Based Motion Planning Methods

Abstract

Motion planning is a fundamental problem in autonomous robotics that requires finding a path to a specified goal that avoids obstacles and takes into account a robot's limitations and constraints. It is often desirable for this path to also optimize a cost function, such as path length. Formal path-quality guarantees for continuously valued search spaces are an active area of research interest. Recent results have proven that some sampling-based planning methods probabilistically converge toward the optimal solution as computational effort approaches infinity. This article summarizes the assumptions behind these popular asymptotically optimal techniques and provides an introduction to the significant ongoing research on this topic.

Keyword(s): asymptotically optimal motion planning, motion planning, optimal motion planning, robot motion planning, robotics, sampling-based planning
Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-061920-093753
2021-05-03
2024-04-26
Loading full text...

Full text loading...

/deliver/fulltext/control/4/1/annurev-control-061920-093753.html?itemId=/content/journals/10.1146/annurev-control-061920-093753&mimeType=html&fmt=ahah

Literature Cited

  1. 1. 
    Hart PE, Nilsson NJ, Raphael B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybernet. 4:100–7
     [Google Scholar]
  2. 2. 
    Kavraki LE, Švestka P, Latombe JC, Overmars MH. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12:566–80
     [Google Scholar]
  3. 3. 
    Hsu D, Latombe JC, Motwani R. 1999. Path planning in expansive configuration spaces. Int. J. Comput. Geom. Appl. 9:495–512
     [Google Scholar]
  4. 4. 
    LaValle SM, Kuffner JJJr 2001. Randomized kinodynamic planning. Int. J. Robot. Res 20:378–400
     [Google Scholar]
  5. 5. 
    Kavraki LE, Kolountzakis MN, Latombe JC. 1998. Analysis of probabilistic roadmaps for path planning. IEEE Trans. Robot. Autom. 14:166–71
     [Google Scholar]
  6. 6. 
    Karaman S, Frazzoli E. 2011. Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 30:846–94
     [Google Scholar]
  7. 7. 
    Ferguson D, Stentz A. 2006. Anytime RRTs. 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems,5369–75 Piscataway, NJ: IEEE
     [Google Scholar]
  8. 8. 
    Janson L, Schmerling E, Clark A, Pavone M 2015. Fast Marching Tree: a fast marching sampling-based method for optimal motion planning in many dimensions. Int. J. Robot. Res. 34:883–921
     [Google Scholar]
  9. 9. 
    Solovey K, Kleinbort M. 2020. The critical radius in sampling-based motion planning. Int. J. Robot. Res. 39:266–85
     [Google Scholar]
  10. 10. 
    Solovey K, Janson L, Schmerling E, Frazzoli E, Pavone M. 2020. Revisiting the asymptotic optimality of RRT*. 2020 IEEE International Conference on Robotics and Automation2189–95 Piscataway, NJ: IEEE
     [Google Scholar]
  11. 11. 
    Huynh VA, Kogan L, Frazzoli E. 2014. A martingale approach and time-consistent sampling-based algorithms for risk management in stochastic optimal control. 53rd IEEE Conference on Decision and Control1858–65 Piscataway, NJ: IEEE
     [Google Scholar]
  12. 12. 
    Bera T, Seetharama Bhat M, Ghose D 2013. Probabilistic analysis of sampling based path planning algorithms. 2013 IEEE International Symposium on Intelligent Control370–75 Piscataway, NJ: IEEE
     [Google Scholar]
  13. 13. 
    Janson L, Ichter B, Pavone M. 2018. Deterministic sampling-based motion planning: optimality, complexity, and performance. Int. J. Robot. Res 37:46–61
     [Google Scholar]
  14. 14. 
    Solovey K, Salzman O, Halperin D. 2018. New perspective on sampling-based motion planning via random geometric graphs. Int. J. Robot. Res. 37:1117–33
     [Google Scholar]
  15. 15. 
    Li Y, Littlefield Z, Bekris KE. 2016. Asymptotically optimal sampling-based kinodynamic planning. Int. J. Robot. Res. 35:528–64
     [Google Scholar]
  16. 16. 
    Hauser K, Zhou Y. 2016. Asymptotically optimal planning by feasible kinodynamic planning in a state-cost space. IEEE Trans. Robot. 32:1431–43
     [Google Scholar]
  17. 17. 
    Kleinbort M, Granados E, Solovey K, Bonalli R, Bekris KE, Halperin D. 2020. Refined analysis of asymptotically-optimal kinodynamic planning in the state-cost space. 2020 IEEE International Conference on Robotics and Automation6344–50 Piscataway, NJ: IEEE
     [Google Scholar]
  18. 18. 
    Vega-Brown W, Roy N 2020. Asymptotically optimal planning under piecewise-analytic constraints. Algorithmic Foundations of Robotics XII: Proceedings of the Twelfth Workshop on the Algorithmic Foundations of Robotics K Goldberg, P Abbeel, K Bekris, L Miller 528–43 Cham, Switz: Springer
     [Google Scholar]
  19. 19. 
    Shome R, Nakhimovich D, Bekris KE. 2020. Pushing the boundaries of asymptotic optimality in integrated task and motion planning Paper presented at the 14th International Workshop on the Algorithmic Foundations of Robotics Oulu, Finl:.
  20. 20. 
    Marble JD, Bekris KE. 2013. Asymptotically near-optimal planning with probabilistic roadmap spanners. IEEE Trans. Robot. 29:432–44
     [Google Scholar]
  21. 21. 
    Wang W, Balkcom D, Chakrabarti A. 2013. A fast streaming spanner algorithm for incrementally constructing sparse roadmaps. 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems1257–63 Piscataway, NJ: IEEE
     [Google Scholar]
  22. 22. 
    Dobson A, Bekris KE. 2014. Sparse roadmap spanners for asymptotically near-optimal motion planning. Int. J. Robot. Res. 33:18–47
     [Google Scholar]
  23. 23. 
    Salzman O, Halperin D. 2016. Asymptotically near-optimal RRT for fast, high-quality motion planning. IEEE Trans. Robot. 32:473–83
     [Google Scholar]
  24. 24. 
    Dobson A, Bekris KE. 2013. A study on the finite-time near-optimality properties of sampling-based motion planners. 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems1236–41 Piscataway, NJ: IEEE
     [Google Scholar]
  25. 25. 
    Dobson A, Moustakides GV, Bekris KE. 2015. Geometric probability results for bounding path quality in sampling-based roadmaps after finite computation. 2015 IEEE International Conference on Robotics and Automation4180–86 Piscataway, NJ: IEEE
     [Google Scholar]
  26. 26. 
    Tsao M, Solovey K, Pavone M. 2020. Sample complexity of probabilistic roadmaps via ε-nets. 2020 IEEE International Conference on Robotics and Automation2196–202 Piscataway, NJ: IEEE
     [Google Scholar]
  27. 27. 
    Gammell JD, Barfoot TD, Srinivasa SS. 2018. Informed sampling for asymptotically optimal path planning. IEEE Trans. Robot. 34:966–84
     [Google Scholar]
  28. 28. 
    Palmieri L, Bruns L, Meurer M, Arras KO. 2020. Dispertio: optimal sampling for safe deterministic motion planning. IEEE Robot. Autom. Lett 5:362–68
     [Google Scholar]
  29. 29. 
    Settimi A, Caporale D, Kryczka P, Ferrati M, Pallottino L. 2016. Motion primitive based random planning for loco-manipulation tasks. 2016 IEEE-RAS 16th International Conference on Humanoid Robots1059–66 Piscataway, NJ: IEEE
     [Google Scholar]
  30. 30. 
    Kiesel S, Burns E, Ruml W. 2012. Abstraction-guided sampling for motion planning. Proceedings of the Fifth Annual Symposium on Combinatorial Search162–63 Palo Alto, CA: AAAI Press
     [Google Scholar]
  31. 31. 
    Brunner M, Brüggemann B, Schulz D. 2013. Hierarchical rough terrain motion planning using an optimal sampling-based method. 2013 IEEE International Conference on Robotics and Automation5539–44 Piscataway, NJ: IEEE
     [Google Scholar]
  32. 32. 
    Reid W, Fitch R, Göktoğan AH, Sukkarieh S. 2019. Sampling-based hierarchical motion planning for a reconfigurable wheel-on-leg planetary analogue exploration rover. J. Field Robot. 37:786–811
     [Google Scholar]
  33. 33. 
    Wang J, Meng MQH. 2020. Optimal path planning using generalized Voronoi graph and multiple potential functions. IEEE Trans. Ind. Electron. 67:10621–30
     [Google Scholar]
  34. 34. 
    Qureshi AH, Ayaz Y. 2016. Potential functions based sampling heuristic for optimal path planning. Auton. Robots 40:1079–93
     [Google Scholar]
  35. 35. 
    Hauer F, Tsiotras P 2017. Deformable rapidly-exploring random trees. Robotics: Science and Systems XIII N Amato, S Srinivasa, N Ayanian, S Kuindersma, pap. 8 N.p: Robot. Sci. Syst. Found.
     [Google Scholar]
  36. 36. 
    Bialkowski J, Otte M, Frazzoli E. 2013. Free-configuration biased sampling for motion planning. 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems1272–79 Piscataway, NJ: IEEE
     [Google Scholar]
  37. 37. 
    Kim D, Lee J, Yoon S. 2014. Cloud RRT*: sampling cloud based RRT*. 2014 IEEE International Conference on Robotics and Automation2519–26 Piscataway, NJ: IEEE
     [Google Scholar]
  38. 38. 
    Meng Z, Qin H, Sun H, Shen X, Ang MHJr 2017. Obstacle-guided informed planning towards robot navigation in cluttered environments. 2017 IEEE International Conference on Robotics and Biomimetics332–37 Piscataway, NJ: IEEE
     [Google Scholar]
  39. 39. 
    Lai T, Ramos F, Francis G. 2019. Balancing global exploration and local-connectivity exploitation with rapidly-exploring random disjointed-trees. 2019 International Conference on Robotics and Automation5537–43 Piscataway, NJ: IEEE
     [Google Scholar]
  40. 40. 
    Kang M, Kim D, Yoon S. 2019. Harmonious sampling for mobile manipulation planning. 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems3185–92 Piscataway, NJ: IEEE
     [Google Scholar]
  41. 41. 
    Kobilarov M. 2012. Cross-entropy motion planning. Int. J. Robot. Res. . 31:855–71
     [Google Scholar]
  42. 42. 
    Arslan O, Tsiotras P. 2015. Machine learning guided exploration for sampling-based motion planning algorithms. 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems2646–52 Piscataway, NJ: IEEE
     [Google Scholar]
  43. 43. 
    Iversen TF, Ellekilde LP. 2016. Kernel density estimation based self-learning sampling strategy for motion planning of repetitive tasks. 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems1380–87 Piscataway, NJ: IEEE
     [Google Scholar]
  44. 44. 
    Lehner P, Albu-Schäffer A. 2017. Repetition sampling for efficiently planning similar constrained manipulation tasks. 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems2851–56 Piscataway, NJ: IEEE
     [Google Scholar]
  45. 45. 
    Ichter B, Harrison J, Pavone M. 2018. Learning sampling distributions for robot motion planning. 2018 IEEE International Conference on Robotics and Automation7087–94 Piscataway, NJ: IEEE
     [Google Scholar]
  46. 46. 
    Qureshi AH, Yip MC. 2018. Deeply informed neural sampling for robot motion planning. 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems6582–88 Piscataway, NJ: IEEE
     [Google Scholar]
  47. 47. 
    Zhang C, Huh J, Lee DD. 2018. Learning implicit sampling distributions for motion planning. 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems3654–61 Piscataway, NJ: IEEE
     [Google Scholar]
  48. 48. 
    Kumar R, Mandalika A, Choudhury S, Srinivasa SS. 2019. LEGO: leveraging experience in roadmap generation for sampling-based planning. 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems1488–95 Piscataway, NJ: IEEE
     [Google Scholar]
  49. 49. 
    Lai T, Morere P, Ramos F, Francis G. 2020. Bayesian local sampling-based planning. IEEE Robot. Autom. Lett 5:1953–60
     [Google Scholar]
  50. 50. 
    Akgun B, Stilman M. 2011. Sampling heuristics for optimal motion planning in high dimensions. 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems2640–45 Piscataway, NJ: IEEE
     [Google Scholar]
  51. 51. 
    Nasir J, Islam F, Malik U, Ayaz Y, Hasan O et al. 2013. RRT*-SMART: a rapid convergence implementation of RRT*. Int. J. Adv. Robot. Syst. 10:299
     [Google Scholar]
  52. 52. 
    Perez A, Karaman S, Shkolnik A, Frazzoli E, Teller S, Walter MR. 2011. Asymptotically-optimal path planning for manipulation using incremental sampling-based algorithms. 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems4307–13 Piscataway, NJ: IEEE
     [Google Scholar]
  53. 53. 
    Otte M, Correll N. 2013. C-FOREST: parallel shortest path planning with superlinear speedup. IEEE Trans. Robot. 29:798–806
     [Google Scholar]
  54. 54. 
    Arslan O, Tsiotras P. 2015. Dynamic programming guided exploration for sampling-based motion planning algorithms. 2015 IEEE International Conference on Robotics and Automation4819–26 Piscataway, NJ: IEEE
     [Google Scholar]
  55. 55. 
    Kunz T, Thomaz A, Christensen H. 2016. Hierarchical rejection sampling for informed kinodynamic planning in high-dimensional spaces. 2016 IEEE International Conference on Robotics and Automation89–96 Piscataway, NJ: IEEE
     [Google Scholar]
  56. 56. 
    Littlefield Z, Bekris KE 2018. Informed asymptotically near-optimal planning for field robots with dynamics. Field and Service Robotics: Results of the 11th International Conference M Hutter, R Siegwart 449–63 Cham, Switz: Springer
     [Google Scholar]
  57. 57. 
    Yi D, Thakker R, Gulino C, Salzman O, Srinivasa SS. 2018. Generalizing informed sampling for asymptotically-optimal sampling-based kinodynamic planning via Markov chain Monte Carlo. 2018 IEEE International Conference on Robotics and Automation7063–70 Piscataway, NJ: IEEE
     [Google Scholar]
  58. 58. 
    Joshi SS, Tsiotras P. 2019. Non-parametric informed exploration for sampling-based motion planning. 2019 International Conference on Robotics and Automation5915–21 Piscataway, NJ: IEEE
     [Google Scholar]
  59. 59. 
    Persson SM, Sharf I. 2014. Sampling-based A* algorithm for robot path-planning. Int. J. Robot. Res 33:1683–708
     [Google Scholar]
  60. 60. 
    Salzman O, Halperin D. 2015. Asymptotically-optimal motion planning using lower bounds on cost. 2015 IEEE International Conference on Robotics and Automation4167–72 Piscataway, NJ: IEEE
     [Google Scholar]
  61. 61. 
    Gammell JD, Barfoot TD, Srinivasa SS. 2020. Batch Informed Trees (BIT*): informed asymptotically optimal anytime search. Int. J. Robot. Res 39:543–67
     [Google Scholar]
  62. 62. 
    Holston AC, Kim DH, Kim JH. 2017. Fast-BIT*: modified heuristic for sampling-based optimal planning with a faster first solution and convergence in implicit random geometric graphs. 2017 IEEE International Conference on Robotics and Biomimetics1892–99 Piscataway, NJ: IEEE
     [Google Scholar]
  63. 63. 
    Strub MP, Gammell JD. 2020. Advanced BIT* (ABIT*): sampling-based planning with advanced graph-search techniques. 2020 IEEE International Conference on Robotics and Automation130–36 Piscataway, NJ: IEEE
     [Google Scholar]
  64. 64. 
    Strub MP, Gammell JD. 2020. Adaptively Informed Trees (AIT*): fast asymptotically optimal path planning through adaptive heuristics. 2020 IEEE International Conference on Robotics and Automation3191–98 Piscataway, NJ: IEEE
     [Google Scholar]
  65. 65. 
    Paden B, Varricchio V, Frazzoli E. 2017. Verification and synthesis of admissible heuristics for kinodynamic motion planning. IEEE Robot. Autom. Lett 2:648–55
     [Google Scholar]
  66. 66. 
    Hauser K. 2015. Lazy collision checking in asymptotically-optimal motion planning. 2015 IEEE International Conference on Robotics and Automation2951–57 Piscataway, NJ: IEEE
     [Google Scholar]
  67. 67. 
    Kim D, Kwon Y, Yoon S. 2018. Adaptive lazy collision checking for optimal sampling-based motion planning. 2018 15th International Conference on Ubiquitous Robots320–27 Piscataway, NJ: IEEE
     [Google Scholar]
  68. 68. 
    Luna R, Şucan IA, Moll M, Kavraki LE. 2013. Anytime solution optimization for sampling-based motion planning. 2013 IEEE International Conference on Robotics and Automation5068–74 Piscataway, NJ: IEEE
     [Google Scholar]
  69. 69. 
    Zucker M, Ratliff N, Dragan AD, Pivtoraiko M, Klingensmith M et al. 2013. CHOMP: Covariant Hamiltonian Optimization for Motion Planning. Int. J. Robot. Res 32:1164–93
     [Google Scholar]
  70. 70. 
    Choudhury S, Gammell JD, Barfoot TD, Srinivasa SS, Scherer S. 2016. Regionally Accelerated Batch Informed Trees (RABIT*): a framework to integrate local information into optimal path planning. 2016 IEEE International Conference on Robotics and Automation4207–14 Piscataway, NJ: IEEE
     [Google Scholar]
  71. 71. 
    Suh J, Gong J, Oh S. 2017. Fast sampling-based cost-aware path planning with nonmyopic extensions using cross entropy. IEEE Trans. Robot. 33:1313–26
     [Google Scholar]
  72. 72. 
    Kim D, Yoon S. 2020. Simultaneous planning of sampling and optimization: study on lazy evaluation and configuration free space approximation for optimal motion planning algorithm. Auton. Robots 44:165–81
     [Google Scholar]
  73. 73. 
    Kim MC, Song JB. 2018. Informed RRT* with improved converging rate by adopting wrapping procedure. Intell. Serv. Robot. 11:53–60
     [Google Scholar]
  74. 74. 
    Kuntz A, Bowen C, Alterovitz R 2020. Fast anytime motion planning in point clouds by interleaving sampling and interior point optimization. Robotics Research: The 18th International Symposium ISRR N Amato, G Hager, S Thomas, M Torres-Torriti 929–45 Cham, Switz: Springer
     [Google Scholar]
  75. 75. 
    Kim D, Kang M, Yoon S. 2019. Volumetric Tree*: adaptive sparse graph for effective exploration of homotopy classes. 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems1496–503 Piscataway, NJ: IEEE
     [Google Scholar]
  76. 76. 
    Kuffner JJJr, LaValle SM. 2000. RRT-connect: an efficient approach to single-query path planning. 2000 IEEE International Conference on Robotics and Automation, Vol. 2995–1001 Piscataway, NJ: IEEE
     [Google Scholar]
  77. 77. 
    Klemm S, Oberländer J, Hermann A, Roennau A, Schamm T et al. 2015. RRT*-Connect: faster, asymptotically optimal motion planning. 2015 IEEE International Conference on Robotics and Biomimetics1670–77 Piscataway, NJ: IEEE
     [Google Scholar]
  78. 78. 
    Jordan M, Perez A. 2013. Optimal bidirectional Rapidly-exploring Random Trees Tech. Rep. MIT-CSAIL-TR-2013-021 Comput. Sci. Artif. Intell. Lab., Mass. Inst. Technol Cambridge:
  79. 79. 
    Qureshi AH, Ayaz Y. 2015. Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments. Robot. Auton. Syst 68:1–11
     [Google Scholar]
  80. 80. 
    Burget F, Bennewitz M, Burgard W. 2016. BI2RRT*: an efficient sampling-based path planning framework for task-constrained mobile manipulation. 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems3714–21 Piscataway, NJ: IEEE
     [Google Scholar]
  81. 81. 
    Jaillet L, Porta JM. 2013. Efficient asymptotically-optimal path planning on manifolds. Robot. Auton. Syst. 61:797–807
     [Google Scholar]
  82. 82. 
    Boardman B, Harden T, Martínez S. 2014. Optimal kinodynamic motion planning in environments with unexpected obstacles. 2014 52nd Annual Allerton Conference on Communication1026–32 Piscataway, NJ: IEEE
     [Google Scholar]
  83. 83. 
    Starek JA, Gomez JV, Schmerling E, Janson L, Moreno L, Pavone M. 2015. An asymptotically-optimal sampling-based algorithm for bi-directional motion planning. 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems2072–78 Piscataway, NJ: IEEE
     [Google Scholar]
  84. 84. 
    Alterovitz R, Patil S, Derbakova A. 2011. Rapidly-exploring roadmaps: weighing exploration versus refinement in optimal motion planning. 2011 IEEE International Conference on Robotics and Automation3706–12 Piscataway, NJ: IEEE
     [Google Scholar]
  85. 85. 
    Shan YX, Li BJ, Zhou J, Zhang Y. 2014. An approach to speed up RRT*. 2014 IEEE Intelligent Vehicles Symposium Proceedings594–98 Piscataway, NJ: IEEE
     [Google Scholar]
  86. 86. 
    Arslan O, Tsiotras P. 2013. Use of relaxation methods in sampling-based algorithms for optimal motion planning. 2013 IEEE International Conference on Robotics and Automation2421–28 Piscataway, NJ: IEEE
     [Google Scholar]
  87. 87. 
    Arslan O, Tsiotras P. 2016. Incremental sampling-based motion planners using policy iteration methods. 2016 IEEE 55th Conference on Decision and Control5004–9 Piscataway, NJ: IEEE
     [Google Scholar]
  88. 88. 
    Kingston Z, Moll M, Kavraki LE. 2019. Exploring implicit spaces for constrained sampling-based planning. Int. J. Robot. Res 38:1151–78
     [Google Scholar]
  89. 89. 
    Karaman S, Frazzoli E. 2013. Sampling-based optimal motion planning for non-holonomic dynamical systems. 2013 IEEE International Conference on Robotics and Automation5041–47 Piscataway, NJ: IEEE
     [Google Scholar]
  90. 90. 
    Park JJ, Kuipers B. 2015. Feedback motion planning via non-holonomic RRT* for mobile robots. 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems4035–40 Piscataway, NJ: IEEE
     [Google Scholar]
  91. 91. 
    Schmerling E, Janson L, Pavone M. 2015. Optimal sampling-based motion planning under differential constraints: the driftless case. 2015 IEEE International Conference on Robotics and Automation2368–75 Piscataway, NJ: IEEE
     [Google Scholar]
  92. 92. 
    Yershov DS, Frazzoli E. 2016. Asymptotically optimal feedback planning using a numerical Hamilton-Jacobi-Bellman solver and an adaptive mesh refinement. Int. J. Robot. Res. . 35:565–84
     [Google Scholar]
  93. 93. 
    Palmieri L, Kucner TP, Magnusson M, Lilienthal AJ, Arras KO 2017. Kinodynamic motion planning on Gaussian mixture fields. 2017 IEEE International Conference on Robotics and Automation6176–81 Piscataway, NJ: IEEE
     [Google Scholar]
  94. 94. 
    Karaman S, Frazzoli E. 2010. Optimal kinodynamic motion planning using incremental sampling-based methods. 49th IEEE Conference on Decision and Control7681–87 Piscataway, NJ: IEEE
     [Google Scholar]
  95. 95. 
    Schmerling E, Janson L, Pavone M. 2015. Optimal sampling-based motion planning under differential constraints: the drift case with linear affine dynamics. 2015 54th IEEE Conference on Decision and Control2574–81 Piscataway, NJ: IEEE
     [Google Scholar]
  96. 96. 
    Jeon JH, Karaman S, Frazzoli E. 2011. Anytime computation of time-optimal off-road vehicle maneuvers using the RRT*. 2011 50th IEEE Conference on Decision and Control and European Control Conference3276–82 Piscataway, NJ: IEEE
     [Google Scholar]
  97. 97. 
    Perez A, Platt R, Konidaris G, Kaelbling L, Lozano-Perez T. 2012. LQR-RRT*: optimal sampling-based motion planning with automatically derived extension heuristics. 2012 IEEE International Conference on Robotics and Automation2537–42 Piscataway, NJ: IEEE
     [Google Scholar]
  98. 98. 
    Goretkin G, Perez A, Platt R, Konidaris G. 2013. Optimal sampling-based planning for linear-quadratic kinodynamic systems. 2013 IEEE International Conference on Robotics and Automation2429–36 Piscataway, NJ: IEEE
     [Google Scholar]
  99. 99. 
    Webb DJ, van den Berg J. 2013. Kinodynamic RRT*: asymptotically optimal motion planning for robots with linear dynamics. 2013 IEEE International Conference on Robotics and Automation5054–61 Piscataway, NJ: IEEE
     [Google Scholar]
  100. 100. 
    Ha JS, Lee JJ, Choi HL. 2013. A successive approximation-based approach for optimal kinodynamic motion planning with nonlinear differential constraints. 52nd IEEE Conference on Decision and Control3623–28 Piscataway, NJ: IEEE
     [Google Scholar]
  101. 101. 
    Arslan O, Berntorp K, Tsiotras P. 2017. Sampling-based algorithms for optimal motion planning using closed-loop prediction. 2017 IEEE International Conference on Robotics and Automation4991–96 Piscataway, NJ: IEEE
     [Google Scholar]
  102. 102. 
    Sakcak B, Bascetta L, Ferretti G, Prandini M. 2019. Sampling-based optimal kinodynamic planning with motion primitives. Auton. Robots 43:1715–32
     [Google Scholar]
  103. 103. 
    Xie C, van den Berg J, Patil S, Abbeel P. 2015. Toward asymptotically optimal motion planning for kinodynamic systems using a two-point boundary value problem solver. 2015 IEEE International Conference on Robotics and Automation4187–94 Piscataway, NJ: IEEE
     [Google Scholar]
  104. 104. 
    Jeon JH, Karaman S, Frazzoli E. 2015. Optimal sampling-based feedback motion trees among obstacles for controllable linear systems with linear constraints. 2015 IEEE International Conference on Robotics and Automation4195–201 Piscataway, NJ: IEEE
     [Google Scholar]
  105. 105. 
    Littlefield Z, Bekris KE. 2018. Efficient and asymptotically optimal kinodynamic motion planning via dominance-informed regions. 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems Piscataway, NJ: IEEE https://doi.org/10.1109/IROS.2018.8593672
    [Crossref] [Google Scholar]
  106. 106. 
    Abbasi-Yadkori Y, Modayil J, Szepesvari C. 2010. Extending rapidly-exploring random trees for asymptotically optimal anytime motion planning. 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems127–32 Piscataway, NJ: IEEE
     [Google Scholar]
  107. 107. 
    Paden B, Frazzoli E 2020. A generalized label correcting method for optimal kinodynamic motion planning. Algorithmic Foundations of Robotics XII: Proceedings of the Twelfth Workshop on the Algorithmic Foundations of Robotics K Goldberg, P Abbeel, K Bekris, L Miller 512–27 Cham, Switz: Springer
     [Google Scholar]
  108. 108. 
    Karaman S, Frazzoli E. 2012. Sampling-based algorithms for optimal motion planning with deterministic μ-calculus specifications. 2012 American Control Conference735–42 Piscataway, NJ: IEEE
     [Google Scholar]
  109. 109. 
    Varricchio V, Chaudhari P, Frazzoli E. 2014. Sampling-based algorithms for optimal motion planning using process algebra specifications. 2014 IEEE International Conference on Robotics and Automation5326–32 Piscataway, NJ: IEEE
     [Google Scholar]
  110. 110. 
    Cho K, Suh J, Tomlin CJ, Oh S. 2017. Cost-aware path planning under co-safe temporal logic specifications. IEEE Robot. Autom. Lett 2:2308–2315
     [Google Scholar]
  111. 111. 
    Oh Y, Cho K, Choi Y, Oh S. 2017. Robust multi-layered sampling-based path planning for temporal logic-based missions. 2017 IEEE 56th Annual Conference on Decision and Control1675–80 Piscataway, NJ: IEEE
     [Google Scholar]
  112. 112. 
    Zhang Z, Du R, Cowlagi RV. 2020. Randomized sampling-based trajectory optimization for UAVs to satisfy linear temporal logic specifications. Aerosp. Sci. Technol. 96:105591
     [Google Scholar]
  113. 113. 
    Reyes Castro LI, Chaudhari P, Tůmová J, Karaman S, Frazzoli E, Rus D 2013. Incremental sampling-based algorithm for minimum-violation motion planning. 52nd IEEE Conference on Decision and Control3217–24 Piscataway, NJ: IEEE
     [Google Scholar]
  114. 114. 
    Vasile C, Raman V, Karaman S. 2017. Sampling-based synthesis of maximally-satisfying controllers for temporal logic specifications. 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems3840–47 Piscataway, NJ: IEEE
     [Google Scholar]
  115. 115. 
    Chaudhari P, Karaman S, Frazzoli E. 2012. Sampling-based algorithm for filtering using Markov chain approximations. 2012 IEEE 51st IEEE Conference on Decision and Control5972–78 Piscataway, NJ: IEEE
     [Google Scholar]
  116. 116. 
    Huynh VA, Karaman S, Frazzoli E. 2016. An incremental sampling-based algorithm for stochastic optimal control. Int. J. Robot. Res 35:305–33
     [Google Scholar]
  117. 117. 
    Huynh VA, Frazzoli E. 2012. Probabilistically-sound and asymptotically-optimal algorithm for stochastic control with trajectory constraints. 2012 IEEE 51st IEEE Conference on Decision and Control1486–93 Piscataway, NJ: IEEE
     [Google Scholar]
  118. 118. 
    Chaudhari P, Karaman S, Hsu D, Frazzoli E. 2013. Sampling-based algorithms for continuous-time POMDPs. 2013 American Control Conference4604–10 Piscataway, NJ: IEEE
     [Google Scholar]
  119. 119. 
    Karaman S, Frazzoli E 2010. Incremental sampling-based algorithms for a class of pursuit-evasion games. Algorithmic Foundations of Robotics IX: Selected Contributions of the Ninth International Workshop on the Algorithmic Foundations of Robotics D Hsu, V Isler, JC Latombe, MC Lin 71–87 Berlin: Springer
     [Google Scholar]
  120. 120. 
    Karaman S, Walter MR, Perez A, Frazzoli E, Teller S. 2011. Anytime motion planning using the RRT*. 2011 IEEE International Conference on Robotics and Automation1478–83 Piscataway, NJ: IEEE
     [Google Scholar]
  121. 121. 
    Liu S, Liu H, Dong K, Zhu X, Liang B. 2018. A path optimization algorithm for motion planning with the moving target. 2018 IEEE International Conference on Mechatronics and Automation2126–31 Piscataway, NJ: IEEE
     [Google Scholar]
  122. 122. 
    To KYC, Yoo C, Anstee S, Fitch R 2020. Distance and steering heuristics for streamline-based flow field planning. 2020 IEEE International Conference on Robotics and Automation1867–73 Piscataway, NJ: IEEE
     [Google Scholar]
  123. 123. 
    Jeon JH, Cowlagi RV, Peters SC, Karaman S, Frazzoli E et al. 2013. Optimal motion planning with the half-car dynamical model for autonomous high-speed driving. 2013 American Control Conference188–93 Piscataway, NJ: IEEE
     [Google Scholar]
  124. 124. 
    Shin H, Kim D, Yoon S. 2018. Kinodynamic comfort trajectory planning for car-like robots. 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems6532–39 Piscataway, NJ: IEEE
     [Google Scholar]
  125. 125. 
    Xiang S, Gao H, Liu Z, Gosselin C. 2020. Dynamic point-to-point trajectory planning for three degrees-of-freedom cable-suspended parallel robots using rapidly exploring random tree search. J. Mech. Robot. 12:041007
     [Google Scholar]
  126. 126. 
    Chao N, Liu Y, Xia H, Peng M, Ayodeji A. 2019. DL-RRT* algorithm for least dose path re-planning in dynamic radioactive environments. Nucl. Eng. Technol. 51:825–36
     [Google Scholar]
  127. 127. 
    Devaurs D, Siméon T, Cortés J. 2016. Optimal path planning in complex cost spaces with sampling-based algorithms. IEEE Trans. Autom. Sci. Eng. 13:415–24
     [Google Scholar]
  128. 128. 
    Yi D, Goodrich MA, Seppi KD. 2015. MORRF*: sampling-based multi-objective motion planning. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence1733–39 Palo Alto, CA: AAAI Press
     [Google Scholar]
  129. 129. 
    Fu M, Kuntz A, Salzman O, Alterovitz R 2019. Toward asymptotically-optimal inspection planning via efficient near-optimal graph search. Robotics: Science and Systems XV A Bicchi, H Kress-Gazit, S Hutchinson, pap. 57 N.p: Robot. Sci. Syst. Found.
     [Google Scholar]
  130. 130. 
    Rahman MM, Bobadilla L, Rapp B. 2016. Sampling-based planning algorithms for multi-objective missions. 2016 IEEE International Conference on Automation Science and Engineering709–14 Piscataway, NJ: IEEE
     [Google Scholar]
  131. 131. 
    Hollinger GA, Sukhatme GS. 2014. Sampling-based robotic information gathering algorithms. Int. J. Robot. Res 33:1271–87
     [Google Scholar]
  132. 132. 
    Jadidi MG, Miro JV, Dissanayake G. 2019. Sampling-based incremental information gathering with applications to robotic exploration and environmental monitoring. Int. J. Robot. Res. 38:658–85
     [Google Scholar]
  133. 133. 
    Sayre-McCord T, Karaman S. 2018. Perception-driven sparse graphs for optimal motion planning. 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems8110–17 Piscataway, NJ: IEEE
     [Google Scholar]
  134. 134. 
    Shome R, Solovey K, Dobson A, Halperin D, Bekris KE. 2020. dRRT*: scalable and informed asymptotically-optimal multi-robot motion planning. Auton. Robots 44:443–67
     [Google Scholar]
  135. 135. 
    Shome R, Bekris KE. 2017. Improving the scalability of asymptotically optimal motion planning for humanoid dual-arm manipulators. 2017 IEEE-RAS 17th International Conference on Humanoid Robotics271–77 Piscataway, NJ: IEEE
     [Google Scholar]
  136. 136. 
    Lee H, Kim H, Kim HJ. 2018. Planning and control for collision-free cooperative aerial transportation. IEEE Trans. Autom. Sci. Eng. 15:189–201
     [Google Scholar]
  137. 137. 
    Schmitt PS, Neubauer W, Feiten W, Wurm KM, Wichert GV, Burgard W. 2017. Optimal, sampling-based manipulation planning. 2017 IEEE International Conference on Robotics and Automation3426–32 Piscataway, NJ: IEEE
     [Google Scholar]
  138. 138. 
    Shome R, Bekris KE. 2019. Anytime multi-arm task and motion planning for pick-and-place of individual objects via handoffs. 2019 International Symposium on Multi-Robot and Multi-Agent Systems37–43 Piscataway, NJ: IEEE
     [Google Scholar]
  139. 139. 
    Bry A, Roy N. 2011. Rapidly-exploring Random Belief Trees for motion planning under uncertainty. 2011 IEEE International Conference on Robotics and Automation723–30 Piscataway, NJ: IEEE
     [Google Scholar]
  140. 140. 
    Luders BD, Karaman S, How JP. 2013. Robust sampling-based motion planning with asymptotic optimality guarantees. AIAA Guidance, Navigation, and Control Conference pap. 2013–5097 Reston, VA: Am. Inst. Aeronaut. Astronaut.
     [Google Scholar]
  141. 141. 
    Bopardikar SD, Englot B, Speranzon A, van den Berg J. 2016. Robust belief space planning under intermittent sensing via a maximum eigenvalue-based bound. Int. J. Robot. Res. . 35:1609–26
     [Google Scholar]
  142. 142. 
    Sun W, Torres LG, van den Berg J, Alterovitz R 2016. Safe motion planning for imprecise robotic manipulators by minimizing probability of collision. Robotics Research: The 16th International Symposium ISRR M Inaba, P Corke 685–701 Cham, Switz: Springer
     [Google Scholar]
  143. 143. 
    Virani N, Zhu M. 2016. Robust adaptive motion planning in the presence of dynamic obstacles. 2016 American Control Conference2104–9 Piscataway, NJ: IEEE
     [Google Scholar]
  144. 144. 
    Yang H, Lim J, Yoon S. 2016. Anytime RRBT for handling uncertainty and dynamic objects. 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems4786–93 Piscataway, NJ: IEEE
     [Google Scholar]
  145. 145. 
    Luders BD, How JP. 2014. An optimizing sampling-based motion planner with guaranteed robustness to bounded uncertainty. 2014 American Control Conference771–77 Piscataway, NJ: IEEE
     [Google Scholar]
  146. 146. 
    Shan T, Englot B. 2017. Belief roadmap search: advances in optimal and efficient planning under uncertainty. 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems5318–25 Piscataway, NJ: IEEE
     [Google Scholar]
  147. 147. 
    Littlefield Z, Klimenko D, Kurniawati H, Bekris KE 2018. The importance of a suitable distance function in belief-space planning. Robotics Research: Volume 2 A Bicchi, W Burgard 683–700 Cham, Switz: Springer
     [Google Scholar]
  148. 148. 
    Otte M, Frazzoli E. 2016. RRTX: asymptotically optimal single-query sampling-based motion planning with quick replanning. Int. J. Robot. Res 35:797–822
     [Google Scholar]
  149. 149. 
    Chen Y, He Z, Li S 2019. Horizon-based lazy optimal RRT for fast, efficient replanning in dynamic environment. Auton. Robots 43:2271–92
     [Google Scholar]
  150. 150. 
    Janson L, Hu T, Pavone M 2018. Safe motion planning in unknown environments: optimality benchmarks and tractable policies. Robotics: Science and Systems XIV H Kress-Gazit, S Srinivasa, T Howard, N Atanasov, pap. 61 N.p.: Robot. Sci. Syst. Found.
     [Google Scholar]
/content/journals/10.1146/annurev-control-061920-093753
Loading
Asymptotically Optimal Sampling-Based Motion Planning Methods
Annual Review of Control, Robotics, and Autonomous Systems 4, 295 (2021); https://doi.org/10.1146/annurev-control-061920-093753
/content/journals/10.1146/annurev-control-061920-093753
/content/journals/10.1146/annurev-control-061920-093753
Loading

Data & Media loading...

  • Article Type: Review Article

Most Cited Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error