|
AIToolbox
A library that offers tools for AI problem solving.
|
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, ValueFunction > | operator() (const M &model) |
| This function solves a POMDP::Model completely. More... | |
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.
| 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.
| h | The horizon chosen. |
| tolerance | The tolerance factor to stop the IncrementalPruning loop. |
| unsigned AIToolbox::POMDP::IncrementalPruning::getHorizon | ( | ) | const |
This function returns the currently set horizon parameter.
| double AIToolbox::POMDP::IncrementalPruning::getTolerance | ( | ) | const |
This function will return the currently set tolerance parameter.
| 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.
| M | The type of POMDP model that needs to be solved. |
| model | The POMDP model that needs to be solved. |
| void AIToolbox::POMDP::IncrementalPruning::setHorizon | ( | unsigned | h | ) |
This function allows setting the horizon parameter.
| h | The new horizon parameter. |
| 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.
| t | The new tolerance parameter. |