“Continuous-Curvature Path Generation Using Fermat's Spiral”
Authors: Anastasios M. Lekkas, Andreas Reason Dahl, Morten Breivik and Thor I. Fossen,Affiliation: NTNU, Centre for Ships and Ocean Structures, NTNU, Department of Marine Technology, NTNU, Department of Engineering Cybernetics and NTNU, Centre for Autonomous Marine Operations and Systems
Reference: 2013, Vol 34, No 4, pp. 183-198.
Keywords: Path planning, Fermat's spiral, continuous curvature, parametric curve, path tracking
Abstract: This paper proposes a novel methodology, based on Fermat's spiral (FS), for constructing curvature-continuous parametric paths in a plane. FS has a zero curvature at its origin, a property that allows it to be connected with a straight line smoothly, that is, without the curvature discontinuity which occurs at the transition point between a line and a circular arc when constructing Dubins paths. Furthermore, contrary to the computationally expensive clothoids, FS is described by very simple parametric equations that are trivial to compute. On the downside, computing the length of an FS arc involves a Gaussian hypergeometric function. However, this function is absolutely convergent and it is also shown that it poses no restrictions to the domain within which the length can be calculated. In addition, we present an alternative parametrization of FS which eliminates the parametric speed singularity at the origin, hence making the spiral suitable for path-tracking applications. A detailed description of how to construct curvature-continuous paths with FS is given.
PDF (889 Kb)
DOI: 10.4173/mic.2013.4.3DOI forward links to this article:
| [1] Daniel de A. Fernandes, Asgeir J. Sørensen and Decio C. Donha (2015), doi:10.4173/mic.2015.2.2 |
| [2] Anastasios M. Lekkas and Thor I. Fossen (2014), doi:10.1109/TCST.2014.2306774 |
| [3] Jinhong Noh, Jaehyung Park, Haiyun Wang, Jonghun Park, Seongryong Chang and Ukyoul Huh (2015), doi:10.1109/ICIT.2015.7125154 |
| [4] Anastasios M. Lekkas, Ann L. Roald and Morten Breivik (2016), doi:10.1016/j.ifacol.2016.10.313 |
| [5] Ibrahim A. Hameed (2017), doi:10.1007/978-3-319-48308-5_86 |
| [6] Mauro Candeloro, Anastasios M. Lekkas and Asgeir J. Sørensen (2017), doi:10.1016/j.conengprac.2017.01.007 |
| [7] Artur Wolek and Craig A. Woolsey (2017), doi:10.1007/978-3-319-55372-6_9 |
| [8] Yong Chen, Yiyu Cai, Jianmin Zheng and Daniel Thalmann (2017), doi:10.1109/TRO.2017.2699670 |
| [9] Albert Sans-Muntadas, Eleni Kelasidi, Kristin Y. Pettersen and Edmund Brekke (2017), doi:10.1109/CCTA.2017.8062549 |
| [10] Enrico Bertolazzi and Marco Frego (2018), doi:10.1016/j.cam.2018.03.029 |
| [11] Jian Wang, Aleksandr Y. Krasnov, Sergey A. Chepinskiy, Huimin Liu, Yifan Chen and Kirill A. Artemov (2018), doi:10.1109/ICPHYS.2018.8390750 |
| [12] Xiao Chen, Jianqiang Zhang, Min Yang, Liu Zhong and Jiao Dong (2018), doi:10.1109/CCDC.2018.8407982 |
| [13] Zheng Zeng, Lian Lian, Karl Sammut, Fangpo He, Youhong Tang and Andrew Lammas (2015), doi:10.1016/j.oceaneng.2015.10.007 |
| [14] Sungsu Park (2019), doi:10.1155/2019/3754182 |
| [15] Enrico Bertolazzi, Paolo Bevilacqua and Marco Frego (2019), doi:10.1016/j.matcom.2019.10.001 |
| [16] Botao Zhang, Aleksandr Y. Krasnov, Sergey A. Chepinskiy, Valery V. Grigoriev, Kirill A. Artemov, Duzhesheng Liao, Shengyi Zhang and Jian Wang (2019), doi:10.1109/MMAR.2019.8864705 |
| [17] Binghua Shi, Yixin Su, Danhong Zhang, Chen Wang and Mahmoud Samy AbouOmar (2019), doi:10.1109/ACCESS.2019.2955440 |
| [18] James P. Wilson, Khushboo Mittal and Shalabh Gupta (2019), doi:10.23919/OCEANS40490.2019.8962644 |
| [19] A R Bestugin, A D Filin and I A Kirshina (2020), doi:10.1088/1757-899X/862/5/052061 |
| [20] Jialei Zhang, Xianbo Xiang, Weijia Li, Shaolong Yang and Qin Zhang (2020), doi:10.1016/j.oceaneng.2020.107901 |
| [21] Marco Frego and Enrico Bertolazzi (2018), doi:10.23919/ECC.2018.8550554 |
| [22] Tom Stian Andersen, Ghada Bouzidi and Raymond Kristiansen (2018), doi:10.1109/ICUAS.2018.8453415 |
| [23] Tagir Muslimov and Rustem Munasypov (2020), doi:10.1007/978-3-030-60337-3_23 |
| [24] Anete Vagale, Rachid Oucheikh, Robin T. Bye, Ottar L. Osen and Thor I. Fossen (2021), doi:10.1007/s00773-020-00787-6 |
| [25] (2021), doi:10.1002/9781119575016.ref |
| [26] Belen Santos Leon, Jane Jean Kiam and Axel Schulte (2021), doi:10.1007/978-3-030-77091-4_11 |
| [27] Mirko Kokot, Damjan Miklic and Tamara Petrovic (2021), doi:10.1109/LRA.2021.3099086 |
| [28] Shilp Dixit, Umberto Montanaro, Mehrdad Dianati, Alexandros Mouzakitis and Saber Fallah (2021), doi:10.1109/TCST.2020.3024586 |
| [29] Thanh-Toan Nguyen, Ngoc-Huy Tran, Tran-Minh-Duc Ho and Hung Nguyen (2021), doi:10.1109/ATC52653.2021.9598281 |
| [30] Marco Frego (2022), doi:10.1016/j.amc.2021.126907 |
| [31] Jian Wang, Aleksandr Y. Krasnov, Sergey A. Chepinskiy, Huimin Liu, Yifan Chen and Sergey A. Kholunin (2018), doi:10.1109/ICPHYS.2018.8390749 |
| [32] Andreas B. Martinsen, Anastasios M. Lekkas and Sebastien Gros (2022), doi:10.1109/TCST.2021.3094617 |
| [33] Anh-Duy Nguyen, Ngoc-Huy Tran, Thanh-Toan Nguyen, An-Tri Nguyen and Thien-Phuc Tran (2022), doi:10.1007/978-3-030-99666-6_133 |
| [34] Ziheng Wang, Chunfeng Liu, Zhao Zhao, Tao Yu and Wenyu Qu (2022), doi:10.1109/CSCWD54268.2022.9776081 |
| [35] Austin Costley, Randall Christensen, Robert C. Leishman and Greg N. Droge (2022), doi:10.1109/TAES.2021.3138037 |
| [36] Seyed Mostafa Hosseini, Abolfazl Ranjbar Noei and Seyed Jalil Sadati Rostami (2022), doi:10.1177/01423312221112192 |
| [37] Sungsu Park (2022), doi:10.3390/app122211336 |
| [38] Enrico Bertolazzi, Cecilia Frego, Marco Frego, Seyed Mohsen Hosseini and Angelika Peer (2023), doi:10.1109/HISTELCON56357.2023.10365736 |
| [39] Justin Allen, Ryan Dorosh, Chris Ninatanta, Andrew Allen, Linlin Shui, Kyle Yoshida, Jiecai Luo and Ming Luo (2024), doi:10.1109/LRA.2024.3369473 |
| [40] Leah Buechley, Jaime Gould and Fiona Bell (2024), doi:10.1145/3613904.3642155 |
| [41] Guiqiang Bai, Yanli Chen, Xinyu Hu and Junhong Cui (2024), doi:10.1109/TITS.2024.3352902 |
| [42] Maged Marghany (2024), doi:10.1016/B978-0-443-19155-8.00008-8 |
| [43] Cai Huahui (2024), doi:10.1109/ACCTCS61748.2024.00009 |
| [44] Keren Lois Daniel and Ramesh Chandra Poonia (2024), doi:10.2174/0126662558258394231228080539 |
| [45] Ronny Tsalik, Siddhardha Kedarisetty and Tal Shima (2024), doi:10.2514/1.G008283 |
| [46] Le Phuc Minh Nguyen and Ngoc-Huy Tran (2024), doi:10.1007/978-3-031-60154-5_29 |
| [47] Oivind K. Kjerstad and Erlend M. Coates (2024), doi:10.1016/j.ifacol.2024.10.024 |
[1] Abramowitz, M. and Stegun, I. (1970). Handbook of mathematical functions, Dover Publishing Inc. New York.
[2] Bakolas, E. and Tsiotras, P. (2010). Time-optimal synthesis for the Zermelo-Markov-Dubins problem: The constant wind case, In American Control Conference. IEEE, Baltimore, Maryland, USA.
[3] Bakolas, E. and Tsiotras, P. (2013). Optimal synthesis of the Zermelo--Markov--Dubins problem in a constant drift field, Journal of Optimization Theory and Applications. 156(2):469--492. doi:10.1007/s10957-012-0128-0
[4] Barsky, B.A. and DeRose, T.D. (1989). Geometric continuity of parametric curves: three equivalent characterizations, IEEE Computer Graphics and Applications. 9(6):60--69. doi:10.1109/38.41470
[5] Breivik, M. and Fossen, T.I. (2004). Path following for marine surface vessels, In Proceedings of the OTO'04. Kobe, Japan, 2004. doi:10.1109/OCEANS.2004.1406507
[6] Breivik, M. and Fossen, T.I. (2004). Path following of straight lines and circles for marine surface vessels, In Proceedings of the IFAC Conference on Control Applications in Marine Systems. Ancona, Italy, 2004.
[7] Breivik, M. and Fossen, T.I. (2009). Guidance laws for autonomous underwater vehicles, chapter4, pages 51--76, INTECH Education and Publishing.
[8] Bruyninckx, H. and Reynaerts, D. (1997). Path planning for mobile and hyper-redundant robots using Pythagorean hodograph curves, In Proceedings of the 8th International Conference on Advanced Robotics. IEEE, Monterey, CA, USA. doi:10.1109/ICAR.1997.620243
[9] Candeloro, M., Lekkas, A.M., Sorensen, A.J., and Fossen, T.I. (2013). Continuous curvature path planning using Voronoi diagrams and Fermat's spirals, In 9th IFAC Conference on Control Applications in Marine Systems. Osaka, Japan.
[10] Chang, A.J., Brazil, M., Rubinstein, J.H., and Thomas, D.A. (2012). Curvature-constrained directional-cost paths in the plane, Journal of Global Optimization. 53(4):663--681. doi:10.1007/s10898-011-9730-1
[11] Chitsaz, H. and LaValle, S.M. (2007). Time-optimal paths for a Dubins airplane, In Proceedings of the 46th IEEE Conference on Decision and Control. New Orleans, Louisiana, USA. doi:10.1109/CDC.2007.4434966
[12] Dahl, A.R. (2013). Path Planning and Guidance for Marine Surface Vessels, Master's thesis, Norwegian University of Science and Technology, 2013.
[13] Dubins, L.E. (1957). On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents, American Journal of Mathematics. 79(3):497--516. doi:10.2307/2372560
[14] Eriksson-Bique, S., Kirkpatrick, D., and Polishchuk, V. (2012). Discrete Dubins paths, arXiv preprint arXiv:1211.2365.
[15] Farin, G. and Sapidis, N. (1989). Curvature and the fairness of curves and surfaces, IEEE Computer Graphics and Applications. 9(2):52--57. doi:10.1109/38.19051
[16] Farouki, R.T. (1997). Pythagorean-hodograph quintic transition curves of monotone curvature, Computer-Aided Design. 29(9):601--606. doi:10.1016/S0010-4485(97)00004-3
[17] Farouki, R.T. (2008). Pythagorean---hodograph Curves, Springer. doi:10.1007/978-3-540-73398-0
[18] Farouki, R.T. and Sakkalis, T. (1990). Pythagorean hodographs, IBM Journal of Research and Development. 34(5):736--752. doi:10.1147/rd.345.0736
[19] Farouki, R.T. and Sakkalis, T. (1991). Real rational curves are not `unit speed', Computer Aided Geometric Design. 8(2):151--157. doi:10.1016/0167-8396(91)90040-I
[20] Fermat, P. (1679). Ad locos planos et solidos isagoge, Varia Opera Mathematica.
[21] Fossen, T.I. (2011). Handbook of Marine Craft Hydrodynamics and Motion Control, John Wiley and Sons Ltd.. doi:10.1002/9781119994138
[22] Fossen, T.I. and Lekkas, A.M. (2014). Direct and indirect adaptive integral line-of-sight path-following controllers for marine craft exposed to ocean currents, International Journal of Adaptive Control and Signal Processing. (submitted).
[23] Fraichard, T. and Scheuer, A. (2004). From Reeds and Shepp's to continuous-curvature paths, IEEE Transactions on Robotics. 20(6):1025--1035. doi:10.1109/TRO.2004.833789
[24] Gajny, L., Bearee, R., Nyiri, E., and Gibaru, O. (2012). Path planning with PH G2 splines in R2, In Proceedings of the 1st International Conference on Systems and Computer Science. IEEE, Lille, France. doi:10.1109/IConSCS.2012.6502455
[25] Harary, G. and Tal, A. (2012). 3D Euler spirals for 3D curve completion, Computational Geometry. 45(3):115--126. doi:10.1016/j.comgeo.2011.10.001
[26] Haugen, J. (2010). Guidance Algorithms for Planar Path-based Motion Control Scenarios, Master's thesis, Norwegian University of Science and Technology, 2010.
[27] Hota, S. and Ghose, D. (2013). Optimal trajectory generation for convergence to a rectilinear path, Journal of Intelligent & Robotic Systems. pages 1--20.
[28] Jorgensen, U. and Skjetne, R. (2012). Generating safe and equally long trajectories for multiple unmanned agents, In 20th Mediterranean Conference on Control & Automation (MED). IEEE, Barcelona, Spain. doi:10.1109/MED.2012.6265862
[29] LaValle, S.M. (2006). Planning algorithms, Cambridge university press. doi:10.1017/CBO9780511546877
[30] Lekkas, A.M. and Fossen, T.I. (2013). Line-of-Sight Guidance for Path Following of Marine Vehicles, chapter 5, in Advanced in Marine Robotics, pages 63--92, LAP LAMBERT Academic Publishing (O. Gal, Ed.).
[31] Pearson, J.W. (2009). Computation of hypergeometric functions, Master's thesis, University of Oxford.
[32] Peters, J. (2012). Changing variables, IEEE Computer Graphics and Applications. 32(3):88--93. doi:10.1109/MCG.2012.51
[33] Reeds, J.A. and Shepp, L.A. (1990). Optimal paths for a car that goes both forwards and backwards, Pacific Journal of Mathematics. 145(2):367--393. doi:10.2140/pjm.1990.145.367
[34] Shanmugavel, M., Tsourdos, A., White, B., and Zbikowski, R. (2010). Co-operative path planning of multiple UAVs using Dubins paths with clothoid arcs, Control Engineering Practice. 18(9):1084--1092. doi:10.1016/j.conengprac.2009.02.010
[35] Shanmugavel, M., Tsourdos, A., Zbikowski, R., and White, B. (2007). Path planning of multiple UAVs with clothoid curves in two dimensions, In Proceedings of the 17th IFAC Symposium on Automatic Control in Aerospace. Toulouse, France, 2007.
[36] Shanmugavel, M., Tsourdos, A., Zbikowski, R., and White, B.A. (2007). 3D path planning for multiple UAVs using Pythagorean hodograph curves, In AIAA Guidance, Navigation, and Control Conference and Exhibit, Hilton Head, South Carolina. 2007.
[37] Techy, L. and Woolsey, C.A. (2009). Minimum-time path planning for unmanned aerial vehicles in steady uniform winds, Journal of Guidance, Control, and Dynamics. 32(6):1736--1746. doi:10.2514/1.44580
[38] Toussaint, G.J., Basar, T., and Bullo, F. (2001). Motion planning for nonlinear underactuated vehicles using H-Infinity techniques, In Proceedings of the American Control Conference. IEEE, Arlington, Virginia, USA.
[39] Tsourdos, A., White, B., and Shanmugavel, M. (2011). Cooperative path planning of unmanned aerial vehicles, Wiley Online Library.
BibTeX:
@article{MIC-2013-4-3,
title={{Continuous-Curvature Path Generation Using Fermat's Spiral}},
author={Lekkas, Anastasios M. and Dahl, Andreas Reason and Breivik, Morten and Fossen, Thor I.},
journal={Modeling, Identification and Control},
volume={34},
number={4},
pages={183--198},
year={2013},
doi={10.4173/mic.2013.4.3},
publisher={Norwegian Society of Automatic Control}
};