# A Non-Smooth Numerical Optimization Approach to the Three-Point Dubins Problem (3 PDP)
## 2 Background and State-of-the-Art Methods  
Several results approximate the solution of the MPMDP under the hypothesis that the distance between consecutive points is at least \(d^{\star}:=4\rho_{\min}=4/\kappa_{\max}\), a condition that implies that only CSC paths will constitute the solution, so that cases CCC are not considered. Under this hypothesis, in defining the angles at the waypoints as the angles of the line segment connecting the adjacent points in the sequence, the approximation yields a path that is not more than 1.91 times longer than the optimal one. Without the \(d>d^{\star}\) distance assumption, there is a method to construct a path that is at most 5.03 times longer than the optimal, a factor which decreases to 2.58 if the distance between the points is more than \(d^{\star}\)[25; 26]. Apart from the bounds, some exact results can be derived and computed in different ways, covering some or all the possible feasible paths. The first exact result in the problem of visiting an ordered sequence of waypoints with a Dubins path is given in [25; 27; 28], under the assumption that the distance between consecutive points is at least \(d^{\star}\), thus considering the CSC cases only. It is shown that the problem becomes locally convex over an open region; however, this region is not even connected, and therefore, \(2^{n-2}\) subproblems must be solved, each containing a local minimum of the original problem. In their analysis, the authors reduce the complexity to \(2^{k}\), with \(k\) being the number of sharp turns of the path. A different approach, based on inversive geometry [26], proposes an iterative method (IM) to solve the 3 PDP with a \(3\times 3\) non-linear system of equations to find the optimal angle at the middle point for paths CSC-CSC (or shorter words). This method that combines geometric arguments with the bisection algorithm is compared with the brute force method of discretizing the middle angle with 360 samples and testing all cases (called the discretization-based method--DBM [29; 30]), showing a computational time improvement ranging from a factor of about 14 in the best case, for points that have a distance greater than \(d^{\star}\), to a worse case improvement of a factor of 5 for points that are closer than \(d^{\star}\). Regarding accuracy, the iterative method in [26] is generally more precise than the brute force DBM. However, it does not cover the cases where the path contains a CCC word. An approach that covers all cases and is based on algebraic methods is the one proposed in [31], where the trigonometric relations that characterize the solution are transformed into polynomials of relatively high degree, from 4 to 20. In the paper, it is discussed that although, in principle, there are \(6\times 6\) potential path types (4 CSCs and 2 CCCs for each pair of points), of these 36 cases, only 18 are optimal candidates; see Table 1.  
The algorithm requires constructing and finding the (real) roots of these 18 polynomials and, for each admissible root, testing the length of the path. The angle corresponding to the shortest length is elected as the optimal angle at the midpoint. This method is called the polynomial-based method, PBM, and requires, in the worst case, the computation of \(2\times 4\ +\ 2\times 6+10\times 8+4\times 20\ =\ 180\) pairs of Dubins paths, plus the time to find up to their 180 roots. Depending on the distance of the points, this method achieves a speed-up ranging from 25 to 45 times the speed of the DBM with 360 samples [31]. A recent method [28] is based on geometrical observations and solves the case for points having a distance larger than \(d^{*}\); thus, the cases are CSC (but not CCC). It takes the name of the geometry-based method or GBM. This method is purely geometrical and bases the solution on the construction of a special ellipse. The solution is computed by building circles of radius \(\rho_{\min}\) with tangents on the initial and final points (four possible circles).