| Title | Asymptotically Optimal Pruning for Nonholonomic Nearest-Neighbor Search |
| Publication Type | Conference Paper |
| Year of Publication | 2018 |
| Authors | Varricchio, Valerio, Frazzoli, Emilio |
| Conference Name | 2018 IEEE Conference on Decision and Control (CDC) |
| Date Published | dec |
| Keywords | asymptotic 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 |
| Abstract | Nearest-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. |
| DOI | 10.1109/CDC.2018.8618732 |
| Citation Key | varricchio_asymptotically_2018 |
Asymptotically Optimal Pruning for Nonholonomic Nearest-Neighbor Search