Detailed Description

template<class NODE_TYPE_DATA, class EDGE_TYPE, class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>
class mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >

This class contains motions and motions tree structures for the hybrid navigation algorithm.

Usage:

Note

: this class inheredit mrpt::graphs::CDirectedTree, please refer to inheritance for detail about generic tree methods

 - initialize a motions tree using .initializeMoveTree()
 - addEdge (from, to)
 - add here more instructions

Changes history

06/MAR/2014: Creation (MB)
21/JAN/2015: Refactoring (JLBC)

Definition at line 50 of file TMoveTree.h.

#include <mrpt/nav/planners/TMoveTree.h>

Inheritance diagram for mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >:

Classes
struct	node_t

Public Types
using	base_t = mrpt::graphs::CDirectedTree< EDGE_TYPE >

using	edge_t = EDGE_TYPE

using	node_map_t = typename MAPS_IMPLEMENTATION::template map< mrpt::graphs::TNodeID, node_t >
	Map: TNode_ID => Node info. More...

using	path_t = std::list< node_t >
	A topological path up-tree. More...

using	TListEdges = std::list< TEdgeInfo >

using	TMapNode2ListEdges = std::map< TNodeID, TListEdges >

Public Member Functions
template<class NODE_TYPE_FOR_METRIC >
mrpt::graphs::TNodeID	getNearestNode (const NODE_TYPE_FOR_METRIC &query_pt, const PoseDistanceMetric< NODE_TYPE_FOR_METRIC > &distanceMetricEvaluator, double out_distance=nullptr, const std::set< mrpt::graphs::TNodeID > ignored_nodes=nullptr) const
	Finds the nearest node to a given pose, using the given metric. More...

void	insertNodeAndEdge (const mrpt::graphs::TNodeID parent_id, const mrpt::graphs::TNodeID new_child_id, const NODE_TYPE_DATA &new_child_node_data, const EDGE_TYPE &new_edge_data)

void	insertNode (const mrpt::graphs::TNodeID node_id, const NODE_TYPE_DATA &node_data)
	Insert a node without edges (should be used only for a tree root node) More...

mrpt::graphs::TNodeID	getNextFreeNodeID () const

const node_map_t &	getAllNodes () const

void	backtrackPath (const mrpt::graphs::TNodeID target_node, path_t &out_path) const
	Builds the path (sequence of nodes, with info about next edge) up-tree from a `target_node` towards the root Nodes are ordered in the direction ROOT -> start_node. More...

Utilities
void	clear ()
	Empty all edge data and set "root" to INVALID_NODEID. More...

void	visitDepthFirst (const TNodeID vroot, Visitor &user_visitor, const size_t root_depth_level=0) const
	Depth-first visit of all children nodes of a given root (itself excluded from the visit), invoking a user-provided function for each node/edge. More...

void	visitBreadthFirst (const TNodeID vroot, Visitor &user_visitor, const size_t root_depth_level=0) const
	Breadth-first visit of all children nodes of a given root (itself excluded from the visit), invoking a user-provided function for each node/edge. More...

std::string	getAsTextDescription () const
	Return a text representation of the tree spanned in a depth-first view, as in this example: More...

Public Attributes
Data
TNodeID	root
	The root of the tree. More...

TMapNode2ListEdges	edges_to_children
	The edges of each node. More...

Private Attributes
node_map_t	m_nodes
	Info per node. More...

Member Typedef Documentation

◆ base_t

template<class NODE_TYPE_DATA , class EDGE_TYPE , class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>

using mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::base_t = mrpt::graphs::CDirectedTree<EDGE_TYPE>

Definition at line 74 of file TMoveTree.h.

◆ edge_t

template<class NODE_TYPE_DATA , class EDGE_TYPE , class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>

using mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::edge_t = EDGE_TYPE

Definition at line 75 of file TMoveTree.h.

◆ node_map_t

template<class NODE_TYPE_DATA , class EDGE_TYPE , class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>

using mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::node_map_t = typename MAPS_IMPLEMENTATION::template map< mrpt::graphs::TNodeID, node_t>

Map: TNode_ID => Node info.

Definition at line 78 of file TMoveTree.h.

◆ path_t

template<class NODE_TYPE_DATA , class EDGE_TYPE , class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>

using mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::path_t = std::list<node_t>

A topological path up-tree.

Definition at line 80 of file TMoveTree.h.

◆ TListEdges

using mrpt::graphs::CDirectedTree< EDGE_TYPE >::TListEdges = std::list<TEdgeInfo>

inherited

Definition at line 73 of file CDirectedTree.h.

◆ TMapNode2ListEdges

using mrpt::graphs::CDirectedTree< EDGE_TYPE >::TMapNode2ListEdges = std::map<TNodeID, TListEdges>

inherited

Definition at line 74 of file CDirectedTree.h.

Member Function Documentation

◆ backtrackPath()

template<class NODE_TYPE_DATA , class EDGE_TYPE , class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>

void mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::backtrackPath	(	const mrpt::graphs::TNodeID	target_node,
		path_t &	out_path
	)		const

inline

Builds the path (sequence of nodes, with info about next edge) up-tree from a target_node towards the root Nodes are ordered in the direction ROOT -> start_node.

Definition at line 145 of file TMoveTree.h.

References INVALID_NODEID, mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::m_nodes, and mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::node_t::parent_id.

Referenced by mrpt::nav::PlannerRRT_SE2_TPS::solve().

Here is the caller graph for this function:

◆ clear()

void mrpt::graphs::CDirectedTree< EDGE_TYPE >::clear ( )

inlineinherited

Empty all edge data and set "root" to INVALID_NODEID.

Definition at line 88 of file CDirectedTree.h.

References mrpt::graphs::CDirectedTree< TYPE_EDGES >::edges_to_children, INVALID_NODEID, and mrpt::graphs::CDirectedTree< TYPE_EDGES >::root.

◆ getAllNodes()

template<class NODE_TYPE_DATA , class EDGE_TYPE , class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>

const node_map_t& mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::getAllNodes ( ) const

inline

Definition at line 140 of file TMoveTree.h.

References mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::m_nodes.

Referenced by mrpt::nav::PlannerRRT_SE2_TPS::solve().

Here is the caller graph for this function:

◆ getAsTextDescription()

std::string mrpt::graphs::CDirectedTree< EDGE_TYPE >::getAsTextDescription ( ) const

inlineinherited

Return a text representation of the tree spanned in a depth-first view, as in this example:

0
 -> 1
 -> 2
     -> 4
     -> 5
 -> 3

Definition at line 166 of file CDirectedTree.h.

References mrpt::graphs::CDirectedTree< TYPE_EDGES >::root, and mrpt::graphs::CDirectedTree< TYPE_EDGES >::visitDepthFirst().

◆ getNearestNode()

template<class NODE_TYPE_DATA , class EDGE_TYPE , class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>

template<class NODE_TYPE_FOR_METRIC >

mrpt::graphs::TNodeID mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::getNearestNode	(	const NODE_TYPE_FOR_METRIC &	query_pt,
		const PoseDistanceMetric< NODE_TYPE_FOR_METRIC > &	distanceMetricEvaluator,
		double *	out_distance = `nullptr`,
		const std::set< mrpt::graphs::TNodeID > *	ignored_nodes = `nullptr`
	)		const

inline

Finds the nearest node to a given pose, using the given metric.

Definition at line 84 of file TMoveTree.h.

References ASSERT_, INVALID_NODEID, and mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::m_nodes.

Referenced by mrpt::nav::PlannerRRT_SE2_TPS::solve().

Here is the caller graph for this function:

◆ getNextFreeNodeID()

template<class NODE_TYPE_DATA , class EDGE_TYPE , class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>

mrpt::graphs::TNodeID mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::getNextFreeNodeID ( ) const

inline

Definition at line 139 of file TMoveTree.h.

References mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::m_nodes.

Referenced by mrpt::nav::PlannerRRT_SE2_TPS::solve().

Here is the caller graph for this function:

◆ insertNode()

template<class NODE_TYPE_DATA , class EDGE_TYPE , class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>

void mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::insertNode	(	const mrpt::graphs::TNodeID	node_id,
		const NODE_TYPE_DATA &	node_data
	)

inline

Insert a node without edges (should be used only for a tree root node)

Definition at line 133 of file TMoveTree.h.

References INVALID_NODEID, and mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::m_nodes.

Referenced by mrpt::nav::PlannerRRT_SE2_TPS::solve().

Here is the caller graph for this function:

◆ insertNodeAndEdge()

template<class NODE_TYPE_DATA , class EDGE_TYPE , class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>

void mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::insertNodeAndEdge	(	const mrpt::graphs::TNodeID	parent_id,
		const mrpt::graphs::TNodeID	new_child_id,
		const NODE_TYPE_DATA &	new_child_node_data,
		const EDGE_TYPE &	new_edge_data
	)

inline

Definition at line 114 of file TMoveTree.h.

References mrpt::graphs::CDirectedTree< EDGE_TYPE >::edges_to_children, and mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::m_nodes.

Referenced by mrpt::nav::PlannerRRT_SE2_TPS::solve().

Here is the caller graph for this function:

◆ visitBreadthFirst()

void mrpt::graphs::CDirectedTree< EDGE_TYPE >::visitBreadthFirst	(	const TNodeID	vroot,
		Visitor &	user_visitor,
		const size_t	root_depth_level = `0`
	)		const

inlineinherited

Breadth-first visit of all children nodes of a given root (itself excluded from the visit), invoking a user-provided function for each node/edge.

See also: visitDepthFirst

Definition at line 139 of file CDirectedTree.h.

References mrpt::graphs::CDirectedTree< TYPE_EDGES >::edges_to_children, and mrpt::graphs::CDirectedTree< TYPE_EDGES >::visitDepthFirst().

◆ visitDepthFirst()

void mrpt::graphs::CDirectedTree< EDGE_TYPE >::visitDepthFirst	(	const TNodeID	vroot,
		Visitor &	user_visitor,
		const size_t	root_depth_level = `0`
	)		const

inlineinherited

Depth-first visit of all children nodes of a given root (itself excluded from the visit), invoking a user-provided function for each node/edge.

See also: visitBreadthFirst

Definition at line 119 of file CDirectedTree.h.

References mrpt::graphs::CDirectedTree< TYPE_EDGES >::edges_to_children, and mrpt::graphs::CDirectedTree< TYPE_EDGES >::visitDepthFirst().

Member Data Documentation

◆ edges_to_children

TMapNode2ListEdges mrpt::graphs::CDirectedTree< EDGE_TYPE >::edges_to_children

inherited

The edges of each node.

Definition at line 81 of file CDirectedTree.h.

Referenced by mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::insertNodeAndEdge().

◆ m_nodes

template<class NODE_TYPE_DATA , class EDGE_TYPE , class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>

node_map_t mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::m_nodes

private

Info per node.

Definition at line 177 of file TMoveTree.h.

Referenced by mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::backtrackPath(), mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::getAllNodes(), mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::getNearestNode(), mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::getNextFreeNodeID(), mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::insertNode(), and mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >::insertNodeAndEdge().

◆ root

TNodeID mrpt::graphs::CDirectedTree< EDGE_TYPE >::root

inherited

The root of the tree.

Definition at line 79 of file CDirectedTree.h.

Detailed Description

template<class NODE_TYPE_DATA, class EDGE_TYPE, class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector> class mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >

Classes

Public Types

Public Member Functions

Public Attributes

Private Attributes

Member Typedef Documentation

◆ base_t

◆ edge_t

◆ node_map_t

◆ path_t

◆ TListEdges

◆ TMapNode2ListEdges

Member Function Documentation

◆ backtrackPath()

◆ clear()

◆ getAllNodes()

◆ getAsTextDescription()

◆ getNearestNode()

◆ getNextFreeNodeID()

◆ insertNode()

◆ insertNodeAndEdge()

◆ visitBreadthFirst()

◆ visitDepthFirst()

Member Data Documentation

◆ edges_to_children

◆ m_nodes

◆ root

template<class NODE_TYPE_DATA, class EDGE_TYPE, class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector>
class mrpt::nav::TMoveTree< NODE_TYPE_DATA, EDGE_TYPE, MAPS_IMPLEMENTATION >