GraphOfConvexSets Class Reference

Detailed Description

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

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 ()
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 mixed-integer 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

Member Typedef Documentation

EdgeId

using EdgeId = Identifier<class EdgeTag>

VertexId

using VertexId = Identifier<class VertexTag>

Constructor & Destructor Documentation

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

AddEdge() [1/2]

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.

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

AddEdge() [2/2]

Edge* AddEdge	(	const Vertex &	u,
		const 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.

AddVertex()

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

(

)

Removes all constraints added to any edge with AddPhiConstraint.

Edges() [1/2]

std::vector<Edge*> Edges

(

)

Returns mutable pointers to the edges stored in the graph.

Edges() [2/2]

std::vector<const Edge*> 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).

operator=() [1/2]

GraphOfConvexSets& operator= ( GraphOfConvexSets &&  )

delete

operator=() [2/2]

GraphOfConvexSets& operator= ( const GraphOfConvexSets &  )

delete

RemoveEdge() [1/2]

void RemoveEdge

(

EdgeId

edge_id

)

Removes edge edge_id from the graph.

Precondition

The edge must be part of the graph.

RemoveEdge() [2/2]

void RemoveEdge

(

const Edge &

edge

)

Removes edge edge from the graph.

Precondition

The edge must be part of the graph.

RemoveVertex() [1/2]

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.

Precondition

The vertex must be part of the graph.

RemoveVertex() [2/2]

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.

Precondition

The vertex must be part of the graph.

SolveShortestPath() [1/2]

solvers::MathematicalProgramResult SolveShortestPath	(	VertexId	source_id,
		VertexId	target_id,
		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.

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.

SolveShortestPath() [2/2]

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.

Vertices() [1/2]

std::vector<Vertex*> Vertices

(

)

Returns mutable pointers to the vertices stored in the graph.

Vertices() [2/2]

std::vector<const Vertex*> Vertices

(

)

const

Returns pointers to the vertices stored in the graph.

Friends And Related Function Documentation

PreprocessShortestPathTest

friend class PreprocessShortestPathTest

friend

---

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

• drake/geometry/optimization/graph_of_convex_sets.h