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 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 introducing pivot points. We then implicitly
define Voronoi regions an 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.
본 연구에서는 샘플링 기반 모션 플래너 (sampling-based motion planner) 를 위한 고차원 데이터에 대해
빠르고 정확한 k-근접점 탐색 알고리즘 (k-nearest neighbor search algorithm) 을 제안한다.
제안하는 방법은 국지성 민감 해싱 (locality sensitive hashing - LSH) 에 기반 하지만, 임의의 거리
함수 (distance metric) 에 동작하도록 확장 하였으며 또한 모션 플래닝에서 생성되는 불규칙적인 샘플들에 대해서도
잘 동작하도록 디자인 되었다. 이를 위하여 우리는 임의의 거리 함수로 정의된 공간의 샘플들을 중심점 (pivot) 을 이용하여
간단한 유클리디언 공간 (Euclidean space) 의 점들로 변환한다. 그리고 보로노이 지역들 (Voronoi
regions) 을 간접적으로 정의하고, 각각의 보로노이 지역들에 대해 국지적으로 LSH 방법을 알맞는 매개 변수와 함께
적용한다. 제안한 방법을 고차원 모션 플래닝 문제에 적용한 실험에서 기존 방법들 대비 3배 이상의 속도 향상과 더불어 보다
나은 정확도를 보였다.
