A generic focal list algorithm that returns linearly bounded solutions 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. More...

#include <FocalAdd.h>

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

[legend]

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

[legend]

Classes
struct	FocalTreapItem

struct	OpenTreapItem

struct	SearchState

Public Types
enum	stateLoc { kClosedList, kOpenList, kOpenFocalList }

Public Member Functions
	FocalAdd (double optimalBound=2)

virtual	~FocalAdd ()

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 FocalAdd< state, action, environment >::SearchState &	GetOpenItem (unsigned int which)

const FocalAdd< 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 FocalAdd< state, action, environment >

A generic focal list algorithm that returns linearly bounded solutions 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 46 of file FocalAdd.h.

Member Enumeration Documentation

◆ stateLoc

template<class state , class action , class environment >

enum FocalAdd::stateLoc

Enumerator
kClosedList
kOpenList
kOpenFocalList

Definition at line 105 of file FocalAdd.h.

Constructor & Destructor Documentation

◆ FocalAdd()

template<class state , class action , class environment >

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

inline

Definition at line 48 of file FocalAdd.h.

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

◆ ~FocalAdd()

template<class state , class action , class environment >

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

inlinevirtual

Definition at line 54 of file FocalAdd.h.

Member Function Documentation

◆ Add()

template<class state , class action , class environment >

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

private

Definition at line 832 of file FocalAdd.h.

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

◆ CheckNextFocalNode()

template<class state , class action , class environment >

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

Definition at line 782 of file FocalAdd.h.

◆ CheckNextOpenNode()

template<class state , class action , class environment >

state FocalAdd< 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 776 of file FocalAdd.h.

◆ DoSingleSearchStep()

template<class state , class action , class environment >

bool FocalAdd< 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 373 of file FocalAdd.h.

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

◆ Draw()

template<class state , class action , class environment >

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

Definition at line 965 of file FocalAdd.h.

References d, kClosedList, and kOpenList.

◆ DrawFocal()

template<class state , class action , class environment >

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

private

◆ DrawOpen()

template<class state , class action , class environment >

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

private

◆ ExpandFocal()

template<class state , class action , class environment >

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

private

Definition at line 582 of file FocalAdd.h.

References kOpenList.

◆ ExpandOpen()

template<class state , class action , class environment >

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

private

Expands a single state from the given open list.

Author: Nathan Sturtevant

Date: 01/27/19

Definition at line 496 of file FocalAdd.h.

References kClosedList.

◆ ExtractPathToStart()

template<class state , class action , class environment >

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

inline

Definition at line 67 of file FocalAdd.h.

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

◆ ExtractPathToStartFromID()

template<class state , class action , class environment >

void FocalAdd< 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 705 of file FocalAdd.h.

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

◆ GetFocalItem()

template<class state , class action , class environment >

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

inline

Definition at line 127 of file FocalAdd.h.

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

◆ GetFocalListGCost()

template<class state , class action , class environment >

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

Definition at line 803 of file FocalAdd.h.

◆ GetMemoryUsage()

template<class state , class action , class environment >

int FocalAdd< 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 747 of file FocalAdd.h.

◆ GetName()

template<class state , class action , class environment >

const char * FocalAdd< 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 244 of file FocalAdd.h.

◆ GetNodesExpanded()

template<class state , class action , class environment >

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

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 95 of file FocalAdd.h.

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

◆ GetNodesTouched()

template<class state , class action , class environment >

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

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 96 of file FocalAdd.h.

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

◆ GetNumFocalItems()

template<class state , class action , class environment >

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

inline

Definition at line 121 of file FocalAdd.h.

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

◆ GetNumItems()

template<class state , class action , class environment >

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

inline

Definition at line 86 of file FocalAdd.h.

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

◆ GetNumOpenItems()

template<class state , class action , class environment >

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

inline

Definition at line 120 of file FocalAdd.h.

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

◆ GetOpenItem()

template<class state , class action , class environment >

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

inline

Definition at line 122 of file FocalAdd.h.

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

◆ GetOpenListGCost()

template<class state , class action , class environment >

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

Definition at line 789 of file FocalAdd.h.

References kClosedList.

◆ GetOptimalityBound()

template<class state , class action , class environment >

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

inline

Definition at line 104 of file FocalAdd.h.

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

◆ GetParent()

template<class state , class action , class environment >

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

Definition at line 716 of file FocalAdd.h.

◆ GetPath() [1/2]

template<class state , class action , class environment >

void FocalAdd< 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 278 of file FocalAdd.h.

◆ GetPath() [2/2]

template<class state , class action , class environment >

void FocalAdd< 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 263 of file FocalAdd.h.

◆ GetUniqueNodesExpanded()

template<class state , class action , class environment >

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

inline

Definition at line 74 of file FocalAdd.h.

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

◆ InitializeSearch()

template<class state , class action , class environment >

bool FocalAdd< 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 307 of file FocalAdd.h.

References min().

◆ LogFinalStats()

template<class state , class action , class environment >

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

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 98 of file FocalAdd.h.

◆ OpenGLDraw()

template<class state , class action , class environment >

void FocalAdd< 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 960 of file FocalAdd.h.

◆ PeekFocal()

template<class state , class action , class environment >

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

inlineprivate

Definition at line 200 of file FocalAdd.h.

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

◆ PeekOpen()

template<class state , class action , class environment >

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

inlineprivate

Definition at line 195 of file FocalAdd.h.

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

◆ PrintStats()

template<class state , class action , class environment >

void FocalAdd< 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 733 of file FocalAdd.h.

◆ ResetNodeCount()

template<class state , class action , class environment >

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

inline

Definition at line 75 of file FocalAdd.h.

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

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

◆ SetHeuristic()

template<class state , class action , class environment >

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

inline

Definition at line 93 of file FocalAdd.h.

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

◆ SetOptimalityBound()

template<class state , class action , class environment >

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

inline

Definition at line 103 of file FocalAdd.h.

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

Member Data Documentation

◆ bestSolution

template<class state , class action , class environment >

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

private

Definition at line 226 of file FocalAdd.h.

◆ bound

template<class state , class action , class environment >

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

private

Definition at line 227 of file FocalAdd.h.

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

◆ edgeCosts

template<class state , class action , class environment >

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

private

Definition at line 221 of file FocalAdd.h.

◆ env

template<class state , class action , class environment >

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

private

Definition at line 225 of file FocalAdd.h.

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

◆ focal

template<class state , class action , class environment >

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

private

Definition at line 206 of file FocalAdd.h.

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

◆ goal

template<class state , class action , class environment >

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

Definition at line 62 of file FocalAdd.h.

◆ hash

template<class state , class action , class environment >

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

private

Definition at line 208 of file FocalAdd.h.

◆ minF

template<class state , class action , class environment >

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

private

Definition at line 229 of file FocalAdd.h.

◆ neighborID

template<class state , class action , class environment >

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

private

Definition at line 220 of file FocalAdd.h.

◆ neighborLoc

template<class state , class action , class environment >

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

private

Definition at line 222 of file FocalAdd.h.

◆ neighbors

template<class state , class action , class environment >

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

private

Definition at line 219 of file FocalAdd.h.

◆ nodesExpanded

template<class state , class action , class environment >

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

private

Definition at line 217 of file FocalAdd.h.

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

◆ nodesTouched

template<class state , class action , class environment >

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

private

Definition at line 217 of file FocalAdd.h.

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

◆ open

template<class state , class action , class environment >

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

private

Definition at line 207 of file FocalAdd.h.

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

◆ phi_focal

template<class state , class action , class environment >

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

private

Definition at line 210 of file FocalAdd.h.

◆ phi_open

template<class state , class action , class environment >

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

private

Definition at line 211 of file FocalAdd.h.

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

◆ solution

template<class state , class action , class environment >

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

private

Definition at line 224 of file FocalAdd.h.

◆ start

template<class state , class action , class environment >

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

Definition at line 62 of file FocalAdd.h.

◆ states

template<class state , class action , class environment >

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

private

Definition at line 209 of file FocalAdd.h.

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

◆ theHeuristic

template<class state , class action , class environment >

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

private

Definition at line 230 of file FocalAdd.h.

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

◆ uniqueNodesExpanded

template<class state , class action , class environment >

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

private

Definition at line 228 of file FocalAdd.h.

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

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

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

Classes

Public Types

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

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

Member Enumeration Documentation

◆ stateLoc

Constructor & Destructor Documentation

◆ FocalAdd()

◆ ~FocalAdd()

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 FocalAdd< state, action, environment >