# A Non-Smooth Numerical Optimization Approach to the Three-Point Dubins Problem (3 PDP)
## 6 Algorithms
### Pattern Search with Root Finder
In the first sampling, we took the middle point uniformly distributed in \([-10,10]\times[-10,10]\). The initial and final angles were in the interval \([-\pi,\pi]\), and the maximum curvature was kept constant at \(1\). The same test was conducted in [26; 28; 31]. In summary,

\[(x_{m},y_{m})\in[-10,10]\times[-10,10],\quad\theta_{i},\ \theta_{f}\in[-\pi, \pi],\quad\text{and}\quad\kappa_{max}=1, \tag{50}\]

The second test sampled the middle point randomly inside the region \([-2,2]\times[-2,2]\). As before, the initial and final angles were randomly sampled in the interval \([-\pi,\pi]\), and we randomly generated the maximum curvature inside the interval \([0.1,1.5]\). In brief,

\[(x_{m},y_{m})\in[-2,2]\times[-2,2],\quad\theta_{i},\ \theta_{f}\in[-\pi, \pi],\quad\text{and}\quad\kappa_{max}\in[0.1,1.5]. \tag{51}\]

We proposed the second test because, when the middle point is distant from the initial and the final points, we lose two potential solutions of the 3 PDP. When the distance is greater than the maximum curvature inverse, we can only observe 4 of the 18 possible solutions, which are the ones with the straight line in the middle. In Tables 2 and 4, we present the mean and standard deviation of both the number of iterations and computational time for the sampling in (50) and (51), respectively. The last columns of the tables present the number of calls to the Dubins function, on average. It is important to highlight that the number of iterations is linked to the number of Dubins calls (twice). The information is redundant, but most of the available state-of-the-art publications report the number of Dubins calls. The computational time is measured in milliseconds. It is important to stress that the computational time depends on the implementation. Tables 3 and 5 present a comparison between different approaches scaling the results with the DBM benchmark. The ratio is computed as the number of iterations and time of the algorithm divided by the number of iterations and time of the DBM algorithm. The results are presented for the sampling in (50) and (51), respectively. The four tables (Tables 2-5) showcase the strong performance of our algorithm when the middle point is distant, on average. In fact, in this occurrence, both the length and the derivative do not jump; hence, non-smooth root-finding algorithms can be used to obtain the minimum length curve. The results show that the proposed algorithms outperform the benchmark algorithms in terms of the number of iterations and time. The pattern search with the root finder and the pattern trichotomy algorithms are more efficient than the brute force (DBM) and refinement (iDDP) algorithms by a factor ranging between 4.27 and 6.67 times depending on the proposed sampling. Moreover, it should be noted that these methods do not achieve the same precision: indeed, the DBM evaluates the problem with a 1-degree precision, while the other methods have a precision of \(10^{-2}\) degrees. However, the threshold precision can be set to a custom value in our proposed methods. The Pattern Trichotomy algorithm is the most efficient one. It requires the fewest iterations and the least amount of time. The pattern search algorithm is slightly less efficient than the Pattern Trichotomy algorithm. However, it is still more efficient than the DBM, IM, PBM, and iDDP algorithms. The pattern search algorithm combined with the root finder (algorithm 748) requires fewer iterations on average. However, the trichotomy algorithm implementation allows a speed-up in the computational time. Hence, the patterntrichotomy algorithm equipped with a root finder is the fastest and most efficient. Furthermore, when root finding is employed, both pattern search with algorithm 748 and Pattern Trichotomy with algorithm 748 yield the same exact result up to machine precision. Looking at the comparison in Table 5, we can see that the pattern search and Pattern Trichotomy algorithms require approximately 4 times fewer iterations than the DBM algorithm, and 2.8 times with respect to the iDPP.