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

#include <AStarEpsilon.h>

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

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

[legend]

Public Member Functions
	AStarEpsilon (double optimalBound=2)

virtual	~AStarEpsilon ()

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)
	‍** More...

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

void	ExtractPathToStartFromID (uint64_t node, std::vector< state > &thePath)
	Returns the next state on the open list (but doesn't pop it off the queue). More...

const state &	GetParent (const state &s)

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 AStarEpsilon. More...

state	CheckNextOpenNode ()

state	CheckNextFocalNode ()

bool	GetOpenListGCost (const state &val, double &gCost) const

bool	GetFocalListGCost (const state &val, double &gCost) const

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

bool	GetClosedItem (const state &s, AStarOpenClosedData< state > &)

unsigned int	GetNumOpenItems ()

unsigned int	GetNumFocalItems ()

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

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

const int	GetNumItems ()

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

bool	HaveExpandedState (const state &val)

dataLocation	GetStateLocation (const state &val)

void	SetHeuristic (Heuristic< state > *h)

uint64_t	GetNodesExpanded () const

uint64_t	GetNodesTouched () const

void	LogFinalStats (StatCollection *)

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

void	Draw (Graphics::Display &d) const

void	SetOptimalityBound (double w)

double	GetOptimalityBound ()

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

virtual	~GenericSearchAlgorithm ()

virtual void	OpenGLDraw (const environment *env) const

Public Attributes
AStarOpenClosed< state, AStarCompare< state > >	f

AStarOpenClosed< state, GBFSCompare< state > >	focal

state	goal

state	start

Private Member Functions
void	DrawOpen (Graphics::Display &d) const

void	DrawFocal (Graphics::Display &d) const

void	ExpandOpen ()
	Expands a single state from the given open list. More...

void	ExpandFocal ()

Private Attributes
uint64_t	nodesTouched

uint64_t	nodesExpanded

std::vector< state >	neighbors

std::vector< uint64_t >	neighborID

std::vector< double >	edgeCosts

std::vector< dataLocation >	neighborLoc

std::vector< state >	solution

environment *	env

double	bestSolution

double	bound

uint64_t	uniqueNodesExpanded

Heuristic< state > *	theHeuristic

Detailed Description

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

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

Definition at line 41 of file AStarEpsilon.h.

Constructor & Destructor Documentation

◆ AStarEpsilon()

template<class state , class action , class environment >

AStarEpsilon< state, action, environment >::AStarEpsilon ( double optimalBound = 2 )

inline

Definition at line 43 of file AStarEpsilon.h.

References AStarEpsilon< state, action, environment >::bound, AStarEpsilon< state, action, environment >::env, AStarEpsilon< state, action, environment >::ResetNodeCount(), and AStarEpsilon< state, action, environment >::theHeuristic.

◆ ~AStarEpsilon()

template<class state , class action , class environment >

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

inlinevirtual

Definition at line 44 of file AStarEpsilon.h.

Member Function Documentation

◆ CheckNextFocalNode()

template<class state , class action , class environment >

state AStarEpsilon< state, action, environment >::CheckNextFocalNode

Definition at line 614 of file AStarEpsilon.h.

◆ CheckNextOpenNode()

template<class state , class action , class environment >

state AStarEpsilon< state, action, environment >::CheckNextOpenNode

Definition at line 607 of file AStarEpsilon.h.

◆ DoSingleSearchStep()

template<class state , class action , class environment >

bool AStarEpsilon< 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 253 of file AStarEpsilon.h.

References flesseq().

◆ Draw()

template<class state , class action , class environment >

void AStarEpsilon< state, action, environment >::Draw ( Graphics::Display & d ) const

Definition at line 729 of file AStarEpsilon.h.

References d.

◆ DrawFocal()

template<class state , class action , class environment >

void AStarEpsilon< state, action, environment >::DrawFocal ( Graphics::Display & d ) const

private

Definition at line 794 of file AStarEpsilon.h.

References d, kClosedList, and kOpenList.

◆ DrawOpen()

template<class state , class action , class environment >

void AStarEpsilon< state, action, environment >::DrawOpen ( Graphics::Display & d ) const

private

Definition at line 738 of file AStarEpsilon.h.

References d, kClosedList, and kOpenList.

◆ ExpandFocal()

template<class state , class action , class environment >

void AStarEpsilon< state, action, environment >::ExpandFocal

private

Definition at line 438 of file AStarEpsilon.h.

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

◆ ExpandOpen()

template<class state , class action , class environment >

void AStarEpsilon< state, action, environment >::ExpandOpen

private

Expands a single state from the given open list.

Author: Nathan Sturtevant

Date: 01/27/19

Definition at line 350 of file AStarEpsilon.h.

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

◆ ExtractPathToStart()

template<class state , class action , class environment >

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

inline

Definition at line 57 of file AStarEpsilon.h.

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

◆ ExtractPathToStartFromID()

template<class state , class action , class environment >

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

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. 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 538 of file AStarEpsilon.h.

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

◆ GetClosedItem()

template<class state , class action , class environment >

bool AStarEpsilon< state, action, environment >::GetClosedItem	(	const state &	s,
		AStarOpenClosedData< state > &	result
	)

Definition at line 649 of file AStarEpsilon.h.

References kClosedList.

◆ GetClosedListGCost()

template<class state , class action , class environment >

bool AStarEpsilon< 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 the states

Definition at line 594 of file AStarEpsilon.h.

References kClosedList.

◆ GetFocalItem()

template<class state , class action , class environment >

const AStarOpenClosedData<state>& AStarEpsilon< state, action, environment >::GetFocalItem ( unsigned int which )

inline

Definition at line 78 of file AStarEpsilon.h.

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

◆ GetFocalListGCost()

template<class state , class action , class environment >

bool AStarEpsilon< state, action, environment >::GetFocalListGCost	(	const state &	val,
		double &	gCost
	)		const

Definition at line 635 of file AStarEpsilon.h.

References kOpenList.

◆ GetItem()

template<class state , class action , class environment >

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

inline

Definition at line 80 of file AStarEpsilon.h.

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

◆ GetMemoryUsage()

template<class state , class action , class environment >

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

Return the amount of memory used by AStarEpsilon.

Author: Nathan Sturtevant

Date: 03/22/06

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

Definition at line 578 of file AStarEpsilon.h.

◆ GetName()

template<class state , class action , class environment >

const char * AStarEpsilon< 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 129 of file AStarEpsilon.h.

◆ GetNodesExpanded()

template<class state , class action , class environment >

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

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 88 of file AStarEpsilon.h.

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

◆ GetNodesTouched()

template<class state , class action , class environment >

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

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 89 of file AStarEpsilon.h.

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

◆ GetNumFocalItems()

template<class state , class action , class environment >

unsigned int AStarEpsilon< state, action, environment >::GetNumFocalItems ( )

inline

Definition at line 76 of file AStarEpsilon.h.

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

◆ GetNumItems()

template<class state , class action , class environment >

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

inline

Definition at line 79 of file AStarEpsilon.h.

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

◆ GetNumOpenItems()

template<class state , class action , class environment >

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

inline

Definition at line 75 of file AStarEpsilon.h.

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

◆ GetOpenItem()

template<class state , class action , class environment >

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

inline

Definition at line 77 of file AStarEpsilon.h.

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

◆ GetOpenListGCost()

template<class state , class action , class environment >

bool AStarEpsilon< state, action, environment >::GetOpenListGCost	(	const state &	val,
		double &	gCost
	)		const

Definition at line 622 of file AStarEpsilon.h.

References kOpenList.

◆ GetOptimalityBound()

template<class state , class action , class environment >

double AStarEpsilon< state, action, environment >::GetOptimalityBound ( )

inline

Definition at line 97 of file AStarEpsilon.h.

References AStarEpsilon< state, action, environment >::bound.

◆ GetParent()

template<class state , class action , class environment >

const state & AStarEpsilon< state, action, environment >::GetParent ( const state & s )

Definition at line 549 of file AStarEpsilon.h.

◆ GetPath() [1/2]

template<class state , class action , class environment >

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

virtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 163 of file AStarEpsilon.h.

◆ GetPath() [2/2]

template<class state , class action , class environment >

void AStarEpsilon< 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 148 of file AStarEpsilon.h.

◆ GetStateLocation()

template<class state , class action , class environment >

dataLocation AStarEpsilon< state, action, environment >::GetStateLocation ( const state & val )

inline

Definition at line 83 of file AStarEpsilon.h.

References AStarEpsilon< state, action, environment >::env, AStarEpsilon< state, action, environment >::focal, and AStarOpenClosed< state, CmpKey, dataStructure >::Lookup().

◆ GetUniqueNodesExpanded()

template<class state , class action , class environment >

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

inline

Definition at line 64 of file AStarEpsilon.h.

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

◆ HaveExpandedState()

template<class state , class action , class environment >

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

inline

Definition at line 81 of file AStarEpsilon.h.

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

◆ InitializeSearch()

template<class state , class action , class environment >

bool AStarEpsilon< 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 192 of file AStarEpsilon.h.

◆ LogFinalStats()

template<class state , class action , class environment >

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

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 91 of file AStarEpsilon.h.

◆ OpenGLDraw()

template<class state , class action , class environment >

void AStarEpsilon< 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 670 of file AStarEpsilon.h.

References kClosedList, and kOpenList.

◆ PrintStats()

template<class state , class action , class environment >

void AStarEpsilon< 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 564 of file AStarEpsilon.h.

◆ ResetNodeCount()

template<class state , class action , class environment >

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

inline

Definition at line 65 of file AStarEpsilon.h.

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

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

◆ SetHeuristic()

template<class state , class action , class environment >

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

inline

Definition at line 86 of file AStarEpsilon.h.

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

◆ SetOptimalityBound()

template<class state , class action , class environment >

void AStarEpsilon< state, action, environment >::SetOptimalityBound ( double w )

inline

Definition at line 96 of file AStarEpsilon.h.

References AStarEpsilon< state, action, environment >::bound.

Member Data Documentation

◆ bestSolution

template<class state , class action , class environment >

double AStarEpsilon< state, action, environment >::bestSolution

private

Definition at line 112 of file AStarEpsilon.h.

◆ bound

template<class state , class action , class environment >

double AStarEpsilon< state, action, environment >::bound

private

Definition at line 113 of file AStarEpsilon.h.

Referenced by AStarEpsilon< state, action, environment >::AStarEpsilon(), AStarEpsilon< state, action, environment >::GetOptimalityBound(), and AStarEpsilon< state, action, environment >::SetOptimalityBound().

◆ edgeCosts

template<class state , class action , class environment >

std::vector<double> AStarEpsilon< state, action, environment >::edgeCosts

private

Definition at line 107 of file AStarEpsilon.h.

◆ env

template<class state , class action , class environment >

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

private

Definition at line 111 of file AStarEpsilon.h.

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

◆ f

template<class state , class action , class environment >

AStarOpenClosed<state, AStarCompare<state> > AStarEpsilon< state, action, environment >::f

Definition at line 49 of file AStarEpsilon.h.

Referenced by AStarEpsilon< state, action, environment >::GetNumOpenItems(), and AStarEpsilon< state, action, environment >::GetOpenItem().

◆ focal

template<class state , class action , class environment >

AStarOpenClosed<state, GBFSCompare<state> > AStarEpsilon< state, action, environment >::focal

Definition at line 51 of file AStarEpsilon.h.

Referenced by AStarEpsilon< state, action, environment >::ExtractPathToStart(), AStarEpsilon< state, action, environment >::GetFocalItem(), AStarEpsilon< state, action, environment >::GetItem(), AStarEpsilon< state, action, environment >::GetNumFocalItems(), AStarEpsilon< state, action, environment >::GetNumItems(), AStarEpsilon< state, action, environment >::GetStateLocation(), and AStarEpsilon< state, action, environment >::HaveExpandedState().

◆ goal

template<class state , class action , class environment >

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

Definition at line 52 of file AStarEpsilon.h.

◆ neighborID

template<class state , class action , class environment >

std::vector<uint64_t> AStarEpsilon< state, action, environment >::neighborID

private

Definition at line 106 of file AStarEpsilon.h.

◆ neighborLoc

template<class state , class action , class environment >

std::vector<dataLocation> AStarEpsilon< state, action, environment >::neighborLoc

private

Definition at line 108 of file AStarEpsilon.h.

◆ neighbors

template<class state , class action , class environment >

std::vector<state> AStarEpsilon< state, action, environment >::neighbors

private

Definition at line 105 of file AStarEpsilon.h.

◆ nodesExpanded

template<class state , class action , class environment >

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

private

Definition at line 103 of file AStarEpsilon.h.

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

◆ nodesTouched

template<class state , class action , class environment >

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

private

Definition at line 103 of file AStarEpsilon.h.

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

◆ solution

template<class state , class action , class environment >

std::vector<state> AStarEpsilon< state, action, environment >::solution

private

Definition at line 110 of file AStarEpsilon.h.

◆ start

template<class state , class action , class environment >

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

Definition at line 52 of file AStarEpsilon.h.

◆ theHeuristic

template<class state , class action , class environment >

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

private

Definition at line 115 of file AStarEpsilon.h.

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

◆ uniqueNodesExpanded

template<class state , class action , class environment >

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

private

Definition at line 114 of file AStarEpsilon.h.

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

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

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

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

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

Constructor & Destructor Documentation

◆ AStarEpsilon()

◆ ~AStarEpsilon()

Member Function Documentation

◆ CheckNextFocalNode()

◆ CheckNextOpenNode()

◆ DoSingleSearchStep()

◆ Draw()

◆ DrawFocal()

◆ DrawOpen()

◆ ExpandFocal()

◆ ExpandOpen()

◆ ExtractPathToStart()

◆ ExtractPathToStartFromID()

◆ GetClosedItem()

◆ GetClosedListGCost()

◆ GetFocalItem()

◆ GetFocalListGCost()

◆ GetItem()

◆ GetMemoryUsage()

◆ GetName()

◆ GetNodesExpanded()

◆ GetNodesTouched()

◆ GetNumFocalItems()

◆ GetNumItems()

◆ GetNumOpenItems()

◆ GetOpenItem()

◆ GetOpenListGCost()

◆ GetOptimalityBound()

◆ GetParent()

◆ GetPath() [1/2]

◆ GetPath() [2/2]

◆ GetStateLocation()

◆ GetUniqueNodesExpanded()

◆ HaveExpandedState()

◆ InitializeSearch()

◆ LogFinalStats()

◆ OpenGLDraw()

◆ PrintStats()

◆ ResetNodeCount()

◆ SetHeuristic()

◆ SetOptimalityBound()

Member Data Documentation

◆ bestSolution

◆ bound

◆ edgeCosts

◆ env

◆ f

◆ focal

◆ goal

◆ neighborID

◆ neighborLoc

◆ neighbors

◆ nodesExpanded

◆ nodesTouched

◆ solution

◆ start

◆ theHeuristic

◆ uniqueNodesExpanded

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