Koenigs Class Reference

#include <Koenigs.h>

Inheritance diagram for Koenigs:

[legend]Collaboration diagram for Koenigs:

[legend]List of all members.


Public Member Functions
	Koenigs ()
	Koenigs (int sizeLSS)
virtual	~Koenigs ()
void	setParams (KoenigslevelData _unitData, KoenigsGroup _group)
	Get the parameters of the Koenigs unit and set them inside Koenigs.
path *	getPath (graphAbstraction aMap, node from, node to, reservationProvider rp=NULL)
	The wrapper for the main procedure.
virtual const char *	getName ()
int	getNumAbsLevels ()
void	resetNewlySeenCount ()
int	getNewlySeenCount ()
graphAbstraction *	getAMap ()
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.
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.
void	resetCachedPaths ()
	Clears the cached paths and corridors.
int	defineCorridor (int aLevel)
	Finds and marks the corridor that restricts search at the given level.
void	markCorridor (corridor *c)
	Mark the corridor in extNodes for a constant time lookup.
void	relaxEdge (heap nodeHeap, graph g, edge e, int source, int nextNode, node d, graphAbstraction *map)
	This is the standard definition of relaxation as in Introduction to Algorithms (cormen, leiserson and rivest).
void	aStarLSS (graphAbstraction map, node from, node to, reservationProvider rp)
	Define the local search space (LSS) in terms of the first n states expanded by an A* search.
void	relaxLSS (graphAbstraction map, node from, node *to)
	Update the heuristic values in the local search space (LSS) using Dijkstra's algorithm, as prescribed by Koenig in "A Comparison of Fast Search Methods for Real-Time Situated Agents".
path *	greedyPathLSS (graphAbstraction aMap, node from, node to, reservationProvider rp)
	Returns a path generated by using the greedy strategy: repeatedly move from the current state to the neighboring state s that minimizes f; ties are broken in favor of staying in the LSS.
Private Attributes
char	KoenigsName [128]
graphAbstraction *	aMap
KoenigsGroup *	group
int	numAbsLevels
algSpec *	algAtLevel
KoenigslevelData *	unitData
std::deque< extNode >	extNodes
int	newlySeenCount
std::vector< node * >	_LSS
std::map< node *, bool, ltNodePtr >	_inLSS
unsigned int	_sizeLSS
Friends
class	KoenigsGroup

Constructor & Destructor Documentation

Koenigs::Koenigs ( )

Koenigs::Koenigs ( int sizeLSS )

Koenigs::~Koenigs ( ) [virtual]

Member Function Documentation

void Koenigs::aStarLSS ( graphAbstraction * map,

node * from,

node * to,

reservationProvider * rp

) [inline, private]

Define the local search space (LSS) in terms of the first n states expanded by an A* search.
This code taken from Nathan's A* implementation in aStar.cpp

int Koenigs::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

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

Generates algorithm's name.

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

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

graphAbstraction* Koenigs::getAMap ( ) [inline]

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

Gets the closed list index of a node.

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

Gets the corridor index of a node.

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

Gets the depth of a node.

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

Tells us if the node is in the extNodes array.

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

Gets the g-value of a node.

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

Implements searchAlgorithm.

int Koenigs::getNewlySeenCount ( ) [inline]

int Koenigs::getNumAbsLevels ( ) [inline]

path * Koenigs::getPath ( graphAbstraction * aMap,

node * from,

node * to,

reservationProvider * rp = NULL

) [virtual]

The wrapper for the main procedure.

Implements searchAlgorithm.

path * Koenigs::greedyPathLSS ( graphAbstraction * aMap,

node * from,

node * to,

reservationProvider * rp

) [private]

Returns a path generated by using the greedy strategy: repeatedly move from the current state to the neighboring state s that minimizes f; ties are broken in favor of staying in the LSS.

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

Mark the corridor in extNodes for a constant time lookup.

void Koenigs::relaxEdge ( heap * nodeHeap,

graph * g,

edge * e,

int source,

int nextNode,

node * d,

graphAbstraction * map

) [inline, private]

This is the standard definition of relaxation as in Introduction to Algorithms (cormen, leiserson and rivest).
This code taken from Nathan's A* implementation in aStar.cpp

void Koenigs::relaxLSS ( graphAbstraction * map,

node * from,

node * to

) [inline, private]

Update the heuristic values in the local search space (LSS) using Dijkstra's algorithm, as prescribed by Koenig in "A Comparison of Fast Search Methods for Real-Time Situated Agents".
(1) Go through the LSS and, for each state s on the border of the LSS, enter s into a heap with the appropriate cost.
(2) Remove the 'best' state from the top of the heap and set its h value. Relax the neighbors (update their potential h values) and repeat.

void Koenigs::resetCachedPaths ( ) [private]

Clears the cached paths and corridors.

void Koenigs::resetNewlySeenCount ( ) [inline]

void Koenigs::setClosedListIndex ( node * n,

int index

) [inline, private]

Sets the closed list index of a node.

void Koenigs::setCorridorIndex ( node * n,

int index

) [inline, private]

Sets the corridor index of a node.

void Koenigs::setDepth ( node * n,

int depth

) [inline, private]

Sets the depth of a node.

void Koenigs::setgValue ( node * n,

double g

) [inline, private]

Sets the g-value of a node.

void Koenigs::setParams ( KoenigslevelData * _unitData,

KoenigsGroup * _group

)

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