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

This class implements the Incremental Pruning algorithm. More...

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

Public Member Functions

 IncrementalPruning (unsigned h, 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, ValueFunctionoperator() (const M &model)
 This function solves a POMDP::Model completely. More...
 

Detailed Description

This class implements the Incremental Pruning algorithm.

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

From each solution, it computes the full set of possible projections. It then computes all possible cross-sums of such projections, in order to compute all possible vectors that can be included in the final solution.

What makes this method unique is its pruning strategy. Instead of generating every possible vector, combining them and pruning, it tries to prune at every possible occasion in order to minimize the number of possible vectors at any given time. Thus it will prune after creating the projections, after every single cross-sum, and in the end when combining all projections for each action.

The performances of this method are heavily dependent on the linear programming methods used. In particular, this code currently utilizes the lp_solve55 library. However, this library is not the most efficient implementation, as it defaults to a somewhat slow solver, and its problem-building API also tends to be slow due to lots of bounds checking (which are cool, but sometimes people know what they are doing). Still, to avoid replicating infinite amounts of code and managing memory by ourselves, we use its API. It would be nice if one day we could port directly into the code a fast lp implementation; for now we do what we can.

Constructor & Destructor Documentation

◆ IncrementalPruning()

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

Parameters
hThe horizon chosen.
toleranceThe tolerance factor to stop the IncrementalPruning loop.

Member Function Documentation

◆ getHorizon()

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

This function returns the currently set horizon parameter.

Returns
The current horizon.

◆ getTolerance()

double AIToolbox::POMDP::IncrementalPruning::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::IncrementalPruning::operator() ( const M &  model)

This function solves a POMDP::Model completely.

This function is pretty expensive (as are possibly all POMDP solvers). It generates for each new solved timestep the whole set of possible ValueFunctions, and prunes it incrementally, trying to reduce as much as possible the linear programming solves required.

Template Parameters
MThe type of POMDP model that needs to be solved.
Parameters
modelThe 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::IncrementalPruning::setHorizon ( unsigned  h)

This function allows setting the horizon parameter.

Parameters
hThe new horizon parameter.

◆ setTolerance()

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

Parameters
tThe new tolerance parameter.

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