Drake
Drake C++ Documentation
GraphOfConvexSets Class Reference

## Detailed Description

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.

#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 ()

VertexAddVertex (const ConvexSet &set, std::string name="")
Adds a vertex to the graph. More...

EdgeAddEdge (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 ()

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...

Does not allow copy, move, or assignment
GraphOfConvexSets (const GraphOfConvexSets &)=delete

GraphOfConvexSetsoperator= (const GraphOfConvexSets &)=delete

GraphOfConvexSets (GraphOfConvexSets &&)=delete

GraphOfConvexSetsoperator= (GraphOfConvexSets &&)=delete

## Friends

class PreprocessShortestPathTest

## ◆ EdgeId

 using EdgeId = Identifier

## ◆ VertexId

 using VertexId = Identifier

## ◆ GraphOfConvexSets() [1/3]

 GraphOfConvexSets ( const GraphOfConvexSets & )
delete

## ◆ GraphOfConvexSets() [2/3]

 GraphOfConvexSets ( GraphOfConvexSets && )
delete

## ◆ GraphOfConvexSets() [3/3]

 GraphOfConvexSets ( )
default

Constructs an empty graph.

## ◆ ~GraphOfConvexSets()

 virtual ~GraphOfConvexSets ( )
virtual

## Member Function Documentation

 Edge* AddEdge ( Vertex * u, Vertex * v, std::string name = "" )

Adds an edge to the graph from Vertex u to Vertex v.

The vertex references must refer to valid vertices in this graph. If name is empty then a default name will be provided.

 Vertex* AddVertex ( const ConvexSet & set, std::string name = "" )

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.

## ◆ ClearAllPhiConstraints()

 void ClearAllPhiConstraints ( )

## ◆ Edges() [1/2]

 std::vector Edges ( )

Returns mutable pointers to the edges stored in the graph.

## ◆ Edges() [2/2]

 std::vector Edges ( ) const

Returns pointers to the edges stored in the graph.

## ◆ GetGraphvizString()

 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.

Parameters
 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).

## ◆ GetSolutionPath()

 std::vector 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.

Parameters
 tolerance defines the threshold for checking the integrality conditions of the binary variables for each edge. tolerance = 0 would demand that the binary variables are exactly 1 for the edges on the path. tolerance = 1 would allow the binary variables to be any value in [0, 1]. The default value is 1e-3.
Exceptions
 std::exception if !result.is_success() or no path from source to target can be found in the solution.

## ◆ operator=() [1/2]

 GraphOfConvexSets& operator= ( GraphOfConvexSets && )
delete

## ◆ operator=() [2/2]

 GraphOfConvexSets& operator= ( const GraphOfConvexSets & )
delete

## ◆ RemoveEdge()

 void RemoveEdge ( Edge * edge )

Removes edge edge from the graph.

Precondition
The edge must be part of the graph.

## ◆ RemoveVertex()

 void RemoveVertex ( 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.

Precondition
The vertex must be part of the graph.

## ◆ SolveConvexRestriction()

 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.

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.

## ◆ SolveShortestPath()

 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.

"Shortest Paths in Graphs of Convex Sets" by Tobia Marcucci, Jack Umenberger, Pablo A. Parrilo, Russ Tedrake. https://arxiv.org/abs/2101.11565

Parameters
 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. The following default options will be used if they are not provided in options: options.convex_relaxation = false, options.max_rounded_paths = 0, options.preprocessing = false.
Exceptions
 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 non-negative for all values of the continuous variables.

## ◆ Vertices() [1/2]

 std::vector Vertices ( )

Returns mutable pointers to the vertices stored in the graph.

## ◆ Vertices() [2/2]

 std::vector Vertices ( ) const

Returns pointers to the vertices stored in the graph.

## ◆ PreprocessShortestPathTest

 friend class PreprocessShortestPathTest
friend

The documentation for this class was generated from the following file: