Personal tools
You are here: Home CG seminar 2018 The critical radius in sampling-based motion planning
« June 2020 »
Log in

Forgot your password?

The critical radius in sampling-based motion planning

Wednesday, November 1st, 2017, 16:10

Schreiber 309


The Critical Radius in Sampling-Based Motion Planning

Kiril Solovey, TAU


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.
Document Actions