Efficient nearest-neighbor search algorithms for sub-Riemannian geometries
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2019
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2019
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/122500 |
| _version_ | 1811084318745821184 |
|---|---|
| author | Varricchio, Valerio. |
| author2 | Emilio Frazzoll. |
| author_facet | Emilio Frazzoll. Varricchio, Valerio. |
| author_sort | Varricchio, Valerio. |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2019 |
| first_indexed | 2024-09-23T12:48:50Z |
| format | Thesis |
| id | mit-1721.1/122500 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T12:48:50Z |
| publishDate | 2019 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1225002019-10-14T03:03:39Z Efficient nearest-neighbor search algorithms for sub-Riemannian geometries Varricchio, Valerio. Emilio Frazzoll. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Aeronautics and Astronautics. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2019 Cataloged from PDF version of thesis. Includes bibliographical references. The Motion Planning problem has been at the core of a significant amount of research in the past decades and it has recently gained traction outside academia with the rise of commercial interest in self-driving cars and autonomous aerial vehicles. Among the leading algorithms to tackle the problem are sampling-based planners, such as Probabilistic Road Maps (PRMs), Rapidly-exploring Random Trees (RRTs) and a large number of variants thereof. In this thesis, we focus on a crucial building block shared by these algorithms: nearest-neighbor search. While nearest-neighbor search is known as the asymptotically dominant bottleneck of sampling-based planners, popular algorithms to efficiently identify neighbors are limited to robots capable of unconstrained motions, commonly referred to as holonomic. Nevertheless, this is rarely the case in the vast majority of practical applications, where the dynamical system at hand is often subject to a class of differential constraints called nonholonomic. We tackle the problem with sub-Riemannian geometries, a mathematical tool to study manifolds that can be traversed under local constraints. After drawing the parallel with nonholonomic mechanical systems, we exploit peculiar properties of these geometries and their natural notion of distance to devise specialized, efficient nearest-neighbor search algorithms. Our contributions are two-fold: First, we generalize existing space-partitioning techniques (k-d trees) to sub-Riemannian metrics. This is achieved by introducing i) a criterion - the outer Box Bound - that discards halfspaces consistently with the metric and ii) a space-partitioning technique - the Lie splitting strategy - that organizes the dataset for optimal asymptotic performance. Second, we propose pruning techniques to further improve the query runtime. This is achieved by reducing the number of distance evaluations required to discern the nearest neighbors and exploiting heuristics that provably approximate a sub-Riemannian metric up to a constant factor, asymptotically. by Valerio Varricchio. Ph. D. Ph.D. Massachusetts Institute of Technology, Department of Aeronautics and Astronautics 2019-10-11T21:53:26Z 2019-10-11T21:53:26Z 2019 2019 Thesis https://hdl.handle.net/1721.1/122500 1121187080 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 121 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Aeronautics and Astronautics. Varricchio, Valerio. Efficient nearest-neighbor search algorithms for sub-Riemannian geometries |
| title | Efficient nearest-neighbor search algorithms for sub-Riemannian geometries |
| title_full | Efficient nearest-neighbor search algorithms for sub-Riemannian geometries |
| title_fullStr | Efficient nearest-neighbor search algorithms for sub-Riemannian geometries |
| title_full_unstemmed | Efficient nearest-neighbor search algorithms for sub-Riemannian geometries |
| title_short | Efficient nearest-neighbor search algorithms for sub-Riemannian geometries |
| title_sort | efficient nearest neighbor search algorithms for sub riemannian geometries |
| topic | Aeronautics and Astronautics. |
| url | https://hdl.handle.net/1721.1/122500 |
| work_keys_str_mv | AT varricchiovalerio efficientnearestneighborsearchalgorithmsforsubriemanniangeometries |