Massively parallel computation of globally optimal shortest paths with curvature penalization

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.