AIToolbox::POMDP::Witness Class Reference

This class implements the Witness algorithm. More...

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

Public Member Functions
	Witness (unsigned horizon, double tolerance)
	Basic constructor. More...
void	setTolerance (double t)
	This function sets the tolerance parameter. More...
void	setHorizon (unsigned h)
	This function allows setting the horizon parameter. More...
double	getTolerance () const
	This function will return the currently set tolerance parameter. More...
unsigned	getHorizon () const
	This function returns the currently set horizon parameter. More...
template<IsModel M>
std::tuple< double, ValueFunction >	operator() (const M &model)
	This function solves a POMDP::Model completely. More...

Detailed Description

This class implements the Witness algorithm.

This algorithm solves a POMDP Model perfectly. It computes solutions for each horizon incrementally, every new solution building upon the previous one.

The Witness algorithm tries to avoid creating all possible cross-sums of the projected vectors. Instead, it relies on a proof that states that if a VEntry is suboptimal, then we can at least find a better one by modifying a single subtree.

Given this, the Witness algorithm starts off by finding a single optimal VEntry for a random belief. Then, using the theorem, it knows that if a better VEntry exists, then there must be at least one VEntry completely equal to the one we just found but for a subtree, and that one will be better. Thus, it adds to an agenda all possible variations of the found optimal VEntry.

From there, it examines each one of them, trying to look for a witness point. Once found, again it produces an optimal VEntry for that point and adds to the agenda all of its possible variations. VEntry which do not have any witness points are removed from the agenda.

In addition, Witness will not add to the agenda any VEntry which it has already added; it uses a set to keep track of which combinations of subtrees it has already tried.

Constructor & Destructor Documentation

Witness()

AIToolbox::POMDP::Witness::Witness	(	unsigned	horizon,
		double	tolerance
	)

Basic constructor.

This constructor sets the default horizon used to solve a POMDP::Model.

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 Witness to perform a number of iterations equal to the horizon specified. Otherwise, Witness will stop as soon as the difference between two iterations is less than the tolerance specified.

Parameters

horizon	The horizon chosen.
tolerance	The tolerance factor to stop the value iteration loop.

Member Function Documentation

getHorizon()

unsigned AIToolbox::POMDP::Witness::getHorizon

(

)

const

This function returns the currently set horizon parameter.

Returns

The current horizon.

getTolerance()

double AIToolbox::POMDP::Witness::getTolerance

(

)

const

This function will return the currently set tolerance parameter.

Returns

The currently set tolerance parameter.

operator()()

template<IsModel M>

std::tuple< double, ValueFunction > AIToolbox::POMDP::Witness::operator()

(

const M &

model

)

This function solves a POMDP::Model completely.

This function is pretty expensive (as are possibly all POMDP solvers). It solves a series of LPs trying to find all possible beliefs where an alphavector has not yet been found.

Template Parameters

M	The type of POMDP model that needs to be solved.

Parameters

model

The POMDP model that needs to be solved.

Returns

A tuple containing the maximum variation for the ValueFunction and the computed ValueFunction.

setHorizon()

void AIToolbox::POMDP::Witness::setHorizon

(

unsigned

h

)

This function allows setting the horizon parameter.

Parameters

h	The new horizon parameter.

setTolerance()

void AIToolbox::POMDP::Witness::setTolerance

(

double

t

)

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 Witness to perform a number of iterations equal to the horizon specified. Otherwise, Witness will stop as soon as the difference between two iterations is less than the tolerance specified.

Parameters

t	The new tolerance parameter.

---

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

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