Point-clothoid distance and projection computation.

*(English)*Zbl 07124609A clothoid (or Euler spiral, or Cornu spiral) is a planar curve whose curvature is a linear function of the arc length. It appears as the solution of an optimal control problem for a car-like robot that has to find the shortest path connecting two points in the plane with given initial and final angles and curvatures, driving at constant speed.
The authors propose an algorithm to compute the minimum distance between a given point in the plane and an assigned clothoid spiral curve.
The projection of the point on the curve is also found.
The solution is relevant in many applications ranging from robotics to autonomous vehicles.
The minimization is formulated as a root-finding problem which typically has multiple solutions associated to local minima. A proper interval for the curvilinear abscissa, that contains the global solution is recognized. Due to its spiraling path, the clothoid has a low curvature region near the inflection point and a high curvature region around points at infinity, where the revolving curve shows many potential solutions. The transition from a clothoid to an arc of circle and from an arc of circle to a straight line (which are particular cases of clothoids) is smoothly computed. The algorithm is validated with extensive numerical tests and is proved to be much better than brute force algorithms in terms of accuracy, convergence and computational time.

Reviewer: Vladimir P. Kostov (Nice)

##### MSC:

65D17 | Computer-aided design (modeling of curves and surfaces) |

65H05 | Numerical computation of solutions to single equations |

65H20 | Global methods, including homotopy approaches to the numerical solution of nonlinear equations |

65S05 | Graphical methods in numerical analysis |

PDF
BibTeX
XML
Cite

\textit{M. Frego} and \textit{E. Bertolazzi}, SIAM J. Sci. Comput. 41, No. 5, A3326--A3353 (2019; Zbl 07124609)

Full Text:
DOI

**OpenURL**

##### References:

[1] | M. Abramowitz and I. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, National Bureau of Standards Applied Mathematics Series 55, U.S. Government Printing Office, Washington, DC, 1964. |

[2] | G. Arechavaleta, J.-P. Laumond, H. Hicheur, and A. Berthoz, An optimality principle governing human walking, IEEE Trans. Robotics, 24 (2008), pp. 5–14, https://doi.org/10.1109/TRO.2008.915449. |

[3] | E. Bakolas and P. Tsiotras, On the generation of nearly optimal, planar paths of bounded curvature and bounded curvature gradient, in Proceedings of the American Control Conference, 2009, pp. 385–390, https://doi.org/10.1109/ACC.2009.5160269. |

[4] | E. Bertolazzi, P. Bevilacqua, and M. Frego, Clothoids: A C++ library with Matlab interface for the handling of clothoid curves, Rend. Semin. Mat., 76 (2018). |

[5] | E. Bertolazzi and M. Frego, \(G^1\) fitting with clothoids, Math. Methods Appl. Sci., 38 (2015), pp. 881–897, https://doi.org/10.1002/mma.3114. · Zbl 1314.65019 |

[6] | E. Bertolazzi and M. Frego, Interpolating clothoid splines with curvature continuity, Math. Methods Appl. Sci., 41 (2017), pp. 1723–1737, https://doi.org/10.1002/mma.4700. · Zbl 1386.65073 |

[7] | E. Bertolazzi and M. Frego, Clothoids Library. https://github.com/ebertolazzi/Clothoids (2018). |

[8] | E. Bertolazzi and M. Frego, On the \(G^2\) Hermite interpolation problem with clothoids, J. Comput. Appl. Math., 341 (2018), pp. 99–116, https://doi.org/10.1016/j.cam.2018.03.029. |

[9] | E. Bertolazzi and M. Frego, Semianalytical minimum-time solution for the optimal control of a vehicle subject to limited acceleration, Optimal Control Appl. Methods, 39 (2018), pp. 774–791, https://doi.org/10.1002/oca.2376. · Zbl 1391.93147 |

[10] | E. Bertolazzi and M. Frego, A note on robust biarc computation, Comput. Aided Design Appl., 16 (2019), pp. 822–835, https://doi.org/10.14733/cadaps.2019.822-835. |

[11] | P. Bevilacqua, M. Frego, D. Fontanelli, and L. Palopoli, Reactive planning for assistive robots, IEEE Robotics Automation Lett., 3 (2018), pp. 1276–1283, https://doi.org/10.1109/LRA.2018.2795642. |

[12] | E. Degtiariova-Kostova and V. Kostov, Irregularity of Optimal Trajectories in a Control Problem for a Car-like Robot, Tech. report RR-3411, INRIA, 1998, https://hal.inria.fr/inria-00073279. |

[13] | F. Farina, D. Fontanelli, A. Garulli, A. Giannitrapani, and D. Prattichizzo, Walking ahead: The headed social force model, PLOS One, 12 (2017), pp. 1–23, https://doi.org/10.1371/journal.pone.0169734. |

[14] | M. Frego and E. Bertolazzi, On the distance between a point and a clothoid curve, in Proceedings of the European Control Conference, 2018, pp. 1–6. · Zbl 1391.93147 |

[15] | M. Frego, E. Bertolazzi, F. Biral, D. Fontanelli, and L. Palopoli, Semi-analytical minimum time solutions with velocity constraints for trajectory following of vehicles, Automatica, 86 (2017), pp. 18–28, https://doi.org/10.1016/j.automatica.2017.08.020. · Zbl 1375.93035 |

[16] | M. Frego, P. Bevilacqua, E. Bertolazzi, F. Biral, D. Fontanelli, and L. Palopoli, Trajectory planning for car-like vehicles: A modular approach, in Proceedings of the IEEE 55th Conference on Decision and Control, 2016, pp. 203–209, https://doi.org/10.1109/CDC.2016.7798270. |

[17] | E. W. Grafarend, R. J. You, and R. Syffus, Map Projections: Cartographic Information Systems, 2nd ed., Springer-Verlag, New York, 2014, https://doi.org/10.1007/978-3-642-36494-5. |

[18] | H. Guggenheimer, Differential Geometry, Dover, Mineola, NY, 1977. |

[19] | L. Hammarstrand, M. Fatemi, A. F. Garcìa-Fernàndez, and L. Svensson, Long-range road geometry estimation using moving vehicles and roadside observations, IEEE Trans. Intelligent Transportation Syst., 17 (2016), pp. 2144–2158, https://doi.org/10.1109/TITS.2016.2517701. |

[20] | V. Kostov and E. Degtiariova-Kostova, Some Properties of Clothoids, Tech. report RR-2752, INRIA, 1995, http://hal.inria.fr/inria-00073940. · Zbl 0863.49024 |

[21] | V. P. Kostov and E. V. Degtiariova-Kostova, The planar motion with bounded derivative of the curvature and its suboptimal paths, Acta Math. Univ. Comenian. (N.S.), 64 (1995), pp. 185–226. · Zbl 0877.49028 |

[22] | R. Levien, The Euler Spiral: A Mathematical History, Tech. report UCB/EECS-2008-111, EECS Department, University of California, Berkeley, 2008, http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-111.html. |

[23] | J. McCrae and K. Singh, Sketching piecewise clothoid curves, Comput. & Graphics, 33 (2009), pp. 452–461, https://doi.org/10.1016/j.cag.2009.05.006. |

[24] | D. S. Meek and D. J. Walton, A note on finding clothoids, J. Comput. Appl. Math., 170 (2004), pp. 433–453, https://doi.org/10.1016/j.cam.2003.12.047. · Zbl 1050.65017 |

[25] | D. S. Meek and D. J. Walton, A two-point G1 Hermite interpolating family of spirals, J. Comput. Appl. Math., 223 (2009), pp. 97–113, https://doi.org/10.1016/j.cam.2007.12.027. · Zbl 1156.65016 |

[26] | F. W. Olver, D. W. Lozier, R. F. Boisvert, and C. W. Clark, NIST Handbook of Mathematical Functions, Cambridge University Press, New York, 2010. |

[27] | A. Piazzi, C. G. L. Bianco, and M. Romano, \({{\eta } }^3\)-splines for the smooth path generation of wheeled mobile robots, IEEE Trans. Robotics, 23 (2007), pp. 1089–1095, https://doi.org/10.1109/TRO.2007.903816. |

[28] | A. Scheuer and T. Fraichard, Continuous-curvature path planning for car-like vehicles, in Proceedings of the 1997 IEEE/RSJ International Conference on Intelligent Robots and Systems. Vol. 2, 1997, pp. 997–1003, https://doi.org/10.1109/IROS.1997.655130. |

[29] | Y. Shan, W. Yang, C. Chen, J. Zhou, L. Zheng, and B. Li, CF-Pursuit: A pursuit method with a clothoid fitting and a fuzzy controller for autonomous vehicles, Internat. J. Adv. Robot. Syst., 12 (2015), https://doi.org/10.5772/61391. |

[30] | J. Stoer, Curve fitting with clothoidal splines, J. Res. Nat. Bur. Standards, 87 (1982), pp. 317–346, https://doi.org/10.6028/jres.087.021. · Zbl 0515.65011 |

[31] | H. J. Sussmann, The Markov-Dubins problem with angular acceleration control, in Proceedings of the 36th IEEE Conference on Decision and Control, Vol. 3, 1997, pp. 2639–2643, https://doi.org/10.1109/CDC.1997.657778. |

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.