Abstract
We present a motion planning algorithm for cases where geometry of the robot cannot be neglected and where its dynamics are governed by non-holonomic constraints. While the two problems are classically treated separately, orientation of the robot strongly affects its possible motions both from the obstacle avoidance and from kinodynamic constraints perspective. We adopt an abstraction based approach ensuring asymptotic completeness. To handle the complex dynamics, a data driven approach is presented to construct a library of feedback motion primitives that guarantee a bounded error in following arbitrarily long trajectories. The library is constructed along local abstractions of the dynamics that enables addition of new motion primitives through abstraction refinement. Both the robot and the obstacles are represented as a union of circles, which allows arbitrarily precise approximation of complex geometries. To handle the geometrical constraints, we represent over- and under-approximations of the three-dimensional collision space as a finite set of two-dimensional “slices” corresponding to different intervals of the robot’s orientation space. Starting from a coarse slicing, we use the collision space over-approximation to find a valid path and the under-approximation to check for potential path non-existence. If none of the attempts are conclusive, the abstraction is refined. The algorithm is applied for motion planning and control of a rover with slipping without its prior modelling.
This work was supported by the EU H2020 Research and Innovation Programme under GA No. 731869 (Co4Robots) and the Knut and Alice Wallenberg Foundation, project IPSYS.
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
Similar content being viewed by others
References
Arslan, O., Tsiotras, P.: Use of relaxation methods in sampling-based algorithms for optimal motion planning. In: 2013 IEEE International Conference on Robotics and Automation, pp. 2421–2428. IEEE (2013)
Barraquand, J., Latombe, J.-C.: Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles. Algorithmica 10(2–4), 121 (1993)
Basch, J., Guibas, L.J., Hsu, D., Nguyen, A.T.: Disconnection proofs for motion planning. In: Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation, vol. 2, pp. 1765–1772. IEEE (2001). (Cat. No. 01CH37164)
Dang, T., Maler, O., Testylier, R.: Accurate hybridization of nonlinear systems. In: Proceedings of the 13th ACM International Conference on Hybrid Systems: Computation and Control, pp. 11–20. ACM (2010)
Frazzoli, E., Dahleh, M.A., Feron, E.: Maneuver-based motion planning for nonlinear systems with symmetries. IEEE Trans. Robot. 21(6), 1077–1091 (2005)
González, D., Pérez, J., Milanés, V., Nashashibi, F.: A review of motion planning techniques for automated vehicles. IEEE Trans. Intell. Transp. Syst. 17(4), 1135–1145 (2016)
Hsu, D., Kindel, R., Latombe, J.-C., Rock, S.: Randomized kinodynamic motion planning with moving obstacles. Int. J. Robot. Res. 21(3), 233–255 (2002)
Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 30(7), 846–894 (2011)
Kavraki, L.E., Svestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566–580 (1996)
LaValle, S.M.: Rapidly-exploring random trees: a new tool for path planning (1998)
Li, Y., Littlefield, Z., Bekris, K.E.: Asymptotically optimal sampling-based kinodynamic planning. Int. J. Robot. Res. 35(5), 528–564 (2016)
Likhachev, M., Gordon, G.J., Thrun, S.: ARA*: Anytime A* with provable bounds on sub-optimality. In: Advances in Neural Information Processing Systems, pp. 767–774 (2004)
Majumdar, A., Tedrake, R.: Funnel libraries for real-time robust feedback motion planning. Int. J. Robot. Res. 36(8), 947–982 (2017)
McCarthy, Z., Bretl, T., Hutchinson, S.: Proving path non-existence using sampling and alpha shapes. In: 2012 IEEE International Conference on Robotics and Automation, pp. 2563–2569. IEEE (2012)
Paden, B., Čáp, M., Yong, S.Z., Yershov, D., Frazzoli, E.: A survey of motion planning and control techniques for self-driving urban vehicles. IEEE Trans. Intell. Vehi. 1(1), 33–55 (2016)
Perez, A., Platt, R., Konidaris, G., Kaelbling, L., Lozano-Perez, T.: LQR-RRT*: optimal sampling-based motion planning with automatically derived extension heuristics. In: 2012 IEEE International Conference on Robotics and Automation, pp. 2537–2542. IEEE (2012)
Petereit, J., Emter, T., Frey, C.W., Kopfstedt, T., Beutel, A.: Application of hybrid A* to an autonomous mobile robot for path planning in unstructured outdoor environments. In: ROBOTIK 2012; 7th German Conference on Robotics, pp. 1–6. VDE (2012)
Polack, P., Altché, F., d’Andréa Novel, B., de La Fortelle, A.: The kinematic bicycle model: a consistent model for planning feasible trajectories for autonomous vehicles? In: 2017 IEEE Intelligent Vehicles Symposium (IV), pp. 812–818. IEEE (2017)
Varava, A., Carvalho, J.F., Kragic, D., Pokorny, F.T.: Free space of rigid objects: caging, path non-existence, and narrow passage detection. In: Workshop on Algorithmic Foundations of Robotics (2018)
Vukosavljev, M., Kroeze, Z., Broucke, M.E., Schoellig, A.P.: A framework for multi-vehicle navigation using feedback-based motion primitives. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 223–229. IEEE (2017)
Zhang, L., Kim, Y.J., Manocha, D.: A simple path non-existence algorithm using c-obstacle query. In: Algorithmic Foundation of Robotics VII, pp. 269–284. Springer, Cham (2008). https://doi.org/10.1007/978-3-540-68405-3_17
Zhou, B., Chiang, Y.J., Yap, C.: Soft subdivision motion planning for complex planar robots. In: 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
1 Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Tajvar, P., Varava, A., Kragic, D., Tumova, J. (2022). Robust Motion Planning for Non-holonomic Robots with Planar Geometric Constraints. In: Asfour, T., Yoshida, E., Park, J., Christensen, H., Khatib, O. (eds) Robotics Research. ISRR 2019. Springer Proceedings in Advanced Robotics, vol 20. Springer, Cham. https://doi.org/10.1007/978-3-030-95459-8_52
Download citation
DOI: https://doi.org/10.1007/978-3-030-95459-8_52
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-95458-1
Online ISBN: 978-3-030-95459-8
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)