Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2008 | OriginalPaper | Chapter

5. Motion Planning

Authors : Lydia E. Kavraki, Prof, Steven M. LaValle, Prof

Published in: Springer Handbook of Robotics

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This chapter first provides a formulation of the geometric path planning problem in Sect. 5.1 and then introduces sampling-based planning in Sect. 5.2. 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. 5.3. These approaches provide theoretical guarantees and for simple planning instances they outperform sampling-based planners. Section 5.4 considers problems that involve differential constraints, while Sect. 5.5 overviews several other extensions of the basic problem formulation and proposed solutions. Finally, Sect. 5.7 addresses some important and more advanced topics related to motion planning.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Sensing and Estimation
next chapter Motion Control
Literature
5.1.
J.H. Reif: Complexity of the moverʼs problem and generalizations, IEEE Symp. Found. Comput. Sci. (1979) pp. 421–427
5.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)
5.3.
S.R. Lindemann, S.M. LaValle: Current issues in sampling-based motion planning. In: Robotics Research: The Eleventh International Symposium, ed. by P. Dario, R. Chatila (Springer, Berlin 2005) pp. 36–54
5.4.
J.T. Schwartz, M. Sharir: A survey of motion planning and related geometric algorithms, Artif. Intell. J. 37, 157–169 (1988)CrossRefMATHMathSciNet
5.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 Press, Cambridge 2005)MATH
5.6.
J.C. Latombe: Robot Motion Planning (Kluwer, Boston 1991)
5.7.
5.8.
S. Udupa: Collision detection and avoidance in computer controlled manipulators. Ph.D. Thesis (Dept. of Electical Engineering, California Institute of Technology 1977)
5.9.
T. Lozano-Pérez: Spatial planning: A configuration space approach, IEEE Trans. Comput. C-32(2), 108–120 (1983)CrossRef
5.10.
J.T. Schwartz, M. Sharir: On the piano moversʼ problem: III. Coordinating the motion of several independent bodies, Int. J. Robot. Res. 2(3), 97–140 (1983)CrossRefMathSciNet
5.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)CrossRefMATHMathSciNet
5.12.
J.F. Canny: The Complexity of Robot Motion Planning (MIT Press, Cambridge 1988)
5.13.
D. Halperin, M. Sharir: A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment, Discrete Comput. Geom. 16, 121–134 (1996)CrossRefMATHMathSciNet
5.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. Robot. Res. 3(4), 76–88 (1984)CrossRef
5.15.
J. Canny, J. Reif: New lower bound techniques for robot motion planning problems, IEEE Symp. Found. Comput. Sci. (1987) pp. 49–60
5.16.
M.C. Lin, J.F. Canny: Efficient algorithms for incremental distance computation, IEEE Int. Conf. Robot. Autom. (1991)
5.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 1998) pp. 1–53
5.18.
M.C. Lin, D. Manocha: Collision and proximity queries. In: Handbook of Discrete and Computational Geometry, 2nd Ed, ed. by J.E. Goodman, J. OʼRourke (Chapman Hall/CRC, New York 2004) pp. 787–807
5.19.
L.E. Kavraki, P. Svestka, J.C. Latombe, M.H. Overmars: Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Trans. Robot. Autom. 12(4), 566–580 (1996)CrossRef
5.20.
N.M. Amato, O.B. Bayazit, L.K. Dale, C. Jones, D. Vallejo: OBPRM: an obstacle-based PRM for 3D workspaces, Workshop Algorith. Found. Robot. (1998) pp. 155–168
5.21.
V. Boor, M.H. Overmars, A.F. van der Stappen: The Gaussian sampling strategy for probabilistic roadmap planners, IEEE Int. Conf. Robot. Autom. (1999) pp. 1018–1023
5.22.
C. Holleman, L.E. Kavraki: A framework for using the workspace medial axis in PRM planners, IEEE Int. Conf. Robot. Autom. (2000) pp. 1408–1413
5.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. Robot. Autom. (2003)
5.24.
S.M. LaValle, M.S. Branicky, S.R. Lindemann: On the relationship between classical grid search and probabilistic roadmaps, Int. J. Robot. Res. 23(7/8), 673–692 (2004)CrossRef
5.25.
T. Siméon, J.-P. Laumond, C. Nissoux: Visibility based probabilistic roadmaps for motion planning, Adv. Robot. 14(6), 477–493 (2000)CrossRef
5.26.
J. Barraquand, L. Kavraki, J.-C. Latombe, T.-Y. Li, R. Motwani, P. Raghavan: A random sampling scheme for robot path planning. In: Proceedings International Symposium on Robotics Research, ed. by G. Giralt, G. Hirzinger (Springer, New York 1996) pp. 249–264
5.27.
A. Ladd, L.E. Kavraki: Measure theoretic analysis of probabilistic path planning, IEEE Trans. Robot. Autom. 20(2), 229–242 (2004)CrossRef
5.28.
R. Geraerts, M. Overmars: Sampling techniques for probabilistic roadmap planners, Int. Conf. Intell. Auton. Syst. (2004)
5.29.
D. Hsu, T. Jiang, J. Reif, Z. Sun: The bridge test for sampling narrow passages with probabilistic roadmap planners, IEEE Int. Conf. Robot. Autom. (2003)
5.30.
R. Bohlin, L. Kavraki: Path planning using lazy PRM, IEEE Int. Conf. Robot. Autom. (2000)
5.31.
B. Burns, O. Brock: Sampling-based motion planning using predictive models, IEEE/RSJ Int. Conf. Intell. Robot. Autom. (2005)
5.32.
P. Isto: Constructing probabilistic roadmaps with powerful local planning and path optimization, IEEE/RSJ Int. Conf. Intell. Robot. Syst. (2002) pp. 2323–2328
5.33.
P. Leven, S.A. Hutchinson: Using manipulability to bias sampling during the construction of probabilistic roadmaps, IEEE Trans. Robot. Autom. 19(6), 1020–1026 (2003)CrossRef
5.34.
D. Nieuwenhuisen, M.H. Overmars: Useful cycles in probabilistic roadmap graphs, IEEE Int. Conf. Robot. Autom. (2004) pp. 446–452
5.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
5.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. Robot. Syst. (2003)
5.37.
M. Strandberg: Augmenting RRT-planners with local trees, IEEE Int. Conf. Robot. Autom. (2004) pp. 3258–3262
5.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)
5.39.
J. Bruce, M. Veloso: Real-time randomized path planning for robot navigation, IEEE/RSJ Int. Conf. Intell. Robot. Autom. (2002)
5.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)CrossRef
5.41.
M. Kallmann, M. Mataric: Motion planning using dynamic roadmaps, IEEE Int. Conf. Robot. Autom. (2004)
5.42.
A. Yershova, L. Jaillet, T. Simeon, S.M. LaValle: Dynamic-domain RRTs: efficient exploration by controlling the sampling domain, IEEE Int. Conf. Robot. Autom. (2005)
5.43.
D. Hsu, J.C. Latombe, R. Motwani: Path planning in expansive configuration spaces, Int. J. Comput. Geom. Appl. 4, 495–512 (1999)CrossRefMathSciNet
5.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)
5.45.
G. Sánchez, J.-C. Latombe: A single-query bi-directional probabilistic roadmap planner with lazy collision checking, ISRR Int. Symp. Robot. Res. (2001)
5.46.
S. Carpin, G. Pillonetto: Robot motion planning using adaptive random walks, IEEE Int. Conf. Robot. Autom. (2003) pp. 3809–3814
5.47.
A. Ladd, L.E. Kavraki: Fast exploration for robots with dynamics, Workshop Algorithm. Found. Robot. (Zeist, Amsterdam 2004)
5.48.
K.E. Bekris, L.E. Kavraki: Greedy but safe replanning under differential constraints, IEEE Int. Conf. Robot. Autom. (2007)
5.49.
C. OʼDunlaing, C.K. Yap: A retraction method for planning the motion of a disc, J. Algorithms 6, 104–111 (1982)CrossRefMathSciNet
5.50.
D. Leven, M. Sharir: Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams, Discrete Comput. Geom. 2, 9–31 (1987)CrossRefMATHMathSciNet
5.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 Press, New York 2004) pp. 1037–1064
5.52.
N.J. Nilsson: A mobile automaton: An application of artificial intelligence techniques, 1st Int. Conf. Artif. Intell. (1969) pp. 509–520
5.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 Press, New York 2004) pp. 643–663
5.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
5.55.
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry: Algorithms and Applications, 2nd edn. (Springer, Berlin 2000)MATH
5.56.
J.M. Keil: Polygon decomposition. In: Handbook on Computational Geometry, ed. by J.R. Sack, J. Urrutia (Elsevier, New York 2000)
5.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)CrossRefMATHMathSciNet
5.58.
O. Khatib: Real-time obstacle avoidance for manipulators and mobile robots, Int. J. Robot. Res. 5(1), 90–98 (1986)CrossRefMathSciNet
5.59.
J. Barraquand, J.-C. Latombe: Robot motion planning: A distributed representation approach, Int. J. Robot. Res. 10(6), 628–649 (1991)CrossRef
5.60.
E. Rimon, D.E. Koditschek: Exact robot navigation using artificial potential fields, IEEE Trans. Robot. Autom. 8(5), 501–518 (1992)CrossRef
5.61.
J.P. Laumond: Trajectories for mobile robots with kinematic and environment constraints, Int. Conf. Intell. Auton. Syst. (1986) pp. 346–354
5.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 1998) pp. 1–53CrossRef
5.63.
5.64.
5.65.
J. Canny, A. Rege, J. Reif: An exact algorithm for kinodynamic planning in the plane, Discrete Comput. Geom. 6, 461–484 (1991)CrossRefMATHMathSciNet
5.66.
J. Go, T. Vu, J.J. Kuffner: Autonomous behaviors for interactive vehicle animations, SIGGRAPH Symp. Comput. Animat. (2004)
5.67.
M. Pivtoraiko, A. Kelly: Generating near minimal spanning control sets for constrained motion planning in discrete state spaces, IEEE/RSJ Int. Conf. Intell. Robot. Syst. (2005)
5.68.
J. Hollerbach: Dynamic scaling of manipulator trajectories, Tech. Rep. 700 (MIT A.I. Lab Memo, 1983)
5.69.
K.G. Shin, N.D. McKay: Minimum-time control of robot manipulators with geometric path constraints, IEEE Trans. Autom. Contr. 30(6), 531–541 (1985)CrossRefMATH
5.70.
K.G. Shin, N.D. McKay: A dynamic programming approach to trajectory planning of robotic manipulators, IEEE Trans. Autom. Contr. 31(6), 491–500 (1986)CrossRefMATH
5.71.
S. Sastry: Nonlinear Systems: Analysis, Stability, and Control (Springer, Berlin 1999)MATH
5.72.
D.J. Balkcom, M.T. Mason: Time optimal trajectories for bounded velocity differential drive vehicles, Int. J. Robot. Res. 21(3), 199–217 (2002)CrossRef
5.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 1998) pp. 93–169CrossRef
5.74.
P. Svestka, M.H. Overmars: Coordinated motion planning for multiple car-like robots using probabilistic roadmaps, IEEE Int. Conf. Robot. Autom. (1995) pp. 1631–1636
5.75.
S. Sekhavat, P. Svestka, J.-P. Laumond, M.H. Overmars: Multilevel path planning for nonholonomic robots using semiholonomic subsystems, Int. J. Robot. Res. 17, 840–857 (1998)CrossRef
5.76.
P. Ferbach: A method of progressive constraints for nonholonomic motion planning, IEEE Int. Conf. Robot. Autom. (1996) pp. 2949–2955
5.77.
S. Pancanti, L. Pallottino, D. Salvadorini, A. Bicchi: Motion planning through symbols and lattices, IEEE Int. Conf. Robot. Autom. (2004) pp. 3914–3919
5.78.
J. Barraquand, J.-C. Latombe: Nonholonomic multibody mobile robots: controllability and motion planning in the presence of obstacles, Algorithmica 10, 121–155 (1993)CrossRefMATHMathSciNet
5.79.
S.M. LaValle, J.J. Kuffner: Randomized kinodynamic planning, IEEE Int. Conf. Robot. Autom. (1999) pp. 473–479
5.80.
A. M. Ladd, L. E. Kavraki: Motion planning in the presence of drift underactuation and discrete system changes. In: Robotics: Science and Systems I ed. by (MIT Press, Boston 2005) pp. 233–241
5.81.
5.82.
D. Cox, J. Little, D. OʼShea: Ideals, Varieties, and Algorithms (Springer, Berlin 1992)MATH
5.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)MATHMathSciNet
5.84.
J. Yakey, S.M. LaValle, L.E. Kavraki: Randomized path planning for linkages with closed kinematic chains, IEEE Trans. Robot. Autom. 17(6), 951–958 (2001)CrossRef
5.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
5.86.
J. Cortés: Motion Planning Algorithms for General Closed-Chain Mechanisms. Ph.D. Thesis (Institut National Polytechnique do Toulouse, Toulouse 2003)
5.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)
5.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)CrossRefMATHMathSciNet
5.89.
M.T. Mason: Mechanics of Robotic Manipulation (MIT Press, Cambridge 2001)
5.90.
5.91.
J.H. Reif, M. Sharir: Motion planning in the presence of moving obstacles, J. ACM 41, 764–790 (1994)CrossRefMATH
5.92.
5.93.
J. van den Berg, M. Overmars: Prioritized motion planning for multiple robots, IEEE/RSJ Int. Conf. Intell. Robot. Syst. (2005) pp. 2217–2222
5.94.
T. Siméon, S. Leroy, J.-P. Laumond: Path coordination for multiple mobile robots: A resolution complete algorithm, IEEE Trans. Robot. Autom. 18(1), 42–49 (2002)CrossRef
5.95.
R. Ghrist, J.M. OʼKane, S.M. LaValle: Pareto optimal coordination on roadmaps, Workshop Algorithm. Found. Robot. (2004) pp. 185–200
5.96.
S.M. LaValle, S.A. Hutchinson: Optimal motion planning for multiple robots having independent goals, IEEE Trans. Robot. Autom. 14(6), 912–925 (1998)CrossRef
5.97.
W.M. Boothby: An Introduction to Differentiable Manifolds and Riemannian Geometry, 2nd edn. (Academic, New York 2003)
5.98.
A. Hatcher: Algebraic Topology (Cambridge Univ Press, Cambridge 2002)MATH
5.99.
G.S. Chirikjian, A.B. Kyatkin: Engineering Applications of Noncommutative Harmonic Analysis (CRC, Boca Raton 2001)MATH
5.100.
J. Arvo: Fast random rotation matrices. In: Graphics Gems III, ed. by D. Kirk (Academic, New York 1992) pp. 117–120
5.101.
H. Niederreiter: Random Number Generation and Quasi-Monte-Carlo Methods (Society for Industrial and Applied Mathematics, Philadelphia 1992)MATH
5.102.
S. Basu, R. Pollack, M.-F. Roy: Algorithms in Real Algebraic Geometry (Springer, Berlin 2003)MATH
5.103.
B. Mishra: Computational real algebraic geometry. In: Handbook of Discrete and Computational Geometry, ed. by J.E. Goodman, J. OʼRourke (CRC, New York 1997) pp. 537–556
5.104.
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)CrossRefMATHMathSciNet
5.105.
B.R. Donald: A search algorithm for motion planning with six degrees of freedom, Artif. Intell. J. 31, 295–353 (1987)CrossRefMATH
5.106.
5.107.
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 1998) pp. 8–23
Metadata
Title
Motion Planning
Authors
Lydia E. Kavraki, Prof
Steven M. LaValle, Prof
Copyright Year
2008
Book
Springer Handbook of Robotics

Print ISBN: 978-3-540-23957-4

Electronic ISBN: 978-3-540-30301-5

Copyright Year: 2008

DOI
https://doi.org/10.1007/978-3-540-30301-5_6