Speaker: Michal Kleinbort, TAU

Title: The Increasing Role of Nearest-Neighbor Search in
Sampling-Based Motion Planning

Abstract:
---------
Sampling-based techniques for planning collision-free
motion for robots typically rely on two major components:
static collision detection and nearest-neighbor (NN)
search. Whereas the former is traditionally considered the
computational bottleneck in such methods (sometimes cited
for over 95% of the running time of these algorithms),
recently-introduced approaches have stronger dependence on
NN search.

In this talk I will discuss the changing role of
nearest-neighbor search in sampling-based algorithms,
survey variants in which the NN search becomes the main
computational cost, and present preliminary efficient
results for some of them. In particular I will show that
for asymptotically-optimal sampling-based algorithms, which
demand a larger number of neighbors per query over their
non-optimal counterparts, NN methods tailored to efficiently
finding the required number of neighbors can significantly
speed up their running time.

Based in part on joint work with Dan Halperin and Oren
Salzman.