# A Non-Smooth Numerical Optimization Approach to the Three-Point Dubins Problem (3 PDP)
## 6 Algorithms
### Pattern Search with Root Finder
In these examples, high performance is essential due to the routine's frequent invocation. Extensive numerical tests were conducted on a standard benchmark pool of 10,000 random Three-Point Dubins Problems. Two different sampling ranges were employed to reflect standard benchmarks and more representative scenarios with a middle point close to the

Figure 4: An example of the total length of a three-point Dubins path for comparison with [28]. (**Top**: path result with alternating colors for each arc; **Middle**: total length \(\ell\) as a function of the middle angle \(\theta_{m}\); **Bottom**: derivative of total length \(\ell\) as a function of the middle angle \(\theta_{m}\). )initial and final points. The results demonstrate that our proposed algorithms significantly outperform existing methods in terms of both iteration count and computational time. For the first sampling range, our pattern search and Pattern Trichotomy algorithms achieved an iteration count reduction factor of approximately 4.27 to 6.674 times compared to the DBM algorithm, and a time reduction factor ranging from \(\sim\)325 to \(\sim\)493 times. For the second sampling range, the iteration count reduction factors were similar with a range of 4.27 to 5.47 times, with the time reduction factors being 265 to 354 times compared to the DBM algorithm. Additionally, when combined with Algorithm 748, both the pattern search and Pattern Trichotomy methods consistently yielded results with machine precision, demonstrating their robustness and accuracy. These performance improvements are notable when compared to other state-of-the-art methods, such as the polynomial-based method (PBM) in [31], which achieves a 25-45 times speed-up over the DBM, and the geometry-based method (GBM) in [28], which offers a speed-up of approximately 150 times. Our methods achieve a computational speed-up factor exceeding 300 times compared to the DBM and less than half the time declared in [28]. Overall, our methods represent a significant advancement in solving the 3 PDP efficiently, making them highly suitable for applications where computational performance is critical. ## 9 Future Works

Our research is ongoing, and this work is part of a broader project. We are working on the generalization of the 3 PDP to the Multipoint Markov-Dubins problem (MPMDP). The goal is to provide a general and fast method to solve these Dubins-related challenging problems encountered in robotics. Our research aims to find a solution that does not rely on finite meshing exploration. Moreover, we are working on domain-specific applications for the 3 PDP. We are including our implementation into an autonomous parking framework [38]. The solution to the 3 PDP is used to efficiently compute an exploration trajectory with obstacle collision checking. Furthermore, we are extending the framework developed in [4] to include low-speed maneuvers with the 3 PDP. The goal is to employ a piecewise constant curvature profile for _valet_ maneuvers. Conceptualization, M.P., E.B. and M.F. ; Methodology, M.P., E.B. and M.F. The authors contributed equally to this work. All authors have read and agreed to the published version of the manuscript. This research received no external funding

**Data Availability Statement:** Not applicable. **Conflicts of Interest:** The authors declare no conflicts of interest. ## References

* [PERSON] et al. (2023) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] UAV Path Planning in Multi-Task Environments with Risks through Natural Language Understanding. _Drones_**2023**, \(7\), 147. [[https://doi.org/10.3390/drones7030147](https://doi.org/10.3390/drones7030147)]([https://doi.org/10.3390/drones7030147](https://doi.org/10.3390/drones7030147)). * [PERSON] et al. (2024) [PERSON] [PERSON]; [PERSON] [PERSON]; [PERSON] [PERSON]; [PERSON]; [PERSON] [PERSON]; [PERSON]; [PERSON] [PERSON] Algorithm Based on Morphological Operators for Shortness Path Planning. _Algorithms_**2024**, _17_, 184.