Complexity Reduction of the Three-Point Dubins Problem (3PDP) Via Symmetry Exploitation for Machine Learning Purposes
Marco Frego, Enrico Saccon, Davide De Martini, Luigi Palopoli
AI summary
Problem
The Three-Point Dubins Problem (3PDP) requires enumerating 18 possible path combinations and solving high-degree polynomials, making it computationally expensive and slow for real-time autonomous navigation.
Approach
The authors apply an invertible geometric transform to map the problem into a canonical space, reducing nine input variables to five bounded angles and curvature, then train KNN and neural networks to classify path types and regress the optimal heading angle.
Key results
- Reduced problem dimensionality from 9 to 5 variables via canonical circle mapping
- Achieved up to 100% accuracy in classifying the 18 admissible Dubins path types
- Trained a regression neural network to accurately predict the intermediate heading angle
- Demonstrated that ML predictions can warm-start traditional solvers to drastically cut computation time
Why it matters
Provides a fast, reliable alternative to slow enumeration methods, enabling real-time path planning for autonomous vehicles, drones, and robotic systems.
Abstract
This work proposes a machine learning approach for the Three-Point Dubins Problem (3PDP) based on classifi- cation and regression. The 3PDP is a path planning problem with Dubins curves through 3 waypoints. The goal is to find the heading at the intermediate point and the form of the two Dubins paths joining the three points. Classification is used to select the correct path type (out of 18) to avoid the trial-and- error enumeration of all cases; regression is employed to have a good initial guess for finding the heading angle. Our results are used to improve and speed-up existing methods in terms of efficiency and accuracy.