הרצאה פומבית - Efficient high-quality motion planning

Abstract: 

Motion planning is a fundamental research topic in robotics with applications in diverse domains such as surgical planning, computational biology, autonomous exploration, search-and-rescue, and warehouse management. Here, we are given a robot moving in an environment cluttered with obstacles and are required to plan a collision-free path for the robot from a given start to a given goal location.

Nearly forty years ago, early results showed that the general problem is PSPACE-Hard, thus a common approach is to use sampling-based algorithms which study the structure of the search space using stochastic methods. These methods, introduced in the mid 90s enabled solving motion-planning problems that were previously considered infeasible. However, only recently algorithms that provide (asymptotic) guarantees on the quality of the solution were introduced. These algorithms incur substantial overhead when compared to their non-optimal counterparts with respect to their running time / storage requirements.

In this talk I will review prevalent sampling-based motion-planning algorithms and their connection to random geometric graphs. Furthermore I will review a set of tools developed during my Ph.D studies that allow to significantly increase the computational efficiency of high-quality sampling-based algorithms. These tools range from using efficient graph-search algorithm, adapting surface-simplification tools and nearest-neighbor data structures to motion planning and more. The talk will be self contained and will not assume any prior knowledge.

The talk is based on work developed as part of my Ph.D. studies under the supervision of Prof. Dan Halperin. Part of the contributions that will be presented are a result of collaboration with Kiril Solovey, Michal Kleinbort, Doron Shahrabani and Pankaj K. Agarwal.