THESIS DEFENSE: Graphs of Convex Sets with Applications to Optimal Control and Motion Planning

Location: https://mit.zoom.us/j/92105752330 (streamed in 32-G449, Patil/Kiva).

Zoom meeting password: 462319

Committee Members:
Russ Tedrake (Advisor)
Pablo Parrilo (Advisor)
Manfred Morari
Sertac Karaman

Abstract: This thesis introduces a new class of problems at the interface of combinatorial and convex optimization. We consider graphs where each vertex is paired with a convex program, and each edge couples two programs through additional convex costs and constraints. We call such a graph a Graph of Convex Sets (GCS). Over a GCS we can formulate any optimization problem that we can formulate over an ordinary weighted graph, with scalar costs on the vertices and edges. In fact, for any fixed choice of the variables in the convex programs, a GCS reduces to a weighted graph where we can seek, e.g., a path, a matching, a tour, or a spanning tree of minimum cost. The challenge in a GCS problem lies in solving the discrete and the continuous components of the problem jointly.

By combining the modelling power of graphs and convex optimization, GCSs are a flexible framework to formulate and solve many real-world problems. The graph and the combinatorial goal (e.g., finding a path or a tour) model the high-level discrete skeleton of a problem. The convex costs and constraints fill in the low-level continuous details. The primary contribution of this thesis is an efficient and unified method for solving any GCS problem. Starting from an integer-linear-programming formulation of an optimization problem over a weighted graph, this method formulates the corresponding GCS problem as an efficient Mixed-Integer Convex Program (MICP). This MICP can then be solved to global optimality using common branch-and-bound solvers, or approximately by rounding the solution of its convex relaxation. Importantly, both the formulation of the MICP and its solution are fully automatic, and a user of our framework does not need any expertise in mixed-integer optimization.

We first describe the GCS framework and the formulation of our MICP in general terms, without presupposing the specific combinatorial problem to be solved over the GCS. We illustrate our techniques through multiple examples spanning logistics, transportation, scheduling, navigation, and computational geometry. Then we focus on the Shortest-Path Problem (SPP) in GCS. This problem is particularly interesting since it generalizes a wide variety of multi-stage decision-making problems and, using our techniques, it can be solved very effectively. We consider two main applications of the SPP in GCS: optimal control of dynamical systems and collision-free motion planning. In these two areas, our techniques either generalize or significantly improve upon algorithms and optimization methods that have been developed for decades and are widely used in academia and industry.

Bio: Tobia Marcucci is a sixth-year PhD student at the Massachusetts Institute of Technology (MIT), Computer Science and Artificial Intelligence Laboratory (CSAIL), under the supervision of Russ Tedrake and Pablo Parrilo. During his PhD, Tobia has also spent one year at Stanford University as a graduate visiting researcher in Stephen Boyd’s group. Before MIT, Tobia was at the University of Pisa, where he graduated cum laude in mechanical engineering and where he started a PhD in robotics at the Research Center E. Piaggio and the Istituto Italiano di Tecnologia (IIT). His research lies at the intersection of convex and combinatorial optimization, with applications to robotics, motion planning, and optimal control.

For more information, please contact Mieke Moran (mieke@csail.mit.edu)