VEGA: Decomposition Solver for Graphs of Convex Sets
Representative GCS benchmark instance families spanning maze, helicopter, shelf, contact-graph, SDP pushing, and bimanual problems.Motivation
Graph of Convex Sets (GCS) is a powerful modeling framework for planning problems that combine discrete choices with continuous decisions. A path through the graph selects a sequence of convex regions or modes, while the optimization variables choose continuous states inside those regions.
This makes GCS a natural fit for robotics problems such as motion planning through convex regions, manipulation with contact modes, and mixed discrete-continuous task planning. The challenge is scale. A centralized relaxation can become very large, and the graph structure that made the model natural is no longer fully exploited by a generic conic solve.
Contribution
VEGA is a decomposition solver for GCS programs written in C++. Instead of solving the full conic relaxation as one monolithic program, the method splits the problem into the pieces already present in the model: a local program at each vertex, a local program at each edge, and a global graph optimization update.
At each iteration, these subproblems can be solved in parallel and then driven toward consensus. This creates a solver architecture that matches the original modeling structure and can scale to very large problems.
In addition to VEGA, we provide a benchmark of GCS instances from the literature and distribute these instances as GcsBench. We provide new C++ and Python based infrastructure in GcsCpp for modelling, serializing, and deserializing instances so that other researchers can contribute their own instances to the benchmark. We also provide bridges to transform Drake's GraphOfConvexSets objects and gcsopt models to the standardized GcsCpp instances.
The benchmark set includes maze navigation, helicopter flight, shelf planning, bimanual manipulation, semidefinite pushing, and contact-graph instances. These programs take anywhere from less than a second to tens of minutes to solve with general-purpose convex solvers. The contact-graph instances are too large to be solved in a reasonable time by general-purpose methods.
Results
VEGA is designed to solve GCS instances where the convex relaxation is too large to solve using a general-purpose, centralized solver.
It is the only solver in the benchmark capable of solving any of the contact-graph instances. On problems where centralized solvers do succeed, VEGA is typically slower as the additional overhead of coordinating the local solvers outweighs any benefits from using the decomposition-based method.
I am a final-year PhD candidate at MIT, advised by Pablo Parrilo and Russ Tedrake, working at the intersection of mathematical optimization, robotics, and reliable autonomy. My research develops scalable algorithms for high-performance decision-making, particularly in robotics.
I am interested in the entire decision-making pipeline, from high-level modeling, high-performance solver implementations, and low-level linear algebra to enable faster optimal decisions. I specialize in semidefinite programming and sums-of-squares optimization and development of convex optimization solvers. A central theme in my work is turning mathematical structure into computation. I build algorithms that exploit polynomial, conic, and graph structure to make difficult problems tractable, and am committed to distributing robust, open-source implementations of my methods.
I wrote CCosmo, a C++ first-order conic solver family, and VEGA, a decomposition solver for Graphs of Convex Sets. I am also an active contributor to Drake’s optimization, geometry, and planning stack. I am interested in industrial research roles where rigorous optimization, scalable algorithms, and high-quality software can push the frontier of AI, robotics, autonomy, and scientific computing.