Name
Abstract | ||
|---|---|---|
We present a fast, yet accurate k-nearest neighbor search algorithm for high-dimensional sampling-based motion planners. Our technique is built on top of Locality Sensitive Hashing (LSH), but is extended to support arbitrary distance metrics used for motion planning problems and adapt irregular distributions of samples generated in the configuration space. To enable such novel characteristics our method embeds samples generated in the configuration space into a simple l2 norm space by using pivot points. We then implicitly define Voronoi regions and use local LSHs with varying quantization factors for those Voronoi regions. We have applied our method and other prior techniques to high-dimensional motion planning problems. Our method is able to show performance improvement by a factor of up to three times even with higher accuracy over prior, approximate nearest neighbor search techniques. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/IROS.2013.6697130 | IROS |
Keywords | Field | DocType |
k-nearest neighbor search algorithm,voronoi regions,quantization factors,pivot points,mobile robots,distance metrics,computational geometry,vlsh,high-dimensional sampling-based motion planner,robot configurations,search problems,path planning,sample irregular distribution,configuration space,voronoi-based locality sensitive hashing,sampling methods,l2 norm space | Search algorithm,Computer science,Computational geometry,Voronoi diagram,Artificial intelligence,Nearest neighbor search,Locality-sensitive hashing,Motion planning,Computer vision,Mathematical optimization,Algorithm,Norm (mathematics),Configuration space | Conference |
ISSN | Citations | PageRank |
2153-0858 | 1 | 0.35 |
References | Authors | |
11 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tieu Lin Loi | 1 | 1 | 0.35 |
| Jae-Pil Heo | 2 | 135 | 8.78 |
| Junghwan Lee | 3 | 50 | 12.51 |
| Sung-Eui Yoon | 4 | 798 | 54.82 |