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

Annual Review of Control, Robotics, and Autonomous Systems

Volume 7, 2024

Sampling-Based Motion Planning: A Comparative Review

Abstract

Sampling-based motion planning is one of the fundamental paradigms to generate robot motions, and a cornerstone of robotics research. This comparative review provides an up-to-date guide and reference manual for the use of sampling-based motion planning algorithms. It includes a history of motion planning, an overview of the most successful planners, and a discussion of their properties. It also shows how planners can handle special cases and how extensions of motion planning can be accommodated. To put sampling-based motion planning into a larger context, a discussion of alternative motion generation frameworks highlights their respective differences from sampling-based motion planning. Finally, a set of sampling-based motion planners are compared on 24 challenging planning problems in order to provide insights into which planners perform well in which situations and where future research would be required. This comparative review thereby provides not only a useful reference manual for researchers in the field but also a guide for practitioners to make informed algorithmic decisions.

Keyword(s): motion generation, motion planning, path planning
Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-061623-094742
2024-07-10
2024-12-04
Loading full text...

Full text loading...

/deliver/fulltext/control/7/1/annurev-control-061623-094742.html?itemId=/content/journals/10.1146/annurev-control-061623-094742&mimeType=html&fmt=ahah

Literature Cited

  1. 1.
    Kavraki LE, Svestka P, Latombe JC, Overmars MH. 1996.. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. . IEEE Trans. Robot. 12:(4):566–80
     [Crossref] [Google Scholar]
  2. 2.
    Hsu D, Latombe JC, Motwani R. 1999.. Path planning in expansive configuration spaces. . Int. J. Comput. Geom. Appl. 9:(4–5):495–512
     [Crossref] [Google Scholar]
  3. 3.
    Kuffner JJ, LaValle SM. 2000.. RRT-Connect: an efficient approach to single-query path planning. . In 2000 IEEE International Conference on Robotics and Automation, Vol. 2, pp. 995–1001. Piscataway, NJ:: IEEE
     [Google Scholar]
  4. 4.
    Karaman S, Frazzoli E. 2011.. Sampling-based algorithms for optimal motion planning. . Int. J. Robot. Res. 30:(7):846–94
     [Crossref] [Google Scholar]
  5. 5.
    Hartmann VN, Orthey A, Driess D, Oguz OS, Toussaint M. 2023.. Long-horizon multi-robot rearrangement planning for construction assembly. . IEEE Trans. Robot. 39:(1):239–52
     [Crossref] [Google Scholar]
  6. 6.
    Hönig W, Preiss JA, Kumar TKS, Sukhatme GS, Ayanian N. 2018.. Trajectory planning for quadrotor swarms. . IEEE Trans. Robot. 34:(4):856–69
     [Crossref] [Google Scholar]
  7. 7.
    Claussmann L, Revilloud M, Gruyer D, Glaser S. 2019.. A review of motion planning for highway autonomous driving. . IEEE Trans. Intell. Transp. Syst. 21:(5):1826–48
     [Crossref] [Google Scholar]
  8. 8.
    Murray S, Floyd-Jones W, Qi Y, Sorin DJ, Konidaris GD. 2016.. Robot motion planning on a chip. . In Robotics: Science and Systems XII, ed. D Hsu, N Amato, S Berman, S Jacobs, pap. 4 . N.p.:: Robot. Sci. Syst. Found.
     [Google Scholar]
  9. 9.
    Al-Bluwi I, Siméon T, Cortés J. 2012.. Motion planning algorithms for molecular simulations: a survey. . Comput. Sci. Rev. 6:(4):125–43
     [Crossref] [Google Scholar]
  10. 10.
    Chamzas C, Quintero-Peña C, Kingston Z, Orthey A, Rakita D, et al. 2022.. MotionBenchMaker: a tool to generate and benchmark motion planning datasets. . IEEE Robot. Autom. Lett. 7:(2):882–89
     [Crossref] [Google Scholar]
  11. 11.
    Cohen BJ, Chitta S, Likhachev M. 2010.. Search-based planning for manipulation with motion primitives. . In 2010 IEEE International Conference on Robotics and Automation, pp. 2902–8. Piscataway, NJ:: IEEE
     [Google Scholar]
  12. 12.
    Toussaint M. 2017.. A tutorial on Newton methods for constrained trajectory optimization and relations to SLAM, Gaussian process smoothing, optimal control, and probabilistic inference. . In Geometric and Numerical Foundations of Movements, ed. JP Laumond, N Mansard, JB Lasserre , pp. 361–92. Cham, Switz:.: Springer
     [Google Scholar]
  13. 13.
    Cheng CA, Mukadam M, Issac J, Birchfield S, Fox D, et al. 2021.. RMPflow: a geometric framework for generation of multitask motion policies. . IEEE Trans. Autom. Sci. Eng. 18:(3):968–87
     [Crossref] [Google Scholar]
  14. 14.
    Kober J, Bagnell JA, Peters J. 2013.. Reinforcement learning in robotics: a survey. . Int. J. Robot. Res. 32:(11):1238–74
     [Crossref] [Google Scholar]
  15. 15.
    Lozano-Pérez T, Wesley MA. 1979.. An algorithm for planning collision-free paths among polyhedral obstacles. . Commun. ACM 22:(10):560–70
     [Crossref] [Google Scholar]
  16. 16.
    Lozano-Pérez T. 1983.. Spatial planning: a configuration space approach. . IEEE Trans. Comput. C-32:(2):108–20
     [Crossref] [Google Scholar]
  17. 17.
    Schwartz JT, Sharir M. 1983.. On the ``piano movers'' problem. II. General techniques for computing topological properties of real algebraic manifolds. . Adv. Appl. Math. 4:(3):298–351
     [Crossref] [Google Scholar]
  18. 18.
    Reif JH. 1979.. Complexity of the mover's problem and generalizations. . In 20th Annual Symposium on Foundations of Computer Science, pp. 421–27. Piscataway, NJ:: IEEE
     [Google Scholar]
  19. 19.
    Canny J, Reif J. 1987.. New lower bound techniques for robot motion planning problems. . In 28th Annual Symposium on Foundations of Computer Science, pp. 49–60. Piscataway, NJ:: IEEE
     [Google Scholar]
  20. 20.
    Canny J. 1988.. The Complexity of Robot Motion Planning. Cambridge, MA:: MIT Press
     [Google Scholar]
  21. 21.
    Khatib O. 1986.. Real-time obstacle avoidance for manipulators and mobile robots. . In Autonomous Robot Vehicles, ed. IJ Cox, GT Wilfong , pp. 396–404. New York:: Springer
     [Google Scholar]
  22. 22.
    Sato K. 1992.. Deadlock-free motion planning using the laplace potential field. . Adv. Robot. 7:(5):449–61
     [Crossref] [Google Scholar]
  23. 23.
    Koditschek D. 1987.. Exact robot navigation by means of potential functions: some topological considerations. . In 1987 IEEE International Conference on Robotics and Automation, Vol. 1, pp. 1–6. Piscataway, NJ:: IEEE
     [Google Scholar]
  24. 24.
    Koditschek DE, Rimon E. 1990.. Robot navigation functions on manifolds with boundary. . Adv. Appl. Math. 11:(4):412–42
     [Crossref] [Google Scholar]
  25. 25.
    Barraquand J, Langlois B, Latombe JC. 1992.. Numerical potential field techniques for robot path planning. . IEEE Trans. Syst. Man Cybernet. 22:(2):224–41
     [Crossref] [Google Scholar]
  26. 26.
    Latombe JC. 1999.. Motion planning: a journey of robots, molecules, digital actors, and other artifacts. . Int. J. Robot. Res. 18:(11):1119–28
     [Crossref] [Google Scholar]
  27. 27.
    Barraquand J, Latombe JC. 1991.. Robot motion planning: a distributed representation approach. . Int. J. Robot. Res. 10:(6):628–49
     [Crossref] [Google Scholar]
  28. 28.
    Sánchez G, Latombe JC. 2003.. A single-query bi-directional probabilistic roadmap planner with lazy collision checking. . In Robotics Research: The Tenth International Symposium, ed. RA Jarvis, A Zelinsky , pp. 403–17. Berlin:: Springer
     [Google Scholar]
  29. 29.
    LaValle SM. 1998.. Rapidly-exploring random trees: a new tool for path planning. Tech. Rep. , Iowa State Univ., Ames:
     [Google Scholar]
  30. 30.
    Barraquand J, Kavraki LE, Latombe JC, Li TY, Motwani R, Raghavan P. 1996.. A random sampling scheme for path planning. . In Robotics Research: The Seventh International Symposium, ed. G Giralt, G Hirzinger , pp. 249–64. London:: Springer
     [Google Scholar]
  31. 31.
    Amato NM, Bayazit OB, Dale LK, Jones C, Vallejo D. 1998.. OBPRM: an obstacle-based PRM for 3D workspaces. . In Robotics: The Algorithmic Perspective, ed. PK Agarwal, LE Kavraki, MT Mason , pp. 155–68. Boca Raton, FL:: CRC
     [Google Scholar]
  32. 32.
    Hsu D, Kavraki LE, Latombe JC, Motwani R, Sorkin S. 1998.. On finding narrow passages with probabilistic roadmap planners. . In Robotics: The Algorithmic Perspective, ed. PK Agarwal, LE Kavraki, MT Mason , pp. 141–54. Boca Raton, FL:: CRC
     [Google Scholar]
  33. 33.
    Hsu D, Jiang T, Reif J, Sun Z. 2003.. The bridge test for sampling narrow passages with probabilistic roadmap planners. . In 2003 IEEE International Conference on Robotics and Automation, Vol. 3, pp. 4420–26. Piscataway, NJ:: IEEE
     [Google Scholar]
  34. 34.
    Boor V, Overmars MH, Van Der Stappen AF. 1999.. The Gaussian sampling strategy for probabilistic roadmap planners. . In 1999 IEEE International Conference on Robotics and Automation, Vol. 2, pp. 1018–23. Piscataway, NJ:: IEEE
     [Google Scholar]
  35. 35.
    Van den Berg JP, Overmars MH. 2005.. Using workspace information as a guide to non-uniform sampling in probabilistic roadmap planners. . Int. J. Robot. Res. 24:(12):1055–71
     [Crossref] [Google Scholar]
  36. 36.
    Yang Y, Brock O. 2005.. Efficient motion planning based on disassembly. . In Robotics: Science and Systems I, ed. S Thrun, GS Sukhatme, S Schaal , pp. 97–104. Cambridge, MA:: MIT Press
     [Google Scholar]
  37. 37.
    Kurniawati H, Hsu D. 2004.. Workspace importance sampling for probabilistic roadmap planning. . In IEEE International Conference on Intelligent Robots and Systems, Vol. 2, pp. 1618–23. Piscataway, NJ:: IEEE
     [Google Scholar]
  38. 38.
    Wilmarth SA, Amato NM, Stiller PF. 1999.. MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space. . In 1999 IEEE International Conference on Robotics and Automation, Vol. 2, pp. 1024–31. Piscataway, NJ:: IEEE
     [Google Scholar]
  39. 39.
    Burns B, Brock O. 2005.. Toward optimal configuration space sampling. . In Robotics: Science and Systems I, ed. S Thrun, GS Sukhatme, S Schaal , pp. 105–12. Cambridge, MA:: MIT Press
     [Google Scholar]
  40. 40.
    Yershova A, Jaillet L, Siméon T, LaValle SM. 2005.. Dynamic-domain RRTs: efficient exploration by controlling the sampling domain. . In 2005 IEEE International Conference on Robotics and Automation, pp. 3856–61. Piscataway, NJ:: IEEE
     [Google Scholar]
  41. 41.
    Yershova A, LaValle SM. 2009.. Motion planning for highly constrained spaces. . In Robot Motion and Control 2009, ed. KR Kozłowski , pp. 297–306. London:: Springer
     [Google Scholar]
  42. 42.
    Geraerts R, Overmars MH. 2007.. Creating high-quality paths for motion planning. . Int. J. Robot. Res. 26:(8):845–63
     [Crossref] [Google Scholar]
  43. 43.
    Van den Berg J, Overmars M. 2008.. Planning time-minimal safe paths amidst unpredictably moving obstacles. . Int. J. Robot. Res. 27:(11–12):1274–94
     [Crossref] [Google Scholar]
  44. 44.
    Raveh B, Enosh A, Halperin D. 2011.. A little more, a lot better: improving path quality by a path-merging algorithm. . IEEE Trans. Robot. 27:(2):365–71
     [Crossref] [Google Scholar]
  45. 45.
    Luna R, Şucan IA, Moll M, Kavraki LE. 2013.. Anytime solution optimization for sampling-based motion planning. . In 2013 IEEE International Conference on Robotics and Automation, pp. 5068–74. Piscataway, NJ:: IEEE
     [Google Scholar]
  46. 46.
    Solovey K, Kleinbort M. 2020.. The critical radius in sampling-based motion planning. . Int. J. Robot. Res. 39:(2–3):266–85
     [Crossref] [Google Scholar]
  47. 47.
    Berenson D, Abbeel P, Goldberg K. 2012.. A robot path planning framework that learns from experience. . In 2012 IEEE International Conference on Robotics and Automation, pp. 3671–78. Piscataway, NJ:: IEEE
     [Google Scholar]
  48. 48.
    Coleman D, Şucan IA, Moll M, Okada K, Correll N. 2015.. Experience-based planning with sparse roadmap spanners. . In 2015 IEEE International Conference on Robotics and Automation, pp. 900–5. Piscataway, NJ:: IEEE
     [Google Scholar]
  49. 49.
    Lien JM, Lu Y. 2010.. Planning motion in environments with similar obstacles. . In Robotics: Science and Systems V, ed. J Trinkle, Y Matsuoka, JA Castellanos , pp. 89–96. Cambridge, MA:: MIT Press
     [Google Scholar]
  50. 50.
    Lehner P, Albu-Schäffer A. 2018.. The repetition roadmap for repetitive constrained motion planning. . IEEE Robot. Autom. Lett. 3:(3):3884–91
     [Crossref] [Google Scholar]
  51. 51.
    Chamzas C, Kingston Z, Quintero-Peña C, Shrivastava A, Kavraki LE. 2021.. Learning sampling distributions using local 3D workspace decompositions for motion planning in high dimensions. . In 2021 IEEE International Conference on Robotics and Automation, pp. 1283–89. Piscataway, NJ:: IEEE
     [Google Scholar]
  52. 52.
    Ichter B, Harrison J, Pavone M. 2018.. Learning sampling distributions for robot motion planning. . In 2018 IEEE International Conference on Robotics and Automation, pp. 7087–94. Piscataway, NJ:: IEEE
     [Google Scholar]
  53. 53.
    Chamzas C, Cullen A, Shrivastava A, Kavraki LE. 2022.. Learning to retrieve relevant experiences for motion planning. . In 2022 IEEE International Conference on Robotics and Automation, pp. 7233–40. Piscataway, NJ:: IEEE
     [Google Scholar]
  54. 54.
    McMahon T, Sivaramakrishnan A, Granados E, Bekris KE. 2022.. A survey on the integration of machine learning with sampling-based motion planning. . Found. Trends Robot. 9:(4):266–327
     [Crossref] [Google Scholar]
  55. 55.
    Choset H, Lynch KM, Hutchinson S, Kantor GA, Burgard W. 2005.. Principles of Robot Motion: Theory, Algorithms, and Implementations. Cambridge, MA:: MIT Press
     [Google Scholar]
  56. 56.
    LaValle SM. 2006.. Planning Algorithms. Cambridge, UK:: Cambridge Univ. Press
     [Google Scholar]
  57. 57.
    Lynch KM, Park FC. 2017.. Modern Robotics. Cambridge, UK:: Cambridge Univ. Press
     [Google Scholar]
  58. 58.
    Farber M. 2003.. Topological complexity of motion planning. . Discrete Comput. Geom. 29:(2):211–21
     [Crossref] [Google Scholar]
  59. 59.
    Lee JM. 2003.. Introduction to Smooth Manifolds. New York:: Springer
     [Google Scholar]
  60. 60.
    Čech E, Frolík Z, Katětov M. 1966.. Topological Spaces. Prague:: Academia
     [Google Scholar]
  61. 61.
    Wilson WA. 1931.. On quasi-metric spaces. . Am. J. Math. 53:(3):675–84
     [Crossref] [Google Scholar]
  62. 62.
    Grothe F, Hartmann VN, Orthey A, Toussaint M. 2022.. ST-RRT*: asymptotically-optimal bidirectional motion planning through space-time. . In 2022 IEEE International Conference on Robotics and Automation, pp. 3314–20. Piscataway, NJ:: IEEE
     [Google Scholar]
  63. 63.
    Wilson WA. 1931.. On semi-metric spaces. . Am. J. Math. 53:(2):361–73
     [Crossref] [Google Scholar]
  64. 64.
    Wang G, Zhang B, Ng TE. 2007.. Towards network triangle inequality violation aware distributed systems. . In IMC '07: Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, pp. 175–88. New York:: ACM
     [Google Scholar]
  65. 65.
    Ladd AM, Kavraki LE. 2004.. Fast tree-based exploration of state space for robots with dynamics. . In Algorithmic Foundations of Robotics VI, ed. M Erdmann, M Overmars, D Hsu, F van der Stappen , pp. 297–312. Berlin:: Springer
     [Google Scholar]
  66. 66.
    Bertsekas D, Tsitsiklis JN. 2008.. Introduction to Probability, Vol. 1. Belmont, MA:: Athena Sci.
     [Google Scholar]
  67. 67.
    Janson L, Ichter B, Pavone M. 2018.. Deterministic sampling-based motion planning: optimality, complexity, and performance. . Int. J. Robot. Res. 37:(1):46–61
     [Crossref] [Google Scholar]
  68. 68.
    Palmieri L, Bruns L, Meurer M, Arras KO. 2019.. Dispertio: optimal sampling for safe deterministic motion planning. . IEEE Robot. Autom. Lett. 5:(2):362–68
     [Crossref] [Google Scholar]
  69. 69.
    Verginis CK, Dimarogonas DV, Kavraki LE. 2023.. KDF: kinodynamic motion planning via geometric sampling-based algorithms and funnel control. . IEEE Trans. Robot. 39:(2):978–97
     [Crossref] [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. . In 2016 IEEE International Conference on Robotics and Automation, pp. 4207–14. Piscataway, NJ:: IEEE
     [Google Scholar]
  71. 71.
    Faust A, Ramirez O, Fiser M, Oslund K, Francis A, et al. 2018.. PRM-RL: long-range robotic navigation tasks by combining reinforcement learning and sampling-based planning. . In 2018 IEEE International Conference on Robotics and Automation, pp. 5113–20. Piscataway, NJ:: IEEE
     [Google Scholar]
  72. 72.
    Dobson A, Bekris KE. 2014.. Sparse roadmap spanners for asymptotically near-optimal motion planning. . Int. J. Robot. Res. 33:(1):18–47
     [Crossref] [Google Scholar]
  73. 73.
    Salzman O, Halperin D. 2016.. Asymptotically near-optimal RRT for fast, high-quality motion planning. . IEEE Trans. Robot. 32:(3):473–83
     [Crossref] [Google Scholar]
  74. 74.
    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:(7):883–921
     [Crossref] [Google Scholar]
  75. 75.
    Bohlin R, Kavraki LE. 2000.. Path planning using lazy PRM. . In 2000 IEEE International Conference on Robotics and Automation, Vol. 1, pp. 521–28. Piscataway, NJ:: IEEE
     [Google Scholar]
  76. 76.
    Hauser K. 2015.. Lazy collision checking in asymptotically-optimal motion planning. . In 2015 IEEE International Conference on Robotics and Automation, pp. 2951–57. Piscataway, NJ:: IEEE
     [Google Scholar]
  77. 77.
    Mandalika A, Choudhury S, Salzman O, Srinivasa S. 2019.. Generalized lazy search for robot motion planning: interleaving search and edge evaluation via event-based toggles. . In Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, ed. J Benton, N Lipovetsky, E Onaindia, DE Smith, S Srivastava , pp. 745–53. Palo Alto, CA:: AAAI Press
     [Google Scholar]
  78. 78.
    Orthey A, Toussaint M. 2019.. Rapidly-exploring quotient-space trees: motion planning using sequential simplifications. . In Robotics Research: The 19th International Symposium ISRR, ed. T Asfour, E Yoshida, J Park, H Christensen, O Khatib , pp. 52–68. Cham, Switz:.: Springer
     [Google Scholar]
  79. 79.
    Klemm S, Oberländer J, Hermann A, Roennau A, Schamm T, et al. 2015.. RRT*-Connect: faster, asymptotically optimal motion planning. . In 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 1670–77. Piscataway, NJ:: IEEE
     [Google Scholar]
  80. 80.
    Siméon T, Laumond JP, Nissoux C. 2000.. Visibility-based probabilistic roadmaps for motion planning. . Adv. Robot. 14:(6):477–93
     [Crossref] [Google Scholar]
  81. 81.
    Li Y, Littlefield Z, Bekris KE. 2016.. Asymptotically optimal sampling-based kinodynamic planning. . Int. J. Robot. Res. 35:(5):528–64
     [Crossref] [Google Scholar]
  82. 82.
    Pearl J. 1984.. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Reading, MA:: Addison-Wesley
     [Google Scholar]
  83. 83.
    Gammell JD, Srinivasa SS, Barfoot TD. 2014.. Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. . In 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2997–3004. Piscataway, NJ:: IEEE
     [Google Scholar]
  84. 84.
    Gammell JD, Barfoot TD, Srinivasa SS. 2020.. Batch informed trees (BIT*): informed asymptotically optimal anytime search. . Int. J. Robot. Res. 39:(5):543–67
     [Crossref] [Google Scholar]
  85. 85.
    Strub MP, Gammell JD. 2020.. Advanced BIT* (ABIT*): sampling-based planning with advanced graph-search techniques. . In 2020 IEEE International Conference on Robotics and Automation, pp. 130–36. Piscataway, NJ:: IEEE
     [Google Scholar]
  86. 86.
    Şucan IA, Kavraki LE. 2009.. Kinodynamic motion planning by interior-exterior cell exploration. . In Algorithmic Foundation of Robotics VIII, ed. GS Chirikjian, H Choset, M Morales, T Murphey , pp. 449–64. Berlin:: Springer
     [Google Scholar]
  87. 87.
    Şucan IA, Kavraki LE. 2011.. A sampling-based tree planner for systems with complex dynamics. . IEEE Trans. Robot. 28:(1):116–31
     [Crossref] [Google Scholar]
  88. 88.
    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:(5):786–811
     [Crossref] [Google Scholar]
  89. 89.
    Şucan IA, Moll M, Kavraki LE. 2012.. The Open Motion Planning Library. . IEEE Robot. Autom. Mag. 19:(4):72–82
     [Crossref] [Google Scholar]
  90. 90.
    Moll M, Chamzas C, Kingston Z, Kavraki LE. 2021.. HyperPlan: a framework for motion planning algorithm selection and parameter optimization. . In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2511–18. Piscataway, NJ:: IEEE
     [Google Scholar]
  91. 91.
    Cano J, Yang Y, Bodin B, Nagarajan V, O'Boyle M. 2018.. Automatic parameter tuning of motion planning algorithms. . In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 8103–9. Piscataway, NJ:: IEEE
     [Google Scholar]
  92. 92.
    Gammell JD, Strub MP. 2021.. A survey of asymptotically optimal sampling-based motion planning methods. . Annu. Rev. Control Robot. Auton. Syst. 4::295–318
     [Crossref] [Google Scholar]
  93. 93.
    Gammell JD, Barfoot TD, Srinivasa SS. 2018.. Informed sampling for asymptotically optimal path planning. . IEEE Trans. Robot. 34:(4):966–84
     [Crossref] [Google Scholar]
  94. 94.
    Orthey A, Toussaint M. 2021.. Sparse multilevel roadmaps for high-dimensional robot motion planning. . In 2021 IEEE International Conference on Robotics and Automation, pp. 7851–57. Piscataway, NJ:: IEEE
     [Google Scholar]
  95. 95.
    McCarthy Z, Bretl T, Hutchinson S. 2012.. Proving path non-existence using sampling and alpha shapes. . In 2012 IEEE International Conference on Robotics and Automation, pp. 2563–69. Piscataway, NJ:: IEEE
     [Google Scholar]
  96. 96.
    Varava A, Carvalho JF, Pokorny FT, Kragic D. 2021.. Free space of rigid objects: caging, path non-existence, and narrow passage detection. . Int. J. Robot. Res. 40:(10–11):1049–67
     [Crossref] [Google Scholar]
  97. 97.
    Li S, Dantam N. 2021.. Learning proofs of motion planning infeasibility. . In Robotics: Science and Systems XVII, ed. D Shell, M Toussaint, MA Hsieh, pap. 64 . N.p.:: Robot. Sci. Syst. Found.
     [Google Scholar]
  98. 98.
    Dubins LE. 1957.. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. . Am. J. Math. 79:(3):497–516
     [Crossref] [Google Scholar]
  99. 99.
    Reeds J, Shepp L. 1990.. Optimal paths for a car that goes both forwards and backwards. . Pac. J. Math. 145:(2):367–93
     [Crossref] [Google Scholar]
  100. 100.
    LaValle SM, Kuffner JJ. 2001.. Randomized kinodynamic planning. . Int. J. Robot. Res. 20:(5):378–400
     [Crossref] [Google Scholar]
  101. 101.
    Hauser K, Zhou Y. 2016.. Asymptotically optimal planning by feasible kinodynamic planning in a state–cost space. . IEEE Trans. Robot. 32:(6):1431–43
     [Crossref] [Google Scholar]
  102. 102.
    Mukadam M, Dong J, Yan X, Dellaert F, Boots B. 2018.. Continuous-time Gaussian process motion planning via probabilistic inference. . Int. J. Robot. Res. 37:(11):1319–40
     [Crossref] [Google Scholar]
  103. 103.
    Kamat J, Ortiz-Haro J, Toussaint M, Pokorny FT, Orthey A. 2022.. BITKOMO: combining sampling and optimization for fast convergence in optimal motion planning. . In 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4492–97. Piscataway, NJ:: IEEE
     [Google Scholar]
  104. 104.
    Alwala KV, Mukadam M. 2021.. Joint sampling and trajectory optimization over graphs for online motion planning. . In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4700–7. Piscataway, NJ:: IEEE
     [Google Scholar]
  105. 105.
    Kingston Z, Moll M, Kavraki LE. 2018.. Sampling-based methods for motion planning with constraints. . Annu. Rev. Control Robot. Auton. Syst. 1::159–85
     [Crossref] [Google Scholar]
  106. 106.
    Berenson D, Srinivasa S, Kuffner J. 2011.. Task space regions: a framework for pose-constrained manipulation planning. . Int. J. Robot. Res. 30:(12):1435–60
     [Crossref] [Google Scholar]
  107. 107.
    Phillips M, Likhachev M. 2011.. SIPP: safe interval path planning for dynamic environments. . In 2011 IEEE International Conference on Robotics and Automation, pp. 5628–35. Piscataway, NJ:: IEEE
     [Google Scholar]
  108. 108.
    Otte M, Frazzoli E. 2016.. RRTX: asymptotically optimal single-query sampling-based motion planning with quick replanning. . Int. J. Robot. Res. 35:(7):797–822
     [Crossref] [Google Scholar]
  109. 109.
    Kurniawati H. 2022.. Partially observable Markov decision processes and robotics. . Annu. Rev. Control Robot. Auton. Syst. 5::253–77
     [Crossref] [Google Scholar]
  110. 110.
    Phiquepal C, Orthey A, Viennot N, Toussaint M. 2022.. Path-tree optimization in discrete partially observable environments using rapidly-exploring belief-space graphs. . IEEE Robot. Autom. Lett. 7:(4):10160–67
     [Crossref] [Google Scholar]
  111. 111.
    Elimelech K, Indelman V. 2022.. Simplified decision making in the belief space using belief sparsification. . Int. J. Robot. Res. 41:(5):470–96
     [Crossref] [Google Scholar]
  112. 112.
    Ko I, Kim B, Park FC. 2014.. Randomized path planning on vector fields. . Int. J. Robot. Res. 33:(13):1664–82
     [Crossref] [Google Scholar]
  113. 113.
    Tang Z, Chen B, Lan R, Li S. 2020.. Vector field guided RRT* based on motion primitives for quadrotor kinodynamic planning. . J. Intell. Robot. Syst. 100::1325–39
     [Crossref] [Google Scholar]
  114. 114.
    Hernández JD, Vidal E, Moll M, Palomeras N, Carreras M, Kavraki LE. 2019.. Online motion planning for unexplored underwater environments using autonomous underwater vehicles. . J. Field Robot. 36:(2):370–96
     [Crossref] [Google Scholar]
  115. 115.
    Vidal E, Moll M, Palomeras N, Hernández JD, Carreras M, Kavraki LE. 2019.. Online multilayered motion planning with dynamic constraints for autonomous underwater vehicles. . In 2019 IEEE International Conference on Robotics and Automation, pp. 8936–42. Piscataway, NJ:: IEEE
     [Google Scholar]
  116. 116.
    Boyd S, Vandenberghe L. 2004.. Convex Optimization. Cambridge, UK:: Cambridge Univ. Press
     [Google Scholar]
  117. 117.
    Hauser K. 2014.. Fast interpolation and time-optimization with contact. . Int. J. Robot. Res. 33:(9):1231–50
     [Crossref] [Google Scholar]
  118. 118.
    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:(9–10):1164–93
     [Crossref] [Google Scholar]
  119. 119.
    Schulman J, Duan Y, Ho J, Lee A, Awwal I, et al. 2014.. Motion planning with sequential convex optimization and convex collision checking. . Int. J. Robot. Res. 33:(9):1251–70
     [Crossref] [Google Scholar]
  120. 120.
    Schaal S. 2006.. Dynamic movement primitives—a framework for motor control in humans and humanoid robotics. . In Adaptive Motion of Animals and Machines, ed. H Kimura, K Tsuchiya, A Ishiguro, H Witte , pp. 261–80. Tokyo:: Springer
     [Google Scholar]
  121. 121.
    Kober J, Peters J. 2011.. Policy search for motor primitives in robotics. . Mach. Learn. 84:(1–2):171–203
     [Crossref] [Google Scholar]
  122. 122.
    Kober J, Bagnell JA, Peters J. 2013.. Reinforcement learning in robotics: a survey. . Int. J. Robot. Res. 32:(11):1238–74
     [Crossref] [Google Scholar]
  123. 123.
    Paraschos A, Daniel C, Peters J, Neumann G. 2018.. Using probabilistic movement primitives in robotics. . Auton. Robots 42::529–51
     [Crossref] [Google Scholar]
  124. 124.
    Giszter SF. 2015.. Motor primitives—new data and future questions. . Curr. Opin. Neurobiol. 33::156–65
     [Crossref] [Google Scholar]
  125. 125.
    Graziano M. 2008.. The Intelligent Movement Machine: An Ethological Perspective on the Primate Motor System. Oxford, UK:: Oxford Univ. Press
     [Google Scholar]
  126. 126.
    Bhardwaj M, Sundaralingam B, Mousavian A, Ratliff ND, Fox D, et al. 2022.. STORM: an integrated framework for fast joint-space model-predictive control for reactive manipulation. . In Proceedings of the 5th Conference on Robot Learning, ed. A Faust, D Hsu, G Neumann , pp. 750–59. Proc. Mach. Learn. Res. 164 . N.p.:: PMLR
     [Google Scholar]
  127. 127.
    Koenig S, Likhachev M, Furcy D. 2004.. Lifelong planning A*. . Artif. Intell. 155:(1–2):93–146
     [Crossref] [Google Scholar]
  128. 128.
    Ren Z, Rathinam S, Likhachev M, Choset H. 2022.. Multi-objective path-based D* lite. . IEEE Robot. Autom. Lett. 7:(2):3318–25
     [Crossref] [Google Scholar]
  129. 129.
    Hart PE, Nilsson NJ, Raphael B. 1968.. A formal basis for the heuristic determination of minimum cost paths. . IEEE Trans. Syst. Sci. Cybernet. 4:(2):100–7
     [Crossref] [Google Scholar]
  130. 130.
    Liu S, Mohta K, Atanasov N, Kumar V. 2018.. Search-based motion planning for aggressive flight in SE(3). . IEEE Robot. Autom. Lett. 3:(3):2439–46
     [Crossref] [Google Scholar]
  131. 131.
    Araki M. 2010.. PID control. . In Control Systems, Robotics, and Automation, Vol. 2: PID Control, ed. H Unbehauen , pp. 58–79. Oxford, UK:: EOLSS
     [Google Scholar]
  132. 132.
    Klemm V, Morra A, Gulich L, Mannhart D, Rohr D, et al. 2020.. LQR-assisted whole-body control of a wheeled bipedal robot with kinematic loops. . IEEE Robot. Autom. Lett. 5:(2):3745–52
     [Crossref] [Google Scholar]
  133. 133.
    Grandia R, Farshidian F, Ranftl R, Hutter M. 2019.. Feedback MPC for torque-controlled legged robots. . In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4730–37. Piscataway, NJ:: IEEE
     [Google Scholar]
  134. 134.
    Majumdar A, Tedrake R. 2017.. Funnel libraries for real-time robust feedback motion planning. . Int. J. Robot. Res. 36:(8):947–82
     [Crossref] [Google Scholar]
  135. 135.
    Sutton RS, Barto AG. 2018.. Reinforcement Learning: An Introduction. Cambridge, MA:: MIT Press
     [Google Scholar]
  136. 136.
    Watkins CJCH. 1989.. Learning from delayed rewards. PhD Thesis , King's Coll., Cambridge, UK:
     [Google Scholar]
  137. 137.
    Moll M, Şucan IA, Kavraki LE. 2015.. Benchmarking motion planning algorithms: an extensible infrastructure for analysis and visualization. . IEEE Robot. Autom. Mag. 22:(3):96–102
     [Crossref] [Google Scholar]
  138. 138.
    Hsu D, Latombe JC, Kurniawati H. 2006.. On the probabilistic foundations of probabilistic roadmap planning. . Int. J. Robot. Res. 25:(7):627–43
     [Crossref] [Google Scholar]
  139. 139.
    Kingston Z, Moll M, Kavraki LE. 2019.. Exploring implicit spaces for constrained sampling-based planning. . Int. J. Robot. Res. 38:(10–11):1151–78
     [Crossref] [Google Scholar]
  140. 140.
    Tsianos KI, Şucan IA, Kavraki LE. 2007.. Sampling-based robot motion planning: towards realistic applications. . Comput. Sci. Rev. 1:(1):2–11
     [Crossref] [Google Scholar]
  141. 141.
    Elbanhawi M, Simic M. 2014.. Sampling-based robot motion planning: a review. . IEEE Access 2::56–77
     [Crossref] [Google Scholar]
  142. 142.
    Mac TT, Copot C, Tran DT, De Keyser R. 2016.. Heuristic approaches in robot path planning: a survey. . Robot. Auton. Syst. 86::13–28
     [Crossref] [Google Scholar]
  143. 143.
    Gipson B, Hsu D, Kavraki LE, Latombe JC. 2012.. Computational models of protein kinematics and dynamics: beyond simulation. . Annu. Rev. Anal. Chem. 5::273–91
     [Crossref] [Google Scholar]
  144. 144.
    Al-Bluwi I, Siméon T, Cortés J. 2012.. Motion planning algorithms for molecular simulations: a survey. . Comput. Sci. Rev. 6:(4):125–43
     [Crossref] [Google Scholar]
  145. 145.
    Goerzen C, Kong Z, Mettler B. 2010.. A survey of motion planning algorithms from the perspective of autonomous UAV guidance. . J. Intell. Robot. Syst. 57:(1):65–100
     [Crossref] [Google Scholar]
  146. 146.
    Garrett CR, Chitnis R, Holladay R, Kim B, Silver T, et al. 2021.. Integrated task and motion planning. . Annu. Rev. Control Robot. Auton. Syst. 4::265–93
     [Crossref] [Google Scholar]
/content/journals/10.1146/annurev-control-061623-094742
Loading
Sampling-Based Motion Planning: A Comparative Review
Annual Review of Control, Robotics, and Autonomous Systems 7, 285 (2024); https://doi.org/10.1146/annurev-control-061623-094742
/content/journals/10.1146/annurev-control-061623-094742
/content/journals/10.1146/annurev-control-061623-094742
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