Massively parallel computation of globally optimal shortest paths with curvature penalization
Open Access
- 8 November 2022
- journal article
- research article
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 35 (2)
Abstract
We address the computation of paths globally minimizing an energy involving their curvature, with given endpoints and tangents at these endpoints, according to models known as the Reeds‐Shepp car (reversible and forward variants), the Euler‐Mumford elasticae, and the Dubins car. For that purpose, we numerically solve degenerate variants of the eikonal equation, on a three‐dimensional domain, in a massively parallel manner on a graphical processing unit. Due to the high anisotropy and nonlinearity of the addressed Partial Differential Equation, the discretization stencil is rather wide, has numerous elements, and is costly to generate, which leads to subtle compromises between computational cost, memory usage, and cache coherency. Accelerations by a factor 30 to 120 are obtained w.r.t a sequential implementation. The efficiency and the robustness of the method is illustrated in various contexts, ranging from motion planning to vessel segmentation and radar configuration.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Optimal Synthesis of the Zermelo–Markov–Dubins Problem in a Constant Drift FieldJournal of Optimization Theory and Applications, 2012
- Existence of planar curves minimizing length and curvatureProceedings of the Steklov Institute of Mathematics, 2010
- Parallel algorithms for approximation of distance maps on parametric surfacesACM Transactions on Graphics, 2008
- A Fast Iterative Method for Eikonal EquationsSIAM Journal on Scientific Computing, 2008
- Finite-element Discretization of Static Hamilton-Jacobi Equations based on a Local Variational PrincipleComputing and Visualization in Science, 2006
- Ordered Upwind Methods for Static Hamilton--Jacobi Equations: Theory and AlgorithmsSIAM Journal on Numerical Analysis, 2003
- A fast marching level set method for monotonically advancing fronts.Proceedings of the National Academy of Sciences, 1996
- Efficient algorithms for globally optimal trajectoriesIEEE Transactions on Automatic Control, 1995
- A Viscosity Solutions Approach to Shape-From-ShadingSIAM Journal on Numerical Analysis, 1992
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987