MultiAgentDecisionProcess
|
BGIP_SolverBranchAndBound is a class that performs Branch-and-Bound search for identical payoff Bayesian Games. More...
#include <BGIP_SolverBranchAndBound.h>
Public Member Functions | |
BGIP_SolverBranchAndBound (const boost::shared_ptr< const BayesianGameIdenticalPayoffInterface > &bg, int verbose=0, size_t nrDesiredSolutions=1, bool expandAll=false, BGIP_BnB::BnB_JointTypeOrdering jtOrdering=BGIP_BnB::IdentityMapping, bool reComputeHeur=false) | |
Constructor. More... | |
bool | GetNextJointPolicyAndValueSpecific (boost::shared_ptr< JointPolicyDiscretePure > &jpol, double &value) |
The specific implementation that should be implemented by the derived class: More... | |
size_t | GetNrNodesExpanded () const |
bool | IsExactSolver () const |
Methods should indicated whether they compute exact (optimal) solutions or not. More... | |
void | SetCBGlowerBound (double lowerbound) |
void | SetCBGupperBound (double upperbound) |
double | Solve () |
The methods that performs the planning. More... | |
~BGIP_SolverBranchAndBound () | |
Public Member Functions inherited from BGIP_IncrementalSolverInterface_T< JP > | |
BGIP_IncrementalSolverInterface_T (const boost::shared_ptr< const BayesianGameIdenticalPayoffInterface > &bg, size_t nrDesiredSolutions=INT_MAX) | |
virtual boost::shared_ptr < JointPolicyDiscretePure > | GetNewJpol () const |
this gives a implementation of GetNewJpol (specified in BayesianGameIdenticalPayoffSolver) More... | |
Public Member Functions inherited from BGIP_IncrementalSolverInterface | |
bool | AllSolutionsHaveBeenReturned () const |
BGIP_IncrementalSolverInterface (const boost::shared_ptr< const BayesianGameIdenticalPayoffInterface > &bg, size_t nrDesiredSolutions=INT_MAX) | |
bool | GetNextJointPolicyAndValue (boost::shared_ptr< JointPolicyDiscretePure > &jpol, double &value) |
Gets the next solution from the Incremental CBG solver. More... | |
virtual | ~BGIP_IncrementalSolverInterface () |
Public Member Functions inherited from BayesianGameIdenticalPayoffSolver | |
void | AddSolution (const JointPolicyPureVector &jp, double value) |
void | AddSolution (const JointPolicyPureVectorForClusteredBG &jp, double value) |
void | AddSolution (LIndex jpolIndex, double value) |
BayesianGameIdenticalPayoffSolver (const boost::shared_ptr< const BayesianGameIdenticalPayoffInterface > &bg, size_t nrDesiredSolutions=1) | |
(default) Constructor More... | |
double | Evaluate (const JointPolicyPureVector &jpolBG) const |
double | Evaluate (const JointPolicyPureVectorForClusteredBG &jpolBG) const |
boost::shared_ptr< const BayesianGameIdenticalPayoffInterface > | GetBGIPI () const |
double | GetExpectedReward () const |
const boost::shared_ptr < JointPolicy > | GetJointPolicy () const |
const JointPolicyPureVector & | GetJointPolicyPureVector () const |
boost::shared_ptr< JPPVValuePair > | GetNextSolutionJPPV () const |
boost::shared_ptr < PartialJPDPValuePair > | GetNextSolutionPJPDP () const |
size_t | GetNrDesiredSolutions () const |
size_t | GetNrFoundSolutions () const |
Gets the found number of solutions. More... | |
double | GetPayoff () const |
std::ofstream * | GetResultsOFStream () const |
std::ofstream * | GetTimingsOFStream () const |
bool | GetWriteAnyTimeResults () const |
bool | IsEmptyJPPV () const |
bool | IsEmptyPJPDP () const |
void | PopNextSolutionJPPV () |
void | PopNextSolutionPJPDP () |
void | SaveSolution (const std::string &filename) const |
void | SetAnyTimeResults (bool turn_on, std::ofstream *results, std::ofstream *timings) |
Turns Anytime results on and of. More... | |
virtual void | SetDeadline (double deadlineInSeconds) |
To limit the amount of time the solver uses. More... | |
void | SetNrDesiredSolutions (size_t n) |
Gets the desired number of solutions to be returned. More... | |
std::string | SoftPrintSolution () const |
virtual | ~BayesianGameIdenticalPayoffSolver () |
Destructor. More... | |
Private Member Functions | |
void | ComputeCompleteInformationValues () |
Computes the "complete information" heuristic values for all joint types. More... | |
std::vector< double > | ComputeMinContributionValues () const |
void | ComputeValidJointActionExtensions (BGIP_BnB_NodePtr node, std::vector< Index > &valid_JAs) |
returns std::vector with all joint action indices that are valid. More... | |
void | ComputeValidJointActions (Index jt_bgI, std::vector< Index > &valid_JAs, BGIP_BnB_NodePtr node) |
the following computes the valid joint actions for jt_bgI. More... | |
void | ComputeValidJointActionsOld (BGIP_BnB_NodePtr node, Index jt_bgI, std::vector< Index > &valid_JAs) |
computes the valid joint actions in a slow manner but always works correctly. More... | |
double | ComputeValueOfFullySpecifiedPolicy (BGIP_BnB_NodePtr node) |
void | ConvertNodeToPolicyAndAddToSolution (BGIP_BnB_NodePtr node, double value) |
void | Expand (BGIP_BnB_NodePtr node, Index JA) |
void | ExpandAllExtensions (BGIP_BnB_NodePtr node) |
void | GenerateJointActions (const std::vector< Index > &valid_action_set, std::vector< Index > &curr_JA, std::vector< Index > &valid_JAs, Index agentI) |
void | GenerateJointActions_ProcessAction (const std::vector< Index > &valid_action_set, std::vector< Index > &curr_JA, std::vector< Index > &valid_JAs, Index agentI, Index actionI) |
double | GetContribution (Index jtI, Index jaI) const |
Get the contribution of a (joint type,joint action) pair. More... | |
Index | GetDepthFirstSpecified (Index agentI, Index typeI, BGIP_BnB_NodePtr node) const |
Index | GetJTIndexMapping (Index i, BGIP_BnB_NodePtr node) const |
Returns the i-th joint type for which a joint action will be selected. More... | |
double | GetPerJPRatio (size_t s) const |
void | Pop (BGIP_BnB_NodePtr node) |
void | PopAndDeleteNode (BGIP_BnB_NodePtr node) |
void | PrintStatistics (Index i) const |
void | ProcessFullySpecifiedNode (BGIP_BnB_NodePtr node) |
void | Prune (double value) |
void | ReComputeH (BGIP_BnB_NodePtr node) |
void | ReOrderJointTypes (std::vector< Index > &jtIndexMapping) |
void | ReOrderJointTypes (const std::vector< Index > &origJTIndexMapping, const std::vector< double > &origValues, const std::vector< double > &orderedValues, std::vector< Index > &jtIndexMapping) const |
Orders the joint type mapping origJTIndexMapping (with values origValues) according to orderValues. More... | |
double | ReSolve () |
void | SortAscending (std::vector< double > &values) const |
Sorts a std::vector in ascending order. More... | |
void | SortDescending (std::vector< double > &values) const |
Sorts a std::vector in descending order. More... | |
Private Attributes | |
BGIP_BnB_NodePtr | _m_bestNode |
the best node found so far... More... | |
boost::shared_ptr< const BayesianGameIdenticalPayoffInterface > | _m_bgip |
Pointer to the BG we're solving. More... | |
double | _m_CBGlowerBound |
double | _m_CBGupperBound |
std::vector< double > | _m_completeInformationValues |
std::vector< std::vector< Index > > | _m_depthFirstSpecified |
_m_depthFirstSpecified[agentI][typeI] specifies at what depth typeI of agentI is first specified. More... | |
bool | _m_expandAll |
std::vector< std::vector< Index > > | _m_jaToIndCache |
std::vector< Index > | _m_jtIndexMapping |
_m_jtIndexMapping[i] the i-th joint type for which a joint action will be selected, _m_jtIndexMapping[i] = j means that the j-th joint-type of the BG will be the i-th for which a . More... | |
BGIP_BnB::BnB_JointTypeOrdering | _m_jtOrdering |
The ordering of joint types used in the search. More... | |
Index | _m_maxDepth |
the maximum depth of a search node (i.e., the depth at which it is fully More... | |
double | _m_maxLowerBound |
const std::vector< size_t > & | _m_nrActions |
size_t | _m_nrAgents |
size_t | _m_nrJTs |
size_t | _m_nrNodesExpanded |
size_t | _m_nrNodesFullySpecified |
size_t | _m_nrNodesPruned |
size_t | _m_nrSolutionsComputed |
The number of solutions we already computed for the incremental solver. More... | |
std::priority_queue < BGIP_BnB_NodePtr > * | _m_openQueue |
The priority queue keeping track of all the open nodes in the search. More... | |
bool | _m_reComputeH |
bool | _m_reComputeJTIndexMapping |
bool | _m_solved |
Whether we already called Solve(). More... | |
int | _m_verbosity |
Level of verboseness of the solver. More... | |
Additional Inherited Members | |
Protected Member Functions inherited from BayesianGameIdenticalPayoffSolver | |
virtual void | CheckDeadline (const std::string &errorMessage) const |
Checks whether the deadline has expired. Throws EDeadline. More... | |
virtual void | InitDeadline () |
Should be called at the beginning of Solve(). More... | |
Protected Attributes inherited from BGIP_IncrementalSolverInterface | |
size_t | _m_nrSolutionsReturned |
The number of solutions we already returned (not computed) More... | |
BGIP_SolverBranchAndBound is a class that performs Branch-and-Bound search for identical payoff Bayesian Games.
The template argument JP represents the joint policy class the solver should return.
|
inline |
Constructor.
Directly Associates a problem with the planner Information regarding the problem is used to construct a joint policy of the proper shape.
References BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BGIP_BnB::ConsistentMaxContribution, BGIP_BnB::ConsistentMaxContributionDifference, BGIP_BnB::ConsistentMinContribution, and BGIP_BnB::UNSPECIFIED_ACTION.
|
inline |
References BGIP_SolverBranchAndBound< JP >::_m_openQueue.
|
inlineprivate |
Computes the "complete information" heuristic values for all joint types.
References BayesianGameIdenticalPayoffSolver::CheckDeadline(), BGIP_SolverBranchAndBound< JP >::GetContribution(), and PrintTools::SoftPrintVector().
Referenced by BGIP_SolverBranchAndBound< JP >::Solve().
|
inlineprivate |
References BGIP_SolverBranchAndBound< JP >::GetContribution(), and PrintTools::SoftPrintVector().
Referenced by BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes().
|
inlineprivate |
returns std::vector with all joint action indices that are valid.
References BGIP_SolverBranchAndBound< JP >::ComputeValidJointActions(), BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionsOld(), VectorTools::Equal(), BGIP_SolverBranchAndBound< JP >::GetJTIndexMapping(), and PrintTools::SoftPrintVector().
Referenced by BGIP_SolverBranchAndBound< JP >::ExpandAllExtensions().
|
inlineprivate |
the following computes the valid joint actions for jt_bgI.
when CACHE_IMPLIED_JPOL is true, it simply uses the cached implied policy: valid_action_set[agI] = _m_impliedJPol[agI][tI]; to determine the valid actions for each agent.
References BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BGIP_SolverBranchAndBound< JP >::GenerateJointActions(), BGIP_SolverBranchAndBound< JP >::GetDepthFirstSpecified(), PrintTools::SoftPrintVector(), and BGIP_BnB::UNSPECIFIED_ACTION.
Referenced by BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionExtensions(), and BGIP_SolverBranchAndBound< JP >::ReComputeH().
|
inlineprivate |
computes the valid joint actions in a slow manner but always works correctly.
References BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BGIP_SolverBranchAndBound< JP >::GetDepthFirstSpecified(), and BGIP_BnB::UNSPECIFIED_ACTION.
Referenced by BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionExtensions().
|
inlineprivate |
|
inlineprivate |
References BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BayesianGameIdenticalPayoffSolver::AddSolution(), BGIP_SolverBranchAndBound< JP >::GetDepthFirstSpecified(), and BGIP_IncrementalSolverInterface_T< JP >::GetNewJpol().
Referenced by BGIP_SolverBranchAndBound< JP >::ProcessFullySpecifiedNode().
|
inlineprivate |
|
inlineprivate |
|
inlineprivate |
|
inlineprivate |
Get the contribution of a (joint type,joint action) pair.
Referenced by BGIP_SolverBranchAndBound< JP >::ComputeCompleteInformationValues(), BGIP_SolverBranchAndBound< JP >::ComputeMinContributionValues(), BGIP_SolverBranchAndBound< JP >::ComputeValueOfFullySpecifiedPolicy(), BGIP_SolverBranchAndBound< JP >::Expand(), and BGIP_SolverBranchAndBound< JP >::ReComputeH().
|
inlineprivate |
|
inlineprivate |
Returns the i-th joint type for which a joint action will be selected.
Referenced by BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionExtensions(), BGIP_SolverBranchAndBound< JP >::ComputeValueOfFullySpecifiedPolicy(), and BGIP_SolverBranchAndBound< JP >::ReComputeH().
|
inlinevirtual |
The specific implementation that should be implemented by the derived class:
Implements BGIP_IncrementalSolverInterface.
References BayesianGameIdenticalPayoffSolver::GetNextSolutionJPPV(), BayesianGameIdenticalPayoffSolver::GetNextSolutionPJPDP(), BayesianGameIdenticalPayoffSolver::GetNrFoundSolutions(), BayesianGameIdenticalPayoffSolver::IsEmptyJPPV(), BayesianGameIdenticalPayoffSolver::IsEmptyPJPDP(), BayesianGameIdenticalPayoffSolver::PopNextSolutionJPPV(), BayesianGameIdenticalPayoffSolver::PopNextSolutionPJPDP(), BGIP_SolverBranchAndBound< JP >::ReSolve(), and BGIP_SolverBranchAndBound< JP >::Solve().
|
inline |
|
inlineprivate |
References Globals::CastLIndexToDouble().
Referenced by BGIP_SolverBranchAndBound< JP >::PrintStatistics(), and BGIP_SolverBranchAndBound< JP >::ReSolve().
|
inlinevirtual |
Methods should indicated whether they compute exact (optimal) solutions or not.
Implements BayesianGameIdenticalPayoffSolver.
|
inlineprivate |
|
inlineprivate |
|
inlineprivate |
References BGIP_SolverBranchAndBound< JP >::GetPerJPRatio(), and PRINTNUM.
Referenced by BGIP_SolverBranchAndBound< JP >::ReSolve().
|
inlineprivate |
References BGIP_SolverBranchAndBound< JP >::ComputeValueOfFullySpecifiedPolicy(), BGIP_SolverBranchAndBound< JP >::ConvertNodeToPolicyAndAddToSolution(), BayesianGameIdenticalPayoffSolver::GetNrDesiredSolutions(), BGIP_SolverBranchAndBound< JP >::Pop(), BGIP_SolverBranchAndBound< JP >::PopAndDeleteNode(), and BGIP_SolverBranchAndBound< JP >::Prune().
Referenced by BGIP_SolverBranchAndBound< JP >::ReSolve().
|
inlineprivate |
|
inlineprivate |
References BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BGIP_SolverBranchAndBound< JP >::ComputeValidJointActions(), BGIP_BnB::ConsistentMaxContribution, BGIP_BnB::ConsistentMaxContributionDifference, BGIP_BnB::ConsistentMinContribution, BGIP_SolverBranchAndBound< JP >::GetContribution(), BGIP_SolverBranchAndBound< JP >::GetJTIndexMapping(), BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes(), PrintTools::SoftPrintVector(), BGIP_SolverBranchAndBound< JP >::SortDescending(), and BGIP_BnB::UNSPECIFIED_ACTION.
Referenced by BGIP_SolverBranchAndBound< JP >::Expand().
|
inlineprivate |
References BGIP_SolverBranchAndBound< JP >::_m_completeInformationValues, BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BGIP_BnB::BasisTypes, BGIP_SolverBranchAndBound< JP >::ComputeMinContributionValues(), BGIP_BnB::ConsistentMaxContribution, BGIP_BnB::ConsistentMaxContributionDifference, BGIP_BnB::ConsistentMinContribution, BGIP_BnB::DescendingProbability, BGIP_BnB::IdentityMapping, BGIP_BnB::MaxContribution, BGIP_BnB::MaxContributionDifference, BGIP_BnB::MinContribution, PrintTools::SoftPrintVector(), BGIP_SolverBranchAndBound< JP >::SortAscending(), BGIP_SolverBranchAndBound< JP >::SortDescending(), and BGIP_BnB::UNSPECIFIED_ACTION.
Referenced by BGIP_SolverBranchAndBound< JP >::ReComputeH(), and BGIP_SolverBranchAndBound< JP >::Solve().
|
inlineprivate |
Orders the joint type mapping origJTIndexMapping (with values origValues) according to orderValues.
References BGIP_BnB::UNSPECIFIED_ACTION.
|
inlineprivate |
References BGIP_SolverBranchAndBound< JP >::_m_CBGlowerBound, BayesianGameIdenticalPayoffSolver::CheckDeadline(), BGIP_SolverBranchAndBound< JP >::ExpandAllExtensions(), BayesianGameIdenticalPayoffSolver::GetBGIPI(), BayesianGameIdenticalPayoffSolver::GetNrDesiredSolutions(), BayesianGameIdenticalPayoffSolver::GetNrFoundSolutions(), BayesianGameIdenticalPayoffSolver::GetPayoff(), BGIP_SolverBranchAndBound< JP >::GetPerJPRatio(), BGIP_SolverBranchAndBound< JP >::PrintStatistics(), Globals::PROB_PRECISION, BGIP_SolverBranchAndBound< JP >::ProcessFullySpecifiedNode(), and PrintTools::SoftPrintVector().
Referenced by BGIP_SolverBranchAndBound< JP >::GetNextJointPolicyAndValueSpecific(), and BGIP_SolverBranchAndBound< JP >::Solve().
|
inlinevirtual |
Implements BayesianGameIdenticalPayoffSolver.
|
inlinevirtual |
Implements BayesianGameIdenticalPayoffSolver.
|
inlinevirtual |
The methods that performs the planning.
Returns the expected reward.
Implements BayesianGameIdenticalPayoffSolver.
References BGIP_SolverBranchAndBound< JP >::ComputeCompleteInformationValues(), BayesianGameIdenticalPayoffSolver::InitDeadline(), BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes(), BGIP_SolverBranchAndBound< JP >::ReSolve(), and PrintTools::SoftPrintVector().
Referenced by BGIP_SolverBranchAndBound< JP >::GetNextJointPolicyAndValueSpecific().
|
inlineprivate |
Sorts a std::vector in ascending order.
Referenced by BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes(), and BGIP_SolverBranchAndBound< JP >::SortDescending().
|
inlineprivate |
Sorts a std::vector in descending order.
References BGIP_SolverBranchAndBound< JP >::SortAscending().
Referenced by BGIP_SolverBranchAndBound< JP >::ReComputeH(), and BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes().
|
private |
the best node found so far...
|
private |
Pointer to the BG we're solving.
|
private |
Referenced by BGIP_SolverBranchAndBound< JP >::Expand(), and BGIP_SolverBranchAndBound< JP >::ReSolve().
|
private |
|
private |
Referenced by BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes().
|
private |
_m_depthFirstSpecified[agentI][typeI] specifies at what depth typeI of agentI is first specified.
This is computed when the ordering is determined.
|
private |
|
private |
|
private |
_m_jtIndexMapping[i] the i-th joint type for which a joint action will be selected, _m_jtIndexMapping[i] = j means that the j-th joint-type of the BG will be the i-th for which a .
so
|
private |
The ordering of joint types used in the search.
|
private |
the maximum depth of a search node (i.e., the depth at which it is fully
|
private |
|
private |
|
private |
Referenced by BGIP_SolverBranchAndBound< JP >::BGIP_SolverBranchAndBound(), BGIP_SolverBranchAndBound< JP >::ComputeValidJointActions(), BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionsOld(), BGIP_SolverBranchAndBound< JP >::ConvertNodeToPolicyAndAddToSolution(), BGIP_SolverBranchAndBound< JP >::ReComputeH(), and BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes().
|
private |
|
private |
|
private |
|
private |
|
private |
The number of solutions we already computed for the incremental solver.
|
private |
The priority queue keeping track of all the open nodes in the search.
Referenced by BGIP_SolverBranchAndBound< JP >::Prune(), and BGIP_SolverBranchAndBound< JP >::~BGIP_SolverBranchAndBound().
|
private |
|
private |
|
private |
Whether we already called Solve().
|
private |
Level of verboseness of the solver.