GraphOfConvexSets 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
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 mixedinteger 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 nontrivial ways to the underlying program.
#include <drake/geometry/optimization/graph_of_convex_sets.h>
Classes  
class  Edge 
An edge in the graph connects between vertex u and vertex v . More...  
class  Vertex 
Each vertex in the graph has a corresponding ConvexSet, and a std::string name. More...  
Public Types  
using  VertexId = Identifier< class VertexTag > 
using  EdgeId = Identifier< class EdgeTag > 
Public Member Functions  
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 (VertexId u_id, VertexId v_id, std::string name="") 
Adds an edge to the graph from VertexId u_id to VertexId v_id . More...  
Edge *  AddEdge (const Vertex &u, const Vertex &v, std::string name="") 
Adds an edge to the graph from Vertex u to Vertex v . More...  
void  RemoveVertex (VertexId vertex_id) 
Removes vertex vertex_id from the graph as well as any edges from or to the vertex. More...  
void  RemoveVertex (const Vertex &vertex) 
Removes vertex vertex from the graph as well as any edges from or to the vertex. More...  
void  RemoveEdge (EdgeId edge_id) 
Removes edge edge_id from the graph. More...  
void  RemoveEdge (const 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 (VertexId source_id, VertexId target_id, const GraphOfConvexSetsOptions &options=GraphOfConvexSetsOptions()) const 
Formulates and solves the mixedinteger convex formulation of the shortest path problem on the graph, as discussed in detail in. More...  
solvers::MathematicalProgramResult  SolveShortestPath (const Vertex &source, const Vertex &target, const GraphOfConvexSetsOptions &options=GraphOfConvexSetsOptions()) const 
Convenience overload that takes const reference arguments for source and target. More...  
Does not allow copy, move, or assignment  
GraphOfConvexSets (const GraphOfConvexSets &)=delete  
GraphOfConvexSets &  operator= (const GraphOfConvexSets &)=delete 
GraphOfConvexSets (GraphOfConvexSets &&)=delete  
GraphOfConvexSets &  operator= (GraphOfConvexSets &&)=delete 
Friends  
class  PreprocessShortestPathTest 
using EdgeId = Identifier<class EdgeTag> 
using VertexId = Identifier<class VertexTag> 

delete 

delete 

default 
Constructs an empty graph.

virtual 
Adds an edge to the graph from VertexId u_id
to VertexId v_id
.
The ids must refer to valid vertices in this graph. If name
is empty then a default name will be provided.
Adds a vertex to the graph.
A copy of set
is cloned and stored inside the graph. If name
is empty then a default name will be provided.
void ClearAllPhiConstraints  (  ) 
Removes all constraints added to any edge with AddPhiConstraint.
std::vector<Edge*> Edges  (  ) 
Returns mutable pointers to the edges stored in the graph.
std::vector<const Edge*> Edges  (  )  const 
Returns pointers to the edges stored in the graph.
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.
If results
is supplied, then the graph will be annotated with the solution values.
show_slacks  determines whether the values of the intermediate (slack) variables are also displayed in the graph. 
precision  sets the floating point precision (how many digits are generated) of the annotations. 
scientific  sets the floating point formatting to scientific (if true) or fixed (if false). 

delete 

delete 
void RemoveEdge  (  EdgeId  edge_id  ) 
Removes edge edge_id
from the graph.
void RemoveEdge  (  const Edge &  edge  ) 
Removes edge edge
from the graph.
void RemoveVertex  (  VertexId  vertex_id  ) 
Removes vertex vertex_id
from the graph as well as any edges from or to the vertex.
Runtime is O(nₑ) where nₑ is the number of edges in the graph.
void RemoveVertex  (  const Vertex &  vertex  ) 
Removes vertex vertex
from the graph as well as any edges from or to the vertex.
Runtime is O(nₑ) where nₑ is the number of edges in the graph.
solvers::MathematicalProgramResult SolveShortestPath  (  VertexId  source_id, 
VertexId  target_id,  
const GraphOfConvexSetsOptions &  options = GraphOfConvexSetsOptions() 

)  const 
Formulates and solves the mixedinteger convex formulation of the shortest path problem on the graph, as discussed in detail in.
"Shortest Paths in Graphs of Convex Sets" by Tobia Marcucci, Jack Umenberger, Pablo A. Parrilo, Russ Tedrake. https://arxiv.org/abs/2101.11565
source  specifies the source set. The solver will choose any point in that set; to start at a particular continuous state consider adding a Point set to the graph and using that as the source. 
target  specifies the target set. The solver will choose any point in that set. 
options  include all settings for solving the shortest path problem. See GraphOfConvexSetsOptions for further details. 
std::exception  if any of the costs or constraints in the graph are incompatible with the shortest path formulation or otherwise unsupported. All costs must be nonnegative for all values of the continuous variables. 
solvers::MathematicalProgramResult SolveShortestPath  (  const Vertex &  source, 
const Vertex &  target,  
const GraphOfConvexSetsOptions &  options = GraphOfConvexSetsOptions() 

)  const 
Convenience overload that takes const reference arguments for source and target.
std::vector<Vertex*> Vertices  (  ) 
Returns mutable pointers to the vertices stored in the graph.
std::vector<const Vertex*> Vertices  (  )  const 
Returns pointers to the vertices stored in the graph.

friend 