Doctoral Thesis: Graphs of Convex Sets with Applications to Optimal Control and Motion Planning

By: Tobia Marcucci

Supervisors: Russ Tedrake, Pablo Parrilo

Details

• Date: Monday, April 22
• Time: 2:00 pm - 4:00 pm
• Category: Thesis Defense
• Location: Remotely but 32-G449 to Broadcast

Additional Location Details:

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.