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:
Robotics and the Handbook Read chapter Read first chapter

2016 | OriginalPaper | Chapter

47. Motion Planning and Obstacle Avoidance

Authors : Javier Minguez, Florant Lamiraux, Jean-Paul Laumond

Published in: Springer Handbook of Robotics

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

This chapter describes motion planning and obstacle avoidance for mobile robots. We will see how the two areas do not share the same modeling background. From the very beginning of motion planning, research has been dominated by computer sciences. Researchers aim at devising well-grounded algorithms with well-understood completeness and exactness properties.
The challenge of this chapter is to present both nonholonomic motion planning (Sects. 47.1–47.6) and obstacle avoidance (Sects. 47.7–47.10) issues. Section 47.11 reviews recent successful approaches that tend to embrace the whole problem of motion planning and motion control. These approaches benefit from both nonholonomic motion planning and obstacle avoidance methods.

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 Simultaneous Localization and Mapping
next chapter Modeling and Control of Legged Robots
Appendix
Available only for authorised users
Literature
47.1
N.J. Nilson: A mobile automaton: An application of artificial intelligence techniques, 1st Int. Jt. Conf. Artif. Intell. (1969) pp. 509–520
47.2
A. Thompson: The navigation system of the JPL robot, 5th Int. Jt. Conf. Artif. Intell., Cambridge (1977) pp. 749–757
47.3
G. Giralt, R. Sobek, R. Chatila: A multi-level planning and navigation system for a mobile robot: A 1st approach to Hilare, 6th Int. Jt. Conf. Artif. Intell. (1979) pp. 335–337
47.4
47.5
47.6
J.-P. Laumond: Feasible trajectories for mobile robots with kinematic and environment constraints. In: Intelligent Autonomous Systems, ed. by F.C.A. Groen (Hertzberger, Amsterdam 1987) pp. 346–354
47.7
Z. Li, J.F. Canny: Nonholonomic Motion Planning (Kluwer, Dordrecht 1992)MATH
47.8
M. Likhachev, D. Ferguson: Planning long dynamically-feasible maneuvers for autonomous vehicles, Int. J. Robotics Res. 28(8), 933–945 (2009)CrossRef
47.9
H. Sussmann: Lie brackets, real analyticity and geometric control. In: Differential Geometric Control Theory, Progress in Mathematics, Vol. 27, ed. by R. Brockett, R. Millman, H. Sussmann (Birkhauser, New York 1982) pp. 1–116
47.10
47.11
J.-P. Laumond: Singularities and topological aspects in nonholonomic motion planning. In: Nonholonomic motion Planning, ed. by Z. Li, J.F. Canny (Kluwer, Boston 1992) pp. 149–199MATH
47.12
47.13
J.-P. Laumond, P. Jacobs, M. Taix, R. Murray: A motion planner for nonholonomic mobile robot, IEEE Trans. Robotics Autom. 10(5), 577–593 (1994)CrossRef
47.14
P. Cheng, S.M. LaValle: Reducing metric sensitivity in randomized trajectory design, IEEE/RSJ Int. Conf. Intell. Robots Syst. (IROS) (2001) pp. 43–48
47.15
J.A. Reeds, R.A. Shepp: Optimal paths for a car that goes both forward and backwards, Pac. J. Math. 145(2), 367–393 (1990)MathSciNetCrossRef
47.16
47.17
D. Balkcom, M. Mason: Time optimal trajectories for bounded velocity differential drive vehicles, Int. J. Robotics Res. 21(3), 199–218 (2002)CrossRef
47.18
D. Tilbury, R. Murray, S. Sastry: Trajectory generation for the n-trailer problem using Goursat normal form, IEEE Trans. Autom. Control 40(5), 802–819 (1995)MathSciNetMATHCrossRef
47.19
S. Sekhavat, J.-P. Laumond: Topological property for collision-free nonholonomic motion planning: The case of sinusoidal inputs for chained form systems, IEEE Trans. Robotics Autom. 14(5), 671–680 (1998)CrossRef
47.20
M. Fliess, J. Lévine, P. Martin, P. Rouchon: Flatness and defect of non-linear systems: Introductory theory and examples, Int. J. Control 61(6), 1327–1361 (1995)MathSciNetMATHCrossRef
47.21
P. Rouchon, M. Fliess, J. Lévine, P. Martin: Flatness and motion planning: The car with n trailers, Eur. Control Conf. (1993) pp. 1518–1522
47.22
F. Lamiraux, J.-P. Laumond: Flatness and smalltime controllability of multibody mobile robots: Application to motion planning, IEEE Trans. Autom. Control 45(10), 1878–1881 (2000)MATHCrossRef
47.23
P. Rouchon: Necessary condition and genericity of dynamic feedback linearization, J. Math. Syst. Estim. Control 4(2), 1–14 (1994)MathSciNetMATH
47.24
P. Rouchon, M. Fliess, J. Lévine, P. Martin: Flatness, motion planning and trailer systems, IEEE Int. Conf. Decis. Control (1993) pp. 2700–2705
47.25
S. Sekhavat, J. Hermosillo: Cycab bi-steerable cars: A new family of differentially flat systems, Adv. Robotics 16(5), 445–462 (2002)CrossRef
47.26
J. Barraquand, J.C. Latombe: Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles, Algorithmica 10, 121–155 (1993)MathSciNetMATHCrossRef
47.27
A. Divelbiss, T. Wen: A path space approach to nonholonomic motion planning in the presence of obstacles, IEEE Trans. Robotics Autom. 13(3), 443–451 (1997)CrossRef
47.28
S. LaValle, J. Kuffner: Randomized kinodynamic planning, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (1999) pp. 473–479
47.29
F. Lamiraux, E. Ferré, E. Vallée: Kinodynamic motion planning: Connecting exploration trees using trajectory optimization methods, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (2004) pp. 3987–3992
47.30
V. Lumelsky, A. Stepanov: Path planning strategies for a point mobile automation moving admist unknown obstacles of arbitrary shape, Algorithmica 2, 403–430 (1987)MathSciNetMATHCrossRef
47.31
R. Chatila: Path planning and environmental learning in a mobile robot system, Eur. Conf. Artif. Intell. (1982)
47.32
L. Gouzenes: Strategies for solving collision-free trajectories problems for mobile robots and manipulator robots, Int. J. Robotics Res. 3(4), 51–65 (1984)CrossRef
47.33
R. Chattergy: Some heuristics for the navigation of a robot, Int. J. Robotics Res. 4(1), 59–66 (1985)CrossRef
47.34
O. Khatib: Real-time obstacle avoidance for manipulators and mobile robots, Int. J. Robotics Res. 5, 90–98 (1986)CrossRef
47.35
B.H. Krogh, C.E. Thorpe: Integrated path planning and dynamic steering control for autonomous vehicles, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (1986) pp. 1664–1669
47.36
J. Borenstein, Y. Koren: Real-time obstacle avoidance for fast mobile robots, IEEE Trans. Syst. Man Cybern. 19(5), 1179–1187 (1989)CrossRef
47.37
K. Azarm, G. Schmidt: Integrated mobile robot motion planning and execution in changing indoor environments, IEEE/RSJ Int. Conf. Intell. Robots Syst. (IROS) (1994) pp. 298–305
47.38
A. Masoud, S. Masoud, M. Bayoumi: Robot navigation using a pressure generated mechanical stress field, the biharmonical potential approach, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (1994) pp. 124–129
47.39
L. Singh, H. Stephanou, J. Wen: Real-time robot motion control with circulatory fields, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (1996) pp. 2737–2742CrossRef
47.40
J. Borenstein, Y. Koren: The vector field histogram-fast obstacle avoidance for mbile robots, IEEE Trans. Robotics Autom. 7, 278–288 (1991)CrossRef
47.41
J. Minguez: The obstacle restriction method (ORM): Obstacle avoidance in difficult scenarios, IEEE/RSJ Int. Conf. Intell. Robot Syst. (IROS) (2005)
47.42
D. Vikerimark, J. Minguez: Reactive obstacle avoidance for mobile robots that operate in confined 3-D workspaces, IEEE Mediterr. Electrotech. Conf. (2006)
47.43
W. Feiten, R. Bauer, G. Lawitzky: Robust obstacle avoidance in unknown and cramped environments, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (1994) pp. 2412–2417
47.44
D. Fox, W. Burgard, S. Thrun: The dynamic window approach to collision avoidance, IEEE Robotics Autom. Mag. 4(1), 23–33 (1997)CrossRef
47.45
P. Fiorini, Z. Shiller: Motion planning in dynamic environments using velocity obstacles, Int. J. Robotics Res. 17(7), 760–772 (1998)CrossRef
47.46
F. Large, C. Laugier, Z. Shiller: Navigation among moving obstacles using the NLVO: Principles and applications to intelligent vehicles, Auton. Robots 19(2), 159–171 (2005)CrossRef
47.47
R. Simmons: The curvature-velocity method for local obstacle avoidance, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (1996) pp. 3375–3382CrossRef
47.48
J. Minguez, L. Montano: Nearness diagram (ND) navigation: Collision avoidance in troublesome scenarios, IEEE Trans. Robotics Autom. 20(1), 45–59 (2004)CrossRef
47.49
J. Minguez, J. Osuna, L. Montano: A divide and conquer strategy to achieve reactive collision avoidance in troublesome scenarios, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (2004)
47.50
J.W. Durham, F. Bullo: Smooth nearness-diagram navigation, IEEE/RSJ Int. Conf. Intell. Robots Syst. (IROS) (2008)
47.51
C.-C. Yu, W.-C. Chen, C.-C. Wang: Self-tuning nearness diagram navigation, Int. Conf. Serv. Interact. Robotics (SIRCon) (2009)
47.52
M. Mujahad, D. Fischer, B. Mertsching, H. Jaddu: Closest gap based (CG) reactive obstacle avoidance Navigation for highly cluttered environments, IEEE/RSJ Int. Conf. Intell. Robots Syst. (IROS) (2010) pp. 1805–1812
47.53
R.B. Tilove: Local obstacle avoidance for mobile robots based on the method of artificial potentials, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (1990) pp. 566–571CrossRef
47.54
R.C. Arkin: Behavior-Based Robotics (MIT Press, Cambridge 1999)
47.55
J. Minguez, L. Montano: Abstracting any vehicle shape and the kinematics and dynamic constraints from reactive collision avoidance methods, Eur. Conf. Mob. Robots (2007)
47.56
J. Minguez, L. Montano, J. Santos-Victor: Abstracting the vehicle shape and kinematic constraints from the obstacle avoidance methods, Auton. Robots 20(1), 43–59 (2006)CrossRef
47.57
L. Armesto, V. Girbés, M. Vincze, S. Olufs, P. Muñoz-Benavent: Mobile robot obstacle avoidance based on quasi-holonomic smooth paths, Lect. Notes Comput. Sci. 7429, 244–255 (2012)CrossRef
47.58
J.L. Blanco, J. González, J.A. Fernández-Madrigal: Foundations of parameterized trajectories-based space transformations for obstacle avoidance. In: Motion Planning, ed. by X.-Y. Jing (InTech, Rijeka 2008)
47.59
J. Minguez, L. Montano: Robot navigation in very complex dense and cluttered indoor/outdoor environments, 15th IFAC World Congr. (2002)
47.60
A. De Luca, G. Oriolo: Local incremental planning for nonholonomic mobile robots, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (1994) pp. 104–110
47.61
A. Bemporad, A. De Luca, G. Oriolo: Local incremental planning for car-like robot navigating among obstacles, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (1996) pp. 1205–1211CrossRef
47.62
S. Quinlan, O. Khatib: Elastic bands: Connecting path planning and control, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (1993) pp. 802–807
47.63
O. Brock, O. Khatib: Real-time replanning in high-dimensional configuration spaces using sets of homotopic paths, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (2000) pp. 550–555
47.64
F. Lamiraux, D. Bonnafous, O. Lefebvre: Reactive path deformation for nonholonomic mobile robots, IEEE Trans. Robotics 20(6), 967–977 (2004)CrossRef
47.65
Y. Yang, O. Brock: Elastic roadmaps – Motion generation for autonomous mobile manipulation, Auton. Robots 28(1), 113–130 (2010)CrossRef
47.66
E. Yoshida, C. Esteves, I. Belousov, J.-P. Laumond, T. Sakaguchi, K. Yokoi: Planning 3-d collision-free dynamic robotic motion through iterative reshaping, IEEE Trans. Robotics 24, 1186–1198 (2008)CrossRef
47.67
H. Kurniawati, T. Fraichard: From path to trajectory deformation, IEEE/RSJ Int. Conf. Intell. Robots Syst. (IROS) (2007)
47.68
O. Brock, O. Khatib: High-speed navigation using the global dynamic window approach, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (1999) pp. 341–346
47.69
I. Ulrich, J. Borenstein: VFH*: Local obstacle avoidance with look-ahead verification, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (2000) pp. 2505–2511
47.70
J. Minguez, L. Montano: Sensor-based motion robot motion generation in unknown, dynamic and troublesome scenarios, Robotics Auton. Syst. 52(4), 290–311 (2005)CrossRef
47.71
C. Stachniss, W. Burgard: An integrated approach to goal-directed obstacle avoidance under dynamic constraints for dynamic environments, IEEE/RSJ Int. Conf. Intell. Robots Syst. (IROS) (2002) pp. 508–513
47.72
R. Philipsen, R. Siegwart: Smooth and efficient obstacle avoidance for a tour guide robot, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (2003)
47.73
L. Montesano, J. Minguez, L. Montano: Lessons learned in integration for sensor-based robot navigation systems, Int. J. Adv. Robotics Syst. 3(1), 85–91 (2006)
47.74
F. Lu, E. Milios: Robot pose estimation in unknown environments by matching 2-D range scans, Intell. Robotic Syst. 18, 249–275 (1997)CrossRef
47.75
J. Minguez, L. Montesano, F. Lamiraux: Metric-based iterative closest point scan matching for sensor displacement estimation, IEEE Trans. Robotics 22(5), 1047–1054 (2006)CrossRef
47.76
A. Stenz: The focussed $d^{*}$ Algorithm for real-time replanning, Int. Jt. Conf. Artif. Intell. (IJCAI) (1995) pp. 1652–1659
47.77
S. Koenig, M. Likhachev: Improved fast replanning for robot navigation in unknown terrain, Proc. IEEE Int. Conf. Robotics Autom. (ICRA) (2002)
47.78
J.-P. Laumond: Robot motion planning and control. In: Lecture Notes in Control and Information Science, ed. by J.P. Laumond (Springer, New York 1998)
47.79
H. Choset, K.M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L.E. Kavraki, S. Thrun: Principles of Robot Motion (MIT Press, Cambridge 2005)MATH
47.80
Metadata
Title
Motion Planning and Obstacle Avoidance
Authors
Javier Minguez
Florant Lamiraux
Jean-Paul Laumond
Copyright Year
2016
Publisher
Springer International Publishing
Book
Springer Handbook of Robotics

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

Electronic ISBN: 978-3-319-32552-1

Copyright Year: 2016

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