VLSH: Voronoi-based Locality Sensitive Hashing

by Tieu Lin Loi, Jae-Pil Heo, Junghwan Lee and Sung-Eui Yoon
(To appear at) IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2013

The left figure shows disconnected roadmaps when we use only points contained in Voronoi regions vr¡Ç(pi), while the right figure shows a well-connected roadmap by using the extended Voronoi regions evr¡Ç(pi). Green edges in the right figure are additionally connected by using evr¡Ç(p2) of a pivot p2.

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.

Contents

Paper (PDF) 
Tieu Lin Loi, Jae-Pil Heo, Junghwan Lee and Sung-Eui Yoon
IROS, 2013
Talk slide

Dept. of Computer Science
KAIST
373-1 Guseong-dong, Yuseong-gu, Daejeon, 305-701
South Korea
sglabkaist dot gmail dot com