Linear Algebra and Optimization Seminar - Tobia Marcucci

Linear Algebra and Optimization Seminar

Title: Shortest Paths in Graphs of Convex Sets
Speaker: Tobia Marcucci, MIT
Date: January 18
Time: 4:30 PM - 5:20 PM
Location: Green Earth Sciences Building, Room 150

Given a graph, the shortest-path problem requires finding a sequence
of edges of minimum cost that connects a source vertex to a target
vertex.  We consider a variant of this classical problem in which:
  i) the position of each vertex in the graph is a continuous decision
     variable, constrained in a convex set,
 ii) the length of an edge is a convex function of the position of its
Problems of this form arise naturally in many areas, including optimal
control, autonomous navigation, and scheduling.  The price for such
wide applicability is the complexity of this problem, which is easily
seen to be NP-hard.  I will present a lightweight mixed-integer
formulation of the problem at hand.  This formulation has a very tight
convex relaxation and makes it possible to efficiently find
globally-optimal paths in large graphs and in high-dimensional spaces.
I will also discuss applications in robotics, and show how the proposed
optimization framework can outperform motion-planning algorithms that
have been optimized for decades and are widely used in industry.

Tobia Marcucci graduated cum laude in mechanical engineering from the
University of Pisa in 2015.  From 2015 to 2017 he was a PhD student in
robotics at the Research Center E. Piaggio, University of Pisa, and
the Istituto Italiano di Tecnologia.  In 2017 he moved to the Computer
Science and Artificial Intelligence Laboratory, Massachusetts
Institute of Technology, to continue his PhD studies under the
supervision of Russ Tedrake and Pablo Parrilo.  Currently, he is
visiting Stephen Boyd's group at Stanford University for a period of
nine months.  His research lies at the intersection of convex and
combinatorial optimization, with applications to robotics and control.

Wednesday, January 25, 2023 - 4:30pm to 5:20pm