The ability to plan collision-free motions is an important aspect of robots' autonomy: While performing tasks in cluttered environments, the robots need to avoid obstacles as well as fellow robots. The motion-planning problem has been extensively studied over the past four decades. It was primarily investigated as a theoretical problem in computational geometry and has since been the subject of research in robotics as well as computer graphics, computational biology, architectural design, artificial intelligence, and more.
In this talk, I will present results developed during my Ph.D. studies concerning the currently most common type of motion planning algorithms---sampling-based motion planners---and their main building blocks, namely collision detection and nearest-neighbor search. I will discuss the relation between these two components, theoretically and practically, and show that the distribution of work between them defies common belief.
Motion planning can be notoriously challenging when additional constraints are taken into account. For instance, when the robots have differential (kinodynamic) constraints on their motion, specialized planning algorithms, often different from their geometric counterparts, are required.
I will conclude my talk with a novel analysis of one of the commonly-used planners in the presence of differential constraints and describe an extension allowing convergence to high-quality trajectories.
Michal Kleinbort is a Ph.D. candidate at Tel Aviv University working under the supervision of Prof. Dan Halperin in the Computational Geometry Lab.
She holds an M.Sc. in Computer Science from Tel Aviv University.
Her work lies on the border of robotics and computational geometry, focusing on algorithmic motion planning.