[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Motion Planning

  • Chapter
  • First Online:
Springer Handbook of Robotics

Part of the book series: Springer Handbooks ((SHB))

  • 95k Accesses

Abstract

This chapter first provides a formulation of the geometric path planning problem in Sect. 7.2 and then introduces sampling-based planning in Sect. 7.3. Sampling-based planners are general techniques applicable to a wide set of problems and have been successful in dealing with hard planning instances. For specific, often simpler, planning instances, alternative approaches exist and are presented in Sect. 7.4. These approaches provide theoretical guarantees and for simple planning instances they outperform sampling-based planners. Section 7.5 considers problems that involve differential constraints, while Sect. 7.6 overviews several other extensions of the basic problem formulation and proposed solutions. Finally, Sect. 7.8 addresses some important and more advanced topics related to motion planning.

figure a

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 223.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
GBP 279.99
Price includes VAT (United Kingdom)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Abbreviations

1-D:

one-dimensional

2-D:

two-dimensional

3-D:

three-dimensional

PRM:

probabilistic roadmap method

RDT:

rapidly exploring dense tree

RLG:

random loop generator

RRT:

rapidly exploring random tree

References

  1. J.H. Reif: Complexity of the mover's problem and generalizations, IEEE Symp. Found. Comput. Sci. (1979) pp. 421–427

    Google Scholar 

  2. H.H. Gonzalez-Banos, D. Hsu, J.C. Latombe: Motion planning: Recent developments. In: Automous Mobile Robots: Sensing, Control, Decision-Making and Applications, ed. by S.S. Ge, F.L. Lewis (CRC, Boca Raton 2006)

    Google Scholar 

  3. S.R. Lindemann, S.M. LaValle: Current issues in sampling-based motion planning, 11th Int. Symp. Robotics Res. (Springer, Berlin, Heidelberg 2005) pp. 36–54

    Google Scholar 

  4. J.T. Schwartz, M. Sharir: A survey of motion planning and related geometric algorithms, Artif. Intell. J. 37, 157–169 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  5. H. Choset, K.M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L.E. Kavraki, S. Thrun: Principles of Robot Motion: Theory, Algorithms, and Implementations (MIT, Cambridge 2005)

    MATH  Google Scholar 

  6. J.C. Latombe: Robot Motion Planning (Kluwer, Boston 1991)

    Book  MATH  Google Scholar 

  7. S.M. LaValle: Planning Algorithms (Cambridge Univ. Press, Cambridge 2006)

    Book  MATH  Google Scholar 

  8. S. Udupa: Collision detection and avoidance in computer controlled manipulators, Ph.D. Thesis (Dept. of Electical Engineering, California Institute of Technology, Pasadena 1977)

    Google Scholar 

  9. T. Lozano-Pérez: Spatial planning: A configuration space approach, IEEE Trans. Comput. C 32(2), 108–120 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  10. J.T. Schwartz, M. Sharir: On the piano movers' problem: III. Coordinating the motion of several independent bodies, Int. J. Robotics Res. 2(3), 97–140 (1983)

    Article  MATH  Google Scholar 

  11. J.T. Schwartz, M. Sharir: On the piano movers' problem: V. The case of a rod moving in three-dimensional space amidst polyhedral obstacles, Commun. Pure Appl. Math. 37, 815–848 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  12. J.F. Canny: The Complexity of Robot Motion Planning (MIT, Cambridge 1988)

    MATH  Google Scholar 

  13. D. Halperin, M. Sharir: A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment, Discret. Comput. Geom. 16, 121–134 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  14. J.E. Hopcroft, J.T. Schwartz, M. Sharir: On the complexity of motion planning for multiple independent objects: PSPACE-hardness of the warehouseman's problem, Int. J. Robotics Res. 3(4), 76–88 (1984)

    Article  Google Scholar 

  15. J. Canny, J. Reif: New lower bound techniques for robot motion planning problems, IEEE Symp. Found. Comput. Sci. (1987) pp. 49–60

    Google Scholar 

  16. M.C. Lin, J.F. Canny: Efficient algorithms for incremental distance computation, IEEE Int. Conf. Robotics Autom. (1991) pp. 1008–1014

    Google Scholar 

  17. P. Jiménez, F. Thomas, C. Torras: Collision detection algorithms for motion planning. In: Robot Motion Planning and Control, ed. by J.P. Laumond (Springer, Berlin, Heidelberg 1998) pp. 1–53

    Google Scholar 

  18. M.C. Lin, D. Manocha: Collision and proximity queries. In: Handbook of Discrete and Computational Geometry, 2nd edn., ed. by J.E. Goodman, J. O'Rourke (Chapman Hall/CRC, Boca Raton 2004) pp. 787–807

    Google Scholar 

  19. L.E. Kavraki, P. Svestka, J.C. Latombe, M.H. Overmars: Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Trans. Robotics Autom. 12(4), 566–580 (1996)

    Article  Google Scholar 

  20. N.M. Amato, O.B. Bayazit, L.K. Dale, C. Jones, D. Vallejo: OBPRM: An obstacle-based PRM for 3-D workspaces, Workshop Algorith. Found. Robotics (1998) pp. 155–168

    Google Scholar 

  21. V. Boor, M.H. Overmars, A.F. van der Stappen: The Gaussian sampling strategy for probabilistic roadmap planners, IEEE Int. Conf. Robotics Autom. (1999) pp. 1018–1023

    Google Scholar 

  22. C. Holleman, L.E. Kavraki: A framework for using the workspace medial axis in PRM planners, IEEE Int. Conf. Robotics Autom. (2000) pp. 1408–1413

    Google Scholar 

  23. J.M. Lien, S.L. Thomas, N.M. Amato: A general framework for sampling on the medial axis of the free space, IEEE Int. Conf. Robotics Autom. (2003)

    Google Scholar 

  24. S.M. LaValle, M.S. Branicky, S.R. Lindemann: On the relationship between classical grid search and probabilistic roadmaps, Int. J. Robotics Res. 23(7/8), 673–692 (2004)

    Article  Google Scholar 

  25. T. Siméon, J.-P. Laumond, C. Nissoux: Visibility based probabilistic roadmaps for motion planning, Adv. Robotics 14(6), 477–493 (2000)

    Article  Google Scholar 

  26. J. Barraquand, L. Kavraki, J.-C. Latombe, T.-Y. Li, R. Motwani, P. Raghavan: A random sampling scheme for robot path planning, Proc. Int. Symp. Robotics Res. (1996) pp. 249–264

    Chapter  Google Scholar 

  27. A. Ladd, L.E. Kavraki: Measure theoretic analysis of probabilistic path planning, IEEE Trans. Robotics Autom. 20(2), 229–242 (2004)

    Article  Google Scholar 

  28. R. Geraerts, M. Overmars: Sampling techniques for probabilistic roadmap planners, Int. Conf. Intell. Auton. Syst. (2004) pp. 600–609

    Google Scholar 

  29. D. Hsu, T. Jiang, J. Reif, Z. Sun: The bridge test for sampling narrow passages with probabilistic roadmap planners, IEEE Int. Conf. Robotics Autom. (2003) pp. 4420–4426

    Google Scholar 

  30. R. Bohlin, L. Kavraki: Path planning using lazy PRM, IEEE Int. Conf. Robotics Autom. (2000) pp. 521–528

    Google Scholar 

  31. B. Burns, O. Brock: Sampling-based motion planning using predictive models, IEEE Int. Conf. Robotics Autom. (2005) pp. 3120–3125

    Google Scholar 

  32. P. Isto: Constructing probabilistic roadmaps with powerful local planning and path optimization, IEEE/RSJ Int. Conf. Intell. Robots Syst. (2002) pp. 2323–2328

    Google Scholar 

  33. P. Leven, S.A. Hutchinson: Using manipulability to bias sampling during the construction of probabilistic roadmaps, IEEE Trans. Robotics Autom. 19(6), 1020–1026 (2003)

    Article  Google Scholar 

  34. D. Nieuwenhuisen, M.H. Overmars: Useful cycles in probabilistic roadmap graphs, IEEE Int. Conf. Robotics Autom. (2004) pp. 446–452

    Google Scholar 

  35. S.M. LaValle, J.J. Kuffner: Rapidly-exploring random trees: progress and prospects. In: Algorithmic and Computational Robotics: New Direction, ed. by B.R. Donald, K.M. Lynch, D. Rus (A.K. Peters, Wellesley 2001) pp. 293–308

    Google Scholar 

  36. K.E. Bekris, B.Y. Chen, A. Ladd, E. Plaku, L.E. Kavraki: Multiple query probabilistic roadmap planning using single query primitives, IEEE/RSJ Int. Conf. Intell. Robots Syst. (2003) pp. 656–661

    Google Scholar 

  37. M. Strandberg: Augmenting RRT-planners with local trees, IEEE Int. Conf. Robotics Autom. (2004) pp. 3258–3262

    Google Scholar 

  38. J.J. Kuffner, S.M. LaValle: An Efficient Approach to Path Planning Using Balanced Bidirectional RRT Search, Techn. Rep. CMU-RI-TR-05-34 Robotics Institute (Carnegie Mellon University, Pittsburgh 2005)

    Google Scholar 

  39. J. Bruce, M. Veloso: Real-time randomized path planning for robot navigation, IEEE/RSJ Int. Conf. Intell. Robots Syst. (2002) pp. 2383–2388

    Google Scholar 

  40. E. Frazzoli, M.A. Dahleh, E. Feron: Real-time motion planning for agile autonomous vehicles, AIAA J. Guid. Contr. 25(1), 116–129 (2002)

    Article  Google Scholar 

  41. M. Kallmann, M. Mataric: Motion planning using dynamic roadmaps, IEEE Int. Conf. Robotics Autom. (2004) pp. 4399–4404

    Google Scholar 

  42. A. Yershova, L. Jaillet, T. Simeon, S.M. LaValle: Dynamic-domain RRTs: Efficient exploration by controlling the sampling domain, IEEE Int. Conf. Robotics Autom. (2005) pp. 3867–3872

    Google Scholar 

  43. D. Hsu, J.C. Latombe, R. Motwani: Path planning in expansive configuration spaces, Int. J. Comput. Geom. Appl. 4, 495–512 (1999)

    Article  MathSciNet  Google Scholar 

  44. D. Hsu, R. Kindel, J.C. Latombe, S. Rock: Randomized kinodynamic motion planning with moving obstacles. In: Algorithmic and Computational Robotics: New Directions, ed. by B.R. Donald, K.M. Lynch, D. Rus (A.K. Peters, Wellesley 2001) pp. 247–264

    Google Scholar 

  45. G. Sánchez, J.-C. Latombe: A single-query bi-directional probabilistic roadmap planner with lazy collision checking, ISRR Int. Symp. Robotics Res. (2007) pp. 403–413

    Google Scholar 

  46. S. Carpin, G. Pillonetto: Robot motion planning using adaptive random walks, IEEE Int. Conf. Robotics Autom. (2003) pp. 3809–3814

    Google Scholar 

  47. A. Ladd, L.E. Kavraki: Fast exploration for robots with dynamics, Workshop Algorithm. Found. Robotics, Amsterdam (2004)

    Google Scholar 

  48. K.E. Bekris, L.E. Kavraki: Greedy but safe replanning under differential constraints, IEEE Int. Conf. Robotics Autom. (2007) pp. 704–710

    Google Scholar 

  49. C. O'Dunlaing, C.K. Yap: A retraction method for planning the motion of a disc, J. Algorithms 6, 104–111 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  50. D. Leven, M. Sharir: Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams, Discret. Comput. Geom. 2, 9–31 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  51. M. Sharir: Algorithmic motion planning. In: Handbook of Discrete and Computational Geometry, 2nd edn., ed. by J.E. Goodman, J. O'Rourke (Chapman Hall/CRC, Boca Raton 2004) pp. 1037–1064

    Google Scholar 

  52. N.J. Nilsson: A mobile automaton: An application of artificial intelligence techniques, 1st Int. Conf. Artif. Intell. (1969) pp. 509–520

    Google Scholar 

  53. J. O'Rourke: Visibility. In: Handbook of Discrete and Computational Geometry, 2nd edn., ed. by J.E. Goodman, J. O'Rourke (Chapman Hall/CRC, Boca Raton 2004) pp. 643–663

    Google Scholar 

  54. B. Chazelle: Approximation and decomposition of shapes. In: Algorithmic and Geometric Aspects of Robotics, ed. by J.T. Schwartz, C.K. Yap (Lawrence Erlbaum, Hillsdale 1987) pp. 145–185

    Google Scholar 

  55. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry: Algorithms and Applications, 2nd edn. (Springer, Berlin, Heidelberg 2000)

    Book  MATH  Google Scholar 

  56. J.M. Keil: Polygon decomposition. In: Handbook on Computational Geometry, ed. by J.R. Sack, J. Urrutia (Elsevier, New York 2000)

    Google Scholar 

  57. J.T. Schwartz, M. Sharir: On the piano movers' problem: I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers, Commun. Pure Appl. Math. 36, 345–398 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  58. O. Khatib: Real-time obstacle avoidance for manipulators and mobile robots, Int. J. Robotics Res. 5(1), 90–98 (1986)

    Article  Google Scholar 

  59. J. Barraquand, J.-C. Latombe: Robot motion planning: A distributed representation approach, Int. J. Robotics Res. 10(6), 628–649 (1991)

    Article  Google Scholar 

  60. E. Rimon, D.E. Koditschek: Exact robot navigation using artificial potential fields, IEEE Trans. Robotics Autom. 8(5), 501–518 (1992)

    Article  Google Scholar 

  61. J.P. Laumond: Trajectories for mobile robots with kinematic and environment constraints, Int. Conf. Intell. Auton. Syst. (1986) pp. 346–354

    Google Scholar 

  62. J.P. Laumond, S. Sekhavat, F. Lamiraux: Guidelines in nonholonomic motion planning for mobile robots. In: Robot Motion Planning and Control, ed. by J.P. Laumond (Springer, Berlin, Heidelberg 1998) pp. 1–53

    Chapter  Google Scholar 

  63. B.R. Donald, P.G. Xavier, J. Canny, J. Reif: Kinodynamic planning, Journal ACM 40, 1048–1066 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  64. C. O'Dunlaing: Motion planning with inertial constraints, Algorithmica 2(4), 431–475 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  65. J. Canny, A. Rege, J. Reif: An exact algorithm for kinodynamic planning in the plane, Discret. Comput. Geom. 6, 461–484 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  66. J. Go, T. Vu, J.J. Kuffner: Autonomous behaviors for interactive vehicle animations, SIGGRAPH/Eurographics Symp. Comput. Animat., Aire-la-Ville (2004) pp. 9–18

    Google Scholar 

  67. M. Pivtoraiko, A. Kelly: Generating near minimal spanning control sets for constrained motion planning in discrete state spaces, IEEE/RSJ Int. Conf. Intell. Robots Syst. (2005) pp. 3231–3237

    Google Scholar 

  68. J. Hollerbach: Dynamic scaling of manipulator trajectories, Tech. Rep. 700 (MIT, Cambridge 1983)

    Book  MATH  Google Scholar 

  69. K.G. Shin, N.D. McKay: Minimum-time control of robot manipulators with geometric path constraints, IEEE Trans. Autom. Control 30(6), 531–541 (1985)

    Article  MATH  Google Scholar 

  70. K.G. Shin, N.D. McKay: A dynamic programming approach to trajectory planning of robotic manipulators, IEEE Trans. Autom. Control 31(6), 491–500 (1986)

    Article  MATH  Google Scholar 

  71. S. Sastry: Nonlinear Systems: Analysis, Stability, and Control (Springer, Berlin, Heidelberg 1999)

    Book  MATH  Google Scholar 

  72. D.J. Balkcom, M.T. Mason: Time optimal trajectories for bounded velocity differential drive vehicles, Int. J. Robotics Res. 21(3), 199–217 (2002)

    Article  Google Scholar 

  73. P. Souères, J.-D. Boissonnat: Optimal trajectories for nonholonomic mobile robots. In: Robot Motion Planning and Control, ed. by J.P. Laumond (Springer, Berlin, Heidelberg 1998) pp. 93–169

    Chapter  Google Scholar 

  74. P. Svestka, M.H. Overmars: Coordinated motion planning for multiple car-like robots using probabilistic roadmaps, IEEE Int. Conf. Robotics Autom. (1995) pp. 1631–1636

    Google Scholar 

  75. S. Sekhavat, P. Svestka, J.-P. Laumond, M.H. Overmars: Multilevel path planning for nonholonomic robots using semiholonomic subsystems, Int. J. Robotics Res. 17, 840–857 (1998)

    Article  Google Scholar 

  76. P. Ferbach: A method of progressive constraints for nonholonomic motion planning, IEEE Int. Conf. Robotics Autom. (1996) pp. 2949–2955

    Google Scholar 

  77. S. Pancanti, L. Pallottino, D. Salvadorini, A. Bicchi: Motion planning through symbols and lattices, IEEE Int. Conf. Robotics Autom. (2004) pp. 3914–3919

    Google Scholar 

  78. J. Barraquand, J.-C. Latombe: Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles, Algorithmica 10, 121–155 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  79. S.M. LaValle, J.J. Kuffner: Randomized kinodynamic planning, IEEE Int. Conf. Robotics Autom. (1999) pp. 473–479

    Google Scholar 

  80. A.M. Ladd, L.E. Kavraki: Motion planning in the presence of drift underactuation and discrete system changes, Robotics Sci. Syst. I, Cambridge (2005) pp. 233–241

    Google Scholar 

  81. J.-P. Merlet: Parallel Robots (Kluwer, Boston 2000)

    Book  MATH  Google Scholar 

  82. D. Cox, J. Little, D. O'Shea: Ideals, Varieties, and Algorithms (Springer, Berlin, Heidelberg 1992)

    Book  MATH  Google Scholar 

  83. R.J. Milgram, J.C. Trinkle: The geometry of configuration spaces for closed chains in two and three dimensions, Homol. Homot. Appl. 6(1), 237–267 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  84. J. Yakey, S.M. LaValle, L.E. Kavraki: Randomized path planning for linkages with closed kinematic chains, IEEE Trans. Robotics Autom. 17(6), 951–958 (2001)

    Article  Google Scholar 

  85. L. Han, N.M. Amato: A kinematics-based probabilistic roadmap method for closed chain systems. In: Algorithmic and Computational Robotics: New Directions, ed. by B.R. Donald, K.M. Lynch, D. Rus (A.K. Peters, Wellesley 2001) pp. 233–246

    Google Scholar 

  86. J. Cortés: Motion Planning Algorithms for General Closed-Chain Mechanisms, Ph.D. Thesis (Institut National Polytechnique do Toulouse, Toulouse 2003)

    Google Scholar 

  87. R. Alami, J.-P. Laumond, T. Siméon: Two manipulation planning algorithms. In: Algorithms for Robotic Motion and Manipulation, ed. by J.P. Laumond, M. Overmars (A.K. Peters, Wellesley 1997)

    MATH  Google Scholar 

  88. L.E. Kavraki, M. Kolountzakis: Partitioning a planar assembly into two connected parts is NP-complete, Inform. Process. Lett. 55(3), 159–165 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  89. M.T. Mason: Mechanics of Robotic Manipulation (MIT, Cambridge 2001)

    Book  Google Scholar 

  90. K. Sutner, W. Maass: Motion planning among time dependent obstacles, Acta Inform. 26, 93–122 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  91. J.H. Reif, M. Sharir: Motion planning in the presence of moving obstacles, Journal ACM 41, 764–790 (1994)

    Article  MATH  Google Scholar 

  92. M.A. Erdmann, T. Lozano-Pérez: On multiple moving objects, Algorithmica 2, 477–521 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  93. J. van den Berg, M. Overmars: Prioritized motion planning for multiple robots, IEEE/RSJ Int. Conf. Intell. Robots Syst. (2005) pp. 2217–2222

    Google Scholar 

  94. T. Siméon, S. Leroy, J.-P. Laumond: Path coordination for multiple mobile robots: A resolution complete algorithm, IEEE Trans. Robotics Autom. 18(1), 42–49 (2002)

    Article  Google Scholar 

  95. R. Ghrist, J.M. O'Kane, S.M. LaValle: Pareto optimal coordination on roadmaps, Workshop Algorithm. Found. Robotics (2004) pp. 185–200

    Chapter  Google Scholar 

  96. S.M. LaValle, S.A. Hutchinson: Optimal motion planning for multiple robots having independent goals, IEEE Trans. Robotics Autom. 14(6), 912–925 (1998)

    Article  Google Scholar 

  97. P.R. Kumar, P. Varaiya: Stochastic Systems (Prentice Hall, Englewood Cliffs 1986)

    MATH  Google Scholar 

  98. S.M. LaValle: Sensing and Filtering: A Fresh Perspective Based on Preimages and Information Spaces, Foundations and Trends in Robotics (Now Publ., Delft 2012)

    MATH  Google Scholar 

  99. R. Alterovitz, N. Simeon, K. Goldberg: The stochastic motion roadmap: A sampling framework for planning with Markov motion uncertainty, Robotics Sci. Syst. 3, 233–241 (2007)

    MATH  Google Scholar 

  100. H. Kurniawati, D. Hsu, W.S. Lee: SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces, Robotics Sci. Syst. (2008)

    Google Scholar 

  101. J. Pineau, G. Gordon, S. Thrun: Point-based value iteration, Int. Joint Conf. Artif. Intell. (2003) pp. 1025–1032

    Google Scholar 

  102. R. Platt, R. Tedrake, T. Lozano-Perez, L.P. Kaelbling: Belief space planning assuming maximum likelihood observations, Robotics Sci. Syst. (2010)

    Google Scholar 

  103. N. Roy, G. Gordon: Exponential family PCA for belief compression in POMDPs, Adv. Neural Inform. Process. Syst. (2003)

    Google Scholar 

  104. R. He, S. Prentice, N. Roy: Planning in information space for a quadrotor helicopter in a GPS-denied environment, IEEE Int. Conf. Robotics Autom. (2008)

    Google Scholar 

  105. S. Koenig, M. Likhachev: $D^{*}$ lite, AAAI Nat. Conf. Artif. Intell. (2002) pp. 476–483

    Google Scholar 

  106. A. Stentz: Optimal and efficient path planning for partially-known environments, IEEE Int. Conf. Robotics Autom. (1994) pp. 3310–3317

    Google Scholar 

  107. J. Hershberger, S. Suri: Efficient Computation of Euclidean shortest paths in the plane, IEEE Symp. Found. Comp. Sci. (1995) pp. 508–517

    Google Scholar 

  108. J.S.B. Mitchell: Shortest paths among obstacles in the plane, Int. J. Comput. Geom. Applic. 6(3), 309 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  109. J. Choi, J. Sellen, C.K. Yap: Precision-sensitive Euclidean shortest path in 3-space, ACM Symp. Comput. Geo. (1995) pp. 350–359

    Google Scholar 

  110. C.H. Papadimitriou: An algorithm for shortest-path planning in three dimensions, Inform. Process. Lett. 20(5), 259 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  111. D. Yershov, S.M. LaValle: Simplicial Dijkstra and A* algorithms for optimal feedback planning, IEEE/RSJ Int. Conf. Intell. Robots Syst. (2011)

    Google Scholar 

  112. S. Karaman, E. Frazzoli: Sampling-based algorithms for optimal motion planning, Int. J. Robotics Res. 30(7), 846 (2011)

    Article  MATH  Google Scholar 

  113. J.D. Marble, K.E. Bekris: Towards small asymptotically near-optimal roadmaps, IEEE Int. Conf. Robotics Autom. (2012)

    Google Scholar 

  114. W.M. Boothby: An Introduction to Differentiable Manifolds and Riemannian Geometry, 2nd edn. (Academic, New York 2003)

    MATH  Google Scholar 

  115. A. Hatcher: Algebraic Topology (Cambridge Univ. Press, Cambridge 2002)

    MATH  Google Scholar 

  116. G.S. Chirikjian, A.B. Kyatkin: Engineering Applications of Noncommutative Harmonic Analysis (CRC, Boca Raton 2001)

    MATH  Google Scholar 

  117. J. Arvo: Fast random rotation matrices. In: Graphics Gems III, ed. by D. Kirk (Academic, New York 1992) pp. 117–120

    Google Scholar 

  118. H. Niederreiter: Random Number Generation and Quasi-Monte-Carlo Methods (Society for Industrial and Applied Mathematics, Philadelphia 1992)

    Book  MATH  Google Scholar 

  119. S. Basu, R. Pollack, M.-F. Roy: Algorithms in Real Algebraic Geometry (Springer, Berlin, Heidelberg 2003)

    Book  MATH  Google Scholar 

  120. B. Mishra: Computational real algebraic geometry. In: Handbook of Discrete and Computational Geometry, ed. by J.E. Goodman, J. O'Rourke (CRC, Boca Raton 1997) pp. 537–556

    MATH  Google Scholar 

  121. J.T. Schwartz, M. Sharir: On the piano movers' problem: II. General techniques for computing topological properties of algebraic manifolds, Commun. Pure Appl. Math. 36, 345–398 (1983)

    Article  MATH  Google Scholar 

  122. B.R. Donald: A search algorithm for motion planning with six degrees of freedom, Artif. Intell. J. 31, 295–353 (1987)

    Article  MATH  Google Scholar 

  123. D.S. Arnon: Geometric reasoning with logic and algebra, Artif. Intell. J. 37(1-3), 37–60 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  124. G.E. Collins: Quantifier elimination by cylindrical algebraic decomposition–twenty years of progress. In: Quantifier Elimination and Cylindrical Algebraic Decomposition, ed. by B.F. Caviness, J.R. Johnson (Springer, Berlin, Heidelberg 1998) pp. 8–23

    Chapter  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Rice University, 6100 Main Street, TX 77005, Houston, USA

    Lydia E. Kavraki

  2. Department of Computer Science, University of Illinois, 201 North Goodwin Avenue, 3318 Siebel Center, IL 61801, Urbana, USA

    Steven M. LaValle

Authors
  1. Lydia E. Kavraki
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Steven M. LaValle
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lydia E. Kavraki .

Editor information

Editors and Affiliations

  1. Department of Electrical Engineering, University of Naples Federico II, Via Claudio 21, 80125, Naples, Italy

    Bruno Siciliano

  2. Department of Computer Sciences, Artificial Intelligence Laboratory, Stanford University, 450 Serra Mall, CA 94305, Stanford, USA

    Oussama Khatib

Video-References

Video-References

:

Powder transfer task using demonstration-guided motion planningavailable from http://handbookofrobotics.org/view-chapter/07/videodetails/17

:

Simulation of a large crowdavailable from http://handbookofrobotics.org/view-chapter/07/videodetails/21

:

Motion planning in multi-robot scenarioavailable from http://handbookofrobotics.org/view-chapter/07/videodetails/22

:

Alpha puzzleavailable from http://handbookofrobotics.org/view-chapter/07/videodetails/23

:

Kinodynamic motion planning for a car-like robotavailable from http://handbookofrobotics.org/view-chapter/07/videodetails/24

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Kavraki, L.E., LaValle, S.M. (2016). Motion Planning. In: Siciliano, B., Khatib, O. (eds) Springer Handbook of Robotics. Springer Handbooks. Springer, Cham. https://doi.org/10.1007/978-3-319-32552-1_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-32552-1_7

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-32550-7

  • Online ISBN: 978-3-319-32552-1

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation