A templated version of A*, based on HOG genericAStar. More...

#include <PEAStar.h>

Inheritance diagram for PEAStar< state, action, environment >:

Collaboration diagram for PEAStar< state, action, environment >:

Public Member Functions
	PEAStar ()

virtual	~PEAStar ()

void	GetPath (environment *env, const state &from, const state &to, std::vector< state > &thePath)
	Perform an A* search between two states. More...

void	GetPath (environment *, const state &, const state &, std::vector< action > &)

bool	InitializeSearch (environment *env, const state &from, const state &to, std::vector< state > &thePath)
	Initialize the A* search. More...

bool	DoSingleSearchStep (std::vector< state > &thePath)
	Expand a single node. More...

void	AddAdditionalStartState (state &newState)
	Add additional start state to the search. More...

void	AddAdditionalStartState (state &newState, double cost)
	Add additional start state to the search. More...

state	CheckNextNode ()
	Returns the next state on the open list (but doesn't pop it off the queue). More...

void	ExtractPathToStart (state &node, std::vector< state > &thePath)

void	ExtractPathToStartFromID (uint64_t node, std::vector< state > &thePath)
	Get the path from a goal state to the start state. More...

virtual const char *	GetName ()
	Return the name of the algorithm. More...

void	PrintStats ()
	A function that prints the number of states in the closed list and open queue. More...

uint64_t	GetUniqueNodesExpanded ()

void	ResetNodeCount ()

int	GetMemoryUsage ()
	Return the amount of memory used by PEAStar. More...

bool	GetClosedListGCost (const state &val, double &gCost) const
	Get state from the closed list. More...

unsigned int	GetNumOpenItems ()

const AStarOpenClosedData< state > &	GetOpenItem (unsigned int which)

const int	GetNumItems ()

const AStarOpenClosedData< state > &	GetItem (unsigned int which)

bool	HaveExpandedState (const state &val)

void	SetReopenNodes (bool re)

bool	GetReopenNodes ()

void	SetHeuristic (Heuristic< state > *h)

uint64_t	GetNodesExpanded () const

uint64_t	GetNodesTouched () const

void	LogFinalStats (StatCollection *)

void	SetStopAfterGoal (bool val)

bool	GetStopAfterGoal ()

void	OpenGLDraw () const
	Draw the open/closed list. More...

void	SetWeight (double w)

Public Member Functions inherited from GenericSearchAlgorithm< state, action, environment >
	GenericSearchAlgorithm ()

virtual	~GenericSearchAlgorithm ()

virtual void	OpenGLDraw (const environment *env) const

Public Attributes
AStarOpenClosed< state, PEAStarCompare< state > >	openClosedList

state	goal

state	start

Private Attributes
std::vector< state >	succ

uint64_t	nodesTouched

uint64_t	nodesExpanded

environment *	env

bool	stopAfterGoal

double	weight

bool	reopenNodes

uint64_t	uniqueNodesExpanded

Heuristic< state > *	theHeuristic

Detailed Description

template<class state, class action, class environment>
class PEAStar< state, action, environment >

A templated version of A*, based on HOG genericAStar.

Definition at line 66 of file PEAStar.h.

Constructor & Destructor Documentation

◆ PEAStar()

template<class state , class action , class environment >

PEAStar< state, action, environment >::PEAStar ( )

inline

Definition at line 68 of file PEAStar.h.

References PEAStar< state, action, environment >::env, PEAStar< state, action, environment >::reopenNodes, PEAStar< state, action, environment >::ResetNodeCount(), PEAStar< state, action, environment >::stopAfterGoal, and PEAStar< state, action, environment >::weight.

◆ ~PEAStar()

template<class state , class action , class environment >

virtual PEAStar< state, action, environment >::~PEAStar ( )

inlinevirtual

Definition at line 69 of file PEAStar.h.

Member Function Documentation

◆ AddAdditionalStartState() [1/2]

template<class state , class action , class environment >

void PEAStar< state, action, environment >::AddAdditionalStartState ( state & newState )

Add additional start state to the search.

This should only be called after Initialize Search and before DoSingleSearchStep.

Author: Nathan Sturtevant

Date: 01/06/08

Definition at line 220 of file PEAStar.h.

◆ AddAdditionalStartState() [2/2]

template<class state , class action , class environment >

void PEAStar< state, action, environment >::AddAdditionalStartState	(	state &	newState,
		double	cost
	)

Add additional start state to the search.

This should only be called after Initialize Search

Author: Nathan Sturtevant

Date: 09/25/10

Definition at line 231 of file PEAStar.h.

◆ CheckNextNode()

template<class state , class action , class environment >

state PEAStar< state, action, environment >::CheckNextNode

Returns the next state on the open list (but doesn't pop it off the queue).

Author: Nathan Sturtevant

Date: 03/22/06

Returns: The first state in the open list.

Definition at line 357 of file PEAStar.h.

◆ DoSingleSearchStep()

template<class state , class action , class environment >

bool PEAStar< state, action, environment >::DoSingleSearchStep ( std::vector< state > & thePath )

virtual

Expand a single node.

Author: Nathan Sturtevant

Date: 03/22/06

Parameters

thePath will contain an optimal path from start to goal if the function returns TRUE

Returns: TRUE if there is no path or if we have found the goal, FALSE otherwise

Reimplemented from GenericSearchAlgorithm< state, action, environment >.

Definition at line 247 of file PEAStar.h.

References fequal(), fgreater(), fless(), kClosedList, kNotFound, and kOpenList.

◆ ExtractPathToStart()

template<class state , class action , class environment >

void PEAStar< state, action, environment >::ExtractPathToStart	(	state &	node,
		std::vector< state > &	thePath
	)

inline

Definition at line 84 of file PEAStar.h.

References PEAStar< state, action, environment >::env, PEAStar< state, action, environment >::ExtractPathToStartFromID(), AStarOpenClosed< state, CmpKey, dataStructure >::Lookup(), and PEAStar< state, action, environment >::openClosedList.

◆ ExtractPathToStartFromID()

template<class state , class action , class environment >

void PEAStar< state, action, environment >::ExtractPathToStartFromID	(	uint64_t	node,
		std::vector< state > &	thePath
	)

Get the path from a goal state to the start state.

Author: Nathan Sturtevant

Date: 03/22/06

Parameters

goalNode	the goal state
thePath	will contain the path from goalNode to the start state

Definition at line 375 of file PEAStar.h.

Referenced by PEAStar< state, action, environment >::ExtractPathToStart().

◆ GetClosedListGCost()

template<class state , class action , class environment >

bool PEAStar< state, action, environment >::GetClosedListGCost	(	const state &	val,
		double &	gCost
	)		const

Get state from the closed list.

Author: Nathan Sturtevant

Date: 10/09/07

Parameters

val	The state to lookup in the closed list @gCost The g-cost of the node in the closed list

Returns: success Whether we found the value or not more states

Definition at line 422 of file PEAStar.h.

References kClosedList.

◆ GetItem()

template<class state , class action , class environment >

const AStarOpenClosedData<state>& PEAStar< state, action, environment >::GetItem ( unsigned int which )

inline

Definition at line 102 of file PEAStar.h.

References AStarOpenClosed< state, CmpKey, dataStructure >::Lookat(), and PEAStar< state, action, environment >::openClosedList.

◆ GetMemoryUsage()

template<class state , class action , class environment >

int PEAStar< state, action, environment >::GetMemoryUsage

Return the amount of memory used by PEAStar.

Author: Nathan Sturtevant

Date: 03/22/06

Returns: The combined number of elements in the closed list and open queue

Definition at line 406 of file PEAStar.h.

◆ GetName()

template<class state , class action , class environment >

const char * PEAStar< state, action, environment >::GetName

virtual

Return the name of the algorithm.

Author: Nathan Sturtevant

Date: 03/22/06

Returns: The name of the algorithm

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 146 of file PEAStar.h.

◆ GetNodesExpanded()

template<class state , class action , class environment >

uint64_t PEAStar< state, action, environment >::GetNodesExpanded ( ) const

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 111 of file PEAStar.h.

References PEAStar< state, action, environment >::nodesExpanded.

◆ GetNodesTouched()

template<class state , class action , class environment >

uint64_t PEAStar< state, action, environment >::GetNodesTouched ( ) const

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 112 of file PEAStar.h.

References PEAStar< state, action, environment >::nodesTouched.

◆ GetNumItems()

template<class state , class action , class environment >

const int PEAStar< state, action, environment >::GetNumItems ( )

inline

Definition at line 101 of file PEAStar.h.

References PEAStar< state, action, environment >::openClosedList, and AStarOpenClosed< state, CmpKey, dataStructure >::size().

◆ GetNumOpenItems()

template<class state , class action , class environment >

unsigned int PEAStar< state, action, environment >::GetNumOpenItems ( )

inline

Definition at line 99 of file PEAStar.h.

References PEAStar< state, action, environment >::openClosedList, and AStarOpenClosed< state, CmpKey, dataStructure >::OpenSize().

◆ GetOpenItem()

template<class state , class action , class environment >

const AStarOpenClosedData<state>& PEAStar< state, action, environment >::GetOpenItem ( unsigned int which )

inline

Definition at line 100 of file PEAStar.h.

References AStarOpenClosed< state, CmpKey, dataStructure >::GetOpenItem(), AStarOpenClosed< state, CmpKey, dataStructure >::Lookat(), and PEAStar< state, action, environment >::openClosedList.

◆ GetPath() [1/2]

template<class state , class action , class environment >

void PEAStar< state, action, environment >::GetPath	(	environment *	,
		const state &	,
		const state &	,
		std::vector< action > &
	)

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 72 of file PEAStar.h.

◆ GetPath() [2/2]

template<class state , class action , class environment >

void PEAStar< state, action, environment >::GetPath	(	environment *	_env,
		const state &	from,
		const state &	to,
		std::vector< state > &	thePath
	)

virtual

Perform an A* search between two states.

Author: Nathan Sturtevant

Date: 03/22/06

Parameters

_env	The search environment
from	The start state
to	The goal state
thePath	A vector of states which will contain an optimal path between from and to when the function returns, if one exists.

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 165 of file PEAStar.h.

◆ GetReopenNodes()

template<class state , class action , class environment >

bool PEAStar< state, action, environment >::GetReopenNodes ( )

inline

Definition at line 107 of file PEAStar.h.

References PEAStar< state, action, environment >::reopenNodes.

◆ GetStopAfterGoal()

template<class state , class action , class environment >

bool PEAStar< state, action, environment >::GetStopAfterGoal ( )

inline

Definition at line 117 of file PEAStar.h.

References PEAStar< state, action, environment >::stopAfterGoal.

◆ GetUniqueNodesExpanded()

template<class state , class action , class environment >

uint64_t PEAStar< state, action, environment >::GetUniqueNodesExpanded ( )

inline

Definition at line 90 of file PEAStar.h.

References PEAStar< state, action, environment >::uniqueNodesExpanded.

◆ HaveExpandedState()

template<class state , class action , class environment >

bool PEAStar< state, action, environment >::HaveExpandedState ( const state & val )

inline

Definition at line 103 of file PEAStar.h.

References PEAStar< state, action, environment >::env, kNotFound, AStarOpenClosed< state, CmpKey, dataStructure >::Lookup(), and PEAStar< state, action, environment >::openClosedList.

◆ InitializeSearch()

template<class state , class action , class environment >

bool PEAStar< state, action, environment >::InitializeSearch	(	environment *	_env,
		const state &	from,
		const state &	to,
		std::vector< state > &	thePath
	)

virtual

Initialize the A* search.

Author: Nathan Sturtevant

Date: 03/22/06

Parameters

_env	The search environment
from	The start state
to	The goal state

Returns: TRUE if initialization was successful, FALSE otherwise

Reimplemented from GenericSearchAlgorithm< state, action, environment >.

Definition at line 186 of file PEAStar.h.

◆ LogFinalStats()

template<class state , class action , class environment >

void PEAStar< state, action, environment >::LogFinalStats ( StatCollection * )

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 114 of file PEAStar.h.

◆ OpenGLDraw()

template<class state , class action , class environment >

void PEAStar< state, action, environment >::OpenGLDraw

virtual

Draw the open/closed list.

Author: Nathan Sturtevant

Date: 03/12/09

Reimplemented from GenericSearchAlgorithm< state, action, environment >.

Definition at line 441 of file PEAStar.h.

References AStarOpenClosedData< state >::data, kClosedList, kOpenList, AStarOpenClosedData< state >::reopened, and AStarOpenClosedData< state >::where.

◆ PrintStats()

template<class state , class action , class environment >

void PEAStar< state, action, environment >::PrintStats

A function that prints the number of states in the closed list and open queue.

Author: Nathan Sturtevant

Date: 03/22/06

Definition at line 392 of file PEAStar.h.

◆ ResetNodeCount()

template<class state , class action , class environment >

void PEAStar< state, action, environment >::ResetNodeCount ( )

inline

Definition at line 91 of file PEAStar.h.

References PEAStar< state, action, environment >::nodesExpanded, PEAStar< state, action, environment >::nodesTouched, and PEAStar< state, action, environment >::uniqueNodesExpanded.

Referenced by PEAStar< state, action, environment >::PEAStar().

◆ SetHeuristic()

template<class state , class action , class environment >

void PEAStar< state, action, environment >::SetHeuristic ( Heuristic< state > * h )

inline

Definition at line 109 of file PEAStar.h.

References PEAStar< state, action, environment >::theHeuristic.

◆ SetReopenNodes()

template<class state , class action , class environment >

void PEAStar< state, action, environment >::SetReopenNodes ( bool re )

inline

Definition at line 106 of file PEAStar.h.

References PEAStar< state, action, environment >::reopenNodes.

◆ SetStopAfterGoal()

template<class state , class action , class environment >

void PEAStar< state, action, environment >::SetStopAfterGoal ( bool val )

inline

Definition at line 116 of file PEAStar.h.

References PEAStar< state, action, environment >::stopAfterGoal.

◆ SetWeight()

template<class state , class action , class environment >

void PEAStar< state, action, environment >::SetWeight ( double w )

inline

Definition at line 121 of file PEAStar.h.

References PEAStar< state, action, environment >::weight.

Member Data Documentation

◆ env

template<class state , class action , class environment >

environment* PEAStar< state, action, environment >::env

private

Definition at line 125 of file PEAStar.h.

Referenced by PEAStar< state, action, environment >::ExtractPathToStart(), PEAStar< state, action, environment >::HaveExpandedState(), and PEAStar< state, action, environment >::PEAStar().

◆ goal

template<class state , class action , class environment >

state PEAStar< state, action, environment >::goal

Definition at line 76 of file PEAStar.h.

◆ nodesExpanded

template<class state , class action , class environment >

uint64_t PEAStar< state, action, environment >::nodesExpanded

private

Definition at line 124 of file PEAStar.h.

Referenced by PEAStar< state, action, environment >::GetNodesExpanded(), and PEAStar< state, action, environment >::ResetNodeCount().

◆ nodesTouched

template<class state , class action , class environment >

uint64_t PEAStar< state, action, environment >::nodesTouched

private

Definition at line 124 of file PEAStar.h.

Referenced by PEAStar< state, action, environment >::GetNodesTouched(), and PEAStar< state, action, environment >::ResetNodeCount().

◆ openClosedList

template<class state , class action , class environment >

AStarOpenClosed<state, PEAStarCompare<state> > PEAStar< state, action, environment >::openClosedList

Definition at line 72 of file PEAStar.h.

Referenced by PEAStar< state, action, environment >::ExtractPathToStart(), PEAStar< state, action, environment >::GetItem(), PEAStar< state, action, environment >::GetNumItems(), PEAStar< state, action, environment >::GetNumOpenItems(), PEAStar< state, action, environment >::GetOpenItem(), and PEAStar< state, action, environment >::HaveExpandedState().

◆ reopenNodes

template<class state , class action , class environment >

bool PEAStar< state, action, environment >::reopenNodes

private

Definition at line 130 of file PEAStar.h.

Referenced by PEAStar< state, action, environment >::GetReopenNodes(), PEAStar< state, action, environment >::PEAStar(), and PEAStar< state, action, environment >::SetReopenNodes().

◆ start

template<class state , class action , class environment >

state PEAStar< state, action, environment >::start

Definition at line 76 of file PEAStar.h.

◆ stopAfterGoal

template<class state , class action , class environment >

bool PEAStar< state, action, environment >::stopAfterGoal

private

Definition at line 126 of file PEAStar.h.

Referenced by PEAStar< state, action, environment >::GetStopAfterGoal(), PEAStar< state, action, environment >::PEAStar(), and PEAStar< state, action, environment >::SetStopAfterGoal().

◆ succ

template<class state , class action , class environment >

std::vector<state> PEAStar< state, action, environment >::succ

private

Definition at line 123 of file PEAStar.h.

◆ theHeuristic

template<class state , class action , class environment >

Heuristic<state>* PEAStar< state, action, environment >::theHeuristic

private

Definition at line 132 of file PEAStar.h.

Referenced by PEAStar< state, action, environment >::SetHeuristic().

◆ uniqueNodesExpanded

template<class state , class action , class environment >

uint64_t PEAStar< state, action, environment >::uniqueNodesExpanded

private

Definition at line 131 of file PEAStar.h.

Referenced by PEAStar< state, action, environment >::GetUniqueNodesExpanded(), and PEAStar< state, action, environment >::ResetNodeCount().

◆ weight

template<class state , class action , class environment >

double PEAStar< state, action, environment >::weight

private

Definition at line 128 of file PEAStar.h.

Referenced by PEAStar< state, action, environment >::PEAStar(), and PEAStar< state, action, environment >::SetWeight().

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

/home/sturtevant/nightly/hog2/generic/PEAStar.h

Public Member Functions

Public Attributes

Private Attributes

Detailed Description

template<class state, class action, class environment> class PEAStar< state, action, environment >

Constructor & Destructor Documentation

◆ PEAStar()

◆ ~PEAStar()

Member Function Documentation

◆ AddAdditionalStartState() [1/2]

◆ AddAdditionalStartState() [2/2]

◆ CheckNextNode()

◆ DoSingleSearchStep()

◆ ExtractPathToStart()

◆ ExtractPathToStartFromID()

◆ GetClosedListGCost()

◆ GetItem()

◆ GetMemoryUsage()

◆ GetName()

◆ GetNodesExpanded()

◆ GetNodesTouched()

◆ GetNumItems()

◆ GetNumOpenItems()

◆ GetOpenItem()

◆ GetPath() [1/2]

◆ GetPath() [2/2]

◆ GetReopenNodes()

◆ GetStopAfterGoal()

◆ GetUniqueNodesExpanded()

◆ HaveExpandedState()

◆ InitializeSearch()

◆ LogFinalStats()

◆ OpenGLDraw()

◆ PrintStats()

◆ ResetNodeCount()

◆ SetHeuristic()

◆ SetReopenNodes()

◆ SetStopAfterGoal()

◆ SetWeight()

Member Data Documentation

◆ env

◆ goal

◆ nodesExpanded

◆ nodesTouched

◆ openClosedList

◆ reopenNodes

◆ start

◆ stopAfterGoal

◆ succ

◆ theHeuristic

◆ uniqueNodesExpanded

◆ weight

template<class state, class action, class environment>
class PEAStar< state, action, environment >