×

zbMATH — the first resource for mathematics

Efficient intersection between splines of clothoids. (English) Zbl 07318062
Summary: A technique for the intersection of two splines of clothoid curves is herein presented. The study is motivated by the motion planning problem for a nonholonomic automated robotic vehicle, where a clothoid spline represents the path of the robot and the presence of an intersection with the path of another robot or with some obstacles boundaries means a possible collision. The algorithm works by segmenting each spline into small tangent triangles and then by organising the resulting, possibly large, number of triangles in a tree structure to exploit an efficient hierarchical check for intersections. Among various possible tree structures, the AABB tree is selected, which is a balanced choice between the complexity of the construction and the cost of evaluation, and avoids the need for extensive comparisons between each pair of clothoid segments that compose the splines. Indeed, only on pairs of intersecting triangles the collision is checked at curve level. This reduction of the computational cost yields an algorithm that can be effectively applied to real time applications.
MSC:
93Bxx Controllability, observability, and system structure
93Cxx Model systems in control theory
49Nxx Miscellaneous topics in calculus of variations and optimal control
Software:
Clothoids
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aila, Timo; Karras, Tero; Laine, Samuli, On quality metrics of bounding volume hierarchies, (Proceedings of the 5th High-Performance Graphics Conference. Proceedings of the 5th High-Performance Graphics Conference, HPG ’13 (2013), ACM: ACM New York, NY, USA), 101-107
[2] Andreetto, Marco; Divan, Stefano; Ferrari, Francesco; Fontanelli, Daniele; Palopoli, Luigi; Zenatti, Fabiano, Simulating passivity for robotic walkers via authority-sharing, IEEE Robot. Autom. Lett., 3, 2, 1306-1313 (2018)
[3] Alessandro Antonucci, Daniele Fontanelli, Towards a predictive behavioural model for service robots in shared environments, in: 2018 IEEE Workshop on Advanced Robotics and its Social Impacts, ARSO, 2018, pp. 9-14.
[4] Efstathios Bakolas, Panagiotis Tsiotras, On the generation of nearly optimal, planar paths of bounded curvature and bounded curvature gradient, in: 2009 American Control Conference, 2009, pp. 385-390.
[5] Baran, Ilya; Lehtinen, Jaakko; Popovic, Jovan, Sketching clothoid splines using shortest paths, Comput. Graph. Forum (2010)
[6] Enrico Bertolazzi, Paolo Bevilacqua, Francesco Biral, Daniele Fontanelli, Marco Frego, Luigi Palopoli, Efficient re-planning for robotic cars, in: 2018 European Control Conference, ECC, 2018, pp. 1068-1073. · Zbl 1375.93035
[7] Bertolazzi, Enrico; Bevilacqua, Paolo; Frego, Marco, Clothoids: a C++ library with Matlab interface for the handling of clothoid curves, Rend. Semin. Mat. Univ. Politec. Torino, 76, 2 (2018)
[8] Bertolazzi, Enrico; Frego, Marco, \( G^1\) fitting with clothoids, Math. Methods Appl. Sci., 38, 5, 881-897 (2015) · Zbl 1314.65019
[9] Bertolazzi, Enrico; Frego, Marco, Interpolating clothoid splines with curvature continuity, Math. Methods Appl. Sci., 41, 4, 1723-1737 (2017) · Zbl 1386.65073
[10] Bertolazzi, Enrico; Frego, Marco, On the \(G^2\) Hermite interpolation problem with clothoids, J. Comput. Appl. Math., 341, 99-116 (2018) · Zbl 07143613
[11] Bertolazzi, Enrico; Frego, Marco, Semianalytical minimum-time solution for the optimal control of a vehicle subject to limited acceleration, Optim. Control Appl. Methods (2018) · Zbl 1391.93147
[12] Bertolazzi, Enrico; Frego, Marco, A note on robust biarc computation, Comput.-Aided Des. Appl., 16, 5, 822-835 (2019) · Zbl 07124609
[13] Bertolazzi, Enrico; Frego, Marco, Clothoids: a C++ library with Matlab interface (2019) · Zbl 1314.65019
[14] Bevilacqua, Paolo; Frego, Marco; Bertolazzi, Enrico; Fontanelli, Daniele; Palopoli, Luigi; Biral, Francesco, Path planning maximising human comfort for assistive robots, (2016 IEEE Conference on Control Applications (CCA) (2016), IEEE), 1421-1427
[15] Bevilacqua, Paolo; Frego, Marco; Fontanelli, Daniele; Palopoli, Luigi, Reactive planning for assistive robots, IEEE Robot. Autom. Lett., 3, 2, 1276-1283 (2018)
[16] Blažková, Eva; Šír, Zbyněk, Exploiting the implicit support function for a topologically accurate approximation of algebraic curves, (Floater, Michael; Lyche, Tom; Mazure, Marie-Laurence; Mørken, Knut; Schumaker, Larry L., Mathematical Methods for Curves and Surfaces (2014), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 49-67 · Zbl 1356.65043
[17] Davis, Thomas G., Total least-squares spiral curve fitting, J. Surv. Eng., 125, 4, 159-176 (1999)
[18] Degen, Wendelin L. F., Approximation of curves by a measure of shape, (Farin, Gerald; Bieri, Hanspeter; Brunnett, Guido; De Rose, Tony, Geometric Modelling (1998), Springer Vienna: Springer Vienna Vienna), 81-99 · Zbl 0939.68144
[19] Eloe, Nathan W.; Steurer, Joseph A.; Leopold, Jennifer L.; Sabharwal, Chaman L., Dual graph partitioning for bottom-up BVH construction, J. Vis. Lang. Comput., 25, 6, 764-771 (2014), Distributed Multimedia Systems DMS2014 Part I
[20] Ericson, Christer, Real-Time Collision Detection (2004), CRC Press, Inc.: CRC Press, Inc. Boca Raton, FL, USA
[21] Marco Frego, Enrico Bertolazzi, On the distance between a point and a clothoid curve, in: 2018 European Control Conference, ECC, 2018, pp. 1-6. · Zbl 1386.65073
[22] Frego, Marco; Bertolazzi, Enrico, The distance of a point from a clothoid curve, SIAM J. Sci. Comput. (2019), accepted · Zbl 07124609
[23] Frego, Marco; Bertolazzi, Enrico; Biral, Francesco; Fontanelli, Daniele; Palopoli, Luigi, Semi-analytical minimum time solutions with velocity constraints for trajectory following of vehicles, Automatica, 86, 18-28 (2017) · Zbl 1375.93035
[24] Marco Frego, Paolo Bevilacqua, Enrico Bertolazzi, Francesco Biral, Daniele Fontanelli, Luigi Palopoli, Trajectory planning for car-like vehicles: A modular approach, in: 2016 IEEE 55th Conference on Decision and Control, CDC, 2016, pp. 203-209. · Zbl 1375.93035
[25] Garach, Laura; De Oña, Juan; Pasadas, Miguel, Determination of alignments in existing roads by using spline techniques, Math. Comput. Simulation, 102, 144-152 (2014)
[26] Guigue, Philippe; Devillers, Olivier, Fast and robust triangle-triangle overlap test using orientation predicates, J. Graph. Tools, 8, 1, 25-32 (2003)
[27] Larsson, Thomas, Adaptive Bounding Volume Hierarchies for Efficient Collision Queries (2009), Mälardalen University, School of Innovation, Design and Engineering, (Ph.D. thesis)
[28] Lekkas, Anastasios M.; Dahl, Andreas Reason; Breivik, Morten; Fossen, Thor I., Continuous-curvature path generation using Fermat’s spiral, Model. Identif. Control, 34, 4, 183-198 (2013)
[29] Levien, Raph, The Euler Spiral: A Mathematical HistoryTechnical Report UCB/EECS-2008-111 (2008), EECS Department, University of California: EECS Department, University of California Berkeley
[30] Levien, Raph; Séquin, Carlo H., Interpolating splines: Which is the fairest of them all?, Comput.-Aided Des. Appl., 6, 1, 91-102 (2009)
[31] Luo, Tong; Chen, Huan; Kassab, Ghassan S., 3D reconstruction of elastin fibres in coronary adventitia, J. Microsc., 265, 1, 121-131 (2017)
[32] Magnago, Valerio; Andreetto, Marco; Divan, Stefano; Fontanelli, Daniele; Palopoli, Luigi, Ruling the control authority of a service robot based on information precision, (2018 IEEE International Conference on Robotics and Automation (ICRA) (2018), IEEE), 7204-7210
[33] McCrae, James; Singh, Karan, Sketching piecewise clothoid curves, Comput. Graph., 33, 4, 452-461 (2009)
[34] Meek, Derek S.; Thomas, Robert S. D., A guided clothoid spline, Comput. Aided Geom. Design, 8, 2, 163-174 (1991) · Zbl 0829.65005
[35] Meek, Derek S.; Walton, Desmond J., A note on finding clothoids, J. Comput. Appl. Math., 170, 2, 433-453 (2004) · Zbl 1050.65017
[36] Miura, Kenjiro T.; Shibuya, Dai; Gobithaasan, R. U.; Usuki, Shin, Designing log-aesthetic splines with G2 continuity, Comput.-Aided Des. Appl., 10, 6, 1021-1032 (2013)
[37] Nakanishi, Toshio; Yikai, Kunio; ichi Satoh, Jun; Miyoshi, Isao; Satoh, Akira; Takahashi, Michiya, The development of a road traffic simulation system in broad areas, Math. Comput. Simulation, 39, 3, 207-212 (1995)
[38] Omohundro, Stephen M., Five Balltree Construction Algorithms (1989), International Computer Science Institute: International Computer Science Institute Berkeley
[39] Paluszny, Marco; Tovar, Francisco; Patterson, Richard R., G2 composite cubic Bézier curves, J. Comput. Appl. Math., 102, 1, 49-71 (1999), Computational Methods in Computer Graphics · Zbl 0948.65012
[40] Piazzi, Aurelio; Lo Bianco, Corrado Guarino; Romano, Massimo, \( \eta^3\)-splines for the smooth path generation of wheeled mobile robots, IEEE Trans. Robot., 23, 5, 1089-1095 (2007)
[41] Shinozaki, Nobuo; Sibuya, Masaaki; Tanabe, Kunio, Numerical algorithms for the Moore-Penrose inverse of a matrix: Direct methods, Ann. Inst. Statist. Math., 24, 1, 193-203 (1972) · Zbl 0315.65027
[42] Stoer, Josef, Curve fitting with clothoidal splines, J. Res. Natl. Bur. Stand., 87, 4, 317-346 (1982) · Zbl 0515.65011
[43] Sulaiman, Hamzah Asyrani; Bade, Abdullah, Bounding volume hierarchies for collision detection, (Mukai, Nobuhiko, Computer Graphics (2012), IntechOpen: IntechOpen Rijeka)
[44] Tounsi, Mohamed; Le Corre, J. F., Trajectory generation for mobile robots, Math. Comput. Simulation, 41, 3, 367-376 (1996), Robotics
[45] Walton, Desmond J.; Meek, Derek S., A controlled clothoid spline, Comput. Graph., 29, 3, 353-363 (2005)
[46] Yi-Si Xing, Xiaoping P. Liu, Shaoping Xu, Efficient collision detection based on AABB trees and sort algorithm, in: IEEE ICCA 2010, 2010, pp. 328-332.
[47] Ziatdinov, Rushan; Yoshida, Norimasa; Kim, Tae-wan, Analytic parametric equations of log-aesthetic curves in terms of incomplete gamma functions, Comput. Aided Geom. Design, 29, 2, 129-140 (2012) · Zbl 1242.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.