NavGraph build and manages the graph over a raster. More...

Detailed Description

NavGraph build and manages the graph over a raster.

Definition at line 59 of file NavGraph.hpp.

#include <NavGraph.hpp>

Inheritance diagram for jafar::lgl::NavGraph:

Public Types
enum	verbose_tag { VERBOSE_SILENT = 0, VERBOSE_ERRORS, VERBOSE_WARNINGS, VERBOSE_INFO, VERBOSE_DEBUG }
typedef NavGraphT< NavGEdge, NavGNode, COST_TYPE >	NavGraphContainer
	The navigation graph container with edge, node and cost definitions.
typedef NavAStar < NavGraphContainer::GraphContainer, NavGraphContainer::Vertex, COST_TYPE >	AStarPlanner
	A* star search path planner definition.
typedef std::pair < NavGraphContainer::Vertex, double >	frontierPoint
	Frontier element.
Public Member Functions
	NavGraph ()
	Default Constructor.
	NavGraph (GeoData _geodata, Quadtree< double, GeoData > _quadtree=NULL, bool _doNavGraphPruning=PRUNING_DISABLED, double _pruningThreshold=DEFAULT_PRUNING_THRESHOLD, PositionManager _posManager=NULL, CostManager _costManager=NULL, boost::function< void(const NavGNode &, int)> displayHook=NULL)
	Constructor.
	~NavGraph ()
	Destructor.
NavGraphContainer *	getGraph ()
	Return the pointer on the graph container usable in boost macros.
Quadtree< double, GeoData > *	getQuadtree ()
	Return the quadtree pointer.
bool	rebuildGraph ()
	Simply clears the graph and recalls buildGraph.
bool	findPath (const NavLocation &locstart, const NavLocation &locend, NavPath &navpath)
	Calculates path with AStar according to the Edge::weight.
bool	fastFindPath (const NavLocation &locstart, const NavLocation &locend, NavPath &navpath)
	Fast find path without any other calculus.
bool	findPath (const NavLocation &locstart, const NavLocation &locend, NavPath &navpath, double &pCost)
	Calculates path with AStar according to the Edge::weight and returns path cost.
bool	fastFindPath (const NavLocation &locstart, const NavLocation &locend, NavPath &navpath, double &pCost)
	Fast find path without any other calculus.
bool	findPathOnUtility (const NavLocation &start, const NavLocation &end, NavPath &navpath, double authDist=0.0)
	Calculates path with AStar according to the Edge::gru.
double	navCostAtNode (const NavLocation &_loc)
	Selects corresponding node at location and returns navigation cost.
double	navCostAtNode (const NavGraphContainer::Vertex &vn)
	Caculates navigation cost.
double	getPathCost ()
	Get the nominal path overall cost.
double	getCoopPathCost ()
	Get the cooperative path overall cost.
int	getNumberOfVertices ()
	Get the number of vertices in the graph.
int	getNumberOfEdges ()
	Get the number of edges in the graph.
void	getNavGNodeFromNavLocation (NavGNode &nnode, const NavLocation &v)
	Get a copy of the corresponding node at the given navigation location.
void	getOffClusterFromVertex (const NavGraphContainer::Vertex &A, DecompCluster **dcluster, int &i, int &j)
	Returns the decomposition cluster that has the greatest information entropy in the direct neighborhood around vertex A It also gives a pointer to the cluster in order to retreive its attribute and gives its position (i,j) in term of raster cell index.
NavLocation	getNavLocFromVertex (const NavGraphContainer::Vertex &A)
	Few lines to get the navigation location from a graph vertex.
bool	areClose (const NavGraphContainer::Vertex &a, const NavGraphContainer::Vertex &b)
	Return true of vertex a and b are spatially close according to "closeDistance" object variable.
double	euclideanDistance (const NavGraphContainer::Vertex &a, const NavGraphContainer::Vertex &b)
	Returns the euclidean distance between two vertices.
bool	saveAnyField (const std::string &outfile, attributeKey _at)
	Output binary ppm showing the beautiful path alternative field.
bool	resetGoalReachingPotential ()
	Reset all graph nodes potential (Goal Reaching Potential)
bool	updateNavigationUtility ()
	Calculates navigation utility from entropy and GRP.
double *	getPotential ()
	Return the sparsly interpolated grid of path alternative potential.
void	calculateNavigationUtility (bool bsetter)
	Set the parameter to enable the navigation utility calculation.
void	calculateGoalReachingPotential (bool bsetter)
	Set the parameter to enable GRP calculation.
void	setGeodataPotential (bool bsetter)
	Dis/Enable GRP to be transported to the Geodata.
void	setGeodataUtility (bool bsetter)
	Dis/Enable GRU to be transported to the Geodata.
void	calculateTerrainFactor ()
	Function to precalculate terrain classes cost factors*.
void	addNode (const NavLocation &atThisLoc, NavGraphContainer::Vertex &vloc)
	Add a node to the graph.
bool	isOnFrontier (NavGraphContainer::Vertex &vloc)
	Check if this node is on the frontier between known and unknown environment.
bool	extendFrontiers (NavGraphContainer::Vertex &vfrontier, double vcost)
	Sort-Insert a new vertex in the frontier point list.
void	setNavGraphPruningOption (bool _doNavGraphPruning)
	Enable or disabled the pruning of obstacle vertices and edges in the navigation graph.
bool	getNavGraphPruningOption ()
	Tell if the pruning option is enabled or not.
void	setPathPruningOption (bool _doPathPruning)
	Enable or disabled the pruning of paths on pruned zones.
bool	getPathPruningOption ()
	Tell if the path pruning option is enabled or not.
void	setPruningThreshold (double _pruningThreshold)
	Change the threshold value for the obstacle pruning option.
double	getPruningThreshold ()
	Give the current pruningThreshold value.
PositionManager *	getPositionManager ()
	Returns the point to the position manager so it can be used outside.
std::list< frontierPoint >	getFrontiers ()
	Returns the current list of frontier points.
double	getNSP (const NavGraphContainer::Vertex &v)
	Return the navigation success potential NSP of the corresponding vertex.
bool	isCalculateGRP ()
	Return calculate_grp.
bool	isSetGeodataPotential ()
	Return set_geodata_grp.
Public Attributes
verbose_tag	verbose
	Tell the nav graph what to print out.
Protected Member Functions
void	setDisplayHookFunction (boost::function< void(const NavGNode &, int)>_displayHook)
Protected Attributes
GeoData *	geodata
Quadtree< double, GeoData > *	quadtree
	Quadtree associated to the geodata.
bool	doNavGraphPruning
	If true, the navigation graph will prune the obstacle edges and vertices.
double	pruningThreshold
	Threshold while pruning obstacles in the navigation graph a DEFAULT_PRUNING_THRESHOLD value is fixed (0.5) NB : between 0 and 1 ; a high value means less tolerance.
bool	doPathPruning
	Tells the path finder to cut path search to the closest position while looking for path between undisconnected positions (when start or goal is in a pruned zone).
PositionManager *	posManager
	Associated position manager.
CostManager *	costManager
	Associated cost manager.
NavGraphContainer *	graph
	THe graph containing all edges and vertices built upon the quadtree decomposition of the geodata.
AStarPlanner *	planner
	Planner to find path in the graph thanx to A Star.
boost::function< void(const NavGNode &, int)>	displayHook
	Outside viewer which some functions are used to display what's happening in boost astar.
Private Types
typedef double	COST_TYPE
	Cost type definition.
Private Member Functions
bool	buildGraph ()
	Build graph over the terrain using the quadtree/decomp information.
Private Attributes
bool	m_quadtree_madeinhere
	Tag to tell if quadtree is auto produced.
bool	m_costmanager_madeinhere
	Tag to tell if cost manager has been auto produced.
bool	m_posmanager_madeinhere
	Tag to tell if the position manager has been auto produced.
double	m_closeDistance
	Distance to determine that a point is close or not from the goal.
bool	set_geodata_gru
	If True NavGraph will update geodata internal maps with the goal reaching utility.
bool	set_geodata_grp
	If True NavGraph will update geodata internal maps using the goal reaching potential value.
bool	calculate_navutil
	If True the Path utilitywill be calculated after each path planning.
bool	calculate_grp
	If True the Goal Reaching Potential will be calculated after each path planning.
double	terrainFactor [((T_OBSTACLE-T_FREE)+1)]
	Terrain classes weight for navigation cost calculation RElation between speeds of operations.
double	pathCost
	Resulting path cost.
double	coopPathCost
	Resultingi cooperation path cost.
std::list< frontierPoint >	frontiers
	Odered list of frontier points and their associated cost.

Constructor & Destructor Documentation

jafar::lgl::NavGraph::NavGraph	(	GeoData *	_geodata,
		Quadtree< double, GeoData > *	_quadtree = `NULL`,
		bool	_doNavGraphPruning = `PRUNING_DISABLED`,
		double	_pruningThreshold = `DEFAULT_PRUNING_THRESHOLD`,
		PositionManager *	_posManager = `NULL`,
		CostManager *	_costManager = `NULL`,
		boost::function< void(const NavGNode &, int)>	displayHook = `NULL`
	)

Constructor.

Parameters:

_posManager	The position manager only depends on the geo data and the quad tree so they are not mandatory.
_costManager	The cost manager only depends on the geo data and the quad tree so they are not mandatory.
_quadtree	The quadtree is not a mandatory parameter as it only depends on the geodata

Member Function Documentation

void jafar::lgl::NavGraph::addNode	(	const NavLocation &	atThisLoc,
		NavGraphContainer::Vertex &	vloc
	)

Add a node to the graph.

The connexion is assured within its cluster (or clusters if on a cluster's border) by the creation of all edges to its neighbor nodes.

Does not check if there is already a node at this location.
Equal weights are set on both edge-directions.

Parameters:

atThisLoc	Navigation location at which the node will be added
vloc	will be set as the corresponding graph vertex

bool jafar::lgl::NavGraph::buildGraph ( ) [private]

Build graph over the terrain using the quadtree/decomp information.

void jafar::lgl::NavGraph::calculateGoalReachingPotential ( bool bsetter )

Set the parameter to enable GRP calculation.

See also:: calculate_grp

void jafar::lgl::NavGraph::calculateNavigationUtility ( bool bsetter )

Set the parameter to enable the navigation utility calculation.

See also:: calculate_navutil

void jafar::lgl::NavGraph::calculateTerrainFactor ( )

Function to precalculate terrain classes cost factors*.

These costs are vehicule-dependant as they represent the rate differences between motion speed of a robot on different types of terrain.

bool jafar::lgl::NavGraph::extendFrontiers	(	NavGraphContainer::Vertex &	vfrontier,
		double	vcost
	)

Sort-Insert a new vertex in the frontier point list.

Parameters:

vfrontier	Vertex to add
vcost	its associated navigation cost (after path planning)

Returns:: false if vcost is the highest meaning vfrontier has been added at the end of the list.

bool jafar::lgl::NavGraph::fastFindPath	(	const NavLocation &	locstart,
		const NavLocation &	locend,
		NavPath &	navpath
	)

Fast find path without any other calculus.

See also:: findPath

bool jafar::lgl::NavGraph::fastFindPath	(	const NavLocation &	locstart,
		const NavLocation &	locend,
		NavPath &	navpath,
		double &	pCost
	)

Fast find path without any other calculus.

And set the path cost.

See also:: findPath

bool jafar::lgl::NavGraph::findPath	(	const NavLocation &	locstart,
		const NavLocation &	locend,
		NavPath &	navpath
	)

Calculates path with AStar according to the Edge::weight.

Parameters:

locstart	Start location
locend	Goal location
navpath	Resulting navigation path

bool jafar::lgl::NavGraph::findPathOnUtility	(	const NavLocation &	start,
		const NavLocation &	end,
		NavPath &	navpath,
		double	authDist = `0.0`
	)

Calculates path with AStar according to the Edge::gru.

Parameters:

start	Starting location
end	Goal location
navpath	Resulting path object.
authDist	Adviced distance for the wanted path. Usually used as the authorized distance before a meeting point. It sets a limit in time according to the space-time meeting and the motion capabilities of the vehicule requiring the path.

std::list<frontierPoint> jafar::lgl::NavGraph::getFrontiers ( )

Returns the current list of frontier points.

A frontier point is defined as a graph node at the interface between well-known and poorly-known lands.

void jafar::lgl::NavGraph::getNavGNodeFromNavLocation	(	NavGNode &	nnode,
		const NavLocation &	v
	)

Get a copy of the corresponding node at the given navigation location.

This method should not be used if your goal is to modify the graph contents. Rather than this you should use: vertex = graph->getVertex(NavLocation) and use the vertex (index) directly with the graph container: (*(graph->getGCtn()))[vertex]

bool jafar::lgl::NavGraph::getNavGraphPruningOption ( )

Tell if the pruning option is enabled or not.

Tell if the obstacle pruning option while building the navigation graph is enabled (true) or not (false).

double jafar::lgl::NavGraph::getNSP ( const NavGraphContainer::Vertex & v )

Return the navigation success potential NSP of the corresponding vertex.

Parameters:

v	Vertex on which we want the NSP

Returns:: the NSP of vertex v

bool jafar::lgl::NavGraph::getPathPruningOption ( )

Tell if the path pruning option is enabled or not.

True if enabled.

bool jafar::lgl::NavGraph::isOnFrontier ( NavGraphContainer::Vertex & vloc )

Check if this node is on the frontier between known and unknown environment.

The frontier nodes should have at least one high entropy connexion.

bool jafar::lgl::NavGraph::rebuildGraph ( )

Simply clears the graph and recalls buildGraph.

See also:: buildGraph()

void jafar::lgl::NavGraph::setGeodataPotential ( bool bsetter )

Dis/Enable GRP to be transported to the Geodata.

it costs time but it is very useful for visualisation

See also:: set_geodata_grp

void jafar::lgl::NavGraph::setGeodataUtility ( bool bsetter )

Dis/Enable GRU to be transported to the Geodata.

it costs time but it is very useful for visualisation

See also:: set_geodata_gru

void jafar::lgl::NavGraph::setNavGraphPruningOption ( bool _doNavGraphPruning )

Enable or disabled the pruning of obstacle vertices and edges in the navigation graph.

Parameters:

_doNavGraphPruning PRUNING_ENABLED (=true) or PRUNING_DISABLED

void jafar::lgl::NavGraph::setPathPruningOption ( bool _doPathPruning )

Enable or disabled the pruning of paths on pruned zones.

Parameters:

_doPathPruning true of false

void jafar::lgl::NavGraph::setPruningThreshold ( double _pruningThreshold )

Change the threshold value for the obstacle pruning option.

Parameters:

Pruning DEFAULT_PRUNING_THRESHOLD = 0.5

Member Data Documentation

bool jafar::lgl::NavGraph::calculate_grp [private]

If True the Goal Reaching Potential will be calculated after each path planning.

Definition at line 422 of file NavGraph.hpp.

bool jafar::lgl::NavGraph::calculate_navutil [private]

If True the Path utilitywill be calculated after each path planning.

Definition at line 419 of file NavGraph.hpp.

bool jafar::lgl::NavGraph::doNavGraphPruning [protected]

If true, the navigation graph will prune the obstacle edges and vertices.

PRUNING_ENABLED = true PRUNING_DISABLED = false

Definition at line 350 of file NavGraph.hpp.

bool jafar::lgl::NavGraph::doPathPruning [protected]

Tells the path finder to cut path search to the closest position while looking for path between undisconnected positions (when start or goal is in a pruned zone).

By default it is set as the same as doNavGraphPruning. If false the path won't be calculated at all if one of the position is in a pruned zone.