SCS Faculty Candidate Sertac Karaman
Thursday, March 1st
1:00 p.m. GHC 6115
Host: Matthew Mason

*Anytime Sampling-based Algorithms
                      and Fundamental Limits
                           for Motion Control*

*Abstract:*

Sampling-based algorithms, such as the Rapidly-exploring Random Trees (RRTs)
and the Probabilistic RoadMaps (PRMs), are widely used in robot motion
planning. In the first part of the talk, we prove a number of results on
sampling-based algorithms. First, we show that the RRT algorithm is not
asymptotically optimal, i.e., it fails to convergence to optimal
trajectories, almost surely. Moreover, we show that all existing variants of
PRMs lack either asymptotic optimality or computational efficiency. Second,
we propose two novel algorithms, called the RRT* and the PRM*, which are
asymptotically optimal. Furthermore, their asymptotic computational
complexity is no more than that of the RRT or any existing PRM variant .
Third, we extend the application domain of sampling-based algorithms in a
number of novel directions including differential games, stochastic optimal
control, and planning with complex task specifications.

In the second part of the talk, inspired by hawks flying through dense
forests at high speeds, we study the fundamental limits of high-speed motion
through a randomly-generated obstacle field that resembles a planar forest
environment. We show that, when the forest generation process is ergodic,
the existence of infinite collision-free trajectories through the forest
exhibits a phase transition. That is, there exists a critical speed such
that collision-free flight can not be maintained indefinitely at any
super-critical speed, with probability one, although there exists an
infinite collision-free trajectory at any sub-critical speed, almost surely.

In both parts of the talk, we establish novel connections between robot
motion planning and mathematical tools of statistical physics, such as
percolation theory and random graphs, which may be of independent interest.

*Speaker: *

Sertac Karaman

Laboratory for Information and Decision Systems,

Massachusetts Institute of Technology, Cambridge, MA.

*Speaker Bio:*

Sertac Karaman holds B.S. degrees in Mechanical Engineering and in Computer
Engineering both from Istanbul Technical University and an S.M. degree in
Mechanical Engineering from Massachusetts Institute of Technology (MIT).
Currently, he is a Ph.D. candidate in the Department of Electrical
Engineering and Computer Science at MIT. His main research interests include
motion planning, control theory, embedded systems, autonomous vehicles,
agile robotic vehicles as well as applications of stochastic geometry and
statistical physics in the context of robotics. He is the recipient of the
AIAA Wright Brothers Graduate award in 2011, the NVIDIA Graduate Fellowship
in 2011, and the Willow Garage Best Open-source Code Award (with Emilio
Frazzoli) in 2010.