Abstract
An optimal kinodynamic motion planning algorithm is presented and described as a generalized label correcting (GLC) method. Advantages of the technique include a simple implementation, convergence to the optimal cost with increasing resolution, and no requirement for a point-to-point local planning subroutine. The principal contribution of this paper is the construction and analysis of the GLC conditions which are the basis of the proposed algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Kavraki, L.E., Svestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces. IEEE Transactions on Robotics and Automation 12(4) (1996) 566–580
Karaman, S., Frazzoli, E.: Sampling-Based Algorithms for Optimal Motion Planning. The International Journal of Robotics Research 30(7) (2011) 846–894
Hsu, D., Kindel, R., Latombe, J.C., Rock, S.: Randomized kinodynamic motion planning with moving obstacles. The International Journal of Robotics Research 21(3) (2002) 233–255
LaValle, S.M., Kuffner, J.J.: Randomized kinodynamic planning. The International Journal of Robotics Research 20(5) (2001) 378–400
Karaman, S., Frazzoli, E.: Optimal Kinodynamic Motion Planning Using Incremental Sampling-Based Methods. In: IEEE Conference on Decision and Control. (2010) 7681–7687
Perez, A., Platt Jr, R., Konidaris, G., Kaelbling, L., Lozano-Perez, T.: LQR-RRT*: Optimal Sampling-Based Motion Planning with Automatically Derived Extension Heuristics. In: International Conference on Robotics and Automation, IEEE (2012) 2537–2542
Xie, C., van den Berg, J., Patil, S., Abbeel, P.: Toward Asymptotically Optimal Motion Planning for Kinodynamic Systems Using a Two-Point Boundary Value Problem Solver. In: International Conference on Robotics and Automation, IEEE (2015) 4187–4194
Dijkstra, E.W.: A Note on Two Problems in Connexion with Graphs. Numerische mathematik 1(1) (1959) 269–271
Dolgov, D., Thrun, S., Montemerlo, M., Diebel, J.: Path planning for autonomous vehicles in unknown semi-structured environments. The International Journal of Robotics Research 29(5) (2010) 485–501
Li, Y., Littlefield, Z., Bekris, K.E.: Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning. In: Algorithmic Foundations of Robotics XI. Springer (2015) 263–282
Coddington, E.A., Levinson, N.: Theory of Ordinary Differential Equations. McGraw-Hill Education (1955)
Hart, P.E., Nilsson, N.J., Raphael, B.: A Formal Basis for the Heuristic Determination of Minimum Cost Paths. Systems Science and Cybernetics 4(2) (1968) 100–107
Karaman, S.: RRT* Library. http://karaman.mit.edu/software.html
Li, Y., Littlefield, Z., Bekris, K.E.: Sparse RRT package. https://bitbucket.org/pracsys/sparse_rrt/ Accessed: Jan. 2016.
Spong, M.W.: The Swing Up Control Problem for the Acrobot. Control Systems, IEEE 15(1) (1995) 49–55
Yershov, D.S., LaValle, S.M.: Sufficient Conditions for the Existence of Resolution Complete Planning Algorithms. In: Algorithmic Foundations of Robotics IX. Springer (2011) 303–320
Khalil, H.K., Grizzle, J.: Nonlinear Systems. Volume 3. Prentice hall New Jersey (1996)
Kolmogorov, A.N., Fomin, S.V.: Elements of the Theory of Functions and Functional Analysis. Vol. 2, Measure. The Lebesgue Integral. Hilbert Spaces. Graylock Press (1961)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Paden, B., Frazzoli, E. (2020). A Generalized Label Correcting Method for Optimal Kinodynamic Motion Planning. In: Goldberg, K., Abbeel, P., Bekris, K., Miller, L. (eds) Algorithmic Foundations of Robotics XII. Springer Proceedings in Advanced Robotics, vol 13. Springer, Cham. https://doi.org/10.1007/978-3-030-43089-4_33
Download citation
DOI: https://doi.org/10.1007/978-3-030-43089-4_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-43088-7
Online ISBN: 978-3-030-43089-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)