Back to Search
Start Over
An Efficient Semi-Real-Time Algorithm for Path Planning in the Hamilton-Jacobi Formulation
- Publication Year :
- 2023
-
Abstract
- We present a semi-real-time algorithm for minimal-time optimal path planning based on optimal control theory, dynamic programming, and Hamilton-Jacobi (HJ) equations. Partial differential equation (PDE) based optimal path planning methods are well-established in the literature, and provide an interpretable alternative to black-box machine learning algorithms. However, due to the computational burden of grid-based PDE solvers, many previous methods do not scale well to high dimensional problems and are not applicable in real-time scenarios even for low dimensional problems. We present a semi-real-time algorithm for optimal path planning in the HJ formulation, using grid-free numerical methods based on Hopf-Lax formulas. In doing so, we retain the intepretablity of PDE based path planning, but because the numerical method is grid-free, it is efficient and does not suffer from the curse of dimensionality, and thus can be applied in semi-real-time and account for realistic concerns like obstacle discovery. This represents a significant step in averting the tradeoff between interpretability and efficiency. We present the algorithm with application to synthetic examples of isotropic motion planning in two-dimensions, though with slight adjustments, it could be applied to many other problems.<br />Comment: 6 pages, 2 figures, submitted to American Control Conference 2024
- Subjects :
- Mathematics - Optimization and Control
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2309.02357
- Document Type :
- Working Paper