The RRT class models a Rapidly-Exploring Random Tree see: http://msl.cs.uiuc.edu/~lavalle/papers/Lav98c.pdf The NodeData most frequently will represent the state type modeled. It corresponds to the types of \(x_{rand}\) and \(x_{new}\) from the paper cited above. The EdgeData type corresponds to the type of \(u\) in the paper. It is the input that should subsequently be applied to reach from one state to another and this is what the applications most often will use. More...

#include <rapidly_exploring_random_tree.h>

Inheritance diagram for cengine::search::RRT< NodeData, EdgeData >:

[legend]

Collaboration diagram for cengine::search::RRT< NodeData, EdgeData >:

[legend]

Public Types
typedef NodeData	vertex_data_t
	vertex_data_t The type of node data

typedef EdgeData	edge_data_t
	edge_data_t The type of the edge data

typedef kernel::BoostSerialGraph< vertex_data_t, edge_data_t >::vertex_t	vertex_t
	vertex_t the vertex type

typedef kernel::BoostSerialGraph< vertex_data_t, edge_data_t >::edge_t	edge_t
	edge_t The edge type

typedef kernel::BoostSerialGraph< vertex_data_t, edge_data_t >::edge_iterator	edge_iterator
	edge_iterator Edge iterator

typedef kernel::BoostSerialGraph< vertex_data_t, edge_data_t >::adjacency_iterator	adjacency_iterator
	adjacency_iterator Adjacency iterator

Public Member Functions
	RRT ()
	RRT Default constructor. Creates an empty tree.

vertex_t &	get_vertex (uint_t v)
	get_vertex Returns the v-th vertex

const vertex_t &	get_vertex (uint_t v) const
	get_vertex Returns the v-th vertex

vertex_t &	get_vertex (adjacency_iterator itr)
	Access the vertex given the vertex descriptor This is needed when accessing the vertices using the adjacency_iterator.

const vertex_t &	get_vertex (adjacency_iterator itr) const
	Access the vertex given the vertex descriptor This is needed when accessing the vertices using the adjacency_iterator.

std::pair< adjacency_iterator, adjacency_iterator >	get_vertex_neighbors (uint_t id) const
	Returns the neighboring vertices for the given vertex id.

std::pair< adjacency_iterator, adjacency_iterator >	get_vertex_neighbors (const vertex_t &v) const
	Returns the neighboring vertices for the given vertex id.

vertex_t &	add_vertex (const vertex_t &node)
	add_vertex Add a new vertex to the tree

vertex_t &	add_vertex (const vertex_data_t &data)
	Add a new vertex in the tree that has the given data.

edge_t &	get_edge (uint_t v1, uint_t v2)
	get_edge Returns the edge between the vertices v1 and v2

const edge_t &	get_edge (uint_t v1, uint_t v2) const
	get_edge Returns the edge between the vertices v1 and v2

std::pair< edge_iterator, edge_iterator >	edges () const
	edges Access the edges of the tree

edge_t &	add_edge (uint_t v1, uint_t v2)
	add_edge Add a new edge between the vertices v1 and v2

template<typename MetricTp >
const vertex_t &	find_nearest_neighbor (const vertex_t &other, const MetricTp &metric) const
	find_nearest_neighbor find the nearest neighbor of other node in this tree

template<typename MetricTp >
const vertex_t &	find_nearest_neighbor (const vertex_data_t &other, const MetricTp &metric) const
	find_nearest_neighbor find the nearest neighbor of other node in this tree

void	clear ()
	clear Clear the underlying tree

uint_t	n_vertices () const
	n_vertices. Returns the number of vertices of the tree

uint_t	n_edges () const
	n_edges. Returns the number of edges of the tree

void	set_show_iterations_flag (bool val)
	set_show_iterations_flag Set the show_iterations_ flag

template<typename StateSelector , typename MetricTp , typename DynamicsTp >
void	build (uint_t nitrs, const vertex_t &xinit, const StateSelector &state_selector, const MetricTp &metric, DynamicsTp &dynamics)
	Build the tree.

template<typename StateSelector , typename MetricTp , typename DynamicsTp >
std::tuple< bool, uint_t, uint_t >	build (uint_t nitrs, const vertex_t &xinit, const vertex_t &goal, const StateSelector &state_selector, const MetricTp &metric, DynamicsTp &dynamics, real_t goal_radius)
	Build the tree by using the given goal. The tree expands as long as the specified number of nodes has not been reached or the goal is not found yet. The algorithm terminates when either the number of nodes specified is built or the goal is found.

Detailed Description

template<typename NodeData, typename EdgeData>
class cengine::search::RRT< NodeData, EdgeData >

The RRT class models a Rapidly-Exploring Random Tree see: http://msl.cs.uiuc.edu/~lavalle/papers/Lav98c.pdf The NodeData most frequently will represent the state type modeled. It corresponds to the types of \(x_{rand}\) and \(x_{new}\) from the paper cited above. The EdgeData type corresponds to the type of \(u\) in the paper. It is the input that should subsequently be applied to reach from one state to another and this is what the applications most often will use.

Member Typedef Documentation

◆ adjacency_iterator

template<typename NodeData , typename EdgeData >

typedef kernel::BoostSerialGraph<vertex_data_t,edge_data_t>::adjacency_iterator cengine::search::RRT< NodeData, EdgeData >::adjacency_iterator

adjacency_iterator Adjacency iterator

◆ edge_data_t

template<typename NodeData , typename EdgeData >

typedef EdgeData cengine::search::RRT< NodeData, EdgeData >::edge_data_t

edge_data_t The type of the edge data

◆ edge_iterator

template<typename NodeData , typename EdgeData >

typedef kernel::BoostSerialGraph<vertex_data_t,edge_data_t>::edge_iterator cengine::search::RRT< NodeData, EdgeData >::edge_iterator

edge_iterator Edge iterator

◆ edge_t

template<typename NodeData , typename EdgeData >

typedef kernel::BoostSerialGraph<vertex_data_t,edge_data_t>::edge_t cengine::search::RRT< NodeData, EdgeData >::edge_t

edge_t The edge type

◆ vertex_data_t

template<typename NodeData , typename EdgeData >

typedef NodeData cengine::search::RRT< NodeData, EdgeData >::vertex_data_t

vertex_data_t The type of node data

◆ vertex_t

template<typename NodeData , typename EdgeData >

typedef kernel::BoostSerialGraph<vertex_data_t,edge_data_t>::vertex_t cengine::search::RRT< NodeData, EdgeData >::vertex_t

vertex_t the vertex type

Constructor & Destructor Documentation

◆ RRT()

template<typename NodeData , typename EdgeData >

cengine::search::RRT< NodeData, EdgeData >::RRT ( )

RRT Default constructor. Creates an empty tree.

Member Function Documentation

◆ add_edge()

template<typename NodeData , typename EdgeData >

edge_t & cengine::search::RRT< NodeData, EdgeData >::add_edge	(	uint_t	v1,
		uint_t	v2
	)

inline

add_edge Add a new edge between the vertices v1 and v2

Parameters

v1	Vertex 1
v2	Vertex 2

◆ add_vertex() [1/2]

template<typename NodeData , typename EdgeData >

RRT< NodeData, EdgeData >::vertex_t & cengine::search::RRT< NodeData, EdgeData >::add_vertex ( const vertex_data_t & data )

Add a new vertex in the tree that has the given data.

◆ add_vertex() [2/2]

template<typename NodeData , typename EdgeData >

vertex_t & cengine::search::RRT< NodeData, EdgeData >::add_vertex ( const vertex_t & node )

inline

add_vertex Add a new vertex to the tree

Parameters

node	The new vertex to add

◆ build() [1/2]

template<typename NodeTp , typename EdgeTp >

template<typename StateSelector , typename MetricTp , typename DynamicsTp >

void cengine::search::RRT< NodeTp, EdgeTp >::build	(	uint_t	nitrs,
		const vertex_t &	xinit,
		const StateSelector &	state_selector,
		const MetricTp &	metric,
		DynamicsTp &	dynamics
	)

Build the tree.

◆ build() [2/2]

template<typename NodeData , typename EdgeData >

template<typename StateSelector , typename MetricTp , typename DynamicsTp >

std::tuple< bool, uint_t, uint_t > cengine::search::RRT< NodeData, EdgeData >::build	(	uint_t	nitrs,
		const vertex_t &	xinit,
		const vertex_t &	goal,
		const StateSelector &	state_selector,
		const MetricTp &	metric,
		DynamicsTp &	dynamics,
		real_t	goal_radius
	)

Build the tree by using the given goal. The tree expands as long as the specified number of nodes has not been reached or the goal is not found yet. The algorithm terminates when either the number of nodes specified is built or the goal is found.

◆ clear()

template<typename NodeData , typename EdgeData >

void cengine::search::RRT< NodeData, EdgeData >::clear ( )

inline

clear Clear the underlying tree

◆ edges()

template<typename NodeData , typename EdgeData >

std::pair< edge_iterator, edge_iterator > cengine::search::RRT< NodeData, EdgeData >::edges ( ) const

inline

edges Access the edges of the tree

◆ find_nearest_neighbor() [1/2]

template<typename NodeData , typename EdgeData >

template<typename MetricTp >

const RRT< NodeData, EdgeData >::vertex_t & cengine::search::RRT< NodeData, EdgeData >::find_nearest_neighbor	(	const vertex_data_t &	other,
		const MetricTp &	metric
	)		const

find_nearest_neighbor find the nearest neighbor of other node in this tree

Parameters

other The node for which to find the nearest neighbor

Returns

◆ find_nearest_neighbor() [2/2]

template<typename NodeData , typename EdgeData >

template<typename MetricTp >

const RRT< NodeData, EdgeData >::vertex_t & cengine::search::RRT< NodeData, EdgeData >::find_nearest_neighbor	(	const vertex_t &	other,
		const MetricTp &	metric
	)		const

find_nearest_neighbor find the nearest neighbor of other node in this tree

Parameters

other The node for which to find the nearest neighbor

Returns

◆ get_edge() [1/2]

template<typename NodeData , typename EdgeData >

edge_t & cengine::search::RRT< NodeData, EdgeData >::get_edge	(	uint_t	v1,
		uint_t	v2
	)

inline

get_edge Returns the edge between the vertices v1 and v2

Parameters

v1	Vertex 1
v2	Vertex 2

◆ get_edge() [2/2]

template<typename NodeData , typename EdgeData >

const edge_t & cengine::search::RRT< NodeData, EdgeData >::get_edge	(	uint_t	v1,
		uint_t	v2
	)		const

inline

get_edge Returns the edge between the vertices v1 and v2

Parameters

v1	Vertex 1
v2	Vertex 2

◆ get_vertex() [1/4]

template<typename NodeData , typename EdgeData >

vertex_t & cengine::search::RRT< NodeData, EdgeData >::get_vertex ( adjacency_iterator itr )

inline

Access the vertex given the vertex descriptor This is needed when accessing the vertices using the adjacency_iterator.

◆ get_vertex() [2/4]

template<typename NodeData , typename EdgeData >

const vertex_t & cengine::search::RRT< NodeData, EdgeData >::get_vertex ( adjacency_iterator itr ) const

inline

Access the vertex given the vertex descriptor This is needed when accessing the vertices using the adjacency_iterator.

◆ get_vertex() [3/4]

template<typename NodeData , typename EdgeData >

vertex_t & cengine::search::RRT< NodeData, EdgeData >::get_vertex ( uint_t v )

inline

get_vertex Returns the v-th vertex

◆ get_vertex() [4/4]

template<typename NodeData , typename EdgeData >

const vertex_t & cengine::search::RRT< NodeData, EdgeData >::get_vertex ( uint_t v ) const

inline

get_vertex Returns the v-th vertex

◆ get_vertex_neighbors() [1/2]

template<typename NodeData , typename EdgeData >

std::pair< adjacency_iterator, adjacency_iterator > cengine::search::RRT< NodeData, EdgeData >::get_vertex_neighbors ( const vertex_t & v ) const

inline

Returns the neighboring vertices for the given vertex id.

◆ get_vertex_neighbors() [2/2]

template<typename NodeData , typename EdgeData >

std::pair< adjacency_iterator, adjacency_iterator > cengine::search::RRT< NodeData, EdgeData >::get_vertex_neighbors ( uint_t id ) const

inline

Returns the neighboring vertices for the given vertex id.

◆ n_edges()

template<typename NodeData , typename EdgeData >

uint_t cengine::search::RRT< NodeData, EdgeData >::n_edges ( ) const

inline

n_edges. Returns the number of edges of the tree

Returns

◆ n_vertices()

template<typename NodeData , typename EdgeData >

uint_t cengine::search::RRT< NodeData, EdgeData >::n_vertices ( ) const

inline

n_vertices. Returns the number of vertices of the tree

Returns

◆ set_show_iterations_flag()

template<typename NodeData , typename EdgeData >

void cengine::search::RRT< NodeData, EdgeData >::set_show_iterations_flag ( bool val )

inline

set_show_iterations_flag Set the show_iterations_ flag

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

libs/bitrl/src/bitrl/planning/rapidly_exploring_random_tree.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ adjacency_iterator

◆ edge_data_t

◆ edge_iterator

◆ edge_t

◆ vertex_data_t

◆ vertex_t

Constructor & Destructor Documentation

◆ RRT()

Member Function Documentation

◆ add_edge()

◆ add_vertex() [1/2]

◆ add_vertex() [2/2]

◆ build() [1/2]

◆ build() [2/2]

◆ clear()

◆ edges()

◆ find_nearest_neighbor() [1/2]

◆ find_nearest_neighbor() [2/2]

◆ get_edge() [1/2]

◆ get_edge() [2/2]

◆ get_vertex() [1/4]

◆ get_vertex() [2/4]

◆ get_vertex() [3/4]

◆ get_vertex() [4/4]

◆ get_vertex_neighbors() [1/2]

◆ get_vertex_neighbors() [2/2]

◆ n_edges()

◆ n_vertices()

◆ set_show_iterations_flag()