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.
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.
|
| 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 |
|
The non-convexity in a GCS problem comes from the binary variables (phi) associated with the edges being active or inactive in the solution.
If those binary variables are fixed, then the problem is convex – this is a so-called "convex restriction" of the original problem.
The convex restriction can often be solved much more efficiently than solving the full GCS problem with additional constraints to fix the binaries; it can be written using less decision variables, and needs only to include the vertices associated with at least one of the active edges. Decision variables for all other convex sets will be set to NaN.
- Exceptions
-
std::exception | if the program cannot be written as a convex optimization consumable by one of the standard solvers. |