GeneralizedMAAStarPlanner Class Reference

GeneralizedMAAStarPlanner is a class that represents the Generalized MAA* planner class. More...

#include <GeneralizedMAAStarPlanner.h>

Inheritance diagram for GeneralizedMAAStarPlanner:

Public Member Functions
	GeneralizedMAAStarPlanner (int verbose_level=0, double slack=0.0)
	(default) Constructor More...
double	GetExpectedReward () const
boost::shared_ptr< JointPolicy >	GetJointPolicy ()
boost::shared_ptr < JointPolicyDiscrete >	GetJointPolicyDiscrete ()
boost::shared_ptr < JointPolicyDiscretePure >	GetJointPolicyDiscretePure ()
LIndex	GetMaxJPolPoolSize () const
double	GetMaxLowerBound () const
LIndex	GetNrEvaluatedJPolBGs () const
GeneralizedMAAStarPlanner &	operator= (const GeneralizedMAAStarPlanner &o)
	Copy assignment operator. More...
void	Plan ()
void	SetDeadline (size_t deadlineInS)
void	SetIntermediateResultFile (std::ofstream &of)
void	SetIntermediateTimingFilename (const std::string &filename)
void	SetSaveAllBGs (const std::string &filename)
void	SetVerbose (int verbose)
	~GeneralizedMAAStarPlanner ()
	Destructor. More...
Public Member Functions inherited from TimedAlgorithm
void	AddTimedEvent (const std::string &id, clock_t duration)
	Adds event of certain duration, e.g., an external program call. More...
std::vector< double >	GetTimedEventDurations (const std::string &id)
	Returns all stored durations (in s) for a particular event. More...
void	LoadTimers (const std::string &filename)
	Load timing info from file filename. More...
void	PrintTimers () const
	Print stored timing info. More...
void	PrintTimersSummary () const
	Sums data and prints out a summary. More...
void	SaveTimers (const std::string &filename) const
	Save collected timing info to file filename. More...
void	SaveTimers (std::ofstream &of) const
	Save collected timing info to ofstream of. More...
void	StartTimer (const std::string &id) const
	Start to time an event identified by id. More...
void	StopTimer (const std::string &id) const
	Stop to time an event identified by id. More...
	TimedAlgorithm ()
	(default) Constructor More...
virtual	~TimedAlgorithm ()
	Destructor. More...

Protected Member Functions
virtual bool	ConstructAndValuateNextPolicies (const boost::shared_ptr< PartialPolicyPoolItemInterface > &ppi, const boost::shared_ptr< PartialPolicyPoolInterface > &poolOfNextPolicies, bool &cleanUpPPI)=0
	The 'NEXT' function as described in refGMAA. More...
virtual boost::shared_ptr < PartialJointPolicyDiscretePure >	ConstructExtendedJointPolicy (const PartialJointPolicyDiscretePure &jpolPrevTs, const JointPolicyDiscretePure &jpolBG, const std::vector< size_t > &nrOHts, const std::vector< Index > &firstOHtsI)=0
	Extends a previous policy jpolPrevTs to the next stage. More...
virtual Interface_ProblemToPolicyDiscretePure *	GetThisFromMostDerivedPU ()=0
	every derived class must implement this function as follows: More...
virtual boost::shared_ptr < PartialJointPolicyDiscretePure >	NewJPol () const =0
	return a new policy. More...
virtual boost::shared_ptr < PartialPolicyPoolInterface >	NewPP () const =0
	return a new policy pool. More...
virtual boost::shared_ptr < PartialPolicyPoolItemInterface >	NewPPI (const boost::shared_ptr< PartialJointPolicyDiscretePure > &p, double v) const =0
	return a new policy pool item. More...
void	Prune (PartialPolicyPoolInterface &JPVs, size_t k)
virtual void	ResetPlanner ()=0
	This should reset the planner, so it can be started from the beginning. More...
void	SelectKBestPoliciesToProcessFurther (const boost::shared_ptr< PartialPolicyPoolInterface > &poolOfNextPolicies, bool are_LBs, double bestLB, size_t k)
	Returns the k best-ranked (partial) joint policies. More...
virtual void	SelectPoliciesToProcessFurther (const boost::shared_ptr< PartialPolicyPoolInterface > &poolOfNextPolicies, bool are_LBs, double bestLB)=0
	Limits the policies to be further examined. More...
void	SetCBGbounds (const boost::shared_ptr< PartialPolicyPoolItemInterface > &ppi, const boost::shared_ptr< BayesianGameIdenticalPayoffSolver > &bgips, bool is_last_ts, double discount)

Protected Attributes
std::string	_m_bgBaseFilename
size_t	_m_bgCounter
std::vector< size_t >	_m_expanded_childs
	_m_expanded_childs[t] contains the number of child nodes that were expanded 'at stage t'. More...
std::ofstream *	_m_intermediateResultFile
	Pointer to an file stream to store the intermediate (timing) results. More...
std::string	_m_intermediateTimingFilename
std::vector< LIndex >	_m_max_expanded_childs
LIndex	_m_nrJPolBGsEvaluated
size_t	_m_nrPoliciesToProcess
std::vector < BayesianGameForDecPOMDPStage * >	_m_pointersToAllBGTS
bool	_m_saveIntermediateTiming
double	_m_slack
	when the heuristic is not admissible, or the past reward is an approximation, we may add some slack such that good policies are not pruned More...
bool	_m_useSparseBeliefs
int	_m_verboseness
	the level of verboseness, default=0, >0 verbose, <0 silent More...

Private Member Functions
void	Initialize ()
	Initialize the planner. More...

Private Attributes
size_t	_m_deadline
double	_m_expectedRewardFoundPolicy
	the expected reward of the best found policy More...
boost::shared_ptr < JointPolicyDiscretePure >	_m_foundPolicy
	the best found policy More...
LIndex	_m_maxJPolPoolSize
	a counter that maintains the maximum size of the policy pool during the planning process. More...
double	_m_maxLowerBound
	The highest lowerbound found so far. More...

Detailed Description

GeneralizedMAAStarPlanner is a class that represents the Generalized MAA* planner class.

This implements GMAA pretty much as described in refGMAA (see DOC-References.h). The 'NEXT' as described in refGMAA, is called 'ConstructAndValuateNextPolicies'.

Additionally there is a function 'SelectPoliciesToProcessFurther'. (not to be confused with the 'SELECT' function from refGMAA !!!) Given the result of ConstructAndValuateNextPolicies, SelectPoliciesToProcessFurther determines which of these will actually be added to the policy pool. I.e., ConstructAndValuateNextPolicies and SelectPoliciesToProcessFurther together form 'NEXT'.

The 'SELECT' function as described in refGMAA is implemented by the policy pool (see PartialPolicyPoolInterface) itself.

See also

GMAA_MAAstar, GMAA, PartialPolicyPoolInterface

Constructor & Destructor Documentation

GeneralizedMAAStarPlanner::GeneralizedMAAStarPlanner	(	int	verbose_level = 0,
		double	slack = 0.0
	)

(default) Constructor

References _m_bgBaseFilename, _m_bgCounter, _m_intermediateResultFile, _m_nrJPolBGsEvaluated, _m_nrPoliciesToProcess, and _m_saveIntermediateTiming.

GeneralizedMAAStarPlanner::~GeneralizedMAAStarPlanner

(

)

Destructor.

Member Function Documentation

virtual bool GeneralizedMAAStarPlanner::ConstructAndValuateNextPolicies ( const boost::shared_ptr< PartialPolicyPoolItemInterface > &  ppi, const boost::shared_ptr< PartialPolicyPoolInterface > &  poolOfNextPolicies, bool &  cleanUpPPI  )

protectedpure virtual

The 'NEXT' function as described in refGMAA.

The function that from a given <jpol,val> pair construct a new (ordered by value->priority_queue) set of joint policies. This function should be overriden in derived classes to get different planning behavior.

Implemented in GMAA_kGMAACluster, GMAA_MAAstarCluster, GMAA_MAAstar, GMAA_MAA_ELSI, GMAA_kGMAA, and GMAA_MAAstarClassic.

Referenced by Plan().

virtual boost::shared_ptr<PartialJointPolicyDiscretePure> GeneralizedMAAStarPlanner::ConstructExtendedJointPolicy ( const PartialJointPolicyDiscretePure &  jpolPrevTs, const JointPolicyDiscretePure &  jpolBG, const std::vector< size_t > &  nrOHts, const std::vector< Index > &  firstOHtsI  )

protectedpure virtual

Extends a previous policy jpolPrevTs to the next stage.

This function extends a previous policy jpolPrevTs for ts-1 with the behavior specified by the policy of the BayesianGame for time step ts (jpolBG). jpolPrevTs - a joint policy for the DecPOMDP up to time step ts-1 (i.e. with depth=ts-2) jpolBG - a joint policy for the BayesianGame for time step ts. nrOHts - a vector that specifies the number of observation histories for eac agents at time step ts. firstOHtsI - a vector that specifies the index of the first observation history in time step ts for each agent (this functions as the offset in the conversion BG->DecPOMDP index conversion).

returns a new JointPolicyPureVector (so it must be explicitly deleted)

Implemented in GeneralizedMAAStarPlannerForFactoredDecPOMDPDiscrete, and GeneralizedMAAStarPlannerForDecPOMDPDiscrete.

double GeneralizedMAAStarPlanner::GetExpectedReward ( void  ) const

inline

Referenced by GeneralizedMAAStarPlannerForDecPOMDPDiscrete::GetExpectedReward(), and GeneralizedMAAStarPlannerForFactoredDecPOMDPDiscrete::GetExpectedReward().

boost::shared_ptr< JointPolicy > GeneralizedMAAStarPlanner::GetJointPolicy

(

void

)

References _m_foundPolicy.

Referenced by GeneralizedMAAStarPlannerForDecPOMDPDiscrete::GetJointPolicy(), and GeneralizedMAAStarPlannerForFactoredDecPOMDPDiscrete::GetJointPolicy().

boost::shared_ptr< JointPolicyDiscrete > GeneralizedMAAStarPlanner::GetJointPolicyDiscrete

(

void

)

References _m_foundPolicy.

JPDP_sharedPtr GeneralizedMAAStarPlanner::GetJointPolicyDiscretePure

(

)

References _m_foundPolicy.

LIndex GeneralizedMAAStarPlanner::GetMaxJPolPoolSize ( ) const

inline

double GeneralizedMAAStarPlanner::GetMaxLowerBound ( ) const

inline

Referenced by SetCBGbounds().

LIndex GeneralizedMAAStarPlanner::GetNrEvaluatedJPolBGs ( ) const

inline

References _m_nrJPolBGsEvaluated.

virtual Interface_ProblemToPolicyDiscretePure* GeneralizedMAAStarPlanner::GetThisFromMostDerivedPU ( )

protectedpure virtual

every derived class must implement this function as follows:

GetThisFromMostDerivedPU() { return this; } Giving us access to the Interface_ProblemToPolicyDiscretePure in this base class.

Implemented in GeneralizedMAAStarPlannerForFactoredDecPOMDPDiscrete, GeneralizedMAAStarPlannerForDecPOMDPDiscrete, GMAA_kGMAACluster, and GMAA_MAAstarCluster.

Referenced by Plan().

void GeneralizedMAAStarPlanner::Initialize ( )

private

Initialize the planner.

Call the ResetPlanner() of the derived planners.

References _m_bgCounter, _m_expanded_childs, _m_expectedRewardFoundPolicy, _m_foundPolicy, _m_max_expanded_childs, _m_maxJPolPoolSize, _m_maxLowerBound, _m_pointersToAllBGTS, and ResetPlanner().

Referenced by Plan().

virtual boost::shared_ptr<PartialJointPolicyDiscretePure> GeneralizedMAAStarPlanner::NewJPol ( ) const

protectedpure virtual

return a new policy.

Different versions of GMAA may make use of different implementations of policies. This function must be implemented by a derived class and return a pointer to a newly created PolicyPoolItem object. This way,the derived class can determine the implementation of the policy.

it returns a pointer to a PartialJointPolicyDiscretePure that is created by 'new' therefore, do not forget to 'delete'!!

Implemented in GMAA_kGMAACluster, GMAA_MAAstarCluster, GeneralizedMAAStarPlannerForFactoredDecPOMDPDiscrete, and GeneralizedMAAStarPlannerForDecPOMDPDiscrete.

Referenced by Plan().

virtual boost::shared_ptr<PartialPolicyPoolInterface> GeneralizedMAAStarPlanner::NewPP ( ) const

protectedpure virtual

return a new policy pool.

this function must be implemented by a derived class and return a pointer to a PartialPolicyPoolInterface object. This way,the derived class can determine the implementation of the policy pools used and thus the 'SELECT' functions as described in refGMAA.

it returns a pointer to a PartialPolicyPoolInterface that is created by 'new' therefore, do not forget to 'delete'!!

Implemented in GeneralizedMAAStarPlannerForFactoredDecPOMDPDiscrete, and GeneralizedMAAStarPlannerForDecPOMDPDiscrete.

Referenced by Plan(), Prune(), and SelectKBestPoliciesToProcessFurther().

virtual boost::shared_ptr<PartialPolicyPoolItemInterface> GeneralizedMAAStarPlanner::NewPPI ( const boost::shared_ptr< PartialJointPolicyDiscretePure > &  p, double  v  ) const

protectedpure virtual

return a new policy pool item.

This function must be implemented by a derived class and return a pointer to a newly created PolicyPoolItem object. This way,the derived class can determine the implementation of the policy pools used and thus the 'SELECT' functions as described in refGMAA.

it returns a pointer to a PartialPolicyPoolInterface that is created by 'new' therefore, do not forget to 'delete'!!Overloaded form of NewPP().

Creates a PartialPolicyPoolItemInterface which contains joint policy p, with value v.

Implemented in GMAA_kGMAACluster, GMAA_MAAstarCluster, GMAA_MAAstar, GMAA_kGMAA, GMAA_MAAstarClassic, GeneralizedMAAStarPlannerForFactoredDecPOMDPDiscrete, and GeneralizedMAAStarPlannerForDecPOMDPDiscrete.

GeneralizedMAAStarPlanner & GeneralizedMAAStarPlanner::operator=

(

const GeneralizedMAAStarPlanner &

o

)

Copy assignment operator.

void GeneralizedMAAStarPlanner::Plan

(

)

References _m_deadline, _m_expanded_childs, _m_expectedRewardFoundPolicy, _m_foundPolicy, _m_intermediateResultFile, _m_intermediateTimingFilename, _m_max_expanded_childs, _m_maxJPolPoolSize, _m_maxLowerBound, _m_saveIntermediateTiming, _m_slack, _m_verboseness, ConstructAndValuateNextPolicies(), DEBUG_GMAA4, GetThisFromMostDerivedPU(), Initialize(), NewJPol(), NewPP(), TimedAlgorithm::SaveTimers(), SelectPoliciesToProcessFurther(), PrintTools::SoftPrintVector(), TimedAlgorithm::StartTimer(), and TimedAlgorithm::StopTimer().

Referenced by GeneralizedMAAStarPlannerForDecPOMDPDiscrete::Plan(), and GeneralizedMAAStarPlannerForFactoredDecPOMDPDiscrete::Plan().

void GeneralizedMAAStarPlanner::Prune ( PartialPolicyPoolInterface &  JPVs, size_t  k  )

protected

References PartialPolicyPoolInterface::GetBestRanked(), NewPP(), PartialPolicyPoolInterface::PopBestRanked(), and PartialPolicyPoolInterface::Size().

virtual void GeneralizedMAAStarPlanner::ResetPlanner ( )

protectedpure virtual

This should reset the planner, so it can be started from the beginning.

Implemented in GMAA_kGMAACluster, GMAA_MAAstarCluster, GMAA_MAAstar, GMAA_kGMAA, GMAA_MAAstarClassic, and GMAA_MAA_ELSI.

Referenced by Initialize().

void GeneralizedMAAStarPlanner::SelectKBestPoliciesToProcessFurther ( const boost::shared_ptr< PartialPolicyPoolInterface > &  poolOfNextPolicies, bool  are_LBs, double  bestLB, size_t  k  )

protected

Returns the k best-ranked (partial) joint policies.

An implementation of the 'SELECT' function, that returns the k (partial) joint policies with the highest heuristic values.

References NewPP().

Referenced by GMAA_kGMAA::SelectPoliciesToProcessFurther(), and GMAA_kGMAACluster::SelectPoliciesToProcessFurther().

virtual void GeneralizedMAAStarPlanner::SelectPoliciesToProcessFurther ( const boost::shared_ptr< PartialPolicyPoolInterface > &  poolOfNextPolicies, bool  are_LBs, double  bestLB  )

protectedpure virtual

Limits the policies to be further examined.

Of the <jpol,val> pairs found by ConstructAndValuateNextPolicies, we may not want to process all of them further. This function performs a selection. This function should be overriden in derived classes to get different planning behavior.

Implemented in GMAA_kGMAACluster, GMAA_MAAstarCluster, GMAA_MAAstar, GMAA_kGMAA, GMAA_MAAstarClassic, and GMAA_MAA_ELSI.

Referenced by Plan().

void GeneralizedMAAStarPlanner::SetCBGbounds ( const boost::shared_ptr< PartialPolicyPoolItemInterface > &  ppi, const boost::shared_ptr< BayesianGameIdenticalPayoffSolver > &  bgips, bool  is_last_ts, double  discount  )

inlineprotected

References GetMaxLowerBound().

Referenced by GeneralizedMAAStarPlannerForDecPOMDPDiscrete::SetCBGbounds(), and GeneralizedMAAStarPlannerForFactoredDecPOMDPDiscrete::SetCBGbounds().

void GeneralizedMAAStarPlanner::SetDeadline

(

size_t

deadlineInS

)

References _m_deadline, and _m_verboseness.

void GeneralizedMAAStarPlanner::SetIntermediateResultFile ( std::ofstream &  of )

inline

void GeneralizedMAAStarPlanner::SetIntermediateTimingFilename

(

const std::string &

filename

)

References _m_intermediateTimingFilename, and _m_saveIntermediateTiming.

void GeneralizedMAAStarPlanner::SetSaveAllBGs ( const std::string &  filename )

inline

void GeneralizedMAAStarPlanner::SetVerbose

(

int

verbose

)

References _m_verboseness.

Member Data Documentation

std::string GeneralizedMAAStarPlanner::_m_bgBaseFilename

protected

Referenced by GMAA_MAA_ELSI::CAVNP_quick_n_dirty2(), GMAA_MAAstarClassic::ConstructAndValuateNextPolicies(), GMAA_kGMAA::ConstructAndValuateNextPolicies(), GMAA_MAAstar::ConstructAndValuateNextPolicies(), GMAA_MAAstarCluster::ConstructAndValuateNextPolicies(), GMAA_MAA_ELSI::ConstructBayesianGame(), and GeneralizedMAAStarPlanner().

size_t GeneralizedMAAStarPlanner::_m_bgCounter

protected

Referenced by GMAA_MAA_ELSI::CAVNP_quick_n_dirty2(), GMAA_MAAstarClassic::ConstructAndValuateNextPolicies(), GMAA_kGMAA::ConstructAndValuateNextPolicies(), GMAA_MAAstar::ConstructAndValuateNextPolicies(), GMAA_MAAstarCluster::ConstructAndValuateNextPolicies(), GMAA_MAA_ELSI::ConstructBayesianGame(), GeneralizedMAAStarPlanner(), and Initialize().

size_t GeneralizedMAAStarPlanner::_m_deadline

private

Referenced by Plan(), and SetDeadline().

std::vector<size_t> GeneralizedMAAStarPlanner::_m_expanded_childs

protected

_m_expanded_childs[t] contains the number of child nodes that were expanded 'at stage t'.

That means

selected parent of depth t = ^t -> child has depth t+1 = (varphi^t, ^t) (so the child nodes are depth t+1 !)

Referenced by Initialize(), and Plan().

double GeneralizedMAAStarPlanner::_m_expectedRewardFoundPolicy

private

the expected reward of the best found policy

Referenced by Initialize(), and Plan().

boost::shared_ptr<JointPolicyDiscretePure> GeneralizedMAAStarPlanner::_m_foundPolicy

private

the best found policy

Referenced by GetJointPolicy(), GetJointPolicyDiscrete(), GetJointPolicyDiscretePure(), Initialize(), and Plan().

std::ofstream* GeneralizedMAAStarPlanner::_m_intermediateResultFile

protected

Pointer to an file stream to store the intermediate (timing) results.

Referenced by GeneralizedMAAStarPlanner(), and Plan().

std::string GeneralizedMAAStarPlanner::_m_intermediateTimingFilename

protected

Referenced by Plan(), and SetIntermediateTimingFilename().

std::vector<LIndex> GeneralizedMAAStarPlanner::_m_max_expanded_childs

protected

Referenced by Initialize(), and Plan().

LIndex GeneralizedMAAStarPlanner::_m_maxJPolPoolSize

private

a counter that maintains the maximum size of the policy pool during the planning process.

Referenced by Initialize(), and Plan().

double GeneralizedMAAStarPlanner::_m_maxLowerBound

private

The highest lowerbound found so far.

Referenced by Initialize(), and Plan().

LIndex GeneralizedMAAStarPlanner::_m_nrJPolBGsEvaluated

protected

Referenced by GMAA_MAAstarClassic::ConstructAndValuateNextPolicies(), GMAA_MAA_ELSI::ConstructAndValuateNextPoliciesExactBG(), GeneralizedMAAStarPlanner(), and GetNrEvaluatedJPolBGs().

size_t GeneralizedMAAStarPlanner::_m_nrPoliciesToProcess

protected

Referenced by GMAA_kGMAA::ConstructAndValuateNextPolicies(), GMAA_kGMAACluster::ConstructAndValuateNextPolicies(), GeneralizedMAAStarPlanner(), GMAA_kGMAA::GMAA_kGMAA(), GMAA_kGMAACluster::GMAA_kGMAACluster(), GMAA_kGMAA::SelectPoliciesToProcessFurther(), and GMAA_kGMAACluster::SelectPoliciesToProcessFurther().

std::vector<BayesianGameForDecPOMDPStage*> GeneralizedMAAStarPlanner::_m_pointersToAllBGTS

protected

Referenced by Initialize().

bool GeneralizedMAAStarPlanner::_m_saveIntermediateTiming

protected

Referenced by GeneralizedMAAStarPlanner(), Plan(), and SetIntermediateTimingFilename().

double GeneralizedMAAStarPlanner::_m_slack

protected

when the heuristic is not admissible, or the past reward is an approximation, we may add some slack such that good policies are not pruned

Referenced by Plan().

bool GeneralizedMAAStarPlanner::_m_useSparseBeliefs

protected

Referenced by GeneralizedMAAStarPlannerForDecPOMDPDiscrete::GeneralizedMAAStarPlannerForDecPOMDPDiscrete(), and GeneralizedMAAStarPlannerForFactoredDecPOMDPDiscrete::GeneralizedMAAStarPlannerForFactoredDecPOMDPDiscrete().

int GeneralizedMAAStarPlanner::_m_verboseness

protected

the level of verboseness, default=0, >0 verbose, <0 silent

Referenced by GMAA_MAA_ELSI::CAVNP_quick_n_dirty2(), GMAA_MAAstarClassic::ConstructAndValuateNextPolicies(), GMAA_MAAstar::ConstructAndValuateNextPolicies(), GMAA_MAAstarCluster::ConstructAndValuateNextPolicies(), GMAA_kGMAACluster::ConstructAndValuateNextPolicies(), GMAA_MAA_ELSI::ConstructAndValuateNextPoliciesExactBG(), GMAA_MAA_ELSI::ConstructBayesianGame(), Plan(), SetDeadline(), and SetVerbose().