PRLRTSk Class Reference

#include <PRLRTSk.h>

Inheritance diagram for PRLRTSk:

[legend]Collaboration diagram for PRLRTSk:

[legend]List of all members.


Public Member Functions
	PRLRTSk ()
	PRLRTSk (int d, double gamma, double lQ, int k)
virtual path *	getPath (graphAbstraction aMap, node from, node to, reservationProvider rp=NULL)
	The wrapper for the main procedure.
virtual const char *	getName ()
virtual	~PRLRTSk ()
int	getNumAbsLevels ()
void	setParams (PRLRTSklevelData _unitData, PRLRTSkGroup _group)
	Get the parameters of the PRLRTSk unit and set them inside PRLRTSk.
void	resetNewlySeenCount ()
int	getNewlySeenCount ()
graphAbstraction *	getAMap ()
Protected Attributes
algSpec *	algAtLevel
Private Member Functions
void	setCorridorIndex (node *n, int index)
	Sets the corridor index of a node.
void	setClosedListIndex (node *n, int index)
	Sets the closed list index of a node.
void	setDepth (node *n, int depth)
	Sets the depth of a node.
void	setgValue (node *n, double g)
	Sets the g-value of a node.
int	getCorridorIndex (node *n)
	Gets the corridor index of a node.
int	getClosedListIndex (node *n)
	Gets the closed list index of a node.
int	getDepth (node *n)
	Gets the depth of a node.
double	getgValue (node *n)
	Gets the g-value of a node.
void	setFValue (node *n, double fv)
	Sets the f-value of a node.
double	getFValue (node *n)
	Gets the f-value of a node.
void	setInternal (node *n)
	Sets the node to be internal (expandable) during large update.
bool	getInternal (node *n)
	Gets whether the node is internal (expandable) during large update.
int	getAllocateENI (node *n)
	Given a node, return the index of the corresponding extended node.
int	getENI (node *n)
	Tells us if the node is in the extNodes array.
void	generateName (char *name)
	Generates algorithm's name.
path *	lrts (graphAbstraction aMap, node from, node to, reservationProvider rp)
	The core routine of LRTS -- computes at most length d path.
path *	makePath (graph *g, unsigned current, int aLevel)
bool	abstractsTo (node s, node ap)
	Checks if the given node abstracts to the given abstract parent.
void	trimPath (node *newHead, int level)
	Scans through the cached path at the given level and deletes nodes until the new node supplied is encountered.
node *	aPathEnd (int aLevel)
	Finds the first non-pass-through level above the given level and scans the cached path there.
path *	waStar (graphAbstraction aMap, node from, node to, node hGoal, reservationProvider *rp)
	------------------ Weighted A* in a corridor ---------- Originally implemented by Nathan Sturtevant.
path *	extractBestPath (graph *g, unsigned int current)
	A helper function for PRLRTSk::wAStar.
void	relaxEdge (heap nodeHeap, graph g, graphAbstraction aMap, edge e, node from, node to, node *dest, double gamma)
	A helper function for PRLRTSk::wAStar.
bool	isOnAPath (node s, node *ap, int &l)
	Checks if a node is on a cached abstract path.
node *	aP (node *s)
	Returns the one-level parent of the given node.
void	resetCachedPaths ()
	Clears the cached paths and corridors.
path *	computePath (graphAbstraction aMap, node from, node to, reservationProvider rp)
	The main path-planning procedure.
int	defineCorridor (int aLevel)
	Finds and marks the corridor that restricts search at the given level.
void	markCorridor (corridor *c)
	Marks the corridor in extNodes for a constant time lookup.
void	buildCorridor (corridor c, path p)
	Builds a corridor for a given path.
bool	isLegitimateState (node *s)
	Checks if the given state is legitimate (i.e., can be included in the search): i.
double	updateHeuristic (graphAbstraction aMap, node from, node to, int d, double gamma, reservationProvider rp)
	Updates heuristic of a node by doing a d-ply lookahead.
Private Attributes
char	PRLRTSkName [128]
graphAbstraction *	aMap
PRLRTSkGroup *	group
int	numAbsLevels
PRLRTSklevelData *	unitData
std::deque< extNode >	extNodes
int	newlySeenCount
Friends
class	PRLRTSkGroup

Constructor & Destructor Documentation

PRLRTSk::PRLRTSk ( )

PRLRTSk::PRLRTSk ( int d,

double gamma,

double lQ,

int k

)

PRLRTSk::~PRLRTSk ( ) [virtual]

Member Function Documentation

bool PRLRTSk::abstractsTo ( node * s,

node * ap

) [private]

Checks if the given node abstracts to the given abstract parent.

node * PRLRTSk::aP ( node * s ) [private]

Returns the one-level parent of the given node.

node * PRLRTSk::aPathEnd ( int aLevel ) [private]

Finds the first non-pass-through level above the given level and scans the cached path there.
Returns the pointer to its end

void PRLRTSk::buildCorridor ( corridor * c,

path * p

) [private]

Builds a corridor for a given path.

path * PRLRTSk::computePath ( graphAbstraction * aMap,

node * from,

node * to,

reservationProvider * rp

) [private]

The main path-planning procedure.

int PRLRTSk::defineCorridor ( int aLevel ) [private]

Finds and marks the corridor that restricts search at the given level.
Returns -1 if no corridor is defined above us

path * PRLRTSk::extractBestPath ( graph * g,

unsigned int current

) [private]

A helper function for PRLRTSk::wAStar.

void PRLRTSk::generateName ( char * name ) [private]

Generates algorithm's name.

int PRLRTSk::getAllocateENI ( node * n ) [inline, private]

Given a node, return the index of the corresponding extended node.
Create one if needed

graphAbstraction* PRLRTSk::getAMap ( ) [inline]

int PRLRTSk::getClosedListIndex ( node * n ) [inline, private]

Gets the closed list index of a node.

int PRLRTSk::getCorridorIndex ( node * n ) [inline, private]

Gets the corridor index of a node.

int PRLRTSk::getDepth ( node * n ) [inline, private]

Gets the depth of a node.

int PRLRTSk::getENI ( node * n ) [inline, private]

Tells us if the node is in the extNodes array.

double PRLRTSk::getFValue ( node * n ) [inline, private]

Gets the f-value of a node.

double PRLRTSk::getgValue ( node * n ) [inline, private]

Gets the g-value of a node.

bool PRLRTSk::getInternal ( node * n ) [inline, private]

Gets whether the node is internal (expandable) during large update.

virtual const char* PRLRTSk::getName ( ) [inline, virtual]

Implements searchAlgorithm.

int PRLRTSk::getNewlySeenCount ( ) [inline]

int PRLRTSk::getNumAbsLevels ( ) [inline]

path * PRLRTSk::getPath ( graphAbstraction * aMap,

node * from,

node * to,

reservationProvider * rp = NULL

) [virtual]

The wrapper for the main procedure.

Implements searchAlgorithm.
Reimplemented in patPRLRTSk.

bool PRLRTSk::isLegitimateState ( node * s ) [private]

Checks if the given state is legitimate (i.e., can be included in the search): i.
there is no corridor above ii. there is a corridor above and the given state abstracts to it

bool PRLRTSk::isOnAPath ( node * s,

node ** ap,

int & l

) [private]

Checks if a node is on a cached abstract path.
If so then returns the corresponding abstract parent and its level in the hierarchy

path * PRLRTSk::lrts ( graphAbstraction * aMap,

node * from,

node * to,

reservationProvider * rp

) [private]

The core routine of LRTS -- computes at most length d path.

path * PRLRTSk::makePath ( graph * g,

unsigned current,

int aLevel

) [private]

void PRLRTSk::markCorridor ( corridor * c ) [private]

Marks the corridor in extNodes for a constant time lookup.

void PRLRTSk::relaxEdge ( heap * nodeHeap,

graph * g,

graphAbstraction * aMap,

edge * e,

node * from,

node * to,

node * dest,

double gamma

) [private]

A helper function for PRLRTSk::wAStar.

void PRLRTSk::resetCachedPaths ( ) [private]

Clears the cached paths and corridors.

void PRLRTSk::resetNewlySeenCount ( ) [inline]

void PRLRTSk::setClosedListIndex ( node * n,

int index

) [inline, private]

Sets the closed list index of a node.

void PRLRTSk::setCorridorIndex ( node * n,

int index

) [inline, private]

Sets the corridor index of a node.

void PRLRTSk::setDepth ( node * n,

int depth

) [inline, private]

Sets the depth of a node.

void PRLRTSk::setFValue ( node * n,

double fv

) [inline, private]

Sets the f-value of a node.

void PRLRTSk::setgValue ( node * n,

double g

) [inline, private]

Sets the g-value of a node.

void PRLRTSk::setInternal ( node * n ) [inline, private]

Sets the node to be internal (expandable) during large update.

void PRLRTSk::setParams ( PRLRTSklevelData * _unitData,

PRLRTSkGroup * _group

)

Get the parameters of the PRLRTSk unit and set them inside PRLRTSk.

void PRLRTSk::trimPath ( node * newHead,

int level

) [private]

Scans through the cached path at the given level and deletes nodes until the new node supplied is encountered.

double PRLRTSk::updateHeuristic ( graphAbstraction * aMap,

node * from,

node * to,

int d,

double gamma,

reservationProvider * rp

) [private]

Updates heuristic of a node by doing a d-ply lookahead.
Returns the amplitude of the update

path * PRLRTSk::waStar ( graphAbstraction * aMap,

node * from,

node * to,

node * hGoal,

reservationProvider * rp

) [private]

------------------ Weighted A* in a corridor ---------- Originally implemented by Nathan Sturtevant.
Extended to weighted A* and adopted to the PR LRTS settings by Vadim Bulitko. Computes the best path from FROM to TO. Uses hGoal as the heuristic goal. If TO is not on the same level as FROM, a path will be returned that ends inside the child of TO.