Proximity Queries for Absolutely Continuous Parametric Curves
This addresses a computational bottleneck in motion planning for autonomous robots like self-driving cars, but it is incremental as it builds on existing curve bounding techniques.
The paper tackles the problem of evaluating proximity between planned robot paths and obstacles, which is non-convex and computationally intensive, by presenting methods for absolutely continuous parametric curves to compute minimum separating distance, tolerance verification, and collision detection, demonstrating efficiency and accuracy in numerical simulations.
In motion planning problems for autonomous robots, such as self-driving cars, the robot must ensure that its planned path is not in close proximity to obstacles in the environment. However, the problem of evaluating the proximity is generally non-convex and serves as a significant computational bottleneck for motion planning algorithms. In this paper, we present methods for a general class of absolutely continuous parametric curves to compute: (i) the minimum separating distance, (ii) tolerance verification, and (iii) collision detection. Our methods efficiently compute bounds on obstacle proximity by bounding the curve in a convex region. This bound is based on an upper bound on the curve arc length that can be expressed in closed form for a useful class of parametric curves including curves with trigonometric or polynomial bases. We demonstrate the computational efficiency and accuracy of our approach through numerical simulations of several proximity problems.