Visible to the public Asymptotically Optimal Pruning for Nonholonomic Nearest-Neighbor Search

TitleAsymptotically Optimal Pruning for Nonholonomic Nearest-Neighbor Search
Publication TypeConference Paper
Year of Publication2018
AuthorsVarricchio, Valerio, Frazzoli, Emilio
Conference Name2018 IEEE Conference on Decision and Control (CDC)
Date Publisheddec
Keywordsasymptotic computational bottleneck, asymptotic properties, computational complexity, computationally demanding task, differential geometry, distance evaluations, exact Nearest-Neighbor Search, explicit distance comparisons, geodesic distance, k-d tree algorithm, Measurement, Metrics, mobile robots, nearest neighbor search, nearest neighbour methods, nonholonomic constraints, optimal pruning, path planning, pruning techniques, pubcrawl, sampling-based motion planning algorithms, search problems, set theory, tree searching
AbstractNearest-Neighbor Search (NNS) arises as a key component of sampling-based motion planning algorithms and it is known as their asymptotic computational bottleneck. Algorithms for exact Nearest-Neighbor Search rely on explicit distance comparisons to different extents. However, in motion planning, evaluating distances is generally a computationally demanding task, since the metric is induced by the minimum cost of steering a dynamical system between states. In the presence of driftless nonholonomic constraints, we propose efficient pruning techniques for the k-d tree algorithm that drastically reduce the number of distance evaluations performed during a query. These techniques exploit computationally convenient lower and upper bounds to the geodesic distance of the corresponding sub-Riemannian geometry. Based on asymptotic properties of the reachable sets, we show that the proposed pruning techniques are optimal, modulo a constant factor, and we provide experimental results with the Reeds-Shepp vehicle model.
Citation Keyvarricchio_asymptotically_2018