Topological Nearest-Neighbor Filtering for Sampling-Based Planners
| Autor: | Andrew Bregger, Nancy M. Amato, Read Sandstrem, Ben Smith, Shawna Thomas |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Computer Science::Robotics
Computer science 020204 information systems Hash function 0202 electrical engineering electronic engineering information engineering Sampling (statistics) 020201 artificial intelligence & image processing 02 engineering and technology Motion planning Filter (signal processing) Topology Bottleneck k-nearest neighbors algorithm |
| Zdroj: | ICRA |
| DOI: | 10.1109/icra.2018.8460896 |
| Popis: | Nearest-neighbor finding is a major bottleneck for sampling-based motion planning algorithms. The cost of finding nearest neighbors grows with the size of the roadmap, leading to significant slowdowns for problems which require many configurations to find a solution. Prior work has investigated relieving this pressure with quicker computational techniques, such as kd-trees or locality-sensitive hashing. In this work, we investigate an alternative direction for expediting this process based on workspace connectivity. We present an algorithm called Topological Nearest-Neighbor Filtering, which employs a workspace decomposition to select a topologically relevant set of candidate neighbor configurations as a pre-processing step for a nearest-neighbor algorithm. We investigate the application of this filter to several varieties of RRT and demonstrate that the filter improves both nearest-neighbor time and overall planning performance. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|