PBVI.hpp

Go to the documentation of this file.

#ifndef AI_TOOLBOX_POMDP_PBVI_HEADER_FILE
#define AI_TOOLBOX_POMDP_PBVI_HEADER_FILE
 
#include <AIToolbox/Utils/Prune.hpp>
#include <AIToolbox/POMDP/Types.hpp>
#include <AIToolbox/POMDP/TypeTraits.hpp>
#include <AIToolbox/POMDP/Utils.hpp>
#include <AIToolbox/POMDP/Algorithms/Utils/Projecter.hpp>
#include <AIToolbox/POMDP/Algorithms/Utils/BeliefGenerator.hpp>
 
namespace AIToolbox::POMDP {
    class PBVI {
        public:
            PBVI(size_t nBeliefs, unsigned h, double tolerance);
 
            void setTolerance(double tolerance);
 
            void setHorizon(unsigned h);
 
            void setBeliefSize(size_t nBeliefs);
 
            double getTolerance() const;
 
            unsigned getHorizon() const;
 
            size_t getBeliefSize() const;
 
            template <IsModel M>
            std::tuple<double, ValueFunction> operator()(const M & model, ValueFunction v = {});
 
            template <IsModel M>
            std::tuple<double, ValueFunction> operator()(const M & model, const std::vector<Belief> & beliefs, ValueFunction v = {});
 
        private:
            template <typename ProjectionsRow>
            VList crossSum(const ProjectionsRow & projs, size_t a, const std::vector<Belief> & bl);
 
            size_t S, A, O, beliefSize_;
            unsigned horizon_;
            double tolerance_;
 
            mutable RandomEngine rand_;
    };
 
    template <IsModel M>
    std::tuple<double, ValueFunction> PBVI::operator()(const M & model, ValueFunction v) {
        // In this implementation we compute all beliefs in advance. This
        // is mostly due to the fact that I prefer counter parameters (how
        // many beliefs do you want?) versus timers (loop until time is
        // up). However, this is easily changeable, since the belief generator
        // can be called multiple times to increase the size of the belief
        // vector.
        BeliefGenerator bGen(model);
        return operator()(model, bGen(beliefSize_), v);
    }
 
    template <IsModel M>
    std::tuple<double, ValueFunction> PBVI::operator()(const M & model, const std::vector<Belief> & beliefs, ValueFunction v) {
        // Initialize "global" variables
        S = model.getS();
        A = model.getA();
        O = model.getO();
 
        if (v.size() == 0)
            v = makeValueFunction(S);
 
        unsigned timestep = 0;
 
        Projecter projecter(model);
 
        // And off we go
        const bool useTolerance = checkDifferentSmall(tolerance_, 0.0);
        double variation = tolerance_ * 2; // Make it bigger
        while ( timestep < horizon_ && ( !useTolerance || variation > tolerance_ ) ) {
            ++timestep;
 
            // Compute all possible outcomes, from our previous results.
            // This means that for each action-observation pair, we are going
            // to obtain the same number of possible outcomes as the number
            // of entries in our initial vector w.
            auto projs = projecter(v.back());
 
            size_t finalWSize = 0;
            // In this method we split the work by action, which will then
            // be joined again at the end of the loop. This is not required,
            // but there does not seem to be a speed boost by not doing
            // so (not that I found one, if there is one I'd like to know!)
            for ( size_t a = 0; a < A; ++a ) {
                projs[a][0] = crossSum( projs[a], a, beliefs );
                finalWSize += projs[a][0].size();
            }
            VList w;
            w.reserve(finalWSize);
 
            for ( size_t a = 0; a < A; ++a )
                w.insert(std::end(w), std::make_move_iterator(std::begin(projs[a][0])), std::make_move_iterator(std::end(projs[a][0])));
 
            auto begin = std::begin(w);
            auto end   = std::end(w);
            auto bound = begin;
            for ( const auto & belief : beliefs )
                bound = extractBestAtPoint(belief, begin, bound, end, unwrap);
 
            w.erase(bound, std::end(w));
 
            // If you want to save as much memory as possible, do this.
            // It make take some time more though since it needs to reallocate
            // and copy stuff around.
            // w.shrink_to_fit();
 
            v.emplace_back(std::move(w));
 
            // Check convergence
            if ( useTolerance )
                variation = weakBoundDistance(v[v.size()-2], v.back());
        }
 
        return std::make_tuple(useTolerance ? variation : 0.0, v);
    }
 
    template <typename ProjectionsRow>
    VList PBVI::crossSum(const ProjectionsRow & projs, const size_t a, const std::vector<Belief> & bl) {
        VList result;
        result.reserve(bl.size());
 
        for ( const auto & b : bl )
            result.emplace_back(crossSumBestAtBelief(b, projs, a));
 
        const auto rbegin = std::begin(result);
        const auto rend   = std::end  (result);
 
        result.erase(extractDominated(rbegin, rend, unwrap), rend);
 
        return result;
    }
}
 
#endif