PERSEUS.hpp

Go to the documentation of this file.

#ifndef AI_TOOLBOX_POMDP_PERSEUS_HEADER_FILE
#define AI_TOOLBOX_POMDP_PERSEUS_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 PERSEUS {
        public:
            PERSEUS(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, double minReward);
 
        private:
 
            template <typename ProjectionsTable>
            VList crossSum(const ProjectionsTable & projs, const std::vector<Belief> & bl, const VList & oldV);
 
            size_t S, A, O, beliefSize_;
            unsigned horizon_;
            double tolerance_;
 
            mutable RandomEngine rand_;
    };
 
    template <IsModel M>
    std::tuple<double, ValueFunction> PERSEUS::operator()(const M & model, const double minReward) {
        if ( model.getDiscount() == 1 ) throw std::invalid_argument("The model cannot have a discount of 1 in PERSEUS!");
        // Initialize "global" variables
        S = model.getS();
        A = model.getA();
        O = model.getO();
 
        // 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);
        const auto beliefs = bGen(beliefSize_);
 
        // We initialize the ValueFunction to the "worst" case scenario.
        ValueFunction v = makeValueFunction(S);
 
        v[0][0].values.fill(minReward / (1.0 - model.getDiscount()));
 
        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.
            const auto projs = projecter(v[timestep-1]);
            // Here we find the minimum number of VEntries that we need to improve
            // v on all beliefs from v[timestep-1].
            v.emplace_back( crossSum( projs, beliefs, v[timestep-1] ) );
 
            // Check convergence
            if ( useTolerance )
                variation = weakBoundDistance(v[timestep-1], v[timestep]);
        }
 
        return std::make_tuple(useTolerance ? variation : 0.0, v);
    }
 
    template <typename ProjectionsTable>
    VList PERSEUS::crossSum(const ProjectionsTable & projs, const std::vector<Belief> & bl, const VList & oldV) {
        VList result, helper;
        result.reserve(bl.size());
        helper.reserve(A);
        bool start = true;
        double currentValue, oldValue;
 
        auto rbegin = std::begin(result);
        auto rend   = std::end  (result);
        const auto obegin = std::begin(oldV);
        const auto oend   = std::end  (oldV);
 
        for ( const auto & b : bl ) {
            if ( !start ) {
                // If we have already improved this belief, skip it
                findBestAtPoint( b, rbegin, rend, &currentValue, unwrap);
                findBestAtPoint( b, obegin, oend,   &oldValue,   unwrap);
                if ( currentValue >= oldValue ) continue;
            }
 
            result.emplace_back(crossSumBestAtBelief(b, projs));
 
            rbegin = std::begin(result);
            rend   = std::end  (result);
 
            start = false;
        }
 
        result.erase(extractDominated(rbegin, rend, unwrap), std::end(result));
 
        return result;
    }
}
 
#endif