GraphOfConvexSets (GCS) implements the design pattern and optimization problems first introduced in the paper "Shortest Paths in Graphs of Convex Sets".
"Shortest Paths in Graphs of Convex Sets" by Tobia Marcucci, Jack Umenberger, Pablo A. Parrilo, Russ Tedrake. https://arxiv.org/abs/2101.11565
- Warning
- This feature is considered to be experimental and may change or be removed at any time, without any deprecation notice ahead of time.
Each vertex in the graph is associated with a convex set over continuous variables, edges in the graph contain convex costs and constraints on these continuous variables. We can then formulate optimization problems over this graph, such as the shortest path problem where each visit to a vertex also corresponds to selecting an element from the convex set subject to the costs and constraints. Behind the scenes, we construct efficient mixed-integer convex transcriptions of the graph problem using MathematicalProgram. However, we provide the option to solve an often tight convex relaxation of the problem with GraphOfConvexSetsOptions::convex_relaxation and employ a cheap rounding stage which solves the convex restriction along potential paths to find a feasible solution to the original problem.
Design note: This class avoids providing any direct access to the MathematicalProgram that it constructs nor to the decision variables / constraints. The users should be able to write constraints against "placeholder" decision variables on the vertices and edges, but these get translated in non-trivial ways to the underlying program.
Advanced Usage: Guiding Non-convex Optimization with the GraphOfConvexSets
Solving a GCS problem using convex relaxation involves two components:
- Convex Relaxation: The relaxation of the binary variables (edge activations) and perspective operations on the convex cost/constraints leads to a convex problem that considers the graph as a whole.
- Rounding: After solving the relaxation, a randomized rounding scheme is applied to obtain a feasible solution for the original problem. We interpret the relaxed flow variables as edge probabilities to guide the maximum likelyhood depth first search from the source to target vertices. Each rounding is calling SolveConvexRestriction.
To handle non-convex constraints, one can provide convex surrogates to the relaxation and the true non-convex constraints to the rounding problem. These surrogates approximate the non-convex constraints, making the relaxation solvable as a convex optimization to guide the non-convex rounding. This can be controlled by the Transcription enum in the AddConstraint method. We encourage users to provide a strong convex surrogate, when possible, to better approximate the original non-convex problem.
|
| GraphOfConvexSets ()=default |
| Constructs an empty graph. More...
|
|
virtual | ~GraphOfConvexSets () |
|
Vertex * | AddVertex (const ConvexSet &set, std::string name="") |
| Adds a vertex to the graph. More...
|
|
Edge * | AddEdge (Vertex *u, Vertex *v, std::string name="") |
| Adds an edge to the graph from Vertex u to Vertex v . More...
|
|
void | RemoveVertex (Vertex *vertex) |
| Removes vertex vertex from the graph as well as any edges from or to the vertex. More...
|
|
void | RemoveEdge (Edge *edge) |
| Removes edge edge from the graph. More...
|
|
std::vector< Vertex * > | Vertices () |
| Returns mutable pointers to the vertices stored in the graph. More...
|
|
std::vector< const Vertex * > | Vertices () const |
| Returns pointers to the vertices stored in the graph. More...
|
|
std::vector< Edge * > | Edges () |
| Returns mutable pointers to the edges stored in the graph. More...
|
|
std::vector< const Edge * > | Edges () const |
| Returns pointers to the edges stored in the graph. More...
|
|
void | ClearAllPhiConstraints () |
| Removes all constraints added to any edge with AddPhiConstraint. More...
|
|
std::string | GetGraphvizString (const std::optional< solvers::MathematicalProgramResult > &result=std::nullopt, bool show_slacks=true, int precision=3, bool scientific=false) const |
| Returns a Graphviz string describing the graph vertices and edges. More...
|
|
solvers::MathematicalProgramResult | SolveShortestPath (const Vertex &source, const Vertex &target, const GraphOfConvexSetsOptions &options=GraphOfConvexSetsOptions()) const |
| Formulates and solves the mixed-integer convex formulation of the shortest path problem on the graph, as discussed in detail in. More...
|
|
std::vector< const Edge * > | GetSolutionPath (const Vertex &source, const Vertex &target, const solvers::MathematicalProgramResult &result, double tolerance=1e-3) const |
| Extracts a path from source to target described by the result returned by SolveShortestPath(), via depth-first search following the largest values of the edge binary variables. More...
|
|
solvers::MathematicalProgramResult | SolveConvexRestriction (const std::vector< const Edge * > &active_edges, const GraphOfConvexSetsOptions &options=GraphOfConvexSetsOptions()) const |
| The non-convexity in a GCS problem comes from the binary variables (phi) associated with the edges being active or inactive in the solution. More...
|
|
|
| GraphOfConvexSets (const GraphOfConvexSets &)=delete |
|
GraphOfConvexSets & | operator= (const GraphOfConvexSets &)=delete |
|
| GraphOfConvexSets (GraphOfConvexSets &&)=delete |
|
GraphOfConvexSets & | operator= (GraphOfConvexSets &&)=delete |
|