# A Non-Smooth Numerical Optimization Approach to the Three-Point Dubins Problem (3 PDP)
## 6 Algorithms
### Pattern Search with Root Finder
However, if we compare the time required by the algorithms, the pattern search exhibits a factor of 270, and the Pattern Trichotomy, a factor of 320. Other speed-up factors (compared to the brute force DBM) declared in the literature are about 3 for the iDPP [12], which is a general method capable of solving the MPMDP with \(n\) points, adapted for the case \(n=3\); about 5 for the inversive geometry iterative method (IM) [26]; between 25 and 45 for the polynomial-based method (PBM) [31]; and about 150 for the geometry-based method (GBM) [28], (which solves exactly the case of points at distance \(d>d^{*}\) only, and gives a good approximation otherwise). Therefore, we can conclude that our methods are performant. Figure 3 illustrates the optimal configuration of the three-point Dubins connection in a challenging configuration. In the second subfigure, the total length showcases strong discontinuities resulting in a tiny interval of existence of the retrieved minimum. Furthermore, the derivative displays many noncontinuous points, hence demonstrating the non-applicability of derivative methods, at least globally. We compared the example proposed in [28; 31], where they tested their implementation versus the DBM. The test example has the following definition:

\[\mathbf{P_{i}}=(0,0),\quad\vartheta_{i}=\frac{\pi}{3},\quad\mathbf{P_{m}}=(10, 5),\quad\mathbf{P_{f}}=(15,20),\quad\vartheta_{f}=\frac{\pi}{6}. \tag{52}\]

The DBM yields the following solution:

\[\ell_{\text{total}}=27.11279494,\ \theta_{M}=0.8575935377. \tag{53}\] \begin{table}
\begin{tabular}{l c c c c} \hline \hline
**Algorithm** & **Iter Number** & \multicolumn{2}{c}{**Time (ms)**} & \\  & \(\mu\) & \(\sigma\) & \(\mu\) & \(\sigma\) & **N. Dubins Calls** \\ \hline Pattern search & 85.54 & 10.66 & 0.174 & 0.036 & \(\sim\)171 \\ Pattern search + 748 & 46.27 & 10.72 & 0.122 & 0.031 & \(\sim\)92 \\ Pattern Trichotomy & 73.69 & 7.97 & 0.150 & 0.026 & \(\sim\)147 \\ Pattern Trichotomy + 748 & 54.99 & 8.74 & 0.115 & 0.025 & \(\sim\)109 \\ \hline DBM – Algorithm 2 & 360 & 0.0 & 54.846 & 3.210 & 720 \\ iDPP [12] & 128 & 0.0 & 19.455 & 0.740 & 256 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The evaluation of the proposed algorithms with the benchmark test with mean \(\mu\) and standard deviation \(\sigma\) of iterations and computational times for the sampling in (50). \begin{table}
\begin{tabular}{l c c} \hline \hline
**Algorithm** & **Iter Number Ratio** & **Time Ratio** \\ \hline Pattern search & 4.27 & 325.66 \\ Pattern search + 748 & 6.57 & 471.78 \\ Pattern Trichotomy & 4.94 & 374.73 \\ Pattern Trichotomy + 748 & 6.67 & 493.50 \\ \hline iDPP [12] & 2.81 & 2.82 \\ IM [26] & n/a & 5 \\ PBM [31] & n/a & [25; 45] \\ GBM [28] & n/a & 150 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Comparison between number of iterations and time with respect to brute force DBM for sampling in (50). (n/a means not available. )This is a suboptimal solution, as highlighted in [28]. Their work claims to obtain a solution that is \(1.08\times 10^{-6}\) % better than that of the DBM. Our approach provides solutions with the following values, reported in Table 6 and Figure 4, representing our best solution. The DBM performs 360 iterations and will need to perform 100 times more to achieve the same precision as in [28]. Moreover, the pattern search and Pattern Trichotomy algorithms stop the iteration when a custom tolerance is reached (1/100 degree). On the other hand, when combined with Algorithm 748, our approach retrieves the solution to machine precision, yielding the true numerical minimum. ## 8 Conclusions

We presented two novel algorithms for solving the 3 PDP, a non-smooth constrained minimization problem and an optimal control problem. Our methods leverage the pattern search technique, integrating analytic derivatives within continuous-length function intervals to enhance computational efficiency. This improvement is crucial for the 3 PDP and may also be used for the Dubins Traveling Salesman Problem.