Abstract

————

Motion planning is a fundamental problem in robotics: allowing autonomous robots to efficiently navigate in environments cluttered with obstacles. Sampling-based algorithms, which were first described two decades ago, have made a great impact on the field of robotics by providing simple but highly-effective tools for motion planning. These techniques aim to capture the structure of the problem by randomly sampling robot configurations and connecting nearby samples, to form discrete graphs which approximate the robot’s range of movements.

In this talk I will describe a new result concerning the theoretical asymptotic guarantees of sampling-based planners, which significantly improves upon the celebrated work of Karaman and Frazzoli (2011). Particularly, we prove that the number of neighbors considered for connection to each sample can be reduced from O(log n) (where n is the number of samples) to only O(1), without sacrificing asymptotic completeness or optimality. Continuum percolation theory plays an important role in our proofs.

The talk is based on the following paper: 

Kiril Solovey and Michal Kleinbort, “The Critical Radius in Sampling-Based Motion Planning”, arXiv:1709.06290, 2017.

Biography

—————

Kiril Solovey is a Ph.D. student at the School of Computer Science, Tel-Aviv University, Israel, working under the guidance of Dan Halperin. His research interests include sampling-based techniques for robot motion planning, multi-robot systems, and computational geometry. Kiril is a Clore Scholar and a recipient of the Best Student Paper award at Robotics: Science and Systems 2015.

Contact information: kirilsol@post.tau.ac.il / kirilsol.github.io