|
AIToolbox
A library that offers tools for AI problem solving.
|
This class represents the LinearSupport algorithm. More...
#include <AIToolbox/POMDP/Algorithms/LinearSupport.hpp>
Public Member Functions | |
| LinearSupport (unsigned horizon, double tolerance) | |
| Basic constructor. More... | |
| void | setTolerance (double tolerance) |
| 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 represents the LinearSupport algorithm.
This method is similar in spirit to Witness. The idea is that we look at certain belief points, and we try to find the best alphavectors in those points. Rather than looking for them though, the idea here is that we know where they are, if there are any at all.
As the ValueFunction is piecewise linear and convex, if there's any other hyperplane that we can add to improve it, the improvements are going to be maximal at one of the vertices of the original surface.
The idea thus is the following: first we compute the set of alphavectors for the corners, so we can be sure about them. Then we find all vertices that those alphavectors create, and we compute the error between the true ValueFunction and their current values.
If the error is greater than a certain amount, we allow their supporting alphavector to join the ValueFunction, and we increase the size of the vertex set by adding all new vertices that are created by adding the new surface (and removing the ones that are made useless by it).
We repeat until we have checked all available vertices, and at that point we are done.
While this can be a very inefficient algorithm, the fact that vertices are checked in an orderly fashion, from highest error to lowest, allows if one needs it to convert this algorithm into an anytime algorithm. Even if there is limited time to compute the solution, the algorithm is guaranteed to work in the areas with high error first, allowing one to compute good approximations even without a lot of resources.
| AIToolbox::POMDP::LinearSupport::LinearSupport | ( | 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 LinearSupport to perform a number of iterations equal to the horizon specified. Otherwise, LinearSupport will stop as soon as the difference between two iterations is less than the tolerance specified.
| horizon | The horizon chosen. |
| tolerance | The tolerance factor to stop the value iteration loop. |
| unsigned AIToolbox::POMDP::LinearSupport::getHorizon | ( | ) | const |
This function returns the currently set horizon parameter.
| double AIToolbox::POMDP::LinearSupport::getTolerance | ( | ) | const |
This function will return the currently set tolerance parameter.
| std::tuple< double, ValueFunction > AIToolbox::POMDP::LinearSupport::operator() | ( | const M & | model | ) |
This function solves a POMDP::Model completely.
This function is pretty expensive (as are possibly all POMDP solvers). It evaluates all vertices in the ValueFunction surface in order to determine whether it is complete, otherwise it improves it incrementally.
| M | The type of POMDP model that needs to be solved. |
| model | The POMDP model that needs to be solved. |
| void AIToolbox::POMDP::LinearSupport::setHorizon | ( | unsigned | h | ) |
This function allows setting the horizon parameter.
| h | The new horizon parameter. |
| void AIToolbox::POMDP::LinearSupport::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 LinearSupport to perform a number of iterations equal to the horizon specified. Otherwise, LinearSupport will stop as soon as the difference between two iterations is less than the tolerance specified.
| tolerance | The new tolerance parameter. |