A generic focal list algorithm. More...

#include <Focal.h>

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

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

[legend]

Classes
struct	FocalTreapItem

struct	OpenTreapItem

struct	SearchState

Public Types
enum	stateLoc { kClosedList, kOpenList, kOpenFocalList }

Public Member Functions
	Focal (double optimalBound=2)

virtual	~Focal ()

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 (size_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 Focal. More...

state	CheckNextOpenNode ()
	Get state from the closed list. More...

state	CheckNextFocalNode ()

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

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

const int	GetNumItems ()

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 ()

unsigned int	GetNumOpenItems ()

unsigned int	GetNumFocalItems ()

const Focal< state, action, environment >::SearchState &	GetOpenItem (unsigned int which)

const Focal< state, action, environment >::SearchState &	GetFocalItem (unsigned int which)

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

virtual	~GenericSearchAlgorithm ()

virtual void	OpenGLDraw (const environment *env) const

Public Attributes
state	goal

state	start

Private Member Functions
SearchState &	PeekOpen ()

SearchState &	PeekFocal ()

void	Add (state &s, double g, double h, size_t parent)

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
Treap< FocalTreapItem >	focal

Treap< OpenTreapItem >	open

std::unordered_map< state, size_t >	hash

std::vector< SearchState >	states

std::function< double(double, double)>	phi_focal

std::function< double(double, double)>	phi_open

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

double	minF

Heuristic< state > *	theHeuristic

Detailed Description

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

A generic focal list algorithm.

Open is sorted by f; provide a function for sorting focal Provide a weight w Given minimum f in open, anything up to w*minf goes into focal Expand from focal until empty; otherwise expand from open

Definition at line 44 of file Focal.h.

Member Enumeration Documentation

◆ stateLoc

template<class state , class action , class environment >

enum Focal::stateLoc

Enumerator
kClosedList
kOpenList
kOpenFocalList

Definition at line 103 of file Focal.h.

Constructor & Destructor Documentation

◆ Focal()

template<class state , class action , class environment >

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

inline

Definition at line 46 of file Focal.h.

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

◆ ~Focal()

template<class state , class action , class environment >

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

inlinevirtual

Definition at line 52 of file Focal.h.

Member Function Documentation

◆ Add()

template<class state , class action , class environment >

void Focal< state, action, environment >::Add	(	state &	s,
		double	g,
		double	h,
		size_t	parent
	)

private

Definition at line 828 of file Focal.h.

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

◆ CheckNextFocalNode()

template<class state , class action , class environment >

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

Definition at line 778 of file Focal.h.

◆ CheckNextOpenNode()

template<class state , class action , class environment >

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

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 772 of file Focal.h.

◆ DoSingleSearchStep()

template<class state , class action , class environment >

bool Focal< 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 369 of file Focal.h.

References fless(), flesseq(), kOpenList, and Focal< state, action, environment >::FocalTreapItem::location.

◆ Draw()

template<class state , class action , class environment >

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

Definition at line 961 of file Focal.h.

References d, kClosedList, and kOpenList.

◆ DrawFocal()

template<class state , class action , class environment >

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

private

◆ DrawOpen()

template<class state , class action , class environment >

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

private

◆ ExpandFocal()

template<class state , class action , class environment >

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

private

Definition at line 578 of file Focal.h.

References kOpenList.

◆ ExpandOpen()

template<class state , class action , class environment >

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

private

Expands a single state from the given open list.

Author: Nathan Sturtevant

Date: 01/27/19

Definition at line 492 of file Focal.h.

References kClosedList.

◆ ExtractPathToStart()

template<class state , class action , class environment >

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

inline

Definition at line 65 of file Focal.h.

References Focal< state, action, environment >::env, Focal< state, action, environment >::ExtractPathToStartFromID(), and Focal< state, action, environment >::focal.

◆ ExtractPathToStartFromID()

template<class state , class action , class environment >

void Focal< state, action, environment >::ExtractPathToStartFromID	(	size_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 701 of file Focal.h.

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

◆ GetFocalItem()

template<class state , class action , class environment >

const Focal<state,action,environment>::SearchState& Focal< state, action, environment >::GetFocalItem ( unsigned int which )

inline

Definition at line 125 of file Focal.h.

References Focal< state, action, environment >::focal, and Focal< state, action, environment >::states.

◆ GetFocalListGCost()

template<class state , class action , class environment >

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

Definition at line 799 of file Focal.h.

◆ GetMemoryUsage()

template<class state , class action , class environment >

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

Return the amount of memory used by Focal.

Author: Nathan Sturtevant

Date: 03/22/06

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

Definition at line 743 of file Focal.h.

◆ GetName()

template<class state , class action , class environment >

const char * Focal< 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 242 of file Focal.h.

◆ GetNodesExpanded()

template<class state , class action , class environment >

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

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 93 of file Focal.h.

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

◆ GetNodesTouched()

template<class state , class action , class environment >

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

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 94 of file Focal.h.

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

◆ GetNumFocalItems()

template<class state , class action , class environment >

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

inline

Definition at line 119 of file Focal.h.

References Focal< state, action, environment >::focal.

◆ GetNumItems()

template<class state , class action , class environment >

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

inline

Definition at line 84 of file Focal.h.

References Focal< state, action, environment >::states.

◆ GetNumOpenItems()

template<class state , class action , class environment >

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

inline

Definition at line 118 of file Focal.h.

References Focal< state, action, environment >::open.

◆ GetOpenItem()

template<class state , class action , class environment >

const Focal<state,action,environment>::SearchState& Focal< state, action, environment >::GetOpenItem ( unsigned int which )

inline

Definition at line 120 of file Focal.h.

References Focal< state, action, environment >::open, and Focal< state, action, environment >::states.

◆ GetOpenListGCost()

template<class state , class action , class environment >

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

Definition at line 785 of file Focal.h.

References kClosedList.

◆ GetOptimalityBound()

template<class state , class action , class environment >

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

inline

Definition at line 102 of file Focal.h.

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

◆ GetParent()

template<class state , class action , class environment >

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

Definition at line 712 of file Focal.h.

◆ GetPath() [1/2]

template<class state , class action , class environment >

void Focal< 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 276 of file Focal.h.

◆ GetPath() [2/2]

template<class state , class action , class environment >

void Focal< 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 261 of file Focal.h.

◆ GetUniqueNodesExpanded()

template<class state , class action , class environment >

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

inline

Definition at line 72 of file Focal.h.

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

◆ InitializeSearch()

template<class state , class action , class environment >

bool Focal< 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 305 of file Focal.h.

◆ LogFinalStats()

template<class state , class action , class environment >

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

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 96 of file Focal.h.

◆ OpenGLDraw()

template<class state , class action , class environment >

void Focal< 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 956 of file Focal.h.

◆ PeekFocal()

template<class state , class action , class environment >

SearchState& Focal< state, action, environment >::PeekFocal ( )

inlineprivate

Definition at line 198 of file Focal.h.

References Focal< state, action, environment >::focal.

◆ PeekOpen()

template<class state , class action , class environment >

SearchState& Focal< state, action, environment >::PeekOpen ( )

inlineprivate

Definition at line 193 of file Focal.h.

References Focal< state, action, environment >::open.

◆ PrintStats()

template<class state , class action , class environment >

void Focal< 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 729 of file Focal.h.

◆ ResetNodeCount()

template<class state , class action , class environment >

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

inline

Definition at line 73 of file Focal.h.

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

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

◆ SetHeuristic()

template<class state , class action , class environment >

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

inline

Definition at line 91 of file Focal.h.

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

◆ SetOptimalityBound()

template<class state , class action , class environment >

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

inline

Definition at line 101 of file Focal.h.

References Focal< state, action, environment >::bound, and Focal< state, action, environment >::phi_focal.

Member Data Documentation

◆ bestSolution

template<class state , class action , class environment >

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

private

Definition at line 224 of file Focal.h.

◆ bound

template<class state , class action , class environment >

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

private

Definition at line 225 of file Focal.h.

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

◆ edgeCosts

template<class state , class action , class environment >

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

private

Definition at line 219 of file Focal.h.

◆ env

template<class state , class action , class environment >

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

private

Definition at line 223 of file Focal.h.

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

◆ focal

template<class state , class action , class environment >

Treap<FocalTreapItem> Focal< state, action, environment >::focal

private

Definition at line 204 of file Focal.h.

Referenced by Focal< state, action, environment >::ExtractPathToStart(), Focal< state, action, environment >::GetFocalItem(), Focal< state, action, environment >::GetNumFocalItems(), and Focal< state, action, environment >::PeekFocal().

◆ goal

template<class state , class action , class environment >

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

Definition at line 60 of file Focal.h.

◆ hash

template<class state , class action , class environment >

std::unordered_map<state, size_t> Focal< state, action, environment >::hash

private

Definition at line 206 of file Focal.h.

◆ minF

template<class state , class action , class environment >

double Focal< state, action, environment >::minF

private

Definition at line 227 of file Focal.h.

◆ neighborID

template<class state , class action , class environment >

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

private

Definition at line 218 of file Focal.h.

◆ neighborLoc

template<class state , class action , class environment >

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

private

Definition at line 220 of file Focal.h.

◆ neighbors

template<class state , class action , class environment >

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

private

Definition at line 217 of file Focal.h.

◆ nodesExpanded

template<class state , class action , class environment >

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

private

Definition at line 215 of file Focal.h.

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

◆ nodesTouched

template<class state , class action , class environment >

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

private

Definition at line 215 of file Focal.h.

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

◆ open

template<class state , class action , class environment >

Treap<OpenTreapItem> Focal< state, action, environment >::open

private

Definition at line 205 of file Focal.h.

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

◆ phi_focal

template<class state , class action , class environment >

std::function<double(double, double)> Focal< state, action, environment >::phi_focal

private

Definition at line 208 of file Focal.h.

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

◆ phi_open

template<class state , class action , class environment >

std::function<double(double, double)> Focal< state, action, environment >::phi_open

private

Definition at line 209 of file Focal.h.

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

◆ solution

template<class state , class action , class environment >

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

private

Definition at line 222 of file Focal.h.

◆ start

template<class state , class action , class environment >

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

Definition at line 60 of file Focal.h.

◆ states

template<class state , class action , class environment >

std::vector<SearchState> Focal< state, action, environment >::states

private

Definition at line 207 of file Focal.h.

Referenced by Focal< state, action, environment >::GetFocalItem(), Focal< state, action, environment >::GetNumItems(), and Focal< state, action, environment >::GetOpenItem().

◆ theHeuristic

template<class state , class action , class environment >

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

private

Definition at line 228 of file Focal.h.

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

◆ uniqueNodesExpanded

template<class state , class action , class environment >

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

private

Definition at line 226 of file Focal.h.

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

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

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

Classes

Public Types

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

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

Member Enumeration Documentation

◆ stateLoc

Constructor & Destructor Documentation

◆ Focal()

◆ ~Focal()

Member Function Documentation

◆ Add()

◆ CheckNextFocalNode()

◆ CheckNextOpenNode()

◆ DoSingleSearchStep()

◆ Draw()

◆ DrawFocal()

◆ DrawOpen()

◆ ExpandFocal()

◆ ExpandOpen()

◆ ExtractPathToStart()

◆ ExtractPathToStartFromID()

◆ GetFocalItem()

◆ GetFocalListGCost()

◆ GetMemoryUsage()

◆ GetName()

◆ GetNodesExpanded()

◆ GetNodesTouched()

◆ GetNumFocalItems()

◆ GetNumItems()

◆ GetNumOpenItems()

◆ GetOpenItem()

◆ GetOpenListGCost()

◆ GetOptimalityBound()

◆ GetParent()

◆ GetPath() [1/2]

◆ GetPath() [2/2]

◆ GetUniqueNodesExpanded()

◆ InitializeSearch()

◆ LogFinalStats()

◆ OpenGLDraw()

◆ PeekFocal()

◆ PeekOpen()

◆ PrintStats()

◆ ResetNodeCount()

◆ SetHeuristic()

◆ SetOptimalityBound()

Member Data Documentation

◆ bestSolution

◆ bound

◆ edgeCosts

◆ env

◆ focal

◆ goal

◆ hash

◆ minF

◆ neighborID

◆ neighborLoc

◆ neighbors

◆ nodesExpanded

◆ nodesTouched

◆ open

◆ phi_focal

◆ phi_open

◆ solution

◆ start

◆ states

◆ theHeuristic

◆ uniqueNodesExpanded

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