Loading Events

RI Seminar


Russ Tedrake Professor Electrical Engineering & Computer Science, MIT
Friday, January 27
3:30 pm to 4:30 pm
1305 Newell Simon Hall
Motion Planning Around Obstacles with Graphs of Convex Sets

In this talk, I’ll describe a new approach to planning that strongly leverages both continuous and discrete/combinatorial optimization. The framework is fairly general, but I will focus on a particular application of the framework to planning continuous curves around obstacles. Traditionally, these sort of motion planning problems have either been solved by trajectory optimization approaches, which suffer with local minima in the presence of obstacles, or by sampling-based motion planning algorithms, which can struggle with derivative constraints and sample-complexity in very high dimensions. In the proposed framework, called Graphs of Convex Sets (GCS), we can recast the trajectory optimization problem over a parametric class of continuous curves into a problem combining convex optimization formulations for graph search and for motion planning.

The result is a non-convex optimization problem whose convex relaxation is very tight — to the point that we can very often solve very complex motion planning problems to global optimality using the convex relaxation plus a cheap rounding strategy. I will describe numerical experiments of GCS applied to a quadrotor flying through buildings and robotic arms moving through confined spaces. On a seven-degree-of-freedom manipulator, GCS can outperform widely-used sampling-based planners by finding higher-quality trajectories in less time, and in 14 dimensions (or more) it can solve problems to global optimality which are hard to approach with sampling-based techniques. Finally, I’ll discuss new extensions using GCS for planning on manifolds and task and motion planning.

Brief Bio: Professor Tedrake is the Toyota Professor of Electrical Engineering and Computer Science, Aeronautics and Astronautics and Mechanical Engineering at MIT, the Director of the Center for Robotics at the Computer Vision and Artificial Intelligence Lab and leader of the MIT’s entry in the DARPA Robotics Challenge. Russ is also the Vice President of Robotics Research at the Toyota Research Institute. He is a recipient of the 2021 Jamieson Teaching Award, the NSF CAREER Award, the MIT Jerome Saltzer Award for undergraduate teaching, the DARPA Young Faculty Award in Mathematics, the 2012 Ruth and Joel Spira Teaching Award, and was named a Microsoft Research New Faculty Fellow.

Professor Tedrake’s research is focused on finding elegant control solutions for interesting (underactuated, stochastic, and/or difficult to model) dynamical systems that he can build and experiment with. He is  particularly interested in finding connections between mechanics (especially non-smooth mechanics) and machine learning/optimization theory which enable robust control design for complex mechanical systems. These days he is primarily focused in merging more of the powerful tools from systems theory with machine learning for robotic manipulation.

Professor Tedrake received his B.S.E. in Computer Engineering from the University of Michigan, Ann Arbor, in 1999, and his Ph.D. in Electrical Engineering and Computer Science from MIT in 2004, working with Sebastian Seung. After graduation, he joined the MIT Brain and Cognitive Sciences Department as a Postdoctoral Associate. During his education, he has also spent time at Microsoft, Microsoft Research, and the Santa Fe Institute.