Geometriae Dedicata
Census of bounded curvature paths
Jean Díaz
A bounded curvature path is a continuously differentiable piece-wise \(C^2\) path with bounded absolute curvature connecting two points in the tangent bundle of a surface. These paths have been widely considered in computer science and engineering since the bound on curvature models the trajectory of the motion of robots under turning circle constraints. Analyzing global properties of spaces of bounded curvature paths is not a simple matter since the length variation between length minimizers of arbitrary close endpoints or directions is in many cases discontinuous. In this note, we develop a simple technology allowing us to partition the space of spaces of bounded curvature paths into one-parameter families. These families of spaces are classified in terms of the type of connected components their elements have (homotopy classes, isotopy classes, or isolated points) as we vary a parameter defined in the reals. Consequently, we answer a question raised by Dubins (Pac J Math 11(2):471–481, 1961).
Bounded curvature paths Regular homotopies Dubins paths
This article is dedicated to the memory of Paula Elisa Ayala Hoffmann.
Homotopy classes and deformations of Dubins paths
We would like to motivate a theory analyzing algorithmic aspects of deformations of piecewise bounded curvature paths of constant curvature. Many standard questions in computational geometry can be adapted for this class of paths.
In [6] we defined operations on bounded curvature paths being a finite number of concatenations of line segments and arcs of unit radius circles, the so-called cs paths. The line segments and arcs of circles are called components. The number of components is called the complexity of the path.3 Also in [6], we proved that a cs path can be constructed arbitrarily close to any given bounded curvature path. It is of interest to study the computational complexity of deforming cs paths.
It is not hard to see that for any given \(\textsc {x,y}\in T{\mathbb {R}}^2\) the space \(\Gamma (\textsc {x,y})\) has a finite number of Dubins paths. In Example 9.2 we index Dubins paths according to their length. The length minimizer in \(\Gamma (\textsc {x,y})\) is denoted by \(\gamma _0\).
Next, we relate the types of connected components, the number of local minima, number of global minima, existence of local maxima, and deformations of cs paths. In Fig. 14 we consider seven illustrations, and in Example 9.2 we consider seven items. We associate illustrations and items in an obvious way.
A schematic representation for spaces of bounded curvature paths. Each of the seven illustrations represent the connected components \(\Gamma (n)\subset \Gamma (\textsc {x,y})\) admitting Dubins paths, here represented by points. Points with the same color suggest that the associated paths are bounded-homotopic, see Figs. 2, 15, 16 and 17
Consider \(x=(0,0)\), \(X=e^{2\pi i}\in T_x{\mathbb {R}}^2\). In Fig. 14 we illustrate spaces \(\Gamma (\textsc {x,y})\) such that:
\(y=(z,0)\), \(z\in {\mathbb {R}}^+\), \(Y=e^{2\pi i}\in T_y{\mathbb {R}}^2\). This example corresponds to the Euclidean geometry case (up to isometries) where the single length minimizer between any two points is a line segment.
\(y=(4,-8)\), \(Y=e^{2\pi i}\in T_y{\mathbb {R}}^2\). There are four Dubins paths, \(\gamma _0\) being the length minimizer, see Fig. 15. The paths \(\gamma _0\) and \(\gamma _3\) are bounded-homotopic. This is checked in Proposition 4.3 and Fig. 13 in [6].
\(y=(z,0)\), \(z\ge 4\), \(Y=e^{\pi i}\in T_y{\mathbb {R}}^2\). There are four Dubins paths, with \(\gamma _0\) and \(\gamma _1\) being length minimizers. These four paths are not bounded-homotopic one to the other. In Fig. 1 in [2] we illustrate the two length minimizers.
\(y=(-2,1)\), \(Y=e^{-\frac{\pi }{4} i}\in T_y{\mathbb {R}}^2\). There are six Dubins paths, one being the length minimizer, see Fig. 2. The paths \(\gamma _0\) and \(\gamma _5\); \(\gamma _1\) and \(\gamma _4\), and \(\gamma _2\) and \(\gamma _3\) are pair-wise bounded-homotopic. This can be verified by applying Proposition 4.4 in [6].
\(y=(3,0)\), \(Y=e^{\frac{\pi }{3} i}\in T_y{\mathbb {R}}^2\). Since \(y\in B\), then \(\Theta (y)>0\), so we have that there exists a bounded isotopy class \(\Delta (\textsc {x,y})\), or equivalently \(\Omega \ne \emptyset \). In this case, the length minimiser in \(\Gamma (\textsc {x,y})\) is a unique csc path and it is an element in \(\Delta (\textsc {x,y})\). This is a consequence of Proposition 2.13 in [4] and Theorem 8.1 in [5].
Note that there are eight Dubins paths, one being the length minimizer (\(\gamma _0\) lies in \(\Omega \)), see Fig. 16. In addition, the paths \(\gamma _0\), \(w_1\) and \(w_2\) are bounded-isotopic one to the other since they are paths in \(\Delta (\textsc {x,y})\), see Theorem 5.4 in [6]. It seems plausible to think that \(w_1\) and \(w_2\) are local maxima (not local minima) of length. In addition, the path \(\gamma _3\) is the length minimizer in \(\Delta '(\textsc {x,y})\).
There are six Dubins paths, the length minimizer being an isolated point, see Fig. 17 and Theorem 3.9 in [5]. By a similar argument as the one in Proposition 4.4 in [6] we conclude that \(\gamma _1\) is bounded-homotopic to \(\gamma _4\).
\(x=y\) and \(X=Y\). Closed bounded curvature paths are not bounded-homotopic to a single point. In this case, the length minimiser \(\gamma _0\) is an isolated point of length zero, see Theorem 3.9 in [5]. There are two non-trivial length minimisers, say \(\gamma _1\) and \(\gamma _2\). These paths lie in the adjacent circles \(C_l(\textsc {x})\) and \(C_r(\textsc {x})\) respectively. It is easy to see that \(\gamma _1\) and \(\gamma _2\) lie in different homotopy classes since they have winding number 1 and \(-1\) respectively, see Theorem 4.6 in [2].
Spaces of bounded curvature paths may have four local minima of length. Note that \(\gamma _0\) and \(\gamma _3\) are bounded-homotopic, see Proposition 4.3 in [6]
Spaces of bounded curvature paths may have up to eight csc-ccc paths, local minima (or maxima) of length. Note that \(\gamma _3\) and \(\gamma _6\) are bounded-homotopic
After the previous examples, a natural task would be to determine for any pair of endpoints \(\textsc {x,y}\in T{\mathbb {R}}^2\) the exact number of homotopy classes admitting Dubins paths. This should be done after first describing all the possible scenarios for homotopies between Dubins paths.
A closely related problem is the following. Given \(\textsc {x},\textsc {y}_\theta \in T{\mathbb {R}}^2\), \(\theta \in (-\pi ,\pi ]\). Describe how the number of Dubins paths vary, as we vary \(\theta \in (-\pi ,\pi ]\). Also, describe how the type of all (up to eight?) Dubins paths vary for all the fibers. A description of the type of the global minimum (first Dubins path) has been obtained in [11].
Given \( \textsc {x},\textsc {y}\in T{\mathbb {R}}^2\). What are the complexity \(n>3\)cs paths of minimal length? For certain pairs the answer is trivial. What if \(d(x,y)<4\)?
Given two cs paths with prescribed complexity and lying in the same homotopy class. What is the minimal number of operations (or moves) to deform one path into the other? What are these moves?
Spaces of bounded curvature paths may have six local minima of length. Note that \(\gamma _1\) and \(\gamma _4\) are bounded-homotopic. It is of interest to classify the fibers \(\Gamma (\textsc {x},\textsc {y}_\theta )\) in terms of the way the type and number of Dubins paths changes as \(\theta \) varies, see also Figs. 2, 15 and 16
Agarwal, P.K., Biedl, T., Lazard, S., Robbins, S., Suri, S., Whitesides, S.: Curvature-constrained shortest paths in a convex polygon. SIAM J. Comput. 31(6), 1814–1851 (2002). (electronic)MathSciNetCrossRefzbMATHGoogle Scholar
Ayala, J.: Length minimising bounded curvature paths in homotopy classes. Topol. Appl. 193, 140–151 (2015)MathSciNetCrossRefzbMATHGoogle Scholar
Ayala, J.: On the topology of the spaces of curvature constrained plane curves. Adv. Geom. 17(3), 283–292 (2017)MathSciNetCrossRefzbMATHGoogle Scholar
Ayala, J., Kirszenblat, D., Rubinstein, J.H.: A geometric approach to shortest bounded curvature paths. Commun. Anal. Geom. 26(4), 679–697 (2018)MathSciNetCrossRefzbMATHGoogle Scholar
Ayala, J., Rubinstein, J.H.: Non-uniqueness of the Homotopy Class of Bounded Curvature Paths (2014) arXiv:1403.4911 [math.MG]
Ayala, J., Rubinstein, J.H.: The classification of homotopy classes of bounded curvature paths. Isr. J. Math. 213(1), 79–107 (2016)MathSciNetCrossRefzbMATHGoogle Scholar
Backer, J., Kirkpatrick, D.: Finding curvature-constrained paths that avoid polygonal obstacles. In: SCG 07: Proceedings of the Twenty-Third Annual Symposium on Computational Geometry, pp. 66–73, New York, NY, USA, ACM Press, 2007Google Scholar
Boissonat, J.-D., Cerezo, A., Leblond, K.: Shortest paths of bounded curvature in the plane. In: Proceedings of the IEEE International Conference on Robotics and Automation. 3. Piscataway, NJ. pp. 2315–2320 (May 1992)Google Scholar
Boissonnat, J.-D., Lazard, S.: A polynomial-time algorithm for computing shortest paths of bounded curvature amidst moderate obstacles. Int. J. Comput. Geom. Appl. 13(3), 189–229 (2003)MathSciNetCrossRefzbMATHGoogle Scholar
Brazil, M., Grossman, P.A., Thomas, D.A., Rubinstein, J.H., Lee, D., Wormald, N.C.: Constrained path optimisation for underground mine layout. In: The 2007 International Conference of Applied and Engineering Mathematics (ICAEM07), London, pp. 856–861 (2007)Google Scholar
Bui, X.-N., Soueres, P., Boissonnat, J.-D., Laumond, J.-P.: The Shortest Path Synthesis for Non-holonomic Robots Moving Forwards. Technical Report 2153, INRIA, Nice-Sophia-Antipolis (1994)Google Scholar
Chitsaz, H., LaValle, S.M.: Time-optimal paths for a Dubins airplane. In: 2007 46th IEEE Conference on Decision and Control. IEEE, pp. 2379–2384 (2007)Google Scholar
Chang, A., Brazil, M., Thomas, D.A., Rubinstein, J.H.: Curvature-constrained directional-cost paths in the plane. J. Glob. Optim. 53(4), 663–681 (2012)MathSciNetCrossRefzbMATHGoogle Scholar
Diaz, J., Ayala, J.: Dubins Explorer: A software for bounded curvature paths, http://joseayala.org/dubins_explorer.html (2014)
Dubins, L.E.: On curves of minimal length with constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am. J. Math. 79, 139–155 (1957)MathSciNetCrossRefzbMATHGoogle Scholar
Dubins, L.E.: On plane curve with curvature. Pac. J. Math. 11(2), 471–481 (1961)MathSciNetCrossRefzbMATHGoogle Scholar
Duindam, V., Xu, J., Alterovitz, R., Sastry, S., Goldberg, K.: 3D motion planning algorithms for steerable needles using inverse kinematics. Int. J. Rob. Res. 57, 535–549 (2009)Google Scholar
Fortune, S., Wilfong, G.: Planning constrained motion. Ann. Math. Artif. Intell. 3(1), 21–82 (1991). Algorithmic motion planning in roboticsMathSciNetCrossRefzbMATHGoogle Scholar
Jacobs, P., Canny, J.: Planning smooth paths for mobile robots. In: Li, Z., Canny, J. (eds.) Nonholonomic Motion Planning, pp. 271–342. Kluwer Academic, Norwell, MA (1992)Google Scholar
Johnson, H.H.: An application of the maximum principle to the geometry of plane curves. Proc. Am. Math. Soc. 44(2), 432–435 (1974)MathSciNetCrossRefzbMATHGoogle Scholar
Markov, A.A.: Some examples of the solution of a special kind of problem on greatest and least quantities. Soobshch. Karkovsk. Mat. Obshch. 1, 250–276 (1887)Google Scholar
Ny, J.L., Feron, E., Frazzoli, E.: On the Dubins traveling salesman problem. IEEE Trans. Autom. Control 57(1), 265–270 (2012)MathSciNetCrossRefzbMATHGoogle Scholar
Owen, M., Beard, R.W., McLain, T.W.: Implementing Dubins airplane paths on fixed-wing UAVs*. In: Valavanis, K., Vachtsevanos, G. (eds.) Handbook of Unmanned Aerial Vehicles, pp. 1677–1701. Springer, Dordrecht (2015)Google Scholar
Reeds, J.A., Shepp, L.A.: Optimal paths for a car that goes both forwards and backwards. Pac. J. Math. 145(2), 367–393 (1990)MathSciNetCrossRefGoogle Scholar
Reif, J., Wang, H.: The complexity of the two dimensional curvature-constrained shortest-path problem. In: WAFR Õ98: Proceedings of the Third Workshop on the Algorithmic Foundations of Robotics on Robotics : The Algorithmic Perspective, pp. 49–57, Natick, MA, USA. A. K. Peters, Ltd (1998)Google Scholar
Saldanha, N., Zulkhe, P.: Components of spaces of curves with constrained curvature on flat surfaces. Pac. J. Math. 281(1), 185–242 (2016)MathSciNetCrossRefGoogle Scholar
Shkel, A.M., Lumelsky, V.: Classification of the Dubins set. Robot. Auton. Syst. 34, 179–202 (2001)CrossRefzbMATHGoogle Scholar
Soueres, P., Laumond, J.P.: Shortest paths synthesis for a car-like robot. IEEE Trans. Autom. Control 41(5), 672–688 (1996)MathSciNetCrossRefzbMATHGoogle Scholar
Sussmann, H.J.: Shortest 3-dimensional paths with a prescribed curvature bound, from: Proceeings of 34th IEEE Conference on Decision and Control (New Orleans), pp. 3306–3312 (1995)Google Scholar
Tsourdos, A., White, B., Shanmugavel, M.: Cooperative Path Planning of Unmanned Aerial Vehicles. Wiley, Chichester (2010)Google Scholar
Whitney, H.: On regular closed curves in the plane. Compos. Math. 4, 276–284 (1937)MathSciNetzbMATHGoogle Scholar
1.FIAUniversidad Arturo PratIquiqueChile
Díaz, J. & Ayala, J. Geom Dedicata (2019). https://doi.org/10.1007/s10711-019-00444-2