AIToolbox
A library that offers tools for AI problem solving.
AIToolbox::POMDP::PERSEUS Class Reference

This class implements the PERSEUS algorithm. More...

#include <AIToolbox/POMDP/Algorithms/PERSEUS.hpp>

Public Member Functions

 PERSEUS (size_t nBeliefs, unsigned h, double tolerance)
 Basic constructor. More...
 
void setTolerance (double tolerance)
 This function sets the tolerance parameter. More...
 
void setHorizon (unsigned h)
 This function sets a new horizon parameter. More...
 
void setBeliefSize (size_t nBeliefs)
 This function sets a new number of support beliefs. More...
 
double getTolerance () const
 This function returns the currently set tolerance parameter. More...
 
unsigned getHorizon () const
 This function returns the currently set horizon parameter. More...
 
size_t getBeliefSize () const
 This function returns the currently set number of support beliefs to use during a solve pass. More...
 
template<IsModel M>
std::tuple< double, ValueFunctionoperator() (const M &model, double minReward)
 This function solves a POMDP::Model approximately. More...
 

Detailed Description

This class implements the PERSEUS algorithm.

The idea behind this algorithm is very similar to PBVI. The thing that changes is how beliefs are considered; in PERSEUS we only try to find as little VEntries as possible as to ensure that all beliefs considered are improved. This allows to skip generating VEntry for most beliefs considered, since usually few VEntry are responsible for supporting most of the beliefs.

At the same time, this means that solutions found by PERSEUS may be extremely approximate with respect to the true Value Functions. This is because as long as the values for all the particle beliefs are increased, no matter how slightly, the algorithm stops looking - in effect simply guaranteeing that the worst action is never taken. However for many problems the solution found is actually very good, also given that due to the increased performance PERSEUS can do many more iterations than, for example, PBVI.

This method works best when it is allowed to iterate until convergence, and thus shouldn't be used on problems with finite horizons.

Constructor & Destructor Documentation

◆ PERSEUS()

AIToolbox::POMDP::PERSEUS::PERSEUS ( size_t  nBeliefs,
unsigned  h,
double  tolerance 
)

Basic constructor.

This constructor sets the default horizon/tolerance used to solve a POMDP::Model and the number of beliefs used to approximate the ValueFunction.

Parameters
nBeliefsThe number of support beliefs to use.
hThe horizon chosen.
toleranceThe tolerance factor to stop the PERSEUS loop.

Member Function Documentation

◆ getBeliefSize()

size_t AIToolbox::POMDP::PERSEUS::getBeliefSize ( ) const

This function returns the currently set number of support beliefs to use during a solve pass.

Returns
The number of support beliefs.

◆ getHorizon()

unsigned AIToolbox::POMDP::PERSEUS::getHorizon ( ) const

This function returns the currently set horizon parameter.

Returns
The current horizon.

◆ getTolerance()

double AIToolbox::POMDP::PERSEUS::getTolerance ( ) const

This function returns the currently set tolerance parameter.

Returns
The current tolerance.

◆ operator()()

template<IsModel M>
std::tuple< double, ValueFunction > AIToolbox::POMDP::PERSEUS::operator() ( const M &  model,
double  minReward 
)

This function solves a POMDP::Model approximately.

This function computes a set of beliefs for which to solve the input model. The beliefs are chosen stochastically, trying to cover as much as possible of the belief space in order to offer as precise a solution as possible.

The final solution will try to be as small as possible, in order to drastically improve performances, while at the same time provide a reasonably good result.

Note that the model input cannot have a discount of 1, due to how PERSEUS initializes the value function internally; if the model provided has a discount of 1 we throw.

Template Parameters
MThe type of POMDP model that needs to be solved.
Parameters
modelThe POMDP model that needs to be solved.
minRewardThe minimum reward obtainable from this model.
Returns
A tuple containing the maximum variation for the ValueFunction and the computed ValueFunction.

◆ setBeliefSize()

void AIToolbox::POMDP::PERSEUS::setBeliefSize ( size_t  nBeliefs)

This function sets a new number of support beliefs.

Parameters
nBeliefsThe new number of support beliefs.

◆ setHorizon()

void AIToolbox::POMDP::PERSEUS::setHorizon ( unsigned  h)

This function sets a new horizon parameter.

Parameters
hThe new horizon parameter.

◆ setTolerance()

void AIToolbox::POMDP::PERSEUS::setTolerance ( double  tolerance)

This function sets the tolerance parameter.

The tolerance parameter must be >= 0.0, otherwise the constructor will throw an std::runtime_error. The tolerance parameter sets the convergence criterion. A tolerance of 0.0 forces PERSEUS to perform a number of iterations equal to the horizon specified. Otherwise, PERSEUS will stop as soon as the difference between two iterations is less than the tolerance specified.

Parameters
toleranceThe new tolerance parameter.

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