AIToolbox::POMDP::GapMin Class Reference

This class implements the GapMin algorithm. More...

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

Public Member Functions
	GapMin (double initialTolerance, unsigned precisionDigits)
	Basic constructor. More...
void	setInitialTolerance (double initialTolerance)
	This function sets the initial tolerance used to compute the initial bounds. More...
double	getInitialTolerance () const
	This function returns the initial tolerance used to compute the initial bounds. More...
void	setPrecisionDigits (unsigned digits)
	This function sets the digits in precision for the returned solution. More...
unsigned	getPrecisionDigits () const
	This function returns the currently set digits of precision. More...
template<IsModel M>
std::tuple< double, double, VList, MDP::QFunction >	operator() (const M &model, const Belief &initialBelief)
	This function efficiently computes bounds for the optimal value of the input belief for the input POMDP. More...

Detailed Description

This class implements the GapMin algorithm.

This method works by repeatedly refining both a lower bound and upper bound for the input POMDP.

The lower bound is worked through PBVI.

The upper bound is worked through a combination of alphavectors, and a belief-value pair piecewise linear surface.

At each iteration, a set of beliefs are found that the algorithm thinks may be useful to reduce the bound.

For the lower bound, these beliefs are added to a list, and run through PBVI. Spurious beliefs are then removed.

For the upper bound, the beliefs are used to create a temporary belief POMDP, where each belief is a state. This belief is then used as input to the FastInformedBound algorithm, which refines its upper bound.

The strong point of the algorithm is that beliefs are searched by gap size, so that the beliefs that are most likely to decrease the gap are looked at first. This results in less overall work to highly reduce the bound.

In order to act, the output lower bound should be used (as it's the only one that gives an actual guarantee), but for this just using PBVI may be more useful.

Constructor & Destructor Documentation

GapMin()

AIToolbox::POMDP::GapMin::GapMin	(	double	initialTolerance,
		unsigned	precisionDigits
	)

Basic constructor.

The input parameters can heavily influence both the time and the strictness of the resulting bound.

The tolerance parameter must be >= 0.0, otherwise the function will throw an std::runtime_error.

See also

setInitialTolerance(double)

setPrecisionDigits(unsigned)

Parameters

initialTolerance	The tolerance to compute the initial bounds.
precisionDigits	The number of digits precision to stop the gap searching process.

Member Function Documentation

getInitialTolerance()

double AIToolbox::POMDP::GapMin::getInitialTolerance

(

)

const

This function returns the initial tolerance used to compute the initial bounds.

Returns

The currently set initial tolerance.

getPrecisionDigits()

unsigned AIToolbox::POMDP::GapMin::getPrecisionDigits

(

)

const

This function returns the currently set digits of precision.

See also

setPrecisionDigits(unsigned);

Returns

The currently set digits of precision to use to test for convergence.

operator()()

template<IsModel M>

std::tuple< double, double, VList, MDP::QFunction > AIToolbox::POMDP::GapMin::operator()	(	const M &	model,
		const Belief &	initialBelief
	)

This function efficiently computes bounds for the optimal value of the input belief for the input POMDP.

Parameters

model	The model to compute the gap for.
initialBelief	The belief to compute the gap for.

Returns

The lower and upper gap bounds, the lower bound VList, and the upper bound QFunction.

setInitialTolerance()

void AIToolbox::POMDP::GapMin::setInitialTolerance

(

double

initialTolerance

)

This function sets the initial tolerance used to compute the initial bounds.

This value is only used before having an initial bounds approximation. Once that has been established, the tolerance is dependent on the digits of precision parameter.

The tolerance parameter must be >= 0.0, otherwise the function will throw an std::runtime_error.

See also

setPrecisionDigits(unsigned);

Parameters

initialTolerance

The new initial tolerance.

setPrecisionDigits()

void AIToolbox::POMDP::GapMin::setPrecisionDigits

(

unsigned

digits

)

This function sets the digits in precision for the returned solution.

Depending on the values for the input model, the precision of the solution is automatically adjusted to the input precision digits.

In particular, the return threshold is equal to:

std::pow(10, std::ceil(std::log10(std::max(std::fabs(ub), std::fabs(lb))))-precisionDigits);

This is used in two ways:

• To check for lower and upper bound convergence. If the bounds difference is less than the threshold, the GapMin terminates.
• To check for gap size converngence. If the gap has not reduced by more than the threshold during the last iteration, GapMin terminates.

Parameters

digits

The number of digits of precision to use to test for convergence.

---

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

• include/AIToolbox/POMDP/Algorithms/GapMin.hpp